Handle the transition on any character as a separate type of transition
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Jan 2015 21:56:22 +0000 (21:56 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Jan 2015 21:56:22 +0000 (21:56 +0000)
commit1947869237204fe20aa18f5351adaa1443f7333a
treeeee4bd6e74e7302646483def859fe97e6ec83632
parenta37634ede3a91372e0033fc41682abf3f5030d79
Handle the transition on any character as a separate type of transition
https://bugs.webkit.org/show_bug.cgi?id=140711

Reviewed by Andreas Kling.

Instead of considering the universal transition as 127 transitions, it is now
handled as a separate type of transition.

The goal is to reduce the number of exit edge to consider for each node. Instead
of having 127 for any partition containing one universal transition, we have
as few exit edges as necessary + one universal transition.

In the NFA, the universal transition is stored directly on NFANode in a new
HashSet (transitionsOnAnyCharacter).
The target nodes are made exclusive between "transitionsOnAnyCharacter" and "transitions"
by construction. That is not strictly needed but it simplify debugging at the moment.

When converting a NFA to a DFA, we first find all the node that transition on any character.
Then, when we iterate over "real" transition, we also augment that set with the set on
any character.

When creating the DFA node, we first consider each "real" transition, then we have a single
"fallback" transition for any character that has not been handled yet.

When matching, we first search for any real transition. If there is none but a fallback exists,
we take the fallback.

* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::nextState):
(WebCore::ContentExtensions::printTransitions):
(WebCore::ContentExtensions::DFA::debugPrintDot):
(WebCore::ContentExtensions::printTransition): Deleted.
* contentextensions/DFANode.h:
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::addTransition):
(WebCore::ContentExtensions::NFA::addTransitionsOnAnyCharacter):
(WebCore::ContentExtensions::printTransitions):
(WebCore::ContentExtensions::NFA::debugPrintDot):
(WebCore::ContentExtensions::printTransition): Deleted.
* contentextensions/NFA.h:
* contentextensions/NFANode.h:
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::populateTransitions):
(WebCore::ContentExtensions::getOrCreateDFANode):
(WebCore::ContentExtensions::NFAToDFA::convert):
* contentextensions/URLFilterParser.cpp:
(WebCore::ContentExtensions::GraphBuilder::generateTransition):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@178857 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/WebCore/ChangeLog
Source/WebCore/contentextensions/DFA.cpp
Source/WebCore/contentextensions/DFANode.h
Source/WebCore/contentextensions/NFA.cpp
Source/WebCore/contentextensions/NFA.h
Source/WebCore/contentextensions/NFANode.h
Source/WebCore/contentextensions/NFAToDFA.cpp
Source/WebCore/contentextensions/URLFilterParser.cpp