LCOV - code coverage report
Current view: top level - src/runtime - runtime-regexp.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 664 712 93.3 %
Date: 2017-04-26 Functions: 50 71 70.4 %

          Line data    Source code
       1             : // Copyright 2014 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/runtime/runtime-utils.h"
       6             : 
       7             : #include <functional>
       8             : 
       9             : #include "src/arguments.h"
      10             : #include "src/conversions-inl.h"
      11             : #include "src/isolate-inl.h"
      12             : #include "src/messages.h"
      13             : #include "src/regexp/jsregexp-inl.h"
      14             : #include "src/regexp/jsregexp.h"
      15             : #include "src/regexp/regexp-utils.h"
      16             : #include "src/string-builder.h"
      17             : #include "src/string-search.h"
      18             : 
      19             : namespace v8 {
      20             : namespace internal {
      21             : 
      22             : namespace {
      23             : 
      24             : // Looks up the capture of the given name. Returns the (1-based) numbered
      25             : // capture index or -1 on failure.
      26         168 : int LookupNamedCapture(std::function<bool(String*)> name_matches,
      27             :                        FixedArray* capture_name_map) {
      28             :   // TODO(jgruber): Sort capture_name_map and do binary search via
      29             :   // internalized strings.
      30             : 
      31             :   int maybe_capture_index = -1;
      32         168 :   const int named_capture_count = capture_name_map->length() >> 1;
      33         504 :   for (int j = 0; j < named_capture_count; j++) {
      34             :     // The format of {capture_name_map} is documented at
      35             :     // JSRegExp::kIrregexpCaptureNameMapIndex.
      36         420 :     const int name_ix = j * 2;
      37         420 :     const int index_ix = j * 2 + 1;
      38             : 
      39             :     String* capture_name = String::cast(capture_name_map->get(name_ix));
      40         420 :     if (!name_matches(capture_name)) continue;
      41             : 
      42             :     maybe_capture_index = Smi::cast(capture_name_map->get(index_ix))->value();
      43          84 :     break;
      44             :   }
      45             : 
      46         168 :   return maybe_capture_index;
      47             : }
      48             : 
      49             : }  // namespace
      50             : 
      51             : class CompiledReplacement {
      52             :  public:
      53       83981 :   explicit CompiledReplacement(Zone* zone)
      54       83981 :       : parts_(1, zone), replacement_substrings_(0, zone), zone_(zone) {}
      55             : 
      56             :   // Return whether the replacement is simple. Can also fail and return Nothing
      57             :   // if the given replacement string is invalid (and requires throwing a
      58             :   // SyntaxError).
      59             :   Maybe<bool> Compile(Handle<JSRegExp> regexp, Handle<String> replacement,
      60             :                       int capture_count, int subject_length);
      61             : 
      62             :   // Use Apply only if Compile returned false.
      63             :   void Apply(ReplacementStringBuilder* builder, int match_from, int match_to,
      64             :              int32_t* match);
      65             : 
      66             :   // Number of distinct parts of the replacement pattern.
      67       21080 :   int parts() { return parts_.length(); }
      68             : 
      69             :   Zone* zone() const { return zone_; }
      70             : 
      71             :  private:
      72             :   enum PartType {
      73             :     SUBJECT_PREFIX = 1,
      74             :     SUBJECT_SUFFIX,
      75             :     SUBJECT_CAPTURE,
      76             :     REPLACEMENT_SUBSTRING,
      77             :     REPLACEMENT_STRING,
      78             :     NUMBER_OF_PART_TYPES
      79             :   };
      80             : 
      81             :   struct ReplacementPart {
      82             :     static inline ReplacementPart SubjectMatch() {
      83             :       return ReplacementPart(SUBJECT_CAPTURE, 0);
      84             :     }
      85             :     static inline ReplacementPart SubjectCapture(int capture_index) {
      86             :       return ReplacementPart(SUBJECT_CAPTURE, capture_index);
      87             :     }
      88             :     static inline ReplacementPart SubjectPrefix() {
      89             :       return ReplacementPart(SUBJECT_PREFIX, 0);
      90             :     }
      91             :     static inline ReplacementPart SubjectSuffix(int subject_length) {
      92             :       return ReplacementPart(SUBJECT_SUFFIX, subject_length);
      93             :     }
      94             :     static inline ReplacementPart ReplacementString() {
      95             :       return ReplacementPart(REPLACEMENT_STRING, 0);
      96             :     }
      97             :     static inline ReplacementPart ReplacementSubString(int from, int to) {
      98             :       DCHECK(from >= 0);
      99             :       DCHECK(to > from);
     100        1050 :       return ReplacementPart(-from, to);
     101             :     }
     102             : 
     103             :     // If tag <= 0 then it is the negation of a start index of a substring of
     104             :     // the replacement pattern, otherwise it's a value from PartType.
     105             :     ReplacementPart(int tag, int data) : tag(tag), data(data) {
     106             :       // Must be non-positive or a PartType value.
     107             :       DCHECK(tag < NUMBER_OF_PART_TYPES);
     108             :     }
     109             :     // Either a value of PartType or a non-positive number that is
     110             :     // the negation of an index into the replacement string.
     111             :     int tag;
     112             :     // The data value's interpretation depends on the value of tag:
     113             :     // tag == SUBJECT_PREFIX ||
     114             :     // tag == SUBJECT_SUFFIX:  data is unused.
     115             :     // tag == SUBJECT_CAPTURE: data is the number of the capture.
     116             :     // tag == REPLACEMENT_SUBSTRING ||
     117             :     // tag == REPLACEMENT_STRING:    data is index into array of substrings
     118             :     //                               of the replacement string.
     119             :     // tag <= 0: Temporary representation of the substring of the replacement
     120             :     //           string ranging over -tag .. data.
     121             :     //           Is replaced by REPLACEMENT_{SUB,}STRING when we create the
     122             :     //           substring objects.
     123             :     int data;
     124             :   };
     125             : 
     126             :   template <typename Char>
     127       83981 :   Maybe<bool> ParseReplacementPattern(ZoneList<ReplacementPart>* parts,
     128             :                                       Vector<Char> characters,
     129             :                                       FixedArray* capture_name_map,
     130             :                                       int capture_count, int subject_length,
     131             :                                       Zone* zone) {
     132             :     // Equivalent to String::GetSubstitution, except that this method converts
     133             :     // the replacement string into an internal representation that avoids
     134             :     // repeated parsing when used repeatedly.
     135             :     DCHECK_IMPLIES(capture_name_map != nullptr,
     136             :                    FLAG_harmony_regexp_named_captures);
     137             : 
     138       83981 :     int length = characters.length();
     139             :     int last = 0;
     140   141821205 :     for (int i = 0; i < length; i++) {
     141   141737295 :       Char c = characters[i];
     142   141737295 :       if (c == '$') {
     143        4024 :         int next_index = i + 1;
     144        4024 :         if (next_index == length) {  // No next character!
     145             :           break;
     146             :         }
     147        4009 :         Char c2 = characters[next_index];
     148        4009 :         switch (c2) {
     149             :           case '$':
     150         120 :             if (i > last) {
     151             :               // There is a substring before. Include the first "$".
     152             :               parts->Add(
     153             :                   ReplacementPart::ReplacementSubString(last, next_index),
     154         150 :                   zone);
     155          75 :               last = next_index + 1;  // Continue after the second "$".
     156             :             } else {
     157             :               // Let the next substring start with the second "$".
     158             :               last = next_index;
     159             :             }
     160             :             i = next_index;
     161         120 :             break;
     162             :           case '`':
     163          30 :             if (i > last) {
     164          60 :               parts->Add(ReplacementPart::ReplacementSubString(last, i), zone);
     165             :             }
     166          60 :             parts->Add(ReplacementPart::SubjectPrefix(), zone);
     167             :             i = next_index;
     168          30 :             last = i + 1;
     169          30 :             break;
     170             :           case '\'':
     171          30 :             if (i > last) {
     172          60 :               parts->Add(ReplacementPart::ReplacementSubString(last, i), zone);
     173             :             }
     174          60 :             parts->Add(ReplacementPart::SubjectSuffix(subject_length), zone);
     175             :             i = next_index;
     176          30 :             last = i + 1;
     177          30 :             break;
     178             :           case '&':
     179          30 :             if (i > last) {
     180          60 :               parts->Add(ReplacementPart::ReplacementSubString(last, i), zone);
     181             :             }
     182          60 :             parts->Add(ReplacementPart::SubjectMatch(), zone);
     183             :             i = next_index;
     184          30 :             last = i + 1;
     185          30 :             break;
     186             :           case '0':
     187             :           case '1':
     188             :           case '2':
     189             :           case '3':
     190             :           case '4':
     191             :           case '5':
     192             :           case '6':
     193             :           case '7':
     194             :           case '8':
     195             :           case '9': {
     196        3686 :             int capture_ref = c2 - '0';
     197        3686 :             if (capture_ref > capture_count) {
     198             :               i = next_index;
     199             :               continue;
     200             :             }
     201        2516 :             int second_digit_index = next_index + 1;
     202        2516 :             if (second_digit_index < length) {
     203             :               // Peek ahead to see if we have two digits.
     204        2308 :               Char c3 = characters[second_digit_index];
     205        2308 :               if ('0' <= c3 && c3 <= '9') {  // Double digits.
     206        2220 :                 int double_digit_ref = capture_ref * 10 + c3 - '0';
     207        2220 :                 if (double_digit_ref <= capture_count) {
     208             :                   next_index = second_digit_index;
     209             :                   capture_ref = double_digit_ref;
     210             :                 }
     211             :               }
     212             :             }
     213        2516 :             if (capture_ref > 0) {
     214        2456 :               if (i > last) {
     215             :                 parts->Add(ReplacementPart::ReplacementSubString(last, i),
     216         180 :                            zone);
     217             :               }
     218             :               DCHECK(capture_ref <= capture_count);
     219        4912 :               parts->Add(ReplacementPart::SubjectCapture(capture_ref), zone);
     220        2456 :               last = next_index + 1;
     221             :             }
     222             :             i = next_index;
     223        2516 :             break;
     224             :           }
     225             :           case '<': {
     226          98 :             if (capture_name_map == nullptr) {
     227             :               i = next_index;
     228             :               break;
     229             :             }
     230             : 
     231             :             // Scan until the next '>', throwing a SyntaxError exception if one
     232             :             // is not found, and let the enclosed substring be groupName.
     233             : 
     234          98 :             const int name_start_index = next_index + 1;
     235             :             int closing_bracket_index = -1;
     236         392 :             for (int j = name_start_index; j < length; j++) {
     237         378 :               if (characters[j] == '>') {
     238             :                 closing_bracket_index = j;
     239             :                 break;
     240             :               }
     241             :             }
     242             : 
     243             :             // Throw a SyntaxError for invalid replacement strings.
     244          98 :             if (closing_bracket_index == -1) return Nothing<bool>();
     245             : 
     246             :             Vector<Char> requested_name =
     247             :                 characters.SubVector(name_start_index, closing_bracket_index);
     248             : 
     249             :             // Let capture be ? Get(namedCaptures, groupName).
     250             : 
     251             :             const int capture_index = LookupNamedCapture(
     252             :                 [=](String* capture_name) {
     253             :                   return capture_name->IsEqualTo(requested_name);
     254         210 :                 },
     255         168 :                 capture_name_map);
     256             : 
     257             :             // If ? HasProperty(_namedCaptures_, _groupName_) is *false*, throw
     258             :             // a *SyntaxError* exception.
     259          84 :             if (capture_index == -1) return Nothing<bool>();
     260             : 
     261             :             // If capture is undefined, replace the text through the following
     262             :             // '>' with the empty string.
     263             :             // Otherwise, replace the text through the following '>' with
     264             :             // ? ToString(capture).
     265             : 
     266             :             DCHECK(1 <= capture_index && capture_index <= capture_count);
     267             : 
     268          42 :             if (i > last) {
     269           0 :               parts->Add(ReplacementPart::ReplacementSubString(last, i), zone);
     270             :             }
     271          84 :             parts->Add(ReplacementPart::SubjectCapture(capture_index), zone);
     272          42 :             last = closing_bracket_index + 1;
     273             :             i = closing_bracket_index;
     274          42 :             break;
     275             :           }
     276             :           default:
     277             :             i = next_index;
     278             :             break;
     279             :         }
     280             :       }
     281             :     }
     282       83925 :     if (length > last) {
     283       82219 :       if (last == 0) {
     284             :         // Replacement is simple.  Do not use Apply to do the replacement.
     285             :         return Just(true);
     286             :       } else {
     287        1590 :         parts->Add(ReplacementPart::ReplacementSubString(last, length), zone);
     288             :       }
     289             :     }
     290             :     return Just(false);
     291             :   }
     292             : 
     293             :   ZoneList<ReplacementPart> parts_;
     294             :   ZoneList<Handle<String> > replacement_substrings_;
     295             :   Zone* zone_;
     296             : };
     297             : 
     298       83981 : Maybe<bool> CompiledReplacement::Compile(Handle<JSRegExp> regexp,
     299             :                                          Handle<String> replacement,
     300             :                                          int capture_count,
     301       85031 :                                          int subject_length) {
     302             :   {
     303             :     DisallowHeapAllocation no_gc;
     304       83981 :     String::FlatContent content = replacement->GetFlatContent();
     305             :     DCHECK(content.IsFlat());
     306             : 
     307             :     FixedArray* capture_name_map = nullptr;
     308       83981 :     if (capture_count > 0) {
     309             :       DCHECK_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
     310             :       Object* maybe_capture_name_map = regexp->CaptureNameMap();
     311        2828 :       if (maybe_capture_name_map->IsFixedArray()) {
     312             :         DCHECK(FLAG_harmony_regexp_named_captures);
     313             :         capture_name_map = FixedArray::cast(maybe_capture_name_map);
     314             :       }
     315             :     }
     316             : 
     317             :     Maybe<bool> simple = Nothing<bool>();
     318       83981 :     if (content.IsOneByte()) {
     319             :       simple = ParseReplacementPattern(&parts_, content.ToOneByteVector(),
     320             :                                        capture_name_map, capture_count,
     321       81203 :                                        subject_length, zone());
     322             :     } else {
     323             :       DCHECK(content.IsTwoByte());
     324             :       simple = ParseReplacementPattern(&parts_, content.ToUC16Vector(),
     325             :                                        capture_name_map, capture_count,
     326        2778 :                                        subject_length, zone());
     327             :     }
     328      167906 :     if (simple.IsNothing() || simple.FromJust()) return simple;
     329             :   }
     330             : 
     331             :   Isolate* isolate = replacement->GetIsolate();
     332             :   // Find substrings of replacement string and create them as String objects.
     333             :   int substring_index = 0;
     334        7189 :   for (int i = 0, n = parts_.length(); i < n; i++) {
     335        3638 :     int tag = parts_[i].tag;
     336        3638 :     if (tag <= 0) {  // A replacement string slice.
     337        1050 :       int from = -tag;
     338        1050 :       int to = parts_[i].data;
     339             :       replacement_substrings_.Add(
     340        2100 :           isolate->factory()->NewSubString(replacement, from, to), zone());
     341        1050 :       parts_[i].tag = REPLACEMENT_SUBSTRING;
     342        1050 :       parts_[i].data = substring_index;
     343        1050 :       substring_index++;
     344        2588 :     } else if (tag == REPLACEMENT_STRING) {
     345             :       replacement_substrings_.Add(replacement, zone());
     346           0 :       parts_[i].data = substring_index;
     347           0 :       substring_index++;
     348             :     }
     349             :   }
     350             :   return Just(false);
     351             : }
     352             : 
     353             : 
     354        2902 : void CompiledReplacement::Apply(ReplacementStringBuilder* builder,
     355             :                                 int match_from, int match_to, int32_t* match) {
     356             :   DCHECK_LT(0, parts_.length());
     357        7658 :   for (int i = 0, n = parts_.length(); i < n; i++) {
     358        4756 :     ReplacementPart part = parts_[i];
     359        4756 :     switch (part.tag) {
     360             :       case SUBJECT_PREFIX:
     361          75 :         if (match_from > 0) builder->AddSubjectSlice(0, match_from);
     362             :         break;
     363             :       case SUBJECT_SUFFIX: {
     364             :         int subject_length = part.data;
     365          75 :         if (match_to < subject_length) {
     366          60 :           builder->AddSubjectSlice(match_to, subject_length);
     367             :         }
     368             :         break;
     369             :       }
     370             :       case SUBJECT_CAPTURE: {
     371             :         int capture = part.data;
     372        2896 :         int from = match[capture * 2];
     373        2896 :         int to = match[capture * 2 + 1];
     374        2896 :         if (from >= 0 && to > from) {
     375        2763 :           builder->AddSubjectSlice(from, to);
     376             :         }
     377             :         break;
     378             :       }
     379             :       case REPLACEMENT_SUBSTRING:
     380             :       case REPLACEMENT_STRING:
     381        3420 :         builder->AddString(replacement_substrings_[part.data]);
     382        1710 :         break;
     383             :       default:
     384           0 :         UNREACHABLE();
     385             :     }
     386             :   }
     387        2902 : }
     388             : 
     389     1530299 : void FindOneByteStringIndices(Vector<const uint8_t> subject, uint8_t pattern,
     390             :                               List<int>* indices, unsigned int limit) {
     391             :   DCHECK(limit > 0);
     392             :   // Collect indices of pattern in subject using memchr.
     393             :   // Stop after finding at most limit values.
     394     1530299 :   const uint8_t* subject_start = subject.start();
     395     1530299 :   const uint8_t* subject_end = subject_start + subject.length();
     396             :   const uint8_t* pos = subject_start;
     397     4508443 :   while (limit > 0) {
     398             :     pos = reinterpret_cast<const uint8_t*>(
     399     2978099 :         memchr(pos, pattern, subject_end - pos));
     400     4508398 :     if (pos == NULL) return;
     401     1447845 :     indices->Add(static_cast<int>(pos - subject_start));
     402     1447845 :     pos++;
     403     1447845 :     limit--;
     404             :   }
     405             : }
     406             : 
     407       58860 : void FindTwoByteStringIndices(const Vector<const uc16> subject, uc16 pattern,
     408             :                               List<int>* indices, unsigned int limit) {
     409             :   DCHECK(limit > 0);
     410       58860 :   const uc16* subject_start = subject.start();
     411       58860 :   const uc16* subject_end = subject_start + subject.length();
     412     2072584 :   for (const uc16* pos = subject_start; pos < subject_end && limit > 0; pos++) {
     413     2013724 :     if (*pos == pattern) {
     414       18501 :       indices->Add(static_cast<int>(pos - subject_start));
     415       18501 :       limit--;
     416             :     }
     417             :   }
     418       58860 : }
     419             : 
     420             : template <typename SubjectChar, typename PatternChar>
     421       47013 : void FindStringIndices(Isolate* isolate, Vector<const SubjectChar> subject,
     422             :                        Vector<const PatternChar> pattern, List<int>* indices,
     423             :                        unsigned int limit) {
     424             :   DCHECK(limit > 0);
     425             :   // Collect indices of pattern in subject.
     426             :   // Stop after finding at most limit values.
     427           0 :   int pattern_length = pattern.length();
     428       47013 :   int index = 0;
     429           0 :   StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
     430       52899 :   while (limit > 0) {
     431      105798 :     index = search.Search(subject, index);
     432       99912 :     if (index < 0) return;
     433        5886 :     indices->Add(index);
     434        5886 :     index += pattern_length;
     435        5886 :     limit--;
     436             :   }
     437             : }
     438             : 
     439     1636172 : void FindStringIndicesDispatch(Isolate* isolate, String* subject,
     440             :                                String* pattern, List<int>* indices,
     441             :                                unsigned int limit) {
     442             :   {
     443             :     DisallowHeapAllocation no_gc;
     444     1636172 :     String::FlatContent subject_content = subject->GetFlatContent();
     445     1636172 :     String::FlatContent pattern_content = pattern->GetFlatContent();
     446             :     DCHECK(subject_content.IsFlat());
     447             :     DCHECK(pattern_content.IsFlat());
     448     1636172 :     if (subject_content.IsOneByte()) {
     449     1577208 :       Vector<const uint8_t> subject_vector = subject_content.ToOneByteVector();
     450     1577208 :       if (pattern_content.IsOneByte()) {
     451             :         Vector<const uint8_t> pattern_vector =
     452     1577208 :             pattern_content.ToOneByteVector();
     453     1577208 :         if (pattern_vector.length() == 1) {
     454             :           FindOneByteStringIndices(subject_vector, pattern_vector[0], indices,
     455     1530299 :                                    limit);
     456             :         } else {
     457             :           FindStringIndices(isolate, subject_vector, pattern_vector, indices,
     458       46909 :                             limit);
     459             :         }
     460             :       } else {
     461             :         FindStringIndices(isolate, subject_vector,
     462           0 :                           pattern_content.ToUC16Vector(), indices, limit);
     463             :       }
     464             :     } else {
     465       58964 :       Vector<const uc16> subject_vector = subject_content.ToUC16Vector();
     466       58964 :       if (pattern_content.IsOneByte()) {
     467             :         Vector<const uint8_t> pattern_vector =
     468       58964 :             pattern_content.ToOneByteVector();
     469       58964 :         if (pattern_vector.length() == 1) {
     470             :           FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
     471       58860 :                                    limit);
     472             :         } else {
     473             :           FindStringIndices(isolate, subject_vector, pattern_vector, indices,
     474         104 :                             limit);
     475             :         }
     476             :       } else {
     477           0 :         Vector<const uc16> pattern_vector = pattern_content.ToUC16Vector();
     478           0 :         if (pattern_vector.length() == 1) {
     479             :           FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
     480           0 :                                    limit);
     481             :         } else {
     482             :           FindStringIndices(isolate, subject_vector, pattern_vector, indices,
     483           0 :                             limit);
     484             :         }
     485             :       }
     486             :     }
     487             :   }
     488     1636172 : }
     489             : 
     490             : namespace {
     491       55704 : List<int>* GetRewoundRegexpIndicesList(Isolate* isolate) {
     492       55704 :   List<int>* list = isolate->regexp_indices();
     493             :   list->Rewind(0);
     494       55704 :   return list;
     495             : }
     496             : 
     497       55704 : void TruncateRegexpIndicesList(Isolate* isolate) {
     498             :   // Same size as smallest zone segment, preserving behavior from the
     499             :   // runtime zone.
     500             :   static const int kMaxRegexpIndicesListCapacity = 8 * KB;
     501       64929 :   if (isolate->regexp_indices()->capacity() > kMaxRegexpIndicesListCapacity) {
     502             :     isolate->regexp_indices()->Clear();  //  Throw away backing storage
     503             :   }
     504       55704 : }
     505             : }  // namespace
     506             : 
     507             : template <typename ResultSeqString>
     508     1580468 : MUST_USE_RESULT static Object* StringReplaceGlobalAtomRegExpWithString(
     509             :     Isolate* isolate, Handle<String> subject, Handle<JSRegExp> pattern_regexp,
     510             :     Handle<String> replacement, Handle<RegExpMatchInfo> last_match_info) {
     511             :   DCHECK(subject->IsFlat());
     512             :   DCHECK(replacement->IsFlat());
     513             : 
     514     3160936 :   List<int>* indices = GetRewoundRegexpIndicesList(isolate);
     515             : 
     516             :   DCHECK_EQ(JSRegExp::ATOM, pattern_regexp->TypeTag());
     517             :   String* pattern =
     518             :       String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex));
     519             :   int subject_len = subject->length();
     520             :   int pattern_len = pattern->length();
     521             :   int replacement_len = replacement->length();
     522             : 
     523     1580468 :   FindStringIndicesDispatch(isolate, *subject, pattern, indices, 0xffffffff);
     524             : 
     525             :   int matches = indices->length();
     526     3151666 :   if (matches == 0) return *subject;
     527             : 
     528             :   // Detect integer overflow.
     529             :   int64_t result_len_64 = (static_cast<int64_t>(replacement_len) -
     530             :                            static_cast<int64_t>(pattern_len)) *
     531             :                               static_cast<int64_t>(matches) +
     532        9270 :                           static_cast<int64_t>(subject_len);
     533             :   int result_len;
     534        9270 :   if (result_len_64 > static_cast<int64_t>(String::kMaxLength)) {
     535             :     STATIC_ASSERT(String::kMaxLength < kMaxInt);
     536             :     result_len = kMaxInt;  // Provoke exception.
     537             :   } else {
     538        9255 :     result_len = static_cast<int>(result_len_64);
     539             :   }
     540        9270 :   if (result_len == 0) {
     541          30 :     return isolate->heap()->empty_string();
     542             :   }
     543             : 
     544             :   int subject_pos = 0;
     545             :   int result_pos = 0;
     546             : 
     547             :   MaybeHandle<SeqString> maybe_res;
     548             :   if (ResultSeqString::kHasOneByteEncoding) {
     549       15852 :     maybe_res = isolate->factory()->NewRawOneByteString(result_len);
     550             :   } else {
     551        2628 :     maybe_res = isolate->factory()->NewRawTwoByteString(result_len);
     552             :   }
     553             :   Handle<SeqString> untyped_res;
     554        9240 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, untyped_res, maybe_res);
     555             :   Handle<ResultSeqString> result = Handle<ResultSeqString>::cast(untyped_res);
     556             : 
     557       14796 :   for (int i = 0; i < matches; i++) {
     558             :     // Copy non-matched subject content.
     559       14796 :     if (subject_pos < indices->at(i)) {
     560       26912 :       String::WriteToFlat(*subject, result->GetChars() + result_pos,
     561       13456 :                           subject_pos, indices->at(i));
     562       13456 :       result_pos += indices->at(i) - subject_pos;
     563             :     }
     564             : 
     565             :     // Replace match.
     566       14796 :     if (replacement_len > 0) {
     567       27288 :       String::WriteToFlat(*replacement, result->GetChars() + result_pos, 0,
     568       13644 :                           replacement_len);
     569       13644 :       result_pos += replacement_len;
     570             :     }
     571             : 
     572       14796 :     subject_pos = indices->at(i) + pattern_len;
     573             :   }
     574             :   // Add remaining subject content at the end.
     575        9225 :   if (subject_pos < subject_len) {
     576       15084 :     String::WriteToFlat(*subject, result->GetChars() + result_pos, subject_pos,
     577        7542 :                         subject_len);
     578             :   }
     579             : 
     580        9225 :   int32_t match_indices[] = {indices->at(matches - 1),
     581        9225 :                              indices->at(matches - 1) + pattern_len};
     582        9225 :   RegExpImpl::SetLastMatchInfo(last_match_info, subject, 0, match_indices);
     583             : 
     584             :   TruncateRegexpIndicesList(isolate);
     585             : 
     586        9225 :   return *result;
     587             : }
     588             : 
     589       84109 : MUST_USE_RESULT static Object* StringReplaceGlobalRegExpWithString(
     590       83981 :     Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
     591             :     Handle<String> replacement, Handle<RegExpMatchInfo> last_match_info) {
     592             :   DCHECK(subject->IsFlat());
     593             :   DCHECK(replacement->IsFlat());
     594             : 
     595       84109 :   int capture_count = regexp->CaptureCount();
     596             :   int subject_length = subject->length();
     597             : 
     598       84109 :   JSRegExp::Type typeTag = regexp->TypeTag();
     599       84109 :   if (typeTag == JSRegExp::IRREGEXP) {
     600             :     // Ensure the RegExp is compiled so we can access the capture-name map.
     601       11835 :     if (RegExpImpl::IrregexpPrepare(regexp, subject) == -1) {
     602             :       DCHECK(isolate->has_pending_exception());
     603         128 :       return isolate->heap()->exception();
     604             :     }
     605             :   }
     606             : 
     607             :   // CompiledReplacement uses zone allocation.
     608       83981 :   Zone zone(isolate->allocator(), ZONE_NAME);
     609       83981 :   CompiledReplacement compiled_replacement(&zone);
     610             :   Maybe<bool> maybe_simple_replace = compiled_replacement.Compile(
     611       83981 :       regexp, replacement, capture_count, subject_length);
     612       83981 :   if (maybe_simple_replace.IsNothing()) {
     613         112 :     THROW_NEW_ERROR_RETURN_FAILURE(
     614             :         isolate, NewSyntaxError(MessageTemplate::kRegExpInvalidReplaceString,
     615             :                                 replacement));
     616             :   }
     617             : 
     618             :   const bool simple_replace = maybe_simple_replace.FromJust();
     619             : 
     620             :   // Shortcut for simple non-regexp global replacements
     621       83925 :   if (typeTag == JSRegExp::ATOM && simple_replace) {
     622      142418 :     if (subject->HasOnlyOneByteChars() && replacement->HasOnlyOneByteChars()) {
     623             :       return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
     624       68621 :           isolate, subject, regexp, replacement, last_match_info);
     625             :     } else {
     626             :       return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
     627        3518 :           isolate, subject, regexp, replacement, last_match_info);
     628             :     }
     629             :   }
     630             : 
     631       11786 :   RegExpImpl::GlobalCache global_cache(regexp, subject, isolate);
     632       11786 :   if (global_cache.HasException()) return isolate->heap()->exception();
     633             : 
     634             :   int32_t* current_match = global_cache.FetchNext();
     635       11786 :   if (current_match == NULL) {
     636        1246 :     if (global_cache.HasException()) return isolate->heap()->exception();
     637        1152 :     return *subject;
     638             :   }
     639             : 
     640             :   // Guessing the number of parts that the final result string is built
     641             :   // from. Global regexps can match any number of times, so we guess
     642             :   // conservatively.
     643       10540 :   int expected_parts = (compiled_replacement.parts() + 1) * 4 + 1;
     644       10540 :   ReplacementStringBuilder builder(isolate->heap(), subject, expected_parts);
     645             : 
     646             :   // Number of parts added by compiled replacement plus preceeding
     647             :   // string and possibly suffix after last match.  It is possible for
     648             :   // all components to use two elements when encoded as two smis.
     649       10540 :   const int parts_added_per_loop = 2 * (compiled_replacement.parts() + 2);
     650             : 
     651             :   int prev = 0;
     652             : 
     653    19580296 :   do {
     654             :     builder.EnsureCapacity(parts_added_per_loop);
     655             : 
     656    19580296 :     int start = current_match[0];
     657    19580296 :     int end = current_match[1];
     658             : 
     659    19580296 :     if (prev < start) {
     660      349660 :       builder.AddSubjectSlice(prev, start);
     661             :     }
     662             : 
     663    19580296 :     if (simple_replace) {
     664    19577394 :       builder.AddString(replacement);
     665             :     } else {
     666        2902 :       compiled_replacement.Apply(&builder, start, end, current_match);
     667             :     }
     668             :     prev = end;
     669             : 
     670             :     current_match = global_cache.FetchNext();
     671             :   } while (current_match != NULL);
     672             : 
     673       10540 :   if (global_cache.HasException()) return isolate->heap()->exception();
     674             : 
     675       10540 :   if (prev < subject_length) {
     676             :     builder.EnsureCapacity(2);
     677        8455 :     builder.AddSubjectSlice(prev, subject_length);
     678             :   }
     679             : 
     680             :   RegExpImpl::SetLastMatchInfo(last_match_info, subject, capture_count,
     681       10540 :                                global_cache.LastSuccessfulMatch());
     682             : 
     683      115572 :   RETURN_RESULT_OR_FAILURE(isolate, builder.ToString());
     684             : }
     685             : 
     686             : template <typename ResultSeqString>
     687     1716142 : MUST_USE_RESULT static Object* StringReplaceGlobalRegExpWithEmptyString(
     688             :     Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
     689             :     Handle<RegExpMatchInfo> last_match_info) {
     690             :   DCHECK(subject->IsFlat());
     691             : 
     692             :   // Shortcut for simple non-regexp global replacements
     693     1716142 :   if (regexp->TypeTag() == JSRegExp::ATOM) {
     694     1508329 :     Handle<String> empty_string = isolate->factory()->empty_string();
     695     1508329 :     if (subject->IsOneByteRepresentation()) {
     696             :       return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
     697     1459656 :           isolate, subject, regexp, empty_string, last_match_info);
     698             :     } else {
     699             :       return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
     700       48673 :           isolate, subject, regexp, empty_string, last_match_info);
     701             :     }
     702             :   }
     703             : 
     704      207813 :   RegExpImpl::GlobalCache global_cache(regexp, subject, isolate);
     705      207813 :   if (global_cache.HasException()) return isolate->heap()->exception();
     706             : 
     707             :   int32_t* current_match = global_cache.FetchNext();
     708      207813 :   if (current_match == NULL) {
     709      206456 :     if (global_cache.HasException()) return isolate->heap()->exception();
     710      206441 :     return *subject;
     711             :   }
     712             : 
     713        1357 :   int start = current_match[0];
     714        1357 :   int end = current_match[1];
     715        1357 :   int capture_count = regexp->CaptureCount();
     716             :   int subject_length = subject->length();
     717             : 
     718        1357 :   int new_length = subject_length - (end - start);
     719        1357 :   if (new_length == 0) return isolate->heap()->empty_string();
     720             : 
     721             :   Handle<ResultSeqString> answer;
     722             :   if (ResultSeqString::kHasOneByteEncoding) {
     723             :     answer = Handle<ResultSeqString>::cast(
     724        1726 :         isolate->factory()->NewRawOneByteString(new_length).ToHandleChecked());
     725             :   } else {
     726             :     answer = Handle<ResultSeqString>::cast(
     727         764 :         isolate->factory()->NewRawTwoByteString(new_length).ToHandleChecked());
     728             :   }
     729             : 
     730             :   int prev = 0;
     731             :   int position = 0;
     732             : 
     733     1979897 :   do {
     734     1979897 :     start = current_match[0];
     735     1979897 :     end = current_match[1];
     736     1979897 :     if (prev < start) {
     737             :       // Add substring subject[prev;start] to answer string.
     738     3953398 :       String::WriteToFlat(*subject, answer->GetChars() + position, prev, start);
     739     1976699 :       position += start - prev;
     740             :     }
     741             :     prev = end;
     742             : 
     743             :     current_match = global_cache.FetchNext();
     744             :   } while (current_match != NULL);
     745             : 
     746        1245 :   if (global_cache.HasException()) return isolate->heap()->exception();
     747             : 
     748        1245 :   RegExpImpl::SetLastMatchInfo(last_match_info, subject, capture_count,
     749             :                                global_cache.LastSuccessfulMatch());
     750             : 
     751        1245 :   if (prev < subject_length) {
     752             :     // Add substring subject[prev;length] to answer string.
     753        1448 :     String::WriteToFlat(*subject, answer->GetChars() + position, prev,
     754         724 :                         subject_length);
     755         724 :     position += subject_length - prev;
     756             :   }
     757             : 
     758        1245 :   if (position == 0) return isolate->heap()->empty_string();
     759             : 
     760             :   // Shorten string and fill
     761             :   int string_size = ResultSeqString::SizeFor(position);
     762             :   int allocated_string_size = ResultSeqString::SizeFor(new_length);
     763         965 :   int delta = allocated_string_size - string_size;
     764             : 
     765             :   answer->set_length(position);
     766        1597 :   if (delta == 0) return *answer;
     767             : 
     768         333 :   Address end_of_string = answer->address() + string_size;
     769         333 :   Heap* heap = isolate->heap();
     770             : 
     771             :   // The trimming is performed on a newly allocated object, which is on a
     772             :   // freshly allocated page or on an already swept page. Hence, the sweeper
     773             :   // thread can not get confused with the filler creation. No synchronization
     774             :   // needed.
     775             :   // TODO(hpayer): We should shrink the large object page if the size
     776             :   // of the object changed significantly.
     777         333 :   if (!heap->lo_space()->Contains(*answer)) {
     778         318 :     heap->CreateFillerObjectAt(end_of_string, delta, ClearRecordedSlots::kNo);
     779             :   }
     780         666 :   heap->AdjustLiveBytes(*answer, -delta);
     781         333 :   return *answer;
     782             : }
     783             : 
     784             : namespace {
     785             : 
     786     1796479 : Object* StringReplaceGlobalRegExpWithStringHelper(
     787             :     Isolate* isolate, Handle<JSRegExp> regexp, Handle<String> subject,
     788             :     Handle<String> replacement, Handle<RegExpMatchInfo> last_match_info) {
     789     1796479 :   CHECK(regexp->GetFlags() & JSRegExp::kGlobal);
     790             : 
     791     1796479 :   subject = String::Flatten(subject);
     792             : 
     793     1796479 :   if (replacement->length() == 0) {
     794     1716142 :     if (subject->HasOnlyOneByteChars()) {
     795             :       return StringReplaceGlobalRegExpWithEmptyString<SeqOneByteString>(
     796     1666723 :           isolate, subject, regexp, last_match_info);
     797             :     } else {
     798             :       return StringReplaceGlobalRegExpWithEmptyString<SeqTwoByteString>(
     799       49419 :           isolate, subject, regexp, last_match_info);
     800             :     }
     801             :   }
     802             : 
     803       80337 :   replacement = String::Flatten(replacement);
     804             : 
     805             :   return StringReplaceGlobalRegExpWithString(isolate, subject, regexp,
     806       80337 :                                              replacement, last_match_info);
     807             : }
     808             : 
     809             : }  // namespace
     810             : 
     811     3558044 : RUNTIME_FUNCTION(Runtime_StringReplaceGlobalRegExpWithString) {
     812     1779022 :   HandleScope scope(isolate);
     813             :   DCHECK_EQ(4, args.length());
     814             : 
     815     3558044 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
     816     3558044 :   CONVERT_ARG_HANDLE_CHECKED(String, replacement, 2);
     817     3558044 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
     818     3558044 :   CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 3);
     819             : 
     820             :   return StringReplaceGlobalRegExpWithStringHelper(
     821     1779022 :       isolate, regexp, subject, replacement, last_match_info);
     822             : }
     823             : 
     824      145106 : RUNTIME_FUNCTION(Runtime_StringSplit) {
     825       72553 :   HandleScope handle_scope(isolate);
     826             :   DCHECK_EQ(3, args.length());
     827      145106 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
     828      145106 :   CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1);
     829      145106 :   CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]);
     830       72553 :   CHECK(limit > 0);
     831             : 
     832       72553 :   int subject_length = subject->length();
     833       72553 :   int pattern_length = pattern->length();
     834       72553 :   CHECK(pattern_length > 0);
     835             : 
     836       72553 :   if (limit == 0xffffffffu) {
     837             :     FixedArray* last_match_cache_unused;
     838             :     Handle<Object> cached_answer(
     839             :         RegExpResultsCache::Lookup(isolate->heap(), *subject, *pattern,
     840             :                                    &last_match_cache_unused,
     841             :                                    RegExpResultsCache::STRING_SPLIT_SUBSTRINGS),
     842       19227 :         isolate);
     843       19227 :     if (*cached_answer != Smi::kZero) {
     844             :       // The cache FixedArray is a COW-array and can therefore be reused.
     845             :       Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(
     846       33698 :           Handle<FixedArray>::cast(cached_answer));
     847             :       return *result;
     848             :     }
     849             :   }
     850             : 
     851             :   // The limit can be very large (0xffffffffu), but since the pattern
     852             :   // isn't empty, we can never create more parts than ~half the length
     853             :   // of the subject.
     854             : 
     855       55704 :   subject = String::Flatten(subject);
     856       55704 :   pattern = String::Flatten(pattern);
     857             : 
     858      167112 :   List<int>* indices = GetRewoundRegexpIndicesList(isolate);
     859             : 
     860       55704 :   FindStringIndicesDispatch(isolate, *subject, *pattern, indices, limit);
     861             : 
     862       55704 :   if (static_cast<uint32_t>(indices->length()) < limit) {
     863       55659 :     indices->Add(subject_length);
     864             :   }
     865             : 
     866             :   // The list indices now contains the end of each part to create.
     867             : 
     868             :   // Create JSArray of substrings separated by separator.
     869             :   int part_count = indices->length();
     870             : 
     871             :   Handle<JSArray> result =
     872             :       isolate->factory()->NewJSArray(FAST_ELEMENTS, part_count, part_count,
     873       55704 :                                      INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
     874             : 
     875             :   DCHECK(result->HasFastObjectElements());
     876             : 
     877       55704 :   Handle<FixedArray> elements(FixedArray::cast(result->elements()));
     878             : 
     879       55704 :   if (part_count == 1 && indices->at(0) == subject_length) {
     880       38804 :     elements->set(0, *subject);
     881             :   } else {
     882             :     int part_start = 0;
     883      508165 :     FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < part_count, i++, {
     884             :       int part_end = indices->at(i);
     885             :       Handle<String> substring =
     886             :           isolate->factory()->NewProperSubString(subject, part_start, part_end);
     887             :       elements->set(i, *substring);
     888             :       part_start = part_end + pattern_length;
     889             :     });
     890             :   }
     891             : 
     892       55704 :   if (limit == 0xffffffffu) {
     893        2378 :     if (result->HasFastObjectElements()) {
     894             :       RegExpResultsCache::Enter(isolate, subject, pattern, elements,
     895             :                                 isolate->factory()->empty_fixed_array(),
     896        4756 :                                 RegExpResultsCache::STRING_SPLIT_SUBSTRINGS);
     897             :     }
     898             :   }
     899             : 
     900       55704 :   TruncateRegexpIndicesList(isolate);
     901             : 
     902       72553 :   return *result;
     903             : }
     904             : 
     905             : // ES##sec-regexpcreate
     906             : // RegExpCreate ( P, F )
     907        3256 : RUNTIME_FUNCTION(Runtime_RegExpCreate) {
     908        1628 :   HandleScope scope(isolate);
     909             :   DCHECK_EQ(1, args.length());
     910        1628 :   CONVERT_ARG_HANDLE_CHECKED(Object, source_object, 0);
     911             : 
     912             :   Handle<String> source;
     913        1628 :   if (source_object->IsUndefined(isolate)) {
     914          30 :     source = isolate->factory()->empty_string();
     915             :   } else {
     916        3196 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
     917             :         isolate, source, Object::ToString(isolate, source_object));
     918             :   }
     919             : 
     920        4884 :   Handle<Map> map(isolate->regexp_function()->initial_map());
     921             :   Handle<JSRegExp> regexp =
     922        1628 :       Handle<JSRegExp>::cast(isolate->factory()->NewJSObjectFromMap(map));
     923             : 
     924        1628 :   JSRegExp::Flags flags = JSRegExp::kNone;
     925             : 
     926        1628 :   RETURN_FAILURE_ON_EXCEPTION(isolate,
     927             :                               JSRegExp::Initialize(regexp, source, flags));
     928             : 
     929        1628 :   return *regexp;
     930             : }
     931             : 
     932     1774050 : RUNTIME_FUNCTION(Runtime_RegExpExec) {
     933      591350 :   HandleScope scope(isolate);
     934             :   DCHECK_EQ(4, args.length());
     935     1182700 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
     936     1182700 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
     937     1182700 :   CONVERT_INT32_ARG_CHECKED(index, 2);
     938     1182700 :   CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 3);
     939             :   // Due to the way the JS calls are constructed this must be less than the
     940             :   // length of a string, i.e. it is always a Smi.  We check anyway for security.
     941      591350 :   CHECK(index >= 0);
     942      591350 :   CHECK(index <= subject->length());
     943      591350 :   isolate->counters()->regexp_entry_runtime()->Increment();
     944     1182700 :   RETURN_RESULT_OR_FAILURE(
     945      591350 :       isolate, RegExpImpl::Exec(regexp, subject, index, last_match_info));
     946             : }
     947             : 
     948       34914 : RUNTIME_FUNCTION(Runtime_RegExpInternalReplace) {
     949       17457 :   HandleScope scope(isolate);
     950             :   DCHECK_EQ(3, args.length());
     951       34914 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
     952       34914 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
     953       34914 :   CONVERT_ARG_HANDLE_CHECKED(String, replacement, 2);
     954             : 
     955             :   Handle<RegExpMatchInfo> internal_match_info =
     956       17457 :       isolate->regexp_internal_match_info();
     957             : 
     958             :   return StringReplaceGlobalRegExpWithStringHelper(
     959       17457 :       isolate, regexp, subject, replacement, internal_match_info);
     960             : }
     961             : 
     962             : namespace {
     963             : 
     964        4976 : class MatchInfoBackedMatch : public String::Match {
     965             :  public:
     966        5032 :   MatchInfoBackedMatch(Isolate* isolate, Handle<JSRegExp> regexp,
     967             :                        Handle<String> subject,
     968             :                        Handle<RegExpMatchInfo> match_info)
     969       10064 :       : isolate_(isolate), match_info_(match_info) {
     970        5032 :     subject_ = String::Flatten(subject);
     971             : 
     972        5032 :     if (regexp->TypeTag() == JSRegExp::IRREGEXP) {
     973             :       Object* o = regexp->CaptureNameMap();
     974        4852 :       has_named_captures_ = o->IsFixedArray();
     975        4852 :       if (has_named_captures_) {
     976             :         DCHECK(FLAG_harmony_regexp_named_captures);
     977          98 :         capture_name_map_ = handle(FixedArray::cast(o));
     978             :       }
     979             :     } else {
     980         180 :       has_named_captures_ = false;
     981             :     }
     982        5032 :   }
     983             : 
     984          30 :   Handle<String> GetMatch() override {
     985          30 :     return RegExpUtils::GenericCaptureGetter(isolate_, match_info_, 0, nullptr);
     986             :   }
     987             : 
     988          30 :   Handle<String> GetPrefix() override {
     989             :     const int match_start = match_info_->Capture(0);
     990          30 :     return isolate_->factory()->NewSubString(subject_, 0, match_start);
     991             :   }
     992             : 
     993          30 :   Handle<String> GetSuffix() override {
     994             :     const int match_end = match_info_->Capture(1);
     995             :     return isolate_->factory()->NewSubString(subject_, match_end,
     996          30 :                                              subject_->length());
     997             :   }
     998             : 
     999         182 :   bool HasNamedCaptures() override { return has_named_captures_; }
    1000             : 
    1001        5032 :   int CaptureCount() override {
    1002        5032 :     return match_info_->NumberOfCaptureRegisters() / 2;
    1003             :   }
    1004             : 
    1005       11486 :   MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
    1006             :     Handle<Object> capture_obj = RegExpUtils::GenericCaptureGetter(
    1007       11486 :         isolate_, match_info_, i, capture_exists);
    1008             :     return (*capture_exists) ? Object::ToString(isolate_, capture_obj)
    1009       22972 :                              : isolate_->factory()->empty_string();
    1010             :   }
    1011             : 
    1012          84 :   MaybeHandle<String> GetNamedCapture(Handle<String> name,
    1013             :                                       CaptureState* state) override {
    1014             :     DCHECK(has_named_captures_);
    1015             :     const int capture_index = LookupNamedCapture(
    1016         210 :         [=](String* capture_name) { return capture_name->Equals(*name); },
    1017         252 :         *capture_name_map_);
    1018             : 
    1019          84 :     if (capture_index == -1) {
    1020          42 :       *state = INVALID;
    1021             :       return name;  // Arbitrary string handle.
    1022             :     }
    1023             : 
    1024             :     DCHECK(1 <= capture_index && capture_index <= CaptureCount());
    1025             : 
    1026             :     bool capture_exists;
    1027             :     Handle<String> capture_value;
    1028          84 :     ASSIGN_RETURN_ON_EXCEPTION(isolate_, capture_value,
    1029             :                                GetCapture(capture_index, &capture_exists),
    1030             :                                String);
    1031             : 
    1032          42 :     if (!capture_exists) {
    1033          14 :       *state = UNMATCHED;
    1034          14 :       return isolate_->factory()->empty_string();
    1035             :     } else {
    1036          28 :       *state = MATCHED;
    1037             :       return capture_value;
    1038             :     }
    1039             :   }
    1040             : 
    1041             :  private:
    1042             :   Isolate* isolate_;
    1043             :   Handle<String> subject_;
    1044             :   Handle<RegExpMatchInfo> match_info_;
    1045             : 
    1046             :   bool has_named_captures_;
    1047             :   Handle<FixedArray> capture_name_map_;
    1048             : };
    1049             : 
    1050         626 : class VectorBackedMatch : public String::Match {
    1051             :  public:
    1052         313 :   VectorBackedMatch(Isolate* isolate, Handle<String> subject,
    1053             :                     Handle<String> match, int match_position,
    1054             :                     ZoneVector<Handle<Object>>* captures,
    1055             :                     Handle<Object> groups_obj)
    1056             :       : isolate_(isolate),
    1057             :         match_(match),
    1058             :         match_position_(match_position),
    1059         626 :         captures_(captures) {
    1060         313 :     subject_ = String::Flatten(subject);
    1061             : 
    1062             :     DCHECK(groups_obj->IsUndefined(isolate) || groups_obj->IsJSReceiver());
    1063         313 :     has_named_captures_ = !groups_obj->IsUndefined(isolate);
    1064         313 :     if (has_named_captures_) groups_obj_ = Handle<JSReceiver>::cast(groups_obj);
    1065         313 :   }
    1066             : 
    1067           0 :   Handle<String> GetMatch() override { return match_; }
    1068             : 
    1069           0 :   Handle<String> GetPrefix() override {
    1070           0 :     return isolate_->factory()->NewSubString(subject_, 0, match_position_);
    1071             :   }
    1072             : 
    1073           0 :   Handle<String> GetSuffix() override {
    1074           0 :     const int match_end_position = match_position_ + match_->length();
    1075             :     return isolate_->factory()->NewSubString(subject_, match_end_position,
    1076           0 :                                              subject_->length());
    1077             :   }
    1078             : 
    1079         238 :   bool HasNamedCaptures() override { return has_named_captures_; }
    1080             : 
    1081         626 :   int CaptureCount() override { return static_cast<int>(captures_->size()); }
    1082             : 
    1083          84 :   MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
    1084         168 :     Handle<Object> capture_obj = captures_->at(i);
    1085         168 :     if (capture_obj->IsUndefined(isolate_)) {
    1086           0 :       *capture_exists = false;
    1087           0 :       return isolate_->factory()->empty_string();
    1088             :     }
    1089          84 :     *capture_exists = true;
    1090          84 :     return Object::ToString(isolate_, capture_obj);
    1091             :   }
    1092             : 
    1093         210 :   MaybeHandle<String> GetNamedCapture(Handle<String> name,
    1094             :                                       CaptureState* state) override {
    1095             :     DCHECK(has_named_captures_);
    1096             : 
    1097             :     Maybe<bool> maybe_capture_exists =
    1098         210 :         JSReceiver::HasProperty(groups_obj_, name);
    1099         210 :     if (maybe_capture_exists.IsNothing()) return MaybeHandle<String>();
    1100             : 
    1101         210 :     if (!maybe_capture_exists.FromJust()) {
    1102          84 :       *state = INVALID;
    1103             :       return name;  // Arbitrary string handle.
    1104             :     }
    1105             : 
    1106             :     Handle<Object> capture_obj;
    1107         252 :     ASSIGN_RETURN_ON_EXCEPTION(isolate_, capture_obj,
    1108             :                                Object::GetProperty(groups_obj_, name), String);
    1109         252 :     if (capture_obj->IsUndefined(isolate_)) {
    1110          42 :       *state = UNMATCHED;
    1111          42 :       return isolate_->factory()->empty_string();
    1112             :     } else {
    1113          84 :       *state = MATCHED;
    1114          84 :       return Object::ToString(isolate_, capture_obj);
    1115             :     }
    1116             :   }
    1117             : 
    1118             :  private:
    1119             :   Isolate* isolate_;
    1120             :   Handle<String> subject_;
    1121             :   Handle<String> match_;
    1122             :   const int match_position_;
    1123             :   ZoneVector<Handle<Object>>* captures_;
    1124             : 
    1125             :   bool has_named_captures_;
    1126             :   Handle<JSReceiver> groups_obj_;
    1127             : };
    1128             : 
    1129             : // Create the groups object (see also the RegExp result creation in
    1130             : // RegExpBuiltinsAssembler::ConstructNewResultFromMatchInfo).
    1131         112 : Handle<JSObject> ConstructNamedCaptureGroupsObject(
    1132             :     Isolate* isolate, Handle<FixedArray> capture_map,
    1133             :     std::function<Object*(int)> f_get_capture) {
    1134             :   DCHECK(FLAG_harmony_regexp_named_captures);
    1135         112 :   Handle<JSObject> groups = isolate->factory()->NewJSObjectWithNullProto();
    1136             : 
    1137         112 :   const int capture_count = capture_map->length() >> 1;
    1138         336 :   for (int i = 0; i < capture_count; i++) {
    1139         224 :     const int name_ix = i * 2;
    1140         224 :     const int index_ix = i * 2 + 1;
    1141             : 
    1142             :     Handle<String> capture_name(String::cast(capture_map->get(name_ix)));
    1143             :     const int capture_ix = Smi::cast(capture_map->get(index_ix))->value();
    1144             :     DCHECK(1 <= capture_ix && capture_ix <= capture_count);
    1145             : 
    1146         224 :     Handle<Object> capture_value(f_get_capture(capture_ix), isolate);
    1147             :     DCHECK(capture_value->IsUndefined(isolate) || capture_value->IsString());
    1148             : 
    1149         224 :     JSObject::AddProperty(groups, capture_name, capture_value, NONE);
    1150             :   }
    1151             : 
    1152         112 :   return groups;
    1153             : }
    1154             : 
    1155             : // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
    1156             : // separate last match info.  See comment on that function.
    1157             : template <bool has_capture>
    1158      141405 : static Object* SearchRegExpMultiple(Isolate* isolate, Handle<String> subject,
    1159             :                                     Handle<JSRegExp> regexp,
    1160             :                                     Handle<RegExpMatchInfo> last_match_array,
    1161             :                                     Handle<JSArray> result_array) {
    1162             :   DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
    1163             :   DCHECK_NE(has_capture, regexp->CaptureCount() == 0);
    1164             :   DCHECK(subject->IsFlat());
    1165             : 
    1166      141405 :   int capture_count = regexp->CaptureCount();
    1167             :   int subject_length = subject->length();
    1168             : 
    1169             :   static const int kMinLengthToCache = 0x1000;
    1170             : 
    1171      141405 :   if (subject_length > kMinLengthToCache) {
    1172             :     FixedArray* last_match_cache;
    1173             :     Object* cached_answer = RegExpResultsCache::Lookup(
    1174             :         isolate->heap(), *subject, regexp->data(), &last_match_cache,
    1175          60 :         RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
    1176          60 :     if (cached_answer->IsFixedArray()) {
    1177           0 :       int capture_registers = (capture_count + 1) * 2;
    1178           0 :       int32_t* last_match = NewArray<int32_t>(capture_registers);
    1179           0 :       for (int i = 0; i < capture_registers; i++) {
    1180           0 :         last_match[i] = Smi::cast(last_match_cache->get(i))->value();
    1181             :       }
    1182             :       Handle<FixedArray> cached_fixed_array =
    1183             :           Handle<FixedArray>(FixedArray::cast(cached_answer));
    1184             :       // The cache FixedArray is a COW-array and we need to return a copy.
    1185             :       Handle<FixedArray> copied_fixed_array =
    1186             :           isolate->factory()->CopyFixedArrayWithMap(
    1187           0 :               cached_fixed_array, isolate->factory()->fixed_array_map());
    1188           0 :       JSArray::SetContent(result_array, copied_fixed_array);
    1189           0 :       RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count,
    1190             :                                    last_match);
    1191             :       DeleteArray(last_match);
    1192             :       return *result_array;
    1193             :     }
    1194             :   }
    1195             : 
    1196      141405 :   RegExpImpl::GlobalCache global_cache(regexp, subject, isolate);
    1197      141405 :   if (global_cache.HasException()) return isolate->heap()->exception();
    1198             : 
    1199             :   // Ensured in Runtime_RegExpExecMultiple.
    1200             :   DCHECK(result_array->HasFastObjectElements());
    1201             :   Handle<FixedArray> result_elements(
    1202             :       FixedArray::cast(result_array->elements()));
    1203      141288 :   if (result_elements->length() < 16) {
    1204           0 :     result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
    1205             :   }
    1206             : 
    1207             :   FixedArrayBuilder builder(result_elements);
    1208             : 
    1209             :   // Position to search from.
    1210             :   int match_start = -1;
    1211             :   int match_end = 0;
    1212             :   bool first = true;
    1213             : 
    1214             :   // Two smis before and after the match, for very long strings.
    1215             :   static const int kMaxBuilderEntriesPerRegExpMatch = 5;
    1216             : 
    1217             :   while (true) {
    1218             :     int32_t* current_match = global_cache.FetchNext();
    1219      731799 :     if (current_match == NULL) break;
    1220      590511 :     match_start = current_match[0];
    1221      590511 :     builder.EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
    1222      590511 :     if (match_end < match_start) {
    1223       95834 :       ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
    1224             :                                                 match_start);
    1225             :     }
    1226      590511 :     match_end = current_match[1];
    1227             :     {
    1228             :       // Avoid accumulating new handles inside loop.
    1229             :       HandleScope temp_scope(isolate);
    1230             :       Handle<String> match;
    1231      590511 :       if (!first) {
    1232      449321 :         match = isolate->factory()->NewProperSubString(subject, match_start,
    1233             :                                                        match_end);
    1234             :       } else {
    1235      141190 :         match =
    1236             :             isolate->factory()->NewSubString(subject, match_start, match_end);
    1237             :         first = false;
    1238             :       }
    1239             : 
    1240             :       if (has_capture) {
    1241             :         // Arguments array to replace function is match, captures, index and
    1242             :         // subject, i.e., 3 + capture count in total. If the RegExp contains
    1243             :         // named captures, they are also passed as the last argument.
    1244             : 
    1245             :         Handle<Object> maybe_capture_map(regexp->CaptureNameMap(), isolate);
    1246             :         const bool has_named_captures = maybe_capture_map->IsFixedArray();
    1247             :         DCHECK_IMPLIES(has_named_captures, FLAG_harmony_regexp_named_captures);
    1248             : 
    1249             :         const int argc =
    1250      282419 :             has_named_captures ? 4 + capture_count : 3 + capture_count;
    1251             : 
    1252      282419 :         Handle<FixedArray> elements = isolate->factory()->NewFixedArray(argc);
    1253             :         int cursor = 0;
    1254             : 
    1255      282419 :         elements->set(cursor++, *match);
    1256      829569 :         for (int i = 1; i <= capture_count; i++) {
    1257      547150 :           int start = current_match[i * 2];
    1258      547150 :           if (start >= 0) {
    1259      547019 :             int end = current_match[i * 2 + 1];
    1260             :             DCHECK(start <= end);
    1261             :             Handle<String> substring =
    1262      547019 :                 isolate->factory()->NewSubString(subject, start, end);
    1263     1094038 :             elements->set(cursor++, *substring);
    1264             :           } else {
    1265             :             DCHECK(current_match[i * 2 + 1] < 0);
    1266         262 :             elements->set(cursor++, isolate->heap()->undefined_value());
    1267             :           }
    1268             :         }
    1269             : 
    1270      282419 :         elements->set(cursor++, Smi::FromInt(match_start));
    1271      282419 :         elements->set(cursor++, *subject);
    1272             : 
    1273      282419 :         if (has_named_captures) {
    1274             :           Handle<FixedArray> capture_map =
    1275          84 :               Handle<FixedArray>::cast(maybe_capture_map);
    1276             :           Handle<JSObject> groups = ConstructNamedCaptureGroupsObject(
    1277         168 :               isolate, capture_map, [=](int ix) { return elements->get(ix); });
    1278          84 :           elements->set(cursor++, *groups);
    1279             :         }
    1280             : 
    1281             :         DCHECK_EQ(cursor, argc);
    1282      282419 :         builder.Add(*isolate->factory()->NewJSArrayWithElements(elements));
    1283             :       } else {
    1284      308092 :         builder.Add(*match);
    1285             :       }
    1286             :     }
    1287             :   }
    1288             : 
    1289      141288 :   if (global_cache.HasException()) return isolate->heap()->exception();
    1290             : 
    1291      141209 :   if (match_start >= 0) {
    1292             :     // Finished matching, with at least one match.
    1293      141190 :     if (match_end < subject_length) {
    1294         583 :       ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
    1295             :                                                 subject_length);
    1296             :     }
    1297             : 
    1298      141190 :     RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count,
    1299             :                                  global_cache.LastSuccessfulMatch());
    1300             : 
    1301      141190 :     if (subject_length > kMinLengthToCache) {
    1302             :       // Store the last successful match into the array for caching.
    1303             :       // TODO(yangguo): do not expose last match to JS and simplify caching.
    1304          60 :       int capture_registers = (capture_count + 1) * 2;
    1305             :       Handle<FixedArray> last_match_cache =
    1306          60 :           isolate->factory()->NewFixedArray(capture_registers);
    1307             :       int32_t* last_match = global_cache.LastSuccessfulMatch();
    1308         270 :       for (int i = 0; i < capture_registers; i++) {
    1309         210 :         last_match_cache->set(i, Smi::FromInt(last_match[i]));
    1310             :       }
    1311             :       Handle<FixedArray> result_fixed_array = builder.array();
    1312         120 :       result_fixed_array->Shrink(builder.length());
    1313             :       // Cache the result and copy the FixedArray into a COW array.
    1314             :       Handle<FixedArray> copied_fixed_array =
    1315             :           isolate->factory()->CopyFixedArrayWithMap(
    1316          60 :               result_fixed_array, isolate->factory()->fixed_array_map());
    1317          60 :       RegExpResultsCache::Enter(
    1318             :           isolate, subject, handle(regexp->data(), isolate), copied_fixed_array,
    1319             :           last_match_cache, RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
    1320             :     }
    1321      282380 :     return *builder.ToJSArray(result_array);
    1322             :   } else {
    1323          19 :     return isolate->heap()->null_value();  // No matches at all.
    1324             :   }
    1325             : }
    1326             : 
    1327             : // Legacy implementation of RegExp.prototype[Symbol.replace] which
    1328             : // doesn't properly call the underlying exec method.
    1329        8818 : MUST_USE_RESULT MaybeHandle<String> RegExpReplace(Isolate* isolate,
    1330             :                                                   Handle<JSRegExp> regexp,
    1331             :                                                   Handle<String> string,
    1332             :                                                   Handle<Object> replace_obj) {
    1333             :   // Functional fast-paths are dispatched directly by replace builtin.
    1334             :   DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
    1335             :   DCHECK(!replace_obj->IsCallable());
    1336             : 
    1337             :   Factory* factory = isolate->factory();
    1338             : 
    1339             :   const int flags = regexp->GetFlags();
    1340        8818 :   const bool global = (flags & JSRegExp::kGlobal) != 0;
    1341        8818 :   const bool sticky = (flags & JSRegExp::kSticky) != 0;
    1342             : 
    1343             :   Handle<String> replace;
    1344       17636 :   ASSIGN_RETURN_ON_EXCEPTION(isolate, replace,
    1345             :                              Object::ToString(isolate, replace_obj), String);
    1346        8818 :   replace = String::Flatten(replace);
    1347             : 
    1348        8818 :   Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();
    1349             : 
    1350        8818 :   if (!global) {
    1351             :     // Non-global regexp search, string replace.
    1352             : 
    1353             :     uint32_t last_index = 0;
    1354        5046 :     if (sticky) {
    1355             :       Handle<Object> last_index_obj(regexp->LastIndex(), isolate);
    1356           0 :       ASSIGN_RETURN_ON_EXCEPTION(isolate, last_index_obj,
    1357             :                                  Object::ToLength(isolate, last_index_obj),
    1358             :                                  String);
    1359           0 :       last_index = PositiveNumberToUint32(*last_index_obj);
    1360             : 
    1361           0 :       if (static_cast<int>(last_index) > string->length()) last_index = 0;
    1362             :     }
    1363             : 
    1364             :     Handle<Object> match_indices_obj;
    1365       10092 :     ASSIGN_RETURN_ON_EXCEPTION(
    1366             :         isolate, match_indices_obj,
    1367             :         RegExpImpl::Exec(regexp, string, last_index, last_match_info), String);
    1368             : 
    1369        5046 :     if (match_indices_obj->IsNull(isolate)) {
    1370          14 :       if (sticky) regexp->SetLastIndex(0);
    1371             :       return string;
    1372             :     }
    1373             : 
    1374             :     auto match_indices = Handle<RegExpMatchInfo>::cast(match_indices_obj);
    1375             : 
    1376             :     const int start_index = match_indices->Capture(0);
    1377             :     const int end_index = match_indices->Capture(1);
    1378             : 
    1379        5032 :     if (sticky) regexp->SetLastIndex(end_index);
    1380             : 
    1381        5032 :     IncrementalStringBuilder builder(isolate);
    1382        5032 :     builder.AppendString(factory->NewSubString(string, 0, start_index));
    1383             : 
    1384        5032 :     if (replace->length() > 0) {
    1385        5032 :       MatchInfoBackedMatch m(isolate, regexp, string, match_indices);
    1386             :       Handle<String> replacement;
    1387       10064 :       ASSIGN_RETURN_ON_EXCEPTION(isolate, replacement,
    1388             :                                  String::GetSubstitution(isolate, &m, replace),
    1389             :                                  String);
    1390        4976 :       builder.AppendString(replacement);
    1391             :     }
    1392             : 
    1393             :     builder.AppendString(
    1394        4976 :         factory->NewSubString(string, end_index, string->length()));
    1395        4976 :     return builder.Finish();
    1396             :   } else {
    1397             :     // Global regexp search, string replace.
    1398             :     DCHECK(global);
    1399        7544 :     RETURN_ON_EXCEPTION(isolate, RegExpUtils::SetLastIndex(isolate, regexp, 0),
    1400             :                         String);
    1401             : 
    1402        3772 :     if (replace->length() == 0) {
    1403           0 :       if (string->HasOnlyOneByteChars()) {
    1404             :         Object* result =
    1405             :             StringReplaceGlobalRegExpWithEmptyString<SeqOneByteString>(
    1406           0 :                 isolate, string, regexp, last_match_info);
    1407             :         return handle(String::cast(result), isolate);
    1408             :       } else {
    1409             :         Object* result =
    1410             :             StringReplaceGlobalRegExpWithEmptyString<SeqTwoByteString>(
    1411           0 :                 isolate, string, regexp, last_match_info);
    1412             :         return handle(String::cast(result), isolate);
    1413             :       }
    1414             :     }
    1415             : 
    1416             :     Object* result = StringReplaceGlobalRegExpWithString(
    1417        3772 :         isolate, string, regexp, replace, last_match_info);
    1418        3772 :     if (result->IsString()) {
    1419             :       return handle(String::cast(result), isolate);
    1420             :     } else {
    1421             :       return MaybeHandle<String>();
    1422             :     }
    1423             :   }
    1424             : 
    1425             :   UNREACHABLE();
    1426             :   return MaybeHandle<String>();
    1427             : }
    1428             : 
    1429             : }  // namespace
    1430             : 
    1431             : // This is only called for StringReplaceGlobalRegExpWithFunction.
    1432      282810 : RUNTIME_FUNCTION(Runtime_RegExpExecMultiple) {
    1433      141405 :   HandleScope handles(isolate);
    1434             :   DCHECK_EQ(4, args.length());
    1435             : 
    1436      282810 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
    1437      282810 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
    1438      282810 :   CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 2);
    1439      282810 :   CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);
    1440      141405 :   CHECK(result_array->HasFastObjectElements());
    1441             : 
    1442      141405 :   subject = String::Flatten(subject);
    1443      141405 :   CHECK(regexp->GetFlags() & JSRegExp::kGlobal);
    1444             : 
    1445      141405 :   if (regexp->CaptureCount() == 0) {
    1446             :     return SearchRegExpMultiple<false>(isolate, subject, regexp,
    1447      140395 :                                        last_match_info, result_array);
    1448             :   } else {
    1449             :     return SearchRegExpMultiple<true>(isolate, subject, regexp, last_match_info,
    1450        1010 :                                       result_array);
    1451      141405 :   }
    1452             : }
    1453             : 
    1454       29414 : RUNTIME_FUNCTION(Runtime_StringReplaceNonGlobalRegExpWithFunction) {
    1455       14707 :   HandleScope scope(isolate);
    1456             :   DCHECK_EQ(3, args.length());
    1457       29414 :   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
    1458       29414 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
    1459       29414 :   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, replace_obj, 2);
    1460             : 
    1461             :   DCHECK(RegExpUtils::IsUnmodifiedRegExp(isolate, regexp));
    1462             :   DCHECK(replace_obj->map()->is_callable());
    1463             : 
    1464       14707 :   Factory* factory = isolate->factory();
    1465       14707 :   Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();
    1466             : 
    1467       14707 :   const int flags = regexp->GetFlags();
    1468             :   DCHECK_EQ(flags & JSRegExp::kGlobal, 0);
    1469             : 
    1470             :   // TODO(jgruber): This should be an easy port to CSA with massive payback.
    1471             : 
    1472       14707 :   const bool sticky = (flags & JSRegExp::kSticky) != 0;
    1473             :   uint32_t last_index = 0;
    1474       14707 :   if (sticky) {
    1475           0 :     Handle<Object> last_index_obj(regexp->LastIndex(), isolate);
    1476           0 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1477             :         isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));
    1478           0 :     last_index = PositiveNumberToUint32(*last_index_obj);
    1479             : 
    1480           0 :     if (static_cast<int>(last_index) > subject->length()) last_index = 0;
    1481             :   }
    1482             : 
    1483             :   Handle<Object> match_indices_obj;
    1484       29414 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1485             :       isolate, match_indices_obj,
    1486             :       RegExpImpl::Exec(regexp, subject, last_index, last_match_info));
    1487             : 
    1488       14692 :   if (match_indices_obj->IsNull(isolate)) {
    1489       14247 :     if (sticky) regexp->SetLastIndex(0);
    1490             :     return *subject;
    1491             :   }
    1492             : 
    1493             :   Handle<RegExpMatchInfo> match_indices =
    1494         445 :       Handle<RegExpMatchInfo>::cast(match_indices_obj);
    1495             : 
    1496         445 :   const int index = match_indices->Capture(0);
    1497         445 :   const int end_of_match = match_indices->Capture(1);
    1498             : 
    1499         445 :   if (sticky) regexp->SetLastIndex(end_of_match);
    1500             : 
    1501         445 :   IncrementalStringBuilder builder(isolate);
    1502         445 :   builder.AppendString(factory->NewSubString(subject, 0, index));
    1503             : 
    1504             :   // Compute the parameter list consisting of the match, captures, index,
    1505             :   // and subject for the replace function invocation. If the RegExp contains
    1506             :   // named captures, they are also passed as the last argument.
    1507             : 
    1508             :   // The number of captures plus one for the match.
    1509         445 :   const int m = match_indices->NumberOfCaptureRegisters() / 2;
    1510             : 
    1511             :   bool has_named_captures = false;
    1512             :   Handle<FixedArray> capture_map;
    1513         445 :   if (m > 1) {
    1514             :     // The existence of capture groups implies IRREGEXP kind.
    1515             :     DCHECK_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
    1516             : 
    1517         173 :     Object* maybe_capture_map = regexp->CaptureNameMap();
    1518         173 :     if (maybe_capture_map->IsFixedArray()) {
    1519             :       has_named_captures = true;
    1520          28 :       capture_map = handle(FixedArray::cast(maybe_capture_map));
    1521             :     }
    1522             :   }
    1523             : 
    1524             :   DCHECK_IMPLIES(has_named_captures, FLAG_harmony_regexp_named_captures);
    1525         445 :   const int argc = has_named_captures ? m + 3 : m + 2;
    1526         890 :   ScopedVector<Handle<Object>> argv(argc);
    1527             : 
    1528             :   int cursor = 0;
    1529         689 :   for (int j = 0; j < m; j++) {
    1530             :     bool ok;
    1531             :     Handle<String> capture =
    1532         689 :         RegExpUtils::GenericCaptureGetter(isolate, match_indices, j, &ok);
    1533         689 :     if (ok) {
    1534         574 :       argv[cursor++] = capture;
    1535             :     } else {
    1536         115 :       argv[cursor++] = factory->undefined_value();
    1537             :     }
    1538             :   }
    1539             : 
    1540         890 :   argv[cursor++] = handle(Smi::FromInt(index), isolate);
    1541         445 :   argv[cursor++] = subject;
    1542             : 
    1543         445 :   if (has_named_captures) {
    1544          28 :     argv[cursor++] = ConstructNamedCaptureGroupsObject(
    1545          84 :         isolate, capture_map, [&argv](int ix) { return *argv[ix]; });
    1546             :   }
    1547             : 
    1548             :   DCHECK_EQ(cursor, argc);
    1549             : 
    1550             :   Handle<Object> replacement_obj;
    1551        1335 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1552             :       isolate, replacement_obj,
    1553             :       Execution::Call(isolate, replace_obj, factory->undefined_value(), argc,
    1554             :                       argv.start()));
    1555             : 
    1556             :   Handle<String> replacement;
    1557         890 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1558             :       isolate, replacement, Object::ToString(isolate, replacement_obj));
    1559             : 
    1560         445 :   builder.AppendString(replacement);
    1561             :   builder.AppendString(
    1562         445 :       factory->NewSubString(subject, end_of_match, subject->length()));
    1563             : 
    1564       15597 :   RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
    1565             : }
    1566             : 
    1567             : namespace {
    1568             : 
    1569          60 : MUST_USE_RESULT MaybeHandle<Object> ToUint32(Isolate* isolate,
    1570             :                                              Handle<Object> object,
    1571             :                                              uint32_t* out) {
    1572          60 :   if (object->IsUndefined(isolate)) {
    1573          45 :     *out = kMaxUInt32;
    1574             :     return object;
    1575             :   }
    1576             : 
    1577             :   Handle<Object> number;
    1578          30 :   ASSIGN_RETURN_ON_EXCEPTION(isolate, number, Object::ToNumber(object), Object);
    1579          15 :   *out = NumberToUint32(*number);
    1580             :   return object;
    1581             : }
    1582             : 
    1583          45 : Handle<JSArray> NewJSArrayWithElements(Isolate* isolate,
    1584             :                                        Handle<FixedArray> elems,
    1585             :                                        int num_elems) {
    1586          45 :   elems->Shrink(num_elems);
    1587          45 :   return isolate->factory()->NewJSArrayWithElements(elems);
    1588             : }
    1589             : 
    1590             : }  // namespace
    1591             : 
    1592             : // Slow path for:
    1593             : // ES#sec-regexp.prototype-@@replace
    1594             : // RegExp.prototype [ @@split ] ( string, limit )
    1595         120 : RUNTIME_FUNCTION(Runtime_RegExpSplit) {
    1596          60 :   HandleScope scope(isolate);
    1597             :   DCHECK_EQ(3, args.length());
    1598             : 
    1599             :   DCHECK(args[1]->IsString());
    1600             : 
    1601         120 :   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, recv, 0);
    1602         120 :   CONVERT_ARG_HANDLE_CHECKED(String, string, 1);
    1603          60 :   CONVERT_ARG_HANDLE_CHECKED(Object, limit_obj, 2);
    1604             : 
    1605          60 :   Factory* factory = isolate->factory();
    1606             : 
    1607          60 :   Handle<JSFunction> regexp_fun = isolate->regexp_function();
    1608             :   Handle<Object> ctor;
    1609         120 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1610             :       isolate, ctor, Object::SpeciesConstructor(isolate, recv, regexp_fun));
    1611             : 
    1612             :   Handle<Object> flags_obj;
    1613         180 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1614             :       isolate, flags_obj, JSObject::GetProperty(recv, factory->flags_string()));
    1615             : 
    1616             :   Handle<String> flags;
    1617         120 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, flags,
    1618             :                                      Object::ToString(isolate, flags_obj));
    1619             : 
    1620          60 :   Handle<String> u_str = factory->LookupSingleCharacterStringFromCode('u');
    1621          60 :   const bool unicode = (String::IndexOf(isolate, flags, u_str, 0) >= 0);
    1622             : 
    1623          60 :   Handle<String> y_str = factory->LookupSingleCharacterStringFromCode('y');
    1624          60 :   const bool sticky = (String::IndexOf(isolate, flags, y_str, 0) >= 0);
    1625             : 
    1626             :   Handle<String> new_flags = flags;
    1627          60 :   if (!sticky) {
    1628         120 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, new_flags,
    1629             :                                        factory->NewConsString(flags, y_str));
    1630             :   }
    1631             : 
    1632             :   Handle<JSReceiver> splitter;
    1633             :   {
    1634             :     const int argc = 2;
    1635             : 
    1636          60 :     ScopedVector<Handle<Object>> argv(argc);
    1637          60 :     argv[0] = recv;
    1638          60 :     argv[1] = new_flags;
    1639             : 
    1640          60 :     Handle<JSFunction> ctor_fun = Handle<JSFunction>::cast(ctor);
    1641             :     Handle<Object> splitter_obj;
    1642         120 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1643             :         isolate, splitter_obj, Execution::New(ctor_fun, argc, argv.start()));
    1644             : 
    1645          60 :     splitter = Handle<JSReceiver>::cast(splitter_obj);
    1646             :   }
    1647             : 
    1648             :   uint32_t limit;
    1649          60 :   RETURN_FAILURE_ON_EXCEPTION(isolate, ToUint32(isolate, limit_obj, &limit));
    1650             : 
    1651          60 :   const uint32_t length = string->length();
    1652             : 
    1653          60 :   if (limit == 0) return *factory->NewJSArray(0);
    1654             : 
    1655          60 :   if (length == 0) {
    1656             :     Handle<Object> result;
    1657          45 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1658             :         isolate, result, RegExpUtils::RegExpExec(isolate, splitter, string,
    1659             :                                                  factory->undefined_value()));
    1660             : 
    1661          15 :     if (!result->IsNull(isolate)) return *factory->NewJSArray(0);
    1662             : 
    1663          15 :     Handle<FixedArray> elems = factory->NewUninitializedFixedArray(1);
    1664          15 :     elems->set(0, *string);
    1665          30 :     return *factory->NewJSArrayWithElements(elems);
    1666             :   }
    1667             : 
    1668             :   static const int kInitialArraySize = 8;
    1669          45 :   Handle<FixedArray> elems = factory->NewFixedArrayWithHoles(kInitialArraySize);
    1670             :   int num_elems = 0;
    1671             : 
    1672             :   uint32_t string_index = 0;
    1673             :   uint32_t prev_string_index = 0;
    1674         225 :   while (string_index < length) {
    1675         180 :     RETURN_FAILURE_ON_EXCEPTION(
    1676             :         isolate, RegExpUtils::SetLastIndex(isolate, splitter, string_index));
    1677             : 
    1678             :     Handle<Object> result;
    1679         540 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1680             :         isolate, result, RegExpUtils::RegExpExec(isolate, splitter, string,
    1681             :                                                  factory->undefined_value()));
    1682             : 
    1683         180 :     if (result->IsNull(isolate)) {
    1684             :       string_index = RegExpUtils::AdvanceStringIndex(isolate, string,
    1685          75 :                                                      string_index, unicode);
    1686             :       continue;
    1687             :     }
    1688             : 
    1689             :     Handle<Object> last_index_obj;
    1690         210 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1691             :         isolate, last_index_obj, RegExpUtils::GetLastIndex(isolate, splitter));
    1692             : 
    1693         210 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1694             :         isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));
    1695             : 
    1696             :     const uint32_t end =
    1697         105 :         std::min(PositiveNumberToUint32(*last_index_obj), length);
    1698         105 :     if (end == prev_string_index) {
    1699             :       string_index = RegExpUtils::AdvanceStringIndex(isolate, string,
    1700           0 :                                                      string_index, unicode);
    1701             :       continue;
    1702             :     }
    1703             : 
    1704             :     {
    1705             :       Handle<String> substr =
    1706         105 :           factory->NewSubString(string, prev_string_index, string_index);
    1707         105 :       elems = FixedArray::SetAndGrow(elems, num_elems++, substr);
    1708         105 :       if (static_cast<uint32_t>(num_elems) == limit) {
    1709           0 :         return *NewJSArrayWithElements(isolate, elems, num_elems);
    1710             :       }
    1711             :     }
    1712             : 
    1713             :     prev_string_index = end;
    1714             : 
    1715             :     Handle<Object> num_captures_obj;
    1716         315 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1717             :         isolate, num_captures_obj,
    1718             :         Object::GetProperty(result, isolate->factory()->length_string()));
    1719             : 
    1720         210 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1721             :         isolate, num_captures_obj, Object::ToLength(isolate, num_captures_obj));
    1722         105 :     const int num_captures = PositiveNumberToUint32(*num_captures_obj);
    1723             : 
    1724         105 :     for (int i = 1; i < num_captures; i++) {
    1725             :       Handle<Object> capture;
    1726           0 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1727             :           isolate, capture, Object::GetElement(isolate, result, i));
    1728           0 :       elems = FixedArray::SetAndGrow(elems, num_elems++, capture);
    1729           0 :       if (static_cast<uint32_t>(num_elems) == limit) {
    1730           0 :         return *NewJSArrayWithElements(isolate, elems, num_elems);
    1731             :       }
    1732             :     }
    1733             : 
    1734             :     string_index = prev_string_index;
    1735             :   }
    1736             : 
    1737             :   {
    1738             :     Handle<String> substr =
    1739          45 :         factory->NewSubString(string, prev_string_index, length);
    1740          45 :     elems = FixedArray::SetAndGrow(elems, num_elems++, substr);
    1741             :   }
    1742             : 
    1743          90 :   return *NewJSArrayWithElements(isolate, elems, num_elems);
    1744             : }
    1745             : 
    1746             : // Slow path for:
    1747             : // ES#sec-regexp.prototype-@@replace
    1748             : // RegExp.prototype [ @@replace ] ( string, replaceValue )
    1749       19265 : RUNTIME_FUNCTION(Runtime_RegExpReplace) {
    1750        9361 :   HandleScope scope(isolate);
    1751             :   DCHECK_EQ(3, args.length());
    1752             : 
    1753       18722 :   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, recv, 0);
    1754       18722 :   CONVERT_ARG_HANDLE_CHECKED(String, string, 1);
    1755        9361 :   Handle<Object> replace_obj = args.at(2);
    1756             : 
    1757        9361 :   Factory* factory = isolate->factory();
    1758             : 
    1759        9361 :   string = String::Flatten(string);
    1760             : 
    1761             :   // Fast-path for unmodified JSRegExps.
    1762        9361 :   if (RegExpUtils::IsUnmodifiedRegExp(isolate, recv)) {
    1763       17636 :     RETURN_RESULT_OR_FAILURE(
    1764             :         isolate, RegExpReplace(isolate, Handle<JSRegExp>::cast(recv), string,
    1765             :                                replace_obj));
    1766             :   }
    1767             : 
    1768         543 :   const uint32_t length = string->length();
    1769             :   const bool functional_replace = replace_obj->IsCallable();
    1770             : 
    1771             :   Handle<String> replace;
    1772         543 :   if (!functional_replace) {
    1773         946 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, replace,
    1774             :                                        Object::ToString(isolate, replace_obj));
    1775             :   }
    1776             : 
    1777             :   Handle<Object> global_obj;
    1778        1629 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1779             :       isolate, global_obj,
    1780             :       JSReceiver::GetProperty(recv, factory->global_string()));
    1781         543 :   const bool global = global_obj->BooleanValue();
    1782             : 
    1783             :   bool unicode = false;
    1784         543 :   if (global) {
    1785             :     Handle<Object> unicode_obj;
    1786         936 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1787             :         isolate, unicode_obj,
    1788             :         JSReceiver::GetProperty(recv, factory->unicode_string()));
    1789         312 :     unicode = unicode_obj->BooleanValue();
    1790             : 
    1791         312 :     RETURN_FAILURE_ON_EXCEPTION(isolate,
    1792             :                                 RegExpUtils::SetLastIndex(isolate, recv, 0));
    1793             :   }
    1794             : 
    1795        1086 :   Zone zone(isolate->allocator(), ZONE_NAME);
    1796        1086 :   ZoneVector<Handle<Object>> results(&zone);
    1797             : 
    1798             :   while (true) {
    1799             :     Handle<Object> result;
    1800        2706 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1801             :         isolate, result, RegExpUtils::RegExpExec(isolate, recv, string,
    1802             :                                                  factory->undefined_value()));
    1803             : 
    1804         882 :     if (result->IsNull(isolate)) break;
    1805             : 
    1806         495 :     results.push_back(result);
    1807         495 :     if (!global) break;
    1808             : 
    1809             :     Handle<Object> match_obj;
    1810         708 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
    1811             :                                        Object::GetElement(isolate, result, 0));
    1812             : 
    1813             :     Handle<String> match;
    1814         708 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
    1815             :                                        Object::ToString(isolate, match_obj));
    1816             : 
    1817         354 :     if (match->length() == 0) {
    1818           0 :       RETURN_FAILURE_ON_EXCEPTION(isolate, RegExpUtils::SetAdvancedStringIndex(
    1819             :                                                isolate, recv, string, unicode));
    1820             :     }
    1821             :   }
    1822             : 
    1823             :   // TODO(jgruber): Look into ReplacementStringBuilder instead.
    1824         528 :   IncrementalStringBuilder builder(isolate);
    1825             :   uint32_t next_source_position = 0;
    1826             : 
    1827        1710 :   for (const auto& result : results) {
    1828             :     Handle<Object> captures_length_obj;
    1829        1429 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1830             :         isolate, captures_length_obj,
    1831             :         Object::GetProperty(result, factory->length_string()));
    1832             : 
    1833         878 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1834             :         isolate, captures_length_obj,
    1835             :         Object::ToLength(isolate, captures_length_obj));
    1836         439 :     const int captures_length = PositiveNumberToUint32(*captures_length_obj);
    1837             : 
    1838             :     Handle<Object> match_obj;
    1839         878 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
    1840             :                                        Object::GetElement(isolate, result, 0));
    1841             : 
    1842             :     Handle<String> match;
    1843         878 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
    1844             :                                        Object::ToString(isolate, match_obj));
    1845             : 
    1846         439 :     const int match_length = match->length();
    1847             : 
    1848             :     Handle<Object> position_obj;
    1849        1317 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1850             :         isolate, position_obj,
    1851             :         Object::GetProperty(result, factory->index_string()));
    1852             : 
    1853         878 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1854             :         isolate, position_obj, Object::ToInteger(isolate, position_obj));
    1855             :     const uint32_t position =
    1856         439 :         std::min(PositiveNumberToUint32(*position_obj), length);
    1857             : 
    1858             :     // Do not reserve capacity since captures_length is user-controlled.
    1859         439 :     ZoneVector<Handle<Object>> captures(&zone);
    1860             : 
    1861        3163 :     for (int n = 0; n < captures_length; n++) {
    1862             :       Handle<Object> capture;
    1863        2724 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1864             :           isolate, capture, Object::GetElement(isolate, result, n));
    1865             : 
    1866        1362 :       if (!capture->IsUndefined(isolate)) {
    1867        2108 :         ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, capture,
    1868             :                                            Object::ToString(isolate, capture));
    1869             :       }
    1870        1362 :       captures.push_back(capture);
    1871             :     }
    1872             : 
    1873         439 :     Handle<Object> groups_obj = isolate->factory()->undefined_value();
    1874         439 :     if (FLAG_harmony_regexp_named_captures) {
    1875        1050 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1876             :           isolate, groups_obj,
    1877             :           Object::GetProperty(result, factory->groups_string()));
    1878             :     }
    1879             : 
    1880         439 :     const bool has_named_captures = !groups_obj->IsUndefined(isolate);
    1881             :     DCHECK_IMPLIES(has_named_captures, FLAG_harmony_regexp_named_captures);
    1882             : 
    1883             :     Handle<String> replacement;
    1884         439 :     if (functional_replace) {
    1885             :       const int argc =
    1886         126 :           has_named_captures ? captures_length + 3 : captures_length + 2;
    1887         126 :       ScopedVector<Handle<Object>> argv(argc);
    1888             : 
    1889             :       int cursor = 0;
    1890         350 :       for (int j = 0; j < captures_length; j++) {
    1891         350 :         argv[cursor++] = captures[j];
    1892             :       }
    1893             : 
    1894         252 :       argv[cursor++] = handle(Smi::FromInt(position), isolate);
    1895         126 :       argv[cursor++] = string;
    1896         126 :       if (has_named_captures) argv[cursor++] = groups_obj;
    1897             : 
    1898             :       DCHECK_EQ(cursor, argc);
    1899             : 
    1900             :       Handle<Object> replacement_obj;
    1901         378 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1902             :           isolate, replacement_obj,
    1903             :           Execution::Call(isolate, replace_obj, factory->undefined_value(),
    1904             :                           argc, argv.start()));
    1905             : 
    1906         252 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1907         126 :           isolate, replacement, Object::ToString(isolate, replacement_obj));
    1908             :     } else {
    1909             :       DCHECK(!functional_replace);
    1910         313 :       if (!groups_obj->IsUndefined(isolate)) {
    1911         588 :         ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1912             :             isolate, groups_obj, JSReceiver::ToObject(isolate, groups_obj));
    1913             :       }
    1914             :       VectorBackedMatch m(isolate, string, match, position, &captures,
    1915         313 :                           groups_obj);
    1916         626 :       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1917         201 :           isolate, replacement, String::GetSubstitution(isolate, &m, replace));
    1918             :     }
    1919             : 
    1920         327 :     if (position >= next_source_position) {
    1921             :       builder.AppendString(
    1922         327 :           factory->NewSubString(string, next_source_position, position));
    1923         327 :       builder.AppendString(replacement);
    1924             : 
    1925         327 :       next_source_position = position + match_length;
    1926             :     }
    1927         327 :   }
    1928             : 
    1929         416 :   if (next_source_position < length) {
    1930             :     builder.AppendString(
    1931         287 :         factory->NewSubString(string, next_source_position, length));
    1932             :   }
    1933             : 
    1934       10193 :   RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
    1935             : }
    1936             : 
    1937           0 : RUNTIME_FUNCTION(Runtime_RegExpExecReThrow) {
    1938             :   SealHandleScope shs(isolate);
    1939             :   DCHECK_EQ(0, args.length());
    1940           0 :   Object* exception = isolate->pending_exception();
    1941           0 :   isolate->clear_pending_exception();
    1942           0 :   return isolate->ReThrow(exception);
    1943             : }
    1944             : 
    1945     1186418 : RUNTIME_FUNCTION(Runtime_RegExpInitializeAndCompile) {
    1946      593209 :   HandleScope scope(isolate);
    1947             :   DCHECK_EQ(3, args.length());
    1948     1186418 :   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
    1949     1186418 :   CONVERT_ARG_HANDLE_CHECKED(String, source, 1);
    1950     1186418 :   CONVERT_ARG_HANDLE_CHECKED(String, flags, 2);
    1951             : 
    1952      593209 :   RETURN_FAILURE_ON_EXCEPTION(isolate,
    1953             :                               JSRegExp::Initialize(regexp, source, flags));
    1954             : 
    1955      593209 :   return *regexp;
    1956             : }
    1957             : 
    1958     1676164 : RUNTIME_FUNCTION(Runtime_IsRegExp) {
    1959             :   SealHandleScope shs(isolate);
    1960             :   DCHECK_EQ(1, args.length());
    1961      838082 :   CONVERT_ARG_CHECKED(Object, obj, 0);
    1962      838082 :   return isolate->heap()->ToBoolean(obj->IsJSRegExp());
    1963             : }
    1964             : 
    1965             : }  // namespace internal
    1966             : }  // namespace v8

Generated by: LCOV version 1.10