jsregexp.cc 245 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/regexp/jsregexp.h"
6

7
#include "src/ast/ast.h"
8 9 10 11 12
#include "src/base/platform/platform.h"
#include "src/compilation-cache.h"
#include "src/compiler.h"
#include "src/execution.h"
#include "src/factory.h"
13
#include "src/isolate-inl.h"
14 15
#include "src/messages.h"
#include "src/ostreams.h"
16 17 18 19 20
#include "src/regexp/interpreter-irregexp.h"
#include "src/regexp/jsregexp-inl.h"
#include "src/regexp/regexp-macro-assembler.h"
#include "src/regexp/regexp-macro-assembler-irregexp.h"
#include "src/regexp/regexp-macro-assembler-tracer.h"
21
#include "src/regexp/regexp-parser.h"
22
#include "src/regexp/regexp-stack.h"
23
#include "src/runtime/runtime.h"
24
#include "src/splay-tree-inl.h"
25 26
#include "src/string-search.h"
#include "src/unicode-decoder.h"
27

28 29 30 31 32
#ifdef V8_I18N_SUPPORT
#include "unicode/uset.h"
#include "unicode/utypes.h"
#endif  // V8_I18N_SUPPORT

33 34
#ifndef V8_INTERPRETED_REGEXP
#if V8_TARGET_ARCH_IA32
35
#include "src/regexp/ia32/regexp-macro-assembler-ia32.h"
36
#elif V8_TARGET_ARCH_X64
37
#include "src/regexp/x64/regexp-macro-assembler-x64.h"
38
#elif V8_TARGET_ARCH_ARM64
39
#include "src/regexp/arm64/regexp-macro-assembler-arm64.h"
40
#elif V8_TARGET_ARCH_ARM
41
#include "src/regexp/arm/regexp-macro-assembler-arm.h"
42
#elif V8_TARGET_ARCH_PPC
43
#include "src/regexp/ppc/regexp-macro-assembler-ppc.h"
44 45
#elif V8_TARGET_ARCH_S390
#include "src/regexp/s390/regexp-macro-assembler-s390.h"
46
#elif V8_TARGET_ARCH_MIPS
47
#include "src/regexp/mips/regexp-macro-assembler-mips.h"
48
#elif V8_TARGET_ARCH_MIPS64
49
#include "src/regexp/mips64/regexp-macro-assembler-mips64.h"
50
#elif V8_TARGET_ARCH_X87
51
#include "src/regexp/x87/regexp-macro-assembler-x87.h"
52 53 54 55 56 57 58 59 60
#else
#error Unsupported target architecture.
#endif
#endif


