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 "src/arguments.h" 8 #include "src/conversions-inl.h" 9 #include "src/isolate-inl.h" 10 #include "src/messages.h" 11 #include "src/regexp/jsregexp-inl.h" 12 #include "src/regexp/jsregexp.h" 13 #include "src/string-builder.h" 14 #include "src/string-search.h" 15 16 namespace v8 { 17 namespace internal { 18 19 class CompiledReplacement { 20 public: 21 explicit CompiledReplacement(Zone* zone) 22 : parts_(1, zone), replacement_substrings_(0, zone), zone_(zone) {} 23 24 // Return whether the replacement is simple. 25 bool Compile(Handle<String> replacement, int capture_count, 26 int subject_length); 27 28 // Use Apply only if Compile returned false. 29 void Apply(ReplacementStringBuilder* builder, int match_from, int match_to, 30 int32_t* match); 31 32 // Number of distinct parts of the replacement pattern. 33 int parts() { return parts_.length(); } 34 35 Zone* zone() const { return zone_; } 36 37 private: 38 enum PartType { 39 SUBJECT_PREFIX = 1, 40 SUBJECT_SUFFIX, 41 SUBJECT_CAPTURE, 42 REPLACEMENT_SUBSTRING, 43 REPLACEMENT_STRING, 44 NUMBER_OF_PART_TYPES 45 }; 46 47 struct ReplacementPart { 48 static inline ReplacementPart SubjectMatch() { 49 return ReplacementPart(SUBJECT_CAPTURE, 0); 50 } 51 static inline ReplacementPart SubjectCapture(int capture_index) { 52 return ReplacementPart(SUBJECT_CAPTURE, capture_index); 53 } 54 static inline ReplacementPart SubjectPrefix() { 55 return ReplacementPart(SUBJECT_PREFIX, 0); 56 } 57 static inline ReplacementPart SubjectSuffix(int subject_length) { 58 return ReplacementPart(SUBJECT_SUFFIX, subject_length); 59 } 60 static inline ReplacementPart ReplacementString() { 61 return ReplacementPart(REPLACEMENT_STRING, 0); 62 } 63 static inline ReplacementPart ReplacementSubString(int from, int to) { 64 DCHECK(from >= 0); 65 DCHECK(to > from); 66 return ReplacementPart(-from, to); 67 } 68 69 // If tag <= 0 then it is the negation of a start index of a substring of 70 // the replacement pattern, otherwise it's a value from PartType. 71 ReplacementPart(int tag, int data) : tag(tag), data(data) { 72 // Must be non-positive or a PartType value. 73 DCHECK(tag < NUMBER_OF_PART_TYPES); 74 } 75 // Either a value of PartType or a non-positive number that is 76 // the negation of an index into the replacement string. 77 int tag; 78 // The data value's interpretation depends on the value of tag: 79 // tag == SUBJECT_PREFIX || 80 // tag == SUBJECT_SUFFIX: data is unused. 81 // tag == SUBJECT_CAPTURE: data is the number of the capture. 82 // tag == REPLACEMENT_SUBSTRING || 83 // tag == REPLACEMENT_STRING: data is index into array of substrings 84 // of the replacement string. 85 // tag <= 0: Temporary representation of the substring of the replacement 86 // string ranging over -tag .. data. 87 // Is replaced by REPLACEMENT_{SUB,}STRING when we create the 88 // substring objects. 89 int data; 90 }; 91 92 template <typename Char> 93 bool ParseReplacementPattern(ZoneList<ReplacementPart>* parts, 94 Vector<Char> characters, int capture_count, 95 int subject_length, Zone* zone) { 96 int length = characters.length(); 97 int last = 0; 98 for (int i = 0; i < length; i++) { 99 Char c = characters[i]; 100 if (c == '$') { 101 int next_index = i + 1; 102 if (next_index == length) { // No next character! 103 break; 104 } 105 Char c2 = characters[next_index]; 106 switch (c2) { 107 case '$': 108 if (i > last) { 109 // There is a substring before. Include the first "$". 110 parts->Add( 111 ReplacementPart::ReplacementSubString(last, next_index), 112 zone); 113 last = next_index + 1; // Continue after the second "$". 114 } else { 115 // Let the next substring start with the second "$". 116 last = next_index; 117 } 118 i = next_index; 119 break; 120 case '`': 121 if (i > last) { 122 parts->Add(ReplacementPart::ReplacementSubString(last, i), zone); 123 } 124 parts->Add(ReplacementPart::SubjectPrefix(), zone); 125 i = next_index; 126 last = i + 1; 127 break; 128 case '\'': 129 if (i > last) { 130 parts->Add(ReplacementPart::ReplacementSubString(last, i), zone); 131 } 132 parts->Add(ReplacementPart::SubjectSuffix(subject_length), zone); 133 i = next_index; 134 last = i + 1; 135 break; 136 case '&': 137 if (i > last) { 138 parts->Add(ReplacementPart::ReplacementSubString(last, i), zone); 139 } 140 parts->Add(ReplacementPart::SubjectMatch(), zone); 141 i = next_index; 142 last = i + 1; 143 break; 144 case '0': 145 case '1': 146 case '2': 147 case '3': 148 case '4': 149 case '5': 150 case '6': 151 case '7': 152 case '8': 153 case '9': { 154 int capture_ref = c2 - '0'; 155 if (capture_ref > capture_count) { 156 i = next_index; 157 continue; 158 } 159 int second_digit_index = next_index + 1; 160 if (second_digit_index < length) { 161 // Peek ahead to see if we have two digits. 162 Char c3 = characters[second_digit_index]; 163 if ('0' <= c3 && c3 <= '9') { // Double digits. 164 int double_digit_ref = capture_ref * 10 + c3 - '0'; 165 if (double_digit_ref <= capture_count) { 166 next_index = second_digit_index; 167 capture_ref = double_digit_ref; 168 } 169 } 170 } 171 if (capture_ref > 0) { 172 if (i > last) { 173 parts->Add(ReplacementPart::ReplacementSubString(last, i), 174 zone); 175 } 176 DCHECK(capture_ref <= capture_count); 177 parts->Add(ReplacementPart::SubjectCapture(capture_ref), zone); 178 last = next_index + 1; 179 } 180 i = next_index; 181 break; 182 } 183 default: 184 i = next_index; 185 break; 186 } 187 } 188 } 189 if (length > last) { 190 if (last == 0) { 191 // Replacement is simple. Do not use Apply to do the replacement. 192 return true; 193 } else { 194 parts->Add(ReplacementPart::ReplacementSubString(last, length), zone); 195 } 196 } 197 return false; 198 } 199 200 ZoneList<ReplacementPart> parts_; 201 ZoneList<Handle<String> > replacement_substrings_; 202 Zone* zone_; 203 }; 204 205 206 bool CompiledReplacement::Compile(Handle<String> replacement, int capture_count, 207 int subject_length) { 208 { 209 DisallowHeapAllocation no_gc; 210 String::FlatContent content = replacement->GetFlatContent(); 211 DCHECK(content.IsFlat()); 212 bool simple = false; 213 if (content.IsOneByte()) { 214 simple = ParseReplacementPattern(&parts_, content.ToOneByteVector(), 215 capture_count, subject_length, zone()); 216 } else { 217 DCHECK(content.IsTwoByte()); 218 simple = ParseReplacementPattern(&parts_, content.ToUC16Vector(), 219 capture_count, subject_length, zone()); 220 } 221 if (simple) return true; 222 } 223 224 Isolate* isolate = replacement->GetIsolate(); 225 // Find substrings of replacement string and create them as String objects. 226 int substring_index = 0; 227 for (int i = 0, n = parts_.length(); i < n; i++) { 228 int tag = parts_[i].tag; 229 if (tag <= 0) { // A replacement string slice. 230 int from = -tag; 231 int to = parts_[i].data; 232 replacement_substrings_.Add( 233 isolate->factory()->NewSubString(replacement, from, to), zone()); 234 parts_[i].tag = REPLACEMENT_SUBSTRING; 235 parts_[i].data = substring_index; 236 substring_index++; 237 } else if (tag == REPLACEMENT_STRING) { 238 replacement_substrings_.Add(replacement, zone()); 239 parts_[i].data = substring_index; 240 substring_index++; 241 } 242 } 243 return false; 244 } 245 246 247 void CompiledReplacement::Apply(ReplacementStringBuilder* builder, 248 int match_from, int match_to, int32_t* match) { 249 DCHECK_LT(0, parts_.length()); 250 for (int i = 0, n = parts_.length(); i < n; i++) { 251 ReplacementPart part = parts_[i]; 252 switch (part.tag) { 253 case SUBJECT_PREFIX: 254 if (match_from > 0) builder->AddSubjectSlice(0, match_from); 255 break; 256 case SUBJECT_SUFFIX: { 257 int subject_length = part.data; 258 if (match_to < subject_length) { 259 builder->AddSubjectSlice(match_to, subject_length); 260 } 261 break; 262 } 263 case SUBJECT_CAPTURE: { 264 int capture = part.data; 265 int from = match[capture * 2]; 266 int to = match[capture * 2 + 1]; 267 if (from >= 0 && to > from) { 268 builder->AddSubjectSlice(from, to); 269 } 270 break; 271 } 272 case REPLACEMENT_SUBSTRING: 273 case REPLACEMENT_STRING: 274 builder->AddString(replacement_substrings_[part.data]); 275 break; 276 default: 277 UNREACHABLE(); 278 } 279 } 280 } 281 282 283 void FindOneByteStringIndices(Vector<const uint8_t> subject, uint8_t pattern, 284 ZoneList<int>* indices, unsigned int limit, 285 Zone* zone) { 286 DCHECK(limit > 0); 287 // Collect indices of pattern in subject using memchr. 288 // Stop after finding at most limit values. 289 const uint8_t* subject_start = subject.start(); 290 const uint8_t* subject_end = subject_start + subject.length(); 291 const uint8_t* pos = subject_start; 292 while (limit > 0) { 293 pos = reinterpret_cast<const uint8_t*>( 294 memchr(pos, pattern, subject_end - pos)); 295 if (pos == NULL) return; 296 indices->Add(static_cast<int>(pos - subject_start), zone); 297 pos++; 298 limit--; 299 } 300 } 301 302 303 void FindTwoByteStringIndices(const Vector<const uc16> subject, uc16 pattern, 304 ZoneList<int>* indices, unsigned int limit, 305 Zone* zone) { 306 DCHECK(limit > 0); 307 const uc16* subject_start = subject.start(); 308 const uc16* subject_end = subject_start + subject.length(); 309 for (const uc16* pos = subject_start; pos < subject_end && limit > 0; pos++) { 310 if (*pos == pattern) { 311 indices->Add(static_cast<int>(pos - subject_start), zone); 312 limit--; 313 } 314 } 315 } 316 317 318 template <typename SubjectChar, typename PatternChar> 319 void FindStringIndices(Isolate* isolate, Vector<const SubjectChar> subject, 320 Vector<const PatternChar> pattern, 321 ZoneList<int>* indices, unsigned int limit, Zone* zone) { 322 DCHECK(limit > 0); 323 // Collect indices of pattern in subject. 324 // Stop after finding at most limit values. 325 int pattern_length = pattern.length(); 326 int index = 0; 327 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); 328 while (limit > 0) { 329 index = search.Search(subject, index); 330 if (index < 0) return; 331 indices->Add(index, zone); 332 index += pattern_length; 333 limit--; 334 } 335 } 336 337 338 void FindStringIndicesDispatch(Isolate* isolate, String* subject, 339 String* pattern, ZoneList<int>* indices, 340 unsigned int limit, Zone* zone) { 341 { 342 DisallowHeapAllocation no_gc; 343 String::FlatContent subject_content = subject->GetFlatContent(); 344 String::FlatContent pattern_content = pattern->GetFlatContent(); 345 DCHECK(subject_content.IsFlat()); 346 DCHECK(pattern_content.IsFlat()); 347 if (subject_content.IsOneByte()) { 348 Vector<const uint8_t> subject_vector = subject_content.ToOneByteVector(); 349 if (pattern_content.IsOneByte()) { 350 Vector<const uint8_t> pattern_vector = 351 pattern_content.ToOneByteVector(); 352 if (pattern_vector.length() == 1) { 353 FindOneByteStringIndices(subject_vector, pattern_vector[0], indices, 354 limit, zone); 355 } else { 356 FindStringIndices(isolate, subject_vector, pattern_vector, indices, 357 limit, zone); 358 } 359 } else { 360 FindStringIndices(isolate, subject_vector, 361 pattern_content.ToUC16Vector(), indices, limit, zone); 362 } 363 } else { 364 Vector<const uc16> subject_vector = subject_content.ToUC16Vector(); 365 if (pattern_content.IsOneByte()) { 366 Vector<const uint8_t> pattern_vector = 367 pattern_content.ToOneByteVector(); 368 if (pattern_vector.length() == 1) { 369 FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices, 370 limit, zone); 371 } else { 372 FindStringIndices(isolate, subject_vector, pattern_vector, indices, 373 limit, zone); 374 } 375 } else { 376 Vector<const uc16> pattern_vector = pattern_content.ToUC16Vector(); 377 if (pattern_vector.length() == 1) { 378 FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices, 379 limit, zone); 380 } else { 381 FindStringIndices(isolate, subject_vector, pattern_vector, indices, 382 limit, zone); 383 } 384 } 385 } 386 } 387 } 388 389 390 template <typename ResultSeqString> 391 MUST_USE_RESULT static Object* StringReplaceGlobalAtomRegExpWithString( 392 Isolate* isolate, Handle<String> subject, Handle<JSRegExp> pattern_regexp, 393 Handle<String> replacement, Handle<JSArray> last_match_info) { 394 DCHECK(subject->IsFlat()); 395 DCHECK(replacement->IsFlat()); 396 397 ZoneScope zone_scope(isolate->runtime_zone()); 398 ZoneList<int> indices(8, zone_scope.zone()); 399 DCHECK_EQ(JSRegExp::ATOM, pattern_regexp->TypeTag()); 400 String* pattern = 401 String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex)); 402 int subject_len = subject->length(); 403 int pattern_len = pattern->length(); 404 int replacement_len = replacement->length(); 405 406 FindStringIndicesDispatch(isolate, *subject, pattern, &indices, 0xffffffff, 407 zone_scope.zone()); 408 409 int matches = indices.length(); 410 if (matches == 0) return *subject; 411 412 // Detect integer overflow. 413 int64_t result_len_64 = (static_cast<int64_t>(replacement_len) - 414 static_cast<int64_t>(pattern_len)) * 415 static_cast<int64_t>(matches) + 416 static_cast<int64_t>(subject_len); 417 int result_len; 418 if (result_len_64 > static_cast<int64_t>(String::kMaxLength)) { 419 STATIC_ASSERT(String::kMaxLength < kMaxInt); 420 result_len = kMaxInt; // Provoke exception. 421 } else { 422 result_len = static_cast<int>(result_len_64); 423 } 424 425 int subject_pos = 0; 426 int result_pos = 0; 427 428 MaybeHandle<SeqString> maybe_res; 429 if (ResultSeqString::kHasOneByteEncoding) { 430 maybe_res = isolate->factory()->NewRawOneByteString(result_len); 431 } else { 432 maybe_res = isolate->factory()->NewRawTwoByteString(result_len); 433 } 434 Handle<SeqString> untyped_res; 435 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, untyped_res, maybe_res); 436 Handle<ResultSeqString> result = Handle<ResultSeqString>::cast(untyped_res); 437 438 for (int i = 0; i < matches; i++) { 439 // Copy non-matched subject content. 440 if (subject_pos < indices.at(i)) { 441 String::WriteToFlat(*subject, result->GetChars() + result_pos, 442 subject_pos, indices.at(i)); 443 result_pos += indices.at(i) - subject_pos; 444 } 445 446 // Replace match. 447 if (replacement_len > 0) { 448 String::WriteToFlat(*replacement, result->GetChars() + result_pos, 0, 449 replacement_len); 450 result_pos += replacement_len; 451 } 452 453 subject_pos = indices.at(i) + pattern_len; 454 } 455 // Add remaining subject content at the end. 456 if (subject_pos < subject_len) { 457 String::WriteToFlat(*subject, result->GetChars() + result_pos, subject_pos, 458 subject_len); 459 } 460 461 int32_t match_indices[] = {indices.at(matches - 1), 462 indices.at(matches - 1) + pattern_len}; 463 RegExpImpl::SetLastMatchInfo(last_match_info, subject, 0, match_indices); 464 465 return *result; 466 } 467 468 469 MUST_USE_RESULT static Object* StringReplaceGlobalRegExpWithString( 470 Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp, 471 Handle<String> replacement, Handle<JSArray> last_match_info) { 472 DCHECK(subject->IsFlat()); 473 DCHECK(replacement->IsFlat()); 474 475 int capture_count = regexp->CaptureCount(); 476 int subject_length = subject->length(); 477 478 // CompiledReplacement uses zone allocation. 479 ZoneScope zone_scope(isolate->runtime_zone()); 480 CompiledReplacement compiled_replacement(zone_scope.zone()); 481 bool simple_replace = 482 compiled_replacement.Compile(replacement, capture_count, subject_length); 483 484 // Shortcut for simple non-regexp global replacements 485 if (regexp->TypeTag() == JSRegExp::ATOM && simple_replace) { 486 if (subject->HasOnlyOneByteChars() && replacement->HasOnlyOneByteChars()) { 487 return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>( 488 isolate, subject, regexp, replacement, last_match_info); 489 } else { 490 return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>( 491 isolate, subject, regexp, replacement, last_match_info); 492 } 493 } 494 495 RegExpImpl::GlobalCache global_cache(regexp, subject, isolate); 496 if (global_cache.HasException()) return isolate->heap()->exception(); 497 498 int32_t* current_match = global_cache.FetchNext(); 499 if (current_match == NULL) { 500 if (global_cache.HasException()) return isolate->heap()->exception(); 501 return *subject; 502 } 503 504 // Guessing the number of parts that the final result string is built 505 // from. Global regexps can match any number of times, so we guess 506 // conservatively. 507 int expected_parts = (compiled_replacement.parts() + 1) * 4 + 1; 508 ReplacementStringBuilder builder(isolate->heap(), subject, expected_parts); 509 510 // Number of parts added by compiled replacement plus preceeding 511 // string and possibly suffix after last match. It is possible for 512 // all components to use two elements when encoded as two smis. 513 const int parts_added_per_loop = 2 * (compiled_replacement.parts() + 2); 514 515 int prev = 0; 516 517 do { 518 builder.EnsureCapacity(parts_added_per_loop); 519 520 int start = current_match[0]; 521 int end = current_match[1]; 522 523 if (prev < start) { 524 builder.AddSubjectSlice(prev, start); 525 } 526 527 if (simple_replace) { 528 builder.AddString(replacement); 529 } else { 530 compiled_replacement.Apply(&builder, start, end, current_match); 531 } 532 prev = end; 533 534 current_match = global_cache.FetchNext(); 535 } while (current_match != NULL); 536 537 if (global_cache.HasException()) return isolate->heap()->exception(); 538 539 if (prev < subject_length) { 540 builder.EnsureCapacity(2); 541 builder.AddSubjectSlice(prev, subject_length); 542 } 543 544 RegExpImpl::SetLastMatchInfo(last_match_info, subject, capture_count, 545 global_cache.LastSuccessfulMatch()); 546 547 RETURN_RESULT_OR_FAILURE(isolate, builder.ToString()); 548 } 549 550 551 template <typename ResultSeqString> 552 MUST_USE_RESULT static Object* StringReplaceGlobalRegExpWithEmptyString( 553 Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp, 554 Handle<JSArray> last_match_info) { 555 DCHECK(subject->IsFlat()); 556 557 // Shortcut for simple non-regexp global replacements 558 if (regexp->TypeTag() == JSRegExp::ATOM) { 559 Handle<String> empty_string = isolate->factory()->empty_string(); 560 if (subject->IsOneByteRepresentation()) { 561 return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>( 562 isolate, subject, regexp, empty_string, last_match_info); 563 } else { 564 return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>( 565 isolate, subject, regexp, empty_string, last_match_info); 566 } 567 } 568 569 RegExpImpl::GlobalCache global_cache(regexp, subject, isolate); 570 if (global_cache.HasException()) return isolate->heap()->exception(); 571 572 int32_t* current_match = global_cache.FetchNext(); 573 if (current_match == NULL) { 574 if (global_cache.HasException()) return isolate->heap()->exception(); 575 return *subject; 576 } 577 578 int start = current_match[0]; 579 int end = current_match[1]; 580 int capture_count = regexp->CaptureCount(); 581 int subject_length = subject->length(); 582 583 int new_length = subject_length - (end - start); 584 if (new_length == 0) return isolate->heap()->empty_string(); 585 586 Handle<ResultSeqString> answer; 587 if (ResultSeqString::kHasOneByteEncoding) { 588 answer = Handle<ResultSeqString>::cast( 589 isolate->factory()->NewRawOneByteString(new_length).ToHandleChecked()); 590 } else { 591 answer = Handle<ResultSeqString>::cast( 592 isolate->factory()->NewRawTwoByteString(new_length).ToHandleChecked()); 593 } 594 595 int prev = 0; 596 int position = 0; 597 598 do { 599 start = current_match[0]; 600 end = current_match[1]; 601 if (prev < start) { 602 // Add substring subject[prev;start] to answer string. 603 String::WriteToFlat(*subject, answer->GetChars() + position, prev, start); 604 position += start - prev; 605 } 606 prev = end; 607 608 current_match = global_cache.FetchNext(); 609 } while (current_match != NULL); 610 611 if (global_cache.HasException()) return isolate->heap()->exception(); 612 613 RegExpImpl::SetLastMatchInfo(last_match_info, subject, capture_count, 614 global_cache.LastSuccessfulMatch()); 615 616 if (prev < subject_length) { 617 // Add substring subject[prev;length] to answer string. 618 String::WriteToFlat(*subject, answer->GetChars() + position, prev, 619 subject_length); 620 position += subject_length - prev; 621 } 622 623 if (position == 0) return isolate->heap()->empty_string(); 624 625 // Shorten string and fill 626 int string_size = ResultSeqString::SizeFor(position); 627 int allocated_string_size = ResultSeqString::SizeFor(new_length); 628 int delta = allocated_string_size - string_size; 629 630 answer->set_length(position); 631 if (delta == 0) return *answer; 632 633 Address end_of_string = answer->address() + string_size; 634 Heap* heap = isolate->heap(); 635 636 // The trimming is performed on a newly allocated object, which is on a 637 // fresly allocated page or on an already swept page. Hence, the sweeper 638 // thread can not get confused with the filler creation. No synchronization 639 // needed. 640 // TODO(hpayer): We should shrink the large object page if the size 641 // of the object changed significantly. 642 if (!heap->lo_space()->Contains(*answer)) { 643 heap->CreateFillerObjectAt(end_of_string, delta, ClearRecordedSlots::kNo); 644 } 645 heap->AdjustLiveBytes(*answer, -delta, Heap::CONCURRENT_TO_SWEEPER); 646 return *answer; 647 } 648 649 650 RUNTIME_FUNCTION(Runtime_StringReplaceGlobalRegExpWithString) { 651 HandleScope scope(isolate); 652 DCHECK(args.length() == 4); 653 654 CONVERT_ARG_HANDLE_CHECKED(String, subject, 0); 655 CONVERT_ARG_HANDLE_CHECKED(String, replacement, 2); 656 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1); 657 CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 3); 658 659 CHECK(regexp->GetFlags() & JSRegExp::kGlobal); 660 CHECK(last_match_info->HasFastObjectElements()); 661 662 subject = String::Flatten(subject); 663 664 if (replacement->length() == 0) { 665 if (subject->HasOnlyOneByteChars()) { 666 return StringReplaceGlobalRegExpWithEmptyString<SeqOneByteString>( 667 isolate, subject, regexp, last_match_info); 668 } else { 669 return StringReplaceGlobalRegExpWithEmptyString<SeqTwoByteString>( 670 isolate, subject, regexp, last_match_info); 671 } 672 } 673 674 replacement = String::Flatten(replacement); 675 676 return StringReplaceGlobalRegExpWithString(isolate, subject, regexp, 677 replacement, last_match_info); 678 } 679 680 681 RUNTIME_FUNCTION(Runtime_StringSplit) { 682 HandleScope handle_scope(isolate); 683 DCHECK(args.length() == 3); 684 CONVERT_ARG_HANDLE_CHECKED(String, subject, 0); 685 CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1); 686 CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]); 687 CHECK(limit > 0); 688 689 int subject_length = subject->length(); 690 int pattern_length = pattern->length(); 691 CHECK(pattern_length > 0); 692 693 if (limit == 0xffffffffu) { 694 FixedArray* last_match_cache_unused; 695 Handle<Object> cached_answer( 696 RegExpResultsCache::Lookup(isolate->heap(), *subject, *pattern, 697 &last_match_cache_unused, 698 RegExpResultsCache::STRING_SPLIT_SUBSTRINGS), 699 isolate); 700 if (*cached_answer != Smi::FromInt(0)) { 701 // The cache FixedArray is a COW-array and can therefore be reused. 702 Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements( 703 Handle<FixedArray>::cast(cached_answer)); 704 return *result; 705 } 706 } 707 708 // The limit can be very large (0xffffffffu), but since the pattern 709 // isn't empty, we can never create more parts than ~half the length 710 // of the subject. 711 712 subject = String::Flatten(subject); 713 pattern = String::Flatten(pattern); 714 715 static const int kMaxInitialListCapacity = 16; 716 717 ZoneScope zone_scope(isolate->runtime_zone()); 718 719 // Find (up to limit) indices of separator and end-of-string in subject 720 int initial_capacity = Min<uint32_t>(kMaxInitialListCapacity, limit); 721 ZoneList<int> indices(initial_capacity, zone_scope.zone()); 722 723 FindStringIndicesDispatch(isolate, *subject, *pattern, &indices, limit, 724 zone_scope.zone()); 725 726 if (static_cast<uint32_t>(indices.length()) < limit) { 727 indices.Add(subject_length, zone_scope.zone()); 728 } 729 730 // The list indices now contains the end of each part to create. 731 732 // Create JSArray of substrings separated by separator. 733 int part_count = indices.length(); 734 735 Handle<JSArray> result = 736 isolate->factory()->NewJSArray(FAST_ELEMENTS, part_count, part_count, 737 INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE); 738 739 DCHECK(result->HasFastObjectElements()); 740 741 Handle<FixedArray> elements(FixedArray::cast(result->elements())); 742 743 if (part_count == 1 && indices.at(0) == subject_length) { 744 elements->set(0, *subject); 745 } else { 746 int part_start = 0; 747 FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < part_count, i++, { 748 int part_end = indices.at(i); 749 Handle<String> substring = 750 isolate->factory()->NewProperSubString(subject, part_start, part_end); 751 elements->set(i, *substring); 752 part_start = part_end + pattern_length; 753 }); 754 } 755 756 if (limit == 0xffffffffu) { 757 if (result->HasFastObjectElements()) { 758 RegExpResultsCache::Enter(isolate, subject, pattern, elements, 759 isolate->factory()->empty_fixed_array(), 760 RegExpResultsCache::STRING_SPLIT_SUBSTRINGS); 761 } 762 } 763 764 return *result; 765 } 766 767 768 RUNTIME_FUNCTION(Runtime_RegExpExec) { 769 HandleScope scope(isolate); 770 DCHECK(args.length() == 4); 771 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0); 772 CONVERT_ARG_HANDLE_CHECKED(String, subject, 1); 773 CONVERT_INT32_ARG_CHECKED(index, 2); 774 CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 3); 775 // Due to the way the JS calls are constructed this must be less than the 776 // length of a string, i.e. it is always a Smi. We check anyway for security. 777 CHECK(index >= 0); 778 CHECK(index <= subject->length()); 779 isolate->counters()->regexp_entry_runtime()->Increment(); 780 RETURN_RESULT_OR_FAILURE( 781 isolate, RegExpImpl::Exec(regexp, subject, index, last_match_info)); 782 } 783 784 785 RUNTIME_FUNCTION(Runtime_RegExpFlags) { 786 SealHandleScope shs(isolate); 787 DCHECK(args.length() == 1); 788 CONVERT_ARG_CHECKED(JSRegExp, regexp, 0); 789 return regexp->flags(); 790 } 791 792 793 RUNTIME_FUNCTION(Runtime_RegExpSource) { 794 SealHandleScope shs(isolate); 795 DCHECK(args.length() == 1); 796 CONVERT_ARG_CHECKED(JSRegExp, regexp, 0); 797 return regexp->source(); 798 } 799 800 801 RUNTIME_FUNCTION(Runtime_RegExpConstructResult) { 802 HandleScope handle_scope(isolate); 803 DCHECK(args.length() == 3); 804 CONVERT_SMI_ARG_CHECKED(size, 0); 805 CHECK(size >= 0 && size <= FixedArray::kMaxLength); 806 CONVERT_ARG_HANDLE_CHECKED(Object, index, 1); 807 CONVERT_ARG_HANDLE_CHECKED(Object, input, 2); 808 Handle<FixedArray> elements = isolate->factory()->NewFixedArray(size); 809 Handle<Map> regexp_map(isolate->native_context()->regexp_result_map()); 810 Handle<JSObject> object = 811 isolate->factory()->NewJSObjectFromMap(regexp_map, NOT_TENURED); 812 Handle<JSArray> array = Handle<JSArray>::cast(object); 813 array->set_elements(*elements); 814 array->set_length(Smi::FromInt(size)); 815 // Write in-object properties after the length of the array. 816 array->InObjectPropertyAtPut(JSRegExpResult::kIndexIndex, *index); 817 array->InObjectPropertyAtPut(JSRegExpResult::kInputIndex, *input); 818 return *array; 819 } 820 821 822 RUNTIME_FUNCTION(Runtime_RegExpInitializeAndCompile) { 823 HandleScope scope(isolate); 824 DCHECK(args.length() == 3); 825 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0); 826 CONVERT_ARG_HANDLE_CHECKED(String, source, 1); 827 CONVERT_ARG_HANDLE_CHECKED(String, flags, 2); 828 829 RETURN_FAILURE_ON_EXCEPTION(isolate, 830 JSRegExp::Initialize(regexp, source, flags)); 831 832 return *regexp; 833 } 834 835 836 // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain 837 // separate last match info. See comment on that function. 838 template <bool has_capture> 839 static Object* SearchRegExpMultiple(Isolate* isolate, Handle<String> subject, 840 Handle<JSRegExp> regexp, 841 Handle<JSArray> last_match_array, 842 Handle<JSArray> result_array) { 843 DCHECK(subject->IsFlat()); 844 DCHECK_NE(has_capture, regexp->CaptureCount() == 0); 845 846 int capture_count = regexp->CaptureCount(); 847 int subject_length = subject->length(); 848 849 static const int kMinLengthToCache = 0x1000; 850 851 if (subject_length > kMinLengthToCache) { 852 FixedArray* last_match_cache; 853 Object* cached_answer = RegExpResultsCache::Lookup( 854 isolate->heap(), *subject, regexp->data(), &last_match_cache, 855 RegExpResultsCache::REGEXP_MULTIPLE_INDICES); 856 if (cached_answer->IsFixedArray()) { 857 int capture_registers = (capture_count + 1) * 2; 858 int32_t* last_match = NewArray<int32_t>(capture_registers); 859 for (int i = 0; i < capture_registers; i++) { 860 last_match[i] = Smi::cast(last_match_cache->get(i))->value(); 861 } 862 Handle<FixedArray> cached_fixed_array = 863 Handle<FixedArray>(FixedArray::cast(cached_answer)); 864 // The cache FixedArray is a COW-array and can therefore be reused. 865 JSArray::SetContent(result_array, cached_fixed_array); 866 RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count, 867 last_match); 868 DeleteArray(last_match); 869 return *result_array; 870 } 871 } 872 873 RegExpImpl::GlobalCache global_cache(regexp, subject, isolate); 874 if (global_cache.HasException()) return isolate->heap()->exception(); 875 876 // Ensured in Runtime_RegExpExecMultiple. 877 DCHECK(result_array->HasFastObjectElements()); 878 Handle<FixedArray> result_elements( 879 FixedArray::cast(result_array->elements())); 880 if (result_elements->length() < 16) { 881 result_elements = isolate->factory()->NewFixedArrayWithHoles(16); 882 } 883 884 FixedArrayBuilder builder(result_elements); 885 886 // Position to search from. 887 int match_start = -1; 888 int match_end = 0; 889 bool first = true; 890 891 // Two smis before and after the match, for very long strings. 892 static const int kMaxBuilderEntriesPerRegExpMatch = 5; 893 894 while (true) { 895 int32_t* current_match = global_cache.FetchNext(); 896 if (current_match == NULL) break; 897 match_start = current_match[0]; 898 builder.EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch); 899 if (match_end < match_start) { 900 ReplacementStringBuilder::AddSubjectSlice(&builder, match_end, 901 match_start); 902 } 903 match_end = current_match[1]; 904 { 905 // Avoid accumulating new handles inside loop. 906 HandleScope temp_scope(isolate); 907 Handle<String> match; 908 if (!first) { 909 match = isolate->factory()->NewProperSubString(subject, match_start, 910 match_end); 911 } else { 912 match = 913 isolate->factory()->NewSubString(subject, match_start, match_end); 914 first = false; 915 } 916 917 if (has_capture) { 918 // Arguments array to replace function is match, captures, index and 919 // subject, i.e., 3 + capture count in total. 920 Handle<FixedArray> elements = 921 isolate->factory()->NewFixedArray(3 + capture_count); 922 923 elements->set(0, *match); 924 for (int i = 1; i <= capture_count; i++) { 925 int start = current_match[i * 2]; 926 if (start >= 0) { 927 int end = current_match[i * 2 + 1]; 928 DCHECK(start <= end); 929 Handle<String> substring = 930 isolate->factory()->NewSubString(subject, start, end); 931 elements->set(i, *substring); 932 } else { 933 DCHECK(current_match[i * 2 + 1] < 0); 934 elements->set(i, isolate->heap()->undefined_value()); 935 } 936 } 937 elements->set(capture_count + 1, Smi::FromInt(match_start)); 938 elements->set(capture_count + 2, *subject); 939 builder.Add(*isolate->factory()->NewJSArrayWithElements(elements)); 940 } else { 941 builder.Add(*match); 942 } 943 } 944 } 945 946 if (global_cache.HasException()) return isolate->heap()->exception(); 947 948 if (match_start >= 0) { 949 // Finished matching, with at least one match. 950 if (match_end < subject_length) { 951 ReplacementStringBuilder::AddSubjectSlice(&builder, match_end, 952 subject_length); 953 } 954 955 RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count, 956 global_cache.LastSuccessfulMatch()); 957 958 if (subject_length > kMinLengthToCache) { 959 // Store the last successful match into the array for caching. 960 // TODO(yangguo): do not expose last match to JS and simplify caching. 961 int capture_registers = (capture_count + 1) * 2; 962 Handle<FixedArray> last_match_cache = 963 isolate->factory()->NewFixedArray(capture_registers); 964 int32_t* last_match = global_cache.LastSuccessfulMatch(); 965 for (int i = 0; i < capture_registers; i++) { 966 last_match_cache->set(i, Smi::FromInt(last_match[i])); 967 } 968 Handle<FixedArray> result_fixed_array = builder.array(); 969 result_fixed_array->Shrink(builder.length()); 970 // Cache the result and turn the FixedArray into a COW array. 971 RegExpResultsCache::Enter( 972 isolate, subject, handle(regexp->data(), isolate), result_fixed_array, 973 last_match_cache, RegExpResultsCache::REGEXP_MULTIPLE_INDICES); 974 } 975 return *builder.ToJSArray(result_array); 976 } else { 977 return isolate->heap()->null_value(); // No matches at all. 978 } 979 } 980 981 982 // This is only called for StringReplaceGlobalRegExpWithFunction. This sets 983 // lastMatchInfoOverride to maintain the last match info, so we don't need to 984 // set any other last match array info. 985 RUNTIME_FUNCTION(Runtime_RegExpExecMultiple) { 986 HandleScope handles(isolate); 987 DCHECK(args.length() == 4); 988 989 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0); 990 CONVERT_ARG_HANDLE_CHECKED(String, subject, 1); 991 CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2); 992 CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3); 993 CHECK(last_match_info->HasFastObjectElements()); 994 CHECK(result_array->HasFastObjectElements()); 995 996 subject = String::Flatten(subject); 997 CHECK(regexp->GetFlags() & JSRegExp::kGlobal); 998 999 if (regexp->CaptureCount() == 0) { 1000 return SearchRegExpMultiple<false>(isolate, subject, regexp, 1001 last_match_info, result_array); 1002 } else { 1003 return SearchRegExpMultiple<true>(isolate, subject, regexp, last_match_info, 1004 result_array); 1005 } 1006 } 1007 1008 1009 RUNTIME_FUNCTION(Runtime_RegExpExecReThrow) { 1010 SealHandleScope shs(isolate); 1011 DCHECK(args.length() == 4); 1012 Object* exception = isolate->pending_exception(); 1013 isolate->clear_pending_exception(); 1014 return isolate->ReThrow(exception); 1015 } 1016 1017 1018 RUNTIME_FUNCTION(Runtime_IsRegExp) { 1019 SealHandleScope shs(isolate); 1020 DCHECK(args.length() == 1); 1021 CONVERT_ARG_CHECKED(Object, obj, 0); 1022 return isolate->heap()->ToBoolean(obj->IsJSRegExp()); 1023 } 1024 } // namespace internal 1025 } // namespace v8 1026