diff --git a/CLAUDE.md b/CLAUDE.md index 6c58de27ba..93e50343d2 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -115,7 +115,7 @@ cargo run < demos/demo_negation.txt - `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value` - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES` - `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs - - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) + - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_update` (copy-on-write inserts and deletes; an emptied leaf or node leaves its parent, an emptied tree is root 0; #550) and `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - `value_pages.rs`: append-only value pages for strings over 64 bytes - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) @@ -129,6 +129,7 @@ cargo run < demos/demo_negation.txt 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#.`, else PRS-081 (#594) + - `parser/statement.rs`: `transact`/`retract` read one fact at a time (#550): `kind_of` dispatches on the first two tokens; one pass keeps today's error order (phases 1 tokens … 6 valid windows, the earliest phase's first error, phase 3 in today's check order); `read_statement` (pass 1) keeps at most `TX_CHUNK_FACTS` materialised facts and the offset after the last, and returns phase 5–6 errors from `Statement::facts`, which runs pass 2 from that offset for a larger statement; `set_tx_chunk_facts` for tests. The `Parser` reads tokens on demand from a `Lexer` (`keep` off checks structure without holding it); `parse_transact`/`parse_retract` remain under `cfg(test)` for the differential tests - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 15 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) - `executor.rs`: Query executor — temporal filter (tx-time → net-assert → valid-time), not/not-join post-filter - `matcher.rs`: Pattern matching with variable unification; `edn_to_value`, `edn_to_entity_id` @@ -206,7 +207,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1725 tests** (1711 passing, 14 ignored; unit + integration + doc). +**1735 tests** (1721 passing, 14 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index ca9781cda4..33f1796894 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-21 with `cargo test --quiet` -**Result**: 1,711 passing tests and 14 ignored tests (1,725 total) +**Result**: 1,721 passing tests and 14 ignored tests (1,735 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628). Tests in `tests/not_join_test.rs` check that recursion through a rule with `not`, `not-join` or `or`, directly or through another rule, returns every row along a chain, and that the `not` still removes the rows it should; evaluator unit tests check that such recursion stops at its fixpoint that `max_iterations` and `max_results` end one that does not with INT-020, and that `max_results` counts the facts every pass derives, not only the mixed rule's (#633). @@ -29,6 +29,8 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Fact arity** (`tests/error_codes_prs_test.rs`, 2 tests; #649): a fact of five or six elements, with or without a map 4th, fails with `PRS-108`, and a transaction holding one stores none of its facts. - **Parser tightening** (`tests/error_codes_prs_test.rs`, 10 tests; #651): `PRS-109` to `PRS-114` from their inputs (an unterminated string, a `:` with no name, `(query [])`, an empty `:find`/`:where`/`:with` in each position, an unknown query keyword with and without a value after it, a constant rule head argument); `PRS-061` for a value after each query option; `PRS-097` for a clause list headed by an operator or a variable, also inside `not`, `or` and a rule body; `PRS-105` for a rule named by a variable or an operator; `PRS-025`/`PRS-029`/`PRS-063` for an aggregate, window or expression named by a variable; the forms next to them still run (an option followed by a keyword, `(- ?n 1)`, a zero-argument rule). Thirteen new `tests/grammar/invalid/syntax/` fixtures. - **Parser vs grammar** (`src/query/datalog/parser/verifier.rs`, 4 tests; #643): about 1.07M lexical strings and 555K structural inputs at the default bound (7.6M at `MINIGRAF_GRAMMAR_BOUND=4`) checked against `tests/grammar/grammar.pest`; known drift by cause in `KNOWN_DRIFT` (none left: #650, #651 fixed), semantic codes with witnesses in `SEMANTIC`. +- **Statement reader** (`src/query/datalog/parser/statement.rs`, 6 tests; `tests/read_only_open_test.rs`, 1 test; #550): every `transact`/`retract` built from up to three of 34 statement tokens (balanced or not) in 10 templates, and a corpus of statements with errors in several phases (a later lexer error over an earlier structure error, a later structure error over an earlier fact error, phase 3 in today's check order, too-deep nesting inside a fact and an extra element), give the same command or error through the reader as through the whole-input parser, and the same facts or error through the write path at chunk sizes 1, 2, 3 and the default; the sequences raise 24 distinct codes and reach pass 2; pass 2 resumes just after the last kept fact; materialisation and window errors come with the facts, after `API-014` on a read-only database; the parser's `keep` flag checks structure and holds nothing; lexer offsets are byte offsets. +- **Copy-on-write delete** (`src/storage/btree.rs`, 3 tests; #550): `cow_update` against a `BTreeSet` model over random insert and delete batches (samples, contiguous runs that empty leaves and subtrees, a deleted key inserted again) on trees of 0 to 60,000 keys, each step walked as `verify` walks a tree, every page of the old tree unchanged, `freed` exactly the old nodes dropped; deleting everything, front half first, gives root 0 and root 0 takes inserts again; a missing, unsorted or repeated delete, or a delete on root 0, is `INT-049`. - **Grammar page** (`tests/grammar_doc.rs`, 10 tests; #643): `docs/GRAMMAR.md` matches the EBNF rendered from `tests/grammar/grammar.pest`; each rendering rule (sequence, choice and grouping, names and builtins, `SOI`/`EOI` dropped, lookaheads as comments, bounded repetition, quoting, token marks, section titles, line breaking, the whitespace note and the comment note it joins) on a small grammar. - **Plan independence** (`tests/plan_independence_test.rs`, 15 tests, `test-oracle` feature only; #596): a matrix of queries (joins in both text orders, cross products, keyword and ref, floats, long strings, filter and binding expressions, recursive rules and rules with `not`, `or`/`or-join` including the #250 short-circuit shapes, placed and deferred `not`/`not-join`, aggregates, `:as-of`, `:valid-at`, `:any-valid-time`), in memory and on file after a checkpoint and a reopen, through `execute` and a cursor, gives the same bag of rows with clause reordering on and off (`minigraf::__reorder`) and with the engine's negation bodies and `or` branches chosen, forced hashed and forced correlated (`minigraf::__subplans`, #546; the matrix gains #546's negation and disjunction shapes); #596's example and the unification cases (an expression whose output is its input, two expressions on one variable, integer vs float, `-0.0` vs `0.0`); and `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds, nested and in rule bodies (#620); and expressions, chains of them and a `not` after them, reading a variable only an `or` binds, in queries, with rules and in rule bodies (#625; `tests/disjunction_test.rs` repeats them without `test-oracle`). Under `test-oracle` the model-based and property tests also rerun every generated query with reordering off (the property test also with negation bodies and `or` branches forced hashed; it generates `or` / `or-join` over bound variables, #546). Unit tests cover `branch_outer_reads` (#620), the planner deferring an expression only an `or` can bind for, after the expressions placed before it and ahead of the deferred `not`s (#625), `apply_expr` (equal, different, integer vs float, NaN, `-0.0`/`0.0` with and without replacing, keyword vs ref both ways, a failing expression), `Binders::expression`, the switch (source order kept, per thread, restored on drop), and the engine planner's `Bind` modes and build side with the switch off; the engine's join matrix gains six unification shapes. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). diff --git a/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md b/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md new file mode 100644 index 0000000000..c1b5cf131e --- /dev/null +++ b/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md @@ -0,0 +1,114 @@ +# Streaming transactions (#550) — Plan + +Spec: `docs/superpowers/specs/2026-10-21-streaming-transactions-design.md` (merged as #683), +called "the spec" below. PRs target `v3`, merge commits. None uses a closing keyword for #473 or +#550; #550 closes by hand after PR 3. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–9: lexer, statement reader (pass 1 and pass 2), `cow_update` (spec §3, §6) | `feat/550-parser` | +| 2 | 10–15: `PageAllocator::release`, large single statements, WAL guard, open-time dirty rule, crash and fault tests, 1M acceptance (spec §4) | `feat/550-large-statements` | +| 3 | 16–21: statement bases, snapshot reads in a `WriteTransaction`, measurement, `TX_CHUNK_FACTS`, docs (spec §5, §7, §8.2) | `feat/550-statement-bases` | + +Each PR leaves `v3` with no unused code outside `cfg(test)` and updates the test counts. Only +PR 3 changes `CHANGELOG.md` and the docs site: PRs 1 and 2 change no behaviour a user sees +(PR 2 changes when a large transaction is written, documented with PR 3). + +## Design decisions not fixed by the spec + +1. **One `Parser`, over a `Lexer`.** `Lexer { input: &str, pos: usize, error: Option }` + yields one `Token` at a time; after its first error it yields nothing more and keeps the + error. `Parser` reads from a `Lexer` instead of a `Vec`, with one token of lookahead. + So every command reads tokens on demand. `parse_edn` and the non-statement path of + `parse_datalog_command` keep today's errors by finishing the lexer before they report: a + lexer error anywhere in the input wins over a structure error, as `tokenize` before + `Parser` gave. `tokenize` stays as `Lexer::new(input).collect()` for tests (`cfg(test)`). + One non-generic `Parser` keeps the binary from carrying two copies. +2. **A `keep` flag on `Parser`.** With `keep` off, `parse_value` checks structure exactly as + with it on but vectors, lists and maps hold no elements. The statement reader skips every + element of a statement other than the facts and the transaction-level map this way, so an + extra element (an error, `PRS-075`/`PRS-076`) is never held whole either. +3. **Where the reader lives.** `src/query/datalog/parser/statement.rs`, a child module of the + parser like `verifier.rs`, so it reads the lexer and `Parser` without widening their + visibility. It holds the per-fact phase 4 checks (`transact_pattern`, `retract_pattern`, + moved out of `parse_transact`/`parse_retract`) and phase 5, `materialize_assertion` and + `materialize_retraction_of` (moved from `db.rs`; `Minigraf::materialize_transaction` and + `materialize_retraction` stay for `BrowserDb` and loop over them). +4. **Dispatch.** `parse_datalog_command` lexes the first two tokens. `(` then the symbol + `transact` or `retract` goes to the statement reader; anything else, including a lexer + error in those two tokens, takes today's path. The statement reader builds the same + `DatalogCommand::Transact`/`Retract` for `parse_datalog_command`'s callers (`BrowserDb`, + `Minigraf::query`, `prepare`), holding every `Pattern` as today. Writes use + `read_statement` instead, which keeps no `Pattern`s. +5. **Phase 3 order.** The spec says "first error in text order" within a phase. Phase 3 is + not in text order today: `PRS-075` (extra elements, after the facts) is checked before + `PRS-042` (facts not a vector). The reader records what phase 3 needs (element count, the + map's result, the facts element's kind) and runs today's checks in today's order at the + end of the input. +6. **Phases 5 and 6 are reported when the facts are taken.** `read_statement` returns `Err` + for a phase 1–4 error and a `Statement` otherwise; a phase 5 or 6 error is kept in the + `Statement` and returned by `Statement::facts`/`Statement::chunks`. `Minigraf::execute` + checks `reject_if_read_only` between the two, as it does between parsing and + materialising today, so a statement on a read-only database still gets `API-014` before + `INT-002`. +7. **Pass 1 keeps `TX_CHUNK_FACTS` facts, not `TX_CHUNK_FACTS + 1`.** It records the byte + offset after the last kept fact and marks the statement large when one more fact follows. + Pass 2 resumes there. Same result, and the acceptance bound "at most `TX_CHUNK_FACTS` + materialised facts" holds exactly. +8. **`TX_CHUNK_FACTS`** is `16_384` until PR 3's measurement. `cfg(test)` (and, from PR 2, + `test-oracle`) gets a thread-local override `set_tx_chunk_facts`. +9. **In PR 1 every statement takes the small path.** `Statement::facts` returns the kept facts + for a small statement and, for a large one, runs pass 2 and appends every chunk. So pass 2 + runs on every statement over `TX_CHUNK_FACTS` facts, with today's memory, and the + differential test drives it with the override. +10. **`cow_update(root, inserts, deletes, …)`.** Inserts and deletes are routed down the tree + as two sorted runs per child. At a leaf the deletes are applied first (each must be + present, else `INT-049`), then the inserts are merged, so a key deleted and inserted in + one call is kept. A node whose result is empty returns no pieces and its parent drops + the child slot with it: the next child's separator then starts the parent's slot list, + where `write_internal_pieces` already ignores it. An internal node with no children left + returns no pieces too; a root with none gives root 0. `cow_insert` stays as a thin call + of `cow_update` with no deletes. +11. **`PageAllocator::release(id)`** pushes `id` onto the free ids the allocator hands out + next. A released id that is not handed out again joins the new free list in + `finish_free_list`, as every unused free id does today. It moves from PR 1 (spec §9) to + PR 2, its first caller, so PR 1 adds no code only tests call. + +## PR 1 steps + +1. **Lexer.** Turn `tokenize` into `Lexer::next_token`, byte offset `pos`, `Iterator` impl, + `error()`; `tokenize` under `cfg(test)`. Existing tokenizer tests pass unchanged. +2. **Parser over the lexer** (decision 1) with `keep` (decision 2) and a settable `depth`; + `parse_edn` finishes the lexer before reporting. Grammar verifier passes unchanged. +3. **Old path kept for tests.** `parse_transact`/`parse_retract` and an + `old_parse_datalog_command` move under `cfg(test)` (removed with the executor in #551). +4. **Statement reader** (`statement.rs`): the outer list and facts vector by hand, each fact + by `Parser::parse_value`, every other element skipped with `keep` off. One `FirstError` + (phase, error), replaced only by an earlier phase; phases run only while below the + recorded one; a lexer error ends the pass; a structure error leaves only lexing. +5. **`parse_datalog_command`** dispatches statements to the reader (decision 4). +6. **Pass 1 and pass 2.** `read_statement(input, tx_id) -> Result`: phases 5–6 per + fact, kept facts, resume offset. `Statement::facts()` and `Statement::chunks()` (pass 2, + `Iterator>>`); `Statement::is_retract()`, `is_large()`. +7. **Callers.** `Minigraf::execute` and `WriteTransaction::execute` use `read_statement` for + statements and `parse_datalog_command` for the rest; their phase 6 and 7 checks stay. + `WriteTransaction` computes its staging `tx_id` before pass 1. +8. **Differential tests.** Old path against the reader, over every token sequence up to 3 + long (balanced or not) from the verifier's tokens plus statement tokens, in statement + templates, and a corpus of multi-error statements: same `DatalogCommand` or same code; + then phases 5–7 against `materialize_*` + `check_valid_windows` + + `check_one_window_per_triple`, with the chunk size forced to 1–3. Unit tests for + the deferred phase 5–6 error, the resume offset, the `keep` flag and the lexer's offset. +9. **`cow_update`** (decision 10): property tests against a `BTreeSet` model over random + insert/delete batches on trees of 1–3 levels, a `verify`-style walk after every step, + every page the old root reaches unchanged, `freed` exactly the dropped old nodes, deletes + of missing, unsorted or repeated keys `INT-049`, delete-everything gives root 0. + +## PR 2 and PR 3 + +Planned in detail when PR 1 is merged, against the code it leaves. PR 2: `PageAllocator::release` (decision 11), spec §4 for +`Minigraf::execute` and a first-statement-large `WriteTransaction` (the chunk writer, +working trees, commit as a checkpoint, rollback, WAL guard, open-time dirty rule), the oracle +hook for the chunk-size override, fault matrix and crash-kill cases, the 1M acceptance test. +PR 3: spec §5 and §7, the measurement on the bench machine, the final `TX_CHUNK_FACTS`, and +the docs listed in spec §9. diff --git a/src/db.rs b/src/db.rs index b4f9480913..3a9d031dd8 100644 --- a/src/db.rs +++ b/src/db.rs @@ -6,7 +6,7 @@ //! - `Minigraf::begin_write()` / `WriteTransaction` for explicit transactions //! - `Minigraf::checkpoint()` for manual WAL compaction -use crate::graph::types::{Fact, TxId, VALID_TIME_FOREVER}; +use crate::graph::types::{Fact, TxId}; /// Sentinel value used in `materialize_transaction` to signal "no explicit `valid_from` /// was provided; use the transaction timestamp at commit time." @@ -27,9 +27,10 @@ use crate::query::datalog::functions::{ AggImpl, AggregateDesc, FunctionRegistry, PredicateDesc, UdfFinaliseFn, UdfOps, UdfStepFn, }; use crate::query::datalog::parser::parse_datalog_command; +use crate::query::datalog::parser::statement::{self, Kind}; use crate::query::datalog::prepared::reject_unbound_slots; use crate::query::datalog::rules::RuleRegistry; -use crate::query::datalog::types::{AttributeSpec, DatalogCommand, Transaction}; +use crate::query::datalog::types::DatalogCommand; use crate::storage::backend::MemoryBackend; #[cfg(not(target_arch = "wasm32"))] use crate::storage::backend::file::{FileBackend, LockMode}; @@ -726,51 +727,57 @@ impl Minigraf { bail_coded!(ErrorCode::Int001); } + if let Some(kind) = statement::kind_of(input) { + return self.execute_statement(input, kind); + } let cmd = parse_datalog_command(input)?; - if let DatalogCommand::Query(q) = &cmd { - reject_unbound_slots(q)?; + match cmd { + DatalogCommand::Query(ref q) => { + reject_unbound_slots(q)?; + // Read-only: no lock needed + let snapshot = self.inner.fact_storage.snapshot()?; + self.read_executor(snapshot).execute(cmd) + } + DatalogCommand::Rule(_) => { + // Rule registration is a write: it mutates the shared + // RuleRegistry, so it runs under write_lock (no WAL needed). + let _ctx = self + .inner + .write_lock + .lock() + .map_err(|_| err_coded!(ErrorCode::Api001))?; + let executor = DatalogExecutor::new_with_rules_and_functions( + self.inner.fact_storage.clone(), + self.inner.rules.clone(), + self.inner.functions.clone(), + ); + executor.execute(cmd) + } + DatalogCommand::Transact(_) | DatalogCommand::Retract(_) => { + Err(err_coded!(ErrorCode::Api002)) + } } + } - // Determine if this is a read-only command (query only). - // Rule registration is treated as a write because it mutates the shared RuleRegistry. - let is_write = matches!( - cmd, - DatalogCommand::Transact(_) | DatalogCommand::Retract(_) | DatalogCommand::Rule(_) - ); - - if is_write { - match &cmd { - DatalogCommand::Transact(_) => self.reject_if_read_only("transact")?, - DatalogCommand::Retract(_) => self.reject_if_read_only("retract")?, - _ => {} - } + /// Execute a `transact` or `retract` with correct WAL-first ordering: + /// 1. Read the statement (pass 1, #550) and materialize its facts (no storage mutation yet) + /// 2. Allocate tx_count + tx_id and stamp facts + /// 3. Write WAL entry FIRST — if this fails, FactStorage is unchanged + /// 4. Apply facts to shared FactStorage + fn execute_statement(&self, input: &str, kind: Kind) -> Result { + // Before the lock, as parsing is: a malformed statement never waits. + // Its materialisation and window errors come with its facts, below. + let statement = statement::read_statement(input, kind, crate::graph::types::tx_id_now())?; + self.reject_if_read_only(kind.name())?; + { let mut ctx = self .inner .write_lock .lock() .map_err(|_| err_coded!(ErrorCode::Api001))?; - // Handle write commands with correct WAL-first ordering for Transact/Retract: - // 1. Materialize facts (no storage mutation yet) - // 2. Allocate tx_count + tx_id and stamp facts - // 3. Write WAL entry FIRST — if this fails, FactStorage is unchanged - // 4. Apply facts to shared FactStorage - // For Rule registration: acquire lock to serialize rule changes, no WAL needed - let (stamped, is_retract) = match &cmd { - DatalogCommand::Transact(tx) => (Minigraf::materialize_transaction(tx)?, false), - DatalogCommand::Retract(tx) => (Minigraf::materialize_retraction(tx)?, true), - DatalogCommand::Rule(_) => { - // Rule registration: execute while holding write_lock to serialize - // rule registry changes (no WAL needed for rules) - let executor = DatalogExecutor::new_with_rules_and_functions( - self.inner.fact_storage.clone(), - self.inner.rules.clone(), - self.inner.functions.clone(), - ); - return executor.execute(cmd); - } - _ => return Err(err_coded!(ErrorCode::Api002)), - }; + let stamped = statement.facts()?; + let is_retract = kind == Kind::Retract; // Before allocating: a rejected transaction takes no tx_count. let tx_id = crate::graph::types::tx_id_now(); crate::graph::storage::check_valid_windows(&stamped, tx_id)?; @@ -817,10 +824,6 @@ impl Minigraf { } else { Ok(QueryResult::Transacted(tx_id)) } - } else { - // Read-only: no lock needed - let snapshot = self.inner.fact_storage.snapshot()?; - self.read_executor(snapshot).execute(cmd) } } @@ -1270,70 +1273,25 @@ impl Minigraf { /// Convert a `Transaction` into a list of assertion `Fact`s (tx_id and tx_count /// are set to 0 as placeholders; they are assigned at commit time). - pub(crate) fn materialize_transaction(tx: &Transaction) -> Result> { - use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; - use crate::query::datalog::types::EdnValue; - - let tx_valid_from = tx.valid_from; - let tx_valid_to = tx.valid_to; - let mut facts = Vec::new(); - - for pattern in &tx.facts { - let entity = - edn_to_entity_id(&pattern.entity).map_err(|e| err_coded!(ErrorCode::Int002, e))?; - - let attr = match &pattern.attribute { - AttributeSpec::Real(EdnValue::Keyword(k)) => k.clone(), - AttributeSpec::Real(_) => bail_coded!(ErrorCode::Api003), - AttributeSpec::Pseudo(_) => bail_coded!(ErrorCode::Api004), - }; - - let value = - edn_to_value(&pattern.value).map_err(|e| err_coded!(ErrorCode::Int003, e))?; - - let valid_from = pattern - .valid_from - .or(tx_valid_from) - .unwrap_or(VALID_FROM_USE_TX_TIME); - let valid_to = pattern - .valid_to - .or(tx_valid_to) - .unwrap_or(VALID_TIME_FOREVER); - - facts.push(Fact::with_valid_time( - entity, attr, value, 0, 0, valid_from, valid_to, - )); - } - - Ok(facts) + #[cfg(any(test, all(target_arch = "wasm32", feature = "browser")))] + pub(crate) fn materialize_transaction( + tx: &crate::query::datalog::types::Transaction, + ) -> Result> { + tx.facts + .iter() + .map(|pattern| statement::materialize_assertion(pattern, tx.valid_from, tx.valid_to)) + .collect() } /// Convert a `Transaction` into a list of retraction `Fact`s. - pub(crate) fn materialize_retraction(tx: &Transaction) -> Result> { - use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; - use crate::query::datalog::types::EdnValue; - - let mut facts = Vec::new(); - - for pattern in &tx.facts { - let entity = - edn_to_entity_id(&pattern.entity).map_err(|e| err_coded!(ErrorCode::Int002, e))?; - - let attr = match &pattern.attribute { - AttributeSpec::Real(EdnValue::Keyword(k)) => k.clone(), - AttributeSpec::Real(_) => bail_coded!(ErrorCode::Api003), - AttributeSpec::Pseudo(_) => bail_coded!(ErrorCode::Api004), - }; - - let value = - edn_to_value(&pattern.value).map_err(|e| err_coded!(ErrorCode::Int003, e))?; - - let mut f = Fact::retract(entity, attr, value, 0); - f.tx_count = 0; - facts.push(f); - } - - Ok(facts) + #[cfg(any(test, all(target_arch = "wasm32", feature = "browser")))] + pub(crate) fn materialize_retraction( + tx: &crate::query::datalog::types::Transaction, + ) -> Result> { + tx.facts + .iter() + .map(statement::materialize_retraction_of) + .collect() } // ── UDF registration ───────────────────────────────────────────────────── @@ -1514,23 +1472,22 @@ impl<'a> WriteTransaction<'a> { } fn execute_inner(&mut self, input: &str) -> Result { + if let Some(kind) = statement::kind_of(input) { + // A rejected statement stages nothing; the transaction stays + // usable. Pass 1 checks windows at the staging time; `commit` + // checks them again at the commit time. + let staged_tx_id = + std::cmp::max(crate::graph::types::tx_id_now(), self.next_pending_tx_id); + let facts = statement::read_statement(input, kind, staged_tx_id)?.facts()?; + crate::graph::storage::check_one_window_per_triple(&facts)?; + self.stage_pending_facts(facts); + return Ok(QueryResult::Ok); + } let cmd = parse_datalog_command(input)?; match cmd { - DatalogCommand::Transact(tx) => { - // A rejected statement stages nothing; the transaction stays - // usable. `commit` checks windows again at the commit time. - let facts = Minigraf::materialize_transaction(&tx)?; - let staged_tx_id = - std::cmp::max(crate::graph::types::tx_id_now(), self.next_pending_tx_id); - crate::graph::storage::check_valid_windows(&facts, staged_tx_id)?; - crate::graph::storage::check_one_window_per_triple(&facts)?; - self.stage_pending_facts(facts); - Ok(QueryResult::Ok) - } - DatalogCommand::Retract(tx) => { - self.stage_pending_facts(Minigraf::materialize_retraction(&tx)?); - Ok(QueryResult::Ok) + DatalogCommand::Transact(_) | DatalogCommand::Retract(_) => { + Err(err_coded!(ErrorCode::Api002)) } DatalogCommand::Query(ref q) => { reject_unbound_slots(q)?; @@ -1800,6 +1757,7 @@ impl Drop for WriteTransaction<'_> { #[cfg(all(test, not(target_arch = "wasm32")))] mod tests { use super::*; + use crate::graph::types::VALID_TIME_FOREVER; // ── repl factory ──────────────────────────────────────────────────────── diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index 96614353cd..6ba88dcfb1 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -31,309 +31,343 @@ enum Token { } /// Tokenize EDN input +#[cfg(test)] fn tokenize(input: &str) -> Result> { - let mut tokens = Vec::new(); - let mut chars = input.chars().peekable(); - - while let Some(&ch) = chars.peek() { - match ch { - // Whitespace - ' ' | '\t' | '\n' | '\r' | ',' => { - chars.next(); - } - // Parens and brackets - '(' => { - tokens.push(Token::LeftParen); - chars.next(); - } - ')' => { - tokens.push(Token::RightParen); - chars.next(); - } - '[' => { - tokens.push(Token::LeftBracket); - chars.next(); - } - ']' => { - tokens.push(Token::RightBracket); - chars.next(); - } - '{' => { - tokens.push(Token::LeftBrace); - chars.next(); - } - '}' => { - tokens.push(Token::RightBrace); - chars.next(); - } - // String literals - '"' => { - chars.next(); // consume opening quote - let mut string = String::new(); - let mut closed = false; - while let Some(&ch) = chars.peek() { - if ch == '"' { - chars.next(); // consume closing quote - closed = true; - break; - } else if ch == '\\' { - chars.next(); - // Handle escape sequences - if let Some(&escaped) = chars.peek() { - chars.next(); - match escaped { - 'n' => string.push('\n'), - 't' => string.push('\t'), - 'r' => string.push('\r'), - '"' => string.push('"'), - '\\' => string.push('\\'), - _ => string.push(escaped), + let mut lexer = Lexer::new(input); + let tokens = lexer.by_ref().collect(); + lexer.finish()?; + Ok(tokens) +} + +/// Reads EDN tokens from `input` one at a time (#550). After its first error +/// it yields nothing more and keeps the error. +struct Lexer<'a> { + input: &'a str, + /// Byte offset of the next character. + pos: usize, + error: Option, +} + +impl<'a> Lexer<'a> { + fn new(input: &'a str) -> Self { + Self::at(input, 0) + } + + /// A lexer that starts at byte `pos` of `input`, which must be a token + /// boundary. + fn at(input: &'a str, pos: usize) -> Self { + Lexer { + input, + pos, + error: None, + } + } + + /// Lex the rest of the input, keeping nothing: its first error, if any. + fn finish(&mut self) -> Result<()> { + while self.next().is_some() {} + match self.error.take() { + Some(e) => Err(e), + None => Ok(()), + } + } + + fn peek_char(&self) -> Option { + self.input.get(self.pos..)?.chars().next() + } + + fn bump(&mut self) { + if let Some(ch) = self.peek_char() { + self.pos += ch.len_utf8(); + } + } + + /// The next token, or `None` at the end of the input. + fn lex(&mut self) -> Result> { + while let Some(ch) = self.peek_char() { + let token = match ch { + // Whitespace + ' ' | '\t' | '\n' | '\r' | ',' => { + self.bump(); + continue; + } + // Parens and brackets + '(' => { + self.bump(); + Token::LeftParen + } + ')' => { + self.bump(); + Token::RightParen + } + '[' => { + self.bump(); + Token::LeftBracket + } + ']' => { + self.bump(); + Token::RightBracket + } + '{' => { + self.bump(); + Token::LeftBrace + } + '}' => { + self.bump(); + Token::RightBrace + } + // String literals + '"' => { + self.bump(); // consume opening quote + let mut string = String::new(); + let mut closed = false; + while let Some(ch) = self.peek_char() { + if ch == '"' { + self.bump(); // consume closing quote + closed = true; + break; + } else if ch == '\\' { + self.bump(); + // Handle escape sequences + if let Some(escaped) = self.peek_char() { + self.bump(); + match escaped { + 'n' => string.push('\n'), + 't' => string.push('\t'), + 'r' => string.push('\r'), + '"' => string.push('"'), + '\\' => string.push('\\'), + _ => string.push(escaped), + } } + } else { + if string.len() >= MAX_STRING_LENGTH { + bail_coded!(ErrorCode::Prs007, MAX_STRING_LENGTH); + } + string.push(ch); + self.bump(); } - } else { - if string.len() >= MAX_STRING_LENGTH { - bail_coded!(ErrorCode::Prs007, MAX_STRING_LENGTH); - } - string.push(ch); - chars.next(); } - } - if !closed { - bail_coded!(ErrorCode::Prs109); - } - tokens.push(Token::String(string)); - } - // Keywords (start with :) - ':' => { - chars.next(); - let mut keyword = String::from(":"); - while let Some(&ch) = chars.peek() { - // '?' is a constituent character, matching symbols (see below) and - // EDN itself — predicate-style names like :person/alive? are idiomatic. - // A keyword can never be a query variable, so there is no ambiguity. - if ch.is_alphanumeric() || ch == '/' || ch == '-' || ch == '_' || ch == '?' { - if keyword.len() >= MAX_KEYWORD_LENGTH { - bail_coded!(ErrorCode::Prs008, MAX_KEYWORD_LENGTH); + if !closed { + bail_coded!(ErrorCode::Prs109); + } + Token::String(string) + } + // Keywords (start with :) + ':' => { + self.bump(); + let mut keyword = String::from(":"); + while let Some(ch) = self.peek_char() { + // '?' is a constituent character, matching symbols (see below) and + // EDN itself — predicate-style names like :person/alive? are idiomatic. + // A keyword can never be a query variable, so there is no ambiguity. + if ch.is_alphanumeric() || ch == '/' || ch == '-' || ch == '_' || ch == '?' + { + if keyword.len() >= MAX_KEYWORD_LENGTH { + bail_coded!(ErrorCode::Prs008, MAX_KEYWORD_LENGTH); + } + keyword.push(ch); + self.bump(); + } else { + break; } - keyword.push(ch); - chars.next(); - } else { - break; } - } - if keyword.len() == 1 { - bail_coded!(ErrorCode::Prs110); - } - tokens.push(Token::Keyword(keyword)); - } - // Tagged literals (start with #) - '#' => { - chars.next(); - let mut tag = String::new(); - while let Some(&ch) = chars.peek() { - if ch.is_alphanumeric() || ch == '-' { - if tag.len() >= MAX_SYMBOL_LENGTH { - bail_coded!(ErrorCode::Prs009, MAX_SYMBOL_LENGTH); + if keyword.len() == 1 { + bail_coded!(ErrorCode::Prs110); + } + Token::Keyword(keyword) + } + // Tagged literals (start with #) + '#' => { + self.bump(); + let mut tag = String::new(); + while let Some(ch) = self.peek_char() { + if ch.is_alphanumeric() || ch == '-' { + if tag.len() >= MAX_SYMBOL_LENGTH { + bail_coded!(ErrorCode::Prs009, MAX_SYMBOL_LENGTH); + } + tag.push(ch); + self.bump(); + } else { + break; } - tag.push(ch); - chars.next(); - } else { - break; } + Token::TaggedLiteral(tag) } - tokens.push(Token::TaggedLiteral(tag)); - } - // Numbers or symbols starting with - - '-' => { - let start_pos = chars.clone(); - chars.next(); - if let Some(&next_ch) = chars.peek() { - if next_ch.is_numeric() { + // Numbers or symbols starting with - + '-' => { + self.bump(); + match self.peek_char() { // It's a negative number - let mut num_str = String::from("-"); - let (is_float, num) = parse_number(&mut chars, &mut num_str)?; - if is_float { - let f: f64 = num - .parse() - .map_err(|_| err_coded!(ErrorCode::Int007, num.clone()))?; - tokens.push(Token::Float(f)); - } else { - let i: i64 = num - .parse() - .map_err(|_| err_coded!(ErrorCode::Int008, num.clone()))?; - tokens.push(Token::Integer(i)); - } - } else { + Some(next_ch) if next_ch.is_numeric() => self.number(String::from("-"))?, // It's a symbol starting with - - chars = start_pos; - chars.next(); - let symbol = parse_symbol(&mut chars, '-')?; - tokens.push(Token::Symbol(symbol)); - } - } else { - // Just a - symbol - tokens.push(Token::Symbol("-".to_string())); - } - } - // Numbers - '0'..='9' => { - let mut num_str = String::new(); - let (is_float, num) = parse_number(&mut chars, &mut num_str)?; - if is_float { - let f: f64 = num - .parse() - .map_err(|_| err_coded!(ErrorCode::Int007, num.clone()))?; - tokens.push(Token::Float(f)); - } else { - let i: i64 = num - .parse() - .map_err(|_| err_coded!(ErrorCode::Int008, num.clone()))?; - tokens.push(Token::Integer(i)); - } - } - // Symbols (including variables starting with ?) - _ if ch.is_alphabetic() || ch == '?' || ch == '_' => { - let mut symbol = String::new(); - while let Some(&ch) = chars.peek() { - if ch.is_alphanumeric() || ch == '?' || ch == '_' || ch == '-' || ch == '/' { - if symbol.len() >= MAX_SYMBOL_LENGTH { - bail_coded!(ErrorCode::Int009, MAX_SYMBOL_LENGTH); - } - symbol.push(ch); - chars.next(); - } else { - break; + Some(_) => Token::Symbol(self.symbol(String::from("-"))?), + // Just a - symbol + None => Token::Symbol("-".to_string()), } } - - // Check for special symbols - match symbol.as_str() { - "true" => tokens.push(Token::Boolean(true)), - "false" => tokens.push(Token::Boolean(false)), - "nil" => tokens.push(Token::Nil), - _ => tokens.push(Token::Symbol(symbol)), + // Numbers + '0'..='9' => self.number(String::new())?, + // Symbols (including variables starting with ?) + _ if ch.is_alphabetic() || ch == '?' || ch == '_' => { + let symbol = self.symbol(String::new())?; + // Check for special symbols + match symbol.as_str() { + "true" => Token::Boolean(true), + "false" => Token::Boolean(false), + "nil" => Token::Nil, + _ => Token::Symbol(symbol), + } } - } - // Operator symbols: <, <=, >, >=, =, !=, +, *, / - '<' | '>' | '=' | '+' | '*' | '/' => { - chars.next(); - let mut sym = String::from(ch); - // Consume a trailing '=' to form <=, >= - if (ch == '<' || ch == '>') && chars.peek() == Some(&'=') { - sym.push('='); - chars.next(); + // Operator symbols: <, <=, >, >=, =, !=, +, *, / + '<' | '>' | '=' | '+' | '*' | '/' => { + self.bump(); + let mut sym = String::from(ch); + // Consume a trailing '=' to form <=, >= + if (ch == '<' || ch == '>') && self.peek_char() == Some('=') { + sym.push('='); + self.bump(); + } + Token::Symbol(sym) } - tokens.push(Token::Symbol(sym)); - } - '!' => { - chars.next(); - if chars.peek() == Some(&'=') { - chars.next(); - tokens.push(Token::Symbol("!=".to_string())); - } else { - bail_coded!(ErrorCode::Prs002, '!'); + '!' => { + self.bump(); + if self.peek_char() == Some('=') { + self.bump(); + Token::Symbol("!=".to_string()) + } else { + bail_coded!(ErrorCode::Prs002, '!'); + } } - } - // EDN line comment: skip from ';' to the next newline (or end of input) - ';' => { - chars.next(); // consume ';' - while let Some(&c) = chars.peek() { - if c == '\n' { - break; + // EDN line comment: skip from ';' to the next newline (or end of input) + ';' => { + self.bump(); // consume ';' + while let Some(c) = self.peek_char() { + if c == '\n' { + break; + } + self.bump(); } - chars.next(); + continue; } - } - '$' => { - chars.next(); // consume '$' - let mut name = String::new(); - while let Some(&ch) = chars.peek() { - if ch.is_alphanumeric() || ch == '_' || ch == '-' { - if name.len() >= MAX_SYMBOL_LENGTH { - bail_coded!(ErrorCode::Prs074, MAX_SYMBOL_LENGTH); + '$' => { + self.bump(); // consume '$' + let mut name = String::new(); + while let Some(ch) = self.peek_char() { + if ch.is_alphanumeric() || ch == '_' || ch == '-' { + if name.len() >= MAX_SYMBOL_LENGTH { + bail_coded!(ErrorCode::Prs074, MAX_SYMBOL_LENGTH); + } + name.push(ch); + self.bump(); + } else { + break; } - name.push(ch); - chars.next(); - } else { - break; } + if name.is_empty() { + bail_coded!(ErrorCode::Prs083); + } + Token::BindSlot(name) } - if name.is_empty() { - bail_coded!(ErrorCode::Prs083); + _ => { + bail_coded!(ErrorCode::Prs002, ch); } - tokens.push(Token::BindSlot(name)); - } - _ => { - bail_coded!(ErrorCode::Prs002, ch); + }; + return Ok(Some(token)); + } + Ok(None) + } + + /// A number whose text starts with `num` (`""` or `"-"`). + fn number(&mut self, mut num: String) -> Result { + let mut is_float = false; + while let Some(ch) = self.peek_char() { + if ch.is_numeric() { + num.push(ch); + self.bump(); + } else if ch == '.' && !is_float { + is_float = true; + num.push(ch); + self.bump(); + } else { + break; } } - } - - Ok(tokens) -} - -fn parse_number( - chars: &mut std::iter::Peekable, - num_str: &mut String, -) -> Result<(bool, String)> { - let mut is_float = false; - - while let Some(&ch) = chars.peek() { - if ch.is_numeric() { - num_str.push(ch); - chars.next(); - } else if ch == '.' && !is_float { - is_float = true; - num_str.push(ch); - chars.next(); + if is_float { + let f: f64 = num + .parse() + .map_err(|_| err_coded!(ErrorCode::Int007, num.clone()))?; + Ok(Token::Float(f)) } else { - break; + let i: i64 = num + .parse() + .map_err(|_| err_coded!(ErrorCode::Int008, num.clone()))?; + Ok(Token::Integer(i)) } } - Ok((is_float, num_str.clone())) + /// The rest of a symbol whose text starts with `symbol`. + fn symbol(&mut self, mut symbol: String) -> Result { + while let Some(ch) = self.peek_char() { + if ch.is_alphanumeric() || ch == '?' || ch == '_' || ch == '-' || ch == '/' { + if symbol.len() >= MAX_SYMBOL_LENGTH { + bail_coded!(ErrorCode::Int009, MAX_SYMBOL_LENGTH); + } + symbol.push(ch); + self.bump(); + } else { + break; + } + } + Ok(symbol) + } } -fn parse_symbol(chars: &mut std::iter::Peekable, first: char) -> Result { - let mut symbol = String::from(first); - while let Some(&ch) = chars.peek() { - if ch.is_alphanumeric() || ch == '?' || ch == '_' || ch == '-' || ch == '/' { - if symbol.len() >= MAX_SYMBOL_LENGTH { - bail_coded!(ErrorCode::Int009, MAX_SYMBOL_LENGTH); +impl Iterator for Lexer<'_> { + type Item = Token; + + fn next(&mut self) -> Option { + if self.error.is_some() { + return None; + } + match self.lex() { + Ok(token) => token, + Err(e) => { + self.error = Some(e); + None } - symbol.push(ch); - chars.next(); - } else { - break; } } - Ok(symbol) } -/// Parser for EDN values -struct Parser { - tokens: Vec, - pos: usize, +/// Parser for EDN values, reading tokens from a [`Lexer`] as it needs them. +struct Parser<'a> { + lexer: Lexer<'a>, + peeked: Option, depth: usize, + /// When false, vectors, lists and maps are checked but hold no elements. + keep: bool, } -impl Parser { - fn new(tokens: Vec) -> Self { +impl<'a> Parser<'a> { + fn new(lexer: Lexer<'a>) -> Self { Parser { - tokens, - pos: 0, + lexer, + peeked: None, depth: 0, + keep: true, } } - fn peek(&self) -> Option<&Token> { - self.tokens.get(self.pos) + fn peek(&mut self) -> Option<&Token> { + if self.peeked.is_none() { + self.peeked = self.lexer.next(); + } + self.peeked.as_ref() } fn advance(&mut self) -> Option { - let token = self.tokens.get(self.pos)?.clone(); - self.pos += 1; - Some(token) + self.peeked.take().or_else(|| self.lexer.next()) } fn parse_map(&mut self) -> Result { @@ -347,7 +381,9 @@ impl Parser { } let key = self.parse_value()?; let val = self.parse_value()?; - pairs.push((key, val)); + if self.keep { + pairs.push((key, val)); + } } bail_coded!(ErrorCode::Prs006); @@ -459,7 +495,10 @@ impl Parser { self.advance(); // consume ] return Ok(EdnValue::Vector(elements)); } - elements.push(self.parse_value()?); + let value = self.parse_value()?; + if self.keep { + elements.push(value); + } } bail_coded!(ErrorCode::Prs004); @@ -474,7 +513,10 @@ impl Parser { self.advance(); // consume ) return Ok(EdnValue::List(elements)); } - elements.push(self.parse_value()?); + let value = self.parse_value()?; + if self.keep { + elements.push(value); + } } bail_coded!(ErrorCode::Prs005); @@ -483,11 +525,16 @@ impl Parser { /// Parse EDN input into EdnValue pub fn parse_edn(input: &str) -> Result { - let tokens = tokenize(input)?; - let mut parser = Parser::new(tokens); - let value = parser.parse_value()?; - if let Some(token) = parser.peek() { - let repr = format!("{:?}", token); + let mut parser = Parser::new(Lexer::new(input)); + let value = parser.parse_value(); + let trailing = match value { + Ok(_) => parser.peek().map(|token| format!("{:?}", token)), + Err(_) => None, + }; + // A lexer error anywhere in the input comes before a structure error. + parser.lexer.finish()?; + let value = value?; + if let Some(repr) = trailing { bail_coded!(ErrorCode::Prs077, repr); } Ok(value) @@ -495,6 +542,16 @@ pub fn parse_edn(input: &str) -> Result { /// Parse a Datalog command from EDN pub fn parse_datalog_command(input: &str) -> Result { + if let Some(kind) = statement::kind_of(input) { + return statement::parse(input, kind); + } + parse_whole_command(input) +} + +/// Parse a command read whole into one [`EdnValue`]. `transact` and `retract` +/// go to [`statement`] instead; their whole-input parsers stay for its +/// differential tests. +fn parse_whole_command(input: &str) -> Result { let edn = parse_edn(input)?; match edn { @@ -513,7 +570,9 @@ pub fn parse_datalog_command(input: &str) -> Result { let rest = &elements[1..]; match command { "query" => parse_query(rest), + #[cfg(test)] "transact" => parse_transact(rest), + #[cfg(test)] "retract" => parse_retract(rest), "rule" => parse_rule(rest), _ => bail_coded!(ErrorCode::Prs011, command), @@ -1016,6 +1075,7 @@ fn parse_query(elements: &[EdnValue]) -> Result { Ok(DatalogCommand::Query(query)) } +#[cfg(test)] fn parse_transact(elements: &[EdnValue]) -> Result { // Parse (transact [facts]) or (transact {opts} [facts]) if elements.is_empty() { @@ -1145,6 +1205,7 @@ fn parse_valid_time_map(pairs: &[(EdnValue, EdnValue)]) -> Result<(Option, Ok((valid_from, valid_to)) } +#[cfg(test)] fn parse_retract(elements: &[EdnValue]) -> Result { // Same structure as transact if elements.is_empty() { @@ -2173,6 +2234,7 @@ fn parse_rule(elements: &[EdnValue]) -> Result { })) } +pub(crate) mod statement; #[cfg(all(test, not(target_arch = "wasm32")))] mod verifier; diff --git a/src/query/datalog/parser/statement.rs b/src/query/datalog/parser/statement.rs new file mode 100644 index 0000000000..a0cf4e076c --- /dev/null +++ b/src/query/datalog/parser/statement.rs @@ -0,0 +1,839 @@ +//! `transact` and `retract` statements, read one fact at a time (#550, spec +//! `2026-10-21-streaming-transactions-design.md` §3). +//! +//! A statement's errors are found in phases (spec §3.3): 1 tokens, 2 EDN +//! structure, 3 the command, 4 each fact's shape, 5 materialisation, 6 valid +//! windows. Today's whole-input code runs each phase over the whole statement +//! before the next, so it reports the first error of the earliest phase that +//! has one. The reader keeps that order in one pass that holds one fact at a +//! time: it records the error of the earliest phase found so far, runs only the +//! phases before it from then on, and reports it at the end of the input. + +use super::{Lexer, Parser, Token, parse_valid_time_map}; +use crate::db::VALID_FROM_USE_TX_TIME; +use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::graph::storage::check_valid_windows; +use crate::graph::types::{Fact, TxId, VALID_TIME_FOREVER}; +use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; +use crate::query::datalog::types::{AttributeSpec, DatalogCommand, EdnValue, Pattern, Transaction}; +use anyhow::Result; + +/// Most facts a statement holds materialised at once; a statement with more +/// is read again in chunks of this many (spec §3.3). +const TX_CHUNK_FACTS: usize = 16_384; + +#[cfg(test)] +thread_local! { + static CHUNK_FACTS: std::cell::Cell> = const { std::cell::Cell::new(None) }; +} + +/// Set this thread's chunk size (`None`: [`TX_CHUNK_FACTS`]), so tests reach +/// pass 2 with small statements. +#[cfg(test)] +pub(crate) fn set_tx_chunk_facts(n: Option) { + CHUNK_FACTS.with(|c| c.set(n)); +} + +fn tx_chunk_facts() -> usize { + #[cfg(test)] + if let Some(n) = CHUNK_FACTS.with(std::cell::Cell::get) { + return n.max(1); + } + TX_CHUNK_FACTS +} + +/// Which statement a command is. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum Kind { + Transact, + Retract, +} + +impl Kind { + pub(crate) fn name(self) -> &'static str { + match self { + Kind::Transact => "transact", + Kind::Retract => "retract", + } + } +} + +/// The statement `input` is, from its first two tokens: `(` and the symbol +/// `transact` or `retract`. `None` for any other command, and when those +/// tokens do not lex (the whole-input parser reports that error). +pub(crate) fn kind_of(input: &str) -> Option { + let mut lexer = Lexer::new(input); + if lexer.next()? != Token::LeftParen { + return None; + } + match lexer.next()? { + Token::Symbol(s) if s == "transact" => Some(Kind::Transact), + Token::Symbol(s) if s == "retract" => Some(Kind::Retract), + _ => None, + } +} + +// Phases, in the order today's code runs them (spec §3.3). +const LEX: u8 = 1; +const STRUCTURE: u8 = 2; +const COMMAND: u8 = 3; +const FACT: u8 = 4; +const MATERIALIZE: u8 = 5; +const WINDOW: u8 = 6; + +/// The error of the earliest phase found so far: within a phase, the first. +struct FirstError { + phase: u8, + error: Option, +} + +impl FirstError { + fn new() -> Self { + FirstError { + phase: u8::MAX, + error: None, + } + } + + fn record(&mut self, phase: u8, error: anyhow::Error) { + if phase < self.phase { + self.phase = phase; + self.error = Some(error); + } + } + + /// Whether `phase` still runs: no error of it or an earlier phase yet. + fn runs(&self, phase: u8) -> bool { + phase < self.phase + } +} + +/// A statement's transaction-level valid-time defaults. +#[derive(Clone, Copy, Default)] +struct Defaults { + valid_from: Option, + valid_to: Option, +} + +/// Read the statement `input` (its kind checked by [`kind_of`]) through +/// phases 1–4. Each fact that passes them while no error is recorded goes to +/// `on_fact` with the byte offset just after it. Returns the defaults. +fn read( + input: &str, + kind: Kind, + first: &mut FirstError, + on_fact: &mut dyn FnMut(Pattern, usize, &mut FirstError), +) -> Defaults { + let mut p = Parser::new(Lexer::new(input)); + // `(` and the command symbol. + p.advance(); + p.advance(); + let mut shape = Shape::default(); + if let Err(e) = read_elements(&mut p, kind, &mut shape, first, on_fact) { + first.record(STRUCTURE, e); + } + if let Err(e) = p.lexer.finish() { + first.record(LEX, e); + } + let defaults = shape.defaults(); + if let Err(e) = shape.check(kind) { + first.record(COMMAND, e); + } + defaults +} + +/// What phase 3 needs to know about a statement's elements. +#[derive(Default)] +struct Shape { + elements: usize, + /// The transaction-level map's defaults (`transact` only), when the first + /// element is a map. + map: Option>, + /// Whether the facts element is a vector. + facts_vector: bool, +} + +impl Shape { + /// The defaults of a well-formed transaction-level map, else none. + fn defaults(&self) -> Defaults { + match &self.map { + Some(Ok(defaults)) => *defaults, + _ => Defaults::default(), + } + } + + /// Phase 3, in the order `parse_transact` / `parse_retract` check it. + fn check(self, kind: Kind) -> Result<()> { + match kind { + Kind::Transact => { + if self.elements == 0 { + bail_coded!(ErrorCode::Prs041); + } + let consumed = match self.map { + Some(map) => { + map?; + if self.elements < 2 { + bail_coded!(ErrorCode::Prs048); + } + 2 + } + None => 1, + }; + if self.elements > consumed { + bail_coded!(ErrorCode::Prs075, self.elements - consumed); + } + if !self.facts_vector { + bail_coded!(ErrorCode::Prs042); + } + } + Kind::Retract => { + if self.elements == 0 { + bail_coded!(ErrorCode::Prs043); + } + if self.elements > 1 { + bail_coded!(ErrorCode::Prs076, self.elements - 1); + } + if !self.facts_vector { + bail_coded!(ErrorCode::Prs044); + } + } + } + Ok(()) + } +} + +/// The command list's elements, then the end of the input. Returns the first +/// structure error (phase 2); the facts go through [`read_facts`]. +fn read_elements( + p: &mut Parser<'_>, + kind: Kind, + shape: &mut Shape, + first: &mut FirstError, + on_fact: &mut dyn FnMut(Pattern, usize, &mut FirstError), +) -> Result<()> { + loop { + // The command list is at depth 1, as `parse_edn` parses it. + p.depth = 1; + let (opens_map, opens_vector) = match p.peek() { + None => bail_coded!(ErrorCode::Prs005), + Some(Token::RightParen) => { + p.advance(); + break; + } + Some(token) => (*token == Token::LeftBrace, *token == Token::LeftBracket), + }; + let at = shape.elements; + shape.elements += 1; + let facts_at = usize::from(shape.map.is_some()); + if kind == Kind::Transact && at == 0 && opens_map { + p.keep = true; + let map = p.parse_value(); + p.keep = false; + let pairs = match map? { + EdnValue::Map(pairs) => pairs, + _ => bail_coded!(ErrorCode::Int019, "a map element parsed as another kind"), + }; + shape.map = Some( + parse_valid_time_map(&pairs).map(|(valid_from, valid_to)| Defaults { + valid_from, + valid_to, + }), + ); + } else if at == facts_at && opens_vector { + shape.facts_vector = true; + read_facts(p, kind, shape.defaults(), first, on_fact)?; + } else { + // Any other element is checked, not held (decision 2). + p.keep = false; + p.parse_value()?; + } + } + if let Some(token) = p.peek() { + let repr = format!("{:?}", token); + bail_coded!(ErrorCode::Prs077, repr); + } + Ok(()) +} + +/// The facts vector, from its `[`: each fact through phase 4 while no error of +/// phases 1–4 is recorded. Returns the first structure error. +fn read_facts( + p: &mut Parser<'_>, + kind: Kind, + defaults: Defaults, + first: &mut FirstError, + on_fact: &mut dyn FnMut(Pattern, usize, &mut FirstError), +) -> Result<()> { + p.advance(); + loop { + // Facts are at depth 3: the command list, then the facts vector. + p.depth = 2; + match p.peek() { + None => bail_coded!(ErrorCode::Prs004), + Some(Token::RightBracket) => { + p.advance(); + return Ok(()); + } + Some(_) => {} + } + let wanted = first.runs(FACT); + p.keep = wanted; + let fact = p.parse_value(); + p.keep = false; + let fact = fact?; + if wanted { + // `parse_value` leaves no token peeked: the lexer is just past the fact. + let end = p.lexer.pos; + match fact_pattern(kind, &fact, defaults) { + Ok(pattern) => on_fact(pattern, end, first), + Err(e) => first.record(FACT, e), + } + } + } +} + +/// Phase 4 for one fact: its shape and per-fact map, as `parse_transact` / +/// `parse_retract` check each fact. +fn fact_pattern(kind: Kind, fact: &EdnValue, defaults: Defaults) -> Result { + match kind { + Kind::Transact => { + let fact_vec = fact + .as_vector() + .ok_or_else(|| err_coded!(ErrorCode::Prs045))?; + // A fact is [e a v] or [e a v {opts}] + let (entity, attribute, value, opts) = match fact_vec.as_slice() { + [e, a, v] => (e, a, v, None), + [e, a, v, opts] => (e, a, v, Some(opts)), + _ if fact_vec.len() < 3 => bail_coded!(ErrorCode::Prs046, fact_vec.len()), + _ => bail_coded!(ErrorCode::Prs108, fact_vec.len()), + }; + let (fact_valid_from, fact_valid_to) = match opts { + Some(EdnValue::Map(pairs)) => parse_valid_time_map(pairs)?, + Some(other) => { + let repr = format!("{:?}", other); + bail_coded!(ErrorCode::Prs047, repr); + } + None => (None, None), + }; + // Per-fact overrides take precedence over transaction-level defaults + Ok(Pattern::with_valid_time( + entity.clone(), + attribute.clone(), + value.clone(), + fact_valid_from.or(defaults.valid_from), + fact_valid_to.or(defaults.valid_to), + )) + } + Kind::Retract => { + let fact_vec = fact + .as_vector() + .ok_or_else(|| err_coded!(ErrorCode::Prs089))?; + if fact_vec.len() != 3 { + bail_coded!(ErrorCode::Prs090, fact_vec.len()); + } + Pattern::from_edn(fact_vec).map_err(anyhow::Error::msg) + } + } +} + +/// Parse a statement for [`super::parse_datalog_command`]: phases 1–4, every +/// fact kept as a [`Pattern`]. +pub(super) fn parse(input: &str, kind: Kind) -> Result { + let mut first = FirstError::new(); + let mut patterns = Vec::new(); + let defaults = read(input, kind, &mut first, &mut |pattern, _, _| { + patterns.push(pattern); + }); + if let Some(e) = first.error { + return Err(e); + } + let mut tx = Transaction::new(patterns); + Ok(match kind { + Kind::Transact => { + tx.valid_from = defaults.valid_from; + tx.valid_to = defaults.valid_to; + DatalogCommand::Transact(tx) + } + Kind::Retract => DatalogCommand::Retract(tx), + }) +} + +/// Phase 5 for one assertion: a [`Fact`] with `tx_id` and `tx_count` 0 and an +/// unset `valid_from` as [`VALID_FROM_USE_TX_TIME`], stamped at commit. +pub(crate) fn materialize_assertion( + pattern: &Pattern, + defaults_from: Option, + defaults_to: Option, +) -> Result { + let entity = edn_to_entity_id(&pattern.entity).map_err(|e| err_coded!(ErrorCode::Int002, e))?; + let attr = real_attribute(pattern)?; + let value = edn_to_value(&pattern.value).map_err(|e| err_coded!(ErrorCode::Int003, e))?; + let valid_from = pattern + .valid_from + .or(defaults_from) + .unwrap_or(VALID_FROM_USE_TX_TIME); + let valid_to = pattern + .valid_to + .or(defaults_to) + .unwrap_or(VALID_TIME_FOREVER); + Ok(Fact::with_valid_time( + entity, attr, value, 0, 0, valid_from, valid_to, + )) +} + +/// Phase 5 for one retraction, with `tx_id` and `tx_count` 0. +pub(crate) fn materialize_retraction_of(pattern: &Pattern) -> Result { + let entity = edn_to_entity_id(&pattern.entity).map_err(|e| err_coded!(ErrorCode::Int002, e))?; + let attr = real_attribute(pattern)?; + let value = edn_to_value(&pattern.value).map_err(|e| err_coded!(ErrorCode::Int003, e))?; + let mut f = Fact::retract(entity, attr, value, 0); + f.tx_count = 0; + Ok(f) +} + +fn real_attribute(pattern: &Pattern) -> Result { + match &pattern.attribute { + AttributeSpec::Real(EdnValue::Keyword(k)) => Ok(k.clone()), + AttributeSpec::Real(_) => bail_coded!(ErrorCode::Api003), + AttributeSpec::Pseudo(_) => bail_coded!(ErrorCode::Api004), + } +} + +fn materialize(kind: Kind, pattern: &Pattern) -> Result { + match kind { + // The pattern already carries the transaction-level defaults. + Kind::Transact => materialize_assertion(pattern, None, None), + Kind::Retract => materialize_retraction_of(pattern), + } +} + +/// A `transact` or `retract` checked by pass 1 (spec §3.3). +pub(crate) struct Statement<'a> { + input: &'a str, + kind: Kind, + defaults: Defaults, + chunk: usize, + /// The first facts, at most `chunk` of them. + kept: Vec, + /// When more facts follow the kept ones (a large statement): the byte + /// offset just after the last kept fact, where pass 2 resumes. + resume: Option, + /// The first error of phase 5 or 6, reported when the facts are taken + /// (decision 6 of the plan). + deferred: Option, +} + +/// Pass 1 over the statement `input` of kind `kind`: phases 1–6, with +/// `tx_id` as the time an unset `valid_from` takes. A phase 1–4 error is +/// returned here; a phase 5–6 one by [`Statement::facts`]. +pub(crate) fn read_statement(input: &str, kind: Kind, tx_id: TxId) -> Result> { + let chunk = tx_chunk_facts(); + let mut kept: Vec = Vec::new(); + let mut last_end = 0usize; + let mut resume = None; + let mut first = FirstError::new(); + let defaults = read(input, kind, &mut first, &mut |pattern, end, first| { + if !first.runs(MATERIALIZE) { + return; + } + let fact = match materialize(kind, &pattern) { + Ok(fact) => fact, + Err(e) => return first.record(MATERIALIZE, e), + }; + if first.runs(WINDOW) + && let Err(e) = check_valid_windows(std::slice::from_ref(&fact), tx_id) + { + first.record(WINDOW, e); + } + if kept.len() < chunk { + kept.push(fact); + last_end = end; + } else if resume.is_none() { + resume = Some(last_end); + } + }); + if first.phase <= FACT + && let Some(e) = first.error + { + return Err(e); + } + Ok(Statement { + input, + kind, + defaults, + chunk, + kept, + resume, + deferred: first.error, + }) +} + +impl<'a> Statement<'a> { + /// Every fact of the statement, or its phase 5–6 error. A large statement + /// is read again (pass 2) from where pass 1 stopped keeping facts. + pub(crate) fn facts(self) -> Result> { + if let Some(e) = self.deferred { + return Err(e); + } + let mut facts = self.kept; + if let Some(pos) = self.resume { + let mut rest = Pass2::new(self.input, pos, self.kind, self.defaults); + while let Some(chunk) = rest.next_chunk(self.chunk)? { + facts.extend(chunk); + } + } + Ok(facts) + } +} + +/// Pass 2: the facts after the kept ones, `chunk` at a time. +struct Pass2<'a> { + parser: Option>, + kind: Kind, + defaults: Defaults, +} + +impl<'a> Pass2<'a> { + /// Resume at byte `pos` of `input`, inside the facts vector. + fn new(input: &'a str, pos: usize, kind: Kind, defaults: Defaults) -> Self { + Pass2 { + parser: Some(Parser::new(Lexer::at(input, pos))), + kind, + defaults, + } + } + + /// The next at most `chunk` facts, `None` at the end of the facts vector. + /// Pass 1 has checked every phase, so an error here is one it did not see. + fn next_chunk(&mut self, chunk: usize) -> Result>> { + let Some(p) = self.parser.as_mut() else { + return Ok(None); + }; + let mut facts = Vec::new(); + while facts.len() < chunk { + p.depth = 2; + match p.peek() { + Some(Token::RightBracket) => { + self.parser = None; + break; + } + None => { + let e = p.lexer.error.take(); + self.parser = None; + return Err(e.unwrap_or_else(|| err_coded!(ErrorCode::Prs004))); + } + Some(_) => {} + } + let fact = p.parse_value()?; + let pattern = fact_pattern(self.kind, &fact, self.defaults)?; + facts.push(materialize(self.kind, &pattern)?); + } + Ok((!facts.is_empty()).then_some(facts)) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::db::Minigraf; + use crate::error::MinigrafError; + use crate::graph::storage::check_one_window_per_triple; + use crate::query::datalog::parser::{parse_datalog_command, parse_whole_command}; + + /// An outcome to compare: the value, or the error's code and text. + fn outcome(r: Result) -> std::result::Result { + r.map_err(|e| { + let text = format!("{e:#}"); + (MinigrafError::from(e).code().to_string(), text) + }) + } + + /// Today's write path: the whole-input parser, then phases 5–7. + fn old_write(input: &str, tx_id: TxId) -> Result> { + let facts = match parse_whole_command(input)? { + DatalogCommand::Transact(tx) => { + let facts = Minigraf::materialize_transaction(&tx)?; + check_valid_windows(&facts, tx_id)?; + facts + } + DatalogCommand::Retract(tx) => Minigraf::materialize_retraction(&tx)?, + _ => bail_coded!(ErrorCode::Int019, "not a statement"), + }; + check_one_window_per_triple(&facts)?; + Ok(facts) + } + + /// The write path through the statement reader. + fn new_write(input: &str, kind: Kind, tx_id: TxId) -> Result> { + let facts = read_statement(input, kind, tx_id)?.facts()?; + check_valid_windows(&facts, tx_id)?; + check_one_window_per_triple(&facts)?; + Ok(facts) + } + + /// `input` gives the same command or error through both parsers, and the + /// same facts or error through both write paths at every chunk size. + /// Returns the write's error code, or the number of facts written. + fn check_same(input: &str) -> std::result::Result { + let Some(kind) = kind_of(input) else { + assert!( + !input.trim_start().starts_with("(transact") + && !input.trim_start().starts_with("(retract"), + "a statement not dispatched: {input}" + ); + return Err(String::new()); + }; + assert!( + outcome(parse_datalog_command(input)) == outcome(parse_whole_command(input)), + "parse differs: {input}" + ); + let tx_id = crate::graph::types::tx_id_now(); + let old = outcome(old_write(input, tx_id)); + for chunk in [None, Some(1), Some(2), Some(3)] { + set_tx_chunk_facts(chunk); + let new = outcome(new_write(input, kind, tx_id)); + set_tx_chunk_facts(None); + assert!(old == new, "write differs at chunk {chunk:?}: {input}"); + } + old.map(|facts| facts.len()).map_err(|(code, _)| code) + } + + const TEMPLATES: [(&str, &str); 10] = [ + ("(transact [", "])"), + ("(transact [[:a :b 1", "]])"), + ("(transact {", "} [[:a :b 1]])"), + ("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [", "])"), + ("(transact [[:a :b 1] ", " [:c :d 2]])"), + ("(transact ", ")"), + ("(transact [", ""), + ("(retract [", "])"), + ("(retract [[:a :b 1] ", "])"), + ("(retract ", ")"), + ]; + + const TOKENS: [&str; 34] = [ + "(", + ")", + "[", + "]", + "{", + "}", + "[:a :b 1]", + "[:a :b 1]", + "[:e :f \"x\" {:valid-from \"2021-01-01T00:00:00Z\"}]", + "[:a :b 1 {:valid-to \"2021-01-01T00:00:00Z\"}]", + "[:a :b 1 {:valid-from \"2030-01-01T00:00:00Z\" :valid-to \"2025-01-01T00:00:00Z\"}]", + "[:a :b 1 {:valid-from \"2019-01-01T00:00:00Z\"}]", + "[:a :b]", + "[:a :b 1 2 3]", + "[:a :b 1 2]", + "[1.5 :b 1]", + "[:a b 1]", + "[:a :b ?x]", + "[#uuid \"550e8400-e29b-41d4-a716-446655440000\" :b 1]", + ":valid-from", + ":valid-to", + "\"2024-01-01T00:00:00Z\"", + "\"bad-ts\"", + "{:foo 1}", + "1", + "nil", + "?x", + "!", + "\"open", + "#foo", + "#uuid 5", + "$s", + "transact", + "; c\n", + ]; + + fn each_sequence(len: usize, f: &mut impl FnMut(&[usize])) { + fn go(buf: &mut Vec, len: usize, f: &mut impl FnMut(&[usize])) { + if buf.len() == len { + return f(buf); + } + for t in 0..TOKENS.len() { + buf.push(t); + go(buf, len, f); + buf.pop(); + } + } + go(&mut Vec::new(), len, f); + } + + #[test] + fn statements_match_the_whole_input_parser() { + // One run per template: its codes and most facts. + let run = |&(prefix, suffix): &(&str, &str)| { + let mut text = String::new(); + let mut codes = std::collections::BTreeSet::new(); + let mut most_facts = 0; + for len in 0..=3 { + each_sequence(len, &mut |seq| { + text.clear(); + text.push_str(prefix); + for &t in seq { + text.push(' '); + text.push_str(TOKENS[t]); + } + text.push(' '); + text.push_str(suffix); + match check_same(&text) { + Ok(n) => most_facts = most_facts.max(n), + Err(code) => { + codes.insert(code); + } + } + }); + } + (codes, most_facts) + }; + // A thread per template where there are threads (not on wasm32). + #[cfg(not(target_arch = "wasm32"))] + let results: Vec<_> = std::thread::scope(|scope| { + let workers: Vec<_> = TEMPLATES + .iter() + .map(|t| scope.spawn(move || run(t))) + .collect(); + workers + .into_iter() + .map(|w| w.join().expect("differential worker panicked")) + .collect() + }); + #[cfg(target_arch = "wasm32")] + let results: Vec<_> = TEMPLATES.iter().map(run).collect(); + let most_facts = results.iter().map(|(_, n)| *n).max().unwrap_or(0); + let codes: std::collections::BTreeSet = + results.into_iter().flat_map(|(c, _)| c).collect(); + // The sequences reach pass 2 and every phase. + assert!(most_facts > 3, "a statement over three chunks of one"); + for code in [ + "PRS-002", "PRS-003", "PRS-004", "PRS-005", "PRS-042", "PRS-044", "PRS-045", "PRS-046", + "PRS-047", "PRS-071", "PRS-073", "PRS-075", "PRS-076", "PRS-077", "PRS-088", "PRS-089", + "PRS-090", "PRS-108", "PRS-109", "INT-002", "INT-003", "API-003", "API-011", "API-019", + ] { + assert!(codes.contains(code), "no statement raised {code}"); + } + } + + /// Statements with errors in several phases, each reporting today's. + #[test] + fn multi_error_statements_report_todays_error() { + let long = "x".repeat(super::super::MAX_SYMBOL_LENGTH + 1); + let corpus = [ + // A later lexer error beats an earlier structure error. + "(transact [[:a :b 1)] !)".to_string(), + format!("(transact [[:a :b] [{long} :b 1]])"), + // A later structure error beats an earlier fact error. + "(transact [[:a :b] [:c :d 1 }])".to_string(), + "(transact [[:a :b 1 2 3]] [)".to_string(), + "(transact [[1 :b 1]]) extra".to_string(), + // Phase 3: extra elements before a facts element that is not a vector. + "(transact 5 6)".to_string(), + "(transact {:foo 1} 5 6)".to_string(), + "(transact {:valid-from 1})".to_string(), + "(transact [[:a :b]] [[:c :d 1]])".to_string(), + "(retract [[:a :b]] 5)".to_string(), + "(retract 5)".to_string(), + "(retract)".to_string(), + "(transact)".to_string(), + // A later fact error beats an earlier materialisation error. + "(transact [[1 :b 1] [:a :b]])".to_string(), + "(retract [[:a b 1] [:a :b 1 2]])".to_string(), + // A later materialisation error beats an earlier window error. + "(transact [[:a :b 1 {:valid-to \"2001-01-01T00:00:00Z\"}] [:a b 1]])".to_string(), + // Window and one-window-per-triple errors. + "(transact [[:a :b 1 {:valid-to \"2001-01-01T00:00:00Z\"}] [:c :d 2 {:valid-to \"2002-01-01T00:00:00Z\"}]])".to_string(), + "(transact [[:a :b 1 {:valid-from \"2001-01-01T00:00:00Z\"}] [:a :b 1 {:valid-from \"2002-01-01T00:00:00Z\"}]])".to_string(), + // Too deep, inside a fact and inside an extra element. + format!("(transact [[:a :b {}1{}]])", "[".repeat(120), "]".repeat(120)), + format!("(transact [] {}{})", "(".repeat(120), ")".repeat(120)), + // Comments and whitespace between facts. + "(transact ; c\n [[:a :b 1] ; d\n [:c :d 2]] ; e\n)".to_string(), + "(transact [[:a :b 1]".to_string(), + "(transact [[:a :b 1]]".to_string(), + "(transact".to_string(), + "(retract".to_string(), + ]; + for input in &corpus { + let _ = check_same(input); + } + } + + #[test] + fn large_statements_resume_after_the_last_kept_fact() { + let input = "(transact [[:a :n 1] [:a :n 2] [:a :n 3] [:a :n 4] [:a :n 5]])"; + set_tx_chunk_facts(Some(2)); + let statement = read_statement(input, Kind::Transact, 1).unwrap(); + set_tx_chunk_facts(None); + assert_eq!(statement.kept.len(), 2, "kept facts"); + let resume = statement.resume.expect("large"); + assert_eq!( + input.get(resume..), + Some(" [:a :n 3] [:a :n 4] [:a :n 5]])") + ); + let mut rest = Pass2::new(input, resume, Kind::Transact, Defaults::default()); + let sizes: Vec = std::iter::from_fn(|| rest.next_chunk(2).unwrap()) + .map(|c| c.len()) + .collect(); + assert_eq!(sizes, vec![2, 1], "chunk sizes"); + + set_tx_chunk_facts(Some(5)); + let exact = read_statement(input, Kind::Transact, 1).unwrap(); + set_tx_chunk_facts(None); + assert!(exact.resume.is_none(), "five facts fit a chunk of five"); + assert_eq!(exact.facts().unwrap().len(), 5, "facts"); + } + + #[test] + fn materialisation_and_window_errors_come_with_the_facts() { + let code = |r: Result>| MinigrafError::from(r.unwrap_err()).code(); + let statement = + read_statement("(transact [[1 :b 1]])", Kind::Transact, 1).expect("phases 1-4 pass"); + assert_eq!(code(statement.facts()), "INT-002"); + let statement = read_statement( + "(transact [[:a :b 1 {:valid-to \"2001-01-01T00:00:00Z\"}]])", + Kind::Transact, + crate::graph::types::tx_id_now(), + ) + .expect("phases 1-4 pass"); + assert_eq!(code(statement.facts()), "API-019"); + let shape = read_statement("(transact [[:a :b]])", Kind::Transact, 1); + assert_eq!( + MinigrafError::from(shape.err().expect("phase 4")).code(), + "PRS-046" + ); + } + + #[test] + fn parser_without_keep_checks_structure_and_holds_nothing() { + let mut p = Parser::new(Lexer::new( + "[1 (2 {:a [3]}) #uuid \"550e8400-e29b-41d4-a716-446655440000\"]", + )); + p.keep = false; + assert!(matches!(p.parse_value().unwrap(), EdnValue::Vector(v) if v.is_empty())); + let mut p = Parser::new(Lexer::new("[1 {:a} 2]")); + p.keep = false; + let e = p.parse_value().unwrap_err(); + assert_eq!(MinigrafError::from(e).code(), "PRS-003"); + } + + #[test] + fn lexer_offsets_are_byte_offsets() { + let mut lexer = Lexer::new("[\"é名\" :k]"); + assert_eq!(lexer.next(), Some(Token::LeftBracket)); + assert_eq!(lexer.next(), Some(Token::String("é名".to_string()))); + assert_eq!(lexer.pos, 8, "after the string"); + let mut resumed = Lexer::at("[\"é名\" :k]", 8); + assert_eq!(resumed.next(), Some(Token::Keyword(":k".to_string()))); + assert_eq!(resumed.next(), Some(Token::RightBracket)); + assert_eq!(resumed.next(), None); + assert!(resumed.finish().is_ok()); + let mut bad = Lexer::new("[ ! ]"); + assert_eq!(bad.next(), Some(Token::LeftBracket)); + assert_eq!(bad.next(), None, "stops at the error"); + assert_eq!(bad.next(), None, "and stays stopped"); + assert!(bad.finish().is_err()); + } +} diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 1893b87824..cae5a81976 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -90,11 +90,13 @@ impl EdnValue { } /// Check if this is a map + #[cfg(test)] pub fn is_map(&self) -> bool { matches!(self, EdnValue::Map(_)) } /// Get the map contents if this is a map + #[cfg(test)] pub fn as_map(&self) -> Option<&Vec<(EdnValue, EdnValue)>> { match self { EdnValue::Map(m) => Some(m), diff --git a/src/storage/btree.rs b/src/storage/btree.rs index c22a95bc93..a35b09d3a2 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -5,10 +5,10 @@ //! empty values and DICT uses real ones. Leaves have no sibling pointers: scans //! use [`LeafCursor`], which keeps the path from the root. //! -//! [`build_btree`] bulk-builds a tree from sorted entries. [`cow_insert`] adds -//! entries copy-on-write, rewriting only the touched leaves and their paths and -//! splitting by balanced bytes. Every page comes from a [`PageAllocator`], so an -//! insert never writes a page the old tree uses. +//! [`build_btree`] bulk-builds a tree from sorted entries. [`cow_update`] adds +//! and deletes entries copy-on-write, rewriting only the touched leaves and +//! their paths and splitting by balanced bytes. Every page comes from a +//! [`PageAllocator`], so an update never writes a page the old tree uses. use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::storage::cache::PageCache; @@ -316,11 +316,56 @@ fn write_internal_pieces( Ok(pieces) } -/// Insert sorted `entries` below `page_id`, copy-on-write. Returns the pieces -/// that replace the node; the node itself goes into `freed`. -fn insert_node( +/// Route sorted `items` to the children of `node`: one run per child, in +/// child order. +fn route_runs( + node: &Internal<'_>, + items: Vec, + key: impl Fn(&T) -> &[u8], +) -> Result)>> { + let mut runs: Vec<(usize, Vec)> = Vec::new(); + let mut from = 0usize; + for item in items { + let c = node.route(key(&item), from)?; + from = c; + match runs.last_mut() { + Some((last, run)) if *last == c => run.push(item), + _ => runs.push((c, vec![item])), + } + } + Ok(runs) +} + +/// Remove sorted `deletes` from sorted `entries`; each must be there. +fn remove_keys(entries: Vec, deletes: &[Vec]) -> Result> { + let mut out = Vec::with_capacity(entries.len().saturating_sub(deletes.len())); + let mut del = deletes.iter().peekable(); + for entry in entries { + if del.peek().is_some_and(|k| **k == entry.0) { + del.next(); + } else if del + .peek() + .is_some_and(|k| k.as_slice() < entry.0.as_slice()) + { + bail_coded!(ErrorCode::Int049, "delete of a key not in the tree"); + } else { + out.push(entry); + } + } + if del.next().is_some() { + bail_coded!(ErrorCode::Int049, "delete of a key not in the tree"); + } + Ok(out) +} + +/// Apply sorted `deletes`, then sorted `inserts`, below `page_id`, +/// copy-on-write. Returns the pieces that replace the node, none if nothing is +/// left below it; the node itself goes into `freed`. +#[allow(clippy::too_many_arguments)] +fn update_node( page_id: u64, - entries: Vec, + inserts: Vec, + deletes: Vec>, depth: usize, backend: &mut dyn StorageBackend, cache: &PageCache, @@ -337,9 +382,11 @@ fn insert_node( freed.push(page_id); match page.first().copied() { Some(PAGE_TYPE_LEAF) => { - let merged = merge_entries(decode_leaf(&page[..])?, entries)?; + let kept = remove_keys(decode_leaf(&page[..])?, &deletes)?; + let merged = merge_entries(kept, inserts)?; let mut pieces = Vec::new(); let mut prev_last: Option> = None; + // A leaf left empty packs into no group, so it returns no pieces. for group in pack_leaves(merged)? { let (Some((first, _)), Some((last, _))) = (group.first(), group.last()) else { continue; @@ -357,19 +404,14 @@ fn insert_node( Some(PAGE_TYPE_INTERNAL) => { let node = Internal::new(&page[..])?; let count = node.count(); - // Route the entries: they are sorted, so each child takes a run. - let mut runs: Vec<(usize, Vec)> = Vec::new(); - let mut from = 0usize; - for entry in entries { - let c = node.route(&entry.0, from)?; - from = c; - match runs.last_mut() { - Some((last, run)) if *last == c => run.push(entry), - _ => runs.push((c, vec![entry])), - } - } - let mut elems: Vec<(Option>, u64)> = Vec::with_capacity(count + runs.len() + 1); - let mut runs = runs.into_iter().peekable(); + // The entries and keys are sorted, so each child takes a run. + let mut ins = route_runs(&node, inserts, |e| e.0.as_slice())? + .into_iter() + .peekable(); + let mut del = route_runs(&node, deletes, Vec::as_slice)? + .into_iter() + .peekable(); + let mut elems: Vec<(Option>, u64)> = Vec::with_capacity(count + 2); for i in 0..=count { let sep_before = if i == 0 { None @@ -377,35 +419,51 @@ fn insert_node( Some(node.sep(i - 1)?.to_vec()) }; let child = node.child(i)?; - if runs.peek().is_some_and(|(c, _)| *c == i) { - let (_, run) = runs - .next() - .ok_or_else(|| err_coded!(ErrorCode::Int049, "routed run missing"))?; - let pieces = insert_node(child, run, depth + 1, backend, cache, alloc, freed)?; - for (k, piece) in pieces.into_iter().enumerate() { - let sep = if k == 0 { - sep_before.clone() - } else { - piece.sep - }; - elems.push((sep, piece.id)); - } - } else { + let child_ins = match ins.next_if(|(c, _)| *c == i) { + Some((_, run)) => run, + None => Vec::new(), + }; + let child_del = match del.next_if(|(c, _)| *c == i) { + Some((_, run)) => run, + None => Vec::new(), + }; + if child_ins.is_empty() && child_del.is_empty() { elems.push((sep_before, child)); + continue; + } + let pieces = update_node( + child, + child_ins, + child_del, + depth + 1, + backend, + cache, + alloc, + freed, + )?; + // A child with nothing left drops out with its separator. When + // it was the first, the next child's separator now leads, and + // `write_internal_pieces` ignores a leading separator. + for (k, piece) in pieces.into_iter().enumerate() { + let sep = if k == 0 { + sep_before.clone() + } else { + piece.sep + }; + elems.push((sep, piece.id)); } } + if elems.is_empty() { + return Ok(Vec::new()); + } write_internal_pieces(elems, backend, cache, alloc) } _ => bail_coded!(ErrorCode::Stg013, page_id), } } -/// Insert sorted, distinct `entries` into the tree at `root`, copy-on-write -/// (spec §8.3): only the touched leaves and their paths to the root are -/// rewritten, at ids from `alloc`; every page they replace goes into `freed`. -/// Untouched subtrees are shared with the old tree, which stays readable. A -/// root split adds a level. Root 0 (no tree) is a bulk build. Returns the new -/// root. +/// Insert sorted, distinct `entries` into the tree at `root`, copy-on-write: +/// [`cow_update`] with no deletes. pub fn cow_insert( root: u64, entries: Vec, @@ -414,14 +472,46 @@ pub fn cow_insert( alloc: &mut PageAllocator, freed: &mut Vec, ) -> Result { - check_sorted(&entries)?; + cow_update(root, entries, Vec::new(), backend, cache, alloc, freed) +} + +/// Delete sorted, distinct `deletes` from the tree at `root`, then insert +/// sorted, distinct `inserts`, copy-on-write (spec §8.3; #550 spec §6): only +/// the touched leaves and their paths to the root are rewritten, at ids from +/// `alloc`; every page they replace goes into `freed`. Untouched subtrees are +/// shared with the old tree, which stays readable. A root split adds a level. +/// +/// A delete of a key not in the tree is `INT-049`. A leaf left empty is removed +/// from its parent, and an internal node left with no children in turn; a leaf +/// left with fewer keys stays as it is, and separators are not rewritten. A +/// tree left with no keys is empty: root 0. Root 0 (no tree) is a bulk build of +/// `inserts`. Returns the new root. +pub fn cow_update( + root: u64, + inserts: Vec, + deletes: Vec>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + alloc: &mut PageAllocator, + freed: &mut Vec, +) -> Result { + check_sorted(&inserts)?; + if deletes.windows(2).any(|w| matches!(w, [a, b] if a >= b)) { + bail_coded!(ErrorCode::Int049, "deletes not sorted and distinct"); + } if root == 0 { - return build_btree(entries, backend, cache, alloc); + if !deletes.is_empty() { + bail_coded!(ErrorCode::Int049, "delete of a key not in the tree"); + } + return build_btree(inserts, backend, cache, alloc); } - if entries.is_empty() { + if inserts.is_empty() && deletes.is_empty() { return Ok(root); } - let mut pieces = insert_node(root, entries, 0, backend, cache, alloc, freed)?; + let mut pieces = update_node(root, inserts, deletes, 0, backend, cache, alloc, freed)?; + if pieces.is_empty() { + return Ok(0); + } while pieces.len() > 1 { let elems = pieces.into_iter().map(|p| (p.sep, p.id)).collect(); pieces = write_internal_pieces(elems, backend, cache, alloc)?; @@ -429,7 +519,7 @@ pub fn cow_insert( pieces .pop() .map(|p| p.id) - .ok_or_else(|| err_coded!(ErrorCode::Int049, "insert produced no root")) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "update produced no root")) } // ─── Reading ───────────────────────────────────────────────────────────────── @@ -1770,4 +1860,277 @@ mod tests { assert_eq!(code(b.sync().unwrap_err()), "INT-049"); assert_eq!(code(b.close().unwrap_err()), "INT-049"); } + + // ─── cow_update (#550 spec §6) ─────────────────────────────────────────── + + /// Walk the tree at `root` as `verify` does: keys strictly ascending and + /// within their parent's separators, no empty leaf below the root, every + /// page reached once. Returns its entries and node ids. + fn walk_checked( + root: u64, + backend: &dyn StorageBackend, + cache: &PageCache, + ) -> (Vec, BTreeSet) { + type Visit = (u64, usize, Option>, Option>); + let (mut entries, mut nodes) = (Vec::new(), BTreeSet::new()); + if root == 0 { + return (entries, nodes); + } + let mut stack: Vec = vec![(root, 0, None, None)]; + while let Some((id, depth, lo, hi)) = stack.pop() { + assert!(nodes.insert(id), "a page is reached twice"); + assert!(depth <= MAX_TREE_DEPTH, "too deep"); + let page = cache.get_or_load(id, backend).unwrap(); + if page[0] == PAGE_TYPE_LEAF { + let leaf = decode_leaf(&page[..]).unwrap(); + assert!(depth == 0 || !leaf.is_empty(), "empty leaf below the root"); + for (k, v) in leaf { + assert!(lo.as_ref().is_none_or(|l| &k >= l), "key below its range"); + assert!(hi.as_ref().is_none_or(|h| &k < h), "key above its range"); + assert!( + entries.last().is_none_or(|(p, _): &Entry| p < &k), + "keys out of order" + ); + entries.push((k, v)); + } + } else { + let node = Internal::new(&page[..]).unwrap(); + let n = node.count(); + let mut children = Vec::new(); + for i in 0..=n { + let c_lo = if i == 0 { + lo.clone() + } else { + Some(node.sep(i - 1).unwrap().to_vec()) + }; + let c_hi = if i < n { + Some(node.sep(i).unwrap().to_vec()) + } else { + hi.clone() + }; + children.push((node.child(i).unwrap(), depth + 1, c_lo, c_hi)); + } + stack.extend(children.into_iter().rev()); + } + } + (entries, nodes) + } + + /// The bytes of every page the tree at `root` reaches. + fn page_bytes( + root: u64, + backend: &dyn StorageBackend, + cache: &PageCache, + ) -> Vec<(u64, Vec)> { + let (_, nodes) = walk_checked(root, backend, cache); + nodes + .into_iter() + .map(|id| (id, backend.read_page(id).unwrap())) + .collect() + } + + /// One `cow_update` on the tree at `root`, checked against `model`: the + /// new tree holds the model's keys, the old tree's pages are unchanged and + /// it still holds `before`, `freed` is exactly the old nodes the new tree + /// dropped, and the new tree's other nodes are new pages. + #[allow(clippy::too_many_arguments)] + fn update_checked( + root: u64, + inserts: Vec, + deletes: Vec>, + model: &mut BTreeSet>, + backend: &mut MemoryBackend, + cache: &PageCache, + next: &mut u64, + generation: u64, + ) -> u64 { + let old_pages = page_bytes(root, backend, cache); + let (before, old_nodes) = walk_checked(root, backend, cache); + let mut alloc = PageAllocator::new(Vec::new(), *next, generation); + let mut freed = Vec::new(); + let changed = !inserts.is_empty() || !deletes.is_empty(); + for k in &deletes { + model.remove(k); + } + model.extend(inserts.iter().map(|(k, _)| k.clone())); + let new_root = cow_update( + root, inserts, deletes, backend, cache, &mut alloc, &mut freed, + ) + .unwrap(); + let start = *next; + *next = alloc.next_append(); + let (after, new_nodes) = walk_checked(new_root, backend, cache); + let want: Vec = model.iter().map(|k| (k.clone(), Vec::new())).collect(); + assert!(after == want, "the tree differs from the model"); + if model.is_empty() && root != 0 { + assert_eq!(new_root, 0, "an emptied tree is root 0"); + } + for (id, bytes) in &old_pages { + assert!( + backend.read_page(*id).unwrap() == *bytes, + "an old page was written" + ); + } + assert!( + walk_checked(root, backend, cache).0 == before, + "the old tree still reads" + ); + let freed: BTreeSet = freed.into_iter().collect(); + let dropped: BTreeSet = old_nodes.difference(&new_nodes).copied().collect(); + if changed && root != 0 { + assert!(freed == dropped, "freed is exactly the replaced old nodes"); + } else { + assert!(freed.is_empty(), "nothing freed"); + } + for id in new_nodes.difference(&old_nodes) { + assert!(*id >= start, "new nodes are new pages"); + } + new_root + } + + #[test] + fn cow_update_matches_a_model_over_random_steps() { + let mut rng = Rng(0x550); + let mut ctr = 0; + for round in 0..6 { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(8192); + let mut model = BTreeSet::new(); + let start = + random_entries(&mut rng, [0, 1, 300, 3000, 20_000, 60_000][round], &mut ctr); + model.extend(start.iter().map(|(k, _)| k.clone())); + let (mut root, mut next) = build_at(start, &mut backend, &cache, 2); + for step in 0..30u64 { + let keys: Vec> = model.iter().cloned().collect(); + let mut deletes: Vec> = match rng.below(4) { + // A random sample. + 0 | 1 if !keys.is_empty() => (0..rng.below(400)) + .map(|_| keys[rng.below(keys.len() as u64)].clone()) + .collect(), + // A contiguous run: whole leaves and subtrees go. + 2 if !keys.is_empty() => { + let a = rng.below(keys.len() as u64); + let b = (a + 1 + rng.below(4000)).min(keys.len()); + keys[a..b].to_vec() + } + _ => Vec::new(), + }; + deletes.sort(); + deletes.dedup(); + let n = rng.below(300); + let mut inserts = random_entries(&mut rng, n, &mut ctr); + // Sometimes a deleted key comes straight back. + if let Some(k) = deletes.first().filter(|_| rng.below(3) == 0) { + inserts.push((k.clone(), Vec::new())); + inserts.sort(); + inserts.dedup_by(|a, b| a.0 == b.0); + } + root = update_checked( + root, + inserts, + deletes, + &mut model, + &mut backend, + &cache, + &mut next, + step + 3, + ); + } + } + } + + #[test] + fn cow_update_deleting_everything_is_root_zero() { + for n in [1u64, 200, 3000, 60_000] { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(8192); + let entries: Vec = (0..n).map(|i| entry(i * 2, i)).collect(); + let mut model: BTreeSet> = entries.iter().map(|(k, _)| k.clone()).collect(); + let (root, mut next) = build_at(entries.clone(), &mut backend, &cache, 2); + // Half first, from the front, so first children drop out. + let half: Vec> = entries[..entries.len() / 2] + .iter() + .map(|(k, _)| k.clone()) + .collect(); + let root = update_checked( + root, + Vec::new(), + half, + &mut model, + &mut backend, + &cache, + &mut next, + 3, + ); + let rest: Vec> = model.iter().cloned().collect(); + let root = update_checked( + root, + Vec::new(), + rest, + &mut model, + &mut backend, + &cache, + &mut next, + 4, + ); + assert_eq!(root, 0, "empty"); + // Root 0 takes inserts as a bulk build. + let again = vec![entry(7, 7)]; + let root = update_checked( + root, + again, + Vec::new(), + &mut model, + &mut backend, + &cache, + &mut next, + 5, + ); + assert_ne!(root, 0, "a tree again"); + } + } + + #[test] + fn cow_update_rejects_bad_deletes() { + let cache = PageCache::new(4096); + let mut backend = MemoryBackend::new(); + let entries: Vec = (0..3000).map(|n| entry(n * 2, n)).collect(); + let (root, next) = build_at(entries, &mut backend, &cache, 2); + let cases: [(u64, Vec>); 5] = [ + // A missing key between stored ones, past the last, and on root 0. + (root, vec![key(1, 0)]), + (root, vec![key(0, 0), key(1, 0)]), + (root, vec![key(10_000_000, 0)]), + (0, vec![key(0, 0)]), + // Unsorted or repeated deletes. + (root, vec![key(2, 1), key(0, 0)]), + ]; + for (at, deletes) in cases { + let mut alloc = PageAllocator::new(Vec::new(), next, 3); + let mut freed = Vec::new(); + let err = cow_update( + at, + Vec::new(), + deletes, + &mut backend, + &cache, + &mut alloc, + &mut freed, + ) + .unwrap_err(); + assert_eq!(code(err), "INT-049"); + } + let mut alloc = PageAllocator::new(Vec::new(), next, 3); + let err = cow_update( + root, + Vec::new(), + vec![key(0, 0), key(0, 0)], + &mut backend, + &cache, + &mut alloc, + &mut Vec::new(), + ) + .unwrap_err(); + assert_eq!(code(err), "INT-049"); + } } diff --git a/tests/read_only_open_test.rs b/tests/read_only_open_test.rs index 0c8167b083..6642be11fb 100644 --- a/tests/read_only_open_test.rs +++ b/tests/read_only_open_test.rs @@ -380,6 +380,22 @@ fn in_memory_read_only_refuses_writes() { assert!(names(&db).is_empty()); } +/// A statement's parse errors come before API-014, and its materialisation and +/// window errors after it, as they did before the statement reader (#550). +#[test] +fn read_only_comes_between_parse_and_materialise_errors() { + let db = OpenOptions::new().read_only(true).open_memory().unwrap(); + let code = |input: &str| db.execute(input).expect_err(input).code(); + assert_eq!(code("(transact [[:a :b]])"), "PRS-046"); + assert_eq!(code("(retract [[:a :b 1] 5])"), "PRS-089"); + assert_eq!(code("(transact [[1 :b 1]])"), "API-014"); + assert_eq!(code("(retract [[:a b 1]])"), "API-014"); + assert_eq!( + code(r#"(transact [[:a :b 1 {:valid-to "2001-01-01T00:00:00Z"}]])"#), + "API-014" + ); +} + #[test] fn builder_path_open_is_read_only() { let dir = tempfile::tempdir().unwrap();