runtime-regexp.cc 67.6 KB
Newer Older
1 2 3 4
// Copyright 2014 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.

5 6
#include <functional>

7
#include "src/common/message-template.h"
8 9
#include "src/execution/arguments-inl.h"
#include "src/execution/isolate-inl.h"
10
#include "src/heap/heap-inl.h"  // For ToBoolean. TODO(jkummerow): Drop.
11
#include "src/logging/counters.h"
12
#include "src/numbers/conversions-inl.h"
13
#include "src/objects/js-array-inl.h"
14
#include "src/objects/js-regexp-inl.h"
15
#include "src/regexp/regexp-utils.h"
16
#include "src/regexp/regexp.h"
17
#include "src/runtime/runtime-utils.h"
18 19
#include "src/strings/string-builder-inl.h"
#include "src/strings/string-search.h"
20
#include "src/zone/zone-chunk-list.h"
21 22 23 24

namespace v8 {
namespace internal {

25 26
namespace {

27 28 29 30 31 32 33 34 35 36 37 38 39 40
// Returns -1 for failure.
uint32_t GetArgcForReplaceCallable(uint32_t num_captures,
                                   bool has_named_captures) {
  const uint32_t kAdditionalArgsWithoutNamedCaptures = 2;
  const uint32_t kAdditionalArgsWithNamedCaptures = 3;
  if (num_captures > Code::kMaxArguments) return -1;
  uint32_t argc = has_named_captures
                      ? num_captures + kAdditionalArgsWithNamedCaptures
                      : num_captures + kAdditionalArgsWithoutNamedCaptures;
  STATIC_ASSERT(Code::kMaxArguments < std::numeric_limits<uint32_t>::max() -
                                          kAdditionalArgsWithNamedCaptures);
  return (argc > Code::kMaxArguments) ? -1 : argc;
}

41 42
// Looks up the capture of the given name. Returns the (1-based) numbered
// capture index or -1 on failure.
43
int LookupNamedCapture(const std::function<bool(String)>& name_matches,
44
                       FixedArray capture_name_map) {
45 46 47 48
  // TODO(jgruber): Sort capture_name_map and do binary search via
  // internalized strings.

  int maybe_capture_index = -1;
49
  const int named_capture_count = capture_name_map.length() >> 1;
50 51 52 53 54 55
  for (int j = 0; j < named_capture_count; j++) {
    // The format of {capture_name_map} is documented at
    // JSRegExp::kIrregexpCaptureNameMapIndex.
    const int name_ix = j * 2;
    const int index_ix = j * 2 + 1;

56
    String capture_name = String::cast(capture_name_map.get(name_ix));
57 58
    if (!name_matches(capture_name)) continue;

59
    maybe_capture_index = Smi::ToInt(capture_name_map.get(index_ix));
60 61 62 63 64 65 66 67
    break;
  }

  return maybe_capture_index;
}

}  // namespace

68 69 70
class CompiledReplacement {
 public:
  explicit CompiledReplacement(Zone* zone)
71
      : parts_(zone), replacement_substrings_(zone) {}
72

73
  // Return whether the replacement is simple.
74 75 76
  bool Compile(Isolate* isolate, Handle<JSRegExp> regexp,
               Handle<String> replacement, int capture_count,
               int subject_length);
77 78 79 80 81 82

  // Use Apply only if Compile returned false.
  void Apply(ReplacementStringBuilder* builder, int match_from, int match_to,
             int32_t* match);

  // Number of distinct parts of the replacement pattern.
83
  int parts() { return static_cast<int>(parts_.size()); }
84 85 86 87 88 89 90 91

 private:
  enum PartType {
    SUBJECT_PREFIX = 1,
    SUBJECT_SUFFIX,
    SUBJECT_CAPTURE,
    REPLACEMENT_SUBSTRING,
    REPLACEMENT_STRING,
92
    EMPTY_REPLACEMENT,
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    NUMBER_OF_PART_TYPES
  };

  struct ReplacementPart {
    static inline ReplacementPart SubjectMatch() {
      return ReplacementPart(SUBJECT_CAPTURE, 0);
    }
    static inline ReplacementPart SubjectCapture(int capture_index) {
      return ReplacementPart(SUBJECT_CAPTURE, capture_index);
    }
    static inline ReplacementPart SubjectPrefix() {
      return ReplacementPart(SUBJECT_PREFIX, 0);
    }
    static inline ReplacementPart SubjectSuffix(int subject_length) {
      return ReplacementPart(SUBJECT_SUFFIX, subject_length);
    }
    static inline ReplacementPart ReplacementString() {
      return ReplacementPart(REPLACEMENT_STRING, 0);
    }
112 113 114
    static inline ReplacementPart EmptyReplacement() {
      return ReplacementPart(EMPTY_REPLACEMENT, 0);
    }
115
    static inline ReplacementPart ReplacementSubString(int from, int to) {
116 117
      DCHECK_LE(0, from);
      DCHECK_GT(to, from);
118 119 120 121 122 123 124 125 126 127 128 129 130 131
      return ReplacementPart(-from, to);
    }

    // If tag <= 0 then it is the negation of a start index of a substring of
    // the replacement pattern, otherwise it's a value from PartType.
    ReplacementPart(int tag, int data) : tag(tag), data(data) {
      // Must be non-positive or a PartType value.
      DCHECK(tag < NUMBER_OF_PART_TYPES);
    }
    // Either a value of PartType or a non-positive number that is
    // the negation of an index into the replacement string.
    int tag;
    // The data value's interpretation depends on the value of tag:
    // tag == SUBJECT_PREFIX ||
132
    // tag == SUBJECT_SUFFIX:  data is unused.
133 134 135 136
    // tag == SUBJECT_CAPTURE: data is the number of the capture.
    // tag == REPLACEMENT_SUBSTRING ||
    // tag == REPLACEMENT_STRING:    data is index into array of substrings
    //                               of the replacement string.
137
    // tag == EMPTY_REPLACEMENT: data is unused.
138 139 140 141 142 143 144 145
    // tag <= 0: Temporary representation of the substring of the replacement
    //           string ranging over -tag .. data.
    //           Is replaced by REPLACEMENT_{SUB,}STRING when we create the
    //           substring objects.
    int data;
  };

