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

5 6
#include "src/conversions.h"

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 15 16 17 18 19
#include "src/conversions-inl.h"
#include "src/dtoa.h"
#include "src/factory.h"
#include "src/list-inl.h"
#include "src/strtod.h"
#include "src/utils.h"
20

21 22 23 24 25
#ifndef _STLP_VENDOR_CSTD
// STLPort doesn't import fpclassify into the std namespace.
using std::fpclassify;
#endif

26 27
namespace v8 {
namespace internal {
28

29

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
namespace {

// C++-style iterator adaptor for StringCharacterStream
// (unlike C++ iterators the end-marker has different type).
class StringCharacterStreamIterator {
 public:
  class EndMarker {};

  explicit StringCharacterStreamIterator(StringCharacterStream* stream);

  uint16_t operator*() const;
  void operator++();
  bool operator==(EndMarker const&) const { return end_; }
  bool operator!=(EndMarker const& m) const { return !end_; }

 private:
  StringCharacterStream* const stream_;
  uint16_t current_;
  bool end_;
};


StringCharacterStreamIterator::StringCharacterStreamIterator(
    StringCharacterStream* stream) : stream_(stream) {
  ++(*this);
}

uint16_t StringCharacterStreamIterator::operator*() const {
  return current_;
}


void StringCharacterStreamIterator::operator++() {
  end_ = !stream_->HasMore();
  if (!end_) {
    current_ = stream_->GetNext();
  }
}
}  // End anonymous namespace.


71 72
double StringToDouble(UnicodeCache* unicode_cache,
                      const char* str, int flags, double empty_string_val) {
73 74 75 76 77
  // We cast to const uint8_t* here to avoid instantiating the
  // InternalStringToDouble() template for const char* as well.
  const uint8_t* start = reinterpret_cast<const uint8_t*>(str);
  const uint8_t* end = start + StrLength(str);
  return InternalStringToDouble(unicode_cache, start, end, flags,
78
                                empty_string_val);
79 80 81
}


82
double StringToDouble(UnicodeCache* unicode_cache,
83
                      Vector<const uint8_t> str,
84 85
                      int flags,
                      double empty_string_val) {
86 87 88 89 90
  // We cast to const uint8_t* here to avoid instantiating the
  // InternalStringToDouble() template for const char* as well.
  const uint8_t* start = reinterpret_cast<const uint8_t*>(str.start());
  const uint8_t* end = start + str.length();
  return InternalStringToDouble(unicode_cache, start, end, flags,
91
                                empty_string_val);
92 93
}

94

95 96 97 98 99 100 101 102 103
double StringToDouble(UnicodeCache* unicode_cache,
                      Vector<const uc16> str,
                      int flags,
                      double empty_string_val) {
  const uc16* end = str.start() + str.length();
  return InternalStringToDouble(unicode_cache, str.start(), end, flags,
                                empty_string_val);
}

104

105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
// Converts a string into an integer.
double StringToInt(UnicodeCache* unicode_cache,
                   Vector<const uint8_t> vector,
                   int radix) {
  return InternalStringToInt(
      unicode_cache, vector.start(), vector.start() + vector.length(), radix);
}


double StringToInt(UnicodeCache* unicode_cache,
                   Vector<const uc16> vector,
                   int radix) {
  return InternalStringToInt(
      unicode_cache, vector.start(), vector.start() + vector.length(), radix);
}


122 123
const char* DoubleToCString(double v, Vector<char> buffer) {
  switch (fpclassify(v)) {
124 125 126
    case FP_NAN: return "NaN";
    case FP_INFINITE: return (v < 0.0 ? "-Infinity" : "Infinity");
    case FP_ZERO: return "0";
127
    default: {
128
      SimpleStringBuilder builder(buffer.start(), buffer.length());
129 130
      int decimal_point;
      int sign;
131
      const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1;
132
      char decimal_rep[kV8DtoaBufferCapacity];
133
      int length;
134

135 136 137
      DoubleToAscii(v, DTOA_SHORTEST, 0,
                    Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                    &sign, &length, &decimal_point);
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168

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

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

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

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

      } else {
        // ECMA-262 section 9.8.1 step 9 and 10 combined.
        builder.AddCharacter(decimal_rep[0]);
        if (length != 1) {
          builder.AddCharacter('.');
          builder.AddString(decimal_rep + 1);
        }
        builder.AddCharacter('e');
        builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
        int exponent = decimal_point - 1;
        if (exponent < 0) exponent = -exponent;
169
        builder.AddDecimalInteger(exponent);
170
      }
171
    return builder.Finalize();
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
    }
  }
}


const char* IntToCString(int n, Vector<char> buffer) {
  bool negative = false;
  if (n < 0) {
    // We must not negate the most negative int.
    if (n == kMinInt) return DoubleToCString(n, buffer);
    negative = true;
    n = -n;
  }
  // Build the string backwards from the least significant digit.
  int i = buffer.length();
  buffer[--i] = '\0';
  do {
    buffer[--i] = '0' + (n % 10);
    n /= 10;
  } while (n);
  if (negative) buffer[--i] = '-';
  return buffer.start() + i;
}


char* DoubleToFixedCString(double value, int f) {
198
  const int kMaxDigitsBeforePoint = 21;
199 200
  const double kFirstNonFixed = 1e21;
  const int kMaxDigitsAfterPoint = 20;
201 202
  DCHECK(f >= 0);
  DCHECK(f <= kMaxDigitsAfterPoint);
203 204 205 206 207 208 209 210

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

211 212 213
  // If abs_value has more than kMaxDigitsBeforePoint digits before the point
  // use the non-fixed conversion routine.
  if (abs_value >= kFirstNonFixed) {
214
    char arr[100];
215
    Vector<char> buffer(arr, arraysize(arr));
216 217 218 219 220 221
    return StrDup(DoubleToCString(value, buffer));
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
222
  // Add space for the '\0' byte.
223
  const int kDecimalRepCapacity =
224
      kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 1;
225 226
  char decimal_rep[kDecimalRepCapacity];
  int decimal_rep_length;
227 228 229
  DoubleToAscii(value, DTOA_FIXED, f,
                Vector<char>(decimal_rep, kDecimalRepCapacity),
                &sign, &decimal_rep_length, &decimal_point);
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246

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

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

  if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
    zero_postfix_length = decimal_point + f - decimal_rep_length -
                          zero_prefix_length;
  }

  unsigned rep_length =
      zero_prefix_length + decimal_rep_length + zero_postfix_length;
247
  SimpleStringBuilder rep_builder(rep_length + 1);
248 249 250 251 252 253 254 255
  rep_builder.AddPadding('0', zero_prefix_length);
  rep_builder.AddString(decimal_rep);
  rep_builder.AddPadding('0', zero_postfix_length);
  char* rep = rep_builder.Finalize();

  // Create the result string by appending a minus and putting in a
  // decimal point if needed.
  unsigned result_size = decimal_point + f + 2;
256
  SimpleStringBuilder builder(result_size + 1);
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
  if (negative) builder.AddCharacter('-');
  builder.AddSubstring(rep, decimal_point);
  if (f > 0) {
    builder.AddCharacter('.');
    builder.AddSubstring(rep + decimal_point, f);
  }
  DeleteArray(rep);
  return builder.Finalize();
}


static char* CreateExponentialRepresentation(char* decimal_rep,
                                             int exponent,
                                             bool negative,
                                             int significant_digits) {
  bool negative_exponent = false;
  if (exponent < 0) {
    negative_exponent = true;
    exponent = -exponent;
  }

  // Leave room in the result for appending a minus, for a period, the
  // letter 'e', a minus or a plus depending on the exponent, and a
  // three digit exponent.
  unsigned result_size = significant_digits + 7;
282
  SimpleStringBuilder builder(result_size + 1);
283 284 285 286 287 288

  if (negative) builder.AddCharacter('-');
  builder.AddCharacter(decimal_rep[0]);
  if (significant_digits != 1) {
    builder.AddCharacter('.');
    builder.AddString(decimal_rep + 1);
289 290
    int rep_length = StrLength(decimal_rep);
    builder.AddPadding('0', significant_digits - rep_length);
291 292 293 294
  }

  builder.AddCharacter('e');
  builder.AddCharacter(negative_exponent ? '-' : '+');
295
  builder.AddDecimalInteger(exponent);
296 297 298 299 300
  return builder.Finalize();
}


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 306 307 308 309 310 311 312 313

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

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
314 315 316 317 318 319
  // f corresponds to the digits after the point. There is always one digit
  // before the point. The number of requested_digits equals hence f + 1.
  // And we have to add one character for the null-terminator.
  const int kV8DtoaBufferCapacity = kMaxDigitsAfterPoint + 1 + 1;
  // Make sure that the buffer is big enough, even if we fall back to the
  // shortest representation (which happens when f equals -1).
320
  DCHECK(kBase10MaximalLength <= kMaxDigitsAfterPoint + 1);
321
  char decimal_rep[kV8DtoaBufferCapacity];
322 323
  int decimal_rep_length;

324
  if (f == -1) {
325 326 327 328
    DoubleToAscii(value, DTOA_SHORTEST, 0,
                  Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                  &sign, &decimal_rep_length, &decimal_point);
    f = decimal_rep_length - 1;
329
  } else {
330 331 332
    DoubleToAscii(value, DTOA_PRECISION, f + 1,
                  Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                  &sign, &decimal_rep_length, &decimal_point);
333
  }
334 335
  DCHECK(decimal_rep_length > 0);
  DCHECK(decimal_rep_length <= f + 1);
336 337 338 339 340 341 342 343 344 345

