Make the NFA transitions range-based
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 29 Jun 2015 19:40:12 +0000 (19:40 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 29 Jun 2015 19:40:12 +0000 (19:40 +0000)
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@186079 268f45cc-cd09-0410-ab3c-d52691b4dbfc

18 files changed:
Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/contentextensions/CombinedURLFilters.cpp
Source/WebCore/contentextensions/ContentExtensionCompiler.cpp
Source/WebCore/contentextensions/DFA.cpp
Source/WebCore/contentextensions/DFA.h
Source/WebCore/contentextensions/ImmutableNFA.h [new file with mode: 0644]
Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h [new file with mode: 0644]
Source/WebCore/contentextensions/MutableRange.h [new file with mode: 0644]
Source/WebCore/contentextensions/MutableRangeList.h [new file with mode: 0644]
Source/WebCore/contentextensions/NFA.cpp
Source/WebCore/contentextensions/NFA.h
Source/WebCore/contentextensions/NFANode.h
Source/WebCore/contentextensions/NFAToDFA.cpp
Source/WebCore/contentextensions/NFAToDFA.h
Source/WebCore/contentextensions/Term.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp

index ee79778..dc8d14f 100644 (file)
@@ -1,3 +1,186 @@
+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.
+
 2015-06-29  Youenn Fablet  <youenn.fablet@crf.canon.fr>
 
         Binding generator should allow using JSC::Value for "any" parameter in lieu of ScriptValue
index fd36302..a484c79 100644 (file)
                26F0C89F1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C89D1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp */; };
                26F0C8A01A2EC3BE002794F8 /* ContentExtensionsBackend.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F0C89E1A2EC3BE002794F8 /* ContentExtensionsBackend.h */; settings = {ATTRIBUTES = (Private, ); }; };
                26F40D4A14904A6300CA67C4 /* EventLoopIOS.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26F40D4914904A6300CA67C4 /* EventLoopIOS.mm */; };
+               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, ); }; };
                26F9A83818A046AC00AEB88A /* ViewportConfiguration.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F9A83618A046AC00AEB88A /* ViewportConfiguration.cpp */; };
                26F9A83918A046AC00AEB88A /* ViewportConfiguration.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F9A83718A046AC00AEB88A /* ViewportConfiguration.h */; settings = {ATTRIBUTES = (Private, ); }; };
                26FAE4CC1852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26FAE4C81852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp */; };
                26F0C89D1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionsBackend.cpp; sourceTree = "<group>"; };
                26F0C89E1A2EC3BE002794F8 /* ContentExtensionsBackend.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContentExtensionsBackend.h; sourceTree = "<group>"; };
                26F40D4914904A6300CA67C4 /* EventLoopIOS.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = EventLoopIOS.mm; sourceTree = "<group>"; };
+               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>"; };
                26F9A83618A046AC00AEB88A /* ViewportConfiguration.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ViewportConfiguration.cpp; sourceTree = "<group>"; };
                26F9A83718A046AC00AEB88A /* ViewportConfiguration.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ViewportConfiguration.h; sourceTree = "<group>"; };
                26FAE4C81852E3A5004C8C46 /* ResourceHandleCFURLConnectionDelegate.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ResourceHandleCFURLConnectionDelegate.cpp; sourceTree = "<group>"; };
                                26A517FB1AB92238006335DF /* DFAMinimizer.cpp */,
                                26A517FC1AB92238006335DF /* DFAMinimizer.h */,
                                267725F91A5B3AD9003C24DD /* DFANode.h */,
+                               26F756B21B3B66F70005DD79 /* ImmutableNFA.h */,
+                               26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */,
+                               26F756AE1B3B65AC0005DD79 /* MutableRange.h */,
+                               26F756AF1B3B65AC0005DD79 /* MutableRangeList.h */,
                                269397251A4A5FBD00E8349D /* NFA.cpp */,
                                269397231A4A5B6400E8349D /* NFA.h */,
                                269397201A4A412F00E8349D /* NFANode.h */,
                                62CD325A1157E57C0063B0A7 /* CustomEvent.h in Headers */,
                                A8CB413E0E8633FD0032C4F0 /* DashArray.h in Headers */,
                                A80E6D0B0A1989CA007FB8C5 /* DashboardRegion.h in Headers */,
