<!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>[185230] 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/185230">185230</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-06-04 18:01:59 -0700 (Thu, 04 Jun 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Combine tiny DFAs into slightly larger ones
https://bugs.webkit.org/show_bug.cgi?id=145572
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-06-04
Reviewed by Alex Christensen.
Source/WebCore:
This patch changes the ContentExtensions compiler to combine tiny DFA
until they reach a minimum size.
The main tool introduced here is DFAMerger. It combines 2 DFAs into
a single DFA that represent the union of the two machines.
That is done by a simple subset construction on the "name" of the nodes
in each DFAs.
Since we only merge 2 machines, and they are both deterministic, we know that
we can only be in one state of each machine, or a state in one machine without
equivalent in the other machine.
We exploit that to identify the mapping between nodes. To identify a node in
the new machine from nodes in the original machines, we just concatenate the node
IDs into a single 64 bits number. If there is no node in one of the machine, we
use a special tag.
The current algorithm does not have any subgraph pruning, machines grow very very
quickly. Because of that, we only merge very small DFAs at the moment.
Test: http/tests/contentextensions/filters-with-quantifiers-combined.html
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
* contentextensions/ContentExtensionsDebugging.h:
* contentextensions/DFA.cpp:
(WebCore::ContentExtensions::DFA::graphSize):
(WebCore::ContentExtensions::DFA::debugPrintDot):
* contentextensions/DFA.h:
* contentextensions/DFACombiner.cpp: Added.
(WebCore::ContentExtensions::DFAMerger::DFAMerger):
(WebCore::ContentExtensions::DFAMerger::merge):
(WebCore::ContentExtensions::DFAMerger::signatureForIndices):
(WebCore::ContentExtensions::DFAMerger::extractIndexA):
(WebCore::ContentExtensions::DFAMerger::extractIndexB):
(WebCore::ContentExtensions::DFAMerger::getOrCreateCombinedNode):
(WebCore::ContentExtensions::DFAMerger::setHalfSignature):
(WebCore::ContentExtensions::DFAMerger::populateTransitions):
(WebCore::ContentExtensions::DFAMerger::populateFromFallbackTransitions):
(WebCore::ContentExtensions::DFAMerger::createTransitions):
(WebCore::ContentExtensions::DFAMerger::createFallbackTransitionIfNeeded):
(WebCore::ContentExtensions::DFACombiner::combineDFAs):
* contentextensions/DFACombiner.h: Copied from Source/WebCore/contentextensions/DFA.h.
(WebCore::ContentExtensions::DFACombiner::addDFA):
Tools:
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WebCore/DFACombiner.cpp: Added.
(TestWebKitAPI::DFACombinerTest::SetUp):
(TestWebKitAPI::combine):
(TestWebKitAPI::TEST_F):
* TestWebKitAPI/Tests/WebCore/DFAHelpers.h: Copied from Source/WebCore/contentextensions/DFA.h.
(TestWebKitAPI::countLiveNodes):
(TestWebKitAPI::createNFAs):
(TestWebKitAPI::buildDFAFromPatterns):
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
(TestWebKitAPI::countLiveNodes): Deleted.
(TestWebKitAPI::createNFAs): Deleted.
(TestWebKitAPI::buildDFAFromPatterns): Deleted.
LayoutTests:
* http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt: Added.
* http/tests/contentextensions/filters-with-quantifiers-combined.html: Added.
* http/tests/contentextensions/filters-with-quantifiers-combined.html.json: Added.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<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="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.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="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedexpectedtxt">trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt</a></li>
<li><a href="#trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedhtml">trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html</a></li>
<li><a href="#trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedhtmljson">trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html.json</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFACombinercpp">trunk/Source/WebCore/contentextensions/DFACombiner.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFACombinerh">trunk/Source/WebCore/contentextensions/DFACombiner.h</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFACombinercpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFACombiner.cpp</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreDFAHelpersh">trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/LayoutTests/ChangeLog 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -1,3 +1,14 @@
</span><ins>+2015-06-04 Benjamin Poulain <bpoulain@apple.com>
+
+ Combine tiny DFAs into slightly larger ones
+ https://bugs.webkit.org/show_bug.cgi?id=145572
+
+ Reviewed by Alex Christensen.
+
+ * http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt: Added.
+ * http/tests/contentextensions/filters-with-quantifiers-combined.html: Added.
+ * http/tests/contentextensions/filters-with-quantifiers-combined.html.json: Added.
+
</ins><span class="cx"> 2015-06-04 Said Abou-Hallawa <sabouhallawa@apple.com>
</span><span class="cx">
</span><span class="cx"> Skip failed layout tests following <http://trac.webkit.org/changeset/185207>
</span></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined-expected.txt 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,53 @@
</span><ins>+layer at (0,0) size 785x952
+ RenderView at (0,0) size 785x600
+layer at (0,0) size 785x952
+ RenderBlock {HTML} at (0,0) size 785x952
+ RenderBody {BODY} at (8,8) size 769x936
+ RenderText {#text} at (0,0) size 200x18
+ text run at (0,0) width 200: "The images below should load."
+ RenderBR {BR} at (199,14) size 1x0
+ RenderImage {IMG} at (0,18) size 100x100
+ RenderBR {BR} at (100,118) size 0x0
+ RenderImage {IMG} at (0,118) size 100x100
+ RenderBR {BR} at (100,218) size 0x0
+ RenderImage {IMG} at (0,218) size 100x100
+ RenderBR {BR} at (100,318) size 0x0
+ RenderImage {IMG} at (0,318) size 100x100
+ RenderBR {BR} at (100,418) size 0x0
+ RenderImage {IMG} at (0,418) size 100x100
+ RenderBR {BR} at (100,518) size 0x0
+ RenderImage {IMG} at (0,518) size 100x100
+ RenderBR {BR} at (100,618) size 0x0
+ RenderImage {IMG} at (0,618) size 100x100
+ RenderBR {BR} at (100,718) size 0x0
+ RenderImage {IMG} at (0,718) size 100x100
+ RenderBR {BR} at (100,818) size 0x0
+ RenderImage {IMG} at (0,818) size 100x100
+ RenderBR {BR} at (100,918) size 0x0
+ RenderText {#text} at (0,918) size 242x18
+ text run at (0,918) width 242: "The images below should be blocked."
+ RenderBR {BR} at (241,932) size 1x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
+ RenderImage {IMG} at (0,936) size 0x0
+ RenderBR {BR} at (0,936) size 0x0
</ins></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,26 @@
</span><ins>+<body>
+The images below should load.<br>
+<img src="http://127.0.0.1:8000/resources/square100.png"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?abcabcdwhitelist"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?abccccccc"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?defffffff"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?jkljkljkl"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?pqrabcdef"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?wxybc"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?acbxyxyxyxyxy"><br>
+<img src="http://127.0.0.1:8000/resources/square100.png?abcdefjklpqrwxyacdacbbcghmosvabacbxy"><br>
+
+The images below should be blocked.<br>
+<img src="http://localhost:8000/resources/square100.png?abcabc"><br>
+<img src="http://localhost:8000/resources/square100.png?abccabc"><br>
+<img src="http://localhost:8000/resources/square100.png?defghi"><br>
+<img src="http://localhost:8000/resources/square100.png?defgghi"><br>
+<img src="http://localhost:8000/resources/square100.png?jklmno"><br>
+<img src="http://localhost:8000/resources/square100.png?jkljklmno"><br>
+<img src="http://localhost:8000/resources/square100.png?pqrstv"><br>
+<img src="http://localhost:8000/resources/square100.png?pqrabcstv"><br>
+<img src="http://localhost:8000/resources/square100.png?wxyabc"><br>
+<img src="http://localhost:8000/resources/square100.png?wxydefabc"><br>
+<img src="http://localhost:8000/resources/square100.png?acbwxy"><br>
+<img src="http://localhost:8000/resources/square100.png?abcacbdefabcdjklwhitelistwxy"><br>
+</body>
</ins></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionsfilterswithquantifierscombinedhtmljson"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html.json (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html.json (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/filters-with-quantifiers-combined.html.json 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,58 @@
</span><ins>+[
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "abc.*abc"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "def.*ghi"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "jkl.*mno"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "pqr.*stv"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "wxy.*abc"
+ }
+ },
+ {
+ "action": {
+ "type": "ignore-previous-rules"
+ },
+ "trigger": {
+ "url-filter": "abcd.*whitelist"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "acb.*wxy"
+ }
+ }
+]
</ins></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Source/WebCore/ChangeLog 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -1,3 +1,55 @@
</span><ins>+2015-06-04 Benjamin Poulain <bpoulain@apple.com>
+
+ Combine tiny DFAs into slightly larger ones
+ https://bugs.webkit.org/show_bug.cgi?id=145572
+
+ Reviewed by Alex Christensen.
+
+ This patch changes the ContentExtensions compiler to combine tiny DFA
+ until they reach a minimum size.
+
+ The main tool introduced here is DFAMerger. It combines 2 DFAs into
+ a single DFA that represent the union of the two machines.
+ That is done by a simple subset construction on the "name" of the nodes
+ in each DFAs.
+
+ Since we only merge 2 machines, and they are both deterministic, we know that
+ we can only be in one state of each machine, or a state in one machine without
+ equivalent in the other machine.
+ We exploit that to identify the mapping between nodes. To identify a node in
+ the new machine from nodes in the original machines, we just concatenate the node
+ IDs into a single 64 bits number. If there is no node in one of the machine, we
+ use a special tag.
+
+ The current algorithm does not have any subgraph pruning, machines grow very very
+ quickly. Because of that, we only merge very small DFAs at the moment.
+
+ Test: http/tests/contentextensions/filters-with-quantifiers-combined.html
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/ContentExtensionsDebugging.h:
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::graphSize):
+ (WebCore::ContentExtensions::DFA::debugPrintDot):
+ * contentextensions/DFA.h:
+ * contentextensions/DFACombiner.cpp: Added.
+ (WebCore::ContentExtensions::DFAMerger::DFAMerger):
+ (WebCore::ContentExtensions::DFAMerger::merge):
+ (WebCore::ContentExtensions::DFAMerger::signatureForIndices):
+ (WebCore::ContentExtensions::DFAMerger::extractIndexA):
+ (WebCore::ContentExtensions::DFAMerger::extractIndexB):
+ (WebCore::ContentExtensions::DFAMerger::getOrCreateCombinedNode):
+ (WebCore::ContentExtensions::DFAMerger::setHalfSignature):
+ (WebCore::ContentExtensions::DFAMerger::populateTransitions):
+ (WebCore::ContentExtensions::DFAMerger::populateFromFallbackTransitions):
+ (WebCore::ContentExtensions::DFAMerger::createTransitions):
+ (WebCore::ContentExtensions::DFAMerger::createFallbackTransitionIfNeeded):
+ (WebCore::ContentExtensions::DFACombiner::combineDFAs):
+ * contentextensions/DFACombiner.h: Copied from Source/WebCore/contentextensions/DFA.h.
+ (WebCore::ContentExtensions::DFACombiner::addDFA):
+
</ins><span class="cx"> 2015-06-04 Matt Rajca <mrajca@apple.com>
</span><span class="cx">
</span><span class="cx"> Rename MediaSessionManager to PlatformMediaSessionManager for consistency with PlatformMediaSession.
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -1017,6 +1017,8 @@
</span><span class="cx"> 269397261A4A5FBD00E8349D /* NFA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 269397251A4A5FBD00E8349D /* NFA.cpp */; };
</span><span class="cx"> 26A517FD1AB92238006335DF /* DFAMinimizer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */; };
</span><span class="cx"> 26A517FE1AB92238006335DF /* DFAMinimizer.h in Headers */ = {isa = PBXBuildFile; fileRef = 26A517FC1AB92238006335DF /* DFAMinimizer.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><ins>+ 26A807841B18F97700E219BE /* DFACombiner.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26A807821B18F97700E219BE /* DFACombiner.cpp */; };
+ 26A807851B18F97700E219BE /* DFACombiner.h in Headers */ = {isa = PBXBuildFile; fileRef = 26A807831B18F97700E219BE /* DFACombiner.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 26AA0F9E18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26AA0F9D18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp */; };
</span><span class="cx"> 26B9998F1803AE7200D01121 /* RegisterAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 26B9998E1803AE7200D01121 /* RegisterAllocator.h */; };
</span><span class="cx"> 26B999911803B3C900D01121 /* StackAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 26B999901803B3C900D01121 /* StackAllocator.h */; };
</span><span class="lines">@@ -8141,6 +8143,8 @@
</span><span class="cx"> 269397251A4A5FBD00E8349D /* NFA.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NFA.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFAMinimizer.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26A517FC1AB92238006335DF /* DFAMinimizer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFAMinimizer.h; sourceTree = "<group>"; };
</span><ins>+ 26A807821B18F97700E219BE /* DFACombiner.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFACombiner.cpp; sourceTree = "<group>"; };
+ 26A807831B18F97700E219BE /* DFACombiner.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFACombiner.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26AA0F9918D2973D00419381 /* makeSelectorPseudoElementsMap.py */ = {isa = PBXFileReference; lastKnownFileType = text.script.python; path = makeSelectorPseudoElementsMap.py; sourceTree = "<group>"; };
</span><span class="cx"> 26AA0F9A18D2973D00419381 /* SelectorPseudoElementTypeMap.in */ = {isa = PBXFileReference; lastKnownFileType = text; path = SelectorPseudoElementTypeMap.in; sourceTree = "<group>"; };
</span><span class="cx"> 26AA0F9D18D2A18B00419381 /* SelectorPseudoElementTypeMap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SelectorPseudoElementTypeMap.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15649,6 +15653,8 @@
</span><span class="cx"> 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */,
</span><span class="cx"> 5C3930601AA0F6A90029C816 /* DFABytecodeInterpreter.cpp */,
</span><span class="cx"> 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */,
</span><ins>+ 26A807821B18F97700E219BE /* DFACombiner.cpp */,
+ 26A807831B18F97700E219BE /* DFACombiner.h */,
</ins><span class="cx"> 26A517FB1AB92238006335DF /* DFAMinimizer.cpp */,
</span><span class="cx"> 26A517FC1AB92238006335DF /* DFAMinimizer.h */,
</span><span class="cx"> 267725F91A5B3AD9003C24DD /* DFANode.h */,
</span><span class="lines">@@ -24162,6 +24168,7 @@
</span><span class="cx"> F98FFF4511A2676200F548E8 /* CSSOMUtils.h in Headers */,
</span><span class="cx"> A80E6D000A1989CA007FB8C5 /* CSSPageRule.h in Headers */,
</span><span class="cx"> BC772B3E0C4EA91E0083285F /* CSSParser.h in Headers */,
</span><ins>+ 26A807851B18F97700E219BE /* DFACombiner.h in Headers */,
</ins><span class="cx"> FB78AD2E151BF5E600FE54D3 /* CSSParserMode.h in Headers */,
</span><span class="cx"> BC02A4B70E0997B9004B6D2B /* CSSParserValues.h in Headers */,
</span><span class="cx"> 977B3863122883E900B81FF8 /* CSSPreloadScanner.h in Headers */,
</span><span class="lines">@@ -28283,6 +28290,7 @@
</span><span class="cx"> 2EF1BFEA121C9F4200C27627 /* FileStream.cpp in Sources */,
</span><span class="cx"> C57FEDE11212EE9C0097BE65 /* FileSystem.cpp in Sources */,
</span><span class="cx"> 5160306C0CC4362300C8AC25 /* FileSystemCF.cpp in Sources */,
</span><ins>+ 26A807841B18F97700E219BE /* DFACombiner.cpp in Sources */,
</ins><span class="cx"> 26C17A3F1491D2D400D12BA2 /* FileSystemIOS.mm in Sources */,
</span><span class="cx"> 514B3F760C722055000530DF /* FileSystemMac.mm in Sources */,
</span><span class="cx"> 5160300B0CC4251200C8AC25 /* FileSystemPOSIX.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -36,6 +36,7 @@
</span><span class="cx"> #include "ContentExtensionRule.h"
</span><span class="cx"> #include "ContentExtensionsDebugging.h"
</span><span class="cx"> #include "DFABytecodeCompiler.h"
</span><ins>+#include "DFACombiner.h"
</ins><span class="cx"> #include "NFA.h"
</span><span class="cx"> #include "NFAToDFA.h"
</span><span class="cx"> #include "URLFilterParser.h"
</span><span class="lines">@@ -235,6 +236,10 @@
</span><span class="cx"> LOG_LARGE_STRUCTURES(domainFilters, domainFilters.memoryUsed());
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><ins>+ unsigned machinesWithoutDomainsCount = 0;
+ unsigned totalBytecodeSizeForMachinesWithoutDomains = 0;
+ unsigned machinesWithDomainsCount = 0;
+ unsigned totalBytecodeSizeForMachinesWithDomains = 0;
</ins><span class="cx"> double totalNFAToByteCodeBuildTimeStart = monotonicallyIncreasingTime();
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="lines">@@ -243,20 +248,9 @@
</span><span class="cx"> const unsigned maxNFASize = 30000;
</span><span class="cx">
</span><span class="cx"> bool firstNFAWithoutDomainsSeen = false;
</span><del>- // FIXME: Combine small NFAs to reduce the number of NFAs.
- filtersWithoutDomains.processNFAs(maxNFASize, [&](NFA&& nfa) {
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- dataLogF("filtersWithoutDomains NFA\n");
- nfa.debugPrintDot();
-#endif
</del><span class="cx">
</span><del>- LOG_LARGE_STRUCTURES(nfa, nfa.memoryUsed());
-
- DFA dfa = NFAToDFA::convert(nfa);
- LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
-
- dfa.minimize();
-
</del><ins>+ auto lowerFiltersWithoutDomainsDFAToBytecode = [&](DFA&& dfa)
+ {
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> dataLogF("filtersWithoutDomains DFA\n");
</span><span class="cx"> dfa.debugPrintDot();
</span><span class="lines">@@ -272,10 +266,41 @@
</span><span class="cx"> DFABytecodeCompiler compiler(dfa, bytecode);
</span><span class="cx"> compiler.compile();
</span><span class="cx"> LOG_LARGE_STRUCTURES(bytecode, bytecode.capacity() * sizeof(uint8_t));
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ ++machinesWithoutDomainsCount;
+ totalBytecodeSizeForMachinesWithoutDomains += bytecode.size();
+#endif
</ins><span class="cx"> client.writeFiltersWithoutDomainsBytecode(WTF::move(bytecode));
</span><span class="cx">
</span><span class="cx"> firstNFAWithoutDomainsSeen = true;
</span><ins>+ };
+
+ const unsigned smallDFASize = 100;
+ DFACombiner smallFiltersWithoutDomainsDFACombiner;
+ filtersWithoutDomains.processNFAs(maxNFASize, [&](NFA&& nfa) {
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ dataLogF("filtersWithoutDomains NFA\n");
+ nfa.debugPrintDot();
+#endif
+
+ LOG_LARGE_STRUCTURES(nfa, nfa.memoryUsed());
+ DFA dfa = NFAToDFA::convert(nfa);
+ LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
+
+ if (dfa.graphSize() < smallDFASize)
+ smallFiltersWithoutDomainsDFACombiner.addDFA(WTF::move(dfa));
+ else {
+ dfa.minimize();
+ lowerFiltersWithoutDomainsDFAToBytecode(WTF::move(dfa));
+ }
</ins><span class="cx"> });
</span><ins>+
+
+ smallFiltersWithoutDomainsDFACombiner.combineDFAs(smallDFASize, [&](DFA&& dfa) {
+ LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
+ lowerFiltersWithoutDomainsDFAToBytecode(WTF::move(dfa));
+ });
+
</ins><span class="cx"> ASSERT(filtersWithoutDomains.isEmpty());
</span><span class="cx">
</span><span class="cx"> if (!firstNFAWithoutDomainsSeen) {
</span><span class="lines">@@ -297,6 +322,27 @@
</span><span class="cx"> universalActionsWithoutDomains.clear();
</span><span class="cx">
</span><span class="cx"> bool firstNFAWithDomainsSeen = false;
</span><ins>+ auto lowerFiltersWithDomainsDFAToBytecode = [&](DFA&& dfa)
+ {
+ if (!firstNFAWithDomainsSeen) {
+ // Put all the universal actions on the first DFA.
+ addUniversalActionsToDFA(dfa, universalActionsWithDomains);
+ }
+
+ Vector<DFABytecode> bytecode;
+ DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ LOG_LARGE_STRUCTURES(bytecode, bytecode.capacity() * sizeof(uint8_t));
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ ++machinesWithDomainsCount;
+ totalBytecodeSizeForMachinesWithDomains += bytecode.size();
+#endif
+ client.writeFiltersWithDomainsBytecode(WTF::move(bytecode));
+
+ firstNFAWithDomainsSeen = true;
+ };
+
+ DFACombiner smallFiltersWithDomainsDFACombiner;
</ins><span class="cx"> filtersWithDomains.processNFAs(maxNFASize, [&](NFA&& nfa) {
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> dataLogF("filtersWithDomains NFA\n");
</span><span class="lines">@@ -309,26 +355,20 @@
</span><span class="cx"> dfa.debugPrintDot();
</span><span class="cx"> #endif
</span><span class="cx"> LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
</span><del>- // Minimizing this DFA would not be effective because all actions with domains are unique.
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- dataLogF("filtersWithDomains POST MINIMIZING DFA\n");
- dfa.debugPrintDot();
-#endif
</del><ins>+
</ins><span class="cx"> ASSERT_WITH_MESSAGE(!dfa.nodes[dfa.root].hasActions(), "Filters with domains that match everything are not allowed right now.");
</span><del>-
- if (!firstNFAWithDomainsSeen) {
- // Put all the universal actions on the first DFA.
- addUniversalActionsToDFA(dfa, universalActionsWithDomains);
</del><ins>+
+ if (dfa.graphSize() < smallDFASize)
+ smallFiltersWithDomainsDFACombiner.addDFA(WTF::move(dfa));
+ else {
+ dfa.minimize();
+ lowerFiltersWithDomainsDFAToBytecode(WTF::move(dfa));
</ins><span class="cx"> }
</span><del>-
- Vector<DFABytecode> bytecode;
- DFABytecodeCompiler compiler(dfa, bytecode);
- compiler.compile();
- LOG_LARGE_STRUCTURES(bytecode, bytecode.capacity() * sizeof(uint8_t));
- client.writeFiltersWithDomainsBytecode(WTF::move(bytecode));
-
- firstNFAWithDomainsSeen = true;
</del><span class="cx"> });
</span><ins>+ smallFiltersWithDomainsDFACombiner.combineDFAs(smallDFASize, [&](DFA&& dfa) {
+ LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
+ lowerFiltersWithDomainsDFAToBytecode(WTF::move(dfa));
+ });
</ins><span class="cx"> ASSERT(filtersWithDomains.isEmpty());
</span><span class="cx">
</span><span class="cx"> if (!firstNFAWithDomainsSeen) {
</span><span class="lines">@@ -364,7 +404,7 @@
</span><span class="cx"> // Minimizing this DFA would not be effective because all actions are unique
</span><span class="cx"> // and because of the tree-like structure of this DFA.
</span><span class="cx"> ASSERT_WITH_MESSAGE(!dfa.nodes[dfa.root].hasActions(), "There should not be any domains that match everything.");
</span><del>-
</del><ins>+
</ins><span class="cx"> Vector<DFABytecode> bytecode;
</span><span class="cx"> DFABytecodeCompiler compiler(dfa, bytecode);
</span><span class="cx"> compiler.compile();
</span><span class="lines">@@ -376,6 +416,9 @@
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> double totalNFAToByteCodeBuildTimeEnd = monotonicallyIncreasingTime();
</span><span class="cx"> dataLogF(" Time spent building and compiling the DFAs: %f\n", (totalNFAToByteCodeBuildTimeEnd - totalNFAToByteCodeBuildTimeStart));
</span><ins>+
+ dataLogF(" Number of machines without domain filters: %d (total bytecode size = %d)\n", machinesWithoutDomainsCount, totalBytecodeSizeForMachinesWithoutDomains);
+ dataLogF(" Number of machines with domain filters: %d (total bytecode size = %d)\n", machinesWithDomainsCount, totalBytecodeSizeForMachinesWithDomains);
</ins><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> client.finalize();
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -127,6 +127,16 @@
</span><span class="cx"> DFAMinimizer::minimize(*this);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+unsigned DFA::graphSize() const
+{
+ unsigned count = 0;
+ for (const DFANode& node : nodes) {
+ if (!node.isKilled())
+ ++count;
+ }
+ return count;
+}
+
</ins><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> static void printRange(bool firstRange, char rangeStart, char rangeEnd)
</span><span class="cx"> {
</span><span class="lines">@@ -212,14 +222,14 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector<unsigned> correspondingNFANodes = nodes[i].correspondingNFANodes;
</span><del>- ASSERT(!correspondingNFANodes.isEmpty());
- dataLogF("<BR/>NFA Nodes: ");
- for (unsigned correspondingDFANodeIndex = 0; correspondingDFANodeIndex < correspondingNFANodes.size(); ++correspondingDFANodeIndex) {
- if (correspondingDFANodeIndex)
- dataLogF(", ");
- dataLogF("%d", correspondingNFANodes[correspondingDFANodeIndex]);
</del><ins>+ if (!correspondingNFANodes.isEmpty()) {
+ dataLogF("<BR/>NFA Nodes: ");
+ for (unsigned correspondingDFANodeIndex = 0; correspondingDFANodeIndex < correspondingNFANodes.size(); ++correspondingDFANodeIndex) {
+ if (correspondingDFANodeIndex)
+ dataLogF(", ");
+ dataLogF("%d", correspondingNFANodes[correspondingDFANodeIndex]);
+ }
</ins><span class="cx"> }
</span><del>-
</del><span class="cx"> dataLogF(">]");
</span><span class="cx">
</span><span class="cx"> if (!actions.isEmpty())
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -39,6 +39,7 @@
</span><span class="cx"> // The DFA abstract a partial DFA graph in a compact form.
</span><span class="cx"> struct WEBCORE_EXPORT DFA {
</span><span class="cx"> void minimize();
</span><ins>+ unsigned graphSize() const;
</ins><span class="cx"> size_t memoryUsed() const;
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFACombinercpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/DFACombiner.cpp (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFACombiner.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFACombiner.cpp 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,266 @@
</span><ins>+/*
+ * Copyright (C) 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.
+ */
+
+#include "config.h"
+#include "DFACombiner.h"
+
+#include <wtf/HashMap.h>
+#include <wtf/HashSet.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class DFAMerger {
+public:
+ DFAMerger(const DFA& a, const DFA& b)
+ : m_dfaA(a)
+ , m_dfaB(b)
+ {
+ }
+
+ DFA merge()
+ {
+ if (!m_nodeMapping.isEmpty())
+ return m_output;
+
+ uint64_t rootSignature = signatureForIndices(m_dfaA.root, m_dfaB.root);
+ getOrCreateCombinedNode(rootSignature);
+
+ while (!m_unprocessedNodes.isEmpty()) {
+ memset(m_transitionTargets, 0xff, sizeof(m_transitionTargets));
+
+ uint64_t unprocessedNode = m_unprocessedNodes.takeLast();
+
+ // We cannot cache the source node itself since we modify the machine. We only manipulate the IDs.
+ uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
+
+ // Populate the unique transitions.
+ uint32_t indexA = extractIndexA(unprocessedNode);
+ if (indexA != invalidNodeIndex)
+ populateTransitions<WhichDFA::A>(indexA);
+
+ uint32_t indexB = extractIndexB(unprocessedNode);
+ if (indexB != invalidNodeIndex)
+ populateTransitions<WhichDFA::B>(indexB);
+
+ // Spread the fallback transitions over the unique transitions and keep a reference to the fallback transition.
+ uint64_t fallbackTransitionSignature = signatureForIndices(invalidNodeIndex, invalidNodeIndex);
+ if (indexA != invalidNodeIndex)
+ populateFromFallbackTransitions<WhichDFA::A>(indexA, fallbackTransitionSignature);
+ if (indexB != invalidNodeIndex)
+ populateFromFallbackTransitions<WhichDFA::B>(indexB, fallbackTransitionSignature);
+
+ createTransitions(sourceNodeId);
+ createFallbackTransitionIfNeeded(sourceNodeId, fallbackTransitionSignature);
+ }
+ return m_output;
+ }
+
+private:
+ uint32_t invalidNodeIndex = 0xffffffff;
+
+ enum class WhichDFA {
+ A,
+ B
+ };
+
+ static uint64_t signatureForIndices(uint32_t aIndex, uint32_t bIndex)
+ {
+ return static_cast<uint64_t>(aIndex) << 32 | bIndex;
+ }
+
+ static uint32_t extractIndexA(uint64_t signature)
+ {
+ return static_cast<uint32_t>(signature >> 32);
+ }
+
+ static uint32_t extractIndexB(uint64_t signature)
+ {
+ return static_cast<uint32_t>(signature);
+ }
+
+ uint32_t getOrCreateCombinedNode(uint64_t newNodeSignature)
+ {
+ auto addResult = m_nodeMapping.add(newNodeSignature, invalidNodeIndex);
+ if (!addResult.isNewEntry)
+ return addResult.iterator->value;
+
+ m_output.nodes.append(DFANode());
+ uint32_t newNodeIndex = m_output.nodes.size() - 1;
+ addResult.iterator->value = newNodeIndex;
+ m_unprocessedNodes.append(newNodeSignature);
+
+ uint32_t indexA = extractIndexA(newNodeSignature);
+ uint32_t indexB = extractIndexB(newNodeSignature);
+
+ HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
+ if (indexA != invalidNodeIndex) {
+ const DFANode& node = m_dfaA.nodes[indexA];
+ uint32_t actionsStart = node.actionsStart();
+ uint32_t actionsEnd = actionsStart + node.actionsLength();
+ for (uint32_t i = actionsStart; i < actionsEnd; ++i)
+ actions.add(m_dfaA.actions[i]);
+ }
+ if (indexB != invalidNodeIndex) {
+ const DFANode& node = m_dfaB.nodes[indexB];
+ uint32_t actionsStart = node.actionsStart();
+ uint32_t actionsEnd = actionsStart + node.actionsLength();
+ for (uint32_t i = actionsStart; i < actionsEnd; ++i)
+ actions.add(m_dfaB.actions[i]);
+ }
+
+ uint32_t actionsStart = m_output.actions.size();
+ for (uint64_t action : actions)
+ m_output.actions.append(action);
+ uint32_t actionsEnd = m_output.actions.size();
+ uint16_t actionsLength = static_cast<uint16_t>(actionsEnd - actionsStart);
+
+ m_output.nodes.last().setActions(actionsStart, actionsLength);
+ return newNodeIndex;
+ }
+
+ template<WhichDFA whichDFA>
+ void setHalfSignature(uint64_t& signature, uint32_t value)
+ {
+ unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
+ uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
+ signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
+ }
+
+ template<WhichDFA whichDFA>
+ void populateTransitions(uint32_t nodeIndex)
+ {
+ const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
+ const DFANode& node = dfa.nodes[nodeIndex];
+ uint32_t transitionsStart = node.transitionsStart();
+ uint32_t transitionsEnd = transitionsStart + node.transitionsLength();
+
+ // Extract transitions.
+ for (uint32_t transitionIndex = transitionsStart; transitionIndex < transitionsEnd; ++transitionIndex) {
+ uint8_t transitionCharacter = dfa.transitionCharacters[transitionIndex];
+ RELEASE_ASSERT(transitionCharacter < WTF_ARRAY_LENGTH(m_transitionTargets));
+
+ uint32_t transitionDestination = dfa.transitionDestinations[transitionIndex];
+ setHalfSignature<whichDFA>(m_transitionTargets[transitionCharacter], transitionDestination);
+ }
+ }
+
+ template<WhichDFA whichDFA>
+ void populateFromFallbackTransitions(uint32_t nodeIndex, uint64_t& fallbackTransitionSignature)
+ {
+ const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
+ const DFANode& node = dfa.nodes[nodeIndex];
+ if (!node.hasFallbackTransition())
+ return;
+
+ uint32_t fallbackTarget = node.fallbackTransitionDestination(dfa);
+ setHalfSignature<whichDFA>(fallbackTransitionSignature, fallbackTarget);
+
+ // Spread the fallback over transitions where the other has something and we don't.
+ for (unsigned i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
+ uint64_t& targetSignature = m_transitionTargets[i];
+
+ uint32_t otherTarget = (whichDFA == WhichDFA::A) ? extractIndexB(targetSignature) : extractIndexA(targetSignature);
+ uint32_t selfTarget = (whichDFA == WhichDFA::A) ? extractIndexA(targetSignature) : extractIndexB(targetSignature);
+
+ if (otherTarget != invalidNodeIndex && selfTarget == invalidNodeIndex)
+ setHalfSignature<whichDFA>(targetSignature, fallbackTarget);
+ }
+ }
+
+ void createTransitions(uint32_t sourceNodeId)
+ {
+ // Create transitions out of the source node, creating new nodes as needed.
+ uint32_t transitionsStart = m_output.transitionCharacters.size();
+ for (uint8_t i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
+ uint64_t signature = m_transitionTargets[i];
+ if (signature == signatureForIndices(invalidNodeIndex, invalidNodeIndex))
+ continue;
+ uint32_t nodeId = getOrCreateCombinedNode(signature);
+ m_output.transitionCharacters.append(i);
+ m_output.transitionDestinations.append(nodeId);
+ }
+ uint32_t transitionsEnd = m_output.transitionCharacters.size();
+ uint8_t transitionsLength = static_cast<uint8_t>(transitionsEnd - transitionsStart);
+
+ m_output.nodes[sourceNodeId].setTransitions(transitionsStart, transitionsLength);
+ }
+
+ void createFallbackTransitionIfNeeded(uint32_t sourceNodeId, uint64_t fallbackTransitionSignature)
+ {
+ if (fallbackTransitionSignature != signatureForIndices(invalidNodeIndex, invalidNodeIndex)) {
+ uint32_t nodeId = getOrCreateCombinedNode(fallbackTransitionSignature);
+ m_output.nodes[sourceNodeId].addFallbackTransition(m_output, nodeId);
+ }
+ }
+
+ const DFA& m_dfaA;
+ const DFA& m_dfaB;
+ DFA m_output;
+ HashMap<uint64_t, uint32_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> m_nodeMapping;
+ Vector<uint64_t> m_unprocessedNodes;
+ uint64_t m_transitionTargets[128];
+};
+
+void DFACombiner::combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler)
+{
+ if (m_dfas.isEmpty())
+ return;
+
+ for (unsigned i = m_dfas.size(); i--;) {
+ if (m_dfas[i].graphSize() > minimumSize) {
+ handler(WTF::move(m_dfas[i]));
+ m_dfas.remove(i);
+ }
+ }
+
+ while (!m_dfas.isEmpty()) {
+ if (m_dfas.size() == 1) {
+ handler(WTF::move(m_dfas.first()));
+ return;
+ }
+
+ DFA a = m_dfas.takeLast();
+ DFA b = m_dfas.takeLast();
+ DFAMerger dfaMerger(a, b);
+ DFA c = dfaMerger.merge();
+
+ if (c.graphSize() > minimumSize) {
+ // Minimizing is somewhat expensive. We only do it in bulk when we reach the threshold
+ // to reduce the load.
+ c.minimize();
+ }
+
+ if (c.graphSize() > minimumSize)
+ handler(WTF::move(c));
+ else
+ m_dfas.append(c);
+ }
+}
+
+}
+
+} // namespace WebCore
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFACombinerh"></a>
<div class="addfile"><h4>Added: trunk/Source/WebCore/contentextensions/DFACombiner.h (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFACombiner.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFACombiner.h 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,55 @@
</span><ins>+/*
+ * Copyright (C) 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 DFACombiner_h
+#define DFACombiner_h
+
+#include "DFA.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class WEBCORE_EXPORT DFACombiner {
+public:
+ void addDFA(DFA&&);
+ void combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler);
+
+private:
+ Vector<DFA> m_dfas;
+};
+
+inline void DFACombiner::addDFA(DFA&& dfa)
+{
+ dfa.minimize();
+ m_dfas.append(WTF::move(dfa));
+}
+
+}
+
+} // namespace WebCore
+
+#endif
</ins></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Tools/ChangeLog 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -1,3 +1,24 @@
</span><ins>+2015-06-04 Benjamin Poulain <bpoulain@apple.com>
+
+ Combine tiny DFAs into slightly larger ones
+ https://bugs.webkit.org/show_bug.cgi?id=145572
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WebCore/DFACombiner.cpp: Added.
+ (TestWebKitAPI::DFACombinerTest::SetUp):
+ (TestWebKitAPI::combine):
+ (TestWebKitAPI::TEST_F):
+ * TestWebKitAPI/Tests/WebCore/DFAHelpers.h: Copied from Source/WebCore/contentextensions/DFA.h.
+ (TestWebKitAPI::countLiveNodes):
+ (TestWebKitAPI::createNFAs):
+ (TestWebKitAPI::buildDFAFromPatterns):
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+ (TestWebKitAPI::countLiveNodes): Deleted.
+ (TestWebKitAPI::createNFAs): Deleted.
+ (TestWebKitAPI::buildDFAFromPatterns): Deleted.
+
</ins><span class="cx"> 2015-06-04 Alexey Proskuryakov <ap@apple.com>
</span><span class="cx">
</span><span class="cx"> WebKitTestRunner leaks strings in generateWhitelist()
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -19,6 +19,7 @@
</span><span class="cx"> 1ADBEFE3130C6AA100D61D19 /* simple-accelerated-compositing.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1ADBEFBC130C6A0100D61D19 /* simple-accelerated-compositing.html */; };
</span><span class="cx"> 1AEDE22613E5E7E700E62FE8 /* InjectedBundleControllerMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */; };
</span><span class="cx"> 1CB9BC381A67482300FE5678 /* WeakPtr.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1CB9BC371A67482300FE5678 /* WeakPtr.cpp */; };
</span><ins>+ 260BA5791B1D2E7B004FA07C /* DFACombiner.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 260BA5781B1D2E7B004FA07C /* DFACombiner.cpp */; };
</ins><span class="cx"> 26DF5A6315A2A27E003689C2 /* CancelLoadFromResourceLoadDelegate.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26DF5A6115A2A22B003689C2 /* CancelLoadFromResourceLoadDelegate.html */; };
</span><span class="cx"> 26F52EAD1828827B0023D412 /* geolocationGetCurrentPosition.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26F52EAC1828820E0023D412 /* geolocationGetCurrentPosition.html */; };
</span><span class="cx"> 26F52EAF18288C230023D412 /* geolocationGetCurrentPositionWithHighAccuracy.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26F52EAE18288C040023D412 /* geolocationGetCurrentPositionWithHighAccuracy.html */; };
</span><span class="lines">@@ -433,6 +434,8 @@
</span><span class="cx"> 1AEF994817A09F5300998EF0 /* GetPIDAfterAbortedProcessLaunch.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GetPIDAfterAbortedProcessLaunch.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 1AFDE6541953B2C000C48FFA /* Optional.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Optional.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 1CB9BC371A67482300FE5678 /* WeakPtr.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WeakPtr.cpp; sourceTree = "<group>"; };
</span><ins>+ 260BA5781B1D2E7B004FA07C /* DFACombiner.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFACombiner.cpp; sourceTree = "<group>"; };
+ 260BA57A1B1D2EE2004FA07C /* DFAHelpers.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFAHelpers.h; sourceTree = "<group>"; };
</ins><span class="cx"> 261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = SetAndUpdateCacheModel.mm; sourceTree = "<group>"; };
</span><span class="cx"> 26300B1716755CD90066886D /* ListHashSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ListHashSet.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 265AF54F15D1E48A00B0CB4A /* WTFString.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WTFString.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -858,6 +861,8 @@
</span><span class="cx"> 93A720E518F1A0E800A848E1 /* CalculationValue.cpp */,
</span><span class="cx"> 7CB184C41AA3F2100066EDFD /* ContentExtensions.cpp */,
</span><span class="cx"> CD5451E919E41F9D0016936F /* CSSParser.cpp */,
</span><ins>+ 260BA5781B1D2E7B004FA07C /* DFACombiner.cpp */,
+ 260BA57A1B1D2EE2004FA07C /* DFAHelpers.h */,
</ins><span class="cx"> 26F6E1EF1ADC749B00DE696B /* DFAMinimizer.cpp */,
</span><span class="cx"> 41973B5A1AF2286A006C7B36 /* FileSystem.cpp */,
</span><span class="cx"> 14464012167A8305000BD218 /* LayoutUnit.cpp */,
</span><span class="lines">@@ -1602,6 +1607,7 @@
</span><span class="cx"> 41973B5B1AF2286A006C7B36 /* FileSystem.cpp in Sources */,
</span><span class="cx"> 7A5623111AD5AF3E0096B920 /* MenuTypesForMouseEvents.cpp in Sources */,
</span><span class="cx"> 26F6E1F01ADC749B00DE696B /* DFAMinimizer.cpp in Sources */,
</span><ins>+ 260BA5791B1D2E7B004FA07C /* DFACombiner.cpp in Sources */,
</ins><span class="cx"> 7A99D9941AD4A29D00373141 /* MenuTypesForMouseEvents.mm in Sources */,
</span><span class="cx"> );
</span><span class="cx"> runOnlyForDeploymentPostprocessing = 0;
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFACombinercpp"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFACombiner.cpp (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFACombiner.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFACombiner.cpp 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,121 @@
</span><ins>+/*
+ * Copyright (C) 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.
+ */
+
+#include "config.h"
+
+#include "DFAHelpers.h"
+#include <WebCore/DFACombiner.h>
+#include <wtf/MainThread.h>
+
+using namespace WebCore;
+using namespace ContentExtensions;
+
+namespace TestWebKitAPI {
+
+class DFACombinerTest : public testing::Test {
+public:
+ virtual void SetUp()
+ {
+ WTF::initializeMainThread();
+ }
+};
+
+Vector<DFA> combine(Vector<DFA> dfas, unsigned minimumSize)
+{
+ DFACombiner combiner;
+ for (DFA& dfa : dfas)
+ combiner.addDFA(WTF::move(dfa));
+
+ Vector<DFA> output;
+ combiner.combineDFAs(minimumSize, [&output](DFA&& dfa) {
+ output.append(dfa);
+ });
+ return output;
+}
+
+TEST_F(DFACombinerTest, Basic)
+{
+ Vector<DFA> dfas = { buildDFAFromPatterns({ "foo"}), buildDFAFromPatterns({ "bar"}) };
+ Vector<DFA> combinedDFAs = combine(dfas, 10000);
+ EXPECT_EQ(static_cast<size_t>(1), combinedDFAs.size());
+
+ DFA reference = buildDFAFromPatterns({ "foo", "bar"});
+ reference.minimize();
+ EXPECT_EQ(countLiveNodes(reference), countLiveNodes(combinedDFAs.first()));
+}
+
+
+TEST_F(DFACombinerTest, IdenticalDFAs)
+{
+ Vector<DFA> dfas = { buildDFAFromPatterns({ "foo"}), buildDFAFromPatterns({ "foo"}) };
+ Vector<DFA> combinedDFAs = combine(dfas, 10000);
+ EXPECT_EQ(static_cast<size_t>(1), combinedDFAs.size());
+
+ // The result should have the exact same size as the minimized input.
+ DFA reference = buildDFAFromPatterns({ "foo"});
+ reference.minimize();
+ EXPECT_EQ(countLiveNodes(reference), countLiveNodes(combinedDFAs.first()));
+}
+
+TEST_F(DFACombinerTest, NoInput)
+{
+ DFACombiner combiner;
+ unsigned counter = 0;
+ combiner.combineDFAs(100000, [&counter](DFA&& dfa) {
+ ++counter;
+ });
+ EXPECT_EQ(static_cast<unsigned>(0), counter);
+}
+
+TEST_F(DFACombinerTest, SingleInput)
+{
+ Vector<DFA> dfas = { buildDFAFromPatterns({ "WebKit"}) };
+ Vector<DFA> combinedDFAs = combine(dfas, 10000);
+ EXPECT_EQ(static_cast<size_t>(1), combinedDFAs.size());
+
+ DFA reference = buildDFAFromPatterns({ "WebKit"});
+ reference.minimize();
+ EXPECT_EQ(countLiveNodes(reference), countLiveNodes(combinedDFAs.first()));
+}
+
+TEST_F(DFACombinerTest, InputTooLargeForMinimumSize)
+{
+ Vector<DFA> dfas = { buildDFAFromPatterns({ "foo"}), buildDFAFromPatterns({ "bar"}) };
+ Vector<DFA> combinedDFAs = combine(dfas, 2);
+ EXPECT_EQ(static_cast<size_t>(2), combinedDFAs.size());
+ EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(combinedDFAs[0]));
+ EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(combinedDFAs[1]));
+}
+
+TEST_F(DFACombinerTest, CombinedInputReachesMinimumSize)
+{
+ Vector<DFA> dfas = { buildDFAFromPatterns({ "foo"}), buildDFAFromPatterns({ "bar"}), buildDFAFromPatterns({ "WebKit"}) };
+ Vector<DFA> combinedDFAs = combine(dfas, 5);
+ EXPECT_EQ(static_cast<size_t>(2), combinedDFAs.size());
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(combinedDFAs[0]));
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(combinedDFAs[1]));
+}
+
+} // namespace TestWebKitAPI
</ins></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAHelpersh"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h (0 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -0,0 +1,67 @@
</span><ins>+/*
+ * Copyright (C) 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.
+ */
+
+#include <WebCore/CombinedURLFilters.h>
+#include <WebCore/NFA.h>
+#include <WebCore/NFAToDFA.h>
+#include <WebCore/URLFilterParser.h>
+
+using namespace WebCore;
+
+namespace TestWebKitAPI {
+
+static unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
+{
+ unsigned counter = 0;
+ for (const auto& node : dfa.nodes) {
+ if (!node.isKilled())
+ ++counter;
+ }
+ return counter;
+}
+
+static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
+{
+ Vector<ContentExtensions::NFA> nfas;
+
+ combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
+ nfas.append(WTF::move(nfa));
+ });
+
+ return nfas;
+}
+
+static ContentExtensions::DFA buildDFAFromPatterns(Vector<const char*> patterns)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+
+ for (const char* pattern : patterns)
+ parser.addPattern(pattern, false, 0);
+ Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
+ return ContentExtensions::NFAToDFA::convert(nfas[0]);
+}
+
+} // namespace TestWebKitAPI
</ins></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreDFAMinimizercpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (185229 => 185230)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-06-05 00:31:07 UTC (rev 185229)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-06-05 01:01:59 UTC (rev 185230)
</span><span class="lines">@@ -25,14 +25,9 @@
</span><span class="cx">
</span><span class="cx"> #include "config.h"
</span><span class="cx">
</span><del>-#include <WebCore/CombinedURLFilters.h>
-#include <WebCore/NFA.h>
-#include <WebCore/NFAToDFA.h>
-#include <WebCore/URLFilterParser.h>
</del><ins>+#include "DFAHelpers.h"
</ins><span class="cx"> #include <wtf/MainThread.h>
</span><span class="cx">
</span><del>-using namespace WebCore;
-
</del><span class="cx"> namespace TestWebKitAPI {
</span><span class="cx">
</span><span class="cx"> class DFAMinimizerTest : public testing::Test {
</span><span class="lines">@@ -43,38 +38,6 @@
</span><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-static unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
-{
- unsigned counter = 0;
- for (const auto& node : dfa.nodes) {
- if (!node.isKilled())
- ++counter;
- }
- return counter;
-}
-
-static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
-{
- Vector<ContentExtensions::NFA> nfas;
-
- combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
- nfas.append(WTF::move(nfa));
- });
-
- return nfas;
-}
-
-ContentExtensions::DFA buildDFAFromPatterns(Vector<const char*> patterns)
-{
- ContentExtensions::CombinedURLFilters combinedURLFilters;
- ContentExtensions::URLFilterParser parser(combinedURLFilters);
-
- for (const char* pattern : patterns)
- parser.addPattern(pattern, false, 0);
- Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
- return ContentExtensions::NFAToDFA::convert(nfas[0]);
-}
-
</del><span class="cx"> TEST_F(DFAMinimizerTest, BasicSearch)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*foo", ".*bar", ".*bang"});
</span></span></pre>
</div>
</div>
</body>
</html>