namespace v8 {
namespace internal {

61 62 63 64 65 66 67
MUST_USE_RESULT
static inline MaybeHandle<Object> ThrowRegExpException(
    Handle<JSRegExp> re, Handle<String> pattern, Handle<String> error_text) {
  Isolate* isolate = re->GetIsolate();
  THROW_NEW_ERROR(isolate, NewSyntaxError(MessageTemplate::kMalformedRegExp,
                                          pattern, error_text),
                  Object);
68 69 70
}


71 72 73
inline void ThrowRegExpException(Handle<JSRegExp> re,
                                 Handle<String> error_text) {
  USE(ThrowRegExpException(re, Handle<String>(re->Pattern()), error_text));
74 75 76
}


77 78 79 80
ContainedInLattice AddRange(ContainedInLattice containment,
                            const int* ranges,
                            int ranges_length,
                            Interval new_range) {
81
  DCHECK((ranges_length & 1) == 1);
82
  DCHECK(ranges[ranges_length - 1] == String::kMaxCodePoint + 1);
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
  if (containment == kLatticeUnknown) return containment;
  bool inside = false;
  int last = 0;
  for (int i = 0; i < ranges_length; inside = !inside, last = ranges[i], i++) {
    // Consider the range from last to ranges[i].
    // We haven't got to the new range yet.
    if (ranges[i] <= new_range.from()) continue;
    // New range is wholly inside last-ranges[i].  Note that new_range.to() is
    // inclusive, but the values in ranges are not.
    if (last <= new_range.from() && new_range.to() < ranges[i]) {
      return Combine(containment, inside ? kLatticeIn : kLatticeOut);
    }
    return kLatticeUnknown;
  }
  return containment;
}


// More makes code generation slower, less makes V8 benchmark score lower.
const int kMaxLookaheadForBoyerMoore = 8;
// In a 3-character pattern you can maximally step forwards 3 characters
// at a time, which is not always enough to pay for the extra logic.
const int kPatternTooShortForBoyerMoore = 2;


// Identifies the sort of regexps where the regexp engine is faster
// than the code used for atom matches.
static bool HasFewDifferentCharacters(Handle<String> pattern) {
  int length = Min(kMaxLookaheadForBoyerMoore, pattern->length());
  if (length <= kPatternTooShortForBoyerMoore) return false;
  const int kMod = 128;
  bool character_found[kMod];
  int different = 0;
  memset(&character_found[0], 0, sizeof(character_found));
  for (int i = 0; i < length; i++) {
    int ch = (pattern->Get(i) & (kMod - 1));
    if (!character_found[ch]) {
      character_found[ch] = true;
      different++;
      // We declare a regexp low-alphabet if it has at least 3 times as many
      // characters as it has different characters.
      if (different * 3 > length) return false;
    }
  }
  return true;
}


131 132 133
// Generic RegExp methods. Dispatches to implementation specific methods.


134 135 136
MaybeHandle<Object> RegExpImpl::Compile(Handle<JSRegExp> re,
                                        Handle<String> pattern,
                                        JSRegExp::Flags flags) {
137
  Isolate* isolate = re->GetIsolate();
138
  Zone zone(isolate->allocator());
139
  CompilationCache* compilation_cache = isolate->compilation_cache();
140 141 142 143
  MaybeHandle<FixedArray> maybe_cached =
      compilation_cache->LookupRegExp(pattern, flags);
  Handle<FixedArray> cached;
  bool in_cache = maybe_cached.ToHandle(&cached);
144
  LOG(isolate, RegExpCompileEvent(re, in_cache));
145 146 147 148 149 150

  Handle<Object> result;
  if (in_cache) {
    re->set_data(*cached);
    return re;
  }
151
  pattern = String::Flatten(pattern);
152
  PostponeInterruptsScope postpone(isolate);
153
  RegExpCompileData parse_result;
154
  FlatStringReader reader(isolate, pattern);
155
  if (!RegExpParser::ParseRegExp(re->GetIsolate(), &zone, &reader, flags,
156
                                 &parse_result)) {
157
    // Throw an exception if we fail to parse the pattern.
158
    return ThrowRegExpException(re, pattern, parse_result.error);
159 160
  }

161 162
  bool has_been_compiled = false;

163 164
  if (parse_result.simple && !(flags & JSRegExp::kIgnoreCase) &&
      !(flags & JSRegExp::kSticky) && !HasFewDifferentCharacters(pattern)) {
165 166
    // Parse-tree is a single atom that is equal to the pattern.
    AtomCompile(re, pattern, flags, pattern);
167
    has_been_compiled = true;
168 169
  } else if (parse_result.tree->IsAtom() && !(flags & JSRegExp::kIgnoreCase) &&
             !(flags & JSRegExp::kSticky) && parse_result.capture_count == 0) {
170 171
    RegExpAtom* atom = parse_result.tree->AsAtom();
    Vector<const uc16> atom_pattern = atom->data();
172 173 174 175 176
    Handle<String> atom_string;
    ASSIGN_RETURN_ON_EXCEPTION(
        isolate, atom_string,
        isolate->factory()->NewStringFromTwoByte(atom_pattern),
        Object);
177 178 179 180 181 182
    if (!HasFewDifferentCharacters(atom_string)) {
      AtomCompile(re, pattern, flags, atom_string);
      has_been_compiled = true;
    }
  }
  if (!has_been_compiled) {
183 184
    IrregexpInitialize(re, pattern, flags, parse_result.capture_count);
  }
185
  DCHECK(re->data()->IsFixedArray());
186 187 188
  // Compilation succeeded so the data is set on the regexp
  // and we can store it in the cache.
  Handle<FixedArray> data(FixedArray::cast(re->data()));
189
  compilation_cache->PutRegExp(pattern, flags, data);
190 191 192 193 194

  return re;
}


195 196 197 198
MaybeHandle<Object> RegExpImpl::Exec(Handle<JSRegExp> regexp,
                                     Handle<String> subject,
                                     int index,
                                     Handle<JSArray> last_match_info) {
199 200 201 202
  switch (regexp->TypeTag()) {
    case JSRegExp::ATOM:
      return AtomExec(regexp, subject, index, last_match_info);
    case JSRegExp::IRREGEXP: {
203
      return IrregexpExec(regexp, subject, index, last_match_info);
204 205 206
    }
    default:
      UNREACHABLE();
207
      return MaybeHandle<Object>();
208 209 210 211 212 213 214 215 216 217 218
  }
}


// RegExp Atom implementation: Simple string search using indexOf.


void RegExpImpl::AtomCompile(Handle<JSRegExp> re,
                             Handle<String> pattern,
                             JSRegExp::Flags flags,
                             Handle<String> match_pattern) {
219 220 221 222 223
  re->GetIsolate()->factory()->SetRegExpAtomData(re,
                                                 JSRegExp::ATOM,
                                                 pattern,
                                                 flags,
                                                 match_pattern);
224 225 226 227 228 229 230
}


static void SetAtomLastCapture(FixedArray* array,
                               String* subject,
                               int from,
                               int to) {
231
  SealHandleScope shs(array->GetIsolate());
232 233 234 235 236 237 238 239
  RegExpImpl::SetLastCaptureCount(array, 2);
  RegExpImpl::SetLastSubject(array, subject);
  RegExpImpl::SetLastInput(array, subject);
  RegExpImpl::SetCapture(array, 0, from);
  RegExpImpl::SetCapture(array, 1, to);
}


240 241 242 243 244 245
int RegExpImpl::AtomExecRaw(Handle<JSRegExp> regexp,
                            Handle<String> subject,
                            int index,
                            int32_t* output,
                            int output_size) {
  Isolate* isolate = regexp->GetIsolate();
246

247 248
  DCHECK(0 <= index);
  DCHECK(index <= subject->length());
249

250 251
  subject = String::Flatten(subject);
  DisallowHeapAllocation no_gc;  // ensure vectors stay valid
252

253
  String* needle = String::cast(regexp->DataAt(JSRegExp::kAtomPatternIndex));
254
  int needle_len = needle->length();
255 256
  DCHECK(needle->IsFlat());
  DCHECK_LT(0, needle_len);
257

258 259 260
  if (index + needle_len > subject->length()) {
    return RegExpImpl::RE_FAILURE;
  }
261

262
  for (int i = 0; i < output_size; i += 2) {
263 264
    String::FlatContent needle_content = needle->GetFlatContent();
    String::FlatContent subject_content = subject->GetFlatContent();
265 266
    DCHECK(needle_content.IsFlat());
    DCHECK(subject_content.IsFlat());
267
    // dispatch on type of strings
268 269 270 271 272 273 274 275 276 277 278 279
    index =
        (needle_content.IsOneByte()
             ? (subject_content.IsOneByte()
                    ? SearchString(isolate, subject_content.ToOneByteVector(),
                                   needle_content.ToOneByteVector(), index)
                    : SearchString(isolate, subject_content.ToUC16Vector(),
                                   needle_content.ToOneByteVector(), index))
             : (subject_content.IsOneByte()
                    ? SearchString(isolate, subject_content.ToOneByteVector(),
                                   needle_content.ToUC16Vector(), index)
                    : SearchString(isolate, subject_content.ToUC16Vector(),
                                   needle_content.ToUC16Vector(), index)));
280 281 282 283 284 285 286
    if (index == -1) {
      return i / 2;  // Return number of matches.
    } else {
      output[i] = index;
      output[i+1] = index + needle_len;
      index += needle_len;
    }
287
  }
288 289
  return output_size / 2;
}
290

291 292 293 294 295 296 297 298 299 300 301 302 303 304 305

Handle<Object> RegExpImpl::AtomExec(Handle<JSRegExp> re,
                                    Handle<String> subject,
                                    int index,
                                    Handle<JSArray> last_match_info) {
  Isolate* isolate = re->GetIsolate();

  static const int kNumRegisters = 2;
  STATIC_ASSERT(kNumRegisters <= Isolate::kJSRegexpStaticOffsetsVectorSize);
  int32_t* output_registers = isolate->jsregexp_static_offsets_vector();

  int res = AtomExecRaw(re, subject, index, output_registers, kNumRegisters);

  if (res == RegExpImpl::RE_FAILURE) return isolate->factory()->null_value();

306 307
  DCHECK_EQ(res, RegExpImpl::RE_SUCCESS);
  SealHandleScope shs(isolate);
308 309
  FixedArray* array = FixedArray::cast(last_match_info->elements());
  SetAtomLastCapture(array, *subject, output_registers[0], output_registers[1]);
310 311 312 313 314 315 316
  return last_match_info;
}


// Irregexp implementation.

// Ensures that the regexp object contains a compiled version of the
317
// source for either one-byte or two-byte subject strings.
318 319 320 321
// If the compiled version doesn't already exist, it is compiled
// from the source pattern.
// If compilation fails, an exception is thrown and this function
// returns false.
322 323 324 325
bool RegExpImpl::EnsureCompiledIrregexp(Handle<JSRegExp> re,
                                        Handle<String> sample_subject,
                                        bool is_one_byte) {
  Object* compiled_code = re->DataAt(JSRegExp::code_index(is_one_byte));
326 327 328 329 330
#ifdef V8_INTERPRETED_REGEXP
  if (compiled_code->IsByteArray()) return true;
#else  // V8_INTERPRETED_REGEXP (RegExp native code)
  if (compiled_code->IsCode()) return true;
#endif
331 332
  // We could potentially have marked this as flushable, but have kept
  // a saved version if we did not flush it yet.
333
  Object* saved_code = re->DataAt(JSRegExp::saved_code_index(is_one_byte));
334 335
  if (saved_code->IsCode()) {
    // Reinstate the code in the original place.
336 337
    re->SetDataAt(JSRegExp::code_index(is_one_byte), saved_code);
    DCHECK(compiled_code->IsSmi());
338 339
    return true;
  }
340
  return CompileIrregexp(re, sample_subject, is_one_byte);
341 342 343
}


344 345
bool RegExpImpl::CompileIrregexp(Handle<JSRegExp> re,
                                 Handle<String> sample_subject,
346
                                 bool is_one_byte) {
347
  // Compile the RegExp.
348
  Isolate* isolate = re->GetIsolate();
349
  Zone zone(isolate->allocator());
350 351 352
  PostponeInterruptsScope postpone(isolate);
  // If we had a compilation error the last time this is saved at the
  // saved code index.
353
  Object* entry = re->DataAt(JSRegExp::code_index(is_one_byte));
354 355 356
  // When arriving here entry can only be a smi, either representing an
  // uncompiled regexp, a previous compilation error, or code that has
  // been flushed.
357
  DCHECK(entry->IsSmi());
358
  int entry_value = Smi::cast(entry)->value();
359
  DCHECK(entry_value == JSRegExp::kUninitializedValue ||
360 361 362 363 364 365 366
         entry_value == JSRegExp::kCompilationErrorValue ||
         (entry_value < JSRegExp::kCodeAgeMask && entry_value >= 0));

  if (entry_value == JSRegExp::kCompilationErrorValue) {
    // A previous compilation failed and threw an error which we store in
    // the saved code index (we store the error message, not the actual
    // error). Recreate the error object and throw it.
367 368
    Object* error_string = re->DataAt(JSRegExp::saved_code_index(is_one_byte));
    DCHECK(error_string->IsString());
369
    Handle<String> error_message(String::cast(error_string));
370
    ThrowRegExpException(re, error_message);
371 372 373 374 375 376
    return false;
  }

  JSRegExp::Flags flags = re->GetFlags();

  Handle<String> pattern(re->Pattern());
377
  pattern = String::Flatten(pattern);
378
  RegExpCompileData compile_data;
379
  FlatStringReader reader(isolate, pattern);
380 381
  if (!RegExpParser::ParseRegExp(isolate, &zone, &reader, flags,
                                 &compile_data)) {
382 383
    // Throw an exception if we fail to parse the pattern.
    // THIS SHOULD NOT HAPPEN. We already pre-parsed it successfully once.
384
    USE(ThrowRegExpException(re, pattern, compile_data.error));
385 386
    return false;
  }
387 388 389
  RegExpEngine::CompilationResult result =
      RegExpEngine::Compile(isolate, &zone, &compile_data, flags, pattern,
                            sample_subject, is_one_byte);
390 391
  if (result.error_message != NULL) {
    // Unable to compile regexp.
392 393 394
    Handle<String> error_message = isolate->factory()->NewStringFromUtf8(
        CStrVector(result.error_message)).ToHandleChecked();
    ThrowRegExpException(re, error_message);
395 396 397 398
    return false;
  }

  Handle<FixedArray> data = Handle<FixedArray>(FixedArray::cast(re->data()));
399
  data->set(JSRegExp::code_index(is_one_byte), result.code);
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
  int register_max = IrregexpMaxRegisterCount(*data);
  if (result.num_registers > register_max) {
    SetIrregexpMaxRegisterCount(*data, result.num_registers);
  }

  return true;
}


int RegExpImpl::IrregexpMaxRegisterCount(FixedArray* re) {
  return Smi::cast(
      re->get(JSRegExp::kIrregexpMaxRegisterCountIndex))->value();
}


void RegExpImpl::SetIrregexpMaxRegisterCount(FixedArray* re, int value) {
  re->set(JSRegExp::kIrregexpMaxRegisterCountIndex, Smi::FromInt(value));
}


int RegExpImpl::IrregexpNumberOfCaptures(FixedArray* re) {
  return Smi::cast(re->get(JSRegExp::kIrregexpCaptureCountIndex))->value();
}


int RegExpImpl::IrregexpNumberOfRegisters(FixedArray* re) {
  return Smi::cast(re->get(JSRegExp::kIrregexpMaxRegisterCountIndex))->value();
}


430 431
ByteArray* RegExpImpl::IrregexpByteCode(FixedArray* re, bool is_one_byte) {
  return ByteArray::cast(re->get(JSRegExp::code_index(is_one_byte)));
432 433 434
}


435 436
Code* RegExpImpl::IrregexpNativeCode(FixedArray* re, bool is_one_byte) {
  return Code::cast(re->get(JSRegExp::code_index(is_one_byte)));
437 438 439 440 441 442 443 444
}


void RegExpImpl::IrregexpInitialize(Handle<JSRegExp> re,
                                    Handle<String> pattern,
                                    JSRegExp::Flags flags,
                                    int capture_count) {
  // Initialize compiled code entries to null.
445 446 447 448 449
  re->GetIsolate()->factory()->SetRegExpIrregexpData(re,
                                                     JSRegExp::IRREGEXP,
                                                     pattern,
                                                     flags,
                                                     capture_count);
450 451 452 453
}


int RegExpImpl::IrregexpPrepare(Handle<JSRegExp> regexp,
454
                                Handle<String> subject) {
455
  subject = String::Flatten(subject);
456

457 458 459
  // Check representation of the underlying storage.
  bool is_one_byte = subject->IsOneByteRepresentationUnderneath();
  if (!EnsureCompiledIrregexp(regexp, subject, is_one_byte)) return -1;
460

461 462
#ifdef V8_INTERPRETED_REGEXP
  // Byte-code regexp needs space allocated for all its registers.
463 464 465 466 467
  // The result captures are copied to the start of the registers array
  // if the match succeeds.  This way those registers are not clobbered
  // when we set the last match info from last successful match.
  return IrregexpNumberOfRegisters(FixedArray::cast(regexp->data())) +
         (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
468 469 470 471 472 473 474 475
#else  // V8_INTERPRETED_REGEXP
  // Native regexp only needs room to output captures. Registers are handled
  // internally.
  return (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
#endif  // V8_INTERPRETED_REGEXP
}


476 477 478 479 480
int RegExpImpl::IrregexpExecRaw(Handle<JSRegExp> regexp,
                                Handle<String> subject,
                                int index,
                                int32_t* output,
                                int output_size) {
481 482 483
  Isolate* isolate = regexp->GetIsolate();

  Handle<FixedArray> irregexp(FixedArray::cast(regexp->data()), isolate);
484

485 486 487
  DCHECK(index >= 0);
  DCHECK(index <= subject->length());
  DCHECK(subject->IsFlat());
488

489
  bool is_one_byte = subject->IsOneByteRepresentationUnderneath();
490 491

#ifndef V8_INTERPRETED_REGEXP
492
  DCHECK(output_size >= (IrregexpNumberOfCaptures(*irregexp) + 1) * 2);
493
  do {
494 495
    EnsureCompiledIrregexp(regexp, subject, is_one_byte);
    Handle<Code> code(IrregexpNativeCode(*irregexp, is_one_byte), isolate);
496 497 498 499
    // The stack is used to allocate registers for the compiled regexp code.
    // This means that in case of failure, the output registers array is left
    // untouched and contains the capture results from the previous successful
    // match.  We can use that to set the last match info lazily.
500 501 502
    NativeRegExpMacroAssembler::Result res =
        NativeRegExpMacroAssembler::Match(code,
                                          subject,
503 504
                                          output,
                                          output_size,
505 506
                                          index,
                                          isolate);
507
    if (res != NativeRegExpMacroAssembler::RETRY) {
508
      DCHECK(res != NativeRegExpMacroAssembler::EXCEPTION ||
509
             isolate->has_pending_exception());
510 511 512 513 514 515 516 517 518 519 520 521
      STATIC_ASSERT(
          static_cast<int>(NativeRegExpMacroAssembler::SUCCESS) == RE_SUCCESS);
      STATIC_ASSERT(
          static_cast<int>(NativeRegExpMacroAssembler::FAILURE) == RE_FAILURE);
      STATIC_ASSERT(static_cast<int>(NativeRegExpMacroAssembler::EXCEPTION)
                    == RE_EXCEPTION);
      return static_cast<IrregexpResult>(res);
    }
    // If result is RETRY, the string has changed representation, and we
    // must restart from scratch.
    // In this case, it means we must make sure we are prepared to handle
    // the, potentially, different subject (the string can switch between
522
    // being internal and external, and even between being Latin1 and UC16,
523
    // but the characters are always the same).
524
    IrregexpPrepare(regexp, subject);
525
    is_one_byte = subject->IsOneByteRepresentationUnderneath();
526 527 528 529 530
  } while (true);
  UNREACHABLE();
  return RE_EXCEPTION;
#else  // V8_INTERPRETED_REGEXP

531
  DCHECK(output_size >= IrregexpNumberOfRegisters(*irregexp));
532 533 534 535
  // We must have done EnsureCompiledIrregexp, so we can get the number of
  // registers.
  int number_of_capture_registers =
      (IrregexpNumberOfCaptures(*irregexp) + 1) * 2;
536 537 538 539
  int32_t* raw_output = &output[number_of_capture_registers];
  // We do not touch the actual capture result registers until we know there
  // has been a match so that we can use those capture results to set the
  // last match info.
540
  for (int i = number_of_capture_registers - 1; i >= 0; i--) {
541
    raw_output[i] = -1;
542
  }
543 544
  Handle<ByteArray> byte_codes(IrregexpByteCode(*irregexp, is_one_byte),
                               isolate);
545

546 547 548
  IrregexpResult result = IrregexpInterpreter::Match(isolate,
                                                     byte_codes,
                                                     subject,
549
                                                     raw_output,
550
                                                     index);
551 552
  if (result == RE_SUCCESS) {
    // Copy capture results to the start of the registers array.
553
    MemCopy(output, raw_output, number_of_capture_registers * sizeof(int32_t));
554
  }
555
  if (result == RE_EXCEPTION) {
556
    DCHECK(!isolate->has_pending_exception());
557
    isolate->StackOverflow();
558
  }
559
  return result;
560 561 562 563
#endif  // V8_INTERPRETED_REGEXP
}


564 565 566 567
MaybeHandle<Object> RegExpImpl::IrregexpExec(Handle<JSRegExp> regexp,
                                             Handle<String> subject,
                                             int previous_index,
                                             Handle<JSArray> last_match_info) {
568
  Isolate* isolate = regexp->GetIsolate();
569
  DCHECK_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
570 571

  // Prepare space for the return values.
572
#if defined(V8_INTERPRETED_REGEXP) && defined(DEBUG)
573
  if (FLAG_trace_regexp_bytecodes) {
574
    String* pattern = regexp->Pattern();
575 576
    PrintF("\n\nRegexp match:   /%s/\n\n", pattern->ToCString().get());
    PrintF("\n\nSubject string: '%s'\n\n", subject->ToCString().get());
577 578
  }
#endif
579
  int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
580 581
  if (required_registers < 0) {
    // Compiling failed with an exception.
582 583
    DCHECK(isolate->has_pending_exception());
    return MaybeHandle<Object>();
584 585
  }

586 587 588 589
  int32_t* output_registers = NULL;
  if (required_registers > Isolate::kJSRegexpStaticOffsetsVectorSize) {
    output_registers = NewArray<int32_t>(required_registers);
  }
590
  base::SmartArrayPointer<int32_t> auto_release(output_registers);
591 592 593
  if (output_registers == NULL) {
    output_registers = isolate->jsregexp_static_offsets_vector();
  }
594

595 596
  int res = RegExpImpl::IrregexpExecRaw(
      regexp, subject, previous_index, output_registers, required_registers);
597
  if (res == RE_SUCCESS) {
598 599 600 601
    int capture_count =
        IrregexpNumberOfCaptures(FixedArray::cast(regexp->data()));
    return SetLastMatchInfo(
        last_match_info, subject, capture_count, output_registers);
602 603
  }
  if (res == RE_EXCEPTION) {
604 605
    DCHECK(isolate->has_pending_exception());
    return MaybeHandle<Object>();
606
  }
607
  DCHECK(res == RE_FAILURE);
608
  return isolate->factory()->null_value();
609 610 611
}


612 613 614 615 616 617 618
static void EnsureSize(Handle<JSArray> array, uint32_t minimum_size) {
  if (static_cast<uint32_t>(array->elements()->length()) < minimum_size) {
    JSArray::SetLength(array, minimum_size);
  }
}


619 620 621 622
Handle<JSArray> RegExpImpl::SetLastMatchInfo(Handle<JSArray> last_match_info,
                                             Handle<String> subject,
                                             int capture_count,
                                             int32_t* match) {
623
  DCHECK(last_match_info->HasFastObjectElements());
624
  int capture_register_count = (capture_count + 1) * 2;
625 626
  EnsureSize(last_match_info, capture_register_count + kLastMatchOverhead);
  DisallowHeapAllocation no_allocation;
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666
  FixedArray* array = FixedArray::cast(last_match_info->elements());
  if (match != NULL) {
    for (int i = 0; i < capture_register_count; i += 2) {
      SetCapture(array, i, match[i]);
      SetCapture(array, i + 1, match[i + 1]);
    }
  }
  SetLastCaptureCount(array, capture_register_count);
  SetLastSubject(array, *subject);
  SetLastInput(array, *subject);
  return last_match_info;
}


RegExpImpl::GlobalCache::GlobalCache(Handle<JSRegExp> regexp,
                                     Handle<String> subject,
                                     Isolate* isolate)
  : register_array_(NULL),
    register_array_size_(0),
    regexp_(regexp),
    subject_(subject) {
#ifdef V8_INTERPRETED_REGEXP
  bool interpreted = true;
#else
  bool interpreted = false;
#endif  // V8_INTERPRETED_REGEXP

  if (regexp_->TypeTag() == JSRegExp::ATOM) {
    static const int kAtomRegistersPerMatch = 2;
    registers_per_match_ = kAtomRegistersPerMatch;
    // There is no distinction between interpreted and native for atom regexps.
    interpreted = false;
  } else {
    registers_per_match_ = RegExpImpl::IrregexpPrepare(regexp_, subject_);
    if (registers_per_match_ < 0) {
      num_matches_ = -1;  // Signal exception.
      return;
    }
  }

667 668
  DCHECK_NE(0, regexp->GetFlags() & JSRegExp::kGlobal);
  if (!interpreted) {
669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
    register_array_size_ =
        Max(registers_per_match_, Isolate::kJSRegexpStaticOffsetsVectorSize);
    max_matches_ = register_array_size_ / registers_per_match_;
  } else {
    // Global loop in interpreted regexp is not implemented.  We choose
    // the size of the offsets vector so that it can only store one match.
    register_array_size_ = registers_per_match_;
    max_matches_ = 1;
  }

  if (register_array_size_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
    register_array_ = NewArray<int32_t>(register_array_size_);
  } else {
    register_array_ = isolate->jsregexp_static_offsets_vector();
  }

  // Set state so that fetching the results the first time triggers a call
  // to the compiled regexp.
  current_match_index_ = max_matches_ - 1;
  num_matches_ = max_matches_;
689 690
  DCHECK(registers_per_match_ >= 2);  // Each match has at least one capture.
  DCHECK_GE(register_array_size_, registers_per_match_);
691 692 693 694 695 696
  int32_t* last_match =
      &register_array_[current_match_index_ * registers_per_match_];
  last_match[0] = -1;
  last_match[1] = 0;
}

697 698 699 700 701 702 703 704 705 706
int RegExpImpl::GlobalCache::AdvanceZeroLength(int last_index) {
  if ((regexp_->GetFlags() & JSRegExp::kUnicode) != 0 &&
      last_index + 1 < subject_->length() &&
      unibrow::Utf16::IsLeadSurrogate(subject_->Get(last_index)) &&
      unibrow::Utf16::IsTrailSurrogate(subject_->Get(last_index + 1))) {
    // Advance over the surrogate pair.
    return last_index + 2;
  }
  return last_index + 1;
}
707

708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835
// -------------------------------------------------------------------
// Implementation of the Irregexp regular expression engine.
//
// The Irregexp regular expression engine is intended to be a complete
// implementation of ECMAScript regular expressions.  It generates either
// bytecodes or native code.

//   The Irregexp regexp engine is structured in three steps.
//   1) The parser generates an abstract syntax tree.  See ast.cc.
//   2) From the AST a node network is created.  The nodes are all
//      subclasses of RegExpNode.  The nodes represent states when
//      executing a regular expression.  Several optimizations are
//      performed on the node network.
//   3) From the nodes we generate either byte codes or native code
//      that can actually execute the regular expression (perform
//      the search).  The code generation step is described in more
//      detail below.

// Code generation.
//
//   The nodes are divided into four main categories.
//   * Choice nodes
//        These represent places where the regular expression can
//        match in more than one way.  For example on entry to an
//        alternation (foo|bar) or a repetition (*, +, ? or {}).
//   * Action nodes
//        These represent places where some action should be
//        performed.  Examples include recording the current position
//        in the input string to a register (in order to implement
//        captures) or other actions on register for example in order
//        to implement the counters needed for {} repetitions.
//   * Matching nodes
//        These attempt to match some element part of the input string.
//        Examples of elements include character classes, plain strings
//        or back references.
//   * End nodes
//        These are used to implement the actions required on finding
//        a successful match or failing to find a match.
//
//   The code generated (whether as byte codes or native code) maintains
//   some state as it runs.  This consists of the following elements:
//
//   * The capture registers.  Used for string captures.
//   * Other registers.  Used for counters etc.
//   * The current position.
//   * The stack of backtracking information.  Used when a matching node
//     fails to find a match and needs to try an alternative.
//
// Conceptual regular expression execution model:
//
//   There is a simple conceptual model of regular expression execution
//   which will be presented first.  The actual code generated is a more
//   efficient simulation of the simple conceptual model:
//
//   * Choice nodes are implemented as follows:
//     For each choice except the last {
//       push current position
//       push backtrack code location
//       <generate code to test for choice>
//       backtrack code location:
//       pop current position
//     }
//     <generate code to test for last choice>
//
//   * Actions nodes are generated as follows
//     <push affected registers on backtrack stack>
//     <generate code to perform action>
//     push backtrack code location
//     <generate code to test for following nodes>
//     backtrack code location:
//     <pop affected registers to restore their state>
//     <pop backtrack location from stack and go to it>
//
//   * Matching nodes are generated as follows:
//     if input string matches at current position
//       update current position
//       <generate code to test for following nodes>
//     else
//       <pop backtrack location from stack and go to it>
//
//   Thus it can be seen that the current position is saved and restored
//   by the choice nodes, whereas the registers are saved and restored by
//   by the action nodes that manipulate them.
//
//   The other interesting aspect of this model is that nodes are generated
//   at the point where they are needed by a recursive call to Emit().  If
//   the node has already been code generated then the Emit() call will
//   generate a jump to the previously generated code instead.  In order to
//   limit recursion it is possible for the Emit() function to put the node
//   on a work list for later generation and instead generate a jump.  The
//   destination of the jump is resolved later when the code is generated.
//
// Actual regular expression code generation.
//
//   Code generation is actually more complicated than the above.  In order
//   to improve the efficiency of the generated code some optimizations are
//   performed
//
//   * Choice nodes have 1-character lookahead.
//     A choice node looks at the following character and eliminates some of
//     the choices immediately based on that character.  This is not yet
//     implemented.
//   * Simple greedy loops store reduced backtracking information.
//     A quantifier like /.*foo/m will greedily match the whole input.  It will
//     then need to backtrack to a point where it can match "foo".  The naive
//     implementation of this would push each character position onto the
//     backtracking stack, then pop them off one by one.  This would use space
//     proportional to the length of the input string.  However since the "."
//     can only match in one way and always has a constant length (in this case
//     of 1) it suffices to store the current position on the top of the stack
//     once.  Matching now becomes merely incrementing the current position and
//     backtracking becomes decrementing the current position and checking the
//     result against the stored current position.  This is faster and saves
//     space.
//   * The current state is virtualized.
//     This is used to defer expensive operations until it is clear that they
//     are needed and to generate code for a node more than once, allowing
//     specialized an efficient versions of the code to be created. This is
//     explained in the section below.
//
// Execution state virtualization.
//
//   Instead of emitting code, nodes that manipulate the state can record their
//   manipulation in an object called the Trace.  The Trace object can record a
//   current position offset, an optional backtrack code location on the top of
//   the virtualized backtrack stack and some register changes.  When a node is
//   to be emitted it can flush the Trace or update it.  Flushing the Trace
//   will emit code to bring the actual state into line with the virtual state.
836
//   Avoiding flushing the state can postpone some work (e.g. updates of capture
837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857
//   registers).  Postponing work can save time when executing the regular
//   expression since it may be found that the work never has to be done as a
//   failure to match can occur.  In addition it is much faster to jump to a
//   known backtrack code location than it is to pop an unknown backtrack
//   location from the stack and jump there.
//
//   The virtual state found in the Trace affects code generation.  For example
//   the virtual state contains the difference between the actual current
//   position and the virtual current position, and matching code needs to use
//   this offset to attempt a match in the correct location of the input
//   string.  Therefore code generated for a non-trivial trace is specialized
//   to that trace.  The code generator therefore has the ability to generate
//   code for each node several times.  In order to limit the size of the
//   generated code there is an arbitrary limit on how many specialized sets of
//   code may be generated for a given node.  If the limit is reached, the
//   trace is flushed and a generic version of the code for a node is emitted.
//   This is subsequently used for that node.  The code emitted for non-generic
//   trace is not recorded in the node and so it cannot currently be reused in
//   the event that code generation is requested for an identical trace.


858
void RegExpTree::AppendToText(RegExpText* text, Zone* zone) {
859 860 861 862
  UNREACHABLE();
}


863 864
void RegExpAtom::AppendToText(RegExpText* text, Zone* zone) {
  text->AddElement(TextElement::Atom(this), zone);
865 866 867
}


868 869
void RegExpCharacterClass::AppendToText(RegExpText* text, Zone* zone) {
  text->AddElement(TextElement::CharClass(this), zone);
870 871 872
}


873
void RegExpText::AppendToText(RegExpText* text, Zone* zone) {
874
  for (int i = 0; i < elements()->length(); i++)
875
    text->AddElement(elements()->at(i), zone);
876 877 878 879
}


TextElement TextElement::Atom(RegExpAtom* atom) {
880
  return TextElement(ATOM, atom);
881 882 883
}


884 885
TextElement TextElement::CharClass(RegExpCharacterClass* char_class) {
  return TextElement(CHAR_CLASS, char_class);
886 887 888
}


889 890 891 892 893 894 895
int TextElement::length() const {
  switch (text_type()) {
    case ATOM:
      return atom()->length();

    case CHAR_CLASS:
      return 1;
896
  }
897 898
  UNREACHABLE();
  return 0;
899 900 901 902 903
}


DispatchTable* ChoiceNode::GetTable(bool ignore_case) {
  if (table_ == NULL) {
904 905
    table_ = new(zone()) DispatchTable(zone());
    DispatchTableConstructor cons(table_, ignore_case, zone());
906 907 908 909 910 911
    cons.BuildTable(this);
  }
  return table_;
}


912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928
class FrequencyCollator {
 public:
  FrequencyCollator() : total_samples_(0) {
    for (int i = 0; i < RegExpMacroAssembler::kTableSize; i++) {
      frequencies_[i] = CharacterFrequency(i);
    }
  }

  void CountCharacter(int character) {
    int index = (character & RegExpMacroAssembler::kTableMask);
    frequencies_[index].Increment();
    total_samples_++;
  }

  // Does not measure in percent, but rather per-128 (the table size from the
  // regexp macro assembler).
  int Frequency(int in_character) {
929
    DCHECK((in_character & RegExpMacroAssembler::kTableMask) == in_character);
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958
    if (total_samples_ < 1) return 1;  // Division by zero.
    int freq_in_per128 =
        (frequencies_[in_character].counter() * 128) / total_samples_;
    return freq_in_per128;
  }

 private:
  class CharacterFrequency {
   public:
    CharacterFrequency() : counter_(0), character_(-1) { }
    explicit CharacterFrequency(int character)
        : counter_(0), character_(character) { }

    void Increment() { counter_++; }
    int counter() { return counter_; }
    int character() { return character_; }

   private:
    int counter_;
    int character_;
  };


 private:
  CharacterFrequency frequencies_[RegExpMacroAssembler::kTableSize];
  int total_samples_;
};


959 960
class RegExpCompiler {
 public:
961
  RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count,
962
                 JSRegExp::Flags flags, bool is_one_byte);
963 964 965 966 967 968 969 970 971

  int AllocateRegister() {
    if (next_register_ >= RegExpMacroAssembler::kMaxRegister) {
      reg_exp_too_big_ = true;
      return next_register_;
    }
    return next_register_++;
  }

972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987
  // Lookarounds to match lone surrogates for unicode character class matches
  // are never nested. We can therefore reuse registers.
  int UnicodeLookaroundStackRegister() {
    if (unicode_lookaround_stack_register_ == kNoRegister) {
      unicode_lookaround_stack_register_ = AllocateRegister();
    }
    return unicode_lookaround_stack_register_;
  }

  int UnicodeLookaroundPositionRegister() {
    if (unicode_lookaround_position_register_ == kNoRegister) {
      unicode_lookaround_position_register_ = AllocateRegister();
    }
    return unicode_lookaround_position_register_;
  }

988 989 990 991 992
  RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler,
                                           RegExpNode* start,
                                           int capture_count,
                                           Handle<String> pattern);

993 994 995 996 997 998
  inline void AddWork(RegExpNode* node) {
    if (!node->on_work_list() && !node->label()->is_bound()) {
      node->set_on_work_list(true);
      work_list_->Add(node);
    }
  }
999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013

  static const int kImplementationOffset = 0;
  static const int kNumberOfRegistersOffset = 0;
  static const int kCodeOffset = 1;

  RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
  EndNode* accept() { return accept_; }

  static const int kMaxRecursion = 100;
  inline int recursion_depth() { return recursion_depth_; }
  inline void IncrementRecursionDepth() { recursion_depth_++; }
  inline void DecrementRecursionDepth() { recursion_depth_--; }

  void SetRegExpTooBig() { reg_exp_too_big_ = true; }

1014 1015
  inline bool ignore_case() { return (flags_ & JSRegExp::kIgnoreCase) != 0; }
  inline bool unicode() { return (flags_ & JSRegExp::kUnicode) != 0; }
1016 1017 1018 1019 1020 1021 1022
  inline bool one_byte() { return one_byte_; }
  inline bool optimize() { return optimize_; }
  inline void set_optimize(bool value) { optimize_ = value; }
  inline bool limiting_recursion() { return limiting_recursion_; }
  inline void set_limiting_recursion(bool value) {
    limiting_recursion_ = value;
  }
1023 1024
  bool read_backward() { return read_backward_; }
  void set_read_backward(bool value) { read_backward_ = value; }
1025
  FrequencyCollator* frequency_collator() { return &frequency_collator_; }
1026

1027 1028 1029 1030 1031
  int current_expansion_factor() { return current_expansion_factor_; }
  void set_current_expansion_factor(int value) {
    current_expansion_factor_ = value;
  }

1032
  Isolate* isolate() const { return isolate_; }
1033 1034
  Zone* zone() const { return zone_; }

1035
  static const int kNoRegister = -1;
1036

1037 1038 1039
 private:
  EndNode* accept_;
  int next_register_;
1040 1041
  int unicode_lookaround_stack_register_;
  int unicode_lookaround_position_register_;
1042 1043 1044
  List<RegExpNode*>* work_list_;
  int recursion_depth_;
  RegExpMacroAssembler* macro_assembler_;
1045
  JSRegExp::Flags flags_;
1046
  bool one_byte_;
1047
  bool reg_exp_too_big_;
1048 1049
  bool limiting_recursion_;
  bool optimize_;
1050
  bool read_backward_;
1051
  int current_expansion_factor_;
1052
  FrequencyCollator frequency_collator_;
1053
  Isolate* isolate_;
1054
  Zone* zone_;
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068
};


class RecursionCheck {
 public:
  explicit RecursionCheck(RegExpCompiler* compiler) : compiler_(compiler) {
    compiler->IncrementRecursionDepth();
  }
  ~RecursionCheck() { compiler_->DecrementRecursionDepth(); }
 private:
  RegExpCompiler* compiler_;
};


1069 1070
static RegExpEngine::CompilationResult IrregexpRegExpTooBig(Isolate* isolate) {
  return RegExpEngine::CompilationResult(isolate, "RegExp too big");
1071 1072 1073 1074 1075
}


// Attempts to compile the regexp using an Irregexp code generator.  Returns
// a fixed array or a null handle depending on whether it succeeded.
1076
RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count,
1077
                               JSRegExp::Flags flags, bool one_byte)
1078
    : next_register_(2 * (capture_count + 1)),
1079 1080
      unicode_lookaround_stack_register_(kNoRegister),
      unicode_lookaround_position_register_(kNoRegister),
1081 1082
      work_list_(NULL),
      recursion_depth_(0),
1083
      flags_(flags),
1084
      one_byte_(one_byte),
1085
      reg_exp_too_big_(false),
1086 1087
      limiting_recursion_(false),
      optimize_(FLAG_regexp_optimization),
1088
      read_backward_(false),
1089 1090
      current_expansion_factor_(1),
      frequency_collator_(),
1091
      isolate_(isolate),
1092 1093
      zone_(zone) {
  accept_ = new(zone) EndNode(EndNode::ACCEPT, zone);
1094
  DCHECK(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister);
1095 1096 1097 1098 1099 1100 1101 1102
}


RegExpEngine::CompilationResult RegExpCompiler::Assemble(
    RegExpMacroAssembler* macro_assembler,
    RegExpNode* start,
    int capture_count,
    Handle<String> pattern) {
1103 1104
  Heap* heap = pattern->GetHeap();

1105 1106
#ifdef DEBUG
  if (FLAG_trace_regexp_assembler)
1107 1108
    macro_assembler_ =
        new RegExpMacroAssemblerTracer(isolate(), macro_assembler);
1109 1110 1111
  else
#endif
    macro_assembler_ = macro_assembler;
1112

1113 1114 1115 1116 1117 1118 1119 1120 1121
  List <RegExpNode*> work_list(0);
  work_list_ = &work_list;
  Label fail;
  macro_assembler_->PushBacktrack(&fail);
  Trace new_trace;
  start->Emit(this, &new_trace);
  macro_assembler_->Bind(&fail);
  macro_assembler_->Fail();
  while (!work_list.is_empty()) {
1122 1123 1124 1125 1126 1127 1128
    RegExpNode* node = work_list.RemoveLast();
    node->set_on_work_list(false);
    if (!node->label()->is_bound()) node->Emit(this, &new_trace);
  }
  if (reg_exp_too_big_) {
    macro_assembler_->AbortedCodeGeneration();
    return IrregexpRegExpTooBig(isolate_);
1129 1130
  }

1131 1132
  Handle<HeapObject> code = macro_assembler_->GetCode(pattern);
  heap->IncreaseTotalRegexpCodeGenerated(code->Size());
1133
  work_list_ = NULL;
1134
#if defined(ENABLE_DISASSEMBLER) && !defined(V8_INTERPRETED_REGEXP)
1135
  if (FLAG_print_code) {
1136 1137 1138
    CodeTracer::Scope trace_scope(heap->isolate()->GetCodeTracer());
    OFStream os(trace_scope.file());
    Handle<Code>::cast(code)->Disassemble(pattern->ToCString().get(), os);
1139
  }
1140 1141
#endif
#ifdef DEBUG
1142 1143 1144 1145 1146 1147 1148 1149 1150
  if (FLAG_trace_regexp_assembler) {
    delete macro_assembler_;
  }
#endif
  return RegExpEngine::CompilationResult(*code, next_register_);
}


bool Trace::DeferredAction::Mentions(int that) {
1151
  if (action_type() == ActionNode::CLEAR_CAPTURES) {
1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171
    Interval range = static_cast<DeferredClearCaptures*>(this)->range();
    return range.Contains(that);
  } else {
    return reg() == that;
  }
}


bool Trace::mentions_reg(int reg) {
  for (DeferredAction* action = actions_;
       action != NULL;
       action = action->next()) {
    if (action->Mentions(reg))
      return true;
  }
  return false;
}


bool Trace::GetStoredPosition(int reg, int* cp_offset) {
1172
  DCHECK_EQ(0, *cp_offset);
1173 1174 1175 1176
  for (DeferredAction* action = actions_;
       action != NULL;
       action = action->next()) {
    if (action->Mentions(reg)) {
1177
      if (action->action_type() == ActionNode::STORE_POSITION) {
1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
        *cp_offset = static_cast<DeferredCapture*>(action)->cp_offset();
        return true;
      } else {
        return false;
      }
    }
  }
  return false;
}


1189 1190
int Trace::FindAffectedRegisters(OutSet* affected_registers,
                                 Zone* zone) {
1191 1192 1193 1194
  int max_register = RegExpCompiler::kNoRegister;
  for (DeferredAction* action = actions_;
       action != NULL;
       action = action->next()) {
1195
    if (action->action_type() == ActionNode::CLEAR_CAPTURES) {
1196 1197
      Interval range = static_cast<DeferredClearCaptures*>(action)->range();
      for (int i = range.from(); i <= range.to(); i++)
1198
        affected_registers->Set(i, zone);
1199 1200
      if (range.to() > max_register) max_register = range.to();
    } else {
1201
      affected_registers->Set(action->reg(), zone);
1202 1203 1204 1205 1206 1207 1208 1209 1210
      if (action->reg() > max_register) max_register = action->reg();
    }
  }
  return max_register;
}


void Trace::RestoreAffectedRegisters(RegExpMacroAssembler* assembler,
                                     int max_register,
1211 1212
                                     const OutSet& registers_to_pop,
                                     const OutSet& registers_to_clear) {
1213
  for (int reg = max_register; reg >= 0; reg--) {
1214 1215 1216
    if (registers_to_pop.Get(reg)) {
      assembler->PopRegister(reg);
    } else if (registers_to_clear.Get(reg)) {
1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228
      int clear_to = reg;
      while (reg > 0 && registers_to_clear.Get(reg - 1)) {
        reg--;
      }
      assembler->ClearRegisters(reg, clear_to);
    }
  }
}


void Trace::PerformDeferredActions(RegExpMacroAssembler* assembler,
                                   int max_register,
1229
                                   const OutSet& affected_registers,
1230
                                   OutSet* registers_to_pop,
1231 1232
                                   OutSet* registers_to_clear,
                                   Zone* zone) {
1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252
  // The "+1" is to avoid a push_limit of zero if stack_limit_slack() is 1.
  const int push_limit = (assembler->stack_limit_slack() + 1) / 2;

  // Count pushes performed to force a stack limit check occasionally.
  int pushes = 0;

  for (int reg = 0; reg <= max_register; reg++) {
    if (!affected_registers.Get(reg)) {
      continue;
    }

    // The chronologically first deferred action in the trace
    // is used to infer the action needed to restore a register
    // to its previous state (or not, if it's safe to ignore it).
    enum DeferredActionUndoType { IGNORE, RESTORE, CLEAR };
    DeferredActionUndoType undo_action = IGNORE;

    int value = 0;
    bool absolute = false;
    bool clear = false;
1253 1254
    static const int kNoStore = kMinInt;
    int store_position = kNoStore;
1255 1256 1257 1258 1259 1260
    // This is a little tricky because we are scanning the actions in reverse
    // historical order (newest first).
    for (DeferredAction* action = actions_;
         action != NULL;
         action = action->next()) {
      if (action->Mentions(reg)) {
1261
        switch (action->action_type()) {
1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274
          case ActionNode::SET_REGISTER: {
            Trace::DeferredSetRegister* psr =
                static_cast<Trace::DeferredSetRegister*>(action);
            if (!absolute) {
              value += psr->value();
              absolute = true;
            }
            // SET_REGISTER is currently only used for newly introduced loop
            // counters. They can have a significant previous value if they
            // occour in a loop. TODO(lrn): Propagate this information, so
            // we can set undo_action to IGNORE if we know there is no value to
            // restore.
            undo_action = RESTORE;
1275
            DCHECK_EQ(store_position, kNoStore);
1276
            DCHECK(!clear);
1277 1278 1279 1280 1281 1282
            break;
          }
          case ActionNode::INCREMENT_REGISTER:
            if (!absolute) {
              value++;
            }
1283
            DCHECK_EQ(store_position, kNoStore);
1284
            DCHECK(!clear);
1285 1286 1287 1288 1289
            undo_action = RESTORE;
            break;
          case ActionNode::STORE_POSITION: {
            Trace::DeferredCapture* pc =
                static_cast<Trace::DeferredCapture*>(action);
1290
            if (!clear && store_position == kNoStore) {
1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305
              store_position = pc->cp_offset();
            }

            // For captures we know that stores and clears alternate.
            // Other register, are never cleared, and if the occur
            // inside a loop, they might be assigned more than once.
            if (reg <= 1) {
              // Registers zero and one, aka "capture zero", is
              // always set correctly if we succeed. There is no
              // need to undo a setting on backtrack, because we
              // will set it again or fail.
              undo_action = IGNORE;
            } else {
              undo_action = pc->is_capture() ? CLEAR : RESTORE;
            }
1306 1307
            DCHECK(!absolute);
            DCHECK_EQ(value, 0);
1308 1309 1310 1311 1312 1313
            break;
          }
          case ActionNode::CLEAR_CAPTURES: {
            // Since we're scanning in reverse order, if we've already
            // set the position we have to ignore historically earlier
            // clearing operations.
1314
            if (store_position == kNoStore) {
1315 1316 1317
              clear = true;
            }
            undo_action = RESTORE;
1318 1319
            DCHECK(!absolute);
            DCHECK_EQ(value, 0);
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338
            break;
          }
          default:
            UNREACHABLE();
            break;
        }
      }
    }
    // Prepare for the undo-action (e.g., push if it's going to be popped).
    if (undo_action == RESTORE) {
      pushes++;
      RegExpMacroAssembler::StackCheckFlag stack_check =
          RegExpMacroAssembler::kNoStackLimitCheck;
      if (pushes == push_limit) {
        stack_check = RegExpMacroAssembler::kCheckStackLimit;
        pushes = 0;
      }

      assembler->PushRegister(reg, stack_check);
1339
      registers_to_pop->Set(reg, zone);
1340
    } else if (undo_action == CLEAR) {
1341
      registers_to_clear->Set(reg, zone);
1342 1343 1344
    }
    // Perform the chronologically last action (or accumulated increment)
    // for the register.
1345
    if (store_position != kNoStore) {
1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363
      assembler->WriteCurrentPositionToRegister(reg, store_position);
    } else if (clear) {
      assembler->ClearRegisters(reg, reg);
    } else if (absolute) {
      assembler->SetRegister(reg, value);
    } else if (value != 0) {
      assembler->AdvanceRegister(reg, value);
    }
  }
}


// This is called as we come into a loop choice node and some other tricky
// nodes.  It normalizes the state of the code generator to ensure we can
// generate generic code.
void Trace::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
  RegExpMacroAssembler* assembler = compiler->macro_assembler();

1364
  DCHECK(!is_trivial());
1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386

