From 5622312519057fcc9ab02c04cafb327f53233081 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 23:20:05 +0530 Subject: [PATCH] fix: one current valid-time window per (e, a, v) (#435) At transaction time N a triple now has exactly one current valid-time window: the one from its latest assertion at or before N, if newer than its last retraction. A later assertion replaces the earlier window, which stays visible through :as-of. Closing, extending or reopening a window is a plain transact with the new bounds; retract still withdraws the triple. net_asserted_facts now picks a winner per (e, a, v) instead of per (e, a, v, vf, vt), and the on-disk key walk stops at each triple's first transaction group. Two windows of one triple in one transaction are rejected with the new API-011 before a tx_count is taken (execute, WriteTransaction::commit, the browser write path, FactStorage::transact*). Records written before the check with two windows in one transaction keep both; open, WAL replay and migration never fail on them. This changes query results for existing data, so it ships in v3.0.0. Design: docs/superpowers/specs/2026-10-06-one-window-per-triple-design.md Refs #435, #383 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 3 +- CLAUDE.md | 2 +- README.md | 2 +- ROADMAP.md | 1 + docs/ERROR_REFERENCE.md | 24 ++ docs/TEST_COVERAGE.md | 4 +- .../specs/2026-10-06-live-key-scans-design.md | 4 + ...2026-10-06-one-window-per-triple-design.md | 59 +++ src/browser/mod.rs | 3 + src/db.rs | 6 + src/error.rs | 9 + src/graph/storage.rs | 371 +++++++++++++----- src/storage/mod.rs | 4 +- src/storage/persistent_facts.rs | 77 ++++ src/storage/reader.rs | 72 ++-- tests/bitemporal_test.rs | 47 ++- tests/multi_value_test.rs | 123 +++--- tests/valid_time_window_test.rs | 230 +++++++++++ 18 files changed, 796 insertions(+), 245 deletions(-) create mode 100644 docs/superpowers/specs/2026-10-06-one-window-per-triple-design.md create mode 100644 tests/valid_time_window_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 268c48b27e..68ee32c6ff 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -16,6 +16,7 @@ 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. ### Added @@ -30,7 +31,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Internal -- **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (newest assertion per valid-time window, newer than every retraction) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. +- **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. ### Tests diff --git a/CLAUDE.md b/CLAUDE.md index 92ffeb6beb..a8923e6ab4 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -194,7 +194,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1252 tests** (1243 passing, 9 ignored; unit + integration + doc). +**1267 tests** (1258 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 41884054e0..aa7336f7c7 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1252 tests +cargo test # run 1267 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index cb6f7ab715..3b80de0838 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -62,6 +62,7 @@ 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`) - `btree_page` fuzz target that reaches node decoding (#375) Scope — release-gate testing and documentation: diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 55f0d8a8eb..26ae510b4f 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -166,6 +166,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 | | INT-000 | Unclassified internal error | Internal | | INT-001 | WriteTransaction already in progress on this thread | Internal | | INT-002 | Invalid entity (API layer) | Internal | @@ -2428,6 +2429,29 @@ 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 + +**Error text**: `one transaction 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, or from several `execute()` calls inside one `WriteTransaction`. + +**Resolution**: +- Assert the fact once per transaction, with the window it should have. +- To change a window later (close it, extend it, reopen it), `transact` the same fact again with the new bounds. The earlier window stays visible through `:as-of`. +- 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 +(transact [[:alice :salary 100000 {:valid-from "2020-01-01" :valid-to "2022-01-01"}] + [:alice :salary 100000 {:valid-from "2024-01-01"}]]) + +;; Accepted: close the open window in a later transaction +(transact {:valid-from "2020-01-01"} [[:alice :salary 100000]]) +(transact {:valid-from "2020-01-01" :valid-to "2022-01-01"} [[:alice :salary 100000]]) +``` + +**Scenario**: A batch import writes the same fact once per period it was true, all in one transaction. + --- ## INT — Internal Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index cad6856be3..7820215fd5 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-06 with `cargo test --quiet` -**Result**: 1,243 passing tests and 9 ignored tests (1,252 total) +**Result**: 1,258 passing tests and 9 ignored tests (1,267 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-06-live-key-scans-design.md b/docs/superpowers/specs/2026-10-06-live-key-scans-design.md index fbe0948db6..b1872223db 100644 --- a/docs/superpowers/specs/2026-10-06-live-key-scans-design.md +++ b/docs/superpowers/specs/2026-10-06-live-key-scans-design.md @@ -4,6 +4,10 @@ **Milestone:** v3.0.0, branch `v3`, file format v8 (no format change) **Builds on:** `2026-10-05-v8-storage-format-design.md` §5.3, §7 +> **Superseded in part by #435** (`2026-10-06-one-window-per-triple-design.md`): net-assert now +> keeps each triple's newest transaction, not the newest assertion per window, so the walk +> stops at the first transaction group of each triple. The per-window rule below is history. + ## 1. Problem Every non-`:as-of` query fetches facts, then applies `net_asserted_facts` (keep an diff --git a/docs/superpowers/specs/2026-10-06-one-window-per-triple-design.md b/docs/superpowers/specs/2026-10-06-one-window-per-triple-design.md new file mode 100644 index 0000000000..6197cdacb4 --- /dev/null +++ b/docs/superpowers/specs/2026-10-06-one-window-per-triple-design.md @@ -0,0 +1,59 @@ +# One current valid-time window per triple — Design + +**Issue:** #435, tracker #383 +**Milestone:** v3.0.0, branch `v3` (no format change; changes query results) +**Builds on:** `2026-10-06-live-key-scans-design.md` (#379) + +## 1. Model + +For each `(e, a, v)`, transaction time N has exactly one current valid-time window: the +window of the latest assertion with `tx_count ≤ N`, provided it is newer than the +triple's last retraction. `:as-of N` selects that window; `:valid-at` is then checked +against it only. A later assertion replaces the earlier window, which stays visible +through `:as-of` of the earlier transaction. Closing, extending or reopening a window +is a `transact` with the new bounds. `retract` still withdraws the triple. + +## 2. Defect + +`net_asserted_facts` picked a winner per `(e, a, v, vf, vt)`, so every window ever +asserted stayed live until a retraction. `[vf, ∞)` followed by `[vf, D)` left both live. + +## 3. Changes + +- `net_asserted_facts` (`src/graph/storage.rs`): one map keyed by `(e, a, v)` holding + the first latest assertion's index and `tx_count`, plus a `tied` flag set when another + assertion has the same `tx_count`. Untied triples keep one record with no extra work. + Tied triples (only from data written before §4) take a second pass that keeps each + window of the latest transaction once, which also keeps the function idempotent + under duplicated input. +- On-disk walk (`OnDiskReader::live_scan`, `src/storage/reader.rs`): the first + transaction group of a triple at or before `as_of` decides it. A retraction in it + hides the triple, otherwise its assertions are emitted. Every older entry is dead and + skipped (with the existing seek after 8). The per-triple window set is gone. +- `check_one_window_per_triple`: two assertions of one triple with different + `(vf, vt)` in one transaction are rejected with **API-011**. It runs on + `Minigraf::execute` transacts and `WriteTransaction::commit` before a `tx_count` is + allocated or the WAL is written, and in `FactStorage::transact`/`transact_batch`. + Unresolved `valid_from`s all hold `VALID_FROM_USE_TX_TIME`, so repeats without bounds + compare equal, as they will after stamping. Identical repeats and retractions are + allowed. WAL replay, migration and `load_fact` are not checked: old data must open. + +## 4. Data written before the check + +v2.x and earlier v3 builds could store two windows of one triple in one transaction. +Both stay live (once each) until a later transaction of that triple. In-memory and +on-disk paths agree on this, and no open or migration fails because of it. + +## 5. Tests + +- Unit: replace, close, retraction-withdraws, same-transaction retraction, legacy tied + windows; randomized histories against a per-triple model (replaces the pre-#323 + per-window oracle); API-011 accepts repeats, other values and retractions; a rejected + `transact_batch` takes no `tx_count`. +- On disk: hand-written history (closing, same-transaction retract, legacy pair) at every + `as_of`, before and after reopen; fails on the per-window walk. +- `tests/valid_time_window_test.rs`: the issue's table, close, extend/reopen, + retract-then-reassert, API-011 from `transact` and `WriteTransaction`, in memory, + checkpointed, and reopened, through EAVT and AEVT queries. +- Revised: `bitemporal_test::test_same_eav_later_valid_time_interval_replaces_earlier`, + `multi_value_test::multi_value_time_stints_visible_at_correct_valid_time_on_every_path`. diff --git a/src/browser/mod.rs b/src/browser/mod.rs index e8a065f423..8b1c61159b 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -266,6 +266,9 @@ impl BrowserDb { let (dirty_pages, result_json) = { let mut inner = self.inner.borrow_mut(); + // Before allocating: a rejected transaction takes no tx_count (#435). + 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(); diff --git a/src/db.rs b/src/db.rs index cd2edb2ed6..d86f51a0fa 100644 --- a/src/db.rs +++ b/src/db.rs @@ -626,6 +626,8 @@ impl Minigraf { } _ => return Err(err_coded!(ErrorCode::Api002)), }; + // Before allocating: a rejected transaction takes no tx_count. + 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(); @@ -1325,6 +1327,10 @@ impl<'a> WriteTransaction<'a> { let facts_to_commit = std::mem::take(&mut self.pending_facts); if !facts_to_commit.is_empty() { + // 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(); let tx_id = crate::graph::types::tx_id_now(); diff --git a/src/error.rs b/src/error.rs index 18567c53cc..457bf4163c 100644 --- a/src/error.rs +++ b/src/error.rs @@ -198,6 +198,7 @@ pub(crate) enum ErrorCode { Api008, Api009, Api010, + Api011, Int001, Int002, Int003, @@ -1136,6 +1137,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "query contains bind slots ({}); use prepare() and execute the prepared query with bind values", ErrorCategory::Api, ), + ( + ErrorCode::Api011, + "API-011", + "one transaction asserts the same value of {} with two valid-time windows; assert it once with its final window", + ErrorCategory::Api, + ), ( ErrorCode::Int001, "INT-001", @@ -1884,6 +1891,7 @@ mod tests { | ErrorCode::Api008 | ErrorCode::Api009 | ErrorCode::Api010 + | ErrorCode::Api011 | ErrorCode::Int001 | ErrorCode::Int002 | ErrorCode::Int003 @@ -2089,6 +2097,7 @@ mod tests { ErrorCode::Api008, ErrorCode::Api009, ErrorCode::Api010, + ErrorCode::Api011, ErrorCode::Int001, ErrorCode::Int002, ErrorCode::Int003, diff --git a/src/graph/storage.rs b/src/graph/storage.rs index c832d86c80..4b8c978ac9 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -1,4 +1,4 @@ -use crate::error::{ErrorCode, err_coded}; +use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::types::{ Attribute, EntityId, Fact, TransactOptions, TxId, VALID_TIME_FOREVER, Value, tx_id_now, }; @@ -129,24 +129,27 @@ impl FactStorage { opts: Option, ) -> Result { let tx_id = tx_id_now(); - let tx_count = self - .tx_counter - .fetch_add(1, Ordering::SeqCst) - .saturating_add(1); let opts = opts.unwrap_or_default(); - let facts: Vec = fact_tuples + let mut facts: Vec = fact_tuples .into_iter() .map(|(entity, attribute, value)| { let valid_from = opts .valid_from .unwrap_or_else(|| i64::try_from(tx_id).unwrap_or(i64::MAX)); let valid_to = opts.valid_to.unwrap_or(VALID_TIME_FOREVER); - Fact::with_valid_time( - entity, attribute, value, tx_id, tx_count, valid_from, valid_to, - ) + Fact::with_valid_time(entity, attribute, value, tx_id, 0, valid_from, valid_to) }) .collect(); + // Before allocating: a rejected transaction takes no tx_count. + check_one_window_per_triple(&facts)?; + let tx_count = self + .tx_counter + .fetch_add(1, Ordering::SeqCst) + .saturating_add(1); + for fact in &mut facts { + fact.tx_count = tx_count; + } let mut d = self .data @@ -182,13 +185,9 @@ impl FactStorage { default_opts: Option, ) -> Result<(TxId, u64)> { let tx_id = tx_id_now(); - let tx_count = self - .tx_counter - .fetch_add(1, Ordering::SeqCst) - .saturating_add(1); let default_opts = default_opts.unwrap_or_default(); - let facts: Vec = fact_tuples + let mut facts: Vec = fact_tuples .into_iter() .map(|(entity, attribute, value, per_fact_opts)| { let opts = per_fact_opts.unwrap_or_else(|| default_opts.clone()); @@ -196,11 +195,18 @@ impl FactStorage { .valid_from .unwrap_or_else(|| i64::try_from(tx_id).unwrap_or(i64::MAX)); let valid_to = opts.valid_to.unwrap_or(VALID_TIME_FOREVER); - Fact::with_valid_time( - entity, attribute, value, tx_id, tx_count, valid_from, valid_to, - ) + Fact::with_valid_time(entity, attribute, value, tx_id, 0, valid_from, valid_to) }) .collect(); + // Before allocating: a rejected transaction takes no tx_count. + check_one_window_per_triple(&facts)?; + let tx_count = self + .tx_counter + .fetch_add(1, Ordering::SeqCst) + .saturating_add(1); + for fact in &mut facts { + fact.tx_count = tx_count; + } let mut d = self .data @@ -409,16 +415,20 @@ pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { /// Compute the net-asserted view of a fact set. /// -/// For each unique `(entity, attribute, value)` triple: -/// 1. Find the retraction with the highest `tx_count` (if any). -/// 2. Keep all assertions whose `tx_count` is greater than that retraction. -/// 3. Deduplicate surviving assertions by `(valid_from, valid_to)`, keeping the -/// one with the highest `tx_count` for each validity window. +/// For each unique `(entity, attribute, value)` triple (#435): +/// 1. Find its latest assertion by `tx_count` and its latest retraction. +/// 2. If the assertion is newer than the retraction, keep that transaction's +/// assertion of the triple; otherwise keep nothing. +/// +/// At a given transaction time a triple has exactly one current valid-time +/// window: a later assertion replaces the window of an earlier one, which stays +/// visible through `:as-of` of the earlier transaction. Closing, extending or +/// reopening a window is a `transact` of the same triple with the new bounds; +/// a retraction withdraws the triple. /// -/// This allows the same EAV triple to be asserted at multiple non-overlapping -/// valid-time intervals (e.g., salary=$100k valid 2020–2022 AND 2024–2026). -/// A retraction still cancels all prior assertions of that triple, but -/// re-assertions after the retraction are preserved. +/// Writes reject two windows of one triple in one transaction +/// ([`check_one_window_per_triple`]). Records written before that check may +/// still hold them; all of that transaction's windows are kept then, once each. /// /// Uses [`encode_value`] for the value key to handle floating-point edge cases /// (NaN canonicalisation, ±0.0 disambiguation) consistently with the rest of @@ -430,60 +440,106 @@ pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { /// # Implementation note /// /// Hot path for every non-`:as-of` query (#323). Each value is encoded once; -/// the two group maps borrow `(entity, attribute, value_bytes)` from the input +/// the group maps borrow `(entity, attribute, value_bytes)` from the input /// instead of cloning them. They keep std's randomly keyed hasher on purpose: /// values are often untrusted text (agent memory), and a fixed-seed fast hash -/// would let crafted colliding values make every query quadratic. `by_window` stores the -/// index and `tx_count` of the winning assertion per validity window; survivors -/// are moved out of `facts` at the end, preserving input order. +/// would let crafted colliding values make every query quadratic. `latest` +/// stores the index and `tx_count` of the first latest assertion per triple, +/// and whether another assertion ties with it; only tied triples take a second +/// pass. Survivors are moved out of `facts` at the end, preserving input order. /// -/// Idempotent under duplicated input records (a duplicate assertion ties with -/// the original and loses; a duplicate retraction leaves the max unchanged). +/// Idempotent under duplicated input records (a duplicate assertion is kept +/// once per window; a duplicate retraction leaves the max unchanged). /// `selective_fact_fetch` relies on this instead of deduplicating. pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { - use std::collections::HashMap; + use std::collections::{HashMap, HashSet}; type EavKey<'a> = (&'a EntityId, &'a str, &'a [u8]); type WindowKey<'a> = (&'a EntityId, &'a str, &'a [u8], i64, i64); + /// The first latest assertion of a triple. + struct Latest { + idx: usize, + tx_count: u64, + tied: bool, + } + let encoded: Vec> = facts.iter().map(|f| encode_value(&f.value)).collect(); let mut keep = vec![false; facts.len()]; { let mut max_retract_tx: HashMap, u64> = HashMap::new(); - let mut by_window: HashMap, (usize, u64)> = HashMap::new(); + let mut latest: HashMap, Latest> = HashMap::new(); for (idx, (fact, value_bytes)) in facts.iter().zip(encoded.iter()).enumerate() { - let entity = &fact.entity; - let attribute = fact.attribute.as_str(); - let value = value_bytes.as_slice(); + let key = ( + &fact.entity, + fact.attribute.as_str(), + value_bytes.as_slice(), + ); if fact.asserted { - by_window - .entry((entity, attribute, value, fact.valid_from, fact.valid_to)) + latest + .entry(key) .and_modify(|winner| { - if fact.tx_count > winner.1 { - *winner = (idx, fact.tx_count); + if fact.tx_count > winner.tx_count { + *winner = Latest { + idx, + tx_count: fact.tx_count, + tied: false, + }; + } else if fact.tx_count == winner.tx_count { + winner.tied = true; } }) - .or_insert((idx, fact.tx_count)); + .or_insert(Latest { + idx, + tx_count: fact.tx_count, + tied: false, + }); } else { max_retract_tx - .entry((entity, attribute, value)) + .entry(key) .and_modify(|max_tx| *max_tx = (*max_tx).max(fact.tx_count)) .or_insert(fact.tx_count); } } - for ((entity, attribute, value, _, _), (idx, tx_count)) in &by_window { - let retract_tx = max_retract_tx - .get(&(*entity, *attribute, *value)) - .copied() - .unwrap_or(0); - if *tx_count > retract_tx - && let Some(slot) = keep.get_mut(*idx) - { + let mut any_tied = false; + latest.retain(|key, winner| { + let retract_tx = max_retract_tx.get(key).copied().unwrap_or(0); + if winner.tx_count <= retract_tx { + return false; + } + if winner.tied { + any_tied = true; + return true; + } + if let Some(slot) = keep.get_mut(winner.idx) { *slot = true; } + false + }); + + // Tied triples (several records of the latest transaction): keep each + // window of that transaction once. + if any_tied { + let mut seen: HashSet> = HashSet::new(); + for (idx, (fact, value_bytes)) in facts.iter().zip(encoded.iter()).enumerate() { + let key = ( + &fact.entity, + fact.attribute.as_str(), + value_bytes.as_slice(), + ); + if fact.asserted + && latest + .get(&key) + .is_some_and(|winner| winner.tx_count == fact.tx_count) + && seen.insert((key.0, key.1, key.2, fact.valid_from, fact.valid_to)) + && let Some(slot) = keep.get_mut(idx) + { + *slot = true; + } + } } } @@ -494,6 +550,30 @@ pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { .collect() } +/// Reject a transaction's facts if they assert one `(entity, attribute, value)` +/// with two different valid-time windows (API-011, #435): that transaction +/// would hold no single latest window for the triple. Run on stamped facts, +/// before anything is written. Identical repeats are allowed. +pub(crate) fn check_one_window_per_triple(facts: &[Fact]) -> Result<()> { + use std::collections::HashMap; + let mut windows: HashMap<(&EntityId, &str, Vec), (i64, i64)> = HashMap::new(); + for fact in facts.iter().filter(|f| f.asserted) { + let window = (fact.valid_from, fact.valid_to); + let key = ( + &fact.entity, + fact.attribute.as_str(), + encode_value(&fact.value), + ); + if windows + .insert(key, window) + .is_some_and(|prev| prev != window) + { + bail_coded!(ErrorCode::Api011, fact.attribute); + } + } + Ok(()) +} + /// The pending fact at `pos`, as indexed by `FactData::pending_indexes`. fn pending_fact(d: &FactData, pos: usize) -> Result { d.facts @@ -1586,15 +1666,15 @@ mod tests { assert_eq!(result[0].tx_count, 6); } - /// A single retraction wipes all valid-time windows of the same EAV triple, - /// not just the window that was explicitly retracted. + /// A retraction withdraws the triple whatever window its latest + /// assertion had. /// /// Timeline: /// tx=1 assert W1 (2020–2022) - /// tx=2 assert W2 (2024–2026) - /// tx=3 retract → both windows must disappear + /// tx=2 assert W2 (2024–) → replaces W1 + /// tx=3 retract → nothing live #[test] - fn test_net_asserted_retraction_wipes_all_windows() { + fn test_net_asserted_retraction_withdraws_triple() { let entity = uuid::Uuid::new_v4(); let attr = ":salary"; let value = Value::Integer(100_000); @@ -1620,67 +1700,152 @@ mod tests { ]; let result = net_asserted_facts(facts); - assert_eq!( - result.len(), - 0, - "retraction should wipe all windows for the EAV triple" + assert_eq!(result.len(), 0, "retraction withdraws the triple"); + } + + /// A later assertion replaces the window of an earlier one (#435). + #[test] + fn test_net_asserted_later_window_replaces_earlier() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let facts = vec![ + make_assert(entity, ":a", value.clone(), 1, 1_000, 2_000), + make_assert(entity, ":a", value.clone(), 2, 5_000, VALID_TIME_FOREVER), + ]; + let result = net_asserted_facts(facts); + assert_eq!(result.len(), 1, "one window per triple"); + assert_eq!(result[0].tx_count, 2); + assert_eq!(result[0].valid_from, 5_000); + } + + /// Closing an open window: `[vf, ∞)` then `[vf, D)` leaves only the + /// bounded window live (#435). + #[test] + fn test_net_asserted_closing_window() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let facts = vec![ + make_assert(entity, ":a", value.clone(), 1, 1_000, VALID_TIME_FOREVER), + make_assert(entity, ":a", value.clone(), 2, 1_000, 3_000), + ]; + let result = net_asserted_facts(facts); + assert_eq!(result.len(), 1, "one window per triple"); + assert_eq!(result[0].valid_to, 3_000); + } + + /// Records written before API-011 can hold two windows of one triple in + /// one transaction; both stay live, once each, in input order. + #[test] + fn test_net_asserted_legacy_same_tx_windows_kept() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let older = make_assert(entity, ":a", value.clone(), 1, 0, VALID_TIME_FOREVER); + let w1 = make_assert(entity, ":a", value.clone(), 2, 1_000, 2_000); + let w2 = make_assert(entity, ":a", value.clone(), 2, 5_000, 6_000); + let facts = vec![older, w1.clone(), w2.clone(), w1.clone()]; + let result = net_asserted_facts(facts); + assert_eq!(result.len(), 2, "both windows of tx 2, once each"); + assert_eq!(result[0].valid_from, 1_000); + assert_eq!(result[1].valid_from, 5_000); + } + + /// A retraction in the triple's latest transaction hides that + /// transaction's assertion too. + #[test] + fn test_net_asserted_same_tx_retraction_hides() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let facts = vec![ + make_assert(entity, ":a", value.clone(), 1, 0, VALID_TIME_FOREVER), + make_assert(entity, ":a", value.clone(), 2, 0, VALID_TIME_FOREVER), + make_retract(entity, ":a", value.clone(), 2), + ]; + assert!(net_asserted_facts(facts).is_empty(), "retracted in tx 2"); + } + + #[test] + fn check_one_window_per_triple_rejects_two_windows() { + let entity = uuid::Uuid::new_v4(); + let value = Value::Integer(1); + let w1 = make_assert(entity, ":a", value.clone(), 1, 1_000, 2_000); + let w2 = make_assert(entity, ":a", value.clone(), 1, 5_000, 6_000); + let other_value = make_assert(entity, ":a", Value::Integer(2), 1, 5_000, 6_000); + let retraction = make_retract(entity, ":a", value.clone(), 1); + + check_one_window_per_triple(&[w1.clone(), w1.clone()]).expect("identical repeat"); + check_one_window_per_triple(&[w1.clone(), other_value]).expect("other value"); + check_one_window_per_triple(&[w1.clone(), retraction]).expect("retraction"); + let err = check_one_window_per_triple(&[w1, w2]).expect_err("two windows"); + assert_eq!(crate::error::MinigrafError::from(err).code(), "API-011"); + } + + #[test] + fn transact_batch_rejects_two_windows_without_taking_a_tx() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + let opts = |vf, vt| { + Some(TransactOptions { + valid_from: Some(vf), + valid_to: Some(vt), + }) + }; + let err = storage.transact_batch( + vec![ + (e, ":a".to_string(), Value::Integer(1), opts(1_000, 2_000)), + (e, ":a".to_string(), Value::Integer(1), opts(5_000, 6_000)), + ], + None, ); + assert!(err.is_err(), "two windows rejected"); + assert_eq!(storage.current_tx_count(), 0, "no tx_count taken"); + assert_eq!(storage.fact_count(), 0, "nothing written"); } - /// Pre-#323 implementation, kept verbatim as the oracle for the - /// randomized equivalence test. + /// Per-triple model, written for clarity: group each triple's records, + /// find its newest assertion and newest retraction, keep the newest + /// transaction's assertions (one per window) if they are newer (#435). fn net_asserted_facts_reference(facts: Vec) -> Vec { - use std::collections::HashMap; + use std::collections::BTreeMap; type EavKey = (EntityId, Attribute, Vec); - type WindowKey = (EntityId, Attribute, Vec, i64, i64); - - let mut max_retract_tx: HashMap = HashMap::new(); - let mut by_window: HashMap = HashMap::new(); - + let mut by_triple: BTreeMap> = BTreeMap::new(); for fact in facts { - let eav_key = ( + let key = ( fact.entity, fact.attribute.clone(), encode_value(&fact.value), ); + by_triple.entry(key).or_default().push(fact); + } - if fact.asserted { - let window_key = ( - eav_key.0, - eav_key.1, - eav_key.2, - fact.valid_from, - fact.valid_to, - ); - match by_window.get(&window_key) { - None => { - by_window.insert(window_key, fact); - } - Some(existing) if fact.tx_count > existing.tx_count => { - by_window.insert(window_key, fact); - } - _ => {} + let mut out = Vec::new(); + for records in by_triple.into_values() { + let newest_assert = records + .iter() + .filter(|f| f.asserted) + .map(|f| f.tx_count) + .max(); + let newest_retract = records + .iter() + .filter(|f| !f.asserted) + .map(|f| f.tx_count) + .max() + .unwrap_or(0); + let Some(tx) = newest_assert.filter(|tx| *tx > newest_retract) else { + continue; + }; + let mut windows = Vec::new(); + for f in records + .into_iter() + .filter(|f| f.asserted && f.tx_count == tx) + { + if !windows.contains(&(f.valid_from, f.valid_to)) { + windows.push((f.valid_from, f.valid_to)); + out.push(f); } - } else { - let tx_count = fact.tx_count; - max_retract_tx - .entry(eav_key) - .and_modify(|max_tx| *max_tx = (*max_tx).max(tx_count)) - .or_insert(tx_count); } } - - by_window - .into_iter() - .filter_map(|((entity, attribute, value, _, _), fact)| { - let retract_tx = max_retract_tx - .get(&(entity, attribute, value)) - .copied() - .unwrap_or(0); - (fact.tx_count > retract_tx).then_some(fact) - }) - .collect() + out } /// Order-independent comparison key for a fact set. @@ -1753,7 +1918,7 @@ mod tests { let actual = sorted_keys(&net_asserted_facts(facts)); assert_eq!( actual, expected, - "new net_asserted_facts diverged from reference" + "net_asserted_facts diverged from the per-triple model" ); } } diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 16d2cbf4af..68d2dcd41d 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -361,8 +361,8 @@ pub trait CommittedReader: Send + Sync { /// The committed facts of `scan` that survive net-assert among the /// committed records with `tx_count <= as_of` (every record when `None`): - /// for each `(e, a, v)`, the newest assertion per valid-time window that is - /// newer than every retraction (#379). + /// for each `(e, a, v)`, the assertion of its newest transaction, unless + /// that transaction holds a retraction (#379, #435). /// /// Applying `net_asserted_facts` to these plus the pending facts gives the /// same result as applying it to every record, because each pending fact is diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index c0479b458e..efcf86b736 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -1773,6 +1773,83 @@ mod tests { assert_live_reads_match(&pfs, &model, &scans, &[None, Some(now / 2)]); } + /// One window per triple on disk (#435): a later window replaces an + /// earlier one, a retraction in the newest transaction hides that + /// transaction's assertion, and records written before API-011 with two + /// windows in one transaction keep both. Committed live reads equal the + /// in-memory net-assert at every `as_of`, before and after reopen. + #[test] + fn live_reads_keep_one_transaction_per_triple() { + use crate::graph::types::{Fact, VALID_TIME_FOREVER}; + let (e1, e2, e3) = (entity(1), entity(2), entity(3)); + let rec = |e: Uuid, tx: u64, vf: i64, vt: i64, asserted: bool| { + let mut f = Fact::with_valid_time( + e, + ":d".to_string(), + Value::Integer(7), + 1_000 + tx, + tx, + vf, + vt, + ); + f.asserted = asserted; + f + }; + let history = [ + // e1: open window, then the same window closed. + rec(e1, 1, 100, VALID_TIME_FOREVER, true), + rec(e1, 2, 100, 300, true), + // e2: assertion, then assert + retract in one transaction. + rec(e2, 1, 100, VALID_TIME_FOREVER, true), + rec(e2, 3, 100, VALID_TIME_FOREVER, true), + rec(e2, 3, 0, VALID_TIME_FOREVER, false), + // e3: two windows in one transaction (pre-API-011 data). + rec(e3, 2, 100, 200, true), + rec(e3, 4, 100, 200, true), + rec(e3, 4, 500, 600, true), + ]; + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 32).unwrap(); + let model = FactStorage::new(); + for f in history { + pfs.storage().load_fact(f.clone()).unwrap(); + model.load_fact(f).unwrap(); + } + pfs.storage().restore_tx_counter().unwrap(); + pfs.mark_dirty(); + pfs.save().unwrap(); + + let attrs = vec![":d".to_string()]; + let scans = live_scans(&[e1, e2, e3], &attrs); + let as_ofs = [None, Some(1), Some(2), Some(3), Some(4)]; + assert_live_reads_match(&pfs, &model, &scans, &as_ofs); + + let live = pfs + .storage() + .get_live_facts(crate::storage::Scan::All, None) + .unwrap(); + let windows = |e: Uuid| { + let mut w: Vec<(i64, i64)> = live + .iter() + .filter(|f| f.entity == e) + .map(|f| (f.valid_from, f.valid_to)) + .collect(); + w.sort_unstable(); + w + }; + assert_eq!(windows(e1), vec![(100, 300)], "closed window replaces open"); + assert!(windows(e2).is_empty(), "same-transaction retraction hides"); + assert_eq!( + windows(e3), + vec![(100, 200), (500, 600)], + "legacy pair kept" + ); + + drop(pfs); + let pfs = PersistentFactStorage::new(mem, 32).unwrap(); + assert_live_reads_match(&pfs, &model, &scans, &as_ofs); + } + /// A point read on a triple with a long history reads a few pages, not the /// history: the retraction behind the current assertion skips the rest with /// one seek, and `as_of` enters the triple with one seek. diff --git a/src/storage/reader.rs b/src/storage/reader.rs index dab7e6d2a4..94edcdaa34 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -11,7 +11,6 @@ use crate::storage::keys::{self, Index, KeyFact}; use crate::storage::meta::MetaPage; use crate::storage::{CommittedReader, Scan, StorageBackend}; use anyhow::Result; -use std::collections::HashSet; use std::sync::{Arc, Mutex}; /// [`CommittedReader`] over one committed meta's trees. @@ -62,12 +61,12 @@ impl OnDiskReader { /// Facts of `index` entries starting with `prefix` that survive net-assert /// at `as_of`, decided on the key bytes (#379, spec §5.3). /// - /// The history of one triple is contiguous and newest first. Entries are - /// taken one transaction at a time: a transaction that holds a retraction - /// hides its own assertions and everything older in the triple. Otherwise - /// each assertion is kept if its valid-time window (`vf vt` bytes) has not - /// been seen in the triple yet. With `as_of`, entries newer than `as_of` - /// are passed over. Entries that are passed over are skipped one by one, and + /// The history of one triple is contiguous and newest first, so its first + /// transaction at or before `as_of` decides it (#435): a transaction that + /// holds a retraction hides the triple, otherwise its assertions are kept + /// (one, unless written before API-011 existed). Everything older in the + /// triple is hidden. With `as_of`, entries newer than `as_of` are passed + /// over. Entries that are passed over are skipped one by one, and /// after [`SEEK_AFTER`] of them in one triple the cursor seeks past the run, /// so a long history costs O(log) page visits while a short one costs no /// seek. Only kept entries are decoded and translated through the dictionary. @@ -85,7 +84,6 @@ impl OnDiskReader { } let mut cursor = LeafCursor::new(root, Some(prefix), &self.backend, &self.cache)?; let mut triple: Vec = Vec::new(); - let mut windows: HashSet> = HashSet::new(); let mut group = TxGroup::default(); // Entries of the current triple are hidden from here on. let mut dead = false; @@ -102,30 +100,25 @@ impl OnDiskReader { let tx = r.tx_desc()?; let new_triple = key_triple != triple.as_slice(); if new_triple { - group.flush(index, &mut windows, dict, &mut out)?; + group.flush(index, dict, &mut out)?; triple.clear(); triple.extend_from_slice(key_triple); - windows.clear(); dead = false; skipped = 0; } if as_of.is_some_and(|limit| tx > limit) { Step::Pass(None) } else { - let window = rest - .get(r.position()..rest.len().saturating_sub(1)) - .unwrap_or_default(); let retraction = k.last() == Some(&0); Step::Entry { tx, - window: window.to_vec(), key: (!retraction).then(|| k.clone()), } } } } _ => { - group.flush(index, &mut windows, dict, &mut out)?; + group.flush(index, dict, &mut out)?; return Ok(out); } }; @@ -143,21 +136,18 @@ impl OnDiskReader { cursor.seek(&target)?; } } - Step::Entry { tx, window, key } => { - if group.tx != Some(tx) { - if group.flush(index, &mut windows, dict, &mut out)? { - // The retraction hides this older entry too. - dead = true; - skipped = 1; - continue; - } - group = TxGroup { - tx: Some(tx), - ..TxGroup::default() - }; + Step::Entry { tx, key } => { + if group.tx.is_some_and(|decided| decided != tx) { + // The triple's newest transaction decided it; this + // older entry and the rest of the triple are hidden. + group.flush(index, dict, &mut out)?; + dead = true; + skipped = 1; + continue; } + group.tx = Some(tx); match key { - Some(key) => group.assertions.push((window, key)), + Some(key) => group.assertions.push(key), None => group.retracted = true, } } @@ -175,11 +165,7 @@ enum Step { /// (`0xFF`: past the whole triple), or `tx↓(as_of)` when `None`. Pass(Option), /// An entry at or before `as_of`; `key` is kept for assertions only. - Entry { - tx: u64, - window: Vec, - key: Option>, - }, + Entry { tx: u64, key: Option> }, } /// The entries of one triple with one `tx_count`. @@ -187,31 +173,25 @@ enum Step { struct TxGroup { tx: Option, retracted: bool, - /// `(vf vt bytes, key)` of each assertion. - assertions: Vec<(Vec, Vec)>, + /// Key of each assertion (distinct windows, since keys are unique). + assertions: Vec>, } impl TxGroup { - /// Emit the surviving assertions; returns true if the group held a - /// retraction (so every older entry of the triple is hidden too). Resets - /// the group. + /// Emit the group's assertions unless it holds a retraction, and reset it. fn flush( &mut self, index: Index, - windows: &mut HashSet>, dict: &mut DictReader<'_>, out: &mut Vec, - ) -> Result { + ) -> Result<()> { let group = std::mem::take(self); - if group.retracted { - return Ok(true); - } - for (window, key) in group.assertions { - if windows.insert(window) { + if !group.retracted { + for key in group.assertions { out.push(dict.fact(&KeyFact::decode(index, &key)?)?); } } - Ok(false) + Ok(()) } } diff --git a/tests/bitemporal_test.rs b/tests/bitemporal_test.rs index 2a206bf138..22a137ee59 100644 --- a/tests/bitemporal_test.rs +++ b/tests/bitemporal_test.rs @@ -361,15 +361,14 @@ fn test_as_of_counter_time_travel() { } // ============================================================================ -// Regression: same EAV asserted at multiple valid-time intervals must coexist +// One current valid-time window per (e, a, v) (#435) // ============================================================================ -/// The same (entity, attribute, value) triple asserted with different valid-time -/// windows must all be visible when querying within their respective windows. -/// Previously, `net_asserted_facts` collapsed them by keeping only the latest -/// tx_count, causing earlier valid-time intervals to be silently lost. +/// The same (entity, attribute, value) triple asserted with a second +/// valid-time window replaces the first: at each transaction time the triple +/// has one current window. The earlier window stays visible through `:as-of`. #[test] -fn test_same_eav_multiple_valid_time_intervals() { +fn test_same_eav_later_valid_time_interval_replaces_earlier() { let db = Minigraf::in_memory().unwrap(); // tx_count=1: Alice earns 100000 from 2020-01-01 to 2022-01-01 @@ -378,21 +377,32 @@ fn test_same_eav_multiple_valid_time_intervals() { r#"(transact {:valid-from "2020-01-01" :valid-to "2022-01-01"} [[:alice :salary 100000]])"#, ); - // tx_count=2: Alice earns 100000 again from 2024-01-01 to 2026-01-01 + // tx_count=2: Alice earns 100000 from 2024-01-01 to 2026-01-01 exec( &db, r#"(transact {:valid-from "2024-01-01" :valid-to "2026-01-01"} [[:alice :salary 100000]])"#, ); - // Query at 2021-06-01 → should find the 2020-2022 assertion + // Now: the 2020-2022 window was replaced at tx 2 let rows_2021 = result_rows(exec( &db, r#"(query [:find ?v :valid-at "2021-06-01" :where [:alice :salary ?v]])"#, )); - assert_eq!(rows_2021.len(), 1, "salary visible at 2021-06-01"); - assert_eq!(rows_2021[0][0], Value::Integer(100000)); + assert_eq!(rows_2021.len(), 0, "earlier window replaced"); - // Query at 2025-01-01 → should find the 2024-2026 assertion + // As of tx 1, the 2020-2022 window is still the current one + let rows_2021_as_of_1 = result_rows(exec( + &db, + r#"(query [:find ?v :as-of 1 :valid-at "2021-06-01" :where [:alice :salary ?v]])"#, + )); + assert_eq!( + rows_2021_as_of_1.len(), + 1, + "earlier window visible as of tx 1" + ); + assert_eq!(rows_2021_as_of_1[0][0], Value::Integer(100000)); + + // Query at 2025-01-01 → the 2024-2026 window let rows_2025 = result_rows(exec( &db, r#"(query [:find ?v :valid-at "2025-01-01" :where [:alice :salary ?v]])"#, @@ -400,23 +410,12 @@ fn test_same_eav_multiple_valid_time_intervals() { assert_eq!(rows_2025.len(), 1, "salary visible at 2025-01-01"); assert_eq!(rows_2025[0][0], Value::Integer(100000)); - // Query at 2023-01-01 → gap between intervals, should find nothing - let rows_2023 = result_rows(exec( - &db, - r#"(query [:find ?v :valid-at "2023-01-01" :where [:alice :salary ?v]])"#, - )); - assert_eq!(rows_2023.len(), 0, "no salary in the gap between intervals"); - - // Query with :any-valid-time → should see BOTH intervals + // Query with :any-valid-time → one window let rows_any = result_rows(exec( &db, r#"(query [:find ?v :valid-at :any-valid-time :where [:alice :salary ?v]])"#, )); - assert_eq!( - rows_any.len(), - 2, - "both valid-time intervals visible with :any-valid-time" - ); + assert_eq!(rows_any.len(), 1, "one current window per triple"); } /// Retraction still cancels all prior assertions of the same EAV, but diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index 366dc27ef2..0bbb0acba9 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -336,88 +336,81 @@ fn v7_multivalue_fixture_migrates_and_reads_correctly() { } } -/// Two valid-time stints for the *same* (entity, attribute, value) written in -/// one transaction must both be individually visible: a `:valid-at` query -/// inside the second window's range must return that stint (not the first, -/// not neither), and `:any-valid-time` must return both, on every selective -/// query path. The pre-fix `selective_fact_fetch` dedup key -/// `(entity, attribute, tx_count, asserted, value_bytes)` has no valid-time -/// component, so these two facts — same tx_count (one transact call), same -/// value bytes (`true`), same asserted flag — collapse into a single -/// arbitrary survivor in the entity-bound and attribute+join loops. A full -/// scan does not go through `selective_fact_fetch` (its patterns are not -/// selective — unbound attribute/value), so it is unaffected and serves as -/// the control. +/// Two valid-time stints for the *same* (entity, attribute, value): written +/// in one transaction they are API-011 (#435); written in two, the second +/// replaces the first, so a `:valid-at` query inside the second window returns +/// exactly one row on every selective path, the first window is visible only +/// `:as-of` tx 1, and `:any-valid-time` sees one stint. A full scan does not +/// go through `selective_fact_fetch` and serves as the control. #[test] fn multi_value_time_stints_visible_at_correct_valid_time_on_every_path() { let db = Minigraf::in_memory().unwrap(); + let err = db + .execute( + r#"(transact [[:vt/alice :employed true {:valid-from "2020-01-01" :valid-to "2021-01-01"}] [:vt/alice :employed true {:valid-from "2022-01-01" :valid-to "2023-01-01"}]])"#, + ) + .expect_err("two windows of one triple in one transaction"); + assert_eq!(err.code(), "API-011"); + // The `:note` marker's valid-time window must cover both stints' windows — - // otherwise the query's `:valid-at "2022-06-01"` filter (applied to every - // candidate fact, including the join marker) would drop `:note` itself, - // since its default valid_from is the real transaction wall-clock time. + // otherwise the query's `:valid-at` filter (applied to every candidate + // fact, including the join marker) would drop `:note` itself, since its + // default valid_from is the real transaction wall-clock time. + db.execute( + r#"(transact [[:vt/alice :employed true {:valid-from "2020-01-01" :valid-to "2021-01-01"}] [:vt/alice :note "vt" {:valid-from "2000-01-01"}]])"#, + ) + .unwrap(); db.execute( - r#"(transact [[:vt/alice :employed true {:valid-from "2020-01-01" :valid-to "2021-01-01"}] [:vt/alice :employed true {:valid-from "2022-01-01" :valid-to "2023-01-01"}] [:vt/alice :note "vt" {:valid-from "2000-01-01"}]])"#, + r#"(transact {:valid-from "2022-01-01" :valid-to "2023-01-01"} [[:vt/alice :employed true]])"#, ) .unwrap(); - // Inside the second window only: exactly one row on every path. - let eavt = rows( - db.execute(r#"(query [:find ?v :valid-at "2022-06-01" :where [:vt/alice :employed ?v]])"#) + let count = |valid_at: &str, as_of: &str| -> [usize; 3] { + let eavt = rows( + db.execute(&format!( + r#"(query [:find ?v {as_of} :valid-at {valid_at} :where [:vt/alice :employed ?v]])"# + )) .unwrap(), - ); - assert_eq!( - eavt.len(), - 1, - "entity-bound path must return the stint valid in the second window" - ); - - let aevt = rows( - db.execute( - r#"(query [:find ?v :valid-at "2022-06-01" :where [?e :employed ?v] [?e :note "vt"]])"#, ) - .unwrap(), - ); - assert_eq!( - aevt.len(), - 1, - "attribute+join path must return the stint valid in the second window" - ); - - let scan = rows( - db.execute( - r#"(query [:find ?a ?v :valid-at "2022-06-01" :where [?e ?a ?v] [?e :note "vt"]])"#, + .len(); + let aevt = rows( + db.execute(&format!( + r#"(query [:find ?v {as_of} :valid-at {valid_at} :where [?e :employed ?v] [?e :note "vt"]])"# + )) + .unwrap(), ) - .unwrap(), - ) - .into_iter() - .filter(|r| matches!(&r[0], Value::Keyword(a) if a == ":employed")) - .count(); - assert_eq!( - scan, 1, - "full scan path must return the stint valid in the second window" - ); - - // Under :any-valid-time, both stints must be visible on the selective paths. - let eavt_any = rows( - db.execute(r#"(query [:find ?v :any-valid-time :where [:vt/alice :employed ?v]])"#) + .len(); + let scan = rows( + db.execute(&format!( + r#"(query [:find ?a ?v {as_of} :valid-at {valid_at} :where [?e ?a ?v] [?e :note "vt"]])"# + )) .unwrap(), + ) + .into_iter() + .filter(|r| matches!(&r[0], Value::Keyword(a) if a == ":employed")) + .count(); + [eavt, aevt, scan] + }; + + assert_eq!( + count(r#""2022-06-01""#, ""), + [1, 1, 1], + "every path must return the stint valid in the second window" ); assert_eq!( - eavt_any.len(), - 2, - "entity-bound path must return both stints under :any-valid-time" + count(r#""2020-06-01""#, ""), + [0, 0, 0], + "the first stint was replaced at tx 2" ); - - let aevt_any = rows( - db.execute( - r#"(query [:find ?v :any-valid-time :where [?e :employed ?v] [?e :note "vt"]])"#, - ) - .unwrap(), + assert_eq!( + count(r#""2020-06-01""#, ":as-of 1"), + [1, 1, 1], + "the first stint is current as of tx 1" ); assert_eq!( - aevt_any.len(), - 2, - "attribute+join path must return both stints under :any-valid-time" + count(":any-valid-time", ""), + [1, 1, 1], + "one current stint per triple under :any-valid-time" ); } diff --git a/tests/valid_time_window_test.rs b/tests/valid_time_window_test.rs new file mode 100644 index 0000000000..6daaeac937 --- /dev/null +++ b/tests/valid_time_window_test.rs @@ -0,0 +1,230 @@ +//! One current valid-time window per `(e, a, v)` (#435). +//! +//! At transaction time N a triple has exactly one current window: the one of +//! its latest assertion at or before N that is newer than its last retraction. +//! A later assertion replaces an earlier window, which stays visible through +//! `:as-of`. Each scenario runs in memory, file-backed with every write +//! checkpointed (committed key walk), and file-backed after a reopen, through +//! an entity-bound pattern (EAVT) and an attribute scan (AEVT). +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult}; + +/// The databases each scenario runs against. +enum Mode { + Memory, + Checkpointed, + Reopened, +} + +const MODES: [Mode; 3] = [Mode::Memory, Mode::Checkpointed, Mode::Reopened]; + +/// Run `writes` in a fresh database of `mode`, then hand it to `check`. +fn with_db(mode: &Mode, writes: &[&str], check: impl Fn(&Minigraf)) { + match mode { + Mode::Memory => { + let db = Minigraf::in_memory().unwrap(); + for w in writes { + db.execute(w).unwrap(); + } + check(&db); + } + Mode::Checkpointed | Mode::Reopened => { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("w.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for w in writes { + db.execute(w).unwrap(); + db.checkpoint().unwrap(); + } + if matches!(mode, Mode::Checkpointed) { + check(&db); + return; + } + } + let db = Minigraf::open(&path).unwrap(); + check(&db); + } + } +} + +fn count(db: &Minigraf, query: &str) -> usize { + match db.execute(query).unwrap() { + QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("expected query results"), + } +} + +/// Whether `[:d/c :description "r"]` is visible at `as_of` (`""` = now) and +/// `valid_at`, checked through EAVT and AEVT; both must agree. +fn visible(db: &Minigraf, as_of: &str, valid_at: &str) -> bool { + let eavt = count( + db, + &format!( + r#"(query [:find ?v {as_of} :valid-at "{valid_at}" :where [:d/c :description ?v]])"# + ), + ); + let aevt = count( + db, + &format!( + r#"(query [:find ?e {as_of} :valid-at "{valid_at}" :where [?e :description "r"]])"# + ), + ); + assert_eq!(eavt, aevt, "EAVT and AEVT paths agree"); + assert!(eavt <= 1, "at most one window per triple"); + eavt == 1 +} + +/// The issue's table: a later bounded window replaces an earlier one. +#[test] +fn later_assertion_replaces_earlier_window() { + let writes = [ + r#"(transact {:valid-from "2020-01-01" :valid-to "2022-01-01"} [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2024-01-01"} [[:d/c :description "r"]])"#, + ]; + for mode in &MODES { + with_db(mode, &writes, |db| { + assert!(visible(db, ":as-of 1", "2021-01-01"), "tx 1 window"); + assert!(!visible(db, ":as-of 2", "2021-01-01"), "replaced at tx 2"); + assert!(visible(db, ":as-of 2", "2025-01-01"), "tx 2 window"); + assert!(!visible(db, "", "2021-01-01"), "replaced now"); + assert!(visible(db, "", "2025-01-01"), "current window"); + assert!(!visible(db, ":as-of 1", "2025-01-01"), "not yet asserted"); + }); + } +} + +/// Closing an open window is a `transact` with `:valid-to`. +#[test] +fn transact_with_valid_to_closes_open_window() { + let writes = [ + r#"(transact {:valid-from "2020-01-01"} [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2020-01-01" :valid-to "2023-01-01"} [[:d/c :description "r"]])"#, + ]; + for mode in &MODES { + with_db(mode, &writes, |db| { + assert!(visible(db, ":as-of 1", "2025-01-01"), "open before closing"); + assert!(!visible(db, "", "2025-01-01"), "closed now"); + assert!(visible(db, "", "2021-01-01"), "inside the closed window"); + }); + } +} + +/// Reopening a closed window, and extending one. +#[test] +fn transact_reopens_and_extends_window() { + let writes = [ + r#"(transact {:valid-from "2020-01-01" :valid-to "2021-01-01"} [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2020-01-01" :valid-to "2022-01-01"} [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2020-01-01"} [[:d/c :description "r"]])"#, + ]; + for mode in &MODES { + with_db(mode, &writes, |db| { + assert!(!visible(db, ":as-of 1", "2021-06-01"), "before extending"); + assert!(visible(db, ":as-of 2", "2021-06-01"), "extended"); + assert!(!visible(db, ":as-of 2", "2030-01-01"), "still bounded"); + assert!(visible(db, "", "2030-01-01"), "reopened"); + }); + } +} + +/// A retraction withdraws the triple; a later assertion brings back only +/// its own window. +#[test] +fn retraction_withdraws_then_reassertion_has_own_window() { + let writes = [ + r#"(transact {:valid-from "2020-01-01"} [[:d/c :description "r"]])"#, + r#"(retract [[:d/c :description "r"]])"#, + r#"(transact {:valid-from "2024-01-01" :valid-to "2025-01-01"} [[:d/c :description "r"]])"#, + ]; + for mode in &MODES { + with_db(mode, &writes, |db| { + assert!(!visible(db, ":as-of 2", "2021-01-01"), "retracted"); + assert!(!visible(db, "", "2021-01-01"), "old window gone"); + assert!(visible(db, "", "2024-06-01"), "new window"); + }); + } +} + +/// Two windows of one triple in one `transact` are API-011, and nothing is +/// written or counted. +#[test] +fn same_transaction_two_windows_rejected() { + for mode in &MODES { + with_db(mode, &[r#"(transact [[:d/x :n 1]])"#], |db| { + let err = db + .execute( + r#"(transact [[:d/c :description "r" {:valid-from "2020-01-01" :valid-to "2021-01-01"}] + [:d/c :description "r" {:valid-from "2024-01-01"}]])"#, + ) + .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 next transaction takes tx 2: the rejected one took none. + db.execute(r#"(transact [[:d/c :description "r"]])"#) + .unwrap(); + assert_eq!( + count( + db, + r#"(query [:find ?v :as-of 2 :valid-at :any-valid-time :where [:d/c :description ?v]])"# + ), + 1, + "next transaction is tx 2" + ); + }); + } +} + +/// Identical repeats and different values in one transaction are fine. +#[test] +fn same_transaction_repeat_or_other_value_accepted() { + let db = Minigraf::in_memory().unwrap(); + db.execute(r#"(transact [[:d/c :description "r"] [:d/c :description "r"]])"#) + .unwrap(); + db.execute( + r#"(transact [[:d/c :tag "a" {:valid-to "2030-01-01"}] [:d/c :tag "b" {:valid-from "2020-01-01"}]])"#, + ) + .unwrap(); +} + +/// Two windows of one triple across `execute` calls of one +/// `WriteTransaction` are API-011 at commit, and nothing is written. +#[test] +fn write_transaction_two_windows_rejected_at_commit() { + for mode in &MODES { + with_db(mode, &[], |db| { + let mut tx = db.begin_write().unwrap(); + tx.execute( + r#"(transact {:valid-from "2020-01-01" :valid-to "2021-01-01"} [[:d/c :description "r"]])"#, + ) + .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"); + }); + } +} + +/// Default valid-from in a `WriteTransaction` resolves to the commit time +/// for every fact, so repeating a fact without bounds is one window. +#[test] +fn write_transaction_repeat_without_bounds_accepted() { + let db = Minigraf::in_memory().unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:d/c :description "r"]])"#) + .unwrap(); + tx.execute(r#"(transact [[:d/c :description "r"]])"#) + .unwrap(); + tx.commit().unwrap(); +}