runtime-strings.cc 28.1 KB
Newer Older
1 2 3 4
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/arguments-inl.h"
6 7
#include "src/conversions.h"
#include "src/counters.h"
8
#include "src/heap/heap-inl.h"
9
#include "src/objects-inl.h"
10
#include "src/objects/js-array-inl.h"
11
#include "src/objects/slots.h"
12
#include "src/objects/smi.h"
13
#include "src/regexp/jsregexp-inl.h"
14
#include "src/regexp/regexp-utils.h"
15
#include "src/runtime/runtime-utils.h"
16
#include "src/string-builder-inl.h"
17 18 19 20 21
#include "src/string-search.h"

namespace v8 {
namespace internal {

22 23
RUNTIME_FUNCTION(Runtime_GetSubstitution) {
  HandleScope scope(isolate);
24
  DCHECK_EQ(5, args.length());
25 26 27 28
  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);
29
  CONVERT_SMI_ARG_CHECKED(start_index, 4);
30 31 32 33 34 35 36 37 38

  // 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_; }
39 40 41 42 43
    Handle<String> GetPrefix() override { return prefix_; }
    Handle<String> GetSuffix() override { return suffix_; }

    int CaptureCount() override { return 0; }
    bool HasNamedCaptures() override { return false; }
44 45 46 47
    MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
      *capture_exists = false;
      return match_;  // Return arbitrary string handle.
    }
48
    MaybeHandle<String> GetNamedCapture(Handle<String> name,
49
                                        CaptureState* state) override {
50 51
      UNREACHABLE();
    }
52 53 54 55 56 57 58 59 60 61 62 63

   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(
64 65
      isolate,
      String::GetSubstitution(isolate, &match, replacement, start_index));
66 67
}

68 69 70 71 72 73 74 75 76 77 78
// 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()) {
79
    ConsString cons = ConsString::cast(*subject);
80 81
    Handle<String> first = handle(cons->first(), isolate);
    Handle<String> second = handle(cons->second(), isolate);
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
    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 {
99
    int index = String::IndexOf(isolate, subject, search, 0);
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
    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);
115
  DCHECK_EQ(3, args.length());
116 117 118 119 120 121 122 123 124 125 126 127 128
  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;
  }
129 130
  if (isolate->has_pending_exception())
    return ReadOnlyRoots(isolate).exception();
131

132
  subject = String::Flatten(isolate, subject);
133 134 135 136
  if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
                                     kRecursionLimit).ToHandle(&result)) {
    return *result;
  }
137 138
  if (isolate->has_pending_exception())
    return ReadOnlyRoots(isolate).exception();
139 140
  // In case of empty handle and no pending exception we have stack overflow.
  return isolate->StackOverflow();
141 142
}

143 144 145 146 147 148
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);
149
  return *String::Trim(isolate, string, trim_mode);
150 151
}

152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
// 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());
174
    return ReadOnlyRoots(isolate).exception();
175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
  }
  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);
}

195 196
// ES6 #sec-string.prototype.indexof
// String.prototype.indexOf(searchString [, position])
197 198
RUNTIME_FUNCTION(Runtime_StringIndexOf) {
  HandleScope scope(isolate);
199
  DCHECK_EQ(3, args.length());
200 201 202 203 204 205 206 207 208
  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);
209
  DCHECK_EQ(3, args.length());
210 211 212 213 214 215
  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)));
216 217 218
}

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

224
RUNTIME_FUNCTION(Runtime_StringSubstring) {
225
  HandleScope scope(isolate);
226
  DCHECK_EQ(3, args.length());
227
  CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
228 229 230 231 232
  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());
233 234 235 236
  isolate->counters()->sub_string_runtime()->Increment();
  return *isolate->factory()->NewSubString(string, start, end);
}

237
RUNTIME_FUNCTION(Runtime_StringAdd) {
238
  HandleScope scope(isolate);
239
  DCHECK_EQ(2, args.length());
240 241
  CONVERT_ARG_HANDLE_CHECKED(String, str1, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, str2, 1);
242
  isolate->counters()->string_add_runtime()->Increment();
243 244
  RETURN_RESULT_OR_FAILURE(isolate,
                           isolate->factory()->NewConsString(str1, str2));
245 246 247 248 249
}


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

255
RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
256
  HandleScope handle_scope(isolate);
257
  DCHECK_EQ(2, args.length());
258 259 260 261 262 263 264

  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.
265
  subject = String::Flatten(isolate, subject);
266 267

  if (i >= static_cast<uint32_t>(subject->length())) {
268
    return ReadOnlyRoots(isolate).nan_value();
269 270 271 272 273 274 275
  }

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

RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
  HandleScope scope(isolate);
276
  DCHECK_EQ(3, args.length());
277 278 279 280 281 282 283 284
  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;
285
  CHECK(TryNumberToSize(array->length(), &actual_array_length));
286
  CHECK_GE(array_length, 0);
287
  CHECK(static_cast<size_t>(array_length) <= actual_array_length);
288 289

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

292
  CHECK(array->HasFastElements());
293 294 295
  JSObject::EnsureCanContainHeapObjectElements(array);

  int special_length = special->length();
296
  if (!array->HasObjectElements()) {
297
    return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
298 299 300 301 302 303 304
  }

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

  {
    DisallowHeapAllocation no_gc;
305
    FixedArray fixed_array = FixedArray::cast(array->elements());
306 307 308 309 310
    if (fixed_array->length() < array_length) {
      array_length = fixed_array->length();
    }

    if (array_length == 0) {
311
      return ReadOnlyRoots(isolate).empty_string();
312
    } else if (array_length == 1) {
313
      Object first = fixed_array->get(0);
314 315 316 317 318 319 320
      if (first->IsString()) return first;
    }
    length = StringBuilderConcatLength(special_length, fixed_array,
                                       array_length, &one_byte);
  }

  if (length == -1) {
321
    return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
322
  }
323
  if (length == 0) {
324
    return ReadOnlyRoots(isolate).empty_string();
325
  }
326 327 328 329 330

  if (one_byte) {
    Handle<SeqOneByteString> answer;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, answer, isolate->factory()->NewRawOneByteString(length));
331
    DisallowHeapAllocation no_gc;
332
    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
333 334 335 336 337 338 339
                              FixedArray::cast(array->elements()),
                              array_length);
    return *answer;
  } else {
    Handle<SeqTwoByteString> answer;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, answer, isolate->factory()->NewRawTwoByteString(length));
340
    DisallowHeapAllocation no_gc;
341
    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
342 343 344 345 346 347
                              FixedArray::cast(array->elements()),
                              array_length);
    return *answer;
  }
}

348
// TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
349 350
RUNTIME_FUNCTION(Runtime_StringBuilderJoin) {
  HandleScope scope(isolate);
351
  DCHECK_EQ(3, args.length());
352 353 354 355 356 357
  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, separator, 2);
358
  CHECK(array->HasObjectElements());
359
  CHECK_GE(array_length, 0);
360

361
  Handle<FixedArray> fixed_array(FixedArray::cast(array->elements()), isolate);
362 363 364 365 366
  if (fixed_array->length() < array_length) {
    array_length = fixed_array->length();
  }

  if (array_length == 0) {
367
    return ReadOnlyRoots(isolate).empty_string();
368
  } else if (array_length == 1) {
369
    Object first = fixed_array->get(0);
370
    CHECK(first->IsString());
371 372 373 374
    return first;
  }

  int separator_length = separator->length();
375
  CHECK_GT(separator_length, 0);
376 377 378 379 380 381 382
  int max_nof_separators =
      (String::kMaxLength + separator_length - 1) / separator_length;
  if (max_nof_separators < (array_length - 1)) {
    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
  }
  int length = (array_length - 1) * separator_length;
  for (int i = 0; i < array_length; i++) {
383
    Object element_obj = fixed_array->get(i);
384
    CHECK(element_obj->IsString());
385
    String element = String::cast(element_obj);
386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
    int increment = element->length();
    if (increment > String::kMaxLength - length) {
      STATIC_ASSERT(String::kMaxLength < kMaxInt);
      length = kMaxInt;  // Provoke exception;
      break;
    }
    length += increment;
  }

  Handle<SeqTwoByteString> answer;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, answer, isolate->factory()->NewRawTwoByteString(length));

  DisallowHeapAllocation no_gc;

401
  uc16* sink = answer->GetChars(no_gc);
402 403 404 405
#ifdef DEBUG
  uc16* end = sink + length;
#endif

406
  CHECK(fixed_array->get(0)->IsString());
407 408
  String first = String::cast(fixed_array->get(0));
  String separator_raw = *separator;
409

410 411 412 413 414 415 416 417 418
  int first_length = first->length();
  String::WriteToFlat(first, sink, 0, first_length);
  sink += first_length;

  for (int i = 1; i < array_length; i++) {
    DCHECK(sink + separator_length <= end);
    String::WriteToFlat(separator_raw, sink, 0, separator_length);
    sink += separator_length;

419
    CHECK(fixed_array->get(i)->IsString());
420
    String element = String::cast(fixed_array->get(i));
421 422 423 424 425 426 427 428 429 430 431 432
    int element_length = element->length();
    DCHECK(sink + element_length <= end);
    String::WriteToFlat(element, sink, 0, element_length);
    sink += element_length;
  }
  DCHECK(sink == end);

  // Use %_FastOneByteArrayJoin instead.
  DCHECK(!answer->IsOneByteRepresentation());
  return *answer;
}

