<!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>[186910] 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/186910">186910</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-07-16 14:51:08 -0700 (Thu, 16 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[Content extensions] Combine suffixes when generating NFAs
https://bugs.webkit.org/show_bug.cgi?id=146961
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-07-16
Reviewed by Alex Christensen.
Source/WebCore:
In this patch, I add a mechanism very similar to the prefix tree
but for the suffix (called a reverse suffix tree here).
The idea is here is to reuse the existing NFA nodes when generating
a chain of suffix Term that were already generated previously.
When generating a disjunction ending with the same suffix, we now
have the same trailing NFA nodes for both sides of the disjunction.
Mixing the prefix and suffix generation can be tricky, we do not want
transitions from a pattern to creep into the suffix of an other.
To avoid any conflict, the rules here are very simple:
-Only use the reverse suffix tree for terms without actions
up to a leaf term with actions.
This rule ensure that no action will accidentally make its way
to an other rule by resuing a vertex of the reverse suffix tree.
-Only use the reverse suffix tree for chains of terms in which
each term only has zero or one following term.
With this condition, when taking any vertex of the reverse suffix
tree, there is only one edge that move out of that vertex when reading
from left to right.
For any vertex, there is only one possible string generated
left-to-right, a single suffix.
This is overly restrictive but it is fast, easier to verify, and it works
well in practice.
For all the more complicated cases, we can count on the Minimizer to
find a better solution.
With all the simple suffixes merged, our NFAs are smaller, which
let us combine more patterns.
The DFAs are also smaller and faster to produce since their size
is relative to the NFA sizes.
Overall, I get the following gains:
-Chris's test case:
compile time -40%.
bytecode size -14%.
-Armand's test case:
compile time -53%.
bytecode size -13%.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::ActiveSubtree::ActiveSubtree):
(WebCore::ContentExtensions::generateInfixUnsuitableForReverseSuffixTree):
(WebCore::ContentExtensions::generateSuffixWithReverseSuffixTree):
(WebCore::ContentExtensions::clearReverseSuffixTree):
(WebCore::ContentExtensions::generateNFAForSubtree):
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::debugPrintDot):
Forgot to close a tag, dot was not happy.
* contentextensions/HashableActionList.h: Added.
(WebCore::ContentExtensions::HashableActionList::HashableActionList):
(WebCore::ContentExtensions::HashableActionList::isEmptyValue):
(WebCore::ContentExtensions::HashableActionList::isDeletedValue):
(WebCore::ContentExtensions::HashableActionList::operator==):
(WebCore::ContentExtensions::HashableActionList::operator!=):
(WebCore::ContentExtensions::HashableActionListHash::hash):
(WebCore::ContentExtensions::HashableActionListHash::equal):
We need a way to group reverse suffix tree by their terminal actions.
This new hash structure lets us find unique vertex for a list of actions
in any order.
* contentextensions/ImmutableNFANodeBuilder.h:
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::isValid):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::nodeId):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::addTransition):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::addEpsilonTransition):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::ImmutableNFANodeBuilder): Deleted.
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::~ImmutableNFANodeBuilder): Deleted.
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::operator=): Deleted.
* contentextensions/Term.h:
(WebCore::ContentExtensions::Term::generateGraph):
(WebCore::ContentExtensions::Term::generateSubgraphForAtom):
Node building changes a bit.
Previously, it was assumed nodes are always built from left to right.
Getting the node on the right was done by providing the left node and the term
doing the transition.
Now we have both left to right and right to left generation.
The right-to-left has a specific property: no edge can be added after
it's initial term (rule 2 of our reverse suffix tree). This simplifies
things a bit since we can finalize all the nodes in the suffix tree.
All we need is to keep their ID to be able to link new nodes
to the reverse suffix tree.
Source/WTF:
* wtf/Vector.h:
(WTF::minCapacity>::Vector):
(WTF::=):
Copying a vector with a different inline capacity was broken due to
the addition of MinimumCapacity.
This feature was needed by this patch so I fixed WTF.
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
(TestWebKitAPI::compareContents):
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfVectorh">trunk/Source/WTF/wtf/Vector.h</a></li>
<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="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsImmutableNFANodeBuilderh">trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsTermh">trunk/Source/WebCore/contentextensions/Term.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFVectorcpp">trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWebCorecontentextensionsHashableActionListh">trunk/Source/WebCore/contentextensions/HashableActionList.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WTF/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-07-16 Benjamin Poulain <bpoulain@apple.com>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ * wtf/Vector.h:
+ (WTF::minCapacity>::Vector):
+ (WTF::=):
+ Copying a vector with a different inline capacity was broken due to
+ the addition of MinimumCapacity.
+
+ This feature was needed by this patch so I fixed WTF.
+
</ins><span class="cx"> 2015-07-15 Anders Carlsson <andersca@apple.com>
</span><span class="cx">
</span><span class="cx"> Make JavaScriptCore SPI headers used by WebCore SPI headers self-contained
</span></span></pre></div>
<a id="trunkSourceWTFwtfVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Vector.h (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Vector.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WTF/wtf/Vector.h 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -638,12 +638,12 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector(const Vector&);
</span><del>- template<size_t otherCapacity, typename otherOverflowBehaviour>
- explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
</del><ins>+ template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+ explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
</ins><span class="cx">
</span><span class="cx"> Vector& operator=(const Vector&);
</span><del>- template<size_t otherCapacity, typename otherOverflowBehaviour>
- Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
</del><ins>+ template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+ Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
</ins><span class="cx">
</span><span class="cx"> Vector(Vector&&);
</span><span class="cx"> Vector& operator=(Vector&&);
</span><span class="lines">@@ -819,8 +819,8 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</span><del>-template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</del><ins>+template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
</ins><span class="cx"> : Base(other.capacity(), other.size())
</span><span class="cx"> {
</span><span class="cx"> asanSetInitialBufferSizeTo(other.size());
</span><span class="lines">@@ -855,8 +855,8 @@
</span><span class="cx"> inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
</span><span class="cx">
</span><span class="cx"> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</span><del>-template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</del><ins>+template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
</ins><span class="cx"> {
</span><span class="cx"> // If the inline capacities match, we should call the more specific
</span><span class="cx"> // template. If the inline capacities don't match, the two objects
</span></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -1,3 +1,104 @@
</span><ins>+2015-07-16 Benjamin Poulain <bpoulain@apple.com>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ In this patch, I add a mechanism very similar to the prefix tree
+ but for the suffix (called a reverse suffix tree here).
+
+ The idea is here is to reuse the existing NFA nodes when generating
+ a chain of suffix Term that were already generated previously.
+ When generating a disjunction ending with the same suffix, we now
+ have the same trailing NFA nodes for both sides of the disjunction.
+
+ Mixing the prefix and suffix generation can be tricky, we do not want
+ transitions from a pattern to creep into the suffix of an other.
+
+ To avoid any conflict, the rules here are very simple:
+ -Only use the reverse suffix tree for terms without actions
+ up to a leaf term with actions.
+
+ This rule ensure that no action will accidentally make its way
+ to an other rule by resuing a vertex of the reverse suffix tree.
+
+ -Only use the reverse suffix tree for chains of terms in which
+ each term only has zero or one following term.
+
+ With this condition, when taking any vertex of the reverse suffix
+ tree, there is only one edge that move out of that vertex when reading
+ from left to right.
+ For any vertex, there is only one possible string generated
+ left-to-right, a single suffix.
+
+ This is overly restrictive but it is fast, easier to verify, and it works
+ well in practice.
+ For all the more complicated cases, we can count on the Minimizer to
+ find a better solution.
+
+
+ With all the simple suffixes merged, our NFAs are smaller, which
+ let us combine more patterns.
+ The DFAs are also smaller and faster to produce since their size
+ is relative to the NFA sizes.
+
+ Overall, I get the following gains:
+ -Chris's test case:
+ compile time -40%.
+ bytecode size -14%.
+ -Armand's test case:
+ compile time -53%.
+ bytecode size -13%.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::ActiveSubtree::ActiveSubtree):
+ (WebCore::ContentExtensions::generateInfixUnsuitableForReverseSuffixTree):
+ (WebCore::ContentExtensions::generateSuffixWithReverseSuffixTree):
+ (WebCore::ContentExtensions::clearReverseSuffixTree):
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::debugPrintDot):
+ Forgot to close a tag, dot was not happy.
+
+ * contentextensions/HashableActionList.h: Added.
+ (WebCore::ContentExtensions::HashableActionList::HashableActionList):
+ (WebCore::ContentExtensions::HashableActionList::isEmptyValue):
+ (WebCore::ContentExtensions::HashableActionList::isDeletedValue):
+ (WebCore::ContentExtensions::HashableActionList::operator==):
+ (WebCore::ContentExtensions::HashableActionList::operator!=):
+ (WebCore::ContentExtensions::HashableActionListHash::hash):
+ (WebCore::ContentExtensions::HashableActionListHash::equal):
+ We need a way to group reverse suffix tree by their terminal actions.
+ This new hash structure lets us find unique vertex for a list of actions
+ in any order.
+
+ * contentextensions/ImmutableNFANodeBuilder.h:
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::isValid):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::nodeId):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addEpsilonTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::ImmutableNFANodeBuilder): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::~ImmutableNFANodeBuilder): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::operator=): Deleted.
+ * contentextensions/Term.h:
+ (WebCore::ContentExtensions::Term::generateGraph):
+ (WebCore::ContentExtensions::Term::generateSubgraphForAtom):
+ Node building changes a bit.
+
+ Previously, it was assumed nodes are always built from left to right.
+ Getting the node on the right was done by providing the left node and the term
+ doing the transition.
+
+ Now we have both left to right and right to left generation.
+
+ The right-to-left has a specific property: no edge can be added after
+ it's initial term (rule 2 of our reverse suffix tree). This simplifies
+ things a bit since we can finalize all the nodes in the suffix tree.
+ All we need is to keep their ID to be able to link new nodes
+ to the reverse suffix tree.
+
</ins><span class="cx"> 2015-07-16 Brady Eidson <beidson@apple.com>
</span><span class="cx">
</span><span class="cx"> Rolling out part of r186895 until rdar://problem/21861167 is resolved.
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -1040,6 +1040,7 @@
</span><span class="cx"> 26E944D91AC4B2DD007B85B5 /* CombinedURLFilters.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26E944DD1AC4B4EA007B85B5 /* Term.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944DC1AC4B4EA007B85B5 /* Term.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26E98A10130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E98A0F130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h */; };
</span><ins>+ 26EA89A71B4F2B75008C5FD2 /* HashableActionList.h in Headers */ = {isa = PBXBuildFile; fileRef = 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */; };
</ins><span class="cx"> 26F0C8971A2E724B002794F8 /* ContentExtensionParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C8951A2E724B002794F8 /* ContentExtensionParser.cpp */; };
</span><span class="cx"> 26F0C8981A2E724B002794F8 /* ContentExtensionParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F0C8961A2E724B002794F8 /* ContentExtensionParser.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26F0C89B1A2EC110002794F8 /* ContentExtensionRule.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C8991A2EC110002794F8 /* ContentExtensionRule.cpp */; };
</span><span class="lines">@@ -8200,6 +8201,7 @@
</span><span class="cx"> 26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CombinedURLFilters.h; sourceTree = "<group>"; };
</span><span class="cx"> 26E944DC1AC4B4EA007B85B5 /* Term.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Term.h; sourceTree = "<group>"; };
</span><span class="cx"> 26E98A0F130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TextCodecASCIIFastPath.h; sourceTree = "<group>"; };
</span><ins>+ 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashableActionList.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26F0C8951A2E724B002794F8 /* ContentExtensionParser.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionParser.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26F0C8961A2E724B002794F8 /* ContentExtensionParser.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContentExtensionParser.h; sourceTree = "<group>"; };
</span><span class="cx"> 26F0C8991A2EC110002794F8 /* ContentExtensionRule.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionRule.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15736,6 +15738,7 @@
</span><span class="cx"> 26A517FC1AB92238006335DF /* DFAMinimizer.h */,
</span><span class="cx"> 26D4E8451B42539D00E033A2 /* DFANode.cpp */,
</span><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><ins>+ 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */,
</ins><span class="cx"> 26F756B21B3B66F70005DD79 /* ImmutableNFA.h */,
</span><span class="cx"> 26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */,
</span><span class="cx"> 26F756AE1B3B65AC0005DD79 /* MutableRange.h */,
</span><span class="lines">@@ -27288,6 +27291,7 @@
</span><span class="cx"> 0709D78F1AE55554004E42F8 /* WebMediaSessionManager.h in Headers */,
</span><span class="cx"> 0709D7951AE55A29004E42F8 /* WebMediaSessionManagerClient.h in Headers */,
</span><span class="cx"> 0709D7931AE5557E004E42F8 /* WebMediaSessionManagerMac.h in Headers */,
</span><ins>+ 26EA89A71B4F2B75008C5FD2 /* HashableActionList.h in Headers */,
</ins><span class="cx"> E1A3162D134BC32D007C9A4F /* WebNSAttributedStringExtras.h in Headers */,
</span><span class="cx"> 99CC0B6B18BEA1FF006CEBCC /* WebReplayInputs.h in Headers */,
</span><span class="cx"> A502C5DF13049B3500FC7D53 /* WebSafeGCActivityCallbackIOS.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-16 21:51:08 UTC (rev 186910)
</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 "HashableActionList.h"
</ins><span class="cx"> #include "Term.h"
</span><span class="cx"> #include <wtf/DataLog.h>
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="lines">@@ -48,6 +49,19 @@
</span><span class="cx"> PrefixTreeEdges edges;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+struct ReverseSuffixTreeVertex;
+struct ReverseSuffixTreeEdge {
+ const Term* term;
+ std::unique_ptr<ReverseSuffixTreeVertex> child;
+};
+typedef Vector<ReverseSuffixTreeEdge, 0, WTF::CrashOnOverflow, 1> ReverseSuffixTreeEdges;
+
+struct ReverseSuffixTreeVertex {
+ ReverseSuffixTreeEdges edges;
+ uint32_t nodeId;
+};
+typedef HashMap<HashableActionList, ReverseSuffixTreeVertex, HashableActionListHash, HashableActionListHashTraits> ReverseSuffixTreeRoots;
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> static size_t recursiveMemoryUsed(const PrefixTreeVertex& vertex)
</span><span class="cx"> {
</span><span class="lines">@@ -206,39 +220,186 @@
</span><span class="cx"> actions.append(actionId);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, HashMap<const PrefixTreeVertex*, ActionList>& actions, size_t maxNFASize)
</del><ins>+struct ActiveSubtree {
+ ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
+ : vertex(vertex)
+ , nfaNode(WTF::move(nfaNode))
+ , edgeIndex(edgeIndex)
+ {
+ }
+ PrefixTreeVertex& vertex;
+ ImmutableCharNFANodeBuilder nfaNode;
+ unsigned edgeIndex;
+};
+
+static void generateInfixUnsuitableForReverseSuffixTree(NFA& nfa, Vector<ActiveSubtree>& stack, const HashMap<const PrefixTreeVertex*, ActionList>& actions)
</ins><span class="cx"> {
</span><ins>+ // To avoid conflicts, we use the reverse suffix tree for subtrees that do not merge
+ // in the prefix tree.
+ //
+ // We only unify the suffixes to the actions on the leaf.
+ // If there are actions inside the tree, we generate the part of the subtree up to the action.
+ //
+ // If we accidentally insert a node with action inside the reverse-suffix-tree, we would create
+ // new actions on unrelated pattern when unifying their suffixes.
+ for (unsigned i = stack.size() - 1; i--;) {
+ ActiveSubtree& activeSubtree = stack[i];
+ if (activeSubtree.nfaNode.isValid())
+ return;
+
+ RELEASE_ASSERT_WITH_MESSAGE(i > 0, "The bottom of the stack must be the root of our fixed-length subtree. It should have it the isValid() case above.");
+
+ auto actionsIterator = actions.find(&activeSubtree.vertex);
+ bool hasActionInsideTree = actionsIterator != actions.end();
+
+ // Stricto sensu, we should count the number of exit edges with fixed length.
+ // That is costly and unlikely to matter in practice.
+ bool hasSingleOutcome = activeSubtree.vertex.edges.size() == 1;
+
+ if (hasActionInsideTree || !hasSingleOutcome) {
+ // Go back to the end of the subtree that has already been generated.
+ // From there, generate everything up to the vertex we found.
+ unsigned end = i;
+ unsigned beginning = end;
+
+ ActiveSubtree* sourceActiveSubtree = nullptr;
+ while (beginning--) {
+ ActiveSubtree& activeSubtree = stack[beginning];
+ if (activeSubtree.nfaNode.isValid()) {
+ sourceActiveSubtree = &activeSubtree;
+ break;
+ }
+ }
+ ASSERT_WITH_MESSAGE(sourceActiveSubtree, "The root should always have a valid generator.");
+
+ for (unsigned stackIndex = beginning + 1; stackIndex <= end; ++stackIndex) {
+ ImmutableCharNFANodeBuilder& sourceNode = sourceActiveSubtree->nfaNode;
+ ASSERT(sourceNode.isValid());
+ auto& edge = sourceActiveSubtree->vertex.edges[sourceActiveSubtree->edgeIndex];
+
+ ActiveSubtree& destinationActiveSubtree = stack[stackIndex];
+ destinationActiveSubtree.nfaNode = edge.term->generateGraph(nfa, sourceNode, actions.get(&destinationActiveSubtree.vertex));
+
+ sourceActiveSubtree = &destinationActiveSubtree;
+ }
+
+ return;
+ }
+ }
+}
+
+static void generateSuffixWithReverseSuffixTree(NFA& nfa, Vector<ActiveSubtree>& stack, const HashMap<const PrefixTreeVertex*, ActionList>& actions, ReverseSuffixTreeRoots& reverseSuffixTreeRoots)
+{
+ ActiveSubtree& leafSubtree = stack.last();
+ ASSERT_WITH_MESSAGE(!leafSubtree.nfaNode.isValid(), "The leaf should never be generated by the code above, it should always be inserted into the prefix tree.");
+
+ ActionList actionList = actions.get(&leafSubtree.vertex);
+ ASSERT_WITH_MESSAGE(!actionList.isEmpty(), "Our prefix tree should always have actions on the leaves by construction.");
+
+ HashableActionList hashableActionList(actionList);
+ auto rootAddResult = reverseSuffixTreeRoots.add(hashableActionList, ReverseSuffixTreeVertex());
+ if (rootAddResult.isNewEntry) {
+ ImmutableCharNFANodeBuilder newNode(nfa);
+ newNode.setActions(actionList.begin(), actionList.end());
+ rootAddResult.iterator->value.nodeId = newNode.nodeId();
+ }
+
+ ReverseSuffixTreeVertex* activeReverseSuffixTreeVertex = &rootAddResult.iterator->value;
+ uint32_t destinationNodeId = rootAddResult.iterator->value.nodeId;
+
+ unsigned stackPosition = stack.size() - 2;
+ while (true) {
+ ActiveSubtree& source = stack[stackPosition];
+ auto& edge = source.vertex.edges[source.edgeIndex];
+
+ // This is the end condition: when we meet a node that has already been generated,
+ // we just need to connect our backward tree to the forward tree.
+ //
+ // We *must not* add this last node to the reverse-suffix tree. That node can have
+ // transitions back to earlier part of the prefix tree. If the prefix tree "caches"
+ // such node, it would create new transitions that did not exist in the source language.
+ if (source.nfaNode.isValid()) {
+ stack.shrink(stackPosition + 1);
+ edge.term->generateGraph(nfa, source.nfaNode, destinationNodeId);
+ return;
+ }
+ --stackPosition;
+
+ ASSERT_WITH_MESSAGE(!actions.contains(&source.vertex), "Any node with final actions should have been created before hitting the reverse suffix-tree.");
+
+ ReverseSuffixTreeEdge* existingEdge = nullptr;
+ for (ReverseSuffixTreeEdge& potentialExistingEdge : activeReverseSuffixTreeVertex->edges) {
+ if (edge.term == potentialExistingEdge.term) {
+ existingEdge = &potentialExistingEdge;
+ break;
+ }
+ }
+
+ if (existingEdge)
+ activeReverseSuffixTreeVertex = existingEdge->child.get();
+ else {
+ ImmutableCharNFANodeBuilder newNode(nfa);
+ edge.term->generateGraph(nfa, newNode, destinationNodeId);
+ std::unique_ptr<ReverseSuffixTreeVertex> newVertex(new ReverseSuffixTreeVertex());
+ newVertex->nodeId = newNode.nodeId();
+
+ ReverseSuffixTreeVertex* newVertexAddress = newVertex.get();
+ activeReverseSuffixTreeVertex->edges.append(ReverseSuffixTreeEdge({ edge.term, WTF::move(newVertex) }));
+ activeReverseSuffixTreeVertex = newVertexAddress;
+ }
+ destinationNodeId = activeReverseSuffixTreeVertex->nodeId;
+
+ ASSERT(source.vertex.edges.size() == 1);
+ source.vertex.edges.clear();
+ }
+
+ RELEASE_ASSERT_NOT_REACHED();
+}
+
+static void clearReverseSuffixTree(ReverseSuffixTreeRoots& reverseSuffixTreeRoots)
+{
+ // We cannot rely on the destructor being called in order from top to bottom as we may overflow
+ // the stack. Instead, we go depth first in the reverse-suffix-tree.
+
+ for (auto& slot : reverseSuffixTreeRoots) {
+ Vector<ReverseSuffixTreeVertex*, 128> stack;
+ stack.append(&slot.value);
+
+ while (true) {
+ ReverseSuffixTreeVertex* top = stack.last();
+ if (top->edges.isEmpty()) {
+ stack.removeLast();
+ if (stack.isEmpty())
+ break;
+ stack.last()->edges.removeLast();
+ } else
+ stack.append(top->edges.last().child.get());
+ }
+ }
+ reverseSuffixTreeRoots.clear();
+}
+
+static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, const HashMap<const PrefixTreeVertex*, ActionList>& actions, size_t maxNFASize)
+{
</ins><span class="cx"> // This recurses the subtree of the prefix tree.
</span><span class="cx"> // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph,
</span><span class="cx"> // recurses into children, and deletes any processed leaf nodes.
</span><del>- struct ActiveSubtree {
- ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
- : vertex(vertex)
- , nfaNode(WTF::move(nfaNode))
- , edgeIndex(edgeIndex)
- {
- }
- PrefixTreeVertex& vertex;
- ImmutableCharNFANodeBuilder nfaNode;
- unsigned edgeIndex;
- };
</del><ins>+
+ ReverseSuffixTreeRoots reverseSuffixTreeRoots;
</ins><span class="cx"> Vector<ActiveSubtree> stack;
</span><span class="cx"> if (!root.edges.isEmpty())
</span><span class="cx"> stack.append(ActiveSubtree(root, WTF::move(subtreeRoot), 0));
</span><ins>+
</ins><span class="cx"> bool nfaTooBig = false;
</span><span class="cx">
</span><span class="cx"> // Generate graphs for each subtree that does not contain any quantifiers.
</span><span class="cx"> while (!stack.isEmpty()) {
</span><span class="cx"> PrefixTreeVertex& vertex = stack.last().vertex;
</span><span class="cx"> const unsigned edgeIndex = stack.last().edgeIndex;
</span><del>-
- // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
- if (vertex.edges.isEmpty() && nfa.nodes.size() > maxNFASize)
- nfaTooBig = true;
-
</del><ins>+
</ins><span class="cx"> if (edgeIndex < vertex.edges.size()) {
</span><span class="cx"> auto& edge = vertex.edges[edgeIndex];
</span><del>-
</del><ins>+
</ins><span class="cx"> // Clean up any processed leaves and return early if we are past the maxNFASize.
</span><span class="cx"> if (nfaTooBig) {
</span><span class="cx"> stack.last().edgeIndex = stack.last().vertex.edges.size();
</span><span class="lines">@@ -251,17 +412,28 @@
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-
- ImmutableCharNFANodeBuilder newNode = edge.term->generateGraph(nfa, stack.last().nfaNode, actions.get(edge.child.get()));
</del><span class="cx"> ASSERT(edge.child.get());
</span><del>- stack.append(ActiveSubtree(*edge.child.get(), WTF::move(newNode), 0));
</del><ins>+ ImmutableCharNFANodeBuilder emptyBuilder;
+ stack.append(ActiveSubtree(*edge.child.get(), WTF::move(emptyBuilder), 0));
</ins><span class="cx"> } else {
</span><ins>+ bool isLeaf = vertex.edges.isEmpty();
+
</ins><span class="cx"> ASSERT(edgeIndex == vertex.edges.size());
</span><span class="cx"> vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
</span><span class="cx"> {
</span><span class="cx"> return !edge.term;
</span><span class="cx"> });
</span><del>- stack.removeLast();
</del><ins>+
+ if (isLeaf) {
+ generateInfixUnsuitableForReverseSuffixTree(nfa, stack, actions);
+ generateSuffixWithReverseSuffixTree(nfa, stack, actions, reverseSuffixTreeRoots);
+
+ // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
+ if (nfa.nodes.size() > maxNFASize)
+ nfaTooBig = true;
+ } else
+ stack.removeLast();
+
</ins><span class="cx"> if (!stack.isEmpty()) {
</span><span class="cx"> auto& activeSubtree = stack.last();
</span><span class="cx"> auto& edge = activeSubtree.vertex.edges[stack.last().edgeIndex];
</span><span class="lines">@@ -271,6 +443,7 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+ clearReverseSuffixTree(reverseSuffixTreeRoots);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void CombinedURLFilters::processNFAs(size_t maxNFASize, std::function<void(NFA&&)> handler)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -147,7 +147,7 @@
</span><span class="cx"> dataLogF("%llu", actions[actionIndex]);
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>- dataLogF("]");
</del><ins>+ dataLogF(">]");
</ins><span class="cx">
</span><span class="cx"> if (!actions.isEmpty())
</span><span class="cx"> dataLogF(" [shape=doublecircle]");
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsHashableActionListh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/HashableActionList.h (0 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/HashableActionList.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/HashableActionList.h 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -0,0 +1,97 @@
</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 HashableActionList_h
+#define HashableActionList_h
+
+#include <wtf/StringHasher.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+struct HashableActionList {
+ enum DeletedValueTag { DeletedValue };
+ explicit HashableActionList(DeletedValueTag) { state = Deleted; }
+
+ enum EmptyValueTag { EmptyValue };
+ explicit HashableActionList(EmptyValueTag) { state = Empty; }
+
+ template<typename AnyVectorType>
+ explicit HashableActionList(const AnyVectorType& otherActions)
+ : actions(otherActions)
+ , state(Valid)
+ {
+ std::sort(actions.begin(), actions.end());
+ 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; }
+
+ bool operator==(const HashableActionList other) const
+ {
+ return state == other.state && actions == other.actions;
+ }
+
+ bool operator!=(const HashableActionList other) const
+ {
+ return !(*this == other);
+ }
+
+ Vector<uint64_t> actions;
+ unsigned hash;
+ enum {
+ Valid,
+ Empty,
+ Deleted
+ } state;
+};
+
+struct HashableActionListHash {
+ static unsigned hash(const HashableActionList& actionKey)
+ {
+ return actionKey.hash;
+ }
+
+ static bool equal(const HashableActionList& a, const HashableActionList& b)
+ {
+ return a == b;
+ }
+ static const bool safeToCompareToEmptyOrDeleted = false;
+};
+
+struct HashableActionListHashTraits : public WTF::CustomHashTraits<HashableActionList> {
+ static const bool emptyValueIsZero = false;
+};
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsImmutableNFANodeBuilderh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -52,9 +52,6 @@
</span><span class="cx"> {
</span><span class="cx"> m_nodeId = m_immutableNFA->nodes.size();
</span><span class="cx"> m_immutableNFA->nodes.append(ImmutableNFANode());
</span><del>-#if !ASSERT_DISABLED
- m_isDisconnected = true;
-#endif
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ImmutableNFANodeBuilder(ImmutableNFANodeBuilder&& other)
</span><span class="lines">@@ -64,25 +61,28 @@
</span><span class="cx"> , m_actions(WTF::move(other.m_actions))
</span><span class="cx"> , m_nodeId(other.m_nodeId)
</span><span class="cx"> , m_finalized(other.m_finalized)
</span><del>-#if !ASSERT_DISABLED
- , m_isDisconnected(other.m_isDisconnected)
-#endif
</del><span class="cx"> {
</span><span class="cx"> other.m_immutableNFA = nullptr;
</span><span class="cx"> other.m_finalized = true;
</span><del>-#if !ASSERT_DISABLED
- other.m_isDisconnected = false;
-#endif
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ~ImmutableNFANodeBuilder()
</span><span class="cx"> {
</span><del>- ASSERT_WITH_MESSAGE(!m_isDisconnected, "This nodes is not connected to anything and is not reached by any other node.");
-
</del><span class="cx"> if (!m_finalized)
</span><span class="cx"> finalize();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isValid() const
+ {
+ return !!m_immutableNFA;
+ }
+
+ uint32_t nodeId() const
+ {
+ ASSERT(isValid());
+ return m_nodeId;
+ }
+
</ins><span class="cx"> struct TrivialRange {
</span><span class="cx"> CharacterType first;
</span><span class="cx"> CharacterType last;
</span><span class="lines">@@ -108,15 +108,10 @@
</span><span class="cx"> bool isEnd;
</span><span class="cx"> };
</span><span class="cx">
</span><del>- void addTransition(CharacterType first, CharacterType last, const ImmutableNFANodeBuilder& target)
</del><ins>+ void addTransition(CharacterType first, CharacterType last, uint32_t targetNodeId)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(!m_finalized);
</span><span class="cx"> ASSERT(m_immutableNFA);
</span><del>- ASSERT(m_immutableNFA == target.m_immutableNFA);
-#if !ASSERT_DISABLED
- m_isDisconnected = false;
- target.m_isDisconnected = false;
-#endif
</del><span class="cx">
</span><span class="cx"> struct Converter {
</span><span class="cx"> TargetSet convert(uint32_t target)
</span><span class="lines">@@ -130,19 +125,20 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> Converter converter;
</span><del>- m_ranges.extend(FakeRangeIterator { { first, last }, target.m_nodeId, false }, FakeRangeIterator { { 0, 0 }, target.m_nodeId, true }, converter);
</del><ins>+ m_ranges.extend(FakeRangeIterator { { first, last }, targetNodeId, false }, FakeRangeIterator { { 0, 0 }, targetNodeId, true }, converter);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void addEpsilonTransition(const ImmutableNFANodeBuilder& target)
</span><span class="cx"> {
</span><ins>+ ASSERT(m_immutableNFA == target.m_immutableNFA);
+ addEpsilonTransition(target.m_nodeId);
+ }
+
+ void addEpsilonTransition(uint32_t targetNodeId)
+ {
</ins><span class="cx"> ASSERT(!m_finalized);
</span><span class="cx"> ASSERT(m_immutableNFA);
</span><del>- ASSERT(m_immutableNFA == target.m_immutableNFA);
-#if !ASSERT_DISABLED
- m_isDisconnected = false;
- target.m_isDisconnected = false;
-#endif
- m_epsilonTransitionTargets.add(target.m_nodeId);
</del><ins>+ m_epsilonTransitionTargets.add(targetNodeId);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename ActionIterator>
</span><span class="lines">@@ -168,10 +164,6 @@
</span><span class="cx">
</span><span class="cx"> other.m_immutableNFA = nullptr;
</span><span class="cx"> other.m_finalized = true;
</span><del>-#if !ASSERT_DISABLED
- m_isDisconnected = other.m_isDisconnected;
- other.m_isDisconnected = false;
-#endif
</del><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -230,9 +222,6 @@
</span><span class="cx"> HashSet<ActionType, WTF::IntHash<ActionType>, WTF::UnsignedWithZeroKeyHashTraits<ActionType>> m_actions;
</span><span class="cx"> uint32_t m_nodeId;
</span><span class="cx"> bool m_finalized { true };
</span><del>-#if !ASSERT_DISABLED
- mutable bool m_isDisconnected { false };
-#endif
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsTermh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/Term.h (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/Term.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/Term.h 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -83,7 +83,8 @@
</span><span class="cx">
</span><span class="cx"> void quantify(const AtomQuantifier&);
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const;
</del><ins>+ ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const;
+ void generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
</ins><span class="cx">
</span><span class="cx"> bool isEndOfLineAssertion() const;
</span><span class="cx">
</span><span class="lines">@@ -118,7 +119,8 @@
</span><span class="cx"> // The return value can be false for a group equivalent to a universal transition.
</span><span class="cx"> bool isUniversalTransition() const;
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source) const;
</del><ins>+ void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const;
+ void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
</ins><span class="cx">
</span><span class="cx"> void destroy();
</span><span class="cx">
</span><span class="lines">@@ -377,50 +379,52 @@
</span><span class="cx"> m_quantifier = quantifier;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const
</del><ins>+inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const
</ins><span class="cx"> {
</span><ins>+ ImmutableCharNFANodeBuilder newEnd(nfa);
+ generateGraph(nfa, source, newEnd.nodeId());
+ newEnd.setActions(finalActions.begin(), finalActions.end());
+ return newEnd;
+}
+
+inline void Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
+{
</ins><span class="cx"> ASSERT(isValid());
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder newEnd;
-
</del><span class="cx"> switch (m_quantifier) {
</span><span class="cx"> case AtomQuantifier::One: {
</span><del>- newEnd = generateSubgraphForAtom(nfa, start);
</del><ins>+ generateSubgraphForAtom(nfa, source, destination);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrOne: {
</span><del>- newEnd = generateSubgraphForAtom(nfa, start);
- start.addEpsilonTransition(newEnd);
</del><ins>+ generateSubgraphForAtom(nfa, source, destination);
+ source.addEpsilonTransition(destination);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrMore: {
</span><span class="cx"> ImmutableCharNFANodeBuilder repeatStart(nfa);
</span><del>- start.addEpsilonTransition(repeatStart);
</del><ins>+ source.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatEnd(nfa);
+ generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
</ins><span class="cx"> repeatEnd.addEpsilonTransition(repeatStart);
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder kleenEnd(nfa);
- repeatEnd.addEpsilonTransition(kleenEnd);
- start.addEpsilonTransition(kleenEnd);
- newEnd = WTF::move(kleenEnd);
</del><ins>+ repeatEnd.addEpsilonTransition(destination);
+ source.addEpsilonTransition(destination);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::OneOrMore: {
</span><span class="cx"> ImmutableCharNFANodeBuilder repeatStart(nfa);
</span><del>- start.addEpsilonTransition(repeatStart);
</del><ins>+ source.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatEnd(nfa);
+ generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
</ins><span class="cx"> repeatEnd.addEpsilonTransition(repeatStart);
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder afterRepeat(nfa);
- repeatEnd.addEpsilonTransition(afterRepeat);
- newEnd = WTF::move(afterRepeat);
</del><ins>+ repeatEnd.addEpsilonTransition(destination);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>- newEnd.setActions(finalActions.begin(), finalActions.end());
- return newEnd;
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline bool Term::isEndOfLineAssertion() const
</span><span class="lines">@@ -582,14 +586,19 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline ImmutableCharNFANodeBuilder Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source) const
</del><ins>+inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const
</ins><span class="cx"> {
</span><ins>+ generateSubgraphForAtom(nfa, source, destination.nodeId());
+}
+
+inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
+{
</ins><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><span class="cx"> ASSERT_NOT_REACHED();
</span><del>- return ImmutableCharNFANodeBuilder();
</del><ins>+ source.addEpsilonTransition(destination);
+ break;
</ins><span class="cx"> case TermType::CharacterSet: {
</span><del>- ImmutableCharNFANodeBuilder newNode(nfa);
</del><span class="cx"> if (!m_atomData.characterSet.inverted()) {
</span><span class="cx"> UChar i = 0;
</span><span class="cx"> while (true) {
</span><span class="lines">@@ -602,7 +611,7 @@
</span><span class="cx"> ++i;
</span><span class="cx"> while (i < 128 && m_atomData.characterSet.get(i))
</span><span class="cx"> ++i;
</span><del>- source.addTransition(start, i - 1, newNode);
</del><ins>+ source.addTransition(start, i - 1, destination);
</ins><span class="cx"> }
</span><span class="cx"> } else {
</span><span class="cx"> UChar i = 1;
</span><span class="lines">@@ -616,27 +625,32 @@
</span><span class="cx"> ++i;
</span><span class="cx"> while (i < 128 && !m_atomData.characterSet.get(i))
</span><span class="cx"> ++i;
</span><del>- source.addTransition(start, i - 1, newNode);
</del><ins>+ source.addTransition(start, i - 1, destination);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>- return newNode;
</del><ins>+ break;
</ins><span class="cx"> }
</span><span class="cx"> case TermType::Group: {
</span><span class="cx"> if (m_atomData.group.terms.isEmpty()) {
</span><span class="cx"> // FIXME: any kind of empty term could be avoided in the parser. This case should turned into an assertion.
</span><del>- ImmutableCharNFANodeBuilder newNode(nfa);
- source.addEpsilonTransition(newNode);
- return newNode;
</del><ins>+ source.addEpsilonTransition(destination);
+ return;
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+ if (m_atomData.group.terms.size() == 1) {
+ m_atomData.group.terms.first().generateGraph(nfa, source, destination);
+ return;
+ }
+
</ins><span class="cx"> ImmutableCharNFANodeBuilder lastTarget = m_atomData.group.terms.first().generateGraph(nfa, source, ActionList());
</span><del>- for (unsigned i = 1; i < m_atomData.group.terms.size(); ++i) {
</del><ins>+ for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {
</ins><span class="cx"> const Term& currentTerm = m_atomData.group.terms[i];
</span><span class="cx"> ImmutableCharNFANodeBuilder newNode = currentTerm.generateGraph(nfa, lastTarget, ActionList());
</span><span class="cx"> lastTarget = WTF::move(newNode);
</span><span class="cx"> }
</span><del>-
- return lastTarget;
</del><ins>+ const Term& lastTerm = m_atomData.group.terms.last();
+ lastTerm.generateGraph(nfa, lastTarget, destination);
+ break;
</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 (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -1,3 +1,14 @@
</span><ins>+2015-07-16 Benjamin Poulain <bpoulain@apple.com>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::compareContents):
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+
</ins><span class="cx"> 2015-07-15 Carlos Garcia Campos <cgarcia@igalia.com>
</span><span class="cx">
</span><span class="cx"> [GTK] Input method filter is always enabled when the view is focused
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFVectorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -95,6 +95,103 @@
</span><span class="cx"> EXPECT_EQ(4, vector[3]);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST(WTF_Vector, InitializeFromOtherInitialCapacity)
+{
+ Vector<int, 3> vector = { 1, 3, 2, 4 };
+ Vector<int, 5> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+ EXPECT_EQ(5U, vectorCopy.capacity());
+
+ EXPECT_EQ(1, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(4, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherInitialCapacity)
+{
+ Vector<int, 3> vector = { 1, 3, 2, 4 };
+ Vector<int, 5> vectorCopy { 0 };
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(1U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+ EXPECT_EQ(5U, vectorCopy.capacity());
+
+ EXPECT_EQ(1, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(4, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, InitializeFromOtherOverflowBehavior)
+{
+ Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
+ Vector<int, 7, UnsafeVectorOverflow> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(4, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherOverflowBehavior)
+{
+ Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
+ Vector<int, 7, UnsafeVectorOverflow> vectorCopy = { 0, 0, 0 };
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(3U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(4, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, InitializeFromOtherMinCapacity)
+{
+ Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
+ Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(3, vectorCopy[0]);
+ EXPECT_EQ(4, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherMinCapacity)
+{
+ Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
+ Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(0U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(3, vectorCopy[0]);
+ EXPECT_EQ(4, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
</ins><span class="cx"> TEST(WTF_Vector, Reverse)
</span><span class="cx"> {
</span><span class="cx"> Vector<int> intVector;
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -235,6 +235,36 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("http://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, SingleCharacter)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^z\"}}]");
+ testRequest(matchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("zttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"y\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/ywebkit"), { ContentExtensions::ActionType::BlockLoad });
+}
+
+TEST_F(ContentExtensionTest, SingleCharacterDisjunction)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^z\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^c\"}}]");
+ testRequest(matchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("bttp://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("cttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("dttp://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("zttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"x\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"y\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/dwebkit"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/xwebkit"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/ywebkit"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/zwebkit"), { });
+}
+
</ins><span class="cx"> TEST_F(ContentExtensionTest, RangeBasic)
</span><span class="cx"> {
</span><span class="cx"> auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"w[0-9]c\", \"url-filter-is-case-sensitive\":true}},"
</span><span class="lines">@@ -444,6 +474,142 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("https://post.org/post"), { });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, UndistinguishableActionInsidePrefixTree)
+{
+ // In this case, the two actions are undistinguishable. The actions of "prefix" appear inside the prefixtree
+ // ending at "suffix".
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefix\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefixsuffix\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://prefix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/aaaprefixaaa"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://prefixsuffix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefixsuffix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bbbprefixsuffixbbb"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://suffix.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/suffix"), { });
+}
+
+TEST_F(ContentExtensionTest, DistinguishableActionInsidePrefixTree)
+{
+ // In this case, the two actions are distinguishable.
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefix\"}},"
+ "{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\"prefixsuffix\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://prefix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/aaaprefixaaa"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://prefixsuffix.org/"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefixsuffix"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bbbprefixsuffixbbb"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://suffix.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/suffix"), { });
+}
+
+TEST_F(ContentExtensionTest, DistinguishablePrefixAreNotMerged)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"foo\\\\.org\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"bar\\\\.org\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foo.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://bar.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://foor.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fooar.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fooba.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foob.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foor.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foar.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foba.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fob.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://barf.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://barfo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baroo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baro.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baf.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://bafo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baoo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://bao.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("http://foo.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://oo.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://o.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://rgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://gbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgr.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.org.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgorg/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgrg/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgg/"), { ContentExtensions::ActionType::BlockLoad });
+}
+
+static void compareContents(const ContentExtensions::DFABytecodeInterpreter::Actions& a, const Vector<uint64_t>& b)
+{
+ EXPECT_EQ(a.size(), b.size());
+ for (unsigned i = 0; i < b.size(); ++i)
+ EXPECT_TRUE(a.contains(b[i]));
+}
+
+TEST_F(ContentExtensionTest, SearchSuffixesWithIdenticalActionAreMerged)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("foo\\.org", false, 0));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("ba\\.org", false, 0));
+
+ Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
+ EXPECT_EQ(1ul, nfas.size());
+ EXPECT_EQ(12ul, nfas.first().nodes.size());
+
+ ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ Vector<ContentExtensions::DFABytecode> bytecode;
+ ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ ContentExtensions::DFABytecodeInterpreter interpreter(bytecode.data(), bytecode.size());
+ compareContents(interpreter.interpret("foo.org", 0), { 0 });
+ compareContents(interpreter.interpret("ba.org", 0), { 0 });
+ compareContents(interpreter.interpret("bar.org", 0), { });
+
+ compareContents(interpreter.interpret("paddingfoo.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingba.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingbar.org", 0), { });
+}
+
+TEST_F(ContentExtensionTest, SearchSuffixesWithDistinguishableActionAreNotMerged)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("foo\\.org", false, 0));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("ba\\.org", false, 1));
+
+ Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
+
+ EXPECT_EQ(1ul, nfas.size());
+ EXPECT_EQ(17ul, nfas.first().nodes.size());
+
+ ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ Vector<ContentExtensions::DFABytecode> bytecode;
+ ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ ContentExtensions::DFABytecodeInterpreter interpreter(bytecode.data(), bytecode.size());
+ compareContents(interpreter.interpret("foo.org", 0), { 0 });
+ compareContents(interpreter.interpret("ba.org", 0), { 1 });
+ compareContents(interpreter.interpret("bar.org", 0), { });
+
+ compareContents(interpreter.interpret("paddingfoo.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingba.org", 0), { 1 });
+ compareContents(interpreter.interpret("paddingba.orgfoo.org", 0), { 1, 0 });
+ compareContents(interpreter.interpret("paddingbar.org", 0), { });
+}
+
</ins><span class="cx"> TEST_F(ContentExtensionTest, DomainTriggers)
</span><span class="cx"> {
</span><span class="cx"> auto ifDomainBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"test\\\\.html\", \"if-domain\":[\"webkit.org\"]}}]");
</span><span class="lines">@@ -853,13 +1019,6 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> #ifdef NDEBUG
</span><del>-static void compareContents(const ContentExtensions::DFABytecodeInterpreter::Actions& a, const Vector<uint64_t>& b)
-{
- EXPECT_EQ(a.size(), b.size());
- for (unsigned i = 0; i < b.size(); ++i)
- EXPECT_TRUE(a.contains(b[i]));
-}
-
</del><span class="cx"> static uint64_t expectedIndex(char c, unsigned position)
</span><span class="cx"> {
</span><span class="cx"> uint64_t index = c - 'A';
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (186909 => 186910)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-16 21:51:08 UTC (rev 186910)
</span><span class="lines">@@ -41,15 +41,31 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, BasicSearch)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*foo", ".*bar", ".*bang"});
</span><del>- EXPECT_EQ(static_cast<size_t>(10), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(8), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(DFAMinimizerTest, MergeSuffixes)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*aaa", ".*aab", ".*aba", ".*abb", ".*baa", ".*bab", ".*bba", ".*bbb"});
+ EXPECT_EQ(static_cast<size_t>(12), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, MergeInfixes)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*aaakit", ".*aabkit", ".*abakit", ".*abbkit", ".*baakit", ".*babkit", ".*bbakit", ".*bbbkit"});
+ EXPECT_EQ(static_cast<size_t>(15), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
+}
+
</ins><span class="cx"> TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge1)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.a", "^b.a", "^bac", "^bbc", "^BCC"});
</span><del>- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -57,7 +73,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge2)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^bbc", "^BCC", "^a.a", "^b.a"});
</span><del>- EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -65,7 +81,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge3)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.c", "^b.c", "^baa", "^bba", "^BCA"});
</span><del>- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -73,7 +89,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge4)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^baa", "^bba", "^BCA", "^a.c", "^b.c"});
</span><del>- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -81,7 +97,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, FallbackTransitionsToOtherNodeInSameGroupDoesNotDifferentiateGroup)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^aac", "^a.c", "^b.c"});
</span><del>- EXPECT_EQ(static_cast<size_t>(9), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(5), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -89,7 +105,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator1)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.bc.de", "^a.bd.ef"});
</span><del>- EXPECT_EQ(static_cast<size_t>(12), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
</span><span class="cx"> }
</span><span class="lines">@@ -97,7 +113,7 @@
</span><span class="cx"> TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator2)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^cb.", "^db.b"});
</span><del>- EXPECT_EQ(static_cast<size_t>(8), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
</ins><span class="cx"> dfa.minimize();
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
</span><span class="cx"> }
</span></span></pre>
</div>
</div>
</body>
</html>