derive/
path.rs

1// Modern, minimalistic & standard-compliant cold wallet library.
2//
3// SPDX-License-Identifier: Apache-2.0
4//
5// Written in 2020-2024 by
6//     Dr Maxim Orlovsky <orlovsky@lnp-bp.org>
7//
8// Copyright (C) 2020-2024 LNP/BP Standards Association. All rights reserved.
9// Copyright (C) 2020-2024 Dr Maxim Orlovsky. All rights reserved.
10//
11// Licensed under the Apache License, Version 2.0 (the "License");
12// you may not use this file except in compliance with the License.
13// You may obtain a copy of the License at
14//
15//     http://www.apache.org/licenses/LICENSE-2.0
16//
17// Unless required by applicable law or agreed to in writing, software
18// distributed under the License is distributed on an "AS IS" BASIS,
19// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20// See the License for the specific language governing permissions and
21// limitations under the License.
22
23use core::fmt::{self, Display, Formatter};
24use core::num::ParseIntError;
25use core::ops::Index;
26use core::str::FromStr;
27use std::collections::BTreeSet;
28
29use amplify::confinement;
30use amplify::confinement::{Confined, NonEmptyOrdSet};
31
32use crate::{DerivationIndex, Idx, IdxBase, IndexParseError, NormalIndex, Terminal};
33
34#[derive(Clone, Eq, PartialEq, Debug, Display, Error)]
35#[display(doc_comments)]
36pub enum DerivationParseError {
37    /// unable to parse derivation path '{0}' - {1}
38    InvalidIndex(String, IndexParseError),
39    /// invalid derivation path format '{0}'
40    InvalidFormat(String),
41}
42
43#[derive(Clone, Eq, PartialEq, Hash, Debug)]
44pub struct DerivationSeg<I: IdxBase = NormalIndex>(NonEmptyOrdSet<I, 8>);
45
46impl<I: IdxBase> From<&'static [I]> for DerivationSeg<I> {
47    fn from(indexes: &'static [I]) -> Self {
48        Self(Confined::from_iter_checked(indexes.iter().copied()))
49    }
50}
51
52impl<I: IdxBase> From<[I; 2]> for DerivationSeg<I> {
53    fn from(indexes: [I; 2]) -> Self { Self(Confined::from_iter_checked(indexes)) }
54}
55
56impl<I: IdxBase> From<[I; 3]> for DerivationSeg<I> {
57    fn from(indexes: [I; 3]) -> Self { Self(Confined::from_iter_checked(indexes)) }
58}
59
60impl<I: IdxBase> From<[I; 4]> for DerivationSeg<I> {
61    fn from(indexes: [I; 4]) -> Self { Self(Confined::from_iter_checked(indexes)) }
62}
63
64impl<I: IdxBase> DerivationSeg<I> {
65    pub fn new(index: I) -> Self { DerivationSeg(NonEmptyOrdSet::with(index)) }
66
67    pub fn with(iter: impl IntoIterator<Item = I>) -> Result<Self, confinement::Error> {
68        Confined::try_from_iter(iter).map(DerivationSeg)
69    }
70
71    #[inline]
72    pub fn count(&self) -> u8 { self.0.len() as u8 }
73
74    #[inline]
75    pub fn is_distinct(&self, other: &Self) -> bool { self.0.is_disjoint(&other.0) }
76
77    #[inline]
78    pub fn at(&self, index: u8) -> Option<I> { self.0.iter().nth(index as usize).copied() }
79
80    #[inline]
81    pub fn first(&self) -> I {
82        *self
83            .0
84            .first()
85            .expect("confined type guarantees that there is at least one item in the collection")
86    }
87
88    #[inline]
89    pub fn into_set(self) -> BTreeSet<I> { self.0.release() }
90
91    #[inline]
92    pub fn to_set(&self) -> BTreeSet<I> { self.0.to_unconfined() }
93
94    #[inline]
95    pub fn as_set(&self) -> &BTreeSet<I> { self.0.as_unconfined() }
96}
97
98impl DerivationSeg<NormalIndex> {
99    pub fn standard() -> Self {
100        DerivationSeg(NonEmptyOrdSet::from_iter_checked([NormalIndex::ZERO, NormalIndex::ONE]))
101    }
102}
103
104impl<I: IdxBase> Index<u8> for DerivationSeg<I> {
105    type Output = I;
106
107    fn index(&self, index: u8) -> &Self::Output {
108        self.0
109            .iter()
110            .nth(index as usize)
111            .expect("requested position in derivation segment exceeds its length")
112    }
113}
114
115impl<I: IdxBase + Display> Display for DerivationSeg<I> {
116    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
117        if self.count() == 1 {
118            write!(f, "{}", self[0])
119        } else {
120            f.write_str("<")?;
121            let mut first = true;
122            for index in &self.0 {
123                if !first {
124                    f.write_str(";")?;
125                }
126                write!(f, "{index}")?;
127                first = false;
128            }
129            f.write_str(">")
130        }
131    }
132}
133
134#[derive(Clone, Eq, PartialEq, Debug, Display, Error, From)]
135#[display(doc_comments)]
136pub enum SegParseError {
137    /// derivation contains invalid index - {0}.
138    #[from]
139    #[from(ParseIntError)]
140    InvalidFormat(IndexParseError),
141
142    /// derivation segment contains too many variants.
143    #[from]
144    Confinement(confinement::Error),
145}
146
147impl<I: IdxBase> FromStr for DerivationSeg<I>
148where
149    I: FromStr,
150    SegParseError: From<I::Err>,
151{
152    type Err = SegParseError;
153
154    fn from_str(s: &str) -> Result<Self, Self::Err> {
155        let t = s.trim_start_matches('<').trim_end_matches('>');
156        if t.len() + 2 == s.len() {
157            let set = t.split(';').map(I::from_str).collect::<Result<BTreeSet<_>, _>>()?;
158            Ok(Self(Confined::try_from_iter(set)?))
159        } else {
160            Ok(Self(I::from_str(s).map(Confined::with)?))
161        }
162    }
163}
164
165/// Derivation path that consisting only of single type of segments.
166///
167/// Useful in specifying concrete derivation from a provided extended public key
168/// without extended private key accessible.
169///
170/// Type guarantees that the number of derivation path segments is non-zero.
171#[derive(Wrapper, WrapperMut, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Default, Debug, From)]
172#[wrapper(Deref)]
173#[wrapper_mut(DerefMut)]
174#[cfg_attr(
175    feature = "serde",
176    derive(Serialize, Deserialize),
177    serde(crate = "serde_crate", rename_all = "camelCase")
178)]
179pub struct DerivationPath<I = DerivationIndex>(Vec<I>);
180
181impl<I: Clone, const LEN: usize> From<[I; LEN]> for DerivationPath<I> {
182    fn from(path: [I; LEN]) -> Self { Self(path.to_vec()) }
183}
184
185impl<I: Clone> From<&[I]> for DerivationPath<I> {
186    fn from(path: &[I]) -> Self { Self(path.to_vec()) }
187}
188
189impl<I> AsRef<[I]> for DerivationPath<I> {
190    fn as_ref(&self) -> &[I] { self.0.as_ref() }
191}
192
193impl<I: Display> Display for DerivationPath<I> {
194    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
195        for segment in &self.0 {
196            f.write_str("/")?;
197            Display::fmt(segment, f)?;
198        }
199        Ok(())
200    }
201}
202
203impl<I: FromStr> FromStr for DerivationPath<I>
204where IndexParseError: From<<I as FromStr>::Err>
205{
206    type Err = DerivationParseError;
207
208    fn from_str(mut s: &str) -> Result<Self, Self::Err> {
209        if s.starts_with('/') {
210            s = &s[1..];
211        }
212        let inner = s
213            .split('/')
214            .map(I::from_str)
215            .collect::<Result<Vec<_>, I::Err>>()
216            .map_err(|err| DerivationParseError::InvalidIndex(s.to_owned(), err.into()))?;
217        if inner.is_empty() {
218            return Err(DerivationParseError::InvalidFormat(s.to_owned()));
219        }
220        Ok(Self(inner))
221    }
222}
223
224impl<I> IntoIterator for DerivationPath<I> {
225    type Item = I;
226    type IntoIter = std::vec::IntoIter<I>;
227
228    fn into_iter(self) -> Self::IntoIter { self.0.into_iter() }
229}
230
231impl<'path, I: Copy> IntoIterator for &'path DerivationPath<I> {
232    type Item = I;
233    type IntoIter = std::iter::Copied<std::slice::Iter<'path, I>>;
234
235    fn into_iter(self) -> Self::IntoIter { self.0.iter().copied() }
236}
237
238impl<I> FromIterator<I> for DerivationPath<I> {
239    fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self { Self(iter.into_iter().collect()) }
240}
241
242impl<I: Idx> DerivationPath<I> {
243    /// Constructs empty derivation path.
244    pub fn new() -> Self { Self(vec![]) }
245
246    pub fn with_capacity(capacity: usize) -> Self { Self(Vec::with_capacity(capacity)) }
247
248    pub fn terminal(&self) -> Option<Terminal> {
249        let mut iter = self.iter().rev();
250        let index = iter.next()?;
251        if index.is_hardened() {
252            return None;
253        }
254        let index = NormalIndex::normal(index.child_number() as u16);
255        let keychain = iter.next()?;
256        if keychain.is_hardened() {
257            return None;
258        }
259        let keychain = u8::try_from(keychain.child_number()).ok()?;
260        Some(Terminal::new(keychain, index))
261    }
262
263    pub fn shared_prefix<I2>(&self, master: impl AsRef<[I2]>) -> usize
264    where
265        I: Into<DerivationIndex>,
266        I2: Idx + Into<DerivationIndex>,
267    {
268        let master = master.as_ref();
269        if master.len() <= self.len() {
270            let shared = self
271                .iter()
272                .zip(master)
273                .take_while(|(i1, i2)| (**i1).into() == (**i2).into())
274                .count();
275            if shared == master.len() {
276                return shared;
277            }
278        }
279        0
280    }
281}
282
283#[cfg(test)]
284mod test {
285    use super::*;
286    use crate::HardenedIndex;
287
288    #[test]
289    fn altstr() {
290        let path1 = DerivationPath::<HardenedIndex>::from_str("86h/1h/0h").unwrap();
291        let path2 = DerivationPath::<HardenedIndex>::from_str("86'/1'/0'").unwrap();
292        let path3 = DerivationPath::<HardenedIndex>::from_str("86'/1h/0h").unwrap();
293        assert_eq!(path1, path2);
294        assert_eq!(path1, path3);
295    }
296}
derive/path.rs

derive/
path.rs
