[m-rev.] for review: fix a bug in the string to int and uint overflow checks

[Julien Fischer]

For review by anyone.

We can almost certainly do better for the common bases performance-wise (and
likely the generic case as well). I will look into doing that separately.

-------------

Fix a bug in string to int and uint overflow checks.

The overflow checks for string to int and string to uint conversion are
incorrect. Those predicates produce an incorrect result for input strings
that should have failed due to overflow.

The problem is in the predicate accumulate_int/4 (and the equivalent predicates
for the negative int and unsigned int cases). This predicate processes a single
character of the input string, building up the integer value in an accumulator.
After we update the accumulator, we do a check for overflow, as per the last
line of the following:

    :- pred accumulate_int(int::in, char::in, int::in, int::out) is semidet.

    accumulate_int(Base, Char, N0, N) :-
        char.unsafe_base_digit_to_int(Base, Char, M),
        N = (Base * N0) + M,
        % Fail on overflow.
        N0 =< N.

The issue here is that the overflow check carried out by the last line
is not sufficient to detect the situation where calculating N overflows
and then wraps around to a point where the overflow check succeeds.

For example, with 32-bit ints consider the input string "5368709120" (in the
base 10 case). At the last step of the conversion loop, we have N0 = 536870912
and the final digit '0'. The true value of (10 * 536870912) + 0 is 5368709120,
which does not fit in 32 bits. The multiplication wraps around, giving N =
1073741824.  Since 536870912 =< 1073741824, the overflow check succeeds, and
the conversion incorrectly returns 1073741824 instead of failing.

The old check detects an overflow only if N wraps around to a value below N0.
The fix is to check that (Base * N0) + M does not exceed max_int.
That is:

    N0 =< (max_int - M) // Base

The negative integer and unsigned integer cases are similar, with one
subtlety: the check for the negative case requires division to truncate
towards zero. Using flooring division would fail to detect some overflows.

library/string.m:
    Fix the overflow checks in string to int and uint conversion as above.

tests/general/test_string_to_int_overflow.{m,exp*}:
    Add regression tests for the broken overflow check.

tests/hard_coded/Mmakefile:
tests/hard_coded/string_to_uint_overflow.{m,exp*}:
    Add a test for string to uint overflow.

Julien.

diff --git a/library/string.m b/library/string.m
index b2909f2a9..47d599f62 100644
--- a/library/string.m
+++ b/library/string.m
@@ -6035,10 +6035,10 @@ base_positive_int_accumulator(Base) = Pred :-

 accumulate_int(Base, Char, N0, N) :-
     char.unsafe_base_digit_to_int(Base, Char, M),
-    N = (Base * N0) + M,
-    % Fail on overflow.
-    % XXX depends on undefined behaviour
-    N0 =< N.
+    % Fail if Base * N0 + M would exceed max_int.
+    % The division is safe since our caller sets Base to be in 2..36.
+    N0 =< (max_int - M) `unchecked_quotient` Base,
+    N = (Base * N0) + M.

 :- func base_negative_int_accumulator(int) = pred(char, int, int).
 :- mode base_negative_int_accumulator(in) = out(pred(in, in, out) is semidet)
@@ -6067,10 +6067,13 @@ base_negative_int_accumulator(Base) = Pred :-

 accumulate_negative_int(Base, Char, N0, N) :-
     char.unsafe_base_digit_to_int(Base, Char, M),
-    N = (Base * N0) - M,
-    % Fail on overflow.
-    % XXX depends on undefined behaviour
-    N =< N0.
+    % Fail if Base * N0 - M would be less than min_int.
+    % We must use truncating division in the following check.
+    % Flooring division (i.e. div) causes the test to succeed
+    % for values of N0 for which the multiplication overflows.
+    % The division is safe since our caller sets Base to be in 2..36.
+    N0 >= (min_int + M) `unchecked_quotient` Base,
+    N = (Base * N0) - M.

 %---------------------%

@@ -6124,10 +6127,11 @@ base_uint_accumulator(Base) = Pred :-

 accumulate_uint(Base, BaseInt, Char, N0, N) :-
     char.unsafe_base_digit_to_int(BaseInt, Char, M),
-    N = (Base * N0) + uint.det_from_int(M),
-    % Fail on overflow.
-    % XXX depends on undefined behaviour
-    N0 =< N.
+    MU = uint.det_from_int(M),
+    % Fail if Base * N0 + MU would exceed max_uint.
+    % The division is safe since our caller sets Base to be in 2..36.
+    N0 =< (max_uint - MU) `unchecked_quotient` Base,
+    N = (Base * N0) + MU.

 %---------------------%

diff --git a/tests/general/test_string_to_int_overflow.exp
b/tests/general/test_string_to_int_overflow.exp
index e63fd6345..0e238b425 100644
--- a/tests/general/test_string_to_int_overflow.exp
+++ b/tests/general/test_string_to_int_overflow.exp
@@ -32,3 +32,24 @@ no
 no
 no
 no
