forest-filecoin 0.33.8

// Copyright 2019-2026 ChainSafe Systems
// SPDX-License-Identifier: Apache-2.0, MIT

use std::num::NonZeroUsize;

use crate::beacon::{BeaconEntry, IGNORE_DRAND};
use crate::blocks::{Tipset, TipsetKey};
use crate::chain::Error;
use crate::db::{DbImpl, EthMappingsStore};
use crate::prelude::*;
use crate::shim::clock::ChainEpoch;
use crate::utils::cache::SizeTrackingCache;
use nonzero_ext::nonzero;
use num::Integer;
use tracing::info;

const DEFAULT_TIPSET_CACHE_SIZE: NonZeroUsize = nonzero!(2880_usize * 3); // 3-day-worth epochs, maximum ~50MiB
// use `20` as checkpoint interval to match Lotus:
// <https://github.com/filecoin-project/lotus/blob/v1.35.1/chain/store/index.go#L52>
const TIPSET_LOOKUP_CHECKPOINT_INTERVAL: ChainEpoch = 20;

type TipsetCache = SizeTrackingCache<TipsetKey, Tipset>;

type IsEpochFinalizedFn = Arc<dyn Fn(ChainEpoch) -> bool + Send + Sync>;

/// Keeps look-back tipsets in cache at a given interval `skip_length` and can
/// be used to look-back at the chain to retrieve an old tipset.
pub struct ChainIndex {
    /// tipset key to tipset mappings.
    ts_cache: TipsetCache,
    /// `Blockstore` pointer needed to load tipsets from cold storage.
    db: DbImpl,
    /// Genesis tipset
    genesis: Tipset,
    /// check whether an epoch is finalized
    is_epoch_finalized: Option<IsEpochFinalizedFn>,
}

impl ShallowClone for ChainIndex {
    fn shallow_clone(&self) -> Self {
        Self {
            ts_cache: self.ts_cache.shallow_clone(),
            db: self.db.shallow_clone(),
            genesis: self.genesis.shallow_clone(),
            is_epoch_finalized: self.is_epoch_finalized.clone(),
        }
    }
}

#[derive(Debug, Clone, Copy)]
/// Methods for resolving fetches of null tipsets.
/// Imagine epoch 10 is null but epoch 9 and 11 exist. If epoch we request epoch
/// 10, should 9 or 11 be returned?
pub enum ResolveNullTipset {
    TakeNewer,
    TakeOlder,
    /// Return [`Error::NullRound`] instead of resolving to a neighboring tipset.
    Fail,
}

impl ChainIndex {
    pub fn new(db: impl Into<DbImpl>, genesis: Tipset) -> Self {
        assert!(genesis.epoch() == 0, "genesis tipset must be at epoch 0");
        let db = db.into();
        let ts_cache = SizeTrackingCache::new_with_metrics("tipset", DEFAULT_TIPSET_CACHE_SIZE);
        Self {
            ts_cache,
            db,
            genesis,
            is_epoch_finalized: None,
        }
    }

    pub fn with_is_epoch_finalized(mut self, f: IsEpochFinalizedFn) -> Self {
        self.is_epoch_finalized = Some(f);
        self
    }

    pub fn db(&self) -> &DbImpl {
        &self.db
    }

    pub fn db_owned(&self) -> DbImpl {
        self.db().shallow_clone()
    }

    pub fn genesis(&self) -> &Tipset {
        &self.genesis
    }

    /// Loads a tipset from memory given the tipset keys and cache. Semantically
    /// identical to [`Tipset::load`] but the result is cached.
    pub fn load_tipset(&self, tsk: &TipsetKey) -> Result<Option<Tipset>, Error> {
        crate::def_is_env_truthy!(cache_disabled, "FOREST_TIPSET_CACHE_DISABLED");
        if cache_disabled() {
            Ok(Tipset::load(&self.db, tsk)?)
        } else {
            enum TmpError {
                NotFound,
                LoadError(anyhow::Error),
            }
            match self.ts_cache.get_or_insert_with(tsk, || {
                Tipset::load(&self.db, tsk)
                    .map(|opt| opt.ok_or(TmpError::NotFound))
                    .map_err(TmpError::LoadError)
                    .flatten()
            }) {
                Ok(ts) => Ok(Some(ts)),
                Err(TmpError::NotFound) => Ok(None),
                Err(TmpError::LoadError(e)) => Err(e.into()),
            }
        }
    }

