#![cfg_attr(test, allow(clippy::unwrap_used, clippy::expect_used))]
use forensicnomicon::sqlite::{
SQLITE_FREELIST_TRUNK_OFFSET, SQLITE_HEADER_SIZE, SQLITE_MAGIC, SQLITE_PAGE_SIZE_OFFSET,
};
const RESERVED_SPACE_OFFSET: usize = 20;
const TEXT_ENCODING_OFFSET: usize = 56;
const DB_SIZE_IN_PAGES_OFFSET: usize = 28;
const FREELIST_COUNT_OFFSET: usize = 36;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Error {
TooShort,
BadMagic,
BadPageSize(u32),
PageOutOfRange(u32),
NotATablePage(u8),
TruncatedCell,
TooManyPages,
MalformedFreelist,
MalformedOverflow,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ChainBreak;
#[derive(Debug, Clone, PartialEq)]
pub enum Value {
Null,
Integer(i64),
Real(f64),
Text(String),
Blob(Vec<u8>),
}
#[derive(Debug, Clone, PartialEq)]
pub struct Row {
pub rowid: i64,
pub values: Vec<Value>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct CarvedCell {
pub offset: usize,
pub byte_len: usize,
pub rowid: i64,
pub values: Vec<Value>,
pub confidence: f32,
}
#[derive(Debug, Clone, PartialEq)]
pub struct CellFragment {
pub offset: usize,
pub byte_len: usize,
pub surviving: Vec<(usize, Value)>,
pub missing: usize,
pub confidence: f32,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SpilledCell {
pub offset: usize,
pub byte_len: usize,
pub payload_len: usize,
pub rowid: i64,
pub serials: Vec<i64>,
pub local_len: usize,
pub local_payload_off: usize,
pub first_overflow: u32,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum TextEncoding {
#[default]
Utf8,
Utf16Le,
Utf16Be,
}
impl TextEncoding {
fn decode(self, bytes: &[u8]) -> String {
match self {
Self::Utf8 => String::from_utf8_lossy(bytes).into_owned(),
Self::Utf16Le => Self::decode_utf16(bytes, u16::from_le_bytes),
Self::Utf16Be => Self::decode_utf16(bytes, u16::from_be_bytes),
}
}
fn decode_utf16(bytes: &[u8], conv: fn([u8; 2]) -> u16) -> String {
let units: Vec<u16> = bytes
.chunks_exact(2)
.map(|c| conv([c[0], c[1]]))
.collect();
String::from_utf16_lossy(&units)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Header {
pub page_size: u32,
pub reserved: u8,
pub text_encoding: TextEncoding,
}
impl Header {
#[must_use]
pub fn usable_size(self) -> u32 {
self.page_size.saturating_sub(u32::from(self.reserved))
}
}
pub struct Database {
bytes: Vec<u8>,
header: Header,
wal: Option<WalOverlay>,
}
struct WalOverlay {
pages: std::collections::BTreeMap<u32, Vec<u8>>,
frames: Vec<WalFramePage>,
raw: Vec<u8>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WalFramePage {
pub frame_index: usize,
pub page_no: u32,
pub salt1: u32,
pub salt2: u32,
pub is_commit: bool,
pub page: Vec<u8>,
}
const MAX_PAGES_PER_WALK: usize = 1_000_000;
const MIN_INFERRED_COLUMNS: usize = 2;
const IN_PAGE_CONFIDENCE_FACTOR: f32 = 0.8;
const OVERFLOW_CHAIN_CONFIDENCE_FACTOR: f32 = 0.75;
const FREEBLOCK_RECONSTRUCT_CONFIDENCE: f32 = 0.4;
const FRAGMENT_CONFIDENCE: f32 = 0.2;
const MAX_FREEBLOCKS_PER_PAGE: usize = 4096;
const WAL_MAGIC_BE: u32 = 0x377f_0682;
const WAL_MAGIC_LE: u32 = 0x377f_0683;
impl Database {
pub fn open(bytes: Vec<u8>) -> Result<Self, Error> {
let header = parse_header(&bytes)?;
Ok(Self {
bytes,
header,
wal: None,
})
}
pub fn open_with_wal(bytes: Vec<u8>, wal: &[u8]) -> Result<Self, Error> {
let header = parse_header(&bytes)?;
let overlay = WalOverlay::parse(wal, header.page_size)?;
Ok(Self {
bytes,
header,
wal: overlay,
})
}
#[must_use]
pub fn wal_applied(&self) -> bool {
self.wal.as_ref().is_some_and(|w| !w.pages.is_empty())
}
#[must_use]
pub fn wal_frame_pages(&self) -> &[WalFramePage] {
self.wal.as_ref().map_or(&[], |w| w.frames.as_slice())
}
#[must_use]
pub fn wal_timeline(&self) -> Option<WalTimeline> {
let raw = self.wal.as_ref()?.raw.as_slice();
WalTimeline::parse(&self.bytes, raw, self.header.page_size).ok()
}
pub fn wal_timeline_from(bytes: &[u8], wal: &[u8]) -> Result<WalTimeline, WalValidationError> {
let header = parse_header(bytes).map_err(WalValidationError::Header)?;
WalTimeline::parse(bytes, wal, header.page_size)
}
#[must_use]
pub fn header(&self) -> Header {
self.header
}
#[must_use]
pub fn page_count(&self) -> u32 {
let header = self.header_page_count();
let file = self.file_page_count();
if header != 0 && header == file {
header
} else {
file
}
}
#[must_use]
pub fn header_page_count(&self) -> u32 {
be_u32(&self.bytes, DB_SIZE_IN_PAGES_OFFSET)
}
#[must_use]
pub fn file_page_count(&self) -> u32 {
let ps = self.header.page_size as usize;
u32::try_from(self.bytes.len() / ps).unwrap_or(u32::MAX)
}
#[must_use]
pub fn freelist_count(&self) -> u32 {
be_u32(&self.bytes, FREELIST_COUNT_OFFSET)
}
pub fn freelist_pages(&self) -> Result<Vec<u32>, Error> {
let (leaves, trunks) = self.freelist_pages_split()?;
let mut free: Vec<u32> = leaves.into_iter().collect();
free.extend(trunks);
Ok(free)
}
pub fn freelist_pages_split(
&self,
) -> Result<
(
std::collections::BTreeSet<u32>,
std::collections::BTreeSet<u32>,
),
Error,
> {
let mut leaves = std::collections::BTreeSet::new();
let mut trunks = std::collections::BTreeSet::new();
let mut trunk = be_u32(&self.bytes, SQLITE_FREELIST_TRUNK_OFFSET);
let total_pages = self.file_page_count();
let max_leaves = (self.header.page_size as usize / 4).saturating_sub(2);
let mut visited = 0usize;
let cap = total_pages as usize + 1;
while trunk != 0 {
visited += 1;
if visited > cap {
return Err(Error::MalformedFreelist);
}
if trunk > total_pages {
return Err(Error::MalformedFreelist);
}
let slice = self.page_slice(trunk)?;
let next = be_u32(slice, 0);
let leaf_count = be_u32(slice, 4) as usize;
if leaf_count > max_leaves {
return Err(Error::MalformedFreelist);
}
for i in 0..leaf_count {
let leaf = be_u32(slice, 8 + i * 4);
if leaf == 0 || leaf > total_pages {
return Err(Error::MalformedFreelist);
}
leaves.insert(leaf);
}
trunks.insert(trunk);
trunk = next;
}
Ok((leaves, trunks))
}
pub fn read_freed_overflow_chain(
&self,
first: u32,
remaining: usize,
usable: usize,
freed_leaves: &std::collections::BTreeSet<u32>,
) -> Result<(Vec<u8>, Vec<u32>), ChainBreak> {
let per_page = usable.checked_sub(4).filter(|&p| p > 0).ok_or(ChainBreak)?;
let max_deliverable = per_page.checked_mul(freed_leaves.len()).ok_or(ChainBreak)?;
if remaining > max_deliverable {
return Err(ChainBreak);
}
let total_pages = self.file_page_count();
let mut content = Vec::with_capacity(remaining);
let mut chain = Vec::new();
let mut visited = std::collections::BTreeSet::new();
let mut page = first;
let mut left = remaining;
while left > 0 {
if page == 0 || page > total_pages {
return Err(ChainBreak);
}
if !freed_leaves.contains(&page) {
return Err(ChainBreak);
}
if !visited.insert(page) {
return Err(ChainBreak); }
let slice = self.raw_page(page).ok_or(ChainBreak)?;
let next = be_u32(slice, 0);
let take = left.min(per_page);
let chunk = slice.get(4..4 + take).ok_or(ChainBreak)?;
content.extend_from_slice(chunk);
chain.push(page);
left -= take;
page = next;
}
Ok((content, chain))
}
#[must_use]
pub fn raw_page(&self, page: u32) -> Option<&[u8]> {
if page == 0 {
return None;
}
let ps = self.header.page_size as usize;
let start = (page as usize - 1).checked_mul(ps)?;
let end = start.checked_add(ps)?;
self.bytes.get(start..end)
}
#[must_use]
pub fn carve_cells(&self, page_bytes: &[u8], column_count: usize) -> Vec<CarvedCell> {
let mut out = Vec::new();
if column_count == 0 {
return out;
}
let mut off = 0usize;
while off < page_bytes.len() {
if let Some(cell) = try_carve_cell_at(page_bytes, off, Some(column_count), self.header.text_encoding) {
off += cell.byte_len.max(1);
out.push(cell);
} else {
off += 1;
}
}
out
}
#[must_use]
pub fn carve_cells_inferred(&self, page_bytes: &[u8]) -> Vec<CarvedCell> {
let mut out = Vec::new();
let mut off = 0usize;
while off < page_bytes.len() {
if let Some(cell) = try_carve_cell_at(page_bytes, off, None, self.header.text_encoding) {
off += cell.byte_len.max(1);
out.push(cell);
} else {
off += 1;
}
}
out
}
#[must_use]
pub fn carve_leaf_cells(&self, page_bytes: &[u8]) -> Vec<CarvedCell> {
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
let Some(&page_type) = page_bytes.get(hdr_off) else {
return Vec::new();
};
if page_type != 0x0d {
return Vec::new(); }
let cell_count = be_u16(page_bytes, hdr_off + 3) as usize;
let cell_ptr_array = hdr_off + 8; let mut out = Vec::new();
for i in 0..cell_count {
let cell_off = be_u16(page_bytes, cell_ptr_array + i * 2) as usize;
if cell_off == 0 || cell_off >= page_bytes.len() {
continue; }
if let Some(cell) = try_carve_cell_at(page_bytes, cell_off, None, self.header.text_encoding) {
out.push(cell);
}
}
out
}
#[must_use]
pub fn carve_free_regions(
&self,
page_bytes: &[u8],
column_count_hint: usize,
) -> Vec<CarvedCell> {
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
let Some(&page_type) = page_bytes.get(hdr_off) else {
return Vec::new();
};
if page_type != 0x0d {
return Vec::new(); }
let mut out = Vec::new();
let regions = self.free_regions_of_leaf(page_bytes, hdr_off);
for (lo, hi) in regions {
let Some(region) = page_bytes.get(lo..hi) else {
continue; };
let cells = if column_count_hint == 0 {
self.carve_cells_inferred(region)
} else {
self.carve_cells(region, column_count_hint)
};
for mut cell in cells {
cell.offset += lo;
cell.confidence *= IN_PAGE_CONFIDENCE_FACTOR;
out.push(cell);
}
}
out
}
#[must_use]
pub fn carve_overflow_records(&self, page_bytes: &[u8]) -> Vec<(CarvedCell, Vec<u32>)> {
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
let Some(&page_type) = page_bytes.get(hdr_off) else {
return Vec::new();
};
if page_type != 0x0d {
return Vec::new(); }
let Ok((freed_leaves, _trunks)) = self.freelist_pages_split() else {
return Vec::new();
};
let usable = self.header.usable_size() as usize;
let mut out = Vec::new();
let regions = self.free_regions_of_leaf(page_bytes, hdr_off);
for (lo, hi) in regions {
let Some(region) = page_bytes.get(lo..hi) else {
continue; };
let mut off = 0usize;
while off < region.len() {
let Some(sc) = try_carve_spilled_cell_at(region, off, usable, None) else {
off += 1;
continue;
};
if let Some((mut cell, chain)) =
self.resolve_spilled(region, &sc, usable, &freed_leaves)
{
cell.offset = lo + sc.offset;
out.push((cell, chain));
off += sc.byte_len.max(1);
} else {
off += 1;
}
}
}
out
}
fn resolve_spilled(
&self,
region: &[u8],
sc: &SpilledCell,
usable: usize,
freed_leaves: &std::collections::BTreeSet<u32>,
) -> Option<(CarvedCell, Vec<u32>)> {
let remaining = sc.payload_len.checked_sub(sc.local_len)?;
let local_payload =
region.get(sc.local_payload_off..sc.local_payload_off + sc.local_len)?;
let (chain_content, chain) = self
.read_freed_overflow_chain(sc.first_overflow, remaining, usable, freed_leaves)
.ok()?;
let mut payload = Vec::with_capacity(sc.payload_len);
payload.extend_from_slice(local_payload);
payload.extend_from_slice(&chain_content);
if payload.len() != sc.payload_len {
return None; }
let values = decode_record(&payload, sc.serials.len(), sc.rowid, self.header.text_encoding).ok()?;
if values.len() != sc.serials.len() {
return None; }
let any_replacement = values.iter().any(|v| match v {
Value::Text(t) => t.contains('\u{FFFD}'),
_ => false,
});
if any_replacement {
return None;
}
if !values.iter().any(is_distinctive) {
return None; }
let cell = CarvedCell {
offset: sc.offset,
byte_len: sc.byte_len,
rowid: sc.rowid,
values,
confidence: 0.9 * OVERFLOW_CHAIN_CONFIDENCE_FACTOR,
};
Some((cell, chain))
}
#[must_use]
pub fn carve_overflow_template_records(
&self,
page_bytes: &[u8],
) -> Vec<(CarvedCell, Vec<u32>)> {
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
if page_bytes.get(hdr_off) != Some(&0x0d) {
return Vec::new();
}
let Some(template) = freeblock_template(page_bytes, hdr_off, self.header.text_encoding) else {
return Vec::new();
};
let Ok((freed_leaves, _trunks)) = self.freelist_pages_split() else {
return Vec::new();
};
let usable = self.header.usable_size() as usize;
let mut out = Vec::new();
let first_freeblock = be_u16(page_bytes, hdr_off + 1) as usize;
let mut fb = first_freeblock;
let mut walked = 0usize;
let mut visited = std::collections::BTreeSet::new();
while fb != 0 && walked < MAX_FREEBLOCKS_PER_PAGE {
walked += 1;
if !visited.insert(fb) {
break; }
let next = be_u16(page_bytes, fb) as usize;
if let Some((cell, chain)) =
template.reconstruct_spilled(self, page_bytes, fb, usable, &freed_leaves)
{
out.push((cell, chain));
}
fb = next;
}
out
}
#[must_use]
pub fn carve_overflow_fragments(&self, page_bytes: &[u8]) -> Vec<CellFragment> {
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
let Some(&page_type) = page_bytes.get(hdr_off) else {
return Vec::new();
};
if page_type != 0x0d {
return Vec::new();
}
let Ok((freed_leaves, _trunks)) = self.freelist_pages_split() else {
return Vec::new();
};
let usable = self.header.usable_size() as usize;
let mut out = Vec::new();
let regions = self.free_regions_of_leaf(page_bytes, hdr_off);
for (lo, hi) in regions {
let Some(region) = page_bytes.get(lo..hi) else {
continue; };
let mut off = 0usize;
while off < region.len() {
let Some(sc) = try_carve_spilled_cell_at(region, off, usable, None) else {
off += 1;
continue;
};
let remaining = sc.payload_len.saturating_sub(sc.local_len);
let chain_ok = self
.read_freed_overflow_chain(sc.first_overflow, remaining, usable, &freed_leaves)
.is_ok();
if !chain_ok {
if let Some(mut frag) = salvage_local_prefix(region, &sc, self.header.text_encoding) {
frag.offset += lo;
out.push(frag);
}
}
off += sc.byte_len.max(1);
}
}
out
}
#[must_use]
pub fn reconstruct_freeblock_records(&self, page_bytes: &[u8]) -> Vec<CarvedCell> {
let _ = self;
reconstruct_freeblock_inner(page_bytes, self.header.text_encoding).0
}
#[must_use]
pub fn reconstruct_freeblock_fragments(&self, page_bytes: &[u8]) -> Vec<CellFragment> {
let _ = self;
reconstruct_freeblock_inner(page_bytes, self.header.text_encoding).1
}
fn free_regions_of_leaf(&self, page_bytes: &[u8], hdr_off: usize) -> Vec<(usize, usize)> {
if page_bytes.get(hdr_off) != Some(&0x0d) {
return Vec::new(); }
let cell_count = be_u16(page_bytes, hdr_off + 3) as usize;
let cell_ptr_array = hdr_off + 8; let usable = self.header.usable_size() as usize;
let mut live: Vec<(usize, usize)> = Vec::with_capacity(cell_count);
for i in 0..cell_count {
let cell_off = be_u16(page_bytes, cell_ptr_array + i * 2) as usize;
if cell_off == 0 || cell_off >= page_bytes.len() {
continue; }
if let Some(len) = live_cell_len(page_bytes, cell_off, usable) {
live.push((cell_off, cell_off.saturating_add(len)));
}
}
live.sort_unstable_by_key(|&(s, _)| s);
let content_lo = cell_ptr_array + cell_count * 2;
free_regions(&live, content_lo, page_bytes.len())
}
#[must_use]
pub fn has_user_table(&self) -> bool {
let Ok(rows) = self.read_table(1, 5) else {
return false; };
rows.iter().any(|row| {
let is_table = matches!(row.values.first(), Some(Value::Text(t)) if t == "table");
let user = matches!(
row.values.get(1),
Some(Value::Text(n)) if !n.starts_with("sqlite_")
);
is_table && user
})
}
#[must_use]
pub fn live_rowids(&self) -> std::collections::BTreeSet<i64> {
let mut ids = std::collections::BTreeSet::new();
let Ok(schema) = self.read_table(1, 5) else {
return ids; };
for row in schema {
let is_table = matches!(row.values.first(), Some(Value::Text(t)) if t == "table");
if !is_table {
continue; }
let Some(Value::Integer(root)) = row.values.get(3) else {
continue; };
let Ok(root) = u32::try_from(*root) else {
continue; };
let mut visited = 0usize;
self.collect_rowids(root, &mut ids, &mut visited);
}
ids
}
#[must_use]
pub fn live_rows(&self) -> std::collections::BTreeMap<i64, Vec<Value>> {
let mut rows = std::collections::BTreeMap::new();
let Ok(schema) = self.read_table(1, 5) else {
return rows; };
for row in schema {
let is_table = matches!(row.values.first(), Some(Value::Text(t)) if t == "table");
if !is_table {
continue; }
let Some(Value::Integer(root)) = row.values.get(3) else {
continue; };
let Ok(root) = u32::try_from(*root) else {
continue; };
let mut visited = 0usize;
self.collect_rows(root, &mut rows, &mut visited);
}
rows
}
#[must_use]
pub fn live_schema_rows(&self) -> Vec<Vec<Value>> {
match self.read_table(1, 5) {
Ok(rows) => rows.into_iter().map(|row| row.values).collect(),
Err(_) => Vec::new(), }
}
fn collect_rows(
&self,
page: u32,
rows: &mut std::collections::BTreeMap<i64, Vec<Value>>,
visited: &mut usize,
) {
*visited += 1;
if *visited > MAX_PAGES_PER_WALK {
return; }
let Ok(slice) = self.page_slice(page) else {
return; };
let hdr_off = if page == 1 { SQLITE_HEADER_SIZE } else { 0 };
let Some(&page_type) = slice.get(hdr_off) else {
return; };
let cell_count = be_u16(slice, hdr_off + 3) as usize;
match page_type {
0x0d => {
let cell_ptr_array = hdr_off + 8;
for i in 0..cell_count {
let cell_off = be_u16(slice, cell_ptr_array + i * 2) as usize;
if let Some(cell) = try_carve_cell_at(slice, cell_off, None, self.header.text_encoding) {
rows.insert(cell.rowid, cell.values);
} else if let Some(rowid) = live_cell_rowid(slice, cell_off) {
rows.entry(rowid).or_default(); }
}
}
0x05 => {
let cell_ptr_array = hdr_off + 12;
for i in 0..cell_count {
let cell_off = be_u16(slice, cell_ptr_array + i * 2) as usize;
let child = be_u32(slice, cell_off);
if child != 0 && child != page {
self.collect_rows(child, rows, visited);
}
}
let right = be_u32(slice, hdr_off + 8);
if right != 0 && right != page {
self.collect_rows(right, rows, visited);
}
}
_ => {} }
}
fn collect_rowids(
&self,
page: u32,
ids: &mut std::collections::BTreeSet<i64>,
visited: &mut usize,
) {
*visited += 1;
if *visited > MAX_PAGES_PER_WALK {
return; }
let Ok(slice) = self.page_slice(page) else {
return; };
let hdr_off = if page == 1 { SQLITE_HEADER_SIZE } else { 0 };
let Some(&page_type) = slice.get(hdr_off) else {
return; };
let cell_count = be_u16(slice, hdr_off + 3) as usize;
match page_type {
0x0d => {
let cell_ptr_array = hdr_off + 8;
for i in 0..cell_count {
let cell_off = be_u16(slice, cell_ptr_array + i * 2) as usize;
if let Some(rowid) = live_cell_rowid(slice, cell_off) {
ids.insert(rowid);
}
}
}
0x05 => {
let cell_ptr_array = hdr_off + 12;
for i in 0..cell_count {
let cell_off = be_u16(slice, cell_ptr_array + i * 2) as usize;
let child = be_u32(slice, cell_off);
if child != 0 && child != page {
self.collect_rowids(child, ids, visited);
}
}
let right = be_u32(slice, hdr_off + 8);
if right != 0 && right != page {
self.collect_rowids(right, ids, visited);
}
}
_ => {} }
}
pub fn read_table(&self, root_page: u32, column_count: usize) -> Result<Vec<Row>, Error> {
let mut rows = Vec::new();
let mut visited = 0usize;
self.walk_table_page(root_page, column_count, &mut rows, &mut visited)?;
Ok(rows)
}
fn page_slice(&self, page: u32) -> Result<&[u8], Error> {
if page == 0 {
return Err(Error::PageOutOfRange(0));
}
if let Some(wal) = &self.wal {
if let Some(overlaid) = wal.pages.get(&page) {
return Ok(overlaid.as_slice());
}
}
let ps = self.header.page_size as usize;
let start = (page as usize - 1) * ps;
let end = start.checked_add(ps).ok_or(Error::PageOutOfRange(page))?;
self.bytes
.get(start..end)
.ok_or(Error::PageOutOfRange(page))
}
fn walk_table_page(
&self,
page: u32,
column_count: usize,
rows: &mut Vec<Row>,
visited: &mut usize,
) -> Result<(), Error> {
*visited += 1;
if *visited > MAX_PAGES_PER_WALK {
return Err(Error::TooManyPages);
}
let slice = self.page_slice(page)?;
let hdr_off = if page == 1 { SQLITE_HEADER_SIZE } else { 0 };
let page_type = *slice.get(hdr_off).ok_or(Error::TruncatedCell)?;
let cell_count = be_u16(slice, hdr_off + 3) as usize;
match page_type {
0x0d => self.read_leaf_cells(slice, hdr_off, cell_count, column_count, rows),
0x05 => {
let cell_ptr_array = hdr_off + 12;
for i in 0..cell_count {
let p = cell_ptr_array + i * 2;
let cell_off = be_u16(slice, p) as usize;
let child = be_u32(slice, cell_off);
self.walk_table_page(child, column_count, rows, visited)?;
}
let right = be_u32(slice, hdr_off + 8);
self.walk_table_page(right, column_count, rows, visited)
}
other => Err(Error::NotATablePage(other)),
}
}
fn read_leaf_cells(
&self,
slice: &[u8],
hdr_off: usize,
cell_count: usize,
column_count: usize,
rows: &mut Vec<Row>,
) -> Result<(), Error> {
let cell_ptr_array = hdr_off + 8; for i in 0..cell_count {
let p = cell_ptr_array + i * 2;
let cell_off = be_u16(slice, p) as usize;
let row = self.decode_leaf_cell(slice, cell_off, column_count)?;
rows.push(row);
}
Ok(())
}
fn decode_leaf_cell(
&self,
slice: &[u8],
off: usize,
column_count: usize,
) -> Result<Row, Error> {
let (payload_len, n1) = read_varint(slice, off)?;
let (rowid, n2) = read_varint(slice, off + n1)?;
let payload_start = off + n1 + n2;
let total = usize::try_from(payload_len).map_err(|_| Error::TruncatedCell)?;
let usable = self.header.usable_size() as usize;
let local = local_payload_len(total, usable);
let payload = if local >= total {
slice
.get(payload_start..payload_start + total)
.ok_or(Error::TruncatedCell)?
.to_vec()
} else {
let head = slice
.get(payload_start..payload_start + local)
.ok_or(Error::TruncatedCell)?;
let first_overflow = be_u32(slice, payload_start + local);
let mut buf = Vec::with_capacity(total);
buf.extend_from_slice(head);
self.read_overflow_chain(first_overflow, total - local, &mut buf)?;
buf
};
let values = decode_record(&payload, column_count, rowid, self.header.text_encoding)?;
Ok(Row { rowid, values })
}
fn read_overflow_chain(
&self,
first: u32,
mut remaining: usize,
buf: &mut Vec<u8>,
) -> Result<(), Error> {
let usable = self.header.usable_size() as usize;
let per_page = usable.saturating_sub(4);
if per_page == 0 {
return Err(Error::MalformedOverflow);
}
let total_pages = self.file_page_count();
let cap = total_pages as usize + 1;
let mut page = first;
let mut visited = 0usize;
while remaining > 0 {
if page == 0 || page > total_pages {
return Err(Error::MalformedOverflow);
}
visited += 1;
if visited > cap {
return Err(Error::MalformedOverflow);
}
let slice = self.page_slice(page)?;
let next = be_u32(slice, 0);
let take = remaining.min(per_page);
let chunk = slice.get(4..4 + take).ok_or(Error::TruncatedCell)?;
buf.extend_from_slice(chunk);
remaining -= take;
page = next;
}
Ok(())
}
}
fn local_payload_len(total: usize, usable: usize) -> usize {
let max_local = usable - 35; if total <= max_local {
return total;
}
let min_local = (usable - 12) * 32 / 255 - 23; let k = min_local + (total - min_local) % (usable - 4);
if k <= max_local {
k
} else {
min_local
}
}
impl WalOverlay {
fn parse(wal: &[u8], page_size: u32) -> Result<Option<Self>, Error> {
use forensicnomicon::sqlite::{SQLITE_WAL_FRAME_HEADER_SIZE, SQLITE_WAL_HEADER_SIZE};
let Some(hdr) = wal.get(..SQLITE_WAL_HEADER_SIZE) else {
return Ok(None);
};
let magic = be_u32(hdr, 0);
if magic != WAL_MAGIC_BE && magic != WAL_MAGIC_LE {
return Ok(None);
}
let wal_page_size = be_u32(hdr, 8);
if wal_page_size != page_size {
return Ok(None);
}
let salt1 = be_u32(hdr, 16);
let salt2 = be_u32(hdr, 20);
let ps = page_size as usize;
let frame_stride = SQLITE_WAL_FRAME_HEADER_SIZE + ps;
let mut committed: std::collections::BTreeMap<u32, Vec<u8>> =
std::collections::BTreeMap::new();
let mut pending: std::collections::BTreeMap<u32, Vec<u8>> =
std::collections::BTreeMap::new();
let mut frames: Vec<WalFramePage> = Vec::new();
let mut pending_frames: Vec<WalFramePage> = Vec::new();
let mut off = SQLITE_WAL_HEADER_SIZE;
let max_frames = wal.len() / frame_stride + 1;
let mut frame_no = 0usize;
while let Some(frame) = wal.get(off..off + frame_stride) {
frame_no += 1;
if frame_no > max_frames {
break; }
let page_no = be_u32(frame, 0);
let db_size = be_u32(frame, 4);
let fsalt1 = be_u32(frame, 8);
let fsalt2 = be_u32(frame, 12);
if fsalt1 != salt1 || fsalt2 != salt2 {
break;
}
if page_no == 0 {
break; }
let data = frame
.get(SQLITE_WAL_FRAME_HEADER_SIZE..)
.ok_or(Error::TruncatedCell)?;
pending.insert(page_no, data.to_vec());
let is_commit = db_size != 0;
pending_frames.push(WalFramePage {
frame_index: frame_no - 1, page_no,
salt1,
salt2,
is_commit,
page: data.to_vec(),
});
if is_commit {
for (p, d) in std::mem::take(&mut pending) {
committed.insert(p, d);
}
frames.append(&mut pending_frames);
}
off += frame_stride;
}
if committed.is_empty() {
Ok(None)
} else {
Ok(Some(WalOverlay {
pages: committed,
frames,
raw: wal.to_vec(),
}))
}
}
}
const MAX_WAL_SEGMENTS: usize = 1024;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct WalSegmentId(pub usize);
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WalSegment {
pub id: WalSegmentId,
pub salt1: u32,
pub salt2: u32,
pub page_size: u32,
pub frame_count: usize,
pub checkpoint_seq: u32,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CommitId {
pub segment: WalSegmentId,
pub commit_frame_index: usize,
pub db_size_after_commit: u32,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct WalLsn {
pub salt1: u32,
pub salt2: u32,
pub frame_index: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CohortTopology {
LinearSegment,
Disconnected,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommittedPageVersion {
pub page_no: u32,
pub bytes: Vec<u8>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommitSnapshot {
id: CommitId,
salt1: u32,
salt2: u32,
overlaid: std::collections::BTreeMap<u32, Vec<u8>>,
}
impl CommitSnapshot {
#[must_use]
pub fn id(&self) -> CommitId {
self.id
}
#[must_use]
pub fn db_size_after_commit(&self) -> u32 {
self.id.db_size_after_commit
}
#[must_use]
pub fn lsn(&self) -> WalLsn {
WalLsn {
salt1: self.salt1,
salt2: self.salt2,
frame_index: self.id.commit_frame_index,
}
}
#[must_use]
pub fn page_numbers(&self) -> Vec<u32> {
self.overlaid.keys().copied().collect()
}
#[must_use]
pub fn page_version(&self, page_no: u32) -> Option<CommittedPageVersion> {
let bytes = self.overlaid.get(&page_no)?.clone();
Some(CommittedPageVersion { page_no, bytes })
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WalDiff {
changed: Vec<u32>,
}
impl WalDiff {
#[must_use]
pub fn changed_pages(&self) -> &[u32] {
&self.changed
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WalResidue {
pub segment: WalSegmentId,
pub first_frame_index: usize,
pub frame_count: usize,
pub reason: ResidueReason,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ResidueReason {
BeyondLastCommit,
SaltReset,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum MaterializationSafety {
PhysicalValidated,
CommitValidated,
ReplaySafe,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WalValidationError {
BadMagic,
PageSizeMismatch { db: u32, wal: u32 },
Header(Error),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WalTimeline {
page_size: u32,
base_pages: std::collections::BTreeMap<u32, Vec<u8>>,
segments: Vec<WalSegment>,
snapshots: Vec<CommitSnapshot>,
residue: Vec<WalResidue>,
safety: MaterializationSafety,
}
impl WalTimeline {
fn parse(bytes: &[u8], wal: &[u8], page_size: u32) -> Result<Self, WalValidationError> {
use forensicnomicon::sqlite::{SQLITE_WAL_FRAME_HEADER_SIZE, SQLITE_WAL_HEADER_SIZE};
let hdr = wal
.get(..SQLITE_WAL_HEADER_SIZE)
.ok_or(WalValidationError::BadMagic)?;
let magic = be_u32(hdr, 0);
if magic != WAL_MAGIC_BE && magic != WAL_MAGIC_LE {
return Err(WalValidationError::BadMagic);
}
let wal_page_size = be_u32(hdr, 8);
if wal_page_size != page_size {
return Err(WalValidationError::PageSizeMismatch {
db: page_size,
wal: wal_page_size,
});
}
let checkpoint_seq = be_u32(hdr, 12);
let mut salt1 = be_u32(hdr, 16);
let mut salt2 = be_u32(hdr, 20);
let ps = page_size as usize;
let frame_stride = SQLITE_WAL_FRAME_HEADER_SIZE + ps;
let mut base_pages: std::collections::BTreeMap<u32, Vec<u8>> =
std::collections::BTreeMap::new();
for (idx, page) in bytes
.chunks_exact(ps)
.take(u32::MAX as usize - 1)
.enumerate()
{
let pno = idx as u32 + 1; base_pages.insert(pno, page.to_vec());
}
let mut segments: Vec<WalSegment> = Vec::new();
let mut snapshots: Vec<CommitSnapshot> = Vec::new();
let mut residue: Vec<WalResidue> = Vec::new();
let mut seg_ordinal = 0usize;
let mut seg_frame_count = 0usize;
let mut committed_pages: std::collections::BTreeMap<u32, Vec<u8>> = base_pages.clone();
let mut pending: std::collections::BTreeMap<u32, Vec<u8>> =
std::collections::BTreeMap::new();
let mut last_commit_global_frame: Option<usize> = None;
let mut uncommitted_tail_start: Option<usize> = None;
let mut off = SQLITE_WAL_HEADER_SIZE;
let max_frames = wal.len() / frame_stride + 1;
let mut frame_no = 0usize;
while let Some(frame) = wal.get(off..off + frame_stride) {
if frame_no >= max_frames {
break; }
let page_no = be_u32(frame, 0);
let db_size = be_u32(frame, 4);
let fsalt1 = be_u32(frame, 8);
let fsalt2 = be_u32(frame, 12);
if fsalt1 != salt1 || fsalt2 != salt2 {
if segments.len() >= MAX_WAL_SEGMENTS {
break; }
Self::close_segment(
&mut segments,
&mut residue,
WalSegmentId(seg_ordinal),
salt1,
salt2,
page_size,
checkpoint_seq,
seg_frame_count,
uncommitted_tail_start,
);
seg_ordinal += 1;
salt1 = fsalt1;
salt2 = fsalt2;
seg_frame_count = 0;
pending.clear();
uncommitted_tail_start = None;
}
if page_no == 0 {
break; }
let data = match frame.get(SQLITE_WAL_FRAME_HEADER_SIZE..) {
Some(d) => d.to_vec(),
None => break, };
let frame_index_in_seg = seg_frame_count;
seg_frame_count += 1;
pending.insert(page_no, data);
let is_commit = db_size != 0;
if is_commit {
for (p, d) in std::mem::take(&mut pending) {
committed_pages.insert(p, d);
}
committed_pages.retain(|&p, _| p <= db_size);
let id = CommitId {
segment: WalSegmentId(seg_ordinal),
commit_frame_index: frame_index_in_seg,
db_size_after_commit: db_size,
};
snapshots.push(CommitSnapshot {
id,
overlaid: committed_pages.clone(),
salt1,
salt2,
});
last_commit_global_frame = Some(frame_no);
uncommitted_tail_start = None;
} else if uncommitted_tail_start.is_none() {
uncommitted_tail_start = Some(frame_index_in_seg);
}
frame_no += 1;
off += frame_stride;
}
Self::close_segment(
&mut segments,
&mut residue,
WalSegmentId(seg_ordinal),
salt1,
salt2,
page_size,
checkpoint_seq,
seg_frame_count,
uncommitted_tail_start,
);
let safety = if snapshots.is_empty() {
MaterializationSafety::PhysicalValidated
} else if last_commit_global_frame.is_some() {
MaterializationSafety::ReplaySafe
} else {
MaterializationSafety::CommitValidated };
Ok(Self {
page_size,
base_pages,
segments,
snapshots,
residue,
safety,
})
}
#[allow(clippy::too_many_arguments)]
fn close_segment(
segments: &mut Vec<WalSegment>,
residue: &mut Vec<WalResidue>,
id: WalSegmentId,
salt1: u32,
salt2: u32,
page_size: u32,
checkpoint_seq: u32,
frame_count: usize,
uncommitted_tail_start: Option<usize>,
) {
if frame_count == 0 {
return;
}
segments.push(WalSegment {
id,
salt1,
salt2,
page_size,
frame_count,
checkpoint_seq,
});
if let Some(start) = uncommitted_tail_start {
residue.push(WalResidue {
segment: id,
first_frame_index: start,
frame_count: frame_count - start,
reason: ResidueReason::BeyondLastCommit,
});
}
}
#[must_use]
pub fn segments(&self) -> &[WalSegment] {
&self.segments
}
#[must_use]
pub fn commit_snapshots(&self) -> &[CommitSnapshot] {
&self.snapshots
}
#[must_use]
pub fn residue(&self) -> &[WalResidue] {
&self.residue
}
#[must_use]
pub fn snapshot_at(&self, id: CommitId) -> Option<&CommitSnapshot> {
self.snapshots.iter().find(|s| s.id == id)
}
#[must_use]
pub fn safety(&self) -> MaterializationSafety {
self.safety
}
#[must_use]
pub fn topology(&self) -> CohortTopology {
if self.segments.len() <= 1 {
CohortTopology::LinearSegment
} else {
CohortTopology::Disconnected
}
}
#[must_use]
pub fn checksums_are_tamper_evident(&self) -> bool {
false
}
#[must_use]
pub fn diff_base_to_last_commit(&self) -> Option<WalDiff> {
let last = self.snapshots.last()?;
let mut changed = Vec::new();
let mut pages: std::collections::BTreeSet<u32> = std::collections::BTreeSet::new();
pages.extend(self.base_pages.keys().copied());
pages.extend(last.overlaid.keys().copied());
for p in pages {
let base = self.base_pages.get(&p);
let now = last.overlaid.get(&p);
if base != now {
changed.push(p);
}
}
Some(WalDiff { changed })
}
#[must_use]
pub fn page_size(&self) -> u32 {
self.page_size
}
#[must_use]
pub fn to_temporal_cohort(
&self,
artifact: forensicnomicon::history::identity::ArtifactRef,
) -> forensicnomicon::history::cohort::TemporalCohort<CommitId> {
use forensicnomicon::history::cohort::{TemporalCohort, TemporalState};
use forensicnomicon::history::epoch::{CohortTopology, EpochTag, LsnKind};
use forensicnomicon::history::identity::IdentityDiscipline;
use forensicnomicon::history::profiles;
let profile = profiles::SourceTemporalProfile::sqlite_wal();
let mut commit_seq_in_segment: std::collections::HashMap<WalSegmentId, u32> =
std::collections::HashMap::new();
let states = self
.snapshots
.iter()
.map(|snap| {
let id = snap.id();
let lsn = snap.lsn();
let seq = commit_seq_in_segment.entry(id.segment).or_insert(0);
let commit_seq = *seq;
*seq += 1;
let mut tag = [0u8; 32];
tag[0..4].copy_from_slice(&lsn.salt1.to_be_bytes());
tag[4..8].copy_from_slice(&lsn.salt2.to_be_bytes());
tag[8..12].copy_from_slice(&(id.commit_frame_index as u32).to_be_bytes());
tag[12..16].copy_from_slice(&id.db_size_after_commit.to_be_bytes());
TemporalState {
epoch: EpochTag::from_bytes(tag),
ordering_key: Some(LsnKind::SqliteWalFrame {
salt1: lsn.salt1,
salt2: lsn.salt2,
frame_seq: lsn.frame_index as u32,
commit_seq,
}),
wall_time: None,
clock: profile.clock.clone(),
safety: profile.safety.clone(),
handle: id,
}
})
.collect();
TemporalCohort {
artifact,
discipline: IdentityDiscipline::PathStable,
topology: CohortTopology::SubJournalCommits,
states,
}
}
}
fn is_distinctive(value: &Value) -> bool {
match value {
Value::Text(t) => t.len() >= 4 && !t.contains('\u{FFFD}'),
Value::Real(_) => true,
Value::Null | Value::Integer(_) | Value::Blob(_) => false,
}
}
fn serial_body_len(serial: i64) -> Option<usize> {
match serial {
0 | 8 | 9 | 10 | 11 => Some(0),
1 => Some(1),
2 => Some(2),
3 => Some(3),
4 => Some(4),
5 => Some(6),
6 | 7 => Some(8),
n if n >= 12 => Some(((n - 12) / 2) as usize),
_ => None, }
}
fn live_cell_len(buf: &[u8], off: usize, usable: usize) -> Option<usize> {
let (payload_len, n1) = read_varint(buf, off).ok()?;
let (_rowid, n2) = read_varint(buf, off + n1).ok()?;
let total = usize::try_from(payload_len).ok()?;
let local = local_payload_len(total, usable);
let on_page = if local >= total {
n1 + n2 + total
} else {
n1 + n2 + local + 4 };
Some(on_page)
}
fn live_cell_rowid(buf: &[u8], off: usize) -> Option<i64> {
let (_payload_len, n1) = read_varint(buf, off).ok()?;
let (rowid, _) = read_varint(buf, off + n1).ok()?;
Some(rowid)
}
fn free_regions(live: &[(usize, usize)], lo: usize, hi: usize) -> Vec<(usize, usize)> {
let mut regions = Vec::new();
let mut cursor = lo;
for &(s, e) in live {
let s = s.clamp(lo, hi);
let e = e.clamp(lo, hi);
if s > cursor {
regions.push((cursor, s));
}
if e > cursor {
cursor = e;
}
}
if cursor < hi {
regions.push((cursor, hi));
}
regions
}
fn reconstruct_freeblock_inner(
page_bytes: &[u8],
enc: TextEncoding,
) -> (Vec<CarvedCell>, Vec<CellFragment>) {
let mut cells = Vec::new();
let mut frags = Vec::new();
let hdr_off = if page_bytes.starts_with(SQLITE_MAGIC) {
SQLITE_HEADER_SIZE
} else {
0
};
let Some(&page_type) = page_bytes.get(hdr_off) else {
return (cells, frags);
};
if page_type != 0x0d {
return (cells, frags); }
let Some(template) = freeblock_template(page_bytes, hdr_off, enc) else {
return (cells, frags);
};
let first_freeblock = be_u16(page_bytes, hdr_off + 1) as usize;
let mut fb = first_freeblock;
let mut walked = 0usize;
let mut visited = std::collections::BTreeSet::new();
while fb != 0 && walked < MAX_FREEBLOCKS_PER_PAGE {
walked += 1;
if !visited.insert(fb) {
break; }
let next = be_u16(page_bytes, fb) as usize;
let size = be_u16(page_bytes, fb + 2) as usize;
let Some(fb_end) = fb.checked_add(size) else {
break; };
if size >= 4 && fb_end <= page_bytes.len() {
template.reconstruct_span_tiered(page_bytes, fb, fb_end, false, &mut cells, &mut frags);
}
fb = next;
}
let cell_count = be_u16(page_bytes, hdr_off + 3) as usize;
let cptr_end = hdr_off + 8 + cell_count * 2;
let cca = be_u16(page_bytes, hdr_off + 5) as usize;
if cca > cptr_end && cca <= page_bytes.len() {
for anchor_off in cptr_end..cca {
let Some(anchor) =
try_carve_cell_at(page_bytes, anchor_off, Some(template.column_count), enc)
else {
continue;
};
let has_text = anchor
.values
.iter()
.any(|v| matches!(v, Value::Text(t) if !t.is_empty() && !t.contains('\u{FFFD}')));
if !has_text {
continue;
}
let tail_start = anchor.offset + anchor.byte_len;
template
.reconstruct_span_tiered(page_bytes, tail_start, cca, true, &mut cells, &mut frags);
break; }
}
(cells, frags)
}
fn freeblock_template(page_bytes: &[u8], hdr_off: usize, enc: TextEncoding) -> Option<FreeblockTemplate> {
let cell_count = be_u16(page_bytes, hdr_off + 3) as usize;
let cell_ptr_array = hdr_off + 8;
for i in 0..cell_count {
let cell_off = be_u16(page_bytes, cell_ptr_array + i * 2) as usize;
if cell_off == 0 || cell_off >= page_bytes.len() {
continue;
}
let Ok((_payload_len, n1)) = read_varint(page_bytes, cell_off) else {
continue; };
let Ok((_rowid, n2)) = read_varint(page_bytes, cell_off + n1) else {
continue; };
let prefix_len = n1 + n2;
if prefix_len > 4 {
continue; }
let payload_start = cell_off + n1 + n2;
let Ok((header_len, hn)) = read_varint(page_bytes, payload_start) else {
continue; };
let header_len = usize::try_from(header_len).ok()?;
if header_len < hn {
continue; }
let mut serials = Vec::new();
let mut hpos = hn;
let mut ok = true;
while hpos < header_len {
let Ok((s, used)) = read_varint(page_bytes, payload_start + hpos) else {
ok = false; break; };
serials.push((s, hpos, used));
hpos += used;
}
if !ok || hpos != header_len || serials.len() < MIN_INFERRED_COLUMNS {
continue; }
return FreeblockTemplate::build(prefix_len, header_len, hn, &serials, enc);
}
None
}
struct FreeblockTemplate {
column_count: usize,
known_lead_serials: Vec<i64>,
surviving_serials_off: usize,
text_encoding: TextEncoding,
}
impl FreeblockTemplate {
fn build(
prefix_len: usize,
_header_len: usize,
_hn: usize,
serials: &[(i64, usize, usize)],
enc: TextEncoding,
) -> Option<FreeblockTemplate> {
let clobbered_header_bytes = 4usize.checked_sub(prefix_len)?;
let mut known_lead = Vec::new();
let mut surviving_serials_off = None;
for &(serial, hpos, _used) in serials {
if hpos >= clobbered_header_bytes {
surviving_serials_off = Some(prefix_len + hpos);
break;
}
known_lead.push(serial);
}
let surviving_serials_off = surviving_serials_off?;
if known_lead.is_empty() || known_lead.len() >= serials.len() {
return None;
}
Some(FreeblockTemplate {
column_count: serials.len(),
known_lead_serials: known_lead,
surviving_serials_off,
text_encoding: enc,
})
}
fn reconstruct_span_tiered(
&self,
page: &[u8],
lo: usize,
hi: usize,
enforce_follower_mark: bool,
cells: &mut Vec<CarvedCell>,
frags: &mut Vec<CellFragment>,
) {
let mut cell_start = lo;
let mut built = 0usize;
while cell_start < hi && built < MAX_FREEBLOCKS_PER_PAGE {
if enforce_follower_mark && be_u16(page, cell_start) != 0 {
break; }
let Some((cell, record_end)) = self.reconstruct_one(page, cell_start, hi) else {
if let Some(frag) = self.salvage_fragment(page, cell_start, hi) {
frags.push(frag);
}
break;
};
cells.push(cell);
built += 1;
cell_start = record_end;
}
}
fn salvage_fragment(
&self,
page: &[u8],
cell_start: usize,
span_end: usize,
) -> Option<CellFragment> {
let surviving_count = self.column_count - self.known_lead_serials.len();
let tail_start = cell_start.checked_add(self.surviving_serials_off)?;
let mut serials = self.known_lead_serials.clone();
let mut pos = tail_start;
for _ in 0..surviving_count {
let Ok((s, used)) = read_varint(page, pos) else {
break; };
if serial_body_len(s).is_none() {
break; }
let Some(next) = pos.checked_add(used) else {
break; };
if next > span_end {
break; }
serials.push(s);
pos = next;
}
let body_start = pos;
let mut surviving: Vec<(usize, Value)> = Vec::new();
let mut bpos = body_start;
for (idx, &s) in serials.iter().enumerate() {
let Some(blen) = serial_body_len(s) else {
break; };
let Some(body_end) = bpos.checked_add(blen) else {
break; };
if body_end > span_end {
break; }
let Some(body) = page.get(bpos..body_end) else {
break; };
let Ok((val, _)) = decode_value(body, 0, s, self.text_encoding) else {
break; };
surviving.push((idx, val));
bpos = body_end;
}
if !surviving.iter().any(|(_, v)| is_distinctive(v)) {
return None;
}
let last_body_end = bpos;
Some(CellFragment {
offset: cell_start,
byte_len: last_body_end.saturating_sub(cell_start),
missing: self.column_count - surviving.len(),
surviving,
confidence: FRAGMENT_CONFIDENCE,
})
}
fn reconstruct_one(
&self,
page: &[u8],
cell_start: usize,
span_end: usize,
) -> Option<(CarvedCell, usize)> {
let surviving_count = self.column_count - self.known_lead_serials.len();
let tail_start = cell_start.checked_add(self.surviving_serials_off)?;
let mut serials = self.known_lead_serials.clone();
let mut pos = tail_start;
for _ in 0..surviving_count {
let (s, used) = read_varint(page, pos).ok()?;
serial_body_len(s)?;
serials.push(s);
pos = pos.checked_add(used)?;
if pos > span_end {
return None;
}
}
let mut body_len = 0usize;
for &s in &serials {
body_len = body_len.checked_add(serial_body_len(s)?)?;
}
let body_start = pos;
let record_end = body_start.checked_add(body_len)?;
if record_end > span_end {
return None;
}
let body = page.get(body_start..record_end)?;
let values = decode_synthetic_record(&serials, body, self.text_encoding)?;
if values.len() != self.column_count {
return None; }
Some((
CarvedCell {
offset: cell_start,
byte_len: record_end - cell_start,
rowid: 0, values,
confidence: FREEBLOCK_RECONSTRUCT_CONFIDENCE,
},
record_end,
))
}
fn reconstruct_spilled(
&self,
db: &Database,
page: &[u8],
cell_start: usize,
usable: usize,
freed_leaves: &std::collections::BTreeSet<u32>,
) -> Option<(CarvedCell, Vec<u32>)> {
const CLOBBER: usize = 4;
let serials_start = cell_start.checked_add(CLOBBER)?;
let mut serials = Vec::with_capacity(self.column_count);
let mut pos = serials_start;
for _ in 0..self.column_count {
let (s, used) = read_varint(page, pos).ok()?;
serial_body_len(s)?;
serials.push(s);
pos = pos.checked_add(used)?;
}
let mut serial_bytes_len = 0usize;
for &s in &serials {
serial_bytes_len += varint_len(s);
}
let mut header_len = serial_bytes_len + 1;
while varint_len(header_len as i64) + serial_bytes_len != header_len {
header_len += 1;
}
if pos.checked_sub(serials_start)? != serial_bytes_len {
return None; }
let mut body_len = 0usize;
for &s in &serials {
body_len = body_len.checked_add(serial_body_len(s)?)?;
}
let payload_len = header_len.checked_add(body_len)?;
if payload_len <= usable.checked_sub(35)? {
return None;
}
let local_len = local_payload_len(payload_len, usable);
let body_start = pos;
let local_body = local_len.checked_sub(header_len)?;
let local_body_end = body_start.checked_add(local_body)?;
let ptr_off = local_body_end;
let ptr_slice = page.get(ptr_off..ptr_off + 4)?;
let first_overflow =
u32::from_be_bytes([ptr_slice[0], ptr_slice[1], ptr_slice[2], ptr_slice[3]]);
let local_body_bytes = page.get(body_start..local_body_end)?;
let remaining = payload_len - local_len;
let (chain_content, chain) = db
.read_freed_overflow_chain(first_overflow, remaining, usable, freed_leaves)
.ok()?;
let mut header = enc_varint_into(header_len);
for &s in &serials {
header.extend(enc_varint_into(usize::try_from(s).ok()?));
}
if header.len() != header_len {
return None; }
let mut payload = Vec::with_capacity(payload_len);
payload.extend_from_slice(&header);
payload.extend_from_slice(local_body_bytes);
payload.extend_from_slice(&chain_content);
if payload.len() != payload_len {
return None; }
let values = decode_record(&payload, self.column_count, 0, db.header.text_encoding).ok()?;
if values.len() != self.column_count {
return None; }
let any_replacement = values.iter().any(|v| match v {
Value::Text(t) => t.contains('\u{FFFD}'),
_ => false,
});
if any_replacement {
return None;
}
if !values.iter().any(is_distinctive) {
return None;
}
Some((
CarvedCell {
offset: cell_start,
byte_len: ptr_off + 4 - cell_start,
rowid: 0,
values,
confidence: FREEBLOCK_RECONSTRUCT_CONFIDENCE * OVERFLOW_CHAIN_CONFIDENCE_FACTOR,
},
chain,
))
}
}
fn decode_synthetic_record(serials: &[i64], body: &[u8], enc: TextEncoding) -> Option<Vec<Value>> {
let mut values = Vec::with_capacity(serials.len());
let mut bpos = 0usize;
for &serial in serials {
let (val, size) = decode_value(body, bpos, serial, enc).ok()?;
values.push(val);
bpos = bpos.checked_add(size)?;
}
Some(values)
}
fn try_carve_cell_at(
buf: &[u8],
off: usize,
expected_columns: Option<usize>,
enc: TextEncoding,
) -> Option<CarvedCell> {
let (payload_len, n1) = read_varint(buf, off).ok()?;
let payload_len = usize::try_from(payload_len).ok()?;
if payload_len == 0 {
return None;
}
let (rowid, n2) = read_varint(buf, off + n1).ok()?;
if rowid <= 0 {
return None;
}
let payload_start = off + n1 + n2;
let payload = buf.get(payload_start..payload_start + payload_len)?;
let (header_len, hn) = read_varint(payload, 0).ok()?;
let header_len = usize::try_from(header_len).ok()?;
if header_len > payload.len() || header_len < hn {
return None;
}
let cap = expected_columns.unwrap_or(0);
let mut serials = Vec::with_capacity(cap);
let mut hpos = hn;
while hpos < header_len {
let (s, used) = read_varint(payload, hpos).ok()?;
serials.push(s);
hpos += used;
}
if hpos != header_len {
return None;
}
match expected_columns {
Some(n) if serials.len() != n => return None,
None if serials.len() < MIN_INFERRED_COLUMNS => return None,
_ => {}
}
let column_count = serials.len();
let mut body_len = 0usize;
for &s in &serials {
body_len += serial_body_len(s)?;
}
if header_len + body_len != payload_len {
return None;
}
let values = decode_record(payload, column_count, rowid, enc).ok()?;
if values.len() != column_count {
return None; }
let has_real_text = values.iter().any(|v| match v {
Value::Text(t) => !t.is_empty() && !t.contains('\u{FFFD}'),
_ => false,
});
let confidence = if has_real_text { 0.9 } else { 0.6 };
Some(CarvedCell {
offset: off,
byte_len: (payload_start + payload_len) - off,
rowid,
values,
confidence,
})
}
fn try_carve_spilled_cell_at(
buf: &[u8],
off: usize,
usable: usize,
expected_columns: Option<usize>,
) -> Option<SpilledCell> {
let (payload_len, n1) = read_varint(buf, off).ok()?;
let payload_len = usize::try_from(payload_len).ok()?;
if payload_len <= usable.checked_sub(35)? {
return None;
}
let (rowid, n2) = read_varint(buf, off + n1).ok()?;
if rowid <= 0 {
return None;
}
let payload_start = off + n1 + n2;
let local_len = local_payload_len(payload_len, usable);
let prefix = buf.get(payload_start..payload_start + local_len + 4)?;
let (header_len, hn) = read_varint(prefix, 0).ok()?;
let header_len = usize::try_from(header_len).ok()?;
if header_len > local_len || header_len < hn {
return None;
}
let mut serials = Vec::new();
let mut hpos = hn;
while hpos < header_len {
let (s, used) = read_varint(prefix, hpos).ok()?;
serials.push(s);
hpos += used;
}
if hpos != header_len {
return None;
}
match expected_columns {
Some(n) if serials.len() != n => return None,
None if serials.len() < MIN_INFERRED_COLUMNS => return None,
_ => {}
}
let mut body_len = 0usize;
for &s in &serials {
body_len += serial_body_len(s)?;
}
if header_len + body_len != payload_len {
return None;
}
let first_overflow = be_u32(prefix, local_len);
Some(SpilledCell {
offset: off,
byte_len: n1 + n2 + local_len + 4,
payload_len,
rowid,
serials,
local_len,
local_payload_off: payload_start,
first_overflow,
})
}
fn salvage_local_prefix(region: &[u8], sc: &SpilledCell, enc: TextEncoding) -> Option<CellFragment> {
let local_end = sc.local_payload_off.checked_add(sc.local_len)?;
let (header_len, _hn) = read_varint(region, sc.local_payload_off).ok()?;
let header_len = usize::try_from(header_len).ok()?;
let mut bpos = sc.local_payload_off.checked_add(header_len)?;
let mut surviving: Vec<(usize, Value)> = Vec::new();
for (idx, &serial) in sc.serials.iter().enumerate() {
let Some(blen) = serial_body_len(serial) else {
break; };
let Some(body_end) = bpos.checked_add(blen) else {
break; };
if body_end > local_end {
break; }
let Some(body) = region.get(bpos..body_end) else {
break; };
let Ok((val, _)) = decode_value(body, 0, serial, enc) else {
break; };
surviving.push((idx, val));
bpos = body_end;
}
if !surviving.iter().any(|(_, v)| is_distinctive(v)) {
return None;
}
Some(CellFragment {
offset: sc.offset,
byte_len: bpos.saturating_sub(sc.local_payload_off),
missing: sc.serials.len() - surviving.len(),
surviving,
confidence: FRAGMENT_CONFIDENCE,
})
}
fn parse_header(bytes: &[u8]) -> Result<Header, Error> {
let head = bytes.get(..SQLITE_HEADER_SIZE).ok_or(Error::TooShort)?;
if !head.starts_with(SQLITE_MAGIC) {
return Err(Error::BadMagic);
}
let raw = be_u16(head, SQLITE_PAGE_SIZE_OFFSET);
let page_size: u32 = if raw == 1 { 65536 } else { u32::from(raw) };
let valid = (512..=65536).contains(&page_size) && page_size.is_power_of_two();
if !valid {
return Err(Error::BadPageSize(page_size));
}
let reserved = *head.get(RESERVED_SPACE_OFFSET).ok_or(Error::TooShort)?;
let text_encoding = match be_u32(head, TEXT_ENCODING_OFFSET) {
2 => TextEncoding::Utf16Le,
3 => TextEncoding::Utf16Be,
_ => TextEncoding::Utf8,
};
Ok(Header {
page_size,
reserved,
text_encoding,
})
}
fn decode_record(
payload: &[u8],
_column_count: usize,
rowid: i64,
enc: TextEncoding,
) -> Result<Vec<Value>, Error> {
let (header_len, n) = read_varint(payload, 0)?;
let header_len = header_len as usize;
if header_len > payload.len() {
return Err(Error::TruncatedCell);
}
let mut serials = Vec::new();
let mut hpos = n;
while hpos < header_len {
let (s, used) = read_varint(payload, hpos)?;
serials.push(s);
hpos += used;
}
let mut values = Vec::with_capacity(serials.len());
let mut bpos = header_len;
for (idx, &serial) in serials.iter().enumerate() {
let (val, size) = decode_value(payload, bpos, serial, enc)?;
let val = if idx == 0 && serial == 0 {
Value::Integer(rowid)
} else {
val
};
values.push(val);
bpos += size;
}
Ok(values)
}
fn decode_value(
buf: &[u8],
off: usize,
serial: i64,
enc: TextEncoding,
) -> Result<(Value, usize), Error> {
Ok(match serial {
0 | 10 | 11 => (Value::Null, 0),
1 => (
Value::Integer(i64::from(read_be_u64(buf, off, 1)? as i8)),
1,
),
2 => (
Value::Integer(i64::from(read_be_u64(buf, off, 2)? as i16)),
2,
),
3 => (Value::Integer(sign_extend(read_be_u64(buf, off, 3)?, 3)), 3),
4 => (
Value::Integer(i64::from(read_be_u64(buf, off, 4)? as i32)),
4,
),
5 => (Value::Integer(sign_extend(read_be_u64(buf, off, 6)?, 6)), 6),
6 => (Value::Integer(read_be_u64(buf, off, 8)? as i64), 8),
7 => {
let bits = read_be_u64(buf, off, 8)?;
(Value::Real(f64::from_bits(bits)), 8)
}
8 => (Value::Integer(0), 0),
9 => (Value::Integer(1), 0),
n if n >= 12 && n % 2 == 0 => {
let len = ((n - 12) / 2) as usize;
let bytes = buf.get(off..off + len).ok_or(Error::TruncatedCell)?;
(Value::Blob(bytes.to_vec()), len)
}
n => {
let len = ((n - 13) / 2) as usize;
let bytes = buf.get(off..off + len).ok_or(Error::TruncatedCell)?;
(Value::Text(enc.decode(bytes)), len)
}
})
}
fn read_be_u64(buf: &[u8], off: usize, width: usize) -> Result<u64, Error> {
let bytes = buf.get(off..off + width).ok_or(Error::TruncatedCell)?;
let mut acc: u64 = 0;
for &b in bytes {
acc = (acc << 8) | u64::from(b);
}
Ok(acc)
}
fn sign_extend(raw: u64, width: usize) -> i64 {
let bits = width * 8;
let shift = 64 - bits;
((raw as i64) << shift) >> shift
}
fn read_varint(buf: &[u8], off: usize) -> Result<(i64, usize), Error> {
let mut result: u64 = 0;
for i in 0..8 {
let b = *buf.get(off + i).ok_or(Error::TruncatedCell)?;
result = (result << 7) | u64::from(b & 0x7f);
if b & 0x80 == 0 {
return Ok((result as i64, i + 1));
}
}
let b = *buf.get(off + 8).ok_or(Error::TruncatedCell)?;
result = (result << 8) | u64::from(b);
Ok((result as i64, 9))
}
fn be_u16(buf: &[u8], off: usize) -> u16 {
let mut b = [0u8; 2];
if let Some(s) = buf.get(off..off + 2) {
b.copy_from_slice(s);
}
u16::from_be_bytes(b)
}
fn varint_len(value: i64) -> usize {
if value < 0 {
return 1; }
enc_varint_into(value as usize).len()
}
fn enc_varint_into(value: usize) -> Vec<u8> {
if value == 0 {
return vec![0];
}
let mut groups = Vec::new();
let mut n = value as u64;
while n > 0 {
groups.push((n & 0x7f) as u8);
n >>= 7;
}
groups.reverse();
let last = groups.len() - 1;
for (i, g) in groups.iter_mut().enumerate() {
if i != last {
*g |= 0x80;
}
}
groups
}
fn be_u32(buf: &[u8], off: usize) -> u32 {
let mut b = [0u8; 4];
if let Some(s) = buf.get(off..off + 4) {
b.copy_from_slice(s);
}
u32::from_be_bytes(b)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn varint_single_byte() {
assert_eq!(read_varint(&[0x05], 0).unwrap(), (5, 1));
}
#[test]
fn varint_two_bytes() {
assert_eq!(read_varint(&[0x81, 0x00], 0).unwrap(), (128, 2));
}
#[test]
fn varint_truncated_is_err() {
assert_eq!(read_varint(&[0x81], 0), Err(Error::TruncatedCell));
}
#[test]
fn sign_extend_three_byte_negative() {
assert_eq!(sign_extend(0x00FF_FFFF, 3), -1);
}
#[test]
fn decode_value_text_and_blob() {
let (v, n) = decode_value(b"hi", 0, 17, TextEncoding::Utf8).unwrap(); assert_eq!(v, Value::Text("hi".into()));
assert_eq!(n, 2);
let (v, n) = decode_value(&[0xAA, 0xBB], 0, 16, TextEncoding::Utf8).unwrap(); assert_eq!(v, Value::Blob(vec![0xAA, 0xBB]));
assert_eq!(n, 2);
}
#[test]
fn decode_value_int_literals() {
assert_eq!(decode_value(&[], 0, 8, TextEncoding::Utf8).unwrap(), (Value::Integer(0), 0));
assert_eq!(decode_value(&[], 0, 9, TextEncoding::Utf8).unwrap(), (Value::Integer(1), 0));
}
#[test]
fn bad_magic_rejected() {
let mut b = vec![0u8; 100];
b[..16].copy_from_slice(b"NOT SQLITE 3\0\0\0\0");
assert_eq!(parse_header(&b), Err(Error::BadMagic));
}
#[test]
fn too_short_rejected() {
assert_eq!(parse_header(&[0u8; 10]), Err(Error::TooShort));
}
const DELETED_DB: &[u8] = include_bytes!("../../tests/data/deleted_places.db");
const CLEAN_DB: &[u8] = include_bytes!("../../tests/data/places.db");
#[test]
fn free_regions_is_complement_of_live_extents() {
let live = [(10, 20), (30, 40)];
let regions = free_regions(&live, 5, 50);
assert_eq!(regions, vec![(5, 10), (20, 30), (40, 50)]);
assert_eq!(free_regions(&[], 5, 50), vec![(5, 50)]);
assert!(free_regions(&[(0, 100)], 5, 50).is_empty());
}
#[test]
fn live_cell_len_reads_on_page_footprint() {
let buf = [0x03, 0x01, 0xAA, 0xBB, 0xCC];
let usable = 4096;
assert_eq!(live_cell_len(&buf, 0, usable), Some(1 + 1 + 3));
assert_eq!(live_cell_len(&[0x81], 0, usable), None);
}
#[test]
fn carve_free_regions_recovers_in_page_remnant() {
let db = Database::open(DELETED_DB.to_vec()).unwrap();
let page = db.raw_page(8).unwrap();
let carved = db.carve_free_regions(page, 6);
assert!(carved.iter().any(|c| c.rowid == 237));
assert!(carved.iter().all(|c| c.rowid > 200));
assert!(db.carve_free_regions(&[0x05u8; 4096], 6).is_empty());
assert!(db.carve_free_regions(&[], 6).is_empty());
}
#[test]
fn carve_leaf_cells_reads_allocated_cells_and_rejects_non_leaf() {
let db = Database::open(DELETED_DB.to_vec()).unwrap();
let page = db.raw_page(8).unwrap();
let cells = db.carve_leaf_cells(page);
assert!(
cells.iter().any(|c| c.rowid == 181),
"must read the allocated cells of the leaf"
);
let _ = db.carve_leaf_cells(db.raw_page(1).unwrap());
assert!(db.carve_leaf_cells(&[0x05u8; 4096]).is_empty());
assert!(db.carve_leaf_cells(&[]).is_empty());
}
#[test]
fn carve_free_regions_handles_page_one_and_inferred() {
let db = Database::open(DELETED_DB.to_vec()).unwrap();
let page1 = db.raw_page(1).unwrap();
let _ = db.carve_free_regions(page1, 6);
let page8 = db.raw_page(8).unwrap();
let inferred = db.carve_free_regions(page8, 0);
assert!(inferred.iter().any(|c| c.rowid == 237));
}
#[test]
fn live_cell_len_accounts_for_overflow_pointer() {
let usable = 4096usize;
assert_eq!(live_cell_len(&[0x03, 0x01, 0, 0, 0], 0, usable), Some(5));
let mut buf = vec![0xA7, 0x08, 0x01];
buf.extend(std::iter::repeat_n(0u8, 5000));
let total = 5000usize;
let local = local_payload_len(total, usable);
assert!(local < total, "this payload must spill");
assert_eq!(live_cell_len(&buf, 0, usable), Some(2 + 1 + local + 4));
}
#[test]
fn carve_cells_inferred_matches_fixed_count() {
let db = Database::open(DELETED_DB.to_vec()).unwrap();
let page = db.raw_page(10).unwrap();
let fixed = db.carve_cells(page, 6);
let inferred = db.carve_cells_inferred(page);
assert!(!fixed.is_empty());
let fixed_ids: std::collections::BTreeSet<i64> = fixed.iter().map(|c| c.rowid).collect();
let inf_ids: std::collections::BTreeSet<i64> = inferred.iter().map(|c| c.rowid).collect();
assert!(fixed_ids.is_subset(&inf_ids));
}
#[test]
fn has_user_table_distinguishes_live_and_dropped() {
let live = Database::open(CLEAN_DB.to_vec()).unwrap();
assert!(live.has_user_table());
let with_deletions = Database::open(DELETED_DB.to_vec()).unwrap();
assert!(with_deletions.has_user_table());
}
#[test]
fn live_rowids_collects_live_rows_only() {
let db = Database::open(CLEAN_DB.to_vec()).unwrap();
let ids = db.live_rowids();
assert_eq!(ids.len(), 5);
assert!(ids.contains(&1) && ids.contains(&5));
let del = Database::open(DELETED_DB.to_vec()).unwrap();
let live = del.live_rowids();
assert!(live.contains(&1) && live.contains(&200));
assert!(!live.contains(&201) && !live.contains(&400));
}
#[test]
fn live_rows_decodes_current_values() {
let db = Database::open(CLEAN_DB.to_vec()).unwrap();
let rows = db.live_rows();
assert_eq!(rows.len(), 5);
let r1 = rows.get(&1).expect("row 1 present");
assert!(
matches!(r1.get(1), Some(Value::Text(t)) if t.contains("rust-lang")),
"row 1 values must be decoded: {r1:?}"
);
let ids = db.live_rowids();
assert_eq!(
rows.keys().copied().collect::<Vec<_>>(),
ids.into_iter().collect::<Vec<_>>()
);
let del = Database::open(DELETED_DB.to_vec()).unwrap();
let del_rows = del.live_rows();
assert_eq!(del_rows.len(), 200);
let r1 = del_rows.get(&1).expect("live row 1");
assert!(
matches!(r1.get(1), Some(Value::Text(t)) if t.contains("site-1.example")),
"interior-walked live row 1 must decode its url: {r1:?}"
);
}
const NEMETZ_0C_01: &[u8] = include_bytes!("../../tests/data/nemetz/0C/0C-01.db");
#[test]
fn reconstruct_freeblock_records_recovers_clobbered_rows() {
let db = Database::open(NEMETZ_0C_01.to_vec()).unwrap();
let page = db.raw_page(2).unwrap();
let recovered = db.reconstruct_freeblock_records(page);
assert!(recovered.iter().any(|c| c.values
== vec![
Value::Integer(20005),
Value::Integer(3_780_322_152),
Value::Integer(3_909_007_646),
Value::Integer(120_462_986),
Value::Integer(1_290_558_629),
]));
assert!(recovered
.iter()
.all(|c| c.rowid == 0 && c.confidence <= 0.5));
}
const NEMETZ_0D_07: &[u8] = include_bytes!("../../tests/data/nemetz/0D/0D-07.db");
#[test]
fn reconstruct_freeblock_records_walks_coalesced_cells() {
let db = Database::open(NEMETZ_0D_07.to_vec()).unwrap();
let page = db.raw_page(3).unwrap();
let recovered = db.reconstruct_freeblock_records(page);
let has = |name: &str, surname: &str| {
recovered.iter().any(|c| {
matches!(c.values.get(1), Some(Value::Text(t)) if t == name)
&& matches!(c.values.get(2), Some(Value::Text(t)) if t == surname)
})
};
assert!(has("Luca", "Schumacher"), "head cell must be recovered");
assert!(
has("Kurt", "Schubert"),
"second coalesced cell must be recovered"
);
assert!(
has("Georg", "Schulz"),
"third coalesced cell must be recovered"
);
assert!(recovered
.iter()
.all(|c| c.rowid == 0 && c.confidence <= 0.5));
}
fn opened() -> Database {
Database::open(NEMETZ_0C_01.to_vec()).unwrap()
}
#[test]
fn reconstruct_freeblock_records_without_template_is_empty() {
let db = opened();
let mut page = vec![0u8; 256];
page[0] = 0x0d; page[1] = 0x00;
page[2] = 0x40; page[3] = 0x00;
page[4] = 0x01; page[8] = 0x00;
page[9] = 0x00;
page[64] = 0x00;
page[65] = 0x00;
page[66] = 0x00;
page[67] = 0x08;
assert!(db.reconstruct_freeblock_records(&page).is_empty());
}
#[test]
fn reconstruct_freeblock_records_breaks_cyclic_chain() {
let db = opened();
let src = db.raw_page(2).unwrap().to_vec();
let mut page = src.clone();
page[1] = 0x00;
page[2] = 100;
page[100] = 0x00;
page[101] = 100; page[102] = 0xff;
page[103] = 0xff; let _ = db.reconstruct_freeblock_records(&page);
}
#[test]
fn is_distinctive_classifies_every_storage_class() {
assert!(is_distinctive(&Value::Text("Anja".into())));
assert!(is_distinctive(&Value::Text("\u{00e4}\u{00f6}".into()))); assert!(is_distinctive(&Value::Real(3.5)));
assert!(!is_distinctive(&Value::Text("abc".into()))); assert!(!is_distinctive(&Value::Text(String::new())));
assert!(!is_distinctive(&Value::Text("ab\u{fffd}x".into()))); assert!(!is_distinctive(&Value::Integer(20004)));
assert!(!is_distinctive(&Value::Null));
assert!(!is_distinctive(&Value::Blob(vec![1, 2, 3, 4, 5])));
}
fn synth_frag_page(live_off: usize, fb: usize, fb_size: usize, freed: &[u8]) -> Vec<u8> {
let mut page = vec![0u8; 256];
page[0] = 0x0d; page[1] = (fb >> 8) as u8;
page[2] = (fb & 0xff) as u8;
page[3] = 0x00;
page[4] = 0x01; page[5] = (live_off >> 8) as u8;
page[6] = (live_off & 0xff) as u8; page[8] = (live_off >> 8) as u8;
page[9] = (live_off & 0xff) as u8;
let live = [
13u8, 5u8, 0x04, 0x01, 0x15, 0x15, 0x09, b'L', b'i', b'v', b'e', b'R', b'o', b'w', b'!',
];
page[live_off..live_off + live.len()].copy_from_slice(&live);
page[fb..fb + freed.len()].copy_from_slice(freed);
page[fb] = 0x00;
page[fb + 1] = 0x00;
page[fb + 2] = (fb_size >> 8) as u8;
page[fb + 3] = (fb_size & 0xff) as u8;
page
}
#[test]
fn fragment_salvage_truncated_tail() {
let db = opened();
let mut freed = vec![0u8; 16];
freed[4] = 0x15;
freed[5] = 0x15;
freed[6] = 0x07;
freed[7..11].copy_from_slice(b"Anja");
freed[11..15].copy_from_slice(b"Frnk");
let page = synth_frag_page(96, 64, 12, &freed);
let frags = db.reconstruct_freeblock_fragments(&page);
assert_eq!(frags.len(), 1, "exactly one fragment salvaged");
let f = &frags[0];
assert_eq!(f.offset, 64);
assert_eq!(
f.surviving,
vec![(0, Value::Integer(7)), (1, Value::Text("Anja".into()))]
);
assert_eq!(f.missing, 1, "c2 did not decode");
assert!((f.confidence - 0.2).abs() < f32::EPSILON);
let cells = db.reconstruct_freeblock_records(&page);
assert!(cells.iter().all(|c| c.offset != 64));
}
#[test]
fn fragment_salvage_partial_tail() {
let db = opened();
let mut freed = vec![0u8; 16];
freed[4] = 0x15;
freed[5] = 0x15;
freed[6] = 0x07;
freed[7..11].copy_from_slice(b"Lena");
let page = synth_frag_page(96, 64, 11, &freed); let frags = db.reconstruct_freeblock_fragments(&page);
assert_eq!(frags.len(), 1);
assert_eq!(
frags[0].surviving,
vec![(0, Value::Integer(7)), (1, Value::Text("Lena".into()))]
);
}
#[test]
fn fragment_salvage_full_record_yields_no_fragment() {
let db = opened();
let mut freed = vec![0u8; 16];
freed[4] = 0x15;
freed[5] = 0x15;
freed[6] = 0x07;
freed[7..11].copy_from_slice(b"Whol");
freed[11..15].copy_from_slice(b"Erow");
let page = synth_frag_page(96, 64, 15, &freed);
let cells = db.reconstruct_freeblock_records(&page);
assert!(
cells.iter().any(|c| c.offset == 64),
"full record recovered"
);
assert!(
db.reconstruct_freeblock_fragments(&page).is_empty(),
"no fragment when the full record is recoverable"
);
}
#[test]
fn fragment_salvage_integer_only_is_rejected() {
let db = opened();
let mut freed = vec![0u8; 12];
freed[4] = 0x01; freed[5] = 0x01; freed[6] = 0x07;
freed[7] = 0x08;
let page = synth_frag_page(96, 64, 8, &freed); assert!(
db.reconstruct_freeblock_fragments(&page).is_empty(),
"integer-only prefix is not distinctive — no fragment"
);
}
#[test]
fn fragment_salvage_does_not_extend_walk() {
let db = opened();
let mut freed = vec![0u8; 16];
freed[4] = 0x15;
freed[5] = 0x15;
freed[6] = 0x07;
freed[7..11].copy_from_slice(b"Stop");
freed[11..15].copy_from_slice(b"Here");
let page = synth_frag_page(96, 64, 12, &freed);
assert_eq!(db.reconstruct_freeblock_fragments(&page).len(), 1);
}
const NEMETZ_0D_01: &[u8] = include_bytes!("../../tests/data/nemetz/0D/0D-01.db");
#[test]
fn fragment_salvage_recovers_anja_on_0d01() {
let db = Database::open(NEMETZ_0D_01.to_vec()).unwrap();
let page = db.raw_page(2).unwrap();
let frags = db.reconstruct_freeblock_fragments(page);
let f = frags
.iter()
.find(|f| {
f.surviving
.iter()
.any(|(_, v)| matches!(v, Value::Text(t) if t == "Anja"))
})
.expect("0D-01 page 2 must salvage the Anja fragment");
assert!(f
.surviving
.iter()
.any(|(_, v)| matches!(v, Value::Text(t) if t == "Frank")));
assert!((f.confidence - 0.2).abs() < f32::EPSILON);
let cells = db.reconstruct_freeblock_records(page);
assert!(cells.iter().all(|c| !c
.values
.iter()
.any(|v| matches!(v, Value::Text(t) if t == "Anja"))));
}
fn enc_varint(mut n: u64) -> Vec<u8> {
if n == 0 {
return vec![0];
}
let mut groups = Vec::new();
while n > 0 {
groups.push((n & 0x7f) as u8);
n >>= 7;
}
groups.reverse();
let last = groups.len() - 1;
for (i, g) in groups.iter_mut().enumerate() {
if i != last {
*g |= 0x80;
}
}
groups
}
fn synth_spilled_prefix(
rowid: i64,
id: i64,
name: &str,
code_len: usize,
usable: usize,
first_overflow: u32,
) -> (Vec<u8>, usize, usize, Vec<i64>) {
let id_serial = 1i64; let name_serial = 13 + 2 * name.len() as i64; let code_serial = 13 + 2 * code_len as i64; let serials = vec![id_serial, name_serial, code_serial];
let mut serial_bytes = Vec::new();
for &s in &serials {
serial_bytes.extend(enc_varint(s as u64));
}
let mut header_len = serial_bytes.len() + 1;
while enc_varint(header_len as u64).len() + serial_bytes.len() != header_len {
header_len += 1;
}
let mut header = enc_varint(header_len as u64);
header.extend(&serial_bytes);
let body_len = 1 + name.len() + code_len;
let payload_len = header.len() + body_len;
let local = local_payload_len(payload_len, usable);
let mut payload = header.clone();
payload.push(id as u8); payload.extend(name.as_bytes());
payload.extend(std::iter::repeat_n(b'C', code_len));
assert_eq!(payload.len(), payload_len);
let mut cell = enc_varint(payload_len as u64);
cell.extend(enc_varint(rowid as u64));
cell.extend(&payload[..local]);
cell.extend(first_overflow.to_be_bytes());
(cell, payload_len, local, serials)
}
#[test]
fn spilled_recognizer_reads_intact_prefix() {
let usable = 4096usize;
let (cell, p, local, serials) = synth_spilled_prefix(20012, 42, "Ella", 4200, usable, 13);
assert!(p > usable - 35, "this record must spill");
let off = 50usize;
let mut buf = vec![0u8; off];
buf.extend(&cell);
let sc = try_carve_spilled_cell_at(&buf, off, usable, Some(3))
.expect("must recognize the intact-prefix spilled cell");
assert_eq!(sc.payload_len, p);
assert_eq!(sc.local_len, local);
assert_eq!(sc.rowid, 20012);
assert_eq!(sc.first_overflow, 13);
assert_eq!(sc.serials, serials);
assert_eq!(sc.offset, off);
}
#[test]
fn spilled_recognizer_abstains_for_in_page_payload() {
let usable = 4096usize;
let (cell, p, _local, _s) = synth_spilled_prefix(7, 1, "Bob", 10, usable, 9);
assert!(p <= usable - 35, "this record must NOT spill");
assert!(try_carve_spilled_cell_at(&cell, 0, usable, Some(3)).is_none());
}
#[test]
fn spilled_recognizer_abstains_on_truncated_pointer() {
let usable = 4096usize;
let (cell, _p, _local, _s) = synth_spilled_prefix(20012, 42, "Ella", 4200, usable, 13);
let truncated = &cell[..cell.len() - 2];
assert!(try_carve_spilled_cell_at(truncated, 0, usable, Some(3)).is_none());
}
#[test]
fn spilled_recognizer_abstains_on_column_mismatch() {
let usable = 4096usize;
let (cell, _p, _local, _s) = synth_spilled_prefix(20012, 42, "Ella", 4200, usable, 13);
assert!(try_carve_spilled_cell_at(&cell, 0, usable, Some(5)).is_none());
assert!(try_carve_spilled_cell_at(&cell, 0, usable, None).is_some());
}
#[test]
fn spilled_recognizer_abstains_on_nonpositive_rowid() {
let usable = 4096usize;
let (cell, _p, _local, _s) = synth_spilled_prefix(0, 42, "Ella", 4000, usable, 13);
assert!(try_carve_spilled_cell_at(&cell, 0, usable, Some(3)).is_none());
}
fn synth_db(page_size: usize, page_count: usize, trunk: u32, fl_count: u32) -> Vec<u8> {
let mut b = vec![0u8; page_size * page_count];
b[..16].copy_from_slice(SQLITE_MAGIC);
b[16..18].copy_from_slice(&(page_size as u16).to_be_bytes());
b[18] = 1; b[19] = 1; b[20] = 0; b[21] = 64;
b[22] = 32;
b[23] = 32;
b[32..36].copy_from_slice(&trunk.to_be_bytes());
b[36..40].copy_from_slice(&fl_count.to_be_bytes());
b[100] = 0x0d;
b
}
fn write_trunk(b: &mut [u8], page_size: usize, page: u32, next_trunk: u32, leaves: &[u32]) {
let base = (page as usize - 1) * page_size;
b[base..base + 4].copy_from_slice(&next_trunk.to_be_bytes());
b[base + 4..base + 8].copy_from_slice(&(leaves.len() as u32).to_be_bytes());
for (i, &lf) in leaves.iter().enumerate() {
b[base + 8 + i * 4..base + 12 + i * 4].copy_from_slice(&lf.to_be_bytes());
}
}
fn write_overflow(b: &mut [u8], page_size: usize, page: u32, next: u32, content: &[u8]) {
let base = (page as usize - 1) * page_size;
b[base..base + 4].copy_from_slice(&next.to_be_bytes());
b[base + 4..base + 4 + content.len()].copy_from_slice(content);
}
#[test]
fn freelist_split_separates_leaves_and_trunks() {
let ps = 512usize;
let mut b = synth_db(ps, 6, 2, 4);
write_trunk(&mut b, ps, 2, 0, &[3, 4, 5]);
let db = Database::open(b).unwrap();
let (leaves, trunks) = db.freelist_pages_split().unwrap();
assert_eq!(leaves, [3u32, 4, 5].into_iter().collect());
assert_eq!(trunks, [2u32].into_iter().collect());
let all: std::collections::BTreeSet<u32> =
db.freelist_pages().unwrap().into_iter().collect();
assert_eq!(all, [2u32, 3, 4, 5].into_iter().collect());
}
#[test]
fn freed_chain_assembles_single_leaf_page() {
let ps = 512usize;
let usable = ps; let mut b = synth_db(ps, 6, 2, 4);
write_trunk(&mut b, ps, 2, 0, &[3, 4, 5]);
let remaining = 100usize;
let content: Vec<u8> = (0..remaining).map(|i| (i % 251) as u8).collect();
write_overflow(&mut b, ps, 3, 0, &content);
let db = Database::open(b).unwrap();
let (leaves, _trunks) = db.freelist_pages_split().unwrap();
let (bytes, chain) = db
.read_freed_overflow_chain(3, remaining, usable, &leaves)
.expect("intact single-leaf chain must assemble");
assert_eq!(bytes, content);
assert_eq!(chain, vec![3]);
}
#[test]
fn freed_chain_assembles_multi_leaf_pages() {
let ps = 512usize;
let usable = ps;
let per_page = usable - 4;
let mut b = synth_db(ps, 8, 2, 5);
write_trunk(&mut b, ps, 2, 0, &[3, 4, 5, 6]);
let remaining = per_page + 50;
let content: Vec<u8> = (0..remaining).map(|i| (i % 251) as u8).collect();
write_overflow(&mut b, ps, 3, 4, &content[..per_page]);
write_overflow(&mut b, ps, 4, 0, &content[per_page..]);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
let (bytes, chain) = db
.read_freed_overflow_chain(3, remaining, usable, &leaves)
.expect("intact 2-leaf chain must assemble");
assert_eq!(bytes, content);
assert_eq!(chain, vec![3, 4]);
}
#[test]
fn freed_chain_breaks_on_non_freelist_page() {
let ps = 512usize;
let usable = ps;
let mut b = synth_db(ps, 6, 2, 2);
write_trunk(&mut b, ps, 2, 0, &[3]); let content = vec![7u8; 100];
write_overflow(&mut b, ps, 4, 0, &content);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
assert!(db
.read_freed_overflow_chain(4, 100, usable, &leaves)
.is_err());
}
#[test]
fn freed_chain_breaks_on_trunk_page() {
let ps = 512usize;
let usable = ps;
let mut b = synth_db(ps, 6, 2, 2);
write_trunk(&mut b, ps, 2, 0, &[3]);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
assert!(db
.read_freed_overflow_chain(2, 100, usable, &leaves)
.is_err());
}
#[test]
fn freed_chain_breaks_on_cycle() {
let ps = 512usize;
let usable = ps;
let per_page = usable - 4;
let mut b = synth_db(ps, 6, 2, 3);
write_trunk(&mut b, ps, 2, 0, &[3, 4]);
write_overflow(&mut b, ps, 3, 4, &vec![1u8; per_page]);
write_overflow(&mut b, ps, 4, 3, &vec![2u8; per_page]);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
assert!(db
.read_freed_overflow_chain(3, per_page * 10, usable, &leaves)
.is_err());
}
#[test]
fn freed_chain_breaks_on_premature_zero_pointer() {
let ps = 512usize;
let usable = ps;
let per_page = usable - 4;
let mut b = synth_db(ps, 6, 2, 2);
write_trunk(&mut b, ps, 2, 0, &[3]);
write_overflow(&mut b, ps, 3, 0, &vec![9u8; per_page]);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
assert!(db
.read_freed_overflow_chain(3, per_page + 10, usable, &leaves)
.is_err());
}
#[test]
fn freed_chain_breaks_on_capacity_overflow() {
let ps = 512usize;
let usable = ps;
let mut b = synth_db(ps, 6, 2, 2);
write_trunk(&mut b, ps, 2, 0, &[3]);
write_overflow(&mut b, ps, 3, 0, &vec![1u8; usable - 4]);
let db = Database::open(b).unwrap();
let (leaves, _t) = db.freelist_pages_split().unwrap();
let absurd = (usable - 4) * leaves.len() + 1;
assert!(db
.read_freed_overflow_chain(3, absurd, usable, &leaves)
.is_err());
}
fn synth_clobbered_spill_db(break_chain: bool) -> Vec<u8> {
let ps = 4096usize;
let usable = ps;
let mut b = synth_db(ps, 6, 3, 2);
write_trunk(&mut b, ps, 3, 0, &[4, 5]);
let name = b"Zoe";
let code_len = 4200usize;
let serials: [i64; 3] = [1, 13 + 2 * name.len() as i64, 13 + 2 * code_len as i64];
let mut serial_bytes = Vec::new();
for &s in &serials {
serial_bytes.extend(enc_varint(s as u64));
}
let mut header_len = serial_bytes.len() + 1;
while enc_varint(header_len as u64).len() + serial_bytes.len() != header_len {
header_len += 1;
}
let mut header = enc_varint(header_len as u64);
header.extend(&serial_bytes);
let mut full_payload = header.clone();
full_payload.push(7u8); full_payload.extend(name);
full_payload.extend(std::iter::repeat_n(b'C', code_len));
let payload_len = full_payload.len();
let local = local_payload_len(payload_len, usable);
let remaining = payload_len - local;
let base2 = ps; let tmpl_name = b"Al";
let tmpl_code = b"xy";
let tser: [i64; 3] = [
1,
13 + 2 * tmpl_name.len() as i64,
13 + 2 * tmpl_code.len() as i64,
];
let mut tsb = Vec::new();
for &s in &tser {
tsb.extend(enc_varint(s as u64));
}
let mut thl = tsb.len() + 1;
while enc_varint(thl as u64).len() + tsb.len() != thl {
thl += 1;
}
let mut tpayload = enc_varint(thl as u64);
tpayload.extend(&tsb);
tpayload.push(1u8);
tpayload.extend(tmpl_name);
tpayload.extend(tmpl_code);
let live_off = 200usize;
let mut live_cell = enc_varint(tpayload.len() as u64);
live_cell.extend(enc_varint(1u64)); live_cell.extend(&tpayload);
b[base2 + live_off..base2 + live_off + live_cell.len()].copy_from_slice(&live_cell);
b[base2] = 0x0d;
b[base2 + 1..base2 + 3].copy_from_slice(&1000u16.to_be_bytes());
b[base2 + 3..base2 + 5].copy_from_slice(&1u16.to_be_bytes());
b[base2 + 5..base2 + 7].copy_from_slice(&100u16.to_be_bytes());
b[base2 + 8..base2 + 10].copy_from_slice(&(live_off as u16).to_be_bytes());
let spill_off = 1000usize;
let mut spill_cell = enc_varint(payload_len as u64);
spill_cell.extend(enc_varint(1u64)); let prefix_len = spill_cell.len();
spill_cell.extend(&full_payload[..local]);
let chain_first = if break_chain { 3u32 } else { 4u32 };
spill_cell.extend(chain_first.to_be_bytes());
b[base2 + spill_off..base2 + spill_off + spill_cell.len()].copy_from_slice(&spill_cell);
b[base2 + spill_off] = 0;
b[base2 + spill_off + 1] = 0;
b[base2 + spill_off + 2..base2 + spill_off + 4].copy_from_slice(&4u16.to_be_bytes());
write_overflow(&mut b, ps, 4, 0, &full_payload[local..local + remaining]);
let _ = prefix_len;
b
}
#[test]
fn clobbered_spilled_cell_reconstructs_with_unknown_rowid() {
let db = Database::open(synth_clobbered_spill_db(false)).unwrap();
let page2 = db.raw_page(2).unwrap();
let recovered = db.carve_overflow_template_records(page2);
let (cell, chain) = recovered
.iter()
.find(|(c, _)| matches!(c.values.get(1), Some(Value::Text(t)) if t == "Zoe"))
.expect("synthetic clobbered spilled cell must reconstruct");
assert_eq!(cell.rowid, 0);
assert!(matches!(cell.values.get(2), Some(Value::Text(t)) if t.len() == 4200));
assert_eq!(chain, &vec![4u32]);
}
#[test]
fn clobbered_spilled_broken_chain_yields_no_full_row() {
let db = Database::open(synth_clobbered_spill_db(true)).unwrap();
let page2 = db.raw_page(2).unwrap();
let recovered = db.carve_overflow_template_records(page2);
assert!(recovered
.iter()
.all(|(c, _)| !matches!(c.values.get(1), Some(Value::Text(t)) if t == "Zoe")));
}
#[test]
fn enc_varint_into_round_trips_zero_and_multibyte() {
assert_eq!(enc_varint_into(0), vec![0]);
assert_eq!(varint_len(0), 1);
let v = enc_varint_into(8413);
assert_eq!(varint_len(8413), v.len());
assert_eq!(read_varint(&v, 0).unwrap(), (8413, v.len()));
assert_eq!(varint_len(-1), 1);
}
fn synth_gap_spill_db(break_chain: bool, code_len: usize, name: &str) -> Vec<u8> {
let ps = 4096usize;
let usable = ps;
let mut b = synth_db(ps, 6, 3, 2);
write_trunk(&mut b, ps, 3, 0, &[4, 5]);
let base2 = ps;
let serials: [i64; 3] = [1, 13 + 2 * name.len() as i64, 13 + 2 * code_len as i64];
let mut serial_bytes = Vec::new();
for &s in &serials {
serial_bytes.extend(enc_varint(s as u64));
}
let mut header_len = serial_bytes.len() + 1;
while enc_varint(header_len as u64).len() + serial_bytes.len() != header_len {
header_len += 1;
}
let mut payload = enc_varint(header_len as u64);
payload.extend(&serial_bytes);
payload.push(9u8); payload.extend(name.as_bytes());
payload.extend(std::iter::repeat_n(b'C', code_len));
let payload_len = payload.len();
let local = local_payload_len(payload_len, usable);
let remaining = payload_len - local;
let spill_off = 1500usize;
let mut cell = enc_varint(payload_len as u64);
cell.extend(enc_varint(5u64)); cell.extend(&payload[..local]);
let first = if break_chain { 3u32 } else { 4u32 };
cell.extend(first.to_be_bytes());
b[base2 + spill_off..base2 + spill_off + cell.len()].copy_from_slice(&cell);
b[base2] = 0x0d;
b[base2 + 1] = 0; b[base2 + 2] = 0;
b[base2 + 3..base2 + 5].copy_from_slice(&0u16.to_be_bytes()); b[base2 + 5..base2 + 7].copy_from_slice(&8u16.to_be_bytes());
write_overflow(&mut b, ps, 4, 0, &payload[local..local + remaining]);
b
}
#[test]
fn carve_overflow_records_resolves_gap_spill() {
let db = Database::open(synth_gap_spill_db(false, 4200, "Nora")).unwrap();
let page2 = db.raw_page(2).unwrap();
let recovered = db.carve_overflow_records(page2);
let (cell, chain) = recovered
.iter()
.find(|(c, _)| matches!(c.values.get(1), Some(Value::Text(t)) if t == "Nora"))
.expect("gap-resident spilled cell must resolve to a full row");
assert_eq!(cell.rowid, 5);
assert!(matches!(cell.values.get(2), Some(Value::Text(t)) if t.len() == 4200));
assert_eq!(chain, &vec![4u32]);
assert!(cell.confidence < 0.72);
assert!(db.carve_overflow_records(&[0x05u8; 4096]).is_empty());
assert!(db.carve_overflow_records(&[]).is_empty());
}
#[test]
fn carve_overflow_records_rejects_trunk_chain() {
let db = Database::open(synth_gap_spill_db(true, 4200, "Nora")).unwrap();
let page2 = db.raw_page(2).unwrap();
assert!(db
.carve_overflow_records(page2)
.iter()
.all(|(c, _)| !matches!(c.values.get(1), Some(Value::Text(t)) if t == "Nora")));
}
#[test]
fn stale_leaf_chain_with_invalid_utf8_is_rejected() {
let ps = 4096usize;
let usable = ps;
let mut b = synth_db(ps, 6, 3, 2);
write_trunk(&mut b, ps, 3, 0, &[4, 5]);
let base2 = ps;
let name = "Stale";
let code_len = 4200usize;
let serials: [i64; 3] = [1, 13 + 2 * name.len() as i64, 13 + 2 * code_len as i64];
let mut serial_bytes = Vec::new();
for &s in &serials {
serial_bytes.extend(enc_varint(s as u64));
}
let mut header_len = serial_bytes.len() + 1;
while enc_varint(header_len as u64).len() + serial_bytes.len() != header_len {
header_len += 1;
}
let mut payload = enc_varint(header_len as u64);
payload.extend(&serial_bytes);
payload.push(9u8);
payload.extend(name.as_bytes());
payload.extend(std::iter::repeat_n(b'C', code_len));
let payload_len = payload.len();
let local = local_payload_len(payload_len, usable);
let remaining = payload_len - local;
let spill_off = 1500usize;
let mut cell = enc_varint(payload_len as u64);
cell.extend(enc_varint(5u64));
cell.extend(&payload[..local]);
cell.extend(4u32.to_be_bytes());
b[base2 + spill_off..base2 + spill_off + cell.len()].copy_from_slice(&cell);
b[base2] = 0x0d;
b[base2 + 3..base2 + 5].copy_from_slice(&0u16.to_be_bytes());
b[base2 + 5..base2 + 7].copy_from_slice(&8u16.to_be_bytes());
let stale = vec![0xffu8; remaining];
write_overflow(&mut b, ps, 4, 0, &stale);
let db = Database::open(b).unwrap();
let page2 = db.raw_page(2).unwrap();
assert!(db.carve_overflow_records(page2).is_empty());
}
#[test]
fn carve_overflow_fragments_salvages_broken_gap_spill() {
let db = Database::open(synth_gap_spill_db(true, 4200, "Nora")).unwrap();
let page2 = db.raw_page(2).unwrap();
let frags = db.carve_overflow_fragments(page2);
let f = frags
.iter()
.find(|f| {
f.surviving
.iter()
.any(|(_, v)| matches!(v, Value::Text(t) if t == "Nora"))
})
.expect("broken-chain gap spill must salvage a fragment");
assert!(f
.surviving
.iter()
.any(|(i, v)| *i == 0 && matches!(v, Value::Integer(9))));
let ok = Database::open(synth_gap_spill_db(false, 4200, "Nora")).unwrap();
let ok_page = ok.raw_page(2).unwrap();
assert!(ok.carve_overflow_fragments(ok_page).iter().all(|f| !f
.surviving
.iter()
.any(|(_, v)| matches!(v, Value::Text(t) if t == "Nora"))));
assert!(db.carve_overflow_fragments(&[0x05u8; 4096]).is_empty());
assert!(db.carve_overflow_fragments(&[]).is_empty());
}
}