FindChallenges explores the Miniscript node tree by going deep into the first child’s subtree, then the second, and so on - effectively performing a pre-order Traversal (Depth-First Search) recursively, using the call stack which can result in stack overflows on Windows debug builds.
This change replaces the recursive implementation with an iterative version using an explicit stack. The new implementation also performs a pre-order depth-first traversal, though it processes children in right-to-left order (rather than left-to-right) due to the LIFO nature of the stack. Since both versions store results in a std::set, which automatically sorts and deduplicates elements, the exact traversal order doesn’t affect the final result.
It is an alternative to increasing the Windows stack size, as proposed in #32349, and addresses the issue raised in #32341 by avoiding deep recursion altogether.
The change is done in two commits:
- add a new iterative
FindChallengesmethod and rename the old method to*_recursive(to simplify the next commit where we remove it), asserting that its result matches the original; - remove the original recursive implementation.
This approach avoids ignoring the misc-no-recursion warning as well.
I tried modifying the new method to store results in a vector instead, but it demonstrated that the deduplication provided by std::set was necessary. One example showing the need for deduplication:
Recursive (using set):
0 (6, 9070746)
1 (6, 19532513)
2 (6, 3343376967)
Iterative (using vector attempt):
0 (6, 19532513)
1 (6, 9070746)
2 (6, 3343376967)
3 (6, 9070746) // Duplicate entry
The performance of the test is the same as before, with the recursive method.
