conversions.cc 48.3 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/numbers/conversions.h"
6

7
#include <limits.h>
8
#include <stdarg.h>
9

10
#include <cmath>
11

12 13
#include "src/base/numbers/dtoa.h"
#include "src/base/numbers/strtod.h"
14
#include "src/base/platform/wrappers.h"
15
#include "src/bigint/bigint.h"
16
#include "src/common/assert-scope.h"
17
#include "src/handles/handles.h"
18
#include "src/heap/factory.h"
19
#include "src/objects/bigint.h"
20
#include "src/objects/objects-inl.h"
21
#include "src/objects/string-inl.h"
22
#include "src/strings/char-predicates-inl.h"
23
#include "src/utils/allocation.h"
24

25
#if defined(_STLP_VENDOR_CSTD)
26
// STLPort doesn't import fpclassify into the std namespace.
27 28 29
#define FPCLASSIFY_NAMESPACE
#else
#define FPCLASSIFY_NAMESPACE std
30 31
#endif

32 33
namespace v8 {
namespace internal {
34

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
// Helper class for building result strings in a character buffer. The
// purpose of the class is to use safe operations that checks the
// buffer bounds on all operations in debug mode.
// This simple base class does not allow formatted output.
class SimpleStringBuilder {
 public:
  // Create a string builder with a buffer of the given size. The
  // buffer is allocated through NewArray<char> and must be
  // deallocated by the caller of Finalize().
  explicit SimpleStringBuilder(int size) {
    buffer_ = base::Vector<char>::New(size);
    position_ = 0;
  }

  SimpleStringBuilder(char* buffer, int size)
      : buffer_(buffer, size), position_(0) {}

  ~SimpleStringBuilder() {
    if (!is_finalized()) Finalize();
  }

  // Get the current position in the builder.
  int position() const {
    DCHECK(!is_finalized());
    return position_;
  }

  // Add a single character to the builder. It is not allowed to add
  // 0-characters; use the Finalize() method to terminate the string
  // instead.
  void AddCharacter(char c) {
    DCHECK_NE(c, '\0');
    DCHECK(!is_finalized() && position_ < buffer_.length());
    buffer_[position_++] = c;
  }

  // Add an entire string to the builder. Uses strlen() internally to
  // compute the length of the input string.
  void AddString(const char* s) {
    size_t len = strlen(s);
    DCHECK_GE(kMaxInt, len);
    AddSubstring(s, static_cast<int>(len));
  }

  // Add the first 'n' characters of the given 0-terminated string 's' to the
  // builder. The input string must have enough characters.
  void AddSubstring(const char* s, int n) {
    DCHECK(!is_finalized() && position_ + n <= buffer_.length());
    DCHECK_LE(n, strlen(s));
    std::memcpy(&buffer_[position_], s, n * kCharSize);
    position_ += n;
  }

  // Add character padding to the builder. If count is non-positive,
  // nothing is added to the builder.
  void AddPadding(char c, int count) {
    for (int i = 0; i < count; i++) {
      AddCharacter(c);
    }
  }

  // Add the decimal representation of the value.
  void AddDecimalInteger(int value) {
    uint32_t number = static_cast<uint32_t>(value);
    if (value < 0) {
      AddCharacter('-');
      number = static_cast<uint32_t>(-value);
    }
    int digits = 1;
    for (uint32_t factor = 10; digits < 10; digits++, factor *= 10) {
      if (factor > number) break;
    }
    position_ += digits;
    for (int i = 1; i <= digits; i++) {
      buffer_[position_ - i] = '0' + static_cast<char>(number % 10);
      number /= 10;
    }
  }

  // Finalize the string by 0-terminating it and returning the buffer.
  char* Finalize() {
    DCHECK(!is_finalized() && position_ <= buffer_.length());
    // If there is no space for null termination, overwrite last character.
    if (position_ == buffer_.length()) {
      position_--;
      // Print ellipsis.
      for (int i = 3; i > 0 && position_ > i; --i) buffer_[position_ - i] = '.';
    }
    buffer_[position_] = '\0';
    // Make sure nobody managed to add a 0-character to the
    // buffer while building the string.
    DCHECK(strlen(buffer_.begin()) == static_cast<size_t>(position_));
    position_ = -1;
    DCHECK(is_finalized());
    return buffer_.begin();
  }

 protected:
  base::Vector<char> buffer_;
  int position_;

  bool is_finalized() const { return position_ < 0; }

 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
};

142 143 144 145 146
inline double JunkStringValue() {
  return bit_cast<double, uint64_t>(kQuietNaNMask);
}

inline double SignedZero(bool negative) {
147
  return negative ? base::uint64_to_double(base::Double::kSignMask) : 0.0;
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
}

inline bool isDigit(int x, int radix) {
  return (x >= '0' && x <= '9' && x < '0' + radix) ||
         (radix > 10 && x >= 'a' && x < 'a' + radix - 10) ||
         (radix > 10 && x >= 'A' && x < 'A' + radix - 10);
}

inline bool isBinaryDigit(int x) { return x == '0' || x == '1'; }

template <class Iterator, class EndMark>
bool SubStringEquals(Iterator* current, EndMark end, const char* substring) {
  DCHECK(**current == *substring);
  for (substring++; *substring != '\0'; substring++) {
    ++*current;
    if (*current == end || **current != *substring) return false;
  }
  ++*current;
  return true;
}

// Returns true if a nonspace character has been found and false if the
// end was been reached before finding a nonspace character.
template <class Iterator, class EndMark>
172
inline bool AdvanceToNonspace(Iterator* current, EndMark end) {
173
  while (*current != end) {
174
    if (!IsWhiteSpaceOrLineTerminator(**current)) return true;
175 176 177 178 179 180 181
    ++*current;
  }
  return false;
}

// Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end.
template <int radix_log_2, class Iterator, class EndMark>
182
double InternalStringToIntDouble(Iterator current, EndMark end, bool negative,
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
                                 bool allow_trailing_junk) {
  DCHECK(current != end);

  // Skip leading 0s.
  while (*current == '0') {
    ++current;
    if (current == end) return SignedZero(negative);
  }

  int64_t number = 0;
  int exponent = 0;
  const int radix = (1 << radix_log_2);

  int lim_0 = '0' + (radix < 10 ? radix : 10);
  int lim_a = 'a' + (radix - 10);
  int lim_A = 'A' + (radix - 10);

  do {
    int digit;
    if (*current >= '0' && *current < lim_0) {
      digit = static_cast<char>(*current) - '0';
    } else if (*current >= 'a' && *current < lim_a) {
      digit = static_cast<char>(*current) - 'a' + 10;
    } else if (*current >= 'A' && *current < lim_A) {
      digit = static_cast<char>(*current) - 'A' + 10;
    } else {
209
      if (allow_trailing_junk || !AdvanceToNonspace(&current, end)) {
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
        break;
      } else {
        return JunkStringValue();
      }
    }

    number = number * radix + digit;
    int overflow = static_cast<int>(number >> 53);
    if (overflow != 0) {
      // Overflow occurred. Need to determine which direction to round the
      // result.
      int overflow_bits_count = 1;
      while (overflow > 1) {
        overflow_bits_count++;
        overflow >>= 1;
      }

      int dropped_bits_mask = ((1 << overflow_bits_count) - 1);
      int dropped_bits = static_cast<int>(number) & dropped_bits_mask;
      number >>= overflow_bits_count;
      exponent = overflow_bits_count;

      bool zero_tail = true;
      while (true) {
        ++current;
        if (current == end || !isDigit(*current, radix)) break;
        zero_tail = zero_tail && *current == '0';
        exponent += radix_log_2;
      }

240
      if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
        return JunkStringValue();
      }

      int middle_value = (1 << (overflow_bits_count - 1));
      if (dropped_bits > middle_value) {
        number++;  // Rounding up.
      } else if (dropped_bits == middle_value) {
        // Rounding to even to consistency with decimals: half-way case rounds
        // up if significant part is odd and down otherwise.
        if ((number & 1) != 0 || !zero_tail) {
          number++;  // Rounding up.
        }
      }

      // Rounding up may cause overflow.
      if ((number & (static_cast<int64_t>(1) << 53)) != 0) {
        exponent++;
        number >>= 1;
      }
      break;
    }
    ++current;
  } while (current != end);

