Add first batch of tests for History class

diff --git a/src/mc/explo/udpor/History.hpp b/src/mc/explo/udpor/History.hpp
index c7512a2..d4b9753 100644 (file)
--- a/src/mc/explo/udpor/History.hpp
+++ b/src/mc/explo/udpor/History.hpp
@@ -48,50 +48,13 @@ private:
    */
   EventSet events_;
 
-  /**
-   * @brief An iterator which traverses the history of a set of events
-   */
-  struct Iterator {
-  private:
-    EventSet frontier;
-    EventSet current_history = EventSet();
-
-    std::optional<std::reference_wrapper<Configuration>> configuration;
-
-    friend History;
-
-  public:
-    Iterator(const EventSet& initial_events, std::optional<std::reference_wrapper<Configuration>> config = std::nullopt)
-        : frontier(initial_events), configuration(config)
-    {
-    }
-
-    Iterator& operator++();
-
-    auto operator->() { return frontier.begin().operator->(); }
-    auto operator*() const { return *frontier.begin(); }
-
-    // If what the iterator sees next is the same, we consider them
-    // to be the same iterator. This way, once the iterator has completed
-    // its search, it will be "equal" to an iterator searching nothing
-    bool operator==(const Iterator& other) { return this->frontier == other.frontier; }
-    bool operator!=(const Iterator& other) { return not(this->operator==(other)); }
-
-    using iterator_category = std::forward_iterator_tag;
-    using difference_type   = int; // # of steps between
-    using value_type        = UnfoldingEvent*;
-    using pointer           = value_type*;
-    using reference         = value_type&;
-  };
-
 public:
-  History()                          = default;
   History(const History&)            = default;
   History& operator=(History const&) = default;
   History(History&&)                 = default;
 
   explicit History(UnfoldingEvent* e) : events_({e}) {}
-  explicit History(EventSet event_set) : events_(std::move(event_set)) {}
+  explicit History(EventSet event_set = EventSet()) : events_(std::move(event_set)) {}
 
   auto begin() const { return Iterator(events_); }
   auto end() const { return Iterator(EventSet()); }
@@ -123,6 +86,41 @@ public:
    */
   EventSet get_all_events() const;
   EventSet get_event_diff_with(const Configuration& config) const;
+
+private:
+  /**
+   * @brief An iterator which traverses the history of a set of events
+   */
+  struct Iterator {
+  private:
+    EventSet frontier;
+    EventSet current_history = EventSet();
+    std::optional<std::reference_wrapper<Configuration>> configuration;
+
+    friend History;
+
+  public:
+    Iterator(const EventSet& initial_events, std::optional<std::reference_wrapper<Configuration>> config = std::nullopt)
+        : frontier(initial_events), configuration(config)
+    {
+    }
+
+    Iterator& operator++();
+    auto operator->() { return frontier.begin().operator->(); }
+    auto operator*() const { return *frontier.begin(); }
+
+    // If what the iterator sees next is the same, we consider them
+    // to be the same iterator. This way, once the iterator has completed
+    // its search, it will be "equal" to an iterator searching nothing
+    bool operator==(const Iterator& other) { return this->frontier == other.frontier; }
+    bool operator!=(const Iterator& other) { return not(this->operator==(other)); }
+
+    using iterator_category = std::forward_iterator_tag;
+    using difference_type   = int; // # of steps between
+    using value_type        = UnfoldingEvent*;
+    using pointer           = value_type*;
+    using reference         = value_type&;
+  };
 };
 
 } // namespace simgrid::mc::udpor

