<!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>[178857] 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/178857">178857</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-01-21 13:56:22 -0800 (Wed, 21 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</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>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/ChangeLog 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -1,3 +1,53 @@
</span><ins>+2015-01-21 Benjamin Poulain <benjamin@webkit.org>
+
+ 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):
+
</ins><span class="cx"> 2015-01-20 Antti Koivisto <antti@apple.com>
</span><span class="cx">
</span><span class="cx"> REGRESSION(r178180): Membuster regressed ~4%
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -65,12 +65,17 @@
</span><span class="cx">
</span><span class="cx"> const DFANode& node = m_nodes[currentState];
</span><span class="cx"> auto nextNode = node.transitions.find(character);
</span><del>- if (nextNode == node.transitions.end()) {
- ok = false;
- return 0;
</del><ins>+ if (nextNode != node.transitions.end()) {
+ ok = true;
+ return nextNode->value;
</ins><span class="cx"> }
</span><del>- ok = true;
- return nextNode->value;
</del><ins>+ if (node.hasFallbackTransition) {
+ ok = true;
+ return node.fallbackTransition;
+ }
+ ok = false;
+ return 0;
+
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> const Vector<uint64_t>& DFA::actions(unsigned currentState) const
</span><span class="lines">@@ -95,9 +100,12 @@
</span><span class="cx"> dataLogF("\\\\%d-\\\\%d", rangeStart, rangeEnd);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void printTransition(unsigned sourceNode, const HashMap<uint16_t, unsigned>& transitions)
</del><ins>+static void printTransitions(const Vector<DFANode>& graph, unsigned sourceNodeId)
</ins><span class="cx"> {
</span><del>- if (transitions.isEmpty())
</del><ins>+ const DFANode& sourceNode = graph[sourceNodeId];
+ const HashMap<uint16_t, unsigned>& transitions = sourceNode.transitions;
+
+ if (transitions.isEmpty() && !sourceNode.hasFallbackTransition)
</ins><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> HashMap<unsigned, Vector<uint16_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
</span><span class="lines">@@ -112,7 +120,7 @@
</span><span class="cx">
</span><span class="cx"> // Then we go over each one an display the ranges one by one.
</span><span class="cx"> for (const auto& transitionPerTarget : transitionsPerTarget) {
</span><del>- dataLogF(" %d -> %d [label=\"", sourceNode, transitionPerTarget.key);
</del><ins>+ dataLogF(" %d -> %d [label=\"", sourceNodeId, transitionPerTarget.key);
</ins><span class="cx">
</span><span class="cx"> Vector<uint16_t> incommingCharacters = transitionPerTarget.value;
</span><span class="cx"> std::sort(incommingCharacters.begin(), incommingCharacters.end());
</span><span class="lines">@@ -134,6 +142,9 @@
</span><span class="cx">
</span><span class="cx"> dataLogF("\"];\n");
</span><span class="cx"> }
</span><ins>+
+ if (sourceNode.hasFallbackTransition)
+ dataLogF(" %d -> %d [label=\"[fallback]\"];\n", sourceNodeId, sourceNode.fallbackTransition);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void DFA::debugPrintDot() const
</span><span class="lines">@@ -174,7 +185,7 @@
</span><span class="cx">
</span><span class="cx"> dataLogF(" {\n");
</span><span class="cx"> for (unsigned i = 0; i < m_nodes.size(); ++i)
</span><del>- printTransition(i, m_nodes[i].transitions);
</del><ins>+ printTransitions(m_nodes, i);
</ins><span class="cx">
</span><span class="cx"> dataLogF(" }\n");
</span><span class="cx"> dataLogF("}\n");
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -41,6 +41,8 @@
</span><span class="cx"> class DFANode {
</span><span class="cx"> public:
</span><span class="cx"> HashMap<uint16_t, unsigned> transitions;
</span><ins>+ bool hasFallbackTransition = false;
+ unsigned fallbackTransition;
</ins><span class="cx"> Vector<uint64_t> actions;
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -53,6 +53,10 @@
</span><span class="cx"> ASSERT(to < m_nodes.size());
</span><span class="cx"> ASSERT(character);
</span><span class="cx">
</span><ins>+ NFANode& fromNode = m_nodes[from];
+ if (fromNode.transitionsOnAnyCharacter.contains(to))
+ return;
+
</ins><span class="cx"> auto addResult = m_nodes[from].transitions.add(character, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>());
</span><span class="cx"> addResult.iterator->value.add(to);
</span><span class="cx"> }
</span><span class="lines">@@ -66,6 +70,18 @@
</span><span class="cx"> addResult.iterator->value.add(to);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+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);
+}
+
</ins><span class="cx"> void NFA::setFinal(unsigned node, uint64_t ruleId)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(!m_nodes[node].finalRuleIds.contains(ruleId));
</span><span class="lines">@@ -114,8 +130,11 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void printTransition(unsigned sourceNode, const HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>>& transitions, uint16_t epsilonTransitionCharacter)
</del><ins>+static void printTransitions(const Vector<NFANode>& graph, unsigned sourceNode, uint16_t epsilonTransitionCharacter)
</ins><span class="cx"> {
</span><ins>+ const NFANode& node = graph[sourceNode];
+ const HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>>& transitions = node.transitions;
+
</ins><span class="cx"> HashMap<unsigned, HashSet<uint16_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
</span><span class="cx">
</span><span class="cx"> for (const auto& transition : transitions) {
</span><span class="lines">@@ -149,6 +168,9 @@
</span><span class="cx">
</span><span class="cx"> dataLogF("\"];\n");
</span><span class="cx"> }
</span><ins>+
+ for (unsigned targetOnAnyCharacter : node.transitionsOnAnyCharacter)
+ dataLogF(" %d -> %d [label=\"[any input]\"];\n", sourceNode, targetOnAnyCharacter);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void NFA::debugPrintDot() const
</span><span class="lines">@@ -193,7 +215,7 @@
</span><span class="cx">
</span><span class="cx"> dataLogF(" {\n");
</span><span class="cx"> for (unsigned i = 0; i < m_nodes.size(); ++i)
</span><del>- printTransition(i, m_nodes[i].transitions, epsilonTransitionCharacter);
</del><ins>+ printTransitions(m_nodes, i, epsilonTransitionCharacter);
</ins><span class="cx"> dataLogF(" }\n");
</span><span class="cx"> dataLogF("}\n");
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -48,6 +48,7 @@
</span><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><ins>+ void addTransitionsOnAnyCharacter(unsigned from, unsigned to);
</ins><span class="cx"> void setFinal(unsigned node, uint64_t ruleId);
</span><span class="cx">
</span><span class="cx"> unsigned graphSize() const;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFANode.h (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFANode.h 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/NFANode.h 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -41,6 +41,7 @@
</span><span class="cx"> class NFANode {
</span><span class="cx"> public:
</span><span class="cx"> HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> transitions;
</span><ins>+ HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsOnAnyCharacter;
</ins><span class="cx">
</span><span class="cx"> Vector<uint64_t> finalRuleIds;
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -291,9 +291,10 @@
</span><span class="cx"> NodeIdSet m_targets[128];
</span><span class="cx"> };
</span><span class="cx">
</span><del>-static inline void populateTransitions(SetTransitions& setTransitions, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, const Vector<Vector<unsigned>>& nfaNodeclosures)
</del><ins>+static inline void populateTransitions(SetTransitions& setTransitions, NodeIdSet& setFallbackTransition, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, const Vector<Vector<unsigned>>& nfaNodeclosures)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(!graph.isEmpty());
</span><ins>+ ASSERT(setFallbackTransition.isEmpty());
</ins><span class="cx"> #if !ASSERT_DISABLED
</span><span class="cx"> for (const NodeIdSet& set : setTransitions)
</span><span class="cx"> ASSERT(set.isEmpty());
</span><span class="lines">@@ -302,16 +303,36 @@
</span><span class="cx"> const unsigned* buffer = sourceNodeSet.buffer();
</span><span class="cx"> for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
</span><span class="cx"> unsigned nodeId = buffer[i];
</span><ins>+ const NFANode& nfaSourceNode = graph[nodeId];
+ if (!nfaSourceNode.transitionsOnAnyCharacter.isEmpty())
+ setFallbackTransition.add(nfaSourceNode.transitionsOnAnyCharacter.begin(), nfaSourceNode.transitionsOnAnyCharacter.end());
+ }
+ for (unsigned targetNodeId : setFallbackTransition)
+ extendSetWithClosure(nfaNodeclosures, targetNodeId, setFallbackTransition);
+
+ for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
+ unsigned nodeId = buffer[i];
</ins><span class="cx"> for (const auto& transitionSlot : graph[nodeId].transitions) {
</span><span class="cx"> NodeIdSet& targetSet = setTransitions[transitionSlot.key];
</span><span class="cx"> for (unsigned targetNodId : transitionSlot.value) {
</span><span class="cx"> targetSet.add(targetNodId);
</span><span class="cx"> extendSetWithClosure(nfaNodeclosures, targetNodId, targetSet);
</span><span class="cx"> }
</span><ins>+ targetSet.add(setFallbackTransition.begin(), setFallbackTransition.end());
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, Vector<DFANode>& dfaGraph, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
+{
+ NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, nfaNodeSet);
+ auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
+ if (uniqueNodeIdAddResult.isNewEntry)
+ unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
+
+ return uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
+}
+
</ins><span class="cx"> DFA NFAToDFA::convert(NFA& nfa)
</span><span class="cx"> {
</span><span class="cx"> Vector<NFANode>& nfaGraph = nfa.m_nodes;
</span><span class="lines">@@ -337,7 +358,8 @@
</span><span class="cx"> UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
</span><span class="cx">
</span><span class="cx"> unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
</span><del>- populateTransitions(transitionsFromClosedSet, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);
</del><ins>+ NodeIdSet setFallbackTransition;
+ populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);
</ins><span class="cx">
</span><span class="cx"> // FIXME: there should not be any transition on key 0.
</span><span class="cx"> for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {
</span><span class="lines">@@ -346,18 +368,19 @@
</span><span class="cx"> if (targetNodeSet.isEmpty())
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, targetNodeSet);
- auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
-
- unsigned targetNodeId = uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
</del><ins>+ unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);
</ins><span class="cx"> const auto addResult = dfaGraph[dfaNodeId].transitions.add(key, targetNodeId);
</span><span class="cx"> ASSERT_UNUSED(addResult, addResult.isNewEntry);
</span><span class="cx">
</span><del>- if (uniqueNodeIdAddResult.isNewEntry)
- unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
-
</del><span class="cx"> targetNodeSet.clear();
</span><span class="cx"> }
</span><ins>+ if (!setFallbackTransition.isEmpty()) {
+ unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);
+ DFANode& dfaSourceNode = dfaGraph[dfaNodeId];
+ ASSERT(!dfaSourceNode.hasFallbackTransition);
+ dfaSourceNode.hasFallbackTransition = true;
+ dfaSourceNode.fallbackTransition = targetNodeId;
+ }
</ins><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><span class="cx">
</span><span class="cx"> return DFA(WTF::move(dfaGraph), 0);
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsURLFilterParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/URLFilterParser.cpp (178856 => 178857)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-01-21 21:43:55 UTC (rev 178856)
+++ trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-01-21 21:56:22 UTC (rev 178857)
</span><span class="lines">@@ -245,8 +245,7 @@
</span><span class="cx"> {
</span><span class="cx"> if (trivialAtom & hasNonCharacterMask) {
</span><span class="cx"> ASSERT(trivialAtom & newlineClassIDBuiltinMask);
</span><del>- for (unsigned i = 1; i < 128; ++i)
- m_nfa.addTransition(source, target, i);
</del><ins>+ m_nfa.addTransitionsOnAnyCharacter(source, target);
</ins><span class="cx"> } else {
</span><span class="cx"> if (trivialAtom & caseInsensitiveMask) {
</span><span class="cx"> char character = static_cast<char>(trivialAtom & characterMask);
</span></span></pre>
</div>
</div>
</body>
</html>