  template <typename Char>
146
  bool ParseReplacementPattern(ZoneChunkList<ReplacementPart>* parts,
147
                               Vector<Char> characters,
148
                               FixedArray capture_name_map, int capture_count,
149
                               int subject_length) {
150 151 152
    // Equivalent to String::GetSubstitution, except that this method converts
    // the replacement string into an internal representation that avoids
    // repeated parsing when used repeatedly.
153 154 155 156 157 158 159 160 161 162 163 164 165 166
    int length = characters.length();
    int last = 0;
    for (int i = 0; i < length; i++) {
      Char c = characters[i];
      if (c == '$') {
        int next_index = i + 1;
        if (next_index == length) {  // No next character!
          break;
        }
        Char c2 = characters[next_index];
        switch (c2) {
          case '$':
            if (i > last) {
              // There is a substring before. Include the first "$".
167 168
              parts->push_back(
                  ReplacementPart::ReplacementSubString(last, next_index));
169 170 171 172 173 174 175 176 177
              last = next_index + 1;  // Continue after the second "$".
            } else {
              // Let the next substring start with the second "$".
              last = next_index;
            }
            i = next_index;
            break;
          case '`':
            if (i > last) {
178
              parts->push_back(ReplacementPart::ReplacementSubString(last, i));
179
            }
180
            parts->push_back(ReplacementPart::SubjectPrefix());
181 182 183 184 185
            i = next_index;
            last = i + 1;
            break;
          case '\'':
            if (i > last) {
186
              parts->push_back(ReplacementPart::ReplacementSubString(last, i));
187
            }
188
            parts->push_back(ReplacementPart::SubjectSuffix(subject_length));
189 190 191 192 193
            i = next_index;
            last = i + 1;
            break;
          case '&':
            if (i > last) {
194
              parts->push_back(ReplacementPart::ReplacementSubString(last, i));
195
            }
196
            parts->push_back(ReplacementPart::SubjectMatch());
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
            i = next_index;
            last = i + 1;
            break;
          case '0':
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
          case '6':
          case '7':
          case '8':
          case '9': {
            int capture_ref = c2 - '0';
            if (capture_ref > capture_count) {
              i = next_index;
              continue;
            }
            int second_digit_index = next_index + 1;
            if (second_digit_index < length) {
              // Peek ahead to see if we have two digits.
              Char c3 = characters[second_digit_index];
              if ('0' <= c3 && c3 <= '9') {  // Double digits.
                int double_digit_ref = capture_ref * 10 + c3 - '0';
                if (double_digit_ref <= capture_count) {
                  next_index = second_digit_index;
                  capture_ref = double_digit_ref;
                }
              }
            }
            if (capture_ref > 0) {
              if (i > last) {
229 230
                parts->push_back(
                    ReplacementPart::ReplacementSubString(last, i));
231 232
              }
              DCHECK(capture_ref <= capture_count);
233
              parts->push_back(ReplacementPart::SubjectCapture(capture_ref));
234 235 236 237 238
              last = next_index + 1;
            }
            i = next_index;
            break;
          }
239
          case '<': {
240
            if (capture_name_map.is_null()) {
241 242 243 244
              i = next_index;
              break;
            }

245 246
            // Scan until the next '>', and let the enclosed substring be the
            // groupName.
247 248 249 250 251 252 253 254 255 256

            const int name_start_index = next_index + 1;
            int closing_bracket_index = -1;
            for (int j = name_start_index; j < length; j++) {
              if (characters[j] == '>') {
                closing_bracket_index = j;
                break;
              }
            }

257 258 259 260 261 262
            // If no closing bracket is found, '$<' is treated as a string
            // literal.
            if (closing_bracket_index == -1) {
              i = next_index;
              break;
            }
263 264 265 266 267 268

            Vector<Char> requested_name =
                characters.SubVector(name_start_index, closing_bracket_index);

            // Let capture be ? Get(namedCaptures, groupName).

269
            const int capture_index = LookupNamedCapture(
270
                [=](String capture_name) {
271
                  return capture_name.IsEqualTo(requested_name);
272 273 274
                },
                capture_name_map);

275 276
            // If capture is undefined or does not exist, replace the text
            // through the following '>' with the empty string.
277 278 279
            // Otherwise, replace the text through the following '>' with
            // ? ToString(capture).

280 281
            DCHECK(capture_index == -1 ||
                   (1 <= capture_index && capture_index <= capture_count));
282 283

            if (i > last) {
284
              parts->push_back(ReplacementPart::ReplacementSubString(last, i));
285
            }
286 287 288 289
            parts->push_back(
                (capture_index == -1)
                    ? ReplacementPart::EmptyReplacement()
                    : ReplacementPart::SubjectCapture(capture_index));
290 291 292 293
            last = closing_bracket_index + 1;
            i = closing_bracket_index;
            break;
          }
294 295 296 297 298 299 300 301 302
          default:
            i = next_index;
            break;
        }
      }
    }
    if (length > last) {
      if (last == 0) {
        // Replacement is simple.  Do not use Apply to do the replacement.
303
        return true;
304
      } else {
305
        parts->push_back(ReplacementPart::ReplacementSubString(last, length));
306 307
      }
    }
308
    return false;
309 310
  }

311 312
  ZoneChunkList<ReplacementPart> parts_;
  ZoneVector<Handle<String>> replacement_substrings_;
313 314
};

315
bool CompiledReplacement::Compile(Isolate* isolate, Handle<JSRegExp> regexp,
316 317
                                  Handle<String> replacement, int capture_count,
                                  int subject_length) {
318 319
  {
    DisallowHeapAllocation no_gc;
320
    String::FlatContent content = replacement->GetFlatContent(no_gc);
321
    DCHECK(content.IsFlat());
322

323
    FixedArray capture_name_map;
324 325
    if (capture_count > 0) {
      DCHECK_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
326
      Object maybe_capture_name_map = regexp->CaptureNameMap();
327
      if (maybe_capture_name_map.IsFixedArray()) {
328 329 330 331
        capture_name_map = FixedArray::cast(maybe_capture_name_map);
      }
    }

332
    bool simple;
333 334
    if (content.IsOneByte()) {
      simple = ParseReplacementPattern(&parts_, content.ToOneByteVector(),
335
                                       capture_name_map, capture_count,
336
                                       subject_length);
337 338 339
    } else {
      DCHECK(content.IsTwoByte());
      simple = ParseReplacementPattern(&parts_, content.ToUC16Vector(),
340
                                       capture_name_map, capture_count,
341
                                       subject_length);
342
    }
343
    if (simple) return true;
344 345 346 347
  }

  // Find substrings of replacement string and create them as String objects.
  int substring_index = 0;
348 349
  for (ReplacementPart& part : parts_) {
    int tag = part.tag;
350 351
    if (tag <= 0) {  // A replacement string slice.
      int from = -tag;
352 353 354 355 356
      int to = part.data;
      replacement_substrings_.push_back(
          isolate->factory()->NewSubString(replacement, from, to));
      part.tag = REPLACEMENT_SUBSTRING;
      part.data = substring_index;
357 358
      substring_index++;
    } else if (tag == REPLACEMENT_STRING) {
359 360
      replacement_substrings_.push_back(replacement);
      part.data = substring_index;
361 362 363
      substring_index++;
    }
  }
364
  return false;
365 366 367 368 369
}


void CompiledReplacement::Apply(ReplacementStringBuilder* builder,
                                int match_from, int match_to, int32_t* match) {
370 371
  DCHECK_LT(0, parts_.size());
  for (ReplacementPart& part : parts_) {
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
    switch (part.tag) {
      case SUBJECT_PREFIX:
        if (match_from > 0) builder->AddSubjectSlice(0, match_from);
        break;
      case SUBJECT_SUFFIX: {
        int subject_length = part.data;
        if (match_to < subject_length) {
          builder->AddSubjectSlice(match_to, subject_length);
        }
        break;
      }
      case SUBJECT_CAPTURE: {
        int capture = part.data;
        int from = match[capture * 2];
        int to = match[capture * 2 + 1];
        if (from >= 0 && to > from) {
          builder->AddSubjectSlice(from, to);
        }
        break;
      }
      case REPLACEMENT_SUBSTRING:
      case REPLACEMENT_STRING:
        builder->AddString(replacement_substrings_[part.data]);
        break;
396 397
      case EMPTY_REPLACEMENT:
        break;
398 399 400 401 402 403
      default:
        UNREACHABLE();
    }
  }
}

404
void FindOneByteStringIndices(Vector<const uint8_t> subject, uint8_t pattern,
405
                              std::vector<int>* indices, unsigned int limit) {
406
  DCHECK_LT(0, limit);
407 408
  // Collect indices of pattern in subject using memchr.
  // Stop after finding at most limit values.
409
  const uint8_t* subject_start = subject.begin();
410 411 412 413 414
  const uint8_t* subject_end = subject_start + subject.length();
  const uint8_t* pos = subject_start;
  while (limit > 0) {
    pos = reinterpret_cast<const uint8_t*>(
        memchr(pos, pattern, subject_end - pos));
415
    if (pos == nullptr) return;
416
    indices->push_back(static_cast<int>(pos - subject_start));
417 418 419 420 421 422
    pos++;
    limit--;
  }
}

void FindTwoByteStringIndices(const Vector<const uc16> subject, uc16 pattern,
423
                              std::vector<int>* indices, unsigned int limit) {
424
  DCHECK_LT(0, limit);
425
  const uc16* subject_start = subject.begin();
426 427 428
  const uc16* subject_end = subject_start + subject.length();
  for (const uc16* pos = subject_start; pos < subject_end && limit > 0; pos++) {
    if (*pos == pattern) {
429
      indices->push_back(static_cast<int>(pos - subject_start));
430 431 432 433 434 435 436
      limit--;
    }
  }
}

template <typename SubjectChar, typename PatternChar>
void FindStringIndices(Isolate* isolate, Vector<const SubjectChar> subject,
437 438
                       Vector<const PatternChar> pattern,
                       std::vector<int>* indices, unsigned int limit) {
439
  DCHECK_LT(0, limit);
440 441 442 443 444 445 446 447
  // Collect indices of pattern in subject.
  // Stop after finding at most limit values.
  int pattern_length = pattern.length();
  int index = 0;
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
  while (limit > 0) {
    index = search.Search(subject, index);
    if (index < 0) return;
448
    indices->push_back(index);
449 450 451 452 453
    index += pattern_length;
    limit--;
  }
}

454 455
void FindStringIndicesDispatch(Isolate* isolate, String subject, String pattern,
                               std::vector<int>* indices, unsigned int limit) {
456 457
  {
    DisallowHeapAllocation no_gc;
458 459
    String::FlatContent subject_content = subject.GetFlatContent(no_gc);
    String::FlatContent pattern_content = pattern.GetFlatContent(no_gc);
460 461 462 463 464 465 466 467 468
    DCHECK(subject_content.IsFlat());
    DCHECK(pattern_content.IsFlat());
    if (subject_content.IsOneByte()) {
      Vector<const uint8_t> subject_vector = subject_content.ToOneByteVector();
      if (pattern_content.IsOneByte()) {
        Vector<const uint8_t> pattern_vector =
            pattern_content.ToOneByteVector();
        if (pattern_vector.length() == 1) {
          FindOneByteStringIndices(subject_vector, pattern_vector[0], indices,
469
                                   limit);
470 471
        } else {
          FindStringIndices(isolate, subject_vector, pattern_vector, indices,
472
                            limit);
473 474 475
        }
      } else {
        FindStringIndices(isolate, subject_vector,
476
                          pattern_content.ToUC16Vector(), indices, limit);
477 478 479 480 481 482 483 484
      }
    } else {
      Vector<const uc16> subject_vector = subject_content.ToUC16Vector();
      if (pattern_content.IsOneByte()) {
        Vector<const uint8_t> pattern_vector =
            pattern_content.ToOneByteVector();
        if (pattern_vector.length() == 1) {
          FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
485
                                   limit);
486 487
        } else {
          FindStringIndices(isolate, subject_vector, pattern_vector, indices,
488
                            limit);
489 490 491 492 493
        }
      } else {
        Vector<const uc16> pattern_vector = pattern_content.ToUC16Vector();
        if (pattern_vector.length() == 1) {
          FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
494
                                   limit);
495 496
        } else {
          FindStringIndices(isolate, subject_vector, pattern_vector, indices,
497
                            limit);
498 499 500 501 502 503
        }
      }
    }
  }
}