diff --git a/src/mc/explo/udpor/History_test.cpp b/src/mc/explo/udpor/History_test.cpp
new file mode 100644 (file)
index 0000000..a1fbd1a
--- /dev/null
+++ b/src/mc/explo/udpor/History_test.cpp
@@ -0,0 +1,212 @@
+/* Copyright (c) 2017-2023. The SimGrid Team. All rights reserved.               */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#include "src/3rd-party/catch.hpp"
+#include "src/mc/explo/udpor/History.hpp"
+#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
+
+using namespace simgrid::mc::udpor;
+
+TEST_CASE("simgrid::mc::udpor::History: History generation")
+{
+  // The following tests concern the given event tree
+  //        e1
+  //    /      /
+  //  e2        e6
+  //  | \  \  /   /
+  // e3 e4 e5      e7
+  UnfoldingEvent e1;
+  UnfoldingEvent e2{&e1}, e6{&e1};
+  UnfoldingEvent e3{&e2}, e4{&e2};
+  UnfoldingEvent e5{&e2, &e6}, e7{&e6};
+
+  SECTION("History with no events")
+  {
+    History history;
+    REQUIRE(history.get_all_events() == EventSet());
+    REQUIRE_FALSE(history.contains(&e1));
+    REQUIRE_FALSE(history.contains(&e2));
+    REQUIRE_FALSE(history.contains(&e3));
+    REQUIRE_FALSE(history.contains(&e4));
+    REQUIRE_FALSE(history.contains(&e5));
+    REQUIRE_FALSE(history.contains(&e6));
+    REQUIRE_FALSE(history.contains(&e7));
+  }
+
+  SECTION("Histories with a single event")
+  {
+    SECTION("Root event's history has a single event")
+    {
+      History history(&e1);
+      REQUIRE(history.get_all_events() == EventSet({&e1}));
+    }
+
+    SECTION("Check node e2")
+    {
+      History history(&e2);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e2}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE(history.contains(&e2));
+      REQUIRE_FALSE(history.contains(&e3));
+      REQUIRE_FALSE(history.contains(&e4));
+      REQUIRE_FALSE(history.contains(&e5));
+      REQUIRE_FALSE(history.contains(&e6));
+      REQUIRE_FALSE(history.contains(&e7));
+    }
+
+    SECTION("Check node e3")
+    {
+      History history(&e3);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e3}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE(history.contains(&e2));
+      REQUIRE(history.contains(&e3));
+      REQUIRE_FALSE(history.contains(&e4));
+      REQUIRE_FALSE(history.contains(&e5));
+      REQUIRE_FALSE(history.contains(&e6));
+      REQUIRE_FALSE(history.contains(&e7));
+    }
+
+    SECTION("Check node e4")
+    {
+      History history(&e4);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e4}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE(history.contains(&e2));
+      REQUIRE_FALSE(history.contains(&e3));
+      REQUIRE(history.contains(&e4));
+      REQUIRE_FALSE(history.contains(&e5));
+      REQUIRE_FALSE(history.contains(&e6));
+      REQUIRE_FALSE(history.contains(&e7));
+    }
+
+    SECTION("Check node e5")
+    {
+      History history(&e5);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e6, &e5}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE(history.contains(&e2));
+      REQUIRE_FALSE(history.contains(&e3));
+      REQUIRE_FALSE(history.contains(&e4));
+      REQUIRE(history.contains(&e5));
+      REQUIRE(history.contains(&e6));
+      REQUIRE_FALSE(history.contains(&e7));
+    }
+
+    SECTION("Check node e6")
+    {
+      History history(&e6);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e6}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE_FALSE(history.contains(&e2));
+      REQUIRE_FALSE(history.contains(&e3));
+      REQUIRE_FALSE(history.contains(&e4));
+      REQUIRE_FALSE(history.contains(&e5));
+      REQUIRE(history.contains(&e6));
+      REQUIRE_FALSE(history.contains(&e7));
+    }
+
+    SECTION("Check node e7")
+    {
+      History history(&e7);
+      REQUIRE(history.get_all_events() == EventSet({&e1, &e6, &e7}));
+      REQUIRE(history.contains(&e1));
+      REQUIRE_FALSE(history.contains(&e2));
+      REQUIRE_FALSE(history.contains(&e3));
+      REQUIRE_FALSE(history.contains(&e4));
+      REQUIRE_FALSE(history.contains(&e5));
+      REQUIRE(history.contains(&e6));
+      REQUIRE(history.contains(&e7));
+    }
+  }
+
+  SECTION("Histories with multiple nodes")
+  {
+    SECTION("Nodes contained in the same branch")
+    {
+      History history_e1e2(EventSet({&e1, &e2}));
+      REQUIRE(history_e1e2.get_all_events() == EventSet({&e1, &e2}));
+      REQUIRE(history_e1e2.contains(&e1));
+      REQUIRE(history_e1e2.contains(&e2));
+      REQUIRE_FALSE(history_e1e2.contains(&e3));
+      REQUIRE_FALSE(history_e1e2.contains(&e4));
+      REQUIRE_FALSE(history_e1e2.contains(&e5));
+      REQUIRE_FALSE(history_e1e2.contains(&e6));
+      REQUIRE_FALSE(history_e1e2.contains(&e7));
+
+      History history_e1e3(EventSet({&e1, &e3}));
+      REQUIRE(history_e1e3.get_all_events() == EventSet({&e1, &e2, &e3}));
+      REQUIRE(history_e1e3.contains(&e1));
+      REQUIRE(history_e1e3.contains(&e2));
+      REQUIRE(history_e1e3.contains(&e3));
+      REQUIRE_FALSE(history_e1e3.contains(&e4));
+      REQUIRE_FALSE(history_e1e3.contains(&e5));
+      REQUIRE_FALSE(history_e1e3.contains(&e6));
+      REQUIRE_FALSE(history_e1e3.contains(&e7));
+
+      History history_e6e7(EventSet({&e6, &e7}));
+      REQUIRE(history_e6e7.get_all_events() == EventSet({&e1, &e6, &e7}));
+      REQUIRE(history_e6e7.contains(&e1));
+      REQUIRE_FALSE(history_e6e7.contains(&e2));
+      REQUIRE_FALSE(history_e6e7.contains(&e3));
+      REQUIRE_FALSE(history_e6e7.contains(&e4));
+      REQUIRE_FALSE(history_e6e7.contains(&e5));
+      REQUIRE(history_e6e7.contains(&e6));
+      REQUIRE(history_e6e7.contains(&e7));
+    }
+
+    SECTION("Nodes with the same ancestor")
+    {
+      History history_e3e5(EventSet({&e3, &e5}));
+      REQUIRE(history_e3e5.get_all_events() == EventSet({&e1, &e2, &e3, &e5, &e6}));
+      REQUIRE(history_e3e5.contains(&e1));
+      REQUIRE(history_e3e5.contains(&e2));
+      REQUIRE(history_e3e5.contains(&e3));
+      REQUIRE_FALSE(history_e3e5.contains(&e4));
+      REQUIRE(history_e3e5.contains(&e5));
+      REQUIRE(history_e3e5.contains(&e6));
+      REQUIRE_FALSE(history_e3e5.contains(&e7));
+    }
+
+    SECTION("Nodes with the different ancestors")
+    {
+      History history_e4e7(EventSet({&e4, &e7}));
+      REQUIRE(history_e4e7.get_all_events() == EventSet({&e1, &e2, &e4, &e6, &e7}));
+      REQUIRE(history_e4e7.contains(&e1));
+      REQUIRE(history_e4e7.contains(&e2));
+      REQUIRE_FALSE(history_e4e7.contains(&e3));
+      REQUIRE(history_e4e7.contains(&e4));
+      REQUIRE_FALSE(history_e4e7.contains(&e5));
+      REQUIRE(history_e4e7.contains(&e6));
+      REQUIRE(history_e4e7.contains(&e7));
+    }
+
+    SECTION("Large number of nodes")
+    {
+      History history_e2356(EventSet({&e2, &e3, &e5, &e6}));
+      REQUIRE(history_e2356.get_all_events() == EventSet({&e1, &e2, &e3, &e5, &e6}));
+      REQUIRE(history_e2356.contains(&e1));
+      REQUIRE(history_e2356.contains(&e2));
+      REQUIRE(history_e2356.contains(&e3));
+      REQUIRE_FALSE(history_e2356.contains(&e4));
+      REQUIRE(history_e2356.contains(&e5));
+      REQUIRE(history_e2356.contains(&e6));
+      REQUIRE_FALSE(history_e2356.contains(&e7));
+    }
+
+    SECTION("History of the entire graph is the entire graph")
+    {
+      History history_e2356(EventSet({&e1, &e2, &e3, &e4, &e5, &e6, &e7}));
+      REQUIRE(history_e2356.get_all_events() == EventSet({&e1, &e2, &e3, &e4, &e5, &e6, &e7}));
+      REQUIRE(history_e2356.contains(&e1));
+      REQUIRE(history_e2356.contains(&e2));
+      REQUIRE(history_e2356.contains(&e3));
+      REQUIRE(history_e2356.contains(&e4));
+      REQUIRE(history_e2356.contains(&e5));
+      REQUIRE(history_e2356.contains(&e6));
+      REQUIRE(history_e2356.contains(&e7));
+    }
+  }
+}