+                               26F756B01B3B65AC0005DD79 /* MutableRange.h in Headers */,
                                97BC6A211505F081001B74AC /* Database.h in Headers */,
                                97BC6A241505F081001B74AC /* DatabaseAuthorizer.h in Headers */,
                                FE16CFD4169D1DED00D3A0C7 /* DatabaseBackend.h in Headers */,
                                85909CE40ACC7A7E00DF01F1 /* DOMCSSUnknownRuleInternal.h in Headers */,
                                858C381C0AA8E29600B187A4 /* DOMCSSValue.h in Headers */,
                                85B498F30ADB336A00925CBB /* DOMCSSValueInternal.h in Headers */,
+                               26F756B31B3B66F70005DD79 /* ImmutableNFA.h in Headers */,
                                858C383C0AA8ED8200B187A4 /* DOMCSSValueList.h in Headers */,
                                85909D2B0ACC7D5500DF01F1 /* DOMCSSValueListInternal.h in Headers */,
                                E10B9CCC0B747A44003ED890 /* DOMCustomXPathNSResolver.h in Headers */,
                                BCEA486E097D93020094C9E4 /* RenderDeprecatedFlexibleBox.h in Headers */,
                                D302754A12A5FE84004BD828 /* RenderDetailsMarker.h in Headers */,
                                A76E5F7F135E0DCF00A69837 /* RenderedDocumentMarker.h in Headers */,
+                               26F756B51B3B68F20005DD79 /* ImmutableNFANodeBuilder.h in Headers */,
                                9B32CDA913DF7FA900F34D13 /* RenderedPosition.h in Headers */,
                                E43A023B17EB370A004CDD25 /* RenderElement.h in Headers */,
                                0F5B7A5510F65D7A00376302 /* RenderEmbeddedObject.h in Headers */,
                                B2227A810D00BF220071B782 /* SVGPathSegList.h in Headers */,
                                8476C9E611DF6A0B00555B02 /* SVGPathSegListBuilder.h in Headers */,
                                084A0829128D7867002DB1F1 /* SVGPathSegListPropertyTearOff.h in Headers */,
+                               26F756B11B3B65AC0005DD79 /* MutableRangeList.h in Headers */,
                                84B6B978120F13E500B8EFAF /* SVGPathSegListSource.h in Headers */,
                                83C1D435178D5AB500141E68 /* SVGPathSegMovetoAbs.h in Headers */,
                                83C1D436178D5AB500141E68 /* SVGPathSegMovetoRel.h in Headers */,
index c13d775..b6e4b0a 100644 (file)
@@ -193,25 +193,25 @@ void CombinedURLFilters::addPattern(uint64_t actionId, const Vector<Term>& patte
         actions.append(actionId);
 }
 