433
template <typename sinkchar>
434
static void WriteRepeatToFlat(String src, Vector<sinkchar> buffer, int cursor,
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
                              int repeat, int length) {
  if (repeat == 0) return;

  sinkchar* start = &buffer[cursor];
  String::WriteToFlat<sinkchar>(src, start, 0, length);

  int done = 1;
  sinkchar* next = start + length;

  while (done < repeat) {
    int block = Min(done, repeat - done);
    int block_chars = block * length;
    CopyChars(next, start, block_chars);
    next += block_chars;
    done += block;
  }
}

453
// TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
454
template <typename Char>
455
static void JoinSparseArrayWithSeparator(FixedArray elements,
456 457
                                         int elements_length,
                                         uint32_t array_length,
458
                                         String separator,
459 460 461 462
                                         Vector<Char> buffer) {
  DisallowHeapAllocation no_gc;
  int previous_separator_position = 0;
  int separator_length = separator->length();
463
  DCHECK_LT(0, separator_length);
464 465 466
  int cursor = 0;
  for (int i = 0; i < elements_length; i += 2) {
    int position = NumberToInt32(elements->get(i));
467
    String string = String::cast(elements->get(i + 1));
468 469
    int string_length = string->length();
    if (string->length() > 0) {
470 471 472 473 474
      int repeat = position - previous_separator_position;
      WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat,
                              separator_length);
      cursor += repeat * separator_length;
      previous_separator_position = position;
475 476 477 478
      String::WriteToFlat<Char>(string, &buffer[cursor], 0, string_length);
      cursor += string->length();
    }
  }
479 480 481 482

  int last_array_index = static_cast<int>(array_length - 1);
  // Array length must be representable as a signed 32-bit number,
  // otherwise the total string length would have been too large.
483
  DCHECK_LE(array_length, 0x7FFFFFFF);  // Is int32_t.
484 485 486
  int repeat = last_array_index - previous_separator_position;
  WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat, separator_length);
  cursor += repeat * separator_length;
487 488 489
  DCHECK(cursor <= buffer.length());
}

490
// TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
491 492
RUNTIME_FUNCTION(Runtime_SparseJoinWithSeparator) {
  HandleScope scope(isolate);
493
  DCHECK_EQ(3, args.length());
494 495 496 497 498
  CONVERT_ARG_HANDLE_CHECKED(JSArray, elements_array, 0);
  CONVERT_NUMBER_CHECKED(uint32_t, array_length, Uint32, args[1]);
  CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
  // elements_array is fast-mode JSarray of alternating positions
  // (increasing order) and strings.
499
  CHECK(elements_array->HasSmiOrObjectElements());
500 501
  // array_length is length of original array (used to add separators);
  // separator is string to put between elements. Assumed to be non-empty.
502
  CHECK_GT(array_length, 0);
503 504 505 506 507 508

  // Find total length of join result.
  int string_length = 0;
  bool is_one_byte = separator->IsOneByteRepresentation();
  bool overflow = false;
  CONVERT_NUMBER_CHECKED(int, elements_length, Int32, elements_array->length());
509
  CHECK(elements_length <= elements_array->elements()->length());
510
  CHECK_EQ(elements_length & 1, 0);  // Even length.
511
  FixedArray elements = FixedArray::cast(elements_array->elements());
512 513 514
  {
    DisallowHeapAllocation no_gc;
    for (int i = 0; i < elements_length; i += 2) {
515
      String string = String::cast(elements->get(i + 1));
516 517 518 519 520 521 522 523 524 525 526 527 528 529 530
      int length = string->length();
      if (is_one_byte && !string->IsOneByteRepresentation()) {
        is_one_byte = false;
      }
      if (length > String::kMaxLength ||
          String::kMaxLength - length < string_length) {
        overflow = true;
        break;
      }
      string_length += length;
    }
  }

  int separator_length = separator->length();
  if (!overflow && separator_length > 0) {
531
    if (array_length <= 0x7FFFFFFFu) {
532 533 534 535 536 537 538 539 540 541 542
      int separator_count = static_cast<int>(array_length) - 1;
      int remaining_length = String::kMaxLength - string_length;
      if ((remaining_length / separator_length) >= separator_count) {
        string_length += separator_length * (array_length - 1);
      } else {
        // Not room for the separators within the maximal string length.
        overflow = true;
      }
    } else {
      // Nonempty separator and at least 2^31-1 separators necessary
      // means that the string is too large to create.
543
      STATIC_ASSERT(String::kMaxLength < 0x7FFFFFFF);
544 545 546 547 548 549 550 551 552 553 554 555 556 557
      overflow = true;
    }
  }
  if (overflow) {
    // Throw an exception if the resulting string is too large. See
    // https://code.google.com/p/chromium/issues/detail?id=336820
    // for details.
    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
  }

  if (is_one_byte) {
    Handle<SeqOneByteString> result = isolate->factory()
                                          ->NewRawOneByteString(string_length)
                                          .ToHandleChecked();
558
    DisallowHeapAllocation no_gc;
559 560 561
    JoinSparseArrayWithSeparator<uint8_t>(
        FixedArray::cast(elements_array->elements()), elements_length,
        array_length, *separator,
562
        Vector<uint8_t>(result->GetChars(no_gc), string_length));
563 564 565 566 567
    return *result;
  } else {
    Handle<SeqTwoByteString> result = isolate->factory()
                                          ->NewRawTwoByteString(string_length)
                                          .ToHandleChecked();
568
    DisallowHeapAllocation no_gc;
569 570 571
    JoinSparseArrayWithSeparator<uc16>(
        FixedArray::cast(elements_array->elements()), elements_length,
        array_length, *separator,
572
        Vector<uc16>(result->GetChars(no_gc), string_length));
573 574 575 576 577 578 579 580 581
    return *result;
  }
}

