Diff
Modified: trunk/Source/WebCore/ChangeLog (181662 => 181663)
--- trunk/Source/WebCore/ChangeLog 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/ChangeLog 2015-03-17 20:47:42 UTC (rev 181663)
@@ -1,3 +1,48 @@
+2015-03-17 Benjamin Poulain <[email protected]>
+
+ Compile character ranges targeting the same state as range check in the bytecode
+ https://bugs.webkit.org/show_bug.cgi?id=142759
+
+ Reviewed by Alex Christensen.
+
+ Previously, character ranges would be compiled as many individual character checks.
+ For example, a transition on "[a-z]" would do 26 character checks + jump, which leads
+ to enormous matchines.
+
+ With this patch, we find the ranges at lowering time and generate a single instruction
+ for them: "CheckValueRange". This helps making the machine denser when the input
+ use character sets.
+
+ The second part of this patch goes further in the case where the transitions out of
+ a state cover the entire alphabet. In that case, we create a fallback transition
+ on the fly and remove all the ranges made useless.
+ That case is common when ranges are used with inverse character set (e.g. [^a]+a).
+
+ * contentextensions/DFABytecode.h:
+ (WebCore::ContentExtensions::instructionSizeWithArguments):
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::emitCheckValueRange):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileCheckForRange):
+ * contentextensions/DFABytecodeCompiler.h:
+ Extend the compiler to detect ranges and lower them as CheckValueRange.
+
+ * contentextensions/DFABytecodeInterpreter.cpp:
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
+ Range checks in the interpreter.
+
+ * contentextensions/NFA.cpp:
+ (WebCore::ContentExtensions::NFA::setFinal):
+ This assertion does not make sense with the current codebase. Actions are "compressed",
+ it is possible to have two patterns with the same action.
+
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::simplifyTransitions):
+ A very simple DFA optimization function: it only reduce the strength of ranges.
+
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+
2015-03-17 Jer Noble <[email protected]>
REGRESSION (r181423): Crash @ generatedcontent.org at com.apple.WebCore: WebCore::MediaPlayer::maximumDurationToCacheMediaTime const + 4
Modified: trunk/Source/WebCore/contentextensions/DFABytecode.h (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/DFABytecode.h 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/DFABytecode.h 2015-03-17 20:47:42 UTC (rev 181663)
@@ -41,6 +41,12 @@
// The index to jump to if the values are equal (4 bytes).
CheckValue,
+ // Jump to an offset if the input value is within a certain range.
+ // The lower value (1 byte).
+ // The higher value (1 byte).
+ // The index to jump to if the value is in the range (4 bytes).
+ CheckValueRange,
+
// AppendAction has one argument:
// The action to append (4 bytes).
AppendAction,
@@ -63,6 +69,8 @@
switch (instruction) {
case DFABytecodeInstruction::CheckValue:
return sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + sizeof(unsigned);
+ case DFABytecodeInstruction::CheckValueRange:
+ return sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + sizeof(uint8_t) + sizeof(unsigned);
case DFABytecodeInstruction::AppendAction:
return sizeof(DFABytecodeInstruction) + sizeof(unsigned);
case DFABytecodeInstruction::TestFlagsAndAppendAction:
Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-03-17 20:47:42 UTC (rev 181663)
@@ -30,6 +30,7 @@
#include "ContentExtensionRule.h"
#include "DFA.h"
+#include "DFANode.h"
namespace WebCore {
@@ -76,6 +77,18 @@
append<unsigned>(m_bytecode, 0); // This value will be set when linking.
}
+void DFABytecodeCompiler::emitCheckValueRange(uint8_t lowValue, uint8_t highValue, unsigned destinationNodeIndex)
+{
+ ASSERT_WITH_MESSAGE(lowValue != highValue, "A single value check should be emitted for single values.");
+ ASSERT_WITH_MESSAGE(lowValue < highValue, "The instruction semantic impose lowValue is smaller than highValue.");
+
+ append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::CheckValueRange);
+ append<uint8_t>(m_bytecode, lowValue);
+ append<uint8_t>(m_bytecode, highValue);
+ m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
+ append<unsigned>(m_bytecode, 0);
+}
+
void DFABytecodeCompiler::emitTerminate()
{
append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Terminate);
@@ -95,16 +108,63 @@
else
emitAppendAction(static_cast<unsigned>(action));
}
-
- for (const auto& transition : node.transitions)
- emitCheckValue(transition.key, transition.value);
-
+ compileNodeTransitions(node);
+}
+
+void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)
+{
+ bool hasRangeMin = false;
+ uint16_t rangeMin;
+ unsigned rangeDestination = 0;
+
+ for (unsigned char i = 0; i < 128; ++i) {
+ auto transitionIterator = node.transitions.find(i);
+ if (transitionIterator == node.transitions.end()) {
+ if (hasRangeMin) {
+ ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == rangeDestination), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
+
+ unsigned char lastHighValue = i - 1;
+ compileCheckForRange(rangeMin, lastHighValue, rangeDestination);
+ hasRangeMin = false;
+ }
+ continue;
+ }
+
+ if (!hasRangeMin) {
+ hasRangeMin = true;
+ rangeMin = transitionIterator->key;
+ rangeDestination = transitionIterator->value;
+ } else {
+ if (transitionIterator->value == rangeDestination)
+ continue;
+
+ unsigned char lastHighValue = i - 1;
+ compileCheckForRange(rangeMin, lastHighValue, rangeDestination);
+ rangeMin = i;
+ rangeDestination = transitionIterator->value;
+ }
+ }
+ if (hasRangeMin)
+ compileCheckForRange(rangeMin, 127, rangeDestination);
+
if (node.hasFallbackTransition)
emitJump(node.fallbackTransition);
else
emitTerminate();
}
-
+
+void DFABytecodeCompiler::compileCheckForRange(uint16_t lowValue, uint16_t highValue, unsigned destinationNodeIndex)
+{
+ ASSERT_WITH_MESSAGE(lowValue < 128, "The DFA engine only supports the ASCII alphabet.");
+ ASSERT_WITH_MESSAGE(highValue < 128, "The DFA engine only supports the ASCII alphabet.");
+ ASSERT(lowValue <= highValue);
+
+ if (lowValue == highValue)
+ emitCheckValue(lowValue, destinationNodeIndex);
+ else
+ emitCheckValueRange(lowValue, highValue, destinationNodeIndex);
+}
+
void DFABytecodeCompiler::compile()
{
ASSERT(!m_bytecode.size());
Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-03-17 20:47:42 UTC (rev 181663)
@@ -29,7 +29,6 @@
#if ENABLE(CONTENT_EXTENSIONS)
#include "DFABytecode.h"
-#include "DFANode.h"
#include <wtf/Vector.h>
namespace WebCore {
@@ -37,6 +36,7 @@
namespace ContentExtensions {
class DFA;
+class DFANode;
class DFABytecodeCompiler {
public:
@@ -50,11 +50,14 @@
private:
void compileNode(unsigned);
+ void compileNodeTransitions(const DFANode&);
+ void compileCheckForRange(uint16_t lowValue, uint16_t highValue, unsigned destinationNodeIndex);
void emitAppendAction(unsigned);
void emitTestFlagsAndAppendAction(uint16_t flags, unsigned);
void emitJump(unsigned destinationNodeIndex);
void emitCheckValue(uint8_t value, unsigned destinationNodeIndex);
+ void emitCheckValueRange(uint8_t lowValue, uint8_t highValue, unsigned destinationNodeIndex);
void emitTerminate();
Vector<DFABytecode>& m_bytecode;
Modified: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-03-17 20:47:42 UTC (rev 181663)
@@ -73,6 +73,22 @@
programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValue);
break;
+ 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;
+ urlIndex++; // This represents an edge in the DFA.
+ } else
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValueRange);
+ break;
+ }
+
case DFABytecodeInstruction::Jump:
if (!url[urlIndex] || urlIndexIsAfterEndOfString)
return actions;
Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-03-17 20:47:42 UTC (rev 181663)
@@ -83,8 +83,8 @@
void NFA::setFinal(unsigned node, uint64_t ruleId)
{
- ASSERT(!m_nodes[node].finalRuleIds.contains(ruleId));
- m_nodes[node].finalRuleIds.append(ruleId);
+ if (!m_nodes[node].finalRuleIds.contains(ruleId))
+ m_nodes[node].finalRuleIds.append(ruleId);
}
unsigned NFA::graphSize() const
Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (181662 => 181663)
--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2015-03-17 20:47:42 UTC (rev 181663)
@@ -338,6 +338,49 @@
return uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
}
+static void simplifyTransitions(Vector<DFANode>& dfaGraph)
+{
+ for (DFANode& dfaNode : dfaGraph) {
+ if (!dfaNode.hasFallbackTransition
+ && ((dfaNode.transitions.size() == 126 && !dfaNode.transitions.contains(0))
+ || (dfaNode.transitions.size() == 127 && dfaNode.transitions.contains(0)))) {
+ unsigned bestTarget = std::numeric_limits<unsigned>::max();
+ unsigned bestTargetScore = 0;
+ HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;
+ for (const auto transition : dfaNode.transitions) {
+ if (!transition.key)
+ continue;
+
+ unsigned transitionTarget = transition.value;
+ auto addResult = targetHistogram.add(transitionTarget, 1);
+ if (!addResult.isNewEntry)
+ addResult.iterator->value++;
+
+ if (addResult.iterator->value > bestTargetScore) {
+ bestTargetScore = addResult.iterator->value;
+ bestTarget = transitionTarget;
+ }
+ }
+ ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");
+
+ dfaNode.hasFallbackTransition = true;
+ dfaNode.fallbackTransition = bestTarget;
+ }
+
+ if (dfaNode.hasFallbackTransition) {
+ Vector<uint16_t, 128> keys;
+ DFANodeTransitions& transitions = dfaNode.transitions;
+ copyKeysToVector(transitions, keys);
+
+ for (uint16_t key : keys) {
+ auto transitionIterator = transitions.find(key);
+ if (transitionIterator->value == dfaNode.fallbackTransition)
+ transitions.remove(transitionIterator);
+ }
+ }
+ }
+}
+
DFA NFAToDFA::convert(NFA& nfa)
{
Vector<NFANode>& nfaGraph = nfa.m_nodes;
@@ -387,6 +430,7 @@
}
} while (!unprocessedNodes.isEmpty());
+ simplifyTransitions(dfaGraph);
return DFA(WTF::move(dfaGraph), 0);
}
Modified: trunk/Tools/ChangeLog (181662 => 181663)
--- trunk/Tools/ChangeLog 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Tools/ChangeLog 2015-03-17 20:47:42 UTC (rev 181663)
@@ -1,3 +1,13 @@
+2015-03-17 Benjamin Poulain <[email protected]>
+
+ Compile character ranges targeting the same state as range check in the bytecode
+ https://bugs.webkit.org/show_bug.cgi?id=142759
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::TEST_F):
+
2015-03-17 Youenn Fablet <[email protected]>
W3C test parser and converter should use test importer host
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (181662 => 181663)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-03-17 20:28:33 UTC (rev 181662)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-03-17 20:47:42 UTC (rev 181663)
@@ -122,6 +122,56 @@
testRequest(backend, mainDocumentRequest("http://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
}
+TEST_F(ContentExtensionTest, RangeBasic)
+{
+ const char* rangeBasicFilter = "[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".*w[0-9]c\", \"url-filter-is-case-sensitive\":true}},{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\".*[A-H][a-z]cko\", \"url-filter-is-case-sensitive\":true}}]";
+ auto extensionData = ContentExtensions::compileRuleList(rangeBasicFilter);
+ auto extension = InMemoryCompiledContentExtension::create(WTF::move(extensionData));
+
+ ContentExtensions::ContentExtensionsBackend backend;
+ backend.addContentExtension("PatternNestedGroupsFilter", extension);
+
+ testRequest(backend, mainDocumentRequest("http://w3c.org"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("w2c://whatwg.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/w0c"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/wac"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/wAc"), { });
+
+ // Note: URL parsing and canonicalization lowercase the scheme and hostname.
+ testRequest(backend, mainDocumentRequest("Aacko://webkit.org"), { });
+ testRequest(backend, mainDocumentRequest("aacko://webkit.org"), { });
+ testRequest(backend, mainDocumentRequest("http://gCcko.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://gccko.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/Gecko"), { ContentExtensions::ActionType::BlockCookies });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/gecko"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/GEcko"), { });
+}
+
+TEST_F(ContentExtensionTest, RangeExclusionGeneratingUniversalTransition)
+{
+ // Transition of the type ([^X]X) effictively transition on every input.
+ const char* rangeExclusionGeneratingUniversalTransitionFilter = "[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".*[^a]+afoobar\"}}]";
+ auto extensionData = ContentExtensions::compileRuleList(rangeExclusionGeneratingUniversalTransitionFilter);
+ auto extension = InMemoryCompiledContentExtension::create(WTF::move(extensionData));
+
+ ContentExtensions::ContentExtensionsBackend backend;
+ backend.addContentExtension("PatternNestedGroupsFilter", extension);
+
+ testRequest(backend, mainDocumentRequest("http://w3c.org"), { });
+
+ testRequest(backend, mainDocumentRequest("http://w3c.org/foobafoobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/foobarfoobar"), { });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/FOOBAFOOBAR"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/FOOBARFOOBAR"), { });
+
+ // The character before the "a" prefix cannot be another "a".
+ testRequest(backend, mainDocumentRequest("http://w3c.org/aafoobar"), { });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/Aafoobar"), { });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/aAfoobar"), { });
+ testRequest(backend, mainDocumentRequest("http://w3c.org/AAfoobar"), { });
+}
+
const char* patternsStartingWithGroupFilter = "[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"(http://whatwg\\\\.org/)?webkit\134\134.org\"}}]";
TEST_F(ContentExtensionTest, PatternStartingWithGroup)
@@ -219,6 +269,26 @@
testRequest(backend, mainDocumentRequest("http://webkit.org/foobarfoo"), { });
testRequest(backend, mainDocumentRequest("http://webkit.org/foobarf"), { });
}
+
+TEST_F(ContentExtensionTest, EndOfLineAssertionWithInvertedCharacterSet)
+{
+ const char* endOfLineAssertionWithInvertedCharacterSetFilter = "[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".*[^y]$\"}}]";
+ auto extensionData = ContentExtensions::compileRuleList(endOfLineAssertionWithInvertedCharacterSetFilter);
+ auto extension = InMemoryCompiledContentExtension::create(WTF::move(extensionData));
+
+ ContentExtensions::ContentExtensionsBackend backend;
+ backend.addContentExtension("EndOfLineAssertion", extension);
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/a"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/Ya"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/yFoobar"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/y"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/Y"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foobary"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/foobarY"), { });
+}
const char* loadTypeFilter = "[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".*webkit.org\",\"load-type\":[\"third-party\"]}},"
"{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\".*whatwg.org\",\"load-type\":[\"first-party\"]}},"
