runtime-strings.cc 18.7 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/execution/arguments-inl.h"
6
#include "src/heap/heap-inl.h"
7
#include "src/logging/counters.h"
8
#include "src/numbers/conversions.h"
9
#include "src/objects/js-array-inl.h"
10
#include "src/objects/objects-inl.h"
11
#include "src/objects/slots.h"
12
#include "src/objects/smi.h"
13
#include "src/regexp/regexp-utils.h"
14
#include "src/runtime/runtime-utils.h"
15 16
#include "src/strings/string-builder-inl.h"
#include "src/strings/string-search.h"
17 18 19 20

namespace v8 {
namespace internal {

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

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

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

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

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

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

142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
// 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());
164
    return ReadOnlyRoots(isolate).exception();
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
  }
  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);
}

185 186
// ES6 #sec-string.prototype.indexof
// String.prototype.indexOf(searchString [, position])
187 188
RUNTIME_FUNCTION(Runtime_StringIndexOf) {
  HandleScope scope(isolate);
189
  DCHECK_EQ(3, args.length());
190 191 192 193 194 195 196 197 198
  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);
199
  DCHECK_EQ(3, args.length());
200 201 202 203 204 205
  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)));
206 207 208
}

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

214
RUNTIME_FUNCTION(Runtime_StringSubstring) {
215
  HandleScope scope(isolate);
216
  DCHECK_EQ(3, args.length());
217
  CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
218 219 220 221 222
  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());
223 224 225 226
  isolate->counters()->sub_string_runtime()->Increment();
  return *isolate->factory()->NewSubString(string, start, end);
}

227
RUNTIME_FUNCTION(Runtime_StringAdd) {
228
  HandleScope scope(isolate);
229
  DCHECK_EQ(2, args.length());
230 231
  CONVERT_ARG_HANDLE_CHECKED(String, str1, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, str2, 1);
232
  isolate->counters()->string_add_runtime()->Increment();
233 234
  RETURN_RESULT_OR_FAILURE(isolate,
                           isolate->factory()->NewConsString(str1, str2));
235 236 237 238 239
}


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

245
RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
246
  HandleScope handle_scope(isolate);
247
  DCHECK_EQ(2, args.length());
248 249 250 251 252 253 254

  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.
255
  subject = String::Flatten(isolate, subject);
256 257

  if (i >= static_cast<uint32_t>(subject->length())) {
258
    return ReadOnlyRoots(isolate).nan_value();
259 260 261 262 263 264 265
  }

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

RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
  HandleScope scope(isolate);
266
  DCHECK_EQ(3, args.length());
267 268
  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
  int32_t array_length;
269
  if (!args[1].ToInt32(&array_length)) {
270 271 272 273 274
    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
  }
  CONVERT_ARG_HANDLE_CHECKED(String, special, 2);

  size_t actual_array_length = 0;
275
  CHECK(TryNumberToSize(array->length(), &actual_array_length));
276
  CHECK_GE(array_length, 0);
277
  CHECK(static_cast<size_t>(array_length) <= actual_array_length);
278 279

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

282
  CHECK(array->HasFastElements());
283 284 285
  JSObject::EnsureCanContainHeapObjectElements(array);

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

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

  {
294
    DisallowGarbageCollection no_gc;
295
    FixedArray fixed_array = FixedArray::cast(array->elements());
296 297
    if (fixed_array.length() < array_length) {
      array_length = fixed_array.length();
298 299 300
    }

    if (array_length == 0) {
301
      return ReadOnlyRoots(isolate).empty_string();
302
    } else if (array_length == 1) {
303 304
      Object first = fixed_array.get(0);
      if (first.IsString()) return first;
305 306 307 308 309 310
    }
    length = StringBuilderConcatLength(special_length, fixed_array,
                                       array_length, &one_byte);
  }

  if (length == -1) {
311
    return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
312
  }
313
  if (length == 0) {
314
    return ReadOnlyRoots(isolate).empty_string();
315
  }
