[18/18] argv_ref speedup: reuse argv in recursion

[Eric Blake]

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

Next in the series, and mission accomplished!  M4 now performs
arbitrary-depth recursive macro expansion in linear time and space,
regardless of whether $@ appears in isolation or inside single-byte quote
delimiters; compared with the quadratic time and space used by all
released versions of GNU M4 (I also know that BSD m4 is quadratic, while
Solaris m4 has such puny limits on the maximum number of arguments to a
single macro that arbitrary recursion isn't possible).  Multi-byte quote
delimiters unfortunately still require quadratic effort, because of the
semantics of m4 token pasting, but as this is not the common case for
autoconf, I'm not as worried about that.  This patch was surprisingly
small to wrap up my efforts over the past 5 months when Ralf first prodded
me into looking at it.  Basically, when doing recursive macros, a very
common idiom is reusing the first few arguments with the next element of
the tail arguments (as in `$0(`$1', shift(shift($@)))').  This patch
optimizes the idiom, by recognizing that if the current argv includes a
wrapper around a prior argv in the last array slot of grouped arguments,
then the prior argv should be reused rather than creating a nested wrapper
for the current argv.

And since I've basically rewritten the input engine from what it was in M4
1.4.4 (when I first started contributing patches), I'm adding myself as
one of the primary authors in --version output.

However, the argv_ref branch still has more patches that need porting to
head before I declare it closed.  With the framework improvements I added
for linear recursion, I made it possible to process data in FIFO order
(fixing POSIX compliance of m4wrap), to pass builtin tokens transparently
through user macros rather than always flattening to the empty string (as
is done in other m4 implementations), and to process NUL bytes
transparently (as a GNU extension, since POSIX and all other m4
implementations require the input to be a text file).  I will continue
porting those improvements over to head before 1.4.11 is ready for
release; however, I'm debating about doing a beta release of m4 1.4.10b
right now to give the speedups a wider field testing, and ensure I haven't
introduced any accidental regressions.

2008-02-23  Eric Blake  <address@hidden>

        Stage 18: try harder to reuse argv in recursion.
        When pushing arguments that contain an existing $@ ref, reuse the
        ref rather than creating another layer of wrappers.
        Memory impact: noticeable improvement, due to better $@ reuse.
        Speed impact: noticeable improvement, due to O(n^2) to O(n)
        reduction in unboxed recursion.
        * src/macro.c (make_argv_ref_token): Avoid wrapping $@ when
        possible.
        (push_args): Let make_argv_ref_token take care of pending data.
        * doc/m4.texinfo (Improved foreach): Tweak wording to match new
        performance capability.  Add regression tests.
        * NEWS: Document the speedup.
        * src/m4.c (AUTHORS): Claim credit for my rewrite.

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

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

iD8DBQFHv6DT84KuGfSFAYARAgymAJ98iTvPr68leB8P/0XdKS0AMzhR9QCfcOjc
EL7YP5De8BoYWou7BvmJb8E=
=7H42
-----END PGP SIGNATURE-----

>From cfdd338da41015cee1ec0691fae84607d145e2ac Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 22 Feb 2008 19:54:48 -0700
Subject: [PATCH] Stage 18: try harder to reuse argv in recursion.

* m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible.
(m4_push_args): Let make_argv_ref take care of pending data.
* doc/m4.texinfo (Improved foreach): Tweak wording to match new
performance capability.
* tests/others.at (recursion): Add tests to avoid performance
regression.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog       |   15 ++++++++++
 doc/m4.texinfo  |   35 ++++++++++++++++-------
 m4/macro.c      |   83 ++++++++++++++++++++++++++++++------------------------
 tests/others.at |   32 +++++++++++++++++++++
 4 files changed, 117 insertions(+), 48 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 8e55fdb..877cda7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+2008-02-23  Eric Blake  <address@hidden>
+
+       Stage 18: try harder to reuse argv in recursion.
+       When pushing arguments that contain an existing $@ ref, reuse the
+       ref rather than creating another layer of wrappers.
+       Memory impact: noticeable improvement, due to better $@ reuse.
+       Speed impact: noticeable improvement, due to O(n^2) to O(n)
+       reduction in unboxed recursion.
+       * m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible.
+       (m4_push_args): Let make_argv_ref take care of pending data.
+       * doc/m4.texinfo (Improved foreach): Tweak wording to match new
+       performance capability.
+       * tests/others.at (recursion): Add tests to avoid performance
+       regression.
+
 2008-02-22  Eric Blake  <address@hidden>
 
        Update NEWS.
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index ffc1949..909f8e3 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -8406,17 +8406,16 @@ helper method immediately, the 
@samp{defn(address@hidden')} no longer
 contains unexpanded macros.
 
 The astute m4 programmer might notice that the solution above still uses
-more memory, and thus more time, than strictly necessary.  Note that
address@hidden, which contains an arbitrarily long quoted list, is expanded
-and rescanned three times per iteration of @code{_foreachq}.
-Furthermore, every iteration of the algorithm effectively unboxes then
-reboxes the list, which costs a couple of macro invocations.  It is
-possible to rewrite the algorithm for a bit more speed by swapping the
-order of the arguments to @code{_foreachq} in order to operate on an
-unboxed list in the first place, and by using the fixed-length @samp{$#}
-instead of an arbitrary length list as the key to end recursion.  This
-alternative approach is available as
address@hidden@value{VERSION}/@/examples/@/foreach3.m4}:
+more macro invocations than strictly necessary.  Note that @samp{$2},
+which contains an arbitrarily long quoted list, is expanded and
+rescanned three times per iteration of @code{_foreachq}.  Furthermore,
+every iteration of the algorithm effectively unboxes then reboxes the
+list, which costs a couple of macro invocations.  It is possible to
+rewrite the algorithm by swapping the order of the arguments to
address@hidden in order to operate on an unboxed list in the first
+place, and by using the fixed-length @samp{$#} instead of an arbitrary
+length list as the key to end recursion.  This alternative approach is
+available as @address@hidden/@/examples/@/foreach3.m4}:
 
 @comment examples
 @example
@@ -8459,6 +8458,20 @@ foreachq(`x', ``1', `2', `3', `4'', `x
 @result{}4
 @end example
 
+Prior to M4 1.4.11, every instance of @samp{$@@} was rescanned as it was
+encountered.  Thus, the @file{foreachq3.m4} alternative used much less
+memory than @file{foreachq2.m4}, and executed as much as 10% faster,
+since each iteration encountered fewer @samp{$@@}.  However, the
+implementation of rescanning every byte in @samp{$@@} was quadratic in
+the number of bytes scanned (for example, making the broken version in
address@hidden cubic, rather than quadratic, in behavior).  Once the
+underlying M4 implementation was improved in 1.4.11 to reuse results of
+previous scans, both styles of @code{foreachq} become linear in the
+number of bytes scanned, and the difference in timing is no longer
+noticeable; in fact, after the change, the @file{foreachq2.m4} version
+uses slightly less memory since it tracks fewer arguments per macro
+invocation.
+
 For yet another approach, the improved version of @code{foreach},
 available in @address@hidden/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @address@hidden to begin with, using
diff --git a/m4/macro.c b/m4/macro.c
index 0b86018..743d326 100644
--- a/m4/macro.c
+++ b/m4/macro.c
@@ -1081,24 +1081,56 @@ make_argv_ref (m4 *context, m4_symbol_value *value, 
m4_obstack *obs,
 {
   m4__symbol_chain *chain;
 
-  assert (obstack_object_size (obs) == 0);
-  /* TODO reuse $@ even if argv has multiple array slots.  */
-  if (argv->wrapper && argv->arraylen == 1)
-    {
-      assert (argv->array[0]->type == M4_SYMBOL_COMP
-             && argv->array[0]->u.u_c.wrapper);
-      chain= argv->array[0]->u.u_c.chain;
-      assert (!chain->next && chain->type == M4__CHAIN_ARGV
-             && !chain->u.u_a.skip_last);
-      argv = chain->u.u_a.argv;
-      index += chain->u.u_a.index - 1;
-    }
   if (argv->argc <= index)
     return NULL;
+  value->type = M4_SYMBOL_COMP;
+  value->u.u_c.chain = value->u.u_c.end = NULL;
+
+  /* Cater to the common idiom of $0(`$1',shift(shift($@))), by
+     inlining the first few arguments and reusing the original $@ ref,
+     rather than creating another layer of wrappers.  */
+  while (argv->wrapper)
+    {
+      size_t i;
+      for (i = 0; i < argv->arraylen; i++)
+       {
+         if (argv->array[i]->type == M4_SYMBOL_COMP
+             && argv->array[i]->u.u_c.wrapper)
+           break;
+         if (index == 1)
+           {
+             m4__push_arg_quote (context, obs, argv, i + 1, quotes);
+             /* TODO support M4_SYNTAX_COMMA.  */
+             obstack_1grow (obs, ',');
+           }
+         else
+           index--;
+       }
+      assert (i < argv->arraylen);
+      if (i + 1 == argv->arraylen)
+       {
+         assert (argv->array[i]->type == M4_SYMBOL_COMP
+                 && argv->array[i]->u.u_c.wrapper);
+         chain = argv->array[i]->u.u_c.chain;
+         assert (!chain->next && chain->type == M4__CHAIN_ARGV
+                 && !chain->u.u_a.skip_last);
+         argv = chain->u.u_a.argv;
+         index += chain->u.u_a.index - 1;
+       }
+      else
+       {
+         index += i;
+         break;
+       }
+    }
 
+  m4__make_text_link (obs, &value->u.u_c.chain, &value->u.u_c.end);
   chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain);
-  value->type = M4_SYMBOL_COMP;
-  value->u.u_c.chain = value->u.u_c.end = chain;
+  if (value->u.u_c.end)
+    value->u.u_c.end->next = chain;
+  else
+    value->u.u_c.chain = chain;
+  value->u.u_c.end = chain;
   value->u.u_c.wrapper = true;
   value->u.u_c.has_func = argv->has_func;
   chain->next = NULL;
@@ -1591,11 +1623,8 @@ m4_push_args (m4 *context, m4_obstack *obs, 
m4_macro_args *argv, bool skip,
 {
   m4_symbol_value tmp;
   m4_symbol_value *value;
-  m4__symbol_chain *chain;
   size_t i = skip ? 2 : 1;
   const m4_string_pair *quotes = m4_get_syntax_quotes (M4SYNTAX);
-  char *str = NULL;
-  size_t len = obstack_object_size (obs);
 
   if (argv->argc <= i)
     return;
@@ -1606,30 +1635,10 @@ m4_push_args (m4 *context, m4_obstack *obs, 
m4_macro_args *argv, bool skip,
       return;
     }
 
-  /* Since make_argv_ref puts data on obs, we must first close any
-     pending data.  The resulting symbol contents live entirely on
-     obs, so we call push_symbol with a level of -1.  */
-  if (len)
-    {
-      obstack_1grow (obs, '\0');
-      str = (char *) obstack_finish (obs);
-    }
-
   /* TODO allow shift, $@, to push builtins without flatten.  */
   value = make_argv_ref (context, &tmp, obs, -1, argv, i, true,
                         quote ? quotes : NULL);
   assert (value == &tmp);
-  if (len)
-    {
-      chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain);
-      chain->next = value->u.u_c.chain;
-      value->u.u_c.chain = chain;
-      chain->type = M4__CHAIN_STR;
-      chain->quote_age = 0;
-      chain->u.u_s.str = str;
-      chain->u.u_s.len = len;
-      chain->u.u_s.level = SIZE_MAX;
-    }
   if (m4__push_symbol (context, value, -1, argv->inuse))
     arg_mark (argv);
 }
diff --git a/tests/others.at b/tests/others.at
index 0b58c29..fbd692b 100644
--- a/tests/others.at
+++ b/tests/others.at
@@ -332,6 +332,38 @@ AT_CHECK_M4(["$abs_srcdir/null.m4"], [2],
 AT_CLEANUP
 
 
+## --------- ##
+## recursion ##
+## --------- ##
+
+AT_SETUP([recursion])
+
+dnl This input exploits contents of loop.m4 to print out the final value
+dnl of the recursion.
+AT_DATA([in.m4],
+[[define(`debug', `define(`popdef', `divert`'i')')dnl
+include(`loop.m4')dnl
+]])
+
+dnl boxed recursion
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose loop.m4], [0],
+[[ 1 2 3 4 5 6 7 8 9 10
+]])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 loop.m4], [0])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 in.m4], [0], [[10000
+]])
+
+dnl unboxed recursion
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose -Dalt loop.m4], 
[0],
+[[ 1 2 3 4 5 6 7 8 9 10
+]])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 -Dalt loop.m4], [0])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt in.m4], [0], [[10000
+]])
+
+AT_CLEANUP
+
+
 ## ------- ##
 ## reverse ##
 ## ------- ##
