Method TreeEvalMaybe

src/script/miniscript.h:652–713

     */
    template<typename Result, typename State, typename DownFn, typename UpFn>
    std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
    {
        /** Entries of the explicit stack tracked in this algorithm. */
        struct StackElem
        {
            const Node& node; //!< The node being evaluated.
            size_t expanded; //!< How many children of this node have been expanded.
            State state; //!< The state for that node.

            StackElem(const Node& node_, size_t exp_, State&& state_) :
                node(node_), expanded(exp_), state(std::move(state_)) {}
        };
        /* Stack of tree nodes being explored. */
        std::vector<StackElem> stack;
        /* Results of subtrees so far. Their order and mapping to tree nodes
         * is implicitly defined by stack. */
        std::vector<Result> results;
        stack.emplace_back(*this, 0, std::move(root_state));

        /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
         * State variables are omitted for simplicity.
         *
         * First: stack=[(A,0)] results=[]
         *        stack=[(A,1),(B,0)] results=[]
         *        stack=[(A,1)] results=[B]
         *        stack=[(A,2),(C,0)] results=[B]
         *        stack=[(A,2),(C,1),(D,0)] results=[B]
         *        stack=[(A,2),(C,1)] results=[B,D]
         *        stack=[(A,2),(C,2),(E,0)] results=[B,D]
         *        stack=[(A,2),(C,2)] results=[B,D,E]
         *        stack=[(A,2)] results=[B,C]
         *        stack=[(A,3),(F,0)] results=[B,C]
         *        stack=[(A,3)] results=[B,C,F]
         * Final: stack=[] results=[A]
         */
        while (stack.size()) {
            const Node& node = stack.back().node;
            if (stack.back().expanded < node.subs.size()) {
                /* We encounter a tree node with at least one unexpanded child.
                 * Expand it. By the time we hit this node again, the result of
                 * that child (and all earlier children) will be at the end of `results`. */
                size_t child_index = stack.back().expanded++;
                State child_state = downfn(stack.back().state, node, child_index);
                stack.emplace_back(node.subs[child_index], 0, std::move(child_state));
                continue;
            }
            // Invoke upfn with the last node.subs.size() elements of results as input.
            assert(results.size() >= node.subs.size());
            std::optional<Result> result{upfn(std::move(stack.back().state), node,
                std::span<Result>{results}.last(node.subs.size()))};
            // If evaluation returns std::nullopt, abort immediately.
            if (!result) return {};
            // Replace the last node.subs.size() elements of results with the new result.
            results.erase(results.end() - node.subs.size(), results.end());
            results.push_back(std::move(*result));
            stack.pop_back();
        }
        // The final remaining results element is the root result, return it.