Line data Source code
1 : // Copyright 2008-2009 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 : #include "src/regexp/regexp-macro-assembler-irregexp.h"
6 :
7 : #include "src/ast/ast.h"
8 : #include "src/objects-inl.h"
9 : #include "src/regexp/bytecodes-irregexp.h"
10 : #include "src/regexp/regexp-macro-assembler-irregexp-inl.h"
11 : #include "src/regexp/regexp-macro-assembler.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 3246 : RegExpMacroAssemblerIrregexp::RegExpMacroAssemblerIrregexp(Isolate* isolate,
17 : Zone* zone)
18 : : RegExpMacroAssembler(isolate, zone),
19 : buffer_(Vector<byte>::New(1024)),
20 : pc_(0),
21 : own_buffer_(true),
22 : advance_current_end_(kInvalidPC),
23 6492 : isolate_(isolate) {}
24 :
25 9733 : RegExpMacroAssemblerIrregexp::~RegExpMacroAssemblerIrregexp() {
26 3246 : if (backtrack_.is_linked()) backtrack_.Unuse();
27 3246 : if (own_buffer_) buffer_.Dispose();
28 6487 : }
29 :
30 :
31 : RegExpMacroAssemblerIrregexp::IrregexpImplementation
32 0 : RegExpMacroAssemblerIrregexp::Implementation() {
33 0 : return kBytecodeImplementation;
34 : }
35 :
36 :
37 640572 : void RegExpMacroAssemblerIrregexp::Bind(Label* l) {
38 320286 : advance_current_end_ = kInvalidPC;
39 : DCHECK(!l->is_bound());
40 320286 : if (l->is_linked()) {
41 193438 : int pos = l->pos();
42 864613 : while (pos != 0) {
43 : int fixup = pos;
44 477737 : pos = *reinterpret_cast<int32_t*>(buffer_.start() + fixup);
45 477737 : *reinterpret_cast<uint32_t*>(buffer_.start() + fixup) = pc_;
46 : }
47 : }
48 320286 : l->bind_to(pc_);
49 320286 : }
50 :
51 :
52 1071524 : void RegExpMacroAssemblerIrregexp::EmitOrLink(Label* l) {
53 535762 : if (l == nullptr) l = &backtrack_;
54 535762 : if (l->is_bound()) {
55 58025 : Emit32(l->pos());
56 : } else {
57 : int pos = 0;
58 477737 : if (l->is_linked()) {
59 284299 : pos = l->pos();
60 : }
61 477737 : l->link_to(pc_);
62 477737 : Emit32(pos);
63 : }
64 535762 : }
65 :
66 :
67 10299 : void RegExpMacroAssemblerIrregexp::PopRegister(int register_index) {
68 : DCHECK_LE(0, register_index);
69 : DCHECK_GE(kMaxRegister, register_index);
70 10299 : Emit(BC_POP_REGISTER, register_index);
71 10299 : }
72 :
73 :
74 10299 : void RegExpMacroAssemblerIrregexp::PushRegister(
75 : int register_index,
76 : StackCheckFlag check_stack_limit) {
77 : DCHECK_LE(0, register_index);
78 : DCHECK_GE(kMaxRegister, register_index);
79 10299 : Emit(BC_PUSH_REGISTER, register_index);
80 10299 : }
81 :
82 :
83 53076 : void RegExpMacroAssemblerIrregexp::WriteCurrentPositionToRegister(
84 : int register_index, int cp_offset) {
85 : DCHECK_LE(0, register_index);
86 : DCHECK_GE(kMaxRegister, register_index);
87 53076 : Emit(BC_SET_REGISTER_TO_CP, register_index);
88 53076 : Emit32(cp_offset); // Current position offset.
89 53076 : }
90 :
91 :
92 22514 : void RegExpMacroAssemblerIrregexp::ClearRegisters(int reg_from, int reg_to) {
93 : DCHECK(reg_from <= reg_to);
94 65561 : for (int reg = reg_from; reg <= reg_to; reg++) {
95 43047 : SetRegister(reg, -1);
96 : }
97 22514 : }
98 :
99 :
100 880 : void RegExpMacroAssemblerIrregexp::ReadCurrentPositionFromRegister(
101 : int register_index) {
102 : DCHECK_LE(0, register_index);
103 : DCHECK_GE(kMaxRegister, register_index);
104 880 : Emit(BC_SET_CP_TO_REGISTER, register_index);
105 880 : }
106 :
107 :
108 873 : void RegExpMacroAssemblerIrregexp::WriteStackPointerToRegister(
109 : int register_index) {
110 : DCHECK_LE(0, register_index);
111 : DCHECK_GE(kMaxRegister, register_index);
112 873 : Emit(BC_SET_REGISTER_TO_SP, register_index);
113 873 : }
114 :
115 :
116 880 : void RegExpMacroAssemblerIrregexp::ReadStackPointerFromRegister(
117 : int register_index) {
118 : DCHECK_LE(0, register_index);
119 : DCHECK_GE(kMaxRegister, register_index);
120 880 : Emit(BC_SET_SP_TO_REGISTER, register_index);
121 880 : }
122 :
123 :
124 37 : void RegExpMacroAssemblerIrregexp::SetCurrentPositionFromEnd(int by) {
125 : DCHECK(is_uint24(by));
126 37 : Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
127 37 : }
128 :
129 :
130 43694 : void RegExpMacroAssemblerIrregexp::SetRegister(int register_index, int to) {
131 : DCHECK_LE(0, register_index);
132 : DCHECK_GE(kMaxRegister, register_index);
133 43694 : Emit(BC_SET_REGISTER, register_index);
134 43694 : Emit32(to);
135 43694 : }
136 :
137 :
138 697 : void RegExpMacroAssemblerIrregexp::AdvanceRegister(int register_index, int by) {
139 : DCHECK_LE(0, register_index);
140 : DCHECK_GE(kMaxRegister, register_index);
141 697 : Emit(BC_ADVANCE_REGISTER, register_index);
142 697 : Emit32(by);
143 697 : }
144 :
145 :
146 65384 : void RegExpMacroAssemblerIrregexp::PopCurrentPosition() {
147 65384 : Emit(BC_POP_CP, 0);
148 65384 : }
149 :
150 :
151 67419 : void RegExpMacroAssemblerIrregexp::PushCurrentPosition() {
152 67419 : Emit(BC_PUSH_CP, 0);
153 67419 : }
154 :
155 :
156 3409 : void RegExpMacroAssemblerIrregexp::Backtrack() {
157 3409 : Emit(BC_POP_BT, 0);
158 3409 : }
159 :
160 :
161 181351 : void RegExpMacroAssemblerIrregexp::GoTo(Label* l) {
162 181351 : if (advance_current_end_ == pc_) {
163 : // Combine advance current and goto.
164 18684 : pc_ = advance_current_start_;
165 18684 : Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
166 18684 : EmitOrLink(l);
167 18684 : advance_current_end_ = kInvalidPC;
168 : } else {
169 : // Regular goto.
170 162667 : Emit(BC_GOTO, 0);
171 162667 : EmitOrLink(l);
172 : }
173 181351 : }
174 :
175 :
176 71383 : void RegExpMacroAssemblerIrregexp::PushBacktrack(Label* l) {
177 71383 : Emit(BC_PUSH_BT, 0);
178 71383 : EmitOrLink(l);
179 71383 : }
180 :
181 :
182 4354 : bool RegExpMacroAssemblerIrregexp::Succeed() {
183 4354 : Emit(BC_SUCCEED, 0);
184 4354 : return false; // Restart matching for global regexp not supported.
185 : }
186 :
187 :
188 3251 : void RegExpMacroAssemblerIrregexp::Fail() {
189 3251 : Emit(BC_FAIL, 0);
190 3251 : }
191 :
192 :
193 72808 : void RegExpMacroAssemblerIrregexp::AdvanceCurrentPosition(int by) {
194 : DCHECK_LE(kMinCPOffset, by);
195 : DCHECK_GE(kMaxCPOffset, by);
196 72808 : advance_current_start_ = pc_;
197 72808 : advance_current_offset_ = by;
198 72808 : Emit(BC_ADVANCE_CP, by);
199 72808 : advance_current_end_ = pc_;
200 72808 : }
201 :
202 :
203 2035 : void RegExpMacroAssemblerIrregexp::CheckGreedyLoop(
204 : Label* on_tos_equals_current_position) {
205 2035 : Emit(BC_CHECK_GREEDY, 0);
206 2035 : EmitOrLink(on_tos_equals_current_position);
207 2035 : }
208 :
209 :
210 189947 : void RegExpMacroAssemblerIrregexp::LoadCurrentCharacter(int cp_offset,
211 : Label* on_failure,
212 : bool check_bounds,
213 : int characters) {
214 : DCHECK_LE(kMinCPOffset, cp_offset);
215 : DCHECK_GE(kMaxCPOffset, cp_offset);
216 : int bytecode;
217 189947 : if (check_bounds) {
218 76724 : if (characters == 4) {
219 : bytecode = BC_LOAD_4_CURRENT_CHARS;
220 76724 : } else if (characters == 2) {
221 : bytecode = BC_LOAD_2_CURRENT_CHARS;
222 : } else {
223 : DCHECK_EQ(1, characters);
224 : bytecode = BC_LOAD_CURRENT_CHAR;
225 : }
226 : } else {
227 113223 : if (characters == 4) {
228 : bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
229 113223 : } else if (characters == 2) {
230 : bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
231 : } else {
232 : DCHECK_EQ(1, characters);
233 : bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
234 : }
235 : }
236 189947 : Emit(bytecode, cp_offset);
237 189947 : if (check_bounds) EmitOrLink(on_failure);
238 189947 : }
239 :
240 :
241 2309 : void RegExpMacroAssemblerIrregexp::CheckCharacterLT(uc16 limit,
242 : Label* on_less) {
243 2309 : Emit(BC_CHECK_LT, limit);
244 2309 : EmitOrLink(on_less);
245 2309 : }
246 :
247 :
248 2893 : void RegExpMacroAssemblerIrregexp::CheckCharacterGT(uc16 limit,
249 : Label* on_greater) {
250 2893 : Emit(BC_CHECK_GT, limit);
251 2893 : EmitOrLink(on_greater);
252 2893 : }
253 :
254 :
255 39290 : void RegExpMacroAssemblerIrregexp::CheckCharacter(uint32_t c, Label* on_equal) {
256 39290 : if (c > MAX_FIRST_ARG) {
257 0 : Emit(BC_CHECK_4_CHARS, 0);
258 0 : Emit32(c);
259 : } else {
260 39290 : Emit(BC_CHECK_CHAR, c);
261 : }
262 39290 : EmitOrLink(on_equal);
263 39290 : }
264 :
265 :
266 51 : void RegExpMacroAssemblerIrregexp::CheckAtStart(Label* on_at_start) {
267 51 : Emit(BC_CHECK_AT_START, 0);
268 51 : EmitOrLink(on_at_start);
269 51 : }
270 :
271 :
272 490 : void RegExpMacroAssemblerIrregexp::CheckNotAtStart(int cp_offset,
273 : Label* on_not_at_start) {
274 490 : Emit(BC_CHECK_NOT_AT_START, cp_offset);
275 490 : EmitOrLink(on_not_at_start);
276 490 : }
277 :
278 :
279 143393 : void RegExpMacroAssemblerIrregexp::CheckNotCharacter(uint32_t c,
280 : Label* on_not_equal) {
281 143393 : if (c > MAX_FIRST_ARG) {
282 0 : Emit(BC_CHECK_NOT_4_CHARS, 0);
283 0 : Emit32(c);
284 : } else {
285 143393 : Emit(BC_CHECK_NOT_CHAR, c);
286 : }
287 143393 : EmitOrLink(on_not_equal);
288 143393 : }
289 :
290 :
291 1003 : void RegExpMacroAssemblerIrregexp::CheckCharacterAfterAnd(
292 : uint32_t c,
293 : uint32_t mask,
294 : Label* on_equal) {
295 1003 : if (c > MAX_FIRST_ARG) {
296 0 : Emit(BC_AND_CHECK_4_CHARS, 0);
297 0 : Emit32(c);
298 : } else {
299 1003 : Emit(BC_AND_CHECK_CHAR, c);
300 : }
301 1003 : Emit32(mask);
302 1003 : EmitOrLink(on_equal);
303 1003 : }
304 :
305 :
306 1272 : void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterAnd(
307 : uint32_t c,
308 : uint32_t mask,
309 : Label* on_not_equal) {
310 1272 : if (c > MAX_FIRST_ARG) {
311 0 : Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
312 0 : Emit32(c);
313 : } else {
314 1272 : Emit(BC_AND_CHECK_NOT_CHAR, c);
315 : }
316 1272 : Emit32(mask);
317 1272 : EmitOrLink(on_not_equal);
318 1272 : }
319 :
320 :
321 17 : void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterMinusAnd(
322 : uc16 c,
323 : uc16 minus,
324 : uc16 mask,
325 : Label* on_not_equal) {
326 17 : Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
327 17 : Emit16(minus);
328 17 : Emit16(mask);
329 17 : EmitOrLink(on_not_equal);
330 17 : }
331 :
332 :
333 3765 : void RegExpMacroAssemblerIrregexp::CheckCharacterInRange(
334 : uc16 from,
335 : uc16 to,
336 : Label* on_in_range) {
337 3765 : Emit(BC_CHECK_CHAR_IN_RANGE, 0);
338 3765 : Emit16(from);
339 3765 : Emit16(to);
340 3765 : EmitOrLink(on_in_range);
341 3765 : }
342 :
343 :
344 6951 : void RegExpMacroAssemblerIrregexp::CheckCharacterNotInRange(
345 : uc16 from,
346 : uc16 to,
347 : Label* on_not_in_range) {
348 6951 : Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
349 6951 : Emit16(from);
350 6951 : Emit16(to);
351 6951 : EmitOrLink(on_not_in_range);
352 6951 : }
353 :
354 :
355 1564 : void RegExpMacroAssemblerIrregexp::CheckBitInTable(
356 : Handle<ByteArray> table, Label* on_bit_set) {
357 1564 : Emit(BC_CHECK_BIT_IN_TABLE, 0);
358 1564 : EmitOrLink(on_bit_set);
359 26588 : for (int i = 0; i < kTableSize; i += kBitsPerByte) {
360 : int byte = 0;
361 200192 : for (int j = 0; j < kBitsPerByte; j++) {
362 400384 : if (table->get(i + j) != 0) byte |= 1 << j;
363 : }
364 25024 : Emit8(byte);
365 : }
366 1564 : }
367 :
368 :
369 121 : void RegExpMacroAssemblerIrregexp::CheckNotBackReference(int start_reg,
370 : bool read_backward,
371 : Label* on_not_equal) {
372 : DCHECK_LE(0, start_reg);
373 : DCHECK_GE(kMaxRegister, start_reg);
374 : Emit(read_backward ? BC_CHECK_NOT_BACK_REF_BACKWARD : BC_CHECK_NOT_BACK_REF,
375 121 : start_reg);
376 121 : EmitOrLink(on_not_equal);
377 121 : }
378 :
379 :
380 333 : void RegExpMacroAssemblerIrregexp::CheckNotBackReferenceIgnoreCase(
381 : int start_reg, bool read_backward, bool unicode, Label* on_not_equal) {
382 : DCHECK_LE(0, start_reg);
383 : DCHECK_GE(kMaxRegister, start_reg);
384 : Emit(read_backward ? (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD
385 : : BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD)
386 : : (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE
387 : : BC_CHECK_NOT_BACK_REF_NO_CASE),
388 333 : start_reg);
389 333 : EmitOrLink(on_not_equal);
390 333 : }
391 :
392 :
393 286 : void RegExpMacroAssemblerIrregexp::IfRegisterLT(int register_index,
394 : int comparand,
395 : Label* on_less_than) {
396 : DCHECK_LE(0, register_index);
397 : DCHECK_GE(kMaxRegister, register_index);
398 286 : Emit(BC_CHECK_REGISTER_LT, register_index);
399 286 : Emit32(comparand);
400 286 : EmitOrLink(on_less_than);
401 286 : }
402 :
403 :
404 480 : void RegExpMacroAssemblerIrregexp::IfRegisterGE(int register_index,
405 : int comparand,
406 : Label* on_greater_or_equal) {
407 : DCHECK_LE(0, register_index);
408 : DCHECK_GE(kMaxRegister, register_index);
409 480 : Emit(BC_CHECK_REGISTER_GE, register_index);
410 480 : Emit32(comparand);
411 480 : EmitOrLink(on_greater_or_equal);
412 480 : }
413 :
414 :
415 51 : void RegExpMacroAssemblerIrregexp::IfRegisterEqPos(int register_index,
416 : Label* on_eq) {
417 : DCHECK_LE(0, register_index);
418 : DCHECK_GE(kMaxRegister, register_index);
419 51 : Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
420 51 : EmitOrLink(on_eq);
421 51 : }
422 :
423 :
424 3246 : Handle<HeapObject> RegExpMacroAssemblerIrregexp::GetCode(
425 : Handle<String> source) {
426 3246 : Bind(&backtrack_);
427 3246 : Emit(BC_POP_BT, 0);
428 3246 : Handle<ByteArray> array = isolate_->factory()->NewByteArray(length());
429 : Copy(array->GetDataStartAddress());
430 3246 : return array;
431 : }
432 :
433 :
434 0 : int RegExpMacroAssemblerIrregexp::length() {
435 6492 : return pc_;
436 : }
437 :
438 0 : void RegExpMacroAssemblerIrregexp::Copy(byte* a) {
439 3246 : MemCopy(a, buffer_.start(), length());
440 0 : }
441 :
442 :
443 406 : void RegExpMacroAssemblerIrregexp::Expand() {
444 406 : bool old_buffer_was_our_own = own_buffer_;
445 406 : Vector<byte> old_buffer = buffer_;
446 812 : buffer_ = Vector<byte>::New(old_buffer.length() * 2);
447 406 : own_buffer_ = true;
448 406 : MemCopy(buffer_.start(), old_buffer.start(), old_buffer.length());
449 406 : if (old_buffer_was_our_own) {
450 : old_buffer.Dispose();
451 : }
452 406 : }
453 :
454 : } // namespace internal
455 178779 : } // namespace v8
|