Simplify use of FOR_EACH_TAIL

* 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 (Bug#25605).

3 files changed, 33 insertions, 23 deletions

diff --git a/src/data.c b/src/data.c
index 8e07bf01b44..12dc2df0bac 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 ac7c1f265a4..4de74a5967f 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 a9011b4a8be..102e8bd70ef 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,
@@ -4585,20 +4586,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.  */