Line data Source code
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/arguments-inl.h"
6 : #include "src/conversions.h"
7 : #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 : #include "src/string-search.h"
18 :
19 : namespace v8 {
20 : namespace internal {
21 :
22 153 : RUNTIME_FUNCTION(Runtime_GetSubstitution) {
23 153 : HandleScope scope(isolate);
24 : DCHECK_EQ(5, args.length());
25 306 : CONVERT_ARG_HANDLE_CHECKED(String, matched, 0);
26 306 : CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
27 306 : CONVERT_SMI_ARG_CHECKED(position, 2);
28 306 : CONVERT_ARG_HANDLE_CHECKED(String, replacement, 3);
29 306 : CONVERT_SMI_ARG_CHECKED(start_index, 4);
30 :
31 : // A simple match without captures.
32 306 : class SimpleMatch : public String::Match {
33 : public:
34 153 : SimpleMatch(Handle<String> match, Handle<String> prefix,
35 : Handle<String> suffix)
36 153 : : match_(match), prefix_(prefix), suffix_(suffix) {}
37 :
38 36 : Handle<String> GetMatch() override { return match_; }
39 18 : Handle<String> GetPrefix() override { return prefix_; }
40 18 : Handle<String> GetSuffix() override { return suffix_; }
41 :
42 153 : int CaptureCount() override { return 0; }
43 0 : bool HasNamedCaptures() override { return false; }
44 0 : MaybeHandle<String> GetCapture(int i, bool* capture_exists) override {
45 0 : *capture_exists = false;
46 0 : return match_; // Return arbitrary string handle.
47 : }
48 0 : MaybeHandle<String> GetNamedCapture(Handle<String> name,
49 : CaptureState* state) override {
50 0 : UNREACHABLE();
51 : }
52 :
53 : private:
54 : Handle<String> match_, prefix_, suffix_;
55 : };
56 :
57 : Handle<String> prefix =
58 153 : isolate->factory()->NewSubString(subject, 0, position);
59 : Handle<String> suffix = isolate->factory()->NewSubString(
60 306 : subject, position + matched->length(), subject->length());
61 306 : SimpleMatch match(matched, prefix, suffix);
62 :
63 306 : RETURN_RESULT_OR_FAILURE(
64 : isolate,
65 153 : String::GetSubstitution(isolate, &match, replacement, start_index));
66 : }
67 :
68 : // This may return an empty MaybeHandle if an exception is thrown or
69 : // we abort due to reaching the recursion limit.
70 82932 : MaybeHandle<String> StringReplaceOneCharWithString(
71 : Isolate* isolate, Handle<String> subject, Handle<String> search,
72 : Handle<String> replace, bool* found, int recursion_limit) {
73 : StackLimitCheck stackLimitCheck(isolate);
74 82932 : if (stackLimitCheck.HasOverflowed() || (recursion_limit == 0)) {
75 420 : return MaybeHandle<String>();
76 : }
77 82512 : recursion_limit--;
78 165024 : if (subject->IsConsString()) {
79 78075 : ConsString cons = ConsString::cast(*subject);
80 156150 : Handle<String> first = handle(cons->first(), isolate);
81 156150 : Handle<String> second = handle(cons->second(), isolate);
82 : Handle<String> new_first;
83 78075 : if (!StringReplaceOneCharWithString(isolate, first, search, replace, found,
84 156150 : recursion_limit).ToHandle(&new_first)) {
85 73764 : return MaybeHandle<String>();
86 : }
87 4311 : if (*found) return isolate->factory()->NewConsString(new_first, second);
88 :
89 : Handle<String> new_second;
90 4311 : if (!StringReplaceOneCharWithString(isolate, second, search, replace, found,
91 : recursion_limit)
92 8622 : .ToHandle(&new_second)) {
93 18 : return MaybeHandle<String>();
94 : }
95 4293 : if (*found) return isolate->factory()->NewConsString(first, new_second);
96 :
97 4275 : return subject;
98 : } else {
99 4437 : int index = String::IndexOf(isolate, subject, search, 0);
100 4437 : if (index == -1) return subject;
101 36 : *found = true;
102 36 : Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
103 : Handle<String> cons1;
104 72 : ASSIGN_RETURN_ON_EXCEPTION(
105 : isolate, cons1, isolate->factory()->NewConsString(first, replace),
106 : String);
107 : Handle<String> second =
108 36 : isolate->factory()->NewSubString(subject, index + 1, subject->length());
109 36 : return isolate->factory()->NewConsString(cons1, second);
110 : }
111 : }
112 :
113 300 : RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {
114 300 : HandleScope scope(isolate);
115 : DCHECK_EQ(3, args.length());
116 600 : CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
117 600 : CONVERT_ARG_HANDLE_CHECKED(String, search, 1);
118 600 : CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);
119 :
120 : // If the cons string tree is too deep, we simply abort the recursion and
121 : // retry with a flattened subject string.
122 : const int kRecursionLimit = 0x1000;
123 300 : bool found = false;
124 : Handle<String> result;
125 300 : if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
126 600 : kRecursionLimit).ToHandle(&result)) {
127 : return *result;
128 : }
129 246 : if (isolate->has_pending_exception())
130 : return ReadOnlyRoots(isolate).exception();
131 :
132 246 : subject = String::Flatten(isolate, subject);
133 246 : if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
134 492 : kRecursionLimit).ToHandle(&result)) {
135 : return *result;
136 : }
137 174 : if (isolate->has_pending_exception())
138 : return ReadOnlyRoots(isolate).exception();
139 : // In case of empty handle and no pending exception we have stack overflow.
140 174 : return isolate->StackOverflow();
141 : }
142 :
143 36 : RUNTIME_FUNCTION(Runtime_StringTrim) {
144 36 : HandleScope scope(isolate);
145 : DCHECK_EQ(2, args.length());
146 36 : Handle<String> string = args.at<String>(0);
147 72 : CONVERT_SMI_ARG_CHECKED(mode, 1);
148 36 : String::TrimMode trim_mode = static_cast<String::TrimMode>(mode);
149 72 : return *String::Trim(isolate, string, trim_mode);
150 : }
151 :
152 : // ES6 #sec-string.prototype.includes
153 : // String.prototype.includes(searchString [, position])
154 486 : RUNTIME_FUNCTION(Runtime_StringIncludes) {
155 486 : HandleScope scope(isolate);
156 : DCHECK_EQ(3, args.length());
157 :
158 486 : Handle<Object> receiver = args.at(0);
159 972 : if (receiver->IsNullOrUndefined(isolate)) {
160 189 : THROW_NEW_ERROR_RETURN_FAILURE(
161 : isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
162 : isolate->factory()->NewStringFromAsciiChecked(
163 : "String.prototype.includes")));
164 : }
165 : Handle<String> receiver_string;
166 846 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
167 : Object::ToString(isolate, receiver));
168 :
169 : // Check if the search string is a regExp and fail if it is.
170 405 : Handle<Object> search = args.at(1);
171 405 : Maybe<bool> is_reg_exp = RegExpUtils::IsRegExp(isolate, search);
172 405 : if (is_reg_exp.IsNothing()) {
173 : DCHECK(isolate->has_pending_exception());
174 : return ReadOnlyRoots(isolate).exception();
175 : }
176 405 : if (is_reg_exp.FromJust()) {
177 216 : THROW_NEW_ERROR_RETURN_FAILURE(
178 : isolate, NewTypeError(MessageTemplate::kFirstArgumentNotRegExp,
179 : isolate->factory()->NewStringFromStaticChars(
180 : "String.prototype.includes")));
181 : }
182 : Handle<String> search_string;
183 666 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
184 : Object::ToString(isolate, args.at(1)));
185 : Handle<Object> position;
186 666 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
187 : Object::ToInteger(isolate, args.at(2)));
188 :
189 333 : uint32_t index = receiver_string->ToValidIndex(*position);
190 : int index_in_str =
191 333 : String::IndexOf(isolate, receiver_string, search_string, index);
192 666 : return *isolate->factory()->ToBoolean(index_in_str != -1);
193 : }
194 :
195 : // ES6 #sec-string.prototype.indexof
196 : // String.prototype.indexOf(searchString [, position])
197 789 : RUNTIME_FUNCTION(Runtime_StringIndexOf) {
198 789 : HandleScope scope(isolate);
199 : DCHECK_EQ(3, args.length());
200 789 : return String::IndexOf(isolate, args.at(0), args.at(1), args.at(2));
201 : }
202 :
203 : // ES6 #sec-string.prototype.indexof
204 : // String.prototype.indexOf(searchString, position)
205 : // Fast version that assumes that does not perform conversions of the incoming
206 : // arguments.
207 1028923 : RUNTIME_FUNCTION(Runtime_StringIndexOfUnchecked) {
208 1028923 : HandleScope scope(isolate);
209 : DCHECK_EQ(3, args.length());
210 1028923 : Handle<String> receiver_string = args.at<String>(0);
211 1028923 : Handle<String> search_string = args.at<String>(1);
212 1028923 : int index = std::min(std::max(args.smi_at(2), 0), receiver_string->length());
213 :
214 : return Smi::FromInt(String::IndexOf(isolate, receiver_string, search_string,
215 1028923 : static_cast<uint32_t>(index)));
216 : }
217 :
218 5 : RUNTIME_FUNCTION(Runtime_StringLastIndexOf) {
219 5 : HandleScope handle_scope(isolate);
220 : return String::LastIndexOf(isolate, args.at(0), args.at(1),
221 10 : isolate->factory()->undefined_value());
222 : }
223 :
224 847238 : RUNTIME_FUNCTION(Runtime_StringSubstring) {
225 847238 : HandleScope scope(isolate);
226 : DCHECK_EQ(3, args.length());
227 1694476 : CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
228 1694476 : CONVERT_INT32_ARG_CHECKED(start, 1);
229 1694476 : CONVERT_INT32_ARG_CHECKED(end, 2);
230 : DCHECK_LE(0, start);
231 : DCHECK_LE(start, end);
232 : DCHECK_LE(end, string->length());
233 847238 : isolate->counters()->sub_string_runtime()->Increment();
234 1694476 : return *isolate->factory()->NewSubString(string, start, end);
235 : }
236 :
237 6836647 : RUNTIME_FUNCTION(Runtime_StringAdd) {
238 6836647 : HandleScope scope(isolate);
239 : DCHECK_EQ(2, args.length());
240 13673294 : CONVERT_ARG_HANDLE_CHECKED(String, str1, 0);
241 13673294 : CONVERT_ARG_HANDLE_CHECKED(String, str2, 1);
242 6836647 : isolate->counters()->string_add_runtime()->Increment();
243 13673294 : RETURN_RESULT_OR_FAILURE(isolate,
244 6836647 : isolate->factory()->NewConsString(str1, str2));
245 : }
246 :
247 :
248 900 : RUNTIME_FUNCTION(Runtime_InternalizeString) {
249 900 : HandleScope handles(isolate);
250 : DCHECK_EQ(1, args.length());
251 1800 : CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
252 1800 : return *isolate->factory()->InternalizeString(string);
253 : }
254 :
255 112024 : RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
256 112024 : HandleScope handle_scope(isolate);
257 : DCHECK_EQ(2, args.length());
258 :
259 224048 : CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
260 224048 : CONVERT_NUMBER_CHECKED(uint32_t, i, Uint32, args[1]);
261 :
262 : // Flatten the string. If someone wants to get a char at an index
263 : // in a cons string, it is likely that more indices will be
264 : // accessed.
265 112024 : subject = String::Flatten(isolate, subject);
266 :
267 112024 : if (i >= static_cast<uint32_t>(subject->length())) {
268 : return ReadOnlyRoots(isolate).nan_value();
269 : }
270 :
271 336072 : return Smi::FromInt(subject->Get(i));
272 : }
273 :
274 90695 : RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
275 90695 : HandleScope scope(isolate);
276 : DCHECK_EQ(3, args.length());
277 181390 : CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
278 : int32_t array_length;
279 90695 : if (!args[1]->ToInt32(&array_length)) {
280 0 : THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
281 : }
282 181390 : CONVERT_ARG_HANDLE_CHECKED(String, special, 2);
283 :
284 90695 : size_t actual_array_length = 0;
285 90695 : CHECK(TryNumberToSize(array->length(), &actual_array_length));
286 90695 : CHECK_GE(array_length, 0);
287 90695 : 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 90695 : CHECK(array->HasFastElements());
293 90695 : JSObject::EnsureCanContainHeapObjectElements(array);
294 :
295 90695 : int special_length = special->length();
296 90695 : if (!array->HasObjectElements()) {
297 0 : return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
298 : }
299 :
300 : int length;
301 90695 : bool one_byte = special->HasOnlyOneByteChars();
302 :
303 : {
304 : DisallowHeapAllocation no_gc;
305 181390 : FixedArray fixed_array = FixedArray::cast(array->elements());
306 90695 : if (fixed_array->length() < array_length) {
307 0 : array_length = fixed_array->length();
308 : }
309 :
310 90695 : if (array_length == 0) {
311 : return ReadOnlyRoots(isolate).empty_string();
312 90695 : } else if (array_length == 1) {
313 90036 : Object first = fixed_array->get(0);
314 180072 : if (first->IsString()) return first;
315 : }
316 : length = StringBuilderConcatLength(special_length, fixed_array,
317 659 : array_length, &one_byte);
318 : }
319 :
320 659 : if (length == -1) {
321 0 : return isolate->Throw(ReadOnlyRoots(isolate).illegal_argument_string());
322 : }
323 659 : if (length == 0) {
324 : return ReadOnlyRoots(isolate).empty_string();
325 : }
326 :
327 659 : if (one_byte) {
328 : Handle<SeqOneByteString> answer;
329 1308 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
330 : isolate, answer, isolate->factory()->NewRawOneByteString(length));
331 : DisallowHeapAllocation no_gc;
332 : StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
333 1290 : FixedArray::cast(array->elements()),
334 2580 : array_length);
335 : return *answer;
336 : } else {
337 : Handle<SeqTwoByteString> answer;
338 10 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
339 : isolate, answer, isolate->factory()->NewRawTwoByteString(length));
340 : DisallowHeapAllocation no_gc;
341 : StringBuilderConcatHelper(*special, answer->GetChars(no_gc),
342 10 : FixedArray::cast(array->elements()),
343 20 : array_length);
344 : return *answer;
345 90695 : }
346 : }
347 :
348 : // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
349 0 : RUNTIME_FUNCTION(Runtime_StringBuilderJoin) {
350 0 : HandleScope scope(isolate);
351 : DCHECK_EQ(3, args.length());
352 0 : CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
353 : int32_t array_length;
354 0 : if (!args[1]->ToInt32(&array_length)) {
355 0 : THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
356 : }
357 0 : CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
358 0 : CHECK(array->HasObjectElements());
359 0 : CHECK_GE(array_length, 0);
360 :
361 0 : Handle<FixedArray> fixed_array(FixedArray::cast(array->elements()), isolate);
362 0 : if (fixed_array->length() < array_length) {
363 0 : array_length = fixed_array->length();
364 : }
365 :
366 0 : if (array_length == 0) {
367 : return ReadOnlyRoots(isolate).empty_string();
368 0 : } else if (array_length == 1) {
369 0 : Object first = fixed_array->get(0);
370 0 : CHECK(first->IsString());
371 0 : return first;
372 : }
373 :
374 0 : int separator_length = separator->length();
375 0 : CHECK_GT(separator_length, 0);
376 : int max_nof_separators =
377 0 : (String::kMaxLength + separator_length - 1) / separator_length;
378 0 : if (max_nof_separators < (array_length - 1)) {
379 0 : THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
380 : }
381 0 : int length = (array_length - 1) * separator_length;
382 0 : for (int i = 0; i < array_length; i++) {
383 0 : Object element_obj = fixed_array->get(i);
384 0 : CHECK(element_obj->IsString());
385 0 : String element = String::cast(element_obj);
386 0 : int increment = element->length();
387 0 : if (increment > String::kMaxLength - length) {
388 : STATIC_ASSERT(String::kMaxLength < kMaxInt);
389 : length = kMaxInt; // Provoke exception;
390 0 : break;
391 : }
392 0 : length += increment;
393 : }
394 :
395 : Handle<SeqTwoByteString> answer;
396 0 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
397 : isolate, answer, isolate->factory()->NewRawTwoByteString(length));
398 :
399 : DisallowHeapAllocation no_gc;
400 :
401 0 : uc16* sink = answer->GetChars(no_gc);
402 : #ifdef DEBUG
403 : uc16* end = sink + length;
404 : #endif
405 :
406 0 : CHECK(fixed_array->get(0)->IsString());
407 0 : String first = String::cast(fixed_array->get(0));
408 0 : String separator_raw = *separator;
409 :
410 0 : int first_length = first->length();
411 0 : String::WriteToFlat(first, sink, 0, first_length);
412 0 : sink += first_length;
413 :
414 0 : for (int i = 1; i < array_length; i++) {
415 : DCHECK(sink + separator_length <= end);
416 0 : String::WriteToFlat(separator_raw, sink, 0, separator_length);
417 0 : sink += separator_length;
418 :
419 0 : CHECK(fixed_array->get(i)->IsString());
420 0 : String element = String::cast(fixed_array->get(i));
421 0 : int element_length = element->length();
422 : DCHECK(sink + element_length <= end);
423 0 : String::WriteToFlat(element, sink, 0, element_length);
424 0 : sink += element_length;
425 : }
426 : DCHECK(sink == end);
427 :
428 : // Use %_FastOneByteArrayJoin instead.
429 : DCHECK(!answer->IsOneByteRepresentation());
430 0 : return *answer;
431 : }
432 :
433 : template <typename sinkchar>
434 0 : static void WriteRepeatToFlat(String src, Vector<sinkchar> buffer, int cursor,
435 : int repeat, int length) {
436 0 : if (repeat == 0) return;
437 :
438 0 : sinkchar* start = &buffer[cursor];
439 0 : String::WriteToFlat<sinkchar>(src, start, 0, length);
440 :
441 : int done = 1;
442 0 : sinkchar* next = start + length;
443 :
444 0 : while (done < repeat) {
445 0 : int block = Min(done, repeat - done);
446 0 : int block_chars = block * length;
447 0 : CopyChars(next, start, block_chars);
448 : next += block_chars;
449 0 : done += block;
450 : }
451 : }
452 :
453 : // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
454 : template <typename Char>
455 0 : static void JoinSparseArrayWithSeparator(FixedArray elements,
456 : int elements_length,
457 : uint32_t array_length,
458 : String separator,
459 : Vector<Char> buffer) {
460 : DisallowHeapAllocation no_gc;
461 : int previous_separator_position = 0;
462 : int separator_length = separator->length();
463 : DCHECK_LT(0, separator_length);
464 : int cursor = 0;
465 0 : for (int i = 0; i < elements_length; i += 2) {
466 0 : int position = NumberToInt32(elements->get(i));
467 0 : String string = String::cast(elements->get(i + 1));
468 : int string_length = string->length();
469 0 : if (string->length() > 0) {
470 0 : int repeat = position - previous_separator_position;
471 0 : WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat,
472 : separator_length);
473 0 : cursor += repeat * separator_length;
474 : previous_separator_position = position;
475 0 : String::WriteToFlat<Char>(string, &buffer[cursor], 0, string_length);
476 0 : cursor += string->length();
477 : }
478 : }
479 :
480 0 : int last_array_index = static_cast<int>(array_length - 1);
481 : // Array length must be representable as a signed 32-bit number,
482 : // otherwise the total string length would have been too large.
483 : DCHECK_LE(array_length, 0x7FFFFFFF); // Is int32_t.
484 0 : int repeat = last_array_index - previous_separator_position;
485 0 : WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat, separator_length);
486 : cursor += repeat * separator_length;
487 : DCHECK(cursor <= buffer.length());
488 0 : }
489 :
490 : // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
491 0 : RUNTIME_FUNCTION(Runtime_SparseJoinWithSeparator) {
492 0 : HandleScope scope(isolate);
493 : DCHECK_EQ(3, args.length());
494 0 : CONVERT_ARG_HANDLE_CHECKED(JSArray, elements_array, 0);
495 0 : CONVERT_NUMBER_CHECKED(uint32_t, array_length, Uint32, args[1]);
496 0 : CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
497 : // elements_array is fast-mode JSarray of alternating positions
498 : // (increasing order) and strings.
499 0 : CHECK(elements_array->HasSmiOrObjectElements());
500 : // array_length is length of original array (used to add separators);
501 : // separator is string to put between elements. Assumed to be non-empty.
502 0 : CHECK_GT(array_length, 0);
503 :
504 : // Find total length of join result.
505 : int string_length = 0;
506 0 : bool is_one_byte = separator->IsOneByteRepresentation();
507 : bool overflow = false;
508 0 : CONVERT_NUMBER_CHECKED(int, elements_length, Int32, elements_array->length());
509 0 : CHECK(elements_length <= elements_array->elements()->length());
510 0 : CHECK_EQ(elements_length & 1, 0); // Even length.
511 0 : FixedArray elements = FixedArray::cast(elements_array->elements());
512 : {
513 : DisallowHeapAllocation no_gc;
514 0 : for (int i = 0; i < elements_length; i += 2) {
515 0 : String string = String::cast(elements->get(i + 1));
516 0 : int length = string->length();
517 0 : if (is_one_byte && !string->IsOneByteRepresentation()) {
518 : is_one_byte = false;
519 : }
520 0 : if (length > String::kMaxLength ||
521 0 : String::kMaxLength - length < string_length) {
522 : overflow = true;
523 0 : break;
524 : }
525 0 : string_length += length;
526 : }
527 : }
528 :
529 0 : int separator_length = separator->length();
530 0 : if (!overflow && separator_length > 0) {
531 0 : if (array_length <= 0x7FFFFFFFu) {
532 0 : int separator_count = static_cast<int>(array_length) - 1;
533 0 : int remaining_length = String::kMaxLength - string_length;
534 0 : if ((remaining_length / separator_length) >= separator_count) {
535 0 : string_length += separator_length * (array_length - 1);
536 : } else {
537 : // Not room for the separators within the maximal string length.
538 : overflow = true;
539 : }
540 : } else {
541 : // Nonempty separator and at least 2^31-1 separators necessary
542 : // means that the string is too large to create.
543 : STATIC_ASSERT(String::kMaxLength < 0x7FFFFFFF);
544 : overflow = true;
545 : }
546 : }
547 0 : if (overflow) {
548 : // Throw an exception if the resulting string is too large. See
549 : // https://code.google.com/p/chromium/issues/detail?id=336820
550 : // for details.
551 0 : THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
552 : }
553 :
554 0 : if (is_one_byte) {
555 : Handle<SeqOneByteString> result = isolate->factory()
556 0 : ->NewRawOneByteString(string_length)
557 0 : .ToHandleChecked();
558 : DisallowHeapAllocation no_gc;
559 : JoinSparseArrayWithSeparator<uint8_t>(
560 0 : FixedArray::cast(elements_array->elements()), elements_length,
561 : array_length, *separator,
562 0 : Vector<uint8_t>(result->GetChars(no_gc), string_length));
563 : return *result;
564 : } else {
565 : Handle<SeqTwoByteString> result = isolate->factory()
566 0 : ->NewRawTwoByteString(string_length)
567 0 : .ToHandleChecked();
568 : DisallowHeapAllocation no_gc;
569 : JoinSparseArrayWithSeparator<uc16>(
570 0 : FixedArray::cast(elements_array->elements()), elements_length,
571 : array_length, *separator,
572 0 : Vector<uc16>(result->GetChars(no_gc), string_length));
573 : return *result;
574 0 : }
575 : }
576 :
577 : // Copies Latin1 characters to the given fixed array looking up
578 : // one-char strings in the cache. Gives up on the first char that is
579 : // not in the cache and fills the remainder with smi zeros. Returns
580 : // the length of the successfully copied prefix.
581 110 : static int CopyCachedOneByteCharsToArray(Heap* heap, const uint8_t* chars,
582 : FixedArray elements, int length) {
583 : DisallowHeapAllocation no_gc;
584 110 : FixedArray one_byte_cache = heap->single_character_string_cache();
585 : Object undefined = ReadOnlyRoots(heap).undefined_value();
586 : int i;
587 : WriteBarrierMode mode = elements->GetWriteBarrierMode(no_gc);
588 4220 : for (i = 0; i < length; ++i) {
589 4216 : Object value = one_byte_cache->get(chars[i]);
590 4216 : if (value == undefined) break;
591 4110 : elements->set(i, value, mode);
592 : }
593 110 : if (i < length) {
594 106 : MemsetTagged(elements->RawFieldOfElementAt(i), Smi::kZero, length - i);
595 : }
596 : #ifdef DEBUG
597 : for (int j = 0; j < length; ++j) {
598 : Object element = elements->get(j);
599 : DCHECK(element == Smi::kZero ||
600 : (element->IsString() && String::cast(element)->LooksValid()));
601 : }
602 : #endif
603 110 : return i;
604 : }
605 :
606 : // Converts a String to JSArray.
607 : // For example, "foo" => ["f", "o", "o"].
608 146 : RUNTIME_FUNCTION(Runtime_StringToArray) {
609 146 : HandleScope scope(isolate);
610 : DCHECK_EQ(2, args.length());
611 292 : CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
612 292 : CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
613 :
614 146 : s = String::Flatten(isolate, s);
615 146 : const int length = static_cast<int>(Min<uint32_t>(s->length(), limit));
616 :
617 : Handle<FixedArray> elements;
618 : int position = 0;
619 292 : if (s->IsFlat() && s->IsOneByteRepresentation()) {
620 : // Try using cached chars where possible.
621 110 : elements = isolate->factory()->NewUninitializedFixedArray(length);
622 :
623 : DisallowHeapAllocation no_gc;
624 110 : String::FlatContent content = s->GetFlatContent(no_gc);
625 110 : if (content.IsOneByte()) {
626 110 : Vector<const uint8_t> chars = content.ToOneByteVector();
627 : // Note, this will initialize all elements (not only the prefix)
628 : // to prevent GC from seeing partially initialized array.
629 : position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.start(),
630 110 : *elements, length);
631 : } else {
632 : MemsetTagged(elements->data_start(),
633 0 : ReadOnlyRoots(isolate).undefined_value(), length);
634 : }
635 : } else {
636 36 : elements = isolate->factory()->NewFixedArray(length);
637 : }
638 56163 : for (int i = position; i < length; ++i) {
639 : Handle<Object> str =
640 112326 : isolate->factory()->LookupSingleCharacterStringFromCode(s->Get(i));
641 56163 : elements->set(i, *str);
642 : }
643 :
644 : #ifdef DEBUG
645 : for (int i = 0; i < length; ++i) {
646 : DCHECK_EQ(String::cast(elements->get(i))->length(), 1);
647 : }
648 : #endif
649 :
650 292 : return *isolate->factory()->NewJSArrayWithElements(elements);
651 : }
652 :
653 16493 : RUNTIME_FUNCTION(Runtime_StringLessThan) {
654 16493 : HandleScope handle_scope(isolate);
655 : DCHECK_EQ(2, args.length());
656 32986 : CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
657 32986 : CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
658 16493 : ComparisonResult result = String::Compare(isolate, x, y);
659 : DCHECK_NE(result, ComparisonResult::kUndefined);
660 : return isolate->heap()->ToBoolean(
661 16493 : ComparisonResultToBool(Operation::kLessThan, result));
662 : }
663 :
664 3121244 : RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual) {
665 3121244 : HandleScope handle_scope(isolate);
666 : DCHECK_EQ(2, args.length());
667 6242488 : CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
668 6242488 : CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
669 3121244 : ComparisonResult result = String::Compare(isolate, x, y);
670 : DCHECK_NE(result, ComparisonResult::kUndefined);
671 : return isolate->heap()->ToBoolean(
672 3121244 : ComparisonResultToBool(Operation::kLessThanOrEqual, result));
673 : }
674 :
675 0 : RUNTIME_FUNCTION(Runtime_StringGreaterThan) {
676 0 : HandleScope handle_scope(isolate);
677 : DCHECK_EQ(2, args.length());
678 0 : CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
679 0 : CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
680 0 : ComparisonResult result = String::Compare(isolate, x, y);
681 : DCHECK_NE(result, ComparisonResult::kUndefined);
682 : return isolate->heap()->ToBoolean(
683 0 : ComparisonResultToBool(Operation::kGreaterThan, result));
684 : }
685 :
686 1285298 : RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual) {
687 1285298 : HandleScope handle_scope(isolate);
688 : DCHECK_EQ(2, args.length());
689 2570596 : CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
690 2570596 : CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
691 1285298 : ComparisonResult result = String::Compare(isolate, x, y);
692 : DCHECK_NE(result, ComparisonResult::kUndefined);
693 : return isolate->heap()->ToBoolean(
694 1285298 : ComparisonResultToBool(Operation::kGreaterThanOrEqual, result));
695 : }
696 :
697 660771 : RUNTIME_FUNCTION(Runtime_StringEqual) {
698 660771 : HandleScope handle_scope(isolate);
699 : DCHECK_EQ(2, args.length());
700 1321542 : CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
701 1321542 : CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
702 660771 : return isolate->heap()->ToBoolean(String::Equals(isolate, x, y));
703 : }
704 :
705 648 : RUNTIME_FUNCTION(Runtime_FlattenString) {
706 648 : HandleScope scope(isolate);
707 : DCHECK_EQ(1, args.length());
708 1296 : CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
709 1296 : return *String::Flatten(isolate, str);
710 : }
711 :
712 152 : RUNTIME_FUNCTION(Runtime_StringMaxLength) {
713 : SealHandleScope shs(isolate);
714 152 : return Smi::FromInt(String::kMaxLength);
715 : }
716 :
717 1313 : RUNTIME_FUNCTION(Runtime_StringCompareSequence) {
718 1313 : HandleScope handle_scope(isolate);
719 : DCHECK_EQ(3, args.length());
720 2626 : CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
721 2626 : CONVERT_ARG_HANDLE_CHECKED(String, search_string, 1);
722 2626 : CONVERT_NUMBER_CHECKED(int, start, Int32, args[2]);
723 :
724 : // Check if start + searchLength is in bounds.
725 : DCHECK_LE(start + search_string->length(), string->length());
726 :
727 2626 : FlatStringReader string_reader(isolate, String::Flatten(isolate, string));
728 : FlatStringReader search_reader(isolate,
729 2626 : String::Flatten(isolate, search_string));
730 :
731 82823 : for (int i = 0; i < search_string->length(); i++) {
732 40791 : if (string_reader.Get(start + i) != search_reader.Get(i)) {
733 : return ReadOnlyRoots(isolate).false_value();
734 : }
735 : }
736 :
737 1313 : return ReadOnlyRoots(isolate).true_value();
738 : }
739 :
740 603 : RUNTIME_FUNCTION(Runtime_StringEscapeQuotes) {
741 603 : HandleScope handle_scope(isolate);
742 : DCHECK_EQ(1, args.length());
743 1206 : CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
744 :
745 : // Equivalent to global replacement `string.replace(/"/g, """)`, but this
746 : // does not modify any global state (e.g. the regexp match info).
747 :
748 603 : const int string_length = string->length();
749 : Handle<String> quotes =
750 603 : isolate->factory()->LookupSingleCharacterStringFromCode('"');
751 :
752 603 : int index = String::IndexOf(isolate, string, quotes, 0);
753 :
754 : // No quotes, nothing to do.
755 603 : if (index == -1) return *string;
756 :
757 : // Find all quotes.
758 270 : std::vector<int> indices = {index};
759 189 : while (index + 1 < string_length) {
760 90 : index = String::IndexOf(isolate, string, quotes, index + 1);
761 90 : if (index == -1) break;
762 54 : indices.emplace_back(index);
763 : }
764 :
765 : // Build the replacement string.
766 : Handle<String> replacement =
767 135 : isolate->factory()->NewStringFromAsciiChecked(""");
768 135 : const int estimated_part_count = static_cast<int>(indices.size()) * 2 + 1;
769 : ReplacementStringBuilder builder(isolate->heap(), string,
770 135 : estimated_part_count);
771 :
772 : int prev_index = -1; // Start at -1 to avoid special-casing the first match.
773 324 : for (int index : indices) {
774 189 : const int slice_start = prev_index + 1;
775 : const int slice_end = index;
776 189 : if (slice_end > slice_start) {
777 45 : builder.AddSubjectSlice(slice_start, slice_end);
778 : }
779 189 : builder.AddString(replacement);
780 : prev_index = index;
781 : }
782 :
783 135 : if (prev_index < string_length - 1) {
784 36 : builder.AddSubjectSlice(prev_index + 1, string_length);
785 : }
786 :
787 873 : return *builder.ToString().ToHandleChecked();
788 : }
789 :
790 : } // namespace internal
791 178779 : } // namespace v8
|