<!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>[187087] branches/safari-601.1-branch</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/187087">187087</a></dd>
<dt>Author</dt> <dd>matthew_hanson@apple.com</dd>
<dt>Date</dt> <dd>2015-07-20 22:08:21 -0700 (Mon, 20 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge <a href="http://trac.webkit.org/projects/webkit/changeset/186910">r186910</a>. rdar://problem/21863296</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#branchessafari6011branchSourceWTFChangeLog">branches/safari-601.1-branch/Source/WTF/ChangeLog</a></li>
<li><a href="#branchessafari6011branchSourceWTFwtfVectorh">branches/safari-601.1-branch/Source/WTF/wtf/Vector.h</a></li>
<li><a href="#branchessafari6011branchSourceWebCoreChangeLog">branches/safari-601.1-branch/Source/WebCore/ChangeLog</a></li>
<li><a href="#branchessafari6011branchSourceWebCoreWebCorexcodeprojprojectpbxproj">branches/safari-601.1-branch/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#branchessafari6011branchSourceWebCorecontentextensionsCombinedURLFilterscpp">branches/safari-601.1-branch/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#branchessafari6011branchSourceWebCorecontentextensionsDFAcpp">branches/safari-601.1-branch/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#branchessafari6011branchSourceWebCorecontentextensionsImmutableNFANodeBuilderh">branches/safari-601.1-branch/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h</a></li>
<li><a href="#branchessafari6011branchSourceWebCorecontentextensionsTermh">branches/safari-601.1-branch/Source/WebCore/contentextensions/Term.h</a></li>
<li><a href="#branchessafari6011branchToolsChangeLog">branches/safari-601.1-branch/Tools/ChangeLog</a></li>
<li><a href="#branchessafari6011branchToolsTestWebKitAPITestsWTFVectorcpp">branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp</a></li>
<li><a href="#branchessafari6011branchToolsTestWebKitAPITestsWebCoreContentExtensionscpp">branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
<li><a href="#branchessafari6011branchToolsTestWebKitAPITestsWebCoreDFAMinimizercpp">branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#branchessafari6011branchSourceWebCorecontentextensionsHashableActionListh">branches/safari-601.1-branch/Source/WebCore/contentextensions/HashableActionList.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="branchessafari6011branchSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WTF/ChangeLog (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WTF/ChangeLog 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WTF/ChangeLog 2015-07-21 05:08:21 UTC (rev 187087)
</span><span class="lines">@@ -1,3 +1,22 @@
</span><ins>+2015-07-20 Matthew Hanson <matthew_hanson@apple.com>
+
+ Merge r186910. rdar://problem/21863296
+
+ 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 Lucas Forschler <lforschler@apple.com>
</span><span class="cx">
</span><span class="cx"> Merge r186826
</span></span></pre></div>
<a id="branchessafari6011branchSourceWTFwtfVectorh"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WTF/wtf/Vector.h (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WTF/wtf/Vector.h 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WTF/wtf/Vector.h 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/ChangeLog (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/ChangeLog 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/ChangeLog 2015-07-21 05:08:21 UTC (rev 187087)
</span><span class="lines">@@ -1,5 +1,110 @@
</span><span class="cx"> 2015-07-20 Matthew Hanson <matthew_hanson@apple.com>
</span><span class="cx">
</span><ins>+ Merge r186910. rdar://problem/21863296
+
+ 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.
+
+2015-07-20 Matthew Hanson <matthew_hanson@apple.com>
+
</ins><span class="cx"> Merge r186715. rdar://problem/21863296
</span><span class="cx">
</span><span class="cx"> 2015-07-11 Benjamin Poulain <benjamin@webkit.org>
</span></span></pre></div>
<a id="branchessafari6011branchSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/WebCore.xcodeproj/project.pbxproj (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-21 05:08:21 UTC (rev 187087)
</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">@@ -8194,6 +8195,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">@@ -15724,6 +15726,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">@@ -27268,6 +27271,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="branchessafari6011branchSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/contentextensions/CombinedURLFilters.cpp (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/contentextensions/DFA.cpp (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/contentextensions/DFA.cpp 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/contentextensions/DFA.cpp 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchSourceWebCorecontentextensionsHashableActionListh"></a>
<div class="addfile"><h4>Added: branches/safari-601.1-branch/Source/WebCore/contentextensions/HashableActionList.h (0 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/contentextensions/HashableActionList.h (rev 0)
+++ branches/safari-601.1-branch/Source/WebCore/contentextensions/HashableActionList.h 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchSourceWebCorecontentextensionsImmutableNFANodeBuilderh"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchSourceWebCorecontentextensionsTermh"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Source/WebCore/contentextensions/Term.h (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Source/WebCore/contentextensions/Term.h 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Source/WebCore/contentextensions/Term.h 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchToolsChangeLog"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Tools/ChangeLog (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Tools/ChangeLog 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Tools/ChangeLog 2015-07-21 05:08:21 UTC (rev 187087)
</span><span class="lines">@@ -1,5 +1,20 @@
</span><span class="cx"> 2015-07-20 Matthew Hanson <matthew_hanson@apple.com>
</span><span class="cx">
</span><ins>+ Merge r186910. rdar://problem/21863296
+
+ 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:
+
+2015-07-20 Matthew Hanson <matthew_hanson@apple.com>
+
</ins><span class="cx"> Merge r186982. rdar://problem/21567820
</span><span class="cx">
</span><span class="cx"> 2015-07-17 Andy Estes <aestes@apple.com>
</span></span></pre></div>
<a id="branchessafari6011branchToolsTestWebKitAPITestsWTFVectorcpp"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-21 05:08:21 UTC (rev 187087)
</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="branchessafari6011branchToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-21 05:08:21 UTC (rev 187087)
</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></pre></div>
<a id="branchessafari6011branchToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (187086 => 187087)</h4>
<pre class="diff"><span>
<span class="info">--- branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-21 05:08:13 UTC (rev 187086)
+++ branches/safari-601.1-branch/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-21 05:08:21 UTC (rev 187087)
</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>