Re: [PATCH] Support a stack of LINENO values for AS_MESSAGE.

[Eric Blake]

Paolo Bonzini <bonzini <at> gnu.org> writes:

> 2008-10-14  Paolo Bonzini  <bonzini <at> gnu.org>
> 
>       * lib/m4sugar/m4sh.m4 (_AS_ECHO_LOG): If defined, use $as_lineno as
>       the line number emitted to the log file.
>       (AS_LINENO_PUSH, AS_LINENO_POP): New.

Now that this is already applied...

> +m4_defun([AS_LINENO_PUSH], 
> +[dnl No, I am not going to comment on how this works.  The fun is yours.
> +as_lineno=${as_lineno-"$1"} 
as_lineno_stack=as_lineno_stack=$as_lineno_stack])

It is conceivable that some shells might (be taught to) recognize v=${v}text 
(and its variants) as an append, without having to resort to a new operator (at 
any rate, I have successfully taught the future m4 1.6 to recognize
 m4_define([v],m4_defn([v])text)
as an append, without needing to add new syntax).  Prepending necessarily 
triggers quadratic behavior during memory growth (the old string must be copied 
in entirety to its new location, on every growth), while appending can be 
amortized linear given a decent implementation (over-allocate geometrically, so 
that if the next assignment to v looks like an append, you only need modify the 
tail of the existing pointer rather than reallocate and copy).  However, I 
don't know if any current shell actually implements this optimization without a 
new syntax (although I do know that bash added the new syntax of the += 
operator, precisely because of libtool's experience with quadratic append 
behavior).

So, for potential efficiency purposes, should we rewrite this line to use:

as_lineno_stack=$as_lineno_stack=as_lineno_stack

or maybe even write AS_APPEND([var],[text]), which expands to a shell function 
that uses += on bash and traditional appends elsewhere?

> +m4_defun([AS_LINENO_POP],
> +[eval $as_lineno_stack; test "x$as_lineno_stack" = x && AS_UNSET
([as_lineno])])

On the other hand, this efficiency argument is probably moot - even if a shell 
can recognize an append pattern and make it linear, the eval that shrinks the 
variable size will probably still exhibit quadratic behavior by copying the 
entire substring of the old definition back into the new definition on every 
iteration.  And the quadratic nature of this algorithm is only apparent on 
heavily nested code; how deep do you anticipate a typical nesting of the 
as_lineno_stack to reach?

-- 
Eric Blake