1 /* Copyright (c) 2017-2023. The SimGrid Team. All rights reserved. */
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. */
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"
13 using namespace simgrid::xbt;
14 using namespace simgrid::mc::udpor;
16 TEST_CASE("simgrid::mc::udpor::EventSet: Initial conditions when creating sets")
18 SECTION("Initialization with no elements")
20 SECTION("Default initializer")
23 REQUIRE(event_set.size() == 0);
24 REQUIRE(event_set.empty());
27 SECTION("Set initializer")
29 EventSet event_set({});
30 REQUIRE(event_set.size() == 0);
31 REQUIRE(event_set.empty());
34 SECTION("List initialization")
37 REQUIRE(event_set.size() == 0);
38 REQUIRE(event_set.empty());
42 SECTION("Initialization with one or more elements")
44 UnfoldingEvent e1, e2, e3;
46 SECTION("Set initializer")
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());
56 SECTION("List initialization")
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());
68 TEST_CASE("simgrid::mc::udpor::EventSet: Insertions")
71 UnfoldingEvent e1, e2, e3;
73 SECTION("Inserting unique elements")
75 event_set.insert(&e1);
76 REQUIRE(event_set.size() == 1);
77 REQUIRE(event_set.contains(&e1));
78 REQUIRE_FALSE(event_set.empty());
80 event_set.insert(&e2);
81 REQUIRE(event_set.size() == 2);
82 REQUIRE(event_set.contains(&e2));
83 REQUIRE_FALSE(event_set.empty());
85 SECTION("Check contains inserted elements")
87 REQUIRE(event_set.contains(&e1));
88 REQUIRE(event_set.contains(&e2));
89 REQUIRE_FALSE(event_set.contains(&e3));
93 SECTION("Inserting duplicate elements")
95 event_set.insert(&e1);
96 REQUIRE(event_set.size() == 1);
97 REQUIRE(event_set.contains(&e1));
98 REQUIRE_FALSE(event_set.empty());
100 event_set.insert(&e1);
101 REQUIRE(event_set.size() == 1);
102 REQUIRE(event_set.contains(&e1));
103 REQUIRE_FALSE(event_set.empty());
105 SECTION("Check contains inserted elements")
107 REQUIRE(event_set.contains(&e1));
108 REQUIRE_FALSE(event_set.contains(&e2));
109 REQUIRE_FALSE(event_set.contains(&e3));
114 TEST_CASE("simgrid::mc::udpor::EventSet: Deletions")
120 EventSet event_set({&e1, &e2, &e3});
122 SECTION("Remove an element already present")
124 REQUIRE(event_set.contains(&e1));
126 // Recall that event_set = {e2, e3}
127 event_set.remove(&e1);
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());
139 SECTION("Remove a single element more than once")
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());
150 SECTION("Remove more than one element")
152 // Recall that event_set = {e3}
153 event_set.remove(&e2);
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());
161 // Recall that event_set = {}
162 event_set.remove(&e3);
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());
172 SECTION("Remove an element absent from the set")
174 REQUIRE_FALSE(event_set.contains(&e4));
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));
183 // Ensure e4 isn't somehow added
184 REQUIRE_FALSE(event_set.contains(&e4));
185 REQUIRE_FALSE(event_set.empty());
189 TEST_CASE("simgrid::mc::udpor::EventSet: Set Equality")
195 EventSet A{&e1, &e2, &e3}, B{&e1, &e2, &e3}, C{&e1, &e2, &e3};
197 SECTION("Equality implies containment")
201 for (const auto& e : A) {
202 REQUIRE(B.contains(e));
205 for (const auto& e : B) {
206 REQUIRE(A.contains(e));
210 SECTION("Containment implies equality")
212 for (const auto& e : A) {
213 REQUIRE(B.contains(e));
216 for (const auto& e : C) {
217 REQUIRE(C.contains(e));
223 SECTION("Equality is an equivalence relation")
244 SECTION("Equality after copy (assignment + constructor)")
249 REQUIRE(A == A_copy);
250 REQUIRE(A == A_copy2);
253 SECTION("Equality after move constructor")
256 EventSet A_move(std::move(A));
257 REQUIRE(A_move == A_copy);
260 SECTION("Equality after move-assignment")
263 EventSet A_move = std::move(A);
264 REQUIRE(A_move == A_copy);
268 TEST_CASE("simgrid::mc::udpor::EventSet: Set Union Tests")
270 UnfoldingEvent e1, e2, e3, e4;
273 EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3};
275 SECTION("Unions with no effect")
279 SECTION("Self union")
282 EventSet A_union = A.make_union(A);
283 REQUIRE(A == A_union);
286 REQUIRE(A == A_copy);
289 SECTION("Union with empty set")
291 // A = A union empty set
292 EventSet A_union = A.make_union(EventSet());
293 REQUIRE(A == A_union);
295 A.form_union(EventSet());
296 REQUIRE(A == A_copy);
299 SECTION("Union with an equivalent set")
301 // A = A union B if B == A
302 EventSet A_equiv{&e1, &e2, &e3};
303 REQUIRE(A == A_equiv);
305 EventSet A_union = A.make_union(A_equiv);
306 REQUIRE(A_union == A_copy);
308 A.form_union(A_equiv);
309 REQUIRE(A == A_copy);
312 SECTION("Union with a subset")
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);
319 REQUIRE(A == A_copy);
323 SECTION("Unions with partial overlaps")
325 EventSet A_union_B = A.make_union(B);
326 REQUIRE(A_union_B == C);
331 EventSet B_union_D = B.make_union(D);
332 REQUIRE(B_union_D == C);
338 SECTION("Set union properties")
340 SECTION("Union operator is symmetric")
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);
347 SECTION("Union operator commutes")
349 // The last SECTION tested pair-wise
350 // equivalence, so we only check
352 EventSet AD = A.make_union(D);
353 EventSet AC = A.make_union(C);
354 EventSet CD = D.make_union(C);
356 EventSet ADC = AD.make_union(C);
357 EventSet ACD = AC.make_union(D);
358 EventSet CDA = CD.make_union(A);
363 // Test `form_union()` in the same way
369 A.form_union(C_copy);
370 A.form_union(D_copy);
372 D.form_union(A_copy);
373 D.form_union(C_copy);
385 TEST_CASE("simgrid::mc::udpor::EventSet: Set Difference Tests")
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};
400 SECTION("Difference with no effect")
402 SECTION("Difference with empty set")
404 EventSet A_copy = A.subtracting(EventSet());
405 REQUIRE(A == A_copy);
407 A.subtract(EventSet());
408 REQUIRE(A == A_copy);
411 SECTION("Difference with empty intersection")
413 // A intersection E = empty set
414 EventSet A_copy = A.subtracting(E);
415 REQUIRE(A == A_copy);
418 REQUIRE(A == A_copy);
420 EventSet D_copy = D.subtracting(E);
421 REQUIRE(D == D_copy);
424 REQUIRE(D == D_copy);
428 SECTION("Difference with some overlap")
431 EventSet A_minus_B = A.subtracting(B);
432 REQUIRE(A_minus_B == F);
434 // B - D = {&e2, &e4}
435 EventSet B_minus_D = B.subtracting(D);
436 REQUIRE(B_minus_D == EventSet({&e2, &e4}));
439 SECTION("Difference with complete overlap")
441 SECTION("Difference with same set gives empty set")
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());
451 SECTION("Difference with superset gives empty set")
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());
466 TEST_CASE("simgrid::mc::udpor::EventSet: Subset Tests")
468 UnfoldingEvent e1, e2, e3, e4;
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
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};
478 SECTION("Subset operator properties")
480 SECTION("Subset operator is not commutative")
482 REQUIRE(A.is_subset_of(C));
483 REQUIRE_FALSE(C.is_subset_of(A));
485 SECTION("Commutativity implies equality and vice versa")
487 REQUIRE(A.is_subset_of(F));
488 REQUIRE(F.is_subset_of(A));
492 REQUIRE(A.is_subset_of(F));
493 REQUIRE(F.is_subset_of(A));
497 SECTION("Subset operator is transitive")
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));
507 SECTION("Subset operator is reflexive")
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));
519 TEST_CASE("simgrid::mc::udpor::EventSet: Testing Configurations")
521 // The following tests concern the given event structure:
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>());
537 SECTION("Valid Configurations")
539 SECTION("The empty set is valid")
541 REQUIRE(EventSet().is_valid_configuration());
544 SECTION("The set with only the root event is valid")
546 REQUIRE(EventSet({&e1}).is_valid_configuration());
549 SECTION("All sets of maximal events are valid configurations")
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());
568 SECTION("Configuration checks")
570 // 6 choose 0 = 1 test
571 REQUIRE(EventSet().is_valid_configuration());
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());
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());
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());
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());
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());
645 // 6 choose 6 = 1 test
646 REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
649 SECTION("Maximal event sets")
651 // 6 choose 0 = 1 test
652 REQUIRE(EventSet().is_maximal());
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());
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());
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());
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());
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());
726 // 6 choose 6 = 1 test
727 REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_maximal());
731 TEST_CASE("simgrid::mc::udpor::EventSet: Moving into a collection")
739 EventSet B({&e1, &e2});
740 EventSet C({&e1, &e2, &e3});
741 EventSet D({&e1, &e2, &e3, &e4});
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();
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));
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);
764 TEST_CASE("simgrid::mc::udpor::EventSet: Checking conflicts")
766 // The following tests concern the given event structure:
772 // The tests enumerate all possible subsets of the events
773 // in the structure and test whether those subsets contain
776 // Each test assigns different transitions to each event to
777 // make the scenarios more interesting
779 SECTION("No conflicts throughout the whole structure with independent actions")
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>());
788 // 6 choose 0 = 1 test
789 CHECK(EventSet().is_conflict_free());
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());
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());
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());
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());
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());
863 // 6 choose 6 = 1 test
864 CHECK(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
867 SECTION("Conflicts throughout the whole structure with dependent actions (except with DFS sets)")
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>());
878 // 6 choose 0 = 1 test
879 // There are no events even to be in conflict with
880 CHECK(EventSet().is_conflict_free());
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());
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());
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());
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());
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());
955 // 6 choose 6 = 1 test
956 CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
959 SECTION("Conditional conflicts")
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>());
968 // 6 choose 0 = 1 test
969 // There are no events even to be in conflict with
970 CHECK(EventSet().is_conflict_free());
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());
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());
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());
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());
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());
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());
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());
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());
1053 // 6 choose 6 = 1 test
1054 CHECK_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_conflict_free());
1058 TEST_CASE("simgrid::mc::udpor::EventSet: Topological Ordering Property Observed for Every Possible Subset")
1060 // The following tests concern the given event structure:
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>());
1076 const EventSet all_events{&e1, &e2, &e3, &e4, &e5, &e6, &e7};
1078 for (const auto& subset_of_iterators : make_powerset_iter<EventSet>(all_events)) {
1079 // Verify that the topological ordering property holds for every subset
1081 const EventSet subset = [&subset_of_iterators]() {
1082 EventSet subset_local;
1083 for (const auto& iter : subset_of_iterators) {
1084 subset_local.insert(*iter);
1086 return subset_local;
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
1093 EventSet invalid_events = subset;
1094 const auto ordered_events = subset.get_topological_ordering();
1096 std::for_each(ordered_events.begin(), ordered_events.end(), [&](const UnfoldingEvent* e) {
1098 for (auto* e_hist : history) {
1101 REQUIRE_FALSE(invalid_events.contains(e_hist));
1103 invalid_events.remove(e);
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();
1113 std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
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
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));
1125 events_seen.insert(e);