regexp-parser.cc 66 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/execution/isolate.h"
10
#include "src/heap/factory.h"
11
#include "src/objects/objects-inl.h"
12
#include "src/regexp/property-sequences.h"
13
#include "src/regexp/regexp-macro-assembler.h"
14
#include "src/regexp/regexp.h"
15
#include "src/strings/char-predicates-inl.h"
16 17
#include "src/utils/ostreams.h"
#include "src/utils/utils.h"
18
#include "src/zone/zone-list-inl.h"
19

20
#ifdef V8_INTL_SUPPORT
21
#include "unicode/uniset.h"
22
#endif  // V8_INTL_SUPPORT
23

24 25 26
namespace v8 {
namespace internal {

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

49 50
template <bool update_position>
inline uc32 RegExpParser::ReadNext() {
51 52 53
  int position = next_pos_;
  uc32 c0 = in()->Get(position);
  position++;
54 55
  // Read the whole surrogate pair in case of unicode flag, if possible.
  if (unicode() && position < in()->length() &&
56 57 58 59 60 61 62 63 64 65 66 67
      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;
}


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

76
void RegExpParser::Advance() {
77
  if (has_next()) {
78 79
    StackLimitCheck check(isolate());
    if (check.HasOverflowed()) {
80
      if (FLAG_correctness_fuzzer_suppressions) {
81 82
        FATAL("Aborting on stack overflow");
      }
83
      ReportError(RegExpError::kStackOverflow);
84
    } else if (zone()->excess_allocation()) {
85 86 87
      if (FLAG_correctness_fuzzer_suppressions) {
        FATAL("Aborting on excess zone allocation");
      }
88
      ReportError(RegExpError::kTooLarge);
89
    } 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
RegExpTree* RegExpParser::ReportError(RegExpError error) {
141
  if (failed_) return nullptr;  // Do not overwrite any existing error.
142
  failed_ = true;
143 144 145
  error_ = error;
  error_pos_ = position();
  // Zip to the end to make sure no more input is read.
146 147
  current_ = kEndMarker;
  next_pos_ = in()->length();
148
  return nullptr;
149 150
}

151 152
#define CHECK_FAILED /**/);    \
  if (failed_) return nullptr; \
153 154 155 156 157 158
  ((void)0

// Pattern ::
//   Disjunction
RegExpTree* RegExpParser::ParsePattern() {
  RegExpTree* result = ParseDisjunction(CHECK_FAILED);
159
  PatchNamedBackReferences(CHECK_FAILED);
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
  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.
182
  RegExpParserState initial_state(nullptr, INITIAL, RegExpLookaround::LOOKAHEAD,
183
                                  0, nullptr, top_level_flags_, zone());
184 185 186 187 188 189 190 191
  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.
192
          return ReportError(RegExpError::kUnterminatedGroup);
193 194 195 196 197 198
        }
        DCHECK_EQ(INITIAL, state->group_type());
        // Parsing completed successfully.
        return builder->ToRegExp();
      case ')': {
        if (!state->IsSubexpression()) {
199
          return ReportError(RegExpError::kUnmatchedParen);
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
        }
        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) {
215 216 217 218
          if (state->IsNamedCapture()) {
            CreateNamedCaptureAtIndex(state->capture_name(),
                                      capture_index CHECK_FAILED);
          }
219 220 221
          RegExpCapture* capture = GetCapture(capture_index);
          capture->set_body(body);
          body = capture;
222
        } else if (group_type == GROUPING) {
223
          body = zone()->New<RegExpGroup>(body);
224
        } else {
225 226 227
          DCHECK(group_type == POSITIVE_LOOKAROUND ||
                 group_type == NEGATIVE_LOOKAROUND);
          bool is_positive = (group_type == POSITIVE_LOOKAROUND);
228
          body = zone()->New<RegExpLookaround>(
229 230 231 232 233 234 235 236 237
              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);
238
        // For compatibility with JSC and ES3, we allow quantifiers after
239 240 241 242 243 244 245 246 247 248 249
        // lookaheads, and break in all cases.
        break;
      }
      case '|': {
        Advance();
        builder->NewAlternative();
        continue;
      }
      case '*':
      case '+':
      case '?':
250
        return ReportError(RegExpError::kNothingToRepeat);
251 252
      case '^': {
        Advance();
253
        if (builder->multiline()) {
254
          builder->AddAssertion(zone()->New<RegExpAssertion>(
255
              RegExpAssertion::START_OF_LINE, builder->flags()));
256
        } else {
257
          builder->AddAssertion(zone()->New<RegExpAssertion>(
258
              RegExpAssertion::START_OF_INPUT, builder->flags()));
259 260 261 262 263 264 265
          set_contains_anchor();
        }
        continue;
      }
      case '$': {
        Advance();
        RegExpAssertion::AssertionType assertion_type =
266 267 268
            builder->multiline() ? RegExpAssertion::END_OF_LINE
                                 : RegExpAssertion::END_OF_INPUT;
        builder->AddAssertion(
269
            zone()->New<RegExpAssertion>(assertion_type, builder->flags()));
270 271 272 273 274
        continue;
      }
      case '.': {
        Advance();
        ZoneList<CharacterRange>* ranges =
275
            zone()->New<ZoneList<CharacterRange>>(2, zone());
276

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

285
        RegExpCharacterClass* cc =
286
            zone()->New<RegExpCharacterClass>(zone(), ranges, builder->flags());
287
        builder->AddCharacterClass(cc);
288 289 290
        break;
      }
      case '(': {
291
        state = ParseOpenParenthesis(state CHECK_FAILED);
292 293 294 295
        builder = state->builder();
        continue;
      }
      case '[': {
296
        RegExpTree* cc = ParseCharacterClass(builder CHECK_FAILED);
297
        builder->AddCharacterClass(cc->AsCharacterClass());
298 299 300 301 302 303 304
        break;
      }
      // Atom ::
      //   \ AtomEscape
      case '\\':
        switch (Next()) {
          case kEndMarker:
305
            return ReportError(RegExpError::kEscapeAtEndOfPattern);
306 307
          case 'b':
            Advance(2);
308
            builder->AddAssertion(zone()->New<RegExpAssertion>(
309
                RegExpAssertion::BOUNDARY, builder->flags()));
310 311 312
            continue;
          case 'B':
            Advance(2);
313
            builder->AddAssertion(zone()->New<RegExpAssertion>(
314
                RegExpAssertion::NON_BOUNDARY, builder->flags()));
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
            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 =
330
                zone()->New<ZoneList<CharacterRange>>(2, zone());
331 332
            CharacterRange::AddClassEscape(
                c, ranges, unicode() && builder->ignore_case(), zone());
333 334
            RegExpCharacterClass* cc = zone()->New<RegExpCharacterClass>(
                zone(), ranges, builder->flags());
335
            builder->AddCharacterClass(cc);
336 337
            break;
          }
338 339 340 341 342
          case 'p':
          case 'P': {
            uc32 p = Next();
            Advance(2);
            if (unicode()) {
343
              ZoneList<CharacterRange>* ranges =
344
                  zone()->New<ZoneList<CharacterRange>>(2, zone());
345 346
              ZoneVector<char> name_1(zone());
              ZoneVector<char> name_2(zone());
347 348
              if (ParsePropertyClassName(&name_1, &name_2)) {
                if (AddPropertyClassRange(ranges, p == 'P', name_1, name_2)) {
349 350
                  RegExpCharacterClass* cc = zone()->New<RegExpCharacterClass>(
                      zone(), ranges, builder->flags());
351 352 353 354 355 356 357 358 359 360
                  builder->AddCharacterClass(cc);
                  break;
                }
                if (p == 'p' && name_2.empty()) {
                  RegExpTree* sequence = GetPropertySequence(name_1);
                  if (sequence != nullptr) {
                    builder->AddAtom(sequence);
                    break;
                  }
                }
361
              }
362
              return ReportError(RegExpError::kInvalidPropertyName);
363 364 365 366 367
            } else {
              builder->AddCharacter(p);
            }
            break;
          }
368 369 370 371 372 373 374 375 376 377
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
          case '6':
          case '7':
          case '8':
          case '9': {
            int index = 0;
378 379
            bool is_backref = ParseBackReferenceIndex(&index CHECK_FAILED);
            if (is_backref) {
380 381 382 383 384 385 386 387 388
              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);
389
                RegExpTree* atom =
390
                    zone()->New<RegExpBackReference>(capture, builder->flags());
391 392 393 394
                builder->AddAtom(atom);
              }
              break;
            }
395 396 397
            // With /u, no identity escapes except for syntax characters
            // are allowed. Otherwise, all identity escapes are allowed.
            if (unicode()) {
398
              return ReportError(RegExpError::kInvalidEscape);
399
            }
400 401
            uc32 first_digit = Next();
            if (first_digit == '8' || first_digit == '9') {
402 403
              builder->AddCharacter(first_digit);
              Advance(2);
404 405
              break;
            }
406
            V8_FALLTHROUGH;
407 408 409
          }
          case '0': {
            Advance();
410 411
            if (unicode() && Next() >= '0' && Next() <= '9') {
              // With /u, decimal escape with leading 0 are not parsed as octal.
412
              return ReportError(RegExpError::kInvalidDecimalEscape);
413
            }
414 415 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
            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'.
448 449 450
              // Read the backslash as a literal character instead of as
              // starting an escape.
              // ES#prod-annexB-ExtendedPatternCharacter
451 452
              if (unicode()) {
                // With /u, invalid escapes are not treated as identity escapes.
453
                return ReportError(RegExpError::kInvalidUnicodeEscape);
454
              }
455 456 457
              builder->AddCharacter('\\');
            } else {
              Advance(2);
458
              builder->AddCharacter(controlLetter & 0x1F);
459 460 461 462 463 464 465 466
            }
            break;
          }
          case 'x': {
            Advance(2);
            uc32 value;
            if (ParseHexEscape(2, &value)) {
              builder->AddCharacter(value);
467
            } else if (!unicode()) {
468 469
              builder->AddCharacter('x');
            } else {
470
              // With /u, invalid escapes are not treated as identity escapes.
471
              return ReportError(RegExpError::kInvalidEscape);
472 473 474 475 476 477 478
            }
            break;
          }
          case 'u': {
            Advance(2);
            uc32 value;
            if (ParseUnicodeEscape(&value)) {
479
              builder->AddEscapedUnicodeCharacter(value);
480
            } else if (!unicode()) {
481 482
              builder->AddCharacter('u');
            } else {
483
              // With /u, invalid escapes are not treated as identity escapes.
484
              return ReportError(RegExpError::kInvalidUnicodeEscape);
485 486 487
            }
            break;
          }
488
          case 'k':
489 490
            // Either an identity escape or a named back-reference.  The two
            // interpretations are mutually exclusive: '\k' is interpreted as
491
            // an identity escape for non-Unicode patterns without named
492 493
            // capture groups, and as the beginning of a named back-reference
            // in all other cases.
494
            if (unicode() || HasNamedCaptures()) {
495 496 497 498
              Advance(2);
              ParseNamedBackReference(builder, state CHECK_FAILED);
              break;
            }
499
            V8_FALLTHROUGH;
500 501
          default:
            Advance();
502 503 504
            // With /u, no identity escapes except for syntax characters
            // are allowed. Otherwise, all identity escapes are allowed.
            if (!unicode() || IsSyntaxCharacterOrSlash(current())) {
505 506 507
              builder->AddCharacter(current());
              Advance();
            } else {
508
              return ReportError(RegExpError::kInvalidEscape);
509 510 511 512 513 514
            }
            break;
        }
        break;
      case '{': {
        int dummy;
515
        bool parsed = ParseIntervalQuantifier(&dummy, &dummy CHECK_FAILED);
516
        if (parsed) return ReportError(RegExpError::kNothingToRepeat);
517
        V8_FALLTHROUGH;
518
      }
519 520 521
      case '}':
      case ']':
        if (unicode()) {
522
          return ReportError(RegExpError::kLoneQuantifierBrackets);
523
        }
524
        V8_FALLTHROUGH;
525
      default:
526
        builder->AddUnicodeCharacter(current());
527 528 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
        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) {
557
            return ReportError(RegExpError::kRangeOutOfOrder);
558 559
          }
          break;
560 561
        } else if (unicode()) {
          // With /u, incomplete quantifiers are not allowed.
562
          return ReportError(RegExpError::kIncompleteQuantifier);
563
        }
