25373448073

Committed 05 May 2026 11:23AM UTC coverage: 63.201% (+0.2%) from 63.042%

Build # 25373448073

Build Type

push

github

Committed by

web-flow

Commit Message

release: v0.5.1 (#94)

Co-authored-by: Claude Opus 4.7 (1M context) <noreply@anthropic.com>

Coverage Stats

7641 of 12090 relevant lines covered (63.2%)

1.21 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

79.9

/src/sql/pager/overflow.rs

//! Overflow storage for cells that don't fit on one table-leaf page.
//!
//! Two pieces live here:
//!
//! - [`OverflowRef`] — the on-page marker that replaces a full cell when
//!   the cell's body is too large to keep inline. It carries the rowid
//!   (so the page's slot directory stays rowid-ordered), the total size
//!   of the external body, and a pointer to the first overflow page of
//!   the chain that holds the body.
//! - [`write_overflow_chain`] / [`read_overflow_chain`] — turn raw bytes
//!   into a chain of `Overflow`-typed pages and back. Each overflow page
//!   reuses the existing 7-byte page header (type tag + next-page + payload
//!   length) — we're not adding a new page format.
//!
//! **Decision to inline the rowid and NOT inline any of the body.** SQLite's
//! leaf-cell scheme keeps a prefix of the body inline before spilling, so
//! small lookups by rowid don't need a chain walk. We'd still have to chase
//! the chain for most columns anyway, so for simplicity this implementation
//! spills the entire body. A later optimization can split cells at a
//! threshold and keep a prefix inline without changing the page layout.
//!
//! **Overflow threshold.** Inserting a cell whose encoded length is more
//! than roughly a quarter of the page payload area (≈ 1000 bytes) is a
//! good candidate for overflow — on a ~4 KiB page you can still keep at
//! least 3-4 cells per page. The exact threshold is the caller's choice;
//! this module just exposes [`OVERFLOW_THRESHOLD`] as a suggestion.

use crate::error::{Result, SQLRiteError};
use crate::sql::pager::cell::{Cell, KIND_LOCAL, KIND_OVERFLOW};
use crate::sql::pager::page::{PAGE_HEADER_SIZE, PAGE_SIZE, PAYLOAD_PER_PAGE, PageType};
use crate::sql::pager::pager::Pager;
use crate::sql::pager::varint;

/// Inline cell-body size above which the caller should consider overflowing.
/// Sized so at least 4 inline cells can coexist on a page alongside their
/// slot directory.
pub const OVERFLOW_THRESHOLD: usize = PAYLOAD_PER_PAGE / 4;

/// On-page marker that stands in for a cell whose body lives in an overflow
/// chain. Rowid is inlined so the page's binary search over slots still
/// works without chasing the chain.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct OverflowRef {
    pub rowid: i64,
    /// Exact byte count that `read_overflow_chain` must produce; the
    /// caller then feeds those bytes to `LocalCellBody::decode`.
    pub total_body_len: u64,
    /// First page of the Overflow-type chain carrying the body.
    pub first_overflow_page: u32,
}

impl OverflowRef {
    /// Serializes the reference using the shared
    /// `[cell_length varint | kind_tag | body]` prefix; `kind_tag` is
    /// always `KIND_OVERFLOW` for this type.
    pub fn encode(&self) -> Vec<u8> {
        let mut body = Vec::with_capacity(1 + varint::MAX_VARINT_BYTES * 2 + 4);
        body.push(KIND_OVERFLOW);
        varint::write_i64(&mut body, self.rowid);
        varint::write_u64(&mut body, self.total_body_len);
        body.extend_from_slice(&self.first_overflow_page.to_le_bytes());

        let mut out = Vec::with_capacity(body.len() + varint::MAX_VARINT_BYTES);
        varint::write_u64(&mut out, body.len() as u64);
        out.extend_from_slice(&body);
        out
    }

    pub fn decode(buf: &[u8], pos: usize) -> Result<(OverflowRef, usize)> {
        let (body_len, len_bytes) = varint::read_u64(buf, pos)?;
        let body_start = pos + len_bytes;
        let body_end = body_start
            .checked_add(body_len as usize)
            .ok_or_else(|| SQLRiteError::Internal("overflow ref length overflow".to_string()))?;
        if body_end > buf.len() {
            return Err(SQLRiteError::Internal(format!(
                "overflow ref extends past buffer: needs {body_start}..{body_end}, have {}",
                buf.len()
            )));
        }

        let body = &buf[body_start..body_end];
        if body.first().copied() != Some(KIND_OVERFLOW) {
            return Err(SQLRiteError::Internal(format!(
                "OverflowRef::decode called on non-overflow entry (kind_tag = {:#x})",
                body.first().copied().unwrap_or(0)
            )));
        }
        let mut cur = 1usize;
        let (rowid, n) = varint::read_i64(body, cur)?;
        cur += n;
        let (total_body_len, n) = varint::read_u64(body, cur)?;
        cur += n;
        if cur + 4 > body.len() {
            return Err(SQLRiteError::Internal(
                "overflow ref truncated before first_overflow_page".to_string(),
            ));
        }
        let first_overflow_page = u32::from_le_bytes(body[cur..cur + 4].try_into().unwrap());
        cur += 4;
        if cur != body.len() {
            return Err(SQLRiteError::Internal(format!(
                "overflow ref had {} trailing bytes",
                body.len() - cur
            )));
        }
        Ok((
            OverflowRef {
                rowid,
                total_body_len,
                first_overflow_page,
            },
            body_end - pos,
        ))
    }
}

