<!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>[178436] 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/178436">178436</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-01-14 12:32:39 -0800 (Wed, 14 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Do not create new set for every sub-operation when converting a NFA to DFA
https://bugs.webkit.org/show_bug.cgi?id=140380
Reviewed by Andreas Kling.
This is the first step toward making the NFA-to-DFA conversion more scalable: instead
of creating new sets for each step of the algorithm, we use two kinds of sets
and never do any copy.
The first new tool to do that is UniqueNodeIdSetImpl. It represents a set of NFA state corresponding to a DFA
state. It is unique per DFA state.
HashableNodeIdSet is a helper tool storing a UniqueNodeIdSetImpl.
The creation of new sets now goes like this:
1) Get a NodeIdSet for each possible transition.
2) For each transition:
2a) Extend the NodeIdSet in place with its epsilon closure.
2b) Get the UniqueNodeIdSetImpl corresponding to the new set we discovered.
2c) If the UniqueNodeIdSetImpl is new, queue it for processing.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/ContentExtensionsDebugging.h: Copied from Source/WebCore/contentextensions/DFANode.h.
* contentextensions/ContentExtensionsBackend.cpp:
(WebCore::ContentExtensions::ContentExtensionsBackend::setRuleList):
* contentextensions/ContentExtensionsManager.cpp:
(WebCore::ContentExtensions::ExtensionsManager::loadExtension):
Added some logging to inspect more easily what the clients are sending.
* contentextensions/DFA.cpp:
* contentextensions/DFA.h:
* contentextensions/DFANode.h:
* contentextensions/NFA.cpp:
* contentextensions/NFA.h:
* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::epsilonClosure):
Instead of returning a new HashSet, extend the input HashSet.
(WebCore::ContentExtensions::UniqueNodeIdSetImpl::buffer):
(WebCore::ContentExtensions::UniqueNodeIdSet::UniqueNodeIdSet):
(WebCore::ContentExtensions::UniqueNodeIdSet::operator=):
(WebCore::ContentExtensions::UniqueNodeIdSet::~UniqueNodeIdSet):
(WebCore::ContentExtensions::UniqueNodeIdSet::operator==):
(WebCore::ContentExtensions::UniqueNodeIdSet::impl):
(WebCore::ContentExtensions::UniqueNodeIdSet::hash):
(WebCore::ContentExtensions::UniqueNodeIdSet::isEmptyValue):
(WebCore::ContentExtensions::UniqueNodeIdSet::isDeletedValue):
(WebCore::ContentExtensions::UniqueNodeIdSetHash::hash):
(WebCore::ContentExtensions::UniqueNodeIdSetHash::equal):
UniqueNodeIdSetImpl is a compact representation of a NodeIdSet corresponding to a DFA node.
It is never built directly, it is only built on demand through NodeIdSetToUniqueNodeIdSetTranslator
from a NodeIdSet.
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::hash):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::equal):
(WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
(WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::operator[]):
(WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::size):
(WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::begin):
(WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::end):
(WebCore::ContentExtensions::populateTransitionsExcludingEpsilon):
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::setTransitionsExcludingEpsilon): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSet::HashableNodeIdSet): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSet::operator=): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSet::isEmptyValue): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSet::isDeletedValue): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSet::nodeIdSet): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSetHash::hash): Deleted.
(WebCore::ContentExtensions::HashableNodeIdSetHash::equal): Deleted.
(WebCore::ContentExtensions::addDFAState): Deleted.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreWebCorexcodeprojprojectpbxproj">trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp">trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsManagercpp">trunk/Source/WebCore/contentextensions/ContentExtensionsManager.cpp</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="#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>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsDebuggingh">trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/ChangeLog 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -1,3 +1,80 @@
</span><ins>+2015-01-14 Benjamin Poulain <benjamin@webkit.org>
+
+ Do not create new set for every sub-operation when converting a NFA to DFA
+ https://bugs.webkit.org/show_bug.cgi?id=140380
+
+ Reviewed by Andreas Kling.
+
+ This is the first step toward making the NFA-to-DFA conversion more scalable: instead
+ of creating new sets for each step of the algorithm, we use two kinds of sets
+ and never do any copy.
+
+ The first new tool to do that is UniqueNodeIdSetImpl. It represents a set of NFA state corresponding to a DFA
+ state. It is unique per DFA state.
+
+ HashableNodeIdSet is a helper tool storing a UniqueNodeIdSetImpl.
+
+ The creation of new sets now goes like this:
+ 1) Get a NodeIdSet for each possible transition.
+ 2) For each transition:
+ 2a) Extend the NodeIdSet in place with its epsilon closure.
+ 2b) Get the UniqueNodeIdSetImpl corresponding to the new set we discovered.
+ 2c) If the UniqueNodeIdSetImpl is new, queue it for processing.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/ContentExtensionsDebugging.h: Copied from Source/WebCore/contentextensions/DFANode.h.
+ * contentextensions/ContentExtensionsBackend.cpp:
+ (WebCore::ContentExtensions::ContentExtensionsBackend::setRuleList):
+ * contentextensions/ContentExtensionsManager.cpp:
+ (WebCore::ContentExtensions::ExtensionsManager::loadExtension):
+ Added some logging to inspect more easily what the clients are sending.
+
+ * contentextensions/DFA.cpp:
+ * contentextensions/DFA.h:
+ * contentextensions/DFANode.h:
+ * contentextensions/NFA.cpp:
+ * contentextensions/NFA.h:
+ * contentextensions/NFAToDFA.cpp:
+
+ (WebCore::ContentExtensions::epsilonClosure):
+ Instead of returning a new HashSet, extend the input HashSet.
+
+ (WebCore::ContentExtensions::UniqueNodeIdSetImpl::buffer):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::UniqueNodeIdSet):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::operator=):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::~UniqueNodeIdSet):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::operator==):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::impl):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::hash):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::isEmptyValue):
+ (WebCore::ContentExtensions::UniqueNodeIdSet::isDeletedValue):
+ (WebCore::ContentExtensions::UniqueNodeIdSetHash::hash):
+ (WebCore::ContentExtensions::UniqueNodeIdSetHash::equal):
+ UniqueNodeIdSetImpl is a compact representation of a NodeIdSet corresponding to a DFA node.
+
+ It is never built directly, it is only built on demand through NodeIdSetToUniqueNodeIdSetTranslator
+ from a NodeIdSet.
+
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::hash):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::equal):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
+ (WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::operator[]):
+ (WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::size):
+ (WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::begin):
+ (WebCore::ContentExtensions::SetTransitionsExcludingEpsilon::end):
+ (WebCore::ContentExtensions::populateTransitionsExcludingEpsilon):
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ (WebCore::ContentExtensions::setTransitionsExcludingEpsilon): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSet::HashableNodeIdSet): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSet::operator=): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSet::isEmptyValue): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSet::isDeletedValue): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSet::nodeIdSet): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSetHash::hash): Deleted.
+ (WebCore::ContentExtensions::HashableNodeIdSetHash::equal): Deleted.
+ (WebCore::ContentExtensions::addDFAState): Deleted.
+
</ins><span class="cx"> 2015-01-14 Chris Dumez <cdumez@apple.com>
</span><span class="cx">
</span><span class="cx"> Make 'TypeName' parameter unnecessary in CSSPropertyNames.in
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -1014,6 +1014,7 @@
</span><span class="cx"> 24F54EAD101FE914000AE741 /* ApplicationCacheHost.h in Headers */ = {isa = PBXBuildFile; fileRef = 24F54EAB101FE914000AE741 /* ApplicationCacheHost.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 2542F4DA1166C25A00E89A86 /* UserGestureIndicator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2542F4D81166C25A00E89A86 /* UserGestureIndicator.cpp */; };
</span><span class="cx"> 2542F4DB1166C25A00E89A86 /* UserGestureIndicator.h in Headers */ = {isa = PBXBuildFile; fileRef = 2542F4D91166C25A00E89A86 /* UserGestureIndicator.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><ins>+ 262391361A648CEE007251A3 /* ContentExtensionsDebugging.h in Headers */ = {isa = PBXBuildFile; fileRef = 262391351A648CEE007251A3 /* ContentExtensionsDebugging.h */; };
</ins><span class="cx"> 26255F0018878DFF0006E1FD /* UserAgentIOS.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26255EFF18878DFF0006E1FD /* UserAgentIOS.mm */; };
</span><span class="cx"> 26255F0318878E110006E1FD /* UserAgent.h in Headers */ = {isa = PBXBuildFile; fileRef = 26255F0118878E110006E1FD /* UserAgent.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 26255F0418878E110006E1FD /* UserAgentMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26255F0218878E110006E1FD /* UserAgentMac.mm */; };
</span><span class="lines">@@ -8010,6 +8011,7 @@
</span><span class="cx"> 2527CC9516BF95DD009DDAC0 /* PlatformSpeechSynthesisUtterance.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PlatformSpeechSynthesisUtterance.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2542F4D81166C25A00E89A86 /* UserGestureIndicator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = UserGestureIndicator.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2542F4D91166C25A00E89A86 /* UserGestureIndicator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UserGestureIndicator.h; sourceTree = "<group>"; };
</span><ins>+ 262391351A648CEE007251A3 /* ContentExtensionsDebugging.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContentExtensionsDebugging.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26255EFF18878DFF0006E1FD /* UserAgentIOS.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = UserAgentIOS.mm; sourceTree = "<group>"; };
</span><span class="cx"> 26255F0118878E110006E1FD /* UserAgent.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UserAgent.h; sourceTree = "<group>"; };
</span><span class="cx"> 26255F0218878E110006E1FD /* UserAgentMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = UserAgentMac.mm; sourceTree = "<group>"; };
</span><span class="lines">@@ -15319,6 +15321,7 @@
</span><span class="cx"> 26F0C89A1A2EC110002794F8 /* ContentExtensionRule.h */,
</span><span class="cx"> 26F0C89D1A2EC3BE002794F8 /* ContentExtensionsBackend.cpp */,
</span><span class="cx"> 26F0C89E1A2EC3BE002794F8 /* ContentExtensionsBackend.h */,
</span><ins>+ 262391351A648CEE007251A3 /* ContentExtensionsDebugging.h */,
</ins><span class="cx"> 26F0C8931A2D7A76002794F8 /* ContentExtensionsInterface.cpp */,
</span><span class="cx"> 26F0C8911A2D79CB002794F8 /* ContentExtensionsInterface.h */,
</span><span class="cx"> 26F0C8951A2E724B002794F8 /* ContentExtensionsManager.cpp */,
</span><span class="lines">@@ -26155,6 +26158,7 @@
</span><span class="cx"> 08250939128BD4D800E2ED8E /* SVGAnimatedTransformList.h in Headers */,
</span><span class="cx"> 085A15931289A8DD002710E3 /* SVGAnimatedTransformListPropertyTearOff.h in Headers */,
</span><span class="cx"> 439D334313A6911C00C20F4F /* SVGAnimatedType.h in Headers */,
</span><ins>+ 262391361A648CEE007251A3 /* ContentExtensionsDebugging.h in Headers */,
</ins><span class="cx"> 439D334413A6911C00C20F4F /* SVGAnimatedTypeAnimator.h in Headers */,
</span><span class="cx"> B22279900D00BF220071B782 /* SVGAnimateElement.h in Headers */,
</span><span class="cx"> 832B843419D8E55100B26055 /* SVGAnimateElementBase.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -28,10 +28,12 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include "NFA.h"
</span><span class="cx"> #include "NFAToDFA.h"
</span><span class="cx"> #include "URL.h"
</span><span class="cx"> #include "URLFilterParser.h"
</span><ins>+#include <wtf/CurrentTime.h>
</ins><span class="cx"> #include <wtf/DataLog.h>
</span><span class="cx"> #include <wtf/NeverDestroyed.h>
</span><span class="cx"> #include <wtf/text/CString.h>
</span><span class="lines">@@ -57,6 +59,10 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double nfaBuildTimeStart = monotonicallyIncreasingTime();
+#endif
+
</ins><span class="cx"> NFA nfa;
</span><span class="cx"> for (unsigned ruleIndex = 0; ruleIndex < ruleList.size(); ++ruleIndex) {
</span><span class="cx"> const ContentExtensionRule& contentExtensionRule = ruleList[ruleIndex];
</span><span class="lines">@@ -72,8 +78,32 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double nfaBuildTimeEnd = monotonicallyIncreasingTime();
+ dataLogF(" Time spent building the NFA: %f\n", (nfaBuildTimeEnd - nfaBuildTimeStart));
+#endif
+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ nfa.debugPrintDot();
+#endif
+
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaBuildTimeStart = monotonicallyIncreasingTime();
+#endif
+
+ CompiledContentExtension compiledContentExtension = { NFAToDFA::convert(nfa), ruleList };
+
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double dfaBuildTimeEnd = monotonicallyIncreasingTime();
+ dataLogF(" Time spent building the DFA: %f\n", (dfaBuildTimeEnd - dfaBuildTimeStart));
+#endif
+
</ins><span class="cx"> // FIXME: never add a DFA that only matches the empty set.
</span><del>- CompiledContentExtension compiledContentExtension = { NFAToDFA::convert(nfa), ruleList };
</del><ins>+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ compiledContentExtension.dfa.debugPrintDot();
+#endif
+
</ins><span class="cx"> m_ruleLists.set(identifier, compiledContentExtension);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsDebuggingh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h (0 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -0,0 +1,37 @@
</span><ins>+/*
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ContentExtensionsDebugging_h
+#define ContentExtensionsDebugging_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#define CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING 0
+
+#define CONTENT_EXTENSIONS_PERFORMANCE_REPORTING 0
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // ContentExtensionsDebugging_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsManagercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsManager.cpp (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsManager.cpp 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsManager.cpp 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -30,12 +30,14 @@
</span><span class="cx">
</span><span class="cx"> #include "ContentExtensionRule.h"
</span><span class="cx"> #include "ContentExtensionsBackend.h"
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include <JavaScriptCore/IdentifierInlines.h>
</span><span class="cx"> #include <JavaScriptCore/JSCJSValueInlines.h>
</span><span class="cx"> #include <JavaScriptCore/JSGlobalObject.h>
</span><span class="cx"> #include <JavaScriptCore/JSONObject.h>
</span><span class="cx"> #include <JavaScriptCore/StructureInlines.h>
</span><span class="cx"> #include <JavaScriptCore/VM.h>
</span><ins>+#include <wtf/CurrentTime.h>
</ins><span class="cx"> #include <wtf/text/WTFString.h>
</span><span class="cx">
</span><span class="cx"> using namespace JSC;
</span><span class="lines">@@ -154,6 +156,9 @@
</span><span class="cx">
</span><span class="cx"> void loadExtension(const String& identifier, const String& rules)
</span><span class="cx"> {
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double loadExtensionStartTime = monotonicallyIncreasingTime();
+#endif
</ins><span class="cx"> RefPtr<VM> vm = VM::create();
</span><span class="cx">
</span><span class="cx"> JSLockHolder locker(vm.get());
</span><span class="lines">@@ -169,6 +174,11 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ double loadExtensionEndTime = monotonicallyIncreasingTime();
+ dataLogF("Time spent loading extension %s: %f\n", identifier.utf8().data(), (loadExtensionEndTime - loadExtensionStartTime));
+#endif
+
</ins><span class="cx"> ContentExtensionsBackend::sharedInstance().setRuleList(identifier, ruleList);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -79,7 +79,7 @@
</span><span class="cx"> return m_nodes[currentState].actions;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-#ifndef NDEBUG
</del><ins>+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</ins><span class="cx"> static void printRange(bool firstRange, char rangeStart, char rangeEnd)
</span><span class="cx"> {
</span><span class="cx"> if (!firstRange)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include "DFANode.h"
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="lines">@@ -50,7 +51,7 @@
</span><span class="cx"> unsigned nextState(unsigned currentState, char character, bool& ok) const;
</span><span class="cx"> const Vector<uint64_t>& actions(unsigned currentState) const;
</span><span class="cx">
</span><del>-#ifndef NDEBUG
</del><ins>+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</ins><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #endif
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFANode.h (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/DFANode.h 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="lines">@@ -42,7 +43,7 @@
</span><span class="cx"> HashMap<uint16_t, unsigned> transitions;
</span><span class="cx"> Vector<uint64_t> actions;
</span><span class="cx">
</span><del>-#ifndef NDEBUG
</del><ins>+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</ins><span class="cx"> Vector<unsigned> correspondingDFANodes;
</span><span class="cx"> #endif
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -85,7 +85,7 @@
</span><span class="cx"> m_nodes.shrink(size);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-#ifndef NDEBUG
</del><ins>+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</ins><span class="cx">
</span><span class="cx"> static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include "NFANode.h"
</span><span class="cx"> #include <limits>
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="lines">@@ -53,7 +54,7 @@
</span><span class="cx"> unsigned graphSize() const;
</span><span class="cx"> void restoreToGraphSize(unsigned);
</span><span class="cx">
</span><del>-#ifndef NDEBUG
</del><ins>+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</ins><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #endif
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (178435 => 178436)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-14 20:16:23 UTC (rev 178435)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-01-14 20:32:39 UTC (rev 178436)
</span><span class="lines">@@ -28,8 +28,10 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "ContentExtensionsDebugging.h"
</ins><span class="cx"> #include "DFANode.h"
</span><span class="cx"> #include "NFA.h"
</span><ins>+#include <wtf/DataLog.h>
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx">
</span><span class="lines">@@ -37,209 +39,296 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><ins>+// FIXME: set a better initial size.
+// FIXME: include the hash inside NodeIdSet.
</ins><span class="cx"> typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> NodeIdSet;
</span><span class="cx">
</span><del>-static NodeIdSet epsilonClosure(const NodeIdSet& nodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
</del><ins>+static inline void epsilonClosure(NodeIdSet& nodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(!nodeSet.isEmpty());
</span><span class="cx"> ASSERT(!graph.isEmpty());
</span><span class="cx">
</span><del>- // We go breadth-first first into our graph following all the epsilon transition. At each generation,
- // discoveredNodes contains all the new nodes we have discovered by following a single epsilon transition
- // out of the previous set of nodes.
- NodeIdSet outputNodeSet = nodeSet;
- NodeIdSet discoveredNodes = nodeSet;
</del><ins>+ // FIXME: fine a good inline size for unprocessedNodes.
+ Vector<unsigned> unprocessedNodes;
+ copyToVector(nodeSet, unprocessedNodes);
+
</ins><span class="cx"> do {
</span><del>- outputNodeSet.add(discoveredNodes.begin(), discoveredNodes.end());
-
- NodeIdSet nextGenerationDiscoveredNodes;
-
- for (unsigned nodeId : discoveredNodes) {
- const NFANode& node = graph[nodeId];
- auto epsilonTransitionSlot = node.transitions.find(epsilonTransitionCharacter);
- if (epsilonTransitionSlot != node.transitions.end()) {
- const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>& targets = epsilonTransitionSlot->value;
- for (unsigned targetNodeId : targets) {
- if (!outputNodeSet.contains(targetNodeId))
- nextGenerationDiscoveredNodes.add(targetNodeId);
- }
</del><ins>+ unsigned unprocessedNodeId = unprocessedNodes.takeLast();
+ const NFANode& node = graph[unprocessedNodeId];
+ auto epsilonTransitionSlot = node.transitions.find(epsilonTransitionCharacter);
+ if (epsilonTransitionSlot != node.transitions.end()) {
+ for (unsigned targetNodeId : epsilonTransitionSlot->value) {
+ auto addResult = nodeSet.add(targetNodeId);
+ if (addResult.isNewEntry)
+ unprocessedNodes.append(targetNodeId);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>-
- discoveredNodes = nextGenerationDiscoveredNodes;
- } while (!discoveredNodes.isEmpty());
-
- ASSERT(!outputNodeSet.isEmpty());
- return outputNodeSet;
</del><ins>+ } while (!unprocessedNodes.isEmpty());
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-typedef HashMap<uint16_t, NodeIdSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> SetTransitionsExcludingEpsilon;
</del><ins>+struct UniqueNodeIdSetImpl {
+ unsigned* buffer()
+ {
+ return m_buffer;
+ }
</ins><span class="cx">
</span><del>-static SetTransitionsExcludingEpsilon setTransitionsExcludingEpsilon(const NodeIdSet& nodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
-{
- ASSERT(!nodeSet.isEmpty());
- ASSERT(!graph.isEmpty());
-
- SetTransitionsExcludingEpsilon outputSetTransitionsExcludingEpsilon;
-
- for (unsigned nodeId : nodeSet) {
- const NFANode& node = graph[nodeId];
- for (const auto& transitionSlot : node.transitions) {
- if (transitionSlot.key != epsilonTransitionCharacter) {
- auto existingTransition = outputSetTransitionsExcludingEpsilon.find(transitionSlot.key);
- if (existingTransition != outputSetTransitionsExcludingEpsilon.end())
- existingTransition->value.add(transitionSlot.value.begin(), transitionSlot.value.end());
- else {
- NodeIdSet newSet;
- newSet.add(transitionSlot.value.begin(), transitionSlot.value.end());
- outputSetTransitionsExcludingEpsilon.add(transitionSlot.key, newSet);
- }
- }
- }
</del><ins>+ const unsigned* buffer() const
+ {
+ return m_buffer;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- return outputSetTransitionsExcludingEpsilon;
-}
</del><ins>+ unsigned m_size;
+ unsigned m_hash;
+ unsigned m_dfaNodeId;
+private:
+ unsigned m_buffer[1];
+};
</ins><span class="cx">
</span><del>-class HashableNodeIdSet {
</del><ins>+class UniqueNodeIdSet {
</ins><span class="cx"> public:
</span><ins>+ UniqueNodeIdSet() { }
</ins><span class="cx"> enum EmptyValueTag { EmptyValue };
</span><span class="cx"> enum DeletedValueTag { DeletedValue };
</span><span class="cx">
</span><del>- HashableNodeIdSet(EmptyValueTag) { }
- HashableNodeIdSet(DeletedValueTag)
- : m_isDeleted(true)
</del><ins>+ UniqueNodeIdSet(EmptyValueTag) { }
+ UniqueNodeIdSet(DeletedValueTag)
+ : m_uniqueNodeIdSetBuffer(reinterpret_cast_ptr<UniqueNodeIdSetImpl*>(-1))
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- HashableNodeIdSet(const NodeIdSet& nodeIdSet)
- : m_nodeIdSet(nodeIdSet)
</del><ins>+ UniqueNodeIdSet(const NodeIdSet& nodeIdSet, unsigned hash, unsigned dfaNodeId)
</ins><span class="cx"> {
</span><del>- ASSERT(!nodeIdSet.isEmpty());
</del><ins>+ ASSERT(nodeIdSet.size());
+
+ unsigned size = nodeIdSet.size();
+ size_t byteSize = sizeof(UniqueNodeIdSetImpl) + (size - 1) * sizeof(unsigned);
+ m_uniqueNodeIdSetBuffer = static_cast<UniqueNodeIdSetImpl*>(fastMalloc(byteSize));
+
+ m_uniqueNodeIdSetBuffer->m_size = size;
+ m_uniqueNodeIdSetBuffer->m_hash = hash;
+ m_uniqueNodeIdSetBuffer->m_dfaNodeId = dfaNodeId;
+
+ unsigned* buffer = m_uniqueNodeIdSetBuffer->buffer();
+ for (unsigned nodeId : nodeIdSet) {
+ *buffer = nodeId;
+ ++buffer;
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- HashableNodeIdSet(HashableNodeIdSet&& other)
- : m_nodeIdSet(other.m_nodeIdSet)
- , m_isDeleted(other.m_isDeleted)
</del><ins>+ UniqueNodeIdSet(UniqueNodeIdSet&& other)
+ : m_uniqueNodeIdSetBuffer(other.m_uniqueNodeIdSetBuffer)
</ins><span class="cx"> {
</span><del>- other.m_nodeIdSet.clear();
- other.m_isDeleted = false;
</del><ins>+ other.m_uniqueNodeIdSetBuffer = nullptr;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- HashableNodeIdSet& operator=(HashableNodeIdSet&& other)
</del><ins>+ UniqueNodeIdSet& operator=(UniqueNodeIdSet&& other)
</ins><span class="cx"> {
</span><del>- m_nodeIdSet = other.m_nodeIdSet;
- other.m_nodeIdSet.clear();
- m_isDeleted = other.m_isDeleted;
- other.m_isDeleted = false;
</del><ins>+ m_uniqueNodeIdSetBuffer = other.m_uniqueNodeIdSetBuffer;
+ other.m_uniqueNodeIdSetBuffer = nullptr;
</ins><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool isEmptyValue() const { return m_nodeIdSet.isEmpty(); }
- bool isDeletedValue() const { return m_isDeleted; }
</del><ins>+ ~UniqueNodeIdSet()
+ {
+ fastFree(m_uniqueNodeIdSetBuffer);
+ }
</ins><span class="cx">
</span><del>- NodeIdSet nodeIdSet() const { return m_nodeIdSet; }
</del><ins>+ bool operator==(const UniqueNodeIdSet& other) const
+ {
+ return m_uniqueNodeIdSetBuffer == other.m_uniqueNodeIdSetBuffer;
+ }
</ins><span class="cx">
</span><ins>+ bool operator==(const NodeIdSet& other) const
+ {
+ if (m_uniqueNodeIdSetBuffer->m_size != static_cast<unsigned>(other.size()))
+ return false;
+ unsigned* buffer = m_uniqueNodeIdSetBuffer->buffer();
+ for (unsigned i = 0; i < m_uniqueNodeIdSetBuffer->m_size; ++i) {
+ if (!other.contains(buffer[i]))
+ return false;
+ }
+ return true;
+ }
+
+ UniqueNodeIdSetImpl* impl() const { return m_uniqueNodeIdSetBuffer; }
+
+ unsigned hash() const { return m_uniqueNodeIdSetBuffer->m_hash; }
+ bool isEmptyValue() const { return !m_uniqueNodeIdSetBuffer; }
+ bool isDeletedValue() const { return m_uniqueNodeIdSetBuffer == reinterpret_cast_ptr<UniqueNodeIdSetImpl*>(-1); }
+
</ins><span class="cx"> private:
</span><del>- NodeIdSet m_nodeIdSet;
- bool m_isDeleted = false;
</del><ins>+ UniqueNodeIdSetImpl* m_uniqueNodeIdSetBuffer = nullptr;
</ins><span class="cx"> };
</span><span class="cx">
</span><del>-struct HashableNodeIdSetHash {
- static unsigned hash(const HashableNodeIdSet& p)
</del><ins>+struct UniqueNodeIdSetHash {
+ static unsigned hash(const UniqueNodeIdSet& p)
</ins><span class="cx"> {
</span><del>- unsigned hash = 4207445155;
- for (unsigned nodeId : p.nodeIdSet())
- hash += DefaultHash<unsigned>::Hash::hash(nodeId);
- return hash;
</del><ins>+ return p.hash();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- static bool equal(const HashableNodeIdSet& a, const HashableNodeIdSet& b)
</del><ins>+ static bool equal(const UniqueNodeIdSet& a, const UniqueNodeIdSet& b)
</ins><span class="cx"> {
</span><del>- return a.nodeIdSet() == b.nodeIdSet() && a.isDeletedValue() == b.isDeletedValue();
</del><ins>+ return a == b;
</ins><span class="cx"> }
</span><del>- static const bool safeToCompareToEmptyOrDeleted = true;
</del><ins>+ // It would be fine to compare empty or deleted here, but not for the HashTranslator.
+ static const bool safeToCompareToEmptyOrDeleted = false;
</ins><span class="cx"> };
</span><span class="cx">
</span><del>-struct HashableNodeIdSetHashTraits : public WTF::CustomHashTraits<HashableNodeIdSet> { };
</del><ins>+struct UniqueNodeIdSetHashHashTraits : public WTF::CustomHashTraits<UniqueNodeIdSet> {
+ static const bool emptyValueIsZero = true;
</ins><span class="cx">
</span><del>-typedef HashMap<HashableNodeIdSet, unsigned, HashableNodeIdSetHash, HashableNodeIdSetHashTraits> NFAToDFANodeMap;
</del><ins>+ // FIXME: Get a good size.
+ static const int minimumTableSize = 128;
+};
</ins><span class="cx">
</span><del>-static unsigned addDFAState(Vector<DFANode>& dfaGraph, NFAToDFANodeMap& nfaToDFANodeMap, const Vector<NFANode>& nfaGraph, NodeIdSet nfaNodes, unsigned epsilonTransitionCharacter)
-{
- ASSERT(!nfaToDFANodeMap.contains(nfaNodes));
- ASSERT_UNUSED(epsilonTransitionCharacter, epsilonClosure(nfaNodes, nfaGraph, epsilonTransitionCharacter) == nfaNodes);
</del><ins>+typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;
</ins><span class="cx">
</span><del>- DFANode newDFANode;
</del><ins>+struct NodeIdSetToUniqueNodeIdSetSource {
+ NodeIdSetToUniqueNodeIdSetSource(Vector<DFANode>& dfaGraph, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)
+ : dfaGraph(dfaGraph)
+ , nfaGraph(nfaGraph)
+ , nodeIdSet(nodeIdSet)
+ {
+ // The hashing operation must be independant of the nodeId.
+ unsigned hash = 4207445155;
+ for (unsigned nodeId : nodeIdSet)
+ hash += nodeId;
+ this->hash = DefaultHash<unsigned>::Hash::hash(hash);
+ }
+ Vector<DFANode>& dfaGraph;
+ const Vector<NFANode>& nfaGraph;
+ const NodeIdSet& nodeIdSet;
+ unsigned hash;
+};
</ins><span class="cx">
</span><del>- HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
- for (unsigned nfaNodeId : nfaNodes) {
- const NFANode& nfaNode = nfaGraph[nfaNodeId];
- if (nfaNode.isFinal)
- actions.add(nfaNode.ruleId);
-#ifndef NDEBUG
- newDFANode.correspondingDFANodes.append(nfaNodeId);
</del><ins>+struct NodeIdSetToUniqueNodeIdSetTranslator {
+ static unsigned hash(const NodeIdSetToUniqueNodeIdSetSource& source)
+ {
+ return source.hash;
+ }
+
+ static inline bool equal(const UniqueNodeIdSet& a, const NodeIdSetToUniqueNodeIdSetSource& b)
+ {
+ return a == b.nodeIdSet;
+ }
+
+ static void translate(UniqueNodeIdSet& location, const NodeIdSetToUniqueNodeIdSetSource& source, unsigned hash)
+ {
+ DFANode newDFANode;
+
+ HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
+ for (unsigned nfaNodeId : source.nodeIdSet) {
+ const NFANode& nfaNode = source.nfaGraph[nfaNodeId];
+ if (nfaNode.isFinal)
+ actions.add(nfaNode.ruleId);
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ newDFANode.correspondingDFANodes.append(nfaNodeId);
</ins><span class="cx"> #endif
</span><ins>+ }
+ copyToVector(actions, newDFANode.actions);
+
+ unsigned dfaNodeId = source.dfaGraph.size();
+ source.dfaGraph.append(newDFANode);
+ new (NotNull, &location) UniqueNodeIdSet(source.nodeIdSet, hash, dfaNodeId);
+
+ ASSERT(location.impl());
</ins><span class="cx"> }
</span><ins>+};
</ins><span class="cx">
</span><del>- for (uint64_t action : actions)
- newDFANode.actions.append(action);
</del><ins>+class SetTransitionsExcludingEpsilon {
+public:
+ NodeIdSet& operator[](unsigned index)
+ {
+ ASSERT(index < size());
+ return m_targets[index];
+ }
</ins><span class="cx">
</span><del>- unsigned dfaNodeId = dfaGraph.size();
- dfaGraph.append(newDFANode);
- nfaToDFANodeMap.add(nfaNodes, dfaNodeId);
- return dfaNodeId;
</del><ins>+ unsigned size() const
+ {
+ return WTF_ARRAY_LENGTH(m_targets);
+ }
+
+ NodeIdSet* begin()
+ {
+ return m_targets;
+ }
+
+ NodeIdSet* end()
+ {
+ return m_targets + size();
+ }
+
+private:
+ NodeIdSet m_targets[128];
+};
+
+static inline void populateTransitionsExcludingEpsilon(SetTransitionsExcludingEpsilon& setTransitionsExcludingEpsilon, const UniqueNodeIdSetImpl& sourceNodeSet, const Vector<NFANode>& graph, unsigned epsilonTransitionCharacter)
+{
+ ASSERT(!graph.isEmpty());
+#if !ASSERT_DISABLED
+ for (const NodeIdSet& set : setTransitionsExcludingEpsilon)
+ ASSERT(set.isEmpty());
+#endif
+
+ const unsigned* buffer = sourceNodeSet.buffer();
+ for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
+ unsigned nodeId = buffer[i];
+ 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());
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-typedef HashSet<HashableNodeIdSet, HashableNodeIdSetHash, HashableNodeIdSetHashTraits> SetOfNodeSet;
-
</del><span class="cx"> DFA NFAToDFA::convert(const NFA& nfa)
</span><span class="cx"> {
</span><span class="cx"> Vector<DFANode> dfaGraph;
</span><del>- NFAToDFANodeMap nfaToDFANodeMap;
</del><span class="cx">
</span><del>- SetOfNodeSet processedStateSets;
- SetOfNodeSet unprocessedStateSets;
-
</del><span class="cx"> const Vector<NFANode>& nfaGraph = nfa.m_nodes;
</span><span class="cx">
</span><span class="cx"> NodeIdSet initialSet({ nfa.root() });
</span><del>- NodeIdSet closedInitialSet = epsilonClosure(initialSet, nfaGraph, NFA::epsilonTransitionCharacter);
</del><ins>+ epsilonClosure(initialSet, nfaGraph, NFA::epsilonTransitionCharacter);
</ins><span class="cx">
</span><del>- addDFAState(dfaGraph, nfaToDFANodeMap, nfaGraph, closedInitialSet, NFA::epsilonTransitionCharacter);
- unprocessedStateSets.add(closedInitialSet);
</del><ins>+ UniqueNodeIdSetTable uniqueNodeIdSetTable;
</ins><span class="cx">
</span><ins>+ NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, initialSet);
+ auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
+
+ Vector<UniqueNodeIdSetImpl*> unprocessedNodes;
+ unprocessedNodes.append(addResult.iterator->impl());
+
+ SetTransitionsExcludingEpsilon transitionsFromClosedSet;
+
</ins><span class="cx"> do {
</span><del>- HashableNodeIdSet stateSet = unprocessedStateSets.takeAny();
</del><ins>+ UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
</ins><span class="cx">
</span><del>- ASSERT(!processedStateSets.contains(stateSet.nodeIdSet()));
- processedStateSets.add(stateSet.nodeIdSet());
</del><ins>+ unsigned dfaNodeId = uniqueNodeIdSetImpl->m_dfaNodeId;
+ populateTransitionsExcludingEpsilon(transitionsFromClosedSet, *uniqueNodeIdSetImpl, nfaGraph, NFA::epsilonTransitionCharacter);
</ins><span class="cx">
</span><del>- unsigned dfaNodeId = nfaToDFANodeMap.get(stateSet);
</del><ins>+ // FIXME: there should not be any transition on key 0.
+ for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {
+ NodeIdSet& targetNodeSet = transitionsFromClosedSet[key];
</ins><span class="cx">
</span><del>- SetTransitionsExcludingEpsilon transitionsFromClosedSet = setTransitionsExcludingEpsilon(stateSet.nodeIdSet(), nfaGraph, NFA::epsilonTransitionCharacter);
- for (const auto& transitionSlot : transitionsFromClosedSet) {
- NodeIdSet closedTargetNodeSet = epsilonClosure(transitionSlot.value, nfaGraph, NFA::epsilonTransitionCharacter);
- unsigned newDFANodeId;
</del><ins>+ if (targetNodeSet.isEmpty())
+ continue;
</ins><span class="cx">
</span><del>- const auto& existingNFAToDFAAssociation = nfaToDFANodeMap.find(closedTargetNodeSet);
- if (existingNFAToDFAAssociation != nfaToDFANodeMap.end())
- newDFANodeId = existingNFAToDFAAssociation->value;
- else
- newDFANodeId = addDFAState(dfaGraph, nfaToDFANodeMap, nfaGraph, closedTargetNodeSet, NFA::epsilonTransitionCharacter);
</del><ins>+ epsilonClosure(targetNodeSet, nfaGraph, NFA::epsilonTransitionCharacter);
</ins><span class="cx">
</span><del>- ASSERT(newDFANodeId < dfaGraph.size());
</del><ins>+ NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, targetNodeSet);
+ auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
</ins><span class="cx">
</span><del>- const auto addResult = dfaGraph[dfaNodeId].transitions.set(transitionSlot.key, newDFANodeId);
</del><ins>+ unsigned targetNodeId = uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
+ const auto addResult = dfaGraph[dfaNodeId].transitions.add(key, targetNodeId);
</ins><span class="cx"> ASSERT_UNUSED(addResult, addResult.isNewEntry);
</span><span class="cx">
</span><del>- if (!processedStateSets.contains(closedTargetNodeSet))
- unprocessedStateSets.add(closedTargetNodeSet);
</del><ins>+ if (uniqueNodeIdAddResult.isNewEntry)
+ unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
+
+ targetNodeSet.clear();
</ins><span class="cx"> }
</span><del>- } while (!unprocessedStateSets.isEmpty());
</del><ins>+ } while (!unprocessedNodes.isEmpty());
</ins><span class="cx">
</span><del>- ASSERT(processedStateSets.size() == nfaToDFANodeMap.size());
-
</del><span class="cx"> return DFA(WTF::move(dfaGraph), 0);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>