From d5027d81db68851ea03444b76529c62675f4eda3 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 8 Oct 2026 23:57:13 +0530 Subject: [PATCH 1/3] docs: restore TEST_COVERAGE.md emptied by the v2.0.4 merge The merge of main into v3 (d61b9a4, #488) resolved a conflict in docs/TEST_COVERAGE.md by leaving the file empty. Restore v3's version from before the merge; main's v2.0.4 edits to it are v2.x-only. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- docs/TEST_COVERAGE.md | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index e69de29bb2..867c579d83 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -0,0 +1,42 @@ +# Minigraf Test Coverage + +## Coverage Summary + +**Verified**: 2026-10-08 with `cargo test --quiet` + +**Result**: 1,363 passing tests and 9 ignored tests (1,372 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/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). 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. 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 + +- **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. +- **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). +- **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. +- **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery. +- **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). +- **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. + +### Ignored Tests + +The nine ignored tests are intentionally excluded from a normal local run: + +- Six rustdoc examples that reference internal types and cannot compile as standalone examples. +- One high-contention concurrency stress test intended for scheduled runs. +- One long-haul smoke test intended for scheduled runs. +- One size test at 1.15M facts (`size_per_fact_in_433_shape_1m`), run by the nightly smoke workflow. + +### Reproducing + +```bash +# Standard suite +cargo test --quiet + +# Include the scheduled/ignored tests when the host supports them +cargo test -- --include-ignored + +# Generate a local branch-coverage report (requires cargo-llvm-cov) +cargo llvm-cov --branch --html +``` + +Coverage percentages are intentionally not fixed in this document: they depend on the current toolchain and instrumentation. The CI coverage gates and the command above are the source of truth for the current measurement. From 3d29db8a7731c8fffa04bec9519494964a5cf13f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 8 Oct 2026 23:57:13 +0530 Subject: [PATCH 2/3] test: widen property tests to joins, negation, predicates and time travel (#386) tests/property_test.rs now writes random histories (batched transacts, retracts, write transactions, checkpoints) and compares random queries (1-3 joined patterns, not/not-join, a comparison predicate, :as-of, :valid-at, :any-valid-time) with a reference evaluator, in memory and against a file before and after a reopen. A write or query error fails the test; the three existing properties no longer count an error as an empty result. The temporal reference model of the model-based test (#385) moves to tests/reference_model/ and is shared by both tests. The nightly job drops from 8M to 1M cases (1M in memory, 100k file-backed, ~1.6 h locally). Mutation checks are listed in the spec. Refs #386 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- .github/workflows/property-tests.yml | 5 +- CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- .../plans/2026-10-08-wider-property-tests.md | 23 + .../2026-10-08-wider-property-tests-design.md | 136 +++ tests/model_based_test.rs | 476 +---------- tests/property_test.proptest-regressions | 2 + tests/property_test.rs | 798 +++++++++++++++++- tests/reference_model/mod.rs | 483 +++++++++++ 10 files changed, 1429 insertions(+), 502 deletions(-) create mode 100644 docs/superpowers/plans/2026-10-08-wider-property-tests.md create mode 100644 docs/superpowers/specs/2026-10-08-wider-property-tests-design.md create mode 100644 tests/reference_model/mod.rs diff --git a/.github/workflows/property-tests.yml b/.github/workflows/property-tests.yml index 2fe4261a46..65a1072e5c 100644 --- a/.github/workflows/property-tests.yml +++ b/.github/workflows/property-tests.yml @@ -19,8 +19,11 @@ jobs: fail-fast: false matrix: include: + # Query properties (#386): 1M in-memory cases (~3 ms each) and a + # tenth as many file-backed ones (~57 ms each, checkpoint and + # reopen), plus 1M of each one-pattern property; ~1.6 h locally. - test: property_test - cases: 8000000 + cases: 1000000 # Model-based storage test (#385): each case runs up to 50 steps # against a file, ~0.1 s per case. - test: model_based_test diff --git a/CLAUDE.md b/CLAUDE.md index 4cba5ad6c4..025f4415c4 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 -**1372 tests** (1363 passing, 9 ignored; unit + integration + doc). +**1374 tests** (1365 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 7d35475136..59f0e9f490 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 1372 tests +cargo test # run 1374 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 867c579d83..43e2f521e1 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-08 with `cargo test --quiet` -**Result**: 1,363 passing tests and 9 ignored tests (1,372 total) +**Result**: 1,365 passing tests and 9 ignored tests (1,374 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/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). 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. 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). `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). 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. 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/plans/2026-10-08-wider-property-tests.md b/docs/superpowers/plans/2026-10-08-wider-property-tests.md new file mode 100644 index 0000000000..e8b5616654 --- /dev/null +++ b/docs/superpowers/plans/2026-10-08-wider-property-tests.md @@ -0,0 +1,23 @@ +# Wider property tests — Plan + +Spec: `docs/superpowers/specs/2026-10-08-wider-property-tests-design.md` (#386). + +1. **Shared model:** move pools, time grid, `Window`/`Effective`, `valid_at`, + statement types and `Model` from `tests/model_based_test.rs` to + `tests/reference_model/mod.rs`; `mod reference_model;` in both files. The + model-based test must pass unchanged. +2. **Error fix:** the three existing properties fail on a write or query error. +3. **Histories:** `arb_history()` over `Transact`/`Retract`/`WriteTx`/`Checkpoint`, + accepted statements only; apply to the model with `Model::commit`. +4. **Queries:** `Query { patterns, neg, pred, temporal, find }` with a renderer + to EDN and `arb_query()` that keeps each pattern after the first joined. +5. **Reference evaluator:** visible facts, nested-loop join, `not`/`not-join`, + predicates as `eval_binop`, projection; multiset or set comparison. +6. **Properties:** in-memory and file-backed (queries before and after reopen). +7. **Self-check:** each mutation in spec §8 applied to the reference must fail + the test; then restore. +8. **Timing:** measure per-case time; set nightly `PROPTEST_CASES` for ~3 h and + comment it in `property-tests.yml`. +9. **Docs:** test count in CLAUDE.md, README.md, docs/TEST_COVERAGE.md. +10. **PR** to `v3`, "Refs #386", monitor CI. Then the v2.x backport PR to `main` + (spec §9). diff --git a/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md b/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md new file mode 100644 index 0000000000..ac31dc6168 --- /dev/null +++ b/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md @@ -0,0 +1,136 @@ +# Wider property tests — Design + +**Issue:** #386, tracker #383 +**Milestone:** v3.0.0, branch `v3`, with a v2.x backport to `main` (test and CI only; +no library change) + +## 1. Goal + +`tests/property_test.rs` checks query semantics against a reference evaluator, +but only for one-pattern queries over an in-memory database written one fact per +`transact`, and it counts a query error as an empty result. Widen it to joins, +negation, predicates and temporal queries over histories written in batches with +retractions, on both the in-memory and the file-backed database. The sibling +model-based test (#385) covers operation sequences with single-pattern reads; +this test covers query semantics. + +## 2. Shared reference model + +The temporal reference of `tests/model_based_test.rs` (value pool `V`, the time +grid, `Window`/`Effective`, `valid_at`, and `Model` with `verdict`, `records`, +`commit` and `live`) moves unchanged to `tests/reference_model/mod.rs`. Both test +files use it with `mod reference_model;`. One copy of the subtle rules (#435 one +window per triple, #477 latest statement wins, API-011/API-019 verdicts) keeps +the two tests from drifting apart. + +## 3. Histories + +A case writes a history of 1–12 operations to a fresh database: + +| Op | API | +|---|---| +| `Transact` | one `(transact …)` of 1–8 facts, tx- and fact-level windows from the grid | +| `Retract` | one `(retract …)` of 1–4 triples | +| `WriteTx` | `begin_write`, 1–4 transact/retract statements, `commit` | +| `Checkpoint` | `checkpoint()` (file backend only; a no-op in memory) | + +Facts come from the shared pools (4 entities, 3 attributes, 18 values including +refs to the entities), so batches repeat entities and attributes, and retractions +hit live triples. Generated statements are always accepted: an empty or inverted +window is rewritten to start in 2000 and a repeated triple in one statement +keeps one window. Rejections are the model-based test's job; here every write +must succeed. + +## 4. Backends + +- **Memory:** `Minigraf::in_memory()`. +- **File:** `open_with_options` in a temp dir (`SyncMode::Normal`), with the + history's `Checkpoint` ops applied, so the queries read a mix of checkpointed + and pending facts. The queries run once on the open handle, then again after a + drop and reopen (default options or `page_cache_size(4)`). + +## 5. Queries + +Each case runs 1–4 generated queries. A query has: + +- **Patterns:** 1–3 `[E A V]`. `E` is an entity variable (`?e0`–`?e2`) or an + entity constant. `A` is an attribute constant, or rarely `?a`. `V` is a value + variable (`?v0`–`?v2`), an entity variable (a ref join), a pool constant, or + `_`. The small variable pools make patterns share variables, so most queries + with two or three patterns are joins. Every pattern after the first shares a + variable with an earlier one, so there are no cross products. +- **Negation (optional):** `(not [E A V])` over variables already bound, or + `(not-join [?x] [?x A ?fresh])` with a variable already bound. +- **Predicate (optional):** `[(op ?x c)]` or `[(op ?x ?y)]` with `op` in + `< <= > >= = !=`, over bound variables. +- **Temporal:** none, `:as-of N`, `:valid-at T`, both, or `:any-valid-time`. + `N` ranges over 0..=tx count + 1, `T` over the model-based grid. +- **Find:** a non-empty subset of the bound variables. + +## 6. Reference evaluator + +1. Visible facts: `Model::live(as_of)`, then `valid_at` (skipped for + `:any-valid-time`). +2. Patterns: a nested-loop join over the visible facts, one binding map per + combination; `_` matches anything and binds nothing; an entity variable in `V` + matches `V::Ref`. +3. `not` removes a binding when its pattern matches a visible fact; `not-join` + when some visible fact matches with the join variable bound. +4. Predicates follow `eval_binop`: `=`/`!=` compare values structurally; + orderings compare two strings bytewise and numbers as `f64`; any other pair is + a type error that drops the binding (no query error). +5. Project onto the find variables. + +**Comparison.** The engine returns one row per binding, not a set: `[:find ?e +:where [?e :c ?v]]` gives one row per `?v`. When the find covers every variable +and no pattern has `_`, each binding is distinct, so rows are compared as sorted +multisets; a duplicated or dropped fact then shows up. Otherwise rows are +compared as sets, which holds whether the engine keeps bag semantics or moves to +sets. + +Results render as in the model-based test: entities as pool indices, so failure +messages carry no `Uuid` (CodeQL rule). + +## 7. Errors + +Any write, checkpoint, reopen or query error fails the case with its error code. +The three existing properties stay (one fact per `transact`, cheap), with +`if result.is_err() { return vec![]; }` replaced by a failure. + +## 8. Cases and CI + +New properties read `PROPTEST_CASES` (default 256 in normal CI). The file-backed +property runs a tenth of that, since each case touches the disk. Measured per +case: 3 ms in memory, 57 ms file-backed, 0.7 ms for each one-pattern property. +The nightly count drops from 8,000,000 to 1,000,000: about 1.6 h locally, well +inside the 6-hour limit on a slower runner. + +Histories and query constants favour small integers and entities, and drop the +model-based test's hot triple: with the shared generators only 16% of queries +returned rows; with these, about 35% do, over a mean of 13 visible facts. + +Mutation checks during development, each caught: `:valid-at` inclusive at +`:valid-to`; `<` evaluated as `<=`; a predicate type error that keeps the row; +the on-disk read skipping retractions, or not hiding a triple's older +transactions; and, in the reference, `not` ignoring `:as-of` and patterns +ignoring their attribute. (Emitting on-disk retractions as assertions is an +equivalent mutant: the executor's net-assert step drops them.) Minimized +failures become named regression tests in the same file. + +## 9. v2.x backport + +A separate PR to `main` ports the test with a reference limited to v2.x +semantics: + +- No v8 model rules: v2 has no API-011/API-019 (#435, #436), so the generator + never repeats a triple within one transaction and never writes an empty + window. +- #371 (same-transaction multi-valued facts read back as one value): no + transaction writes two values of one entity and attribute, and no batched + retract removes two such values. +- #435 (several valid windows per triple): a triple is never asserted again + while it is live. +- #406/#414 do not apply: generated finds are always bound. + +`verify()` is not called (it does not exist on v2). The PR names these +exclusions. diff --git a/tests/model_based_test.rs b/tests/model_based_test.rs index b8af0c4284..b4d02b7c18 100644 --- a/tests/model_based_test.rs +++ b/tests/model_based_test.rs @@ -11,196 +11,18 @@ //! Design: docs/superpowers/specs/2026-10-07-model-based-test-design.md #![cfg(not(target_arch = "wasm32"))] +mod reference_model; + +use minigraf::MinigrafError; use minigraf::db::{Minigraf, OpenOptions, SyncMode}; -use minigraf::{MinigrafError, QueryResult, Value}; use proptest::prelude::*; use proptest::test_runner::TestCaseError; +use reference_model::*; 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, @@ -238,109 +60,6 @@ struct Step { 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::bool::weighted(0.9), - ) - .prop_map(|(window, facts, repeat, fix_windows)| { - 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); - } - // Usually an empty or inverted window is rewritten to start in - // 2000 (every `:valid-to` on the grid is later); otherwise the - // statement is an API-019 rejection (#436). - for f in fix_windows.then_some(&mut facts).into_iter().flatten() { - 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), @@ -401,193 +120,6 @@ fn arb_steps() -> impl Strategy> { ) } -// ── 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 error code a statement is rejected with, if any: API-019 for an - /// empty or inverted window (#436), then API-011 for one triple with two - /// windows in the statement. - fn verdict(stmt: &Stmt) -> Option<&'static str> { - let Stmt::Transact { window, facts } = stmt else { - return None; - }; - let windows: Vec = facts.iter().map(|f| effective(*window, f.window)).collect(); - if !windows.iter().all(|w| window_is_valid(*w)) { - return Some("API-019"); - } - for (i, x) in facts.iter().enumerate() { - for (j, y) in facts.iter().enumerate().skip(i + 1) { - if x.e == y.e && x.a == y.a && x.v == y.v && windows[i] != windows[j] { - return Some("API-011"); - } - } - } - None - } - - /// The records a committed transaction of accepted `stmts` adds: each - /// triple's records from the last statement that wrote it (#477). - fn records(stmts: &[Stmt], tx: u64) -> Vec { - let mut out: Vec<(usize, Record)> = Vec::new(); - for (n, stmt) in stmts.iter().enumerate() { - match stmt { - Stmt::Transact { window, facts } => { - for f in facts { - out.push(( - n, - 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(( - n, - Record { - tx, - e: *e, - a: *a, - v: v.clone(), - window: (None, FOREVER), - asserted: false, - }, - )); - } - } - } - } - let last = |r: &Record| { - out.iter() - .filter(|(_, x)| x.e == r.e && x.a == r.a && x.v == r.v) - .map(|(n, _)| *n) - .max() - }; - out.iter() - .filter(|(n, r)| last(r) == Some(*n)) - .map(|(_, r)| r.clone()) - .collect() - } - - /// Apply a committed transaction of accepted statements. - fn commit(&mut self, stmts: &[Stmt]) { - if stmts.is_empty() { - return; - } - self.tx_count += 1; - self.log.extend(Self::records(stmts, self.tx_count)); - } - - 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> { - self.result_rows(db.execute(query), query) - } - - fn result_rows( - &self, - result: Result, - query: &str, - ) -> Result>, TestCaseError> { - let result = result - .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, diff --git a/tests/property_test.proptest-regressions b/tests/property_test.proptest-regressions index 8217048bf5..64e7edeec1 100644 --- a/tests/property_test.proptest-regressions +++ b/tests/property_test.proptest-regressions @@ -6,3 +6,5 @@ # everyone who runs the test benefits from these saved cases. cc 06842cd54e6438a54a2509966aa47b3763aa08b4daccf7953647c16767de6703 # shrinks to facts = [TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }] cc 0cb2c60faac9ad670ed1b43ec1d56273127b4c442301d0425c859ef704510102 # shrinks to facts = [TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }] +cc f99380e7856d179e1ca7f0bdb4ea50d66edfb4da1e63c9fa3198691f59e7b241 # shrinks to history = [Exec(Transact { window: Window { vf: None, vt: None }, facts: [FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }] })], queries = [Query { pats: [Pat { e: Var(E(0)), a: Some(2), v: Const(Str(2)) }, Pat { e: Var(E(0)), a: Some(0), v: Var(V(2)) }], neg: None, pred: None, temporal: Temporal { as_of: Some(60096), at: Any }, find: [V(2)] }, Query { pats: [Pat { e: Var(E(2)), a: Some(0), v: Const(Int(2)) }], neg: None, pred: Some(Pred { op: Ne, l: E(2), r: Const(Ref(2)) }), temporal: Temporal { as_of: Some(43407), at: Now }, find: [E(2)] }], reopen = Default +cc 00bd8fdbbe9120bbcfe48fd90d0e9219fe1d7c7173da769fbcbfd4f9e4105915 # shrinks to history = [Exec(Transact { window: Window { vf: None, vt: None }, facts: [FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }] })], queries = [Query { pats: [Pat { e: Var(E(0)), a: None, v: Var(E(0)) }], neg: None, pred: Some(Pred { op: Lt, l: E(0), r: Const(Ref(0)) }), temporal: Temporal { as_of: None, at: Now }, find: [E(0)] }] diff --git a/tests/property_test.rs b/tests/property_test.rs index 96bbc48de3..4556f8c24d 100644 --- a/tests/property_test.rs +++ b/tests/property_test.rs @@ -1,15 +1,27 @@ -//! Cross-feature property tests (#221). +//! Cross-feature property tests (#221, #386). //! //! Compares Minigraf query results against a deliberately simple reference -//! evaluator for randomly-generated small graphs. +//! evaluator. The first three properties write one fact per `transact` and run +//! one-pattern queries. The others write random histories (batched transacts, +//! retractions, write transactions, checkpoints) and run random queries with +//! joins, `not`/`not-join`, predicates, `:as-of`, `:valid-at` and +//! `:any-valid-time`, in memory and against a file that is reopened. //! //! Run: cargo test --test property_test //! More cases: PROPTEST_CASES=500 cargo test --test property_test +//! +//! Design: docs/superpowers/specs/2026-10-08-wider-property-tests-design.md #![cfg(not(target_arch = "wasm32"))] +mod reference_model; + use minigraf::QueryResult; -use minigraf::db::Minigraf; +use minigraf::db::{Minigraf, OpenOptions, SyncMode}; use proptest::prelude::*; +use proptest::test_runner::TestCaseError; +use reference_model::*; +use std::collections::HashMap; +use std::path::Path; use uuid::Uuid; #[derive(Debug, Clone)] @@ -43,12 +55,6 @@ struct TestQuery { negation_attr: Option, } -/// Compute the deterministic UUID for a keyword entity (mirrors `edn_to_entity_id`). -fn entity_uuid(idx: usize) -> Uuid { - let kw = format!(":e{idx}"); - Uuid::new_v5(&Uuid::NAMESPACE_OID, kw.as_bytes()) -} - // ── Reference evaluator (naive, independent of production code) ─────────────── fn ref_eval(facts: &[TestFact], query: &TestQuery) -> Vec { @@ -80,19 +86,23 @@ fn ref_eval(facts: &[TestFact], query: &TestQuery) -> Vec { // ── Minigraf evaluator ──────────────────────────────────────────────────────── -fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Vec { +fn minigraf_eval( + facts: &[TestFact], + query: &TestQuery, + max_entity: usize, +) -> Result, TestCaseError> { // Pre-compute UUID → index mapping for all possible entity indices. - let uuid_to_idx: std::collections::HashMap = - (0..max_entity).map(|i| (entity_uuid(i), i)).collect(); + let uuid_to_idx: HashMap = (0..max_entity).map(|i| (entity_uuid(i), i)).collect(); - let db = Minigraf::in_memory().unwrap(); + let db = Minigraf::in_memory().map_err(|_| TestCaseError::fail("in_memory failed"))?; for fact in facts { let entity_kw = format!(":e{}", fact.entity); let val_edn = fact.value.to_edn(); let attr = &fact.attribute; let edn = format!(r#"(transact [[{entity_kw} {attr} {val_edn}]])"#); - let _ = db.execute(&edn); + db.execute(&edn) + .map_err(|e| TestCaseError::fail(format!("transact failed ({})", e.code())))?; } let val_clause = match &query.value_filter { @@ -108,12 +118,10 @@ fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Ve let attr = &query.attribute; let datalog = format!("(query [:find ?e :where [?e {attr} ?v]{val_clause}{neg_clause}])"); - let result = db.execute(&datalog); - // Skip test cases where the generated query fails to parse/evaluate. - if result.is_err() { - return vec![]; - } - match result.unwrap() { + let result = db + .execute(&datalog) + .map_err(|e| TestCaseError::fail(format!("query failed ({}): {datalog}", e.code())))?; + match result { QueryResult::QueryResults { results, .. } => { let mut entities: Vec = results .into_iter() @@ -125,9 +133,9 @@ fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Ve .collect(); entities.sort(); entities.dedup(); - entities + Ok(entities) } - _ => vec![], + _ => Err(TestCaseError::fail("not a query result")), } } @@ -171,7 +179,7 @@ proptest! { negation_attr: None, }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; prop_assert_eq!(ref_result, mg_result); } @@ -184,7 +192,7 @@ proptest! { negation_attr: Some(":active".to_string()), }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; let neg_entities: std::collections::HashSet = facts .iter() @@ -211,8 +219,748 @@ proptest! { negation_attr: None, }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; prop_assert!(ref_result.is_empty(), "reference: impossible path must be empty"); prop_assert!(mg_result.is_empty(), "minigraf: impossible path must be empty"); } } + +// ── Histories (#386) ────────────────────────────────────────────────────────── + +/// One write of a history. Every generated statement is accepted. +#[derive(Clone, Debug)] +enum HistoryOp { + Exec(Stmt), + WriteTx(Vec), + /// `checkpoint()` on the file backend; nothing in memory. + Checkpoint, +} + +/// Make a statement acceptable: an empty or inverted window starts in 2000 +/// (API-019), and a triple repeated in one statement keeps its first fact +/// (API-011). Rejections are the model-based test's job. +fn accepted(stmt: Stmt) -> Stmt { + match stmt { + Stmt::Transact { window, facts } => { + let mut kept: Vec = Vec::new(); + for mut f in facts { + if kept.iter().any(|k| k.e == f.e && k.a == f.a && k.v == f.v) { + continue; + } + if !window_is_valid(effective(window, f.window)) { + f.window.vf = Some(0); + } + kept.push(f); + } + Stmt::Transact { + window, + facts: kept, + } + } + retract => retract, + } +} + +/// A value, weighted to small integers and entities so that facts share +/// values and joins on them match. +fn arb_dense_v() -> impl Strategy { + prop_oneof![ + 3 => (0i64..3).prop_map(V::Int), + 2 => (0..ENTITIES).prop_map(V::Ref), + 2 => arb_v(), + ] +} + +fn arb_dense_triple() -> impl Strategy { + (0..ENTITIES, 0..ATTRS.len(), arb_dense_v()) +} + +/// Larger batches than the model-based test's, without its hot triple, so +/// that a history leaves many live facts to join. +fn arb_dense_transact() -> impl Strategy { + ( + arb_window(), + prop::collection::vec((arb_dense_triple(), arb_window()), 1..10), + ) + .prop_map(|(window, facts)| { + accepted(Stmt::Transact { + window, + facts: facts + .into_iter() + .map(|((e, a, v), window)| FactSpec { e, a, v, window }) + .collect(), + }) + }) +} + +fn arb_dense_retract() -> impl Strategy { + prop::collection::vec(arb_dense_triple(), 1..4).prop_map(|facts| Stmt::Retract { facts }) +} + +fn arb_history_op() -> impl Strategy { + prop_oneof![ + 6 => arb_dense_transact().prop_map(HistoryOp::Exec), + 2 => arb_dense_retract().prop_map(HistoryOp::Exec), + 2 => prop::collection::vec( + prop_oneof![3 => arb_dense_transact(), 2 => arb_dense_retract()], + 1..5, + ) + .prop_map(HistoryOp::WriteTx), + 2 => Just(HistoryOp::Checkpoint), + ] +} + +fn arb_history() -> impl Strategy> { + prop::collection::vec(arb_history_op(), 1..17) +} + +// ── Queries (#386) ──────────────────────────────────────────────────────────── + +/// A query variable: entity-like (`?e0`–`?e2`, in E or V position), value +/// (`?v0`–`?v2`, V position only) or the attribute variable `?a`. +#[derive(Clone, Copy, Debug, PartialEq)] +enum Var { + E(u8), + V(u8), + A, +} + +impl Var { + fn name(self) -> String { + match self { + Var::E(i) => format!("?e{i}"), + Var::V(i) => format!("?v{i}"), + Var::A => "?a".to_string(), + } + } +} + +#[derive(Clone, Debug, PartialEq)] +enum Term { + Var(Var), + Entity(usize), + Const(V), + Blank, +} + +#[derive(Clone, Debug)] +struct Pat { + e: Term, + /// `None` is the attribute variable `?a`. + a: Option, + v: Term, +} + +impl Pat { + fn vars(&self) -> Vec { + let mut out = Vec::new(); + if let Term::Var(x) = self.e { + out.push(x); + } + if self.a.is_none() { + out.push(Var::A); + } + if let Term::Var(x) = self.v { + out.push(x); + } + out + } + + fn edn(&self) -> String { + let term = |t: &Term| match t { + Term::Var(x) => x.name(), + Term::Entity(e) => format!(":e{e}"), + Term::Const(v) => v.edn(), + Term::Blank => "_".to_string(), + }; + let a = self.a.map_or("?a".to_string(), |a| ATTRS[a].to_string()); + format!("[{} {a} {}]", term(&self.e), term(&self.v)) + } +} + +#[derive(Clone, Debug)] +enum Neg { + Not(Pat), + /// `(not-join [?x] [?x a v])`, with `v` a fresh `?z` when `None`. + NotJoin { + var: Var, + a: usize, + v: Option, + }, +} + +#[derive(Clone, Copy, Debug)] +enum CmpOp { + Lt, + Le, + Gt, + Ge, + Eq, + Ne, +} + +impl CmpOp { + fn edn(self) -> &'static str { + match self { + CmpOp::Lt => "<", + CmpOp::Le => "<=", + CmpOp::Gt => ">", + CmpOp::Ge => ">=", + CmpOp::Eq => "=", + CmpOp::Ne => "!=", + } + } +} + +#[derive(Clone, Debug)] +enum Operand { + Var(Var), + Const(V), +} + +#[derive(Clone, Debug)] +struct Pred { + op: CmpOp, + l: Var, + r: Operand, +} + +#[derive(Clone, Copy, Debug)] +struct Temporal { + /// Raw `:as-of`; reduced modulo (tx count + 2) when the query runs. + as_of: Option, + at: At, +} + +#[derive(Clone, Copy, Debug)] +enum At { + Now, + /// An index into `AT_YEARS`. + Year(usize), + Any, +} + +#[derive(Clone, Debug)] +struct Query { + pats: Vec, + neg: Option, + pred: Option, + temporal: Temporal, + /// The variables in `:find`, in order. + find: Vec, +} + +/// Variables bound by the patterns, in order of first appearance. +fn bound_vars(pats: &[Pat]) -> Vec { + let mut out: Vec = Vec::new(); + for x in pats.iter().flat_map(Pat::vars) { + if !out.contains(&x) { + out.push(x); + } + } + out +} + +impl Query { + fn edn(&self, tx_count: u64) -> String { + let mut opts = String::new(); + if let Some(n) = self.as_of(tx_count) { + opts.push_str(&format!(":as-of {n} ")); + } + match self.temporal.at { + At::Now => {} + At::Year(i) => opts.push_str(&format!(":valid-at \"{}-01-01\" ", AT_YEARS[i])), + At::Any => opts.push_str(":any-valid-time "), + } + let mut clauses: Vec = self.pats.iter().map(Pat::edn).collect(); + match &self.neg { + None => {} + Some(Neg::Not(p)) => clauses.push(format!("(not {})", p.edn())), + Some(Neg::NotJoin { var, a, v }) => { + let v = v.as_ref().map_or("?z".to_string(), V::edn); + let x = var.name(); + clauses.push(format!("(not-join [{x}] [{x} {} {v}])", ATTRS[*a])); + } + } + if let Some(p) = &self.pred { + let r = match &p.r { + Operand::Var(x) => x.name(), + Operand::Const(v) => v.edn(), + }; + clauses.push(format!("[({} {} {r})]", p.op.edn(), p.l.name())); + } + let find: Vec = self.find.iter().map(|x| x.name()).collect(); + format!( + "(query [:find {} {opts}:where {}])", + find.join(" "), + clauses.join(" ") + ) + } + + fn as_of(&self, tx_count: u64) -> Option { + self.temporal.as_of.map(|n| u64::from(n) % (tx_count + 2)) + } + + /// Rows are compared as multisets when each binding is a distinct row: + /// every variable is in `:find` and no pattern has `_`. + fn distinct_rows(&self) -> bool { + self.find.len() == bound_vars(&self.pats).len() + && self + .pats + .iter() + .all(|p| p.e != Term::Blank && p.v != Term::Blank) + } +} + +fn arb_var() -> impl Strategy { + prop_oneof![(0u8..3).prop_map(Var::E), (0u8..3).prop_map(Var::V)] +} + +fn arb_e_term() -> impl Strategy { + prop_oneof![ + 4 => (0u8..3).prop_map(|i| Term::Var(Var::E(i))), + 1 => (0..ENTITIES).prop_map(Term::Entity), + ] +} + +fn arb_v_term() -> impl Strategy { + prop_oneof![ + 4 => (0u8..3).prop_map(|i| Term::Var(Var::V(i))), + 2 => (0u8..3).prop_map(|i| Term::Var(Var::E(i))), + 1 => arb_dense_v().prop_map(Term::Const), + 1 => Just(Term::Blank), + ] +} + +fn arb_pat() -> impl Strategy { + ( + arb_e_term(), + prop::option::weighted(0.9, 0..ATTRS.len()), + arb_v_term(), + ) + .prop_map(|(e, a, v)| Pat { e, a, v }) +} + +fn arb_cmp() -> impl Strategy { + prop_oneof![ + Just(CmpOp::Lt), + Just(CmpOp::Le), + Just(CmpOp::Gt), + Just(CmpOp::Ge), + Just(CmpOp::Eq), + Just(CmpOp::Ne), + ] +} + +/// Raw query parts; `build_query` turns them into a well-formed query. +type RawQuery = ( + Vec, + Option<(bool, Pat, usize, Option)>, + Option<(CmpOp, bool, V)>, + Temporal, + Vec, + (usize, usize), +); + +fn arb_temporal() -> impl Strategy { + ( + prop::option::weighted(0.4, any::()), + prop_oneof![ + 2 => Just(At::Now), + 2 => (0..AT_YEARS.len()).prop_map(At::Year), + 1 => Just(At::Any), + ], + ) + .prop_map(|(as_of, at)| Temporal { as_of, at }) +} + +fn arb_query() -> impl Strategy { + ( + prop::collection::vec(arb_pat(), 1..4), + prop::option::weighted( + 0.35, + ( + any::(), + arb_pat(), + 0..ATTRS.len(), + prop::option::of(arb_dense_v()), + ), + ), + prop::option::weighted(0.35, (arb_cmp(), any::(), arb_dense_v())), + arb_temporal(), + prop::collection::vec(any::(), 8), + (any::(), any::()), + ) + .prop_map(build_query) +} + +/// Pick the `n`-th (mod len) of `vars` that satisfies `ok`. +fn pick(vars: &[Var], n: usize, ok: impl Fn(Var) -> bool) -> Option { + let cands: Vec = vars.iter().copied().filter(|x| ok(*x)).collect(); + (!cands.is_empty()).then(|| cands[n % cands.len()]) +} + +fn build_query(raw: RawQuery) -> Query { + let (mut pats, neg, pred, temporal, find_mask, (n1, n2)) = raw; + + // At least one variable, so `:find` is not empty. + if bound_vars(&pats).is_empty() { + pats[0].e = Term::Var(Var::E(0)); + } + // Each pattern after the first shares a variable with the ones before it + // when they bind any, so no query is a cross product. + for i in 1..pats.len() { + let before = bound_vars(&pats[..i]); + if before.is_empty() || pats[i].vars().iter().any(|x| before.contains(x)) { + continue; + } + let pat = &mut pats[i]; + if let Some(x) = pick(&before, n1 + i, |x| matches!(x, Var::E(_))) { + pat.e = Term::Var(x); + } else if let Some(x) = pick(&before, n1 + i, |x| x != Var::A) { + pat.v = Term::Var(x); + } else { + pat.a = None; + } + } + let bound = bound_vars(&pats); + + let neg = neg.and_then(|(plain, mut p, a, v)| { + if plain { + // `not` over bound variables only: an unbound one becomes `_`. + let fix = |t: &mut Term, pos_e: bool| { + if let Term::Var(x) = *t + && (!bound.contains(&x) || (pos_e && matches!(x, Var::V(_)))) + { + *t = if pos_e { Term::Entity(0) } else { Term::Blank }; + } + }; + fix(&mut p.e, true); + fix(&mut p.v, false); + if p.a.is_none() && !bound.contains(&Var::A) { + p.a = Some(a); + } + Some(Neg::Not(p)) + } else { + pick(&bound, n2, |x| matches!(x, Var::E(_))).map(|var| Neg::NotJoin { var, a, v }) + } + }); + + let pred = pred.and_then(|(op, var_rhs, c)| { + // Mostly a value variable: orderings over entities are type errors. + let l = pick(&bound, n1, |x| matches!(x, Var::V(_))) + .or_else(|| pick(&bound, n1, |x| x != Var::A))?; + let r = match pick(&bound, n2, |x| x != Var::A && x != l) { + Some(x) if var_rhs => Operand::Var(x), + // Expressions take no `#uuid` literal (PRS-070). + _ if matches!(c, V::Ref(_)) => Operand::Const(V::Int(1)), + _ => Operand::Const(c), + }; + Some(Pred { op, l, r }) + }); + + let mut find: Vec = bound + .iter() + .zip(find_mask.iter().cycle()) + .filter(|(_, keep)| **keep) + .map(|(x, _)| *x) + .collect(); + if find.is_empty() { + find.push(bound[n1 % bound.len()]); + } + + Query { + pats, + neg, + pred, + temporal, + find, + } +} + +// ── Reference query evaluator (#386) ────────────────────────────────────────── + +/// A bound value: a pool value (entities are `V::Ref`) or an attribute. +#[derive(Clone, Debug, PartialEq)] +enum B { + Val(V), + Attr(usize), +} + +impl B { + fn render(&self) -> String { + match self { + B::Val(v) => v.render(), + B::Attr(a) => attr_render(*a), + } + } +} + +type Binding = Vec<(Var, B)>; + +fn lookup(b: &Binding, x: Var) -> Option<&B> { + b.iter().find(|(y, _)| *y == x).map(|(_, v)| v) +} + +/// Unify `term` with `value` under `b`; `None` when they conflict. +fn unify(mut b: Binding, term: &Term, value: B) -> Option { + match term { + Term::Blank => Some(b), + Term::Entity(e) => (value == B::Val(V::Ref(*e))).then_some(b), + Term::Const(c) => (value == B::Val(c.clone())).then_some(b), + Term::Var(x) => match lookup(&b, *x) { + Some(bound) => (*bound == value).then_some(b), + None => { + b.push((*x, value)); + Some(b) + } + }, + } +} + +/// Match one pattern against one fact under `b`. +fn match_fact(b: &Binding, p: &Pat, f: &Live) -> Option { + let mut b = unify(b.clone(), &p.e, B::Val(V::Ref(f.e)))?; + b = match p.a { + Some(a) => (a == f.a).then_some(b)?, + None => unify(b, &Term::Var(Var::A), B::Attr(f.a))?, + }; + unify(b, &p.v, B::Val(f.v.clone())) +} + +/// `eval_binop` for a comparison: `None` is a type error, which drops the row. +fn compare(op: CmpOp, l: &B, r: &B) -> Option { + match op { + CmpOp::Eq => return Some(l == r), + CmpOp::Ne => return Some(l != r), + _ => {} + } + let num = |b: &B| match b { + B::Val(V::Int(n)) => Some(*n as f64), + B::Val(V::Float) => Some(1.5), + _ => None, + }; + let ord = match (l, r) { + (B::Val(V::Str(a)), B::Val(V::Str(b))) => Some(pool_string(*a).cmp(&pool_string(*b))), + _ => num(l)?.partial_cmp(&num(r)?), + }?; + Some(match op { + CmpOp::Lt => ord.is_lt(), + CmpOp::Le => ord.is_le(), + CmpOp::Gt => ord.is_gt(), + CmpOp::Ge => ord.is_ge(), + CmpOp::Eq | CmpOp::Ne => unreachable!(), + }) +} + +fn ref_query(model: &Model, q: &Query) -> Vec { + let at = match q.temporal.at { + At::Now => Some(None), + At::Year(i) => Some(Some(jan1_ms(AT_YEARS[i]))), + At::Any => None, + }; + let facts: Vec = model + .live(q.as_of(model.tx_count)) + .into_iter() + .filter(|l| at.is_none_or(|at| valid_at(l.window, at))) + .collect(); + + let mut bindings: Vec = vec![Vec::new()]; + for p in &q.pats { + bindings = bindings + .iter() + .flat_map(|b| facts.iter().filter_map(|f| match_fact(b, p, f))) + .collect(); + } + match &q.neg { + None => {} + Some(Neg::Not(p)) => { + bindings.retain(|b| !facts.iter().any(|f| match_fact(b, p, f).is_some())); + } + Some(Neg::NotJoin { var, a, v }) => { + bindings.retain(|b| { + let x = lookup(b, *var); + !facts.iter().any(|f| { + x == Some(&B::Val(V::Ref(f.e))) + && f.a == *a + && v.as_ref().is_none_or(|v| *v == f.v) + }) + }); + } + } + if let Some(p) = &q.pred { + bindings.retain(|b| { + let l = lookup(b, p.l); + let r = match &p.r { + Operand::Var(x) => lookup(b, *x).cloned(), + Operand::Const(c) => Some(B::Val(c.clone())), + }; + match (l, r) { + (Some(l), Some(r)) => compare(p.op, l, &r) == Some(true), + _ => false, + } + }); + } + bindings + .iter() + .map(|b| { + q.find + .iter() + .map(|x| lookup(b, *x).map_or("?".to_string(), B::render)) + .collect::>() + .join(" ") + }) + .collect() +} + +// ── Driver (#386) ───────────────────────────────────────────────────────────── + +#[derive(Clone, Copy, Debug)] +enum Reopen { + Default, + SmallCache, +} + +fn open(path: &Path, mode: Reopen) -> Result { + let opts = OpenOptions::new().synchronous(SyncMode::Normal); + let opts = match mode { + Reopen::Default => opts, + Reopen::SmallCache => opts.page_cache_size(4), + }; + Minigraf::open_with_options(path, opts) + .map_err(|e| TestCaseError::fail(format!("open failed ({})", e.code()))) +} + +/// Write `history` to `db` and the model. `Checkpoint` runs only when +/// `checkpoints` is set (the file backend). +fn write_history( + db: &Minigraf, + model: &mut Model, + history: &[HistoryOp], + checkpoints: bool, +) -> Result<(), TestCaseError> { + let fail = |what: &str, i: usize, code: &str| { + TestCaseError::fail(format!("op {i}: {what} failed ({code})")) + }; + for (i, op) in history.iter().enumerate() { + match op { + HistoryOp::Exec(stmt) => { + db.execute(&stmt.edn()) + .map_err(|e| fail("write", i, e.code()))?; + model.commit(std::slice::from_ref(stmt)); + } + HistoryOp::WriteTx(stmts) => { + let mut tx = db.begin_write().map_err(|e| fail("begin", i, e.code()))?; + for stmt in stmts { + tx.execute(&stmt.edn()) + .map_err(|e| fail("statement", i, e.code()))?; + } + tx.commit().map_err(|e| fail("commit", i, e.code()))?; + model.commit(stmts); + } + HistoryOp::Checkpoint => { + if checkpoints { + db.checkpoint() + .map_err(|e| fail("checkpoint", i, e.code()))?; + } + } + } + } + Ok(()) +} + +fn check_queries( + db: &Minigraf, + ctx: &Ctx, + model: &Model, + queries: &[Query], + stage: &str, +) -> Result<(), TestCaseError> { + prop_assert_eq!(db.current_tx_count(), model.tx_count, "{}: tx count", stage); + for q in queries { + let edn = q.edn(model.tx_count); + let got: Vec = ctx + .rows(db, &edn)? + .into_iter() + .map(|r| r.join(" ")) + .collect(); + let want = ref_query(model, q); + if q.distinct_rows() { + prop_assert_eq!(sorted(got), sorted(want), "{}: {}", stage, edn); + } else { + let set = |rows: Vec| { + let mut rows = sorted(rows); + rows.dedup(); + rows + }; + prop_assert_eq!(set(got), set(want), "{}: {}", stage, edn); + } + } + Ok(()) +} + +fn ctx() -> Ctx { + Ctx { + uuids: (0..ENTITIES).map(|i| (entity_uuid(i), i)).collect(), + } +} + +fn run_in_memory(history: &[HistoryOp], queries: &[Query]) -> Result<(), TestCaseError> { + let db = Minigraf::in_memory().map_err(|_| TestCaseError::fail("in_memory failed"))?; + let mut model = Model::default(); + write_history(&db, &mut model, history, false)?; + check_queries(&db, &ctx(), &model, queries, "in memory") +} + +fn run_file_backed( + history: &[HistoryOp], + queries: &[Query], + reopen: Reopen, +) -> Result<(), TestCaseError> { + let dir = tempfile::tempdir().map_err(|_| TestCaseError::fail("tempdir"))?; + let path = dir.path().join("prop.graph"); + let ctx = ctx(); + let mut model = Model::default(); + let db = open(&path, Reopen::Default)?; + write_history(&db, &mut model, history, true)?; + check_queries(&db, &ctx, &model, queries, "file, open")?; + drop(db); + let db = open(&path, reopen)?; + check_queries(&db, &ctx, &model, queries, "file, reopened") +} + +fn cases() -> u32 { + std::env::var("PROPTEST_CASES") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(256) +} + +proptest! { + #![proptest_config(ProptestConfig::with_cases(cases()))] + + /// Joins, negation, predicates and temporal queries over a random history + /// match the reference evaluator. + #[test] + fn query_matches_reference_in_memory( + history in arb_history(), + queries in prop::collection::vec(arb_query(), 1..5), + ) { + run_in_memory(&history, &queries)?; + } +} + +proptest! { + #![proptest_config(ProptestConfig::with_cases((cases() / 10).max(1)))] + + /// The same against a file: checkpoints within the history, and queries + /// both on the open handle and after a reopen. + #[test] + fn query_matches_reference_file_backed( + history in arb_history(), + queries in prop::collection::vec(arb_query(), 1..5), + reopen in prop_oneof![Just(Reopen::Default), Just(Reopen::SmallCache)], + ) { + run_file_backed(&history, &queries, reopen)?; + } +} diff --git a/tests/reference_model/mod.rs b/tests/reference_model/mod.rs new file mode 100644 index 0000000000..42abc8b26e --- /dev/null +++ b/tests/reference_model/mod.rs @@ -0,0 +1,483 @@ +//! Reference model shared by the model-based test (#385) and the property +//! tests (#386): value pools, the valid-time grid, statements, and the +//! bi-temporal log that decides which facts a query sees. +#![allow(dead_code)] + +use minigraf::db::Minigraf; +use minigraf::{MinigrafError, QueryResult, Value}; +use proptest::prelude::*; +use proptest::test_runner::TestCaseError; +use std::collections::HashMap; +use uuid::Uuid; + +// ── Pools ───────────────────────────────────────────────────────────────────── + +pub const ENTITIES: usize = 4; +pub 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. +pub 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)] +pub enum V { + Int(i64), + Bool(bool), + Kw, + Float, + Str(u8), + Ref(usize), +} + +impl V { + pub 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)), + } + } + + pub 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}"), + } + } +} + +pub 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()) + } +} + +pub 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`). +pub 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. +pub 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 +} + +pub const VF_YEARS: [i64; 4] = [2000, 2002, 2004, 2006]; +pub const VT_YEARS: [i64; 4] = [2003, 2005, 2007, 2200]; +/// `:valid-at` instants: every window bound, plus points before, between and after. +pub const AT_YEARS: [i64; 12] = [ + 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2100, 2300, +]; +pub const FOREVER: i64 = i64::MAX; + +/// An optional `:valid-from` / `:valid-to` (grid indices). +#[derive(Clone, Copy, Debug, Default, PartialEq)] +pub struct Window { + pub vf: Option, + pub vt: Option, +} + +impl Window { + pub fn is_empty(&self) -> bool { + self.vf.is_none() && self.vt.is_none() + } + + pub 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"). +pub type Effective = (Option, i64); + +pub 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) +} + +pub 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. +pub 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)] +pub struct FactSpec { + pub e: usize, + pub a: usize, + pub v: V, + pub window: Window, +} + +#[derive(Clone, Debug)] +pub enum Stmt { + Transact { + window: Window, + facts: Vec, + }, + Retract { + facts: Vec<(usize, usize, V)>, + }, +} + +impl Stmt { + pub 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 ──────────────────────────────────────────────────────────────── + +pub 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), + ] +} + +pub 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). +pub fn arb_triple() -> impl Strategy { + prop_oneof![ + 2 => (0..ENTITIES, 0..ATTRS.len(), arb_v()), + 1 => Just((0, 0, V::Int(0))), + ] +} + +pub fn arb_transact() -> impl Strategy { + ( + arb_window(), + prop::collection::vec((arb_triple(), arb_window()), 1..6), + prop::option::weighted(0.15, arb_window()), + prop::bool::weighted(0.9), + ) + .prop_map(|(window, facts, repeat, fix_windows)| { + 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); + } + // Usually an empty or inverted window is rewritten to start in + // 2000 (every `:valid-to` on the grid is later); otherwise the + // statement is an API-019 rejection (#436). + for f in fix_windows.then_some(&mut facts).into_iter().flatten() { + if !window_is_valid(effective(window, f.window)) { + f.window.vf = Some(0); + } + } + Stmt::Transact { window, facts } + }) +} + +pub fn arb_retract() -> impl Strategy { + prop::collection::vec(arb_triple(), 1..4).prop_map(|facts| Stmt::Retract { facts }) +} + +pub fn arb_stmt() -> impl Strategy { + prop_oneof![3 => arb_transact(), 2 => arb_retract()] +} + +// ── Reference model ─────────────────────────────────────────────────────────── + +#[derive(Clone, Debug)] +pub struct Record { + pub tx: u64, + pub e: usize, + pub a: usize, + pub v: V, + pub window: Effective, + pub asserted: bool, +} + +/// A live fact: one window per triple, from its newest assertion (#435). +#[derive(Clone, Debug)] +pub struct Live { + pub e: usize, + pub a: usize, + pub v: V, + pub window: Effective, + pub tx: u64, +} + +#[derive(Default)] +pub struct Model { + pub log: Vec, + pub tx_count: u64, +} + +impl Model { + /// The error code a statement is rejected with, if any: API-019 for an + /// empty or inverted window (#436), then API-011 for one triple with two + /// windows in the statement. + pub fn verdict(stmt: &Stmt) -> Option<&'static str> { + let Stmt::Transact { window, facts } = stmt else { + return None; + }; + let windows: Vec = facts.iter().map(|f| effective(*window, f.window)).collect(); + if !windows.iter().all(|w| window_is_valid(*w)) { + return Some("API-019"); + } + for (i, x) in facts.iter().enumerate() { + for (j, y) in facts.iter().enumerate().skip(i + 1) { + if x.e == y.e && x.a == y.a && x.v == y.v && windows[i] != windows[j] { + return Some("API-011"); + } + } + } + None + } + + /// The records a committed transaction of accepted `stmts` adds: each + /// triple's records from the last statement that wrote it (#477). + pub fn records(stmts: &[Stmt], tx: u64) -> Vec { + let mut out: Vec<(usize, Record)> = Vec::new(); + for (n, stmt) in stmts.iter().enumerate() { + match stmt { + Stmt::Transact { window, facts } => { + for f in facts { + out.push(( + n, + 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(( + n, + Record { + tx, + e: *e, + a: *a, + v: v.clone(), + window: (None, FOREVER), + asserted: false, + }, + )); + } + } + } + } + let last = |r: &Record| { + out.iter() + .filter(|(_, x)| x.e == r.e && x.a == r.a && x.v == r.v) + .map(|(n, _)| *n) + .max() + }; + out.iter() + .filter(|(n, r)| last(r) == Some(*n)) + .map(|(_, r)| r.clone()) + .collect() + } + + /// Apply a committed transaction of accepted statements. + pub fn commit(&mut self, stmts: &[Stmt]) { + if stmts.is_empty() { + return; + } + self.tx_count += 1; + self.log.extend(Self::records(stmts, self.tx_count)); + } + + pub 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 ──────────────────────────────────────────────────────────────────── + +pub struct Ctx { + pub uuids: HashMap, +} + +impl Ctx { + pub fn rows(&self, db: &Minigraf, query: &str) -> Result>, TestCaseError> { + self.result_rows(db.execute(query), query) + } + + pub fn result_rows( + &self, + result: Result, + query: &str, + ) -> Result>, TestCaseError> { + let result = result + .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}"))), + } + } +} + +pub fn sorted(mut rows: Vec) -> Vec { + rows.sort(); + rows +} + +pub fn attr_render(a: usize) -> String { + format!("k{}", ATTRS[a]) +} From 143cb6e68db626b046269479fbe04da96e0e9bd2 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 9 Oct 2026 00:02:18 +0530 Subject: [PATCH 3/3] test: drop an unused property-test generator (#386) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- tests/property_test.rs | 4 ---- 1 file changed, 4 deletions(-) diff --git a/tests/property_test.rs b/tests/property_test.rs index 4556f8c24d..9bb9eef436 100644 --- a/tests/property_test.rs +++ b/tests/property_test.rs @@ -512,10 +512,6 @@ impl Query { } } -fn arb_var() -> impl Strategy { - prop_oneof![(0u8..3).prop_map(Var::E), (0u8..3).prop_map(Var::V)] -} - fn arb_e_term() -> impl Strategy { prop_oneof![ 4 => (0u8..3).prop_map(|i| Term::Var(Var::E(i))),