src/mc/explo/udpor/Configuration_test.cpp

   1 /* Copyright (c) 2017-2023. The SimGrid Team. All rights reserved.               */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/3rd-party/catch.hpp"
   7 #include "src/mc/explo/udpor/Configuration.hpp"
   8 #include "src/mc/explo/udpor/EventSet.hpp"
   9 #include "src/mc/explo/udpor/History.hpp"
  10 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
  11
  12 using namespace simgrid::mc::udpor;
  13
  14 TEST_CASE("simgrid::mc::udpor::Configuration: Constructing Configurations")
  15 {
  16   // The following tests concern the given event structure:
  17   //                e1
  18   //              /
  19   //            e2
  20   //           /
  21   //          e3
  22   //         /  /
  23   //        e4   e5
  24   UnfoldingEvent e1;
  25   UnfoldingEvent e2{&e1};
  26   UnfoldingEvent e3{&e2};
  27   UnfoldingEvent e4{&e3};
  28   UnfoldingEvent e5{&e3};
  29
  30   SECTION("Creating a configuration without events")
  31   {
  32     Configuration C;
  33     REQUIRE(C.get_events().empty());
  34     REQUIRE(C.get_latest_event() == nullptr);
  35   }
  36
  37   SECTION("Creating a configuration with events")
  38   {
  39     // 5 choose 0 = 1 test
  40     REQUIRE_NOTHROW(Configuration({&e1}));
  41
  42     // 5 choose 1 = 5 tests
  43     REQUIRE_THROWS_AS(Configuration({&e2}), std::invalid_argument);
  44     REQUIRE_THROWS_AS(Configuration({&e3}), std::invalid_argument);
  45     REQUIRE_THROWS_AS(Configuration({&e4}), std::invalid_argument);
  46     REQUIRE_THROWS_AS(Configuration({&e5}), std::invalid_argument);
  47
  48     // 5 choose 2 = 10 tests
  49     REQUIRE_NOTHROW(Configuration({&e1, &e2}));
  50     REQUIRE_THROWS_AS(Configuration({&e1, &e3}), std::invalid_argument);
  51     REQUIRE_THROWS_AS(Configuration({&e1, &e4}), std::invalid_argument);
  52     REQUIRE_THROWS_AS(Configuration({&e1, &e5}), std::invalid_argument);
  53     REQUIRE_THROWS_AS(Configuration({&e2, &e3}), std::invalid_argument);
  54     REQUIRE_THROWS_AS(Configuration({&e2, &e4}), std::invalid_argument);
  55     REQUIRE_THROWS_AS(Configuration({&e2, &e5}), std::invalid_argument);
  56     REQUIRE_THROWS_AS(Configuration({&e3, &e4}), std::invalid_argument);
  57     REQUIRE_THROWS_AS(Configuration({&e3, &e5}), std::invalid_argument);
  58     REQUIRE_THROWS_AS(Configuration({&e4, &e5}), std::invalid_argument);
  59
  60     // 5 choose 3 = 10 tests
  61     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}));
  62     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4}), std::invalid_argument);
  63     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e5}), std::invalid_argument);
  64     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4}), std::invalid_argument);
  65     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e5}), std::invalid_argument);
  66     REQUIRE_THROWS_AS(Configuration({&e1, &e4, &e5}), std::invalid_argument);
  67     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4}), std::invalid_argument);
  68     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e5}), std::invalid_argument);
  69     REQUIRE_THROWS_AS(Configuration({&e2, &e4, &e5}), std::invalid_argument);
  70     REQUIRE_THROWS_AS(Configuration({&e3, &e4, &e5}), std::invalid_argument);
  71
  72     // 5 choose 4 = 5 tests
  73     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}));
  74     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e5}));
  75     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4, &e5}), std::invalid_argument);
  76     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4, &e5}), std::invalid_argument);
  77     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4, &e5}), std::invalid_argument);
  78
  79     // 5 choose 5 = 1 test
  80     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4, &e5}));
  81   }
  82 }
  83
  84 TEST_CASE("simgrid::mc::udpor::Configuration: Adding Events")
  85 {
  86   // The following tests concern the given event structure:
  87   //                e1
  88   //              /
  89   //            e2
  90   //           /
  91   //         /  /
  92   //        e3   e4
  93   UnfoldingEvent e1;
  94   UnfoldingEvent e2{&e1};
  95   UnfoldingEvent e3{&e2};
  96   UnfoldingEvent e4{&e2};
  97
  98   REQUIRE_THROWS_AS(Configuration().add_event(nullptr), std::invalid_argument);
  99   REQUIRE_THROWS_AS(Configuration().add_event(&e2), std::invalid_argument);
 100   REQUIRE_THROWS_AS(Configuration().add_event(&e3), std::invalid_argument);
 101   REQUIRE_THROWS_AS(Configuration().add_event(&e4), std::invalid_argument);
 102   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e3), std::invalid_argument);
 103   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e4), std::invalid_argument);
 104
 105   REQUIRE_NOTHROW(Configuration().add_event(&e1));
 106   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e1));
 107   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e2));
 108   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e1));
 109   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e2));
 110   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e3));
 111   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e4));
 112   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e1));
 113   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e2));
 114   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e3));
 115   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e4));
 116   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e1));
 117   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e2));
 118   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e3));
 119   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e4));
 120   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e1));
 121   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e2));
 122   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e3));
 123   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e4));
 124 }
 125
 126 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
 127 {
 128   // The following tests concern the given event structure:
 129   //               e1
 130   //              /
 131   //            e2
 132   //           /
 133   //          e3
 134   //         /
 135   //        e4
 136   UnfoldingEvent e1;
 137   UnfoldingEvent e2{&e1};
 138   UnfoldingEvent e3{&e2};
 139   UnfoldingEvent e4{&e3};
 140
 141   SECTION("Topological ordering for entire set")
 142   {
 143     Configuration C{&e1, &e2, &e3, &e4};
 144     REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 145     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 146   }
 147
 148   SECTION("Topological ordering for subsets")
 149   {
 150     SECTION("No elements")
 151     {
 152       Configuration C;
 153       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{});
 154       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{});
 155     }
 156
 157     SECTION("e1 only")
 158     {
 159       Configuration C{&e1};
 160       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1});
 161       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e1});
 162     }
 163
 164     SECTION("e1 and e2 only")
 165     {
 166       Configuration C{&e1, &e2};
 167       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2});
 168       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e2, &e1});
 169     }
 170
 171     SECTION("e1, e2, and e3 only")
 172     {
 173       Configuration C{&e1, &e2, &e3};
 174       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3});
 175       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e3, &e2, &e1});
 176     }
 177   }
 178 }
 179
 180 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
 181 {
 182   // The following tests concern the given event structure:
 183   //                e1
 184   //              /
 185   //            e2
 186   //           /
 187   //          e3
 188   //         /  /
 189   //        e4   e6
 190   //        /
 191   //       e5
 192   UnfoldingEvent e1;
 193   UnfoldingEvent e2{&e1};
 194   UnfoldingEvent e3{&e2};
 195   UnfoldingEvent e4{&e3};
 196   UnfoldingEvent e5{&e4};
 197   UnfoldingEvent e6{&e3};
 198
 199   SECTION("Topological ordering for subsets")
 200   {
 201     SECTION("No elements")
 202     {
 203       Configuration C;
 204       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{});
 205       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{});
 206     }
 207
 208     SECTION("e1 only")
 209     {
 210       Configuration C{&e1};
 211       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1});
 212       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e1});
 213     }
 214
 215     SECTION("e1 and e2 only")
 216     {
 217       Configuration C{&e1, &e2};
 218       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2});
 219       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e2, &e1});
 220     }
 221
 222     SECTION("e1, e2, and e3 only")
 223     {
 224       Configuration C{&e1, &e2, &e3};
 225       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3});
 226       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e3, &e2, &e1});
 227     }
 228
 229     SECTION("e1, e2, e3, and e6 only")
 230     {
 231       Configuration C{&e1, &e2, &e3, &e6};
 232       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6});
 233       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e6, &e3, &e2, &e1});
 234     }
 235
 236     SECTION("e1, e2, e3, and e4 only")
 237     {
 238       Configuration C{&e1, &e2, &e3, &e4};
 239       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 240       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 241     }
 242
 243     SECTION("e1, e2, e3, e4, and e5 only")
 244     {
 245       Configuration C{&e1, &e2, &e3, &e4, &e5};
 246       REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5});
 247       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 248               std::vector<UnfoldingEvent*>{&e5, &e4, &e3, &e2, &e1});
 249     }
 250
 251     SECTION("e1, e2, e3, e4 and e6 only")
 252     {
 253       // In this case, e4 and e6 are interchangeable. Hence, we have to check
 254       // if the sorting gives us *any* of the combinations
 255       Configuration C{&e1, &e2, &e3, &e4, &e6};
 256       REQUIRE((C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6} ||
 257                C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4}));
 258       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 259                    std::vector<UnfoldingEvent*>{&e6, &e4, &e3, &e2, &e1} ||
 260                C.get_topologically_sorted_events_of_reverse_graph() ==
 261                    std::vector<UnfoldingEvent*>{&e4, &e6, &e3, &e2, &e1}));
 262     }
 263
 264     SECTION("Topological ordering for entire set")
 265     {
 266       // In this case, e4/e5 are both interchangeable with e6. Hence, again we have to check
 267       // if the sorting gives us *any* of the combinations
 268       Configuration C{&e1, &e2, &e3, &e4, &e5, &e6};
 269       REQUIRE((C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5, &e6} ||
 270                C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6, &e5} ||
 271                C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4, &e5}));
 272       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 273                    std::vector<UnfoldingEvent*>{&e6, &e5, &e4, &e3, &e2, &e1} ||
 274                C.get_topologically_sorted_events_of_reverse_graph() ==
 275                    std::vector<UnfoldingEvent*>{&e5, &e6, &e4, &e3, &e2, &e1} ||
 276                C.get_topologically_sorted_events_of_reverse_graph() ==
 277                    std::vector<UnfoldingEvent*>{&e5, &e4, &e6, &e3, &e2, &e1}));
 278     }
 279   }
 280 }
 281
 282 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order Very Complicated")
 283 {
 284   // The following tests concern the given event structure:
 285   //                e1
 286   //              /   /
 287   //            e2    e8
 288   //           /  /    /  /
 289   //          e3   /   /    /
 290   //         /  /    /      e11
 291   //        e4  e6   e7
 292   //        /   /  /   /
 293   //       e5   e9    e10
 294   //        /   /     /
 295   //         /  /   /
 296   //         [   e12    ]
 297   UnfoldingEvent e1;
 298   UnfoldingEvent e2{&e1};
 299   UnfoldingEvent e8{&e1};
 300   UnfoldingEvent e3{&e2};
 301   UnfoldingEvent e4{&e3};
 302   UnfoldingEvent e5{&e4};
 303   UnfoldingEvent e6{&e4};
 304   UnfoldingEvent e7{&e2, &e8};
 305   UnfoldingEvent e9{&e6, &e7};
 306   UnfoldingEvent e10{&e7};
 307   UnfoldingEvent e11{&e8};
 308   UnfoldingEvent e12{&e5, &e9, &e10};
 309   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12};
 310
 311   SECTION("Test every combination of the maximal configuration (forward graph)")
 312   {
 313     // To test this, we ensure that for the `i`th event
 314     // in `ordered_events`, each event in `ordered_events[0...<i]
 315     // is contained in the history of `ordered_events[i]`.
 316     EventSet events_seen;
 317     const auto ordered_events = C.get_topologically_sorted_events();
 318
 319     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](UnfoldingEvent* e) {
 320       History history(e);
 321       for (auto* e_hist : history) {
 322         // In this demo, we want to make sure that
 323         // we don't mark not yet seeing `e` as an error.
 324         // The history of `e` traverses `e` itself. All
 325         // other events in e's history are included in
 326         if (e_hist == e)
 327           continue;
 328
 329         // If this event has not been "seen" before,
 330         // this implies that event `e` appears earlier
 331         // in the list than one of its dependencies
 332         REQUIRE(events_seen.contains(e_hist));
 333       }
 334       events_seen.insert(e);
 335     });
 336   }
 337
 338   SECTION("Test every combination of the maximal configuration (reverse graph)")
 339   {
 340     // To test this, we ensure that for the `i`th event
 341     // in `ordered_events`, no event in `ordered_events[0...<i]
 342     // is contained in the history of `ordered_events[i]`.
 343     EventSet events_seen;
 344     const auto ordered_events = C.get_topologically_sorted_events_of_reverse_graph();
 345
 346     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](UnfoldingEvent* e) {
 347       History history(e);
 348
 349       for (auto* e_hist : history) {
 350         // Unlike the test above, we DO want to ensure
 351         // that `e` itself ALSO isn't yet seen
 352
 353         // If this event has been "seen" before,
 354         // this implies that event `e` appears later
 355         // in the list than one of its ancestors
 356         REQUIRE_FALSE(events_seen.contains(e_hist));
 357       }
 358       events_seen.insert(e);
 359     });
 360   }
 361 }