• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2011 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/numbers/conversions.h"
6 
7 #include <limits.h>
8 #include <stdarg.h>
9 
10 #include <cmath>
11 
12 #include "src/base/numbers/dtoa.h"
13 #include "src/base/numbers/strtod.h"
14 #include "src/base/platform/wrappers.h"
15 #include "src/base/small-vector.h"
16 #include "src/bigint/bigint.h"
17 #include "src/common/assert-scope.h"
18 #include "src/handles/handles.h"
19 #include "src/heap/factory.h"
20 #include "src/objects/bigint.h"
21 #include "src/objects/objects-inl.h"
22 #include "src/objects/string-inl.h"
23 #include "src/strings/char-predicates-inl.h"
24 #include "src/utils/allocation.h"
25 
26 #if defined(_STLP_VENDOR_CSTD)
27 // STLPort doesn't import fpclassify into the std namespace.
28 #define FPCLASSIFY_NAMESPACE
29 #else
30 #define FPCLASSIFY_NAMESPACE std
31 #endif
32 
33 namespace v8 {
34 namespace internal {
35 
36 // Helper class for building result strings in a character buffer. The
37 // purpose of the class is to use safe operations that checks the
38 // buffer bounds on all operations in debug mode.
39 // This simple base class does not allow formatted output.
40 class SimpleStringBuilder {
41  public:
42   // Create a string builder with a buffer of the given size. The
43   // buffer is allocated through NewArray<char> and must be
44   // deallocated by the caller of Finalize().
SimpleStringBuilder(int size)45   explicit SimpleStringBuilder(int size) {
46     buffer_ = base::Vector<char>::New(size);
47     position_ = 0;
48   }
49 
SimpleStringBuilder(char * buffer,int size)50   SimpleStringBuilder(char* buffer, int size)
51       : buffer_(buffer, size), position_(0) {}
52 
~SimpleStringBuilder()53   ~SimpleStringBuilder() {
54     if (!is_finalized()) Finalize();
55   }
56 
57   // Get the current position in the builder.
position() const58   int position() const {
59     DCHECK(!is_finalized());
60     return position_;
61   }
62 
63   // Add a single character to the builder. It is not allowed to add
64   // 0-characters; use the Finalize() method to terminate the string
65   // instead.
AddCharacter(char c)66   void AddCharacter(char c) {
67     DCHECK_NE(c, '\0');
68     DCHECK(!is_finalized() && position_ < buffer_.length());
69     buffer_[position_++] = c;
70   }
71 
72   // Add an entire string to the builder. Uses strlen() internally to
73   // compute the length of the input string.
AddString(const char * s)74   void AddString(const char* s) {
75     size_t len = strlen(s);
76     DCHECK_GE(kMaxInt, len);
77     AddSubstring(s, static_cast<int>(len));
78   }
79 
80   // Add the first 'n' characters of the given 0-terminated string 's' to the
81   // builder. The input string must have enough characters.
AddSubstring(const char * s,int n)82   void AddSubstring(const char* s, int n) {
83     DCHECK(!is_finalized() && position_ + n <= buffer_.length());
84     DCHECK_LE(n, strlen(s));
85     std::memcpy(&buffer_[position_], s, n * kCharSize);
86     position_ += n;
87   }
88 
89   // Add character padding to the builder. If count is non-positive,
90   // nothing is added to the builder.
AddPadding(char c,int count)91   void AddPadding(char c, int count) {
92     for (int i = 0; i < count; i++) {
93       AddCharacter(c);
94     }
95   }
96 
97   // Add the decimal representation of the value.
AddDecimalInteger(int value)98   void AddDecimalInteger(int value) {
99     uint32_t number = static_cast<uint32_t>(value);
100     if (value < 0) {
101       AddCharacter('-');
102       number = static_cast<uint32_t>(-value);
103     }
104     int digits = 1;
105     for (uint32_t factor = 10; digits < 10; digits++, factor *= 10) {
106       if (factor > number) break;
107     }
108     position_ += digits;
109     for (int i = 1; i <= digits; i++) {
110       buffer_[position_ - i] = '0' + static_cast<char>(number % 10);
111       number /= 10;
112     }
113   }
114 
115   // Finalize the string by 0-terminating it and returning the buffer.
Finalize()116   char* Finalize() {
117     DCHECK(!is_finalized() && position_ <= buffer_.length());
118     // If there is no space for null termination, overwrite last character.
119     if (position_ == buffer_.length()) {
120       position_--;
121       // Print ellipsis.
122       for (int i = 3; i > 0 && position_ > i; --i) buffer_[position_ - i] = '.';
123     }
124     buffer_[position_] = '\0';
125     // Make sure nobody managed to add a 0-character to the
126     // buffer while building the string.
127     DCHECK(strlen(buffer_.begin()) == static_cast<size_t>(position_));
128     position_ = -1;
129     DCHECK(is_finalized());
130     return buffer_.begin();
131   }
132 
133  protected:
134   base::Vector<char> buffer_;
135   int position_;
136 
is_finalized() const137   bool is_finalized() const { return position_ < 0; }
138 
139  private:
140   DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
141 };
142 
JunkStringValue()143 inline double JunkStringValue() {
144   return bit_cast<double, uint64_t>(kQuietNaNMask);
145 }
146 
SignedZero(bool negative)147 inline double SignedZero(bool negative) {
148   return negative ? base::uint64_to_double(base::Double::kSignMask) : 0.0;
149 }
150 
isDigit(int x,int radix)151 inline bool isDigit(int x, int radix) {
152   return (x >= '0' && x <= '9' && x < '0' + radix) ||
153          (radix > 10 && x >= 'a' && x < 'a' + radix - 10) ||
154          (radix > 10 && x >= 'A' && x < 'A' + radix - 10);
155 }
156 
isBinaryDigit(int x)157 inline bool isBinaryDigit(int x) { return x == '0' || x == '1'; }
158 
159 template <class Iterator, class EndMark>
SubStringEquals(Iterator * current,EndMark end,const char * substring)160 bool SubStringEquals(Iterator* current, EndMark end, const char* substring) {
161   DCHECK(**current == *substring);
162   for (substring++; *substring != '\0'; substring++) {
163     ++*current;
164     if (*current == end || **current != *substring) return false;
165   }
166   ++*current;
167   return true;
168 }
169 
170 // Returns true if a nonspace character has been found and false if the
171 // end was been reached before finding a nonspace character.
172 template <class Iterator, class EndMark>
AdvanceToNonspace(Iterator * current,EndMark end)173 inline bool AdvanceToNonspace(Iterator* current, EndMark end) {
174   while (*current != end) {
175     if (!IsWhiteSpaceOrLineTerminator(**current)) return true;
176     ++*current;
177   }
178   return false;
179 }
180 
181 // Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end.
182 template <int radix_log_2, class Iterator, class EndMark>
InternalStringToIntDouble(Iterator current,EndMark end,bool negative,bool allow_trailing_junk)183 double InternalStringToIntDouble(Iterator current, EndMark end, bool negative,
184                                  bool allow_trailing_junk) {
185   DCHECK(current != end);
186 
187   // Skip leading 0s.
188   while (*current == '0') {
189     ++current;
190     if (current == end) return SignedZero(negative);
191   }
192 
193   int64_t number = 0;
194   int exponent = 0;
195   const int radix = (1 << radix_log_2);
196 
197   int lim_0 = '0' + (radix < 10 ? radix : 10);
198   int lim_a = 'a' + (radix - 10);
199   int lim_A = 'A' + (radix - 10);
200 
201   do {
202     int digit;
203     if (*current >= '0' && *current < lim_0) {
204       digit = static_cast<char>(*current) - '0';
205     } else if (*current >= 'a' && *current < lim_a) {
206       digit = static_cast<char>(*current) - 'a' + 10;
207     } else if (*current >= 'A' && *current < lim_A) {
208       digit = static_cast<char>(*current) - 'A' + 10;
209     } else {
210       if (allow_trailing_junk || !AdvanceToNonspace(&current, end)) {
211         break;
212       } else {
213         return JunkStringValue();
214       }
215     }
216 
217     number = number * radix + digit;
218     int overflow = static_cast<int>(number >> 53);
219     if (overflow != 0) {
220       // Overflow occurred. Need to determine which direction to round the
221       // result.
222       int overflow_bits_count = 1;
223       while (overflow > 1) {
224         overflow_bits_count++;
225         overflow >>= 1;
226       }
227 
228       int dropped_bits_mask = ((1 << overflow_bits_count) - 1);
229       int dropped_bits = static_cast<int>(number) & dropped_bits_mask;
230       number >>= overflow_bits_count;
231       exponent = overflow_bits_count;
232 
233       bool zero_tail = true;
234       while (true) {
235         ++current;
236         if (current == end || !isDigit(*current, radix)) break;
237         zero_tail = zero_tail && *current == '0';
238         exponent += radix_log_2;
239       }
240 
241       if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
242         return JunkStringValue();
243       }
244 
245       int middle_value = (1 << (overflow_bits_count - 1));
246       if (dropped_bits > middle_value) {
247         number++;  // Rounding up.
248       } else if (dropped_bits == middle_value) {
249         // Rounding to even to consistency with decimals: half-way case rounds
250         // up if significant part is odd and down otherwise.
251         if ((number & 1) != 0 || !zero_tail) {
252           number++;  // Rounding up.
253         }
254       }
255 
256       // Rounding up may cause overflow.
257       if ((number & (static_cast<int64_t>(1) << 53)) != 0) {
258         exponent++;
259         number >>= 1;
260       }
261       break;
262     }
263     ++current;
264   } while (current != end);
265 
266   DCHECK(number < ((int64_t)1 << 53));
267   DCHECK(static_cast<int64_t>(static_cast<double>(number)) == number);
268 
269   if (exponent == 0) {
270     if (negative) {
271       if (number == 0) return -0.0;
272       number = -number;
273     }
274     return static_cast<double>(number);
275   }
276 
277   DCHECK_NE(number, 0);
278   return std::ldexp(static_cast<double>(negative ? -number : number), exponent);
279 }
280 
281 namespace {
282 
283 // Subclasses of StringToIntHelper get access to internal state:
284 enum class State { kRunning, kError, kJunk, kEmpty, kZero, kDone };
285 
286 enum class Sign { kNegative, kPositive, kNone };
287 
288 }  // namespace
289 
290 // ES6 18.2.5 parseInt(string, radix) (with NumberParseIntHelper subclass);
291 // and BigInt parsing cases from https://tc39.github.io/proposal-bigint/
292 // (with StringToBigIntHelper subclass).
293 template <typename IsolateT>
294 class StringToIntHelper {
295  public:
StringToIntHelper(IsolateT * isolate,Handle<String> subject,int radix)296   StringToIntHelper(IsolateT* isolate, Handle<String> subject, int radix)
297       : isolate_(isolate), subject_(subject), radix_(radix) {
298     DCHECK(subject->IsFlat());
299   }
300 
301   // Used for the StringToBigInt operation.
StringToIntHelper(IsolateT * isolate,Handle<String> subject)302   StringToIntHelper(IsolateT* isolate, Handle<String> subject)
303       : isolate_(isolate), subject_(subject) {
304     DCHECK(subject->IsFlat());
305   }
306 
307   // Used for parsing BigInt literals, where the input is a Zone-allocated
308   // buffer of one-byte digits, along with an optional radix prefix.
StringToIntHelper(IsolateT * isolate,const uint8_t * subject,int length)309   StringToIntHelper(IsolateT* isolate, const uint8_t* subject, int length)
310       : isolate_(isolate), raw_one_byte_subject_(subject), length_(length) {}
311   virtual ~StringToIntHelper() = default;
312 
313  protected:
314   // Subclasses must implement these:
315   virtual void ParseOneByte(const uint8_t* start) = 0;
316   virtual void ParseTwoByte(const base::uc16* start) = 0;
317 
318   // Subclasses must call this to do all the work.
319   void ParseInt();
320 
321   // Subclass constructors should call these for configuration before calling
322   // ParseInt().
set_allow_binary_and_octal_prefixes()323   void set_allow_binary_and_octal_prefixes() {
324     allow_binary_and_octal_prefixes_ = true;
325   }
set_disallow_trailing_junk()326   void set_disallow_trailing_junk() { allow_trailing_junk_ = false; }
allow_trailing_junk()327   bool allow_trailing_junk() { return allow_trailing_junk_; }
328 
IsOneByte() const329   bool IsOneByte() const {
330     return raw_one_byte_subject_ != nullptr ||
331            String::IsOneByteRepresentationUnderneath(*subject_);
332   }
333 
GetOneByteVector(const DisallowGarbageCollection & no_gc)334   base::Vector<const uint8_t> GetOneByteVector(
335       const DisallowGarbageCollection& no_gc) {
336     if (raw_one_byte_subject_ != nullptr) {
337       return base::Vector<const uint8_t>(raw_one_byte_subject_, length_);
338     }
339     return subject_->GetFlatContent(no_gc).ToOneByteVector();
340   }
341 
GetTwoByteVector(const DisallowGarbageCollection & no_gc)342   base::Vector<const base::uc16> GetTwoByteVector(
343       const DisallowGarbageCollection& no_gc) {
344     return subject_->GetFlatContent(no_gc).ToUC16Vector();
345   }
346 
isolate()347   IsolateT* isolate() { return isolate_; }
radix()348   int radix() { return radix_; }
cursor()349   int cursor() { return cursor_; }
length()350   int length() { return length_; }
negative()351   bool negative() { return sign_ == Sign::kNegative; }
sign()352   Sign sign() { return sign_; }
state()353   State state() { return state_; }
set_state(State state)354   void set_state(State state) { state_ = state; }
355 
356  private:
357   template <class Char>
358   void DetectRadixInternal(Char current, int length);
359 
360   IsolateT* isolate_;
361   Handle<String> subject_;
362   const uint8_t* raw_one_byte_subject_ = nullptr;
363   int radix_ = 0;
364   int cursor_ = 0;
365   int length_ = 0;
366   Sign sign_ = Sign::kNone;
367   bool leading_zero_ = false;
368   bool allow_binary_and_octal_prefixes_ = false;
369   bool allow_trailing_junk_ = true;
370   State state_ = State::kRunning;
371 };
372 
373 template <typename IsolateT>
ParseInt()374 void StringToIntHelper<IsolateT>::ParseInt() {
375   DisallowGarbageCollection no_gc;
376   if (IsOneByte()) {
377     base::Vector<const uint8_t> vector = GetOneByteVector(no_gc);
378     DetectRadixInternal(vector.begin(), vector.length());
379     if (state_ != State::kRunning) return;
380     ParseOneByte(vector.begin());
381   } else {
382     base::Vector<const base::uc16> vector = GetTwoByteVector(no_gc);
383     DetectRadixInternal(vector.begin(), vector.length());
384     if (state_ != State::kRunning) return;
385     ParseTwoByte(vector.begin());
386   }
387 }
388 
389 template <typename IsolateT>
390 template <class Char>
DetectRadixInternal(Char current,int length)391 void StringToIntHelper<IsolateT>::DetectRadixInternal(Char current,
392                                                       int length) {
393   Char start = current;
394   length_ = length;
395   Char end = start + length;
396 
397   if (!AdvanceToNonspace(&current, end)) {
398     return set_state(State::kEmpty);
399   }
400 
401   if (*current == '+') {
402     // Ignore leading sign; skip following spaces.
403     ++current;
404     if (current == end) {
405       return set_state(State::kJunk);
406     }
407     sign_ = Sign::kPositive;
408   } else if (*current == '-') {
409     ++current;
410     if (current == end) {
411       return set_state(State::kJunk);
412     }
413     sign_ = Sign::kNegative;
414   }
415 
416   if (radix_ == 0) {
417     // Radix detection.
418     radix_ = 10;
419     if (*current == '0') {
420       ++current;
421       if (current == end) return set_state(State::kZero);
422       if (*current == 'x' || *current == 'X') {
423         radix_ = 16;
424         ++current;
425         if (current == end) return set_state(State::kJunk);
426       } else if (allow_binary_and_octal_prefixes_ &&
427                  (*current == 'o' || *current == 'O')) {
428         radix_ = 8;
429         ++current;
430         if (current == end) return set_state(State::kJunk);
431       } else if (allow_binary_and_octal_prefixes_ &&
432                  (*current == 'b' || *current == 'B')) {
433         radix_ = 2;
434         ++current;
435         if (current == end) return set_state(State::kJunk);
436       } else {
437         leading_zero_ = true;
438       }
439     }
440   } else if (radix_ == 16) {
441     if (*current == '0') {
442       // Allow "0x" prefix.
443       ++current;
444       if (current == end) return set_state(State::kZero);
445       if (*current == 'x' || *current == 'X') {
446         ++current;
447         if (current == end) return set_state(State::kJunk);
448       } else {
449         leading_zero_ = true;
450       }
451     }
452   }
453   // Skip leading zeros.
454   while (*current == '0') {
455     leading_zero_ = true;
456     ++current;
457     if (current == end) return set_state(State::kZero);
458   }
459 
460   if (!leading_zero_ && !isDigit(*current, radix_)) {
461     return set_state(State::kJunk);
462   }
463 
464   DCHECK(radix_ >= 2 && radix_ <= 36);
465   STATIC_ASSERT(String::kMaxLength <= INT_MAX);
466   cursor_ = static_cast<int>(current - start);
467 }
468 
469 class NumberParseIntHelper : public StringToIntHelper<Isolate> {
470  public:
NumberParseIntHelper(Isolate * isolate,Handle<String> string,int radix)471   NumberParseIntHelper(Isolate* isolate, Handle<String> string, int radix)
472       : StringToIntHelper(isolate, string, radix) {}
473 
474   template <class Char>
ParseInternal(Char start)475   void ParseInternal(Char start) {
476     Char current = start + cursor();
477     Char end = start + length();
478 
479     if (radix() == 10) return HandleBaseTenCase(current, end);
480     if (base::bits::IsPowerOfTwo(radix())) {
481       result_ = HandlePowerOfTwoCase(current, end);
482       set_state(State::kDone);
483       return;
484     }
485     return HandleGenericCase(current, end);
486   }
ParseOneByte(const uint8_t * start)487   void ParseOneByte(const uint8_t* start) final { return ParseInternal(start); }
ParseTwoByte(const base::uc16 * start)488   void ParseTwoByte(const base::uc16* start) final {
489     return ParseInternal(start);
490   }
491 
GetResult()492   double GetResult() {
493     ParseInt();
494     switch (state()) {
495       case State::kJunk:
496       case State::kEmpty:
497         return JunkStringValue();
498       case State::kZero:
499         return SignedZero(negative());
500       case State::kDone:
501         return negative() ? -result_ : result_;
502       case State::kError:
503       case State::kRunning:
504         break;
505     }
506     UNREACHABLE();
507   }
508 
509  private:
510   template <class Char>
511   void HandleGenericCase(Char current, Char end);
512 
513   template <class Char>
HandlePowerOfTwoCase(Char current,Char end)514   double HandlePowerOfTwoCase(Char current, Char end) {
515     const bool allow_trailing_junk = true;
516     // GetResult() will take care of the sign bit, so ignore it for now.
517     const bool negative = false;
518     switch (radix()) {
519       case 2:
520         return InternalStringToIntDouble<1>(current, end, negative,
521                                             allow_trailing_junk);
522       case 4:
523         return InternalStringToIntDouble<2>(current, end, negative,
524                                             allow_trailing_junk);
525       case 8:
526         return InternalStringToIntDouble<3>(current, end, negative,
527                                             allow_trailing_junk);
528 
529       case 16:
530         return InternalStringToIntDouble<4>(current, end, negative,
531                                             allow_trailing_junk);
532 
533       case 32:
534         return InternalStringToIntDouble<5>(current, end, negative,
535                                             allow_trailing_junk);
536       default:
537         UNREACHABLE();
538     }
539   }
540 
541   template <class Char>
HandleBaseTenCase(Char current,Char end)542   void HandleBaseTenCase(Char current, Char end) {
543     // Parsing with strtod.
544     const int kMaxSignificantDigits = 309;  // Doubles are less than 1.8e308.
545     // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero
546     // end.
547     const int kBufferSize = kMaxSignificantDigits + 2;
548     char buffer[kBufferSize];
549     int buffer_pos = 0;
550     while (*current >= '0' && *current <= '9') {
551       if (buffer_pos <= kMaxSignificantDigits) {
552         // If the number has more than kMaxSignificantDigits it will be parsed
553         // as infinity.
554         DCHECK_LT(buffer_pos, kBufferSize);
555         buffer[buffer_pos++] = static_cast<char>(*current);
556       }
557       ++current;
558       if (current == end) break;
559     }
560 
561     SLOW_DCHECK(buffer_pos < kBufferSize);
562     buffer[buffer_pos] = '\0';
563     base::Vector<const char> buffer_vector(buffer, buffer_pos);
564     result_ = Strtod(buffer_vector, 0);
565     set_state(State::kDone);
566   }
567 
568   double result_ = 0;
569 };
570 
571 template <class Char>
HandleGenericCase(Char current,Char end)572 void NumberParseIntHelper::HandleGenericCase(Char current, Char end) {
573   // The following code causes accumulating rounding error for numbers greater
574   // than ~2^56. It's explicitly allowed in the spec: "if R is not 2, 4, 8, 10,
575   // 16, or 32, then mathInt may be an implementation-dependent approximation to
576   // the mathematical integer value" (15.1.2.2).
577 
578   int lim_0 = '0' + (radix() < 10 ? radix() : 10);
579   int lim_a = 'a' + (radix() - 10);
580   int lim_A = 'A' + (radix() - 10);
581 
582   // NOTE: The code for computing the value may seem a bit complex at
583   // first glance. It is structured to use 32-bit multiply-and-add
584   // loops as long as possible to avoid losing precision.
585 
586   bool done = false;
587   do {
588     // Parse the longest part of the string starting at {current}
589     // possible while keeping the multiplier, and thus the part
590     // itself, within 32 bits.
591     uint32_t part = 0, multiplier = 1;
592     while (true) {
593       uint32_t d;
594       if (*current >= '0' && *current < lim_0) {
595         d = *current - '0';
596       } else if (*current >= 'a' && *current < lim_a) {
597         d = *current - 'a' + 10;
598       } else if (*current >= 'A' && *current < lim_A) {
599         d = *current - 'A' + 10;
600       } else {
601         done = true;
602         break;
603       }
604 
605       // Update the value of the part as long as the multiplier fits
606       // in 32 bits. When we can't guarantee that the next iteration
607       // will not overflow the multiplier, we stop parsing the part
608       // by leaving the loop.
609       const uint32_t kMaximumMultiplier = 0xFFFFFFFFU / 36;
610       uint32_t m = multiplier * static_cast<uint32_t>(radix());
611       if (m > kMaximumMultiplier) break;
612       part = part * radix() + d;
613       multiplier = m;
614       DCHECK(multiplier > part);
615 
616       ++current;
617       if (current == end) {
618         done = true;
619         break;
620       }
621     }
622     result_ = result_ * multiplier + part;
623   } while (!done);
624 
625   if (!allow_trailing_junk() && AdvanceToNonspace(&current, end)) {
626     return set_state(State::kJunk);
627   }
628   return set_state(State::kDone);
629 }
630 
631 // Converts a string to a double value. Assumes the Iterator supports
632 // the following operations:
633 // 1. current == end (other ops are not allowed), current != end.
634 // 2. *current - gets the current character in the sequence.
635 // 3. ++current (advances the position).
636 template <class Iterator, class EndMark>
InternalStringToDouble(Iterator current,EndMark end,int flags,double empty_string_val)637 double InternalStringToDouble(Iterator current, EndMark end, int flags,
638                               double empty_string_val) {
639   // To make sure that iterator dereferencing is valid the following
640   // convention is used:
641   // 1. Each '++current' statement is followed by check for equality to 'end'.
642   // 2. If AdvanceToNonspace returned false then current == end.
643   // 3. If 'current' becomes be equal to 'end' the function returns or goes to
644   // 'parsing_done'.
645   // 4. 'current' is not dereferenced after the 'parsing_done' label.
646   // 5. Code before 'parsing_done' may rely on 'current != end'.
647   if (!AdvanceToNonspace(&current, end)) {
648     return empty_string_val;
649   }
650 
651   const bool allow_trailing_junk = (flags & ALLOW_TRAILING_JUNK) != 0;
652 
653   // Maximum number of significant digits in decimal representation.
654   // The longest possible double in decimal representation is
655   // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
656   // (768 digits). If we parse a number whose first digits are equal to a
657   // mean of 2 adjacent doubles (that could have up to 769 digits) the result
658   // must be rounded to the bigger one unless the tail consists of zeros, so
659   // we don't need to preserve all the digits.
660   const int kMaxSignificantDigits = 772;
661 
662   // The longest form of simplified number is: "-<significant digits>'.1eXXX\0".
663   const int kBufferSize = kMaxSignificantDigits + 10;
664   char buffer[kBufferSize];
665   int buffer_pos = 0;
666 
667   // Exponent will be adjusted if insignificant digits of the integer part
668   // or insignificant leading zeros of the fractional part are dropped.
669   int exponent = 0;
670   int significant_digits = 0;
671   int insignificant_digits = 0;
672   bool nonzero_digit_dropped = false;
673 
674   enum class Sign { kNone, kNegative, kPositive };
675 
676   Sign sign = Sign::kNone;
677 
678   if (*current == '+') {
679     // Ignore leading sign.
680     ++current;
681     if (current == end) return JunkStringValue();
682     sign = Sign::kPositive;
683   } else if (*current == '-') {
684     ++current;
685     if (current == end) return JunkStringValue();
686     sign = Sign::kNegative;
687   }
688 
689   static const char kInfinityString[] = "Infinity";
690   if (*current == kInfinityString[0]) {
691     if (!SubStringEquals(&current, end, kInfinityString)) {
692       return JunkStringValue();
693     }
694 
695     if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
696       return JunkStringValue();
697     }
698 
699     DCHECK_EQ(buffer_pos, 0);
700     return (sign == Sign::kNegative) ? -V8_INFINITY : V8_INFINITY;
701   }
702 
703   bool leading_zero = false;
704   if (*current == '0') {
705     ++current;
706     if (current == end) return SignedZero(sign == Sign::kNegative);
707 
708     leading_zero = true;
709 
710     // It could be hexadecimal value.
711     if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) {
712       ++current;
713       if (current == end || !isDigit(*current, 16) || sign != Sign::kNone) {
714         return JunkStringValue();  // "0x".
715       }
716 
717       return InternalStringToIntDouble<4>(current, end, false,
718                                           allow_trailing_junk);
719 
720       // It could be an explicit octal value.
721     } else if ((flags & ALLOW_OCTAL) && (*current == 'o' || *current == 'O')) {
722       ++current;
723       if (current == end || !isDigit(*current, 8) || sign != Sign::kNone) {
724         return JunkStringValue();  // "0o".
725       }
726 
727       return InternalStringToIntDouble<3>(current, end, false,
728                                           allow_trailing_junk);
729 
730       // It could be a binary value.
731     } else if ((flags & ALLOW_BINARY) && (*current == 'b' || *current == 'B')) {
732       ++current;
733       if (current == end || !isBinaryDigit(*current) || sign != Sign::kNone) {
734         return JunkStringValue();  // "0b".
735       }
736 
737       return InternalStringToIntDouble<1>(current, end, false,
738                                           allow_trailing_junk);
739     }
740 
741     // Ignore leading zeros in the integer part.
742     while (*current == '0') {
743       ++current;
744       if (current == end) return SignedZero(sign == Sign::kNegative);
745     }
746   }
747 
748   bool octal = leading_zero && (flags & ALLOW_IMPLICIT_OCTAL) != 0;
749 
750   // Copy significant digits of the integer part (if any) to the buffer.
751   while (*current >= '0' && *current <= '9') {
752     if (significant_digits < kMaxSignificantDigits) {
753       DCHECK_LT(buffer_pos, kBufferSize);
754       buffer[buffer_pos++] = static_cast<char>(*current);
755       significant_digits++;
756       // Will later check if it's an octal in the buffer.
757     } else {
758       insignificant_digits++;  // Move the digit into the exponential part.
759       nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
760     }
761     octal = octal && *current < '8';
762     ++current;
763     if (current == end) goto parsing_done;
764   }
765 
766   if (significant_digits == 0) {
767     octal = false;
768   }
769 
770   if (*current == '.') {
771     if (octal && !allow_trailing_junk) return JunkStringValue();
772     if (octal) goto parsing_done;
773 
774     ++current;
775     if (current == end) {
776       if (significant_digits == 0 && !leading_zero) {
777         return JunkStringValue();
778       } else {
779         goto parsing_done;
780       }
781     }
782 
783     if (significant_digits == 0) {
784       // octal = false;
785       // Integer part consists of 0 or is absent. Significant digits start after
786       // leading zeros (if any).
787       while (*current == '0') {
788         ++current;
789         if (current == end) return SignedZero(sign == Sign::kNegative);
790         exponent--;  // Move this 0 into the exponent.
791       }
792     }
793 
794     // There is a fractional part.  We don't emit a '.', but adjust the exponent
795     // instead.
796     while (*current >= '0' && *current <= '9') {
797       if (significant_digits < kMaxSignificantDigits) {
798         DCHECK_LT(buffer_pos, kBufferSize);
799         buffer[buffer_pos++] = static_cast<char>(*current);
800         significant_digits++;
801         exponent--;
802       } else {
803         // Ignore insignificant digits in the fractional part.
804         nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
805       }
806       ++current;
807       if (current == end) goto parsing_done;
808     }
809   }
810 
811   if (!leading_zero && exponent == 0 && significant_digits == 0) {
812     // If leading_zeros is true then the string contains zeros.
813     // If exponent < 0 then string was [+-]\.0*...
814     // If significant_digits != 0 the string is not equal to 0.
815     // Otherwise there are no digits in the string.
816     return JunkStringValue();
817   }
818 
819   // Parse exponential part.
820   if (*current == 'e' || *current == 'E') {
821     if (octal) return JunkStringValue();
822     ++current;
823     if (current == end) {
824       if (allow_trailing_junk) {
825         goto parsing_done;
826       } else {
827         return JunkStringValue();
828       }
829     }
830     char exponent_sign = '+';
831     if (*current == '+' || *current == '-') {
832       exponent_sign = static_cast<char>(*current);
833       ++current;
834       if (current == end) {
835         if (allow_trailing_junk) {
836           goto parsing_done;
837         } else {
838           return JunkStringValue();
839         }
840       }
841     }
842 
843     if (current == end || *current < '0' || *current > '9') {
844       if (allow_trailing_junk) {
845         goto parsing_done;
846       } else {
847         return JunkStringValue();
848       }
849     }
850 
851     const int max_exponent = INT_MAX / 2;
852     DCHECK(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
853     int num = 0;
854     do {
855       // Check overflow.
856       int digit = *current - '0';
857       if (num >= max_exponent / 10 &&
858           !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
859         num = max_exponent;
860       } else {
861         num = num * 10 + digit;
862       }
863       ++current;
864     } while (current != end && *current >= '0' && *current <= '9');
865 
866     exponent += (exponent_sign == '-' ? -num : num);
867   }
868 
869   if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
870     return JunkStringValue();
871   }
872 
873 parsing_done:
874   exponent += insignificant_digits;
875 
876   if (octal) {
877     return InternalStringToIntDouble<3>(buffer, buffer + buffer_pos,
878                                         sign == Sign::kNegative,
879                                         allow_trailing_junk);
880   }
881 
882   if (nonzero_digit_dropped) {
883     buffer[buffer_pos++] = '1';
884     exponent--;
885   }
886 
887   SLOW_DCHECK(buffer_pos < kBufferSize);
888   buffer[buffer_pos] = '\0';
889 
890   double converted =
891       Strtod(base::Vector<const char>(buffer, buffer_pos), exponent);
892   return (sign == Sign::kNegative) ? -converted : converted;
893 }
894 
StringToDouble(const char * str,int flags,double empty_string_val)895 double StringToDouble(const char* str, int flags, double empty_string_val) {
896   // We use {base::OneByteVector} instead of {base::CStrVector} to avoid
897   // instantiating the InternalStringToDouble() template for {const char*} as
898   // well.
899   return StringToDouble(base::OneByteVector(str), flags, empty_string_val);
900 }
901 
StringToDouble(base::Vector<const uint8_t> str,int flags,double empty_string_val)902 double StringToDouble(base::Vector<const uint8_t> str, int flags,
903                       double empty_string_val) {
904   return InternalStringToDouble(str.begin(), str.end(), flags,
905                                 empty_string_val);
906 }
907 
StringToDouble(base::Vector<const base::uc16> str,int flags,double empty_string_val)908 double StringToDouble(base::Vector<const base::uc16> str, int flags,
909                       double empty_string_val) {
910   const base::uc16* end = str.begin() + str.length();
911   return InternalStringToDouble(str.begin(), end, flags, empty_string_val);
912 }
913 
StringToInt(Isolate * isolate,Handle<String> string,int radix)914 double StringToInt(Isolate* isolate, Handle<String> string, int radix) {
915   NumberParseIntHelper helper(isolate, string, radix);
916   return helper.GetResult();
917 }
918 
919 template <typename IsolateT>
920 class StringToBigIntHelper : public StringToIntHelper<IsolateT> {
921  public:
922   enum class Behavior { kStringToBigInt, kLiteral };
923 
924   // Used for StringToBigInt operation (BigInt constructor and == operator).
StringToBigIntHelper(IsolateT * isolate,Handle<String> string)925   StringToBigIntHelper(IsolateT* isolate, Handle<String> string)
926       : StringToIntHelper<IsolateT>(isolate, string),
927         behavior_(Behavior::kStringToBigInt) {
928     this->set_allow_binary_and_octal_prefixes();
929     this->set_disallow_trailing_junk();
930   }
931 
932   // Used for parsing BigInt literals, where the input is a buffer of
933   // one-byte ASCII digits, along with an optional radix prefix.
StringToBigIntHelper(IsolateT * isolate,const uint8_t * string,int length)934   StringToBigIntHelper(IsolateT* isolate, const uint8_t* string, int length)
935       : StringToIntHelper<IsolateT>(isolate, string, length),
936         behavior_(Behavior::kLiteral) {
937     this->set_allow_binary_and_octal_prefixes();
938   }
939 
ParseOneByte(const uint8_t * start)940   void ParseOneByte(const uint8_t* start) final { return ParseInternal(start); }
ParseTwoByte(const base::uc16 * start)941   void ParseTwoByte(const base::uc16* start) final {
942     return ParseInternal(start);
943   }
944 
GetResult()945   MaybeHandle<BigInt> GetResult() {
946     this->ParseInt();
947     if (behavior_ == Behavior::kStringToBigInt && this->sign() != Sign::kNone &&
948         this->radix() != 10) {
949       return MaybeHandle<BigInt>();
950     }
951     if (this->state() == State::kEmpty) {
952       if (behavior_ == Behavior::kStringToBigInt) {
953         this->set_state(State::kZero);
954       } else {
955         UNREACHABLE();
956       }
957     }
958     switch (this->state()) {
959       case State::kJunk:
960       case State::kError:
961         return MaybeHandle<BigInt>();
962       case State::kZero:
963         return BigInt::Zero(this->isolate(), allocation_type());
964       case State::kDone:
965         return BigInt::Allocate(this->isolate(), &accumulator_,
966                                 this->negative(), allocation_type());
967       case State::kEmpty:
968       case State::kRunning:
969         break;
970     }
971     UNREACHABLE();
972   }
973 
974   // Used for converting BigInt literals. The scanner has already checked
975   // that the literal is valid and not too big, so this always succeeds.
DecimalString(bigint::Processor * processor)976   std::unique_ptr<char[]> DecimalString(bigint::Processor* processor) {
977     DCHECK_EQ(behavior_, Behavior::kLiteral);
978     this->ParseInt();
979     DCHECK_EQ(this->state(), State::kDone);
980     int num_digits = accumulator_.ResultLength();
981     base::SmallVector<bigint::digit_t, 8> digit_storage(num_digits);
982     bigint::RWDigits digits(digit_storage.data(), num_digits);
983     processor->FromString(digits, &accumulator_);
984     int num_chars = bigint::ToStringResultLength(digits, 10, false);
985     std::unique_ptr<char[]> out(new char[num_chars + 1]);
986     processor->ToString(out.get(), &num_chars, digits, 10, false);
987     out[num_chars] = '\0';
988     return out;
989   }
990 
991  private:
992   template <class Char>
ParseInternal(Char start)993   void ParseInternal(Char start) {
994     using Result = bigint::FromStringAccumulator::Result;
995     Char current = start + this->cursor();
996     Char end = start + this->length();
997     current = accumulator_.Parse(current, end, this->radix());
998 
999     Result result = accumulator_.result();
1000     if (result == Result::kMaxSizeExceeded) {
1001       return this->set_state(State::kError);
1002     }
1003     if (!this->allow_trailing_junk() && AdvanceToNonspace(&current, end)) {
1004       return this->set_state(State::kJunk);
1005     }
1006     return this->set_state(State::kDone);
1007   }
1008 
allocation_type()1009   AllocationType allocation_type() {
1010     // For literals, we pretenure the allocated BigInt, since it's about
1011     // to be stored in the interpreter's constants array.
1012     return behavior_ == Behavior::kLiteral ? AllocationType::kOld
1013                                            : AllocationType::kYoung;
1014   }
1015 
1016   bigint::FromStringAccumulator accumulator_{BigInt::kMaxLength};
1017   Behavior behavior_;
1018 };
1019 
StringToBigInt(Isolate * isolate,Handle<String> string)1020 MaybeHandle<BigInt> StringToBigInt(Isolate* isolate, Handle<String> string) {
1021   string = String::Flatten(isolate, string);
1022   StringToBigIntHelper<Isolate> helper(isolate, string);
1023   return helper.GetResult();
1024 }
1025 
1026 template <typename IsolateT>
BigIntLiteral(IsolateT * isolate,const char * string)1027 MaybeHandle<BigInt> BigIntLiteral(IsolateT* isolate, const char* string) {
1028   StringToBigIntHelper<IsolateT> helper(
1029       isolate, reinterpret_cast<const uint8_t*>(string),
1030       static_cast<int>(strlen(string)));
1031   return helper.GetResult();
1032 }
1033 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
1034     MaybeHandle<BigInt> BigIntLiteral(Isolate* isolate, const char* string);
1035 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
1036     MaybeHandle<BigInt> BigIntLiteral(LocalIsolate* isolate,
1037                                       const char* string);
1038 
BigIntLiteralToDecimal(LocalIsolate * isolate,base::Vector<const uint8_t> literal)1039 std::unique_ptr<char[]> BigIntLiteralToDecimal(
1040     LocalIsolate* isolate, base::Vector<const uint8_t> literal) {
1041   StringToBigIntHelper<LocalIsolate> helper(nullptr, literal.begin(),
1042                                             literal.length());
1043   return helper.DecimalString(isolate->bigint_processor());
1044 }
1045 
DoubleToCString(double v,base::Vector<char> buffer)1046 const char* DoubleToCString(double v, base::Vector<char> buffer) {
1047   switch (FPCLASSIFY_NAMESPACE::fpclassify(v)) {
1048     case FP_NAN:
1049       return "NaN";
1050     case FP_INFINITE:
1051       return (v < 0.0 ? "-Infinity" : "Infinity");
1052     case FP_ZERO:
1053       return "0";
1054     default: {
1055       if (IsInt32Double(v)) {
1056         // This will trigger if v is -0 and -0.0 is stringified to "0".
1057         // (see ES section 7.1.12.1 #sec-tostring-applied-to-the-number-type)
1058         return IntToCString(FastD2I(v), buffer);
1059       }
1060       SimpleStringBuilder builder(buffer.begin(), buffer.length());
1061       int decimal_point;
1062       int sign;
1063       const int kV8DtoaBufferCapacity = base::kBase10MaximalLength + 1;
1064       char decimal_rep[kV8DtoaBufferCapacity];
1065       int length;
1066 
1067       base::DoubleToAscii(
1068           v, base::DTOA_SHORTEST, 0,
1069           base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity), &sign,
1070           &length, &decimal_point);
1071 
1072       if (sign) builder.AddCharacter('-');
1073 
1074       if (length <= decimal_point && decimal_point <= 21) {
1075         // ECMA-262 section 9.8.1 step 6.
1076         builder.AddString(decimal_rep);
1077         builder.AddPadding('0', decimal_point - length);
1078 
1079       } else if (0 < decimal_point && decimal_point <= 21) {
1080         // ECMA-262 section 9.8.1 step 7.
1081         builder.AddSubstring(decimal_rep, decimal_point);
1082         builder.AddCharacter('.');
1083         builder.AddString(decimal_rep + decimal_point);
1084 
1085       } else if (decimal_point <= 0 && decimal_point > -6) {
1086         // ECMA-262 section 9.8.1 step 8.
1087         builder.AddString("0.");
1088         builder.AddPadding('0', -decimal_point);
1089         builder.AddString(decimal_rep);
1090 
1091       } else {
1092         // ECMA-262 section 9.8.1 step 9 and 10 combined.
1093         builder.AddCharacter(decimal_rep[0]);
1094         if (length != 1) {
1095           builder.AddCharacter('.');
1096           builder.AddString(decimal_rep + 1);
1097         }
1098         builder.AddCharacter('e');
1099         builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
1100         int exponent = decimal_point - 1;
1101         if (exponent < 0) exponent = -exponent;
1102         builder.AddDecimalInteger(exponent);
1103       }
1104       return builder.Finalize();
1105     }
1106   }
1107 }
1108 
IntToCString(int n,base::Vector<char> buffer)1109 const char* IntToCString(int n, base::Vector<char> buffer) {
1110   bool negative = true;
1111   if (n >= 0) {
1112     n = -n;
1113     negative = false;
1114   }
1115   // Build the string backwards from the least significant digit.
1116   int i = buffer.length();
1117   buffer[--i] = '\0';
1118   do {
1119     // We ensured n <= 0, so the subtraction does the right addition.
1120     buffer[--i] = '0' - (n % 10);
1121     n /= 10;
1122   } while (n);
1123   if (negative) buffer[--i] = '-';
1124   return buffer.begin() + i;
1125 }
1126 
DoubleToFixedCString(double value,int f)1127 char* DoubleToFixedCString(double value, int f) {
1128   const int kMaxDigitsBeforePoint = 21;
1129   const double kFirstNonFixed = 1e21;
1130   DCHECK_GE(f, 0);
1131   DCHECK_LE(f, kMaxFractionDigits);
1132 
1133   bool negative = false;
1134   double abs_value = value;
1135   if (value < 0) {
1136     abs_value = -value;
1137     negative = true;
1138   }
1139 
1140   // If abs_value has more than kMaxDigitsBeforePoint digits before the point
1141   // use the non-fixed conversion routine.
1142   if (abs_value >= kFirstNonFixed) {
1143     char arr[kMaxFractionDigits];
1144     base::Vector<char> buffer(arr, arraysize(arr));
1145     return StrDup(DoubleToCString(value, buffer));
1146   }
1147 
1148   // Find a sufficiently precise decimal representation of n.
1149   int decimal_point;
1150   int sign;
1151   // Add space for the '\0' byte.
1152   const int kDecimalRepCapacity =
1153       kMaxDigitsBeforePoint + kMaxFractionDigits + 1;
1154   char decimal_rep[kDecimalRepCapacity];
1155   int decimal_rep_length;
1156   base::DoubleToAscii(value, base::DTOA_FIXED, f,
1157                       base::Vector<char>(decimal_rep, kDecimalRepCapacity),
1158                       &sign, &decimal_rep_length, &decimal_point);
1159 
1160   // Create a representation that is padded with zeros if needed.
1161   int zero_prefix_length = 0;
1162   int zero_postfix_length = 0;
1163 
1164   if (decimal_point <= 0) {
1165     zero_prefix_length = -decimal_point + 1;
1166     decimal_point = 1;
1167   }
1168 
1169   if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
1170     zero_postfix_length =
1171         decimal_point + f - decimal_rep_length - zero_prefix_length;
1172   }
1173 
1174   unsigned rep_length =
1175       zero_prefix_length + decimal_rep_length + zero_postfix_length;
1176   SimpleStringBuilder rep_builder(rep_length + 1);
1177   rep_builder.AddPadding('0', zero_prefix_length);
1178   rep_builder.AddString(decimal_rep);
1179   rep_builder.AddPadding('0', zero_postfix_length);
1180   char* rep = rep_builder.Finalize();
1181 
1182   // Create the result string by appending a minus and putting in a
1183   // decimal point if needed.
1184   unsigned result_size = decimal_point + f + 2;
1185   SimpleStringBuilder builder(result_size + 1);
1186   if (negative) builder.AddCharacter('-');
1187   builder.AddSubstring(rep, decimal_point);
1188   if (f > 0) {
1189     builder.AddCharacter('.');
1190     builder.AddSubstring(rep + decimal_point, f);
1191   }
1192   DeleteArray(rep);
1193   return builder.Finalize();
1194 }
1195 
CreateExponentialRepresentation(char * decimal_rep,int exponent,bool negative,int significant_digits)1196 static char* CreateExponentialRepresentation(char* decimal_rep, int exponent,
1197                                              bool negative,
1198                                              int significant_digits) {
1199   bool negative_exponent = false;
1200   if (exponent < 0) {
1201     negative_exponent = true;
1202     exponent = -exponent;
1203   }
1204 
1205   // Leave room in the result for appending a minus, for a period, the
1206   // letter 'e', a minus or a plus depending on the exponent, and a
1207   // three digit exponent.
1208   unsigned result_size = significant_digits + 7;
1209   SimpleStringBuilder builder(result_size + 1);
1210 
1211   if (negative) builder.AddCharacter('-');
1212   builder.AddCharacter(decimal_rep[0]);
1213   if (significant_digits != 1) {
1214     builder.AddCharacter('.');
1215     builder.AddString(decimal_rep + 1);
1216     size_t rep_length = strlen(decimal_rep);
1217     DCHECK_GE(significant_digits, rep_length);
1218     builder.AddPadding('0', significant_digits - static_cast<int>(rep_length));
1219   }
1220 
1221   builder.AddCharacter('e');
1222   builder.AddCharacter(negative_exponent ? '-' : '+');
1223   builder.AddDecimalInteger(exponent);
1224   return builder.Finalize();
1225 }
1226 
DoubleToExponentialCString(double value,int f)1227 char* DoubleToExponentialCString(double value, int f) {
1228   // f might be -1 to signal that f was undefined in JavaScript.
1229   DCHECK(f >= -1 && f <= kMaxFractionDigits);
1230 
1231   bool negative = false;
1232   if (value < 0) {
1233     value = -value;
1234     negative = true;
1235   }
1236 
1237   // Find a sufficiently precise decimal representation of n.
1238   int decimal_point;
1239   int sign;
1240   // f corresponds to the digits after the point. There is always one digit
1241   // before the point. The number of requested_digits equals hence f + 1.
1242   // And we have to add one character for the null-terminator.
1243   const int kV8DtoaBufferCapacity = kMaxFractionDigits + 1 + 1;
1244   // Make sure that the buffer is big enough, even if we fall back to the
1245   // shortest representation (which happens when f equals -1).
1246   DCHECK_LE(base::kBase10MaximalLength, kMaxFractionDigits + 1);
1247   char decimal_rep[kV8DtoaBufferCapacity];
1248   int decimal_rep_length;
1249 
1250   if (f == -1) {
1251     base::DoubleToAscii(value, base::DTOA_SHORTEST, 0,
1252                         base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
1253                         &sign, &decimal_rep_length, &decimal_point);
1254     f = decimal_rep_length - 1;
1255   } else {
1256     base::DoubleToAscii(value, base::DTOA_PRECISION, f + 1,
1257                         base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
1258                         &sign, &decimal_rep_length, &decimal_point);
1259   }
1260   DCHECK_GT(decimal_rep_length, 0);
1261   DCHECK(decimal_rep_length <= f + 1);
1262 
1263   int exponent = decimal_point - 1;
1264   char* result =
1265       CreateExponentialRepresentation(decimal_rep, exponent, negative, f + 1);
1266 
1267   return result;
1268 }
1269 
DoubleToPrecisionCString(double value,int p)1270 char* DoubleToPrecisionCString(double value, int p) {
1271   const int kMinimalDigits = 1;
1272   DCHECK(p >= kMinimalDigits && p <= kMaxFractionDigits);
1273   USE(kMinimalDigits);
1274 
1275   bool negative = false;
1276   if (value < 0) {
1277     value = -value;
1278     negative = true;
1279   }
1280 
1281   // Find a sufficiently precise decimal representation of n.
1282   int decimal_point;
1283   int sign;
1284   // Add one for the terminating null character.
1285   const int kV8DtoaBufferCapacity = kMaxFractionDigits + 1;
1286   char decimal_rep[kV8DtoaBufferCapacity];
1287   int decimal_rep_length;
1288 
1289   base::DoubleToAscii(value, base::DTOA_PRECISION, p,
1290                       base::Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
1291                       &sign, &decimal_rep_length, &decimal_point);
1292   DCHECK(decimal_rep_length <= p);
1293 
1294   int exponent = decimal_point - 1;
1295 
1296   char* result = nullptr;
1297 
1298   if (exponent < -6 || exponent >= p) {
1299     result =
1300         CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
1301   } else {
1302     // Use fixed notation.
1303     //
1304     // Leave room in the result for appending a minus, a period and in
1305     // the case where decimal_point is not positive for a zero in
1306     // front of the period.
1307     unsigned result_size =
1308         (decimal_point <= 0) ? -decimal_point + p + 3 : p + 2;
1309     SimpleStringBuilder builder(result_size + 1);
1310     if (negative) builder.AddCharacter('-');
1311     if (decimal_point <= 0) {
1312       builder.AddString("0.");
1313       builder.AddPadding('0', -decimal_point);
1314       builder.AddString(decimal_rep);
1315       builder.AddPadding('0', p - decimal_rep_length);
1316     } else {
1317       const int m = std::min(decimal_rep_length, decimal_point);
1318       builder.AddSubstring(decimal_rep, m);
1319       builder.AddPadding('0', decimal_point - decimal_rep_length);
1320       if (decimal_point < p) {
1321         builder.AddCharacter('.');
1322         const int extra = negative ? 2 : 1;
1323         if (decimal_rep_length > decimal_point) {
1324           const size_t len = strlen(decimal_rep + decimal_point);
1325           DCHECK_GE(kMaxInt, len);
1326           const int n =
1327               std::min(static_cast<int>(len), p - (builder.position() - extra));
1328           builder.AddSubstring(decimal_rep + decimal_point, n);
1329         }
1330         builder.AddPadding('0', extra + (p - builder.position()));
1331       }
1332     }
1333     result = builder.Finalize();
1334   }
1335 
1336   return result;
1337 }
1338 
DoubleToRadixCString(double value,int radix)1339 char* DoubleToRadixCString(double value, int radix) {
1340   DCHECK(radix >= 2 && radix <= 36);
1341   DCHECK(std::isfinite(value));
1342   DCHECK_NE(0.0, value);
1343   // Character array used for conversion.
1344   static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1345 
1346   // Temporary buffer for the result. We start with the decimal point in the
1347   // middle and write to the left for the integer part and to the right for the
1348   // fractional part. 1024 characters for the exponent and 52 for the mantissa
1349   // either way, with additional space for sign, decimal point and string
1350   // termination should be sufficient.
1351   static const int kBufferSize = 2200;
1352   char buffer[kBufferSize];
1353   int integer_cursor = kBufferSize / 2;
1354   int fraction_cursor = integer_cursor;
1355 
1356   bool negative = value < 0;
1357   if (negative) value = -value;
1358 
1359   // Split the value into an integer part and a fractional part.
1360   double integer = std::floor(value);
1361   double fraction = value - integer;
1362   // We only compute fractional digits up to the input double's precision.
1363   double delta = 0.5 * (base::Double(value).NextDouble() - value);
1364   delta = std::max(base::Double(0.0).NextDouble(), delta);
1365   DCHECK_GT(delta, 0.0);
1366   if (fraction >= delta) {
1367     // Insert decimal point.
1368     buffer[fraction_cursor++] = '.';
1369     do {
1370       // Shift up by one digit.
1371       fraction *= radix;
1372       delta *= radix;
1373       // Write digit.
1374       int digit = static_cast<int>(fraction);
1375       buffer[fraction_cursor++] = chars[digit];
1376       // Calculate remainder.
1377       fraction -= digit;
1378       // Round to even.
1379       if (fraction > 0.5 || (fraction == 0.5 && (digit & 1))) {
1380         if (fraction + delta > 1) {
1381           // We need to back trace already written digits in case of carry-over.
1382           while (true) {
1383             fraction_cursor--;
1384             if (fraction_cursor == kBufferSize / 2) {
1385               CHECK_EQ('.', buffer[fraction_cursor]);
1386               // Carry over to the integer part.
1387               integer += 1;
1388               break;
1389             }
1390             char c = buffer[fraction_cursor];
1391             // Reconstruct digit.
1392             digit = c > '9' ? (c - 'a' + 10) : (c - '0');
1393             if (digit + 1 < radix) {
1394               buffer[fraction_cursor++] = chars[digit + 1];
1395               break;
1396             }
1397           }
1398           break;
1399         }
1400       }
1401     } while (fraction >= delta);
1402   }
1403 
1404   // Compute integer digits. Fill unrepresented digits with zero.
1405   while (base::Double(integer / radix).Exponent() > 0) {
1406     integer /= radix;
1407     buffer[--integer_cursor] = '0';
1408   }
1409   do {
1410     double remainder = Modulo(integer, radix);
1411     buffer[--integer_cursor] = chars[static_cast<int>(remainder)];
1412     integer = (integer - remainder) / radix;
1413   } while (integer > 0);
1414 
1415   // Add sign and terminate string.
1416   if (negative) buffer[--integer_cursor] = '-';
1417   buffer[fraction_cursor++] = '\0';
1418   DCHECK_LT(fraction_cursor, kBufferSize);
1419   DCHECK_LE(0, integer_cursor);
1420   // Allocate new string as return value.
1421   char* result = NewArray<char>(fraction_cursor - integer_cursor);
1422   memcpy(result, buffer + integer_cursor, fraction_cursor - integer_cursor);
1423   return result;
1424 }
1425 
1426 // ES6 18.2.4 parseFloat(string)
StringToDouble(Isolate * isolate,Handle<String> string,int flags,double empty_string_val)1427 double StringToDouble(Isolate* isolate, Handle<String> string, int flags,
1428                       double empty_string_val) {
1429   Handle<String> flattened = String::Flatten(isolate, string);
1430   {
1431     DisallowGarbageCollection no_gc;
1432     String::FlatContent flat = flattened->GetFlatContent(no_gc);
1433     DCHECK(flat.IsFlat());
1434     if (flat.IsOneByte()) {
1435       return StringToDouble(flat.ToOneByteVector(), flags, empty_string_val);
1436     } else {
1437       return StringToDouble(flat.ToUC16Vector(), flags, empty_string_val);
1438     }
1439   }
1440 }
1441 
TryStringToDouble(LocalIsolate * isolate,Handle<String> object,int max_length_for_conversion)1442 base::Optional<double> TryStringToDouble(LocalIsolate* isolate,
1443                                          Handle<String> object,
1444                                          int max_length_for_conversion) {
1445   DisallowGarbageCollection no_gc;
1446   int length = object->length();
1447   if (length > max_length_for_conversion) {
1448     return base::nullopt;
1449   }
1450 
1451   const int flags = ALLOW_HEX | ALLOW_OCTAL | ALLOW_BINARY;
1452   auto buffer = std::make_unique<base::uc16[]>(max_length_for_conversion);
1453   SharedStringAccessGuardIfNeeded access_guard(isolate);
1454   String::WriteToFlat(*object, buffer.get(), 0, length, isolate, access_guard);
1455   base::Vector<const base::uc16> v(buffer.get(), length);
1456   return StringToDouble(v, flags);
1457 }
1458 
IsSpecialIndex(String string)1459 bool IsSpecialIndex(String string) {
1460   // Max length of canonical double: -X.XXXXXXXXXXXXXXXXX-eXXX
1461   const int kBufferSize = 24;
1462   const int length = string.length();
1463   if (length == 0 || length > kBufferSize) return false;
1464   uint16_t buffer[kBufferSize];
1465   String::WriteToFlat(string, buffer, 0, length);
1466   // If the first char is not a digit or a '-' or we can't match 'NaN' or
1467   // '(-)Infinity', bailout immediately.
1468   int offset = 0;
1469   if (!IsDecimalDigit(buffer[0])) {
1470     if (buffer[0] == '-') {
1471       if (length == 1) return false;  // Just '-' is bad.
1472       if (!IsDecimalDigit(buffer[1])) {
1473         if (buffer[1] == 'I' && length == 9) {
1474           // Allow matching of '-Infinity' below.
1475         } else {
1476           return false;
1477         }
1478       }
1479       offset++;
1480     } else if (buffer[0] == 'I' && length == 8) {
1481       // Allow matching of 'Infinity' below.
1482     } else if (buffer[0] == 'N' && length == 3) {
1483       // Match NaN.
1484       return buffer[1] == 'a' && buffer[2] == 'N';
1485     } else {
1486       return false;
1487     }
1488   }
1489   // Expected fast path: key is an integer.
1490   static const int kRepresentableIntegerLength = 15;  // (-)XXXXXXXXXXXXXXX
1491   if (length - offset <= kRepresentableIntegerLength) {
1492     const int initial_offset = offset;
1493     bool matches = true;
1494     for (; offset < length; offset++) {
1495       matches &= IsDecimalDigit(buffer[offset]);
1496     }
1497     if (matches) {
1498       // Match 0 and -0.
1499       if (buffer[initial_offset] == '0') return initial_offset == length - 1;
1500       return true;
1501     }
1502   }
1503   // Slow path: test DoubleToString(StringToDouble(string)) == string.
1504   base::Vector<const uint16_t> vector(buffer, length);
1505   double d = StringToDouble(vector, NO_CONVERSION_FLAGS);
1506   if (std::isnan(d)) return false;
1507   // Compute reverse string.
1508   char reverse_buffer[kBufferSize + 1];  // Result will be /0 terminated.
1509   base::Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer));
1510   const char* reverse_string = DoubleToCString(d, reverse_vector);
1511   for (int i = 0; i < length; ++i) {
1512     if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false;
1513   }
1514   return true;
1515 }
1516 }  // namespace internal
1517 }  // namespace v8
1518 
1519 #undef FPCLASSIFY_NAMESPACE
1520