src/mc/explo/udpor/EventSet_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/EventSet.hpp"
   8 #include "src/mc/explo/udpor/History.hpp"
   9 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
  10 #include "src/mc/explo/udpor/udpor_tests_private.hpp"
  11 #include "src/xbt/utils/iter/LazyPowerset.hpp"
  12
  13 using namespace simgrid::xbt;
  14 using namespace simgrid::mc::udpor;
  15
  16 TEST_CASE("simgrid::mc::udpor::EventSet: Initial conditions when creating sets")
  17 {
  18   SECTION("Initialization with no elements")
  19   {
  20     SECTION("Default initializer")
  21     {
  22       EventSet event_set;
  23       REQUIRE(event_set.size() == 0);
  24       REQUIRE(event_set.empty());
  25     }
  26
  27     SECTION("Set initializer")
  28     {
  29       EventSet event_set({});
  30       REQUIRE(event_set.size() == 0);
  31       REQUIRE(event_set.empty());
  32     }
  33
  34     SECTION("List initialization")
  35     {
  36       EventSet event_set{};
  37       REQUIRE(event_set.size() == 0);
  38       REQUIRE(event_set.empty());
  39     }
  40   }
  41
  42   SECTION("Initialization with one or more elements")
  43   {
  44     UnfoldingEvent e1, e2, e3;
  45
  46     SECTION("Set initializer")
  47     {
  48       EventSet event_set({&e1, &e2, &e3});
  49       REQUIRE(event_set.size() == 3);
  50       REQUIRE(event_set.contains(&e1));
  51       REQUIRE(event_set.contains(&e2));
  52       REQUIRE(event_set.contains(&e3));
  53       REQUIRE_FALSE(event_set.empty());
  54     }
  55
  56     SECTION("List initialization")
  57     {
  58       EventSet event_set{&e1, &e2, &e3};
  59       REQUIRE(event_set.size() == 3);
  60       REQUIRE(event_set.contains(&e1));
  61       REQUIRE(event_set.contains(&e2));
  62       REQUIRE(event_set.contains(&e3));
  63       REQUIRE_FALSE(event_set.empty());
  64     }
  65   }
  66 }
  67
  68 TEST_CASE("simgrid::mc::udpor::EventSet: Insertions")
  69 {
  70   EventSet event_set;
  71   UnfoldingEvent e1, e2, e3;
  72
  73   SECTION("Inserting unique elements")
  74   {
  75     event_set.insert(&e1);
  76     REQUIRE(event_set.size() == 1);
  77     REQUIRE(event_set.contains(&e1));
  78     REQUIRE_FALSE(event_set.empty());
  79
  80     event_set.insert(&e2);
  81     REQUIRE(event_set.size() == 2);
  82     REQUIRE(event_set.contains(&e2));
  83     REQUIRE_FALSE(event_set.empty());
  84
  85     SECTION("Check contains inserted elements")
  86     {
  87       REQUIRE(event_set.contains(&e1));
  88       REQUIRE(event_set.contains(&e2));
  89       REQUIRE_FALSE(event_set.contains(&e3));
  90     }
  91   }
  92
  93   SECTION("Inserting duplicate elements")
  94   {
  95     event_set.insert(&e1);
  96     REQUIRE(event_set.size() == 1);
  97     REQUIRE(event_set.contains(&e1));
  98     REQUIRE_FALSE(event_set.empty());
  99
 100     event_set.insert(&e1);
 101     REQUIRE(event_set.size() == 1);
 102     REQUIRE(event_set.contains(&e1));
 103     REQUIRE_FALSE(event_set.empty());
 104
 105     SECTION("Check contains inserted elements")
 106     {
 107       REQUIRE(event_set.contains(&e1));
 108       REQUIRE_FALSE(event_set.contains(&e2));
 109       REQUIRE_FALSE(event_set.contains(&e3));
 110     }
 111   }
 112 }
 113
 114 TEST_CASE("simgrid::mc::udpor::EventSet: Deletions")
 115 {
 116   UnfoldingEvent e1;
 117   UnfoldingEvent e2;
 118   UnfoldingEvent e3;
 119   UnfoldingEvent e4;
 120   EventSet event_set({&e1, &e2, &e3});
 121
 122   SECTION("Remove an element already present")
 123   {
 124     REQUIRE(event_set.contains(&e1));
 125
 126     // Recall that event_set = {e2, e3}
 127     event_set.remove(&e1);
 128
 129     // Check that
 130     // 1. the size decreases by exactly 1
 131     // 2. the set remains unempty
 132     // 3. the other elements are still contained in the set
 133     REQUIRE(event_set.size() == 2);
 134     REQUIRE_FALSE(event_set.contains(&e1));
 135     REQUIRE(event_set.contains(&e2));
 136     REQUIRE(event_set.contains(&e3));
 137     REQUIRE_FALSE(event_set.empty());
 138
 139     SECTION("Remove a single element more than once")
 140     {
 141       // Recall that event_set = {e2, e3}
 142       event_set.remove(&e1);
 143       REQUIRE(event_set.size() == 2);
 144       REQUIRE_FALSE(event_set.contains(&e1));
 145       REQUIRE(event_set.contains(&e2));
 146       REQUIRE(event_set.contains(&e3));
 147       REQUIRE_FALSE(event_set.empty());
 148     }
 149
 150     SECTION("Remove more than one element")
 151     {
 152       // Recall that event_set = {e3}
 153       event_set.remove(&e2);
 154
 155       REQUIRE(event_set.size() == 1);
 156       REQUIRE_FALSE(event_set.contains(&e1));
 157       REQUIRE_FALSE(event_set.contains(&e2));
 158       REQUIRE(event_set.contains(&e3));
 159       REQUIRE_FALSE(event_set.empty());
 160
 161       // Recall that event_set = {}
 162       event_set.remove(&e3);
 163
 164       REQUIRE(event_set.size() == 0);
 165       REQUIRE_FALSE(event_set.contains(&e1));
 166       REQUIRE_FALSE(event_set.contains(&e2));
 167       REQUIRE_FALSE(event_set.contains(&e3));
 168       REQUIRE(event_set.empty());
 169     }
 170   }
 171
 172   SECTION("Remove an element absent from the set")
 173   {
 174     REQUIRE_FALSE(event_set.contains(&e4));
 175
 176     // Recall that event_set = {e1, e2, e3}
 177     event_set.remove(&e4);
 178     REQUIRE(event_set.size() == 3);
 179     REQUIRE(event_set.contains(&e1));
 180     REQUIRE(event_set.contains(&e2));
 181     REQUIRE(event_set.contains(&e3));
 182
 183     // Ensure e4 isn't somehow added
 184     REQUIRE_FALSE(event_set.contains(&e4));
 185     REQUIRE_FALSE(event_set.empty());
 186   }
 187 }
 188
 189 TEST_CASE("simgrid::mc::udpor::EventSet: Set Equality")
 190 {
 191   UnfoldingEvent e1;
 192   UnfoldingEvent e2;
 193   UnfoldingEvent e3;
 194   UnfoldingEvent e4;
 195   EventSet A{&e1, &e2, &e3}, B{&e1, &e2, &e3}, C{&e1, &e2, &e3};
 196
 197   SECTION("Equality implies containment")
 198   {
 199     REQUIRE(A == B);
 200
 201     for (const auto& e : A) {
 202       REQUIRE(B.contains(e));
 203     }
 204
 205     for (const auto& e : B) {
 206       REQUIRE(A.contains(e));
 207     }
 208   }
 209
 210   SECTION("Containment implies equality")
 211   {
 212     for (const auto& e : A) {
 213       REQUIRE(B.contains(e));
 214     }
 215
 216     for (const auto& e : C) {
 217       REQUIRE(C.contains(e));
 218     }
 219
 220     REQUIRE(A == C);
 221   }
 222
 223   SECTION("Equality is an equivalence relation")
 224   {
 225     // Reflexive
 226     REQUIRE(A == A);
 227     REQUIRE(B == B);
 228     REQUIRE(C == C);
 229
 230     // Symmetric
 231     REQUIRE(A == B);
 232     REQUIRE(B == A);
 233     REQUIRE(A == C);
 234     REQUIRE(C == A);
 235     REQUIRE(B == C);
 236     REQUIRE(C == B);
 237
 238     // Transitive
 239     REQUIRE(A == B);
 240     REQUIRE(B == C);
 241     REQUIRE(A == C);
 242   }
 243
 244   SECTION("Equality after copy (assignment + constructor)")
 245   {
 246     EventSet A_copy = A;
 247     EventSet A_copy2(A);
 248
 249     REQUIRE(A == A_copy);
 250     REQUIRE(A == A_copy2);
 251   }
 252
 253   SECTION("Equality after move constructor")
 254   {
 255     EventSet A_copy = A;
 256     EventSet A_move(std::move(A));
 257     REQUIRE(A_move == A_copy);
 258   }
 259
 260   SECTION("Equality after move-assignment")
 261   {
 262     EventSet A_copy = A;
 263     EventSet A_move = std::move(A);
 264     REQUIRE(A_move == A_copy);
 265   }
 266 }
 267
 268 TEST_CASE("simgrid::mc::udpor::EventSet: Set Union Tests")
 269 {
 270   UnfoldingEvent e1, e2, e3, e4;
 271
 272   // C = A + B
 273   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3};
 274
 275   SECTION("Unions with no effect")
 276   {
 277     EventSet A_copy = A;
 278
 279     SECTION("Self union")
 280     {
 281       // A = A union A
 282       EventSet A_union = A.make_union(A);
 283       REQUIRE(A == A_copy);
 284
 285       A.form_union(A);
 286       REQUIRE(A == A_copy);
 287     }
 288
 289     SECTION("Union with empty set")
 290     {
 291       // A = A union empty set
 292       EventSet A_union = A.make_union(EventSet());
 293       REQUIRE(A == A_union);
 294
 295       A.form_union(EventSet());
 296       REQUIRE(A == A_copy);
 297     }
 298
 299     SECTION("Union with an equivalent set")
 300     {
 301       // A = A union B if B == A
 302       EventSet A_equiv{&e1, &e2, &e3};
 303       REQUIRE(A == A_equiv);
 304
 305       EventSet A_union = A.make_union(A_equiv);
 306       REQUIRE(A_union == A_copy);
 307
 308       A.form_union(A_equiv);
 309       REQUIRE(A == A_copy);
 310     }
 311
 312     SECTION("Union with a subset")
 313     {
 314       // A = A union D if D is a subset of A
 315       EventSet A_union = A.make_union(D);
 316       REQUIRE(A == A_union);
 317
 318       A.form_union(D);
 319       REQUIRE(A == A_copy);
 320     }
 321   }
 322
 323   SECTION("Unions with partial overlaps")
 324   {
 325     EventSet A_union_B = A.make_union(B);
 326     REQUIRE(A_union_B == C);
 327
 328     A.form_union(B);
 329     REQUIRE(A == C);
 330
 331     EventSet B_union_D = B.make_union(D);
 332     REQUIRE(B_union_D == C);
 333
 334     B.form_union(D);
 335     REQUIRE(B == C);
 336   }
 337
 338   SECTION("Set union properties")
 339   {
 340     SECTION("Union operator is symmetric")
 341     {
 342       EventSet A_union_B = A.make_union(B);
 343       EventSet B_union_A = B.make_union(A);
 344       REQUIRE(A_union_B == B_union_A);
 345     }
 346
 347     SECTION("Union operator commutes")
 348     {
 349       // The last SECTION tested pair-wise
 350       // equivalence, so we only check
 351       // one of each pai
 352       EventSet AD = A.make_union(D);
 353       EventSet AC = A.make_union(C);
 354       EventSet CD = D.make_union(C);
 355
 356       EventSet ADC = AD.make_union(C);
 357       EventSet ACD = AC.make_union(D);
 358       EventSet CDA = CD.make_union(A);
 359
 360       REQUIRE(ADC == ACD);
 361       REQUIRE(ACD == CDA);
 362
 363       // Test `form_union()` in the same way
 364
 365       EventSet A_copy = A;
 366       EventSet C_copy = C;
 367       EventSet D_copy = D;
 368
 369       A.form_union(C_copy);
 370       A.form_union(D_copy);
 371
 372       D.form_union(A_copy);
 373       D.form_union(C_copy);
 374
 375       C.form_union(A);
 376       C.form_union(D);
 377
 378       REQUIRE(A == D);
 379       REQUIRE(C == D);
 380       REQUIRE(A == C);
 381     }
 382   }
 383 }
 384
 385 TEST_CASE("simgrid::mc::udpor::EventSet: Set Difference Tests")
 386 {
 387   UnfoldingEvent e1;
 388   UnfoldingEvent e2;
 389   UnfoldingEvent e3;
 390   UnfoldingEvent e4;
 391
 392   // C = A + B
 393   // A is a subset of C
 394   // B is a subset of C
 395   // D is a subset of A and C
 396   // E is a subset of B and C
 397   // F is a subset of A, C, and D
 398   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3}, E{&e4}, F{&e1};
 399
 400   SECTION("Difference with no effect")
 401   {
 402     SECTION("Difference with empty set")
 403     {
 404       EventSet A_copy = A.subtracting(EventSet());
 405       REQUIRE(A == A_copy);
 406
 407       A.subtract(EventSet());
 408       REQUIRE(A == A_copy);
 409     }
 410
 411     SECTION("Difference with empty intersection")
 412     {
 413       // A intersection E = empty set
 414       EventSet A_copy = A.subtracting(E);
 415       REQUIRE(A == A_copy);
 416
 417       A.subtract(E);
 418       REQUIRE(A == A_copy);
 419
 420       EventSet D_copy = D.subtracting(E);
 421       REQUIRE(D == D_copy);
 422
 423       D.subtract(E);
 424       REQUIRE(D == D_copy);
 425     }
 426   }
 427
 428   SECTION("Difference with some overlap")
 429   {
 430     // A - B = {&e1} = F
 431     EventSet A_minus_B = A.subtracting(B);
 432     REQUIRE(A_minus_B == F);
 433
 434     // B - D = {&e2, &e4}
 435     EventSet B_minus_D = B.subtracting(D);
 436     REQUIRE(B_minus_D == EventSet({&e2, &e4}));
 437   }
 438
 439   SECTION("Difference with complete overlap")
 440   {
 441     SECTION("Difference with same set gives empty set")
 442     {
 443       REQUIRE(A.subtracting(A) == EventSet());
 444       REQUIRE(B.subtracting(B) == EventSet());
 445       REQUIRE(C.subtracting(C) == EventSet());
 446       REQUIRE(D.subtracting(D) == EventSet());
 447       REQUIRE(E.subtracting(E) == EventSet());
 448       REQUIRE(F.subtracting(F) == EventSet());
 449     }
 450
 451     SECTION("Difference with superset gives empty set")
 452     {
 453       REQUIRE(A.subtracting(C) == EventSet());
 454       REQUIRE(B.subtracting(C) == EventSet());
 455       REQUIRE(D.subtracting(A) == EventSet());
 456       REQUIRE(D.subtracting(C) == EventSet());
 457       REQUIRE(E.subtracting(B) == EventSet());
 458       REQUIRE(E.subtracting(C) == EventSet());
 459       REQUIRE(F.subtracting(A) == EventSet());
 460       REQUIRE(F.subtracting(C) == EventSet());
 461       REQUIRE(F.subtracting(D) == EventSet());
 462     }
 463   }
 464 }
 465
 466 TEST_CASE("simgrid::mc::udpor::EventSet: Subset Tests")
 467 {
 468   UnfoldingEvent e1, e2, e3, e4;
 469
 470   // A is a subset of C only
 471   // B is a subset of C only
 472   // D is a subset of C and A
 473   // D is NOT a subset of B
 474   // B is NOT a subset of D
 475   // ...
 476   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3}, E{&e2, &e3}, F{&e1, &e2, &e3};
 477
 478   SECTION("Subset operator properties")
 479   {
 480     SECTION("Subset operator is not commutative")
 481     {
 482       REQUIRE(A.is_subset_of(C));
 483       REQUIRE_FALSE(C.is_subset_of(A));
 484
 485       SECTION("Commutativity implies equality and vice versa")
 486       {
 487         REQUIRE(A.is_subset_of(F));
 488         REQUIRE(F.is_subset_of(A));
 489         REQUIRE(A == F);
 490
 491         REQUIRE(C == C);
 492         REQUIRE(A.is_subset_of(F));
 493         REQUIRE(F.is_subset_of(A));
 494       }
 495     }
 496
 497     SECTION("Subset operator is transitive")
 498     {
 499       REQUIRE(D.is_subset_of(A));
 500       REQUIRE(A.is_subset_of(C));
 501       REQUIRE(D.is_subset_of(C));
 502       REQUIRE(E.is_subset_of(B));
 503       REQUIRE(B.is_subset_of(C));
 504       REQUIRE(E.is_subset_of(C));
 505     }
 506
 507     SECTION("Subset operator is reflexive")
 508     {
 509       REQUIRE(A.is_subset_of(A));
 510       REQUIRE(B.is_subset_of(B));
 511       REQUIRE(C.is_subset_of(C));
 512       REQUIRE(D.is_subset_of(D));
 513       REQUIRE(E.is_subset_of(E));
 514       REQUIRE(F.is_subset_of(F));
 515     }
 516   }
 517 }
 518
 519 TEST_CASE("simgrid::mc::udpor::EventSet: Testing Configurations")
 520 {
 521   // The following tests concern the given event structure:
 522   //                e1
 523   //              /    /
 524   //            e2      e5
 525   //           /  /      /
 526   //          e3  e4     e6
 527   // The tests enumerate all possible subsets of the events
 528   // in the structure and test whether those subsets are
 529   // maximal and/or valid configurations
 530   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 531   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 532   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 533   UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 534   UnfoldingEvent e5(EventSet({&e1}), std::make_shared<IndependentAction>());
 535   UnfoldingEvent e6(EventSet({&e5}), std::make_shared<IndependentAction>());
 536
 537   SECTION("Valid Configurations")
 538   {
 539     SECTION("The empty set is valid")
 540     {
 541       REQUIRE(EventSet().is_valid_configuration());
 542     }
 543
 544     SECTION("The set with only the root event is valid")
 545     {
 546       REQUIRE(EventSet({&e1}).is_valid_configuration());
 547     }
 548
 549     SECTION("All sets of maximal events are valid configurations")
 550     {
 551       REQUIRE(EventSet({&e1}).is_valid_configuration());
 552       REQUIRE(EventSet({&e1, &e2}).is_valid_configuration());
 553       REQUIRE(EventSet({&e1, &e2, &e3}).is_valid_configuration());
 554       REQUIRE(EventSet({&e1, &e2, &e4}).is_valid_configuration());
 555       REQUIRE(EventSet({&e1, &e5}).is_valid_configuration());
 556       REQUIRE(EventSet({&e1, &e5, &e6}).is_valid_configuration());
 557       REQUIRE(EventSet({&e1, &e2, &e5}).is_valid_configuration());
 558       REQUIRE(EventSet({&e1, &e2, &e5, &e6}).is_valid_configuration());
 559       REQUIRE(EventSet({&e1, &e2, &e3, &e4}).is_valid_configuration());
 560       REQUIRE(EventSet({&e1, &e2, &e3, &e5}).is_valid_configuration());
 561       REQUIRE(EventSet({&e1, &e2, &e4, &e5}).is_valid_configuration());
 562       REQUIRE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_valid_configuration());
 563       REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_valid_configuration());
 564       REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 565     }
 566   }
 567
 568   SECTION("Configuration checks")
 569   {
 570     // 6 choose 0 = 1 test
 571     REQUIRE(EventSet().is_valid_configuration());
 572
 573     // 6 choose 1 = 6 tests
 574     REQUIRE(EventSet({&e1}).is_valid_configuration());
 575     REQUIRE_FALSE(EventSet({&e2}).is_valid_configuration());
 576     REQUIRE_FALSE(EventSet({&e3}).is_valid_configuration());
 577     REQUIRE_FALSE(EventSet({&e4}).is_valid_configuration());
 578     REQUIRE_FALSE(EventSet({&e5}).is_valid_configuration());
 579     REQUIRE_FALSE(EventSet({&e6}).is_valid_configuration());
 580
 581     // 6 choose 2 = 15 tests
 582     REQUIRE(EventSet({&e1, &e2}).is_valid_configuration());
 583     REQUIRE_FALSE(EventSet({&e1, &e3}).is_valid_configuration());
 584     REQUIRE_FALSE(EventSet({&e1, &e4}).is_valid_configuration());
 585     REQUIRE(EventSet({&e1, &e5}).is_valid_configuration());
 586     REQUIRE_FALSE(EventSet({&e1, &e6}).is_valid_configuration());
 587     REQUIRE_FALSE(EventSet({&e2, &e3}).is_valid_configuration());
 588     REQUIRE_FALSE(EventSet({&e2, &e4}).is_valid_configuration());
 589     REQUIRE_FALSE(EventSet({&e2, &e5}).is_valid_configuration());
 590     REQUIRE_FALSE(EventSet({&e2, &e6}).is_valid_configuration());
 591     REQUIRE_FALSE(EventSet({&e3, &e4}).is_valid_configuration());
 592     REQUIRE_FALSE(EventSet({&e3, &e5}).is_valid_configuration());
 593     REQUIRE_FALSE(EventSet({&e3, &e6}).is_valid_configuration());
 594     REQUIRE_FALSE(EventSet({&e4, &e5}).is_valid_configuration());
 595     REQUIRE_FALSE(EventSet({&e4, &e6}).is_valid_configuration());
 596     REQUIRE_FALSE(EventSet({&e5, &e6}).is_valid_configuration());
 597
 598     // 6 choose 3 = 20 tests
 599     REQUIRE(EventSet({&e1, &e2, &e3}).is_valid_configuration());
 600     REQUIRE(EventSet({&e1, &e2, &e4}).is_valid_configuration());
 601     REQUIRE(EventSet({&e1, &e2, &e5}).is_valid_configuration());
 602     REQUIRE_FALSE(EventSet({&e1, &e2, &e6}).is_valid_configuration());
 603     REQUIRE_FALSE(EventSet({&e1, &e3, &e4}).is_valid_configuration());
 604     REQUIRE_FALSE(EventSet({&e1, &e3, &e5}).is_valid_configuration());
 605     REQUIRE_FALSE(EventSet({&e1, &e3, &e6}).is_valid_configuration());
 606     REQUIRE_FALSE(EventSet({&e1, &e4, &e5}).is_valid_configuration());
 607     REQUIRE_FALSE(EventSet({&e1, &e4, &e6}).is_valid_configuration());
 608     REQUIRE(EventSet({&e1, &e5, &e6}).is_valid_configuration());
 609     REQUIRE_FALSE(EventSet({&e2, &e3, &e4}).is_valid_configuration());
 610     REQUIRE_FALSE(EventSet({&e2, &e3, &e5}).is_valid_configuration());
 611     REQUIRE_FALSE(EventSet({&e2, &e3, &e6}).is_valid_configuration());
 612     REQUIRE_FALSE(EventSet({&e2, &e4, &e5}).is_valid_configuration());
 613     REQUIRE_FALSE(EventSet({&e2, &e4, &e6}).is_valid_configuration());
 614     REQUIRE_FALSE(EventSet({&e2, &e5, &e6}).is_valid_configuration());
 615     REQUIRE_FALSE(EventSet({&e3, &e4, &e5}).is_valid_configuration());
 616     REQUIRE_FALSE(EventSet({&e3, &e4, &e6}).is_valid_configuration());
 617     REQUIRE_FALSE(EventSet({&e3, &e5, &e6}).is_valid_configuration());
 618     REQUIRE_FALSE(EventSet({&e4, &e5, &e6}).is_valid_configuration());
 619
 620     // 6 choose 4 = 15 tests
 621     REQUIRE(EventSet({&e1, &e2, &e3, &e4}).is_valid_configuration());
 622     REQUIRE(EventSet({&e1, &e2, &e3, &e5}).is_valid_configuration());
 623     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_valid_configuration());
 624     REQUIRE(EventSet({&e1, &e2, &e4, &e5}).is_valid_configuration());
 625     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_valid_configuration());
 626     REQUIRE(EventSet({&e1, &e2, &e5, &e6}).is_valid_configuration());
 627     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_valid_configuration());
 628     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_valid_configuration());
 629     REQUIRE_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_valid_configuration());
 630     REQUIRE_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_valid_configuration());
 631     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_valid_configuration());
 632     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_valid_configuration());
 633     REQUIRE_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_valid_configuration());
 634     REQUIRE_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_valid_configuration());
 635     REQUIRE_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_valid_configuration());
 636
 637     // 6 choose 5 = 6 tests
 638     REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_valid_configuration());
 639     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_valid_configuration());
 640     REQUIRE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_valid_configuration());
 641     REQUIRE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_valid_configuration());
 642     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_valid_configuration());
 643     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 644
 645     // 6 choose 6 = 1 test
 646     REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 647   }
 648
 649   SECTION("Maximal event sets")
 650   {
 651     // 6 choose 0 = 1 test
 652     REQUIRE(EventSet().is_maximal());
 653
 654     // 6 choose 1 = 6 tests
 655     REQUIRE(EventSet({&e1}).is_maximal());
 656     REQUIRE(EventSet({&e2}).is_maximal());
 657     REQUIRE(EventSet({&e3}).is_maximal());
 658     REQUIRE(EventSet({&e4}).is_maximal());
 659     REQUIRE(EventSet({&e5}).is_maximal());
 660     REQUIRE(EventSet({&e6}).is_maximal());
 661
 662     // 6 choose 2 = 15 tests
 663     REQUIRE_FALSE(EventSet({&e1, &e2}).is_maximal());
 664     REQUIRE_FALSE(EventSet({&e1, &e3}).is_maximal());
 665     REQUIRE_FALSE(EventSet({&e1, &e4}).is_maximal());
 666     REQUIRE_FALSE(EventSet({&e1, &e5}).is_maximal());
 667     REQUIRE_FALSE(EventSet({&e1, &e6}).is_maximal());
 668     REQUIRE_FALSE(EventSet({&e2, &e3}).is_maximal());
 669     REQUIRE_FALSE(EventSet({&e2, &e4}).is_maximal());
 670     REQUIRE(EventSet({&e2, &e5}).is_maximal());
 671     REQUIRE(EventSet({&e2, &e6}).is_maximal());
 672     REQUIRE(EventSet({&e3, &e4}).is_maximal());
 673     REQUIRE(EventSet({&e3, &e5}).is_maximal());
 674     REQUIRE(EventSet({&e3, &e6}).is_maximal());
 675     REQUIRE(EventSet({&e4, &e5}).is_maximal());
 676     REQUIRE(EventSet({&e4, &e6}).is_maximal());
 677     REQUIRE_FALSE(EventSet({&e5, &e6}).is_maximal());
 678
 679     // 6 choose 3 = 20 tests
 680     REQUIRE_FALSE(EventSet({&e1, &e2, &e3}).is_maximal());
 681     REQUIRE_FALSE(EventSet({&e1, &e2, &e4}).is_maximal());
 682     REQUIRE_FALSE(EventSet({&e1, &e2, &e5}).is_maximal());
 683     REQUIRE_FALSE(EventSet({&e1, &e2, &e6}).is_maximal());
 684     REQUIRE_FALSE(EventSet({&e1, &e3, &e4}).is_maximal());
 685     REQUIRE_FALSE(EventSet({&e1, &e3, &e5}).is_maximal());
 686     REQUIRE_FALSE(EventSet({&e1, &e3, &e6}).is_maximal());
 687     REQUIRE_FALSE(EventSet({&e1, &e4, &e5}).is_maximal());
 688     REQUIRE_FALSE(EventSet({&e1, &e4, &e6}).is_maximal());
 689     REQUIRE_FALSE(EventSet({&e1, &e5, &e6}).is_maximal());
 690     REQUIRE_FALSE(EventSet({&e2, &e3, &e4}).is_maximal());
 691     REQUIRE_FALSE(EventSet({&e2, &e3, &e5}).is_maximal());
 692     REQUIRE_FALSE(EventSet({&e2, &e3, &e6}).is_maximal());
 693     REQUIRE_FALSE(EventSet({&e2, &e4, &e5}).is_maximal());
 694     REQUIRE_FALSE(EventSet({&e2, &e4, &e6}).is_maximal());
 695     REQUIRE_FALSE(EventSet({&e2, &e5, &e6}).is_maximal());
 696     REQUIRE(EventSet({&e3, &e4, &e5}).is_maximal());
 697     REQUIRE(EventSet({&e3, &e4, &e6}).is_maximal());
 698     REQUIRE_FALSE(EventSet({&e3, &e5, &e6}).is_maximal());
 699     REQUIRE_FALSE(EventSet({&e4, &e5, &e6}).is_maximal());
 700
 701     // 6 choose 4 = 15 tests
 702     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4}).is_maximal());
 703     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e5}).is_maximal());
 704     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_maximal());
 705     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e5}).is_maximal());
 706     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_maximal());
 707     REQUIRE_FALSE(EventSet({&e1, &e2, &e5, &e6}).is_maximal());
 708     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_maximal());
 709     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_maximal());
 710     REQUIRE_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_maximal());
 711     REQUIRE_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_maximal());
 712     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_maximal());
 713     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_maximal());
 714     REQUIRE_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_maximal());
 715     REQUIRE_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_maximal());
 716     REQUIRE_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_maximal());
 717
 718     // 6 choose 5 = 6 tests
 719     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_maximal());
 720     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_maximal());
 721     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_maximal());
 722     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_maximal());
 723     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_maximal());
 724     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_maximal());
 725
 726     // 6 choose 6 = 1 test
 727     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_maximal());
 728   }
 729 }
 730
 731 TEST_CASE("simgrid::mc::udpor::EventSet: Moving into a collection")
 732 {
 733   UnfoldingEvent e1;
 734   UnfoldingEvent e2;
 735   UnfoldingEvent e3;
 736   UnfoldingEvent e4;
 737
 738   EventSet A({&e1});
 739   EventSet B({&e1, &e2});
 740   EventSet C({&e1, &e2, &e3});
 741   EventSet D({&e1, &e2, &e3, &e4});
 742
 743   EventSet A_copy = A;
 744   EventSet B_copy = B;
 745   EventSet C_copy = C;
 746   EventSet D_copy = D;
 747
 748   std::vector<const UnfoldingEvent*> actual_A = std::move(A).move_into_vector();
 749   std::vector<const UnfoldingEvent*> actual_B = std::move(B).move_into_vector();
 750   std::vector<const UnfoldingEvent*> actual_C = std::move(C).move_into_vector();
 751   std::vector<const UnfoldingEvent*> actual_D = std::move(D).move_into_vector();
 752
 753   EventSet A_copy_remade(std::move(actual_A));
 754   EventSet B_copy_remade(std::move(actual_B));
 755   EventSet C_copy_remade(std::move(actual_C));
 756   EventSet D_copy_remade(std::move(actual_D));
 757
 758   REQUIRE(A_copy == A_copy_remade);
 759   REQUIRE(B_copy == B_copy_remade);
 760   REQUIRE(C_copy == C_copy_remade);
 761   REQUIRE(D_copy == D_copy_remade);
 762 }
 763
 764 TEST_CASE("simgrid::mc::udpor::EventSet: Checking conflicts")
 765 {
 766   // The following tests concern the given event structure:
 767   //                e1
 768   //              /    /
 769   //            e2      e5
 770   //           /  /      /
 771   //          e3  e4     e6
 772   // The tests enumerate all possible subsets of the events
 773   // in the structure and test whether those subsets contain
 774   // conflicts.
 775   //
 776   // Each test assigns different transitions to each event to
 777   // make the scenarios more interesting
 778
 779   SECTION("No conflicts throughout the whole structure with independent actions")
 780   {
 781     UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 782     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 783     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 784     UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 785     UnfoldingEvent e5(EventSet({&e1}), std::make_shared<IndependentAction>());
 786     UnfoldingEvent e6(EventSet({&e5}), std::make_shared<IndependentAction>());
 787
 788     // 6 choose 0 = 1 test
 789     CHECK(EventSet().is_conflict_free());
 790
 791     // 6 choose 1 = 6 tests
 792     CHECK(EventSet({&e1}).is_conflict_free());
 793     CHECK(EventSet({&e2}).is_conflict_free());
 794     CHECK(EventSet({&e3}).is_conflict_free());
 795     CHECK(EventSet({&e4}).is_conflict_free());
 796     CHECK(EventSet({&e5}).is_conflict_free());
 797     CHECK(EventSet({&e6}).is_conflict_free());
 798
 799     // 6 choose 2 = 15 tests
 800     CHECK(EventSet({&e1, &e2}).is_conflict_free());
 801     CHECK(EventSet({&e1, &e3}).is_conflict_free());
 802     CHECK(EventSet({&e1, &e4}).is_conflict_free());
 803     CHECK(EventSet({&e1, &e5}).is_conflict_free());
 804     CHECK(EventSet({&e1, &e6}).is_conflict_free());
 805     CHECK(EventSet({&e2, &e3}).is_conflict_free());
 806     CHECK(EventSet({&e2, &e4}).is_conflict_free());
 807     CHECK(EventSet({&e2, &e5}).is_conflict_free());
 808     CHECK(EventSet({&e2, &e6}).is_conflict_free());
 809     CHECK(EventSet({&e3, &e4}).is_conflict_free());
 810     CHECK(EventSet({&e3, &e5}).is_conflict_free());
 811     CHECK(EventSet({&e3, &e6}).is_conflict_free());
 812     CHECK(EventSet({&e4, &e5}).is_conflict_free());
 813     CHECK(EventSet({&e4, &e6}).is_conflict_free());
 814     CHECK(EventSet({&e5, &e6}).is_conflict_free());
 815
 816     // 6 choose 3 = 20 tests
 817     CHECK(EventSet({&e1, &e2, &e3}).is_conflict_free());
 818     CHECK(EventSet({&e1, &e2, &e4}).is_conflict_free());
 819     CHECK(EventSet({&e1, &e2, &e5}).is_conflict_free());
 820     CHECK(EventSet({&e1, &e2, &e6}).is_conflict_free());
 821     CHECK(EventSet({&e1, &e3, &e4}).is_conflict_free());
 822     CHECK(EventSet({&e1, &e3, &e5}).is_conflict_free());
 823     CHECK(EventSet({&e1, &e3, &e6}).is_conflict_free());
 824     CHECK(EventSet({&e1, &e4, &e5}).is_conflict_free());
 825     CHECK(EventSet({&e1, &e4, &e6}).is_conflict_free());
 826     CHECK(EventSet({&e1, &e5, &e6}).is_conflict_free());
 827     CHECK(EventSet({&e2, &e3, &e4}).is_conflict_free());
 828     CHECK(EventSet({&e2, &e3, &e5}).is_conflict_free());
 829     CHECK(EventSet({&e2, &e3, &e6}).is_conflict_free());
 830     CHECK(EventSet({&e2, &e4, &e5}).is_conflict_free());
 831     CHECK(EventSet({&e2, &e4, &e6}).is_conflict_free());
 832     CHECK(EventSet({&e2, &e5, &e6}).is_conflict_free());
 833     CHECK(EventSet({&e3, &e4, &e5}).is_conflict_free());
 834     CHECK(EventSet({&e3, &e4, &e6}).is_conflict_free());
 835     CHECK(EventSet({&e3, &e5, &e6}).is_conflict_free());
 836     CHECK(EventSet({&e4, &e5, &e6}).is_conflict_free());
 837
 838     // 6 choose 4 = 15 tests
 839     CHECK(EventSet({&e1, &e2, &e3, &e4}).is_conflict_free());
 840     CHECK(EventSet({&e1, &e2, &e3, &e5}).is_conflict_free());
 841     CHECK(EventSet({&e1, &e2, &e3, &e6}).is_conflict_free());
 842     CHECK(EventSet({&e1, &e2, &e4, &e5}).is_conflict_free());
 843     CHECK(EventSet({&e1, &e2, &e4, &e6}).is_conflict_free());
 844     CHECK(EventSet({&e1, &e2, &e5, &e6}).is_conflict_free());
 845     CHECK(EventSet({&e1, &e3, &e4, &e5}).is_conflict_free());
 846     CHECK(EventSet({&e1, &e3, &e4, &e6}).is_conflict_free());
 847     CHECK(EventSet({&e1, &e3, &e5, &e6}).is_conflict_free());
 848     CHECK(EventSet({&e1, &e4, &e5, &e6}).is_conflict_free());
 849     CHECK(EventSet({&e2, &e3, &e4, &e5}).is_conflict_free());
 850     CHECK(EventSet({&e2, &e3, &e4, &e6}).is_conflict_free());
 851     CHECK(EventSet({&e2, &e3, &e5, &e6}).is_conflict_free());
 852     CHECK(EventSet({&e2, &e4, &e5, &e6}).is_conflict_free());
 853     CHECK(EventSet({&e3, &e4, &e5, &e6}).is_conflict_free());
 854
 855     // 6 choose 5 = 6 tests
 856     CHECK(EventSet({&e1, &e2, &e3, &e4, &e5}).is_conflict_free());
 857     CHECK(EventSet({&e1, &e2, &e3, &e4, &e6}).is_conflict_free());
 858     CHECK(EventSet({&e1, &e2, &e3, &e5, &e6}).is_conflict_free());
 859     CHECK(EventSet({&e1, &e2, &e4, &e5, &e6}).is_conflict_free());
 860     CHECK(EventSet({&e1, &e3, &e4, &e5, &e6}).is_conflict_free());
 861     CHECK(EventSet({&e2, &e3, &e4, &e5, &e6}).is_conflict_free());
 862
 863     // 6 choose 6 = 1 test
 864     CHECK(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
 865   }
 866
 867   SECTION("Conflicts throughout the whole structure with dependent actions (except with DFS sets)")
 868   {
 869     // Since all actions are dependent, if a set contains a "fork" or divergent histories,
 870     // we expect the collections to contain conflicts
 871     UnfoldingEvent e1(EventSet(), std::make_shared<DependentAction>());
 872     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<DependentAction>());
 873     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<DependentAction>());
 874     UnfoldingEvent e4(EventSet({&e2}), std::make_shared<DependentAction>());
 875     UnfoldingEvent e5(EventSet({&e1}), std::make_shared<DependentAction>());
 876     UnfoldingEvent e6(EventSet({&e5}), std::make_shared<DependentAction>());
 877
 878     // 6 choose 0 = 1 test
 879     // There are no events even to be in conflict with
 880     CHECK(EventSet().is_conflict_free());
 881
 882     // 6 choose 1 = 6 tests
 883     // Sets of size 1 should have no conflicts
 884     CHECK(EventSet({&e1}).is_conflict_free());
 885     CHECK(EventSet({&e2}).is_conflict_free());
 886     CHECK(EventSet({&e3}).is_conflict_free());
 887     CHECK(EventSet({&e4}).is_conflict_free());
 888     CHECK(EventSet({&e5}).is_conflict_free());
 889     CHECK(EventSet({&e6}).is_conflict_free());
 890
 891     // 6 choose 2 = 15 tests
 892     CHECK(EventSet({&e1, &e2}).is_conflict_free());
 893     CHECK(EventSet({&e1, &e3}).is_conflict_free());
 894     CHECK(EventSet({&e1, &e4}).is_conflict_free());
 895     CHECK(EventSet({&e1, &e5}).is_conflict_free());
 896     CHECK(EventSet({&e1, &e6}).is_conflict_free());
 897     CHECK(EventSet({&e2, &e3}).is_conflict_free());
 898     CHECK(EventSet({&e2, &e4}).is_conflict_free());
 899     CHECK_FALSE(EventSet({&e2, &e5}).is_conflict_free());
 900     CHECK_FALSE(EventSet({&e2, &e6}).is_conflict_free());
 901     CHECK_FALSE(EventSet({&e3, &e4}).is_conflict_free());
 902     CHECK_FALSE(EventSet({&e3, &e5}).is_conflict_free());
 903     CHECK_FALSE(EventSet({&e3, &e6}).is_conflict_free());
 904     CHECK_FALSE(EventSet({&e4, &e5}).is_conflict_free());
 905     CHECK_FALSE(EventSet({&e4, &e6}).is_conflict_free());
 906     CHECK(EventSet({&e5, &e6}).is_conflict_free());
 907
 908     // 6 choose 3 = 20 tests
 909     CHECK(EventSet({&e1, &e2, &e3}).is_conflict_free());
 910     CHECK(EventSet({&e1, &e2, &e4}).is_conflict_free());
 911     CHECK_FALSE(EventSet({&e1, &e2, &e5}).is_conflict_free());
 912     CHECK_FALSE(EventSet({&e1, &e2, &e6}).is_conflict_free());
 913     CHECK_FALSE(EventSet({&e1, &e3, &e4}).is_conflict_free());
 914     CHECK_FALSE(EventSet({&e1, &e3, &e5}).is_conflict_free());
 915     CHECK_FALSE(EventSet({&e1, &e3, &e6}).is_conflict_free());
 916     CHECK_FALSE(EventSet({&e1, &e4, &e5}).is_conflict_free());
 917     CHECK_FALSE(EventSet({&e1, &e4, &e6}).is_conflict_free());
 918     CHECK(EventSet({&e1, &e5, &e6}).is_conflict_free());
 919     CHECK_FALSE(EventSet({&e2, &e3, &e4}).is_conflict_free());
 920     CHECK_FALSE(EventSet({&e2, &e3, &e5}).is_conflict_free());
 921     CHECK_FALSE(EventSet({&e2, &e3, &e6}).is_conflict_free());
 922     CHECK_FALSE(EventSet({&e2, &e4, &e5}).is_conflict_free());
 923     CHECK_FALSE(EventSet({&e2, &e4, &e6}).is_conflict_free());
 924     CHECK_FALSE(EventSet({&e2, &e5, &e6}).is_conflict_free());
 925     CHECK_FALSE(EventSet({&e3, &e4, &e5}).is_conflict_free());
 926     CHECK_FALSE(EventSet({&e3, &e4, &e6}).is_conflict_free());
 927     CHECK_FALSE(EventSet({&e3, &e5, &e6}).is_conflict_free());
 928     CHECK_FALSE(EventSet({&e4, &e5, &e6}).is_conflict_free());
 929
 930     // 6 choose 4 = 15 tests
 931     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4}).is_conflict_free());
 932     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5}).is_conflict_free());
 933     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_conflict_free());
 934     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5}).is_conflict_free());
 935     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_conflict_free());
 936     CHECK_FALSE(EventSet({&e1, &e2, &e5, &e6}).is_conflict_free());
 937     CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_conflict_free());
 938     CHECK_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_conflict_free());
 939     CHECK_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_conflict_free());
 940     CHECK_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_conflict_free());
 941     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_conflict_free());
 942     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_conflict_free());
 943     CHECK_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_conflict_free());
 944     CHECK_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_conflict_free());
 945     CHECK_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_conflict_free());
 946
 947     // 6 choose 5 = 6 tests
 948     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_conflict_free());
 949     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_conflict_free());
 950     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_conflict_free());
 951     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_conflict_free());
 952     CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_conflict_free());
 953     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_conflict_free());
 954
 955     // 6 choose 6 = 1 test
 956     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
 957   }
 958
 959   SECTION("Conditional conflicts")
 960   {
 961     UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 962     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<ConditionallyDependentAction>());
 963     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 964     UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 965     UnfoldingEvent e5(EventSet({&e1}), std::make_shared<DependentAction>());
 966     UnfoldingEvent e6(EventSet({&e5}), std::make_shared<IndependentAction>());
 967
 968     // 6 choose 0 = 1 test
 969     // There are no events even to be in conflict with
 970     CHECK(EventSet().is_conflict_free());
 971
 972     // 6 choose 1 = 6 tests
 973     // Sets of size 1 should still have no conflicts
 974     CHECK(EventSet({&e1}).is_conflict_free());
 975     CHECK(EventSet({&e2}).is_conflict_free());
 976     CHECK(EventSet({&e3}).is_conflict_free());
 977     CHECK(EventSet({&e4}).is_conflict_free());
 978     CHECK(EventSet({&e5}).is_conflict_free());
 979     CHECK(EventSet({&e6}).is_conflict_free());
 980
 981     // 6 choose 2 = 15 tests
 982     CHECK(EventSet({&e1, &e2}).is_conflict_free());
 983     CHECK(EventSet({&e1, &e3}).is_conflict_free());
 984     CHECK(EventSet({&e1, &e4}).is_conflict_free());
 985     CHECK(EventSet({&e1, &e5}).is_conflict_free());
 986     CHECK(EventSet({&e1, &e6}).is_conflict_free());
 987     CHECK(EventSet({&e2, &e3}).is_conflict_free());
 988     CHECK(EventSet({&e2, &e4}).is_conflict_free());
 989     CHECK_FALSE(EventSet({&e2, &e5}).is_conflict_free());
 990
 991     // Although e2 and e6 are not directly dependent,
 992     // e2 conflicts with e5 which causes e6
 993     CHECK_FALSE(EventSet({&e2, &e6}).is_conflict_free());
 994     CHECK(EventSet({&e3, &e4}).is_conflict_free());
 995
 996     // Likewise, since e2 and e5 conflict and e2 causes
 997     // e3, so e3 and e5 conflict
 998     CHECK_FALSE(EventSet({&e3, &e5}).is_conflict_free());
 999     CHECK(EventSet({&e3, &e6}).is_conflict_free());