  DCHECK(number < ((int64_t)1 << 53));
  DCHECK(static_cast<int64_t>(static_cast<double>(number)) == number);

  if (exponent == 0) {
    if (negative) {
      if (number == 0) return -0.0;
      number = -number;
    }
    return static_cast<double>(number);
  }

276
  DCHECK_NE(number, 0);
277 278 279
  return std::ldexp(static_cast<double>(negative ? -number : number), exponent);
}

280 281 282 283 284 285 286 287 288
namespace {

// Subclasses of StringToIntHelper get access to internal state:
enum class State { kRunning, kError, kJunk, kEmpty, kZero, kDone };

enum class Sign { kNegative, kPositive, kNone };

}  // namespace

289
// ES6 18.2.5 parseInt(string, radix) (with NumberParseIntHelper subclass);
290 291
// and BigInt parsing cases from https://tc39.github.io/proposal-bigint/
// (with StringToBigIntHelper subclass).
292
template <typename IsolateT>
293
class StringToIntHelper {
294
 public:
295
  StringToIntHelper(IsolateT* isolate, Handle<String> subject, int radix)
296 297 298
      : isolate_(isolate), subject_(subject), radix_(radix) {
    DCHECK(subject->IsFlat());
  }
299

300
  // Used for the StringToBigInt operation.
301
  StringToIntHelper(IsolateT* isolate, Handle<String> subject)
302 303 304 305
      : isolate_(isolate), subject_(subject) {
    DCHECK(subject->IsFlat());
  }

306 307
  // Used for parsing BigInt literals, where the input is a Zone-allocated
  // buffer of one-byte digits, along with an optional radix prefix.
308
  StringToIntHelper(IsolateT* isolate, const uint8_t* subject, int length)
309
      : isolate_(isolate), raw_one_byte_subject_(subject), length_(length) {}
310
  virtual ~StringToIntHelper() = default;
311

312 313
 protected:
  // Subclasses must implement these:
314 315
  virtual void ParseOneByte(const uint8_t* start) = 0;
  virtual void ParseTwoByte(const base::uc16* start) = 0;
316

317 318 319
  // Subclasses must call this to do all the work.
  void ParseInt();

320 321 322 323 324 325
  // Subclass constructors should call these for configuration before calling
  // ParseInt().
  void set_allow_binary_and_octal_prefixes() {
    allow_binary_and_octal_prefixes_ = true;
  }
  void set_disallow_trailing_junk() { allow_trailing_junk_ = false; }
326
  bool allow_trailing_junk() { return allow_trailing_junk_; }
327

328 329
  bool IsOneByte() const {
    return raw_one_byte_subject_ != nullptr ||
330
           String::IsOneByteRepresentationUnderneath(*subject_);
331 332
  }

333 334
  base::Vector<const uint8_t> GetOneByteVector(
      const DisallowGarbageCollection& no_gc) {
335
    if (raw_one_byte_subject_ != nullptr) {
336
      return base::Vector<const uint8_t>(raw_one_byte_subject_, length_);
337
    }
338
    return subject_->GetFlatContent(no_gc).ToOneByteVector();
339 340
  }

341 342
  base::Vector<const base::uc16> GetTwoByteVector(
      const DisallowGarbageCollection& no_gc) {
343
    return subject_->GetFlatContent(no_gc).ToUC16Vector();
344 345
  }

346
  IsolateT* isolate() { return isolate_; }
347 348 349
  int radix() { return radix_; }
  int cursor() { return cursor_; }
  int length() { return length_; }
350 351
  bool negative() { return sign_ == Sign::kNegative; }
  Sign sign() { return sign_; }
352 353
  State state() { return state_; }
  void set_state(State state) { state_ = state; }
354 355

