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

elements_miniscript/miniscript/
decode.rs
