<!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>[186079] 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/186079">186079</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-06-29 12:40:12 -0700 (Mon, 29 Jun 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Make the NFA transitions range-based
https://bugs.webkit.org/show_bug.cgi?id=146338
Reviewed by Alex Christensen.
Source/WebCore:
Change the NFA to use range based transition for any kind of transition.
The fallback transition is also absorbed as ranges.
Previously, the NFA would only have single transitions and a fallback
transition for all cases not covered by single transitions.
The problem with that design was that character ranges (e.g. [a-z]) were
extended as individual transitions. Something like [^a] would cover
most of the alphabet with transitions.
When converting the NFA to DFA, the time is proportional to the number of states
multiplied by the number of transitions. With many individual transitions,
the run time was an order of magnitude higher than what we want.
This patch changes the NFA to only handle ranges of characters. A single transition
becomes a range with the character as first and last character in the range
('a' becomes 'a' to 'a').
Ranges of characters are handled direclty (e.g. [a-z] becomes a single 'a' to 'z' transition).
In the context of the state machines, ranges have identifies (the target of the transitions).
When two ranges collide, they have to be split such that each part retain its target
except the intersection that gets the union of the targets.
Handling the union of ranges efficiently is critical because we have to do
it for every NFA node in any subset when building the DFA. The helper
class that does that is MutableRange.
The union of ranges is done efficiently because of preconditions on our list of ranges:
-The ranges must be sorted.
-No range in a list can intersect any other range in the same list.
To merge two ranges, we can go over them in order and split them part by part.
It is easy to find what goes where because they are both sorted and we can
compare the characters of each to know how to move forward.
The time to merge 2 range list is proportional to O(n+m) where 'n' and 'm' are
the number of ranges in each list.
Since taking the union of two lists usually create new ranges, we have to allocate
those somewhere efficiently. To do that, MutableRange support an inline capacity,
which is used for the NFAToDFA Convertion.
---
With ranges, the NFA-to-DFA conversion changes very little:
-Each NFA nodes contains a list of ranges and each range has a list of targets.
-The subset construction select any number of NFA nodes corresponding to
a single deterministic state.
-For the subset, we can use MutableRange to merge the ranges of every
NFA node in the set. The resulting list has rangeis with targets corresponding
to the union of all the transitions.
-We go over all the ranges the same way we used to go over the transitions.
Since the DFA does not support ranges, the ranges are spread as individual
transitions + fallback transition.
---
With the efficient merging solved, we still need the actual NFA to use ranges
instead of individual transitions.
I could have used MutableRange for that but it is not the most compact
way to represent ranges that do not need merging.
Instead, the NFA uses a custom structure: ImmutableNFA. It is basically
the same thing, but in that one you cannot change a list of range
after creating it.
Consequently, the sorted ranges in ImmutableNFA are also subsequent
in memory, which is really nice to go over them efficiently
when merging ranges in the NFA-to-DFA conversion. :)
When building the NFA, we don't know all the transitions when creating
each node, BUT we know that we have very few node "unfinished" at any
time. Since we build by going depth-first in the prefix-tree, we only
have the max-depth of live nodes in the worst case.
To help building the NFA out of the prefix tree, we have
ImmutableNFANodeBuilder. It keeps all the informations about a NFA node,
but in a non-compact, mutable form. When a ImmutableNFANodeBuilder
is destroyed, it serialize the information into the immutable NFA.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::empty):
* contentextensions/DFA.h:
* contentextensions/ImmutableNFA.h: Added.
(WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator*):
(WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator->):
(WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator==):
(WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator!=):
(WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator++):
(WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::begin):
(WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::end):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator*):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator->):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator==):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator!=):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator++):
(WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::data):
(WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::begin):
(WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::end):
(WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::debugPrint):
(WebCore::ContentExtensions::ImmutableNFA::transitionsForNode):
(WebCore::ContentExtensions::ImmutableNFA::root):
(WebCore::ContentExtensions::ImmutableNFA::finalize):
(WebCore::ContentExtensions::ImmutableNFA::memoryUsed):
* contentextensions/ImmutableNFANodeBuilder.h: Added.
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::ImmutableNFANodeBuilder):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::~ImmutableNFANodeBuilder):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::addTransition):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::addEpsilonTransition):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::setActions):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::operator=):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::finalize):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkActions):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkTransitions):
(WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkEpsilonTransitions):
* contentextensions/MutableRange.h: Added.
(WebCore::ContentExtensions::MutableRange::MutableRange):
(WebCore::ContentExtensions::MutableRange::operator=):
(WebCore::ContentExtensions::MutableRange::size):
* contentextensions/MutableRangeList.h: Added.
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator*):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator->):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator==):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator!=):
(WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator++):
(WebCore::ContentExtensions::MutableRangeList::begin):
(WebCore::ContentExtensions::MutableRangeList::end):
(WebCore::ContentExtensions::MutableRangeList::appendRange):
(WebCore::ContentExtensions::MutableRangeList::extend):
(WebCore::ContentExtensions::MutableRangeList::isEmpty):
(WebCore::ContentExtensions::MutableRangeList::clear):
(WebCore::ContentExtensions::MutableRangeList::debugPrint):
(WebCore::ContentExtensions::MutableRangeList::insertBetween):
(WebCore::ContentExtensions::MutableRangeList::initializeFrom):
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::debugPrintDot):
(WebCore::ContentExtensions::NFA::NFA): Deleted.
(WebCore::ContentExtensions::NFA::createNode): Deleted.
(WebCore::ContentExtensions::NFA::memoryUsed): Deleted.
(WebCore::ContentExtensions::NFA::addTransition): Deleted.
(WebCore::ContentExtensions::NFA::addEpsilonTransition): Deleted.
(WebCore::ContentExtensions::NFA::addTransitionsOnAnyCharacter): Deleted.
(WebCore::ContentExtensions::NFA::setActions): Deleted.
(WebCore::ContentExtensions::NFA::graphSize): Deleted.
(WebCore::ContentExtensions::NFA::restoreToGraphSize): Deleted.
(WebCore::ContentExtensions::printRange): Deleted.
(WebCore::ContentExtensions::printTransitions): Deleted.
* contentextensions/NFA.h:
(WebCore::ContentExtensions::NFA::root): Deleted.
(WebCore::ContentExtensions::NFA::addRuleId): Deleted.
* contentextensions/NFANode.h:
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::epsilonClosureExcludingSelf):
(WebCore::ContentExtensions::resolveEpsilonClosures):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
(WebCore::ContentExtensions::DataConverterWithEpsilonClosure::convert):
(WebCore::ContentExtensions::DataConverterWithEpsilonClosure::extend):
(WebCore::ContentExtensions::createCombinedTransition):
(WebCore::ContentExtensions::canUseFallbackTransition):
(WebCore::ContentExtensions::findBestFallbackTarget):
(WebCore::ContentExtensions::getOrCreateDFANode):
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::populateTransitions): Deleted.
* contentextensions/NFAToDFA.h:
* contentextensions/Term.h:
(WebCore::ContentExtensions::Term::Term):
(WebCore::ContentExtensions::Term::generateGraph):
(WebCore::ContentExtensions::Term::generateSubgraphForAtom):
(WebCore::ContentExtensions::Term::Term::generateGraph): Deleted.
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
Test some new interesting cases.</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="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAh">trunk/Source/WebCore/contentextensions/DFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAcpp">trunk/Source/WebCore/contentextensions/NFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAh">trunk/Source/WebCore/contentextensions/NFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFANodeh">trunk/Source/WebCore/contentextensions/NFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAh">trunk/Source/WebCore/contentextensions/NFAToDFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsTermh">trunk/Source/WebCore/contentextensions/Term.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<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>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/ChangeLog 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -1,3 +1,186 @@
</span><ins>+2015-06-29 Benjamin Poulain <benjamin@webkit.org>
+
+ Make the NFA transitions range-based
+ https://bugs.webkit.org/show_bug.cgi?id=146338
+
+ Reviewed by Alex Christensen.
+
+ Change the NFA to use range based transition for any kind of transition.
+ The fallback transition is also absorbed as ranges.
+
+ Previously, the NFA would only have single transitions and a fallback
+ transition for all cases not covered by single transitions.
+
+ The problem with that design was that character ranges (e.g. [a-z]) were
+ extended as individual transitions. Something like [^a] would cover
+ most of the alphabet with transitions.
+ When converting the NFA to DFA, the time is proportional to the number of states
+ multiplied by the number of transitions. With many individual transitions,
+ the run time was an order of magnitude higher than what we want.
+
+ This patch changes the NFA to only handle ranges of characters. A single transition
+ becomes a range with the character as first and last character in the range
+ ('a' becomes 'a' to 'a').
+ Ranges of characters are handled direclty (e.g. [a-z] becomes a single 'a' to 'z' transition).
+
+ In the context of the state machines, ranges have identifies (the target of the transitions).
+ When two ranges collide, they have to be split such that each part retain its target
+ except the intersection that gets the union of the targets.
+
+ Handling the union of ranges efficiently is critical because we have to do
+ it for every NFA node in any subset when building the DFA. The helper
+ class that does that is MutableRange.
+
+ The union of ranges is done efficiently because of preconditions on our list of ranges:
+ -The ranges must be sorted.
+ -No range in a list can intersect any other range in the same list.
+
+ To merge two ranges, we can go over them in order and split them part by part.
+ It is easy to find what goes where because they are both sorted and we can
+ compare the characters of each to know how to move forward.
+ The time to merge 2 range list is proportional to O(n+m) where 'n' and 'm' are
+ the number of ranges in each list.
+
+ Since taking the union of two lists usually create new ranges, we have to allocate
+ those somewhere efficiently. To do that, MutableRange support an inline capacity,
+ which is used for the NFAToDFA Convertion.
+
+ ---
+
+ With ranges, the NFA-to-DFA conversion changes very little:
+ -Each NFA nodes contains a list of ranges and each range has a list of targets.
+ -The subset construction select any number of NFA nodes corresponding to
+ a single deterministic state.
+ -For the subset, we can use MutableRange to merge the ranges of every
+ NFA node in the set. The resulting list has rangeis with targets corresponding
+ to the union of all the transitions.
+ -We go over all the ranges the same way we used to go over the transitions.
+ Since the DFA does not support ranges, the ranges are spread as individual
+ transitions + fallback transition.
+
+ ---
+
+ With the efficient merging solved, we still need the actual NFA to use ranges
+ instead of individual transitions.
+
+ I could have used MutableRange for that but it is not the most compact
+ way to represent ranges that do not need merging.
+
+ Instead, the NFA uses a custom structure: ImmutableNFA. It is basically
+ the same thing, but in that one you cannot change a list of range
+ after creating it.
+
+ Consequently, the sorted ranges in ImmutableNFA are also subsequent
+ in memory, which is really nice to go over them efficiently
+ when merging ranges in the NFA-to-DFA conversion. :)
+
+ When building the NFA, we don't know all the transitions when creating
+ each node, BUT we know that we have very few node "unfinished" at any
+ time. Since we build by going depth-first in the prefix-tree, we only
+ have the max-depth of live nodes in the worst case.
+
+ To help building the NFA out of the prefix tree, we have
+ ImmutableNFANodeBuilder. It keeps all the informations about a NFA node,
+ but in a non-compact, mutable form. When a ImmutableNFANodeBuilder
+ is destroyed, it serialize the information into the immutable NFA.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::empty):
+ * contentextensions/DFA.h:
+ * contentextensions/ImmutableNFA.h: Added.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator*):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator->):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator==):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator!=):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator++):
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::begin):
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::end):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator*):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator->):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator==):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator!=):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator++):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::data):
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::begin):
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::end):
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::debugPrint):
+ (WebCore::ContentExtensions::ImmutableNFA::transitionsForNode):
+ (WebCore::ContentExtensions::ImmutableNFA::root):
+ (WebCore::ContentExtensions::ImmutableNFA::finalize):
+ (WebCore::ContentExtensions::ImmutableNFA::memoryUsed):
+ * contentextensions/ImmutableNFANodeBuilder.h: Added.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::ImmutableNFANodeBuilder):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::~ImmutableNFANodeBuilder):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addEpsilonTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::setActions):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::operator=):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::finalize):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkActions):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkTransitions):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::sinkEpsilonTransitions):
+ * contentextensions/MutableRange.h: Added.
+ (WebCore::ContentExtensions::MutableRange::MutableRange):
+ (WebCore::ContentExtensions::MutableRange::operator=):
+ (WebCore::ContentExtensions::MutableRange::size):
+ * contentextensions/MutableRangeList.h: Added.
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator*):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator->):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator==):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator!=):
+ (WebCore::ContentExtensions::MutableRangeList::ConstIterator::operator++):
+ (WebCore::ContentExtensions::MutableRangeList::begin):
+ (WebCore::ContentExtensions::MutableRangeList::end):
+ (WebCore::ContentExtensions::MutableRangeList::appendRange):
+ (WebCore::ContentExtensions::MutableRangeList::extend):
+ (WebCore::ContentExtensions::MutableRangeList::isEmpty):
+ (WebCore::ContentExtensions::MutableRangeList::clear):
+ (WebCore::ContentExtensions::MutableRangeList::debugPrint):
+ (WebCore::ContentExtensions::MutableRangeList::insertBetween):
+ (WebCore::ContentExtensions::MutableRangeList::initializeFrom):
+ * contentextensions/NFA.cpp:
+ (WebCore::ContentExtensions::NFA::debugPrintDot):
+ (WebCore::ContentExtensions::NFA::NFA): Deleted.
+ (WebCore::ContentExtensions::NFA::createNode): Deleted.
+ (WebCore::ContentExtensions::NFA::memoryUsed): Deleted.
+ (WebCore::ContentExtensions::NFA::addTransition): Deleted.
+ (WebCore::ContentExtensions::NFA::addEpsilonTransition): Deleted.
+ (WebCore::ContentExtensions::NFA::addTransitionsOnAnyCharacter): Deleted.
+ (WebCore::ContentExtensions::NFA::setActions): Deleted.
+ (WebCore::ContentExtensions::NFA::graphSize): Deleted.
+ (WebCore::ContentExtensions::NFA::restoreToGraphSize): Deleted.
+ (WebCore::ContentExtensions::printRange): Deleted.
+ (WebCore::ContentExtensions::printTransitions): Deleted.
+ * contentextensions/NFA.h:
+ (WebCore::ContentExtensions::NFA::root): Deleted.
+ (WebCore::ContentExtensions::NFA::addRuleId): Deleted.
+ * contentextensions/NFANode.h:
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::epsilonClosureExcludingSelf):
+ (WebCore::ContentExtensions::resolveEpsilonClosures):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
+ (WebCore::ContentExtensions::DataConverterWithEpsilonClosure::convert):
+ (WebCore::ContentExtensions::DataConverterWithEpsilonClosure::extend):
+ (WebCore::ContentExtensions::createCombinedTransition):
+ (WebCore::ContentExtensions::canUseFallbackTransition):
+ (WebCore::ContentExtensions::findBestFallbackTarget):
+ (WebCore::ContentExtensions::getOrCreateDFANode):
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ (WebCore::ContentExtensions::populateTransitions): Deleted.
+ * contentextensions/NFAToDFA.h:
+ * contentextensions/Term.h:
+ (WebCore::ContentExtensions::Term::Term):
+ (WebCore::ContentExtensions::Term::generateGraph):
+ (WebCore::ContentExtensions::Term::generateSubgraphForAtom):
+ (WebCore::ContentExtensions::Term::Term::generateGraph): Deleted.
+
</ins><span class="cx"> 2015-06-29 Youenn Fablet <youenn.fablet@crf.canon.fr>
</span><span class="cx">
</span><span class="cx"> Binding generator should allow using JSC::Value for "any" parameter in lieu of ScriptValue
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -1040,6 +1040,10 @@
</span><span class="cx"> 26F0C89F1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C89D1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp */; };
</span><span class="cx"> 26F0C8A01A2EC3BE002794F8 /* ContentExtensionsBackend.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F0C89E1A2EC3BE002794F8 /* ContentExtensionsBackend.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26F40D4A14904A6300CA67C4 /* EventLoopIOS.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26F40D4914904A6300CA67C4 /* EventLoopIOS.mm */; };
</span><ins>+ 26F756B01B3B65AC0005DD79 /* MutableRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F756AE1B3B65AC0005DD79 /* MutableRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 26F756B11B3B65AC0005DD79 /* MutableRangeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F756AF1B3B65AC0005DD79 /* MutableRangeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 26F756B31B3B66F70005DD79 /* ImmutableNFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F756B21B3B66F70005DD79 /* ImmutableNFA.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 26F756B51B3B68F20005DD79 /* ImmutableNFANodeBuilder.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 26F9A83818A046AC00AEB88A /* ViewportConfiguration.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F9A83618A046AC00AEB88A /* ViewportConfiguration.cpp */; };
</span><span class="cx"> 26F9A83918A046AC00AEB88A /* ViewportConfiguration.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F9A83718A046AC00AEB88A /* ViewportConfiguration.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26FAE4CC1852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26FAE4C81852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp */; };
</span><span class="lines">@@ -8181,6 +8185,10 @@
</span><span class="cx"> 26F0C89D1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionsBackend.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26F0C89E1A2EC3BE002794F8 /* ContentExtensionsBackend.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContentExtensionsBackend.h; sourceTree = "<group>"; };
</span><span class="cx"> 26F40D4914904A6300CA67C4 /* EventLoopIOS.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = EventLoopIOS.mm; sourceTree = "<group>"; };
</span><ins>+ 26F756AE1B3B65AC0005DD79 /* MutableRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MutableRange.h; sourceTree = "<group>"; };
+ 26F756AF1B3B65AC0005DD79 /* MutableRangeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MutableRangeList.h; sourceTree = "<group>"; };
+ 26F756B21B3B66F70005DD79 /* ImmutableNFA.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ImmutableNFA.h; sourceTree = "<group>"; };
+ 26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ImmutableNFANodeBuilder.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26F9A83618A046AC00AEB88A /* ViewportConfiguration.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ViewportConfiguration.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26F9A83718A046AC00AEB88A /* ViewportConfiguration.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ViewportConfiguration.h; sourceTree = "<group>"; };
</span><span class="cx"> 26FAE4C81852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ResourceHandleCFURLConnectionDelegate.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15688,6 +15696,10 @@
</span><span class="cx"> 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */,
</span><span class="cx"> 26A517FC1AB92238006335DF /* DFAMinimizer.h */,
</span><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><ins>+ 26F756B21B3B66F70005DD79 /* ImmutableNFA.h */,
+ 26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */,
+ 26F756AE1B3B65AC0005DD79 /* MutableRange.h */,
+ 26F756AF1B3B65AC0005DD79 /* MutableRangeList.h */,
</ins><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */,
</span><span class="cx"> 269397231A4A5B6400E8349D /* NFA.h */,
</span><span class="cx"> 269397201A4A412F00E8349D /* NFANode.h */,
</span><span class="lines">@@ -24240,6 +24252,7 @@
</span><span class="cx"> 62CD325A1157E57C0063B0A7 /* CustomEvent.h in Headers */,
</span><span class="cx"> A8CB413E0E8633FD0032C4F0 /* DashArray.h in Headers */,
</span><span class="cx"> A80E6D0B0A1989CA007FB8C5 /* DashboardRegion.h in Headers */,
</span><ins>+ 26F756B01B3B65AC0005DD79 /* MutableRange.h in Headers */,
</ins><span class="cx"> 97BC6A211505F081001B74AC /* Database.h in Headers */,
</span><span class="cx"> 97BC6A241505F081001B74AC /* DatabaseAuthorizer.h in Headers */,
</span><span class="cx"> FE16CFD4169D1DED00D3A0C7 /* DatabaseBackend.h in Headers */,
</span><span class="lines">@@ -24400,6 +24413,7 @@
</span><span class="cx"> 85909CE40ACC7A7E00DF01F1 /* DOMCSSUnknownRuleInternal.h in Headers */,
</span><span class="cx"> 858C381C0AA8E29600B187A4 /* DOMCSSValue.h in Headers */,
</span><span class="cx"> 85B498F30ADB336A00925CBB /* DOMCSSValueInternal.h in Headers */,
</span><ins>+ 26F756B31B3B66F70005DD79 /* ImmutableNFA.h in Headers */,
</ins><span class="cx"> 858C383C0AA8ED8200B187A4 /* DOMCSSValueList.h in Headers */,
</span><span class="cx"> 85909D2B0ACC7D5500DF01F1 /* DOMCSSValueListInternal.h in Headers */,
</span><span class="cx"> E10B9CCC0B747A44003ED890 /* DOMCustomXPathNSResolver.h in Headers */,
</span><span class="lines">@@ -26234,6 +26248,7 @@
</span><span class="cx"> BCEA486E097D93020094C9E4 /* RenderDeprecatedFlexibleBox.h in Headers */,
</span><span class="cx"> D302754A12A5FE84004BD828 /* RenderDetailsMarker.h in Headers */,
</span><span class="cx"> A76E5F7F135E0DCF00A69837 /* RenderedDocumentMarker.h in Headers */,
</span><ins>+ 26F756B51B3B68F20005DD79 /* ImmutableNFANodeBuilder.h in Headers */,
</ins><span class="cx"> 9B32CDA913DF7FA900F34D13 /* RenderedPosition.h in Headers */,
</span><span class="cx"> E43A023B17EB370A004CDD25 /* RenderElement.h in Headers */,
</span><span class="cx"> 0F5B7A5510F65D7A00376302 /* RenderEmbeddedObject.h in Headers */,
</span><span class="lines">@@ -26858,6 +26873,7 @@
</span><span class="cx"> B2227A810D00BF220071B782 /* SVGPathSegList.h in Headers */,
</span><span class="cx"> 8476C9E611DF6A0B00555B02 /* SVGPathSegListBuilder.h in Headers */,
</span><span class="cx"> 084A0829128D7867002DB1F1 /* SVGPathSegListPropertyTearOff.h in Headers */,
</span><ins>+ 26F756B11B3B65AC0005DD79 /* MutableRangeList.h in Headers */,
</ins><span class="cx"> 84B6B978120F13E500B8EFAF /* SVGPathSegListSource.h in Headers */,
</span><span class="cx"> 83C1D435178D5AB500141E68 /* SVGPathSegMovetoAbs.h in Headers */,
</span><span class="cx"> 83C1D436178D5AB500141E68 /* SVGPathSegMovetoRel.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -193,25 +193,25 @@
</span><span class="cx"> actions.append(actionId);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex& root, size_t maxNFASize)
</del><ins>+static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, size_t maxNFASize)
</ins><span class="cx"> {
</span><span class="cx"> // This recurses the subtree of the prefix tree.
</span><span class="cx"> // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph,
</span><span class="cx"> // recurses into children, and deletes any processed leaf nodes.
</span><span class="cx"> struct ActiveSubtree {
</span><del>- ActiveSubtree(PrefixTreeVertex& vertex, unsigned nfaNodeId, unsigned edgeIndex)
</del><ins>+ ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
</ins><span class="cx"> : vertex(vertex)
</span><del>- , nfaNodeId(nfaNodeId)
</del><ins>+ , nfaNode(WTF::move(nfaNode))
</ins><span class="cx"> , edgeIndex(edgeIndex)
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx"> PrefixTreeVertex& vertex;
</span><del>- unsigned nfaNodeId;
</del><ins>+ ImmutableCharNFANodeBuilder nfaNode;
</ins><span class="cx"> unsigned edgeIndex;
</span><span class="cx"> };
</span><span class="cx"> Vector<ActiveSubtree> stack;
</span><span class="cx"> if (!root.edges.isEmpty())
</span><del>- stack.append(ActiveSubtree(root, nfaRootId, 0));
</del><ins>+ stack.append(ActiveSubtree(root, WTF::move(subtreeRoot), 0));
</ins><span class="cx"> bool nfaTooBig = false;
</span><span class="cx">
</span><span class="cx"> // Generate graphs for each subtree that does not contain any quantifiers.
</span><span class="lines">@@ -220,7 +220,7 @@
</span><span class="cx"> const unsigned edgeIndex = stack.last().edgeIndex;
</span><span class="cx">
</span><span class="cx"> // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
</span><del>- if (vertex.edges.isEmpty() && nfa.graphSize() > maxNFASize)
</del><ins>+ if (vertex.edges.isEmpty() && nfa.nodes.size() > maxNFASize)
</ins><span class="cx"> nfaTooBig = true;
</span><span class="cx">
</span><span class="cx"> if (edgeIndex < vertex.edges.size()) {
</span><span class="lines">@@ -237,10 +237,10 @@
</span><span class="cx"> stack.last().edgeIndex++;
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><del>-
- unsigned subtreeRootId = edge.term.generateGraph(nfa, stack.last().nfaNodeId, edge.child->finalActions);
</del><ins>+
+ ImmutableCharNFANodeBuilder newNode = edge.term.generateGraph(nfa, stack.last().nfaNode, edge.child->finalActions);
</ins><span class="cx"> ASSERT(edge.child.get());
</span><del>- stack.append(ActiveSubtree(*edge.child.get(), subtreeRootId, 0));
</del><ins>+ stack.append(ActiveSubtree(*edge.child.get(), WTF::move(newNode), 0));
</ins><span class="cx"> } else {
</span><span class="cx"> ASSERT(edgeIndex == vertex.edges.size());
</span><span class="cx"> vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
</span><span class="lines">@@ -286,22 +286,26 @@
</span><span class="cx"> stack.removeLast();
</span><span class="cx"> }
</span><span class="cx"> ASSERT_WITH_MESSAGE(!stack.isEmpty(), "At least the root should be in the stack");
</span><del>-
</del><ins>+
</ins><span class="cx"> // Make an NFA with the subtrees for whom this is also the last quantifier (or who also have no quantifier).
</span><span class="cx"> NFA nfa;
</span><del>- // Put the prefix into the NFA.
- unsigned prefixEnd = nfa.root();
- for (unsigned i = 0; i < stack.size() - 1; ++i) {
- ASSERT(!stack[i]->edges.isEmpty());
- const PrefixTreeEdge& edge = stack[i]->edges.last();
- prefixEnd = edge.term.generateGraph(nfa, prefixEnd, edge.child->finalActions);
</del><ins>+ {
+ // Put the prefix into the NFA.
+ ImmutableCharNFANodeBuilder lastNode(nfa);
+ for (unsigned i = 0; i < stack.size() - 1; ++i) {
+ const PrefixTreeEdge& edge = stack[i]->edges.last();
+ ImmutableCharNFANodeBuilder newNode = edge.term.generateGraph(nfa, lastNode, edge.child->finalActions);
+ lastNode = WTF::move(newNode);
+ }
+
+ // Put the non-quantified vertices in the subtree into the NFA and delete them.
+ ASSERT(stack.last());
+ generateNFAForSubtree(nfa, WTF::move(lastNode), *stack.last(), maxNFASize);
</ins><span class="cx"> }
</span><del>- // Put the non-quantified vertices in the subtree into the NFA and delete them.
- ASSERT(stack.last());
- generateNFAForSubtree(nfa, prefixEnd, *stack.last(), maxNFASize);
-
</del><ins>+ nfa.finalize();
+
</ins><span class="cx"> handler(WTF::move(nfa));
</span><del>-
</del><ins>+
</ins><span class="cx"> // Clean up any processed leaf nodes.
</span><span class="cx"> while (true) {
</span><span class="cx"> if (stack.size() > 1) {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -309,9 +309,7 @@
</span><span class="cx"> // Our bytecode interpreter expects to have at least one DFA, so if we haven't seen any
</span><span class="cx"> // create a dummy one and add any universal actions.
</span><span class="cx">
</span><del>- NFA dummyNFA;
- DFA dummyDFA = NFAToDFA::convert(dummyNFA);
-
</del><ins>+ DFA dummyDFA = DFA::empty();
</ins><span class="cx"> addUniversalActionsToDFA(dummyDFA, universalActionsWithoutDomains);
</span><span class="cx">
</span><span class="cx"> Vector<DFABytecode> bytecode;
</span><span class="lines">@@ -376,10 +374,8 @@
</span><span class="cx"> if (!firstNFAWithDomainsSeen) {
</span><span class="cx"> // Our bytecode interpreter expects to have at least one DFA, so if we haven't seen any
</span><span class="cx"> // create a dummy one and add any universal actions.
</span><del>-
- NFA dummyNFA;
- DFA dummyDFA = NFAToDFA::convert(dummyNFA);
-
</del><ins>+
+ DFA dummyDFA = DFA::empty();
</ins><span class="cx"> addUniversalActionsToDFA(dummyDFA, universalActionsWithDomains);
</span><span class="cx">
</span><span class="cx"> Vector<DFABytecode> bytecode;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -35,6 +35,13 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+DFA DFA::empty()
+{
+ DFA newDFA;
+ newDFA.nodes.append(DFANode());
+ return newDFA;
+}
+
</ins><span class="cx"> size_t DFA::memoryUsed() const
</span><span class="cx"> {
</span><span class="cx"> return sizeof(DFA)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -38,6 +38,8 @@
</span><span class="cx">
</span><span class="cx"> // The DFA abstract a partial DFA graph in a compact form.
</span><span class="cx"> struct WEBCORE_EXPORT DFA {
</span><ins>+ static DFA empty();
+
</ins><span class="cx"> void minimize();
</span><span class="cx"> unsigned graphSize() const;
</span><span class="cx"> size_t memoryUsed() const;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsImmutableNFAh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/ImmutableNFA.h (0 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ImmutableNFA.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFA.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -0,0 +1,173 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ImmutableNFA_h
+#define ImmutableNFA_h
+
+#include <wtf/Vector.h>
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+template <typename CharacterType>
+struct ImmutableRange {
+ uint32_t targetStart;
+ uint32_t targetEnd;
+ CharacterType first;
+ CharacterType last;
+};
+
+struct ImmutableNFANode {
+ uint32_t rangesStart { 0 };
+ uint32_t rangesEnd { 0 };
+ uint32_t epsilonTransitionTargetsStart { 0 };
+ uint32_t epsilonTransitionTargetsEnd { 0 };
+ uint32_t actionStart { 0 };
+ uint32_t actionEnd { 0 };
+};
+
+template <typename CharacterType, typename ActionType>
+struct ImmutableNFA {
+ Vector<ImmutableNFANode> nodes;
+ Vector<ImmutableRange<CharacterType>> transitions;
+ Vector<uint32_t> targets;
+ Vector<uint32_t> epsilonTransitionsTargets;
+ Vector<ActionType> actions;
+
+ struct ConstTargetIterator {
+ const ImmutableNFA& immutableNFA;
+ uint32_t position;
+
+ const uint32_t& operator*() const { return immutableNFA.targets[position]; }
+ const uint32_t* operator->() const { return &immutableNFA.targets[position]; }
+
+ bool operator==(const ConstTargetIterator& other) const
+ {
+ ASSERT(&immutableNFA == &other.immutableNFA);
+ return position == other.position;
+ }
+ bool operator!=(const ConstTargetIterator& other) const { return !(*this == other); }
+
+ ConstTargetIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+ };
+
+ struct IterableConstTargets {
+ const ImmutableNFA& immutableNFA;
+ uint32_t targetStart;
+ uint32_t targetEnd;
+
+ ConstTargetIterator begin() const { return { immutableNFA, targetStart }; }
+ ConstTargetIterator end() const { return { immutableNFA, targetEnd }; }
+ };
+
+ struct ConstRangeIterator {
+ const ImmutableNFA& immutableNFA;
+ uint32_t position;
+
+ const ImmutableRange<CharacterType>& operator*() const { return immutableNFA.transitions[position]; }
+ const ImmutableRange<CharacterType>* operator->() const { return &immutableNFA.transitions[position]; }
+
+ bool operator==(const ConstRangeIterator& other) const
+ {
+ ASSERT(&immutableNFA == &other.immutableNFA);
+ return position == other.position;
+ }
+ bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
+
+ ConstRangeIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+
+ IterableConstTargets data() const
+ {
+ const ImmutableRange<CharacterType>& range = immutableNFA.transitions[position];
+ return { immutableNFA, range.targetStart, range.targetEnd };
+ };
+ };
+
+ struct IterableConstRange {
+ const ImmutableNFA& immutableNFA;
+ uint32_t rangesStart;
+ uint32_t rangesEnd;
+
+ ConstRangeIterator begin() const { return { immutableNFA, rangesStart }; }
+ ConstRangeIterator end() const { return { immutableNFA, rangesEnd }; }
+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ void debugPrint() const
+ {
+ for (const auto& range : *this)
+ WTFLogAlways(" %d-%d", range.first, range.last);
+ }
+#endif
+ };
+
+ IterableConstRange transitionsForNode(uint32_t nodeId) const
+ {
+ const ImmutableNFANode& node = nodes[nodeId];
+ return { *this, node.rangesStart, node.rangesEnd };
+ };
+
+ uint32_t root() const
+ {
+ RELEASE_ASSERT(!nodes.isEmpty());
+ return 0;
+ }
+
+ void finalize()
+ {
+ nodes.shrinkToFit();
+ transitions.shrinkToFit();
+ targets.shrinkToFit();
+ epsilonTransitionsTargets.shrinkToFit();
+ actions.shrinkToFit();
+ }
+
+ size_t memoryUsed() const
+ {
+ return nodes.capacity() * sizeof(ImmutableNFANode)
+ + transitions.capacity() * sizeof(ImmutableRange<CharacterType>)
+ + targets.capacity() * sizeof(uint32_t)
+ + epsilonTransitionsTargets.capacity() * sizeof(uint32_t)
+ + actions.capacity() * sizeof(ActionType);
+ }
+};
+
+}
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // ImmutableNFA_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsImmutableNFANodeBuilderh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (0 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -0,0 +1,244 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ImmutableNFANodeBuilder_h
+#define ImmutableNFANodeBuilder_h
+
+#include "ImmutableNFA.h"
+#include "MutableRangeList.h"
+#include <wtf/HashSet.h>
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+// A ImmutableNFANodeBuilder let you build a NFA node by adding states and linking with other nodes.
+// Whe a builder is destructed, all its properties are finalized into the NFA. Using the NA with a live
+// builder results in undefined behaviors.
+template <typename CharacterType, typename ActionType>
+class ImmutableNFANodeBuilder {
+ typedef ImmutableNFA<CharacterType, ActionType> TypedImmutableNFA;
+ typedef HashSet<uint32_t, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> TargetSet;
+public:
+ ImmutableNFANodeBuilder() { }
+
+ ImmutableNFANodeBuilder(TypedImmutableNFA& immutableNFA)
+ : m_immutableNFA(&immutableNFA)
+ , m_finalized(false)
+ {
+ m_nodeId = m_immutableNFA->nodes.size();
+ m_immutableNFA->nodes.append(ImmutableNFANode());
+#if !ASSERT_DISABLED
+ m_isDisconnected = true;
+#endif
+ }
+
+ ImmutableNFANodeBuilder(ImmutableNFANodeBuilder&& other)
+ : m_immutableNFA(other.m_immutableNFA)
+ , m_ranges(WTF::move(other.m_ranges))
+ , m_epsilonTransitionTargets(WTF::move(m_epsilonTransitionTargets))
+ , m_actions(WTF::move(other.m_actions))
+ , m_nodeId(other.m_nodeId)
+ , m_finalized(other.m_finalized)
+#if !ASSERT_DISABLED
+ , m_isDisconnected(other.m_isDisconnected)
+#endif
+ {
+ other.m_immutableNFA = nullptr;
+ other.m_finalized = true;
+#if !ASSERT_DISABLED
+ other.m_isDisconnected = false;
+#endif
+ }
+
+ ~ImmutableNFANodeBuilder()
+ {
+ ASSERT_WITH_MESSAGE(!m_isDisconnected, "This nodes is not connected to anything and is not reached by any other node.");
+
+ if (!m_finalized)
+ finalize();
+ }
+
+ struct TrivialRange {
+ CharacterType first;
+ CharacterType last;
+ };
+
+ struct FakeRangeIterator {
+ const TrivialRange& operator*() const { return range; }
+ const TrivialRange* operator->() const { return &range; }
+ uint32_t data() const { return targetId; }
+ bool operator==(const FakeRangeIterator& other)
+ {
+ return this->isEnd == other.isEnd;
+ }
+ bool operator!=(const FakeRangeIterator& other) { return !(*this == other); }
+ FakeRangeIterator operator++()
+ {
+ isEnd = true;
+ return *this;
+ }
+
+ TrivialRange range;
+ uint32_t targetId;
+ bool isEnd;
+ };
+
+ void addTransition(CharacterType first, CharacterType last, const ImmutableNFANodeBuilder& target)
+ {
+ ASSERT(!m_finalized);
+ ASSERT(m_immutableNFA);
+ ASSERT(m_immutableNFA == target.m_immutableNFA);
+#if !ASSERT_DISABLED
+ m_isDisconnected = false;
+ target.m_isDisconnected = false;
+#endif
+
+ struct Converter {
+ TargetSet convert(uint32_t target)
+ {
+ return TargetSet({ target });
+ }
+ void extend(TargetSet& existingTargets, uint32_t target)
+ {
+ existingTargets.add(target);
+ }
+ };
+
+ Converter converter;
+ m_ranges.extend(FakeRangeIterator { { first, last }, target.m_nodeId, false }, FakeRangeIterator { { 0, 0 }, target.m_nodeId, true }, converter);
+ }
+
+ void addEpsilonTransition(const ImmutableNFANodeBuilder& target)
+ {
+ ASSERT(!m_finalized);
+ ASSERT(m_immutableNFA);
+ ASSERT(m_immutableNFA == target.m_immutableNFA);
+#if !ASSERT_DISABLED
+ m_isDisconnected = false;
+ target.m_isDisconnected = false;
+#endif
+ m_epsilonTransitionTargets.add(target.m_nodeId);
+ }
+
+ template<typename ActionIterator>
+ void setActions(ActionIterator begin, ActionIterator end)
+ {
+ ASSERT(!m_finalized);
+ ASSERT(m_immutableNFA);
+
+ m_actions.add(begin, end);
+ }
+
+ ImmutableNFANodeBuilder& operator=(ImmutableNFANodeBuilder&& other)
+ {
+ if (!m_finalized)
+ finalize();
+
+ m_immutableNFA = other.m_immutableNFA;
+ m_ranges = WTF::move(other.m_ranges);
+ m_epsilonTransitionTargets = WTF::move(other.m_epsilonTransitionTargets);
+ m_actions = WTF::move(other.m_actions);
+ m_nodeId = other.m_nodeId;
+ m_finalized = other.m_finalized;
+
+ other.m_immutableNFA = nullptr;
+ other.m_finalized = true;
+#if !ASSERT_DISABLED
+ m_isDisconnected = other.m_isDisconnected;
+ other.m_isDisconnected = false;
+#endif
+ return *this;
+ }
+
+private:
+ void finalize()
+ {
+ ASSERT_WITH_MESSAGE(!m_finalized, "The API contract is that the builder can only be finalized once.");
+ m_finalized = true;
+ ImmutableNFANode& immutableNFANode = m_immutableNFA->nodes[m_nodeId];
+ sinkActions(immutableNFANode);
+ sinkEpsilonTransitions(immutableNFANode);
+ sinkTransitions(immutableNFANode);
+ }
+
+ void sinkActions(ImmutableNFANode& immutableNFANode)
+ {
+ unsigned actionStart = m_immutableNFA->actions.size();
+ for (const ActionType& action : m_actions)
+ m_immutableNFA->actions.append(action);
+ unsigned actionEnd = m_immutableNFA->actions.size();
+ immutableNFANode.actionStart = actionStart;
+ immutableNFANode.actionEnd = actionEnd;
+ }
+
+ void sinkTransitions(ImmutableNFANode& immutableNFANode)
+ {
+ unsigned transitionsStart = m_immutableNFA->transitions.size();
+ for (const auto& range : m_ranges) {
+ unsigned targetsStart = m_immutableNFA->targets.size();
+ for (uint32_t target : range.data)
+ m_immutableNFA->targets.append(target);
+ unsigned targetsEnd = m_immutableNFA->targets.size();
+
+ m_immutableNFA->transitions.append(ImmutableRange<CharacterType> { targetsStart, targetsEnd, range.first, range.last });
+ }
+ unsigned transitionsEnd = m_immutableNFA->transitions.size();
+
+ immutableNFANode.rangesStart = transitionsStart;
+ immutableNFANode.rangesEnd = transitionsEnd;
+ }
+
+ void sinkEpsilonTransitions(ImmutableNFANode& immutableNFANode)
+ {
+ unsigned start = m_immutableNFA->epsilonTransitionsTargets.size();
+ for (uint32_t target : m_epsilonTransitionTargets)
+ m_immutableNFA->epsilonTransitionsTargets.append(target);
+ unsigned end = m_immutableNFA->epsilonTransitionsTargets.size();
+
+ immutableNFANode.epsilonTransitionTargetsStart = start;
+ immutableNFANode.epsilonTransitionTargetsEnd = end;
+ }
+
+ TypedImmutableNFA* m_immutableNFA { nullptr };
+ MutableRangeList<CharacterType, TargetSet> m_ranges;
+ TargetSet m_epsilonTransitionTargets;
+ HashSet<ActionType, WTF::IntHash<ActionType>, WTF::UnsignedWithZeroKeyHashTraits<ActionType>> m_actions;
+ uint32_t m_nodeId;
+ bool m_finalized { true };
+#if !ASSERT_DISABLED
+ mutable bool m_isDisconnected { false };
+#endif
+};
+
+}
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // ImmutableNFANodeBuilder_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsMutableRangeh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/MutableRange.h (0 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/MutableRange.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/MutableRange.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -0,0 +1,102 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef MutableRange_h
+#define MutableRange_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+template <typename CharacterType, typename DataType>
+class MutableRange {
+ typedef MutableRange<CharacterType, DataType> TypedMutableRange;
+public:
+ MutableRange(uint32_t nextRangeIndex, CharacterType first, CharacterType last)
+ : nextRangeIndex(nextRangeIndex)
+ , first(first)
+ , last(last)
+ {
+ ASSERT(first <= last);
+ }
+
+ MutableRange(const DataType& data, uint32_t nextRangeIndex, CharacterType first, CharacterType last)
+ : data(data)
+ , nextRangeIndex(nextRangeIndex)
+ , first(first)
+ , last(last)
+ {
+ ASSERT(first <= last);
+ }
+
+ MutableRange(DataType&& data, uint32_t nextRangeIndex, CharacterType first, CharacterType last)
+ : data(WTF::move(data))
+ , nextRangeIndex(nextRangeIndex)
+ , first(first)
+ , last(last)
+ {
+ ASSERT(first <= last);
+ }
+
+ MutableRange(MutableRange&& other)
+ : data(WTF::move(other.data))
+ , nextRangeIndex(other.nextRangeIndex)
+ , first(other.first)
+ , last(other.last)
+ {
+ ASSERT(first <= last);
+ }
+
+ TypedMutableRange& operator=(TypedMutableRange&& other)
+ {
+ data = WTF::move(other.data);
+ nextRangeIndex = WTF::move(other.nextRangeIndex);
+ first = WTF::move(other.first);
+ last = WTF::move(other.last);
+ return *this;
+ }
+
+ DataType data;
+
+ // We use a funny convention: if there are no nextRange, the nextRangeIndex is zero.
+ // This is faster to check than a special value in many cases.
+ // We can use zero because ranges can only form a chain, and the first range is always zero by convention.
+ // When we insert something in from of the first range, we swap the values.
+ uint32_t nextRangeIndex;
+ CharacterType first;
+ CharacterType last;
+
+ CharacterType size() const { return last - first; }
+};
+
+}
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // MutableRange_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsMutableRangeListh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/MutableRangeList.h (0 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/MutableRangeList.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/MutableRangeList.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -0,0 +1,261 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef MutableRangeList_h
+#define MutableRangeList_h
+
+#include "MutableRange.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+// A range list keeps ranges sorted. Ranges are not sorted in the vector, but
+template <typename CharacterType, typename DataType, unsigned inlineCapacity = 0>
+class MutableRangeList {
+ typedef MutableRange<CharacterType, DataType> TypedMutableRange;
+public:
+ class ConstIterator {
+ public:
+ const MutableRangeList& rangeList;
+ uint32_t index;
+ bool atEnd;
+
+ const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
+ const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
+
+ bool operator==(const ConstIterator& other) const
+ {
+ ASSERT(&rangeList == &other.rangeList);
+ if (atEnd || other.atEnd)
+ return atEnd == other.atEnd;
+ return index == other.index;
+ }
+ bool operator!=(const ConstIterator& other) const { return !(*this == other); }
+
+ ConstIterator& operator++()
+ {
+ ASSERT(!atEnd);
+ index = rangeList.m_ranges[index].nextRangeIndex;
+ if (!index)
+ atEnd = true;
+ return *this;
+ }
+ };
+
+ ConstIterator begin() const { return ConstIterator { *this, 0, m_ranges.isEmpty() }; }
+ ConstIterator end() const { return ConstIterator { *this, 0, true }; }
+
+ uint32_t appendRange(uint32_t lastRangeIndex, CharacterType first, CharacterType last, const DataType& data)
+ {
+ uint32_t newRangeIndex = m_ranges.size();
+ m_ranges.append(TypedMutableRange(data, 0, first, last));
+ if (!newRangeIndex)
+ return 0;
+
+ ASSERT(!m_ranges[lastRangeIndex].nextRangeIndex);
+ ASSERT(m_ranges[lastRangeIndex].last < first);
+
+ m_ranges[lastRangeIndex].nextRangeIndex = newRangeIndex;
+ return newRangeIndex;
+ }
+
+ template <typename RangeIterator, typename DataConverter>
+ void extend(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
+ {
+ if (otherIterator == otherEnd)
+ return;
+
+ if (m_ranges.isEmpty()) {
+ initializeFrom(otherIterator, otherEnd, dataConverter);
+ return;
+ }
+
+ bool reachedSelfEnd = false;
+ uint32_t lastSelfRangeIndex = 0;
+ uint32_t selfRangeIndex = 0;
+
+ auto otherRangeOffset = otherIterator->first; // To get the right type :)
+ otherRangeOffset = 0;
+
+ do {
+ TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
+
+ // First, we move forward until we find something interesting.
+ if (activeSelfRange->last < otherIterator->first + otherRangeOffset) {
+ lastSelfRangeIndex = selfRangeIndex;
+ selfRangeIndex = activeSelfRange->nextRangeIndex;
+ reachedSelfEnd = !selfRangeIndex;
+ continue;
+ }
+ if (otherIterator->last < activeSelfRange->first) {
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator->first + otherRangeOffset, otherIterator->last, dataConverter.convert(otherIterator.data()));
+
+ ++otherIterator;
+ otherRangeOffset = 0;
+ continue;
+ }
+
+ // If we reached here, we have:
+ // 1) activeRangeA->last >= activeRangeB->first.
+ // 2) activeRangeA->first <= activeRangeB->last.
+ // But we don't know how they collide.
+
+ // Do we have a part on the left? Create a new range for it.
+ if (activeSelfRange->first < otherIterator->first + otherRangeOffset) {
+ DataType copiedData = activeSelfRange->data;
+ CharacterType newRangeFirstCharacter = activeSelfRange->first;
+ activeSelfRange->first = otherIterator->first + otherRangeOffset;
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator->first + otherRangeOffset - 1, WTF::move(copiedData));
+ activeSelfRange = &m_ranges[selfRangeIndex];
+ } else if (otherIterator->first + otherRangeOffset < activeSelfRange->first) {
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator->first + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
+
+ activeSelfRange = &m_ranges[selfRangeIndex];
+ 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;
+ }
+
+ // Here, we know both ranges start at the same point, we need to create the part that intersect
+ // and merge the data.
+
+ if (activeSelfRange->last == otherIterator->last) {
+ // If they finish together, things are really easy: we just add B to A.
+ dataConverter.extend(activeSelfRange->data, otherIterator.data());
+
+ lastSelfRangeIndex = selfRangeIndex;
+ selfRangeIndex = activeSelfRange->nextRangeIndex;
+ reachedSelfEnd = !selfRangeIndex;
+
+ ++otherIterator;
+ otherRangeOffset = 0;
+ continue;
+ }
+
+ if (activeSelfRange->last > otherIterator->last) {
+ // If A is bigger than B, we add a merged version and move A to the right.
+
+ CharacterType combinedPartStart = activeSelfRange->first;
+ activeSelfRange->first = otherIterator->last + 1;
+
+ DataType combinedData = activeSelfRange->data;
+ dataConverter.extend(combinedData, otherIterator.data());
+ insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator->last, WTF::move(combinedData));
+
+ ++otherIterator;
+ otherRangeOffset = 0;
+ continue;
+ }
+
+ // If we reached here, B ends after A. We merge the intersection and move on.
+ ASSERT(otherIterator->last > activeSelfRange->last);
+ dataConverter.extend(activeSelfRange->data, otherIterator.data());
+
+ otherRangeOffset = activeSelfRange->last - otherIterator->first + 1;
+ lastSelfRangeIndex = selfRangeIndex;
+ selfRangeIndex = activeSelfRange->nextRangeIndex;
+ reachedSelfEnd = !selfRangeIndex;
+ } while (!reachedSelfEnd && otherIterator != otherEnd);
+
+ while (otherIterator != otherEnd) {
+ lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator->first + otherRangeOffset, otherIterator->last, dataConverter.convert(otherIterator.data()));
+ otherRangeOffset = 0;
+ ++otherIterator;
+ }
+ }
+
+ bool isEmpty() const
+ {
+ return m_ranges.isEmpty();
+ }
+
+ void clear()
+ {
+ m_ranges.clear();
+ }
+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ void debugPrint() const
+ {
+ for (const TypedMutableRange& range : *this)
+ WTFLogAlways(" %d-%d", range.first, range.last);
+ }
+#endif
+
+ Vector<MutableRange<CharacterType, DataType>, inlineCapacity> m_ranges;
+private:
+ void insertBetween(uint32_t& leftRangeIndex, uint32_t& rightRangeIndex, CharacterType first, CharacterType last, DataType&& data)
+ {
+ ASSERT(m_ranges[rightRangeIndex].first > last);
+
+ if (!rightRangeIndex) {
+ // This is a special case. We always keep the first range as the first element in the vector.
+ uint32_t movedRangeIndex = m_ranges.size();
+ m_ranges.append(WTF::move(m_ranges.first()));
+ m_ranges[0] = TypedMutableRange(WTF::move(data), movedRangeIndex, first, last);
+ leftRangeIndex = 0;
+ rightRangeIndex = movedRangeIndex;
+ return;
+ }
+
+ ASSERT(m_ranges[leftRangeIndex].nextRangeIndex == rightRangeIndex);
+ ASSERT(m_ranges[leftRangeIndex].last < first);
+
+ uint32_t newRangeIndex = m_ranges.size();
+ m_ranges.append(TypedMutableRange(WTF::move(data), rightRangeIndex, first, last));
+ m_ranges[leftRangeIndex].nextRangeIndex = newRangeIndex;
+ leftRangeIndex = newRangeIndex;
+ }
+
+ template <typename RangeIterator, typename DataConverter>
+ void initializeFrom(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
+ {
+ ASSERT_WITH_MESSAGE(otherIterator != otherEnd, "We should never do anything when extending with a null range.");
+ ASSERT_WITH_MESSAGE(m_ranges.isEmpty(), "This code does not handle splitting, it can only be used on empty RangeList.");
+
+ uint32_t loopCounter = 0;
+ do {
+ m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
+ loopCounter + 1,
+ otherIterator->first,
+ otherIterator->last));
+ ++loopCounter;
+ ++otherIterator;
+ } while (otherIterator != otherEnd);
+
+ if (!m_ranges.isEmpty())
+ m_ranges.last().nextRangeIndex = 0;
+ }
+};
+
+}
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // MutableRangeList_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include <wtf/ASCIICType.h>
</ins><span class="cx"> #include <wtf/DataLog.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx">
</span><span class="lines">@@ -35,184 +36,85 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-NFA::NFA()
- : m_root(createNode())
-{
-}
-
-unsigned NFA::createNode()
-{
- unsigned nextId = m_nodes.size();
- m_nodes.append(NFANode());
- return nextId;
-}
-
-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
-size_t NFA::memoryUsed() const
-{
- size_t size = sizeof(NFA);
- for (const NFANode& node : m_nodes) {
- for (const auto& transition : node.transitions)
- size += transition.value.capacity() * sizeof(unsigned);
- size += sizeof(node)
- + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
- + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
- + node.finalRuleIds.capacity() * sizeof(uint64_t);
- }
- return size;
-}
-#endif
-
-void NFA::addTransition(unsigned from, unsigned to, char character)
-{
- ASSERT(from < m_nodes.size());
- ASSERT(to < m_nodes.size());
-
- NFANode& fromNode = m_nodes[from];
- if (fromNode.transitionsOnAnyCharacter.contains(to))
- return;
-
- auto addResult = m_nodes[from].transitions.add(character, NFANodeIndexSet());
- addResult.iterator->value.add(to);
-}
-
-void NFA::addEpsilonTransition(unsigned from, unsigned to)
-{
- ASSERT(from < m_nodes.size());
- ASSERT(to < m_nodes.size());
-
- auto addResult = m_nodes[from].transitions.add(epsilonTransitionCharacter, NFANodeIndexSet());
- addResult.iterator->value.add(to);
-}
-
-void NFA::addTransitionsOnAnyCharacter(unsigned from, unsigned to)
-{
- ASSERT(from < m_nodes.size());
- ASSERT(to < m_nodes.size());
-
- NFANode& fromNode = m_nodes[from];
- fromNode.transitionsOnAnyCharacter.add(to);
-
- for (auto transitionSlot : fromNode.transitions)
- transitionSlot.value.remove(to);
-}
-
-void NFA::setActions(unsigned node, const ActionList& actions)
-{
- ASSERT_WITH_MESSAGE(m_nodes[node].finalRuleIds.isEmpty(), "The final state should only be defined once.");
- copyToVector(actions, m_nodes[node].finalRuleIds);
-}
-
-unsigned NFA::graphSize() const
-{
- return m_nodes.size();
-}
-
-void NFA::restoreToGraphSize(unsigned size)
-{
- ASSERT(size >= 1);
- ASSERT(size <= graphSize());
-
- m_nodes.shrink(size);
-}
-
</del><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><del>-static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
-{
- if (!firstRange)
- dataLogF(", ");
- if (rangeStart == rangeEnd) {
- if (rangeStart == epsilonTransitionCharacter)
- dataLogF("É›");
- else if (rangeStart == '"' || rangeStart == '\\')
- dataLogF("\\%c", rangeStart);
- else if (rangeStart >= '!' && rangeStart <= '~')
- dataLogF("%c", rangeStart);
- else
- dataLogF("\\\\%d", rangeStart);
- } else {
- if (rangeStart == 1 && rangeEnd == 127)
- dataLogF("[any input]");
- else
- dataLogF("\\\\%d-\\\\%d", rangeStart, rangeEnd);
- }
-}
-
-static void printTransitions(const Vector<NFANode>& graph, unsigned sourceNode, uint16_t epsilonTransitionCharacter)
-{
- const NFANode& node = graph[sourceNode];
- const HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>& transitions = node.transitions;
-
- HashMap<unsigned, HashSet<uint16_t, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
-
- for (const auto& transition : transitions) {
- for (unsigned targetNode : transition.value) {
- transitionsPerTarget.add(targetNode, HashSet<uint16_t, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>());
- transitionsPerTarget.find(targetNode)->value.add(transition.key);
- }
- }
-
- for (const auto& transitionPerTarget : transitionsPerTarget) {
- dataLogF(" %d -> %d [label=\"", sourceNode, transitionPerTarget.key);
-
- Vector<uint16_t> incommingCharacters;
- copyToVector(transitionPerTarget.value, incommingCharacters);
- std::sort(incommingCharacters.begin(), incommingCharacters.end());
-
- uint16_t rangeStart = incommingCharacters.first();
- uint16_t rangeEnd = rangeStart;
- bool first = true;
- for (unsigned sortedTransitionIndex = 1; sortedTransitionIndex < incommingCharacters.size(); ++sortedTransitionIndex) {
- uint16_t nextChar = incommingCharacters[sortedTransitionIndex];
- if (nextChar == rangeEnd+1) {
- rangeEnd = nextChar;
- continue;
- }
- printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
- rangeStart = rangeEnd = nextChar;
- first = false;
- }
- printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
-
- dataLogF("\"];\n");
- }
-
- for (unsigned targetOnAnyCharacter : node.transitionsOnAnyCharacter)
- dataLogF(" %d -> %d [label=\"[any input]\"];\n", sourceNode, targetOnAnyCharacter);
-}
-
</del><span class="cx"> void NFA::debugPrintDot() const
</span><span class="cx"> {
</span><span class="cx"> dataLogF("digraph NFA_Transitions {\n");
</span><span class="cx"> dataLogF(" rankdir=LR;\n");
</span><span class="cx"> dataLogF(" node [shape=circle];\n");
</span><span class="cx"> dataLogF(" {\n");
</span><del>- for (unsigned i = 0; i < m_nodes.size(); ++i) {
</del><ins>+
+ for (unsigned i = 0; i < nodes.size(); ++i) {
</ins><span class="cx"> dataLogF(" %d [label=<Node %d", i, i);
</span><span class="cx">
</span><del>- const ActionList& finalRules = m_nodes[i].finalRuleIds;
- if (!finalRules.isEmpty()) {
</del><ins>+ const auto& node = nodes[i];
+
+ if (node.actionStart != node.actionEnd) {
</ins><span class="cx"> dataLogF("<BR/>(Final: ");
</span><del>- for (unsigned ruleIndex = 0; ruleIndex < finalRules.size(); ++ruleIndex) {
- if (ruleIndex)
</del><ins>+ bool isFirst = true;
+ for (unsigned actionIndex = node.actionStart; actionIndex < node.actionEnd; ++actionIndex) {
+ if (!isFirst)
</ins><span class="cx"> dataLogF(", ");
</span><del>- dataLogF("%llu", finalRules[ruleIndex]);
</del><ins>+ dataLogF("%llu", actions[actionIndex]);
+ isFirst = false;
</ins><span class="cx"> }
</span><span class="cx"> dataLogF(")");
</span><span class="cx"> }
</span><del>-
</del><span class="cx"> dataLogF(">]");
</span><span class="cx">
</span><del>- if (!finalRules.isEmpty())
</del><ins>+ if (node.actionStart != node.actionEnd)
</ins><span class="cx"> dataLogF(" [shape=doublecircle]");
</span><del>-
</del><span class="cx"> dataLogF(";\n");
</span><span class="cx"> }
</span><span class="cx"> dataLogF(" }\n");
</span><span class="cx">
</span><span class="cx"> dataLogF(" {\n");
</span><del>- for (unsigned i = 0; i < m_nodes.size(); ++i)
- printTransitions(m_nodes, i, epsilonTransitionCharacter);
</del><ins>+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ const auto& node = nodes[i];
+
+ HashMap<uint32_t, Vector<uint32_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
+
+ for (uint32_t transitionIndex = node.rangesStart; transitionIndex < node.rangesEnd; ++transitionIndex) {
+ const ImmutableCharRange& range = transitions[transitionIndex];
+ for (uint32_t targetIndex = range.targetStart; targetIndex < range.targetEnd; ++targetIndex) {
+ uint32_t target = targets[targetIndex];
+ auto addResult = transitionsPerTarget.add(target, Vector<uint32_t>());
+ addResult.iterator->value.append(transitionIndex);
+ }
+ }
+
+ for (const auto& slot : transitionsPerTarget) {
+ dataLogF(" %d -> %d [label=\"", i, slot.key);
+
+ bool isFirst = true;
+ for (uint32_t rangeIndex : slot.value) {
+ if (!isFirst)
+ dataLogF(", ");
+ else
+ isFirst = false;
+
+ const ImmutableCharRange& range = transitions[rangeIndex];
+ if (range.first == range.last) {
+ if (isASCIIPrintable(range.first))
+ dataLogF("%c", range.first);
+ else
+ dataLogF("%d", range.first);
+ } else {
+ if (isASCIIPrintable(range.first) && isASCIIPrintable(range.last))
+ dataLogF("%c-%c", range.first, range.last);
+ else
+ dataLogF("%d-%d", range.first, range.last);
+ }
+ }
+ dataLogF("\"]\n");
+ }
+
+ for (uint32_t epsilonTargetIndex = node.epsilonTransitionTargetsStart; epsilonTargetIndex < node.epsilonTransitionTargetsEnd; ++epsilonTargetIndex) {
+ uint32_t target = epsilonTransitionsTargets[epsilonTargetIndex];
+ dataLogF(" %d -> %d [label=\"É›\"]\n", i, target);
+ }
+ }
+
</ins><span class="cx"> dataLogF(" }\n");
</span><span class="cx"> dataLogF("}\n");
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><span class="cx"> #include "ContentExtensionsDebugging.h"
</span><ins>+#include "ImmutableNFANodeBuilder.h"
</ins><span class="cx"> #include "NFANode.h"
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="lines">@@ -36,42 +37,13 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-class NFAToDFA;
</del><ins>+typedef ImmutableRange<char> ImmutableCharRange;
+typedef ImmutableNFANodeBuilder<char, uint64_t> ImmutableCharNFANodeBuilder;
</ins><span class="cx">
</span><del>-// The NFA provides a way to build a NFA graph with characters or epsilon as transitions.
-// The nodes are accessed through an identifier.
-class NFA {
-public:
- WEBCORE_EXPORT NFA();
- unsigned root() const { return m_root; }
- unsigned createNode();
-
- void addTransition(unsigned from, unsigned to, char character);
- void addEpsilonTransition(unsigned from, unsigned to);
- void addTransitionsOnAnyCharacter(unsigned from, unsigned to);
- void setActions(unsigned node, const ActionList& finalActions);
-
- unsigned graphSize() const;
- void restoreToGraphSize(unsigned);
-
</del><ins>+struct NFA : public ImmutableNFA<char, uint64_t> {
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><del>- void addRuleId(unsigned node, const ActionList& ruleIds);
-
</del><span class="cx"> void debugPrintDot() const;
</span><del>-#else
- void addRuleId(unsigned, uint64_t) { }
</del><span class="cx"> #endif
</span><del>-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
- size_t memoryUsed() const;
-#endif
-
-private:
- friend class NFAToDFA;
-
- static const unsigned epsilonTransitionCharacter = 256;
-
- Vector<NFANode> m_nodes;
- unsigned m_root;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFANode.h (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFANode.h 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/NFANode.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -45,7 +45,7 @@
</span><span class="cx">
</span><span class="cx"> class NFANode {
</span><span class="cx"> public:
</span><del>- HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> transitions;
</del><ins>+ NFANodeTransitions transitions;
</ins><span class="cx"> NFANodeIndexSet transitionsOnAnyCharacter;
</span><span class="cx">
</span><span class="cx"> ActionList finalRuleIds;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -30,6 +30,8 @@
</span><span class="cx">
</span><span class="cx"> #include "ContentExtensionsDebugging.h"
</span><span class="cx"> #include "DFANode.h"
</span><ins>+#include "ImmutableNFA.h"
+#include "MutableRangeList.h"
</ins><span class="cx"> #include "NFA.h"
</span><span class="cx"> #include <wtf/DataLog.h>
</span><span class="cx"> #include <wtf/HashMap.h>
</span><span class="lines">@@ -39,53 +41,48 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+typedef MutableRange<char, NFANodeIndexSet> NFANodeRange;
+typedef MutableRangeList<char, NFANodeIndexSet> NFANodeRangeList;
+typedef MutableRangeList<char, NFANodeIndexSet, 128> PreallocatedNFANodeRangeList;
+
</ins><span class="cx"> // FIXME: set a better initial size.
</span><span class="cx"> // FIXME: include the hash inside NodeIdSet.
</span><span class="cx"> typedef NFANodeIndexSet NodeIdSet;
</span><span class="cx">
</span><del>-static inline void epsilonClosureExcludingSelf(const Vector<NFANode>& nfaGraph, unsigned nodeId, unsigned epsilonTransitionCharacter, Vector<unsigned>& output)
</del><ins>+static inline void epsilonClosureExcludingSelf(NFA& nfa, unsigned nodeId, Vector<unsigned>& output)
</ins><span class="cx"> {
</span><del>- const auto& transitions = nfaGraph[nodeId].transitions;
- auto epsilonTransitionSlot = transitions.find(epsilonTransitionCharacter);
-
- if (epsilonTransitionSlot == transitions.end())
- return;
-
</del><span class="cx"> NodeIdSet closure({ nodeId });
</span><del>- Vector<unsigned, 64> unprocessedNodes;
- copyToVector(epsilonTransitionSlot->value, unprocessedNodes);
- closure.add(unprocessedNodes.begin(), unprocessedNodes.end());
- output = unprocessedNodes;
</del><ins>+ Vector<unsigned, 64> unprocessedNodes({ nodeId });
</ins><span class="cx">
</span><span class="cx"> do {
</span><span class="cx"> unsigned unprocessedNodeId = unprocessedNodes.takeLast();
</span><del>- const NFANode& node = nfaGraph[unprocessedNodeId];
- auto epsilonTransitionSlot = node.transitions.find(epsilonTransitionCharacter);
- if (epsilonTransitionSlot != node.transitions.end()) {
- for (unsigned targetNodeId : epsilonTransitionSlot->value) {
- auto addResult = closure.add(targetNodeId);
- if (addResult.isNewEntry) {
- unprocessedNodes.append(targetNodeId);
- output.append(targetNodeId);
- }
</del><ins>+ const auto& node = nfa.nodes[unprocessedNodeId];
+
+ for (uint32_t epsilonTargetIndex = node.epsilonTransitionTargetsStart; epsilonTargetIndex < node.epsilonTransitionTargetsEnd; ++epsilonTargetIndex) {
+ uint32_t targetNodeId = nfa.epsilonTransitionsTargets[epsilonTargetIndex];
+ auto addResult = closure.add(targetNodeId);
+ if (addResult.isNewEntry) {
+ unprocessedNodes.append(targetNodeId);
+ output.append(targetNodeId);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><ins>+
+ output.shrinkToFit();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static void resolveEpsilonClosures(Vector<NFANode>& nfaGraph, unsigned epsilonTransitionCharacter, Vector<Vector<unsigned>>& nfaNodeClosures)
</del><ins>+static void resolveEpsilonClosures(NFA& nfa, Vector<Vector<unsigned>>& nfaNodeClosures)
</ins><span class="cx"> {
</span><del>- unsigned nfaGraphSize = nfaGraph.size();
</del><ins>+ unsigned nfaGraphSize = nfa.nodes.size();
</ins><span class="cx"> nfaNodeClosures.resize(nfaGraphSize);
</span><ins>+
</ins><span class="cx"> for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId)
</span><del>- epsilonClosureExcludingSelf(nfaGraph, nodeId, epsilonTransitionCharacter, nfaNodeClosures[nodeId]);
</del><ins>+ epsilonClosureExcludingSelf(nfa, nodeId, nfaNodeClosures[nodeId]);
</ins><span class="cx">
</span><del>- for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId) {
- if (!nfaNodeClosures[nodeId].isEmpty()) {
- bool epsilonTransitionIsRemoved = nfaGraph[nodeId].transitions.remove(epsilonTransitionCharacter);
- ASSERT_UNUSED(epsilonTransitionIsRemoved, epsilonTransitionIsRemoved);
- }
- }
</del><ins>+ // Every nodes still point to that table, but we won't use it ever again.
+ // Clear it to get back the memory. That's not pretty but memory is important here, we have both
+ // graphs existing at the same time.
+ nfa.epsilonTransitionsTargets.clear();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> static ALWAYS_INLINE void extendSetWithClosure(const Vector<Vector<unsigned>>& nfaNodeClosures, unsigned nodeId, NodeIdSet& set)
</span><span class="lines">@@ -214,9 +211,9 @@
</span><span class="cx"> typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;
</span><span class="cx">
</span><span class="cx"> struct NodeIdSetToUniqueNodeIdSetSource {
</span><del>- NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const NFA& nfa, const NodeIdSet& nodeIdSet)
</ins><span class="cx"> : dfa(dfa)
</span><del>- , nfaGraph(nfaGraph)
</del><ins>+ , nfa(nfa)
</ins><span class="cx"> , nodeIdSet(nodeIdSet)
</span><span class="cx"> {
</span><span class="cx"> // The hashing operation must be independant of the nodeId.
</span><span class="lines">@@ -226,7 +223,7 @@
</span><span class="cx"> this->hash = DefaultHash<unsigned>::Hash::hash(hash);
</span><span class="cx"> }
</span><span class="cx"> DFA& dfa;
</span><del>- const Vector<NFANode>& nfaGraph;
</del><ins>+ const NFA& nfa;
</ins><span class="cx"> const NodeIdSet& nodeIdSet;
</span><span class="cx"> unsigned hash;
</span><span class="cx"> };
</span><span class="lines">@@ -247,14 +244,13 @@
</span><span class="cx"> DFANode newDFANode;
</span><span class="cx">
</span><span class="cx"> HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
</span><ins>+
</ins><span class="cx"> for (unsigned nfaNodeId : source.nodeIdSet) {
</span><del>- const NFANode& nfaNode = source.nfaGraph[nfaNodeId];
- actions.add(nfaNode.finalRuleIds.begin(), nfaNode.finalRuleIds.end());
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- newDFANode.correspondingNFANodes.append(nfaNodeId);
-#endif
</del><ins>+ const auto& nfaNode = source.nfa.nodes[nfaNodeId];
+ for (unsigned actionIndex = nfaNode.actionStart; actionIndex < nfaNode.actionEnd; ++actionIndex)
+ actions.add(source.nfa.actions[actionIndex]);
</ins><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> unsigned actionsStart = source.dfa.actions.size();
</span><span class="cx"> for (uint64_t action : actions)
</span><span class="cx"> source.dfa.actions.append(action);
</span><span class="lines">@@ -298,46 +294,118 @@
</span><span class="cx"> NodeIdSet m_targets[128];
</span><span class="cx"> };
</span><span class="cx">
</span><del>-static inline void populateTransitions(SetTransitions& setTransitions, NodeIdSet& setFallbackTransition, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, const Vector<Vector<unsigned>>& nfaNodeclosures)
</del><ins>+struct DataConverterWithEpsilonClosure {
+ const Vector<Vector<unsigned>>& nfaNodeclosures;
+
+ template<typename Iterable>
+ NFANodeIndexSet convert(const Iterable& iterable)
+ {
+ NFANodeIndexSet result;
+ for (unsigned nodeId : iterable) {
+ result.add(nodeId);
+ const Vector<unsigned>& nodeClosure = nfaNodeclosures[nodeId];
+ result.add(nodeClosure.begin(), nodeClosure.end());
+ }
+ return result;
+ }
+
+ template<typename Iterable>
+ void extend(NFANodeIndexSet& destination, const Iterable& iterable)
+ {
+ for (unsigned nodeId : iterable) {
+ auto addResult = destination.add(nodeId);
+ if (addResult.isNewEntry) {
+ const Vector<unsigned>& nodeClosure = nfaNodeclosures[nodeId];
+ destination.add(nodeClosure.begin(), nodeClosure.end());
+ }
+ }
+ }
+};
+
+static inline void createCombinedTransition(PreallocatedNFANodeRangeList& combinedRangeList, const UniqueNodeIdSetImpl& sourceNodeSet, const NFA& immutableNFA, const Vector<Vector<unsigned>>& nfaNodeclosures)
</ins><span class="cx"> {
</span><del>- ASSERT(!graph.isEmpty());
- ASSERT(setFallbackTransition.isEmpty());
-#if !ASSERT_DISABLED
- for (const NodeIdSet& set : setTransitions)
- ASSERT(set.isEmpty());
-#endif
</del><ins>+ combinedRangeList.clear();
</ins><span class="cx">
</span><del>- Vector<unsigned, 8> allFallbackTransitions;
</del><span class="cx"> const unsigned* buffer = sourceNodeSet.buffer();
</span><ins>+
+ DataConverterWithEpsilonClosure converter { nfaNodeclosures };
</ins><span class="cx"> for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
</span><span class="cx"> unsigned nodeId = buffer[i];
</span><del>- const NFANode& nfaSourceNode = graph[nodeId];
- for (unsigned targetTransition : nfaSourceNode.transitionsOnAnyCharacter)
- allFallbackTransitions.append(targetTransition);
</del><ins>+ auto transitions = immutableNFA.transitionsForNode(nodeId);
+ combinedRangeList.extend(transitions.begin(), transitions.end(), converter);
</ins><span class="cx"> }
</span><del>- for (unsigned targetNodeId : allFallbackTransitions) {
- auto addResult = setFallbackTransition.add(targetNodeId);
- if (addResult.isNewEntry)
- extendSetWithClosure(nfaNodeclosures, targetNodeId, setFallbackTransition);
</del><ins>+}
+
+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;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
- unsigned nodeId = buffer[i];
- for (const auto& transitionSlot : graph[nodeId].transitions) {
- NodeIdSet& targetSet = setTransitions[transitionSlot.key];
- for (unsigned targetNodId : transitionSlot.value) {
- targetSet.add(targetNodId);
- extendSetWithClosure(nfaNodeclosures, targetNodId, targetSet);
- }
- if (transitionSlot.key)
- targetSet.add(setFallbackTransition.begin(), setFallbackTransition.end());
</del><ins>+ 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;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><ins>+ return bestTarget;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
</del><ins>+static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const NFA& nfa, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
</ins><span class="cx"> {
</span><del>- NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, nfaNodeSet);
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfa, nfaNodeSet);
</ins><span class="cx"> auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx"> if (uniqueNodeIdAddResult.isNewEntry)
</span><span class="cx"> unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
</span><span class="lines">@@ -347,60 +415,63 @@
</span><span class="cx">
</span><span class="cx"> DFA NFAToDFA::convert(NFA& nfa)
</span><span class="cx"> {
</span><ins>+ Vector<Vector<unsigned>> nfaNodeClosures;
+ resolveEpsilonClosures(nfa, nfaNodeClosures);
+
</ins><span class="cx"> DFA dfa;
</span><del>- Vector<NFANode>& nfaGraph = nfa.m_nodes;
</del><span class="cx">
</span><del>- Vector<Vector<unsigned>> nfaNodeClosures;
- resolveEpsilonClosures(nfaGraph, NFA::epsilonTransitionCharacter, nfaNodeClosures);
-
</del><span class="cx"> NodeIdSet initialSet({ nfa.root() });
</span><span class="cx"> extendSetWithClosure(nfaNodeClosures, nfa.root(), initialSet);
</span><span class="cx">
</span><span class="cx"> UniqueNodeIdSetTable uniqueNodeIdSetTable;
</span><span class="cx">
</span><del>- NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, initialSet);
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfa, initialSet);
</ins><span class="cx"> auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx">
</span><span class="cx"> Vector<UniqueNodeIdSetImpl*> unprocessedNodes;
</span><span class="cx"> unprocessedNodes.append(addResult.iterator->impl());
</span><span class="cx">
</span><del>- SetTransitions transitionsFromClosedSet;
-
</del><ins>+ PreallocatedNFANodeRangeList combinedRangeList;
+ Vector<unsigned, 128> rangeToTarget;
</ins><span class="cx"> do {
</span><span class="cx"> UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
</span><ins>+ createCombinedTransition(combinedRangeList, *uniqueNodeIdSetImpl, nfa, nfaNodeClosures);
</ins><span class="cx">
</span><del>- unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
- NodeIdSet setFallbackTransition;
- populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);
</del><ins>+ rangeToTarget.clear();
+ for (const NFANodeRange& range : combinedRangeList) {
+ unsigned targetNodeId = getOrCreateDFANode(range.data, nfa, dfa, uniqueNodeIdSetTable, unprocessedNodes);
+ rangeToTarget.append(targetNodeId);
+ }
</ins><span class="cx">
</span><ins>+ bool useFallbackTransition = canUseFallbackTransition(combinedRangeList);
+ uint32_t preferedFallbackTarget = 0;
+ if (useFallbackTransition)
+ preferedFallbackTarget = findBestFallbackTarget(combinedRangeList, rangeToTarget);
+
</ins><span class="cx"> unsigned transitionsStart = dfa.transitionCharacters.size();
</span><del>- ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());
- for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {
- NodeIdSet& targetNodeSet = transitionsFromClosedSet[key];
</del><ins>+ unsigned rangeToTargetIndex = 0;
</ins><span class="cx">
</span><del>- if (targetNodeSet.isEmpty())
- continue;
</del><ins>+ for (const NFANodeRange& range : combinedRangeList) {
+ unsigned targetNodeId = rangeToTarget[rangeToTargetIndex];
</ins><span class="cx">
</span><del>- unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);
- RELEASE_ASSERT(key <= 127);
- dfa.transitionCharacters.append(static_cast<uint8_t>(key));
- dfa.transitionDestinations.append(targetNodeId);
-
- targetNodeSet.clear();
</del><ins>+ 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;
</ins><span class="cx"> }
</span><span class="cx"> unsigned transitionsEnd = dfa.transitionCharacters.size();
</span><del>- ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());
</del><span class="cx"> unsigned transitionsLength = transitionsEnd - transitionsStart;
</span><del>- RELEASE_ASSERT(transitionsLength <= 127);
- dfa.nodes[dfaNodeId].setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
-
- if (!setFallbackTransition.isEmpty()) {
- unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);
- DFANode& dfaSourceNode = dfa.nodes[dfaNodeId];
- dfaSourceNode.addFallbackTransition(dfa, targetNodeId);
- }
</del><ins>+ unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
+ DFANode& dfaSourceNode = dfa.nodes[dfaNodeId];
+ ASSERT_WITH_MESSAGE(transitionsLength < 127, "Transitions covering the entire alphabet should use a fallback transition");
+ dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
+
+ if (useFallbackTransition)
+ dfaSourceNode.addFallbackTransition(dfa, preferedFallbackTarget);
</ins><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><del>-
</del><span class="cx"> return dfa;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.h (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -34,7 +34,7 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-class NFA;
</del><ins>+struct NFA;
</ins><span class="cx">
</span><span class="cx"> // NFAToDFA provides a way to build a DFA corresponding to a NFA.
</span><span class="cx"> class NFAToDFA {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsTermh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/Term.h (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/Term.h 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Source/WebCore/contentextensions/Term.h 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -86,7 +86,7 @@
</span><span class="cx">
</span><span class="cx"> void quantify(const AtomQuantifier&);
</span><span class="cx">
</span><del>- unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
</del><ins>+ ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const;
</ins><span class="cx">
</span><span class="cx"> bool isEndOfLineAssertion() const;
</span><span class="cx">
</span><span class="lines">@@ -118,7 +118,7 @@
</span><span class="cx"> // The return value can be false for a group equivalent to a universal transition.
</span><span class="cx"> bool isUniversalTransition() const;
</span><span class="cx">
</span><del>- unsigned generateSubgraphForAtom(NFA&, unsigned source) const;
</del><ins>+ ImmutableCharNFANodeBuilder generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source) const;
</ins><span class="cx">
</span><span class="cx"> void destroy();
</span><span class="cx">
</span><span class="lines">@@ -286,7 +286,7 @@
</span><span class="cx"> : m_termType(TermType::CharacterSet)
</span><span class="cx"> {
</span><span class="cx"> new (NotNull, &m_atomData.characterSet) CharacterSet();
</span><del>- for (UChar i = 0; i < 128; ++i)
</del><ins>+ for (UChar i = 1; i < 128; ++i)
</ins><span class="cx"> m_atomData.characterSet.set(i);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -395,11 +395,11 @@
</span><span class="cx"> m_quantifier = quantifier;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
</del><ins>+inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(isValid());
</span><span class="cx">
</span><del>- unsigned newEnd;
</del><ins>+ ImmutableCharNFANodeBuilder newEnd;
</ins><span class="cx">
</span><span class="cx"> switch (m_quantifier) {
</span><span class="cx"> case AtomQuantifier::One: {
</span><span class="lines">@@ -408,36 +408,36 @@
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrOne: {
</span><span class="cx"> newEnd = generateSubgraphForAtom(nfa, start);
</span><del>- nfa.addEpsilonTransition(start, newEnd);
</del><ins>+ start.addEpsilonTransition(newEnd);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrMore: {
</span><del>- unsigned repeatStart = nfa.createNode();
- nfa.addEpsilonTransition(start, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatStart(nfa);
+ start.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
- nfa.addEpsilonTransition(repeatEnd, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+ repeatEnd.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- unsigned kleenEnd = nfa.createNode();
- nfa.addEpsilonTransition(repeatEnd, kleenEnd);
- nfa.addEpsilonTransition(start, kleenEnd);
- newEnd = kleenEnd;
</del><ins>+ ImmutableCharNFANodeBuilder kleenEnd(nfa);
+ repeatEnd.addEpsilonTransition(kleenEnd);
+ start.addEpsilonTransition(kleenEnd);
+ newEnd = WTF::move(kleenEnd);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::OneOrMore: {
</span><del>- unsigned repeatStart = nfa.createNode();
- nfa.addEpsilonTransition(start, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatStart(nfa);
+ start.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
- nfa.addEpsilonTransition(repeatEnd, repeatStart);
</del><ins>+ ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+ repeatEnd.addEpsilonTransition(repeatStart);
</ins><span class="cx">
</span><del>- unsigned afterRepeat = nfa.createNode();
- nfa.addEpsilonTransition(repeatEnd, afterRepeat);
- newEnd = afterRepeat;
</del><ins>+ ImmutableCharNFANodeBuilder afterRepeat(nfa);
+ repeatEnd.addEpsilonTransition(afterRepeat);
+ newEnd = WTF::move(afterRepeat);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><del>- nfa.setActions(newEnd, finalActions);
</del><ins>+ newEnd.setActions(finalActions.begin(), finalActions.end());
</ins><span class="cx"> return newEnd;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -612,36 +612,61 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline unsigned Term::generateSubgraphForAtom(NFA& nfa, unsigned source) const
</del><ins>+inline ImmutableCharNFANodeBuilder Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source) const
</ins><span class="cx"> {
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><span class="cx"> case TermType::Deleted:
</span><span class="cx"> ASSERT_NOT_REACHED();
</span><del>- return -1;
</del><ins>+ return ImmutableCharNFANodeBuilder();
</ins><span class="cx"> case TermType::CharacterSet: {
</span><del>- unsigned target = nfa.createNode();
- if (isUniversalTransition())
- nfa.addTransitionsOnAnyCharacter(source, target);
- else {
- if (!m_atomData.characterSet.inverted()) {
- for (UChar i = 0; i < 128; ++i) {
- if (m_atomData.characterSet.get(i))
- nfa.addTransition(source, target, static_cast<char>(i));
- }
- } else {
- for (UChar i = 1; i < 128; ++i) {
- if (!m_atomData.characterSet.get(i))
- nfa.addTransition(source, target, static_cast<char>(i));
- }
</del><ins>+ ImmutableCharNFANodeBuilder newNode(nfa);
+ if (!m_atomData.characterSet.inverted()) {
+ UChar i = 0;
+ while (true) {
+ while (i < 128 && !m_atomData.characterSet.get(i))
+ ++i;
+ if (i == 128)
+ break;
+
+ UChar start = i;
+ ++i;
+ while (i < 128 && m_atomData.characterSet.get(i))
+ ++i;
+ source.addTransition(start, i - 1, newNode);
</ins><span class="cx"> }
</span><ins>+ } else {
+ UChar i = 1;
+ while (true) {
+ while (i < 128 && m_atomData.characterSet.get(i))
+ ++i;
+ if (i == 128)
+ break;
+
+ UChar start = i;
+ ++i;
+ while (i < 128 && !m_atomData.characterSet.get(i))
+ ++i;
+ source.addTransition(start, i - 1, newNode);
+ }
</ins><span class="cx"> }
</span><del>- return target;
</del><ins>+ return newNode;
</ins><span class="cx"> }
</span><span class="cx"> case TermType::Group: {
</span><del>- unsigned lastTarget = source;
- for (const Term& term : m_atomData.group.terms)
- lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
</del><ins>+ if (m_atomData.group.terms.isEmpty()) {
+ // FIXME: any kind of empty term could be avoided in the parser. This case should turned into an assertion.
+ ImmutableCharNFANodeBuilder newNode(nfa);
+ source.addEpsilonTransition(newNode);
+ return newNode;
+ }
+
+ ImmutableCharNFANodeBuilder lastTarget = m_atomData.group.terms.first().generateGraph(nfa, source, ActionList());
+ for (unsigned i = 1; i < m_atomData.group.terms.size(); ++i) {
+ const Term& currentTerm = m_atomData.group.terms[i];
+ ImmutableCharNFANodeBuilder newNode = currentTerm.generateGraph(nfa, lastTarget, ActionList());
+ lastTarget = WTF::move(newNode);
+ }
+
</ins><span class="cx"> return lastTarget;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Tools/ChangeLog 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -1,3 +1,13 @@
</span><ins>+2015-06-29 Benjamin Poulain <benjamin@webkit.org>
+
+ Make the NFA transitions range-based
+ https://bugs.webkit.org/show_bug.cgi?id=146338
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ Test some new interesting cases.
+
</ins><span class="cx"> 2015-06-28 Dan Bernstein <mitz@apple.com>
</span><span class="cx">
</span><span class="cx"> [Xcode] Use the same environment for command-line and IDE builds
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (186078 => 186079)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-06-29 19:12:29 UTC (rev 186078)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-06-29 19:40:12 UTC (rev 186079)
</span><span class="lines">@@ -304,6 +304,38 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("http://webkit.org/fobar"), { });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, EmptyGroups)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://webkit\\\\.org/foo()bar\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://webkit\\\\.org/((me)()(too))\"}}]");
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foo"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bar"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/me"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/too"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/metoo"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foome"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foomebar"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/mefoo"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/mefootoo"), { });
+}
+
+TEST_F(ContentExtensionTest, QuantifiedEmptyGroups)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://webkit\\\\.org/foo()+bar\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^http://webkit\\\\.org/(()*()?(target)()+)\"}}]");
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foo"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bar"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/me"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/too"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/target"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foome"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foomebar"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/mefoo"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/mefootoo"), { });
+}
+
</ins><span class="cx"> TEST_F(ContentExtensionTest, MatchPastEndOfString)
</span><span class="cx"> {
</span><span class="cx"> auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".+\"}}]");
</span><span class="lines">@@ -359,6 +391,16 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("http://webkit.org/foobarY"), { });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, DotDoesNotIncludeEndOfLine)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"https://webkit\\\\.org/.\"}}]");
+
+ testRequest(backend, mainDocumentRequest("https://webkit.org/foobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("https://webkit.org/A"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("https://webkit.org/z"), { ContentExtensions::ActionType::BlockLoad });
+}
+
</ins><span class="cx"> TEST_F(ContentExtensionTest, PrefixInfixSuffixExactMatch)
</span><span class="cx"> {
</span><span class="cx"> auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"infix\"}},"
</span><span class="lines">@@ -1368,4 +1410,524 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("bbbb://www.webkit.org/"), { });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+// *** We have the following ranges intersections: ***
+// Full overlap.
+// 1)
+// A: |-----|
+// B: |---|
+// 2)
+// A: |-----|
+// B: |
+// 3)
+// A: |---|
+// B: |-----|
+// 4)
+// A: |
+// B: |-----|
+// One edge in common
+// 5)
+// A: |-|
+// B: |-|
+// 6)
+// A: |
+// B: |-|
+// 7)
+// A: |-|
+// B: |
+// 8)
+// A: |-|
+// B: |-|
+// 9)
+// A: |
+// B: |-|
+// 10)
+// A: |-|
+// B: |
+// B overlap on the left side of A.
+// 11)
+// A: |---|
+// B: |---|
+// 12)
+// A: |---|
+// B: |-----|
+// A overlap on the left side of B
+// 13)
+// A: |---|
+// B: |---|
+// 14)
+// A: |-----|
+// B: |---|
+// Equal ranges
+// 15)
+// A: |---|
+// B: |---|
+// 16)
+// A: |
+// B: |
+
+TEST_F(ContentExtensionTest, RangeOverlapCase1)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"^[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\":\"[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase2)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"^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\":\"[a-m]\"}},"
+ "{\"action\":{\"type\":\"ignore-previous-rules\"},\"trigger\":{\"url-filter\":\"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, RangeOverlapCase3)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase4)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^l\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"l\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase5)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase6)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase7)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^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\":\"[a-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"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, RangeOverlapCase8)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase9)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"e\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase10)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^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\":\"[e-h]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"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, RangeOverlapCase11)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase12)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[e-g]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase13)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[b-d]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase14)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[b-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[b-e]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase15)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^[c-f]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^[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\":\"[c-f]\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, RangeOverlapCase16)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^c\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"^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\":\"c\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"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, QuantifiedOneOrMoreRangesCase11And13)
+{
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"[c-e]+[g-i]+YYY\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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, QuantifiedOneOrMoreRangesCase11And13InGroups)
+{
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"([c-e])+([g-i]+YYY)\"}},"
+ "{\"action\":{\"type\":\"css-display-none\",\"selector\":\".hidden\"},\"trigger\":{\"url-filter\":\"[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>
</div>
</body>
</html>