regexp-macro-assembler-irregexp.cc 12.5 KB
Newer Older
1
// Copyright 2008-2009 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"
#include "ast.h"
#include "bytecodes-irregexp.h"
#include "regexp-macro-assembler.h"
#include "regexp-macro-assembler-irregexp.h"
33
#include "regexp-macro-assembler-irregexp-inl.h"
34 35


36 37
namespace v8 {
namespace internal {
38

39
#ifdef V8_INTERPRETED_REGEXP
40

41 42 43 44
RegExpMacroAssemblerIrregexp::RegExpMacroAssemblerIrregexp(Vector<byte> buffer,
                                                           Zone* zone)
    : RegExpMacroAssembler(zone),
      buffer_(buffer),
45
      pc_(0),
46
      own_buffer_(false),
47 48
      advance_current_end_(kInvalidPC),
      isolate_(zone->isolate()) { }
49 50


51
RegExpMacroAssemblerIrregexp::~RegExpMacroAssemblerIrregexp() {
52
  if (backtrack_.is_linked()) backtrack_.Unuse();
53
  if (own_buffer_) buffer_.Dispose();
54 55 56 57 58 59 60 61 62 63
}


RegExpMacroAssemblerIrregexp::IrregexpImplementation
RegExpMacroAssemblerIrregexp::Implementation() {
  return kBytecodeImplementation;
}


void RegExpMacroAssemblerIrregexp::Bind(Label* l) {
64
  advance_current_end_ = kInvalidPC;
65 66 67 68 69
  ASSERT(!l->is_bound());
  if (l->is_linked()) {
    int pos = l->pos();
    while (pos != 0) {
      int fixup = pos;
70 71
      pos = *reinterpret_cast<int32_t*>(buffer_.start() + fixup);
      *reinterpret_cast<uint32_t*>(buffer_.start() + fixup) = pc_;
72 73 74
    }
  }
  l->bind_to(pc_);
75 76 77 78
}


void RegExpMacroAssemblerIrregexp::EmitOrLink(Label* l) {
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
79
  if (l == NULL) l = &backtrack_;
80 81 82 83 84 85 86 87 88 89
  if (l->is_bound()) {
    Emit32(l->pos());
  } else {
    int pos = 0;
    if (l->is_linked()) {
      pos = l->pos();
    }
    l->link_to(pc_);
    Emit32(pos);
  }
90 91 92 93
}


void RegExpMacroAssemblerIrregexp::PopRegister(int register_index) {
94 95
  ASSERT(register_index >= 0);
  ASSERT(register_index <= kMaxRegister);
96
  Emit(BC_POP_REGISTER, register_index);
97 98 99
}


100 101 102
void RegExpMacroAssemblerIrregexp::PushRegister(
    int register_index,
    StackCheckFlag check_stack_limit) {
103
  ASSERT(register_index >= 0);
104
  ASSERT(register_index <= kMaxRegister);
105
  Emit(BC_PUSH_REGISTER, register_index);
106 107 108 109
}


void RegExpMacroAssemblerIrregexp::WriteCurrentPositionToRegister(
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
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);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
114
  Emit32(cp_offset);  // Current position offset.
115 116 117
}


118 119 120 121 122
void RegExpMacroAssemblerIrregexp::ClearRegisters(int reg_from, int reg_to) {
  ASSERT(reg_from <= reg_to);
  for (int reg = reg_from; reg <= reg_to; reg++) {
    SetRegister(reg, -1);
  }
123 124 125
}


126 127
void RegExpMacroAssemblerIrregexp::ReadCurrentPositionFromRegister(
    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 134 135
}


void RegExpMacroAssemblerIrregexp::WriteStackPointerToRegister(
    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 142 143
}


void RegExpMacroAssemblerIrregexp::ReadStackPointerFromRegister(
    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
}


150 151 152 153 154 155
void RegExpMacroAssemblerIrregexp::SetCurrentPositionFromEnd(int by) {
  ASSERT(is_uint24(by));
  Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
}


156
void 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 164
}


void 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 172
}


void RegExpMacroAssemblerIrregexp::PopCurrentPosition() {
173
  Emit(BC_POP_CP, 0);
174 175 176 177
}


void RegExpMacroAssemblerIrregexp::PushCurrentPosition() {
178
  Emit(BC_PUSH_CP, 0);
179 180 181 182
}


void RegExpMacroAssemblerIrregexp::Backtrack() {
183
  Emit(BC_POP_BT, 0);
184 185 186 187
}


void RegExpMacroAssemblerIrregexp::GoTo(Label* l) {
188 189 190 191 192 193 194 195 196 197 198
  if (advance_current_end_ == pc_) {
    // Combine advance current and goto.
    pc_ = advance_current_start_;
    Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
    EmitOrLink(l);
    advance_current_end_ = kInvalidPC;
  } else {
    // Regular goto.
    Emit(BC_GOTO, 0);
    EmitOrLink(l);
  }
199 200 201 202
}