 private:
356 357 358
  template <class Char>
  void DetectRadixInternal(Char current, int length);

359
  IsolateT* isolate_;
360
  Handle<String> subject_;
361 362
  const uint8_t* raw_one_byte_subject_ = nullptr;
  int radix_ = 0;
363 364
  int cursor_ = 0;
  int length_ = 0;
365
  Sign sign_ = Sign::kNone;
366
  bool leading_zero_ = false;
367 368
  bool allow_binary_and_octal_prefixes_ = false;
  bool allow_trailing_junk_ = true;
369
  State state_ = State::kRunning;
370 371
};

372 373
template <typename IsolateT>
void StringToIntHelper<IsolateT>::ParseInt() {
374 375 376 377 378 379 380 381 382 383 384
  DisallowGarbageCollection no_gc;
  if (IsOneByte()) {
    base::Vector<const uint8_t> vector = GetOneByteVector(no_gc);
    DetectRadixInternal(vector.begin(), vector.length());
    if (state_ != State::kRunning) return;
    ParseOneByte(vector.begin());
  } else {
    base::Vector<const base::uc16> vector = GetTwoByteVector(no_gc);
    DetectRadixInternal(vector.begin(), vector.length());
    if (state_ != State::kRunning) return;
    ParseTwoByte(vector.begin());
385 386 387
  }
}

388
template <typename IsolateT>
389
template <class Char>
390 391
void StringToIntHelper<IsolateT>::DetectRadixInternal(Char current,
                                                      int length) {
392 393 394
  Char start = current;
  length_ = length;
  Char end = start + length;
395

396
  if (!AdvanceToNonspace(&current, end)) {
397
    return set_state(State::kEmpty);
398 399 400 401 402 403
  }

  if (*current == '+') {
    // Ignore leading sign; skip following spaces.
    ++current;
    if (current == end) {
404
      return set_state(State::kJunk);
405
    }
406
    sign_ = Sign::kPositive;
407 408 409
  } else if (*current == '-') {
    ++current;
    if (current == end) {
410
      return set_state(State::kJunk);
411
    }
412
    sign_ = Sign::kNegative;
413 414 415 416 417 418 419
  }

  if (radix_ == 0) {
    // Radix detection.
    radix_ = 10;
    if (*current == '0') {
      ++current;
420
      if (current == end) return set_state(State::kZero);
421 422 423
      if (*current == 'x' || *current == 'X') {
        radix_ = 16;
        ++current;
424
        if (current == end) return set_state(State::kJunk);
425
      } else if (allow_binary_and_octal_prefixes_ &&
426 427 428
                 (*current == 'o' || *current == 'O')) {
        radix_ = 8;
        ++current;
429
        if (current == end) return set_state(State::kJunk);
430
      } else if (allow_binary_and_octal_prefixes_ &&
431 432 433
                 (*current == 'b' || *current == 'B')) {
        radix_ = 2;
        ++current;
434
        if (current == end) return set_state(State::kJunk);
435 436 437 438 439 440 441 442
      } else {
        leading_zero_ = true;
      }
    }
  } else if (radix_ == 16) {
    if (*current == '0') {
      // Allow "0x" prefix.
      ++current;
443
      if (current == end) return set_state(State::kZero);
444 445
      if (*current == 'x' || *current == 'X') {
        ++current;
446
        if (current == end) return set_state(State::kJunk);
447 448 449 450 451 452 453 454 455
      } else {
        leading_zero_ = true;
      }
    }
  }
  // Skip leading zeros.
  while (*current == '0') {
    leading_zero_ = true;
    ++current;
456
    if (current == end) return set_state(State::kZero);
457 458 459
  }

  if (!leading_zero_ && !isDigit(*current, radix_)) {
460
    return set_state(State::kJunk);
461 462 463 464 465
  }

  DCHECK(radix_ >= 2 && radix_ <= 36);
  STATIC_ASSERT(String::kMaxLength <= INT_MAX);
  cursor_ = static_cast<int>(current - start);
466 467
}

468
class NumberParseIntHelper : public StringToIntHelper<Isolate> {
469 470 471 472
 public:
  NumberParseIntHelper(Isolate* isolate, Handle<String> string, int radix)
      : StringToIntHelper(isolate, string, radix) {}

473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
  template <class Char>
  void ParseInternal(Char start) {
    Char current = start + cursor();
    Char end = start + length();

    if (radix() == 10) return HandleBaseTenCase(current, end);
    if (base::bits::IsPowerOfTwo(radix())) {
      result_ = HandlePowerOfTwoCase(current, end);
      set_state(State::kDone);
      return;
    }
    return HandleGenericCase(current, end);
  }
  void ParseOneByte(const uint8_t* start) final { return ParseInternal(start); }
  void ParseTwoByte(const base::uc16* start) final {
    return ParseInternal(start);
  }

491 492 493
  double GetResult() {
    ParseInt();
    switch (state()) {
494 495
      case State::kJunk:
      case State::kEmpty:
496
        return JunkStringValue();
497
      case State::kZero:
498
        return SignedZero(negative());
499
      case State::kDone:
500
        return negative() ? -result_ : result_;
501 502
      case State::kError:
      case State::kRunning:
503 504 505 506
        break;
    }
    UNREACHABLE();
  }
507

508
 private:
509 510
  template <class Char>
  void HandleGenericCase(Char current, Char end);
511 512

  template <class Char>
513
  double HandlePowerOfTwoCase(Char current, Char end) {
514 515 516 517 518
    const bool allow_trailing_junk = true;
    // GetResult() will take care of the sign bit, so ignore it for now.
    const bool negative = false;
    switch (radix()) {
      case 2:
519 520
        return InternalStringToIntDouble<1>(current, end, negative,
                                            allow_trailing_junk);
521
      case 4:
522 523
        return InternalStringToIntDouble<2>(current, end, negative,
                                            allow_trailing_junk);
524
      case 8:
525 526
        return InternalStringToIntDouble<3>(current, end, negative,
                                            allow_trailing_junk);
527 528

      case 16:
529 530
        return InternalStringToIntDouble<4>(current, end, negative,
                                            allow_trailing_junk);
531 532

      case 32:
533 534
        return InternalStringToIntDouble<5>(current, end, negative,
                                            allow_trailing_junk);
535 536 537 538 539 540
      default:
        UNREACHABLE();
    }
  }

  template <class Char>
541
  void HandleBaseTenCase(Char current, Char end) {
542 543 544 545 546 547 548 549 550 551 552
    // Parsing with strtod.
    const int kMaxSignificantDigits = 309;  // Doubles are less than 1.8e308.
    // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero
    // end.
    const int kBufferSize = kMaxSignificantDigits + 2;
    char buffer[kBufferSize];
    int buffer_pos = 0;
    while (*current >= '0' && *current <= '9') {
      if (buffer_pos <= kMaxSignificantDigits) {
        // If the number has more than kMaxSignificantDigits it will be parsed
        // as infinity.
553
        DCHECK_LT(buffer_pos, kBufferSize);
554 555 556 557 558 559 560 561
        buffer[buffer_pos++] = static_cast<char>(*current);
      }
      ++current;
      if (current == end) break;
    }

    SLOW_DCHECK(buffer_pos < kBufferSize);
    buffer[buffer_pos] = '\0';
562
    base::Vector<const char> buffer_vector(buffer, buffer_pos);
563 564
    result_ = Strtod(buffer_vector, 0);
    set_state(State::kDone);
565 566 567 568 569
  }

