From e38c46670951ceabb09293dcdc3bd6320f63769b Mon Sep 17 00:00:00 2001 From: Maxwell Pirtle Date: Wed, 8 Mar 2023 11:18:50 +0100 Subject: [PATCH] Add preliminary tests for checking event conflicts --- src/mc/explo/udpor/EventSet.cpp | 13 +- src/mc/explo/udpor/EventSet.hpp | 2 + src/mc/explo/udpor/EventSet_test.cpp | 257 ++++++++++++++++++++++- src/mc/explo/udpor/UnfoldingEvent.cpp | 2 +- src/xbt/utils/iter/variable_for_loop.hpp | 6 +- 5 files changed, 268 insertions(+), 12 deletions(-) diff --git a/src/mc/explo/udpor/EventSet.cpp b/src/mc/explo/udpor/EventSet.cpp index 2cdb6fbed3..3973022f1b 100644 --- a/src/mc/explo/udpor/EventSet.cpp +++ b/src/mc/explo/udpor/EventSet.cpp @@ -7,7 +7,7 @@ #include "src/mc/explo/udpor/Configuration.hpp" #include "src/mc/explo/udpor/History.hpp" #include "src/mc/explo/udpor/UnfoldingEvent.hpp" -#include "src/mc/explo/udpor/maximal_subsets_iterator.hpp" +#include "src/xbt/utils/iter/variable_for_loop.hpp" #include #include @@ -143,12 +143,11 @@ bool EventSet::is_maximal() const bool EventSet::is_conflict_free() const { - const auto begin = maximal_subsets_iterator(*this, std::nullopt, {2}); - const auto end = maximal_subsets_iterator(); - return std::none_of(begin, end, [](const EventSet event_pair) { - const auto events = std::move(event_pair).move_into_vector(); - const UnfoldingEvent* e1 = events[0]; - const UnfoldingEvent* e2 = events[1]; + const auto begin = simgrid::xbt::variable_for_loop{{*this}, {*this}}; + const auto end = simgrid::xbt::variable_for_loop(); + return std::none_of(begin, end, [=](const auto event_pair) { + const UnfoldingEvent* e1 = *event_pair[0]; + const UnfoldingEvent* e2 = *event_pair[1]; return e1->conflicts_with(e2); }); } diff --git a/src/mc/explo/udpor/EventSet.hpp b/src/mc/explo/udpor/EventSet.hpp index e49e1dbfef..d4ed132623 100644 --- a/src/mc/explo/udpor/EventSet.hpp +++ b/src/mc/explo/udpor/EventSet.hpp @@ -147,6 +147,8 @@ public: * @brief Moves the event set into a list */ std::vector move_into_vector() const&&; + + using const_iterator = std::unordered_set::const_iterator; }; } // namespace simgrid::mc::udpor diff --git a/src/mc/explo/udpor/EventSet_test.cpp b/src/mc/explo/udpor/EventSet_test.cpp index 534a616e38..de0822aedf 100644 --- a/src/mc/explo/udpor/EventSet_test.cpp +++ b/src/mc/explo/udpor/EventSet_test.cpp @@ -6,7 +6,9 @@ #include "src/3rd-party/catch.hpp" #include "src/mc/explo/udpor/EventSet.hpp" #include "src/mc/explo/udpor/UnfoldingEvent.hpp" +#include "src/mc/transition/Transition.hpp" +using namespace simgrid::mc; using namespace simgrid::mc::udpor; TEST_CASE("simgrid::mc::udpor::EventSet: Initial conditions when creating sets") @@ -380,7 +382,10 @@ TEST_CASE("simgrid::mc::udpor::EventSet: Set Union Tests") TEST_CASE("simgrid::mc::udpor::EventSet: Set Difference Tests") { - UnfoldingEvent e1, e2, e3, e4; + UnfoldingEvent e1; + UnfoldingEvent e2; + UnfoldingEvent e3; + UnfoldingEvent e4; // C = A + B // A is a subset of C @@ -719,4 +724,254 @@ TEST_CASE("simgrid::mc::udpor::EventSet: Testing Configurations") // 6 choose 6 = 1 test REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_maximal()); } +} + +TEST_CASE("simgrid::mc::udpor::EventSet: Moving into a collection") +{ + UnfoldingEvent e1; + UnfoldingEvent e2; + UnfoldingEvent e3; + UnfoldingEvent e4; + + EventSet A({&e1}); + EventSet B({&e1, &e2}); + EventSet C({&e1, &e2, &e3}); + EventSet D({&e1, &e2, &e3, &e4}); + + EventSet A_copy = A; + EventSet B_copy = B; + EventSet C_copy = C; + EventSet D_copy = D; + + std::vector actual_A = std::move(A).move_into_vector(); + std::vector actual_B = std::move(B).move_into_vector(); + std::vector actual_C = std::move(C).move_into_vector(); + std::vector actual_D = std::move(D).move_into_vector(); + + EventSet A_copy_remade(std::move(actual_A)); + EventSet B_copy_remade(std::move(actual_B)); + EventSet C_copy_remade(std::move(actual_C)); + EventSet D_copy_remade(std::move(actual_D)); + + REQUIRE(A_copy == A_copy_remade); + REQUIRE(B_copy == B_copy_remade); + REQUIRE(C_copy == C_copy_remade); + REQUIRE(D_copy == D_copy_remade); +} + +TEST_CASE("simgrid::mc::udpor::EventSet: Checking conflicts") +{ + struct IndependentAction : public Transition { + // Independent with everyone else + bool depends(const Transition* other) const override { return false; } + }; + + struct DependentAction : public Transition { + // Dependent with everyone else (except IndependentAction) + bool depends(const Transition* other) const override + { + return dynamic_cast(other) == nullptr; + } + }; + + struct ConditionallyDependentAction : public Transition { + // Dependent only with DependentAction (i.e. not itself) + bool depends(const Transition* other) const override + { + return dynamic_cast(other) != nullptr; + } + }; + + // The following tests concern the given event structure: + // e1 + // / / + // e2 e5 + // / / / + // e3 e4 e6 + // The tests enumerate all possible subsets of the events + // in the structure and test whether those subsets contain + // conflicts. + // + // Each test assigns different transitions to each event to + // make the scenarios more interesting + + SECTION("No conflicts throughout the whole structure with independent actions") + { + UnfoldingEvent e1(EventSet(), std::make_shared()); + UnfoldingEvent e2(EventSet({&e1}), std::make_shared()); + UnfoldingEvent e3(EventSet({&e2}), std::make_shared()); + UnfoldingEvent e4(EventSet({&e2}), std::make_shared()); + UnfoldingEvent e5(EventSet({&e1}), std::make_shared()); + UnfoldingEvent e6(EventSet({&e5}), std::make_shared()); + + // 6 choose 0 = 1 test + CHECK(EventSet().is_conflict_free()); + + // 6 choose 1 = 6 tests + CHECK(EventSet({&e1}).is_conflict_free()); + CHECK(EventSet({&e2}).is_conflict_free()); + CHECK(EventSet({&e3}).is_conflict_free()); + CHECK(EventSet({&e4}).is_conflict_free()); + CHECK(EventSet({&e5}).is_conflict_free()); + CHECK(EventSet({&e6}).is_conflict_free()); + + // 6 choose 2 = 15 tests + CHECK(EventSet({&e1, &e2}).is_conflict_free()); + CHECK(EventSet({&e1, &e3}).is_conflict_free()); + CHECK(EventSet({&e1, &e4}).is_conflict_free()); + CHECK(EventSet({&e1, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3}).is_conflict_free()); + CHECK(EventSet({&e2, &e4}).is_conflict_free()); + CHECK(EventSet({&e2, &e5}).is_conflict_free()); + CHECK(EventSet({&e2, &e6}).is_conflict_free()); + CHECK(EventSet({&e3, &e4}).is_conflict_free()); + CHECK(EventSet({&e3, &e5}).is_conflict_free()); + CHECK(EventSet({&e3, &e6}).is_conflict_free()); + CHECK(EventSet({&e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e5, &e6}).is_conflict_free()); + + // 6 choose 3 = 20 tests + CHECK(EventSet({&e1, &e2, &e3}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e4}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e4}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e4}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e5}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e2, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e3, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e3, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e3, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 4 = 15 tests + CHECK(EventSet({&e1, &e2, &e3, &e4}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e3, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e3, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e4, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e4, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e3, &e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 5 = 6 tests + CHECK(EventSet({&e1, &e2, &e3, &e4, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e3, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e3, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e4, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e3, &e4, &e5, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3, &e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 6 = 1 test + CHECK(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free()); + } + + SECTION("Conflicts throughout the whole structure with dependent actions (except with DFS sets)") + { + // Since all actions are dependent, if a set contains a "fork" or divergent histories, + // we expect the collections to contain conflicts + UnfoldingEvent e1(EventSet(), std::make_shared()); + UnfoldingEvent e2(EventSet({&e1}), std::make_shared()); + UnfoldingEvent e3(EventSet({&e2}), std::make_shared()); + UnfoldingEvent e4(EventSet({&e2}), std::make_shared()); + UnfoldingEvent e5(EventSet({&e1}), std::make_shared()); + UnfoldingEvent e6(EventSet({&e5}), std::make_shared()); + + // 6 choose 0 = 1 test + // There are no events even to be in conflict with + CHECK(EventSet().is_conflict_free()); + + // 6 choose 1 = 6 tests + // Sets of size 1 should have no conflicts + CHECK(EventSet({&e1}).is_conflict_free()); + CHECK(EventSet({&e2}).is_conflict_free()); + CHECK(EventSet({&e3}).is_conflict_free()); + CHECK(EventSet({&e4}).is_conflict_free()); + CHECK(EventSet({&e5}).is_conflict_free()); + CHECK(EventSet({&e6}).is_conflict_free()); + + // 6 choose 2 = 15 tests + CHECK(EventSet({&e1, &e2}).is_conflict_free()); + CHECK(EventSet({&e1, &e3}).is_conflict_free()); + CHECK(EventSet({&e1, &e4}).is_conflict_free()); + CHECK(EventSet({&e1, &e5}).is_conflict_free()); + CHECK(EventSet({&e1, &e6}).is_conflict_free()); + CHECK(EventSet({&e2, &e3}).is_conflict_free()); + CHECK(EventSet({&e2, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e5, &e6}).is_conflict_free()); + + // 6 choose 3 = 20 tests + CHECK(EventSet({&e1, &e2, &e3}).is_conflict_free()); + CHECK(EventSet({&e1, &e2, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e4, &e6}).is_conflict_free()); + CHECK(EventSet({&e1, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 4 = 15 tests + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 5 = 6 tests + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_conflict_free()); + CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_conflict_free()); + + // 6 choose 6 = 1 test + CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free()); + } } \ No newline at end of file diff --git a/src/mc/explo/udpor/UnfoldingEvent.cpp b/src/mc/explo/udpor/UnfoldingEvent.cpp index 9dffa8354b..bd49e863e9 100644 --- a/src/mc/explo/udpor/UnfoldingEvent.cpp +++ b/src/mc/explo/udpor/UnfoldingEvent.cpp @@ -42,7 +42,7 @@ EventSet UnfoldingEvent::get_history() const bool UnfoldingEvent::related_to(const UnfoldingEvent* other) const { - return EventSet({this, other}).is_maximal(); + return this->in_history_of(other) or other->in_history_of(this); } bool UnfoldingEvent::in_history_of(const UnfoldingEvent* other) const diff --git a/src/xbt/utils/iter/variable_for_loop.hpp b/src/xbt/utils/iter/variable_for_loop.hpp index 75c4b5478f..bd5d29ab10 100644 --- a/src/xbt/utils/iter/variable_for_loop.hpp +++ b/src/xbt/utils/iter/variable_for_loop.hpp @@ -53,7 +53,7 @@ public: if (has_effect and (not collections.empty())) { std::transform(collections.begin(), collections.end(), std::back_inserter(current_subset), - [](const auto& c) { return c.get().begin(); }); + [](const auto& c) { return c.get().cbegin(); }); underlying_collections = std::move(collections); } // Otherwise leave `underlying_collections` as default-initialized (i.e. empty) @@ -89,8 +89,8 @@ template void variable_for_loop::increment // If the `j`th element has reached its own end, reset it // back to the beginning and keep moving forward - if (new_position == underlying_collections[j].get().end()) { - current_subset[j] = underlying_collections[j].get().begin(); + if (new_position == underlying_collections[j].get().cend()) { + current_subset[j] = underlying_collections[j].get().cbegin(); } else { // Otherwise we've found the largest element which needed to // be moved down. Everyone else before us has been reset -- 2.20.1