564
        continue;
565 566 567 568 569 570 571 572 573 574 575 576
      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();
    }
577
    if (!builder->AddQuantifierToAtom(min, max, quantifier_type)) {
578
      return ReportError(RegExpError::kInvalidQuantifier);
579
    }
580 581 582
  }
}

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
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': {
612
        if (!FLAG_regexp_mode_modifiers) {
613
          ReportError(RegExpError::kInvalidGroup);
614 615 616 617 618 619 620 621
          return nullptr;
        }
        Advance();
        bool flags_sense = true;  // Switching on flags.
        while (subexpr_type != GROUPING) {
          switch (current()) {
            case '-':
              if (!flags_sense) {
622
                ReportError(RegExpError::kMultipleFlagDashes);
623 624 625 626 627 628 629 630 631 632 633 634 635
                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) {
636
                ReportError(RegExpError::kRepeatedFlag);
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
                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:
664
              ReportError(RegExpError::kInvalidFlagGroup);
665 666 667 668 669 670 671
              return nullptr;
          }
        }
        break;
      }
      case '<':
        Advance();
672 673 674 675 676 677 678 679 680 681
        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;
682
        }
683 684 685 686
        is_named_capture = true;
        has_named_captures_ = true;
        Advance();
        break;
687
      default:
688
        ReportError(RegExpError::kInvalidGroup);