    /// Loads a tipset from memory given the tipset keys and cache.
    /// This calls fails if the tipset is missing or invalid. Semantically
    /// identical to [`Tipset::load_required`] but the result is cached.
    pub fn load_required_tipset(&self, tsk: &TipsetKey) -> Result<Tipset, Error> {
        self.load_tipset(tsk)?
            .ok_or_else(|| Error::NotFound("Key for header".into()))
    }

    /// Find tipset at epoch `to` in the chain of ancestors starting at `from`.
    ///
    /// Returns `Ok(Some(tipset))` when epoch `to` resolves. Returns `Ok(None)` if the ancestor
    /// walk completes without resolving `to` (for example missing parent tipsets). Returns `Err`
    /// if `to` is greater than `from.epoch()` or genesis lookup fails when `to` is zero.
    ///
    /// # Why pass in the `from` argument?
    ///
    /// Imagine the database contains five tipsets and a genesis block in this
    /// configuration:
    ///
    /// ```text
    ///           ┌───────┐  ┌────────┐  ┌────────┐
    /// Genesis◄──┤Epoch 1◄──┤Epoch 2A◄──┤Epoch 3A│
    ///           └───▲───┘  └────────┘  └────────┘
    ///               │      ┌────────┐  ┌────────┐
    ///               └──────┤Epoch 2B◄──┤Epoch 3B│
    ///                      └────────┘  └────────┘
    /// ```
    ///
    /// Here we have a fork in the chain and it is ambiguous which tipset to
    /// load when epoch 2 is requested. The ambiguity is solved by passing in a
    /// younger tipset (higher epoch) from which has the desired tipset as an
    /// ancestor.
    /// Calling `get_tipset_by_height(2, epoch_3a)` will return `Epoch 2A`.
    /// Calling `get_tipset_by_height(2, epoch_3b)` will return `Epoch 2B`.
    ///
    /// # What happens when a null tipset is requested?
    ///
    /// ```text
    ///           ┌───────┐          ┌───────┐  ┌───────┐
    /// Genesis◄──┤Epoch 1│   Null   │Epoch 3◄──┤Epoch 4│
    ///           └───▲───┘          └───┬───┘  └───────┘
    ///               │                  │
    ///               └──────────────────┘
    /// ```
    /// If the requested epoch points to a null tipset, there are three options:
    /// pick the nearest older tipset, pick the nearest younger tipset, or fail.
    /// Requesting epoch 2 with [`ResolveNullTipset::TakeNewer`] will return
    /// epoch 3, with [`ResolveNullTipset::TakeOlder`] will return epoch 1, and
    /// with [`ResolveNullTipset::Fail`] will return [`Error::NullRound`].
    pub fn tipset_by_height(
        &self,
        to: ChainEpoch,
        mut from: Tipset,
        resolve: ResolveNullTipset,
    ) -> Result<Option<Tipset>, Error> {
        use crate::shim::policy::policy_constants::CHAIN_FINALITY;

        crate::def_is_env_truthy!(lookup_table_disabled, "FOREST_TIPSET_LOOKUP_TABLE_DISABLED");

        if to == 0 {
            return Ok(Some(self.genesis.shallow_clone()));
        }

        let from_epoch = from.epoch();
        let is_epoch_finalized = |epoch: ChainEpoch| {
            if let Some(is_epoch_finalized) = &self.is_epoch_finalized {
                is_epoch_finalized(epoch)
            } else {
                epoch <= from_epoch - CHAIN_FINALITY
            }
        };

        let mut checkpoint_from_epoch = to;
        while !lookup_table_disabled()
            && checkpoint_from_epoch < from_epoch
            // unfinalized checkpoints are subject to change
            && is_epoch_finalized(checkpoint_from_epoch)
        {
            if let Ok(Some(checkpoint_from_key)) =
                self.db.tipset_key_by_epoch(checkpoint_from_epoch)
                && let Ok(Some(checkpoint_from)) = self.load_tipset(&checkpoint_from_key)
            {
                from = checkpoint_from;
                break;
            }
            checkpoint_from_epoch = Self::next_tipset_lookup_checkpoint(checkpoint_from_epoch);
        }

        if to > from.epoch() {
            return Err(Error::Other(format!(
                "looking for tipset with height greater than start point, req: {to}, head: {from}",
                from = from.epoch()
            )));
        } else if to == from.epoch() {
            return Ok(Some(from));
        }

        for (child, parent) in from.chain(&self.db).tuple_windows() {
            // update cache only when child is finalized.
            if Self::is_tipset_lookup_checkpoint(child.epoch())
                && is_epoch_finalized(child.epoch())
                && let Err(e) = self.db.set_tipset_key_at_epoch(&child)
            {
                tracing::warn!(
                    "failed to update tipset height cache, epoch: {}, key: {}, error: {e}",
                    child.epoch(),
                    child.key()
                );
            }

            if to == child.epoch() {
                return Ok(Some(child));
            }
            if to > parent.epoch() {
                // We're at a point where child.epoch() > x > parent.epoch().
                match resolve {
                    ResolveNullTipset::TakeOlder => return Ok(Some(parent)),
                    ResolveNullTipset::TakeNewer => return Ok(Some(child)),
                    ResolveNullTipset::Fail => return Err(Error::NullRound(to)),
                }
            }
        }
        Ok(None)
    }

