LCOV - code coverage report
Current view: top level - src/script - miniscript.h (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 7 1127 0.6 %
Date: 2023-10-05 12:38:51 Functions: 4 319 1.3 %
Branches: 0 3957 0.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2019-2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #ifndef BITCOIN_SCRIPT_MINISCRIPT_H
       6                 :            : #define BITCOIN_SCRIPT_MINISCRIPT_H
       7                 :            : 
       8                 :            : #include <algorithm>
       9                 :            : #include <functional>
      10                 :            : #include <numeric>
      11                 :            : #include <memory>
      12                 :            : #include <optional>
      13                 :            : #include <string>
      14                 :            : #include <vector>
      15                 :            : 
      16                 :            : #include <assert.h>
      17                 :            : #include <cstdlib>
      18                 :            : 
      19                 :            : #include <policy/policy.h>
      20                 :            : #include <primitives/transaction.h>
      21                 :            : #include <script/script.h>
      22                 :            : #include <span.h>
      23                 :            : #include <util/spanparsing.h>
      24                 :            : #include <util/strencodings.h>
      25                 :            : #include <util/string.h>
      26                 :            : #include <util/vector.h>
      27                 :            : 
      28                 :            : namespace miniscript {
      29                 :            : 
      30                 :            : /** This type encapsulates the miniscript type system properties.
      31                 :            :  *
      32                 :            :  * Every miniscript expression is one of 4 basic types, and additionally has
      33                 :            :  * a number of boolean type properties.
      34                 :            :  *
      35                 :            :  * The basic types are:
      36                 :            :  * - "B" Base:
      37                 :            :  *   - Takes its inputs from the top of the stack.
      38                 :            :  *   - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack.
      39                 :            :  *   - When dissatisfied, pushes a 0 onto the stack.
      40                 :            :  *   - This is used for most expressions, and required for the top level one.
      41                 :            :  *   - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY.
      42                 :            :  * - "V" Verify:
      43                 :            :  *   - Takes its inputs from the top of the stack.
      44                 :            :  *   - When satisfied, pushes nothing.
      45                 :            :  *   - Cannot be dissatisfied.
      46                 :            :  *   - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
      47                 :            :  *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
      48                 :            :  *     and OP_EQUAL), or by combining a V fragment under some conditions.
      49                 :            :  *   - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
      50                 :            :  * - "K" Key:
      51                 :            :  *   - Takes its inputs from the top of the stack.
      52                 :            :  *   - Becomes a B when followed by OP_CHECKSIG.
      53                 :            :  *   - Always pushes a public key onto the stack, for which a signature is to be
      54                 :            :  *     provided to satisfy the expression.
      55                 :            :  *   - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY
      56                 :            :  * - "W" Wrapped:
      57                 :            :  *   - Takes its input from one below the top of the stack.
      58                 :            :  *   - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below.
      59                 :            :  *   - When dissatisfied, pushes 0 op top of the stack or one below.
      60                 :            :  *   - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK".
      61                 :            :  *   - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG
      62                 :            :  *
      63                 :            :  * There a type properties that help reasoning about correctness:
      64                 :            :  * - "z" Zero-arg:
      65                 :            :  *   - Is known to always consume exactly 0 stack elements.
      66                 :            :  *   - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY
      67                 :            :  * - "o" One-arg:
      68                 :            :  *   - Is known to always consume exactly 1 stack element.
      69                 :            :  *   - Conflicts with property 'z'
      70                 :            :  *   - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL
      71                 :            :  * - "n" Nonzero:
      72                 :            :  *   - For every way this expression can be satisfied, a satisfaction exists that never needs
      73                 :            :  *     a zero top stack element.
      74                 :            :  *   - Conflicts with property 'z' and with type 'W'.
      75                 :            :  * - "d" Dissatisfiable:
      76                 :            :  *   - There is an easy way to construct a dissatisfaction for this expression.
      77                 :            :  *   - Conflicts with type 'V'.
      78                 :            :  * - "u" Unit:
      79                 :            :  *   - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero).
      80                 :            :  *   - Conflicts with type 'V'.
      81                 :            :  *
      82                 :            :  * Additional type properties help reasoning about nonmalleability:
      83                 :            :  * - "e" Expression:
      84                 :            :  *   - This implies property 'd', but the dissatisfaction is nonmalleable.
      85                 :            :  *   - This generally requires 'e' for all subexpressions which are invoked for that
      86                 :            :  *     dissatifsaction, and property 'f' for the unexecuted subexpressions in that case.
      87                 :            :  *   - Conflicts with type 'V'.
      88                 :            :  * - "f" Forced:
      89                 :            :  *   - Dissatisfactions (if any) for this expression always involve at least one signature.
      90                 :            :  *   - Is always true for type 'V'.
      91                 :            :  * - "s" Safe:
      92                 :            :  *   - Satisfactions for this expression always involve at least one signature.
      93                 :            :  * - "m" Nonmalleable:
      94                 :            :  *   - For every way this expression can be satisfied (which may be none),
      95                 :            :  *     a nonmalleable satisfaction exists.
      96                 :            :  *   - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions
      97                 :            :  *     which are dissatisfied when satisfying the parent.
      98                 :            :  *
      99                 :            :  * One type property is an implementation detail:
     100                 :            :  * - "x" Expensive verify:
     101                 :            :  *   - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG.
     102                 :            :  *   - Not having this property means that it can be converted to a V at no cost (by switching to the
     103                 :            :  *     -VERIFY version of the last opcode).
     104                 :            :  *
     105                 :            :  * Five more type properties for representing timelock information. Spend paths
     106                 :            :  * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together.
     107                 :            :  * This helps users detect if miniscript does not match the semantic behaviour the
     108                 :            :  * user expects.
     109                 :            :  * - "g" Whether the branch contains a relative time timelock
     110                 :            :  * - "h" Whether the branch contains a relative height timelock
     111                 :            :  * - "i" Whether the branch contains an absolute time timelock
     112                 :            :  * - "j" Whether the branch contains an absolute height timelock
     113                 :            :  * - "k"
     114                 :            :  *   - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock
     115                 :            :  *     of the same type.
     116                 :            :  *   - If the miniscript does not have the "k" property, the miniscript template will not match
     117                 :            :  *     the user expectation of the corresponding spending policy.
     118                 :            :  * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also
     119                 :            :  * valid in places where an X, a Y, a Z, an XY, ... is expected.
     120                 :            : */
     121                 :            : class Type {
     122                 :            :     //! Internal bitmap of properties (see ""_mst operator for details).
     123                 :            :     uint32_t m_flags;
     124                 :            : 
     125                 :            :     //! Internal constructor used by the ""_mst operator.
     126                 :          0 :     explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
     127                 :            : 
     128                 :            : public:
     129                 :            :     //! The only way to publicly construct a Type is using this literal operator.
     130                 :            :     friend constexpr Type operator"" _mst(const char* c, size_t l);
     131                 :            : 
     132                 :            :     //! Compute the type with the union of properties.
     133                 :          0 :     constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
     134                 :            : 
     135                 :            :     //! Compute the type with the intersection of properties.
     136                 :          0 :     constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
     137                 :            : 
     138                 :            :     //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
     139                 :          0 :     constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
     140                 :            : 
     141                 :            :     //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
     142                 :          0 :     constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
     143                 :            : 
     144                 :            :     //! Equality operator.
     145                 :          0 :     constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
     146                 :            : 
     147                 :            :     //! The empty type if x is false, itself otherwise.
     148         [ #  # ]:          0 :     constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
     149                 :            : };
     150                 :            : 
     151                 :            : //! Literal operator to construct Type objects.
     152                 :          0 : inline constexpr Type operator"" _mst(const char* c, size_t l) {
     153                 :          0 :     Type typ{0};
     154                 :            : 
     155         [ #  # ]:          0 :     for (const char *p = c; p < c + l; p++) {
     156                 :          0 :         typ = typ | Type(
     157         [ #  # ]:          0 :             *p == 'B' ? 1 << 0 : // Base type
     158         [ #  # ]:          0 :             *p == 'V' ? 1 << 1 : // Verify type
     159         [ #  # ]:          0 :             *p == 'K' ? 1 << 2 : // Key type
     160         [ #  # ]:          0 :             *p == 'W' ? 1 << 3 : // Wrapped type
     161         [ #  # ]:          0 :             *p == 'z' ? 1 << 4 : // Zero-arg property
     162         [ #  # ]:          0 :             *p == 'o' ? 1 << 5 : // One-arg property
     163         [ #  # ]:          0 :             *p == 'n' ? 1 << 6 : // Nonzero arg property
     164         [ #  # ]:          0 :             *p == 'd' ? 1 << 7 : // Dissatisfiable property
     165         [ #  # ]:          0 :             *p == 'u' ? 1 << 8 : // Unit property
     166         [ #  # ]:          0 :             *p == 'e' ? 1 << 9 : // Expression property
     167         [ #  # ]:          0 :             *p == 'f' ? 1 << 10 : // Forced property
     168         [ #  # ]:          0 :             *p == 's' ? 1 << 11 : // Safe property
     169         [ #  # ]:          0 :             *p == 'm' ? 1 << 12 : // Nonmalleable property
     170         [ #  # ]:          0 :             *p == 'x' ? 1 << 13 : // Expensive verify
     171         [ #  # ]:          0 :             *p == 'g' ? 1 << 14 : // older: contains relative time timelock   (csv_time)
     172         [ #  # ]:          0 :             *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
     173         [ #  # ]:          0 :             *p == 'i' ? 1 << 16 : // after: contains time timelock   (cltv_time)
     174         [ #  # ]:          0 :             *p == 'j' ? 1 << 17 : // after: contains height timelock   (cltv_height)
     175         [ #  # ]:          0 :             *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
     176   [ #  #  #  # ]:          0 :             (throw std::logic_error("Unknown character in _mst literal"), 0)
     177                 :            :         );
     178                 :          0 :     }
     179                 :            : 
     180                 :          0 :     return typ;
     181                 :          0 : }
     182                 :            : 
     183                 :            : using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
     184                 :            : 
     185                 :            : template<typename Key> struct Node;
     186                 :            : template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
     187                 :            : 
     188                 :            : //! Construct a miniscript node as a shared_ptr.
     189                 :            : template<typename Key, typename... Args>
     190                 :          0 : NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
     191                 :            : 
     192                 :            : //! The different node types in miniscript.
     193                 :            : enum class Fragment {
     194                 :            :     JUST_0,    //!< OP_0
     195                 :            :     JUST_1,    //!< OP_1
     196                 :            :     PK_K,      //!< [key]
     197                 :            :     PK_H,      //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY
     198                 :            :     OLDER,     //!< [n] OP_CHECKSEQUENCEVERIFY
     199                 :            :     AFTER,     //!< [n] OP_CHECKLOCKTIMEVERIFY
     200                 :            :     SHA256,    //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL
     201                 :            :     HASH256,   //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL
     202                 :            :     RIPEMD160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL
     203                 :            :     HASH160,   //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL
     204                 :            :     WRAP_A,    //!< OP_TOALTSTACK [X] OP_FROMALTSTACK
     205                 :            :     WRAP_S,    //!< OP_SWAP [X]
     206                 :            :     WRAP_C,    //!< [X] OP_CHECKSIG
     207                 :            :     WRAP_D,    //!< OP_DUP OP_IF [X] OP_ENDIF
     208                 :            :     WRAP_V,    //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X)
     209                 :            :     WRAP_J,    //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF
     210                 :            :     WRAP_N,    //!< [X] OP_0NOTEQUAL
     211                 :            :     AND_V,     //!< [X] [Y]
     212                 :            :     AND_B,     //!< [X] [Y] OP_BOOLAND
     213                 :            :     OR_B,      //!< [X] [Y] OP_BOOLOR
     214                 :            :     OR_C,      //!< [X] OP_NOTIF [Y] OP_ENDIF
     215                 :            :     OR_D,      //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
     216                 :            :     OR_I,      //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
     217                 :            :     ANDOR,     //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
     218                 :            :     THRESH,    //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
     219                 :            :     MULTI,     //!< [k] [key_n]* [n] OP_CHECKMULTISIG
     220                 :            :     // AND_N(X,Y) is represented as ANDOR(X,Y,0)
     221                 :            :     // WRAP_T(X) is represented as AND_V(X,1)
     222                 :            :     // WRAP_L(X) is represented as OR_I(0,X)
     223                 :            :     // WRAP_U(X) is represented as OR_I(X,0)
     224                 :            : };
     225                 :            : 
     226                 :            : enum class Availability {
     227                 :            :     NO,
     228                 :            :     YES,
     229                 :            :     MAYBE,
     230                 :            : };
     231                 :            : 
     232                 :            : namespace internal {
     233                 :            : 
     234                 :            : //! Helper function for Node::CalcType.
     235                 :            : Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys);
     236                 :            : 
     237                 :            : //! Helper function for Node::CalcScriptLen.
     238                 :            : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
     239                 :            : 
     240                 :            : //! A helper sanitizer/checker for the output of CalcType.
     241                 :            : Type SanitizeType(Type x);
     242                 :            : 
     243                 :            : //! An object representing a sequence of witness stack elements.
     244                 :            : struct InputStack {
     245                 :            :     /** Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node).
     246                 :            :      *  The MAYBE value is used for size estimation, when keys/preimages may actually be unavailable,
     247                 :            :      *  but may be available at signing time. This makes the InputStack structure and signing logic,
     248                 :            :      *  filled with dummy signatures/preimages usable for witness size estimation.
     249                 :            :      */
     250                 :         40 :     Availability available = Availability::YES;
     251                 :            :     //! Whether this stack contains a digital signature.
     252                 :         40 :     bool has_sig = false;
     253                 :            :     //! Whether this stack is malleable (can be turned into an equally valid other stack by a third party).
     254                 :         40 :     bool malleable = false;
     255                 :            :     //! Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction).
     256                 :            :     //! Note that this flag does not affect the satisfaction algorithm; it is only used for sanity checking.
     257                 :         40 :     bool non_canon = false;
     258                 :            :     //! Serialized witness size.
     259                 :         16 :     size_t size = 0;
     260                 :            :     //! Data elements.
     261                 :            :     std::vector<std::vector<unsigned char>> stack;
     262                 :            :     //! Construct an empty stack (valid).
     263                 :         32 :     InputStack() {}
     264                 :            :     //! Construct a valid single-element stack (with an element up to 75 bytes).
     265                 :         48 :     InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {}
     266                 :            :     //! Change availability
     267                 :            :     InputStack& SetAvailable(Availability avail);
     268                 :            :     //! Mark this input stack as having a signature.
     269                 :            :     InputStack& SetWithSig();
     270                 :            :     //! Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions).
     271                 :            :     InputStack& SetNonCanon();
     272                 :            :     //! Mark this input stack as malleable.
     273                 :            :     InputStack& SetMalleable(bool x = true);
     274                 :            :     //! Concatenate two input stacks.
     275                 :            :     friend InputStack operator+(InputStack a, InputStack b);
     276                 :            :     //! Choose between two potential input stacks.
     277                 :            :     friend InputStack operator|(InputStack a, InputStack b);
     278                 :            : };
     279                 :            : 
     280                 :            : /** A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in numeric context). */
     281                 :            : static const auto ZERO = InputStack(std::vector<unsigned char>());
     282                 :            : /** A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challenges). */
     283                 :            : static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable();
     284                 :            : /** A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric context). */
     285                 :            : static const auto ONE = InputStack(Vector((unsigned char)1));
     286                 :            : /** The empty stack. */
     287                 :            : static const auto EMPTY = InputStack();
     288                 :            : /** A stack representing the lack of any (dis)satisfactions. */
     289                 :            : static const auto INVALID = InputStack().SetAvailable(Availability::NO);
     290                 :            : 
     291                 :            : //! A pair of a satisfaction and a dissatisfaction InputStack.
     292                 :            : struct InputResult {
     293                 :            :     InputStack nsat, sat;
     294                 :            : 
     295                 :            :     template<typename A, typename B>
     296   [ #  #  #  #  :          0 :     InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {}
                   #  # ]
     297                 :            : };
     298                 :            : 
     299                 :            : //! Class whose objects represent the maximum of a list of integers.
     300                 :            : template<typename I>
     301                 :            : struct MaxInt {
     302                 :            :     const bool valid;
     303                 :            :     const I value;
     304                 :            : 
     305                 :          0 :     MaxInt() : valid(false), value(0) {}
     306                 :          0 :     MaxInt(I val) : valid(true), value(val) {}
     307                 :            : 
     308                 :          0 :     friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
     309   [ #  #  #  # ]:          0 :         if (!a.valid || !b.valid) return {};
     310                 :          0 :         return a.value + b.value;
     311                 :          0 :     }
     312                 :            : 
     313                 :          0 :     friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
     314         [ #  # ]:          0 :         if (!a.valid) return b;
     315         [ #  # ]:          0 :         if (!b.valid) return a;
     316                 :          0 :         return std::max(a.value, b.value);
     317                 :          0 :     }
     318                 :            : };
     319                 :            : 
     320                 :            : struct Ops {
     321                 :            :     //! Non-push opcodes.
     322                 :            :     uint32_t count;
     323                 :            :     //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
     324                 :            :     MaxInt<uint32_t> sat;
     325                 :            :     //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
     326                 :            :     MaxInt<uint32_t> dsat;
     327                 :            : 
     328                 :          0 :     Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
     329                 :            : };
     330                 :            : 
     331                 :            : struct StackSize {
     332                 :            :     //! Maximum stack size to satisfy;
     333                 :            :     MaxInt<uint32_t> sat;
     334                 :            :     //! Maximum stack size to dissatisfy;
     335                 :            :     MaxInt<uint32_t> dsat;
     336                 :            : 
     337                 :          0 :     StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
     338                 :            : };
     339                 :            : 
     340                 :            : struct WitnessSize {
     341                 :            :     //! Maximum witness size to satisfy;
     342                 :            :     MaxInt<uint32_t> sat;
     343                 :            :     //! Maximum witness size to dissatisfy;
     344                 :            :     MaxInt<uint32_t> dsat;
     345                 :            : 
     346                 :          0 :     WitnessSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
     347                 :            : };
     348                 :            : 
     349                 :            : struct NoDupCheck {};
     350                 :            : 
     351                 :            : } // namespace internal
     352                 :            : 
     353                 :            : //! A node in a miniscript expression.
     354                 :            : template<typename Key>
     355                 :            : struct Node {
     356                 :            :     //! What node type this node is.
     357                 :            :     const Fragment fragment;
     358                 :            :     //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
     359                 :            :     const uint32_t k = 0;
     360                 :            :     //! The keys used by this expression (only for PK_K/PK_H/MULTI)
     361                 :            :     const std::vector<Key> keys;
     362                 :            :     //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
     363                 :            :     const std::vector<unsigned char> data;
     364                 :            :     //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
     365                 :            :     const std::vector<NodeRef<Key>> subs;
     366                 :            : 
     367                 :            : private:
     368                 :            :     //! Cached ops counts.
     369                 :            :     const internal::Ops ops;
     370                 :            :     //! Cached stack size bounds.
     371                 :            :     const internal::StackSize ss;
     372                 :            :     //! Cached witness size bounds.
     373                 :            :     const internal::WitnessSize ws;
     374                 :            :     //! Cached expression type (computed by CalcType and fed through SanitizeType).
     375                 :            :     const Type typ;
     376                 :            :     //! Cached script length (computed by CalcScriptLen).
     377                 :            :     const size_t scriptlen;
     378                 :            :     //! Whether a public key appears more than once in this node. This value is initialized
     379                 :            :     //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the
     380                 :            :     //! computation, requiring it to be done manually by invoking DuplicateKeyCheck().
     381                 :            :     //! DuplicateKeyCheck(), or a non-NoDupCheck constructor, will compute has_duplicate_keys
     382                 :            :     //! for all subnodes as well.
     383                 :            :     mutable std::optional<bool> has_duplicate_keys;
     384                 :            : 
     385                 :            : 
     386                 :            :     //! Compute the length of the script for this miniscript (including children).
     387                 :          0 :     size_t CalcScriptLen() const {
     388                 :          0 :         size_t subsize = 0;
     389   [ #  #  #  # ]:          0 :         for (const auto& sub : subs) {
     390                 :          0 :             subsize += sub->ScriptSize();
     391                 :            :         }
     392   [ #  #  #  # ]:          0 :         Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
     393                 :          0 :         return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
     394                 :            :     }
     395                 :            : 
     396                 :            :     /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
     397                 :            :      *
     398                 :            :      * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
     399                 :            :      * result can be thought of as first using downfn to compute a "state" for each node,
     400                 :            :      * from the root down to the leaves. Then upfn is used to compute a "result" for each
     401                 :            :      * node, from the leaves back up to the root, which is then returned. In the actual
     402                 :            :      * implementation, both functions are invoked in an interleaved fashion, performing a
     403                 :            :      * depth-first traversal of the tree.
     404                 :            :      *
     405                 :            :      * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
     406                 :            :      * - root is the state of the root node, of type State.
     407                 :            :      * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
     408                 :            :      *   node, its state, and an index of one of its children, computes the state of that
     409                 :            :      *   child. It can modify the state. Children of a given node will have downfn()
     410                 :            :      *   called in order.
     411                 :            :      * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
     412                 :            :      *   which given a node, its state, and a Span of the results of its children,
     413                 :            :      *   computes the result of the node. If std::nullopt is returned by upfn,
     414                 :            :      *   TreeEvalMaybe() immediately returns std::nullopt.
     415                 :            :      * The return value of TreeEvalMaybe is the result of the root node.
     416                 :            :      *
     417                 :            :      * Result type cannot be bool due to the std::vector<bool> specialization.
     418                 :            :      */
     419                 :            :     template<typename Result, typename State, typename DownFn, typename UpFn>
     420                 :          0 :     std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
     421                 :            :     {
     422                 :            :         /** Entries of the explicit stack tracked in this algorithm. */
     423                 :            :         struct StackElem
     424                 :            :         {
     425                 :            :             const Node& node; //!< The node being evaluated.
     426                 :            :             size_t expanded; //!< How many children of this node have been expanded.
     427                 :            :             State state; //!< The state for that node.
     428                 :            : 
     429                 :          0 :             StackElem(const Node& node_, size_t exp_, State&& state_) :
     430                 :          0 :                 node(node_), expanded(exp_), state(std::move(state_)) {}
     431                 :            :         };
     432                 :            :         /* Stack of tree nodes being explored. */
     433                 :          0 :         std::vector<StackElem> stack;
     434                 :            :         /* Results of subtrees so far. Their order and mapping to tree nodes
     435                 :            :          * is implicitly defined by stack. */
     436                 :          0 :         std::vector<Result> results;
     437   [ #  #  #  #  :          0 :         stack.emplace_back(*this, 0, std::move(root_state));
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     438                 :            : 
     439                 :            :         /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
     440                 :            :          * State variables are omitted for simplicity.
     441                 :            :          *
     442                 :            :          * First: stack=[(A,0)] results=[]
     443                 :            :          *        stack=[(A,1),(B,0)] results=[]
     444                 :            :          *        stack=[(A,1)] results=[B]
     445                 :            :          *        stack=[(A,2),(C,0)] results=[B]
     446                 :            :          *        stack=[(A,2),(C,1),(D,0)] results=[B]
     447                 :            :          *        stack=[(A,2),(C,1)] results=[B,D]
     448                 :            :          *        stack=[(A,2),(C,2),(E,0)] results=[B,D]
     449                 :            :          *        stack=[(A,2),(C,2)] results=[B,D,E]
     450                 :            :          *        stack=[(A,2)] results=[B,C]
     451                 :            :          *        stack=[(A,3),(F,0)] results=[B,C]
     452                 :            :          *        stack=[(A,3)] results=[B,C,F]
     453                 :            :          * Final: stack=[] results=[A]
     454                 :            :          */
     455   [ #  #  #  #  :          0 :         while (stack.size()) {
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     456                 :          0 :             const Node& node = stack.back().node;
     457   [ #  #  #  #  :          0 :             if (stack.back().expanded < node.subs.size()) {
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     458                 :            :                 /* We encounter a tree node with at least one unexpanded child.
     459                 :            :                  * Expand it. By the time we hit this node again, the result of
     460                 :            :                  * that child (and all earlier children) will be at the end of `results`. */
     461                 :          0 :                 size_t child_index = stack.back().expanded++;
     462   [ #  #  #  #  :          0 :                 State child_state = downfn(stack.back().state, node, child_index);
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     463   [ #  #  #  #  :          0 :                 stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     464                 :          0 :                 continue;
     465                 :            :             }
     466                 :            :             // Invoke upfn with the last node.subs.size() elements of results as input.
     467   [ #  #  #  #  :          0 :             assert(results.size() >= node.subs.size());
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     468   [ #  #  #  #  :          0 :             std::optional<Result> result{upfn(std::move(stack.back().state), node,
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     469   [ #  #  #  #  :          0 :                 Span<Result>{results}.last(node.subs.size()))};
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     470                 :            :             // If evaluation returns std::nullopt, abort immediately.
     471   [ #  #  #  #  :          0 :             if (!result) return {};
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     472                 :            :             // Replace the last node.subs.size() elements of results with the new result.
     473   [ #  #  #  #  :          0 :             results.erase(results.end() - node.subs.size(), results.end());
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     474   [ #  #  #  #  :          0 :             results.push_back(std::move(*result));
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     475                 :          0 :             stack.pop_back();
     476   [ #  #  #  #  :          0 :         }
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     477                 :            :         // The final remaining results element is the root result, return it.
     478   [ #  #  #  #  :          0 :         assert(results.size() == 1);
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     479   [ #  #  #  #  :          0 :         return std::move(results[0]);
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     480                 :          0 :     }
     481                 :            : 
     482                 :            :     /** Like TreeEvalMaybe, but without downfn or State type.
     483                 :            :      * upfn takes (const Node&, Span<Result>) and returns std::optional<Result>. */
     484                 :            :     template<typename Result, typename UpFn>
     485                 :            :     std::optional<Result> TreeEvalMaybe(UpFn upfn) const
     486                 :            :     {
     487                 :            :         struct DummyState {};
     488                 :            :         return TreeEvalMaybe<Result>(DummyState{},
     489                 :            :             [](DummyState, const Node&, size_t) { return DummyState{}; },
     490                 :            :             [&upfn](DummyState, const Node& node, Span<Result> subs) {
     491                 :            :                 return upfn(node, subs);
     492                 :            :             }
     493                 :            :         );
     494                 :            :     }
     495                 :            : 
     496                 :            :     /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
     497                 :            :     template<typename Result, typename State, typename DownFn, typename UpFn>
     498                 :          0 :     Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
     499                 :            :     {
     500                 :            :         // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
     501                 :            :         // unconditionally dereference the result (it cannot be std::nullopt).
     502   [ #  #  #  # ]:          0 :         return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
     503                 :          0 :             std::forward<DownFn>(downfn),
     504                 :          0 :             [&upfn](State&& state, const Node& node, Span<Result> subs) {
     505                 :          0 :                 Result res{upfn(std::move(state), node, subs)};
     506   [ #  #  #  # ]:          0 :                 return std::optional<Result>(std::move(res));
     507                 :          0 :             }
     508                 :            :         ));
     509                 :          0 :     }
     510                 :            : 
     511                 :            :     /** Like TreeEval, but without downfn or State type.
     512                 :            :      *  upfn takes (const Node&, Span<Result>) and returns Result. */
     513                 :            :     template<typename Result, typename UpFn>
     514                 :          0 :     Result TreeEval(UpFn upfn) const
     515                 :            :     {
     516                 :            :         struct DummyState {};
     517   [ #  #  #  #  :          0 :         return std::move(*TreeEvalMaybe<Result>(DummyState{},
             #  #  #  # ]
     518                 :          0 :             [](DummyState, const Node&, size_t) { return DummyState{}; },
     519                 :          0 :             [&upfn](DummyState, const Node& node, Span<Result> subs) {
     520                 :          0 :                 Result res{upfn(node, subs)};
     521   [ #  #  #  #  :          0 :                 return std::optional<Result>(std::move(res));
             #  #  #  # ]
     522                 :          0 :             }
     523                 :            :         ));
     524                 :          0 :     }
     525                 :            : 
     526                 :            :     /** Compare two miniscript subtrees, using a non-recursive algorithm. */
     527                 :          0 :     friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
     528                 :            :     {
     529                 :          0 :         std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
     530         [ #  # ]:          0 :         queue.emplace_back(node1, node2);
     531         [ #  # ]:          0 :         while (!queue.empty()) {
     532                 :          0 :             const auto& [a, b] = queue.back();
     533                 :          0 :             queue.pop_back();
     534   [ #  #  #  #  :          0 :             if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     535   [ #  #  #  #  :          0 :             if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     536   [ #  #  #  # ]:          0 :             if (a.subs.size() < b.subs.size()) return -1;
     537   [ #  #  #  # ]:          0 :             if (b.subs.size() < a.subs.size()) return 1;
     538                 :          0 :             size_t n = a.subs.size();
     539         [ #  # ]:          0 :             for (size_t i = 0; i < n; ++i) {
     540   [ #  #  #  # ]:          0 :                 queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
     541                 :          0 :             }
     542                 :            :         }
     543                 :          0 :         return 0;
     544                 :          0 :     }
     545                 :            : 
     546                 :            :     //! Compute the type for this miniscript.
     547                 :          0 :     Type CalcType() const {
     548                 :            :         using namespace internal;
     549                 :            : 
     550                 :            :         // THRESH has a variable number of subexpressions
     551                 :          0 :         std::vector<Type> sub_types;
     552   [ #  #  #  # ]:          0 :         if (fragment == Fragment::THRESH) {
     553   [ #  #  #  #  :          0 :             for (const auto& sub : subs) sub_types.push_back(sub->GetType());
             #  #  #  # ]
     554                 :          0 :         }
     555                 :            :         // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
     556   [ #  #  #  #  :          0 :         Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
             #  #  #  # ]
     557   [ #  #  #  #  :          0 :         Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
             #  #  #  # ]
     558   [ #  #  #  #  :          0 :         Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
             #  #  #  # ]
     559                 :            : 
     560   [ #  #  #  #  :          0 :         return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
             #  #  #  # ]
     561                 :          0 :     }
     562                 :            : 
     563                 :            : public:
     564                 :            :     template<typename Ctx>
     565                 :          0 :     CScript ToScript(const Ctx& ctx) const
     566                 :            :     {
     567                 :            :         // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
     568                 :            :         // The State is a boolean: whether or not the node's script expansion is followed
     569                 :            :         // by an OP_VERIFY (which may need to be combined with the last script opcode).
     570                 :          0 :         auto downfn = [](bool verify, const Node& node, size_t index) {
     571                 :            :             // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
     572   [ #  #  #  # ]:          0 :             if (node.fragment == Fragment::WRAP_V) return true;
     573                 :            :             // The subexpression of WRAP_S, and the last subexpression of AND_V
     574                 :            :             // inherit the followed-by-OP_VERIFY property from the parent.
     575   [ #  #  #  #  :          0 :             if (node.fragment == Fragment::WRAP_S ||
             #  #  #  # ]
     576   [ #  #  #  # ]:          0 :                 (node.fragment == Fragment::AND_V && index == 1)) return verify;
     577                 :          0 :             return false;
     578                 :          0 :         };
     579                 :            :         // The upward function computes for a node, given its followed-by-OP_VERIFY status
     580                 :            :         // and the CScripts of its child nodes, the CScript of the node.
     581                 :          0 :         auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
     582   [ #  #  #  #  :          0 :             switch (node.fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     583         [ #  # ]:          0 :                 case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
     584   [ #  #  #  # ]:          0 :                 case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
     585                 :          0 :                 case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
     586                 :          0 :                 case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
     587                 :          0 :                 case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
     588                 :          0 :                 case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
     589                 :          0 :                 case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
     590                 :          0 :                 case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
     591                 :          0 :                 case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
     592                 :          0 :                 case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
     593                 :          0 :                 case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
     594                 :          0 :                 case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
     595                 :            :                 case Fragment::WRAP_V: {
     596   [ #  #  #  # ]:          0 :                     if (node.subs[0]->GetType() << "x"_mst) {
     597                 :          0 :                         return BuildScript(std::move(subs[0]), OP_VERIFY);
     598                 :            :                     } else {
     599                 :          0 :                         return std::move(subs[0]);
     600                 :            :                     }
     601                 :            :                 }
     602                 :          0 :                 case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
     603                 :          0 :                 case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
     604                 :          0 :                 case Fragment::JUST_1: return BuildScript(OP_1);
     605                 :          0 :                 case Fragment::JUST_0: return BuildScript(OP_0);
     606                 :          0 :                 case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
     607                 :          0 :                 case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
     608                 :          0 :                 case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
     609                 :          0 :                 case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
     610                 :          0 :                 case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
     611                 :          0 :                 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
     612                 :          0 :                 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
     613                 :            :                 case Fragment::MULTI: {
     614                 :          0 :                     CScript script = BuildScript(node.k);
     615   [ #  #  #  # ]:          0 :                     for (const auto& key : node.keys) {
     616   [ #  #  #  #  :          0 :                         script = BuildScript(std::move(script), ctx.ToPKBytes(key));
             #  #  #  # ]
     617                 :            :                     }
     618   [ #  #  #  # ]:          0 :                     return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
     619                 :          0 :                 }
     620                 :            :                 case Fragment::THRESH: {
     621                 :          0 :                     CScript script = std::move(subs[0]);
     622   [ #  #  #  # ]:          0 :                     for (size_t i = 1; i < subs.size(); ++i) {
     623   [ #  #  #  # ]:          0 :                         script = BuildScript(std::move(script), subs[i], OP_ADD);
     624                 :          0 :                     }
     625   [ #  #  #  # ]:          0 :                     return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
     626                 :          0 :                 }
     627                 :            :             }
     628                 :          0 :             assert(false);
     629                 :          0 :         };
     630                 :          0 :         return TreeEval<CScript>(false, downfn, upfn);
     631                 :            :     }
     632                 :            : 
     633                 :            :     template<typename CTx>
     634                 :          0 :     std::optional<std::string> ToString(const CTx& ctx) const {
     635                 :            :         // To construct the std::string representation for a Miniscript object, we use
     636                 :            :         // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
     637                 :            :         // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
     638                 :          0 :         auto downfn = [](bool, const Node& node, size_t) {
     639   [ #  #  #  #  :          0 :             return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
             #  #  #  # ]
     640   [ #  #  #  #  :          0 :                     node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
             #  #  #  # ]
     641   [ #  #  #  #  :          0 :                     node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
             #  #  #  # ]
     642   [ #  #  #  # ]:          0 :                     node.fragment == Fragment::WRAP_C ||
     643   [ #  #  #  #  :          0 :                     (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
             #  #  #  # ]
     644   [ #  #  #  # ]:          0 :                     (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
     645   [ #  #  #  # ]:          0 :                     (node.fragment == Fragment::OR_I && node.subs[1]->fragment == Fragment::JUST_0));
     646                 :            :         };
     647                 :            :         // The upward function computes for a node, given whether its parent is a wrapper,
     648                 :            :         // and the string representations of its child nodes, the string representation of the node.
     649                 :          0 :         auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
     650   [ #  #  #  # ]:          0 :             std::string ret = wrapped ? ":" : "";
     651                 :            : 
     652   [ #  #  #  #  :          0 :             switch (node.fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     653   [ #  #  #  #  :          0 :                 case Fragment::WRAP_A: return "a" + std::move(subs[0]);
             #  #  #  # ]
     654   [ #  #  #  #  :          0 :                 case Fragment::WRAP_S: return "s" + std::move(subs[0]);
             #  #  #  # ]
     655                 :            :                 case Fragment::WRAP_C:
     656   [ #  #  #  # ]:          0 :                     if (node.subs[0]->fragment == Fragment::PK_K) {
     657                 :            :                         // pk(K) is syntactic sugar for c:pk_k(K)
     658   [ #  #  #  # ]:          0 :                         auto key_str = ctx.ToString(node.subs[0]->keys[0]);
     659   [ #  #  #  # ]:          0 :                         if (!key_str) return {};
     660   [ #  #  #  #  :          0 :                         return std::move(ret) + "pk(" + std::move(*key_str) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     661                 :          0 :                     }
     662   [ #  #  #  # ]:          0 :                     if (node.subs[0]->fragment == Fragment::PK_H) {
     663                 :            :                         // pkh(K) is syntactic sugar for c:pk_h(K)
     664   [ #  #  #  # ]:          0 :                         auto key_str = ctx.ToString(node.subs[0]->keys[0]);
     665   [ #  #  #  # ]:          0 :                         if (!key_str) return {};
     666   [ #  #  #  #  :          0 :                         return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     667                 :          0 :                     }
     668   [ #  #  #  #  :          0 :                     return "c" + std::move(subs[0]);
             #  #  #  # ]
     669   [ #  #  #  #  :          0 :                 case Fragment::WRAP_D: return "d" + std::move(subs[0]);
             #  #  #  # ]
     670   [ #  #  #  #  :          0 :                 case Fragment::WRAP_V: return "v" + std::move(subs[0]);
             #  #  #  # ]
     671   [ #  #  #  #  :          0 :                 case Fragment::WRAP_J: return "j" + std::move(subs[0]);
             #  #  #  # ]
     672   [ #  #  #  #  :          0 :                 case Fragment::WRAP_N: return "n" + std::move(subs[0]);
             #  #  #  # ]
     673                 :            :                 case Fragment::AND_V:
     674                 :            :                     // t:X is syntactic sugar for and_v(X,1).
     675   [ #  #  #  #  :          0 :                     if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
          #  #  #  #  #  
                #  #  # ]
     676                 :          0 :                     break;
     677                 :            :                 case Fragment::OR_I:
     678   [ #  #  #  #  :          0 :                     if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
          #  #  #  #  #  
                #  #  # ]
     679   [ #  #  #  #  :          0 :                     if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
          #  #  #  #  #  
                #  #  # ]
     680                 :          0 :                     break;
     681                 :          0 :                 default: break;
     682                 :            :             }
     683   [ #  #  #  #  :          0 :             switch (node.fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     684                 :            :                 case Fragment::PK_K: {
     685   [ #  #  #  # ]:          0 :                     auto key_str = ctx.ToString(node.keys[0]);
     686   [ #  #  #  # ]:          0 :                     if (!key_str) return {};
     687   [ #  #  #  #  :          0 :                     return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     688                 :          0 :                 }
     689                 :            :                 case Fragment::PK_H: {
     690   [ #  #  #  # ]:          0 :                     auto key_str = ctx.ToString(node.keys[0]);
     691   [ #  #  #  # ]:          0 :                     if (!key_str) return {};
     692   [ #  #  #  #  :          0 :                     return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     693                 :          0 :                 }
     694   [ #  #  #  #  :          0 :                 case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     695   [ #  #  #  #  :          0 :                 case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     696   [ #  #  #  #  :          0 :                 case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     697   [ #  #  #  #  :          0 :                 case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     698   [ #  #  #  #  :          0 :                 case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     699   [ #  #  #  #  :          0 :                 case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     700   [ #  #  #  #  :          0 :                 case Fragment::JUST_1: return std::move(ret) + "1";
             #  #  #  # ]
     701   [ #  #  #  #  :          0 :                 case Fragment::JUST_0: return std::move(ret) + "0";
             #  #  #  # ]
     702   [ #  #  #  #  :          0 :                 case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     703   [ #  #  #  #  :          0 :                 case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     704   [ #  #  #  #  :          0 :                 case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     705   [ #  #  #  #  :          0 :                 case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     706   [ #  #  #  #  :          0 :                 case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     707   [ #  #  #  #  :          0 :                 case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     708                 :            :                 case Fragment::ANDOR:
     709                 :            :                     // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
     710   [ #  #  #  #  :          0 :                     if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     711   [ #  #  #  #  :          0 :                     return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                #  #  # ]
     712                 :            :                 case Fragment::MULTI: {
     713   [ #  #  #  #  :          0 :                     auto str = std::move(ret) + "multi(" + ::ToString(node.k);
          #  #  #  #  #  
                #  #  # ]
     714   [ #  #  #  # ]:          0 :                     for (const auto& key : node.keys) {
     715   [ #  #  #  # ]:          0 :                         auto key_str = ctx.ToString(key);
     716   [ #  #  #  # ]:          0 :                         if (!key_str) return {};
     717   [ #  #  #  #  :          0 :                         str += "," + std::move(*key_str);
          #  #  #  #  #  
                      # ]
     718   [ #  #  #  # ]:          0 :                     }
     719   [ #  #  #  #  :          0 :                     return std::move(str) + ")";
             #  #  #  # ]
     720                 :          0 :                 }
     721                 :            :                 case Fragment::THRESH: {
     722   [ #  #  #  #  :          0 :                     auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
          #  #  #  #  #  
                #  #  # ]
     723   [ #  #  #  # ]:          0 :                     for (auto& sub : subs) {
     724   [ #  #  #  #  :          0 :                         str += "," + std::move(sub);
             #  #  #  # ]
     725                 :            :                     }
     726   [ #  #  #  #  :          0 :                     return std::move(str) + ")";
             #  #  #  # ]
     727                 :          0 :                 }
     728                 :          0 :                 default: break;
     729                 :            :             }
     730                 :          0 :             assert(false);
     731                 :          0 :         };
     732                 :            : 
     733                 :          0 :         return TreeEvalMaybe<std::string>(false, downfn, upfn);
     734                 :            :     }
     735                 :            : 
     736                 :            : private:
     737                 :          0 :     internal::Ops CalcOps() const {
     738   [ #  #  #  #  :          0 :         switch (fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                #  #  # ]
     739                 :          0 :             case Fragment::JUST_1: return {0, 0, {}};
     740                 :          0 :             case Fragment::JUST_0: return {0, {}, 0};
     741                 :          0 :             case Fragment::PK_K: return {0, 0, 0};
     742                 :          0 :             case Fragment::PK_H: return {3, 0, 0};
     743                 :            :             case Fragment::OLDER:
     744                 :          0 :             case Fragment::AFTER: return {1, 0, {}};
     745                 :            :             case Fragment::SHA256:
     746                 :            :             case Fragment::RIPEMD160:
     747                 :            :             case Fragment::HASH256:
     748                 :          0 :             case Fragment::HASH160: return {4, 0, {}};
     749                 :          0 :             case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
     750                 :            :             case Fragment::AND_B: {
     751                 :          0 :                 const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
     752                 :          0 :                 const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
     753                 :          0 :                 const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
     754                 :          0 :                 return {count, sat, dsat};
     755                 :            :             }
     756                 :            :             case Fragment::OR_B: {
     757                 :          0 :                 const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
     758                 :          0 :                 const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
     759                 :          0 :                 const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
     760                 :          0 :                 return {count, sat, dsat};
     761                 :            :             }
     762                 :            :             case Fragment::OR_D: {
     763                 :          0 :                 const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
     764                 :          0 :                 const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
     765                 :          0 :                 const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
     766                 :          0 :                 return {count, sat, dsat};
     767                 :            :             }
     768                 :            :             case Fragment::OR_C: {
     769                 :          0 :                 const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
     770                 :          0 :                 const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
     771                 :          0 :                 return {count, sat, {}};
     772                 :            :             }
     773                 :            :             case Fragment::OR_I: {
     774                 :          0 :                 const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
     775                 :          0 :                 const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
     776                 :          0 :                 const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
     777                 :          0 :                 return {count, sat, dsat};
     778                 :            :             }
     779                 :            :             case Fragment::ANDOR: {
     780                 :          0 :                 const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
     781                 :          0 :                 const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
     782                 :          0 :                 const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
     783                 :          0 :                 return {count, sat, dsat};
     784                 :            :             }
     785                 :          0 :             case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
     786                 :            :             case Fragment::WRAP_S:
     787                 :            :             case Fragment::WRAP_C:
     788                 :          0 :             case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
     789                 :          0 :             case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
     790                 :          0 :             case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
     791                 :          0 :             case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
     792                 :          0 :             case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
     793                 :            :             case Fragment::THRESH: {
     794                 :          0 :                 uint32_t count = 0;
     795                 :          0 :                 auto sats = Vector(internal::MaxInt<uint32_t>(0));
     796   [ #  #  #  # ]:          0 :                 for (const auto& sub : subs) {
     797                 :          0 :                     count += sub->ops.count + 1;
     798   [ #  #  #  #  :          0 :                     auto next_sats = Vector(sats[0] + sub->ops.dsat);
             #  #  #  # ]
     799   [ #  #  #  #  :          0 :                     for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     800   [ #  #  #  #  :          0 :                     next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
             #  #  #  # ]
     801                 :          0 :                     sats = std::move(next_sats);
     802                 :          0 :                 }
     803   [ #  #  #  # ]:          0 :                 assert(k <= sats.size());
     804   [ #  #  #  # ]:          0 :                 return {count, sats[k], sats[0]};
     805                 :          0 :             }
     806                 :            :         }
     807                 :          0 :         assert(false);
     808                 :          0 :     }
     809                 :            : 
     810                 :          0 :     internal::StackSize CalcStackSize() const {
     811   [ #  #  #  #  :          0 :         switch (fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     812                 :          0 :             case Fragment::JUST_0: return {{}, 0};
     813                 :            :             case Fragment::JUST_1:
     814                 :            :             case Fragment::OLDER:
     815                 :          0 :             case Fragment::AFTER: return {0, {}};
     816                 :          0 :             case Fragment::PK_K: return {1, 1};
     817                 :          0 :             case Fragment::PK_H: return {2, 2};
     818                 :            :             case Fragment::SHA256:
     819                 :            :             case Fragment::RIPEMD160:
     820                 :            :             case Fragment::HASH256:
     821                 :          0 :             case Fragment::HASH160: return {1, {}};
     822                 :            :             case Fragment::ANDOR: {
     823                 :          0 :                 const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
     824                 :          0 :                 const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
     825                 :          0 :                 return {sat, dsat};
     826                 :            :             }
     827                 :          0 :             case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
     828                 :          0 :             case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
     829                 :            :             case Fragment::OR_B: {
     830                 :          0 :                 const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
     831                 :          0 :                 const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
     832                 :          0 :                 return {sat, dsat};
     833                 :            :             }
     834                 :          0 :             case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
     835                 :          0 :             case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
     836                 :          0 :             case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
     837                 :          0 :             case Fragment::MULTI: return {k + 1, k + 1};
     838                 :            :             case Fragment::WRAP_A:
     839                 :            :             case Fragment::WRAP_N:
     840                 :            :             case Fragment::WRAP_S:
     841                 :          0 :             case Fragment::WRAP_C: return subs[0]->ss;
     842                 :          0 :             case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
     843                 :          0 :             case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
     844                 :          0 :             case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
     845                 :            :             case Fragment::THRESH: {
     846                 :          0 :                 auto sats = Vector(internal::MaxInt<uint32_t>(0));
     847   [ #  #  #  # ]:          0 :                 for (const auto& sub : subs) {
     848   [ #  #  #  #  :          0 :                     auto next_sats = Vector(sats[0] + sub->ss.dsat);
             #  #  #  # ]
     849   [ #  #  #  #  :          0 :                     for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     850   [ #  #  #  #  :          0 :                     next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
             #  #  #  # ]
     851                 :          0 :                     sats = std::move(next_sats);
     852                 :          0 :                 }
     853   [ #  #  #  # ]:          0 :                 assert(k <= sats.size());
     854   [ #  #  #  # ]:          0 :                 return {sats[k], sats[0]};
     855                 :          0 :             }
     856                 :            :         }
     857                 :          0 :         assert(false);
     858                 :          0 :     }
     859                 :            : 
     860                 :          0 :     internal::WitnessSize CalcWitnessSize() const {
     861   [ #  #  #  #  :          0 :         switch (fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     862                 :          0 :             case Fragment::JUST_0: return {{}, 0};
     863                 :            :             case Fragment::JUST_1:
     864                 :            :             case Fragment::OLDER:
     865                 :          0 :             case Fragment::AFTER: return {0, {}};
     866                 :          0 :             case Fragment::PK_K: return {1 + 72, 1};
     867                 :          0 :             case Fragment::PK_H: return {1 + 72 + 1 + 33, 1 + 1 + 33};
     868                 :            :             case Fragment::SHA256:
     869                 :            :             case Fragment::RIPEMD160:
     870                 :            :             case Fragment::HASH256:
     871                 :          0 :             case Fragment::HASH160: return {1 + 32, {}};
     872                 :            :             case Fragment::ANDOR: {
     873                 :          0 :                 const auto sat{(subs[0]->ws.sat + subs[1]->ws.sat) | (subs[0]->ws.dsat + subs[2]->ws.sat)};
     874                 :          0 :                 const auto dsat{subs[0]->ws.dsat + subs[2]->ws.dsat};
     875                 :          0 :                 return {sat, dsat};
     876                 :            :             }
     877                 :          0 :             case Fragment::AND_V: return {subs[0]->ws.sat + subs[1]->ws.sat, {}};
     878                 :          0 :             case Fragment::AND_B: return {subs[0]->ws.sat + subs[1]->ws.sat, subs[0]->ws.dsat + subs[1]->ws.dsat};
     879                 :            :             case Fragment::OR_B: {
     880                 :          0 :                 const auto sat{(subs[0]->ws.dsat + subs[1]->ws.sat) | (subs[0]->ws.sat + subs[1]->ws.dsat)};
     881                 :          0 :                 const auto dsat{subs[0]->ws.dsat + subs[1]->ws.dsat};
     882                 :          0 :                 return {sat, dsat};
     883                 :            :             }
     884                 :          0 :             case Fragment::OR_C: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), {}};
     885                 :          0 :             case Fragment::OR_D: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), subs[0]->ws.dsat + subs[1]->ws.dsat};
     886                 :          0 :             case Fragment::OR_I: return {(subs[0]->ws.sat + 1 + 1) | (subs[1]->ws.sat + 1), (subs[0]->ws.dsat + 1 + 1) | (subs[1]->ws.dsat + 1)};
     887                 :          0 :             case Fragment::MULTI: return {k * (1 + 72) + 1, k + 1};
     888                 :            :             case Fragment::WRAP_A:
     889                 :            :             case Fragment::WRAP_N:
     890                 :            :             case Fragment::WRAP_S:
     891                 :          0 :             case Fragment::WRAP_C: return subs[0]->ws;
     892                 :          0 :             case Fragment::WRAP_D: return {1 + 1 + subs[0]->ws.sat, 1};
     893                 :          0 :             case Fragment::WRAP_V: return {subs[0]->ws.sat, {}};
     894                 :          0 :             case Fragment::WRAP_J: return {subs[0]->ws.sat, 1};
     895                 :            :             case Fragment::THRESH: {
     896                 :          0 :                 auto sats = Vector(internal::MaxInt<uint32_t>(0));
     897   [ #  #  #  # ]:          0 :                 for (const auto& sub : subs) {
     898   [ #  #  #  #  :          0 :                     auto next_sats = Vector(sats[0] + sub->ws.dsat);
             #  #  #  # ]
     899   [ #  #  #  #  :          0 :                     for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ws.dsat) | (sats[j - 1] + sub->ws.sat));
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     900   [ #  #  #  #  :          0 :                     next_sats.push_back(sats[sats.size() - 1] + sub->ws.sat);
             #  #  #  # ]
     901                 :          0 :                     sats = std::move(next_sats);
     902                 :          0 :                 }
     903   [ #  #  #  # ]:          0 :                 assert(k <= sats.size());
     904   [ #  #  #  # ]:          0 :                 return {sats[k], sats[0]};
     905                 :          0 :             }
     906                 :            :         }
     907                 :          0 :         assert(false);
     908                 :          0 :     }
     909                 :            : 
     910                 :            :     template<typename Ctx>
     911                 :          0 :     internal::InputResult ProduceInput(const Ctx& ctx) const {
     912                 :            :         using namespace internal;
     913                 :            : 
     914                 :            :         // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions
     915                 :            :         // given those of its subnodes.
     916                 :          0 :         auto helper = [&ctx](const Node& node, Span<InputResult> subres) -> InputResult {
     917   [ #  #  #  #  :          0 :             switch (node.fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     918                 :            :                 case Fragment::PK_K: {
     919                 :          0 :                     std::vector<unsigned char> sig;
     920         [ #  # ]:          0 :                     Availability avail = ctx.Sign(node.keys[0], sig);
     921   [ #  #  #  #  :          0 :                     return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
             #  #  #  # ]
     922                 :          0 :                 }
     923                 :            :                 case Fragment::PK_H: {
     924                 :          0 :                     std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig;
     925         [ #  # ]:          0 :                     Availability avail = ctx.Sign(node.keys[0], sig);
     926   [ #  #  #  #  :          0 :                     return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     927                 :          0 :                 }
     928                 :            :                 case Fragment::MULTI: {
     929                 :            :                     // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
     930                 :            :                     // In the loop below, these stacks are built up using a dynamic programming approach.
     931                 :            :                     // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many.
     932                 :          0 :                     std::vector<InputStack> sats = Vector(ZERO);
     933         [ #  # ]:          0 :                     for (size_t i = 0; i < node.keys.size(); ++i) {
     934                 :          0 :                         std::vector<unsigned char> sig;
     935         [ #  # ]:          0 :                         Availability avail = ctx.Sign(node.keys[i], sig);
     936                 :            :                         // Compute signature stack for just the i'th key.
     937   [ #  #  #  #  :          0 :                         auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
             #  #  #  # ]
     938                 :            :                         // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
     939                 :            :                         // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the
     940                 :            :                         // current (i'th) key. The very last element needs all signatures filled.
     941                 :          0 :                         std::vector<InputStack> next_sats;
     942         [ #  # ]:          0 :                         next_sats.push_back(sats[0]);
     943   [ #  #  #  #  :          0 :                         for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
          #  #  #  #  #  
                #  #  # ]
     944   [ #  #  #  # ]:          0 :                         next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
     945                 :            :                         // Switch over.
     946                 :          0 :                         sats = std::move(next_sats);
     947                 :          0 :                     }
     948                 :            :                     // The dissatisfaction consists of k+1 stack elements all equal to 0.
     949         [ #  # ]:          0 :                     InputStack nsat = ZERO;
     950   [ #  #  #  #  :          0 :                     for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO;
                   #  # ]
     951         [ #  # ]:          0 :                     assert(node.k <= sats.size());
     952         [ #  # ]:          0 :                     return {std::move(nsat), std::move(sats[node.k])};
     953                 :          0 :                 }
     954                 :            :                 case Fragment::THRESH: {
     955                 :            :                     // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions.
     956                 :            :                     // In the loop below, these stacks are built up using a dynamic programming approach.
     957                 :            :                     // sats[0] starts off empty.
     958                 :          0 :                     std::vector<InputStack> sats = Vector(EMPTY);
     959         [ #  # ]:          0 :                     for (size_t i = 0; i < subres.size(); ++i) {
     960                 :            :                         // Introduce an alias for the i'th last satisfaction/dissatisfaction.
     961                 :          0 :                         auto& res = subres[subres.size() - i - 1];
     962                 :            :                         // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions
     963                 :            :                         // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat
     964                 :            :                         // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions.
     965                 :          0 :                         std::vector<InputStack> next_sats;
     966   [ #  #  #  #  :          0 :                         next_sats.push_back(sats[0] + res.nsat);
             #  #  #  # ]
     967   [ #  #  #  #  :          0 :                         for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat));
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     968   [ #  #  #  # ]:          0 :                         next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
     969                 :            :                         // Switch over.
     970                 :          0 :                         sats = std::move(next_sats);
     971                 :          0 :                     }
     972                 :            :                     // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction
     973                 :            :                     // is computed by gathering all sats[i].nsat for i != k.
     974         [ #  # ]:          0 :                     InputStack nsat = INVALID;
     975         [ #  # ]:          0 :                     for (size_t i = 0; i < sats.size(); ++i) {
     976                 :            :                         // i==k is the satisfaction; i==0 is the canonical dissatisfaction;
     977                 :            :                         // the rest are non-canonical (a no-signature dissatisfaction - the i=0
     978                 :            :                         // form - is always available) and malleable (due to overcompleteness).
     979                 :            :                         // Marking the solutions malleable here is not strictly necessary, as they
     980                 :            :                         // should already never be picked in non-malleable solutions due to the
     981                 :            :                         // availability of the i=0 form.
     982   [ #  #  #  #  :          0 :                         if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon();
             #  #  #  # ]
     983                 :            :                         // Include all dissatisfactions (even these non-canonical ones) in nsat.
     984   [ #  #  #  # ]:          0 :                         if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]);
     985                 :          0 :                     }
     986         [ #  # ]:          0 :                     assert(node.k <= sats.size());
     987         [ #  # ]:          0 :                     return {std::move(nsat), std::move(sats[node.k])};
     988                 :          0 :                 }
     989                 :            :                 case Fragment::OLDER: {
     990         [ #  # ]:          0 :                     return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID};
     991                 :            :                 }
     992                 :            :                 case Fragment::AFTER: {
     993         [ #  # ]:          0 :                     return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID};
     994                 :            :                 }
     995                 :            :                 case Fragment::SHA256: {
     996                 :          0 :                     std::vector<unsigned char> preimage;
     997         [ #  # ]:          0 :                     Availability avail = ctx.SatSHA256(node.data, preimage);
     998   [ #  #  #  #  :          0 :                     return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
                   #  # ]
     999                 :          0 :                 }
    1000                 :            :                 case Fragment::RIPEMD160: {
    1001                 :          0 :                     std::vector<unsigned char> preimage;
    1002         [ #  # ]:          0 :                     Availability avail = ctx.SatRIPEMD160(node.data, preimage);
    1003   [ #  #  #  #  :          0 :                     return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
                   #  # ]
    1004                 :          0 :                 }
    1005                 :            :                 case Fragment::HASH256: {
    1006                 :          0 :                     std::vector<unsigned char> preimage;
    1007         [ #  # ]:          0 :                     Availability avail = ctx.SatHASH256(node.data, preimage);
    1008   [ #  #  #  #  :          0 :                     return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
                   #  # ]
    1009                 :          0 :                 }
    1010                 :            :                 case Fragment::HASH160: {
    1011                 :          0 :                     std::vector<unsigned char> preimage;
    1012         [ #  # ]:          0 :                     Availability avail = ctx.SatHASH160(node.data, preimage);
    1013   [ #  #  #  #  :          0 :                     return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
                   #  # ]
    1014                 :          0 :                 }
    1015                 :            :                 case Fragment::AND_V: {
    1016                 :          0 :                     auto& x = subres[0], &y = subres[1];
    1017                 :            :                     // As the dissatisfaction here only consist of a single option, it doesn't
    1018                 :            :                     // actually need to be listed (it's not required for reasoning about malleability of
    1019                 :            :                     // other options), and is never required (no valid miniscript relies on the ability
    1020                 :            :                     // to satisfy the type V left subexpression). It's still listed here for
    1021                 :            :                     // completeness, as a hypothetical (not currently implemented) satisfier that doesn't
    1022                 :            :                     // care about malleability might in some cases prefer it still.
    1023   [ #  #  #  #  :          0 :                     return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
          #  #  #  #  #  
             #  #  #  #  
                      # ]
    1024                 :            :                 }
    1025                 :            :                 case Fragment::AND_B: {
    1026                 :          0 :                     auto& x = subres[0], &y = subres[1];
    1027                 :            :                     // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here
    1028                 :            :                     // as malleable. While they are definitely malleable, they are also non-canonical due
    1029                 :            :                     // to the guaranteed existence of a no-signature other dissatisfaction (the 1st)
    1030                 :            :                     // option. Because of that, the 2nd and 3rd option will never be chosen, even if they
    1031                 :            :                     // weren't marked as malleable.
    1032   [ #  #  #  #  :          0 :                     return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    1033                 :            :                 }
    1034                 :            :                 case Fragment::OR_B: {
    1035                 :          0 :                     auto& x = subres[0], &z = subres[1];
    1036                 :            :                     // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat).
    1037   [ #  #  #  #  :          0 :                     return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
    1038                 :            :                 }
    1039                 :            :                 case Fragment::OR_C: {
    1040                 :          0 :                     auto& x = subres[0], &z = subres[1];
    1041   [ #  #  #  #  :          0 :                     return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
          #  #  #  #  #  
                      # ]
    1042                 :            :                 }
    1043                 :            :                 case Fragment::OR_D: {
    1044                 :          0 :                     auto& x = subres[0], &z = subres[1];
    1045   [ #  #  #  #  :          0 :                     return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
          #  #  #  #  #  
             #  #  #  #  
                      # ]
    1046                 :            :                 }
    1047                 :            :                 case Fragment::OR_I: {
    1048                 :          0 :                     auto& x = subres[0], &z = subres[1];
    1049   [ #  #  #  #  :          0 :                     return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
    1050                 :            :                 }
    1051                 :            :                 case Fragment::ANDOR: {
    1052                 :          0 :                     auto& x = subres[0], &y = subres[1], &z = subres[2];
    1053   [ #  #  #  #  :          0 :                     return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                #  #  # ]
    1054                 :            :                 }
    1055                 :            :                 case Fragment::WRAP_A:
    1056                 :            :                 case Fragment::WRAP_S:
    1057                 :            :                 case Fragment::WRAP_C:
    1058                 :            :                 case Fragment::WRAP_N:
    1059                 :          0 :                     return std::move(subres[0]);
    1060                 :            :                 case Fragment::WRAP_D: {
    1061                 :          0 :                     auto &x = subres[0];
    1062   [ #  #  #  #  :          0 :                     return {ZERO, x.sat + ONE};
                   #  # ]
    1063                 :            :                 }
    1064                 :            :                 case Fragment::WRAP_J: {
    1065                 :          0 :                     auto &x = subres[0];
    1066                 :            :                     // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists.
    1067                 :            :                     // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even
    1068                 :            :                     // if a dissatisfaction with a top zero element is found, we don't know whether another one with a
    1069                 :            :                     // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly
    1070                 :            :                     // dissatisfiable, this alternative dissatisfaction exists and leads to malleability.
    1071   [ #  #  #  #  :          0 :                     return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
                   #  # ]
    1072                 :            :                 }
    1073                 :            :                 case Fragment::WRAP_V: {
    1074                 :          0 :                     auto &x = subres[0];
    1075                 :          0 :                     return {INVALID, std::move(x.sat)};
    1076                 :            :                 }
    1077                 :          0 :                 case Fragment::JUST_0: return {EMPTY, INVALID};
    1078                 :          0 :                 case Fragment::JUST_1: return {INVALID, EMPTY};
    1079                 :            :             }
    1080                 :          0 :             assert(false);
    1081                 :            :             return {INVALID, INVALID};
    1082                 :          0 :         };
    1083                 :            : 
    1084                 :          0 :         auto tester = [&helper](const Node& node, Span<InputResult> subres) -> InputResult {
    1085                 :          0 :             auto ret = helper(node, subres);
    1086                 :            : 
    1087                 :            :             // Do a consistency check between the satisfaction code and the type checker
    1088                 :            :             // (the actual satisfaction code in ProduceInputHelper does not use GetType)
    1089                 :            : 
    1090                 :            :             // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0.
    1091   [ #  #  #  #  :          0 :             if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 0);
             #  #  #  # ]
    1092   [ #  #  #  #  :          0 :             if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 0);
             #  #  #  # ]
    1093                 :            : 
    1094                 :            :             // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1.
    1095   [ #  #  #  #  :          0 :             if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 1);
             #  #  #  # ]
    1096   [ #  #  #  #  :          0 :             if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 1);
             #  #  #  # ]
    1097                 :            : 
    1098                 :            :             // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions,
    1099                 :            :             // the top element cannot be 0.
    1100   [ #  #  #  #  :          0 :             if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() >= 1);
             #  #  #  # ]
    1101   [ #  #  #  #  :          0 :             if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() >= 1);
             #  #  #  # ]
    1102   [ #  #  #  #  :          0 :             if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.stack.back().empty());
             #  #  #  # ]
    1103                 :            : 
    1104                 :            :             // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable,
    1105                 :            :             // it must be canonical.
    1106   [ #  #  #  #  :          0 :             if (node.GetType() << "d"_mst) assert(ret.nsat.available != Availability::NO);
                   #  # ]
    1107   [ #  #  #  #  :          0 :             if (node.GetType() << "d"_mst) assert(!ret.nsat.has_sig);
                   #  # ]
    1108   [ #  #  #  #  :          0 :             if (node.GetType() << "d"_mst && !ret.nsat.malleable) assert(!ret.nsat.non_canon);
             #  #  #  # ]
    1109                 :            : 
    1110                 :            :             // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature.
    1111   [ #  #  #  #  :          0 :             if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.has_sig);
             #  #  #  # ]
    1112   [ #  #  #  #  :          0 :             if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) assert(ret.sat.has_sig);
             #  #  #  # ]
    1113                 :            : 
    1114                 :            :             // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist.
    1115   [ #  #  #  #  :          0 :             if (node.GetType() << "me"_mst) assert(ret.nsat.available != Availability::NO);
                   #  # ]
    1116   [ #  #  #  #  :          0 :             if (node.GetType() << "me"_mst) assert(!ret.nsat.malleable);
                   #  # ]
    1117                 :            : 
    1118                 :            :             // For 'm' nodes, if a satisfaction exists, it must be non-malleable.
    1119   [ #  #  #  #  :          0 :             if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.malleable);
             #  #  #  # ]
    1120                 :            : 
    1121                 :            :             // If a non-malleable satisfaction exists, it must be canonical.
    1122   [ #  #  #  #  :          0 :             if (ret.sat.available != Availability::NO && !ret.sat.malleable) assert(!ret.sat.non_canon);
                   #  # ]
    1123                 :            : 
    1124                 :          0 :             return ret;
    1125         [ #  # ]:          0 :         };
    1126                 :            : 
    1127                 :          0 :         return TreeEval<InputResult>(tester);
    1128                 :            :     }
    1129                 :            : 
    1130                 :            : public:
    1131                 :            :     /** Update duplicate key information in this Node.
    1132                 :            :      *
    1133                 :            :      * This uses a custom key comparator provided by the context in order to still detect duplicates
    1134                 :            :      * for more complicated types.
    1135                 :            :      */
    1136                 :          0 :     template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const
    1137                 :            :     {
    1138                 :            :         // We cannot use a lambda here, as lambdas are non assignable, and the set operations
    1139                 :            :         // below require moving the comparators around.
    1140                 :            :         struct Comp {
    1141                 :            :             const Ctx* ctx_ptr;
    1142                 :          0 :             Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
    1143                 :          0 :             bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
    1144                 :            :         };
    1145                 :            : 
    1146                 :            :         // state in the recursive computation:
    1147                 :            :         // - std::nullopt means "this node has duplicates"
    1148                 :            :         // - an std::set means "this node has no duplicate keys, and they are: ...".
    1149                 :            :         using keyset = std::set<Key, Comp>;
    1150                 :            :         using state = std::optional<keyset>;
    1151                 :            : 
    1152                 :          0 :         auto upfn = [&ctx](const Node& node, Span<state> subs) -> state {
    1153                 :            :             // If this node is already known to have duplicates, nothing left to do.
    1154   [ #  #  #  #  :          0 :             if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {};
          #  #  #  #  #  
                #  #  # ]
    1155                 :            : 
    1156                 :            :             // Check if one of the children is already known to have duplicates.
    1157   [ #  #  #  #  :          0 :             for (auto& sub : subs) {
                   #  # ]
    1158   [ #  #  #  #  :          0 :                 if (!sub.has_value()) {
                   #  # ]
    1159                 :          0 :                     node.has_duplicate_keys = true;
    1160                 :          0 :                     return {};
    1161                 :            :                 }
    1162                 :            :             }
    1163                 :            : 
    1164                 :            :             // Start building the set of keys involved in this node and children.
    1165                 :            :             // Start by keys in this node directly.
    1166                 :          0 :             size_t keys_count = node.keys.size();
    1167   [ #  #  #  #  :          0 :             keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
                   #  # ]
    1168   [ #  #  #  #  :          0 :             if (key_set.size() != keys_count) {
                   #  # ]
    1169                 :            :                 // It already has duplicates; bail out.
    1170   [ #  #  #  #  :          0 :                 node.has_duplicate_keys = true;
                   #  # ]
    1171                 :          0 :                 return {};
    1172                 :            :             }
    1173                 :            : 
    1174                 :            :             // Merge the keys from the children into this set.
    1175   [ #  #  #  #  :          0 :             for (auto& sub : subs) {
                   #  # ]
    1176   [ #  #  #  #  :          0 :                 keys_count += sub->size();
                   #  # ]
    1177                 :            :                 // Small optimization: std::set::merge is linear in the size of the second arg but
    1178                 :            :                 // logarithmic in the size of the first.
    1179   [ #  #  #  #  :          0 :                 if (key_set.size() < sub->size()) std::swap(key_set, *sub);
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
    1180   [ #  #  #  #  :          0 :                 key_set.merge(*sub);
          #  #  #  #  #  
                #  #  # ]
    1181   [ #  #  #  #  :          0 :                 if (key_set.size() != keys_count) {
                   #  # ]
    1182   [ #  #  #  #  :          0 :                     node.has_duplicate_keys = true;
                   #  # ]
    1183                 :          0 :                     return {};
    1184                 :            :                 }
    1185                 :            :             }
    1186                 :            : 
    1187   [ #  #  #  #  :          0 :             node.has_duplicate_keys = false;
                   #  # ]
    1188   [ #  #  #  #  :          0 :             return key_set;
                   #  # ]
    1189                 :          0 :         };
    1190                 :            : 
    1191                 :          0 :         TreeEval<state>(upfn);
    1192                 :          0 :     }
    1193                 :            : 
    1194                 :            :     //! Return the size of the script for this expression (faster than ToScript().size()).
    1195                 :          0 :     size_t ScriptSize() const { return scriptlen; }
    1196                 :            : 
    1197                 :            :     //! Return the maximum number of ops needed to satisfy this script non-malleably.
    1198                 :          0 :     std::optional<uint32_t> GetOps() const {
    1199         [ #  # ]:          0 :         if (!ops.sat.valid) return {};
    1200                 :          0 :         return ops.count + ops.sat.value;
    1201                 :          0 :     }
    1202                 :            : 
    1203                 :            :     //! Return the number of ops in the script (not counting the dynamic ones that depend on execution).
    1204                 :          0 :     uint32_t GetStaticOps() const { return ops.count; }
    1205                 :            : 
    1206                 :            :     //! Check the ops limit of this script against the consensus limit.
    1207                 :          0 :     bool CheckOpsLimit() const {
    1208         [ #  # ]:          0 :         if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
    1209                 :          0 :         return true;
    1210                 :          0 :     }
    1211                 :            : 
    1212                 :            :     /** Return the maximum number of stack elements needed to satisfy this script non-malleably.
    1213                 :            :      * This does not account for the P2WSH script push. */
    1214                 :          0 :     std::optional<uint32_t> GetStackSize() const {
    1215         [ #  # ]:          0 :         if (!ss.sat.valid) return {};
    1216                 :          0 :         return ss.sat.value;
    1217                 :          0 :     }
    1218                 :            : 
    1219                 :            :     //! Check the maximum stack size for this script against the policy limit.
    1220                 :          0 :     bool CheckStackSize() const {
    1221         [ #  # ]:          0 :         if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
    1222                 :          0 :         return true;
    1223                 :          0 :     }
    1224                 :            : 
    1225                 :            :     //! Whether no satisfaction exists for this node.
    1226                 :          0 :     bool IsNotSatisfiable() const { return !GetStackSize(); }
    1227                 :            : 
    1228                 :            :     /** Return the maximum size in bytes of a witness to satisfy this script non-malleably. Note this does
    1229                 :            :      * not include the witness script push. */
    1230                 :          0 :     std::optional<uint32_t> GetWitnessSize() const {
    1231         [ #  # ]:          0 :         if (!ws.sat.valid) return {};
    1232                 :          0 :         return ws.sat.value;
    1233                 :          0 :     }
    1234                 :            : 
    1235                 :            :     //! Return the expression type.
    1236                 :          0 :     Type GetType() const { return typ; }
    1237                 :            : 
    1238                 :            :     //! Find an insane subnode which has no insane children. Nullptr if there is none.
    1239                 :          0 :     const Node* FindInsaneSub() const {
    1240                 :          0 :         return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
    1241   [ #  #  #  # ]:          0 :             for (auto& sub: subs) if (sub) return sub;
    1242         [ #  # ]:          0 :             if (!node.IsSaneSubexpression()) return &node;
    1243                 :          0 :             return nullptr;
    1244                 :          0 :         });
    1245                 :            :     }
    1246                 :            : 
    1247                 :            :     //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all
    1248                 :            :     //! key, time, and hashing nodes, and should return their satisfiability.
    1249                 :            :     template<typename F>
    1250                 :          0 :     bool IsSatisfiable(F fn) const
    1251                 :            :     {
    1252                 :            :         // TreeEval() doesn't support bool as NodeType, so use int instead.
    1253                 :          0 :         return TreeEval<int>([&fn](const Node& node, Span<int> subs) -> bool {
    1254   [ #  #  #  #  :          0 :             switch (node.fragment) {
             #  #  #  # ]
    1255                 :            :                 case Fragment::JUST_0:
    1256                 :          0 :                     return false;
    1257                 :            :                 case Fragment::JUST_1:
    1258                 :          0 :                     return true;
    1259                 :            :                 case Fragment::PK_K:
    1260                 :            :                 case Fragment::PK_H:
    1261                 :            :                 case Fragment::MULTI:
    1262                 :            :                 case Fragment::AFTER:
    1263                 :            :                 case Fragment::OLDER:
    1264                 :            :                 case Fragment::HASH256:
    1265                 :            :                 case Fragment::HASH160:
    1266                 :            :                 case Fragment::SHA256:
    1267                 :            :                 case Fragment::RIPEMD160:
    1268                 :          0 :                     return bool{fn(node)};
    1269                 :            :                 case Fragment::ANDOR:
    1270   [ #  #  #  # ]:          0 :                     return (subs[0] && subs[1]) || subs[2];
    1271                 :            :                 case Fragment::AND_V:
    1272                 :            :                 case Fragment::AND_B:
    1273         [ #  # ]:          0 :                     return subs[0] && subs[1];
    1274                 :            :                 case Fragment::OR_B:
    1275                 :            :                 case Fragment::OR_C:
    1276                 :            :                 case Fragment::OR_D:
    1277                 :            :                 case Fragment::OR_I:
    1278         [ #  # ]:          0 :                     return subs[0] || subs[1];
    1279                 :            :                 case Fragment::THRESH:
    1280                 :          0 :                     return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k;
    1281                 :            :                 default: // wrappers
    1282         [ #  # ]:          0 :                     assert(subs.size() == 1);
    1283                 :          0 :                     return subs[0];
    1284                 :            :             }
    1285                 :          0 :         });
    1286                 :            :     }
    1287                 :            : 
    1288                 :            :     //! Check whether this node is valid at all.
    1289   [ #  #  #  # ]:          0 :     bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
    1290                 :            : 
    1291                 :            :     //! Check whether this node is valid as a script on its own.
    1292   [ #  #  #  # ]:          0 :     bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
    1293                 :            : 
    1294                 :            :     //! Check whether this script can always be satisfied in a non-malleable way.
    1295                 :          0 :     bool IsNonMalleable() const { return GetType() << "m"_mst; }
    1296                 :            : 
    1297                 :            :     //! Check whether this script always needs a signature.
    1298                 :          0 :     bool NeedsSignature() const { return GetType() << "s"_mst; }
    1299                 :            : 
    1300                 :            :     //! Check whether there is no satisfaction path that contains both timelocks and heightlocks
    1301                 :          0 :     bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
    1302                 :            : 
    1303                 :            :     //! Check whether there is no duplicate key across this fragment and all its sub-fragments.
    1304         [ #  # ]:          0 :     bool CheckDuplicateKey() const { return has_duplicate_keys && !*has_duplicate_keys; }
    1305                 :            : 
    1306                 :            :     //! Whether successful non-malleable satisfactions are guaranteed to be valid.
    1307   [ #  #  #  # ]:          0 :     bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
    1308                 :            : 
    1309                 :            :     //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own.
    1310   [ #  #  #  #  :          0 :     bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); }
                   #  # ]
    1311                 :            : 
    1312                 :            :     //! Check whether this node is safe as a script on its own.
    1313   [ #  #  #  # ]:          0 :     bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
    1314                 :            : 
    1315                 :            :     //! Produce a witness for this script, if possible and given the information available in the context.
    1316                 :            :     //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction()
    1317                 :            :     //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's
    1318                 :            :     //! conditions are satisfied (private keys and hash preimages available, locktimes satsified).
    1319                 :            :     template<typename Ctx>
    1320                 :          0 :     Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const {
    1321                 :          0 :         auto ret = ProduceInput(ctx);
    1322   [ #  #  #  #  :          0 :         if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO;
                   #  # ]
    1323                 :          0 :         stack = std::move(ret.sat.stack);
    1324                 :          0 :         return ret.sat.available;
    1325                 :          0 :     }
    1326                 :            : 
    1327                 :            :     //! Equality testing.
    1328                 :          0 :     bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
    1329                 :            : 
    1330                 :            :     // Constructors with various argument combinations, which bypass the duplicate key check.
    1331   [ #  #  #  #  :          0 :     Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
          #  #  #  #  #  
                      # ]
    1332   [ #  #  #  #  :          0 :     Node(internal::NoDupCheck, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    1333                 :            :     Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
    1334   [ #  #  #  #  :          0 :     Node(internal::NoDupCheck, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    1335   [ #  #  #  #  :          0 :     Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    1336   [ #  #  #  #  :          0 :     Node(internal::NoDupCheck, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    1337                 :            : 
    1338                 :            :     // Constructors with various argument combinations, which do perform the duplicate key check.
    1339                 :            :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
    1340                 :            :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
    1341                 :            :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
    1342                 :            :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
    1343                 :            :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
    1344         [ #  # ]:          0 :     template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, val) { DuplicateKeyCheck(ctx); }
    1345                 :            : };
    1346                 :            : 
    1347                 :            : namespace internal {
    1348                 :            : 
    1349                 :            : enum class ParseContext {
    1350                 :            :     /** An expression which may be begin with wrappers followed by a colon. */
    1351                 :            :     WRAPPED_EXPR,
    1352                 :            :     /** A miniscript expression which does not begin with wrappers. */
    1353                 :            :     EXPR,
    1354                 :            : 
    1355                 :            :     /** SWAP wraps the top constructed node with s: */
    1356                 :            :     SWAP,
    1357                 :            :     /** ALT wraps the top constructed node with a: */
    1358                 :            :     ALT,
    1359                 :            :     /** CHECK wraps the top constructed node with c: */
    1360                 :            :     CHECK,
    1361                 :            :     /** DUP_IF wraps the top constructed node with d: */
    1362                 :            :     DUP_IF,
    1363                 :            :     /** VERIFY wraps the top constructed node with v: */
    1364                 :            :     VERIFY,
    1365                 :            :     /** NON_ZERO wraps the top constructed node with j: */
    1366                 :            :     NON_ZERO,
    1367                 :            :     /** ZERO_NOTEQUAL wraps the top constructed node with n: */
    1368                 :            :     ZERO_NOTEQUAL,
    1369                 :            :     /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
    1370                 :            :     WRAP_U,
    1371                 :            :     /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
    1372                 :            :     WRAP_T,
    1373                 :            : 
    1374                 :            :     /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
    1375                 :            :     AND_N,
    1376                 :            :     /** AND_V will construct an and_v node from the last two constructed nodes. */
    1377                 :            :     AND_V,
    1378                 :            :     /** AND_B will construct an and_b node from the last two constructed nodes. */
    1379                 :            :     AND_B,
    1380                 :            :     /** ANDOR will construct an andor node from the last three constructed nodes. */
    1381                 :            :     ANDOR,
    1382                 :            :     /** OR_B will construct an or_b node from the last two constructed nodes. */
    1383                 :            :     OR_B,
    1384                 :            :     /** OR_C will construct an or_c node from the last two constructed nodes. */
    1385                 :            :     OR_C,
    1386                 :            :     /** OR_D will construct an or_d node from the last two constructed nodes. */
    1387                 :            :     OR_D,
    1388                 :            :     /** OR_I will construct an or_i node from the last two constructed nodes. */
    1389                 :            :     OR_I,
    1390                 :            : 
    1391                 :            :     /** THRESH will read a wrapped expression, and then look for a COMMA. If
    1392                 :            :      * no comma follows, it will construct a thresh node from the appropriate
    1393                 :            :      * number of constructed children. Otherwise, it will recurse with another
    1394                 :            :      * THRESH. */
    1395                 :            :     THRESH,
    1396                 :            : 
    1397                 :            :     /** COMMA expects the next element to be ',' and fails if not. */
    1398                 :            :     COMMA,
    1399                 :            :     /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
    1400                 :            :     CLOSE_BRACKET,
    1401                 :            : };
    1402                 :            : 
    1403                 :            : int FindNextChar(Span<const char> in, const char m);
    1404                 :            : 
    1405                 :            : /** Parse a key string ending at the end of the fragment's text representation. */
    1406                 :            : template<typename Key, typename Ctx>
    1407                 :          0 : std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
    1408                 :            : {
    1409                 :          0 :     int key_size = FindNextChar(in, ')');
    1410         [ #  # ]:          0 :     if (key_size < 1) return {};
    1411                 :          0 :     auto key = ctx.FromString(in.begin(), in.begin() + key_size);
    1412         [ #  # ]:          0 :     if (!key) return {};
    1413                 :          0 :     return {{std::move(*key), key_size}};
    1414                 :          0 : }
    1415                 :            : 
    1416                 :            : /** Parse a hex string ending at the end of the fragment's text representation. */
    1417                 :            : template<typename Ctx>
    1418                 :          0 : std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
    1419                 :            :                                                                          const Ctx& ctx)
    1420                 :            : {
    1421                 :          0 :     int hash_size = FindNextChar(in, ')');
    1422         [ #  # ]:          0 :     if (hash_size < 1) return {};
    1423         [ #  # ]:          0 :     std::string val = std::string(in.begin(), in.begin() + hash_size);
    1424   [ #  #  #  # ]:          0 :     if (!IsHex(val)) return {};
    1425         [ #  # ]:          0 :     auto hash = ParseHex(val);
    1426         [ #  # ]:          0 :     if (hash.size() != expected_size) return {};
    1427   [ #  #  #  # ]:          0 :     return {{std::move(hash), hash_size}};
    1428                 :          0 : }
    1429                 :            : 
    1430                 :            : /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
    1431                 :            : template<typename Key>
    1432                 :          0 : void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
    1433                 :            : {
    1434                 :          0 :     NodeRef<Key> child = std::move(constructed.back());
    1435                 :          0 :     constructed.pop_back();
    1436   [ #  #  #  # ]:          0 :     if (reverse) {
    1437   [ #  #  #  #  :          0 :         constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
             #  #  #  # ]
    1438                 :          0 :     } else {
    1439   [ #  #  #  #  :          0 :         constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
             #  #  #  # ]
    1440                 :            :     }
    1441                 :          0 : }
    1442                 :            : 
    1443                 :            : /**
    1444                 :            :  * Parse a miniscript from its textual descriptor form.
    1445                 :            :  * This does not check whether the script is valid, let alone sane. The caller is expected to use
    1446                 :            :  * the `IsValidTopLevel()` and `IsSaneTopLevel()` to check for these properties on the node.
    1447                 :            :  */
    1448                 :            : template<typename Key, typename Ctx>
    1449                 :          0 : inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
    1450                 :            : {
    1451                 :            :     using namespace spanparsing;
    1452                 :            : 
    1453                 :            :     // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
    1454                 :            :     // script byte from all leaf nodes, counting it instead whenever a space for a recursive
    1455                 :            :     // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
    1456                 :            :     // increment the script_size by at least one, except for:
    1457                 :            :     // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
    1458                 :            :     //   This is not an issue however, as "space" for them has to be created by combinators,
    1459                 :            :     //   which do increment script_size.
    1460                 :            :     // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
    1461                 :            :     //   (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
    1462                 :            :     //   to be interleaved with other fragments to be valid, so this is not a concern.
    1463                 :          0 :     size_t script_size{1};
    1464                 :            : 
    1465                 :            :     // The two integers are used to hold state for thresh()
    1466                 :          0 :     std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
    1467                 :          0 :     std::vector<NodeRef<Key>> constructed;
    1468                 :            : 
    1469         [ #  # ]:          0 :     to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1470                 :            : 
    1471         [ #  # ]:          0 :     while (!to_parse.empty()) {
    1472         [ #  # ]:          0 :         if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
    1473                 :            : 
    1474                 :            :         // Get the current context we are decoding within
    1475                 :          0 :         auto [cur_context, n, k] = to_parse.back();
    1476                 :          0 :         to_parse.pop_back();
    1477                 :            : 
    1478   [ #  #  #  #  :          0 :         switch (cur_context) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
    1479                 :            :         case ParseContext::WRAPPED_EXPR: {
    1480                 :          0 :             std::optional<size_t> colon_index{};
    1481         [ #  # ]:          0 :             for (size_t i = 1; i < in.size(); ++i) {
    1482         [ #  # ]:          0 :                 if (in[i] == ':') {
    1483         [ #  # ]:          0 :                     colon_index = i;
    1484                 :          0 :                     break;
    1485                 :            :                 }
    1486   [ #  #  #  # ]:          0 :                 if (in[i] < 'a' || in[i] > 'z') break;
    1487                 :          0 :             }
    1488                 :            :             // If there is no colon, this loop won't execute
    1489                 :          0 :             bool last_was_v{false};
    1490   [ #  #  #  #  :          0 :             for (size_t j = 0; colon_index && j < *colon_index; ++j) {
                   #  # ]
    1491         [ #  # ]:          0 :                 if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
    1492         [ #  # ]:          0 :                 if (in[j] == 'a') {
    1493                 :          0 :                     script_size += 2;
    1494         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::ALT, -1, -1);
    1495         [ #  # ]:          0 :                 } else if (in[j] == 's') {
    1496                 :          0 :                     script_size += 1;
    1497         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::SWAP, -1, -1);
    1498         [ #  # ]:          0 :                 } else if (in[j] == 'c') {
    1499                 :          0 :                     script_size += 1;
    1500         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::CHECK, -1, -1);
    1501         [ #  # ]:          0 :                 } else if (in[j] == 'd') {
    1502                 :          0 :                     script_size += 3;
    1503         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
    1504         [ #  # ]:          0 :                 } else if (in[j] == 'j') {
    1505                 :          0 :                     script_size += 4;
    1506         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
    1507         [ #  # ]:          0 :                 } else if (in[j] == 'n') {
    1508                 :          0 :                     script_size += 1;
    1509         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
    1510         [ #  # ]:          0 :                 } else if (in[j] == 'v') {
    1511                 :            :                     // do not permit "...vv...:"; it's not valid, and also doesn't trigger early
    1512                 :            :                     // failure as script_size isn't incremented.
    1513         [ #  # ]:          0 :                     if (last_was_v) return {};
    1514         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
    1515         [ #  # ]:          0 :                 } else if (in[j] == 'u') {
    1516                 :          0 :                     script_size += 4;
    1517         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
    1518         [ #  # ]:          0 :                 } else if (in[j] == 't') {
    1519                 :          0 :                     script_size += 1;
    1520         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
    1521         [ #  # ]:          0 :                 } else if (in[j] == 'l') {
    1522                 :            :                     // The l: wrapper is equivalent to or_i(0,X)
    1523                 :          0 :                     script_size += 4;
    1524   [ #  #  #  # ]:          0 :                     constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
    1525         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::OR_I, -1, -1);
    1526                 :          0 :                 } else {
    1527                 :          0 :                     return {};
    1528                 :            :                 }
    1529                 :          0 :                 last_was_v = (in[j] == 'v');
    1530                 :          0 :             }
    1531         [ #  # ]:          0 :             to_parse.emplace_back(ParseContext::EXPR, -1, -1);
    1532   [ #  #  #  # ]:          0 :             if (colon_index) in = in.subspan(*colon_index + 1);
    1533                 :          0 :             break;
    1534                 :            :         }
    1535                 :            :         case ParseContext::EXPR: {
    1536   [ #  #  #  #  :          0 :             if (Const("0", in)) {
                   #  # ]
    1537   [ #  #  #  # ]:          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
    1538   [ #  #  #  #  :          0 :             } else if (Const("1", in)) {
                   #  # ]
    1539   [ #  #  #  # ]:          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
    1540   [ #  #  #  #  :          0 :             } else if (Const("pk(", in)) {
                   #  # ]
    1541         [ #  # ]:          0 :                 auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
    1542         [ #  # ]:          0 :                 if (!res) return {};
    1543         [ #  # ]:          0 :                 auto& [key, key_size] = *res;
    1544   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
          #  #  #  #  #  
                #  #  # ]
    1545                 :          0 :                 in = in.subspan(key_size + 1);
    1546                 :          0 :                 script_size += 34;
    1547   [ #  #  #  #  :          0 :             } else if (Const("pkh(", in)) {
                   #  # ]
    1548         [ #  # ]:          0 :                 auto res = ParseKeyEnd<Key>(in, ctx);
    1549         [ #  # ]:          0 :                 if (!res) return {};
    1550         [ #  # ]:          0 :                 auto& [key, key_size] = *res;
    1551   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
          #  #  #  #  #  
                #  #  # ]
    1552                 :          0 :                 in = in.subspan(key_size + 1);
    1553                 :          0 :                 script_size += 24;
    1554   [ #  #  #  #  :          0 :             } else if (Const("pk_k(", in)) {
                   #  # ]
    1555         [ #  # ]:          0 :                 auto res = ParseKeyEnd<Key>(in, ctx);
    1556         [ #  # ]:          0 :                 if (!res) return {};
    1557         [ #  # ]:          0 :                 auto& [key, key_size] = *res;
    1558   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
             #  #  #  # ]
    1559                 :          0 :                 in = in.subspan(key_size + 1);
    1560                 :          0 :                 script_size += 33;
    1561   [ #  #  #  #  :          0 :             } else if (Const("pk_h(", in)) {
                   #  # ]
    1562         [ #  # ]:          0 :                 auto res = ParseKeyEnd<Key>(in, ctx);
    1563         [ #  # ]:          0 :                 if (!res) return {};
    1564         [ #  # ]:          0 :                 auto& [key, key_size] = *res;
    1565   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
             #  #  #  # ]
    1566                 :          0 :                 in = in.subspan(key_size + 1);
    1567                 :          0 :                 script_size += 23;
    1568   [ #  #  #  #  :          0 :             } else if (Const("sha256(", in)) {
                   #  # ]
    1569         [ #  # ]:          0 :                 auto res = ParseHexStrEnd(in, 32, ctx);
    1570         [ #  # ]:          0 :                 if (!res) return {};
    1571         [ #  # ]:          0 :                 auto& [hash, hash_size] = *res;
    1572   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
                   #  # ]
    1573                 :          0 :                 in = in.subspan(hash_size + 1);
    1574                 :          0 :                 script_size += 38;
    1575   [ #  #  #  #  :          0 :             } else if (Const("ripemd160(", in)) {
             #  #  #  # ]
    1576         [ #  # ]:          0 :                 auto res = ParseHexStrEnd(in, 20, ctx);
    1577         [ #  # ]:          0 :                 if (!res) return {};
    1578         [ #  # ]:          0 :                 auto& [hash, hash_size] = *res;
    1579   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
                   #  # ]
    1580                 :          0 :                 in = in.subspan(hash_size + 1);
    1581                 :          0 :                 script_size += 26;
    1582   [ #  #  #  #  :          0 :             } else if (Const("hash256(", in)) {
             #  #  #  # ]
    1583         [ #  # ]:          0 :                 auto res = ParseHexStrEnd(in, 32, ctx);
    1584         [ #  # ]:          0 :                 if (!res) return {};
    1585         [ #  # ]:          0 :                 auto& [hash, hash_size] = *res;
    1586   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
                   #  # ]
    1587                 :          0 :                 in = in.subspan(hash_size + 1);
    1588                 :          0 :                 script_size += 38;
    1589   [ #  #  #  #  :          0 :             } else if (Const("hash160(", in)) {
             #  #  #  # ]
    1590         [ #  # ]:          0 :                 auto res = ParseHexStrEnd(in, 20, ctx);
    1591         [ #  # ]:          0 :                 if (!res) return {};
    1592         [ #  # ]:          0 :                 auto& [hash, hash_size] = *res;
    1593   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
                   #  # ]
    1594                 :          0 :                 in = in.subspan(hash_size + 1);
    1595                 :          0 :                 script_size += 26;
    1596   [ #  #  #  #  :          0 :             } else if (Const("after(", in)) {
             #  #  #  # ]
    1597         [ #  # ]:          0 :                 int arg_size = FindNextChar(in, ')');
    1598         [ #  # ]:          0 :                 if (arg_size < 1) return {};
    1599                 :            :                 int64_t num;
    1600   [ #  #  #  #  :          0 :                 if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
                   #  # ]
    1601   [ #  #  #  # ]:          0 :                 if (num < 1 || num >= 0x80000000L) return {};
    1602   [ #  #  #  # ]:          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
    1603                 :          0 :                 in = in.subspan(arg_size + 1);
    1604                 :          0 :                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
    1605   [ #  #  #  #  :          0 :             } else if (Const("older(", in)) {
                   #  # ]
    1606         [ #  # ]:          0 :                 int arg_size = FindNextChar(in, ')');
    1607         [ #  # ]:          0 :                 if (arg_size < 1) return {};
    1608                 :            :                 int64_t num;
    1609   [ #  #  #  #  :          0 :                 if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
                   #  # ]
    1610   [ #  #  #  # ]:          0 :                 if (num < 1 || num >= 0x80000000L) return {};
    1611   [ #  #  #  # ]:          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
    1612                 :          0 :                 in = in.subspan(arg_size + 1);
    1613                 :          0 :                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
    1614   [ #  #  #  #  :          0 :             } else if (Const("multi(", in)) {
                   #  # ]
    1615                 :            :                 // Get threshold
    1616         [ #  # ]:          0 :                 int next_comma = FindNextChar(in, ',');
    1617         [ #  # ]:          0 :                 if (next_comma < 1) return {};
    1618   [ #  #  #  #  :          0 :                 if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
             #  #  #  # ]
    1619                 :          0 :                 in = in.subspan(next_comma + 1);
    1620                 :            :                 // Get keys
    1621                 :          0 :                 std::vector<Key> keys;
    1622         [ #  # ]:          0 :                 while (next_comma != -1) {
    1623         [ #  # ]:          0 :                     next_comma = FindNextChar(in, ',');
    1624   [ #  #  #  # ]:          0 :                     int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
    1625         [ #  # ]:          0 :                     if (key_length < 1) return {};
    1626         [ #  # ]:          0 :                     auto key = ctx.FromString(in.begin(), in.begin() + key_length);
    1627         [ #  # ]:          0 :                     if (!key) return {};
    1628   [ #  #  #  # ]:          0 :                     keys.push_back(std::move(*key));
    1629                 :          0 :                     in = in.subspan(key_length + 1);
    1630                 :            :                 }
    1631   [ #  #  #  # ]:          0 :                 if (keys.size() < 1 || keys.size() > 20) return {};
    1632   [ #  #  #  # ]:          0 :                 if (k < 1 || k > (int64_t)keys.size()) return {};
    1633                 :          0 :                 script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
    1634   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
                   #  # ]
    1635   [ #  #  #  #  :          0 :             } else if (Const("thresh(", in)) {
             #  #  #  # ]
    1636         [ #  # ]:          0 :                 int next_comma = FindNextChar(in, ',');
    1637         [ #  # ]:          0 :                 if (next_comma < 1) return {};
    1638   [ #  #  #  #  :          0 :                 if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
             #  #  #  # ]
    1639         [ #  # ]:          0 :                 if (k < 1) return {};
    1640                 :          0 :                 in = in.subspan(next_comma + 1);
    1641                 :            :                 // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
    1642   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(ParseContext::THRESH, 1, k);
    1643         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1644                 :          0 :                 script_size += 2 + (k > 16) + (k > 0x7f) + (k > 0x7fff) + (k > 0x7fffff);
    1645   [ #  #  #  #  :          0 :             } else if (Const("andor(", in)) {
                   #  # ]
    1646         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
    1647         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
    1648         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1649         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::COMMA, -1, -1);
    1650         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1651         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::COMMA, -1, -1);
    1652         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1653                 :          0 :                 script_size += 5;
    1654                 :          0 :             } else {
    1655   [ #  #  #  #  :          0 :                 if (Const("and_n(", in)) {
                   #  # ]
    1656         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::AND_N, -1, -1);
    1657                 :          0 :                     script_size += 5;
    1658   [ #  #  #  #  :          0 :                 } else if (Const("and_b(", in)) {
                   #  # ]
    1659         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::AND_B, -1, -1);
    1660                 :          0 :                     script_size += 2;
    1661   [ #  #  #  #  :          0 :                 } else if (Const("and_v(", in)) {
                   #  # ]
    1662         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::AND_V, -1, -1);
    1663                 :          0 :                     script_size += 1;
    1664   [ #  #  #  #  :          0 :                 } else if (Const("or_b(", in)) {
                   #  # ]
    1665         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::OR_B, -1, -1);
    1666                 :          0 :                     script_size += 2;
    1667   [ #  #  #  #  :          0 :                 } else if (Const("or_c(", in)) {
                   #  # ]
    1668         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::OR_C, -1, -1);
    1669                 :          0 :                     script_size += 3;
    1670   [ #  #  #  #  :          0 :                 } else if (Const("or_d(", in)) {
                   #  # ]
    1671         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::OR_D, -1, -1);
    1672                 :          0 :                     script_size += 4;
    1673   [ #  #  #  #  :          0 :                 } else if (Const("or_i(", in)) {
                   #  # ]
    1674         [ #  # ]:          0 :                     to_parse.emplace_back(ParseContext::OR_I, -1, -1);
    1675                 :          0 :                     script_size += 4;
    1676                 :          0 :                 } else {
    1677                 :          0 :                     return {};
    1678                 :            :                 }
    1679         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
    1680         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1681         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::COMMA, -1, -1);
    1682         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1683                 :            :             }
    1684                 :          0 :             break;
    1685                 :            :         }
    1686                 :            :         case ParseContext::ALT: {
    1687   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
    1688                 :          0 :             break;
    1689                 :            :         }
    1690                 :            :         case ParseContext::SWAP: {
    1691   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
    1692                 :          0 :             break;
    1693                 :            :         }
    1694                 :            :         case ParseContext::CHECK: {
    1695   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
    1696                 :          0 :             break;
    1697                 :            :         }
    1698                 :            :         case ParseContext::DUP_IF: {
    1699   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
    1700                 :          0 :             break;
    1701                 :            :         }
    1702                 :            :         case ParseContext::NON_ZERO: {
    1703   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
    1704                 :          0 :             break;
    1705                 :            :         }
    1706                 :            :         case ParseContext::ZERO_NOTEQUAL: {
    1707   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
    1708                 :          0 :             break;
    1709                 :            :         }
    1710                 :            :         case ParseContext::VERIFY: {
    1711   [ #  #  #  #  :          0 :             script_size += (constructed.back()->GetType() << "x"_mst);
                   #  # ]
    1712   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
    1713                 :          0 :             break;
    1714                 :            :         }
    1715                 :            :         case ParseContext::WRAP_U: {
    1716   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
                   #  # ]
    1717                 :          0 :             break;
    1718                 :            :         }
    1719                 :            :         case ParseContext::WRAP_T: {
    1720   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
                   #  # ]
    1721                 :          0 :             break;
    1722                 :            :         }
    1723                 :            :         case ParseContext::AND_B: {
    1724         [ #  # ]:          0 :             BuildBack(Fragment::AND_B, constructed);
    1725                 :          0 :             break;
    1726                 :            :         }
    1727                 :            :         case ParseContext::AND_N: {
    1728                 :          0 :             auto mid = std::move(constructed.back());
    1729                 :          0 :             constructed.pop_back();
    1730   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
                   #  # ]
    1731                 :            :             break;
    1732                 :          0 :         }
    1733                 :            :         case ParseContext::AND_V: {
    1734         [ #  # ]:          0 :             BuildBack(Fragment::AND_V, constructed);
    1735                 :          0 :             break;
    1736                 :            :         }
    1737                 :            :         case ParseContext::OR_B: {
    1738         [ #  # ]:          0 :             BuildBack(Fragment::OR_B, constructed);
    1739                 :          0 :             break;
    1740                 :            :         }
    1741                 :            :         case ParseContext::OR_C: {
    1742         [ #  # ]:          0 :             BuildBack(Fragment::OR_C, constructed);
    1743                 :          0 :             break;
    1744                 :            :         }
    1745                 :            :         case ParseContext::OR_D: {
    1746         [ #  # ]:          0 :             BuildBack(Fragment::OR_D, constructed);
    1747                 :          0 :             break;
    1748                 :            :         }
    1749                 :            :         case ParseContext::OR_I: {
    1750         [ #  # ]:          0 :             BuildBack(Fragment::OR_I, constructed);
    1751                 :          0 :             break;
    1752                 :            :         }
    1753                 :            :         case ParseContext::ANDOR: {
    1754                 :          0 :             auto right = std::move(constructed.back());
    1755                 :          0 :             constructed.pop_back();
    1756                 :          0 :             auto mid = std::move(constructed.back());
    1757                 :          0 :             constructed.pop_back();
    1758   [ #  #  #  # ]:          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
    1759                 :            :             break;
    1760                 :          0 :         }
    1761                 :            :         case ParseContext::THRESH: {
    1762         [ #  # ]:          0 :             if (in.size() < 1) return {};
    1763         [ #  # ]:          0 :             if (in[0] == ',') {
    1764                 :          0 :                 in = in.subspan(1);
    1765   [ #  #  #  #  :          0 :                 to_parse.emplace_back(ParseContext::THRESH, n+1, k);
                   #  # ]
    1766         [ #  # ]:          0 :                 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
    1767                 :          0 :                 script_size += 2;
    1768         [ #  # ]:          0 :             } else if (in[0] == ')') {
    1769   [ #  #  #  # ]:          0 :                 if (k > n) return {};
    1770                 :          0 :                 in = in.subspan(1);
    1771                 :            :                 // Children are constructed in reverse order, so iterate from end to beginning
    1772                 :          0 :                 std::vector<NodeRef<Key>> subs;
    1773   [ #  #  #  # ]:          0 :                 for (int i = 0; i < n; ++i) {
    1774         [ #  # ]:          0 :                     subs.push_back(std::move(constructed.back()));
    1775                 :          0 :                     constructed.pop_back();
    1776                 :          0 :                 }
    1777         [ #  # ]:          0 :                 std::reverse(subs.begin(), subs.end());
    1778   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
                   #  # ]
    1779                 :          0 :             } else {
    1780                 :          0 :                 return {};
    1781                 :            :             }
    1782                 :          0 :             break;
    1783                 :            :         }
    1784                 :            :         case ParseContext::COMMA: {
    1785   [ #  #  #  # ]:          0 :             if (in.size() < 1 || in[0] != ',') return {};
    1786                 :          0 :             in = in.subspan(1);
    1787                 :          0 :             break;
    1788                 :            :         }
    1789                 :            :         case ParseContext::CLOSE_BRACKET: {
    1790   [ #  #  #  # ]:          0 :             if (in.size() < 1 || in[0] != ')') return {};
    1791                 :          0 :             in = in.subspan(1);
    1792                 :          0 :             break;
    1793                 :            :         }
    1794                 :            :         }
    1795                 :            :     }
    1796                 :            : 
    1797                 :            :     // Sanity checks on the produced miniscript
    1798         [ #  # ]:          0 :     assert(constructed.size() == 1);
    1799   [ #  #  #  # ]:          0 :     assert(constructed[0]->ScriptSize() == script_size);
    1800         [ #  # ]:          0 :     if (in.size() > 0) return {};
    1801                 :          0 :     NodeRef<Key> tl_node = std::move(constructed.front());
    1802         [ #  # ]:          0 :     tl_node->DuplicateKeyCheck(ctx);
    1803                 :          0 :     return tl_node;
    1804         [ #  # ]:          0 : }
    1805                 :            : 
    1806                 :            : /** Decode a script into opcode/push pairs.
    1807                 :            :  *
    1808                 :            :  * Construct a vector with one element per opcode in the script, in reverse order.
    1809                 :            :  * Each element is a pair consisting of the opcode, as well as the data pushed by
    1810                 :            :  * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
    1811                 :            :  * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
    1812                 :            :  * respectively, plus OP_VERIFY.
    1813                 :            :  */
    1814                 :            : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
    1815                 :            : 
    1816                 :            : /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
    1817                 :            : std::optional<int64_t> ParseScriptNumber(const Opcode& in);
    1818                 :            : 
    1819                 :            : enum class DecodeContext {
    1820                 :            :     /** A single expression of type B, K, or V. Specifically, this can't be an
    1821                 :            :      * and_v or an expression of type W (a: and s: wrappers). */
    1822                 :            :     SINGLE_BKV_EXPR,
    1823                 :            :     /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
    1824                 :            :      * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
    1825                 :            :     BKV_EXPR,
    1826                 :            :     /** An expression of type W (a: or s: wrappers). */
    1827                 :            :     W_EXPR,
    1828                 :            : 
    1829                 :            :     /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
    1830                 :            :      * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
    1831                 :            :      * with s: */
    1832                 :            :     SWAP,
    1833                 :            :     /** ALT expects the next element to be TOALTSTACK (we must have already read a
    1834                 :            :      * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
    1835                 :            :     ALT,
    1836                 :            :     /** CHECK wraps the top constructed node with c: */
    1837                 :            :     CHECK,
    1838                 :            :     /** DUP_IF wraps the top constructed node with d: */
    1839                 :            :     DUP_IF,
    1840                 :            :     /** VERIFY wraps the top constructed node with v: */
    1841                 :            :     VERIFY,
    1842                 :            :     /** NON_ZERO wraps the top constructed node with j: */
    1843                 :            :     NON_ZERO,
    1844                 :            :     /** ZERO_NOTEQUAL wraps the top constructed node with n: */
    1845                 :            :     ZERO_NOTEQUAL,
    1846                 :            : 
    1847                 :            :     /** MAYBE_AND_V will check if the next part of the script could be a valid
    1848                 :            :      * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
    1849                 :            :      * to decode it and construct the and_v node. This is recursive, to deal with
    1850                 :            :      * multiple and_v nodes inside each other. */
    1851                 :            :     MAYBE_AND_V,
    1852                 :            :     /** AND_V will construct an and_v node from the last two constructed nodes. */
    1853                 :            :     AND_V,
    1854                 :            :     /** AND_B will construct an and_b node from the last two constructed nodes. */
    1855                 :            :     AND_B,
    1856                 :            :     /** ANDOR will construct an andor node from the last three constructed nodes. */
    1857                 :            :     ANDOR,
    1858                 :            :     /** OR_B will construct an or_b node from the last two constructed nodes. */
    1859                 :            :     OR_B,
    1860                 :            :     /** OR_C will construct an or_c node from the last two constructed nodes. */
    1861                 :            :     OR_C,
    1862                 :            :     /** OR_D will construct an or_d node from the last two constructed nodes. */
    1863                 :            :     OR_D,
    1864                 :            : 
    1865                 :            :     /** In a thresh expression, all sub-expressions other than the first are W-type,
    1866                 :            :      * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
    1867                 :            :      * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
    1868                 :            :     THRESH_W,
    1869                 :            :     /** THRESH_E constructs a thresh node from the appropriate number of constructed
    1870                 :            :      * children. */
    1871                 :            :     THRESH_E,
    1872                 :            : 
    1873                 :            :     /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
    1874                 :            :      * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
    1875                 :            :      * a BKV_EXPR and then deal with the next opcode case-by-case. */
    1876                 :            :     ENDIF,
    1877                 :            :     /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
    1878                 :            :      * we could either be in an or_d or an or_c node. We then check for IFDUP to
    1879                 :            :      * distinguish these cases. */
    1880                 :            :     ENDIF_NOTIF,
    1881                 :            :     /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
    1882                 :            :      * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
    1883                 :            :      * OP_NOTIF. */
    1884                 :            :     ENDIF_ELSE,
    1885                 :            : };
    1886                 :            : 
    1887                 :            : //! Parse a miniscript from a bitcoin script
    1888                 :            : template<typename Key, typename Ctx, typename I>
    1889                 :          0 : inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
    1890                 :            : {
    1891                 :            :     // The two integers are used to hold state for thresh()
    1892                 :          0 :     std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
    1893                 :          0 :     std::vector<NodeRef<Key>> constructed;
    1894                 :            : 
    1895                 :            :     // This is the top level, so we assume the type is B
    1896                 :            :     // (in particular, disallowing top level W expressions)
    1897   [ #  #  #  # ]:          0 :     to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
    1898                 :            : 
    1899   [ #  #  #  # ]:          0 :     while (!to_parse.empty()) {
    1900                 :            :         // Exit early if the Miniscript is not going to be valid.
    1901   [ #  #  #  #  :          0 :         if (!constructed.empty() && !constructed.back()->IsValid()) return {};
          #  #  #  #  #  
                #  #  # ]
    1902                 :            : 
    1903                 :            :         // Get the current context we are decoding within
    1904                 :          0 :         auto [cur_context, n, k] = to_parse.back();
    1905                 :          0 :         to_parse.pop_back();
    1906                 :            : 
    1907   [ #  #  #  #  :          0 :         switch(cur_context) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1908                 :            :         case DecodeContext::SINGLE_BKV_EXPR: {
    1909   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    1910                 :            : 
    1911                 :            :             // Constants
    1912   [ #  #  #  # ]:          0 :             if (in[0].first == OP_1) {
    1913                 :          0 :                 ++in;
    1914   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
             #  #  #  # ]
    1915                 :          0 :                 break;
    1916                 :            :             }
    1917   [ #  #  #  # ]:          0 :             if (in[0].first == OP_0) {
    1918                 :          0 :                 ++in;
    1919   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
             #  #  #  # ]
    1920                 :          0 :                 break;
    1921                 :            :             }
    1922                 :            :             // Public keys
    1923   [ #  #  #  # ]:          0 :             if (in[0].second.size() == 33) {
    1924   [ #  #  #  # ]:          0 :                 auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
    1925   [ #  #  #  # ]:          0 :                 if (!key) return {};
    1926                 :          0 :                 ++in;
    1927   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1928                 :          0 :                 break;
    1929         [ #  # ]:          0 :             }
    1930   [ #  #  #  #  :          0 :             if (last - in >= 5 && in[0].first == OP_VERIFY && in[1].first == OP_EQUAL && in[3].first == OP_HASH160 && in[4].first == OP_DUP && in[2].second.size() == 20) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
    1931   [ #  #  #  # ]:          0 :                 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
    1932   [ #  #  #  # ]:          0 :                 if (!key) return {};
    1933                 :          0 :                 in += 5;
    1934   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1935                 :          0 :                 break;
    1936                 :          0 :             }
    1937                 :            :             // Time locks
    1938                 :          0 :             std::optional<int64_t> num;
    1939   [ #  #  #  #  :          0 :             if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1940                 :          0 :                 in += 2;
    1941   [ #  #  #  #  :          0 :                 if (*num < 1 || *num > 0x7FFFFFFFL) return {};
          #  #  #  #  #  
                #  #  # ]
    1942   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
          #  #  #  #  #  
                      # ]
    1943                 :          0 :                 break;
    1944                 :            :             }
    1945   [ #  #  #  #  :          0 :             if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1946                 :          0 :                 in += 2;
    1947   [ #  #  #  #  :          0 :                 if (num < 1 || num > 0x7FFFFFFFL) return {};
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1948   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
          #  #  #  #  #  
                      # ]
    1949                 :          0 :                 break;
    1950                 :            :             }
    1951                 :            :             // Hashes
    1952   [ #  #  #  #  :          0 :             if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && (num = ParseScriptNumber(in[5])) && num == 32 && in[6].first == OP_SIZE) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    1953   [ #  #  #  #  :          0 :                 if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
             #  #  #  # ]
    1954   [ #  #  #  #  :          0 :                     constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
             #  #  #  # ]
    1955                 :          0 :                     in += 7;
    1956                 :          0 :                     break;
    1957   [ #  #  #  #  :          0 :                 } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
             #  #  #  # ]
    1958   [ #  #  #  #  :          0 :                     constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
             #  #  #  # ]
    1959                 :          0 :                     in += 7;
    1960                 :          0 :                     break;
    1961   [ #  #  #  #  :          0 :                 } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
             #  #  #  # ]
    1962   [ #  #  #  #  :          0 :                     constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
             #  #  #  # ]
    1963                 :          0 :                     in += 7;
    1964                 :          0 :                     break;
    1965   [ #  #  #  #  :          0 :                 } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
             #  #  #  # ]
    1966   [ #  #  #  #  :          0 :                     constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
             #  #  #  # ]
    1967                 :          0 :                     in += 7;
    1968                 :          0 :                     break;
    1969                 :            :                 }
    1970                 :          0 :             }
    1971                 :            :             // Multi
    1972   [ #  #  #  #  :          0 :             if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
             #  #  #  # ]
    1973                 :          0 :                 std::vector<Key> keys;
    1974   [ #  #  #  # ]:          0 :                 const auto n = ParseScriptNumber(in[1]);
    1975   [ #  #  #  #  :          0 :                 if (!n || last - in < 3 + *n) return {};
          #  #  #  #  #  
                      # ]
    1976   [ #  #  #  #  :          0 :                 if (*n < 1 || *n > 20) return {};
          #  #  #  #  #  
                #  #  # ]
    1977   [ #  #  #  #  :          0 :                 for (int i = 0; i < *n; ++i) {
                   #  # ]
    1978   [ #  #  #  # ]:          0 :                     if (in[2 + i].second.size() != 33) return {};
    1979   [ #  #  #  # ]:          0 :                     auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
    1980   [ #  #  #  # ]:          0 :                     if (!key) return {};
    1981   [ #  #  #  #  :          0 :                     keys.push_back(std::move(*key));
             #  #  #  # ]
    1982         [ #  # ]:          0 :                 }
    1983   [ #  #  #  #  :          0 :                 const auto k = ParseScriptNumber(in[2 + *n]);
                   #  # ]
    1984   [ #  #  #  #  :          0 :                 if (!k || *k < 1 || *k > *n) return {};
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
    1985         [ #  # ]:          0 :                 in += 3 + *n;
    1986   [ #  #  #  # ]:          0 :                 std::reverse(keys.begin(), keys.end());
    1987   [ #  #  #  #  :          0 :                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
          #  #  #  #  #  
                      # ]
    1988                 :          0 :                 break;
    1989                 :          0 :             }
    1990                 :            :             /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
    1991                 :            :              * than BKV_EXPR, because and_v commutes with these wrappers. For example,
    1992                 :            :              * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
    1993                 :            :             // c: wrapper
    1994   [ #  #  #  # ]:          0 :             if (in[0].first == OP_CHECKSIG) {
    1995                 :          0 :                 ++in;
    1996   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
    1997   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    1998                 :          0 :                 break;
    1999                 :            :             }
    2000                 :            :             // v: wrapper
    2001   [ #  #  #  # ]:          0 :             if (in[0].first == OP_VERIFY) {
    2002                 :          0 :                 ++in;
    2003   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
    2004   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2005                 :          0 :                 break;
    2006                 :            :             }
    2007                 :            :             // n: wrapper
    2008   [ #  #  #  # ]:          0 :             if (in[0].first == OP_0NOTEQUAL) {
    2009                 :          0 :                 ++in;
    2010   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
    2011   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2012                 :          0 :                 break;
    2013                 :            :             }
    2014                 :            :             // Thresh
    2015   [ #  #  #  #  :          0 :             if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
    2016   [ #  #  #  #  :          0 :                 if (*num < 1) return {};
                   #  # ]
    2017                 :          0 :                 in += 2;
    2018   [ #  #  #  #  :          0 :                 to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
                   #  # ]
    2019                 :          0 :                 break;
    2020                 :            :             }
    2021                 :            :             // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
    2022   [ #  #  #  # ]:          0 :             if (in[0].first == OP_ENDIF) {
    2023                 :          0 :                 ++in;
    2024   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
    2025   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
    2026                 :          0 :                 break;
    2027                 :            :             }
    2028                 :            :             /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
    2029                 :            :              * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
    2030                 :            :              * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
    2031                 :            :              * miniscript, while the latter is valid. So we leave the and_v "outside"
    2032                 :            :              * while decoding. */
    2033                 :            :             // and_b
    2034   [ #  #  #  # ]:          0 :             if (in[0].first == OP_BOOLAND) {
    2035                 :          0 :                 ++in;
    2036   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
    2037   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2038   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
    2039                 :          0 :                 break;
    2040                 :            :             }
    2041                 :            :             // or_b
    2042   [ #  #  #  # ]:          0 :             if (in[0].first == OP_BOOLOR) {
    2043                 :          0 :                 ++in;
    2044   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
    2045   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2046   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
    2047                 :          0 :                 break;
    2048                 :            :             }
    2049                 :            :             // Unrecognised expression
    2050                 :          0 :             return {};
    2051                 :            :         }
    2052                 :            :         case DecodeContext::BKV_EXPR: {
    2053   [ #  #  #  # ]:          0 :             to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
    2054   [ #  #  #  # ]:          0 :             to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2055                 :          0 :             break;
    2056                 :            :         }
    2057                 :            :         case DecodeContext::W_EXPR: {
    2058                 :            :             // a: wrapper
    2059   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    2060   [ #  #  #  # ]:          0 :             if (in[0].first == OP_FROMALTSTACK) {
    2061                 :          0 :                 ++in;
    2062   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ALT, -1, -1);
    2063                 :          0 :             } else {
    2064   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
    2065                 :            :             }
    2066   [ #  #  #  # ]:          0 :             to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
    2067                 :          0 :             break;
    2068                 :            :         }
    2069                 :            :         case DecodeContext::MAYBE_AND_V: {
    2070                 :            :             // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
    2071                 :            :             // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
    2072   [ #  #  #  #  :          0 :             if (in < last && in[0].first != OP_IF && in[0].first != OP_ELSE && in[0].first != OP_NOTIF && in[0].first != OP_TOALTSTACK && in[0].first != OP_SWAP) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
    2073   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
    2074                 :            :                 // BKV_EXPR can contain more AND_V nodes
    2075   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
    2076                 :          0 :             }
    2077                 :          0 :             break;
    2078                 :            :         }
    2079                 :            :         case DecodeContext::SWAP: {
    2080   [ #  #  #  #  :          0 :             if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
          #  #  #  #  #  
                #  #  # ]
    2081                 :          0 :             ++in;
    2082   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2083                 :          0 :             break;
    2084                 :            :         }
    2085                 :            :         case DecodeContext::ALT: {
    2086   [ #  #  #  #  :          0 :             if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
          #  #  #  #  #  
                #  #  # ]
    2087                 :          0 :             ++in;
    2088   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2089                 :          0 :             break;
    2090                 :            :         }
    2091                 :            :         case DecodeContext::CHECK: {
    2092   [ #  #  #  # ]:          0 :             if (constructed.empty()) return {};
    2093   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2094                 :          0 :             break;
    2095                 :            :         }
    2096                 :            :         case DecodeContext::DUP_IF: {
    2097   [ #  #  #  # ]:          0 :             if (constructed.empty()) return {};
    2098   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2099                 :          0 :             break;
    2100                 :            :         }
    2101                 :            :         case DecodeContext::VERIFY: {
    2102   [ #  #  #  # ]:          0 :             if (constructed.empty()) return {};
    2103   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2104                 :          0 :             break;
    2105                 :            :         }
    2106                 :            :         case DecodeContext::NON_ZERO: {
    2107   [ #  #  #  # ]:          0 :             if (constructed.empty()) return {};
    2108   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2109                 :          0 :             break;
    2110                 :            :         }
    2111                 :            :         case DecodeContext::ZERO_NOTEQUAL: {
    2112   [ #  #  #  # ]:          0 :             if (constructed.empty()) return {};
    2113   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
             #  #  #  # ]
    2114                 :          0 :             break;
    2115                 :            :         }
    2116                 :            :         case DecodeContext::AND_V: {
    2117   [ #  #  #  # ]:          0 :             if (constructed.size() < 2) return {};
    2118   [ #  #  #  # ]:          0 :             BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
    2119                 :          0 :             break;
    2120                 :            :         }
    2121                 :            :         case DecodeContext::AND_B: {
    2122   [ #  #  #  # ]:          0 :             if (constructed.size() < 2) return {};
    2123   [ #  #  #  # ]:          0 :             BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
    2124                 :          0 :             break;
    2125                 :            :         }
    2126                 :            :         case DecodeContext::OR_B: {
    2127   [ #  #  #  # ]:          0 :             if (constructed.size() < 2) return {};
    2128   [ #  #  #  # ]:          0 :             BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
    2129                 :          0 :             break;
    2130                 :            :         }
    2131                 :            :         case DecodeContext::OR_C: {
    2132   [ #  #  #  # ]:          0 :             if (constructed.size() < 2) return {};
    2133   [ #  #  #  # ]:          0 :             BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
    2134                 :          0 :             break;
    2135                 :            :         }
    2136                 :            :         case DecodeContext::OR_D: {
    2137   [ #  #  #  # ]:          0 :             if (constructed.size() < 2) return {};
    2138   [ #  #  #  # ]:          0 :             BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
    2139                 :          0 :             break;
    2140                 :            :         }
    2141                 :            :         case DecodeContext::ANDOR: {
    2142   [ #  #  #  # ]:          0 :             if (constructed.size() < 3) return {};
    2143                 :          0 :             NodeRef<Key> left = std::move(constructed.back());
    2144                 :          0 :             constructed.pop_back();
    2145                 :          0 :             NodeRef<Key> right = std::move(constructed.back());
    2146                 :          0 :             constructed.pop_back();
    2147                 :          0 :             NodeRef<Key> mid = std::move(constructed.back());
    2148   [ #  #  #  #  :          0 :             constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
             #  #  #  # ]
    2149                 :            :             break;
    2150                 :          0 :         }
    2151                 :            :         case DecodeContext::THRESH_W: {
    2152   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    2153   [ #  #  #  # ]:          0 :             if (in[0].first == OP_ADD) {
    2154                 :          0 :                 ++in;
    2155   [ #  #  #  #  :          0 :                 to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
          #  #  #  #  #  
                #  #  # ]
    2156   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
    2157                 :          0 :             } else {
    2158   [ #  #  #  #  :          0 :                 to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
          #  #  #  #  #  
                #  #  # ]
    2159                 :            :                 // All children of thresh have type modifier d, so cannot be and_v
    2160   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2161                 :            :             }
    2162                 :          0 :             break;
    2163                 :            :         }
    2164                 :            :         case DecodeContext::THRESH_E: {
    2165   [ #  #  #  #  :          0 :             if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
    2166                 :          0 :             std::vector<NodeRef<Key>> subs;
    2167   [ #  #  #  #  :          0 :             for (int i = 0; i < n; ++i) {
             #  #  #  # ]
    2168                 :          0 :                 NodeRef<Key> sub = std::move(constructed.back());
    2169                 :          0 :                 constructed.pop_back();
    2170   [ #  #  #  # ]:          0 :                 subs.push_back(std::move(sub));
    2171                 :          0 :             }
    2172   [ #  #  #  #  :          0 :             constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
          #  #  #  #  #  
                #  #  # ]
    2173                 :            :             break;
    2174                 :          0 :         }
    2175                 :            :         case DecodeContext::ENDIF: {
    2176   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    2177                 :            : 
    2178                 :            :             // could be andor or or_i
    2179   [ #  #  #  # ]:          0 :             if (in[0].first == OP_ELSE) {
    2180                 :          0 :                 ++in;
    2181   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
    2182   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
    2183                 :          0 :             }
    2184                 :            :             // could be j: or d: wrapper
    2185   [ #  #  #  # ]:          0 :             else if (in[0].first == OP_IF) {
    2186   [ #  #  #  #  :          0 :                 if (last - in >= 2 && in[1].first == OP_DUP) {
             #  #  #  # ]
    2187                 :          0 :                     in += 2;
    2188   [ #  #  #  # ]:          0 :                     to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
    2189   [ #  #  #  #  :          0 :                 } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
          #  #  #  #  #  
                #  #  # ]
    2190                 :          0 :                     in += 3;
    2191   [ #  #  #  # ]:          0 :                     to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
    2192                 :          0 :                 }
    2193                 :            :                 else {
    2194                 :          0 :                     return {};
    2195                 :            :                 }
    2196                 :            :             // could be or_c or or_d
    2197   [ #  #  #  # ]:          0 :             } else if (in[0].first == OP_NOTIF) {
    2198                 :          0 :                 ++in;
    2199   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
    2200                 :          0 :             }
    2201                 :            :             else {
    2202                 :          0 :                 return {};
    2203                 :            :             }
    2204                 :          0 :             break;
    2205                 :            :         }
    2206                 :            :         case DecodeContext::ENDIF_NOTIF: {
    2207   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    2208   [ #  #  #  # ]:          0 :             if (in[0].first == OP_IFDUP) {
    2209                 :          0 :                 ++in;
    2210   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
    2211                 :          0 :             } else {
    2212   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
    2213                 :            :             }
    2214                 :            :             // or_c and or_d both require X to have type modifier d so, can't contain and_v
    2215   [ #  #  #  # ]:          0 :             to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2216                 :          0 :             break;
    2217                 :            :         }
    2218                 :            :         case DecodeContext::ENDIF_ELSE: {
    2219   [ #  #  #  # ]:          0 :             if (in >= last) return {};
    2220   [ #  #  #  # ]:          0 :             if (in[0].first == OP_IF) {
    2221                 :          0 :                 ++in;
    2222   [ #  #  #  # ]:          0 :                 BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
    2223   [ #  #  #  # ]:          0 :             } else if (in[0].first == OP_NOTIF) {
    2224                 :          0 :                 ++in;
    2225   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
    2226                 :            :                 // andor requires X to have type modifier d, so it can't be and_v
    2227   [ #  #  #  # ]:          0 :                 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
    2228                 :          0 :             } else {
    2229                 :          0 :                 return {};
    2230                 :            :             }
    2231                 :          0 :             break;
    2232                 :            :         }
    2233                 :            :         }
    2234                 :            :     }
    2235   [ #  #  #  # ]:          0 :     if (constructed.size() != 1) return {};
    2236                 :          0 :     NodeRef<Key> tl_node = std::move(constructed.front());
    2237   [ #  #  #  # ]:          0 :     tl_node->DuplicateKeyCheck(ctx);
    2238                 :            :     // Note that due to how ComputeType works (only assign the type to the node if the
    2239                 :            :     // subs' types are valid) this would fail if any node of tree is badly typed.
    2240   [ #  #  #  #  :          0 :     if (!tl_node->IsValidTopLevel()) return {};
             #  #  #  # ]
    2241                 :          0 :     return tl_node;
    2242                 :          0 : }
    2243                 :            : 
    2244                 :            : } // namespace internal
    2245                 :            : 
    2246                 :            : template<typename Ctx>
    2247                 :          0 : inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
    2248                 :          0 :     return internal::Parse<typename Ctx::Key>(str, ctx);
    2249                 :            : }
    2250                 :            : 
    2251                 :            : template<typename Ctx>
    2252                 :          0 : inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
    2253                 :            :     using namespace internal;
    2254                 :            :     // A too large Script is necessarily invalid, don't bother parsing it.
    2255   [ #  #  #  # ]:          0 :     if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
    2256                 :          0 :     auto decomposed = DecomposeScript(script);
    2257   [ #  #  #  # ]:          0 :     if (!decomposed) return {};
    2258         [ #  # ]:          0 :     auto it = decomposed->begin();
    2259   [ #  #  #  #  :          0 :     auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
                   #  # ]
    2260   [ #  #  #  #  :          0 :     if (!ret) return {};
             #  #  #  # ]
    2261   [ #  #  #  #  :          0 :     if (it != decomposed->end()) return {};
                   #  # ]
    2262                 :          0 :     return ret;
    2263                 :          0 : }
    2264                 :            : 
    2265                 :            : } // namespace miniscript
    2266                 :            : 
    2267                 :            : #endif // BITCOIN_SCRIPT_MINISCRIPT_H

Generated by: LCOV version 1.14