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
  10 #include <algorithm>
  11 #include <exception>
  12 #include <queue>
  13
  14 namespace simgrid::mc::odpor {
  15
  16 aid_t WakeupTreeNode::get_first_actor() const
  17 {
  18   if (seq_.empty()) {
  19     throw std::invalid_argument("Attempted to extract the first actor from "
  20                                 "a node in a wakeup tree representing the "
  21                                 "empty execution (likely the root node)");
  22   }
  23   return get_sequence().front()->aid_;
  24 }
  25
  26 void WakeupTreeNode::add_child(WakeupTreeNode* node)
  27 {
  28   this->children_.push_back(node);
  29   node->parent_ = this;
  30 }
  31
  32 WakeupTreeNode::~WakeupTreeNode()
  33 {
  34   if (parent_ != nullptr) {
  35     // TODO: We can probably be more clever here: when
  36     // we add the child to a node, we could perhaps
  37     // try instead to keep a reference to position of the
  38     // child in the list of the parent.
  39     parent_->children_.remove(this);
  40   }
  41 }
  42
  43 WakeupTree::WakeupTree() : WakeupTree(std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode({}))) {}
  44 WakeupTree::WakeupTree(std::unique_ptr<WakeupTreeNode> root) : root_(root.get())
  45 {
  46   this->insert_node(std::move(root));
  47 }
  48
  49 WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
  50 {
  51   if (not root->is_single_process()) {
  52     throw std::invalid_argument("Selecting subtrees is only defined for single-process nodes");
  53   }
  54
  55   const aid_t p = root->get_first_actor();
  56
  57   // Perform a BFS search to perform a deep copy of the portion
  58   // of the tree underneath and including `root`. Note that `root`
  59   // is contained within the context of a *different* wakeup tree;
  60   // hence, we have to be careful to update each node's children
  61   // appropriately
  62   auto subtree = WakeupTree();
  63
  64   std::list<std::pair<WakeupTreeNode*, WakeupTreeNode*>> frontier{std::make_pair(root, subtree.root_)};
  65   while (not frontier.empty()) {
  66     auto [node_in_other_tree, subtree_equivalent] = frontier.front();
  67     frontier.pop_front();
  68
  69     // For each child of the node corresponding to that in `subtree`,
  70     // make clones of each of its children and add them to `frontier`
  71     // to that their children are added, and so on. Note that the subtree
  72     // **explicitly** removes the first process from each child
  73     for (WakeupTreeNode* child_in_other_tree : node_in_other_tree->get_ordered_children()) {
  74       auto p_w           = child_in_other_tree->get_sequence();
  75       const auto p_again = p_w.front()->aid_;
  76
  77       // INVARIANT: A nodes of a wakeup tree form a prefix-closed set;
  78       // this means that any child node `c` of a node `n` must contain
  79       // `n.get_sequence()` as a prefix of `c.get_sequence()`
  80       xbt_assert(p_again == p,
  81                  "Invariant Violation: The wakeup tree from which a subtree with actor "
  82                  "`%ld` is being taken is not prefix free! The child node starts with "
  83                  "`%ld` while the parent is `%ld`! This indicates that there "
  84                  "is a bug in the insertion logic for the wakeup tree",
  85                  p, p_again, p);
  86       p_w.pop_front();
  87
  88       WakeupTreeNode* child_equivalent = subtree.make_node(p_w);
  89       frontier.push_back(std::make_pair(child_in_other_tree, child_equivalent));
  90     }
  91   }
  92   return subtree;
  93 }
  94
  95 void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root)
  96 {
  97   if (not contains(root)) {
  98     throw std::invalid_argument("Attempting to remove a subtree pivoted from a node "
  99                                 "that is not contained in this wakeup tree");
 100   }
 101
 102   std::list<WakeupTreeNode*> subtree_contents{root};
 103   std::list<WakeupTreeNode*> frontier{root};
 104   while (not frontier.empty()) {
 105     auto node = frontier.front();
 106     frontier.pop_front();
 107     for (const auto& child : node->get_ordered_children()) {
 108       frontier.push_back(child);
 109       subtree_contents.push_back(child);
 110     }
 111   }
 112
 113   // After having found each node with BFS, now we can
 114   // remove them. This prevents the "joys" of iteration during mutation
 115   for (WakeupTreeNode* node_to_remove : subtree_contents) {
 116     this->remove_node(node_to_remove);
 117   }
 118 }
 119
 120 bool WakeupTree::contains(WakeupTreeNode* node) const
 121 {
 122   return std::find_if(this->nodes_.begin(), this->nodes_.end(), [=](const auto& pair) { return pair.first == node; }) !=
 123          this->nodes_.end();
 124 }
 125
 126 WakeupTreeNode* WakeupTree::make_node(const PartialExecution& u)
 127 {
 128   auto node                 = std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode(u));
 129   auto* node_handle         = node.get();
 130   this->nodes_[node_handle] = std::move(node);
 131   return node_handle;
 132 }
 133
 134 void WakeupTree::insert_node(std::unique_ptr<WakeupTreeNode> node)
 135 {
 136   auto* node_handle         = node.get();
 137   this->nodes_[node_handle] = std::move(node);
 138 }
 139
 140 void WakeupTree::remove_node(WakeupTreeNode* node)
 141 {
 142   this->nodes_.erase(node);
 143 }
 144
 145 void WakeupTree::insert(const Execution& E, const PartialExecution& w)
 146 {
 147   // See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
 148
 149   // Find the first node `v` in the tree such that
 150   // `v ~_[E] w` and `v`  is not a leaf node
 151   for (WakeupTreeNode* node : *this) {
 152     if (const auto shortest_sequence = E.get_shortest_odpor_sq_subset_insertion(node->get_sequence(), w);
 153         shortest_sequence.has_value()) {
 154       // Insert the sequence as a child of `node`, but only
 155       // if the node is not already a leaf
 156       if (not node->is_leaf() or node == this->root_) {
 157         WakeupTreeNode* new_node = this->make_node(shortest_sequence.value());
 158         node->add_child(new_node);
 159       }
 160       // Since we're following the post-order traversal of the tree,
 161       // the first such node we see is the smallest w.r.t "<"
 162       return;
 163     }
 164   }
 165 }
 166
 167 } // namespace simgrid::mc::odpor