689 690 691 692
        return nullptr;
    }
  }
  if (subexpr_type == CAPTURE) {
693
    if (captures_started_ >= JSRegExp::kMaxCaptures) {
694
      ReportError(RegExpError::kTooManyCaptures);
695 696 697 698 699 700 701 702 703 704
      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.
705 706 707
  return zone()->New<RegExpParserState>(state, subexpr_type, lookaround_type,
                                        captures_started_, capture_name, flags,
                                        zone());
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

#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() {
735 736
  DCHECK(!is_scanned_for_captures_);
  const int saved_position = position();
737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759
  // 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 '(':
760 761 762 763 764 765 766 767 768 769 770
        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;

771 772
          Advance();
          if (current() == '=' || current() == '!') break;
773 774 775 776 777

          // 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;
778 779
        }
        capture_count++;
780 781 782 783 784
        break;
    }
  }
  capture_count_ = capture_count;
  is_scanned_for_captures_ = true;
785
  Reset(saved_position);
786 787 788 789 790 791 792 793 794 795 796 797 798 799 800
}


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');
801
      if (value > JSRegExp::kMaxCaptures) {
802 803 804 805 806 807 808 809 810
        Reset(start);
        return false;
      }
      Advance();
    } else {
      break;
    }
  }
  if (value > captures_started()) {
811
    if (!is_scanned_for_captures_) ScanForCaptures();
812 813 814 815 816 817 818 819 820
    if (value > capture_count_) {
      Reset(start);
      return false;
    }
  }
  *index_out = value;
  return true;
}

821 822 823 824 825 826 827 828 829 830
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() {
831
  ZoneVector<uc16>* name = zone()->New<ZoneVector<uc16>>(zone());
832 833 834 835

  bool at_start = true;
  while (true) {
    uc32 c = current();
836
    Advance();
837 838 839

    // Convert unicode escapes.
    if (c == '\\' && current() == 'u') {
840
      Advance();
841
      if (!ParseUnicodeEscape(&c)) {
842
        ReportError(RegExpError::kInvalidUnicodeEscape);
843 844 845 846
        return nullptr;
      }
    }

847 848
    // The backslash char is misclassified as both ID_Start and ID_Continue.
    if (c == '\\') {
849
      ReportError(RegExpError::kInvalidCaptureGroupName);
850 851 852
      return nullptr;
    }

853
    if (at_start) {
854
      if (!IsIdentifierStart(c)) {
855
        ReportError(RegExpError::kInvalidCaptureGroupName);
856 857 858 859 860 861 862
        return nullptr;
      }
      push_code_unit(name, c);
      at_start = false;
    } else {
      if (c == '>') {
        break;
863
      } else if (IsIdentifierPart(c)) {
864 865
        push_code_unit(name, c);
      } else {
866
        ReportError(RegExpError::kInvalidCaptureGroupName);
867 868 869 870 871 872 873 874 875 876 877 878 879
        return nullptr;
      }
    }
  }

  return name;
}

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

880 881 882 883 884
  RegExpCapture* capture = GetCapture(index);
  DCHECK_NULL(capture->name());

  capture->set_name(name);

885
  if (named_captures_ == nullptr) {
886 887
    named_captures_ =
        zone_->New<ZoneSet<RegExpCapture*, RegExpCaptureNameLess>>(zone());
888 889
  } else {
    // Check for duplicates and bail if we find any.
890 891 892

    const auto& named_capture_it = named_captures_->find(capture);
    if (named_capture_it != named_captures_->end()) {
893
      ReportError(RegExpError::kDuplicateCaptureGroupName);
894
      return false;
895 896 897
    }
  }

898
  named_captures_->emplace(capture);
899 900 901 902 903 904 905 906

  return true;
}

bool RegExpParser::ParseNamedBackReference(RegExpBuilder* builder,
                                           RegExpParserState* state) {
  // The parser is assumed to be on the '<' in \k<name>.
  if (current() != '<') {
907
    ReportError(RegExpError::kInvalidNamedReference);
908 909 910
    return false;
  }

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

  if (state->IsInsideCaptureGroup(name)) {
    builder->AddEmpty();
  } else {
920
    RegExpBackReference* atom =
921
        zone()->New<RegExpBackReference>(builder->flags());
922 923 924 925 926 927
    atom->set_name(name);

    builder->AddAtom(atom);

    if (named_back_references_ == nullptr) {
      named_back_references_ =
928
          zone()->New<ZoneList<RegExpBackReference*>>(1, zone());
929 930 931 932 933 934 935 936 937 938 939
    }
    named_back_references_->Add(atom, zone());
  }

  return true;
}

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

  if (named_captures_ == nullptr) {
940
    ReportError(RegExpError::kInvalidNamedCaptureReference);
941 942 943 944 945 946 947 948
    return;
  }

  // Look up and patch the actual capture for each named back reference.

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