  if (actions_ == NULL && backtrack() == NULL) {
    // Here we just have some deferred cp advances to fix and we are back to
    // a normal situation.  We may also have to forget some information gained
    // through a quick check that was already performed.
    if (cp_offset_ != 0) assembler->AdvanceCurrentPosition(cp_offset_);
    // Create a new trivial state and generate the node with that.
    Trace new_state;
    successor->Emit(compiler, &new_state);
    return;
  }

  // Generate deferred actions here along with code to undo them again.
  OutSet affected_registers;

  if (backtrack() != NULL) {
    // Here we have a concrete backtrack location.  These are set up by choice
    // nodes and so they indicate that we have a deferred save of the current
    // position which we may need to emit here.
    assembler->PushCurrentPosition();
  }

1387 1388
  int max_register = FindAffectedRegisters(&affected_registers,
                                           compiler->zone());
1389 1390 1391 1392 1393 1394
  OutSet registers_to_pop;
  OutSet registers_to_clear;
  PerformDeferredActions(assembler,
                         max_register,
                         affected_registers,
                         &registers_to_pop,
1395 1396
                         &registers_to_clear,
                         compiler->zone());
1397 1398 1399 1400 1401 1402 1403
  if (cp_offset_ != 0) {
    assembler->AdvanceCurrentPosition(cp_offset_);
  }

