lucisearch 0.8.0

use crate::core::{LuciError, Result};

use crate::storage::block::{BLOCK_SIZE, BlockId, HEADER_SIZE};

/// Magic bytes identifying a Luci index file.
///
/// The last two bytes encode a format family marker (`\x00`) and a
/// non-zero sentinel (`\x01`) to detect truncated files.
pub const MAGIC: [u8; 8] = *b"LUCI\x00\x00\x00\x01";

/// Current format version. Incremented on breaking format changes.
///
/// v3 (2026-06): keyword columns gain a persisted per-block offset index
/// (`ColumnType::KeywordBlocked = 8`) for O(1) ordinal→string lookup, per
/// [[optimization-keyword-dict-offset-index]]. The bump is the old-binary
/// safety net: an old binary maps the unknown `col_type = 8` to `Empty` and
/// would silently drop the `_id` column, so it must instead reject the file
/// loudly via the `format_version > FORMAT_VERSION` check. `commit()` stamps
/// this version on every write, making any new-binary write a one-way upgrade.
///
/// v2 (2026-05): adds the per-field vector-index directory to
/// `MetadataSnapshot` per [[global-vector-indices]]
/// Alternative B. The HNSW graph for each `dense_vector` field is
/// stored in its own file extent rather than per-segment.
pub const FORMAT_VERSION: u32 = 3;

// Byte offsets within the 4 KB header.
const OFF_MAGIC: usize = 0;
const OFF_VERSION: usize = 8;
const OFF_BLOCK_SIZE: usize = 12;
const OFF_ROOT_A_BLOCK: usize = 16;
const OFF_ROOT_A_CHECKSUM: usize = 24;
const OFF_ROOT_B_BLOCK: usize = 32;
const OFF_ROOT_B_CHECKSUM: usize = 40;
const OFF_ACTIVE_ROOT: usize = 48;

/// Sentinel value for a root pointer that has never been written.
const EMPTY_ROOT_BLOCK: u64 = u64::MAX;

/// A root pointer in the file header.
///
/// Points to a metadata root block and stores its xxHash (XXH3) checksum
/// for integrity validation during crash recovery.
///
/// See [[architecture-storage-format#Atomic Commit Protocol]].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RootPointer {
    /// Block containing the metadata root, or `None` if this slot has never
    /// been committed to.
    pub block_id: Option<BlockId>,
    /// xxHash (XXH3-64) checksum of the metadata root block contents.
    pub checksum: u64,
}

impl RootPointer {
    /// A root pointer that has never been written.
    pub const EMPTY: Self = Self {
        block_id: None,
        checksum: 0,
    };

    /// Create a root pointer referencing a metadata block.
    pub const fn new(block_id: BlockId, checksum: u64) -> Self {
        Self {
            block_id: Some(block_id),
            checksum,
        }
    }

    /// Whether this root pointer has been written to.
    pub const fn is_populated(&self) -> bool {
        self.block_id.is_some()
    }
}

/// Identifies which root pointer is active.
///
/// The two-root-pointer scheme alternates between A and B on each commit,
/// ensuring the inactive root always holds the last known-good state.
///
/// See [[architecture-storage-format#Atomic Commit Protocol]].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ActiveRoot {
    A = 0,
    B = 1,
}

impl ActiveRoot {
    /// The other root — the one that will be written next.
    pub const fn inactive(self) -> Self {
        match self {
            Self::A => Self::B,
            Self::B => Self::A,
        }
    }
}

/// The 4 KB file header for a `.luci` index file.
///
/// Contains magic bytes, format version, block size, two root pointers for
/// atomic commit, and an active root flag. Serializes to exactly
/// [`HEADER_SIZE`] bytes.
///
/// See [[architecture-storage-format#File Layout]].
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FileHeader {
    pub format_version: u32,
    pub block_size: u32,
    pub root_a: RootPointer,
    pub root_b: RootPointer,
    pub active_root: ActiveRoot,
}