949 950 951
    // Capture used to search the named_captures_ by name, index of the
    // capture is never used.
    static const int kInvalidIndex = 0;
952
    RegExpCapture* search_capture = zone()->New<RegExpCapture>(kInvalidIndex);
953 954
    DCHECK_NULL(search_capture->name());
    search_capture->set_name(ref->name());
955

956 957 958 959 960
    int index = -1;
    const auto& capture_it = named_captures_->find(search_capture);
    if (capture_it != named_captures_->end()) {
      index = (*capture_it)->index();
    } else {
961
      ReportError(RegExpError::kInvalidNamedCaptureReference);
962 963 964 965 966 967
      return;
    }

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

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);
975
  if (captures_ == nullptr) {
976
    captures_ = zone()->New<ZoneList<RegExpCapture*>>(know_captures, zone());
977 978
  }
  while (captures_->length() < know_captures) {
979
    captures_->Add(zone()->New<RegExpCapture>(captures_->length() + 1), zone());
980 981 982 983
  }
  return captures_->at(index - 1);
}

984 985 986 987 988 989 990 991 992 993 994 995
namespace {

struct RegExpCaptureIndexLess {
  bool operator()(const RegExpCapture* lhs, const RegExpCapture* rhs) const {
    DCHECK_NOT_NULL(lhs);
    DCHECK_NOT_NULL(rhs);
    return lhs->index() < rhs->index();
  }
};

}  // namespace

996
Handle<FixedArray> RegExpParser::CreateCaptureNameMap() {
997
  if (named_captures_ == nullptr || named_captures_->empty()) {
998
    return Handle<FixedArray>();
999
  }
1000

1001 1002 1003 1004 1005 1006 1007 1008 1009
  // Named captures are sorted by name (because the set is used to ensure
  // name uniqueness). But the capture name map must to be sorted by index.

  ZoneVector<RegExpCapture*> sorted_named_captures(
      named_captures_->begin(), named_captures_->end(), zone());
  std::sort(sorted_named_captures.begin(), sorted_named_captures.end(),
            RegExpCaptureIndexLess{});
  DCHECK_EQ(sorted_named_captures.size(), named_captures_->size());

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

1012
  int len = static_cast<int>(sorted_named_captures.size()) * 2;
1013 1014
  Handle<FixedArray> array = factory->NewFixedArray(len);

1015
  int i = 0;
1016
  for (const auto& capture : sorted_named_captures) {
1017 1018 1019 1020
    Vector<const uc16> capture_name(capture->name()->data(),
                                    capture->name()->size());
    // CSA code in ConstructNewResultFromMatchInfo requires these strings to be
    // internalized so they can be used as property names in the 'exec' results.
1021
    Handle<String> name = factory->InternalizeString(capture_name);
1022
    array->set(i * 2, *name);
1023
    array->set(i * 2 + 1, Smi::FromInt(capture->index()));
1024 1025

    i++;
1026
  }
1027
  DCHECK_EQ(i * 2, len);
1028 1029 1030

  return array;
}
1031

1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
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_;
}

1042
bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(int index) {
1043
  for (RegExpParserState* s = this; s != nullptr; s = s->previous_state()) {
1044 1045 1046 1047 1048 1049 1050 1051 1052
    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;
}

1053 1054 1055
bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(
    const ZoneVector<uc16>* name) {
  DCHECK_NOT_NULL(name);
1056
  for (RegExpParserState* s = this; s != nullptr; s = s->previous_state()) {
1057 1058 1059 1060 1061
    if (s->capture_name() == nullptr) continue;
    if (*s->capture_name() == *name) return true;
  }
  return false;
}
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 1106 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

// 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.
1134
  // ES#prod-annexB-LegacyOctalEscapeSequence
1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165
  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;
}

1166
// This parses RegExpUnicodeEscapeSequence as described in ECMA262.
1167 1168 1169 1170
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.
1171
  if (current() == '{' && unicode()) {
1172 1173
    int start = position();
    Advance();
1174
    if (ParseUnlimitedLengthHexNumber(0x10FFFF, value)) {
1175 1176 1177 1178 1179 1180 1181 1182 1183
      if (current() == '}') {
        Advance();
        return true;
      }
    }
    Reset(start);
    return false;
  }
  // \u but no {, or \u{...} escapes not allowed.
1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201
  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;
1202 1203
}

1204
#ifdef V8_INTL_SUPPORT
1205 1206 1207

namespace {

1208 1209
bool IsExactPropertyAlias(const char* property_name, UProperty property) {
  const char* short_name = u_getPropertyName(property, U_SHORT_PROPERTY_NAME);
1210 1211
  if (short_name != nullptr && strcmp(property_name, short_name) == 0)
    return true;
1212 1213 1214
  for (int i = 0;; i++) {
    const char* long_name = u_getPropertyName(
        property, static_cast<UPropertyNameChoice>(U_LONG_PROPERTY_NAME + i));
1215
    if (long_name == nullptr) break;
1216 1217 1218 1219 1220 1221 1222
    if (strcmp(property_name, long_name) == 0) return true;
  }
  return false;
}

bool IsExactPropertyValueAlias(const char* property_value_name,
                               UProperty property, int32_t property_value) {
1223 1224
  const char* short_name =
      u_getPropertyValueName(property, property_value, U_SHORT_PROPERTY_NAME);
1225
  if (short_name != nullptr && strcmp(property_value_name, short_name) == 0) {
1226 1227
    return true;
  }
1228 1229 1230 1231
  for (int i = 0;; i++) {
    const char* long_name = u_getPropertyValueName(
        property, property_value,
        static_cast<UPropertyNameChoice>(U_LONG_PROPERTY_NAME + i));
1232
    if (long_name == nullptr) break;
1233
    if (strcmp(property_value_name, long_name) == 0) return true;
1234 1235 1236 1237
  }
  return false;
}

1238 1239 1240
bool LookupPropertyValueName(UProperty property,
                             const char* property_value_name, bool negate,
                             ZoneList<CharacterRange>* result, Zone* zone) {
1241 1242 1243 1244 1245 1246
  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;
  }
1247
  int32_t property_value =
1248
      u_getPropertyValueEnum(property_for_lookup, property_value_name);
1249 1250
  if (property_value == UCHAR_INVALID_CODE) return false;

1251 1252
  // We require the property name to match exactly to one of the property value
  // aliases. However, u_getPropertyValueEnum uses loose matching.
1253
  if (!IsExactPropertyValueAlias(property_value_name, property_for_lookup,
1254
                                 property_value)) {
1255 1256 1257
    return false;
  }

1258
  UErrorCode ec = U_ZERO_ERROR;
1259 1260 1261
  icu::UnicodeSet set;
  set.applyIntPropertyValue(property, property_value, ec);
  bool success = ec == U_ZERO_ERROR && !set.isEmpty();
1262 1263

