miniscript/primitives/
threshold.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Thresholds
4//!
5//! Miniscript
6
7#[cfg(all(not(feature = "std"), not(test)))]
8use alloc::{vec, vec::Vec};
9use core::{cmp, fmt, iter};
10#[cfg(any(feature = "std", test))]
11use std::vec;
12
13/// Error parsing an absolute locktime.
14#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
15pub struct ThresholdError {
16    k: usize,
17    n: usize,
18    max: Option<usize>,
19}
20
21impl fmt::Display for ThresholdError {
22    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
23        if self.n == 0 {
24            f.write_str("thresholds in Miniscript must be nonempty")
25        } else if self.k == 0 {
26            f.write_str("thresholds in Miniscript must have k > 0")
27        } else if self.k > self.n {
28            write!(f, "invalid threshold {}-of-{}; cannot have k > n", self.k, self.n)
29        } else {
30            debug_assert!(self.max.is_some());
31            let max = self.max.unwrap();
32            debug_assert!(self.n > max);
33            write!(f, "invalid threshold {}-of-{}; maximum size is {}", self.k, self.n, max)
34        }
35    }
36}
37
38#[cfg(feature = "std")]
39impl std::error::Error for ThresholdError {
40    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { None }
41}
42
43/// Structure representing a k-of-n threshold collection of some arbitrary
44/// object `T`.
45///
46/// If the constant parameter `MAX` is nonzero, it represents a cap on the
47/// `n` value; if `n` exceeds `MAX` then an error is returned on construction.
48#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
49pub struct Threshold<T, const MAX: usize> {
50    k: usize,
51    inner: Vec<T>,
52}
53
54impl<T, const MAX: usize> Threshold<T, MAX> {
55    /// Constructs a threshold directly from a threshold value and collection.
56    pub fn new(k: usize, inner: Vec<T>) -> Result<Self, ThresholdError> {
57        if k == 0 || k > inner.len() || (MAX > 0 && inner.len() > MAX) {
58            Err(ThresholdError { k, n: inner.len(), max: (MAX > 0).then(|| MAX) })
59        } else {
60            Ok(Threshold { k, inner })
61        }
62    }
63
64    /// Constructs a threshold from a threshold value and an iterator that yields collection
65    /// elements.
66    pub fn from_iter<I: Iterator<Item = T>>(k: usize, iter: I) -> Result<Self, ThresholdError> {
67        let min_size = cmp::max(k, iter.size_hint().0);
68        // Do an early return if our minimum size exceeds the max.
69        if MAX > 0 && min_size > MAX {
70            let n = iter.count();
71            return Err(ThresholdError { k, n, max: (MAX > 0).then(|| MAX) });
72        }
73
74        let mut inner = Vec::with_capacity(min_size);
75        iter.for_each(|x| inner.push(x));
76        Self::new(k, inner)
77    }
78
79    /// Constructor for an "or" represented as a 1-of-2 threshold.
80    pub fn or(left: T, right: T) -> Self {
81        debug_assert!(MAX == 0 || MAX > 1);
82        Threshold { k: 1, inner: vec![left, right] }
83    }
84
85    /// Constructor for an "and" represented as a 2-of-2 threshold.
86    pub fn and(left: T, right: T) -> Self {
87        debug_assert!(MAX == 0 || MAX > 1);
88        Threshold { k: 2, inner: vec![left, right] }
89    }
90
91    /// Whether this threshold is a 1-of-n.
92    pub fn is_or(&self) -> bool { self.k == 1 }
93
94    /// Whether this threshold is a n-of-n.
95    pub fn is_and(&self) -> bool { self.k == self.inner.len() }
96
97    /// Changes the type-system-enforced maximum value of the threshold.
98    pub fn set_maximum<const NEWMAX: usize>(self) -> Result<Threshold<T, NEWMAX>, ThresholdError> {
99        Threshold::new(self.k, self.inner)
100    }
101
102    /// Forgets the type-system-enforced maximum value of the threshold.
103    pub fn forget_maximum(self) -> Threshold<T, 0> { Threshold { k: self.k, inner: self.inner } }
104
105    /// Constructs a threshold from an existing threshold by applying a mapping function to
106    /// each individual item.
107    pub fn map<U, F: FnMut(T) -> U>(self, mapfn: F) -> Threshold<U, MAX> {
108        Threshold { k: self.k, inner: self.inner.into_iter().map(mapfn).collect() }
109    }
110
111    /// Like [`Self::map`] but takes a reference to the threshold rather than taking ownership.
112    pub fn map_ref<U, F: FnMut(&T) -> U>(&self, mapfn: F) -> Threshold<U, MAX> {
113        Threshold { k: self.k, inner: self.inner.iter().map(mapfn).collect() }
114    }
115
116    /// Like [`Self::map`] except that the mapping function may return an error.
117    pub fn translate<U, F, FuncError>(self, translatefn: F) -> Result<Threshold<U, MAX>, FuncError>
118    where
119        F: FnMut(T) -> Result<U, FuncError>,
120    {
121        let k = self.k;
122        self.inner
123            .into_iter()
124            .map(translatefn)
125            .collect::<Result<Vec<_>, _>>()
126            .map(|inner| Threshold { k, inner })
127    }
128
129    /// Like [`Self::translate`] but takes a reference to the threshold rather than taking ownership.
130    pub fn translate_ref<U, F, FuncError>(
131        &self,
132        translatefn: F,
133    ) -> Result<Threshold<U, MAX>, FuncError>
134    where
135        F: FnMut(&T) -> Result<U, FuncError>,
136    {
137        let k = self.k;
138        self.inner
139            .iter()
140            .map(translatefn)
141            .collect::<Result<Vec<_>, _>>()
142            .map(|inner| Threshold { k, inner })
143    }
144
145    /// Like [`Self::translate_ref`] but passes indices to the closure rather than internal data.
146    ///
147    /// This is useful in situations where the data to be translated exists outside of the
148    /// threshold itself, and the threshold data is irrelevant. In particular it is commonly
149    /// paired with [`crate::expression::Tree::to_null_threshold`].
150    ///
151    /// If the data to be translated comes from a post-order iterator, you may instead want
152    /// [`Self::map_from_post_order_iter`].
153    pub fn translate_by_index<U, F, FuncError>(
154        &self,
155        translatefn: F,
156    ) -> Result<Threshold<U, MAX>, FuncError>
157    where
158        F: FnMut(usize) -> Result<U, FuncError>,
159    {
160        let k = self.k;
161        (0..self.inner.len())
162            .map(translatefn)
163            .collect::<Result<Vec<_>, _>>()
164            .map(|inner| Threshold { k, inner })
165    }
166
167    /// Construct a threshold from an existing threshold which has been processed in some way.
168    ///
169    /// It is a common pattern in this library to transform data structures by
170    /// running a post-order iterator over them, putting processed elements into
171    /// a vector to be later referenced by their parents.
172    ///
173    /// This function encapsulates that pattern by taking the child-index vector of
174    /// the`PostOrderIterItem`, under consideration, and the vector of processed
175    /// elements.
176    pub fn map_from_post_order_iter<U: Clone>(
177        &self,
178        child_indices: &[usize],
179        processed: &[U],
180    ) -> Threshold<U, MAX> {
181        debug_assert_eq!(
182            self.inner.len(),
183            child_indices.len(),
184            "internal consistency error translating threshold by post-order iterator"
185        );
186        let mut processed_inner = Vec::with_capacity(self.inner.len());
187        processed_inner.extend(child_indices.iter().copied().map(|n| processed[n].clone()));
188        Threshold { k: self.k, inner: processed_inner }
189    }
190
191    /// Accessor for the number of elements in the threshold.
192    // non-const because Vec::len is not const
193    pub fn n(&self) -> usize { self.inner.len() }
194
195    /// Accessor for the threshold value.
196    pub const fn k(&self) -> usize { self.k }
197
198    /// Accessor for the underlying data.
199    pub fn data(&self) -> &[T] { &self.inner }
200
201    /// Mutable accessor for the underlying data.
202    ///
203    /// This returns access to the underlying data as a mutable slice, which allows you
204    /// to modify individual elements. To change the number of elements, you must
205    /// destructure the threshold with [`Self::k`] and [`Self::into_data`] and
206    /// reconstruct it (and on reconstruction, deal with any errors caused by your
207    /// tinkering with the threshold values).
208    pub fn data_mut(&mut self) -> &mut [T] { &mut self.inner }
209
210    /// Accessor for the underlying data.
211    pub fn into_data(self) -> Vec<T> { self.inner }
212
213    /// Passthrough to an iterator on the underlying vector.
214    pub fn iter(&self) -> core::slice::Iter<'_, T> { self.inner.iter() }
215}
216
217impl<T> Threshold<T, 0> {
218    /// Constructor for an "or" represented as a 1-of-n threshold.
219    ///
220    /// # Panics
221    ///
222    /// Panics if the passed vector is empty.
223    pub fn or_n(inner: Vec<T>) -> Self {
224        assert_ne!(inner.len(), 0);
225        Threshold { k: 1, inner }
226    }
227
228    /// Constructor for an "and" represented as a n-of-n threshold.
229    ///
230    /// # Panics
231    ///
232    /// Panics if the passed vector is empty.
233    pub fn and_n(inner: Vec<T>) -> Self {
234        assert_ne!(inner.len(), 0);
235        Threshold { k: inner.len(), inner }
236    }
237}
238
239impl<T, const MAX: usize> iter::IntoIterator for Threshold<T, MAX> {
240    type Item = T;
241    type IntoIter = vec::IntoIter<T>;
242
243    fn into_iter(self) -> Self::IntoIter { self.inner.into_iter() }
244}
245
246impl<T: fmt::Display, const MAX: usize> Threshold<T, MAX> {
247    /// Produces an object which can [`fmt::Display`] the threshold.
248    pub fn display<'s>(&'s self, name: &'s str, show_k: bool) -> impl fmt::Display + 's {
249        ThreshDisplay { name, thresh: self, show_k }
250    }
251}
252
253impl<T: fmt::Debug, const MAX: usize> Threshold<T, MAX> {
254    /// Produces an object which can [`fmt::Debug`] the threshold.
255    pub fn debug<'s>(&'s self, name: &'s str, show_k: bool) -> impl fmt::Debug + 's {
256        ThreshDisplay { name, thresh: self, show_k }
257    }
258}
259
260struct ThreshDisplay<'t, 's, T, const MAX: usize> {
261    name: &'s str,
262    thresh: &'t Threshold<T, MAX>,
263    show_k: bool,
264}
265
266impl<'t, 's, T, const MAX: usize> fmt::Display for ThreshDisplay<'t, 's, T, MAX>
267where
268    T: fmt::Display,
269{
270    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
271        use core::fmt::Write;
272
273        f.write_str(self.name)?;
274        f.write_char('(')?;
275        let inners = if self.show_k {
276            write!(f, "{}", self.thresh.k)?;
277            &self.thresh.inner[0..]
278        } else {
279            write!(f, "{}", self.thresh.inner[0])?;
280            &self.thresh.inner[1..]
281        };
282        for inner in inners {
283            write!(f, ",{}", inner)?;
284        }
285        f.write_char(')')
286    }
287}
288
289impl<'t, 's, T, const MAX: usize> fmt::Debug for ThreshDisplay<'t, 's, T, MAX>
290where
291    T: fmt::Debug,
292{
293    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
294        use core::fmt::Write;
295
296        f.write_str(self.name)?;
297        f.write_char('(')?;
298        let inners = if self.show_k {
299            write!(f, "{}", self.thresh.k)?;
300            &self.thresh.inner[0..]
301        } else {
302            write!(f, "{:?}", self.thresh.inner[0])?;
303            &self.thresh.inner[1..]
304        };
305        for inner in inners {
306            write!(f, ",{:?}", inner)?;
307        }
308        f.write_char(')')
309    }
310}
miniscript/primitives/threshold.rs

miniscript/primitives/
threshold.rs
