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

#include "src/regexp/regexp-parser.h"

7 8
#include <vector>

9
#include "src/char-predicates-inl.h"
10
#include "src/heap/factory.h"
11 12
#include "src/isolate.h"
#include "src/objects-inl.h"
13
#include "src/ostreams.h"
14
#include "src/regexp/jsregexp.h"
15
#include "src/regexp/property-sequences.h"
16 17
#include "src/utils.h"

18
#ifdef V8_INTL_SUPPORT
19
#include "unicode/uniset.h"
20 21 22
// TODO(mathias): Remove this when we no longer need to check
// `U_ICU_VERSION_MAJOR_NUM`.
#include "unicode/uvernum.h"
23
#endif  // V8_INTL_SUPPORT
24

25 26 27 28
namespace v8 {
namespace internal {

RegExpParser::RegExpParser(FlatStringReader* in, Handle<String>* error,
29
                           JSRegExp::Flags flags, Isolate* isolate, Zone* zone)
30 31 32
    : isolate_(isolate),
      zone_(zone),
      error_(error),
33 34 35
      captures_(nullptr),
      named_captures_(nullptr),
      named_back_references_(nullptr),
36 37
      in_(in),
      current_(kEndMarker),
38
      top_level_flags_(flags),
39 40 41 42 43 44 45
      next_pos_(0),
      captures_started_(0),
      capture_count_(0),
      has_more_(true),
      simple_(false),
      contains_anchor_(false),
      is_scanned_for_captures_(false),
46
      has_named_captures_(false),
47 48 49 50
      failed_(false) {
  Advance();
}

51 52
template <bool update_position>
inline uc32 RegExpParser::ReadNext() {
53 54 55
  int position = next_pos_;
  uc32 c0 = in()->Get(position);
  position++;
56 57
  // Read the whole surrogate pair in case of unicode flag, if possible.
  if (unicode() && position < in()->length() &&
58 59 60 61 62 63 64 65 66 67 68 69
      unibrow::Utf16::IsLeadSurrogate(static_cast<uc16>(c0))) {
    uc16 c1 = in()->Get(position);
    if (unibrow::Utf16::IsTrailSurrogate(c1)) {
      c0 = unibrow::Utf16::CombineSurrogatePair(static_cast<uc16>(c0), c1);
      position++;
    }
  }
  if (update_position) next_pos_ = position;
  return c0;
}


70 71
uc32 RegExpParser::Next() {
  if (has_next()) {
72
    return ReadNext<false>();
73 74 75 76 77
  } else {
    return kEndMarker;
  }
}

78
void RegExpParser::Advance() {
79
  if (has_next()) {
80 81
    StackLimitCheck check(isolate());
    if (check.HasOverflowed()) {
82 83 84
      if (FLAG_abort_on_stack_or_string_length_overflow) {
        FATAL("Aborting on stack overflow");
      }
85
      ReportError(CStrVector(
86
          MessageFormatter::TemplateString(MessageTemplate::kStackOverflow)));
87 88 89
    } else if (zone()->excess_allocation()) {
      ReportError(CStrVector("Regular expression too large"));
    } else {
90
      current_ = ReadNext<true>();
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
    }
  } else {
    current_ = kEndMarker;
    // Advance so that position() points to 1-after-the-last-character. This is
    // important so that Reset() to this position works correctly.
    next_pos_ = in()->length() + 1;
    has_more_ = false;
  }
}


void RegExpParser::Reset(int pos) {
  next_pos_ = pos;
  has_more_ = (pos < in()->length());
  Advance();
}

108
void RegExpParser::Advance(int dist) {
109
  next_pos_ += dist - 1;
110
  Advance();
111 112 113 114 115
}


bool RegExpParser::simple() { return simple_; }

116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
bool RegExpParser::IsSyntaxCharacterOrSlash(uc32 c) {
  switch (c) {
    case '^':
    case '$':
    case '\\':
    case '.':
    case '*':
    case '+':
    case '?':
    case '(':
    case ')':
    case '[':
    case ']':
    case '{':
    case '}':
    case '|':
    case '/':
      return true;
    default:
      break;
  }
  return false;
138 139 140 141
}


RegExpTree* RegExpParser::ReportError(Vector<const char> message) {
142
  if (failed_) return nullptr;  // Do not overwrite any existing error.
143
  failed_ = true;
144 145 146 147
  *error_ = isolate()
                ->factory()
                ->NewStringFromOneByte(Vector<const uint8_t>::cast(message))
                .ToHandleChecked();
148 149 150
  // Zip to the end to make sure the no more input is read.
  current_ = kEndMarker;
  next_pos_ = in()->length();
151
  return nullptr;
152 153
}

154 155
#define CHECK_FAILED /**/);    \
  if (failed_) return nullptr; \
156 157 158 159 160 161
  ((void)0

// Pattern ::
//   Disjunction
RegExpTree* RegExpParser::ParsePattern() {
  RegExpTree* result = ParseDisjunction(CHECK_FAILED);
162
  PatchNamedBackReferences(CHECK_FAILED);
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
  DCHECK(!has_more());
  // If the result of parsing is a literal string atom, and it has the
  // same length as the input, then the atom is identical to the input.
  if (result->IsAtom() && result->AsAtom()->length() == in()->length()) {
    simple_ = true;
  }
  return result;
}


// Disjunction ::
//   Alternative
//   Alternative | Disjunction
// Alternative ::
//   [empty]
//   Term Alternative
// Term ::
//   Assertion
//   Atom
//   Atom Quantifier
RegExpTree* RegExpParser::ParseDisjunction() {
  // Used to store current state while parsing subexpressions.
185
  RegExpParserState initial_state(nullptr, INITIAL, RegExpLookaround::LOOKAHEAD,
186
                                  0, nullptr, top_level_flags_, zone());
187 188 189 190 191 192 193 194
  RegExpParserState* state = &initial_state;
  // Cache the builder in a local variable for quick access.
  RegExpBuilder* builder = initial_state.builder();
  while (true) {
    switch (current()) {
      case kEndMarker:
        if (state->IsSubexpression()) {
          // Inside a parenthesized group when hitting end of input.
195
          return ReportError(CStrVector("Unterminated group"));
196 197 198 199 200 201
        }
        DCHECK_EQ(INITIAL, state->group_type());
        // Parsing completed successfully.
        return builder->ToRegExp();
      case ')': {
        if (!state->IsSubexpression()) {
202
          return ReportError(CStrVector("Unmatched ')'"));
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
        }
        DCHECK_NE(INITIAL, state->group_type());

        Advance();
        // End disjunction parsing and convert builder content to new single
        // regexp atom.
        RegExpTree* body = builder->ToRegExp();

        int end_capture_index = captures_started();

        int capture_index = state->capture_index();
        SubexpressionType group_type = state->group_type();

        // Build result of subexpression.
        if (group_type == CAPTURE) {
218 219 220 221
          if (state->IsNamedCapture()) {
            CreateNamedCaptureAtIndex(state->capture_name(),
                                      capture_index CHECK_FAILED);
          }
222 223 224
          RegExpCapture* capture = GetCapture(capture_index);
          capture->set_body(body);
          body = capture;
225 226 227
        } else if (group_type == GROUPING) {
          body = new (zone()) RegExpGroup(body);
        } else {
228 229 230 231 232 233 234 235 236 237 238 239 240
          DCHECK(group_type == POSITIVE_LOOKAROUND ||
                 group_type == NEGATIVE_LOOKAROUND);
          bool is_positive = (group_type == POSITIVE_LOOKAROUND);
          body = new (zone()) RegExpLookaround(
              body, is_positive, end_capture_index - capture_index,
              capture_index, state->lookaround_type());
        }

        // Restore previous state.
        state = state->previous_state();
        builder = state->builder();

        builder->AddAtom(body);
241
        // For compatibility with JSC and ES3, we allow quantifiers after
242 243 244 245 246 247 248 249 250 251 252 253 254 255
        // lookaheads, and break in all cases.
        break;
      }
      case '|': {
        Advance();
        builder->NewAlternative();
        continue;
      }
      case '*':
      case '+':
      case '?':
        return ReportError(CStrVector("Nothing to repeat"));
      case '^': {
        Advance();
256 257 258
        if (builder->multiline()) {
          builder->AddAssertion(new (zone()) RegExpAssertion(
              RegExpAssertion::START_OF_LINE, builder->flags()));
259
        } else {
260 261
          builder->AddAssertion(new (zone()) RegExpAssertion(
              RegExpAssertion::START_OF_INPUT, builder->flags()));
262 263 264 265 266 267 268
          set_contains_anchor();
        }
        continue;
      }
      case '$': {
        Advance();
        RegExpAssertion::AssertionType assertion_type =
269 270 271 272
            builder->multiline() ? RegExpAssertion::END_OF_LINE
                                 : RegExpAssertion::END_OF_INPUT;
        builder->AddAssertion(
            new (zone()) RegExpAssertion(assertion_type, builder->flags()));
273 274 275 276 277 278
        continue;
      }
      case '.': {
        Advance();
        ZoneList<CharacterRange>* ranges =
            new (zone()) ZoneList<CharacterRange>(2, zone());
279

280
        if (builder->dotall()) {
281 282 283
          // Everything.
          CharacterRange::AddClassEscape('*', ranges, false, zone());
        } else {
284
          // Everything except \x0A, \x0D, \u2028 and \u2029
285 286 287
          CharacterRange::AddClassEscape('.', ranges, false, zone());
        }

288
        RegExpCharacterClass* cc =
289
            new (zone()) RegExpCharacterClass(zone(), ranges, builder->flags());
290
        builder->AddCharacterClass(cc);
291 292 293
        break;
      }
      case '(': {
294
        state = ParseOpenParenthesis(state CHECK_FAILED);
295 296 297 298
        builder = state->builder();
        continue;
      }
      case '[': {
299
        RegExpTree* cc = ParseCharacterClass(builder CHECK_FAILED);
300
        builder->AddCharacterClass(cc->AsCharacterClass());
301 302 303 304 305 306 307 308 309 310
        break;
      }
      // Atom ::
      //   \ AtomEscape
      case '\\':
        switch (Next()) {
          case kEndMarker:
            return ReportError(CStrVector("\\ at end of pattern"));
          case 'b':
            Advance(2);
311 312
            builder->AddAssertion(new (zone()) RegExpAssertion(
                RegExpAssertion::BOUNDARY, builder->flags()));
313 314 315
            continue;
          case 'B':
            Advance(2);
316 317
            builder->AddAssertion(new (zone()) RegExpAssertion(
                RegExpAssertion::NON_BOUNDARY, builder->flags()));
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
            continue;
          // AtomEscape ::
          //   CharacterClassEscape
          //
          // CharacterClassEscape :: one of
          //   d D s S w W
          case 'd':
          case 'D':
          case 's':
          case 'S':
          case 'w':
          case 'W': {
            uc32 c = Next();
            Advance(2);
            ZoneList<CharacterRange>* ranges =
                new (zone()) ZoneList<CharacterRange>(2, zone());
334 335
            CharacterRange::AddClassEscape(
                c, ranges, unicode() && builder->ignore_case(), zone());
336 337
            RegExpCharacterClass* cc = new (zone())
                RegExpCharacterClass(zone(), ranges, builder->flags());
338
            builder->AddCharacterClass(cc);
339 340
            break;
          }
341 342 343 344 345
          case 'p':
          case 'P': {
            uc32 p = Next();
            Advance(2);
            if (unicode()) {
346 347
              ZoneList<CharacterRange>* ranges =
                  new (zone()) ZoneList<CharacterRange>(2, zone());
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362
              std::vector<char> name_1, name_2;
              if (ParsePropertyClassName(&name_1, &name_2)) {
                if (AddPropertyClassRange(ranges, p == 'P', name_1, name_2)) {
                  RegExpCharacterClass* cc = new (zone())
                      RegExpCharacterClass(zone(), ranges, builder->flags());
                  builder->AddCharacterClass(cc);
                  break;
                }
                if (p == 'p' && name_2.empty()) {
                  RegExpTree* sequence = GetPropertySequence(name_1);
                  if (sequence != nullptr) {
                    builder->AddAtom(sequence);
                    break;
                  }
                }
363
              }
364
              return ReportError(CStrVector("Invalid property name"));
365 366 367 368 369
            } else {
              builder->AddCharacter(p);
            }
            break;
          }
370 371 372 373 374 375 376 377 378 379
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
          case '6':
          case '7':
          case '8':
          case '9': {
            int index = 0;
380 381
            bool is_backref = ParseBackReferenceIndex(&index CHECK_FAILED);
            if (is_backref) {
382 383 384 385 386 387 388 389 390
              if (state->IsInsideCaptureGroup(index)) {
                // The back reference is inside the capture group it refers to.
                // Nothing can possibly have been captured yet, so we use empty
                // instead. This ensures that, when checking a back reference,
                // the capture registers of the referenced capture are either
                // both set or both cleared.
                builder->AddEmpty();
              } else {
                RegExpCapture* capture = GetCapture(index);
391 392
                RegExpTree* atom =
                    new (zone()) RegExpBackReference(capture, builder->flags());
393 394 395 396
                builder->AddAtom(atom);
              }
              break;
            }
397 398 399 400 401
            // With /u, no identity escapes except for syntax characters
            // are allowed. Otherwise, all identity escapes are allowed.
            if (unicode()) {
              return ReportError(CStrVector("Invalid escape"));
            }
402 403
            uc32 first_digit = Next();
            if (first_digit == '8' || first_digit == '9') {
404 405
              builder->AddCharacter(first_digit);
              Advance(2);
406 407
              break;
            }
408
            V8_FALLTHROUGH;
409 410 411
          }
          case '0': {
            Advance();
412 413 414 415
            if (unicode() && Next() >= '0' && Next() <= '9') {
              // With /u, decimal escape with leading 0 are not parsed as octal.
              return ReportError(CStrVector("Invalid decimal escape"));
            }
416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
            uc32 octal = ParseOctalLiteral();
            builder->AddCharacter(octal);
            break;
          }
          // ControlEscape :: one of
          //   f n r t v
          case 'f':
            Advance(2);
            builder->AddCharacter('\f');
            break;
          case 'n':
            Advance(2);
            builder->AddCharacter('\n');
            break;
          case 'r':
            Advance(2);
            builder->AddCharacter('\r');
            break;
          case 't':
            Advance(2);
            builder->AddCharacter('\t');
            break;
          case 'v':
            Advance(2);
            builder->AddCharacter('\v');
            break;
          case 'c': {
            Advance();
            uc32 controlLetter = Next();
            // Special case if it is an ASCII letter.
            // Convert lower case letters to uppercase.
            uc32 letter = controlLetter & ~('a' ^ 'A');
            if (letter < 'A' || 'Z' < letter) {
              // controlLetter is not in range 'A'-'Z' or 'a'-'z'.
450 451 452
              // Read the backslash as a literal character instead of as
              // starting an escape.
              // ES#prod-annexB-ExtendedPatternCharacter
453 454 455 456
              if (unicode()) {
                // With /u, invalid escapes are not treated as identity escapes.
                return ReportError(CStrVector("Invalid unicode escape"));
              }
457 458 459
              builder->AddCharacter('\\');
            } else {
              Advance(2);
460
              builder->AddCharacter(controlLetter & 0x1F);
461 462 463 464 465 466 467 468
            }
            break;
          }
          case 'x': {
            Advance(2);
            uc32 value;
            if (ParseHexEscape(2, &value)) {
              builder->AddCharacter(value);
469
            } else if (!unicode()) {
470 471
              builder->AddCharacter('x');
            } else {
472
              // With /u, invalid escapes are not treated as identity escapes.
473 474 475 476 477 478 479 480
              return ReportError(CStrVector("Invalid escape"));
            }
            break;
          }
          case 'u': {
            Advance(2);
            uc32 value;
            if (ParseUnicodeEscape(&value)) {
481
              builder->AddEscapedUnicodeCharacter(value);
482
            } else if (!unicode()) {
483 484
              builder->AddCharacter('u');
            } else {
485
              // With /u, invalid escapes are not treated as identity escapes.
486
              return ReportError(CStrVector("Invalid Unicode escape"));
487 488 489
            }
            break;
          }
490
          case 'k':
491 492
            // Either an identity escape or a named back-reference.  The two
            // interpretations are mutually exclusive: '\k' is interpreted as
493
            // an identity escape for non-Unicode patterns without named
494 495
            // capture groups, and as the beginning of a named back-reference
            // in all other cases.
496
            if (unicode() || HasNamedCaptures()) {
497 498 499 500
              Advance(2);
              ParseNamedBackReference(builder, state CHECK_FAILED);
              break;
            }
501
            V8_FALLTHROUGH;
502 503
          default:
            Advance();
504 505 506
            // With /u, no identity escapes except for syntax characters
            // are allowed. Otherwise, all identity escapes are allowed.
            if (!unicode() || IsSyntaxCharacterOrSlash(current())) {
507 508 509 510 511 512 513 514 515 516
              builder->AddCharacter(current());
              Advance();
            } else {
              return ReportError(CStrVector("Invalid escape"));
            }
            break;
        }
        break;
      case '{': {
        int dummy;
517 518
        bool parsed = ParseIntervalQuantifier(&dummy, &dummy CHECK_FAILED);
        if (parsed) return ReportError(CStrVector("Nothing to repeat"));
519
        V8_FALLTHROUGH;
520
      }
521 522 523 524 525
      case '}':
      case ']':
        if (unicode()) {
          return ReportError(CStrVector("Lone quantifier brackets"));
        }
526
        V8_FALLTHROUGH;
527
      default:
528
        builder->AddUnicodeCharacter(current());
529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
        Advance();
        break;
    }  // end switch(current())

    int min;
    int max;
    switch (current()) {
      // QuantifierPrefix ::
      //   *
      //   +
      //   ?
      //   {
      case '*':
        min = 0;
        max = RegExpTree::kInfinity;
        Advance();
        break;
      case '+':
        min = 1;
        max = RegExpTree::kInfinity;
        Advance();
        break;
      case '?':
        min = 0;
        max = 1;
        Advance();
        break;
      case '{':
        if (ParseIntervalQuantifier(&min, &max)) {
          if (max < min) {
559 560
            return ReportError(
                CStrVector("numbers out of order in {} quantifier"));
561 562
          }
          break;
563 564 565
        } else if (unicode()) {
          // With /u, incomplete quantifiers are not allowed.
          return ReportError(CStrVector("Incomplete quantifier"));
566
        }
567
        continue;
568 569 570 571 572 573 574 575 576 577 578 579
      default:
        continue;
    }
    RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY;
    if (current() == '?') {
      quantifier_type = RegExpQuantifier::NON_GREEDY;
      Advance();
    } else if (FLAG_regexp_possessive_quantifier && current() == '+') {
      // FLAG_regexp_possessive_quantifier is a debug-only flag.
      quantifier_type = RegExpQuantifier::POSSESSIVE;
      Advance();
    }
580 581 582
    if (!builder->AddQuantifierToAtom(min, max, quantifier_type)) {
      return ReportError(CStrVector("Invalid quantifier"));
    }
583 584 585
  }
}

586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614
RegExpParser::RegExpParserState* RegExpParser::ParseOpenParenthesis(
    RegExpParserState* state) {
  RegExpLookaround::Type lookaround_type = state->lookaround_type();
  bool is_named_capture = false;
  JSRegExp::Flags switch_on = JSRegExp::kNone;
  JSRegExp::Flags switch_off = JSRegExp::kNone;
  const ZoneVector<uc16>* capture_name = nullptr;
  SubexpressionType subexpr_type = CAPTURE;
  Advance();
  if (current() == '?') {
    switch (Next()) {
      case ':':
        Advance(2);
        subexpr_type = GROUPING;
        break;
      case '=':
        Advance(2);
        lookaround_type = RegExpLookaround::LOOKAHEAD;
        subexpr_type = POSITIVE_LOOKAROUND;
        break;
      case '!':
        Advance(2);
        lookaround_type = RegExpLookaround::LOOKAHEAD;
        subexpr_type = NEGATIVE_LOOKAROUND;
        break;
      case '-':
      case 'i':
      case 's':
      case 'm': {
615
        if (!FLAG_regexp_mode_modifiers) {
616 617 618 619 620 621 622 623 624 625 626 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 667 668 669 670 671 672 673 674
          ReportError(CStrVector("Invalid group"));
          return nullptr;
        }
        Advance();
        bool flags_sense = true;  // Switching on flags.
        while (subexpr_type != GROUPING) {
          switch (current()) {
            case '-':
              if (!flags_sense) {
                ReportError(CStrVector("Multiple dashes in flag group"));
                return nullptr;
              }
              flags_sense = false;
              Advance();
              continue;
            case 's':
            case 'i':
            case 'm': {
              JSRegExp::Flags bit = JSRegExp::kUnicode;
              if (current() == 'i') bit = JSRegExp::kIgnoreCase;
              if (current() == 'm') bit = JSRegExp::kMultiline;
              if (current() == 's') bit = JSRegExp::kDotAll;
              if (((switch_on | switch_off) & bit) != 0) {
                ReportError(CStrVector("Repeated flag in flag group"));
                return nullptr;
              }
              if (flags_sense) {
                switch_on |= bit;
              } else {
                switch_off |= bit;
              }
              Advance();
              continue;
            }
            case ')': {
              Advance();
              state->builder()
                  ->FlushText();  // Flush pending text using old flags.
              // These (?i)-style flag switches don't put us in a subexpression
              // at all, they just modify the flags in the rest of the current
              // subexpression.
              JSRegExp::Flags flags =
                  (state->builder()->flags() | switch_on) & ~switch_off;
              state->builder()->set_flags(flags);
              return state;
            }
            case ':':
              Advance();
              subexpr_type = GROUPING;  // Will break us out of the outer loop.
              continue;
            default:
              ReportError(CStrVector("Invalid flag group"));
              return nullptr;
          }
        }
        break;
      }
      case '<':
        Advance();
675 676 677 678 679 680 681 682 683 684
        if (Next() == '=') {
          Advance(2);
          lookaround_type = RegExpLookaround::LOOKBEHIND;
          subexpr_type = POSITIVE_LOOKAROUND;
          break;
        } else if (Next() == '!') {
          Advance(2);
          lookaround_type = RegExpLookaround::LOOKBEHIND;
          subexpr_type = NEGATIVE_LOOKAROUND;
          break;
685
        }
686 687 688 689
        is_named_capture = true;
        has_named_captures_ = true;
        Advance();
        break;
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
      default:
        ReportError(CStrVector("Invalid group"));
        return nullptr;
    }
  }
  if (subexpr_type == CAPTURE) {
    if (captures_started_ >= kMaxCaptures) {
      ReportError(CStrVector("Too many captures"));
      return nullptr;
    }
    captures_started_++;

    if (is_named_capture) {
      capture_name = ParseCaptureGroupName(CHECK_FAILED);
    }
  }
  JSRegExp::Flags flags = (state->builder()->flags() | switch_on) & ~switch_off;
  // Store current state and begin new disjunction parsing.
  return new (zone())
      RegExpParserState(state, subexpr_type, lookaround_type, captures_started_,
                        capture_name, flags, zone());
}
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

#ifdef DEBUG
// Currently only used in an DCHECK.
static bool IsSpecialClassEscape(uc32 c) {
  switch (c) {
    case 'd':
    case 'D':
    case 's':
    case 'S':
    case 'w':
    case 'W':
      return true;
    default:
      return false;
  }
}
#endif


// In order to know whether an escape is a backreference or not we have to scan
// the entire regexp and find the number of capturing parentheses.  However we
// don't want to scan the regexp twice unless it is necessary.  This mini-parser
// is called when needed.  It can see the difference between capturing and
// noncapturing parentheses and can skip character classes and backslash-escaped
// characters.
void RegExpParser::ScanForCaptures() {
738 739
  DCHECK(!is_scanned_for_captures_);
  const int saved_position = position();
740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762
  // Start with captures started previous to current position
  int capture_count = captures_started();
  // Add count of captures after this position.
  int n;
  while ((n = current()) != kEndMarker) {
    Advance();
    switch (n) {
      case '\\':
        Advance();
        break;
      case '[': {
        int c;
        while ((c = current()) != kEndMarker) {
          Advance();
          if (c == '\\') {
            Advance();
          } else {
            if (c == ']') break;
          }
        }
        break;
      }
      case '(':
763 764 765 766 767 768 769 770 771 772 773
        if (current() == '?') {
          // At this point we could be in
          // * a non-capturing group '(:',
          // * a lookbehind assertion '(?<=' '(?<!'
          // * or a named capture '(?<'.
          //
          // Of these, only named captures are capturing groups.

          Advance();
          if (current() != '<') break;

774 775
          Advance();
          if (current() == '=' || current() == '!') break;
776 777 778 779 780

          // Found a possible named capture. It could turn out to be a syntax
          // error (e.g. an unterminated or invalid name), but that distinction
          // does not matter for our purposes.
          has_named_captures_ = true;
781 782
        }
        capture_count++;
783 784 785 786 787
        break;
    }
  }
  capture_count_ = capture_count;
  is_scanned_for_captures_ = true;
788
  Reset(saved_position);
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
}


bool RegExpParser::ParseBackReferenceIndex(int* index_out) {
  DCHECK_EQ('\\', current());
  DCHECK('1' <= Next() && Next() <= '9');
  // Try to parse a decimal literal that is no greater than the total number
  // of left capturing parentheses in the input.
  int start = position();
  int value = Next() - '0';
  Advance(2);
  while (true) {
    uc32 c = current();
    if (IsDecimalDigit(c)) {
      value = 10 * value + (c - '0');
      if (value > kMaxCaptures) {
        Reset(start);
        return false;
      }
      Advance();
    } else {
      break;
    }
  }
  if (value > captures_started()) {
814
    if (!is_scanned_for_captures_) ScanForCaptures();
815 816 817 818 819 820 821 822 823
    if (value > capture_count_) {
      Reset(start);
      return false;
    }
  }
  *index_out = value;
  return true;
}

824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839
static void push_code_unit(ZoneVector<uc16>* v, uint32_t code_unit) {
  if (code_unit <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
    v->push_back(code_unit);
  } else {
    v->push_back(unibrow::Utf16::LeadSurrogate(code_unit));
    v->push_back(unibrow::Utf16::TrailSurrogate(code_unit));
  }
}

const ZoneVector<uc16>* RegExpParser::ParseCaptureGroupName() {
  ZoneVector<uc16>* name =
      new (zone()->New(sizeof(ZoneVector<uc16>))) ZoneVector<uc16>(zone());

  bool at_start = true;
  while (true) {
    uc32 c = current();
840
    Advance();
841 842 843

    // Convert unicode escapes.
    if (c == '\\' && current() == 'u') {
844
      Advance();
845 846 847 848 849 850
      if (!ParseUnicodeEscape(&c)) {
        ReportError(CStrVector("Invalid Unicode escape sequence"));
        return nullptr;
      }
    }

851 852 853 854 855 856
    // The backslash char is misclassified as both ID_Start and ID_Continue.
    if (c == '\\') {
      ReportError(CStrVector("Invalid capture group name"));
      return nullptr;
    }

857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887
    if (at_start) {
      if (!IdentifierStart::Is(c)) {
        ReportError(CStrVector("Invalid capture group name"));
        return nullptr;
      }
      push_code_unit(name, c);
      at_start = false;
    } else {
      if (c == '>') {
        break;
      } else if (IdentifierPart::Is(c)) {
        push_code_unit(name, c);
      } else {
        ReportError(CStrVector("Invalid capture group name"));
        return nullptr;
      }
    }
  }

  return name;
}

bool RegExpParser::CreateNamedCaptureAtIndex(const ZoneVector<uc16>* name,
                                             int index) {
  DCHECK(0 < index && index <= captures_started_);
  DCHECK_NOT_NULL(name);

  if (named_captures_ == nullptr) {
    named_captures_ = new (zone()) ZoneList<RegExpCapture*>(1, zone());
  } else {
    // Check for duplicates and bail if we find any.
888
    // TODO(jgruber): O(n^2).
889 890 891 892 893 894 895 896 897
    for (const auto& named_capture : *named_captures_) {
      if (*named_capture->name() == *name) {
        ReportError(CStrVector("Duplicate capture group name"));
        return false;
      }
    }
  }

  RegExpCapture* capture = GetCapture(index);
898
  DCHECK_NULL(capture->name());
899 900 901 902 903 904 905 906 907 908 909 910 911 912 913

  capture->set_name(name);
  named_captures_->Add(capture, zone());

  return true;
}

bool RegExpParser::ParseNamedBackReference(RegExpBuilder* builder,
                                           RegExpParserState* state) {
  // The parser is assumed to be on the '<' in \k<name>.
  if (current() != '<') {
    ReportError(CStrVector("Invalid named reference"));
    return false;
  }

914
  Advance();
915 916 917 918 919 920 921 922
  const ZoneVector<uc16>* name = ParseCaptureGroupName();
  if (name == nullptr) {
    return false;
  }

  if (state->IsInsideCaptureGroup(name)) {
    builder->AddEmpty();
  } else {
923 924
    RegExpBackReference* atom =
        new (zone()) RegExpBackReference(builder->flags());
925 926 927 928 929 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 959 960 961 962 963 964 965 966 967 968
    atom->set_name(name);

    builder->AddAtom(atom);

    if (named_back_references_ == nullptr) {
      named_back_references_ =
          new (zone()) ZoneList<RegExpBackReference*>(1, zone());
    }
    named_back_references_->Add(atom, zone());
  }

  return true;
}

void RegExpParser::PatchNamedBackReferences() {
  if (named_back_references_ == nullptr) return;

  if (named_captures_ == nullptr) {
    ReportError(CStrVector("Invalid named capture referenced"));
    return;
  }

  // Look up and patch the actual capture for each named back reference.
  // TODO(jgruber): O(n^2), optimize if necessary.

  for (int i = 0; i < named_back_references_->length(); i++) {
    RegExpBackReference* ref = named_back_references_->at(i);

    int index = -1;
    for (const auto& capture : *named_captures_) {
      if (*capture->name() == *ref->name()) {
        index = capture->index();
        break;
      }
    }

    if (index == -1) {
      ReportError(CStrVector("Invalid named capture referenced"));
      return;
    }

    ref->set_capture(GetCapture(index));
  }
}
969 970 971 972 973 974 975

RegExpCapture* RegExpParser::GetCapture(int index) {
  // The index for the capture groups are one-based. Its index in the list is
  // zero-based.
  int know_captures =
      is_scanned_for_captures_ ? capture_count_ : captures_started_;
  DCHECK(index <= know_captures);
976
  if (captures_ == nullptr) {
977 978 979 980 981 982 983 984
    captures_ = new (zone()) ZoneList<RegExpCapture*>(know_captures, zone());
  }
  while (captures_->length() < know_captures) {
    captures_->Add(new (zone()) RegExpCapture(captures_->length() + 1), zone());
  }
  return captures_->at(index - 1);
}

985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002
Handle<FixedArray> RegExpParser::CreateCaptureNameMap() {
  if (named_captures_ == nullptr || named_captures_->is_empty())
    return Handle<FixedArray>();

  Factory* factory = isolate()->factory();

  int len = named_captures_->length() * 2;
  Handle<FixedArray> array = factory->NewFixedArray(len);

  for (int i = 0; i < named_captures_->length(); i++) {
    RegExpCapture* capture = named_captures_->at(i);
    MaybeHandle<String> name = factory->NewStringFromTwoByte(capture->name());
    array->set(i * 2, *name.ToHandleChecked());
    array->set(i * 2 + 1, Smi::FromInt(capture->index()));
  }

  return array;
}
1003

1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
bool RegExpParser::HasNamedCaptures() {
  if (has_named_captures_ || is_scanned_for_captures_) {
    return has_named_captures_;
  }

  ScanForCaptures();
  DCHECK(is_scanned_for_captures_);
  return has_named_captures_;
}

1014
bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(int index) {
1015
  for (RegExpParserState* s = this; s != nullptr; s = s->previous_state()) {
1016 1017 1018 1019 1020 1021 1022 1023 1024
    if (s->group_type() != CAPTURE) continue;
    // Return true if we found the matching capture index.
    if (index == s->capture_index()) return true;
    // Abort if index is larger than what has been parsed up till this state.
    if (index > s->capture_index()) return false;
  }
  return false;
}

1025 1026 1027
bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(
    const ZoneVector<uc16>* name) {
  DCHECK_NOT_NULL(name);
1028
  for (RegExpParserState* s = this; s != nullptr; s = s->previous_state()) {
1029 1030 1031 1032 1033
    if (s->capture_name() == nullptr) continue;
    if (*s->capture_name() == *name) return true;
  }
  return false;
}
1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105

// QuantifierPrefix ::
//   { DecimalDigits }
//   { DecimalDigits , }
//   { DecimalDigits , DecimalDigits }
//
// Returns true if parsing succeeds, and set the min_out and max_out
// values. Values are truncated to RegExpTree::kInfinity if they overflow.
bool RegExpParser::ParseIntervalQuantifier(int* min_out, int* max_out) {
  DCHECK_EQ(current(), '{');
  int start = position();
  Advance();
  int min = 0;
  if (!IsDecimalDigit(current())) {
    Reset(start);
    return false;
  }
  while (IsDecimalDigit(current())) {
    int next = current() - '0';
    if (min > (RegExpTree::kInfinity - next) / 10) {
      // Overflow. Skip past remaining decimal digits and return -1.
      do {
        Advance();
      } while (IsDecimalDigit(current()));
      min = RegExpTree::kInfinity;
      break;
    }
    min = 10 * min + next;
    Advance();
  }
  int max = 0;
  if (current() == '}') {
    max = min;
    Advance();
  } else if (current() == ',') {
    Advance();
    if (current() == '}') {
      max = RegExpTree::kInfinity;
      Advance();
    } else {
      while (IsDecimalDigit(current())) {
        int next = current() - '0';
        if (max > (RegExpTree::kInfinity - next) / 10) {
          do {
            Advance();
          } while (IsDecimalDigit(current()));
          max = RegExpTree::kInfinity;
          break;
        }
        max = 10 * max + next;
        Advance();
      }
      if (current() != '}') {
        Reset(start);
        return false;
      }
      Advance();
    }
  } else {
    Reset(start);
    return false;
  }
  *min_out = min;
  *max_out = max;
  return true;
}


uc32 RegExpParser::ParseOctalLiteral() {
  DCHECK(('0' <= current() && current() <= '7') || current() == kEndMarker);
  // For compatibility with some other browsers (not all), we parse
  // up to three octal digits with a value below 256.
1106
  // ES#prod-annexB-LegacyOctalEscapeSequence
1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137
  uc32 value = current() - '0';
  Advance();
  if ('0' <= current() && current() <= '7') {
    value = value * 8 + current() - '0';
    Advance();
    if (value < 32 && '0' <= current() && current() <= '7') {
      value = value * 8 + current() - '0';
      Advance();
    }
  }
  return value;
}


bool RegExpParser::ParseHexEscape(int length, uc32* value) {
  int start = position();
  uc32 val = 0;
  for (int i = 0; i < length; ++i) {
    uc32 c = current();
    int d = HexValue(c);
    if (d < 0) {
      Reset(start);
      return false;
    }
    val = val * 16 + d;
    Advance();
  }
  *value = val;
  return true;
}

1138
// This parses RegExpUnicodeEscapeSequence as described in ECMA262.
1139 1140 1141 1142
bool RegExpParser::ParseUnicodeEscape(uc32* value) {
  // Accept both \uxxxx and \u{xxxxxx} (if harmony unicode escapes are
  // allowed). In the latter case, the number of hex digits between { } is
  // arbitrary. \ and u have already been read.
1143
  if (current() == '{' && unicode()) {
1144 1145
    int start = position();
    Advance();
1146
    if (ParseUnlimitedLengthHexNumber(0x10FFFF, value)) {
1147 1148 1149 1150 1151 1152 1153 1154 1155
      if (current() == '}') {
        Advance();
        return true;
      }
    }
    Reset(start);
    return false;
  }
  // \u but no {, or \u{...} escapes not allowed.
1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
  bool result = ParseHexEscape(4, value);
  if (result && unicode() && unibrow::Utf16::IsLeadSurrogate(*value) &&
      current() == '\\') {
    // Attempt to read trail surrogate.
    int start = position();
    if (Next() == 'u') {
      Advance(2);
      uc32 trail;
      if (ParseHexEscape(4, &trail) &&
          unibrow::Utf16::IsTrailSurrogate(trail)) {
        *value = unibrow::Utf16::CombineSurrogatePair(static_cast<uc16>(*value),
                                                      static_cast<uc16>(trail));
        return true;
      }
    }
    Reset(start);
  }
  return result;
1174 1175
}

1176
#ifdef V8_INTL_SUPPORT
1177 1178 1179

namespace {

1180 1181
bool IsExactPropertyAlias(const char* property_name, UProperty property) {
  const char* short_name = u_getPropertyName(property, U_SHORT_PROPERTY_NAME);
1182 1183
  if (short_name != nullptr && strcmp(property_name, short_name) == 0)
    return true;
1184 1185 1186
  for (int i = 0;; i++) {
    const char* long_name = u_getPropertyName(
        property, static_cast<UPropertyNameChoice>(U_LONG_PROPERTY_NAME + i));
1187
    if (long_name == nullptr) break;
1188 1189 1190 1191 1192 1193 1194
    if (strcmp(property_name, long_name) == 0) return true;
  }
  return false;
}

bool IsExactPropertyValueAlias(const char* property_value_name,
                               UProperty property, int32_t property_value) {
1195 1196
  const char* short_name =
      u_getPropertyValueName(property, property_value, U_SHORT_PROPERTY_NAME);
1197
  if (short_name != nullptr && strcmp(property_value_name, short_name) == 0) {
1198 1199
    return true;
  }
1200 1201 1202 1203
  for (int i = 0;; i++) {
    const char* long_name = u_getPropertyValueName(
        property, property_value,
        static_cast<UPropertyNameChoice>(U_LONG_PROPERTY_NAME + i));
1204
    if (long_name == nullptr) break;
1205
    if (strcmp(property_value_name, long_name) == 0) return true;
1206 1207 1208 1209
  }
  return false;
}

1210 1211 1212
bool LookupPropertyValueName(UProperty property,
                             const char* property_value_name, bool negate,
                             ZoneList<CharacterRange>* result, Zone* zone) {
1213 1214 1215 1216 1217 1218
  UProperty property_for_lookup = property;
  if (property_for_lookup == UCHAR_SCRIPT_EXTENSIONS) {
    // For the property Script_Extensions, we have to do the property value
    // name lookup as if the property is Script.
    property_for_lookup = UCHAR_SCRIPT;
  }
1219
  int32_t property_value =
1220
      u_getPropertyValueEnum(property_for_lookup, property_value_name);
1221 1222
  if (property_value == UCHAR_INVALID_CODE) return false;

1223 1224
  // We require the property name to match exactly to one of the property value
  // aliases. However, u_getPropertyValueEnum uses loose matching.
1225
  if (!IsExactPropertyValueAlias(property_value_name, property_for_lookup,
1226
                                 property_value)) {
1227 1228 1229
    return false;
  }

1230
  UErrorCode ec = U_ZERO_ERROR;
1231 1232 1233
  icu::UnicodeSet set;
  set.applyIntPropertyValue(property, property_value, ec);
  bool success = ec == U_ZERO_ERROR && !set.isEmpty();
1234 1235

  if (success) {
1236 1237 1238 1239 1240 1241
    set.removeAllStrings();
    if (negate) set.complement();
    for (int i = 0; i < set.getRangeCount(); i++) {
      result->Add(
          CharacterRange::Range(set.getRangeStart(i), set.getRangeEnd(i)),
          zone);
1242 1243 1244 1245 1246
    }
  }
  return success;
}

1247 1248 1249 1250 1251
template <size_t N>
inline bool NameEquals(const char* name, const char (&literal)[N]) {
  return strncmp(name, literal, N + 1) == 0;
}

1252 1253 1254
bool LookupSpecialPropertyValueName(const char* name,
                                    ZoneList<CharacterRange>* result,
                                    bool negate, Zone* zone) {
1255
  if (NameEquals(name, "Any")) {
1256 1257 1258 1259 1260 1261
    if (negate) {
      // Leave the list of character ranges empty, since the negation of 'Any'
      // is the empty set.
    } else {
      result->Add(CharacterRange::Everything(), zone);
    }
1262 1263
  } else if (NameEquals(name, "ASCII")) {
    result->Add(negate ? CharacterRange::Range(0x80, String::kMaxCodePoint)
1264
                       : CharacterRange::Range(0x0, 0x7F),
1265 1266
                zone);
  } else if (NameEquals(name, "Assigned")) {
1267 1268
    return LookupPropertyValueName(UCHAR_GENERAL_CATEGORY, "Unassigned",
                                   !negate, result, zone);
1269 1270 1271 1272 1273 1274
  } else {
    return false;
  }
  return true;
}

1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298
// Explicitly whitelist supported binary properties. The spec forbids supporting
// properties outside of this set to ensure interoperability.
bool IsSupportedBinaryProperty(UProperty property) {
  switch (property) {
    case UCHAR_ALPHABETIC:
    // 'Any' is not supported by ICU. See LookupSpecialPropertyValueName.
    // 'ASCII' is not supported by ICU. See LookupSpecialPropertyValueName.
    case UCHAR_ASCII_HEX_DIGIT:
    // 'Assigned' is not supported by ICU. See LookupSpecialPropertyValueName.
    case UCHAR_BIDI_CONTROL:
    case UCHAR_BIDI_MIRRORED:
    case UCHAR_CASE_IGNORABLE:
    case UCHAR_CASED:
    case UCHAR_CHANGES_WHEN_CASEFOLDED:
    case UCHAR_CHANGES_WHEN_CASEMAPPED:
    case UCHAR_CHANGES_WHEN_LOWERCASED:
    case UCHAR_CHANGES_WHEN_NFKC_CASEFOLDED:
    case UCHAR_CHANGES_WHEN_TITLECASED:
    case UCHAR_CHANGES_WHEN_UPPERCASED:
    case UCHAR_DASH:
    case UCHAR_DEFAULT_IGNORABLE_CODE_POINT:
    case UCHAR_DEPRECATED:
    case UCHAR_DIACRITIC:
    case UCHAR_EMOJI:
1299 1300 1301
#if U_ICU_VERSION_MAJOR_NUM >= 60
    case UCHAR_EMOJI_COMPONENT:
#endif
1302 1303 1304
    case UCHAR_EMOJI_MODIFIER_BASE:
    case UCHAR_EMOJI_MODIFIER:
    case UCHAR_EMOJI_PRESENTATION:
Jungshik Shin's avatar
Jungshik Shin committed
1305 1306 1307
#if U_ICU_VERSION_MAJOR_NUM >= 62
    case UCHAR_EXTENDED_PICTOGRAPHIC:
#endif
1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325
    case UCHAR_EXTENDER:
    case UCHAR_GRAPHEME_BASE:
    case UCHAR_GRAPHEME_EXTEND:
    case UCHAR_HEX_DIGIT:
    case UCHAR_ID_CONTINUE:
    case UCHAR_ID_START:
    case UCHAR_IDEOGRAPHIC:
    case UCHAR_IDS_BINARY_OPERATOR:
    case UCHAR_IDS_TRINARY_OPERATOR:
    case UCHAR_JOIN_CONTROL:
    case UCHAR_LOGICAL_ORDER_EXCEPTION:
    case UCHAR_LOWERCASE:
    case UCHAR_MATH:
    case UCHAR_NONCHARACTER_CODE_POINT:
    case UCHAR_PATTERN_SYNTAX:
    case UCHAR_PATTERN_WHITE_SPACE:
    case UCHAR_QUOTATION_MARK:
    case UCHAR_RADICAL:
1326 1327 1328
#if U_ICU_VERSION_MAJOR_NUM >= 60
    case UCHAR_REGIONAL_INDICATOR:
#endif
1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344
    case UCHAR_S_TERM:
    case UCHAR_SOFT_DOTTED:
    case UCHAR_TERMINAL_PUNCTUATION:
    case UCHAR_UNIFIED_IDEOGRAPH:
    case UCHAR_UPPERCASE:
    case UCHAR_VARIATION_SELECTOR:
    case UCHAR_WHITE_SPACE:
    case UCHAR_XID_CONTINUE:
    case UCHAR_XID_START:
      return true;
    default:
      break;
  }
  return false;
}

1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357
bool IsUnicodePropertyValueCharacter(char c) {
  // https://tc39.github.io/proposal-regexp-unicode-property-escapes/
  //
  // Note that using this to validate each parsed char is quite conservative.
  // A possible alternative solution would be to only ensure the parsed
  // property name/value candidate string does not contain '\0' characters and
  // let ICU lookups trigger the final failure.
  if ('a' <= c && c <= 'z') return true;
  if ('A' <= c && c <= 'Z') return true;
  if ('0' <= c && c <= '9') return true;
  return (c == '_');
}

1358 1359
}  // anonymous namespace

1360 1361 1362 1363
bool RegExpParser::ParsePropertyClassName(std::vector<char>* name_1,
                                          std::vector<char>* name_2) {
  DCHECK(name_1->empty());
  DCHECK(name_2->empty());
1364 1365 1366 1367 1368 1369 1370 1371
  // Parse the property class as follows:
  // - In \p{name}, 'name' is interpreted
  //   - either as a general category property value name.
  //   - or as a binary property name.
  // - In \p{name=value}, 'name' is interpreted as an enumerated property name,
  //   and 'value' is interpreted as one of the available property value names.
  // - Aliases in PropertyAlias.txt and PropertyValueAlias.txt can be used.
  // - Loose matching is not applied.
1372
  if (current() == '{') {
1373 1374
    // Parse \p{[PropertyName=]PropertyNameValue}
    for (Advance(); current() != '}' && current() != '='; Advance()) {
1375
      if (!IsUnicodePropertyValueCharacter(current())) return false;
1376
      if (!has_next()) return false;
1377
      name_1->push_back(static_cast<char>(current()));
1378 1379 1380
    }
    if (current() == '=') {
      for (Advance(); current() != '}'; Advance()) {
1381
        if (!IsUnicodePropertyValueCharacter(current())) return false;
1382
        if (!has_next()) return false;
1383
        name_2->push_back(static_cast<char>(current()));
1384
      }
1385
      name_2->push_back(0);  // null-terminate string.
1386 1387
    }
  } else {
1388
    return false;
1389 1390
  }
  Advance();
1391
  name_1->push_back(0);  // null-terminate string.
1392

1393 1394 1395 1396
  DCHECK(name_1->size() - 1 == std::strlen(name_1->data()));
  DCHECK(name_2->empty() || name_2->size() - 1 == std::strlen(name_2->data()));
  return true;
}
1397

1398 1399 1400 1401 1402
bool RegExpParser::AddPropertyClassRange(ZoneList<CharacterRange>* add_to,
                                         bool negate,
                                         const std::vector<char>& name_1,
                                         const std::vector<char>& name_2) {
  if (name_2.empty()) {
1403
    // First attempt to interpret as general category property value name.
1404
    const char* name = name_1.data();
1405
    if (LookupPropertyValueName(UCHAR_GENERAL_CATEGORY_MASK, name, negate,
1406
                                add_to, zone())) {
1407 1408 1409
      return true;
    }
    // Interpret "Any", "ASCII", and "Assigned".
1410
    if (LookupSpecialPropertyValueName(name, add_to, negate, zone())) {
1411 1412 1413 1414
      return true;
    }
    // Then attempt to interpret as binary property name with value name 'Y'.
    UProperty property = u_getPropertyEnum(name);
1415
    if (!IsSupportedBinaryProperty(property)) return false;
1416
    if (!IsExactPropertyAlias(name, property)) return false;
1417
    return LookupPropertyValueName(property, negate ? "N" : "Y", false, add_to,
1418
                                   zone());
1419 1420 1421
  } else {
    // Both property name and value name are specified. Attempt to interpret
    // the property name as enumerated property.
1422 1423
    const char* property_name = name_1.data();
    const char* value_name = name_2.data();
1424 1425
    UProperty property = u_getPropertyEnum(property_name);
    if (!IsExactPropertyAlias(property_name, property)) return false;
1426 1427 1428 1429 1430 1431 1432
    if (property == UCHAR_GENERAL_CATEGORY) {
      // We want to allow aggregate value names such as "Letter".
      property = UCHAR_GENERAL_CATEGORY_MASK;
    } else if (property != UCHAR_SCRIPT &&
               property != UCHAR_SCRIPT_EXTENSIONS) {
      return false;
    }
1433
    return LookupPropertyValueName(property, value_name, negate, add_to,
1434
                                   zone());
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 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501
RegExpTree* RegExpParser::GetPropertySequence(const std::vector<char>& name_1) {
  if (!FLAG_harmony_regexp_sequence) return nullptr;
  const char* name = name_1.data();
  const uc32* sequence_list = nullptr;
  JSRegExp::Flags flags = JSRegExp::kUnicode;
  if (NameEquals(name, "Emoji_Flag_Sequence")) {
    sequence_list = UnicodePropertySequences::kEmojiFlagSequences;
  } else if (NameEquals(name, "Emoji_Tag_Sequence")) {
    sequence_list = UnicodePropertySequences::kEmojiTagSequences;
  } else if (NameEquals(name, "Emoji_ZWJ_Sequence")) {
    sequence_list = UnicodePropertySequences::kEmojiZWJSequences;
  }
  if (sequence_list != nullptr) {
    // TODO(yangguo): this creates huge regexp code. Alternative to this is
    // to create a new operator that checks for these sequences at runtime.
    RegExpBuilder builder(zone(), flags);
    while (true) {                   // Iterate through list of sequences.
      while (*sequence_list != 0) {  // Iterate through sequence.
        builder.AddUnicodeCharacter(*sequence_list);
        sequence_list++;
      }
      sequence_list++;
      if (*sequence_list == 0) break;
      builder.NewAlternative();
    }
    return builder.ToRegExp();
  }

  if (NameEquals(name, "Emoji_Keycap_Sequence")) {
    // https://unicode.org/reports/tr51/#def_emoji_keycap_sequence
    // emoji_keycap_sequence := [0-9#*] \x{FE0F 20E3}
    RegExpBuilder builder(zone(), flags);
    ZoneList<CharacterRange>* prefix_ranges =
        new (zone()) ZoneList<CharacterRange>(2, zone());
    prefix_ranges->Add(CharacterRange::Range('0', '9'), zone());
    prefix_ranges->Add(CharacterRange::Singleton('#'), zone());
    prefix_ranges->Add(CharacterRange::Singleton('*'), zone());
    builder.AddCharacterClass(
        new (zone()) RegExpCharacterClass(zone(), prefix_ranges, flags));
    builder.AddCharacter(0xFE0F);
    builder.AddCharacter(0x20E3);
    return builder.ToRegExp();
  } else if (NameEquals(name, "Emoji_Modifier_Sequence")) {
    // https://unicode.org/reports/tr51/#def_emoji_modifier_sequence
    // emoji_modifier_sequence := emoji_modifier_base emoji_modifier
    RegExpBuilder builder(zone(), flags);
    ZoneList<CharacterRange>* modifier_base_ranges =
        new (zone()) ZoneList<CharacterRange>(2, zone());
    LookupPropertyValueName(UCHAR_EMOJI_MODIFIER_BASE, "Y", false,
                            modifier_base_ranges, zone());
    builder.AddCharacterClass(
        new (zone()) RegExpCharacterClass(zone(), modifier_base_ranges, flags));
    ZoneList<CharacterRange>* modifier_ranges =
        new (zone()) ZoneList<CharacterRange>(2, zone());
    LookupPropertyValueName(UCHAR_EMOJI_MODIFIER, "Y", false, modifier_ranges,
                            zone());
    builder.AddCharacterClass(
        new (zone()) RegExpCharacterClass(zone(), modifier_ranges, flags));
    return builder.ToRegExp();
  }

  return nullptr;
}

1502
#else  // V8_INTL_SUPPORT
1503

1504 1505
bool RegExpParser::ParsePropertyClassName(std::vector<char>* name_1,
                                          std::vector<char>* name_2) {
1506
  return false;
1507
}
1508

1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519
bool RegExpParser::AddPropertyClassRange(ZoneList<CharacterRange>* add_to,
                                         bool negate,
                                         const std::vector<char>& name_1,
                                         const std::vector<char>& name_2) {
  return false;
}

RegExpTree* RegExpParser::GetPropertySequence(const std::vector<char>& name) {
  return nullptr;
}

1520
#endif  // V8_INTL_SUPPORT
1521

1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541
bool RegExpParser::ParseUnlimitedLengthHexNumber(int max_value, uc32* value) {
  uc32 x = 0;
  int d = HexValue(current());
  if (d < 0) {
    return false;
  }
  while (d >= 0) {
    x = x * 16 + d;
    if (x > max_value) {
      return false;
    }
    Advance();
    d = HexValue(current());
  }
  *value = x;
  return true;
}


uc32 RegExpParser::ParseClassCharacterEscape() {
1542
  DCHECK_EQ('\\', current());
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568
  DCHECK(has_next() && !IsSpecialClassEscape(Next()));
  Advance();
  switch (current()) {
    case 'b':
      Advance();
      return '\b';
    // ControlEscape :: one of
    //   f n r t v
    case 'f':
      Advance();
      return '\f';
    case 'n':
      Advance();
      return '\n';
    case 'r':
      Advance();
      return '\r';
    case 't':
      Advance();
      return '\t';
    case 'v':
      Advance();
      return '\v';
    case 'c': {
      uc32 controlLetter = Next();
      uc32 letter = controlLetter & ~('A' ^ 'a');
1569 1570 1571
      // Inside a character class, we also accept digits and underscore as
      // control characters, unless with /u. See Annex B:
      // ES#prod-annexB-ClassControlLetter
1572
      if (letter >= 'A' && letter <= 'Z') {
1573 1574
        Advance(2);
        // Control letters mapped to ASCII control characters in the range
1575 1576
        // 0x00-0x1F.
        return controlLetter & 0x1F;
1577
      }
1578 1579 1580 1581 1582 1583 1584 1585
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
        ReportError(CStrVector("Invalid class escape"));
        return 0;
      }
      if ((controlLetter >= '0' && controlLetter <= '9') ||
          controlLetter == '_') {
        Advance(2);
1586
        return controlLetter & 0x1F;
1587
      }
1588 1589
      // We match JSC in reading the backslash as a literal
      // character instead of as starting an escape.
1590
      // TODO(v8:6201): Not yet covered by the spec.
1591 1592 1593
      return '\\';
    }
    case '0':
1594 1595 1596 1597 1598
      // With /u, \0 is interpreted as NUL if not followed by another digit.
      if (unicode() && !(Next() >= '0' && Next() <= '9')) {
        Advance();
        return 0;
      }
1599
      V8_FALLTHROUGH;
1600 1601 1602 1603 1604 1605 1606 1607 1608 1609
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
      // For compatibility, we interpret a decimal escape that isn't
      // a back reference (and therefore either \0 or not valid according
      // to the specification) as a 1..3 digit octal character code.
1610
      // ES#prod-annexB-LegacyOctalEscapeSequence
1611 1612 1613 1614 1615
      if (unicode()) {
        // With /u, decimal escape is not interpreted as octal character code.
        ReportError(CStrVector("Invalid class escape"));
        return 0;
      }
1616 1617 1618 1619
      return ParseOctalLiteral();
    case 'x': {
      Advance();
      uc32 value;
1620 1621 1622 1623 1624
      if (ParseHexEscape(2, &value)) return value;
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
        ReportError(CStrVector("Invalid escape"));
        return 0;
1625
      }
1626 1627 1628
      // If \x is not followed by a two-digit hexadecimal, treat it
      // as an identity escape.
      return 'x';
1629 1630 1631 1632
    }
    case 'u': {
      Advance();
      uc32 value;
1633 1634 1635 1636 1637
      if (ParseUnicodeEscape(&value)) return value;
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
        ReportError(CStrVector("Invalid unicode escape"));
        return 0;
1638
      }
1639 1640 1641
      // If \u is not followed by a two-digit hexadecimal, treat it
      // as an identity escape.
      return 'u';
1642 1643 1644
    }
    default: {
      uc32 result = current();
1645
      // With /u, no identity escapes except for syntax characters and '-' are
1646
      // allowed. Otherwise, all identity escapes are allowed.
1647
      if (!unicode() || IsSyntaxCharacterOrSlash(result) || result == '-') {
1648 1649 1650 1651 1652 1653 1654 1655 1656 1657
        Advance();
        return result;
      }
      ReportError(CStrVector("Invalid escape"));
      return 0;
    }
  }
  return 0;
}

1658 1659 1660 1661 1662 1663
void RegExpParser::ParseClassEscape(ZoneList<CharacterRange>* ranges,
                                    Zone* zone,
                                    bool add_unicode_case_equivalents,
                                    uc32* char_out, bool* is_class_escape) {
  uc32 current_char = current();
  if (current_char == '\\') {
1664 1665 1666 1667 1668 1669 1670
    switch (Next()) {
      case 'w':
      case 'W':
      case 'd':
      case 'D':
      case 's':
      case 'S': {
1671 1672
        CharacterRange::AddClassEscape(static_cast<char>(Next()), ranges,
                                       add_unicode_case_equivalents, zone);
1673
        Advance(2);
1674 1675
        *is_class_escape = true;
        return;
1676 1677
      }
      case kEndMarker:
1678 1679 1680 1681
        ReportError(CStrVector("\\ at end of pattern"));
        return;
      case 'p':
      case 'P':
1682
        if (unicode()) {
1683 1684
          bool negate = Next() == 'P';
          Advance(2);
1685 1686 1687
          std::vector<char> name_1, name_2;
          if (!ParsePropertyClassName(&name_1, &name_2) ||
              !AddPropertyClassRange(ranges, negate, name_1, name_2)) {
1688 1689 1690 1691 1692 1693
            ReportError(CStrVector("Invalid property name in character class"));
          }
          *is_class_escape = true;
          return;
        }
        break;
1694
      default:
1695
        break;
1696
    }
1697 1698
    *char_out = ParseClassCharacterEscape();
    *is_class_escape = false;
1699 1700
  } else {
    Advance();
1701 1702
    *char_out = current_char;
    *is_class_escape = false;
1703
  }
1704
}
1705

1706
RegExpTree* RegExpParser::ParseCharacterClass(const RegExpBuilder* builder) {
1707
  static const char* kUnterminated = "Unterminated character class";
1708
  static const char* kRangeInvalid = "Invalid character class";
1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719
  static const char* kRangeOutOfOrder = "Range out of order in character class";

  DCHECK_EQ(current(), '[');
  Advance();
  bool is_negated = false;
  if (current() == '^') {
    is_negated = true;
    Advance();
  }
  ZoneList<CharacterRange>* ranges =
      new (zone()) ZoneList<CharacterRange>(2, zone());
1720
  bool add_unicode_case_equivalents = unicode() && builder->ignore_case();
1721
  while (has_more() && current() != ']') {
1722 1723 1724 1725
    uc32 char_1, char_2;
    bool is_class_1, is_class_2;
    ParseClassEscape(ranges, zone(), add_unicode_case_equivalents, &char_1,
                     &is_class_1 CHECK_FAILED);
1726 1727 1728 1729 1730 1731 1732
    if (current() == '-') {
      Advance();
      if (current() == kEndMarker) {
        // If we reach the end we break out of the loop and let the
        // following code report an error.
        break;
      } else if (current() == ']') {
1733
        if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1734 1735 1736
        ranges->Add(CharacterRange::Singleton('-'), zone());
        break;
      }
1737 1738 1739
      ParseClassEscape(ranges, zone(), add_unicode_case_equivalents, &char_2,
                       &is_class_2 CHECK_FAILED);
      if (is_class_1 || is_class_2) {
1740
        // Either end is an escaped character class. Treat the '-' verbatim.
1741 1742 1743 1744
        if (unicode()) {
          // ES2015 21.2.2.15.1 step 1.
          return ReportError(CStrVector(kRangeInvalid));
        }
1745
        if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1746
        ranges->Add(CharacterRange::Singleton('-'), zone());
1747
        if (!is_class_2) ranges->Add(CharacterRange::Singleton(char_2), zone());
1748 1749
        continue;
      }
1750
      // ES2015 21.2.2.15.1 step 6.
1751
      if (char_1 > char_2) {
1752
        return ReportError(CStrVector(kRangeOutOfOrder));
1753
      }
1754
      ranges->Add(CharacterRange::Range(char_1, char_2), zone());
1755
    } else {
1756
      if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1757 1758 1759
    }
  }
  if (!has_more()) {
1760
    return ReportError(CStrVector(kUnterminated));
1761 1762
  }
  Advance();
1763 1764
  RegExpCharacterClass::CharacterClassFlags character_class_flags;
  if (is_negated) character_class_flags = RegExpCharacterClass::NEGATED;
1765 1766
  return new (zone()) RegExpCharacterClass(zone(), ranges, builder->flags(),
                                           character_class_flags);
1767 1768 1769 1770 1771 1772 1773
}


#undef CHECK_FAILED


bool RegExpParser::ParseRegExp(Isolate* isolate, Zone* zone,
1774 1775
                               FlatStringReader* input, JSRegExp::Flags flags,
                               RegExpCompileData* result) {
1776
  DCHECK(result != nullptr);
1777
  RegExpParser parser(input, &result->error, flags, isolate, zone);
1778 1779
  RegExpTree* tree = parser.ParsePattern();
  if (parser.failed()) {
1780
    DCHECK(tree == nullptr);
1781 1782
    DCHECK(!result->error.is_null());
  } else {
1783
    DCHECK(tree != nullptr);
1784
    DCHECK(result->error.is_null());
1785
    if (FLAG_trace_regexp_parser) {
1786
      StdoutStream os;
1787 1788 1789
      tree->Print(os, zone);
      os << "\n";
    }
1790 1791 1792 1793
    result->tree = tree;
    int capture_count = parser.captures_started();
    result->simple = tree->IsAtom() && parser.simple() && capture_count == 0;
    result->contains_anchor = parser.contains_anchor();
1794
    result->capture_name_map = parser.CreateCaptureNameMap();
1795 1796 1797 1798 1799
    result->capture_count = capture_count;
  }
  return !parser.failed();
}

1800
RegExpBuilder::RegExpBuilder(Zone* zone, JSRegExp::Flags flags)
1801 1802
    : zone_(zone),
      pending_empty_(false),
1803
      flags_(flags),
1804
      characters_(nullptr),
1805
      pending_surrogate_(kNoPendingSurrogate),
1806 1807 1808 1809 1810 1811 1812 1813 1814 1815
      terms_(),
      alternatives_()
#ifdef DEBUG
      ,
      last_added_(ADD_NONE)
#endif
{
}


1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828
void RegExpBuilder::AddLeadSurrogate(uc16 lead_surrogate) {
  DCHECK(unibrow::Utf16::IsLeadSurrogate(lead_surrogate));
  FlushPendingSurrogate();
  // Hold onto the lead surrogate, waiting for a trail surrogate to follow.
  pending_surrogate_ = lead_surrogate;
}


void RegExpBuilder::AddTrailSurrogate(uc16 trail_surrogate) {
  DCHECK(unibrow::Utf16::IsTrailSurrogate(trail_surrogate));
  if (pending_surrogate_ != kNoPendingSurrogate) {
    uc16 lead_surrogate = pending_surrogate_;
    pending_surrogate_ = kNoPendingSurrogate;
1829 1830 1831 1832
    DCHECK(unibrow::Utf16::IsLeadSurrogate(lead_surrogate));
    uc32 combined =
        unibrow::Utf16::CombineSurrogatePair(lead_surrogate, trail_surrogate);
    if (NeedsDesugaringForIgnoreCase(combined)) {
1833
      AddCharacterClassForDesugaring(combined);
1834 1835 1836 1837 1838
    } else {
      ZoneList<uc16> surrogate_pair(2, zone());
      surrogate_pair.Add(lead_surrogate, zone());
      surrogate_pair.Add(trail_surrogate, zone());
      RegExpAtom* atom =
1839
          new (zone()) RegExpAtom(surrogate_pair.ToConstVector(), flags_);
1840 1841
      AddAtom(atom);
    }
1842 1843 1844 1845 1846 1847 1848 1849 1850 1851
  } else {
    pending_surrogate_ = trail_surrogate;
    FlushPendingSurrogate();
  }
}


void RegExpBuilder::FlushPendingSurrogate() {
  if (pending_surrogate_ != kNoPendingSurrogate) {
    DCHECK(unicode());
1852 1853
    uc32 c = pending_surrogate_;
    pending_surrogate_ = kNoPendingSurrogate;
1854
    AddCharacterClassForDesugaring(c);
1855 1856 1857 1858
  }
}


1859
void RegExpBuilder::FlushCharacters() {
1860
  FlushPendingSurrogate();
1861
  pending_empty_ = false;
1862
  if (characters_ != nullptr) {
1863 1864
    RegExpTree* atom =
        new (zone()) RegExpAtom(characters_->ToConstVector(), flags_);
1865
    characters_ = nullptr;
1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888
    text_.Add(atom, zone());
    LAST(ADD_ATOM);
  }
}


void RegExpBuilder::FlushText() {
  FlushCharacters();
  int num_text = text_.length();
  if (num_text == 0) {
    return;
  } else if (num_text == 1) {
    terms_.Add(text_.last(), zone());
  } else {
    RegExpText* text = new (zone()) RegExpText(zone());
    for (int i = 0; i < num_text; i++) text_.Get(i)->AppendToText(text, zone());
    terms_.Add(text, zone());
  }
  text_.Clear();
}


void RegExpBuilder::AddCharacter(uc16 c) {
1889
  FlushPendingSurrogate();
1890
  pending_empty_ = false;
1891
  if (NeedsDesugaringForIgnoreCase(c)) {
1892
    AddCharacterClassForDesugaring(c);
1893
  } else {
1894
    if (characters_ == nullptr) {
1895 1896 1897 1898
      characters_ = new (zone()) ZoneList<uc16>(4, zone());
    }
    characters_->Add(c, zone());
    LAST(ADD_CHAR);
1899 1900 1901 1902
  }
}


1903
void RegExpBuilder::AddUnicodeCharacter(uc32 c) {
1904
  if (c > static_cast<uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
1905 1906 1907 1908 1909 1910 1911
    DCHECK(unicode());
    AddLeadSurrogate(unibrow::Utf16::LeadSurrogate(c));
    AddTrailSurrogate(unibrow::Utf16::TrailSurrogate(c));
  } else if (unicode() && unibrow::Utf16::IsLeadSurrogate(c)) {
    AddLeadSurrogate(c);
  } else if (unicode() && unibrow::Utf16::IsTrailSurrogate(c)) {
    AddTrailSurrogate(c);
1912 1913 1914 1915 1916
  } else {
    AddCharacter(static_cast<uc16>(c));
  }
}

1917 1918 1919 1920 1921 1922 1923
void RegExpBuilder::AddEscapedUnicodeCharacter(uc32 character) {
  // A lead or trail surrogate parsed via escape sequence will not
  // pair up with any preceding lead or following trail surrogate.
  FlushPendingSurrogate();
  AddUnicodeCharacter(character);
  FlushPendingSurrogate();
}
1924

1925 1926 1927
void RegExpBuilder::AddEmpty() { pending_empty_ = true; }


1928
void RegExpBuilder::AddCharacterClass(RegExpCharacterClass* cc) {
1929
  if (NeedsDesugaringForUnicode(cc)) {
1930
    // With /u, character class needs to be desugared, so it
1931 1932 1933 1934 1935 1936 1937
    // must be a standalone term instead of being part of a RegExpText.
    AddTerm(cc);
  } else {
    AddAtom(cc);
  }
}

1938 1939
void RegExpBuilder::AddCharacterClassForDesugaring(uc32 c) {
  AddTerm(new (zone()) RegExpCharacterClass(
1940 1941
      zone(), CharacterRange::List(zone(), CharacterRange::Singleton(c)),
      flags_));
1942 1943 1944
}


1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960
void RegExpBuilder::AddAtom(RegExpTree* term) {
  if (term->IsEmpty()) {
    AddEmpty();
    return;
  }
  if (term->IsTextElement()) {
    FlushCharacters();
    text_.Add(term, zone());
  } else {
    FlushText();
    terms_.Add(term, zone());
  }
  LAST(ADD_ATOM);
}


1961 1962 1963 1964 1965 1966 1967
void RegExpBuilder::AddTerm(RegExpTree* term) {
  FlushText();
  terms_.Add(term, zone());
  LAST(ADD_ATOM);
}


1968 1969
void RegExpBuilder::AddAssertion(RegExpTree* assert) {
  FlushText();
1970 1971 1972 1973 1974 1975
  if (terms_.length() > 0 && terms_.last()->IsAssertion()) {
    // Omit repeated assertions of the same type.
    RegExpAssertion* last = terms_.last()->AsAssertion();
    RegExpAssertion* next = assert->AsAssertion();
    if (last->assertion_type() == next->assertion_type()) return;
  }
1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000
  terms_.Add(assert, zone());
  LAST(ADD_ASSERT);
}


void RegExpBuilder::NewAlternative() { FlushTerms(); }


void RegExpBuilder::FlushTerms() {
  FlushText();
  int num_terms = terms_.length();
  RegExpTree* alternative;
  if (num_terms == 0) {
    alternative = new (zone()) RegExpEmpty();
  } else if (num_terms == 1) {
    alternative = terms_.last();
  } else {
    alternative = new (zone()) RegExpAlternative(terms_.GetList(zone()));
  }
  alternatives_.Add(alternative, zone());
  terms_.Clear();
  LAST(ADD_NONE);
}


2001 2002
bool RegExpBuilder::NeedsDesugaringForUnicode(RegExpCharacterClass* cc) {
  if (!unicode()) return false;
2003 2004 2005 2006
  // TODO(yangguo): we could be smarter than this. Case-insensitivity does not
  // necessarily mean that we need to desugar. It's probably nicer to have a
  // separate pass to figure out unicode desugarings.
  if (ignore_case()) return true;
2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021
  ZoneList<CharacterRange>* ranges = cc->ranges(zone());
  CharacterRange::Canonicalize(ranges);
  for (int i = ranges->length() - 1; i >= 0; i--) {
    uc32 from = ranges->at(i).from();
    uc32 to = ranges->at(i).to();
    // Check for non-BMP characters.
    if (to >= kNonBmpStart) return true;
    // Check for lone surrogates.
    if (from <= kTrailSurrogateEnd && to >= kLeadSurrogateStart) return true;
  }
  return false;
}


bool RegExpBuilder::NeedsDesugaringForIgnoreCase(uc32 c) {
2022
#ifdef V8_INTL_SUPPORT
2023
  if (unicode() && ignore_case()) {
2024 2025 2026 2027
    icu::UnicodeSet set(c, c);
    set.closeOver(USET_CASE_INSENSITIVE);
    set.removeAllStrings();
    return set.size() > 1;
2028 2029 2030
  }
  // In the case where ICU is not included, we act as if the unicode flag is
  // not set, and do not desugar.
2031
#endif  // V8_INTL_SUPPORT
2032 2033 2034 2035
  return false;
}


2036 2037 2038 2039 2040 2041 2042 2043
RegExpTree* RegExpBuilder::ToRegExp() {
  FlushTerms();
  int num_alternatives = alternatives_.length();
  if (num_alternatives == 0) return new (zone()) RegExpEmpty();
  if (num_alternatives == 1) return alternatives_.last();
  return new (zone()) RegExpDisjunction(alternatives_.GetList(zone()));
}

2044
bool RegExpBuilder::AddQuantifierToAtom(
2045
    int min, int max, RegExpQuantifier::QuantifierType quantifier_type) {
2046
  FlushPendingSurrogate();
2047 2048
  if (pending_empty_) {
    pending_empty_ = false;
2049
    return true;
2050 2051
  }
  RegExpTree* atom;
2052
  if (characters_ != nullptr) {
2053 2054 2055 2056 2057 2058
    DCHECK(last_added_ == ADD_CHAR);
    // Last atom was character.
    Vector<const uc16> char_vector = characters_->ToConstVector();
    int num_chars = char_vector.length();
    if (num_chars > 1) {
      Vector<const uc16> prefix = char_vector.SubVector(0, num_chars - 1);
2059
      text_.Add(new (zone()) RegExpAtom(prefix, flags_), zone());
2060 2061
      char_vector = char_vector.SubVector(num_chars - 1, num_chars);
    }
2062
    characters_ = nullptr;
2063
    atom = new (zone()) RegExpAtom(char_vector, flags_);
2064 2065 2066 2067 2068 2069 2070 2071
    FlushText();
  } else if (text_.length() > 0) {
    DCHECK(last_added_ == ADD_ATOM);
    atom = text_.RemoveLast();
    FlushText();
  } else if (terms_.length() > 0) {
    DCHECK(last_added_ == ADD_ATOM);
    atom = terms_.RemoveLast();
2072 2073 2074 2075 2076 2077 2078 2079
    if (atom->IsLookaround()) {
      // With /u, lookarounds are not quantifiable.
      if (unicode()) return false;
      // Lookbehinds are not quantifiable.
      if (atom->AsLookaround()->type() == RegExpLookaround::LOOKBEHIND) {
        return false;
      }
    }
2080 2081 2082 2083
    if (atom->max_match() == 0) {
      // Guaranteed to only match an empty string.
      LAST(ADD_TERM);
      if (min == 0) {
2084
        return true;
2085 2086
      }
      terms_.Add(atom, zone());
2087
      return true;
2088 2089 2090 2091 2092 2093 2094 2095
    }
  } else {
    // Only call immediately after adding an atom or character!
    UNREACHABLE();
  }
  terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom),
             zone());
  LAST(ADD_TERM);
2096
  return true;
2097 2098 2099 2100
}

}  // namespace internal
}  // namespace v8