Diff
Modified: trunk/Source/WebCore/ChangeLog (180768 => 180769)
--- trunk/Source/WebCore/ChangeLog 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/ChangeLog 2015-02-27 19:20:27 UTC (rev 180769)
@@ -1,3 +1,41 @@
+2015-02-27 Alex Christensen <achristen...@webkit.org>
+
+ Compile DFA to bytecode.
+ https://bugs.webkit.org/show_bug.cgi?id=142031
+
+ Reviewed by Benjamin Poulain.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/ContentExtensionsBackend.cpp:
+ (WebCore::ContentExtensions::ContentExtensionsBackend::setRuleList):
+ (WebCore::ContentExtensions::ContentExtensionsBackend::shouldBlockURL):
+ * contentextensions/ContentExtensionsBackend.h:
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::nextState): Deleted.
+ (WebCore::ContentExtensions::DFA::actions): Deleted.
+ * contentextensions/DFA.h:
+ (WebCore::ContentExtensions::DFA::size):
+ (WebCore::ContentExtensions::DFA::nodeAt):
+ * contentextensions/DFABytecode.h: Added.
+ (WebCore::ContentExtensions::instructionSizeWithArguments):
+ * contentextensions/DFABytecodeCompiler.cpp: Added.
+ (WebCore::ContentExtensions::append):
+ (WebCore::ContentExtensions::set32Bits):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::emitAppendAction):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::emitJump):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::emitCheckValue):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::emitTerminate):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::reserveBufferCapacity):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compile):
+ * contentextensions/DFABytecodeCompiler.h: Added.
+ (WebCore::ContentExtensions::DFABytecodeCompiler::DFABytecodeCompiler):
+ * contentextensions/DFABytecodeInterpreter.cpp: Added.
+ (WebCore::ContentExtensions::getBits):
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
+ * contentextensions/DFABytecodeInterpreter.h: Added.
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::DFABytecodeInterpreter):
+
2015-02-27 Zalan Bujtas <za...@apple.com>
Use after free in WebCore::RenderNamedFlowFragment::restoreRegionObjectsOriginalStyle
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (180768 => 180769)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-02-27 19:20:27 UTC (rev 180769)
@@ -2142,6 +2142,11 @@
5C4304B1191AC908000E2BC0 /* EXTShaderTextureLOD.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C4304AE191AC908000E2BC0 /* EXTShaderTextureLOD.h */; };
5C4304B5191AEF46000E2BC0 /* JSEXTShaderTextureLOD.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5C4304B3191AEF46000E2BC0 /* JSEXTShaderTextureLOD.cpp */; };
5C4304B6191AEF46000E2BC0 /* JSEXTShaderTextureLOD.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C4304B4191AEF46000E2BC0 /* JSEXTShaderTextureLOD.h */; };
+ 5C9A7A751AA0F6EA00958ACF /* DFABytecodeCompiler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5C39305E1AA0F6A90029C816 /* DFABytecodeCompiler.cpp */; };
+ 5C9A7A761AA0F6ED00958ACF /* DFABytecodeInterpreter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5C3930601AA0F6A90029C816 /* DFABytecodeInterpreter.cpp */; };
+ 5CD9F5661AA0F73C00DA45FF /* DFABytecode.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C39305D1AA0F6A90029C816 /* DFABytecode.h */; };
+ 5CD9F5671AA0F74200DA45FF /* DFABytecodeCompiler.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */; };
+ 5CD9F5681AA0F74600DA45FF /* DFABytecodeInterpreter.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */; };
5CFC4350192409E300A0D3B5 /* PointerLockController.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5CFC434E192406A900A0D3B5 /* PointerLockController.cpp */; };
5D21A80213ECE5DF00BB7064 /* WebVTTParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5D21A80013ECE5DF00BB7064 /* WebVTTParser.cpp */; };
5D21A80313ECE5DF00BB7064 /* WebVTTParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 5D21A80113ECE5DF00BB7064 /* WebVTTParser.h */; };
@@ -9286,6 +9291,11 @@
5B30695A18B3D3450099D5E8 /* WebGLDrawBuffers.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = WebGLDrawBuffers.cpp; path = canvas/WebGLDrawBuffers.cpp; sourceTree = "<group>"; };
5B30695B18B3D3450099D5E8 /* WebGLDrawBuffers.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = WebGLDrawBuffers.h; path = canvas/WebGLDrawBuffers.h; sourceTree = "<group>"; };
5B30695C18B3D3450099D5E8 /* WebGLDrawBuffers.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; name = WebGLDrawBuffers.idl; path = canvas/WebGLDrawBuffers.idl; sourceTree = "<group>"; };
+ 5C39305D1AA0F6A90029C816 /* DFABytecode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFABytecode.h; sourceTree = "<group>"; };
+ 5C39305E1AA0F6A90029C816 /* DFABytecodeCompiler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFABytecodeCompiler.cpp; sourceTree = "<group>"; };
+ 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFABytecodeCompiler.h; sourceTree = "<group>"; };
+ 5C3930601AA0F6A90029C816 /* DFABytecodeInterpreter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFABytecodeInterpreter.cpp; sourceTree = "<group>"; };
+ 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFABytecodeInterpreter.h; sourceTree = "<group>"; };
5C4304AD191AC908000E2BC0 /* EXTShaderTextureLOD.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = EXTShaderTextureLOD.cpp; path = canvas/EXTShaderTextureLOD.cpp; sourceTree = "<group>"; };
5C4304AE191AC908000E2BC0 /* EXTShaderTextureLOD.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = EXTShaderTextureLOD.h; path = canvas/EXTShaderTextureLOD.h; sourceTree = "<group>"; };
5C4304AF191AC908000E2BC0 /* EXTShaderTextureLOD.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; name = EXTShaderTextureLOD.idl; path = canvas/EXTShaderTextureLOD.idl; sourceTree = "<group>"; };
@@ -15395,6 +15405,11 @@
26F0C8961A2E724B002794F8 /* ContentExtensionsManager.h */,
267725F61A5B3AD9003C24DD /* DFA.cpp */,
267725F71A5B3AD9003C24DD /* DFA.h */,
+ 5C39305D1AA0F6A90029C816 /* DFABytecode.h */,
+ 5C39305E1AA0F6A90029C816 /* DFABytecodeCompiler.cpp */,
+ 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */,
+ 5C3930601AA0F6A90029C816 /* DFABytecodeInterpreter.cpp */,
+ 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */,
267725F91A5B3AD9003C24DD /* DFANode.h */,
269397251A4A5FBD00E8349D /* NFA.cpp */,
269397231A4A5B6400E8349D /* NFA.h */,
@@ -24068,6 +24083,7 @@
85ECBEEB0AA7626900544F0B /* DOMHTMLAreaElement.h in Headers */,
85E7119C0AC5D5350053270F /* DOMHTMLAreaElementInternal.h in Headers */,
859A9C470AA5E3BD00B694B2 /* DOMHTMLBaseElement.h in Headers */,
+ 5CD9F5681AA0F74600DA45FF /* DFABytecodeInterpreter.h in Headers */,
85E7119D0AC5D5350053270F /* DOMHTMLBaseElementInternal.h in Headers */,
85ECBEED0AA7626900544F0B /* DOMHTMLBaseFontElement.h in Headers */,
85E7119E0AC5D5350053270F /* DOMHTMLBaseFontElementInternal.h in Headers */,
@@ -24547,6 +24563,7 @@
9307F1D80AF2D59000DBA31A /* HitTestResult.h in Headers */,
BC3BC29C0E91AB0F00835588 /* HostWindow.h in Headers */,
FD31609912B026F700C1A359 /* HRTFDatabase.h in Headers */,
+ 5CD9F5671AA0F74200DA45FF /* DFABytecodeCompiler.h in Headers */,
FD31609B12B026F700C1A359 /* HRTFDatabaseLoader.h in Headers */,
FD31609D12B026F700C1A359 /* HRTFElevation.h in Headers */,
FD31609F12B026F700C1A359 /* HRTFKernel.h in Headers */,
@@ -24662,6 +24679,7 @@
A871DC280A15205700B12A68 /* HTMLTitleElement.h in Headers */,
977B3878122883E900B81FF8 /* HTMLTokenizer.h in Headers */,
0707568C142262D600414161 /* HTMLTrackElement.h in Headers */,
+ 5CD9F5661AA0F73C00DA45FF /* DFABytecode.h in Headers */,
977B37261228721700B81FF8 /* HTMLTreeBuilder.h in Headers */,
A8EA79F20A1916DF00A8EF5F /* HTMLUListElement.h in Headers */,
AD49914318F0815100BF0092 /* HTMLUnknownElement.h in Headers */,
@@ -28182,6 +28200,7 @@
B275357B0B053814002CE64F /* ImageMac.mm in Sources */,
2D5A592F152525230036EE51 /* ImageOrientation.cpp in Sources */,
B51A2F4117D7D5DE0072517A /* ImageQualityController.cpp in Sources */,
+ 5C9A7A761AA0F6ED00958ACF /* DFABytecodeInterpreter.cpp in Sources */,
0F3C725E1974874B00AEDD0C /* ImageSource.cpp in Sources */,
B275355F0B053814002CE64F /* ImageSourceCG.cpp in Sources */,
4B3480930EEF50D400AC1B41 /* ImageSourceCGMac.mm in Sources */,
@@ -28713,6 +28732,7 @@
B2FA3D3A0AB75A6F000E5AC4 /* JSSVGAnimatedBoolean.cpp in Sources */,
B2FA3D3C0AB75A6F000E5AC4 /* JSSVGAnimatedEnumeration.cpp in Sources */,
B2FA3D3E0AB75A6F000E5AC4 /* JSSVGAnimatedInteger.cpp in Sources */,
+ 5C9A7A751AA0F6EA00958ACF /* DFABytecodeCompiler.cpp in Sources */,
B2FA3D400AB75A6F000E5AC4 /* JSSVGAnimatedLength.cpp in Sources */,
B2FA3D420AB75A6F000E5AC4 /* JSSVGAnimatedLengthList.cpp in Sources */,
B2FA3D440AB75A6F000E5AC4 /* JSSVGAnimatedNumber.cpp in Sources */,
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp (180768 => 180769)
--- trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.cpp 2015-02-27 19:20:27 UTC (rev 180769)
@@ -29,6 +29,8 @@
#if ENABLE(CONTENT_EXTENSIONS)
#include "ContentExtensionsDebugging.h"
+#include "DFABytecodeCompiler.h"
+#include "DFABytecodeInterpreter.h"
#include "NFA.h"
#include "NFAToDFA.h"
#include "URL.h"
@@ -85,7 +87,7 @@
double dfaBuildTimeStart = monotonicallyIncreasingTime();
#endif
- CompiledContentExtension compiledContentExtension = { NFAToDFA::convert(nfa), ruleList };
+ const DFA dfa = NFAToDFA::convert(nfa);
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
double dfaBuildTimeEnd = monotonicallyIncreasingTime();
@@ -95,9 +97,13 @@
// FIXME: never add a DFA that only matches the empty set.
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- compiledContentExtension.dfa.debugPrintDot();
+ dfa.debugPrintDot();
#endif
+ Vector<DFABytecode> bytecode;
+ DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ CompiledContentExtension compiledContentExtension = { bytecode, ruleList };
m_ruleLists.set(identifier, compiledContentExtension);
}
@@ -115,24 +121,13 @@
{
const String& urlString = url.string();
ASSERT_WITH_MESSAGE(urlString.containsOnlyASCII(), "A decoded URL should only contain ASCII characters. The matching algorithm assumes the input is ASCII.");
+ const CString& urlCString = urlString.utf8();
for (auto& ruleListSlot : m_ruleLists) {
- CompiledContentExtension& compiledContentExtension = ruleListSlot.value;
- unsigned state = compiledContentExtension.dfa.root();
-
- HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> triggeredActions;
-
- for (unsigned i = 0; i < urlString.length(); ++i) {
- char character = static_cast<char>(urlString[i]);
- bool ok;
- state = compiledContentExtension.dfa.nextState(state, character, ok);
- if (!ok)
- break;
-
- const Vector<uint64_t>& actions = compiledContentExtension.dfa.actions(state);
- if (!actions.isEmpty())
- triggeredActions.add(actions.begin(), actions.end());
- }
+ const CompiledContentExtension& compiledContentExtension = ruleListSlot.value;
+ DFABytecodeInterpreter interpreter(compiledContentExtension.bytecode);
+ DFABytecodeInterpreter::Actions triggeredActions = interpreter.interpret(urlCString);
+ // FIXME: We should eventually do something with each action rather than just returning a bool.
if (!triggeredActions.isEmpty()) {
Vector<uint64_t> sortedActions;
copyToVector(triggeredActions, sortedActions);
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.h (180768 => 180769)
--- trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.h 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsBackend.h 2015-02-27 19:20:27 UTC (rev 180769)
@@ -30,6 +30,7 @@
#include "ContentExtensionRule.h"
#include "DFA.h"
+#include "DFABytecode.h"
#include <wtf/HashMap.h>
#include <wtf/text/StringHash.h>
#include <wtf/text/WTFString.h>
@@ -60,7 +61,7 @@
private:
struct CompiledContentExtension {
- DFA dfa;
+ Vector<DFABytecode> bytecode;
Vector<ContentExtensionRule> ruleList;
};
Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (180768 => 180769)
--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-02-27 19:20:27 UTC (rev 180769)
@@ -59,31 +59,6 @@
return *this;
}
-unsigned DFA::nextState(unsigned currentState, char character, bool& ok) const
-{
- ASSERT(currentState < m_nodes.size());
-
- const DFANode& node = m_nodes[currentState];
- auto nextNode = node.transitions.find(character);
- if (nextNode != node.transitions.end()) {
- ok = true;
- return nextNode->value;
- }
- if (node.hasFallbackTransition) {
- ok = true;
- return node.fallbackTransition;
- }
- ok = false;
- return 0;
-
-}
-
-const Vector<uint64_t>& DFA::actions(unsigned currentState) const
-{
- ASSERT(currentState < m_nodes.size());
- return m_nodes[currentState].actions;
-}
-
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
static void printRange(bool firstRange, char rangeStart, char rangeEnd)
{
Modified: trunk/Source/WebCore/contentextensions/DFA.h (180768 => 180769)
--- trunk/Source/WebCore/contentextensions/DFA.h 2015-02-27 18:50:20 UTC (rev 180768)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2015-02-27 19:20:27 UTC (rev 180769)
@@ -46,10 +46,8 @@
DFA& operator=(const DFA&);
unsigned root() const { return m_root; }
- // If there is a transition to a valid state on "character", return that state and set ok to true.
- // Otherwise, the return value is undefined and ok is false.
- unsigned nextState(unsigned currentState, char character, bool& ok) const;
- const Vector<uint64_t>& actions(unsigned currentState) const;
+ unsigned size() const { return m_nodes.size(); }
+ const DFANode& nodeAt(unsigned i) const { return m_nodes[i]; }
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
void debugPrintDot() const;
Added: trunk/Source/WebCore/contentextensions/DFABytecode.h (0 => 180769)
--- trunk/Source/WebCore/contentextensions/DFABytecode.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFABytecode.h 2015-02-27 19:20:27 UTC (rev 180769)
@@ -0,0 +1,76 @@
+/*
+ * 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 DFABytecode_h
+#define DFABytecode_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+typedef uint8_t DFABytecode;
+
+enum class DFABytecodeInstruction : uint8_t {
+
+ // CheckValue has two arguments:
+ // The value to check (1 byte),
+ // The index to jump to if the values are equal (4 bytes).
+ CheckValue,
+
+ // AppendAction has one argument:
+ // The action to append (4 bytes).
+ AppendAction,
+
+ // Terminate has no arguments.
+ Terminate,
+
+ // Jump has one argument:
+ // The index to jump to unconditionally (4 bytes).
+ Jump,
+};
+
+static inline size_t instructionSizeWithArguments(DFABytecodeInstruction instruction)
+{
+ switch (instruction) {
+ case DFABytecodeInstruction::CheckValue:
+ return sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + sizeof(unsigned);
+ case DFABytecodeInstruction::AppendAction:
+ return sizeof(DFABytecodeInstruction) + sizeof(unsigned);
+ case DFABytecodeInstruction::Terminate:
+ return sizeof(DFABytecodeInstruction);
+ case DFABytecodeInstruction::Jump:
+ return sizeof(DFABytecodeInstruction) + sizeof(unsigned);
+ }
+}
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // DFABytecode_h
Added: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (0 => 180769)
--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-02-27 19:20:27 UTC (rev 180769)
@@ -0,0 +1,116 @@
+/*
+ * 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 "DFABytecodeCompiler.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "ContentExtensionRule.h"
+#include "DFA.h"
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+template <typename IntType>
+inline void append(Vector<DFABytecode>& bytecode, IntType value)
+{
+ bytecode.resize(bytecode.size() + sizeof(IntType));
+ *reinterpret_cast<IntType*>(&bytecode[bytecode.size() - sizeof(IntType)]) = value;
+}
+
+inline void set32Bits(Vector<DFABytecode>& bytecode, unsigned index, unsigned value)
+{
+ *reinterpret_cast<unsigned*>(&bytecode[index]) = value;
+}
+
+void DFABytecodeCompiler::emitAppendAction(unsigned action)
+{
+ append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::AppendAction);
+ append<unsigned>(m_bytecode, action);
+}
+
+void DFABytecodeCompiler::emitJump(unsigned destinationNodeIndex)
+{
+ append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Jump);
+ m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
+ append<unsigned>(m_bytecode, 0); // This value will be set when linking.
+}
+
+void DFABytecodeCompiler::emitCheckValue(uint8_t value, unsigned destinationNodeIndex)
+{
+ append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::CheckValue);
+ append<uint8_t>(m_bytecode, value);
+ m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
+ append<unsigned>(m_bytecode, 0); // This value will be set when linking.
+}
+
+void DFABytecodeCompiler::emitTerminate()
+{
+ append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Terminate);
+}
+
+void DFABytecodeCompiler::compileNode(unsigned index)
+{
+ const DFANode& node = m_dfa.nodeAt(index);
+
+ // Record starting index for linking.
+ m_nodeStartOffsets[index] = m_bytecode.size();
+
+ for (uint64_t action : node.actions)
+ emitAppendAction(static_cast<unsigned>(action));
+
+ for (const auto& transition : node.transitions)
+ emitCheckValue(transition.key, transition.value);
+
+ if (node.hasFallbackTransition)
+ emitJump(node.fallbackTransition);
+ else
+ emitTerminate();
+}
+
+void DFABytecodeCompiler::compile()
+{
+ ASSERT(!m_bytecode.size());
+ m_nodeStartOffsets.resize(m_dfa.size());
+
+ // Make sure the root is always at the beginning of the bytecode.
+ compileNode(m_dfa.root());
+ for (unsigned i = 0; i < m_dfa.size(); i++) {
+ if (i != m_dfa.root())
+ compileNode(i);
+ }
+
+ // Link.
+ for (const auto& linkRecord : m_linkRecords)
+ set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
+}
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
Added: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (0 => 180769)
--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-02-27 19:20:27 UTC (rev 180769)
@@ -0,0 +1,75 @@
+/*
+ * 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 DFABytecodeCompiler_h
+#define DFABytecodeCompiler_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "DFABytecode.h"
+#include "DFANode.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class DFA;
+
+class DFABytecodeCompiler {
+public:
+ DFABytecodeCompiler(const DFA& dfa, Vector<DFABytecode>& bytecode)
+ : m_bytecode(bytecode)
+ , m_dfa(dfa)
+ {
+ }
+
+ void compile();
+
+private:
+ void compileNode(unsigned);
+
+ void emitAppendAction(unsigned);
+ void emitJump(unsigned destinationNodeIndex);
+ void emitCheckValue(uint8_t value, unsigned destinationNodeIndex);
+ void emitTerminate();
+
+ Vector<DFABytecode>& m_bytecode;
+ const DFA& m_dfa;
+
+ Vector<unsigned> m_nodeStartOffsets;
+
+ // The first value is the index in the bytecode buffer where the jump is to be written.
+ // The second value is the index of the node to jump to.
+ Vector<std::pair<unsigned, unsigned>> m_linkRecords;
+};
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // DFABytecodeCompiler_h
Added: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp (0 => 180769)
--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-02-27 19:20:27 UTC (rev 180769)
@@ -0,0 +1,92 @@
+/*
+ * 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 "DFABytecodeInterpreter.h"
+
+#include <wtf/text/CString.h>
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+template <typename IntType>
+static inline IntType getBits(const Vector<DFABytecode>& bytecode, unsigned index)
+{
+ return *reinterpret_cast<const IntType*>(&bytecode[index]);
+}
+
+DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpret(const CString& urlCString)
+{
+ const char* url = ""
+ ASSERT(url);
+
+ unsigned programCounter = 0;
+ unsigned urlIndex = 0;
+ Actions actions;
+
+ // This should always terminate if interpreting correctly compiled bytecode.
+ while (true) {
+ switch (static_cast<DFABytecodeInstruction>(bytecode[programCounter])) {
+
+ case DFABytecodeInstruction::Terminate:
+ return actions;
+
+ case DFABytecodeInstruction::CheckValue:
+ // Check to see if the next character in the url is the value stored with the bytecode.
+ if (!url[urlIndex])
+ return actions; // Reached null character at end.
+ if (url[urlIndex] == getBits<uint8_t>(bytecode, programCounter + sizeof(DFABytecode))) {
+ programCounter = getBits<unsigned>(bytecode, programCounter + sizeof(DFABytecode) + sizeof(uint8_t));
+ urlIndex++; // This represents an edge in the DFA.
+ } else
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValue);
+ break;
+
+ case DFABytecodeInstruction::Jump:
+ programCounter = getBits<unsigned>(bytecode, programCounter + sizeof(DFABytecode));
+ urlIndex++; // This represents an edge in the DFA.
+ break;
+
+ case DFABytecodeInstruction::AppendAction:
+ actions.add(static_cast<uint64_t>(getBits<unsigned>(bytecode, programCounter + sizeof(DFABytecode))));
+ programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
+ break;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
+ }
+ ASSERT(urlIndex <= urlCString.length()); // We should always terminate at a null character at the end of a String.
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+}
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
Added: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h (0 => 180769)
--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h 2015-02-27 19:20:27 UTC (rev 180769)
@@ -0,0 +1,61 @@
+/*
+ * 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 DFABytecodeInterpreter_h
+#define DFABytecodeInterpreter_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "ContentExtensionRule.h"
+#include "DFABytecode.h"
+#include <wtf/HashSet.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class DFABytecodeInterpreter {
+public:
+ DFABytecodeInterpreter(const Vector<DFABytecode>& bytecode)
+ : bytecode(bytecode)
+ {
+ }
+
+ typedef HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> Actions;
+
+ Actions interpret(const CString&);
+
+private:
+ const Vector<DFABytecode>& bytecode;
+};
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // DFABytecodeInterpreter_h
