bug#25605: [DRAFT PATCH 1/2] Simplify use of FOR_EACH_TAIL

[Paul Eggert]

* src/data.c (circular_list): New function.
* src/lisp.h (FOR_EACH_TAIL): Use Brent’s algorithm and C99 for-loop
decl, to eliminate the need for the args TAIL, TORTOISE and N, and
to speed things up a bit on typical hosts with optimization.
All uses changed.
---
 src/data.c |  6 ++++++
 src/fns.c  | 16 +++++++---------
 src/lisp.h | 34 ++++++++++++++++++++--------------
 3 files changed, 33 insertions(+), 23 deletions(-)

diff --git a/src/data.c b/src/data.c
index 8e07bf0..12dc2df 100644
--- a/src/data.c
+++ b/src/data.c
@@ -170,6 +170,12 @@ args_out_of_range_3 (Lisp_Object a1, Lisp_Object a2, 
Lisp_Object a3)
   xsignal3 (Qargs_out_of_range, a1, a2, a3);
 }
 
+void
+circular_list (Lisp_Object list)
+{
+  xsignal1 (Qcircular_list, list);
+}
+
 
 /* Data type predicates.  */
 
diff --git a/src/fns.c b/src/fns.c
index ac7c1f2..4de74a5 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1544,25 +1544,23 @@ list.
 Write `(setq foo (delq element foo))' to be sure of correctly changing
 the value of a list `foo'.  See also `remq', which does not modify the
 argument.  */)
-  (register Lisp_Object elt, Lisp_Object list)
+  (Lisp_Object elt, Lisp_Object list)
 {
-  Lisp_Object tail, tortoise, prev = Qnil;
-  bool skip;
+  Lisp_Object prev = Qnil;
 
-  FOR_EACH_TAIL (tail, list, tortoise, skip)
+  FOR_EACH_TAIL (list)
     {
-      Lisp_Object tem = XCAR (tail);
+      Lisp_Object tem = XCAR (li.tail);
       if (EQ (elt, tem))
        {
          if (NILP (prev))
-           list = XCDR (tail);
+           list = XCDR (li.tail);
          else
-           Fsetcdr (prev, XCDR (tail));
+           Fsetcdr (prev, XCDR (li.tail));
        }
       else
-       prev = tail;
+       prev = li.tail;
     }
-  CHECK_LIST_END (tail, list);
   return list;
 }
 
diff --git a/src/lisp.h b/src/lisp.h
index 1ac3816..2d74d44 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3317,6 +3317,7 @@ extern struct Lisp_Symbol *indirect_variable (struct 
Lisp_Symbol *);
 extern _Noreturn void args_out_of_range (Lisp_Object, Lisp_Object);
 extern _Noreturn void args_out_of_range_3 (Lisp_Object, Lisp_Object,
                                           Lisp_Object);
+extern _Noreturn void circular_list (Lisp_Object);
 extern Lisp_Object do_symval_forwarding (union Lisp_Fwd *);
 enum Set_Internal_Bind {
   SET_INTERNAL_SET,
@@ -4586,20 +4587,25 @@ enum
         Lisp_String))                                                  \
      : make_unibyte_string (str, len))
 
-/* Loop over all tails of a list, checking for cycles.
-   FIXME: Make tortoise and n internal declarations.
-   FIXME: Unroll the loop body so we don't need `n'.  */
-#define FOR_EACH_TAIL(hare, list, tortoise, n) \
-  for ((tortoise) = (hare) = (list), (n) = true;               \
-       CONSP (hare);                                           \
-       (hare = XCDR (hare), (n) = !(n),                                \
-       ((n)                                                    \
-        ? (EQ (hare, tortoise)                                 \
-           ? xsignal1 (Qcircular_list, list)                   \
-           : (void) 0)                                         \
-        /* Move tortoise before the next iteration, in case */ \
-        /* the next iteration does an Fsetcdr.  */             \
-        : (void) ((tortoise) = XCDR (tortoise)))))
+/* Loop over tails of LIST, checking for dotted lists and cycles.
+   In the loop body, ‘li.tail’ is the current cons; the name ‘li’ is
+   short for “list iterator”.  The expression LIST may be evaluated
+   more than once, and so should not have side effects.  The loop body
+   should not modify the list’s top level structure other than by
+   perhaps deleting the current cons.
+
+   Use Brent’s teleporting tortoise-hare algorithm.  See:
+   Brent RP. BIT. 1980;20(2):176-84. doi:10.1007/BF01933190
+   http://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf  */
+
+#define FOR_EACH_TAIL(list)                                            \
+  for (struct { Lisp_Object tail, tortoise; intptr_t n, max; } li      \
+        = { list, list, 2, 2 };                                        \
+       CONSP (li.tail) || (CHECK_LIST_END (li.tail, list), false);     \
+       (li.tail = XCDR (li.tail),                                      \
+       (li.n-- == 0                                                    \
+        ? (void) (li.n = li.max <<= 1, li.tortoise = li.tail)          \
+        : EQ (li.tail, li.tortoise) ? circular_list (list) : (void) 0)))
 
 /* Do a `for' loop over alist values.  */
 
-- 
2.9.3