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/runtime/runtime-utils.h"
6
7#include "src/arguments.h"
8#include "src/regexp/jsregexp-inl.h"
9#include "src/string-builder.h"
10#include "src/string-search.h"
11
12namespace v8 {
13namespace internal {
14
15// This may return an empty MaybeHandle if an exception is thrown or
16// we abort due to reaching the recursion limit.
17MaybeHandle<String> StringReplaceOneCharWithString(
18    Isolate* isolate, Handle<String> subject, Handle<String> search,
19    Handle<String> replace, bool* found, int recursion_limit) {
20  StackLimitCheck stackLimitCheck(isolate);
21  if (stackLimitCheck.HasOverflowed() || (recursion_limit == 0)) {
22    return MaybeHandle<String>();
23  }
24  recursion_limit--;
25  if (subject->IsConsString()) {
26    ConsString* cons = ConsString::cast(*subject);
27    Handle<String> first = Handle<String>(cons->first());
28    Handle<String> second = Handle<String>(cons->second());
29    Handle<String> new_first;
30    if (!StringReplaceOneCharWithString(isolate, first, search, replace, found,
31                                        recursion_limit).ToHandle(&new_first)) {
32      return MaybeHandle<String>();
33    }
34    if (*found) return isolate->factory()->NewConsString(new_first, second);
35
36    Handle<String> new_second;
37    if (!StringReplaceOneCharWithString(isolate, second, search, replace, found,
38                                        recursion_limit)
39             .ToHandle(&new_second)) {
40      return MaybeHandle<String>();
41    }
42    if (*found) return isolate->factory()->NewConsString(first, new_second);
43
44    return subject;
45  } else {
46    int index = String::IndexOf(isolate, subject, search, 0);
47    if (index == -1) return subject;
48    *found = true;
49    Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
50    Handle<String> cons1;
51    ASSIGN_RETURN_ON_EXCEPTION(
52        isolate, cons1, isolate->factory()->NewConsString(first, replace),
53        String);
54    Handle<String> second =
55        isolate->factory()->NewSubString(subject, index + 1, subject->length());
56    return isolate->factory()->NewConsString(cons1, second);
57  }
58}
59
60
61RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {
62  HandleScope scope(isolate);
63  DCHECK(args.length() == 3);
64  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
65  CONVERT_ARG_HANDLE_CHECKED(String, search, 1);
66  CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);
67
68  // If the cons string tree is too deep, we simply abort the recursion and
69  // retry with a flattened subject string.
70  const int kRecursionLimit = 0x1000;
71  bool found = false;
72  Handle<String> result;
73  if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
74                                     kRecursionLimit).ToHandle(&result)) {
75    return *result;
76  }
77  if (isolate->has_pending_exception()) return isolate->heap()->exception();
78
79  subject = String::Flatten(subject);
80  if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,
81                                     kRecursionLimit).ToHandle(&result)) {
82    return *result;
83  }
84  if (isolate->has_pending_exception()) return isolate->heap()->exception();
85  // In case of empty handle and no pending exception we have stack overflow.
86  return isolate->StackOverflow();
87}
88
89
90RUNTIME_FUNCTION(Runtime_StringIndexOf) {
91  HandleScope scope(isolate);
92  DCHECK(args.length() == 3);
93  return String::IndexOf(isolate, args.at<Object>(0), args.at<Object>(1),
94                         args.at<Object>(2));
95}
96
97RUNTIME_FUNCTION(Runtime_StringLastIndexOf) {
98  HandleScope handle_scope(isolate);
99  return String::LastIndexOf(isolate, args.at<Object>(0), args.at<Object>(1),
100                             isolate->factory()->undefined_value());
101}
102
103RUNTIME_FUNCTION(Runtime_SubString) {
104  HandleScope scope(isolate);
105  DCHECK(args.length() == 3);
106
107  CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
108  int start, end;
109  // We have a fast integer-only case here to avoid a conversion to double in
110  // the common case where from and to are Smis.
111  if (args[1]->IsSmi() && args[2]->IsSmi()) {
112    CONVERT_SMI_ARG_CHECKED(from_number, 1);
113    CONVERT_SMI_ARG_CHECKED(to_number, 2);
114    start = from_number;
115    end = to_number;
116  } else if (args[1]->IsNumber() && args[2]->IsNumber()) {
117    CONVERT_DOUBLE_ARG_CHECKED(from_number, 1);
118    CONVERT_DOUBLE_ARG_CHECKED(to_number, 2);
119    start = FastD2IChecked(from_number);
120    end = FastD2IChecked(to_number);
121  } else {
122    return isolate->ThrowIllegalOperation();
123  }
124  // The following condition is intentionally robust because the SubStringStub
125  // delegates here and we test this in cctest/test-strings/RobustSubStringStub.
126  if (end < start || start < 0 || end > string->length()) {
127    return isolate->ThrowIllegalOperation();
128  }
129  isolate->counters()->sub_string_runtime()->Increment();
130
131  return *isolate->factory()->NewSubString(string, start, end);
132}
133
134
135RUNTIME_FUNCTION(Runtime_StringAdd) {
136  HandleScope scope(isolate);
137  DCHECK(args.length() == 2);
138  CONVERT_ARG_HANDLE_CHECKED(Object, obj1, 0);
139  CONVERT_ARG_HANDLE_CHECKED(Object, obj2, 1);
140  isolate->counters()->string_add_runtime()->Increment();
141  MaybeHandle<String> maybe_str1(Object::ToString(isolate, obj1));
142  MaybeHandle<String> maybe_str2(Object::ToString(isolate, obj2));
143  Handle<String> str1;
144  Handle<String> str2;
145  maybe_str1.ToHandle(&str1);
146  maybe_str2.ToHandle(&str2);
147  RETURN_RESULT_OR_FAILURE(isolate,
148                           isolate->factory()->NewConsString(str1, str2));
149}
150
151
152RUNTIME_FUNCTION(Runtime_InternalizeString) {
153  HandleScope handles(isolate);
154  DCHECK(args.length() == 1);
155  CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
156  return *isolate->factory()->InternalizeString(string);
157}
158
159
160RUNTIME_FUNCTION(Runtime_StringCharCodeAtRT) {
161  HandleScope handle_scope(isolate);
162  DCHECK(args.length() == 2);
163
164  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
165  CONVERT_NUMBER_CHECKED(uint32_t, i, Uint32, args[1]);
166
167  // Flatten the string.  If someone wants to get a char at an index
168  // in a cons string, it is likely that more indices will be
169  // accessed.
170  subject = String::Flatten(subject);
171
172  if (i >= static_cast<uint32_t>(subject->length())) {
173    return isolate->heap()->nan_value();
174  }
175
176  return Smi::FromInt(subject->Get(i));
177}
178
179
180RUNTIME_FUNCTION(Runtime_StringCompare) {
181  HandleScope handle_scope(isolate);
182  DCHECK_EQ(2, args.length());
183  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
184  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
185  isolate->counters()->string_compare_runtime()->Increment();
186  switch (String::Compare(x, y)) {
187    case ComparisonResult::kLessThan:
188      return Smi::FromInt(LESS);
189    case ComparisonResult::kEqual:
190      return Smi::FromInt(EQUAL);
191    case ComparisonResult::kGreaterThan:
192      return Smi::FromInt(GREATER);
193    case ComparisonResult::kUndefined:
194      break;
195  }
196  UNREACHABLE();
197  return Smi::kZero;
198}
199
200
201RUNTIME_FUNCTION(Runtime_StringBuilderConcat) {
202  HandleScope scope(isolate);
203  DCHECK(args.length() == 3);
204  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
205  int32_t array_length;
206  if (!args[1]->ToInt32(&array_length)) {
207    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
208  }
209  CONVERT_ARG_HANDLE_CHECKED(String, special, 2);
210
211  size_t actual_array_length = 0;
212  CHECK(TryNumberToSize(array->length(), &actual_array_length));
213  CHECK(array_length >= 0);
214  CHECK(static_cast<size_t>(array_length) <= actual_array_length);
215
216  // This assumption is used by the slice encoding in one or two smis.
217  DCHECK(Smi::kMaxValue >= String::kMaxLength);
218
219  CHECK(array->HasFastElements());
220  JSObject::EnsureCanContainHeapObjectElements(array);
221
222  int special_length = special->length();
223  if (!array->HasFastObjectElements()) {
224    return isolate->Throw(isolate->heap()->illegal_argument_string());
225  }
226
227  int length;
228  bool one_byte = special->HasOnlyOneByteChars();
229
230  {
231    DisallowHeapAllocation no_gc;
232    FixedArray* fixed_array = FixedArray::cast(array->elements());
233    if (fixed_array->length() < array_length) {
234      array_length = fixed_array->length();
235    }
236
237    if (array_length == 0) {
238      return isolate->heap()->empty_string();
239    } else if (array_length == 1) {
240      Object* first = fixed_array->get(0);
241      if (first->IsString()) return first;
242    }
243    length = StringBuilderConcatLength(special_length, fixed_array,
244                                       array_length, &one_byte);
245  }
246
247  if (length == -1) {
248    return isolate->Throw(isolate->heap()->illegal_argument_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    StringBuilderConcatHelper(*special, answer->GetChars(),
256                              FixedArray::cast(array->elements()),
257                              array_length);
258    return *answer;
259  } else {
260    Handle<SeqTwoByteString> answer;
261    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
262        isolate, answer, isolate->factory()->NewRawTwoByteString(length));
263    StringBuilderConcatHelper(*special, answer->GetChars(),
264                              FixedArray::cast(array->elements()),
265                              array_length);
266    return *answer;
267  }
268}
269
270
271RUNTIME_FUNCTION(Runtime_StringBuilderJoin) {
272  HandleScope scope(isolate);
273  DCHECK(args.length() == 3);
274  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
275  int32_t array_length;
276  if (!args[1]->ToInt32(&array_length)) {
277    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
278  }
279  CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
280  CHECK(array->HasFastObjectElements());
281  CHECK(array_length >= 0);
282
283  Handle<FixedArray> fixed_array(FixedArray::cast(array->elements()));
284  if (fixed_array->length() < array_length) {
285    array_length = fixed_array->length();
286  }
287
288  if (array_length == 0) {
289    return isolate->heap()->empty_string();
290  } else if (array_length == 1) {
291    Object* first = fixed_array->get(0);
292    CHECK(first->IsString());
293    return first;
294  }
295
296  int separator_length = separator->length();
297  CHECK(separator_length > 0);
298  int max_nof_separators =
299      (String::kMaxLength + separator_length - 1) / separator_length;
300  if (max_nof_separators < (array_length - 1)) {
301    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
302  }
303  int length = (array_length - 1) * separator_length;
304  for (int i = 0; i < array_length; i++) {
305    Object* element_obj = fixed_array->get(i);
306    CHECK(element_obj->IsString());
307    String* element = String::cast(element_obj);
308    int increment = element->length();
309    if (increment > String::kMaxLength - length) {
310      STATIC_ASSERT(String::kMaxLength < kMaxInt);
311      length = kMaxInt;  // Provoke exception;
312      break;
313    }
314    length += increment;
315  }
316
317  Handle<SeqTwoByteString> answer;
318  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
319      isolate, answer, isolate->factory()->NewRawTwoByteString(length));
320
321  DisallowHeapAllocation no_gc;
322
323  uc16* sink = answer->GetChars();
324#ifdef DEBUG
325  uc16* end = sink + length;
326#endif
327
328  CHECK(fixed_array->get(0)->IsString());
329  String* first = String::cast(fixed_array->get(0));
330  String* separator_raw = *separator;
331
332  int first_length = first->length();
333  String::WriteToFlat(first, sink, 0, first_length);
334  sink += first_length;
335
336  for (int i = 1; i < array_length; i++) {
337    DCHECK(sink + separator_length <= end);
338    String::WriteToFlat(separator_raw, sink, 0, separator_length);
339    sink += separator_length;
340
341    CHECK(fixed_array->get(i)->IsString());
342    String* element = String::cast(fixed_array->get(i));
343    int element_length = element->length();
344    DCHECK(sink + element_length <= end);
345    String::WriteToFlat(element, sink, 0, element_length);
346    sink += element_length;
347  }
348  DCHECK(sink == end);
349
350  // Use %_FastOneByteArrayJoin instead.
351  DCHECK(!answer->IsOneByteRepresentation());
352  return *answer;
353}
354
355template <typename sinkchar>
356static void WriteRepeatToFlat(String* src, Vector<sinkchar> buffer, int cursor,
357                              int repeat, int length) {
358  if (repeat == 0) return;
359
360  sinkchar* start = &buffer[cursor];
361  String::WriteToFlat<sinkchar>(src, start, 0, length);
362
363  int done = 1;
364  sinkchar* next = start + length;
365
366  while (done < repeat) {
367    int block = Min(done, repeat - done);
368    int block_chars = block * length;
369    CopyChars(next, start, block_chars);
370    next += block_chars;
371    done += block;
372  }
373}
374
375template <typename Char>
376static void JoinSparseArrayWithSeparator(FixedArray* elements,
377                                         int elements_length,
378                                         uint32_t array_length,
379                                         String* separator,
380                                         Vector<Char> buffer) {
381  DisallowHeapAllocation no_gc;
382  int previous_separator_position = 0;
383  int separator_length = separator->length();
384  DCHECK_LT(0, separator_length);
385  int cursor = 0;
386  for (int i = 0; i < elements_length; i += 2) {
387    int position = NumberToInt32(elements->get(i));
388    String* string = String::cast(elements->get(i + 1));
389    int string_length = string->length();
390    if (string->length() > 0) {
391      int repeat = position - previous_separator_position;
392      WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat,
393                              separator_length);
394      cursor += repeat * separator_length;
395      previous_separator_position = position;
396      String::WriteToFlat<Char>(string, &buffer[cursor], 0, string_length);
397      cursor += string->length();
398    }
399  }
400
401  int last_array_index = static_cast<int>(array_length - 1);
402  // Array length must be representable as a signed 32-bit number,
403  // otherwise the total string length would have been too large.
404  DCHECK(array_length <= 0x7fffffff);  // Is int32_t.
405  int repeat = last_array_index - previous_separator_position;
406  WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat, separator_length);
407  cursor += repeat * separator_length;
408  DCHECK(cursor <= buffer.length());
409}
410
411
412RUNTIME_FUNCTION(Runtime_SparseJoinWithSeparator) {
413  HandleScope scope(isolate);
414  DCHECK(args.length() == 3);
415  CONVERT_ARG_HANDLE_CHECKED(JSArray, elements_array, 0);
416  CONVERT_NUMBER_CHECKED(uint32_t, array_length, Uint32, args[1]);
417  CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
418  // elements_array is fast-mode JSarray of alternating positions
419  // (increasing order) and strings.
420  CHECK(elements_array->HasFastSmiOrObjectElements());
421  // array_length is length of original array (used to add separators);
422  // separator is string to put between elements. Assumed to be non-empty.
423  CHECK(array_length > 0);
424
425  // Find total length of join result.
426  int string_length = 0;
427  bool is_one_byte = separator->IsOneByteRepresentation();
428  bool overflow = false;
429  CONVERT_NUMBER_CHECKED(int, elements_length, Int32, elements_array->length());
430  CHECK(elements_length <= elements_array->elements()->length());
431  CHECK((elements_length & 1) == 0);  // Even length.
432  FixedArray* elements = FixedArray::cast(elements_array->elements());
433  {
434    DisallowHeapAllocation no_gc;
435    for (int i = 0; i < elements_length; i += 2) {
436      String* string = String::cast(elements->get(i + 1));
437      int length = string->length();
438      if (is_one_byte && !string->IsOneByteRepresentation()) {
439        is_one_byte = false;
440      }
441      if (length > String::kMaxLength ||
442          String::kMaxLength - length < string_length) {
443        overflow = true;
444        break;
445      }
446      string_length += length;
447    }
448  }
449
450  int separator_length = separator->length();
451  if (!overflow && separator_length > 0) {
452    if (array_length <= 0x7fffffffu) {
453      int separator_count = static_cast<int>(array_length) - 1;
454      int remaining_length = String::kMaxLength - string_length;
455      if ((remaining_length / separator_length) >= separator_count) {
456        string_length += separator_length * (array_length - 1);
457      } else {
458        // Not room for the separators within the maximal string length.
459        overflow = true;
460      }
461    } else {
462      // Nonempty separator and at least 2^31-1 separators necessary
463      // means that the string is too large to create.
464      STATIC_ASSERT(String::kMaxLength < 0x7fffffff);
465      overflow = true;
466    }
467  }
468  if (overflow) {
469    // Throw an exception if the resulting string is too large. See
470    // https://code.google.com/p/chromium/issues/detail?id=336820
471    // for details.
472    THROW_NEW_ERROR_RETURN_FAILURE(isolate, NewInvalidStringLengthError());
473  }
474
475  if (is_one_byte) {
476    Handle<SeqOneByteString> result = isolate->factory()
477                                          ->NewRawOneByteString(string_length)
478                                          .ToHandleChecked();
479    JoinSparseArrayWithSeparator<uint8_t>(
480        FixedArray::cast(elements_array->elements()), elements_length,
481        array_length, *separator,
482        Vector<uint8_t>(result->GetChars(), string_length));
483    return *result;
484  } else {
485    Handle<SeqTwoByteString> result = isolate->factory()
486                                          ->NewRawTwoByteString(string_length)
487                                          .ToHandleChecked();
488    JoinSparseArrayWithSeparator<uc16>(
489        FixedArray::cast(elements_array->elements()), elements_length,
490        array_length, *separator,
491        Vector<uc16>(result->GetChars(), string_length));
492    return *result;
493  }
494}
495
496
497// Copies Latin1 characters to the given fixed array looking up
498// one-char strings in the cache. Gives up on the first char that is
499// not in the cache and fills the remainder with smi zeros. Returns
500// the length of the successfully copied prefix.
501static int CopyCachedOneByteCharsToArray(Heap* heap, const uint8_t* chars,
502                                         FixedArray* elements, int length) {
503  DisallowHeapAllocation no_gc;
504  FixedArray* one_byte_cache = heap->single_character_string_cache();
505  Object* undefined = heap->undefined_value();
506  int i;
507  WriteBarrierMode mode = elements->GetWriteBarrierMode(no_gc);
508  for (i = 0; i < length; ++i) {
509    Object* value = one_byte_cache->get(chars[i]);
510    if (value == undefined) break;
511    elements->set(i, value, mode);
512  }
513  if (i < length) {
514    DCHECK(Smi::kZero == 0);
515    memset(elements->data_start() + i, 0, kPointerSize * (length - i));
516  }
517#ifdef DEBUG
518  for (int j = 0; j < length; ++j) {
519    Object* element = elements->get(j);
520    DCHECK(element == Smi::kZero ||
521           (element->IsString() && String::cast(element)->LooksValid()));
522  }
523#endif
524  return i;
525}
526
527
528// Converts a String to JSArray.
529// For example, "foo" => ["f", "o", "o"].
530RUNTIME_FUNCTION(Runtime_StringToArray) {
531  HandleScope scope(isolate);
532  DCHECK(args.length() == 2);
533  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
534  CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
535
536  s = String::Flatten(s);
537  const int length = static_cast<int>(Min<uint32_t>(s->length(), limit));
538
539  Handle<FixedArray> elements;
540  int position = 0;
541  if (s->IsFlat() && s->IsOneByteRepresentation()) {
542    // Try using cached chars where possible.
543    elements = isolate->factory()->NewUninitializedFixedArray(length);
544
545    DisallowHeapAllocation no_gc;
546    String::FlatContent content = s->GetFlatContent();
547    if (content.IsOneByte()) {
548      Vector<const uint8_t> chars = content.ToOneByteVector();
549      // Note, this will initialize all elements (not only the prefix)
550      // to prevent GC from seeing partially initialized array.
551      position = CopyCachedOneByteCharsToArray(isolate->heap(), chars.start(),
552                                               *elements, length);
553    } else {
554      MemsetPointer(elements->data_start(), isolate->heap()->undefined_value(),
555                    length);
556    }
557  } else {
558    elements = isolate->factory()->NewFixedArray(length);
559  }
560  for (int i = position; i < length; ++i) {
561    Handle<Object> str =
562        isolate->factory()->LookupSingleCharacterStringFromCode(s->Get(i));
563    elements->set(i, *str);
564  }
565
566#ifdef DEBUG
567  for (int i = 0; i < length; ++i) {
568    DCHECK(String::cast(elements->get(i))->length() == 1);
569  }
570#endif
571
572  return *isolate->factory()->NewJSArrayWithElements(elements);
573}
574
575
576static inline bool ToUpperOverflows(uc32 character) {
577  // y with umlauts and the micro sign are the only characters that stop
578  // fitting into one-byte when converting to uppercase.
579  static const uc32 yuml_code = 0xff;
580  static const uc32 micro_code = 0xb5;
581  return (character == yuml_code || character == micro_code);
582}
583
584
585template <class Converter>
586MUST_USE_RESULT static Object* ConvertCaseHelper(
587    Isolate* isolate, String* string, SeqString* result, int result_length,
588    unibrow::Mapping<Converter, 128>* mapping) {
589  DisallowHeapAllocation no_gc;
590  // We try this twice, once with the assumption that the result is no longer
591  // than the input and, if that assumption breaks, again with the exact
592  // length.  This may not be pretty, but it is nicer than what was here before
593  // and I hereby claim my vaffel-is.
594  //
595  // NOTE: This assumes that the upper/lower case of an ASCII
596  // character is also ASCII.  This is currently the case, but it
597  // might break in the future if we implement more context and locale
598  // dependent upper/lower conversions.
599  bool has_changed_character = false;
600
601  // Convert all characters to upper case, assuming that they will fit
602  // in the buffer
603  StringCharacterStream stream(string);
604  unibrow::uchar chars[Converter::kMaxWidth];
605  // We can assume that the string is not empty
606  uc32 current = stream.GetNext();
607  bool ignore_overflow = Converter::kIsToLower || result->IsSeqTwoByteString();
608  for (int i = 0; i < result_length;) {
609    bool has_next = stream.HasMore();
610    uc32 next = has_next ? stream.GetNext() : 0;
611    int char_length = mapping->get(current, next, chars);
612    if (char_length == 0) {
613      // The case conversion of this character is the character itself.
614      result->Set(i, current);
615      i++;
616    } else if (char_length == 1 &&
617               (ignore_overflow || !ToUpperOverflows(current))) {
618      // Common case: converting the letter resulted in one character.
619      DCHECK(static_cast<uc32>(chars[0]) != current);
620      result->Set(i, chars[0]);
621      has_changed_character = true;
622      i++;
623    } else if (result_length == string->length()) {
624      bool overflows = ToUpperOverflows(current);
625      // We've assumed that the result would be as long as the
626      // input but here is a character that converts to several
627      // characters.  No matter, we calculate the exact length
628      // of the result and try the whole thing again.
629      //
630      // Note that this leaves room for optimization.  We could just
631      // memcpy what we already have to the result string.  Also,
632      // the result string is the last object allocated we could
633      // "realloc" it and probably, in the vast majority of cases,
634      // extend the existing string to be able to hold the full
635      // result.
636      int next_length = 0;
637      if (has_next) {
638        next_length = mapping->get(next, 0, chars);
639        if (next_length == 0) next_length = 1;
640      }
641      int current_length = i + char_length + next_length;
642      while (stream.HasMore()) {
643        current = stream.GetNext();
644        overflows |= ToUpperOverflows(current);
645        // NOTE: we use 0 as the next character here because, while
646        // the next character may affect what a character converts to,
647        // it does not in any case affect the length of what it convert
648        // to.
649        int char_length = mapping->get(current, 0, chars);
650        if (char_length == 0) char_length = 1;
651        current_length += char_length;
652        if (current_length > String::kMaxLength) {
653          AllowHeapAllocation allocate_error_and_return;
654          THROW_NEW_ERROR_RETURN_FAILURE(isolate,
655                                         NewInvalidStringLengthError());
656        }
657      }
658      // Try again with the real length.  Return signed if we need
659      // to allocate a two-byte string for to uppercase.
660      return (overflows && !ignore_overflow) ? Smi::FromInt(-current_length)
661                                             : Smi::FromInt(current_length);
662    } else {
663      for (int j = 0; j < char_length; j++) {
664        result->Set(i, chars[j]);
665        i++;
666      }
667      has_changed_character = true;
668    }
669    current = next;
670  }
671  if (has_changed_character) {
672    return result;
673  } else {
674    // If we didn't actually change anything in doing the conversion
675    // we simple return the result and let the converted string
676    // become garbage; there is no reason to keep two identical strings
677    // alive.
678    return string;
679  }
680}
681
682
683static const uintptr_t kOneInEveryByte = kUintptrAllBitsSet / 0xFF;
684static const uintptr_t kAsciiMask = kOneInEveryByte << 7;
685
686// Given a word and two range boundaries returns a word with high bit
687// set in every byte iff the corresponding input byte was strictly in
688// the range (m, n). All the other bits in the result are cleared.
689// This function is only useful when it can be inlined and the
690// boundaries are statically known.
691// Requires: all bytes in the input word and the boundaries must be
692// ASCII (less than 0x7F).
693static inline uintptr_t AsciiRangeMask(uintptr_t w, char m, char n) {
694  // Use strict inequalities since in edge cases the function could be
695  // further simplified.
696  DCHECK(0 < m && m < n);
697  // Has high bit set in every w byte less than n.
698  uintptr_t tmp1 = kOneInEveryByte * (0x7F + n) - w;
699  // Has high bit set in every w byte greater than m.
700  uintptr_t tmp2 = w + kOneInEveryByte * (0x7F - m);
701  return (tmp1 & tmp2 & (kOneInEveryByte * 0x80));
702}
703
704
705#ifdef DEBUG
706static bool CheckFastAsciiConvert(char* dst, const char* src, int length,
707                                  bool changed, bool is_to_lower) {
708  bool expected_changed = false;
709  for (int i = 0; i < length; i++) {
710    if (dst[i] == src[i]) continue;
711    expected_changed = true;
712    if (is_to_lower) {
713      DCHECK('A' <= src[i] && src[i] <= 'Z');
714      DCHECK(dst[i] == src[i] + ('a' - 'A'));
715    } else {
716      DCHECK('a' <= src[i] && src[i] <= 'z');
717      DCHECK(dst[i] == src[i] - ('a' - 'A'));
718    }
719  }
720  return (expected_changed == changed);
721}
722#endif
723
724
725template <class Converter>
726static bool FastAsciiConvert(char* dst, const char* src, int length,
727                             bool* changed_out) {
728#ifdef DEBUG
729  char* saved_dst = dst;
730  const char* saved_src = src;
731#endif
732  DisallowHeapAllocation no_gc;
733  // We rely on the distance between upper and lower case letters
734  // being a known power of 2.
735  DCHECK('a' - 'A' == (1 << 5));
736  // Boundaries for the range of input characters than require conversion.
737  static const char lo = Converter::kIsToLower ? 'A' - 1 : 'a' - 1;
738  static const char hi = Converter::kIsToLower ? 'Z' + 1 : 'z' + 1;
739  bool changed = false;
740  uintptr_t or_acc = 0;
741  const char* const limit = src + length;
742
743  // dst is newly allocated and always aligned.
744  DCHECK(IsAligned(reinterpret_cast<intptr_t>(dst), sizeof(uintptr_t)));
745  // Only attempt processing one word at a time if src is also aligned.
746  if (IsAligned(reinterpret_cast<intptr_t>(src), sizeof(uintptr_t))) {
747    // Process the prefix of the input that requires no conversion one aligned
748    // (machine) word at a time.
749    while (src <= limit - sizeof(uintptr_t)) {
750      const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
751      or_acc |= w;
752      if (AsciiRangeMask(w, lo, hi) != 0) {
753        changed = true;
754        break;
755      }
756      *reinterpret_cast<uintptr_t*>(dst) = w;
757      src += sizeof(uintptr_t);
758      dst += sizeof(uintptr_t);
759    }
760    // Process the remainder of the input performing conversion when
761    // required one word at a time.
762    while (src <= limit - sizeof(uintptr_t)) {
763      const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
764      or_acc |= w;
765      uintptr_t m = AsciiRangeMask(w, lo, hi);
766      // The mask has high (7th) bit set in every byte that needs
767      // conversion and we know that the distance between cases is
768      // 1 << 5.
769      *reinterpret_cast<uintptr_t*>(dst) = w ^ (m >> 2);
770      src += sizeof(uintptr_t);
771      dst += sizeof(uintptr_t);
772    }
773  }
774  // Process the last few bytes of the input (or the whole input if
775  // unaligned access is not supported).
776  while (src < limit) {
777    char c = *src;
778    or_acc |= c;
779    if (lo < c && c < hi) {
780      c ^= (1 << 5);
781      changed = true;
782    }
783    *dst = c;
784    ++src;
785    ++dst;
786  }
787
788  if ((or_acc & kAsciiMask) != 0) return false;
789
790  DCHECK(CheckFastAsciiConvert(saved_dst, saved_src, length, changed,
791                               Converter::kIsToLower));
792
793  *changed_out = changed;
794  return true;
795}
796
797
798template <class Converter>
799MUST_USE_RESULT static Object* ConvertCase(
800    Handle<String> s, Isolate* isolate,
801    unibrow::Mapping<Converter, 128>* mapping) {
802  s = String::Flatten(s);
803  int length = s->length();
804  // Assume that the string is not empty; we need this assumption later
805  if (length == 0) return *s;
806
807  // Simpler handling of ASCII strings.
808  //
809  // NOTE: This assumes that the upper/lower case of an ASCII
810  // character is also ASCII.  This is currently the case, but it
811  // might break in the future if we implement more context and locale
812  // dependent upper/lower conversions.
813  if (s->IsOneByteRepresentationUnderneath()) {
814    // Same length as input.
815    Handle<SeqOneByteString> result =
816        isolate->factory()->NewRawOneByteString(length).ToHandleChecked();
817    DisallowHeapAllocation no_gc;
818    String::FlatContent flat_content = s->GetFlatContent();
819    DCHECK(flat_content.IsFlat());
820    bool has_changed_character = false;
821    bool is_ascii = FastAsciiConvert<Converter>(
822        reinterpret_cast<char*>(result->GetChars()),
823        reinterpret_cast<const char*>(flat_content.ToOneByteVector().start()),
824        length, &has_changed_character);
825    // If not ASCII, we discard the result and take the 2 byte path.
826    if (is_ascii) return has_changed_character ? *result : *s;
827  }
828
829  Handle<SeqString> result;  // Same length as input.
830  if (s->IsOneByteRepresentation()) {
831    result = isolate->factory()->NewRawOneByteString(length).ToHandleChecked();
832  } else {
833    result = isolate->factory()->NewRawTwoByteString(length).ToHandleChecked();
834  }
835
836  Object* answer = ConvertCaseHelper(isolate, *s, *result, length, mapping);
837  if (answer->IsException(isolate) || answer->IsString()) return answer;
838
839  DCHECK(answer->IsSmi());
840  length = Smi::cast(answer)->value();
841  if (s->IsOneByteRepresentation() && length > 0) {
842    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
843        isolate, result, isolate->factory()->NewRawOneByteString(length));
844  } else {
845    if (length < 0) length = -length;
846    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
847        isolate, result, isolate->factory()->NewRawTwoByteString(length));
848  }
849  return ConvertCaseHelper(isolate, *s, *result, length, mapping);
850}
851
852
853RUNTIME_FUNCTION(Runtime_StringToLowerCase) {
854  HandleScope scope(isolate);
855  DCHECK_EQ(args.length(), 1);
856  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
857  return ConvertCase(s, isolate, isolate->runtime_state()->to_lower_mapping());
858}
859
860
861RUNTIME_FUNCTION(Runtime_StringToUpperCase) {
862  HandleScope scope(isolate);
863  DCHECK_EQ(args.length(), 1);
864  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
865  return ConvertCase(s, isolate, isolate->runtime_state()->to_upper_mapping());
866}
867
868RUNTIME_FUNCTION(Runtime_StringLessThan) {
869  HandleScope handle_scope(isolate);
870  DCHECK_EQ(2, args.length());
871  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
872  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
873  switch (String::Compare(x, y)) {
874    case ComparisonResult::kLessThan:
875      return isolate->heap()->true_value();
876    case ComparisonResult::kEqual:
877    case ComparisonResult::kGreaterThan:
878      return isolate->heap()->false_value();
879    case ComparisonResult::kUndefined:
880      break;
881  }
882  UNREACHABLE();
883  return Smi::kZero;
884}
885
886RUNTIME_FUNCTION(Runtime_StringLessThanOrEqual) {
887  HandleScope handle_scope(isolate);
888  DCHECK_EQ(2, args.length());
889  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
890  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
891  switch (String::Compare(x, y)) {
892    case ComparisonResult::kEqual:
893    case ComparisonResult::kLessThan:
894      return isolate->heap()->true_value();
895    case ComparisonResult::kGreaterThan:
896      return isolate->heap()->false_value();
897    case ComparisonResult::kUndefined:
898      break;
899  }
900  UNREACHABLE();
901  return Smi::kZero;
902}
903
904RUNTIME_FUNCTION(Runtime_StringGreaterThan) {
905  HandleScope handle_scope(isolate);
906  DCHECK_EQ(2, args.length());
907  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
908  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
909  switch (String::Compare(x, y)) {
910    case ComparisonResult::kGreaterThan:
911      return isolate->heap()->true_value();
912    case ComparisonResult::kEqual:
913    case ComparisonResult::kLessThan:
914      return isolate->heap()->false_value();
915    case ComparisonResult::kUndefined:
916      break;
917  }
918  UNREACHABLE();
919  return Smi::kZero;
920}
921
922RUNTIME_FUNCTION(Runtime_StringGreaterThanOrEqual) {
923  HandleScope handle_scope(isolate);
924  DCHECK_EQ(2, args.length());
925  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
926  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
927  switch (String::Compare(x, y)) {
928    case ComparisonResult::kEqual:
929    case ComparisonResult::kGreaterThan:
930      return isolate->heap()->true_value();
931    case ComparisonResult::kLessThan:
932      return isolate->heap()->false_value();
933    case ComparisonResult::kUndefined:
934      break;
935  }
936  UNREACHABLE();
937  return Smi::kZero;
938}
939
940RUNTIME_FUNCTION(Runtime_StringEqual) {
941  HandleScope handle_scope(isolate);
942  DCHECK_EQ(2, args.length());
943  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
944  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
945  return isolate->heap()->ToBoolean(String::Equals(x, y));
946}
947
948RUNTIME_FUNCTION(Runtime_StringNotEqual) {
949  HandleScope handle_scope(isolate);
950  DCHECK_EQ(2, args.length());
951  CONVERT_ARG_HANDLE_CHECKED(String, x, 0);
952  CONVERT_ARG_HANDLE_CHECKED(String, y, 1);
953  return isolate->heap()->ToBoolean(!String::Equals(x, y));
954}
955
956RUNTIME_FUNCTION(Runtime_FlattenString) {
957  HandleScope scope(isolate);
958  DCHECK(args.length() == 1);
959  CONVERT_ARG_HANDLE_CHECKED(String, str, 0);
960  return *String::Flatten(str);
961}
962
963
964RUNTIME_FUNCTION(Runtime_StringCharFromCode) {
965  HandleScope handlescope(isolate);
966  DCHECK_EQ(1, args.length());
967  if (args[0]->IsNumber()) {
968    CONVERT_NUMBER_CHECKED(uint32_t, code, Uint32, args[0]);
969    code &= 0xffff;
970    return *isolate->factory()->LookupSingleCharacterStringFromCode(code);
971  }
972  return isolate->heap()->empty_string();
973}
974
975RUNTIME_FUNCTION(Runtime_ExternalStringGetChar) {
976  SealHandleScope shs(isolate);
977  DCHECK_EQ(2, args.length());
978  CONVERT_ARG_CHECKED(ExternalString, string, 0);
979  CONVERT_INT32_ARG_CHECKED(index, 1);
980  return Smi::FromInt(string->Get(index));
981}
982
983RUNTIME_FUNCTION(Runtime_StringCharCodeAt) {
984  SealHandleScope shs(isolate);
985  DCHECK(args.length() == 2);
986  if (!args[0]->IsString()) return isolate->heap()->undefined_value();
987  if (!args[1]->IsNumber()) return isolate->heap()->undefined_value();
988  if (std::isinf(args.number_at(1))) return isolate->heap()->nan_value();
989  return __RT_impl_Runtime_StringCharCodeAtRT(args, isolate);
990}
991
992}  // namespace internal
993}  // namespace v8
994