  if (success) {
1264 1265 1266 1267 1268 1269
    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);
1270 1271 1272 1273 1274
    }
  }
  return success;
}

1275 1276 1277 1278 1279
template <size_t N>
inline bool NameEquals(const char* name, const char (&literal)[N]) {
  return strncmp(name, literal, N + 1) == 0;
}

1280 1281 1282
bool LookupSpecialPropertyValueName(const char* name,
                                    ZoneList<CharacterRange>* result,
                                    bool negate, Zone* zone) {
1283
  if (NameEquals(name, "Any")) {
1284 1285 1286 1287 1288 1289
    if (negate) {
      // Leave the list of character ranges empty, since the negation of 'Any'
      // is the empty set.
    } else {
      result->Add(CharacterRange::Everything(), zone);
    }
1290 1291
  } else if (NameEquals(name, "ASCII")) {
    result->Add(negate ? CharacterRange::Range(0x80, String::kMaxCodePoint)
1292
                       : CharacterRange::Range(0x0, 0x7F),
1293 1294
                zone);
  } else if (NameEquals(name, "Assigned")) {
1295 1296
    return LookupPropertyValueName(UCHAR_GENERAL_CATEGORY, "Unassigned",
                                   !negate, result, zone);
1297 1298 1299 1300 1301 1302
  } else {
    return false;
  }
  return true;
}

Dan Elphick's avatar
Dan Elphick committed
1303
// Explicitly allowlist supported binary properties. The spec forbids supporting
1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326
// 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:
1327
    case UCHAR_EMOJI_COMPONENT:
1328 1329 1330
    case UCHAR_EMOJI_MODIFIER_BASE:
    case UCHAR_EMOJI_MODIFIER:
    case UCHAR_EMOJI_PRESENTATION:
Jungshik Shin's avatar
Jungshik Shin committed
1331
    case UCHAR_EXTENDED_PICTOGRAPHIC:
1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349
    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:
1350
    case UCHAR_REGIONAL_INDICATOR:
1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366
    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;
}

1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
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 == '_');
}

1380 1381
}  // anonymous namespace

1382 1383
bool RegExpParser::ParsePropertyClassName(ZoneVector<char>* name_1,
                                          ZoneVector<char>* name_2) {
1384 1385
  DCHECK(name_1->empty());
  DCHECK(name_2->empty());
1386 1387 1388 1389 1390 1391 1392 1393
  // 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.
1394
  if (current() == '{') {
1395 1396
    // Parse \p{[PropertyName=]PropertyNameValue}
    for (Advance(); current() != '}' && current() != '='; Advance()) {
1397
      if (!IsUnicodePropertyValueCharacter(current())) return false;
1398
      if (!has_next()) return false;
1399
      name_1->push_back(static_cast<char>(current()));
1400 1401 1402
    }
    if (current() == '=') {
      for (Advance(); current() != '}'; Advance()) {
1403
        if (!IsUnicodePropertyValueCharacter(current())) return false;
1404
        if (!has_next()) return false;
1405
        name_2->push_back(static_cast<char>(current()));
1406
      }
1407
      name_2->push_back(0);  // null-terminate string.
1408 1409
    }
  } else {
1410
    return false;
1411 1412
  }
  Advance();
1413
  name_1->push_back(0);  // null-terminate string.
1414

1415 1416 1417 1418
  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;
}
1419

1420 1421
bool RegExpParser::AddPropertyClassRange(ZoneList<CharacterRange>* add_to,
                                         bool negate,
1422 1423
                                         const ZoneVector<char>& name_1,
                                         const ZoneVector<char>& name_2) {
1424
  if (name_2.empty()) {
1425
    // First attempt to interpret as general category property value name.
1426
    const char* name = name_1.data();
1427
    if (LookupPropertyValueName(UCHAR_GENERAL_CATEGORY_MASK, name, negate,
1428
                                add_to, zone())) {
1429 1430 1431
      return true;
    }
    // Interpret "Any", "ASCII", and "Assigned".
1432
    if (LookupSpecialPropertyValueName(name, add_to, negate, zone())) {
1433 1434 1435 1436
      return true;
    }
    // Then attempt to interpret as binary property name with value name 'Y'.
    UProperty property = u_getPropertyEnum(name);
1437
    if (!IsSupportedBinaryProperty(property)) return false;
1438
    if (!IsExactPropertyAlias(name, property)) return false;
1439
    return LookupPropertyValueName(property, negate ? "N" : "Y", false, add_to,
1440
                                   zone());
1441 1442 1443
  } else {
    // Both property name and value name are specified. Attempt to interpret
    // the property name as enumerated property.
1444 1445
    const char* property_name = name_1.data();
    const char* value_name = name_2.data();
1446 1447
    UProperty property = u_getPropertyEnum(property_name);
    if (!IsExactPropertyAlias(property_name, property)) return false;
1448 1449 1450 1451 1452 1453 1454
    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;
    }
1455
    return LookupPropertyValueName(property, value_name, negate, add_to,
1456
                                   zone());
1457
  }
1458 1459
}