/// An on-page entry: either a full local cell, or a pointer to an overflow
/// chain carrying the cell's body.
#[derive(Debug, Clone, PartialEq)]
pub enum PagedEntry {
    Local(Cell),
    Overflow(OverflowRef),
}

impl PagedEntry {
    pub fn rowid(&self) -> i64 {
        match self {
            PagedEntry::Local(c) => c.rowid,
            PagedEntry::Overflow(r) => r.rowid,
        }
    }

    pub fn encode(&self) -> Result<Vec<u8>> {
        match self {
            PagedEntry::Local(c) => c.encode(),
            PagedEntry::Overflow(r) => Ok(r.encode()),
        }
    }

    /// Dispatches on the kind tag and returns the appropriate variant.
    ///
    /// Only `KIND_LOCAL` and `KIND_OVERFLOW` are valid here — `PagedEntry`
    /// is the table-leaf-cell type, so any other kind means a caller
    /// pointed the wrong decoder at this page (the slot directory layout
    /// is shared across leaf B-Trees, but secondary-index, HNSW, and
    /// FTS leaves carry kind-specific cells decoded by `IndexCell::decode`,
    /// `HnswNodeCell::decode`, and `FtsPostingCell::decode` respectively).
    /// The named-kind error makes that mistake obvious next time.
    pub fn decode(buf: &[u8], pos: usize) -> Result<(PagedEntry, usize)> {
        let kind = Cell::peek_kind(buf, pos)?;
        match kind {
            KIND_LOCAL => {
                let (c, n) = Cell::decode(buf, pos)?;
                Ok((PagedEntry::Local(c), n))
            }
            KIND_OVERFLOW => {
                let (r, n) = OverflowRef::decode(buf, pos)?;
                Ok((PagedEntry::Overflow(r), n))
            }
            other => Err(SQLRiteError::Internal(format!(
                "PagedEntry::decode at offset {pos} got kind tag {other:#x} ({}); \
                 expected KIND_LOCAL (0x01) or KIND_OVERFLOW (0x02). \
                 The caller is reading a {} page with the table-leaf decoder.",
                kind_name(other),
                kind_btree_hint(other),
            ))),
        }
    }
}

/// Human-readable label for a cell kind tag — used in error messages
/// to make wrong-decoder mistakes self-explanatory.
fn kind_name(tag: u8) -> &'static str {
    match tag {
        crate::sql::pager::cell::KIND_LOCAL => "KIND_LOCAL",
        crate::sql::pager::cell::KIND_OVERFLOW => "KIND_OVERFLOW",
        crate::sql::pager::cell::KIND_INTERIOR => "KIND_INTERIOR",
        crate::sql::pager::cell::KIND_INDEX => "KIND_INDEX",
        crate::sql::pager::cell::KIND_HNSW => "KIND_HNSW",
        crate::sql::pager::cell::KIND_FTS_POSTING => "KIND_FTS_POSTING",
        _ => "unknown kind",
    }
}

/// Hint pointing at which B-Tree owns a cell of the given kind.
fn kind_btree_hint(tag: u8) -> &'static str {
    match tag {
        crate::sql::pager::cell::KIND_INTERIOR => "B-Tree interior",
        crate::sql::pager::cell::KIND_INDEX => "secondary-index",
        crate::sql::pager::cell::KIND_HNSW => "HNSW",
        crate::sql::pager::cell::KIND_FTS_POSTING => "FTS",
        _ => "non-table",
    }
}

/// Writes `bytes` into a chain of Overflow-typed pages, drawing each
/// page number from the supplied [`PageAllocator`]. Returns the page
/// number of the first link in the chain (the value to record in the
/// `OverflowRef` cell on the owning leaf).
///
/// Pages no longer have to be consecutive — the chain is followed by
/// `next_page` pointers, and the allocator may hand out pages from a
/// freelist or preferred pool that aren't sequential.
pub fn write_overflow_chain(
    pager: &mut Pager,
    bytes: &[u8],
    alloc: &mut crate::sql::pager::allocator::PageAllocator,
) -> Result<u32> {
    if bytes.is_empty() {
        return Err(SQLRiteError::Internal(
            "refusing to write an empty overflow chain — caller should inline instead".to_string(),
        ));
    }
    // Allocate every page in the chain up front so each stage_page call
    // already knows the successor's page number.
    let chunks: Vec<&[u8]> = bytes.chunks(PAYLOAD_PER_PAGE).collect();
    let pages: Vec<u32> = (0..chunks.len()).map(|_| alloc.allocate()).collect();
    for (i, chunk) in chunks.iter().enumerate() {
        let next = if i + 1 < pages.len() { pages[i + 1] } else { 0 };
        pager.stage_page(pages[i], encode_overflow_page(next, chunk)?);
    }
    Ok(pages[0])
}

