Automatically remove nodes from parents

After removing a node from a WakeupTree,
we need to be careful to also have any references
to the node removed, viz. that held onto the
parent of the node in the list of children.
This commit adds a back reference to the
parent node of a given WakeupTreeNode to
allow removal from the parent when destroyed.

Additionally, some bugs were fixed for creating
subtrees and removing subtrees (we forgot to remove
the root for example)

diff --git a/src/mc/api/State.cpp b/src/mc/api/State.cpp
index 7606d26..fb2a806 100644 (file)
--- a/src/mc/api/State.cpp
+++ b/src/mc/api/State.cpp
@@ -206,10 +206,10 @@ void State::sprout_tree_from_parent_state()
   xbt_assert(parent_state_ != nullptr, "Attempting to construct a wakeup tree for the root state "
                                        "(or what appears to be, rather for state without a parent defined)");
   const auto p      = parent_state_->get_transition_out()->aid_;
-  const auto branch = std::find_if(wakeup_tree_.begin(), wakeup_tree_.end(), [=](const odpor::WakeupTreeNode* node) {
-    return node->is_single_process() && node->get_first_actor() == p;
-  });
-  xbt_assert(branch != wakeup_tree_.end(),
+  const auto branch = std::find_if(
+      parent_state_->wakeup_tree_.begin(), parent_state_->wakeup_tree_.end(),
+      [=](const odpor::WakeupTreeNode* node) { return node->is_single_process() && node->get_first_actor() == p; });
+  xbt_assert(branch != parent_state_->wakeup_tree_.end(),
              "Attempted to create a subtree from the wakeup tree of the parent "
              "state using actor `%ld`, but no such subtree could be found. "
              "This implies that the wakeup tree management is broken, "

diff --git a/src/mc/explo/odpor/WakeupTree.cpp b/src/mc/explo/odpor/WakeupTree.cpp
index 9335c69..33a0fb6 100644 (file)
--- a/src/mc/explo/odpor/WakeupTree.cpp
+++ b/src/mc/explo/odpor/WakeupTree.cpp
@@ -23,6 +23,23 @@ aid_t WakeupTreeNode::get_first_actor() const
   return get_sequence().front()->aid_;
 }
 
+void WakeupTreeNode::add_child(WakeupTreeNode* node)
+{
+  this->children_.push_back(node);
+  node->parent_ = this;
+}
+
+WakeupTreeNode::~WakeupTreeNode()
+{
+  if (parent_ != nullptr) {
+    // TODO: We can probably be more clever here: when
+    // we add the child to a node, we could perhaps
+    // try instead to keep a reference to position of the
+    // child in the list of the parent.
+    parent_->children_.remove(this);
+  }
+}
+
 WakeupTree::WakeupTree() : WakeupTree(std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode({}))) {}
 WakeupTree::WakeupTree(std::unique_ptr<WakeupTreeNode> root) : root_(root.get())
 {
@@ -35,17 +52,16 @@ WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
     throw std::invalid_argument("Selecting subtrees is only defined for single-process nodes");
   }
 
-  const aid_t p = (*(root->get_sequence().begin()))->aid_;
+  const aid_t p = root->get_first_actor();
 
   // Perform a BFS search to perform a deep copy of the portion
   // of the tree underneath and including `root`. Note that `root`
   // is contained within the context of a *different* wakeup tree;
   // hence, we have to be careful to update each node's children
   // appropriately
-  auto subtree                    = WakeupTree();
-  WakeupTreeNode* root_equivalent = subtree.make_node(root->get_sequence());
+  auto subtree = WakeupTree();
 
-  std::list<std::pair<WakeupTreeNode*, WakeupTreeNode*>> frontier{std::make_pair(root, root_equivalent)};
+  std::list<std::pair<WakeupTreeNode*, WakeupTreeNode*>> frontier{std::make_pair(root, subtree.root_)};
   while (not frontier.empty()) {
     auto [node_in_other_tree, subtree_equivalent] = frontier.front();
     frontier.pop_front();
@@ -70,7 +86,6 @@ WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
       p_w.pop_front();
 
       WakeupTreeNode* child_equivalent = subtree.make_node(p_w);
-      subtree_equivalent->add_child(child_equivalent);
       frontier.push_back(std::make_pair(child_in_other_tree, child_equivalent));
     }
   }
@@ -84,7 +99,7 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root)
                                 "that is not contained in this wakeup tree");
   }
 
-  std::list<WakeupTreeNode*> subtree_contents;
+  std::list<WakeupTreeNode*> subtree_contents{root};
   std::list<WakeupTreeNode*> frontier{root};
   while (not frontier.empty()) {
     auto node = frontier.front();
@@ -96,7 +111,7 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root)
   }
 
   // After having found each node with BFS, now we can
-  // remove them. This prevents the "joys" iteration during mutation
+  // remove them. This prevents the "joys" of iteration during mutation
   for (WakeupTreeNode* node_to_remove : subtree_contents) {
     this->remove_node(node_to_remove);
   }

diff --git a/src/mc/explo/odpor/WakeupTree.hpp b/src/mc/explo/odpor/WakeupTree.hpp
index 553667c..7a6eb27 100644 (file)
--- a/src/mc/explo/odpor/WakeupTree.hpp
+++ b/src/mc/explo/odpor/WakeupTree.hpp
@@ -10,6 +10,7 @@
 #include "src/mc/explo/odpor/odpor_forward.hpp"
 
 #include <memory>
+#include <optional>
 #include <unordered_map>
 
 namespace simgrid::mc::odpor {
@@ -19,6 +20,8 @@ private:
   explicit WakeupTreeNode(const PartialExecution& u) : seq_(u) {}
   explicit WakeupTreeNode(PartialExecution&& u) : seq_(std::move(u)) {}
 
+  WakeupTreeNode* parent_ = nullptr;
+
   /** An ordered list of children of for this node in the tree */
   std::list<WakeupTreeNode*> children_;
 
@@ -30,6 +33,7 @@ private:
   friend WakeupTreeIterator;
 
 public:
+  ~WakeupTreeNode();
   WakeupTreeNode(const WakeupTreeNode&)            = delete;
   WakeupTreeNode(WakeupTreeNode&&)                 = default;
   WakeupTreeNode& operator=(const WakeupTreeNode&) = delete;
@@ -47,7 +51,7 @@ public:
   aid_t get_first_actor() const;
 
   /** Insert a node `node` as a new child of this node */
-  void add_child(WakeupTreeNode* node) { this->children_.push_back(node); }
+  void add_child(WakeupTreeNode* node);
 };
 
 class WakeupTree {

diff --git a/src/mc/explo/odpor/WakeupTreeIterator.cpp b/src/mc/explo/odpor/WakeupTreeIterator.cpp
index eb3d219..6c81203 100644 (file)
--- a/src/mc/explo/odpor/WakeupTreeIterator.cpp
+++ b/src/mc/explo/odpor/WakeupTreeIterator.cpp
@@ -31,7 +31,7 @@ void WakeupTreeIterator::push_until_left_most_found()
     for (auto iter = children.rbegin(); iter != children.rend(); ++iter) {
       // iter.base() points one element past where we seek; hence,
       // we move it over one position
-      post_order_iteration.push((--iter.base()));
+      post_order_iteration.push(std::prev(iter.base()));
     }
     cur_top_node = *post_order_iteration.top();
   }