1460
RegExpTree* RegExpParser::GetPropertySequence(const ZoneVector<char>& name_1) {
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
  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 =
1493
        zone()->New<ZoneList<CharacterRange>>(2, zone());
1494 1495 1496 1497
    prefix_ranges->Add(CharacterRange::Range('0', '9'), zone());
    prefix_ranges->Add(CharacterRange::Singleton('#'), zone());
    prefix_ranges->Add(CharacterRange::Singleton('*'), zone());
    builder.AddCharacterClass(
1498
        zone()->New<RegExpCharacterClass>(zone(), prefix_ranges, flags));
1499 1500 1501 1502 1503 1504 1505 1506
    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 =
1507
        zone()->New<ZoneList<CharacterRange>>(2, zone());
1508 1509 1510
    LookupPropertyValueName(UCHAR_EMOJI_MODIFIER_BASE, "Y", false,
                            modifier_base_ranges, zone());
    builder.AddCharacterClass(
1511
        zone()->New<RegExpCharacterClass>(zone(), modifier_base_ranges, flags));
1512
    ZoneList<CharacterRange>* modifier_ranges =
1513
        zone()->New<ZoneList<CharacterRange>>(2, zone());
1514 1515 1516
    LookupPropertyValueName(UCHAR_EMOJI_MODIFIER, "Y", false, modifier_ranges,
                            zone());
    builder.AddCharacterClass(
1517
        zone()->New<RegExpCharacterClass>(zone(), modifier_ranges, flags));
1518 1519 1520 1521 1522 1523
    return builder.ToRegExp();
  }

  return nullptr;
}

1524
#else  // V8_INTL_SUPPORT
1525

1526 1527
bool RegExpParser::ParsePropertyClassName(ZoneVector<char>* name_1,
                                          ZoneVector<char>* name_2) {
1528
  return false;
1529
}
1530

1531 1532
bool RegExpParser::AddPropertyClassRange(ZoneList<CharacterRange>* add_to,
                                         bool negate,
1533 1534
                                         const ZoneVector<char>& name_1,
                                         const ZoneVector<char>& name_2) {
1535 1536 1537
  return false;
}

1538
RegExpTree* RegExpParser::GetPropertySequence(const ZoneVector<char>& name) {
1539 1540 1541
  return nullptr;
}

1542
#endif  // V8_INTL_SUPPORT
1543

1544 1545 1546 1547 1548 1549 1550 1551
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;
1552
    if (x > static_cast<uc32>(max_value)) {
1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563
      return false;
    }
    Advance();
    d = HexValue(current());
  }
  *value = x;
  return true;
}


uc32 RegExpParser::ParseClassCharacterEscape() {
1564
  DCHECK_EQ('\\', current());
1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590
  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');
1591 1592 1593
      // Inside a character class, we also accept digits and underscore as
      // control characters, unless with /u. See Annex B:
      // ES#prod-annexB-ClassControlLetter
1594
      if (letter >= 'A' && letter <= 'Z') {
1595 1596
        Advance(2);
        // Control letters mapped to ASCII control characters in the range
1597 1598
        // 0x00-0x1F.
        return controlLetter & 0x1F;
1599
      }
1600 1601
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
1602
        ReportError(RegExpError::kInvalidClassEscape);
1603 1604 1605 1606 1607
        return 0;
      }
      if ((controlLetter >= '0' && controlLetter <= '9') ||
          controlLetter == '_') {
        Advance(2);
1608
        return controlLetter & 0x1F;
1609
      }
1610 1611
      // We match JSC in reading the backslash as a literal
      // character instead of as starting an escape.
1612
      // TODO(v8:6201): Not yet covered by the spec.
1613 1614 1615
      return '\\';
    }
    case '0':
1616 1617 1618 1619 1620
      // With /u, \0 is interpreted as NUL if not followed by another digit.
      if (unicode() && !(Next() >= '0' && Next() <= '9')) {
        Advance();
        return 0;
      }
1621
      V8_FALLTHROUGH;
1622 1623 1624 1625 1626 1627 1628 1629 1630 1631
    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.
1632
      // ES#prod-annexB-LegacyOctalEscapeSequence
1633 1634
      if (unicode()) {
        // With /u, decimal escape is not interpreted as octal character code.
1635
        ReportError(RegExpError::kInvalidClassEscape);
1636 1637
        return 0;
      }
1638 1639 1640 1641
      return ParseOctalLiteral();
    case 'x': {
      Advance();
      uc32 value;
1642 1643 1644
      if (ParseHexEscape(2, &value)) return value;
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
1645
        ReportError(RegExpError::kInvalidEscape);
1646
        return 0;
1647
      }
1648 1649 1650
      // If \x is not followed by a two-digit hexadecimal, treat it
      // as an identity escape.
      return 'x';
1651 1652 1653 1654
    }
    case 'u': {
      Advance();
      uc32 value;
1655 1656 1657
      if (ParseUnicodeEscape(&value)) return value;
      if (unicode()) {
        // With /u, invalid escapes are not treated as identity escapes.
1658
        ReportError(RegExpError::kInvalidUnicodeEscape);
1659
        return 0;
1660
      }
1661 1662 1663
      // If \u is not followed by a two-digit hexadecimal, treat it
      // as an identity escape.
      return 'u';
1664 1665 1666
    }
    default: {
      uc32 result = current();
1667
      // With /u, no identity escapes except for syntax characters and '-' are
1668
      // allowed. Otherwise, all identity escapes are allowed.
1669
      if (!unicode() || IsSyntaxCharacterOrSlash(result) || result == '-') {
1670 1671 1672
        Advance();
        return result;
      }
1673
      ReportError(RegExpError::kInvalidEscape);
1674 1675 1676
      return 0;
    }
  }
1677
  UNREACHABLE();
1678 1679
}

1680 1681 1682 1683 1684 1685
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 == '\\') {
1686 1687 1688 1689 1690 1691 1692
    switch (Next()) {
      case 'w':
      case 'W':
      case 'd':
      case 'D':
      case 's':
      case 'S': {
1693 1694
        CharacterRange::AddClassEscape(static_cast<char>(Next()), ranges,
                                       add_unicode_case_equivalents, zone);
1695
        Advance(2);
1696 1697
        *is_class_escape = true;
        return;
1698 1699
      }
      case kEndMarker:
1700
        ReportError(RegExpError::kEscapeAtEndOfPattern);
1701 1702 1703
        return;
      case 'p':
      case 'P':
1704
        if (unicode()) {
1705 1706
          bool negate = Next() == 'P';
          Advance(2);
1707 1708
          ZoneVector<char> name_1(zone);
          ZoneVector<char> name_2(zone);
1709 1710
          if (!ParsePropertyClassName(&name_1, &name_2) ||
              !AddPropertyClassRange(ranges, negate, name_1, name_2)) {
1711
            ReportError(RegExpError::kInvalidClassPropertyName);
1712 1713 1714 1715 1716
          }
          *is_class_escape = true;
          return;
        }
        break;
1717
      default:
1718
        break;
1719
    }
1720 1721
    *char_out = ParseClassCharacterEscape();
    *is_class_escape = false;
1722 1723
  } else {
    Advance();
1724 1725
    *char_out = current_char;
    *is_class_escape = false;
1726
  }
