diff --git a/CHANGELOG.md b/CHANGELOG.md index a5382c12f6..872fe42b83 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -20,6 +20,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added +- **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. - **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/CLAUDE.md b/CLAUDE.md index 6e20c7f530..32b3b4f3e2 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -138,8 +138,9 @@ cargo run < demos/demo_negation.txt 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input) -6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size` +6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size` - `src/cursor.rs`: `Cursor` / `Batch` — owned, `Send` cursor returned by `Minigraf::query` and `PreparedQuery::query` (#432); answer computed at open today, shaped for streaming operators + - `src/fact_log.rs`: `FactLog` / `FactFilter` / `FactRecord` / `FactOrder` — every fact version streamed by `Minigraf::fact_log` (#430): tx order (multi-pass, bounded window) or storage order, key-level filters; an open log pins the committed generation, deferring checkpoints (`API-013`) 7. **`src/wal.rs`** — Fact-level sidecar WAL, CRC32-protected entries, crash recovery @@ -195,7 +196,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1285 tests** (1276 passing, 9 ignored; unit + integration + doc). +**1309 tests** (1300 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 b5e997ff06..1cdc5c9d43 100644 --- a/README.md +++ b/README.md @@ -66,7 +66,7 @@ v2.x gets data-integrity and security fixes for 12 months after v3.0.0 ships. Se ## Quick Start ```rust -use minigraf::{Minigraf, OpenOptions}; +use minigraf::{FactFilter, Minigraf, OpenOptions}; // Open or create a file-backed database let db = OpenOptions::new().path("myapp.graph").open()?; @@ -90,6 +90,12 @@ while let Some(batch) = cursor.next_batch(1000)? { for row in batch.rows() { /* row[0] is ?name */ } } +// Fact log — every assertion and retraction, in transaction order, without Datalog +let mut log = db.fact_log(&FactFilter::new().attribute_prefix(":person/"))?; +while let Some(batch) = log.next_batch(1000)? { + for rec in batch { /* rec.tx_count, rec.entity, rec.attribute, rec.value, rec.asserted */ } +} + // Explicit transaction — all-or-nothing let mut tx = db.begin_write()?; tx.execute(r#"(transact [[:alice :person/age 31]])"#)?; @@ -111,7 +117,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1285 tests +cargo test # run 1309 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 26e2e3c885..a427d680d8 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -68,6 +68,7 @@ Scope — format and storage integrity: Scope — query API: - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`, with the current evaluator computing the answer at open). The binding cursor objects follow. Streaming operators replace the evaluator behind the cursor in 3.x without further API changes; how operators bound their memory (spill, scratch pages in the `.graph` file, or a clear error) is still open. +- Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log defers checkpoints (`API-013` for an explicit one). Read-only open (#429) and a raw log writer (#431) complete the extract-transform-load path; the binding objects follow with #462. Scope — release-gate testing and documentation: diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 9926740986..b29d281c9c 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -168,6 +168,7 @@ with no `CodedError` anywhere in its chain. | 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-012 | Non-query command passed to query() | Database API | +| API-013 | Checkpoint while a fact log is open | 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 | @@ -2472,6 +2473,25 @@ while let Some(batch) = cursor.next_batch(1000)? { **Scenario**: Code that dispatches every command string through one function switches from `execute()` to `query()` for all of them. +### API-013 Checkpoint while a fact log is open + +**Error text**: `checkpoint deferred while {} fact log(s) are open; close them and checkpoint again` + +**Cause**: `db.fact_log()` returns a `FactLog` that reads the committed pages as they were when it opened. A checkpoint frees pages that a later checkpoint reuses, so while any fact log is open, checkpoints are deferred. Writes still succeed and stay in the WAL, and automatic checkpoints wait. `checkpoint()` or `rebuild_indexes()` with uncheckpointed writes, or `rebuild_indexes()` on a file database, returns this error. The `{}` is the number of open logs. Nothing is written. + +**Resolution**: +- Finish reading, or call `close()` on the log (dropping it is the same), then checkpoint again. +- Keep fact logs short-lived on a database that takes writes, because the WAL grows until they close. + +```rust +let mut log = db.fact_log(&FactFilter::new())?; +while let Some(batch) = log.next_batch(1000)? { /* ... */ } +log.close(); +db.checkpoint()?; +``` + +**Scenario**: A backup job streams the fact log on a thread while the application calls `checkpoint()` on a timer. + --- ## INT — Internal Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 20383c3d5c..248dad91e2 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,276 passing tests and 9 ignored tests (1,285 total) +**Result**: 1,300 passing tests and 9 ignored tests (1,309 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-07-fact-log-iterator-design.md b/docs/superpowers/specs/2026-10-07-fact-log-iterator-design.md new file mode 100644 index 0000000000..82345e2a5f --- /dev/null +++ b/docs/superpowers/specs/2026-10-07-fact-log-iterator-design.md @@ -0,0 +1,169 @@ +# Fact-log iterator (#430, v3.0.0) — design + +**Issue:** #430 (streaming fact-log iterator with full history and coarse filters). +**Branch:** `v3`. **Related:** #432 (cursor API, merged as `Cursor`), #429 (read-only +open), #431 (raw log writer), #462 (binding cursors), temporal_reasoning#378. + +## Goal + +Read every fact version in a graph (assertions and retractions, with `tx_count`, `tx_id` +and valid-time bounds) as a stream, without Datalog and with memory bounded +independently of graph size. This is the extract step of an offline migration and a +rebuild path for derived stores, such as the temporal_reasoning FTS sidecar, that does +not depend on query evaluation. + +## API + +```rust +impl Minigraf { + pub fn fact_log(&self, filter: &FactFilter) -> Result; +} + +pub struct FactRecord { // plain data, public fields + pub entity: EntityId, + pub attribute: String, + pub value: Value, + pub tx_count: u64, // what `:as-of N` compares against + pub tx_id: u64, // transaction wall-clock time (Unix ms) + pub valid_from: i64, + pub valid_to: i64, // i64::MAX = forever + pub asserted: bool, // false = retraction record +} + +#[derive(Clone, Debug, Default)] +pub struct FactFilter { /* private */ } +impl FactFilter { + pub fn new() -> Self; + pub fn attributes(self, idents: I) -> Self; // exact idents + pub fn attribute_prefix(self, prefix: &str) -> Self; // e.g. ":ingestion/"; repeatable + pub fn entities>(self, ids: I) -> Self; + pub fn tx_range(self, range: impl RangeBounds) -> Self; + pub fn order(self, order: FactOrder) -> Self; + pub fn window(self, facts: usize) -> Self; // Tx order memory bound +} + +#[non_exhaustive] +pub enum FactOrder { Tx /* default */, Storage } + +impl FactLog { // owned, Send, no lifetime + pub fn next_batch(&mut self, max: usize) -> Result>, MinigrafError>; + pub fn close(self); +} +impl Iterator for FactLog { type Item = Result; } +``` + +`FactLog` follows the shape of `Cursor`: `max == 0` is treated as 1, batches are never +empty, and `None` is the only end signal (it repeats). After an error the log is +finished. + +## Decisions + +1. **Order, chosen by the caller.** + - `FactOrder::Tx` (default): ascending `tx_count`. Within one transaction the order + is unspecified but deterministic for a given file state. Format v8 does not record + insertion order once facts are checkpointed (EAVT key order replaces it), and + transactions are sets, so `:as-of N` means the same for a consumer that copies the + records in this order. + - `FactOrder::Storage`: one pass in the order the storage reads most cheaply. Records + still carry `tx_count`. This suits consumers that sort or index the records + themselves. +2. **No tx-ordered index in v8, so Tx order is multi-pass.** The format is frozen (golden + corpus, #391). Each pass walks the selected index ranges and reads `tx↓` and the ids + from the key bytes, without decoding. It keeps the `window` smallest + `(tx_count, key)` entries greater than the last one emitted, in a bounded max-heap, + then decodes them as the consumer pulls batches. Memory is O(window) keys. The cost is + `ceil(N / window)` key scans. The default window is 262,144, so 4M facts take 16 + scans. A transaction larger than the window is split across passes at a key boundary. + Nothing is lost or repeated, because `(tx_count, key)` is a total order and keys are + unique. +3. **Snapshot and checkpoint pin.** No reader may hold an on-disk reader across two + checkpoints, because pages freed by checkpoint N are reused at N+1 (v8 spec §8.1). + `fact_log()` briefly takes the write lock, then records the current committed reader + and the length of the pending (uncheckpointed) fact list, and increments a pin count + on the shared `FactStorage`. While the pin count is above zero: + - auto-checkpoints (WAL threshold, `WriteTransaction` commit) and the checkpoint on + drop are deferred. Writes still succeed and the WAL grows. The next write after the + last log closes triggers the deferred auto-checkpoint. + - explicit `checkpoint()` and `rebuild_indexes()` fail with the new **`API-013`**, + "checkpoint deferred while {} fact log(s) are open; close them and checkpoint + again". Nothing is written. + - `verify()` and queries are unaffected. + Dropping or closing the log releases the pin. Because the pending list is cleared + only by a checkpoint and is append-only otherwise, the snapshot is exact: committed + facts of the recorded reader, then pending facts `[0, len)`. Writes that commit after + `fact_log()` returns are not seen. Taking the write lock at open also means a + transaction is never seen half-applied. This works like a SQLite WAL-mode reader. The + lock is held only during open, never for the life of the log, so the #432 decision + "no lock held for a cursor's life" still holds. +4. **Committed before pending.** Every pending fact is newer than every committed one (an + invariant `CommittedReader::live_facts` already relies on), and the pending list is in + `tx_count` order with insertion order within a transaction. Both orders therefore emit + committed facts first and pending facts after them, in list order. +5. **Filters** are optional and ANDed: the attribute filter (an exact set and prefixes, + ORed), the entity set, and the tx range. They are applied to key bytes before any + decoding. Range selection: + - With entities: EAVT, one range per known entity id. Unknown UUIDs match nothing. + - Otherwise, with exact attributes only: AEVT, one range per known attribute id. + - Otherwise: the whole of EAVT. Attribute ids are tested against the filter once each + (memoised; prefix tests translate the id through the dictionary). + Not provided, from the issue: + - **Entity ident prefix.** Keyword entities are stored as UUIDv5 hashes, so no ident + can be recovered. + - **Entity type.** It needs a join. Run a Datalog query for the UUIDs and pass them to + `entities`. + - **"Untouched ranges" for page-wise copy.** v8 trees share a dictionary and use + copy-on-write pages, so a page range is not a self-contained unit to copy. #431 + owns the write side. +6. **`FactRecord` is new public data, not `Fact`.** `Fact` is crate-private. The record's + field names follow `Fact`. #431's `LogWriter::append` will take the same type. +7. **Errors.** Called on a thread that holds a `WriteTransaction`, `fact_log()` fails + with `INT-001`, because opening needs the write lock, as `execute()` does. A page read + error mid-stream is returned by `next_batch` (or as an iterator item). In-memory + databases have only pending facts and no pin effect. +8. **Lifetime.** A log owns `Arc`s to the committed reader and the fact store. It can + outlive the `Minigraf` handle and move threads. Because of that, the backend, and + with it the file lock, stays open until the log is dropped. +9. **Out of scope:** the FFI cursor (`next_batch(n)` in the bindings, tracked with + #462), read-only open (#429) and the writer (#431). + +## Implementation + +- `src/fact_log.rs`: `FactRecord`, `FactFilter`, `FactOrder`, `FactLog`, re-exported + from `lib.rs`. Committed part: `Storage` keeps `(range index, last key)` and resumes + with `LeafCursor::seek(last ‖ 0x00)`. `Tx` keeps `after: (tx, key)`, runs a pass when + its decoded buffer is empty, and is finished when a pass returns fewer than `window` + entries. Pending part: index into the pending list, read in chunks under the read + guard. +- `CommittedReader::log_source() -> Option<&dyn LogSource>` (default `None`). + `OnDiskReader` implements `LogSource`: `last_tx()` (from the meta), `eid_of`, + `iid_of`, `ident_of`, `walk(index, prefix, after, visit)` over key bytes, and + `decode(index, keys) -> Vec` with one `DictReader`. +- `FactStorage`: `log_pins: Arc`, `pin_log() -> LogPin` (decrements on + drop), `log_pins()`, `pending_len()`, `pending_range(from, to)`, and + `committed_reader()`. +- `Minigraf`: `do_checkpoint` returns `API-013` when pinned. Auto-checkpoint call sites + skip when pinned. `rebuild_indexes` refuses when pinned. `Inner::drop` already ignores + errors. +- `API-013` is registered in `src/error.rs` and `docs/ERROR_REFERENCE.md`. + +## Tests (`tests/fact_log_test.rs`) + +- Full history: every assertion and retraction written, with the same `tx_count`, + `tx_id`, valid bounds and `asserted`, in non-decreasing `tx_count` order (Tx). + `Storage` returns the same multiset. +- The same records from an in-memory DB, a file DB with everything pending, everything + checkpointed, half checkpointed, and after reopen. +- A small `window` (2, 3) with one transaction larger than the window: no loss, no + duplicates, Tx order kept. +- Filters on committed and pending data: exact attributes, prefix, entities, tx range, + combinations, unknown attribute or entity (empty), empty range. +- Long string values (value pages) and explicit valid-time windows round-trip. +- Snapshot: a write after `fact_log()` is not seen. `checkpoint()` and + `rebuild_indexes()` fail with `API-013` while a log is open, and nothing changes. + Auto-checkpoint is deferred (the WAL still holds the entries) and happens on the first + write after close. `checkpoint()` succeeds after `close()`. +- `next_batch(0)` makes progress, batches are bounded and non-empty, and `None` repeats. + The iterator equals the batch output. +- `FactLog: Send`. A log can be consumed on another thread after the `Minigraf` is + dropped. +- `INT-001` inside a `WriteTransaction` thread. diff --git a/src/db.rs b/src/db.rs index 28d75a1efa..2a4ea18811 100644 --- a/src/db.rs +++ b/src/db.rs @@ -662,8 +662,9 @@ impl Minigraf { } // Trigger auto-checkpoint AFTER facts are in FactStorage so the - // checkpoint captures the newly written facts. - if should_checkpoint { + // checkpoint captures the newly written facts. An open fact log + // defers it; the first write after the log closes runs it (#430). + if should_checkpoint && self.inner.fact_storage.log_pins() == 0 { Minigraf::do_checkpoint(&self.inner.fact_storage, &mut ctx)?; } @@ -729,6 +730,47 @@ impl Minigraf { Cursor::from_result(self.read_executor().execute(cmd)?) } + /// Stream every fact record (assertions and retractions, with their + /// transaction and valid-time bounds) that `filter` keeps, without Datalog. + /// + /// The log reads the database as it is when this returns; writes that + /// commit later are not in it. Memory does not grow with the database: + /// [`FactOrder::Tx`](crate::FactOrder::Tx) holds at most + /// [`FactFilter::window`](crate::FactFilter::window) records, + /// [`FactOrder::Storage`](crate::FactOrder::Storage) one batch. + /// + /// While a log is open, checkpoints are deferred: writes still succeed and + /// stay in the WAL, automatic checkpoints wait, and [`checkpoint`] and + /// [`rebuild_indexes`] fail with `API-013` if they have work to do. Close + /// or drop the log (or read it to the end) to release the database. The + /// log owns what it reads, so it can outlive this handle and move to + /// another thread; the database file stays open until it is dropped. + /// + /// # Errors + /// + /// Returns an error if a `WriteTransaction` is active on **this thread** + /// (`INT-001`), or if the dictionary cannot be read. + /// + /// [`checkpoint`]: Self::checkpoint + /// [`rebuild_indexes`]: Self::rebuild_indexes + pub fn fact_log(&self, filter: &crate::FactFilter) -> Result { + self.fact_log_inner(filter).map_err(MinigrafError::from) + } + + fn fact_log_inner(&self, filter: &crate::FactFilter) -> Result { + if is_write_tx_active() { + bail_coded!(ErrorCode::Int001); + } + // Held while the log opens: no transaction is half applied and no + // checkpoint runs until the log's pin is registered. + let _ctx = self + .inner + .write_lock + .lock() + .map_err(|_| err_coded!(ErrorCode::Api001))?; + crate::FactLog::open(&self.inner.fact_storage, filter) + } + // ── Explicit transaction ────────────────────────────────────────────────── /// Begin an explicit write transaction. @@ -1407,8 +1449,9 @@ impl<'a> WriteTransaction<'a> { } // Trigger auto-checkpoint AFTER facts are in FactStorage so the - // checkpoint captures the newly written facts. - if should_checkpoint { + // checkpoint captures the newly written facts. An open fact log + // defers it; the first write after the log closes runs it (#430). + if should_checkpoint && self.inner.fact_storage.log_pins() == 0 { Minigraf::do_checkpoint(&self.inner.fact_storage, &mut self.guard)?; } } diff --git a/src/error.rs b/src/error.rs index eda4828c3f..fe4232e2a8 100644 --- a/src/error.rs +++ b/src/error.rs @@ -200,6 +200,7 @@ pub(crate) enum ErrorCode { Api010, Api011, Api012, + Api013, Int001, Int002, Int003, @@ -1150,6 +1151,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "only (query ...) commands can be opened as a cursor; got {}", ErrorCategory::Api, ), + ( + ErrorCode::Api013, + "API-013", + "checkpoint deferred while {} fact log(s) are open; close them and checkpoint again", + ErrorCategory::Api, + ), ( ErrorCode::Int001, "INT-001", @@ -1900,6 +1907,7 @@ mod tests { | ErrorCode::Api010 | ErrorCode::Api011 | ErrorCode::Api012 + | ErrorCode::Api013 | ErrorCode::Int001 | ErrorCode::Int002 | ErrorCode::Int003 @@ -2107,6 +2115,7 @@ mod tests { ErrorCode::Api010, ErrorCode::Api011, ErrorCode::Api012, + ErrorCode::Api013, ErrorCode::Int001, ErrorCode::Int002, ErrorCode::Int003, diff --git a/src/fact_log.rs b/src/fact_log.rs new file mode 100644 index 0000000000..c397f92260 --- /dev/null +++ b/src/fact_log.rs @@ -0,0 +1,545 @@ +//! Every fact version, streamed (#430). +//! +//! [`crate::Minigraf::fact_log`] returns a [`FactLog`] over the records of the +//! database (assertions and retractions, with their transaction and valid-time +//! bounds), filtered by a [`FactFilter`]. It reads the index trees directly, +//! without Datalog, and its memory does not grow with the database. +//! +//! The log reads the database as it was when it opened. While any log is open, +//! checkpoints are deferred: writes still succeed and stay in the WAL, and +//! [`crate::Minigraf::checkpoint`] fails with `API-013`. Close the log, or drop +//! it, to release the database. + +use crate::error::{ErrorCode, MinigrafError, err_coded}; +use crate::graph::storage::{FactStorage, LogPin}; +use crate::graph::types::{EntityId, Fact, Value}; +use crate::storage::keys::{self, Index}; +use crate::storage::{CommittedReader, LogSource}; +use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque}; +use std::ops::{Bound, RangeBounds}; +use std::sync::Arc; + +/// Default for [`FactFilter::window`]. +pub const DEFAULT_WINDOW: usize = 1 << 18; + +/// One record of the fact log: an assertion or a retraction. +#[derive(Debug, Clone, PartialEq)] +pub struct FactRecord { + /// The entity the fact is about. + pub entity: EntityId, + /// The attribute ident, e.g. `":person/name"`. + pub attribute: String, + /// The value. + pub value: Value, + /// The transaction counter that `:as-of N` compares against. + pub tx_count: u64, + /// The transaction's wall-clock time (Unix milliseconds). + pub tx_id: u64, + /// Start of the valid-time window (Unix milliseconds). + pub valid_from: i64, + /// End of the valid-time window (Unix milliseconds); `i64::MAX` is forever. + pub valid_to: i64, + /// `false` for a retraction record. + pub asserted: bool, +} + +impl From for FactRecord { + fn from(f: Fact) -> Self { + FactRecord { + entity: f.entity, + attribute: f.attribute, + value: f.value, + tx_count: f.tx_count, + tx_id: f.tx_id, + valid_from: f.valid_from, + valid_to: f.valid_to, + asserted: f.asserted, + } + } +} + +/// The order of a [`FactLog`]. +#[non_exhaustive] +#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)] +pub enum FactOrder { + /// Ascending `tx_count`. The order within one transaction is unspecified + /// (it is deterministic for a given file state). The storage has no index + /// in transaction order, so each [`FactFilter::window`] records cost one + /// scan of the selected index keys. + #[default] + Tx, + /// The order the storage reads most cheaply, in one scan. Records still + /// carry their `tx_count`. + Storage, +} + +/// Which records a [`FactLog`] returns, and in what order. +/// +/// Every filter is optional; the ones that are set must all match. They are +/// checked on index keys, so records they exclude are never decoded. +/// +/// ``` +/// # use minigraf::{FactFilter, FactOrder}; +/// let filter = FactFilter::new() +/// .attribute_prefix(":ingestion/") +/// .tx_range(10..=20) +/// .order(FactOrder::Storage); +/// ``` +#[derive(Debug, Clone, Default)] +pub struct FactFilter { + attributes: Option>, + prefixes: Vec, + entities: Option>, + /// Inclusive `tx_count` bounds. + tx: Option<(u64, u64)>, + order: FactOrder, + window: Option, +} + +impl FactFilter { + /// A filter that matches every record, in [`FactOrder::Tx`]. + pub fn new() -> Self { + Self::default() + } + + /// Keep records whose attribute is one of `idents`. Combined with + /// [`attribute_prefix`](Self::attribute_prefix), a record matching either + /// is kept. Calling it again adds to the set. + pub fn attributes(mut self, idents: I) -> Self + where + I: IntoIterator, + S: Into, + { + self.attributes + .get_or_insert_with(HashSet::new) + .extend(idents.into_iter().map(Into::into)); + self + } + + /// Keep records whose attribute starts with `prefix`, such as a namespace + /// (`":ingestion/"`). Calling it again adds another prefix. + pub fn attribute_prefix(mut self, prefix: &str) -> Self { + self.prefixes.push(prefix.to_string()); + self + } + + /// Keep records of the entities `ids`. Calling it again adds to the set. + pub fn entities>(mut self, ids: I) -> Self { + self.entities.get_or_insert_with(HashSet::new).extend(ids); + self + } + + /// Keep records whose `tx_count` is in `range`. + pub fn tx_range(mut self, range: impl RangeBounds) -> Self { + let lo = match range.start_bound() { + Bound::Included(&n) => Some(n), + Bound::Excluded(&n) => n.checked_add(1), + Bound::Unbounded => Some(0), + }; + let hi = match range.end_bound() { + Bound::Included(&n) => Some(n), + Bound::Excluded(&n) => n.checked_sub(1), + Bound::Unbounded => Some(u64::MAX), + }; + // An empty range is stored as `lo > hi`. + self.tx = Some(match (lo, hi) { + (Some(lo), Some(hi)) => (lo, hi), + _ => (1, 0), + }); + self + } + + /// The order of the log. Defaults to [`FactOrder::Tx`]. + pub fn order(mut self, order: FactOrder) -> Self { + self.order = order; + self + } + + /// In [`FactOrder::Tx`], the most records held in memory at once + /// (default [`DEFAULT_WINDOW`]); each window costs one scan of the + /// selected index keys. `0` is treated as 1. Not used by + /// [`FactOrder::Storage`]. + pub fn window(mut self, records: usize) -> Self { + self.window = Some(records); + self + } + + fn has_attribute_filter(&self) -> bool { + self.attributes.is_some() || !self.prefixes.is_empty() + } + + fn attribute_ok(&self, attribute: &str) -> bool { + !self.has_attribute_filter() + || self + .attributes + .as_ref() + .is_some_and(|set| set.contains(attribute)) + || self + .prefixes + .iter() + .any(|p| attribute.starts_with(p.as_str())) + } + + fn tx_ok(&self, tx: u64) -> bool { + self.tx.is_none_or(|(lo, hi)| lo <= tx && tx <= hi) + } + + fn matches(&self, f: &Fact) -> bool { + self.tx_ok(f.tx_count) + && self + .entities + .as_ref() + .is_none_or(|set| set.contains(&f.entity)) + && self.attribute_ok(&f.attribute) + } +} + +/// A forward-only stream of fact records, from [`crate::Minigraf::fact_log`]. +/// +/// Pull records with [`FactLog::next_batch`] or iterate over them. The log +/// holds the database as it was when it opened and defers checkpoints until +/// it is closed or dropped, or has returned its last record. +/// +/// ``` +/// # use minigraf::{FactFilter, Minigraf}; +/// let db = Minigraf::in_memory().unwrap(); +/// db.execute(r#"(transact [[:alice :person/name "Alice"]])"#).unwrap(); +/// db.execute(r#"(retract [[:alice :person/name "Alice"]])"#).unwrap(); +/// +/// let mut log = db.fact_log(&FactFilter::new()).unwrap(); +/// while let Some(batch) = log.next_batch(1000).unwrap() { +/// for rec in batch { +/// println!("{} {} {}", rec.tx_count, rec.attribute, rec.asserted); +/// } +/// } +/// ``` +pub struct FactLog { + filter: FactFilter, + committed: Option, + storage: FactStorage, + /// Next pending fact to read, and the end of the snapshot. + pending_pos: usize, + pending_end: usize, + done: bool, + pin: Option, +} + +impl std::fmt::Debug for FactLog { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct("FactLog") + .field("order", &self.filter.order) + .field("done", &self.done) + .finish_non_exhaustive() + } +} + +impl FactLog { + /// Open a log over the current state of `storage`. The caller holds the + /// write lock, so no transaction is half applied and no checkpoint runs. + pub(crate) fn open(storage: &FactStorage, filter: &FactFilter) -> anyhow::Result { + let pin = storage.pin_log(); + let (reader, pending_end) = storage.log_snapshot()?; + let committed = match reader { + Some(reader) => Committed::new(reader, filter)?, + None => None, + }; + Ok(FactLog { + filter: filter.clone(), + committed, + storage: storage.clone(), + pending_pos: 0, + pending_end, + done: false, + pin: Some(pin), + }) + } + + /// The next batch of at most `max` records, or `None` once every record + /// has been returned. A batch is never empty; `max == 0` is treated as 1. + /// + /// # Errors + /// + /// A page read error or damaged index entry. The log is finished after an + /// error. + pub fn next_batch(&mut self, max: usize) -> Result>, MinigrafError> { + if self.done { + return Ok(None); + } + match self.fill(max.max(1)) { + Ok(batch) if !batch.is_empty() => Ok(Some(batch)), + Ok(_) => { + self.finish(); + Ok(None) + } + Err(e) => { + self.finish(); + Err(e.into()) + } + } + } + + /// Stop reading and release the database. Equivalent to dropping the log. + pub fn close(self) {} + + fn finish(&mut self) { + self.done = true; + self.committed = None; + self.pin = None; + } + + fn fill(&mut self, n: usize) -> anyhow::Result> { + let mut out = Vec::new(); + if let Some(c) = &mut self.committed { + c.fill(n, &self.filter, &mut out)?; + if c.finished() { + self.committed = None; + } + } + while out.len() < n && self.pending_pos < self.pending_end { + let end = self + .pending_pos + .saturating_add(n - out.len()) + .min(self.pending_end); + let facts = self.storage.pending_range(self.pending_pos, end)?; + if facts.is_empty() { + // The snapshot ends here; nothing past it can appear. + self.pending_pos = self.pending_end; + break; + } + self.pending_pos = self.pending_pos.saturating_add(facts.len()); + out.extend( + facts + .into_iter() + .filter(|f| self.filter.matches(f)) + .map(FactRecord::from), + ); + } + Ok(out) + } +} + +impl Iterator for FactLog { + type Item = Result; + + fn next(&mut self) -> Option { + match self.next_batch(1) { + Ok(Some(batch)) => batch.into_iter().next().map(Ok), + Ok(None) => None, + Err(e) => Some(Err(e)), + } + } +} + +/// The committed part of a log: key ranges of one index in the generation the +/// log opened on. +struct Committed { + reader: Arc, + index: Index, + /// Key prefixes to walk, in ascending order. + ranges: Vec>, + /// Whether attribute ids still need checking against the filter. + check_attribute: bool, + /// The filter's answer per attribute id. + attribute_ok: HashMap, + state: State, +} + +enum State { + Storage { + range: usize, + after: Option>, + }, + Tx { + window: usize, + /// The greatest `(tx_count, key)` already taken into a window. + after: Option<(u64, Vec)>, + /// Keys of the current window, ascending, not yet returned. + buffer: VecDeque>, + /// The last window held every remaining key. + exhausted: bool, + }, +} + +impl Committed { + /// `None` when the filter leaves nothing to read in the committed part. + fn new(reader: Arc, filter: &FactFilter) -> anyhow::Result> { + let src = log_source(&reader)?; + if let Some((lo, hi)) = filter.tx + && (lo > hi || lo > src.last_tx()) + { + return Ok(None); + } + let (index, ranges, check_attribute) = if let Some(entities) = &filter.entities { + let mut eids = Vec::new(); + for e in entities { + if let Some(eid) = src.eid_of(e)? { + eids.push(eid); + } + } + eids.sort_unstable(); + let ranges = eids.into_iter().map(keys::entity_prefix).collect(); + (Index::Eavt, ranges, filter.has_attribute_filter()) + } else if let (Some(attributes), true) = (&filter.attributes, filter.prefixes.is_empty()) { + let mut iids = Vec::new(); + for a in attributes { + if let Some(iid) = src.iid_of(a)? { + iids.push(iid); + } + } + iids.sort_unstable(); + let ranges = iids.into_iter().map(keys::attribute_prefix).collect(); + (Index::Aevt, ranges, false) + } else { + (Index::Eavt, vec![Vec::new()], filter.has_attribute_filter()) + }; + if ranges.is_empty() { + return Ok(None); + } + let state = match filter.order { + FactOrder::Storage => State::Storage { + range: 0, + after: None, + }, + FactOrder::Tx => State::Tx { + window: filter.window.unwrap_or(DEFAULT_WINDOW).max(1), + after: None, + buffer: VecDeque::new(), + exhausted: false, + }, + }; + Ok(Some(Committed { + reader, + index, + ranges, + check_attribute, + attribute_ok: HashMap::new(), + state, + })) + } + + fn finished(&self) -> bool { + match &self.state { + State::Storage { range, .. } => *range >= self.ranges.len(), + State::Tx { + buffer, exhausted, .. + } => buffer.is_empty() && *exhausted, + } + } + + /// Append up to `n - out.len()` records to `out`. + fn fill( + &mut self, + n: usize, + filter: &FactFilter, + out: &mut Vec, + ) -> anyhow::Result<()> { + let src = log_source(&self.reader)?; + let index = self.index; + let check_attribute = self.check_attribute; + let memo = &mut self.attribute_ok; + // The key's tx_count if the filter keeps it. + let mut keep = |key: &[u8]| -> anyhow::Result> { + let (_, a, tx) = keys::entity_attribute_tx(index, key)?; + if !filter.tx_ok(tx) { + return Ok(None); + } + if check_attribute { + let ok = match memo.get(&a) { + Some(ok) => *ok, + None => { + let iid = u32::try_from(a) + .map_err(|_| err_coded!(ErrorCode::Int049, "iid out of range"))?; + let ok = filter.attribute_ok(&src.ident_of(iid)?); + memo.insert(a, ok); + ok + } + }; + if !ok { + return Ok(None); + } + } + Ok(Some(tx)) + }; + + match &mut self.state { + State::Storage { range, after } => { + while out.len() < n && *range < self.ranges.len() { + let want = n - out.len(); + let prefix = self.ranges.get(*range).map_or(&[][..], Vec::as_slice); + let mut taken: Vec> = Vec::new(); + src.walk(index, prefix, after.as_deref(), &mut |k| { + if keep(k)?.is_some() { + taken.push(k.to_vec()); + } + Ok(taken.len() < want) + })?; + if taken.len() < want { + *range += 1; + *after = None; + } else { + *after = taken.last().cloned(); + } + out.extend(src.decode(index, &taken)?.into_iter().map(FactRecord::from)); + } + } + State::Tx { + window, + after, + buffer, + exhausted, + } => { + while out.len() < n { + if buffer.is_empty() { + if *exhausted { + break; + } + // One pass: the `window` smallest (tx, key) after `after`. + let mut heap: BinaryHeap<(u64, Vec)> = BinaryHeap::new(); + for prefix in &self.ranges { + src.walk(index, prefix, None, &mut |k| { + let Some(tx) = keep(k)? else { + return Ok(true); + }; + if let Some((atx, akey)) = &*after + && (tx, k) <= (*atx, akey.as_slice()) + { + return Ok(true); + } + if heap.len() >= *window { + match heap.peek() { + Some((mtx, mkey)) if (tx, k) < (*mtx, mkey.as_slice()) => { + heap.pop(); + } + _ => return Ok(true), + } + } + heap.push((tx, k.to_vec())); + Ok(true) + })?; + } + *exhausted = heap.len() < *window; + let sorted = heap.into_sorted_vec(); + if let Some(last) = sorted.last() { + *after = Some(last.clone()); + } + buffer.extend(sorted.into_iter().map(|(_, k)| k)); + if buffer.is_empty() { + *exhausted = true; + break; + } + } + let take = (n - out.len()).min(buffer.len()); + let keys: Vec> = buffer.drain(..take).collect(); + out.extend(src.decode(index, &keys)?.into_iter().map(FactRecord::from)); + } + } + } + Ok(()) + } +} + +fn log_source(reader: &Arc) -> anyhow::Result<&dyn LogSource> { + reader + .log_source() + .ok_or_else(|| err_coded!(ErrorCode::Int049, "committed reader has no index keys")) +} diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 4b8c978ac9..2f7ac46a8c 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -6,7 +6,7 @@ use crate::query::datalog::types::AsOf; use crate::storage::index::{Indexes, encode_value}; use anyhow::Result; use std::collections::HashSet; -use std::sync::atomic::{AtomicU64, Ordering}; +use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering}; use std::sync::{Arc, RwLock}; /// Compact key for O(1) duplicate detection in `FactData::pending_keys`. @@ -89,6 +89,18 @@ pub(crate) struct FactStorage { data: Arc>, /// Monotonically incrementing batch counter — increments once per transact/retract call. tx_counter: Arc, + /// Open fact logs (#430). While above zero, no checkpoint may publish a + /// new committed generation: a log reads pages of the one it opened on. + log_pins: Arc, +} + +/// Keeps checkpoints from running while a fact log is open; released on drop. +pub(crate) struct LogPin(Arc); + +impl Drop for LogPin { + fn drop(&mut self) { + self.0.fetch_sub(1, Ordering::SeqCst); + } } impl Default for FactStorage { @@ -108,6 +120,7 @@ impl FactStorage { committed: None, })), tx_counter: Arc::new(AtomicU64::new(0)), + log_pins: Arc::new(AtomicUsize::new(0)), } } @@ -371,6 +384,41 @@ impl FactStorage { d.facts.clone() } + /// The committed reader and the number of pending facts, read together. + /// + /// The pending list is append-only between checkpoints, so with a + /// [`LogPin`] held its first `len` entries stay where they are. + pub(crate) fn log_snapshot( + &self, + ) -> Result<(Option>, usize)> { + let d = self + .data + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; + Ok((d.committed.clone(), d.facts.len())) + } + + /// Clones of the pending facts at positions `from..to` (clamped). + pub(crate) fn pending_range(&self, from: usize, to: usize) -> Result> { + let d = self + .data + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; + let to = to.min(d.facts.len()); + Ok(d.facts.get(from.min(to)..to).unwrap_or(&[]).to_vec()) + } + + /// Register an open fact log; checkpoints are refused until it is dropped. + pub(crate) fn pin_log(&self) -> LogPin { + self.log_pins.fetch_add(1, Ordering::SeqCst); + LogPin(self.log_pins.clone()) + } + + /// The number of open fact logs. + pub(crate) fn log_pins(&self) -> usize { + self.log_pins.load(Ordering::SeqCst) + } + /// Clear pending facts and pending indexes after a successful checkpoint. pub(crate) fn post_checkpoint_clear(&self) { let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); diff --git a/src/lib.rs b/src/lib.rs index 70f51255e4..39f16d0723 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -78,6 +78,8 @@ pub mod cursor; pub mod db; pub mod error; +/// Every fact version, streamed: [`FactLog`], [`FactFilter`], [`FactRecord`]. +pub mod fact_log; pub(crate) mod graph; pub(crate) mod query; /// Interactive REPL for exploring a [`Minigraf`] database from the command line. @@ -101,6 +103,7 @@ pub use graph::types::{EntityId, Value}; // Query result types pub use cursor::{Batch, Cursor}; +pub use fact_log::{FactFilter, FactLog, FactOrder, FactRecord}; pub use query::datalog::executor::QueryResult; // Bi-temporal query types diff --git a/src/storage/keys.rs b/src/storage/keys.rs index dd43e5a314..77e3ec0210 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -573,6 +573,26 @@ pub fn triple_len(index: Index, key: &[u8]) -> Result { Ok(r.position()) } +/// `(e, a, tx_count)` of an EAVT or AEVT key, read without decoding the value. +pub fn entity_attribute_tx(index: Index, key: &[u8]) -> Result<(u64, u64, u64)> { + let mut r = Reader::new(key); + let (e, a) = match index { + Index::Eavt => { + let e = r.uint()?; + (e, r.uint()?) + } + Index::Aevt => { + let a = r.uint()?; + (r.uint()?, a) + } + Index::Avet | Index::Vaet => { + bail_coded!(ErrorCode::Int049, "entity_attribute_tx: EAVT or AEVT only") + } + }; + r.skip_value()?; + Ok((e, a, r.tx_desc()?)) +} + /// Key prefix of every EAVT entry of entity `e`. pub fn entity_prefix(e: u64) -> Vec { let mut k = Vec::new(); diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 68d2dcd41d..a22ae7e2bb 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -386,6 +386,41 @@ pub trait CommittedReader: Send + Sync { .collect(); Ok(crate::graph::storage::net_asserted_facts(in_window)) } + + /// Key-level access for the fact log, if this reader has keys. + fn log_source(&self) -> Option<&dyn LogSource> { + None + } +} + +/// Key-level access to one committed generation, for the fact log (#430). +/// +/// Implemented by [`reader::OnDiskReader`]. Only EAVT and AEVT are walked. +pub trait LogSource { + /// The `last_checkpointed_tx_count` of this generation: every committed + /// fact has a `tx_count` at or below it. + fn last_tx(&self) -> u64; + /// The entity id of `entity`, if it has any committed fact. + fn eid_of(&self, entity: &crate::graph::types::EntityId) -> Result>; + /// The ident id of `ident`, if it is in the dictionary. + fn iid_of(&self, ident: &str) -> Result>; + /// The ident with id `iid`. + fn ident_of(&self, iid: u32) -> Result; + /// Visit, in key order, the keys of `index` that start with `prefix` and + /// sort after `after` (all of them when `None`), until `visit` returns false. + fn walk( + &self, + index: keys::Index, + prefix: &[u8], + after: Option<&[u8]>, + visit: &mut dyn FnMut(&[u8]) -> Result, + ) -> Result<()>; + /// Translate `index` keys back into facts. + fn decode( + &self, + index: keys::Index, + keys: &[Vec], + ) -> Result>; } /// The facts a read covers. diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index efcf86b736..db7bb289fd 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -301,6 +301,7 @@ impl PersistentFactStorage { if !self.dirty { return Ok(()); } + self.refuse_while_logs_open()?; let pending_facts = self.storage.get_pending_facts(); let m = self.meta; let next_gen = m.next_generation()?; @@ -391,6 +392,8 @@ impl PersistentFactStorage { use crate::storage::keys::{Index, KeyFact}; use std::collections::BTreeSet; + self.refuse_while_logs_open()?; + let m = self.meta; let next_gen = m.next_generation()?; let pending_facts = self.storage.get_pending_facts(); @@ -545,6 +548,15 @@ impl PersistentFactStorage { Ok(()) } + /// API-013 while a fact log is open: it reads pages of the active + /// generation, and a commit frees pages that the next one reuses (#430). + fn refuse_while_logs_open(&self) -> Result<()> { + match self.storage.log_pins() { + 0 => Ok(()), + n => Err(err_coded!(ErrorCode::Api013, n)), + } + } + /// Get a reference to the underlying fact storage pub fn storage(&self) -> &FactStorage { &self.storage diff --git a/src/storage/reader.rs b/src/storage/reader.rs index 94edcdaa34..e3f23974a1 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -3,13 +3,14 @@ //! Every index entry holds a whole fact, so a read touches only index leaves, //! the DICT pages that translate its ids, and a value page for a long string. +use crate::error::{ErrorCode, bail_coded}; use crate::graph::types::{EntityId, Fact}; use crate::storage::btree::{LeafCursor, MutexStorageBackend, prefix_scan}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, SharedDictCache}; use crate::storage::keys::{self, Index, KeyFact}; use crate::storage::meta::MetaPage; -use crate::storage::{CommittedReader, Scan, StorageBackend}; +use crate::storage::{CommittedReader, LogSource, Scan, StorageBackend}; use anyhow::Result; use std::sync::{Arc, Mutex}; @@ -20,6 +21,7 @@ pub struct OnDiskReader { eavt_root: u64, aevt_root: u64, dict_root: u64, + last_tx: u64, shared: SharedDictCache, } @@ -31,6 +33,7 @@ impl OnDiskReader { eavt_root: meta.eavt_root, aevt_root: meta.aevt_root, dict_root: meta.dict_root, + last_tx: meta.last_checkpointed_tx_count, shared: SharedDictCache::default(), } } @@ -195,7 +198,69 @@ impl TxGroup { } } +impl LogSource for OnDiskReader { + fn last_tx(&self) -> u64 { + self.last_tx + } + + fn eid_of(&self, entity: &EntityId) -> Result> { + self.dict().eid_of(entity) + } + + fn iid_of(&self, ident: &str) -> Result> { + self.dict().iid_of(ident) + } + + fn ident_of(&self, iid: u32) -> Result { + self.dict().name_of(iid) + } + + fn walk( + &self, + index: Index, + prefix: &[u8], + after: Option<&[u8]>, + visit: &mut dyn FnMut(&[u8]) -> Result, + ) -> Result<()> { + let root = match index { + Index::Eavt => self.eavt_root, + Index::Aevt => self.aevt_root, + Index::Avet | Index::Vaet => { + bail_coded!(ErrorCode::Int049, "fact log walks EAVT or AEVT only") + } + }; + if root == 0 { + return Ok(()); + } + let mut cursor = LeafCursor::new(root, Some(prefix), &self.backend, &self.cache)?; + if let Some(after) = after { + // Keys are unique, so the first key after `after` is the first one + // at or above `after ‖ 0x00`. + let mut target = after.to_vec(); + target.push(0); + cursor.seek(&target)?; + } + while let Some((k, _)) = cursor.next_ref()? { + if !k.starts_with(prefix) || !visit(k)? { + break; + } + } + Ok(()) + } + + fn decode(&self, index: Index, keys: &[Vec]) -> Result> { + let mut dict = self.dict(); + keys.iter() + .map(|k| dict.fact(&KeyFact::decode(index, k)?)) + .collect() + } +} + impl CommittedReader for OnDiskReader { + fn log_source(&self) -> Option<&dyn LogSource> { + Some(self) + } + fn live_facts(&self, scan: Scan<'_>, as_of: Option) -> Result> { let mut dict = self.dict(); let (index, root, prefix) = match scan { diff --git a/tests/fact_log_test.rs b/tests/fact_log_test.rs new file mode 100644 index 0000000000..b6e3238e76 --- /dev/null +++ b/tests/fact_log_test.rs @@ -0,0 +1,567 @@ +//! `Minigraf::fact_log` streams every fact record with its transaction and +//! valid-time bounds (#430). These tests check the records against a model of +//! the writes, in every split between checkpointed and pending facts, both +//! orders and small windows, the filters, the snapshot, and the checkpoint pin. + +use minigraf::{FactFilter, FactLog, FactOrder, FactRecord, Minigraf, OpenOptions, QueryResult}; +use std::path::Path; +use uuid::Uuid; + +const NAMES: [&str; 4] = ["e1", "e2", "e3", "e4"]; + +fn uuid(i: usize) -> Uuid { + Uuid::from_u128(0x1000 + i as u128) +} + +fn name_of(u: &Uuid) -> &'static str { + (0..NAMES.len()) + .find(|&i| uuid(i) == *u) + .map_or("?", |i| NAMES[i]) +} + +const LONG: &str = "a long string value that is stored in a value page, not in the key: \ + 0123456789abcdefghijklmnopqrstuvwxyz"; +const SALARY_FROM: i64 = 1_577_836_800_000; // 2020-01-01 +const SALARY_TO: i64 = 1_640_995_200_000; // 2022-01-01 +const BULK: usize = 20; + +/// One record as the model knows it: `(tx_count, entity, attribute, value, asserted, tx_id)`. +type Row = (u64, String, String, String, bool, u64); + +fn row(r: &FactRecord) -> Row { + ( + r.tx_count, + name_of(&r.entity).to_string(), + r.attribute.clone(), + format!("{:?}", r.value), + r.asserted, + r.tx_id, + ) +} + +fn tx_id_of(result: QueryResult) -> u64 { + match result { + QueryResult::Transacted(t) | QueryResult::Retracted(t) => t, + _ => panic!("expected a write result"), + } +} + +/// The writes, one transaction per step: `(command, records)` where each record +/// is `(entity, attribute, value as Debug, asserted)`. +fn steps() -> Vec<(String, Vec<(usize, &'static str, String, bool)>)> { + let e = |i: usize| format!("#uuid \"{}\"", uuid(i)); + let s = |v: &str| format!("String({v:?})"); + let mut steps = vec![ + ( + format!( + r#"(transact [[{} :person/name "Alice"] [{} :person/age 30] + [{} :person/name "Bob"] [{} :ingestion/src "x"]])"#, + e(0), + e(0), + e(1), + e(1) + ), + vec![ + (0, ":person/name", s("Alice"), true), + (0, ":person/age", "Integer(30)".to_string(), true), + (1, ":person/name", s("Bob"), true), + (1, ":ingestion/src", s("x"), true), + ], + ), + ( + format!( + r#"(transact [[{} :person/age 31] [{} :ingestion/batch 7] + [{} :person/active true] [{} :person/role :role/admin] + [{} :person/score 2.5]])"#, + e(0), + e(2), + e(0), + e(1), + e(1) + ), + vec![ + (0, ":person/age", "Integer(31)".to_string(), true), + (2, ":ingestion/batch", "Integer(7)".to_string(), true), + (0, ":person/active", "Boolean(true)".to_string(), true), + ( + 1, + ":person/role", + "Keyword(\":role/admin\")".to_string(), + true, + ), + (1, ":person/score", "Float(2.5)".to_string(), true), + ], + ), + ( + format!("(retract [[{} :person/age 30]])", e(0)), + vec![(0, ":person/age", "Integer(30)".to_string(), false)], + ), + ( + format!("(transact [[{} :doc/body \"{LONG}\"]])", e(2)), + vec![(2, ":doc/body", s(LONG), true)], + ), + ( + format!( + r#"(transact {{:valid-from "2020-01-01" :valid-to "2022-01-01"}} [[{} :person/salary 100]])"#, + e(1) + ), + vec![(1, ":person/salary", "Integer(100)".to_string(), true)], + ), + ]; + let bulk: String = (0..BULK) + .map(|i| format!("[{} :bulk/n {i}]", e(3))) + .collect(); + steps.push(( + format!("(transact [{bulk}])"), + (0..BULK) + .map(|i| (3, ":bulk/n", format!("Integer({i})"), true)) + .collect(), + )); + steps.push(( + format!(r#"(retract [[{} :ingestion/src "x"]])"#, e(1)), + vec![(1, ":ingestion/src", s("x"), false)], + )); + steps +} + +/// Run the steps from `from` on, checkpointing after step `checkpoint_after` +/// (1-based), and return the model rows. +fn write(db: &Minigraf, checkpoint_after: Option) -> Vec { + let mut model = Vec::new(); + for (i, (cmd, records)) in steps().into_iter().enumerate() { + let tx_id = tx_id_of(db.execute(&cmd).unwrap()); + let tx = (i + 1) as u64; + model.extend(records.into_iter().map(|(ent, a, v, asserted)| { + ( + tx, + NAMES[ent].to_string(), + a.to_string(), + v, + asserted, + tx_id, + ) + })); + if checkpoint_after == Some(i + 1) { + db.checkpoint().unwrap(); + } + } + model +} + +fn sorted(mut rows: Vec) -> Vec { + rows.sort(); + rows +} + +fn drain(log: &mut FactLog, max: usize) -> Vec { + let mut out = Vec::new(); + while let Some(batch) = log.next_batch(max).unwrap() { + assert!(!batch.is_empty(), "a batch is never empty"); + assert!(batch.len() <= max.max(1), "batch exceeds max"); + out.extend(batch); + } + assert!( + log.next_batch(max).unwrap().is_none(), + "the end stays the end" + ); + out +} + +fn read(db: &Minigraf, filter: &FactFilter, max: usize) -> Vec { + drain(&mut db.fact_log(filter).unwrap(), max) +} + +fn assert_tx_ordered(records: &[FactRecord]) { + assert!( + records.windows(2).all(|w| w[0].tx_count <= w[1].tx_count), + "records out of tx order" + ); +} + +fn file_db(path: &Path) -> Minigraf { + let opts = OpenOptions::default().wal_checkpoint_threshold(usize::MAX); + OpenOptions::path(opts, path).open().unwrap() +} + +/// Every way the history can be split between committed and pending facts. +fn layouts(dir: &Path) -> Vec<(&'static str, Minigraf, Vec)> { + let mem = Minigraf::in_memory().unwrap(); + let mem_model = write(&mem, None); + let mut out = vec![("memory", mem, mem_model)]; + for (name, cp) in [ + ("pending", None), + ("half", Some(4)), + ("committed", Some(steps().len())), + ] { + let db = file_db(&dir.join(format!("{name}.graph"))); + let model = write(&db, cp); + out.push((name, db, model)); + } + let path = dir.join("reopened.graph"); + let model = { + let db = file_db(&path); + let model = write(&db, Some(2)); + db.checkpoint().unwrap(); + model + }; + out.push(("reopened", file_db(&path), model)); + out +} + +#[test] +fn every_record_in_every_layout_order_and_window() { + let dir = tempfile::tempdir().unwrap(); + for (_name, db, model) in layouts(dir.path()) { + for window in [1, 2, 3, 7, 1000] { + for max in [1, 5, 1000] { + let records = read(&db, &FactFilter::new().window(window), max); + assert_tx_ordered(&records); + let rows: Vec = records.iter().map(row).collect(); + assert_eq!( + sorted(rows), + sorted(model.clone()), + "tx order: wrong records" + ); + } + } + for max in [1, 4, 1000] { + let filter = FactFilter::new().order(FactOrder::Storage); + let rows: Vec = read(&db, &filter, max).iter().map(row).collect(); + assert_eq!( + sorted(rows), + sorted(model.clone()), + "storage order: wrong records" + ); + } + } +} + +#[test] +fn records_are_identical_across_layouts() { + let dir = tempfile::tempdir().unwrap(); + let mut all = Vec::new(); + for (_name, db, _) in layouts(dir.path()) { + let mut recs: Vec<(u64, String, String, String, bool, Option, i64)> = + read(&db, &FactFilter::new(), 1000) + .iter() + .map(|r| { + ( + r.tx_count, + name_of(&r.entity).to_string(), + r.attribute.clone(), + format!("{:?}", r.value), + r.asserted, + // `None` for the transaction time, so layouts written + // at different times compare equal. + (r.valid_from != r.tx_id as i64).then_some(r.valid_from), + r.valid_to, + ) + }) + .collect(); + recs.sort(); + all.push(recs); + } + assert!(all.windows(2).all(|w| w[0] == w[1]), "layouts disagree"); +} + +#[test] +fn valid_time_and_long_values_round_trip() { + let dir = tempfile::tempdir().unwrap(); + for (_name, db, _) in layouts(dir.path()) { + let records = read(&db, &FactFilter::new(), 1000); + let salary = records + .iter() + .find(|r| r.attribute == ":person/salary") + .expect("salary record"); + assert_eq!(salary.valid_from, SALARY_FROM); + assert_eq!(salary.valid_to, SALARY_TO); + let name = records + .iter() + .find(|r| r.attribute == ":person/name") + .expect("name record"); + assert_eq!( + name.valid_from, name.tx_id as i64, + "default valid_from is tx time" + ); + assert_eq!(name.valid_to, i64::MAX, "default valid_to is forever"); + let body = records + .iter() + .find(|r| r.attribute == ":doc/body") + .expect("long value record"); + assert_eq!(body.value, minigraf::Value::String(LONG.to_string())); + } +} + +#[test] +fn a_transaction_larger_than_the_window_is_split_without_loss() { + let db = Minigraf::in_memory().unwrap(); + let dir = tempfile::tempdir().unwrap(); + let file = file_db(&dir.path().join("bulk.graph")); + for db in [&db, &file] { + write(db, None); + } + file.checkpoint().unwrap(); + for db in [&db, &file] { + let filter = FactFilter::new().attributes([":bulk/n"]).window(3); + let records = read(db, &filter, 2); + assert_eq!(records.len(), BULK); + let mut values: Vec = records.iter().map(|r| format!("{:?}", r.value)).collect(); + values.sort(); + values.dedup(); + assert_eq!(values.len(), BULK, "no duplicates"); + } +} + +fn check_filter(filter: FactFilter, keep: impl Fn(&Row) -> bool) { + let dir = tempfile::tempdir().unwrap(); + for (_name, db, model) in layouts(dir.path()) { + let expected = sorted(model.into_iter().filter(|r| keep(r)).collect()); + for f in [ + filter.clone(), + filter.clone().window(2), + filter.clone().order(FactOrder::Storage), + ] { + let records = read(&db, &f, 3); + let rows: Vec = records.iter().map(row).collect(); + assert_eq!(sorted(rows), expected, "filtered records differ"); + } + } +} + +#[test] +fn filter_exact_attributes() { + check_filter( + FactFilter::new().attributes([":person/name", ":person/age"]), + |r| r.2 == ":person/name" || r.2 == ":person/age", + ); +} + +#[test] +fn filter_attribute_prefix() { + check_filter(FactFilter::new().attribute_prefix(":ingestion/"), |r| { + r.2.starts_with(":ingestion/") + }); +} + +#[test] +fn filter_attributes_or_prefix() { + check_filter( + FactFilter::new() + .attributes([":doc/body"]) + .attribute_prefix(":ingestion/"), + |r| r.2 == ":doc/body" || r.2.starts_with(":ingestion/"), + ); +} + +#[test] +fn filter_entities() { + check_filter(FactFilter::new().entities([uuid(0), uuid(2)]), |r| { + r.1 == "e1" || r.1 == "e3" + }); +} + +#[test] +fn filter_entities_and_attribute_prefix() { + check_filter( + FactFilter::new() + .entities([uuid(1)]) + .attribute_prefix(":person/"), + |r| r.1 == "e2" && r.2.starts_with(":person/"), + ); +} + +#[test] +fn filter_tx_ranges() { + check_filter(FactFilter::new().tx_range(2..=4), |r| { + (2..=4).contains(&r.0) + }); + check_filter(FactFilter::new().tx_range(..3), |r| r.0 < 3); + check_filter(FactFilter::new().tx_range(5..), |r| r.0 >= 5); + check_filter(FactFilter::new().tx_range(3..3), |_| false); +} + +#[test] +fn filter_tx_range_and_attributes() { + check_filter( + FactFilter::new().attributes([":person/age"]).tx_range(3..), + |r| r.2 == ":person/age" && r.0 >= 3, + ); +} + +#[test] +fn filters_on_unknown_names_match_nothing() { + check_filter(FactFilter::new().attributes([":no/such"]), |_| false); + check_filter(FactFilter::new().attribute_prefix(":no/"), |_| false); + check_filter(FactFilter::new().entities([uuid(99)]), |_| false); + check_filter(FactFilter::new().attributes(Vec::::new()), |_| { + false + }); +} + +#[test] +fn zero_max_makes_progress_and_iterator_matches_batches() { + let db = Minigraf::in_memory().unwrap(); + let model = write(&db, None); + let mut log = db.fact_log(&FactFilter::new()).unwrap(); + let first = log.next_batch(0).unwrap().expect("a record"); + assert_eq!(first.len(), 1); + let batches = read(&db, &FactFilter::new(), 4); + let iterated: Vec = db + .fact_log(&FactFilter::new()) + .unwrap() + .map(Result::unwrap) + .collect(); + assert_eq!(iterated.len(), model.len()); + assert!(iterated == batches, "iterator and batches differ"); +} + +#[test] +fn empty_database_has_no_records() { + let db = Minigraf::in_memory().unwrap(); + assert!(read(&db, &FactFilter::new(), 10).is_empty()); + let dir = tempfile::tempdir().unwrap(); + let file = file_db(&dir.path().join("empty.graph")); + assert!(read(&file, &FactFilter::new(), 10).is_empty()); +} + +#[test] +fn writes_after_open_are_not_in_the_log() { + let dir = tempfile::tempdir().unwrap(); + for (_name, db, model) in layouts(dir.path()) { + for order in [FactOrder::Tx, FactOrder::Storage] { + let before = read(&db, &FactFilter::new(), 1000).len(); + let mut log = db + .fact_log(&FactFilter::new().order(order).window(2)) + .unwrap(); + let first = log.next_batch(1).unwrap().expect("a record"); + db.execute(r#"(transact [[:late :person/name "Late"]])"#) + .unwrap(); + let mut records = first; + records.extend(drain(&mut log, 3)); + assert_eq!(records.len(), before, "late write leaked in"); + assert!(before >= model.len()); + } + } +} + +fn wal_exists(path: &Path) -> bool { + let mut p = path.as_os_str().to_owned(); + p.push(".wal"); + Path::new(&p).exists() +} + +#[test] +fn checkpoint_and_rebuild_are_api_013_while_a_log_is_open() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("pin.graph"); + let db = file_db(&path); + let model = write(&db, Some(3)); + let log = db.fact_log(&FactFilter::new()).unwrap(); + + let err = db.checkpoint().expect_err("checkpoint must be refused"); + assert_eq!(err.code(), "API-013"); + let err = db.rebuild_indexes().expect_err("rebuild must be refused"); + assert_eq!(err.code(), "API-013"); + assert!(db.verify().unwrap().is_ok(), "verify still runs"); + assert!(wal_exists(&path), "nothing was checkpointed"); + + // The refused calls left the log intact. + let records: Vec = log.map(Result::unwrap).collect(); + assert_eq!(records.len(), model.len()); + + // Reading to the end released the database. + db.checkpoint().unwrap(); + assert!(!wal_exists(&path)); + let rows: Vec = read(&db, &FactFilter::new(), 100).iter().map(row).collect(); + assert_eq!(sorted(rows), sorted(model)); +} + +#[test] +fn checkpoint_with_nothing_to_write_is_allowed_while_a_log_is_open() { + let dir = tempfile::tempdir().unwrap(); + let db = file_db(&dir.path().join("idle.graph")); + write(&db, Some(steps().len())); + let _log = db.fact_log(&FactFilter::new()).unwrap(); + db.checkpoint().unwrap(); +} + +#[test] +fn close_releases_the_database() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("close.graph"); + let db = file_db(&path); + write(&db, None); + let mut log = db.fact_log(&FactFilter::new()).unwrap(); + assert!(log.next_batch(1).unwrap().is_some()); + log.close(); + db.checkpoint().unwrap(); + assert!(!wal_exists(&path)); +} + +#[test] +fn auto_checkpoint_waits_for_the_log() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("auto.graph"); + let opts = OpenOptions::default().wal_checkpoint_threshold(2); + let db = OpenOptions::path(opts, &path).open().unwrap(); + db.execute(r#"(transact [[:a :n 1]])"#).unwrap(); + let log = db.fact_log(&FactFilter::new()).unwrap(); + for i in 2..6 { + db.execute(&format!("(transact [[:a :n {i}]])")).unwrap(); + } + assert!(wal_exists(&path), "auto-checkpoint must wait"); + drop(log); + db.execute(r#"(transact [[:a :n 6]])"#).unwrap(); + assert!( + !wal_exists(&path), + "the first write after close checkpoints" + ); + assert_eq!(read(&db, &FactFilter::new(), 100).len(), 6); +} + +#[test] +fn write_transaction_commit_defers_auto_checkpoint() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("wtx.graph"); + let opts = OpenOptions::default().wal_checkpoint_threshold(1); + let db = OpenOptions::path(opts, &path).open().unwrap(); + let log = db.fact_log(&FactFilter::new()).unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:a :n 1]])"#).unwrap(); + tx.commit().unwrap(); + assert!(wal_exists(&path), "commit's auto-checkpoint must wait"); + drop(log); + assert_eq!(read(&db, &FactFilter::new(), 100).len(), 1); +} + +#[test] +fn fact_log_on_a_write_transaction_thread_is_int_001() { + let db = Minigraf::in_memory().unwrap(); + let _tx = db.begin_write().unwrap(); + let err = db + .fact_log(&FactFilter::new()) + .expect_err("must not open inside a write transaction"); + assert_eq!(err.code(), "INT-001"); +} + +#[test] +fn log_is_send_and_outlives_the_database_handle() { + fn assert_send() {} + assert_send::(); + + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("send.graph"); + let db = file_db(&path); + let model = write(&db, Some(4)); + let log = db.fact_log(&FactFilter::new().window(2)).unwrap(); + drop(db); + let n = std::thread::spawn(move || log.map(Result::unwrap).count()) + .join() + .unwrap(); + assert_eq!(n, model.len()); + + // The pending writes were kept in the WAL and replay on the next open. + let db = file_db(&path); + let rows: Vec = read(&db, &FactFilter::new(), 100).iter().map(row).collect(); + assert_eq!(sorted(rows), sorted(model)); +}