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