1727
}
1728

1729
RegExpTree* RegExpParser::ParseCharacterClass(const RegExpBuilder* builder) {
1730 1731 1732 1733 1734 1735 1736 1737
  DCHECK_EQ(current(), '[');
  Advance();
  bool is_negated = false;
  if (current() == '^') {
    is_negated = true;
    Advance();
  }
  ZoneList<CharacterRange>* ranges =
1738
      zone()->New<ZoneList<CharacterRange>>(2, zone());
1739
  bool add_unicode_case_equivalents = unicode() && builder->ignore_case();
1740
  while (has_more() && current() != ']') {
1741 1742 1743 1744
    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);
1745 1746 1747 1748 1749 1750 1751
    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() == ']') {
1752
        if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1753 1754 1755
        ranges->Add(CharacterRange::Singleton('-'), zone());
        break;
      }
1756 1757 1758
      ParseClassEscape(ranges, zone(), add_unicode_case_equivalents, &char_2,
                       &is_class_2 CHECK_FAILED);
      if (is_class_1 || is_class_2) {
1759
        // Either end is an escaped character class. Treat the '-' verbatim.
1760 1761
        if (unicode()) {
          // ES2015 21.2.2.15.1 step 1.
1762
          return ReportError(RegExpError::kInvalidCharacterClass);
1763
        }
1764
        if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1765
        ranges->Add(CharacterRange::Singleton('-'), zone());
1766
        if (!is_class_2) ranges->Add(CharacterRange::Singleton(char_2), zone());
1767 1768
        continue;
      }
1769
      // ES2015 21.2.2.15.1 step 6.
1770
      if (char_1 > char_2) {
1771
        return ReportError(RegExpError::kOutOfOrderCharacterClass);
1772
      }
1773
      ranges->Add(CharacterRange::Range(char_1, char_2), zone());
1774
    } else {
1775
      if (!is_class_1) ranges->Add(CharacterRange::Singleton(char_1), zone());
1776 1777 1778
    }
  }
  if (!has_more()) {
1779
    return ReportError(RegExpError::kUnterminatedCharacterClass);
1780 1781
  }
  Advance();
1782 1783
  RegExpCharacterClass::CharacterClassFlags character_class_flags;
  if (is_negated) character_class_flags = RegExpCharacterClass::NEGATED;
1784
  return zone()->New<RegExpCharacterClass>(zone(), ranges, builder->flags(),
1785
                                           character_class_flags);
1786 1787 1788 1789 1790
}


#undef CHECK_FAILED

1791 1792
bool RegExpParser::Parse(RegExpCompileData* result,
                         const DisallowHeapAllocation&) {
1793
  DCHECK(result != nullptr);
1794 1795
  RegExpTree* tree = ParsePattern();
  if (failed()) {
1796
    DCHECK(tree == nullptr);
1797 1798 1799
    DCHECK(error_ != RegExpError::kNone);
    result->error = error_;
    result->error_pos = error_pos_;
1800
  } else {
1801
    DCHECK(tree != nullptr);
1802
    DCHECK(error_ == RegExpError::kNone);
1803
    if (FLAG_trace_regexp_parser) {
1804
      StdoutStream os;
1805
      tree->Print(os, zone());
1806 1807
      os << "\n";
    }
1808
    result->tree = tree;
1809 1810 1811
    int capture_count = captures_started();
    result->simple = tree->IsAtom() && simple() && capture_count == 0;
    result->contains_anchor = contains_anchor();
1812 1813
    result->capture_count = capture_count;
  }
1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834
  return !failed();
}

bool RegExpParser::ParseRegExp(Isolate* isolate, Zone* zone,
                               FlatStringReader* input, JSRegExp::Flags flags,
                               RegExpCompileData* result) {
  RegExpParser parser(input, flags, isolate, zone);
  bool success;
  {
    DisallowHeapAllocation no_gc;
    success = parser.Parse(result, no_gc);
  }
  if (success) {
    result->capture_name_map = parser.CreateCaptureNameMap();
  }
  return success;
}

bool RegExpParser::VerifyRegExpSyntax(Isolate* isolate, Zone* zone,
                                      FlatStringReader* input,
                                      JSRegExp::Flags flags,
1835
                                      RegExpCompileData* result,
1836 1837
                                      const DisallowHeapAllocation& no_gc) {
  RegExpParser parser(input, flags, isolate, zone);
1838
  return parser.Parse(result, no_gc);
1839 1840
}

1841
RegExpBuilder::RegExpBuilder(Zone* zone, JSRegExp::Flags flags)
1842 1843
    : zone_(zone),
      pending_empty_(false),
1844
      flags_(flags),
1845
      characters_(nullptr),
1846
      pending_surrogate_(kNoPendingSurrogate),
1847 1848 1849 1850 1851 1852 1853 1854 1855 1856
      terms_(),
      alternatives_()
#ifdef DEBUG
      ,
      last_added_(ADD_NONE)
#endif
{
}


1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869
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;
1870 1871 1872 1873
    DCHECK(unibrow::Utf16::IsLeadSurrogate(lead_surrogate));
    uc32 combined =
        unibrow::Utf16::CombineSurrogatePair(lead_surrogate, trail_surrogate);
    if (NeedsDesugaringForIgnoreCase(combined)) {
1874
      AddCharacterClassForDesugaring(combined);
1875 1876 1877 1878 1879
    } else {
      ZoneList<uc16> surrogate_pair(2, zone());
      surrogate_pair.Add(lead_surrogate, zone());
      surrogate_pair.Add(trail_surrogate, zone());
      RegExpAtom* atom =
1880
          zone()->New<RegExpAtom>(surrogate_pair.ToConstVector(), flags_);
1881 1882
      AddAtom(atom);
    }