  double result_ = 0;
};

570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
template <class Char>
void NumberParseIntHelper::HandleGenericCase(Char current, Char end) {
  // The following code causes accumulating rounding error for numbers greater
  // than ~2^56. It's explicitly allowed in the spec: "if R is not 2, 4, 8, 10,
  // 16, or 32, then mathInt may be an implementation-dependent approximation to
  // the mathematical integer value" (15.1.2.2).

  int lim_0 = '0' + (radix() < 10 ? radix() : 10);
  int lim_a = 'a' + (radix() - 10);
  int lim_A = 'A' + (radix() - 10);

  // NOTE: The code for computing the value may seem a bit complex at
  // first glance. It is structured to use 32-bit multiply-and-add
  // loops as long as possible to avoid losing precision.

  bool done = false;
  do {
    // Parse the longest part of the string starting at {current}
    // possible while keeping the multiplier, and thus the part
    // itself, within 32 bits.
    uint32_t part = 0, multiplier = 1;
    while (true) {
      uint32_t d;
      if (*current >= '0' && *current < lim_0) {
        d = *current - '0';
      } else if (*current >= 'a' && *current < lim_a) {
        d = *current - 'a' + 10;
      } else if (*current >= 'A' && *current < lim_A) {
        d = *current - 'A' + 10;
      } else {
        done = true;
        break;
      }

      // Update the value of the part as long as the multiplier fits
      // in 32 bits. When we can't guarantee that the next iteration
      // will not overflow the multiplier, we stop parsing the part
      // by leaving the loop.
      const uint32_t kMaximumMultiplier = 0xFFFFFFFFU / 36;
      uint32_t m = multiplier * static_cast<uint32_t>(radix());
      if (m > kMaximumMultiplier) break;
      part = part * radix() + d;
      multiplier = m;
      DCHECK(multiplier > part);

      ++current;
      if (current == end) {
        done = true;
        break;
      }
    }
    result_ = result_ * multiplier + part;
  } while (!done);

  if (!allow_trailing_junk() && AdvanceToNonspace(&current, end)) {
    return set_state(State::kJunk);
  }
  return set_state(State::kDone);
}

630 631 632 633 634 635
// Converts a string to a double value. Assumes the Iterator supports
// the following operations:
// 1. current == end (other ops are not allowed), current != end.
// 2. *current - gets the current character in the sequence.
// 3. ++current (advances the position).
template <class Iterator, class EndMark>
636 637
double InternalStringToDouble(Iterator current, EndMark end, int flags,
                              double empty_string_val) {
638 639 640 641 642 643 644 645
  // To make sure that iterator dereferencing is valid the following
  // convention is used:
  // 1. Each '++current' statement is followed by check for equality to 'end'.
  // 2. If AdvanceToNonspace returned false then current == end.
  // 3. If 'current' becomes be equal to 'end' the function returns or goes to
  // 'parsing_done'.
  // 4. 'current' is not dereferenced after the 'parsing_done' label.
  // 5. Code before 'parsing_done' may rely on 'current != end'.
646
  if (!AdvanceToNonspace(&current, end)) {
647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662
    return empty_string_val;
  }

  const bool allow_trailing_junk = (flags & ALLOW_TRAILING_JUNK) != 0;

  // Maximum number of significant digits in decimal representation.
  // The longest possible double in decimal representation is
  // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
  // (768 digits). If we parse a number whose first digits are equal to a
  // mean of 2 adjacent doubles (that could have up to 769 digits) the result
  // must be rounded to the bigger one unless the tail consists of zeros, so
  // we don't need to preserve all the digits.
  const int kMaxSignificantDigits = 772;

  // The longest form of simplified number is: "-<significant digits>'.1eXXX\0".
  const int kBufferSize = kMaxSignificantDigits + 10;
663
  char buffer[kBufferSize];
664 665 666 667 668 669 670 671 672
  int buffer_pos = 0;

  // Exponent will be adjusted if insignificant digits of the integer part
  // or insignificant leading zeros of the fractional part are dropped.
  int exponent = 0;
  int significant_digits = 0;
  int insignificant_digits = 0;
  bool nonzero_digit_dropped = false;

673
  enum class Sign { kNone, kNegative, kPositive };
674

675
  Sign sign = Sign::kNone;
676 677 678 679 680

  if (*current == '+') {
    // Ignore leading sign.
    ++current;
    if (current == end) return JunkStringValue();
681
    sign = Sign::kPositive;
682 683 684
  } else if (*current == '-') {
    ++current;
    if (current == end) return JunkStringValue();
685
    sign = Sign::kNegative;
686 687 688 689 690 691 692 693
  }

  static const char kInfinityString[] = "Infinity";
  if (*current == kInfinityString[0]) {
    if (!SubStringEquals(&current, end, kInfinityString)) {
      return JunkStringValue();
    }

694
    if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
695 696 697
      return JunkStringValue();
    }

698
    DCHECK_EQ(buffer_pos, 0);
699
    return (sign == Sign::kNegative) ? -V8_INFINITY : V8_INFINITY;
700 701 702 703 704
  }

  bool leading_zero = false;
  if (*current == '0') {
    ++current;
705
    if (current == end) return SignedZero(sign == Sign::kNegative);
706 707 708 709 710 711

    leading_zero = true;

    // It could be hexadecimal value.
    if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) {
      ++current;
712
      if (current == end || !isDigit(*current, 16) || sign != Sign::kNone) {
713 714 715
        return JunkStringValue();  // "0x".
      }

716
      return InternalStringToIntDouble<4>(current, end, false,
717 718 719 720 721
                                          allow_trailing_junk);

      // It could be an explicit octal value.
    } else if ((flags & ALLOW_OCTAL) && (*current == 'o' || *current == 'O')) {
      ++current;
722
      if (current == end || !isDigit(*current, 8) || sign != Sign::kNone) {
723 724 725
        return JunkStringValue();  // "0o".
      }

726
      return InternalStringToIntDouble<3>(current, end, false,
727 728 729 730 731
                                          allow_trailing_junk);

      // It could be a binary value.
    } else if ((flags & ALLOW_BINARY) && (*current == 'b' || *current == 'B')) {
      ++current;
732
      if (current == end || !isBinaryDigit(*current) || sign != Sign::kNone) {
733 734 735
        return JunkStringValue();  // "0b".
      }

736
      return InternalStringToIntDouble<1>(current, end, false,
737 738 739 740 741 742
                                          allow_trailing_junk);
    }

