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