diff --git a/.github/workflows/crash-kill.yml b/.github/workflows/crash-kill.yml index fa72f14c7a..3f94c0aec7 100644 --- a/.github/workflows/crash-kill.yml +++ b/.github/workflows/crash-kill.yml @@ -64,7 +64,10 @@ jobs: RUST_BACKTRACE: 1 run: | set -o pipefail - cargo test --test crash_kill_test -- --nocapture 2>&1 | tee crash-kill-output.txt + # v3's large-transaction variant (#550) needs the test hooks. + features="" + if [ "$CRASH_REF" != main ]; then features="--features test-oracle"; fi + cargo test $features --test crash_kill_test -- --nocapture 2>&1 | tee crash-kill-output.txt - name: Record SIGKILL crash-safety failure if: ${{ failure() }} @@ -79,7 +82,7 @@ jobs: echo echo "- Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" echo "- Commit: $(git rev-parse HEAD)" - echo "- Reproduce: cargo test --test crash_kill_test -- --nocapture" + echo "- Reproduce: cargo test --test crash_kill_test -- --nocapture (v3: --features test-oracle)" echo " (set MINIGRAF_CRASH_KILL_ROUNDS to raise the round count; MINIGRAF_CRASH_KILL_SEED to the printed base seed to replay)" echo echo "## Test output" diff --git a/.github/workflows/smoke.yml b/.github/workflows/smoke.yml index 154ce1989f..9188ec21c8 100644 --- a/.github/workflows/smoke.yml +++ b/.github/workflows/smoke.yml @@ -66,3 +66,22 @@ jobs: run: cargo test --profile bench --test memory_limit_acceptance_test -- --ignored --nocapture --test-threads=1 env: RUST_BACKTRACE: 1 + + # #550: a 1M-fact transact holds at most one chunk of facts and commits as + # a checkpoint; peak RSS is printed. test-oracle: the statement reader's + # high-water mark. + large-transaction-acceptance: + name: Large transaction acceptance + runs-on: ubuntu-latest + timeout-minutes: 30 + + steps: + - uses: actions/checkout@v4 + + - name: Install Rust stable + uses: dtolnay/rust-toolchain@stable + + - name: Run the acceptance test + run: cargo test --profile bench --features test-oracle --test large_transaction_acceptance_test -- --ignored --nocapture + env: + RUST_BACKTRACE: 1 diff --git a/CLAUDE.md b/CLAUDE.md index 93e50343d2..b3e0c9786c 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -126,10 +126,11 @@ cargo run < demos/demo_negation.txt - `dir_sync.rs`: `sync_parent_dir` — fsyncs the parent directory after creating the `.graph`/WAL or deleting the WAL (no-op off Unix) - `packed_pages.rs`: v7 fact pages, read only for migration - `persistent_facts.rs`: `PersistentFactStorage` — v8 save/load, auto-migration v7→v8 + - `persistent_facts/large_tx.rs`: large transactions (#550): `Minigraf::execute` of a statement over `TX_CHUNK_FACTS` facts on a file database becomes large (WAL guard: the WAL exists, header only, before any page; cache generation bound `g + 1`; next `tx_count` reserved, allocated at the commit point; `tx_id` fixed), writes each chunk into copy-on-write working trees (per-chunk `Encoder` over the working DICT, no `SharedDictCache`; a fact an earlier chunk wrote kept once, another window of its triple `API-011`; replaced pages it wrote released to the allocator, `g`'s freed), and commits as a checkpoint (pending store included, meta `g + 1`, WAL deleted). A statement error rolls back (cache bound `g`, written pages evicted, handle dirty so the next checkpoint writes a meta before deleting the WAL); an I/O failure also marks the handle failed (`STG-046`). A WAL found at open also marks the handle dirty. `WriteTransaction` stays on the staged path until #550 PR 3 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/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`/`Statement::chunks` (one `Chunk` at a time; pass 2 from that offset for a larger statement); `set_tx_chunk_facts` for tests (`minigraf::__tx_chunk_facts` and `__statement_facts_high_water` under `test-oracle`). 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` @@ -207,7 +208,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1735 tests** (1721 passing, 14 ignored; unit + integration + doc). +**1752 tests** (1738 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 33f1796894..5e7b434754 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,9 +2,9 @@ ## Coverage Summary -**Verified**: 2026-10-21 with `cargo test --quiet` +**Verified**: 2026-10-22 with `cargo test --quiet` -**Result**: 1,721 passing tests and 14 ignored tests (1,735 total) +**Result**: 1,738 passing tests and 14 ignored tests (1,752 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,8 +29,9 @@ 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. +- **Statement reader** (`src/query/datalog/parser/statement.rs`, 8 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`. +- **Large transactions** (`src/storage/persistent_facts/large_tx.rs`, 7 tests; `src/fault_matrix.rs`, 4 tests; `src/storage/page.rs`, 2 tests; `src/storage/cache.rs`, `src/storage/btree.rs` and `statement.rs`, 4 tests; #550): a `transact`/`retract` of more than one chunk, run by `Minigraf::execute` on a file database at chunk sizes 1 to 4, stores the same records as the one-chunk path (repeats across chunks stored once, several values and windows of one attribute, shared long values, refs, keywords, transaction-level windows, retractions, pending WAL entries committed with it), returns its `tx_id`, answers `:as-of`, passes `verify`, deletes the WAL and survives reopen; another window of a triple an earlier chunk wrote (`API-011`) and a value too long for a checkpoint in a later chunk (`WAL-003`) give the one-chunk path's code and message, take no `tx_count`, write no meta and leave the WAL, and the next checkpoint writes a meta before deleting it, as the first checkpoint after an open with a WAL does; a crash before the meta write on a new file reopens through the WAL guard, and is `STG-033` without it; cursors and fact logs opened before and between chunks keep their snapshot through later checkpoints. The fault matrix injects every write and sync fault at every call of a large transaction on a file with one and with two valid meta slots, with and without a WAL beforehand. Allocator tracking and release, cache eviction, and cursor peeking have unit tests. With `test-oracle`, `tests/crash_kill_test.rs` adds a variant whose child makes most transactions large and rolls back a large statement after writing pages, and `tests/model_based_test.rs` runs at a chunk size of 2; `tests/large_transaction_acceptance_test.rs` (ignored, `test-oracle` only, nightly in `.github/workflows/smoke.yml`) holds at most 16,384 materialised facts for a 1M-fact `transact` and prints peak RSS. - **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 index c1b5cf131e..bc9c8c968d 100644 --- a/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md +++ b/docs/superpowers/plans/2026-10-21-550-streaming-transactions.md @@ -7,7 +7,7 @@ called "the spec" below. PRs target `v3`, merge commits. None uses a closing key | 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` | +| 2 | 10–15: `PageAllocator::release`, large `Minigraf::execute` 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 @@ -104,11 +104,177 @@ PR 3 changes `CHANGELOG.md` and the docs site: PRs 1 and 2 change no behaviour a 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. +## PR 2: large single statements + +Checked against `v3` at `3ea155ba` (PR 1 merged). Line numbers are from that commit. + +### Scope + +A `transact` or `retract` run by `Minigraf::execute` on a writable file database +(`WriteContext::File`) with more than `TX_CHUNK_FACTS` facts goes through spec §4: it becomes +large, writes its facts in chunks into working trees, and commits as a checkpoint. Every other +statement takes today's path: + +- **In-memory databases** (`WriteContext::Memory`) keep the small path. They have no pages, and + the whole database is in memory anyway. +- **`BrowserDb`** is unchanged: it parses with `parse_datalog_command` and commits through its + own path (`src/browser/mod.rs`), not `execute_statement`. +- **`WriteTransaction`** stays small in PR 2 (decision 12). + +### Decisions not fixed by the spec (PR 2) + +12. **`WriteTransaction` moves to PR 3** (user decision, 2026-10-22). Spec §9 puts a + `WriteTransaction` whose first statement is large in PR 2. Its later statements would need + §5.2's deletes of an earlier statement's keys (last statement wins), and its queries §7's + reads of the working trees, both PR 3. So every `WriteTransaction` statement is staged as + today until PR 3, which enables the large path for all of them at once. +13. **No statement base in PR 2.** The large statement is its transaction's only statement, so + its base (§5.1) is the transaction's start. A statement error rolls the whole transaction + back (§4.4), which is what §5.3 does for a first statement. With nothing written before + the statement, §4.2 step 3 has `handed` = every id written and `held` empty: a replaced + page this transaction wrote is released at once. +14. **`tx_count` is reserved, then allocated at the commit point.** Spec §4.1 step 3 calls + `allocate_tx_count` when the transaction becomes large. Under the write lock nothing else + allocates (the writable `Minigraf` paths that call `allocate_tx_count`, `db.rs:786` and `db.rs:1588`, hold it; `FactStorage::transact` is called only by tests), so the + transaction uses `current_tx_count() + 1` and calls `allocate_tx_count` just after its meta + write, which must return the same value (`INT-049` otherwise). A rolled-back large + transaction then takes no `tx_count`, as a small one rejected before its WAL entry takes + none today (`db.rs:781`); a small one rejected with `WAL-003` takes one, since the WAL + entry checks sizes after the allocation. +15. **Where it lives.** `src/storage/persistent_facts/large_tx.rs`, a child module of + `persistent_facts` (as `browser_access.rs` is), so it uses `PersistentFactStorage`'s + private fields (`backend`, `page_cache`, `meta`, `failed`, `dirty`) and `activate`. + `LargeTx` holds generation `g`'s meta, the working meta (five roots, `next_eid`, + `next_iid`, `fact_count`), the allocator, `freed`, `tx_count` and `tx_id`; + `PersistentFactStorage::begin_large`, `LargeTx::write_chunk`, `commit` and `rollback`. + `execute_statement` drives it within one call under the write lock; PR 3 keeps the type + in the `WriteTransaction`. The backend mutex is taken per chunk, not for the transaction + (`save` holds it throughout, `persistent_facts.rs:431`), so reads go on between chunks. +16. **Written ids.** `PageAllocator::tracking(self)` turns on a set of every id `alloc` and + `alloc_append` hand out; `handed(id)` asks it. `release(id)` (decision 11) pushes `id` + onto `free`, the stack `alloc` pops next. A page `cow_update` replaces is in the set (this + transaction wrote it: released) or not (generation `g` references it: `freed`); no third + case without a base (decision 13). The set keeps released ids too: on rollback every id + in it is evicted from the cache (decision 21). +17. **Phase 7 across chunks** (§5.2 fast path). `check_one_window_per_triple` runs on each + chunk before stamping, as today on the whole statement. Across chunks, after the chunk is + encoded, each EAVT entry's triple (`keys::triple_len`) is looked up in the working EAVT + tree with one `LeafCursor` seeking forward through the sorted entries; keys of this + `tx_count` come first (`tx↓`). A key equal to the entry is an earlier chunk's copy of the + same fact: the entry is dropped from all four trees' inserts (its other keys come from + `KeyFact::decode` + `KeyFact::key`). An assertion key with another window, when the entry + is an assertion, is `API-011`. An assertion and a retraction of one triple both stay, as + `check_one_window_per_triple` allows. +18. **Statement errors and failures** (§4.4). A chunk's checks run before it writes anything: + `check_valid_windows` at the fixed `tx_id` (`API-019`), `check_one_window_per_triple` + (`API-011`) and `wal::check_fact_size` per fact (`WAL-003`, the limit the WAL entry + enforced and the `Encoder` enforces again). These, `API-011` from decision 17, and every + pass 2 error are statement errors: the transaction rolls back, the handle is not failed. + Any other error once `begin_large` returns (I/O, `INT-*`) also marks the handle failed + (`STG-046`) before the rollback. `write_chunk` returns which kind it was. +19. **Error order across chunks.** Pass 1 reports every phase 1–6 error at read time, as PR 1 + does. Pass 2 reports a chunk's errors before a later chunk's. Today's whole-statement + order would report a later chunk's `API-011` before an earlier chunk's `WAL-003` (the WAL + serialises after the phase 7 check, `db.rs:779-806`), and a later chunk's `API-019` at the + commit time before an earlier chunk's `API-011` (the millisecond window of spec §3.3). + For a large statement both come in chunk order instead. +20. **Chunks from `Statement`.** `Statement::chunks(self) -> Result>` returns the + deferred phase 5–6 error, or an iterator of `Result>`: the kept facts, then + pass 2's chunks. `Statement::facts` collects it. `Statement::is_large()`. +21. **Cache on rollback** (§4.4). `PageCache::evict(&HashSet)` drops those entries in + one pass over the LRU order (`invalidate`, `cache.rs:200`, scans the order per id). The + spec evicts `written`; evicting released ids too costs nothing more and leaves no page of + a generation that never existed. The bound goes back to `g` (`set_generation_bound`, + `cache.rs:89`). +22. **The WAL guard** is the lazy open `wal_write_stamped_batch` does (`db.rs:1655`), moved + to a helper both call. `WalWriter::open_or_create_at` writes and syncs the header + (`wal.rs:55-56`) and syncs the directory (`wal.rs:238`); an existing file is reopened as + is, so its base stays `≤ g`. +23. **Open-time dirty rule** (§4.5 rule 2). `open_with_options_inner` calls `pfs.force_dirty()` + when the WAL file exists on a writable open (`db.rs:581`). `do_checkpoint`'s early + return (`db.rs:1155`) then deletes a WAL without a meta only when no WAL existed at open + and this handle wrote none, i.e. never with a WAL a large transaction could have guarded. +24. **Test hooks.** `set_tx_chunk_facts` is built under `cfg(any(test, feature = + "test-oracle"))`; `minigraf::__tx_chunk_facts(Option) -> TxChunkGuard` exposes it + under `test-oracle` (as `__reorder`, `src/lib.rs:134`). The acceptance count is a + thread-local high-water mark of materialised `Fact`s held at once by pass 1, pass 2 and + the chunk writer (`minigraf::__statement_facts_high_water`, `test-oracle`). `Token`s, + `EdnValue`s and `Pattern`s are one fact's worth by PR 1's construction and are not + counted. + +### Deviations from the spec (PR 2) + +1. `WriteTransaction` keeps the small path until PR 3 (decision 12; spec §9). +2. `tx_count` is allocated at the commit point, not when the transaction becomes large + (decision 14; spec §4.1 step 3). `tx_id` is still fixed when it becomes large. +3. Rollback evicts every id handed out, not only those still written (decision 21; spec §4.4). +4. Errors of different chunks come in chunk order (decision 19; spec §3.3 for pass 2). +5. Two records of one triple in different chunks, one with a default `valid_from` and one with + an explicit `valid_from` equal to the fixed `tx_id`, compare equal after stamping and are + kept once; within one chunk, as today, they are `API-011`. Hitting it needs the exact + millisecond the transaction became large. +6. The acceptance count is `Fact`s only (decision 24; spec §3.4 / §8.1 also name `Pattern`, + `EdnValue`, `Token`). + +### PR 2 steps + +10. **Allocator and cache.** `PageAllocator::tracking`, `handed`, `release` (decisions 11, + 16) and `PageCache::evict` (decision 21). Unit tests: a released id is handed out next, + an unused released id is on the new free list, `handed` covers `alloc` and + `alloc_append` but not ids before `tracking`, `evict` leaves other entries. +11. **Statement chunks and hooks.** `Statement::chunks`, `is_large`, `facts` over `chunks` + (decision 20); the high-water mark and the `test-oracle` hooks (decision 24). PR 1's + differential tests run over `chunks` too. +12. **`LargeTx`** (decision 15). `begin_large(tx_id)`: bound `g + 1`, allocator + `from_chain(.., g + 1).with_quarantine(pages_in_force()).tracking()`, working meta = + `g`'s. `write_chunk(facts)`: the checks (decision 18), stamp (`tx_id`, `tx_count`, + default `valid_from`), a new `Encoder` from the working counters staging against + `DictReader::new(working.dict_root, ..)` with no `SharedDictCache`, `finish`, the + cross-chunk check (decision 17), `cow_update` on the five working roots with no deletes, + replaced pages released or `freed` (decision 16), working counters and `fact_count` + updated. `commit(pending)`: the pending store's facts (`get_pending_facts`) as one more + chunk (own `tx_count`s, own `Encoder`, no checks), `finish_free_list(freed)`, `sync`, + meta `g + 1` with `last_checkpointed_tx_count = tx_count`, `check_written`, meta write, + `sync` (commit point), `allocate_tx_count` (decision 14), `activate`, `publish(reader, + g + 1, pending_len, freed)`, `dirty = false`. `rollback`: bound `g`, evict, drop the rest. + Unit tests on `MemoryBackend` with chunk sizes 1–4: same records as the small path for + the same statements (fact log), `verify` clean, every page accounted for + (`assert_space_accounted`), pages `g` references never written, a rolled-back + transaction leaves the backend's `g` pages and the active meta unchanged, a generation + pinned before `begin_large` keeps its pages, repeated facts across chunks stored once, + `API-011` across chunks. +13. **`execute_statement`.** After the lock and `refuse_if_failed`: `is_large()` on a `File` + context takes the large path: WAL guard (decision 22), `begin_large(tx_id_now())`, each + chunk through `write_chunk`, `commit`, then `delete_wal`. A statement error rolls back + and `force_dirty`s; a failure marks the handle failed, rolls back and `force_dirty`s. The + open-time dirty rule (decision 23). Tests: `execute` at chunk sizes 1–4 against chunk + size `None` on the same statements (records, `current_tx_count`, `:as-of`), a large + statement with a WAL of earlier entries commits them too and deletes the WAL, a failed + large statement takes no `tx_count` and the next checkpoint writes a meta, reopen after + a WAL with every entry checkpointed writes one meta on the first checkpoint (existing + #457 tests updated for it). +14. **Crash, faults, isolation.** Fault matrix (`src/fault_matrix.rs`): `Op::LargeTransact` + on a file with one valid meta slot (new, never checkpointed) and with both, each with and + without a WAL beforehand, chunk size 4, a large `X` with long values, a repeat and a + retraction; `is_whole_x` for it. `tests/crash_kill_test.rs`, under `test-oracle`: a + variant whose child sets the chunk size to 2, so most transactions are large, and runs a + statement that fails `API-011` in pass 2 every few transactions (a rollback with pages + written, not logged); the kill lands during a large transaction, after its commit point, + or after a rollback before the next checkpoint. A unit test reproduces spec §4.5: a large + transaction killed after writing pages on a new file reopens (WAL base `g`) and, without + the guard WAL, is `STG-033`. Cursor and fact log opened before, during (between chunks, + from a test hook in `write_chunk`) and after a large transaction see their snapshot + only. `tests/model_based_test.rs` under `test-oracle` runs with the chunk size at 2 (spec §8.1: 3), so its retractions, of 1–3 facts, are large too. +15. **Acceptance and docs.** `tests/large_transaction_acceptance_test.rs` (`test-oracle`, + ignored, `.github/workflows/smoke.yml` nightly as `memory_limit_acceptance_test` is): a + 1M-fact `transact` on a file database; the high-water mark is at most `TX_CHUNK_FACTS`; + peak RSS (`VmHWM`) printed. Test counts in `CLAUDE.md` and `docs/TEST_COVERAGE.md`; + `CLAUDE.md`'s module notes for `large_tx.rs`. No `CHANGELOG.md` or docs-site change + (PR 3). + +## PR 3 + +Planned in detail when PR 2 is merged, against the code it leaves: spec §5 and §7, the large +path for every `WriteTransaction` statement (decision 12), 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 3a9d031dd8..6a2d274a44 100644 --- a/src/db.rs +++ b/src/db.rs @@ -557,7 +557,7 @@ impl Minigraf { } else { None }; - let pfs = if opts.read_only { + let mut pfs = if opts.read_only { PersistentFactStorage::open_read_only(backend, opts.page_cache_size, wal_base)? } else { PersistentFactStorage::open(backend, opts.page_cache_size, wal_base)? @@ -581,6 +581,12 @@ impl Minigraf { // Open the WAL writer only if the WAL file already exists from a previous session. // Otherwise, create it lazily on the first write. let wal = if wal_path.exists() { + // A WAL is deleted only after a meta of a later generation than + // its base is durable: the first checkpoint commits one even with + // nothing to write. A large transaction that crashed left pages of + // `g + 1` behind this WAL, and without it a file with one valid + // meta slot would be refused (#550 spec §4.5). + pfs.force_dirty(); Some(WalWriter::open_or_create_at( &wal_path, opts.synchronous, @@ -776,6 +782,11 @@ impl Minigraf { .lock() .map_err(|_| err_coded!(ErrorCode::Api001))?; + #[cfg(not(target_arch = "wasm32"))] + if statement.is_large() && matches!(*ctx, WriteContext::File { .. }) { + return self.execute_large(&mut ctx, statement, kind); + } + let stamped = statement.facts()?; let is_retract = kind == Kind::Retract; // Before allocating: a rejected transaction takes no tx_count. @@ -827,6 +838,73 @@ impl Minigraf { } } + /// A statement with more facts than one chunk, on a file database (#550 + /// spec §4): written a chunk at a time into copy-on-write working trees + /// and committed as a checkpoint, with no WAL entry. Its `tx_id` is the + /// time it became large. + #[cfg(not(target_arch = "wasm32"))] + fn execute_large( + &self, + ctx: &mut WriteContext, + statement: statement::Statement<'_>, + kind: Kind, + ) -> Result { + use crate::storage::persistent_facts::ChunkError; + let chunks = statement.chunks()?; + refuse_if_failed(ctx)?; + let WriteContext::File { + pfs, + wal, + db_path, + wal_entry_count, + } = ctx + else { + bail_coded!(ErrorCode::Int019, "a large statement without a file"); + }; + // The WAL guard: a crash before the commit point finds a WAL whose + // base is this generation, never an orphan `g + 1` page (§4.5). + Self::open_wal( + wal, + db_path, + self.inner.options.synchronous, + pfs.generation(), + )?; + let mut tx = pfs.begin_large(crate::graph::types::tx_id_now())?; + for chunk in chunks { + let written = match chunk { + Ok(mut chunk) => pfs.write_large_chunk(&mut tx, &mut chunk), + Err(e) => Err(ChunkError::Statement(e)), + }; + if let Err(ChunkError::Statement(e) | ChunkError::Failure(e)) = written { + pfs.rollback_large(tx); + return Err(e); + } + } + let tx_id = tx.tx_id(); + pfs.commit_large(tx)?; + Self::delete_wal(wal, db_path, wal_entry_count)?; + Ok(match kind { + Kind::Retract => QueryResult::Retracted(tx_id), + Kind::Transact => QueryResult::Transacted(tx_id), + }) + } + + /// The WAL writer, opening the file (or creating it with the header only, + /// base generation `generation`) if it is not open. + #[cfg(not(target_arch = "wasm32"))] + fn open_wal<'w>( + wal: &'w mut Option, + db_path: &Path, + sync: SyncMode, + generation: u64, + ) -> Result<&'w mut WalWriter> { + if wal.is_none() { + let wal_path = Self::wal_path_for(db_path); + *wal = Some(WalWriter::open_or_create_at(&wal_path, sync, generation)?); + } + wal.as_mut().ok_or_else(|| err_coded!(ErrorCode::Api009)) + } + /// The executor for a read-only command: no lock, the database's limits, /// every read from `snapshot`. fn read_executor(&self, snapshot: Snapshot) -> DatalogExecutor { @@ -1111,6 +1189,16 @@ impl Minigraf { self.inner.fact_storage.snapshot() } + /// The active meta page's generation (0 without a file), for tests that + /// check when a checkpoint commits. + #[cfg(all(test, not(target_arch = "wasm32")))] + pub(crate) fn generation(&self) -> u64 { + match &*self.inner.write_lock.lock().unwrap() { + WriteContext::File { pfs, .. } | WriteContext::ReadOnly { pfs } => pfs.generation(), + WriteContext::Memory => 0, + } + } + /// End the handle as a killed process would: no close-time checkpoint and /// no save on drop. Whatever reached the file stays; the lock is released. #[cfg(all(test, not(target_arch = "wasm32")))] @@ -1653,16 +1741,8 @@ impl<'a> WriteTransaction<'a> { wal_entry_count, } => { // Lazily open the WAL writer if not already open. - if wal.is_none() { - let wal_path = Minigraf::wal_path_for(db_path); - *wal = Some(WalWriter::open_or_create_at( - &wal_path, - opts.synchronous, - pfs.generation(), - )?); - } - - let wal_writer = wal.as_mut().ok_or_else(|| err_coded!(ErrorCode::Api009))?; + let wal_writer = + Minigraf::open_wal(wal, db_path, opts.synchronous, pfs.generation())?; wal_writer.append_entry(tx_count, facts)?; pfs.mark_dirty(); *wal_entry_count = wal_entry_count.saturating_add(1); diff --git a/src/fault_matrix.rs b/src/fault_matrix.rs index 222fac6185..dae29c54dc 100644 --- a/src/fault_matrix.rs +++ b/src/fault_matrix.rs @@ -60,18 +60,44 @@ enum Op { Close, /// `rebuild_indexes()` with entries pending. Rebuild, + /// A large transaction (#550): chunks written into working trees and + /// committed as a checkpoint. `one_slot`: on a file never checkpointed, + /// with one valid meta slot; else on the file `build` makes. `wal`: with + /// entries pending in the WAL beforehand, else with no WAL. + Large { one_slot: bool, wal: bool }, } impl Op { /// Whether the operation writes its own transaction (`X`). fn writes_x(self) -> bool { - matches!(self, Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint) + matches!( + self, + Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint | Op::Large { .. } + ) + } + + /// The transaction the operation writes, and how many records it leaves. + fn x(self) -> (&'static str, usize) { + match self { + Op::Large { .. } => (X_LARGE, X_LARGE_FACTS), + _ => (X, X_FACTS), + } } } const X: &str = r#"(transact [[:x1 :p/x 1] [:x1 :p/x 2] [:x2 :p/xlong "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"]])"#; const X_FACTS: usize = 3; +/// A large transaction at a chunk size of [`LARGE_CHUNK`]: several values of +/// one attribute, long values shared by two facts, and a repeated fact, which +/// is stored once. +const X_LARGE: &str = r#"(transact [[:x1 :p/x 1] [:x1 :p/x 2] [:x1 :p/x 3] + [:x2 :p/xlong "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"] + [:x3 :p/xlong "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"] + [:x4 :p/x 4] [:x5 :p/x 5] [:x1 :p/x 1] [:x6 :p/xref :x1] [:x7 :p/x 7] [:x8 :p/x 8]])"#; +const X_LARGE_FACTS: usize = 10; +const LARGE_CHUNK: usize = 3; + fn open(path: &Path, op: Op) -> Minigraf { let threshold = if op == Op::AutoCheckpoint { 3 } else { 1000 }; OpenOptions::new() @@ -104,6 +130,18 @@ fn bulk(prefix: &str, n: usize) -> String { /// `TransactNewWal`, two entries pending in the WAL. fn build(path: &Path, op: Op) -> Minigraf { let db = open(path, op); + if let Op::Large { + one_slot: true, + wal, + } = op + { + if wal { + db.execute(&bulk("c", 20)).unwrap(); + db.execute(r#"(transact [[:e1 :p/tag "c"] [:e3 :p/ref :e1]])"#) + .unwrap(); + } + return db; + } db.execute(&bulk("a", 150)).unwrap(); db.execute(r#"(transact [[:e1 :p/tag "a"] [:e1 :p/tag "b"] [:e2 :p/n 1]])"#) .unwrap(); @@ -112,7 +150,7 @@ fn build(path: &Path, op: Op) -> Minigraf { db.execute(r#"(retract [[:e1 :p/tag "a"] [:a7 :p/n 7]])"#) .unwrap(); db.checkpoint().unwrap(); - if op != Op::TransactNewWal { + if !matches!(op, Op::TransactNewWal | Op::Large { wal: false, .. }) { db.execute(&bulk("c", 20)).unwrap(); db.execute(r#"(transact [[:e1 :p/tag "c"] [:e3 :p/ref :e1]])"#) .unwrap(); @@ -130,9 +168,9 @@ fn extra(before: &[Rec], after: &[Rec]) -> Option> { Some(rest) } -/// Whether `recs` is exactly one whole `X` transaction. -fn is_whole_x(recs: &[Rec]) -> bool { - recs.len() == X_FACTS +/// Whether `recs` is exactly one whole `X` transaction of `op`. +fn is_whole_x(recs: &[Rec], op: Op) -> bool { + recs.len() == op.x().1 && recs.iter().all(|r| r.1.starts_with(":p/x") && r.7) && recs.iter().all(|r| r.3 == recs[0].3) } @@ -146,7 +184,7 @@ fn reopen_and_check(path: &Path, op: Op, live: &[Rec], x_failed: bool) { let reopened = snapshot(&db); let more = extra(live, &reopened).expect("a fact the handle held was lost"); assert!( - more.is_empty() || (x_failed && is_whole_x(&more)), + more.is_empty() || (x_failed && is_whole_x(&more, op)), "reopened file holds facts the handle never committed, or part of one" ); let report = db.verify().unwrap(); @@ -176,6 +214,11 @@ fn run(op: Op, f: Fault) -> u64 { Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint => { (db.execute(X).map(|_| ()), Some(db)) } + Op::Large { .. } => { + let _chunk = + crate::query::datalog::parser::statement::set_tx_chunk_facts(Some(LARGE_CHUNK)); + (db.execute(X_LARGE).map(|_| ()), Some(db)) + } Op::Checkpoint => (db.checkpoint(), Some(db)), Op::Rebuild => (db.rebuild_indexes(), Some(db)), Op::Close => { @@ -191,11 +234,14 @@ fn run(op: Op, f: Fault) -> u64 { let applied = extra(&before, &live).expect("the handle lost a fact"); if op.writes_x() { assert!( - applied.is_empty() || is_whole_x(&applied), + applied.is_empty() || is_whole_x(&applied, op), "the handle applied part of a transaction" ); if result.is_ok() { - assert!(is_whole_x(&applied), "a committed transaction is missing"); + assert!( + is_whole_x(&applied, op), + "a committed transaction is missing" + ); } } else { assert!(applied.is_empty(), "a checkpoint changed the facts"); @@ -285,6 +331,40 @@ fn faults_during_rebuild_indexes() { run_all(Op::Rebuild); } +#[test] +fn faults_during_a_large_transaction() { + run_all(Op::Large { + one_slot: false, + wal: true, + }); +} + +#[test] +fn faults_during_a_large_transaction_that_creates_the_wal() { + run_all(Op::Large { + one_slot: false, + wal: false, + }); +} + +/// One valid meta slot: without the WAL guard, a fault after the first page +/// write would leave a file refused with STG-033 (#550 spec §4.5). +#[test] +fn faults_during_a_large_transaction_on_a_new_file() { + run_all(Op::Large { + one_slot: true, + wal: false, + }); +} + +#[test] +fn faults_during_a_large_transaction_on_a_new_file_with_a_wal() { + run_all(Op::Large { + one_slot: true, + wal: true, + }); +} + /// The disk fills part-way through a checkpoint: every write from then on /// fails. The checkpoint fails, the handle refuses writes with STG-046, and /// after space is freed a reopen holds every committed fact. diff --git a/src/lib.rs b/src/lib.rs index 035e0182cd..bdb1936bb2 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -135,6 +135,29 @@ pub fn __reorder(on: bool) -> ReorderGuard { query::datalog::optimizer::set_reorder(on) } +// Large-transaction tests (#550): statements read and written in small chunks. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub use query::datalog::parser::statement::TxChunkGuard; + +/// Sets how many facts a `transact` or `retract` materialises at once on this +/// thread until the returned guard drops (`None`: the built-in size), so a +/// statement with more facts takes the large-transaction path (#550). Only +/// for tests; built with the `test-oracle` feature only. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub fn __tx_chunk_facts(n: Option) -> TxChunkGuard { + query::datalog::parser::statement::set_tx_chunk_facts(n) +} + +/// The most materialised statement facts this thread held at once since the +/// last call (#550 acceptance). Built with the `test-oracle` feature only. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub fn __statement_facts_high_water() -> usize { + query::datalog::parser::statement::take_held_high_water() +} + // Plan-independence tests (#546): force how negation bodies and `or` branches run. #[cfg(feature = "test-oracle")] #[doc(hidden)] diff --git a/src/query/datalog/parser/statement.rs b/src/query/datalog/parser/statement.rs index a0cf4e076c..5d5ced9bde 100644 --- a/src/query/datalog/parser/statement.rs +++ b/src/query/datalog/parser/statement.rs @@ -22,26 +22,103 @@ use anyhow::Result; /// is read again in chunks of this many (spec §3.3). const TX_CHUNK_FACTS: usize = 16_384; -#[cfg(test)] +#[cfg(any(test, feature = "test-oracle"))] thread_local! { static CHUNK_FACTS: std::cell::Cell> = const { std::cell::Cell::new(None) }; + /// Facts in [`Chunk`]s alive on this thread, and the most there have been. + static HELD: std::cell::Cell<(usize, usize)> = const { std::cell::Cell::new((0, 0)) }; } /// 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)); +/// pass 2 and the large path with small statements. +#[cfg(any(test, feature = "test-oracle"))] +pub(crate) fn set_tx_chunk_facts(n: Option) -> TxChunkGuard { + TxChunkGuard(CHUNK_FACTS.with(|c| c.replace(n))) +} + +/// Restores the previous [`set_tx_chunk_facts`] setting on drop. +#[cfg(any(test, feature = "test-oracle"))] +#[must_use = "the chunk size is restored when the guard drops"] +pub struct TxChunkGuard(Option); + +#[cfg(any(test, feature = "test-oracle"))] +impl Drop for TxChunkGuard { + fn drop(&mut self) { + CHUNK_FACTS.with(|c| c.set(self.0)); + } } -fn tx_chunk_facts() -> usize { - #[cfg(test)] +/// The most facts [`Chunk`]s held at once on this thread since the last call +/// (#550 spec §8.1 acceptance), then start counting again from those held now. +#[cfg(any(test, feature = "test-oracle"))] +pub(crate) fn take_held_high_water() -> usize { + HELD.with(|h| { + let (now, high) = h.get(); + h.set((now, now)); + high + }) +} + +pub(crate) fn tx_chunk_facts() -> usize { + #[cfg(any(test, feature = "test-oracle"))] if let Some(n) = CHUNK_FACTS.with(std::cell::Cell::get) { return n.max(1); } TX_CHUNK_FACTS } +/// At most one chunk of a statement's materialised facts. With `test` or +/// `test-oracle`, the facts alive in chunks are counted for the acceptance +/// test's high-water mark. +pub(crate) struct Chunk(Vec); + +impl Chunk { + fn new(facts: Vec) -> Self { + #[cfg(any(test, feature = "test-oracle"))] + HELD.with(|h| { + let (now, high) = h.get(); + let now = now.saturating_add(facts.len()); + h.set((now, high.max(now))); + }); + Chunk(facts) + } + + /// The facts, no longer counted. + pub(crate) fn into_vec(mut self) -> Vec { + let facts = std::mem::take(&mut self.0); + #[cfg(any(test, feature = "test-oracle"))] + HELD.with(|h| { + let (now, high) = h.get(); + h.set((now.saturating_sub(facts.len()), high)); + }); + facts + } +} + +#[cfg(any(test, feature = "test-oracle"))] +impl Drop for Chunk { + fn drop(&mut self) { + let n = self.0.len(); + HELD.with(|h| { + let (now, high) = h.get(); + h.set((now.saturating_sub(n), high)); + }); + } +} + +impl std::ops::Deref for Chunk { + type Target = [Fact]; + fn deref(&self) -> &[Fact] { + &self.0 + } +} + +impl std::ops::DerefMut for Chunk { + fn deref_mut(&mut self) -> &mut [Fact] { + &mut self.0 + } +} + /// Which statement a command is. #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub(crate) enum Kind { @@ -414,7 +491,7 @@ pub(crate) struct Statement<'a> { defaults: Defaults, chunk: usize, /// The first facts, at most `chunk` of them. - kept: Vec, + kept: Chunk, /// 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, @@ -462,27 +539,67 @@ pub(crate) fn read_statement(input: &str, kind: Kind, tx_id: TxId) -> Result Statement<'a> { + /// Whether the statement has more facts than one chunk (spec §2). + #[cfg(not(target_arch = "wasm32"))] + pub(crate) fn is_large(&self) -> bool { + self.resume.is_some() + } + /// 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> { + let mut facts = Vec::new(); + for chunk in self.chunks()? { + facts.extend(chunk?.into_vec()); + } + Ok(facts) + } + + /// The statement's facts a chunk at a time: the kept facts, then pass 2 + /// from where pass 1 stopped keeping them. Or its phase 5–6 error. + pub(crate) fn chunks(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(Chunks { + kept: Some(self.kept), + rest: self + .resume + .map(|pos| Pass2::new(self.input, pos, self.kind, self.defaults)), + chunk: self.chunk, + }) + } +} + +/// A statement's facts, one [`Chunk`] at a time ([`Statement::chunks`]). An +/// error ends it. +pub(crate) struct Chunks<'a> { + kept: Option, + rest: Option>, + chunk: usize, +} + +impl Iterator for Chunks<'_> { + type Item = Result; + + fn next(&mut self) -> Option> { + if let Some(kept) = self.kept.take() + && !kept.is_empty() + { + return Some(Ok(kept)); } - Ok(facts) + let next = self.rest.as_mut()?.next_chunk(self.chunk); + if !matches!(next, Ok(Some(_))) { + self.rest = None; + } + next.transpose() } } @@ -505,7 +622,7 @@ impl<'a> Pass2<'a> { /// 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>> { + fn next_chunk(&mut self, chunk: usize) -> Result> { let Some(p) = self.parser.as_mut() else { return Ok(None); }; @@ -528,7 +645,7 @@ impl<'a> Pass2<'a> { let pattern = fact_pattern(self.kind, &fact, self.defaults)?; facts.push(materialize(self.kind, &pattern)?); } - Ok((!facts.is_empty()).then_some(facts)) + Ok((!facts.is_empty()).then(|| Chunk::new(facts))) } } @@ -590,9 +707,10 @@ mod tests { 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); + let new = { + let _chunk = set_tx_chunk_facts(chunk); + outcome(new_write(input, kind, tx_id)) + }; assert!(old == new, "write differs at chunk {chunk:?}: {input}"); } old.map(|facts| facts.len()).map_err(|(code, _)| code) @@ -764,9 +882,10 @@ mod tests { #[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); + let statement = { + let _chunk = set_tx_chunk_facts(Some(2)); + read_statement(input, Kind::Transact, 1).unwrap() + }; assert_eq!(statement.kept.len(), 2, "kept facts"); let resume = statement.resume.expect("large"); assert_eq!( @@ -778,14 +897,71 @@ mod tests { .map(|c| c.len()) .collect(); assert_eq!(sizes, vec![2, 1], "chunk sizes"); + #[cfg(not(target_arch = "wasm32"))] + assert!(statement.is_large()); + let sizes: Vec = statement + .chunks() + .unwrap() + .map(|c| c.unwrap().len()) + .collect(); + assert_eq!(sizes, vec![2, 2, 1], "kept facts, then pass 2"); - set_tx_chunk_facts(Some(5)); - let exact = read_statement(input, Kind::Transact, 1).unwrap(); - set_tx_chunk_facts(None); + let exact = { + let _chunk = set_tx_chunk_facts(Some(5)); + read_statement(input, Kind::Transact, 1).unwrap() + }; assert!(exact.resume.is_none(), "five facts fit a chunk of five"); assert_eq!(exact.facts().unwrap().len(), 5, "facts"); } + #[test] + fn chunks_hold_at_most_one_chunk_of_facts_at_once() { + let input: String = (0..10).map(|i| format!("[:a :n {i}]")).collect(); + let input = format!("(transact [{input}])"); + let _chunk = set_tx_chunk_facts(Some(3)); + let _ = take_held_high_water(); + let statement = read_statement(&input, Kind::Transact, 1).unwrap(); + let mut n = 0; + for chunk in statement.chunks().unwrap() { + n += chunk.unwrap().len(); + } + assert_eq!(n, 10); + assert_eq!(take_held_high_water(), 3, "one chunk at a time"); + let held: Vec = read_statement(&input, Kind::Transact, 1) + .unwrap() + .chunks() + .unwrap() + .map(Result::unwrap) + .collect(); + assert_eq!(held.len(), 4); + assert_eq!(take_held_high_water(), 10, "every chunk kept is counted"); + drop(held); + assert_eq!(take_held_high_water(), 10, "held when the count restarted"); + assert_eq!(take_held_high_water(), 0, "dropped chunks are not counted"); + } + + #[test] + fn a_pass_2_error_ends_the_chunks() { + // Pass 1 never sees this input past the kept facts: pass 2 resumes + // into a string a test cuts short. + let input = "(transact [[:a :n 1] [:a :n 2] [:a :n 3]])"; + let statement = { + let _chunk = set_tx_chunk_facts(Some(1)); + read_statement(input, Kind::Transact, 1).unwrap() + }; + let short = &input[..input.len() - 8]; + let mut chunks = Chunks { + kept: None, + rest: statement + .resume + .map(|pos| Pass2::new(short, pos, Kind::Transact, Defaults::default())), + chunk: 1, + }; + assert_eq!(chunks.next().unwrap().unwrap().len(), 1); + assert!(chunks.next().unwrap().is_err(), "cut short"); + assert!(chunks.next().is_none(), "nothing after an error"); + } + #[test] fn materialisation_and_window_errors_come_with_the_facts() { let code = |r: Result>| MinigrafError::from(r.unwrap_err()).code(); diff --git a/src/storage/btree.rs b/src/storage/btree.rs index a35b09d3a2..adde52e41f 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -641,6 +641,23 @@ impl<'a> LeafCursor<'a> { } } + /// The next entry in key order without moving past it, or `None` past + /// the last one. + #[cfg(not(target_arch = "wasm32"))] + pub(crate) fn peek_ref(&mut self) -> Result> { + loop { + if self.done { + return Ok(None); + } + if self.pos < self.entries.len() { + return Ok(self.entries.get(self.pos)); + } + if !self.advance_leaf()? { + return Ok(None); + } + } + } + /// Like [`next_ref`](Self::next_ref), but clones the entry. #[cfg(test)] pub(crate) fn next(&mut self) -> Result> { @@ -1202,6 +1219,28 @@ mod tests { assert!(seen.is_empty(), "no key below the target"); } + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn peek_returns_the_next_entry_across_leaves_without_consuming_it() { + let (backend, cache, root, leaves) = multi_leaf_tree(); + let leaf0 = leaf_keys(leaves[0], &backend, &cache); + let leaf1 = leaf_keys(leaves[1], &backend, &cache); + let mut cursor = + LeafCursor::new(root, leaf0.last().map(Vec::as_slice), &backend, &cache).unwrap(); + assert_eq!( + cursor.next_ref().unwrap().unwrap().0, + *leaf0.last().unwrap() + ); + for _ in 0..2 { + assert_eq!(cursor.peek_ref().unwrap().unwrap().0, leaf1[0], "next leaf"); + } + assert_eq!( + cursor.next_ref().unwrap().unwrap().0, + leaf1[0], + "not consumed" + ); + } + #[test] fn cursor_into_an_empty_leaf_below_the_root_is_int_049() { let (mut backend, cache, root, leaves) = multi_leaf_tree(); diff --git a/src/storage/cache.rs b/src/storage/cache.rs index 427d2592af..6fff543279 100644 --- a/src/storage/cache.rs +++ b/src/storage/cache.rs @@ -203,6 +203,15 @@ impl PageCache { inner.order.retain(|&id| id != page_id); } + /// Remove every page in `ids` from the cache, in one pass over the LRU + /// order: the pages a rolled-back large transaction wrote (#550 spec §4.4). + #[cfg(not(target_arch = "wasm32"))] + pub fn evict(&self, ids: &std::collections::HashSet) { + let mut inner = self.inner.write().unwrap_or_else(|e| e.into_inner()); + inner.entries.retain(|id, _| !ids.contains(id)); + inner.order.retain(|id| !ids.contains(id)); + } + /// Number of pages currently cached (for testing). #[allow(dead_code)] pub fn cached_page_count(&self) -> usize { @@ -460,4 +469,18 @@ mod tests { cache.get_or_load(1, &backend).unwrap(); assert_eq!(cache.cached_page_count(), 1); } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn evict_drops_only_the_given_pages() { + let cache = PageCache::new(8); + for id in 1..=4 { + cache.put_dirty(id, make_page(id, 0x11)); + } + cache.evict(&[2, 4, 9].into()); + assert_eq!(cache.cached_page_count(), 2); + let backend = MemoryBackend::new(); + assert!(cache.get_or_load(2, &backend).is_err(), "2 is read again"); + assert_eq!(cache.get_or_load(1, &backend).unwrap()[MARK], 0x11); + } } diff --git a/src/storage/page.rs b/src/storage/page.rs index 994c1c1b52..26b57aad03 100644 --- a/src/storage/page.rs +++ b/src/storage/page.rs @@ -188,6 +188,8 @@ pub struct PageAllocator { chain_bound: u64, next_append: u64, generation: u64, + /// Every id handed out since [`tracking`](Self::tracking), when on. + handed: Option>, } impl PageAllocator { @@ -205,6 +207,7 @@ impl PageAllocator { chain_bound: next_append, next_append, generation, + handed: None, } } @@ -221,6 +224,7 @@ impl PageAllocator { chain_bound: next_append, next_append, generation, + handed: None, } } @@ -234,6 +238,35 @@ impl PageAllocator { self } + /// Record every id handed out from now on, for [`handed`](Self::handed) and + /// [`handed_ids`](Self::handed_ids): a large transaction tells the pages + /// it wrote from those generation `g` references (#550 spec §4.2). + #[cfg(not(target_arch = "wasm32"))] + pub fn tracking(mut self) -> Self { + self.handed = Some(std::collections::HashSet::new()); + self + } + + /// Whether `id` was handed out since [`tracking`](Self::tracking). + #[cfg(not(target_arch = "wasm32"))] + pub fn handed(&self, id: u64) -> bool { + self.handed.as_ref().is_some_and(|h| h.contains(&id)) + } + + /// Every id handed out since [`tracking`](Self::tracking), released or not. + #[cfg(not(target_arch = "wasm32"))] + pub fn handed_ids(&self) -> Option<&std::collections::HashSet> { + self.handed.as_ref() + } + + /// Hand `id` out again, next: a page this allocator handed out that no + /// tree references any more (#550 spec §4.2 step 3). If it is not handed + /// out again, [`finish_free_list`](Self::finish_free_list) lists it free. + #[cfg(not(target_arch = "wasm32"))] + pub fn release(&mut self, id: u64) { + self.free.push(id); + } + /// The generation every page written through this allocator is stamped with. #[cfg(test)] pub fn generation(&self) -> u64 { @@ -258,6 +291,9 @@ impl PageAllocator { self.skipped.push(id); continue; } + if let Some(h) = self.handed.as_mut() { + h.insert(id); + } return Ok(id); } if self.chain_next == 0 { @@ -286,6 +322,9 @@ impl PageAllocator { self.next_append = id .checked_add(1) .ok_or_else(|| err_coded!(ErrorCode::Int048, "page id overflow"))?; + if let Some(h) = self.handed.as_mut() { + h.insert(id); + } Ok(id) } @@ -492,4 +531,48 @@ mod tests { want.sort_unstable(); assert_eq!(read, want); } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn tracking_records_every_id_handed_out_and_release_hands_it_out_next() { + let b = crate::storage::backend::MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); + let mut a = PageAllocator::new(vec![4, 7, 9], 20, 2); + assert_eq!(a.alloc(&b, &c).unwrap(), 4); + let mut a = a.tracking(); + assert_eq!(a.alloc(&b, &c).unwrap(), 7); + assert_eq!(a.alloc_append().unwrap(), 20); + assert!(!a.handed(4), "handed out before tracking"); + assert!(a.handed(7)); + assert!(a.handed(20)); + assert!(!a.handed(9), "never handed out"); + + a.release(20); + assert_eq!(a.alloc(&b, &c).unwrap(), 20, "a released id comes next"); + a.release(7); + assert_eq!( + a.handed_ids().unwrap().len(), + 2, + "released ids stay recorded" + ); + assert_eq!( + a.take_unused_free(), + vec![7, 9], + "an unused released id is free" + ); + } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn a_released_id_not_handed_out_again_stays_free() { + let mut b = crate::storage::backend::MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); + let mut a = PageAllocator::new(Vec::new(), 10, 2).tracking(); + let id = a.alloc(&b, &c).unwrap(); + a.release(id); + let (head, _, listed) = a.finish_free_list(vec![], &mut b, &c).unwrap(); + // The new list's one page: handed out again, not leaked. + assert_eq!(head, id, "the released id holds the new free list"); + assert!(listed.is_empty()); + } } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 172dd3327e..d5ee113f44 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -26,6 +26,11 @@ use anyhow::Result; // and the native coverage report, never see it. #[cfg(all(target_arch = "wasm32", feature = "browser"))] mod browser_access; +// Large transactions (#550): file databases only. +#[cfg(not(target_arch = "wasm32"))] +mod large_tx; +#[cfg(not(target_arch = "wasm32"))] +pub(crate) use large_tx::ChunkError; use std::sync::{Arc, Mutex}; /// Persistent fact storage with page-based persistence. diff --git a/src/storage/persistent_facts/large_tx.rs b/src/storage/persistent_facts/large_tx.rs new file mode 100644 index 0000000000..30500e6516 --- /dev/null +++ b/src/storage/persistent_facts/large_tx.rs @@ -0,0 +1,776 @@ +//! Large transactions (#550, spec `2026-10-21-streaming-transactions-design.md` +//! §4): a transaction with more facts than one chunk writes them, a chunk at a +//! time, into copy-on-write working trees, and commits as a checkpoint. +//! +//! The working trees start as generation `g`'s and become generation `g + 1`'s +//! at commit. Every page they gain comes from an allocator that hands out only +//! ids `g` does not reference, so generation `g` and every reader of it are +//! untouched until the commit point, the meta page write, and after a rollback. +//! The caller holds the database's write lock throughout. + +use super::PersistentFactStorage; +use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::graph::storage::{check_one_window_per_triple, check_valid_windows}; +use crate::graph::types::{Fact, TxId}; +use crate::storage::StorageBackend; +use crate::storage::btree::{LeafCursor, cow_update}; +use crate::storage::cache::PageCache; +use crate::storage::dict::{DictReader, Encoded, Encoder}; +use crate::storage::keys::{self, Index, KeyFact}; +use crate::storage::meta::{MetaPage, slot_page}; +use crate::storage::node::Entry; +use crate::storage::page::PageAllocator; +use anyhow::Result; +use std::collections::HashSet; + +/// A large transaction in progress: generation `g`'s meta, the working state +/// that becomes `g + 1`'s, and the pages it has written. +pub(crate) struct LargeTx { + /// Generation `g`'s meta, active while the transaction runs. + base: MetaPage, + /// The working roots, counters and fact count, as generation `g + 1`. + work: MetaPage, + /// Hands out only ids `g` does not reference, and records them. + alloc: PageAllocator, + /// Pages `g` references that the working trees replaced. + freed: Vec, + tx_count: u64, + tx_id: TxId, +} + +/// How a chunk failed. +pub(crate) enum ChunkError { + /// The statement is rejected (`API-011`, `API-019`, `WAL-003`): roll back, + /// the handle stays usable. + Statement(anyhow::Error), + /// A write or read failed after pages may have been written: the handle + /// is failed (`STG-046`); roll back. + Failure(anyhow::Error), +} + +impl LargeTx { + /// The transaction time every fact is stamped with, fixed when the + /// transaction became large. + pub(crate) fn tx_id(&self) -> TxId { + self.tx_id + } +} + +impl PersistentFactStorage { + /// Make the current transaction large (spec §4.1 steps 2–4): raise the + /// cache's generation bound to `g + 1`, reserve the next `tx_count`, and + /// build the allocator. The caller has created the WAL guard (step 1). + /// + /// The `tx_count` is the next one; it is allocated at the commit point, + /// so a transaction that rolls back takes none (plan decision 14). + pub(crate) fn begin_large(&mut self, tx_id: TxId) -> Result { + self.refuse_if_failed()?; + let base = self.meta; + let next = base.next_generation()?; + let tx_count = self + .storage + .current_tx_count() + .checked_add(1) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "tx_count overflow"))?; + let alloc = PageAllocator::from_chain( + base.freelist_head, + base.freelist_count, + base.page_count, + next, + ) + .with_quarantine(self.storage.pages_in_force()) + .tracking(); + self.page_cache.set_generation_bound(next); + Ok(LargeTx { + base, + work: MetaPage { + generation: next, + ..base + }, + alloc, + freed: Vec::new(), + tx_count, + tx_id, + }) + } + + /// Write one chunk of the statement (spec §4.2): check it, stamp it with + /// the transaction's `tx_count` and `tx_id`, encode it against the + /// working dictionary and apply it to the working trees. + /// + /// A [`ChunkError::Failure`] has already marked the handle failed. + pub(crate) fn write_large_chunk( + &mut self, + tx: &mut LargeTx, + facts: &mut [Fact], + ) -> std::result::Result<(), ChunkError> { + // Checks first, before this chunk writes anything: a rejected + // statement is not a failure. + check_chunk(facts, tx.tx_id).map_err(ChunkError::Statement)?; + for f in facts.iter_mut() { + f.tx_id = tx.tx_id; + f.tx_count = tx.tx_count; + if f.asserted && f.valid_from == crate::db::VALID_FROM_USE_TX_TIME { + f.valid_from = tx.tx_id.cast_signed(); + } + } + let result = self.apply_chunk(tx, facts, true); + if let Err(ChunkError::Failure(_)) = &result { + self.failed = true; + } + #[cfg(test)] + if result.is_ok() { + tests::after_chunk(); + } + result + } + + /// Commit the transaction as a checkpoint (spec §4.3): the pending store's + /// facts join the working trees, the free list is written, and the meta + /// page of `g + 1` is the commit point. The caller deletes the WAL next. + /// + /// On an error the handle is failed (`STG-046`) and the in-memory state is + /// rolled back; the file holds `g`, or `g + 1` complete if the meta page + /// reached it. + pub(crate) fn commit_large(&mut self, mut tx: LargeTx) -> Result<()> { + self.failed = true; + match self.commit_large_inner(&mut tx) { + Ok(()) => { + self.failed = false; + Ok(()) + } + Err(e) => { + // Dirty, so a checkpoint is refused (STG-046) rather than + // deleting the WAL guard without a meta. + self.rollback_large(tx); + Err(e) + } + } + } + + fn commit_large_inner(&mut self, tx: &mut LargeTx) -> Result<()> { + let mut pending = self.storage.get_pending_facts(); + let pending_len = pending.len(); + // Their own tx_counts and statement rules: only encoded and inserted. + match self.apply_chunk(tx, &mut pending, false) { + Ok(()) => {} + Err(ChunkError::Statement(e) | ChunkError::Failure(e)) => return Err(e), + } + drop(pending); + + let mut backend = self.lock()?; + let (freelist_head, freelist_count, _) = + tx.alloc + .finish_free_list(tx.freed.clone(), &mut *backend, &self.page_cache)?; + backend.sync()?; + let new_meta = MetaPage { + page_count: tx.alloc.next_append(), + last_checkpointed_tx_count: tx.tx_count, + freelist_head, + freelist_count, + ..tx.work + }; + super::check_written(&*backend, &new_meta)?; + backend.write_page(slot_page(new_meta.generation), &new_meta.encode())?; + backend.sync()?; + drop(backend); + + // Committed. No other writer runs under the write lock, so the + // reserved tx_count is the next one. + let tx_count = self.storage.allocate_tx_count(); + if tx_count != tx.tx_count { + bail_coded!( + ErrorCode::Int049, + format!("tx_count {tx_count} allocated, {} reserved", tx.tx_count) + ); + } + self.dirty = false; + let reader = self.activate(new_meta); + self.storage.publish( + reader, + new_meta.generation, + pending_len, + std::mem::take(&mut tx.freed), + ); + Ok(()) + } + + /// Roll back (spec §4.4): generation `g` stays active and untouched. The + /// pages written are free in `g` or past its `page_count`. The handle is + /// marked dirty, so its next checkpoint commits a meta before it deletes + /// the WAL guard (§4.5). + pub(crate) fn rollback_large(&mut self, tx: LargeTx) { + self.undo_large(&tx); + self.dirty = true; + } + + /// Set the cache's generation bound back to `g` and drop the pages the + /// transaction wrote from the cache. + fn undo_large(&self, tx: &LargeTx) { + self.page_cache.set_generation_bound(tx.base.generation); + if let Some(handed) = tx.alloc.handed_ids() { + self.page_cache.evict(handed); + } + } + + /// Encode `facts` against the working dictionary and apply them to the + /// working trees. With `own`, they are this transaction's: a fact an + /// earlier chunk wrote is kept once, and another window of one of its + /// triples is `API-011`. + fn apply_chunk( + &mut self, + tx: &mut LargeTx, + facts: &mut [Fact], + own: bool, + ) -> std::result::Result<(), ChunkError> { + let failure = ChunkError::Failure; + let mut backend = self.lock().map_err(failure)?; + let cache = &*self.page_cache; + let encoded = + encode(facts, &tx.work, &mut tx.alloc, &mut *backend, cache).map_err(failure)?; + let Encoded { + mut index, + dict, + next_eid, + next_iid, + } = encoded; + if own { + let repeats = repeats(&tx.work, &index[0], tx.tx_count, &*backend, cache)?; + drop_repeats(&mut index, &repeats).map_err(failure)?; + } + let added = u64::try_from(index[0].len()) + .map_err(|_| ChunkError::Failure(err_coded!(ErrorCode::Stg024)))?; + + let mut roots = tx.work.tree_roots(); + for (root, entries) in roots.iter_mut().zip(index.into_iter().chain([dict])) { + let mut replaced = Vec::new(); + *root = cow_update( + *root, + entries, + Vec::new(), + &mut *backend, + cache, + &mut tx.alloc, + &mut replaced, + ) + .map_err(failure)?; + // A page this transaction wrote is referenced by nothing now; a + // page of `g` is freed at commit (spec §4.2 step 3; no statement + // base in a one-statement transaction, plan decision 13). + for id in replaced { + if tx.alloc.handed(id) { + tx.alloc.release(id); + } else { + tx.freed.push(id); + } + } + } + let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; + tx.work = MetaPage { + eavt_root, + aevt_root, + avet_root, + vaet_root, + dict_root, + next_eid, + next_iid, + fact_count: tx.work.fact_count.checked_add(added).ok_or_else(|| { + ChunkError::Failure(err_coded!(ErrorCode::Int048, "fact_count overflow")) + })?, + ..tx.work + }; + Ok(()) + } +} + +/// A chunk's statement checks, before it writes anything (plan decision 18): +/// valid windows at the fixed `tx_id` (`API-019`), one window per triple +/// within the chunk (`API-011`), and the sizes a checkpoint can store +/// (`WAL-003`, as the WAL entry checked them). +fn check_chunk(facts: &[Fact], tx_id: TxId) -> Result<()> { + check_valid_windows(facts, tx_id)?; + check_one_window_per_triple(facts)?; + for f in facts { + crate::wal::check_fact_size(f)?; + } + Ok(()) +} + +/// Assign ids for `facts` against the working dictionary of `work` (with no +/// `SharedDictCache`: the committed reader's cache must never learn an id +/// that is not committed), write their new long values, and build every +/// tree's entries. +fn encode( + facts: &[Fact], + work: &MetaPage, + alloc: &mut PageAllocator, + backend: &mut dyn StorageBackend, + cache: &PageCache, +) -> Result { + let mut encoder = Encoder::new(work.next_eid, work.next_iid); + { + let mut dict = DictReader::new(work.dict_root, &*backend, cache); + for f in facts { + encoder.stage(f, &mut dict)?; + } + } + encoder.finish(alloc, backend, cache) +} + +/// The positions in `eavt` (a chunk's sorted EAVT entries, all of `tx_count`) +/// of facts an earlier chunk of the transaction already wrote to the working +/// trees of `work` (#550 spec §5.2, fast path). Another window of an asserted +/// triple there is `API-011`, as within one statement today. +fn repeats( + work: &MetaPage, + eavt: &[Entry], + tx_count: u64, + backend: &dyn StorageBackend, + cache: &PageCache, +) -> std::result::Result, ChunkError> { + let failure = ChunkError::Failure; + let mut out = Vec::new(); + if work.eavt_root == 0 { + return Ok(out); + } + let mut cursor: Option> = None; + // The working keys of the current triple and this tx_count: one run per + // triple, read once even when the chunk has several records of it. + let mut start: Vec = Vec::new(); + let mut run: Vec> = Vec::new(); + for (i, (key, _)) in eavt.iter().enumerate() { + let triple = keys::triple_len(Index::Eavt, key).map_err(failure)?; + let mut s = key.get(..triple).unwrap_or_default().to_vec(); + keys::put_tx_desc(&mut s, tx_count); + if s != start { + start = s; + run.clear(); + let cursor = match &mut cursor { + Some(c) => { + c.seek(&start).map_err(failure)?; + c + } + None => cursor.insert( + LeafCursor::new(work.eavt_root, Some(&start), backend, cache) + .map_err(failure)?, + ), + }; + while let Some((k, _)) = cursor.peek_ref().map_err(failure)? { + if !k.starts_with(&start) { + break; + } + run.push(k.clone()); + cursor.next_ref().map_err(failure)?; + } + } + let asserted = key.last() == Some(&1); + if run.iter().any(|k| k == key) { + out.push(i); + } else if asserted && run.iter().any(|k| k.last() == Some(&1)) { + let attribute = KeyFact::decode(Index::Eavt, key) + .and_then(|kf| DictReader::new(work.dict_root, backend, cache).name_of(kf.a)) + .map_err(failure)?; + return Err(ChunkError::Statement(err_coded!( + ErrorCode::Api011, + attribute + ))); + } + } + Ok(out) +} + +/// Remove the facts at `positions` of the EAVT entries from all four index +/// trees' entries. +fn drop_repeats(index: &mut [Vec; 4], positions: &[usize]) -> Result<()> { + if positions.is_empty() { + return Ok(()); + } + let mut gone: [HashSet>; 4] = Default::default(); + for &i in positions { + let key = index[0] + .get(i) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "repeat out of range"))?; + let kf = KeyFact::decode(Index::Eavt, &key.0)?; + for (set, idx) in gone.iter_mut().zip(Index::ALL) { + if let Some(k) = kf.key(idx) { + set.insert(k); + } + } + } + for (entries, set) in index.iter_mut().zip(&gone) { + entries.retain(|(k, _)| !set.contains(k)); + } + Ok(()) +} + +#[cfg(test)] +mod tests { + use crate::db::{Minigraf, OpenOptions}; + use crate::fact_log::FactFilter; + use crate::query::datalog::parser::statement::set_tx_chunk_facts; + use std::cell::RefCell; + use std::path::Path; + + thread_local! { + static AFTER_CHUNK: RefCell>> = RefCell::new(None); + } + + /// Run the hook a test set, after each chunk a large transaction writes. + pub(super) fn after_chunk() { + let hook = AFTER_CHUNK.with(|h| h.borrow_mut().take()); + if let Some(mut f) = hook { + f(); + AFTER_CHUNK.with(|h| *h.borrow_mut() = Some(f)); + } + } + + /// One fact version, comparable across databases: a default `valid_from` + /// (the transaction time) is `None`. + type Rec = (String, String, String, u64, Option, i64, bool); + + fn records(db: &Minigraf) -> Vec { + let mut v: Vec = db + .fact_log(&FactFilter::new()) + .unwrap() + .map(|r| { + let r = r.unwrap(); + let default_from = r.valid_from == i64::try_from(r.tx_id).unwrap(); + ( + r.entity.to_string(), + r.attribute, + format!("{:?}", r.value), + r.tx_count, + (!default_from).then_some(r.valid_from), + r.valid_to, + r.asserted, + ) + }) + .collect(); + v.sort(); + v + } + + fn wal_of(path: &Path) -> std::path::PathBuf { + let mut wal = path.as_os_str().to_owned(); + wal.push(".wal"); + wal.into() + } + + fn code(r: Result) -> String { + r.expect_err("rejected").code().to_string() + } + + const LONG: &str = + "llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll"; + + /// Statements covering what a chunk boundary can split: repeats, + /// several values and windows of one attribute, long values shared + /// between facts, refs, keywords, transaction-level windows, retractions + /// of committed and unknown facts, and one-fact statements whose WAL + /// entries are pending when a large statement commits. + fn workload() -> Vec { + vec![ + format!( + r#"(transact [[:a :n 1] [:a :n 2] [:a :n 1] [:b :ref :a] [:b :s "{LONG}"] + [:c :s "{LONG}"] [:a :n 3 {{:valid-from "2020-01-01T00:00:00Z" + :valid-to "2021-01-01T00:00:00Z"}}] [:d :k :kw] [:d :k :kw]])"# + ), + "(transact [[:h :n 1]])".into(), + "(retract [[:a :n 1] [:b :ref :a] [:zz :n 9]])".into(), + r#"(transact {:valid-from "2019-01-01T00:00:00Z"} [[:e :n 1] [:e :n 2] [:e :n 1] [:f :n 5]])"#.into(), + "(transact [[:h :n 2]])".into(), + "(transact [[:a :n 4] [:a :n 4] [:a :n 4]])".into(), + format!( + r#"(transact [[:g :s "{LONG}x"] [:g :s "{LONG}x"] [:a :n 1] [:g :n 1] [:g :n 2]])"# + ), + ] + } + + #[test] + fn large_statements_store_what_small_ones_do() { + let dir = tempfile::tempdir().unwrap(); + let small_path = dir.path().join("small.graph"); + let small = Minigraf::open(&small_path).unwrap(); + for stmt in workload() { + small.execute(&stmt).unwrap(); + } + small.checkpoint().unwrap(); + let want = records(&small); + assert!(want.len() > 10); + + for chunk in 1..=4 { + let path = dir.path().join(format!("large{chunk}.graph")); + let db = Minigraf::open(&path).unwrap(); + { + let _chunk = set_tx_chunk_facts(Some(chunk)); + for stmt in workload() { + db.execute(&stmt).unwrap(); + } + } + assert!(records(&db) == want, "records at chunk {chunk}"); + assert_eq!(db.current_tx_count(), small.current_tx_count()); + assert!(db.verify().unwrap().is_ok(), "verify at chunk {chunk}"); + assert!( + !wal_of(&path).exists(), + "the last large statement committed the WAL's entries" + ); + drop(db); + let db = Minigraf::open(&path).unwrap(); + assert!( + records(&db) == want, + "records after reopen at chunk {chunk}" + ); + assert!(db.verify().unwrap().is_ok()); + } + } + + #[test] + fn a_large_statement_returns_its_tx_id_and_answers_as_of() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("t.graph")).unwrap(); + db.execute("(transact [[:a :n 1]])").unwrap(); + let _chunk = set_tx_chunk_facts(Some(2)); + let before = crate::graph::types::tx_id_now(); + let crate::QueryResult::Transacted(tx_id) = db + .execute("(transact [[:a :n 2] [:a :n 3] [:b :n 4]])") + .unwrap() + else { + panic!("not a transact result"); + }; + assert!(tx_id >= before); + let as_of = |n: u64| { + let q = format!("(query [:find ?v :as-of {n} :where [:a :n ?v]])"); + match db.execute(&q).unwrap() { + crate::QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("not query results"), + } + }; + assert_eq!(as_of(1), 1); + assert_eq!(as_of(2), 3); + let log: Vec<_> = db + .fact_log(&FactFilter::new()) + .unwrap() + .map(Result::unwrap) + .collect(); + assert!( + log.iter() + .filter(|r| r.tx_count == 2) + .all(|r| r.tx_id == tx_id && r.valid_from == i64::try_from(tx_id).unwrap()) + ); + } + + #[test] + fn a_rejected_large_statement_writes_nothing_and_takes_no_tx_count() { + let w1 = r#"{:valid-from "2020-01-01T00:00:00Z"}"#; + let w2 = r#"{:valid-from "2021-01-01T00:00:00Z"}"#; + let over = format!( + r#""{}""#, + "x".repeat(crate::storage::keys::MAX_VALUE_BYTES + 1) + ); + let cases = [ + // Another window of a triple an earlier chunk wrote. + ( + format!("(transact [[:a :n 1 {w1}] [:b :n 1] [:c :n 1] [:a :n 1 {w2}]])"), + "API-011", + ), + // A value a checkpoint cannot store, in a later chunk. + ( + format!("(transact [[:a :n 1] [:b :n 1] [:c :n 1] [:d :s {over}]])"), + "WAL-003", + ), + ]; + for (stmt, want) in cases { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + db.execute(&workload()[0]).unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:h :n 1]])").unwrap(); + let before = records(&db); + let generation = db.generation(); + + let small = code(db.execute(&stmt)); + assert_eq!(small, want, "small path"); + let message = db.execute(&stmt).unwrap_err().to_string(); + // The small path takes a tx_count for WAL-003 (the WAL entry + // checks sizes after the count is allocated); the large one none. + let tx_count = db.current_tx_count(); + let large = { + let _chunk = set_tx_chunk_facts(Some(2)); + db.execute(&stmt).unwrap_err() + }; + assert_eq!(large.code(), want, "large path"); + assert_eq!(large.to_string(), message, "same message"); + assert_eq!(db.current_tx_count(), tx_count, "no tx_count taken"); + assert!(records(&db) == before); + assert!(db.verify().unwrap().is_ok()); + assert_eq!(db.generation(), generation, "no meta written"); + assert!(wal_of(&path).exists(), "the WAL stays"); + + // The transaction stays usable, and the next checkpoint commits + // a meta before it deletes the WAL. + db.execute("(transact [[:i :n 1]])").unwrap(); + db.checkpoint().unwrap(); + assert_eq!(db.generation(), generation + 1); + assert!(!wal_of(&path).exists()); + let after = records(&db); + drop(db); + let db = Minigraf::open(&path).unwrap(); + assert!(records(&db) == after); + assert!(db.verify().unwrap().is_ok()); + } + } + + #[test] + fn a_rollback_alone_makes_the_next_checkpoint_write_a_meta() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + let _chunk = set_tx_chunk_facts(Some(1)); + let stmt = r#"(transact [[:a :n 1 {:valid-from "2020-01-01T00:00:00Z"}] + [:a :n 1 {:valid-from "2021-01-01T00:00:00Z"}]])"#; + assert_eq!(code(db.execute(stmt)), "API-011"); + assert_eq!(db.generation(), 1); + assert!(wal_of(&path).exists(), "the WAL guard"); + db.checkpoint().unwrap(); + assert_eq!(db.generation(), 2, "a meta before the WAL goes"); + assert!(!wal_of(&path).exists()); + } + + #[test] + fn a_wal_at_open_makes_the_first_checkpoint_write_a_meta() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + db.execute("(transact [[:a :n 1]])").unwrap(); + db.checkpoint().unwrap(); + db.kill(); + // A WAL every entry of which is checkpointed (none here): only its + // header, as a large transaction's guard leaves it. + let _ = + crate::wal::WalWriter::open_or_create_at(&wal_of(&path), crate::db::SyncMode::Full, 2) + .unwrap(); + let db = Minigraf::open(&path).unwrap(); + db.checkpoint().unwrap(); + assert_eq!(db.generation(), 3); + assert!(!wal_of(&path).exists()); + } + + /// Spec §4.5: a large transaction that stops after writing pages of + /// `g + 1` on a new file (one valid meta slot) reopens at `g` because its + /// WAL guard says so; without the guard the file would be refused. + #[test] + fn the_wal_guard_lets_a_new_file_reopen_after_a_crash_in_a_large_transaction() { + use crate::storage::fault::{self, Fault, Site}; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let db = Minigraf::open(&path).unwrap(); + let _chunk = set_tx_chunk_facts(Some(2)); + let stmt = "(transact [[:a :n 1] [:b :n 2] [:c :n 3] [:d :n 4] [:e :n 5]])"; + // The meta page is the last page write; fail it. + let writes = { + let probe_dir = tempfile::tempdir().unwrap(); + let probe = Minigraf::open(probe_dir.path().join("p.graph")).unwrap(); + fault::arm(Fault::Eio, u64::MAX); + probe.execute(stmt).unwrap(); + let n = fault::count(); + fault::disarm(); + probe.kill(); + n + }; + // Writes: the WAL header, pages, the meta, the WAL removal. + fault::arm(Fault::Eio, writes - 2); + db.execute(stmt).expect_err("the meta write fails"); + assert_eq!(fault::disarm(), Some(Site::PageWrite)); + db.kill(); + + let copy = dir.path().join("copy.graph"); + std::fs::copy(&path, ©).unwrap(); + let db = Minigraf::open(&path).expect("the WAL guard says generation 1"); + assert!(records(&db).is_empty()); + assert!(db.verify().unwrap().is_ok()); + db.execute(stmt).unwrap(); + assert_eq!(records(&db).len(), 5); + drop(db); + let err = Minigraf::open(©).err().expect("no guard"); + assert_eq!(err.code(), "STG-033"); + } + + #[test] + fn readers_see_their_snapshot_through_a_large_transaction() { + let dir = tempfile::tempdir().unwrap(); + let db = OpenOptions::new() + .path(dir.path().join("t.graph")) + .open() + .unwrap(); + db.execute(&workload()[0]).unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:h :n 1]])").unwrap(); + let before = records(&db); + let query = "(query [:find ?e ?a ?v :where [?e ?a ?v]])"; + let rows = |c: crate::Cursor| { + let mut v: Vec = c.map(|r| format!("{:?}", r.unwrap())).collect(); + v.sort(); + v + }; + let want_rows = rows(db.query(query).unwrap()); + + let cursor_before = db.query(query).unwrap(); + let log_before = db.fact_log(&FactFilter::new()).unwrap(); + let during: std::rc::Rc>> = + std::rc::Rc::default(); + { + let (db, during) = (db.clone(), during.clone()); + AFTER_CHUNK.with(|h| { + *h.borrow_mut() = Some(Box::new(move || { + let c = db.query(query).unwrap(); + let l = db.fact_log(&FactFilter::new()).unwrap(); + during.borrow_mut().push((c, l)); + })) + }); + } + let big: String = (0..40) + .map(|i| format!("[:x{i} :n {i}] [:a :n {i}]")) + .collect(); + { + let _chunk = set_tx_chunk_facts(Some(8)); + db.execute(&format!("(transact [{big}])")).unwrap(); + } + AFTER_CHUNK.with(|h| h.borrow_mut().take()); + // Later commits must not reuse a page the readers may still read. + for i in 0..5 { + db.execute(&format!("(transact [[:a :n {i}] [:y{i} :n {i}]])")) + .unwrap(); + db.checkpoint().unwrap(); + } + let during = std::mem::take(&mut *during.borrow_mut()); + assert_eq!(during.len(), 10, "one pair per chunk"); + let log_rows = |l: crate::FactLog| { + let mut v: Vec = l + .map(|r| { + let r = r.unwrap(); + format!("{} {} {:?} {}", r.entity, r.attribute, r.value, r.tx_count) + }) + .collect(); + v.sort(); + v + }; + let want_log: Vec = { + let mut v: Vec = before + .iter() + .map(|r| format!("{} {} {} {}", r.0, r.1, r.2, r.3)) + .collect(); + v.sort(); + v + }; + assert!(rows(cursor_before) == want_rows, "cursor opened before"); + assert!(log_rows(log_before) == want_log, "log opened before"); + for (c, l) in during { + assert!(rows(c) == want_rows, "cursor opened during"); + assert!(log_rows(l) == want_log, "log opened during"); + } + let after = db.query(query).unwrap(); + assert!(rows(after).len() > want_rows.len(), "cursor opened after"); + assert!(db.verify().unwrap().is_ok()); + } +} diff --git a/tests/crash_kill_test.rs b/tests/crash_kill_test.rs index 2bcc0abdbf..ee78556cab 100644 --- a/tests/crash_kill_test.rs +++ b/tests/crash_kill_test.rs @@ -21,7 +21,14 @@ //! This also covers the original #308 report (a kill mid-checkpoint left a //! header checksum mismatch): every round must reopen. //! -//! Round count: `MINIGRAF_CRASH_KILL_ROUNDS` (default 5, one per variant; +//! With the `test-oracle` feature a sixth variant makes most transactions +//! large (#550): they write pages and commit as a checkpoint, with no WAL +//! entry, and every fourth one is followed by a large statement that fails +//! after writing pages and rolls back. The kill lands during a large +//! transaction, after its commit point, or after a rollback before the next +//! checkpoint. +//! +//! Round count: `MINIGRAF_CRASH_KILL_ROUNDS` (default one per variant; //! `.github/workflows/crash-kill.yml` runs 100 nightly on each OS). Replay a //! failure with the base seed it prints: `MINIGRAF_CRASH_KILL_SEED`. //! @@ -37,13 +44,11 @@ use std::process::Command; use std::time::{Duration, Instant}; use uuid::Uuid; -const DEFAULT_ROUNDS: usize = 5; - fn rounds() -> usize { std::env::var("MINIGRAF_CRASH_KILL_ROUNDS") .ok() .and_then(|s| s.parse().ok()) - .unwrap_or(DEFAULT_ROUNDS) + .unwrap_or(VARIANTS.len()) } // ── Workload ────────────────────────────────────────────────────────────────── @@ -173,16 +178,32 @@ enum Variant { AutoCheckpoint, /// As `CheckpointEvery3`, with `SyncMode::Normal` (no WAL fsync). NormalSync, + /// Statements of more than [`LARGE_CHUNK`] facts are large (#550), and a + /// failing large statement follows every fourth transaction; + /// `checkpoint()` after every fifth. + #[cfg(feature = "test-oracle")] + Large, } -const VARIANTS: [Variant; 5] = [ +const VARIANTS: &[Variant] = &[ Variant::CheckpointEach, Variant::CheckpointEvery3, Variant::WalOnly, Variant::AutoCheckpoint, Variant::NormalSync, + #[cfg(feature = "test-oracle")] + Variant::Large, ]; +/// The chunk size of the `Large` variant's child. +#[cfg(feature = "test-oracle")] +const LARGE_CHUNK: usize = 2; + +/// Fails with API-011 in its second chunk, after the first is written. +#[cfg(feature = "test-oracle")] +const FAILS_LARGE: &str = r#"(transact [[:e0 :a0 0 {:valid-from "2020-01-01T00:00:00Z"}] [:e1 :a0 0] + [:e2 :a0 0] [:e0 :a0 0 {:valid-from "2021-01-01T00:00:00Z"}]])"#; + impl Variant { fn options(self) -> OpenOptions { let opts = OpenOptions::new(); @@ -191,6 +212,8 @@ impl Variant { Variant::AutoCheckpoint => opts.wal_checkpoint_threshold(2), Variant::NormalSync => opts.synchronous(SyncMode::Normal), Variant::CheckpointEach | Variant::CheckpointEvery3 => opts, + #[cfg(feature = "test-oracle")] + Variant::Large => opts, } } @@ -199,6 +222,8 @@ impl Variant { Variant::CheckpointEach => true, Variant::CheckpointEvery3 | Variant::NormalSync => k % 3 == 0, Variant::WalOnly | Variant::AutoCheckpoint => false, + #[cfg(feature = "test-oracle")] + Variant::Large => k % 5 == 0, } } } @@ -448,6 +473,10 @@ fn crash_kill_child_entrypoint() { .expect("child opens log"); let db = Minigraf::open_with_options(&db_path, variant.options()).expect("child opens db"); + #[cfg(feature = "test-oracle")] + let large = matches!(variant, Variant::Large); + #[cfg(feature = "test-oracle")] + let _chunk = large.then(|| minigraf::__tx_chunk_facts(Some(LARGE_CHUNK))); let mut rng = Rng::new(seed); let mut live = BTreeSet::new(); for k in 1.. { @@ -456,6 +485,13 @@ fn crash_kill_child_entrypoint() { log.write_all(format!("{k}\n").as_bytes()) .expect("child logs transaction"); live = next; + #[cfg(feature = "test-oracle")] + if large && k % 4 == 0 { + let e = db + .execute(FAILS_LARGE) + .expect_err("a failing large statement"); + assert_eq!(e.code(), "API-011"); + } if variant.checkpoint_after(k) { db.checkpoint().expect("child checkpoint"); } diff --git a/tests/large_transaction_acceptance_test.rs b/tests/large_transaction_acceptance_test.rs new file mode 100644 index 0000000000..cfb31468f0 --- /dev/null +++ b/tests/large_transaction_acceptance_test.rs @@ -0,0 +1,102 @@ +//! Acceptance test for large transactions (#550 spec §8.1, #473 spec §8): a +//! 1M-fact `transact` on a file database holds at most `TX_CHUNK_FACTS` +//! materialised facts at any time, and commits as a checkpoint. +//! +//! Ignored by default; `.github/workflows/smoke.yml` runs it nightly: +//! +//! ```text +//! cargo test --profile bench --features test-oracle --test large_transaction_acceptance_test -- --ignored --nocapture +//! ``` +//! +//! The count of facts held comes from a high-water mark the statement reader +//! keeps (`minigraf::__statement_facts_high_water`, `test-oracle` only). Peak +//! RSS comes from `/proc/self/status` (Linux only) and is printed, not +//! checked: the bound is on facts, and the input string alone is about 25 MB. +#![cfg(all(feature = "test-oracle", not(target_arch = "wasm32")))] + +use minigraf::{Minigraf, QueryResult}; + +const FACTS: usize = 1_000_000; +/// `TX_CHUNK_FACTS` until #550 PR 3's measurement sets it. +const TX_CHUNK_FACTS: usize = 16_384; + +/// A `kB` field of `/proc/self/status`; 0 where it does not exist. +fn proc_status_kb(field: &str) -> usize { + std::fs::read_to_string("/proc/self/status") + .ok() + .and_then(|s| { + s.lines() + .find_map(|l| l.strip_prefix(field)?.strip_prefix(':').map(str::to_owned)) + }) + .and_then(|v| v.trim().trim_end_matches("kB").trim().parse().ok()) + .unwrap_or(0) +} + +fn count(db: &Minigraf, query: &str) -> usize { + match db.execute(query).unwrap() { + QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("not a query result"), + } +} + +#[test] +#[ignore] +fn one_million_fact_transact_holds_one_chunk() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("large.graph"); + let db = Minigraf::open(&path).unwrap(); + // Half the facts on new entities, half on a few: the DICT grows and the + // index leaves split, and repeated entities cross chunks. + let mut input = String::with_capacity(FACTS * 26); + input.push_str("(transact ["); + for i in 0..FACTS { + if i % 2 == 0 { + input.push_str(&format!("[:e{i} :n {i}]")); + } else { + input.push_str(&format!("[:hub{} :m {i}]", i % 64)); + } + } + input.push_str("])"); + + let _ = minigraf::__statement_facts_high_water(); + let reset = std::fs::write("/proc/self/clear_refs", "5").is_ok(); + let before_kb = proc_status_kb("VmRSS"); + let start = std::time::Instant::now(); + db.execute(&input).unwrap(); + let elapsed = start.elapsed(); + let high = minigraf::__statement_facts_high_water(); + let peak_kb = proc_status_kb("VmHWM"); + eprintln!( + "one_million_fact_transact_holds_one_chunk: {FACTS} facts in {elapsed:.2?}; \ + at most {high} facts held; peak RSS {} MiB, {} MiB over the start{}", + peak_kb / 1024, + peak_kb.saturating_sub(before_kb) / 1024, + if reset { + "" + } else { + " (high-water mark not reset)" + } + ); + assert!(high > 0, "the statement was counted"); + assert!( + high <= TX_CHUNK_FACTS, + "at most one chunk of facts held at once" + ); + + let mut wal = path.as_os_str().to_owned(); + wal.push(".wal"); + assert!( + !std::path::Path::new(&wal).exists(), + "committed as a checkpoint" + ); + assert_eq!(db.current_tx_count(), 1); + assert_eq!(count(&db, "(query [:find ?v :where [:e10 :n ?v]])"), 1); + assert_eq!( + count(&db, "(query [:find ?v :where [:hub1 :m ?v]])"), + FACTS / 64 + ); + assert!(db.verify().unwrap().is_ok()); + drop(db); + let db = Minigraf::open(&path).unwrap(); + assert_eq!(count(&db, "(query [:find ?e :where [?e :n 999998]])"), 1); +} diff --git a/tests/model_based_test.rs b/tests/model_based_test.rs index 09475e1965..fc8778a864 100644 --- a/tests/model_based_test.rs +++ b/tests/model_based_test.rs @@ -110,9 +110,13 @@ fn cases() -> u32 { proptest! { #![proptest_config(ProptestConfig::with_cases(cases()))] - /// Every read after every step matches the reference model. + /// Every read after every step matches the reference model. With + /// `test-oracle`, statements of more than two facts are large (#550): + /// written in chunks and committed as a checkpoint. #[test] fn file_backed_db_matches_model(steps in arb_steps()) { + #[cfg(feature = "test-oracle")] + let _chunk = minigraf::__tx_chunk_facts(Some(2)); run_with(&steps, Checks::All, source_order())?; } }