1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/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#include "src/strings/string-builder-inl.h"
16#include "src/strings/string-search.h"
17
18namespace v8 {
19namespace internal {
20
21RUNTIME_FUNCTION(Runtime_GetSubstitution) {
22  HandleScope scope(isolate);
23  DCHECK_EQ(5, args.length());
24  Handle<String> matched = args.at<String>(0);
25  Handle<String> subject = args.at<String>(1);
26  int position = args.smi_value_at(2);
27  Handle<String> replacement = args.at<String>(3);
28  int start_index = args.smi_value_at(4);
29
30  // A simple match without captures.
31  class SimpleMatch : public String::Match {
32   public:
33    SimpleMatch(Handle<String> match, Handle<String> prefix,
34                Handle<String> suffix)
35        : match_(match), prefix_(prefix), suffix_(suffix) {}
36
37    Handle<String> GetMatch() override { return match_; }
38    Handle<String> GetPrefix() override { return prefix_; }
39    Handle<String> GetSuffix() override { return suffix_; }
40
41    int CaptureCount() override { return 0; }
42    bool HasNamedCaptures() override { return false; }
43    MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
44      *capture_exists = false;
45      return match_;  // Return arbitrary string handle.
46    }
47    MaybeHandle<String> GetNamedCapture(Handle<String> name,
48                                        CaptureState* state) override {
49      UNREACHABLE();
50    }
51
52   private:
53    Handle<String> match_, prefix_, suffix_;
54  };
55
56  Handle<String> prefix =
57      isolate->factory()->NewSubString(subject, 0, position);
58  Handle<String> suffix = isolate->factory()->NewSubString(
59      subject, position + matched->length(), subject->length());
60  SimpleMatch match(matched, prefix, suffix);
61
62  RETURN_RESULT_OR_FAILURE(
63      isolate,
64      String::GetSubstitution(isolate, &match, replacement, start_index));
65}
66
67// This may return an empty MaybeHandle if an exception is thrown or
68// we abort due to reaching the recursion limit.
69MaybeHandle<String> StringReplaceOneCharWithString(
70    Isolate* isolate, Handle<String> subject, Handle<String> search,
71    Handle<String> replace, bool* found, int recursion_limit) {
72  StackLimitCheck stackLimitCheck(isolate);
73  if (stackLimitCheck.HasOverflowed() || (recursion_limit == 0)) {
74    return MaybeHandle<String>();
75  }
76  recursion_limit--;
77  if (subject->IsConsString()) {
78    ConsString cons = ConsString::cast(*subject);
79    Handle<String> first = handle(cons.first(), isolate);
80    Handle<String> second = handle(cons.second(), isolate);
81    Handle<String> new_first;
82    if (!StringReplaceOneCharWithString(isolate, first, search, replace, found,
83                                        recursion_limit).ToHandle(&new_first)) {
84      return MaybeHandle<String>();
85    }
86    if (*found) return isolate->factory()->NewConsString(new_first, second);
87
88    Handle<String> new_second;
89    if (!StringReplaceOneCharWithString(isolate, second, search, replace, found,
90                                        recursion_limit)
91             .ToHandle(&new_second)) {
92      return MaybeHandle<String>();
93    }
94    if (*found) return isolate->factory()->NewConsString(first, new_second);
95
96    return subject;
97  } else {
98    int index = String::IndexOf(isolate, subject, search, 0);
99    if (index == -1) return subject;
100    *found = true;
101    Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
102    Handle<String> cons1;
103    ASSIGN_RETURN_ON_EXCEPTION(
104        isolate, cons1, isolate->factory()->NewConsString(first, replace),
105        String);
106    Handle<String> second =
107        isolate->factory()->NewSubString(subject, index + 1, subject->length());
108    return isolate->factory()->NewConsString(cons1, second);
109  }
110}
111
112RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {
113  HandleScope scope(isolate);
114  DCHECK_EQ(3, args.length());
115  Handle<String> subject = args.at<String>(0);
116  Handle<String> search = args.at<String>(1);
117  Handle<String> replace = args.at<String>(2);
118
119  // If the cons string tree is too deep, we simply abort the recursion and
120  // retry with a flattened subject string.
121  const int kRecursionLimit = 0x1000;
122  bool found = false;
123  Handle<String> result;
124  if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
125                                     kRecursionLimit).ToHandle(&result)) {
126    return *result;
127  }
128  if (isolate->has_pending_exception())
129    return ReadOnlyRoots(isolate).exception();
130
131  subject = String::Flatten(isolate, subject);
132  if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
133                                     kRecursionLimit).ToHandle(&result)) {
134    return *result;
135  }
136  if (isolate->has_pending_exception())
137    return ReadOnlyRoots(isolate).exception();
138  // In case of empty handle and no pending exception we have stack overflow.
139  return isolate->StackOverflow();
140}
141
142RUNTIME_FUNCTION(Runtime_StringLastIndexOf) {
143  HandleScope handle_scope(isolate);
144  return String::LastIndexOf(isolate, args.at(0), args.at(1),
145                             isolate->factory()->undefined_value());
146}
147
148RUNTIME_FUNCTION(Runtime_StringSubstring) {
149  HandleScope scope(isolate);
150  DCHECK_EQ(3, args.length());
151  Handle<String> string = args.at<String>(0);
152  int start = args.smi_value_at(1);
153  int end = args.smi_value_at(2);
154  DCHECK_LE(0, start);
155  DCHECK_LE(start, end);
156  DCHECK_LE(end, string->length());
157  isolate->counters()->sub_string_runtime()->Increment();
158  return *isolate->factory()->NewSubString(string, start, end);
159}
160
161RUNTIME_FUNCTION(Runtime_StringAdd) {
162  HandleScope scope(isolate);
163  DCHECK_EQ(2, args.length());
164  Handle<String> str1 = args.at<String>(0);
165  Handle<String> str2 = args.at<String>(1);
166  isolate->counters()->string_add_runtime()->Increment();
167  RETURN_RESULT_OR_FAILURE(isolate,
168                           isolate->factory()->NewConsString(str1, str2));
169}
170
171
172RUNTIME_FUNCTION(Runtime_InternalizeString) {
173  HandleScope handles(isolate);
174  DCHECK_EQ(1, args.length());
175  Handle<String> string = args.at<String>(0);
176  return *isolate->factory()->InternalizeString(string);
177}
178
179RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
180  HandleScope handle_scope(isolate);
181  DCHECK_EQ(2, args.length());
182
183  Handle<String> subject = args.at<String>(0);
184  uint32_t i = NumberToUint32(args[1]);
185
186  // Flatten the string.  If someone wants to get a char at an index
187  // in a cons string, it is likely that more indices will be
188  // accessed.
189  subject = String::Flatten(isolate, subject);
190
191  if (i >= static_cast<uint32_t>(subject->length())) {
192    return ReadOnlyRoots(isolate).nan_value();
193  }
194
195  return Smi::FromInt(subject->Get(i));
196}
197
198RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
199  HandleScope scope(isolate);
200  DCHECK_EQ(3, args.length());
201  Handle<JSArray> array = args.at<JSArray>(0);
202  int32_t array_length;
203  if (!args[1].ToInt32(&array_length)) {
204    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
205  }
206  Handle<String> special = args.at<String>(2);
207
208  size_t actual_array_length = 0;
209  CHECK(TryNumberToSize(array->length(), &actual_array_length));
210  CHECK_GE(array_length, 0);
211  CHECK(static_cast<size_t>(array_length) <= actual_array_length);
212
213  // This assumption is used by the slice encoding in one or two smis.
214  DCHECK_GE(Smi::kMaxValue, String::kMaxLength);
215
216  CHECK(array->HasFastElements());
217  JSObject::EnsureCanContainHeapObjectElements(array);
218
219  int special_length = special->length();
220  if (!array->HasObjectElements()) {
221    return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
222  }
223
224  int length;
225  bool one_byte = special->IsOneByteRepresentation();
226
227  {
228    DisallowGarbageCollection no_gc;
229    FixedArray fixed_array = FixedArray::cast(array->elements());
230    if (fixed_array.length() < array_length) {
231      array_length = fixed_array.length();
232    }
233
234    if (array_length == 0) {
235      return ReadOnlyRoots(isolate).empty_string();
236    } else if (array_length == 1) {
237      Object first = fixed_array.get(0);
238      if (first.IsString()) return first;
239    }
240    length = StringBuilderConcatLength(special_length, fixed_array,
241                                       array_length, &one_byte);
242  }
243
244  if (length == -1) {
245    return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
246  }
247  if (length == 0) {
248    return ReadOnlyRoots(isolate).empty_string();
249  }
250
251  if (one_byte) {
252    Handle<SeqOneByteString> answer;
253    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
254        isolate, answer, isolate->factory()->NewRawOneByteString(length));
255    DisallowGarbageCollection no_gc;
256    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
257                              FixedArray::cast(array->elements()),
258                              array_length);
259    return *answer;
260  } else {
261    Handle<SeqTwoByteString> answer;
262    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
263        isolate, answer, isolate->factory()->NewRawTwoByteString(length));
264    DisallowGarbageCollection no_gc;
265    StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
266                              FixedArray::cast(array->elements()),
267                              array_length);
268    return *answer;
269  }
270}
271
272
273// Copies Latin1 characters to the given fixed array looking up
274// one-char strings in the cache. Gives up on the first char that is
275// not in the cache and fills the remainder with smi zeros. Returns
276// the length of the successfully copied prefix.
277static int CopyCachedOneByteCharsToArray(Heap* heap, const uint8_t* chars,
278                                         FixedArray elements, int length) {
279  DisallowGarbageCollection no_gc;
280  FixedArray one_byte_cache = heap->single_character_string_cache();
281  Object undefined = ReadOnlyRoots(heap).undefined_value();
282  int i;
283  WriteBarrierMode mode = elements.GetWriteBarrierMode(no_gc);
284  for (i = 0; i < length; ++i) {
285    Object value = one_byte_cache.get(chars[i]);
286    if (value == undefined) break;
287    elements.set(i, value, mode);
288  }
289  if (i < length) {
290    MemsetTagged(elements.RawFieldOfElementAt(i), Smi::zero(), length - i);
291  }
292#ifdef DEBUG
293  for (int j = 0; j < length; ++j) {
294    Object element = elements.get(j);
295    DCHECK(element == Smi::zero() ||
296           (element.IsString() && String::cast(element).LooksValid()));
297  }
298#endif
299  return i;
300}
301
302// Converts a String to JSArray.
303// For example, "foo" => ["f", "o", "o"].
304RUNTIME_FUNCTION(Runtime_StringToArray) {
305  HandleScope scope(isolate);
306  DCHECK_EQ(2, args.length());
307  Handle<String> s = args.at<String>(0);
308  uint32_t limit = NumberToUint32(args[1]);
309
310  s = String::Flatten(isolate, s);
311  const int length =
312      static_cast<int>(std::min(static_cast<uint32_t>(s->length()), limit));
313
314  Handle<FixedArray> elements;
315  int position = 0;
316  if (s->IsFlat() && s->IsOneByteRepresentation()) {
317    // Try using cached chars where possible.
318    elements = isolate->factory()->NewFixedArray(length);
319
320    DisallowGarbageCollection no_gc;
321    String::FlatContent content = s->GetFlatContent(no_gc);
322    if (content.IsOneByte()) {
323      base::Vector<const uint8_t> chars = content.ToOneByteVector();
324      // Note, this will initialize all elements (not only the prefix)
325      // to prevent GC from seeing partially initialized array.
326      position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.begin(),
327                                               *elements, length);
328    } else {
329      MemsetTagged(elements->data_start(),
330                   ReadOnlyRoots(isolate).undefined_value(), length);
331    }
332  } else {
333    elements = isolate->factory()->NewFixedArray(length);
334  }
335  for (int i = position; i < length; ++i) {
336    Handle<Object> str =
337        isolate->factory()->LookupSingleCharacterStringFromCode(s->Get(i));
338    elements->set(i, *str);
339  }
340
341#ifdef DEBUG
342  for (int i = 0; i < length; ++i) {
343    DCHECK_EQ(String::cast(elements->get(i)).length(), 1);
344  }
345#endif
346
347  return *isolate->factory()->NewJSArrayWithElements(elements);
348}
349
350RUNTIME_FUNCTION(Runtime_StringLessThan) {
351  HandleScope handle_scope(isolate);
352  DCHECK_EQ(2, args.length());
353  Handle<String> x = args.at<String>(0);
354  Handle<String> y = args.at<String>(1);
355  ComparisonResult result = String::Compare(isolate, x, y);
356  DCHECK_NE(result, ComparisonResult::kUndefined);
357  return isolate->heap()->ToBoolean(
358      ComparisonResultToBool(Operation::kLessThan, result));
359}
360
361RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual) {
362  HandleScope handle_scope(isolate);
363  DCHECK_EQ(2, args.length());
364  Handle<String> x = args.at<String>(0);
365  Handle<String> y = args.at<String>(1);
366  ComparisonResult result = String::Compare(isolate, x, y);
367  DCHECK_NE(result, ComparisonResult::kUndefined);
368  return isolate->heap()->ToBoolean(
369      ComparisonResultToBool(Operation::kLessThanOrEqual, result));
370}
371
372RUNTIME_FUNCTION(Runtime_StringGreaterThan) {
373  HandleScope handle_scope(isolate);
374  DCHECK_EQ(2, args.length());
375  Handle<String> x = args.at<String>(0);
376  Handle<String> y = args.at<String>(1);
377  ComparisonResult result = String::Compare(isolate, x, y);
378  DCHECK_NE(result, ComparisonResult::kUndefined);
379  return isolate->heap()->ToBoolean(
380      ComparisonResultToBool(Operation::kGreaterThan, result));
381}
382
383RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual) {
384  HandleScope handle_scope(isolate);
385  DCHECK_EQ(2, args.length());
386  Handle<String> x = args.at<String>(0);
387  Handle<String> y = args.at<String>(1);
388  ComparisonResult result = String::Compare(isolate, x, y);
389  DCHECK_NE(result, ComparisonResult::kUndefined);
390  return isolate->heap()->ToBoolean(
391      ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
392}
393
394RUNTIME_FUNCTION(Runtime_StringEqual) {
395  HandleScope handle_scope(isolate);
396  DCHECK_EQ(2, args.length());
397  Handle<String> x = args.at<String>(0);
398  Handle<String> y = args.at<String>(1);
399  return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
400}
401
402RUNTIME_FUNCTION(Runtime_FlattenString) {
403  HandleScope scope(isolate);
404  DCHECK_EQ(1, args.length());
405  Handle<String> str = args.at<String>(0);
406  return *String::Flatten(isolate, str);
407}
408
409RUNTIME_FUNCTION(Runtime_StringMaxLength) {
410  SealHandleScope shs(isolate);
411  return Smi::FromInt(String::kMaxLength);
412}
413
414RUNTIME_FUNCTION(Runtime_StringEscapeQuotes) {
415  HandleScope handle_scope(isolate);
416  DCHECK_EQ(1, args.length());
417  Handle<String> string = args.at<String>(0);
418
419  // Equivalent to global replacement `string.replace(/"/g, "&quot")`, but this
420  // does not modify any global state (e.g. the regexp match info).
421
422  const int string_length = string->length();
423  Handle<String> quotes =
424      isolate->factory()->LookupSingleCharacterStringFromCode('"');
425
426  int quote_index = String::IndexOf(isolate, string, quotes, 0);
427
428  // No quotes, nothing to do.
429  if (quote_index == -1) return *string;
430
431  // Find all quotes.
432  std::vector<int> indices = {quote_index};
433  while (quote_index + 1 < string_length) {
434    quote_index = String::IndexOf(isolate, string, quotes, quote_index + 1);
435    if (quote_index == -1) break;
436    indices.emplace_back(quote_index);
437  }
438
439  // Build the replacement string.
440  Handle<String> replacement =
441      isolate->factory()->NewStringFromAsciiChecked("&quot;");
442  const int estimated_part_count = static_cast<int>(indices.size()) * 2 + 1;
443  ReplacementStringBuilder builder(isolate->heap(), string,
444                                   estimated_part_count);
445
446  int prev_index = -1;  // Start at -1 to avoid special-casing the first match.
447  for (int index : indices) {
448    const int slice_start = prev_index + 1;
449    const int slice_end = index;
450    if (slice_end > slice_start) {
451      builder.AddSubjectSlice(slice_start, slice_end);
452    }
453    builder.AddString(replacement);
454    prev_index = index;
455  }
456
457  if (prev_index < string_length - 1) {
458    builder.AddSubjectSlice(prev_index + 1, string_length);
459  }
460
461  return *builder.ToString().ToHandleChecked();
462}
463
464}  // namespace internal
465}  // namespace v8
466