1000     CHECK_FALSE(EventSet({&e4, &e5}).is_conflict_free());
1001     CHECK(EventSet({&e4, &e6}).is_conflict_free());
1002     CHECK(EventSet({&e5, &e6}).is_conflict_free());
1003
1004     // 6 choose 3 = 20 tests
1005     CHECK(EventSet({&e1, &e2, &e3}).is_conflict_free());
1006     CHECK(EventSet({&e1, &e2, &e4}).is_conflict_free());
1007     CHECK_FALSE(EventSet({&e1, &e2, &e5}).is_conflict_free());
1008     CHECK_FALSE(EventSet({&e1, &e2, &e6}).is_conflict_free());
1009     CHECK(EventSet({&e1, &e3, &e4}).is_conflict_free());
1010     CHECK_FALSE(EventSet({&e1, &e3, &e5}).is_conflict_free());
1011     CHECK(EventSet({&e1, &e3, &e6}).is_conflict_free());
1012     CHECK_FALSE(EventSet({&e1, &e4, &e5}).is_conflict_free());
1013     CHECK(EventSet({&e1, &e4, &e6}).is_conflict_free());
1014     CHECK(EventSet({&e1, &e5, &e6}).is_conflict_free());
1015     CHECK(EventSet({&e2, &e3, &e4}).is_conflict_free());
1016     CHECK_FALSE(EventSet({&e2, &e3, &e5}).is_conflict_free());
1017     CHECK_FALSE(EventSet({&e2, &e3, &e6}).is_conflict_free());
1018     CHECK_FALSE(EventSet({&e2, &e4, &e5}).is_conflict_free());
1019     CHECK_FALSE(EventSet({&e2, &e4, &e6}).is_conflict_free());
1020     CHECK_FALSE(EventSet({&e2, &e5, &e6}).is_conflict_free());
1021     CHECK_FALSE(EventSet({&e3, &e4, &e5}).is_conflict_free());
1022     CHECK(EventSet({&e3, &e4, &e6}).is_conflict_free());
1023     CHECK_FALSE(EventSet({&e3, &e5, &e6}).is_conflict_free());
1024     CHECK_FALSE(EventSet({&e4, &e5, &e6}).is_conflict_free());
1025
1026     // 6 choose 4 = 15 tests
1027     CHECK(EventSet({&e1, &e2, &e3, &e4}).is_conflict_free());
1028     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5}).is_conflict_free());
1029
1030     // e2 is dependent with e6
1031     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_conflict_free());
1032     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5}).is_conflict_free());
1033     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_conflict_free());
1034     CHECK_FALSE(EventSet({&e1, &e2, &e5, &e6}).is_conflict_free());
1035     CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_conflict_free());
1036     CHECK(EventSet({&e1, &e3, &e4, &e6}).is_conflict_free());
1037     CHECK_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_conflict_free());
1038     CHECK_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_conflict_free());
1039     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_conflict_free());
1040     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_conflict_free());
1041     CHECK_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_conflict_free());
1042     CHECK_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_conflict_free());
1043     CHECK_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_conflict_free());
1044
1045     // 6 choose 5 = 6 tests
1046     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_conflict_free());
1047     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_conflict_free());
1048     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_conflict_free());
1049     CHECK_FALSE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_conflict_free());
1050     CHECK_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_conflict_free());
1051     CHECK_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_conflict_free());
1052
1053     // 6 choose 6 = 1 test
1054     CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
1055   }
1056 }
1057
1058 TEST_CASE("simgrid::mc::udpor::EventSet: Topological Ordering Property Observed for Every Possible Subset")
1059 {
1060   // The following tests concern the given event structure:
1061   //                e1
1062   //              /   /
1063   //            e2    e6
1064   //           /  /    /
1065   //          e3   /   /
1066   //         /  /    /
1067   //        e4  e5   e7
1068   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
1069   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
1070   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
1071   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
1072   UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
1073   UnfoldingEvent e6(EventSet({&e1}), std::make_shared<IndependentAction>());
1074   UnfoldingEvent e7(EventSet({&e2, &e6}), std::make_shared<IndependentAction>());
1075
1076   const EventSet all_events{&e1, &e2, &e3, &e4, &e5, &e6, &e7};
1077
1078   for (const auto& subset_of_iterators : make_powerset_iter<EventSet>(all_events)) {
1079     // Verify that the topological ordering property holds for every subset
1080
1081     const EventSet subset = [&subset_of_iterators]() {
1082       EventSet subset_local;
1083       for (const auto iter : subset_of_iterators) {
1084         subset_local.insert(*iter);
1085       }
1086       return subset_local;
1087     }();
1088
1089     {
1090       // To test this, we verify that at each point none of the events
1091       // that follow after any particular event `e` are contained in
1092       // `e`'s history
1093       EventSet invalid_events   = subset;
1094       const auto ordered_events = subset.get_topological_ordering();
1095
1096       std::for_each(ordered_events.begin(), ordered_events.end(), [&](const UnfoldingEvent* e) {
1097         History history(e);
1098         for (auto* e_hist : history) {
1099           if (e_hist == e)
1100             continue;
1101           REQUIRE_FALSE(invalid_events.contains(e_hist));
1102         }
1103         invalid_events.remove(e);
1104       });
1105     }
1106     {
1107       // To test this, we verify that at each point none of the events
1108       // that we've processed in the ordering are ever seen again
1109       // in anybody else's history
1110       EventSet events_seen;
1111       const auto ordered_events = subset.get_topological_ordering_of_reverse_graph();
1112
1113       std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
1114         History history(e);
1115
1116         for (auto* e_hist : history) {
1117           // Unlike the test above, we DO want to ensure
1118           // that `e` itself ALSO isn't yet seen
1119
1120           // If this event has been "seen" before,
1121           // this implies that event `e` appears later
1122           // in the list than one of its ancestors
1123           REQUIRE_FALSE(events_seen.contains(e_hist));
1124         }
1125         events_seen.insert(e);
1126       });
1127     }
1128   }
1129 }