2434afb8e9ad1ac59d9782fb0ab1ce172fad8268
[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)
97 {
98     const DFANode& node = m_dfa.nodeAt(index);
99
100     // Record starting index for linking.
101     m_nodeStartOffsets[index] = m_bytecode.size();
102
103     for (uint64_t action : node.actions) {
104         // High bits are used to store flags. See compileRuleList.
105         if (action & 0xFFFF00000000)
106             emitTestFlagsAndAppendAction(static_cast<uint16_t>(action >> 32), static_cast<unsigned>(action));
107         else
108             emitAppendAction(static_cast<unsigned>(action));
109     }
110     compileNodeTransitions(node);
111 }
112
113 void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)
114 {
115     unsigned destinations[128];
116     const unsigned noDestination = std::numeric_limits<unsigned>::max();
117     for (uint16_t i = 0; i < 128; i++) {
118         auto it = node.transitions.find(i);
119         if (it == node.transitions.end())
120             destinations[i] = noDestination;
121         else
122             destinations[i] = it->value;
123     }
124
125     Vector<Range> ranges;
126     uint8_t rangeMin;
127     bool hasRangeMin = false;
128     for (uint8_t i = 0; i < 128; i++) {
129         if (hasRangeMin) {
130             ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
131             if (destinations[i] != destinations[rangeMin]) {
132
133                 // This is the end of a range. Check if it can be case insensitive.
134                 uint8_t rangeMax = i - 1;
135                 bool caseSensitive = true;
136                 if (rangeMin >= 'A' && rangeMax <= 'Z') {
137                     caseSensitive = false;
138                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
139                         if (destinations[rangeMin] != destinations[toASCIILower(rangeIndex)]) {
140                             caseSensitive = true;
141                             break;
142                         }
143                     }
144                 }
145
146                 if (!caseSensitive) {
147                     // If all the lower-case destinations are the same as the upper-case destinations,
148                     // then they will be covered by a case-insensitive range and will not need their own range.
149                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
150                         ASSERT(destinations[rangeMin] == destinations[toASCIILower(rangeIndex)]);
151                         destinations[toASCIILower(rangeIndex)] = noDestination;
152                     }
153                     ranges.append(Range(toASCIILower(rangeMin), toASCIILower(rangeMax), destinations[rangeMin], caseSensitive));
154                 } else
155                     ranges.append(Range(rangeMin, rangeMax, destinations[rangeMin], caseSensitive));
156
157                 if (destinations[i] == noDestination)
158                     hasRangeMin = false;
159                 else
160                     rangeMin = i;
161             }
162         } else {
163             if (destinations[i] != noDestination) {
164                 rangeMin = i;
165                 hasRangeMin = true;
166             }
167         }
168     }
169     if (hasRangeMin) {
170         // Ranges are appended after passing the end of them.
171         // If a range goes to 127, we will have an uncommitted rangeMin because the loop does not check 128.
172         // If a range goes to 127, there will never be values higher than it, so checking for case-insensitive ranges would always fail.
173         ranges.append(Range(rangeMin, 127, destinations[rangeMin], true));
174     }
175
176     for (const auto& range : ranges)
177         compileCheckForRange(range);
178     if (node.hasFallbackTransition)
179         emitJump(node.fallbackTransition);
180     else
181         emitTerminate();
182 }
183
184 void DFABytecodeCompiler::compileCheckForRange(const Range& range)
185 {
186     ASSERT_WITH_MESSAGE(range.max < 128, "The DFA engine only supports the ASCII alphabet.");
187     ASSERT(range.min <= range.max);
188
189     if (range.min == range.max)
190         emitCheckValue(range.min, range.destination, range.caseSensitive);
191     else
192         emitCheckValueRange(range.min, range.max, range.destination, range.caseSensitive);
193 }
194
195 void DFABytecodeCompiler::compile()
196 {
197     // DFA header.
198     unsigned startLocation = m_bytecode.size();
199     append<unsigned>(m_bytecode, 0);
200     m_nodeStartOffsets.resize(m_dfa.size());
201     
202     // Make sure the root is always at the beginning of the bytecode.
203     compileNode(m_dfa.root());
204     for (unsigned i = 0; i < m_dfa.size(); i++) {
205         if (i != m_dfa.root())
206             compileNode(i);
207     }
208
209     // Link.
210     for (const auto& linkRecord : m_linkRecords)
211         set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
212     
213     // Set size header.
214     set32Bits(m_bytecode, startLocation, m_bytecode.size() - startLocation);
215 }
216     
217 } // namespace ContentExtensions
218
219 } // namespace WebCore
220
221 #endif // ENABLE(CONTENT_EXTENSIONS)