<!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>[178739] 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/178739">178739</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-01-20 12:43:33 -0800 (Tue, 20 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Resolve the epsilon transitions for each state upfront instead of dynamically
https://bugs.webkit.org/show_bug.cgi?id=140654
Reviewed by Andreas Kling.
Instead of recomputing the epsilon-closure for each set, we compute the closure
of every element at the beginning of the transformation.
We then remove the epsilon transitions from the NFA to simplify populateTransitions().
The epsilon transitions are still there, but they are now in a separate graph we use
in parallel.
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::epsilonClosureExcludingSelf):
(WebCore::ContentExtensions::resolveEpsilonClosures):
(WebCore::ContentExtensions::extendSetWithClosure):
(WebCore::ContentExtensions::populateTransitions):
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::epsilonClosure): Deleted.
(WebCore::ContentExtensions::populateTransitionsExcludingEpsilon): Deleted.
* contentextensions/NFAToDFA.h:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAh">trunk/Source/WebCore/contentextensions/NFAToDFA.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (178738 => 178739)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-01-20 20:42:44 UTC (rev 178738)
+++ trunk/Source/WebCore/ChangeLog 2015-01-20 20:43:33 UTC (rev 178739)
</span><span class="lines">@@ -1,3 +1,27 @@
</span><ins>+2015-01-20 Benjamin Poulain <benjamin@webkit.org>
+
+ Resolve the epsilon transitions for each state upfront instead of dynamically
+ https://bugs.webkit.org/show_bug.cgi?id=140654
+
+ Reviewed by Andreas Kling.
+
+ Instead of recomputing the epsilon-closure for each set, we compute the closure
+ of every element at the beginning of the transformation.
+
+ We then remove the epsilon transitions from the NFA to simplify populateTransitions().
+ The epsilon transitions are still there, but they are now in a separate graph we use
+ in parallel.
+
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::epsilonClosureExcludingSelf):
+ (WebCore::ContentExtensions::resolveEpsilonClosures):
+ (WebCore::ContentExtensions::extendSetWithClosure):
+ (WebCore::ContentExtensions::populateTransitions):
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ (WebCore::ContentExtensions::epsilonClosure): Deleted.
+ (WebCore::ContentExtensions::populateTransitionsExcludingEpsilon): Deleted.
+ * contentextensions/NFAToDFA.h:
+
</ins><span class="cx"> 2015-01-20 Chris Dumez <cdumez@apple.com>
</span><span class="cx">
</span><span class="cx"> Log types of resources being loaded using DiagnosticLoggingClient
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (178738 => 178739)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-20 20:42:44 UTC (rev 178738)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-20 20:43:33 UTC (rev 178739)
</span><span class="lines">@@ -43,29 +43,59 @@
</span><span class="cx"> // FIXME: include the hash inside NodeIdSet.
</span><span class="cx"> typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> NodeIdSet;
</span><span class="cx">
</span><del>-static inline void epsilonClosure(NodeIdSet& nodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
</del><ins>+static inline void epsilonClosureExcludingSelf(const Vector<NFANode>& nfaGraph, unsigned nodeId, unsigned epsilonTransitionCharacter, Vector<unsigned>& output)
</ins><span class="cx"> {
</span><del>- ASSERT(!nodeSet.isEmpty());
- ASSERT(!graph.isEmpty());
</del><ins>+ const auto& transitions = nfaGraph[nodeId].transitions;
+ auto epsilonTransitionSlot = transitions.find(epsilonTransitionCharacter);
</ins><span class="cx">
</span><del>- // FIXME: fine a good inline size for unprocessedNodes.
- Vector<unsigned> unprocessedNodes;
- copyToVector(nodeSet, unprocessedNodes);
</del><ins>+ if (epsilonTransitionSlot == transitions.end())
+ return;
</ins><span class="cx">
</span><ins>+ NodeIdSet closure({ nodeId });
+ Vector<unsigned, 64> unprocessedNodes;
+ copyToVector(epsilonTransitionSlot->value, unprocessedNodes);
+ closure.add(unprocessedNodes.begin(), unprocessedNodes.end());
+ output = unprocessedNodes;
+
</ins><span class="cx"> do {
</span><span class="cx"> unsigned unprocessedNodeId = unprocessedNodes.takeLast();
</span><del>- const NFANode& node = graph[unprocessedNodeId];
</del><ins>+ const NFANode& node = nfaGraph[unprocessedNodeId];
</ins><span class="cx"> auto epsilonTransitionSlot = node.transitions.find(epsilonTransitionCharacter);
</span><span class="cx"> if (epsilonTransitionSlot != node.transitions.end()) {
</span><span class="cx"> for (unsigned targetNodeId : epsilonTransitionSlot->value) {
</span><del>- auto addResult = nodeSet.add(targetNodeId);
- if (addResult.isNewEntry)
</del><ins>+ auto addResult = closure.add(targetNodeId);
+ if (addResult.isNewEntry) {
</ins><span class="cx"> unprocessedNodes.append(targetNodeId);
</span><ins>+ output.append(targetNodeId);
+ }
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static void resolveEpsilonClosures(Vector<NFANode>& nfaGraph, unsigned epsilonTransitionCharacter, Vector<Vector<unsigned>>& nfaNodeClosures)
+{
+ unsigned nfaGraphSize = nfaGraph.size();
+ nfaNodeClosures.resize(nfaGraphSize);
+ for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId)
+ epsilonClosureExcludingSelf(nfaGraph, nodeId, epsilonTransitionCharacter, nfaNodeClosures[nodeId]);
+
+ for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId) {
+ if (!nfaNodeClosures[nodeId].isEmpty()) {
+ bool epsilonTransitionIsRemoved = nfaGraph[nodeId].transitions.remove(epsilonTransitionCharacter);
+ ASSERT_UNUSED(epsilonTransitionIsRemoved, epsilonTransitionIsRemoved);
+ }
+ }
+}
+
+static ALWAYS_INLINE void extendSetWithClosure(const Vector<Vector<unsigned>>& nfaNodeClosures, unsigned nodeId, NodeIdSet& set)
+{
+ ASSERT(set.contains(nodeId));
+ const Vector<unsigned>& nodeClosure = nfaNodeClosures[nodeId];
+ if (!nodeClosure.isEmpty())
+ set.add(nodeClosure.begin(), nodeClosure.end());
+}
+
</ins><span class="cx"> struct UniqueNodeIdSetImpl {
</span><span class="cx"> unsigned* buffer()
</span><span class="cx"> {
</span><span class="lines">@@ -234,7 +264,7 @@
</span><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-class SetTransitionsExcludingEpsilon {
</del><ins>+class SetTransitions {
</ins><span class="cx"> public:
</span><span class="cx"> NodeIdSet& operator[](unsigned index)
</span><span class="cx"> {
</span><span class="lines">@@ -261,49 +291,53 @@
</span><span class="cx"> NodeIdSet m_targets[128];
</span><span class="cx"> };
</span><span class="cx">
</span><del>-static inline void populateTransitionsExcludingEpsilon(SetTransitionsExcludingEpsilon& setTransitionsExcludingEpsilon, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
</del><ins>+static inline void populateTransitions(SetTransitions& setTransitions, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, const Vector<Vector<unsigned>>& nfaNodeclosures)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(!graph.isEmpty());
</span><span class="cx"> #if !ASSERT_DISABLED
</span><del>- for (const NodeIdSet& set : setTransitionsExcludingEpsilon)
</del><ins>+ for (const NodeIdSet& set : setTransitions)
</ins><span class="cx"> ASSERT(set.isEmpty());
</span><span class="cx"> #endif
</span><span class="cx">
</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><del>- const NFANode& node = graph[nodeId];
- for (const auto& transitionSlot : node.transitions) {
- if (transitionSlot.key != epsilonTransitionCharacter)
- setTransitionsExcludingEpsilon[transitionSlot.key].add(transitionSlot.value.begin(), transitionSlot.value.end());
</del><ins>+ for (const auto& transitionSlot : graph[nodeId].transitions) {
+ NodeIdSet& targetSet = setTransitions[transitionSlot.key];
+ for (unsigned targetNodId : transitionSlot.value) {
+ targetSet.add(targetNodId);
+ extendSetWithClosure(nfaNodeclosures, targetNodId, targetSet);
+ }
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-DFA NFAToDFA::convert(const NFA& nfa)
</del><ins>+DFA NFAToDFA::convert(NFA& nfa)
</ins><span class="cx"> {
</span><del>- Vector<DFANode> dfaGraph;
</del><ins>+ Vector<NFANode>& nfaGraph = nfa.m_nodes;
</ins><span class="cx">
</span><del>- const Vector<NFANode>& nfaGraph = nfa.m_nodes;
</del><ins>+ Vector<Vector<unsigned>> nfaNodeClosures;
+ resolveEpsilonClosures(nfaGraph, NFA::epsilonTransitionCharacter, nfaNodeClosures);
</ins><span class="cx">
</span><span class="cx"> NodeIdSet initialSet({ nfa.root() });
</span><del>- epsilonClosure(initialSet, nfaGraph, NFA::epsilonTransitionCharacter);
</del><ins>+ extendSetWithClosure(nfaNodeClosures, nfa.root(), initialSet);
</ins><span class="cx">
</span><span class="cx"> UniqueNodeIdSetTable uniqueNodeIdSetTable;
</span><span class="cx">
</span><ins>+ Vector<DFANode> dfaGraph;
</ins><span class="cx"> NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, initialSet);
</span><span class="cx"> auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx">
</span><span class="cx"> Vector<UniqueNodeIdSetImpl*> unprocessedNodes;
</span><span class="cx"> unprocessedNodes.append(addResult.iterator->impl());
</span><span class="cx">
</span><del>- SetTransitionsExcludingEpsilon transitionsFromClosedSet;
</del><ins>+ SetTransitions transitionsFromClosedSet;
</ins><span class="cx">
</span><span class="cx"> do {
</span><span class="cx"> UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
</span><span class="cx">
</span><span class="cx"> unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
</span><del>- populateTransitionsExcludingEpsilon(transitionsFromClosedSet, *uniqueNodeIdSetImpl, nfaGraph, NFA::epsilonTransitionCharacter);
</del><ins>+ populateTransitions(transitionsFromClosedSet, *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">@@ -312,8 +346,6 @@
</span><span class="cx"> if (targetNodeSet.isEmpty())
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- epsilonClosure(targetNodeSet, nfaGraph, NFA::epsilonTransitionCharacter);
-
</del><span class="cx"> NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, targetNodeSet);
</span><span class="cx"> auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.h (178738 => 178739)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-01-20 20:42:44 UTC (rev 178738)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.h 2015-01-20 20:43:33 UTC (rev 178739)
</span><span class="lines">@@ -39,7 +39,7 @@
</span><span class="cx"> // NFAToDFA provides a way to build a DFA corresponding to a NFA.
</span><span class="cx"> class NFAToDFA {
</span><span class="cx"> public:
</span><del>- static DFA convert(const NFA&);
</del><ins>+ static DFA convert(NFA&);
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre>
</div>
</div>
</body>
</html>