-static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex& root, size_t maxNFASize)
+static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, size_t maxNFASize)
 {
     // This recurses the subtree of the prefix tree.
     // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph,
     // recurses into children, and deletes any processed leaf nodes.
     struct ActiveSubtree {
-        ActiveSubtree(PrefixTreeVertex& vertex, unsigned nfaNodeId, unsigned edgeIndex)
+        ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
             : vertex(vertex)
-            , nfaNodeId(nfaNodeId)
+            , nfaNode(WTF::move(nfaNode))
             , edgeIndex(edgeIndex)
         {
         }
         PrefixTreeVertex& vertex;
-        unsigned nfaNodeId;
+        ImmutableCharNFANodeBuilder nfaNode;
         unsigned edgeIndex;
     };
     Vector<ActiveSubtree> stack;
     if (!root.edges.isEmpty())
-        stack.append(ActiveSubtree(root, nfaRootId, 0));
+        stack.append(ActiveSubtree(root, WTF::move(subtreeRoot), 0));
     bool nfaTooBig = false;
     
     // Generate graphs for each subtree that does not contain any quantifiers.
@@ -220,7 +220,7 @@ static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex
         const unsigned edgeIndex = stack.last().edgeIndex;
         
         // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
-        if (vertex.edges.isEmpty() && nfa.graphSize() > maxNFASize)
+        if (vertex.edges.isEmpty() && nfa.nodes.size() > maxNFASize)
             nfaTooBig = true;
         
         if (edgeIndex < vertex.edges.size()) {
@@ -237,10 +237,10 @@ static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex
                 stack.last().edgeIndex++;
                 continue;
             }
-            
-            unsigned subtreeRootId = edge.term.generateGraph(nfa, stack.last().nfaNodeId, edge.child->finalActions);
+
+            ImmutableCharNFANodeBuilder newNode = edge.term.generateGraph(nfa, stack.last().nfaNode, edge.child->finalActions);
             ASSERT(edge.child.get());
-            stack.append(ActiveSubtree(*edge.child.get(), subtreeRootId, 0));
+            stack.append(ActiveSubtree(*edge.child.get(), WTF::move(newNode), 0));
         } else {
             ASSERT(edgeIndex == vertex.edges.size());
             vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
@@ -286,22 +286,26 @@ void CombinedURLFilters::processNFAs(size_t maxNFASize, std::function<void(NFA&&
             stack.removeLast();
         }
         ASSERT_WITH_MESSAGE(!stack.isEmpty(), "At least the root should be in the stack");
-        
+
         // Make an NFA with the subtrees for whom this is also the last quantifier (or who also have no quantifier).
         NFA nfa;
-        // 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);
+        {
+            // 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);
         }
-        // Put the non-quantified vertices in the subtree into the NFA and delete them.
-        ASSERT(stack.last());
-        generateNFAForSubtree(nfa, prefixEnd, *stack.last(), maxNFASize);
-        
+        nfa.finalize();
+
         handler(WTF::move(nfa));
-        
+
         // Clean up any processed leaf nodes.
         while (true) {
             if (stack.size() > 1) {
index 325f73d..9830e4f 100644 (file)
@@ -309,9 +309,7 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, Strin
         // Our bytecode interpreter expects to have at least one DFA, so if we haven't seen any
         // create a dummy one and add any universal actions.
 
-        NFA dummyNFA;
-        DFA dummyDFA = NFAToDFA::convert(dummyNFA);
-
+        DFA dummyDFA = DFA::empty();
         addUniversalActionsToDFA(dummyDFA, universalActionsWithoutDomains);
 
         Vector<DFABytecode> bytecode;
@@ -376,10 +374,8 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, Strin
     if (!firstNFAWithDomainsSeen) {
         // Our bytecode interpreter expects to have at least one DFA, so if we haven't seen any
         // create a dummy one and add any universal actions.
-        
-        NFA dummyNFA;
-        DFA dummyDFA = NFAToDFA::convert(dummyNFA);
-        
+
+        DFA dummyDFA = DFA::empty();
         addUniversalActionsToDFA(dummyDFA, universalActionsWithDomains);
         
         Vector<DFABytecode> bytecode;
index 5c3d365..0ee04d9 100644 (file)
@@ -35,6 +35,13 @@ namespace WebCore {
 
 namespace ContentExtensions {
 
+DFA DFA::empty()
+{
+    DFA newDFA;
+    newDFA.nodes.append(DFANode());
+    return newDFA;
+}
+
 size_t DFA::memoryUsed() const
 {
     return sizeof(DFA)
index 3ebca71..188dfb4 100644 (file)
@@ -38,6 +38,8 @@ namespace ContentExtensions {
 
 // The DFA abstract a partial DFA graph in a compact form.
 struct WEBCORE_EXPORT DFA {
+    static DFA empty();
+
     void minimize();
     unsigned graphSize() const;
     size_t memoryUsed() const;
diff --git a/Source/WebCore/contentextensions/ImmutableNFA.h b/Source/WebCore/contentextensions/ImmutableNFA.h
new file mode 100644 (file)
index 0000000..1f2034f
--- /dev/null
@@ -0,0 +1,173 @@
+/*
+ * 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
diff --git a/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h b/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h
new file mode 100644 (file)
index 0000000..45414be
--- /dev/null
@@ -0,0 +1,244 @@
+/*
+ * 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
diff --git a/Source/WebCore/contentextensions/MutableRange.h b/Source/WebCore/contentextensions/MutableRange.h
new file mode 100644 (file)
index 0000000..35d142b
--- /dev/null
@@ -0,0 +1,102 @@
+/*
+ * 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
diff --git a/Source/WebCore/contentextensions/MutableRangeList.h b/Source/WebCore/contentextensions/MutableRangeList.h
new file mode 100644 (file)
index 0000000..cb12898
--- /dev/null
@@ -0,0 +1,261 @@
+/*
+ * 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
index b301884..5df0846 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(CONTENT_EXTENSIONS)
 
+#include <wtf/ASCIICType.h>
 #include <wtf/DataLog.h>
 #include <wtf/HashSet.h>
 
@@ -35,184 +36,85 @@ namespace WebCore {
 
 namespace ContentExtensions {
 
-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);
-}
-
 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
-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);
-}
-
 void NFA::debugPrintDot() const
 {
     dataLogF("digraph NFA_Transitions {\n");
     dataLogF("    rankdir=LR;\n");
     dataLogF("    node [shape=circle];\n");
     dataLogF("    {\n");
-    for (unsigned i = 0; i < m_nodes.size(); ++i) {
+
+    for (unsigned i = 0; i < nodes.size(); ++i) {
         dataLogF("         %d [label=<Node %d", i, i);
 
-        const ActionList& finalRules = m_nodes[i].finalRuleIds;
-        if (!finalRules.isEmpty()) {
+        const auto& node = nodes[i];
+
+        if (node.actionStart != node.actionEnd) {
             dataLogF("<BR/>(Final: ");
-            for (unsigned ruleIndex = 0; ruleIndex < finalRules.size(); ++ruleIndex) {
-                if (ruleIndex)
+            bool isFirst = true;
+            for (unsigned actionIndex = node.actionStart; actionIndex < node.actionEnd; ++actionIndex) {
+                if (!isFirst)
                     dataLogF(", ");
-                dataLogF("%llu", finalRules[ruleIndex]);
+                dataLogF("%llu", actions[actionIndex]);
+                isFirst = false;
             }
             dataLogF(")");
         }
-
         dataLogF(">]");
 
-        if (!finalRules.isEmpty())
+        if (node.actionStart != node.actionEnd)
             dataLogF(" [shape=doublecircle]");
-
         dataLogF(";\n");
     }
     dataLogF("    }\n");
 
     dataLogF("    {\n");
-    for (unsigned i = 0; i < m_nodes.size(); ++i)
-        printTransitions(m_nodes, i, epsilonTransitionCharacter);
+    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);
+        }
+    }
+
     dataLogF("    }\n");
     dataLogF("}\n");
 }
index 4e4c228..b9bfc26 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(CONTENT_EXTENSIONS)
 
 #include "ContentExtensionsDebugging.h"
+#include "ImmutableNFANodeBuilder.h"
 #include "NFANode.h"
 #include <wtf/Vector.h>
 
@@ -36,42 +37,13 @@ namespace WebCore {
 
 namespace ContentExtensions {
 
-class NFAToDFA;
-
-// 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);
+typedef ImmutableRange<char> ImmutableCharRange;
+typedef ImmutableNFANodeBuilder<char, uint64_t> ImmutableCharNFANodeBuilder;
 
+struct NFA : public ImmutableNFA<char, uint64_t> {
 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
-    void addRuleId(unsigned node, const ActionList& ruleIds);
-
     void debugPrintDot() const;
-#else
-    void addRuleId(unsigned, uint64_t) { }
 #endif
-#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;
 };
 
 }
index 8cdac29..6f43c38 100644 (file)
@@ -45,7 +45,7 @@ typedef HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::Uns
 
 class NFANode {
 public:
-    HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> transitions;
+    NFANodeTransitions transitions;
     NFANodeIndexSet transitionsOnAnyCharacter;
 
     ActionList finalRuleIds;
index 945f56a..6a2b3e4 100644 (file)
@@ -30,6 +30,8 @@
 
 #include "ContentExtensionsDebugging.h"
 #include "DFANode.h"
+#include "ImmutableNFA.h"
+#include "MutableRangeList.h"
 #include "NFA.h"
 #include <wtf/DataLog.h>
 #include <wtf/HashMap.h>
@@ -39,53 +41,48 @@ namespace WebCore {
 
 namespace ContentExtensions {
 
+typedef MutableRange<char, NFANodeIndexSet> NFANodeRange;
+typedef MutableRangeList<char, NFANodeIndexSet> NFANodeRangeList;
+typedef MutableRangeList<char, NFANodeIndexSet, 128> PreallocatedNFANodeRangeList;
+
 // FIXME: set a better initial size.
 // FIXME: include the hash inside NodeIdSet.
 typedef NFANodeIndexSet NodeIdSet;
 
-static inline void epsilonClosureExcludingSelf(const Vector<NFANode>& nfaGraph, unsigned nodeId, unsigned epsilonTransitionCharacter, Vector<unsigned>& output)
+static inline void epsilonClosureExcludingSelf(NFA& nfa, unsigned nodeId, Vector<unsigned>& output)
 {
-    const auto& transitions = nfaGraph[nodeId].transitions;
-    auto epsilonTransitionSlot = transitions.find(epsilonTransitionCharacter);
-
-    if (epsilonTransitionSlot == transitions.end())
-        return;
-
     NodeIdSet closure({ nodeId });
-    Vector<unsigned, 64> unprocessedNodes;
-    copyToVector(epsilonTransitionSlot->value, unprocessedNodes);
-    closure.add(unprocessedNodes.begin(), unprocessedNodes.end());
-    output = unprocessedNodes;
+    Vector<unsigned, 64> unprocessedNodes({ nodeId });
 
     do {
         unsigned unprocessedNodeId = unprocessedNodes.takeLast();
-        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);
-                }
+        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);
             }
         }
     } while (!unprocessedNodes.isEmpty());
+
+    output.shrinkToFit();
 }
 
-static void resolveEpsilonClosures(Vector<NFANode>& nfaGraph, unsigned epsilonTransitionCharacter, Vector<Vector<unsigned>>& nfaNodeClosures)
+static void resolveEpsilonClosures(NFA& nfa, Vector<Vector<unsigned>>& nfaNodeClosures)
 {
-    unsigned nfaGraphSize = nfaGraph.size();
+    unsigned nfaGraphSize = nfa.nodes.size();
     nfaNodeClosures.resize(nfaGraphSize);
+
     for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId)
-        epsilonClosureExcludingSelf(nfaGraph, nodeId, epsilonTransitionCharacter, nfaNodeClosures[nodeId]);
+        epsilonClosureExcludingSelf(nfa, nodeId, nfaNodeClosures[nodeId]);
 
-    for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId) {
-        if (!nfaNodeClosures[nodeId].isEmpty()) {
-            bool epsilonTransitionIsRemoved = nfaGraph[nodeId].transitions.remove(epsilonTransitionCharacter);
-            ASSERT_UNUSED(epsilonTransitionIsRemoved, epsilonTransitionIsRemoved);
-        }
-    }
+    // 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();
 }
 
 static ALWAYS_INLINE void extendSetWithClosure(const Vector<Vector<unsigned>>& nfaNodeClosures, unsigned nodeId, NodeIdSet& set)
@@ -214,9 +211,9 @@ struct UniqueNodeIdSetHashHashTraits : public WTF::CustomHashTraits<UniqueNodeId
 typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;
 
 struct NodeIdSetToUniqueNodeIdSetSource {
-    NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)
+    NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const NFA& nfa, const NodeIdSet& nodeIdSet)
         : dfa(dfa)
-        , nfaGraph(nfaGraph)
+        , nfa(nfa)
         , nodeIdSet(nodeIdSet)
     {
         // The hashing operation must be independant of the nodeId.
@@ -226,7 +223,7 @@ struct NodeIdSetToUniqueNodeIdSetSource {
         this->hash = DefaultHash<unsigned>::Hash::hash(hash);
     }
     DFA& dfa;
-    const Vector<NFANode>& nfaGraph;
+    const NFA& nfa;
     const NodeIdSet& nodeIdSet;
     unsigned hash;
 };
@@ -247,14 +244,13 @@ struct NodeIdSetToUniqueNodeIdSetTranslator {
         DFANode newDFANode;
 
         HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
+
         for (unsigned nfaNodeId : source.nodeIdSet) {
-            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
+            const auto& nfaNode = source.nfa.nodes[nfaNodeId];
+            for (unsigned actionIndex = nfaNode.actionStart; actionIndex < nfaNode.actionEnd; ++actionIndex)
+                actions.add(source.nfa.actions[actionIndex]);
         }
-        
+
         unsigned actionsStart = source.dfa.actions.size();
         for (uint64_t action : actions)
             source.dfa.actions.append(action);
@@ -298,46 +294,118 @@ private:
     NodeIdSet m_targets[128];
 };
 
-static inline void populateTransitions(SetTransitions& setTransitions, NodeIdSet& setFallbackTransition, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, const Vector<Vector<unsigned>>& nfaNodeclosures)
+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)
 {
-    ASSERT(!graph.isEmpty());
-    ASSERT(setFallbackTransition.isEmpty());
-#if !ASSERT_DISABLED
-    for (const NodeIdSet& set : setTransitions)
-        ASSERT(set.isEmpty());
-#endif
-
-    Vector<unsigned, 8> allFallbackTransitions;
+    combinedRangeList.clear();
+
     const unsigned* buffer = sourceNodeSet.buffer();
+
+    DataConverterWithEpsilonClosure converter { nfaNodeclosures };
     for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
         unsigned nodeId = buffer[i];
-        const NFANode& nfaSourceNode = graph[nodeId];
-        for (unsigned targetTransition : nfaSourceNode.transitionsOnAnyCharacter)
-            allFallbackTransitions.append(targetTransition);
+        auto transitions = immutableNFA.transitionsForNode(nodeId);
+        combinedRangeList.extend(transitions.begin(), transitions.end(), converter);
     }
-    for (unsigned targetNodeId : allFallbackTransitions) {
-        auto addResult = setFallbackTransition.add(targetNodeId);
-        if (addResult.isNewEntry)
-            extendSetWithClosure(nfaNodeclosures, targetNodeId, setFallbackTransition);
+}
+
+static inline bool canUseFallbackTransition(const PreallocatedNFANodeRangeList& rangeList)
+{
+    // Transitions can contains "0" if the expression has a end-of-line marker.
+    // Fallback transitions cover 1-127. We have to be careful with the first.
+
+    auto iterator = rangeList.begin();
+    auto end = rangeList.end();
+    if (iterator == end)
+        return false;
+
+    char lastSeenCharacter = 0;
+    if (!iterator->first) {
+        lastSeenCharacter = iterator->last;
+        if (lastSeenCharacter == 127)
+            return true;
+        ++iterator;
     }
 
-    for (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());
+    for (;iterator != end; ++iterator) {
+        ASSERT(iterator->first > lastSeenCharacter);
+        if (iterator->first != lastSeenCharacter + 1)
+            return false;
+
+        if (iterator->last == 127)
+            return true;
+        lastSeenCharacter = iterator->last;
+    }
+    return false;
+}
+
+static inline uint32_t findBestFallbackTarget(const PreallocatedNFANodeRangeList& rangeList, const Vector<unsigned, 128>& rangeToTarget)
+{
+    ASSERT(canUseFallbackTransition(rangeList));
+
+    HashMap<uint32_t, unsigned, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> histogram;
+
+    unsigned rangeToTargetIndex = 0;
+    auto iterator = rangeList.begin();
+    auto end = rangeList.end();
+    ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition.");
+
+    if (!iterator->first && !iterator->last) {
+        ++iterator;
+        ++rangeToTargetIndex;
+    }
+    ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition.");
+
+    uint32_t bestTarget = rangeToTarget[rangeToTargetIndex];
+    unsigned bestTargetScore = !iterator->first ? iterator->size() - 1 : iterator->size();
+    histogram.add(bestTarget, bestTargetScore);
+    ++iterator;
+    ++rangeToTargetIndex;
+
+    for (;iterator != end; ++iterator, ++rangeToTargetIndex) {
+        unsigned rangeSize = iterator->size();
+        uint32_t target = rangeToTarget[rangeToTargetIndex];
+        auto addResult = histogram.add(target, rangeSize);
+        if (!addResult.isNewEntry)
+            addResult.iterator->value += rangeSize;
+        if (addResult.iterator->value > bestTargetScore) {
+            bestTargetScore = addResult.iterator->value;
+            bestTarget = target;
         }
     }
+    return bestTarget;
 }
 
-static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
+static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const NFA& nfa, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
 {
-    NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, nfaNodeSet);
+    NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfa, nfaNodeSet);
     auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
     if (uniqueNodeIdAddResult.isNewEntry)
         unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
@@ -347,60 +415,63 @@ static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, co
 
 DFA NFAToDFA::convert(NFA& nfa)
 {
-    DFA dfa;
-    Vector<NFANode>& nfaGraph = nfa.m_nodes;
-
     Vector<Vector<unsigned>> nfaNodeClosures;
-    resolveEpsilonClosures(nfaGraph, NFA::epsilonTransitionCharacter, nfaNodeClosures);
+    resolveEpsilonClosures(nfa, nfaNodeClosures);
+
+    DFA dfa;
 
     NodeIdSet initialSet({ nfa.root() });
     extendSetWithClosure(nfaNodeClosures, nfa.root(), initialSet);
 
     UniqueNodeIdSetTable uniqueNodeIdSetTable;
 
-    NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, initialSet);
+    NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfa, initialSet);
     auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
 
     Vector<UniqueNodeIdSetImpl*> unprocessedNodes;
     unprocessedNodes.append(addResult.iterator->impl());
 
-    SetTransitions transitionsFromClosedSet;
-
+    PreallocatedNFANodeRangeList combinedRangeList;
+    Vector<unsigned, 128> rangeToTarget;
     do {
         UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
+        createCombinedTransition(combinedRangeList, *uniqueNodeIdSetImpl, nfa, nfaNodeClosures);
 
-        unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
-        NodeIdSet setFallbackTransition;
-        populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);
+        rangeToTarget.clear();
+        for (const NFANodeRange& range : combinedRangeList) {
+            unsigned targetNodeId = getOrCreateDFANode(range.data, nfa, dfa, uniqueNodeIdSetTable, unprocessedNodes);
+            rangeToTarget.append(targetNodeId);
+        }
 
-        unsigned transitionsStart = dfa.transitionCharacters.size();
-        ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());
-        for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {
-            NodeIdSet& targetNodeSet = transitionsFromClosedSet[key];
+        bool useFallbackTransition = canUseFallbackTransition(combinedRangeList);
+        uint32_t preferedFallbackTarget = 0;
+        if (useFallbackTransition)
+            preferedFallbackTarget = findBestFallbackTarget(combinedRangeList, rangeToTarget);
 
-            if (targetNodeSet.isEmpty())
-                continue;
+        unsigned transitionsStart = dfa.transitionCharacters.size();
+        unsigned rangeToTargetIndex = 0;
 
-            unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);
-            RELEASE_ASSERT(key <= 127);
-            dfa.transitionCharacters.append(static_cast<uint8_t>(key));
-            dfa.transitionDestinations.append(targetNodeId);
+        for (const NFANodeRange& range : combinedRangeList) {
+            unsigned targetNodeId = rangeToTarget[rangeToTargetIndex];
 
-            targetNodeSet.clear();
+            if (!(useFallbackTransition && targetNodeId == preferedFallbackTarget)) {
+                for (unsigned i = range.first; i <= static_cast<unsigned>(range.last); ++i) {
+                    dfa.transitionCharacters.append(static_cast<uint8_t>(i));
+                    dfa.transitionDestinations.append(targetNodeId);
+                }
+            }
+            ++rangeToTargetIndex;
         }
         unsigned transitionsEnd = dfa.transitionCharacters.size();
-        ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());
         unsigned transitionsLength = transitionsEnd - transitionsStart;
-        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);
-        }
-    } while (!unprocessedNodes.isEmpty());
+        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);
+    } while (!unprocessedNodes.isEmpty());
     return dfa;
 }
 
index d1cb119..8882f42 100644 (file)
@@ -34,7 +34,7 @@ namespace WebCore {
 
 namespace ContentExtensions {
 
-class NFA;
+struct NFA;
 
 // NFAToDFA provides a way to build a DFA corresponding to a NFA.
 class NFAToDFA {
index 8d2246a..fc99f6f 100644 (file)
@@ -86,7 +86,7 @@ public:
 
     void quantify(const AtomQuantifier&);
 
-    unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
+    ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const;
 
     bool isEndOfLineAssertion() const;
 
@@ -118,7 +118,7 @@ private:
     // The return value can be false for a group equivalent to a universal transition.
     bool isUniversalTransition() const;
 
-    unsigned generateSubgraphForAtom(NFA&, unsigned source) const;
+    ImmutableCharNFANodeBuilder generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source) const;
 
     void destroy();
 
@@ -286,7 +286,7 @@ inline Term::Term(UniversalTransitionTag)
     : m_termType(TermType::CharacterSet)
 {
     new (NotNull, &m_atomData.characterSet) CharacterSet();
-    for (UChar i = 0; i < 128; ++i)
+    for (UChar i = 1; i < 128; ++i)
         m_atomData.characterSet.set(i);
 }
 
@@ -395,11 +395,11 @@ inline void Term::quantify(const AtomQuantifier& quantifier)
     m_quantifier = quantifier;
 }
 
-inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
+inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const
 {
     ASSERT(isValid());
 
-    unsigned newEnd;
+    ImmutableCharNFANodeBuilder newEnd;
 
     switch (m_quantifier) {
     case AtomQuantifier::One: {
@@ -408,36 +408,36 @@ inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const Action
     }
     case AtomQuantifier::ZeroOrOne: {
         newEnd = generateSubgraphForAtom(nfa, start);
-        nfa.addEpsilonTransition(start, newEnd);
+        start.addEpsilonTransition(newEnd);
         break;
     }
     case AtomQuantifier::ZeroOrMore: {
-        unsigned repeatStart = nfa.createNode();
-        nfa.addEpsilonTransition(start, repeatStart);
+        ImmutableCharNFANodeBuilder repeatStart(nfa);
+        start.addEpsilonTransition(repeatStart);
 
-        unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
-        nfa.addEpsilonTransition(repeatEnd, repeatStart);
+        ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+        repeatEnd.addEpsilonTransition(repeatStart);
 
-        unsigned kleenEnd = nfa.createNode();
-        nfa.addEpsilonTransition(repeatEnd, kleenEnd);
-        nfa.addEpsilonTransition(start, kleenEnd);
-        newEnd = kleenEnd;
+        ImmutableCharNFANodeBuilder kleenEnd(nfa);
+        repeatEnd.addEpsilonTransition(kleenEnd);
+        start.addEpsilonTransition(kleenEnd);
+        newEnd = WTF::move(kleenEnd);
         break;
     }
     case AtomQuantifier::OneOrMore: {
-        unsigned repeatStart = nfa.createNode();
-        nfa.addEpsilonTransition(start, repeatStart);
+        ImmutableCharNFANodeBuilder repeatStart(nfa);
+        start.addEpsilonTransition(repeatStart);
 
-        unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
-        nfa.addEpsilonTransition(repeatEnd, repeatStart);
+        ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+        repeatEnd.addEpsilonTransition(repeatStart);
 
-        unsigned afterRepeat = nfa.createNode();
-        nfa.addEpsilonTransition(repeatEnd, afterRepeat);
-        newEnd = afterRepeat;
+        ImmutableCharNFANodeBuilder afterRepeat(nfa);
+        repeatEnd.addEpsilonTransition(afterRepeat);
+        newEnd = WTF::move(afterRepeat);
         break;
     }
     }
-    nfa.setActions(newEnd, finalActions);
+    newEnd.setActions(finalActions.begin(), finalActions.end());
     return newEnd;
 }
 
@@ -612,36 +612,61 @@ inline bool Term::isUniversalTransition() const
     return false;
 }
 
-inline unsigned Term::generateSubgraphForAtom(NFA& nfa, unsigned source) const
+inline ImmutableCharNFANodeBuilder Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source) const
 {
     switch (m_termType) {
     case TermType::Empty:
     case TermType::Deleted:
         ASSERT_NOT_REACHED();
-        return -1;
+        return ImmutableCharNFANodeBuilder();
     case TermType::CharacterSet: {
-        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));
-                }
+        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);
+            }
+        } 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);
             }
         }
-        return target;
+        return newNode;
     }
     case TermType::Group: {
-        unsigned lastTarget = source;
-        for (const Term& term : m_atomData.group.terms)
-            lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
+        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);
+        }
+
         return lastTarget;
     }
     }
index ac175d2..87678e3 100644 (file)
@@ -1,3 +1,13 @@
+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.
+
 2015-06-28  Dan Bernstein  <mitz@apple.com>
 
         [Xcode] Use the same environment for command-line and IDE builds
index 9b3797f..14c25b4 100644 (file)
@@ -304,6 +304,38 @@ TEST_F(ContentExtensionTest, PatternNestedGroups)
     testRequest(backend, mainDocumentRequest("http://webkit.org/fobar"), { });
 }
 
+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"), { });
+}
+
 TEST_F(ContentExtensionTest, MatchPastEndOfString)
 {
     auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".+\"}}]");
@@ -359,6 +391,16 @@ TEST_F(ContentExtensionTest, EndOfLineAssertionWithInvertedCharacterSet)
     testRequest(backend, mainDocumentRequest("http://webkit.org/foobarY"), { });
 }
 
+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 });
+}
+
 TEST_F(ContentExtensionTest, PrefixInfixSuffixExactMatch)
 {
     auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"infix\"}},"
@@ -1368,4 +1410,524 @@ TEST_F(ContentExtensionTest, SimpleFallBackTransitionDifferentiator2)
     testRequest(backend, mainDocumentRequest("bbbb://www.webkit.org/"), { });
 }
 
+// *** 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 });
+}
+
 } // namespace TestWebKitAPI