zcash_client_backend/data_api/
scanning.rs

1//! Common types used for managing a queue of scanning ranges.
2
3use std::fmt;
4use std::ops::Range;
5
6use zcash_protocol::consensus::BlockHeight;
7
8#[cfg(feature = "unstable-spanning-tree")]
9pub mod spanning_tree;
10
11/// Scanning range priority levels.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
13pub enum ScanPriority {
14    /// Block ranges that are ignored have lowest priority.
15    Ignored,
16    /// Block ranges that have already been scanned will not be re-scanned.
17    Scanned,
18    /// Block ranges to be scanned to advance the fully-scanned height.
19    Historic,
20    /// Block ranges adjacent to heights at which the user opened the wallet.
21    OpenAdjacent,
22    /// Blocks that must be scanned to complete note commitment tree shards adjacent to found notes.
23    FoundNote,
24    /// Blocks that must be scanned to complete the latest note commitment tree shard.
25    ChainTip,
26    /// A previously scanned range that must be verified to check it is still in the
27    /// main chain, has highest priority.
28    Verify,
29}
30
31/// A range of blocks to be scanned, along with its associated priority.
32#[derive(Debug, Clone, PartialEq, Eq)]
33pub struct ScanRange {
34    block_range: Range<BlockHeight>,
35    priority: ScanPriority,
36}
37
38impl fmt::Display for ScanRange {
39    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
40        write!(
41            f,
42            "{:?}({}..{})",
43            self.priority, self.block_range.start, self.block_range.end,
44        )
45    }
46}
47
48impl ScanRange {
49    /// Constructs a scan range from its constituent parts.
50    pub fn from_parts(block_range: Range<BlockHeight>, priority: ScanPriority) -> Self {
51        assert!(
52            block_range.end >= block_range.start,
53            "{:?} is invalid for ScanRange({:?})",
54            block_range,
55            priority,
56        );
57        ScanRange {
58            block_range,
59            priority,
60        }
61    }
62
63    /// Returns the range of block heights to be scanned.
64    pub fn block_range(&self) -> &Range<BlockHeight> {
65        &self.block_range
66    }
67
68    /// Returns the priority with which the scan range should be scanned.
69    pub fn priority(&self) -> ScanPriority {
70        self.priority
71    }
72
73    /// Returns whether or not the scan range is empty.
74    pub fn is_empty(&self) -> bool {
75        self.block_range.is_empty()
76    }
77
78    /// Returns the number of blocks in the scan range.
79    pub fn len(&self) -> usize {
80        usize::try_from(u32::from(self.block_range.end) - u32::from(self.block_range.start))
81            .unwrap()
82    }
83
84    /// Shifts the start of the block range to the right if `block_height >
85    /// self.block_range().start`. Returns `None` if the resulting range would
86    /// be empty (or the range was already empty).
87    pub fn truncate_start(&self, block_height: BlockHeight) -> Option<Self> {
88        if block_height >= self.block_range.end || self.is_empty() {
89            None
90        } else {
91            Some(ScanRange {
92                block_range: self.block_range.start.max(block_height)..self.block_range.end,
93                priority: self.priority,
94            })
95        }
96    }
97
98    /// Shifts the end of the block range to the left if `block_height <
99    /// self.block_range().end`. Returns `None` if the resulting range would
100    /// be empty (or the range was already empty).
101    pub fn truncate_end(&self, block_height: BlockHeight) -> Option<Self> {
102        if block_height <= self.block_range.start || self.is_empty() {
103            None
104        } else {
105            Some(ScanRange {
106                block_range: self.block_range.start..self.block_range.end.min(block_height),
107                priority: self.priority,
108            })
109        }
110    }
111
112    /// Splits this scan range at the specified height, such that the provided height becomes the
113    /// end of the first range returned and the start of the second. Returns `None` if
114    /// `p <= self.block_range().start || p >= self.block_range().end`.
115    pub fn split_at(&self, p: BlockHeight) -> Option<(Self, Self)> {
116        (p > self.block_range.start && p < self.block_range.end).then_some((
117            ScanRange {
118                block_range: self.block_range.start..p,
119                priority: self.priority,
120            },
121            ScanRange {
122                block_range: p..self.block_range.end,
123                priority: self.priority,
124            },
125        ))
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::{ScanPriority, ScanRange};
132
133    fn scan_range(start: u32, end: u32) -> ScanRange {
134        ScanRange::from_parts((start.into())..(end.into()), ScanPriority::Scanned)
135    }
136
137    #[test]
138    fn truncate_start() {
139        let r = scan_range(5, 8);
140
141        assert_eq!(r.truncate_start(4.into()), Some(scan_range(5, 8)));
142        assert_eq!(r.truncate_start(5.into()), Some(scan_range(5, 8)));
143        assert_eq!(r.truncate_start(6.into()), Some(scan_range(6, 8)));
144        assert_eq!(r.truncate_start(7.into()), Some(scan_range(7, 8)));
145        assert_eq!(r.truncate_start(8.into()), None);
146        assert_eq!(r.truncate_start(9.into()), None);
147
148        let empty = scan_range(5, 5);
149        assert_eq!(empty.truncate_start(4.into()), None);
150        assert_eq!(empty.truncate_start(5.into()), None);
151        assert_eq!(empty.truncate_start(6.into()), None);
152    }
153
154    #[test]
155    fn truncate_end() {
156        let r = scan_range(5, 8);
157
158        assert_eq!(r.truncate_end(9.into()), Some(scan_range(5, 8)));
159        assert_eq!(r.truncate_end(8.into()), Some(scan_range(5, 8)));
160        assert_eq!(r.truncate_end(7.into()), Some(scan_range(5, 7)));
161        assert_eq!(r.truncate_end(6.into()), Some(scan_range(5, 6)));
162        assert_eq!(r.truncate_end(5.into()), None);
163        assert_eq!(r.truncate_end(4.into()), None);
164
165        let empty = scan_range(5, 5);
166        assert_eq!(empty.truncate_end(4.into()), None);
167        assert_eq!(empty.truncate_end(5.into()), None);
168        assert_eq!(empty.truncate_end(6.into()), None);
169    }
170
171    #[test]
172    fn split_at() {
173        let r = scan_range(5, 8);
174
175        assert_eq!(r.split_at(4.into()), None);
176        assert_eq!(r.split_at(5.into()), None);
177        assert_eq!(
178            r.split_at(6.into()),
179            Some((scan_range(5, 6), scan_range(6, 8)))
180        );
181        assert_eq!(
182            r.split_at(7.into()),
183            Some((scan_range(5, 7), scan_range(7, 8)))
184        );
185        assert_eq!(r.split_at(8.into()), None);
186        assert_eq!(r.split_at(9.into()), None);
187
188        let empty = scan_range(5, 5);
189        assert_eq!(empty.split_at(4.into()), None);
190        assert_eq!(empty.split_at(5.into()), None);
191        assert_eq!(empty.split_at(6.into()), None);
192    }
193}
zcash_client_backend/data_api/scanning.rs

zcash_client_backend/data_api/
scanning.rs