504
namespace {
505 506 507
std::vector<int>* GetRewoundRegexpIndicesList(Isolate* isolate) {
  std::vector<int>* list = isolate->regexp_indices();
  list->clear();
508 509 510
  return list;
}

heimbuef's avatar
heimbuef committed
511 512 513
void TruncateRegexpIndicesList(Isolate* isolate) {
  // Same size as smallest zone segment, preserving behavior from the
  // runtime zone.
514
  static const int kMaxRegexpIndicesListCapacity = 8 * KB;
515 516 517 518 519
  std::vector<int>* indicies = isolate->regexp_indices();
  if (indicies->capacity() > kMaxRegexpIndicesListCapacity) {
    // Throw away backing storage.
    indicies->clear();
    indicies->shrink_to_fit();
520 521 522 523
  }
}
}  // namespace

524
template <typename ResultSeqString>
525
V8_WARN_UNUSED_RESULT static Object StringReplaceGlobalAtomRegExpWithString(
526
    Isolate* isolate, Handle<String> subject, Handle<JSRegExp> pattern_regexp,
527
    Handle<String> replacement, Handle<RegExpMatchInfo> last_match_info) {
528 529 530
  DCHECK(subject->IsFlat());
  DCHECK(replacement->IsFlat());

531
  std::vector<int>* indices = GetRewoundRegexpIndicesList(isolate);
532

533
  DCHECK_EQ(JSRegExp::ATOM, pattern_regexp->TypeTag());
534
  String pattern =
535 536
      String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex));
  int subject_len = subject->length();
537
  int pattern_len = pattern.length();
538 539
  int replacement_len = replacement->length();

540
  FindStringIndicesDispatch(isolate, *subject, pattern, indices, 0xFFFFFFFF);
541

542
  if (indices->empty()) return *subject;
543 544 545 546

  // Detect integer overflow.
  int64_t result_len_64 = (static_cast<int64_t>(replacement_len) -
                           static_cast<int64_t>(pattern_len)) *
547
                              static_cast<int64_t>(indices->size()) +
548 549 550 551 552 553 554 555
                          static_cast<int64_t>(subject_len);
  int result_len;
  if (result_len_64 > static_cast<int64_t>(String::kMaxLength)) {
    STATIC_ASSERT(String::kMaxLength < kMaxInt);
    result_len = kMaxInt;  // Provoke exception.
  } else {
    result_len = static_cast<int>(result_len_64);
  }
556
  if (result_len == 0) {
557
    return ReadOnlyRoots(isolate).empty_string();
558
  }
559 560 561 562 563 564 565 566 567 568 569 570 571 572

  int subject_pos = 0;
  int result_pos = 0;

  MaybeHandle<SeqString> maybe_res;
  if (ResultSeqString::kHasOneByteEncoding) {
    maybe_res = isolate->factory()->NewRawOneByteString(result_len);
  } else {
    maybe_res = isolate->factory()->NewRawTwoByteString(result_len);
  }
  Handle<SeqString> untyped_res;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, untyped_res, maybe_res);
  Handle<ResultSeqString> result = Handle<ResultSeqString>::cast(untyped_res);

573
  DisallowHeapAllocation no_gc;
574
  for (int index : *indices) {
575
    // Copy non-matched subject content.
576
    if (subject_pos < index) {
577
      String::WriteToFlat(*subject, result->GetChars(no_gc) + result_pos,
578 579
                          subject_pos, index);
      result_pos += index - subject_pos;
580 581 582 583
    }

    // Replace match.
    if (replacement_len > 0) {
584
      String::WriteToFlat(*replacement, result->GetChars(no_gc) + result_pos, 0,
585 586 587 588
                          replacement_len);
      result_pos += replacement_len;
    }

589
    subject_pos = index + pattern_len;
590 591 592
  }
  // Add remaining subject content at the end.
  if (subject_pos < subject_len) {
593 594
    String::WriteToFlat(*subject, result->GetChars(no_gc) + result_pos,
                        subject_pos, subject_len);
595 596
  }

597
  int32_t match_indices[] = {indices->back(), indices->back() + pattern_len};
598
  RegExp::SetLastMatchInfo(isolate, last_match_info, subject, 0, match_indices);
599

600 601
  TruncateRegexpIndicesList(isolate);

602 603 604
  return *result;
}

605
V8_WARN_UNUSED_RESULT static Object StringReplaceGlobalRegExpWithString(
606
    Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
607
    Handle<String> replacement, Handle<RegExpMatchInfo> last_match_info) {
608 609 610 611 612 613
  DCHECK(subject->IsFlat());
  DCHECK(replacement->IsFlat());

  int capture_count = regexp->CaptureCount();
  int subject_length = subject->length();

614 615
  JSRegExp::Type typeTag = regexp->TypeTag();
  if (typeTag == JSRegExp::IRREGEXP) {
Ana Peško's avatar
Ana Peško committed
616 617 618 619 620 621 622 623 624 625 626 627 628 629
    // Force tier up to native code for global replaces. The global replace is
    // implemented differently for native code and bytecode execution, where the
    // native code expects an array to store all the matches, and the bytecode
    // matches one at a time, so it's easier to tier-up to native code from the
    // start.
    if (FLAG_regexp_tier_up) {
      regexp->MarkTierUpForNextExec();
      if (FLAG_trace_regexp_tier_up) {
        PrintF(
            "Forcing tier-up of JSRegExp object %p in "
            "StringReplaceGlobalRegExpWithString\n",
            reinterpret_cast<void*>(regexp->ptr()));
      }
    }
630
    // Ensure the RegExp is compiled so we can access the capture-name map.
631
    if (RegExp::IrregexpPrepare(isolate, regexp, subject) == -1) {
632
      DCHECK(isolate->has_pending_exception());
633
      return ReadOnlyRoots(isolate).exception();
634
    }
635 636
  }

637
  // CompiledReplacement uses zone allocation.
638
  Zone zone(isolate->allocator(), ZONE_NAME);
639
  CompiledReplacement compiled_replacement(&zone);
640
  const bool simple_replace = compiled_replacement.Compile(
641
      isolate, regexp, replacement, capture_count, subject_length);
642 643

  // Shortcut for simple non-regexp global replacements
644
  if (typeTag == JSRegExp::ATOM && simple_replace) {
645 646
    if (subject->IsOneByteRepresentation() &&
        replacement->IsOneByteRepresentation()) {
647 648 649 650 651 652 653 654
      return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
          isolate, subject, regexp, replacement, last_match_info);
    } else {
      return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
          isolate, subject, regexp, replacement, last_match_info);
    }
  }

655
  RegExpGlobalCache global_cache(regexp, subject, isolate);
656
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
657 658

  int32_t* current_match = global_cache.FetchNext();
659
  if (current_match == nullptr) {
660
    if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
    return *subject;
  }

  // Guessing the number of parts that the final result string is built
  // from. Global regexps can match any number of times, so we guess
  // conservatively.
  int expected_parts = (compiled_replacement.parts() + 1) * 4 + 1;
  ReplacementStringBuilder builder(isolate->heap(), subject, expected_parts);

  int prev = 0;

  do {
    int start = current_match[0];
    int end = current_match[1];

    if (prev < start) {
      builder.AddSubjectSlice(prev, start);
    }

    if (simple_replace) {
      builder.AddString(replacement);
    } else {
      compiled_replacement.Apply(&builder, start, end, current_match);
    }
    prev = end;

    current_match = global_cache.FetchNext();
688
  } while (current_match != nullptr);
689

690
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
691 692 693 694 695

  if (prev < subject_length) {
    builder.AddSubjectSlice(prev, subject_length);
  }

696 697
  RegExp::SetLastMatchInfo(isolate, last_match_info, subject, capture_count,
                           global_cache.LastSuccessfulMatch());
698

699
  RETURN_RESULT_OR_FAILURE(isolate, builder.ToString());
700 701 702
}

template <typename ResultSeqString>
703
V8_WARN_UNUSED_RESULT static Object StringReplaceGlobalRegExpWithEmptyString(
704
    Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
705
    Handle<RegExpMatchInfo> last_match_info) {
706 707 708 709 710 711 712 713 714 715 716 717 718 719
  DCHECK(subject->IsFlat());

  // Shortcut for simple non-regexp global replacements
  if (regexp->TypeTag() == JSRegExp::ATOM) {
    Handle<String> empty_string = isolate->factory()->empty_string();
    if (subject->IsOneByteRepresentation()) {
      return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
          isolate, subject, regexp, empty_string, last_match_info);
    } else {
      return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
          isolate, subject, regexp, empty_string, last_match_info);
    }
  }

720
  RegExpGlobalCache global_cache(regexp, subject, isolate);
721
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
722 723

  int32_t* current_match = global_cache.FetchNext();
724
  if (current_match == nullptr) {
725
    if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
726 727 728 729 730 731 732 733 734
    return *subject;
  }

  int start = current_match[0];
  int end = current_match[1];
  int capture_count = regexp->CaptureCount();
  int subject_length = subject->length();

  int new_length = subject_length - (end - start);
