1 | // Copyright 2012 the V8 project authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | #ifndef V8_REGEXP_REGEXP_MACRO_ASSEMBLER_H_ |
6 | #define V8_REGEXP_REGEXP_MACRO_ASSEMBLER_H_ |
7 | |
8 | #include "src/label.h" |
9 | #include "src/regexp/regexp-ast.h" |
10 | |
11 | namespace v8 { |
12 | namespace internal { |
13 | |
14 | static const uc32 kLeadSurrogateStart = 0xd800; |
15 | static const uc32 kLeadSurrogateEnd = 0xdbff; |
16 | static const uc32 kTrailSurrogateStart = 0xdc00; |
17 | static const uc32 kTrailSurrogateEnd = 0xdfff; |
18 | static const uc32 kNonBmpStart = 0x10000; |
19 | static const uc32 kNonBmpEnd = 0x10ffff; |
20 | |
21 | struct DisjunctDecisionRow { |
22 | RegExpCharacterClass cc; |
23 | Label* on_match; |
24 | }; |
25 | |
26 | |
27 | class RegExpMacroAssembler { |
28 | public: |
29 | // The implementation must be able to handle at least: |
30 | static const int kMaxRegister = (1 << 16) - 1; |
31 | static const int kMaxCPOffset = (1 << 15) - 1; |
32 | static const int kMinCPOffset = -(1 << 15); |
33 | |
34 | static const int kTableSizeBits = 7; |
35 | static const int kTableSize = 1 << kTableSizeBits; |
36 | static const int kTableMask = kTableSize - 1; |
37 | |
38 | enum IrregexpImplementation { |
39 | kIA32Implementation, |
40 | kARMImplementation, |
41 | kARM64Implementation, |
42 | kMIPSImplementation, |
43 | kS390Implementation, |
44 | kPPCImplementation, |
45 | kX64Implementation, |
46 | kX87Implementation, |
47 | kBytecodeImplementation |
48 | }; |
49 | |
50 | enum StackCheckFlag { |
51 | kNoStackLimitCheck = false, |
52 | kCheckStackLimit = true |
53 | }; |
54 | |
55 | RegExpMacroAssembler(Isolate* isolate, Zone* zone); |
56 | virtual ~RegExpMacroAssembler(); |
57 | // This function is called when code generation is aborted, so that |
58 | // the assembler could clean up internal data structures. |
59 | virtual void AbortedCodeGeneration() {} |
60 | // The maximal number of pushes between stack checks. Users must supply |
61 | // kCheckStackLimit flag to push operations (instead of kNoStackLimitCheck) |
62 | // at least once for every stack_limit() pushes that are executed. |
63 | virtual int stack_limit_slack() = 0; |
64 | virtual bool CanReadUnaligned() = 0; |
65 | virtual void AdvanceCurrentPosition(int by) = 0; // Signed cp change. |
66 | virtual void AdvanceRegister(int reg, int by) = 0; // r[reg] += by. |
67 | // Continues execution from the position pushed on the top of the backtrack |
68 | // stack by an earlier PushBacktrack(Label*). |
69 | virtual void Backtrack() = 0; |
70 | virtual void Bind(Label* label) = 0; |
71 | virtual void CheckAtStart(Label* on_at_start) = 0; |
72 | // Dispatch after looking the current character up in a 2-bits-per-entry |
73 | // map. The destinations vector has up to 4 labels. |
74 | virtual void CheckCharacter(unsigned c, Label* on_equal) = 0; |
75 | // Bitwise and the current character with the given constant and then |
76 | // check for a match with c. |
77 | virtual void CheckCharacterAfterAnd(unsigned c, |
78 | unsigned and_with, |
79 | Label* on_equal) = 0; |
80 | virtual void CheckCharacterGT(uc16 limit, Label* on_greater) = 0; |
81 | virtual void CheckCharacterLT(uc16 limit, Label* on_less) = 0; |
82 | virtual void CheckGreedyLoop(Label* on_tos_equals_current_position) = 0; |
83 | virtual void CheckNotAtStart(int cp_offset, Label* on_not_at_start) = 0; |
84 | virtual void CheckNotBackReference(int start_reg, bool read_backward, |
85 | Label* on_no_match) = 0; |
86 | virtual void CheckNotBackReferenceIgnoreCase(int start_reg, |
87 | bool read_backward, bool unicode, |
88 | Label* on_no_match) = 0; |
89 | // Check the current character for a match with a literal character. If we |
90 | // fail to match then goto the on_failure label. End of input always |
91 | // matches. If the label is nullptr then we should pop a backtrack address |
92 | // off the stack and go to that. |
93 | virtual void CheckNotCharacter(unsigned c, Label* on_not_equal) = 0; |
94 | virtual void CheckNotCharacterAfterAnd(unsigned c, |
95 | unsigned and_with, |
96 | Label* on_not_equal) = 0; |
97 | // Subtract a constant from the current character, then and with the given |
98 | // constant and then check for a match with c. |
99 | virtual void CheckNotCharacterAfterMinusAnd(uc16 c, |
100 | uc16 minus, |
101 | uc16 and_with, |
102 | Label* on_not_equal) = 0; |
103 | virtual void CheckCharacterInRange(uc16 from, |
104 | uc16 to, // Both inclusive. |
105 | Label* on_in_range) = 0; |
106 | virtual void CheckCharacterNotInRange(uc16 from, |
107 | uc16 to, // Both inclusive. |
108 | Label* on_not_in_range) = 0; |
109 | |
110 | // The current character (modulus the kTableSize) is looked up in the byte |
111 | // array, and if the found byte is non-zero, we jump to the on_bit_set label. |
112 | virtual void CheckBitInTable(Handle<ByteArray> table, Label* on_bit_set) = 0; |
113 | |
114 | // Checks whether the given offset from the current position is before |
115 | // the end of the string. May overwrite the current character. |
116 | virtual void CheckPosition(int cp_offset, Label* on_outside_input); |
117 | // Check whether a standard/default character class matches the current |
118 | // character. Returns false if the type of special character class does |
119 | // not have custom support. |
120 | // May clobber the current loaded character. |
121 | virtual bool CheckSpecialCharacterClass(uc16 type, Label* on_no_match); |
122 | virtual void Fail() = 0; |
123 | virtual Handle<HeapObject> GetCode(Handle<String> source) = 0; |
124 | virtual void GoTo(Label* label) = 0; |
125 | // Check whether a register is >= a given constant and go to a label if it |
126 | // is. Backtracks instead if the label is nullptr. |
127 | virtual void IfRegisterGE(int reg, int comparand, Label* if_ge) = 0; |
128 | // Check whether a register is < a given constant and go to a label if it is. |
129 | // Backtracks instead if the label is nullptr. |
130 | virtual void IfRegisterLT(int reg, int comparand, Label* if_lt) = 0; |
131 | // Check whether a register is == to the current position and go to a |
132 | // label if it is. |
133 | virtual void IfRegisterEqPos(int reg, Label* if_eq) = 0; |
134 | virtual IrregexpImplementation Implementation() = 0; |
135 | virtual void LoadCurrentCharacter(int cp_offset, |
136 | Label* on_end_of_input, |
137 | bool check_bounds = true, |
138 | int characters = 1) = 0; |
139 | virtual void PopCurrentPosition() = 0; |
140 | virtual void PopRegister(int register_index) = 0; |
141 | // Pushes the label on the backtrack stack, so that a following Backtrack |
142 | // will go to this label. Always checks the backtrack stack limit. |
143 | virtual void PushBacktrack(Label* label) = 0; |
144 | virtual void PushCurrentPosition() = 0; |
145 | virtual void PushRegister(int register_index, |
146 | StackCheckFlag check_stack_limit) = 0; |
147 | virtual void ReadCurrentPositionFromRegister(int reg) = 0; |
148 | virtual void ReadStackPointerFromRegister(int reg) = 0; |
149 | virtual void SetCurrentPositionFromEnd(int by) = 0; |
150 | virtual void SetRegister(int register_index, int to) = 0; |
151 | // Return whether the matching (with a global regexp) will be restarted. |
152 | virtual bool Succeed() = 0; |
153 | virtual void WriteCurrentPositionToRegister(int reg, int cp_offset) = 0; |
154 | virtual void ClearRegisters(int reg_from, int reg_to) = 0; |
155 | virtual void WriteStackPointerToRegister(int reg) = 0; |
156 | |
157 | // Compares two-byte strings case insensitively. |
158 | // Called from generated RegExp code. |
159 | static int CaseInsensitiveCompareUC16(Address byte_offset1, |
160 | Address byte_offset2, |
161 | size_t byte_length, Isolate* isolate); |
162 | |
163 | // Check that we are not in the middle of a surrogate pair. |
164 | void CheckNotInSurrogatePair(int cp_offset, Label* on_failure); |
165 | |
166 | // Controls the generation of large inlined constants in the code. |
167 | void set_slow_safe(bool ssc) { slow_safe_compiler_ = ssc; } |
168 | bool slow_safe() { return slow_safe_compiler_; } |
169 | |
170 | enum GlobalMode { |
171 | NOT_GLOBAL, |
172 | GLOBAL_NO_ZERO_LENGTH_CHECK, |
173 | GLOBAL, |
174 | GLOBAL_UNICODE |
175 | }; |
176 | // Set whether the regular expression has the global flag. Exiting due to |
177 | // a failure in a global regexp may still mean success overall. |
178 | inline void set_global_mode(GlobalMode mode) { global_mode_ = mode; } |
179 | inline bool global() { return global_mode_ != NOT_GLOBAL; } |
180 | inline bool global_with_zero_length_check() { |
181 | return global_mode_ == GLOBAL || global_mode_ == GLOBAL_UNICODE; |
182 | } |
183 | inline bool global_unicode() { return global_mode_ == GLOBAL_UNICODE; } |
184 | |
185 | Isolate* isolate() const { return isolate_; } |
186 | Zone* zone() const { return zone_; } |
187 | |
188 | private: |
189 | bool slow_safe_compiler_; |
190 | GlobalMode global_mode_; |
191 | Isolate* isolate_; |
192 | Zone* zone_; |
193 | }; |
194 | |
195 | class NativeRegExpMacroAssembler: public RegExpMacroAssembler { |
196 | public: |
197 | // Type of input string to generate code for. |
198 | enum Mode { LATIN1 = 1, UC16 = 2 }; |
199 | |
200 | // Result of calling generated native RegExp code. |
201 | // RETRY: Something significant changed during execution, and the matching |
202 | // should be retried from scratch. |
203 | // EXCEPTION: Something failed during execution. If no exception has been |
204 | // thrown, it's an internal out-of-memory, and the caller should |
205 | // throw the exception. |
206 | // FAILURE: Matching failed. |
207 | // SUCCESS: Matching succeeded, and the output array has been filled with |
208 | // capture positions. |
209 | enum Result { RETRY = -2, EXCEPTION = -1, FAILURE = 0, SUCCESS = 1 }; |
210 | |
211 | NativeRegExpMacroAssembler(Isolate* isolate, Zone* zone); |
212 | ~NativeRegExpMacroAssembler() override; |
213 | bool CanReadUnaligned() override; |
214 | |
215 | // Returns a {Result} sentinel, or the number of successful matches. |
216 | static int Match(Handle<Code> regexp, Handle<String> subject, |
217 | int* offsets_vector, int offsets_vector_length, |
218 | int previous_index, Isolate* isolate); |
219 | |
220 | // Called from RegExp if the backtrack stack limit is hit. |
221 | // Tries to expand the stack. Returns the new stack-pointer if |
222 | // successful, and updates the stack_top address, or returns 0 if unable |
223 | // to grow the stack. |
224 | // This function must not trigger a garbage collection. |
225 | static Address GrowStack(Address stack_pointer, Address* stack_top, |
226 | Isolate* isolate); |
227 | |
228 | static const byte* StringCharacterPosition( |
229 | String subject, int start_index, const DisallowHeapAllocation& no_gc); |
230 | |
231 | static int CheckStackGuardState(Isolate* isolate, int start_index, |
232 | bool is_direct_call, Address* return_address, |
233 | Code re_code, Address* subject, |
234 | const byte** input_start, |
235 | const byte** input_end); |
236 | |
237 | // Byte map of one byte characters with a 0xff if the character is a word |
238 | // character (digit, letter or underscore) and 0x00 otherwise. |
239 | // Used by generated RegExp code. |
240 | static const byte word_character_map[256]; |
241 | |
242 | static Address word_character_map_address() { |
243 | return reinterpret_cast<Address>(&word_character_map[0]); |
244 | } |
245 | |
246 | // Returns a {Result} sentinel, or the number of successful matches. |
247 | V8_EXPORT_PRIVATE static int Execute(Code code, String input, |
248 | int start_offset, |
249 | const byte* input_start, |
250 | const byte* input_end, int* output, |
251 | int output_size, Isolate* isolate); |
252 | }; |
253 | |
254 | } // namespace internal |
255 | } // namespace v8 |
256 | |
257 | #endif // V8_REGEXP_REGEXP_MACRO_ASSEMBLER_H_ |
258 | |