+--------
+no
+no
+no
+no
+no
+no
+no
+no
+--------
+no
+no
+no
+no
+no
+no
+no
+no
+--------
+no
+no
diff --git a/tests/general/test_string_to_int_overflow.exp2
b/tests/general/test_string_to_int_overflow.exp2
index 0396465cf..25ab020e7 100644
--- a/tests/general/test_string_to_int_overflow.exp2
+++ b/tests/general/test_string_to_int_overflow.exp2
@@ -32,3 +32,24 @@ no
 no
 -9223372036854775808
 no
+--------
+no
+no
+no
+no
+no
+no
+no
+no
+--------
+5368709120
+-5368709120
+5368709120
+-5368709120
+5368709120
+-5368709120
+4474497024
+-4474497024
+--------
+no
+-2147483650
diff --git a/tests/general/test_string_to_int_overflow.m
b/tests/general/test_string_to_int_overflow.m
index 9ba787582..012c890a1 100644
--- a/tests/general/test_string_to_int_overflow.m
+++ b/tests/general/test_string_to_int_overflow.m
@@ -20,8 +20,6 @@

 :- implementation.

-:- import_module list.
-:- import_module maybe.
 :- import_module string.

 %---------------------------------------------------------------------------%
@@ -34,6 +32,7 @@ main(!IO) :-

     line(!IO),

+    % Boundary values for 32-bit integers.
     test(base_string_to_int(10, "2147483647"), !IO),
     test(base_string_to_int(10, "2147483648"), !IO),
     test(base_string_to_int(10, "-2147483648"), !IO),
@@ -41,6 +40,7 @@ main(!IO) :-

     line(!IO),

+    % Boundary values for 64-bit integers.
     test(base_string_to_int(10, "9223372036854775807"), !IO),
     test(base_string_to_int(10, "9223372036854775808"), !IO),
     test(base_string_to_int(10, "-9223372036854775808"), !IO),
@@ -72,15 +72,56 @@ main(!IO) :-
     test(base_string_to_int(36, "1Y2P0IJ32E8E7"), !IO),
     test(base_string_to_int(36, "1Y2P0IJ32E8E8"), !IO),
     test(base_string_to_int(36, "-1Y2P0IJ32E8E8"), !IO),
-    test(base_string_to_int(36, "-1Y2P0IJ32E8E9"), !IO).
+    test(base_string_to_int(36, "-1Y2P0IJ32E8E9"), !IO),

-:- pred test(pred(T), io, io).
-:- mode test(pred(out) is semidet, di, uo) is det.
+    line(!IO),
+
+    % Regression tests for incorrect overflow check. For each of these
+    % values, processing the final digit overflows by 2^63 or more
+    % (2^31 on 32-bit platforms), so the wrapped-around result has the
+    % same sign as the accumulator and lies beyond it. The old overflow
+    % check (N0 =< N) therefore failed to detect the overflow. (Smaller
+    % overflows wrap to a value of the opposite sign, which the old
+    % check did detect.)
+    %
+    % There are no cases for base 2, because none exist. With base 2 the
+    % magnitude of the result of processing one digit is less than twice
+    % the magnitude of the accumulator, so an overflowing result always
+    % lands in the opposite-sign range that the old check detected.
+
+    % Overflow check regression tests for 64-bit ints.
+    test(base_string_to_int(10, "23058430092136939520"), !IO),
+    test(base_string_to_int(10, "-23058430092136939520"), !IO),
+    test(base_string_to_int(16, "14000000000000000"), !IO),
+    test(base_string_to_int(16, "-14000000000000000"), !IO),
+    test(base_string_to_int(8, "2400000000000000000000"), !IO),
+    test(base_string_to_int(8, "-2400000000000000000000"), !IO),
+    test(base_string_to_int(36, "5000000000000"), !IO),
+    test(base_string_to_int(36, "-5000000000000"), !IO),
+
+    line(!IO),
+
+    % Overflow check regression tests for 32-bit ints.
+    test(base_string_to_int(10, "5368709120"), !IO),
+    test(base_string_to_int(10, "-5368709120"), !IO),
+    test(base_string_to_int(16, "140000000"), !IO),
+    test(base_string_to_int(16, "-140000000"), !IO),
+    test(base_string_to_int(8, "50000000000"), !IO),
+    test(base_string_to_int(8, "-50000000000"), !IO),
+    test(base_string_to_int(36, "2200000"), !IO),
+    test(base_string_to_int(36, "-2200000"), !IO),
+
+    line(!IO),
+
+    % Check truncating division is used in overflow checks.
+    test(base_string_to_int(10, "-9223372036854775810"), !IO),
+    test(base_string_to_int(10, "-2147483650"), !IO).
+
+:- pred test(pred(T)::in(pred(out) is semidet), io::di, io::uo) is det.

 test(P, !IO) :-
     ( if P(X) then
-        io.write(X, !IO),
-        io.nl(!IO)
+        io.write_line(X, !IO)
     else
         io.write_string("no\n", !IO)
     ).
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index 2e0855ef4..feb11639e 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -436,6 +436,7 @@ ORDINARY_PROGS = \
  string_switch_3 \
  string_switch_4 \
  string_to_float_overflow \