735
  if (new_length == 0) return ReadOnlyRoots(isolate).empty_string();
736 737 738 739 740 741 742 743 744 745 746 747 748

  Handle<ResultSeqString> answer;
  if (ResultSeqString::kHasOneByteEncoding) {
    answer = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawOneByteString(new_length).ToHandleChecked());
  } else {
    answer = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawTwoByteString(new_length).ToHandleChecked());
  }

  int prev = 0;
  int position = 0;

749
  DisallowHeapAllocation no_gc;
750 751 752 753 754
  do {
    start = current_match[0];
    end = current_match[1];
    if (prev < start) {
      // Add substring subject[prev;start] to answer string.
755 756
      String::WriteToFlat(*subject, answer->GetChars(no_gc) + position, prev,
                          start);
757 758 759 760 761
      position += start - prev;
    }
    prev = end;

    current_match = global_cache.FetchNext();
762
  } while (current_match != nullptr);
763

764
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
765

766 767
  RegExp::SetLastMatchInfo(isolate, last_match_info, subject, capture_count,
                           global_cache.LastSuccessfulMatch());
768 769 770

  if (prev < subject_length) {
    // Add substring subject[prev;length] to answer string.
771
    String::WriteToFlat(*subject, answer->GetChars(no_gc) + position, prev,
772 773 774 775
                        subject_length);
    position += subject_length - prev;
  }

776
  if (position == 0) return ReadOnlyRoots(isolate).empty_string();
777 778 779 780 781 782 783 784 785 786 787 788 789

  // Shorten string and fill
  int string_size = ResultSeqString::SizeFor(position);
  int allocated_string_size = ResultSeqString::SizeFor(new_length);
  int delta = allocated_string_size - string_size;

  answer->set_length(position);
  if (delta == 0) return *answer;

  Address end_of_string = answer->address() + string_size;
  Heap* heap = isolate->heap();

  // The trimming is performed on a newly allocated object, which is on a
790
  // freshly allocated page or on an already swept page. Hence, the sweeper
791 792
  // thread can not get confused with the filler creation. No synchronization
  // needed.
793 794
  // TODO(hpayer): We should shrink the large object page if the size
  // of the object changed significantly.
795
  if (!heap->IsLargeObject(*answer)) {
796
    heap->CreateFillerObjectAt(end_of_string, delta, ClearRecordedSlots::kNo);
797
  }
798 799 800 801 802
  return *answer;
}

RUNTIME_FUNCTION(Runtime_StringSplit) {
  HandleScope handle_scope(isolate);
803
  DCHECK_EQ(3, args.length());
804 805 806
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1);
  CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]);
807
  CHECK_LT(0, limit);
808 809 810

  int subject_length = subject->length();
  int pattern_length = pattern->length();
811
  CHECK_LT(0, pattern_length);
812

813
  if (limit == 0xFFFFFFFFu) {
814
    FixedArray last_match_cache_unused;
815 816
    Handle<Object> cached_answer(
        RegExpResultsCache::Lookup(isolate->heap(), *subject, *pattern,
817
                                   &last_match_cache_unused,
818 819
                                   RegExpResultsCache::STRING_SPLIT_SUBSTRINGS),
        isolate);
820
    if (*cached_answer != Smi::kZero) {
821 822 823 824 825 826 827
      // The cache FixedArray is a COW-array and can therefore be reused.
      Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(
          Handle<FixedArray>::cast(cached_answer));
      return *result;
    }
  }

828
  // The limit can be very large (0xFFFFFFFFu), but since the pattern
829 830 831
  // isn't empty, we can never create more parts than ~half the length
  // of the subject.

832 833
  subject = String::Flatten(isolate, subject);
  pattern = String::Flatten(isolate, pattern);
834

835
  std::vector<int>* indices = GetRewoundRegexpIndicesList(isolate);
836

837
  FindStringIndicesDispatch(isolate, *subject, *pattern, indices, limit);
838

839 840
  if (static_cast<uint32_t>(indices->size()) < limit) {
    indices->push_back(subject_length);
841 842 843 844 845
  }

  // The list indices now contains the end of each part to create.

  // Create JSArray of substrings separated by separator.
846
  int part_count = static_cast<int>(indices->size());
847

848
  Handle<JSArray> result =
849
      isolate->factory()->NewJSArray(PACKED_ELEMENTS, part_count, part_count,
850
                                     INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
851

852
  DCHECK(result->HasObjectElements());
853

854
  Handle<FixedArray> elements(FixedArray::cast(result->elements()), isolate);
855

856
  if (part_count == 1 && indices->at(0) == subject_length) {
857 858 859
    elements->set(0, *subject);
  } else {
    int part_start = 0;
860
    FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < part_count, i++, {
861
      int part_end = indices->at(i);
862 863 864 865
      Handle<String> substring =
          isolate->factory()->NewProperSubString(subject, part_start, part_end);
      elements->set(i, *substring);
      part_start = part_end + pattern_length;
866
    });
867 868
  }

869
  if (limit == 0xFFFFFFFFu) {
870
    if (result->HasObjectElements()) {
871
      RegExpResultsCache::Enter(isolate, subject, pattern, elements,
872
                                isolate->factory()->empty_fixed_array(),
873 874 875 876
                                RegExpResultsCache::STRING_SPLIT_SUBSTRINGS);
    }
  }

877 878
  TruncateRegexpIndicesList(isolate);

879 880 881
  return *result;
}

882
RUNTIME_FUNCTION(Runtime_RegExpExec) {
883
  HandleScope scope(isolate);
884
  DCHECK_EQ(4, args.length());
885 886 887
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
  CONVERT_INT32_ARG_CHECKED(index, 2);
888
  CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 3);
889 890
  // Due to the way the JS calls are constructed this must be less than the
  // length of a string, i.e. it is always a Smi.  We check anyway for security.
891 892
  CHECK_LE(0, index);
  CHECK_GE(subject->length(), index);
893
  isolate->counters()->regexp_entry_runtime()->Increment();
894 895
  RETURN_RESULT_OR_FAILURE(
      isolate, RegExp::Exec(isolate, regexp, subject, index, last_match_info));
896 897
}

898 899 900 901
namespace {

class MatchInfoBackedMatch : public String::Match {
 public:
902 903
  MatchInfoBackedMatch(Isolate* isolate, Handle<JSRegExp> regexp,
                       Handle<String> subject,
904
                       Handle<RegExpMatchInfo> match_info)
905
      : isolate_(isolate), match_info_(match_info) {
906
    subject_ = String::Flatten(isolate, subject);
907 908

    if (regexp->TypeTag() == JSRegExp::IRREGEXP) {
909
      Object o = regexp->CaptureNameMap();
910
      has_named_captures_ = o.IsFixedArray();
911
      if (has_named_captures_) {
912
        capture_name_map_ = handle(FixedArray::cast(o), isolate);
913 914 915 916
      }
    } else {
      has_named_captures_ = false;
    }
917 918 919 920 921 922 923
  }

  Handle<String> GetMatch() override {
    return RegExpUtils::GenericCaptureGetter(isolate_, match_info_, 0, nullptr);
  }

  Handle<String> GetPrefix() override {
924
    const int match_start = match_info_->Capture(0);
925 926 927 928
    return isolate_->factory()->NewSubString(subject_, 0, match_start);
  }

  Handle<String> GetSuffix() override {
929
    const int match_end = match_info_->Capture(1);
930 931 932 933
    return isolate_->factory()->NewSubString(subject_, match_end,
                                             subject_->length());
  }

934 935
  bool HasNamedCaptures() override { return has_named_captures_; }

936
  int CaptureCount() override {
937
    return match_info_->NumberOfCaptureRegisters() / 2;
938 939
  }

940 941 942 943 944 945 946 947
  MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
    Handle<Object> capture_obj = RegExpUtils::GenericCaptureGetter(
        isolate_, match_info_, i, capture_exists);
    return (*capture_exists) ? Object::ToString(isolate_, capture_obj)
                             : isolate_->factory()->empty_string();
  }

  MaybeHandle<String> GetNamedCapture(Handle<String> name,
948
                                      CaptureState* state) override {
949 950
    DCHECK(has_named_captures_);
    const int capture_index = LookupNamedCapture(
951
        [=](String capture_name) { return capture_name.Equals(*name); },
952 953 954
        *capture_name_map_);

    if (capture_index == -1) {
955
      *state = INVALID;
956 957 958 959
      return name;  // Arbitrary string handle.
    }

    DCHECK(1 <= capture_index && capture_index <= CaptureCount());
960 961 962 963 964 965 966 967 968 969 970 971 972 973

    bool capture_exists;
    Handle<String> capture_value;
    ASSIGN_RETURN_ON_EXCEPTION(isolate_, capture_value,
                               GetCapture(capture_index, &capture_exists),
                               String);

    if (!capture_exists) {
      *state = UNMATCHED;
      return isolate_->factory()->empty_string();
    } else {
      *state = MATCHED;
      return capture_value;
    }
974
  }
975

976 977 978
 private:
  Isolate* isolate_;
  Handle<String> subject_;
979
  Handle<RegExpMatchInfo> match_info_;
980 981 982

