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