1883 1884 1885 1886 1887 1888 1889 1890 1891 1892
  } else {
    pending_surrogate_ = trail_surrogate;
    FlushPendingSurrogate();
  }
}


void RegExpBuilder::FlushPendingSurrogate() {
  if (pending_surrogate_ != kNoPendingSurrogate) {
    DCHECK(unicode());
1893 1894
    uc32 c = pending_surrogate_;
    pending_surrogate_ = kNoPendingSurrogate;
1895
    AddCharacterClassForDesugaring(c);
1896 1897 1898 1899
  }
}


1900
void RegExpBuilder::FlushCharacters() {
1901
  FlushPendingSurrogate();
1902
  pending_empty_ = false;
1903
  if (characters_ != nullptr) {
1904
    RegExpTree* atom =
1905
        zone()->New<RegExpAtom>(characters_->ToConstVector(), flags_);
1906
    characters_ = nullptr;
1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920
    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 {
1921
    RegExpText* text = zone()->New<RegExpText>(zone());
1922 1923 1924 1925 1926 1927 1928 1929
    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) {
1930
  FlushPendingSurrogate();
1931
  pending_empty_ = false;
1932
  if (NeedsDesugaringForIgnoreCase(c)) {
1933
    AddCharacterClassForDesugaring(c);
1934
  } else {
1935
    if (characters_ == nullptr) {
1936
      characters_ = zone()->New<ZoneList<uc16>>(4, zone());
1937 1938 1939
    }
    characters_->Add(c, zone());
    LAST(ADD_CHAR);
1940 1941 1942 1943
  }
}


1944
void RegExpBuilder::AddUnicodeCharacter(uc32 c) {
1945
  if (c > static_cast<uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
1946 1947 1948 1949 1950 1951 1952
    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);
1953 1954 1955 1956 1957
  } else {
    AddCharacter(static_cast<uc16>(c));
  }
}

1958 1959 1960 1961 1962 1963 1964
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();
}
1965

1966 1967 1968
void RegExpBuilder::AddEmpty() { pending_empty_ = true; }


1969
void RegExpBuilder::AddCharacterClass(RegExpCharacterClass* cc) {
1970
  if (NeedsDesugaringForUnicode(cc)) {
1971
    // With /u, character class needs to be desugared, so it
1972 1973 1974 1975 1976 1977 1978
    // must be a standalone term instead of being part of a RegExpText.
    AddTerm(cc);
  } else {
    AddAtom(cc);
  }
}

1979
void RegExpBuilder::AddCharacterClassForDesugaring(uc32 c) {
1980
  AddTerm(zone()->New<RegExpCharacterClass>(
1981 1982
      zone(), CharacterRange::List(zone(), CharacterRange::Singleton(c)),
      flags_));
1983 1984 1985
}


1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001
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);
}


2002 2003 2004 2005 2006 2007 2008
void RegExpBuilder::AddTerm(RegExpTree* term) {
  FlushText();
  terms_.Add(term, zone());
  LAST(ADD_ATOM);
}


2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023
void RegExpBuilder::AddAssertion(RegExpTree* assert) {
  FlushText();
  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) {
2024
    alternative = zone()->New<RegExpEmpty>();
2025 2026 2027
  } else if (num_terms == 1) {
    alternative = terms_.last();
  } else {
2028
    alternative = zone()->New<RegExpAlternative>(terms_.GetList(zone()));
2029 2030 2031 2032 2033 2034 2035
  }
  alternatives_.Add(alternative, zone());
  terms_.Clear();
  LAST(ADD_NONE);
}


2036 2037
bool RegExpBuilder::NeedsDesugaringForUnicode(RegExpCharacterClass* cc) {
  if (!unicode()) return false;
2038 2039 2040 2041
  // 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;
2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056
  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) {
2057
#ifdef V8_INTL_SUPPORT
2058
  if (unicode() && ignore_case()) {
2059 2060 2061 2062
    icu::UnicodeSet set(c, c);
    set.closeOver(USET_CASE_INSENSITIVE);
    set.removeAllStrings();
    return set.size() > 1;
2063 2064 2065
  }
  // In the case where ICU is not included, we act as if the unicode flag is
  // not set, and do not desugar.
2066
#endif  // V8_INTL_SUPPORT
2067 2068 2069 2070
  return false;
}


2071 2072 2073
RegExpTree* RegExpBuilder::ToRegExp() {
  FlushTerms();
  int num_alternatives = alternatives_.length();
2074
  if (num_alternatives == 0) return zone()->New<RegExpEmpty>();
2075
  if (num_alternatives == 1) return alternatives_.last();
2076
  return zone()->New<RegExpDisjunction>(alternatives_.GetList(zone()));
2077 2078
}

2079
bool RegExpBuilder::AddQuantifierToAtom(
2080
    int min, int max, RegExpQuantifier::QuantifierType quantifier_type) {
2081
  FlushPendingSurrogate();
2082 2083
  if (pending_empty_) {
    pending_empty_ = false;
2084
    return true;
2085 2086
  }
  RegExpTree* atom;
2087
  if (characters_ != nullptr) {
2088 2089 2090 2091 2092 2093
    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);
2094
      text_.Add(zone()->New<RegExpAtom>(prefix, flags_), zone());
2095 2096
      char_vector = char_vector.SubVector(num_chars - 1, num_chars);
    }
2097
    characters_ = nullptr;
2098
    atom = zone()->New<RegExpAtom>(char_vector, flags_);
2099 2100 2101 2102 2103 2104 2105 2106
    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();
2107 2108 2109 2110 2111 2112 2113 2114
    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;
      }
    }
2115 2116 2117 2118
    if (atom->max_match() == 0) {
      // Guaranteed to only match an empty string.
      LAST(ADD_TERM);
      if (min == 0) {
2119
        return true;
2120 2121
      }
      terms_.Add(atom, zone());
2122
      return true;
2123 2124 2125 2126 2127
    }
  } else {
    // Only call immediately after adding an atom or character!
    UNREACHABLE();
  }
2128
  terms_.Add(zone()->New<RegExpQuantifier>(min, max, quantifier_type, atom),
2129 2130
             zone());
  LAST(ADD_TERM);
2131
  return true;
2132 2133 2134 2135
}

}  // namespace internal
}  // namespace v8