    // Ignore leading zeros in the integer part.
    while (*current == '0') {
      ++current;
743
      if (current == end) return SignedZero(sign == Sign::kNegative);
744 745 746 747 748 749 750 751
    }
  }

  bool octal = leading_zero && (flags & ALLOW_IMPLICIT_OCTAL) != 0;

  // Copy significant digits of the integer part (if any) to the buffer.
  while (*current >= '0' && *current <= '9') {
    if (significant_digits < kMaxSignificantDigits) {
752
      DCHECK_LT(buffer_pos, kBufferSize);
753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
      buffer[buffer_pos++] = static_cast<char>(*current);
      significant_digits++;
      // Will later check if it's an octal in the buffer.
    } else {
      insignificant_digits++;  // Move the digit into the exponential part.
      nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
    }
    octal = octal && *current < '8';
    ++current;
    if (current == end) goto parsing_done;
  }

  if (significant_digits == 0) {
    octal = false;
  }

  if (*current == '.') {
    if (octal && !allow_trailing_junk) return JunkStringValue();
    if (octal) goto parsing_done;

    ++current;
    if (current == end) {
      if (significant_digits == 0 && !leading_zero) {
        return JunkStringValue();
      } else {
        goto parsing_done;
      }
    }

    if (significant_digits == 0) {
      // octal = false;
      // Integer part consists of 0 or is absent. Significant digits start after
      // leading zeros (if any).
      while (*current == '0') {
        ++current;
788
        if (current == end) return SignedZero(sign == Sign::kNegative);
789 790 791 792 793 794 795 796
        exponent--;  // Move this 0 into the exponent.
      }
    }

    // There is a fractional part.  We don't emit a '.', but adjust the exponent
    // instead.
    while (*current >= '0' && *current <= '9') {
      if (significant_digits < kMaxSignificantDigits) {
797
        DCHECK_LT(buffer_pos, kBufferSize);
798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828
        buffer[buffer_pos++] = static_cast<char>(*current);
        significant_digits++;
        exponent--;
      } else {
        // Ignore insignificant digits in the fractional part.
        nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
      }
      ++current;
      if (current == end) goto parsing_done;
    }
  }

  if (!leading_zero && exponent == 0 && significant_digits == 0) {
    // If leading_zeros is true then the string contains zeros.
    // If exponent < 0 then string was [+-]\.0*...
    // If significant_digits != 0 the string is not equal to 0.
    // Otherwise there are no digits in the string.
    return JunkStringValue();
  }

  // Parse exponential part.
  if (*current == 'e' || *current == 'E') {
    if (octal) return JunkStringValue();
    ++current;
    if (current == end) {
      if (allow_trailing_junk) {
        goto parsing_done;
      } else {
        return JunkStringValue();
      }
    }
829
    char exponent_sign = '+';
830
    if (*current == '+' || *current == '-') {
831
      exponent_sign = static_cast<char>(*current);
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864
      ++current;
      if (current == end) {
        if (allow_trailing_junk) {
          goto parsing_done;
        } else {
          return JunkStringValue();
        }
      }
    }

    if (current == end || *current < '0' || *current > '9') {
      if (allow_trailing_junk) {
        goto parsing_done;
      } else {
        return JunkStringValue();
      }
    }

    const int max_exponent = INT_MAX / 2;
    DCHECK(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
    int num = 0;
    do {
      // Check overflow.
      int digit = *current - '0';
      if (num >= max_exponent / 10 &&
          !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
        num = max_exponent;
      } else {
        num = num * 10 + digit;
      }
      ++current;
    } while (current != end && *current >= '0' && *current <= '9');

865
    exponent += (exponent_sign == '-' ? -num : num);
866 867
  }

868
  if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
869 870 871 872 873 874 875
    return JunkStringValue();
  }

parsing_done:
  exponent += insignificant_digits;

  if (octal) {
876
    return InternalStringToIntDouble<3>(buffer, buffer + buffer_pos,
877 878
                                        sign == Sign::kNegative,
                                        allow_trailing_junk);
879 880 881 882 883 884 885 886 887 888
  }

  if (nonzero_digit_dropped) {
    buffer[buffer_pos++] = '1';
    exponent--;
  }

  SLOW_DCHECK(buffer_pos < kBufferSize);
  buffer[buffer_pos] = '\0';

889 890
  double converted =
      Strtod(base::Vector<const char>(buffer, buffer_pos), exponent);
891
  return (sign == Sign::kNegative) ? -converted : converted;
892 893
}

894
double StringToDouble(const char* str, int flags, double empty_string_val) {
895 896 897 898
  // We use {base::OneByteVector} instead of {base::CStrVector} to avoid
  // instantiating the InternalStringToDouble() template for {const char*} as
  // well.
  return StringToDouble(base::OneByteVector(str), flags, empty_string_val);
899 900
}

901
double StringToDouble(base::Vector<const uint8_t> str, int flags,
902
                      double empty_string_val) {
903 904
  return InternalStringToDouble(str.begin(), str.end(), flags,
                                empty_string_val);
905 906
}

907
double StringToDouble(base::Vector<const base::uc16> str, int flags,
908
                      double empty_string_val) {
909
  const base::uc16* end = str.begin() + str.length();
910
  return InternalStringToDouble(str.begin(), end, flags, empty_string_val);
911 912
}

913 914 915
double StringToInt(Isolate* isolate, Handle<String> string, int radix) {
  NumberParseIntHelper helper(isolate, string, radix);
  return helper.GetResult();
916 917
}

918 919
template <typename IsolateT>
class StringToBigIntHelper : public StringToIntHelper<IsolateT> {
920
 public:
921
  enum class Behavior { kStringToBigInt, kLiteral };
922 923

  // Used for StringToBigInt operation (BigInt constructor and == operator).
924 925
  StringToBigIntHelper(IsolateT* isolate, Handle<String> string)
      : StringToIntHelper<IsolateT>(isolate, string),
926
        behavior_(Behavior::kStringToBigInt) {
927 928
    this->set_allow_binary_and_octal_prefixes();
    this->set_disallow_trailing_junk();
929
  }
930

931 932
  // Used for parsing BigInt literals, where the input is a buffer of
  // one-byte ASCII digits, along with an optional radix prefix.
933 934
  StringToBigIntHelper(IsolateT* isolate, const uint8_t* string, int length)
      : StringToIntHelper<IsolateT>(isolate, string, length),
935
        behavior_(Behavior::kLiteral) {
936
    this->set_allow_binary_and_octal_prefixes();
937
  }
938

939 940 941 942 943
  void ParseOneByte(const uint8_t* start) final { return ParseInternal(start); }
  void ParseTwoByte(const base::uc16* start) final {
    return ParseInternal(start);
  }

944
  MaybeHandle<BigInt> GetResult() {
945 946 947
    this->ParseInt();
    if (behavior_ == Behavior::kStringToBigInt && this->sign() != Sign::kNone &&
        this->radix() != 10) {
948
      return MaybeHandle<BigInt>();
949
    }
950
    if (this->state() == State::kEmpty) {
951
      if (behavior_ == Behavior::kStringToBigInt) {
952
        this->set_state(State::kZero);
953 954 955 956
      } else {
        UNREACHABLE();
      }
    }
957 958 959
    switch (this->state()) {
      case State::kJunk:
      case State::kError:
960
        return MaybeHandle<BigInt>();
961
      case State::kZero:
962
        return BigInt::Zero(this->isolate(), allocation_type());
963
      case State::kDone:
964
        return BigInt::Allocate(this->isolate(), &accumulator_,
965
                                this->negative(), allocation_type());
966 967
      case State::kEmpty:
      case State::kRunning:
968 969 970 971
        break;
    }
    UNREACHABLE();
  }
972

973 974 975
 private:
  template <class Char>
  void ParseInternal(Char start) {
976
    using Result = bigint::FromStringAccumulator::Result;
977 978
    Char current = start + this->cursor();
    Char end = start + this->length();
979
    current = accumulator_.Parse(current, end, this->radix());
980

981 982 983 984
    Result result = accumulator_.result();
    if (result == Result::kMaxSizeExceeded) {
      return this->set_state(State::kError);
    }
985 986 987 988 989
    if (!this->allow_trailing_junk() && AdvanceToNonspace(&current, end)) {
      return this->set_state(State::kJunk);
    }
    return this->set_state(State::kDone);
  }
990

991 992 993 994 995 996 997
  AllocationType allocation_type() {
    // For literals, we pretenure the allocated BigInt, since it's about
    // to be stored in the interpreter's constants array.
    return behavior_ == Behavior::kLiteral ? AllocationType::kOld
                                           : AllocationType::kYoung;
  }

998
  bigint::FromStringAccumulator accumulator_{BigInt::kMaxLength};
999
  Behavior behavior_;
1000 1001
};

