1 /* Copyright (c) 2008-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/mc/explo/odpor/WakeupTree.hpp"
7 #include "src/mc/explo/odpor/Execution.hpp"
8 #include "xbt/asserts.h"
9 #include "xbt/string.hpp"
16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_wut, mc, "Logging specific to ODPOR WakeupTrees");
18 namespace simgrid::mc::odpor {
20 void WakeupTreeNode::add_child(WakeupTreeNode* node)
22 this->children_.push_back(node);
26 std::string WakeupTreeNode::string_of_whole_tree(int indentation_level) const
28 std::string tabulations = "";
29 for (int i = 0; i < indentation_level; i++)
31 std::string final_string = action_ == nullptr ? "<>\n"
32 : tabulations + "Actor " + std::to_string(action_->aid_) + ": " +
33 action_->to_string(true) + "\n";
34 for (auto node : children_)
35 final_string += node->string_of_whole_tree(indentation_level + 1);
39 PartialExecution WakeupTreeNode::get_sequence() const
41 // TODO: Prevent having to compute this at the node level
42 // and instead track this with the iterator
43 PartialExecution seq_;
44 const WakeupTreeNode* cur_node = this;
45 while (cur_node != nullptr && not cur_node->is_root()) {
46 seq_.push_front(cur_node->action_);
47 cur_node = cur_node->parent_;
52 void WakeupTreeNode::detatch_from_parent()
54 if (parent_ != nullptr) {
55 // TODO: There may be a better method
56 // of keeping track of a node's reference to
57 // its parent, perhaps keeping track
58 // of a std::list<>::iterator instead.
59 // This would allow us to detach a node
60 // in O(1) instead of O(|children|) time
61 parent_->children_.remove(this);
65 WakeupTree::WakeupTree() : WakeupTree(std::make_unique<WakeupTreeNode>()) {}
66 WakeupTree::WakeupTree(std::unique_ptr<WakeupTreeNode> root) : root_(root.get())
68 this->insert_node(std::move(root));
71 std::vector<std::string> WakeupTree::get_single_process_texts() const
73 std::vector<std::string> trace;
74 for (const auto* child : root_->children_) {
75 const auto t = child->get_action();
76 auto message = xbt::string_printf("Actor %ld: %s", t->aid_, t->to_string(true).c_str());
77 trace.emplace_back(std::move(message));
82 std::optional<aid_t> WakeupTree::get_min_single_process_actor() const
84 if (const auto node = get_min_single_process_node(); node.has_value()) {
85 return node.value()->get_actor();
90 std::optional<WakeupTreeNode*> WakeupTree::get_min_single_process_node() const
95 // INVARIANT: The induced post-order relation always places children
96 // in order before the parent. The list of children maintained by
97 // each node represents that ordering, and the first child of
98 // the root is by definition the smallest of the single-process nodes
99 xbt_assert(not this->root_->children_.empty(), "What the");
100 return this->root_->children_.front();
103 std::string WakeupTree::string_of_whole_tree() const
105 return root_->string_of_whole_tree(0);
108 WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
110 // Perform a BFS search to perform a deep copy of the portion
111 // of the tree underneath and including `root`. Note that `root`
112 // is contained within the context of a *different* wakeup tree;
113 // hence, we have to be careful to update each node's children
115 auto subtree = WakeupTree();
117 std::list<std::pair<WakeupTreeNode*, WakeupTreeNode*>> frontier{std::make_pair(root, subtree.root_)};
118 while (not frontier.empty()) {
119 auto [node_in_other_tree, subtree_equivalent] = frontier.front();
120 frontier.pop_front();
122 // For each child of the node corresponding to that in `subtree`,
123 // make clones of each of its children and add them to `frontier`
124 // to that their children are added, and so on.
125 for (WakeupTreeNode* child_in_other_tree : node_in_other_tree->get_ordered_children()) {
126 WakeupTreeNode* child_equivalent = subtree.make_node(child_in_other_tree->get_action());
127 subtree_equivalent->add_child(child_equivalent);
128 frontier.push_back(std::make_pair(child_in_other_tree, child_equivalent));
134 void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root)
136 if (not contains(root)) {
137 throw std::invalid_argument("Attempting to remove a subtree pivoted from a node "
138 "that is not contained in this wakeup tree");
141 std::list<WakeupTreeNode*> subtree_contents{root};
142 std::list<WakeupTreeNode*> frontier{root};
143 while (not frontier.empty()) {
144 const auto* node = frontier.front();
145 frontier.pop_front();
146 for (const auto& child : node->get_ordered_children()) {
147 frontier.push_back(child);
148 subtree_contents.push_back(child);
152 // After having found each node with BFS, now we can
153 // remove them. This prevents the "joys" of iteration during mutation.
154 // We also remove the `root` from being referenced by its own parent (since
155 // it will soon be destroyed)
156 root->detatch_from_parent();
157 for (WakeupTreeNode* node_to_remove : subtree_contents) {
158 this->remove_node(node_to_remove);
162 void WakeupTree::remove_subtree_at_aid(aid_t proc)
164 for (const auto& child : root_->get_ordered_children())
165 if (child->get_actor() == proc) {
166 this->remove_subtree_rooted_at(child);
171 void WakeupTree::remove_min_single_process_subtree()
173 if (const auto node = get_min_single_process_node(); node.has_value()) {
174 remove_subtree_rooted_at(node.value());
178 bool WakeupTree::contains(const WakeupTreeNode* node) const
180 return std::find_if(this->nodes_.begin(), this->nodes_.end(), [=](const auto& pair) { return pair.first == node; }) !=
184 WakeupTreeNode* WakeupTree::make_node(std::shared_ptr<Transition> u)
186 auto node = std::make_unique<WakeupTreeNode>(std::move(u));
187 auto* node_handle = node.get();
188 this->nodes_[node_handle] = std::move(node);
192 void WakeupTree::insert_node(std::unique_ptr<WakeupTreeNode> node)
194 auto* node_handle = node.get();
195 this->nodes_[node_handle] = std::move(node);
198 void WakeupTree::remove_node(WakeupTreeNode* node)
200 this->nodes_.erase(node);
203 WakeupTree::InsertionResult WakeupTree::insert(const Execution& E, const PartialExecution& w)
205 // See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
207 // Find the first node `v` in the tree such that
208 // `v ~_[E] w` and `v` is not a leaf node
209 for (WakeupTreeNode* node : *this) {
210 if (const auto shortest_sequence = E.get_shortest_odpor_sq_subset_insertion(node->get_sequence(), w);
211 shortest_sequence.has_value()) {
212 // Insert the sequence as a child of `node`, but only
213 // if the node is not already a leaf
214 if (not node->is_leaf() || node == this->root_) {
215 // NOTE: It's entirely possible that the shortest
216 // sequence we are inserting is empty. Consider the
217 // following two cases:
219 // 1. `w` is itself empty. Evidently, insertion succeeds but nothing needs
222 // 2. a leaf node in the tree already contains `w` exactly.
223 // In this case, the empty `w'` returned (viz. `shortest_seq`)
224 // such that `w [=_[E] v.w'` would be empty
225 this->insert_sequence_after(node, shortest_sequence.value());
226 return node == this->root_ ? InsertionResult::root : InsertionResult::interior_node;
228 // Since we're following the post-order traversal of the tree,
229 // the first such node we see is the smallest w.r.t "<"
230 return InsertionResult::leaf;
233 xbt_die("Insertion should always succeed with the root node (which contains no "
234 "prior execution). If we've reached this point, this implies either that "
235 "the wakeup tree traversal is broken or that computation of the shortest "
236 "sequence to insert into the tree is broken");
239 void WakeupTree::insert_sequence_after(WakeupTreeNode* node, const PartialExecution& w)
241 WakeupTreeNode* cur_node = node;
242 for (const auto& w_i : w) {
243 WakeupTreeNode* new_node = this->make_node(w_i);
244 cur_node->add_child(new_node);
249 } // namespace simgrid::mc::odpor