Re: m4sugar and m4 1.6, bison

[Eric Blake]

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

According to Ralf Wildenhues on 7/14/2008 1:26 PM:
|> But there is still the matter of how to remove all
|> the stale macros if the key being appended to is redefined as empty.
|
| ... are certainly enough of a churn to require that such an improved
| algorithm gets a new name, and the old one *remains*, supported with
| its current semantics.

I came to the same conclusion - the API I'm thinking of, along with
lightly tested code, is:

# Expand IF-PRESENT or IF-ABSENT depending on whether VALUE
# is in the set KEY.
# O(1)
#m4_set_contains(KEY, VALUE, [IF-PRESENT], [IF_ABSENT])
m4_define([m4_set_contains],
[dnl track creation of this value
m4_if(m4_ifdef([_m4_set_entry($1,$2)],
~               [m4_defn([_m4_set_entry($1,$2)])], [0]),
~      [1], [$3], [$4])[]dnl
])

# Add VALUE to the set KEY, if it is not already present.
# VALUE can be arbitrary text (except that unbalanced quotes should
# be given via quadrigraphs), while KEY must not contain a comma.
# Expand IF-NEW or IF-DUP accordingly.
# O(n) in the maximum length of unpruned set (depending on m4 quality)
#m4_set_add(KEY, VALUE, [IF-NEW], [IF-DUP])
m4_define([m4_set_add],
[m4_set_contains([$1], [$2], [$4],
[dnl track creation of this value
m4_define([_m4_set_entry($1,$2)], [1])dnl
dnl and keep running track of all values in set
m4_append([_m4_set_values($1)], [[$2]], [,])$3])[]dnl
])

# Remove VALUE from the set KEY, if it is present.
# Expand IF-DELETED or IF-ABSENT accordingly.
# Note that this implementation occupies extra memory until the next
# m4_set_prune (which may be via m4_set_display or m4_set_delete).
# O(1)
#m4_set_remove(KEY, VALUE, [IF-DELETED], [IF-ABSENT])
m4_define([m4_set_remove],
[m4_set_contains([$1], [$2],
~           [m4_define([_m4_set_entry($1,$2)], [0])$3], [$4])[]dnl
])

# Return a string containing all the elements of the set KEY,
# separated by SEP.  No provision is made for disambiguating
# set elements that contain non-empty SEP as a sub-string.
# This implementation also prunes any extra memory from deleted values.
# O(n) in the maximum length of unpruned set (depending on m4 quality)
#m4_set_contents(KEY, [SEP])
m4_define([m4_set_contents],
[m4_set_prune([$1])m4_join([$2], m4_ifdef([_m4_set_values($1)],
~  [m4_unquote(m4_defn([_m4_set_values($1)]))]))[]dnl
])

# Return a string containing only the VALUEs that are elements
# of the set KEY, separated by SEP.  No provision is made for
# disambiguating set elements that contain non-empty SEP as a
# sub-string.  The resulting string can contain duplicates, if
# a given VALUE in the set is listed in multiple arguments.
# No pruning of extra memory from deleted values is performed.
# O(m) in the number of VALUEs.
#m4_set_filter(KEY, [SEP], VALUE, [...])
m4_define([m4_set_filter],
[m4_join([$2]m4_foreach([m4_value], m4_dquote(m4_shift2($@)),
~  [m4_set_contains([$1], m4_defn([m4_value]),
~    [, m4_defn([m4_value])])]))[]dnl
])

# Delete the set KEY, reclaiming all its memory.
# O(n) in the maximum length of unpruned set
#m4_set_delete(KEY)
m4_define([m4_set_delete],
[m4_ifdef([_m4_set_values($1)],
~  [m4_foreach([m4_value], m4_defn([_m4_set_values($1)]),
~    [m4_undefine([_m4_set_entry($1,]m4_defn([m4_value])[)])])dnl
m4_undefine([_m4_set_values($1)])])dnl
])

# Reclaim any memory occupied by deleted set elements from the set KEY.
# O(n) in the maximum length of unpruned set
#m4_set_prune(KEY)
m4_define([m4_set_prune],
[m4_ifdef([_m4_set_values($1)], [m4_define([_m4_set_values($1)],
~  m4_join([,]m4_foreach([m4_value], m4_defn([_m4_set_values($1)]),
~    [m4_if(m4_defn([_m4_set_entry($1,]m4_defn([m4_value])[)]),
~      [0], [m4_undefine([_m4_set_entry($1,]m4_defn([m4_value])[)])],
~      [, m4_dquote(m4_defn([m4_value]))])[]dnl
])))])dnl
])


With the above, counting the number of set elements is O(n).  We could
additionally add O(1) set size querying, if desired, by making m4_set_add
and m4_set_remove modify _m4_set_size($1).

- --
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

iEYEARECAAYFAkh8FOgACgkQ84KuGfSFAYCV/gCgglJtmCAJDgxCO+iN8/FBxf+l
HesAn0mXPQAipt8DjcA2pkc2oE7AbFmT
=z5B5
-----END PGP SIGNATURE-----