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