impl FileHeader {
    /// Create a header for a brand-new index file.
    pub fn new() -> Self {
        Self {
            format_version: FORMAT_VERSION,
            block_size: BLOCK_SIZE,
            root_a: RootPointer::EMPTY,
            root_b: RootPointer::EMPTY,
            active_root: ActiveRoot::A,
        }
    }

    /// Test-only constructor that pins `format_version` to an arbitrary value.
    ///
    /// `FORMAT_VERSION` is a compile-time `const`, so a test that needs to
    /// fabricate an older-version header (e.g. to prove `commit()` re-stamps it
    /// — see `version_stamped_on_any_commit`) cannot change the const; it sets
    /// the field explicitly here, then serializes via `to_bytes()` rather than
    /// hand-assembling raw header bytes.
    #[cfg(test)]
    pub fn with_format_version(version: u32) -> Self {
        Self {
            format_version: version,
            ..Self::new()
        }
    }

    /// The currently active root pointer.
    pub fn active_root_pointer(&self) -> &RootPointer {
        match self.active_root {
            ActiveRoot::A => &self.root_a,
            ActiveRoot::B => &self.root_b,
        }
    }

    /// The inactive root pointer (will be overwritten on next commit).
    pub fn inactive_root_pointer(&self) -> &RootPointer {
        match self.active_root {
            ActiveRoot::A => &self.root_b,
            ActiveRoot::B => &self.root_a,
        }
    }

    /// Prepare the next commit: write new metadata to the inactive root
    /// pointer and flip the active flag.
    ///
    /// Also re-stamps `format_version` to the writing binary's
    /// [`FORMAT_VERSION`]. A new binary always writes the current on-disk
    /// formats (e.g. `ColumnType::KeywordBlocked`), so the header must
    /// advertise the current version even when committing a file created by an
    /// older binary — otherwise an old binary could later open the upgraded
    /// file and silently misread the new column layout ([[code-must-not-lie]]).
    /// This makes any new-binary write a one-way upgrade. The stamp survives
    /// only because `SingleFileDirectory::commit` is refresh-first (it re-reads
    /// the on-disk header *before* this flip); see
    /// [[optimization-keyword-dict-offset-index]] and
    /// [[project_hnsw_recall_merge_persist_bug]].
    pub fn commit(&mut self, metadata_block: BlockId, checksum: u64) {
        let new_root = RootPointer::new(metadata_block, checksum);
        match self.active_root {
            ActiveRoot::A => self.root_b = new_root,
            ActiveRoot::B => self.root_a = new_root,
        }
        self.active_root = self.active_root.inactive();
        self.format_version = FORMAT_VERSION;
    }

    /// Serialize the header to a 4 KB byte buffer.
    pub fn to_bytes(&self) -> [u8; HEADER_SIZE as usize] {
        let mut buf = [0u8; HEADER_SIZE as usize];

        buf[OFF_MAGIC..OFF_MAGIC + 8].copy_from_slice(&MAGIC);
        buf[OFF_VERSION..OFF_VERSION + 4].copy_from_slice(&self.format_version.to_le_bytes());
        buf[OFF_BLOCK_SIZE..OFF_BLOCK_SIZE + 4].copy_from_slice(&self.block_size.to_le_bytes());

        // Root A
        let root_a_block = self
            .root_a
            .block_id
            .map_or(EMPTY_ROOT_BLOCK, |b| b.as_u64());
        buf[OFF_ROOT_A_BLOCK..OFF_ROOT_A_BLOCK + 8].copy_from_slice(&root_a_block.to_le_bytes());
        buf[OFF_ROOT_A_CHECKSUM..OFF_ROOT_A_CHECKSUM + 8]
            .copy_from_slice(&self.root_a.checksum.to_le_bytes());

        // Root B
        let root_b_block = self
            .root_b
            .block_id
            .map_or(EMPTY_ROOT_BLOCK, |b| b.as_u64());
        buf[OFF_ROOT_B_BLOCK..OFF_ROOT_B_BLOCK + 8].copy_from_slice(&root_b_block.to_le_bytes());
        buf[OFF_ROOT_B_CHECKSUM..OFF_ROOT_B_CHECKSUM + 8]
            .copy_from_slice(&self.root_b.checksum.to_le_bytes());

        // Active root flag
        buf[OFF_ACTIVE_ROOT] = self.active_root as u8;

        buf
    }

