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