[m-rev.] Check for overflow in string.base_string_to_int for base 10

[Ralph Becket]

Estimated hours taken: 0.5
Branches: main

Only check for overflow when converting strings to ints when the base is 10.
Other number bases are assumed to denote bit patterns and no overflow test
is employed.

NEWS:
	Mention the change.

library/string.m:
	Amend accumulate_int to perform an overflow check on base 10 numbers.

tests/general/Mmakefile:
tests/general/test_string_to_int_overflow.m:
tests/general/test_string_to_int_overflow.exp:
	Add a test case.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.502
diff -u -r1.502 NEWS
--- NEWS	30 Jan 2009 03:51:43 -0000	1.502
+++ NEWS	2 Feb 2009 02:40:56 -0000
@@ -33,6 +33,12 @@
 * A new module, parsing_utils, has been added to provide support for
   implementing recursive descent parsers.
 
+* The string.to_int familiy of predicates now fails (or throws an exception
+  for the det_ versions) on base 10 numbers that do not fit in the range
+  [int.min_int+1, int.max_int].  Numbers outside this range lead to overflow.
+  Numbers not in base 10 are assumed to denote bit patterns and are not
+  checked for overflow.
+
 * We have added extra modes to many of the fold style predicates in the
   library in order to better support (mostly-)unique accumulators.
 
Index: library/string.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/string.m,v
retrieving revision 1.278
diff -u -r1.278 string.m
--- library/string.m	29 Jan 2009 06:55:12 -0000	1.278
+++ library/string.m	1 Feb 2009 23:10:27 -0000
@@ -306,6 +306,7 @@
 
     % As above, but fail instead of throwing an exception if the
     % list contains a null character.
+    %
 :- pred string.semidet_from_char_list(list(char)::in, string::uo) is semidet.
 
     % Same as string.from_char_list, except that it reverses the order
@@ -323,12 +324,14 @@
 
     % Converts a signed base 10 string to an int; throws an exception
     % if the string argument does not match the regexp [+-]?[0-9]+
+    % or the number is not in the range [int.min_int+1, int.max_int].
     %
 :- func string.det_to_int(string) = int.
 
     % Convert a string to an int. The string must contain only digits,
     % optionally preceded by a plus or minus sign. If the string does
-    % not match this syntax, string.to_int fails.
+    % not match this syntax or the number is not in the range
+    % [int.min_int+1, int.max_int], string.to_int fails.
     %
 :- pred string.to_int(string::in, int::out) is semidet.
 
@@ -336,13 +339,15 @@
     % must contain one or more digits in the specified base, optionally
     % preceded by a plus or minus sign. For bases > 10, digits 10 to 35
     % are represented by the letters A-Z or a-z. If the string does not match
-    % this syntax, the predicate fails.
+    % this syntax or the base is 10 and the number is not in the range
+    % [int.min_int+1, int.max_int], the predicate fails.
     %
 :- pred string.base_string_to_int(int::in, string::in, int::out) is semidet.
 
     % Converts a signed base N string to an int; throws an exception
     % if the string argument is not precisely an optional sign followed by
-    % a non-empty string of base N digits.
+    % a non-empty string of base N digits and, if the base is 10, the number
+    % is in the range [int.min_int+1, int.max_int].
     %
 :- func string.det_base_string_to_int(int, string) = int.
 
@@ -944,9 +949,11 @@
 
 :- pred accumulate_int(int::in, char::in, int::in, int::out) is semidet.
 
-accumulate_int(Base, Char, N, (Base * N) + M) :-
+accumulate_int(Base, Char, N0, N) :-
     char.digit_to_int(Char, M),
-    M < Base.
+    M < Base,
+    N = (Base * N0) + M,
+    ( N0 =< N ; Base \= 10 ).           % Fail on overflow for base 10 numbers.
 
 % It is important to inline string.index and string.index_det.
 % so that the compiler can do loop invariant hoisting
Index: tests/general/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/general/Mmakefile,v
retrieving revision 1.57
diff -u -r1.57 Mmakefile
--- tests/general/Mmakefile	28 Jan 2009 07:19:42 -0000	1.57
+++ tests/general/Mmakefile	2 Feb 2009 02:34:38 -0000
@@ -68,6 +68,7 @@
 		string_test_2 \
 		string_to_float \
 		test_parsing_utils \
+		test_string_to_int_overflow \
 		test_univ \
 		unreachable \
 		unsafe_uniqueness
Index: tests/general/test_string_to_int_overflow.exp
===================================================================
RCS file: tests/general/test_string_to_int_overflow.exp
diff -N tests/general/test_string_to_int_overflow.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/general/test_string_to_int_overflow.exp	2 Feb 2009 02:34:19 -0000
@@ -0,0 +1 @@
+[yes, no, yes, yes]
Index: tests/general/test_string_to_int_overflow.m
===================================================================
RCS file: tests/general/test_string_to_int_overflow.m
diff -N tests/general/test_string_to_int_overflow.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/general/test_string_to_int_overflow.m	2 Feb 2009 02:34:03 -0000
@@ -0,0 +1,41 @@
+%-----------------------------------------------------------------------------%
+% test_string_to_int_overflow.m
+% Ralph Becket <rafe at csse.unimelb.edu.au>
+% Mon Feb  2 13:29:05 EST 2009
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%
+%-----------------------------------------------------------------------------%
+
+:- module test_string_to_int_overflow.
+
+:- interface.
+
+:- import_module io.
+
+
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module bool.
+:- import_module list.
+:- import_module string.
+
+%-----------------------------------------------------------------------------%
+
+main(!IO) :-
+    Xs = [
+        ( if string.to_int("999", _) then yes else no ),
+        ( if string.to_int("99999999999999999999", _) then yes else no ),
+        ( if string.base_string_to_int(16, "ffffffffff", _) then yes else no ),
+        ( if string.base_string_to_int(10, "999", _) then yes else no )
+    ],
+    io.print(Xs, !IO),
+    io.nl(!IO).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------