/// Walks an overflow chain starting at `first_page` and concatenates its
/// payload bytes. Reads exactly `total_body_len` bytes — a mismatch between
/// what the chain carries and what the OverflowRef claims is a corruption
/// error.
pub fn read_overflow_chain(pager: &Pager, first_page: u32, total_body_len: u64) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(total_body_len as usize);
    let mut current = first_page;
    while current != 0 {
        let raw = pager.read_page(current).ok_or_else(|| {
            SQLRiteError::Internal(format!("overflow chain references missing page {current}"))
        })?;
        let ty_byte = raw[0];
        if ty_byte != PageType::Overflow as u8 {
            return Err(SQLRiteError::Internal(format!(
                "page {current} was supposed to be Overflow but is type {ty_byte}"
            )));
        }
        let next = u32::from_le_bytes(raw[1..5].try_into().unwrap());
        let payload_len = u16::from_le_bytes(raw[5..7].try_into().unwrap()) as usize;
        if payload_len > PAYLOAD_PER_PAGE {
            return Err(SQLRiteError::Internal(format!(
                "overflow page {current} reports payload_len {payload_len} > max"
            )));
        }
        out.extend_from_slice(&raw[PAGE_HEADER_SIZE..PAGE_HEADER_SIZE + payload_len]);
        current = next;
    }
    if out.len() as u64 != total_body_len {
        return Err(SQLRiteError::Internal(format!(
            "overflow chain produced {} bytes, OverflowRef claimed {total_body_len}",
            out.len()
        )));
    }
    Ok(out)
}

/// Encodes a single `Overflow`-typed page holding `payload` bytes. Shared
/// with the rest of the pager via the standard 7-byte page header layout.
fn encode_overflow_page(next: u32, payload: &[u8]) -> Result<[u8; PAGE_SIZE]> {
    if payload.len() > PAYLOAD_PER_PAGE {
        return Err(SQLRiteError::Internal(format!(
            "overflow page payload {} exceeds max {PAYLOAD_PER_PAGE}",
            payload.len()
        )));
    }
    let mut buf = [0u8; PAGE_SIZE];
    buf[0] = PageType::Overflow as u8;
    buf[1..5].copy_from_slice(&next.to_le_bytes());
    buf[5..7].copy_from_slice(&(payload.len() as u16).to_le_bytes());
    buf[PAGE_HEADER_SIZE..PAGE_HEADER_SIZE + payload.len()].copy_from_slice(payload);
    Ok(buf)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sql::db::table::Value;

    fn tmp_path(name: &str) -> std::path::PathBuf {
        let mut p = std::env::temp_dir();
        let pid = std::process::id();
        let nanos = std::time::SystemTime::now()
            .duration_since(std::time::UNIX_EPOCH)
            .map(|d| d.as_nanos())
            .unwrap_or(0);
        p.push(format!("sqlrite-overflow-{pid}-{nanos}-{name}.sqlrite"));
        p
    }

    #[test]
    fn overflow_ref_round_trip() {
        let r = OverflowRef {
            rowid: 42,
            total_body_len: 123_456,
            first_overflow_page: 7,
        };
        let bytes = r.encode();
        let (back, consumed) = OverflowRef::decode(&bytes, 0).unwrap();
        assert_eq!(back, r);
        assert_eq!(consumed, bytes.len());
    }

    #[test]
    fn paged_entry_dispatches_on_kind() {
        let local = Cell::new(1, vec![Some(Value::Integer(10))]);
        let local_bytes = local.encode().unwrap();
        let (decoded, _) = PagedEntry::decode(&local_bytes, 0).unwrap();
        assert_eq!(decoded, PagedEntry::Local(local));

        let overflow = OverflowRef {
            rowid: 2,
            total_body_len: 5000,
            first_overflow_page: 13,
        };
        let overflow_bytes = overflow.encode();
        let (decoded, _) = PagedEntry::decode(&overflow_bytes, 0).unwrap();
        assert_eq!(decoded, PagedEntry::Overflow(overflow));
    }

    /// SQLR-1 — `PagedEntry::decode` is the table-leaf-cell decoder.
    /// Pointing it at a secondary-index leaf used to surface as a
    /// cryptic `unknown paged-entry kind tag 0x4`. The new error
    /// message names the offending kind and the B-Tree the caller
    /// is mistakenly walking.
    #[test]
    fn paged_entry_decode_rejects_index_kind_with_clear_error() {
        use crate::sql::pager::index_cell::IndexCell;
        let ic = IndexCell::new(42, Value::Text("alice".into()));
        let bytes = ic.encode().unwrap();
        let err = PagedEntry::decode(&bytes, 0).unwrap_err();
        let msg = format!("{err}");
        assert!(
            msg.contains("KIND_INDEX"),
            "expected error to name KIND_INDEX, got: {msg}",
        );
        assert!(
            msg.contains("secondary-index"),
            "expected error to identify the secondary-index B-Tree, got: {msg}",
        );
    }

    /// Symmetric coverage for HNSW and FTS — same wrong-decoder shape,
    /// same diagnostic guarantee.
    #[test]
    fn paged_entry_decode_rejects_hnsw_and_fts_kinds() {
        use crate::sql::pager::cell::{KIND_FTS_POSTING, KIND_HNSW};
        // Build minimal byte sequences carrying the right kind tag at
        // the right offset. Body content past the kind tag doesn't
        // matter — we expect the dispatch to short-circuit on the tag.
        for (tag, hint) in [(KIND_HNSW, "HNSW"), (KIND_FTS_POSTING, "FTS")] {
            // body_len declared as 1 (the kind tag itself); body is the
            // tag and nothing else. Honest about what's in the buffer
            // so a future tightening of `peek_kind` doesn't bite us.
            let bytes = vec![/*body_len varint=*/ 1u8, tag];
            let err = PagedEntry::decode(&bytes, 0).unwrap_err();
            let msg = format!("{err}");
            assert!(
                msg.contains(hint),
                "expected error to identify the {hint} B-Tree, got: {msg}",
            );
        }
    }

    #[test]
    fn peek_rowid_works_for_both_kinds() {
        let local = Cell::new(99, vec![Some(Value::Integer(1))]);
        let local_bytes = local.encode().unwrap();
        assert_eq!(Cell::peek_rowid(&local_bytes, 0).unwrap(), 99);

        let overflow = OverflowRef {
            rowid: -7,
            total_body_len: 100,
            first_overflow_page: 42,
        };
        let overflow_bytes = overflow.encode();
        assert_eq!(Cell::peek_rowid(&overflow_bytes, 0).unwrap(), -7);
    }

    #[test]
    fn write_then_read_overflow_chain() {
        let path = tmp_path("chain");
        let mut pager = Pager::create(&path).unwrap();

        // A blob that definitely spans multiple pages.
        let blob: Vec<u8> = (0..10_000).map(|i| (i % 251) as u8).collect();
        let pages_needed = blob.len().div_ceil(PAYLOAD_PER_PAGE) as u32;
        let mut alloc =
            crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
        let start = write_overflow_chain(&mut pager, &blob, &mut alloc).unwrap();
        assert_eq!(start, 10);
        // Linear allocation from page 10 → high water = 10 + pages_needed.
        assert_eq!(alloc.high_water(), 10 + pages_needed);

        pager
            .commit(crate::sql::pager::header::DbHeader {
                page_count: alloc.high_water(),
                schema_root_page: 1,
                format_version: crate::sql::pager::header::FORMAT_VERSION_BASELINE,
                freelist_head: 0,
            })
            .unwrap();

        // Fresh pager to verify we read from disk.
        drop(pager);
        let pager = Pager::open(&path).unwrap();
        let back = read_overflow_chain(&pager, start, blob.len() as u64).unwrap();
        assert_eq!(back, blob);

        let _ = std::fs::remove_file(&path);
    }

    #[test]
    fn read_overflow_chain_rejects_length_mismatch() {
        let path = tmp_path("mismatch");
        let mut pager = Pager::create(&path).unwrap();
        let blob = vec![1u8; 500];
        let mut alloc =
            crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
        let start = write_overflow_chain(&mut pager, &blob, &mut alloc).unwrap();
        assert_eq!(start, 10);
        pager
            .commit(crate::sql::pager::header::DbHeader {
                page_count: alloc.high_water(),
                schema_root_page: 1,
                format_version: crate::sql::pager::header::FORMAT_VERSION_BASELINE,
                freelist_head: 0,
            })
            .unwrap();

        // Claim more bytes than the chain actually carries.
        let err = read_overflow_chain(&pager, start, 999).unwrap_err();
        assert!(format!("{err}").contains("overflow chain produced"));

        let _ = std::fs::remove_file(&path);
    }

    #[test]
    fn empty_chain_is_rejected() {
        let path = tmp_path("empty");
        let mut pager = Pager::create(&path).unwrap();
        let mut alloc =
            crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
        let err = write_overflow_chain(&mut pager, &[], &mut alloc).unwrap_err();
        assert!(format!("{err}").contains("empty overflow chain"));
        let _ = std::fs::remove_file(&path);
    }

    #[test]
    fn overflow_threshold_is_reasonable() {
        // The threshold should leave room for at least 4 cells per page.
        assert!(OVERFLOW_THRESHOLD <= PAYLOAD_PER_PAGE / 4);
        // And it should be comfortably larger than a typical small cell.
        assert!(OVERFLOW_THRESHOLD > 200);
    }
}

