469397 - (0.5).toFixed(0) is 0, should be 1

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Adam L. Peller]

In FF3, this expression returns 1.  In FF3b2, it returns 0.  ECMA-262 says it should round up to 1.

(IE has a bug where it returns 0, FWIW, even for 0.9)

Comment 1

[Boris Zbarsky [:bzbarsky]]

As near as I can tell, it switched from 1 to "" during http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=2008-08-06+00%3A00%3A00&enddate=2008-08-07+04%3A00%3A00 and then to 0 during http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=2008-10-14+00%3A00%3A00&enddate=2008-10-15+04%3A00%3A00

Comment 2

[Boris Zbarsky [:bzbarsky]]

Er, that second range should be http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=2008-10-13+00%3A00%3A00&enddate=2008-10-14+04%3A00%3A00

Comment 3

[Boris Zbarsky [:bzbarsky]]

And that second range corresponds to a TM merge.  :(

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

But it does contain bug 459606.

Comment 5

[Boris Zbarsky [:bzbarsky]]

The first range was wrong too.  The correct range is http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=2008-08-05+00%3A00%3A00&enddate=2008-08-06+04%3A00%3A00

Comment 6

[Boris Zbarsky [:bzbarsky]]

OK.  So yeah, the first range contains bug 384244 and the second range contains the bug Blake pointed out.  Those are the two culprits involved.

Comment 7

[Boris Zbarsky [:bzbarsky]]

OK.  So we call dtoa().  We get to line 2917, which does a check for d < 1 (which we have here) and if so scales everything by a factor of 10.  So now d == 5.  Then, because ilim == 0, we do this:

  if (dval(d) > dval(eps))
    goto one_digit;
  if (dval(d) < -dval(eps))
    goto no_digits;
  goto fast_failed;

eps is an epsilon double value, d == 0, so we go to fast_failed.

Then we start doing the bigint computations there and end up in the no_digits case.  In this case ilim == 0, mode == 3.  So to end up there we need to have:

   cmb(b,S = multadd(S,5,0)) <= 0

In this case, b == S as far as I can tell.  Both are 671088640 (after the multadd, that is).

Comment 8

[Brian Crowder]

Attachment: a fix

Would love to have your opinion on this "fix", bz.  It does fix the reported bug, but I am not confident that it's the Right Fix.  (will get a js/src peer to look after you've seen it)

Comment 9

[Boris Zbarsky [:bzbarsky]]

Yikes.  Comment 7 was my first-ever look at this code...

This does sorta seem to make sense, but I only have a very weak idea of what that comparison is trying to do.  I'd have to read much more carefully through all this bigint stuff to make sure it's really the right thing.

Am I really as qualified as we have to do that?  :(  I was kinda hoping someone else had looked at this code a bit more than myself...

Comment 10

[Brian Crowder]

Yeah, Igor knows it pretty well, but since it was fresh in your mind I thought I'd start with you.  He's next.  :)

Comment 11

[Brendan Eich [:brendan]]

bz is the most advanced-degree-holding Mathematician around ;-).

Is the bug in upstream dtoa.c?

/be

Comment 12

[Brian Crowder]

brendan:  That's not clear.  We chose to fix the (0.1).toFixed() bug here, but it's possible we should've fixed it externally.  With the fix we've done here, this bug is revealed (or perhaps our fix causes this bug, in a sense).  I'm not sure; this code is hairy at best.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Attachment: Brain-dump from my reading through this code, including all the review comments I'm about to make

This is only valid for mode == 3, so I really hope that's the only mode we use...

Comment 14

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 353092 [details] [diff] [review]
a fix

