bag has issues if an item matches multiple elements

[exodist]

    my $check = bag {
        item match qr/a/;
        item match qr/b/;
        end();    # Ensure no other elements exist.
    };  

    is(['fab', 'bad'], $check);

In this case we get a failure cause both items match the first element, so the second element is considered 'extra' for the end check. A quick-fix would be to never re-check an element, but that is not a valid fix:

    my $check = bag {
        item match qr/a/;
        item match qr/ab/; # <---- change is here
        end();    # Ensure no other elements exist.
    };  

    is(['fab', 'bad'], $check);

This one will still fail because the less greedy bag item got 'fab' and 'ab' will not match against 'bad' but a human reader knows this should pass.

I think bag as it is currently needs a bit of an overhaul. We need to iterate over the array, not the bag items. We need to record all matches. When 'end; is not specified we just need to check that all items have at least 1 match in the array, easy. When 'end' is used we need to make sure both lists have a match in the other, but in cases where there are multiple matches we need to pick one. This can get complicated.

[exodist]

This was discovered when looking at Test-More/Test2-Suite#43.

[dakkar]

FWIW, Test::Deep has the same problem, and they just documented it.
I'll try to come up with some implementation that does not suffer from combinatorial explosion.

[dakkar]

I have rewritten Bag in a maybe-too-complicated way. It builds a matrix of inputs × checks, then looks at it to see what went wrong.
It handles the degenerate cases (empty input array, empty bag) up front.
My main problem at the moment: I don't know what kind of deltas to return in some cases. Suggestions very welcome.

[exodist]

First off, those commits are failing in travis, so that needs to be fixed.

I have not yet done a full code review, I will when I have a chance.

I would like an explanation of how it handles things after the matrix is created. Say 1 check matches 2 items in the array, but no other checks match either item, will it pass or fail? What about more complicated scenarios where all items in the array have matched at least 1 check, but some checks matched multiple items, but there are less checks than matched items and 'end' was used?

I am actually not 100% sure what the correct way to handle these scenarios are, so right now I am interested in how you handle them.

[dakkar]

Re: failing, yes, I know, the tests that are failing are those that check the deltas returned in cases where I'm not sure what we should be returning.

My current logic is:

• each check must match at least one input element, always
• if end was used ($closed, in my code):
  • each input element must match at least one match
  • the number of input elements must be the same as the number of checks
    • this is actually not wholly implemented, because I have no clear idea how to report it, but there's a $inputs_with_matches counter to use for that purpose

Regarding deltas:

• if an input element matches 0 checks, I return the deltas from each check against that element
• if a check matches 0 input elements, I return {dne=>'got',id=>[ARRAY=>'*'],check=>$the_check} (I read that as "there's no input anywhere matching this check")
• if there are more matching elements than checks, I return {id=>[ARRAY=>$idx],got=>$list[$dx],check=>$check} for each check matching that element (this is horrible, since I'm abusing Delta to report a successful match)

So the open questions are:

• is my basic logic sound?
• how do we report "these elements matched, but you weren't expecting them to"?
• how do we report "these checks matched multiple times, but you weren't expecting them to"?
• does my approach to implementing the logic make sense?

[exodist]

Yes, it makes sense. Once again I have not looked at the code. That said I worked it out, and here is how I think the deltas should work:

First check that the array has at least as many elements as the bag, if it does not then add a delta that indicates we expected more items:

| PATH        | GOT | CHECK |
| [0] <count> | 5   | 8+    |

If end is specified we want to do the same for the opposite, more array items than bag items:

| PATH        | GOT | CHECK |
| [0] <count> | 8   | 5     |

After those deltas add the ones for any checks that didn't match an item

| PATH   | GOT              | CHECK |
| [0][*] | <DOES NOT EXIST> | x     |

if end() is specified add deltas for any extra array items, these should indicate we expected them to not exist.

| PATH   | GOT | OP      | CHECK            |
| [0][0] | a   | !exists | <DOES NOT EXIST> |

if end() is not specified, but we have deltas for any failure, add deltas for all unmatched items, this should NOT indicate we expected them to not exist, the 'expected' and 'op' columns should be empty. This is just informative diagnostics

| PATH   | GOT | OP | CHECK |
| [0][0] | a   |    |       |

To summarize

• Delta for the count if there are more items in the bag than the array, should expect the count of the bag or more (bag_count+)
• Delta for the count if the array is bigger than the bag and 'end' is used
• Delta for any unmatched check, always
• Delta for extra/unmatched array items if end is used
• Delta for any extra/unmatched array items if end is not used, but there are unmatched checks, or count mismatch (this does not indicate that the items should not exist, it just prints them for diag purposes)