    /// Non-blocking version of [`Self::tipset_by_height`]
    pub async fn tipset_by_height_async(
        &self,
        to: ChainEpoch,
        from: Tipset,
        resolve: ResolveNullTipset,
    ) -> Result<Option<Tipset>, Error> {
        let this = self.shallow_clone();
        tokio::task::spawn_blocking(move || this.tipset_by_height(to, from, resolve)).await?
    }

    /// Same as [`Self::tipset_by_height`], but errors if that would return `None`.
    /// This call can be expensive and blocking, use [`Self::load_required_tipset_by_height`]
    /// in async contexts to avoid exhausting Tokio worker threads.
    pub fn load_required_tipset_by_height_blocking(
        &self,
        to: ChainEpoch,
        from: Tipset,
        resolve: ResolveNullTipset,
    ) -> Result<Tipset, Error> {
        self.tipset_by_height(to, from, resolve)?
            .ok_or_else(|| Error::NotFound(format!("tipset at epoch {to}").into()))
    }

    /// Same as [`Self::tipset_by_height_async`], but errors if that would return `None`.
    pub async fn load_required_tipset_by_height(
        &self,
        to: ChainEpoch,
        from: Tipset,
        resolve: ResolveNullTipset,
    ) -> Result<Tipset, Error> {
        self.tipset_by_height_async(to, from, resolve)
            .await?
            .ok_or_else(|| Error::NotFound(format!("tipset at epoch {to}").into()))
    }

    /// Finds the latest beacon entry given a tipset up to 20 tipsets behind
    pub fn latest_beacon_entry(&self, tipset: Tipset) -> Result<BeaconEntry, Error> {
        for ts in tipset.chain(&self.db).take(20) {
            if let Some(entry) = ts.min_ticket_block().beacon_entries.last() {
                return Ok(entry.clone());
            }
            if ts.epoch() == 0 {
                return Err(Error::Other(
                    "made it back to genesis block without finding beacon entry".to_owned(),
                ));
            }
        }

        if *IGNORE_DRAND {
            return Ok(BeaconEntry::new(0, vec![9; 16]));
        }

        Err(Error::Other(
            "Found no beacon entries in the 20 latest tipsets".to_owned(),
        ))
    }

    fn next_tipset_lookup_checkpoint(epoch: ChainEpoch) -> ChainEpoch {
        epoch - epoch.mod_floor(&TIPSET_LOOKUP_CHECKPOINT_INTERVAL)
            + TIPSET_LOOKUP_CHECKPOINT_INTERVAL
    }

    pub fn is_tipset_lookup_checkpoint(epoch: ChainEpoch) -> bool {
        epoch.mod_floor(&TIPSET_LOOKUP_CHECKPOINT_INTERVAL) == 0
    }

