Skip to main content

reth_chain_state/in_memory/
blocks.rs

1use super::{canonical::InMemoryStateBlockCounts, BlockState, ExecutedBlock, NewCanonicalChain};
2use alloy_consensus::BlockHeader;
3use alloy_eips::BlockNumHash;
4use alloy_primitives::{
5    map::{B256Map, B256Set},
6    BlockNumber, B256,
7};
8use reth_primitives_traits::NodePrimitives;
9use std::{cmp::Reverse, collections::BTreeMap, sync::Arc};
10
11/// All executed in-memory blocks, split into the canonical and the non-canonical section.
12///
13/// # Invariants
14///
15/// - **I1** Every tracked block is in exactly one section.
16/// - **I2** The number index of the canonical section and its blocks describe the same blocks. The
17///   number index and the parent index of the non-canonical section describe exactly its blocks and
18///   hold no empty set.
19/// - **I3** A canonical block links to the state tracked for its parent in the canonical section, a
20///   non-canonical block to the state tracked for its parent in either section. Without such a
21///   parent the link is `None`.
22/// - **I4** The canonical section is one chain: the parent links of its head cover exactly the
23///   canonical section.
24/// - **I5** The pending hash, if set, names a tracked block.
25///
26/// # Parent links
27///
28/// The parent link of a [`BlockState`] is immutable, so that a state is one consistent snapshot
29/// of a block and its ancestors. A block whose parent link has to change is therefore replaced by
30/// a new state, and so is every tracked block built on it, because a block points at its parent.
31/// Removing the oldest blocks of a chain replaces every tracked block above them. Each
32/// replacement is one allocation, and their number is bounded by the number of tracked blocks.
33#[derive(Debug, Default)]
34pub(super) struct InMemoryBlocks<N: NodePrimitives> {
35    /// The canonical chain above the persisted frontier.
36    canonical: InMemoryCanonicalBlocks<N>,
37    /// Executed blocks that are not canonical.
38    non_canonical: InMemoryNonCanonicalBlocks<N>,
39    /// Hash of the pending block.
40    pending_hash: Option<B256>,
41    /// Hashes of the blocks whose parent link may be stale, see [`Self::relink`].
42    ///
43    /// This is empty between operations and kept to reuse its allocation.
44    relink_queue: Vec<B256>,
45    /// Number of blocks removed so far.
46    removed_count: u64,
47}
48
49impl<N: NodePrimitives> InMemoryBlocks<N> {
50    /// Creates the blocks from the canonical blocks, their numbers and the pending block.
51    pub(super) fn new(
52        blocks: B256Map<Arc<BlockState<N>>>,
53        numbers: BTreeMap<BlockNumber, B256>,
54        pending: Option<BlockState<N>>,
55    ) -> Self {
56        let mut this =
57            Self { canonical: InMemoryCanonicalBlocks { blocks, numbers }, ..Default::default() };
58        if let Some(pending) = pending {
59            this.pending_hash = Some(pending.hash());
60            this.non_canonical.insert(Arc::new(pending));
61        }
62        this
63    }
64
65    /// Returns the state of the tracked block with the given hash, canonical or not.
66    pub(super) fn get(&self, hash: &B256) -> Option<&Arc<BlockState<N>>> {
67        self.canonical.get(hash).or_else(|| self.non_canonical.blocks.get(hash))
68    }
69
70    /// Returns `true` if a block with the given hash is tracked, canonical or not.
71    pub(super) fn contains(&self, hash: &B256) -> bool {
72        self.canonical.blocks.contains_key(hash) || self.non_canonical.blocks.contains_key(hash)
73    }
74
75    /// Returns the canonical section.
76    pub(super) const fn canonical(&self) -> &InMemoryCanonicalBlocks<N> {
77        &self.canonical
78    }
79
80    /// Returns the state of the pending block, if there is one.
81    pub(super) fn pending_state(&self) -> Option<&Arc<BlockState<N>>> {
82        self.pending_hash.and_then(|hash| self.get(&hash))
83    }
84
85    /// Returns the number of tracked blocks per section.
86    pub(super) fn counts(&self) -> InMemoryStateBlockCounts {
87        InMemoryStateBlockCounts {
88            canonical: self.canonical.blocks.len(),
89            non_canonical: self.non_canonical.blocks.len(),
90        }
91    }
92
93    /// Returns the number of canonical blocks and the lowest and highest of their numbers.
94    pub(super) fn stats(&self) -> InMemoryBlocksStats {
95        let numbers = &self.canonical.numbers;
96        InMemoryBlocksStats {
97            count: numbers.len(),
98            earliest: numbers.first_key_value().map(|(number, _)| *number),
99            latest: numbers.last_key_value().map(|(number, _)| *number),
100        }
101    }
102
103    /// Returns the number of blocks that were removed so far. It never decreases.
104    pub(super) const fn removed_count(&self) -> u64 {
105        self.removed_count
106    }
107
108    /// Inserts `block` into the non-canonical section unless it is already tracked.
109    ///
110    /// Does not change the pending block. Returns `true` if the block was inserted.
111    pub(super) fn insert_executed(&mut self, block: ExecutedBlock<N>) -> bool {
112        if self.contains(&block.recovered_block().hash()) {
113            return false
114        }
115        let parent = self.linked_parent(&block.recovered_block().parent_hash(), false).cloned();
116        let state = Arc::new(BlockState::with_parent(block, parent));
117        // Blocks built on this one can already be tracked, for example if it was removed as
118        // persisted before.
119        self.queue_children_of(&state);
120        self.non_canonical.insert(state);
121        self.relink();
122        true
123    }
124
125    /// Inserts `block` like [`Self::insert_executed`] and makes it the pending block, also if it
126    /// is already tracked.
127    ///
128    /// Returns `true` if the block was inserted.
129    pub(super) fn insert_pending(&mut self, block: ExecutedBlock<N>) -> bool {
130        let hash = block.recovered_block().hash();
131        let inserted = self.insert_executed(block);
132        self.pending_hash = Some(hash);
133        inserted
134    }
135
136    /// Makes the new blocks of `new_chain` the top of the canonical chain, see
137    /// [`Self::set_canonical_chain`], and inserts the blocks a reorg replaced that are not tracked
138    /// into the non-canonical section.
139    pub(super) fn update_chain(&mut self, new_chain: NewCanonicalChain<N>) {
140        match new_chain {
141            NewCanonicalChain::Commit { new } => self.set_canonical_chain(new),
142            NewCanonicalChain::Reorg { new, old } => {
143                self.set_canonical_chain(new);
144                // The tracked ones were moved to the non-canonical section above.
145                for block in old {
146                    self.insert_executed(block);
147                }
148            }
149        }
150    }
151
152    /// Makes `new`, a chain of blocks from oldest to newest, the top of the canonical chain and
153    /// clears the pending block.
154    ///
155    /// Afterwards the canonical section consists of the blocks of `new` and of the canonical
156    /// blocks below the first of them that it builds on. Every other canonical block is moved to
157    /// the non-canonical section. A block of `new` that is tracked as non-canonical is moved to
158    /// the canonical section, one that is not tracked is inserted into it.
159    pub(super) fn set_canonical_chain(&mut self, new: Vec<ExecutedBlock<N>>) {
160        debug_assert!(
161            new.windows(2).all(|blocks| {
162                blocks[1].recovered_block().parent_hash() == blocks[0].recovered_block().hash()
163            }),
164            "the new canonical blocks are not a chain"
165        );
166        let Some(first) = new.first() else {
167            debug_assert!(false, "the new canonical chain is empty");
168            return
169        };
170        let first_number = first.block_number();
171
172        // The canonical blocks below the first new block stay canonical if the new chain builds
173        // on them. They are one chain, so it is enough to compare the highest of them.
174        let builds_on_canonical = self
175            .canonical
176            .numbers
177            .range(..first_number)
178            .next_back()
179            .is_none_or(|(_, hash)| *hash == first.recovered_block().parent_hash());
180        debug_assert!(
181            builds_on_canonical,
182            "the new canonical chain does not build on the canonical blocks below it"
183        );
184        let first_demoted = if builds_on_canonical { first_number } else { BlockNumber::MIN };
185        let demoted = self
186            .canonical
187            .numbers
188            .range(first_demoted..)
189            .filter(|(number, hash)| {
190                // The new blocks are a chain, so the one at a height is found by its offset.
191                number
192                    .checked_sub(first_number)
193                    .and_then(|offset| new.get(offset as usize))
194                    .is_none_or(|block| block.recovered_block().hash() != **hash)
195            })
196            .map(|(_, hash)| *hash)
197            .collect::<Vec<_>>();
198        for hash in demoted {
199            let state = self.canonical.remove(&hash);
200            self.queue_moved(&state);
201            self.non_canonical.insert(state);
202        }
203
204        for block in new {
205            let hash = block.recovered_block().hash();
206            if self.canonical.blocks.contains_key(&hash) {
207                continue
208            }
209            let state = if self.non_canonical.blocks.contains_key(&hash) {
210                self.non_canonical.remove(&hash)
211            } else {
212                let parent =
213                    self.linked_parent(&block.recovered_block().parent_hash(), true).cloned();
214                Arc::new(BlockState::with_parent(block, parent))
215            };
216            self.queue_moved(&state);
217            self.canonical.insert(state);
218        }
219
220        self.pending_hash = None;
221        self.relink();
222    }
223
224    /// Moves every canonical block to the non-canonical section and clears the pending block.
225    pub(super) fn demote_canonical_chain(&mut self) {
226        let canonical = std::mem::take(&mut self.canonical);
227        // Only the link of the oldest block can be stale: as a non-canonical block it links to a
228        // non-canonical parent.
229        self.relink_queue.extend(canonical.numbers.first_key_value().map(|(_, hash)| *hash));
230        for state in canonical.blocks.into_values() {
231            self.non_canonical.insert(state);
232        }
233        self.pending_hash = None;
234        self.relink();
235    }
236
237    /// Removes the canonical blocks up to and including `remove_until` and returns their states,
238    /// oldest first.
239    ///
240    /// Removes nothing if `persisted_hash` is neither a canonical block nor the block the
241    /// canonical chain builds on. Clears the pending block if it was removed.
242    pub(super) fn remove_canonical_until(
243        &mut self,
244        persisted_hash: B256,
245        remove_until: BlockNumber,
246    ) -> Vec<Arc<BlockState<N>>> {
247        // If the persisted hash is not on the canonical chain, canonical blocks were not actually
248        // persisted. This can happen if persisting takes a long time while a reorg is happening.
249        if !self.canonical.contains_or_builds_on(&persisted_hash) {
250            return Vec::new()
251        }
252        let removed = self.canonical.remove_until(remove_until);
253        self.finish_removal(&removed);
254        removed
255    }
256
257    /// Removes the non-canonical blocks that can never become canonical once `finalized` is
258    /// final, and returns their states: the non-canonical blocks below its height, the other
259    /// non-canonical blocks at its height, and every block built on such a block at its height.
260    ///
261    /// Clears the pending block if it was removed.
262    pub(super) fn prune_conflicting_with_finalized(
263        &mut self,
264        finalized: BlockNumHash,
265    ) -> Vec<Arc<BlockState<N>>> {
266        let removed = self.non_canonical.remove_conflicting_with(finalized);
267        self.finish_removal(&removed);
268        removed
269    }
270
271    /// Removes the non-canonical blocks whose chain builds on a block above `persisted_number`,
272    /// the height of the persisted tip, and returns their states.
273    ///
274    /// The block such a chain builds on is neither tracked nor persisted, which happens when
275    /// blocks are removed from disk. The removed blocks can only be executed again once that
276    /// block is.
277    ///
278    /// Clears the pending block if it was removed.
279    pub(super) fn prune_built_above(
280        &mut self,
281        persisted_number: BlockNumber,
282    ) -> Vec<Arc<BlockState<N>>> {
283        let removed = self.non_canonical.remove_built_above(persisted_number);
284        self.finish_removal(&removed);
285        removed
286    }
287
288    /// Removes all blocks of both sections, clears the pending block and returns what was
289    /// tracked.
290    pub(super) fn clear(&mut self) -> Self {
291        let removed_count = self.removed_count +
292            (self.canonical.blocks.len() + self.non_canonical.blocks.len()) as u64;
293        std::mem::replace(self, Self { removed_count, ..Default::default() })
294    }
295
296    /// Asserts the invariants of this type.
297    #[cfg(any(test, debug_assertions))]
298    pub(super) fn assert_invariants(&self) {
299        let Self { canonical, non_canonical, pending_hash, relink_queue, removed_count: _ } = self;
300
301        // I1 and I2.
302        assert_eq!(canonical.numbers.len(), canonical.blocks.len());
303        for (number, hash) in &canonical.numbers {
304            assert_eq!(canonical.blocks[hash].number(), *number);
305            assert!(!non_canonical.blocks.contains_key(hash), "block {hash} is in both sections");
306        }
307        for (number, hashes) in &non_canonical.numbers {
308            assert!(!hashes.is_empty(), "the number index holds an empty set");
309            for hash in hashes {
310                assert_eq!(non_canonical.blocks[hash].number(), *number);
311            }
312        }
313        for (parent_hash, hashes) in &non_canonical.children {
314            assert!(!hashes.is_empty(), "the parent index holds an empty set");
315            for hash in hashes {
316                assert_eq!(non_canonical.blocks[hash].parent_hash(), *parent_hash);
317            }
318        }
319        for index in [
320            non_canonical.numbers.values().map(B256Set::len).sum::<usize>(),
321            non_canonical.children.values().map(B256Set::len).sum::<usize>(),
322        ] {
323            assert_eq!(index, non_canonical.blocks.len(), "an index misses non-canonical blocks");
324        }
325
326        // I3.
327        assert!(relink_queue.is_empty(), "blocks are still queued for relinking");
328        for state in canonical.blocks.values().chain(non_canonical.blocks.values()) {
329            let is_canonical = canonical.blocks.contains_key(&state.hash());
330            match (state.parent.as_ref(), self.linked_parent(&state.parent_hash(), is_canonical)) {
331                (None, None) => {}
332                (Some(linked), Some(parent)) if Arc::ptr_eq(linked, parent) => {}
333                (linked, parent) => panic!(
334                    "block {} is linked to {:?}, but its tracked parent is {:?}",
335                    state.hash(),
336                    linked.map(|linked| linked.hash()),
337                    parent.map(|parent| parent.hash()),
338                ),
339            }
340        }
341
342        // I4.
343        assert_eq!(
344            canonical.head().map_or(0, |head| head.chain().count()),
345            canonical.blocks.len(),
346            "the canonical section is not one chain"
347        );
348
349        // I5.
350        assert!(
351            pending_hash.is_none_or(|hash| self.contains(&hash)),
352            "the pending block is not tracked"
353        );
354    }
355
356    /// Returns the state a block in the given section links to as its parent.
357    ///
358    /// A canonical block only links to a canonical parent. A non-canonical block links to its
359    /// parent in either section.
360    fn linked_parent(&self, parent_hash: &B256, canonical: bool) -> Option<&Arc<BlockState<N>>> {
361        if canonical {
362            self.canonical.get(parent_hash)
363        } else {
364            self.get(parent_hash)
365        }
366    }
367
368    /// Returns the hashes of all blocks, in either section, that are built on `parent`.
369    fn children_of(&self, parent: &BlockState<N>) -> impl Iterator<Item = B256> + '_ {
370        self.canonical.children_of(parent).chain(self.non_canonical.children_of(parent))
371    }
372
373    /// Queues the blocks built on `parent`, a block that was inserted or removed, for
374    /// [`Self::relink`].
375    fn queue_children_of(&mut self, parent: &BlockState<N>) {
376        let mut queue = std::mem::take(&mut self.relink_queue);
377        queue.extend(self.children_of(parent));
378        self.relink_queue = queue;
379    }
380
381    /// Queues `state`, a block that changes section, and the blocks built on it for
382    /// [`Self::relink`].
383    fn queue_moved(&mut self, state: &BlockState<N>) {
384        self.relink_queue.push(state.hash());
385        self.queue_children_of(state);
386    }
387
388    /// Replaces every queued block whose parent link does not point at the state
389    /// [`Self::linked_parent`] returns for it by a state with that link, and does the same for
390    /// the blocks built on a replaced block.
391    fn relink(&mut self) {
392        let mut queue = std::mem::take(&mut self.relink_queue);
393        // The oldest block is visited first, and the blocks built on a replaced block right
394        // after it. Every block is then visited after its ancestors and replaced at most once.
395        queue.sort_unstable_by_key(|hash| Reverse(self.get(hash).map(|state| state.number())));
396        while let Some(hash) = queue.pop() {
397            let canonical = self.canonical.blocks.contains_key(&hash);
398            let Some(state) = self.get(&hash) else {
399                debug_assert!(false, "block {hash} is queued for relinking but not tracked");
400                continue
401            };
402            let parent = self.linked_parent(&state.parent_hash(), canonical);
403            let linked = match (state.parent.as_ref(), parent) {
404                (None, None) => true,
405                (Some(linked), Some(parent)) => Arc::ptr_eq(linked, parent),
406                _ => false,
407            };
408            if linked {
409                continue
410            }
411            let relinked = Arc::new(BlockState::with_parent(state.block(), parent.cloned()));
412            queue.extend(self.children_of(&relinked));
413            let section =
414                if canonical { &mut self.canonical.blocks } else { &mut self.non_canonical.blocks };
415            section.insert(hash, relinked);
416        }
417        self.relink_queue = queue;
418    }
419
420    /// Counts the `removed` blocks, clears the pending block if it is one of them, and relinks
421    /// the blocks built on them.
422    fn finish_removal(&mut self, removed: &[Arc<BlockState<N>>]) {
423        self.removed_count += removed.len() as u64;
424        if self.pending_hash.is_some_and(|hash| !self.contains(&hash)) {
425            self.pending_hash = None;
426        }
427        for state in removed {
428            self.queue_children_of(state);
429        }
430        self.relink();
431    }
432}
433
434/// The canonical chain above the persisted frontier.
435#[derive(Debug, Default)]
436pub(super) struct InMemoryCanonicalBlocks<N: NodePrimitives> {
437    /// Canonical blocks by hash.
438    blocks: B256Map<Arc<BlockState<N>>>,
439    /// Canonical block hashes by number.
440    numbers: BTreeMap<BlockNumber, B256>,
441}
442
443impl<N: NodePrimitives> InMemoryCanonicalBlocks<N> {
444    /// Returns the state of the canonical block with the given hash.
445    pub(super) fn get(&self, hash: &B256) -> Option<&Arc<BlockState<N>>> {
446        self.blocks.get(hash)
447    }
448
449    /// Returns the state of the canonical block with the given number.
450    pub(super) fn by_number(&self, number: BlockNumber) -> Option<&Arc<BlockState<N>>> {
451        self.numbers.get(&number).and_then(|hash| self.blocks.get(hash))
452    }
453
454    /// Returns the hash of the canonical block with the given number.
455    pub(super) fn hash_by_number(&self, number: BlockNumber) -> Option<B256> {
456        self.numbers.get(&number).copied()
457    }
458
459    /// Returns the state of the highest canonical block.
460    pub(super) fn head(&self) -> Option<&Arc<BlockState<N>>> {
461        self.numbers.last_key_value().and_then(|(_, hash)| self.blocks.get(hash))
462    }
463
464    /// Returns the number of canonical blocks.
465    #[cfg(test)]
466    pub(super) fn len(&self) -> usize {
467        self.blocks.len()
468    }
469
470    /// Returns `true` if `hash` is a canonical in-memory block or the block the chain builds on.
471    ///
472    /// This is whether [`BlockState::chain_hashes`] of the head contains `hash`, answered from
473    /// the indexes.
474    fn contains_or_builds_on(&self, hash: &B256) -> bool {
475        self.blocks.contains_key(hash) ||
476            self.numbers
477                .first_key_value()
478                .and_then(|(_, first)| self.blocks.get(first))
479                .is_some_and(|first| first.parent_hash() == *hash)
480    }
481
482    /// Returns the hash of the canonical block built on `parent`, if there is one.
483    fn children_of(&self, parent: &BlockState<N>) -> impl Iterator<Item = B256> + '_ {
484        let parent_hash = parent.hash();
485        parent
486            .number()
487            .checked_add(1)
488            .and_then(|number| self.by_number(number))
489            .filter(|child| child.parent_hash() == parent_hash)
490            .map(|child| child.hash())
491            .into_iter()
492    }
493
494    /// Makes `state` the canonical block at its height, which must be vacant.
495    fn insert(&mut self, state: Arc<BlockState<N>>) {
496        let hash = state.hash();
497        let displaced = self.numbers.insert(state.number(), hash);
498        debug_assert!(displaced.is_none(), "canonical height {} is not vacant", state.number());
499        self.blocks.insert(hash, state);
500    }
501
502    /// Removes the canonical block with the given hash and returns its state.
503    ///
504    /// # Panics
505    ///
506    /// If the block is not canonical.
507    fn remove(&mut self, hash: &B256) -> Arc<BlockState<N>> {
508        let Some(state) = self.blocks.remove(hash) else {
509            unreachable!("block {hash} is not canonical")
510        };
511        let indexed = self.numbers.remove(&state.number());
512        debug_assert_eq!(indexed, Some(*hash), "canonical block {hash} is not indexed by number");
513        state
514    }
515
516    /// Removes the canonical blocks up to and including `number` and returns their states,
517    /// oldest first.
518    fn remove_until(&mut self, number: BlockNumber) -> Vec<Arc<BlockState<N>>> {
519        let mut removed = Vec::new();
520        while let Some(first) = self.numbers.first_entry() &&
521            *first.key() <= number
522        {
523            let hash = first.remove();
524            let Some(state) = self.blocks.remove(&hash) else {
525                unreachable!("canonical block {hash} is indexed by number but not tracked")
526            };
527            removed.push(state);
528        }
529        removed
530    }
531}
532
533/// Executed blocks that are not canonical.
534///
535/// These are blocks that were validated but are not (yet) part of the canonical chain: blocks
536/// that were executed but not made canonical, blocks of forks, and blocks a reorg moved off the
537/// canonical chain. They stay here until they become canonical or can no longer become canonical.
538#[derive(Debug, Default)]
539pub(super) struct InMemoryNonCanonicalBlocks<N: NodePrimitives> {
540    /// Non-canonical blocks by hash.
541    blocks: B256Map<Arc<BlockState<N>>>,
542    /// Non-canonical block hashes by number. Forks can put several blocks at the same height.
543    numbers: BTreeMap<BlockNumber, B256Set>,
544    /// Non-canonical block hashes by parent hash. The parent can be non-canonical, canonical or
545    /// not tracked.
546    children: B256Map<B256Set>,
547}
548
549impl<N: NodePrimitives> InMemoryNonCanonicalBlocks<N> {
550    /// Returns the hashes of the non-canonical blocks built on `parent`.
551    fn children_of(&self, parent: &BlockState<N>) -> impl Iterator<Item = B256> + '_ {
552        self.children.get(&parent.hash()).into_iter().flatten().copied()
553    }
554
555    /// Inserts `state`, the state of a block that is not tracked, and indexes it.
556    fn insert(&mut self, state: Arc<BlockState<N>>) {
557        let hash = state.hash();
558        self.numbers.entry(state.number()).or_default().insert(hash);
559        self.children.entry(state.parent_hash()).or_default().insert(hash);
560        let replaced = self.blocks.insert(hash, state);
561        debug_assert!(replaced.is_none(), "block {hash} is already non-canonical");
562    }
563
564    /// Removes the non-canonical block with the given hash from the blocks and the indexes, and
565    /// returns its state.
566    ///
567    /// # Panics
568    ///
569    /// If the block is not non-canonical.
570    fn remove(&mut self, hash: &B256) -> Arc<BlockState<N>> {
571        let Some(state) = self.blocks.remove(hash) else {
572            unreachable!("block {hash} is not non-canonical")
573        };
574        if remove_indexed(self.numbers.get_mut(&state.number()), hash) {
575            self.numbers.remove(&state.number());
576        }
577        if remove_indexed(self.children.get_mut(&state.parent_hash()), hash) {
578            self.children.remove(&state.parent_hash());
579        }
580        state
581    }
582
583    /// Removes the blocks that can never become canonical once `finalized` is final, and returns
584    /// their states: the blocks below its height, the other blocks at its height, and every block
585    /// built on such a block at its height.
586    fn remove_conflicting_with(&mut self, finalized: BlockNumHash) -> Vec<Arc<BlockState<N>>> {
587        let mut removed = Vec::new();
588        while let Some(hash) = self
589            .numbers
590            .first_key_value()
591            .filter(|(number, _)| **number < finalized.number)
592            .and_then(|(_, hashes)| hashes.iter().next().copied())
593        {
594            removed.push(self.remove(&hash));
595        }
596
597        // The blocks removed from here on are the queue of blocks whose children are removed
598        // next. The blocks below the finalized height are not part of it, because the finalized
599        // block is built on one of them.
600        let mut next = removed.len();
601        while let Some(hash) = self
602            .numbers
603            .get(&finalized.number)
604            .and_then(|hashes| hashes.iter().find(|hash| **hash != finalized.hash).copied())
605        {
606            removed.push(self.remove(&hash));
607        }
608        while next < removed.len() {
609            let parent_hash = removed[next].hash();
610            while let Some(hash) =
611                self.children.get(&parent_hash).and_then(|hashes| hashes.iter().next().copied())
612            {
613                removed.push(self.remove(&hash));
614            }
615            next += 1;
616        }
617        removed
618    }
619
620    /// Removes the blocks whose chain builds on a block above `persisted_number`, and returns
621    /// their states.
622    fn remove_built_above(&mut self, persisted_number: BlockNumber) -> Vec<Arc<BlockState<N>>> {
623        // A chain that builds on a block above the persisted height starts two blocks above it
624        // at the lowest.
625        let hashes = self
626            .numbers
627            .range(persisted_number.saturating_add(2)..)
628            .flat_map(|(_, hashes)| hashes)
629            .filter(|hash| self.blocks[*hash].anchor().number > persisted_number)
630            .copied()
631            .collect::<Vec<_>>();
632        hashes.iter().map(|hash| self.remove(hash)).collect()
633    }
634}
635
636/// The number of canonical blocks in memory and the lowest and highest of their numbers.
637#[derive(Debug)]
638pub(super) struct InMemoryBlocksStats {
639    /// The number of canonical blocks.
640    pub(super) count: usize,
641    /// The number of the earliest canonical block.
642    pub(super) earliest: Option<BlockNumber>,
643    /// The number of the latest canonical block.
644    pub(super) latest: Option<BlockNumber>,
645}
646
647/// Removes `hash` from `hashes`, the set an index of the non-canonical section holds for a block,
648/// and returns `true` if the set is empty afterwards and has to be removed from the index.
649fn remove_indexed(hashes: Option<&mut B256Set>, hash: &B256) -> bool {
650    let Some(hashes) = hashes else {
651        debug_assert!(false, "non-canonical block {hash} is not indexed");
652        return false
653    };
654    let removed = hashes.remove(hash);
655    debug_assert!(removed, "non-canonical block {hash} is not indexed");
656    hashes.is_empty()
657}
658
659#[cfg(test)]
660mod tests {
661    use super::*;
662    use crate::test_utils::TestBlockBuilder;
663    use reth_ethereum_primitives::EthPrimitives;
664
665    fn hash(block: &ExecutedBlock) -> B256 {
666        block.recovered_block().hash()
667    }
668
669    /// Returns the hashes the non-canonical section indexes as built on `parent`.
670    fn non_canonical_children(
671        blocks: &InMemoryBlocks<EthPrimitives>,
672        parent: &ExecutedBlock,
673    ) -> B256Set {
674        blocks.non_canonical.children.get(&hash(parent)).cloned().unwrap_or_default()
675    }
676
677    /// Returns the number of canonical and of non-canonical blocks.
678    fn counts(blocks: &InMemoryBlocks<EthPrimitives>) -> (usize, usize) {
679        (blocks.canonical.blocks.len(), blocks.non_canonical.blocks.len())
680    }
681
682    /// Returns the hashes both sections index at the given height, the canonical one first.
683    fn hashes_at(blocks: &InMemoryBlocks<EthPrimitives>, number: BlockNumber) -> Vec<B256> {
684        let canonical = blocks.canonical.numbers.get(&number).into_iter();
685        let non_canonical = blocks.non_canonical.numbers.get(&number).into_iter().flatten();
686        canonical.chain(non_canonical).copied().collect()
687    }
688
689    #[test]
690    fn executed_blocks_move_between_sections_and_are_relinked_on_trim() {
691        let mut builder = TestBlockBuilder::eth();
692        let mut blocks = InMemoryBlocks::<EthPrimitives>::default();
693
694        // Blocks are executed first and made canonical afterwards.
695        let canonical = builder.get_executed_blocks(1..4).collect::<Vec<_>>();
696        let inserted = canonical
697            .iter()
698            .map(|block| {
699                assert!(blocks.insert_executed(block.clone()));
700                Arc::clone(blocks.get(&hash(block)).unwrap())
701            })
702            .collect::<Vec<_>>();
703        assert_eq!(counts(&blocks), (0, 3));
704        assert!(blocks.canonical().head().is_none());
705        assert!(Arc::ptr_eq(inserted[2].parent.as_ref().unwrap(), &inserted[1]));
706
707        blocks.set_canonical_chain(canonical.clone());
708        assert_eq!(counts(&blocks), (3, 0));
709        for (block, before) in canonical.iter().zip(&inserted) {
710            let after = blocks.canonical().get(&hash(block)).unwrap();
711            assert!(Arc::ptr_eq(before, after), "a block whose parent link is unchanged is moved");
712        }
713
714        // A fork off block 1 and the pending block on top of the head are not canonical.
715        let fork = builder.get_executed_block_with_number(2, hash(&canonical[0]));
716        assert!(blocks.insert_executed(fork.clone()));
717        let pending = builder.get_executed_block_with_number(4, hash(&canonical[2]));
718        assert!(blocks.insert_pending(pending.clone()));
719        assert!(blocks.canonical().get(&hash(&fork)).is_none());
720        assert!(blocks.canonical().get(&hash(&pending)).is_none());
721        assert_eq!(
722            non_canonical_children(&blocks, &canonical[0]),
723            B256Set::from_iter([hash(&fork)])
724        );
725        assert_eq!(hashes_at(&blocks, 2), vec![hash(&canonical[1]), hash(&fork)]);
726        assert_eq!(blocks.get(&hash(&fork)).unwrap().chain().count(), 2);
727        assert_eq!(blocks.pending_state().unwrap().hash(), hash(&pending));
728        assert_eq!(blocks.pending_state().unwrap().chain().count(), 4);
729
730        // Removing the blocks up to block 2 relinks every remaining block, canonical or not, so
731        // nothing keeps the removed blocks alive.
732        let trimmed = inserted[..2].iter().map(Arc::downgrade).collect::<Vec<_>>();
733        drop(inserted);
734        let persisted = canonical[1].recovered_block().num_hash();
735        let removed = blocks.remove_canonical_until(persisted.hash, persisted.number);
736        assert_eq!(
737            removed.iter().map(|state| state.hash()).collect::<Vec<_>>(),
738            vec![hash(&canonical[0]), hash(&canonical[1])]
739        );
740        drop(removed);
741        assert!(trimmed.iter().all(|state| state.upgrade().is_none()), "removed blocks are pinned");
742
743        let head = blocks.canonical().head().unwrap();
744        assert_eq!(head.hash(), hash(&canonical[2]));
745        assert!(head.parent.is_none());
746        assert!(Arc::ptr_eq(blocks.pending_state().unwrap().parent.as_ref().unwrap(), head));
747        // The fork's parent was removed, so its chain starts at the fork itself.
748        let fork_state = blocks.get(&hash(&fork)).unwrap();
749        assert!(fork_state.parent.as_ref().is_none());
750        assert_eq!(fork_state.anchor(), canonical[0].recovered_block().num_hash());
751        blocks.assert_invariants();
752    }
753
754    #[test]
755    fn reorg_moves_blocks_between_sections() {
756        let mut builder = TestBlockBuilder::eth();
757        let mut blocks = InMemoryBlocks::<EthPrimitives>::default();
758
759        let base = builder.get_executed_block_with_number(1, B256::random());
760        let old_tip = builder.get_executed_block_with_number(2, hash(&base));
761        blocks.set_canonical_chain(vec![base.clone(), old_tip.clone()]);
762        let old_tip_state = Arc::clone(blocks.canonical().get(&hash(&old_tip)).unwrap());
763
764        let new_tip = builder.get_executed_block_with_number(2, hash(&base));
765        assert!(blocks.insert_pending(new_tip.clone()));
766        let new_tip_state = Arc::clone(blocks.get(&hash(&new_tip)).unwrap());
767        blocks.update_chain(NewCanonicalChain::Reorg {
768            new: vec![new_tip.clone()],
769            old: vec![old_tip.clone()],
770        });
771
772        assert!(Arc::ptr_eq(&new_tip_state, blocks.canonical().head().unwrap()));
773        assert!(blocks.canonical().get(&hash(&old_tip)).is_none());
774        // The reorged block stays tracked as non-canonical, with the same state.
775        assert!(Arc::ptr_eq(&old_tip_state, blocks.get(&hash(&old_tip)).unwrap()));
776        assert_eq!(non_canonical_children(&blocks, &base), B256Set::from_iter([hash(&old_tip)]));
777        assert!(blocks.pending_state().is_none(), "a chain update clears the pending block");
778
779        // Reorging back moves the same states back.
780        blocks.update_chain(NewCanonicalChain::Reorg {
781            new: vec![old_tip],
782            old: vec![new_tip.clone()],
783        });
784        assert!(Arc::ptr_eq(&old_tip_state, blocks.canonical().head().unwrap()));
785        assert!(Arc::ptr_eq(&new_tip_state, blocks.get(&hash(&new_tip)).unwrap()));
786        assert_eq!(counts(&blocks), (2, 1));
787        blocks.assert_invariants();
788    }
789
790    #[test]
791    fn inserting_a_removed_parent_relinks_only_its_non_canonical_children() {
792        let mut builder = TestBlockBuilder::eth();
793        let mut blocks = InMemoryBlocks::<EthPrimitives>::default();
794        let chain = builder.get_executed_blocks(1..4).collect::<Vec<_>>();
795        blocks.set_canonical_chain(chain.clone());
796        let fork = builder.get_executed_block_with_number(2, hash(&chain[0]));
797        blocks.insert_executed(fork.clone());
798        let persisted = chain[0].recovered_block().num_hash();
799        blocks.remove_canonical_until(persisted.hash, persisted.number);
800        assert!(blocks.get(&hash(&fork)).unwrap().parent.is_none());
801        assert_eq!(blocks.canonical().head().unwrap().chain().count(), 2);
802
803        // A persisted block can be tracked again, as a non-canonical block.
804        assert!(blocks.insert_executed(chain[0].clone()));
805        blocks.assert_invariants();
806
807        // The fork links to it, but the canonical chain does not continue in the non-canonical
808        // section.
809        let parent = blocks.get(&hash(&chain[0])).unwrap();
810        assert!(Arc::ptr_eq(blocks.get(&hash(&fork)).unwrap().parent.as_ref().unwrap(), parent));
811        assert!(blocks.canonical().get(&hash(&chain[1])).unwrap().parent.is_none());
812        assert_eq!(blocks.canonical().head().unwrap().chain().count(), 2);
813
814        // Once no block is canonical, the oldest of the demoted blocks links to it as well.
815        blocks.demote_canonical_chain();
816        assert_eq!(counts(&blocks), (0, 4));
817        assert_eq!(blocks.get(&hash(&chain[2])).unwrap().chain().count(), 3);
818        blocks.assert_invariants();
819    }
820
821    #[test]
822    fn prune_conflicting_with_finalized_removes_blocks_that_cannot_become_canonical() {
823        let mut builder = TestBlockBuilder::eth();
824        let mut blocks = InMemoryBlocks::<EthPrimitives>::default();
825        let canonical = builder.get_executed_blocks(1..5).collect::<Vec<_>>();
826        blocks.set_canonical_chain(canonical.clone());
827
828        let fork_a = builder.get_executed_block_with_number(2, hash(&canonical[0]));
829        let fork_a_child = builder.get_executed_block_with_number(3, hash(&fork_a));
830        let fork_b = builder.get_executed_block_with_number(3, hash(&canonical[1]));
831        let fork_b_child = builder.get_executed_block_with_number(4, hash(&fork_b));
832        let fork_c = builder.get_executed_block_with_number(4, hash(&canonical[2]));
833        for block in [&fork_a, &fork_a_child, &fork_b, &fork_c] {
834            assert!(blocks.insert_executed(block.clone()));
835        }
836        assert!(blocks.insert_pending(fork_b_child.clone()));
837
838        // With block 3 finalized, only the fork built on it can still become canonical.
839        let removed =
840            blocks.prune_conflicting_with_finalized(canonical[2].recovered_block().num_hash());
841        assert_eq!(removed.len(), 4);
842        for block in [&fork_a, &fork_a_child, &fork_b, &fork_b_child] {
843            assert!(!blocks.contains(&hash(block)));
844        }
845        assert!(blocks.contains(&hash(&fork_c)));
846        assert!(blocks.pending_state().is_none(), "the removed block is still pending");
847        assert_eq!(counts(&blocks), (4, 1), "canonical blocks are removed separately");
848        blocks.assert_invariants();
849    }
850}