[Content Extensions] Remove memory page reporting
[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 "ContentExtensionsDebugging.h"
30 #include <wtf/text/CString.h>
31
32 #if ENABLE(CONTENT_EXTENSIONS)
33
34 namespace WebCore {
35     
36 namespace ContentExtensions {
37
38 template <typename IntType>
39 static inline IntType getBits(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
40 {
41     ASSERT_UNUSED(bytecodeLength, index + sizeof(IntType) <= bytecodeLength);
42     return *reinterpret_cast<const IntType*>(&bytecode[index]);
43 }
44
45 static inline DFABytecodeInstruction getInstruction(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
46 {
47     return static_cast<DFABytecodeInstruction>(getBits<uint8_t>(bytecode, bytecodeLength, index) & DFABytecodeInstructionMask);
48 }
49
50 static inline size_t jumpSizeInBytes(DFABytecodeJumpSize jumpSize)
51 {
52     switch (jumpSize) {
53     case Int8:
54         return sizeof(int8_t);
55     case Int16:
56         return sizeof(int16_t);
57     case Int32:
58         return sizeof(int32_t);
59     default:
60         RELEASE_ASSERT_NOT_REACHED();
61     }
62 }
63
64 static inline DFABytecodeJumpSize getJumpSize(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
65 {
66     DFABytecodeJumpSize jumpSize = static_cast<DFABytecodeJumpSize>(getBits<uint8_t>(bytecode, bytecodeLength, index) & DFABytecodeJumpSizeMask);
67     ASSERT(jumpSize == DFABytecodeJumpSize::Int32 || jumpSize == DFABytecodeJumpSize::Int16 || jumpSize == DFABytecodeJumpSize::Int8);
68     return jumpSize;
69 }
70
71 static inline int32_t getJumpDistance(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index, DFABytecodeJumpSize jumpSize)
72 {
73     switch (jumpSize) {
74     case Int8:
75         return getBits<int8_t>(bytecode, bytecodeLength, index);
76     case Int16:
77         return getBits<int16_t>(bytecode, bytecodeLength, index);
78     case Int32:
79         return getBits<int32_t>(bytecode, bytecodeLength, index);
80     default:
81         RELEASE_ASSERT_NOT_REACHED();
82     }
83 }
84
85 void DFABytecodeInterpreter::interpretAppendAction(uint32_t& programCounter, Actions& actions, bool ifDomain)
86 {
87     ASSERT(getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::AppendAction
88         || getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::AppendActionWithIfDomain
89         || getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::AppendActionDefaultStylesheet);
90     actions.add((ifDomain ? IfDomainFlag : 0) | static_cast<uint64_t>(getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))));
91     programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
92     ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::AppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::AppendActionWithIfDomain));
93     ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::AppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::AppendActionDefaultStylesheet));
94 }
95
96 void DFABytecodeInterpreter::interpretTestFlagsAndAppendAction(uint32_t& programCounter, uint16_t flags, Actions& actions, bool ifDomain)
97 {
98     ASSERT(getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::TestFlagsAndAppendAction
99         || getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::TestFlagsAndAppendActionWithIfDomain);
100     uint16_t flagsToCheck = getBits<uint16_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction));
101
102     uint16_t loadTypeFlags = flagsToCheck & LoadTypeMask;
103     uint16_t ressourceTypeFlags = flagsToCheck & ResourceTypeMask;
104     
105     bool loadTypeMatches = loadTypeFlags ? (loadTypeFlags & flags) : true;
106     bool ressourceTypeMatches = ressourceTypeFlags ? (ressourceTypeFlags & flags) : true;
107     
108     if (loadTypeMatches && ressourceTypeMatches)
109         actions.add((ifDomain ? IfDomainFlag : 0) | static_cast<uint64_t>(getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint16_t))));
110     programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
111     ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendActionWithIfDomain));
112 }
113
114 DFABytecodeInterpreter::Actions DFABytecodeInterpreter::actionsForDefaultStylesheetFromDFARoot()
115 {
116     Actions actions;
117
118     // DFA header.
119     uint32_t dfaBytecodeLength = getBits<uint32_t>(m_bytecode, m_bytecodeLength, 0);
120     uint32_t programCounter = sizeof(uint32_t);
121
122     while (programCounter < dfaBytecodeLength) {
123         DFABytecodeInstruction instruction = getInstruction(m_bytecode, m_bytecodeLength, programCounter);
124         if (instruction == DFABytecodeInstruction::AppendActionDefaultStylesheet)
125             interpretAppendAction(programCounter, actions, false);
126         else if (instruction == DFABytecodeInstruction::AppendAction)
127             programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
128         else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendAction)
129             programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
130         else {
131             // actionsForDefaultStylesheetFromDFARoot should only be called on the DFA without domains,
132             // which should never have any actions with if-domain.
133             ASSERT(instruction != DFABytecodeInstruction::TestFlagsAndAppendActionWithIfDomain);
134             ASSERT(instruction != DFABytecodeInstruction::AppendActionWithIfDomain);
135             break;
136         }
137     }
138     return actions;
139 }
140     
141 DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpret(const CString& urlCString, uint16_t flags)
142 {
143     const char* url = urlCString.data();
144     ASSERT(url);
145     
146     Actions actions;
147     
148     uint32_t programCounter = 0;
149     while (programCounter < m_bytecodeLength) {
150
151         // DFA header.
152         uint32_t dfaStart = programCounter;
153         uint32_t dfaBytecodeLength = getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter);
154         programCounter += sizeof(uint32_t);
155
156         // Skip the default stylesheet actions on the DFA root. These are accessed via actionsForDefaultStylesheetFromDFARoot.
157         if (!dfaStart) {
158             while (programCounter < dfaBytecodeLength) {
159                 DFABytecodeInstruction instruction = getInstruction(m_bytecode, m_bytecodeLength, programCounter);
160                 if (instruction == DFABytecodeInstruction::AppendActionDefaultStylesheet)
161                     programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendActionDefaultStylesheet);
162                 else if (instruction == DFABytecodeInstruction::AppendAction)
163                     interpretAppendAction(programCounter, actions, false);
164                 else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendAction)
165                     interpretTestFlagsAndAppendAction(programCounter, flags, actions, false);
166                 else
167                     break;
168             }
169             if (programCounter >= m_bytecodeLength)
170                 return actions;
171         } else {
172             ASSERT_WITH_MESSAGE(getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::AppendAction
173                 && getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::TestFlagsAndAppendAction,
174                 "Triggers that match everything should only be in the first DFA.");
175         }
176         
177         // Interpret the bytecode from this DFA.
178         // This should always terminate if interpreting correctly compiled bytecode.
179         uint32_t urlIndex = 0;
180         bool urlIndexIsAfterEndOfString = false;
181         while (true) {
182             ASSERT(programCounter <= m_bytecodeLength);
183             switch (getInstruction(m_bytecode, m_bytecodeLength, programCounter)) {
184
185             case DFABytecodeInstruction::Terminate:
186                 goto nextDFA;
187                     
188             case DFABytecodeInstruction::CheckValueCaseSensitive: {
189                 if (urlIndexIsAfterEndOfString)
190                     goto nextDFA;
191
192                 // Check to see if the next character in the url is the value stored with the bytecode.
193                 char character = url[urlIndex];
194                 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
195                 if (character == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))) {
196                     uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t);
197                     programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
198                     if (!character)
199                         urlIndexIsAfterEndOfString = true;
200                     urlIndex++; // This represents an edge in the DFA.
201                 } else
202                     programCounter += sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
203                 break;
204             }
205
206             case DFABytecodeInstruction::CheckValueCaseInsensitive: {
207                 if (urlIndexIsAfterEndOfString)
208                     goto nextDFA;
209
210                 // Check to see if the next character in the url is the value stored with the bytecode.
211                 char character = toASCIILower(url[urlIndex]);
212                 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
213                 if (character == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))) {
214                     uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t);
215                     programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
216                     if (!character)
217                         urlIndexIsAfterEndOfString = true;
218                     urlIndex++; // This represents an edge in the DFA.
219                 } else
220                     programCounter += sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
221                 break;
222             }
223                     
224             case DFABytecodeInstruction::CheckValueRangeCaseSensitive: {
225                 if (urlIndexIsAfterEndOfString)
226                     goto nextDFA;
227                 
228                 char character = url[urlIndex];
229                 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
230                 if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))
231                     && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t))) {
232                     uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
233                     programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
234                     if (!character)
235                         urlIndexIsAfterEndOfString = true;
236                     urlIndex++; // This represents an edge in the DFA.
237                 } else
238                     programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
239                 break;
240             }
241
242             case DFABytecodeInstruction::CheckValueRangeCaseInsensitive: {
243                 if (urlIndexIsAfterEndOfString)
244                     goto nextDFA;
245                 
246                 char character = toASCIILower(url[urlIndex]);
247                 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
248                 if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))
249                     && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t))) {
250                     uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
251                     programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
252                     if (!character)
253                         urlIndexIsAfterEndOfString = true;
254                     urlIndex++; // This represents an edge in the DFA.
255                 } else
256                     programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
257                 break;
258             }
259
260             case DFABytecodeInstruction::Jump: {
261                 if (!url[urlIndex] || urlIndexIsAfterEndOfString)
262                     goto nextDFA;
263                 
264                 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction);
265                 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
266                 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
267                 urlIndex++; // This represents an edge in the DFA.
268                 break;
269             }
270                     
271             case DFABytecodeInstruction::AppendAction:
272                 interpretAppendAction(programCounter, actions, false);
273                 break;
274                     
275             case DFABytecodeInstruction::AppendActionWithIfDomain:
276                 interpretAppendAction(programCounter, actions, true);
277                 break;
278                     
279             case DFABytecodeInstruction::TestFlagsAndAppendAction:
280                 interpretTestFlagsAndAppendAction(programCounter, flags, actions, false);
281                 break;
282             
283             case DFABytecodeInstruction::TestFlagsAndAppendActionWithIfDomain:
284                 interpretTestFlagsAndAppendAction(programCounter, flags, actions, true);
285                 break;
286                     
287             default:
288                 RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
289             }
290             // We should always terminate before or at a null character at the end of a String.
291             ASSERT(urlIndex <= urlCString.length() || (urlIndexIsAfterEndOfString && urlIndex <= urlCString.length() + 1));
292         }
293         RELEASE_ASSERT_NOT_REACHED(); // The while loop can only be exited using goto nextDFA.
294         nextDFA:
295         ASSERT(dfaBytecodeLength);
296         programCounter = dfaStart + dfaBytecodeLength;
297     }
298     return actions;
299 }
300
301 } // namespace ContentExtensions
302     
303 } // namespace WebCore
304
305 #endif // ENABLE(CONTENT_EXTENSIONS)