Fix non-determinism in `UniqueElementsContainerOf` and `UniqueElementsVectorOf`. These domains are typically used with sequence containers like `std::vector`, where the ordering of elements is important. However, by basing the domains on `absl::flat_hash_set`, the ordering gets lost, leading to non-determinism. This can lead to unexpected behavior, especially in combination with combinators like `FlatMap`. The fix exploits the fact that `AssociativeContainerOfImpl<absl::flat_hash_set>` uses `std::list` -- a sequence container -- as a corpus type, so it already preserves the ordering of elements. Furthermore, it automatically dedups elements while doing `Init` and `Mutate`. The only problematic part are the functions `FromValue` and `GetValue` in `UniqueElementsContainerImpl`, which convert the values via an intermediate set and can thus lose the ordering. The fix is to convert the values directly, element by element. I also improved validation, which now makes sure that the corpus value indeed has unique elements. PiperOrigin-RevId: 715922985
diff --git a/domain_tests/BUILD b/domain_tests/BUILD index 041ac42..6c84318 100644 --- a/domain_tests/BUILD +++ b/domain_tests/BUILD
@@ -79,7 +79,7 @@ "@com_google_absl//absl/random", "@com_google_absl//absl/strings", "@com_google_fuzztest//fuzztest:domain_core", - "@com_google_fuzztest//fuzztest:type_support", + "@com_google_fuzztest//fuzztest:meta", "@com_google_googletest//:gtest_main", ], )
diff --git a/domain_tests/CMakeLists.txt b/domain_tests/CMakeLists.txt index 1095369..c7d97b1 100644 --- a/domain_tests/CMakeLists.txt +++ b/domain_tests/CMakeLists.txt
@@ -68,7 +68,7 @@ absl::random_random absl::strings fuzztest::domain_core - fuzztest::type_support + fuzztest::meta GTest::gmock_main )
diff --git a/domain_tests/container_combinators_test.cc b/domain_tests/container_combinators_test.cc index 53a9324..9416cae 100644 --- a/domain_tests/container_combinators_test.cc +++ b/domain_tests/container_combinators_test.cc
@@ -35,7 +35,7 @@ #include "absl/strings/str_cat.h" #include "./fuzztest/domain_core.h" #include "./domain_tests/domain_testing.h" -#include "./fuzztest/internal/type_support.h" +#include "./fuzztest/internal/meta.h" namespace fuzztest { namespace { @@ -48,8 +48,10 @@ using ::testing::FieldsAre; using ::testing::Ge; using ::testing::Gt; +using ::testing::HasSubstr; using ::testing::IsEmpty; using ::testing::Le; +using ::testing::MatchesRegex; using ::testing::Pair; using ::testing::SizeIs; @@ -236,7 +238,7 @@ TEST(UniqueElementsContainerTest, InitGeneratesSeeds) { auto domain = UniqueElementsContainerOf<std::unordered_multiset<int>>(Arbitrary<int>()) - .WithSeeds({{1, 3, 3, 7}}); + .WithSeeds({{1, 3, 7}}); EXPECT_THAT(GenerateInitialValues(domain, 1000), Contains(Value(domain, {1, 3, 7}))); @@ -300,14 +302,28 @@ EXPECT_THAT( domain_a.ValidateCorpusValue(value_b.corpus_value), - IsInvalid(testing::MatchesRegex( + IsInvalid(MatchesRegex( R"(Invalid value in container at index 0 >> The value .+ is not InRange\(0, 9\))"))); EXPECT_THAT( domain_b.ValidateCorpusValue(value_a.corpus_value), - IsInvalid(testing::MatchesRegex( + IsInvalid(MatchesRegex( R"(Invalid value in container at index 0 >> The value .+ is not InRange\(10, 19\))"))); } +TEST(UniqueElementsVectorOf, ValidationRejectsNonUniqueElements) { + auto domain = UniqueElementsVectorOf(InRange(1, 10)); + Value value(domain, {1, 2, 2, 3}); + + EXPECT_THAT( + domain.ValidateCorpusValue(value.corpus_value), + IsInvalid(HasSubstr(R"(The container doesn't have unique elements)"))); +} + +TEST(UniqueElementsVectorOf, VerifyRoundTripThroughConversion) { + auto domain = UniqueElementsVectorOf(InRange(100, 1000)).WithMaxSize(5); + VerifyRoundTripThroughConversion(GenerateValues(domain), domain); +} + TEST(ContainerCombinatorTest, ArrayOfOne) { // A domain of std::array<T, 1> values can be defined in two ways: auto with_explicit_size = ArrayOf<1>(InRange(0.0, 1.0));
diff --git a/fuzztest/internal/domains/unique_elements_container_of_impl.h b/fuzztest/internal/domains/unique_elements_container_of_impl.h index db30b33..370a691 100644 --- a/fuzztest/internal/domains/unique_elements_container_of_impl.h +++ b/fuzztest/internal/domains/unique_elements_container_of_impl.h
@@ -29,35 +29,26 @@ namespace fuzztest::internal { template <typename InnerDomain> -using UniqueDomainValueT = absl::flat_hash_set<value_type_t<InnerDomain>>; - -template <typename InnerDomain> using UniqueDomain = - AssociativeContainerOfImpl<UniqueDomainValueT<InnerDomain>, InnerDomain>; + AssociativeContainerOfImpl<absl::flat_hash_set<value_type_t<InnerDomain>>, + InnerDomain>; // UniqueElementsContainerImpl supports producing containers of type `T`, with // elements of type `E` from domain `InnerDomain inner`, with a guarantee that // each element of the container has a unique value from `InnerDomain`. The -// guarantee is provided by using a `absl::flat_hash_set<E>` as our corpus_type, -// which is (effectively) produced by `UnorderedSetOf(inner)`. +// guarantee is provided by using a `absl::flat_hash_set<E>` under the hood. template <typename T, typename InnerDomain> class UniqueElementsContainerImpl : public domain_implementor::DomainBase< UniqueElementsContainerImpl<T, InnerDomain>, T, corpus_type_t<UniqueDomain<InnerDomain>>> { - using InnerUniqueDomainValueT = UniqueDomainValueT<InnerDomain>; - using InnerUniqueDomain = UniqueDomain<InnerDomain>; - public: using typename UniqueElementsContainerImpl::DomainBase::corpus_type; using typename UniqueElementsContainerImpl::DomainBase::value_type; UniqueElementsContainerImpl() = default; explicit UniqueElementsContainerImpl(InnerDomain inner) - : unique_domain_(std::move(inner)) {} - - // All of these methods delegate at least partially to the unique_domain_ - // member. + : inner_domain_(inner), unique_domain_(std::move(inner)) {} corpus_type Init(absl::BitGenRef prng) { if (auto seed = this->MaybeGetRandomSeed(prng)) return *seed; @@ -71,13 +62,25 @@ } value_type GetValue(const corpus_type& v) const { - InnerUniqueDomainValueT unique_values = unique_domain_.GetValue(v); - return value_type(unique_values.begin(), unique_values.end()); + // Converts directly via `inner_domain_` instead of via `unique_domain_` to + // preserve the order of elements in sequence containers. + value_type result; + for (const auto& inner_corpus_val : v) { + result.insert(result.end(), inner_domain_.GetValue(inner_corpus_val)); + } + return result; } std::optional<corpus_type> FromValue(const value_type& v) const { - return unique_domain_.FromValue( - value_type_t<InnerUniqueDomain>(v.begin(), v.end())); + // Converts directly via `inner_domain_` instead of via `unique_domain_` to + // preserve the order of elements in sequence containers. + corpus_type result; + for (const auto& inner_user_val : v) { + auto inner_corpus_val = inner_domain_.FromValue(inner_user_val); + if (!inner_corpus_val) return std::nullopt; + result.insert(result.end(), *std::move(inner_corpus_val)); + } + return result; } auto GetPrinter() const { return unique_domain_.GetPrinter(); } @@ -91,7 +94,14 @@ } absl::Status ValidateCorpusValue(const corpus_type& corpus_value) const { - return unique_domain_.ValidateCorpusValue(corpus_value); + absl::Status status = unique_domain_.ValidateCorpusValue(corpus_value); + if (!status.ok()) return status; + auto unique_values = unique_domain_.GetValue(corpus_value); + if (unique_values.size() != corpus_value.size()) { + return absl::InvalidArgumentError( + "The container doesn't have unique elements"); + } + return absl::OkStatus(); } auto& WithSize(size_t s) { return WithMinSize(s).WithMaxSize(s); } @@ -105,7 +115,8 @@ } private: - InnerUniqueDomain unique_domain_; + InnerDomain inner_domain_; + UniqueDomain<InnerDomain> unique_domain_; }; } // namespace fuzztest::internal