Optimize content extensions interpreting speed.
[WebKit-https.git] / Source / WebCore / contentextensions / DFABytecodeCompiler.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 "DFABytecodeCompiler.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "ContentExtensionRule.h"
32 #include "DFA.h"
33 #include "DFANode.h"
34
35 namespace WebCore {
36     
37 namespace ContentExtensions {
38
39 template <typename IntType>
40 inline void append(Vector<DFABytecode>& bytecode, IntType value)
41 {
42     bytecode.resize(bytecode.size() + sizeof(IntType));
43     *reinterpret_cast<IntType*>(&bytecode[bytecode.size() - sizeof(IntType)]) = value;
44 }
45
46 inline void set32Bits(Vector<DFABytecode>& bytecode, unsigned index, unsigned value)
47 {
48     *reinterpret_cast<unsigned*>(&bytecode[index]) = value;
49 }
50
51 void DFABytecodeCompiler::emitAppendAction(unsigned action)
52 {
53     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::AppendAction);
54     append<unsigned>(m_bytecode, action);
55 }
56
57 void DFABytecodeCompiler::emitTestFlagsAndAppendAction(uint16_t flags, unsigned action)
58 {
59     ASSERT(flags);
60     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::TestFlagsAndAppendAction);
61     append<uint16_t>(m_bytecode, flags);
62     append<unsigned>(m_bytecode, action);
63 }
64
65 void DFABytecodeCompiler::emitJump(unsigned destinationNodeIndex)
66 {
67     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Jump);
68     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
69     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
70 }
71
72 void DFABytecodeCompiler::emitCheckValue(uint8_t value, unsigned destinationNodeIndex, bool caseSensitive)
73 {
74     append<DFABytecodeInstruction>(m_bytecode, caseSensitive ? DFABytecodeInstruction::CheckValueCaseSensitive : DFABytecodeInstruction::CheckValueCaseInsensitive);
75     append<uint8_t>(m_bytecode, value);
76     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
77     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
78 }
79
80 void DFABytecodeCompiler::emitCheckValueRange(uint8_t lowValue, uint8_t highValue, unsigned destinationNodeIndex, bool caseSensitive)
81 {
82     ASSERT_WITH_MESSAGE(lowValue < highValue, "The instruction semantic impose lowValue is strictly less than highValue.");
83
84     append<DFABytecodeInstruction>(m_bytecode, caseSensitive ? DFABytecodeInstruction::CheckValueRangeCaseSensitive : DFABytecodeInstruction::CheckValueRangeCaseInsensitive);
85     append<uint8_t>(m_bytecode, lowValue);
86     append<uint8_t>(m_bytecode, highValue);
87     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
88     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
89 }
90
91 void DFABytecodeCompiler::emitTerminate()
92 {
93     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Terminate);
94 }
95
96 void DFABytecodeCompiler::compileNode(unsigned index, bool root)
97 {
98     const DFANode& node = m_dfa.nodeAt(index);
99
100     // Record starting index for linking.
101     if (!root)
102         m_nodeStartOffsets[index] = m_bytecode.size();
103
104     for (uint64_t action : node.actions) {
105         // High bits are used to store flags. See compileRuleList.
106         if (action & 0xFFFF00000000)
107             emitTestFlagsAndAppendAction(static_cast<uint16_t>(action >> 32), static_cast<unsigned>(action));
108         else
109             emitAppendAction(static_cast<unsigned>(action));
110     }
111     
112     // If we jump to the root, we don't want to re-add its actions to a HashSet.
113     // We know we have already added them because the root is always compiled first and we always start interpreting at the beginning.
114     if (root)
115         m_nodeStartOffsets[index] = m_bytecode.size();
116     
117     compileNodeTransitions(node);
118 }
119
120 void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)
121 {
122     unsigned destinations[128];
123     const unsigned noDestination = std::numeric_limits<unsigned>::max();
124     for (uint16_t i = 0; i < 128; i++) {
125         auto it = node.transitions.find(i);
126         if (it == node.transitions.end())
127             destinations[i] = noDestination;
128         else
129             destinations[i] = it->value;
130     }
131
132     Vector<Range> ranges;
133     uint8_t rangeMin;
134     bool hasRangeMin = false;
135     for (uint8_t i = 0; i < 128; i++) {
136         if (hasRangeMin) {
137             ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
138             if (destinations[i] != destinations[rangeMin]) {
139
140                 // This is the end of a range. Check if it can be case insensitive.
141                 uint8_t rangeMax = i - 1;
142                 bool caseSensitive = true;
143                 if (rangeMin >= 'A' && rangeMax <= 'Z') {
144                     caseSensitive = false;
145                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
146                         if (destinations[rangeMin] != destinations[toASCIILower(rangeIndex)]) {
147                             caseSensitive = true;
148                             break;
149                         }
150                     }
151                 }
152
153                 if (!caseSensitive) {
154                     // If all the lower-case destinations are the same as the upper-case destinations,
155                     // then they will be covered by a case-insensitive range and will not need their own range.
156                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
157                         ASSERT(destinations[rangeMin] == destinations[toASCIILower(rangeIndex)]);
158                         destinations[toASCIILower(rangeIndex)] = noDestination;
159                     }
160                     ranges.append(Range(toASCIILower(rangeMin), toASCIILower(rangeMax), destinations[rangeMin], caseSensitive));
161                 } else
162                     ranges.append(Range(rangeMin, rangeMax, destinations[rangeMin], caseSensitive));
163
164                 if (destinations[i] == noDestination)
165                     hasRangeMin = false;
166                 else
167                     rangeMin = i;
168             }
169         } else {
170             if (destinations[i] != noDestination) {
171                 rangeMin = i;
172                 hasRangeMin = true;
173             }
174         }
175     }
176     if (hasRangeMin) {
177         // Ranges are appended after passing the end of them.
178         // If a range goes to 127, we will have an uncommitted rangeMin because the loop does not check 128.
179         // If a range goes to 127, there will never be values higher than it, so checking for case-insensitive ranges would always fail.
180         ranges.append(Range(rangeMin, 127, destinations[rangeMin], true));
181     }
182
183     for (const auto& range : ranges)
184         compileCheckForRange(range);
185     if (node.hasFallbackTransition)
186         emitJump(node.fallbackTransition);
187     else
188         emitTerminate();
189 }
190
191 void DFABytecodeCompiler::compileCheckForRange(const Range& range)
192 {
193     ASSERT_WITH_MESSAGE(range.max < 128, "The DFA engine only supports the ASCII alphabet.");
194     ASSERT(range.min <= range.max);
195
196     if (range.min == range.max)
197         emitCheckValue(range.min, range.destination, range.caseSensitive);
198     else
199         emitCheckValueRange(range.min, range.max, range.destination, range.caseSensitive);
200 }
201
202 void DFABytecodeCompiler::compile()
203 {
204     // DFA header.
205     unsigned startLocation = m_bytecode.size();
206     append<unsigned>(m_bytecode, 0);
207     m_nodeStartOffsets.resize(m_dfa.size());
208     
209     // Make sure the root is always at the beginning of the bytecode.
210     compileNode(m_dfa.root(), true);
211     for (unsigned i = 0; i < m_dfa.size(); i++) {
212         if (i != m_dfa.root())
213             compileNode(i, false);
214     }
215
216     // Link.
217     for (const auto& linkRecord : m_linkRecords)
218         set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
219     
220     // Set size header.
221     set32Bits(m_bytecode, startLocation, m_bytecode.size() - startLocation);
222 }
223     
224 } // namespace ContentExtensions
225
226 } // namespace WebCore
227
228 #endif // ENABLE(CONTENT_EXTENSIONS)