  // Create a new trivial state and generate the node with that.
  Label undo;
  assembler->PushBacktrack(&undo);
1404 1405 1406 1407 1408 1409 1410
  if (successor->KeepRecursing(compiler)) {
    Trace new_state;
    successor->Emit(compiler, &new_state);
  } else {
    compiler->AddWork(successor);
    assembler->GoTo(successor->label());
  }
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477

  // On backtrack we need to restore state.
  assembler->Bind(&undo);
  RestoreAffectedRegisters(assembler,
                           max_register,
                           registers_to_pop,
                           registers_to_clear);
  if (backtrack() == NULL) {
    assembler->Backtrack();
  } else {
    assembler->PopCurrentPosition();
    assembler->GoTo(backtrack());
  }
}


void NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
  RegExpMacroAssembler* assembler = compiler->macro_assembler();

  // Omit flushing the trace. We discard the entire stack frame anyway.

  if (!label()->is_bound()) {
    // We are completely independent of the trace, since we ignore it,
    // so this code can be used as the generic version.
    assembler->Bind(label());
  }

  // Throw away everything on the backtrack stack since the start
  // of the negative submatch and restore the character position.
  assembler->ReadCurrentPositionFromRegister(current_position_register_);
  assembler->ReadStackPointerFromRegister(stack_pointer_register_);
  if (clear_capture_count_ > 0) {
    // Clear any captures that might have been performed during the success
    // of the body of the negative look-ahead.
    int clear_capture_end = clear_capture_start_ + clear_capture_count_ - 1;
    assembler->ClearRegisters(clear_capture_start_, clear_capture_end);
  }
  // Now that we have unwound the stack we find at the top of the stack the
  // backtrack that the BeginSubmatch node got.
  assembler->Backtrack();
}


