nit, clang-format

@@ -174,7 +174,7 @@ unsigned int FillFlags(unsigned int flags)
 std::set<unsigned int> GenerateAllSubMasks(unsigned int flags)
 {
     std::vector<unsigned int> set_flags;
-    const size_t n_flags = sizeof(unsigned int)*8;
+    const size_t n_flags = sizeof(unsigned int) * 8;
     set_flags.reserve(n_flags);
@@ -184,10 +184,10 @@ std::set<unsigned int> GenerateAllSubMasks(unsigned int flags)
     }
     const size_t combos = 1 << set_flags.size();
     // skip last all set flags
-    std::vector<unsigned int> all_flag_combos(combos-1);
-    for (size_t i = 0; i < combos-1; ++i){
-        for(size_t j = 0; j < set_flags.size(); ++j) {
-            if (i & (1<<j)) {
+    std::vector<unsigned int> all_flag_combos(combos - 1);
+    for (size_t i = 0; i < combos - 1; ++i) {
+        for (size_t j = 0; j < set_flags.size(); ++j) {
+            if (i & (1 << j)) {
                 all_flag_combos[i] |= set_flags[j];

nit, can use braced initialization on these for type safety

-    const size_t n_flags = sizeof(unsigned int)*8;
+    const size_t n_flags{sizeof(unsigned int) * 8};
     set_flags.reserve(n_flags);
     for (size_t i = 0; i < n_flags; ++i) {
-        const unsigned int flag = flags & (1 << i);
+        const unsigned int flag{flags & (1 << i)};

maybe hoist subtracting one to the declaration of combos

-    const size_t combos = 1 << set_flags.size();
+    const size_t combos = (1 << set_flags.size()) - 1;
     // skip last all set flags
-    std::vector<unsigned int> all_flag_combos(combos-1);
-    for (size_t i = 0; i < combos-1; ++i){
+    std::vector<unsigned int> all_flag_combos(combos);
+    for (size_t i = 0; i < combos; ++i) {

If I understand the intent of this code correctly, the idea is that given a set of chosen flags, we want to check that every possible superset of flags doesn't succeed. If that's so, I believe there's a problem with the current FlipAll( GenerateAllSubMasks( flags ) ) logic for computing all possible supersets.

Eg, assuming 3-bit words, for flags = 100, we'll generate all flags sub masks {000}, and then flip them {111}. However, what we really want is to generate all the ~flags = 011 sub masks {010, 001, 000}, and then flip them {101, 110, 111}.

In short, there's a missing bit flip before computing all the sub masks. Ie. it should be

FlipAll( GenerateAllSubMasks( ~flags ) )

With that said, there's still the issue that flipping flag bits doesn't interact well with the TrimFlags operation done inside GenerateAllSubMasks.

Eg. if the only flag bits wereVERIFY_P2SH and VERIFY_WITNESS (in that order), for flags = 00 we'd generate all the ~flags = 11 sub masks {10, 01, 00}, trim them {10, 00, 00} (01 is mapped to 00), remove duplicates {10, 00}, and finally flip them {01, 11}. However, we ended up with an invalid combination (01) when the correct result would have been {10, 11}.

More generally, after fixing the initial missing flip, the code would look something like

FlipAll( Unique( TrimFlags( GenerateAllSubMasksWithoutTrimming( ~flags ) ) ) )

when what we really want is something like:

for flag_superset in FlipAll( GenerateAllSubMasksWithoutTrimming( ~flags ) ) ) ):
    if flag_superset == TrimFlags( flag_superset ):
        # use flag_superset

yeah you're totally right; i've been playing with it a bit as well and noticed that it seems to not be quite right (thanks @jonatack for pointing it out).

The logic is definitely off, and I think it may be intractible in this case since GenerateAllSubMasksWithoutTrimming(~flags) ends up being pretty big... with 20 it might be ok, but eventually there would be too many flags.

Makes sense. Maybe bound the amount of flipped bits? That way you can test some flag interactions, but bound the exponential growth. The bounding capability would also help to put a safeguard against exponential explosion in the tx_invalid test if there are too many set bits in the initial mask.