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
15namespace v8 {
16namespace internal {
17
18RegExpMacroAssemblerIrregexp::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
29RegExpMacroAssemblerIrregexp::~RegExpMacroAssemblerIrregexp() {
30  if (backtrack_.is_linked()) backtrack_.Unuse();
31  if (own_buffer_) buffer_.Dispose();
32}
33
34
35RegExpMacroAssemblerIrregexp::IrregexpImplementation
36RegExpMacroAssemblerIrregexp::Implementation() {
37  return kBytecodeImplementation;
38}
39
40
41void 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
56void RegExpMacroAssemblerIrregexp::EmitOrLink(Label* l) {
57  if (l == NULL) 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
71void RegExpMacroAssemblerIrregexp::PopRegister(int register_index) {
72  DCHECK(register_index >= 0);
73  DCHECK(register_index <= kMaxRegister);
74  Emit(BC_POP_REGISTER, register_index);
75}
76
77
78void RegExpMacroAssemblerIrregexp::PushRegister(
79    int register_index,
80    StackCheckFlag check_stack_limit) {
81  DCHECK(register_index >= 0);
82  DCHECK(register_index <= kMaxRegister);
83  Emit(BC_PUSH_REGISTER, register_index);
84}
85
86
87void RegExpMacroAssemblerIrregexp::WriteCurrentPositionToRegister(
88    int register_index, int cp_offset) {
89  DCHECK(register_index >= 0);
90  DCHECK(register_index <= kMaxRegister);
91  Emit(BC_SET_REGISTER_TO_CP, register_index);
92  Emit32(cp_offset);  // Current position offset.
93}
94
95
96void 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
104void RegExpMacroAssemblerIrregexp::ReadCurrentPositionFromRegister(
105    int register_index) {
106  DCHECK(register_index >= 0);
107  DCHECK(register_index <= kMaxRegister);
108  Emit(BC_SET_CP_TO_REGISTER, register_index);
109}
110
111
112void RegExpMacroAssemblerIrregexp::WriteStackPointerToRegister(
113    int register_index) {
114  DCHECK(register_index >= 0);
115  DCHECK(register_index <= kMaxRegister);
116  Emit(BC_SET_REGISTER_TO_SP, register_index);
117}
118
119
120void RegExpMacroAssemblerIrregexp::ReadStackPointerFromRegister(
121    int register_index) {
122  DCHECK(register_index >= 0);
123  DCHECK(register_index <= kMaxRegister);
124  Emit(BC_SET_SP_TO_REGISTER, register_index);
125}
126
127
128void RegExpMacroAssemblerIrregexp::SetCurrentPositionFromEnd(int by) {
129  DCHECK(is_uint24(by));
130  Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
131}
132
133
134void RegExpMacroAssemblerIrregexp::SetRegister(int register_index, int to) {
135  DCHECK(register_index >= 0);
136  DCHECK(register_index <= kMaxRegister);
137  Emit(BC_SET_REGISTER, register_index);
138  Emit32(to);
139}
140
141
142void RegExpMacroAssemblerIrregexp::AdvanceRegister(int register_index, int by) {
143  DCHECK(register_index >= 0);
144  DCHECK(register_index <= kMaxRegister);
145  Emit(BC_ADVANCE_REGISTER, register_index);
146  Emit32(by);
147}
148
149
150void RegExpMacroAssemblerIrregexp::PopCurrentPosition() {
151  Emit(BC_POP_CP, 0);
152}
153
154
155void RegExpMacroAssemblerIrregexp::PushCurrentPosition() {
156  Emit(BC_PUSH_CP, 0);
157}
158
159
160void RegExpMacroAssemblerIrregexp::Backtrack() {
161  Emit(BC_POP_BT, 0);
162}
163
164
165void 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
180void RegExpMacroAssemblerIrregexp::PushBacktrack(Label* l) {
181  Emit(BC_PUSH_BT, 0);
182  EmitOrLink(l);
183}
184
185
186bool RegExpMacroAssemblerIrregexp::Succeed() {
187  Emit(BC_SUCCEED, 0);
188  return false;  // Restart matching for global regexp not supported.
189}
190
191
192void RegExpMacroAssemblerIrregexp::Fail() {
193  Emit(BC_FAIL, 0);
194}
195
196
197void RegExpMacroAssemblerIrregexp::AdvanceCurrentPosition(int by) {
198  DCHECK(by >= kMinCPOffset);
199  DCHECK(by <= kMaxCPOffset);
200  advance_current_start_ = pc_;
201  advance_current_offset_ = by;
202  Emit(BC_ADVANCE_CP, by);
203  advance_current_end_ = pc_;
204}
205
206
207void 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
214void RegExpMacroAssemblerIrregexp::LoadCurrentCharacter(int cp_offset,
215                                                        Label* on_failure,
216                                                        bool check_bounds,
217                                                        int characters) {
218  DCHECK(cp_offset >= kMinCPOffset);
219  DCHECK(cp_offset <= kMaxCPOffset);
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(characters == 1);
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(characters == 1);
237      bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
238    }
239  }
240  Emit(bytecode, cp_offset);
241  if (check_bounds) EmitOrLink(on_failure);
242}
243
244
245void RegExpMacroAssemblerIrregexp::CheckCharacterLT(uc16 limit,
246                                                    Label* on_less) {
247  Emit(BC_CHECK_LT, limit);
248  EmitOrLink(on_less);
249}
250
251
252void RegExpMacroAssemblerIrregexp::CheckCharacterGT(uc16 limit,
253                                                    Label* on_greater) {
254  Emit(BC_CHECK_GT, limit);
255  EmitOrLink(on_greater);
256}
257
258
259void 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
270void RegExpMacroAssemblerIrregexp::CheckAtStart(Label* on_at_start) {
271  Emit(BC_CHECK_AT_START, 0);
272  EmitOrLink(on_at_start);
273}
274
275
276void 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
283void 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
295void 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
310void 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
325void 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
337void 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
348void 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
359void 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
373void RegExpMacroAssemblerIrregexp::CheckNotBackReference(int start_reg,
374                                                         bool read_backward,
375                                                         Label* on_not_equal) {
376  DCHECK(start_reg >= 0);
377  DCHECK(start_reg <= kMaxRegister);
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
384void RegExpMacroAssemblerIrregexp::CheckNotBackReferenceIgnoreCase(
385    int start_reg, bool read_backward, bool unicode, Label* on_not_equal) {
386  DCHECK(start_reg >= 0);
387  DCHECK(start_reg <= kMaxRegister);
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
397void RegExpMacroAssemblerIrregexp::IfRegisterLT(int register_index,
398                                                int comparand,
399                                                Label* on_less_than) {
400  DCHECK(register_index >= 0);
401  DCHECK(register_index <= kMaxRegister);
402  Emit(BC_CHECK_REGISTER_LT, register_index);
403  Emit32(comparand);
404  EmitOrLink(on_less_than);
405}
406
407
408void RegExpMacroAssemblerIrregexp::IfRegisterGE(int register_index,
409                                                int comparand,
410                                                Label* on_greater_or_equal) {
411  DCHECK(register_index >= 0);
412  DCHECK(register_index <= kMaxRegister);
413  Emit(BC_CHECK_REGISTER_GE, register_index);
414  Emit32(comparand);
415  EmitOrLink(on_greater_or_equal);
416}
417
418
419void RegExpMacroAssemblerIrregexp::IfRegisterEqPos(int register_index,
420                                                   Label* on_eq) {
421  DCHECK(register_index >= 0);
422  DCHECK(register_index <= kMaxRegister);
423  Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
424  EmitOrLink(on_eq);
425}
426
427
428Handle<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
438int RegExpMacroAssemblerIrregexp::length() {
439  return pc_;
440}
441
442
443void RegExpMacroAssemblerIrregexp::Copy(Address a) {
444  MemCopy(a, buffer_.start(), length());
445}
446
447
448void RegExpMacroAssemblerIrregexp::Expand() {
449  bool old_buffer_was_our_own = own_buffer_;
450  Vector<byte> old_buffer = buffer_;
451  buffer_ = Vector<byte>::New(old_buffer.length() * 2);
452  own_buffer_ = true;
453  MemCopy(buffer_.start(), old_buffer.start(), old_buffer.length());
454  if (old_buffer_was_our_own) {
455    old_buffer.Dispose();
456  }
457}
458
459}  // namespace internal
460}  // namespace v8
461
462#endif  // V8_INTERPRETED_REGEXP
463