void RegExpMacroAssemblerIrregexp::PushBacktrack(Label* l) {
203
  Emit(BC_PUSH_BT, 0);
204
  EmitOrLink(l);
205 206 207
}


208
bool RegExpMacroAssemblerIrregexp::Succeed() {
209
  Emit(BC_SUCCEED, 0);
210
  return false;  // Restart matching for global regexp not supported.
211 212 213 214
}


void RegExpMacroAssemblerIrregexp::Fail() {
215
  Emit(BC_FAIL, 0);
216 217 218 219
}


void RegExpMacroAssemblerIrregexp::AdvanceCurrentPosition(int by) {
220 221
  ASSERT(by >= kMinCPOffset);
  ASSERT(by <= kMaxCPOffset);
222 223
  advance_current_start_ = pc_;
  advance_current_offset_ = by;
224
  Emit(BC_ADVANCE_CP, by);
225
  advance_current_end_ = pc_;
226 227 228
}


erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
229 230
void RegExpMacroAssemblerIrregexp::CheckGreedyLoop(
      Label* on_tos_equals_current_position) {
231
  Emit(BC_CHECK_GREEDY, 0);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
232
  EmitOrLink(on_tos_equals_current_position);
233 234 235 236
}


void RegExpMacroAssemblerIrregexp::LoadCurrentCharacter(int cp_offset,
237 238 239
                                                        Label* on_failure,
                                                        bool check_bounds,
                                                        int characters) {
240 241
  ASSERT(cp_offset >= kMinCPOffset);
  ASSERT(cp_offset <= kMaxCPOffset);
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
  int bytecode;
  if (check_bounds) {
    if (characters == 4) {
      bytecode = BC_LOAD_4_CURRENT_CHARS;
    } else if (characters == 2) {
      bytecode = BC_LOAD_2_CURRENT_CHARS;
    } else {
      ASSERT(characters == 1);
      bytecode = BC_LOAD_CURRENT_CHAR;
    }
  } else {
    if (characters == 4) {
      bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
    } else if (characters == 2) {
      bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
    } else {
      ASSERT(characters == 1);
      bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
    }
  }
262
  Emit(bytecode, cp_offset);
263
  if (check_bounds) EmitOrLink(on_failure);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
264 265 266
}


267 268
void RegExpMacroAssemblerIrregexp::CheckCharacterLT(uc16 limit,
                                                    Label* on_less) {
269
  Emit(BC_CHECK_LT, limit);
270
  EmitOrLink(on_less);
271 272 273 274 275
}


void RegExpMacroAssemblerIrregexp::CheckCharacterGT(uc16 limit,
                                                    Label* on_greater) {
276
  Emit(BC_CHECK_GT, limit);
277
  EmitOrLink(on_greater);
278 279 280
}


281
void RegExpMacroAssemblerIrregexp::CheckCharacter(uint32_t c, Label* on_equal) {
282 283 284 285 286 287
  if (c > MAX_FIRST_ARG) {
    Emit(BC_CHECK_4_CHARS, 0);
    Emit32(c);
  } else {
    Emit(BC_CHECK_CHAR, c);
  }
288
  EmitOrLink(on_equal);
289 290 291
}


292
void RegExpMacroAssemblerIrregexp::CheckAtStart(Label* on_at_start) {
293
  Emit(BC_CHECK_AT_START, 0);
294 295 296 297
  EmitOrLink(on_at_start);
}


298
void RegExpMacroAssemblerIrregexp::CheckNotAtStart(Label* on_not_at_start) {
299
  Emit(BC_CHECK_NOT_AT_START, 0);
300 301 302 303
  EmitOrLink(on_not_at_start);
}


304
void RegExpMacroAssemblerIrregexp::CheckNotCharacter(uint32_t c,
305
                                                     Label* on_not_equal) {
306 307 308 309 310 311
  if (c > MAX_FIRST_ARG) {
    Emit(BC_CHECK_NOT_4_CHARS, 0);
    Emit32(c);
  } else {
    Emit(BC_CHECK_NOT_CHAR, c);
  }
312
  EmitOrLink(on_not_equal);
313 314 315
}


316 317 318 319
void RegExpMacroAssemblerIrregexp::CheckCharacterAfterAnd(
    uint32_t c,
    uint32_t mask,
    Label* on_equal) {
320 321 322 323 324 325
  if (c > MAX_FIRST_ARG) {
    Emit(BC_AND_CHECK_4_CHARS, 0);
    Emit32(c);
  } else {
    Emit(BC_AND_CHECK_CHAR, c);
  }
326 327 328 329 330 331 332 333
  Emit32(mask);
  EmitOrLink(on_equal);
}


void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterAnd(
    uint32_t c,
    uint32_t mask,
334
    Label* on_not_equal) {
335 336 337 338 339 340
  if (c > MAX_FIRST_ARG) {
    Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
    Emit32(c);
  } else {
    Emit(BC_AND_CHECK_NOT_CHAR, c);
  }
341
  Emit32(mask);
342
  EmitOrLink(on_not_equal);
343 344 345
}