  int exponent = decimal_point - 1;
  char* result =
      CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1);

  return result;
}


char* DoubleToPrecisionCString(double value, int p) {
346 347
  const int kMinimalDigits = 1;
  const int kMaximalDigits = 21;
348
  DCHECK(p >= kMinimalDigits && p <= kMaximalDigits);
349
  USE(kMinimalDigits);
350 351 352 353 354 355 356 357 358 359

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

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
360 361
  // Add one for the terminating null character.
  const int kV8DtoaBufferCapacity = kMaximalDigits + 1;
362
  char decimal_rep[kV8DtoaBufferCapacity];
363 364
  int decimal_rep_length;

365 366 367
  DoubleToAscii(value, DTOA_PRECISION, p,
                Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                &sign, &decimal_rep_length, &decimal_point);
368
  DCHECK(decimal_rep_length <= p);
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385

  int exponent = decimal_point - 1;

  char* result = NULL;

  if (exponent < -6 || exponent >= p) {
    result =
        CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
  } else {
    // Use fixed notation.
    //
    // Leave room in the result for appending a minus, a period and in
    // the case where decimal_point is not positive for a zero in
    // front of the period.
    unsigned result_size = (decimal_point <= 0)
        ? -decimal_point + p + 3
        : p + 2;
386
    SimpleStringBuilder builder(result_size + 1);
387 388 389 390 391 392 393 394 395 396 397 398 399 400
    if (negative) builder.AddCharacter('-');
    if (decimal_point <= 0) {
      builder.AddString("0.");
      builder.AddPadding('0', -decimal_point);
      builder.AddString(decimal_rep);
      builder.AddPadding('0', p - decimal_rep_length);
    } else {
      const int m = Min(decimal_rep_length, decimal_point);
      builder.AddSubstring(decimal_rep, m);
      builder.AddPadding('0', decimal_point - decimal_rep_length);
      if (decimal_point < p) {
        builder.AddCharacter('.');
        const int extra = negative ? 2 : 1;
        if (decimal_rep_length > decimal_point) {
401
          const int len = StrLength(decimal_rep + decimal_point);
402 403 404 405 406 407 408 409 410 411 412 413 414 415
          const int n = Min(len, p - (builder.position() - extra));
          builder.AddSubstring(decimal_rep + decimal_point, n);
        }
        builder.AddPadding('0', extra + (p - builder.position()));
      }
    }
    result = builder.Finalize();
  }

  return result;
}


