evm_fork_cache_hypersync/
canonical.rs1use std::collections::VecDeque;
2
3use evm_fork_cache_event_protocol::v1::BlockRef;
4
5#[derive(Clone, Debug)]
7pub struct CanonicalTracker {
8 depth: usize,
9 blocks: VecDeque<BlockRef>,
10}
11
12impl CanonicalTracker {
13 pub fn new(depth: usize) -> Self {
15 Self {
16 depth: depth.max(1),
17 blocks: VecDeque::new(),
18 }
19 }
20
21 pub fn apply_blocks(
30 &mut self,
31 blocks: impl IntoIterator<Item = BlockRef>,
32 ) -> Result<Option<ReorgDelta>, CanonicalError> {
33 let blocks: Vec<_> = blocks.into_iter().collect();
34 validate_input_order(&blocks)?;
35 let mut candidate = self.clone();
36 let reorg = candidate.apply_blocks_in_place(blocks)?;
37 *self = candidate;
38 Ok(reorg)
39 }
40
41 fn apply_blocks_in_place(
42 &mut self,
43 blocks: Vec<BlockRef>,
44 ) -> Result<Option<ReorgDelta>, CanonicalError> {
45 let old_tip = self.tip().cloned();
46 let mut common_ancestor = None;
47
48 for block in blocks {
49 validate_block(&block)?;
50 if let Some(existing) = self.block(block.number).cloned() {
51 if existing.hash == block.hash {
52 if existing != block {
53 return Err(CanonicalError::ConflictingBlockMetadata {
54 number: block.number,
55 });
56 }
57 continue;
58 }
59 let ancestor_number =
60 block
61 .number
62 .checked_sub(1)
63 .ok_or(CanonicalError::UnknownParent {
64 number: block.number,
65 parent_hash: block.parent_hash.clone(),
66 })?;
67 let ancestor = self.block(ancestor_number).cloned().ok_or({
68 CanonicalError::HistoryExhausted {
69 required_block: ancestor_number,
70 }
71 })?;
72 if ancestor.hash != block.parent_hash {
73 return Err(CanonicalError::UnknownParent {
74 number: block.number,
75 parent_hash: block.parent_hash,
76 });
77 }
78 if common_ancestor.is_none() {
79 common_ancestor = Some(ancestor.clone());
80 }
81 while self.tip().is_some_and(|tip| tip.number > ancestor.number) {
82 self.blocks.pop_back();
83 }
84 self.push(block);
85 continue;
86 }
87
88 match self.tip() {
89 None => self.push(block),
90 Some(tip)
91 if block.number == tip.number.saturating_add(1)
92 && block.parent_hash == tip.hash =>
93 {
94 self.push(block)
95 }
96 Some(tip) if block.number > tip.number.saturating_add(1) => {
97 return Err(CanonicalError::Gap {
98 expected: tip.number.saturating_add(1),
99 received: block.number,
100 });
101 }
102 Some(_) => {
103 return Err(CanonicalError::HistoryExhausted {
104 required_block: block.number,
105 });
106 }
107 }
108 }
109
110 Ok(common_ancestor.map(|common_ancestor| ReorgDelta {
111 common_ancestor,
112 old_tip: old_tip.expect("a reorg requires existing history"),
113 new_tip: self.tip().expect("replacement branch has a tip").clone(),
114 }))
115 }
116
117 pub fn tip(&self) -> Option<&BlockRef> {
119 self.blocks.back()
120 }
121
122 pub fn is_empty(&self) -> bool {
124 self.blocks.is_empty()
125 }
126
127 pub fn block(&self, number: u64) -> Option<&BlockRef> {
129 self.blocks.iter().find(|block| block.number == number)
130 }
131
132 pub fn block_by_hash(&self, hash: &[u8]) -> Option<&BlockRef> {
134 self.blocks.iter().find(|block| block.hash == hash)
135 }
136
137 pub fn blocks(&self) -> impl ExactSizeIterator<Item = &BlockRef> {
139 self.blocks.iter()
140 }
141
142 pub fn restore_blocks(
150 &mut self,
151 blocks: impl IntoIterator<Item = BlockRef>,
152 ) -> Result<(), CanonicalError> {
153 let mut replacement = Self::new(self.depth);
154 replacement.apply_blocks(blocks)?;
155 *self = replacement;
156 Ok(())
157 }
158
159 fn push(&mut self, block: BlockRef) {
160 self.blocks.push_back(block);
161 while self.blocks.len() > self.depth {
162 self.blocks.pop_front();
163 }
164 }
165}
166
167fn validate_input_order(blocks: &[BlockRef]) -> Result<(), CanonicalError> {
168 for pair in blocks.windows(2) {
169 let expected = pair[0]
170 .number
171 .checked_add(1)
172 .ok_or(CanonicalError::BlockNumberOverflow)?;
173 if pair[1].number != expected {
174 return Err(CanonicalError::NonContiguousInput {
175 expected,
176 received: pair[1].number,
177 });
178 }
179 }
180 Ok(())
181}
182
183fn validate_block(block: &BlockRef) -> Result<(), CanonicalError> {
184 if block.hash.len() != 32 {
185 return Err(CanonicalError::InvalidHashWidth {
186 field: "hash",
187 width: block.hash.len(),
188 });
189 }
190 if block.parent_hash.len() != 32 {
191 return Err(CanonicalError::InvalidHashWidth {
192 field: "parent_hash",
193 width: block.parent_hash.len(),
194 });
195 }
196 Ok(())
197}
198
199#[derive(Clone, Debug, PartialEq, Eq)]
201#[non_exhaustive]
202pub struct ReorgDelta {
203 pub common_ancestor: BlockRef,
205 pub old_tip: BlockRef,
207 pub new_tip: BlockRef,
209}
210
211#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
213#[non_exhaustive]
214pub enum CanonicalError {
215 #[error("block {number} reused a canonical hash with conflicting metadata")]
217 ConflictingBlockMetadata {
218 number: u64,
220 },
221 #[error("canonical input is not contiguous: expected {expected}, received {received}")]
223 NonContiguousInput {
224 expected: u64,
226 received: u64,
228 },
229 #[error("canonical block gap: expected {expected}, received {received}")]
231 Gap {
232 expected: u64,
234 received: u64,
236 },
237 #[error("canonical history does not retain required block {required_block}")]
239 HistoryExhausted {
240 required_block: u64,
242 },
243 #[error("block {number} references unknown parent {parent_hash:?}")]
245 UnknownParent {
246 number: u64,
248 parent_hash: Vec<u8>,
250 },
251 #[error("canonical {field} must be 32 bytes, got {width}")]
253 InvalidHashWidth {
254 field: &'static str,
256 width: usize,
258 },
259 #[error("canonical block number cannot advance beyond u64::MAX")]
261 BlockNumberOverflow,
262}