miniscript_qtum/miniscript/
decode.rs

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

miniscript_qtum/miniscript/
decode.rs