  bool has_named_captures_;
  Handle<FixedArray> capture_name_map_;
983 984 985 986 987 988
};

class VectorBackedMatch : public String::Match {
 public:
  VectorBackedMatch(Isolate* isolate, Handle<String> subject,
                    Handle<String> match, int match_position,
989
                    ZoneVector<Handle<Object>>* captures,
990
                    Handle<Object> groups_obj)
991 992 993 994
      : isolate_(isolate),
        match_(match),
        match_position_(match_position),
        captures_(captures) {
995
    subject_ = String::Flatten(isolate, subject);
996 997 998 999

    DCHECK(groups_obj->IsUndefined(isolate) || groups_obj->IsJSReceiver());
    has_named_captures_ = !groups_obj->IsUndefined(isolate);
    if (has_named_captures_) groups_obj_ = Handle<JSReceiver>::cast(groups_obj);
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
  }

  Handle<String> GetMatch() override { return match_; }

  Handle<String> GetPrefix() override {
    return isolate_->factory()->NewSubString(subject_, 0, match_position_);
  }

  Handle<String> GetSuffix() override {
    const int match_end_position = match_position_ + match_->length();
    return isolate_->factory()->NewSubString(subject_, match_end_position,
                                             subject_->length());
  }

1014 1015
  bool HasNamedCaptures() override { return has_named_captures_; }

1016 1017
  int CaptureCount() override { return static_cast<int>(captures_->size()); }

1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
  MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
    Handle<Object> capture_obj = captures_->at(i);
    if (capture_obj->IsUndefined(isolate_)) {
      *capture_exists = false;
      return isolate_->factory()->empty_string();
    }
    *capture_exists = true;
    return Object::ToString(isolate_, capture_obj);
  }

  MaybeHandle<String> GetNamedCapture(Handle<String> name,
1029
                                      CaptureState* state) override {
1030
    DCHECK(has_named_captures_);
1031 1032 1033 1034 1035 1036 1037 1038 1039 1040

    Maybe<bool> maybe_capture_exists =
        JSReceiver::HasProperty(groups_obj_, name);
    if (maybe_capture_exists.IsNothing()) return MaybeHandle<String>();

    if (!maybe_capture_exists.FromJust()) {
      *state = INVALID;
      return name;  // Arbitrary string handle.
    }

1041 1042
    Handle<Object> capture_obj;
    ASSIGN_RETURN_ON_EXCEPTION(isolate_, capture_obj,
1043 1044
                               Object::GetProperty(isolate_, groups_obj_, name),
                               String);
1045
    if (capture_obj->IsUndefined(isolate_)) {
1046 1047
      *state = UNMATCHED;
      return isolate_->factory()->empty_string();
1048
    } else {
1049
      *state = MATCHED;
1050 1051 1052
      return Object::ToString(isolate_, capture_obj);
    }
  }
1053 1054 1055 1056 1057 1058

 private:
  Isolate* isolate_;
  Handle<String> subject_;
  Handle<String> match_;
  const int match_position_;
1059
  ZoneVector<Handle<Object>>* captures_;
1060 1061 1062

  bool has_named_captures_;
  Handle<JSReceiver> groups_obj_;
1063 1064
};

1065 1066 1067 1068
// Create the groups object (see also the RegExp result creation in
// RegExpBuiltinsAssembler::ConstructNewResultFromMatchInfo).
Handle<JSObject> ConstructNamedCaptureGroupsObject(
    Isolate* isolate, Handle<FixedArray> capture_map,
1069
    const std::function<Object(int)>& f_get_capture) {
1070 1071 1072 1073 1074 1075 1076
  Handle<JSObject> groups = isolate->factory()->NewJSObjectWithNullProto();

  const int capture_count = capture_map->length() >> 1;
  for (int i = 0; i < capture_count; i++) {
    const int name_ix = i * 2;
    const int index_ix = i * 2 + 1;

1077 1078
    Handle<String> capture_name(String::cast(capture_map->get(name_ix)),
                                isolate);
jgruber's avatar
jgruber committed
1079
    const int capture_ix = Smi::ToInt(capture_map->get(index_ix));
1080 1081 1082
    DCHECK(1 <= capture_ix && capture_ix <= capture_count);

    Handle<Object> capture_value(f_get_capture(capture_ix), isolate);
1083
    DCHECK(capture_value->IsUndefined(isolate) || capture_value->IsString());
1084

1085
    JSObject::AddProperty(isolate, groups, capture_name, capture_value, NONE);
1086 1087 1088 1089 1090
  }

  return groups;
}

1091
// Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
1092 1093
// separate last match info.  See comment on that function.
template <bool has_capture>
1094 1095 1096 1097
static Object SearchRegExpMultiple(Isolate* isolate, Handle<String> subject,
                                   Handle<JSRegExp> regexp,
                                   Handle<RegExpMatchInfo> last_match_array,
                                   Handle<JSArray> result_array) {
1098
  DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
1099
  DCHECK_NE(has_capture, regexp->CaptureCount() == 0);
1100
  DCHECK(subject->IsFlat());
1101

Ana Peško's avatar
Ana Peško committed
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114
  // Force tier up to native code for global replaces. The global replace is
  // implemented differently for native code and bytecode execution, where the
  // native code expects an array to store all the matches, and the bytecode
  // matches one at a time, so it's easier to tier-up to native code from the
  // start.
  if (FLAG_regexp_tier_up && regexp->TypeTag() == JSRegExp::IRREGEXP) {
    regexp->MarkTierUpForNextExec();
    if (FLAG_trace_regexp_tier_up) {
      PrintF("Forcing tier-up of JSRegExp object %p in SearchRegExpMultiple\n",
             reinterpret_cast<void*>(regexp->ptr()));
    }
  }

1115 1116 1117 1118 1119 1120
  int capture_count = regexp->CaptureCount();
  int subject_length = subject->length();

  static const int kMinLengthToCache = 0x1000;

  if (subject_length > kMinLengthToCache) {
1121
    FixedArray last_match_cache;
1122
    Object cached_answer = RegExpResultsCache::Lookup(
1123 1124
        isolate->heap(), *subject, regexp->data(), &last_match_cache,
        RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
1125
    if (cached_answer.IsFixedArray()) {
1126 1127 1128
      int capture_registers = (capture_count + 1) * 2;
      int32_t* last_match = NewArray<int32_t>(capture_registers);
      for (int i = 0; i < capture_registers; i++) {
1129
        last_match[i] = Smi::ToInt(last_match_cache.get(i));
1130
      }
1131
      Handle<FixedArray> cached_fixed_array =
1132
          Handle<FixedArray>(FixedArray::cast(cached_answer), isolate);
1133 1134 1135 1136 1137
      // The cache FixedArray is a COW-array and we need to return a copy.
      Handle<FixedArray> copied_fixed_array =
          isolate->factory()->CopyFixedArrayWithMap(
              cached_fixed_array, isolate->factory()->fixed_array_map());
      JSArray::SetContent(result_array, copied_fixed_array);
1138 1139
      RegExp::SetLastMatchInfo(isolate, last_match_array, subject,
                               capture_count, last_match);
1140
      DeleteArray(last_match);
1141
      return *result_array;
1142 1143 1144
    }
  }

1145
  RegExpGlobalCache global_cache(regexp, subject, isolate);
1146
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
1147 1148

  // Ensured in Runtime_RegExpExecMultiple.
1149
  DCHECK(result_array->HasObjectElements());
1150 1151
  Handle<FixedArray> result_elements(FixedArray::cast(result_array->elements()),
                                     isolate);
1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167
  if (result_elements->length() < 16) {
    result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
  }

  FixedArrayBuilder builder(result_elements);

  // Position to search from.
  int match_start = -1;
  int match_end = 0;
  bool first = true;

  // Two smis before and after the match, for very long strings.
  static const int kMaxBuilderEntriesPerRegExpMatch = 5;

  while (true) {
    int32_t* current_match = global_cache.FetchNext();
1168
    if (current_match == nullptr) break;
1169
    match_start = current_match[0];
1170
    builder.EnsureCapacity(isolate, kMaxBuilderEntriesPerRegExpMatch);
1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190
    if (match_end < match_start) {
      ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
                                                match_start);
    }
    match_end = current_match[1];
    {
      // Avoid accumulating new handles inside loop.
      HandleScope temp_scope(isolate);
      Handle<String> match;
      if (!first) {
        match = isolate->factory()->NewProperSubString(subject, match_start,
                                                       match_end);
      } else {
        match =
            isolate->factory()->NewSubString(subject, match_start, match_end);
        first = false;
      }

      if (has_capture) {
        // Arguments array to replace function is match, captures, index and
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201
        // subject, i.e., 3 + capture count in total. If the RegExp contains
        // named captures, they are also passed as the last argument.

        Handle<Object> maybe_capture_map(regexp->CaptureNameMap(), isolate);
        const bool has_named_captures = maybe_capture_map->IsFixedArray();

        const int argc =
            has_named_captures ? 4 + capture_count : 3 + capture_count;

        Handle<FixedArray> elements = isolate->factory()->NewFixedArray(argc);
        int cursor = 0;
1202

1203
        elements->set(cursor++, *match);
1204 1205 1206 1207 1208 1209 1210
        for (int i = 1; i <= capture_count; i++) {
          int start = current_match[i * 2];
          if (start >= 0) {
            int end = current_match[i * 2 + 1];
            DCHECK(start <= end);
            Handle<String> substring =
                isolate->factory()->NewSubString(subject, start, end);
1211
            elements->set(cursor++, *substring);
1212
          } else {
1213
            DCHECK_GT(0, current_match[i * 2 + 1]);
1214
            elements->set(cursor++, ReadOnlyRoots(isolate).undefined_value());
1215 1216
          }
        }
1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229

        elements->set(cursor++, Smi::FromInt(match_start));
        elements->set(cursor++, *subject);

        if (has_named_captures) {
          Handle<FixedArray> capture_map =
              Handle<FixedArray>::cast(maybe_capture_map);
          Handle<JSObject> groups = ConstructNamedCaptureGroupsObject(
              isolate, capture_map, [=](int ix) { return elements->get(ix); });
          elements->set(cursor++, *groups);
        }

        DCHECK_EQ(cursor, argc);
1230 1231 1232 1233 1234 1235 1236
        builder.Add(*isolate->factory()->NewJSArrayWithElements(elements));
      } else {
        builder.Add(*match);
      }
    }
  }

1237
  if (global_cache.HasException()) return ReadOnlyRoots(isolate).exception();
1238 1239 1240 1241 1242 1243 1244 1245

  if (match_start >= 0) {
    // Finished matching, with at least one match.
    if (match_end < subject_length) {
      ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
                                                subject_length);
    }

1246 1247
    RegExp::SetLastMatchInfo(isolate, last_match_array, subject, capture_count,
                             global_cache.LastSuccessfulMatch());
1248 1249

    if (subject_length > kMinLengthToCache) {
1250 1251 1252 1253 1254 1255 1256 1257 1258
      // Store the last successful match into the array for caching.
      // TODO(yangguo): do not expose last match to JS and simplify caching.
      int capture_registers = (capture_count + 1) * 2;
      Handle<FixedArray> last_match_cache =
          isolate->factory()->NewFixedArray(capture_registers);
      int32_t* last_match = global_cache.LastSuccessfulMatch();
      for (int i = 0; i < capture_registers; i++) {
        last_match_cache->set(i, Smi::FromInt(last_match[i]));
      }
1259
      Handle<FixedArray> result_fixed_array =
1260
          FixedArray::ShrinkOrEmpty(isolate, builder.array(), builder.length());
1261 1262 1263 1264
      // Cache the result and copy the FixedArray into a COW array.
      Handle<FixedArray> copied_fixed_array =
          isolate->factory()->CopyFixedArrayWithMap(
              result_fixed_array, isolate->factory()->fixed_array_map());
1265
      RegExpResultsCache::Enter(
1266
          isolate, subject, handle(regexp->data(), isolate), copied_fixed_array,
1267
          last_match_cache, RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
1268
    }
1269
    return *builder.ToJSArray(result_array);
1270
  } else {
1271
    return ReadOnlyRoots(isolate).null_value();  // No matches at all.
1272 1273 1274 1275 1276
  }
}

