When building the NFA of the global disjunction, share the prefix subgraph of existin...
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 15 Jan 2015 22:19:40 +0000 (22:19 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 15 Jan 2015 22:19:40 +0000 (22:19 +0000)
commit11cee6bcb53555c1256e24e1ee4b1dd2d59b5bbd
tree75620ceab0fe461904d2cff5a5c7e8e578dba697
parent87210a21901bca2b611590c6c77c114eb7f9aee3
When building the NFA of the global disjunction, share the prefix subgraph of existing subpatterns
https://bugs.webkit.org/show_bug.cgi?id=140465

Reviewed by Andreas Kling.

This patch updates the parser to produce smaller graphs when multiple patterns
of the rule list share a common prefix.

Previously, GraphBuilder would generate subgraph in place of each parsed
atom. We now only create subgraph if an atom does not appear in the prefix tree.

We accumulate the parsing information into small uint16_t named TrivialAtom.
When generating the subgraph for an new atom, we first check if the prefix tree already
has a corresponding subgraph for that atom. If it does, we do not generate anything and we extend the existing
graph. If there is no existing prefix, we create the subgraph and extend the prefix tree.

Sharing prefix subtrees slows down the subtree generation a bit but the resulting graph is much
simpler for many kind of inputs.

* WebCore.xcodeproj/project.pbxproj:
* contentextensions/ContentExtensionsBackend.cpp:
(WebCore::ContentExtensions::ContentExtensionsBackend::setRuleList):
The URLFilterParser now maintains states (the prefix tree) between patterns.

* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::debugPrintDot):
* contentextensions/DFANode.h:
Fix a typo :)

* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::createNode):
(WebCore::ContentExtensions::NFA::setFinal):
(WebCore::ContentExtensions::NFA::restoreToGraphSize):
(WebCore::ContentExtensions::NFA::addRuleId):
(WebCore::ContentExtensions::NFA::debugPrintDot):
* contentextensions/NFA.h:
(WebCore::ContentExtensions::NFA::addRuleId):
* contentextensions/NFANode.cpp: Removed.
* contentextensions/NFANode.h:
NFA nodes from two patterns are now "merged" by construction, thus we need
to keep track of multiple rules per node.

* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
* contentextensions/URLFilterParser.cpp:
(WebCore::ContentExtensions::trivialAtomFromAsciiCharacter):
(WebCore::ContentExtensions::quantifyTrivialAtom):
(WebCore::ContentExtensions::trivialAtomForNewlineClassIDBuiltin):
(WebCore::ContentExtensions::GraphBuilder::GraphBuilder):
(WebCore::ContentExtensions::GraphBuilder::m_LastPrefixTreeEntry):
(WebCore::ContentExtensions::GraphBuilder::finalize):
(WebCore::ContentExtensions::GraphBuilder::atomPatternCharacter):
(WebCore::ContentExtensions::GraphBuilder::atomBuiltInCharacterClass):
(WebCore::ContentExtensions::GraphBuilder::quantifyAtom):
(WebCore::ContentExtensions::GraphBuilder::fail):
(WebCore::ContentExtensions::GraphBuilder::generateTransition):
(WebCore::ContentExtensions::GraphBuilder::sinkTrivialAtom):
(WebCore::ContentExtensions::GraphBuilder::sinkPendingAtomIfNecessary):
(WebCore::ContentExtensions::URLFilterParser::URLFilterParser):
(WebCore::ContentExtensions::URLFilterParser::addPattern):
(WebCore::ContentExtensions::GraphBuilder::m_lastAtom): Deleted.
(WebCore::ContentExtensions::URLFilterParser::parse): Deleted.
* contentextensions/URLFilterParser.h:
(WebCore::ContentExtensions::URLFilterParser::hasError): Deleted.
(WebCore::ContentExtensions::URLFilterParser::errorMessage): Deleted.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@178529 268f45cc-cd09-0410-ab3c-d52691b4dbfc
12 files changed:
Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/contentextensions/ContentExtensionsBackend.cpp
Source/WebCore/contentextensions/DFA.cpp
Source/WebCore/contentextensions/DFANode.h
Source/WebCore/contentextensions/NFA.cpp
Source/WebCore/contentextensions/NFA.h
Source/WebCore/contentextensions/NFANode.cpp [deleted file]
Source/WebCore/contentextensions/NFANode.h
Source/WebCore/contentextensions/NFAToDFA.cpp
Source/WebCore/contentextensions/URLFilterParser.cpp
Source/WebCore/contentextensions/URLFilterParser.h