Re: m4_for

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Akim Demaille on 8/27/2008 1:14 PM:
> 
>> I haven't tried to build the candidates/make-symbol branch, but I suppose
>> I can look into this further.  Do you know which macro is looping
>> infinitely?  A quick 'git grep m4_shiftn origin/candidates/make-symbol'
>> didn't turn up any use of m4_shiftn outside of m4sugar.
> 
> It's the other way round: change the shift3 in b4_symbol_variant into
> a shiftn, and then it loops for ever.  If you pass --trace=m4:
> 
>  tests/bison --trace=m4 examples/variant.yy
> 
> then, starting at lalr1.cc:1037 you have an endless expansion.
> Partial log attached.
> 
> Here is the beginning of the repeated pattern:
> 
> m4trace:/Users/akim/src/urbi/2.0/bison/_build/i386-apple-darwin9.4.0/../../data/lalr1.cc:1037:
> -1- id 15482: _m4_shiftn([3], [[yytype]], [[yysym.value]], [[template
> destroy]]) -> ???

> 
> At a first glance, it seems that there is a for-loop with incorrect
> bounds:
> 
> m4trace:/Users/akim/src/urbi/2.0/bison/_build/i386-apple-darwin9.4.0/../../data/lalr1.cc:1037:
> -2- id 15485: _m4_for([_m4_s], [5], [4], [1], [[,]m4_dquote([$]_m4_s)])
> -> ???

Yep.  Classic off-by-one error.  m4_shiftn validated that $1 < $#, but I
neglected to realize that $# includes $1, which is not part of the
argument list being shifted.  In the case where $1==$#-1 (such as in
m4_shiftn(3,1,2,3)), the m4 1.4.x version was indeed calling _m4_for with
inverted bounds, leading to a loop that will exhaust all memory.  I'm
committing this to autoconf, then resyncing autoconf to bison.

Fortunately, it is not only safer to use m4_shift3(...) than
m4_shiftn(3,...), but faster too.  m4_shiftn has a lot of overhead,
particularly for small n and large argument lists.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAki2D94ACgkQ84KuGfSFAYDOUQCgjty6uRbOEm3vZSCwRvxrWwj6
aM0An3vFv6ZexeefLU/BwrE9uHY53/ee
=JU1r
-----END PGP SIGNATURE-----

>From d0098d52bcde4a46ed187145e21dccd362f638fc Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Wed, 27 Aug 2008 20:30:25 -0600
Subject: [PATCH] Fix off-by-one bug in _m4_shiftn.

* lib/m4sugar/foreach.m4 (_m4_shiftn): Handle case when shifting
all arguments.
* tests/m4sugar.at (M4 loops): Test it.
Reported by Akim Demaille.

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

diff --git a/ChangeLog b/ChangeLog
index 0aa373c..d627af0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2008-08-27  Eric Blake  <address@hidden>
+
+       Fix off-by-one bug in _m4_shiftn.
+       * lib/m4sugar/foreach.m4 (_m4_shiftn): Handle case when shifting
+       all arguments.
+       * tests/m4sugar.at (M4 loops): Test it.
+       Reported by Akim Demaille.
+
 2008-08-26  Eric Blake  <address@hidden>
 
        Improve INSTALL formatting.
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 80f333d..bfad301 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -215,9 +215,9 @@ m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$$1], [$$2]))]])
 #   ,[$5],[$6],...,[$m]_m4_popdef([_m4_s])
 # before calling m4_shift(_m4_s($@)).
 m4_define([_m4_shiftn],
-[m4_define([_m4_s],
+[m4_if(m4_incr([$1]), [$#], [], [m4_define([_m4_s],
           m4_pushdef([_m4_s])_m4_for([_m4_s], m4_eval([$1 + 2]), [$#], [1],
-  [[,]m4_dquote([$]_m4_s)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])
+  [[,]m4_dquote([$]_m4_s)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])])
 
 # m4_do(STRING, ...)
 # ------------------
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 75c5057..89109c6 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -698,6 +698,9 @@ g], [ myvar|])
 myvar
 dnl only one side effect expansion, prior to visiting list elements
 m4_foreach([i], [[1], [2], [3]m4_errprintn([hi])], [m4_errprintn(i)])dnl
+dnl shifting forms an important part of loops
+m4_shift3:m4_shift3(1,2,3):m4_shift3(1,2,3,4)
+m4_shiftn(3,1,2,3):m4_shiftn(3,1,2,3,4)
 ]],
 [[ 1 2 3
  1 2 3
@@ -731,18 +734,20 @@ m4_foreach([i], [[1], [2], [3]m4_errprintn([hi])], 
[m4_errprintn(i)])dnl
 | f|
  a| b| c,| d,e| f| g|
 outer value
+::4
+:4
 ]], [[hi
 1
 2
 3
 ]])
 
+dnl bounds checking in m4_for
 AT_DATA_M4SUGAR([script.4s],
 [[m4_init
 m4_divert([0])dnl
 m4_for([myvar], 1, 3,-1, [ myvar])
 ]])
-
 AT_CHECK_M4SUGAR([], 1, [],
 [[script.4s:3: error: assert failed: -1 > 0
 script.4s:3: the top level
@@ -754,7 +759,6 @@ AT_DATA_M4SUGAR([script.4s],
 m4_divert([0])dnl
 m4_for([myvar], 1, 2, 0, [ myvar])
 ]])
-
 AT_CHECK_M4SUGAR([], 1, [],
 [[script.4s:3: error: assert failed: 0 > 0
 script.4s:3: the top level
@@ -766,13 +770,24 @@ AT_DATA_M4SUGAR([script.4s],
 m4_divert([0])dnl
 m4_for([myvar], 2, 1, 0, [ myvar])
 ]])
-
 AT_CHECK_M4SUGAR([], 1, [],
 [[script.4s:3: error: assert failed: 0 < 0
 script.4s:3: the top level
 autom4te: m4 failed with exit status: 1
 ]])
 
+dnl m4_shiftn also does bounds checking
+AT_DATA_M4SUGAR([script.4s],
+[[m4_init
+m4_divert([0])dnl
+m4_shiftn(3,1,2)
+]])
+AT_CHECK_M4SUGAR([], 1, [],
+[[script.4s:3: error: assert failed: 0 < 3 && 3 < 3
+script.4s:3: the top level
+autom4te: m4 failed with exit status: 1
+]])
+
 AT_CLEANUP
 
 
-- 
1.6.0