1002
MaybeHandle<BigInt> StringToBigInt(Isolate* isolate, Handle<String> string) {
1003
  string = String::Flatten(isolate, string);
1004
  StringToBigIntHelper<Isolate> helper(isolate, string);
1005 1006
  return helper.GetResult();
}
1007

1008 1009 1010
template <typename IsolateT>
MaybeHandle<BigInt> BigIntLiteral(IsolateT* isolate, const char* string) {
  StringToBigIntHelper<IsolateT> helper(
1011 1012
      isolate, reinterpret_cast<const uint8_t*>(string),
      static_cast<int>(strlen(string)));
1013 1014
  return helper.GetResult();
}
1015 1016 1017
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
    MaybeHandle<BigInt> BigIntLiteral(Isolate* isolate, const char* string);
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
1018
    MaybeHandle<BigInt> BigIntLiteral(LocalIsolate* isolate,
1019
                                      const char* string);
1020

1021
const char* DoubleToCString(double v, base::Vector<char> buffer) {
1022
  switch (FPCLASSIFY_NAMESPACE::fpclassify(v)) {
1023 1024 1025 1026 1027 1028
    case FP_NAN:
      return "NaN";
    case FP_INFINITE:
      return (v < 0.0 ? "-Infinity" : "Infinity");
    case FP_ZERO:
      return "0";
1029
    default: {
1030 1031 1032 1033 1034
      if (IsInt32Double(v)) {
        // This will trigger if v is -0 and -0.0 is stringified to "0".
        // (see ES section 7.1.12.1 #sec-tostring-applied-to-the-number-type)
        return IntToCString(FastD2I(v), buffer);
      }
1035
      SimpleStringBuilder builder(buffer.begin(), buffer.length());
1036 1037
      int decimal_point;
      int sign;
1038
      const int kV8DtoaBufferCapacity = base::kBase10MaximalLength + 1;
1039
      char decimal_rep[kV8DtoaBufferCapacity];
1040
      int length;
1041

1042 1043 1044 1045
      base::DoubleToAscii(
          v, base::DTOA_SHORTEST, 0,
          base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity), &sign,
          &length, &decimal_point);
1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076

      if (sign) builder.AddCharacter('-');

      if (length <= decimal_point && decimal_point <= 21) {
        // ECMA-262 section 9.8.1 step 6.
        builder.AddString(decimal_rep);
        builder.AddPadding('0', decimal_point - length);

      } else if (0 < decimal_point && decimal_point <= 21) {
        // ECMA-262 section 9.8.1 step 7.
        builder.AddSubstring(decimal_rep, decimal_point);
        builder.AddCharacter('.');
        builder.AddString(decimal_rep + decimal_point);

      } else if (decimal_point <= 0 && decimal_point > -6) {
        // ECMA-262 section 9.8.1 step 8.
        builder.AddString("0.");
        builder.AddPadding('0', -decimal_point);
        builder.AddString(decimal_rep);

      } else {
        // ECMA-262 section 9.8.1 step 9 and 10 combined.
        builder.AddCharacter(decimal_rep[0]);
        if (length != 1) {
          builder.AddCharacter('.');
          builder.AddString(decimal_rep + 1);
        }
        builder.AddCharacter('e');
        builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
        int exponent = decimal_point - 1;
        if (exponent < 0) exponent = -exponent;
1077
        builder.AddDecimalInteger(exponent);
1078
      }
1079
      return builder.Finalize();
1080 1081 1082 1083
    }
  }
}

1084
const char* IntToCString(int n, base::Vector<char> buffer) {
1085 1086
  bool negative = true;
  if (n >= 0) {
1087
    n = -n;
1088
    negative = false;
1089 1090 1091 1092 1093
  }
  // Build the string backwards from the least significant digit.
  int i = buffer.length();
  buffer[--i] = '\0';
  do {
1094 1095
    // We ensured n <= 0, so the subtraction does the right addition.
    buffer[--i] = '0' - (n % 10);
1096 1097 1098
    n /= 10;
  } while (n);
  if (negative) buffer[--i] = '-';
1099
  return buffer.begin() + i;
1100 1101 1102
}

char* DoubleToFixedCString(double value, int f) {
1103
  const int kMaxDigitsBeforePoint = 21;
1104
  const double kFirstNonFixed = 1e21;
1105 1106
  DCHECK_GE(f, 0);
  DCHECK_LE(f, kMaxFractionDigits);
1107 1108 1109 1110 1111 1112 1113 1114

  bool negative = false;
  double abs_value = value;
  if (value < 0) {
    abs_value = -value;
    negative = true;
  }

1115 1116 1117
  // If abs_value has more than kMaxDigitsBeforePoint digits before the point
  // use the non-fixed conversion routine.
  if (abs_value >= kFirstNonFixed) {
1118
    char arr[kMaxFractionDigits];
1119
    base::Vector<char> buffer(arr, arraysize(arr));
1120 1121 1122 1123 1124 1125
    return StrDup(DoubleToCString(value, buffer));
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
1126
  // Add space for the '\0' byte.
1127
  const int kDecimalRepCapacity =
1128
      kMaxDigitsBeforePoint + kMaxFractionDigits + 1;
1129 1130
  char decimal_rep[kDecimalRepCapacity];
  int decimal_rep_length;
1131 1132 1133
  base::DoubleToAscii(value, base::DTOA_FIXED, f,
                      base::Vector<char>(decimal_rep, kDecimalRepCapacity),
                      &sign, &decimal_rep_length, &decimal_point);
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144

  // Create a representation that is padded with zeros if needed.
  int zero_prefix_length = 0;
  int zero_postfix_length = 0;

  if (decimal_point <= 0) {
    zero_prefix_length = -decimal_point + 1;
    decimal_point = 1;
  }

  if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
1145 1146
    zero_postfix_length =
        decimal_point + f - decimal_rep_length - zero_prefix_length;
1147 1148 1149 1150
  }

  unsigned rep_length =
      zero_prefix_length + decimal_rep_length + zero_postfix_length;
1151
  SimpleStringBuilder rep_builder(rep_length + 1);
1152 1153 1154 1155 1156 1157 1158 1159
  rep_builder.AddPadding('0', zero_prefix_length);
  rep_builder.AddString(decimal_rep);
  rep_builder.AddPadding('0', zero_postfix_length);
  char* rep = rep_builder.Finalize();

  // Create the result string by appending a minus and putting in a
  // decimal point if needed.
  unsigned result_size = decimal_point + f + 2;
1160
  SimpleStringBuilder builder(result_size + 1);
1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
  if (negative) builder.AddCharacter('-');
  builder.AddSubstring(rep, decimal_point);
  if (f > 0) {
    builder.AddCharacter('.');
    builder.AddSubstring(rep + decimal_point, f);
  }
  DeleteArray(rep);
  return builder.Finalize();
}

