853525 - Convert much of HTMLInputElement (step handling, validation, some event handling, etc.) to use mozilla::Decimal to avoid many rounding issues with fractional step values

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[Jonathan Watt [:jwatt]]

Our implementation contains lots of sources of rounding error that are making <input type=range> with steps that have fractional values behave so badly that we pretty much can't ship it.

The rounding issues are not unique to the "range" type, but they are much more visible and common for "range" compared to the other types we currently ship because:

 * the values that the user can select are computed, not explicitly specified,
   and may contain fractions

 * the user interface results in the user transitioning through many
   values on the way to the one they want, vastly increasing the number of
   bad results that may be seen by the user

 * the "validity state" code is invoked for "range" and, since "range" is a
   number based type, that code also introduces rounding issues that can
   result in the implementation thinking that range is invalid when it
   shouldn't

One thing that I think we really need to do is to make sure that any calculations that should result in exact values in the decimal number system, do so for range. For example, consider:

  <input type=range min=0 max=1 step=0.01>

Currently, as the user moves the thumb from 0 to 1, they will see numbers along the way that are not a multiple of 0.01. For example, instead of 0.01, at the first step up from 0 the input will be given the value 0.00999999999999999. For 0.01, the significand in IEEE double precision would ideally contain the bit pattern 01000111101011100001 repeated forever, but of course there are only 52 bits for the significand, so it can't represent 0.01 precisely. The worst part is that there are many arithmetic operations have to be carried out to find that 0.01 (or the nearest floating point representation of it) is the next step up from 0. Doing these operations with a floating point number type, it's pretty much unavoidable that compounded rounding error will result in our decimal representation of the step being "off".

There are so many places where rounding error can be introduced into the various aspects of "range", and the calculations are often so involved, that ultimately I don't think we're going to be able to consistently present the correct decimal fractions for a range with fractional steps without using a decimal number type internally.

Comment 1

[Jonathan Watt [:jwatt]]

Attachment: mochitests

This test uses an <input type=range step=0.01 max=1>. Without the upcoming patches, this test will fail in the following cases:

VK_PAGE_UP and VK_PAGE_DOWN will put the element into an error state when the value that should be set is 0.7.

VK_UP/VK_DOWN will put the element into an error state when the value that should be set is 0.29, 0.35, 0.41, 0.47, 0.57, 0.58, 0.59, 0.69, 0.7, 0.82, 0.83, 0.94 or 0.95.

Trying to use stepUp/Down to pass through any of the above values will fail (the value will get stuck at that value and not go any higher/lower because bad rounding will keep knocking it back).

Additionally, the assertion:

###!!! ASSERTION: stepBelow/stepAbove will be wrong: 'deltaToStep > 0', file content/html/content/src/HTMLInputElement.cpp

will be hit running the test. Specifically, when VK_PAGE_UP/VK_PAGE_DOWN should set 0.7 or VK_UP/VK_DOWN should set 0.35, 0.41, 0.69, 0.7, 0.82, 0.83 or 0.95.

Comment 2

[Jonathan Watt [:jwatt]]

Attachment: patch

I've tried very hard to keep the invasiveness of this patch to a minimum, and to avoid changing the code paths for non-range types.

It's only really necessary to do the calculations using Decimal, so I've tried to avoid adding functions such as GetMinimumAsDecimal, GetStepBaseAsDecimal, etc. I was trying to get rid of all the Decimal::fromDouble() calls at one point, but it just got way, way too invasive and messy. I think this is a good compromise. What do you think, mounir?

Comment 3

[Mounir Lamouri (:mounir)]

Comment on attachment 740313 [details] [diff] [review]
patch

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

I don't really like the fact that we have Decimal and double being used at the same time. I think it makes things harder to read. I would prefer if we could only use Decimal so things will be easier. If we need to save the few bits we are wasting in some cases (type!={number,range}), we should change that but for the moment, I do not think we care.

So, could you simply change and rename ::ConvertStringToNumber() and ::GetValueAsDouble() to make them use Decimal instead?

Comment 4

[Mounir Lamouri (:mounir)]

Hopefully, this is going to fix bug 783607 ;)

Comment 5

[Jonathan Watt [:jwatt]]

Attachment: patch

Okay, but that means converting all the step handling code. It's probably better that way actually, but it's more invasive.

Comment 6

[Jonathan Watt [:jwatt]]