char* DoubleToRadixCString(double value, int radix) {
416
  DCHECK(radix >= 2 && radix <= 36);
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436

  // Character array used for conversion.
  static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";

  // Buffer for the integer part of the result. 1024 chars is enough
  // for max integer value in radix 2.  We need room for a sign too.
  static const int kBufferSize = 1100;
  char integer_buffer[kBufferSize];
  integer_buffer[kBufferSize - 1] = '\0';

  // Buffer for the decimal part of the result.  We only generate up
  // to kBufferSize - 1 chars for the decimal part.
  char decimal_buffer[kBufferSize];
  decimal_buffer[kBufferSize - 1] = '\0';

  // Make sure the value is positive.
  bool is_negative = value < 0.0;
  if (is_negative) value = -value;

  // Get the integer part and the decimal part.
437
  double integer_part = std::floor(value);
438 439 440 441 442 443
  double decimal_part = value - integer_part;

  // Convert the integer part starting from the back.  Always generate
  // at least one digit.
  int integer_pos = kBufferSize - 2;
  do {
444
    double remainder = modulo(integer_part, radix);
445 446
    integer_buffer[integer_pos--] = chars[static_cast<int>(remainder)];
    integer_part -= remainder;
447 448 449
    integer_part /= radix;
  } while (integer_part >= 1.0);
  // Sanity check.
450
  DCHECK(integer_pos > 0);
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
  // Add sign if needed.
  if (is_negative) integer_buffer[integer_pos--] = '-';

  // Convert the decimal part.  Repeatedly multiply by the radix to
  // generate the next char.  Never generate more than kBufferSize - 1
  // chars.
  //
  // TODO(1093998): We will often generate a full decimal_buffer of
  // chars because hitting zero will often not happen.  The right
  // solution would be to continue until the string representation can
  // be read back and yield the original value.  To implement this
  // efficiently, we probably have to modify dtoa.
  int decimal_pos = 0;
  while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
    decimal_part *= radix;
    decimal_buffer[decimal_pos++] =
467 468
        chars[static_cast<int>(std::floor(decimal_part))];
    decimal_part -= std::floor(decimal_part);
469 470 471 472 473 474 475 476 477 478
  }
  decimal_buffer[decimal_pos] = '\0';

  // Compute the result size.
  int integer_part_size = kBufferSize - 2 - integer_pos;
  // Make room for zero termination.
  unsigned result_size = integer_part_size + decimal_pos;
  // If the number has a decimal part, leave room for the period.
  if (decimal_pos > 0) result_size++;
  // Allocate result and fill in the parts.
