<!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>[181932] 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/181932">181932</a></dd>
<dt>Author</dt> <dd>achristensen@apple.com</dd>
<dt>Date</dt> <dd>2015-03-24 22:19:42 -0700 (Tue, 24 Mar 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[Content Extensions] Add multi-DFA compiling and interpreting.
https://bugs.webkit.org/show_bug.cgi?id=143010
Reviewed by Benjamin Poulain.
Source/WebCore:
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
Compile multiple NFAs to DFAs.
* contentextensions/ContentExtensionsBackend.cpp:
(WebCore::ContentExtensions::ContentExtensionsBackend::actionsForResourceLoad):
Fixed a bug when there are no non-universal actions.
We still need to report that no ignore-previous-rules was hit to apply the
universal actions which are now accessed through DFABytecodeInterpreter::actionsFromDFARoot
and skipped in DFABytecodeInterpreter::interpret.
* contentextensions/DFABytecodeCompiler.cpp:
(WebCore::ContentExtensions::DFABytecodeCompiler::compile):
Add a header for each DFA.
* contentextensions/DFABytecodeInterpreter.cpp:
(WebCore::ContentExtensions::DFABytecodeInterpreter::actionsFromDFARoot):
(WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
Interpret as many DFAs as there are in the bytecode.
Tools:
* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
(TestWebKitAPI::testRequest):
(TestWebKitAPI::TEST_F):
Add some tests for ignore-previous-rules and large rulesets.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp">trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeInterpretercpp">trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp">trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Source/WebCore/ChangeLog 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -1,3 +1,27 @@
</span><ins>+2015-03-24 Alex Christensen <achristensen@webkit.org>
+
+ [Content Extensions] Add multi-DFA compiling and interpreting.
+ https://bugs.webkit.org/show_bug.cgi?id=143010
+
+ Reviewed by Benjamin Poulain.
+
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ Compile multiple NFAs to DFAs.
+ * contentextensions/ContentExtensionsBackend.cpp:
+ (WebCore::ContentExtensions::ContentExtensionsBackend::actionsForResourceLoad):
+ Fixed a bug when there are no non-universal actions.
+ We still need to report that no ignore-previous-rules was hit to apply the
+ universal actions which are now accessed through DFABytecodeInterpreter::actionsFromDFARoot
+ and skipped in DFABytecodeInterpreter::interpret.
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compile):
+ Add a header for each DFA.
+ * contentextensions/DFABytecodeInterpreter.cpp:
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::actionsFromDFARoot):
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
+ Interpret as many DFAs as there are in the bytecode.
+
</ins><span class="cx"> 2015-03-24 Dan Bernstein <mitz@apple.com>
</span><span class="cx">
</span><span class="cx"> Tried to fix the EWS build.
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -111,16 +111,23 @@
</span><span class="cx"> Vector<unsigned> actionLocations = serializeActions(parsedRuleList, actions);
</span><span class="cx"> Vector<uint64_t> universalActionLocations;
</span><span class="cx">
</span><del>- NFA nfa;
- URLFilterParser urlFilterParser(nfa);
</del><ins>+ Vector<NFA> nfas;
+ nfas.append(NFA());
</ins><span class="cx"> bool nonUniversalActionSeen = false;
</span><span class="cx"> for (unsigned ruleIndex = 0; ruleIndex < parsedRuleList.size(); ++ruleIndex) {
</span><ins>+
+ // FIXME: Tune this better and adjust ContentExtensionTest.MultiDFA accordingly.
+ if (nfas[nfas.size() - 1].graphSize() > 500)
+ nfas.append(NFA());
+
+ NFA& lastNFA = nfas[nfas.size() - 1];
+ URLFilterParser urlFilterParser(lastNFA);
</ins><span class="cx"> const ContentExtensionRule& contentExtensionRule = parsedRuleList[ruleIndex];
</span><span class="cx"> const Trigger& trigger = contentExtensionRule.trigger();
</span><span class="cx"> ASSERT(trigger.urlFilter.length());
</span><span class="cx">
</span><span class="cx"> // High bits are used for flags. This should match how they are used in DFABytecodeCompiler::compileNode.
</span><del>- uint64_t actionLocationAndFlags =(static_cast<uint64_t>(trigger.flags) << 32) | static_cast<uint64_t>(actionLocations[ruleIndex]);
</del><ins>+ uint64_t actionLocationAndFlags = (static_cast<uint64_t>(trigger.flags) << 32) | static_cast<uint64_t>(actionLocations[ruleIndex]);
</ins><span class="cx"> URLFilterParser::ParseStatus status = urlFilterParser.addPattern(trigger.urlFilter, trigger.urlFilterIsCaseSensitive, actionLocationAndFlags);
</span><span class="cx">
</span><span class="cx"> if (status == URLFilterParser::MatchesEverything) {
</span><span class="lines">@@ -149,9 +156,17 @@
</span><span class="cx"> double dfaBuildTimeStart = monotonicallyIncreasingTime();
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- DFA dfa = NFAToDFA::convert(nfa);
- for (uint64_t actionLocation : universalActionLocations)
- dfa.nodeAt(dfa.root()).actions.append(actionLocation);
</del><ins>+ Vector<DFABytecode> bytecode;
+ for (size_t i = 0; i < nfas.size(); ++i) {
+ DFA dfa = NFAToDFA::convert(nfas[i]);
+ if (!i) {
+ // Put all the universal actions on the first DFA.
+ for (uint64_t actionLocation : universalActionLocations)
+ dfa.nodeAt(dfa.root()).actions.append(actionLocation);
+ }
+ DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ }
</ins><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> double dfaBuildTimeEnd = monotonicallyIncreasingTime();
</span><span class="lines">@@ -164,10 +179,6 @@
</span><span class="cx"> dfa.debugPrintDot();
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- Vector<DFABytecode> bytecode;
- DFABytecodeCompiler compiler(dfa, bytecode);
- compiler.compile();
-
</del><span class="cx"> return { WTF::move(bytecode), WTF::move(actions) };
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionsBackendcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -80,6 +80,7 @@
</span><span class="cx"> const SerializedActionByte* actions = compiledExtension.actions();
</span><span class="cx"> const unsigned actionsLength = compiledExtension.actionsLength();
</span><span class="cx">
</span><ins>+ bool sawIgnorePreviousRules = false;
</ins><span class="cx"> if (!triggeredActions.isEmpty()) {
</span><span class="cx"> Vector<unsigned> actionLocations;
</span><span class="cx"> actionLocations.reserveInitialCapacity(triggeredActions.size());
</span><span class="lines">@@ -87,8 +88,6 @@
</span><span class="cx"> actionLocations.append(static_cast<unsigned>(actionLocation));
</span><span class="cx"> std::sort(actionLocations.begin(), actionLocations.end());
</span><span class="cx">
</span><del>- bool sawIgnorePreviousRules = false;
-
</del><span class="cx"> // Add actions in reverse order to properly deal with IgnorePreviousRules.
</span><span class="cx"> for (unsigned i = actionLocations.size(); i; i--) {
</span><span class="cx"> Action action = Action::deserialize(actions, actionsLength, actionLocations[i - 1]);
</span><span class="lines">@@ -98,10 +97,9 @@
</span><span class="cx"> }
</span><span class="cx"> finalActions.append(action);
</span><span class="cx"> }
</span><del>-
- if (!sawIgnorePreviousRules)
- finalActions.append(Action(ActionType::CSSDisplayNoneStyleSheet, contentExtension->identifier()));
</del><span class="cx"> }
</span><ins>+ if (!sawIgnorePreviousRules)
+ finalActions.append(Action(ActionType::CSSDisplayNoneStyleSheet, contentExtension->identifier()));
</ins><span class="cx"> }
</span><span class="cx"> return finalActions;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -167,7 +167,9 @@
</span><span class="cx">
</span><span class="cx"> void DFABytecodeCompiler::compile()
</span><span class="cx"> {
</span><del>- ASSERT(!m_bytecode.size());
</del><ins>+ // DFA header.
+ unsigned startLocation = m_bytecode.size();
+ append<unsigned>(m_bytecode, 0);
</ins><span class="cx"> m_nodeStartOffsets.resize(m_dfa.size());
</span><span class="cx">
</span><span class="cx"> // Make sure the root is always at the beginning of the bytecode.
</span><span class="lines">@@ -180,6 +182,9 @@
</span><span class="cx"> // Link.
</span><span class="cx"> for (const auto& linkRecord : m_linkRecords)
</span><span class="cx"> set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
</span><ins>+
+ // Set size header.
+ set32Bits(m_bytecode, startLocation, m_bytecode.size() - startLocation);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeInterpretercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -43,13 +43,15 @@
</span><span class="cx">
</span><span class="cx"> DFABytecodeInterpreter::Actions DFABytecodeInterpreter::actionsFromDFARoot()
</span><span class="cx"> {
</span><del>- unsigned programCounter = 0;
- DFABytecodeInterpreter::Actions globalActionLocations;
</del><ins>+ DFABytecodeInterpreter::Actions universalActionLocations;
+
+ // Skip first DFA header. All universal actions are in the first DFA root.
+ unsigned programCounter = sizeof(unsigned);
</ins><span class="cx"> while (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter]) == DFABytecodeInstruction::AppendAction) {
</span><del>- globalActionLocations.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
</del><ins>+ universalActionLocations.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
</ins><span class="cx"> programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
</span><span class="cx"> }
</span><del>- return globalActionLocations;
</del><ins>+ return universalActionLocations;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpret(const CString& urlCString, uint16_t flags)
</span><span class="lines">@@ -57,78 +59,92 @@
</span><span class="cx"> const char* url = urlCString.data();
</span><span class="cx"> ASSERT(url);
</span><span class="cx">
</span><del>- unsigned programCounter = 0;
- unsigned urlIndex = 0;
- bool urlIndexIsAfterEndOfString = false;
</del><span class="cx"> Actions actions;
</span><span class="cx">
</span><del>- while (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter]) == DFABytecodeInstruction::AppendAction)
- programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
</del><ins>+ unsigned programCounter = 0;
+ while (programCounter < m_bytecodeLength) {
</ins><span class="cx">
</span><del>- // This should always terminate if interpreting correctly compiled bytecode.
- while (true) {
- ASSERT(programCounter <= m_bytecodeLength);
- switch (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter])) {
</del><ins>+ // DFA header.
+ unsigned dfaStart = programCounter;
+ unsigned dfaBytecodeLength = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter);
+ programCounter += sizeof(unsigned);
</ins><span class="cx">
</span><del>- case DFABytecodeInstruction::Terminate:
- return actions;
</del><ins>+ // Skip the universal actions.
+ // FIXME: Replace AppendAction with AppendActions to make this just one jump and make sure there aren't universal actions with flags.
+ while (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter]) == DFABytecodeInstruction::AppendAction)
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
+
+ // Interpret the bytecode from this DFA.
+ // This should always terminate if interpreting correctly compiled bytecode.
+ unsigned urlIndex = 0;
+ bool urlIndexIsAfterEndOfString = false;
+ while (true) {
+ ASSERT(programCounter <= m_bytecodeLength);
+ switch (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter])) {
</ins><span class="cx">
</span><del>- case DFABytecodeInstruction::CheckValue:
- if (urlIndexIsAfterEndOfString)
- return actions;
</del><ins>+ case DFABytecodeInstruction::Terminate:
+ goto nextDFA;
+
+ case DFABytecodeInstruction::CheckValue:
+ if (urlIndexIsAfterEndOfString)
+ goto nextDFA;
</ins><span class="cx">
</span><del>- // Check to see if the next character in the url is the value stored with the bytecode.
- if (url[urlIndex] == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))) {
- programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t));
- if (!url[urlIndex])
- urlIndexIsAfterEndOfString = true;
- urlIndex++; // This represents an edge in the DFA.
- } else
- programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValue);
- break;
</del><ins>+ // Check to see if the next character in the url is the value stored with the bytecode.
+ if (url[urlIndex] == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))) {
+ programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t));
+ if (!url[urlIndex])
+ urlIndexIsAfterEndOfString = true;
+ urlIndex++; // This represents an edge in the DFA.
+ } else
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValue);
+ break;
+
+ case DFABytecodeInstruction::CheckValueRange: {
+ if (urlIndexIsAfterEndOfString)
+ goto nextDFA;
+
+ char character = url[urlIndex];
+ if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))
+ && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t))) {
+ programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t) + sizeof(uint8_t));
+ if (!character)
+ urlIndexIsAfterEndOfString = true;
+ urlIndex++; // This represents an edge in the DFA.
+ } else
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValueRange);
+ break;
+ }
</ins><span class="cx">
</span><del>- case DFABytecodeInstruction::CheckValueRange: {
- if (urlIndexIsAfterEndOfString)
- return actions;
-
- char character = url[urlIndex];
- if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))
- && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t))) {
- programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t) + sizeof(uint8_t));
- if (!character)
- urlIndexIsAfterEndOfString = true;
</del><ins>+ case DFABytecodeInstruction::Jump:
+ if (!url[urlIndex] || urlIndexIsAfterEndOfString)
+ goto nextDFA;
+
+ programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode));
</ins><span class="cx"> urlIndex++; // This represents an edge in the DFA.
</span><del>- } else
- programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValueRange);
- break;
</del><ins>+ break;
+
+ case DFABytecodeInstruction::AppendAction:
+ actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
+ break;
+
+ case DFABytecodeInstruction::TestFlagsAndAppendAction:
+ if (flags & getBits<uint16_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode)))
+ actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint16_t))));
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
+ break;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
+ }
+ // We should always terminate before or at a null character at the end of a String.
+ ASSERT(urlIndex <= urlCString.length() || (urlIndexIsAfterEndOfString && urlIndex <= urlCString.length() + 1));
</ins><span class="cx"> }
</span><del>-
- case DFABytecodeInstruction::Jump:
- if (!url[urlIndex] || urlIndexIsAfterEndOfString)
- return actions;
-
- programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode));
- urlIndex++; // This represents an edge in the DFA.
- break;
-
- case DFABytecodeInstruction::AppendAction:
- actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
- programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
- break;
-
- case DFABytecodeInstruction::TestFlagsAndAppendAction:
- if (flags & getBits<uint16_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode)))
- actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint16_t))));
- programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
- break;
-
- default:
- RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
- }
- // We should always terminate before or at a null character at the end of a String.
- ASSERT(urlIndex <= urlCString.length() || (urlIndexIsAfterEndOfString && urlIndex <= urlCString.length() + 1));
</del><ins>+ nextDFA:
+ ASSERT(dfaBytecodeLength);
+ programCounter = dfaStart + dfaBytecodeLength;
</ins><span class="cx"> }
</span><del>- RELEASE_ASSERT_NOT_REACHED();
</del><ins>+ return actions;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Tools/ChangeLog 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -1,3 +1,15 @@
</span><ins>+2015-03-24 Alex Christensen <achristensen@webkit.org>
+
+ [Content Extensions] Add multi-DFA compiling and interpreting.
+ https://bugs.webkit.org/show_bug.cgi?id=143010
+
+ Reviewed by Benjamin Poulain.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::testRequest):
+ (TestWebKitAPI::TEST_F):
+ Add some tests for ignore-previous-rules and large rulesets.
+
</ins><span class="cx"> 2015-03-24 Benjamin Poulain <bpoulain@apple.com>
</span><span class="cx">
</span><span class="cx"> Make URL filter patterns matching consistent and add a simple canonicalization step
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWebCoreContentExtensionscpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (181931 => 181932)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-03-25 05:12:49 UTC (rev 181931)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-03-25 05:19:42 UTC (rev 181932)
</span><span class="lines">@@ -36,6 +36,7 @@
</span><span class="cx"> #include <wtf/MainThread.h>
</span><span class="cx"> #include <wtf/RunLoop.h>
</span><span class="cx"> #include <wtf/text/CString.h>
</span><ins>+#include <wtf/text/StringBuilder.h>
</ins><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="cx"> namespace ContentExtensions {
</span><span class="lines">@@ -98,16 +99,22 @@
</span><span class="cx"> ContentExtensions::CompiledContentExtensionData m_data;
</span><span class="cx"> };
</span><span class="cx">
</span><del>-void static testRequest(ContentExtensions::ContentExtensionsBackend contentExtensionsBackend, const ResourceLoadInfo& resourceLoadInfo, Vector<ContentExtensions::ActionType> expectedActions)
</del><ins>+void static testRequest(ContentExtensions::ContentExtensionsBackend contentExtensionsBackend, const ResourceLoadInfo& resourceLoadInfo, Vector<ContentExtensions::ActionType> expectedActions, bool ignorePreviousRules = false)
</ins><span class="cx"> {
</span><span class="cx"> auto actions = contentExtensionsBackend.actionsForResourceLoad(resourceLoadInfo);
</span><del>- // The last action is applying the compiled stylesheet.
- EXPECT_EQ(expectedActions.size(), actions.size() ? actions.size() - 1 : 0);
- if (expectedActions.size() != (actions.size() ? actions.size() - 1 : 0))
</del><ins>+
+ unsigned expectedSize = actions.size();
+ if (actions.size() && !ignorePreviousRules)
+ expectedSize--; // The last action is applying the compiled stylesheet.
+
+ EXPECT_EQ(expectedActions.size(), expectedSize);
+ if (expectedActions.size() != expectedSize)
</ins><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < expectedActions.size(); ++i)
</span><span class="cx"> EXPECT_EQ(expectedActions[i], actions[i].type());
</span><ins>+ if (!ignorePreviousRules)
+ EXPECT_EQ(actions[actions.size() - 1].type(), ContentExtensions::ActionType::CSSDisplayNoneStyleSheet);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ResourceLoadInfo mainDocumentRequest(const char* url, ResourceType resourceType = ResourceType::Document)
</span><span class="lines">@@ -510,6 +517,47 @@
</span><span class="cx"> testRequest(backend, mainDocumentRequest("http://block_only_images.org", ResourceType::Document), { });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST_F(ContentExtensionTest, MultiDFA)
+{
+ // Make an NFA with about 2000 nodes.
+ StringBuilder ruleList;
+ ruleList.append('[');
+ for (char c1 = 'A'; c1 <= 'Z'; ++c1) {
+ for (char c2 = 'A'; c2 <= 'Z'; ++c2) {
+ for (char c3 = 'A'; c3 <= 'C'; ++c3) {
+ if (c1 != 'A' || c2 != 'A' || c3 != 'A')
+ ruleList.append(',');
+ ruleList.append("{\"action\":{\"type\":\"");
+
+ // Put an ignore-previous-rules near the middle.
+ if (c1 == 'L' && c2 == 'L' && c3 == 'A')
+ ruleList.append("ignore-previous-rules");
+ else
+ ruleList.append("block");
+
+ ruleList.append("\"},\"trigger\":{\"url-filter\":\".*");
+ ruleList.append(c1);
+ ruleList.append(c2);
+ ruleList.append(c3);
+ ruleList.append("\", \"url-filter-is-case-sensitive\":true}}");
+ }
+ }
+ }
+ ruleList.append(']');
+
+ auto extensionData = ContentExtensions::compileRuleList(ruleList.toString());
+ auto extension = InMemoryCompiledContentExtension::create(WTF::move(extensionData));
+
+ ContentExtensions::ContentExtensionsBackend backend;
+ backend.addContentExtension("ResourceTypeFilter", extension);
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/AAA"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/ZZC"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/LLA/AAA"), { }, true);
+ testRequest(backend, mainDocumentRequest("http://webkit.org/LLA/MMC"), { ContentExtensions::ActionType::BlockLoad }, true);
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+}
+
</ins><span class="cx"> static void testPatternStatus(String pattern, ContentExtensions::URLFilterParser::ParseStatus status)
</span><span class="cx"> {
</span><span class="cx"> ContentExtensions::NFA nfa;
</span></span></pre>
</div>
</div>
</body>
</html>