Branch data Line data Source code
# 1 : : // Copyright (c) 2019 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 <numeric>
# 10 : : #include <memory>
# 11 : : #include <optional>
# 12 : : #include <string>
# 13 : : #include <vector>
# 14 : :
# 15 : : #include <stdlib.h>
# 16 : : #include <assert.h>
# 17 : :
# 18 : : #include <policy/policy.h>
# 19 : : #include <primitives/transaction.h>
# 20 : : #include <script/script.h>
# 21 : : #include <span.h>
# 22 : : #include <util/spanparsing.h>
# 23 : : #include <util/strencodings.h>
# 24 : : #include <util/string.h>
# 25 : : #include <util/vector.h>
# 26 : :
# 27 : : namespace miniscript {
# 28 : :
# 29 : : /** This type encapsulates the miniscript type system properties.
# 30 : : *
# 31 : : * Every miniscript expression is one of 4 basic types, and additionally has
# 32 : : * a number of boolean type properties.
# 33 : : *
# 34 : : * The basic types are:
# 35 : : * - "B" Base:
# 36 : : * - Takes its inputs from the top of the stack.
# 37 : : * - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack.
# 38 : : * - When dissatisfied, pushes a 0 onto the stack.
# 39 : : * - This is used for most expressions, and required for the top level one.
# 40 : : * - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY.
# 41 : : * - "V" Verify:
# 42 : : * - Takes its inputs from the top of the stack.
# 43 : : * - When satisfactied, pushes nothing.
# 44 : : * - Cannot be dissatisfied.
# 45 : : * - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
# 46 : : * of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
# 47 : : * and OP_EQUAL), or by combining a V fragment under some conditions.
# 48 : : * - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
# 49 : : * - "K" Key:
# 50 : : * - Takes its inputs from the top of the stack.
# 51 : : * - Becomes a B when followed by OP_CHECKSIG.
# 52 : : * - Always pushes a public key onto the stack, for which a signature is to be
# 53 : : * provided to satisfy the expression.
# 54 : : * - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY
# 55 : : * - "W" Wrapped:
# 56 : : * - Takes its input from one below the top of the stack.
# 57 : : * - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below.
# 58 : : * - When dissatisfied, pushes 0 op top of the stack or one below.
# 59 : : * - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK".
# 60 : : * - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG
# 61 : : *
# 62 : : * There a type properties that help reasoning about correctness:
# 63 : : * - "z" Zero-arg:
# 64 : : * - Is known to always consume exactly 0 stack elements.
# 65 : : * - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY
# 66 : : * - "o" One-arg:
# 67 : : * - Is known to always consume exactly 1 stack element.
# 68 : : * - Conflicts with property 'z'
# 69 : : * - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL
# 70 : : * - "n" Nonzero:
# 71 : : * - For every way this expression can be satisfied, a satisfaction exists that never needs
# 72 : : * a zero top stack element.
# 73 : : * - Conflicts with property 'z' and with type 'W'.
# 74 : : * - "d" Dissatisfiable:
# 75 : : * - There is an easy way to construct a dissatisfaction for this expression.
# 76 : : * - Conflicts with type 'V'.
# 77 : : * - "u" Unit:
# 78 : : * - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero).
# 79 : : * - Conflicts with type 'V'.
# 80 : : *
# 81 : : * Additional type properties help reasoning about nonmalleability:
# 82 : : * - "e" Expression:
# 83 : : * - This implies property 'd', but the dissatisfaction is nonmalleable.
# 84 : : * - This generally requires 'e' for all subexpressions which are invoked for that
# 85 : : * dissatifsaction, and property 'f' for the unexecuted subexpressions in that case.
# 86 : : * - Conflicts with type 'V'.
# 87 : : * - "f" Forced:
# 88 : : * - Dissatisfactions (if any) for this expression always involve at least one signature.
# 89 : : * - Is always true for type 'V'.
# 90 : : * - "s" Safe:
# 91 : : * - Satisfactions for this expression always involve at least one signature.
# 92 : : * - "m" Nonmalleable:
# 93 : : * - For every way this expression can be satisfied (which may be none),
# 94 : : * a nonmalleable satisfaction exists.
# 95 : : * - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions
# 96 : : * which are dissatisfied when satisfying the parent.
# 97 : : *
# 98 : : * One type property is an implementation detail:
# 99 : : * - "x" Expensive verify:
# 100 : : * - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG.
# 101 : : * - Not having this property means that it can be converted to a V at no cost (by switching to the
# 102 : : * -VERIFY version of the last opcode).
# 103 : : *
# 104 : : * Five more type properties for representing timelock information. Spend paths
# 105 : : * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together.
# 106 : : * This helps users detect if miniscript does not match the semantic behaviour the
# 107 : : * user expects.
# 108 : : * - "g" Whether the branch contains a relative time timelock
# 109 : : * - "h" Whether the branch contains a relative height timelock
# 110 : : * - "i" Whether the branch contains an absolute time timelock
# 111 : : * - "j" Whether the branch contains an absolute height timelock
# 112 : : * - "k"
# 113 : : * - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock
# 114 : : * of the same type.
# 115 : : * - If the miniscript does not have the "k" property, the miniscript template will not match
# 116 : : * the user expectation of the corresponding spending policy.
# 117 : : * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also
# 118 : : * valid in places where an X, a Y, a Z, an XY, ... is expected.
# 119 : : */
# 120 : : class Type {
# 121 : : //! Internal bitmap of properties (see ""_mst operator for details).
# 122 : : uint32_t m_flags;
# 123 : :
# 124 : : //! Internal constructor used by the ""_mst operator.
# 125 : 228150 : explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
# 126 : :
# 127 : : public:
# 128 : : //! The only way to publicly construct a Type is using this literal operator.
# 129 : : friend constexpr Type operator"" _mst(const char* c, size_t l);
# 130 : :
# 131 : : //! Compute the type with the union of properties.
# 132 : 81160 : constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
# 133 : :
# 134 : : //! Compute the type with the intersection of properties.
# 135 : 7444 : constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
# 136 : :
# 137 : : //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
# 138 : 47184 : constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
# 139 : :
# 140 : : //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
# 141 : 0 : constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
# 142 : :
# 143 : : //! Equality operator.
# 144 : 2556 : constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
# 145 : :
# 146 : : //! The empty type if x is false, itself otherwise.
# 147 [ + + ]: 3462 : constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
# 148 : : };
# 149 : :
# 150 : : //! Literal operator to construct Type objects.
# 151 : 63996 : inline constexpr Type operator"" _mst(const char* c, size_t l) {
# 152 : 63996 : Type typ{0};
# 153 : :
# 154 [ + + ]: 136084 : for (const char *p = c; p < c + l; p++) {
# 155 : 72088 : typ = typ | Type(
# 156 [ + + ]: 72088 : *p == 'B' ? 1 << 0 : // Base type
# 157 [ + + ]: 72088 : *p == 'V' ? 1 << 1 : // Verify type
# 158 [ + + ]: 67558 : *p == 'K' ? 1 << 2 : // Key type
# 159 [ + + ]: 56754 : *p == 'W' ? 1 << 3 : // Wrapped type
# 160 [ + + ]: 50048 : *p == 'z' ? 1 << 4 : // Zero-arg property
# 161 [ + + ]: 47204 : *p == 'o' ? 1 << 5 : // One-arg property
# 162 [ + + ]: 40580 : *p == 'n' ? 1 << 6 : // Nonzero arg property
# 163 [ + + ]: 38446 : *p == 'd' ? 1 << 7 : // Dissatisfiable property
# 164 [ + + ]: 33392 : *p == 'u' ? 1 << 8 : // Unit property
# 165 [ + + ]: 28714 : *p == 'e' ? 1 << 9 : // Expression property
# 166 [ + + ]: 26434 : *p == 'f' ? 1 << 10 : // Forced property
# 167 [ + + ]: 20834 : *p == 's' ? 1 << 11 : // Safe property
# 168 [ + + ]: 16848 : *p == 'm' ? 1 << 12 : // Nonmalleable property
# 169 [ + + ]: 14398 : *p == 'x' ? 1 << 13 : // Expensive verify
# 170 [ + + ]: 11232 : *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
# 171 [ + + ]: 8932 : *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
# 172 [ + + ]: 7384 : *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
# 173 [ + + ]: 5844 : *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
# 174 [ + - ]: 4224 : *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
# 175 : 2626 : (throw std::logic_error("Unknown character in _mst literal"), 0)
# 176 : 72088 : );
# 177 : 72088 : }
# 178 : :
# 179 : 63996 : return typ;
# 180 : 63996 : }
# 181 : :
# 182 : : template<typename Key> struct Node;
# 183 : : template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
# 184 : :
# 185 : : //! Construct a miniscript node as a shared_ptr.
# 186 : : template<typename Key, typename... Args>
# 187 : 2054 : NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
# 188 : :
# 189 : : //! The different node types in miniscript.
# 190 : : enum class Fragment {
# 191 : : JUST_0, //!< OP_0
# 192 : : JUST_1, //!< OP_1
# 193 : : PK_K, //!< [key]
# 194 : : PK_H, //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY
# 195 : : OLDER, //!< [n] OP_CHECKSEQUENCEVERIFY
# 196 : : AFTER, //!< [n] OP_CHECKLOCKTIMEVERIFY
# 197 : : SHA256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL
# 198 : : HASH256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL
# 199 : : RIPEMD160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL
# 200 : : HASH160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL
# 201 : : WRAP_A, //!< OP_TOALTSTACK [X] OP_FROMALTSTACK
# 202 : : WRAP_S, //!< OP_SWAP [X]
# 203 : : WRAP_C, //!< [X] OP_CHECKSIG
# 204 : : WRAP_D, //!< OP_DUP OP_IF [X] OP_ENDIF
# 205 : : WRAP_V, //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X)
# 206 : : WRAP_J, //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF
# 207 : : WRAP_N, //!< [X] OP_0NOTEQUAL
# 208 : : AND_V, //!< [X] [Y]
# 209 : : AND_B, //!< [X] [Y] OP_BOOLAND
# 210 : : OR_B, //!< [X] [Y] OP_BOOLOR
# 211 : : OR_C, //!< [X] OP_NOTIF [Y] OP_ENDIF
# 212 : : OR_D, //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
# 213 : : OR_I, //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
# 214 : : ANDOR, //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
# 215 : : THRESH, //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
# 216 : : MULTI, //!< [k] [key_n]* [n] OP_CHECKMULTISIG
# 217 : : // AND_N(X,Y) is represented as ANDOR(X,Y,0)
# 218 : : // WRAP_T(X) is represented as AND_V(X,1)
# 219 : : // WRAP_L(X) is represented as OR_I(0,X)
# 220 : : // WRAP_U(X) is represented as OR_I(X,0)
# 221 : : };
# 222 : :
# 223 : :
# 224 : : namespace internal {
# 225 : :
# 226 : : //! Helper function for Node::CalcType.
# 227 : : Type ComputeType(Fragment nodetype, 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);
# 228 : :
# 229 : : //! Helper function for Node::CalcScriptLen.
# 230 : : size_t ComputeScriptLen(Fragment nodetype, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
# 231 : :
# 232 : : //! A helper sanitizer/checker for the output of CalcType.
# 233 : : Type SanitizeType(Type x);
# 234 : :
# 235 : : //! Class whose objects represent the maximum of a list of integers.
# 236 : : template<typename I>
# 237 : : struct MaxInt {
# 238 : : const bool valid;
# 239 : : const I value;
# 240 : :
# 241 : 3096 : MaxInt() : valid(false), value(0) {}
# 242 : 5572 : MaxInt(I val) : valid(true), value(val) {}
# 243 : :
# 244 : 2740 : friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
# 245 [ + + ][ + + ]: 2740 : if (!a.valid || !b.valid) return {};
# 246 : 1932 : return a.value + b.value;
# 247 : 2740 : }
# 248 : :
# 249 : 1232 : friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
# 250 [ + + ]: 1232 : if (!a.valid) return b;
# 251 [ + + ]: 806 : if (!b.valid) return a;
# 252 : 432 : return std::max(a.value, b.value);
# 253 : 806 : }
# 254 : : };
# 255 : :
# 256 : : struct Ops {
# 257 : : //! Non-push opcodes.
# 258 : : uint32_t count;
# 259 : : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
# 260 : : MaxInt<uint32_t> sat;
# 261 : : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
# 262 : : MaxInt<uint32_t> dsat;
# 263 : :
# 264 : 2054 : Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
# 265 : : };
# 266 : :
# 267 : : struct StackSize {
# 268 : : //! Maximum stack size to satisfy;
# 269 : : MaxInt<uint32_t> sat;
# 270 : : //! Maximum stack size to dissatisfy;
# 271 : : MaxInt<uint32_t> dsat;
# 272 : :
# 273 : 1764 : StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
# 274 : : };
# 275 : :
# 276 : : } // namespace internal
# 277 : :
# 278 : : //! A node in a miniscript expression.
# 279 : : template<typename Key>
# 280 : : struct Node {
# 281 : : //! What node type this node is.
# 282 : : const Fragment nodetype;
# 283 : : //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
# 284 : : const uint32_t k = 0;
# 285 : : //! The keys used by this expression (only for PK_K/PK_H/MULTI)
# 286 : : const std::vector<Key> keys;
# 287 : : //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
# 288 : : const std::vector<unsigned char> data;
# 289 : : //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
# 290 : : const std::vector<NodeRef<Key>> subs;
# 291 : :
# 292 : : private:
# 293 : : //! Cached ops counts.
# 294 : : const internal::Ops ops;
# 295 : : //! Cached stack size bounds.
# 296 : : const internal::StackSize ss;
# 297 : : //! Cached expression type (computed by CalcType and fed through SanitizeType).
# 298 : : const Type typ;
# 299 : : //! Cached script length (computed by CalcScriptLen).
# 300 : : const size_t scriptlen;
# 301 : :
# 302 : : //! Compute the length of the script for this miniscript (including children).
# 303 : 2054 : size_t CalcScriptLen() const {
# 304 : 2054 : size_t subsize = 0;
# 305 [ + + ]: 2054 : for (const auto& sub : subs) {
# 306 : 1740 : subsize += sub->ScriptSize();
# 307 : 1740 : }
# 308 [ + + ]: 2054 : Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
# 309 : 2054 : return internal::ComputeScriptLen(nodetype, sub0type, subsize, k, subs.size(), keys.size());
# 310 : 2054 : }
# 311 : :
# 312 : : /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
# 313 : : *
# 314 : : * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
# 315 : : * result can be thought of as first using downfn to compute a "state" for each node,
# 316 : : * from the root down to the leaves. Then upfn is used to compute a "result" for each
# 317 : : * node, from the leaves back up to the root, which is then returned. In the actual
# 318 : : * implementation, both functions are invoked in an interleaved fashion, performing a
# 319 : : * depth-first traversal of the tree.
# 320 : : *
# 321 : : * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
# 322 : : * - root is the state of the root node, of type State.
# 323 : : * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
# 324 : : * node, its state, and an index of one of its children, computes the state of that
# 325 : : * child. It can modify the state. Children of a given node will have downfn()
# 326 : : * called in order.
# 327 : : * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
# 328 : : * which given a node, its state, and a Span of the results of its children,
# 329 : : * computes the result of the node. If std::nullopt is returned by upfn,
# 330 : : * TreeEvalMaybe() immediately returns std::nullopt.
# 331 : : * The return value of TreeEvalMaybe is the result of the root node.
# 332 : : */
# 333 : : template<typename Result, typename State, typename DownFn, typename UpFn>
# 334 : : std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
# 335 : 252 : {
# 336 : : /** Entries of the explicit stack tracked in this algorithm. */
# 337 : 252 : struct StackElem
# 338 : 252 : {
# 339 : 252 : const Node& node; //!< The node being evaluated.
# 340 : 252 : size_t expanded; //!< How many children of this node have been expanded.
# 341 : 252 : State state; //!< The state for that node.
# 342 : :
# 343 : 252 : StackElem(const Node& node_, size_t exp_, State&& state_) :
# 344 : 1796 : node(node_), expanded(exp_), state(std::move(state_)) {}
# 345 : 252 : };
# 346 : : /* Stack of tree nodes being explored. */
# 347 : 252 : std::vector<StackElem> stack;
# 348 : : /* Results of subtrees so far. Their order and mapping to tree nodes
# 349 : : * is implicitly defined by stack. */
# 350 : 252 : std::vector<Result> results;
# 351 : 252 : stack.emplace_back(*this, 0, std::move(root_state));
# 352 : :
# 353 : : /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
# 354 : : * State variables are omitted for simplicity.
# 355 : : *
# 356 : : * First: stack=[(A,0)] results=[]
# 357 : : * stack=[(A,1),(B,0)] results=[]
# 358 : : * stack=[(A,1)] results=[B]
# 359 : : * stack=[(A,2),(C,0)] results=[B]
# 360 : : * stack=[(A,2),(C,1),(D,0)] results=[B]
# 361 : : * stack=[(A,2),(C,1)] results=[B,D]
# 362 : : * stack=[(A,2),(C,2),(E,0)] results=[B,D]
# 363 : : * stack=[(A,2),(C,2)] results=[B,D,E]
# 364 : : * stack=[(A,2)] results=[B,C]
# 365 : : * stack=[(A,3),(F,0)] results=[B,C]
# 366 : : * stack=[(A,3)] results=[B,C,F]
# 367 : : * Final: stack=[] results=[A]
# 368 : : */
# 369 [ + + ]: 3592 : while (stack.size()) {
# 370 : 3340 : const Node& node = stack.back().node;
# 371 [ + + ]: 3340 : if (stack.back().expanded < node.subs.size()) {
# 372 : : /* We encounter a tree node with at least one unexpanded child.
# 373 : : * Expand it. By the time we hit this node again, the result of
# 374 : : * that child (and all earlier children) will be at the end of `results`. */
# 375 : 1544 : size_t child_index = stack.back().expanded++;
# 376 : 1544 : State child_state = downfn(stack.back().state, node, child_index);
# 377 : 1544 : stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
# 378 : 1544 : continue;
# 379 : 1544 : }
# 380 : : // Invoke upfn with the last node.subs.size() elements of results as input.
# 381 : 1796 : assert(results.size() >= node.subs.size());
# 382 : 0 : std::optional<Result> result{upfn(std::move(stack.back().state), node,
# 383 : 1796 : Span<Result>{results}.last(node.subs.size()))};
# 384 : : // If evaluation returns std::nullopt, abort immediately.
# 385 [ - + ]: 1796 : if (!result) return {};
# 386 : : // Replace the last node.subs.size() elements of results with the new result.
# 387 : 1796 : results.erase(results.end() - node.subs.size(), results.end());
# 388 : 1796 : results.push_back(std::move(*result));
# 389 : 1796 : stack.pop_back();
# 390 : 1796 : }
# 391 : : // The final remaining results element is the root result, return it.
# 392 : 252 : assert(results.size() == 1);
# 393 : 0 : return std::move(results[0]);
# 394 : 252 : }
# 395 : :
# 396 : : /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
# 397 : : template<typename Result, typename State, typename DownFn, typename UpFn>
# 398 : : Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
# 399 : 252 : {
# 400 : : // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
# 401 : : // unconditionally dereference the result (it cannot be std::nullopt).
# 402 : 252 : return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
# 403 : 252 : std::forward<DownFn>(downfn),
# 404 : 1796 : [&upfn](State&& state, const Node& node, Span<Result> subs) {
# 405 : 1796 : Result res{upfn(std::move(state), node, subs)};
# 406 : 1796 : return std::optional<Result>(std::move(res));
# 407 : 1796 : }
# 408 : 252 : ));
# 409 : 252 : }
# 410 : :
# 411 : : //! Compute the type for this miniscript.
# 412 : 2054 : Type CalcType() const {
# 413 : 2054 : using namespace internal;
# 414 : :
# 415 : : // THRESH has a variable number of subexpressions
# 416 : 2054 : std::vector<Type> sub_types;
# 417 [ + + ]: 2054 : if (nodetype == Fragment::THRESH) {
# 418 [ + + ]: 92 : for (const auto& sub : subs) sub_types.push_back(sub->GetType());
# 419 : 32 : }
# 420 : : // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
# 421 [ + + ]: 2054 : Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
# 422 [ + + ]: 2054 : Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
# 423 [ + + ]: 2054 : Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
# 424 : :
# 425 : 2054 : return SanitizeType(ComputeType(nodetype, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
# 426 : 2054 : }
# 427 : :
# 428 : : public:
# 429 : : template<typename Ctx>
# 430 : : CScript ToScript(const Ctx& ctx) const
# 431 : 252 : {
# 432 : : // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
# 433 : : // The State is a boolean: whether or not the node's script expansion is followed
# 434 : : // by an OP_VERIFY (which may need to be combined with the last script opcode).
# 435 : 1544 : auto downfn = [](bool verify, const Node& node, size_t index) {
# 436 : : // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
# 437 [ + + ]: 1544 : if (node.nodetype == Fragment::WRAP_V) return true;
# 438 : : // The subexpression of WRAP_S, and the last subexpression of AND_V
# 439 : : // inherit the followed-by-OP_VERIFY property from the parent.
# 440 [ + + ]: 1372 : if (node.nodetype == Fragment::WRAP_S ||
# 441 [ + + ][ + + ]: 1372 : (node.nodetype == Fragment::AND_V && index == 1)) return verify;
# 442 : 1212 : return false;
# 443 : 1372 : };
# 444 : : // The upward function computes for a node, given its followed-by-OP_VERIFY status
# 445 : : // and the CScripts of its child nodes, the CScript of the node.
# 446 : 1796 : auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
# 447 [ - + ]: 1796 : switch (node.nodetype) {
# 448 [ + + ]: 88 : case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
# 449 [ + + ]: 52 : case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
# 450 [ + + ]: 88 : case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
# 451 [ + + ]: 132 : case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
# 452 [ + + ][ + + ]: 48 : case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
# 453 [ + + ][ + + ]: 16 : case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
# 454 [ + + ][ + + ]: 28 : case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
# 455 [ + + ][ + + ]: 12 : case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
# 456 [ + + ]: 92 : case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
# 457 [ + + ]: 20 : case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
# 458 [ + + ][ - + ]: 108 : case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
# 459 [ + + ]: 8 : case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
# 460 [ + + ]: 172 : case Fragment::WRAP_V: {
# 461 [ + + ]: 172 : if (node.subs[0]->GetType() << "x"_mst) {
# 462 : 128 : return BuildScript(std::move(subs[0]), OP_VERIFY);
# 463 : 128 : } else {
# 464 : 44 : return std::move(subs[0]);
# 465 : 44 : }
# 466 : 172 : }
# 467 [ + + ]: 20 : case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
# 468 [ + + ]: 28 : case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
# 469 [ + + ]: 156 : case Fragment::JUST_1: return BuildScript(OP_1);
# 470 [ + + ]: 176 : case Fragment::JUST_0: return BuildScript(OP_0);
# 471 [ + + ]: 140 : case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
# 472 [ + + ]: 32 : case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
# 473 [ + + ]: 20 : case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
# 474 [ + + ]: 32 : case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
# 475 [ + + ]: 16 : case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
# 476 [ + + ]: 172 : case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
# 477 [ + + ]: 60 : case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
# 478 [ + + ]: 48 : case Fragment::MULTI: {
# 479 : 48 : CScript script = BuildScript(node.k);
# 480 [ + + ]: 92 : for (const auto& key : node.keys) {
# 481 : 92 : script = BuildScript(std::move(script), ctx.ToPKBytes(key));
# 482 : 92 : }
# 483 [ + + ]: 48 : return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
# 484 : 172 : }
# 485 [ + + ]: 32 : case Fragment::THRESH: {
# 486 : 32 : CScript script = std::move(subs[0]);
# 487 [ + + ]: 92 : for (size_t i = 1; i < subs.size(); ++i) {
# 488 : 60 : script = BuildScript(std::move(script), subs[i], OP_ADD);
# 489 : 60 : }
# 490 [ - + ]: 32 : return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
# 491 : 172 : }
# 492 : 1796 : }
# 493 : 0 : assert(false);
# 494 : 0 : return {};
# 495 : 1796 : };
# 496 : 252 : return TreeEval<CScript>(false, downfn, upfn);
# 497 : 252 : }
# 498 : :
# 499 : : template<typename CTx>
# 500 : : bool ToString(const CTx& ctx, std::string& ret) const {
# 501 : : // To construct the std::string representation for a Miniscript object, we use
# 502 : : // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
# 503 : : // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
# 504 : : auto downfn = [](bool, const Node& node, size_t) {
# 505 : : return (node.nodetype == Fragment::WRAP_A || node.nodetype == Fragment::WRAP_S ||
# 506 : : node.nodetype == Fragment::WRAP_D || node.nodetype == Fragment::WRAP_V ||
# 507 : : node.nodetype == Fragment::WRAP_J || node.nodetype == Fragment::WRAP_N ||
# 508 : : node.nodetype == Fragment::WRAP_C ||
# 509 : : (node.nodetype == Fragment::AND_V && node.subs[1]->nodetype == Fragment::JUST_1) ||
# 510 : : (node.nodetype == Fragment::OR_I && node.subs[0]->nodetype == Fragment::JUST_0) ||
# 511 : : (node.nodetype == Fragment::OR_I && node.subs[1]->nodetype == Fragment::JUST_0));
# 512 : : };
# 513 : : // The upward function computes for a node, given whether its parent is a wrapper,
# 514 : : // and the string representations of its child nodes, the string representation of the node.
# 515 : : auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
# 516 : : std::string ret = wrapped ? ":" : "";
# 517 : :
# 518 : : switch (node.nodetype) {
# 519 : : case Fragment::WRAP_A: return "a" + std::move(subs[0]);
# 520 : : case Fragment::WRAP_S: return "s" + std::move(subs[0]);
# 521 : : case Fragment::WRAP_C:
# 522 : : if (node.subs[0]->nodetype == Fragment::PK_K) {
# 523 : : // pk(K) is syntactic sugar for c:pk_k(K)
# 524 : : std::string key_str;
# 525 : : if (!ctx.ToString(node.subs[0]->keys[0], key_str)) return {};
# 526 : : return std::move(ret) + "pk(" + std::move(key_str) + ")";
# 527 : : }
# 528 : : if (node.subs[0]->nodetype == Fragment::PK_H) {
# 529 : : // pkh(K) is syntactic sugar for c:pk_h(K)
# 530 : : std::string key_str;
# 531 : : if (!ctx.ToString(node.subs[0]->keys[0], key_str)) return {};
# 532 : : return std::move(ret) + "pkh(" + std::move(key_str) + ")";
# 533 : : }
# 534 : : return "c" + std::move(subs[0]);
# 535 : : case Fragment::WRAP_D: return "d" + std::move(subs[0]);
# 536 : : case Fragment::WRAP_V: return "v" + std::move(subs[0]);
# 537 : : case Fragment::WRAP_J: return "j" + std::move(subs[0]);
# 538 : : case Fragment::WRAP_N: return "n" + std::move(subs[0]);
# 539 : : case Fragment::AND_V:
# 540 : : // t:X is syntactic sugar for and_v(X,1).
# 541 : : if (node.subs[1]->nodetype == Fragment::JUST_1) return "t" + std::move(subs[0]);
# 542 : : break;
# 543 : : case Fragment::OR_I:
# 544 : : if (node.subs[0]->nodetype == Fragment::JUST_0) return "l" + std::move(subs[1]);
# 545 : : if (node.subs[1]->nodetype == Fragment::JUST_0) return "u" + std::move(subs[0]);
# 546 : : break;
# 547 : : default: break;
# 548 : : }
# 549 : : switch (node.nodetype) {
# 550 : : case Fragment::PK_K: {
# 551 : : std::string key_str;
# 552 : : if (!ctx.ToString(node.keys[0], key_str)) return {};
# 553 : : return std::move(ret) + "pk_k(" + std::move(key_str) + ")";
# 554 : : }
# 555 : : case Fragment::PK_H: {
# 556 : : std::string key_str;
# 557 : : if (!ctx.ToString(node.keys[0], key_str)) return {};
# 558 : : return std::move(ret) + "pk_h(" + std::move(key_str) + ")";
# 559 : : }
# 560 : : case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
# 561 : : case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
# 562 : : case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
# 563 : : case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
# 564 : : case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
# 565 : : case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
# 566 : : case Fragment::JUST_1: return std::move(ret) + "1";
# 567 : : case Fragment::JUST_0: return std::move(ret) + "0";
# 568 : : case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 569 : : case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 570 : : case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 571 : : case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 572 : : case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 573 : : case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 574 : : case Fragment::ANDOR:
# 575 : : // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
# 576 : : if (node.subs[2]->nodetype == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
# 577 : : return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
# 578 : : case Fragment::MULTI: {
# 579 : : auto str = std::move(ret) + "multi(" + ::ToString(node.k);
# 580 : : for (const auto& key : node.keys) {
# 581 : : std::string key_str;
# 582 : : if (!ctx.ToString(key, key_str)) return {};
# 583 : : str += "," + std::move(key_str);
# 584 : : }
# 585 : : return std::move(str) + ")";
# 586 : : }
# 587 : : case Fragment::THRESH: {
# 588 : : auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
# 589 : : for (auto& sub : subs) {
# 590 : : str += "," + std::move(sub);
# 591 : : }
# 592 : : return std::move(str) + ")";
# 593 : : }
# 594 : : default: assert(false);
# 595 : : }
# 596 : : return ""; // Should never be reached.
# 597 : : };
# 598 : :
# 599 : : auto res = TreeEvalMaybe<std::string>(false, downfn, upfn);
# 600 : : if (res.has_value()) ret = std::move(*res);
# 601 : : return res.has_value();
# 602 : : }
# 603 : :
# 604 : 2054 : internal::Ops CalcOps() const {
# 605 [ - + ]: 2054 : switch (nodetype) {
# 606 [ + + ]: 234 : case Fragment::JUST_1: return {0, 0, {}};
# 607 [ + + ]: 216 : case Fragment::JUST_0: return {0, {}, 0};
# 608 [ + + ]: 98 : case Fragment::PK_K: return {0, 0, 0};
# 609 [ + + ]: 52 : case Fragment::PK_H: return {3, 0, 0};
# 610 [ + + ]: 88 : case Fragment::OLDER:
# 611 [ + + ]: 226 : case Fragment::AFTER: return {1, 0, {}};
# 612 [ + + ]: 48 : case Fragment::SHA256:
# 613 [ + + ]: 64 : case Fragment::RIPEMD160:
# 614 [ + + ]: 92 : case Fragment::HASH256:
# 615 [ + + ]: 104 : case Fragment::HASH160: return {4, 0, {}};
# 616 [ + + ]: 154 : case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
# 617 [ + + ]: 40 : case Fragment::AND_B: {
# 618 : 40 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
# 619 : 40 : const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
# 620 : 40 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
# 621 : 40 : return {count, sat, dsat};
# 622 : 92 : }
# 623 [ + + ]: 32 : case Fragment::OR_B: {
# 624 : 32 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
# 625 : 32 : const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
# 626 : 32 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
# 627 : 32 : return {count, sat, dsat};
# 628 : 92 : }
# 629 [ + + ]: 40 : case Fragment::OR_D: {
# 630 : 40 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
# 631 : 40 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
# 632 : 40 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
# 633 : 40 : return {count, sat, dsat};
# 634 : 92 : }
# 635 [ + + ]: 24 : case Fragment::OR_C: {
# 636 : 24 : const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
# 637 : 24 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
# 638 : 24 : return {count, sat, {}};
# 639 : 92 : }
# 640 [ + + ]: 180 : case Fragment::OR_I: {
# 641 : 180 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
# 642 : 180 : const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
# 643 : 180 : const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
# 644 : 180 : return {count, sat, dsat};
# 645 : 92 : }
# 646 [ + + ]: 68 : case Fragment::ANDOR: {
# 647 : 68 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
# 648 : 68 : const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
# 649 : 68 : const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
# 650 : 68 : return {count, sat, dsat};
# 651 : 92 : }
# 652 [ + + ]: 50 : case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
# 653 [ + + ]: 22 : case Fragment::WRAP_S:
# 654 [ + + ]: 134 : case Fragment::WRAP_C:
# 655 [ + + ]: 162 : case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
# 656 [ + + ]: 128 : case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
# 657 [ + + ]: 8 : case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
# 658 [ + + ]: 20 : case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
# 659 [ + + ]: 186 : case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
# 660 [ + + ]: 32 : case Fragment::THRESH: {
# 661 : 32 : uint32_t count = 0;
# 662 : 32 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
# 663 [ + + ]: 92 : for (const auto& sub : subs) {
# 664 : 92 : count += sub->ops.count + 1;
# 665 : 92 : auto next_sats = Vector(sats[0] + sub->ops.dsat);
# 666 [ + + ]: 184 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
# 667 : 92 : next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
# 668 : 92 : sats = std::move(next_sats);
# 669 : 92 : }
# 670 : 32 : assert(k <= sats.size());
# 671 : 0 : return {count, sats[k], sats[0]};
# 672 : 134 : }
# 673 : 2054 : }
# 674 : 0 : assert(false);
# 675 : 0 : return {0, {}, {}};
# 676 : 2054 : }
# 677 : :
# 678 : 2054 : internal::StackSize CalcStackSize() const {
# 679 [ - + ]: 2054 : switch (nodetype) {
# 680 [ + + ]: 216 : case Fragment::JUST_0: return {{}, 0};
# 681 [ + + ]: 234 : case Fragment::JUST_1:
# 682 [ + + ]: 322 : case Fragment::OLDER:
# 683 [ + + ]: 460 : case Fragment::AFTER: return {0, {}};
# 684 [ + + ]: 98 : case Fragment::PK_K: return {1, 1};
# 685 [ + + ]: 52 : case Fragment::PK_H: return {2, 2};
# 686 [ + + ]: 48 : case Fragment::SHA256:
# 687 [ + + ]: 64 : case Fragment::RIPEMD160:
# 688 [ + + ]: 92 : case Fragment::HASH256:
# 689 [ + + ]: 104 : case Fragment::HASH160: return {1, {}};
# 690 [ + + ]: 68 : case Fragment::ANDOR: {
# 691 : 68 : const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
# 692 : 68 : const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
# 693 : 68 : return {sat, dsat};
# 694 : 92 : }
# 695 [ + + ]: 154 : case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
# 696 [ + + ]: 40 : case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
# 697 [ + + ]: 32 : case Fragment::OR_B: {
# 698 : 32 : const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
# 699 : 32 : const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
# 700 : 32 : return {sat, dsat};
# 701 : 92 : }
# 702 [ + + ]: 24 : case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
# 703 [ + + ]: 40 : case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
# 704 [ + + ]: 180 : case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
# 705 [ + + ]: 50 : case Fragment::MULTI: return {k + 1, k + 1};
# 706 [ + + ]: 128 : case Fragment::WRAP_A:
# 707 [ + + ]: 156 : case Fragment::WRAP_N:
# 708 [ + + ]: 178 : case Fragment::WRAP_S:
# 709 [ + + ]: 290 : case Fragment::WRAP_C: return subs[0]->ss;
# 710 [ + + ]: 8 : case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
# 711 [ + + ]: 186 : case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
# 712 [ + + ]: 20 : case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
# 713 [ + + ]: 32 : case Fragment::THRESH: {
# 714 : 32 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
# 715 [ + + ]: 92 : for (const auto& sub : subs) {
# 716 : 92 : auto next_sats = Vector(sats[0] + sub->ss.dsat);
# 717 [ + + ]: 184 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
# 718 : 92 : next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
# 719 : 92 : sats = std::move(next_sats);
# 720 : 92 : }
# 721 : 32 : assert(k <= sats.size());
# 722 : 0 : return {sats[k], sats[0]};
# 723 : 178 : }
# 724 : 2054 : }
# 725 : 0 : assert(false);
# 726 : 0 : return {{}, {}};
# 727 : 2054 : }
# 728 : :
# 729 : : public:
# 730 : : //! Return the size of the script for this expression (faster than ToScript().size()).
# 731 : 4370 : size_t ScriptSize() const { return scriptlen; }
# 732 : :
# 733 : : //! Return the maximum number of ops needed to satisfy this script non-malleably.
# 734 : 126 : uint32_t GetOps() const { return ops.count + ops.sat.value; }
# 735 : :
# 736 : : //! Check the ops limit of this script against the consensus limit.
# 737 : : bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
# 738 : :
# 739 : : /** Return the maximum number of stack elements needed to satisfy this script non-malleably, including
# 740 : : * the script push. */
# 741 : 126 : uint32_t GetStackSize() const { return ss.sat.value + 1; }
# 742 : :
# 743 : : //! Check the maximum stack size for this script against the policy limit.
# 744 : : bool CheckStackSize() const { return GetStackSize() - 1 <= MAX_STANDARD_P2WSH_STACK_ITEMS; }
# 745 : :
# 746 : : //! Return the expression type.
# 747 : 6574 : Type GetType() const { return typ; }
# 748 : :
# 749 : : //! Check whether this node is valid at all.
# 750 [ + + ][ + - ]: 2556 : bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
# 751 : :
# 752 : : //! Check whether this node is valid as a script on its own.
# 753 [ + + ][ + - ]: 432 : bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
# 754 : :
# 755 : : //! Check whether this script can always be satisfied in a non-malleable way.
# 756 : 126 : bool IsNonMalleable() const { return GetType() << "m"_mst; }
# 757 : :
# 758 : : //! Check whether this script always needs a signature.
# 759 : 126 : bool NeedsSignature() const { return GetType() << "s"_mst; }
# 760 : :
# 761 : : //! Do all sanity checks.
# 762 : : bool IsSane() const { return IsValid() && GetType() << "mk"_mst && CheckOpsLimit() && CheckStackSize(); }
# 763 : :
# 764 : : //! Check whether this node is safe as a script on its own.
# 765 : : bool IsSaneTopLevel() const { return IsValidTopLevel() && IsSane() && NeedsSignature(); }
# 766 : :
# 767 : : //! Equality testing.
# 768 : : bool operator==(const Node<Key>& arg) const
# 769 : : {
# 770 : : if (nodetype != arg.nodetype) return false;
# 771 : : if (k != arg.k) return false;
# 772 : : if (data != arg.data) return false;
# 773 : : if (keys != arg.keys) return false;
# 774 : : if (subs.size() != arg.subs.size()) return false;
# 775 : : for (size_t i = 0; i < subs.size(); ++i) {
# 776 : : if (!(*subs[i] == *arg.subs[i])) return false;
# 777 : : }
# 778 : : assert(scriptlen == arg.scriptlen);
# 779 : : assert(typ == arg.typ);
# 780 : : return true;
# 781 : : }
# 782 : :
# 783 : : // Constructors with various argument combinations.
# 784 : : Node(Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : nodetype(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 785 : 104 : Node(Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : nodetype(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 786 : : Node(Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : nodetype(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 787 : 200 : Node(Fragment nt, std::vector<Key> key, uint32_t val = 0) : nodetype(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 788 : 1074 : Node(Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : nodetype(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 789 : 676 : Node(Fragment nt, uint32_t val = 0) : nodetype(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
# 790 : : };
# 791 : :
# 792 : : namespace internal {
# 793 : :
# 794 : : enum class ParseContext {
# 795 : : /** An expression which may be begin with wrappers followed by a colon. */
# 796 : : WRAPPED_EXPR,
# 797 : : /** A miniscript expression which does not begin with wrappers. */
# 798 : : EXPR,
# 799 : :
# 800 : : /** SWAP wraps the top constructed node with s: */
# 801 : : SWAP,
# 802 : : /** ALT wraps the top constructed node with a: */
# 803 : : ALT,
# 804 : : /** CHECK wraps the top constructed node with c: */
# 805 : : CHECK,
# 806 : : /** DUP_IF wraps the top constructed node with d: */
# 807 : : DUP_IF,
# 808 : : /** VERIFY wraps the top constructed node with v: */
# 809 : : VERIFY,
# 810 : : /** NON_ZERO wraps the top constructed node with j: */
# 811 : : NON_ZERO,
# 812 : : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
# 813 : : ZERO_NOTEQUAL,
# 814 : : /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
# 815 : : WRAP_U,
# 816 : : /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
# 817 : : WRAP_T,
# 818 : :
# 819 : : /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
# 820 : : AND_N,
# 821 : : /** AND_V will construct an and_v node from the last two constructed nodes. */
# 822 : : AND_V,
# 823 : : /** AND_B will construct an and_b node from the last two constructed nodes. */
# 824 : : AND_B,
# 825 : : /** ANDOR will construct an andor node from the last three constructed nodes. */
# 826 : : ANDOR,
# 827 : : /** OR_B will construct an or_b node from the last two constructed nodes. */
# 828 : : OR_B,
# 829 : : /** OR_C will construct an or_c node from the last two constructed nodes. */
# 830 : : OR_C,
# 831 : : /** OR_D will construct an or_d node from the last two constructed nodes. */
# 832 : : OR_D,
# 833 : : /** OR_I will construct an or_i node from the last two constructed nodes. */
# 834 : : OR_I,
# 835 : :
# 836 : : /** THRESH will read a wrapped expression, and then look for a COMMA. If
# 837 : : * no comma follows, it will construct a thresh node from the appropriate
# 838 : : * number of constructed children. Otherwise, it will recurse with another
# 839 : : * THRESH. */
# 840 : : THRESH,
# 841 : :
# 842 : : /** COMMA expects the next element to be ',' and fails if not. */
# 843 : : COMMA,
# 844 : : /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
# 845 : : CLOSE_BRACKET,
# 846 : : };
# 847 : :
# 848 : : int FindNextChar(Span<const char> in, const char m);
# 849 : :
# 850 : : /** Parse a key string ending with a ')' or ','. */
# 851 : : template<typename Key, typename Ctx>
# 852 : : std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
# 853 : 80 : {
# 854 : 80 : Key key;
# 855 : 80 : int key_size = FindNextChar(in, ')');
# 856 [ - + ]: 80 : if (key_size < 1) return {};
# 857 [ - + ]: 80 : if (!ctx.FromString(in.begin(), in.begin() + key_size, key)) return {};
# 858 : 80 : return {{std::move(key), key_size}};
# 859 : 80 : }
# 860 : :
# 861 : : /** Parse a hex string ending at the end of the fragment's text representation. */
# 862 : : template<typename Ctx>
# 863 : : std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
# 864 : : const Ctx& ctx)
# 865 : 52 : {
# 866 : 52 : int hash_size = FindNextChar(in, ')');
# 867 [ - + ]: 52 : if (hash_size < 1) return {};
# 868 : 52 : std::string val = std::string(in.begin(), in.begin() + hash_size);
# 869 [ - + ]: 52 : if (!IsHex(val)) return {};
# 870 : 52 : auto hash = ParseHex(val);
# 871 [ - + ]: 52 : if (hash.size() != expected_size) return {};
# 872 : 52 : return {{std::move(hash), hash_size}};
# 873 : 52 : }
# 874 : :
# 875 : : /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
# 876 : : template<typename Key>
# 877 : : void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
# 878 : 406 : {
# 879 : 406 : NodeRef<Key> child = std::move(constructed.back());
# 880 : 406 : constructed.pop_back();
# 881 [ + + ]: 406 : if (reverse) {
# 882 : 206 : constructed.back() = MakeNodeRef<Key>(nt, Vector(std::move(child), std::move(constructed.back())));
# 883 : 206 : } else {
# 884 : 200 : constructed.back() = MakeNodeRef<Key>(nt, Vector(std::move(constructed.back()), std::move(child)));
# 885 : 200 : }
# 886 : 406 : }
# 887 : :
# 888 : : //! Parse a miniscript from its textual descriptor form.
# 889 : : template<typename Key, typename Ctx>
# 890 : : inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
# 891 : 192 : {
# 892 : 192 : using namespace spanparsing;
# 893 : :
# 894 : : // The two integers are used to hold state for thresh()
# 895 : 192 : std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
# 896 : 192 : std::vector<NodeRef<Key>> constructed;
# 897 : :
# 898 : 192 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 899 : :
# 900 [ + + ]: 2568 : while (!to_parse.empty()) {
# 901 : : // Get the current context we are decoding within
# 902 : 2388 : auto [cur_context, n, k] = to_parse.back();
# 903 : 2388 : to_parse.pop_back();
# 904 : :
# 905 [ - + ]: 2388 : switch (cur_context) {
# 906 [ + + ]: 668 : case ParseContext::WRAPPED_EXPR: {
# 907 : 668 : int colon_index = -1;
# 908 [ + - ]: 1448 : for (int i = 1; i < (int)in.size(); ++i) {
# 909 [ + + ]: 1448 : if (in[i] == ':') {
# 910 : 292 : colon_index = i;
# 911 : 292 : break;
# 912 : 292 : }
# 913 [ + + ][ - + ]: 1156 : if (in[i] < 'a' || in[i] > 'z') break;
# 914 : 1156 : }
# 915 : : // If there is no colon, this loop won't execute
# 916 [ + + ]: 1054 : for (int j = 0; j < colon_index; ++j) {
# 917 [ + + ]: 386 : if (in[j] == 'a') {
# 918 : 82 : to_parse.emplace_back(ParseContext::ALT, -1, -1);
# 919 [ + + ]: 304 : } else if (in[j] == 's') {
# 920 : 12 : to_parse.emplace_back(ParseContext::SWAP, -1, -1);
# 921 [ + + ]: 292 : } else if (in[j] == 'c') {
# 922 : 52 : to_parse.emplace_back(ParseContext::CHECK, -1, -1);
# 923 [ + + ]: 240 : } else if (in[j] == 'd') {
# 924 : 4 : to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
# 925 [ + + ]: 236 : } else if (in[j] == 'j') {
# 926 : 10 : to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
# 927 [ + + ]: 226 : } else if (in[j] == 'n') {
# 928 : 14 : to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
# 929 [ + + ]: 212 : } else if (in[j] == 'v') {
# 930 : 100 : to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
# 931 [ + + ]: 112 : } else if (in[j] == 'u') {
# 932 : 24 : to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
# 933 [ + + ]: 88 : } else if (in[j] == 't') {
# 934 : 44 : to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
# 935 [ + - ]: 44 : } else if (in[j] == 'l') {
# 936 : : // The l: wrapper is equivalent to or_i(0,X)
# 937 : 44 : constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
# 938 : 44 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
# 939 : 44 : } else {
# 940 : 0 : return {};
# 941 : 0 : }
# 942 : 386 : }
# 943 : 668 : to_parse.emplace_back(ParseContext::EXPR, -1, -1);
# 944 : 668 : in = in.subspan(colon_index + 1);
# 945 : 668 : break;
# 946 : 668 : }
# 947 [ + + ]: 668 : case ParseContext::EXPR: {
# 948 [ + + ]: 668 : if (Const("0", in)) {
# 949 : 56 : constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
# 950 [ + + ]: 612 : } else if (Const("1", in)) {
# 951 : 112 : constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_1));
# 952 [ + + ]: 500 : } else if (Const("pk(", in)) {
# 953 : 4 : auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
# 954 [ - + ]: 4 : if (!res) return {};
# 955 : 4 : auto& [key, key_size] = *res;
# 956 : 4 : constructed.push_back(MakeNodeRef<Key>(Fragment::WRAP_C, Vector(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))))));
# 957 : 4 : in = in.subspan(key_size + 1);
# 958 [ + + ]: 496 : } else if (Const("pkh(", in)) {
# 959 : 2 : auto res = ParseKeyEnd<Key>(in, ctx);
# 960 [ - + ]: 2 : if (!res) return {};
# 961 : 2 : auto& [key, key_size] = *res;
# 962 : 2 : constructed.push_back(MakeNodeRef<Key>(Fragment::WRAP_C, Vector(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))))));
# 963 : 2 : in = in.subspan(key_size + 1);
# 964 [ + + ]: 494 : } else if (Const("pk_k(", in)) {
# 965 : 50 : auto res = ParseKeyEnd<Key>(in, ctx);
# 966 [ - + ]: 50 : if (!res) return {};
# 967 : 50 : auto& [key, key_size] = *res;
# 968 : 50 : constructed.push_back(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))));
# 969 : 50 : in = in.subspan(key_size + 1);
# 970 [ + + ]: 444 : } else if (Const("pk_h(", in)) {
# 971 : 24 : auto res = ParseKeyEnd<Key>(in, ctx);
# 972 [ - + ]: 24 : if (!res) return {};
# 973 : 24 : auto& [key, key_size] = *res;
# 974 : 24 : constructed.push_back(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))));
# 975 : 24 : in = in.subspan(key_size + 1);
# 976 [ + + ]: 420 : } else if (Const("sha256(", in)) {
# 977 : 24 : auto res = ParseHexStrEnd(in, 32, ctx);
# 978 [ - + ]: 24 : if (!res) return {};
# 979 : 24 : auto& [hash, hash_size] = *res;
# 980 : 24 : constructed.push_back(MakeNodeRef<Key>(Fragment::SHA256, std::move(hash)));
# 981 : 24 : in = in.subspan(hash_size + 1);
# 982 [ + + ]: 396 : } else if (Const("ripemd160(", in)) {
# 983 : 8 : auto res = ParseHexStrEnd(in, 20, ctx);
# 984 [ - + ]: 8 : if (!res) return {};
# 985 : 8 : auto& [hash, hash_size] = *res;
# 986 : 8 : constructed.push_back(MakeNodeRef<Key>(Fragment::RIPEMD160, std::move(hash)));
# 987 : 8 : in = in.subspan(hash_size + 1);
# 988 [ + + ]: 388 : } else if (Const("hash256(", in)) {
# 989 : 14 : auto res = ParseHexStrEnd(in, 32, ctx);
# 990 [ - + ]: 14 : if (!res) return {};
# 991 : 14 : auto& [hash, hash_size] = *res;
# 992 : 14 : constructed.push_back(MakeNodeRef<Key>(Fragment::HASH256, std::move(hash)));
# 993 : 14 : in = in.subspan(hash_size + 1);
# 994 [ + + ]: 374 : } else if (Const("hash160(", in)) {
# 995 : 6 : auto res = ParseHexStrEnd(in, 20, ctx);
# 996 [ - + ]: 6 : if (!res) return {};
# 997 : 6 : auto& [hash, hash_size] = *res;
# 998 : 6 : constructed.push_back(MakeNodeRef<Key>(Fragment::HASH160, std::move(hash)));
# 999 : 6 : in = in.subspan(hash_size + 1);
# 1000 [ + + ]: 368 : } else if (Const("after(", in)) {
# 1001 : 76 : int arg_size = FindNextChar(in, ')');
# 1002 [ - + ]: 76 : if (arg_size < 1) return {};
# 1003 : 76 : int64_t num;
# 1004 [ - + ]: 76 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
# 1005 [ + + ][ + + ]: 76 : if (num < 1 || num >= 0x80000000L) return {};
# 1006 : 72 : constructed.push_back(MakeNodeRef<Key>(Fragment::AFTER, num));
# 1007 : 72 : in = in.subspan(arg_size + 1);
# 1008 [ + + ]: 292 : } else if (Const("older(", in)) {
# 1009 : 48 : int arg_size = FindNextChar(in, ')');
# 1010 [ - + ]: 48 : if (arg_size < 1) return {};
# 1011 : 48 : int64_t num;
# 1012 [ - + ]: 48 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
# 1013 [ + + ][ + + ]: 48 : if (num < 1 || num >= 0x80000000L) return {};
# 1014 : 44 : constructed.push_back(MakeNodeRef<Key>(Fragment::OLDER, num));
# 1015 : 44 : in = in.subspan(arg_size + 1);
# 1016 [ + + ]: 244 : } else if (Const("multi(", in)) {
# 1017 : : // Get threshold
# 1018 : 26 : int next_comma = FindNextChar(in, ',');
# 1019 [ - + ]: 26 : if (next_comma < 1) return {};
# 1020 [ - + ]: 26 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
# 1021 : 26 : in = in.subspan(next_comma + 1);
# 1022 : : // Get keys
# 1023 : 26 : std::vector<Key> keys;
# 1024 [ + + ]: 78 : while (next_comma != -1) {
# 1025 : 52 : Key key;
# 1026 : 52 : next_comma = FindNextChar(in, ',');
# 1027 [ + + ]: 52 : int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
# 1028 [ - + ]: 52 : if (key_length < 1) return {};
# 1029 [ - + ]: 52 : if (!ctx.FromString(in.begin(), in.begin() + key_length, key)) return {};
# 1030 : 52 : keys.push_back(std::move(key));
# 1031 : 52 : in = in.subspan(key_length + 1);
# 1032 : 52 : }
# 1033 [ - + ][ - + ]: 26 : if (keys.size() < 1 || keys.size() > 20) return {};
# 1034 [ - + ][ - + ]: 26 : if (k < 1 || k > (int64_t)keys.size()) return {};
# 1035 : 26 : constructed.push_back(MakeNodeRef<Key>(Fragment::MULTI, std::move(keys), k));
# 1036 [ + + ]: 218 : } else if (Const("thresh(", in)) {
# 1037 : 20 : int next_comma = FindNextChar(in, ',');
# 1038 [ - + ]: 20 : if (next_comma < 1) return {};
# 1039 [ - + ]: 20 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
# 1040 [ + + ]: 20 : if (k < 1) return {};
# 1041 : 18 : in = in.subspan(next_comma + 1);
# 1042 : : // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
# 1043 : 18 : to_parse.emplace_back(ParseContext::THRESH, 1, k);
# 1044 : 18 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1045 [ + + ]: 198 : } else if (Const("andor(", in)) {
# 1046 : 30 : to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
# 1047 : 30 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
# 1048 : 30 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1049 : 30 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
# 1050 : 30 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1051 : 30 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
# 1052 : 30 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1053 : 168 : } else {
# 1054 [ + + ]: 168 : if (Const("and_n(", in)) {
# 1055 : 8 : to_parse.emplace_back(ParseContext::AND_N, -1, -1);
# 1056 [ + + ]: 160 : } else if (Const("and_b(", in)) {
# 1057 : 24 : to_parse.emplace_back(ParseContext::AND_B, -1, -1);
# 1058 [ + + ]: 136 : } else if (Const("and_v(", in)) {
# 1059 : 40 : to_parse.emplace_back(ParseContext::AND_V, -1, -1);
# 1060 [ + + ]: 96 : } else if (Const("or_b(", in)) {
# 1061 : 22 : to_parse.emplace_back(ParseContext::OR_B, -1, -1);
# 1062 [ + + ]: 74 : } else if (Const("or_c(", in)) {
# 1063 : 16 : to_parse.emplace_back(ParseContext::OR_C, -1, -1);
# 1064 [ + + ]: 58 : } else if (Const("or_d(", in)) {
# 1065 : 24 : to_parse.emplace_back(ParseContext::OR_D, -1, -1);
# 1066 [ + - ]: 34 : } else if (Const("or_i(", in)) {
# 1067 : 34 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
# 1068 : 34 : } else {
# 1069 : 0 : return {};
# 1070 : 0 : }
# 1071 : 168 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
# 1072 : 168 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1073 : 168 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
# 1074 : 168 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1075 : 168 : }
# 1076 : 658 : break;
# 1077 : 668 : }
# 1078 [ + + ]: 658 : case ParseContext::ALT: {
# 1079 : 82 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_A, Vector(std::move(constructed.back())));
# 1080 : 82 : break;
# 1081 : 668 : }
# 1082 [ + + ]: 12 : case ParseContext::SWAP: {
# 1083 : 12 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_S, Vector(std::move(constructed.back())));
# 1084 : 12 : break;
# 1085 : 668 : }
# 1086 [ + + ]: 52 : case ParseContext::CHECK: {
# 1087 : 52 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_C, Vector(std::move(constructed.back())));
# 1088 : 52 : break;
# 1089 : 668 : }
# 1090 [ + + ]: 4 : case ParseContext::DUP_IF: {
# 1091 : 4 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_D, Vector(std::move(constructed.back())));
# 1092 : 4 : break;
# 1093 : 668 : }
# 1094 [ + + ]: 10 : case ParseContext::NON_ZERO: {
# 1095 : 10 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_J, Vector(std::move(constructed.back())));
# 1096 : 10 : break;
# 1097 : 668 : }
# 1098 [ + + ]: 14 : case ParseContext::ZERO_NOTEQUAL: {
# 1099 : 14 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_N, Vector(std::move(constructed.back())));
# 1100 : 14 : break;
# 1101 : 668 : }
# 1102 [ + + ]: 100 : case ParseContext::VERIFY: {
# 1103 : 100 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_V, Vector(std::move(constructed.back())));
# 1104 : 100 : break;
# 1105 : 668 : }
# 1106 [ + + ]: 20 : case ParseContext::WRAP_U: {
# 1107 : 20 : constructed.back() = MakeNodeRef<Key>(Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(Fragment::JUST_0)));
# 1108 : 20 : break;
# 1109 : 668 : }
# 1110 [ + + ]: 44 : case ParseContext::WRAP_T: {
# 1111 : 44 : constructed.back() = MakeNodeRef<Key>(Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(Fragment::JUST_1)));
# 1112 : 44 : break;
# 1113 : 668 : }
# 1114 [ + + ]: 24 : case ParseContext::AND_B: {
# 1115 : 24 : BuildBack(Fragment::AND_B, constructed);
# 1116 : 24 : break;
# 1117 : 668 : }
# 1118 [ + + ]: 8 : case ParseContext::AND_N: {
# 1119 : 8 : auto mid = std::move(constructed.back());
# 1120 : 8 : constructed.pop_back();
# 1121 : 8 : constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(Fragment::JUST_0)));
# 1122 : 8 : break;
# 1123 : 668 : }
# 1124 [ + + ]: 40 : case ParseContext::AND_V: {
# 1125 : 40 : BuildBack(Fragment::AND_V, constructed);
# 1126 : 40 : break;
# 1127 : 668 : }
# 1128 [ + + ]: 22 : case ParseContext::OR_B: {
# 1129 : 22 : BuildBack(Fragment::OR_B, constructed);
# 1130 : 22 : break;
# 1131 : 668 : }
# 1132 [ + + ]: 16 : case ParseContext::OR_C: {
# 1133 : 16 : BuildBack(Fragment::OR_C, constructed);
# 1134 : 16 : break;
# 1135 : 668 : }
# 1136 [ + + ]: 24 : case ParseContext::OR_D: {
# 1137 : 24 : BuildBack(Fragment::OR_D, constructed);
# 1138 : 24 : break;
# 1139 : 668 : }
# 1140 [ + + ]: 74 : case ParseContext::OR_I: {
# 1141 : 74 : BuildBack(Fragment::OR_I, constructed);
# 1142 : 74 : break;
# 1143 : 668 : }
# 1144 [ + + ]: 30 : case ParseContext::ANDOR: {
# 1145 : 30 : auto right = std::move(constructed.back());
# 1146 : 30 : constructed.pop_back();
# 1147 : 30 : auto mid = std::move(constructed.back());
# 1148 : 30 : constructed.pop_back();
# 1149 : 30 : constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
# 1150 : 30 : break;
# 1151 : 668 : }
# 1152 [ + + ]: 50 : case ParseContext::THRESH: {
# 1153 [ - + ]: 50 : if (in.size() < 1) return {};
# 1154 [ + + ]: 50 : if (in[0] == ',') {
# 1155 : 32 : in = in.subspan(1);
# 1156 : 32 : to_parse.emplace_back(ParseContext::THRESH, n+1, k);
# 1157 : 32 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
# 1158 [ + - ]: 32 : } else if (in[0] == ')') {
# 1159 [ + + ]: 18 : if (k > n) return {};
# 1160 : 16 : in = in.subspan(1);
# 1161 : : // Children are constructed in reverse order, so iterate from end to beginning
# 1162 : 16 : std::vector<NodeRef<Key>> subs;
# 1163 [ + + ]: 62 : for (int i = 0; i < n; ++i) {
# 1164 : 46 : subs.push_back(std::move(constructed.back()));
# 1165 : 46 : constructed.pop_back();
# 1166 : 46 : }
# 1167 : 16 : std::reverse(subs.begin(), subs.end());
# 1168 : 16 : constructed.push_back(MakeNodeRef<Key>(Fragment::THRESH, std::move(subs), k));
# 1169 : 16 : } else {
# 1170 : 0 : return {};
# 1171 : 0 : }
# 1172 : 48 : break;
# 1173 : 50 : }
# 1174 [ + + ]: 228 : case ParseContext::COMMA: {
# 1175 [ - + ][ - + ]: 228 : if (in.size() < 1 || in[0] != ',') return {};
# 1176 : 228 : in = in.subspan(1);
# 1177 : 228 : break;
# 1178 : 228 : }
# 1179 [ + + ]: 198 : case ParseContext::CLOSE_BRACKET: {
# 1180 [ - + ][ - + ]: 198 : if (in.size() < 1 || in[0] != ')') return {};
# 1181 : 198 : in = in.subspan(1);
# 1182 : 198 : break;
# 1183 : 198 : }
# 1184 : 2388 : }
# 1185 : 2388 : }
# 1186 : :
# 1187 : : // Sanity checks on the produced miniscript
# 1188 : 180 : assert(constructed.size() == 1);
# 1189 [ - + ]: 180 : if (in.size() > 0) return {};
# 1190 : 180 : const NodeRef<Key> tl_node = std::move(constructed.front());
# 1191 [ + + ]: 180 : if (!tl_node->IsValidTopLevel()) return {};
# 1192 : 128 : return tl_node;
# 1193 : 180 : }
# 1194 : :
# 1195 : : /** Decode a script into opcode/push pairs.
# 1196 : : *
# 1197 : : * Construct a vector with one element per opcode in the script, in reverse order.
# 1198 : : * Each element is a pair consisting of the opcode, as well as the data pushed by
# 1199 : : * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
# 1200 : : * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
# 1201 : : * respectively, plus OP_VERIFY.
# 1202 : : */
# 1203 : : bool DecomposeScript(const CScript& script, std::vector<std::pair<opcodetype, std::vector<unsigned char>>>& out);
# 1204 : :
# 1205 : : /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
# 1206 : : bool ParseScriptNumber(const std::pair<opcodetype, std::vector<unsigned char>>& in, int64_t& k);
# 1207 : :
# 1208 : : enum class DecodeContext {
# 1209 : : /** A single expression of type B, K, or V. Specifically, this can't be an
# 1210 : : * and_v or an expression of type W (a: and s: wrappers). */
# 1211 : : SINGLE_BKV_EXPR,
# 1212 : : /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
# 1213 : : * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
# 1214 : : BKV_EXPR,
# 1215 : : /** An expression of type W (a: or s: wrappers). */
# 1216 : : W_EXPR,
# 1217 : :
# 1218 : : /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
# 1219 : : * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
# 1220 : : * with s: */
# 1221 : : SWAP,
# 1222 : : /** ALT expects the next element to be TOALTSTACK (we must have already read a
# 1223 : : * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
# 1224 : : ALT,
# 1225 : : /** CHECK wraps the top constructed node with c: */
# 1226 : : CHECK,
# 1227 : : /** DUP_IF wraps the top constructed node with d: */
# 1228 : : DUP_IF,
# 1229 : : /** VERIFY wraps the top constructed node with v: */
# 1230 : : VERIFY,
# 1231 : : /** NON_ZERO wraps the top constructed node with j: */
# 1232 : : NON_ZERO,
# 1233 : : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
# 1234 : : ZERO_NOTEQUAL,
# 1235 : :
# 1236 : : /** MAYBE_AND_V will check if the next part of the script could be a valid
# 1237 : : * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
# 1238 : : * to decode it and construct the and_v node. This is recursive, to deal with
# 1239 : : * multiple and_v nodes inside each other. */
# 1240 : : MAYBE_AND_V,
# 1241 : : /** AND_V will construct an and_v node from the last two constructed nodes. */
# 1242 : : AND_V,
# 1243 : : /** AND_B will construct an and_b node from the last two constructed nodes. */
# 1244 : : AND_B,
# 1245 : : /** ANDOR will construct an andor node from the last three constructed nodes. */
# 1246 : : ANDOR,
# 1247 : : /** OR_B will construct an or_b node from the last two constructed nodes. */
# 1248 : : OR_B,
# 1249 : : /** OR_C will construct an or_c node from the last two constructed nodes. */
# 1250 : : OR_C,
# 1251 : : /** OR_D will construct an or_d node from the last two constructed nodes. */
# 1252 : : OR_D,
# 1253 : :
# 1254 : : /** In a thresh expression, all sub-expressions other than the first are W-type,
# 1255 : : * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
# 1256 : : * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
# 1257 : : THRESH_W,
# 1258 : : /** THRESH_E constructs a thresh node from the appropriate number of constructed
# 1259 : : * children. */
# 1260 : : THRESH_E,
# 1261 : :
# 1262 : : /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
# 1263 : : * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
# 1264 : : * a BKV_EXPR and then deal with the next opcode case-by-case. */
# 1265 : : ENDIF,
# 1266 : : /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
# 1267 : : * we could either be in an or_d or an or_c node. We then check for IFDUP to
# 1268 : : * distinguish these cases. */
# 1269 : : ENDIF_NOTIF,
# 1270 : : /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
# 1271 : : * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
# 1272 : : * OP_NOTIF. */
# 1273 : : ENDIF_ELSE,
# 1274 : : };
# 1275 : :
# 1276 : : //! Parse a miniscript from a bitcoin script
# 1277 : : template<typename Key, typename Ctx, typename I>
# 1278 : : inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
# 1279 : 126 : {
# 1280 : : // The two integers are used to hold state for thresh()
# 1281 : 126 : std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
# 1282 : 126 : std::vector<NodeRef<Key>> constructed;
# 1283 : :
# 1284 : : // This is the top level, so we assume the type is B
# 1285 : : // (in particular, disallowing top level W expressions)
# 1286 : 126 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
# 1287 : :
# 1288 [ + + ]: 2728 : while (!to_parse.empty()) {
# 1289 : : // Exit early if the Miniscript is not going to be valid.
# 1290 [ + + ][ - + ]: 2602 : if (!constructed.empty() && !constructed.back()->IsValid()) return {};
# 1291 : :
# 1292 : : // Get the current context we are decoding within
# 1293 : 2602 : auto [cur_context, n, k] = to_parse.back();
# 1294 : 2602 : to_parse.pop_back();
# 1295 : :
# 1296 [ - + ]: 2602 : switch(cur_context) {
# 1297 [ + + ]: 772 : case DecodeContext::SINGLE_BKV_EXPR: {
# 1298 [ - + ]: 772 : if (in >= last) return {};
# 1299 : :
# 1300 : : // Constants
# 1301 [ + + ]: 772 : if (in[0].first == OP_1) {
# 1302 : 78 : ++in;
# 1303 : 78 : constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_1));
# 1304 : 78 : break;
# 1305 : 78 : }
# 1306 [ + + ]: 694 : if (in[0].first == OP_0) {
# 1307 : 88 : ++in;
# 1308 : 88 : constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
# 1309 : 88 : break;
# 1310 : 88 : }
# 1311 : : // Public keys
# 1312 [ + + ]: 606 : if (in[0].second.size() == 33) {
# 1313 : 44 : Key key;
# 1314 [ - + ]: 44 : if (!ctx.FromPKBytes(in[0].second.begin(), in[0].second.end(), key)) return {};
# 1315 : 44 : ++in;
# 1316 : 44 : constructed.push_back(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))));
# 1317 : 44 : break;
# 1318 : 44 : }
# 1319 [ + + ][ + + ]: 562 : 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) {
# [ + + ][ + + ]
# [ + + ][ + - ]
# 1320 : 26 : Key key;
# 1321 [ - + ]: 26 : if (!ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end(), key)) return {};
# 1322 : 26 : in += 5;
# 1323 : 26 : constructed.push_back(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))));
# 1324 : 26 : break;
# 1325 : 26 : }
# 1326 : : // Time locks
# 1327 [ + - ][ + + ]: 536 : if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && ParseScriptNumber(in[1], k)) {
# [ + - ]
# 1328 : 44 : in += 2;
# 1329 [ - + ][ - + ]: 44 : if (k < 1 || k > 0x7FFFFFFFL) return {};
# 1330 : 44 : constructed.push_back(MakeNodeRef<Key>(Fragment::OLDER, k));
# 1331 : 44 : break;
# 1332 : 44 : }
# 1333 [ + - ][ + + ]: 492 : if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && ParseScriptNumber(in[1], k)) {
# [ + - ]
# 1334 : 66 : in += 2;
# 1335 [ - + ][ - + ]: 66 : if (k < 1 || k > 0x7FFFFFFFL) return {};
# 1336 : 66 : constructed.push_back(MakeNodeRef<Key>(Fragment::AFTER, k));
# 1337 : 66 : break;
# 1338 : 66 : }
# 1339 : : // Hashes
# 1340 [ + + ][ + + ]: 426 : if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && ParseScriptNumber(in[5], k) && k == 32 && in[6].first == OP_SIZE) {
# [ + + ][ + - ]
# [ + - ][ + - ]
# [ + - ]
# 1341 [ + + ][ + - ]: 52 : if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
# 1342 : 24 : constructed.push_back(MakeNodeRef<Key>(Fragment::SHA256, in[1].second));
# 1343 : 24 : in += 7;
# 1344 : 24 : break;
# 1345 [ + + ][ + - ]: 28 : } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
# 1346 : 8 : constructed.push_back(MakeNodeRef<Key>(Fragment::RIPEMD160, in[1].second));
# 1347 : 8 : in += 7;
# 1348 : 8 : break;
# 1349 [ + + ][ + - ]: 20 : } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
# 1350 : 14 : constructed.push_back(MakeNodeRef<Key>(Fragment::HASH256, in[1].second));
# 1351 : 14 : in += 7;
# 1352 : 14 : break;
# 1353 [ + - ][ + - ]: 14 : } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
# 1354 : 6 : constructed.push_back(MakeNodeRef<Key>(Fragment::HASH160, in[1].second));
# 1355 : 6 : in += 7;
# 1356 : 6 : break;
# 1357 : 6 : }
# 1358 : 52 : }
# 1359 : : // Multi
# 1360 [ + + ][ + + ]: 374 : if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
# 1361 : 24 : std::vector<Key> keys;
# 1362 [ - + ]: 24 : if (!ParseScriptNumber(in[1], n)) return {};
# 1363 [ - + ]: 24 : if (last - in < 3 + n) return {};
# 1364 [ - + ][ - + ]: 24 : if (n < 1 || n > 20) return {};
# 1365 [ + + ]: 70 : for (int i = 0; i < n; ++i) {
# 1366 : 46 : Key key;
# 1367 [ - + ]: 46 : if (in[2 + i].second.size() != 33) return {};
# 1368 [ - + ]: 46 : if (!ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end(), key)) return {};
# 1369 : 46 : keys.push_back(std::move(key));
# 1370 : 46 : }
# 1371 [ - + ]: 24 : if (!ParseScriptNumber(in[2 + n], k)) return {};
# 1372 [ - + ][ - + ]: 24 : if (k < 1 || k > n) return {};
# 1373 : 24 : in += 3 + n;
# 1374 : 24 : std::reverse(keys.begin(), keys.end());
# 1375 : 24 : constructed.push_back(MakeNodeRef<Key>(Fragment::MULTI, std::move(keys), k));
# 1376 : 24 : break;
# 1377 : 24 : }
# 1378 : : /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
# 1379 : : * than BKV_EXPR, because and_v commutes with these wrappers. For example,
# 1380 : : * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
# 1381 : : // c: wrapper
# 1382 [ + + ]: 350 : if (in[0].first == OP_CHECKSIG) {
# 1383 : 54 : ++in;
# 1384 : 54 : to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
# 1385 : 54 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1386 : 54 : break;
# 1387 : 54 : }
# 1388 : : // v: wrapper
# 1389 [ + + ]: 296 : if (in[0].first == OP_VERIFY) {
# 1390 : 86 : ++in;
# 1391 : 86 : to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
# 1392 : 86 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1393 : 86 : break;
# 1394 : 86 : }
# 1395 : : // n: wrapper
# 1396 [ + + ]: 210 : if (in[0].first == OP_0NOTEQUAL) {
# 1397 : 14 : ++in;
# 1398 : 14 : to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
# 1399 : 14 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1400 : 14 : break;
# 1401 : 14 : }
# 1402 : : // Thresh
# 1403 [ + - ][ + + ]: 196 : if (last - in >= 3 && in[0].first == OP_EQUAL && ParseScriptNumber(in[1], k)) {
# [ + - ]
# 1404 [ - + ]: 16 : if (k < 1) return {};
# 1405 : 16 : in += 2;
# 1406 : 16 : to_parse.emplace_back(DecodeContext::THRESH_W, 0, k);
# 1407 : 16 : break;
# 1408 : 16 : }
# 1409 : : // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
# 1410 [ + + ]: 180 : if (in[0].first == OP_ENDIF) {
# 1411 : 154 : ++in;
# 1412 : 154 : to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
# 1413 : 154 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
# 1414 : 154 : break;
# 1415 : 154 : }
# 1416 : : /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
# 1417 : : * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
# 1418 : : * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
# 1419 : : * miniscript, while the latter is valid. So we leave the and_v "outside"
# 1420 : : * while decoding. */
# 1421 : : // and_b
# 1422 [ + + ]: 26 : if (in[0].first == OP_BOOLAND) {
# 1423 : 16 : ++in;
# 1424 : 16 : to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
# 1425 : 16 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1426 : 16 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
# 1427 : 16 : break;
# 1428 : 16 : }
# 1429 : : // or_b
# 1430 [ + - ]: 10 : if (in[0].first == OP_BOOLOR) {
# 1431 : 10 : ++in;
# 1432 : 10 : to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
# 1433 : 10 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1434 : 10 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
# 1435 : 10 : break;
# 1436 : 10 : }
# 1437 : : // Unrecognised expression
# 1438 : 0 : return {};
# 1439 : 10 : }
# 1440 [ + + ]: 522 : case DecodeContext::BKV_EXPR: {
# 1441 : 522 : to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
# 1442 : 522 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1443 : 522 : break;
# 1444 : 10 : }
# 1445 [ + + ]: 56 : case DecodeContext::W_EXPR: {
# 1446 : : // a: wrapper
# 1447 [ - + ]: 56 : if (in >= last) return {};
# 1448 [ + + ]: 56 : if (in[0].first == OP_FROMALTSTACK) {
# 1449 : 46 : ++in;
# 1450 : 46 : to_parse.emplace_back(DecodeContext::ALT, -1, -1);
# 1451 : 46 : } else {
# 1452 : 10 : to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
# 1453 : 10 : }
# 1454 : 56 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
# 1455 : 56 : break;
# 1456 : 56 : }
# 1457 [ + + ]: 522 : case DecodeContext::MAYBE_AND_V: {
# 1458 : : // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
# 1459 : : // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
# 1460 [ + + ][ + + ]: 522 : 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) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# 1461 : 70 : to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
# 1462 : : // BKV_EXPR can contain more AND_V nodes
# 1463 : 70 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
# 1464 : 70 : }
# 1465 : 522 : break;
# 1466 : 56 : }
# 1467 [ + + ]: 10 : case DecodeContext::SWAP: {
# 1468 [ - + ][ - + ]: 10 : if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
# [ - + ]
# 1469 : 10 : ++in;
# 1470 : 10 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_S, Vector(std::move(constructed.back())));
# 1471 : 10 : break;
# 1472 : 10 : }
# 1473 [ + + ]: 46 : case DecodeContext::ALT: {
# 1474 [ - + ][ - + ]: 46 : if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
# [ - + ]
# 1475 : 46 : ++in;
# 1476 : 46 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_A, Vector(std::move(constructed.back())));
# 1477 : 46 : break;
# 1478 : 46 : }
# 1479 [ + + ]: 54 : case DecodeContext::CHECK: {
# 1480 [ - + ]: 54 : if (constructed.empty()) return {};
# 1481 : 54 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_C, Vector(std::move(constructed.back())));
# 1482 : 54 : break;
# 1483 : 54 : }
# 1484 [ + + ]: 4 : case DecodeContext::DUP_IF: {
# 1485 [ - + ]: 4 : if (constructed.empty()) return {};
# 1486 : 4 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_D, Vector(std::move(constructed.back())));
# 1487 : 4 : break;
# 1488 : 4 : }
# 1489 [ + + ]: 86 : case DecodeContext::VERIFY: {
# 1490 [ - + ]: 86 : if (constructed.empty()) return {};
# 1491 : 86 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_V, Vector(std::move(constructed.back())));
# 1492 : 86 : break;
# 1493 : 86 : }
# 1494 [ + + ]: 10 : case DecodeContext::NON_ZERO: {
# 1495 [ - + ]: 10 : if (constructed.empty()) return {};
# 1496 : 10 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_J, Vector(std::move(constructed.back())));
# 1497 : 10 : break;
# 1498 : 10 : }
# 1499 [ + + ]: 14 : case DecodeContext::ZERO_NOTEQUAL: {
# 1500 [ - + ]: 14 : if (constructed.empty()) return {};
# 1501 : 14 : constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_N, Vector(std::move(constructed.back())));
# 1502 : 14 : break;
# 1503 : 14 : }
# 1504 [ + + ]: 70 : case DecodeContext::AND_V: {
# 1505 [ - + ]: 70 : if (constructed.size() < 2) return {};
# 1506 : 70 : BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
# 1507 : 70 : break;
# 1508 : 70 : }
# 1509 [ + + ]: 16 : case DecodeContext::AND_B: {
# 1510 [ - + ]: 16 : if (constructed.size() < 2) return {};
# 1511 : 16 : BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
# 1512 : 16 : break;
# 1513 : 16 : }
# 1514 [ + + ]: 10 : case DecodeContext::OR_B: {
# 1515 [ - + ]: 10 : if (constructed.size() < 2) return {};
# 1516 : 10 : BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
# 1517 : 10 : break;
# 1518 : 10 : }
# 1519 [ + + ]: 8 : case DecodeContext::OR_C: {
# 1520 [ - + ]: 8 : if (constructed.size() < 2) return {};
# 1521 : 8 : BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
# 1522 : 8 : break;
# 1523 : 8 : }
# 1524 [ + + ]: 16 : case DecodeContext::OR_D: {
# 1525 [ - + ]: 16 : if (constructed.size() < 2) return {};
# 1526 : 16 : BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
# 1527 : 16 : break;
# 1528 : 16 : }
# 1529 [ + + ]: 30 : case DecodeContext::ANDOR: {
# 1530 [ - + ]: 30 : if (constructed.size() < 3) return {};
# 1531 : 30 : NodeRef<Key> left = std::move(constructed.back());
# 1532 : 30 : constructed.pop_back();
# 1533 : 30 : NodeRef<Key> right = std::move(constructed.back());
# 1534 : 30 : constructed.pop_back();
# 1535 : 30 : NodeRef<Key> mid = std::move(constructed.back());
# 1536 : 30 : constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
# 1537 : 30 : break;
# 1538 : 30 : }
# 1539 [ + + ]: 46 : case DecodeContext::THRESH_W: {
# 1540 [ - + ]: 46 : if (in >= last) return {};
# 1541 [ + + ]: 46 : if (in[0].first == OP_ADD) {
# 1542 : 30 : ++in;
# 1543 : 30 : to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
# 1544 : 30 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
# 1545 : 30 : } else {
# 1546 : 16 : to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
# 1547 : : // All children of thresh have type modifier d, so cannot be and_v
# 1548 : 16 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1549 : 16 : }
# 1550 : 46 : break;
# 1551 : 46 : }
# 1552 [ + + ]: 16 : case DecodeContext::THRESH_E: {
# 1553 [ - + ][ - + ]: 16 : if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
# [ - + ]
# 1554 : 16 : std::vector<NodeRef<Key>> subs;
# 1555 [ + + ]: 62 : for (int i = 0; i < n; ++i) {
# 1556 : 46 : NodeRef<Key> sub = std::move(constructed.back());
# 1557 : 46 : constructed.pop_back();
# 1558 : 46 : subs.push_back(std::move(sub));
# 1559 : 46 : }
# 1560 : 16 : constructed.push_back(MakeNodeRef<Key>(Fragment::THRESH, std::move(subs), k));
# 1561 : 16 : break;
# 1562 : 16 : }
# 1563 [ + + ]: 154 : case DecodeContext::ENDIF: {
# 1564 [ - + ]: 154 : if (in >= last) return {};
# 1565 : :
# 1566 : : // could be andor or or_i
# 1567 [ + + ]: 154 : if (in[0].first == OP_ELSE) {
# 1568 : 116 : ++in;
# 1569 : 116 : to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
# 1570 : 116 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
# 1571 : 116 : }
# 1572 : : // could be j: or d: wrapper
# 1573 [ + + ]: 38 : else if (in[0].first == OP_IF) {
# 1574 [ + - ][ + + ]: 14 : if (last - in >= 2 && in[1].first == OP_DUP) {
# 1575 : 4 : in += 2;
# 1576 : 4 : to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
# 1577 [ + - ][ + - ]: 10 : } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
# [ + - ]
# 1578 : 10 : in += 3;
# 1579 : 10 : to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
# 1580 : 10 : }
# 1581 : 0 : else {
# 1582 : 0 : return {};
# 1583 : 0 : }
# 1584 : : // could be or_c or or_d
# 1585 [ + - ]: 24 : } else if (in[0].first == OP_NOTIF) {
# 1586 : 24 : ++in;
# 1587 : 24 : to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
# 1588 : 24 : }
# 1589 : 0 : else {
# 1590 : 0 : return {};
# 1591 : 0 : }
# 1592 : 154 : break;
# 1593 : 154 : }
# 1594 [ + + ]: 154 : case DecodeContext::ENDIF_NOTIF: {
# 1595 [ - + ]: 24 : if (in >= last) return {};
# 1596 [ + + ]: 24 : if (in[0].first == OP_IFDUP) {
# 1597 : 16 : ++in;
# 1598 : 16 : to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
# 1599 : 16 : } else {
# 1600 : 8 : to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
# 1601 : 8 : }
# 1602 : : // or_c and or_d both require X to have type modifier d so, can't contain and_v
# 1603 : 24 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1604 : 24 : break;
# 1605 : 24 : }
# 1606 [ + + ]: 116 : case DecodeContext::ENDIF_ELSE: {
# 1607 [ - + ]: 116 : if (in >= last) return {};
# 1608 [ + + ]: 116 : if (in[0].first == OP_IF) {
# 1609 : 86 : ++in;
# 1610 : 86 : BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
# 1611 [ + - ]: 86 : } else if (in[0].first == OP_NOTIF) {
# 1612 : 30 : ++in;
# 1613 : 30 : to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
# 1614 : : // andor requires X to have type modifier d, so it can't be and_v
# 1615 : 30 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
# 1616 : 30 : } else {
# 1617 : 0 : return {};
# 1618 : 0 : }
# 1619 : 116 : break;
# 1620 : 116 : }
# 1621 : 2602 : }
# 1622 : 2602 : }
# 1623 [ - + ]: 126 : if (constructed.size() != 1) return {};
# 1624 : 126 : const NodeRef<Key> tl_node = std::move(constructed.front());
# 1625 : : // Note that due to how ComputeType works (only assign the type to the node if the
# 1626 : : // subs' types are valid) this would fail if any node of tree is badly typed.
# 1627 [ - + ]: 126 : if (!tl_node->IsValidTopLevel()) return {};
# 1628 : 126 : return tl_node;
# 1629 : 126 : }
# 1630 : :
# 1631 : : } // namespace internal
# 1632 : :
# 1633 : : template<typename Ctx>
# 1634 : 192 : inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
# 1635 : 192 : return internal::Parse<typename Ctx::Key>(str, ctx);
# 1636 : 192 : }
# 1637 : :
# 1638 : : template<typename Ctx>
# 1639 : 130 : inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
# 1640 : 130 : using namespace internal;
# 1641 : 130 : std::vector<std::pair<opcodetype, std::vector<unsigned char>>> decomposed;
# 1642 [ + + ]: 130 : if (!DecomposeScript(script, decomposed)) return {};
# 1643 : 126 : auto it = decomposed.begin();
# 1644 : 126 : auto ret = DecodeScript<typename Ctx::Key>(it, decomposed.end(), ctx);
# 1645 [ - + ]: 126 : if (!ret) return {};
# 1646 [ - + ]: 126 : if (it != decomposed.end()) return {};
# 1647 : 126 : return ret;
# 1648 : 126 : }
# 1649 : :
# 1650 : : } // namespace miniscript
# 1651 : :
# 1652 : : #endif // BITCOIN_SCRIPT_MINISCRIPT_H
|
