<!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>[183204] trunk</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/183204">183204</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2015-04-23 12:56:57 -0700 (Thu, 23 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Use less memory when compiling content extensions.
https://bugs.webkit.org/show_bug.cgi?id=144051
Patch by Alex Christensen <achristensen@webkit.org> on 2015-04-23
Reviewed by Darin Adler and Benjamin Poulain.
Source/WebCore:
No change in functionality, correctness already covered by existing tests.
Before this patch, a DFANode contained a HashSet of transitions.
Large vectors of DFANodes made many small HashSets, which was inefficient use of memory.
We now put all the actions and transitions into one big compact Vector and each node owns ranges in that vector.
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::recursiveMemoryUsed):
(WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
* contentextensions/CombinedURLFilters.h:
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
* contentextensions/ContentExtensionsDebugging.h:
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::memoryUsed):
(WebCore::ContentExtensions::DFANode::actions):
(WebCore::ContentExtensions::DFANode::transitions):
(WebCore::ContentExtensions::DFANode::fallbackTransitionDestination):
(WebCore::ContentExtensions::DFANode::changeFallbackTransition):
(WebCore::ContentExtensions::DFANode::addFallbackTransition):
(WebCore::ContentExtensions::DFANode::containsTransition):
(WebCore::ContentExtensions::DFANode::kill):
(WebCore::ContentExtensions::DFA::minimize):
(WebCore::ContentExtensions::DFA::DFA): Deleted.
(WebCore::ContentExtensions::DFA::operator=): Deleted.
* contentextensions/DFA.h:
* contentextensions/DFABytecodeCompiler.cpp:
(WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
(WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
(WebCore::ContentExtensions::DFABytecodeCompiler::compile):
* contentextensions/DFABytecodeCompiler.h:
* contentextensions/DFAMinimizer.cpp:
(WebCore::ContentExtensions::DFAMinimizer::minimize):
* contentextensions/DFAMinimizer.h:
* contentextensions/DFANode.h:
(WebCore::ContentExtensions::DFANode::isKilled):
(WebCore::ContentExtensions::DFANode::hasFallbackTransition):
(WebCore::ContentExtensions::DFANode::hasActions):
(WebCore::ContentExtensions::DFANode::transitionsLength):
(WebCore::ContentExtensions::DFANode::actionsLength):
(WebCore::ContentExtensions::DFANode::actionsStart):
(WebCore::ContentExtensions::DFANode::setActions):
(WebCore::ContentExtensions::DFANode::setTransitions):
(WebCore::ContentExtensions::DFANode::resetTransitions):
(WebCore::ContentExtensions::DFANode::transitionsStart):
(WebCore::ContentExtensions::DFANode::setHasFallbackTransitionWithoutChangingDFA):
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::memoryUsed):
* contentextensions/NFA.h:
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
(WebCore::ContentExtensions::getOrCreateDFANode):
(WebCore::ContentExtensions::NFAToDFA::convert):
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
(TestWebKitAPI::TEST_F):
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
(TestWebKitAPI::countLiveNodes):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFiltersh">trunk/Source/WebCore/contentextensions/CombinedURLFilters.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsDebuggingh">trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAh">trunk/Source/WebCore/contentextensions/DFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilerh">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizercpp">trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizerh">trunk/Source/WebCore/contentextensions/DFAMinimizer.h</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="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/ChangeLog 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -1,3 +1,65 @@
</span><ins>+2015-04-23 Alex Christensen <achristensen@webkit.org>
+
+ Use less memory when compiling content extensions.
+ https://bugs.webkit.org/show_bug.cgi?id=144051
+
+ Reviewed by Darin Adler and Benjamin Poulain.
+
+ No change in functionality, correctness already covered by existing tests.
+
+ Before this patch, a DFANode contained a HashSet of transitions.
+ Large vectors of DFANodes made many small HashSets, which was inefficient use of memory.
+ We now put all the actions and transitions into one big compact Vector and each node owns ranges in that vector.
+
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::recursiveMemoryUsed):
+ (WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
+ * contentextensions/CombinedURLFilters.h:
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/ContentExtensionsDebugging.h:
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::memoryUsed):
+ (WebCore::ContentExtensions::DFANode::actions):
+ (WebCore::ContentExtensions::DFANode::transitions):
+ (WebCore::ContentExtensions::DFANode::fallbackTransitionDestination):
+ (WebCore::ContentExtensions::DFANode::changeFallbackTransition):
+ (WebCore::ContentExtensions::DFANode::addFallbackTransition):
+ (WebCore::ContentExtensions::DFANode::containsTransition):
+ (WebCore::ContentExtensions::DFANode::kill):
+ (WebCore::ContentExtensions::DFA::minimize):
+ (WebCore::ContentExtensions::DFA::DFA): Deleted.
+ (WebCore::ContentExtensions::DFA::operator=): Deleted.
+ * contentextensions/DFA.h:
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compile):
+ * contentextensions/DFABytecodeCompiler.h:
+ * contentextensions/DFAMinimizer.cpp:
+ (WebCore::ContentExtensions::DFAMinimizer::minimize):
+ * contentextensions/DFAMinimizer.h:
+ * contentextensions/DFANode.h:
+ (WebCore::ContentExtensions::DFANode::isKilled):
+ (WebCore::ContentExtensions::DFANode::hasFallbackTransition):
+ (WebCore::ContentExtensions::DFANode::hasActions):
+ (WebCore::ContentExtensions::DFANode::transitionsLength):
+ (WebCore::ContentExtensions::DFANode::actionsLength):
+ (WebCore::ContentExtensions::DFANode::actionsStart):
+ (WebCore::ContentExtensions::DFANode::setActions):
+ (WebCore::ContentExtensions::DFANode::setTransitions):
+ (WebCore::ContentExtensions::DFANode::resetTransitions):
+ (WebCore::ContentExtensions::DFANode::transitionsStart):
+ (WebCore::ContentExtensions::DFANode::setHasFallbackTransitionWithoutChangingDFA):
+ * contentextensions/NFA.cpp:
+ (WebCore::ContentExtensions::NFA::memoryUsed):
+ * contentextensions/NFA.h:
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
+ (WebCore::ContentExtensions::getOrCreateDFANode):
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+
</ins><span class="cx"> 2015-04-23 David Hyatt <hyatt@apple.com>
</span><span class="cx">
</span><span class="cx"> Don't fire a bunch of mouse moveds during scrolling.
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -43,6 +43,21 @@
</span><span class="cx"> bool inVariableLengthPrefix { false };
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+static size_t recursiveMemoryUsed(const std::unique_ptr<PrefixTreeVertex>& node)
+{
+ size_t size = sizeof(PrefixTreeVertex)
+ + node->edges.capacity() * sizeof(std::pair<Term, std::unique_ptr<PrefixTreeVertex>>)
+ + node->finalActions.capacity() * sizeof(uint64_t);
+ for (const auto& child : node->edges.values())
+ size += recursiveMemoryUsed(child);
+ return size;
+}
+
+size_t CombinedURLFilters::memoryUsed() const
+{
+ return recursiveMemoryUsed(m_prefixTreeRoot);
+}
+
</ins><span class="cx"> CombinedURLFilters::CombinedURLFilters()
</span><span class="cx"> : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>())
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFiltersh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -47,6 +47,8 @@
</span><span class="cx"> Vector<NFA> createNFAs() const;
</span><span class="cx"> void clear();
</span><span class="cx">
</span><ins>+ size_t memoryUsed() const;
+
</ins><span class="cx"> private:
</span><span class="cx"> std::unique_ptr<PrefixTreeVertex> m_prefixTreeRoot;
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -134,6 +134,7 @@
</span><span class="cx"> Vector<SerializedActionByte> actions;
</span><span class="cx"> Vector<unsigned> actionLocations = serializeActions(parsedRuleList, actions);
</span><span class="cx"> client.writeActions(WTF::move(actions));
</span><ins>+ LOG_LARGE_STRUCTURES(actions, actions.capacity() * sizeof(SerializedActionByte));
</ins><span class="cx"> actions.clear();
</span><span class="cx">
</span><span class="cx"> HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> universalActionLocations;
</span><span class="lines">@@ -164,6 +165,8 @@
</span><span class="cx"> if (contentExtensionRule.action().type() == ActionType::IgnorePreviousRules)
</span><span class="cx"> ignorePreviousRulesSeen = true;
</span><span class="cx"> }
</span><ins>+ LOG_LARGE_STRUCTURES(parsedRuleList, parsedRuleList.capacity() * sizeof(ContentExtensionRule)); // Doesn't include strings.
+ LOG_LARGE_STRUCTURES(actionLocations, actionLocations.capacity() * sizeof(unsigned));
</ins><span class="cx"> parsedRuleList.clear();
</span><span class="cx"> actionLocations.clear();
</span><span class="cx">
</span><span class="lines">@@ -177,6 +180,7 @@
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> Vector<NFA> nfas = combinedURLFilters.createNFAs();
</span><ins>+ LOG_LARGE_STRUCTURES(combinedURLFilters, combinedURLFilters.memoryUsed());
</ins><span class="cx"> combinedURLFilters.clear();
</span><span class="cx"> if (!nfas.size() && universalActionLocations.size())
</span><span class="cx"> nfas.append(NFA());
</span><span class="lines">@@ -204,6 +208,7 @@
</span><span class="cx"> double dfaBuildTimeStart = monotonicallyIncreasingTime();
</span><span class="cx"> #endif
</span><span class="cx"> DFA dfa = NFAToDFA::convert(nfas[i]);
</span><ins>+ LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
</ins><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> double dfaBuildTimeEnd = monotonicallyIncreasingTime();
</span><span class="cx"> dataLogF(" Time spent building the DFA %zu: %f\n", i, (dfaBuildTimeEnd - dfaBuildTimeStart));
</span><span class="lines">@@ -222,16 +227,22 @@
</span><span class="cx"> WTFLogAlways("DFA %zu", i);
</span><span class="cx"> dfa.debugPrintDot();
</span><span class="cx"> #endif
</span><del>-
- ASSERT_WITH_MESSAGE(!dfa.nodeAt(dfa.root()).actions.size(), "All actions on the DFA root should come from regular expressions that match everything.");
</del><ins>+ ASSERT_WITH_MESSAGE(!dfa.nodes[dfa.root].hasActions(), "All actions on the DFA root should come from regular expressions that match everything.");
</ins><span class="cx"> if (!i) {
</span><span class="cx"> // Put all the universal actions on the first DFA.
</span><ins>+ unsigned actionsStart = dfa.actions.size();
+ dfa.actions.reserveCapacity(dfa.actions.size() + universalActionLocations.size());
</ins><span class="cx"> for (uint64_t actionLocation : universalActionLocations)
</span><del>- dfa.nodeAt(dfa.root()).actions.append(actionLocation);
</del><ins>+ dfa.actions.uncheckedAppend(actionLocation);
+ unsigned actionsEnd = dfa.actions.size();
+ unsigned actionsLength = actionsEnd - actionsStart;
+ RELEASE_ASSERT_WITH_MESSAGE(actionsLength < std::numeric_limits<uint16_t>::max(), "Too many uncombined actions that match everything");
+ dfa.nodes[dfa.root].setActions(actionsStart, static_cast<uint16_t>(actionsLength));
</ins><span class="cx"> }
</span><span class="cx"> DFABytecodeCompiler compiler(dfa, bytecode);
</span><span class="cx"> compiler.compile();
</span><span class="cx"> }
</span><ins>+ LOG_LARGE_STRUCTURES(universalActionLocations, universalActionLocations.capacity() * sizeof(unsigned));
</ins><span class="cx"> universalActionLocations.clear();
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="lines">@@ -240,9 +251,15 @@
</span><span class="cx"> dataLogF(" Bytecode size %zu\n", bytecode.size());
</span><span class="cx"> dataLogF(" DFA count %zu\n", nfas.size());
</span><span class="cx"> #endif
</span><ins>+ size_t nfaMemoryUsed = 0;
+ for (const NFA& nfa : nfas)
+ nfaMemoryUsed += sizeof(NFA) + nfa.memoryUsed();
+ LOG_LARGE_STRUCTURES(nfas, nfaMemoryUsed);
</ins><span class="cx"> nfas.clear();
</span><span class="cx">
</span><ins>+ LOG_LARGE_STRUCTURES(bytecode, bytecode.capacity() * sizeof(uint8_t));
</ins><span class="cx"> client.writeBytecode(WTF::move(bytecode));
</span><ins>+ bytecode.clear();
</ins><span class="cx">
</span><span class="cx"> return { };
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsDebuggingh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -35,6 +35,12 @@
</span><span class="cx"> #define CONTENT_EXTENSIONS_MEMORY_REPORTING 0
</span><span class="cx"> #define CONTENT_EXTENSIONS_PAGE_SIZE 16384
</span><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+#define LOG_LARGE_STRUCTURES(name, size) if (size > 1000000) { WTFLogAlways("NAME: %s SIZE %d", #name, (int)(size)); };
+#else
+#define LOG_LARGE_STRUCTURES(name, size)
+#endif
+
</ins><span class="cx"> #endif // ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><span class="cx"> #endif // ContentExtensionsDebugging_h
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -35,34 +35,90 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-DFA::DFA()
- : m_root(0)
</del><ins>+size_t DFA::memoryUsed() const
</ins><span class="cx"> {
</span><ins>+ return sizeof(DFA)
+ + actions.size() * sizeof(uint64_t)
+ + transitions.size() * sizeof(std::pair<uint8_t, uint32_t>)
+ + nodes.size() * sizeof(DFANode);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-DFA::DFA(Vector<DFANode>&& nodes, unsigned rootIndex)
- : m_nodes(WTF::move(nodes))
- , m_root(rootIndex)
</del><ins>+// FIXME: Make DFANode.cpp.
+Vector<uint64_t> DFANode::actions(const DFA& dfa) const
</ins><span class="cx"> {
</span><del>- ASSERT(rootIndex < m_nodes.size());
</del><ins>+ // FIXME: Use iterators instead of copying the Vector elements.
+ Vector<uint64_t> vector;
+ vector.reserveInitialCapacity(m_actionsLength);
+ for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
+ vector.uncheckedAppend(dfa.actions[i]);
+ return vector;
</ins><span class="cx"> }
</span><ins>+
+Vector<std::pair<uint8_t, uint32_t>> DFANode::transitions(const DFA& dfa) const
+{
+ // FIXME: Use iterators instead of copying the Vector elements.
+ Vector<std::pair<uint8_t, uint32_t>> vector;
+ vector.reserveInitialCapacity(transitionsLength());
+ for (uint32_t i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i)
+ vector.uncheckedAppend(dfa.transitions[i]);
+ return vector;
+}
</ins><span class="cx">
</span><del>-DFA::DFA(const DFA& dfa)
- : m_nodes(dfa.m_nodes)
- , m_root(dfa.m_root)
</del><ins>+uint32_t DFANode::fallbackTransitionDestination(const DFA& dfa) const
</ins><span class="cx"> {
</span><ins>+ RELEASE_ASSERT(hasFallbackTransition());
+
+ // If there is a fallback transition, it is just after the other transitions and has an invalid ASCII character to mark it as a fallback transition.
+ ASSERT(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits<uint8_t>::max());
+ return dfa.transitions[m_transitionsStart + m_transitionsLength].second;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-DFA& DFA::operator=(const DFA& dfa)
</del><ins>+void DFANode::changeFallbackTransition(DFA& dfa, uint32_t newDestination)
</ins><span class="cx"> {
</span><del>- m_nodes = dfa.m_nodes;
- m_root = dfa.m_root;
- return *this;
</del><ins>+ RELEASE_ASSERT(hasFallbackTransition());
+ ASSERT_WITH_MESSAGE(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits<uint8_t>::max(), "When changing a fallback transition, the fallback transition should already be marked as such");
+ dfa.transitions[m_transitionsStart + m_transitionsLength] = std::pair<uint8_t, uint32_t>(std::numeric_limits<uint8_t>::max(), newDestination);
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+void DFANode::addFallbackTransition(DFA& dfa, uint32_t destination)
+{
+ RELEASE_ASSERT_WITH_MESSAGE(dfa.transitions.size() == m_transitionsStart + m_transitionsLength, "Adding a fallback transition should only happen if the node is at the end");
+ dfa.transitions.append(std::pair<uint8_t, uint32_t>(std::numeric_limits<uint8_t>::max(), destination));
+ ASSERT(!(m_flags & HasFallbackTransition));
+ m_flags |= HasFallbackTransition;
+}
+
+bool DFANode::containsTransition(uint8_t transition, DFA& dfa)
+{
+ // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.
+ ASSERT(m_transitionsLength <= 128);
+ for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
+ if (dfa.transitions[i].first == transition)
+ return true;
+ }
+ return false;
+}
+
+void DFANode::kill(DFA& dfa)
+{
+ ASSERT(m_flags != IsKilled);
+ m_flags = IsKilled; // Killed nodes don't have any other flags.
+
+ // Invalidate the now-unused memory in the DFA to make finding bugs easier.
+ for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i)
+ dfa.transitions[i] = std::make_pair(std::numeric_limits<uint8_t>::max(), std::numeric_limits<uint32_t>::max());
+ for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
+ dfa.actions[i] = std::numeric_limits<uint64_t>::max();
+
+ m_actionsStart = 0;
+ m_actionsLength = 0;
+ m_transitionsStart = 0;
+ m_transitionsLength = 0;
+};
+
</ins><span class="cx"> void DFA::minimize()
</span><span class="cx"> {
</span><del>- m_root = DFAMinimizer::minimize(m_nodes, m_root);
</del><ins>+ DFAMinimizer::minimize(*this);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -37,28 +37,19 @@
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><span class="cx"> // The DFA abstract a partial DFA graph in a compact form.
</span><del>-class WEBCORE_EXPORT DFA {
-public:
- DFA();
- DFA(Vector<DFANode>&& nodes, unsigned rootIndex);
- DFA(const DFA& dfa);
-
- DFA& operator=(const DFA&);
-
- unsigned root() const { return m_root; }
- unsigned size() const { return m_nodes.size(); }
- const DFANode& nodeAt(unsigned i) const { return m_nodes[i]; }
- DFANode& nodeAt(unsigned i) { return m_nodes[i]; }
-
</del><ins>+struct WEBCORE_EXPORT DFA {
</ins><span class="cx"> void minimize();
</span><ins>+ size_t memoryUsed() const;
</ins><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #endif
</span><del>-
-private:
- Vector<DFANode> m_nodes;
- unsigned m_root;
</del><ins>+
+ Vector<uint64_t> actions;
+ // FIXME: transitions could be two Vectors to save even more memory.
+ Vector<std::pair<uint8_t, uint32_t>> transitions;
+ Vector<DFANode> nodes;
+ unsigned root { 0 };
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -95,8 +95,8 @@
</span><span class="cx">
</span><span class="cx"> void DFABytecodeCompiler::compileNode(unsigned index, bool root)
</span><span class="cx"> {
</span><del>- const DFANode& node = m_dfa.nodeAt(index);
- if (node.isKilled) {
</del><ins>+ const DFANode& node = m_dfa.nodes[index];
+ if (node.isKilled()) {
</ins><span class="cx"> m_nodeStartOffsets[index] = std::numeric_limits<unsigned>::max();
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="lines">@@ -105,7 +105,7 @@
</span><span class="cx"> if (!root)
</span><span class="cx"> m_nodeStartOffsets[index] = m_bytecode.size();
</span><span class="cx">
</span><del>- for (uint64_t action : node.actions) {
</del><ins>+ for (uint64_t action : node.actions(m_dfa)) {
</ins><span class="cx"> // High bits are used to store flags. See compileRuleList.
</span><span class="cx"> if (action & 0xFFFF00000000)
</span><span class="cx"> emitTestFlagsAndAppendAction(static_cast<uint16_t>(action >> 32), static_cast<unsigned>(action));
</span><span class="lines">@@ -123,14 +123,14 @@
</span><span class="cx">
</span><span class="cx"> void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)
</span><span class="cx"> {
</span><del>- unsigned destinations[128];
- const unsigned noDestination = std::numeric_limits<unsigned>::max();
- for (uint16_t i = 0; i < 128; i++) {
- auto it = node.transitions.find(i);
- if (it == node.transitions.end())
- destinations[i] = noDestination;
- else
- destinations[i] = it->value;
</del><ins>+ uint32_t destinations[128];
+ memset(destinations, 0xff, sizeof(destinations));
+ const uint32_t noDestination = std::numeric_limits<uint32_t>::max();
+
+ for (const auto& pair : node.transitions(m_dfa)) {
+ RELEASE_ASSERT(pair.first < WTF_ARRAY_LENGTH(destinations));
+ ASSERT_WITH_MESSAGE(destinations[pair.first] == noDestination, "Transitions should be unique");
+ destinations[pair.first] = pair.second;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector<Range> ranges;
</span><span class="lines">@@ -138,7 +138,7 @@
</span><span class="cx"> bool hasRangeMin = false;
</span><span class="cx"> for (uint8_t i = 0; i < 128; i++) {
</span><span class="cx"> if (hasRangeMin) {
</span><del>- ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
</del><ins>+ ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition() && node.fallbackTransitionDestination(m_dfa) == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
</ins><span class="cx"> if (destinations[i] != destinations[rangeMin]) {
</span><span class="cx">
</span><span class="cx"> // This is the end of a range. Check if it can be case insensitive.
</span><span class="lines">@@ -186,8 +186,8 @@
</span><span class="cx">
</span><span class="cx"> for (const auto& range : ranges)
</span><span class="cx"> compileCheckForRange(range);
</span><del>- if (node.hasFallbackTransition)
- emitJump(node.fallbackTransition);
</del><ins>+ if (node.hasFallbackTransition())
+ emitJump(node.fallbackTransitionDestination(m_dfa));
</ins><span class="cx"> else
</span><span class="cx"> emitTerminate();
</span><span class="cx"> }
</span><span class="lines">@@ -208,12 +208,12 @@
</span><span class="cx"> // DFA header.
</span><span class="cx"> unsigned startLocation = m_bytecode.size();
</span><span class="cx"> append<unsigned>(m_bytecode, 0);
</span><del>- m_nodeStartOffsets.resize(m_dfa.size());
</del><ins>+ m_nodeStartOffsets.resize(m_dfa.nodes.size());
</ins><span class="cx">
</span><span class="cx"> // Make sure the root is always at the beginning of the bytecode.
</span><del>- compileNode(m_dfa.root(), true);
- for (unsigned i = 0; i < m_dfa.size(); i++) {
- if (i != m_dfa.root())
</del><ins>+ compileNode(m_dfa.root, true);
+ for (unsigned i = 0; i < m_dfa.nodes.size(); i++) {
+ if (i != m_dfa.root)
</ins><span class="cx"> compileNode(i, false);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilerh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -35,7 +35,7 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-class DFA;
</del><ins>+struct DFA;
</ins><span class="cx"> class DFANode;
</span><span class="cx">
</span><span class="cx"> class DFABytecodeCompiler {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -28,8 +28,12 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "DFA.h"
+#include "DFANode.h"
+#include <wtf/HashMap.h>
</ins><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx"> #include <wtf/StringHasher.h>
</span><ins>+#include <wtf/Vector.h>
</ins><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="cx"> namespace ContentExtensions {
</span><span class="lines">@@ -39,20 +43,22 @@
</span><span class="cx"> // simplifyTransitions() tries to collapse individual transitions into fallback transitions.
</span><span class="cx"> // After simplifyTransitions(), you can also make the assumption that a fallback transition target will never be
</span><span class="cx"> // also the target of an individual transition.
</span><del>-static void simplifyTransitions(Vector<DFANode>& dfaGraph)
</del><ins>+static void simplifyTransitions(DFA& dfa)
</ins><span class="cx"> {
</span><del>- for (DFANode& dfaNode : dfaGraph) {
- if (!dfaNode.hasFallbackTransition
- && ((dfaNode.transitions.size() == 126 && !dfaNode.transitions.contains(0))
- || (dfaNode.transitions.size() == 127 && dfaNode.transitions.contains(0)))) {
</del><ins>+ for (DFANode& dfaNode : dfa.nodes) {
+ bool addingFallback = false;
+ uint32_t newFallbackDestination = std::numeric_limits<uint32_t>::max();
+ if (!dfaNode.hasFallbackTransition()
+ && ((dfaNode.transitionsLength() == 126 && !dfaNode.containsTransition(0, dfa))
+ || (dfaNode.transitionsLength() == 127 && dfaNode.containsTransition(0, dfa)))) {
</ins><span class="cx"> unsigned bestTarget = std::numeric_limits<unsigned>::max();
</span><span class="cx"> unsigned bestTargetScore = 0;
</span><span class="cx"> HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;
</span><del>- for (const auto& transition : dfaNode.transitions) {
- if (!transition.key)
</del><ins>+ for (const auto& transition : dfaNode.transitions(dfa)) {
+ if (!transition.first)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- unsigned transitionTarget = transition.value;
</del><ins>+ unsigned transitionTarget = transition.second;
</ins><span class="cx"> auto addResult = targetHistogram.add(transitionTarget, 1);
</span><span class="cx"> if (!addResult.isNewEntry)
</span><span class="cx"> addResult.iterator->value++;
</span><span class="lines">@@ -64,20 +70,44 @@
</span><span class="cx"> }
</span><span class="cx"> ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");
</span><span class="cx">
</span><del>- dfaNode.hasFallbackTransition = true;
- dfaNode.fallbackTransition = bestTarget;
</del><ins>+ newFallbackDestination = bestTarget;
+ addingFallback = true;
</ins><span class="cx"> }
</span><ins>+
+ // Use the same location to write new transitions possibly followed by unused memory.
+ // We can do this because we are always decreasing the amount of memory used.
+ // We will probably need something like setHasFallbackTransitionWithoutChangingDFA to do that.
</ins><span class="cx">
</span><del>- if (dfaNode.hasFallbackTransition) {
- Vector<uint16_t, 128> keys;
- DFANodeTransitions& transitions = dfaNode.transitions;
- copyKeysToVector(transitions, keys);
-
- for (uint16_t key : keys) {
- auto transitionIterator = transitions.find(key);
- if (transitionIterator->value == dfaNode.fallbackTransition)
- transitions.remove(transitionIterator);
</del><ins>+ unsigned oldFallbackTransition = std::numeric_limits<uint32_t>::max();
+ bool hadFallbackTransition = dfaNode.hasFallbackTransition();
+ if (hadFallbackTransition)
+ oldFallbackTransition = dfaNode.fallbackTransitionDestination(dfa);
+
+ newFallbackDestination = (newFallbackDestination == std::numeric_limits<uint32_t>::max() ? oldFallbackTransition : newFallbackDestination);
+ ASSERT(!addingFallback || (newFallbackDestination != std::numeric_limits<uint32_t>::max() && oldFallbackTransition == std::numeric_limits<uint32_t>::max()));
+ bool willHaveFallback = newFallbackDestination != std::numeric_limits<uint32_t>::max();
+ dfaNode.setHasFallbackTransitionWithoutChangingDFA(willHaveFallback);
+
+ if (willHaveFallback) {
+ Vector<std::pair<uint8_t, uint32_t>> transitions = dfaNode.transitions(dfa);
+ unsigned availableSlotCount = transitions.size() + hadFallbackTransition;
+ for (unsigned i = 0; i < transitions.size(); ++i) {
+ if (transitions[i].second == newFallbackDestination)
+ transitions.remove(i--);
</ins><span class="cx"> }
</span><ins>+
+ RELEASE_ASSERT(transitions.size() + willHaveFallback <= availableSlotCount);
+
+ unsigned firstSlot = dfaNode.transitionsStart();
+ dfaNode.resetTransitions(firstSlot, transitions.size());
+ for (unsigned i = 0; i < transitions.size(); ++i)
+ dfa.transitions[firstSlot + i] = transitions[i];
+ for (unsigned i = transitions.size(); i < availableSlotCount; ++i) {
+ // Invalidate now-unused memory to make finding bugs easier.
+ dfa.transitions[firstSlot + i] = std::make_pair(std::numeric_limits<uint8_t>::max(), std::numeric_limits<uint32_t>::max());
+ }
+ if (willHaveFallback)
+ dfa.transitions[firstSlot + transitions.size()] = std::make_pair(std::numeric_limits<uint8_t>::max(), newFallbackDestination);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -221,24 +251,24 @@
</span><span class="cx">
</span><span class="cx"> class FullGraphPartition {
</span><span class="cx"> public:
</span><del>- FullGraphPartition(const Vector<DFANode>& dfaGraph)
</del><ins>+ FullGraphPartition(const DFA& dfa)
</ins><span class="cx"> {
</span><del>- m_nodePartition.initialize(dfaGraph.size());
</del><ins>+ m_nodePartition.initialize(dfa.nodes.size());
</ins><span class="cx">
</span><del>- m_flattenedTransitionsStartOffsetPerNode.resize(dfaGraph.size());
</del><ins>+ m_flattenedTransitionsStartOffsetPerNode.resize(dfa.nodes.size());
</ins><span class="cx"> for (unsigned& counter : m_flattenedTransitionsStartOffsetPerNode)
</span><span class="cx"> counter = 0;
</span><span class="cx">
</span><del>- m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfaGraph.size());
</del><ins>+ m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfa.nodes.size());
</ins><span class="cx"> for (unsigned& counter : m_flattenedFallbackTransitionsStartOffsetPerNode)
</span><span class="cx"> counter = 0;
</span><span class="cx">
</span><span class="cx"> // Count the number of incoming transitions per node.
</span><del>- for (const DFANode& dfaNode : dfaGraph) {
- for (const auto& transition : dfaNode.transitions)
- ++m_flattenedTransitionsStartOffsetPerNode[transition.value];
- if (dfaNode.hasFallbackTransition)
- ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransition];
</del><ins>+ for (const DFANode& dfaNode : dfa.nodes) {
+ for (const auto& transition : dfaNode.transitions(dfa))
+ ++m_flattenedTransitionsStartOffsetPerNode[transition.second];
+ if (dfaNode.hasFallbackTransition())
+ ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransitionDestination(dfa)];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Accumulate the offsets.
</span><span class="lines">@@ -259,11 +289,11 @@
</span><span class="cx"> unsigned flattenedFallbackTransitionsSize = fallbackTransitionAccumulator;
</span><span class="cx">
</span><span class="cx"> // Next, let's fill the transition table and set up the size of each group at the same time.
</span><del>- m_flattenedTransitionsSizePerNode.resize(dfaGraph.size());
</del><ins>+ m_flattenedTransitionsSizePerNode.resize(dfa.nodes.size());
</ins><span class="cx"> for (unsigned& counter : m_flattenedTransitionsSizePerNode)
</span><span class="cx"> counter = 0;
</span><span class="cx">
</span><del>- m_flattenedFallbackTransitionsSizePerNode.resize(dfaGraph.size());
</del><ins>+ m_flattenedFallbackTransitionsSizePerNode.resize(dfa.nodes.size());
</ins><span class="cx"> for (unsigned& counter : m_flattenedFallbackTransitionsSizePerNode)
</span><span class="cx"> counter = 0;
</span><span class="cx">
</span><span class="lines">@@ -271,20 +301,20 @@
</span><span class="cx">
</span><span class="cx"> m_flattenedFallbackTransitions.resize(flattenedFallbackTransitionsSize);
</span><span class="cx">
</span><del>- for (unsigned i = 0; i < dfaGraph.size(); ++i) {
- const DFANode& dfaNode = dfaGraph[i];
- for (const auto& transition : dfaNode.transitions) {
- unsigned targetNodeIndex = transition.value;
</del><ins>+ for (unsigned i = 0; i < dfa.nodes.size(); ++i) {
+ const DFANode& dfaNode = dfa.nodes[i];
+ for (const auto& transition : dfaNode.transitions(dfa)) {
+ unsigned targetNodeIndex = transition.second;
</ins><span class="cx">
</span><span class="cx"> unsigned start = m_flattenedTransitionsStartOffsetPerNode[targetNodeIndex];
</span><span class="cx"> unsigned offset = m_flattenedTransitionsSizePerNode[targetNodeIndex];
</span><span class="cx">
</span><del>- m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.key });
</del><ins>+ m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.first });
</ins><span class="cx">
</span><span class="cx"> ++m_flattenedTransitionsSizePerNode[targetNodeIndex];
</span><span class="cx"> }
</span><del>- if (dfaNode.hasFallbackTransition) {
- unsigned targetNodeIndex = dfaNode.fallbackTransition;
</del><ins>+ if (dfaNode.hasFallbackTransition()) {
+ unsigned targetNodeIndex = dfaNode.fallbackTransitionDestination(dfa);
</ins><span class="cx">
</span><span class="cx"> unsigned start = m_flattenedFallbackTransitionsStartOffsetPerNode[targetNodeIndex];
</span><span class="cx"> unsigned offset = m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];
</span><span class="lines">@@ -403,20 +433,25 @@
</span><span class="cx"> enum EmptyValueTag { EmptyValue };
</span><span class="cx"> explicit ActionKey(EmptyValueTag) { state = Empty; }
</span><span class="cx">
</span><del>- explicit ActionKey(const Vector<uint64_t>& actions)
- : actions(&actions)
- , state(Valid)
</del><ins>+ explicit ActionKey(const DFA* dfa, uint32_t actionsStart, uint16_t actionsLength)
+ : dfa(dfa)
+ , actionsStart(actionsStart)
+ , actionsLength(actionsLength)
</ins><span class="cx"> {
</span><span class="cx"> StringHasher hasher;
</span><del>- hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(actions.data()), actions.size() * sizeof(uint64_t) / sizeof(UChar));
</del><ins>+ hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(&dfa->actions[actionsStart]), actionsLength * sizeof(uint64_t) / sizeof(UChar));
</ins><span class="cx"> hash = hasher.hash();
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool isEmptyValue() const { return state == Empty; }
</span><span class="cx"> bool isDeletedValue() const { return state == Deleted; }
</span><span class="cx">
</span><del>- const Vector<uint64_t>* actions;
</del><span class="cx"> unsigned hash;
</span><ins>+
+ const DFA* dfa;
+ uint32_t actionsStart;
+ uint16_t actionsLength;
+
</ins><span class="cx"> enum {
</span><span class="cx"> Valid,
</span><span class="cx"> Empty,
</span><span class="lines">@@ -430,9 +465,18 @@
</span><span class="cx"> return actionKey.hash;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- static bool equal(const ActionKey& a, const ActionKey& b)
</del><ins>+ // FIXME: Release builds on Mavericks fail with this inlined.
+ __attribute__((noinline)) static bool equal(const ActionKey& a, const ActionKey& b)
</ins><span class="cx"> {
</span><del>- return a.state == b.state && *a.actions == *b.actions;
</del><ins>+ if (a.state != b.state
+ || a.dfa != b.dfa
+ || a.actionsLength != b.actionsLength)
+ return false;
+ for (uint16_t i = 0; i < a.actionsLength; ++i) {
+ if (a.dfa->actions[a.actionsStart + i] != a.dfa->actions[b.actionsStart + i])
+ return false;
+ }
+ return true;
</ins><span class="cx"> }
</span><span class="cx"> static const bool safeToCompareToEmptyOrDeleted = false;
</span><span class="cx"> };
</span><span class="lines">@@ -443,21 +487,21 @@
</span><span class="cx">
</span><span class="cx"> } // anonymous namespace.
</span><span class="cx">
</span><del>-unsigned DFAMinimizer::minimize(Vector<DFANode>& dfaGraph, unsigned root)
</del><ins>+void DFAMinimizer::minimize(DFA& dfa)
</ins><span class="cx"> {
</span><del>- simplifyTransitions(dfaGraph);
</del><ins>+ simplifyTransitions(dfa);
</ins><span class="cx">
</span><del>- FullGraphPartition fullGraphPartition(dfaGraph);
</del><ins>+ FullGraphPartition fullGraphPartition(dfa);
</ins><span class="cx">
</span><span class="cx"> // Unlike traditional minimization final states can be differentiated by their action.
</span><span class="cx"> // Instead of creating a single set for the final state, we partition by actions from
</span><span class="cx"> // the start.
</span><span class="cx"> HashMap<ActionKey, Vector<unsigned>, ActionKeyHash, ActionKeyHashTraits> finalStates;
</span><del>- for (unsigned i = 0; i < dfaGraph.size(); ++i) {
- Vector<uint64_t>& actions = dfaGraph[i].actions;
- if (actions.size()) {
- std::sort(actions.begin(), actions.end());
- auto addResult = finalStates.add(ActionKey(actions), Vector<unsigned>());
</del><ins>+ for (unsigned i = 0; i < dfa.nodes.size(); ++i) {
+ const DFANode& node = dfa.nodes[i];
+ if (node.hasActions()) {
+ // FIXME: Sort the actions in the dfa to make nodes that have the same actions in different order equal.
+ auto addResult = finalStates.add(ActionKey(&dfa, node.actionsStart(), node.actionsLength()), Vector<unsigned>());
</ins><span class="cx"> addResult.iterator->value.append(i);
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -481,36 +525,32 @@
</span><span class="cx"> fullGraphPartition.splitByFallbackTransitions();
</span><span class="cx">
</span><span class="cx"> Vector<unsigned> relocationVector;
</span><del>- relocationVector.reserveInitialCapacity(dfaGraph.size());
- for (unsigned i = 0; i < dfaGraph.size(); ++i)
- relocationVector.append(i);
</del><ins>+ relocationVector.reserveInitialCapacity(dfa.nodes.size());
+ for (unsigned i = 0; i < dfa.nodes.size(); ++i)
+ relocationVector.uncheckedAppend(i);
</ins><span class="cx">
</span><span class="cx"> // Kill the useless nodes and keep track of the new node transitions should point to.
</span><del>- for (unsigned i = 0; i < dfaGraph.size(); ++i) {
</del><ins>+ for (unsigned i = 0; i < dfa.nodes.size(); ++i) {
</ins><span class="cx"> unsigned replacement = fullGraphPartition.nodeReplacement(i);
</span><span class="cx"> if (i != replacement) {
</span><span class="cx"> relocationVector[i] = replacement;
</span><del>-
- DFANode& node = dfaGraph[i];
- node.actions.clear();
- node.transitions.clear();
- node.hasFallbackTransition = false;
- node.isKilled = true;
</del><ins>+ dfa.nodes[i].kill(dfa);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- for (DFANode& node : dfaGraph) {
- for (auto& transition : node.transitions)
- transition.value = relocationVector[transition.value];
- if (node.hasFallbackTransition)
- node.fallbackTransition = relocationVector[node.fallbackTransition];
</del><ins>+ for (DFANode& node : dfa.nodes) {
+ auto nodeTransitions = node.transitions(dfa);
+ for (unsigned i = 0; i < node.transitionsLength(); ++i)
+ dfa.transitions[node.transitionsStart() + i].second = relocationVector[nodeTransitions[i].second];
+ if (node.hasFallbackTransition())
+ node.changeFallbackTransition(dfa, relocationVector[node.fallbackTransitionDestination(dfa)]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // After minimizing, there is no guarantee individual transition are still poiting to different states.
</span><span class="cx"> // The state pointed by one individual transition and the fallback states may have been merged.
</span><del>- simplifyTransitions(dfaGraph);
</del><ins>+ simplifyTransitions(dfa);
</ins><span class="cx">
</span><del>- return relocationVector[root];
</del><ins>+ dfa.root = relocationVector[dfa.root];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAMinimizerh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFAMinimizer.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -28,15 +28,14 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><del>-#include "DFANode.h"
-#include <wtf/Vector.h>
-
</del><span class="cx"> namespace WebCore {
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+struct DFA;
+
</ins><span class="cx"> class DFAMinimizer {
</span><span class="cx"> public:
</span><del>- WEBCORE_EXPORT static unsigned minimize(Vector<DFANode>& dfaGraph, unsigned rootNode);
</del><ins>+ WEBCORE_EXPORT static void minimize(DFA&);
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -36,24 +36,74 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+struct DFA;
+
</ins><span class="cx"> // A DFANode abstract the transition table out of a DFA state. If a state is accepting, the DFANode also have
</span><span class="cx"> // the actions for that state.
</span><del>-
-typedef HashMap<uint16_t, unsigned, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> DFANodeTransitions;
-
</del><span class="cx"> class DFANode {
</span><span class="cx"> public:
</span><del>- DFANodeTransitions transitions;
- bool hasFallbackTransition { false };
- bool isKilled { false };
- unsigned fallbackTransition;
- Vector<uint64_t> actions;
-
</del><ins>+ // FIXME: Stop minimizing killed nodes and add ASSERT(!isKilled()) in many functions here.
+ void kill(DFA&);
+ Vector<uint64_t> actions(const DFA&) const;
+ Vector<std::pair<uint8_t, uint32_t>> transitions(const DFA&) const;
+ uint32_t fallbackTransitionDestination(const DFA&) const;
+ void addFallbackTransition(DFA&, uint32_t destination);
+ bool containsTransition(uint8_t, DFA&);
+ void changeFallbackTransition(DFA&, uint32_t newDestination);
+
+ bool isKilled() const { return m_flags & IsKilled; }
+ bool hasFallbackTransition() const { return m_flags & HasFallbackTransition; }
+ bool hasActions() const { return !!m_actionsLength; }
+ uint8_t transitionsLength() const { return m_transitionsLength; }
+ uint16_t actionsLength() const { return m_actionsLength; }
+ uint32_t actionsStart() const { return m_actionsStart; }
+ uint32_t transitionsStart() const { return m_transitionsStart; }
+
+ void setActions(uint32_t start, uint16_t length)
+ {
+ ASSERT(!m_actionsStart);
+ ASSERT(!m_actionsLength);
+ m_actionsStart = start;
+ m_actionsLength = length;
+ }
+ void setTransitions(uint32_t start, uint16_t length)
+ {
+ ASSERT(!m_transitionsStart);
+ ASSERT(!m_transitionsLength);
+ m_transitionsStart = start;
+ m_transitionsLength = length;
+ }
+ void resetTransitions(uint32_t start, uint16_t length)
+ {
+ m_transitionsStart = start;
+ m_transitionsLength = length;
+ }
+ void setHasFallbackTransitionWithoutChangingDFA(bool shouldHaveFallbackTransition)
+ {
+ if (shouldHaveFallbackTransition)
+ m_flags |= HasFallbackTransition;
+ else
+ m_flags &= ~HasFallbackTransition;
+ }
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> Vector<unsigned> correspondingNFANodes;
</span><span class="cx"> #endif
</span><ins>+private:
+ uint32_t m_actionsStart { 0 };
+ uint32_t m_transitionsStart { 0 };
+ uint16_t m_actionsLength { 0 };
+ uint8_t m_transitionsLength { 0 };
+
+ uint8_t m_flags { 0 };
+ const uint8_t HasFallbackTransition = 0x01;
+ const uint8_t IsKilled = 0x02;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+// FIXME: Pack this down to 12.
+// It's probably already 12 on ARMv7.
+COMPILE_ASSERT(sizeof(DFANode) <= 16, Keep the DFANodes small);
+
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace WebCore
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -47,6 +47,18 @@
</span><span class="cx"> return nextId;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+size_t NFA::memoryUsed() const
+{
+ size_t size = 0;
+ for (const NFANode& node : m_nodes) {
+ size += sizeof(node)
+ + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
+ + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
+ + node.finalRuleIds.size() * sizeof(uint64_t);
+ }
+ return size;
+}
+
</ins><span class="cx"> void NFA::addTransition(unsigned from, unsigned to, char character)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(from < m_nodes.size());
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -63,6 +63,7 @@
</span><span class="cx"> #else
</span><span class="cx"> void addRuleId(unsigned, uint64_t) { }
</span><span class="cx"> #endif
</span><ins>+ size_t memoryUsed() const;
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> friend class NFAToDFA;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -214,8 +214,8 @@
</span><span class="cx"> typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;
</span><span class="cx">
</span><span class="cx"> struct NodeIdSetToUniqueNodeIdSetSource {
</span><del>- NodeIdSetToUniqueNodeIdSetSource(Vector<DFANode>& dfaGraph, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)
- : dfaGraph(dfaGraph)
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)
+ : dfa(dfa)
</ins><span class="cx"> , nfaGraph(nfaGraph)
</span><span class="cx"> , nodeIdSet(nodeIdSet)
</span><span class="cx"> {
</span><span class="lines">@@ -225,7 +225,7 @@
</span><span class="cx"> hash += nodeId;
</span><span class="cx"> this->hash = DefaultHash<unsigned>::Hash::hash(hash);
</span><span class="cx"> }
</span><del>- Vector<DFANode>& dfaGraph;
</del><ins>+ DFA& dfa;
</ins><span class="cx"> const Vector<NFANode>& nfaGraph;
</span><span class="cx"> const NodeIdSet& nodeIdSet;
</span><span class="cx"> unsigned hash;
</span><span class="lines">@@ -254,10 +254,17 @@
</span><span class="cx"> newDFANode.correspondingNFANodes.append(nfaNodeId);
</span><span class="cx"> #endif
</span><span class="cx"> }
</span><del>- copyToVector(actions, newDFANode.actions);
</del><ins>+
+ unsigned actionsStart = source.dfa.actions.size();
+ for (uint64_t action : actions)
+ source.dfa.actions.append(action);
+ unsigned actionsEnd = source.dfa.actions.size();
+ unsigned actionsLength = actionsEnd - actionsStart;
+ RELEASE_ASSERT_WITH_MESSAGE(actionsLength <= std::numeric_limits<uint16_t>::max(), "Too many actions for the current DFANode size.");
+ newDFANode.setActions(actionsStart, static_cast<uint16_t>(actionsLength));
</ins><span class="cx">
</span><del>- unsigned dfaNodeId = source.dfaGraph.size();
- source.dfaGraph.append(newDFANode);
</del><ins>+ unsigned dfaNodeId = source.dfa.nodes.size();
+ source.dfa.nodes.append(newDFANode);
</ins><span class="cx"> new (NotNull, &location) UniqueNodeIdSet(source.nodeIdSet, hash, dfaNodeId);
</span><span class="cx">
</span><span class="cx"> ASSERT(location.impl());
</span><span class="lines">@@ -328,9 +335,9 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, Vector<DFANode>& dfaGraph, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
</del><ins>+static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)
</ins><span class="cx"> {
</span><del>- NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, nfaNodeSet);
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, nfaNodeSet);
</ins><span class="cx"> auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx"> if (uniqueNodeIdAddResult.isNewEntry)
</span><span class="cx"> unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
</span><span class="lines">@@ -340,6 +347,7 @@
</span><span class="cx">
</span><span class="cx"> DFA NFAToDFA::convert(NFA& nfa)
</span><span class="cx"> {
</span><ins>+ DFA dfa;
</ins><span class="cx"> Vector<NFANode>& nfaGraph = nfa.m_nodes;
</span><span class="cx">
</span><span class="cx"> Vector<Vector<unsigned>> nfaNodeClosures;
</span><span class="lines">@@ -350,8 +358,7 @@
</span><span class="cx">
</span><span class="cx"> UniqueNodeIdSetTable uniqueNodeIdSetTable;
</span><span class="cx">
</span><del>- Vector<DFANode> dfaGraph;
- NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, initialSet);
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, initialSet);
</ins><span class="cx"> auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
</span><span class="cx">
</span><span class="cx"> Vector<UniqueNodeIdSetImpl*> unprocessedNodes;
</span><span class="lines">@@ -366,28 +373,32 @@
</span><span class="cx"> NodeIdSet setFallbackTransition;
</span><span class="cx"> populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);
</span><span class="cx">
</span><ins>+ unsigned transitionsStart = dfa.transitions.size();
</ins><span class="cx"> for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {
</span><span class="cx"> NodeIdSet& targetNodeSet = transitionsFromClosedSet[key];
</span><span class="cx">
</span><span class="cx"> if (targetNodeSet.isEmpty())
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);
- const auto addResult = dfaGraph[dfaNodeId].transitions.add(key, targetNodeId);
- ASSERT_UNUSED(addResult, addResult.isNewEntry);
</del><ins>+ unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);
+ RELEASE_ASSERT(key <= 127);
+ dfa.transitions.append(std::make_pair(static_cast<uint8_t>(key), targetNodeId));
</ins><span class="cx">
</span><span class="cx"> targetNodeSet.clear();
</span><span class="cx"> }
</span><ins>+ unsigned transitionsEnd = dfa.transitions.size();
+ unsigned transitionsLength = transitionsEnd - transitionsStart;
+ RELEASE_ASSERT(transitionsLength <= 127);
+ dfa.nodes[dfaNodeId].setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
+
</ins><span class="cx"> if (!setFallbackTransition.isEmpty()) {
</span><del>- unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);
- DFANode& dfaSourceNode = dfaGraph[dfaNodeId];
- ASSERT(!dfaSourceNode.hasFallbackTransition);
- dfaSourceNode.hasFallbackTransition = true;
- dfaSourceNode.fallbackTransition = targetNodeId;
</del><ins>+ unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);
+ DFANode& dfaSourceNode = dfa.nodes[dfaNodeId];
+ dfaSourceNode.addFallbackTransition(dfa, targetNodeId);
</ins><span class="cx"> }
</span><span class="cx"> } while (!unprocessedNodes.isEmpty());
</span><span class="cx">
</span><del>- return DFA(WTF::move(dfaGraph), 0);
</del><ins>+ return dfa;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Tools/ChangeLog 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -1,3 +1,15 @@
</span><ins>+2015-04-23 Alex Christensen <achristensen@webkit.org>
+
+ Use less memory when compiling content extensions.
+ https://bugs.webkit.org/show_bug.cgi?id=144051
+
+ Reviewed by Darin Adler and Benjamin Poulain.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::TEST_F):
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+ (TestWebKitAPI::countLiveNodes):
+
</ins><span class="cx"> 2015-04-22 Michael Catanzaro <mcatanzaro@igalia.com>
</span><span class="cx">
</span><span class="cx"> [CMake] Clean up JSC JIT options
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -487,6 +487,7 @@
</span><span class="cx"> TEST_F(ContentExtensionTest, MultiDFA)
</span><span class="cx"> {
</span><span class="cx"> // Make an NFA with about 1400 nodes.
</span><ins>+ // FIXME: This does not make multiple DFAs anymore. Add a test that does.
</ins><span class="cx"> StringBuilder ruleList;
</span><span class="cx"> ruleList.append('[');
</span><span class="cx"> for (char c1 = 'A'; c1 <= 'Z'; ++c1) {
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (183203 => 183204)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-04-23 19:45:00 UTC (rev 183203)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-04-23 19:56:57 UTC (rev 183204)
</span><span class="lines">@@ -46,8 +46,8 @@
</span><span class="cx"> unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
</span><span class="cx"> {
</span><span class="cx"> unsigned counter = 0;
</span><del>- for (unsigned i = 0; i < dfa.size(); ++i) {
- if (!dfa.nodeAt(i).isKilled)
</del><ins>+ for (const auto& node : dfa.nodes) {
+ if (!node.isKilled())
</ins><span class="cx"> ++counter;
</span><span class="cx"> }
</span><span class="cx"> return counter;
</span></span></pre>
</div>
</div>
</body>
</html>