Attachment: patch

Cleaned up some more.

(In reply to Mounir Lamouri (:mounir) from comment #4)
> Hopefully, this is going to fix bug 783607 ;)

I see, that's why you wanted me to expand the scope of my changes. Cunning. ;)

Comment 7

[Mounir Lamouri (:mounir)]

Comment on attachment 741296 [details] [diff] [review]
patch

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

r=me with the comments addressed.

I also want Boris to have a look at the patch. He might have some interesting feedback and could give his opinions regarding some of the comments I made.

And also, thanks for doing that, this is great! :)

::: content/html/content/src/HTMLInputElement.cpp
@@ +86,5 @@
>  #include "nsContentUtils.h"
>  #include "mozilla/dom/DirectionalityUtils.h"
>  #include "nsRadioVisitor.h"
>  
> +#include "mozilla/Decimal.h"

No need to include that here, it is included in the header.

@@ +111,5 @@
> +inline NS_HIDDEN_(mozilla::Decimal)
> +NS_floorModulo(mozilla::Decimal x, mozilla::Decimal y)
> +{
> +  return (x - y * (x / y).floor());
> +}

I would prefer if that was adde to nsMathUtil.h instead of living there.
We could also have NS_floorModulo be template based and move to mfbt/MathAlgorithms.h

@@ +1165,5 @@
>  
>    return value.IsEmpty();
>  }
>  
> +static Decimal StringToDecimal(nsAString& aValue)

Can't you add a ::fromAString() method to Decimal? It could be better if it lived there I guess.

@@ +1237,5 @@
>        if (!ParseTime(aValue, &milliseconds)) {
>          return false;
>        }
>  
> +      aResultValue = int32_t(milliseconds);

Why do you need to cast? Decimal will do the conversion for int32_t but not with uint32_t? Sounds weird.

