sapio_miniscript/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 bitcoin::blockdata::constants::MAX_BLOCK_WEIGHT;
21use bitcoin::hashes::{hash160, ripemd160, sha256, sha256d, Hash};
22use std::marker::PhantomData;
23use std::{error, fmt};
24use {bitcoin, Miniscript};
25
26use miniscript::lex::{Token as Tk, TokenIter};
27use miniscript::limits::MAX_PUBKEYS_PER_MULTISIG;
28use miniscript::types::extra_props::ExtData;
29use miniscript::types::Property;
30use miniscript::types::Type;
31use miniscript::ScriptContext;
32use std::sync::Arc;
33use Error;
34use MiniscriptKey;
35
36use 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
48/// Decoding error while parsing keys
49#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
50pub enum KeyParseError {
51    /// Bitcoin PublicKey parse error
52    FullKeyParseError(bitcoin::util::key::Error),
53    /// Xonly key parse Error
54    XonlyKeyParseError(bitcoin::secp256k1::Error),
55}
56
57impl ParseableKey for bitcoin::PublicKey {
58    fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
59        bitcoin::PublicKey::from_slice(sl).map_err(KeyParseError::FullKeyParseError)
60    }
61}
62
63impl ParseableKey for bitcoin::secp256k1::XOnlyPublicKey {
64    fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
65        bitcoin::secp256k1::XOnlyPublicKey::from_slice(sl)
66            .map_err(KeyParseError::XonlyKeyParseError)
67    }
68}
69
70impl error::Error for KeyParseError {
71    fn cause(&self) -> Option<&(dyn error::Error + 'static)> {
72        match self {
73            KeyParseError::FullKeyParseError(e) => Some(e),
74            KeyParseError::XonlyKeyParseError(e) => Some(e),
75        }
76    }
77}
78
79impl fmt::Display for KeyParseError {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        match self {
82            KeyParseError::FullKeyParseError(_e) => write!(f, "FullKey Parse Error"),
83            KeyParseError::XonlyKeyParseError(_e) => write!(f, "XonlyKey Parse Error"),
84        }
85    }
86}
87
88/// Private Mod to prevent downstream from implementing this public trait
89mod private {
90
91    pub trait Sealed {}
92
93    // Implement for those same types, but no others.
94    impl Sealed for super::bitcoin::PublicKey {}
95    impl Sealed for super::bitcoin::secp256k1::XOnlyPublicKey {}
96}
97
98#[derive(Copy, Clone, Debug)]
99enum NonTerm {
100    Expression,
101    WExpression,
102    Swap,
103    MaybeAndV,
104    Alt,
105    Check,
106    DupIf,
107    Verify,
108    NonZero,
109    ZeroNotEqual,
110    AndV,
111    AndB,
112    Tern,
113    OrB,
114    OrD,
115    OrC,
116    ThreshW { k: usize, n: usize },
117    ThreshE { k: usize, n: usize },
118    // could be or_d, or_c, or_i, d:, n:
119    EndIf,
120    // could be or_d, or_c
121    EndIfNotIf,
122    // could be or_i or tern
123    EndIfElse,
124}
125/// All AST elements
126#[allow(broken_intra_doc_links)]
127#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
128pub enum Terminal<Pk: MiniscriptKey, Ctx: ScriptContext> {
129    /// `1`
130    True,
131    /// `0`
132    False,
133    // pubkey checks
134    /// `<key>`
135    PkK(Pk),
136    /// `DUP HASH160 <keyhash> EQUALVERIFY`
137    PkH(Pk::Hash),
138    // timelocks
139    /// `n CHECKLOCKTIMEVERIFY`
140    After(u32),
141    /// `n CHECKSEQUENCEVERIFY`
142    Older(u32),
143    // hashlocks
144    /// `SIZE 32 EQUALVERIFY SHA256 <hash> EQUAL`
145    Sha256(sha256::Hash),
146    /// `SIZE 32 EQUALVERIFY HASH256 <hash> EQUAL`
147    Hash256(sha256d::Hash),
148    /// `SIZE 32 EQUALVERIFY RIPEMD160 <hash> EQUAL`
149    Ripemd160(ripemd160::Hash),
150    /// `SIZE 32 EQUALVERIFY HASH160 <hash> EQUAL`
151    Hash160(hash160::Hash),
152    // Wrappers
153    /// `TOALTSTACK [E] FROMALTSTACK`
154    Alt(Arc<Miniscript<Pk, Ctx>>),
155    /// `SWAP [E1]`
156    Swap(Arc<Miniscript<Pk, Ctx>>),
157    /// `[Kt]/[Ke] CHECKSIG`
158    Check(Arc<Miniscript<Pk, Ctx>>),
159    /// `DUP IF [V] ENDIF`
160    DupIf(Arc<Miniscript<Pk, Ctx>>),
161    /// [T] VERIFY
162    Verify(Arc<Miniscript<Pk, Ctx>>),
163    /// SIZE 0NOTEQUAL IF [Fn] ENDIF
164    NonZero(Arc<Miniscript<Pk, Ctx>>),
165    /// [X] 0NOTEQUAL
166    ZeroNotEqual(Arc<Miniscript<Pk, Ctx>>),
167    // Conjunctions
168    /// [V] [T]/[V]/[F]/[Kt]
169    AndV(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
170    /// [E] [W] BOOLAND
171    AndB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
172    /// [various] NOTIF [various] ELSE [various] ENDIF
173    AndOr(
174        Arc<Miniscript<Pk, Ctx>>,
175        Arc<Miniscript<Pk, Ctx>>,
176        Arc<Miniscript<Pk, Ctx>>,
177    ),
178    // Disjunctions
179    /// [E] [W] BOOLOR
180    OrB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
181    /// [E] IFDUP NOTIF [T]/[E] ENDIF
182    OrD(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
183    /// [E] NOTIF [V] ENDIF
184    OrC(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
185    /// IF [various] ELSE [various] ENDIF
186    OrI(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
187    // Thresholds
188    /// [E] ([W] ADD)* k EQUAL
189    Thresh(usize, Vec<Arc<Miniscript<Pk, Ctx>>>),
190    /// k (<key>)* n CHECKMULTISIG
191    Multi(usize, Vec<Pk>),
192    /// <key> CHECKSIG (<key> CHECKSIGADD)*(n-1) k NUMEQUAL
193    MultiA(usize, Vec<Pk>),
194    // Other
195    /// `<hash> OP_CHECKTEMPLATEVERIFY OP_DROP`
196    TxTemplate(sha256::Hash),
197}
198
199macro_rules! match_token {
200    // Base case
201    ($tokens:expr => $sub:expr,) => { $sub };
202    // Recursive case
203    ($tokens:expr, $($first:pat $(,$rest:pat)* => $sub:expr,)*) => {
204        match $tokens.next() {
205            $(
206                Some($first) => match_token!($tokens $(,$rest)* => $sub,),
207            )*
208            Some(other) => return Err(Error::Unexpected(other.to_string())),
209            None => return Err(Error::UnexpectedStart),
210        }
211    };
212}
213
214///Vec representing terminals stack while decoding.
215#[derive(Debug)]
216struct TerminalStack<Pk: MiniscriptKey, Ctx: ScriptContext>(Vec<Miniscript<Pk, Ctx>>);
217
218impl<Pk: MiniscriptKey, Ctx: ScriptContext> TerminalStack<Pk, Ctx> {
219    ///Wrapper around self.0.pop()
220    fn pop(&mut self) -> Option<Miniscript<Pk, Ctx>> {
221        self.0.pop()
222    }
223
224    ///reduce, type check and push a 0-arg node
225    fn reduce0(&mut self, ms: Terminal<Pk, Ctx>) -> Result<(), Error> {
226        let ty = Type::type_check(&ms, return_none)?;
227        let ext = ExtData::type_check(&ms, return_none)?;
228        let ms = Miniscript {
229            node: ms,
230            ty: ty,
231            ext: ext,
232            phantom: PhantomData,
233        };
234        Ctx::check_global_validity(&ms)?;
235        self.0.push(ms);
236        Ok(())
237    }
238
239    ///reduce, type check and push a 1-arg node
240    fn reduce1<F>(&mut self, wrap: F) -> Result<(), Error>
241    where
242        F: FnOnce(Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
243    {
244        let top = self.pop().unwrap();
245        let wrapped_ms = wrap(Arc::new(top));
246
247        let ty = Type::type_check(&wrapped_ms, return_none)?;
248        let ext = ExtData::type_check(&wrapped_ms, return_none)?;
249        let ms = Miniscript {
250            node: wrapped_ms,
251            ty: ty,
252            ext: ext,
253            phantom: PhantomData,
254        };
255        Ctx::check_global_validity(&ms)?;
256        self.0.push(ms);
257        Ok(())
258    }
259
260    ///reduce, type check and push a 2-arg node
261    fn reduce2<F>(&mut self, wrap: F) -> Result<(), Error>
262    where
263        F: FnOnce(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
264    {
265        let left = self.pop().unwrap();
266        let right = self.pop().unwrap();
267
268        let wrapped_ms = wrap(Arc::new(left), Arc::new(right));
269
270        let ty = Type::type_check(&wrapped_ms, return_none)?;
271        let ext = ExtData::type_check(&wrapped_ms, return_none)?;
272        let ms = Miniscript {
273            node: wrapped_ms,
274            ty: ty,
275            ext: ext,
276            phantom: PhantomData,
277        };
278        Ctx::check_global_validity(&ms)?;
279        self.0.push(ms);
280        Ok(())
281    }
282}
283
284/// Parse a script fragment into an `Miniscript`
285#[allow(unreachable_patterns)]
286pub fn parse<Ctx: ScriptContext>(
287    tokens: &mut TokenIter,
288) -> Result<Miniscript<Ctx::Key, Ctx>, Error> {
289    let mut non_term = Vec::with_capacity(tokens.len());
290    let mut term = TerminalStack(Vec::with_capacity(tokens.len()));
291
292    // top level cannot be swap, must be B
293    non_term.push(NonTerm::MaybeAndV);
294    non_term.push(NonTerm::Expression);
295    loop {
296        match non_term.pop() {
297            Some(NonTerm::Expression) => {
298                match_token!(
299                    tokens,
300                    // pubkey
301                    Tk::Bytes33(pk) => {
302                        let ret = Ctx::Key::from_slice(pk)
303                            .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
304                        term.reduce0(Terminal::PkK(ret))?
305                    },
306                    Tk::Bytes65(pk) => {
307                        let ret = Ctx::Key::from_slice(pk)
308                            .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
309                        term.reduce0(Terminal::PkK(ret))?
310                    },
311                    // Note this does not collide with hash32 because they always followed by equal
312                    // and would be parsed in different branch. If we get a naked Bytes32, it must be
313                    // a x-only key
314                    // In miniscript spec, bytes32 only occurs at three places.
315                    // - during parsing XOnly keys in Pk fragment
316                    // - during parsing XOnly keys in MultiA fragment
317                    // - checking for 32 bytes hashlocks (sha256/hash256)
318                    // The second case(MultiA) is disambiguated using NumEqual which is not used anywhere in miniscript
319                    // The third case can only occur hashlocks is disambiguated because hashlocks start from equal, and
320                    // it is impossible for any K type fragment to be followed by EQUAL in miniscript spec. Thus, EQUAL
321                    // after bytes32 means bytes32 is in a hashlock
322                    // Finally for the first case, K being parsed as a solo expression is a Pk type
323                    Tk::Bytes32(pk) => {
324                        let ret = Ctx::Key::from_slice(pk).map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
325                        term.reduce0(Terminal::PkK(ret))?
326                    },
327                    // checksig
328                    Tk::CheckSig => {
329                        non_term.push(NonTerm::Check);
330                        non_term.push(NonTerm::Expression);
331                    },
332                    // pubkeyhash and [T] VERIFY and [T] 0NOTEQUAL
333                    Tk::Verify => match_token!(
334                        tokens,
335                        Tk::Equal => match_token!(
336                            tokens,
337                            Tk::Hash20(hash) => match_token!(
338                                tokens,
339                                Tk::Hash160 => match_token!(
340                                    tokens,
341                                    Tk::Dup => {
342                                        term.reduce0(Terminal::PkH(
343                                            hash160::Hash::from_slice(hash).expect("valid size")
344                                        ))?
345                                    },
346                                    Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
347                                        non_term.push(NonTerm::Verify);
348                                        term.reduce0(Terminal::Hash160(
349                                            hash160::Hash::from_slice(hash).expect("valid size")
350                                        ))?
351                                    },
352                                ),
353                                Tk::Ripemd160, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
354                                    non_term.push(NonTerm::Verify);
355                                    term.reduce0(Terminal::Ripemd160(
356                                        ripemd160::Hash::from_slice(hash).expect("valid size")
357                                    ))?
358                                },
359                            ),
360                            // Tk::Hash20(hash),
361                            Tk::Bytes32(hash) => match_token!(
362                                tokens,
363                                Tk::Sha256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
364                                    non_term.push(NonTerm::Verify);
365                                    term.reduce0(Terminal::Sha256(
366                                        sha256::Hash::from_slice(hash).expect("valid size")
367                                    ))?
368                                },
369                                Tk::Hash256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
370                                    non_term.push(NonTerm::Verify);
371                                    term.reduce0(Terminal::Hash256(
372                                        sha256d::Hash::from_slice(hash).expect("valid size")
373                                    ))?
374                                },
375                            ),
376                            Tk::Num(k) => {
377                                non_term.push(NonTerm::Verify);
378                                non_term.push(NonTerm::ThreshW {
379                                    k: k as usize,
380                                    n: 0
381                                });
382                            },
383                        ),
384                        x => {
385                            tokens.un_next(x);
386                            non_term.push(NonTerm::Verify);
387                            non_term.push(NonTerm::Expression);
388                        },
389                    ),
390                    Tk::ZeroNotEqual => {
391                        non_term.push(NonTerm::ZeroNotEqual);
392                        non_term.push(NonTerm::Expression);
393                    },
394                    // timelocks
395                    Tk::CheckSequenceVerify, Tk::Num(n)
396                        => term.reduce0(Terminal::Older(n))?,
397                    Tk::CheckLockTimeVerify, Tk::Num(n)
398                        => term.reduce0(Terminal::After(n))?,
399                    // hashlocks
400                    Tk::Equal => match_token!(
401                        tokens,
402                        Tk::Bytes32(hash) => match_token!(
403                            tokens,
404                            Tk::Sha256,
405                            Tk::Verify,
406                            Tk::Equal,
407                            Tk::Num(32),
408                            Tk::Size => term.reduce0(Terminal::Sha256(
409                                sha256::Hash::from_slice(hash).expect("valid size")
410                            ))?,
411                            Tk::Hash256,
412                            Tk::Verify,
413                            Tk::Equal,
414                            Tk::Num(32),
415                            Tk::Size => term.reduce0(Terminal::Hash256(
416                                sha256d::Hash::from_slice(hash).expect("valid size")
417                            ))?,
418                        ),
419                        Tk::Hash20(hash) => match_token!(
420                            tokens,
421                            Tk::Ripemd160,
422                            Tk::Verify,
423                            Tk::Equal,
424                            Tk::Num(32),
425                            Tk::Size => term.reduce0(Terminal::Ripemd160(
426                                ripemd160::Hash::from_slice(hash).expect("valid size")
427                            ))?,
428                            Tk::Hash160,
429                            Tk::Verify,
430                            Tk::Equal,
431                            Tk::Num(32),
432                            Tk::Size => term.reduce0(Terminal::Hash160(
433                                hash160::Hash::from_slice(hash).expect("valid size")
434                            ))?,
435                        ),
436                        // thresholds
437                        Tk::Num(k) => {
438                            non_term.push(NonTerm::ThreshW {
439                                k: k as usize,
440                                n: 0
441                            });
442                            // note we do *not* expect an `Expression` here;
443                            // the `ThreshW` handler below will look for
444                            // `OP_ADD` or not and do the right thing
445                        },
446                    ),
447                    Tk::Drop, Tk::CheckTemplateVerify, Tk::Bytes32(h) => term.reduce0(Terminal::TxTemplate(sha256::Hash::from_slice(h).map_err(|_| Error::Unexpected("Wrong Sized Hash in Bytes32".into()))?))?,
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: ty,
566                    ext: 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}
sapio_miniscript/miniscript/decode.rs

sapio_miniscript/miniscript/
decode.rs
