From 7448035f013a26da13f5ee705a39e29a0779dd5c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 7 Oct 2026 19:02:55 +0530 Subject: [PATCH 1/3] docs(spec): valid-time window validation and statement order (#436, #477) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- ...e-validation-and-statement-order-design.md | 72 +++++++++++++++++++ 1 file changed, 72 insertions(+) create mode 100644 docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md diff --git a/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md b/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md new file mode 100644 index 0000000000..17af2c3c3e --- /dev/null +++ b/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md @@ -0,0 +1,72 @@ +# Valid-time window validation and statement order in transactions — Design + +**Issues:** #436, #477 (broadened), tracker #383 +**Milestone:** v3.0.0, branch `v3` (no format change; writes that succeed today can fail) +**Builds on:** `2026-10-06-one-window-per-triple-design.md` (#435) + +## 1. Rules + +1. **Empty or inverted windows are rejected (#436).** A `transact` whose effective + window for any fact has `valid_to <= valid_from` fails with the new **API-019** and + writes nothing. "Effective" means after the defaults are applied: a fact's own + bound, else the transaction's, else `valid_from` = the transaction time and + `valid_to` = forever. So `(transact {:valid-to "2020-01-01"} ...)` is rejected, + because its `valid_from` is now. +2. **Within one `(transact [...])`**, the same `(e, a, v)` with two different windows is + still **API-011**. Identical repeats are allowed and stored once. Duplicate triples in + one `retract` are allowed. +3. **Across statements of one `WriteTransaction`**, the last statement that writes an + `(e, a, v)` decides it, whether it is a `transact` or a `retract` (#477). At commit, + every record of a triple from an earlier statement is dropped. One `tx_id` cannot tell + several versions of a fact apart, so the committed transaction holds each triple's + records from one statement only. Reads inside the transaction already follow statement + order, so they now agree with the committed result. This replaces API-011's + cross-statement rejection. +4. **`LogWriter` copies records verbatim.** Without filters or middleware, an ETL target + must be identical to its source. The writer no longer collapses or rejects records + of one transaction (the API-011 check is removed). It keeps API-015 and API-016, + which protect transaction order. Readers keep their tie rules for transactions that + hold several records of one triple (a retraction in the group hides it; several + windows are kept once each), so source and target read the same. + +`load_fact`, WAL replay, migration and the log writer never check rules 1–3. Files that +already contain such data open and read as before. + +## 2. Changes + +- `src/error.rs`, `docs/ERROR_REFERENCE.md`: **API-019** "Empty or inverted valid-time + window", text `the valid-time window of {} ends at or before it starts; :valid-to must + be later than :valid-from (the transaction time when :valid-from is omitted)`. API-011 + is narrowed to one `(transact ...)`, and its text says so. +- `src/graph/storage.rs`: `check_valid_windows(facts, tx_id)` rejects any assertion whose + `valid_from` (`VALID_FROM_USE_TX_TIME` resolved to `tx_id`) is not before `valid_to`. + `FactStorage::transact`/`transact_batch` call it next to `check_one_window_per_triple`. +- `Minigraf::execute`: take `tx_id` before `allocate_tx_count`, then run both checks, so a + rejected transaction takes no `tx_count`. The same applies to the browser `apply_write`. +- `WriteTransaction::execute` (transact): run both checks on the statement (window + check against the staged `tx_id`) before staging it. A rejected statement stages + nothing, and the transaction stays usable. +- `WriteTransaction::commit`: keep each triple's records from its newest staged + statement only (the highest synthetic `tx_count`), take the commit `tx_id`, run + `check_valid_windows` on what is left (a default `valid_from` moves to the commit time, + so a `:valid-to` between staging and commit is caught here), then allocate the + `tx_count` and write. +- `src/log_writer.rs`: drop the window map and the API-011 check. + +## 3. Tests + +- Unit: `check_valid_windows` (inverted, empty, default `valid_from` against `tx_id`, + retractions ignored, forever); the commit collapse for each mix of statements. +- `tests/valid_time_window_test.rs`: API-019 from `execute` (both bounds, equal bounds, + `:valid-to` only in the past, a per-fact override inverting a transaction window), + from `WriteTransaction::execute`, and at commit, each taking no `tx_count`; old data + with an inverted window still opens. Retract-then-assert, assert-then-retract, + assert-then-assert with another window, and retract-then-retract inside one + `WriteTransaction` give the same rows before and after commit, in memory, + checkpointed and reopened. API-011 inside one statement of a `WriteTransaction` is + raised by `tx.execute`, and the transaction still commits its other statements. +- `tests/log_writer_test.rs`: a record group with two windows and an assert plus + retract of one triple is copied verbatim and reads like the source. +- `tests/model_based_test.rs`: the model applies rules 1–3 (rejections from `execute` + and `tx.execute`, last statement wins at commit) and checks reads inside a write + transaction against the committed result. From a6cd409e63026d44e4f1d4374ce1dabceb1ee4f4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 7 Oct 2026 19:02:55 +0530 Subject: [PATCH 2/3] fix: reject empty valid-time windows; last statement wins in a transaction (#436, #477) A transact whose effective valid-time window ends at or before it starts is now rejected with the new API-019 before a tx_count is taken. The window is checked after defaults, so a :valid-to in the past without a :valid-from fails too. Every write path checks it: execute, each WriteTransaction::execute statement, WriteTransaction::commit (again with the commit time, since a default valid_from moves to it), the browser write path and FactStorage::transact*. When several statements of one WriteTransaction write the same (e, a, v), in any mix of transact and retract, commit now keeps only the records of the last of them. Reads inside the transaction already followed statement order, but the commit stamped one tx_count on every record and a retraction always won, so retract-then-reassert read as live before commit and was gone after it. Two windows in separate statements, formerly API-011, now commit the later window. API-011 is limited to one transact and is raised by tx.execute, which stages nothing and leaves the transaction usable. LogWriter no longer collapses or rejects records of one transaction (the API-011 check is gone), so an unfiltered copy is identical to its source, including old transactions that hold several records of one fact. Writes that succeed today can fail, so this ships in v3.0.0. Design: docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md Refs #436, #477, #383 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 8 +- CLAUDE.md | 2 +- README.md | 2 +- ROADMAP.md | 4 +- docs/ERROR_REFERENCE.md | 35 +++- docs/TEST_COVERAGE.md | 4 +- src/browser/mod.rs | 7 +- src/db.rs | 112 +++++++++- src/error.rs | 11 +- src/graph/storage.rs | 74 +++++++ src/log_writer.rs | 25 +-- src/query/datalog/executor.rs | 4 +- tests/log_writer_test.rs | 56 ++++- tests/model_based_test.proptest-regressions | 7 + tests/model_based_test.rs | 189 +++++++++++------ tests/statement_order_test.rs | 218 ++++++++++++++++++++ tests/valid_time_window_test.rs | 88 +++++++- 17 files changed, 724 insertions(+), 122 deletions(-) create mode 100644 tests/model_based_test.proptest-regressions create mode 100644 tests/statement_order_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 454e685763..fd1faf08b3 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -16,13 +16,15 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **A damaged page is reported, not worked around** (v8 storage format, PR 5 of 5). A query whose indexed lookup reaches a damaged page now fails with that page's `STG-029`/`STG-030`/`STG-031`. Before, the query fell back to a full scan, which could hide the damage. Tests damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every read or checkpoint that reaches the page fails, and the file still opens at its last checkpoint. Measured at 1.15M facts in #433's shape: 142 bytes per fact, history included. A checkpoint after one new fact takes 6.1 ms at 1M facts. Concurrent point queries are 19–31 % faster than before this change: reads reuse the entity and attribute the caller passed, and share cached ident and timestamp lookups. - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit. - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed. -- **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one transaction (one `transact`, or several `execute` calls in one `WriteTransaction`) is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both. +- **Empty or inverted valid-time windows are rejected** (#436). A `transact` whose effective window for any fact ends at or before it starts fails with the new `API-019`, writes nothing and takes no transaction number. The effective window is the one after defaults, so `(transact {:valid-to "2020-01-01"} ...)` is rejected too: its `:valid-from` is the transaction time. This applies to `execute`, each `WriteTransaction::execute` statement and, with the commit time, `WriteTransaction::commit`, and the browser. Before, such a fact was stored, never matched `:valid-at`, and still showed up under `:any-valid-time`. Files that already hold such facts open and read as before. +- **In a `WriteTransaction`, the last statement that writes a fact decides it** (#477). When several `execute` calls in one `WriteTransaction` write the same `(entity, attribute, value)`, in any mix of `transact` and `retract`, the commit keeps only the records from the last of them. Before, reads inside the transaction already followed statement order, but the commit stamped every record with one transaction number and a retraction always won: a fact retracted and then asserted again read as live before `commit()` and was gone after it. Two windows of one fact in separate statements, which were `API-011`, now commit the later window. `API-011` is limited to one `transact`; `tx.execute()` raises it and stages nothing, and the transaction stays usable. +- **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one `transact` is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both. ### Added - **Binding support for cursors, open options, the fact log and the log writer** (#462, #465, #467). Two new codes let language bindings report what Rust's types rule out: `API-017` (an argument the binding cannot convert, such as an entity id that is not a UUID string), from `MinigrafError::invalid_argument`, and `API-018` (a log writer used after `finish` or `close`), from `MinigrafError::closed`. `BrowserDb.query(datalog)` returns a `BrowserCursor` with `vars()`, `nextBatch(maxRows)` (rows as JSON, as in `execute()`, or `undefined` at the end) and `close()`. The shared binding shape is in `docs/superpowers/specs/2026-10-07-binding-etl-surface-design.md`. The wasm32 test build compiles again (a duplicate `page_cache_capacity` and `tempfile` tests on wasm32). - **Fact log: `Minigraf::fact_log()`** (#430). Streams every fact version in the database as `FactRecord`s (entity, attribute, value, `tx_count`, `tx_id`, valid-time bounds, and whether it is an assertion or a retraction), without Datalog. `FactFilter` selects attributes (exact or by prefix), entities and a `tx_count` range, checked on index keys so excluded records are never decoded. `FactOrder::Tx` (the default) returns records in ascending `tx_count`; format v8 has no index in transaction order, so it holds at most `FactFilter::window` records (default 262,144) and scans the selected keys once per window. `FactOrder::Storage` reads in one pass. The log reads the database as it was when it opened; while one is open, checkpoints are deferred (writes stay in the WAL, automatic checkpoints wait, and `checkpoint()` or `rebuild_indexes()` with work to do fail with the new `API-013`). Close, drop or finish the log to release it. Like `Cursor`, a `FactLog` is owned and `Send`. Rust API only for now; the bindings follow. -- **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`), one valid-time window per fact per transaction (`API-011`) and size (`WAL-003`); a rejected record changes nothing. There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. +- **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`) and size (`WAL-003`); a rejected record changes nothing. Records are otherwise copied as they are, so an unfiltered copy is identical to its source, including transactions written before `API-011` or `API-019` that hold several records of one fact (#477). There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. - **Read-only open: `OpenOptions::read_only`** (#429). Opens a database so that nothing done through the handle writes to the `.graph` file or its WAL. The file is locked in shared mode: any number of read-only handles, in this process or others, can hold it at once, and they exclude a read-write open (and it excludes them) with the existing STG-025/STG-026. The handle shows the same data as a read-write open: a WAL left by an earlier session is applied in memory but not checkpointed or deleted, and a format v7 file is read into memory instead of migrated. A missing file is the new `STG-042` (nothing is created). `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` fail with the new `API-014`; queries, cursors, `fact_log`, `verify` and rule registration work, and dropping the handle does not checkpoint. `page_cache_size` applies as usual, so a tool can keep the whole file resident. Rust API only for now; the bindings follow. - **Cursor API: `Minigraf::query()` and `PreparedQuery::query()`** (#432). Both return a `Cursor` that hands a query's rows back in batches: `vars()`, `next_batch(max_rows) -> Result, _>`, `close()`, and an iterator over rows. The answer is fixed when the cursor opens, so writes that commit while it is open do not change it. A cursor borrows nothing from the database handle: it can outlive it and move to another thread. For now the answer is still computed when the cursor opens, under the same limits as `execute()`; the API is shaped so the engine can later produce rows as they are pulled without breaking callers. `query()` rejects `transact`, `retract` and `rule` with the new `API-012`, and a query with bind slots with `API-010`. `execute()` is unchanged. Rust API only for now; the bindings follow. - **`Minigraf::verify()` and `Minigraf::rebuild_indexes()`** (#373). Page checksums turn a torn or rotted page into an error, but they cannot see a page that is valid and says the wrong thing. `verify()` walks every committed page and returns an `IntegrityReport` with one structured error per finding: an index that holds different facts than EAVT or a different count than the meta page (new `STG-038`), keys out of order or a page reached twice (new `STG-039`), dictionary maps that disagree (new `STG-040`), ids with no dictionary entry (`STG-036`), and leaked, doubly used or wrongly free pages (`STG-035`). It keeps no per-fact state: indexes are compared by an order-independent digest. `rebuild_indexes()` rebuilds EAVT, AEVT, AVET and VAET from an intact index that agrees with another one (or the only intact one), derives the free list again, and commits like a checkpoint, including uncheckpointed writes; a crash at any point leaves the previous checkpoint. If no index can serve as the source, or the dictionary is damaged, it fails with new `STG-041` and writes nothing. Both are Rust API only for now; the bindings follow. @@ -44,7 +46,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Tests - **Golden-file compatibility corpus (#391).** `tests/golden/` holds v7 files written by minigraf 2.0.3, each with a JSON manifest of its CRC32, `tx_count` and expected query results. They cover one checkpoint, several checkpoints, indexes rebuilt on open, a WAL left by a crash, a WAL whose entries were already checkpointed, and same-transaction multi-values (#371). `tests/golden_corpus_test.rs` opens a copy of each file and checks its manifest after open, after a checkpoint and reopen, and after one more write. Golden files are never regenerated, only added; a new `golden-corpus` job in `policy.yml` fails a pull request that changes one. The generator is a standalone crate pinned to `minigraf = "=2.0.3"` (`tests/golden/gen/v7/`). On `v3`, each v7 file must also carry a v8 meta page after its first open, and seven v8 files are frozen alongside them, written by the `v3` branch at `23aa57c` (`tests/golden/gen/v8/`): one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values (a 4,068-byte string stored twice, the 64/65-byte inline boundary, a 1,000-byte attribute and keyword). All #371 queries now pass. -- **Model-based storage test (#385).** `tests/model_based_test.rs` runs random sequences of `transact` (multi-valued batches, transaction- and fact-level valid-time windows, a triple repeated with another window), `retract`, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, a 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the `.graph` file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, `current_tx_count`, `verify`, full rows with windows and tx counts, and entity-, entity+attribute-, attribute-, attribute+value-, value-bound and full-scan queries, under `:as-of N` and `:valid-at T`, must match a plain reference model (one valid-time window per triple, #435; API-011 for two windows of one triple in one transaction). Normal CI runs 24 cases; the nightly property-test workflow runs 30,000. +- **Model-based storage test (#385).** `tests/model_based_test.rs` runs random sequences of `transact` (multi-valued batches, transaction- and fact-level valid-time windows, a triple repeated with another window), `retract`, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, a 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the `.graph` file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, `current_tx_count`, `verify`, full rows with windows and tx counts, and entity-, entity+attribute-, attribute-, attribute+value-, value-bound and full-scan queries, under `:as-of N` and `:valid-at T`, must match a plain reference model (one valid-time window per triple, #435; API-011 for two windows of one triple in one statement and API-019 for an empty or inverted window, from `execute` and `tx.execute`, #436; the last statement that writes a triple decides it at commit, #477). Reads inside a write transaction are checked against what its commit will hold. Normal CI runs 24 cases; the nightly property-test workflow runs 30,000. ## v2.0.3 — 2026-10-06 diff --git a/CLAUDE.md b/CLAUDE.md index f71b56dbb1..c25e1b717a 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 -**1348 tests** (1339 passing, 9 ignored; unit + integration + doc). +**1360 tests** (1351 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 51fe798882..35df1b2d89 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 1348 tests +cargo test # run 1360 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 3210a498a7..44a3c7d927 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -62,7 +62,9 @@ Scope — format and storage integrity: The format is frozen for the golden-file corpus (#391). - Index `verify` and public `rebuild_indexes()` (#373; done on `v3`) - Net-assert on v8 keys before resolving facts, for O(live) point queries (#379; done on `v3`) -- One current valid-time window per `(e, a, v)`: a later assertion replaces the earlier window, and two windows of one fact in one transaction are `API-011` (#435; done on `v3`) +- One current valid-time window per `(e, a, v)`: a later assertion replaces the earlier window, and two windows of one fact in one `transact` are `API-011` (#435; done on `v3`) +- Empty or inverted valid-time windows rejected with `API-019` on every write path (#436; done on `v3`) +- In a `WriteTransaction`, the last statement that writes a fact decides it, so reads inside the transaction match the commit; `LogWriter` copies records verbatim (#477; done on `v3`) - `btree_page` fuzz target that reaches node decoding (#375) Scope — query API: diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 5d2d64e71b..4251e931a4 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -168,7 +168,7 @@ with no `CodedError` anywhere in its chain. | API-008 | Function registry lock poisoned | Database API | | API-009 | WAL not initialized | Database API | | API-010 | Query with bind slots passed to execute() | Database API | -| API-011 | Two valid-time windows for one fact in one transaction | Database API | +| API-011 | Two valid-time windows for one fact in one transact | Database API | | API-012 | Non-query command passed to query() | Database API | | API-013 | Checkpoint while a fact log is open | Database API | | API-014 | Write on a read-only handle | Database API | @@ -176,6 +176,7 @@ with no `CodedError` anywhere in its chain. | API-016 | Log writer record with a second tx_id for one transaction | Database API | | API-017 | Invalid argument passed through a language binding | Database API | | API-018 | Call on a closed binding object | Database API | +| API-019 | Empty or inverted valid-time window | Database API | | INT-000 | Unclassified internal error | Internal | | INT-001 | WriteTransaction already in progress on this thread | Internal | | INT-002 | Invalid entity (API layer) | Internal | @@ -2476,11 +2477,11 @@ let result = pq.execute(&[ **Scenario**: A query copied from the prepared-query docs is pasted into the REPL or passed to `db.execute()` unchanged. -### API-011 Two valid-time windows for one fact in one transaction +### API-011 Two valid-time windows for one fact in one transact -**Error text**: `one transaction asserts the same value of {} with two valid-time windows; assert it once with its final window` +**Error text**: `one (transact ...) asserts the same value of {} with two valid-time windows; assert it once with its final window` -**Cause**: One transaction asserts the same entity, attribute and value twice with different `:valid-from`/`:valid-to` bounds. At any transaction time a fact has exactly one current valid-time window, and the window of the latest transaction applies. Two windows in the same transaction leave no latest one, so the transaction is rejected and nothing is written. The `{}` is the attribute. This can come from one `(transact ...)` with per-fact bounds, from several `execute()` calls inside one `WriteTransaction`, or from `LogWriter::append` records of one transaction (that record alone is rejected). +**Cause**: One `(transact ...)` asserts the same entity, attribute and value twice with different `:valid-from`/`:valid-to` bounds. At any transaction time a fact has exactly one current valid-time window. Within one statement neither window comes later, so the statement is rejected and nothing is written. The `{}` is the attribute. Identical repeats are allowed and stored once. Inside a `WriteTransaction`, `tx.execute()` rejects the statement and stages nothing; the transaction stays usable. Across several statements of one `WriteTransaction` there is no error: the last statement that writes a fact decides it (#477). `LogWriter::append` copies records as they are and never returns this code. **Resolution**: - Assert the fact once per transaction, with the window it should have. @@ -2488,7 +2489,7 @@ let result = pq.execute(&[ - A fact that was true over two separate periods cannot have both windows live at once. Model each period as its own entity (for example an `:employment` entity with `:employment/salary`), or keep the latest period current and read earlier ones with `:as-of`. ```clojure -;; Rejected: two windows for [:alice :salary 100000] in one transaction +;; Rejected: two windows for [:alice :salary 100000] in one transact (transact [[:alice :salary 100000 {:valid-from "2020-01-01" :valid-to "2022-01-01"}] [:alice :salary 100000 {:valid-from "2024-01-01"}]]) @@ -2604,6 +2605,30 @@ let mut log = src.fact_log(&FactFilter::new())?; **Scenario**: A loader calls `finish()` in a `finally` block after it already called it on success. +### API-019 Empty or inverted valid-time window + +**Error text**: `the valid-time window of {} ends at or before it starts; :valid-to must be later than :valid-from (the transaction time when :valid-from is omitted)` + +**Cause**: A `transact` gives a fact a valid-time window whose end is at or before its start, so the fact could never match a `:valid-at` query. The check uses the effective window, after defaults: the fact's own bound, else the transaction's, else `:valid-from` is the transaction time and `:valid-to` is forever. A `:valid-to` in the past with no `:valid-from` is therefore rejected too. The whole transaction is rejected, nothing is written and no transaction number is used. The `{}` is the attribute. Inside a `WriteTransaction`, `tx.execute()` checks each statement. `commit()` checks again with the commit time, so a `:valid-to` that passed while staging can still fail at commit. Files written before this check, and records copied by `LogWriter`, are read as they are. + +**Resolution**: +- Give `:valid-to` a later instant than `:valid-from`. +- To record a fact that is no longer true, give it a `:valid-from` before its `:valid-to`, or `retract` it. +- Check that a per-fact `:valid-from`/`:valid-to` does not invert the transaction-level window it overrides. + +```clojure +;; Rejected: ends before it starts, and an empty window +(transact {:valid-from "2026-08-21" :valid-to "2026-08-20"} [[:d/c :description "r"]]) +(transact {:valid-from "2026-08-21" :valid-to "2026-08-21"} [[:d/c :description "r"]]) +;; Rejected: valid-from defaults to now, which is after valid-to +(transact {:valid-to "2020-01-01"} [[:d/c :description "r"]]) + +;; Accepted +(transact {:valid-from "2019-01-01" :valid-to "2020-01-01"} [[:d/c :description "r"]]) +``` + +**Scenario**: An import sets `:valid-to` from a source's end date but leaves out `:valid-from`, so past end dates produce windows that end before the transaction time. + --- ## INT — Internal Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index ceee17ed3d..9fafc11d76 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-07 with `cargo test --quiet` -**Result**: 1,339 passing tests and 9 ignored tests (1,348 total) +**Result**: 1,351 passing tests and 9 ignored tests (1,360 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). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `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 copies a source whose transactions hold two windows of a fact, an assertion and a retraction of one fact, and an inverted window, and checks the copy holds every record and answers like the source at every `:as-of`. 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`, and oversize values or idents `WAL-003` (a second window or a retraction of a fact in one transaction is kept, #477), each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. ### Covered Areas diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 216bbd3ffe..6353c3cd1d 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -322,11 +322,14 @@ impl BrowserDb { let (flush, result_json) = { let mut inner = self.inner.borrow_mut(); - // Before allocating: a rejected transaction takes no tx_count (#435). + // Before allocating: a rejected transaction takes no tx_count + // (#435, #436). + let tx_id = tx_id_now(); + crate::graph::storage::check_valid_windows(&facts, tx_id) + .map_err(|e| JsValue::from_str(&e.to_string()))?; crate::graph::storage::check_one_window_per_triple(&facts) .map_err(|e| JsValue::from_str(&e.to_string()))?; let tx_count = inner.fact_storage.allocate_tx_count(); - let tx_id = tx_id_now(); let stamped: Vec = facts .into_iter() diff --git a/src/db.rs b/src/db.rs index a174aac775..4e0ccdaf1d 100644 --- a/src/db.rs +++ b/src/db.rs @@ -690,10 +690,10 @@ impl Minigraf { _ => return Err(err_coded!(ErrorCode::Api002)), }; // Before allocating: a rejected transaction takes no tx_count. + let tx_id = crate::graph::types::tx_id_now(); + crate::graph::storage::check_valid_windows(&stamped, tx_id)?; crate::graph::storage::check_one_window_per_triple(&stamped)?; - let tx_count = self.inner.fact_storage.allocate_tx_count(); - let tx_id = crate::graph::types::tx_id_now(); let stamped: Vec = stamped .into_iter() @@ -1388,7 +1388,14 @@ impl<'a> WriteTransaction<'a> { match cmd { DatalogCommand::Transact(tx) => { - self.stage_pending_facts(Minigraf::materialize_transaction(&tx)?); + // A rejected statement stages nothing; the transaction stays + // usable. `commit` checks windows again at the commit time. + let facts = Minigraf::materialize_transaction(&tx)?; + let staged_tx_id = + std::cmp::max(crate::graph::types::tx_id_now(), self.next_pending_tx_id); + crate::graph::storage::check_valid_windows(&facts, staged_tx_id)?; + crate::graph::storage::check_one_window_per_triple(&facts)?; + self.stage_pending_facts(facts); Ok(QueryResult::Ok) } DatalogCommand::Retract(tx) => { @@ -1480,12 +1487,17 @@ impl<'a> WriteTransaction<'a> { let facts_to_commit = std::mem::take(&mut self.pending_facts); if !facts_to_commit.is_empty() { + // One tx_id cannot tell several versions of a fact apart, so the + // last statement that wrote a triple decides it, as reads inside + // the transaction already see (#477). Each statement passed + // API-011 when staged, so every triple left has one window. + let facts_to_commit = keep_last_statement(facts_to_commit); // Before allocating: a rejected transaction takes no tx_count. - // Unresolved `valid_from`s all equal `VALID_FROM_USE_TX_TIME`, so - // they compare as they will after stamping. - crate::graph::storage::check_one_window_per_triple(&facts_to_commit)?; - let tx_count = self.inner.fact_storage.allocate_tx_count(); + // A default `valid_from` becomes the commit time, so the windows + // are checked again here (#436). let tx_id = crate::graph::types::tx_id_now(); + crate::graph::storage::check_valid_windows(&facts_to_commit, tx_id)?; + let tx_count = self.inner.fact_storage.allocate_tx_count(); // Stamp facts with tx_id and tx_count let stamped: Vec = facts_to_commit @@ -1612,6 +1624,36 @@ impl<'a> WriteTransaction<'a> { } } +/// Keep, for each `(entity, attribute, value)`, only the staged records of +/// the newest statement that wrote it (#477). Staged facts carry their +/// statement's synthetic `tx_count`; the order of what is kept is unchanged. +fn keep_last_statement(facts: Vec) -> Vec { + use crate::storage::index::encode_value; + use std::collections::HashMap; + + let encoded: Vec> = facts.iter().map(|f| encode_value(&f.value)).collect(); + let mut newest: HashMap<(&crate::graph::types::EntityId, &str, &[u8]), u64> = HashMap::new(); + for (fact, value) in facts.iter().zip(&encoded) { + let slot = newest + .entry((&fact.entity, fact.attribute.as_str(), value.as_slice())) + .or_insert(fact.tx_count); + *slot = (*slot).max(fact.tx_count); + } + let keep: Vec = facts + .iter() + .zip(&encoded) + .map(|(fact, value)| { + newest.get(&(&fact.entity, fact.attribute.as_str(), value.as_slice())) + == Some(&fact.tx_count) + }) + .collect(); + facts + .into_iter() + .zip(keep) + .filter_map(|(fact, kept)| kept.then_some(fact)) + .collect() +} + impl Drop for WriteTransaction<'_> { fn drop(&mut self) { if !self.committed { @@ -1720,6 +1762,62 @@ mod tests { assert_eq!(facts.len(), 0, "dropped transaction must act as rollback"); } + // ── same triple in several statements (#477) ───────────────────────────── + + #[test] + fn keep_last_statement_drops_earlier_records_of_a_triple() { + let e = uuid::Uuid::from_u128(1); + let staged = |v: i64, tx_count: u64, asserted: bool| { + let mut f = if asserted { + Fact::new(e, ":a".to_string(), Value::Integer(v), 0) + } else { + Fact::retract(e, ":a".to_string(), Value::Integer(v), 0) + }; + f.tx_count = tx_count; + f + }; + let kept = keep_last_statement(vec![ + staged(1, 10, true), + staged(2, 10, true), + staged(1, 11, false), + staged(3, 11, false), + staged(3, 12, true), + staged(3, 12, true), + ]); + let got: Vec<(i64, u64, bool)> = kept + .iter() + .map(|f| match f.value { + Value::Integer(v) => (v, f.tx_count, f.asserted), + _ => (0, 0, false), + }) + .collect(); + assert_eq!( + got, + vec![(2, 10, true), (1, 11, false), (3, 12, true), (3, 12, true)], + "each triple keeps its newest statement, in order" + ); + } + + /// A default `valid_from` becomes the commit time, so a `valid_to` that + /// was still ahead when staged but is behind at commit is API-019 (#436). + #[test] + fn commit_rejects_window_that_ended_before_commit_time() { + let db = Minigraf::in_memory().unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:alice :person/age 30]])"#) + .unwrap(); + let soon = crate::graph::types::tx_id_now().saturating_add(20); + for f in &mut tx.pending_facts { + f.valid_to = soon.cast_signed(); + } + while crate::graph::types::tx_id_now() <= soon { + std::thread::yield_now(); + } + let err = tx.commit().expect_err("window ends before the commit time"); + assert_eq!(err.code(), "API-019"); + assert_eq!(db.current_tx_count(), 0, "no tx_count taken"); + } + // ── read-your-own-writes ────────────────────────────────────────────────── #[test] diff --git a/src/error.rs b/src/error.rs index d82afed4e8..3a19ea0599 100644 --- a/src/error.rs +++ b/src/error.rs @@ -208,6 +208,7 @@ pub(crate) enum ErrorCode { Api016, Api017, Api018, + Api019, Int001, Int002, Int003, @@ -1162,7 +1163,7 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ ( ErrorCode::Api011, "API-011", - "one transaction asserts the same value of {} with two valid-time windows; assert it once with its final window", + "one (transact ...) asserts the same value of {} with two valid-time windows; assert it once with its final window", ErrorCategory::Api, ), ( @@ -1207,6 +1208,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "{} is closed", ErrorCategory::Api, ), + ( + ErrorCode::Api019, + "API-019", + "the valid-time window of {} ends at or before it starts; :valid-to must be later than :valid-from (the transaction time when :valid-from is omitted)", + ErrorCategory::Api, + ), ( ErrorCode::Int001, "INT-001", @@ -1985,6 +1992,7 @@ mod tests { | ErrorCode::Api016 | ErrorCode::Api017 | ErrorCode::Api018 + | ErrorCode::Api019 | ErrorCode::Int001 | ErrorCode::Int002 | ErrorCode::Int003 @@ -2201,6 +2209,7 @@ mod tests { ErrorCode::Api016, ErrorCode::Api017, ErrorCode::Api018, + ErrorCode::Api019, ErrorCode::Int001, ErrorCode::Int002, ErrorCode::Int003, diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 2f7ac46a8c..5c9b21af15 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -155,6 +155,7 @@ impl FactStorage { }) .collect(); // Before allocating: a rejected transaction takes no tx_count. + check_valid_windows(&facts, tx_id)?; check_one_window_per_triple(&facts)?; let tx_count = self .tx_counter @@ -212,6 +213,7 @@ impl FactStorage { }) .collect(); // Before allocating: a rejected transaction takes no tx_count. + check_valid_windows(&facts, tx_id)?; check_one_window_per_triple(&facts)?; let tx_count = self .tx_counter @@ -622,6 +624,25 @@ pub(crate) fn check_one_window_per_triple(facts: &[Fact]) -> Result<()> { Ok(()) } +/// Reject a transaction's facts if an assertion's valid-time window ends at or +/// before it starts (API-019, #436). A `valid_from` still holding +/// `VALID_FROM_USE_TX_TIME` is checked as `tx_id`, the transaction time it +/// will be stamped with. Run before anything is written. +pub(crate) fn check_valid_windows(facts: &[Fact], tx_id: TxId) -> Result<()> { + let tx_time = i64::try_from(tx_id).unwrap_or(i64::MAX); + for fact in facts.iter().filter(|f| f.asserted) { + let valid_from = if fact.valid_from == crate::db::VALID_FROM_USE_TX_TIME { + tx_time + } else { + fact.valid_from + }; + if fact.valid_to <= valid_from { + bail_coded!(ErrorCode::Api019, fact.attribute); + } + } + Ok(()) +} + /// The pending fact at `pos`, as indexed by `FactData::pending_indexes`. fn pending_fact(d: &FactData, pos: usize) -> Result { d.facts @@ -1827,6 +1848,59 @@ mod tests { assert_eq!(crate::error::MinigrafError::from(err).code(), "API-011"); } + #[test] + fn check_valid_windows_rejects_empty_and_inverted_windows() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let window = |vf: i64, vt: i64| make_assert(entity, ":a", value.clone(), 1, vf, vt); + let code = |r: Result<()>| crate::error::MinigrafError::from(r.unwrap_err()).code(); + let tx_time = crate::db::VALID_FROM_USE_TX_TIME; + + check_valid_windows(&[window(1_000, 2_000)], 5_000).expect("past window"); + check_valid_windows(&[window(1_000, VALID_TIME_FOREVER)], 5_000).expect("forever"); + check_valid_windows(&[window(tx_time, 5_001)], 5_000).expect("tx time to later"); + check_valid_windows(&[window(tx_time, VALID_TIME_FOREVER)], 5_000).expect("default"); + let mut retraction = make_retract(entity, ":a", value.clone(), 1); + retraction.valid_from = 9_000; + retraction.valid_to = 1_000; + check_valid_windows(&[retraction], 5_000).expect("retractions are not checked"); + + assert_eq!( + code(check_valid_windows(&[window(2_000, 1_000)], 5_000)), + "API-019" + ); + assert_eq!( + code(check_valid_windows(&[window(2_000, 2_000)], 5_000)), + "API-019" + ); + assert_eq!( + code(check_valid_windows(&[window(tx_time, 5_000)], 5_000)), + "API-019" + ); + assert_eq!( + code(check_valid_windows(&[window(tx_time, 1_000)], 5_000)), + "API-019" + ); + assert_eq!( + code(check_valid_windows(&[window(0, 9), window(9, 9)], 5_000)), + "API-019", + "any fact of the batch" + ); + } + + #[test] + fn transact_batch_rejects_inverted_window_without_taking_a_tx() { + let storage = FactStorage::new(); + let entity = uuid::Uuid::new_v4(); + let opts = TransactOptions::new(Some(2_000), Some(1_000)); + let err = storage.transact_batch( + vec![(entity, ":a".to_string(), Value::Integer(1), Some(opts))], + None, + ); + assert!(err.is_err(), "inverted window rejected"); + assert_eq!(storage.current_tx_count(), 0, "no tx_count taken"); + } + #[test] fn transact_batch_rejects_two_windows_without_taking_a_tx() { let storage = FactStorage::new(); diff --git a/src/log_writer.rs b/src/log_writer.rs index c00bcad3b2..5b92a6c8f3 100644 --- a/src/log_writer.rs +++ b/src/log_writer.rs @@ -14,13 +14,11 @@ use crate::db::OpenOptions; use crate::error::{ErrorCode, MinigrafError, bail_coded, err_coded}; use crate::fact_log::FactRecord; -use crate::graph::types::{EntityId, Fact}; +use crate::graph::types::Fact; use crate::storage::backend::file::{FileBackend, LockMode}; use crate::storage::dir_sync::sync_parent_dir; -use crate::storage::index::encode_value; use crate::storage::persistent_facts::PersistentFactStorage; use anyhow::Result; -use std::collections::HashMap; use std::ffi::OsString; use std::path::{Path, PathBuf}; @@ -62,8 +60,6 @@ pub struct LogWriter { tx_count: u64, /// The open transaction's `(tx_count, tx_id)`, if a record can join it. open_tx: Option<(u64, u64)>, - /// The open transaction's valid-time window per asserted `(e, a, v)`. - windows: HashMap<(EntityId, String, Vec), (i64, i64)>, /// Facts loaded since the last batch commit. pending: usize, } @@ -106,7 +102,6 @@ impl LogWriter { partial, tx_count: 0, open_tx: None, - windows: HashMap::new(), pending: 0, }) } @@ -132,8 +127,6 @@ impl LogWriter { /// - `API-015` if `tx_count` is 0, below the writer's, or names a /// transaction that is already closed. /// - `API-016` if it joins the open transaction with a different `tx_id`. - /// - `API-011` if it asserts an `(entity, attribute, value)` the open - /// transaction already asserts with another valid-time window. /// - `WAL-003` if the attribute, a keyword or a string value is longer /// than the format stores. /// @@ -165,15 +158,9 @@ impl LogWriter { asserted: rec.asserted, }; crate::wal::check_fact_size(&fact)?; - let key = ( - fact.entity, - fact.attribute.clone(), - encode_value(&fact.value), - ); - let window = (fact.valid_from, fact.valid_to); - if fact.asserted && joins && self.windows.get(&key).is_some_and(|w| *w != window) { - bail_coded!(ErrorCode::Api011, fact.attribute); - } + // Records are copied as they are (#477): one transaction may hold + // several records of a triple, as a source written before API-011 or + // API-019 can. Readers resolve them the same way in source and target. if !joins { self.close_tx(); @@ -183,9 +170,6 @@ impl LogWriter { self.tx_count = rec.tx_count; self.open_tx = Some((rec.tx_count, rec.tx_id)); } - if fact.asserted { - self.windows.insert(key, window); - } let pfs = self.pfs_mut()?; if pfs.storage().load_fact(fact)? { pfs.mark_dirty(); @@ -255,7 +239,6 @@ impl LogWriter { fn close_tx(&mut self) { self.open_tx = None; - self.windows.clear(); } /// Commit the pending records as the next generation of the file. diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index cf0cfa1aba..52201341c8 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -5376,7 +5376,7 @@ mod expr_eval_tests { let storage = FactStorage::new(); let executor = DatalogExecutor::new(storage); let cmd = parse_datalog_command( - r#"(transact {:valid-to "2025-01-01T00:00:00Z"} [[:alice :person/name "Alice"]])"#, + r#"(transact {:valid-to "2125-01-01T00:00:00Z"} [[:alice :person/name "Alice"]])"#, ) .expect("parse with tx-level valid-to only should succeed"); let result = executor.execute(cmd); @@ -5393,7 +5393,7 @@ mod expr_eval_tests { let storage = FactStorage::new(); let executor = DatalogExecutor::new(storage); let cmd = parse_datalog_command( - r#"(transact [[:alice :person/name "Alice" {:valid-to "2025-01-01T00:00:00Z"}]])"#, + r#"(transact [[:alice :person/name "Alice" {:valid-to "2125-01-01T00:00:00Z"}]])"#, ) .expect("parse with per-fact valid-to only should succeed"); let result = executor.execute(cmd); diff --git a/tests/log_writer_test.rs b/tests/log_writer_test.rs index 58b8abc3df..a5c3684231 100644 --- a/tests/log_writer_test.rs +++ b/tests/log_writer_test.rs @@ -378,10 +378,11 @@ fn rejected_records_change_nothing() { "two tx_ids" ); + // Records are copied as they are (#477): a second window and a + // retraction of the same triple in one transaction are kept. let mut other_window = rec(3, 300, ":a/x", 1); other_window.valid_to = 400; - assert_eq!(code(w.append(&other_window)), "API-011", "two windows"); - // A retraction with another window is a different record, not a conflict. + w.append(&other_window).unwrap(); let mut retraction = other_window.clone(); retraction.asserted = false; w.append(&retraction).unwrap(); @@ -414,6 +415,7 @@ fn rejected_records_change_nothing() { got.sort(); let want = vec![ "3 300 e1 :a/x Integer(1) 300 400 false".to_string(), + "3 300 e1 :a/x Integer(1) 300 400 true".to_string(), "3 300 e1 :a/x Integer(1) 300 9223372036854775807 true".to_string(), "3 300 e1 :a/y Integer(9) 300 9223372036854775807 true".to_string(), "4 250 e1 :a/x Integer(6) 250 9223372036854775807 true".to_string(), @@ -422,6 +424,56 @@ fn rejected_records_change_nothing() { assert!(db.verify().unwrap().is_ok(), "verify is clean"); } +/// A source whose transactions hold several records of one triple, as files +/// written before API-011 and API-019 can (two windows, an assertion and a +/// retraction, an inverted window), is copied record for record, and the +/// copy answers like the source (#477). +#[test] +fn mixed_transactions_are_copied_verbatim() { + let dir = Dir::new(); + let src_path = dir.path("src.graph"); + let mut w = LogWriter::create(&src_path, OpenOptions::new()).unwrap(); + let mut records_in = vec![ + rec(1, 100, ":a/x", 1), + rec(2, 200, ":a/x", 1), + rec(2, 200, ":a/y", 2), + rec(3, 300, ":a/z", 3), + ]; + records_in[1].valid_to = 250; // two windows of :a/x 1 in tx 2 + let mut second = rec(2, 200, ":a/x", 1); + second.valid_from = 50; + second.valid_to = 150; + records_in.insert(2, second); + let mut retracted = rec(2, 200, ":a/y", 2); + retracted.asserted = false; // :a/y 2 asserted and retracted in tx 2 + records_in.push(retracted); + let mut inverted = rec(3, 300, ":a/w", 4); + inverted.valid_to = 200; // ends before it starts + records_in.push(inverted); + records_in.sort_by_key(|r| r.tx_count); + for r in &records_in { + w.append(r).unwrap(); + } + w.finish().unwrap(); + + let src = Minigraf::open(&src_path).unwrap(); + let mut want: Vec = records_in.iter().map(row).collect(); + want.sort(); + assert_eq!(log_rows(&src), want, "source holds every record"); + + let out = dir.path("out.graph"); + copy(&src, &out, |_| true); + let dst = Minigraf::open(&out).unwrap(); + same_answers(&src, &dst); + for n in 0..=src.current_tx_count() { + let q = format!( + "(query [:find ?a ?v ?vf ?vt :as-of {n} :any-valid-time :where [?e ?a ?v] [?e :db/valid-from ?vf] [?e :db/valid-to ?vt]])" + ); + assert_eq!(rows(&src, &q), rows(&dst, &q), "{q}"); + } + assert!(dst.verify().unwrap().is_ok(), "verify is clean"); +} + #[test] fn create_refuses_existing_targets_and_read_only() { let dir = Dir::new(); diff --git a/tests/model_based_test.proptest-regressions b/tests/model_based_test.proptest-regressions new file mode 100644 index 0000000000..f0818d1258 --- /dev/null +++ b/tests/model_based_test.proptest-regressions @@ -0,0 +1,7 @@ +# Seeds for failure cases proptest has generated in the past. It is +# automatically read and these particular cases re-run before any +# novel cases are generated. +# +# It is recommended to check this file in to source control so that +# everyone who runs the test benefits from these saved cases. +cc ae0b4b21bae878a9b766b323137bb385a1736529adf2fa100ca840d3f378eaa3 # shrinks to steps = [Step { op: WriteTx { stmts: [Retract { facts: [(0, 0, Int(0))] }, Transact { window: Window { vf: None, vt: None }, facts: [FactSpec { e: 0, a: 0, v: Int(0), window: Window { vf: None, vt: None } }] }], commit: true }, probe: Probe { as_of: 0, at: 0, e: 0, a: 0, v: Int(0) } }] diff --git a/tests/model_based_test.rs b/tests/model_based_test.rs index f361bd6025..b8af0c4284 100644 --- a/tests/model_based_test.rs +++ b/tests/model_based_test.rs @@ -307,8 +307,9 @@ 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)| { + .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 }) @@ -320,9 +321,10 @@ fn arb_transact() -> impl Strategy { again.window = w; facts.push(again); } - // An empty or inverted window (#436) is rewritten to start in 2000; - // every `:valid-to` on the grid is later. - for f in &mut facts { + // 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); } @@ -350,7 +352,7 @@ fn arb_op() -> impl Strategy { ) .prop_map(|(mut stmts, retract_own, commit)| { // Retract a triple this transaction asserts, before or after - // the assertion: the retraction wins either way. + // the assertion: the later statement wins (#477). let own = stmts.iter().find_map(|s| match s { Stmt::Transact { facts, .. } => Some(facts[0].clone()), Stmt::Retract { .. } => None, @@ -428,62 +430,84 @@ struct Model { } impl Model { - /// The records a committed transaction of `stmts` would add, or `None` - /// when the transaction is rejected with API-011 (one triple, two windows). - fn records(stmts: &[Stmt], tx: u64) -> Option> { - let mut out = Vec::new(); - for stmt in stmts { + /// 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(Record { - tx, - e: f.e, - a: f.a, - v: f.v.clone(), - window: effective(*window, f.window), - asserted: true, - }); + 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(Record { - tx, - e: *e, - a: *a, - v: v.clone(), - window: (None, FOREVER), - asserted: false, - }); + out.push(( + n, + Record { + tx, + e: *e, + a: *a, + v: v.clone(), + window: (None, FOREVER), + asserted: false, + }, + )); } } } } - let asserted: Vec<&Record> = out.iter().filter(|r| r.asserted).collect(); - for (i, x) in asserted.iter().enumerate() { - for y in &asserted[i + 1..] { - if x.e == y.e && x.a == y.a && x.v == y.v && x.window != y.window { - return None; - } - } - } - Some(out) + 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. Returns false when it is rejected. - fn commit(&mut self, stmts: &[Stmt]) -> bool { + /// Apply a committed transaction of accepted statements. + fn commit(&mut self, stmts: &[Stmt]) { if stmts.is_empty() { - return true; - } - match Self::records(stmts, self.tx_count + 1) { - Some(records) => { - self.tx_count += 1; - self.log.extend(records); - true - } - None => false, + return; } + self.tx_count += 1; + self.log.extend(Self::records(stmts, self.tx_count)); } fn live(&self, as_of: Option) -> Vec { @@ -535,8 +559,15 @@ struct Ctx { impl Ctx { fn rows(&self, db: &Minigraf, query: &str) -> Result>, TestCaseError> { - let result = db - .execute(query) + 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 @@ -761,18 +792,18 @@ fn verify(db: &Minigraf, step: usize) -> Result<(), TestCaseError> { Ok(()) } -/// Expect `result` to match the model's verdict: Ok when accepted, API-011 -/// when rejected. +/// Expect `result` to match the model's verdict: Ok when `None`, else that +/// error code. fn expect_outcome( result: Result, - accepted: bool, + verdict: Option<&str>, step: usize, ) -> Result<(), TestCaseError> { - match (result, accepted) { - (Ok(_), true) => Ok(()), - (Err(e), false) if e.code() == "API-011" => Ok(()), - (Ok(_), false) => Err(TestCaseError::fail(format!( - "step {step}: accepted, model expects API-011" + match (result, verdict) { + (Ok(_), None) => Ok(()), + (Err(e), Some(code)) if e.code() == code => Ok(()), + (Ok(_), Some(code)) => Err(TestCaseError::fail(format!( + "step {step}: accepted, model expects {code}" ))), (Err(e), _) => Err(TestCaseError::fail(format!( "step {step}: unexpected error {}", @@ -781,6 +812,9 @@ fn expect_outcome( } } +/// The current `(e, a, v)` of every fact, any valid time. +const IN_TX_QUERY: &str = "(query [:find ?e ?a ?v :any-valid-time :where [?e ?a ?v]])"; + fn run(steps: &[Step]) -> Result<(), TestCaseError> { let dir = tempfile::tempdir().map_err(|_| TestCaseError::fail("tempdir"))?; let mut path = dir.path().join("model.graph"); @@ -797,8 +831,11 @@ fn run(steps: &[Step]) -> Result<(), TestCaseError> { .as_ref() .ok_or_else(|| TestCaseError::fail("no handle"))?; let result = handle.execute(&stmt.edn()); - let accepted = model.commit(std::slice::from_ref(stmt)); - expect_outcome(result, accepted, i)?; + let verdict = Model::verdict(stmt); + if verdict.is_none() { + model.commit(std::slice::from_ref(stmt)); + } + expect_outcome(result, verdict, i)?; } Op::WriteTx { stmts, commit } => { let handle = db @@ -807,14 +844,40 @@ fn run(steps: &[Step]) -> Result<(), TestCaseError> { let mut tx = handle .begin_write() .map_err(|e| TestCaseError::fail(format!("begin_write ({})", e.code())))?; + // A rejected statement stages nothing; the rest still commit. + let mut accepted = Vec::new(); for stmt in stmts { - tx.execute(&stmt.edn()).map_err(|e| { - TestCaseError::fail(format!("step {i}: staged write ({})", e.code())) - })?; + let verdict = Model::verdict(stmt); + expect_outcome(tx.execute(&stmt.edn()), verdict, i)?; + if verdict.is_none() { + accepted.push(stmt.clone()); + } } + // Reads inside the transaction see what the commit will hold. + let mut after = Model { + log: model.log.clone(), + tx_count: model.tx_count, + }; + after.commit(&accepted); + let got: Vec = ctx + .result_rows(tx.execute(IN_TX_QUERY), IN_TX_QUERY)? + .into_iter() + .map(|r| r.join(" ")) + .collect(); + let want: Vec = after + .live(None) + .iter() + .map(|l| format!("r{} {} {}", l.e, attr_render(l.a), l.v.render())) + .collect(); + prop_assert_eq!( + sorted(got), + sorted(want), + "step {}: reads inside the transaction", + i + ); if *commit { - let accepted = model.commit(stmts); - expect_outcome(tx.commit(), accepted, i)?; + model = after; + expect_outcome(tx.commit(), None, i)?; } else { tx.rollback(); } diff --git a/tests/statement_order_test.rs b/tests/statement_order_test.rs new file mode 100644 index 0000000000..76ca5dacd8 --- /dev/null +++ b/tests/statement_order_test.rs @@ -0,0 +1,218 @@ +//! Several writes to one `(e, a, v)` in one `WriteTransaction` (#477). +//! +//! The last statement that writes a triple decides it, in any mix of +//! `transact` and `retract`: reads inside the transaction and the committed +//! result agree. Each scenario runs in memory, file-backed with the commit +//! checkpointed, and file-backed after a reopen. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult, Value}; + +enum Mode { + Memory, + Checkpointed, + Reopened, +} + +const MODES: [Mode; 3] = [Mode::Memory, Mode::Checkpointed, Mode::Reopened]; + +/// `:tag` facts of `:d/c` as `value [valid-to)` rows, sorted, with the +/// current view first and the `:any-valid-time` view second. +type Rows = (Vec, Vec); + +const NOW: &str = r#"(query [:find ?v :where [:d/c :tag ?v]])"#; +const ANY: &str = + r#"(query [:find ?v ?vt :any-valid-time :where [?e :tag ?v] [?e :db/valid-to ?vt]])"#; + +fn render(v: &Value) -> String { + match v { + Value::String(s) => s.clone(), + Value::Integer(n) => n.to_string(), + _ => "other".to_string(), + } +} + +fn to_rows(result: QueryResult) -> Vec { + let QueryResult::QueryResults { results, .. } = result else { + panic!("expected query results"); + }; + let mut rows: Vec = results + .iter() + .map(|r| r.iter().map(render).collect::>().join(" ")) + .collect(); + rows.sort(); + rows +} + +fn read(db: &Minigraf) -> Rows { + ( + to_rows(db.execute(NOW).unwrap()), + to_rows(db.execute(ANY).unwrap()), + ) +} + +/// Run `setup` as separate transactions, then `stmts` in one +/// `WriteTransaction`. Returns the rows read inside the transaction just +/// before commit and the rows read after it (and after a checkpoint or +/// reopen, by `mode`). +fn run(mode: &Mode, setup: &[&str], stmts: &[&str]) -> (Rows, Rows) { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("o.graph"); + let db = match mode { + Mode::Memory => Minigraf::in_memory().unwrap(), + _ => Minigraf::open(&path).unwrap(), + }; + for w in setup { + db.execute(w).unwrap(); + } + let mut tx = db.begin_write().unwrap(); + for s in stmts { + tx.execute(s).unwrap(); + } + let inside = ( + to_rows(tx.execute(NOW).unwrap()), + to_rows(tx.execute(ANY).unwrap()), + ); + tx.commit().unwrap(); + let after = match mode { + Mode::Memory => read(&db), + Mode::Checkpointed => { + db.checkpoint().unwrap(); + read(&db) + } + Mode::Reopened => { + drop(db); + read(&Minigraf::open(&path).unwrap()) + } + }; + (inside, after) +} + +fn rows(now: &[&str], any: &[&str]) -> Rows { + ( + now.iter().map(|s| s.to_string()).collect(), + any.iter().map(|s| s.to_string()).collect(), + ) +} + +const FOREVER: &str = "9223372036854775807"; +/// 2030-01-01 in Unix ms. +const T2030: &str = "1893456000000"; + +const ASSERT: &str = r#"(transact [[:d/c :tag "a"]])"#; +const ASSERT_2030: &str = + r#"(transact {:valid-from "2020-01-01" :valid-to "2030-01-01"} [[:d/c :tag "a"]])"#; +const RETRACT: &str = r#"(retract [[:d/c :tag "a"]])"#; + +/// Every mix of two statements on one triple, after a committed assertion +/// and on an empty database: the second statement decides, before and after +/// commit. +#[test] +fn last_statement_decides_triple() { + let live = rows(&["a"], &[&format!("a {FOREVER}")]); + let live_2030 = rows(&["a"], &[&format!("a {T2030}")]); + let gone = rows(&[], &[]); + let cases: [(&[&str], [&str; 2], &Rows); 10] = [ + (&[ASSERT], [RETRACT, ASSERT], &live), + (&[], [RETRACT, ASSERT], &live), + (&[ASSERT], [ASSERT, RETRACT], &gone), + (&[], [ASSERT, RETRACT], &gone), + (&[ASSERT], [RETRACT, RETRACT], &gone), + (&[ASSERT], [ASSERT, ASSERT_2030], &live_2030), + (&[], [ASSERT_2030, ASSERT], &live), + (&[ASSERT], [RETRACT, ASSERT_2030], &live_2030), + (&[ASSERT_2030], [ASSERT, ASSERT], &live), + (&[ASSERT], [ASSERT_2030, RETRACT], &gone), + ]; + for (i, (setup, stmts, want)) in cases.iter().enumerate() { + for mode in &MODES { + let (inside, after) = run(mode, setup, stmts); + assert_eq!(&inside, *want, "case {i}: inside the transaction"); + assert_eq!(&after, *want, "case {i}: committed"); + } + } +} + +/// Only the triple's earlier statements are dropped: other values in the +/// same statements stay, and the commit is still one transaction. +#[test] +fn other_triples_of_overridden_statement_survive() { + for mode in &MODES { + let (inside, after) = run( + mode, + &[], + &[ + r#"(transact [[:d/c :tag "a"] [:d/c :tag "b"]])"#, + r#"(retract [[:d/c :tag "a"] [:d/c :tag "c"]])"#, + r#"(transact [[:d/c :tag "c"]])"#, + ], + ); + let want = rows( + &["b", "c"], + &[&format!("b {FOREVER}"), &format!("c {FOREVER}")], + ); + assert_eq!(inside, want, "inside the transaction"); + assert_eq!(after, want, "committed"); + } +} + +/// The committed transaction holds only the surviving records: one +/// `tx_count`, and an overridden assertion is not in history. +#[test] +fn commit_writes_one_transaction_without_overridden_records() { + let db = Minigraf::in_memory().unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(ASSERT_2030).unwrap(); + tx.execute(RETRACT).unwrap(); + tx.execute(ASSERT).unwrap(); + tx.commit().unwrap(); + assert_eq!(db.current_tx_count(), 1, "one transaction"); + let history = to_rows( + db.execute( + r#"(query [:find ?v ?vt ?tc :any-valid-time :where [?e :tag ?v] [?e :db/valid-to ?vt] [?e :db/tx-count ?tc]])"#, + ) + .unwrap(), + ); + assert_eq!( + history, + vec![format!("a {FOREVER} 1")], + "only the last statement's record" + ); +} + +/// Two windows of one triple in one statement are API-011 from +/// `tx.execute`; nothing of that statement is staged and the transaction +/// still commits its other statements. +#[test] +fn two_windows_in_one_statement_rejected_by_tx_execute() { + for mode in &MODES { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("w.graph"); + let db = match mode { + Mode::Memory => Minigraf::in_memory().unwrap(), + _ => Minigraf::open(&path).unwrap(), + }; + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:d/c :tag "b"]])"#).unwrap(); + let err = tx + .execute( + r#"(transact [[:d/c :tag "a" {:valid-to "2030-01-01"}] [:d/c :tag "a" {:valid-from "2020-01-01"}] [:d/c :tag "z"]])"#, + ) + .expect_err("two windows in one statement"); + assert_eq!(err.code(), "API-011"); + tx.commit().unwrap(); + let db = match mode { + Mode::Reopened => { + drop(db); + Minigraf::open(&path).unwrap() + } + _ => db, + }; + assert_eq!( + read(&db).0, + vec!["b".to_string()], + "only the accepted statement" + ); + assert_eq!(db.current_tx_count(), 1, "one transaction"); + } +} diff --git a/tests/valid_time_window_test.rs b/tests/valid_time_window_test.rs index 6daaeac937..875c85d13b 100644 --- a/tests/valid_time_window_test.rs +++ b/tests/valid_time_window_test.rs @@ -191,9 +191,10 @@ fn same_transaction_repeat_or_other_value_accepted() { } /// Two windows of one triple across `execute` calls of one -/// `WriteTransaction` are API-011 at commit, and nothing is written. +/// `WriteTransaction`: the later statement's window is the one committed +/// (#477). #[test] -fn write_transaction_two_windows_rejected_at_commit() { +fn write_transaction_two_windows_across_statements_last_wins() { for mode in &MODES { with_db(mode, &[], |db| { let mut tx = db.begin_write().unwrap(); @@ -203,15 +204,10 @@ fn write_transaction_two_windows_rejected_at_commit() { .unwrap(); tx.execute(r#"(transact {:valid-from "2024-01-01"} [[:d/c :description "r"]])"#) .unwrap(); - let err = tx.commit().expect_err("two windows in one transaction"); - assert_eq!(err.code(), "API-011"); - assert!(!visible(db, "", "2020-06-01"), "nothing written"); - assert!(!visible(db, "", "2024-06-01"), "nothing written"); - - // The database still takes writes. - db.execute(r#"(transact {:valid-from "2024-01-01"} [[:d/c :description "r"]])"#) - .unwrap(); - assert!(visible(db, "", "2024-06-01"), "written after the rejection"); + tx.commit().unwrap(); + assert!(!visible(db, "", "2020-06-01"), "earlier statement dropped"); + assert!(visible(db, "", "2024-06-01"), "later statement committed"); + assert!(!visible(db, ":as-of 1", "2020-06-01"), "never in history"); }); } } @@ -228,3 +224,73 @@ fn write_transaction_repeat_without_bounds_accepted() { .unwrap(); tx.commit().unwrap(); } + +// ── Empty or inverted windows (#436) ───────────────────────────────────────── + +/// Transacts whose effective window ends at or before it starts. +const INVERTED: [&str; 5] = [ + r#"(transact {:valid-from "2026-08-21" :valid-to "2026-08-20"} [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2026-08-21" :valid-to "2026-08-21"} [[:d/c :description "r"]])"#, + // valid-from defaults to the transaction time, after valid-to. + r#"(transact {:valid-to "2020-01-01"} [[:d/c :description "r"]])"#, + // A per-fact bound inverts the transaction's window. + r#"(transact {:valid-from "2020-01-01" :valid-to "2030-01-01"} [[:d/x :n 1] [:d/c :description "r" {:valid-to "2019-01-01"}]])"#, + r#"(transact [[:d/x :n 1] [:d/c :description "r" {:valid-from "2031-01-01" :valid-to "2030-01-01"}]])"#, +]; + +/// Each is API-019 from `execute`, writes nothing and takes no `tx_count`. +#[test] +fn inverted_window_rejected_by_execute() { + for mode in &MODES { + with_db(mode, &[r#"(transact [[:d/x :n 0]])"#], |db| { + for (i, w) in INVERTED.iter().enumerate() { + let err = db.execute(w).expect_err("inverted window"); + assert_eq!(err.code(), "API-019", "case {i}"); + } + assert_eq!(db.current_tx_count(), 1, "no tx_count taken"); + assert_eq!( + count( + db, + r#"(query [:find ?e ?a ?v :any-valid-time :where [?e ?a ?v]])"# + ), + 1, + "nothing written" + ); + }); + } +} + +/// A window that ends after it starts, also in the past, is accepted. +#[test] +fn past_window_that_ends_after_it_starts_accepted() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + r#"(transact {:valid-from "2019-01-01" :valid-to "2020-01-01"} [[:d/c :description "r"]])"#, + ) + .unwrap(); + assert!(visible(&db, "", "2019-06-01"), "inside the window"); + assert!(!visible(&db, "", "2020-01-01"), "end is exclusive"); +} + +/// `tx.execute` rejects an inverted statement and stages nothing; the +/// transaction still commits its other statements. +#[test] +fn inverted_window_rejected_by_tx_execute() { + let db = Minigraf::in_memory().unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:d/x :n 1]])"#).unwrap(); + for (i, w) in INVERTED.iter().enumerate() { + let err = tx.execute(w).expect_err("inverted window"); + assert_eq!(err.code(), "API-019", "case {i}"); + } + tx.commit().unwrap(); + assert_eq!(db.current_tx_count(), 1, "one transaction"); + assert_eq!( + count( + &db, + r#"(query [:find ?e ?a ?v :any-valid-time :where [?e ?a ?v]])"# + ), + 1, + "only the accepted statement" + ); +} From 4a790cfed40e192dccd9e6f51291801cb13fddf4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 8 Oct 2026 08:39:20 +0530 Subject: [PATCH 3/3] fix(log_writer): keep the write rules in every built file (#477) LogWriter now rejects records that a normal write could not produce, so no file it builds holds facts that break the v3 write rules: an assertion whose valid-time window ends at or before it starts (API-019), a second window of one fact in one transaction (API-011), and an assertion and a retraction of one fact in one transaction, in either order (new API-020). Records of one transaction share a tx_id and have no order, so such a pair cannot say which write came last. Each rejected record changes nothing and the writer stays usable. An unfiltered copy is identical to a source that keeps these rules. A source written before them (v2.x via migration, earlier v3 builds) fails at the first such record; ERROR_REFERENCE describes the repair a middleware step applies first. Refs #477, #436, #431 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 4 +- ROADMAP.md | 2 +- docs/ERROR_REFERENCE.md | 17 ++- docs/TEST_COVERAGE.md | 2 +- ...e-validation-and-statement-order-design.md | 30 +++-- src/error.rs | 9 ++ src/log_writer.rs | 43 ++++++- tests/log_writer_test.rs | 111 ++++++++++-------- 8 files changed, 148 insertions(+), 70 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index fd1faf08b3..c83ecf946f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,14 +17,14 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit. - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed. - **Empty or inverted valid-time windows are rejected** (#436). A `transact` whose effective window for any fact ends at or before it starts fails with the new `API-019`, writes nothing and takes no transaction number. The effective window is the one after defaults, so `(transact {:valid-to "2020-01-01"} ...)` is rejected too: its `:valid-from` is the transaction time. This applies to `execute`, each `WriteTransaction::execute` statement and, with the commit time, `WriteTransaction::commit`, and the browser. Before, such a fact was stored, never matched `:valid-at`, and still showed up under `:any-valid-time`. Files that already hold such facts open and read as before. -- **In a `WriteTransaction`, the last statement that writes a fact decides it** (#477). When several `execute` calls in one `WriteTransaction` write the same `(entity, attribute, value)`, in any mix of `transact` and `retract`, the commit keeps only the records from the last of them. Before, reads inside the transaction already followed statement order, but the commit stamped every record with one transaction number and a retraction always won: a fact retracted and then asserted again read as live before `commit()` and was gone after it. Two windows of one fact in separate statements, which were `API-011`, now commit the later window. `API-011` is limited to one `transact`; `tx.execute()` raises it and stages nothing, and the transaction stays usable. +- **In a `WriteTransaction`, the last statement that writes a fact decides it** (#477). When several `execute` calls in one `WriteTransaction` write the same `(entity, attribute, value)`, in any mix of `transact` and `retract`, the commit keeps only the records from the last of them. Before, reads inside the transaction already followed statement order, but the commit stamped every record with one transaction number and a retraction always won: a fact retracted and then asserted again read as live before `commit()` and was gone after it. Two windows of one fact in separate statements, which were `API-011`, now commit the later window. `API-011` is limited to one `transact`; `tx.execute()` raises it and stages nothing, and the transaction stays usable. `LogWriter` keeps the same rules (see the log writer entry). - **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one `transact` is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both. ### Added - **Binding support for cursors, open options, the fact log and the log writer** (#462, #465, #467). Two new codes let language bindings report what Rust's types rule out: `API-017` (an argument the binding cannot convert, such as an entity id that is not a UUID string), from `MinigrafError::invalid_argument`, and `API-018` (a log writer used after `finish` or `close`), from `MinigrafError::closed`. `BrowserDb.query(datalog)` returns a `BrowserCursor` with `vars()`, `nextBatch(maxRows)` (rows as JSON, as in `execute()`, or `undefined` at the end) and `close()`. The shared binding shape is in `docs/superpowers/specs/2026-10-07-binding-etl-surface-design.md`. The wasm32 test build compiles again (a duplicate `page_cache_capacity` and `tempfile` tests on wasm32). - **Fact log: `Minigraf::fact_log()`** (#430). Streams every fact version in the database as `FactRecord`s (entity, attribute, value, `tx_count`, `tx_id`, valid-time bounds, and whether it is an assertion or a retraction), without Datalog. `FactFilter` selects attributes (exact or by prefix), entities and a `tx_count` range, checked on index keys so excluded records are never decoded. `FactOrder::Tx` (the default) returns records in ascending `tx_count`; format v8 has no index in transaction order, so it holds at most `FactFilter::window` records (default 262,144) and scans the selected keys once per window. `FactOrder::Storage` reads in one pass. The log reads the database as it was when it opened; while one is open, checkpoints are deferred (writes stay in the WAL, automatic checkpoints wait, and `checkpoint()` or `rebuild_indexes()` with work to do fail with the new `API-013`). Close, drop or finish the log to release it. Like `Cursor`, a `FactLog` is owned and `Send`. Rust API only for now; the bindings follow. -- **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`) and size (`WAL-003`); a rejected record changes nothing. Records are otherwise copied as they are, so an unfiltered copy is identical to its source, including transactions written before `API-011` or `API-019` that hold several records of one fact (#477). There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. +- **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`) and size (`WAL-003`); a rejected record changes nothing. Every file it builds keeps the rules of a normal write (#436, #477): a valid-time window that ends at or before it starts is `API-019`, a second window of one fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction the new `API-020`. An unfiltered copy of a source that keeps these rules is identical to it. A source written before them (v2.x, or earlier v3 builds) can break them, and copying it fails at the first such record, so a middleware step must repair those records first; `docs/ERROR_REFERENCE.md` describes each repair. There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. - **Read-only open: `OpenOptions::read_only`** (#429). Opens a database so that nothing done through the handle writes to the `.graph` file or its WAL. The file is locked in shared mode: any number of read-only handles, in this process or others, can hold it at once, and they exclude a read-write open (and it excludes them) with the existing STG-025/STG-026. The handle shows the same data as a read-write open: a WAL left by an earlier session is applied in memory but not checkpointed or deleted, and a format v7 file is read into memory instead of migrated. A missing file is the new `STG-042` (nothing is created). `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` fail with the new `API-014`; queries, cursors, `fact_log`, `verify` and rule registration work, and dropping the handle does not checkpoint. `page_cache_size` applies as usual, so a tool can keep the whole file resident. Rust API only for now; the bindings follow. - **Cursor API: `Minigraf::query()` and `PreparedQuery::query()`** (#432). Both return a `Cursor` that hands a query's rows back in batches: `vars()`, `next_batch(max_rows) -> Result, _>`, `close()`, and an iterator over rows. The answer is fixed when the cursor opens, so writes that commit while it is open do not change it. A cursor borrows nothing from the database handle: it can outlive it and move to another thread. For now the answer is still computed when the cursor opens, under the same limits as `execute()`; the API is shaped so the engine can later produce rows as they are pulled without breaking callers. `query()` rejects `transact`, `retract` and `rule` with the new `API-012`, and a query with bind slots with `API-010`. `execute()` is unchanged. Rust API only for now; the bindings follow. - **`Minigraf::verify()` and `Minigraf::rebuild_indexes()`** (#373). Page checksums turn a torn or rotted page into an error, but they cannot see a page that is valid and says the wrong thing. `verify()` walks every committed page and returns an `IntegrityReport` with one structured error per finding: an index that holds different facts than EAVT or a different count than the meta page (new `STG-038`), keys out of order or a page reached twice (new `STG-039`), dictionary maps that disagree (new `STG-040`), ids with no dictionary entry (`STG-036`), and leaked, doubly used or wrongly free pages (`STG-035`). It keeps no per-fact state: indexes are compared by an order-independent digest. `rebuild_indexes()` rebuilds EAVT, AEVT, AVET and VAET from an intact index that agrees with another one (or the only intact one), derives the free list again, and commits like a checkpoint, including uncheckpointed writes; a crash at any point leaves the previous checkpoint. If no index can serve as the source, or the dictionary is damaged, it fails with new `STG-041` and writes nothing. Both are Rust API only for now; the bindings follow. diff --git a/ROADMAP.md b/ROADMAP.md index 44a3c7d927..3b1e9871a9 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -64,7 +64,7 @@ Scope — format and storage integrity: - Net-assert on v8 keys before resolving facts, for O(live) point queries (#379; done on `v3`) - One current valid-time window per `(e, a, v)`: a later assertion replaces the earlier window, and two windows of one fact in one `transact` are `API-011` (#435; done on `v3`) - Empty or inverted valid-time windows rejected with `API-019` on every write path (#436; done on `v3`) -- In a `WriteTransaction`, the last statement that writes a fact decides it, so reads inside the transaction match the commit; `LogWriter` copies records verbatim (#477; done on `v3`) +- In a `WriteTransaction`, the last statement that writes a fact decides it, so reads inside the transaction match the commit; `LogWriter` keeps the same rules, with `API-020` for an assertion and retraction of one fact in one transaction (#477; done on `v3`) - `btree_page` fuzz target that reaches node decoding (#375) Scope — query API: diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 4251e931a4..6790e7623b 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -177,6 +177,7 @@ with no `CodedError` anywhere in its chain. | API-017 | Invalid argument passed through a language binding | Database API | | API-018 | Call on a closed binding object | Database API | | API-019 | Empty or inverted valid-time window | Database API | +| API-020 | Assertion and retraction of one fact in one log-writer transaction | Database API | | INT-000 | Unclassified internal error | Internal | | INT-001 | WriteTransaction already in progress on this thread | Internal | | INT-002 | Invalid entity (API layer) | Internal | @@ -2481,7 +2482,7 @@ let result = pq.execute(&[ **Error text**: `one (transact ...) asserts the same value of {} with two valid-time windows; assert it once with its final window` -**Cause**: One `(transact ...)` asserts the same entity, attribute and value twice with different `:valid-from`/`:valid-to` bounds. At any transaction time a fact has exactly one current valid-time window. Within one statement neither window comes later, so the statement is rejected and nothing is written. The `{}` is the attribute. Identical repeats are allowed and stored once. Inside a `WriteTransaction`, `tx.execute()` rejects the statement and stages nothing; the transaction stays usable. Across several statements of one `WriteTransaction` there is no error: the last statement that writes a fact decides it (#477). `LogWriter::append` copies records as they are and never returns this code. +**Cause**: One `(transact ...)` asserts the same entity, attribute and value twice with different `:valid-from`/`:valid-to` bounds. At any transaction time a fact has exactly one current valid-time window. Within one statement neither window comes later, so the statement is rejected and nothing is written. The `{}` is the attribute. Identical repeats are allowed and stored once. Inside a `WriteTransaction`, `tx.execute()` rejects the statement and stages nothing; the transaction stays usable. Across several statements of one `WriteTransaction` there is no error: the last statement that writes a fact decides it (#477). `LogWriter::append` returns this code for a record that asserts a fact the open transaction already asserts with another window; that record alone is rejected. **Resolution**: - Assert the fact once per transaction, with the window it should have. @@ -2609,7 +2610,7 @@ let mut log = src.fact_log(&FactFilter::new())?; **Error text**: `the valid-time window of {} ends at or before it starts; :valid-to must be later than :valid-from (the transaction time when :valid-from is omitted)` -**Cause**: A `transact` gives a fact a valid-time window whose end is at or before its start, so the fact could never match a `:valid-at` query. The check uses the effective window, after defaults: the fact's own bound, else the transaction's, else `:valid-from` is the transaction time and `:valid-to` is forever. A `:valid-to` in the past with no `:valid-from` is therefore rejected too. The whole transaction is rejected, nothing is written and no transaction number is used. The `{}` is the attribute. Inside a `WriteTransaction`, `tx.execute()` checks each statement. `commit()` checks again with the commit time, so a `:valid-to` that passed while staging can still fail at commit. Files written before this check, and records copied by `LogWriter`, are read as they are. +**Cause**: A `transact` gives a fact a valid-time window whose end is at or before its start, so the fact could never match a `:valid-at` query. The check uses the effective window, after defaults: the fact's own bound, else the transaction's, else `:valid-from` is the transaction time and `:valid-to` is forever. A `:valid-to` in the past with no `:valid-from` is therefore rejected too. The whole transaction is rejected, nothing is written and no transaction number is used. The `{}` is the attribute. Inside a `WriteTransaction`, `tx.execute()` checks each statement. `commit()` checks again with the commit time, so a `:valid-to` that passed while staging can still fail at commit. `LogWriter::append` rejects such a record the same way; that record alone is rejected. Files written before this check are read as they are. **Resolution**: - Give `:valid-to` a later instant than `:valid-from`. @@ -2629,6 +2630,18 @@ let mut log = src.fact_log(&FactFilter::new())?; **Scenario**: An import sets `:valid-to` from a source's end date but leaves out `:valid-from`, so past end dates produce windows that end before the transaction time. +### API-020 Assertion and retraction of one fact in one log-writer transaction + +**Error text**: `one transaction both asserts and retracts the same value of {}; keep only the record that decides it` + +**Cause**: `LogWriter::append` was given a record that asserts an entity, attribute and value the open transaction retracts, or retracts one it asserts. Records of one transaction carry one `tx_id` and have no order, so the pair does not say which write came last. A normal write never produces such a transaction: in a `WriteTransaction` the last statement that writes a fact decides it (#477). The record alone is rejected, and the writer stays usable. The `{}` is the attribute. A source written by Minigraf 2.x, or by v3 builds before #477, can hold such transactions; copying one fails at the first such record. + +**Resolution**: +- Keep only the record that decides the fact. Readers of the source hide the fact when its newest transaction holds a retraction, so dropping the transaction's assertions of that fact keeps every query result the same. +- Repair the source's other old records the same way before appending them: a fact with two windows in one transaction (API-011) keeps the window it should have, and an assertion whose window ends before it starts (API-019) is dropped. + +**Scenario**: An offline purge copies a database migrated from v2.x through `fact_log()` and `LogWriter`, and one of its transactions retracted and re-asserted a fact. + --- ## INT — Internal Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 9fafc11d76..0d16cbb932 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -6,7 +6,7 @@ **Result**: 1,351 passing tests and 9 ignored tests (1,360 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). 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 copies a source whose transactions hold two windows of a fact, an assertion and a retraction of one fact, and an inverted window, and checks the copy holds every record and answers like the source at every `:as-of`. 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`, and oversize values or idents `WAL-003` (a second window or a retraction of a fact in one transaction is kept, #477), each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `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. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md b/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md index 17af2c3c3e..7197a0777e 100644 --- a/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md +++ b/docs/superpowers/specs/2026-10-07-write-validation-and-statement-order-design.md @@ -22,15 +22,20 @@ records from one statement only. Reads inside the transaction already follow statement order, so they now agree with the committed result. This replaces API-011's cross-statement rejection. -4. **`LogWriter` copies records verbatim.** Without filters or middleware, an ETL target - must be identical to its source. The writer no longer collapses or rejects records - of one transaction (the API-011 check is removed). It keeps API-015 and API-016, - which protect transaction order. Readers keep their tie rules for transactions that - hold several records of one triple (a retraction in the group hides it; several - windows are kept once each), so source and target read the same. +4. **`LogWriter` keeps the same rules.** Every file it builds satisfies rules 1–3, as if + written normally: an inverted window is API-019, a second window of one triple in one + transaction API-011, and an assertion plus a retraction of one triple in one + transaction (either order) the new **API-020**. Records of one transaction share a + `tx_id` and have no order, so the pair cannot say which came last; no normal write + produces it after rule 3. Each rejected record changes nothing, as with API-015 and + API-016. An unfiltered copy is identical to a source that keeps the rules. A source + written before them (v2.x via migration, earlier v3 builds) fails at the first such + record, and a middleware step must repair it (drop the assertions where a retraction + decides, keep one window, drop inverted windows). -`load_fact`, WAL replay, migration and the log writer never check rules 1–3. Files that -already contain such data open and read as before. +`load_fact`, WAL replay and migration never check rules 1–3. Files that already contain +such data open and read as before: readers keep their tie rules (a retraction in the +group hides the triple; several windows are kept once each). ## 2. Changes @@ -51,7 +56,9 @@ already contain such data open and read as before. `check_valid_windows` on what is left (a default `valid_from` moves to the commit time, so a `:valid-to` between staging and commit is caught here), then allocate the `tx_count` and write. -- `src/log_writer.rs`: drop the window map and the API-011 check. +- `src/log_writer.rs`: per open transaction, the window (or retraction) written for each + triple; API-019, API-011 and API-020 are checked before the record is loaded. New + **API-020** "Assertion and retraction of one fact in one log-writer transaction". ## 3. Tests @@ -65,8 +72,9 @@ already contain such data open and read as before. `WriteTransaction` give the same rows before and after commit, in memory, checkpointed and reopened. API-011 inside one statement of a `WriteTransaction` is raised by `tx.execute`, and the transaction still commits its other statements. -- `tests/log_writer_test.rs`: a record group with two windows and an assert plus - retract of one triple is copied verbatim and reads like the source. +- `tests/log_writer_test.rs`: API-019, API-011 and API-020 (both orders), each leaving + the writer usable and the output exact; duplicate retractions, identical repeats and + the same triple in the next transaction are accepted. - `tests/model_based_test.rs`: the model applies rules 1–3 (rejections from `execute` and `tx.execute`, last statement wins at commit) and checks reads inside a write transaction against the committed result. diff --git a/src/error.rs b/src/error.rs index 3a19ea0599..3fd6cc95bb 100644 --- a/src/error.rs +++ b/src/error.rs @@ -209,6 +209,7 @@ pub(crate) enum ErrorCode { Api017, Api018, Api019, + Api020, Int001, Int002, Int003, @@ -1214,6 +1215,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "the valid-time window of {} ends at or before it starts; :valid-to must be later than :valid-from (the transaction time when :valid-from is omitted)", ErrorCategory::Api, ), + ( + ErrorCode::Api020, + "API-020", + "one transaction both asserts and retracts the same value of {}; keep only the record that decides it", + ErrorCategory::Api, + ), ( ErrorCode::Int001, "INT-001", @@ -1993,6 +2000,7 @@ mod tests { | ErrorCode::Api017 | ErrorCode::Api018 | ErrorCode::Api019 + | ErrorCode::Api020 | ErrorCode::Int001 | ErrorCode::Int002 | ErrorCode::Int003 @@ -2210,6 +2218,7 @@ mod tests { ErrorCode::Api017, ErrorCode::Api018, ErrorCode::Api019, + ErrorCode::Api020, ErrorCode::Int001, ErrorCode::Int002, ErrorCode::Int003, diff --git a/src/log_writer.rs b/src/log_writer.rs index 5b92a6c8f3..274d40215c 100644 --- a/src/log_writer.rs +++ b/src/log_writer.rs @@ -14,17 +14,22 @@ use crate::db::OpenOptions; use crate::error::{ErrorCode, MinigrafError, bail_coded, err_coded}; use crate::fact_log::FactRecord; -use crate::graph::types::Fact; +use crate::graph::types::{EntityId, Fact}; use crate::storage::backend::file::{FileBackend, LockMode}; use crate::storage::dir_sync::sync_parent_dir; +use crate::storage::index::encode_value; use crate::storage::persistent_facts::PersistentFactStorage; use anyhow::Result; +use std::collections::HashMap; use std::ffi::OsString; use std::path::{Path, PathBuf}; /// Pending facts after which the next transaction boundary commits a batch. const BATCH_FACTS: usize = 1 << 16; +/// An `(entity, attribute, encoded value)` triple. +type TripleKey = (EntityId, String, Vec); + /// Writes explicit fact records into a new database file. /// /// Records must come in transaction order: each one either opens a new @@ -60,6 +65,9 @@ pub struct LogWriter { tx_count: u64, /// The open transaction's `(tx_count, tx_id)`, if a record can join it. open_tx: Option<(u64, u64)>, + /// What the open transaction writes per `(e, a, v)`: its valid-time + /// window, or `None` for a retraction. + written: HashMap>, /// Facts loaded since the last batch commit. pending: usize, } @@ -102,6 +110,7 @@ impl LogWriter { partial, tx_count: 0, open_tx: None, + written: HashMap::new(), pending: 0, }) } @@ -127,6 +136,12 @@ impl LogWriter { /// - `API-015` if `tx_count` is 0, below the writer's, or names a /// transaction that is already closed. /// - `API-016` if it joins the open transaction with a different `tx_id`. + /// - `API-019` if it asserts a valid-time window that ends at or before + /// it starts. + /// - `API-011` if it asserts an `(entity, attribute, value)` the open + /// transaction already asserts with another valid-time window. + /// - `API-020` if it asserts an `(entity, attribute, value)` the open + /// transaction retracts, or retracts one it asserts. /// - `WAL-003` if the attribute, a keyword or a string value is longer /// than the format stores. /// @@ -158,9 +173,27 @@ impl LogWriter { asserted: rec.asserted, }; crate::wal::check_fact_size(&fact)?; - // Records are copied as they are (#477): one transaction may hold - // several records of a triple, as a source written before API-011 or - // API-019 can. Readers resolve them the same way in source and target. + // The rules of a normal write hold for every file built here (#477): + // a source carrying older records that break them must be repaired + // before it is copied. + if fact.asserted && fact.valid_to <= fact.valid_from { + bail_coded!(ErrorCode::Api019, fact.attribute); + } + let key = ( + fact.entity, + fact.attribute.clone(), + encode_value(&fact.value), + ); + let this = fact.asserted.then_some((fact.valid_from, fact.valid_to)); + if joins && let Some(prev) = self.written.get(&key) { + match (prev, this) { + (Some(a), Some(b)) if *a != b => bail_coded!(ErrorCode::Api011, fact.attribute), + (Some(_), None) | (None, Some(_)) => { + bail_coded!(ErrorCode::Api020, fact.attribute) + } + _ => {} + } + } if !joins { self.close_tx(); @@ -170,6 +203,7 @@ impl LogWriter { self.tx_count = rec.tx_count; self.open_tx = Some((rec.tx_count, rec.tx_id)); } + self.written.insert(key, this); let pfs = self.pfs_mut()?; if pfs.storage().load_fact(fact)? { pfs.mark_dirty(); @@ -239,6 +273,7 @@ impl LogWriter { fn close_tx(&mut self) { self.open_tx = None; + self.written.clear(); } /// Commit the pending records as the next generation of the file. diff --git a/tests/log_writer_test.rs b/tests/log_writer_test.rs index a5c3684231..4f831fea6b 100644 --- a/tests/log_writer_test.rs +++ b/tests/log_writer_test.rs @@ -378,14 +378,19 @@ fn rejected_records_change_nothing() { "two tx_ids" ); - // Records are copied as they are (#477): a second window and a - // retraction of the same triple in one transaction are kept. let mut other_window = rec(3, 300, ":a/x", 1); other_window.valid_to = 400; - w.append(&other_window).unwrap(); + assert_eq!(code(w.append(&other_window)), "API-011", "two windows"); let mut retraction = other_window.clone(); retraction.asserted = false; - w.append(&retraction).unwrap(); + assert_eq!( + code(w.append(&retraction)), + "API-020", + "retracting what the transaction asserts" + ); + let mut inverted = rec(3, 300, ":a/z", 1); + inverted.valid_to = 300; + assert_eq!(code(w.append(&inverted)), "API-019", "empty window"); let mut big = rec(3, 300, ":a/x", 0); big.value = Value::String("x".repeat(1 << 20)); @@ -414,8 +419,6 @@ fn rejected_records_change_nothing() { let mut got: Vec = records(&db).iter().map(row).collect(); got.sort(); let want = vec![ - "3 300 e1 :a/x Integer(1) 300 400 false".to_string(), - "3 300 e1 :a/x Integer(1) 300 400 true".to_string(), "3 300 e1 :a/x Integer(1) 300 9223372036854775807 true".to_string(), "3 300 e1 :a/y Integer(9) 300 9223372036854775807 true".to_string(), "4 250 e1 :a/x Integer(6) 250 9223372036854775807 true".to_string(), @@ -424,54 +427,64 @@ fn rejected_records_change_nothing() { assert!(db.verify().unwrap().is_ok(), "verify is clean"); } -/// A source whose transactions hold several records of one triple, as files -/// written before API-011 and API-019 can (two windows, an assertion and a -/// retraction, an inverted window), is copied record for record, and the -/// copy answers like the source (#477). +/// Every file the writer builds keeps the rules of a normal write (#477): +/// an inverted window, two windows of one fact in one transaction, and an +/// assertion and a retraction of one fact in one transaction (either order) +/// are rejected. Duplicate retractions, identical repeats, and the same fact +/// in the next transaction are accepted. #[test] -fn mixed_transactions_are_copied_verbatim() { +fn records_that_break_write_rules_are_rejected() { let dir = Dir::new(); - let src_path = dir.path("src.graph"); - let mut w = LogWriter::create(&src_path, OpenOptions::new()).unwrap(); - let mut records_in = vec![ - rec(1, 100, ":a/x", 1), - rec(2, 200, ":a/x", 1), - rec(2, 200, ":a/y", 2), - rec(3, 300, ":a/z", 3), - ]; - records_in[1].valid_to = 250; // two windows of :a/x 1 in tx 2 - let mut second = rec(2, 200, ":a/x", 1); + let out = dir.path("out.graph"); + let mut w = LogWriter::create(&out, OpenOptions::new()).unwrap(); + let code = |r: Result<(), minigraf::MinigrafError>| r.unwrap_err().code().to_string(); + let retract = |mut r: FactRecord| { + r.asserted = false; + r + }; + + let mut inverted = rec(1, 100, ":a/w", 4); + inverted.valid_to = 50; + assert_eq!( + code(w.append(&inverted)), + "API-019", + "ends before it starts" + ); + assert_eq!(w.tx_count(), 0, "a rejected record opens no transaction"); + + w.append(&retract(rec(1, 100, ":a/y", 2))).unwrap(); + w.append(&retract(rec(1, 100, ":a/y", 2))).unwrap(); + assert_eq!( + code(w.append(&rec(1, 100, ":a/y", 2))), + "API-020", + "retract then assert" + ); + w.append(&rec(1, 100, ":a/x", 1)).unwrap(); + w.append(&rec(1, 100, ":a/x", 1)).unwrap(); + assert_eq!( + code(w.append(&retract(rec(1, 100, ":a/x", 1)))), + "API-020", + "assert then retract" + ); + let mut second = rec(1, 100, ":a/x", 1); second.valid_from = 50; - second.valid_to = 150; - records_in.insert(2, second); - let mut retracted = rec(2, 200, ":a/y", 2); - retracted.asserted = false; // :a/y 2 asserted and retracted in tx 2 - records_in.push(retracted); - let mut inverted = rec(3, 300, ":a/w", 4); - inverted.valid_to = 200; // ends before it starts - records_in.push(inverted); - records_in.sort_by_key(|r| r.tx_count); - for r in &records_in { - w.append(r).unwrap(); - } + assert_eq!(code(w.append(&second)), "API-011", "second window"); + // The next transaction may write the fact again, any way. + w.append(&retract(rec(2, 200, ":a/x", 1))).unwrap(); + w.append(&rec(2, 200, ":a/y", 2)).unwrap(); w.finish().unwrap(); - let src = Minigraf::open(&src_path).unwrap(); - let mut want: Vec = records_in.iter().map(row).collect(); - want.sort(); - assert_eq!(log_rows(&src), want, "source holds every record"); - - let out = dir.path("out.graph"); - copy(&src, &out, |_| true); - let dst = Minigraf::open(&out).unwrap(); - same_answers(&src, &dst); - for n in 0..=src.current_tx_count() { - let q = format!( - "(query [:find ?a ?v ?vf ?vt :as-of {n} :any-valid-time :where [?e ?a ?v] [?e :db/valid-from ?vf] [?e :db/valid-to ?vt]])" - ); - assert_eq!(rows(&src, &q), rows(&dst, &q), "{q}"); - } - assert!(dst.verify().unwrap().is_ok(), "verify is clean"); + let db = Minigraf::open(&out).unwrap(); + let mut got: Vec = records(&db).iter().map(row).collect(); + got.sort(); + let want = vec![ + "1 100 e1 :a/x Integer(1) 100 9223372036854775807 true".to_string(), + "1 100 e1 :a/y Integer(2) 100 9223372036854775807 false".to_string(), + "2 200 e1 :a/x Integer(1) 200 9223372036854775807 false".to_string(), + "2 200 e1 :a/y Integer(2) 200 9223372036854775807 true".to_string(), + ]; + assert_eq!(got, want); + assert!(db.verify().unwrap().is_ok(), "verify is clean"); } #[test]