void EndNode::Emit(RegExpCompiler* compiler, Trace* trace) {
  if (!trace->is_trivial()) {
    trace->Flush(compiler, this);
    return;
  }
  RegExpMacroAssembler* assembler = compiler->macro_assembler();
  if (!label()->is_bound()) {
    assembler->Bind(label());
  }
  switch (action_) {
    case ACCEPT:
      assembler->Succeed();
      return;
    case BACKTRACK:
      assembler->GoTo(trace->backtrack());
      return;
    case NEGATIVE_SUBMATCH_SUCCESS:
      // This case is handled in a different virtual method.
      UNREACHABLE();
  }
  UNIMPLEMENTED();
}


1478
void GuardedAlternative::AddGuard(Guard* guard, Zone* zone) {
1479
  if (guards_ == NULL)
1480 1481
    guards_ = new(zone) ZoneList<Guard*>(1, zone);
  guards_->Add(guard, zone);
1482 1483 1484 1485 1486 1487
}


ActionNode* ActionNode::SetRegister(int reg,
                                    int val,
                                    RegExpNode* on_success) {
1488 1489
  ActionNode* result =
      new(on_success->zone()) ActionNode(SET_REGISTER, on_success);
1490 1491 1492 1493 1494 1495 1496
  result->data_.u_store_register.reg = reg;
  result->data_.u_store_register.value = val;
  return result;
}