// Legacy implementation of RegExp.prototype[Symbol.replace] which
// doesn't properly call the underlying exec method.
1277 1278
V8_WARN_UNUSED_RESULT MaybeHandle<String> RegExpReplace(
    Isolate* isolate, Handle<JSRegExp> regexp, Handle<String> string,
1279
    Handle<String> replace) {
1280 1281 1282
  // Functional fast-paths are dispatched directly by replace builtin.
  DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));

1283 1284 1285 1286
  Factory* factory = isolate->factory();

  const int flags = regexp->GetFlags();
  const bool global = (flags & JSRegExp::kGlobal) != 0;
1287
  const bool sticky = (flags & JSRegExp::kSticky) != 0;
1288

1289
  replace = String::Flatten(isolate, replace);
1290

1291
  Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();
1292

1293 1294
  if (!global) {
    // Non-global regexp search, string replace.
1295

1296 1297
    uint32_t last_index = 0;
    if (sticky) {
1298
      Handle<Object> last_index_obj(regexp->last_index(), isolate);
1299 1300 1301 1302 1303 1304
      ASSIGN_RETURN_ON_EXCEPTION(isolate, last_index_obj,
                                 Object::ToLength(isolate, last_index_obj),
                                 String);
      last_index = PositiveNumberToUint32(*last_index_obj);
    }

1305 1306 1307
    Handle<Object> match_indices_obj(ReadOnlyRoots(isolate).null_value(),
                                     isolate);

1308 1309
    // A lastIndex exceeding the string length always returns null (signalling
    // failure) in RegExpBuiltinExec, thus we can skip the call.
1310
    if (last_index <= static_cast<uint32_t>(string->length())) {
1311 1312 1313 1314
      ASSIGN_RETURN_ON_EXCEPTION(
          isolate, match_indices_obj,
          RegExp::Exec(isolate, regexp, string, last_index, last_match_info),
          String);
1315
    }
1316

1317
    if (match_indices_obj->IsNull(isolate)) {
1318
      if (sticky) regexp->set_last_index(Smi::kZero, SKIP_WRITE_BARRIER);
1319 1320
      return string;
    }
1321

1322
    auto match_indices = Handle<RegExpMatchInfo>::cast(match_indices_obj);
1323

1324 1325
    const int start_index = match_indices->Capture(0);
    const int end_index = match_indices->Capture(1);
1326

1327
    if (sticky) {
1328
      regexp->set_last_index(Smi::FromInt(end_index), SKIP_WRITE_BARRIER);
1329
    }
1330

1331 1332
    IncrementalStringBuilder builder(isolate);
    builder.AppendString(factory->NewSubString(string, 0, start_index));
1333

1334
    if (replace->length() > 0) {
1335
      MatchInfoBackedMatch m(isolate, regexp, string, match_indices);
1336 1337 1338 1339 1340 1341
      Handle<String> replacement;
      ASSIGN_RETURN_ON_EXCEPTION(isolate, replacement,
                                 String::GetSubstitution(isolate, &m, replace),
                                 String);
      builder.AppendString(replacement);
    }
1342

1343 1344 1345 1346 1347 1348 1349 1350
    builder.AppendString(
        factory->NewSubString(string, end_index, string->length()));
    return builder.Finish();
  } else {
    // Global regexp search, string replace.
    DCHECK(global);
    RETURN_ON_EXCEPTION(isolate, RegExpUtils::SetLastIndex(isolate, regexp, 0),
                        String);
1351

1352
    if (replace->length() == 0) {
1353
      if (string->IsOneByteRepresentation()) {
1354
        Object result =
1355 1356
            StringReplaceGlobalRegExpWithEmptyString<SeqOneByteString>(
                isolate, string, regexp, last_match_info);
1357 1358
        return handle(String::cast(result), isolate);
      } else {
1359
        Object result =
1360 1361 1362
            StringReplaceGlobalRegExpWithEmptyString<SeqTwoByteString>(
                isolate, string, regexp, last_match_info);
        return handle(String::cast(result), isolate);
1363 1364
      }
    }
1365

1366
    Object result = StringReplaceGlobalRegExpWithString(
1367
        isolate, string, regexp, replace, last_match_info);
1368
    if (result.IsString()) {
1369
      return handle(String::cast(result), isolate);
1370
    } else {
1371
      return MaybeHandle<String>();
1372 1373 1374 1375 1376 1377 1378 1379
    }
  }

  UNREACHABLE();
}

}  // namespace

1380 1381 1382
// This is only called for StringReplaceGlobalRegExpWithFunction.
RUNTIME_FUNCTION(Runtime_RegExpExecMultiple) {
  HandleScope handles(isolate);
1383
  DCHECK_EQ(4, args.length());
1384

1385 1386 1387 1388
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
  CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 2);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);
1389 1390

  DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
1391
  CHECK(result_array->HasObjectElements());
1392

1393
  subject = String::Flatten(isolate, subject);
1394 1395
  CHECK(regexp->GetFlags() & JSRegExp::kGlobal);

1396
  Object result;
1397
  if (regexp->CaptureCount() == 0) {
1398 1399
    result = SearchRegExpMultiple<false>(isolate, subject, regexp,
                                         last_match_info, result_array);
1400
  } else {
1401 1402
    result = SearchRegExpMultiple<true>(isolate, subject, regexp,
                                        last_match_info, result_array);
1403
  }
1404 1405
  DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
  return result;
1406 1407 1408 1409
}

RUNTIME_FUNCTION(Runtime_StringReplaceNonGlobalRegExpWithFunction) {
  HandleScope scope(isolate);
1410
  DCHECK_EQ(3, args.length());
1411 1412
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
1413
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, replace_obj, 2);
1414

1415
  DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
1416
  DCHECK(replace_obj->map().is_callable());
1417

1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428
  Factory* factory = isolate->factory();
  Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();

  const int flags = regexp->GetFlags();
  DCHECK_EQ(flags & JSRegExp::kGlobal, 0);

  // TODO(jgruber): This should be an easy port to CSA with massive payback.

  const bool sticky = (flags & JSRegExp::kSticky) != 0;
  uint32_t last_index = 0;
  if (sticky) {
1429
    Handle<Object> last_index_obj(regexp->last_index(), isolate);
1430 1431 1432 1433 1434
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));
    last_index = PositiveNumberToUint32(*last_index_obj);
  }

