<!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>[186374] 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/186374">186374</a></dd>
<dt>Author</dt> <dd>achristensen@apple.com</dd>
<dt>Date</dt> <dd>2015-07-06 14:06:30 -0700 (Mon, 06 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[Content Extensions] Make the DFA transitions ranges instead of characters
https://bugs.webkit.org/show_bug.cgi?id=146575
Patch by Benjamin Poulain <benjamin@webkit.org> on 2015-07-06
Reviewed by Alex Christensen.
Source/WebCore:
This patch changes the DFA and code using the DFA to use ranges
to represent the transitions between any two nodes.
This patch builds on top of the tools introduced in <a href="http://trac.webkit.org/projects/webkit/changeset/186079">r186079</a>.
The DFA structure is basically the same as ImmutableNFA but without
any epsilon transitions.
This patch introduces a transition iterator to make the DFA
compatible with the existing algorithms.
---
The DFA combiner is rebuilt on top of MutableRangeList. Combining the transitions
of two nodes is one by merging the range list of each not into a common
MutableRangeList.
The data converter takes care of creating the signature of the combination.
The code got simpler since MutableRangeList does most of the work now. It is also
much faster.
---
The minimizer is more intersting.
With the current algorithm, we cannot resolve overlaps between ranges. On the other
hand, the minimizer does not care about the symbol of the transitions if we are careful
to partition transitions of the same symbol together.
What I did was to turn the minimizer into a pure transition based one, BUT each
"symbol" is actually an unbreakable range.
The first step is to go over all the transitions of all the nodes and find the largest
ranges such that the alphabet of interest is covered but there is not a single intersection
between any two nodes (what I called "singular transitions" in the code).
This can be done efficiently with MutableRangeList.
A little trick there is that I also used the converter to count how many real transition
overlaps any singular transition.
Those singular transitions become the alphabet of our minimizer. The "symbol" of our alphabet
is simply the position of the singular transition in the list.
The partition of transition is created by populating each set with all the transition that
overlaps the symbols.
Note that since the partition is created on the fly, the Transition structure used for
repartitioning only contains the source of the transitions.
Once our transition parition has been carefuly created, we can completely forget about
the symbols and only work with subsets.
Since the singular transitions have no overlap (unlike fallback transitions), this new minimizer
will find the minimial solution for well formed input.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::memoryUsed):
(WebCore::ContentExtensions::printTransitions):
(WebCore::ContentExtensions::DFANode::actions): Deleted.
(WebCore::ContentExtensions::DFANode::transitions): Deleted.
(WebCore::ContentExtensions::DFANode::fallbackTransitionDestination): Deleted.
(WebCore::ContentExtensions::DFANode::changeFallbackTransition): Deleted.
(WebCore::ContentExtensions::DFANode::addFallbackTransition): Deleted.
(WebCore::ContentExtensions::DFANode::containsTransition): Deleted.
(WebCore::ContentExtensions::DFANode::kill): Deleted.
(WebCore::ContentExtensions::DFA::debugPrintDot): Deleted.
* contentextensions/DFA.h:
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::range):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::target):
(WebCore::ContentExtensions::DFANode::RangeIterator::range):
(WebCore::ContentExtensions::DFANode::RangeIterator::target):
(WebCore::ContentExtensions::DFANode::RangeIterator::resetTarget):
* contentextensions/DFABytecodeCompiler.cpp:
(WebCore::ContentExtensions::DFABytecodeCompiler::ranges):
(WebCore::ContentExtensions::DFABytecodeCompiler::nodeTransitionsMaxBytecodeSize):
(WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
* contentextensions/DFACombiner.cpp:
(WebCore::ContentExtensions::DFAMerger::TargetConverter::convert):
(WebCore::ContentExtensions::DFAMerger::TargetConverter::extend):
(WebCore::ContentExtensions::DFAMerger::TargetConverter::setHalfSignature):
(WebCore::ContentExtensions::DFAMerger::merge):
(WebCore::ContentExtensions::DFAMerger::getOrCreateCombinedNode):
(WebCore::ContentExtensions::DFAMerger::setHalfSignature): Deleted.
(WebCore::ContentExtensions::DFAMerger::populateTransitions): Deleted.
(WebCore::ContentExtensions::DFAMerger::populateFromFallbackTransitions): Deleted.
(WebCore::ContentExtensions::DFAMerger::createTransitions): Deleted.
(WebCore::ContentExtensions::DFAMerger::createFallbackTransitionIfNeeded): Deleted.
* contentextensions/DFAMinimizer.cpp:
(WebCore::ContentExtensions::DFAMinimizer::minimize):
* contentextensions/DFANode.cpp: Added.
(WebCore::ContentExtensions::DFANode::actions):
(WebCore::ContentExtensions::DFANode::containsTransition):
(WebCore::ContentExtensions::DFANode::kill):
(WebCore::ContentExtensions::DFANode::canUseFallbackTransition):
(WebCore::ContentExtensions::DFANode::bestFallbackTarget):
* contentextensions/DFANode.h:
(WebCore::ContentExtensions::CharRange::size):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator*):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator==):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator!=):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator++):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::first):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::last):
(WebCore::ContentExtensions::DFANode::ConstRangeIterator::data):
(WebCore::ContentExtensions::DFANode::IterableConstRange::begin):
(WebCore::ContentExtensions::DFANode::IterableConstRange::end):
(WebCore::ContentExtensions::DFANode::transitions):
(WebCore::ContentExtensions::DFANode::RangeIterator::operator*):
(WebCore::ContentExtensions::DFANode::RangeIterator::operator==):
(WebCore::ContentExtensions::DFANode::RangeIterator::operator!=):
(WebCore::ContentExtensions::DFANode::RangeIterator::operator++):
(WebCore::ContentExtensions::DFANode::RangeIterator::first):
(WebCore::ContentExtensions::DFANode::RangeIterator::last):
(WebCore::ContentExtensions::DFANode::RangeIterator::data):
(WebCore::ContentExtensions::DFANode::IterableRange::begin):
(WebCore::ContentExtensions::DFANode::IterableRange::end):
(WebCore::ContentExtensions::DFANode::hasFallbackTransition): Deleted.
(WebCore::ContentExtensions::DFANode::transitionsLength): Deleted.
(WebCore::ContentExtensions::DFANode::transitionsStart): Deleted.
(WebCore::ContentExtensions::DFANode::resetTransitions): Deleted.
(WebCore::ContentExtensions::DFANode::setHasFallbackTransitionWithoutChangingDFA): Deleted.
* contentextensions/ImmutableNFA.h:
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::first):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::last):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::data):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::range):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator*): Deleted.
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator->): Deleted.
* contentextensions/ImmutableNFANodeBuilder.h:
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::first):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::last):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::operator*): Deleted.
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::operator->): Deleted.
* contentextensions/MutableRange.h:
(WebCore::ContentExtensions::MutableRange::size): Deleted.
* contentextensions/MutableRangeList.h:
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::first):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::last):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::data):
(WebCore::ContentExtensions::MutableRangeList::extend):
(WebCore::ContentExtensions::MutableRangeList::size):
(WebCore::ContentExtensions::MutableRangeList::initializeFrom):
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::canUseFallbackTransition): Deleted.
(WebCore::ContentExtensions::findBestFallbackTarget): Deleted.
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
Since the minimizer is perfect, we get the minimal solution now,
which is really cool!</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreWebCorexcodeprojprojectpbxproj">trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAh">trunk/Source/WebCore/contentextensions/DFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFACombinercpp">trunk/Source/WebCore/contentextensions/DFACombiner.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizercpp">trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFANodeh">trunk/Source/WebCore/contentextensions/DFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsImmutableNFAh">trunk/Source/WebCore/contentextensions/ImmutableNFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsImmutableNFANodeBuilderh">trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsMutableRangeh">trunk/Source/WebCore/contentextensions/MutableRange.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsMutableRangeListh">trunk/Source/WebCore/contentextensions/MutableRangeList.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</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="#trunkSourceWebCorecontentextensionsDFANodecpp">trunk/Source/WebCore/contentextensions/DFANode.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/ChangeLog 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -1,3 +1,157 @@
</span><ins>+2015-07-06 Benjamin Poulain <benjamin@webkit.org>
+
+ [Content Extensions] Make the DFA transitions ranges instead of characters
+ https://bugs.webkit.org/show_bug.cgi?id=146575
+
+ Reviewed by Alex Christensen.
+
+ This patch changes the DFA and code using the DFA to use ranges
+ to represent the transitions between any two nodes.
+
+ This patch builds on top of the tools introduced in r186079.
+
+ The DFA structure is basically the same as ImmutableNFA but without
+ any epsilon transitions.
+
+ This patch introduces a transition iterator to make the DFA
+ compatible with the existing algorithms.
+
+ ---
+
+ The DFA combiner is rebuilt on top of MutableRangeList. Combining the transitions
+ of two nodes is one by merging the range list of each not into a common
+ MutableRangeList.
+ The data converter takes care of creating the signature of the combination.
+
+ The code got simpler since MutableRangeList does most of the work now. It is also
+ much faster.
+
+ ---
+
+ The minimizer is more intersting.
+
+ With the current algorithm, we cannot resolve overlaps between ranges. On the other
+ hand, the minimizer does not care about the symbol of the transitions if we are careful
+ to partition transitions of the same symbol together.
+
+ What I did was to turn the minimizer into a pure transition based one, BUT each
+ "symbol" is actually an unbreakable range.
+
+ The first step is to go over all the transitions of all the nodes and find the largest
+ ranges such that the alphabet of interest is covered but there is not a single intersection
+ between any two nodes (what I called "singular transitions" in the code).
+
+ This can be done efficiently with MutableRangeList.
+ A little trick there is that I also used the converter to count how many real transition
+ overlaps any singular transition.
+
+ Those singular transitions become the alphabet of our minimizer. The "symbol" of our alphabet
+ is simply the position of the singular transition in the list.
+
+ The partition of transition is created by populating each set with all the transition that
+ overlaps the symbols.
+ Note that since the partition is created on the fly, the Transition structure used for
+ repartitioning only contains the source of the transitions.
+
+ Once our transition parition has been carefuly created, we can completely forget about
+ the symbols and only work with subsets.
+
+ Since the singular transitions have no overlap (unlike fallback transitions), this new minimizer
+ will find the minimial solution for well formed input.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::memoryUsed):
+ (WebCore::ContentExtensions::printTransitions):
+ (WebCore::ContentExtensions::DFANode::actions): Deleted.
+ (WebCore::ContentExtensions::DFANode::transitions): Deleted.
+ (WebCore::ContentExtensions::DFANode::fallbackTransitionDestination): Deleted.
+ (WebCore::ContentExtensions::DFANode::changeFallbackTransition): Deleted.
+ (WebCore::ContentExtensions::DFANode::addFallbackTransition): Deleted.
+ (WebCore::ContentExtensions::DFANode::containsTransition): Deleted.
+ (WebCore::ContentExtensions::DFANode::kill): Deleted.
+ (WebCore::ContentExtensions::DFA::debugPrintDot): Deleted.
+ * contentextensions/DFA.h:
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::range):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::target):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::range):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::target):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::resetTarget):
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::ranges):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::nodeTransitionsMaxBytecodeSize):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
+ * contentextensions/DFACombiner.cpp:
+ (WebCore::ContentExtensions::DFAMerger::TargetConverter::convert):
+ (WebCore::ContentExtensions::DFAMerger::TargetConverter::extend):
+ (WebCore::ContentExtensions::DFAMerger::TargetConverter::setHalfSignature):
+ (WebCore::ContentExtensions::DFAMerger::merge):
+ (WebCore::ContentExtensions::DFAMerger::getOrCreateCombinedNode):
+ (WebCore::ContentExtensions::DFAMerger::setHalfSignature): Deleted.
+ (WebCore::ContentExtensions::DFAMerger::populateTransitions): Deleted.
+ (WebCore::ContentExtensions::DFAMerger::populateFromFallbackTransitions): Deleted.
+ (WebCore::ContentExtensions::DFAMerger::createTransitions): Deleted.
+ (WebCore::ContentExtensions::DFAMerger::createFallbackTransitionIfNeeded): Deleted.
+ * contentextensions/DFAMinimizer.cpp:
+ (WebCore::ContentExtensions::DFAMinimizer::minimize):
+ * contentextensions/DFANode.cpp: Added.
+ (WebCore::ContentExtensions::DFANode::actions):
+ (WebCore::ContentExtensions::DFANode::containsTransition):
+ (WebCore::ContentExtensions::DFANode::kill):
+ (WebCore::ContentExtensions::DFANode::canUseFallbackTransition):
+ (WebCore::ContentExtensions::DFANode::bestFallbackTarget):
+ * contentextensions/DFANode.h:
+ (WebCore::ContentExtensions::CharRange::size):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator*):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator==):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator!=):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::operator++):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::first):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::last):
+ (WebCore::ContentExtensions::DFANode::ConstRangeIterator::data):
+ (WebCore::ContentExtensions::DFANode::IterableConstRange::begin):
+ (WebCore::ContentExtensions::DFANode::IterableConstRange::end):
+ (WebCore::ContentExtensions::DFANode::transitions):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::operator*):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::operator==):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::operator!=):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::operator++):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::first):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::last):
+ (WebCore::ContentExtensions::DFANode::RangeIterator::data):
+ (WebCore::ContentExtensions::DFANode::IterableRange::begin):
+ (WebCore::ContentExtensions::DFANode::IterableRange::end):
+ (WebCore::ContentExtensions::DFANode::hasFallbackTransition): Deleted.
+ (WebCore::ContentExtensions::DFANode::transitionsLength): Deleted.
+ (WebCore::ContentExtensions::DFANode::transitionsStart): Deleted.
+ (WebCore::ContentExtensions::DFANode::resetTransitions): Deleted.
+ (WebCore::ContentExtensions::DFANode::setHasFallbackTransitionWithoutChangingDFA): Deleted.
+ * contentextensions/ImmutableNFA.h:
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::first):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::last):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::data):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::range):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator*): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator->): Deleted.
+ * contentextensions/ImmutableNFANodeBuilder.h:
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::first):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::last):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::operator*): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::FakeRangeIterator::operator->): Deleted.
+ * contentextensions/MutableRange.h:
+ (WebCore::ContentExtensions::MutableRange::size): Deleted.
+ * contentextensions/MutableRangeList.h:
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::first):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::last):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::data):
+ (WebCore::ContentExtensions::MutableRangeList::extend):
+ (WebCore::ContentExtensions::MutableRangeList::size):
+ (WebCore::ContentExtensions::MutableRangeList::initializeFrom):
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ (WebCore::ContentExtensions::canUseFallbackTransition): Deleted.
+ (WebCore::ContentExtensions::findBestFallbackTarget): Deleted.
+
</ins><span class="cx"> 2015-07-06 Timothy Hatcher <timothy@apple.com>
</span><span class="cx">
</span><span class="cx"> Fix ASSERT causing crashes in Inspector tests on the bots.
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -1031,6 +1031,7 @@
</span><span class="cx"> 26C15CF71857E15E00F15C03 /* ResourceHandleCFURLConnectionDelegateWithOperationQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 26C15CF51857E15D00F15C03 /* ResourceHandleCFURLConnectionDelegateWithOperationQueue.h */; };
</span><span class="cx"> 26C17A3E1491D2D400D12BA2 /* FileSystemIOS.h in Headers */ = {isa = PBXBuildFile; fileRef = 26C17A3C1491D2D400D12BA2 /* FileSystemIOS.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26C17A3F1491D2D400D12BA2 /* FileSystemIOS.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26C17A3D1491D2D400D12BA2 /* FileSystemIOS.mm */; };
</span><ins>+ 26D4E8461B42539D00E033A2 /* DFANode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26D4E8451B42539D00E033A2 /* DFANode.cpp */; };
</ins><span class="cx"> 26E944D81AC4B2DD007B85B5 /* CombinedURLFilters.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26E944D41AC4B2DD007B85B5 /* CombinedURLFilters.cpp */; };
</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 */; };
</span><span class="lines">@@ -8180,6 +8181,7 @@
</span><span class="cx"> 26C15CF51857E15D00F15C03 /* ResourceHandleCFURLConnectionDelegateWithOperationQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ResourceHandleCFURLConnectionDelegateWithOperationQueue.h; sourceTree = "<group>"; };
</span><span class="cx"> 26C17A3C1491D2D400D12BA2 /* FileSystemIOS.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FileSystemIOS.h; sourceTree = "<group>"; };
</span><span class="cx"> 26C17A3D1491D2D400D12BA2 /* FileSystemIOS.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FileSystemIOS.mm; sourceTree = "<group>"; };
</span><ins>+ 26D4E8451B42539D00E033A2 /* DFANode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFANode.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 26E944D41AC4B2DD007B85B5 /* CombinedURLFilters.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CombinedURLFilters.cpp; sourceTree = "<group>"; };
</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="lines">@@ -15706,6 +15708,7 @@
</span><span class="cx"> 26A807831B18F97700E219BE /* DFACombiner.h */,
</span><span class="cx"> 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */,
</span><span class="cx"> 26A517FC1AB92238006335DF /* DFAMinimizer.h */,
</span><ins>+ 26D4E8451B42539D00E033A2 /* DFANode.cpp */,
</ins><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><span class="cx"> 26F756B21B3B66F70005DD79 /* ImmutableNFA.h */,
</span><span class="cx"> 26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */,
</span><span class="lines">@@ -30250,6 +30253,7 @@
</span><span class="cx"> B2A1F2AD0CEF0ABF00442F6A /* SVGGlyphElement.cpp in Sources */,
</span><span class="cx"> 24D912BD13CA9A9700D21915 /* SVGGlyphRefElement.cpp in Sources */,
</span><span class="cx"> B2227A290D00BF220071B782 /* SVGGradientElement.cpp in Sources */,
</span><ins>+ 26D4E8461B42539D00E033A2 /* DFANode.cpp in Sources */,
</ins><span class="cx"> B2227AB50D00BF220071B782 /* SVGGraphicsElement.cpp in Sources */,
</span><span class="cx"> 650FBF2A0D9AF047008FC292 /* SVGHKernElement.cpp in Sources */,
</span><span class="cx"> B25599A30D00D8BA00BB825C /* SVGImage.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -46,89 +46,11 @@
</span><span class="cx"> {
</span><span class="cx"> return sizeof(DFA)
</span><span class="cx"> + actions.capacity() * sizeof(uint64_t)
</span><del>- + transitionCharacters.capacity() * sizeof(uint8_t)
</del><ins>+ + transitionRanges.capacity() * sizeof(CharRange)
</ins><span class="cx"> + transitionDestinations.capacity() * sizeof(uint32_t)
</span><span class="cx"> + nodes.capacity() * sizeof(DFANode);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-// FIXME: Make DFANode.cpp.
-Vector<uint64_t> DFANode::actions(const DFA& dfa) const
-{
- // FIXME: Use iterators instead of copying the Vector elements.
- Vector<uint64_t> vector;
- vector.reserveInitialCapacity(m_actionsLength);
- for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
- vector.uncheckedAppend(dfa.actions[i]);
- return vector;
-}
-
-Vector<std::pair<uint8_t, uint32_t>> DFANode::transitions(const DFA& dfa) const
-{
- // FIXME: Use iterators instead of copying the Vector elements.
- Vector<std::pair<uint8_t, uint32_t>> vector;
- vector.reserveInitialCapacity(transitionsLength());
- for (uint32_t i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i)
- vector.uncheckedAppend(std::make_pair(dfa.transitionCharacters[i], dfa.transitionDestinations[i]));
- return vector;
-}
-
-uint32_t DFANode::fallbackTransitionDestination(const DFA& dfa) const
-{
- RELEASE_ASSERT(hasFallbackTransition());
-
- // If there is a fallback transition, it is just after the other transitions and has an invalid ASCII character to mark it as a fallback transition.
- ASSERT(dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] == std::numeric_limits<uint8_t>::max());
- return dfa.transitionDestinations[m_transitionsStart + m_transitionsLength];
-}
-
-void DFANode::changeFallbackTransition(DFA& dfa, uint32_t newDestination)
-{
- RELEASE_ASSERT(hasFallbackTransition());
- ASSERT_WITH_MESSAGE(dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] == std::numeric_limits<uint8_t>::max(), "When changing a fallback transition, the fallback transition should already be marked as such");
- dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] = std::numeric_limits<uint8_t>::max();
- dfa.transitionDestinations[m_transitionsStart + m_transitionsLength] = newDestination;
-}
-
-void DFANode::addFallbackTransition(DFA& dfa, uint32_t destination)
-{
- RELEASE_ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());
- RELEASE_ASSERT_WITH_MESSAGE(dfa.transitionCharacters.size() == m_transitionsStart + m_transitionsLength, "Adding a fallback transition should only happen if the node is at the end");
- dfa.transitionCharacters.append(std::numeric_limits<uint8_t>::max());
- dfa.transitionDestinations.append(destination);
- ASSERT(!(m_flags & HasFallbackTransition));
- m_flags |= HasFallbackTransition;
-}
-
-bool DFANode::containsTransition(uint8_t transition, DFA& dfa)
-{
- // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.
- ASSERT(m_transitionsLength <= 128);
- for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
- if (dfa.transitionCharacters[i] == transition)
- return true;
- }
- return false;
-}
-
-void DFANode::kill(DFA& dfa)
-{
- ASSERT(m_flags != IsKilled);
- m_flags = IsKilled; // Killed nodes don't have any other flags.
-
- // Invalidate the now-unused memory in the DFA to make finding bugs easier.
- for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
- dfa.transitionCharacters[i] = std::numeric_limits<uint8_t>::max();
- dfa.transitionDestinations[i] = std::numeric_limits<uint32_t>::max();
- }
- for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
- dfa.actions[i] = std::numeric_limits<uint64_t>::max();
-
- m_actionsStart = 0;
- m_actionsLength = 0;
- m_transitionsStart = 0;
- m_transitionsLength = 0;
-};
-
</del><span class="cx"> void DFA::minimize()
</span><span class="cx"> {
</span><span class="cx"> DFAMinimizer::minimize(*this);
</span><span class="lines">@@ -165,17 +87,18 @@
</span><span class="cx"> const DFANode& sourceNode = dfa.nodes[sourceNodeId];
</span><span class="cx"> auto transitions = sourceNode.transitions(dfa);
</span><span class="cx">
</span><del>- if (transitions.isEmpty() && !sourceNode.hasFallbackTransition())
</del><ins>+ if (transitions.begin() == transitions.end())
</ins><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> HashMap<unsigned, Vector<uint16_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
</span><span class="cx">
</span><span class="cx"> // First, we build the list of transitions coming to each target node.
</span><span class="cx"> for (const auto& transition : transitions) {
</span><del>- unsigned target = transition.second;
</del><ins>+ unsigned target = transition.target();
</ins><span class="cx"> transitionsPerTarget.add(target, Vector<uint16_t>());
</span><span class="cx">
</span><del>- transitionsPerTarget.find(target)->value.append(transition.first);
</del><ins>+ for (unsigned offset = 0; offset < transition.range().size(); ++offset)
+ transitionsPerTarget.find(target)->value.append(transition.first() + offset);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Then we go over each one an display the ranges one by one.
</span><span class="lines">@@ -202,9 +125,6 @@
</span><span class="cx">
</span><span class="cx"> dataLogF("\"];\n");
</span><span class="cx"> }
</span><del>-
- if (sourceNode.hasFallbackTransition())
- dataLogF(" %d -> %d [label=\"[fallback]\"];\n", sourceNodeId, sourceNode.fallbackTransitionDestination(dfa));
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void DFA::debugPrintDot() const
</span><span class="lines">@@ -228,17 +148,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Vector<unsigned> correspondingNFANodes = nodes[i].correspondingNFANodes;
- if (!correspondingNFANodes.isEmpty()) {
- dataLogF("<BR/>NFA Nodes: ");
- for (unsigned correspondingDFANodeIndex = 0; correspondingDFANodeIndex < correspondingNFANodes.size(); ++correspondingDFANodeIndex) {
- if (correspondingDFANodeIndex)
- dataLogF(", ");
- dataLogF("%d", correspondingNFANodes[correspondingDFANodeIndex]);
- }
- }
- dataLogF(">]");
-
</del><span class="cx"> if (!actions.isEmpty())
</span><span class="cx"> dataLogF(" [shape=doublecircle]");
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -47,16 +47,41 @@
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #endif
</span><del>-
</del><ins>+
+ Vector<DFANode> nodes;
</ins><span class="cx"> Vector<uint64_t> actions;
</span><del>- Vector<uint8_t> transitionCharacters;
</del><ins>+ Vector<CharRange> transitionRanges;
</ins><span class="cx"> Vector<uint32_t> transitionDestinations;
</span><del>- Vector<DFANode> nodes;
</del><span class="cx"> unsigned root { 0 };
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+inline const CharRange& DFANode::ConstRangeIterator::range() const
+{
+ return dfa.transitionRanges[position];
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+inline uint32_t DFANode::ConstRangeIterator::target() const
+{
+ return dfa.transitionDestinations[position];
+}
+
+inline const CharRange& DFANode::RangeIterator::range() const
+{
+ return dfa.transitionRanges[position];
+}
+
+inline uint32_t DFANode::RangeIterator::target() const
+{
+ return dfa.transitionDestinations[position];
+}
+
+inline void DFANode::RangeIterator::resetTarget(uint32_t newTarget)
+{
+ dfa.transitionDestinations[position] = newTarget;
+}
+
+}
+
</ins><span class="cx"> } // namespace WebCore
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(CONTENT_EXTENSIONS)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -204,10 +204,18 @@
</span><span class="cx"> memset(destinations, 0xff, sizeof(destinations));
</span><span class="cx"> const uint32_t noDestination = std::numeric_limits<uint32_t>::max();
</span><span class="cx">
</span><del>- for (const auto& pair : node.transitions(m_dfa)) {
- RELEASE_ASSERT(pair.first < WTF_ARRAY_LENGTH(destinations));
- ASSERT_WITH_MESSAGE(destinations[pair.first] == noDestination, "Transitions should be unique");
- destinations[pair.first] = pair.second;
</del><ins>+ bool canUseFallbackTransition = node.canUseFallbackTransition(m_dfa);
+ uint32_t fallbackTransitionTarget = std::numeric_limits<uint32_t>::max();
+ if (canUseFallbackTransition)
+ fallbackTransitionTarget = node.bestFallbackTarget(m_dfa);
+
+ for (const auto& transition : node.transitions(m_dfa)) {
+ uint32_t targetNodeIndex = transition.target();
+ if (canUseFallbackTransition && fallbackTransitionTarget == targetNodeIndex)
+ continue;
+
+ for (uint16_t i = transition.range().first; i <= transition.range().last; ++i)
+ destinations[i] = targetNodeIndex;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector<Range> ranges;
</span><span class="lines">@@ -215,7 +223,6 @@
</span><span class="cx"> bool hasRangeMin = false;
</span><span class="cx"> for (uint8_t i = 0; i < 128; i++) {
</span><span class="cx"> if (hasRangeMin) {
</span><del>- ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition() && node.fallbackTransitionDestination(m_dfa) == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
</del><span class="cx"> if (destinations[i] != destinations[rangeMin]) {
</span><span class="cx">
</span><span class="cx"> // This is the end of a range. Check if it can be case insensitive.
</span><span class="lines">@@ -260,6 +267,7 @@
</span><span class="cx"> // If a range goes to 127, there will never be values higher than it, so checking for case-insensitive ranges would always fail.
</span><span class="cx"> ranges.append(Range(rangeMin, 127, destinations[rangeMin], true));
</span><span class="cx"> }
</span><ins>+
</ins><span class="cx"> return ranges;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -289,7 +297,7 @@
</span><span class="cx"> unsigned size = 0;
</span><span class="cx"> for (const auto& range : ranges(node))
</span><span class="cx"> size += checkForRangeMaxBytecodeSize(range);
</span><del>- if (node.hasFallbackTransition())
</del><ins>+ if (node.canUseFallbackTransition(m_dfa))
</ins><span class="cx"> size += sizeof(DFABytecodeInstruction::Jump) + sizeof(uint32_t);
</span><span class="cx"> else
</span><span class="cx"> size += instructionSizeWithArguments(DFABytecodeInstruction::Terminate);
</span><span class="lines">@@ -303,8 +311,8 @@
</span><span class="cx">
</span><span class="cx"> for (const auto& range : ranges(node))
</span><span class="cx"> compileCheckForRange(nodeIndex, range);
</span><del>- if (node.hasFallbackTransition())
- emitJump(nodeIndex, node.fallbackTransitionDestination(m_dfa));
</del><ins>+ if (node.canUseFallbackTransition(m_dfa))
+ emitJump(nodeIndex, node.bestFallbackTarget(m_dfa));
</ins><span class="cx"> else
</span><span class="cx"> emitTerminate();
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFACombinercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFACombiner.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFACombiner.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFACombiner.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx"> #include "config.h"
</span><span class="cx"> #include "DFACombiner.h"
</span><span class="cx">
</span><ins>+#include "MutableRangeList.h"
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx">
</span><span class="lines">@@ -34,6 +35,35 @@
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><span class="cx"> class DFAMerger {
</span><ins>+ typedef MutableRangeList<char, uint64_t, 128> CombinedTransitionsMutableRangeList;
+
+ enum class WhichDFA {
+ A,
+ B
+ };
+
+ template<WhichDFA whichDFA>
+ struct TargetConverter {
+ uint64_t convert(uint32_t target)
+ {
+ uint64_t value = 0xffffffffffffffff;
+ extend(value, target);
+ return value;
+ }
+
+ void extend(uint64_t& destination, uint32_t target)
+ {
+ setHalfSignature(destination, target);
+ }
+ private:
+ void setHalfSignature(uint64_t& signature, uint32_t value)
+ {
+ unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
+ uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
+ signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
+ }
+ };
+
</ins><span class="cx"> public:
</span><span class="cx"> DFAMerger(const DFA& a, const DFA& b)
</span><span class="cx"> : m_dfaA(a)
</span><span class="lines">@@ -49,32 +79,40 @@
</span><span class="cx"> uint64_t rootSignature = signatureForIndices(m_dfaA.root, m_dfaB.root);
</span><span class="cx"> getOrCreateCombinedNode(rootSignature);
</span><span class="cx">
</span><ins>+ CombinedTransitionsMutableRangeList combinedTransitions;
</ins><span class="cx"> while (!m_unprocessedNodes.isEmpty()) {
</span><del>- memset(m_transitionTargets, 0xff, sizeof(m_transitionTargets));
</del><ins>+ combinedTransitions.clear();
</ins><span class="cx">
</span><span class="cx"> uint64_t unprocessedNode = m_unprocessedNodes.takeLast();
</span><span class="cx">
</span><del>- // We cannot cache the source node itself since we modify the machine. We only manipulate the IDs.
- uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
-
- // Populate the unique transitions.
</del><span class="cx"> uint32_t indexA = extractIndexA(unprocessedNode);
</span><del>- if (indexA != invalidNodeIndex)
- populateTransitions<WhichDFA::A>(indexA);
</del><ins>+ if (indexA != invalidNodeIndex) {
+ const DFANode& nodeA = m_dfaA.nodes[indexA];
+ auto transitionsA = nodeA.transitions(m_dfaA);
+ TargetConverter<WhichDFA::A> converterA;
+ combinedTransitions.extend(transitionsA.begin(), transitionsA.end(), converterA);
+ }
</ins><span class="cx">
</span><span class="cx"> uint32_t indexB = extractIndexB(unprocessedNode);
</span><del>- if (indexB != invalidNodeIndex)
- populateTransitions<WhichDFA::B>(indexB);
</del><ins>+ if (indexB != invalidNodeIndex) {
+ const DFANode& nodeB = m_dfaB.nodes[indexB];
+ auto transitionsB = nodeB.transitions(m_dfaB);
+ TargetConverter<WhichDFA::B> converterB;
+ combinedTransitions.extend(transitionsB.begin(), transitionsB.end(), converterB);
+ }
</ins><span class="cx">
</span><del>- // Spread the fallback transitions over the unique transitions and keep a reference to the fallback transition.
- uint64_t fallbackTransitionSignature = signatureForIndices(invalidNodeIndex, invalidNodeIndex);
- if (indexA != invalidNodeIndex)
- populateFromFallbackTransitions<WhichDFA::A>(indexA, fallbackTransitionSignature);
- if (indexB != invalidNodeIndex)
- populateFromFallbackTransitions<WhichDFA::B>(indexB, fallbackTransitionSignature);
</del><ins>+ unsigned transitionsStart = m_output.transitionRanges.size();
+ for (const auto& range : combinedTransitions) {
+ unsigned targetNodeId = getOrCreateCombinedNode(range.data);
+ m_output.transitionRanges.append({ range.first, range.last });
+ m_output.transitionDestinations.append(targetNodeId);
+ }
+ unsigned transitionsEnd = m_output.transitionRanges.size();
+ unsigned transitionsLength = transitionsEnd - transitionsStart;
</ins><span class="cx">
</span><del>- createTransitions(sourceNodeId);
- createFallbackTransitionIfNeeded(sourceNodeId, fallbackTransitionSignature);
</del><ins>+ uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
+ DFANode& dfaSourceNode = m_output.nodes[sourceNodeId];
+ dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
</ins><span class="cx"> }
</span><span class="cx"> return m_output;
</span><span class="cx"> }
</span><span class="lines">@@ -82,11 +120,6 @@
</span><span class="cx"> private:
</span><span class="cx"> uint32_t invalidNodeIndex = 0xffffffff;
</span><span class="cx">
</span><del>- enum class WhichDFA {
- A,
- B
- };
-
</del><span class="cx"> static uint64_t signatureForIndices(uint32_t aIndex, uint32_t bIndex)
</span><span class="cx"> {
</span><span class="cx"> return static_cast<uint64_t>(aIndex) << 32 | bIndex;
</span><span class="lines">@@ -122,14 +155,14 @@
</span><span class="cx"> uint32_t actionsStart = node.actionsStart();
</span><span class="cx"> uint32_t actionsEnd = actionsStart + node.actionsLength();
</span><span class="cx"> for (uint32_t i = actionsStart; i < actionsEnd; ++i)
</span><del>- actions.add(m_dfaA.actions[i]);
</del><ins>+ actions.add(m_dfaA.actions[i]);
</ins><span class="cx"> }
</span><span class="cx"> if (indexB != invalidNodeIndex) {
</span><span class="cx"> const DFANode& node = m_dfaB.nodes[indexB];
</span><span class="cx"> uint32_t actionsStart = node.actionsStart();
</span><span class="cx"> uint32_t actionsEnd = actionsStart + node.actionsLength();
</span><span class="cx"> for (uint32_t i = actionsStart; i < actionsEnd; ++i)
</span><del>- actions.add(m_dfaB.actions[i]);
</del><ins>+ actions.add(m_dfaB.actions[i]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> uint32_t actionsStart = m_output.actions.size();
</span><span class="lines">@@ -142,87 +175,11 @@
</span><span class="cx"> return newNodeIndex;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- template<WhichDFA whichDFA>
- void setHalfSignature(uint64_t& signature, uint32_t value)
- {
- unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
- uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
- signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
- }
-
- template<WhichDFA whichDFA>
- void populateTransitions(uint32_t nodeIndex)
- {
- const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
- const DFANode& node = dfa.nodes[nodeIndex];
- uint32_t transitionsStart = node.transitionsStart();
- uint32_t transitionsEnd = transitionsStart + node.transitionsLength();
-
- // Extract transitions.
- for (uint32_t transitionIndex = transitionsStart; transitionIndex < transitionsEnd; ++transitionIndex) {
- uint8_t transitionCharacter = dfa.transitionCharacters[transitionIndex];
- RELEASE_ASSERT(transitionCharacter < WTF_ARRAY_LENGTH(m_transitionTargets));
-
- uint32_t transitionDestination = dfa.transitionDestinations[transitionIndex];
- setHalfSignature<whichDFA>(m_transitionTargets[transitionCharacter], transitionDestination);
- }
- }
-
- template<WhichDFA whichDFA>
- void populateFromFallbackTransitions(uint32_t nodeIndex, uint64_t& fallbackTransitionSignature)
- {
- const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
- const DFANode& node = dfa.nodes[nodeIndex];
- if (!node.hasFallbackTransition())
- return;
-
- uint32_t fallbackTarget = node.fallbackTransitionDestination(dfa);
- setHalfSignature<whichDFA>(fallbackTransitionSignature, fallbackTarget);
-
- // Spread the fallback over transitions where the other has something and we don't.
- for (unsigned i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
- uint64_t& targetSignature = m_transitionTargets[i];
-
- uint32_t otherTarget = (whichDFA == WhichDFA::A) ? extractIndexB(targetSignature) : extractIndexA(targetSignature);
- uint32_t selfTarget = (whichDFA == WhichDFA::A) ? extractIndexA(targetSignature) : extractIndexB(targetSignature);
-
- if (otherTarget != invalidNodeIndex && selfTarget == invalidNodeIndex)
- setHalfSignature<whichDFA>(targetSignature, fallbackTarget);
- }
- }
-
- void createTransitions(uint32_t sourceNodeId)
- {
- // Create transitions out of the source node, creating new nodes as needed.
- uint32_t transitionsStart = m_output.transitionCharacters.size();
- for (uint8_t i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
- uint64_t signature = m_transitionTargets[i];
- if (signature == signatureForIndices(invalidNodeIndex, invalidNodeIndex))
- continue;
- uint32_t nodeId = getOrCreateCombinedNode(signature);
- m_output.transitionCharacters.append(i);
- m_output.transitionDestinations.append(nodeId);
- }
- uint32_t transitionsEnd = m_output.transitionCharacters.size();
- uint8_t transitionsLength = static_cast<uint8_t>(transitionsEnd - transitionsStart);
-
- m_output.nodes[sourceNodeId].setTransitions(transitionsStart, transitionsLength);
- }
-
- void createFallbackTransitionIfNeeded(uint32_t sourceNodeId, uint64_t fallbackTransitionSignature)
- {
- if (fallbackTransitionSignature != signatureForIndices(invalidNodeIndex, invalidNodeIndex)) {
- uint32_t nodeId = getOrCreateCombinedNode(fallbackTransitionSignature);
- m_output.nodes[sourceNodeId].addFallbackTransition(m_output, nodeId);
- }
- }
-
</del><span class="cx"> const DFA& m_dfaA;
</span><span class="cx"> const DFA& m_dfaB;
</span><span class="cx"> DFA m_output;
</span><span class="cx"> HashMap<uint64_t, uint32_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> m_nodeMapping;
</span><span class="cx"> Vector<uint64_t> m_unprocessedNodes;
</span><del>- uint64_t m_transitionTargets[128];
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> void DFACombiner::combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "DFA.h"
</span><span class="cx"> #include "DFANode.h"
</span><ins>+#include "MutableRangeList.h"
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx"> #include <wtf/StringHasher.h>
</span><span class="lines">@@ -40,79 +41,32 @@
</span><span class="cx">
</span><span class="cx"> namespace {
</span><span class="cx">
</span><del>-// simplifyTransitions() tries to collapse individual transitions into fallback transitions.
-// After simplifyTransitions(), you can also make the assumption that a fallback transition target will never be
-// also the target of an individual transition.
-static void simplifyTransitions(DFA& dfa)
</del><ins>+template<typename VectorType, typename Iterable, typename Function>
+static inline void iterateIntersections(const VectorType& singularTransitionsFirsts, const Iterable& iterableTransitionList, const Function& intersectionHandler)
</ins><span class="cx"> {
</span><del>- for (DFANode& dfaNode : dfa.nodes) {
- bool addingFallback = false;
- uint32_t newFallbackDestination = std::numeric_limits<uint32_t>::max();
- if (!dfaNode.hasFallbackTransition()
- && ((dfaNode.transitionsLength() == 126 && !dfaNode.containsTransition(0, dfa))
- || (dfaNode.transitionsLength() == 127 && dfaNode.containsTransition(0, dfa)))) {
- unsigned bestTarget = std::numeric_limits<unsigned>::max();
- unsigned bestTargetScore = 0;
- HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;
- for (const auto& transition : dfaNode.transitions(dfa)) {
- if (!transition.first)
- continue;
</del><ins>+ ASSERT(!singularTransitionsFirsts.isEmpty());
+ auto otherIterator = iterableTransitionList.begin();
+ auto otherEnd = iterableTransitionList.end();
</ins><span class="cx">
</span><del>- unsigned transitionTarget = transition.second;
- auto addResult = targetHistogram.add(transitionTarget, 1);
- if (!addResult.isNewEntry)
- addResult.iterator->value++;
</del><ins>+ if (otherIterator == otherEnd)
+ return;
</ins><span class="cx">
</span><del>- if (addResult.iterator->value > bestTargetScore) {
- bestTargetScore = addResult.iterator->value;
- bestTarget = transitionTarget;
- }
- }
- ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");
</del><ins>+ unsigned singularTransitionsLength = singularTransitionsFirsts.size();
+ unsigned singularTransitionsFirstsIndex = 0;
+ for (; otherIterator != otherEnd; ++otherIterator) {
+ auto firstCharacter = otherIterator.first();
+ while (singularTransitionsFirstsIndex < singularTransitionsLength
+ && singularTransitionsFirsts[singularTransitionsFirstsIndex] != firstCharacter)
+ ++singularTransitionsFirstsIndex;
</ins><span class="cx">
</span><del>- newFallbackDestination = bestTarget;
- addingFallback = true;
- }
-
- // Use the same location to write new transitions possibly followed by unused memory.
- // We can do this because we are always decreasing the amount of memory used.
- // We will probably need something like setHasFallbackTransitionWithoutChangingDFA to do that.
</del><ins>+ intersectionHandler(singularTransitionsFirstsIndex, otherIterator);
+ ++singularTransitionsFirstsIndex;
</ins><span class="cx">
</span><del>- unsigned oldFallbackTransition = std::numeric_limits<uint32_t>::max();
- bool hadFallbackTransition = dfaNode.hasFallbackTransition();
- if (hadFallbackTransition)
- oldFallbackTransition = dfaNode.fallbackTransitionDestination(dfa);
-
- newFallbackDestination = (newFallbackDestination == std::numeric_limits<uint32_t>::max() ? oldFallbackTransition : newFallbackDestination);
- ASSERT(!addingFallback || (newFallbackDestination != std::numeric_limits<uint32_t>::max() && oldFallbackTransition == std::numeric_limits<uint32_t>::max()));
- bool willHaveFallback = newFallbackDestination != std::numeric_limits<uint32_t>::max();
- dfaNode.setHasFallbackTransitionWithoutChangingDFA(willHaveFallback);
-
- if (willHaveFallback) {
- Vector<std::pair<uint8_t, uint32_t>> transitions = dfaNode.transitions(dfa);
- unsigned availableSlotCount = transitions.size() + hadFallbackTransition;
- for (unsigned i = 0; i < transitions.size(); ++i) {
- if (transitions[i].second == newFallbackDestination)
- transitions.remove(i--);
- }
-
- RELEASE_ASSERT(transitions.size() + willHaveFallback <= availableSlotCount);
-
- unsigned firstSlot = dfaNode.transitionsStart();
- dfaNode.resetTransitions(firstSlot, transitions.size());
- for (unsigned i = 0; i < transitions.size(); ++i) {
- dfa.transitionCharacters[firstSlot + i] = transitions[i].first;
- dfa.transitionDestinations[firstSlot + i] = transitions[i].second;
- }
- for (unsigned i = transitions.size(); i < availableSlotCount; ++i) {
- // Invalidate now-unused memory to make finding bugs easier.
- dfa.transitionCharacters[firstSlot + i] = std::numeric_limits<uint8_t>::max();
- dfa.transitionDestinations[firstSlot + i] = std::numeric_limits<uint32_t>::max();
- }
- if (willHaveFallback) {
- dfa.transitionCharacters[firstSlot + transitions.size()] = std::numeric_limits<uint8_t>::max();
- dfa.transitionDestinations[firstSlot + transitions.size()] = newFallbackDestination;
- }
</del><ins>+ auto lastCharacter = otherIterator.last();
+ while (singularTransitionsFirstsIndex < singularTransitionsLength
+ && singularTransitionsFirsts[singularTransitionsFirstsIndex] <= lastCharacter) {
+ intersectionHandler(singularTransitionsFirstsIndex, otherIterator);
+ ++singularTransitionsFirstsIndex;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -137,8 +91,33 @@
</span><span class="cx"> m_sets.append(SetDescriptor({ 0, size, 0 }));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void markElementInCurrentGeneration(unsigned elementIndex)
</del><ins>+ void reserveUninitializedCapacity(unsigned elementCount)
</ins><span class="cx"> {
</span><ins>+ m_partitionedElements.resize(elementCount);
+ m_elementPositionInPartitionedNodes.resize(elementCount);
+ m_elementToSetMap.resize(elementCount);
+ }
+
+ void addSetUnchecked(unsigned start, unsigned size)
+ {
+ m_sets.append(SetDescriptor { start, size, 0 });
+ }
+
+ void setElementUnchecked(unsigned elementIndex, unsigned positionInPartition, unsigned setIndex)
+ {
+ ASSERT(setIndex < m_sets.size());
+ m_partitionedElements[positionInPartition] = elementIndex;
+ m_elementPositionInPartitionedNodes[elementIndex] = positionInPartition;
+ m_elementToSetMap[elementIndex] = setIndex;
+ }
+
+ unsigned startOffsetOfSet(unsigned setIndex) const
+ {
+ return m_sets[setIndex].start;
+ }
+
+ ALWAYS_INLINE void markElementInCurrentGeneration(unsigned elementIndex)
+ {
</ins><span class="cx"> // Swap the node with the first unmarked node.
</span><span class="cx"> unsigned setIndex = m_elementToSetMap[elementIndex];
</span><span class="cx"> SetDescriptor& setDescriptor = m_sets[setIndex];
</span><span class="lines">@@ -238,45 +217,66 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> // List of sets.
</span><del>- Vector<SetDescriptor> m_sets;
</del><ins>+ Vector<SetDescriptor, 0, UnsafeVectorOverflow> m_sets;
</ins><span class="cx">
</span><span class="cx"> // All the element indices such that two elements of the same set never have a element of a different set between them.
</span><del>- Vector<unsigned> m_partitionedElements;
</del><ins>+ Vector<unsigned, 0, UnsafeVectorOverflow> m_partitionedElements;
</ins><span class="cx">
</span><span class="cx"> // Map elementIndex->position in the partitionedElements.
</span><del>- Vector<unsigned> m_elementPositionInPartitionedNodes;
</del><ins>+ Vector<unsigned, 0, UnsafeVectorOverflow> m_elementPositionInPartitionedNodes;
</ins><span class="cx">
</span><span class="cx"> // Map elementIndex->SetIndex.
</span><del>- Vector<unsigned> m_elementToSetMap;
</del><ins>+ Vector<unsigned, 0, UnsafeVectorOverflow> m_elementToSetMap;
</ins><span class="cx">
</span><span class="cx"> // List of sets with any marked node. Each set can appear at most once.
</span><span class="cx"> // FIXME: find a good inline size for this.
</span><del>- Vector<unsigned, 128> m_setsMarkedInCurrentGeneration;
</del><ins>+ Vector<unsigned, 128, UnsafeVectorOverflow> m_setsMarkedInCurrentGeneration;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> class FullGraphPartition {
</span><ins>+ typedef MutableRangeList<char, uint32_t, 128> SingularTransitionsMutableRangeList;
</ins><span class="cx"> public:
</span><span class="cx"> FullGraphPartition(const DFA& dfa)
</span><span class="cx"> {
</span><span class="cx"> m_nodePartition.initialize(dfa.nodes.size());
</span><span class="cx">
</span><del>- m_flattenedTransitionsStartOffsetPerNode.resize(dfa.nodes.size());
- for (unsigned& counter : m_flattenedTransitionsStartOffsetPerNode)
- counter = 0;
</del><ins>+ SingularTransitionsMutableRangeList singularTransitions;
+ CounterConverter counterConverter;
+ for (const DFANode& node : dfa.nodes) {
+ if (node.isKilled())
+ continue;
+ auto transitions = node.transitions(dfa);
+ singularTransitions.extend(transitions.begin(), transitions.end(), counterConverter);
+ }
</ins><span class="cx">
</span><del>- m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfa.nodes.size());
- for (unsigned& counter : m_flattenedFallbackTransitionsStartOffsetPerNode)
- counter = 0;
</del><ins>+ // Count the number of transition for each singular range. This will give us the bucket size
+ // for the transition partition, where transitions are partitioned by "symbol".
+ unsigned rangeIndexAccumulator = 0;
+ for (const auto& transition : singularTransitions) {
+ m_transitionPartition.addSetUnchecked(rangeIndexAccumulator, transition.data);
+ rangeIndexAccumulator += transition.data;
+ }
</ins><span class="cx">
</span><span class="cx"> // Count the number of incoming transitions per node.
</span><del>- for (const DFANode& dfaNode : dfa.nodes) {
- for (const auto& transition : dfaNode.transitions(dfa))
- ++m_flattenedTransitionsStartOffsetPerNode[transition.second];
- if (dfaNode.hasFallbackTransition())
- ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransitionDestination(dfa)];
</del><ins>+ m_flattenedTransitionsStartOffsetPerNode.resize(dfa.nodes.size());
+ memset(m_flattenedTransitionsStartOffsetPerNode.data(), 0, m_flattenedTransitionsStartOffsetPerNode.size() * sizeof(unsigned));
+
+ Vector<char, 0, UnsafeVectorOverflow> singularTransitionsFirsts;
+ singularTransitionsFirsts.reserveInitialCapacity(singularTransitions.m_ranges.size());
+ for (const auto& transition : singularTransitions)
+ singularTransitionsFirsts.uncheckedAppend(transition.first);
+
+ for (const DFANode& node : dfa.nodes) {
+ if (node.isKilled())
+ continue;
+ auto transitions = node.transitions(dfa);
+ iterateIntersections(singularTransitionsFirsts, transitions, [&](unsigned, const DFANode::ConstRangeIterator& origin) {
+ uint32_t targetNodeIndex = origin.target();
+ ++m_flattenedTransitionsStartOffsetPerNode[targetNodeIndex];
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // Accumulate the offsets.
</del><ins>+ // Accumulate the offsets. This gives us the start position of each bucket.
</ins><span class="cx"> unsigned transitionAccumulator = 0;
</span><span class="cx"> for (unsigned i = 0; i < m_flattenedTransitionsStartOffsetPerNode.size(); ++i) {
</span><span class="cx"> unsigned transitionsCountForNode = m_flattenedTransitionsStartOffsetPerNode[i];
</span><span class="lines">@@ -284,65 +284,42 @@
</span><span class="cx"> transitionAccumulator += transitionsCountForNode;
</span><span class="cx"> }
</span><span class="cx"> unsigned flattenedTransitionsSize = transitionAccumulator;
</span><ins>+ ASSERT_WITH_MESSAGE(flattenedTransitionsSize == rangeIndexAccumulator, "The number of transitions should be the same, regardless of how they are arranged in buckets.");
</ins><span class="cx">
</span><del>- unsigned fallbackTransitionAccumulator = 0;
- for (unsigned i = 0; i < m_flattenedFallbackTransitionsStartOffsetPerNode.size(); ++i) {
- unsigned fallbackTransitionsCountForNode = m_flattenedFallbackTransitionsStartOffsetPerNode[i];
- m_flattenedFallbackTransitionsStartOffsetPerNode[i] = fallbackTransitionAccumulator;
- fallbackTransitionAccumulator += fallbackTransitionsCountForNode;
- }
- unsigned flattenedFallbackTransitionsSize = fallbackTransitionAccumulator;
</del><ins>+ m_transitionPartition.reserveUninitializedCapacity(flattenedTransitionsSize);
</ins><span class="cx">
</span><span class="cx"> // Next, let's fill the transition table and set up the size of each group at the same time.
</span><span class="cx"> m_flattenedTransitionsSizePerNode.resize(dfa.nodes.size());
</span><span class="cx"> for (unsigned& counter : m_flattenedTransitionsSizePerNode)
</span><span class="cx"> counter = 0;
</span><del>-
- m_flattenedFallbackTransitionsSizePerNode.resize(dfa.nodes.size());
- for (unsigned& counter : m_flattenedFallbackTransitionsSizePerNode)
- counter = 0;
-
</del><span class="cx"> m_flattenedTransitions.resize(flattenedTransitionsSize);
</span><span class="cx">
</span><del>- m_flattenedFallbackTransitions.resize(flattenedFallbackTransitionsSize);
</del><ins>+ Vector<uint32_t> transitionPerRangeOffset(m_transitionPartition.size());
+ memset(transitionPerRangeOffset.data(), 0, transitionPerRangeOffset.size() * sizeof(uint32_t));
</ins><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < dfa.nodes.size(); ++i) {
</span><del>- const DFANode& dfaNode = dfa.nodes[i];
- for (const auto& transition : dfaNode.transitions(dfa)) {
- unsigned targetNodeIndex = transition.second;
</del><ins>+ const DFANode& node = dfa.nodes[i];
+ if (node.isKilled())
+ continue;
</ins><span class="cx">
</span><ins>+ auto transitions = node.transitions(dfa);
+ iterateIntersections(singularTransitionsFirsts, transitions, [&](unsigned singularTransitonIndex, const DFANode::ConstRangeIterator& origin) {
+ uint32_t targetNodeIndex = origin.target();
+
</ins><span class="cx"> unsigned start = m_flattenedTransitionsStartOffsetPerNode[targetNodeIndex];
</span><span class="cx"> unsigned offset = m_flattenedTransitionsSizePerNode[targetNodeIndex];
</span><ins>+ unsigned positionInFlattenedTransitions = start + offset;
+ m_flattenedTransitions[positionInFlattenedTransitions] = Transition({ i });
</ins><span class="cx">
</span><del>- m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.first });
</del><ins>+ uint32_t& inRangeOffset = transitionPerRangeOffset[singularTransitonIndex];
+ unsigned positionInTransitionPartition = m_transitionPartition.startOffsetOfSet(singularTransitonIndex) + inRangeOffset;
+ ++inRangeOffset;
</ins><span class="cx">
</span><del>- ++m_flattenedTransitionsSizePerNode[targetNodeIndex];
- }
- if (dfaNode.hasFallbackTransition()) {
- unsigned targetNodeIndex = dfaNode.fallbackTransitionDestination(dfa);
</del><ins>+ m_transitionPartition.setElementUnchecked(positionInFlattenedTransitions, positionInTransitionPartition, singularTransitonIndex);
</ins><span class="cx">
</span><del>- unsigned start = m_flattenedFallbackTransitionsStartOffsetPerNode[targetNodeIndex];
- unsigned offset = m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];
-
- m_flattenedFallbackTransitions[start + offset] = i;
- ++m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];
- }
</del><ins>+ ++m_flattenedTransitionsSizePerNode[targetNodeIndex];
+ });
</ins><span class="cx"> }
</span><del>-
- // Create the initial partition of transition. Each character differentiating a transiton
- // from an other gets its own set in the partition.
- m_transitionPartition.initialize(m_flattenedTransitions.size());
- for (uint16_t i = 0; i < 128; ++i) {
- for (unsigned transitionIndex = 0; transitionIndex < m_flattenedTransitions.size(); ++transitionIndex) {
- const Transition& transition = m_flattenedTransitions[transitionIndex];
- if (transition.character == i)
- m_transitionPartition.markElementInCurrentGeneration(transitionIndex);
- }
- m_transitionPartition.refineGeneration([](unsigned) { });
- }
-
- // Fallback partitions are considered as a special type of differentiator, we don't split them initially.
- m_fallbackTransitionPartition.initialize(m_flattenedFallbackTransitions.size());
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void markNode(unsigned nodeIndex)
</span><span class="lines">@@ -359,17 +336,10 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < incomingTransitionsSizeForNode; ++i)
</span><span class="cx"> m_transitionPartition.markElementInCurrentGeneration(incomingTransitionsStartForNode + i);
</span><del>-
- unsigned incomingFallbackTransitionsStartForNode = m_flattenedFallbackTransitionsStartOffsetPerNode[nodeIndex];
- unsigned incomingFallbackTransitionsSizeForNode = m_flattenedFallbackTransitionsSizePerNode[nodeIndex];
-
- for (unsigned i = 0; i < incomingFallbackTransitionsSizeForNode; ++i)
- m_fallbackTransitionPartition.markElementInCurrentGeneration(incomingFallbackTransitionsStartForNode + i);
</del><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> // We only need to split the transitions, we handle the new sets through the main loop.
</span><span class="cx"> m_transitionPartition.refineGeneration([](unsigned) { });
</span><del>- m_fallbackTransitionPartition.refineGeneration([](unsigned) { });
</del><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -386,23 +356,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void splitByFallbackTransitions()
- {
- ASSERT_WITH_MESSAGE(m_nextTransitionSetToProcess || !m_transitionPartition.size(), "We can only distinguish nodes by fallback transition *after* all other transitions are covered. Doing otherwise would be incorrect since the unique transitions from 2 nodes could cover all possible transitions.");
-
- for (unsigned fallbackTransitionSetIndex = 0; fallbackTransitionSetIndex < m_fallbackTransitionPartition.size(); ++fallbackTransitionSetIndex) {
-
- m_fallbackTransitionPartition.iterateSet(fallbackTransitionSetIndex, [&](unsigned transitionIndex) {
- unsigned sourceNodeIndex = m_flattenedFallbackTransitions[transitionIndex];
- m_nodePartition.markElementInCurrentGeneration(sourceNodeIndex);
- });
- refinePartitions();
-
- // Any new split need to spread to all the unique transition that can reach the two new sets.
- splitByUniqueTransitions();
- }
- }
-
</del><span class="cx"> unsigned nodeReplacement(unsigned nodeIndex)
</span><span class="cx"> {
</span><span class="cx"> unsigned setIndex = m_nodePartition.setIndex(nodeIndex);
</span><span class="lines">@@ -412,21 +365,26 @@
</span><span class="cx"> private:
</span><span class="cx"> struct Transition {
</span><span class="cx"> unsigned source;
</span><del>- unsigned target;
- uint16_t character;
</del><span class="cx"> };
</span><span class="cx">
</span><del>- Vector<unsigned> m_flattenedTransitionsStartOffsetPerNode;
- Vector<unsigned> m_flattenedTransitionsSizePerNode;
- Vector<unsigned> m_flattenedFallbackTransitionsStartOffsetPerNode;
- Vector<unsigned> m_flattenedFallbackTransitionsSizePerNode;
</del><ins>+ struct CounterConverter {
+ uint32_t convert(uint32_t)
+ {
+ return 1;
+ }
</ins><span class="cx">
</span><del>- Vector<Transition> m_flattenedTransitions;
- Vector<unsigned> m_flattenedFallbackTransitions;
</del><ins>+ void extend(uint32_t& destination, uint32_t)
+ {
+ ++destination;
+ }
+ };
</ins><span class="cx">
</span><ins>+ Vector<unsigned, 0, UnsafeVectorOverflow> m_flattenedTransitionsStartOffsetPerNode;
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_flattenedTransitionsSizePerNode;
+ Vector<Transition, 0, UnsafeVectorOverflow> m_flattenedTransitions;
+
</ins><span class="cx"> Partition m_nodePartition;
</span><span class="cx"> Partition m_transitionPartition;
</span><del>- Partition m_fallbackTransitionPartition;
</del><span class="cx">
</span><span class="cx"> unsigned m_nextTransitionSetToProcess { 0 };
</span><span class="cx"> };
</span><span class="lines">@@ -494,8 +452,6 @@
</span><span class="cx">
</span><span class="cx"> void DFAMinimizer::minimize(DFA& dfa)
</span><span class="cx"> {
</span><del>- simplifyTransitions(dfa);
-
</del><span class="cx"> FullGraphPartition fullGraphPartition(dfa);
</span><span class="cx">
</span><span class="cx"> // Unlike traditional minimization final states can be differentiated by their action.
</span><span class="lines">@@ -520,21 +476,12 @@
</span><span class="cx"> // Use every splitter to refine the node partitions.
</span><span class="cx"> fullGraphPartition.splitByUniqueTransitions();
</span><span class="cx">
</span><del>- // At this stage, we know that no pair of state can be distinguished by the individual transitions. They can still
- // be distinguished by their fallback transitions.
- //
- // For example, two states [1, 2] can both have a transition on 'x' to a state [3], but each have fallback transition
- // to different states [4] and [5].
- //
- // Here, we distinguish such cases and at each stage refine the new discovered sets by their individual transitions.
- fullGraphPartition.splitByFallbackTransitions();
-
</del><span class="cx"> Vector<unsigned> relocationVector;
</span><span class="cx"> relocationVector.reserveInitialCapacity(dfa.nodes.size());
</span><span class="cx"> for (unsigned i = 0; i < dfa.nodes.size(); ++i)
</span><span class="cx"> relocationVector.uncheckedAppend(i);
</span><span class="cx">
</span><del>- // Kill the useless nodes and keep track of the new node transitions should point to.
</del><ins>+ // Update all the transitions.
</ins><span class="cx"> for (unsigned i = 0; i < dfa.nodes.size(); ++i) {
</span><span class="cx"> unsigned replacement = fullGraphPartition.nodeReplacement(i);
</span><span class="cx"> if (i != replacement) {
</span><span class="lines">@@ -543,19 +490,18 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ dfa.root = relocationVector[dfa.root];
</ins><span class="cx"> for (DFANode& node : dfa.nodes) {
</span><del>- auto nodeTransitions = node.transitions(dfa);
- for (unsigned i = 0; i < node.transitionsLength(); ++i)
- dfa.transitionDestinations[node.transitionsStart() + i] = relocationVector[nodeTransitions[i].second];
- if (node.hasFallbackTransition())
- node.changeFallbackTransition(dfa, relocationVector[node.fallbackTransitionDestination(dfa)]);
- }
</del><ins>+ if (node.isKilled())
+ continue;
</ins><span class="cx">
</span><del>- // After minimizing, there is no guarantee individual transition are still poiting to different states.
- // The state pointed by one individual transition and the fallback states may have been merged.
- simplifyTransitions(dfa);
-
- dfa.root = relocationVector[dfa.root];
</del><ins>+ for (auto& transition : node.transitions(dfa)) {
+ uint32_t target = transition.target();
+ uint32_t relocatedTarget = relocationVector[target];
+ if (target != relocatedTarget)
+ transition.resetTarget(relocatedTarget);
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodecpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/DFANode.cpp (0 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFANode.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -0,0 +1,147 @@
</span><ins>+/*
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFANode.h"
+
+#include "DFA.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+Vector<uint64_t> DFANode::actions(const DFA& dfa) const
+{
+ // FIXME: Use iterators instead of copying the Vector elements.
+ Vector<uint64_t> vector;
+ vector.reserveInitialCapacity(m_actionsLength);
+ for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
+ vector.uncheckedAppend(dfa.actions[i]);
+ return vector;
+}
+
+bool DFANode::containsTransition(char transition, const DFA& dfa) const
+{
+ // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.
+ ASSERT(m_transitionsLength <= 128);
+ for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
+ if (dfa.transitionRanges[i].first <= transition
+ && dfa.transitionRanges[i].last >= transition)
+ return true;
+ }
+ return false;
+}
+
+void DFANode::kill(DFA& dfa)
+{
+ ASSERT(m_flags != IsKilled);
+ m_flags = IsKilled; // Killed nodes don't have any other flags.
+
+ // Invalidate the now-unused memory in the DFA to make finding bugs easier.
+ for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
+ dfa.transitionRanges[i] = { -1, -1 };
+ dfa.transitionDestinations[i] = std::numeric_limits<uint32_t>::max();
+ }
+ for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
+ dfa.actions[i] = std::numeric_limits<uint64_t>::max();
+
+ m_actionsStart = 0;
+ m_actionsLength = 0;
+ m_transitionsStart = 0;
+ m_transitionsLength = 0;
+};
+
+bool DFANode::canUseFallbackTransition(const DFA& dfa) const
+{
+ // Transitions can contain '\0' if the expression has a end-of-line marker.
+ // Fallback transitions cover 1-127. We have to be careful with the first.
+
+ IterableConstRange iterableTransitions = transitions(dfa);
+ auto iterator = iterableTransitions.begin();
+ auto end = iterableTransitions.end();
+ if (iterator == end)
+ return false;
+
+ char lastSeenCharacter = 0;
+ if (!iterator.first()) {
+ lastSeenCharacter = iterator.last();
+ if (lastSeenCharacter == 127)
+ return true;
+ ++iterator;
+ }
+
+ for (;iterator != end; ++iterator) {
+ ASSERT(iterator.first() > lastSeenCharacter);
+ if (iterator.first() != lastSeenCharacter + 1)
+ return false;
+
+ if (iterator.range().last == 127)
+ return true;
+ lastSeenCharacter = iterator.last();
+ }
+ return false;
+}
+
+uint32_t DFANode::bestFallbackTarget(const DFA& dfa) const
+{
+ ASSERT(canUseFallbackTransition(dfa));
+
+ HashMap<uint32_t, unsigned, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> histogram;
+
+ IterableConstRange iterableTransitions = transitions(dfa);
+ auto iterator = iterableTransitions.begin();
+ auto end = iterableTransitions.end();
+ ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition.");
+
+ if (!iterator.first() && !iterator.last())
+ ++iterator;
+ ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition.");
+
+ uint32_t bestTarget = iterator.target();
+ unsigned bestTargetScore = !iterator.range().first ? iterator.range().size() - 1 : iterator.range().size();
+ histogram.add(bestTarget, bestTargetScore);
+ ++iterator;
+
+ for (;iterator != end; ++iterator) {
+ unsigned rangeSize = iterator.range().size();
+ uint32_t target = iterator.target();
+ auto addResult = histogram.add(target, rangeSize);
+ if (!addResult.isNewEntry)
+ addResult.iterator->value += rangeSize;
+ if (addResult.iterator->value > bestTargetScore) {
+ bestTargetScore = addResult.iterator->value;
+ bestTarget = target;
+ }
+ }
+ return bestTarget;
+}
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -38,27 +38,112 @@
</span><span class="cx">
</span><span class="cx"> struct DFA;
</span><span class="cx">
</span><ins>+struct CharRange {
+ char first;
+ char last;
+ unsigned size() const { return last - first + 1; }
+};
+
</ins><span class="cx"> // A DFANode abstract the transition table out of a DFA state. If a state is accepting, the DFANode also have
</span><span class="cx"> // the actions for that state.
</span><span class="cx"> class DFANode {
</span><span class="cx"> public:
</span><ins>+ struct ConstRangeIterator {
+ const DFA& dfa;
+ uint32_t position;
+
+ const ConstRangeIterator& operator*() const { return *this; }
+
+ bool operator==(const ConstRangeIterator& other) const
+ {
+ ASSERT(&dfa == &other.dfa);
+ return position == other.position;
+ }
+ bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
+
+ ConstRangeIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+
+ const CharRange& range() const;
+ uint32_t target() const;
+
+ char first() const { return range().first; }
+ char last() const { return range().last; }
+ uint32_t data() const { return target(); }
+ };
+
+ struct IterableConstRange {
+ const DFA& dfa;
+ uint32_t rangesStart;
+ uint32_t rangesEnd;
+
+ ConstRangeIterator begin() const { return { dfa, rangesStart }; }
+ ConstRangeIterator end() const { return { dfa, rangesEnd }; }
+ };
+
+ IterableConstRange transitions(const DFA& dfa) const
+ {
+ return IterableConstRange { dfa, m_transitionsStart, m_transitionsStart + m_transitionsLength };
+ }
+
+ struct RangeIterator {
+ DFA& dfa;
+ uint32_t position;
+
+ RangeIterator& operator*() { return *this; }
+
+ bool operator==(const RangeIterator& other) const
+ {
+ ASSERT(&dfa == &other.dfa);
+ return position == other.position;
+ }
+ bool operator!=(const RangeIterator& other) const { return !(*this == other); }
+
+ RangeIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+
+ const CharRange& range() const;
+ uint32_t target() const;
+ void resetTarget(uint32_t);
+
+ char first() const { return range().first; }
+ char last() const { return range().last; }
+ uint32_t data() const { return target(); }
+ };
+
+ struct IterableRange {
+ DFA& dfa;
+ uint32_t rangesStart;
+ uint32_t rangesEnd;
+
+ RangeIterator begin() const { return { dfa, rangesStart }; }
+ RangeIterator end() const { return { dfa, rangesEnd }; }
+ };
+
+ IterableRange transitions(DFA& dfa)
+ {
+ return IterableRange { dfa, m_transitionsStart, m_transitionsStart + m_transitionsLength };
+ }
+
</ins><span class="cx"> // FIXME: Stop minimizing killed nodes and add ASSERT(!isKilled()) in many functions here.
</span><span class="cx"> void kill(DFA&);
</span><span class="cx"> Vector<uint64_t> actions(const DFA&) const;
</span><del>- Vector<std::pair<uint8_t, uint32_t>> transitions(const DFA&) const;
- uint32_t fallbackTransitionDestination(const DFA&) const;
- void addFallbackTransition(DFA&, uint32_t destination);
- bool containsTransition(uint8_t, DFA&);
- void changeFallbackTransition(DFA&, uint32_t newDestination);
</del><ins>+ bool containsTransition(char, const DFA&) const;
</ins><span class="cx">
</span><span class="cx"> bool isKilled() const { return m_flags & IsKilled; }
</span><del>- bool hasFallbackTransition() const { return m_flags & HasFallbackTransition; }
</del><span class="cx"> bool hasActions() const { return !!m_actionsLength; }
</span><del>- uint8_t transitionsLength() const { return m_transitionsLength; }
</del><span class="cx"> uint16_t actionsLength() const { return m_actionsLength; }
</span><span class="cx"> uint32_t actionsStart() const { return m_actionsStart; }
</span><del>- uint32_t transitionsStart() const { return m_transitionsStart; }
-
</del><ins>+
+ bool canUseFallbackTransition(const DFA&) const;
+ uint32_t bestFallbackTarget(const DFA&) const;
+
</ins><span class="cx"> void setActions(uint32_t start, uint16_t length)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(!m_actionsStart);
</span><span class="lines">@@ -73,22 +158,7 @@
</span><span class="cx"> m_transitionsStart = start;
</span><span class="cx"> m_transitionsLength = length;
</span><span class="cx"> }
</span><del>- void resetTransitions(uint32_t start, uint16_t length)
- {
- m_transitionsStart = start;
- m_transitionsLength = length;
- }
- void setHasFallbackTransitionWithoutChangingDFA(bool shouldHaveFallbackTransition)
- {
- if (shouldHaveFallbackTransition)
- m_flags |= HasFallbackTransition;
- else
- m_flags &= ~HasFallbackTransition;
- }
-
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- Vector<unsigned> correspondingNFANodes;
-#endif
</del><ins>+
</ins><span class="cx"> private:
</span><span class="cx"> uint32_t m_actionsStart { 0 };
</span><span class="cx"> uint32_t m_transitionsStart { 0 };
</span><span class="lines">@@ -96,17 +166,10 @@
</span><span class="cx"> uint8_t m_transitionsLength { 0 };
</span><span class="cx">
</span><span class="cx"> uint8_t m_flags { 0 };
</span><del>- const uint8_t HasFallbackTransition = 0x01;
- const uint8_t IsKilled = 0x02;
</del><ins>+ const uint8_t IsKilled = 0x01;
</ins><span class="cx"> };
</span><span class="cx">
</span><del>-// FIXME: Pack this down to 12.
-// It's probably already 12 on ARMv7.
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
-COMPILE_ASSERT(sizeof(DFANode) <= 16 + sizeof(Vector<unsigned>), Keep the DFANodes small);
-#else
</del><span class="cx"> COMPILE_ASSERT(sizeof(DFANode) <= 16, Keep the DFANodes small);
</span><del>-#endif
</del><span class="cx">
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsImmutableNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ImmutableNFA.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ImmutableNFA.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFA.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -93,9 +93,6 @@
</span><span class="cx"> const ImmutableNFA& immutableNFA;
</span><span class="cx"> uint32_t position;
</span><span class="cx">
</span><del>- const ImmutableRange<CharacterType>& operator*() const { return immutableNFA.transitions[position]; }
- const ImmutableRange<CharacterType>* operator->() const { return &immutableNFA.transitions[position]; }
-
</del><span class="cx"> bool operator==(const ConstRangeIterator& other) const
</span><span class="cx"> {
</span><span class="cx"> ASSERT(&immutableNFA == &other.immutableNFA);
</span><span class="lines">@@ -109,11 +106,27 @@
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ CharacterType first() const
+ {
+ return range().first;
+ }
+
+ CharacterType last() const
+ {
+ return range().last;
+ }
+
</ins><span class="cx"> IterableConstTargets data() const
</span><span class="cx"> {
</span><del>- const ImmutableRange<CharacterType>& range = immutableNFA.transitions[position];
</del><ins>+ const ImmutableRange<CharacterType>& range = this->range();
</ins><span class="cx"> return { immutableNFA, range.targetStart, range.targetEnd };
</span><span class="cx"> };
</span><ins>+
+ private:
+ const ImmutableRange<CharacterType>& range() const
+ {
+ return immutableNFA.transitions[position];
+ }
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct IterableConstRange {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsImmutableNFANodeBuilderh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -89,8 +89,8 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct FakeRangeIterator {
</span><del>- const TrivialRange& operator*() const { return range; }
- const TrivialRange* operator->() const { return &range; }
</del><ins>+ CharacterType first() const { return range.first; }
+ CharacterType last() const { return range.last; }
</ins><span class="cx"> uint32_t data() const { return targetId; }
</span><span class="cx"> bool operator==(const FakeRangeIterator& other)
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsMutableRangeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/MutableRange.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/MutableRange.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/MutableRange.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -89,8 +89,6 @@
</span><span class="cx"> uint32_t nextRangeIndex;
</span><span class="cx"> CharacterType first;
</span><span class="cx"> CharacterType last;
</span><del>-
- CharacterType size() const { return last - first; }
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsMutableRangeListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/MutableRangeList.h (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/MutableRangeList.h 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/MutableRangeList.h 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -48,6 +48,10 @@
</span><span class="cx"> const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
</span><span class="cx"> const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
</span><span class="cx">
</span><ins>+ CharacterType first() const { return rangeList.m_ranges[index].first; }
+ CharacterType last() const { return rangeList.m_ranges[index].last; }
+ CharacterType data() const { return rangeList.m_ranges[index].data; }
+
</ins><span class="cx"> bool operator==(const ConstIterator& other) const
</span><span class="cx"> {
</span><span class="cx"> ASSERT(&rangeList == &other.rangeList);
</span><span class="lines">@@ -99,21 +103,21 @@
</span><span class="cx"> uint32_t lastSelfRangeIndex = 0;
</span><span class="cx"> uint32_t selfRangeIndex = 0;
</span><span class="cx">
</span><del>- auto otherRangeOffset = otherIterator->first; // To get the right type :)
</del><ins>+ auto otherRangeOffset = otherIterator.first(); // To get the right type :)
</ins><span class="cx"> otherRangeOffset = 0;
</span><span class="cx">
</span><span class="cx"> do {
</span><span class="cx"> TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
</span><span class="cx">
</span><span class="cx"> // First, we move forward until we find something interesting.
</span><del>- if (activeSelfRange->last < otherIterator->first + otherRangeOffset) {
</del><ins>+ if (activeSelfRange->last < otherIterator.first() + otherRangeOffset) {
</ins><span class="cx"> lastSelfRangeIndex = selfRangeIndex;
</span><span class="cx"> selfRangeIndex = activeSelfRange->nextRangeIndex;
</span><span class="cx"> reachedSelfEnd = !selfRangeIndex;
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><del>- if (otherIterator->last < activeSelfRange->first) {
- insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator->first + otherRangeOffset, otherIterator->last, dataConverter.convert(otherIterator.data()));
</del><ins>+ if (otherIterator.last() < activeSelfRange->first) {
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
</ins><span class="cx">
</span><span class="cx"> ++otherIterator;
</span><span class="cx"> otherRangeOffset = 0;
</span><span class="lines">@@ -126,24 +130,24 @@
</span><span class="cx"> // But we don't know how they collide.
</span><span class="cx">
</span><span class="cx"> // Do we have a part on the left? Create a new range for it.
</span><del>- if (activeSelfRange->first < otherIterator->first + otherRangeOffset) {
</del><ins>+ if (activeSelfRange->first < otherIterator.first() + otherRangeOffset) {
</ins><span class="cx"> DataType copiedData = activeSelfRange->data;
</span><span class="cx"> CharacterType newRangeFirstCharacter = activeSelfRange->first;
</span><del>- activeSelfRange->first = otherIterator->first + otherRangeOffset;
- insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator->first + otherRangeOffset - 1, WTF::move(copiedData));
</del><ins>+ activeSelfRange->first = otherIterator.first() + otherRangeOffset;
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator.first() + otherRangeOffset - 1, WTF::move(copiedData));
</ins><span class="cx"> activeSelfRange = &m_ranges[selfRangeIndex];
</span><del>- } else if (otherIterator->first + otherRangeOffset < activeSelfRange->first) {
- insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator->first + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
</del><ins>+ } else if (otherIterator.first() + otherRangeOffset < activeSelfRange->first) {
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
</ins><span class="cx">
</span><span class="cx"> activeSelfRange = &m_ranges[selfRangeIndex];
</span><del>- ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator->first, "The offset must move forward or we could get stuck on this operation.");
- otherRangeOffset = activeSelfRange->first - otherIterator->first;
</del><ins>+ ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator.first(), "The offset must move forward or we could get stuck on this operation.");
+ otherRangeOffset = activeSelfRange->first - otherIterator.first();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Here, we know both ranges start at the same point, we need to create the part that intersect
</span><span class="cx"> // and merge the data.
</span><span class="cx">
</span><del>- if (activeSelfRange->last == otherIterator->last) {
</del><ins>+ if (activeSelfRange->last == otherIterator.last()) {
</ins><span class="cx"> // If they finish together, things are really easy: we just add B to A.
</span><span class="cx"> dataConverter.extend(activeSelfRange->data, otherIterator.data());
</span><span class="cx">
</span><span class="lines">@@ -156,15 +160,15 @@
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- if (activeSelfRange->last > otherIterator->last) {
</del><ins>+ if (activeSelfRange->last > otherIterator.last()) {
</ins><span class="cx"> // If A is bigger than B, we add a merged version and move A to the right.
</span><span class="cx">
</span><span class="cx"> CharacterType combinedPartStart = activeSelfRange->first;
</span><del>- activeSelfRange->first = otherIterator->last + 1;
</del><ins>+ activeSelfRange->first = otherIterator.last() + 1;
</ins><span class="cx">
</span><span class="cx"> DataType combinedData = activeSelfRange->data;
</span><span class="cx"> dataConverter.extend(combinedData, otherIterator.data());
</span><del>- insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator->last, WTF::move(combinedData));
</del><ins>+ insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator.last(), WTF::move(combinedData));
</ins><span class="cx">
</span><span class="cx"> ++otherIterator;
</span><span class="cx"> otherRangeOffset = 0;
</span><span class="lines">@@ -172,22 +176,27 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // If we reached here, B ends after A. We merge the intersection and move on.
</span><del>- ASSERT(otherIterator->last > activeSelfRange->last);
</del><ins>+ ASSERT(otherIterator.last() > activeSelfRange->last);
</ins><span class="cx"> dataConverter.extend(activeSelfRange->data, otherIterator.data());
</span><span class="cx">
</span><del>- otherRangeOffset = activeSelfRange->last - otherIterator->first + 1;
</del><ins>+ otherRangeOffset = activeSelfRange->last - otherIterator.first() + 1;
</ins><span class="cx"> lastSelfRangeIndex = selfRangeIndex;
</span><span class="cx"> selfRangeIndex = activeSelfRange->nextRangeIndex;
</span><span class="cx"> reachedSelfEnd = !selfRangeIndex;
</span><span class="cx"> } while (!reachedSelfEnd && otherIterator != otherEnd);
</span><span class="cx">
</span><span class="cx"> while (otherIterator != otherEnd) {
</span><del>- lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator->first + otherRangeOffset, otherIterator->last, dataConverter.convert(otherIterator.data()));
</del><ins>+ lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
</ins><span class="cx"> otherRangeOffset = 0;
</span><span class="cx"> ++otherIterator;
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ unsigned size() const
+ {
+ return m_ranges.size();
+ }
+
</ins><span class="cx"> bool isEmpty() const
</span><span class="cx"> {
</span><span class="cx"> return m_ranges.isEmpty();
</span><span class="lines">@@ -241,8 +250,8 @@
</span><span class="cx"> do {
</span><span class="cx"> m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
</span><span class="cx"> loopCounter + 1,
</span><del>- otherIterator->first,
- otherIterator->last));
</del><ins>+ otherIterator.first(),
+ otherIterator.last()));
</ins><span class="cx"> ++loopCounter;
</span><span class="cx"> ++otherIterator;
</span><span class="cx"> } while (otherIterator != otherEnd);
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -336,73 +336,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static inline bool canUseFallbackTransition(const PreallocatedNFANodeRangeList& rangeList)
-{
- // Transitions can contains "0" if the expression has a end-of-line marker.
- // Fallback transitions cover 1-127. We have to be careful with the first.
-
- auto iterator = rangeList.begin();
- auto end = rangeList.end();
- if (iterator == end)
- return false;
-
- char lastSeenCharacter = 0;
- if (!iterator->first) {
- lastSeenCharacter = iterator->last;
- if (lastSeenCharacter == 127)
- return true;
- ++iterator;
- }
-
- for (;iterator != end; ++iterator) {
- ASSERT(iterator->first > lastSeenCharacter);
- if (iterator->first != lastSeenCharacter + 1)
- return false;
-
- if (iterator->last == 127)
- return true;
- lastSeenCharacter = iterator->last;
- }
- return false;
-}
-
-static inline uint32_t findBestFallbackTarget(const PreallocatedNFANodeRangeList& rangeList, const Vector<unsigned, 128>& rangeToTarget)
-{
- ASSERT(canUseFallbackTransition(rangeList));
-
- HashMap<uint32_t, unsigned, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> histogram;
-
- unsigned rangeToTargetIndex = 0;
- auto iterator = rangeList.begin();
- auto end = rangeList.end();
- ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition.");
-
- if (!iterator->first && !iterator->last) {
- ++iterator;
- ++rangeToTargetIndex;
- }
- ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition.");
-
- uint32_t bestTarget = rangeToTarget[rangeToTargetIndex];
- unsigned bestTargetScore = !iterator->first ? iterator->size() - 1 : iterator->size();
- histogram.add(bestTarget, bestTargetScore);
- ++iterator;
- ++rangeToTargetIndex;
-
- for (;iterator != end; ++iterator, ++rangeToTargetIndex) {
- unsigned rangeSize = iterator->size();
- uint32_t target = rangeToTarget[rangeToTargetIndex];
- auto addResult = histogram.add(target, rangeSize);
- if (!addResult.isNewEntry)
- addResult.iterator->value += rangeSize;
- if (addResult.iterator->value > bestTargetScore) {
- bestTargetScore = addResult.iterator->value;
- bestTarget = target;
- }
- }
- return bestTarget;
-}
-
</del><span class="cx"> static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const NFA& nfa, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
</span><span class="cx"> {
</span><span class="cx"> NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfa, nfaNodeSet);
</span><span class="lines">@@ -432,46 +365,24 @@
</span><span class="cx"> unprocessedNodes.append(addResult.iterator->impl());
</span><span class="cx">
</span><span class="cx"> PreallocatedNFANodeRangeList combinedRangeList;
</span><del>- Vector<unsigned, 128> rangeToTarget;
</del><span class="cx"> do {
</span><span class="cx"> UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
</span><span class="cx"> createCombinedTransition(combinedRangeList, *uniqueNodeIdSetImpl, nfa, nfaNodeClosures);
</span><span class="cx">
</span><del>- rangeToTarget.clear();
</del><ins>+ unsigned transitionsStart = dfa.transitionRanges.size();
</ins><span class="cx"> for (const NFANodeRange& range : combinedRangeList) {
</span><span class="cx"> unsigned targetNodeId = getOrCreateDFANode(range.data, nfa, dfa, uniqueNodeIdSetTable, unprocessedNodes);
</span><del>- rangeToTarget.append(targetNodeId);
</del><ins>+ dfa.transitionRanges.append({ range.first, range.last });
+ dfa.transitionDestinations.append(targetNodeId);
</ins><span class="cx"> }
</span><del>-
- bool useFallbackTransition = canUseFallbackTransition(combinedRangeList);
- uint32_t preferedFallbackTarget = 0;
- if (useFallbackTransition)
- preferedFallbackTarget = findBestFallbackTarget(combinedRangeList, rangeToTarget);
-
- unsigned transitionsStart = dfa.transitionCharacters.size();
- unsigned rangeToTargetIndex = 0;
-
- for (const NFANodeRange& range : combinedRangeList) {
- unsigned targetNodeId = rangeToTarget[rangeToTargetIndex];
-
- if (!(useFallbackTransition && targetNodeId == preferedFallbackTarget)) {
- for (unsigned i = range.first; i <= static_cast<unsigned>(range.last); ++i) {
- dfa.transitionCharacters.append(static_cast<uint8_t>(i));
- dfa.transitionDestinations.append(targetNodeId);
- }
- }
- ++rangeToTargetIndex;
- }
- unsigned transitionsEnd = dfa.transitionCharacters.size();
</del><ins>+ unsigned transitionsEnd = dfa.transitionRanges.size();
</ins><span class="cx"> unsigned transitionsLength = transitionsEnd - transitionsStart;
</span><ins>+
</ins><span class="cx"> unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
</span><span class="cx"> DFANode& dfaSourceNode = dfa.nodes[dfaNodeId];
</span><del>- ASSERT_WITH_MESSAGE(transitionsLength < 127, "Transitions covering the entire alphabet should use a fallback transition");
</del><span class="cx"> dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
</span><del>-
- if (useFallbackTransition)
- dfaSourceNode.addFallbackTransition(dfa, preferedFallbackTarget);
</del><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><ins>+
</ins><span class="cx"> return dfa;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Tools/ChangeLog 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -1,3 +1,15 @@
</span><ins>+2015-07-06 Benjamin Poulain <benjamin@webkit.org>
+
+ [Content Extensions] Make the DFA transitions ranges instead of characters
+ https://bugs.webkit.org/show_bug.cgi?id=146575
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+ Since the minimizer is perfect, we get the minimal solution now,
+ which is really cool!
+
</ins><span class="cx"> 2015-07-06 Brady Eidson <beidson@apple.com>
</span><span class="cx">
</span><span class="cx"> ShouldOpenExternalURLsPolicy should default to "Allow" for WK2 API loads.
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -1930,4 +1930,470 @@
</span><span class="cx"> testRequest(searchBackend, mainDocumentRequest("zzz://www.ddjjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase1)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"^(bar)*[c-e]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { }, true);
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { }, true);
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { }, true);
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("m://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("n://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"(bar)*[c-e]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { }, true);
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { }, true);
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { }, true);
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.m.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.n.xxx/"), { });
+}
+
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase2)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"^(bar)*b\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { }, true);
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("m://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("n://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"(bar)*l\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.k.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.l.xxx/"), { }, true);
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.m.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.n.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase3)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[a-m]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("m://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("n://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[a-m]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.m.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.n.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase4)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*l\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[a-m]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("k://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("l://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("m://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("n://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*l\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[a-m]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.k.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.l.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.m.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.n.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase5)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[e-h]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("i://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[e-h]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.i.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase6)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[e-h]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("i://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[e-h]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.i.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase7)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*e\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*e\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase8)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[a-e]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("i://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[a-e]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.i.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase9)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[a-e]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[a-e]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase10)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*e\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("i://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*e\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.i.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase11)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[d-f]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("g://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[d-f]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.g.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { });
+}
+
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase12)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[d-g]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("g://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[d-g]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.g.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase13)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[c-e]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[c-e]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase14)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[b-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[c-e]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("h://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[b-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[c-e]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.h.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase15)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*[c-f]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*[c-f]\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("f://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("g://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[c-f]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[c-f]\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.f.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.g.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedRangeOverlapCase16)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^(foo)*c\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^(bar)*c\"}}]");
+
+ testRequest(matchBackend, mainDocumentRequest("a://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("b://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("c://www.webkit.org/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("d://www.webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("e://www.webkit.org/"), { });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*c\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*c\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.a.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.b.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.c.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.d.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.e.xxx/"), { });
+}
+
+TEST_F(ContentExtensionTest, CombinedQuantifiedOneOrMoreRangesCase11And13)
+{
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*[c-e]+[g-i]+YYY\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[b-d]+[h-j]+YYY\"}}]");
+
+ // The interesting ranges only match between 'b' and 'k', plus a gap in 'f'.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.abyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.acyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.adyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aeyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.afyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.agyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ahyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aiyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ajyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.akyyy.xxx/"), { });
+
+ // 'b' is the first character of the second rule.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.byyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bbyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bcyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bdyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.beyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bfyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bgyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.biyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bkyyy.xxx/"), { });
+
+ // 'c' is the first character of the first rule, and it overlaps the first character of the second rule.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cbyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ccyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cdyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ceyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cfyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.chyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ciyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ckyyy.xxx/"), { });
+
+ // 'd' is in the first range of both rule. This series cover overlaps between the two rules.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddhhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.degyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dehyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dfgyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dfhyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.djyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddjjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+}
+
+TEST_F(ContentExtensionTest, CombinedQuantifiedOneOrMoreRangesCase11And13InGroups)
+{
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(foo)*([c-e])+([g-i]+YYY)\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"(bar)*[b-d]+[h-j]+YYY\"}}]");
+
+ // The interesting ranges only match between 'b' and 'k', plus a gap in 'f'.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.abyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.acyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.adyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aeyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.afyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.agyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ahyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.aiyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ajyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.akyyy.xxx/"), { });
+
+ // 'b' is the first character of the second rule.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.byyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bbyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bcyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bdyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.beyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bfyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bgyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.biyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.bkyyy.xxx/"), { });
+
+ // 'c' is the first character of the first rule, and it overlaps the first character of the second rule.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cayyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cbyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ccyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cdyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ceyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cfyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.chyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ciyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.cjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ckyyy.xxx/"), { });
+
+ // 'd' is in the first range of both rule. This series cover overlaps between the two rules.
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddgyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddhhyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector, ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.degyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dehyyy.xxx/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dfgyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.dfhyyy.xxx/"), { });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.djyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+ testRequest(searchBackend, mainDocumentRequest("zzz://www.ddjjyyy.xxx/"), { ContentExtensions::ActionType::CSSDisplayNoneSelector });
+}
+
</ins><span class="cx"> } // namespace TestWebKitAPI
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (186373 => 186374)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-06 20:51:04 UTC (rev 186373)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-06 21:06:30 UTC (rev 186374)
</span><span class="lines">@@ -83,7 +83,7 @@
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^aac", "^a.c", "^b.c"});
</span><span class="cx"> EXPECT_EQ(static_cast<size_t>(9), countLiveNodes(dfa));
</span><span class="cx"> dfa.minimize();
</span><del>- EXPECT_EQ(static_cast<size_t>(5), countLiveNodes(dfa));
</del><ins>+ EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(dfa));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator1)
</span></span></pre>
</div>
</div>
</body>
</html>