346
void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterMinusAnd(
347
    uc16 c,
348
    uc16 minus,
349 350
    uc16 mask,
    Label* on_not_equal) {
351
  Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
352
  Emit16(minus);
353 354
  Emit16(mask);
  EmitOrLink(on_not_equal);
355 356 357
}


358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393
void RegExpMacroAssemblerIrregexp::CheckCharacterInRange(
    uc16 from,
    uc16 to,
    Label* on_in_range) {
  Emit(BC_CHECK_CHAR_IN_RANGE, 0);
  Emit16(from);
  Emit16(to);
  EmitOrLink(on_in_range);
}


void RegExpMacroAssemblerIrregexp::CheckCharacterNotInRange(
    uc16 from,
    uc16 to,
    Label* on_not_in_range) {
  Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
  Emit16(from);
  Emit16(to);
  EmitOrLink(on_not_in_range);
}


void RegExpMacroAssemblerIrregexp::CheckBitInTable(
    Handle<ByteArray> table, Label* on_bit_set) {
  Emit(BC_CHECK_BIT_IN_TABLE, 0);
  EmitOrLink(on_bit_set);
  for (int i = 0; i < kTableSize; i += kBitsPerByte) {
    int byte = 0;
    for (int j = 0; j < kBitsPerByte; j++) {
      if (table->get(i + j) != 0) byte |= 1 << j;
    }
    Emit8(byte);
  }
}


394
void RegExpMacroAssemblerIrregexp::CheckNotBackReference(int start_reg,
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
395
                                                         Label* on_not_equal) {
396 397
  ASSERT(start_reg >= 0);
  ASSERT(start_reg <= kMaxRegister);
398
  Emit(BC_CHECK_NOT_BACK_REF, start_reg);
399
  EmitOrLink(on_not_equal);
400 401 402
}


403
void RegExpMacroAssemblerIrregexp::CheckNotBackReferenceIgnoreCase(
404 405
    int start_reg,
    Label* on_not_equal) {
406 407
  ASSERT(start_reg >= 0);
  ASSERT(start_reg <= kMaxRegister);
408
  Emit(BC_CHECK_NOT_BACK_REF_NO_CASE, start_reg);
409
  EmitOrLink(on_not_equal);
410 411 412
}


413 414
void RegExpMacroAssemblerIrregexp::IfRegisterLT(int register_index,
                                                int comparand,
415
                                                Label* on_less_than) {
416 417
  ASSERT(register_index >= 0);
  ASSERT(register_index <= kMaxRegister);
418 419
  Emit(BC_CHECK_REGISTER_LT, register_index);
  Emit32(comparand);
420
  EmitOrLink(on_less_than);
421 422 423 424 425
}


void RegExpMacroAssemblerIrregexp::IfRegisterGE(int register_index,
                                                int comparand,
426
                                                Label* on_greater_or_equal) {
427 428
  ASSERT(register_index >= 0);
  ASSERT(register_index <= kMaxRegister);
429 430
  Emit(BC_CHECK_REGISTER_GE, register_index);
  Emit32(comparand);
431
  EmitOrLink(on_greater_or_equal);
432 433 434
}


435 436
void RegExpMacroAssemblerIrregexp::IfRegisterEqPos(int register_index,
                                                   Label* on_eq) {
437 438
  ASSERT(register_index >= 0);
  ASSERT(register_index <= kMaxRegister);
439
  Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
440 441 442 443
  EmitOrLink(on_eq);
}


444 445
Handle<HeapObject> RegExpMacroAssemblerIrregexp::GetCode(
    Handle<String> source) {
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
446
  Bind(&backtrack_);
447
  Emit(BC_POP_BT, 0);
448
  Handle<ByteArray> array = isolate_->factory()->NewByteArray(length());
449
  Copy(array->GetDataStartAddress());
450 451 452
  return array;
}

453 454 455 456 457 458 459

int RegExpMacroAssemblerIrregexp::length() {
  return pc_;
}


void RegExpMacroAssemblerIrregexp::Copy(Address a) {
460
  OS::MemCopy(a, buffer_.start(), length());
461 462 463 464 465 466 467 468
}


void RegExpMacroAssemblerIrregexp::Expand() {
  bool old_buffer_was_our_own = own_buffer_;
  Vector<byte> old_buffer = buffer_;
  buffer_ = Vector<byte>::New(old_buffer.length() * 2);
  own_buffer_ = true;
469
  OS::MemCopy(buffer_.start(), old_buffer.start(), old_buffer.length());
470 471 472 473 474
  if (old_buffer_was_our_own) {
    old_buffer.Dispose();
  }
}

475
#endif  // V8_INTERPRETED_REGEXP
476

477
} }  // namespace v8::internal