1435 1436 1437 1438 1439 1440 1441 1442
  Handle<Object> match_indices_obj(ReadOnlyRoots(isolate).null_value(),
                                   isolate);

  // A lastIndex exceeding the string length always returns null (signalling
  // failure) in RegExpBuiltinExec, thus we can skip the call.
  if (last_index <= static_cast<uint32_t>(subject->length())) {
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, match_indices_obj,
1443
        RegExp::Exec(isolate, regexp, subject, last_index, last_match_info));
1444
  }
1445 1446

  if (match_indices_obj->IsNull(isolate)) {
1447
    if (sticky) regexp->set_last_index(Smi::kZero, SKIP_WRITE_BARRIER);
1448 1449 1450 1451 1452 1453 1454 1455 1456
    return *subject;
  }

  Handle<RegExpMatchInfo> match_indices =
      Handle<RegExpMatchInfo>::cast(match_indices_obj);

  const int index = match_indices->Capture(0);
  const int end_of_match = match_indices->Capture(1);

1457
  if (sticky) {
1458
    regexp->set_last_index(Smi::FromInt(end_of_match), SKIP_WRITE_BARRIER);
1459
  }
1460 1461 1462 1463 1464

  IncrementalStringBuilder builder(isolate);
  builder.AppendString(factory->NewSubString(subject, 0, index));

  // Compute the parameter list consisting of the match, captures, index,
1465 1466 1467
  // and subject for the replace function invocation. If the RegExp contains
  // named captures, they are also passed as the last argument.

1468 1469 1470
  // The number of captures plus one for the match.
  const int m = match_indices->NumberOfCaptureRegisters() / 2;

1471 1472 1473 1474 1475 1476
  bool has_named_captures = false;
  Handle<FixedArray> capture_map;
  if (m > 1) {
    // The existence of capture groups implies IRREGEXP kind.
    DCHECK_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);

1477
    Object maybe_capture_map = regexp->CaptureNameMap();
1478
    if (maybe_capture_map.IsFixedArray()) {
1479
      has_named_captures = true;
1480
      capture_map = handle(FixedArray::cast(maybe_capture_map), isolate);
1481 1482 1483
    }
  }

1484 1485 1486 1487 1488
  const uint32_t argc = GetArgcForReplaceCallable(m, has_named_captures);
  if (argc == static_cast<uint32_t>(-1)) {
    THROW_NEW_ERROR_RETURN_FAILURE(
        isolate, NewRangeError(MessageTemplate::kTooManyArguments));
  }
1489 1490
  ScopedVector<Handle<Object>> argv(argc);

1491
  int cursor = 0;
1492 1493 1494 1495 1496
  for (int j = 0; j < m; j++) {
    bool ok;
    Handle<String> capture =
        RegExpUtils::GenericCaptureGetter(isolate, match_indices, j, &ok);
    if (ok) {
1497
      argv[cursor++] = capture;
1498
    } else {
1499
      argv[cursor++] = factory->undefined_value();
1500 1501 1502
    }
  }

1503 1504 1505 1506 1507 1508 1509 1510 1511
  argv[cursor++] = handle(Smi::FromInt(index), isolate);
  argv[cursor++] = subject;

  if (has_named_captures) {
    argv[cursor++] = ConstructNamedCaptureGroupsObject(
        isolate, capture_map, [&argv](int ix) { return *argv[ix]; });
  }

  DCHECK_EQ(cursor, argc);
1512 1513 1514 1515 1516

  Handle<Object> replacement_obj;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, replacement_obj,
      Execution::Call(isolate, replace_obj, factory->undefined_value(), argc,
1517
                      argv.begin()));
1518 1519 1520 1521 1522 1523 1524 1525 1526 1527

  Handle<String> replacement;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, replacement, Object::ToString(isolate, replacement_obj));

  builder.AppendString(replacement);
  builder.AppendString(
      factory->NewSubString(subject, end_of_match, subject->length()));

  RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
1528 1529
}

1530 1531
namespace {

1532 1533 1534
V8_WARN_UNUSED_RESULT MaybeHandle<Object> ToUint32(Isolate* isolate,
                                                   Handle<Object> object,
                                                   uint32_t* out) {
1535 1536 1537 1538 1539 1540
  if (object->IsUndefined(isolate)) {
    *out = kMaxUInt32;
    return object;
  }

  Handle<Object> number;
1541 1542
  ASSIGN_RETURN_ON_EXCEPTION(isolate, number, Object::ToNumber(isolate, object),
                             Object);
1543 1544 1545 1546 1547 1548 1549
  *out = NumberToUint32(*number);
  return object;
}

Handle<JSArray> NewJSArrayWithElements(Isolate* isolate,
                                       Handle<FixedArray> elems,
                                       int num_elems) {
1550
  return isolate->factory()->NewJSArrayWithElements(
1551
      FixedArray::ShrinkOrEmpty(isolate, elems, num_elems));
1552 1553 1554 1555 1556 1557 1558 1559 1560
}

}  // namespace

// Slow path for:
// ES#sec-regexp.prototype-@@replace
// RegExp.prototype [ @@split ] ( string, limit )
RUNTIME_FUNCTION(Runtime_RegExpSplit) {
  HandleScope scope(isolate);
1561
  DCHECK_EQ(3, args.length());
1562 1563 1564 1565 1566 1567 1568 1569 1570 1571

  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, recv, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, string, 1);
  CONVERT_ARG_HANDLE_CHECKED(Object, limit_obj, 2);

  Factory* factory = isolate->factory();

  Handle<JSFunction> regexp_fun = isolate->regexp_function();
  Handle<Object> ctor;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1572
      isolate, ctor, Object::SpeciesConstructor(isolate, recv, regexp_fun));
1573 1574 1575

  Handle<Object> flags_obj;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1576 1577
      isolate, flags_obj,
      JSObject::GetProperty(isolate, recv, factory->flags_string()));
1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604

  Handle<String> flags;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, flags,
                                     Object::ToString(isolate, flags_obj));

  Handle<String> u_str = factory->LookupSingleCharacterStringFromCode('u');
  const bool unicode = (String::IndexOf(isolate, flags, u_str, 0) >= 0);

  Handle<String> y_str = factory->LookupSingleCharacterStringFromCode('y');
  const bool sticky = (String::IndexOf(isolate, flags, y_str, 0) >= 0);

  Handle<String> new_flags = flags;
  if (!sticky) {
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, new_flags,
                                       factory->NewConsString(flags, y_str));
  }

  Handle<JSReceiver> splitter;
  {
    const int argc = 2;

    ScopedVector<Handle<Object>> argv(argc);
    argv[0] = recv;
    argv[1] = new_flags;

    Handle<Object> splitter_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1605
        isolate, splitter_obj,
1606
        Execution::New(isolate, ctor, argc, argv.begin()));
1607 1608 1609 1610 1611 1612 1613

    splitter = Handle<JSReceiver>::cast(splitter_obj);
  }

  uint32_t limit;
  RETURN_FAILURE_ON_EXCEPTION(isolate, ToUint32(isolate, limit_obj, &limit));

1614
  const uint32_t length = string->length();
1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632

  if (limit == 0) return *factory->NewJSArray(0);

  if (length == 0) {
    Handle<Object> result;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, result, RegExpUtils::RegExpExec(isolate, splitter, string,
                                                 factory->undefined_value()));

    if (!result->IsNull(isolate)) return *factory->NewJSArray(0);

    Handle<FixedArray> elems = factory->NewUninitializedFixedArray(1);
    elems->set(0, *string);
    return *factory->NewJSArrayWithElements(elems);
  }

  static const int kInitialArraySize = 8;
  Handle<FixedArray> elems = factory->NewFixedArrayWithHoles(kInitialArraySize);
1633
  uint32_t num_elems = 0;
1634

1635 1636
  uint32_t string_index = 0;
  uint32_t prev_string_index = 0;
1637 1638 1639 1640 1641 1642 1643 1644 1645 1646
  while (string_index < length) {
    RETURN_FAILURE_ON_EXCEPTION(
        isolate, RegExpUtils::SetLastIndex(isolate, splitter, string_index));

    Handle<Object> result;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, result, RegExpUtils::RegExpExec(isolate, splitter, string,
                                                 factory->undefined_value()));

    if (result->IsNull(isolate)) {
1647 1648
      string_index = static_cast<uint32_t>(
          RegExpUtils::AdvanceStringIndex(string, string_index, unicode));
1649 1650 1651 1652 1653 1654 1655 1656 1657 1658
      continue;
    }

    Handle<Object> last_index_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, last_index_obj, RegExpUtils::GetLastIndex(isolate, splitter));

    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));

1659 1660
    const uint32_t end =
        std::min(PositiveNumberToUint32(*last_index_obj), length);
1661
    if (end == prev_string_index) {
1662 1663
      string_index = static_cast<uint32_t>(
          RegExpUtils::AdvanceStringIndex(string, string_index, unicode));
1664 1665 1666 1667 1668 1669
      continue;
    }

    {
      Handle<String> substr =
          factory->NewSubString(string, prev_string_index, string_index);
1670
      elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, substr);
