src/mc/explo/odpor/WakeupTree.cpp

   1 /* Copyright (c) 2008-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/mc/explo/odpor/WakeupTree.hpp"
   7 #include "src/mc/explo/odpor/Execution.hpp"
   8 #include "xbt/asserts.h"
   9 #include "xbt/string.hpp"
  10
  11 #include <algorithm>
  12 #include <exception>
  13 #include <memory>
  14 #include <queue>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_wut, mc, "Logging specific to ODPOR WakeupTrees");
  17
  18
  19 namespace simgrid::mc::odpor {
  20
  21 void WakeupTreeNode::add_child(WakeupTreeNode* node)
  22 {
  23   this->children_.push_back(node);
  24   node->parent_ = this;
  25 }
  26
  27 std::string WakeupTreeNode::string_of_whole_tree(int indentation_level) const
  28 {
  29   std::string tabulations = "";
  30   for (int i = 0; i < indentation_level; i++)
  31     tabulations += "  ";
  32   std::string final_string = action_ == nullptr ? "<>\n" :
  33       tabulations + "Actor " + std::to_string(action_->aid_) + ": " + action_->to_string(true) + "\n";
  34   for (auto node : children_)
  35     final_string += node->string_of_whole_tree(indentation_level + 1);
  36   return final_string;
  37 }
  38
  39 PartialExecution WakeupTreeNode::get_sequence() const
  40 {
  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_;
  48   }
  49   return seq_;
  50 }
  51
  52 void WakeupTreeNode::detatch_from_parent()
  53 {
  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);
  62   }
  63 }
  64
  65 WakeupTree::WakeupTree() : WakeupTree(std::make_unique<WakeupTreeNode>()) {}
  66 WakeupTree::WakeupTree(std::unique_ptr<WakeupTreeNode> root) : root_(root.get())
  67 {
  68   this->insert_node(std::move(root));
  69 }
  70
  71 std::vector<std::string> WakeupTree::get_single_process_texts() const
  72 {
  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));
  78   }
  79   return trace;
  80 }
  81
  82 std::optional<aid_t> WakeupTree::get_min_single_process_actor() const
  83 {
  84   if (const auto node = get_min_single_process_node(); node.has_value()) {
  85     return node.value()->get_actor();
  86   }
  87   return std::nullopt;
  88 }
  89
  90 std::optional<WakeupTreeNode*> WakeupTree::get_min_single_process_node() const
  91 {
  92   if (empty()) {
  93     return std::nullopt;
  94   }
  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();
 101 }
 102
 103 std::string WakeupTree::string_of_whole_tree() const
 104 {
 105   return root_->string_of_whole_tree(0);
 106 }
 107
 108 WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
 109 {
 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
 114   // appropriately
 115   auto subtree = WakeupTree();
 116
 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();
 121
 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));
 129     }
 130   }
 131   return subtree;
 132 }
 133
 134 void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root)
 135 {
 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");
 139   }
 140
 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);
 149     }
 150   }
 151
 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);
 159   }
 160 }
 161
 162 void WakeupTree::remove_min_single_process_subtree()
 163 {
 164   if (const auto node = get_min_single_process_node(); node.has_value()) {
 165     remove_subtree_rooted_at(node.value());
 166   }
 167 }
 168
 169 bool WakeupTree::contains(const WakeupTreeNode* node) const
 170 {
 171   return std::find_if(this->nodes_.begin(), this->nodes_.end(), [=](const auto& pair) { return pair.first == node; }) !=
 172          this->nodes_.end();
 173 }
 174
 175 WakeupTreeNode* WakeupTree::make_node(std::shared_ptr<Transition> u)
 176 {
 177   auto node                 = std::make_unique<WakeupTreeNode>(std::move(u));
 178   auto* node_handle         = node.get();
 179   this->nodes_[node_handle] = std::move(node);
 180   return node_handle;
 181 }
 182
 183 void WakeupTree::insert_node(std::unique_ptr<WakeupTreeNode> node)
 184 {
 185   auto* node_handle         = node.get();
 186   this->nodes_[node_handle] = std::move(node);
 187 }
 188
 189 void WakeupTree::remove_node(WakeupTreeNode* node)
 190 {
 191   this->nodes_.erase(node);
 192 }
 193
 194 WakeupTree::InsertionResult WakeupTree::insert(const Execution& E, const PartialExecution& w)
 195 {
 196   // See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
 197
 198   // Find the first node `v` in the tree such that
 199   // `v ~_[E] w` and `v`  is not a leaf node
 200   for (WakeupTreeNode* node : *this) {
 201     if (const auto shortest_sequence = E.get_shortest_odpor_sq_subset_insertion(node->get_sequence(), w);
 202         shortest_sequence.has_value()) {
 203       // Insert the sequence as a child of `node`, but only
 204       // if the node is not already a leaf
 205       if (not node->is_leaf() || node == this->root_) {
 206         // NOTE: It's entirely possible that the shortest
 207         // sequence we are inserting is empty. Consider the
 208         // following two cases:
 209         //
 210         // 1. `w` is itself empty. Evidently, insertion succeeds but nothing needs
 211         // to happen
 212         //
 213         // 2. a leaf node in the tree already contains `w` exactly.
 214         // In this case, the empty `w'` returned (viz. `shortest_seq`)
 215         // such that `w [=_[E] v.w'` would be empty
 216         this->insert_sequence_after(node, shortest_sequence.value());
 217         return node == this->root_ ? InsertionResult::root : InsertionResult::interior_node;
 218       }
 219       // Since we're following the post-order traversal of the tree,
 220       // the first such node we see is the smallest w.r.t "<"
 221       return InsertionResult::leaf;
 222     }
 223   }
 224   xbt_die("Insertion should always succeed with the root node (which contains no "
 225           "prior execution). If we've reached this point, this implies either that "
 226           "the wakeup tree traversal is broken or that computation of the shortest "
 227           "sequence to insert into the tree is broken");
 228 }
 229
 230 void WakeupTree::insert_sequence_after(WakeupTreeNode* node, const PartialExecution& w)
 231 {
 232   WakeupTreeNode* cur_node = node;
 233   for (const auto& w_i : w) {
 234     WakeupTreeNode* new_node = this->make_node(w_i);
 235     cur_node->add_child(new_node);
 236     cur_node = new_node;
 237   }
 238 }
 239
 240 } // namespace simgrid::mc::odpor