miniscript_debug/miniscript/
decode.rs

1// Miniscript
2// Written in 2019 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15//! Script Decoder
16//!
17//! Functionality to parse a Bitcoin Script into a `Miniscript`
18//!
19
20use core::fmt;
21use core::marker::PhantomData;
22#[cfg(feature = "std")]
23use std::error;
24
25use bitcoin::blockdata::constants::MAX_BLOCK_WEIGHT;
26use bitcoin::hashes::{hash160, ripemd160, sha256, Hash};
27use sync::Arc;
28
29use crate::bitcoin::{LockTime, PackedLockTime, Sequence};
30use crate::miniscript::lex::{Token as Tk, TokenIter};
31use crate::miniscript::limits::MAX_PUBKEYS_PER_MULTISIG;
32use crate::miniscript::types::extra_props::ExtData;
33use crate::miniscript::types::{Property, Type};
34use crate::miniscript::ScriptContext;
35use crate::prelude::*;
36use crate::{bitcoin, hash256, Error, Miniscript, MiniscriptKey, ToPublicKey};
37
38fn return_none<T>(_: usize) -> Option<T> {
39    None
40}
41
42/// Trait for parsing keys from byte slices
43pub trait ParseableKey: Sized + ToPublicKey + private::Sealed {
44    /// Parse a key from slice
45    fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError>;
46}
47
48impl ParseableKey for bitcoin::PublicKey {
49    fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
50        bitcoin::PublicKey::from_slice(sl).map_err(KeyParseError::FullKeyParseError)
51    }
52}
53
54impl ParseableKey for bitcoin::secp256k1::XOnlyPublicKey {
55    fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
56        bitcoin::secp256k1::XOnlyPublicKey::from_slice(sl)
57            .map_err(KeyParseError::XonlyKeyParseError)
58    }
59}
60
61/// Decoding error while parsing keys
62#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
63pub enum KeyParseError {
64    /// Bitcoin PublicKey parse error
65    FullKeyParseError(bitcoin::util::key::Error),
66    /// Xonly key parse Error
67    XonlyKeyParseError(bitcoin::secp256k1::Error),
68}
69
70impl fmt::Display for KeyParseError {
71    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72        match self {
73            KeyParseError::FullKeyParseError(_e) => write!(f, "FullKey Parse Error"),
74            KeyParseError::XonlyKeyParseError(_e) => write!(f, "XonlyKey Parse Error"),
75        }
76    }
77}
78
79#[cfg(feature = "std")]
80impl error::Error for KeyParseError {
81    fn cause(&self) -> Option<&(dyn error::Error + 'static)> {
82        match self {
83            KeyParseError::FullKeyParseError(e) => Some(e),
84            KeyParseError::XonlyKeyParseError(e) => Some(e),
85        }
86    }
87}
88
89/// Private Mod to prevent downstream from implementing this public trait
90mod private {
91
92    pub trait Sealed {}
93
94    // Implement for those same types, but no others.
95    impl Sealed for super::bitcoin::PublicKey {}
96    impl Sealed for super::bitcoin::secp256k1::XOnlyPublicKey {}
97}
98
99#[derive(Copy, Clone, Debug)]
100enum NonTerm {
101    Expression,
102    WExpression,
103    Swap,
104    MaybeAndV,
105    Alt,
106    Check,
107    DupIf,
108    Verify,
109    NonZero,
110    ZeroNotEqual,
111    AndV,
112    AndB,
113    Tern,
114    OrB,
115    OrD,
116    OrC,
117    ThreshW { k: usize, n: usize },
118    ThreshE { k: usize, n: usize },
119    // could be or_d, or_c, or_i, d:, n:
120    EndIf,
121    // could be or_d, or_c
122    EndIfNotIf,
123    // could be or_i or tern
124    EndIfElse,
125}
126/// All AST elements
127/// This variant is the inner Miniscript variant that allows the user to bypass
128/// some of the miniscript rules. You should *never* construct Terminal directly.
129/// This is only exposed to external user to allow matching on the [`crate::Miniscript`]
130///
131/// The average user should always use the [`crate::Descriptor`] APIs. Advanced users
132/// who want deal with Miniscript ASTs should use the [`crate::Miniscript`] APIs.
133#[allow(broken_intra_doc_links)]
134#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
135pub enum Terminal<Pk: MiniscriptKey, Ctx: ScriptContext> {
136    /// `1`
137    True,
138    /// `0`
139    False,
140    // pubkey checks
141    /// `<key>`
142    PkK(Pk),
143    /// `DUP HASH160 <keyhash> EQUALVERIFY`
144    PkH(Pk),
145    /// Only for parsing PkH for Script. These raw descriptors are not yet specified in miniscript.
146    /// We only this variant internally for inferring miniscripts from raw Scripts.
147    /// It is not possible to construct this variant from any of the Miniscript APIs.
148    /// We don't have a generic over here because we don't want to user to have any abstract reasoning
149    /// over raw descriptors.
150    RawPkH(hash160::Hash),
151    // timelocks
152    /// `n CHECKLOCKTIMEVERIFY`
153    After(PackedLockTime),
154    /// `n CHECKSEQUENCEVERIFY`
155    Older(Sequence),
156    // hashlocks
157    /// `SIZE 32 EQUALVERIFY SHA256 <hash> EQUAL`
158    Sha256(Pk::Sha256),
159    /// `SIZE 32 EQUALVERIFY HASH256 <hash> EQUAL`
160    Hash256(Pk::Hash256),
161    /// `SIZE 32 EQUALVERIFY RIPEMD160 <hash> EQUAL`
162    Ripemd160(Pk::Ripemd160),
163    /// `SIZE 32 EQUALVERIFY HASH160 <hash> EQUAL`
164    Hash160(Pk::Hash160),
165    // Wrappers
166    /// `TOALTSTACK [E] FROMALTSTACK`
167    Alt(Arc<Miniscript<Pk, Ctx>>),
168    /// `SWAP [E1]`
169    Swap(Arc<Miniscript<Pk, Ctx>>),
170    /// `[Kt]/[Ke] CHECKSIG`
171    Check(Arc<Miniscript<Pk, Ctx>>),
172    /// `DUP IF [V] ENDIF`
173    DupIf(Arc<Miniscript<Pk, Ctx>>),
174    /// [T] VERIFY
175    Verify(Arc<Miniscript<Pk, Ctx>>),
176    /// SIZE 0NOTEQUAL IF [Fn] ENDIF
177    NonZero(Arc<Miniscript<Pk, Ctx>>),
178    /// [X] 0NOTEQUAL
179    ZeroNotEqual(Arc<Miniscript<Pk, Ctx>>),
180    // Conjunctions
181    /// [V] [T]/[V]/[F]/[Kt]
182    AndV(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
183    /// [E] [W] BOOLAND
184    AndB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
185    /// [various] NOTIF [various] ELSE [various] ENDIF
186    AndOr(
187        Arc<Miniscript<Pk, Ctx>>,
188        Arc<Miniscript<Pk, Ctx>>,
189        Arc<Miniscript<Pk, Ctx>>,
190    ),
191    // Disjunctions
192    /// [E] [W] BOOLOR
193    OrB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
194    /// [E] IFDUP NOTIF [T]/[E] ENDIF
195    OrD(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
196    /// [E] NOTIF [V] ENDIF
197    OrC(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
198    /// IF [various] ELSE [various] ENDIF
199    OrI(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
200    // Thresholds
201    /// [E] ([W] ADD)* k EQUAL
202    Thresh(usize, Vec<Arc<Miniscript<Pk, Ctx>>>),
203    /// k (<key>)* n CHECKMULTISIG
204    Multi(usize, Vec<Pk>),
205    /// <key> CHECKSIG (<key> CHECKSIGADD)*(n-1) k NUMEQUAL
206    MultiA(usize, Vec<Pk>),
207}
208
209macro_rules! match_token {
210    // Base case
211    ($tokens:expr => $sub:expr,) => { $sub };
212    // Recursive case
213    ($tokens:expr, $($first:pat $(,$rest:pat)* => $sub:expr,)*) => {
214        match $tokens.next() {
215            $(
216                Some($first) => match_token!($tokens $(,$rest)* => $sub,),
217            )*
218            Some(other) => return Err(Error::Unexpected(other.to_string())),
219            None => return Err(Error::UnexpectedStart),
220        }
221    };
222}
223
224///Vec representing terminals stack while decoding.
225#[derive(Debug)]
226struct TerminalStack<Pk: MiniscriptKey, Ctx: ScriptContext>(Vec<Miniscript<Pk, Ctx>>);
227
228impl<Pk: MiniscriptKey, Ctx: ScriptContext> TerminalStack<Pk, Ctx> {
229    ///Wrapper around self.0.pop()
230    fn pop(&mut self) -> Option<Miniscript<Pk, Ctx>> {
231        self.0.pop()
232    }
233
234    ///reduce, type check and push a 0-arg node
235    fn reduce0(&mut self, ms: Terminal<Pk, Ctx>) -> Result<(), Error> {
236        let ty = Type::type_check(&ms, return_none)?;
237        let ext = ExtData::type_check(&ms, return_none)?;
238        let ms = Miniscript {
239            node: ms,
240            ty,
241            ext,
242            phantom: PhantomData,
243        };
244        Ctx::check_global_validity(&ms)?;
245        self.0.push(ms);
246        Ok(())
247    }
248
249    ///reduce, type check and push a 1-arg node
250    fn reduce1<F>(&mut self, wrap: F) -> Result<(), Error>
251    where
252        F: FnOnce(Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
253    {
254        let top = self.pop().unwrap();
255        let wrapped_ms = wrap(Arc::new(top));
256
257        let ty = Type::type_check(&wrapped_ms, return_none)?;
258        let ext = ExtData::type_check(&wrapped_ms, return_none)?;
259        let ms = Miniscript {
260            node: wrapped_ms,
261            ty,
262            ext,
263            phantom: PhantomData,
264        };
265        Ctx::check_global_validity(&ms)?;
266        self.0.push(ms);
267        Ok(())
268    }
269
270    ///reduce, type check and push a 2-arg node
271    fn reduce2<F>(&mut self, wrap: F) -> Result<(), Error>
272    where
273        F: FnOnce(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
274    {
275        let left = self.pop().unwrap();
276        let right = self.pop().unwrap();
277
278        let wrapped_ms = wrap(Arc::new(left), Arc::new(right));
279
280        let ty = Type::type_check(&wrapped_ms, return_none)?;
281        let ext = ExtData::type_check(&wrapped_ms, return_none)?;
282        let ms = Miniscript {
283            node: wrapped_ms,
284            ty,
285            ext,
286            phantom: PhantomData,
287        };
288        Ctx::check_global_validity(&ms)?;
289        self.0.push(ms);
290        Ok(())
291    }
292}
293
294/// Parse a script fragment into an `Miniscript`
295#[allow(unreachable_patterns)]
296pub fn parse<Ctx: ScriptContext>(
297    tokens: &mut TokenIter,
298) -> Result<Miniscript<Ctx::Key, Ctx>, Error> {
299    let mut non_term = Vec::with_capacity(tokens.len());
300    let mut term = TerminalStack(Vec::with_capacity(tokens.len()));
301
302    // top level cannot be swap, must be B
303    non_term.push(NonTerm::MaybeAndV);
304    non_term.push(NonTerm::Expression);
305    loop {
306        match non_term.pop() {
307            Some(NonTerm::Expression) => {
308                match_token!(
309                    tokens,
310                    // pubkey
311                    Tk::Bytes33(pk) => {
312                        let ret = Ctx::Key::from_slice(pk)
313                            .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
314                        term.reduce0(Terminal::PkK(ret))?
315                    },
316                    Tk::Bytes65(pk) => {
317                        let ret = Ctx::Key::from_slice(pk)
318                            .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
319                        term.reduce0(Terminal::PkK(ret))?
320                    },
321                    // Note this does not collide with hash32 because they always followed by equal
322                    // and would be parsed in different branch. If we get a naked Bytes32, it must be
323                    // a x-only key
324                    // In miniscript spec, bytes32 only occurs at three places.
325                    // - during parsing XOnly keys in Pk fragment
326                    // - during parsing XOnly keys in MultiA fragment
327                    // - checking for 32 bytes hashlocks (sha256/hash256)
328                    // The second case(MultiA) is disambiguated using NumEqual which is not used anywhere in miniscript
329                    // The third case can only occur hashlocks is disambiguated because hashlocks start from equal, and
330                    // it is impossible for any K type fragment to be followed by EQUAL in miniscript spec. Thus, EQUAL
331                    // after bytes32 means bytes32 is in a hashlock
332                    // Finally for the first case, K being parsed as a solo expression is a Pk type
333                    Tk::Bytes32(pk) => {
334                        let ret = Ctx::Key::from_slice(pk).map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
335                        term.reduce0(Terminal::PkK(ret))?
336                    },
337                    // checksig
338                    Tk::CheckSig => {
339                        non_term.push(NonTerm::Check);
340                        non_term.push(NonTerm::Expression);
341                    },
342                    // pubkeyhash and [T] VERIFY and [T] 0NOTEQUAL
343                    Tk::Verify => match_token!(
344                        tokens,
345                        Tk::Equal => match_token!(
346                            tokens,
347                            Tk::Hash20(hash) => match_token!(
348                                tokens,
349                                Tk::Hash160 => match_token!(
350                                    tokens,
351                                    Tk::Dup => {
352                                        term.reduce0(Terminal::RawPkH(
353                                            hash160::Hash::from_slice(hash).expect("valid size")
354                                        ))?
355                                    },
356                                    Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
357                                        non_term.push(NonTerm::Verify);
358                                        term.reduce0(Terminal::Hash160(
359                                            hash160::Hash::from_slice(hash).expect("valid size")
360                                        ))?
361                                    },
362                                ),
363                                Tk::Ripemd160, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
364                                    non_term.push(NonTerm::Verify);
365                                    term.reduce0(Terminal::Ripemd160(
366                                        ripemd160::Hash::from_slice(hash).expect("valid size")
367                                    ))?
368                                },
369                            ),
370                            // Tk::Hash20(hash),
371                            Tk::Bytes32(hash) => match_token!(
372                                tokens,
373                                Tk::Sha256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
374                                    non_term.push(NonTerm::Verify);
375                                    term.reduce0(Terminal::Sha256(
376                                        sha256::Hash::from_slice(hash).expect("valid size")
377                                    ))?
378                                },
379                                Tk::Hash256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
380                                    non_term.push(NonTerm::Verify);
381                                    term.reduce0(Terminal::Hash256(
382                                        hash256::Hash::from_slice(hash).expect("valid size")
383                                    ))?
384                                },
385                            ),
386                            Tk::Num(k) => {
387                                non_term.push(NonTerm::Verify);
388                                non_term.push(NonTerm::ThreshW {
389                                    k: k as usize,
390                                    n: 0
391                                });
392                            },
393                        ),
394                        x => {
395                            tokens.un_next(x);
396                            non_term.push(NonTerm::Verify);
397                            non_term.push(NonTerm::Expression);
398                        },
399                    ),
400                    Tk::ZeroNotEqual => {
401                        non_term.push(NonTerm::ZeroNotEqual);
402                        non_term.push(NonTerm::Expression);
403                    },
404                    // timelocks
405                    Tk::CheckSequenceVerify, Tk::Num(n)
406                        => term.reduce0(Terminal::Older(Sequence::from_consensus(n)))?,
407                    Tk::CheckLockTimeVerify, Tk::Num(n)
408                        => term.reduce0(Terminal::After(LockTime::from_consensus(n).into()))?,
409                    // hashlocks
410                    Tk::Equal => match_token!(
411                        tokens,
412                        Tk::Bytes32(hash) => match_token!(
413                            tokens,
414                            Tk::Sha256,
415                            Tk::Verify,
416                            Tk::Equal,
417                            Tk::Num(32),
418                            Tk::Size => term.reduce0(Terminal::Sha256(
419                                sha256::Hash::from_slice(hash).expect("valid size")
420                            ))?,
421                            Tk::Hash256,
422                            Tk::Verify,
423                            Tk::Equal,
424                            Tk::Num(32),
425                            Tk::Size => term.reduce0(Terminal::Hash256(
426                                hash256::Hash::from_slice(hash).expect("valid size")
427                            ))?,
428                        ),
429                        Tk::Hash20(hash) => match_token!(
430                            tokens,
431                            Tk::Ripemd160,
432                            Tk::Verify,
433                            Tk::Equal,
434                            Tk::Num(32),
435                            Tk::Size => term.reduce0(Terminal::Ripemd160(
436                                ripemd160::Hash::from_slice(hash).expect("valid size")
437                            ))?,
438                            Tk::Hash160,
439                            Tk::Verify,
440                            Tk::Equal,
441                            Tk::Num(32),
442                            Tk::Size => term.reduce0(Terminal::Hash160(
443                                hash160::Hash::from_slice(hash).expect("valid size")
444                            ))?,
445                        ),
446                        // thresholds
447                        Tk::Num(k) => {
448                            non_term.push(NonTerm::ThreshW {
449                                k: k as usize,
450                                n: 0
451                            });
452                            // note we do *not* expect an `Expression` here;
453                            // the `ThreshW` handler below will look for
454                            // `OP_ADD` or not and do the right thing
455                        },
456                    ),
457                    // most other fragments
458                    Tk::Num(0) => term.reduce0(Terminal::False)?,
459                    Tk::Num(1) => term.reduce0(Terminal::True)?,
460                    Tk::EndIf => {
461                        non_term.push(NonTerm::EndIf);
462                        non_term.push(NonTerm::MaybeAndV);
463                        non_term.push(NonTerm::Expression);
464                    },
465                    // boolean conjunctions and disjunctions
466                    Tk::BoolAnd => {
467                        non_term.push(NonTerm::AndB);
468                        non_term.push(NonTerm::Expression);
469                        non_term.push(NonTerm::WExpression);
470                    },
471                    Tk::BoolOr => {
472                        non_term.push(NonTerm::OrB);
473                        non_term.push(NonTerm::Expression);
474                        non_term.push(NonTerm::WExpression);
475                    },
476                    // CHECKMULTISIG based multisig
477                    Tk::CheckMultiSig, Tk::Num(n) => {
478                        if n as usize > MAX_PUBKEYS_PER_MULTISIG {
479                            return Err(Error::CmsTooManyKeys(n));
480                        }
481                        let mut keys = Vec::with_capacity(n as usize);
482                        for _ in 0..n {
483                            match_token!(
484                                tokens,
485                                Tk::Bytes33(pk) => keys.push(<Ctx::Key>::from_slice(pk)
486                                    .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
487                                Tk::Bytes65(pk) => keys.push(<Ctx::Key>::from_slice(pk)
488                                    .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
489                            );
490                        }
491                        let k = match_token!(
492                            tokens,
493                            Tk::Num(k) => k,
494                        );
495                        keys.reverse();
496                        term.reduce0(Terminal::Multi(k as usize, keys))?;
497                    },
498                    // MultiA
499                    Tk::NumEqual, Tk::Num(k) => {
500                        // Check size before allocating keys
501                        if k > MAX_BLOCK_WEIGHT/32 {
502                            return Err(Error::MultiATooManyKeys(MAX_BLOCK_WEIGHT/32))
503                        }
504                        let mut keys = Vec::with_capacity(k as usize); // atleast k capacity
505                        while tokens.peek() == Some(&Tk::CheckSigAdd) {
506                            match_token!(
507                                tokens,
508                                Tk::CheckSigAdd, Tk::Bytes32(pk) => keys.push(<Ctx::Key>::from_slice(pk)
509                                    .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
510                            );
511                        }
512                        // Last key must be with a CheckSig
513                        match_token!(
514                            tokens,
515                            Tk::CheckSig, Tk::Bytes32(pk) => keys.push(<Ctx::Key>::from_slice(pk)
516                                .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
517                        );
518                        keys.reverse();
519                        term.reduce0(Terminal::MultiA(k as usize, keys))?;
520                    },
521                );
522            }
523            Some(NonTerm::MaybeAndV) => {
524                // Handle `and_v` prefixing
525                if is_and_v(tokens) {
526                    non_term.push(NonTerm::AndV);
527                    non_term.push(NonTerm::Expression);
528                }
529            }
530            Some(NonTerm::Swap) => {
531                // Handle `SWAP` prefixing
532                match_token!(
533                    tokens,
534                    Tk::Swap => {},
535                );
536                term.reduce1(Terminal::Swap)?;
537                // Swap must be always be terminating a NonTerm as it cannot be in and_v
538            }
539            Some(NonTerm::Alt) => {
540                match_token!(
541                    tokens,
542                    Tk::ToAltStack => {},
543                );
544                term.reduce1(Terminal::Alt)?;
545            }
546            Some(NonTerm::Check) => term.reduce1(Terminal::Check)?,
547            Some(NonTerm::DupIf) => term.reduce1(Terminal::DupIf)?,
548            Some(NonTerm::Verify) => term.reduce1(Terminal::Verify)?,
549            Some(NonTerm::NonZero) => term.reduce1(Terminal::NonZero)?,
550            Some(NonTerm::ZeroNotEqual) => term.reduce1(Terminal::ZeroNotEqual)?,
551            Some(NonTerm::AndV) => {
552                if is_and_v(tokens) {
553                    non_term.push(NonTerm::AndV);
554                    non_term.push(NonTerm::MaybeAndV);
555                } else {
556                    term.reduce2(Terminal::AndV)?
557                }
558            }
559            Some(NonTerm::AndB) => term.reduce2(Terminal::AndB)?,
560            Some(NonTerm::OrB) => term.reduce2(Terminal::OrB)?,
561            Some(NonTerm::OrC) => term.reduce2(Terminal::OrC)?,
562            Some(NonTerm::OrD) => term.reduce2(Terminal::OrD)?,
563            Some(NonTerm::Tern) => {
564                let a = term.pop().unwrap();
565                let b = term.pop().unwrap();
566                let c = term.pop().unwrap();
567                let wrapped_ms = Terminal::AndOr(Arc::new(a), Arc::new(c), Arc::new(b));
568
569                let ty = Type::type_check(&wrapped_ms, return_none)?;
570                let ext = ExtData::type_check(&wrapped_ms, return_none)?;
571
572                term.0.push(Miniscript {
573                    node: wrapped_ms,
574                    ty,
575                    ext,
576                    phantom: PhantomData,
577                });
578            }
579            Some(NonTerm::ThreshW { n, k }) => {
580                match_token!(
581                    tokens,
582                    Tk::Add => {
583                        non_term.push(NonTerm::ThreshW { n: n + 1, k });
584                        non_term.push(NonTerm::WExpression);
585                    },
586                    x => {
587                        tokens.un_next(x);
588                        non_term.push(NonTerm::ThreshE { n: n + 1, k });
589                        non_term.push(NonTerm::Expression);
590                    },
591                );
592            }
593            Some(NonTerm::ThreshE { n, k }) => {
594                let mut subs = Vec::with_capacity(n);
595                for _ in 0..n {
596                    subs.push(Arc::new(term.pop().unwrap()));
597                }
598                term.reduce0(Terminal::Thresh(k, subs))?;
599            }
600            Some(NonTerm::EndIf) => {
601                match_token!(
602                    tokens,
603                    Tk::Else => {
604                        non_term.push(NonTerm::EndIfElse);
605                        non_term.push(NonTerm::MaybeAndV);
606                        non_term.push(NonTerm::Expression);
607                    },
608                    Tk::If => match_token!(
609                        tokens,
610                        Tk::Dup => non_term.push(NonTerm::DupIf),
611                        Tk::ZeroNotEqual, Tk::Size
612                            => non_term.push(NonTerm::NonZero),
613                    ),
614                    Tk::NotIf => {
615                        non_term.push(NonTerm::EndIfNotIf);
616                    },
617                );
618            }
619            Some(NonTerm::EndIfNotIf) => {
620                match_token!(
621                    tokens,
622                    Tk::IfDup => non_term.push(NonTerm::OrD),
623                    x => {
624                        tokens.un_next(x);
625                        non_term.push(NonTerm::OrC);
626                    },
627                );
628                non_term.push(NonTerm::Expression);
629            }
630            Some(NonTerm::EndIfElse) => {
631                match_token!(
632                    tokens,
633                    Tk::If => {
634                        term.reduce2(Terminal::OrI)?;
635                    },
636                    Tk::NotIf => {
637                        non_term.push(NonTerm::Tern);
638                        non_term.push(NonTerm::Expression);
639                    },
640                );
641            }
642            Some(NonTerm::WExpression) => {
643                // W expression must be either from swap or Fromaltstack
644                match_token!(tokens,
645                    Tk::FromAltStack => { non_term.push(NonTerm::Alt);},
646                    tok => { tokens.un_next(tok); non_term.push(NonTerm::Swap);},);
647                non_term.push(NonTerm::MaybeAndV);
648                non_term.push(NonTerm::Expression);
649            }
650            None => {
651                // Done :)
652                break;
653            }
654        }
655    }
656
657    assert_eq!(non_term.len(), 0);
658    assert_eq!(term.0.len(), 1);
659    Ok(term.pop().unwrap())
660}
661
662fn is_and_v(tokens: &mut TokenIter) -> bool {
663    match tokens.peek() {
664        None
665        | Some(&Tk::If)
666        | Some(&Tk::NotIf)
667        | Some(&Tk::Else)
668        | Some(&Tk::ToAltStack)
669        | Some(&Tk::Swap) => false,
670        _ => true,
671    }
672}
miniscript_debug/miniscript/decode.rs

miniscript_debug/miniscript/
decode.rs