ActionNode* ActionNode::IncrementRegister(int reg, RegExpNode* on_success) {
1497 1498
  ActionNode* result =
      new(on_success->zone()) ActionNode(INCREMENT_REGISTER, on_success);
1499 1500 1501 1502 1503 1504 1505 1506
  result->data_.u_increment_register.reg = reg;
  return result;
}


ActionNode* ActionNode::StorePosition(int reg,
                                      bool is_capture,
                                      RegExpNode* on_success) {
1507 1508
  ActionNode* result =
      new(on_success->zone()) ActionNode(STORE_POSITION, on_success);
1509 1510 1511 1512 1513 1514 1515 1516
  result->data_.u_position_register.reg = reg;
  result->data_.u_position_register.is_capture = is_capture;
  return result;
}


ActionNode* ActionNode::ClearCaptures(Interval range,
                                      RegExpNode* on_success) {
1517 1518
  ActionNode* result =
      new(on_success->zone()) ActionNode(CLEAR_CAPTURES, on_success);
1519 1520 1521 1522 1523 1524 1525 1526 1527
  result->data_.u_clear_captures.range_from = range.from();
  result->data_.u_clear_captures.range_to = range.to();
  return result;
}


ActionNode* ActionNode::BeginSubmatch(int stack_reg,
                                      int position_reg,
                                      RegExpNode* on_success) {
1528 1529
  ActionNode* result =
      new(on_success->zone()) ActionNode(BEGIN_SUBMATCH, on_success);
1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540
  result->data_.u_submatch.stack_pointer_register = stack_reg;
  result->data_.u_submatch.current_position_register = position_reg;
  return result;
}


ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
                                                int position_reg,
                                                int clear_register_count,
                                                int clear_register_from,
                                                RegExpNode* on_success) {
1541 1542
  ActionNode* result =
      new(on_success->zone()) ActionNode(POSITIVE_SUBMATCH_SUCCESS, on_success);
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554
  result->data_.u_submatch.stack_pointer_register = stack_reg;
  result->data_.u_submatch.current_position_register = position_reg;
  result->data_.u_submatch.clear_register_count = clear_register_count;
  result->data_.u_submatch.clear_register_from = clear_register_from;
  return result;
}


