653153 - parseInt fast-path can cause incorrect results

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Consider this:

js> parseInt("3e100")
3
js> parseInt(3e100)
3e+100

Both should return 3 per ES5 15.1.2.2 step 1. Opera and Safari have the same problem but it works correctly in V8. V8 has the same fast-path but they first check whether the number is in range.

Comment 1

[Jan de Mooij [:jandem]]

evilpie confirmed that IE9 also returns 3 for parseInt(3e100).

Comment 2

[Paul Biggar]

If I understand this correctly, we should always be converting 3e100 into a string, and then parsing it. parseInt will then find the 'e' and end the string there.

We have a fast-path which says "if it's already a double, just use the double value". So this breaks when String(x) gets an 'e' in it, which seems to occur where the exponent is greater than 20. So the solution is to add bounds checks to the fast path.

v8 adds those checks to its fastpath, but I don't understand why it chose these values:

        ((0.01 < string && string < 1e9) ||
            (-1e9 < string && string < -0.01)))

Comment 3

[Paul Biggar]

Attachment: Fix interpreter (WIP)

This fixes the interpreter, but the test case found a bug in the tracejit, which I have yet to investigate.

Comment 4

[Paul Biggar]

Attachment: Fix interpreter (WIP)

Forgot to qrefresh.

Comment 5

[Paul Biggar]

Attachment: Fix the tracer too

A nicer way to fix this, from the tracer side, would be to retry outside the range. I believe we can't retry with doubles, only fail, so this'll have to do.

Is the comment clear enough here?

Comment 6

[Nicholas Nethercote [inactive]]

Comment on attachment 530094 [details] [diff] [review]
Fix the tracer too

Review of attachment 530094 [details] [diff] [review]:

Seems ok to me, but I defer to Waldo on nit-picky spec issues like this.

::: js/src/jsnum.cpp
@@ +509,3 @@
 {
+    /* Fast path - see comment in numParseInt. */
+    if (d < 1e21 && d > -1e21)

That's a confusing way to write that condition.  Swapping the conjuncts would be clearer.  This would be even clearer:

  (-1e21 < d && d < 1e21)

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 530094 [details] [diff] [review]
Fix the tracer too

Review of attachment 530094 [details] [diff] [review]:
-----------------------------------------------------------------

My head hurts now.  But at least this bug's done hurting it!

::: js/src/jit-test/tests/basic/bug653153.js
@@ +11,5 @@
> +for (var i in arr) {
> +    print (arr[i]);
> +    assertEq(parseInt( arr[i]), parseInt(String( arr[i])));
> +    assertEq(parseInt(-arr[i]), parseInt(String(-arr[i])));
> +}

Testing of a range of values like this is all well and good.  But I think it would be good to have, and perform, very explicit testing of the exact boundaries.  So let's add something like this (tested in an old xulrunner that I think doesn't have the optimization that introduced this bug, but not tested in a shell with this patch, so please double-check these tests all work before pushing):

/*
 * Boundary testing for super-large positive numbers between non-exponential
 * and in-exponential-form.
 *
 * NB: While 1e21 is exactly representable as an IEEE754 double-precision
 * number, its nearest neighboring representable values are a good distance
 * away, 65536 to be precise.
 */
assertEq(parseInt(1e21 - 65537) > 1e20, true);

assertEq(1e21 - 65537 !== 1e21 - 65536, true);
assertEq(parseInt(1e21 - 65536), 1);

assertEq(1e21 - 65536, 1e21);
assertEq(parseInt(1e21), 1);

assertEq(1e21 + 65535, 1e21);
assertEq(1e21 + 65536, 1e21);
assertEq(parseInt(1e21 + 65536), 1);

// ES5 leaves exact precision in ToString(bigMagNum) undefined, which
// might make this value inconsistent across implementations (maybe,
// nobody's done the math here).  Regardless, it's definitely a number
// very close to 1, and not a large-magnitude positive number.
assertEq(1e21 + 65537 !== 1e21, true);
assertEq(parseInt(1e21 + 65537) < 1.001, true);


/*
 * Now do the same tests for super-large negative numbers crossing the
 * opposite boundary.
 */

assertEq(parseInt(-1e21 + 65537) < -1e20, true);

assertEq(-1e21 + 65537 !== -1e21 + 65536, true);
assertEq(parseInt(-1e21 + 65536), -1);

assertEq(-1e21 + 65536, -1e21);
assertEq(parseInt(-1e21), -1);

assertEq(-1e21 - 65535, -1e21);
assertEq(-1e21 - 65536, -1e21);
assertEq(parseInt(-1e21 - 65536), -1);

// ES5 leaves exact precision in ToString(bigMagNum) undefined, which
// might make this value inconsistent across implementations (maybe,
// nobody's done the math here).  Regardless, it's definitely a number
// very close to -1, and not a large-magnitude negative number.
assertEq(-1e21 - 65537 !== 1e21, true);
assertEq(parseInt(-1e21 - 65537) > -1.001, true);

::: js/src/jsnum.cpp
@@ +435,5 @@
> +         * 1e21, ToString(string) is in the form "xEy". 'E' marks the end of
> +         * the word, which would mean the result of parseInt(string) should be |x|.
> +         *
> +         * To preserve this behaviour, we can't use the fast-path when string >
> +         * 1e21, or else the result would be |xEy|.

Make that NeM -- ToString uses 'e', not 'E' -- throughout the comment.

@@ +439,5 @@
> +         * 1e21, or else the result would be |xEy|.
> +         */
> +        if (vp[2].isDouble() &&
> +            vp[2].toDouble() < 1.0e21 &&
> +            vp[2].toDouble() > -1.0e21) {

So this suggests that ParseIntDoubleHelper now has vestigial code to handle !JSDOUBLE_IS_FINITE.  Add an assertion at the beginning of ParseIntDoubleHelper that its input d is |-1e21 < d < 1e21|, and remove that code, please.  (The other option would be to make ParseIntDoubleHelper indicate whether it could or couldn't convert, then handle failure by falling into slow-path code in both users, but I can't bring myself to care about the performance of parseInt(+/-Infinity).  :-)  Plus I've stared at this way too long already.)

@@ +509,3 @@
>  {
> +    /* Fast path - see comment in numParseInt. */
> +    if (d < 1e21 && d > -1e21)

Agreed, (-1e21 < d && d < 1e21) is clearer, please do that.

@@ +511,5 @@
> +    if (d < 1e21 && d > -1e21)
> +        return ParseIntDoubleHelper(d);
> +
> +    /* Slow path - convert to a string and parse normally. */
> +    JSString *inputString = js_ValueToString(cx, DoubleValue(d));

Use the specific-to-doubles js_NumberToString(cx, d) instead.

Comment 8

[Paul Biggar]

http://hg.mozilla.org/tracemonkey/rev/adc31247ace4

Comment 9

[Chris Leary [:cdleary] (not checking bugmail)]

cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/adc31247ace4