Last Comment Bug 653153 - parseInt fast-path can cause incorrect results
: parseInt fast-path can cause incorrect results
Status: RESOLVED FIXED
[fixed-in-tracemonkey]
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Paul Biggar
:
:
Mentors:
Depends on:
Blocks: es5
  Show dependency treegraph
 
Reported: 2011-04-27 09:46 PDT by Jan de Mooij [:jandem]
Modified: 2011-05-10 15:14 PDT (History)
11 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Fix interpreter (WIP) (202 bytes, patch)
2011-05-03 15:42 PDT, Paul Biggar
no flags Details | Diff | Splinter Review
Fix interpreter (WIP) (1.32 KB, patch)
2011-05-03 15:43 PDT, Paul Biggar
no flags Details | Diff | Splinter Review
Fix the tracer too (3.54 KB, patch)
2011-05-04 11:30 PDT, Paul Biggar
jwalden+bmo: review+
n.nethercote: feedback+
Details | Diff | Splinter Review

Description Jan de Mooij [:jandem] 2011-04-27 09:46:51 PDT
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] 2011-04-27 09:59:31 PDT
evilpie confirmed that IE9 also returns 3 for parseInt(3e100).
Comment 2 Paul Biggar 2011-05-03 11:23:39 PDT
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 2011-05-03 15:42:10 PDT
Created attachment 529860 [details] [diff] [review]
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 2011-05-03 15:43:32 PDT
Created attachment 529861 [details] [diff] [review]
Fix interpreter (WIP)

Forgot to qrefresh.
Comment 5 Paul Biggar 2011-05-04 11:30:04 PDT
Created attachment 530094 [details] [diff] [review]
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 [:njn] 2011-05-04 17:20:42 PDT
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] (remove +bmo to email) 2011-05-06 15:21:01 PDT
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 9 Chris Leary [:cdleary] (not checking bugmail) 2011-05-10 15:14:28 PDT
cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/adc31247ace4

Note You need to log in before you can comment on or make changes to this bug.