ActionNode* ActionNode::EmptyMatchCheck(int start_register,
                                        int repetition_register,
                                        int repetition_limit,
                                        RegExpNode* on_success) {
1555 1556
  ActionNode* result =
      new(on_success->zone()) ActionNode(EMPTY_MATCH_CHECK, on_success);
1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585
  result->data_.u_empty_match_check.start_register = start_register;
  result->data_.u_empty_match_check.repetition_register = repetition_register;
  result->data_.u_empty_match_check.repetition_limit = repetition_limit;
  return result;
}


#define DEFINE_ACCEPT(Type)                                          \
  void Type##Node::Accept(NodeVisitor* visitor) {                    \
    visitor->Visit##Type(this);                                      \
  }
FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
#undef DEFINE_ACCEPT


void LoopChoiceNode::Accept(NodeVisitor* visitor) {
  visitor->VisitLoopChoice(this);
}


// -------------------------------------------------------------------
// Emit code.


void ChoiceNode::GenerateGuard(RegExpMacroAssembler* macro_assembler,
                               Guard* guard,
                               Trace* trace) {
  switch (guard->op()) {
    case Guard::LT:
1586
      DCHECK(!trace->mentions_reg(guard->reg()));
1587 1588 1589 1590 1591
      macro_assembler->IfRegisterGE(guard->reg(),
                                    guard->value(),
                                    trace->backtrack());
      break;
    case Guard::GEQ:
1592
      DCHECK(!trace->mentions_reg(guard->reg()));
1593 1594 1595 1596 1597 1598 1599 1600 1601
      macro_assembler->IfRegisterLT(guard->reg(),
                                    guard->value(),
                                    trace->backtrack());
      break;
  }
}


