<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[178529] trunk/Source/WebCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/178529">178529</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-01-15 14:19:40 -0800 (Thu, 15 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>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.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreWebCorexcodeprojprojectpbxproj">trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp">trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFANodeh">trunk/Source/WebCore/contentextensions/DFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAcpp">trunk/Source/WebCore/contentextensions/NFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAh">trunk/Source/WebCore/contentextensions/NFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFANodeh">trunk/Source/WebCore/contentextensions/NFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsURLFilterParsercpp">trunk/Source/WebCore/contentextensions/URLFilterParser.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsURLFilterParserh">trunk/Source/WebCore/contentextensions/URLFilterParser.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourceWebCorecontentextensionsNFANodecpp">trunk/Source/WebCore/contentextensions/NFANode.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/ChangeLog 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -1,3 +1,71 @@
</span><ins>+2015-01-15 Benjamin Poulain <benjamin@webkit.org>
+
+ 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.
+
</ins><span class="cx"> 2015-01-14 Alexey Proskuryakov <ap@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector and regular console use different source code locations for messages
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -1031,7 +1031,6 @@
</span><span class="cx"> 267726041A5DF6F2003C24DD /* URLFilterParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 267726021A5DF6F2003C24DD /* URLFilterParser.cpp */; };
</span><span class="cx"> 267726051A5DF6F2003C24DD /* URLFilterParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 267726031A5DF6F2003C24DD /* URLFilterParser.h */; };
</span><span class="cx"> 269239961505E1AA009E57FC /* JSIDBVersionChangeEvent.h in Headers */ = {isa = PBXBuildFile; fileRef = 269239921505E1AA009E57FC /* JSIDBVersionChangeEvent.h */; };
</span><del>- 269397211A4A412F00E8349D /* NFANode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2693971F1A4A412F00E8349D /* NFANode.cpp */; };
</del><span class="cx"> 269397221A4A412F00E8349D /* NFANode.h in Headers */ = {isa = PBXBuildFile; fileRef = 269397201A4A412F00E8349D /* NFANode.h */; };
</span><span class="cx"> 269397241A4A5B6400E8349D /* NFA.h in Headers */ = {isa = PBXBuildFile; fileRef = 269397231A4A5B6400E8349D /* NFA.h */; };
</span><span class="cx"> 269397261A4A5FBD00E8349D /* NFA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 269397251A4A5FBD00E8349D /* NFA.cpp */; };
</span><span class="lines">@@ -8032,7 +8031,6 @@
</span><span class="cx"> 267726031A5DF6F2003C24DD /* URLFilterParser.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = URLFilterParser.h; sourceTree = "<group>"; };
</span><span class="cx"> 269239911505E1AA009E57FC /* JSIDBVersionChangeEvent.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSIDBVersionChangeEvent.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 269239921505E1AA009E57FC /* JSIDBVersionChangeEvent.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSIDBVersionChangeEvent.h; sourceTree = "<group>"; };
</span><del>- 2693971F1A4A412F00E8349D /* NFANode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NFANode.cpp; sourceTree = "<group>"; };
</del><span class="cx"> 269397201A4A412F00E8349D /* NFANode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NFANode.h; sourceTree = "<group>"; };
</span><span class="cx"> 269397231A4A5B6400E8349D /* NFA.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NFA.h; sourceTree = "<group>"; };
</span><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NFA.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15337,7 +15335,6 @@
</span><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */,
</span><span class="cx"> 269397231A4A5B6400E8349D /* NFA.h */,
</span><del>- 2693971F1A4A412F00E8349D /* NFANode.cpp */,
</del><span class="cx"> 269397201A4A412F00E8349D /* NFANode.h */,
</span><span class="cx"> 267725FA1A5B3AD9003C24DD /* NFAToDFA.cpp */,
</span><span class="cx"> 267725FB1A5B3AD9003C24DD /* NFAToDFA.h */,
</span><span class="lines">@@ -29687,7 +29684,6 @@
</span><span class="cx"> B2227A960D00BF220071B782 /* SVGPreserveAspectRatio.cpp in Sources */,
</span><span class="cx"> B543B85717EB758F003BE93A /* SVGPropertyInfo.cpp in Sources */,
</span><span class="cx"> B2227A990D00BF220071B782 /* SVGRadialGradientElement.cpp in Sources */,
</span><del>- 269397211A4A412F00E8349D /* NFANode.cpp in Sources */,
</del><span class="cx"> B2227A9D0D00BF220071B782 /* SVGRectElement.cpp in Sources */,
</span><span class="cx"> BC2274780E8366E200E7F975 /* SVGRenderStyle.cpp in Sources */,
</span><span class="cx"> BC22747A0E8366E200E7F975 /* SVGRenderStyleDefs.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -64,16 +64,16 @@
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> NFA nfa;
</span><ins>+ URLFilterParser urlFilterParser(nfa);
</ins><span class="cx"> for (unsigned ruleIndex = 0; ruleIndex < ruleList.size(); ++ruleIndex) {
</span><span class="cx"> const ContentExtensionRule& contentExtensionRule = ruleList[ruleIndex];
</span><span class="cx"> const ContentExtensionRule::Trigger& trigger = contentExtensionRule.trigger();
</span><span class="cx"> ASSERT(trigger.urlFilter.length());
</span><span class="cx">
</span><del>- URLFilterParser urlFilterParser;
- urlFilterParser.parse(trigger.urlFilter, ruleIndex, nfa);
</del><ins>+ String error = urlFilterParser.addPattern(trigger.urlFilter, ruleIndex);
</ins><span class="cx">
</span><del>- if (urlFilterParser.hasError()) {
- dataLogF("Error while parsing %s: %s", trigger.urlFilter.utf8().data(), urlFilterParser.errorMessage().utf8().data());
</del><ins>+ if (!error.isNull()) {
+ dataLogF("Error while parsing %s: %s\n", trigger.urlFilter.utf8().data(), error.utf8().data());
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -154,13 +154,13 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Vector<unsigned> correspondingDFANodes = m_nodes[i].correspondingDFANodes;
- ASSERT(!correspondingDFANodes.isEmpty());
</del><ins>+ Vector<unsigned> correspondingNFANodes = m_nodes[i].correspondingNFANodes;
+ ASSERT(!correspondingNFANodes.isEmpty());
</ins><span class="cx"> dataLogF("<BR/>NFA Nodes: ");
</span><del>- for (unsigned correspondingDFANodeIndex = 0; correspondingDFANodeIndex < correspondingDFANodes.size(); ++correspondingDFANodeIndex) {
</del><ins>+ for (unsigned correspondingDFANodeIndex = 0; correspondingDFANodeIndex < correspondingNFANodes.size(); ++correspondingDFANodeIndex) {
</ins><span class="cx"> if (correspondingDFANodeIndex)
</span><span class="cx"> dataLogF(", ");
</span><del>- dataLogF("%d", correspondingDFANodes[correspondingDFANodeIndex]);
</del><ins>+ dataLogF("%d", correspondingNFANodes[correspondingDFANodeIndex]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> dataLogF(">]");
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -44,7 +44,7 @@
</span><span class="cx"> Vector<uint64_t> actions;
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><del>- Vector<unsigned> correspondingDFANodes;
</del><ins>+ Vector<unsigned> correspondingNFANodes;
</ins><span class="cx"> #endif
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -40,10 +40,10 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>-unsigned NFA::createNode(uint64_t ruleId)
</del><ins>+unsigned NFA::createNode()
</ins><span class="cx"> {
</span><span class="cx"> unsigned nextId = m_nodes.size();
</span><del>- m_nodes.append(NFANode(ruleId));
</del><ins>+ m_nodes.append(NFANode());
</ins><span class="cx"> return nextId;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -66,10 +66,10 @@
</span><span class="cx"> addResult.iterator->value.add(to);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void NFA::setFinal(unsigned node)
</del><ins>+void NFA::setFinal(unsigned node, uint64_t ruleId)
</ins><span class="cx"> {
</span><del>- ASSERT(node < m_nodes.size());
- m_nodes[node].isFinal = true;
</del><ins>+ ASSERT(!m_nodes[node].finalRuleIds.contains(ruleId));
+ m_nodes[node].finalRuleIds.append(ruleId);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> unsigned NFA::graphSize() const
</span><span class="lines">@@ -79,7 +79,7 @@
</span><span class="cx">
</span><span class="cx"> void NFA::restoreToGraphSize(unsigned size)
</span><span class="cx"> {
</span><del>- ASSERT(size > 1);
</del><ins>+ ASSERT(size >= 1);
</ins><span class="cx"> ASSERT(size <= graphSize());
</span><span class="cx">
</span><span class="cx"> m_nodes.shrink(size);
</span><span class="lines">@@ -87,6 +87,12 @@
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx">
</span><ins>+void NFA::addRuleId(unsigned node, uint64_t ruleId)
+{
+ ASSERT(!m_nodes[node].ruleIds.contains(ruleId));
+ m_nodes[node].ruleIds.append(ruleId);
+}
+
</ins><span class="cx"> static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
</span><span class="cx"> {
</span><span class="cx"> if (!firstRange)
</span><span class="lines">@@ -152,12 +158,33 @@
</span><span class="cx"> dataLogF(" node [shape=circle];\n");
</span><span class="cx"> dataLogF(" {\n");
</span><span class="cx"> for (unsigned i = 0; i < m_nodes.size(); ++i) {
</span><del>- if (m_nodes[i].ruleId == std::numeric_limits<uint64_t>::max())
- dataLogF(" %d [label=\"Node %d\"]", i, i);
- else
- dataLogF(" %d [label=<Node %d<BR/>(Rule %llu)>]", i, i, m_nodes[i].ruleId);
</del><ins>+ dataLogF(" %d [label=<Node %d", i, i);
</ins><span class="cx">
</span><del>- if (m_nodes[i].isFinal)
</del><ins>+ const Vector<uint64_t>& originalRules = m_nodes[i].ruleIds;
+ if (!originalRules.isEmpty()) {
+ dataLogF("<BR/>(Rules: ");
+ for (unsigned ruleIndex = 0; ruleIndex < originalRules.size(); ++ruleIndex) {
+ if (ruleIndex)
+ dataLogF(", ");
+ dataLogF("%llu", originalRules[ruleIndex]);
+ }
+ dataLogF(")");
+ }
+
+ const Vector<uint64_t>& finalRules = m_nodes[i].finalRuleIds;
+ if (!finalRules.isEmpty()) {
+ dataLogF("<BR/>(Final: ");
+ for (unsigned ruleIndex = 0; ruleIndex < finalRules.size(); ++ruleIndex) {
+ if (ruleIndex)
+ dataLogF(", ");
+ dataLogF("%llu", finalRules[ruleIndex]);
+ }
+ dataLogF(")");
+ }
+
+ dataLogF(">]");
+
+ if (!finalRules.isEmpty())
</ins><span class="cx"> dataLogF(" [shape=doublecircle]");
</span><span class="cx">
</span><span class="cx"> dataLogF(";\n");
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -30,7 +30,6 @@
</span><span class="cx">
</span><span class="cx"> #include "ContentExtensionsDebugging.h"
</span><span class="cx"> #include "NFANode.h"
</span><del>-#include <limits>
</del><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="lines">@@ -45,17 +44,21 @@
</span><span class="cx"> public:
</span><span class="cx"> NFA();
</span><span class="cx"> unsigned root() const { return m_root; }
</span><del>- unsigned createNode(uint64_t ruleId = std::numeric_limits<uint64_t>::max());
</del><ins>+ unsigned createNode();
</ins><span class="cx">
</span><span class="cx"> void addTransition(unsigned from, unsigned to, char character);
</span><span class="cx"> void addEpsilonTransition(unsigned from, unsigned to);
</span><del>- void setFinal(unsigned node);
</del><ins>+ void setFinal(unsigned node, uint64_t ruleId);
</ins><span class="cx">
</span><span class="cx"> unsigned graphSize() const;
</span><span class="cx"> void restoreToGraphSize(unsigned);
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><ins>+ void addRuleId(unsigned node, uint64_t ruleId);
+
</ins><span class="cx"> void debugPrintDot() const;
</span><ins>+#else
+ void addRuleId(unsigned, uint64_t) { }
</ins><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> private:
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFANodecpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/WebCore/contentextensions/NFANode.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFANode.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/NFANode.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -1,45 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
- * THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include "config.h"
-#include "NFANode.h"
-
-#if ENABLE(CONTENT_EXTENSIONS)
-
-namespace WebCore {
-
-namespace ContentExtensions {
-
-NFANode::NFANode(uint64_t ruleId)
- : isFinal(false)
- , ruleId(ruleId)
-{
-}
-
-}
-
-} // namespace WebCore
-
-#endif // ENABLE(CONTENT_EXTENSIONS)
</del></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFANode.h (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFANode.h 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/NFANode.h 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -28,8 +28,10 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><ins>+#include <wtf/Vector.h>
</ins><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="cx">
</span><span class="lines">@@ -38,11 +40,12 @@
</span><span class="cx"> // A NFANode abstract the transition table out of a NFA state.
</span><span class="cx"> class NFANode {
</span><span class="cx"> public:
</span><del>- NFANode(uint64_t ruleId);
</del><ins>+ HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> transitions;
</ins><span class="cx">
</span><del>- HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> transitions;
- bool isFinal;
- const uint64_t ruleId;
</del><ins>+ Vector<uint64_t> finalRuleIds;
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ Vector<uint64_t> ruleIds;
+#endif
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -219,10 +219,9 @@
</span><span class="cx"> HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
</span><span class="cx"> for (unsigned nfaNodeId : source.nodeIdSet) {
</span><span class="cx"> const NFANode& nfaNode = source.nfaGraph[nfaNodeId];
</span><del>- if (nfaNode.isFinal)
- actions.add(nfaNode.ruleId);
</del><ins>+ actions.add(nfaNode.finalRuleIds.begin(), nfaNode.finalRuleIds.end());
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><del>- newDFANode.correspondingDFANodes.append(nfaNodeId);
</del><ins>+ newDFANode.correspondingNFANodes.append(nfaNodeId);
</ins><span class="cx"> #endif
</span><span class="cx"> }
</span><span class="cx"> copyToVector(actions, newDFANode.actions);
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsURLFilterParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/URLFilterParser.cpp (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -35,6 +35,35 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+const uint16_t hasNonCharacterMask = 0x0080;
+const uint16_t characterMask = 0x0007F;
+const uint16_t newlineClassIDBuiltinMask = 0x100;
+
+static TrivialAtom trivialAtomFromASCIICharacter(char character)
+{
+ ASSERT(isASCII(character));
+
+ return static_cast<uint16_t>(character);
+}
+
+enum class TrivialAtomQuantifier : uint16_t {
+ ZeroOrOne = 0x1000,
+ ZeroToMany = 0x2000,
+ OneToMany = 0x4000
+};
+
+static void quantifyTrivialAtom(TrivialAtom& trivialAtom, TrivialAtomQuantifier quantifier)
+{
+ ASSERT(trivialAtom & (hasNonCharacterMask | characterMask));
+ ASSERT(!(trivialAtom & 0xf000));
+ trivialAtom |= static_cast<uint16_t>(quantifier);
+}
+
+static TrivialAtom trivialAtomForNewlineClassIDBuiltin()
+{
+ return hasNonCharacterMask | newlineClassIDBuiltinMask;
+}
+
</ins><span class="cx"> class GraphBuilder {
</span><span class="cx"> private:
</span><span class="cx"> struct BoundedSubGraph {
</span><span class="lines">@@ -42,11 +71,11 @@
</span><span class="cx"> unsigned end;
</span><span class="cx"> };
</span><span class="cx"> public:
</span><del>- GraphBuilder(NFA& nfa, uint64_t patternId)
</del><ins>+ GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, uint64_t patternId)
</ins><span class="cx"> : m_nfa(nfa)
</span><span class="cx"> , m_patternId(patternId)
</span><span class="cx"> , m_activeGroup({ nfa.root(), nfa.root() })
</span><del>- , m_lastAtom(m_activeGroup)
</del><ins>+ , m_lastPrefixTreeEntry(&prefixTreeRoot)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -54,8 +83,11 @@
</span><span class="cx"> {
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><ins>+
+ sinkPendingAtomIfNecessary();
+
</ins><span class="cx"> if (m_activeGroup.start != m_activeGroup.end)
</span><del>- m_nfa.setFinal(m_activeGroup.end);
</del><ins>+ m_nfa.setFinal(m_activeGroup.end, m_patternId);
</ins><span class="cx"> else
</span><span class="cx"> fail(ASCIILiteral("The pattern cannot match anything."));
</span><span class="cx"> }
</span><span class="lines">@@ -75,12 +107,13 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><ins>+ sinkPendingAtomIfNecessary();
+
+ char asciiChararacter = static_cast<char>(character);
</ins><span class="cx"> m_hasValidAtom = true;
</span><del>- unsigned newEnd = m_nfa.createNode(m_patternId);
- m_nfa.addTransition(m_lastAtom.end, newEnd, static_cast<char>(character));
- m_lastAtom.start = m_lastAtom.end;
- m_lastAtom.end = newEnd;
- m_activeGroup.end = m_lastAtom.end;
</del><ins>+
+ ASSERT(m_lastPrefixTreeEntry);
+ m_pendingTrivialAtom = trivialAtomFromASCIICharacter(asciiChararacter);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
</span><span class="lines">@@ -89,14 +122,9 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
</span><del>- // FIXME: handle new line properly.
</del><span class="cx"> m_hasValidAtom = true;
</span><del>- unsigned newEnd = m_nfa.createNode(m_patternId);
- for (unsigned i = 1; i < 128; ++i)
- m_nfa.addTransition(m_lastAtom.end, newEnd, i);
- m_lastAtom.start = m_lastAtom.end;
- m_lastAtom.end = newEnd;
- m_activeGroup.end = m_lastAtom.end;
</del><ins>+ ASSERT(m_lastPrefixTreeEntry);
+ m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
</ins><span class="cx"> } else
</span><span class="cx"> fail(ASCIILiteral("Character class is not supported."));
</span><span class="cx"> }
</span><span class="lines">@@ -112,13 +140,13 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ ASSERT(m_lastPrefixTreeEntry);
</ins><span class="cx"> if (!minimum && maximum == 1)
</span><del>- m_nfa.addEpsilonTransition(m_lastAtom.start, m_lastAtom.end);
- else if (!minimum && maximum == JSC::Yarr::quantifyInfinite) {
- m_nfa.addEpsilonTransition(m_lastAtom.start, m_lastAtom.end);
- m_nfa.addEpsilonTransition(m_lastAtom.end, m_lastAtom.start);
- } else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
- m_nfa.addEpsilonTransition(m_lastAtom.end, m_lastAtom.start);
</del><ins>+ quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroOrOne);
+ else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
+ quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroToMany);
+ else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
+ quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::OneToMany);
</ins><span class="cx"> else
</span><span class="cx"> fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
</span><span class="cx"> }
</span><span class="lines">@@ -189,7 +217,6 @@
</span><span class="cx"> fail(ASCIILiteral("Disjunctions are not supported yet."));
</span><span class="cx"> }
</span><span class="cx">
</span><del>-
</del><span class="cx"> private:
</span><span class="cx"> bool hasError() const
</span><span class="cx"> {
</span><span class="lines">@@ -200,43 +227,154 @@
</span><span class="cx"> {
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><ins>+
+ if (m_newPrefixSubtreeRoot)
+ m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
+
</ins><span class="cx"> m_errorMessage = errorMessage;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
+ {
+ if (trivialAtom & hasNonCharacterMask) {
+ ASSERT(trivialAtom & newlineClassIDBuiltinMask);
+ for (unsigned i = 1; i < 128; ++i)
+ m_nfa.addTransition(source, target, i);
+ } else
+ m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
+ }
+
+ BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
+ {
+ if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
+ unsigned newEnd = m_nfa.createNode();
+ m_nfa.addRuleId(newEnd, m_patternId);
+ generateTransition(trivialAtom, start, newEnd);
+ m_nfa.addEpsilonTransition(start, newEnd);
+ return { start, newEnd };
+ }
+
+ if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
+ unsigned repeatStart = m_nfa.createNode();
+ m_nfa.addRuleId(repeatStart, m_patternId);
+ unsigned repeatEnd = m_nfa.createNode();
+ m_nfa.addRuleId(repeatEnd, m_patternId);
+
+ generateTransition(trivialAtom, repeatStart, repeatEnd);
+ m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
+
+ m_nfa.addEpsilonTransition(start, repeatStart);
+
+ unsigned kleenEnd = m_nfa.createNode();
+ m_nfa.addRuleId(kleenEnd, m_patternId);
+ m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
+ m_nfa.addEpsilonTransition(start, kleenEnd);
+ return { start, kleenEnd };
+ }
+
+ if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
+ unsigned repeatStart = m_nfa.createNode();
+ m_nfa.addRuleId(repeatStart, m_patternId);
+ unsigned repeatEnd = m_nfa.createNode();
+ m_nfa.addRuleId(repeatEnd, m_patternId);
+
+ generateTransition(trivialAtom, repeatStart, repeatEnd);
+ m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
+
+ m_nfa.addEpsilonTransition(start, repeatStart);
+
+ unsigned afterRepeat = m_nfa.createNode();
+ m_nfa.addRuleId(afterRepeat, m_patternId);
+ m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
+ return { start, afterRepeat };
+ }
+
+ unsigned newEnd = m_nfa.createNode();
+ m_nfa.addRuleId(newEnd, m_patternId);
+ generateTransition(trivialAtom, start, newEnd);
+ return { start, newEnd };
+ }
+
+ void sinkPendingAtomIfNecessary()
+ {
+ ASSERT(m_lastPrefixTreeEntry);
+
+ if (!m_hasValidAtom)
+ return;
+
+ ASSERT(m_pendingTrivialAtom);
+
+ auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
+ if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
+ m_lastPrefixTreeEntry = nextEntry->value.get();
+ m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
+ } else {
+ std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
+
+ BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
+ nextPrefixTreeEntry->nfaNode = newSubGraph.end;
+
+ auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
+ ASSERT(addResult.isNewEntry);
+
+ m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
+ m_newPrefixStaringPoint = m_pendingTrivialAtom;
+
+ m_lastPrefixTreeEntry = addResult.iterator->value.get();
+ }
+ ASSERT(m_lastPrefixTreeEntry);
+
+ m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
+ m_pendingTrivialAtom = 0;
+ m_hasValidAtom = false;
+ }
+
</ins><span class="cx"> NFA& m_nfa;
</span><span class="cx"> const uint64_t m_patternId;
</span><span class="cx">
</span><span class="cx"> BoundedSubGraph m_activeGroup;
</span><span class="cx">
</span><ins>+ PrefixTreeEntry* m_lastPrefixTreeEntry;
</ins><span class="cx"> bool m_hasValidAtom = false;
</span><del>- BoundedSubGraph m_lastAtom;
</del><ins>+ TrivialAtom m_pendingTrivialAtom = 0;
</ins><span class="cx">
</span><ins>+ PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
+ TrivialAtom m_newPrefixStaringPoint = 0;
+
</ins><span class="cx"> String m_errorMessage;
</span><span class="cx"> };
</span><span class="cx">
</span><del>-void URLFilterParser::parse(const String& pattern, uint64_t patternId, NFA& nfa)
</del><ins>+URLFilterParser::URLFilterParser(NFA& nfa)
+ : m_nfa(nfa)
</ins><span class="cx"> {
</span><ins>+ m_prefixTreeRoot.nfaNode = nfa.root();
+}
+
+String URLFilterParser::addPattern(const String& pattern, uint64_t patternId)
+{
</ins><span class="cx"> if (!pattern.containsOnlyASCII())
</span><del>- m_errorMessage = ASCIILiteral("URLFilterParser only supports ASCII patterns.");
</del><ins>+ return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
</ins><span class="cx"> ASSERT(!pattern.isEmpty());
</span><span class="cx">
</span><span class="cx"> if (pattern.isEmpty())
</span><del>- return;
</del><ins>+ return ASCIILiteral("Empty pattern.");
</ins><span class="cx">
</span><del>- unsigned oldSize = nfa.graphSize();
</del><ins>+ unsigned oldSize = m_nfa.graphSize();
</ins><span class="cx">
</span><del>- GraphBuilder graphBuilder(nfa, patternId);
- const char* error = JSC::Yarr::parse(graphBuilder, pattern, 0);
- if (error)
- m_errorMessage = String(error);
- else
</del><ins>+ String error;
+
+ GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternId);
+ error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
+ if (error.isNull())
</ins><span class="cx"> graphBuilder.finalize();
</span><span class="cx">
</span><del>- if (!error)
- m_errorMessage = graphBuilder.errorMessage();
</del><ins>+ if (error.isNull())
+ error = graphBuilder.errorMessage();
</ins><span class="cx">
</span><del>- if (hasError())
- nfa.restoreToGraphSize(oldSize);
</del><ins>+ if (!error.isNull())
+ m_nfa.restoreToGraphSize(oldSize);
+
+ return error;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsURLFilterParserh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/URLFilterParser.h (178528 => 178529)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/URLFilterParser.h 2015-01-15 22:14:50 UTC (rev 178528)
+++ trunk/Source/WebCore/contentextensions/URLFilterParser.h 2015-01-15 22:19:40 UTC (rev 178529)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include <wtf/HashMap.h>
</ins><span class="cx"> #include <wtf/text/WTFString.h>
</span><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="lines">@@ -36,20 +37,22 @@
</span><span class="cx">
</span><span class="cx"> class NFA;
</span><span class="cx">
</span><ins>+typedef uint16_t TrivialAtom;
+
+struct PrefixTreeEntry {
+ unsigned nfaNode;
+ HashMap<TrivialAtom, std::unique_ptr<PrefixTreeEntry>> nextPattern;
+};
+
+
</ins><span class="cx"> class URLFilterParser {
</span><span class="cx"> public:
</span><del>- void parse(const String& pattern, uint64_t patternId, NFA&);
</del><ins>+ explicit URLFilterParser(NFA&);
+ String addPattern(const String& pattern, uint64_t patternId);
</ins><span class="cx">
</span><del>- bool hasError() const { return !m_errorMessage.isNull(); }
- String errorMessage() const { return m_errorMessage; }
-
</del><span class="cx"> private:
</span><del>- struct BoundedSubGraph {
- unsigned start;
- unsigned end;
- };
-
- String m_errorMessage;
</del><ins>+ NFA& m_nfa;
+ PrefixTreeEntry m_prefixTreeRoot;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre>
</div>
</div>
</body>
</html>