[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-75-gcfdd338

[Eric Blake]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU M4 source repository".

http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=cfdd338da41015cee1ec0691fae84607d145e2ac

The branch, master has been updated
       via  cfdd338da41015cee1ec0691fae84607d145e2ac (commit)
       via  ff7e7bf197df21b3e98eb54759ecbc8f8448dc8d (commit)
      from  2cdf327333be152135f021988c8e0eb6f3e10b51 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit cfdd338da41015cee1ec0691fae84607d145e2ac
Author: Eric Blake <address@hidden>
Date:   Fri Feb 22 19:54:48 2008 -0700

    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>

commit ff7e7bf197df21b3e98eb54759ecbc8f8448dc8d
Author: Eric Blake <address@hidden>
Date:   Fri Feb 22 12:57:57 2008 -0700

    Update NEWS.
    
    * NEWS: Document change to __gnu__ on 2008-02-11.
    
    Signed-off-by: Eric Blake <address@hidden>

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog       |   18 ++++++++++++
 NEWS            |   11 ++++++-
 doc/m4.texinfo  |   35 ++++++++++++++++-------
 m4/macro.c      |   83 ++++++++++++++++++++++++++++++------------------------
 tests/others.at |   32 +++++++++++++++++++++
 5 files changed, 129 insertions(+), 50 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index cb6a845..877cda7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,23 @@
+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.
+       * NEWS: Document change to __gnu__ on 2008-02-11.
+
        Stage 17: pass argv through quoted strings.
        Allow the concatenation of $@ references with other text input
        inside quoted contexts, which requires distinguishing between a
diff --git a/NEWS b/NEWS
index 03627a4..ec63ef2 100644
--- a/NEWS
+++ b/NEWS
@@ -1,6 +1,6 @@
 GNU m4 NEWS - History of user-visible changes.         -*- outline -*-
-Copyright (C) 1992, 1993, 1994, 1998, 2000, 2001, 2006, 2007 Free Software
-Foundation, Inc.
+Copyright (C) 1992, 1993, 1994, 1998, 2000, 2001, 2006, 2007, 2008 Free
+Software Foundation, Inc.
 
 * Version beta 1.9b - ???, by ??? (git version 1.9a-*)
 
@@ -134,6 +134,9 @@ promoted to 2.0.
 
 ** Changed behavior of builtins
 
+*** The module identifier builtins, such as `__gnu__', `__m4_version__',
+    and `__unix__', now warn if given arguments.
+
 *** The `builtin' builtin now has a special form, where if the first
     argument is exactly the special token representing defn(`builtin'), the
     expansion is the special token representing the builtin named in the
@@ -204,6 +207,10 @@ promoted to 2.0.
 
 *** Improvements made in the 1.4.x stable series have been incorporated.
 
+* Version 1.4.11 - ?? ??? 2008, by Eric Blake  (git version 1.4.10a)
+
+** FIXME: import NEWS from branch once 1.4.11 is released.
+
 * Version 1.4.10 - 09 Jul 2007, by Eric Blake  (CVS version 1.4.9c)
 
 ** Upgrade from GPL version 2 to GPL version 3 or later.
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 ##
 ## ------- ##


hooks/post-receive
--
GNU M4 source repository