+ string_to_uint_overflow \
  string_various \
  string_well_formed \
  string_well_formed_utf8 \
diff --git a/tests/hard_coded/string_to_uint_overflow.exp
b/tests/hard_coded/string_to_uint_overflow.exp
new file mode 100644
index 000000000..745b326e8
--- /dev/null
+++ b/tests/hard_coded/string_to_uint_overflow.exp
@@ -0,0 +1,22 @@
+0u
+1u
+999u
+no
+--------
+4294967294u
+4294967295u
+no
+--------
+no
+no
+no
+--------
+no
+no
+no
+no
+--------
+no
+no
+no
+no
diff --git a/tests/hard_coded/string_to_uint_overflow.exp2
b/tests/hard_coded/string_to_uint_overflow.exp2
new file mode 100644
index 000000000..673b74b3f
--- /dev/null
+++ b/tests/hard_coded/string_to_uint_overflow.exp2
@@ -0,0 +1,22 @@
+0u
+1u
+999u
+no
+--------
+4294967294u
+4294967295u
+4294967296u
+--------
+18446744073709551614u
+18446744073709551615u
+no
+--------
+no
+no
+no
+no
+--------
+5368709120u
+5368709120u
+5368709120u
+8589934591u
diff --git a/tests/hard_coded/string_to_uint_overflow.m
b/tests/hard_coded/string_to_uint_overflow.m
new file mode 100644
index 000000000..28961fb38
--- /dev/null
+++ b/tests/hard_coded/string_to_uint_overflow.m
@@ -0,0 +1,94 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+%
+% Test the overflow behaviour of string.to_uint/2.
+%
+% The .exp file is for when uint is 32-bit.
+% The .exp2 file is for when uint is 64-bit.
+%
+%---------------------------------------------------------------------------%
+
+:- module string_to_uint_overflow.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+    test(string.to_uint("0"), !IO),
+    test(string.to_uint("1"), !IO),
+    test(string.to_uint("999"), !IO),
+    test(string.to_uint("99999999999999999999"), !IO),
+
+    line(!IO),
+
+    % Boundary values for 32-bit unsigned integers.
+    test(base_string_to_uint(10, "4294967294"), !IO), % One under.
+    test(base_string_to_uint(10, "4294967295"), !IO), % Boundary.
+    test(base_string_to_uint(10, "4294967296"), !IO), % One over.
+
+    line(!IO),
+
+    % Boundary values for 64-bit unsigned integers.
+    test(base_string_to_uint(10, "18446744073709551614"), !IO), % One under.
+    test(base_string_to_uint(10, "18446744073709551615"), !IO), % Boundary.
+    test(base_string_to_uint(10, "18446744073709551616"), !IO), % One over.
+
+    line(!IO),
+
+    % Regression tests for incorrect overflow check. For each of these
+    % values, processing the final digit wraps past 2^64 (2^32 on 32-bit
+    % platforms) and back to a value that is not below the accumulator,
+    % so the old overflow check (N0 =< N) failed to detect the overflow.
+    %
+    % The base 2 tests are max_uint followed by one more 1 digit:
+    % the true value 2 * max_uint + 1 wraps to exactly max_uint, passing
+    % the old check. This is the only case in base 2 that the old check
+    % fails to detect.
+
+    % Overflow check regression tests for 64-bit uints.
+    test(base_string_to_uint(10, "23058430092136939520"), !IO),
+    test(base_string_to_uint(16, "14000000000000000"), !IO),
+    test(base_string_to_uint(8, "2400000000000000000000"), !IO),
+    test(base_string_to_uint(2,
+        "11111111111111111111111111111111" ++
+        "111111111111111111111111111111111"), !IO),
+
+    line(!IO),
+
+    % Overflow check regression tests for 32-bit uints.
+    test(base_string_to_uint(10, "5368709120"), !IO),
+    test(base_string_to_uint(16, "140000000"), !IO),
+    test(base_string_to_uint(8, "50000000000"), !IO),
+    test(base_string_to_uint(2, "111111111111111111111111111111111"), !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred test(pred(T)::in(pred(out) is semidet), io::di, io::uo) is det.
+
+test(P, !IO) :-
+    ( if P(X) then
+        io.write_line(X, !IO)
+    else
+        io.write_string("no\n", !IO)
+    ).
+
+:- pred line(io::di, io::uo) is det.
+
+line(!IO) :-
+    io.write_string("--------\n", !IO).
+
+%---------------------------------------------------------------------------%
+:- end_module string_to_uint_overflow.
+%---------------------------------------------------------------------------%