Both the recursive and the iterative versions of m4_set_add_all had a bug where they did not update the set size correctly if the set contained tombstones. I guess m4_set_remove isn’t used that often. (I found this bug by accident while investigating an unrelated thing.)
The root cause of the bug was that in the tombstone case we had two different layers quarreling over who got the last word on the size of the set: m4_set_add, called for each value argument, was updating the set size for each actual addition, and then the outer expansion of m4_set_add_all was clobbering those updates with a calculation based on the number of times the loop evaluated to a ‘-’ character, which in the tombstone case was always zero. The fix is to not mess with the set size on each actual addition, relying on the outer calculation in all cases. Most of the volume of the patch is refactoring to eliminate all the duplicate copies of the “add this element only if it isn’t already there” logic which were confusing the issue. I also made m4_set_add_all not go into an infinite loop if invoked with fewer than two arguments. Possibly it should error out in this case instead of silently doing nothing, but I don’t think it matters very much. * lib/m4sugar/m4sugar.m4 (_m4_set_add, _m4_set_add_clean): New macros, factoring out common “add element to set” logic. (m4_set_add): Redefine using _m4_set_add. (_m4_set_add_all): Rename to _m4_set_add_all_clean; use _m4_set_add_clean. (_m4_set_add_check): Use _m4_set_add, not m4_set_add; emit a string of dashes as _m4_set_add_all_clean does. (m4_set_add_all): Update to match renamed _m4_set_add_all_clean. Do nothing if invoked with fewer than two arguments. * lib/m4sugar/foreach.m4: Define variants of _m4_set_add_all_clean and _m4_set_add_all_check, matching the behavior of the definitions in m4sugar.m4. Do not define m4_set_add_all here. * tests/m4sugar.at (m4_set): Add more tests of interaction among m4_set_add_all, m4_set_remove, and m4_set_size. --- lib/m4sugar/foreach.m4 | 15 +++++------ lib/m4sugar/m4sugar.m4 | 60 ++++++++++++++++++++++++++++++++---------- tests/m4sugar.at | 53 +++++++++++++++++++++++++++++++++++++ 3 files changed, 105 insertions(+), 23 deletions(-) diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4 index ab558ac5..e2f512ee 100644 --- a/lib/m4sugar/foreach.m4 +++ b/lib/m4sugar/foreach.m4 @@ -350,13 +350,10 @@ m4_define([_m4_minmax], # # _m4_foreach to the rescue. If no deletions have occurred, then # avoid the speed penalty of m4_set_add. -m4_define([m4_set_add_all], -[m4_if([$#], [0], [], [$#], [1], [], - [m4_define([_m4_set_size($1)], m4_eval(m4_set_size([$1]) - + m4_len(_m4_foreach(m4_ifdef([_m4_set_cleanup($1)], - [[m4_set_add]], [[_$0]])[([$1],], [)], $@))))])]) +m4_define([_m4_set_add_all_clean], +[m4_if([$#], [2], [], + [_m4_foreach([_m4_set_add_clean([$1],], [, [-])], m4_shift($@))])]) -m4_define([_m4_set_add_all], -[m4_ifdef([_m4_set([$1],$2)], [], - [m4_define([_m4_set([$1],$2)], - [1])m4_pushdef([_m4_set([$1])], [$2])-])]) +m4_define([_m4_set_add_all_check], +[m4_if([$#], [2], [], + [_m4_foreach([_m4_set_add([$1],], [, [-])], m4_shift($@))])]) diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4 index 67b31055..c722a830 100644 --- a/lib/m4sugar/m4sugar.m4 +++ b/lib/m4sugar/m4sugar.m4 @@ -2964,6 +2964,43 @@ m4_ifdef([m4_PACKAGE_VERSION], # supply the value via _m4_defn([_m4_set([name])]) without needing any # quote manipulation. + +# _m4_set_add(SET, VALUE, [IF-UNIQ], [IF-DUP]) +# -------------------------------------------- +# Subroutine of m4_set_add and m4_set_add_all. +# Add VALUE as an element of SET, but do not update the size of SET. +# Expand IF-UNIQ on the first addition, and IF-DUP if it is already in +# the set. +# +# Three cases must be handled: +# - _m4_set([$1],$2) is not defined: +# define _m4_set([$1],$2) to 1, push $2 as a definition of _m4_set([$1]), +# expand IF-UNIQ. +# - _m4_set([$1],$2) is defined with value 0: +# define _m4_set([$1],$2) to 1, *don't* modify _m4_set([$1]), +# expand IF-UNIQ. +# - _m4_set([$1],$2) is defined with value 1: +# do nothing but expand IF-DUP. +m4_define([_m4_set_add], +[m4_ifndef([_m4_set([$1],$2)], + [m4_pushdef([_m4_set([$1])],[$2])m4_define([_m4_set([$1],$2)],[1])$3], + [m4_if(m4_indir([_m4_set([$1],$2)]), [0], + [m4_define([_m4_set([$1],$2)],[1])$3], + [$4])])]) + +# _m4_set_add_clean(SET, VALUE, [IF-UNIQ], [IF-DUP]) +# -------------------------------------------------- +# Subroutine of m4_set_add_all. +# Add VALUE as an element of SET, but do not update the size of SET. +# It is safe to assume that VALUE is not a tombstone, i.e. either +# _m4_set([$1],$2) is not defined or it is defined with value 1. +# Expand IF-UNIQ on the first addition, and IF-DUP if it is already in +# the set. +m4_define([_m4_set_add_clean], +[m4_ifndef([_m4_set([$1],$2)], + [m4_pushdef([_m4_set([$1])],[$2])m4_define([_m4_set([$1],$2)],[1])$3], + [$4])]) + # m4_set_add(SET, VALUE, [IF-UNIQ], [IF-DUP]) # ------------------------------------------- # Add VALUE as an element of SET. Expand IF-UNIQ on the first @@ -2974,13 +3011,7 @@ m4_ifdef([m4_PACKAGE_VERSION], # unpruned element, but it is just as easy to check existence directly # as it is to query _m4_set_cleanup($1). m4_define([m4_set_add], -[m4_ifdef([_m4_set([$1],$2)], - [m4_if(m4_indir([_m4_set([$1],$2)]), [0], - [m4_define([_m4_set([$1],$2)], - [1])_m4_set_size([$1], [m4_incr])$3], [$4])], - [m4_define([_m4_set([$1],$2)], - [1])m4_pushdef([_m4_set([$1])], - [$2])_m4_set_size([$1], [m4_incr])$3])]) +[_m4_set_add([$1], [$2], [_m4_set_size([$1], [m4_incr])$3], [$4])]) # m4_set_add_all(SET, VALUE...) # ----------------------------- @@ -2995,18 +3026,19 @@ m4_define([m4_set_add], # # Please keep foreach.m4 in sync with any adjustments made here. m4_define([m4_set_add_all], -[m4_define([_m4_set_size($1)], m4_eval(m4_set_size([$1]) - + m4_len(m4_ifdef([_m4_set_cleanup($1)], [_$0_check], [_$0])([$1], $@))))]) +[m4_case([$#], [0], [], [1], [], + [m4_define([_m4_set_size($1)], + m4_eval(m4_set_size([$1]) + + m4_len(m4_ifdef([_m4_set_cleanup($1)], + [_$0_check], [_$0_clean])([$1], $@))))])]) -m4_define([_m4_set_add_all], +m4_define([_m4_set_add_all_clean], [m4_if([$#], [2], [], - [m4_ifdef([_m4_set([$1],$3)], [], - [m4_define([_m4_set([$1],$3)], [1])m4_pushdef([_m4_set([$1])], - [$3])-])$0([$1], m4_shift2($@))])]) + [_m4_set_add_clean([$1], [$3], [-], [])$0([$1], m4_shift2($@))])]) m4_define([_m4_set_add_all_check], [m4_if([$#], [2], [], - [m4_set_add([$1], [$3])$0([$1], m4_shift2($@))])]) + [_m4_set_add([$1], [$3], [-], [])$0([$1], m4_shift2($@))])]) # m4_set_contains(SET, VALUE, [IF-PRESENT], [IF-ABSENT]) # ------------------------------------------------------ diff --git a/tests/m4sugar.at b/tests/m4sugar.at index 0b36e626..433f3b23 100644 --- a/tests/m4sugar.at +++ b/tests/m4sugar.at @@ -2261,6 +2261,59 @@ m4_count(m4_shift(m4_set_intersection([a], [b]))) 3334 ]]) +# Implementation corner cases. + +# m4_set_add_all dispatches to one of two different helper macros +# depending on whether the set has any tombstones; verify their +# effects are equivalent. N.B. m4_set_dump, m4_set_list, etc. produce +# elements in an arbitrary order, so this test is more brittle than +# I'd like. +AT_CHECK_M4SUGAR_TEXT([[dnl +m4_define([echo_if_member], [m4_set_contains([$1], [$2], [$2])])dnl +m4_set_add_all([a], [1])dnl +m4_set_add_all([a], [2], [3])dnl +m4_set_add_all([a], [4], [5], [6])dnl +m4_set_size([a]) +m4_map_args_sep([echo_if_member([a],], [)], [,], + [1], [2], [3], [4], [5], [6], [x], [y]) +m4_set_dump([a], [,]) + +m4_set_add([b], [x])dnl +m4_set_add([b], [y])dnl +m4_set_remove([b], [x])dnl +m4_set_add_all([b], [1])dnl +m4_set_add_all([b], [2], [3])dnl +m4_set_add_all([b], [4], [5], [6])dnl +m4_set_remove([b], [y])dnl +m4_set_size([b]) +m4_map_args_sep([echo_if_member([b],], [)], [,], + [1], [2], [3], [4], [5], [6], [x], [y]) +m4_set_dump([b], [,]) + +m4_set_add([c], [x])dnl +m4_set_add([c], [y])dnl +m4_set_remove([c], [y])dnl +m4_set_add_all([c], [1])dnl +m4_set_add_all([c], [2], [3])dnl +m4_set_add_all([c], [4], [5], [6])dnl +m4_set_remove([c], [x])dnl +m4_set_size([c]) +m4_map_args_sep([echo_if_member([c],], [)], [,], + [1], [2], [3], [4], [5], [6], [x], [y]) +m4_set_dump([c], [,]) +]], [[6 +1,2,3,4,5,6,, +6,5,4,3,2,1 + +6 +1,2,3,4,5,6,, +6,5,4,3,2,1 + +6 +1,2,3,4,5,6,, +6,5,4,3,2,1 +]]) + AT_CLEANUP -- 2.44.2