1	//! Overflow storage for cells that don't fit on one table-leaf page.
2	//!
3	//! Two pieces live here:
4	//!
5	//! - [`OverflowRef`] — the on-page marker that replaces a full cell when
6	//! the cell's body is too large to keep inline. It carries the rowid
7	//! (so the page's slot directory stays rowid-ordered), the total size
8	//! of the external body, and a pointer to the first overflow page of
9	//! the chain that holds the body.
10	//! - [`write_overflow_chain`] / [`read_overflow_chain`] — turn raw bytes
11	//! into a chain of `Overflow`-typed pages and back. Each overflow page
12	//! reuses the existing 7-byte page header (type tag + next-page + payload
13	//! length) — we're not adding a new page format.
14	//!
15	//! Decision to inline the rowid and NOT inline any of the body. SQLite's
16	//! leaf-cell scheme keeps a prefix of the body inline before spilling, so
17	//! small lookups by rowid don't need a chain walk. We'd still have to chase
18	//! the chain for most columns anyway, so for simplicity this implementation
19	//! spills the entire body. A later optimization can split cells at a
20	//! threshold and keep a prefix inline without changing the page layout.
21	//!
22	//! Overflow threshold. Inserting a cell whose encoded length is more
23	//! than roughly a quarter of the page payload area (≈ 1000 bytes) is a
24	//! good candidate for overflow — on a ~4 KiB page you can still keep at
25	//! least 3-4 cells per page. The exact threshold is the caller's choice;
26	//! this module just exposes [`OVERFLOW_THRESHOLD`] as a suggestion.
27
28	use crate::error::{Result, SQLRiteError};
29	use crate::sql::pager::cell::{Cell, KIND_LOCAL, KIND_OVERFLOW};
30	use crate::sql::pager::page::{PAGE_HEADER_SIZE, PAGE_SIZE, PAYLOAD_PER_PAGE, PageType};
31	use crate::sql::pager::pager::Pager;
32	use crate::sql::pager::varint;
33
34	/// Inline cell-body size above which the caller should consider overflowing.
35	/// Sized so at least 4 inline cells can coexist on a page alongside their
36	/// slot directory.
37	pub const OVERFLOW_THRESHOLD: usize = PAYLOAD_PER_PAGE / 4;
38
39	/// On-page marker that stands in for a cell whose body lives in an overflow
40	/// chain. Rowid is inlined so the page's binary search over slots still
41	/// works without chasing the chain.
42	#[derive(Debug, Clone, PartialEq, Eq)]
43	pub struct OverflowRef {
44	pub rowid: i64,
45	/// Exact byte count that `read_overflow_chain` must produce; the
46	/// caller then feeds those bytes to `LocalCellBody::decode`.
47	pub total_body_len: u64,
48	/// First page of the Overflow-type chain carrying the body.
49	pub first_overflow_page: u32,
50	}
51
52	impl OverflowRef {
53	/// Serializes the reference using the shared
54	/// `[cell_length varint \| kind_tag \| body]` prefix; `kind_tag` is
55	/// always `KIND_OVERFLOW` for this type.
56	pub fn encode(&self) -> Vec<u8> {	1✔
57	let mut body = Vec::with_capacity(1 + varint::MAX_VARINT_BYTES * 2 + 4);	1✔
58	body.push(KIND_OVERFLOW);	1✔
59	varint::write_i64(&mut body, self.rowid);	1✔
60	varint::write_u64(&mut body, self.total_body_len);	1✔
61	body.extend_from_slice(&self.first_overflow_page.to_le_bytes());	1✔
62
63	let mut out = Vec::with_capacity(body.len() + varint::MAX_VARINT_BYTES);	1✔
64	varint::write_u64(&mut out, body.len() as u64);	2✔
65	out.extend_from_slice(&body);	1✔
66	out	1✔
67	}
68
69	pub fn decode(buf: &[u8], pos: usize) -> Result<(OverflowRef, usize)> {	1✔
70	let (body_len, len_bytes) = varint::read_u64(buf, pos)?;	1✔
71	let body_start = pos + len_bytes;	1✔
72	let body_end = body_start	2✔
73	.checked_add(body_len as usize)	1✔
74	.ok_or_else(\|\| SQLRiteError::Internal("overflow ref length overflow".to_string()))?;	1✔
75	if body_end > buf.len() {	1✔
76	return Err(SQLRiteError::Internal(format!(	×
77	"overflow ref extends past buffer: needs {body_start}..{body_end}, have {}",	×
78	buf.len()	×
79	)));
80	}
81
82	let body = &buf[body_start..body_end];	1✔
83	if body.first().copied() != Some(KIND_OVERFLOW) {	1✔
84	return Err(SQLRiteError::Internal(format!(	×
85	"OverflowRef::decode called on non-overflow entry (kind_tag = {:#x})",	×
86	body.first().copied().unwrap_or(0)	×
87	)));
88	}
89	let mut cur = 1usize;	1✔
90	let (rowid, n) = varint::read_i64(body, cur)?;	1✔
91	cur += n;	1✔
92	let (total_body_len, n) = varint::read_u64(body, cur)?;	1✔
93	cur += n;	1✔
94	if cur + 4 > body.len() {	2✔
95	return Err(SQLRiteError::Internal(	×
96	"overflow ref truncated before first_overflow_page".to_string(),	×
97	));
98	}
99	let first_overflow_page = u32::from_le_bytes(body[cur..cur + 4].try_into().unwrap());	2✔
100	cur += 4;	2✔
101	if cur != body.len() {	1✔
102	return Err(SQLRiteError::Internal(format!(	×
103	"overflow ref had {} trailing bytes",	×
104	body.len() - cur	×
105	)));
106	}
107	Ok((	1✔
108	OverflowRef {	1✔
109	rowid,	×
110	total_body_len,	×
111	first_overflow_page,	×
112	},
113	body_end - pos,	1✔
114	))
115	}
116	}
117
118	/// An on-page entry: either a full local cell, or a pointer to an overflow
119	/// chain carrying the cell's body.
120	#[derive(Debug, Clone, PartialEq)]
121	pub enum PagedEntry {
122	Local(Cell),
123	Overflow(OverflowRef),
124	}
125
126	impl PagedEntry {
127	pub fn rowid(&self) -> i64 {	×
128	match self {	×
129	PagedEntry::Local(c) => c.rowid,	×
130	PagedEntry::Overflow(r) => r.rowid,	×
131	}
132	}
133
134	pub fn encode(&self) -> Result<Vec<u8>> {	×
135	match self {	×
136	PagedEntry::Local(c) => c.encode(),	×
137	PagedEntry::Overflow(r) => Ok(r.encode()),	×
138	}
139	}
140
141	/// Dispatches on the kind tag and returns the appropriate variant.
142	///
143	/// Only `KIND_LOCAL` and `KIND_OVERFLOW` are valid here — `PagedEntry`
144	/// is the table-leaf-cell type, so any other kind means a caller
145	/// pointed the wrong decoder at this page (the slot directory layout
146	/// is shared across leaf B-Trees, but secondary-index, HNSW, and
147	/// FTS leaves carry kind-specific cells decoded by `IndexCell::decode`,
148	/// `HnswNodeCell::decode`, and `FtsPostingCell::decode` respectively).
149	/// The named-kind error makes that mistake obvious next time.
150	pub fn decode(buf: &[u8], pos: usize) -> Result<(PagedEntry, usize)> {	2✔
151	let kind = Cell::peek_kind(buf, pos)?;	2✔
152	match kind {	2✔
153	KIND_LOCAL => {	×
154	let (c, n) = Cell::decode(buf, pos)?;	2✔
155	Ok((PagedEntry::Local(c), n))	2✔
156	}
157	KIND_OVERFLOW => {	×
158	let (r, n) = OverflowRef::decode(buf, pos)?;	1✔
159	Ok((PagedEntry::Overflow(r), n))	1✔
160	}
161	other => Err(SQLRiteError::Internal(format!(	2✔
162	"PagedEntry::decode at offset {pos} got kind tag {other:#x} ({}); \	×
163	expected KIND_LOCAL (0x01) or KIND_OVERFLOW (0x02). \	×
164	The caller is reading a {} page with the table-leaf decoder.",	×
165	kind_name(other),	1✔
166	kind_btree_hint(other),	1✔
167	))),
168	}
169	}
170	}
171
172	/// Human-readable label for a cell kind tag — used in error messages
173	/// to make wrong-decoder mistakes self-explanatory.
174	fn kind_name(tag: u8) -> &'static str {	1✔
175	match tag {	1✔
176	crate::sql::pager::cell::KIND_LOCAL => "KIND_LOCAL",	×
177	crate::sql::pager::cell::KIND_OVERFLOW => "KIND_OVERFLOW",	×
178	crate::sql::pager::cell::KIND_INTERIOR => "KIND_INTERIOR",	×
179	crate::sql::pager::cell::KIND_INDEX => "KIND_INDEX",	1✔
180	crate::sql::pager::cell::KIND_HNSW => "KIND_HNSW",	1✔
181	crate::sql::pager::cell::KIND_FTS_POSTING => "KIND_FTS_POSTING",	1✔
182	_ => "unknown kind",	×
183	}
184	}
185
186	/// Hint pointing at which B-Tree owns a cell of the given kind.
187	fn kind_btree_hint(tag: u8) -> &'static str {	1✔
188	match tag {	1✔
189	crate::sql::pager::cell::KIND_INTERIOR => "B-Tree interior",	×
190	crate::sql::pager::cell::KIND_INDEX => "secondary-index",	1✔
191	crate::sql::pager::cell::KIND_HNSW => "HNSW",	1✔
192	crate::sql::pager::cell::KIND_FTS_POSTING => "FTS",	1✔
193	_ => "non-table",	×
194	}
195	}
196
197	/// Writes `bytes` into a chain of Overflow-typed pages, drawing each
198	/// page number from the supplied [`PageAllocator`]. Returns the page
199	/// number of the first link in the chain (the value to record in the
200	/// `OverflowRef` cell on the owning leaf).
201	///
202	/// Pages no longer have to be consecutive — the chain is followed by
203	/// `next_page` pointers, and the allocator may hand out pages from a
204	/// freelist or preferred pool that aren't sequential.
205	pub fn write_overflow_chain(	1✔
206	pager: &mut Pager,
207	bytes: &[u8],
208	alloc: &mut crate::sql::pager::allocator::PageAllocator,
209	) -> Result<u32> {
210	if bytes.is_empty() {	1✔
211	return Err(SQLRiteError::Internal(	1✔
212	"refusing to write an empty overflow chain — caller should inline instead".to_string(),	1✔
213	));
214	}
215	// Allocate every page in the chain up front so each stage_page call
216	// already knows the successor's page number.
217	let chunks: Vec<&[u8]> = bytes.chunks(PAYLOAD_PER_PAGE).collect();	1✔
218	let pages: Vec<u32> = (0..chunks.len()).map(\|_\| alloc.allocate()).collect();	4✔
219	for (i, chunk) in chunks.iter().enumerate() {	2✔
220	let next = if i + 1 < pages.len() { pages[i + 1] } else { 0 };	3✔
221	pager.stage_page(pages[i], encode_overflow_page(next, chunk)?);	2✔
222	}
223	Ok(pages[0])	1✔
224	}
225
226	/// Walks an overflow chain starting at `first_page` and concatenates its
227	/// payload bytes. Reads exactly `total_body_len` bytes — a mismatch between
228	/// what the chain carries and what the OverflowRef claims is a corruption
229	/// error.
230	pub fn read_overflow_chain(pager: &Pager, first_page: u32, total_body_len: u64) -> Result<Vec<u8>> {	2✔
231	let mut out = Vec::with_capacity(total_body_len as usize);	1✔
232	let mut current = first_page;	1✔
233	while current != 0 {	2✔
234	let raw = pager.read_page(current).ok_or_else(\|\| {	2✔
235	SQLRiteError::Internal(format!("overflow chain references missing page {current}"))	×
236	})?;
237	let ty_byte = raw[0];	1✔
238	if ty_byte != PageType::Overflow as u8 {	1✔
239	return Err(SQLRiteError::Internal(format!(	×
240	"page {current} was supposed to be Overflow but is type {ty_byte}"
241	)));
242	}
243	let next = u32::from_le_bytes(raw[1..5].try_into().unwrap());	2✔
244	let payload_len = u16::from_le_bytes(raw[5..7].try_into().unwrap()) as usize;	1✔
245	if payload_len > PAYLOAD_PER_PAGE {	1✔
246	return Err(SQLRiteError::Internal(format!(	×
247	"overflow page {current} reports payload_len {payload_len} > max"
248	)));
249	}
250	out.extend_from_slice(&raw[PAGE_HEADER_SIZE..PAGE_HEADER_SIZE + payload_len]);	2✔
251	current = next;	1✔
252	}
253	if out.len() as u64 != total_body_len {	2✔
254	return Err(SQLRiteError::Internal(format!(	1✔
255	"overflow chain produced {} bytes, OverflowRef claimed {total_body_len}",
256	out.len()	2✔
257	)));
258	}
259	Ok(out)	1✔
260	}
261
262	/// Encodes a single `Overflow`-typed page holding `payload` bytes. Shared
263	/// with the rest of the pager via the standard 7-byte page header layout.
264	fn encode_overflow_page(next: u32, payload: &[u8]) -> Result<[u8; PAGE_SIZE]> {	1✔
265	if payload.len() > PAYLOAD_PER_PAGE {	1✔
266	return Err(SQLRiteError::Internal(format!(	×
267	"overflow page payload {} exceeds max {PAYLOAD_PER_PAGE}",
268	payload.len()	×
269	)));
270	}
271	let mut buf = [0u8; PAGE_SIZE];	1✔
272	buf[0] = PageType::Overflow as u8;	1✔
273	buf[1..5].copy_from_slice(&next.to_le_bytes());	1✔
274	buf[5..7].copy_from_slice(&(payload.len() as u16).to_le_bytes());	1✔
275	buf[PAGE_HEADER_SIZE..PAGE_HEADER_SIZE + payload.len()].copy_from_slice(payload);	2✔
276	Ok(buf)	1✔
277	}
278
279	#[cfg(test)]
280	mod tests {
281	use super::*;
282	use crate::sql::db::table::Value;
283
284	fn tmp_path(name: &str) -> std::path::PathBuf {	1✔
285	let mut p = std::env::temp_dir();	1✔
286	let pid = std::process::id();	2✔
287	let nanos = std::time::SystemTime::now()	2✔
288	.duration_since(std::time::UNIX_EPOCH)	1✔
289	.map(\|d\| d.as_nanos())	3✔
290	.unwrap_or(0);
291	p.push(format!("sqlrite-overflow-{pid}-{nanos}-{name}.sqlrite"));	1✔
292	p	1✔
293	}
294
295	#[test]
296	fn overflow_ref_round_trip() {	3✔
297	let r = OverflowRef {
298	rowid: 42,
299	total_body_len: 123_456,
300	first_overflow_page: 7,
301	};
302	let bytes = r.encode();	1✔
303	let (back, consumed) = OverflowRef::decode(&bytes, 0).unwrap();	2✔
304	assert_eq!(back, r);	1✔
305	assert_eq!(consumed, bytes.len());	1✔
306	}
307
308	#[test]
309	fn paged_entry_dispatches_on_kind() {	3✔
310	let local = Cell::new(1, vec![Some(Value::Integer(10))]);	1✔
311	let local_bytes = local.encode().unwrap();	2✔
312	let (decoded, _) = PagedEntry::decode(&local_bytes, 0).unwrap();	2✔
313	assert_eq!(decoded, PagedEntry::Local(local));	1✔
314
315	let overflow = OverflowRef {
316	rowid: 2,
317	total_body_len: 5000,
318	first_overflow_page: 13,
319	};
320	let overflow_bytes = overflow.encode();	1✔
321	let (decoded, _) = PagedEntry::decode(&overflow_bytes, 0).unwrap();	2✔
322	assert_eq!(decoded, PagedEntry::Overflow(overflow));	1✔
323	}
324
325	/// SQLR-1 — `PagedEntry::decode` is the table-leaf-cell decoder.
326	/// Pointing it at a secondary-index leaf used to surface as a
327	/// cryptic `unknown paged-entry kind tag 0x4`. The new error
328	/// message names the offending kind and the B-Tree the caller
329	/// is mistakenly walking.
330	#[test]
331	fn paged_entry_decode_rejects_index_kind_with_clear_error() {	4✔
332	use crate::sql::pager::index_cell::IndexCell;
333	let ic = IndexCell::new(42, Value::Text("alice".into()));	1✔
334	let bytes = ic.encode().unwrap();	2✔
335	let err = PagedEntry::decode(&bytes, 0).unwrap_err();	2✔
336	let msg = format!("{err}");	2✔
337	assert!(	×
338	msg.contains("KIND_INDEX"),	2✔
339	"expected error to name KIND_INDEX, got: {msg}",
340	);
341	assert!(	×
342	msg.contains("secondary-index"),	2✔
343	"expected error to identify the secondary-index B-Tree, got: {msg}",
344	);
345	}
346
347	/// Symmetric coverage for HNSW and FTS — same wrong-decoder shape,
348	/// same diagnostic guarantee.
349	#[test]
350	fn paged_entry_decode_rejects_hnsw_and_fts_kinds() {	3✔
351	use crate::sql::pager::cell::{KIND_FTS_POSTING, KIND_HNSW};
352	// Build minimal byte sequences carrying the right kind tag at
353	// the right offset. Body content past the kind tag doesn't
354	// matter — we expect the dispatch to short-circuit on the tag.
355	for (tag, hint) in [(KIND_HNSW, "HNSW"), (KIND_FTS_POSTING, "FTS")] {	2✔
356	// body_len declared as 1 (the kind tag itself); body is the
357	// tag and nothing else. Honest about what's in the buffer
358	// so a future tightening of `peek_kind` doesn't bite us.
359	let bytes = vec![/body_len varint=/ 1u8, tag];	2✔
360	let err = PagedEntry::decode(&bytes, 0).unwrap_err();	2✔
361	let msg = format!("{err}");	2✔
362	assert!(	×
363	msg.contains(hint),	2✔
364	"expected error to identify the {hint} B-Tree, got: {msg}",
365	);
366	}
367	}
368
369	#[test]
370	fn peek_rowid_works_for_both_kinds() {	3✔
371	let local = Cell::new(99, vec![Some(Value::Integer(1))]);	1✔
372	let local_bytes = local.encode().unwrap();	2✔
373	assert_eq!(Cell::peek_rowid(&local_bytes, 0).unwrap(), 99);	2✔
374
375	let overflow = OverflowRef {
376	rowid: -7,
377	total_body_len: 100,
378	first_overflow_page: 42,
379	};
380	let overflow_bytes = overflow.encode();	1✔
381	assert_eq!(Cell::peek_rowid(&overflow_bytes, 0).unwrap(), -7);	2✔
382	}
383
384	#[test]
385	fn write_then_read_overflow_chain() {	3✔
386	let path = tmp_path("chain");	1✔
387	let mut pager = Pager::create(&path).unwrap();	2✔
388
389	// A blob that definitely spans multiple pages.
390	let blob: Vec<u8> = (0..10_000).map(\|i\| (i % 251) as u8).collect();	4✔
391	let pages_needed = blob.len().div_ceil(PAYLOAD_PER_PAGE) as u32;	2✔
392	let mut alloc =	1✔
393	crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
394	let start = write_overflow_chain(&mut pager, &blob, &mut alloc).unwrap();	2✔
395	assert_eq!(start, 10);	1✔
396	// Linear allocation from page 10 → high water = 10 + pages_needed.
397	assert_eq!(alloc.high_water(), 10 + pages_needed);	1✔
398
399	pager
400	.commit(crate::sql::pager::header::DbHeader {	1✔
401	page_count: alloc.high_water(),	1✔
402	schema_root_page: 1,
403	format_version: crate::sql::pager::header::FORMAT_VERSION_BASELINE,
404	freelist_head: 0,
405	})
406	.unwrap();
407
408	// Fresh pager to verify we read from disk.
409	drop(pager);	1✔
410	let pager = Pager::open(&path).unwrap();	1✔
411	let back = read_overflow_chain(&pager, start, blob.len() as u64).unwrap();	2✔
412	assert_eq!(back, blob);	2✔
413
414	let _ = std::fs::remove_file(&path);	1✔
415	}
416
417	#[test]
418	fn read_overflow_chain_rejects_length_mismatch() {	3✔
419	let path = tmp_path("mismatch");	1✔
420	let mut pager = Pager::create(&path).unwrap();	2✔
421	let blob = vec![1u8; 500];	1✔
422	let mut alloc =	2✔
423	crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
424	let start = write_overflow_chain(&mut pager, &blob, &mut alloc).unwrap();	2✔
425	assert_eq!(start, 10);	1✔
426	pager
427	.commit(crate::sql::pager::header::DbHeader {	1✔
428	page_count: alloc.high_water(),	1✔
429	schema_root_page: 1,
430	format_version: crate::sql::pager::header::FORMAT_VERSION_BASELINE,
431	freelist_head: 0,
432	})
433	.unwrap();
434
435	// Claim more bytes than the chain actually carries.
436	let err = read_overflow_chain(&pager, start, 999).unwrap_err();	1✔
437	assert!(format!("{err}").contains("overflow chain produced"));	2✔
438
439	let _ = std::fs::remove_file(&path);	1✔
440	}
441
442	#[test]
443	fn empty_chain_is_rejected() {	3✔
444	let path = tmp_path("empty");	1✔
445	let mut pager = Pager::create(&path).unwrap();	2✔
446	let mut alloc =	2✔
447	crate::sql::pager::allocator::PageAllocator::new(std::collections::VecDeque::new(), 10);
448	let err = write_overflow_chain(&mut pager, &[], &mut alloc).unwrap_err();	2✔
449	assert!(format!("{err}").contains("empty overflow chain"));	2✔
450	let _ = std::fs::remove_file(&path);	1✔
451	}
452
453	#[test]
454	fn overflow_threshold_is_reasonable() {	2✔
455	// The threshold should leave room for at least 4 cells per page.
456	assert!(OVERFLOW_THRESHOLD <= PAYLOAD_PER_PAGE / 4);	1✔
457	// And it should be comfortably larger than a typical small cell.
458	assert!(OVERFLOW_THRESHOLD > 200);	1✔
459	}
460	}

joaoh82 / rust_sqlite / 25373448073

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous