featherdb_mvcc/

snapshot.rs

//! Snapshot isolation implementation

use featherdb_core::TransactionId;
use std::collections::HashSet;

/// A consistent view of the database at a point in time
#[derive(Debug, Clone)]
pub struct Snapshot {
    /// Transaction ID of this snapshot
    txn_id: TransactionId,
    /// High-water mark: all transactions with ID >= this were not committed
    high_water_mark: TransactionId,
    /// Transactions with ID < high_water_mark that were NOT committed
    /// (in-progress when snapshot was taken)
    in_progress_at_start: HashSet<TransactionId>,
    /// Ancestor transactions whose changes should also be visible
    /// (used for sub-transactions/savepoints to see parent's uncommitted changes)
    visible_ancestors: HashSet<TransactionId>,
    /// Fast-path flag: true when both in_progress_at_start and visible_ancestors
    /// are empty, allowing can_see() to skip HashSet lookups entirely.
    is_clean: bool,
}

impl Snapshot {
    /// Create a new snapshot
    pub fn new(
        txn_id: TransactionId,
        high_water_mark: TransactionId,
        in_progress: HashSet<TransactionId>,
    ) -> Self {
        let is_clean = in_progress.is_empty();
        Snapshot {
            txn_id,
            high_water_mark,
            in_progress_at_start: in_progress,
            visible_ancestors: HashSet::new(),
            is_clean,
        }
    }

    /// Create a snapshot with visible ancestor transactions
    ///
    /// This is used for sub-transactions (savepoints) that need to see
    /// their parent transaction's uncommitted changes.
    pub fn with_ancestors(
        txn_id: TransactionId,
        high_water_mark: TransactionId,
        in_progress: HashSet<TransactionId>,
        ancestors: HashSet<TransactionId>,
    ) -> Self {
        let is_clean = in_progress.is_empty() && ancestors.is_empty();
        Snapshot {
            txn_id,
            high_water_mark,
            in_progress_at_start: in_progress,
            visible_ancestors: ancestors,
            is_clean,
        }
    }

    /// Add an ancestor transaction whose changes should be visible
    pub fn add_ancestor(&mut self, ancestor: TransactionId) {
        self.visible_ancestors.insert(ancestor);
        self.is_clean = false;
    }

    /// Check if a transaction is an ancestor (part of the same logical transaction)
    pub fn is_ancestor(&self, txn_id: TransactionId) -> bool {
        self.visible_ancestors.contains(&txn_id)
    }

    /// Get the transaction ID of this snapshot
    pub fn txn_id(&self) -> TransactionId {
        self.txn_id
    }

    /// Returns true when all committed transactions are visible.
    /// This enables the ultra-fast scan path that skips per-row MVCC checks.
    #[inline]
    pub fn sees_all_committed(&self) -> bool {
        self.is_clean
    }

    /// Get the high-water mark
    #[inline]
    pub fn high_water_mark(&self) -> TransactionId {
        self.high_water_mark
    }

    /// Check if a transaction's changes are visible to this snapshot
    #[inline]
    pub fn can_see(&self, created_by: TransactionId) -> bool {
        // Own changes are always visible
        if created_by == self.txn_id {
            return true;
        }

        // Fast path: when no in-progress txns and no ancestors exist,
        // visibility is purely a range check (no HashSet lookups)
        if self.is_clean {
            return created_by < self.high_water_mark;
        }

        // Ancestor transactions are also visible (for savepoint support)
        if self.visible_ancestors.contains(&created_by) {
            return true;
        }

        // Future transactions not visible
        if created_by >= self.high_water_mark {
            return false;
        }

        // Transactions that were in-progress when we started are not visible
        !self.in_progress_at_start.contains(&created_by)
    }

    /// Check if a version is visible based on creation and deletion timestamps
    #[inline]
    pub fn is_visible(&self, created_by: TransactionId, deleted_by: Option<TransactionId>) -> bool {
        // Must be able to see when it was created
        if !self.can_see(created_by) {
            return false;
        }

        // If deleted, must not be able to see the deletion
        if let Some(deleted_by) = deleted_by {
            if self.can_see(deleted_by) {
                return false;
            }
        }

        true
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_snapshot_own_changes_visible() {
        let snapshot = Snapshot::new(TransactionId(5), TransactionId(10), HashSet::new());

        assert!(snapshot.can_see(TransactionId(5)));
    }

    #[test]
    fn test_snapshot_old_committed_visible() {
        let snapshot = Snapshot::new(TransactionId(5), TransactionId(10), HashSet::new());

        // Committed before snapshot
        assert!(snapshot.can_see(TransactionId(3)));
    }

    #[test]
    fn test_snapshot_future_not_visible() {
        let snapshot = Snapshot::new(TransactionId(5), TransactionId(10), HashSet::new());

        // Future transaction
        assert!(!snapshot.can_see(TransactionId(15)));
    }

    #[test]
    fn test_snapshot_in_progress_not_visible() {
        let mut in_progress = HashSet::new();
        in_progress.insert(TransactionId(3));

        let snapshot = Snapshot::new(TransactionId(5), TransactionId(10), in_progress);

        // Transaction 3 was in progress when snapshot was taken
        assert!(!snapshot.can_see(TransactionId(3)));
    }

    #[test]
    fn test_snapshot_deleted_visibility() {
        let snapshot = Snapshot::new(TransactionId(5), TransactionId(10), HashSet::new());

        // Created before, not deleted -> visible
        assert!(snapshot.is_visible(TransactionId(2), None));

        // Created before, deleted before -> not visible
        assert!(!snapshot.is_visible(TransactionId(2), Some(TransactionId(3))));

        // Created before, deleted after snapshot -> visible
        assert!(snapshot.is_visible(TransactionId(2), Some(TransactionId(15))));
    }
}