1671
      if (num_elems == limit) {
1672 1673 1674 1675 1676 1677 1678 1679 1680
        return *NewJSArrayWithElements(isolate, elems, num_elems);
      }
    }

    prev_string_index = end;

    Handle<Object> num_captures_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, num_captures_obj,
1681 1682
        Object::GetProperty(isolate, result,
                            isolate->factory()->length_string()));
1683 1684 1685

    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, num_captures_obj, Object::ToLength(isolate, num_captures_obj));
1686
    const uint32_t num_captures = PositiveNumberToUint32(*num_captures_obj);
1687

1688
    for (uint32_t i = 1; i < num_captures; i++) {
1689 1690 1691
      Handle<Object> capture;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, capture, Object::GetElement(isolate, result, i));
1692
      elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, capture);
1693
      if (num_elems == limit) {
1694 1695 1696 1697 1698 1699 1700 1701 1702 1703
        return *NewJSArrayWithElements(isolate, elems, num_elems);
      }
    }

    string_index = prev_string_index;
  }

  {
    Handle<String> substr =
        factory->NewSubString(string, prev_string_index, length);
1704
    elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, substr);
1705 1706 1707 1708 1709
  }

  return *NewJSArrayWithElements(isolate, elems, num_elems);
}

1710 1711 1712
// Slow path for:
// ES#sec-regexp.prototype-@@replace
// RegExp.prototype [ @@replace ] ( string, replaceValue )
1713
RUNTIME_FUNCTION(Runtime_RegExpReplaceRT) {
1714
  HandleScope scope(isolate);
1715
  DCHECK_EQ(3, args.length());
1716 1717 1718

  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, recv, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, string, 1);
1719
  Handle<Object> replace_obj = args.at(2);
1720 1721 1722

  Factory* factory = isolate->factory();

1723
  string = String::Flatten(isolate, string);
1724

1725 1726
  const bool functional_replace = replace_obj->IsCallable();

1727 1728 1729 1730 1731 1732
  Handle<String> replace;
  if (!functional_replace) {
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, replace,
                                       Object::ToString(isolate, replace_obj));
  }

1733
  // Fast-path for unmodified JSRegExps (and non-functional replace).
1734
  if (RegExpUtils::IsUnmodifiedRegExp(isolate, recv)) {
1735 1736 1737
    // We should never get here with functional replace because unmodified
    // regexp and functional replace should be fully handled in CSA code.
    CHECK(!functional_replace);
1738 1739 1740 1741 1742 1743
    Handle<Object> result;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, result,
        RegExpReplace(isolate, Handle<JSRegExp>::cast(recv), string, replace));
    DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, recv));
    return *result;
1744 1745
  }

1746
  const uint32_t length = string->length();
1747 1748 1749 1750

  Handle<Object> global_obj;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, global_obj,
1751
      JSReceiver::GetProperty(isolate, recv, factory->global_string()));
1752
  const bool global = global_obj->BooleanValue(isolate);
1753 1754 1755 1756 1757 1758

  bool unicode = false;
  if (global) {
    Handle<Object> unicode_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, unicode_obj,
1759
        JSReceiver::GetProperty(isolate, recv, factory->unicode_string()));
1760
    unicode = unicode_obj->BooleanValue(isolate);
1761 1762 1763 1764 1765

    RETURN_FAILURE_ON_EXCEPTION(isolate,
                                RegExpUtils::SetLastIndex(isolate, recv, 0));
  }

1766
  Zone zone(isolate->allocator(), ZONE_NAME);
1767 1768 1769 1770 1771
  ZoneVector<Handle<Object>> results(&zone);

  while (true) {
    Handle<Object> result;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1772 1773
        isolate, result, RegExpUtils::RegExpExec(isolate, recv, string,
                                                 factory->undefined_value()));
1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795

    if (result->IsNull(isolate)) break;

    results.push_back(result);
    if (!global) break;

    Handle<Object> match_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
                                       Object::GetElement(isolate, result, 0));

    Handle<String> match;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
                                       Object::ToString(isolate, match_obj));

    if (match->length() == 0) {
      RETURN_FAILURE_ON_EXCEPTION(isolate, RegExpUtils::SetAdvancedStringIndex(
                                               isolate, recv, string, unicode));
    }
  }

  // TODO(jgruber): Look into ReplacementStringBuilder instead.
  IncrementalStringBuilder builder(isolate);
1796
  uint32_t next_source_position = 0;
1797 1798

  for (const auto& result : results) {
1799
    HandleScope handle_scope(isolate);
1800 1801 1802
    Handle<Object> captures_length_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, captures_length_obj,
1803
        Object::GetProperty(isolate, result, factory->length_string()));
1804 1805 1806 1807

    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, captures_length_obj,
        Object::ToLength(isolate, captures_length_obj));
1808 1809
    const uint32_t captures_length =
        PositiveNumberToUint32(*captures_length_obj);
1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823

    Handle<Object> match_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
                                       Object::GetElement(isolate, result, 0));

    Handle<String> match;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
                                       Object::ToString(isolate, match_obj));

    const int match_length = match->length();

    Handle<Object> position_obj;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, position_obj,
1824
        Object::GetProperty(isolate, result, factory->index_string()));
1825 1826 1827

    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, position_obj, Object::ToInteger(isolate, position_obj));
1828 1829
    const uint32_t position =
        std::min(PositiveNumberToUint32(*position_obj), length);
1830

1831 1832
    // Do not reserve capacity since captures_length is user-controlled.
    ZoneVector<Handle<Object>> captures(&zone);
1833

1834
    for (uint32_t n = 0; n < captures_length; n++) {
1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845
      Handle<Object> capture;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, capture, Object::GetElement(isolate, result, n));

      if (!capture->IsUndefined(isolate)) {
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, capture,
                                           Object::ToString(isolate, capture));
      }
      captures.push_back(capture);
    }

1846
    Handle<Object> groups_obj = isolate->factory()->undefined_value();
1847 1848
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, groups_obj,
1849
        Object::GetProperty(isolate, result, factory->groups_string()));
1850 1851 1852

    const bool has_named_captures = !groups_obj->IsUndefined(isolate);

1853 1854
    Handle<String> replacement;
    if (functional_replace) {
1855 1856 1857 1858 1859 1860 1861
      const uint32_t argc =
          GetArgcForReplaceCallable(captures_length, has_named_captures);
      if (argc == static_cast<uint32_t>(-1)) {
        THROW_NEW_ERROR_RETURN_FAILURE(
            isolate, NewRangeError(MessageTemplate::kTooManyArguments));
      }

1862 1863
      ScopedVector<Handle<Object>> argv(argc);

1864
      int cursor = 0;
1865
      for (uint32_t j = 0; j < captures_length; j++) {
1866
        argv[cursor++] = captures[j];
1867 1868
      }

1869 1870 1871 1872 1873
      argv[cursor++] = handle(Smi::FromInt(position), isolate);
      argv[cursor++] = string;
      if (has_named_captures) argv[cursor++] = groups_obj;

      DCHECK_EQ(cursor, argc);
1874 1875 1876 1877 1878

      Handle<Object> replacement_obj;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, replacement_obj,
          Execution::Call(isolate, replace_obj, factory->undefined_value(),
1879
                          argc, argv.begin()));
1880 1881 1882 1883

      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, replacement, Object::ToString(isolate, replacement_obj));
    } else {
1884
      DCHECK(!functional_replace);
1885 1886
      if (!groups_obj->IsUndefined(isolate)) {
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1887
            isolate, groups_obj, Object::ToObject(isolate, groups_obj));
1888 1889 1890
      }
      VectorBackedMatch m(isolate, string, match, position, &captures,
                          groups_obj);
1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, replacement, String::GetSubstitution(isolate, &m, replace));
    }

    if (position >= next_source_position) {
      builder.AppendString(
          factory->NewSubString(string, next_source_position, position));
      builder.AppendString(replacement);

      next_source_position = position + match_length;
    }
  }

  if (next_source_position < length) {
    builder.AppendString(
        factory->NewSubString(string, next_source_position, length));
  }

  RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
}
1911

1912 1913
RUNTIME_FUNCTION(Runtime_RegExpInitializeAndCompile) {
  HandleScope scope(isolate);
1914
  DCHECK_EQ(3, args.length());
1915 1916 1917
  // TODO(pwong): To follow the spec more closely and simplify calling code,
  // this could handle the canonicalization of pattern and flags. See
  // https://tc39.github.io/ecma262/#sec-regexpinitialize
1918 1919 1920 1921 1922 1923 1924 1925 1926
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, source, 1);
  CONVERT_ARG_HANDLE_CHECKED(String, flags, 2);

  RETURN_FAILURE_ON_EXCEPTION(isolate,
                              JSRegExp::Initialize(regexp, source, flags));

  return *regexp;
}
1927

1928
RUNTIME_FUNCTION(Runtime_IsRegExp) {
1929
  SealHandleScope shs(isolate);
1930
  DCHECK_EQ(1, args.length());
1931
  CONVERT_ARG_CHECKED(Object, obj, 0);
1932
  return isolate->heap()->ToBoolean(obj.IsJSRegExp());
1933
}
1934

1935 1936
}  // namespace internal
}  // namespace v8