Re: m4_reverse

[Eric Blake]

Eric Blake <ebb9 <at> byu.net> writes:

> In the process of testing it, I discovered that the current m4_list_cmp
> implementation on an m4_reverse'd list was tricky enough to foil the
> current m4 branch-1.6 heuristics on whether $@ recursion is occurring:
> behavior broke down into quadratic time because the m4_cdr calls hid the
> lists to the point that m4 failed to create back-references and ended up
> reparsing the list on every iteration.  This patch includes a rewrite of
> m4_list_cmp to skip m4_cdr and make the $@ recursion explicit to the
> current m4 (although I might still try to patch m4 to recognize the
> admittedly corner-case recursion pattern); in addition to giving linear
> instead of quadratic behavior, it also reduces m4_list_cmp from 17 to 15
> macros per iteration.

My rewrite was asymmetric - m4_list_cmp([lots of 0], [0]) was fast, but 
m4_list_cmp([0], [lots of 0]) was slow.  m4 still couldn't see through the 
deferred m4_shift in _m4_list_cmp_1, so this fixes it (but requires 16 macros 
per iteration).

From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 08:28:01 -0600
Subject: [PATCH] One more m4_list_cmp tweak.

* lib/m4sugar/m4sugar.m4 (_m4_list_cmp_1): Don't defer shift.
* lib/m4sugar/foreach.m4 (m4_list_cmp): Fix comment.
* tests/m4sugar.at (recursion): Test both directions of list
disparity.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    6 ++++++
 lib/m4sugar/foreach.m4 |    4 ++--
 lib/m4sugar/m4sugar.m4 |    2 +-
 tests/m4sugar.at       |   10 ++++++++++
 4 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 7019f37..877eb28 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2008-07-29  Eric Blake  <address@hidden>
 
+       One more m4_list_cmp tweak.
+       * lib/m4sugar/m4sugar.m4 (_m4_list_cmp_1): Don't defer shift.
+       * lib/m4sugar/foreach.m4 (m4_list_cmp): Fix comment.
+       * tests/m4sugar.at (recursion): Test both directions of list
+       disparity.
+
        Add m4_reverse, and improve m4_list_cmp.
        * lib/m4sugar/m4sugar.m4 (m4_reverse): New macro.
        (m4_list_cmp): Rewrite to give linear behavior with M4 1.6 on an
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 7cc4358..1b5d2f9 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -212,8 +212,8 @@ m4_define([m4_joinall],
 # trailing +0 is necessary to handle a missing list.  Next, create a
 # temporary macro to perform pairwise comparisons until an inequality
 # is found.  For example, m4_list_cmp([1], [1,2]) creates _m4_cmp as
-#   m4_if([($1) != ($3)], [1], [m4_cmp([$1], [$3])],
-#         [($2) != ($4)], [1], [m4_cmp([$2], [$4])],
+#   m4_if(m4_eval([($1) != ($3)]), [1], [m4_cmp([$1], [$3])],
+#         m4_eval([($2) != ($4)]), [1], [m4_cmp([$2], [$4])],
 #         [0]_m4_popdef([_m4_cmp], [_m4_size]))
 # then calls _m4_cmp([1+0], [0], [1], [2+0])
 m4_define([m4_list_cmp],
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 54439ce..a605947 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -2169,7 +2169,7 @@ m4_define([_m4_list_cmp],
 [m4_if([$1], [], [0m4_ignore], [$2], [0], [m4_unquote], [$2m4_ignore])])
 
 m4_define([_m4_list_cmp_1],
-[_m4_list_cmp_2([$2], [m4_shift2($@)], $1)])
+[_m4_list_cmp_2([$2], m4_dquote(m4_shift2($@)), $1)])
 
 m4_define([_m4_list_cmp_2],
 [_m4_list_cmp([$1$3], m4_cmp([$3+0], [$1+0]))(
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index c69e37e..2b73188 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -778,6 +778,8 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
 m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
 m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
   m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
+m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
+m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
 m4_divert_pop(0)
@@ -790,6 +792,8 @@ AT_CHECK_M4SUGAR([-o-], [0], [[48894
 10000
 end
 0
+0
+0
 ]])
 
 AT_DATA_M4SUGAR([script.4s],
@@ -802,6 +806,8 @@ AT_DATA_M4SUGAR([script.4s],
 10000
 end
 0
+0
+0
 m4_exit([0])])
 m4_init
 m4_divert_push(0)[]dnl
@@ -815,6 +821,8 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
 m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
 m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
   m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
+m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
+m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
 m4_divert_pop(0)
@@ -827,6 +835,8 @@ AT_CHECK_M4SUGAR([-o-], [0], [[48894
 10000
 end
 0
+0
+0
 ]])
 
 AT_CLEANUP
-- 
1.5.6.4