// 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,
582
                                         FixedArray elements, int length) {
583
  DisallowHeapAllocation no_gc;
584
  FixedArray one_byte_cache = heap->single_character_string_cache();
585
  Object undefined = ReadOnlyRoots(heap).undefined_value();
586 587 588
  int i;
  WriteBarrierMode mode = elements->GetWriteBarrierMode(no_gc);
  for (i = 0; i < length; ++i) {
589
    Object value = one_byte_cache->get(chars[i]);
590 591 592 593
    if (value == undefined) break;
    elements->set(i, value, mode);
  }
  if (i < length) {
594
    MemsetTagged(elements->RawFieldOfElementAt(i), Smi::kZero, length - i);
595 596 597
  }
#ifdef DEBUG
  for (int j = 0; j < length; ++j) {
598
    Object element = elements->get(j);
599
    DCHECK(element == Smi::kZero ||
600 601 602 603 604 605 606 607 608 609
           (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);
610
  DCHECK_EQ(2, args.length());
611 612 613
  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
  CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);

614
  s = String::Flatten(isolate, s);
615 616 617 618 619 620 621 622 623
  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;
624
    String::FlatContent content = s->GetFlatContent(no_gc);
625 626 627 628 629 630 631
    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.start(),
                                               *elements, length);
    } else {
632 633
      MemsetTagged(elements->data_start(),
                   ReadOnlyRoots(isolate).undefined_value(), length);
634 635 636 637 638 639 640 641 642 643 644 645
    }
  } 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) {
646
    DCHECK_EQ(String::cast(elements->get(i))->length(), 1);
647 648 649 650 651 652
  }
#endif

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

653 654 655 656 657
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);
658
  ComparisonResult result = String::Compare(isolate, x, y);
659 660 661
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kLessThan, result));
662 663 664 665 666 667 668
}

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);
669
  ComparisonResult result = String::Compare(isolate, x, y);
670 671 672
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kLessThanOrEqual, result));
673 674 675 676 677 678 679
}

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);
680
  ComparisonResult result = String::Compare(isolate, x, y);
681 682 683
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kGreaterThan, result));
684 685 686 687 688 689 690
}

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);
691
  ComparisonResult result = String::Compare(isolate, x, y);
692 693 694
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
695 696
}

697
RUNTIME_FUNCTION(Runtime_StringEqual) {
698
  HandleScope handle_scope(isolate);
699
  DCHECK_EQ(2, args.length());
700 701
  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
702
  return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
703 704
}

705 706
RUNTIME_FUNCTION(Runtime_FlattenString) {
  HandleScope scope(isolate);
707
  DCHECK_EQ(1, args.length());
708
  CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
709
  return *String::Flatten(isolate, str);
710 711
}

712 713 714 715 716
RUNTIME_FUNCTION(Runtime_StringMaxLength) {
  SealHandleScope shs(isolate);
  return Smi::FromInt(String::kMaxLength);
}

717
RUNTIME_FUNCTION(Runtime_StringCompareSequence) {
718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738
  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();
}
739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789

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();
}

790 791
}  // namespace internal
}  // namespace v8