@@ +1375,4 @@
>  {
>    MOZ_ASSERT(DoesValueAsNumberApply(),
>               "ConvertNumberToString is only implemented for types implementing .valueAsNumber");
> +  MOZ_ASSERT(aValue.isFinite(),

isFinite() <==> !NaN && !Infinite ? or just !Infinite ?

@@ +1423,5 @@
>        {
>          // Per spec, we need to truncate |aValue| and we should only represent
>          // times inside a day [00:00, 24:00[, which means that we should do a
>          // modulo on |aValue| using the number of milliseconds in a day (86400000).
> +        uint32_t value = NS_floorModulo(aValue.floor(), 86400000).toDouble();

Why .toDouble()? we actually want something a uint32_t here.

@@ +1710,5 @@
>        value += step;
>      }
>    }
>  
> +  value += step * aStep;

I'm pretty sure that change is not needed ;)

@@ +1719,5 @@
>    if (mType == NS_FORM_INPUT_DATE &&
>        NS_floorModulo(value - GetStepBase(), GetStepScaleFactor()) != 0) {
> +    Decimal validStep = Decimal::fromDouble(
> +                          EuclidLCM<uint64_t>(static_cast<uint64_t>(GetStep().toDouble()),
> +                                              static_cast<uint64_t>(GetStepScaleFactor().toDouble())));

Can't you use EuclidLCM<Decimal>(step, GetStepScaleFactor()) ? Why is this using integers instead? I mean, would the algorithm works the same if you just round the result?

@@ +5629,5 @@
>        // we want a multiple of the step scale factor (1 day) as well as of step.
>        if (mType == NS_FORM_INPUT_DATE) {
> +        step = Decimal::fromDouble(
> +                 EuclidLCM<uint64_t>(static_cast<uint64_t>(step.toDouble()),
> +                                     static_cast<uint64_t>(GetStepScaleFactor().toDouble())));

ditto

::: content/html/content/src/HTMLInputElement.h
@@ +19,5 @@
>  #include "nsHTMLFormElement.h" // for ShouldShowInvalidUI()
>  #include "nsIFile.h"
>  #include "nsIFilePicker.h"
>  #include "nsIContentPrefService2.h"
>  

nit: no need to leave an empty line.

@@ +949,3 @@
>     * @result whether the parsing was successful.
>     */
> +  bool ConvertStringToDecimal(nsAString& aValue, Decimal& aResultValue) const;

You are going to hate me but could you keep ConvertStringToNumber() ? That way, we keep the same name as the specification algorithm and 'Number' isn't a type so it doesn't tell much about the type we expect to get.

@@ +960,5 @@
>     * @return whether the function succeded, it will fail if the current input's
>     *         type is not supported or the number can't be converted to a string
>     *         as expected by the type.
>     */
> +  bool ConvertDecimalToString(Decimal aValue, nsAString& aResultString) const;

ditto

::: content/html/content/test/forms/test_step_attribute.html
@@ +681,5 @@
>          { step: '0.001', value: '15:05:05', min: '00:00', result: true },
>          { step: '0.000001', value: '15:05:05', min: '00:00', result: true },
>          // This value has conversion to double issues.
>          { step: '0.0000001', value: '15:05:05', min: '00:00', result: true,
> +          todo: false },

nit: could you just remove the "todo". it defaults to false.

Comment 8

[Jonathan Watt [:jwatt]]

(In reply to Mounir Lamouri (:mounir) from comment #7)
> @@ +111,5 @@
> > +inline NS_HIDDEN_(mozilla::Decimal)
> > +NS_floorModulo(mozilla::Decimal x, mozilla::Decimal y)
> > +{
> > +  return (x - y * (x / y).floor());
> > +}
> 
> I would prefer if that was adde to nsMathUtil.h instead of living there.
> We could also have NS_floorModulo be template based and move to
> mfbt/MathAlgorithms.h

At least for now, converting it to use templates wouldn't help since we'd still need to write a specialist implementation for Decimal as it requires floor() to be called as a method.

> Can't you add a ::fromAString() method to Decimal? It could be better if it
> lived there I guess.

I'm trying to make as few changes to Decimal as possible, especially changes that can't be upstreamed.

> > +      aResultValue = int32_t(milliseconds);
> 
> Why do you need to cast? Decimal will do the conversion for int32_t but not
> with uint32_t? Sounds weird.

It has a ctor taking int32_t, and another private ctor taking double. The compiler prefers the double version, but that doesn't work since it's private.

> isFinite() <==> !NaN && !Infinite ? or just !Infinite ?

isFinite() <==> !NaN && !Infinite

> > +        uint32_t value = NS_floorModulo(aValue.floor(), 86400000).toDouble();
> 
> Why .toDouble()? we actually want something a uint32_t here.

It's the only conversion to a built-in type that's offered.

> > +  value += step * aStep;
> 
> I'm pretty sure that change is not needed ;)

It is. ;) (step won't implicitly convert to int32_t, but aStep will implicitly convert to Decimal.)

> Can't you use EuclidLCM<Decimal>(step, GetStepScaleFactor()) ?

It wouldn't be safe to use EuclidLCM<Decimal>() without explicitly making sure the arguments are rounded. I could round, but Decimal::round() rounds half away from zero, whereas the old code's conversion of double to a uint64_t meant that it would truncate any fractional part. I'd rather change this as a follow-up I think, but I'll take a look.

Comment 9

[Jonathan Watt [:jwatt]]

(In reply to Jonathan Watt [:jwatt] from comment #8)
> Can't you use EuclidLCM<Decimal>(step, GetStepScaleFactor()) ?

On reflection, both the step and the step scale factor will be positive, so I can just call .floor() on them and keep the behavior unchanged.

Comment 10

[Jonathan Watt [:jwatt]]

Attachment: patch [r=mounir]

Comment 11

[Mounir Lamouri (:mounir)]

Jonathan, I think it would be good to fix some issues in Decimal implementation instead of trying to workaround them in HTMLInputElement. Otherwise, I'm afraid that those issues will never be fixed :( The fact that we have to play with some types (int32_t vs uint32_t, double vs int32_t, a * b vs b * a) seems a bit buggy to me.

Comment 12

[Jonathan Watt [:jwatt]]

Sure, I'm upstreaming patches to do exactly those sorts of things. The a * b vs b * a thing was not on my list, but I'll add it.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 741485 [details] [diff] [review]
patch [r=mounir]

r=me, for what it's worth; I have nothing to really add to the bug comments except to strongly agree that calling EuclidLCM on non-integers can easily cause you to have a bad time depending on your precision....

Comment 14

[Jonathan Watt [:jwatt]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/c35ac9704caa
https://hg.mozilla.org/integration/mozilla-inbound/rev/47057b236b1a

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/c35ac9704caa
https://hg.mozilla.org/mozilla-central/rev/47057b236b1a