<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[182808] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/182808">182808</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-04-14 14:08:02 -0700 (Tue, 14 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Add a conservative DFA minimizer for the content extension matcher
https://bugs.webkit.org/show_bug.cgi?id=143501
Reviewed by Alex Christensen.
Source/WebCore:
This patch adds a simple minimizer for DFA graphs. It is not a perfect minimizer:
some indistinguishable are not merged, but no two distinguishable are merged.
The general idea of the algorithm is to put all the state into a single set
and partition iteratively until it is impossible to split any subset by using
a transition to distinguish two states.
Let's ignore fallback transition for now, and I'll explain later how they fit in
the big picture.
The first thing we do is create a partition of the transition by grouping every
transition by the same character in the same subset. This partition of transitions
is the base by which we will partition the states.
Each subset in the transition partition is a "distinguisher" by which we can
separate the state partition.
We also create a second partition, the state partition. This is where we keep
all the subsets of states that have been split so far.
Let say we have the following graph.
1 --a--> 2
1 --b--> 3
2 --c--> 4 (final)
3 --c--> 4 (final)
The partition of transition would start with:
Set 0:
1 --a--> 2
Set 1:
1 --b--> 3
Set 2:
2 --c--> 4
3 --c--> 4
The state partition would have a single set with { 1, 2, 3, 4 }.
Next, we split the state partition by distinguishable final states. In this case,
we would split it into { 1, 2, 3 }, { 4 }.
We then refine the transition partition by splitting it by the states that have
been distinguished. Here, the only transitions to 4 are both is the same set (set 2),
so the transition partition remains the same.
We can now execute the main loop of the algorithm:
1) Split the states by the transitions.
2) Split the transitions that are now reaching two different sets of the state partition.
3) Add any newly discovered "distinguisher" (the ones we split) to the list of "distinguisher"
to process.
In this case, we just iterate over the partition set in order, and add newly split transitions
to the end of the list.
In the example, we would first visit set 0. We have that state 1 is distinguishable
by "a", and the state partition would become { 1 }, { 2, 3 }, { 4 }.
We then visit transition set 1, it distinguishes state 1 which is already alone -> nothing to do.
Finally, we process the transition set 2, it distinguishes 2 and 3, they are already in the same
set -> nothing to do.
There is no more transition to process, we have 3 unique subsets and we should merge 2 and 3.
---
Okay, now how to we fit fallback transition in this model. In this patch, I take the conservative
approach: we split everything assuming fallback transition do not exist, then we refine
by the fallback transitions.
Let's take the following example:
1 --a--> 3
2 --a--> 3
1 -[f]-> 4
2 -[f]-> 5
and at this stage in the algorithm, we have the sets { 1, 2 }, { 3 }, { 4 }, { 5 }.
The states 1 and 2 are together because they cannot be distinguished by 'a', but
the fallback transition distinguishes them.
Since we have done every other split, we have one useful property: we know that every
state in every set transition with the exact set of characters within that set.
If that was not true, there would be one "distinguisher" 'x' that could spit the set
into two subsets: the one with the transition 'x' and the ones without.
Since all the transitions are the same, there is no overlap between the defined transition
and the fallback transition. Consequently, we can use the fallback transition as a whole
transition and use it to distinguish the states.
The fallback transitions are handled like any other transition, we have a partition of such
transitions and split by each of them. BUT, we can only use them after every unique transition
has been covered.
This trick is also what makes the minimization imperfect: it should be possible to merge
states with overlap in their fallback transitions but we would split them.
---
Antti Valmari, Petri Lehtinen, Marie-Pierre Béal and Maxime Crochemore deserve credit for their indirect
work on this patch. Thanks for your wonderful papers about DFA minimization.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::minimize):
(WebCore::ContentExtensions::DFA::debugPrintDot):
* contentextensions/DFA.h:
* contentextensions/DFABytecodeCompiler.cpp:
(WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
* contentextensions/DFAMinimizer.cpp: Added.
(WebCore::ContentExtensions::DFAMinimizer::simplifyTransitions):
(WebCore::ContentExtensions::DFAMinimizer::Partition::initialize):
(WebCore::ContentExtensions::DFAMinimizer::Partition::markElementInCurrentGeneration):
(WebCore::ContentExtensions::DFAMinimizer::Partition::refineGeneration):
(WebCore::ContentExtensions::DFAMinimizer::Partition::iterateSet):
(WebCore::ContentExtensions::DFAMinimizer::Partition::setIndex):
(WebCore::ContentExtensions::DFAMinimizer::Partition::firstElementInSet):
(WebCore::ContentExtensions::DFAMinimizer::Partition::size):
(WebCore::ContentExtensions::DFAMinimizer::Partition::SetDescriptor::indexAfterMarkedElements):
(WebCore::ContentExtensions::DFAMinimizer::Partition::SetDescriptor::end):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::FullGraphPartition):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::markNode):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::refinePartitions):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::splitByUniqueTransitions):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::splitByFallbackTransitions):
(WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::nodeReplacement):
(WebCore::ContentExtensions::DFAMinimizer::ActionKey::ActionKey):
(WebCore::ContentExtensions::DFAMinimizer::ActionKey::isEmptyValue):
(WebCore::ContentExtensions::DFAMinimizer::ActionKey::isDeletedValue):
(WebCore::ContentExtensions::DFAMinimizer::ActionKeyHash::hash):
(WebCore::ContentExtensions::DFAMinimizer::ActionKeyHash::equal):
(WebCore::ContentExtensions::DFAMinimizer::minimize):
* contentextensions/DFAMinimizer.h: Copied from Source/WebCore/contentextensions/DFA.h.
* contentextensions/DFANode.h:
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::simplifyTransitions): Deleted.
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreWebCorexcodeprojprojectpbxproj">trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAh">trunk/Source/WebCore/contentextensions/DFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFANodeh">trunk/Source/WebCore/contentextensions/DFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAh">trunk/Source/WebCore/contentextensions/NFAToDFA.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizercpp">trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizerh">trunk/Source/WebCore/contentextensions/DFAMinimizer.h</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/ChangeLog 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -1,3 +1,152 @@
</span><ins>+2015-04-14 Benjamin Poulain <benjamin@webkit.org>
+
+ Add a conservative DFA minimizer for the content extension matcher
+ https://bugs.webkit.org/show_bug.cgi?id=143501
+
+ Reviewed by Alex Christensen.
+
+ This patch adds a simple minimizer for DFA graphs. It is not a perfect minimizer:
+ some indistinguishable are not merged, but no two distinguishable are merged.
+
+ The general idea of the algorithm is to put all the state into a single set
+ and partition iteratively until it is impossible to split any subset by using
+ a transition to distinguish two states.
+
+ Let's ignore fallback transition for now, and I'll explain later how they fit in
+ the big picture.
+
+
+ The first thing we do is create a partition of the transition by grouping every
+ transition by the same character in the same subset. This partition of transitions
+ is the base by which we will partition the states.
+
+ Each subset in the transition partition is a "distinguisher" by which we can
+ separate the state partition.
+
+ We also create a second partition, the state partition. This is where we keep
+ all the subsets of states that have been split so far.
+
+ Let say we have the following graph.
+
+ 1 --a--> 2
+ 1 --b--> 3
+ 2 --c--> 4 (final)
+ 3 --c--> 4 (final)
+
+ The partition of transition would start with:
+ Set 0:
+ 1 --a--> 2
+ Set 1:
+ 1 --b--> 3
+ Set 2:
+ 2 --c--> 4
+ 3 --c--> 4
+
+ The state partition would have a single set with { 1, 2, 3, 4 }.
+
+
+ Next, we split the state partition by distinguishable final states. In this case,
+ we would split it into { 1, 2, 3 }, { 4 }.
+
+ We then refine the transition partition by splitting it by the states that have
+ been distinguished. Here, the only transitions to 4 are both is the same set (set 2),
+ so the transition partition remains the same.
+
+
+ We can now execute the main loop of the algorithm:
+ 1) Split the states by the transitions.
+ 2) Split the transitions that are now reaching two different sets of the state partition.
+ 3) Add any newly discovered "distinguisher" (the ones we split) to the list of "distinguisher"
+ to process.
+
+ In this case, we just iterate over the partition set in order, and add newly split transitions
+ to the end of the list.
+
+ In the example, we would first visit set 0. We have that state 1 is distinguishable
+ by "a", and the state partition would become { 1 }, { 2, 3 }, { 4 }.
+
+ We then visit transition set 1, it distinguishes state 1 which is already alone -> nothing to do.
+
+ Finally, we process the transition set 2, it distinguishes 2 and 3, they are already in the same
+ set -> nothing to do.
+
+ There is no more transition to process, we have 3 unique subsets and we should merge 2 and 3.
+
+ ---
+
+ Okay, now how to we fit fallback transition in this model. In this patch, I take the conservative
+ approach: we split everything assuming fallback transition do not exist, then we refine
+ by the fallback transitions.
+
+ Let's take the following example:
+ 1 --a--> 3
+ 2 --a--> 3
+ 1 -[f]-> 4
+ 2 -[f]-> 5
+
+ and at this stage in the algorithm, we have the sets { 1, 2 }, { 3 }, { 4 }, { 5 }.
+ The states 1 and 2 are together because they cannot be distinguished by 'a', but
+ the fallback transition distinguishes them.
+
+ Since we have done every other split, we have one useful property: we know that every
+ state in every set transition with the exact set of characters within that set.
+ If that was not true, there would be one "distinguisher" 'x' that could spit the set
+ into two subsets: the one with the transition 'x' and the ones without.
+
+ Since all the transitions are the same, there is no overlap between the defined transition
+ and the fallback transition. Consequently, we can use the fallback transition as a whole
+ transition and use it to distinguish the states.
+
+ The fallback transitions are handled like any other transition, we have a partition of such
+ transitions and split by each of them. BUT, we can only use them after every unique transition
+ has been covered.
+
+ This trick is also what makes the minimization imperfect: it should be possible to merge
+ states with overlap in their fallback transitions but we would split them.
+
+ ---
+
+ Antti Valmari, Petri Lehtinen, Marie-Pierre Béal and Maxime Crochemore deserve credit for their indirect
+ work on this patch. Thanks for your wonderful papers about DFA minimization.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::minimize):
+ (WebCore::ContentExtensions::DFA::debugPrintDot):
+ * contentextensions/DFA.h:
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
+ * contentextensions/DFAMinimizer.cpp: Added.
+ (WebCore::ContentExtensions::DFAMinimizer::simplifyTransitions):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::initialize):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::markElementInCurrentGeneration):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::refineGeneration):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::iterateSet):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::setIndex):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::firstElementInSet):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::size):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::SetDescriptor::indexAfterMarkedElements):
+ (WebCore::ContentExtensions::DFAMinimizer::Partition::SetDescriptor::end):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::FullGraphPartition):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::markNode):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::refinePartitions):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::splitByUniqueTransitions):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::splitByFallbackTransitions):
+ (WebCore::ContentExtensions::DFAMinimizer::FullGraphPartition::nodeReplacement):
+ (WebCore::ContentExtensions::DFAMinimizer::ActionKey::ActionKey):
+ (WebCore::ContentExtensions::DFAMinimizer::ActionKey::isEmptyValue):
+ (WebCore::ContentExtensions::DFAMinimizer::ActionKey::isDeletedValue):
+ (WebCore::ContentExtensions::DFAMinimizer::ActionKeyHash::hash):
+ (WebCore::ContentExtensions::DFAMinimizer::ActionKeyHash::equal):
+ (WebCore::ContentExtensions::DFAMinimizer::minimize):
+ * contentextensions/DFAMinimizer.h: Copied from Source/WebCore/contentextensions/DFA.h.
+ * contentextensions/DFANode.h:
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ (WebCore::ContentExtensions::simplifyTransitions): Deleted.
+
</ins><span class="cx"> 2015-04-14 Chris Dumez <cdumez@apple.com>
</span><span class="cx">
</span><span class="cx"> ASSERT(frame().view() == this) assertion hit in FrameView::windowClipRect() on Windows bots
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -1003,16 +1003,18 @@
</span><span class="cx"> 26601EBF14B3B9AD0012C0FE /* PlatformEventFactoryIOS.h in Headers */ = {isa = PBXBuildFile; fileRef = 26601EBD14B3B9AD0012C0FE /* PlatformEventFactoryIOS.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26601EC014B3B9AD0012C0FE /* PlatformEventFactoryIOS.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26601EBE14B3B9AD0012C0FE /* PlatformEventFactoryIOS.mm */; };
</span><span class="cx"> 267725FC1A5B3AD9003C24DD /* DFA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 267725F61A5B3AD9003C24DD /* DFA.cpp */; };
</span><del>- 267725FD1A5B3AD9003C24DD /* DFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725F71A5B3AD9003C24DD /* DFA.h */; };
- 267725FF1A5B3AD9003C24DD /* DFANode.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725F91A5B3AD9003C24DD /* DFANode.h */; };
</del><ins>+ 267725FD1A5B3AD9003C24DD /* DFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725F71A5B3AD9003C24DD /* DFA.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 267725FF1A5B3AD9003C24DD /* DFANode.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725F91A5B3AD9003C24DD /* DFANode.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 267726001A5B3AD9003C24DD /* NFAToDFA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 267725FA1A5B3AD9003C24DD /* NFAToDFA.cpp */; };
</span><del>- 267726011A5B3AD9003C24DD /* NFAToDFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725FB1A5B3AD9003C24DD /* NFAToDFA.h */; };
</del><ins>+ 267726011A5B3AD9003C24DD /* NFAToDFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 267725FB1A5B3AD9003C24DD /* NFAToDFA.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 267726041A5DF6F2003C24DD /* URLFilterParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 267726021A5DF6F2003C24DD /* URLFilterParser.cpp */; };
</span><span class="cx"> 267726051A5DF6F2003C24DD /* URLFilterParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 267726031A5DF6F2003C24DD /* URLFilterParser.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 269239961505E1AA009E57FC /* JSIDBVersionChangeEvent.h in Headers */ = {isa = PBXBuildFile; fileRef = 269239921505E1AA009E57FC /* JSIDBVersionChangeEvent.h */; };
</span><span class="cx"> 269397221A4A412F00E8349D /* NFANode.h in Headers */ = {isa = PBXBuildFile; fileRef = 269397201A4A412F00E8349D /* NFANode.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 269397241A4A5B6400E8349D /* NFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 269397231A4A5B6400E8349D /* NFA.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 269397261A4A5FBD00E8349D /* NFA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 269397251A4A5FBD00E8349D /* NFA.cpp */; };
</span><ins>+ 26A517FD1AB92238006335DF /* DFAMinimizer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */; };
+ 26A517FE1AB92238006335DF /* DFAMinimizer.h in Headers */ = {isa = PBXBuildFile; fileRef = 26A517FC1AB92238006335DF /* DFAMinimizer.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 26AA0F9E18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26AA0F9D18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp */; };
</span><span class="cx"> 26B9998F1803AE7200D01121 /* RegisterAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 26B9998E1803AE7200D01121 /* RegisterAllocator.h */; };
</span><span class="cx"> 26B999911803B3C900D01121 /* StackAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 26B999901803B3C900D01121 /* StackAllocator.h */; };
</span><span class="lines">@@ -8102,6 +8104,8 @@
</span><span class="cx"> 269397201A4A412F00E8349D /* NFANode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NFANode.h; sourceTree = "<group>"; };
</span><span class="cx"> 269397231A4A5B6400E8349D /* NFA.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NFA.h; sourceTree = "<group>"; };
</span><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NFA.cpp; sourceTree = "<group>"; };
</span><ins>+ 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFAMinimizer.cpp; sourceTree = "<group>"; };
+ 26A517FC1AB92238006335DF /* DFAMinimizer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFAMinimizer.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26AA0F9918D2973D00419381 /* makeSelectorPseudoElementsMap.py */ = {isa = PBXFileReference; lastKnownFileType = text.script.python; path = makeSelectorPseudoElementsMap.py; sourceTree = "<group>"; };
</span><span class="cx"> 26AA0F9A18D2973D00419381 /* SelectorPseudoElementTypeMap.in */ = {isa = PBXFileReference; lastKnownFileType = text; path = SelectorPseudoElementTypeMap.in; sourceTree = "<group>"; };
</span><span class="cx"> 26AA0F9D18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SelectorPseudoElementTypeMap.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15535,6 +15539,8 @@
</span><span class="cx"> 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */,
</span><span class="cx"> 5C3930601AA0F6A90029C816 /* DFABytecodeInterpreter.cpp */,
</span><span class="cx"> 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */,
</span><ins>+ 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */,
+ 26A517FC1AB92238006335DF /* DFAMinimizer.h */,
</ins><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */,
</span><span class="cx"> 269397231A4A5B6400E8349D /* NFA.h */,
</span><span class="lines">@@ -23659,6 +23665,7 @@
</span><span class="cx"> 316FE1120E6E1DA700BF6088 /* AnimationBase.h in Headers */,
</span><span class="cx"> 316FE1140E6E1DA700BF6088 /* AnimationController.h in Headers */,
</span><span class="cx"> 0F15DA8A0F3AAEE70000CE47 /* AnimationControllerPrivate.h in Headers */,
</span><ins>+ 26A517FE1AB92238006335DF /* DFAMinimizer.h in Headers */,
</ins><span class="cx"> 5CBC8DAD1AAA302200E1C803 /* MediaAccessibilitySoftLink.h in Headers */,
</span><span class="cx"> 49E912AD0EFAC906009D0CAF /* AnimationList.h in Headers */,
</span><span class="cx"> 6C568CB119DAFEA000430CA2 /* MaskImageOperation.h in Headers */,
</span><span class="lines">@@ -30363,6 +30370,7 @@
</span><span class="cx"> A833C7CC0A2CF07400D57664 /* XLinkNames.cpp in Sources */,
</span><span class="cx"> 00B9318713BA8DB30035A948 /* XMLDocumentParser.cpp in Sources */,
</span><span class="cx"> 00B9318913BA8DBC0035A948 /* XMLDocumentParserLibxml2.cpp in Sources */,
</span><ins>+ 26A517FD1AB92238006335DF /* DFAMinimizer.cpp in Sources */,
</ins><span class="cx"> 00B9318B13BA8DC90035A948 /* XMLDocumentParserScope.cpp in Sources */,
</span><span class="cx"> 59C28045138DC2410079B7E2 /* XMLErrors.cpp in Sources */,
</span><span class="cx"> BC772C460C4EB2C60083285F /* XMLHttpRequest.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -189,12 +189,29 @@
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><del>- double dfaBuildTimeStart = monotonicallyIncreasingTime();
</del><ins>+ double totalNFAToByteCodeBuildTimeStart = monotonicallyIncreasingTime();
</ins><span class="cx"> #endif
</span><ins>+
</ins><span class="cx"> Vector<DFABytecode> bytecode;
</span><span class="cx"> for (size_t i = 0; i < nfas.size(); ++i) {
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaBuildTimeStart = monotonicallyIncreasingTime();
+#endif
</ins><span class="cx"> DFA dfa = NFAToDFA::convert(nfas[i]);
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaBuildTimeEnd = monotonicallyIncreasingTime();
+ dataLogF(" Time spent building the DFA %zu: %f\n", i, (dfaBuildTimeEnd - dfaBuildTimeStart));
+#endif
</ins><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaMinimizationTimeStart = monotonicallyIncreasingTime();
+#endif
+ dfa.minimize();
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaMinimizationTimeEnd = monotonicallyIncreasingTime();
+ dataLogF(" Time spent miniminizing the DFA %zu: %f\n", i, (dfaMinimizationTimeEnd - dfaMinimizationTimeStart));
+#endif
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> WTFLogAlways("DFA %zu", i);
</span><span class="cx"> dfa.debugPrintDot();
</span><span class="lines">@@ -211,8 +228,8 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><del>- double dfaBuildTimeEnd = monotonicallyIncreasingTime();
- dataLogF(" Time spent building and compiling the DFAs: %f\n", (dfaBuildTimeEnd - dfaBuildTimeStart));
</del><ins>+ double totalNFAToByteCodeBuildTimeEnd = monotonicallyIncreasingTime();
+ dataLogF(" Time spent building and compiling the DFAs: %f\n", (totalNFAToByteCodeBuildTimeEnd - totalNFAToByteCodeBuildTimeStart));
</ins><span class="cx"> dataLogF(" Bytecode size %zu\n", bytecode.size());
</span><span class="cx"> dataLogF(" DFA count %zu\n", nfas.size());
</span><span class="cx"> #endif
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "DFAMinimizer.h"
</ins><span class="cx"> #include <wtf/DataLog.h>
</span><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="lines">@@ -59,6 +60,11 @@
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void DFA::minimize()
+{
+ m_root = DFAMinimizer::minimize(m_nodes, m_root);
+}
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> static void printRange(bool firstRange, char rangeStart, char rangeEnd)
</span><span class="cx"> {
</span><span class="lines">@@ -129,6 +135,9 @@
</span><span class="cx"> dataLogF(" node [shape=circle];\n");
</span><span class="cx"> dataLogF(" {\n");
</span><span class="cx"> for (unsigned i = 0; i < m_nodes.size(); ++i) {
</span><ins>+ if (m_nodes[i].isKilled)
+ continue;
+
</ins><span class="cx"> dataLogF(" %d [label=<Node %d", i, i);
</span><span class="cx"> const Vector<uint64_t>& actions = m_nodes[i].actions;
</span><span class="cx"> if (!actions.isEmpty()) {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -37,7 +37,7 @@
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><span class="cx"> // The DFA abstract a partial DFA graph in a compact form.
</span><del>-class DFA {
</del><ins>+class WEBCORE_EXPORT DFA {
</ins><span class="cx"> public:
</span><span class="cx"> DFA();
</span><span class="cx"> DFA(Vector<DFANode>&& nodes, unsigned rootIndex);
</span><span class="lines">@@ -50,6 +50,8 @@
</span><span class="cx"> const DFANode& nodeAt(unsigned i) const { return m_nodes[i]; }
</span><span class="cx"> DFANode& nodeAt(unsigned i) { return m_nodes[i]; }
</span><span class="cx">
</span><ins>+ void minimize();
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #endif
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -96,6 +96,10 @@
</span><span class="cx"> void DFABytecodeCompiler::compileNode(unsigned index, bool root)
</span><span class="cx"> {
</span><span class="cx"> const DFANode& node = m_dfa.nodeAt(index);
</span><ins>+ if (node.isKilled) {
+ m_nodeStartOffsets[index] = std::numeric_limits<unsigned>::max();
+ return;
+ }
</ins><span class="cx">
</span><span class="cx"> // Record starting index for linking.
</span><span class="cx"> if (!root)
</span><span class="lines">@@ -214,8 +218,14 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Link.
</span><del>- for (const auto& linkRecord : m_linkRecords)
- set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
</del><ins>+ for (const auto& linkRecord : m_linkRecords) {
+ unsigned offset = linkRecord.first;
+ ASSERT(!(*reinterpret_cast<unsigned*>(&m_bytecode[offset])));
+
+ unsigned target = m_nodeStartOffsets[linkRecord.second];
+ RELEASE_ASSERT(target != std::numeric_limits<unsigned>::max());
+ set32Bits(m_bytecode, offset, m_nodeStartOffsets[linkRecord.second]);
+ }
</ins><span class="cx">
</span><span class="cx"> // Set size header.
</span><span class="cx"> set32Bits(m_bytecode, startLocation, m_bytecode.size() - startLocation);
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAMinimizercpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (0 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -0,0 +1,519 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFAMinimizer.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include <wtf/HashSet.h>
+#include <wtf/StringHasher.h>
+
+namespace WebCore {
+namespace ContentExtensions {
+
+namespace {
+
+// simplifyTransitions() tries to collapse individual transitions into fallback transitions.
+// After simplifyTransitions(), you can also make the assumption that a fallback transition target will never be
+// also the target of an individual transition.
+static void simplifyTransitions(Vector<DFANode>& dfaGraph)
+{
+ for (DFANode& dfaNode : dfaGraph) {
+ if (!dfaNode.hasFallbackTransition
+ && ((dfaNode.transitions.size() == 126 && !dfaNode.transitions.contains(0))
+ || (dfaNode.transitions.size() == 127 && dfaNode.transitions.contains(0)))) {
+ unsigned bestTarget = std::numeric_limits<unsigned>::max();
+ unsigned bestTargetScore = 0;
+ HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;
+ for (const auto& transition : dfaNode.transitions) {
+ if (!transition.key)
+ continue;
+
+ unsigned transitionTarget = transition.value;
+ auto addResult = targetHistogram.add(transitionTarget, 1);
+ if (!addResult.isNewEntry)
+ addResult.iterator->value++;
+
+ if (addResult.iterator->value > bestTargetScore) {
+ bestTargetScore = addResult.iterator->value;
+ bestTarget = transitionTarget;
+ }
+ }
+ ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");
+
+ dfaNode.hasFallbackTransition = true;
+ dfaNode.fallbackTransition = bestTarget;
+ }
+
+ if (dfaNode.hasFallbackTransition) {
+ Vector<uint16_t, 128> keys;
+ DFANodeTransitions& transitions = dfaNode.transitions;
+ copyKeysToVector(transitions, keys);
+
+ for (uint16_t key : keys) {
+ auto transitionIterator = transitions.find(key);
+ if (transitionIterator->value == dfaNode.fallbackTransition)
+ transitions.remove(transitionIterator);
+ }
+ }
+ }
+}
+
+class Partition {
+public:
+ void initialize(unsigned size)
+ {
+ if (!size)
+ return;
+
+ m_sets.reserveInitialCapacity(size);
+ m_partitionedElements.resize(size);
+ m_elementPositionInPartitionedNodes.resize(size);
+ m_elementToSetMap.resize(size);
+
+ for (unsigned i = 0; i < size; ++i) {
+ m_partitionedElements[i] = i;
+ m_elementPositionInPartitionedNodes[i] = i;
+ m_elementToSetMap[i] = 0;
+ }
+ m_sets.append(SetDescriptor({ 0, size, 0 }));
+ }
+
+ void markElementInCurrentGeneration(unsigned elementIndex)
+ {
+ // Swap the node with the first unmarked node.
+ unsigned setIndex = m_elementToSetMap[elementIndex];
+ SetDescriptor& setDescriptor = m_sets[setIndex];
+
+ unsigned elementPositionInPartition = m_elementPositionInPartitionedNodes[elementIndex];
+ ASSERT(elementPositionInPartition >= setDescriptor.start);
+ ASSERT(elementPositionInPartition < setDescriptor.end());
+
+ unsigned firstUnmarkedElementPositionInPartition = setDescriptor.indexAfterMarkedElements();
+ ASSERT(firstUnmarkedElementPositionInPartition >= setDescriptor.start && firstUnmarkedElementPositionInPartition < setDescriptor.end());
+ ASSERT(firstUnmarkedElementPositionInPartition >= firstUnmarkedElementPositionInPartition);
+
+ // Swap the nodes in the set.
+ unsigned firstUnmarkedElement = m_partitionedElements[firstUnmarkedElementPositionInPartition];
+ m_partitionedElements[firstUnmarkedElementPositionInPartition] = elementIndex;
+ m_partitionedElements[elementPositionInPartition] = firstUnmarkedElement;
+
+ // Update their index.
+ m_elementPositionInPartitionedNodes[elementIndex] = firstUnmarkedElementPositionInPartition;
+ m_elementPositionInPartitionedNodes[firstUnmarkedElement] = elementPositionInPartition;
+
+ if (!setDescriptor.markedCount) {
+ ASSERT(!m_setsMarkedInCurrentGeneration.contains(setIndex));
+ m_setsMarkedInCurrentGeneration.append(setIndex);
+ }
+ ++setDescriptor.markedCount;
+ }
+
+ // The function passed as argument MUST not modify the partition.
+ template<typename Function>
+ void refineGeneration(const Function& function)
+ {
+ for (unsigned setIndex : m_setsMarkedInCurrentGeneration) {
+ SetDescriptor& setDescriptor = m_sets[setIndex];
+ if (setDescriptor.markedCount == setDescriptor.size) {
+ // Everything is marked, there is nothing to refine.
+ setDescriptor.markedCount = 0;
+ continue;
+ }
+
+ SetDescriptor newSet;
+ bool newSetIsMarkedSet = setDescriptor.markedCount * 2 <= setDescriptor.size;
+ if (newSetIsMarkedSet) {
+ // Less than half of the nodes have been marked.
+ newSet = { setDescriptor.start, setDescriptor.markedCount, 0 };
+ setDescriptor.start = setDescriptor.start + setDescriptor.markedCount;
+ } else
+ newSet = { setDescriptor.start + setDescriptor.markedCount, setDescriptor.size - setDescriptor.markedCount, 0 };
+ setDescriptor.size -= newSet.size;
+ setDescriptor.markedCount = 0;
+
+ unsigned newSetIndex = m_sets.size();
+ m_sets.append(newSet);
+
+ for (unsigned i = newSet.start; i < newSet.end(); ++i)
+ m_elementToSetMap[m_partitionedElements[i]] = newSetIndex;
+
+ function(newSetIndex);
+ }
+ m_setsMarkedInCurrentGeneration.clear();
+ }
+
+ // Call Function() on every node of a given subset.
+ template<typename Function>
+ void iterateSet(unsigned setIndex, const Function& function)
+ {
+ SetDescriptor& setDescriptor = m_sets[setIndex];
+ for (unsigned i = setDescriptor.start; i < setDescriptor.end(); ++i)
+ function(m_partitionedElements[i]);
+ }
+
+ // Index of the set containing the Node.
+ unsigned setIndex(unsigned elementIndex) const
+ {
+ return m_elementToSetMap[elementIndex];
+ }
+
+ // NodeIndex of the first element in the set.
+ unsigned firstElementInSet(unsigned setIndex) const
+ {
+ return m_partitionedElements[m_sets[setIndex].start];
+ }
+
+ unsigned size() const
+ {
+ return m_sets.size();
+ }
+
+private:
+ struct SetDescriptor {
+ unsigned start;
+ unsigned size;
+ unsigned markedCount;
+
+ unsigned indexAfterMarkedElements() const { return start + markedCount; }
+ unsigned end() const { return start + size; }
+ };
+
+ // List of sets.
+ Vector<SetDescriptor> m_sets;
+
+ // All the element indices such that two elements of the same set never have a element of a different set between them.
+ Vector<unsigned> m_partitionedElements;
+
+ // Map elementIndex->position in the partitionedElements.
+ Vector<unsigned> m_elementPositionInPartitionedNodes;
+
+ // Map elementIndex->SetIndex.
+ Vector<unsigned> m_elementToSetMap;
+
+ // List of sets with any marked node. Each set can appear at most once.
+ // FIXME: find a good inline size for this.
+ Vector<unsigned, 128> m_setsMarkedInCurrentGeneration;
+};
+
+class FullGraphPartition {
+public:
+ FullGraphPartition(const Vector<DFANode>& dfaGraph)
+ {
+ m_nodePartition.initialize(dfaGraph.size());
+
+ m_flattenedTransitionsStartOffsetPerNode.resize(dfaGraph.size());
+ for (unsigned& counter : m_flattenedTransitionsStartOffsetPerNode)
+ counter = 0;
+
+ m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfaGraph.size());
+ for (unsigned& counter : m_flattenedFallbackTransitionsStartOffsetPerNode)
+ counter = 0;
+
+ // Count the number of incoming transitions per node.
+ for (const DFANode& dfaNode : dfaGraph) {
+ for (const auto& transition : dfaNode.transitions)
+ ++m_flattenedTransitionsStartOffsetPerNode[transition.value];
+ if (dfaNode.hasFallbackTransition)
+ ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransition];
+ }
+
+ // Accumulate the offsets.
+ unsigned transitionAccumulator = 0;
+ for (unsigned i = 0; i < m_flattenedTransitionsStartOffsetPerNode.size(); ++i) {
+ unsigned transitionsCountForNode = m_flattenedTransitionsStartOffsetPerNode[i];
+ m_flattenedTransitionsStartOffsetPerNode[i] = transitionAccumulator;
+ transitionAccumulator += transitionsCountForNode;
+ }
+ unsigned flattenedTransitionsSize = transitionAccumulator;
+
+ unsigned fallbackTransitionAccumulator = 0;
+ for (unsigned i = 0; i < m_flattenedFallbackTransitionsStartOffsetPerNode.size(); ++i) {
+ unsigned fallbackTransitionsCountForNode = m_flattenedFallbackTransitionsStartOffsetPerNode[i];
+ m_flattenedFallbackTransitionsStartOffsetPerNode[i] = fallbackTransitionAccumulator;
+ fallbackTransitionAccumulator += fallbackTransitionsCountForNode;
+ }
+ unsigned flattenedFallbackTransitionsSize = fallbackTransitionAccumulator;
+
+ // Next, let's fill the transition table and set up the size of each group at the same time.
+ m_flattenedTransitionsSizePerNode.resize(dfaGraph.size());
+ for (unsigned& counter : m_flattenedTransitionsSizePerNode)
+ counter = 0;
+
+ m_flattenedFallbackTransitionsSizePerNode.resize(dfaGraph.size());
+ for (unsigned& counter : m_flattenedFallbackTransitionsSizePerNode)
+ counter = 0;
+
+ m_flattenedTransitions.resize(flattenedTransitionsSize);
+
+ m_flattenedFallbackTransitions.resize(flattenedFallbackTransitionsSize);
+
+ for (unsigned i = 0; i < dfaGraph.size(); ++i) {
+ const DFANode& dfaNode = dfaGraph[i];
+ for (const auto& transition : dfaNode.transitions) {
+ unsigned targetNodeIndex = transition.value;
+
+ unsigned start = m_flattenedTransitionsStartOffsetPerNode[targetNodeIndex];
+ unsigned offset = m_flattenedTransitionsSizePerNode[targetNodeIndex];
+
+ m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.key });
+
+ ++m_flattenedTransitionsSizePerNode[targetNodeIndex];
+ }
+ if (dfaNode.hasFallbackTransition) {
+ unsigned targetNodeIndex = dfaNode.fallbackTransition;
+
+ unsigned start = m_flattenedFallbackTransitionsStartOffsetPerNode[targetNodeIndex];
+ unsigned offset = m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];
+
+ m_flattenedFallbackTransitions[start + offset] = i;
+ ++m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];
+ }
+ }
+
+ // Create the initial partition of transition. Each character differentiating a transiton
+ // from an other gets its own set in the partition.
+ m_transitionPartition.initialize(m_flattenedTransitions.size());
+ for (uint16_t i = 0; i < 128; ++i) {
+ for (unsigned transitionIndex = 0; transitionIndex < m_flattenedTransitions.size(); ++transitionIndex) {
+ const Transition& transition = m_flattenedTransitions[transitionIndex];
+ if (transition.character == i)
+ m_transitionPartition.markElementInCurrentGeneration(transitionIndex);
+ }
+ m_transitionPartition.refineGeneration([](unsigned) { });
+ }
+
+ // Fallback partitions are considered as a special type of differentiator, we don't split them initially.
+ m_fallbackTransitionPartition.initialize(m_flattenedFallbackTransitions.size());
+ }
+
+ void markNode(unsigned nodeIndex)
+ {
+ m_nodePartition.markElementInCurrentGeneration(nodeIndex);
+ }
+
+ void refinePartitions()
+ {
+ m_nodePartition.refineGeneration([&](unsigned smallestSetIndex) {
+ m_nodePartition.iterateSet(smallestSetIndex, [&](unsigned nodeIndex) {
+ unsigned incomingTransitionsStartForNode = m_flattenedTransitionsStartOffsetPerNode[nodeIndex];
+ unsigned incomingTransitionsSizeForNode = m_flattenedTransitionsSizePerNode[nodeIndex];
+
+ for (unsigned i = 0; i < incomingTransitionsSizeForNode; ++i)
+ m_transitionPartition.markElementInCurrentGeneration(incomingTransitionsStartForNode + i);
+
+ unsigned incomingFallbackTransitionsStartForNode = m_flattenedFallbackTransitionsStartOffsetPerNode[nodeIndex];
+ unsigned incomingFallbackTransitionsSizeForNode = m_flattenedFallbackTransitionsSizePerNode[nodeIndex];
+
+ for (unsigned i = 0; i < incomingFallbackTransitionsSizeForNode; ++i)
+ m_fallbackTransitionPartition.markElementInCurrentGeneration(incomingFallbackTransitionsStartForNode + i);
+ });
+
+ // We only need to split the transitions, we handle the new sets through the main loop.
+ m_transitionPartition.refineGeneration([](unsigned) { });
+ m_fallbackTransitionPartition.refineGeneration([](unsigned) { });
+ });
+ }
+
+ void splitByUniqueTransitions()
+ {
+ for (; m_nextTransitionSetToProcess < m_transitionPartition.size(); ++m_nextTransitionSetToProcess) {
+ // We use the known splitters to refine the set.
+ m_transitionPartition.iterateSet(m_nextTransitionSetToProcess, [&](unsigned transitionIndex) {
+ unsigned sourceNodeIndex = m_flattenedTransitions[transitionIndex].source;
+ m_nodePartition.markElementInCurrentGeneration(sourceNodeIndex);
+ });
+
+ refinePartitions();
+ }
+ }
+
+ void splitByFallbackTransitions()
+ {
+ ASSERT_WITH_MESSAGE(m_nextTransitionSetToProcess || !m_transitionPartition.size(), "We can only distinguish nodes by fallback transition *after* all other transitions are covered. Doing otherwise would be incorrect since the unique transitions from 2 nodes could cover all possible transitions.");
+
+ for (unsigned fallbackTransitionSetIndex = 0; fallbackTransitionSetIndex < m_fallbackTransitionPartition.size(); ++fallbackTransitionSetIndex) {
+
+ m_fallbackTransitionPartition.iterateSet(fallbackTransitionSetIndex, [&](unsigned transitionIndex) {
+ unsigned sourceNodeIndex = m_flattenedFallbackTransitions[transitionIndex];
+ m_nodePartition.markElementInCurrentGeneration(sourceNodeIndex);
+ });
+ refinePartitions();
+
+ // Any new split need to spread to all the unique transition that can reach the two new sets.
+ splitByUniqueTransitions();
+ }
+ }
+
+ unsigned nodeReplacement(unsigned nodeIndex)
+ {
+ unsigned setIndex = m_nodePartition.setIndex(nodeIndex);
+ return m_nodePartition.firstElementInSet(setIndex);
+ }
+
+private:
+ struct Transition {
+ unsigned source;
+ unsigned target;
+ uint16_t character;
+ };
+
+ Vector<unsigned> m_flattenedTransitionsStartOffsetPerNode;
+ Vector<unsigned> m_flattenedTransitionsSizePerNode;
+ Vector<unsigned> m_flattenedFallbackTransitionsStartOffsetPerNode;
+ Vector<unsigned> m_flattenedFallbackTransitionsSizePerNode;
+
+ Vector<Transition> m_flattenedTransitions;
+ Vector<unsigned> m_flattenedFallbackTransitions;
+
+ Partition m_nodePartition;
+ Partition m_transitionPartition;
+ Partition m_fallbackTransitionPartition;
+
+ unsigned m_nextTransitionSetToProcess { 0 };
+};
+
+struct ActionKey {
+ enum DeletedValueTag { DeletedValue };
+ explicit ActionKey(DeletedValueTag) { state = Deleted; }
+
+ enum EmptyValueTag { EmptyValue };
+ explicit ActionKey(EmptyValueTag) { state = Empty; }
+
+ explicit ActionKey(const Vector<uint64_t>& actions)
+ : actions(&actions)
+ , state(Valid)
+ {
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(actions.data()), actions.size() * sizeof(uint64_t) / sizeof(UChar));
+ hash = hasher.hash();
+ }
+
+ bool isEmptyValue() const { return state == Empty; }
+ bool isDeletedValue() const { return state == Deleted; }
+
+ const Vector<uint64_t>* actions;
+ unsigned hash;
+ enum {
+ Valid,
+ Empty,
+ Deleted
+ } state;
+};
+
+struct ActionKeyHash {
+ static unsigned hash(const ActionKey& actionKey)
+ {
+ return actionKey.hash;
+ }
+
+ static bool equal(const ActionKey& a, const ActionKey& b)
+ {
+ return a.state == b.state && *a.actions == *b.actions;
+ }
+ static const bool safeToCompareToEmptyOrDeleted = false;
+};
+
+struct ActionKeyHashTraits : public WTF::CustomHashTraits<ActionKey> {
+ static const bool emptyValueIsZero = true;
+};
+
+} // anonymous namespace.
+
+unsigned DFAMinimizer::minimize(Vector<DFANode>& dfaGraph, unsigned root)
+{
+ simplifyTransitions(dfaGraph);
+
+ FullGraphPartition fullGraphPartition(dfaGraph);
+
+ // Unlike traditional minimization final states can be differentiated by their action.
+ // Instead of creating a single set for the final state, we partition by actions from
+ // the start.
+ HashMap<ActionKey, Vector<unsigned>, ActionKeyHash, ActionKeyHashTraits> finalStates;
+ for (unsigned i = 0; i < dfaGraph.size(); ++i) {
+ Vector<uint64_t>& actions = dfaGraph[i].actions;
+ if (actions.size()) {
+ std::sort(actions.begin(), actions.end());
+ auto addResult = finalStates.add(ActionKey(actions), Vector<unsigned>());
+ addResult.iterator->value.append(i);
+ }
+ }
+
+ for (const auto& slot : finalStates) {
+ for (unsigned finalStateIndex : slot.value)
+ fullGraphPartition.markNode(finalStateIndex);
+ fullGraphPartition.refinePartitions();
+ }
+
+ // Use every splitter to refine the node partitions.
+ fullGraphPartition.splitByUniqueTransitions();
+
+ // At this stage, we know that no pair of state can be distinguished by the individual transitions. They can still
+ // be distinguished by their fallback transitions.
+ //
+ // For example, two states [1, 2] can both have a transition on 'x' to a state [3], but each have fallback transition
+ // to different states [4] and [5].
+ //
+ // Here, we distinguish such cases and at each stage refine the new discovered sets by their individual transitions.
+ fullGraphPartition.splitByFallbackTransitions();
+
+ Vector<unsigned> relocationVector;
+ relocationVector.reserveInitialCapacity(dfaGraph.size());
+ for (unsigned i = 0; i < dfaGraph.size(); ++i)
+ relocationVector.append(i);
+
+ // Kill the useless nodes and keep track of the new node transitions should point to.
+ for (unsigned i = 0; i < dfaGraph.size(); ++i) {
+ unsigned replacement = fullGraphPartition.nodeReplacement(i);
+ if (i != replacement) {
+ relocationVector[i] = replacement;
+
+ DFANode& node = dfaGraph[i];
+ node.actions.clear();
+ node.transitions.clear();
+ node.hasFallbackTransition = false;
+ node.isKilled = true;
+ }
+ }
+
+ for (DFANode& node : dfaGraph) {
+ for (auto& transition : node.transitions)
+ transition.value = relocationVector[transition.value];
+ if (node.hasFallbackTransition)
+ node.fallbackTransition = relocationVector[node.fallbackTransition];
+ }
+
+ // After minimizing, there is no guarantee individual transition are still poiting to different states.
+ // The state pointed by one individual transition and the fallback states may have been merged.
+ simplifyTransitions(dfaGraph);
+
+ return relocationVector[root];
+}
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAMinimizerh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/DFAMinimizer.h (0 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.h 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -0,0 +1,47 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFAMinimizer_h
+#define DFAMinimizer_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "DFANode.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+namespace ContentExtensions {
+
+class DFAMinimizer {
+public:
+ WEBCORE_EXPORT static unsigned minimize(Vector<DFANode>& dfaGraph, unsigned rootNode);
+};
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // DFAMinimizer_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -44,7 +44,8 @@
</span><span class="cx"> class DFANode {
</span><span class="cx"> public:
</span><span class="cx"> DFANodeTransitions transitions;
</span><del>- bool hasFallbackTransition = false;
</del><ins>+ bool hasFallbackTransition { false };
+ bool isKilled { false };
</ins><span class="cx"> unsigned fallbackTransition;
</span><span class="cx"> Vector<uint64_t> actions;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -338,49 +338,6 @@
</span><span class="cx"> return uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void simplifyTransitions(Vector<DFANode>& dfaGraph)
-{
- for (DFANode& dfaNode : dfaGraph) {
- if (!dfaNode.hasFallbackTransition
- && ((dfaNode.transitions.size() == 126 && !dfaNode.transitions.contains(0))
- || (dfaNode.transitions.size() == 127 && dfaNode.transitions.contains(0)))) {
- unsigned bestTarget = std::numeric_limits<unsigned>::max();
- unsigned bestTargetScore = 0;
- HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;
- for (const auto transition : dfaNode.transitions) {
- if (!transition.key)
- continue;
-
- unsigned transitionTarget = transition.value;
- auto addResult = targetHistogram.add(transitionTarget, 1);
- if (!addResult.isNewEntry)
- addResult.iterator->value++;
-
- if (addResult.iterator->value > bestTargetScore) {
- bestTargetScore = addResult.iterator->value;
- bestTarget = transitionTarget;
- }
- }
- ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");
-
- dfaNode.hasFallbackTransition = true;
- dfaNode.fallbackTransition = bestTarget;
- }
-
- if (dfaNode.hasFallbackTransition) {
- Vector<uint16_t, 128> keys;
- DFANodeTransitions& transitions = dfaNode.transitions;
- copyKeysToVector(transitions, keys);
-
- for (uint16_t key : keys) {
- auto transitionIterator = transitions.find(key);
- if (transitionIterator->value == dfaNode.fallbackTransition)
- transitions.remove(transitionIterator);
- }
- }
- }
-}
-
</del><span class="cx"> DFA NFAToDFA::convert(NFA& nfa)
</span><span class="cx"> {
</span><span class="cx"> Vector<NFANode>& nfaGraph = nfa.m_nodes;
</span><span class="lines">@@ -430,7 +387,6 @@
</span><span class="cx"> }
</span><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><span class="cx">
</span><del>- simplifyTransitions(dfaGraph);
</del><span class="cx"> return DFA(WTF::move(dfaGraph), 0);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.h (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -39,7 +39,7 @@
</span><span class="cx"> // NFAToDFA provides a way to build a DFA corresponding to a NFA.
</span><span class="cx"> class NFAToDFA {
</span><span class="cx"> public:
</span><del>- static DFA convert(NFA&);
</del><ins>+ WEBCORE_EXPORT static DFA convert(NFA&);
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Tools/ChangeLog 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -1,3 +1,13 @@
</span><ins>+2015-04-14 Benjamin Poulain <benjamin@webkit.org>
+
+ Add a conservative DFA minimizer for the content extension matcher
+ https://bugs.webkit.org/show_bug.cgi?id=143501
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+
</ins><span class="cx"> 2015-04-14 Daniel Bates <dabates@apple.com>
</span><span class="cx">
</span><span class="cx"> Skip failing test Tests/WebKit2Cocoa/FixedLayoutSize.mm on iOS
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -24,6 +24,7 @@
</span><span class="cx"> 26F52EAF18288C230023D412 /* geolocationGetCurrentPositionWithHighAccuracy.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26F52EAE18288C040023D412 /* geolocationGetCurrentPositionWithHighAccuracy.html */; };
</span><span class="cx"> 26F52EB218288F240023D412 /* geolocationWatchPosition.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26F52EB018288F0F0023D412 /* geolocationWatchPosition.html */; };
</span><span class="cx"> 26F52EB318288F240023D412 /* geolocationWatchPositionWithHighAccuracy.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26F52EB118288F0F0023D412 /* geolocationWatchPositionWithHighAccuracy.html */; };
</span><ins>+ 26F6E1F01ADC749B00DE696B /* DFAMinimizer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F6E1EF1ADC749B00DE696B /* DFAMinimizer.cpp */; };
</ins><span class="cx"> 290A9BB91735F63800D71BBC /* OpenNewWindow.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 290A9BB81735F42300D71BBC /* OpenNewWindow.html */; };
</span><span class="cx"> 290F4275172A221C00939FF0 /* custom-protocol-sync-xhr.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 290F4274172A1FDE00939FF0 /* custom-protocol-sync-xhr.html */; };
</span><span class="cx"> 297234B7173AFAC700983601 /* CustomProtocolsInvalidScheme_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 297234B5173AFAC700983601 /* CustomProtocolsInvalidScheme_Bundle.cpp */; };
</span><span class="lines">@@ -441,6 +442,7 @@
</span><span class="cx"> 26F52EAE18288C040023D412 /* geolocationGetCurrentPositionWithHighAccuracy.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = geolocationGetCurrentPositionWithHighAccuracy.html; sourceTree = "<group>"; };
</span><span class="cx"> 26F52EB018288F0F0023D412 /* geolocationWatchPosition.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = geolocationWatchPosition.html; sourceTree = "<group>"; };
</span><span class="cx"> 26F52EB118288F0F0023D412 /* geolocationWatchPositionWithHighAccuracy.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = geolocationWatchPositionWithHighAccuracy.html; sourceTree = "<group>"; };
</span><ins>+ 26F6E1EF1ADC749B00DE696B /* DFAMinimizer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFAMinimizer.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 290A9BB51735DE8A00D71BBC /* CloseNewWindowInNavigationPolicyDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = CloseNewWindowInNavigationPolicyDelegate.mm; sourceTree = "<group>"; };
</span><span class="cx"> 290A9BB81735F42300D71BBC /* OpenNewWindow.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = OpenNewWindow.html; sourceTree = "<group>"; };
</span><span class="cx"> 290F4274172A1FDE00939FF0 /* custom-protocol-sync-xhr.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "custom-protocol-sync-xhr.html"; sourceTree = "<group>"; };
</span><span class="lines">@@ -845,6 +847,7 @@
</span><span class="cx"> 93A720E518F1A0E800A848E1 /* CalculationValue.cpp */,
</span><span class="cx"> 7CB184C41AA3F2100066EDFD /* ContentExtensions.cpp */,
</span><span class="cx"> CD5451E919E41F9D0016936F /* CSSParser.cpp */,
</span><ins>+ 26F6E1EF1ADC749B00DE696B /* DFAMinimizer.cpp */,
</ins><span class="cx"> 14464012167A8305000BD218 /* LayoutUnit.cpp */,
</span><span class="cx"> CDC2C7141797089D00E627FB /* TimeRanges.cpp */,
</span><span class="cx"> 440A1D3814A0103A008A66F2 /* URL.cpp */,
</span><span class="lines">@@ -1581,6 +1584,7 @@
</span><span class="cx"> 7AA6A1521AAC0B31002B2ED3 /* WorkQueue.cpp in Sources */,
</span><span class="cx"> 2E7765CF16C4D81100BA2BB1 /* mainMac.mm in Sources */,
</span><span class="cx"> 7A5623111AD5AF3E0096B920 /* MenuTypesForMouseEvents.cpp in Sources */,
</span><ins>+ 26F6E1F01ADC749B00DE696B /* DFAMinimizer.cpp in Sources */,
</ins><span class="cx"> 7A99D9941AD4A29D00373141 /* MenuTypesForMouseEvents.mm in Sources */,
</span><span class="cx"> );
</span><span class="cx"> runOnlyForDeploymentPostprocessing = 0;
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (182807 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-04-14 20:54:36 UTC (rev 182807)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -730,4 +730,190 @@
</span><span class="cx"> testPatternStatus("((foo)?((.)*)(bar)*)", ContentExtensions::URLFilterParser::ParseStatus::MatchesEverything);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, MinimizingWithMoreFinalStatesThanNonFinalStates)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^h[a-z://]+\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://foo.com/\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://bar.com/\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://foo.com/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://bar.com/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("attp://foo.com/"), { });
+ testRequest(backend, mainDocumentRequest("attp://bar.com/"), { });
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bttp://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bttps://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/b"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://webkit.org/b"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("cttp://webkit.org/B"), { });
+ testRequest(backend, mainDocumentRequest("cttps://webkit.org/B"), { });
+}
+
+TEST_F(ContentExtensionTest, StatesWithDifferentActionsAreNotUnified1)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://www.webkit.org/\"}},"
+ "{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\"^https://www.webkit.org/\"}},"
+ "{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\"^attps://www.webkit.org/\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://www.webkit.org/"), { ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("attps://www.webkit.org/"), { ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("http://www.webkit.org/a"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://www.webkit.org/B"), { ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("attps://www.webkit.org/c"), { ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("http://www.whatwg.org/"), { });
+ testRequest(backend, mainDocumentRequest("https://www.whatwg.org/"), { });
+ testRequest(backend, mainDocumentRequest("attps://www.whatwg.org/"), { });
+}
+
+TEST_F(ContentExtensionTest, StatesWithDifferentActionsAreNotUnified2)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://www.webkit.org/\"}},"
+ "{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\"^https://www.webkit.org/\"}},"
+ "{\"action\":{\"type\":\"css-display-none\", \"selector\":\"#foo\"},\"trigger\":{\"url-filter\":\"^https://www.webkit.org/\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("https://www.whatwg.org/"), { });
+ testRequest(backend, mainDocumentRequest("attps://www.whatwg.org/"), { });
+}
+
+// The order in which transitions from the root will be processed is unpredictable.
+// To exercises the various options, this test exists in various version exchanging the transition to the final state.
+TEST_F(ContentExtensionTest, FallbackTransitionsWithDifferentiatorDoNotMerge1)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.a\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^b.a\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bac\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bbc\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^BCC\"}}]");
+
+ testRequest(backend, mainDocumentRequest("aza://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bac://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bbc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bcc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("aac://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("abc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("acc://www.webkit.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+}
+TEST_F(ContentExtensionTest, FallbackTransitionsWithDifferentiatorDoNotMerge2)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bac\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bbc\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^BCC\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.a\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^b.a\"}}]");
+
+ testRequest(backend, mainDocumentRequest("aza://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bac://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bbc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bcc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("aac://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("abc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("acc://www.webkit.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { });
+}
+TEST_F(ContentExtensionTest, FallbackTransitionsWithDifferentiatorDoNotMerge3)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.c\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^b.c\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^baa\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bba\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^BCA\"}}]");
+
+ testRequest(backend, mainDocumentRequest("azc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("baa://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bba://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bca://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("aaa://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("aba://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("aca://www.webkit.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+}
+TEST_F(ContentExtensionTest, FallbackTransitionsWithDifferentiatorDoNotMerge4)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^baa\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^bba\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^BCA\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.c\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^b.c\"}}]");
+
+ testRequest(backend, mainDocumentRequest("azc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bzc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("baa://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bba://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bca://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("aaa://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("aba://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("aca://www.webkit.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bza://www.webkit.org/"), { });
+}
+
+TEST_F(ContentExtensionTest, FallbackTransitionsToOtherNodeInSameGroupDoesNotDifferentiateGroup)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^aac\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.c\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^b.c\"}}]");
+
+ testRequest(backend, mainDocumentRequest("aac://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("abc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("bac://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("abc://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("aaa://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("aca://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("baa://www.webkit.org/"), { });
+}
+
+TEST_F(ContentExtensionTest, SimpleFallBackTransitionDifferentiator1)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.bc.de\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^a.bd.ef\"}}]");
+
+ testRequest(backend, mainDocumentRequest("abbccde://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("aabcdde://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("aabddef://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("aabddef://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("abcde://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("abdef://www.webkit.org/"), { });
+}
+
+TEST_F(ContentExtensionTest, SimpleFallBackTransitionDifferentiator2)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^cb.\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^db.b\"}}]");
+
+ testRequest(backend, mainDocumentRequest("cba://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("cbb://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("dbab://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("dbxb://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("cca://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("dddd://www.webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("bbbb://www.webkit.org/"), { });
+}
+
</ins><span class="cx"> } // namespace TestWebKitAPI
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (0 => 182808)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-04-14 21:08:02 UTC (rev 182808)
</span><span class="lines">@@ -0,0 +1,131 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include <WebCore/CombinedURLFilters.h>
+#include <WebCore/NFA.h>
+#include <WebCore/NFAToDFA.h>
+#include <WebCore/URLFilterParser.h>
+#include <wtf/MainThread.h>
+
+using namespace WebCore;
+
+namespace TestWebKitAPI {
+
+class DFAMinimizerTest : public testing::Test {
+public:
+ virtual void SetUp()
+ {
+ WTF::initializeMainThread();
+ }
+};
+
+unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
+{
+ unsigned counter = 0;
+ for (unsigned i = 0; i < dfa.size(); ++i) {
+ if (!dfa.nodeAt(i).isKilled)
+ ++counter;
+ }
+ return counter;
+}
+
+ContentExtensions::DFA buildDFAFromPatterns(Vector<const char*> patterns)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+
+ for (const char* pattern : patterns)
+ parser.addPattern(pattern, false, 0);
+ Vector<ContentExtensions::NFA> nfas = combinedURLFilters.createNFAs();
+ return ContentExtensions::NFAToDFA::convert(nfas[0]);
+}
+
+TEST_F(DFAMinimizerTest, BasicSearch)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*foo", ".*bar", ".*bang"});
+ EXPECT_EQ(static_cast<size_t>(10), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge1)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.a", "^b.a", "^bac", "^bbc", "^BCC"});
+ EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge2)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^bbc", "^BCC", "^a.a", "^b.a"});
+ EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge3)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.c", "^b.c", "^baa", "^bba", "^BCA"});
+ EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge4)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^baa", "^bba", "^BCA", "^a.c", "^b.c"});
+ EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, FallbackTransitionsToOtherNodeInSameGroupDoesNotDifferentiateGroup)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^aac", "^a.c", "^b.c"});
+ EXPECT_EQ(static_cast<size_t>(9), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(5), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator1)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.bc.de", "^a.bd.ef"});
+ EXPECT_EQ(static_cast<size_t>(12), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator2)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^cb.", "^db.b"});
+ EXPECT_EQ(static_cast<size_t>(8), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
+}
+
+} // namespace TestWebKitAPI
</ins></span></pre>
</div>
</div>
</body>
</html>