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            "{block_range:?} is invalid for ScanRange({priority:?})",
54        );
55        ScanRange {
56            block_range,
57            priority,
58        }
59    }
60
61    /// Returns the range of block heights to be scanned.
62    pub fn block_range(&self) -> &Range<BlockHeight> {
63        &self.block_range
64    }
65
66    /// Returns the priority with which the scan range should be scanned.
67    pub fn priority(&self) -> ScanPriority {
68        self.priority
69    }
70
71    /// Returns whether or not the scan range is empty.
72    pub fn is_empty(&self) -> bool {
73        self.block_range.is_empty()
74    }
75
76    /// Returns the number of blocks in the scan range.
77    pub fn len(&self) -> usize {
78        usize::try_from(u32::from(self.block_range.end) - u32::from(self.block_range.start))
79            .unwrap()
80    }
81
82    /// Shifts the start of the block range to the right if `block_height >
83    /// self.block_range().start`. Returns `None` if the resulting range would
84    /// be empty (or the range was already empty).
85    pub fn truncate_start(&self, block_height: BlockHeight) -> Option<Self> {
86        if block_height >= self.block_range.end || self.is_empty() {
87            None
88        } else {
89            Some(ScanRange {
90                block_range: self.block_range.start.max(block_height)..self.block_range.end,
91                priority: self.priority,
92            })
93        }
94    }
95
96    /// Shifts the end of the block range to the left if `block_height <
97    /// self.block_range().end`. Returns `None` if the resulting range would
98    /// be empty (or the range was already empty).
99    pub fn truncate_end(&self, block_height: BlockHeight) -> Option<Self> {
100        if block_height <= self.block_range.start || self.is_empty() {
101            None
102        } else {
103            Some(ScanRange {
104                block_range: self.block_range.start..self.block_range.end.min(block_height),
105                priority: self.priority,
106            })
107        }
108    }
109
110    /// Splits this scan range at the specified height, such that the provided height becomes the
111    /// end of the first range returned and the start of the second. Returns `None` if
112    /// `p <= self.block_range().start || p >= self.block_range().end`.
113    pub fn split_at(&self, p: BlockHeight) -> Option<(Self, Self)> {
114        (p > self.block_range.start && p < self.block_range.end).then_some((
115            ScanRange {
116                block_range: self.block_range.start..p,
117                priority: self.priority,
118            },
119            ScanRange {
120                block_range: p..self.block_range.end,
121                priority: self.priority,
122            },
123        ))
124    }
125}
126
127#[cfg(test)]
128mod tests {
129    use super::{ScanPriority, ScanRange};
130
131    fn scan_range(start: u32, end: u32) -> ScanRange {
132        ScanRange::from_parts((start.into())..(end.into()), ScanPriority::Scanned)
133    }
134
135    #[test]
136    fn truncate_start() {
137        let r = scan_range(5, 8);
138
139        assert_eq!(r.truncate_start(4.into()), Some(scan_range(5, 8)));
140        assert_eq!(r.truncate_start(5.into()), Some(scan_range(5, 8)));
141        assert_eq!(r.truncate_start(6.into()), Some(scan_range(6, 8)));
142        assert_eq!(r.truncate_start(7.into()), Some(scan_range(7, 8)));
143        assert_eq!(r.truncate_start(8.into()), None);
144        assert_eq!(r.truncate_start(9.into()), None);
145
146        let empty = scan_range(5, 5);
147        assert_eq!(empty.truncate_start(4.into()), None);
148        assert_eq!(empty.truncate_start(5.into()), None);
149        assert_eq!(empty.truncate_start(6.into()), None);
150    }
151
152    #[test]
153    fn truncate_end() {
154        let r = scan_range(5, 8);
155
156        assert_eq!(r.truncate_end(9.into()), Some(scan_range(5, 8)));
157        assert_eq!(r.truncate_end(8.into()), Some(scan_range(5, 8)));
158        assert_eq!(r.truncate_end(7.into()), Some(scan_range(5, 7)));
159        assert_eq!(r.truncate_end(6.into()), Some(scan_range(5, 6)));
160        assert_eq!(r.truncate_end(5.into()), None);
161        assert_eq!(r.truncate_end(4.into()), None);
162
163        let empty = scan_range(5, 5);
164        assert_eq!(empty.truncate_end(4.into()), None);
165        assert_eq!(empty.truncate_end(5.into()), None);
166        assert_eq!(empty.truncate_end(6.into()), None);
167    }
168
169    #[test]
170    fn split_at() {
171        let r = scan_range(5, 8);
172
173        assert_eq!(r.split_at(4.into()), None);
174        assert_eq!(r.split_at(5.into()), None);
175        assert_eq!(
176            r.split_at(6.into()),
177            Some((scan_range(5, 6), scan_range(6, 8)))
178        );
179        assert_eq!(
180            r.split_at(7.into()),
181            Some((scan_range(5, 7), scan_range(7, 8)))
182        );
183        assert_eq!(r.split_at(8.into()), None);
184        assert_eq!(r.split_at(9.into()), None);
185
186        let empty = scan_range(5, 5);
187        assert_eq!(empty.split_at(4.into()), None);
188        assert_eq!(empty.split_at(5.into()), None);
189        assert_eq!(empty.split_at(6.into()), None);
190    }
191}
zcash_client_backend/data_api/scanning.rs

zcash_client_backend/data_api/
scanning.rs