-- 
1.5.4

>From 58ffaf13f5206f8bac8ec4ebad8147e99157263d Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Mon, 19 Nov 2007 19:40:49 -0700
Subject: [PATCH] Stage 18: try harder to reuse argv in recursion.

* src/macro.c (make_argv_ref_token): Avoid wrapping $@ when
possible.
(push_args): Let make_argv_ref_token take care of pending data.
* doc/m4.texinfo (Improved foreach): Tweak wording to match new
performance capability.  Add regression tests.
* NEWS: Document the speedup.
* src/m4.c (AUTHORS): Claim credit for my rewrite.

(cherry picked from commit 58d580eeca1f75ddd2ca68d8b93fef6eead14350)

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog      |   16 +++++++++
 NEWS           |    4 ++-
 doc/m4.texinfo |   96 +++++++++++++++++++++++++++++++++++++++++++++++++------
 src/m4.c       |    2 +-
 src/macro.c    |   80 ++++++++++++++++++++++++++--------------------
 5 files changed, 150 insertions(+), 48 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 62c4ad1..1269290 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+2008-02-23  Eric Blake  <address@hidden>
+
+       Stage 18: try harder to reuse argv in recursion.
+       When pushing arguments that contain an existing $@ ref, reuse the
+       ref rather than creating another layer of wrappers.
+       Memory impact: noticeable improvement, due to better $@ reuse.
+       Speed impact: noticeable improvement, due to O(n^2) to O(n)
+       reduction in unboxed recursion.
+       * src/macro.c (make_argv_ref_token): Avoid wrapping $@ when
+       possible.
+       (push_args): Let make_argv_ref_token take care of pending data.
+       * doc/m4.texinfo (Improved foreach): Tweak wording to match new
+       performance capability.  Add regression tests.
+       * NEWS: Document the speedup.
+       * src/m4.c (AUTHORS): Claim credit for my rewrite.
+
 2008-02-22  Eric Blake  <address@hidden>
 
        Stage 17: pass argv through quoted strings.