    /// Deserialize a header from a 4 KB byte buffer.
    ///
    /// # Errors
    ///
    /// Returns `LuciError::IndexCorrupted` if the magic bytes are wrong,
    /// the format version is unsupported, or the block size doesn't match.
    pub fn from_bytes(buf: &[u8; HEADER_SIZE as usize]) -> Result<Self> {
        // Validate magic.
        if buf[OFF_MAGIC..OFF_MAGIC + 8] != MAGIC {
            return Err(LuciError::IndexCorrupted(
                "invalid magic bytes — not a Luci index file".into(),
            ));
        }

        let format_version =
            u32::from_le_bytes(buf[OFF_VERSION..OFF_VERSION + 4].try_into().unwrap());
        if format_version > FORMAT_VERSION {
            return Err(LuciError::IndexCorrupted(format!(
                "unsupported format version {format_version} (max supported: {FORMAT_VERSION})"
            )));
        }

        let block_size =
            u32::from_le_bytes(buf[OFF_BLOCK_SIZE..OFF_BLOCK_SIZE + 4].try_into().unwrap());
        if block_size != BLOCK_SIZE {
            return Err(LuciError::IndexCorrupted(format!(
                "unexpected block size {block_size} (expected {BLOCK_SIZE})"
            )));
        }

        let root_a = read_root_pointer(buf, OFF_ROOT_A_BLOCK, OFF_ROOT_A_CHECKSUM);
        let root_b = read_root_pointer(buf, OFF_ROOT_B_BLOCK, OFF_ROOT_B_CHECKSUM);

        let active_root = match buf[OFF_ACTIVE_ROOT] {
            0 => ActiveRoot::A,
            1 => ActiveRoot::B,
            other => {
                return Err(LuciError::IndexCorrupted(format!(
                    "invalid active root flag: {other}"
                )));
            }
        };

        Ok(Self {
            format_version,
            block_size,
            root_a,
            root_b,
            active_root,
        })
    }
}

/// Compute the xxHash (XXH3-64) checksum of a metadata root block.
///
/// See [[architecture-storage-format#Checksum Algorithm]].
pub fn xxh3_checksum(data: &[u8]) -> u64 {
    xxhash_rust::xxh3::xxh3_64(data)
}

