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

Generated by: LCOV version 1.14