Add first batch of tests for conflict detection among events

Detecting conflicts among a collection of events
is super critical to the proper functioning of
UDPOR (it is primarily used to compute en(C) for
a given configuration). Testing conflicts among
events in an event structure is very important.
Subsequent commits and MRs will continue to add
tests for detecting conflicts among collections
of events.

Detecting immediate conflicts is also critical
when it comes to determining which events UDPOR
decides to keep around after continuing its search.
Immediate conflicts are more subtle and should be
tested with great care.

diff --git a/src/mc/explo/udpor/UnfoldingEvent.cpp b/src/mc/explo/udpor/UnfoldingEvent.cpp
index 0f62179..b62ef1a 100644 (file)
--- a/src/mc/explo/udpor/UnfoldingEvent.cpp
+++ b/src/mc/explo/udpor/UnfoldingEvent.cpp
@@ -67,12 +67,10 @@ bool UnfoldingEvent::conflicts_with(const UnfoldingEvent* other) const
   const EventSet unique_to_me    = my_history.subtracting(other_history);
   const EventSet unique_to_other = other_history.subtracting(my_history);
 
-  const bool conflicts_with_me = std::any_of(unique_to_me.begin(), unique_to_me.end(), [&](const UnfoldingEvent* e) {
-    return e->has_dependent_transition_with(other);
-  });
-  const bool conflicts_with_other =
-      std::any_of(unique_to_other.begin(), unique_to_other.end(),
-                  [&](const UnfoldingEvent* e) { return e->has_dependent_transition_with(this); });
+  const bool conflicts_with_me    = std::any_of(unique_to_me.begin(), unique_to_me.end(),
+                                                [&](const UnfoldingEvent* e) { return e->is_dependent_with(other); });
+  const bool conflicts_with_other = std::any_of(unique_to_other.begin(), unique_to_other.end(),
+                                                [&](const UnfoldingEvent* e) { return e->is_dependent_with(this); });
   return conflicts_with_me or conflicts_with_other;
 }
 
@@ -85,7 +83,7 @@ bool UnfoldingEvent::conflicts_with(const Configuration& config) const
   // if they are not related)
   const EventSet potential_conflicts = config.get_events().subtracting(get_history());
   return std::any_of(potential_conflicts.cbegin(), potential_conflicts.cend(),
-                     [&](const UnfoldingEvent* e) { return this->has_dependent_transition_with(e); });
+                     [&](const UnfoldingEvent* e) { return this->is_dependent_with(e); });
 }
 
 bool UnfoldingEvent::immediately_conflicts_with(const UnfoldingEvent* other) const
@@ -122,7 +120,7 @@ bool UnfoldingEvent::is_dependent_with(const Transition* t) const
   return associated_transition->depends(t);
 }
 
-bool UnfoldingEvent::has_dependent_transition_with(const UnfoldingEvent* other) const
+bool UnfoldingEvent::is_dependent_with(const UnfoldingEvent* other) const
 {
   return is_dependent_with(other->associated_transition.get());
 }

diff --git a/src/mc/explo/udpor/UnfoldingEvent.hpp b/src/mc/explo/udpor/UnfoldingEvent.hpp
index b6d9b37..6c57bf6 100644 (file)
--- a/src/mc/explo/udpor/UnfoldingEvent.hpp
+++ b/src/mc/explo/udpor/UnfoldingEvent.hpp
@@ -34,7 +34,7 @@ public:
   bool conflicts_with(const Configuration& config) const;
   bool immediately_conflicts_with(const UnfoldingEvent* other) const;
   bool is_dependent_with(const Transition*) const;
-  bool has_dependent_transition_with(const UnfoldingEvent* other) const;
+  bool is_dependent_with(const UnfoldingEvent* other) const;
 
   const EventSet& get_immediate_causes() const { return this->immediate_causes; }
   Transition* get_transition() const { return this->associated_transition.get(); }

