jerboa-sqlite

A SQLite3-compatible database engine implemented from scratch in Jerboa Scheme — not a binding over libsqlite3, but a reimplementation of the engine: tokenizer, parser, value/type system, VDBE-style virtual machine, B-tree storage, pager, and the sqlite3_*-shaped API.

Pinned compatibility target: SQLite 3.54.0 (the upstream checkout in ../sqlite). The thin FFI wrapper in ../jerboa-sqlite-ffi is used only as a differential-test oracle, never as a runtime dependency.

Status

Built in phases (see OPUS_4_8_SQLITE_HANDOFF.md for the full ladder).

Phase	Scope	State
0	Scaffold, value/type foundations, oracle harness	✅ done
1	Values, tokenizer, parser, in-memory evaluator	✅ done
2	SQLite file reader (header, records, B-tree, schema)	✅ done
3	Read-only SELECT over tables (WHERE/ORDER/LIMIT/DISTINCT/joins)	✅ done
4	Write path: CREATE TABLE/CTAS / CREATE/DROP INDEX / INSERT / UPDATE / DELETE, NOT NULL, freelist basics (experimental)	✅ done
7a	Aggregates + GROUP BY/HAVING; BETWEEN/IN/LIKE/GLOB/COLLATE + scalar functions; compound UNION/INTERSECT/EXCEPT; derived tables, non-recursive CTEs, WITH on INSERT SELECT, and views	✅ done
next	Remaining foreign-key edge cases, index planner, locking/fsync/WAL hardening	planned

What works today: the full value/type system (NULL/INTEGER/REAL/TEXT/BLOB with SQLite truthiness, numeric coercion, storage-class comparison ordering and three-valued logic); a complete SQLite tokenizer (SQLite keywords, all literal and operator forms); a precedence-correct expression parser; and an evaluator covering arithmetic (with integer-overflow→real and /0→NULL), bitwise ops, CAST affinity, SQLite comparison affinity for direct table columns and rowid, CASE, COLLATE BINARY/NOCASE/RTRIM including declared column defaults for direct table scans, bind parameters, and a core set of scalar functions. The prepared-statement API covers prepare/step/reset/finalize, generic and typed bind helpers, column accessors, opt-in batch stepping helpers (sqlite-step-batch!, sqlite-step-batch-vector!, and sqlite-step-batch-vector-typed!), sqlite-exec/sqlite-query, change counters, read-only/open-v2 modes, and connection error accessors. It runs table-less SELECTs in memory, verified expression-by-expression against the SQLite 3.54.0 reference in the differential test lane. It also reads real SQLite database files — parsing the header, records, and table B-trees (including interior pages and overflow chains) — so SELECT <cols/*> FROM <table> returns rows from files written by upstream SQLite, byte-for-byte verified against the reference. Top-level, compound, derived, scalar, and CTE VALUES queries are supported. The write path creates rowid tables (including AUTOINCREMENT/sqlite_sequence), materializes CREATE TABLE ... AS SELECT/VALUES, supports STRICT rowid tables and STORED/VIRTUAL generated columns, stores/query schema-only views, supports ALTER TABLE ... RENAME TO ..., ALTER TABLE ... ADD COLUMN, and ALTER TABLE ... RENAME COLUMN ... TO ..., plus added-column CHECK validation and added-column REFERENCES/default validation, safe DROP COLUMN cases, and creates user index roots (CREATE INDEX, CREATE UNIQUE INDEX, DROP INDEX) while maintaining those indexes across INSERT/UPDATE/DELETE for files that pass upstream PRAGMA integrity_check, including INSERT ... SELECT, WITH-fed INSERT SELECT, UPDATE ... FROM, simple UPSERT, DML RETURNING, and multi-page user indexes; low-level table rowid lookups and index B-tree scans handle upstream overflow payloads, while multi-level and overflow index writes pass upstream integrity checks. The planner can use simple rowid equality point lookups, mandatory INDEXED BY, simple single-table constrained index scans, and covered-projection index scans; broader cost-based planning is still future work. Foreign-key checks are available when PRAGMA foreign_keys=ON for ordinary rowid tables, including parent-key mismatch validation and immediate ON DELETE/ON UPDATE RESTRICT/CASCADE/SET NULL/SET DEFAULT actions, including DROP TABLE's implicit delete behavior; DEFERRABLE INITIALLY DEFERRED constraints are checked at COMMIT or outermost savepoint RELEASE, and PRAGMA defer_foreign_keys can defer otherwise-immediate checks for the current transaction. File commits use a simple DELETE-mode rollback journal and recover a leftover hot journal on open; full locking/fsync and WAL behavior are still future work.

Layout

src/jsqlite/        production engine modules (never touch libsqlite3)
  constants.ss        result codes, open flags, datatype tags (SQLite 3.54.0)
  error.ss            error condition type + result-code plumbing
  value.ss            values, storage classes, truthiness, coercions
  keywords.ss         SQL keyword table
  tokenize.ss         hand-coded tokenizer (mirrors src/tokenize.c)
  ast.ss parse.ss     AST records + precedence-climbing parser
  eval.ss             expression evaluator (SQLite semantics)
  record.ss page.ss   varint/record codec; file header + page geometry
  btree.ss            table/index B-tree read cursors (interior/leaf, overflow, rowid lookup)
  schema.ss           sqlite_schema reader + CREATE TABLE column resolution
  exec.ss             SELECT executor (joins, WHERE, ORDER BY, LIMIT, DISTINCT)
  writer.ss           mutable DB image: header, page alloc, freelist, table/index rebuilds
  dml.ss              CREATE TABLE/INDEX / INSERT / UPDATE / DELETE execution
  api.ss              open/prepare/step/column/finalize (sqlite3_*-shaped)
tools/              test-only tooling
  oracle-runner.ss    differential oracle: jsqlite vs jerboa-sqlite-ffi reference
tests/
  unit/               per-module unit tests
  diff/               differential tests against the reference engine
  fileformat/         file round-trip tests (later phases)
  upstream/           adapted upstream Tcl-test cases (later phases)
docs/
  architecture.md     module map + SQLite pipeline
  test-plan.md        the five test lanes + normalization rules
  compatibility-matrix.md   feature/status tracking

Build & test

Requires jerbuild on PATH. The differential lane additionally requires the ../jerboa-sqlite-ffi reference checkout (a C compiler + system libsqlite3); it is skipped if that checkout is absent.

make unit     # unit tests only (no libsqlite3 needed)
make diff     # differential tests vs the reference oracle
make test     # unit + diff (acceptance gate)
make build    # compile-check all production modules

Design notes

• Values are native Scheme types plus a single sql-null sentinel: INTEGER = exact integer, REAL = flonum, TEXT = string, BLOB = bytevector. SQLite has no boolean type; TRUE/FALSE are integers 1/0, and NULL drives three-valued logic.
• Compatibility is tracked on three surfaces — SQL behavior, on-disk file format, and API shape — each with its own tests. See docs/test-plan.md.
• The engine mirrors SQLite's architecture (SQL → tokenize → parse → codegen → VDBE → B-tree → pager) so that hard compatibility cases (affinity, the file format, transactions) have a place to live correctly.