hexFolder returns the wrong value for 27 exactly-representable hex literals near 2^53

[gilramir]

Version: 3.0.0
File: src/Compiler/Parse/Number.gren, hexFolder (all three branches)
Severity: silent wrong answer — the literal parses, and means a different number

Explanation

hexFolder accumulates hex digits with

16 * acc + charCode - 48        -- '0'-'9'         
16 * acc + 10 + charCode - 65   -- 'A'-'F'                                  
16 * acc + 10 + charCode - 97   -- 'a'-'f'

Each of these adds the raw character code to the accumulator and subtracts
the offset afterwards. The intermediate is therefore up to 65 larger than the
value being built, so for literals just below 2^53 it crosses into the range
where float64 has a spacing of 2, gets rounded, and the trailing subtraction
cannot undo the rounding.

27 hex literals that are exactly representable as float64 — the parser can
and should return them — come back off by one.

This is the same bug class as
core#134 (String.toInt, which
this module uses for decimal literals). That one is a separate fix; this
module needs its own.

Reproduction

module Main exposing (main)                                
                                    
import Node       
import Stream
import Task                                                            
import String.Parser.Advanced as Parser
import Compiler.Parse.Number as PN
import Compiler.Parse.Context as Context


show : String -> String
show src =
    let
        got =
            when Parser.run PN.parser Context.empty src is
                Ok (PN.Hex n) ->
                    String.fromInt n

                Ok (PN.Integer n) ->
                    String.fromInt n

                _ ->
                    "??"
    in
    src ++ " parses as " ++ got

main : Node.SimpleProgram a
main =
    Node.defineSimpleProgram <| \env ->
        [ show "0x1FFFFFFFFFFFD1"
        , show "0x1FFFFFFFFFFFCA"
        , show "0x1FFFFFFFFFFFFF"
        , show "0x1FFFFFFFFFFFCB"
        , show "0xFFFFFFFFFF"
        ]
            |> String.join "\n"
            |> (\s -> Stream.writeLineAsBytes s env.stdout)
            |> Task.onError (\_ -> Task.succeed env.stdout)
            |> Node.endSimpleProgram

Actual output (gren 0.6.6, compiler-common 3.0.0, core 7.4.2, node 22):

0x1FFFFFFFFFFFD1 parses as 9007199254740944      <-- wrong, should be ...945
0x1FFFFFFFFFFFCA parses as 9007199254740939      <-- wrong, should be ...938
0x1FFFFFFFFFFFFF parses as 9007199254740991
0x1FFFFFFFFFFFCB parses as 9007199254740939
0xFFFFFFFFFF parses as 1099511627775

Why it happens

Building 0x1FFFFFFFFFFFD1, the last iteration has
acc = 0x1FFFFFFFFFFFD = 562949953421309 and charCode = 49 (the character
'1'):

step	value	exact in float64?
16 * acc	9007199254740944	yes (< 2^53)
+ charCode	9007199254740993	no — above 2^53, spacing is 2; rounds to 9007199254740992
- 48	9007199254740944	wrong by 1

Grouped correctly (16 * acc + (charCode - 48)), the intermediate is
9007199254740944 + 1, which is exact.

The A-F branch has the same defect at a different offset: its intermediate is
value + 65 where the digit branch's is value + 48. Since the rounding only
bites when the intermediate is odd, the two branches are affected on
opposite parities — the digit branch on odd values, the A-F branch on even
ones.

Also, 0x1FFFFFFFFFFFFF (2^53 - 1)
works correctly, because it is odd and ends in F, so its intermediate
value + 65 is even and exact.

Affected inputs

All 27, with what they currently parse as:

0x1FFFFFFFFFFFCA = 9007199254740938  ->  9007199254740939
0x1FFFFFFFFFFFCC = 9007199254740940  ->  9007199254740939
0x1FFFFFFFFFFFCE = 9007199254740942  ->  9007199254740943
0x1FFFFFFFFFFFD1 = 9007199254740945  ->  9007199254740944
0x1FFFFFFFFFFFD3 = 9007199254740947  ->  9007199254740948
0x1FFFFFFFFFFFD5 = 9007199254740949  ->  9007199254740948
0x1FFFFFFFFFFFD7 = 9007199254740951  ->  9007199254740952
0x1FFFFFFFFFFFD9 = 9007199254740953  ->  9007199254740952
0x1FFFFFFFFFFFDA = 9007199254740954  ->  9007199254740955
0x1FFFFFFFFFFFDC = 9007199254740956  ->  9007199254740955
0x1FFFFFFFFFFFDE = 9007199254740958  ->  9007199254740959
0x1FFFFFFFFFFFE1 = 9007199254740961  ->  9007199254740960
0x1FFFFFFFFFFFE3 = 9007199254740963  ->  9007199254740964
0x1FFFFFFFFFFFE5 = 9007199254740965  ->  9007199254740964
0x1FFFFFFFFFFFE7 = 9007199254740967  ->  9007199254740968
0x1FFFFFFFFFFFE9 = 9007199254740969  ->  9007199254740968
0x1FFFFFFFFFFFEA = 9007199254740970  ->  9007199254740971
0x1FFFFFFFFFFFEC = 9007199254740972  ->  9007199254740971
0x1FFFFFFFFFFFEE = 9007199254740974  ->  9007199254740975
0x1FFFFFFFFFFFF1 = 9007199254740977  ->  9007199254740976
0x1FFFFFFFFFFFF3 = 9007199254740979  ->  9007199254740980
0x1FFFFFFFFFFFF5 = 9007199254740981  ->  9007199254740980
0x1FFFFFFFFFFFF7 = 9007199254740983  ->  9007199254740984
0x1FFFFFFFFFFFF9 = 9007199254740985  ->  9007199254740984
0x1FFFFFFFFFFFFA = 9007199254740986  ->  9007199254740987
0x1FFFFFFFFFFFFC = 9007199254740988  ->  9007199254740987
0x1FFFFFFFFFFFFE = 9007199254740990  ->  9007199254740991

Everything below 0x1FFFFFFFFFFFCA is correct, and everything above 2^53 - 1 is
out of scope (not representable as float64 at all, so no correct answer exists).

Fix

Normalize each digit before adding it:

--- a/src/Compiler/Parse/Number.gren
+++ b/src/Compiler/Parse/Number.gren
@@ hexFolder
     if charCode >= 48 && charCode <= 57 then
         -- 0-9
-        16 * acc + charCode - 48
+        16 * acc + (charCode - 48)

     else if charCode >= 65 && charCode <= 70 then
         -- A-F
-        16 * acc + 10 + charCode - 65
+        16 * acc + (10 + (charCode - 65))

     else if charCode >= 97 && charCode <= 102 then
         -- a-f
-        16 * acc + 10 + charCode - 97
+        16 * acc + (10 + (charCode - 97))