diff --git a/src/mc/explo/udpor/UnfoldingEvent_test.cpp b/src/mc/explo/udpor/UnfoldingEvent_test.cpp
index 1623fd3..5ea1e63 100644 (file)
--- a/src/mc/explo/udpor/UnfoldingEvent_test.cpp
+++ b/src/mc/explo/udpor/UnfoldingEvent_test.cpp
@@ -5,5 +5,393 @@
 
 #include "src/3rd-party/catch.hpp"
 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
+#include "src/mc/explo/udpor/udpor_tests_private.hpp"
 
 using namespace simgrid::mc::udpor;
+
+TEST_CASE("simgrid::mc::udpor::UnfoldingEvent: Dependency/Conflict Tests")
+{
+  SECTION("Properties of the relations")
+  {
+    // The following tests concern the given event structure:
+    //                e1
+    //              /   /
+    //            e2    e6
+    //           /  /    /
+    //          e3   /   /
+    //         /  /    /
+    //        e4  e5   e7
+    //
+    // e5 and e6 are in conflict, e5 and e7 are in conflict, e2 and e6, and e2 ands e7 are in conflict
+    UnfoldingEvent e1(EventSet(), std::make_shared<ConditionallyDependentAction>());
+    UnfoldingEvent e2(EventSet({&e1}), std::make_shared<DependentAction>());
+    UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e5(EventSet({&e3}), std::make_shared<DependentAction>());
+    UnfoldingEvent e6(EventSet({&e1}), std::make_shared<ConditionallyDependentAction>());
+    UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<ConditionallyDependentAction>());
+
+    SECTION("Dependency relation properties")
+    {
+      SECTION("Dependency is reflexive")
+      {
+        REQUIRE(e2.is_dependent_with(&e2));
+        REQUIRE(e5.is_dependent_with(&e5));
+      }
+
+      SECTION("Dependency is symmetric")
+      {
+        REQUIRE(e2.is_dependent_with(&e6));
+        REQUIRE(e6.is_dependent_with(&e2));
+      }
+
+      SECTION("Dependency is NOT necessarily transitive")
+      {
+        REQUIRE(e1.is_dependent_with(&e5));
+        REQUIRE(e5.is_dependent_with(&e7));
+        REQUIRE_FALSE(e1.is_dependent_with(&e7));
+      }
+    }
+
+    SECTION("Conflict relation properties")
+    {
+      SECTION("Conflict relation is irreflexive")
+      {
+        REQUIRE_FALSE(e1.conflicts_with(&e1));
+        REQUIRE_FALSE(e2.conflicts_with(&e2));
+        REQUIRE_FALSE(e3.conflicts_with(&e3));
+        REQUIRE_FALSE(e4.conflicts_with(&e4));
+        REQUIRE_FALSE(e5.conflicts_with(&e5));
+        REQUIRE_FALSE(e6.conflicts_with(&e6));
+        REQUIRE_FALSE(e7.conflicts_with(&e7));
+      }
+
+      SECTION("Conflict relation is symmetric")
+      {
+        REQUIRE(e5.conflicts_with(&e6));
+        REQUIRE(e6.conflicts_with(&e5));
+      }
+    }
+  }
+
+  SECTION("No conflicts whatsoever")
+  {
+    // The following tests concern the given event structure:
+    //                e1
+    //              /   /
+    //            e2    e6
+    //           /  /    /
+    //          e3   /   /
+    //         /  /    /
+    //        e4  e5   e7
+    UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
+    UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e6(EventSet({&e1}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<IndependentAction>());
+
+    // Since everyone's actions are independent of one another, we expect
+    // that there are no conflicts between each pair of events
+    SECTION("Mutual dependencies")
+    {
+      CHECK_FALSE(e1.is_dependent_with(&e1));
+      CHECK_FALSE(e1.is_dependent_with(&e2));
+      CHECK_FALSE(e1.is_dependent_with(&e3));
+      CHECK_FALSE(e1.is_dependent_with(&e4));
+      CHECK_FALSE(e1.is_dependent_with(&e5));
+      CHECK_FALSE(e1.is_dependent_with(&e6));
+      CHECK_FALSE(e1.is_dependent_with(&e7));
+
+      CHECK_FALSE(e2.is_dependent_with(&e2));
+      CHECK_FALSE(e2.is_dependent_with(&e3));
+      CHECK_FALSE(e2.is_dependent_with(&e4));
+      CHECK_FALSE(e2.is_dependent_with(&e5));
+      CHECK_FALSE(e2.is_dependent_with(&e6));
+      CHECK_FALSE(e2.is_dependent_with(&e7));
+
+      CHECK_FALSE(e3.is_dependent_with(&e3));
+      CHECK_FALSE(e3.is_dependent_with(&e4));
+      CHECK_FALSE(e3.is_dependent_with(&e5));
+      CHECK_FALSE(e3.is_dependent_with(&e6));
+      CHECK_FALSE(e3.is_dependent_with(&e7));
+
+      CHECK_FALSE(e4.is_dependent_with(&e4));
+      CHECK_FALSE(e4.is_dependent_with(&e5));
+      CHECK_FALSE(e4.is_dependent_with(&e6));
+      CHECK_FALSE(e4.is_dependent_with(&e7));
+
+      CHECK_FALSE(e5.is_dependent_with(&e5));
+      CHECK_FALSE(e5.is_dependent_with(&e6));
+      CHECK_FALSE(e5.is_dependent_with(&e7));
+
+      CHECK_FALSE(e6.is_dependent_with(&e6));
+      CHECK_FALSE(e6.is_dependent_with(&e7));
+
+      CHECK_FALSE(e7.is_dependent_with(&e7));
+    }
+
+    SECTION("Mutual conflicts")
+    {
+      CHECK_FALSE(e1.conflicts_with(&e1));
+      CHECK_FALSE(e1.conflicts_with(&e2));
+      CHECK_FALSE(e1.conflicts_with(&e3));
+      CHECK_FALSE(e1.conflicts_with(&e4));
+      CHECK_FALSE(e1.conflicts_with(&e5));
+      CHECK_FALSE(e1.conflicts_with(&e6));
+      CHECK_FALSE(e1.conflicts_with(&e7));
+
+      CHECK_FALSE(e2.conflicts_with(&e1));
+      CHECK_FALSE(e2.conflicts_with(&e2));
+      CHECK_FALSE(e2.conflicts_with(&e3));
+      CHECK_FALSE(e2.conflicts_with(&e4));
+      CHECK_FALSE(e2.conflicts_with(&e5));
+      CHECK_FALSE(e2.conflicts_with(&e6));
+      CHECK_FALSE(e2.conflicts_with(&e7));
+
+      CHECK_FALSE(e3.conflicts_with(&e1));
+      CHECK_FALSE(e3.conflicts_with(&e2));
+      CHECK_FALSE(e3.conflicts_with(&e3));
+      CHECK_FALSE(e3.conflicts_with(&e4));
+      CHECK_FALSE(e3.conflicts_with(&e5));
+      CHECK_FALSE(e3.conflicts_with(&e6));
+      CHECK_FALSE(e3.conflicts_with(&e7));
+
+      CHECK_FALSE(e4.conflicts_with(&e1));
+      CHECK_FALSE(e4.conflicts_with(&e2));
+      CHECK_FALSE(e4.conflicts_with(&e3));
+      CHECK_FALSE(e4.conflicts_with(&e4));
+      CHECK_FALSE(e4.conflicts_with(&e5));
+      CHECK_FALSE(e4.conflicts_with(&e6));
+      CHECK_FALSE(e4.conflicts_with(&e7));
+
+      CHECK_FALSE(e5.conflicts_with(&e1));
+      CHECK_FALSE(e5.conflicts_with(&e2));
+      CHECK_FALSE(e5.conflicts_with(&e3));
+      CHECK_FALSE(e5.conflicts_with(&e4));
+      CHECK_FALSE(e5.conflicts_with(&e5));
+      CHECK_FALSE(e5.conflicts_with(&e6));
+      CHECK_FALSE(e5.conflicts_with(&e7));
+
+      CHECK_FALSE(e6.conflicts_with(&e1));
+      CHECK_FALSE(e6.conflicts_with(&e2));
+      CHECK_FALSE(e6.conflicts_with(&e3));
+      CHECK_FALSE(e6.conflicts_with(&e4));
+      CHECK_FALSE(e6.conflicts_with(&e5));
+      CHECK_FALSE(e6.conflicts_with(&e6));
+      CHECK_FALSE(e6.conflicts_with(&e7));
+
+      CHECK_FALSE(e7.conflicts_with(&e1));
+      CHECK_FALSE(e7.conflicts_with(&e2));
+      CHECK_FALSE(e7.conflicts_with(&e3));
+      CHECK_FALSE(e7.conflicts_with(&e4));
+      CHECK_FALSE(e7.conflicts_with(&e5));
+      CHECK_FALSE(e7.conflicts_with(&e6));
+      CHECK_FALSE(e7.conflicts_with(&e7));
+    }
+  }
+
+  SECTION("General conflicts")
+  {
+    // The following tests concern the given event structure:
+    //                e1
+    //              /   /
+    //            e2    e6
+    //           /  /    /
+    //          e3   /   /
+    //         /  /    /
+    //        e4  e5   e7
+    UnfoldingEvent e1(EventSet(), std::make_shared<DependentAction>());
+    UnfoldingEvent e2(EventSet({&e1}), std::make_shared<DependentAction>());
+    UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e6(EventSet({&e1}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<ConditionallyDependentAction>());
+
+    // Since everyone's actions are independent of one another, we expect
+    // that there are no conflicts between each pair of events
+    SECTION("Mutual dependencies")
+    {
+      CHECK(e1.is_dependent_with(&e1));
+      CHECK(e1.is_dependent_with(&e2));
+      CHECK_FALSE(e1.is_dependent_with(&e3));
+      CHECK_FALSE(e1.is_dependent_with(&e4));
+      CHECK_FALSE(e1.is_dependent_with(&e5));
+      CHECK_FALSE(e1.is_dependent_with(&e6));
+      CHECK(e1.is_dependent_with(&e7));
+
+      CHECK(e2.is_dependent_with(&e2));
+      CHECK_FALSE(e2.is_dependent_with(&e3));
+      CHECK_FALSE(e2.is_dependent_with(&e4));
+      CHECK_FALSE(e2.is_dependent_with(&e5));
+      CHECK_FALSE(e2.is_dependent_with(&e6));
+      CHECK(e2.is_dependent_with(&e7));
+
+      CHECK_FALSE(e3.is_dependent_with(&e3));
+      CHECK_FALSE(e3.is_dependent_with(&e4));
+      CHECK_FALSE(e3.is_dependent_with(&e5));
+      CHECK_FALSE(e3.is_dependent_with(&e6));
+      CHECK_FALSE(e3.is_dependent_with(&e7));
+
+      CHECK_FALSE(e4.is_dependent_with(&e4));
+      CHECK_FALSE(e4.is_dependent_with(&e5));
+      CHECK_FALSE(e4.is_dependent_with(&e6));
+      CHECK_FALSE(e4.is_dependent_with(&e7));
+
+      CHECK_FALSE(e5.is_dependent_with(&e5));
+      CHECK_FALSE(e5.is_dependent_with(&e6));
+      CHECK_FALSE(e5.is_dependent_with(&e7));
+
+      CHECK_FALSE(e6.is_dependent_with(&e6));
+      CHECK_FALSE(e6.is_dependent_with(&e7));
+
+      CHECK_FALSE(e7.is_dependent_with(&e7));
+    }
+
+    SECTION("Mutual conflicts")
+    {
+      // Although e1 is dependent with e1, e2, and e7,
+      // since they are related to one another, they are not
+      // considered to be in conflict
+      CHECK_FALSE(e1.conflicts_with(&e1));
+      CHECK_FALSE(e1.conflicts_with(&e2));
+      CHECK_FALSE(e1.conflicts_with(&e3));
+      CHECK_FALSE(e1.conflicts_with(&e4));
+      CHECK_FALSE(e1.conflicts_with(&e5));
+      CHECK_FALSE(e1.conflicts_with(&e6));
+      CHECK_FALSE(e1.conflicts_with(&e7));
+
+      // Same goes for e2 with e2 and e7
+      CHECK_FALSE(e2.conflicts_with(&e1));
+      CHECK_FALSE(e2.conflicts_with(&e2));
+      CHECK_FALSE(e2.conflicts_with(&e3));
+      CHECK_FALSE(e2.conflicts_with(&e4));
+      CHECK_FALSE(e2.conflicts_with(&e5));
+      CHECK_FALSE(e2.conflicts_with(&e6));
+      CHECK_FALSE(e2.conflicts_with(&e7));
+
+      CHECK_FALSE(e3.conflicts_with(&e1));
+      CHECK_FALSE(e3.conflicts_with(&e2));
+      CHECK_FALSE(e3.conflicts_with(&e3));
+      CHECK_FALSE(e3.conflicts_with(&e4));
+      CHECK_FALSE(e3.conflicts_with(&e5));
+      CHECK_FALSE(e3.conflicts_with(&e6));
+      CHECK_FALSE(e3.conflicts_with(&e7));
+
+      CHECK_FALSE(e4.conflicts_with(&e1));
+      CHECK_FALSE(e4.conflicts_with(&e2));
+      CHECK_FALSE(e4.conflicts_with(&e3));
+      CHECK_FALSE(e4.conflicts_with(&e4));
+      CHECK_FALSE(e4.conflicts_with(&e5));
+      CHECK_FALSE(e4.conflicts_with(&e6));
+      CHECK_FALSE(e4.conflicts_with(&e7));
+
+      CHECK_FALSE(e5.conflicts_with(&e1));
+      CHECK_FALSE(e5.conflicts_with(&e2));
+      CHECK_FALSE(e5.conflicts_with(&e3));
+      CHECK_FALSE(e5.conflicts_with(&e4));
+      CHECK_FALSE(e5.conflicts_with(&e5));
+      CHECK_FALSE(e5.conflicts_with(&e6));
+      CHECK_FALSE(e5.conflicts_with(&e7));
+
+      CHECK_FALSE(e6.conflicts_with(&e1));
+      CHECK_FALSE(e6.conflicts_with(&e2));
+      CHECK_FALSE(e6.conflicts_with(&e3));
+      CHECK_FALSE(e6.conflicts_with(&e4));
+      CHECK_FALSE(e6.conflicts_with(&e5));
+      CHECK_FALSE(e6.conflicts_with(&e6));
+      CHECK_FALSE(e6.conflicts_with(&e7));
+
+      CHECK_FALSE(e7.conflicts_with(&e1));
+      CHECK_FALSE(e7.conflicts_with(&e2));
+      CHECK_FALSE(e7.conflicts_with(&e3));
+      CHECK_FALSE(e7.conflicts_with(&e4));
+      CHECK_FALSE(e7.conflicts_with(&e5));
+      CHECK_FALSE(e7.conflicts_with(&e6));
+      CHECK_FALSE(e7.conflicts_with(&e7));
+    }
+  }
+
+  SECTION("More complicated conflicts")
+  {
+    // The following tests concern the given event structure:
+    //                e1
+    //              /   /
+    //            e2    e6
+    //           /      /
+    //          e3      /
+    //         /  /    e7
+    //        e4  e5
+    UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
+    UnfoldingEvent e2(EventSet({&e1}), std::make_shared<ConditionallyDependentAction>());
+    UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
+    UnfoldingEvent e6(EventSet({&e1}), std::make_shared<DependentAction>());
+    UnfoldingEvent e7(EventSet({&e6}), std::make_shared<IndependentAction>());
+
+    CHECK_FALSE(e1.conflicts_with(&e1));
+    CHECK_FALSE(e1.conflicts_with(&e2));
+    CHECK_FALSE(e1.conflicts_with(&e3));
+    CHECK_FALSE(e1.conflicts_with(&e4));
+    CHECK_FALSE(e1.conflicts_with(&e5));
+    CHECK_FALSE(e1.conflicts_with(&e6));
+    CHECK_FALSE(e1.conflicts_with(&e7));
+
+    // e2 conflicts with e6. Since e6 < e7,
+    // e2 also conflicts with e7
+    CHECK_FALSE(e2.conflicts_with(&e1));
+    CHECK_FALSE(e2.conflicts_with(&e2));
+    CHECK_FALSE(e2.conflicts_with(&e3));
+    CHECK_FALSE(e2.conflicts_with(&e4));
+    CHECK_FALSE(e2.conflicts_with(&e5));
+    CHECK(e2.conflicts_with(&e6));
+    REQUIRE(e2.conflicts_with(&e7));
+
+    // e3 and e6 are dependent and unrelated, so they conflict
+    CHECK_FALSE(e3.conflicts_with(&e1));
+    CHECK_FALSE(e3.conflicts_with(&e2));
+    CHECK_FALSE(e3.conflicts_with(&e3));
+    CHECK_FALSE(e3.conflicts_with(&e4));
+    CHECK_FALSE(e3.conflicts_with(&e5));
+    CHECK(e3.conflicts_with(&e6));
+    CHECK_FALSE(e3.conflicts_with(&e7));
+
+    // Since e3 and e6 conflict and e3 < e4, e4 and e6 conflict
+    CHECK_FALSE(e4.conflicts_with(&e1));
+    CHECK_FALSE(e4.conflicts_with(&e2));
+    CHECK_FALSE(e4.conflicts_with(&e3));
+    CHECK_FALSE(e4.conflicts_with(&e4));
+    CHECK_FALSE(e4.conflicts_with(&e5));
+    CHECK(e4.conflicts_with(&e6));
+    CHECK_FALSE(e4.conflicts_with(&e7));
+
+    // Likewise for e5
+    CHECK_FALSE(e5.conflicts_with(&e1));
+    CHECK_FALSE(e5.conflicts_with(&e2));
+    CHECK_FALSE(e5.conflicts_with(&e3));
+    CHECK_FALSE(e5.conflicts_with(&e4));
+    CHECK_FALSE(e5.conflicts_with(&e5));
+    CHECK(e5.conflicts_with(&e6));
+    CHECK_FALSE(e5.conflicts_with(&e7));
+
+    // Conflicts are symmetric
+    CHECK_FALSE(e6.conflicts_with(&e1));
+    CHECK(e6.conflicts_with(&e2));
+    CHECK(e6.conflicts_with(&e3));
+    CHECK(e6.conflicts_with(&e4));
+    CHECK(e6.conflicts_with(&e5));
+    CHECK_FALSE(e6.conflicts_with(&e6));
+    CHECK_FALSE(e6.conflicts_with(&e7));
+
+    CHECK_FALSE(e7.conflicts_with(&e1));
+    CHECK(e7.conflicts_with(&e2));
+    CHECK_FALSE(e7.conflicts_with(&e3));
+    CHECK_FALSE(e7.conflicts_with(&e4));
+    CHECK_FALSE(e7.conflicts_with(&e5));
+    CHECK_FALSE(e7.conflicts_with(&e6));
+    CHECK_FALSE(e7.conflicts_with(&e7));
+  }
+}
\ No newline at end of file