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/conversions.h"
6
7 #include <limits.h>
8 #include <stdarg.h>
9 #include <cmath>
10
11 #include "src/assert-scope.h"
12 #include "src/char-predicates-inl.h"
13 #include "src/codegen.h"
14 #include "src/conversions-inl.h"
15 #include "src/dtoa.h"
16 #include "src/factory.h"
17 #include "src/list-inl.h"
18 #include "src/strtod.h"
19 #include "src/utils.h"
20
21 #ifndef _STLP_VENDOR_CSTD
22 // STLPort doesn't import fpclassify into the std namespace.
23 using std::fpclassify;
24 #endif
25
26 namespace v8 {
27 namespace internal {
28
29
30 namespace {
31
32 // C++-style iterator adaptor for StringCharacterStream
33 // (unlike C++ iterators the end-marker has different type).
34 class StringCharacterStreamIterator {
35 public:
36 class EndMarker {};
37
38 explicit StringCharacterStreamIterator(StringCharacterStream* stream);
39
40 uint16_t operator*() const;
41 void operator++();
operator ==(EndMarker const &) const42 bool operator==(EndMarker const&) const { return end_; }
operator !=(EndMarker const & m) const43 bool operator!=(EndMarker const& m) const { return !end_; }
44
45 private:
46 StringCharacterStream* const stream_;
47 uint16_t current_;
48 bool end_;
49 };
50
51
StringCharacterStreamIterator(StringCharacterStream * stream)52 StringCharacterStreamIterator::StringCharacterStreamIterator(
53 StringCharacterStream* stream) : stream_(stream) {
54 ++(*this);
55 }
56
operator *() const57 uint16_t StringCharacterStreamIterator::operator*() const {
58 return current_;
59 }
60
61
operator ++()62 void StringCharacterStreamIterator::operator++() {
63 end_ = !stream_->HasMore();
64 if (!end_) {
65 current_ = stream_->GetNext();
66 }
67 }
68 } // End anonymous namespace.
69
70
StringToDouble(UnicodeCache * unicode_cache,const char * str,int flags,double empty_string_val)71 double StringToDouble(UnicodeCache* unicode_cache,
72 const char* str, int flags, double empty_string_val) {
73 // We cast to const uint8_t* here to avoid instantiating the
74 // InternalStringToDouble() template for const char* as well.
75 const uint8_t* start = reinterpret_cast<const uint8_t*>(str);
76 const uint8_t* end = start + StrLength(str);
77 return InternalStringToDouble(unicode_cache, start, end, flags,
78 empty_string_val);
79 }
80
81
StringToDouble(UnicodeCache * unicode_cache,Vector<const uint8_t> str,int flags,double empty_string_val)82 double StringToDouble(UnicodeCache* unicode_cache,
83 Vector<const uint8_t> str,
84 int flags,
85 double empty_string_val) {
86 // We cast to const uint8_t* here to avoid instantiating the
87 // InternalStringToDouble() template for const char* as well.
88 const uint8_t* start = reinterpret_cast<const uint8_t*>(str.start());
89 const uint8_t* end = start + str.length();
90 return InternalStringToDouble(unicode_cache, start, end, flags,
91 empty_string_val);
92 }
93
94
StringToDouble(UnicodeCache * unicode_cache,Vector<const uc16> str,int flags,double empty_string_val)95 double StringToDouble(UnicodeCache* unicode_cache,
96 Vector<const uc16> str,
97 int flags,
98 double empty_string_val) {
99 const uc16* end = str.start() + str.length();
100 return InternalStringToDouble(unicode_cache, str.start(), end, flags,
101 empty_string_val);
102 }
103
104
105 // Converts a string into an integer.
StringToInt(UnicodeCache * unicode_cache,Vector<const uint8_t> vector,int radix)106 double StringToInt(UnicodeCache* unicode_cache,
107 Vector<const uint8_t> vector,
108 int radix) {
109 return InternalStringToInt(
110 unicode_cache, vector.start(), vector.start() + vector.length(), radix);
111 }
112
113
StringToInt(UnicodeCache * unicode_cache,Vector<const uc16> vector,int radix)114 double StringToInt(UnicodeCache* unicode_cache,
115 Vector<const uc16> vector,
116 int radix) {
117 return InternalStringToInt(
118 unicode_cache, vector.start(), vector.start() + vector.length(), radix);
119 }
120
121
DoubleToCString(double v,Vector<char> buffer)122 const char* DoubleToCString(double v, Vector<char> buffer) {
123 switch (fpclassify(v)) {
124 case FP_NAN: return "NaN";
125 case FP_INFINITE: return (v < 0.0 ? "-Infinity" : "Infinity");
126 case FP_ZERO: return "0";
127 default: {
128 SimpleStringBuilder builder(buffer.start(), buffer.length());
129 int decimal_point;
130 int sign;
131 const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1;
132 char decimal_rep[kV8DtoaBufferCapacity];
133 int length;
134
135 DoubleToAscii(v, DTOA_SHORTEST, 0,
136 Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
137 &sign, &length, &decimal_point);
138
139 if (sign) builder.AddCharacter('-');
140
141 if (length <= decimal_point && decimal_point <= 21) {
142 // ECMA-262 section 9.8.1 step 6.
143 builder.AddString(decimal_rep);
144 builder.AddPadding('0', decimal_point - length);
145
146 } else if (0 < decimal_point && decimal_point <= 21) {
147 // ECMA-262 section 9.8.1 step 7.
148 builder.AddSubstring(decimal_rep, decimal_point);
149 builder.AddCharacter('.');
150 builder.AddString(decimal_rep + decimal_point);
151
152 } else if (decimal_point <= 0 && decimal_point > -6) {
153 // ECMA-262 section 9.8.1 step 8.
154 builder.AddString("0.");
155 builder.AddPadding('0', -decimal_point);
156 builder.AddString(decimal_rep);
157
158 } else {
159 // ECMA-262 section 9.8.1 step 9 and 10 combined.
160 builder.AddCharacter(decimal_rep[0]);
161 if (length != 1) {
162 builder.AddCharacter('.');
163 builder.AddString(decimal_rep + 1);
164 }
165 builder.AddCharacter('e');
166 builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
167 int exponent = decimal_point - 1;
168 if (exponent < 0) exponent = -exponent;
169 builder.AddDecimalInteger(exponent);
170 }
171 return builder.Finalize();
172 }
173 }
174 }
175
176
IntToCString(int n,Vector<char> buffer)177 const char* IntToCString(int n, Vector<char> buffer) {
178 bool negative = false;
179 if (n < 0) {
180 // We must not negate the most negative int.
181 if (n == kMinInt) return DoubleToCString(n, buffer);
182 negative = true;
183 n = -n;
184 }
185 // Build the string backwards from the least significant digit.
186 int i = buffer.length();
187 buffer[--i] = '\0';
188 do {
189 buffer[--i] = '0' + (n % 10);
190 n /= 10;
191 } while (n);
192 if (negative) buffer[--i] = '-';
193 return buffer.start() + i;
194 }
195
196
DoubleToFixedCString(double value,int f)197 char* DoubleToFixedCString(double value, int f) {
198 const int kMaxDigitsBeforePoint = 21;
199 const double kFirstNonFixed = 1e21;
200 const int kMaxDigitsAfterPoint = 20;
201 DCHECK(f >= 0);
202 DCHECK(f <= kMaxDigitsAfterPoint);
203
204 bool negative = false;
205 double abs_value = value;
206 if (value < 0) {
207 abs_value = -value;
208 negative = true;
209 }
210
211 // If abs_value has more than kMaxDigitsBeforePoint digits before the point
212 // use the non-fixed conversion routine.
213 if (abs_value >= kFirstNonFixed) {
214 char arr[100];
215 Vector<char> buffer(arr, arraysize(arr));
216 return StrDup(DoubleToCString(value, buffer));
217 }
218
219 // Find a sufficiently precise decimal representation of n.
220 int decimal_point;
221 int sign;
222 // Add space for the '\0' byte.
223 const int kDecimalRepCapacity =
224 kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 1;
225 char decimal_rep[kDecimalRepCapacity];
226 int decimal_rep_length;
227 DoubleToAscii(value, DTOA_FIXED, f,
228 Vector<char>(decimal_rep, kDecimalRepCapacity),
229 &sign, &decimal_rep_length, &decimal_point);
230
231 // Create a representation that is padded with zeros if needed.
232 int zero_prefix_length = 0;
233 int zero_postfix_length = 0;
234
235 if (decimal_point <= 0) {
236 zero_prefix_length = -decimal_point + 1;
237 decimal_point = 1;
238 }
239
240 if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
241 zero_postfix_length = decimal_point + f - decimal_rep_length -
242 zero_prefix_length;
243 }
244
245 unsigned rep_length =
246 zero_prefix_length + decimal_rep_length + zero_postfix_length;
247 SimpleStringBuilder rep_builder(rep_length + 1);
248 rep_builder.AddPadding('0', zero_prefix_length);
249 rep_builder.AddString(decimal_rep);
250 rep_builder.AddPadding('0', zero_postfix_length);
251 char* rep = rep_builder.Finalize();
252
253 // Create the result string by appending a minus and putting in a
254 // decimal point if needed.
255 unsigned result_size = decimal_point + f + 2;
256 SimpleStringBuilder builder(result_size + 1);
257 if (negative) builder.AddCharacter('-');
258 builder.AddSubstring(rep, decimal_point);
259 if (f > 0) {
260 builder.AddCharacter('.');
261 builder.AddSubstring(rep + decimal_point, f);
262 }
263 DeleteArray(rep);
264 return builder.Finalize();
265 }
266
267
CreateExponentialRepresentation(char * decimal_rep,int exponent,bool negative,int significant_digits)268 static char* CreateExponentialRepresentation(char* decimal_rep,
269 int exponent,
270 bool negative,
271 int significant_digits) {
272 bool negative_exponent = false;
273 if (exponent < 0) {
274 negative_exponent = true;
275 exponent = -exponent;
276 }
277
278 // Leave room in the result for appending a minus, for a period, the
279 // letter 'e', a minus or a plus depending on the exponent, and a
280 // three digit exponent.
281 unsigned result_size = significant_digits + 7;
282 SimpleStringBuilder builder(result_size + 1);
283
284 if (negative) builder.AddCharacter('-');
285 builder.AddCharacter(decimal_rep[0]);
286 if (significant_digits != 1) {
287 builder.AddCharacter('.');
288 builder.AddString(decimal_rep + 1);
289 int rep_length = StrLength(decimal_rep);
290 builder.AddPadding('0', significant_digits - rep_length);
291 }
292
293 builder.AddCharacter('e');
294 builder.AddCharacter(negative_exponent ? '-' : '+');
295 builder.AddDecimalInteger(exponent);
296 return builder.Finalize();
297 }
298
299
DoubleToExponentialCString(double value,int f)300 char* DoubleToExponentialCString(double value, int f) {
301 const int kMaxDigitsAfterPoint = 20;
302 // f might be -1 to signal that f was undefined in JavaScript.
303 DCHECK(f >= -1 && f <= kMaxDigitsAfterPoint);
304
305 bool negative = false;
306 if (value < 0) {
307 value = -value;
308 negative = true;
309 }
310
311 // Find a sufficiently precise decimal representation of n.
312 int decimal_point;
313 int sign;
314 // f corresponds to the digits after the point. There is always one digit
315 // before the point. The number of requested_digits equals hence f + 1.
316 // And we have to add one character for the null-terminator.
317 const int kV8DtoaBufferCapacity = kMaxDigitsAfterPoint + 1 + 1;
318 // Make sure that the buffer is big enough, even if we fall back to the
319 // shortest representation (which happens when f equals -1).
320 DCHECK(kBase10MaximalLength <= kMaxDigitsAfterPoint + 1);
321 char decimal_rep[kV8DtoaBufferCapacity];
322 int decimal_rep_length;
323
324 if (f == -1) {
325 DoubleToAscii(value, DTOA_SHORTEST, 0,
326 Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
327 &sign, &decimal_rep_length, &decimal_point);
328 f = decimal_rep_length - 1;
329 } else {
330 DoubleToAscii(value, DTOA_PRECISION, f + 1,
331 Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
332 &sign, &decimal_rep_length, &decimal_point);
333 }
334 DCHECK(decimal_rep_length > 0);
335 DCHECK(decimal_rep_length <= f + 1);
336
337 int exponent = decimal_point - 1;
338 char* result =
339 CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1);
340
341 return result;
342 }
343
344
DoubleToPrecisionCString(double value,int p)345 char* DoubleToPrecisionCString(double value, int p) {
346 const int kMinimalDigits = 1;
347 const int kMaximalDigits = 21;
348 DCHECK(p >= kMinimalDigits && p <= kMaximalDigits);
349 USE(kMinimalDigits);
350
351 bool negative = false;
352 if (value < 0) {
353 value = -value;
354 negative = true;
355 }
356
357 // Find a sufficiently precise decimal representation of n.
358 int decimal_point;
359 int sign;
360 // Add one for the terminating null character.
361 const int kV8DtoaBufferCapacity = kMaximalDigits + 1;
362 char decimal_rep[kV8DtoaBufferCapacity];
363 int decimal_rep_length;
364
365 DoubleToAscii(value, DTOA_PRECISION, p,
366 Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
367 &sign, &decimal_rep_length, &decimal_point);
368 DCHECK(decimal_rep_length <= p);
369
370 int exponent = decimal_point - 1;
371
372 char* result = NULL;
373
374 if (exponent < -6 || exponent >= p) {
375 result =
376 CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
377 } else {
378 // Use fixed notation.
379 //
380 // Leave room in the result for appending a minus, a period and in
381 // the case where decimal_point is not positive for a zero in
382 // front of the period.
383 unsigned result_size = (decimal_point <= 0)
384 ? -decimal_point + p + 3
385 : p + 2;
386 SimpleStringBuilder builder(result_size + 1);
387 if (negative) builder.AddCharacter('-');
388 if (decimal_point <= 0) {
389 builder.AddString("0.");
390 builder.AddPadding('0', -decimal_point);
391 builder.AddString(decimal_rep);
392 builder.AddPadding('0', p - decimal_rep_length);
393 } else {
394 const int m = Min(decimal_rep_length, decimal_point);
395 builder.AddSubstring(decimal_rep, m);
396 builder.AddPadding('0', decimal_point - decimal_rep_length);
397 if (decimal_point < p) {
398 builder.AddCharacter('.');
399 const int extra = negative ? 2 : 1;
400 if (decimal_rep_length > decimal_point) {
401 const int len = StrLength(decimal_rep + decimal_point);
402 const int n = Min(len, p - (builder.position() - extra));
403 builder.AddSubstring(decimal_rep + decimal_point, n);
404 }
405 builder.AddPadding('0', extra + (p - builder.position()));
406 }
407 }
408 result = builder.Finalize();
409 }
410
411 return result;
412 }
413
414
DoubleToRadixCString(double value,int radix)415 char* DoubleToRadixCString(double value, int radix) {
416 DCHECK(radix >= 2 && radix <= 36);
417
418 // Character array used for conversion.
419 static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
420
421 // Buffer for the integer part of the result. 1024 chars is enough
422 // for max integer value in radix 2. We need room for a sign too.
423 static const int kBufferSize = 1100;
424 char integer_buffer[kBufferSize];
425 integer_buffer[kBufferSize - 1] = '\0';
426
427 // Buffer for the decimal part of the result. We only generate up
428 // to kBufferSize - 1 chars for the decimal part.
429 char decimal_buffer[kBufferSize];
430 decimal_buffer[kBufferSize - 1] = '\0';
431
432 // Make sure the value is positive.
433 bool is_negative = value < 0.0;
434 if (is_negative) value = -value;
435
436 // Get the integer part and the decimal part.
437 double integer_part = std::floor(value);
438 double decimal_part = value - integer_part;
439
440 // Convert the integer part starting from the back. Always generate
441 // at least one digit.
442 int integer_pos = kBufferSize - 2;
443 do {
444 double remainder = modulo(integer_part, radix);
445 integer_buffer[integer_pos--] = chars[static_cast<int>(remainder)];
446 integer_part -= remainder;
447 integer_part /= radix;
448 } while (integer_part >= 1.0);
449 // Sanity check.
450 DCHECK(integer_pos > 0);
451 // Add sign if needed.
452 if (is_negative) integer_buffer[integer_pos--] = '-';
453
454 // Convert the decimal part. Repeatedly multiply by the radix to
455 // generate the next char. Never generate more than kBufferSize - 1
456 // chars.
457 //
458 // TODO(1093998): We will often generate a full decimal_buffer of
459 // chars because hitting zero will often not happen. The right
460 // solution would be to continue until the string representation can
461 // be read back and yield the original value. To implement this
462 // efficiently, we probably have to modify dtoa.
463 int decimal_pos = 0;
464 while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
465 decimal_part *= radix;
466 decimal_buffer[decimal_pos++] =
467 chars[static_cast<int>(std::floor(decimal_part))];
468 decimal_part -= std::floor(decimal_part);
469 }
470 decimal_buffer[decimal_pos] = '\0';
471
472 // Compute the result size.
473 int integer_part_size = kBufferSize - 2 - integer_pos;
474 // Make room for zero termination.
475 unsigned result_size = integer_part_size + decimal_pos;
476 // If the number has a decimal part, leave room for the period.
477 if (decimal_pos > 0) result_size++;
478 // Allocate result and fill in the parts.
479 SimpleStringBuilder builder(result_size + 1);
480 builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
481 if (decimal_pos > 0) builder.AddCharacter('.');
482 builder.AddSubstring(decimal_buffer, decimal_pos);
483 return builder.Finalize();
484 }
485
486
487 // ES6 18.2.4 parseFloat(string)
StringToDouble(UnicodeCache * unicode_cache,Handle<String> string,int flags,double empty_string_val)488 double StringToDouble(UnicodeCache* unicode_cache, Handle<String> string,
489 int flags, double empty_string_val) {
490 Handle<String> flattened = String::Flatten(string);
491 {
492 DisallowHeapAllocation no_gc;
493 String::FlatContent flat = flattened->GetFlatContent();
494 DCHECK(flat.IsFlat());
495 if (flat.IsOneByte()) {
496 return StringToDouble(unicode_cache, flat.ToOneByteVector(), flags,
497 empty_string_val);
498 } else {
499 return StringToDouble(unicode_cache, flat.ToUC16Vector(), flags,
500 empty_string_val);
501 }
502 }
503 }
504
505
IsSpecialIndex(UnicodeCache * unicode_cache,String * string)506 bool IsSpecialIndex(UnicodeCache* unicode_cache, String* string) {
507 // Max length of canonical double: -X.XXXXXXXXXXXXXXXXX-eXXX
508 const int kBufferSize = 24;
509 const int length = string->length();
510 if (length == 0 || length > kBufferSize) return false;
511 uint16_t buffer[kBufferSize];
512 String::WriteToFlat(string, buffer, 0, length);
513 // If the first char is not a digit or a '-' or we can't match 'NaN' or
514 // '(-)Infinity', bailout immediately.
515 int offset = 0;
516 if (!IsDecimalDigit(buffer[0])) {
517 if (buffer[0] == '-') {
518 if (length == 1) return false; // Just '-' is bad.
519 if (!IsDecimalDigit(buffer[1])) {
520 if (buffer[1] == 'I' && length == 9) {
521 // Allow matching of '-Infinity' below.
522 } else {
523 return false;
524 }
525 }
526 offset++;
527 } else if (buffer[0] == 'I' && length == 8) {
528 // Allow matching of 'Infinity' below.
529 } else if (buffer[0] == 'N' && length == 3) {
530 // Match NaN.
531 return buffer[1] == 'a' && buffer[2] == 'N';
532 } else {
533 return false;
534 }
535 }
536 // Expected fast path: key is an integer.
537 static const int kRepresentableIntegerLength = 15; // (-)XXXXXXXXXXXXXXX
538 if (length - offset <= kRepresentableIntegerLength) {
539 const int initial_offset = offset;
540 bool matches = true;
541 for (; offset < length; offset++) {
542 matches &= IsDecimalDigit(buffer[offset]);
543 }
544 if (matches) {
545 // Match 0 and -0.
546 if (buffer[initial_offset] == '0') return initial_offset == length - 1;
547 return true;
548 }
549 }
550 // Slow path: test DoubleToString(StringToDouble(string)) == string.
551 Vector<const uint16_t> vector(buffer, length);
552 double d = StringToDouble(unicode_cache, vector, NO_FLAGS);
553 if (std::isnan(d)) return false;
554 // Compute reverse string.
555 char reverse_buffer[kBufferSize + 1]; // Result will be /0 terminated.
556 Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer));
557 const char* reverse_string = DoubleToCString(d, reverse_vector);
558 for (int i = 0; i < length; ++i) {
559 if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false;
560 }
561 return true;
562 }
563 } // namespace internal
564 } // namespace v8
565