flatten*: fix two bugs.

* lib.c (lazy_flatten_scan): Fix a problem which results
in cases like (()), ((())) ...  to incorrectly flatten
to (nil).  The do loop in this function which iteratively
descends into a nested left-nesting of a list does not handle
all cases, and therefore the function may not return at that
point. Removing the return fixes the problem, but so does
removing the loop so that in that case we just descend one
level into the nested list, and continue in the main loop.
What is incorrect is that when the consp(a) test fails and the
do loop terminates, we need to distinguish the cases off
a being an atom versus nil. Continuing in the loop does that.
This bug was spotted by a reviewer in the comp.lang.c
Usenet newsgroup.
(lazy_flatten): We neglect  to handle the case here that
the input is an empty list, resulting in (flatten* nil)
returning (nil) rather than nil. The flatten function
is correct.

* tests/012/seq.tl: New tests.

* txr.1: Documentation improved. In particular, these
functions don't handle improper lists. Also, it needs
to be documented that the argument may be an atom.

3 files changed, 86 insertions, 14 deletions

diff --git a/lib.c b/lib.c
index 8d0317c7..0fd695a5 100644
--- a/lib.c
+++ b/lib.c
@@ -3666,12 +3666,11 @@ static val lazy_flatten_scan(val list, val *escape)
         list = cdr(list);
       } else if (atom(a)) {
         return list;
-      } else do {
+      } else {
         push(cdr(list), escape); /* safe mutation: *escape is a local var */
         list = a;
         a = car(list);
-      } while (consp(a));
-      return list;
+      }
     } else if (*escape) {
       list = pop(escape);
     } else {
@@ -3698,7 +3697,9 @@ static val lazy_flatten_func(val lcons)
 
 val lazy_flatten(val list)
 {
-  if (atom(list)) {
+  if (list == nil) {
+    return nil;
+  } if (atom(list)) {
     return cons(list, nil);
   } else {
     val escape = nil;
diff --git a/tests/012/seq.tl b/tests/012/seq.tl
index df5ce065..9aa61148 100644
--- a/tests/012/seq.tl
+++ b/tests/012/seq.tl
@@ -564,4 +564,60 @@
   [separate-keys evenp (vec-list (range 1 20)) square] (#(4 16 36 64 100 144 196 256 324 400)
                                                         #(1 9 25 49 81 121 169 225 289 361)))
 
-
+(mtest
+  (flatten '()) ()
+  (flatten '(nil)) ()
+  (flatten '(a)) (a)
+  (flatten '(a b)) (a b)
+  (flatten '(nil b)) (b)
+  (flatten '(a nil)) (a)
+
+  (flatten '((nil))) ()
+  (flatten '((a))) (a)
+  (flatten '((a) (b))) (a b)
+  (flatten '((nil) (b))) (b)
+  (flatten '((a) (nil))) (a)
+
+  (flatten '((a b))) (a b)
+  (flatten '((nil b))) (b)
+  (flatten '((a nil))) (a)
+
+  (flatten '(((())))) nil
+  (flatten '(((())) a)) (a)
+  (flatten '(((()) a))) (a)
+  (flatten '(((() a)))) (a)
+  (flatten '((((a))))) (a)
+
+  (flatten 3) (3)
+  (flatten '(1 . 2)) :error
+  (flatten '(1 2 . 3)) :error
+  (flatten '(1 (2 . 3))) :error)
+
+(mtest
+  (flatten* '()) ()
+  (flatten* '(nil)) ()
+  (flatten* '(a)) (a)
+  (flatten* '(a b)) (a b)
+  (flatten* '(nil b)) (b)
+  (flatten* '(a nil)) (a)
+
+  (flatten* '((nil))) ()
+  (flatten* '((a))) (a)
+  (flatten* '((a) (b))) (a b)
+  (flatten* '((nil) (b))) (b)
+  (flatten* '((a) (nil))) (a)
+
+  (flatten* '((a b))) (a b)
+  (flatten* '((nil b))) (b)
+  (flatten* '((a nil))) (a)
+
+  (flatten* '(((())))) nil
+  (flatten* '(((())) a)) (a)
+  (flatten* '(((()) a))) (a)
+  (flatten* '(((() a)))) (a)
+  (flatten* '((((a))))) (a)
+
+  (flatten* 3) (3)
+  (lforce (flatten* '(1 . 2))) :error
+  (lforce (flatten* '(1 2 . 3))) :error
+  (lforce (flatten* '(1 (2 . 3)))) :error)
diff --git a/txr.1 b/txr.1
index e47a1dd8..dc316434 100644
--- a/txr.1
+++ b/txr.1
@@ -23103,27 +23103,40 @@ operation: no
 
 .coNP Functions @ flatten and @ flatten*
 .synb
-.mets (flatten << list )
-.mets (flatten* << list )
+.mets (flatten >> { list | << atom })
+.mets (flatten* >> { list | << atom })
 .syne
 .desc
 The
 .code flatten
-function produces a list whose elements are all of the
+function recursively traverses a nested
+.metn list ,
+returning a list whose elements are all of the
 .cod2 non- nil
-atoms contained in the structure of
-.metn list .
+atoms contained in
+.metn list ,
+at any level of nesting.
+If the argument is an
+.meta atom
+rather than a
+.metn list ,
+then it is returned.
+Otherwise, the
+.meta list
+argument must be a proper list, as must all lists
+nested within it.
 
 The
 .code flatten*
-function
-works like
-.code flatten
+function calculates the same result as
+.codn flatten ,
 except that it produces a lazy list. It can be used to lazily flatten an
-infinite lazy structure.
+infinite lazy list.
 
 .TP* Examples:
 .verb
+  (flatten 42) -> 42
+
   (flatten '(1 2 () (3 4))) -> (1 2 3 4)
 
   ;; equivalent to previous, since
@@ -23133,6 +23146,8 @@ infinite lazy structure.
   (flatten nil) -> nil
 
   (flatten '(((()) ()))) -> nil
+
+  (flatten '(a (b . c))) -> ;; error
 .brev
 
 .coNP Functions @ flatcar and @ flatcar*