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#[derive(Debug, Default)]
34pub(super) struct InMemoryBlocks<N: NodePrimitives> {
35 canonical: InMemoryCanonicalBlocks<N>,
37 non_canonical: InMemoryNonCanonicalBlocks<N>,
39 pending_hash: Option<B256>,
41 relink_queue: Vec<B256>,
45 removed_count: u64,
47}
48
49impl<N: NodePrimitives> InMemoryBlocks<N> {
50 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 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 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 pub(super) const fn canonical(&self) -> &InMemoryCanonicalBlocks<N> {
77 &self.canonical
78 }
79
80 pub(super) fn pending_state(&self) -> Option<&Arc<BlockState<N>>> {
82 self.pending_hash.and_then(|hash| self.get(&hash))
83 }
84
85 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 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 pub(super) const fn removed_count(&self) -> u64 {
105 self.removed_count
106 }
107
108 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 self.queue_children_of(&state);
120 self.non_canonical.insert(state);
121 self.relink();
122 true
123 }
124
125 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 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 for block in old {
146 self.insert_executed(block);
147 }
148 }
149 }
150 }
151
152 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 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 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 pub(super) fn demote_canonical_chain(&mut self) {
226 let canonical = std::mem::take(&mut self.canonical);
227 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 pub(super) fn remove_canonical_until(
243 &mut self,
244 persisted_hash: B256,
245 remove_until: BlockNumber,
246 ) -> Vec<Arc<BlockState<N>>> {
247 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 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 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 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 #[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 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 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 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 assert!(
351 pending_hash.is_none_or(|hash| self.contains(&hash)),
352 "the pending block is not tracked"
353 );
354 }
355
356 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 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 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 fn queue_moved(&mut self, state: &BlockState<N>) {
384 self.relink_queue.push(state.hash());
385 self.queue_children_of(state);
386 }
387
388 fn relink(&mut self) {
392 let mut queue = std::mem::take(&mut self.relink_queue);
393 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 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#[derive(Debug, Default)]
436pub(super) struct InMemoryCanonicalBlocks<N: NodePrimitives> {
437 blocks: B256Map<Arc<BlockState<N>>>,
439 numbers: BTreeMap<BlockNumber, B256>,
441}
442
443impl<N: NodePrimitives> InMemoryCanonicalBlocks<N> {
444 pub(super) fn get(&self, hash: &B256) -> Option<&Arc<BlockState<N>>> {
446 self.blocks.get(hash)
447 }
448
449 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 pub(super) fn hash_by_number(&self, number: BlockNumber) -> Option<B256> {
456 self.numbers.get(&number).copied()
457 }
458
459 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 #[cfg(test)]
466 pub(super) fn len(&self) -> usize {
467 self.blocks.len()
468 }
469
470 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 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 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 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 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#[derive(Debug, Default)]
539pub(super) struct InMemoryNonCanonicalBlocks<N: NodePrimitives> {
540 blocks: B256Map<Arc<BlockState<N>>>,
542 numbers: BTreeMap<BlockNumber, B256Set>,
544 children: B256Map<B256Set>,
547}
548
549impl<N: NodePrimitives> InMemoryNonCanonicalBlocks<N> {
550 fn children_of(&self, parent: &BlockState<N>) -> impl Iterator<Item = B256> + '_ {
552 self.children.get(&parent.hash()).into_iter().flatten().copied()
553 }
554
555 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 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 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 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 fn remove_built_above(&mut self, persisted_number: BlockNumber) -> Vec<Arc<BlockState<N>>> {
623 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#[derive(Debug)]
638pub(super) struct InMemoryBlocksStats {
639 pub(super) count: usize,
641 pub(super) earliest: Option<BlockNumber>,
643 pub(super) latest: Option<BlockNumber>,
645}
646
647fn 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 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 fn counts(blocks: &InMemoryBlocks<EthPrimitives>) -> (usize, usize) {
679 (blocks.canonical.blocks.len(), blocks.non_canonical.blocks.len())
680 }
681
682 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 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 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 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 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 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 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 assert!(blocks.insert_executed(chain[0].clone()));
805 blocks.assert_invariants();
806
807 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 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 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}