diff --git a/NEWS b/NEWS
index 31a41c2..8faafcf 100644
--- a/NEWS
+++ b/NEWS
@@ -27,7 +27,9 @@ Version 1.4.11 - ?? ??? 2008, by ????  (git version 1.4.10a-*)
   regular expressions, which speeds up typical Autoconf usage.
 * Enhance the `format' builtin to warn for more suspicious usages, such as
   missing arguments or problems parsing according to the format string.
-* Memory usage is greatly reduced in recursive macros.
+* Enhance the `ifelse' and `shift' builtins so that tail-recursive
+  algorithms based on `$@' operate in linear, rather than quadratic, time
+  and memory.
 * A number of portability improvements inherited from gnulib.
 
 Version 1.4.10 - 09 Jul 2007, by Eric Blake  (CVS version 1.4.9c)
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index 2a549dd..92a8eff 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -7195,17 +7195,17 @@ helper method immediately, the 
@samp{defn(address@hidden')} no longer
 contains unexpanded macros.
 
 The astute m4 programmer might notice that the solution above still uses
-more memory, and thus more time, than strictly necessary.  Note that
address@hidden, which contains an arbitrarily long quoted list, is expanded
-and rescanned three times per iteration of @code{_foreachq}.
-Furthermore, every iteration of the algorithm effectively unboxes then
-reboxes the list, which costs a couple of macro invocations.  It is
-possible to rewrite the algorithm for a bit more speed by swapping the
-order of the arguments to @code{_foreachq} in order to operate on an
-unboxed list in the first place, and by using the fixed-length @samp{$#}
-instead of an arbitrary length list as the key to end recursion.  This
-alternative approach is available as
address@hidden@value{VERSION}/@/examples/@/foreach3.m4}:
+more macro invocations than strictly necessary.  Note that @samp{$2},
+which contains an arbitrarily long quoted list, is expanded and
+rescanned three times per iteration of @code{_foreachq}.  Furthermore,
+every iteration of the algorithm effectively unboxes then reboxes the
+list, which costs a couple of macro invocations.  It is possible to
+rewrite the algorithm by swapping the order of the arguments to
address@hidden in order to operate on an unboxed list in the first
+place, and by using the fixed-length @samp{$#} instead of an arbitrary
+length list as the key to end recursion.  The result is eight macro
+invocations per loop, instead of nine.  This alternative approach is
+available as @address@hidden/@/examples/@/foreach3.m4}:
 
 @comment examples
 @example
@@ -7248,6 +7248,20 @@ foreachq(`x', ``1', `2', `3', `4'', `x
 @result{}4
 @end example
 
