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
18 namespace v8 {
19 namespace internal {
20
RUNTIME_FUNCTION(Runtime_GetSubstitution)21 RUNTIME_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.
StringReplaceOneCharWithString(Isolate * isolate,Handle<String> subject,Handle<String> search,Handle<String> replace,bool * found,int recursion_limit)69 MaybeHandle<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
RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString)112 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringLastIndexOf)142 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringSubstring)148 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringAdd)161 RUNTIME_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
RUNTIME_FUNCTION(Runtime_InternalizeString)172 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringCharCodeAt)179 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringBuilderConcat)198 RUNTIME_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.
CopyCachedOneByteCharsToArray(Heap * heap,const uint8_t * chars,FixedArray elements,int length)277 static 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"].
RUNTIME_FUNCTION(Runtime_StringToArray)304 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringLessThan)350 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual)361 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringGreaterThan)372 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual)383 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringEqual)394 RUNTIME_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
RUNTIME_FUNCTION(Runtime_FlattenString)402 RUNTIME_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
RUNTIME_FUNCTION(Runtime_StringMaxLength)409 RUNTIME_FUNCTION(Runtime_StringMaxLength) {
410 SealHandleScope shs(isolate);
411 return Smi::FromInt(String::kMaxLength);
412 }
413
RUNTIME_FUNCTION(Runtime_StringEscapeQuotes)414 RUNTIME_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, """)`, 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(""");
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