Skip to content

Fix `WakeupTreeIterator` bug comparing different iterators

Overview

Prior to this commit, the WakeupTreeIterator compared iterators stemming from different collections. This is undefined behavior though and not the intended use of iterators anyway.

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 (i.e. which explicit WakeupTreeNode*) have already added their children after adding them to the ordering. Once we re-encounter the node in the ordering, we check whether we've already searched that node's children by referencing a different stack which tracks this information and, if so, simply prevent re-adding the node's children.

Merge request reports