From e4e4e69902766c9b5a6305d724acf6c72ebee139 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 7 Oct 2026 15:34:10 +0530 Subject: [PATCH] test: model-based test of transact/retract/checkpoint/reopen (#385) tests/model_based_test.rs runs random sequences of transacts (multi-valued batches, transaction- and fact-level valid-time windows), retracts, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the .graph file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, the tx counter, verify(), full rows with windows and tx counts, and six query shapes under :as-of N and :valid-at T must match a reference model. Normal CI runs 24 cases. The nightly property-test workflow becomes a matrix over property_test and model_based_test (30,000 cases). Spec: docs/superpowers/specs/2026-10-07-model-based-test-design.md Refs #385 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- .github/workflows/property-tests.yml | 22 +- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- ROADMAP.md | 2 +- docs/TEST_COVERAGE.md | 4 +- .../2026-10-07-model-based-test-design.md | 87 ++ tests/model_based_test.rs | 873 ++++++++++++++++++ 8 files changed, 983 insertions(+), 10 deletions(-) create mode 100644 docs/superpowers/specs/2026-10-07-model-based-test-design.md create mode 100644 tests/model_based_test.rs diff --git a/.github/workflows/property-tests.yml b/.github/workflows/property-tests.yml index d12d35fd0c..2fe4261a46 100644 --- a/.github/workflows/property-tests.yml +++ b/.github/workflows/property-tests.yml @@ -12,9 +12,19 @@ permissions: jobs: proptest: - name: Property tests + name: Property tests (${{ matrix.test }}) runs-on: ubuntu-latest timeout-minutes: 360 + strategy: + fail-fast: false + matrix: + include: + - test: property_test + cases: 8000000 + # Model-based storage test (#385): each case runs up to 50 steps + # against a file, ~0.1 s per case. + - test: model_based_test + cases: 30000 steps: - uses: actions/checkout@v4 @@ -26,9 +36,9 @@ jobs: shell: bash run: | set -o pipefail - cargo test --test property_test -- --nocapture 2>&1 | tee proptest-output.txt + cargo test --test ${{ matrix.test }} -- --nocapture 2>&1 | tee proptest-output.txt env: - PROPTEST_CASES: 8000000 + PROPTEST_CASES: ${{ matrix.cases }} RUST_BACKTRACE: 1 - name: Record property-test failure @@ -37,14 +47,16 @@ jobs: env: GH_TOKEN: ${{ github.token }} ISSUE_TITLE: "Nightly property-test failure" + TEST_NAME: ${{ matrix.test }} + CASES: ${{ matrix.cases }} run: | report_file="property-test-failure.md" { - echo "The nightly property-test workflow failed." + echo "The nightly property-test workflow failed in \`$TEST_NAME\`." echo echo "- Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" echo "- Commit: $GITHUB_SHA" - echo "- Reproduce: \`PROPTEST_CASES=8000000 cargo test --test property_test -- --nocapture\`" + echo "- Reproduce: \`PROPTEST_CASES=$CASES cargo test --test $TEST_NAME -- --nocapture\`" echo echo "## Test output" echo diff --git a/CHANGELOG.md b/CHANGELOG.md index fb71b2f326..454e685763 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -44,6 +44,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Tests - **Golden-file compatibility corpus (#391).** `tests/golden/` holds v7 files written by minigraf 2.0.3, each with a JSON manifest of its CRC32, `tx_count` and expected query results. They cover one checkpoint, several checkpoints, indexes rebuilt on open, a WAL left by a crash, a WAL whose entries were already checkpointed, and same-transaction multi-values (#371). `tests/golden_corpus_test.rs` opens a copy of each file and checks its manifest after open, after a checkpoint and reopen, and after one more write. Golden files are never regenerated, only added; a new `golden-corpus` job in `policy.yml` fails a pull request that changes one. The generator is a standalone crate pinned to `minigraf = "=2.0.3"` (`tests/golden/gen/v7/`). On `v3`, each v7 file must also carry a v8 meta page after its first open, and seven v8 files are frozen alongside them, written by the `v3` branch at `23aa57c` (`tests/golden/gen/v8/`): 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 (a 4,068-byte string stored twice, the 64/65-byte inline boundary, a 1,000-byte attribute and keyword). All #371 queries now pass. +- **Model-based storage test (#385).** `tests/model_based_test.rs` runs random sequences of `transact` (multi-valued batches, transaction- and fact-level valid-time windows, a triple repeated with another window), `retract`, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, a 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the `.graph` file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, `current_tx_count`, `verify`, full rows with windows and tx counts, and entity-, entity+attribute-, attribute-, attribute+value-, value-bound and full-scan queries, under `:as-of N` and `:valid-at T`, must match a plain reference model (one valid-time window per triple, #435; API-011 for two windows of one triple in one transaction). Normal CI runs 24 cases; the nightly property-test workflow runs 30,000. ## v2.0.3 — 2026-10-06 diff --git a/CLAUDE.md b/CLAUDE.md index 5cb7d8bead..f71b56dbb1 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -197,7 +197,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1347 tests** (1338 passing, 9 ignored; unit + integration + doc). +**1348 tests** (1339 passing, 9 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/README.md b/README.md index 15fc187b78..51fe798882 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1347 tests +cargo test # run 1348 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 73557819ac..3210a498a7 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -76,7 +76,7 @@ Scope — release-gate testing and documentation: - Golden-file compatibility corpus for every format version (#391; done on `v3`: six v7 files from 2.0.3 checked after migration, seven v8 files frozen at `23aa57c`) - SIGKILL crash test that checks committed data through EAVT, AEVT and full scan (#384) -- Model-based test of transact/retract/checkpoint/reopen (#385) +- Model-based test of transact/retract/checkpoint/reopen (#385; done on `v3`: `tests/model_based_test.rs`, 30,000 cases nightly) - Wider property tests: file-backed, batched, retracts, temporal, joins (#386) - Persistent fuzz corpus and an operation-sequence target (#387) - Fault injection across save/WAL/recovery (#390) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 1c38586001..ceee17ed3d 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-07 with `cargo test --quiet` -**Result**: 1,338 passing tests and 9 ignored tests (1,347 total) +**Result**: 1,339 passing tests and 9 ignored tests (1,348 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. 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). 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, and `API-011` from `transact` and from `WriteTransaction::commit`. 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` 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. 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, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. +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). 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). 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, and `API-011` from `transact` and from `WriteTransaction::commit`. 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` 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. 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, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-07-model-based-test-design.md b/docs/superpowers/specs/2026-10-07-model-based-test-design.md new file mode 100644 index 0000000000..61632715ba --- /dev/null +++ b/docs/superpowers/specs/2026-10-07-model-based-test-design.md @@ -0,0 +1,87 @@ +# Model-based (stateful) storage test — Design + +**Issue:** #385, tracker #383 +**Milestone:** v3.0.0, branch `v3` (test and CI only; no library change) + +## 1. Goal + +Run random sequences of writes, checkpoints and reopens against a file-backed +database and compare every read with a plain in-memory reference model. The +storage and index bugs of 2026 (#285, #287, #323, #370, #371) only showed up after +such sequences. + +## 2. Shape + +`tests/model_based_test.rs`, one `proptest!` over `Vec`. A step is an +operation plus a probe (the random inputs of the checks that follow it). Plain +proptest replaces `proptest-state-machine`: a `Vec` already shrinks by +dropping and simplifying steps, every operation is valid in every state, and no +dependency is added. + +Pools are small so that steps collide: 4 keyword entities, 3 attributes (one +non-ASCII), 18 values (integers 0–2, `i64::MIN`, booleans, a keyword, a float, short +strings, two 80-byte strings sharing a 40-byte prefix (the v8 long-string key +prefix is 32 bytes), a 3,000-byte string for the value pages, and refs to the +entities). A third of the triples are one hot triple, so that its history grows +past the on-disk scan's seek threshold (8 entries). A case has 1–49 steps. + +## 3. Operations + +| Op | API | Model | +|---|---|---| +| `Transact` | `execute("(transact {window} [[e a v {window}] …])")`, 1–6 facts, sometimes a repeated triple with another window | one tx; API-011 when a triple gets two windows | +| `Retract` | `execute("(retract [[e a v] …])")` | one tx (always, even if nothing matches) | +| `WriteTx` | `begin_write`, 0–4 transact/retract statements (half the time plus a retraction of a triple it asserts, before or after), then `commit` or `rollback` | one tx if committed and non-empty (a same-tx retraction wins); API-011 as above; nothing on rollback | +| `Checkpoint` | `checkpoint()`, then `verify()` | none | +| `Reopen` | drop and `open_with_options`: default, `page_cache_size(4)`, or `wal_checkpoint_threshold(2)`; then `verify()` | none | +| `Crash` | copy the `.graph` file and WAL while the handle is open, drop it, open the copy (same modes); then `verify()` | none | + +`Crash` is the only way to reach WAL replay in-process: dropping a handle always +saves (`PersistentFactStorage::drop` saves when dirty, even with +`wal_checkpoint_threshold(usize::MAX)`), and the file lock forbids leaking it. On +Windows, where locks are mandatory, the copy is taken after the drop. + +All handles use `SyncMode::Normal`: the test checks results, not fsync. + +Valid-time windows come from a grid: `:valid-from` in {2000, 2002, 2004, 2006}, +`:valid-to` in {2003, 2005, 2007, 2200} (January 1st UTC), each optional at the +transaction and the fact level. A fact window that would be empty or inverted +(#436) is rewritten to start in 2000, so every generated window is valid. + +## 4. Model + +A log of records `(tx, e, a, v, valid_from or tx-time, valid_to, asserted)` and a +transaction counter. At `as-of N`, a triple is live when its newest assertion +with `tx ≤ N` is newer than its newest retraction; its window is that +assertion's (one window per triple, #435). A window that starts at transaction +time is before every grid instant up to 2008, after 2100, and before "now". + +## 5. Checks after each step + +- `current_tx_count()` equals the model counter. +- Full rows `?e ?a ?v ?vf ?vt ?tc ?ti` with `:any-valid-time`, current and at a + random `:as-of N` (N up to counter + 1): windows and tx counts match the model, + a tx-time `valid_from` equals the fact's tx id, and tx count → tx id is a + function. +- Entity-bound, entity+attribute-bound, attribute-bound, attribute+value-bound, + value-bound and full-scan queries, each under: default (now), `:valid-at T`, + `:as-of N :valid-at T`, `:as-of N`. T comes from a grid that hits every window + bound plus 1999, 2008, 2100 and 2300. + +Results are compared as sorted lists of rendered rows; entity UUIDs render as +their pool index, so failure messages carry no `Uuid` (CodeQL rule). + +## 6. CI + +Normal CI runs 24 cases (default, overridden by `PROPTEST_CASES`). The nightly +property-test job becomes a matrix over `property_test` (8,000,000 cases) and +`model_based_test` (30,000 cases, ~0.12 s each locally), so the two run in +parallel within their own 6-hour limits; the failure issue names the test. + +Mutation checks during development: the test fails on each of ignored +retractions, an off-by-one `:as-of`, inclusive `:valid-to`, exclusive +`:valid-from`, a same-tx retraction that loses, a missing API-011, on-disk +retractions ignored, on-disk older transactions not hidden, a seek that skips the +`:as-of` transaction, a WAL replay that skips an entry, and a transaction counter +not restored after replay. Minimized failures become named regression +tests in the same file. diff --git a/tests/model_based_test.rs b/tests/model_based_test.rs new file mode 100644 index 0000000000..f361bd6025 --- /dev/null +++ b/tests/model_based_test.rs @@ -0,0 +1,873 @@ +//! Model-based (stateful) test of the file-backed database (#385). +//! +//! Random sequences of transact, retract, write transactions, checkpoints and +//! reopens run against a `.graph` file in a temp dir. After every step, the +//! results of entity-, attribute-, value-bound and full-scan queries, under +//! `:as-of N` and `:valid-at T`, are compared with a plain reference model. +//! +//! Run: cargo test --test model_based_test +//! More cases: PROPTEST_CASES=500 cargo test --test model_based_test +//! +//! Design: docs/superpowers/specs/2026-10-07-model-based-test-design.md +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::db::{Minigraf, OpenOptions, SyncMode}; +use minigraf::{MinigrafError, QueryResult, Value}; +use proptest::prelude::*; +use proptest::test_runner::TestCaseError; +use std::collections::HashMap; +use std::path::Path; +use uuid::Uuid; + +// ── Pools ───────────────────────────────────────────────────────────────────── + +const ENTITIES: usize = 4; +const ATTRS: [&str; 3] = [":a0", ":a1", ":tag/丿"]; + +/// String pool. Indices 3 and 4 are longer than the 64-byte inline limit and +/// share their first 40 bytes; index 5 fills most of a value page. +fn pool_string(i: u8) -> String { + match i { + 0 => "x".to_string(), + 1 => "y".to_string(), + 2 => String::new(), + 3 => format!("{}{}", "p".repeat(40), "A".repeat(40)), + 4 => format!("{}{}", "p".repeat(40), "B".repeat(40)), + _ => "z".repeat(3000), + } +} + +/// A value from the pool. Debug output carries pool indices, never a `Uuid`. +#[derive(Clone, Debug, PartialEq)] +enum V { + Int(i64), + Bool(bool), + Kw, + Float, + Str(u8), + Ref(usize), +} + +impl V { + fn edn(&self) -> String { + match self { + V::Int(n) => n.to_string(), + V::Bool(b) => b.to_string(), + V::Kw => ":k0".to_string(), + V::Float => "1.5".to_string(), + V::Str(i) => format!("\"{}\"", pool_string(*i)), + V::Ref(e) => format!("#uuid \"{}\"", entity_uuid(*e)), + } + } + + fn render(&self) -> String { + match self { + V::Int(n) => format!("i{n}"), + V::Bool(b) => format!("b{b}"), + V::Kw => "k:k0".to_string(), + V::Float => "f1.5".to_string(), + V::Str(i) => render_str(&pool_string(*i)), + V::Ref(e) => format!("r{e}"), + } + } +} + +fn render_str(s: &str) -> String { + if s.len() <= 16 { + format!("s\"{s}\"") + } else { + let head: String = s.chars().take(4).collect(); + let tail: String = s.chars().skip(s.chars().count() - 4).collect(); + format!("s\"{head}..{tail}\"#{}", s.len()) + } +} + +fn entity_uuid(idx: usize) -> Uuid { + Uuid::new_v5(&Uuid::NAMESPACE_OID, format!(":e{idx}").as_bytes()) +} + +/// Render an engine value like the model renders its own (`V::render`). +fn render_value(v: &Value, uuids: &HashMap) -> String { + match v { + Value::Integer(n) => format!("i{n}"), + Value::Boolean(b) => format!("b{b}"), + Value::Keyword(k) => format!("k{k}"), + Value::Float(f) => format!("f{f}"), + Value::String(s) => render_str(s), + Value::Ref(u) => match uuids.get(u) { + Some(i) => format!("r{i}"), + None => "r?".to_string(), + }, + Value::Null => "null".to_string(), + } +} + +// ── Time grid ───────────────────────────────────────────────────────────────── + +/// Unix ms of January 1st of `year`, UTC. +fn jan1_ms(year: i64) -> i64 { + // Days from 1970-01-01 to year-01-01 (proleptic Gregorian). + let y = year - 1; + let days = + 365 * (y - 1969) + (y / 4 - 1969 / 4) - (y / 100 - 1969 / 100) + (y / 400 - 1969 / 400); + days * 86_400_000 +} + +const VF_YEARS: [i64; 4] = [2000, 2002, 2004, 2006]; +const VT_YEARS: [i64; 4] = [2003, 2005, 2007, 2200]; +/// `:valid-at` instants: every window bound, plus points before, between and after. +const AT_YEARS: [i64; 12] = [ + 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2100, 2300, +]; +const FOREVER: i64 = i64::MAX; + +/// An optional `:valid-from` / `:valid-to` (grid indices). +#[derive(Clone, Copy, Debug, Default, PartialEq)] +struct Window { + vf: Option, + vt: Option, +} + +impl Window { + fn is_empty(&self) -> bool { + self.vf.is_none() && self.vt.is_none() + } + + fn edn(&self) -> String { + let mut parts = Vec::new(); + if let Some(i) = self.vf { + parts.push(format!(":valid-from \"{}-01-01\"", VF_YEARS[i as usize])); + } + if let Some(i) = self.vt { + parts.push(format!(":valid-to \"{}-01-01\"", VT_YEARS[i as usize])); + } + format!("{{{}}}", parts.join(" ")) + } +} + +/// An effective valid-time window: `valid_from` is `None` when it is the +/// transaction time (some instant between 2026 and 2100, before "now"). +type Effective = (Option, i64); + +fn effective(tx: Window, fact: Window) -> Effective { + let vf = fact.vf.or(tx.vf).map(|i| jan1_ms(VF_YEARS[i as usize])); + let vt = fact + .vt + .or(tx.vt) + .map_or(FOREVER, |i| jan1_ms(VT_YEARS[i as usize])); + (vf, vt) +} + +fn window_is_valid((vf, vt): Effective) -> bool { + match vf { + Some(vf) => vf < vt, + None => vt > jan1_ms(2100), + } +} + +/// When to read: `None` = now (no `:valid-at`), `Some(ms)` = a grid instant. +fn valid_at(window: Effective, at: Option) -> bool { + let (vf, vt) = window; + match at { + None => vt == FOREVER || vt > jan1_ms(2100), + Some(t) => { + let starts = match vf { + Some(vf) => vf <= t, + None => t >= jan1_ms(2100), + }; + starts && t < vt + } + } +} + +// ── Operations ──────────────────────────────────────────────────────────────── + +#[derive(Clone, Debug)] +struct FactSpec { + e: usize, + a: usize, + v: V, + window: Window, +} + +#[derive(Clone, Debug)] +enum Stmt { + Transact { + window: Window, + facts: Vec, + }, + Retract { + facts: Vec<(usize, usize, V)>, + }, +} + +#[derive(Clone, Copy, Debug)] +enum OpenMode { + Default, + SmallCache, + AutoCheckpoint, +} + +#[derive(Clone, Debug)] +enum Op { + Exec(Stmt), + WriteTx { + stmts: Vec, + commit: bool, + }, + Checkpoint, + Reopen(OpenMode), + /// Open a copy of the `.graph` file and its WAL taken while the handle is + /// open, as a process death would leave them: the WAL is replayed. + Crash(OpenMode), +} + +/// Random inputs of the checks that follow a step. +#[derive(Clone, Debug)] +struct Probe { + as_of: u16, + at: usize, + e: usize, + a: usize, + v: V, +} + +#[derive(Clone, Debug)] +struct Step { + op: Op, + probe: Probe, +} + +impl Stmt { + fn edn(&self) -> String { + match self { + Stmt::Transact { window, facts } => { + let facts: Vec = facts + .iter() + .map(|f| { + let w = if f.window.is_empty() { + String::new() + } else { + format!(" {}", f.window.edn()) + }; + format!("[:e{} {} {}{w}]", f.e, ATTRS[f.a], f.v.edn()) + }) + .collect(); + let w = if window.is_empty() { + String::new() + } else { + format!("{} ", window.edn()) + }; + format!("(transact {w}[{}])", facts.join(" ")) + } + Stmt::Retract { facts } => { + let facts: Vec = facts + .iter() + .map(|(e, a, v)| format!("[:e{e} {} {}]", ATTRS[*a], v.edn())) + .collect(); + format!("(retract [{}])", facts.join(" ")) + } + } + } +} + +// ── Strategies ──────────────────────────────────────────────────────────────── + +fn arb_v() -> impl Strategy { + prop_oneof![ + 3 => (0i64..3).prop_map(V::Int), + 1 => Just(V::Int(i64::MIN)), + 1 => any::().prop_map(V::Bool), + 1 => Just(V::Kw), + 1 => Just(V::Float), + 3 => (0u8..6).prop_map(V::Str), + 2 => (0..ENTITIES).prop_map(V::Ref), + ] +} + +fn arb_window() -> impl Strategy { + prop_oneof![ + 3 => Just(Window::default()), + 2 => (prop::option::of(0u8..4), prop::option::of(0u8..4)) + .prop_map(|(vf, vt)| Window { vf, vt }), + ] +} + +/// A triple; often the same hot one, so that a triple builds a history longer +/// than the on-disk scan's seek threshold (8 entries). +fn arb_triple() -> impl Strategy { + prop_oneof![ + 2 => (0..ENTITIES, 0..ATTRS.len(), arb_v()), + 1 => Just((0, 0, V::Int(0))), + ] +} + +fn arb_transact() -> impl Strategy { + ( + arb_window(), + prop::collection::vec((arb_triple(), arb_window()), 1..6), + prop::option::weighted(0.15, arb_window()), + ) + .prop_map(|(window, facts, repeat)| { + let mut facts: Vec = facts + .into_iter() + .map(|((e, a, v), w)| FactSpec { e, a, v, window: w }) + .collect(); + // Sometimes the same triple twice: an identical repeat or, when the + // windows differ, an API-011 rejection. + if let Some(w) = repeat { + let mut again = facts[0].clone(); + again.window = w; + facts.push(again); + } + // An empty or inverted window (#436) is rewritten to start in 2000; + // every `:valid-to` on the grid is later. + for f in &mut facts { + if !window_is_valid(effective(window, f.window)) { + f.window.vf = Some(0); + } + } + Stmt::Transact { window, facts } + }) +} + +fn arb_retract() -> impl Strategy { + prop::collection::vec(arb_triple(), 1..4).prop_map(|facts| Stmt::Retract { facts }) +} + +fn arb_stmt() -> impl Strategy { + prop_oneof![3 => arb_transact(), 2 => arb_retract()] +} + +fn arb_op() -> impl Strategy { + prop_oneof![ + 6 => arb_transact().prop_map(Op::Exec), + 3 => arb_retract().prop_map(Op::Exec), + 2 => ( + prop::collection::vec(arb_stmt(), 0..4), + any::(), + prop::bool::weighted(0.8), + ) + .prop_map(|(mut stmts, retract_own, commit)| { + // Retract a triple this transaction asserts, before or after + // the assertion: the retraction wins either way. + let own = stmts.iter().find_map(|s| match s { + Stmt::Transact { facts, .. } => Some(facts[0].clone()), + Stmt::Retract { .. } => None, + }); + if let (true, Some(f)) = (retract_own, own) { + let retract = Stmt::Retract { facts: vec![(f.e, f.a, f.v)] }; + if stmts.len() % 2 == 0 { + stmts.push(retract); + } else { + stmts.insert(0, retract); + } + } + Op::WriteTx { stmts, commit } + }), + 2 => Just(Op::Checkpoint), + 2 => prop_oneof![ + Just(OpenMode::Default), + Just(OpenMode::SmallCache), + Just(OpenMode::AutoCheckpoint), + ] + .prop_map(Op::Reopen), + 2 => prop_oneof![ + Just(OpenMode::Default), + Just(OpenMode::SmallCache), + Just(OpenMode::AutoCheckpoint), + ] + .prop_map(Op::Crash), + ] +} + +fn arb_probe() -> impl Strategy { + ( + any::(), + 0..AT_YEARS.len(), + 0..ENTITIES, + 0..ATTRS.len(), + arb_v(), + ) + .prop_map(|(as_of, at, e, a, v)| Probe { as_of, at, e, a, v }) +} + +fn arb_steps() -> impl Strategy> { + prop::collection::vec( + (arb_op(), arb_probe()).prop_map(|(op, probe)| Step { op, probe }), + 1..50, + ) +} + +// ── Reference model ─────────────────────────────────────────────────────────── + +#[derive(Clone, Debug)] +struct Record { + tx: u64, + e: usize, + a: usize, + v: V, + window: Effective, + asserted: bool, +} + +/// A live fact: one window per triple, from its newest assertion (#435). +#[derive(Clone, Debug)] +struct Live { + e: usize, + a: usize, + v: V, + window: Effective, + tx: u64, +} + +#[derive(Default)] +struct Model { + log: Vec, + tx_count: u64, +} + +impl Model { + /// The records a committed transaction of `stmts` would add, or `None` + /// when the transaction is rejected with API-011 (one triple, two windows). + fn records(stmts: &[Stmt], tx: u64) -> Option> { + let mut out = Vec::new(); + for stmt in stmts { + match stmt { + Stmt::Transact { window, facts } => { + for f in facts { + out.push(Record { + tx, + e: f.e, + a: f.a, + v: f.v.clone(), + window: effective(*window, f.window), + asserted: true, + }); + } + } + Stmt::Retract { facts } => { + for (e, a, v) in facts { + out.push(Record { + tx, + e: *e, + a: *a, + v: v.clone(), + window: (None, FOREVER), + asserted: false, + }); + } + } + } + } + let asserted: Vec<&Record> = out.iter().filter(|r| r.asserted).collect(); + for (i, x) in asserted.iter().enumerate() { + for y in &asserted[i + 1..] { + if x.e == y.e && x.a == y.a && x.v == y.v && x.window != y.window { + return None; + } + } + } + Some(out) + } + + /// Apply a committed transaction. Returns false when it is rejected. + fn commit(&mut self, stmts: &[Stmt]) -> bool { + if stmts.is_empty() { + return true; + } + match Self::records(stmts, self.tx_count + 1) { + Some(records) => { + self.tx_count += 1; + self.log.extend(records); + true + } + None => false, + } + } + + fn live(&self, as_of: Option) -> Vec { + let limit = as_of.unwrap_or(u64::MAX); + let mut out: Vec = Vec::new(); + let mut seen: Vec<(usize, usize, &V)> = Vec::new(); + for r in &self.log { + if seen + .iter() + .any(|(e, a, v)| *e == r.e && *a == r.a && *v == &r.v) + { + continue; + } + seen.push((r.e, r.a, &r.v)); + let same = |x: &&Record| x.tx <= limit && x.e == r.e && x.a == r.a && x.v == r.v; + let newest_assert = self + .log + .iter() + .filter(same) + .filter(|x| x.asserted) + .max_by_key(|x| x.tx); + let newest_retract = self + .log + .iter() + .filter(same) + .filter(|x| !x.asserted) + .map(|x| x.tx) + .max() + .unwrap_or(0); + if let Some(a) = newest_assert.filter(|a| a.tx > newest_retract) { + out.push(Live { + e: a.e, + a: a.a, + v: a.v.clone(), + window: a.window, + tx: a.tx, + }); + } + } + out + } +} + +// ── Checks ──────────────────────────────────────────────────────────────────── + +struct Ctx { + uuids: HashMap, +} + +impl Ctx { + fn rows(&self, db: &Minigraf, query: &str) -> Result>, TestCaseError> { + let result = db + .execute(query) + .map_err(|e| TestCaseError::fail(format!("query failed ({}): {query}", e.code())))?; + match result { + QueryResult::QueryResults { results, .. } => Ok(results + .iter() + .map(|row| row.iter().map(|v| render_value(v, &self.uuids)).collect()) + .collect()), + _ => Err(TestCaseError::fail(format!("not a query result: {query}"))), + } + } +} + +fn sorted(mut rows: Vec) -> Vec { + rows.sort(); + rows +} + +fn attr_render(a: usize) -> String { + format!("k{}", ATTRS[a]) +} + +/// Full rows with windows and tx counts, current or at `:as-of N`. +fn check_full_rows( + db: &Minigraf, + ctx: &Ctx, + model: &Model, + as_of: Option, + step: usize, +) -> Result<(), TestCaseError> { + let as_of_clause = as_of.map_or(String::new(), |n| format!(":as-of {n} ")); + let query = format!( + "(query [:find ?e ?a ?v ?vf ?vt ?tc ?ti {as_of_clause}:any-valid-time \ + :where [?e ?a ?v] [?e :db/valid-from ?vf] [?e :db/valid-to ?vt] \ + [?e :db/tx-count ?tc] [?e :db/tx-id ?ti]])" + ); + let mut tx_ids: HashMap = HashMap::new(); + let mut got = Vec::new(); + for row in ctx.rows(db, &query)? { + prop_assert_eq!(row.len(), 7, "step {}: full row width", step); + let (vf, ti) = (&row[3], &row[6]); + // A tx-time valid_from is the fact's own tx id. + let vf = if vf == ti { + "tx".to_string() + } else { + vf.clone() + }; + if let Some(prev) = tx_ids.insert(row[5].clone(), ti.clone()) { + prop_assert_eq!(&prev, ti, "step {}: one tx id per tx count", step); + } + got.push(format!( + "{} {} {} [{vf}, {}) tx{}", + row[0], row[1], row[2], row[4], row[5] + )); + } + let want: Vec = model + .live(as_of) + .iter() + .map(|l| { + let vf = l.window.0.map_or("tx".to_string(), |ms| format!("i{ms}")); + format!( + "r{} {} {} [{vf}, i{}) txi{}", + l.e, + attr_render(l.a), + l.v.render(), + l.window.1, + l.tx + ) + }) + .collect(); + prop_assert_eq!( + sorted(got), + sorted(want), + "step {}: full rows, as-of {:?}", + step, + as_of + ); + Ok(()) +} + +/// The query shapes: (where clause, find vars, model filter + projection). +fn check_shapes( + db: &Minigraf, + ctx: &Ctx, + model: &Model, + probe: &Probe, + as_of: Option, + at: Option, + step: usize, +) -> Result<(), TestCaseError> { + let (pe, pa, pv) = (probe.e, probe.a, &probe.v); + let ea = format!(":e{pe}"); + let aa = ATTRS[pa]; + let ve = pv.edn(); + type Shape<'a> = (&'a str, String, Box Option + 'a>); + let shapes: Vec> = vec![ + ( + "?e ?a ?v", + "[?e ?a ?v]".to_string(), + Box::new(|l: &Live| Some(format!("r{} {} {}", l.e, attr_render(l.a), l.v.render()))), + ), + ( + "?a ?v", + format!("[{ea} ?a ?v]"), + Box::new(move |l: &Live| { + (l.e == pe).then(|| format!("{} {}", attr_render(l.a), l.v.render())) + }), + ), + ( + "?v", + format!("[{ea} {aa} ?v]"), + Box::new(move |l: &Live| (l.e == pe && l.a == pa).then(|| l.v.render())), + ), + ( + "?e ?v", + format!("[?e {aa} ?v]"), + Box::new(move |l: &Live| (l.a == pa).then(|| format!("r{} {}", l.e, l.v.render()))), + ), + ( + "?e", + format!("[?e {aa} {ve}]"), + Box::new(move |l: &Live| (l.a == pa && &l.v == pv).then(|| format!("r{}", l.e))), + ), + ( + "?e ?a", + format!("[?e ?a {ve}]"), + Box::new(move |l: &Live| { + (&l.v == pv).then(|| format!("r{} {}", l.e, attr_render(l.a))) + }), + ), + ]; + + let mut temporal = String::new(); + if let Some(n) = as_of { + temporal.push_str(&format!(":as-of {n} ")); + } + if let Some(t) = at { + let year = AT_YEARS.iter().find(|y| jan1_ms(**y) == t).copied(); + temporal.push_str(&format!(":valid-at \"{}-01-01\" ", year.unwrap_or(1999))); + } + + let live = model.live(as_of); + for (find, clause, project) in &shapes { + let query = format!("(query [:find {find} {temporal}:where {clause}])"); + let got: Vec = ctx + .rows(db, &query)? + .into_iter() + .map(|r| r.join(" ")) + .collect(); + let want: Vec = live + .iter() + .filter(|l| valid_at(l.window, at)) + .filter_map(project) + .collect(); + prop_assert_eq!(sorted(got), sorted(want), "step {}: {}", step, query); + } + Ok(()) +} + +fn check( + db: &Minigraf, + ctx: &Ctx, + model: &Model, + probe: &Probe, + step: usize, +) -> Result<(), TestCaseError> { + prop_assert_eq!( + db.current_tx_count(), + model.tx_count, + "step {}: tx count", + step + ); + let as_of = u64::from(probe.as_of) % (model.tx_count + 2); + let at = jan1_ms(AT_YEARS[probe.at]); + + check_full_rows(db, ctx, model, None, step)?; + check_full_rows(db, ctx, model, Some(as_of), step)?; + check_shapes(db, ctx, model, probe, None, None, step)?; + check_shapes(db, ctx, model, probe, None, Some(at), step)?; + check_shapes(db, ctx, model, probe, Some(as_of), Some(at), step)?; + check_shapes(db, ctx, model, probe, Some(as_of), None, step)?; + Ok(()) +} + +// ── Driver ──────────────────────────────────────────────────────────────────── + +fn open(path: &Path, mode: OpenMode) -> Result { + let opts = OpenOptions::new().synchronous(SyncMode::Normal); + let opts = match mode { + OpenMode::Default => opts, + OpenMode::SmallCache => opts.page_cache_size(4), + OpenMode::AutoCheckpoint => opts.wal_checkpoint_threshold(2), + }; + Minigraf::open_with_options(path, opts) + .map_err(|e| TestCaseError::fail(format!("open failed ({})", e.code()))) +} + +/// Copy the database file and its WAL as they are on disk right now. On +/// Windows, where locks are mandatory, the caller closes the handle first, +/// which turns the step into a plain reopen. +fn crash_copy(from: &Path, to: &Path, step: usize) -> Result<(), TestCaseError> { + let wal = |p: &Path| { + let mut s = p.as_os_str().to_owned(); + s.push(".wal"); + std::path::PathBuf::from(s) + }; + let copy = |a: &Path, b: &Path| { + std::fs::copy(a, b) + .map(|_| ()) + .map_err(|_| TestCaseError::fail(format!("step {step}: copy failed"))) + }; + copy(from, to)?; + if wal(from).exists() { + copy(&wal(from), &wal(to))?; + } + Ok(()) +} + +fn verify(db: &Minigraf, step: usize) -> Result<(), TestCaseError> { + let report = db + .verify() + .map_err(|e| TestCaseError::fail(format!("step {step}: verify failed ({})", e.code())))?; + prop_assert!(report.is_ok(), "step {}: verify found problems", step); + Ok(()) +} + +/// Expect `result` to match the model's verdict: Ok when accepted, API-011 +/// when rejected. +fn expect_outcome( + result: Result, + accepted: bool, + step: usize, +) -> Result<(), TestCaseError> { + match (result, accepted) { + (Ok(_), true) => Ok(()), + (Err(e), false) if e.code() == "API-011" => Ok(()), + (Ok(_), false) => Err(TestCaseError::fail(format!( + "step {step}: accepted, model expects API-011" + ))), + (Err(e), _) => Err(TestCaseError::fail(format!( + "step {step}: unexpected error {}", + e.code() + ))), + } +} + +fn run(steps: &[Step]) -> Result<(), TestCaseError> { + let dir = tempfile::tempdir().map_err(|_| TestCaseError::fail("tempdir"))?; + let mut path = dir.path().join("model.graph"); + let ctx = Ctx { + uuids: (0..ENTITIES).map(|i| (entity_uuid(i), i)).collect(), + }; + let mut model = Model::default(); + let mut db = Some(open(&path, OpenMode::Default)?); + + for (i, step) in steps.iter().enumerate() { + match &step.op { + Op::Exec(stmt) => { + let handle = db + .as_ref() + .ok_or_else(|| TestCaseError::fail("no handle"))?; + let result = handle.execute(&stmt.edn()); + let accepted = model.commit(std::slice::from_ref(stmt)); + expect_outcome(result, accepted, i)?; + } + Op::WriteTx { stmts, commit } => { + let handle = db + .as_ref() + .ok_or_else(|| TestCaseError::fail("no handle"))?; + let mut tx = handle + .begin_write() + .map_err(|e| TestCaseError::fail(format!("begin_write ({})", e.code())))?; + for stmt in stmts { + tx.execute(&stmt.edn()).map_err(|e| { + TestCaseError::fail(format!("step {i}: staged write ({})", e.code())) + })?; + } + if *commit { + let accepted = model.commit(stmts); + expect_outcome(tx.commit(), accepted, i)?; + } else { + tx.rollback(); + } + } + Op::Checkpoint => { + let handle = db + .as_ref() + .ok_or_else(|| TestCaseError::fail("no handle"))?; + handle + .checkpoint() + .map_err(|e| TestCaseError::fail(format!("checkpoint ({})", e.code())))?; + verify(handle, i)?; + } + Op::Reopen(mode) => { + drop(db.take()); + let handle = open(&path, *mode)?; + verify(&handle, i)?; + db = Some(handle); + } + Op::Crash(mode) => { + let copy = dir.path().join(format!("crash{i}.graph")); + if cfg!(windows) { + drop(db.take()); + } + crash_copy(&path, ©, i)?; + drop(db.take()); + path = copy; + let handle = open(&path, *mode)?; + verify(&handle, i)?; + db = Some(handle); + } + } + let handle = db + .as_ref() + .ok_or_else(|| TestCaseError::fail("no handle"))?; + check(handle, &ctx, &model, &step.probe, i)?; + } + Ok(()) +} + +fn cases() -> u32 { + std::env::var("PROPTEST_CASES") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(24) +} + +proptest! { + #![proptest_config(ProptestConfig::with_cases(cases()))] + + /// Every read after every step matches the reference model. + #[test] + fn file_backed_db_matches_model(steps in arb_steps()) { + run(&steps)?; + } +}