+Prior to M4 1.4.11, every instance of @samp{$@@} was rescanned as it was
+encountered.  Thus, the @file{foreachq3.m4} alternative used much less
+memory than @file{foreachq2.m4}, and executed as much as 10% faster,
+since each iteration encountered fewer @samp{$@@}.  However, the
+implementation of rescanning every byte in @samp{$@@} was quadratic in
+the number of bytes scanned (for example, making the broken version in
address@hidden cubic, rather than quadratic, in behavior).  Once the
+underlying M4 implementation was improved in 1.4.11 to reuse results of
+previous scans, both styles of @code{foreachq} become linear in the
+number of bytes scanned, and the difference in timing is no longer
+noticeable; in fact, after the change, the @file{foreachq2.m4} version
+uses slightly less memory since it tracks fewer arguments per macro
+invocation.
+
 For yet another approach, the improved version of @code{foreach},
 available in @address@hidden/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @address@hidden to begin with, using
@@ -7376,6 +7390,66 @@ foreachq(`x', ```active'', ``active''', `<x>
 @result{}<active>
 @end example
 
address@hidden
address@hidden Not worth putting in the manual, but make sure that performance
address@hidden on recursive algorithms is not quadratic.
+
address@hidden boxed recursion
+
address@hidden examples
address@hidden options: -Dlimit=10 -Dverbose
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose}
+include(`loop.m4')dnl
address@hidden 1 2 3 4 5 6 7 8 9 10
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=2500
address@hidden
+$ @kbd {m4 -I examples -Dlimit=2500}
+include(`loop.m4')dnl
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=10000
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10000}
+define(`debug', `define(`popdef',`divert`'i')')
address@hidden
+include(`loop.m4')dnl
address@hidden
address@hidden example
+
address@hidden unboxed recursion
+
address@hidden examples
address@hidden options: -Dlimit=10 -Dverbose -Dalt
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose -Dalt}
+include(`loop.m4')dnl
address@hidden 1 2 3 4 5 6 7 8 9 10
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=2500 -Dalt
address@hidden
+$ @kbd {m4 -I examples -Dlimit=2500 -Dalt}
+include(`loop.m4')dnl
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=10000 -Dalt
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10000 -Dalt}
+define(`debug', `define(`popdef',`divert`'i')')
address@hidden
+include(`loop.m4')dnl
address@hidden
address@hidden example
+
address@hidden ignore
+
 @node Improved cleardivert
 @section Solution for @code{cleardivert}
 
diff --git a/src/m4.c b/src/m4.c
index af4991f..0ace6dc 100644
--- a/src/m4.c
+++ b/src/m4.c
@@ -27,7 +27,7 @@
 
 #include "version-etc.h"
 
-#define AUTHORS "Rene' Seindal"
+#define AUTHORS "Rene' Seindal", "Eric Blake"
 
 static void usage (int);
 
diff --git a/src/macro.c b/src/macro.c
index c0a24c4..32ff62d 100644
--- a/src/macro.c
+++ b/src/macro.c
@@ -1285,24 +1285,55 @@ make_argv_ref_token (token_data *token, struct obstack 
*obs, int level,
 {
   token_chain *chain;
 
-  assert (obstack_object_size (obs) == 0);
-  /* TODO support $@ refs when argv array is larger than 1.  */
-  if (argv->wrapper && argv->arraylen == 1)
-    {
-      assert (TOKEN_DATA_TYPE (argv->array[0]) == TOKEN_COMP
-             && argv->array[0]->u.u_c.wrapper);
-      chain = argv->array[0]->u.u_c.chain;
-      assert (!chain->next && chain->type == CHAIN_ARGV
-             && !chain->u.u_a.skip_last);
-      argv = chain->u.u_a.argv;
-      index += chain->u.u_a.index - 1;
-    }
   if (index >= argv->argc)
     return NULL;
+  TOKEN_DATA_TYPE (token) = TOKEN_COMP;
+  token->u.u_c.chain = token->u.u_c.end = NULL;
 
+  /* Cater to the common idiom of $0(`$1',shift(shift($@))), by
+     inlining the first few arguments and reusing the original $@ ref,
+     rather than creating another layer of wrappers.  */
+  while (argv->wrapper)
+    {
+      unsigned int i;
+      for (i = 0; i < argv->arraylen; i++)
+       {
+         if (TOKEN_DATA_TYPE (argv->array[i]) == TOKEN_COMP
+             && argv->array[i]->u.u_c.wrapper)
+           break;
+         if (index == 1)
+           {
+             push_arg_quote (obs, argv, i + 1, quotes);
+             obstack_1grow (obs, ',');
+           }
+         else
+           index--;
+       }
+      assert (i < argv->arraylen);
+      if (i + 1 == argv->arraylen)
+       {
+         assert (TOKEN_DATA_TYPE (argv->array[i]) == TOKEN_COMP
+                 && argv->array[i]->u.u_c.wrapper);
+         chain = argv->array[i]->u.u_c.chain;
+         assert (!chain->next && chain->type == CHAIN_ARGV
+                 && !chain->u.u_a.skip_last);
+         argv = chain->u.u_a.argv;
+         index += chain->u.u_a.index - 1;
+       }
+      else
+       {
+         index += i;
+         break;
+       }
+    }
+
+  make_text_link (obs, &token->u.u_c.chain, &token->u.u_c.end);
   chain = (token_chain *) obstack_alloc (obs, sizeof *chain);
-  TOKEN_DATA_TYPE (token) = TOKEN_COMP;
-  token->u.u_c.chain = token->u.u_c.end = chain;
+  if (token->u.u_c.end)
+    token->u.u_c.end->next = chain;
+  else
+    token->u.u_c.chain = chain;
+  token->u.u_c.end = chain;
   token->u.u_c.wrapper = true;
   token->u.u_c.has_func = argv->has_func;
   chain->next = NULL;
@@ -1416,8 +1447,6 @@ push_args (struct obstack *obs, macro_arguments *argv, 
bool skip, bool quote)
   unsigned int i = skip ? 2 : 1;
   token_data td;
   token_data *token;
-  char *str = NULL;
-  size_t len = obstack_object_size (obs);
 
   if (i >= argv->argc)
     return;
@@ -1428,29 +1457,10 @@ push_args (struct obstack *obs, macro_arguments *argv, 
bool skip, bool quote)
       return;
     }
 
-  /* Since make_argv_ref_token puts data on obs, we must first close
-     any pending data.  The resulting token contents live entirely on
-     obs, so we call push_token with a level of -1.  */
-  if (len)
-    {
-      obstack_1grow (obs, '\0');
-      str = (char *) obstack_finish (obs);
-    }
   /* TODO allow shift, $@, to push builtins without flatten.  */
   token = make_argv_ref_token (&td, obs, -1, argv, i, true,
                               quote ? &curr_quote : NULL);
   assert (token);
-  if (len)
-    {
-      token_chain *chain = (token_chain *) obstack_alloc (obs, sizeof *chain);
-      chain->next = token->u.u_c.chain;
-      token->u.u_c.chain = chain;
-      chain->type = CHAIN_STR;
-      chain->quote_age = 0;
-      chain->u.u_s.str = str;
-      chain->u.u_s.len = len;
-      chain->u.u_s.level = -1;
-    }
   if (push_token (token, -1, argv->inuse))
     arg_mark (argv);
 }
-- 
1.5.4