1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the alphavm library.
  3  
  4  // Licensed under the Apache License, Version 2.0 (the "License");
  5  // you may not use this file except in compliance with the License.
  6  // You may obtain a copy of the License at:
  7  
  8  // http://www.apache.org/licenses/LICENSE-2.0
  9  
 10  // Unless required by applicable law or agreed to in writing, software
 11  // distributed under the License is distributed on an "AS IS" BASIS,
 12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  // See the License for the specific language governing permissions and
 14  // limitations under the License.
 15  
 16  use crate::block::{Block, Network};
 17  
 18  use alphavm_utilities::ensure_equals;
 19  
 20  use std::collections::VecDeque;
 21  
 22  use anyhow::{Result, ensure};
 23  
 24  /// Helper struct for caching the most recent blocks.
 25  pub(super) struct BlockCache<N: Network> {
 26      /// Contains the most recent blocks ordered by height.
 27      /// We do not use a BTreeMap here as the cache is small and updates to a vector are more efficient
 28      ///
 29      /// Invariant: all entries in this vector (except the first) a height equal to h+1 (where h` is the previous block entry)
 30      blocks: VecDeque<Block<N>>,
 31  }
 32  
 33  impl<N: Network> BlockCache<N> {
 34      /// The maximum size of the cache in blocks.
 35      pub(super) const BLOCK_CACHE_SIZE: u32 = 10;
 36  
 37      /// Initialize the cache with the given blocks.
 38      pub fn new(blocks: Vec<Block<N>>) -> Result<Self> {
 39          ensure!(blocks.len() <= Self::BLOCK_CACHE_SIZE as usize, "Too many blocks to fit in the cache");
 40  
 41          if let Some(block) = blocks.first() {
 42              ensure!(block.height() != 0, "Cannot cache the genesis block");
 43          }
 44          for idx in 1..blocks.len() {
 45              ensure!(blocks[idx - 1].height() + 1 == blocks[idx].height(), "Not a continuous chain of blocks");
 46          }
 47  
 48          Ok(Self { blocks: VecDeque::from(blocks) })
 49      }
 50  
 51      /// Insert a new block into the cache.
 52      /// Must be the successor of the last block inserted into the cache.
 53      #[inline]
 54      pub fn insert(&mut self, block: Block<N>) -> Result<()> {
 55          ensure!(block.height() != 0, "Cannot cache the genesis block");
 56  
 57          if let Some(prev) = self.blocks.back() {
 58              ensure_equals!(
 59                  prev.height() + 1,
 60                  block.height(),
 61                  "Block is not the successor of the last block inserted into the cache"
 62              );
 63          }
 64  
 65          self.blocks.push_back(block.clone());
 66          if self.blocks.len() > (Self::BLOCK_CACHE_SIZE as usize) {
 67              self.blocks.pop_front();
 68          }
 69  
 70          Ok(())
 71      }
 72  
 73      /// Return the block at the given height if it is in the cache.i
 74      #[inline]
 75      pub fn get_block(&self, block_height: u32) -> Option<&Block<N>> {
 76          let first_block = self.blocks.front()?;
 77  
 78          // Determine to location of the cached block (if any).
 79          // This returns `None` if `block_height` is lower than the height of the first cached block.
 80          let offset = block_height.checked_sub(first_block.height())?;
 81  
 82          self.blocks.get(offset as usize)
 83      }
 84  
 85      /// Return the block with the given hash if it is in the cache.
 86      #[inline]
 87      pub fn get_block_by_hash(&self, block_hash: &N::BlockHash) -> Option<&Block<N>> {
 88          // Perform a linear search through the cache.
 89          // This is cheap, as the cache is very small.
 90          self.blocks.iter().find(|block| &block.hash() == block_hash)
 91      }
 92  
 93      /// Remove the last `n` blocks from the cache.
 94      #[inline]
 95      pub fn remove_last_n(&mut self, n: u32) -> Result<()> {
 96          for _ in 0..n {
 97              self.blocks.pop_back();
 98          }
 99          Ok(())
100      }
101  }
102  
103  #[cfg(test)]
104  mod tests {
105      use super::*;
106  
107      use crate::test_helpers::CurrentNetwork;
108  
109      use alphavm_console::{
110          account::{Field, PrivateKey},
111          prelude::{Rng, TestRng},
112      };
113      use alphavm_ledger_authority::Authority;
114      use alphavm_ledger_block::{Header, Metadata, Ratifications, Transactions};
115  
116      type BlockCache = super::BlockCache<CurrentNetwork>;
117  
118      #[test]
119      fn eviction() {
120          // The number of blocks to insert during the test
121          // (must be more than the cache size)
122          const NUM_BLOCKS: u32 = 15;
123          const { assert!(NUM_BLOCKS > BlockCache::BLOCK_CACHE_SIZE) };
124  
125          let rng = &mut TestRng::default();
126          let private_key = PrivateKey::<CurrentNetwork>::new(rng).unwrap();
127  
128          // Construct a chain of blocks.
129          let mut previous_hash = None;
130          let blocks: Vec<_> = (0..NUM_BLOCKS)
131              .map(|h| {
132                  let transactions = Transactions::from(&[]);
133                  let ratifications = Ratifications::try_from(vec![]).unwrap();
134                  let header = if h == 0 {
135                      Header::genesis(&ratifications, &transactions, vec![]).unwrap()
136                  } else {
137                      // Use mock metadata to save compute time.
138                      let metadata = Metadata::new(
139                          CurrentNetwork::ID,
140                          (h * 2) as u64,
141                          h,
142                          0,
143                          (h * 1000) as u128,
144                          CurrentNetwork::GENESIS_COINBASE_TARGET,
145                          CurrentNetwork::GENESIS_PROOF_TARGET + 1,
146                          CurrentNetwork::GENESIS_COINBASE_TARGET,
147                          CurrentNetwork::GENESIS_TIMESTAMP + ((h - 1) * 100) as i64,
148                          CurrentNetwork::GENESIS_TIMESTAMP + (h * 100) as i64,
149                      )
150                      .unwrap();
151  
152                      let previous_state_root: <CurrentNetwork as Network>::StateRoot = rng.r#gen();
153                      Header::<CurrentNetwork>::from(
154                          previous_state_root,
155                          Field::from_u32(1),
156                          Field::from_u32(1),
157                          Field::from_u32(1),
158                          Field::from_u32(1),
159                          Field::from_u32(1),
160                          metadata,
161                      )
162                      .unwrap()
163                  };
164                  let block_hash = rng.r#gen();
165                  let authority = Authority::<CurrentNetwork>::new_beacon(&private_key, block_hash, rng).unwrap();
166  
167                  let block = Block::from_unchecked(
168                      block_hash.into(),
169                      previous_hash.unwrap_or_default(),
170                      header,
171                      authority,
172                      ratifications,
173                      None.into(),
174                      vec![],
175                      transactions,
176                      vec![],
177                  )
178                  .unwrap();
179  
180                  previous_hash = Some(block.hash());
181                  block
182              })
183              .collect();
184  
185          let mut cache = BlockCache::new(vec![]).unwrap();
186          let mut blocks = blocks.into_iter().skip(1);
187  
188          // First, fill up the cache.
189          while cache.blocks.len() < (BlockCache::BLOCK_CACHE_SIZE as usize) {
190              cache.insert(blocks.next().unwrap()).unwrap();
191          }
192  
193          // Then, continue insertions and check that old blocks are evicted.
194          for block in blocks {
195              let hash = block.hash();
196              let height = block.height();
197  
198              cache.insert(block).unwrap();
199  
200              // Ensure eviction work.
201              assert_eq!(cache.blocks.len(), BlockCache::BLOCK_CACHE_SIZE as usize);
202  
203              // Ensure the correct block is returned.
204              let ret1 = cache.get_block(height).unwrap();
205              let ret2 = cache.get_block_by_hash(&hash).unwrap();
206  
207              assert_eq!(ret1.hash(), hash);
208              assert_eq!(ret2.hash(), hash);
209              assert_eq!(ret1.height(), height);
210              assert_eq!(ret2.height(), height);
211  
212              assert_eq!(cache.blocks[0].height(), height - BlockCache::BLOCK_CACHE_SIZE + 1);
213          }
214  
215          // Fetch something that isn't the last block.
216          let block = cache.get_block(10).unwrap();
217          assert_eq!(block.height(), 10);
218  
219          // Fetch the last thing that must be in the cache.
220          assert!(cache.get_block(NUM_BLOCKS - BlockCache::BLOCK_CACHE_SIZE).is_some());
221          // Fetch something that must not be in the cache.
222          assert!(cache.get_block(NUM_BLOCKS - BlockCache::BLOCK_CACHE_SIZE - 1).is_none());
223      }
224  }