    /// Cleans up stale checkpoints at null rounds between the given tipset and its parent in case there's chain reorg.
    /// Returns the number of lookup entries being deleted.
    pub fn cleanup_stale_tipset_lookup_at_null_rounds(
        db: &impl EthMappingsStore,
        ts: &Tipset,
        parent: &Tipset,
    ) -> anyhow::Result<usize> {
        anyhow::ensure!(
            ts.parents() == parent.key(),
            "tipset keys do not match, `ts.parents()` should match `parent.key()`"
        );
        // Cleanup null lookup checkpoints on chain reorg
        let null_checkpoint_epochs = ((parent.epoch() + 1)..ts.epoch())
            .filter(|&epoch| Self::is_tipset_lookup_checkpoint(epoch))
            .collect_vec();
        let mut n_deleted = 0;
        for epoch in null_checkpoint_epochs {
            if db
                .tipset_key_by_epoch(epoch)
                .with_context(|| {
                    format!("db error: failed to dlookup tipset key at epoch {epoch}")
                })?
                .is_some()
            {
                db.delete_tipset_key_at_epoch(epoch).with_context(|| {
                    format!("db error: failed to delete tipset lookup at null epoch {epoch}")
                })?;
                info!("deleted tipset lookup at null epoch {epoch}");
                n_deleted += 1;
            }
        }
        Ok(n_deleted)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::blocks::{CachingBlockHeader, RawBlockHeader};
    use crate::db::MemoryDB;
    use crate::test_utils::dummy_ticket;
    use crate::utils::db::CborStoreExt;
    use std::sync::{
        Arc,
        atomic::{AtomicU64, Ordering},
    };

    fn persist_tipset(tipset: &Tipset, db: &impl Blockstore) {
        for block in tipset.block_headers() {
            db.put_cbor_default(block).unwrap();
        }
    }

    fn genesis_tipset() -> Tipset {
        Tipset::from(CachingBlockHeader::new(RawBlockHeader {
            ticket: dummy_ticket(0),
            ..Default::default()
        }))
    }

    fn tipset_child(parent: &Tipset, epoch: ChainEpoch) -> Tipset {
        // Use a static counter to give all tipsets a unique timestamp
        static COUNTER: AtomicU64 = AtomicU64::new(0);
        let n = COUNTER.fetch_add(1, Ordering::Relaxed);
        Tipset::from(CachingBlockHeader::new(RawBlockHeader {
            parents: parent.key().clone(),
            ticket: dummy_ticket(n as u8),
            epoch,
            timestamp: n,
            ..Default::default()
        }))
    }

    #[test]
    fn get_null_tipset() {
        let db = Arc::new(MemoryDB::default());
        let genesis = genesis_tipset();
        let epoch1 = tipset_child(&genesis, 1);
        let epoch3 = tipset_child(&epoch1, 3);
        let epoch4 = tipset_child(&epoch3, 4);
        persist_tipset(&genesis, &db);
        persist_tipset(&epoch1, &db);
        persist_tipset(&epoch3, &db);
        persist_tipset(&epoch4, &db);

        let index = ChainIndex::new(db, genesis);
        // epoch 2 is null. ResolveNullTipset decided whether to return epoch 1 or epoch 3
        assert_eq!(
            index
                .tipset_by_height(2, epoch4.clone(), ResolveNullTipset::TakeOlder)
                .unwrap()
                .expect("epoch 2 resolved"),
            epoch1
        );

        assert_eq!(
            index
                .tipset_by_height(2, epoch4, ResolveNullTipset::TakeNewer)
                .unwrap()
                .expect("epoch 2 resolved"),
            epoch3
        );
    }

    #[test]
    fn get_different_branches() {
        let db = Arc::new(MemoryDB::default());
        let genesis = genesis_tipset();
        let epoch1 = tipset_child(&genesis, 1);

        let epoch2a = tipset_child(&epoch1, 2);
        let epoch3a = tipset_child(&epoch2a, 3);

        let epoch2b = tipset_child(&epoch1, 2);
        let epoch3b = tipset_child(&epoch2b, 3);

        persist_tipset(&genesis, &db);
        persist_tipset(&epoch1, &db);
        persist_tipset(&epoch2a, &db);
        persist_tipset(&epoch3a, &db);
        persist_tipset(&epoch2b, &db);
        persist_tipset(&epoch3b, &db);

        let index = ChainIndex::new(db, genesis);
        // The chain as forked, epoch 2 and 3 are ambiguous
        assert_eq!(
            index
                .tipset_by_height(2, epoch3a, ResolveNullTipset::TakeOlder)
                .unwrap()
                .expect("epoch 2 on branch a"),
            epoch2a
        );

        assert_eq!(
            index
                .tipset_by_height(2, epoch3b, ResolveNullTipset::TakeOlder)
                .unwrap()
                .expect("epoch 2 on branch b"),
            epoch2b
        );
    }

    #[test]
    fn tipset_by_height_broken_ancestor_chain_returns_none() {
        let db = Arc::new(MemoryDB::default());
        let genesis = genesis_tipset();
        // Epoch 3 header points at a parent key we never persist — `Tipset::chain` stops
        // after this tipset, so `tipset_by_height` finds no `(child, parent)` window.
        let epoch3 = tipset_child(&tipset_child(&genesis, 2), 3);
        persist_tipset(&genesis, &db);
        persist_tipset(&epoch3, &db);

        let index = ChainIndex::new(db, genesis);
        assert!(
            index
                .tipset_by_height(2, epoch3, ResolveNullTipset::TakeOlder)
                .unwrap()
                .is_none()
        );
    }
}