sqlrite/sql/pager/
index_cell.rs

1//! On-disk format for a single secondary-index entry.
2//!
3//! Each entry maps one indexed value to the rowid of the table row
4//! carrying it. For the Phase 3e eager-load model we store one cell per
5//! `(value, rowid)` pair on `TableLeaf`-style pages that live in their
6//! own per-index B-Tree. The tree's shape is identical to a table's —
7//! same leaves, same sibling-chain, same interior pages — so all the 3d
8//! machinery carries over. The only thing different is the per-cell
9//! encoding, signalled by `KIND_INDEX`.
10//!
11//! **Encoding.** Uses the shared `[cell_length | kind_tag | body]`
12//! prefix. The body mirrors a one-column local cell (so value-block
13//! helpers can be reused), except the `rowid` stored here is the
14//! *original* row's rowid — the one the index entry points at.
15//!
16//! ```text
17//!   cell_length   varint          bytes after this field
18//!   kind_tag      u8 = 0x04       (KIND_INDEX)
19//!   rowid         zigzag varint   original row's rowid
20//!   value_tag     u8              one of INTEGER/REAL/TEXT/BOOL
21//!   value_body    variable        the indexed value
22//! ```
23//!
24//! NULLs are never indexed (see `SecondaryIndex::insert`), so there's
25//! no null bitmap — a non-null value is always present.
26
27use crate::error::{Result, SQLRiteError};
28use crate::sql::db::table::Value;
29use crate::sql::pager::cell::{KIND_INDEX, decode_value, encode_value};
30use crate::sql::pager::varint;
31
32/// One `(value, rowid)` pair stored in a per-index B-Tree.
33#[derive(Debug, Clone, PartialEq)]
34pub struct IndexCell {
35    /// Rowid of the row in the base table that carries this value.
36    pub rowid: i64,
37    /// The indexed value. Always non-NULL (NULLs aren't indexed).
38    pub value: Value,
39}
40
41impl IndexCell {
42    pub fn new(rowid: i64, value: Value) -> Self {
43        Self { rowid, value }
44    }
45
46    pub fn encode(&self) -> Result<Vec<u8>> {
47        if matches!(self.value, Value::Null) {
48            return Err(SQLRiteError::Internal(
49                "refusing to encode a NULL index cell — NULLs aren't indexed".to_string(),
50            ));
51        }
52        let mut body = Vec::with_capacity(1 + varint::MAX_VARINT_BYTES + 16);
53        body.push(KIND_INDEX);
54        varint::write_i64(&mut body, self.rowid);
55        encode_value(&mut body, &self.value)?;
56
57        let mut out = Vec::with_capacity(body.len() + varint::MAX_VARINT_BYTES);
58        varint::write_u64(&mut out, body.len() as u64);
59        out.extend_from_slice(&body);
60        Ok(out)
61    }
62
63    pub fn decode(buf: &[u8], pos: usize) -> Result<(IndexCell, usize)> {
64        let (body_len, len_bytes) = varint::read_u64(buf, pos)?;
65        let body_start = pos + len_bytes;
66        let body_end = body_start
67            .checked_add(body_len as usize)
68            .ok_or_else(|| SQLRiteError::Internal("index cell length overflow".to_string()))?;
69        if body_end > buf.len() {
70            return Err(SQLRiteError::Internal(format!(
71                "index cell extends past buffer: needs {body_start}..{body_end}, have {}",
72                buf.len()
73            )));
74        }
75        let body = &buf[body_start..body_end];
76        if body.first().copied() != Some(KIND_INDEX) {
77            return Err(SQLRiteError::Internal(format!(
78                "IndexCell::decode called on non-index entry (kind_tag = {:#x})",
79                body.first().copied().unwrap_or(0)
80            )));
81        }
82        let mut cur = 1usize;
83        let (rowid, n) = varint::read_i64(body, cur)?;
84        cur += n;
85        let (value, n) = decode_value(body, cur)?;
86        cur += n;
87        if cur != body.len() {
88            return Err(SQLRiteError::Internal(format!(
89                "index cell had {} trailing bytes",
90                body.len() - cur
91            )));
92        }
93        Ok((IndexCell { rowid, value }, body_end - pos))
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100    use crate::sql::pager::cell::Cell;
101
102    #[test]
103    fn round_trip_integer_index_cell() {
104        let c = IndexCell::new(42, Value::Integer(-7));
105        let bytes = c.encode().unwrap();
106        let (back, n) = IndexCell::decode(&bytes, 0).unwrap();
107        assert_eq!(back, c);
108        assert_eq!(n, bytes.len());
109    }
110
111    #[test]
112    fn round_trip_text_index_cell() {
113        let c = IndexCell::new(99, Value::Text("alice".to_string()));
114        let bytes = c.encode().unwrap();
115        let (back, _) = IndexCell::decode(&bytes, 0).unwrap();
116        assert_eq!(back, c);
117    }
118
119    #[test]
120    fn peek_rowid_works_on_index_cells() {
121        // Cell::peek_rowid skips the length prefix + kind tag and reads
122        // the rowid varint — should work uniformly for every kind.
123        let c = IndexCell::new(12345, Value::Integer(0));
124        let bytes = c.encode().unwrap();
125        assert_eq!(Cell::peek_rowid(&bytes, 0).unwrap(), 12345);
126    }
127
128    #[test]
129    fn null_value_is_rejected() {
130        let c = IndexCell::new(1, Value::Null);
131        let err = c.encode().unwrap_err();
132        assert!(format!("{err}").contains("NULLs aren't indexed"));
133    }
134
135    #[test]
136    fn decode_rejects_wrong_kind_tag() {
137        use crate::sql::pager::cell::KIND_LOCAL;
138        let mut buf = Vec::new();
139        buf.push(1);
140        buf.push(KIND_LOCAL);
141        let err = IndexCell::decode(&buf, 0).unwrap_err();
142        assert!(format!("{err}").contains("non-index"));
143    }
144}
sqlrite/sql/pager/index_cell.rs

sqlrite/sql/pager/
index_cell.rs
