LCOV - code coverage report
Current view: top level - src/script - miniscript.h (source / functions) Coverage Total Hit
Test: test_bitcoin_coverage.info Lines: 97.7 % 1238 1210
Test Date: 2025-02-16 04:47:53 Functions: 99.5 % 195 194
Branches: 54.0 % 4419 2388

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

Generated by: LCOV version 2.0-1