>@@ -3132,17 +3132,17 @@ dtoa
> 	if (ilim <= 0 && (mode == 3 || mode == 5)) {
>-		if (ilim < 0 || cmp(b,S = multadd(S,5,0)) <= 0) {
>+		if (ilim < 0 || cmp(b,S = multadd(S,5,0)) < 0) {

OK, I think this part is correct in terms of behavior it produces.  The brain dump I attached is valid for mode 3 or mode 5, and those are the only cases in which we'll hit this code.  Here's the analysis (with some modifications from the brain-dump to make it a bit more correct and readable):

When called, dtoa takes the input double and rewrites it as a rational number with an integral numerator and denominator.  The denominator is a power of 2, and is kept track of by just keeping track of the exponent.  The numerator is kept track of in the Bigint called |b|.

After this, several integers are computed:
ilim: tells us where we're rounding to.  It's set to
      ndigits + ceil(log10(d)) where ndigits is the integer passed to
      toFixed and d is the double involved.  We only care about the
      case ilim == 0 if we're going to hit this code change, which
      means that
      we're rounding to right before the first decimal digit of d.
j: Negative the power of 2 represented by the least significant 1 in
   the mantissa of d.
k: floor(log10(d)).

Now in the comparison above, after the multadd has happened, S is always a power of 5 times some power of 2.  In fact,

  S = 5^{max(s5,0)+1} * 2^{max(s2,0)}

If we label the |b| in that same line as b', then in terms of the original |b| we computed on entry to the function:

  b' = b * 5^{max(b5,0)} * 2^{max(b2,0)}

where b is an integer relatively prime to 2.  To get equality of these two integers, must have b a power of 5, with

   log5(b) + max(b5,0) = max(s5,0) + 1.

Further, we must have max(s2,0) == max(b2,0).  Now there's some manipulation of s2 and b2 before we produce the above formulas, but it consists of adding or subtracting the same integer from both for the most part.  The place where they're really set for our purposes is between line 2818 and line 2835.  Now we have 4 cases to consider:

if (j >= 0 && k >= 0):
  b2 = 0
  s2 = j + k
  b5 = 0
  s5 = k
  So can only get equality if j = k = 0.  Then b5 = s5, so to have
  equality we must have b == 5.  Since j == 0, that means that the
  least significant bit of the mantissa was the 1s bit, which means
  the original double was 5.
if (j >= 0 && k < 0):
  b2 = -k
  s2 = j
  b5 = -k
  s5 = 0
  So can only get equality if j == -k.  Then j > 0.  Since b5,s5 >= 0,
  we must have have b a power of 5, with log5(b) + b5 == s5 + 1.  So
  b == 5^{k + 1}.  But b is an integer, so this only works if k == -1,
  b == 1, j == 1.  Thus d is some power of 2, and since j is negative
  the least significant bit of the mantissa and is 1, the only way we
  can hit this is if d == 0.5.
if (j < 0 && k >= 0):
  b2 = -j
  s2 = k
  b5 = 0
  s5 = k
  So can only get equality if j == -k.  Then k > 0.  Since b5,s5 >= 0,
  we must have b a power of 5, with log5(b) + b5 == s5 + 1.  So
  b == 5^{k + 1}.  Since the least significant bit of the mantissa had
  value 2^{-j} == 2^{k}, the original double had the form 
  5^{k+1} * 2^k = 5*10^k.
if (j < 0 && k < 0):
  b2 = -j - k
  s2 = 0
  Can't get b2 == s2, since b2 > 0, so no equality.

This pretends that we never need to hit the max(0,b2) or max(0,s2), which I think is correct for the cases we care about (in that these quantities should never be negative, even after the adjustments that happen to them after they're set above).

So in all the possible cases where we can get equality we're looking at 5*10^n for some value of n >= -1.  In all cases, ilim == 0, so we're rounding to the digit before the 5, and should come out with 10^{n+1}.  So we want to fall into the one_digit case.

That said, in practice we don't hit this code for things like (5).toFixed(-1) or (50).toFixed(-2).  And those are currently buggy and not fixed by this patch (hence the r-, plus for the reasons below).

To fix those, we need to make a similar adjustment in the "small integer" fast path on line 2993.  Here the analysis is much simpler.  Equality only holds if the passed-in double is a 5 times a power of 10, and we're still rounding to the digit before the 5.  So that compare should be a < instead of a <= as well.

Which of course raises the question of why those are <= to start with.  It looks like dtoa implements the "Round to nearest, ties to even" rounding algorithm for IEEE-754 floats (though it only documents this for its strtod, not for its dtoa).  For example, (6.5).toFixed(0) returns 6 in Gecko trunk, while (7.5).toFixed(0) returns 8.  Given that, (0.5).toFixed(0) should be returning 0 to be consistent.

It looks like ECMA-262 toFixed requires rounding using the "Round to nearest, ties away from zero" IEEE-754 algorithm, at least if I read it correctly, right?

So we could fix this 5*10^n issue pretty easily with these two s/<=/</ changes, but we'd have the general problem of things ending in even digit then 5 not rounding correctly, no?

Comment 15

[Brian Crowder]

Attachment: ECMA compatible dtoa.c fixes

Thanks to bz for lots of help debugging.  I'll ask Graydon for review next.

This patch fixes the following cases.

js> (5).toFixed(-1)
10
js> (0.25).toFixed(1)
0.3
js> (0.5).toFixed()
1
js> (6.5).toFixed()
7

Comment 16

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 355610 [details] [diff] [review]
ECMA compatible dtoa.c fixes

Flag these changes with /* MOZILLA CHANGE */ comments, and looks good.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Oh, and perhaps report to the author that this should be how it works when that define that didn't help is set?

Comment 18

[Brian Crowder]

(In reply to comment #16)
> (From update of attachment 355610 [details] [diff] [review])
> Flag these changes with /* MOZILLA CHANGE */ comments, and looks good.

Unfortunately we already have lots of dtoa.c changes which don't contain flag markers like this.  I'm not sure if adding a handful for this case is useful (might even be misleading).

Comment 19

[Brendan Eich [:brendan]]

Main thing is to try to get correctness fixes upstream. How has that gone in the recent past? I know nit and warning fixes don't fly, but correctness (by some spec or other, we may end up in spec wars) should.

/be

Comment 20

[Boris Zbarsky [:bzbarsky]]

Oh, if we have other changes already then don't worry about the marking.

Brendan, I don't think there's a spec wars issue here that can't be solved with ifdefs.  ;)

Comment 21

[Brian Crowder]

I will try again to communicate with dmg

Comment 22

[Graydon Hoare :graydon]

Comment on attachment 355610 [details] [diff] [review]
ECMA compatible dtoa.c fixes

I'm sorry, this is way beyond my ability to comprehend; I've tried reading the code for an hour now and can't make heads or tails of it. Way, way too much obscure state. Perhaps Igor knows it well enough to say?

Comment 23

[Brian Crowder]

Comment on attachment 355610 [details] [diff] [review]
ECMA compatible dtoa.c fixes

Looking for additional review because of the code's complexity and the fact that our tests in this area seem to be lacking.

Comment 24

[Igor Bukanov]

I will try to review this over the weekend.

Comment 25

[Brian Crowder]

igor:  Review-ping?

Thanks.

Comment 26

[Brian Crowder]

Comment on attachment 355610 [details] [diff] [review]
ECMA compatible dtoa.c fixes

Should've moved review to mrbkap after we discussed on IRC, sorry.  Please give this at least a few minutes of your time, mrbkap?

Comment 27

[Dão Gottwald [:dao]]

http://hg.mozilla.org/mozilla-central/rev/98fe21ddf417
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/6676024a697d

Comment 28

[Brian Crowder]

Thanks, Dao!

Comment 29

[Bob Clary [:bc] (inactive)]

http://hg.mozilla.org/mozilla-central/rev/39080f7278b2

Comment 30

[Bob Clary [:bc] (inactive)]

ecma_3/Number/15.7.4.5-2.js	
v 1.9.1, 1.9.2