miniscript_debug/miniscript/types/
mod.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//! Miniscript Types
16//! Contains structures representing Miniscript types and utility functions
17//! Contains all the type checking rules for correctness and malleability
18//! Implemented as per rules on bitcoin.sipa.be/miniscript
19pub mod correctness;
20pub mod extra_props;
21pub mod malleability;
22
23use core::fmt;
24#[cfg(feature = "std")]
25use std::error;
26
27use bitcoin::{LockTime, PackedLockTime, Sequence};
28
29pub use self::correctness::{Base, Correctness, Input};
30pub use self::extra_props::ExtData;
31pub use self::malleability::{Dissat, Malleability};
32use super::ScriptContext;
33use crate::{MiniscriptKey, Terminal};
34
35/// None-returning function to help type inference when we need a
36/// closure that simply returns `None`
37fn return_none<T>(_: usize) -> Option<T> {
38    None
39}
40
41/// Detailed type of a typechecker error
42#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
43pub enum ErrorKind {
44    /// Relative or absolute timelock had an invalid time value (either 0, or >=0x80000000)
45    InvalidTime,
46    /// Passed a `z` argument to a `d` wrapper when `z` was expected
47    NonZeroDupIf,
48    /// Multisignature or threshold policy had a `k` value of 0
49    ZeroThreshold,
50    /// Multisignature or threshold policy has a `k` value in
51    /// excess of the number of subfragments
52    OverThreshold(usize, usize),
53    /// Attempted to construct a disjunction (or `andor`) for which
54    /// none of the child nodes were strong. This means that a 3rd
55    /// party could produce a satisfaction for any branch, meaning
56    /// that no matter which one an honest signer chooses, it is
57    /// possible to malleate the transaction.
58    NoStrongChild,
59    /// Many fragments (all disjunctions except `or_i` as well as
60    /// `andor` require their left child be dissatisfiable.
61    LeftNotDissatisfiable,
62    /// `or_b` requires its right child be dissatisfiable
63    RightNotDissatisfiable,
64    /// Tried to use the `s:` modifier on a fragment that takes more
65    /// than one input
66    SwapNonOne,
67    /// Tried to use the `j:` (`SIZE 0NOTEQUAL IF`) wrapper on something
68    /// that may be satisfied by a 0 input
69    NonZeroZero,
70    /// Many fragments require their left child to be a unit. This
71    /// was not the case.
72    LeftNotUnit,
73    /// Attempted to construct a wrapper, but the child had
74    /// an invalid type
75    ChildBase1(Base),
76    /// Attempted to construct a conjunction or disjunction, but
77    /// the fragments' children were of invalid types
78    ChildBase2(Base, Base),
79    /// Attempted to construct an `andor` but the fragments'
80    /// children were of invalid types
81    ChildBase3(Base, Base, Base),
82    /// The nth child of a threshold fragment had an invalid type (the
83    /// first must be `B` and the rest `W`s)
84    ThresholdBase(usize, Base),
85    /// The nth child of a threshold fragment did not have a unique
86    /// satisfaction
87    ThresholdDissat(usize),
88    /// The nth child of a threshold fragment was not a unit
89    ThresholdNonUnit(usize),
90    /// Insufficiently many children of a threshold fragment were strong
91    ThresholdNotStrong {
92        /// Threshold parameter
93        k: usize,
94        /// Number of children
95        n: usize,
96        /// Number of strong children
97        n_strong: usize,
98    },
99}
100
101/// Error type for typechecking
102#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
103pub struct Error<Pk: MiniscriptKey, Ctx: ScriptContext> {
104    /// The fragment that failed typecheck
105    pub fragment: Terminal<Pk, Ctx>,
106    /// The reason that typechecking failed
107    pub error: ErrorKind,
108}
109
110impl<Pk: MiniscriptKey, Ctx: ScriptContext> fmt::Display for Error<Pk, Ctx> {
111    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
112        match self.error {
113            ErrorKind::InvalidTime => write!(
114                f,
115                "fragment «{}» represents a timelock which value is invalid (time must be in [1; 0x80000000])",
116                self.fragment,
117            ),
118            ErrorKind::NonZeroDupIf => write!(
119                f,
120                "fragment «{}» represents needs to be `z`, needs to consume zero elements from the stack",
121                self.fragment,
122            ),
123            ErrorKind::ZeroThreshold => write!(
124                f,
125                "fragment «{}» has a threshold value of 0",
126                self.fragment,
127            ),
128            ErrorKind::OverThreshold(k, n) => write!(
129                f,
130                "fragment «{}» is a {}-of-{} threshold, which does not
131                 make sense",
132                self.fragment, k, n,
133            ),
134            ErrorKind::NoStrongChild => write!(
135                f,
136                "fragment «{}» requires at least one strong child \
137                 (a 3rd party cannot create a witness without having \
138                 seen one before) to prevent malleability",
139                self.fragment,
140            ),
141            ErrorKind::LeftNotDissatisfiable => write!(
142                f,
143                "fragment «{}» requires its left child be dissatisfiable",
144                self.fragment,
145            ),
146            ErrorKind::RightNotDissatisfiable => write!(
147                f,
148                "fragment «{}» requires its right child be dissatisfiable",
149                self.fragment,
150            ),
151            ErrorKind::SwapNonOne => write!(
152                f,
153                "fragment «{}» attempts to use `SWAP` to prefix something
154                 which does not take exactly one input",
155                self.fragment,
156            ),
157            ErrorKind::NonZeroZero => write!(
158                f,
159                "fragment «{}» attempts to use use the `j:` wrapper around a
160                 fragment which might be satisfied by an input of size zero",
161                self.fragment,
162            ),
163            ErrorKind::LeftNotUnit => write!(
164                f,
165                "fragment «{}» requires its left child be a unit (outputs
166                 exactly 1 given a satisfying input)",
167                self.fragment,
168            ),
169            ErrorKind::ChildBase1(base) => write!(
170                f,
171                "fragment «{}» cannot wrap a fragment of type {:?}",
172                self.fragment, base,
173            ),
174            ErrorKind::ChildBase2(base1, base2) => write!(
175                f,
176                "fragment «{}» cannot accept children of types {:?} and {:?}",
177                self.fragment, base1, base2,
178            ),
179            ErrorKind::ChildBase3(base1, base2, base3) => write!(
180                f,
181                "fragment «{}» cannot accept children of types {:?}, {:?} and {:?}",
182                self.fragment, base1, base2, base3,
183            ),
184            ErrorKind::ThresholdBase(idx, base) => write!(
185                f,
186                "fragment «{}» sub-fragment {} has type {:?} rather than {:?}",
187                self.fragment,
188                idx,
189                base,
190                if idx == 0 { Base::B } else { Base::W },
191            ),
192            ErrorKind::ThresholdDissat(idx) => write!(
193                f,
194                "fragment «{}» sub-fragment {} can not be dissatisfied \
195                 and cannot be used in a threshold",
196                self.fragment, idx,
197            ),
198            ErrorKind::ThresholdNonUnit(idx) => write!(
199                f,
200                "fragment «{}» sub-fragment {} is not a unit (does not put \
201                 exactly 1 on the stack given a satisfying input)",
202                self.fragment, idx,
203            ),
204            ErrorKind::ThresholdNotStrong { k, n, n_strong } => write!(
205                f,
206                "fragment «{}» is a {}-of-{} threshold, and needs {} of \
207                 its children to be strong to prevent malleability; however \
208                 only {} children were strong.",
209                self.fragment,
210                k,
211                n,
212                n - k,
213                n_strong,
214            ),
215        }
216    }
217}
218
219#[cfg(feature = "std")]
220impl<Pk: MiniscriptKey, Ctx: ScriptContext> error::Error for Error<Pk, Ctx> {
221    fn cause(&self) -> Option<&dyn error::Error> {
222        None
223    }
224}
225
226/// Structure representing the type of a Miniscript fragment, including all
227/// properties relevant to the main codebase
228#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
229pub struct Type {
230    /// Correctness/soundness properties
231    pub corr: Correctness,
232    /// Malleability properties
233    pub mall: Malleability,
234}
235
236impl Type {
237    /// Check whether the `self` is a subtype of `other` argument .
238    /// This checks whether the argument `other` has attributes which are present
239    /// in the given `Type`. This returns `true` on same arguments
240    /// `a.is_subtype(a)` is `true`.
241    pub fn is_subtype(&self, other: Self) -> bool {
242        self.corr.is_subtype(other.corr) && self.mall.is_subtype(other.mall)
243    }
244}
245/// Trait representing a type property, which defines how the property
246/// propagates from terminals to the root of a Miniscript
247pub trait Property: Sized {
248    /// Any extra sanity checks/assertions that should be applied after
249    /// typechecking
250    fn sanity_checks(&self) {
251        // no checks by default
252    }
253
254    /// Type property of the `True` fragment
255    fn from_true() -> Self;
256
257    /// Type property of the `False` fragment
258    fn from_false() -> Self;
259
260    /// Type property of the `PkK` fragment
261    fn from_pk_k<Ctx: ScriptContext>() -> Self;
262
263    /// Type property of the `PkH` fragment
264    fn from_pk_h<Ctx: ScriptContext>() -> Self;
265
266    /// Type property of a `Multi` fragment
267    fn from_multi(k: usize, n: usize) -> Self;
268
269    /// Type property of a `MultiA` fragment
270    fn from_multi_a(k: usize, n: usize) -> Self;
271
272    /// Type property of a hash fragment
273    fn from_hash() -> Self;
274
275    /// Type property of a `Sha256` hash. Default implementation simply
276    /// passes through to `from_hash`
277    fn from_sha256() -> Self {
278        Self::from_hash()
279    }
280
281    /// Type property of a `Hash256` hash. Default implementation simply
282    /// passes through to `from_hash`
283    fn from_hash256() -> Self {
284        Self::from_hash()
285    }
286
287    /// Type property of a `Ripemd160` hash. Default implementation simply
288    /// passes through to `from_hash`
289    fn from_ripemd160() -> Self {
290        Self::from_hash()
291    }
292
293    /// Type property of a `Hash160` hash. Default implementation simply
294    /// passes through to `from_hash`
295    fn from_hash160() -> Self {
296        Self::from_hash()
297    }
298
299    /// Type property of a timelock
300    fn from_time(t: u32) -> Self;
301
302    /// Type property of an absolute timelock. Default implementation simply
303    /// passes through to `from_time`
304    fn from_after(t: LockTime) -> Self {
305        Self::from_time(t.to_consensus_u32())
306    }
307
308    /// Type property of a relative timelock. Default implementation simply
309    /// passes through to `from_time`
310    fn from_older(t: Sequence) -> Self {
311        Self::from_time(t.to_consensus_u32())
312    }
313
314    /// Cast using the `Alt` wrapper
315    fn cast_alt(self) -> Result<Self, ErrorKind>;
316
317    /// Cast using the `Swap` wrapper
318    fn cast_swap(self) -> Result<Self, ErrorKind>;
319
320    /// Cast using the `Check` wrapper
321    fn cast_check(self) -> Result<Self, ErrorKind>;
322
323    /// Cast using the `DupIf` wrapper
324    fn cast_dupif(self) -> Result<Self, ErrorKind>;
325
326    /// Cast using the `Verify` wrapper
327    fn cast_verify(self) -> Result<Self, ErrorKind>;
328
329    /// Cast using the `NonZero` wrapper
330    fn cast_nonzero(self) -> Result<Self, ErrorKind>;
331
332    /// Cast using the `ZeroNotEqual` wrapper
333    fn cast_zeronotequal(self) -> Result<Self, ErrorKind>;
334
335    /// Cast by changing `[X]` to `AndV([X], True)`
336    fn cast_true(self) -> Result<Self, ErrorKind> {
337        Self::and_v(self, Self::from_true())
338    }
339
340    /// Cast by changing `[X]` to `or_i([X], 0)` or `or_i(0, [X])`
341    fn cast_or_i_false(self) -> Result<Self, ErrorKind>;
342
343    /// Cast by changing `[X]` to `or_i([X], 0)`. Default implementation
344    /// simply passes through to `cast_or_i_false`
345    fn cast_unlikely(self) -> Result<Self, ErrorKind> {
346        Self::or_i(self, Self::from_false())
347    }
348
349    /// Cast by changing `[X]` to `or_i(0, [X])`. Default implementation
350    /// simply passes through to `cast_or_i_false`
351    fn cast_likely(self) -> Result<Self, ErrorKind> {
352        Self::or_i(Self::from_false(), self)
353    }
354
355    /// Computes the type of an `AndB` fragment
356    fn and_b(left: Self, right: Self) -> Result<Self, ErrorKind>;
357
358    /// Computes the type of an `AndV` fragment
359    fn and_v(left: Self, right: Self) -> Result<Self, ErrorKind>;
360
361    /// Computes the type of an `AndN` fragment
362    fn and_n(left: Self, right: Self) -> Result<Self, ErrorKind> {
363        Self::and_or(left, right, Self::from_false())
364    }
365
366    /// Computes the type of an `OrB` fragment
367    fn or_b(left: Self, right: Self) -> Result<Self, ErrorKind>;
368
369    /// Computes the type of an `OrD` fragment
370    fn or_d(left: Self, right: Self) -> Result<Self, ErrorKind>;
371
372    /// Computes the type of an `OrC` fragment
373    fn or_c(left: Self, right: Self) -> Result<Self, ErrorKind>;
374
375    /// Computes the type of an `OrI` fragment
376    fn or_i(left: Self, right: Self) -> Result<Self, ErrorKind>;
377
378    /// Computes the type of an `AndOr` fragment
379    fn and_or(a: Self, b: Self, c: Self) -> Result<Self, ErrorKind>;
380
381    /// Computes the type of an `Thresh` fragment
382    fn threshold<S>(k: usize, n: usize, sub_ck: S) -> Result<Self, ErrorKind>
383    where
384        S: FnMut(usize) -> Result<Self, ErrorKind>;
385
386    /// Compute the type of a fragment, given a function to look up
387    /// the types of its children, if available and relevant for the
388    /// given fragment
389    fn type_check<Pk, Ctx, C>(
390        fragment: &Terminal<Pk, Ctx>,
391        mut child: C,
392    ) -> Result<Self, Error<Pk, Ctx>>
393    where
394        C: FnMut(usize) -> Option<Self>,
395        Pk: MiniscriptKey,
396        Ctx: ScriptContext,
397    {
398        let mut get_child = |sub, n| {
399            child(n)
400                .map(Ok)
401                .unwrap_or_else(|| Self::type_check(sub, return_none))
402        };
403        let wrap_err = |result: Result<Self, ErrorKind>| {
404            result.map_err(|kind| Error {
405                fragment: fragment.clone(),
406                error: kind,
407            })
408        };
409
410        let ret = match *fragment {
411            Terminal::True => Ok(Self::from_true()),
412            Terminal::False => Ok(Self::from_false()),
413            Terminal::PkK(..) => Ok(Self::from_pk_k::<Ctx>()),
414            Terminal::PkH(..) | Terminal::RawPkH(..) => Ok(Self::from_pk_h::<Ctx>()),
415            Terminal::Multi(k, ref pks) | Terminal::MultiA(k, ref pks) => {
416                if k == 0 {
417                    return Err(Error {
418                        fragment: fragment.clone(),
419                        error: ErrorKind::ZeroThreshold,
420                    });
421                }
422                if k > pks.len() {
423                    return Err(Error {
424                        fragment: fragment.clone(),
425                        error: ErrorKind::OverThreshold(k, pks.len()),
426                    });
427                }
428                match *fragment {
429                    Terminal::Multi(..) => Ok(Self::from_multi(k, pks.len())),
430                    Terminal::MultiA(..) => Ok(Self::from_multi_a(k, pks.len())),
431                    _ => unreachable!(),
432                }
433            }
434            Terminal::After(t) => {
435                // Note that for CLTV this is a limitation not of Bitcoin but Miniscript. The
436                // number on the stack would be a 5 bytes signed integer but Miniscript's B type
437                // only consumes 4 bytes from the stack.
438                if t == PackedLockTime::ZERO {
439                    return Err(Error {
440                        fragment: fragment.clone(),
441                        error: ErrorKind::InvalidTime,
442                    });
443                }
444                Ok(Self::from_after(t.into()))
445            }
446            Terminal::Older(t) => {
447                if t == Sequence::ZERO || !t.is_relative_lock_time() {
448                    return Err(Error {
449                        fragment: fragment.clone(),
450                        error: ErrorKind::InvalidTime,
451                    });
452                }
453                Ok(Self::from_older(t))
454            }
455            Terminal::Sha256(..) => Ok(Self::from_sha256()),
456            Terminal::Hash256(..) => Ok(Self::from_hash256()),
457            Terminal::Ripemd160(..) => Ok(Self::from_ripemd160()),
458            Terminal::Hash160(..) => Ok(Self::from_hash160()),
459            Terminal::Alt(ref sub) => wrap_err(Self::cast_alt(get_child(&sub.node, 0)?)),
460            Terminal::Swap(ref sub) => wrap_err(Self::cast_swap(get_child(&sub.node, 0)?)),
461            Terminal::Check(ref sub) => wrap_err(Self::cast_check(get_child(&sub.node, 0)?)),
462            Terminal::DupIf(ref sub) => wrap_err(Self::cast_dupif(get_child(&sub.node, 0)?)),
463            Terminal::Verify(ref sub) => wrap_err(Self::cast_verify(get_child(&sub.node, 0)?)),
464            Terminal::NonZero(ref sub) => wrap_err(Self::cast_nonzero(get_child(&sub.node, 0)?)),
465            Terminal::ZeroNotEqual(ref sub) => {
466                wrap_err(Self::cast_zeronotequal(get_child(&sub.node, 0)?))
467            }
468            Terminal::AndB(ref l, ref r) => {
469                let ltype = get_child(&l.node, 0)?;
470                let rtype = get_child(&r.node, 1)?;
471                wrap_err(Self::and_b(ltype, rtype))
472            }
473            Terminal::AndV(ref l, ref r) => {
474                let ltype = get_child(&l.node, 0)?;
475                let rtype = get_child(&r.node, 1)?;
476                wrap_err(Self::and_v(ltype, rtype))
477            }
478            Terminal::OrB(ref l, ref r) => {
479                let ltype = get_child(&l.node, 0)?;
480                let rtype = get_child(&r.node, 1)?;
481                wrap_err(Self::or_b(ltype, rtype))
482            }
483            Terminal::OrD(ref l, ref r) => {
484                let ltype = get_child(&l.node, 0)?;
485                let rtype = get_child(&r.node, 1)?;
486                wrap_err(Self::or_d(ltype, rtype))
487            }
488            Terminal::OrC(ref l, ref r) => {
489                let ltype = get_child(&l.node, 0)?;
490                let rtype = get_child(&r.node, 1)?;
491                wrap_err(Self::or_c(ltype, rtype))
492            }
493            Terminal::OrI(ref l, ref r) => {
494                let ltype = get_child(&l.node, 0)?;
495                let rtype = get_child(&r.node, 1)?;
496                wrap_err(Self::or_i(ltype, rtype))
497            }
498            Terminal::AndOr(ref a, ref b, ref c) => {
499                let atype = get_child(&a.node, 0)?;
500                let btype = get_child(&b.node, 1)?;
501                let ctype = get_child(&c.node, 2)?;
502                wrap_err(Self::and_or(atype, btype, ctype))
503            }
504            Terminal::Thresh(k, ref subs) => {
505                if k == 0 {
506                    return Err(Error {
507                        fragment: fragment.clone(),
508                        error: ErrorKind::ZeroThreshold,
509                    });
510                }
511                if k > subs.len() {
512                    return Err(Error {
513                        fragment: fragment.clone(),
514                        error: ErrorKind::OverThreshold(k, subs.len()),
515                    });
516                }
517
518                let mut last_err_frag = None;
519                let res = Self::threshold(k, subs.len(), |n| match get_child(&subs[n].node, n) {
520                    Ok(x) => Ok(x),
521                    Err(e) => {
522                        last_err_frag = Some(e.fragment);
523                        Err(e.error)
524                    }
525                });
526
527                res.map_err(|kind| Error {
528                    fragment: last_err_frag.unwrap_or_else(|| fragment.clone()),
529                    error: kind,
530                })
531            }
532        };
533        if let Ok(ref ret) = ret {
534            ret.sanity_checks()
535        }
536        ret
537    }
538}
539
540impl Property for Type {
541    fn sanity_checks(&self) {
542        debug_assert!(!self.corr.dissatisfiable || self.mall.dissat != Dissat::None);
543        debug_assert!(self.mall.dissat == Dissat::None || self.corr.base != Base::V);
544        debug_assert!(self.mall.safe || self.corr.base != Base::K);
545        debug_assert!(self.mall.non_malleable || self.corr.input != Input::Zero);
546    }
547
548    fn from_true() -> Self {
549        Type {
550            corr: Property::from_true(),
551            mall: Property::from_true(),
552        }
553    }
554
555    fn from_false() -> Self {
556        Type {
557            corr: Property::from_false(),
558            mall: Property::from_false(),
559        }
560    }
561
562    fn from_pk_k<Ctx: ScriptContext>() -> Self {
563        Type {
564            corr: Property::from_pk_k::<Ctx>(),
565            mall: Property::from_pk_k::<Ctx>(),
566        }
567    }
568
569    fn from_pk_h<Ctx: ScriptContext>() -> Self {
570        Type {
571            corr: Property::from_pk_h::<Ctx>(),
572            mall: Property::from_pk_h::<Ctx>(),
573        }
574    }
575
576    fn from_multi(k: usize, n: usize) -> Self {
577        Type {
578            corr: Property::from_multi(k, n),
579            mall: Property::from_multi(k, n),
580        }
581    }
582
583    fn from_multi_a(k: usize, n: usize) -> Self {
584        Type {
585            corr: Property::from_multi_a(k, n),
586            mall: Property::from_multi_a(k, n),
587        }
588    }
589
590    fn from_hash() -> Self {
591        Type {
592            corr: Property::from_hash(),
593            mall: Property::from_hash(),
594        }
595    }
596
597    fn from_sha256() -> Self {
598        Type {
599            corr: Property::from_sha256(),
600            mall: Property::from_sha256(),
601        }
602    }
603
604    fn from_hash256() -> Self {
605        Type {
606            corr: Property::from_hash256(),
607            mall: Property::from_hash256(),
608        }
609    }
610
611    fn from_ripemd160() -> Self {
612        Type {
613            corr: Property::from_ripemd160(),
614            mall: Property::from_ripemd160(),
615        }
616    }
617
618    fn from_hash160() -> Self {
619        Type {
620            corr: Property::from_hash160(),
621            mall: Property::from_hash160(),
622        }
623    }
624
625    fn from_time(t: u32) -> Self {
626        Type {
627            corr: Property::from_time(t),
628            mall: Property::from_time(t),
629        }
630    }
631
632    fn from_after(t: LockTime) -> Self {
633        Type {
634            corr: Property::from_after(t),
635            mall: Property::from_after(t),
636        }
637    }
638
639    fn from_older(t: Sequence) -> Self {
640        Type {
641            corr: Property::from_older(t),
642            mall: Property::from_older(t),
643        }
644    }
645
646    fn cast_alt(self) -> Result<Self, ErrorKind> {
647        Ok(Type {
648            corr: Property::cast_alt(self.corr)?,
649            mall: Property::cast_alt(self.mall)?,
650        })
651    }
652
653    fn cast_swap(self) -> Result<Self, ErrorKind> {
654        Ok(Type {
655            corr: Property::cast_swap(self.corr)?,
656            mall: Property::cast_swap(self.mall)?,
657        })
658    }
659
660    fn cast_check(self) -> Result<Self, ErrorKind> {
661        Ok(Type {
662            corr: Property::cast_check(self.corr)?,
663            mall: Property::cast_check(self.mall)?,
664        })
665    }
666
667    fn cast_dupif(self) -> Result<Self, ErrorKind> {
668        Ok(Type {
669            corr: Property::cast_dupif(self.corr)?,
670            mall: Property::cast_dupif(self.mall)?,
671        })
672    }
673
674    fn cast_verify(self) -> Result<Self, ErrorKind> {
675        Ok(Type {
676            corr: Property::cast_verify(self.corr)?,
677            mall: Property::cast_verify(self.mall)?,
678        })
679    }
680
681    fn cast_nonzero(self) -> Result<Self, ErrorKind> {
682        Ok(Type {
683            corr: Property::cast_nonzero(self.corr)?,
684            mall: Property::cast_nonzero(self.mall)?,
685        })
686    }
687
688    fn cast_zeronotequal(self) -> Result<Self, ErrorKind> {
689        Ok(Type {
690            corr: Property::cast_zeronotequal(self.corr)?,
691            mall: Property::cast_zeronotequal(self.mall)?,
692        })
693    }
694
695    fn cast_true(self) -> Result<Self, ErrorKind> {
696        Ok(Type {
697            corr: Property::cast_true(self.corr)?,
698            mall: Property::cast_true(self.mall)?,
699        })
700    }
701
702    fn cast_or_i_false(self) -> Result<Self, ErrorKind> {
703        Ok(Type {
704            corr: Property::cast_or_i_false(self.corr)?,
705            mall: Property::cast_or_i_false(self.mall)?,
706        })
707    }
708
709    fn cast_unlikely(self) -> Result<Self, ErrorKind> {
710        Ok(Type {
711            corr: Property::cast_unlikely(self.corr)?,
712            mall: Property::cast_unlikely(self.mall)?,
713        })
714    }
715
716    fn cast_likely(self) -> Result<Self, ErrorKind> {
717        Ok(Type {
718            corr: Property::cast_likely(self.corr)?,
719            mall: Property::cast_likely(self.mall)?,
720        })
721    }
722
723    fn and_b(left: Self, right: Self) -> Result<Self, ErrorKind> {
724        Ok(Type {
725            corr: Property::and_b(left.corr, right.corr)?,
726            mall: Property::and_b(left.mall, right.mall)?,
727        })
728    }
729
730    fn and_v(left: Self, right: Self) -> Result<Self, ErrorKind> {
731        Ok(Type {
732            corr: Property::and_v(left.corr, right.corr)?,
733            mall: Property::and_v(left.mall, right.mall)?,
734        })
735    }
736
737    fn or_b(left: Self, right: Self) -> Result<Self, ErrorKind> {
738        Ok(Type {
739            corr: Property::or_b(left.corr, right.corr)?,
740            mall: Property::or_b(left.mall, right.mall)?,
741        })
742    }
743
744    fn or_d(left: Self, right: Self) -> Result<Self, ErrorKind> {
745        Ok(Type {
746            corr: Property::or_d(left.corr, right.corr)?,
747            mall: Property::or_d(left.mall, right.mall)?,
748        })
749    }
750
751    fn or_c(left: Self, right: Self) -> Result<Self, ErrorKind> {
752        Ok(Type {
753            corr: Property::or_c(left.corr, right.corr)?,
754            mall: Property::or_c(left.mall, right.mall)?,
755        })
756    }
757
758    fn or_i(left: Self, right: Self) -> Result<Self, ErrorKind> {
759        Ok(Type {
760            corr: Property::or_i(left.corr, right.corr)?,
761            mall: Property::or_i(left.mall, right.mall)?,
762        })
763    }
764
765    fn and_or(a: Self, b: Self, c: Self) -> Result<Self, ErrorKind> {
766        Ok(Type {
767            corr: Property::and_or(a.corr, b.corr, c.corr)?,
768            mall: Property::and_or(a.mall, b.mall, c.mall)?,
769        })
770    }
771
772    fn threshold<S>(k: usize, n: usize, mut sub_ck: S) -> Result<Self, ErrorKind>
773    where
774        S: FnMut(usize) -> Result<Self, ErrorKind>,
775    {
776        Ok(Type {
777            corr: Property::threshold(k, n, |n| Ok(sub_ck(n)?.corr))?,
778            mall: Property::threshold(k, n, |n| Ok(sub_ck(n)?.mall))?,
779        })
780    }
781
782    /// Compute the type of a fragment assuming all the children of
783    /// Miniscript have been computed already.
784    fn type_check<Pk, Ctx, C>(
785        fragment: &Terminal<Pk, Ctx>,
786        _child: C,
787    ) -> Result<Self, Error<Pk, Ctx>>
788    where
789        C: FnMut(usize) -> Option<Self>,
790        Pk: MiniscriptKey,
791        Ctx: ScriptContext,
792    {
793        let wrap_err = |result: Result<Self, ErrorKind>| {
794            result.map_err(|kind| Error {
795                fragment: fragment.clone(),
796                error: kind,
797            })
798        };
799
800        let ret = match *fragment {
801            Terminal::True => Ok(Self::from_true()),
802            Terminal::False => Ok(Self::from_false()),
803            Terminal::PkK(..) => Ok(Self::from_pk_k::<Ctx>()),
804            Terminal::PkH(..) | Terminal::RawPkH(..) => Ok(Self::from_pk_h::<Ctx>()),
805            Terminal::Multi(k, ref pks) | Terminal::MultiA(k, ref pks) => {
806                if k == 0 {
807                    return Err(Error {
808                        fragment: fragment.clone(),
809                        error: ErrorKind::ZeroThreshold,
810                    });
811                }
812                if k > pks.len() {
813                    return Err(Error {
814                        fragment: fragment.clone(),
815                        error: ErrorKind::OverThreshold(k, pks.len()),
816                    });
817                }
818                match *fragment {
819                    Terminal::Multi(..) => Ok(Self::from_multi(k, pks.len())),
820                    Terminal::MultiA(..) => Ok(Self::from_multi_a(k, pks.len())),
821                    _ => unreachable!(),
822                }
823            }
824            Terminal::After(t) => {
825                // Note that for CLTV this is a limitation not of Bitcoin but Miniscript. The
826                // number on the stack would be a 5 bytes signed integer but Miniscript's B type
827                // only consumes 4 bytes from the stack.
828                if t == PackedLockTime::ZERO {
829                    return Err(Error {
830                        fragment: fragment.clone(),
831                        error: ErrorKind::InvalidTime,
832                    });
833                }
834                Ok(Self::from_after(t.into()))
835            }
836            Terminal::Older(t) => {
837                if t == Sequence::ZERO || !t.is_relative_lock_time() {
838                    return Err(Error {
839                        fragment: fragment.clone(),
840                        error: ErrorKind::InvalidTime,
841                    });
842                }
843                Ok(Self::from_older(t))
844            }
845            Terminal::Sha256(..) => Ok(Self::from_sha256()),
846            Terminal::Hash256(..) => Ok(Self::from_hash256()),
847            Terminal::Ripemd160(..) => Ok(Self::from_ripemd160()),
848            Terminal::Hash160(..) => Ok(Self::from_hash160()),
849            Terminal::Alt(ref sub) => wrap_err(Self::cast_alt(sub.ty)),
850            Terminal::Swap(ref sub) => wrap_err(Self::cast_swap(sub.ty)),
851            Terminal::Check(ref sub) => wrap_err(Self::cast_check(sub.ty)),
852            Terminal::DupIf(ref sub) => wrap_err(Self::cast_dupif(sub.ty)),
853            Terminal::Verify(ref sub) => wrap_err(Self::cast_verify(sub.ty)),
854            Terminal::NonZero(ref sub) => wrap_err(Self::cast_nonzero(sub.ty)),
855            Terminal::ZeroNotEqual(ref sub) => wrap_err(Self::cast_zeronotequal(sub.ty)),
856            Terminal::AndB(ref l, ref r) => {
857                let ltype = l.ty;
858                let rtype = r.ty;
859                wrap_err(Self::and_b(ltype, rtype))
860            }
861            Terminal::AndV(ref l, ref r) => {
862                let ltype = l.ty;
863                let rtype = r.ty;
864                wrap_err(Self::and_v(ltype, rtype))
865            }
866            Terminal::OrB(ref l, ref r) => {
867                let ltype = l.ty;
868                let rtype = r.ty;
869                wrap_err(Self::or_b(ltype, rtype))
870            }
871            Terminal::OrD(ref l, ref r) => {
872                let ltype = l.ty;
873                let rtype = r.ty;
874                wrap_err(Self::or_d(ltype, rtype))
875            }
876            Terminal::OrC(ref l, ref r) => {
877                let ltype = l.ty;
878                let rtype = r.ty;
879                wrap_err(Self::or_c(ltype, rtype))
880            }
881            Terminal::OrI(ref l, ref r) => {
882                let ltype = l.ty;
883                let rtype = r.ty;
884                wrap_err(Self::or_i(ltype, rtype))
885            }
886            Terminal::AndOr(ref a, ref b, ref c) => {
887                let atype = a.ty;
888                let btype = b.ty;
889                let ctype = c.ty;
890                wrap_err(Self::and_or(atype, btype, ctype))
891            }
892            Terminal::Thresh(k, ref subs) => {
893                if k == 0 {
894                    return Err(Error {
895                        fragment: fragment.clone(),
896                        error: ErrorKind::ZeroThreshold,
897                    });
898                }
899                if k > subs.len() {
900                    return Err(Error {
901                        fragment: fragment.clone(),
902                        error: ErrorKind::OverThreshold(k, subs.len()),
903                    });
904                }
905
906                let res = Self::threshold(k, subs.len(), |n| Ok(subs[n].ty));
907
908                res.map_err(|kind| Error {
909                    fragment: fragment.clone(),
910                    error: kind,
911                })
912            }
913        };
914        if let Ok(ref ret) = ret {
915            ret.sanity_checks()
916        }
917        ret
918    }
919}