316 317 318 319 320

  if (one_byte) {
    Handle<SeqOneByteString> answer;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, answer, isolate->factory()->NewRawOneByteString(length));
321
    DisallowGarbageCollection no_gc;
322
    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
323 324 325 326 327 328 329
                              FixedArray::cast(array->elements()),
                              array_length);
    return *answer;
  } else {
    Handle<SeqTwoByteString> answer;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, answer, isolate->factory()->NewRawTwoByteString(length));
330
    DisallowGarbageCollection no_gc;
331
    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
332 333 334 335 336 337 338 339 340 341 342 343
                              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,
344
                                         FixedArray elements, int length) {
345
  DisallowGarbageCollection no_gc;
346
  FixedArray one_byte_cache = heap->single_character_string_cache();
347
  Object undefined = ReadOnlyRoots(heap).undefined_value();
348
  int i;
349
  WriteBarrierMode mode = elements.GetWriteBarrierMode(no_gc);
350
  for (i = 0; i < length; ++i) {
351
    Object value = one_byte_cache.get(chars[i]);
352
    if (value == undefined) break;
353
    elements.set(i, value, mode);
354 355
  }
  if (i < length) {
356
    MemsetTagged(elements.RawFieldOfElementAt(i), Smi::zero(), length - i);
357 358 359
  }
#ifdef DEBUG
  for (int j = 0; j < length; ++j) {
360
    Object element = elements.get(j);
361
    DCHECK(element == Smi::zero() ||
362
           (element.IsString() && String::cast(element).LooksValid()));
363 364 365 366 367 368 369 370 371
  }
#endif
  return i;
}

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

376
  s = String::Flatten(isolate, s);
377 378
  const int length =
      static_cast<int>(std::min(static_cast<uint32_t>(s->length()), limit));
379 380 381 382 383 384 385

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

386
    DisallowGarbageCollection no_gc;
387
    String::FlatContent content = s->GetFlatContent(no_gc);
388 389 390 391
    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.
392
      position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.begin(),
393 394
                                               *elements, length);
    } else {
395 396
      MemsetTagged(elements->data_start(),
                   ReadOnlyRoots(isolate).undefined_value(), length);
397 398 399 400 401 402 403 404 405 406 407 408
    }
  } 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) {
409
    DCHECK_EQ(String::cast(elements->get(i)).length(), 1);
410 411 412 413 414 415
  }
#endif

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

416 417 418 419 420
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);
421
  ComparisonResult result = String::Compare(isolate, x, y);
422 423 424
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kLessThan, result));
425 426 427 428 429 430 431
}

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);
432
  ComparisonResult result = String::Compare(isolate, x, y);
433 434 435
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kLessThanOrEqual, result));
436 437 438 439 440 441 442
}

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);
443
  ComparisonResult result = String::Compare(isolate, x, y);
444 445 446
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kGreaterThan, result));
447 448 449 450 451 452 453
}

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);
454
  ComparisonResult result = String::Compare(isolate, x, y);
455 456 457
  DCHECK_NE(result, ComparisonResult::kUndefined);
  return isolate->heap()->ToBoolean(
      ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
458 459
}

460
RUNTIME_FUNCTION(Runtime_StringEqual) {
461
  HandleScope handle_scope(isolate);
462
  DCHECK_EQ(2, args.length());
463 464
  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
465
  return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
466 467
}

468 469
RUNTIME_FUNCTION(Runtime_FlattenString) {
  HandleScope scope(isolate);
470
  DCHECK_EQ(1, args.length());
471
  CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
472
  return *String::Flatten(isolate, str);
473 474
}

475 476 477 478 479
RUNTIME_FUNCTION(Runtime_StringMaxLength) {
  SealHandleScope shs(isolate);
  return Smi::FromInt(String::kMaxLength);
}

480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
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();
}

530 531
}  // namespace internal
}  // namespace v8