///|
/// SQLite file format 3 reader. All offsets, lengths and page ownership are
/// checked before use; no native SQLite or host SQL/parser is involved.
priv struct DiskCursor {
data : Bytes
mut position : Int32
end : Int32
}
///|
priv struct DiskRow {
key : Int64
values : Array[Value]
}
///|
priv struct SQLiteFile {
data : Bytes
page_size : Int32
usable : Int32
pages : Int32
encoding : Int32
format : Int32
owners : Array[Int32]
parents : Array[Int32]
}
///|
fn DiskCursor::take(c : DiskCursor, n : Int32) -> BytesView raise SqlError {
guard n >= 0 && n <= c.end - c.position else {
fail("corrupt SQLite: truncated field")
}
let bytes = c.data[c.position:c.position + n]
c.position += n
bytes
}
///|
fn DiskCursor::byte(c : DiskCursor) -> Int32 raise SqlError {
c.take(1)[0].to_int()
}
///|
fn DiskCursor::u16(c : DiskCursor) -> Int32 raise SqlError {
(c.byte() << 8) | c.byte()
}
///|
fn DiskCursor::word(c : DiskCursor) -> Int64 raise SqlError {
let mut result = 0L
for _ in 0..<4 {
result = (result << 8) | c.byte().to_int64()
}
result
}
///|
/// The ninth byte contributes all eight bits (including negative rowids).
fn DiskCursor::varint(c : DiskCursor) -> UInt64 raise SqlError {
let mut result = 0UL
for _ in 0..<8 {
let b = c.byte()
result = (result << 7) | (b & 127).to_uint64()
if b < 128 {
return result
}
}
(result << 8) | c.byte().to_uint64()
}
///|
fn disk_int(value : UInt64, limit : Int32) -> Int32 raise SqlError {
guard value <= limit.to_uint64() else {
fail("corrupt SQLite: length/resource limit")
}
value.to_int()
}
///|
fn disk_cursor(
data : Bytes,
offset : Int32,
end : Int32,
) -> DiskCursor raise SqlError {
guard offset >= 0 && end >= offset && end <= data.length() else {
fail("corrupt SQLite: invalid offset")
}
{ data, position: offset, end, }
}
///|
fn SQLiteFile::page_number(
file : SQLiteFile,
n : Int64,
) -> Int32 raise SqlError {
guard n >= 1L && n <= file.pages.to_int64() else {
fail("corrupt SQLite: invalid page number")
}
n.to_int()
}
///|
/// Roles match SQLite pointer-map types. 6 is the pointer-map page itself.
fn SQLiteFile::claim(
file : SQLiteFile,
page : Int32,
role : Int32,
parent : Int32,
) -> Unit raise SqlError {
guard page >= 1 && page <= file.pages && file.owners[page] == 0 else {
fail("corrupt SQLite: cyclic/shared page ownership")
}
file.owners[page] = role
file.parents[page] = parent
}
///|
fn SQLiteFile::at(
file : SQLiteFile,
page : Int32,
offset : Int32,
) -> DiskCursor raise SqlError {
guard page >= 1 && page <= file.pages && offset >= 0 && offset <= file.usable else {
fail("corrupt SQLite: page offset")
}
disk_cursor(
file.data,
(page - 1) * file.page_size + offset,
(page - 1) * file.page_size + file.usable,
)
}
///|
fn sqlite_header(data : Bytes) -> SQLiteFile raise SqlError {
guard data.length() >= 100 &&
data.length() <= 67108864 &&
data[0:16] == b"SQLite format 3\x00" else {
fail("invalid SQLite image header/size")
}
let c = disk_cursor(data, 16, 100)
let size = c.u16()
let page_size = if size == 1 { 65536 } else { size }
guard page_size >= 512 &&
page_size <= 65536 &&
(page_size & (page_size - 1)) == 0 &&
data.length() % page_size == 0 else {
fail("corrupt SQLite: page size/truncated image")
}
let write_version = c.byte()
let read_version = c.byte()
guard (write_version == 1 || write_version == 2) &&
(read_version == 1 || read_version == 2) else {
fail("unsupported SQLite file version")
}
let usable = page_size - c.byte()
guard usable >= 480 && c.byte() == 64 && c.byte() == 32 && c.byte() == 32 else {
fail("corrupt SQLite: page reserve/payload fractions")
}
let pages = data.length() / page_size
let change = c.word()
let declared = c.word()
let valid = disk_cursor(data, 92, 100).word()
guard declared == 0L || change != valid || declared == pages.to_int64() else {
fail("corrupt SQLite: declared page count")
}
let format = disk_cursor(data, 44, 48).word()
let encoding = disk_cursor(data, 56, 60).word()
guard format >= 1L && format <= 4L && encoding >= 1L && encoding <= 3L else {
fail("unsupported SQLite schema format/text encoding")
}
guard data[72:92].to_array().all(b => b == b'\x00') else {
fail("unsupported SQLite header extension")
}
{
data,
page_size,
usable,
pages,
encoding: encoding.to_int(),
format: format.to_int(),
owners: Array::make(pages + 1, 0),
parents: Array::make(pages + 1, 0),
}
}
///|
fn SQLiteFile::text(
file : SQLiteFile,
bytes : BytesView,
) -> String raise SqlError {
try {
if file.encoding == 1 {
@utf8.decode(bytes, ignore_bom=false)
} else {
@utf16.decode(
bytes,
ignore_bom=false,
endianness=if file.encoding == 2 { Little } else { Big },
)
}
} catch {
_ => fail("corrupt SQLite: malformed text encoding")
}
}
///|
fn SQLiteFile::record(
file : SQLiteFile,
bytes : Bytes,
) -> Array[Value] raise SqlError {
let header = disk_cursor(bytes, 0, bytes.length())
let header_size = disk_int(header.varint(), bytes.length())
guard header_size >= header.position else {
fail("corrupt SQLite: record header size")
}
let header = { ..header, end: header_size, }
let body = disk_cursor(bytes, header_size, bytes.length())
let values : Array[Value] = []
while header.position < header.end {
guard values.length() < 2000 else {
fail("SQLite record column resource limit")
}
let serial = disk_int(header.varint(), 134217741)
let value : Value = if serial == 0 {
Null
} else if serial == 8 || serial == 9 {
guard file.format >= 4 else {
fail("corrupt SQLite: serial type in legacy format")
}
Integer((serial - 8).to_int64())
} else if serial >= 1 && serial <= 7 {
let width = match serial {
1 => 1
2 => 2
3 => 3
4 => 4
5 => 6
_ => 8
}
let mut bits = 0UL
for b in body.take(width) {
bits = (bits << 8) | b.to_uint64()
}
if serial == 7 {
let real = bits.reinterpret_as_double()
guard !real.is_nan() else { fail("unsupported SQLite non-finite REAL") }
Real(real)
} else {
let shift = 64 - width * 8
Integer(bits.reinterpret_as_int64() << shift >> shift)
}
} else if serial >= 12 {
let bytes = body.take((serial - 12) / 2)
if serial % 2 == 0 {
Blob(bytes.to_owned())
} else {
Text(file.text(bytes))
}
} else {
fail("corrupt SQLite: reserved serial type")
}
values.push(value)
}
guard body.position == body.end else {
fail("corrupt SQLite: trailing record bytes")
}
values
}
///|
fn SQLiteFile::payload(
file : SQLiteFile,
page : Int32,
cursor : DiskCursor,
size : Int32,
index : Bool,
) -> Bytes raise SqlError {
guard size >= 1 && size <= 67108864 else {
fail("corrupt SQLite: payload size")
}
let maximum = if index {
(file.usable - 12) * 64 / 255 - 23
} else {
file.usable - 35
}
let minimum = (file.usable - 12) * 32 / 255 - 23
let proposed = minimum + (size - minimum) % (file.usable - 4)
let local_size = if size <= maximum {
size
} else if proposed <= maximum {
proposed
} else {
minimum
}
let buffer = @buffer.Buffer()
buffer.write_bytes(cursor.take(local_size).to_owned())
let mut remaining = size - local_size
if remaining > 0 {
let mut next = file.page_number(cursor.word())
let mut previous = page
let mut first = true
while remaining > 0 {
file.claim(next, if first { 3 } else { 4 }, previous)
let overflow = file.at(next, 0)
let following = overflow.word()
let count = remaining.min(file.usable - 4)
buffer.write_bytes(overflow.take(count).to_owned())
remaining -= count
previous = next
first = false
if remaining > 0 {
next = file.page_number(following)
} else {
guard following == 0L else {
fail("corrupt SQLite: excess overflow chain")
}
}
}
}
buffer.to_bytes()
}
///|
/// In-order traversal includes records on index interior pages (WITHOUT ROWID).
fn SQLiteFile::walk(
file : SQLiteFile,
page : Int32,
index : Bool,
parent : Int32,
depth : Int32,
output : Array[DiskRow],
) -> Int32 raise SqlError {
guard depth <= 32 else { fail("SQLite B-tree depth resource limit") }
file.claim(page, if parent == 0 { 1 } else { 5 }, parent)
let offset = if page == 1 { 100 } else { 0 }
let header = file.at(page, offset)
let kind = header.byte()
guard (if index { kind == 2 || kind == 10 } else { kind == 5 || kind == 13 }) else {
fail("corrupt SQLite: B-tree page type")
}
let interior = kind == 2 || kind == 5
let mut free = header.u16()
let count = header.u16()
let content = header.u16()
let content = if content == 0 && file.page_size == 65536 {
65536
} else {
content
}
let fragments = header.byte()
let right = if interior { file.page_number(header.word()) } else { 0 }
let pointers_end = header.position - (page - 1) * file.page_size + count * 2
guard pointers_end <= content && content <= file.usable && fragments <= 60 else {
fail("corrupt SQLite: B-tree header/cell array")
}
let spans : Array[(Int32, Int32)] = []
let mut height = -1
let mut previous_separator : Int64? = None
for _ in 0..= content && pointer < file.usable else {
fail("corrupt SQLite: cell pointer")
}
let cell = file.at(page, pointer)
let child = if interior { file.page_number(cell.word()) } else { 0 }
if interior {
let start = output.length()
let h = file.walk(child, index, page, depth + 1, output)
guard height < 0 || height == h else {
fail("corrupt SQLite: unbalanced B-tree")
}
height = h
if !index {
guard output.length() > start else {
fail("corrupt SQLite: empty table subtree")
}
if previous_separator is Some(key) {
guard output[start].key > key else {
fail("corrupt SQLite: table separator range")
}
}
}
}
if kind == 5 {
let key = cell.varint().reinterpret_as_int64()
guard previous_separator is None ||
(previous_separator is Some(previous) && previous < key) else {
fail("corrupt SQLite: unordered table separators")
}
guard !output.is_empty() && output[output.length() - 1].key <= key else {
fail("corrupt SQLite: table separator")
}
previous_separator = Some(key)
} else {
let size = disk_int(cell.varint(), 67108864)
let key = if index { 0L } else { cell.varint().reinterpret_as_int64() }
if !index && !output.is_empty() {
guard output[output.length() - 1].key < key else {
fail("corrupt SQLite: unordered/duplicate rowid")
}
}
let payload = file.payload(page, cell, size, index)
output.push({ key, values: file.record(payload), })
guard output.length() <= 100000 else {
fail("SQLite B-tree row resource limit")
}
}
spans.push((pointer, cell.position - (page - 1) * file.page_size))
}
if interior {
let start = output.length()
let h = file.walk(right, index, page, depth + 1, output)
guard height < 0 || height == h else {
fail("corrupt SQLite: unbalanced right subtree")
}
height = h
if !index && previous_separator is Some(key) {
guard output.length() > start && output[start].key > key else {
fail("corrupt SQLite: right separator range")
}
}
}
// Validate both cell extents and freeblock chains, including overlaps.
while free != 0 {
guard free >= content && free + 4 <= file.usable else {
fail("corrupt SQLite: freeblock pointer")
}
let block = file.at(page, free)
let next = block.u16()
let size = block.u16()
guard size >= 4 &&
size <= file.usable - free &&
(next == 0 || next >= free + size) else {
fail("corrupt SQLite: freeblock chain")
}
spans.push((free, free + size))
free = next
}
spans.sort_by((a, b) => a.0.compare(b.0))
let mut end = content
let mut actual_fragments = 0
for span in spans {
guard span.0 >= end && span.1 > span.0 && span.1 <= file.usable else {
fail("corrupt SQLite: overlapping cells/freeblocks")
}
let gap = span.0 - end
guard gap <= 3 else { fail("corrupt SQLite: unlisted free space") }
actual_fragments += gap
end = span.1
}
let gap = file.usable - end
guard gap <= 3 && actual_fragments + gap == fragments else {
fail("corrupt SQLite: fragmented space count")
}
if interior {
height + 1
} else {
0
}
}
///|
fn SQLiteFile::tree(
file : SQLiteFile,
root : Int32,
index : Bool,
) -> Array[DiskRow] raise SqlError {
let rows : Array[DiskRow] = []
ignore(file.walk(root, index, 0, 0, rows))
rows
}
///|
fn SQLiteFile::freelist(file : SQLiteFile) -> Unit raise SqlError {
let header = disk_cursor(file.data, 32, 40)
let mut next = header.word()
let expected = header.word()
guard expected <= file.pages.to_int64() else {
fail("corrupt SQLite: freelist count")
}
let mut total = 0
while next != 0L {
let page = file.page_number(next)
file.claim(page, 2, 0)
total += 1
let trunk = file.at(page, 0)
next = trunk.word()
let count = trunk.word()
guard count <= ((file.usable - 8) / 4).to_int64() else {
fail("corrupt SQLite: freelist trunk size")
}
for _ in 0.. Unit raise SqlError {
if disk_cursor(file.data, 52, 56).word() == 0L {
return
}
let interval = file.usable / 5 + 1
for page = 2; page <= file.pages; page = page + interval {
file.claim(page, 6, 0)
}
}
///|
fn SQLiteFile::validate_pages(file : SQLiteFile) -> Unit raise SqlError {
let mapped = disk_cursor(file.data, 52, 56).word() != 0L
let interval = file.usable / 5 + 1
for page in 1..<=file.pages {
guard file.owners[page] != 0 else {
fail("corrupt SQLite: unreferenced page")
}
if !mapped || page == 1 || file.owners[page] == 6 {
continue
}
let map_page = 2 + (page - 2) / interval * interval
let entry = file.at(map_page, (page - map_page - 1) * 5)
guard entry.byte() == file.owners[page] &&
entry.word() == file.parents[page].to_int64() else {
fail("corrupt SQLite: pointer-map backlink")
}
}
}