Announce: UnorderedElementsAre() and UnorderedElementsAreArray()

[Billy Donahue]

GMock has two important new matchers, UnorderedElementsAre() and UnorderedElementsAreArray().

Sample Usage:

   EXPECT_THAT(x, UnorderedElementsAre(m1, m2, ...));
   EXPECT_THAT(x, UnorderedElementsAreArray(mvec));

These succeed if there is some permutation of the matcher sequence such that every element of 'x' is successfully paired to a matcher.

Unlike WhenSorted(ElementsAre(...)) we can use UnorderedElementsAre(...) on a set of matchers that has no sort order. For example:

vector<int> x{1, 6};

EXPECT_THAT(x, ElementsAre(Gt(5), IsOdd()));  // no

EXPECT_THAT(x, UnorderedElementsAre({Gt(5), IsOdd()}));  // yes

This change allows us to write fundamentally better unit tests to check the contents of unordered containers like hash_map or hash_set. Previously, tests would often implicitly rely on the properties of the hash function, or on magic numbers inside the container's implementation. Matching the elements of, say, an 8-element hash_set<Foo*>, was impossible without presorting somehow. Other workarounds include relying on the lexicographic order of some serialized form of the elements, which also has serious limitations.

Anyway, those days are over.

We can now write correct tests against unordered containers far more easily.

using testing::MatchesRegex;

using testing::Pair;

using testing::Pointee;

using testing::UnorderedElementsAre;

hash_map<string, Own*> GetOwnershipMap();

...

 // Check that 'm' has 3 elements in some order:

 // - A key matching /local-.*/ must map to a

 //   Own with owner()=="a".

 // - A key matching /local-.*/ must map to a

 //   Own with owner()=="b".

 // - A key matching /remote-.*/ must also map to a

 //   Own matching owner()=="a".

 EXPECT_THAT(GetOwnershipMap(),

     UnorderedElementsAre(

         Pair(MatchesRegex("local-.*"),

              Partially("owner: a")),

         Pair(MatchesRegex("local-.*"),

              Partially("owner: b")),

         Pair(MatchesRegex("remote-.*"),

              Partially("owner: a"))));

UnorderedElementsAreArray() is similar to UnorderedElementsAre(), but the set of matchers is specified within a container instead of passing them as function arguments. Using such a container is necessary if you have more than 10 matchers, or need to generate matchers programmatically.

The development of these matchers took about 2 months, and it's unusually complex internally (based on a max-flow algorithm to perform max bipartite matching in O(N^3)), but the benefits should be great and the usage is simple.

Special thanks to Alex Pilkiewicz, Corey Kosak, Marcus Boerger and of course Zhanyong Wan for prior work, code reviews and ideas.