1// Copyright 2008-2009 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "v8.h"
29#include "ast.h"
30#include "bytecodes-irregexp.h"
31#include "regexp-macro-assembler.h"
32#include "regexp-macro-assembler-irregexp.h"
33#include "regexp-macro-assembler-irregexp-inl.h"
34
35
36namespace v8 {
37namespace internal {
38
39#ifdef V8_INTERPRETED_REGEXP
40
41RegExpMacroAssemblerIrregexp::RegExpMacroAssemblerIrregexp(Vector<byte> buffer,
42                                                           Zone* zone)
43    : RegExpMacroAssembler(zone),
44      buffer_(buffer),
45      pc_(0),
46      own_buffer_(false),
47      advance_current_end_(kInvalidPC),
48      isolate_(zone->isolate()) { }
49
50
51RegExpMacroAssemblerIrregexp::~RegExpMacroAssemblerIrregexp() {
52  if (backtrack_.is_linked()) backtrack_.Unuse();
53  if (own_buffer_) buffer_.Dispose();
54}
55
56
57RegExpMacroAssemblerIrregexp::IrregexpImplementation
58RegExpMacroAssemblerIrregexp::Implementation() {
59  return kBytecodeImplementation;
60}
61
62
63void RegExpMacroAssemblerIrregexp::Bind(Label* l) {
64  advance_current_end_ = kInvalidPC;
65  ASSERT(!l->is_bound());
66  if (l->is_linked()) {
67    int pos = l->pos();
68    while (pos != 0) {
69      int fixup = pos;
70      pos = *reinterpret_cast<int32_t*>(buffer_.start() + fixup);
71      *reinterpret_cast<uint32_t*>(buffer_.start() + fixup) = pc_;
72    }
73  }
74  l->bind_to(pc_);
75}
76
77
78void RegExpMacroAssemblerIrregexp::EmitOrLink(Label* l) {
79  if (l == NULL) l = &backtrack_;
80  if (l->is_bound()) {
81    Emit32(l->pos());
82  } else {
83    int pos = 0;
84    if (l->is_linked()) {
85      pos = l->pos();
86    }
87    l->link_to(pc_);
88    Emit32(pos);
89  }
90}
91
92
93void RegExpMacroAssemblerIrregexp::PopRegister(int register_index) {
94  ASSERT(register_index >= 0);
95  ASSERT(register_index <= kMaxRegister);
96  Emit(BC_POP_REGISTER, register_index);
97}
98
99
100void RegExpMacroAssemblerIrregexp::PushRegister(
101    int register_index,
102    StackCheckFlag check_stack_limit) {
103  ASSERT(register_index >= 0);
104  ASSERT(register_index <= kMaxRegister);
105  Emit(BC_PUSH_REGISTER, register_index);
106}
107
108
109void RegExpMacroAssemblerIrregexp::WriteCurrentPositionToRegister(
110    int register_index, int cp_offset) {
111  ASSERT(register_index >= 0);
112  ASSERT(register_index <= kMaxRegister);
113  Emit(BC_SET_REGISTER_TO_CP, register_index);
114  Emit32(cp_offset);  // Current position offset.
115}
116
117
118void RegExpMacroAssemblerIrregexp::ClearRegisters(int reg_from, int reg_to) {
119  ASSERT(reg_from <= reg_to);
120  for (int reg = reg_from; reg <= reg_to; reg++) {
121    SetRegister(reg, -1);
122  }
123}
124
125
126void RegExpMacroAssemblerIrregexp::ReadCurrentPositionFromRegister(
127    int register_index) {
128  ASSERT(register_index >= 0);
129  ASSERT(register_index <= kMaxRegister);
130  Emit(BC_SET_CP_TO_REGISTER, register_index);
131}
132
133
134void RegExpMacroAssemblerIrregexp::WriteStackPointerToRegister(
135    int register_index) {
136  ASSERT(register_index >= 0);
137  ASSERT(register_index <= kMaxRegister);
138  Emit(BC_SET_REGISTER_TO_SP, register_index);
139}
140
141
142void RegExpMacroAssemblerIrregexp::ReadStackPointerFromRegister(
143    int register_index) {
144  ASSERT(register_index >= 0);
145  ASSERT(register_index <= kMaxRegister);
146  Emit(BC_SET_SP_TO_REGISTER, register_index);
147}
148
149
150void RegExpMacroAssemblerIrregexp::SetCurrentPositionFromEnd(int by) {
151  ASSERT(is_uint24(by));
152  Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
153}
154
155
156void RegExpMacroAssemblerIrregexp::SetRegister(int register_index, int to) {
157  ASSERT(register_index >= 0);
158  ASSERT(register_index <= kMaxRegister);
159  Emit(BC_SET_REGISTER, register_index);
160  Emit32(to);
161}
162
163
164void RegExpMacroAssemblerIrregexp::AdvanceRegister(int register_index, int by) {
165  ASSERT(register_index >= 0);
166  ASSERT(register_index <= kMaxRegister);
167  Emit(BC_ADVANCE_REGISTER, register_index);
168  Emit32(by);
169}
170
171
172void RegExpMacroAssemblerIrregexp::PopCurrentPosition() {
173  Emit(BC_POP_CP, 0);
174}
175
176
177void RegExpMacroAssemblerIrregexp::PushCurrentPosition() {
178  Emit(BC_PUSH_CP, 0);
179}
180
181
182void RegExpMacroAssemblerIrregexp::Backtrack() {
183  Emit(BC_POP_BT, 0);
184}
185
186
187void RegExpMacroAssemblerIrregexp::GoTo(Label* l) {
188  if (advance_current_end_ == pc_) {
189    // Combine advance current and goto.
190    pc_ = advance_current_start_;
191    Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
192    EmitOrLink(l);
193    advance_current_end_ = kInvalidPC;
194  } else {
195    // Regular goto.
196    Emit(BC_GOTO, 0);
197    EmitOrLink(l);
198  }
199}
200
201
202void RegExpMacroAssemblerIrregexp::PushBacktrack(Label* l) {
203  Emit(BC_PUSH_BT, 0);
204  EmitOrLink(l);
205}
206
207
208bool RegExpMacroAssemblerIrregexp::Succeed() {
209  Emit(BC_SUCCEED, 0);
210  return false;  // Restart matching for global regexp not supported.
211}
212
213
214void RegExpMacroAssemblerIrregexp::Fail() {
215  Emit(BC_FAIL, 0);
216}
217
218
219void RegExpMacroAssemblerIrregexp::AdvanceCurrentPosition(int by) {
220  ASSERT(by >= kMinCPOffset);
221  ASSERT(by <= kMaxCPOffset);
222  advance_current_start_ = pc_;
223  advance_current_offset_ = by;
224  Emit(BC_ADVANCE_CP, by);
225  advance_current_end_ = pc_;
226}
227
228
229void RegExpMacroAssemblerIrregexp::CheckGreedyLoop(
230      Label* on_tos_equals_current_position) {
231  Emit(BC_CHECK_GREEDY, 0);
232  EmitOrLink(on_tos_equals_current_position);
233}
234
235
236void RegExpMacroAssemblerIrregexp::LoadCurrentCharacter(int cp_offset,
237                                                        Label* on_failure,
238                                                        bool check_bounds,
239                                                        int characters) {
240  ASSERT(cp_offset >= kMinCPOffset);
241  ASSERT(cp_offset <= kMaxCPOffset);
242  int bytecode;
243  if (check_bounds) {
244    if (characters == 4) {
245      bytecode = BC_LOAD_4_CURRENT_CHARS;
246    } else if (characters == 2) {
247      bytecode = BC_LOAD_2_CURRENT_CHARS;
248    } else {
249      ASSERT(characters == 1);
250      bytecode = BC_LOAD_CURRENT_CHAR;
251    }
252  } else {
253    if (characters == 4) {
254      bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
255    } else if (characters == 2) {
256      bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
257    } else {
258      ASSERT(characters == 1);
259      bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
260    }
261  }
262  Emit(bytecode, cp_offset);
263  if (check_bounds) EmitOrLink(on_failure);
264}
265
266
267void RegExpMacroAssemblerIrregexp::CheckCharacterLT(uc16 limit,
268                                                    Label* on_less) {
269  Emit(BC_CHECK_LT, limit);
270  EmitOrLink(on_less);
271}
272
273
274void RegExpMacroAssemblerIrregexp::CheckCharacterGT(uc16 limit,
275                                                    Label* on_greater) {
276  Emit(BC_CHECK_GT, limit);
277  EmitOrLink(on_greater);
278}
279
280
281void RegExpMacroAssemblerIrregexp::CheckCharacter(uint32_t c, Label* on_equal) {
282  if (c > MAX_FIRST_ARG) {
283    Emit(BC_CHECK_4_CHARS, 0);
284    Emit32(c);
285  } else {
286    Emit(BC_CHECK_CHAR, c);
287  }
288  EmitOrLink(on_equal);
289}
290
291
292void RegExpMacroAssemblerIrregexp::CheckAtStart(Label* on_at_start) {
293  Emit(BC_CHECK_AT_START, 0);
294  EmitOrLink(on_at_start);
295}
296
297
298void RegExpMacroAssemblerIrregexp::CheckNotAtStart(Label* on_not_at_start) {
299  Emit(BC_CHECK_NOT_AT_START, 0);
300  EmitOrLink(on_not_at_start);
301}
302
303
304void RegExpMacroAssemblerIrregexp::CheckNotCharacter(uint32_t c,
305                                                     Label* on_not_equal) {
306  if (c > MAX_FIRST_ARG) {
307    Emit(BC_CHECK_NOT_4_CHARS, 0);
308    Emit32(c);
309  } else {
310    Emit(BC_CHECK_NOT_CHAR, c);
311  }
312  EmitOrLink(on_not_equal);
313}
314
315
316void RegExpMacroAssemblerIrregexp::CheckCharacterAfterAnd(
317    uint32_t c,
318    uint32_t mask,
319    Label* on_equal) {
320  if (c > MAX_FIRST_ARG) {
321    Emit(BC_AND_CHECK_4_CHARS, 0);
322    Emit32(c);
323  } else {
324    Emit(BC_AND_CHECK_CHAR, c);
325  }
326  Emit32(mask);
327  EmitOrLink(on_equal);
328}
329
330
331void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterAnd(
332    uint32_t c,
333    uint32_t mask,
334    Label* on_not_equal) {
335  if (c > MAX_FIRST_ARG) {
336    Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
337    Emit32(c);
338  } else {
339    Emit(BC_AND_CHECK_NOT_CHAR, c);
340  }
341  Emit32(mask);
342  EmitOrLink(on_not_equal);
343}
344
345
346void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterMinusAnd(
347    uc16 c,
348    uc16 minus,
349    uc16 mask,
350    Label* on_not_equal) {
351  Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
352  Emit16(minus);
353  Emit16(mask);
354  EmitOrLink(on_not_equal);
355}
356
357
358void RegExpMacroAssemblerIrregexp::CheckCharacterInRange(
359    uc16 from,
360    uc16 to,
361    Label* on_in_range) {
362  Emit(BC_CHECK_CHAR_IN_RANGE, 0);
363  Emit16(from);
364  Emit16(to);
365  EmitOrLink(on_in_range);
366}
367
368
369void RegExpMacroAssemblerIrregexp::CheckCharacterNotInRange(
370    uc16 from,
371    uc16 to,
372    Label* on_not_in_range) {
373  Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
374  Emit16(from);
375  Emit16(to);
376  EmitOrLink(on_not_in_range);
377}
378
379
380void RegExpMacroAssemblerIrregexp::CheckBitInTable(
381    Handle<ByteArray> table, Label* on_bit_set) {
382  Emit(BC_CHECK_BIT_IN_TABLE, 0);
383  EmitOrLink(on_bit_set);
384  for (int i = 0; i < kTableSize; i += kBitsPerByte) {
385    int byte = 0;
386    for (int j = 0; j < kBitsPerByte; j++) {
387      if (table->get(i + j) != 0) byte |= 1 << j;
388    }
389    Emit8(byte);
390  }
391}
392
393
394void RegExpMacroAssemblerIrregexp::CheckNotBackReference(int start_reg,
395                                                         Label* on_not_equal) {
396  ASSERT(start_reg >= 0);
397  ASSERT(start_reg <= kMaxRegister);
398  Emit(BC_CHECK_NOT_BACK_REF, start_reg);
399  EmitOrLink(on_not_equal);
400}
401
402
403void RegExpMacroAssemblerIrregexp::CheckNotBackReferenceIgnoreCase(
404    int start_reg,
405    Label* on_not_equal) {
406  ASSERT(start_reg >= 0);
407  ASSERT(start_reg <= kMaxRegister);
408  Emit(BC_CHECK_NOT_BACK_REF_NO_CASE, start_reg);
409  EmitOrLink(on_not_equal);
410}
411
412
413void RegExpMacroAssemblerIrregexp::IfRegisterLT(int register_index,
414                                                int comparand,
415                                                Label* on_less_than) {
416  ASSERT(register_index >= 0);
417  ASSERT(register_index <= kMaxRegister);
418  Emit(BC_CHECK_REGISTER_LT, register_index);
419  Emit32(comparand);
420  EmitOrLink(on_less_than);
421}
422
423
424void RegExpMacroAssemblerIrregexp::IfRegisterGE(int register_index,
425                                                int comparand,
426                                                Label* on_greater_or_equal) {
427  ASSERT(register_index >= 0);
428  ASSERT(register_index <= kMaxRegister);
429  Emit(BC_CHECK_REGISTER_GE, register_index);
430  Emit32(comparand);
431  EmitOrLink(on_greater_or_equal);
432}
433
434
435void RegExpMacroAssemblerIrregexp::IfRegisterEqPos(int register_index,
436                                                   Label* on_eq) {
437  ASSERT(register_index >= 0);
438  ASSERT(register_index <= kMaxRegister);
439  Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
440  EmitOrLink(on_eq);
441}
442
443
444Handle<HeapObject> RegExpMacroAssemblerIrregexp::GetCode(
445    Handle<String> source) {
446  Bind(&backtrack_);
447  Emit(BC_POP_BT, 0);
448  Handle<ByteArray> array = isolate_->factory()->NewByteArray(length());
449  Copy(array->GetDataStartAddress());
450  return array;
451}
452
453
454int RegExpMacroAssemblerIrregexp::length() {
455  return pc_;
456}
457
458
459void RegExpMacroAssemblerIrregexp::Copy(Address a) {
460  OS::MemCopy(a, buffer_.start(), length());
461}
462
463
464void RegExpMacroAssemblerIrregexp::Expand() {
465  bool old_buffer_was_our_own = own_buffer_;
466  Vector<byte> old_buffer = buffer_;
467  buffer_ = Vector<byte>::New(old_buffer.length() * 2);
468  own_buffer_ = true;
469  OS::MemCopy(buffer_.start(), old_buffer.start(), old_buffer.length());
470  if (old_buffer_was_our_own) {
471    old_buffer.Dispose();
472  }
473}
474
475#endif  // V8_INTERPRETED_REGEXP
476
477} }  // namespace v8::internal
478