1171
static char* CreateExponentialRepresentation(char* decimal_rep, int exponent,
1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183
                                             bool negative,
                                             int significant_digits) {
  bool negative_exponent = false;
  if (exponent < 0) {
    negative_exponent = true;
    exponent = -exponent;
  }

  // Leave room in the result for appending a minus, for a period, the
  // letter 'e', a minus or a plus depending on the exponent, and a
  // three digit exponent.
  unsigned result_size = significant_digits + 7;
1184
  SimpleStringBuilder builder(result_size + 1);
1185 1186 1187 1188 1189 1190

  if (negative) builder.AddCharacter('-');
  builder.AddCharacter(decimal_rep[0]);
  if (significant_digits != 1) {
    builder.AddCharacter('.');
    builder.AddString(decimal_rep + 1);
1191 1192 1193
    size_t rep_length = strlen(decimal_rep);
    DCHECK_GE(significant_digits, rep_length);
    builder.AddPadding('0', significant_digits - static_cast<int>(rep_length));
1194 1195 1196 1197
  }

  builder.AddCharacter('e');
  builder.AddCharacter(negative_exponent ? '-' : '+');
1198
  builder.AddDecimalInteger(exponent);
1199 1200 1201 1202 1203
  return builder.Finalize();
}

char* DoubleToExponentialCString(double value, int f) {
  // f might be -1 to signal that f was undefined in JavaScript.
1204
  DCHECK(f >= -1 && f <= kMaxFractionDigits);
1205 1206 1207 1208 1209 1210 1211 1212 1213 1214

  bool negative = false;
  if (value < 0) {
    value = -value;
    negative = true;
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
1215 1216 1217
  // f corresponds to the digits after the point. There is always one digit
  // before the point. The number of requested_digits equals hence f + 1.
  // And we have to add one character for the null-terminator.
1218
  const int kV8DtoaBufferCapacity = kMaxFractionDigits + 1 + 1;
1219 1220
  // Make sure that the buffer is big enough, even if we fall back to the
  // shortest representation (which happens when f equals -1).
1221
  DCHECK_LE(base::kBase10MaximalLength, kMaxFractionDigits + 1);
1222
  char decimal_rep[kV8DtoaBufferCapacity];
1223 1224
  int decimal_rep_length;

1225
  if (f == -1) {
1226 1227 1228
    base::DoubleToAscii(value, base::DTOA_SHORTEST, 0,
                        base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                        &sign, &decimal_rep_length, &decimal_point);
1229
    f = decimal_rep_length - 1;
1230
  } else {
1231 1232 1233
    base::DoubleToAscii(value, base::DTOA_PRECISION, f + 1,
                        base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                        &sign, &decimal_rep_length, &decimal_point);
1234
  }
1235
  DCHECK_GT(decimal_rep_length, 0);
1236
  DCHECK(decimal_rep_length <= f + 1);
1237 1238 1239

  int exponent = decimal_point - 1;
  char* result =
1240
      CreateExponentialRepresentation(decimal_rep, exponent, negative, f + 1);
1241 1242 1243 1244 1245

  return result;
}

char* DoubleToPrecisionCString(double value, int p) {
1246
  const int kMinimalDigits = 1;
1247
  DCHECK(p >= kMinimalDigits && p <= kMaxFractionDigits);
1248
  USE(kMinimalDigits);
1249 1250 1251 1252 1253 1254 1255 1256 1257 1258

  bool negative = false;
  if (value < 0) {
    value = -value;
    negative = true;
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
1259
  // Add one for the terminating null character.
1260
  const int kV8DtoaBufferCapacity = kMaxFractionDigits + 1;
1261
  char decimal_rep[kV8DtoaBufferCapacity];
1262 1263
  int decimal_rep_length;

1264 1265 1266
  base::DoubleToAscii(value, base::DTOA_PRECISION, p,
                      base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                      &sign, &decimal_rep_length, &decimal_point);
1267
  DCHECK(decimal_rep_length <= p);
1268 1269 1270

  int exponent = decimal_point - 1;

1271
  char* result = nullptr;
1272 1273 1274 1275 1276 1277 1278 1279 1280 1281

  if (exponent < -6 || exponent >= p) {
    result =
        CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
  } else {
    // Use fixed notation.
    //
    // Leave room in the result for appending a minus, a period and in
    // the case where decimal_point is not positive for a zero in
    // front of the period.
1282 1283
    unsigned result_size =
        (decimal_point <= 0) ? -decimal_point + p + 3 : p + 2;
1284
    SimpleStringBuilder builder(result_size + 1);
1285 1286 1287 1288 1289 1290 1291
    if (negative) builder.AddCharacter('-');
    if (decimal_point <= 0) {
      builder.AddString("0.");
      builder.AddPadding('0', -decimal_point);
      builder.AddString(decimal_rep);
      builder.AddPadding('0', p - decimal_rep_length);
    } else {
1292
      const int m = std::min(decimal_rep_length, decimal_point);
1293 1294 1295 1296 1297 1298
      builder.AddSubstring(decimal_rep, m);
      builder.AddPadding('0', decimal_point - decimal_rep_length);
      if (decimal_point < p) {
        builder.AddCharacter('.');
        const int extra = negative ? 2 : 1;
        if (decimal_rep_length > decimal_point) {
1299 1300 1301
          const size_t len = strlen(decimal_rep + decimal_point);
          DCHECK_GE(kMaxInt, len);
          const int n =
1302
              std::min(static_cast<int>(len), p - (builder.position() - extra));
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314
          builder.AddSubstring(decimal_rep + decimal_point, n);
        }
        builder.AddPadding('0', extra + (p - builder.position()));
      }
    }
    result = builder.Finalize();
  }

  return result;
}

char* DoubleToRadixCString(double value, int radix) {
1315
  DCHECK(radix >= 2 && radix <= 36);
1316 1317
  DCHECK(std::isfinite(value));
  DCHECK_NE(0.0, value);
1318 1319 1320
  // Character array used for conversion.
  static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";

1321 1322
  // Temporary buffer for the result. We start with the decimal point in the
  // middle and write to the left for the integer part and to the right for the
1323 1324 1325 1326
  // fractional part. 1024 characters for the exponent and 52 for the mantissa
  // either way, with additional space for sign, decimal point and string
  // termination should be sufficient.
  static const int kBufferSize = 2200;
1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337
  char buffer[kBufferSize];
  int integer_cursor = kBufferSize / 2;
  int fraction_cursor = integer_cursor;

  bool negative = value < 0;
  if (negative) value = -value;

  // Split the value into an integer part and a fractional part.
  double integer = std::floor(value);
  double fraction = value - integer;
  // We only compute fractional digits up to the input double's precision.
1338 1339
  double delta = 0.5 * (base::Double(value).NextDouble() - value);
  delta = std::max(base::Double(0.0).NextDouble(), delta);
1340
  DCHECK_GT(delta, 0.0);
1341
  if (fraction >= delta) {
1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366
    // Insert decimal point.
    buffer[fraction_cursor++] = '.';
    do {
      // Shift up by one digit.
      fraction *= radix;
      delta *= radix;
      // Write digit.
      int digit = static_cast<int>(fraction);
      buffer[fraction_cursor++] = chars[digit];
      // Calculate remainder.
      fraction -= digit;
      // Round to even.
      if (fraction > 0.5 || (fraction == 0.5 && (digit & 1))) {
        if (fraction + delta > 1) {
          // We need to back trace already written digits in case of carry-over.
          while (true) {
            fraction_cursor--;
            if (fraction_cursor == kBufferSize / 2) {
              CHECK_EQ('.', buffer[fraction_cursor]);
              // Carry over to the integer part.
              integer += 1;
              break;
            }
            char c = buffer[fraction_cursor];
            // Reconstruct digit.
1367
            digit = c > '9' ? (c - 'a' + 10) : (c - '0');
1368 1369 1370 1371 1372 1373 1374 1375
            if (digit + 1 < radix) {
              buffer[fraction_cursor++] = chars[digit + 1];
              break;
            }
          }
          break;
        }
      }
1376
    } while (fraction >= delta);
1377
  }
1378

1379
  // Compute integer digits. Fill unrepresented digits with zero.
1380
  while (base::Double(integer / radix).Exponent() > 0) {
1381 1382 1383
    integer /= radix;
    buffer[--integer_cursor] = '0';
  }
1384
  do {
1385
    double remainder = Modulo(integer, radix);
1386 1387
    buffer[--integer_cursor] = chars[static_cast<int>(remainder)];
    integer = (integer - remainder) / radix;
1388 1389 1390 1391 1392
  } while (integer > 0);

  // Add sign and terminate string.
  if (negative) buffer[--integer_cursor] = '-';
  buffer[fraction_cursor++] = '\0';
1393 1394
  DCHECK_LT(fraction_cursor, kBufferSize);
  DCHECK_LE(0, integer_cursor);
1395 1396
  // Allocate new string as return value.
  char* result = NewArray<char>(fraction_cursor - integer_cursor);
1397
  memcpy(result, buffer + integer_cursor, fraction_cursor - integer_cursor);
1398
  return result;
1399 1400
}

1401
// ES6 18.2.4 parseFloat(string)
1402
double StringToDouble(Isolate* isolate, Handle<String> string, int flags,
1403 1404
                      double empty_string_val) {
  Handle<String> flattened = String::Flatten(isolate, string);
1405
  {
1406
    DisallowGarbageCollection no_gc;
1407
    String::FlatContent flat = flattened->GetFlatContent(no_gc);
1408 1409
    DCHECK(flat.IsFlat());
    if (flat.IsOneByte()) {
1410
      return StringToDouble(flat.ToOneByteVector(), flags, empty_string_val);
1411
    } else {
1412
      return StringToDouble(flat.ToUC16Vector(), flags, empty_string_val);
1413
    }
1414 1415 1416
  }
}

1417 1418
base::Optional<double> TryStringToDouble(LocalIsolate* isolate,
                                         Handle<String> object,
1419 1420 1421 1422 1423 1424 1425 1426
                                         int max_length_for_conversion) {
  DisallowGarbageCollection no_gc;
  int length = object->length();
  if (length > max_length_for_conversion) {
    return base::nullopt;
  }

  const int flags = ALLOW_HEX | ALLOW_OCTAL | ALLOW_BINARY;
1427
  auto buffer = std::make_unique<base::uc16[]>(max_length_for_conversion);
1428
  SharedStringAccessGuardIfNeeded access_guard(isolate);
1429
  String::WriteToFlat(*object, buffer.get(), 0, length, isolate, access_guard);
1430
  base::Vector<const base::uc16> v(buffer.get(), length);
1431 1432 1433
  return StringToDouble(v, flags);
}

1434
bool IsSpecialIndex(String string) {
dcarney's avatar
dcarney committed
1435 1436
  // Max length of canonical double: -X.XXXXXXXXXXXXXXXXX-eXXX
  const int kBufferSize = 24;
1437
  const int length = string.length();
dcarney's avatar
dcarney committed
1438
  if (length == 0 || length > kBufferSize) return false;
1439
  uint16_t buffer[kBufferSize];
dcarney's avatar
dcarney committed
1440 1441 1442
  String::WriteToFlat(string, buffer, 0, length);
  // If the first char is not a digit or a '-' or we can't match 'NaN' or
  // '(-)Infinity', bailout immediately.
1443
  int offset = 0;
dcarney's avatar
dcarney committed
1444 1445 1446 1447 1448 1449 1450 1451 1452
  if (!IsDecimalDigit(buffer[0])) {
    if (buffer[0] == '-') {
      if (length == 1) return false;  // Just '-' is bad.
      if (!IsDecimalDigit(buffer[1])) {
        if (buffer[1] == 'I' && length == 9) {
          // Allow matching of '-Infinity' below.
        } else {
          return false;
        }
1453
      }
dcarney's avatar
dcarney committed
1454 1455 1456 1457 1458 1459 1460 1461
      offset++;
    } else if (buffer[0] == 'I' && length == 8) {
      // Allow matching of 'Infinity' below.
    } else if (buffer[0] == 'N' && length == 3) {
      // Match NaN.
      return buffer[1] == 'a' && buffer[2] == 'N';
    } else {
      return false;
1462 1463
    }
  }
dcarney's avatar
dcarney committed
1464 1465 1466 1467 1468 1469 1470
  // Expected fast path: key is an integer.
  static const int kRepresentableIntegerLength = 15;  // (-)XXXXXXXXXXXXXXX
  if (length - offset <= kRepresentableIntegerLength) {
    const int initial_offset = offset;
    bool matches = true;
    for (; offset < length; offset++) {
      matches &= IsDecimalDigit(buffer[offset]);
1471
    }
dcarney's avatar
dcarney committed
1472 1473 1474 1475 1476 1477 1478
    if (matches) {
      // Match 0 and -0.
      if (buffer[initial_offset] == '0') return initial_offset == length - 1;
      return true;
    }
  }
  // Slow path: test DoubleToString(StringToDouble(string)) == string.
1479
  base::Vector<const uint16_t> vector(buffer, length);
1480
  double d = StringToDouble(vector, NO_CONVERSION_FLAGS);
dcarney's avatar
dcarney committed
1481 1482 1483
  if (std::isnan(d)) return false;
  // Compute reverse string.
  char reverse_buffer[kBufferSize + 1];  // Result will be /0 terminated.
1484
  base::Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer));
dcarney's avatar
dcarney committed
1485 1486 1487
  const char* reverse_string = DoubleToCString(d, reverse_vector);
  for (int i = 0; i < length; ++i) {
    if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false;
1488 1489 1490
  }
  return true;
}
1491 1492
}  // namespace internal
}  // namespace v8
1493 1494

#undef FPCLASSIFY_NAMESPACE