src/runtime/runtime-strings.cc - v8/v8 - Git at Google

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "src/execution/arguments-inl.h"
 #include "src/heap/heap-inl.h"
 #include "src/logging/counters.h"
 #include "src/numbers/conversions.h"
 #include "src/objects/js-array-inl.h"
 #include "src/objects/objects-inl.h"
 #include "src/objects/slots.h"
 #include "src/objects/smi.h"
 #include "src/regexp/regexp-utils.h"
 #include "src/runtime/runtime-utils.h"
 #include "src/strings/string-builder-inl.h"
 #include "src/strings/string-search.h"

 namespace v8 {
 namespace internal {

 RUNTIME_FUNCTION(Runtime_GetSubstitution) {
   HandleScope scope(isolate);
   DCHECK_EQ(5, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, matched, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
   CONVERT_SMI_ARG_CHECKED(position, 2);
   CONVERT_ARG_HANDLE_CHECKED(String, replacement, 3);
   CONVERT_SMI_ARG_CHECKED(start_index, 4);

   // A simple match without captures.
   class SimpleMatch : public String::Match {
    public:
     SimpleMatch(Handle<String> match, Handle<String> prefix,
                 Handle<String> suffix)
         : match_(match), prefix_(prefix), suffix_(suffix) {}

     Handle<String> GetMatch() override { return match_; }
     Handle<String> GetPrefix() override { return prefix_; }
     Handle<String> GetSuffix() override { return suffix_; }

     int CaptureCount() override { return 0; }
     bool HasNamedCaptures() override { return false; }
     MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
       *capture_exists = false;
       return match_;  // Return arbitrary string handle.
     }
     MaybeHandle<String> GetNamedCapture(Handle<String> name,
                                         CaptureState* state) override {
       UNREACHABLE();
     }

    private:
     Handle<String> match_, prefix_, suffix_;
   };

   Handle<String> prefix =
       isolate->factory()->NewSubString(subject, 0, position);
   Handle<String> suffix = isolate->factory()->NewSubString(
       subject, position + matched->length(), subject->length());
   SimpleMatch match(matched, prefix, suffix);

   RETURN_RESULT_OR_FAILURE(
       isolate,
       String::GetSubstitution(isolate, &match, replacement, start_index));
 }

 // This may return an empty MaybeHandle if an exception is thrown or
 // we abort due to reaching the recursion limit.
 MaybeHandle<String> StringReplaceOneCharWithString(
     Isolate* isolate, Handle<String> subject, Handle<String> search,
     Handle<String> replace, bool* found, int recursion_limit) {
   StackLimitCheck stackLimitCheck(isolate);
   if (stackLimitCheck.HasOverflowed() || (recursion_limit == 0)) {
     return MaybeHandle<String>();
   }
   recursion_limit--;
   if (subject->IsConsString()) {
     ConsString cons = ConsString::cast(*subject);
     Handle<String> first = handle(cons.first(), isolate);
     Handle<String> second = handle(cons.second(), isolate);
     Handle<String> new_first;
     if (!StringReplaceOneCharWithString(isolate, first, search, replace, found,
                                         recursion_limit).ToHandle(&new_first)) {
       return MaybeHandle<String>();
     }
     if (*found) return isolate->factory()->NewConsString(new_first, second);

     Handle<String> new_second;
     if (!StringReplaceOneCharWithString(isolate, second, search, replace, found,
                                         recursion_limit)
              .ToHandle(&new_second)) {
       return MaybeHandle<String>();
     }
     if (*found) return isolate->factory()->NewConsString(first, new_second);

     return subject;
   } else {
     int index = String::IndexOf(isolate, subject, search, 0);
     if (index == -1) return subject;
     *found = true;
     Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
     Handle<String> cons1;
     ASSIGN_RETURN_ON_EXCEPTION(
         isolate, cons1, isolate->factory()->NewConsString(first, replace),
         String);
     Handle<String> second =
         isolate->factory()->NewSubString(subject, index + 1, subject->length());
     return isolate->factory()->NewConsString(cons1, second);
   }
 }

 RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, search, 1);
   CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);

   // If the cons string tree is too deep, we simply abort the recursion and
   // retry with a flattened subject string.
   const int kRecursionLimit = 0x1000;
   bool found = false;
   Handle<String> result;
   if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
                                      kRecursionLimit).ToHandle(&result)) {
     return *result;
   }
   if (isolate->has_pending_exception())
     return ReadOnlyRoots(isolate).exception();

   subject = String::Flatten(isolate, subject);
   if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
                                      kRecursionLimit).ToHandle(&result)) {
     return *result;
   }
   if (isolate->has_pending_exception())
     return ReadOnlyRoots(isolate).exception();
   // In case of empty handle and no pending exception we have stack overflow.
   return isolate->StackOverflow();
 }

 RUNTIME_FUNCTION(Runtime_StringTrim) {
   HandleScope scope(isolate);
   DCHECK_EQ(2, args.length());
   Handle<String> string = args.at<String>(0);
   CONVERT_SMI_ARG_CHECKED(mode, 1);
   String::TrimMode trim_mode = static_cast<String::TrimMode>(mode);
   return *String::Trim(isolate, string, trim_mode);
 }

 // ES6 #sec-string.prototype.includes
 // String.prototype.includes(searchString [, position])
 RUNTIME_FUNCTION(Runtime_StringIncludes) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());

   Handle<Object> receiver = args.at(0);
   if (receiver->IsNullOrUndefined(isolate)) {
     THROW_NEW_ERROR_RETURN_FAILURE(
         isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
                               isolate->factory()->NewStringFromAsciiChecked(
                                   "String.prototype.includes")));
   }
   Handle<String> receiver_string;
   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
                                      Object::ToString(isolate, receiver));

   // Check if the search string is a regExp and fail if it is.
   Handle<Object> search = args.at(1);
   Maybe<bool> is_reg_exp = RegExpUtils::IsRegExp(isolate, search);
   if (is_reg_exp.IsNothing()) {
     DCHECK(isolate->has_pending_exception());
     return ReadOnlyRoots(isolate).exception();
   }
   if (is_reg_exp.FromJust()) {
     THROW_NEW_ERROR_RETURN_FAILURE(
         isolate, NewTypeError(MessageTemplate::kFirstArgumentNotRegExp,
                               isolate->factory()->NewStringFromStaticChars(
                                   "String.prototype.includes")));
   }
   Handle<String> search_string;
   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
                                      Object::ToString(isolate, args.at(1)));
   Handle<Object> position;
   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
                                      Object::ToInteger(isolate, args.at(2)));

   uint32_t index = receiver_string->ToValidIndex(*position);
   int index_in_str =
       String::IndexOf(isolate, receiver_string, search_string, index);
   return *isolate->factory()->ToBoolean(index_in_str != -1);
 }

 // ES6 #sec-string.prototype.indexof
 // String.prototype.indexOf(searchString [, position])
 RUNTIME_FUNCTION(Runtime_StringIndexOf) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());
   return String::IndexOf(isolate, args.at(0), args.at(1), args.at(2));
 }

 // ES6 #sec-string.prototype.indexof
 // String.prototype.indexOf(searchString, position)
 // Fast version that assumes that does not perform conversions of the incoming
 // arguments.
 RUNTIME_FUNCTION(Runtime_StringIndexOfUnchecked) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());
   Handle<String> receiver_string = args.at<String>(0);
   Handle<String> search_string = args.at<String>(1);
   int index = std::min(std::max(args.smi_at(2), 0), receiver_string->length());

   return Smi::FromInt(String::IndexOf(isolate, receiver_string, search_string,
                                       static_cast<uint32_t>(index)));
 }

 RUNTIME_FUNCTION(Runtime_StringLastIndexOf) {
   HandleScope handle_scope(isolate);
   return String::LastIndexOf(isolate, args.at(0), args.at(1),
                              isolate->factory()->undefined_value());
 }

 RUNTIME_FUNCTION(Runtime_StringSubstring) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
   CONVERT_INT32_ARG_CHECKED(start, 1);
   CONVERT_INT32_ARG_CHECKED(end, 2);
   DCHECK_LE(0, start);
   DCHECK_LE(start, end);
   DCHECK_LE(end, string->length());
   isolate->counters()->sub_string_runtime()->Increment();
   return *isolate->factory()->NewSubString(string, start, end);
 }

 RUNTIME_FUNCTION(Runtime_StringAdd) {
   HandleScope scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, str1, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, str2, 1);
   isolate->counters()->string_add_runtime()->Increment();
   RETURN_RESULT_OR_FAILURE(isolate,
                            isolate->factory()->NewConsString(str1, str2));
 }


 RUNTIME_FUNCTION(Runtime_InternalizeString) {
   HandleScope handles(isolate);
   DCHECK_EQ(1, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
   return *isolate->factory()->InternalizeString(string);
 }

 RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());

   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
   CONVERT_NUMBER_CHECKED(uint32_t, i, Uint32, args[1]);

   // Flatten the string.  If someone wants to get a char at an index
   // in a cons string, it is likely that more indices will be
   // accessed.
   subject = String::Flatten(isolate, subject);

   if (i >= static_cast<uint32_t>(subject->length())) {
     return ReadOnlyRoots(isolate).nan_value();
   }

   return Smi::FromInt(subject->Get(i));
 }

 RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
   HandleScope scope(isolate);
   DCHECK_EQ(3, args.length());
   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
   int32_t array_length;
   if (!args[1].ToInt32(&array_length)) {
     THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
   }
   CONVERT_ARG_HANDLE_CHECKED(String, special, 2);

   size_t actual_array_length = 0;
   CHECK(TryNumberToSize(array->length(), &actual_array_length));
   CHECK_GE(array_length, 0);
   CHECK(static_cast<size_t>(array_length) <= actual_array_length);

   // This assumption is used by the slice encoding in one or two smis.
   DCHECK_GE(Smi::kMaxValue, String::kMaxLength);

   CHECK(array->HasFastElements());
   JSObject::EnsureCanContainHeapObjectElements(array);

   int special_length = special->length();
   if (!array->HasObjectElements()) {
     return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
   }

   int length;
   bool one_byte = special->IsOneByteRepresentation();

   {
     DisallowHeapAllocation no_gc;
     FixedArray fixed_array = FixedArray::cast(array->elements());
     if (fixed_array.length() < array_length) {
       array_length = fixed_array.length();
     }

     if (array_length == 0) {
       return ReadOnlyRoots(isolate).empty_string();
     } else if (array_length == 1) {
       Object first = fixed_array.get(0);
       if (first.IsString()) return first;
     }
     length = StringBuilderConcatLength(special_length, fixed_array,
                                        array_length, &one_byte);
   }

   if (length == -1) {
     return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
   }
   if (length == 0) {
     return ReadOnlyRoots(isolate).empty_string();
   }

   if (one_byte) {
     Handle<SeqOneByteString> answer;
     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
         isolate, answer, isolate->factory()->NewRawOneByteString(length));
     DisallowHeapAllocation no_gc;
     StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
                               FixedArray::cast(array->elements()),
                               array_length);
     return *answer;
   } else {
     Handle<SeqTwoByteString> answer;
     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
         isolate, answer, isolate->factory()->NewRawTwoByteString(length));
     DisallowHeapAllocation no_gc;
     StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
                               FixedArray::cast(array->elements()),
                               array_length);
     return *answer;
   }
 }


 // Copies Latin1 characters to the given fixed array looking up
 // one-char strings in the cache. Gives up on the first char that is
 // not in the cache and fills the remainder with smi zeros. Returns
 // the length of the successfully copied prefix.
 static int CopyCachedOneByteCharsToArray(Heap* heap, const uint8_t* chars,
                                          FixedArray elements, int length) {
   DisallowHeapAllocation no_gc;
   FixedArray one_byte_cache = heap->single_character_string_cache();
   Object undefined = ReadOnlyRoots(heap).undefined_value();
   int i;
   WriteBarrierMode mode = elements.GetWriteBarrierMode(no_gc);
   for (i = 0; i < length; ++i) {
     Object value = one_byte_cache.get(chars[i]);
     if (value == undefined) break;
     elements.set(i, value, mode);
   }
   if (i < length) {
     MemsetTagged(elements.RawFieldOfElementAt(i), Smi::zero(), length - i);
   }
 #ifdef DEBUG
   for (int j = 0; j < length; ++j) {
     Object element = elements.get(j);
     DCHECK(element == Smi::zero() ||
            (element.IsString() && String::cast(element).LooksValid()));
   }
 #endif
   return i;
 }

 // Converts a String to JSArray.
 // For example, "foo" => ["f", "o", "o"].
 RUNTIME_FUNCTION(Runtime_StringToArray) {
   HandleScope scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
   CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);

   s = String::Flatten(isolate, s);
   const int length = static_cast<int>(Min<uint32_t>(s->length(), limit));

   Handle<FixedArray> elements;
   int position = 0;
   if (s->IsFlat() && s->IsOneByteRepresentation()) {
     // Try using cached chars where possible.
     elements = isolate->factory()->NewUninitializedFixedArray(length);

     DisallowHeapAllocation no_gc;
     String::FlatContent content = s->GetFlatContent(no_gc);
     if (content.IsOneByte()) {
       Vector<const uint8_t> chars = content.ToOneByteVector();
       // Note, this will initialize all elements (not only the prefix)
       // to prevent GC from seeing partially initialized array.
       position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.begin(),
                                                *elements, length);
     } else {
       MemsetTagged(elements->data_start(),
                    ReadOnlyRoots(isolate).undefined_value(), length);
     }
   } else {
     elements = isolate->factory()->NewFixedArray(length);
   }
   for (int i = position; i < length; ++i) {
     Handle<Object> str =
         isolate->factory()->LookupSingleCharacterStringFromCode(s->Get(i));
     elements->set(i, *str);
   }

 #ifdef DEBUG
   for (int i = 0; i < length; ++i) {
     DCHECK_EQ(String::cast(elements->get(i)).length(), 1);
   }
 #endif

   return *isolate->factory()->NewJSArrayWithElements(elements);
 }

 RUNTIME_FUNCTION(Runtime_StringLessThan) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
   ComparisonResult result = String::Compare(isolate, x, y);
   DCHECK_NE(result, ComparisonResult::kUndefined);
   return isolate->heap()->ToBoolean(
       ComparisonResultToBool(Operation::kLessThan, result));
 }

 RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
   ComparisonResult result = String::Compare(isolate, x, y);
   DCHECK_NE(result, ComparisonResult::kUndefined);
   return isolate->heap()->ToBoolean(
       ComparisonResultToBool(Operation::kLessThanOrEqual, result));
 }

 RUNTIME_FUNCTION(Runtime_StringGreaterThan) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
   ComparisonResult result = String::Compare(isolate, x, y);
   DCHECK_NE(result, ComparisonResult::kUndefined);
   return isolate->heap()->ToBoolean(
       ComparisonResultToBool(Operation::kGreaterThan, result));
 }

 RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
   ComparisonResult result = String::Compare(isolate, x, y);
   DCHECK_NE(result, ComparisonResult::kUndefined);
   return isolate->heap()->ToBoolean(
       ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
 }

 RUNTIME_FUNCTION(Runtime_StringEqual) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
   return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
 }

 RUNTIME_FUNCTION(Runtime_FlattenString) {
   HandleScope scope(isolate);
   DCHECK_EQ(1, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
   return *String::Flatten(isolate, str);
 }

 RUNTIME_FUNCTION(Runtime_StringMaxLength) {
   SealHandleScope shs(isolate);
   return Smi::FromInt(String::kMaxLength);
 }

 RUNTIME_FUNCTION(Runtime_StringCompareSequence) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(3, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, search_string, 1);
   CONVERT_NUMBER_CHECKED(int, start, Int32, args[2]);

   // Check if start + searchLength is in bounds.
   DCHECK_LE(start + search_string->length(), string->length());

   FlatStringReader string_reader(isolate, String::Flatten(isolate, string));
   FlatStringReader search_reader(isolate,
                                  String::Flatten(isolate, search_string));

   for (int i = 0; i < search_string->length(); i++) {
     if (string_reader.Get(start + i) != search_reader.Get(i)) {
       return ReadOnlyRoots(isolate).false_value();
     }
   }

   return ReadOnlyRoots(isolate).true_value();
 }

 RUNTIME_FUNCTION(Runtime_StringEscapeQuotes) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(1, args.length());
   CONVERT_ARG_HANDLE_CHECKED(String, string, 0);

   // Equivalent to global replacement `string.replace(/"/g, "&quot")`, but this
   // does not modify any global state (e.g. the regexp match info).

   const int string_length = string->length();
   Handle<String> quotes =
       isolate->factory()->LookupSingleCharacterStringFromCode('"');

   int index = String::IndexOf(isolate, string, quotes, 0);

   // No quotes, nothing to do.
   if (index == -1) return *string;

   // Find all quotes.
   std::vector<int> indices = {index};
   while (index + 1 < string_length) {
     index = String::IndexOf(isolate, string, quotes, index + 1);
     if (index == -1) break;
     indices.emplace_back(index);
   }

   // Build the replacement string.
   Handle<String> replacement =
       isolate->factory()->NewStringFromAsciiChecked("&quot;");
   const int estimated_part_count = static_cast<int>(indices.size()) * 2 + 1;
   ReplacementStringBuilder builder(isolate->heap(), string,
                                    estimated_part_count);

   int prev_index = -1;  // Start at -1 to avoid special-casing the first match.
   for (int index : indices) {
     const int slice_start = prev_index + 1;
     const int slice_end = index;
     if (slice_end > slice_start) {
       builder.AddSubjectSlice(slice_start, slice_end);
     }
     builder.AddString(replacement);
     prev_index = index;
   }

   if (prev_index < string_length - 1) {
     builder.AddSubjectSlice(prev_index + 1, string_length);
   }

   return *builder.ToString().ToHandleChecked();
 }

 }  // namespace internal
 }  // namespace v8
	// Copyright 2014 the V8 project authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "src/execution/arguments-inl.h"
	#include "src/heap/heap-inl.h"
	#include "src/logging/counters.h"
	#include "src/numbers/conversions.h"
	#include "src/objects/js-array-inl.h"
	#include "src/objects/objects-inl.h"
	#include "src/objects/slots.h"
	#include "src/objects/smi.h"
	#include "src/regexp/regexp-utils.h"
	#include "src/runtime/runtime-utils.h"
	#include "src/strings/string-builder-inl.h"
	#include "src/strings/string-search.h"

	namespace v8 {
	namespace internal {

	RUNTIME_FUNCTION(Runtime_GetSubstitution) {
	HandleScope scope(isolate);
	DCHECK_EQ(5, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, matched, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
	CONVERT_SMI_ARG_CHECKED(position, 2);
	CONVERT_ARG_HANDLE_CHECKED(String, replacement, 3);
	CONVERT_SMI_ARG_CHECKED(start_index, 4);

	// A simple match without captures.
	class SimpleMatch : public String::Match {
	public:
	SimpleMatch(Handle<String> match, Handle<String> prefix,
	Handle<String> suffix)
	: match_(match), prefix_(prefix), suffix_(suffix) {}

	Handle<String> GetMatch() override { return match_; }
	Handle<String> GetPrefix() override { return prefix_; }
	Handle<String> GetSuffix() override { return suffix_; }

	int CaptureCount() override { return 0; }
	bool HasNamedCaptures() override { return false; }
	MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
	*capture_exists = false;
	return match_; // Return arbitrary string handle.
	}
	MaybeHandle<String> GetNamedCapture(Handle<String> name,
	CaptureState* state) override {
	UNREACHABLE();
	}

	private:
	Handle<String> match_, prefix_, suffix_;
	};

	Handle<String> prefix =
	isolate->factory()->NewSubString(subject, 0, position);
	Handle<String> suffix = isolate->factory()->NewSubString(
	subject, position + matched->length(), subject->length());
	SimpleMatch match(matched, prefix, suffix);

	RETURN_RESULT_OR_FAILURE(
	isolate,
	String::GetSubstitution(isolate, &match, replacement, start_index));
	}

	// This may return an empty MaybeHandle if an exception is thrown or
	// we abort due to reaching the recursion limit.
	MaybeHandle<String> StringReplaceOneCharWithString(
	Isolate* isolate, Handle<String> subject, Handle<String> search,
	Handle<String> replace, bool* found, int recursion_limit) {
	StackLimitCheck stackLimitCheck(isolate);
	if (stackLimitCheck.HasOverflowed() \|\| (recursion_limit == 0)) {
	return MaybeHandle<String>();
	}
	recursion_limit--;
	if (subject->IsConsString()) {
	ConsString cons = ConsString::cast(*subject);
	Handle<String> first = handle(cons.first(), isolate);
	Handle<String> second = handle(cons.second(), isolate);
	Handle<String> new_first;
	if (!StringReplaceOneCharWithString(isolate, first, search, replace, found,
	recursion_limit).ToHandle(&new_first)) {
	return MaybeHandle<String>();
	}
	if (*found) return isolate->factory()->NewConsString(new_first, second);

	Handle<String> new_second;
	if (!StringReplaceOneCharWithString(isolate, second, search, replace, found,
	recursion_limit)
	.ToHandle(&new_second)) {
	return MaybeHandle<String>();
	}
	if (*found) return isolate->factory()->NewConsString(first, new_second);

	return subject;
	} else {
	int index = String::IndexOf(isolate, subject, search, 0);
	if (index == -1) return subject;
	*found = true;
	Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
	Handle<String> cons1;
	ASSIGN_RETURN_ON_EXCEPTION(
	isolate, cons1, isolate->factory()->NewConsString(first, replace),
	String);
	Handle<String> second =
	isolate->factory()->NewSubString(subject, index + 1, subject->length());
	return isolate->factory()->NewConsString(cons1, second);
	}
	}

	RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, search, 1);
	CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);

	// If the cons string tree is too deep, we simply abort the recursion and
	// retry with a flattened subject string.
	const int kRecursionLimit = 0x1000;
	bool found = false;
	Handle<String> result;
	if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
	kRecursionLimit).ToHandle(&result)) {
	return *result;
	}
	if (isolate->has_pending_exception())
	return ReadOnlyRoots(isolate).exception();

	subject = String::Flatten(isolate, subject);
	if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
	kRecursionLimit).ToHandle(&result)) {
	return *result;
	}
	if (isolate->has_pending_exception())
	return ReadOnlyRoots(isolate).exception();
	// In case of empty handle and no pending exception we have stack overflow.
	return isolate->StackOverflow();
	}

	RUNTIME_FUNCTION(Runtime_StringTrim) {
	HandleScope scope(isolate);
	DCHECK_EQ(2, args.length());
	Handle<String> string = args.at<String>(0);
	CONVERT_SMI_ARG_CHECKED(mode, 1);
	String::TrimMode trim_mode = static_cast<String::TrimMode>(mode);
	return *String::Trim(isolate, string, trim_mode);
	}

	// ES6 #sec-string.prototype.includes
	// String.prototype.includes(searchString [, position])
	RUNTIME_FUNCTION(Runtime_StringIncludes) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());

	Handle<Object> receiver = args.at(0);
	if (receiver->IsNullOrUndefined(isolate)) {
	THROW_NEW_ERROR_RETURN_FAILURE(
	isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
	isolate->factory()->NewStringFromAsciiChecked(
	"String.prototype.includes")));
	}
	Handle<String> receiver_string;
	ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
	Object::ToString(isolate, receiver));

	// Check if the search string is a regExp and fail if it is.
	Handle<Object> search = args.at(1);
	Maybe<bool> is_reg_exp = RegExpUtils::IsRegExp(isolate, search);
	if (is_reg_exp.IsNothing()) {
	DCHECK(isolate->has_pending_exception());
	return ReadOnlyRoots(isolate).exception();
	}
	if (is_reg_exp.FromJust()) {
	THROW_NEW_ERROR_RETURN_FAILURE(
	isolate, NewTypeError(MessageTemplate::kFirstArgumentNotRegExp,
	isolate->factory()->NewStringFromStaticChars(
	"String.prototype.includes")));
	}
	Handle<String> search_string;
	ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
	Object::ToString(isolate, args.at(1)));
	Handle<Object> position;
	ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
	Object::ToInteger(isolate, args.at(2)));

	uint32_t index = receiver_string->ToValidIndex(*position);
	int index_in_str =
	String::IndexOf(isolate, receiver_string, search_string, index);
	return *isolate->factory()->ToBoolean(index_in_str != -1);
	}

	// ES6 #sec-string.prototype.indexof
	// String.prototype.indexOf(searchString [, position])
	RUNTIME_FUNCTION(Runtime_StringIndexOf) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());
	return String::IndexOf(isolate, args.at(0), args.at(1), args.at(2));
	}

	// ES6 #sec-string.prototype.indexof
	// String.prototype.indexOf(searchString, position)
	// Fast version that assumes that does not perform conversions of the incoming
	// arguments.
	RUNTIME_FUNCTION(Runtime_StringIndexOfUnchecked) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());
	Handle<String> receiver_string = args.at<String>(0);
	Handle<String> search_string = args.at<String>(1);
	int index = std::min(std::max(args.smi_at(2), 0), receiver_string->length());

	return Smi::FromInt(String::IndexOf(isolate, receiver_string, search_string,
	static_cast<uint32_t>(index)));
	}

	RUNTIME_FUNCTION(Runtime_StringLastIndexOf) {
	HandleScope handle_scope(isolate);
	return String::LastIndexOf(isolate, args.at(0), args.at(1),
	isolate->factory()->undefined_value());
	}

	RUNTIME_FUNCTION(Runtime_StringSubstring) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
	CONVERT_INT32_ARG_CHECKED(start, 1);
	CONVERT_INT32_ARG_CHECKED(end, 2);
	DCHECK_LE(0, start);
	DCHECK_LE(start, end);
	DCHECK_LE(end, string->length());
	isolate->counters()->sub_string_runtime()->Increment();
	return *isolate->factory()->NewSubString(string, start, end);
	}

	RUNTIME_FUNCTION(Runtime_StringAdd) {
	HandleScope scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, str1, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, str2, 1);
	isolate->counters()->string_add_runtime()->Increment();
	RETURN_RESULT_OR_FAILURE(isolate,
	isolate->factory()->NewConsString(str1, str2));
	}


	RUNTIME_FUNCTION(Runtime_InternalizeString) {
	HandleScope handles(isolate);
	DCHECK_EQ(1, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
	return *isolate->factory()->InternalizeString(string);
	}

	RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());

	CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
	CONVERT_NUMBER_CHECKED(uint32_t, i, Uint32, args[1]);

	// Flatten the string. If someone wants to get a char at an index
	// in a cons string, it is likely that more indices will be
	// accessed.
	subject = String::Flatten(isolate, subject);

	if (i >= static_cast<uint32_t>(subject->length())) {
	return ReadOnlyRoots(isolate).nan_value();
	}

	return Smi::FromInt(subject->Get(i));
	}

	RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
	HandleScope scope(isolate);
	DCHECK_EQ(3, args.length());
	CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
	int32_t array_length;
	if (!args[1].ToInt32(&array_length)) {
	THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
	}
	CONVERT_ARG_HANDLE_CHECKED(String, special, 2);

	size_t actual_array_length = 0;
	CHECK(TryNumberToSize(array->length(), &actual_array_length));
	CHECK_GE(array_length, 0);
	CHECK(static_cast<size_t>(array_length) <= actual_array_length);

	// This assumption is used by the slice encoding in one or two smis.
	DCHECK_GE(Smi::kMaxValue, String::kMaxLength);

	CHECK(array->HasFastElements());
	JSObject::EnsureCanContainHeapObjectElements(array);

	int special_length = special->length();
	if (!array->HasObjectElements()) {
	return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
	}

	int length;
	bool one_byte = special->IsOneByteRepresentation();

	{
	DisallowHeapAllocation no_gc;
	FixedArray fixed_array = FixedArray::cast(array->elements());
	if (fixed_array.length() < array_length) {
	array_length = fixed_array.length();
	}

	if (array_length == 0) {
	return ReadOnlyRoots(isolate).empty_string();
	} else if (array_length == 1) {
	Object first = fixed_array.get(0);
	if (first.IsString()) return first;
	}
	length = StringBuilderConcatLength(special_length, fixed_array,
	array_length, &one_byte);
	}

	if (length == -1) {
	return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
	}
	if (length == 0) {
	return ReadOnlyRoots(isolate).empty_string();
	}

	if (one_byte) {
	Handle<SeqOneByteString> answer;
	ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
	isolate, answer, isolate->factory()->NewRawOneByteString(length));
	DisallowHeapAllocation no_gc;
	StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
	FixedArray::cast(array->elements()),
	array_length);
	return *answer;
	} else {
	Handle<SeqTwoByteString> answer;
	ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
	isolate, answer, isolate->factory()->NewRawTwoByteString(length));
	DisallowHeapAllocation no_gc;
	StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
	FixedArray::cast(array->elements()),
	array_length);
	return *answer;
	}
	}


	// Copies Latin1 characters to the given fixed array looking up
	// one-char strings in the cache. Gives up on the first char that is
	// not in the cache and fills the remainder with smi zeros. Returns
	// the length of the successfully copied prefix.
	static int CopyCachedOneByteCharsToArray(Heap* heap, const uint8_t* chars,
	FixedArray elements, int length) {
	DisallowHeapAllocation no_gc;
	FixedArray one_byte_cache = heap->single_character_string_cache();
	Object undefined = ReadOnlyRoots(heap).undefined_value();
	int i;
	WriteBarrierMode mode = elements.GetWriteBarrierMode(no_gc);
	for (i = 0; i < length; ++i) {
	Object value = one_byte_cache.get(chars[i]);
	if (value == undefined) break;
	elements.set(i, value, mode);
	}
	if (i < length) {
	MemsetTagged(elements.RawFieldOfElementAt(i), Smi::zero(), length - i);
	}
	#ifdef DEBUG
	for (int j = 0; j < length; ++j) {
	Object element = elements.get(j);
	DCHECK(element == Smi::zero() \|\|
	(element.IsString() && String::cast(element).LooksValid()));
	}
	#endif
	return i;
	}

	// Converts a String to JSArray.
	// For example, "foo" => ["f", "o", "o"].
	RUNTIME_FUNCTION(Runtime_StringToArray) {
	HandleScope scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
	CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);

	s = String::Flatten(isolate, s);
	const int length = static_cast<int>(Min<uint32_t>(s->length(), limit));

	Handle<FixedArray> elements;
	int position = 0;
	if (s->IsFlat() && s->IsOneByteRepresentation()) {
	// Try using cached chars where possible.
	elements = isolate->factory()->NewUninitializedFixedArray(length);

	DisallowHeapAllocation no_gc;
	String::FlatContent content = s->GetFlatContent(no_gc);
	if (content.IsOneByte()) {
	Vector<const uint8_t> chars = content.ToOneByteVector();
	// Note, this will initialize all elements (not only the prefix)
	// to prevent GC from seeing partially initialized array.
	position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.begin(),
	*elements, length);
	} else {
	MemsetTagged(elements->data_start(),
	ReadOnlyRoots(isolate).undefined_value(), length);
	}
	} else {
	elements = isolate->factory()->NewFixedArray(length);
	}
	for (int i = position; i < length; ++i) {
	Handle<Object> str =
	isolate->factory()->LookupSingleCharacterStringFromCode(s->Get(i));
	elements->set(i, *str);
	}

	#ifdef DEBUG
	for (int i = 0; i < length; ++i) {
	DCHECK_EQ(String::cast(elements->get(i)).length(), 1);
	}
	#endif

	return *isolate->factory()->NewJSArrayWithElements(elements);
	}

	RUNTIME_FUNCTION(Runtime_StringLessThan) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
	ComparisonResult result = String::Compare(isolate, x, y);
	DCHECK_NE(result, ComparisonResult::kUndefined);
	return isolate->heap()->ToBoolean(
	ComparisonResultToBool(Operation::kLessThan, result));
	}

	RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
	ComparisonResult result = String::Compare(isolate, x, y);
	DCHECK_NE(result, ComparisonResult::kUndefined);
	return isolate->heap()->ToBoolean(
	ComparisonResultToBool(Operation::kLessThanOrEqual, result));
	}

	RUNTIME_FUNCTION(Runtime_StringGreaterThan) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
	ComparisonResult result = String::Compare(isolate, x, y);
	DCHECK_NE(result, ComparisonResult::kUndefined);
	return isolate->heap()->ToBoolean(
	ComparisonResultToBool(Operation::kGreaterThan, result));
	}

	RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
	ComparisonResult result = String::Compare(isolate, x, y);
	DCHECK_NE(result, ComparisonResult::kUndefined);
	return isolate->heap()->ToBoolean(
	ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
	}

	RUNTIME_FUNCTION(Runtime_StringEqual) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(2, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
	return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
	}

	RUNTIME_FUNCTION(Runtime_FlattenString) {
	HandleScope scope(isolate);
	DCHECK_EQ(1, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
	return *String::Flatten(isolate, str);
	}

	RUNTIME_FUNCTION(Runtime_StringMaxLength) {
	SealHandleScope shs(isolate);
	return Smi::FromInt(String::kMaxLength);
	}

	RUNTIME_FUNCTION(Runtime_StringCompareSequence) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(3, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
	CONVERT_ARG_HANDLE_CHECKED(String, search_string, 1);
	CONVERT_NUMBER_CHECKED(int, start, Int32, args[2]);

	// Check if start + searchLength is in bounds.
	DCHECK_LE(start + search_string->length(), string->length());

	FlatStringReader string_reader(isolate, String::Flatten(isolate, string));
	FlatStringReader search_reader(isolate,
	String::Flatten(isolate, search_string));

	for (int i = 0; i < search_string->length(); i++) {
	if (string_reader.Get(start + i) != search_reader.Get(i)) {
	return ReadOnlyRoots(isolate).false_value();
	}
	}

	return ReadOnlyRoots(isolate).true_value();
	}

	RUNTIME_FUNCTION(Runtime_StringEscapeQuotes) {
	HandleScope handle_scope(isolate);
	DCHECK_EQ(1, args.length());
	CONVERT_ARG_HANDLE_CHECKED(String, string, 0);

	// Equivalent to global replacement `string.replace(/"/g, "&quot")`, but this
	// does not modify any global state (e.g. the regexp match info).

	const int string_length = string->length();
	Handle<String> quotes =
	isolate->factory()->LookupSingleCharacterStringFromCode('"');

	int index = String::IndexOf(isolate, string, quotes, 0);

	// No quotes, nothing to do.
	if (index == -1) return *string;

	// Find all quotes.
	std::vector<int> indices = {index};
	while (index + 1 < string_length) {
	index = String::IndexOf(isolate, string, quotes, index + 1);
	if (index == -1) break;
	indices.emplace_back(index);
	}

	// Build the replacement string.
	Handle<String> replacement =
	isolate->factory()->NewStringFromAsciiChecked(""");
	const int estimated_part_count = static_cast<int>(indices.size()) * 2 + 1;
	ReplacementStringBuilder builder(isolate->heap(), string,
	estimated_part_count);

	int prev_index = -1; // Start at -1 to avoid special-casing the first match.
	for (int index : indices) {
	const int slice_start = prev_index + 1;
	const int slice_end = index;
	if (slice_end > slice_start) {
	builder.AddSubjectSlice(slice_start, slice_end);
	}
	builder.AddString(replacement);
	prev_index = index;
	}

	if (prev_index < string_length - 1) {
	builder.AddSubjectSlice(prev_index + 1, string_length);
	}

	return *builder.ToString().ToHandleChecked();
	}

	} // namespace internal
	} // namespace v8