// Returns the number of characters in the equivalence class, omitting those
1602 1603 1604
// that cannot occur in the source string because it is Latin1.
static int GetCaseIndependentLetters(Isolate* isolate, uc16 character,
                                     bool one_byte_subject,
1605
                                     unibrow::uchar* letters) {
1606 1607
  int length =
      isolate->jsregexp_uncanonicalize()->get(character, '\0', letters);
1608 1609 1610 1611 1612 1613
  // Unibrow returns 0 or 1 for characters where case independence is
  // trivial.
  if (length == 0) {
    letters[0] = character;
    length = 1;
  }
1614 1615 1616 1617 1618 1619 1620 1621 1622

  if (one_byte_subject) {
    int new_length = 0;
    for (int i = 0; i < length; i++) {
      if (letters[i] <= String::kMaxOneByteCharCode) {
        letters[new_length++] = letters[i];
      }
    }
    length = new_length;
1623
  }
1624 1625

  return length;
1626 1627 1628
}


1629 1630
static inline bool EmitSimpleCharacter(Isolate* isolate,
                                       RegExpCompiler* compiler,
1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651
                                       uc16 c,
                                       Label* on_failure,
                                       int cp_offset,
                                       bool check,
                                       bool preloaded) {
  RegExpMacroAssembler* assembler = compiler->macro_assembler();
  bool bound_checked = false;
  if (!preloaded) {
    assembler->LoadCurrentCharacter(
        cp_offset,
        on_failure,
        check);
    bound_checked = true;
  }
  assembler->CheckNotCharacter(c, on_failure);
  return bound_checked;
}


// Only emits non-letters (things that don't have case).  Only used for case
// independent matches.
1652 1653
static inline bool EmitAtomNonLetter(Isolate* isolate,
                                     RegExpCompiler* compiler,
1654 1655 1656 1657 1658 1659
                                     uc16 c,
                                     Label* on_failure,
                                     int cp_offset,
                                     bool check,
                                     bool preloaded) {
  RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
1660
  bool one_byte = compiler->one_byte();
1661
  unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1662
  int length = GetCaseIndependentLetters(isolate, c, one_byte, chars);
1663
  if (length < 1) {
1664 1665 1666
    // This can't match.  Must be an one-byte subject and a non-one-byte
    // character.  We do not need to do anything since the one-byte pass
    // already handled this.
1667 1668 1669 1670 1671
    return false;  // Bounds not checked.
  }
  bool checked = false;
  // We handle the length > 1 case in a later pass.
  if (length == 1) {
1672