[m-rev.] for review: fix bug in string.split_at_separator

[Peter Wang]

Estimated hours taken: 1
Branches: main

library/string.m:
	Fix an off-by-one bug in string.split_at_separator.  The index in the
	initial call to split_at_separator2 was one past the end of the
	string, which worked in the C backends because strings are NUL
	terminated.

	Rename split_at_separator2 to split_at_separator_2 and make it more
	readable.

tests/hard_coded/string_split.exp:
tests/hard_coded/string_split.m:
	Add a couple of cases which seem more likely to fail with an incorrect
	implementation.

Index: library/string.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/string.m,v
retrieving revision 1.260
diff -u -r1.260 string.m
--- library/string.m	30 May 2007 08:16:08 -0000	1.260
+++ library/string.m	5 Jun 2007 00:36:19 -0000
@@ -4475,30 +4475,34 @@
 
 %------------------------------------------------------------------------------%
 
-string.split_at_separator(DelimPred, InStr) = OutStrs :-
-    Count = string.length(InStr),
-    split_at_separator2(DelimPred, InStr, Count, Count, [], OutStrs).
+string.split_at_separator(DelimP, String) = Substrings :-
+    Len = string.length(String),
+    split_at_separator_2(DelimP, String, Len - 1, Len, [], Substrings).
 
-:- pred split_at_separator2(pred(char)::in(pred(in) is semidet), string::in,
+:- pred split_at_separator_2(pred(char)::in(pred(in) is semidet), string::in,
     int::in, int::in, list(string)::in, list(string)::out) is det.
-split_at_separator2(DelimPred, Str, I, ThisSegEnd, ITail, OTail) :-
-    % Walk Str backwards extending accumulated list of chunks as chars
-    % matching DelimPred are found.
-    ( I < 0 -> % We're at the beginning.
-        ( ThisSegEnd<0 ->
-            OTail = ["" | ITail]
-        ;
-            ThisSeg = string.unsafe_substring(Str, 0, ThisSegEnd+1),
-            OTail = [ThisSeg | ITail]
-        )
+
+split_at_separator_2(DelimP, Str, I, SegEnd, Acc0, Acc) :-
+    % Walk Str backwards extending the accumulated list of chunks as chars
+    % matching DelimP are found.
+    %
+    % Invariant: -1 =< I < length(Str)
+    % SegEnd is one past the last index of the current segment.
+    %
+    ( I < 0 ->
+        % We've reached the beginning of the string.
+        Seg = string.unsafe_substring(Str, 0, SegEnd),
+        Acc = [Seg | Acc0]
     ;
         C = string.unsafe_index(Str, I),
-        ( DelimPred(C) -> % Chop here.
-            ThisSeg = string.unsafe_substring(Str, I+1, ThisSegEnd-I),
-            TTail = [ ThisSeg | ITail ],
-            split_at_separator2(DelimPred, Str, I-1, I-1, TTail, OTail)
-        ; % Extend current segment.
-            split_at_separator2(DelimPred, Str, I-1, ThisSegEnd, ITail, OTail)
+        ( DelimP(C) ->
+            % Chop here.
+            SegStart = I + 1,
+            Seg = string.unsafe_substring(Str, SegStart, SegEnd - SegStart),
+            split_at_separator_2(DelimP, Str, I - 1, I, [Seg | Acc0], Acc)
+        ;
+            % Extend current segment.
+            split_at_separator_2(DelimP, Str, I - 1, SegEnd, Acc0, Acc)
         )
     ).
 
Index: tests/hard_coded/string_split.exp
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/string_split.exp,v
retrieving revision 1.1
diff -u -r1.1 string_split.exp
--- tests/hard_coded/string_split.exp	2 Feb 2007 05:39:58 -0000	1.1
+++ tests/hard_coded/string_split.exp	5 Jun 2007 00:36:19 -0000
@@ -1,3 +1,5 @@
+
+!
 hello:world:how:are:you!
 hello<tab>world<tab>how<tab>are<tab><tab>you!
 user<tab>group<tab>id1<tab>id2
Index: tests/hard_coded/string_split.m
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/string_split.m,v
retrieving revision 1.1
diff -u -r1.1 string_split.m
--- tests/hard_coded/string_split.m	2 Feb 2007 05:39:58 -0000	1.1
+++ tests/hard_coded/string_split.m	5 Jun 2007 00:36:19 -0000
@@ -10,6 +10,14 @@
 
 main(!IO) :-
   io__write_list(
+    split_at_separator(char__is_upper, ""),
+    ":", io__write_string, !IO),
+  io__nl(!IO),
+  io__write_list(
+    split_at_separator(char__is_upper, "!"),
+    ":", io__write_string, !IO),
+  io__nl(!IO),
+  io__write_list(
     split_at_separator(char__is_upper, "helloXworldXhowXareYyou!"),
     ":", io__write_string, !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
--------------------------------------------------------------------------