diff --git a/src/mc/explo/udpor/UnfoldingEvent.cpp b/src/mc/explo/udpor/UnfoldingEvent.cpp
index f3b8172..7294a64 100644 (file)
--- a/src/mc/explo/udpor/UnfoldingEvent.cpp
+++ b/src/mc/explo/udpor/UnfoldingEvent.cpp
@@ -7,6 +7,11 @@
 
 namespace simgrid::mc::udpor {
 
+UnfoldingEvent::UnfoldingEvent(std::initializer_list<UnfoldingEvent*> init_list)
+    : UnfoldingEvent(EventSet(std::move(init_list)))
+{
+}
+
 UnfoldingEvent::UnfoldingEvent(EventSet immediate_causes, std::shared_ptr<Transition> transition)
     : associated_transition(std::move(transition)), immediate_causes(std::move(immediate_causes))
 {

diff --git a/src/mc/explo/udpor/UnfoldingEvent.hpp b/src/mc/explo/udpor/UnfoldingEvent.hpp
index 94cfb5b..2bd29e9 100644 (file)
--- a/src/mc/explo/udpor/UnfoldingEvent.hpp
+++ b/src/mc/explo/udpor/UnfoldingEvent.hpp
@@ -10,6 +10,7 @@
 #include "src/mc/explo/udpor/udpor_forward.hpp"
 #include "src/mc/transition/Transition.hpp"
 
+#include <initializer_list>
 #include <memory>
 #include <string>
 
@@ -17,6 +18,7 @@ namespace simgrid::mc::udpor {
 
 class UnfoldingEvent {
 public:
+  UnfoldingEvent(std::initializer_list<UnfoldingEvent*> init_list);
   UnfoldingEvent(EventSet immediate_causes              = EventSet(),
                  std::shared_ptr<Transition> transition = std::make_unique<Transition>());
 

diff --git a/tools/cmake/Tests.cmake b/tools/cmake/Tests.cmake
index e6d38d8..992afa6 100644 (file)
--- a/tools/cmake/Tests.cmake
+++ b/tools/cmake/Tests.cmake
@@ -132,7 +132,8 @@ if (SIMGRID_HAVE_MC)
                                src/mc/sosp/PageStore_test.cpp
                                src/mc/explo/udpor/EventSet_test.cpp
                                src/mc/explo/udpor/Unfolding_test.cpp
-                               src/mc/explo/udpor/UnfoldingEvent_test.cpp)
+                               src/mc/explo/udpor/UnfoldingEvent_test.cpp
+                               src/mc/explo/udpor/History_test.cpp)
 else()
   set(EXTRA_DIST ${EXTRA_DIST} src/mc/sosp/Snapshot_test.cpp src/mc/sosp/PageStore_test.cpp)
 endif()