Inside Bitcoin

501    static constexpr SatInfo OP_SIZE() noexcept { return {-1, 0}; }
502    static constexpr SatInfo OP_CHECKSIG() noexcept { return {1, 1}; }
503    static constexpr SatInfo OP_0NOTEQUAL() noexcept { return {0, 0}; }
504    static constexpr SatInfo OP_VERIFY() noexcept { return {1, 1}; }
505};
506
507class StackSize
508{
509    SatInfo sat, dsat;
510
511public:
512    constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {};
513    constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {};
514
515    const SatInfo& Sat() const { return sat; }
516    const SatInfo& Dsat() const { return dsat; }
517};
518
519struct WitnessSize {
520    //! Maximum witness size to satisfy;
521    MaxInt<uint32_t> sat;
522    //! Maximum witness size to dissatisfy;
523    MaxInt<uint32_t> dsat;
524
525    WitnessSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
526};
527
528struct NoDupCheck {};
529
530} // namespace internal
531
532//! A node in a miniscript expression.
533template <typename Key>
534class Node
535{
536    //! What node type this node is.
537    enum Fragment fragment;
538    //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
539    uint32_t k = 0;
540    //! The keys used by this expression (only for PK_K/PK_H/MULTI)
541    std::vector<Key> keys;
542    //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD160).
543    std::vector<unsigned char> data;
544    //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
545    std::vector<Node> subs;
546    //! The Script context for this node. Either P2WSH or Tapscript.
547    MiniscriptContext m_script_ctx;
548
549public:
550    // Permit 1 level deep recursion since we own instances of our own type.
551    // NOLINTBEGIN(misc-no-recursion)
552    ~Node()
553    {
554        // Destroy the subexpressions iteratively after moving out their
555        // subexpressions to avoid a stack-overflow due to recursive calls to
556        // the subs' destructors.
557        // We move vectors in order to only update array-pointers inside them
558        // rather than moving individual Node instances which would involve
559        // moving/copying each Node field.
560        std::vector<std::vector<Node>> queue;
561        queue.push_back(std::move(subs));
562        do {
563            auto flattening{std::move(queue.back())};
564            queue.pop_back();
565            for (Node& n : flattening) {
566                if (!n.subs.empty()) queue.push_back(std::move(n.subs));
567            }
568        } while (!queue.empty());
569    }
570    // NOLINTEND(misc-no-recursion)
571
572    Node<Key> Clone() const
573    {
574        // Use TreeEval() to avoid a stack-overflow due to recursion
575        auto upfn = [](const Node& node, std::span<Node> children) {
576            std::vector<Node> new_subs;
577            for (auto& child : children) {
578                // It's fine to move from children as they are new nodes having
579                // been produced by calling this function one level down.
580                new_subs.push_back(std::move(child));
581            }
582            return Node{internal::NoDupCheck{}, node.m_script_ctx, node.fragment, std::move(new_subs), node.keys, node.data, node.k};
583        };
584        return TreeEval<Node>(upfn);
585    }
586
587    enum Fragment Fragment() const { return fragment; }
588    uint32_t K() const { return k; }
589    const std::vector<Key>& Keys() const { return keys; }
590    const std::vector<unsigned char>& Data() const { return data; }
591    const std::vector<Node>& Subs() const { return subs; }
592
593private:
594    //! Cached ops counts.
595    internal::Ops ops;
596    //! Cached stack size bounds.
597    internal::StackSize ss;
598    //! Cached witness size bounds.
599    internal::WitnessSize ws;
600    //! Cached expression type (computed by CalcType and fed through SanitizeType).
601    Type typ;
602    //! Cached script length (computed by CalcScriptLen).
603    size_t scriptlen;
604    //! Whether a public key appears more than once in this node. This value is initialized
605    //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the
606    //! computation, requiring it to be done manually by invoking DuplicateKeyCheck().
607    //! DuplicateKeyCheck(), or a non-NoDupCheck constructor, will compute has_duplicate_keys
608    //! for all subnodes as well.
609    mutable std::optional<bool> has_duplicate_keys;
610
611    // Constructor which takes all of the data that a Node could possibly contain.
612    // This is kept private as no valid fragment has all of these arguments.
613    // Only used by Clone()
614    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, std::vector<unsigned char> arg, uint32_t val)
615        : fragment(nt), k(val), keys(std::move(key)), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
616
617    //! Compute the length of the script for this miniscript (including children).
618    size_t CalcScriptLen() const
619    {
620        size_t subsize = 0;
621        for (const auto& sub : subs) {
622            subsize += sub.ScriptSize();
623        }
624        Type sub0type = subs.size() > 0 ? subs[0].GetType() : ""_mst;
625        return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx);
626    }
627
628    /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
629     *
630     * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
631     * result can be thought of as first using downfn to compute a "state" for each node,
632     * from the root down to the leaves. Then upfn is used to compute a "result" for each
633     * node, from the leaves back up to the root, which is then returned. In the actual
634     * implementation, both functions are invoked in an interleaved fashion, performing a
635     * depth-first traversal of the tree.
636     *
637     * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
638     * - root is the state of the root node, of type State.
639     * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
640     *   node, its state, and an index of one of its children, computes the state of that
641     *   child. It can modify the state. Children of a given node will have downfn()
642     *   called in order.
643     * - upfn is a callable (State&&, const Node&, std::span<Result>) -> std::optional<Result>,
644     *   which given a node, its state, and a span of the results of its children,
645     *   computes the result of the node. If std::nullopt is returned by upfn,
646     *   TreeEvalMaybe() immediately returns std::nullopt.
647     * The return value of TreeEvalMaybe is the result of the root node.
648     *
649     * Result type cannot be bool due to the std::vector<bool> specialization.
650     */
651    template<typename Result, typename State, typename DownFn, typename UpFn>
652    std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
653    {
654        /** Entries of the explicit stack tracked in this algorithm. */
655        struct StackElem
656        {
657            const Node& node; //!< The node being evaluated.
658            size_t expanded; //!< How many children of this node have been expanded.
659            State state; //!< The state for that node.
660
661            StackElem(const Node& node_, size_t exp_, State&& state_) :
662                node(node_), expanded(exp_), state(std::move(state_)) {}
663        };
664        /* Stack of tree nodes being explored. */
665        std::vector<StackElem> stack;
666        /* Results of subtrees so far. Their order and mapping to tree nodes
667         * is implicitly defined by stack. */
668        std::vector<Result> results;
669        stack.emplace_back(*this, 0, std::move(root_state));
670
671        /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
672         * State variables are omitted for simplicity.
673         *
674         * First: stack=[(A,0)] results=[]
675         *        stack=[(A,1),(B,0)] results=[]
676         *        stack=[(A,1)] results=[B]
677         *        stack=[(A,2),(C,0)] results=[B]
678         *        stack=[(A,2),(C,1),(D,0)] results=[B]
679         *        stack=[(A,2),(C,1)] results=[B,D]
680         *        stack=[(A,2),(C,2),(E,0)] results=[B,D]
681         *        stack=[(A,2),(C,2)] results=[B,D,E]
682         *        stack=[(A,2)] results=[B,C]
683         *        stack=[(A,3),(F,0)] results=[B,C]
684         *        stack=[(A,3)] results=[B,C,F]
685         * Final: stack=[] results=[A]
686         */
687        while (stack.size()) {
688            const Node& node = stack.back().node;
689            if (stack.back().expanded < node.subs.size()) {
690                /* We encounter a tree node with at least one unexpanded child.
691                 * Expand it. By the time we hit this node again, the result of
692                 * that child (and all earlier children) will be at the end of `results`. */
693                size_t child_index = stack.back().expanded++;
694                State child_state = downfn(stack.back().state, node, child_index);
695                stack.emplace_back(node.subs[child_index], 0, std::move(child_state));
696                continue;
697            }
698            // Invoke upfn with the last node.subs.size() elements of results as input.
699            assert(results.size() >= node.subs.size());
700            std::optional<Result> result{upfn(std::move(stack.back().state), node,
701                std::span<Result>{results}.last(node.subs.size()))};
702            // If evaluation returns std::nullopt, abort immediately.
703            if (!result) return {};
704            // Replace the last node.subs.size() elements of results with the new result.
705            results.erase(results.end() - node.subs.size(), results.end());
706            results.push_back(std::move(*result));
707            stack.pop_back();
708        }
709        // The final remaining results element is the root result, return it.
710        assert(results.size() >= 1);
711        CHECK_NONFATAL(results.size() == 1);
712        return std::move(results[0]);
713    }
714
715    /** Like TreeEvalMaybe, but without downfn or State type.
716     * upfn takes (const Node&, std::span<Result>) and returns std::optional<Result>. */
717    template<typename Result, typename UpFn>
718    std::optional<Result> TreeEvalMaybe(UpFn upfn) const
719    {
720        struct DummyState {};
721        return TreeEvalMaybe<Result>(DummyState{},
722            [](DummyState, const Node&, size_t) { return DummyState{}; },
723            [&upfn](DummyState, const Node& node, std::span<Result> subs) {
724                return upfn(node, subs);
725            }
726        );
727    }
728
729    /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
730    template<typename Result, typename State, typename DownFn, typename UpFn>
731    Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
732    {
733        // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
734        // unconditionally dereference the result (it cannot be std::nullopt).
735        return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
736            std::forward<DownFn>(downfn),
737            [&upfn](State&& state, const Node& node, std::span<Result> subs) {
738                Result res{upfn(std::move(state), node, subs)};
739                return std::optional<Result>(std::move(res));
740            }
741        ));
742    }
743
744    /** Like TreeEval, but without downfn or State type.
745     *  upfn takes (const Node&, std::span<Result>) and returns Result. */
746    template<typename Result, typename UpFn>
747    Result TreeEval(UpFn upfn) const
748    {
749        struct DummyState {};
750        return std::move(*TreeEvalMaybe<Result>(DummyState{},