Fix WakeupTreeIterator bug comparing diff iterators

Prior to this commit, the WakeupTreeIterator
compared iterators stemming from different
collections. This isn't defined behavior though :/.

The goal was to determine if a node should add its
children again when moving to the next node in the
iteration. Instead it suffices to keep track of which
nodes have already added their children after adding
them to the ordering.

diff --git a/src/mc/explo/odpor/WakeupTreeIterator.cpp b/src/mc/explo/odpor/WakeupTreeIterator.cpp
index 6c81203..9017fd8 100644 (file)
--- a/src/mc/explo/odpor/WakeupTreeIterator.cpp
+++ b/src/mc/explo/odpor/WakeupTreeIterator.cpp
@@ -5,6 +5,7 @@
 
 #include "src/mc/explo/odpor/WakeupTreeIterator.hpp"
 #include "src/mc/explo/odpor/WakeupTree.hpp"
+#include "xbt/asserts.h"
 
 namespace simgrid::mc::odpor {
 
@@ -20,19 +21,19 @@ void WakeupTreeIterator::push_until_left_most_found()
   // there are no cycles. This means that at least
   // one node in the tree won't have any children,
   // so the loop will eventually terminate
-  auto* cur_top_node = *post_order_iteration.top();
+  WakeupTreeNode* cur_top_node = *post_order_iteration.top();
   while (not cur_top_node->is_leaf()) {
     // INVARIANT: Since we push children in
     // reverse order (right-most to left-most),
     // we ensure that we'll always process left-most
     // children first
     auto& children = cur_top_node->children_;
-
     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
+      // iter.base() points one element past where we seek; that is,
+      // we want the value one position forward
       post_order_iteration.push(std::prev(iter.base()));
     }
+    has_added_children.push(cur_top_node);
     cur_top_node = *post_order_iteration.top();
   }
 }
@@ -46,7 +47,6 @@ void WakeupTreeIterator::increment()
     return;
   }
 
-  auto prev_top_handle = post_order_iteration.top();
   post_order_iteration.pop();
 
   // If there are now no longer any nodes left,
@@ -57,15 +57,28 @@ void WakeupTreeIterator::increment()
     return;
   }
 
-  // Otherwise, look at the next top node. If
-  // `prev_top` is that node's right-most child,
-  // then we don't attempt to re-add `next_top`'s
-  // children again for we would have already seen them.
-  // To actually determine "right-most", we check if
-  // moving over to the right one spot brings us to the
-  // end of the candidate parent's list
-  const auto* next_top_node = *post_order_iteration.top();
-  if ((++prev_top_handle) != next_top_node->get_ordered_children().end()) {
+  xbt_assert(not has_added_children.empty(), "Invariant violated: There are more "
+                                             "nodes in the iteration that we must search "
+                                             "yet nobody has claimed to have added these nodes. "
+                                             "This implies that the algorithm is not iterating over "
+                                             "the wakeup tree is not following the post-fix order "
+                                             "correctly");
+
+  // Otherwise, look at what is the new, current top node.
+  // We're traversing the tree in
+  //
+  // If we've already added our children, we want
+  // to be sure not to add them again; but we ALSO
+  // want to be sure that we now start checking against
+  // the the node that's next in line as "finished"
+  //
+  // INVARIANT: Since we're searching in post-fix order,
+  // it always suffices to compare the current node
+  // with the top of the stack of nodes which have added their
+  // children
+  if (*post_order_iteration.top() == has_added_children.top()) {
+    has_added_children.pop();
+  } else {
     push_until_left_most_found();
   }
 }

diff --git a/src/mc/explo/odpor/WakeupTreeIterator.hpp b/src/mc/explo/odpor/WakeupTreeIterator.hpp
index e42184c..c33d483 100644 (file)
--- a/src/mc/explo/odpor/WakeupTreeIterator.hpp
+++ b/src/mc/explo/odpor/WakeupTreeIterator.hpp
@@ -56,6 +56,18 @@ private:
    */
   std::stack<node_handle> post_order_iteration;
 
+  /**
+   * @brief The nodes in the current ordering that have already
+   * added their own children
+   *
+   * We need to be able to determine whether to add the children
+   * of a given node. Eventually, we want to search that node itself,
+   * but we have to first search its children. Later, when we
+   * reach each node in this stack again, we'll remember not to add
+   * its children and will search the node in the stack instead.
+   */
+  std::stack<WakeupTreeNode*> has_added_children;
+
   /**
    * @brief Search the wakeup tree until a leaf node appears at the front
    * of the iteration, pushing all children towards the top of the stack