479
  SimpleStringBuilder builder(result_size + 1);
480 481 482 483 484 485
  builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
  if (decimal_pos > 0) builder.AddCharacter('.');
  builder.AddSubstring(decimal_buffer, decimal_pos);
  return builder.Finalize();
}

486

487
// ES6 18.2.4 parseFloat(string)
488 489 490 491 492 493 494 495 496 497 498 499 500 501
double StringToDouble(UnicodeCache* unicode_cache, Handle<String> string,
                      int flags, double empty_string_val) {
  Handle<String> flattened = String::Flatten(string);
  {
    DisallowHeapAllocation no_gc;
    String::FlatContent flat = flattened->GetFlatContent();
    DCHECK(flat.IsFlat());
    if (flat.IsOneByte()) {
      return StringToDouble(unicode_cache, flat.ToOneByteVector(), flags,
                            empty_string_val);
    } else {
      return StringToDouble(unicode_cache, flat.ToUC16Vector(), flags,
                            empty_string_val);
    }
502 503 504 505
  }
}


dcarney's avatar
dcarney committed
506 507 508 509 510
bool IsSpecialIndex(UnicodeCache* unicode_cache, String* string) {
  // Max length of canonical double: -X.XXXXXXXXXXXXXXXXX-eXXX
  const int kBufferSize = 24;
  const int length = string->length();
  if (length == 0 || length > kBufferSize) return false;
511
  uint16_t buffer[kBufferSize];
dcarney's avatar
dcarney committed
512 513 514
  String::WriteToFlat(string, buffer, 0, length);
  // If the first char is not a digit or a '-' or we can't match 'NaN' or
  // '(-)Infinity', bailout immediately.
515
  int offset = 0;
dcarney's avatar
dcarney committed
516 517 518 519 520 521 522 523 524
  if (!IsDecimalDigit(buffer[0])) {
    if (buffer[0] == '-') {
      if (length == 1) return false;  // Just '-' is bad.
      if (!IsDecimalDigit(buffer[1])) {
        if (buffer[1] == 'I' && length == 9) {
          // Allow matching of '-Infinity' below.
        } else {
          return false;
        }
525
      }
dcarney's avatar
dcarney committed
526 527 528 529 530 531 532 533
      offset++;
    } else if (buffer[0] == 'I' && length == 8) {
      // Allow matching of 'Infinity' below.
    } else if (buffer[0] == 'N' && length == 3) {
      // Match NaN.
      return buffer[1] == 'a' && buffer[2] == 'N';
    } else {
      return false;
534 535
    }
  }
dcarney's avatar
dcarney committed
536 537 538 539 540 541 542
  // Expected fast path: key is an integer.
  static const int kRepresentableIntegerLength = 15;  // (-)XXXXXXXXXXXXXXX
  if (length - offset <= kRepresentableIntegerLength) {
    const int initial_offset = offset;
    bool matches = true;
    for (; offset < length; offset++) {
      matches &= IsDecimalDigit(buffer[offset]);
543
    }
dcarney's avatar
dcarney committed
544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559
    if (matches) {
      // Match 0 and -0.
      if (buffer[initial_offset] == '0') return initial_offset == length - 1;
      return true;
    }
  }
  // Slow path: test DoubleToString(StringToDouble(string)) == string.
  Vector<const uint16_t> vector(buffer, length);
  double d = StringToDouble(unicode_cache, vector, NO_FLAGS);
  if (std::isnan(d)) return false;
  // Compute reverse string.
  char reverse_buffer[kBufferSize + 1];  // Result will be /0 terminated.
  Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer));
  const char* reverse_string = DoubleToCString(d, reverse_vector);
  for (int i = 0; i < length; ++i) {
    if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false;
560 561 562
  }
  return true;
}
563 564
}  // namespace internal
}  // namespace v8