static void test_tree_iterator(const WakeupTree& tree, const std::vector<PartialExecution>& expected)
{
- auto tree_iter = tree.begin();
- for (auto expected_iter = expected.begin(); expected_iter != expected.end(); ++expected_iter, ++tree_iter) {
+ uint64_t num_nodes_traversed = 0;
+ auto tree_iter = tree.begin();
+ for (auto expected_iter = expected.begin(); expected_iter != expected.end();
+ ++expected_iter, ++tree_iter, ++num_nodes_traversed) {
REQUIRE(tree_iter != tree.end());
REQUIRE((*tree_iter)->get_sequence() == *expected_iter);
}
+ REQUIRE(num_nodes_traversed == tree.get_num_nodes());
+}
+
+static void test_tree_empty(const WakeupTree& tree)
+{
+ REQUIRE(tree.empty());
+ REQUIRE(tree.get_num_entries() == 0);
+ REQUIRE(tree.get_num_nodes() == 1);
+ REQUIRE_FALSE(tree.get_min_single_process_node().has_value());
+ REQUIRE_FALSE(tree.get_min_single_process_actor().has_value());
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
+}
+
+TEST_CASE("simgrid::mc::odpor::WakeupTree: Constructing Trees")
+{
+ SECTION("Constructing empty trees")
+ {
+ test_tree_empty(WakeupTree());
+ }
+
+ SECTION("Testing subtree creation and manipulation")
+ {
+ // Here, we make everything dependent. This will ensure that each unique sequence
+ // inserted into the tree never "eventually looks like"
+ const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
+ const auto a1 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
+ const auto a2 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
+ const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 4);
+ const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 5);
+ const auto a5 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 6);
+
+ Execution execution;
+ execution.push_transition(a0);
+ execution.push_transition(a1);
+ execution.push_transition(a2);
+ execution.push_transition(a3);
+ execution.push_transition(a4);
+ execution.push_transition(a5);
+
+ // The tree is as follows:
+ // {}
+ // / /
+ // a1 a4
+ // / / /
+ // a2 a3 a1
+ // / / / /
+ // a3 a2 a5 a2
+ // / / /
+ // a4 a4 a3
+ //
+ // Recall that new nodes (in this case the one with
+ // action `a2`) are added such that they are "greater than" (under
+ // the tree's `<` relation) all those that exist under the given parent
+ WakeupTree tree;
+ tree.insert(Execution(), {a1, a2, a3, a4});
+ tree.insert(Execution(), {a1, a3, a2, a4});
+ tree.insert(Execution(), {a1, a3, a2, a4, a5});
+ tree.insert(Execution(), {a1, a3, a5});
+ tree.insert(Execution(), {a4, a2, a1, a3});
+ REQUIRE(tree.get_num_nodes() == 13);
+ test_tree_iterator(tree, std::vector<PartialExecution>{
+ PartialExecution{a1, a2, a3, a4}, PartialExecution{a1, a2, a3},
+ PartialExecution{a1, a2}, PartialExecution{a1, a3, a2, a4},
+ PartialExecution{a1, a3, a2}, PartialExecution{a1, a3, a5}, PartialExecution{a1, a3},
+ PartialExecution{a1}, PartialExecution{a4, a2, a1, a3}, PartialExecution{a4, a2, a1},
+ PartialExecution{a4, a2}, PartialExecution{a4}, PartialExecution{}});
+
+ SECTION("Cloning a tree from the root produces the same tree")
+ {
+ // The root node is the last node
+ auto tree_root = tree.begin();
+ std::advance(tree_root, tree.get_num_nodes() - 1);
+
+ WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree_root);
+ REQUIRE(clone.empty() == tree.empty());
+ REQUIRE(clone.get_num_entries() == tree.get_num_entries());
+ REQUIRE(clone.get_num_nodes() == tree.get_num_nodes());
+
+ auto tree_iter = tree.begin();
+ for (auto clone_iter = clone.begin(); clone_iter != clone.end(); ++clone_iter, ++tree_iter) {
+ REQUIRE(tree_iter != tree.end());
+ REQUIRE((*tree_iter)->get_sequence() == (*clone_iter)->get_sequence());
+ }
+ }
+
+ SECTION("Cloning a subtree from a leaf gives an empty tree")
+ {
+ // Let's pick the first leaf
+ WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree.begin());
+ REQUIRE(clone.empty());
+ REQUIRE(clone.get_num_entries() == 0);
+ REQUIRE(clone.get_num_nodes() == 1);
+ }
+
+ SECTION("Cloning a subtree from an interior node gives the subtree underneath")
+ {
+ // Here, we pick the second-to-last node in the
+ // series, which is the right-most child of the root
+ auto right_most = tree.begin();
+ std::advance(right_most, tree.get_num_nodes() - 2);
+
+ WakeupTree clone = WakeupTree::make_subtree_rooted_at(*right_most);
+ REQUIRE_FALSE(clone.empty());
+ REQUIRE(clone.get_num_entries() == 3);
+ REQUIRE(clone.get_num_nodes() == 4);
+ // Importantly, note that action `a4` is not included in
+ // any of the executions; for in the subtree `clone` `a4`
+ // is now the root.
+ test_tree_iterator(clone, std::vector<PartialExecution>{PartialExecution{a2, a1, a3}, PartialExecution{a2, a1},
+ PartialExecution{a2}, PartialExecution{}});
+ }
+
+ SECTION("Removing the first single-process subtree")
+ {
+ // Prior to removal, the first `a1` was the first single-process node
+ REQUIRE(tree.get_min_single_process_node().has_value());
+ REQUIRE(tree.get_min_single_process_actor().has_value());
+ REQUIRE(tree.get_min_single_process_actor().value() == a1->aid_);
+
+ tree.remove_min_single_process_subtree();
+
+ // Now the first `a4` is
+ REQUIRE(tree.get_min_single_process_node().has_value());
+ REQUIRE(tree.get_min_single_process_actor().has_value());
+ REQUIRE(tree.get_min_single_process_actor().value() == a4->aid_);
+
+ REQUIRE(tree.get_num_nodes() == 5);
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4, a2, a1, a3},
+ PartialExecution{a4, a2, a1}, PartialExecution{a4, a2},
+ PartialExecution{a4}, PartialExecution{}});
+ tree.remove_min_single_process_subtree();
+
+ // At this point, we've removed each single-process subtree, so
+ // the tree should be empty
+ REQUIRE(tree.empty());
+ }
+
+ SECTION("Removing the first single-process subtree from an empty tree has no effect")
+ {
+ WakeupTree empty_tree;
+ test_tree_empty(empty_tree);
+
+ empty_tree.remove_min_single_process_subtree();
+
+ // There should be no effect: the tree should still be empty
+ // and the function should have no effect
+ test_tree_empty(empty_tree);
+ }
+ }
}
TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Insertion for Empty Executions")
{
// We imagine the following completed execution `E`
// consisting of executing actions a0-a3. Execution
- // `E` cis the first such maximal execution explored
+ // `E` is the first such maximal execution explored
// by ODPOR, which implies that a) all sleep sets are
// empty and b) all wakeup trees (i.e. for each prefix) consist of the root
// node with a single leaf containing the action
// taken, save for the wakeup tree of the execution itself
- // which is empty
+ // which is empty.
// We first notice that there's a reversible race between
// events 0 and 3.
const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
+ const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
Execution execution;
execution.push_transition(a0);
execution.push_transition(a1);
execution.push_transition(a2);
execution.push_transition(a3);
+ execution.push_transition(a4);
REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
}
// First, we initialize the tree to how it looked prior
- // to the insertion of the race
+ // to the insertion of the race.
tree.insert(Execution(), {a0});
// Then, after insertion, we ensure that the node was
- // indeed added to the tree
+ // indeed added to the tree.
tree.insert(Execution(), {a1, a3});
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
PartialExecution{a1}, PartialExecution{}});
SECTION("Attempting to re-insert an equivalent sequence should have no effect")
{
// a3 and a1 are interchangeable since `a1` is independent with everything.
- // Since we found an equivalent sequence that is a leaf, nothing should result
+ // Since we found an equivalent sequence that is a leaf, nothing should result..
tree.insert(Execution(), {a3, a1});
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
PartialExecution{a1}, PartialExecution{}});
// / /
// a0 a1
// / /
- // a3 a2
+ // a3 a4
//
// Recall that new nodes (in this case the one with
// action `a2`) are added such that they are "greater than" (under
- // the tree's `<` relation) all those that exist under the given parent
- tree.insert(Execution(), {a1, a2});
+ // the tree's `<` relation) all those that exist under the given parent.
+ tree.insert(Execution(), {a1, a4});
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
- PartialExecution{a1, a2}, PartialExecution{a1},
+ PartialExecution{a1, a4}, PartialExecution{a1},
PartialExecution{}});
}
+
+ SECTION("Inserting an equivalent sequence to a leaf should preserve the tree as-is")
+ {
+ // `a1.a2` is equivalent to `a1.a3` since `a2` and `a3` are independent
+ // (`E ⊢ p ◊ w` where `p := proc(a2)` and `w := a3`). Thus, the tree
+ // should now STILL look as follows:
+ //
+ // {}
+ // / /
+ // a0 a1
+ // /
+ // a3
+ //
+ // Recall that new nodes (in this case the one with
+ // action `a2`) are added such that they are "greater than" (under
+ // the tree's `<` relation) all those that exist under the given parent.
+ tree.insert(Execution(), {a1, a3});
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
+ PartialExecution{a1}, PartialExecution{}});
+ }
}
SECTION("Performing Arbitrary Insertions")
const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
const auto a4 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
const auto a5 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
-
- Execution execution;
- execution.push_transition(a0);
- execution.push_transition(a1);
- execution.push_transition(a2);
- execution.push_transition(a3);
- execution.push_transition(a4);
- execution.push_transition(a5);
-
WakeupTree tree;
SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
// checks whether `a1` is independent with everything in the sequence
// (in this case, consisting only of `a1`) which IS true. Since `a4`
// is already a leaf node of the tree, it suffices to only have `a4`
- // in this tree to guide ODPOR
+ // in this tree to guide ODPOR.
tree.insert(Execution(), {a4});
tree.insert(Execution(), {a1});
REQUIRE(tree.get_num_nodes() == 2);
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{}});
}
- SECTION("Stress test with multiple branch points")
+ SECTION("Stress test with multiple branch points: `~_E` with different looking sequences")
{
+ // After the insertions below, the tree looks like the following:
+ // {}
+ // / /
+ // a0 a2
+ // / | /
+ // a0 a3 a5
tree.insert(Execution(), {a0});
tree.insert(Execution(), {a2, a0});
tree.insert(Execution(), {a2, a3});
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
PartialExecution{a2, a3}, PartialExecution{a2, a5},
PartialExecution{a2}, PartialExecution{}});
+ SECTION("Adding more stress")
+ {
+ // In this case, `a2` and `a1` can be interchanged with each other.
+ // Thus `a2.a1 == a1.a2`. Since there is already an interior node
+ // containing `a2`, we attempt to add the what remains (viz. `a1`) to the
+ // series. HOWEVER: we notice that `a2.a5` is "eventually equivalent to"
+ // (that is `~` with) `a1.a2` since `a2` is an initial of the latter and
+ // `a1` and `a5` are independent of each other.
+ tree.insert(Execution(), {a1, a2});
+ REQUIRE(tree.get_num_nodes() == 6);
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
+ PartialExecution{a2, a3}, PartialExecution{a2, a5},
+ PartialExecution{a2}, PartialExecution{}});
+
+ // With a3.a0, we notice that starting a sequence with `a3` is
+ // always different than starting one with either `a0` or
+ //
+ // After the insertion, the tree looks like the following:
+ // {}
+ // / / /
+ // a0 a2 a3
+ // / | / |
+ // a0 a3 a5 a0
+ tree.insert(Execution(), {a3, a0});
+ REQUIRE(tree.get_num_nodes() == 8);
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
+ PartialExecution{a2, a3}, PartialExecution{a2, a5},
+ PartialExecution{a2}, PartialExecution{a3, a0},
+ PartialExecution{a3}, PartialExecution{}});
+ }
}
}
-}
-TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Subtree Rooting")
-{
- const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
- const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
- const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
- const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
- const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
- const auto a5 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
-
- Execution execution;
- execution.push_transition(a0);
- execution.push_transition(a1);
- execution.push_transition(a2);
- execution.push_transition(a3);
-
- REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
- REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
+ SECTION("Insertion with more subtle equivalents")
+ {
+ const auto cd_1 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
+ const auto i_2 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
+ const auto i_3 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 3);
+ const auto d_1 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
+ const auto d_2 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
+ WakeupTree complex_tree;
+ // After the insertions below, the tree looks like the following:
+ // {}
+ // / /
+ // cd_1 i_2
+ // / /
+ // i_2 d_2
+ // / /
+ // d_1 cd_1
+ // / / /
+ // i_3 d_1 i_3
+ // / / /
+ // d_2 i_3 d_2
+ // / / /
+ // d_2 d_2 d_1
+ //
+ // d_1.i_3.d_2 is equivalent to i_3.d_2.d_1
+ complex_tree.insert(Execution(), {cd_1, i_2, d_1, i_3, d_2, d_2});
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, d_1, i_3, d_2});
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, i_3, d_2, d_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+ test_tree_iterator(complex_tree, std::vector<PartialExecution>{{cd_1, i_2, d_1, i_3, d_2, d_2},
+ {cd_1, i_2, d_1, i_3, d_2},
+ {cd_1, i_2, d_1, i_3},
+ {cd_1, i_2, d_1},
+ {cd_1, i_2},
+ {cd_1},
+ {i_2, d_2, cd_1, d_1, i_3, d_2},
+ {i_2, d_2, cd_1, d_1, i_3},
+ {i_2, d_2, cd_1, d_1},
+ {i_2, d_2, cd_1, i_3, d_2, d_1},
+ {i_2, d_2, cd_1, i_3, d_2},
+ {i_2, d_2, cd_1, i_3},
+ {i_2, d_2, cd_1},
+ {i_2, d_2},
+ {i_2},
+ {}});
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_3.i_2.d_2.cd_1.d_2.d_1
+ //
+ // is already equivalent to
+ //
+ // i_2.d_2.cd_1.i_3.d_2.d_1
+ complex_tree.insert(Execution(), {i_3, i_2, d_2, cd_1, d_2, d_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
- // The wakeup tree should
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_2.d_2.cd_1.d_1.i_3
+ //
+ // is already equivalent to
+ //
+ // i_2.d_2.cd_1.i_3.d_2.d_1
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, d_1, i_3});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
- WakeupTree tree;
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_2.d_2.cd_1
+ //
+ // is accounted for by an interior node of the tree. Since there is no
+ // "extra" portions that are different from what is already
+ // contained in the tree, nothing is added and the tree stays the same
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+ }
}
\ No newline at end of file
