Re: m4sugar and m4 1.6, bison

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

According to Ralf Wildenhues on 7/12/2008 12:39 AM:
| * Ralf Wildenhues wrote on Sat, Jul 12, 2008 at 08:11:55AM CEST:
|> So then here's a first prototype for fast m4_append_uniq, completely
|> untested, and would probably need some more-unique separator after $1 in
|> the definition of m4_key.
|
| I'll blame it on lack of coffee...
|
|> # m4_make_macro_name(STRING)
|> # Turn all characters not fitting to be a macro name into '_'.
|> m4_define([m4_make_macro_name],
|> [m4_bpatsubst([$1], [...])dnl
|> ])

GNU m4 allows any character in a macro name (you just have to use indir
and defn to access such macros).  I think your approach can be made to
work without having to introduce m4_make_macro_name, and thus avoid
collisions altogether.  But there is still the matter of how to remove all
the stale macros if the key being appended to is redefined as empty.

|>
|> # m4_append_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
|> m4_define([m4_append_uniq],
|> [m4_pushdef([m4_key], [_$1_[]make_macro_name([$2])])dnl
|> m4_ifdef(m4_key,
|>   [m4_if([m4_defn(m4_key)], [$2],
|
| This is completely ignoring hash key collision.  So, assuming that
| collisions are rare, i.e., usually strings differ not only in characters
| not allowed in a macro name, then the duplicate test here can just reuse
| the one from the version of m4_append_uniq currently in Autoconf.  That
| will probably still give amortized fast check here.  Actually, I guess
| the uniq part is even O(n), only the reallocs necessary now and then
| will be loglinear.

Linear, actually - the check for whether a macro is defined is amortized
O(1), because macros are stored in a hash table, and coupling an O(1)
search along with Bruno's proof of O(n) insertion, the overall
m4_append_uniq is theoretically still O(n) rather than O(n log n).

At any rate, I see what you are trying to do - add an additional expense
of O(n) storage in order to avoid an expense of O(n) time in searching for
previously supplied entries (m4_append already uses O(n) storage for the
macro name, so you are just increasing the constant factor).  It seems
like libtool's ltsugar provides lt_dict* that does something like this
sort of operation.  And it certainly seems like something worth pursuing,
but not until after m4_append is fixed to be O(n) (no scaling improvements
result by making the search faster if the insertion is still slow).

|
| Still completely untested, of course...
|

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

Eric Blake             [email protected]
-----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

iEYEARECAAYFAkh6AKwACgkQ84KuGfSFAYC4KACeMD3eHciNCG/Mf/UHqfn5mRwF
HmEAniLwS/k6bldZJSn4EcNgcwaoaHyv
=3zLW
-----END PGP SIGNATURE-----