Skip to main content

evm_fork_cache_hypersync/
canonical.rs

1use std::collections::VecDeque;
2
3use evm_fork_cache_event_protocol::v1::BlockRef;
4
5/// Bounded canonical block history used to locate and apply replacement forks.
6#[derive(Clone, Debug)]
7pub struct CanonicalTracker {
8    depth: usize,
9    blocks: VecDeque<BlockRef>,
10}
11
12impl CanonicalTracker {
13    /// Create a tracker retaining at least one canonical block.
14    pub fn new(depth: usize) -> Self {
15        Self {
16            depth: depth.max(1),
17            blocks: VecDeque::new(),
18        }
19    }
20
21    /// Apply ordered canonical blocks, replacing a conflicting retained suffix.
22    ///
23    /// # Errors
24    ///
25    /// Returns [`CanonicalError`] when block references are malformed,
26    /// non-contiguous, conflict at the same hash, contain a gap/unknown parent,
27    /// or require history older than the retained suffix. Failure leaves the
28    /// tracker unchanged.
29    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    /// Borrow the current canonical tip.
118    pub fn tip(&self) -> Option<&BlockRef> {
119        self.blocks.back()
120    }
121
122    /// Whether no canonical checkpoint has been observed yet.
123    pub fn is_empty(&self) -> bool {
124        self.blocks.is_empty()
125    }
126
127    /// Borrow a retained canonical block by number.
128    pub fn block(&self, number: u64) -> Option<&BlockRef> {
129        self.blocks.iter().find(|block| block.number == number)
130    }
131
132    /// Find a retained canonical block by hash.
133    pub fn block_by_hash(&self, hash: &[u8]) -> Option<&BlockRef> {
134        self.blocks.iter().find(|block| block.hash == hash)
135    }
136
137    /// Borrow retained canonical history in ascending block order.
138    pub fn blocks(&self) -> impl ExactSizeIterator<Item = &BlockRef> {
139        self.blocks.iter()
140    }
141
142    /// Replace retained history from a durable source checkpoint.
143    ///
144    /// # Errors
145    ///
146    /// Returns [`CanonicalError`] when the replacement suffix is malformed or
147    /// cannot form one contiguous canonical chain. Failure preserves the
148    /// previously retained history.
149    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/// Canonical suffix replaced by a newly observed fork.
200#[derive(Clone, Debug, PartialEq, Eq)]
201#[non_exhaustive]
202pub struct ReorgDelta {
203    /// Last block shared by the old and new branches.
204    pub common_ancestor: BlockRef,
205    /// Previous canonical tip.
206    pub old_tip: BlockRef,
207    /// New canonical tip after applying the replacement.
208    pub new_tip: BlockRef,
209}
210
211/// Canonical block history could not apply an incoming page safely.
212#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
213#[non_exhaustive]
214pub enum CanonicalError {
215    /// A hash that was already retained was returned with different parent or timestamp data.
216    #[error("block {number} reused a canonical hash with conflicting metadata")]
217    ConflictingBlockMetadata {
218        /// Height of the inconsistent block reference.
219        number: u64,
220    },
221    /// Incoming provider or checkpoint blocks were not strictly contiguous and ascending.
222    #[error("canonical input is not contiguous: expected {expected}, received {received}")]
223    NonContiguousInput {
224        /// Required following block number.
225        expected: u64,
226        /// Returned following block number.
227        received: u64,
228    },
229    /// Incoming blocks skipped a required height.
230    #[error("canonical block gap: expected {expected}, received {received}")]
231    Gap {
232        /// Next required block number.
233        expected: u64,
234        /// First block received after the gap.
235        received: u64,
236    },
237    /// A replacement branch starts before retained history.
238    #[error("canonical history does not retain required block {required_block}")]
239    HistoryExhausted {
240        /// Block required to locate the common ancestor.
241        required_block: u64,
242    },
243    /// The incoming parent is not present at the preceding retained height.
244    #[error("block {number} references unknown parent {parent_hash:?}")]
245    UnknownParent {
246        /// Incoming block number.
247        number: u64,
248        /// Incoming parent hash.
249        parent_hash: Vec<u8>,
250    },
251    /// A canonical hash was not 32 bytes.
252    #[error("canonical {field} must be 32 bytes, got {width}")]
253    InvalidHashWidth {
254        /// Invalid field name.
255        field: &'static str,
256        /// Supplied byte width.
257        width: usize,
258    },
259    /// A canonical sequence attempted to advance beyond the representable block range.
260    #[error("canonical block number cannot advance beyond u64::MAX")]
261    BlockNumberOverflow,
262}