[ContentExtensions] Prepare for compiling stylesheets of selectors to be used on...
[WebKit-https.git] / Source / WebCore / contentextensions / DFABytecodeInterpreter.cpp
1 /*
2  * Copyright (C) 2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "DFABytecodeInterpreter.h"
28
29 #include <wtf/text/CString.h>
30
31 #if ENABLE(CONTENT_EXTENSIONS)
32
33 namespace WebCore {
34     
35 namespace ContentExtensions {
36
37 template <typename IntType>
38 static inline IntType getBits(const DFABytecode* bytecode, unsigned bytecodeLength, unsigned index)
39 {
40     ASSERT_UNUSED(bytecodeLength, index + sizeof(IntType) <= bytecodeLength);
41     return *reinterpret_cast<const IntType*>(&bytecode[index]);
42 }
43     
44 DFABytecodeInterpreter::Actions DFABytecodeInterpreter::actionsFromDFARoot()
45 {
46     unsigned programCounter = 0;
47     DFABytecodeInterpreter::Actions globalActionLocations;
48     while (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter]) == DFABytecodeInstruction::AppendAction) {
49         globalActionLocations.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
50         programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
51     }
52     return globalActionLocations;
53 }
54     
55 DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpret(const CString& urlCString, uint16_t flags)
56 {
57     const char* url = urlCString.data();
58     ASSERT(url);
59     
60     unsigned programCounter = 0;
61     unsigned urlIndex = 0;
62     bool urlIndexIsAfterEndOfString = false;
63     Actions actions;
64     
65     // FIXME: Skip the actions from the root once they are used through actionsFromDFARoot. Change AppendAction to AppendActions to make this faster.
66     
67     // This should always terminate if interpreting correctly compiled bytecode.
68     while (true) {
69         ASSERT(programCounter <= m_bytecodeLength);
70         switch (static_cast<DFABytecodeInstruction>(m_bytecode[programCounter])) {
71
72         case DFABytecodeInstruction::Terminate:
73             return actions;
74
75         case DFABytecodeInstruction::CheckValue:
76             if (urlIndexIsAfterEndOfString)
77                 return actions;
78
79             // Check to see if the next character in the url is the value stored with the bytecode.
80             if (url[urlIndex] == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))) {
81                 programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t));
82                 if (!url[urlIndex])
83                     urlIndexIsAfterEndOfString = true;
84                 urlIndex++; // This represents an edge in the DFA.
85             } else
86                 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValue);
87             break;
88
89         case DFABytecodeInstruction::CheckValueRange: {
90             if (urlIndexIsAfterEndOfString)
91                 return actions;
92
93             char character = url[urlIndex];
94             if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))
95                 && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t))) {
96                 programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint8_t) + sizeof(uint8_t));
97                 if (!character)
98                     urlIndexIsAfterEndOfString = true;
99                 urlIndex++; // This represents an edge in the DFA.
100             } else
101                 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::CheckValueRange);
102             break;
103         }
104
105         case DFABytecodeInstruction::Jump:
106             if (!url[urlIndex] || urlIndexIsAfterEndOfString)
107                 return actions;
108
109             programCounter = getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode));
110             urlIndex++; // This represents an edge in the DFA.
111             break;
112
113         case DFABytecodeInstruction::AppendAction:
114             actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode))));
115             programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
116             break;
117
118         case DFABytecodeInstruction::TestFlagsAndAppendAction:
119             if (flags & getBits<uint16_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode)))
120                 actions.add(static_cast<uint64_t>(getBits<unsigned>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecode) + sizeof(uint16_t))));
121             programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
122             break;
123
124         default:
125             RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
126         }
127         // We should always terminate before or at a null character at the end of a String.
128         ASSERT(urlIndex <= urlCString.length() || (urlIndexIsAfterEndOfString && urlIndex <= urlCString.length() + 1));
129     }
130     RELEASE_ASSERT_NOT_REACHED();
131 }
132
133 } // namespace ContentExtensions
134     
135 } // namespace WebCore
136
137 #endif // ENABLE(CONTENT_EXTENSIONS)