#![cfg_attr(test, allow(clippy::unwrap_used, clippy::expect_used))]
pub mod attribution;
pub mod rebuild;
pub mod row_history;
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,
BadJournalPageSize(u32),
JournalModeConflict,
}
#[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 LiveTableDump {
pub name: String,
pub column_names: Vec<String>,
pub rows: Vec<Row>,
}
#[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;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum WalChecksumEndian {
Big,
Little,
}
impl WalChecksumEndian {
fn from_magic(magic: u32) -> Option<Self> {
match magic {
0x377f_0683 => Some(Self::Big),
0x377f_0682 => Some(Self::Little),
_ => None,
}
}
fn read_word(self, b: [u8; 4]) -> u32 {
match self {
Self::Big => u32::from_be_bytes(b),
Self::Little => u32::from_le_bytes(b),
}
}
}
fn wal_checksum(endian: WalChecksumEndian, mut s0: u32, mut s1: u32, data: &[u8]) -> (u32, u32) {
let mut chunks = data.chunks_exact(8);
for c in &mut chunks {
let x0 = endian.read_word([c[0], c[1], c[2], c[3]]);
let x1 = endian.read_word([c[4], c[5], c[6], c[7]]);
s0 = s0.wrapping_add(x0).wrapping_add(s1);
s1 = s1.wrapping_add(x1).wrapping_add(s0);
}
(s0, s1)
}
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,
})
}
pub fn rollback_prior(&self, journal: &[u8]) -> Result<PriorSnapshot, Error> {
if self.wal_applied() {
return Err(Error::JournalModeConflict);
}
let page_size = self.header.page_size;
let parsed = RollbackJournal::parse(journal, page_size)?;
let main_pages = self.file_page_count();
let mut overlaid: std::collections::BTreeMap<u32, Vec<u8>> =
std::collections::BTreeMap::new();
for pgno in 1..=main_pages {
if let Some(slice) = self.raw_page(pgno) {
overlaid.insert(pgno, slice.to_vec());
}
}
let mut grew_db = false;
for img in parsed.page_images() {
if img.pgno > main_pages {
grew_db = true;
}
overlaid.insert(img.pgno, img.bytes.clone());
}
let reserved = overlaid
.get(&1)
.and_then(|p| p.get(RESERVED_SPACE_OFFSET).copied())
.unwrap_or(self.header.reserved);
let usable = page_size.saturating_sub(u32::from(reserved));
let page_bound = overlaid.keys().copied().next_back().unwrap_or(main_pages);
Ok(PriorSnapshot {
overlaid,
usable,
page_bound,
grew_db,
})
}
#[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 seen = std::collections::BTreeSet::new();
self.collect_rowids(root, &mut ids, &mut seen);
}
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 seen = std::collections::BTreeSet::new();
self.collect_rows(root, &mut rows, &mut seen);
}
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(), }
}
#[must_use]
pub fn live_tables(&self) -> Vec<attribution::LiveTable> {
let mut tables = Vec::new();
let Ok(schema) = self.read_table(1, 5) else {
return tables; };
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::Text(name)) = row.values.get(1) else {
continue; };
if name.starts_with("sqlite_") {
continue;
}
let Some(Value::Integer(root)) = row.values.get(3) else {
continue; };
let Ok(rootpage) = u32::try_from(*root) else {
continue; };
let sql = match row.values.get(4) {
Some(Value::Text(s)) => s.as_str(),
_ => "", };
let defs = attribution::column_defs(sql);
let affinities = defs.as_ref().map_or_else(Vec::new, |d| {
d.iter()
.map(|(_, ty)| attribution::column_affinity(ty))
.collect()
});
let column_names = defs.map(|d| d.into_iter().map(|(n, _)| n).collect());
tables.push(attribution::LiveTable {
name: name.clone(),
rootpage,
column_names,
affinities,
create_sql: sql.to_string(),
});
}
tables
}
#[must_use]
pub fn schema_sql(&self) -> std::collections::BTreeMap<String, String> {
let mut out = std::collections::BTreeMap::new();
let Ok(schema) = self.read_table(1, 5) else {
return out; };
for row in schema {
schema_sql_insert(&mut out, &row.values);
}
out
}
#[must_use]
pub fn row_histories(&self) -> Vec<row_history::TableHistory> {
use row_history::{RowView, VersionOrigin};
let live_dumps = self.live_table_rows();
let without_rowid = self.live_without_rowid_map();
let mut histories = Vec::with_capacity(live_dumps.len());
for dump in live_dumps {
let wr = without_rowid.get(&dump.name).copied().unwrap_or(false);
let mut views: Vec<RowView> = Vec::new();
if let Some(timeline) = self.wal_timeline() {
let mut seq_in_segment: std::collections::BTreeMap<WalSegmentId, u32> =
std::collections::BTreeMap::new();
for snapshot in timeline.commit_snapshots() {
let seg = snapshot.id().segment;
let seq = seq_in_segment.entry(seg).or_insert(0);
let commit_seq = *seq;
*seq += 1;
let snap_tables = snapshot.tables();
let Some(st) = snap_tables.iter().find(|t| t.name == dump.name) else {
continue; };
if st.without_rowid {
continue; }
let schema_known = !st.columns.is_empty();
let rows = match snapshot.read_table(st.rootpage, st.columns.len()) {
Ok(rows) => rows.into_iter().collect(),
Err(_) => std::collections::BTreeMap::new(),
};
views.push(RowView {
commit_seq: Some(commit_seq),
is_final: false,
checksum_valid: snapshot.checksum_valid(),
schema_known,
origin: VersionOrigin::Commit(snapshot.id()),
rows,
});
}
}
let live_rows: std::collections::BTreeMap<i64, Vec<Value>> = dump
.rows
.iter()
.map(|r| (r.rowid, r.values.clone()))
.collect();
views.push(RowView {
commit_seq: None,
is_final: true,
checksum_valid: true,
schema_known: true,
origin: VersionOrigin::Live,
rows: live_rows,
});
histories.push(row_history::table_history(
dump.name,
dump.column_names,
wr,
&views,
));
}
histories
}
fn live_without_rowid_map(&self) -> std::collections::BTreeMap<String, bool> {
let mut map = std::collections::BTreeMap::new();
let Ok(schema) = self.read_table(1, 5) else {
return map; };
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::Text(name)) = row.values.get(1) else {
continue; };
if name.starts_with("sqlite_") {
continue;
}
let sql = match row.values.get(4) {
Some(Value::Text(s)) => s.as_str(),
_ => "", };
map.insert(name.clone(), without_rowid_sql(sql));
}
map
}
#[must_use]
pub fn sqlite_sequence(&self) -> std::collections::BTreeMap<String, i64> {
let mut map = std::collections::BTreeMap::new();
let Ok(schema) = self.read_table(1, 5) else {
return map; };
let mut rootpage: Option<u32> = None;
for row in &schema {
let is_table = matches!(row.values.first(), Some(Value::Text(t)) if t == "table");
if !is_table {
continue;
}
if !matches!(row.values.get(1), Some(Value::Text(n)) if n == "sqlite_sequence") {
continue;
}
if let Some(Value::Integer(root)) = row.values.get(3) {
rootpage = u32::try_from(*root).ok();
}
break;
}
let Some(root) = rootpage else {
return map; };
let Ok(rows) = self.read_table(root, 2) else {
return map; };
for row in rows {
let (Some(Value::Text(name)), Some(Value::Integer(seq))) =
(row.values.first(), row.values.get(1))
else {
continue;
};
map.insert(name.clone(), *seq);
}
map
}
#[must_use]
pub fn live_table_rows(&self) -> Vec<LiveTableDump> {
self.live_tables()
.into_iter()
.map(|table| {
let declared = table.column_names.as_ref().map_or(0, Vec::len);
let rows = self
.read_table(table.rootpage, declared)
.unwrap_or_default();
let widest = rows.iter().map(|r| r.values.len()).max().unwrap_or(0);
let column_names = match table.column_names {
Some(names) => names,
None => (0..widest).map(|i| format!("c{i}")).collect(),
};
LiveTableDump {
name: table.name,
column_names,
rows,
}
})
.collect()
}
#[must_use]
pub fn page_to_table_map(&self) -> std::collections::BTreeMap<u32, String> {
let mut map = std::collections::BTreeMap::new();
for table in self.live_tables() {
let mut pages = std::collections::BTreeSet::new();
let mut visited = 0usize;
self.collect_pages(table.rootpage, &mut pages, &mut visited);
for page in pages {
map.insert(page, table.name.clone());
}
}
map
}
fn collect_pages(
&self,
page: u32,
pages: &mut std::collections::BTreeSet<u32>,
visited: &mut usize,
) {
*visited += 1;
if *visited > MAX_PAGES_PER_WALK {
return; }
if page == 0 || !pages.insert(page) {
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; };
if page_type != 0x05 {
return; }
let cell_count = be_u16(slice, hdr_off + 3) as usize;
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);
self.collect_pages(child, pages, visited);
}
let right = be_u32(slice, hdr_off + 8);
self.collect_pages(right, pages, visited);
}
fn collect_rows(
&self,
page: u32,
rows: &mut std::collections::BTreeMap<i64, Vec<Value>>,
seen: &mut std::collections::BTreeSet<u32>,
) {
if page == 0 || seen.len() > MAX_PAGES_PER_WALK || !seen.insert(page) {
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);
self.collect_rows(child, rows, seen);
}
let right = be_u32(slice, hdr_off + 8);
self.collect_rows(right, rows, seen);
}
_ => {} }
}
fn collect_rowids(
&self,
page: u32,
ids: &mut std::collections::BTreeSet<i64>,
seen: &mut std::collections::BTreeSet<u32>,
) {
if page == 0 || seen.len() > MAX_PAGES_PER_WALK || !seen.insert(page) {
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);
self.collect_rowids(child, ids, seen);
}
let right = be_u32(slice, hdr_off + 8);
self.collect_rowids(right, ids, seen);
}
_ => {} }
}
pub fn read_table(&self, root_page: u32, column_count: usize) -> Result<Vec<Row>, Error> {
read_table_via(self, root_page, column_count)
}
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))
}
}
trait PageSource {
fn page(&self, page: u32) -> Option<&[u8]>;
fn usable(&self) -> usize;
fn page_bound(&self) -> u32;
fn encoding(&self) -> TextEncoding;
}
impl PageSource for Database {
fn page(&self, page: u32) -> Option<&[u8]> {
self.page_slice(page).ok()
}
fn usable(&self) -> usize {
self.header.usable_size() as usize
}
fn page_bound(&self) -> u32 {
self.file_page_count()
}
fn encoding(&self) -> TextEncoding {
self.header.text_encoding
}
}
impl PageSource for CommitSnapshot {
fn page(&self, page: u32) -> Option<&[u8]> {
self.overlaid.get(&page).map(Vec::as_slice)
}
fn usable(&self) -> usize {
self.usable as usize
}
fn page_bound(&self) -> u32 {
self.id.db_size_after_commit
}
fn encoding(&self) -> TextEncoding {
self.overlaid
.get(&1)
.map(|p| match be_u32(p, TEXT_ENCODING_OFFSET) {
2 => TextEncoding::Utf16Le,
3 => TextEncoding::Utf16Be,
_ => TextEncoding::Utf8,
})
.unwrap_or_default()
}
}
fn schema_sql_insert(out: &mut std::collections::BTreeMap<String, String>, values: &[Value]) {
let is_table = matches!(values.first(), Some(Value::Text(t)) if t == "table");
if !is_table {
return;
}
let Some(Value::Text(name)) = values.get(1) else {
return; };
if name.starts_with("sqlite_") {
return;
}
let sql = match values.get(4) {
Some(Value::Text(s)) => s.clone(),
_ => String::new(), };
out.insert(name.clone(), sql);
}
fn read_table_via(
src: &dyn PageSource,
root_page: u32,
column_count: usize,
) -> Result<Vec<Row>, Error> {
let mut rows = Vec::new();
let mut seen = std::collections::BTreeSet::new();
walk_table_page(src, root_page, column_count, &mut rows, &mut seen)?;
Ok(rows)
}
fn walk_table_page(
src: &dyn PageSource,
page: u32,
column_count: usize,
rows: &mut Vec<Row>,
seen: &mut std::collections::BTreeSet<u32>,
) -> Result<(), Error> {
if seen.len() > MAX_PAGES_PER_WALK {
return Err(Error::TooManyPages);
}
if !seen.insert(page) {
return Ok(());
}
let slice = src.page(page).ok_or(Error::PageOutOfRange(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 => read_leaf_cells(src, 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);
walk_table_page(src, child, column_count, rows, seen)?;
}
let right = be_u32(slice, hdr_off + 8);
walk_table_page(src, right, column_count, rows, seen)
}
other => Err(Error::NotATablePage(other)),
}
}
fn read_leaf_cells(
src: &dyn PageSource,
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 = decode_leaf_cell(src, slice, cell_off, column_count)?;
rows.push(row);
}
Ok(())
}
fn decode_leaf_cell(
src: &dyn PageSource,
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 = src.usable();
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);
read_overflow_chain(src, first_overflow, total - local, &mut buf)?;
buf
};
let values = decode_record(&payload, column_count, rowid, src.encoding())?;
Ok(Row { rowid, values })
}
fn read_overflow_chain(
src: &dyn PageSource,
first: u32,
mut remaining: usize,
buf: &mut Vec<u8>,
) -> Result<(), Error> {
let usable = src.usable();
let per_page = usable.saturating_sub(4);
if per_page == 0 {
return Err(Error::MalformedOverflow);
}
let total_pages = src.page_bound();
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 = src.page(page).ok_or(Error::PageOutOfRange(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(())
}
pub(crate) 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>>,
checksum_valid: bool,
usable: u32,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SnapshotTable {
pub name: String,
pub rootpage: u32,
pub columns: Vec<String>,
pub without_rowid: bool,
}
fn normalized_unquoted_sql(create_sql: &str) -> String {
let bytes = create_sql.as_bytes();
let mut unquoted = String::with_capacity(create_sql.len());
let mut quote: Option<u8> = None;
for &c in bytes {
match quote {
Some(q) => {
if c == q {
quote = None;
}
}
None => match c {
b'\'' | b'"' | b'`' => quote = Some(c),
b'[' => quote = Some(b']'),
_ => unquoted.push(c as char),
},
}
}
unquoted
.split_whitespace()
.collect::<Vec<_>>()
.join(" ")
.to_ascii_uppercase()
}
fn without_rowid_sql(create_sql: &str) -> bool {
normalized_unquoted_sql(create_sql).contains("WITHOUT ROWID")
}
#[must_use]
pub fn is_autoincrement(create_sql: &str) -> bool {
let normalized = normalized_unquoted_sql(create_sql);
normalized.contains("INTEGER PRIMARY KEY AUTOINCREMENT")
&& !normalized.contains("WITHOUT ROWID")
}
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 checksum_valid(&self) -> bool {
self.checksum_valid
}
#[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 })
}
#[must_use]
pub fn tables(&self) -> Vec<SnapshotTable> {
let Ok(schema) = read_table_via(self, 1, 5) else {
return Vec::new(); };
let mut out = Vec::new();
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::Text(name)) = row.values.get(1) else {
continue; };
if name.starts_with("sqlite_") {
continue;
}
let Some(Value::Integer(root)) = row.values.get(3) else {
continue; };
let Ok(rootpage) = u32::try_from(*root) else {
continue; };
let sql = match row.values.get(4) {
Some(Value::Text(s)) => s.as_str(),
_ => "", };
let columns = attribution::column_names(sql).unwrap_or_default();
out.push(SnapshotTable {
name: name.clone(),
rootpage,
columns,
without_rowid: without_rowid_sql(sql),
});
}
out
}
pub fn read_table(
&self,
rootpage: u32,
column_count: usize,
) -> Result<Vec<(i64, Vec<Value>)>, Error> {
let rows = read_table_via(self, rootpage, column_count)?;
Ok(rows.into_iter().map(|r| (r.rowid, r.values)).collect())
}
}
#[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 endian = WalChecksumEndian::from_magic(magic).unwrap_or(WalChecksumEndian::Big);
let header_s0 = be_u32(hdr, 24);
let header_s1 = be_u32(hdr, 28);
let mut run_s0 = header_s0;
let mut run_s1 = header_s1;
let mut chain_valid = true;
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;
chain_valid = false;
}
if page_no == 0 {
break; }
let data = match frame.get(SQLITE_WAL_FRAME_HEADER_SIZE..) {
Some(d) => d.to_vec(),
None => break, };
if chain_valid {
let (n0, n1) = wal_checksum(endian, run_s0, run_s1, &frame[0..8]);
let (n0, n1) = wal_checksum(endian, n0, n1, &data);
run_s0 = n0;
run_s1 = n1;
let stored0 = be_u32(frame, 16);
let stored1 = be_u32(frame, 20);
if stored0 != run_s0 || stored1 != run_s1 {
chain_valid = false;
}
}
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,
};
let overlaid = committed_pages.clone();
let reserved = overlaid
.get(&1)
.and_then(|p| p.get(RESERVED_SPACE_OFFSET).copied())
.unwrap_or(0);
let usable = page_size.saturating_sub(u32::from(reserved));
snapshots.push(CommitSnapshot {
id,
overlaid,
salt1,
salt2,
checksum_valid: chain_valid,
usable,
});
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() {
if template.known_lead_serials.is_empty() {
cells.extend(template.reconstruct_span_exact(page_bytes, fb, fb_end));
} else {
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 !template.known_lead_serials.is_empty() && 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?;
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_cell_empty_lead(
&self,
page: &[u8],
cell_start: usize,
span_end: usize,
) -> Option<(CarvedCell, usize)> {
let tail_start = cell_start.checked_add(self.surviving_serials_off)?;
let mut serials = Vec::with_capacity(self.column_count);
let mut pos = tail_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)?;
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_span_exact(&self, page: &[u8], lo: usize, hi: usize) -> Vec<CarvedCell> {
let mut cells = Vec::new();
let mut cell_start = lo;
let mut guard = 0usize;
while cell_start < hi && guard < MAX_FREEBLOCKS_PER_PAGE {
guard += 1;
let Some((cell, record_end)) = self.reconstruct_cell_empty_lead(page, cell_start, hi)
else {
return Vec::new(); };
if record_end <= cell_start {
return Vec::new(); }
cells.push(cell);
cell_start = record_end;
}
if cell_start == hi {
cells
} else {
Vec::new()
}
}
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()
}
pub(crate) 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
}
const JOURNAL_MAGIC: [u8; 8] = [0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7];
const MAX_JOURNAL_RECORDS: usize = 1_000_000;
const SECTOR_CANDIDATES: [u32; 3] = [512, 4096, 0];
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum JournalHeader {
Valid {
n_rec: u32,
mx_page: u32,
nonce: u32,
sector_size: u32,
page_size: u32,
},
ReconstructedZeroed {
page_size: u32,
sector_size: u32,
},
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct JournalPageImage {
pub pgno: u32,
pub segment: usize,
pub bytes: Vec<u8>,
pub checksum_valid: Option<bool>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RollbackJournal {
header: JournalHeader,
images: Vec<JournalPageImage>,
duplicate_pgnos: Vec<u32>,
}
fn journal_cksum(nonce: u32, page: &[u8]) -> u32 {
let mut sum = nonce;
let mut x = page.len() as i64 - 200;
while x > 0 {
if let Some(&b) = page.get(x as usize) {
sum = sum.wrapping_add(u32::from(b));
}
x -= 200;
}
sum
}
fn walk_journal_records(
bytes: &[u8],
start: usize,
page_size: usize,
nonce: Option<u32>,
segment: usize,
limit: usize,
) -> Vec<JournalPageImage> {
let stride = 4usize.saturating_add(page_size).saturating_add(4);
let mut out = Vec::new();
let mut off = start;
let cap = limit.min(MAX_JOURNAL_RECORDS);
while out.len() < cap {
let Some(rec) = bytes.get(off..off.saturating_add(stride)) else {
break; };
let pgno = u32::from_be_bytes([rec[0], rec[1], rec[2], rec[3]]);
if pgno == 0 {
break; }
let page = &rec[4..4 + page_size];
let stored = u32::from_be_bytes([
rec[4 + page_size],
rec[5 + page_size],
rec[6 + page_size],
rec[7 + page_size],
]);
let checksum_valid = nonce.map(|n| journal_cksum(n, page) == stored);
out.push(JournalPageImage {
pgno,
segment,
bytes: page.to_vec(),
checksum_valid,
});
off = off.saturating_add(stride);
}
out
}
fn score_journal_candidate(images: &[JournalPageImage], page_bound: u32) -> usize {
if images.is_empty() {
return 0;
}
let in_range = images
.iter()
.filter(|i| i.pgno >= 1 && i.pgno <= page_bound)
.count();
if in_range == images.len() {
1000 + images.len()
} else {
in_range
}
}
impl RollbackJournal {
pub fn parse(bytes: &[u8], page_size: u32) -> Result<Self, Error> {
if !(512..=65536).contains(&page_size) || !page_size.is_power_of_two() {
return Err(Error::BadJournalPageSize(page_size));
}
let ps = page_size as usize;
let page_bound = u32::try_from(bytes.len() / ps.max(1)).unwrap_or(u32::MAX);
let header_valid = bytes.len() >= 28 && bytes.starts_with(&JOURNAL_MAGIC);
if header_valid {
let n_rec = be_u32(bytes, 8);
let nonce = be_u32(bytes, 12);
let mx_page = be_u32(bytes, 16);
let sector_size = be_u32(bytes, 20);
let hdr_page_size = be_u32(bytes, 24);
let limit = if n_rec == 0 || n_rec == u32::MAX {
MAX_JOURNAL_RECORDS
} else {
n_rec as usize
};
let start = sector_size.max(1) as usize;
let imgs = walk_journal_records(bytes, start, ps, Some(nonce), 0, limit);
let header = JournalHeader::Valid {
n_rec,
mx_page,
nonce,
sector_size,
page_size: if hdr_page_size == page_size {
hdr_page_size
} else {
page_size
},
};
return Ok(Self::from_walk(header, imgs));
}
let mut best: Option<(usize, u32, Vec<JournalPageImage>)> = None;
for cand in SECTOR_CANDIDATES {
let sector = if cand == 0 { page_size } else { cand };
let imgs =
walk_journal_records(bytes, sector as usize, ps, None, 0, MAX_JOURNAL_RECORDS);
let score = score_journal_candidate(&imgs, page_bound);
let better = best.as_ref().map_or(true, |(bs, _, _)| score > *bs);
if better && score > 0 {
best = Some((score, sector, imgs));
}
}
let (sector_size, imgs) = best
.map(|(_, s, i)| (s, i))
.unwrap_or((page_size, Vec::new()));
let header = JournalHeader::ReconstructedZeroed {
page_size,
sector_size,
};
Ok(Self::from_walk(header, imgs))
}
fn from_walk(header: JournalHeader, walked: Vec<JournalPageImage>) -> Self {
let mut seen = std::collections::BTreeSet::new();
let mut images = Vec::with_capacity(walked.len());
let mut duplicate_pgnos: Vec<u32> = Vec::new();
for img in walked {
if seen.insert(img.pgno) {
images.push(img);
} else if !duplicate_pgnos.contains(&img.pgno) {
duplicate_pgnos.push(img.pgno);
}
}
Self {
header,
images,
duplicate_pgnos,
}
}
#[must_use]
pub fn header(&self) -> &JournalHeader {
&self.header
}
#[must_use]
pub fn page_images(&self) -> &[JournalPageImage] {
&self.images
}
#[must_use]
pub fn has_duplicate_pgno(&self) -> bool {
!self.duplicate_pgnos.is_empty()
}
#[must_use]
pub fn duplicate_pgnos(&self) -> &[u32] {
&self.duplicate_pgnos
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PriorSnapshot {
overlaid: std::collections::BTreeMap<u32, Vec<u8>>,
usable: u32,
page_bound: u32,
grew_db: bool,
}
impl PageSource for PriorSnapshot {
fn page(&self, page: u32) -> Option<&[u8]> {
self.overlaid.get(&page).map(Vec::as_slice)
}
fn usable(&self) -> usize {
self.usable as usize
}
fn page_bound(&self) -> u32 {
self.page_bound
}
fn encoding(&self) -> TextEncoding {
self.overlaid
.get(&1)
.map(|p| match be_u32(p, TEXT_ENCODING_OFFSET) {
2 => TextEncoding::Utf16Le,
3 => TextEncoding::Utf16Be,
_ => TextEncoding::Utf8,
})
.unwrap_or_default()
}
}
impl PriorSnapshot {
#[must_use]
pub fn tables(&self) -> Vec<SnapshotTable> {
let Ok(schema) = read_table_via(self, 1, 5) else {
return Vec::new(); };
let mut out = Vec::new();
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::Text(name)) = row.values.get(1) else {
continue; };
if name.starts_with("sqlite_") {
continue;
}
let Some(Value::Integer(root)) = row.values.get(3) else {
continue; };
let Ok(rootpage) = u32::try_from(*root) else {
continue; };
let sql = match row.values.get(4) {
Some(Value::Text(s)) => s.as_str(),
_ => "", };
let columns = attribution::column_names(sql).unwrap_or_default();
out.push(SnapshotTable {
name: name.clone(),
rootpage,
columns,
without_rowid: without_rowid_sql(sql),
});
}
out
}
#[must_use]
pub fn schema_sql(&self) -> std::collections::BTreeMap<String, String> {
let mut out = std::collections::BTreeMap::new();
let Ok(schema) = read_table_via(self, 1, 5) else {
return out; };
for row in schema {
schema_sql_insert(&mut out, &row.values);
}
out
}
pub fn read_table(
&self,
rootpage: u32,
column_count: usize,
) -> Result<Vec<(i64, Vec<Value>)>, Error> {
let rows = read_table_via(self, rootpage, column_count)?;
Ok(rows.into_iter().map(|r| (r.rowid, r.values)).collect())
}
#[must_use]
pub fn grew_db(&self) -> bool {
self.grew_db
}
pub fn read_table_with_pages(
&self,
rootpage: u32,
column_count: usize,
) -> Result<Vec<(i64, Vec<Value>, u32)>, Error> {
let mut out = Vec::new();
let mut seen = std::collections::BTreeSet::new();
walk_table_page_with_leaf(self, rootpage, column_count, &mut out, &mut seen)?;
Ok(out)
}
}
fn walk_table_page_with_leaf(
src: &dyn PageSource,
page: u32,
column_count: usize,
out: &mut Vec<(i64, Vec<Value>, u32)>,
seen: &mut std::collections::BTreeSet<u32>,
) -> Result<(), Error> {
if seen.len() > MAX_PAGES_PER_WALK {
return Err(Error::TooManyPages);
}
if !seen.insert(page) {
return Ok(());
}
let slice = src.page(page).ok_or(Error::PageOutOfRange(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 => {
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 = decode_leaf_cell(src, slice, cell_off, column_count)?;
out.push((row.rowid, row.values, page));
}
Ok(())
}
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);
walk_table_page_with_leaf(src, child, column_count, out, seen)?;
}
let right = be_u32(slice, hdr_off + 8);
walk_table_page_with_leaf(src, right, column_count, out, seen)
}
other => Err(Error::NotATablePage(other)),
}
}
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_text_utf16_le_and_be() {
let le = [b'h', 0x00, b'i', 0x00];
let (v, n) = decode_value(&le, 0, 21, TextEncoding::Utf16Le).unwrap();
assert_eq!(v, Value::Text("hi".into()));
assert_eq!(n, 4);
let be = [0x00, b'h', 0x00, b'i'];
let (v, n) = decode_value(&be, 0, 21, TextEncoding::Utf16Be).unwrap();
assert_eq!(v, Value::Text("hi".into()));
assert_eq!(n, 4);
}
#[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:?}"
);
}
#[test]
fn live_table_rows_dumps_each_user_table_in_rowid_order() {
let db = Database::open(CLEAN_DB.to_vec()).unwrap();
let dumps = db.live_table_rows();
assert_eq!(dumps.len(), 1, "one user-table dump expected: {dumps:?}");
let t = &dumps[0];
assert_eq!(t.name, "moz_places");
assert!(
t.column_names.iter().any(|c| c == "url"),
"real column names expected: {:?}",
t.column_names
);
let rowids: Vec<i64> = t.rows.iter().map(|r| r.rowid).collect();
assert_eq!(rowids, vec![1, 2, 3, 4, 5], "rowid order: {rowids:?}");
assert!(
matches!(t.rows[0].values.get(1), Some(Value::Text(s)) if s.contains("rust-lang")),
"row 1 url must decode: {:?}",
t.rows[0].values
);
}
#[test]
fn live_table_rows_excludes_internal_tables_and_handles_interior_btree() {
let db = Database::open(DELETED_DB.to_vec()).unwrap();
let dumps = db.live_table_rows();
assert!(
dumps.iter().all(|t| !t.name.starts_with("sqlite_")),
"internal tables excluded: {:?}",
dumps.iter().map(|t| &t.name).collect::<Vec<_>>()
);
let places = dumps
.iter()
.find(|t| t.name == "moz_places")
.expect("moz_places dump");
assert_eq!(places.rows.len(), 200, "all live rows dumped");
let ids: Vec<i64> = places.rows.iter().map(|r| r.rowid).collect();
assert!(
ids.windows(2).all(|w| w[0] < w[1]),
"rows in ascending rowid order"
);
assert_eq!(*ids.first().unwrap(), 1);
assert_eq!(*ids.last().unwrap(), 200);
}
#[test]
fn live_table_rows_falls_back_to_generic_columns_on_unparseable_schema() {
use crate::rebuild::{build_recovered_db_tables, RecoveredTable as RT};
let seed = vec![RT {
name: "people".to_string(),
columns: vec!["id".to_string(), "name".to_string()],
rows: vec![vec![Value::Integer(1), Value::Text("alice".into())]],
}];
let mut bytes = build_recovered_db_tables(&seed);
let needle = b"CREATE TABLE \"people\"";
let start = bytes
.windows(needle.len())
.position(|w| w == needle)
.expect("schema SQL present");
let open = bytes[start..]
.iter()
.position(|&b| b == b'(')
.map(|p| start + p)
.expect("column list open paren");
let close = bytes[open..]
.iter()
.position(|&b| b == b')')
.map(|p| open + p)
.expect("column list close paren");
for b in &mut bytes[open..=close] {
*b = b' ';
}
let db = Database::open(bytes).expect("corrupted-schema db still opens");
let dumps = db.live_table_rows();
let people = dumps
.iter()
.find(|t| t.name == "people")
.expect("people dump present");
assert_eq!(
people.column_names,
vec!["c0".to_string(), "c1".to_string()]
);
assert_eq!(people.rows.len(), 1);
assert_eq!(people.rows[0].values.first(), Some(&Value::Integer(1)));
}
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.is_empty(),
"the truncated anchor yields no full record, got {}",
cells.len()
);
}
#[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.is_empty(),
"a trunk-routed broken chain must yield no full row, got {} rows",
recovered.len()
);
}
#[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();
let recovered = db.carve_overflow_records(page2);
assert!(
recovered.is_empty(),
"a trunk-routed chain must yield no full overflow row, got {} rows",
recovered.len()
);
}
#[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).is_empty(),
"an intact chain yields a full row, not a fragment"
);
assert!(db.carve_overflow_fragments(&[0x05u8; 4096]).is_empty());
assert!(db.carve_overflow_fragments(&[]).is_empty());
}
#[test]
fn wal_checksum_known_vector_both_endiannesses() {
let data_be = [0, 0, 0, 2, 0, 0, 0, 3];
assert_eq!(wal_checksum(WalChecksumEndian::Big, 0, 0, &data_be), (2, 5));
assert_eq!(
wal_checksum(WalChecksumEndian::Little, 0, 0, &data_be),
(0x0200_0000, 0x0500_0000)
);
assert_eq!(
wal_checksum(WalChecksumEndian::Big, 2, 5, &data_be),
(9, 17)
);
let big = [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
let _ = wal_checksum(WalChecksumEndian::Big, u32::MAX, u32::MAX, &big);
}
#[test]
fn wal_checksum_endian_from_magic_matches_spec() {
assert_eq!(
WalChecksumEndian::from_magic(0x377f_0683),
Some(WalChecksumEndian::Big)
);
assert_eq!(
WalChecksumEndian::from_magic(0x377f_0682),
Some(WalChecksumEndian::Little)
);
assert_eq!(WalChecksumEndian::from_magic(0xdead_beef), None);
}
fn wrap_db_in_wal(main: &[u8], page_size: u32) -> Vec<u8> {
let ps = page_size as usize;
let n_pages = main.len() / ps;
let endian = WalChecksumEndian::Little; let (salt1, salt2) = (0x1234_5678u32, 0x9abc_def0u32);
let mut wal = vec![0u8; 32];
wal[0..4].copy_from_slice(&0x377f_0682u32.to_be_bytes()); wal[4..8].copy_from_slice(&3_007_000u32.to_be_bytes());
wal[8..12].copy_from_slice(&page_size.to_be_bytes());
wal[12..16].copy_from_slice(&1u32.to_be_bytes());
wal[16..20].copy_from_slice(&salt1.to_be_bytes());
wal[20..24].copy_from_slice(&salt2.to_be_bytes());
let (mut s0, mut s1) = wal_checksum(endian, 0, 0, &wal[0..24]);
wal[24..28].copy_from_slice(&s0.to_be_bytes());
wal[28..32].copy_from_slice(&s1.to_be_bytes());
for i in 0..n_pages {
let page_no = (i + 1) as u32;
let db_size = if i + 1 == n_pages { n_pages as u32 } else { 0 };
let mut fh = [0u8; 24];
fh[0..4].copy_from_slice(&page_no.to_be_bytes());
fh[4..8].copy_from_slice(&db_size.to_be_bytes());
fh[8..12].copy_from_slice(&salt1.to_be_bytes());
fh[12..16].copy_from_slice(&salt2.to_be_bytes());
let data = &main[i * ps..(i + 1) * ps];
let (n0, n1) = wal_checksum(endian, s0, s1, &fh[0..8]);
let (n0, n1) = wal_checksum(endian, n0, n1, data);
s0 = n0;
s1 = n1;
fh[16..20].copy_from_slice(&s0.to_be_bytes());
fh[20..24].copy_from_slice(&s1.to_be_bytes());
wal.extend_from_slice(&fh);
wal.extend_from_slice(data);
}
wal
}
#[test]
fn snapshot_tables_reads_schema_from_its_own_page_one() {
use crate::rebuild::{build_recovered_db_tables, RecoveredTable as RT};
let seed = vec![RT {
name: "people".to_string(),
columns: vec!["id".to_string(), "name".to_string()],
rows: vec![
vec![Value::Integer(1), Value::Text("alice".into())],
vec![Value::Integer(2), Value::Text("bob".into())],
],
}];
let main = build_recovered_db_tables(&seed);
let ps = parse_header(&main).unwrap().page_size;
let wal = wrap_db_in_wal(&main, ps);
let db = Database::open_with_wal(main, &wal).unwrap();
let tl = db.wal_timeline().unwrap();
let snap = tl.commit_snapshots().last().unwrap();
assert!(snap.checksum_valid(), "minted WAL must be checksum-valid");
let tables = snap.tables();
let people = tables
.iter()
.find(|t| t.name == "people")
.expect("table 'people' present in snapshot schema");
assert!(people.rootpage >= 2, "rootpage points past page 1");
assert_eq!(people.columns, vec!["id".to_string(), "name".to_string()]);
assert!(!people.without_rowid, "an ordinary rowid table");
assert!(tables.iter().all(|t| !t.name.starts_with("sqlite_")));
}
#[test]
fn snapshot_read_resolves_overflow_through_snapshot_pages_not_live_view() {
use crate::rebuild::{build_recovered_db_tables, RecoveredTable as RT};
let blob: Vec<u8> = (0..9000u32).map(|i| (i % 251) as u8).collect();
let seed = vec![RT {
name: "t".to_string(),
columns: vec!["id".to_string(), "big".to_string()],
rows: vec![vec![Value::Integer(1), Value::Blob(blob.clone())]],
}];
let minted = build_recovered_db_tables(&seed);
let ps = parse_header(&minted).unwrap().page_size;
let wal = wrap_db_in_wal(&minted, ps);
let mut clobbered_main = minted.clone();
for p in clobbered_main.iter_mut().skip(2 * ps as usize) {
*p = 0xEE;
}
let db = Database::open_with_wal(clobbered_main, &wal).unwrap();
let tl = db.wal_timeline().unwrap();
let snap = tl.commit_snapshots().last().unwrap();
let t = snap
.tables()
.into_iter()
.find(|t| t.name == "t")
.expect("table t in snapshot");
let rows = snap.read_table(t.rootpage, t.columns.len()).unwrap();
assert_eq!(rows.len(), 1, "one row at this commit");
let (rowid, values) = &rows[0];
assert_eq!(*rowid, 1);
assert_eq!(
values.get(1),
Some(&Value::Blob(blob)),
"overflow blob must reassemble from the snapshot's pages, not the clobbered live view"
);
}
#[test]
fn snapshot_read_walks_interior_btree_in_rowid_order() {
use crate::rebuild::{build_recovered_db_tables, RecoveredTable as RT};
let rows_seed: Vec<Vec<Value>> = (1..=500i64)
.map(|i| vec![Value::Integer(i), Value::Text(format!("name-{i}"))])
.collect();
let seed = vec![RT {
name: "big".to_string(),
columns: vec!["id".to_string(), "name".to_string()],
rows: rows_seed,
}];
let minted = build_recovered_db_tables(&seed);
let ps = parse_header(&minted).unwrap().page_size;
let wal = wrap_db_in_wal(&minted, ps);
let db = Database::open_with_wal(minted, &wal).unwrap();
let tl = db.wal_timeline().unwrap();
let snap = tl.commit_snapshots().last().unwrap();
let t = snap
.tables()
.into_iter()
.find(|t| t.name == "big")
.expect("table big");
let rows = snap.read_table(t.rootpage, t.columns.len()).unwrap();
assert_eq!(rows.len(), 500, "all rows across the interior b-tree");
let ids: Vec<i64> = rows.iter().map(|(r, _)| *r).collect();
assert!(ids.windows(2).all(|w| w[0] < w[1]), "ascending rowid order");
assert_eq!(*ids.first().unwrap(), 1);
assert_eq!(*ids.last().unwrap(), 500);
}
#[test]
fn without_rowid_sql_detects_the_clause() {
assert!(without_rowid_sql(
"CREATE TABLE kv(k TEXT PRIMARY KEY, v TEXT) WITHOUT ROWID"
));
assert!(without_rowid_sql(
"CREATE TABLE kv(k TEXT PRIMARY KEY, v TEXT) without rowid"
));
assert!(!without_rowid_sql(
"CREATE TABLE t(id INTEGER PRIMARY KEY, n TEXT)"
));
assert!(!without_rowid_sql(
"CREATE TABLE t(\"without rowid\" TEXT, x INT)"
));
}
#[test]
fn is_autoincrement_detects_only_the_real_clause() {
assert!(is_autoincrement(
"CREATE TABLE students(id INTEGER PRIMARY KEY AUTOINCREMENT, name TEXT)"
));
assert!(is_autoincrement(
"create table t( id integer primary key autoincrement )"
));
assert!(!is_autoincrement(
"CREATE TABLE students(id INTEGER PRIMARY KEY, name TEXT)"
));
assert!(!is_autoincrement(
"CREATE TABLE kv(k INTEGER PRIMARY KEY AUTOINCREMENT, v TEXT) WITHOUT ROWID"
));
assert!(!is_autoincrement(
"CREATE TABLE t(\"autoincrement\" INTEGER PRIMARY KEY, x INT)"
));
assert!(!is_autoincrement(
"CREATE TABLE t(id INTEGER PRIMARY KEY, note TEXT DEFAULT 'autoincrement')"
));
assert!(!is_autoincrement(
"CREATE TABLE t(id INTEGER AUTOINCREMENT, name TEXT)"
));
}
#[test]
fn sqlite_sequence_reads_present_absent_and_multi() {
let plain = Database::open(crate::rebuild::build_recovered_db_tables(&[
crate::rebuild::RecoveredTable {
name: "plain".to_string(),
columns: vec!["c0".to_string()],
rows: vec![vec![Value::Integer(1)]],
},
]))
.expect("minted db opens");
assert!(
plain.sqlite_sequence().is_empty(),
"no AUTOINCREMENT table ⟹ empty sqlite_sequence map"
);
let auto =
Database::open(include_bytes!("../../tests/data/drop_recreate/b_autoinc.db").to_vec())
.expect("open b_autoinc.db");
let seq = auto.sqlite_sequence();
assert_eq!(seq.get("students"), Some(&5), "students high-water = 5");
let upd = Database::open(
include_bytes!("../../tests/data/drop_recreate/upd_autoinc.db").to_vec(),
)
.expect("open upd_autoinc.db");
assert_eq!(upd.sqlite_sequence().get("t"), Some(&5), "t high-water = 5");
}
#[test]
fn schema_sql_reads_current_name_to_create_sql() {
let auto =
Database::open(include_bytes!("../../tests/data/drop_recreate/b_autoinc.db").to_vec())
.expect("open b_autoinc.db");
let schema = auto.schema_sql();
let sql = schema.get("students").expect("students present");
assert!(
sql.contains("AUTOINCREMENT"),
"current CREATE SQL carried verbatim: {sql}"
);
}
#[test]
fn prior_snapshot_schema_sql_reads_prior_create_sql() {
let main = include_bytes!("../../tests/data/drop_recreate/b_journal_altered.db").to_vec();
let journal = include_bytes!("../../tests/data/drop_recreate/b_journal_altered.db-journal");
let db = Database::open(main).expect("open b_journal_altered.db");
let prior = db
.rollback_prior(journal)
.expect("rollback_prior parses the PERSIST journal");
let prior_sql = prior.schema_sql();
let prior_students = prior_sql.get("students").expect("prior students present");
assert!(
!prior_students.contains("extra"),
"prior CREATE SQL lacks the ALTER-added column: {prior_students}"
);
let current = db.schema_sql();
assert_ne!(
current.get("students"),
prior_sql.get("students"),
"prior vs current CREATE SQL differ (the ALTER)"
);
}
#[test]
fn prior_snapshot_schema_sql_dml_only_matches_current() {
let main = include_bytes!("../../tests/data/drop_recreate/b_journal_dml.db").to_vec();
let journal = include_bytes!("../../tests/data/drop_recreate/b_journal_dml.db-journal");
let db = Database::open(main).expect("open b_journal_dml.db");
let prior = db
.rollback_prior(journal)
.expect("rollback_prior parses the PERSIST journal");
assert_eq!(
db.schema_sql().get("students"),
prior.schema_sql().get("students"),
"DML-only ⟹ prior and current CREATE SQL are identical"
);
}
}