fn read_root_pointer(buf: &[u8], block_off: usize, checksum_off: usize) -> RootPointer {
    let raw_block = u64::from_le_bytes(buf[block_off..block_off + 8].try_into().unwrap());
    let checksum = u64::from_le_bytes(buf[checksum_off..checksum_off + 8].try_into().unwrap());

    if raw_block == EMPTY_ROOT_BLOCK {
        RootPointer::EMPTY
    } else {
        RootPointer::new(BlockId(raw_block), checksum)
    }
}

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

    #[test]
    fn new_header_has_empty_roots() {
        let h = FileHeader::new();
        assert_eq!(h.format_version, FORMAT_VERSION);
        assert_eq!(h.block_size, BLOCK_SIZE);
        assert_eq!(h.root_a, RootPointer::EMPTY);
        assert_eq!(h.root_b, RootPointer::EMPTY);
        assert_eq!(h.active_root, ActiveRoot::A);
    }

    #[test]
    fn round_trip_fresh_header() {
        let h = FileHeader::new();
        let bytes = h.to_bytes();
        let h2 = FileHeader::from_bytes(&bytes).unwrap();
        assert_eq!(h, h2);
    }

    #[test]
    fn round_trip_with_populated_roots() {
        let mut h = FileHeader::new();
        h.root_a = RootPointer::new(BlockId(42), 0xDEAD_BEEF);
        h.root_b = RootPointer::new(BlockId(99), 0xCAFE_BABE);
        h.active_root = ActiveRoot::B;

        let bytes = h.to_bytes();
        let h2 = FileHeader::from_bytes(&bytes).unwrap();
        assert_eq!(h, h2);
    }

    #[test]
    fn commit_flips_active_root() {
        let mut h = FileHeader::new();
        assert_eq!(h.active_root, ActiveRoot::A);

        // First commit writes to root B and makes it active.
        h.commit(BlockId(5), 0x1111);
        assert_eq!(h.active_root, ActiveRoot::B);
        assert_eq!(h.root_b, RootPointer::new(BlockId(5), 0x1111));
        assert_eq!(h.root_a, RootPointer::EMPTY);

        // Second commit writes to root A and makes it active.
        h.commit(BlockId(10), 0x2222);
        assert_eq!(h.active_root, ActiveRoot::A);
        assert_eq!(h.root_a, RootPointer::new(BlockId(10), 0x2222));
        // Root B unchanged from first commit.
        assert_eq!(h.root_b, RootPointer::new(BlockId(5), 0x1111));
    }

    #[test]
    fn active_and_inactive_root_pointers() {
        let mut h = FileHeader::new();
        h.commit(BlockId(5), 0x1111);
        // Active is now B.
        assert_eq!(
            *h.active_root_pointer(),
            RootPointer::new(BlockId(5), 0x1111)
        );
        assert_eq!(*h.inactive_root_pointer(), RootPointer::EMPTY);
    }

    #[test]
    fn bad_magic_is_rejected() {
        let mut bytes = FileHeader::new().to_bytes();
        bytes[0] = b'X';
        let err = FileHeader::from_bytes(&bytes).unwrap_err();
        assert!(format!("{err}").contains("magic"));
    }

    #[test]
    fn future_version_is_rejected() {
        let mut h = FileHeader::new();
        h.format_version = FORMAT_VERSION + 1;
        let bytes = h.to_bytes();
        let err = FileHeader::from_bytes(&bytes).unwrap_err();
        assert!(format!("{err}").contains("version"));
    }

    #[test]
    fn wrong_block_size_is_rejected() {
        let mut bytes = FileHeader::new().to_bytes();
        // Overwrite block_size field with a different value.
        bytes[OFF_BLOCK_SIZE..OFF_BLOCK_SIZE + 4].copy_from_slice(&(128 * 1024u32).to_le_bytes());
        let err = FileHeader::from_bytes(&bytes).unwrap_err();
        assert!(format!("{err}").contains("block size"));
    }

    #[test]
    fn invalid_active_root_flag_is_rejected() {
        let mut bytes = FileHeader::new().to_bytes();
        bytes[OFF_ACTIVE_ROOT] = 2;
        let err = FileHeader::from_bytes(&bytes).unwrap_err();
        assert!(format!("{err}").contains("active root"));
    }

    #[test]
    fn header_is_exactly_4kb() {
        let bytes = FileHeader::new().to_bytes();
        assert_eq!(bytes.len(), 4096);
    }

    #[test]
    fn active_root_inactive_is_inverse() {
        assert_eq!(ActiveRoot::A.inactive(), ActiveRoot::B);
        assert_eq!(ActiveRoot::B.inactive(), ActiveRoot::A);
    }

    #[test]
    fn root_pointer_empty_is_not_populated() {
        assert!(!RootPointer::EMPTY.is_populated());
    }

    #[test]
    fn root_pointer_with_block_is_populated() {
        let rp = RootPointer::new(BlockId(0), 0);
        assert!(rp.is_populated());
    }

    #[test]
    fn xxh3_checksum_is_deterministic() {
        let data = b"hello luci";
        let c1 = xxh3_checksum(data);
        let c2 = xxh3_checksum(data);
        assert_eq!(c1, c2);
        assert_ne!(c1, 0); // extremely unlikely to be zero
    }

    #[test]
    fn xxh3_checksum_differs_for_different_data() {
        let c1 = xxh3_checksum(b"block A");
        let c2 = xxh3_checksum(b"block B");
        assert_ne!(c1, c2);
    }
}