diff --git a/CLAUDE.md b/CLAUDE.md index 48498b0164..a1cfe7e1b9 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -122,7 +122,7 @@ cargo run < demos/demo_negation.txt - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_update` (copy-on-write inserts and deletes; an emptied leaf or node leaves its parent, an emptied tree is root 0; #550) and `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - `value_pages.rs`: append-only value pages for strings over 64 bytes - - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) + - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) among the versions a `TxBound` keeps; `tx_order` (cached per reader), `last_tx_at`, `tx_runs` over the DICT's transactions (#551) - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373) - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator (skips quarantined ids), free-list chain - `pins.rs`: `Pins` / `GenerationPin` — generations held by open snapshots and the quarantine of pages checkpoints freed after them (#543) @@ -136,10 +136,10 @@ cargo run < demos/demo_negation.txt - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#.`, else PRS-081 (#594) - `parser/statement.rs`: `transact`/`retract` read one fact at a time (#550): `kind_of` dispatches on the first two tokens; one pass keeps today's error order (phases 1 tokens … 6 valid windows, the earliest phase's first error, phase 3 in today's check order); `read_statement` (pass 1) keeps at most `TX_CHUNK_FACTS` materialised facts and the offset after the last, and returns phase 5–6 errors from `Statement::facts`/`Statement::chunks` (one `Chunk` at a time; pass 2 from that offset for a larger statement); `set_tx_chunk_facts` for tests (`minigraf::__tx_chunk_facts` and `__statement_facts_high_water` under `test-oracle`). The `Parser` reads tokens on demand from a `Lexer` (`keep` off checks structure without holding it); `parse_transact`/`parse_retract` remain under `cfg(test)` for the differential tests - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 15 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) - - `executor.rs`: Query executor — temporal filter (tx-time → net-assert → valid-time), not/not-join post-filter - - `matcher.rs`: Pattern matching with variable unification; `edn_to_value`, `edn_to_entity_id` + - `executor.rs`: `DatalogExecutor` — `transact`/`retract`/`rule` commands, and every query on the engine (`open_query`, `open_rule_query`; planner errors after the pseudo-attribute check, then every predicate the query and its rules name, `QRY-007`). The executor's own query path (temporal filter → net-assert → valid-time, not/not-join post-filter, `or` branches) compiles under `cfg(any(test, feature = "test-oracle"))` only, as the engine's oracle (#551) + - `matcher.rs`: `edn_to_value`, `edn_to_entity_id`; `PatternMatcher` (oracle builds only, #551) - `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), shared by the executor and the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank` and `min`/`max`), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: partitions, sort, peers) (#547) - - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator` (repeats a stratum whose rules recurse through a `not`/`or` rule until it derives nothing new, #633), `evaluate_not_join` + - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits and their errors; for oracle builds only (#551), `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator` (repeats a stratum whose rules recurse through a `not`/`or` rule until it derives nothing new, #633), `evaluate_not_join` - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628) - `rules.rs`: `RuleRegistry` — thread-safe rule management - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper @@ -147,7 +147,7 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a rule query whose every evaluated rule body plans), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree; an engine `QRY-012` agrees with any answer). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. +3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every query also runs on the executor's query path and must agree; an engine `QRY-012` agrees with any answer; `exempt()` skips it for the answer changes of #551 spec §4, whose tests check both answers). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -212,7 +212,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1773 tests** (1759 passing, 14 ignored; unit + integration + doc). +**1779 tests** (1767 passing, 12 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/Cargo.toml b/Cargo.toml index fc4cbafea8..810916c3a2 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -86,8 +86,8 @@ default = [] # Deprecated, does nothing since v3.0.0: every build reorders query clauses # (#594, #596). Kept so that builds naming it still resolve. wasm = [] -# Run the existing executor beside the streaming engine and compare every -# answer (#473 spec §9). Tests only. +# Build the executor's query path and run it beside the streaming engine, +# comparing every answer (#473 spec §9, #551). Tests only. test-oracle = [] browser = [ "dep:wasm-bindgen", diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 4fcd8bb456..609b1c7702 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,9 +2,9 @@ ## Coverage Summary -**Verified**: 2026-10-22 with `cargo test --quiet` +**Verified**: 2026-10-23 with `cargo test --quiet` (with `--features test-oracle`: 1,782 passing, 16 ignored) -**Result**: 1,759 passing tests and 14 ignored tests (1,773 total) +**Result**: 1,767 passing tests and 12 ignored tests (1,779 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628). Tests in `tests/not_join_test.rs` check that recursion through a rule with `not`, `not-join` or `or`, directly or through another rule, returns every row along a chain, and that the `not` still removes the rows it should; evaluator unit tests check that such recursion stops at its fixpoint that `max_iterations` and `max_results` end one that does not with INT-020, and that `max_results` counts the facts every pass derives, not only the mixed rule's (#633). @@ -29,6 +29,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Fact arity** (`tests/error_codes_prs_test.rs`, 2 tests; #649): a fact of five or six elements, with or without a map 4th, fails with `PRS-108`, and a transaction holding one stores none of its facts. - **Parser tightening** (`tests/error_codes_prs_test.rs`, 10 tests; #651): `PRS-109` to `PRS-114` from their inputs (an unterminated string, a `:` with no name, `(query [])`, an empty `:find`/`:where`/`:with` in each position, an unknown query keyword with and without a value after it, a constant rule head argument); `PRS-061` for a value after each query option; `PRS-097` for a clause list headed by an operator or a variable, also inside `not`, `or` and a rule body; `PRS-105` for a rule named by a variable or an operator; `PRS-025`/`PRS-029`/`PRS-063` for an aggregate, window or expression named by a variable; the forms next to them still run (an option followed by a keyword, `(- ?n 1)`, a zero-argument rule). Thirteen new `tests/grammar/invalid/syntax/` fixtures. - **Parser vs grammar** (`src/query/datalog/parser/verifier.rs`, 4 tests; #643): about 1.07M lexical strings and 555K structural inputs at the default bound (7.6M at `MINIGRAF_GRAMMAR_BOUND=4`) checked against `tests/grammar/grammar.pest`; known drift by cause in `KNOWN_DRIFT` (none left: #650, #651 fixed), semantic codes with witnesses in `SEMANTIC`. +- **The engine runs every query** (`src/query/engine/tests.rs`, 6 tests and 2 changed; `src/query/datalog/executor.rs`, 2 tests; `src/storage/persistent_facts.rs`, 2 tests and 1 extended; `src/graph/storage.rs`, 1 test; `tests/plan_independence_test.rs`, 1 test; `tests/disjunction_test.rs`, 1 changed; #551): `:as-of` timestamps on `LogWriter` files whose `tx_id`s rise and whose `tx_id`s fall and rise, before, between, at and after each transaction, with committed, pending and staged facts, plain and rule queries; `Snapshot::tx_bound` keeps the versions the executor's `tx_id <= t` filter keeps and is a counter bound exactly when `tx_id` rises with `tx_count`; the DICT's `tx_order`, `last_tx_at` (gaps, before the first and after the last transaction) and `tx_runs` against a scan; `live_keys` under range bounds equals net-assert over the kept records on random histories; `PendingStore::first_irregular` under `push`, `extend` and `of`; nested `or`/`or-join` in branches (one reading imports the branch cannot hash) under every subplan form; expressions and `not`s with no pattern first; `not` bodies with rule invocations; magic-set head constants and constants no cell equals; every planner error's code and the error order. The two answer changes of the spec (§4) and an unknown predicate in a `not` body are checked against both the engine and the executor, with the oracle exempted. - **Statement reader** (`src/query/datalog/parser/statement.rs`, 8 tests; `tests/read_only_open_test.rs`, 1 test; #550): every `transact`/`retract` built from up to three of 34 statement tokens (balanced or not) in 10 templates, and a corpus of statements with errors in several phases (a later lexer error over an earlier structure error, a later structure error over an earlier fact error, phase 3 in today's check order, too-deep nesting inside a fact and an extra element), give the same command or error through the reader as through the whole-input parser, and the same facts or error through the write path at chunk sizes 1, 2, 3 and the default; the sequences raise 24 distinct codes and reach pass 2; pass 2 resumes just after the last kept fact; materialisation and window errors come with the facts, after `API-014` on a read-only database; the parser's `keep` flag checks structure and holds nothing; lexer offsets are byte offsets. - **Copy-on-write delete** (`src/storage/btree.rs`, 3 tests; #550): `cow_update` against a `BTreeSet` model over random insert and delete batches (samples, contiguous runs that empty leaves and subtrees, a deleted key inserted again) on trees of 0 to 60,000 keys, each step walked as `verify` walks a tree, every page of the old tree unchanged, `freed` exactly the old nodes dropped; deleting everything, front half first, gives root 0 and root 0 takes inserts again; a missing, unsorted or repeated delete, or a delete on root 0, is `INT-049`. - **Large transactions** (`src/storage/persistent_facts/large_tx.rs`, 7 tests; `src/fault_matrix.rs`, 4 tests; `src/storage/page.rs`, 2 tests; `src/storage/cache.rs`, `src/storage/btree.rs` and `statement.rs`, 4 tests; #550): a `transact`/`retract` of more than one chunk, run by `Minigraf::execute` on a file database at chunk sizes 1 to 4, stores the same records as the one-chunk path (repeats across chunks stored once, several values and windows of one attribute, shared long values, refs, keywords, transaction-level windows, retractions, pending WAL entries committed with it), returns its `tx_id`, answers `:as-of`, passes `verify`, deletes the WAL and survives reopen; another window of a triple an earlier chunk wrote (`API-011`) and a value too long for a checkpoint in a later chunk (`WAL-003`) give the one-chunk path's code and message, take no `tx_count`, write no meta and leave the WAL, and the next checkpoint writes a meta before deleting it, as the first checkpoint after an open with a WAL does; a crash before the meta write on a new file reopens through the WAL guard, and is `STG-033` without it; cursors and fact logs opened before and between chunks keep their snapshot through later checkpoints. The fault matrix injects every write and sync fault at every call of a large transaction on a file with one and with two valid meta slots, with and without a WAL beforehand. Allocator tracking and release, cache eviction, and cursor peeking have unit tests. With `test-oracle`, `tests/crash_kill_test.rs` adds a variant whose child makes most transactions large and rolls back a large statement after writing pages, and `tests/model_based_test.rs` runs at a chunk size of 2; `tests/large_transaction_acceptance_test.rs` (ignored, `test-oracle` only, nightly in `.github/workflows/smoke.yml`) holds at most 65,536 materialised facts (the default chunk) for a 1M-fact `transact` and prints peak RSS. diff --git a/docs/superpowers/plans/2026-10-23-551-executor-removal.md b/docs/superpowers/plans/2026-10-23-551-executor-removal.md new file mode 100644 index 0000000000..20eb99f994 --- /dev/null +++ b/docs/superpowers/plans/2026-10-23-551-executor-removal.md @@ -0,0 +1,172 @@ +# Executor removal (#551) — Plan + +Spec: `docs/superpowers/specs/2026-10-23-executor-removal-design.md` (merged as #714), +called "the spec" below. PRs target `v3`, merge commits. None uses a closing keyword for #473 or +#551; #551 closes by hand after PR 3. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–13: the engine runs every query (spec §3, §4) | `feat/551-engine-everywhere` | +| 2 | delete the executor's query path and the oracle, `test-hooks`, size gate (spec §5) | planned after PR 1 | +| 3 | measurement, acceptance, docs (spec §6, §7) | planned after PR 2 | + +Each PR leaves `v3` with no unused code outside `cfg(test)` and the oracle's `cfg`, and updates +the test counts. PR 1 changes `CLAUDE.md`'s module notes and the test counts only; `CHANGELOG.md` +and the docs site, with the two answer changes of spec §4, come in PR 3 (spec §7). + +The oracle stays on through PR 1: every query each step moves to the engine is also run by the +executor, and the answers must agree (`engine::oracle::check`). So each step's tests first show +the executor's answer for the shape, through the oracle, and the step then keeps it. + +## Decisions not fixed by the spec (PR 1) + +1. **No fallback by construction (replaces spec §3.6's panic).** `plan`, `plan_rules`, + `engine::open` and `engine::open_rules` return `Result`. Until step 12 their error is a + `Refusal`: `Unsupported(Cause)` (the executor still runs the query) or `Fail(anyhow::Error)` + (the query fails with that error). Each step deletes the `Cause` variants it covers. Step 12 + deletes `Unsupported` and `Refusal` with it, and with them the two fallback calls in + `open_query` (`executor.rs:532` to `execute_query_with_rules`, `executor.rs:577` to + `execute_query_on_executor`): `open_query` and `open_rule_query` then have no executor + branch, the oracle blocks are the only callers left, and `execute_query_on_executor`, `execute_query_with_rules` and everything + only they reach compile under `cfg(any(test, feature = "test-oracle"))`, as the oracle. That is + stronger than a panic in tests: no build can fall back. The release binary drops the + executor's query path in PR 1. PR 1 reports its size; the gate comes back in PR 2 as the spec + says (§5.4). +2. **Planner invariants are `INT-032`** ("query executor internal error", a catch-all for query + invariants not expected to be reachable): a slot missing after the planner added it, a + pseudo-attribute without a resolved source (the parser's PRS-081 runs first), a bare symbol + that is not a variable, a rule invocation left in a plain query's clauses, G (spec §3.2). +3. **`TxBound` replaces `as_of: Option` in the read path.** In `storage`: + `enum TxBound { All, Upto(u64), Timestamp { t: u64, committed: Arc<[(u64, u64)]> } }`, the + versions a read keeps: every one; those with `tx_count <= n`; or, for committed keys, those + whose `tx_count` is in one of the sorted, disjoint, inclusive ranges `committed`, and for + pending and staged facts those with `tx_id <= t`. It replaces `as_of` in + `KeySource::live_keys`, `OnDiskReader::live_walk` (`tx > limit` becomes + `!bound.keeps_key(tx)`), `FactStorage::pending_live`/`pending_records`/`pending_facts_of_scan` + (`bound.keeps_fact(f)`) and the engine's `ScanSpec`. `CommittedReader::live_facts` and the fact log keep + `Option` (no timestamp reaches them). +4. **Committed keys are filtered by `tx_count` ranges (deviation 1).** A committed key holds a + `tx_count`, not a `tx_id`, and the DICT holds one `tx_id` per `tx_count`: a checkpoint or + migration that meets a second one fails with `STG-037` (`dict.rs:358`), and `LogWriter` + rejects one (`log_writer.rs:154`). So for committed keys "keep a version whose `tx_id <= t`" + is "keep a version whose `tx_count` is in the set of transactions with `tx_id <= t`", and + that set, as ranges, is `committed`; net-assert runs on keys as it does for `Upto`, with no + DICT lookup per version. Pending and staged facts carry their `tx_id` and are filtered on it + directly, because nothing guarantees one `tx_id` per `tx_count` there: a read-only open of a + v7 file loads its facts as pending without the `STG-037` check + (`persistent_facts.rs:158`), and WAL replay appends each entry's facts as written. +5. **Where the bound is resolved.** The plan keeps the query's `:as-of` unresolved + (`AsOfSpec { None, Counter(u64), Timestamp(i64) }`, on `Plan` and `RulesPlan`). + `engine::open`/`open_rules` resolve it once against the snapshot (`Snapshot::tx_bound`) and + put the `TxBound` in `Ctx`; every scan of the query, its bodies and its rules read it there. + A negative timestamp keeps nothing (`Upto(0)`), as `u64::try_from(t).unwrap_or(0)` does on the + executor (`storage.rs:905`). +6. **`Snapshot::tx_bound(t)`.** + - Committed: `KeySource` gains `tx_ids_monotonic() -> Result` (one walk of the DICT + `0x05` prefix, cached in a `OnceLock` on `OnDiskReader`, so once per reader, i.e. per + generation or per large transaction's working trees), `last_tx_at(t) -> Result` + (largest `tx_count` with `tx_id <= t`, 0 if none; binary search over `1..=last_tx` with a + `LeafCursor` seek to the first DICT tx key at or above the probe, since `tx_count`s may have + gaps) and `tx_runs(t, out)` (the walk, appending ranges). + - Pending: `PendingStore` keeps `first_irregular: usize`, the first position whose fact's + `tx_id` is below the previous fact's, or differs from it within the same `tx_count` + (`usize::MAX` if none), updated by `push` and `extend`. The snapshot's pending prefix is + monotonic when `pending_len <= first_irregular`; its staged facts (one `tx_id`, one + `tx_count`) when that `tx_id` is not below the prefix's last. + - Monotonic snapshot (committed, pending, staged, and each part's first `tx_id` not below the + previous part's last): `Upto(c)`, `c` the largest `tx_count` with `tx_id <= t` over the + three, by binary search over the pending prefix (facts are in `tx_count` order). + - Otherwise `Timestamp { t, committed }`, `committed` from the DICT walk. Its ranges are + charged to the query's `Meter` (#549); a file that alternates on every transaction can need + one range per transaction. +7. **`Term::Never`.** A constant no cell can equal: an entity constant that is not a keyword or + UUID, an attribute constant that is not a keyword, a value constant of a kind `value_const` + does not take (vector, list, map). A scan with a `Never` term reads nothing. Step 9's tests + first show the executor's answer for each; any kind on which it raises an error instead gets + that error. +8. **Branches and `not` bodies are planned by `clauses`.** `runs_branch` goes, and + `Builder::anti` stops filtering clause kinds. `sub`'s correlated builder already starts from + `Source::Seed`; its hashed builder starts from `Source::Seed` when the body's first clause to + run is not a pattern. `closed` (whether a body is hashable) also counts the outer variables a + nested `or`/`or-join` reads (`optimizer::clause_ref_vars`), as it counts a nested `not-join`'s. +9. **Unknown predicates are checked at every depth, rule bodies included.** + `check_udf_predicates` walks every clause list of the query, and for a rule query every + evaluated rule's body, and raises `QRY-007` for the first unknown name in text order (query + first, then rules in `plan_rules`' predicate order). The spec says "every predicate a query + names"; a rule body's predicates are named by the query that evaluates it. +10. **Oracle exemption.** `engine::oracle::exempt()` returns a guard (`cfg(test)`/`test-oracle`) + under which `check` is skipped on this thread. Only the two answer-change tests (step 6) use + it. +11. **Head constants.** `HeadArg::Const(EdnValue)`: the entity position takes the cell + `recursive.rs`'s `entity` gives the constant (a keyword's or UUID's entity, else `QRY-013`), + the value position `Cell::of_value`. Resolved once per rule run, not per row. +12. **Readers without keys (M) are `INT-049`** at open, not a required `key_source` (deviation + 2): `MockReader` (`storage.rs:1932`) is the only one, and its tests run no query, so the + trait stays as it is. + +## Deviations from the spec (PR 1) + +1. §3.1's per-version `tx_id` filter is a `tx_count` range filter for committed keys + (decision 4); same versions kept, since the DICT holds one `tx_id` per `tx_count`. Pending + facts keep the per-version filter. Monotonic pending facts also need one `tx_id` per + `tx_count` (`first_irregular`). +2. §3.5's required `key_source` is an `INT-049` at open (decision 12). +3. §3.6's test-time panic is structural: no fallback path exists after step 12 (decision 1). +4. A third answer change (decision 9, found in step 6): an unknown predicate in a `not` or + `not-join` body is `QRY-007` at open. The executor evaluated it per body row, where it + failed, so the `not` kept every outer row. Spec §3.2's "every predicate a query names" covers + it, but §4 does not list it; PR 3's CHANGELOG lists it with the other two. +5. Decision 6 in the code: `first_irregular` also marks a falling `tx_count` (a read-only v7 + open's pending facts need not be in `tx_count` order), and `KeySource::tx_order` returns + whether the DICT's `tx_id`s rise together with the newest `(tx_count, tx_id)`, which + `last_tx_at` searches up to instead of the meta's counter. + +## PR 1 steps + +1. **Plan.** This file. +2. **`Refusal`.** `plan`/`plan_rules`/`open`/`open_rules` and the builder functions return + `Result<_, Refusal>`; every `None` today becomes `Unsupported(cause)` with the spec §2 letter, + lookups that cannot fail become `Fail(INT-032)`. `open_query` falls back on `Unsupported` + only. No answer changes: the whole suite and the oracle pass unchanged. +3. **`TxBound` in storage** (decisions 3, 6): the type, `live_walk`/`live_keys`, + `pending_live`, `first_irregular`, `tx_ids_monotonic`/`last_tx_at`/`tx_runs`, + `Snapshot::tx_bound`. Unit tests: `first_irregular` under `push`/`extend`/`of`, including two + `tx_id`s in one `tx_count` (a read-only v7 open); `last_tx_at` with + gaps, before the first and after the last transaction; `tx_runs` on alternating `tx_id`s; + each against a scan of all facts with the executor's filter. +4. **`:as-of` timestamps on the engine (A)** (decision 5): `AsOfSpec`, `Ctx`'s bound, rule + queries too. Tests: a database whose `tx_id`s rise and a `LogWriter`-built one whose `tx_id`s + fall and rise, at timestamps before, between, at and after transactions, with committed, + pending and staged facts, plain and rule queries, point and attribute scans; the counter + path is taken only on the monotonic one (operator counters); `:as-of` with a negative + timestamp. +5. **Branches (B)** (decision 8): nested `or`/`or-join` in a branch, `not` reading an + expression's variable, rule invocations in a branch of a rule body (`deep`). Tests: + `tests/plan_independence_test.rs`'s nested shapes, `tests/disjunction_test.rs`, under each + `__subplans` setting. +6. **Answer changes** (spec §4; decisions 9, 10): eager `QRY-007` at every depth; the two + exempted tests, each asserting the executor's answer (through `oracle`) and the engine's. + UDF predicates in branches (`notable`) then run on the engine. +7. **No pattern first (C, J):** `Source::Seed` for an expression before any pattern and for a + `front` left at `finish`. Tests: `one` from `rule_query_routing`, a query of `not`s only, an + expression-only `or` branch. +8. **`not` bodies (I)** (decision 8): nested `not`, `or` and `not-join` in a `not` body, in plain + and rule queries, hashed and correlated. +9. **Constants (D, E)** (decisions 7, 11): `HeadArg::Const`, `Term::Never`. Tests: + `test_608_rule_call_with_unbound_argument` on the engine, `(named "alice" ?e)` still + `QRY-013`, one per `Never` kind. +10. **Errors (F, G, H, K, L, N):** `INT-028` for an invocation of three or more arguments (the + code `rule_invocation_to_pattern` returns; the test pins what the executor reports today, + top level and in a branch); `INT-031` for an unbound `or-join` variable; `INT-022` for a head + without arguments, extra head arguments ignored; the stratification error (`INT-054`) + unchanged; `INT-025` for a `:valid-at` slot and `INT-032` for an `:as-of` slot; `INT-032` + for G with a test that the parser rejects it first (PRS-057). Error order: pseudo-attributes, + rules, unknown predicates (#473 spec §5.5), one test with all three. +11. **Readers without keys (M)** (decision 12). +12. **No fallback** (decision 1): `Refusal` and `Unsupported` go; the executor's query path moves + under the oracle's `cfg`. `rule_query_routing` and every routing test assert that every + query runs on the engine (`RUNS`). Full suite with `--features test-oracle`, clippy over all + targets and features, both wasm targets (`wasm.yml`'s commands), on the bench machine. +13. **Docs and size:** `CLAUDE.md` module notes (engine runs every query, executor path is the + oracle), test counts in `CLAUDE.md` and `docs/TEST_COVERAGE.md`; the release binary's size in + the PR description. diff --git a/src/graph/storage.rs b/src/graph/storage.rs index ef9b65a20b..3f6cdf33ca 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -2,7 +2,9 @@ use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::types::{ Attribute, EntityId, Fact, TransactOptions, TxId, VALID_TIME_FOREVER, Value, tx_id_now, }; +#[cfg(any(test, feature = "test-oracle"))] use crate::query::datalog::types::AsOf; +use crate::storage::TxBound; use crate::storage::index::{Indexes, encode_value}; use crate::storage::pins::{GenerationPin, Pins}; use anyhow::Result; @@ -49,15 +51,25 @@ struct PendingStore { /// fact sets (e.g. 1M-fact benchmark setup). keys: HashSet, indexes: Indexes, + /// The first position whose fact's `tx_count` or `tx_id` is below the + /// previous fact's, or whose `tx_id` differs from it within one + /// `tx_count`; `usize::MAX` if none (#551 plan, decision 6). Before it, + /// `tx_count` and `tx_id` rise together, so a timestamp is a counter. + first_irregular: usize, } impl PendingStore { - fn new() -> Arc> { - Arc::new(RwLock::new(PendingStore { - facts: Vec::new(), + fn empty(capacity: usize) -> Self { + PendingStore { + facts: Vec::with_capacity(capacity), keys: HashSet::new(), indexes: Indexes::new(), - })) + first_irregular: usize::MAX, + } + } + + fn new() -> Arc> { + Arc::new(RwLock::new(PendingStore::empty(0))) } /// Append `fact` unless it is already here; returns whether it was added. @@ -65,6 +77,11 @@ impl PendingStore { if !self.keys.insert(pending_key(&fact)) { return false; } + if self.first_irregular == usize::MAX + && self.facts.last().is_some_and(|p| out_of_order(p, &fact)) + { + self.first_irregular = self.facts.len(); + } self.indexes.insert(&fact, self.facts.len()); self.facts.push(fact); true @@ -73,11 +90,7 @@ impl PendingStore { /// A store of `facts`, duplicates skipped: a `WriteTransaction`'s staged /// facts for one query (#550 spec §7). fn of(facts: Vec) -> Self { - let mut store = PendingStore { - facts: Vec::with_capacity(facts.len()), - keys: HashSet::new(), - indexes: Indexes::new(), - }; + let mut store = PendingStore::empty(facts.len()); for fact in facts { store.push(fact); } @@ -89,6 +102,13 @@ impl PendingStore { fn extend(&mut self, facts: Vec) { let base = self.facts.len(); for (i, fact) in facts.iter().enumerate() { + let prev = match i.checked_sub(1) { + Some(j) => facts.get(j), + None => self.facts.last(), + }; + if self.first_irregular == usize::MAX && prev.is_some_and(|p| out_of_order(p, fact)) { + self.first_irregular = base + i; + } self.keys.insert(pending_key(fact)); self.indexes.insert(fact, base + i); } @@ -96,6 +116,14 @@ impl PendingStore { } } +/// Whether `fact`, appended after `prev`, breaks the order in which a +/// timestamp is a counter (`PendingStore::first_irregular`). +fn out_of_order(prev: &Fact, fact: &Fact) -> bool { + fact.tx_count < prev.tx_count + || fact.tx_id < prev.tx_id + || (fact.tx_count == prev.tx_count && fact.tx_id != prev.tx_id) +} + /// The state a read sees: the committed generation and the pending store /// that follows it. A checkpoint replaces all three under this lock's write /// side (#473 spec §4.1), so no read sees the new committed facts together @@ -306,6 +334,68 @@ impl Snapshot { } } + /// The versions `:as-of t` keeps in this snapshot (#551 plan, decision + /// 6): a counter bound when `tx_id` rises with `tx_count` over its + /// committed, pending and staged transactions, else a `tx_id` filter. + pub(crate) fn tx_bound(&self, t: i64) -> Result { + let Ok(t) = u64::try_from(t) else { + // Before every transaction, as `filter_facts_as_of` reads it. + return Ok(TxBound::Upto(0)); + }; + let keys = + match &self.committed { + Some(reader) => Some(reader.key_source().ok_or_else(|| { + err_coded!(ErrorCode::Int049, "a committed reader without keys") + })?), + None => None, + }; + let p = self.read_pending()?; + let len = self.view(&p).len; + let pending = p.facts.get(..len).unwrap_or(&[]); + let staged = self.staged.as_deref(); + let parts = [ + (pending, len <= p.first_irregular), + match staged { + Some(s) => (s.facts.as_slice(), s.first_irregular == usize::MAX), + None => (&[][..], true), + }, + ]; + let (mut monotonic, mut last) = match keys { + Some(k) => { + let order = k.tx_order()?; + (order.monotonic, order.last.map(|(_, tx_id)| tx_id)) + } + None => (true, None), + }; + for (facts, regular) in parts { + if let Some(first) = facts.first() { + monotonic &= regular && last.is_none_or(|l| first.tx_id >= l); + last = facts.last().map(|f| f.tx_id); + } + } + if monotonic { + let mut c = match keys { + Some(k) => k.last_tx_at(t)?, + None => 0, + }; + for (facts, _) in parts { + let n = facts.partition_point(|f| f.tx_id <= t); + if let Some(f) = n.checked_sub(1).and_then(|i| facts.get(i)) { + c = c.max(f.tx_count); + } + } + return Ok(TxBound::Upto(c)); + } + let mut committed = Vec::new(); + if let Some(k) = keys { + k.tx_runs(t, &mut committed)?; + } + Ok(TxBound::Timestamp { + t, + committed: committed.into(), + }) + } + /// Wall-clock time when the snapshot was taken (Unix ms). pub(crate) fn now(&self) -> i64 { self.now @@ -336,6 +426,7 @@ impl Snapshot { /// Every record of the snapshot (assertions and retractions): committed /// facts first, in EAVT order, then the pending facts in append order. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn all_facts(&self) -> Result> { let mut all = match &self.committed { Some(reader) => reader.all_facts()?, @@ -346,6 +437,7 @@ impl Snapshot { } /// The records of the snapshot visible as of `as_of`. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn facts_as_of(&self, as_of: &AsOf) -> Result> { Ok(filter_facts_as_of(self.all_facts()?, as_of)) } @@ -359,6 +451,7 @@ impl Snapshot { /// over every record of the scan up to `as_of` (see /// [`CommittedReader::live_facts`](crate::storage::CommittedReader::live_facts)), /// but committed history is not translated into facts. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn live_facts_of_scans( &self, scans: &[crate::storage::Scan<'_>], @@ -367,8 +460,9 @@ impl Snapshot { let p = self.read_pending()?; let view = self.view(&p); let mut facts = Vec::new(); + let bound = TxBound::of(as_of); for &scan in scans { - pending_facts_of_scan(&view, scan, as_of, &mut facts)?; + pending_facts_of_scan(&view, scan, &bound, &mut facts)?; if let Some(reader) = &self.committed { facts.extend(reader.live_facts(scan, as_of)?); } @@ -386,21 +480,21 @@ pub(crate) enum PendingResume { } impl Snapshot { - /// The pending records of `scan` in the snapshot with `tx_count <= as_of` - /// (all when `None`), assertions and retractions, in no set order. + /// The pending records of `scan` in the snapshot that `bound` keeps, + /// assertions and retractions, in no set order. pub(crate) fn pending_records( &self, scan: crate::storage::Scan<'_>, - as_of: Option, + bound: &TxBound, ) -> Result> { let p = self.read_pending()?; let mut facts = Vec::new(); - pending_facts_of_scan(&self.view(&p), scan, as_of, &mut facts)?; + pending_facts_of_scan(&self.view(&p), scan, bound, &mut facts)?; Ok(facts) } - /// The pending facts of `scan` in the snapshot that survive net-assert at - /// `as_of` among the pending records, appended to `out` in pending index + /// The pending facts of `scan` in the snapshot that survive net-assert + /// among the pending records `bound` keeps, appended to `out` in pending index /// order (EAVT, or AEVT for [`Scan::Attribute`](crate::storage::Scan)). /// /// Reads whole `(entity, attribute)` runs, so every record of a triple is @@ -411,7 +505,7 @@ impl Snapshot { pub(crate) fn pending_live( &self, scan: crate::storage::Scan<'_>, - as_of: Option, + bound: &TxBound, resume: &mut Option, max: usize, out: &mut Vec, @@ -423,7 +517,7 @@ impl Snapshot { let view = self.view(&p); let walk = RunWalk { view: &view, - as_of, + bound, max, }; let stopped = match scan { @@ -472,7 +566,7 @@ impl Snapshot { /// One call of [`Snapshot::pending_live`] over one pending index. struct RunWalk<'a> { view: &'a PendingView<'a>, - as_of: Option, + bound: &'a TxBound, max: usize, } @@ -507,7 +601,7 @@ impl<'a> RunWalk<'a> { first.get_or_insert(k); last = Some(k); let f = self.view.fact(pos)?; - if self.as_of.is_none_or(|n| f.tx_count <= n) { + if self.bound.keeps_fact(&f) { run.push(f); } } @@ -686,6 +780,7 @@ impl FactStorage { /// /// Checks for duplicate facts before loading (based on entity, attribute, value, /// valid_from, valid_to, tx_count, and asserted). + #[cfg(any(test, feature = "test-oracle", not(target_arch = "wasm32")))] pub(crate) fn load_fact(&self, fact: Fact) -> Result { self.write_pending(|p| p.push(fact)) } @@ -724,6 +819,7 @@ impl FactStorage { /// `transact()` call picks up from the right sequence number. The counter /// never moves backwards: it may already hold the file's checkpointed count, /// and when WAL replay loads no facts that count must survive (#447). + #[cfg(any(test, feature = "test-oracle", not(target_arch = "wasm32")))] pub(crate) fn restore_tx_counter(&self) -> Result<()> { let d = self .data @@ -760,6 +856,7 @@ impl FactStorage { /// Returns the complete append-only log. For current state, filter by /// asserted=true and take the most recent fact for each (E, A) pair. /// Includes both committed (on-disk) facts and pending (in-memory) facts. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn get_all_facts(&self) -> Result> { self.snapshot()?.all_facts() } @@ -777,6 +874,7 @@ impl FactStorage { /// /// Returns only facts where asserted=true. This gives you the currently /// valid facts, but includes all historical versions. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn get_asserted_facts(&self) -> Result> { let all = self.get_all_facts()?; Ok(all.into_iter().filter(|f| f.is_asserted()).collect()) @@ -897,6 +995,7 @@ impl FactStorage { /// Apply transaction-time snapshot semantics to a batch of facts. /// /// Used by `Snapshot::facts_as_of`. +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { facts .into_iter() @@ -1108,11 +1207,12 @@ impl FactStorage { } } -/// The pending facts of `scan` in `view`, up to `as_of`, appended to `facts`. +/// The pending facts of `scan` in `view` that `bound` keeps, appended to +/// `facts`. fn pending_facts_of_scan( view: &PendingView<'_>, scan: crate::storage::Scan<'_>, - as_of: Option, + bound: &TxBound, facts: &mut Vec, ) -> Result<()> { use crate::storage::Scan; @@ -1120,7 +1220,7 @@ fn pending_facts_of_scan( use std::ops::Bound::Included; let mut push = |pos: usize| -> Result<()> { let f = view.fact(pos)?; - if as_of.is_none_or(|n| f.tx_count <= n) { + if bound.keeps_fact(&f) { facts.push(f); } Ok(()) @@ -1300,6 +1400,65 @@ impl FactStorage { mod tests { use super::*; + fn fact_at(i: u128, tx_count: u64, tx_id: u64) -> Fact { + Fact { + entity: uuid::Uuid::from_u128(i + 1), + attribute: ":t/n".to_string(), + value: Value::Integer(i as i64), + tx_id, + tx_count, + valid_from: 0, + valid_to: VALID_TIME_FOREVER, + asserted: true, + } + } + + /// `first_irregular` is the first fact whose `tx_count` or `tx_id` falls, + /// or whose `tx_id` differs within one `tx_count` (#551), under `push`, + /// `extend` and `of`; a skipped duplicate does not count. + #[test] + fn first_irregular_marks_the_first_out_of_order_fact() { + let regular = [(1, 100), (1, 100), (2, 100), (3, 300), (5, 400)]; + let cases: [(&[(u64, u64)], usize); 6] = [ + (®ular, usize::MAX), + (&[(1, 100), (2, 90)], 1), + (&[(1, 100), (2, 200), (1, 200)], 2), + // Two `tx_id`s in one `tx_count`: a read-only v7 open. + (&[(1, 100), (2, 200), (2, 210), (3, 300)], 2), + (&[(2, 200), (2, 200), (3, 150), (1, 50)], 2), + (&[], usize::MAX), + ]; + for (txs, want) in cases { + let facts: Vec = txs + .iter() + .enumerate() + .map(|(i, &(c, t))| fact_at(i as u128, c, t)) + .collect(); + let mut pushed = PendingStore::empty(0); + for f in facts.clone() { + pushed.push(f); + } + assert_eq!(pushed.first_irregular, want, "push"); + assert_eq!(PendingStore::of(facts.clone()).first_irregular, want, "of"); + for split in 0..=facts.len() { + let mut extended = PendingStore::empty(0); + extended.extend(facts[..split].to_vec()); + extended.extend(facts[split..].to_vec()); + assert_eq!(extended.first_irregular, want, "extend"); + } + } + // A duplicate is not appended, so it breaks nothing. + let mut store = PendingStore::empty(0); + assert!(store.push(fact_at(0, 2, 200))); + assert!(!store.push(fact_at(0, 2, 200))); + assert!(store.push(fact_at(1, 3, 300))); + assert_eq!(store.first_irregular, usize::MAX); + // Once marked, it stays at the first break. + assert!(store.push(fact_at(2, 1, 100))); + assert!(store.push(fact_at(3, 0, 0))); + assert_eq!(store.first_irregular, 2); + } + #[test] fn test_fact_storage_transact() { use uuid::Uuid; diff --git a/src/graph/types.rs b/src/graph/types.rs index 9db81ca514..529224384c 100644 --- a/src/graph/types.rs +++ b/src/graph/types.rs @@ -293,6 +293,7 @@ pub(crate) struct Fact { impl Fact { /// Create a new asserted fact with default valid time (valid_from=tx_id, valid_to=FOREVER). + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn new(entity: EntityId, attribute: Attribute, value: Value, tx_id: TxId) -> Self { Fact { entity, @@ -348,6 +349,7 @@ impl Fact { } /// Check if this is an assertion (not a retraction) + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn is_asserted(&self) -> bool { self.asserted } diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 4c815f80ab..038e4b16b9 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -23,17 +23,28 @@ /// // Iteration 1: Apply rules, derive {A->C}, delta = {A->C} /// // Iteration 2: No new facts, delta = {}, STOP /// ``` +#[cfg(any(test, feature = "test-oracle"))] use super::functions::FunctionRegistry; +#[cfg(any(test, feature = "test-oracle"))] use super::matcher::{Bindings, PatternMatcher, edn_to_entity_id, edn_to_value}; +#[cfg(any(test, feature = "test-oracle"))] use super::rules::RuleRegistry; -use super::types::{EdnValue, Pattern, Rule, ValidAt, WhereClause}; +use super::types::{EdnValue, Pattern}; +#[cfg(any(test, feature = "test-oracle"))] +use super::types::{Rule, ValidAt, WhereClause}; use crate::error::{ErrorCode, err_coded}; +#[cfg(any(test, feature = "test-oracle"))] use crate::graph::FactStorage; +#[cfg(any(test, feature = "test-oracle"))] use crate::graph::types::{Fact, Value}; +#[cfg(any(test, feature = "test-oracle"))] use crate::storage::index::encode_value; use anyhow::Result; +#[cfg(any(test, feature = "test-oracle"))] use std::collections::BTreeSet; +#[cfg(any(test, feature = "test-oracle"))] use std::collections::HashSet; +#[cfg(any(test, feature = "test-oracle"))] use std::sync::{Arc, RwLock}; /// Default maximum iterations for recursive evaluation (kept for reference). @@ -76,6 +87,7 @@ pub(crate) fn iterations_exceeded(limit: usize) -> anyhow::Error { /// /// let derived_facts = evaluator.evaluate_recursive_rules(&["reachable"])?; /// ``` +#[cfg(any(test, feature = "test-oracle"))] pub struct RecursiveEvaluator { /// Base fact storage storage: FactStorage, @@ -91,6 +103,7 @@ pub struct RecursiveEvaluator { valid_at: Value, } +#[cfg(any(test, feature = "test-oracle"))] impl RecursiveEvaluator { /// Create a new recursive evaluator. /// @@ -100,6 +113,7 @@ impl RecursiveEvaluator { /// * `functions` - Function registry for UDF predicates/aggregates /// * `max_iterations` - Safety limit (e.g., 1000) /// * `max_derived_facts` - Maximum facts the rules may derive (base facts do not count) + #[cfg(any(test, feature = "test-oracle"))] pub fn new( storage: FactStorage, rules: Arc>, @@ -119,6 +133,7 @@ impl RecursiveEvaluator { /// Set the value a `:db/valid-at` pattern in a rule body binds: the /// query's valid time (#617). Without it the pattern binds `nil`. + #[cfg(any(test, feature = "test-oracle"))] pub fn with_valid_at(mut self, valid_at: Value) -> Self { self.valid_at = valid_at; self @@ -134,6 +149,7 @@ impl RecursiveEvaluator { /// /// # Errors /// Returns error if max iterations exceeded or evaluation fails + #[cfg(any(test, feature = "test-oracle"))] pub fn evaluate_recursive_rules(&self, predicates: &[String]) -> Result { // Start with base facts as initial delta let base_facts = self.storage.get_asserted_facts()?; @@ -202,6 +218,7 @@ impl RecursiveEvaluator { /// /// This is a single iteration of the fixed-point loop. /// It applies each rule to the current derived facts and returns newly derived facts. + #[cfg(any(test, feature = "test-oracle"))] fn evaluate_iteration( &self, predicates: &[String], @@ -233,6 +250,7 @@ impl RecursiveEvaluator { /// 1. Convert body patterns and rule invocations to Pattern structs /// 2. Use PatternMatcher to find all bindings /// 3. For each binding, instantiate rule head to create derived fact + #[cfg(any(test, feature = "test-oracle"))] fn evaluate_rule(&self, rule: &Rule, current_facts: &FactStorage) -> Result> { let mut derived = Vec::new(); @@ -311,6 +329,7 @@ impl RecursiveEvaluator { /// /// Example: (reachable ?x ?y) -> [?x :reachable ?y] /// Example: (blocked ?x) -> [?x :blocked ?_rule_value] + #[cfg(any(test, feature = "test-oracle"))] fn rule_invocation_to_pattern(&self, list: &[EdnValue]) -> Result { if list.is_empty() { return Err(err_coded!( @@ -343,6 +362,7 @@ impl RecursiveEvaluator { /// Head: (reachable ?x ?y) /// Bindings: {?x -> alice_uuid, ?y -> bob_uuid} /// Result: Fact(alice_uuid, ":reachable", Ref(bob_uuid)) + #[cfg(any(test, feature = "test-oracle"))] fn instantiate_head(&self, head: &[EdnValue], binding: &Bindings) -> Result { if head.len() < 2 { return Err(err_coded!( @@ -400,6 +420,7 @@ impl RecursiveEvaluator { } /// Substitute a variable with its binding, or return as-is if not a variable. + #[cfg(any(test, feature = "test-oracle"))] fn substitute_variable(&self, edn: &EdnValue, binding: &Bindings) -> Result { match edn { EdnValue::Symbol(s) if s.starts_with('?') => { @@ -419,12 +440,14 @@ impl RecursiveEvaluator { } /// Public version of instantiate_head for use by StratifiedEvaluator. + #[cfg(any(test, feature = "test-oracle"))] pub fn instantiate_head_public(&self, head: &[EdnValue], binding: &Bindings) -> Result { self.instantiate_head(head, binding) } } /// Convert a stored Value back to EdnValue. +#[cfg(any(test, feature = "test-oracle"))] pub fn value_to_edn(value: &Value) -> EdnValue { match value { Value::String(s) => EdnValue::String(s.clone()), @@ -473,6 +496,7 @@ pub(crate) fn rule_invocation_to_pattern(predicate: &str, args: &[EdnValue]) -> /// The outer row's values of the variables a `not` body imports: every /// variable the body names, `?_` ones aside (spec §2 of the #546 design). +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn not_seed(body: &[WhereClause], outer: &Bindings) -> Bindings { crate::query::datalog::optimizer::clause_ref_vars(body) .into_iter() @@ -487,6 +511,7 @@ pub(crate) fn not_seed(body: &[WhereClause], outer: &Bindings) -> Bindings { /// by IEEE `==`, a keyword equal to a ref to the entity it names), never /// substituted as a literal (#546). Every row carries the seed; the caller /// applies the body's expressions. +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn seeded_body_rows( body: &[WhereClause], seed: Bindings, @@ -517,6 +542,7 @@ pub(crate) fn seeded_body_rows( /// The body is matched from the binding's join variables ([`seeded_body_rows`]), /// with `valid_at` as the value a `:db/valid-at` pattern binds (#615), and its /// expressions applied; any row left means the body is satisfiable. +#[cfg(any(test, feature = "test-oracle"))] pub fn evaluate_not_join( join_vars: &[String], clauses: &[WhereClause], @@ -547,6 +573,7 @@ pub fn evaluate_not_join( /// Filter-form (`binding: None`) drops rows where the expr is not truthy or errors. /// Binding-form (`binding: Some(var)`) extends the row with the computed value, /// or keeps it only if an existing value of the variable is equal (#596). +#[cfg(any(test, feature = "test-oracle"))] fn apply_expr_clauses_in_evaluator( bindings: Vec, expr_clauses: &[&WhereClause], @@ -571,6 +598,7 @@ fn apply_expr_clauses_in_evaluator( /// Strata are evaluated in ascending order. Within each stratum, positive-only /// rules are handled by RecursiveEvaluator; rules containing `not` clauses are /// handled by an inner loop that applies `not` filters to candidate bindings. +#[cfg(any(test, feature = "test-oracle"))] pub struct StratifiedEvaluator { storage: FactStorage, rules: Arc>, @@ -583,7 +611,9 @@ pub struct StratifiedEvaluator { valid_at: Value, } +#[cfg(any(test, feature = "test-oracle"))] impl StratifiedEvaluator { + #[cfg(any(test, feature = "test-oracle"))] pub fn new( storage: FactStorage, rules: Arc>, @@ -604,12 +634,14 @@ impl StratifiedEvaluator { /// Set the value a `:db/valid-at` pattern binds in rule bodies and their /// `not` / `not-join` bodies and `or` branches: the query's `:valid-at` /// value, the current time without one, `nil` for `:any-valid-time` (#617). + #[cfg(any(test, feature = "test-oracle"))] pub fn with_valid_at(mut self, valid_at: Value) -> Self { self.valid_at = valid_at; self } /// Derive all facts for the given predicates, respecting stratification order. + #[cfg(any(test, feature = "test-oracle"))] pub fn evaluate(&self, predicates: &[String]) -> Result { use crate::query::datalog::stratification::DependencyGraph; diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 42a0706420..2a060c252a 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1,17 +1,26 @@ +#[cfg(any(test, feature = "test-oracle"))] use super::aggregate::{Agg, Groups, finish_groups, named_vars, value_order, windows}; +#[cfg(any(test, feature = "test-oracle"))] use super::evaluator::{StratifiedEvaluator, evaluate_not_join}; use super::functions::FunctionRegistry; -use super::matcher::{PatternMatcher, edn_to_entity_id, edn_to_value}; +#[cfg(any(test, feature = "test-oracle"))] +use super::matcher::PatternMatcher; +use super::matcher::{edn_to_entity_id, edn_to_value}; +#[cfg(any(test, feature = "test-oracle"))] use super::optimizer; use super::rules::RuleRegistry; +#[cfg(any(test, feature = "test-oracle"))] +use super::types::AsOf; use super::types::{ - AsOf, AttributeSpec, BinOp, DatalogCommand, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, - Rule, Transaction, UnaryOp, ValidAt, WhereClause, WindowFunc, + AttributeSpec, BinOp, DatalogCommand, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, Rule, + Transaction, UnaryOp, ValidAt, WhereClause, WindowFunc, }; use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::FactStorage; use crate::graph::storage::Snapshot; -use crate::graph::types::{Fact, TransactOptions, TxId, Value, tx_id_now}; +#[cfg(any(test, feature = "test-oracle"))] +use crate::graph::types::{Fact, tx_id_now}; +use crate::graph::types::{TransactOptions, TxId, Value}; use anyhow::Result; use std::collections::HashMap; use std::sync::{Arc, RwLock}; @@ -28,6 +37,7 @@ fn check_per_fact_pseudo_attrs(query: &DatalogQuery) -> Result<()> { /// `QRY-007`: surface unknown UDF predicates as errors before processing any /// rows (matches the behaviour of the former apply_expr_clauses post-pass). +#[cfg(any(test, feature = "test-oracle"))] fn check_udf_predicates(query: &DatalogQuery, registry: &FunctionRegistry) -> Result<()> { for clause in &query.where_clauses { if let WhereClause::Expr { @@ -42,11 +52,28 @@ fn check_udf_predicates(query: &DatalogQuery, registry: &FunctionRegistry) -> Re Ok(()) } -/// The clause checks of the executor's own path, for a query the streaming -/// engine runs: its errors come first, from the same code (#473). +/// `QRY-007` for the first of `names` that `registry` lacks: the engine +/// resolves every predicate a query names, at any depth, when it opens +/// (#551 spec §3.2). +fn check_predicates<'a>( + names: impl IntoIterator, + registry: &FunctionRegistry, +) -> Result<()> { + for name in names { + if registry.get_predicate(name).is_none() { + bail_coded!(ErrorCode::Qry007, name); + } + } + Ok(()) +} + +/// The clause checks for a query the streaming engine runs: the executor's +/// pseudo-attribute check, then every predicate it names (#473, #551). fn check_clauses(query: &DatalogQuery, registry: &FunctionRegistry) -> Result<()> { check_per_fact_pseudo_attrs(query)?; - check_udf_predicates(query, registry) + let mut names = Vec::new(); + crate::query::engine::udfs(&query.where_clauses, &mut names); + check_predicates(&names, registry) } /// Returns true if any where clause (at any depth) contains a per-fact @@ -73,6 +100,7 @@ fn query_uses_per_fact_pseudo_attr(query: &DatalogQuery) -> bool { /// including those nested inside `Not`, `NotJoin`, `Or`, and `OrJoin` bodies. /// Used by `selective_fact_fetch` to ensure every pattern that references a fact /// (including not-body patterns) is considered when deciding which indexes to query. +#[cfg(any(test, feature = "test-oracle"))] fn collect_all_patterns(clauses: &[WhereClause]) -> Vec { let mut patterns = Vec::new(); for clause in clauses { @@ -244,6 +272,7 @@ impl DatalogExecutor { /// Read-time "now" for query visibility: the snapshot's time when the /// executor has one, otherwise the wall clock. A write transaction's /// snapshot is at or after its newest staged fact (#550 spec §7). + #[cfg(any(test, feature = "test-oracle"))] fn read_now(&self) -> i64 { self.snapshot .as_ref() @@ -350,6 +379,7 @@ impl DatalogExecutor { /// transaction overlay, and for `:as-of` counters, committed history is already /// reduced to its net-asserted records on index keys (#379); step 2 still runs over /// the union with the pending facts, which gives the same result. + #[cfg(any(test, feature = "test-oracle"))] fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result> { let now = self.read_now(); @@ -389,6 +419,7 @@ impl DatalogExecutor { /// Step 1 without a transaction overlay: pending facts up to `as_of` plus the /// committed facts that survive net-assert at `as_of` (#379), selectively when the /// patterns allow it. Rules need the whole fact base, so they always get a full scan. + #[cfg(any(test, feature = "test-oracle"))] fn live_source_facts(&self, query: &DatalogQuery, as_of: Option) -> Result> { if !query.uses_rules() { let patterns = collect_all_patterns(&query.where_clauses); @@ -419,6 +450,7 @@ impl DatalogExecutor { /// which is idempotent under duplicated records. Each lookup returns the pending facts /// up to `as_of` and the committed facts live at `as_of`, and all lookups read one /// state of the store (`Snapshot::live_facts_of_scans`, #555). + #[cfg(any(test, feature = "test-oracle"))] fn selective_fact_fetch( &self, patterns: &[Pattern], @@ -522,14 +554,9 @@ impl DatalogExecutor { check_find_functions(&query.find, ®istry)?; } - // Check if query uses rules + // A rule query (#548). if query.uses_rules() { - // The engine runs the rule queries it plans (#548). - if let Some(answer) = self.open_rule_query(&query)? { - return Ok(answer); - } - // Use StratifiedEvaluator for queries with rule invocations (handles negation and strata) - return self.execute_query_with_rules(query).map(Answer::Result); + return self.open_rule_query(&query); } // Warn about queries with no binding mechanism @@ -537,50 +564,54 @@ impl DatalogExecutor { return Err(err_coded!(ErrorCode::Int027)); } - // The streaming engine runs the queries it has operators for (#473). - if let Some(plan) = crate::query::engine::plan(&query) { - { - let registry = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - check_clauses(&query, ®istry)?; + // The streaming engine runs every query (#473, #551). A planner + // error comes after the pseudo-attribute check (#473 spec §5.5). + let plan = match crate::query::engine::plan(&query) { + Ok(plan) => plan, + Err(e) => { + check_per_fact_pseudo_attrs(&query)?; + return Err(e); } - let snapshot = self.read_snapshot()?; - if let Some(stream) = crate::query::engine::open( - snapshot.clone(), - plan, - self.functions.clone(), - self.query_memory_limit, - ) { - #[cfg(test)] - crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); - // The comparison drains a second stream, so the one returned - // stays unread. - #[cfg(any(test, feature = "test-oracle"))] - if let Some(again) = crate::query::engine::plan(&query).and_then(|plan| { + }; + { + let registry = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + check_clauses(&query, ®istry)?; + } + let snapshot = self.read_snapshot()?; + let stream = crate::query::engine::open( + snapshot.clone(), + plan, + self.functions.clone(), + self.query_memory_limit, + )?; + #[cfg(test)] + crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); + // The comparison drains a second stream, so the one returned stays + // unread. + #[cfg(any(test, feature = "test-oracle"))] + crate::query::engine::oracle::check( + &crate::query::engine::plan(&query) + .and_then(|plan| { crate::query::engine::open( snapshot.clone(), plan, self.functions.clone(), self.query_memory_limit, ) - }) { - crate::query::engine::oracle::check( - &again.collect(), - &self.oracle(snapshot).execute_query_on_executor(query), - ); - } - return Ok(Answer::Stream(Box::new(stream))); - } - } - self.execute_query_on_executor(query).map(Answer::Result) + }) + .and_then(crate::query::engine::Stream::collect), + &self.oracle(snapshot).execute_query_on_executor(query), + ); + Ok(Answer::Stream(Box::new(stream))) } - /// A rule query on the streaming engine (#548), or `None` when the - /// engine does not plan it. Its errors come in the executor's order: - /// pseudo-attributes, then the rules, then unknown predicates. - fn open_rule_query(&self, query: &DatalogQuery) -> Result> { + /// A rule query on the streaming engine (#548). Its errors come in the + /// executor's order: pseudo-attributes, then the rules, then unknown + /// predicates. + fn open_rule_query(&self, query: &DatalogQuery) -> Result { let plan = { let registry = self .rules @@ -597,8 +628,12 @@ impl DatalogExecutor { } } }; - let Some((plan, seeds)) = plan else { - return Ok(None); + let (plan, seeds) = match plan { + Ok(planned) => planned, + Err(e) => { + check_per_fact_pseudo_attrs(query)?; + return Err(e); + } }; check_per_fact_pseudo_attrs(query)?; let limits = crate::query::engine::Limits { @@ -607,7 +642,11 @@ impl DatalogExecutor { query_memory: self.query_memory_limit, }; let snapshot = self.read_snapshot()?; - let open = |plan| -> Result> { + // The query's predicates, then its rules' (#551 plan, decision 9). + let mut names = Vec::new(); + crate::query::engine::udfs(&query.where_clauses, &mut names); + names.extend(plan.predicates.iter().cloned()); + let open = |plan| -> Result { let stream = crate::query::engine::open_rules( snapshot.clone(), plan, @@ -615,37 +654,26 @@ impl DatalogExecutor { self.functions.clone(), limits, )?; - if stream.is_some() { - let registry = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - check_udf_predicates(query, ®istry)?; - } + let registry = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + check_predicates(&names, ®istry)?; Ok(stream) }; // The comparison drains a second stream, so the one returned stays // unread. #[cfg(any(test, feature = "test-oracle"))] - { - let again = open(plan.clone()); - if !matches!(again, Ok(None)) { - crate::query::engine::oracle::check( - &again.and_then(|s| { - s.map_or_else(|| Err(err_coded!(ErrorCode::Int049)), |s| s.collect()) - }), - &self - .oracle(snapshot.clone()) - .execute_query_with_rules(query.clone()), - ); - } - } - let Some(stream) = open(plan)? else { - return Ok(None); - }; + crate::query::engine::oracle::check( + &open(plan.clone()).and_then(crate::query::engine::Stream::collect), + &self + .oracle(snapshot.clone()) + .execute_query_with_rules(query.clone()), + ); + let stream = open(plan)?; #[cfg(test)] crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); - Ok(Some(Answer::Stream(Box::new(stream)))) + Ok(Answer::Stream(Box::new(stream))) } /// The most facts `query`'s rules may derive: a per-query limit replaces @@ -673,6 +701,7 @@ impl DatalogExecutor { /// [`Self::execute_query`] on this executor, after the checks every /// query passes first. + #[cfg(any(test, feature = "test-oracle"))] fn execute_query_on_executor(&self, query: DatalogQuery) -> Result { // Compute query-level valid_at value for :db/valid-at pseudo-attribute binding. let now = self.read_now(); @@ -831,6 +860,7 @@ impl DatalogExecutor { } /// Execute a query that uses recursive rules + #[cfg(any(test, feature = "test-oracle"))] fn execute_query_with_rules(&self, query: DatalogQuery) -> Result { // Extract ALL predicates (including inside not bodies) so the StratifiedEvaluator // evaluates every referenced rule. This is needed for not-post-filter to work. @@ -1141,6 +1171,7 @@ impl DatalogExecutor { /// the entity position (→ `Ref`) or the value position (→ `Keyword`) of a fact. /// Normalize both to `Value::Ref` so that exclusion-set probes work correctly across /// these two representations. +#[cfg(any(test, feature = "test-oracle"))] fn normalize_value(v: &Value) -> Value { if let Value::Keyword(k) = v { use crate::query::datalog::matcher::edn_to_entity_id; @@ -1158,6 +1189,7 @@ fn normalize_value(v: &Value) -> Value { /// The body is matched from the outer values of the variables it names /// (`seeded_body_rows`, #546). Rule invocations in it match the rule-derived /// facts `storage` holds on the rules path. +#[cfg(any(test, feature = "test-oracle"))] fn not_body_matches( not_body: &[WhereClause], outer: &Binding, @@ -1182,6 +1214,7 @@ fn not_body_matches( /// Precomputes one exclusion set from the body's patterns (matched once against /// `filtered_facts`, independent of `bindings`), then probes it per binding — same /// fast path as the pre-#248 post-filter, just scoped to one clause at a time. +#[cfg(any(test, feature = "test-oracle"))] fn apply_not_clause( bindings: Vec, not_body: &[WhereClause], @@ -1272,6 +1305,7 @@ fn apply_not_clause( /// query path (`execute_query`). Mirrors [`apply_not_clause`] but keys the exclusion /// set on `join_vars` (the subset actually bound in every body row) instead of all /// body variables. +#[cfg(any(test, feature = "test-oracle"))] fn apply_not_join_clause( bindings: Vec, join_vars: &[String], @@ -1369,6 +1403,7 @@ fn apply_not_join_clause( /// Filter `bindings` through a single `(not ...)` body for the rules query path, /// where rule invocations in the body match `derived_facts`. +#[cfg(any(test, feature = "test-oracle"))] fn apply_not_clause_derived( bindings: Vec, not_body: &[WhereClause], @@ -1393,6 +1428,7 @@ fn apply_not_clause_derived( /// Whether `clauses`, or any clause list inside them, holds a per-fact /// pseudo-attribute pattern (#594), which reads metadata a source bound, /// possibly outside `clauses`. +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn reads_metadata(clauses: &[WhereClause]) -> bool { clauses.iter().any(|c| match c { WhereClause::Pattern(p) => p.pseudo_source.is_some(), @@ -1406,6 +1442,7 @@ pub(crate) fn reads_metadata(clauses: &[WhereClause]) -> bool { /// The variables an `or` / `or-join` branch binds itself: by a pattern, a /// rule invocation or an expression output. +#[cfg(any(test, feature = "test-oracle"))] fn branch_binds(branch: &[WhereClause]) -> std::collections::HashSet { let mut bound = std::collections::HashSet::new(); for c in branch { @@ -1436,6 +1473,7 @@ fn branch_binds(branch: &[WhereClause]) -> std::collections::HashSet { /// its own or an enclosing nested branch's. Only the outer row can bind them, so /// a branch with any must be seeded with that row, not evaluated from an empty /// binding and joined afterwards (#620). +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn branch_outer_reads(branch: &[WhereClause]) -> std::collections::HashSet { let bound = branch_binds(branch); let mut reads = std::collections::HashSet::new(); @@ -1457,6 +1495,7 @@ pub(crate) fn branch_outer_reads(branch: &[WhereClause]) -> std::collections::Ha /// Filter `bindings` through a single `(not-join [...] ...)` body for the rules query /// path — no exclusion-set fast path here (matches the pre-#248 post-filter, which /// never had one for this path either). +#[cfg(any(test, feature = "test-oracle"))] fn apply_not_join_clause_derived( bindings: Vec, join_vars: &[String], @@ -1481,6 +1520,7 @@ fn apply_not_join_clause_derived( } /// Extract plain variable values from bindings (non-aggregate path). +#[cfg(any(test, feature = "test-oracle"))] fn extract_variables( bindings: Vec>, find_specs: &[FindSpec], @@ -1502,6 +1542,7 @@ fn extract_variables( results } +#[cfg(any(test, feature = "test-oracle"))] type Binding = std::collections::HashMap; /// Which clause of a query's top-level `:where` gave each variable its value @@ -1630,6 +1671,7 @@ impl Binders { /// - Aggregates only → group-by collapse, then project. /// - Windows only → partition/sort/accumulate per spec, then project. /// - Mixed → aggregate collapses first, window runs over collapsed rows. +#[cfg(any(test, feature = "test-oracle"))] fn apply_post_processing( bindings: Vec, find_specs: &[FindSpec], @@ -1668,6 +1710,7 @@ fn apply_post_processing( /// result does not depend on the order of the bindings. Groups finish in /// key order; the first aggregate in `:find` order whose result is an error /// fails the query, except `INT-042`, which drops the group (spec §3.3). +#[cfg(any(test, feature = "test-oracle"))] fn compute_aggregation( bindings: Vec, find_specs: &[FindSpec], @@ -1790,6 +1833,7 @@ fn compute_aggregation( /// Modifies `bindings` in place; rows keep their order. The values come /// from [`windows`], over each binding's named variables (`nil` when /// absent). +#[cfg(any(test, feature = "test-oracle"))] fn apply_window_functions( bindings: &mut [Binding], find_specs: &[FindSpec], @@ -1820,6 +1864,7 @@ fn apply_window_functions( } /// Project binding maps to output rows in find-spec order. +#[cfg(any(test, feature = "test-oracle"))] fn project_find_specs(bindings: &[Binding], find_specs: &[FindSpec]) -> Vec> { let mut results = Vec::new(); for binding in bindings { @@ -1850,6 +1895,7 @@ fn project_find_specs(bindings: &[Binding], find_specs: &[FindSpec]) -> Vec ValidAt { match valid_at_value { Value::Integer(t) => ValidAt::Timestamp(*t), @@ -1865,6 +1911,7 @@ fn branch_valid_at(valid_at_value: &Value) -> ValidAt { /// 2. Nested Or/OrJoin → apply_or_clauses (recursive) /// 3. Not/NotJoin → post-filter /// 4. Expr → apply_expr_clauses +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn evaluate_branch( branch: &[WhereClause], incoming: Vec, @@ -1997,10 +2044,12 @@ pub(crate) fn evaluate_branch( /// A branch row meets an outer row by join equality (#546, spec §5.3): a /// keyword equals a ref to the entity it names; floats compare by IEEE `==` /// (`Value`'s own equality). Dedup keys stay exact `Value`s. +#[cfg(any(test, feature = "test-oracle"))] fn join_value(v: &Value) -> Value { PatternMatcher::normalize_join_value(v) } +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn apply_or_clauses( clauses: &[WhereClause], mut bindings: Vec, @@ -2627,6 +2676,7 @@ pub(crate) fn eval_expr( /// /// Pre-validates UDF predicate names: returns `Err` if a named UDF predicate is not /// registered, so callers get a clear error rather than silently empty results. +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn apply_expr_clauses( mut bindings: Vec, where_clauses: &[WhereClause], @@ -2663,6 +2713,7 @@ pub(crate) fn apply_expr_clauses( /// IEEE `==`, a keyword equal to a ref to the entity it names, an integer /// never equal to a float. `replace` then takes the result as the value /// (`Binders::expression`). A failing expression drops the row. +#[cfg(any(test, feature = "test-oracle"))] pub(crate) fn apply_expr( expr: &Expr, out: Option<&str>, @@ -2699,6 +2750,99 @@ mod tests { use std::sync::{Arc, RwLock}; use uuid::Uuid; + /// The entities of a one-column query answer, sorted. + fn entities(result: Result) -> Vec { + let QueryResult::QueryResults { results, .. } = result.expect("query") else { + panic!("expected query results"); + }; + let mut out: Vec = results + .iter() + .map(|r| match r.first() { + Some(Value::Ref(u)) => *u, + _ => panic!("expected an entity"), + }) + .collect(); + out.sort(); + out + } + + fn keyword(k: &str) -> Uuid { + crate::query::datalog::matcher::edn_to_entity_id(&EdnValue::Keyword(k.to_string())) + .expect("keyword entity") + } + + fn query_of(text: &str) -> DatalogQuery { + match parse_datalog_command(text).expect("parse") { + DatalogCommand::Query(q) => q, + _ => panic!("expected a query"), + } + } + + /// Answer change 1 (#551 spec §4): a `not` in an `or` branch sees the + /// variable an expression of the branch binds on the engine; the + /// executor applied the branch's `not` before its expression. + #[test] + fn branch_not_sees_its_expression_binding() { + let executor = DatalogExecutor::new(FactStorage::new()); + executor + .execute(parse_datalog_command("(transact [[:x :n 1] [:y :n 2] [:z :n 5]])").unwrap()) + .unwrap(); + let q = "(query [:find ?e :where [?e :n ?v] (or-join [?e ?v] (and [(+ ?v 1) ?w] (not [?f :n ?w])) [?e :n 5])])"; + let _exempt = crate::query::engine::oracle::exempt(); + let before = crate::query::engine::RUNS.with(std::cell::Cell::get); + let engine = entities(executor.execute(parse_datalog_command(q).unwrap())); + assert_eq!( + crate::query::engine::RUNS.with(std::cell::Cell::get), + before + 1, + "the engine runs it" + ); + assert!( + engine == { + let mut v = vec![keyword(":y"), keyword(":z")]; + v.sort(); + v + }, + "the engine: :y (no :n 3) and :z" + ); + let old = entities(executor.execute_query_on_executor(query_of(q))); + assert!(old == vec![keyword(":z")], "the executor: :z only"); + } + + /// Answer change 2 (#551 spec §4): an unknown predicate in an `or` + /// branch is `QRY-007` on the engine whether or not a row reaches it, + /// in a plain query and in a rule body; the executor answered when none + /// did. In a `not` body too (plan deviation 4): the executor's predicate + /// failed on every body row, so the `not` kept every outer row. + #[test] + fn unknown_branch_predicate_fails_eagerly() { + let executor = DatalogExecutor::new(FactStorage::new()); + for cmd in [ + "(transact [[:x :n 1] [:z :n 5]])", + "(rule [(odd ?e) [?e :n ?v] (or (and [?e :n 99] [(no-such? ?v)]) [?e :n 5])])", + ] { + executor + .execute(parse_datalog_command(cmd).unwrap()) + .unwrap(); + } + let plain = + "(query [:find ?e :where [?e :n ?v] (or (and [?e :n 99] [(no-such? ?v)]) [?e :n 5])])"; + let rule = "(query [:find ?e :where (odd ?e)])"; + let negated = "(query [:find ?e :where [?e :n ?v] (not [?e :n ?v] [(no-such? ?v)])])"; + let _exempt = crate::query::engine::oracle::exempt(); + for q in [plain, rule, negated] { + let err = executor + .execute(parse_datalog_command(q).unwrap()) + .expect_err("the engine resolves every predicate"); + assert_eq!(crate::error::MinigrafError::from(err).code(), "QRY-007"); + } + let old = entities(executor.execute_query_on_executor(query_of(plain))); + assert!(old == vec![keyword(":z")], "the executor: :z"); + let old = entities(executor.execute_query_with_rules(query_of(rule))); + assert!(old == vec![keyword(":z")], "the executor, rule body: :z"); + let old = entities(executor.execute_query_on_executor(query_of(negated))); + assert_eq!(old.len(), 2, "the executor: every outer row"); + } + #[test] fn test_execute_transact() { let storage = FactStorage::new(); diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index 1e58d703fd..fc2c68c8ea 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -1,29 +1,43 @@ +#[cfg(any(test, feature = "test-oracle"))] use super::optimizer::IndexHint; -use super::types::{AttributeSpec, EdnValue, Pattern, PseudoAttr}; +use super::types::EdnValue; +#[cfg(any(test, feature = "test-oracle"))] +use super::types::{AttributeSpec, Pattern, PseudoAttr}; +#[cfg(any(test, feature = "test-oracle"))] use crate::graph::FactStorage; -use crate::graph::types::{EntityId, Fact, Value}; +#[cfg(any(test, feature = "test-oracle"))] +use crate::graph::types::Fact; +use crate::graph::types::{EntityId, Value}; +#[cfg(any(test, feature = "test-oracle"))] use std::borrow::Cow; +#[cfg(any(test, feature = "test-oracle"))] use std::collections::HashMap; +#[cfg(any(test, feature = "test-oracle"))] use std::sync::Arc; use uuid::Uuid; /// Variable bindings for query execution /// Maps variable names (e.g., "?name") to their bound values +#[cfg(any(test, feature = "test-oracle"))] pub type Bindings = HashMap; +#[cfg(any(test, feature = "test-oracle"))] enum MatcherStorage { Owned(FactStorage), Slice(Arc<[Fact]>), } /// Pattern matcher that finds facts matching a pattern and produces bindings +#[cfg(any(test, feature = "test-oracle"))] pub struct PatternMatcher { storage: MatcherStorage, /// The `:db/valid-at` value for this query context (Value::Null when not set). pub(crate) valid_at_value: Value, } +#[cfg(any(test, feature = "test-oracle"))] impl PatternMatcher { + #[cfg(any(test, feature = "test-oracle"))] pub fn new(storage: FactStorage) -> Self { PatternMatcher { storage: MatcherStorage::Owned(storage), @@ -45,6 +59,7 @@ impl PatternMatcher { /// Constructs a matcher with an explicit `:db/valid-at` binding value. /// Used by the executor when the query has a known `valid_at` point. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn from_slice_with_valid_at(facts: Arc<[Fact]>, valid_at: Value) -> Self { PatternMatcher { storage: MatcherStorage::Slice(facts), @@ -53,6 +68,7 @@ impl PatternMatcher { } /// Set the value a `:db/valid-at` pattern binds. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn with_valid_at(mut self, valid_at: Value) -> Self { self.valid_at_value = valid_at; self @@ -272,6 +288,7 @@ impl PatternMatcher { /// Match multiple patterns with variable unification /// Returns bindings that satisfy all patterns simultaneously + #[cfg(any(test, feature = "test-oracle"))] pub fn match_patterns(&self, patterns: &[Pattern]) -> Vec { if patterns.is_empty() { return vec![HashMap::new()]; @@ -325,6 +342,7 @@ impl PatternMatcher { /// `rebind` names variables the seed binds whose value this pattern /// replaces with its own (#545): an equal value of another kind, a keyword /// for a ref or the reverse. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn match_with_hint_seeded( &self, seed: Vec, @@ -355,6 +373,7 @@ impl PatternMatcher { /// For each seed binding, extends it by matching all patterns in sequence. /// Returns all extended bindings that satisfy every pattern. /// If `seed` is empty, returns empty. If `patterns` is empty, returns `seed` unchanged. + #[cfg(any(test, feature = "test-oracle"))] pub(crate) fn match_patterns_seeded( &self, patterns: &[Pattern], diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index ee5564b3dd..f223fd5ba6 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -269,6 +269,7 @@ pub(crate) fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::Hash /// /// Returns `(interleaved, deferred)` where `interleaved` pairs each Pattern with /// `Some(hint)` and each Expr/Not/NotJoin with `None`. +#[cfg(any(test, feature = "test-oracle"))] pub fn plan( clauses: Vec, ) -> (Vec<(WhereClause, Option)>, Vec) { diff --git a/src/query/datalog/rules.rs b/src/query/datalog/rules.rs index 96de9c15c7..adfd4a8b3b 100644 --- a/src/query/datalog/rules.rs +++ b/src/query/datalog/rules.rs @@ -80,6 +80,16 @@ impl RuleRegistry { Ok(()) } + /// Register `rule` without the stratification check: a registry no + /// definition can build, for the planner's tests (#551). + #[cfg(test)] + pub(crate) fn insert_unchecked(&mut self, predicate: &str, rule: Rule) { + self.rules + .entry(predicate.to_string()) + .or_default() + .push(rule); + } + /// Get all rules for a given predicate. /// /// Returns an empty vector if no rules are registered for the predicate. diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index cae5a81976..6dc92de011 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -263,6 +263,7 @@ impl FindSpec { /// The logic variable this spec draws values from. /// For rank/row-number (no var), returns a synthetic placeholder. + #[cfg(any(test, feature = "test-oracle"))] pub fn var(&self) -> &str { match self { FindSpec::Variable(v) => v.as_str(), @@ -650,6 +651,7 @@ impl DatalogQuery { /// /// Used by execute_query_with_rules to build positive patterns from rule heads; /// rule invocations inside `not` are handled by the not-post-filter, not here. + #[cfg(any(test, feature = "test-oracle"))] pub fn get_top_level_rule_invocations(&self) -> Vec<(String, Vec)> { self.where_clauses .iter() diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 436838fbc1..2b27dd5bc4 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -82,6 +82,7 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { let keep: Vec = meta.iter().map(|c| want.as_ref() == Some(c)).collect(); batch.retain(&keep); } + Term::Never => batch.retain(&vec![false; batch.len]), Term::Eq(slot) => { let other = batch.cols.get(*slot); let keep: Vec = meta diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index 957b62b432..442342b91e 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -1,10 +1,9 @@ //! Streaming query engine (#473): operators that pass batches of id cells //! over one [`Snapshot`]. //! -//! Built beside the existing executor (spec §9): [`plan`] says which queries -//! run here, and the executor runs the rest. Under `cfg(test)` and the -//! `test-oracle` feature, every query run here is also run by the executor -//! and the answers are compared ([`oracle`]). +//! Every query runs here (#551). Under `cfg(test)` and the `test-oracle` +//! feature, every query is also run by the executor's query path, which is +//! built for that only, and the answers are compared ([`oracle`]). mod aggregate; mod anti; @@ -33,12 +32,12 @@ use crate::graph::storage::Snapshot; use crate::graph::types::{EntityId, Value}; use crate::query::datalog::executor::QueryResult; use crate::query::datalog::functions::FunctionRegistry; -use crate::storage::{CommittedReader, KeySource}; +use crate::storage::{CommittedReader, KeySource, TxBound}; use anyhow::Result; use batch::Batch; use ids::IdSpace; pub(crate) use meter::Meter; -pub(crate) use plan::{Plan, plan, plan_rules}; +pub(crate) use plan::{Plan, plan, plan_rules, udfs}; pub(crate) use recursive::Limits; use std::sync::{Arc, RwLock}; @@ -62,6 +61,8 @@ pub(crate) struct Ctx<'a> { functions: &'a FunctionRegistry, /// In a rule query, the relations its rules derived (#548). derived: Option<&'a relation::Relations>, + /// The versions the query's `:as-of` keeps (#551). + bound: &'a TxBound, } /// What one operator has done (spec §6.3): rows it read or received, rows @@ -127,6 +128,10 @@ pub(crate) struct Stream { hold_ids: bool, /// In a rule query, the relations its rules derived (#548). relations: Option, + /// The versions the query's `:as-of` keeps, and the bytes its ranges + /// hold (#551). + bound: TxBound, + bound_held: meter::Held, closed: bool, } @@ -140,43 +145,68 @@ impl std::fmt::Debug for Stream { } } -/// Open `plan` over `snapshot`, holding at most `memory_limit` bytes, or -/// `None` when the snapshot's committed reader has no keys (a test reader) -/// and the executor must run it. +/// The key-level reads of `snapshot`'s committed generation, if it has one. +fn keys(snapshot: &Snapshot) -> Result> { + match &snapshot.committed { + Some(reader) => match reader.key_source() { + Some(k) => Ok(Some(k)), + // Only a test reader has none (#551 plan, decision 12). + None => Err(err_coded!( + ErrorCode::Int049, + "a committed reader without keys" + )), + }, + None => Ok(None), + } +} + +/// Open `plan` over `snapshot`, holding at most `memory_limit` bytes. pub(crate) fn open( snapshot: Snapshot, plan: Plan, functions: Arc>, memory_limit: usize, -) -> Option { - let keys = match &snapshot.committed { - Some(reader) => Some(reader.key_source()?), - None => None, - }; +) -> Result { + let keys = keys(&snapshot)?; let meter = Meter::new(memory_limit); + let bound = resolve(&snapshot, plan.as_of, &meter)?; let ids = IdSpace::new(keys, &meter); - Some(stream(snapshot, ids, plan, functions, None, meter)) + Ok(stream(snapshot, ids, plan, functions, None, meter, bound)) +} + +/// The versions `as_of` keeps in `snapshot`, and its ranges charged to +/// `meter` (#551 plan, decision 6). +fn resolve( + snapshot: &Snapshot, + as_of: plan::AsOfSpec, + meter: &Arc, +) -> Result<(TxBound, meter::Held)> { + let mut held = meter::Held::new(meter, "AsOf"); + let bound = match as_of { + plan::AsOfSpec::None => TxBound::All, + plan::AsOfSpec::Counter(n) => TxBound::Upto(n), + plan::AsOfSpec::Timestamp(t) => snapshot.tx_bound(t)?, + }; + if let TxBound::Timestamp { committed, .. } = &bound { + held.charge(std::mem::size_of_val::<[(u64, u64)]>(committed))?; + } + Ok((bound, held)) } /// Open the rule query `plan` over `snapshot`: derive its relations, with -/// the magic seeds `seeds` as rows, then open its body (#548). `None` as -/// [`open`]; an error from the rules fails the query here. +/// the magic seeds `seeds` as rows, then open its body (#548). An error from +/// the rules fails the query here. pub(crate) fn open_rules( snapshot: Snapshot, plan: plan::RulesPlan, seeds: &[(EntityId, String, Value)], functions: Arc>, limits: recursive::Limits, -) -> Result> { +) -> Result { let meter = Meter::new(limits.query_memory); + let bound = resolve(&snapshot, plan.as_of, &meter)?; let (ids, relations) = { - let keys = match &snapshot.committed { - Some(reader) => match reader.key_source() { - Some(k) => Some(k), - None => return Ok(None), - }, - None => None, - }; + let keys = keys(&snapshot)?; let mut ids = IdSpace::new(keys, &meter); let iids = plan .evaluated @@ -202,18 +232,20 @@ pub(crate) fn open_rules( snapshot: &snapshot, keys, functions: &functions, + bound: &bound.0, }; recursive::evaluate(&plan, &mut rels, &reads, &mut ids, limits, &meter)?; (ids, rels) }; - Ok(Some(stream( + Ok(stream( snapshot, ids, plan.body, functions, Some(relations), meter, - ))) + bound, + )) } /// The stream of `plan` over `snapshot`. @@ -224,12 +256,14 @@ fn stream( functions: Arc>, relations: Option, meter: Arc, + (bound, bound_held): (TxBound, meter::Held), ) -> Stream { let Plan { source, steps, find, vars, + as_of: _, } = plan; let hold_ids = steps.iter().any(|s| matches!(s, plan::Step::Window { .. })); let root = build(source, steps, &meter); @@ -245,6 +279,8 @@ fn stream( project: Counters::new("Project"), hold_ids, relations, + bound, + bound_held, closed: false, } } @@ -287,6 +323,7 @@ impl Stream { #[cfg(test)] pub(crate) fn for_test(snapshot: Snapshot, root: Box) -> Self { let meter = Meter::unlimited(); + let bound_held = meter::Held::new(&meter, "AsOf"); Stream { snapshot, ids: IdSpace::new(None, &meter), @@ -298,6 +335,8 @@ impl Stream { project: Counters::new("Project"), hold_ids: false, relations: None, + bound: TxBound::All, + bound_held, closed: false, } } @@ -335,6 +374,7 @@ impl Stream { ids: &mut self.ids, functions: &functions, derived: self.relations.as_ref(), + bound: &self.bound, }; let Some(batch) = self.root.next_batch(&mut ctx)? else { return Ok(None); @@ -359,6 +399,8 @@ impl Stream { self.root = Box::new(Closed(counters)); self.ids.release(); self.relations = None; + self.bound = TxBound::All; + self.bound_held.release(); } } diff --git a/src/query/engine/oracle.rs b/src/query/engine/oracle.rs index da264af542..0c04dbeab2 100644 --- a/src/query/engine/oracle.rs +++ b/src/query/engine/oracle.rs @@ -4,6 +4,31 @@ use crate::error::{CodedError, ErrorCode}; use crate::query::datalog::executor::QueryResult; use crate::storage::index::encode_value; use anyhow::Result; +use std::cell::Cell; + +thread_local! { + /// Whether [`check`] is skipped on this thread ([`exempt`]). + static EXEMPT: Cell = const { Cell::new(false) }; +} + +/// Skip [`check`] on this thread until the guard drops: only for the answers +/// the engine changes on purpose, whose tests check both answers (#551 spec +/// §4, plan decision 10). +#[cfg(test)] +pub(crate) fn exempt() -> Exempt { + EXEMPT.with(|e| e.set(true)); + Exempt(()) +} + +#[cfg(test)] +pub(crate) struct Exempt(()); + +#[cfg(test)] +impl Drop for Exempt { + fn drop(&mut self) { + EXEMPT.with(|e| e.set(false)); + } +} /// Panic unless `engine` and `oracle` give the same answer: both errors, or /// the same columns and the same rows as a bag. An engine `QRY-012` agrees @@ -14,6 +39,9 @@ use anyhow::Result; /// panic is how a disagreement fails the test. #[allow(clippy::panic)] pub(crate) fn check(engine: &Result, oracle: &Result) { + if EXEMPT.with(Cell::get) { + return; + } match (engine, oracle) { (Err(_), Err(_)) => {} (Err(e), Ok(_)) diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 8ac07c7943..35fc0b6ce5 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -1,10 +1,7 @@ -//! Planner v2 (#473 spec §6.3): which queries the engine runs, and their -//! operator trees. -//! -//! The engine runs a query whose `:where` holds patterns and expression -//! clauses, and whose `:find` holds plain variables (#545), or aggregates -//! with plain variables and a `:with` (#547). Every other query runs on the -//! existing executor (spec §9). +//! Planner v2 (#473 spec §6.3): the operator tree of every query (#551). +//! A query the planner cannot build fails with a coded error: the executor's +//! code for the same query (INT-022, INT-025, INT-028, INT-031, INT-054), or +//! INT-032 for an invariant the parser keeps. //! //! Clauses run in the order `optimizer::plan` gives the executor, so an //! expression sees the same variables as it does there. A binding expression @@ -23,6 +20,7 @@ use super::cell::Scalar; use super::relation::{Derived, Range}; +use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::types::{EntityId, Value}; use crate::query::datalog::aggregate::named_vars; use crate::query::datalog::evaluator::rule_invocation_to_pattern; @@ -35,9 +33,15 @@ use crate::query::datalog::types::{ AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, PseudoAttr, UnaryOp, ValidAt, WhereClause, }; +use anyhow::Result; use std::collections::{HashMap, HashSet}; use std::sync::Arc; +/// A planner invariant that does not hold (#551 plan, decision 2). +fn invariant(what: &str) -> anyhow::Error { + err_coded!(ErrorCode::Int032, what) +} + /// One position of a pattern. #[derive(Debug, Clone)] pub(crate) enum Term { @@ -48,6 +52,10 @@ pub(crate) enum Term { /// A later occurrence of a variable: must equal its slot. Eq(usize), Const(C), + /// A constant no cell can equal (#551 plan, decision 7): an entity that + /// is not a keyword or UUID, an attribute that is not a keyword, a + /// vector, list or map value. A scan with one reads nothing. + Never, } /// A constant in the value position, with the executor's matching rules @@ -112,7 +120,6 @@ pub(crate) struct ScanSpec { pub(crate) v: Term, /// Metadata columns the scan fills, and their slots. pub(crate) meta: Vec<(Meta, usize)>, - pub(crate) as_of: Option, pub(crate) valid: Valid, /// Number of slots the scan fills. pub(crate) width: usize, @@ -121,6 +128,16 @@ pub(crate) struct ScanSpec { pub(crate) derived: Option, } +impl ScanSpec { + /// Whether a position is a constant no cell equals: the scan reads + /// nothing. + pub(crate) fn never(&self) -> bool { + matches!(self.e, Term::Never) + || matches!(self.a, Term::Never) + || matches!(self.v, Term::Never) + } +} + /// A clause after the scan, in the executor's order. #[derive(Debug, Clone)] pub(crate) enum Step { @@ -264,6 +281,8 @@ pub(crate) struct Plan { /// variable's slot, or a column of `Aggregate`; empty for a body. pub(crate) find: Vec, pub(crate) vars: Vec, + /// The query's `:as-of`; `None` for a body, which reads its query's. + pub(crate) as_of: AsOfSpec, } /// Positions a slot's cells come from. @@ -293,26 +312,38 @@ impl Slots { } } -/// The `:as-of` counter and valid-time test of `query`, or `None` when the -/// engine does not run it: a timestamp is not a key bound, and a slot is -/// resolved before this. -fn temporal(query: &DatalogQuery) -> Option<(Option, Valid)> { +/// A query's `:as-of`, resolved against the snapshot when the query opens +/// (`Snapshot::tx_bound`, #551 plan, decision 5). +#[derive(Debug, Clone, Copy)] +pub(crate) enum AsOfSpec { + None, + Counter(u64), + /// Unix ms. + Timestamp(i64), +} + +/// The `:as-of` and valid-time test of `query`; a slot is resolved before +/// this. +fn temporal(query: &DatalogQuery) -> Result<(AsOfSpec, Valid)> { let as_of = match &query.as_of { - None => None, - Some(AsOf::Counter(n)) => Some(*n), - Some(AsOf::Timestamp(_) | AsOf::Slot(_)) => return None, + None => AsOfSpec::None, + Some(AsOf::Counter(n)) => AsOfSpec::Counter(*n), + Some(AsOf::Timestamp(t)) => AsOfSpec::Timestamp(*t), + // A prepared query substitutes every slot first. + Some(AsOf::Slot(_)) => return Err(invariant("an :as-of slot reached the planner")), }; let valid = match &query.valid_at { None => Valid::Now, Some(ValidAt::Timestamp(t)) => Valid::At(*t), Some(ValidAt::AnyValidTime) => Valid::Any, - Some(ValidAt::Slot(_)) => return None, + // As the executor reports one. + Some(ValidAt::Slot(_)) => bail_coded!(ErrorCode::Int025), }; - Some((as_of, valid)) + Ok((as_of, valid)) } -/// The plan of `query`, or `None` when the engine does not run it yet. -pub(crate) fn plan(query: &DatalogQuery) -> Option { +/// The plan of `query`. +pub(crate) fn plan(query: &DatalogQuery) -> Result { plan_with(query, None) } @@ -320,7 +351,12 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { /// clauses `optimizer::plan` places, in its order, then the `or`s, then the /// deferred ones. With `first`, that pattern runs first (a rule body's delta, /// #548 spec §5.3). -fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) -> Option<()> { +fn clauses( + b: &mut Builder, + clauses: &[WhereClause], + first: Option<&Pattern>, + seeded: &HashSet, +) -> Result<()> { if !clauses.iter().all(|c| { matches!( c, @@ -332,7 +368,9 @@ fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) -> | WhereClause::OrJoin { .. } ) }) { - return None; + // A plain query has no rule invocation, and a rule body's are + // patterns by now (`calls_as_patterns`). + return Err(invariant("a rule invocation reached the planner")); } // With `first`, the rest are ordered after it, its variables bound, each // joining on a variable bound before it where one can (#694). @@ -353,7 +391,7 @@ fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) -> planned.insert(0, (head, None)); (planned, deferred) } - None => optimizer::plan(clauses.to_vec()), + None => optimizer::plan_seeded(clauses.to_vec(), seeded), }; for (c, _) in planned { b.clause(c)?; @@ -370,24 +408,29 @@ fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) -> for c in sorted(deferred) { b.clause(c)?; } - Some(()) + Ok(()) } /// The plan of `query`, whose scans also read the relations `evaluated` /// when it is a rule query (#548). -fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Option { +fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Result { let (as_of, valid) = temporal(query)?; let mut b = Builder::new( Some(Binders::new(&query.where_clauses, Vec::new())), - as_of, valid, evaluated, ); - clauses(&mut b, &query.where_clauses, None)?; + clauses(&mut b, &query.where_clauses, None, &HashSet::new())?; // The parser rejects a variable no clause binds (PRS-080, PRS-022, - // PRS-023); one only some `or` branches bind has no slot here. - let slot = |var: &String| b.slots.by_var.get(var).copied(); + // PRS-023). + let slot = |var: &String| { + b.slots + .by_var + .get(var) + .copied() + .ok_or_else(|| invariant("a :find variable without a slot")) + }; // The column of each `:find` element that is not a window. let mut cols: Vec> = Vec::with_capacity(query.find.len()); let aggregate = query @@ -458,6 +501,7 @@ fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Option< .zip(&cols) .find(|(s, _)| matches!(s, FindSpec::Variable(v) if v == var)) .and_then(|(_, c)| *c) + .ok_or_else(|| invariant("a window's variable without a column")) } else { slot(var) } @@ -465,7 +509,7 @@ fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Option< let named = named_vars(&query.find) .iter() .map(column) - .collect::>>()?; + .collect::>>()?; let keep: Vec = cols.iter().flatten().copied().collect(); let (mut next_kept, mut next_window) = (0, keep.len()); for c in &cols { @@ -483,12 +527,16 @@ fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Option< keep, }); } else { - find = cols.into_iter().collect::>>()?; + find = cols + .into_iter() + .collect::>>() + .ok_or_else(|| invariant("a window outside a window query"))?; } let mut plan = b.finish()?; plan.find = find; plan.vars = query.find.iter().map(FindSpec::display_name).collect(); - Some(plan) + plan.as_of = as_of; + Ok(plan) } /// A rule query on the engine (#548 spec §5): the relations, the rules of @@ -498,9 +546,12 @@ pub(crate) struct RulesPlan { pub(crate) evaluated: Arc, /// Each stratum with rules: its relations, and its rules. pub(crate) strata: Vec<(Vec, Vec)>, - pub(crate) as_of: Option, + pub(crate) as_of: AsOfSpec, pub(crate) valid: Valid, pub(crate) body: Plan, + /// The predicates the evaluated rules' bodies name, in `plan_rules`' + /// predicate order, then text order (#551 plan, decision 9). + pub(crate) predicates: Vec, } /// One rule: its runs in round 1 and the rounds after (spec §5.3). @@ -526,27 +577,27 @@ pub(crate) struct RuleRun { pub(crate) value: Option, } -/// A head argument: a variable (PRS-114 rejects any other). +/// A head argument. #[derive(Debug, Clone)] pub(crate) enum HeadArg { Slot(usize), /// A variable the body does not bind (`INT-022` once a row reaches it). Unbound(String), + /// A constant: only the magic-set rewrite writes one (PRS-114 rejects + /// it in a rule the user defines, #608). + Const(EdnValue), } /// The plan of a rule query: `query` and every rule it evaluates in /// `registry` (the magic-set rewrite's, when it ran), whose relations also -/// hold the attributes `seeds` (magic seeds). `None` when the engine does not -/// run it: a body it does not plan, an `:as-of` timestamp, a slot, a -/// stratification error or an invocation of three or more arguments, which -/// the executor reports. +/// hold the attributes `seeds` (magic seeds). pub(crate) fn plan_rules( query: &DatalogQuery, registry: &RuleRegistry, seeds: &[&str], -) -> Option { +) -> Result { let (as_of, valid) = temporal(query)?; - let strata = DependencyGraph::from_rules(registry).stratify().ok()?; + let strata = DependencyGraph::from_rules(registry).stratify()?; // Every predicate the query invokes, and those their rules invoke, as // `StratifiedEvaluator::evaluate` collects them. let mut preds: Vec = Vec::new(); @@ -568,6 +619,12 @@ pub(crate) fn plan_rules( } i += 1; } + let mut predicates = Vec::new(); + for p in &preds { + for rule in registry.get_rules(p) { + udfs(&rule.body, &mut predicates); + } + } let mut attrs: Vec = preds.iter().map(|p| format!(":{p}")).collect(); for a in seeds { if !attrs.iter().any(|b| b == a) { @@ -602,7 +659,6 @@ pub(crate) fn plan_rules( rel, p, &in_stratum, - as_of, valid, &evaluated, )?); @@ -615,15 +671,35 @@ pub(crate) fn plan_rules( let mut body_query = query.clone(); body_query.where_clauses = calls_as_patterns(&query.where_clauses)?; let body = plan_with(&body_query, Some(evaluated.clone()))?; - Some(RulesPlan { + Ok(RulesPlan { evaluated, strata: planned, as_of, valid, body, + predicates, }) } +/// Append the predicates `clauses` name, at any depth, in text order. +pub(crate) fn udfs(clauses: &[WhereClause], out: &mut Vec) { + for c in clauses { + match c { + WhereClause::Expr { + expr: Expr::UnaryOp(UnaryOp::Udf(name), _), + .. + } => out.push(name.clone()), + WhereClause::Not(body) | WhereClause::NotJoin { clauses: body, .. } => udfs(body, out), + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + for b in branches { + udfs(b, out); + } + } + _ => {} + } + } +} + /// The plan of one rule of predicate `predicate` (relation `rel`), whose /// stratum holds the relations of the attributes `stratum`. #[allow(clippy::too_many_arguments)] @@ -633,15 +709,17 @@ fn rule_plan( rel: usize, predicate: &str, stratum: &HashSet, - as_of: Option, valid: Valid, evaluated: &Arc, -) -> Option { - // The executor reports a head without arguments; a fourth is ignored - // there. - if !(2..=3).contains(&head.len()) { - return None; - } +) -> Result { + // As on the executor: a head without arguments is an error, and + // arguments after the second are ignored. + let Some(entity) = head.get(1) else { + bail_coded!( + ErrorCode::Int022, + "Rule head must have at least 2 elements: (predicate ?arg1)" + ); + }; let naive = naive(body, stratum, false); let clauses = calls_as_patterns(body)?; // The top-level invocations of the stratum, in text order. @@ -656,24 +734,21 @@ fn rule_plan( _ => None, }) .collect(); - let run = |ranges: Vec<(Pattern, Range)>, first: Option<&Pattern>| -> Option { - let mut b = Builder::new(None, as_of, valid, Some(evaluated.clone())); + let run = |ranges: Vec<(Pattern, Range)>, first: Option<&Pattern>| -> Result { + let mut b = Builder::new(None, valid, Some(evaluated.clone())); b.ranges = ranges; - self::clauses(&mut b, &clauses, first)?; + self::clauses(&mut b, &clauses, first, &HashSet::new())?; let slots = std::mem::take(&mut b.slots.by_var); let arg = |e: &EdnValue| match e { - EdnValue::Symbol(v) if v.starts_with('?') => Some(match slots.get(v) { + EdnValue::Symbol(v) if v.starts_with('?') => match slots.get(v) { Some(&s) => HeadArg::Slot(s), None => HeadArg::Unbound(v.clone()), - }), - _ => None, - }; - Some(RuleRun { - entity: arg(head.get(1)?)?, - value: match head.get(2) { - Some(v) => Some(arg(v)?), - None => None, }, + c => HeadArg::Const(c.clone()), + }; + Ok(RuleRun { + entity: arg(entity), + value: head.get(2).map(arg), plan: b.finish()?, }) }; @@ -700,7 +775,7 @@ fn rule_plan( deltas.push(run(ranges, Some(delta))?); } } - Some(RulePlan { + Ok(RulePlan { rel, predicate: predicate.to_string(), full, @@ -731,19 +806,19 @@ fn naive(body: &[WhereClause], stratum: &HashSet, in_or: bool) -> bool { /// `clauses` with every rule invocation, at any depth, read as its pattern /// (`rule_invocation_to_pattern`), as the executor matches it. -fn calls_as_patterns(clauses: &[WhereClause]) -> Option> { +fn calls_as_patterns(clauses: &[WhereClause]) -> Result> { let all = |branches: &[Vec]| { branches .iter() .map(|b| calls_as_patterns(b)) - .collect::>>() + .collect::>>() }; clauses .iter() .map(|c| { - Some(match c { + Ok(match c { WhereClause::RuleInvocation { predicate, args } => { - WhereClause::Pattern(rule_invocation_to_pattern(predicate, args).ok()?) + WhereClause::Pattern(rule_invocation_to_pattern(predicate, args)?) } WhereClause::Not(body) => WhereClause::Not(calls_as_patterns(body)?), WhereClause::NotJoin { join_vars, clauses } => WhereClause::NotJoin { @@ -772,7 +847,6 @@ struct Builder { /// body, where no join or expression replaces a cell (decision 10 of the /// #546 plan). binders: Option, - as_of: Option, valid: Valid, source: Option, steps: Vec, @@ -829,16 +903,10 @@ impl Evaluated { } impl Builder { - fn new( - binders: Option, - as_of: Option, - valid: Valid, - evaluated: Option>, - ) -> Self { + fn new(binders: Option, valid: Valid, evaluated: Option>) -> Self { Builder { slots: Slots::default(), binders, - as_of, valid, source: None, steps: Vec::new(), @@ -849,21 +917,22 @@ impl Builder { } } - fn finish(self) -> Option { - if !self.front.is_empty() { - return None; - } - Some(Plan { - source: self.source?, + fn finish(mut self) -> Result { + // `not`s and no pattern: they run on the empty row (#551). + self.seed(); + let source = self.source.unwrap_or(Source::Seed); + Ok(Plan { + source, steps: self.steps, find: Vec::new(), vars: Vec::new(), + as_of: AsOfSpec::None, }) } - /// Add the steps of `c`; `None` when the engine cannot run it. - fn clause(&mut self, c: WhereClause) -> Option<()> { - let (as_of, valid) = (self.as_of, self.valid); + /// Add the steps of `c`. + fn clause(&mut self, c: WhereClause) -> Result<()> { + let valid = self.valid; match c { WhereClause::Pattern(q) => { let rebind = match &mut self.binders { @@ -872,12 +941,18 @@ impl Builder { }; let pseudo = meta(&q); if pseudo.is_some_and(|m| m != Meta::ValidAt) { - // Reads the hidden variable its source's scan filled. - let source = q.pseudo_source.as_ref()?.as_variable()?; - let col = *self.slots.by_var.get(source)?; + // Reads the hidden variable its source's scan filled; the + // parser names one (PRS-081 otherwise). + let col = q + .pseudo_source + .as_ref() + .and_then(EdnValue::as_variable) + .and_then(|source| self.slots.by_var.get(source)) + .copied() + .ok_or_else(|| invariant("a pseudo-attribute without its source"))?; let value = term(&q.value, &mut self.slots, OTHER, pseudo_const)?; self.steps.push(Step::Pseudo { col, value }); - return Some(()); + return Ok(()); } // A pattern with a stored attribute, or `:db/valid-at` read // as `[e _ _]` and the query's valid time. @@ -921,14 +996,13 @@ impl Builder { a, v, meta: metas.clone(), - as_of, valid, width: slots.len(), derived, })); self.steps.append(&mut self.front); } else { - let mut join = join(&scanned, &attribute, slots, &rebind, as_of, valid)?; + let mut join = join(&scanned, &attribute, slots, &rebind, valid)?; join.inner.derived = derived; for &(m, var) in &wants { let local = join.inner.width; @@ -959,14 +1033,18 @@ impl Builder { } self.outer_patterns.push(WhereClause::Pattern(q.clone())); if pseudo.is_some() { - let col = metas.last()?.1; + let col = metas + .last() + .ok_or_else(|| invariant("a valid-at column without a slot"))? + .1; let value = term(&q.value, &mut self.slots, OTHER, pseudo_const)?; self.steps.push(Step::Pseudo { col, value }); } } WhereClause::Expr { expr, binding } => { - // A clause before the first pattern sees no variable. - self.source.as_ref()?; + // A clause before the first pattern sees no variable: it + // runs once, on the empty row (#551). + self.seed(); let vars = expr_vars(&expr, &self.slots); let step = match binding { None => Step::Filter(expr, vars), @@ -997,7 +1075,7 @@ impl Builder { WhereClause::Not(body) => { // Every variable the body names that the rows bind; the // others are the body's own (its sources' hidden variables). - let imports = optimizer::clause_ref_vars(&body); + let imports = reads(&body); let step = self.anti(&body, imports.into_iter().collect())?; self.push_anti(step); } @@ -1010,9 +1088,20 @@ impl Builder { join_vars, branches, } => self.union(&branches, Some(join_vars))?, - _ => return None, + WhereClause::RuleInvocation { .. } => { + return Err(invariant("a rule invocation reached the planner")); + } + } + Ok(()) + } + + /// Start from the empty row if nothing was planned to scan first, and + /// run the `not`s planned before it. + fn seed(&mut self) { + if self.source.is_none() { + self.source = Some(Source::Seed); + self.steps.append(&mut self.front); } - Some(()) } fn push_anti(&mut self, step: Step) { @@ -1025,42 +1114,29 @@ impl Builder { /// The `AntiJoin` of `body`, whose variables `vars` the outer row gives /// where it binds them (spec §2). - fn anti(&self, body: &[WhereClause], vars: Vec) -> Option { - if !body - .iter() - .all(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) - { - return None; - } - Some(Step::Anti(self.sub(body, vars)?.0)) + fn anti(&self, body: &[WhereClause], vars: Vec) -> Result { + Ok(Step::Anti(self.sub(body, vars)?.0)) } /// The `Union` and `Distinct` of an `or` (`join` is `None`) or an /// `or-join` (spec §5). - fn union(&mut self, branches: &[Vec], join: Option>) -> Option<()> { - if self.source.is_none() { - // Nothing before the `or` binds a variable: its outer side is - // the empty row. - self.source = Some(Source::Seed); - self.steps.append(&mut self.front); - } + fn union(&mut self, branches: &[Vec], join: Option>) -> Result<()> { + // Nothing before the `or` binds a variable: its outer side is the + // empty row. + self.seed(); let mut subs = Vec::with_capacity(branches.len()); for branch in branches { let vars: Vec = match &join { // The parser requires every join variable bound before // (INT-031 on the executor otherwise). Some(j) if j.iter().all(|v| self.slots.by_var.contains_key(v)) => j.clone(), - Some(_) => return None, - None => optimizer::clause_ref_vars(branch).into_iter().collect(), + // The parser rejects it first (INT-018). + Some(j) => { + let v = j.iter().find(|v| !self.slots.by_var.contains_key(*v)); + bail_coded!(ErrorCode::Int031, v.map_or("?", String::as_str)); + } + None => reads(branch).into_iter().collect(), }; - let imports: HashSet = vars - .iter() - .filter(|v| self.slots.by_var.contains_key(*v)) - .cloned() - .collect(); - if !runs_branch(branch, &imports) { - return None; - } subs.push(self.sub(branch, vars)?); } // The variables a branch binds that the rows do not. Every branch of @@ -1080,7 +1156,8 @@ impl Builder { if k == 0 { names = own; } else if own != names { - return None; + // The parser rejects it first (PRS-057). + return Err(invariant("or branches bind different variables")); } } } @@ -1089,7 +1166,10 @@ impl Builder { for (body, slots) in subs { let mut new = Vec::with_capacity(names.len()); for (n, kind) in names.iter().zip(kinds.iter_mut()) { - let inner = *slots.by_var.get(n)?; + let inner = *slots + .by_var + .get(n) + .ok_or_else(|| invariant("a branch without an `or` variable"))?; *kind |= slots.kind(inner); new.push(inner); } @@ -1103,20 +1183,20 @@ impl Builder { let mut slots: Vec = self.slots.by_var.values().copied().collect(); slots.sort_unstable(); self.steps.push(Step::Distinct(slots)); - Some(()) + Ok(()) } /// The plan of a `not` body or an `or` branch whose variables `vars` /// the outer row gives where it binds them (spec §2), hashed or /// correlated (spec §4.4), and its slots. - fn sub(&self, body: &[WhereClause], vars: Vec) -> Option<(Body, Slots)> { + fn sub(&self, body: &[WhereClause], vars: Vec) -> Result<(Body, Slots)> { let mut imports: Vec<(String, usize)> = vars .into_iter() .filter_map(|v| self.slots.by_var.get(&v).map(|&s| (v, s))) .collect(); imports.sort_by_key(|&(_, s)| s); let seeded: HashSet = imports.iter().map(|(v, _)| v.clone()).collect(); - let (seeded_order, seeded_deferred) = optimizer::plan_seeded(body.to_vec(), &seeded); + let (seeded_order, _) = optimizer::plan_seeded(body.to_vec(), &seeded); // A probe per outer row holds nothing: correlated when the first // pattern's entity is imported. let probe = seeded_order @@ -1133,16 +1213,10 @@ impl Builder { optimizer::Subplans::Hash => hashable, optimizer::Subplans::Correlated => false, }; - let (as_of, valid) = (self.as_of, self.valid); + let valid = self.valid; if hash { - let mut b = Builder::new(None, as_of, valid, self.evaluated.clone()); - let (planned, deferred) = optimizer::plan(body.to_vec()); - for (c, _) in planned { - b.clause(c)?; - } - for c in sorted(deferred) { - b.clause(c)?; - } + let mut b = Builder::new(None, valid, self.evaluated.clone()); + clauses(&mut b, body, None, &HashSet::new())?; let keys = imports .iter() .filter_map(|(v, outer)| { @@ -1158,23 +1232,18 @@ impl Builder { .collect(); let slots = std::mem::take(&mut b.slots); let plan = Box::new(b.finish()?); - return Some((Body::Hashed { plan, keys }, slots)); + return Ok((Body::Hashed { plan, keys }, slots)); } - let mut b = Builder::new(None, as_of, valid, self.evaluated.clone()); + let mut b = Builder::new(None, valid, self.evaluated.clone()); for (v, outer) in &imports { let s = b.slots.add(self.slots.kind(*outer)); b.slots.by_var.insert(v.clone(), s); } b.source = Some(Source::Seed); - for (c, _) in seeded_order { - b.clause(c)?; - } - for c in sorted(seeded_deferred) { - b.clause(c)?; - } + clauses(&mut b, body, None, &seeded)?; let slots = std::mem::take(&mut b.slots); let plan = Box::new(b.finish()?); - Some(( + Ok(( Body::Correlated { plan, imports: imports.into_iter().map(|(_, s)| s).collect(), @@ -1192,38 +1261,20 @@ fn sorted(mut deferred: Vec) -> Vec { deferred } -/// Whether the engine runs `branch` of an `or` whose rows give `imports` -/// (decision 11 of the #546 plan). It holds patterns, expressions and -/// `not`s only (a rule invocation or a nested `or` stays on the executor), -/// and no predicate the registry may lack: the executor reports that only -/// when a row reaches it. The executor applies a branch's `not`s before its -/// expressions, so a `not` must not read a variable only an expression of -/// the branch binds. -fn runs_branch(branch: &[WhereClause], imports: &HashSet) -> bool { - let mut by_pattern: HashSet = imports.clone(); - let mut by_expr: HashSet<&str> = HashSet::new(); - for c in branch { +/// Every variable `clauses` name, at any depth: an `or-join` names its join +/// variables only. What a `not` body or `or` branch may import. +fn reads(clauses: &[WhereClause]) -> HashSet { + let mut vars = HashSet::new(); + for c in clauses { match c { - WhereClause::Pattern(p) => by_pattern.extend(optimizer::pattern_bound_vars(p)), - WhereClause::Expr { - expr: Expr::UnaryOp(UnaryOp::Udf(_), _), - .. - } => return false, - WhereClause::Expr { binding, .. } => by_expr.extend(binding.as_deref()), - WhereClause::Not(_) | WhereClause::NotJoin { .. } => {} - _ => return false, + WhereClause::Or(branches) => vars.extend(branches.iter().flat_map(|b| reads(b))), + WhereClause::OrJoin { join_vars, .. } => vars.extend(join_vars.iter().cloned()), + WhereClause::Not(body) => vars.extend(reads(body)), + WhereClause::NotJoin { join_vars, .. } => vars.extend(join_vars.iter().cloned()), + c => vars.extend(optimizer::clause_ref_vars(std::slice::from_ref(c))), } } - branch.iter().all(|c| { - let reads: Vec = match c { - WhereClause::Not(body) => optimizer::clause_ref_vars(body).into_iter().collect(), - WhereClause::NotJoin { join_vars, .. } => join_vars.clone(), - _ => return true, - }; - reads - .iter() - .all(|v| by_pattern.contains(v) || !by_expr.contains(v.as_str())) - }) + vars } /// Whether `p` is a per-fact pseudo-attribute pattern (it scans nothing). @@ -1256,12 +1307,15 @@ fn closed(body: &[WhereClause], imports: &HashSet) -> bool { .as_ref() .and_then(EdnValue::as_variable) .is_some_and(|v| bound.contains(v)), - WhereClause::Not(inner) => optimizer::clause_ref_vars(inner) + WhereClause::Not(inner) => reads(inner) .iter() .all(|v| !imports.contains(v) || bound.contains(v)), WhereClause::NotJoin { join_vars, .. } => join_vars .iter() .all(|v| !imports.contains(v) || bound.contains(v)), + c @ (WhereClause::Or(_) | WhereClause::OrJoin { .. }) => reads(std::slice::from_ref(c)) + .iter() + .all(|v| !imports.contains(v) || bound.contains(v)), _ => true, }) } @@ -1274,9 +1328,8 @@ fn join( attribute: &EdnValue, slots: &mut Slots, rebind: &[String], - as_of: Option, valid: Valid, -) -> Option { +) -> Result { let outer_width = slots.len(); let mut local = Slots::default(); let e = term(&q.entity, &mut local, OTHER, entity_const)?; @@ -1330,13 +1383,12 @@ fn join( } } } - Some(JoinSpec { + Ok(JoinSpec { inner: ScanSpec { e, a, v, meta: Vec::new(), - as_of, valid, width: local.len(), derived: None, @@ -1435,17 +1487,17 @@ fn expr_vars(expr: &Expr, slots: &Slots) -> Vars { out } -/// The term of one pattern position; `None` for a constant `konst` does not -/// take, or a symbol that is not a variable. +/// The term of one pattern position: a variable, a constant `konst` takes, +/// or `Never` for one it does not. fn term( edn: &EdnValue, slots: &mut Slots, kind: u8, konst: impl Fn(&EdnValue) -> Option, -) -> Option> { +) -> Result> { match edn { - EdnValue::Symbol(s) if s == "_" || s.starts_with("?_") => Some(Term::Any), - EdnValue::Symbol(s) if s.starts_with('?') => Some(match slots.by_var.get(s) { + EdnValue::Symbol(s) if s == "_" || s.starts_with("?_") => Ok(Term::Any), + EdnValue::Symbol(s) if s.starts_with('?') => Ok(match slots.by_var.get(s) { Some(&slot) => Term::Eq(slot), None => { let slot = slots.add(kind); @@ -1453,7 +1505,8 @@ fn term( Term::Bind(slot) } }), - EdnValue::Symbol(_) => None, - c => konst(c).map(Term::Const), + // The parser reads no other symbol in a pattern. + EdnValue::Symbol(_) => Err(invariant("a symbol that is not a variable")), + c => Ok(konst(c).map_or(Term::Never, Term::Const)), } } diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index daa58de311..207a64073d 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -18,9 +18,11 @@ use super::scan::Scan; use super::{Ctx, Operator, build}; use crate::error::{ErrorCode, err_coded}; use crate::graph::storage::Snapshot; +use crate::query::datalog::aggregate::type_name; use crate::query::datalog::evaluator::{derived_facts_exceeded, iterations_exceeded}; use crate::query::datalog::functions::FunctionRegistry; -use crate::storage::KeySource; +use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; +use crate::storage::{KeySource, TxBound}; use anyhow::Result; use std::collections::HashSet; use std::mem::size_of; @@ -42,6 +44,8 @@ pub(crate) struct Reads<'a> { pub(crate) snapshot: &'a Snapshot, pub(crate) keys: Option<&'a dyn KeySource>, pub(crate) functions: &'a FunctionRegistry, + /// The versions the query's `:as-of` keeps. + pub(crate) bound: &'a TxBound, } /// Derive every relation of `plan` into `rels`. @@ -111,7 +115,6 @@ fn know_stored( a: Term::Const(attr.clone()), v: Term::Bind(1), meta: Vec::new(), - as_of: plan.as_of, valid: plan.valid, width: 2, derived: None, @@ -159,12 +162,14 @@ fn heads( { let mut ctx = ctx(reads, ids, Some(rels)); let mut root = build(run.plan.source.clone(), run.plan.steps.clone(), meter); + // Constant head arguments' cells, read at the first row. + let mut konst: [Option; 2] = [None, None]; while let Some(batch) = root.next_batch(&mut ctx)? { for i in 0..batch.len { let cell = |slot: usize| batch.cols.get(slot).and_then(|c| c.get(i)); let row = [ - entity(&run.entity, predicate, cell, &mut ctx)?, - value(run.value.as_ref(), cell)?, + entity(&run.entity, predicate, cell, &mut ctx, &mut konst[0])?, + value(run.value.as_ref(), cell, &mut ctx, &mut konst[1])?, ]; if rels.known(rel, &row) { continue; @@ -204,19 +209,36 @@ fn ctx<'a>(reads: &Reads<'a>, ids: &'a mut IdSpace, derived: Option<&'a Relation ids, functions: reads.functions, derived, + bound: reads.bound, } } /// The head's entity cell (spec §5.3): an entity, or the entity a keyword -/// names; anything else is `QRY-013`. +/// names; anything else is `QRY-013`. A constant's is kept in `konst`. fn entity<'c>( arg: &HeadArg, predicate: &str, cell: impl Fn(usize) -> Option<&'c Cell>, ctx: &mut Ctx<'_>, + konst: &mut Option, ) -> Result { let kind = match arg { HeadArg::Unbound(v) => return Err(unbound(v)), + HeadArg::Const(c) => { + if let Some(k) = konst { + return Ok(k.clone()); + } + // As the executor reads a head (`evaluator.rs`). + let k = match edn_to_entity_id(c) { + Ok(u) => Cell::Eid(ctx.ids.eid(ctx.keys, &u)?), + Err(_) => { + let kind = edn_to_value(c).map_or("symbol", |v| type_name(&v)); + return Err(err_coded!(ErrorCode::Qry013, predicate, kind)); + } + }; + *konst = Some(k.clone()); + return Ok(k); + } HeadArg::Slot(s) => match cell(*s) { Some(Cell::Eid(e)) => return Ok(Cell::Eid(*e)), Some(Cell::Iid(i)) => return Ok(Cell::Eid(ctx.ids.keyword_eid(ctx.keys, *i)?)), @@ -235,11 +257,28 @@ fn entity<'c>( } /// The head's value cell: any value but `nil`, which the executor cannot -/// read back (`INT-022`); `true` for a one-argument head. -fn value<'c>(arg: Option<&HeadArg>, cell: impl Fn(usize) -> Option<&'c Cell>) -> Result { +/// read back (`INT-022`); `true` for a one-argument head. A constant's is +/// kept in `konst`. +fn value<'c>( + arg: Option<&HeadArg>, + cell: impl Fn(usize) -> Option<&'c Cell>, + ctx: &mut Ctx<'_>, + konst: &mut Option, +) -> Result { match arg { None => Ok(Cell::Val(Scalar::Bool(true))), Some(HeadArg::Unbound(v)) => Err(unbound(v)), + Some(HeadArg::Const(c)) => { + if let Some(k) = konst { + return Ok(k.clone()); + } + let v = edn_to_value(c).map_err(|e| { + err_coded!(ErrorCode::Int022, format!("Failed to convert value: {e}")) + })?; + let k = Cell::of_value(ctx.ids, ctx.keys, &v)?; + *konst = Some(k.clone()); + Ok(k) + } Some(HeadArg::Slot(s)) => match cell(*s) { Some(Cell::Val(Scalar::Null)) | None => Err(err_coded!( ErrorCode::Int022, diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 8a7fdb2bb1..5f825c4d2d 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -136,6 +136,7 @@ impl Operator for Scan { loop { let mut batch = Batch::new(self.spec.width); match &mut self.state { + State::Start if self.spec.never() => self.state = State::Done, State::Start if self .spec @@ -167,7 +168,7 @@ impl Operator for Scan { *index, prefix, c.resume.as_deref(), - self.spec.as_of, + ctx.bound, BATCH_ROWS, &mut self.keys_buf, )?; @@ -214,7 +215,7 @@ impl Operator for Scan { self.facts_buf.clear(); let more = ctx.snapshot.pending_live( range(&self.spec, self.probe.as_ref()), - self.spec.as_of, + ctx.bound, resume, BATCH_ROWS, &mut self.facts_buf, @@ -445,7 +446,7 @@ fn open( let mut shadow = HashSet::new(); for f in ctx .snapshot - .pending_records(range(spec, probe), spec.as_of)? + .pending_records(range(spec, probe), ctx.bound)? { if let Some(t) = committed_triple(keys, &f)? { shadow.insert(t); @@ -561,6 +562,7 @@ fn fill( ) -> Result { match term { Term::Any | Term::Const(_) => Ok(true), + Term::Never => Ok(false), Term::Bind(slot) => { if let Some(s) = row.get_mut(*slot) { *s = Some(cell()?); diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index d76829c5cb..ad230a0a0a 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -428,16 +428,117 @@ fn engine_reads_many_batches() { assert_eq!(rows(&db, "(query [:find ?e :where [?e :big/n 2999]])"), 1); } -/// The executor still runs what the engine does not: windows, `:as-of` a -/// timestamp. +/// A file built by `LogWriter` whose transaction `i + 1` has `tx_id` +/// `tx_ids[i]`: `:a :n 1` asserted, then retracted, `:a :n 2` and `:b :n 3` +/// asserted, `:b :n 3` retracted, `:a :n 1` asserted again. +fn written(dir: &std::path::Path, name: &str, tx_ids: [u64; 6]) -> std::path::PathBuf { + use crate::{FactRecord, LogWriter, Value}; + let path = dir.join(name); + let mut w = LogWriter::create(&path, crate::OpenOptions::new()).unwrap(); + let ops = [ + (":a", 1, true), + (":a", 1, false), + (":a", 2, true), + (":b", 3, true), + (":b", 3, false), + (":a", 1, true), + ]; + for (i, ((e, v, asserted), tx_id)) in ops.into_iter().zip(tx_ids).enumerate() { + w.append(&FactRecord { + entity: uuid_of(e), + attribute: ":n".to_string(), + value: Value::Integer(v), + tx_count: i as u64 + 1, + tx_id, + valid_from: 0, + valid_to: i64::MAX, + asserted, + }) + .unwrap(); + } + w.finish().unwrap(); + path +} + +/// `:as-of` a timestamp runs on the engine (#551 plan, step 4) and keeps the +/// versions the executor's `tx_id <= t` filter keeps: on a file whose +/// `tx_id`s rise and on one whose `tx_id`s fall and rise (a `LogWriter` +/// copy), at timestamps before, between, at and after its transactions, +/// with committed, pending and staged facts, in plain and rule queries, +/// point and attribute scans. The oracle checks every answer. #[test] -fn other_queries_stay_on_the_executor() { - let db = Minigraf::in_memory().unwrap(); - write_round(&db, 0); - for q in ["(query [:find ?e :as-of \"2099-01-01T00:00:00Z\" :where [?e :person/name ?n]])"] { - let before = runs(); - db.execute(q).unwrap(); - assert_eq!(runs(), before, "query stayed on the executor"); +fn as_of_timestamps_run_on_the_engine() { + let dir = tempfile::tempdir().unwrap(); + let iso = |ms: i64| { + let secs = ms.div_euclid(1000); + let (days, rem) = (secs.div_euclid(86_400), secs.rem_euclid(86_400)); + // Days since 1970-01-01 to a civil date (Howard Hinnant's algorithm). + let z = days + 719_468; + let era = z.div_euclid(146_097); + let doe = z - era * 146_097; + let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365; + let doy = doe - (365 * yoe + yoe / 4 - yoe / 100); + let mp = (5 * doy + 2) / 153; + let d = doy - (153 * mp + 2) / 5 + 1; + let m = if mp < 10 { mp + 3 } else { mp - 9 }; + let y = yoe + era * 400 + i64::from(m <= 2); + format!( + "{y:04}-{m:02}-{d:02}T{:02}:{:02}:{:02}.{:03}Z", + rem / 3600, + rem % 3600 / 60, + rem % 60, + ms.rem_euclid(1000) + ) + }; + let base: u64 = 1_600_000_000_000; + let files = [ + ("rising.graph", [1, 2, 3, 4, 5, 6].map(|k| base + k * 1000)), + ("falling.graph", [3, 1, 4, 2, 6, 5].map(|k| base + k * 1000)), + ]; + let mut stamps: Vec = vec![-1, 0, 1_000_000_000_000, 253_402_300_799_000]; + for k in 0..=7 { + let t = (base + k * 1000) as i64; + stamps.extend([t - 500, t, t + 1]); + } + let queries = [ + "[:find ?e ?v :as-of \"{t}\" :where [?e :n ?v]]", + "[:find ?v :as-of \"{t}\" :where [:a :n ?v]]", + "[:find ?e :as-of \"{t}\" :where [?e :n 1]]", + "[:find ?e ?v :as-of \"{t}\" :where (has ?e ?v)]", + ]; + for (name, tx_ids) in files { + let path = written(dir.path(), name, tx_ids); + let db = Minigraf::open(&path).unwrap(); + db.execute("(rule [(has ?e ?v) [?e :n ?v]])").unwrap(); + let run_all = |db: &Minigraf| { + for q in queries { + for &t in &stamps { + let q = format!("(query {})", q.replace("{t}", &iso(t))); + rows(db, &q); + } + } + }; + // Committed facts only. + run_all(&db); + // Pending facts on top, stamped now: after every committed one. + db.execute("(transact [[:c :n 4] [:a :n 2]])").unwrap(); + db.execute("(retract [[:a :n 1]])").unwrap(); + run_all(&db); + // The same, checkpointed into a new committed generation. + db.checkpoint().unwrap(); + run_all(&db); + // Staged facts in a write transaction. + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:d :n 5]])").unwrap(); + for q in queries { + for t in [stamps[3], (base + 3500) as i64] { + let q = format!("(query {})", q.replace("{t}", &iso(t))); + let before = runs(); + tx.execute(&q).unwrap(); + assert_eq!(runs(), before + 1, "staged reads run on the engine"); + } + } + tx.rollback(); } } @@ -1062,19 +1163,221 @@ fn negation_keeps_multiplicity() { ); } -/// An unknown predicate in a body fails on every body row, so the `not` -/// keeps every outer row (spec §3.3), on the engine as on the executor. +/// A clause list with no pattern to scan first starts from the empty row +/// (#551 plan, step 7): an expression before any pattern, in source order +/// and reordered; a `not` with nothing but an expression after it; an `or` +/// of expression-only branches; a rule body that binds before its pattern. #[test] -fn negation_unknown_predicate_keeps_rows() { +fn no_pattern_first() { let db = Minigraf::in_memory().unwrap(); db.execute("(transact [[:a :n 1] [:b :n 2]])").unwrap(); - assert_eq!( - rows( - &db, - "(query [:find ?e :where [?e :n ?v] (not [?e :n ?v] [(no-such-pred? ?v)])])" + db.execute("(rule [(two ?e ?k) [(+ 1 1) ?k] [?e :n ?k]])") + .unwrap(); + for reorder in [false, true] { + let _g = crate::query::datalog::optimizer::set_reorder(reorder); + for (q, n) in [ + ("[:find ?e ?k :where [(+ 1 1) ?k] [?e :n ?k]]", 1), + ("[:find ?k :where (not [:a :n 7]) [(+ 1 1) ?k]]", 1), + ("[:find ?k :where (not [:a :n 1]) [(+ 1 1) ?k]]", 0), + ("[:find ?k :where [(+ 1 1) ?k] (not [:a :n 1])]", 0), + ("[:find ?k :where (or [(+ 1 1) ?k] [(+ 2 2) ?k])]", 2), + ("[:find ?e :where (two ?e 2)]", 1), + ("[:find ?e ?k :where (two ?e ?k)]", 1), + ] { + assert_eq!(rows(&db, &format!("(query {q})")), n, "{q}"); + } + } +} + +/// A `not` body is planned as a `:where` is (#551 plan, step 8), hashed or +/// correlated, with a rule invocation in it; the parser rejects a nested +/// `not`, `not-join` or `or` before the planner sees one. +#[test] +fn not_bodies_plan_as_clause_lists() { + use crate::query::datalog::optimizer::{Subplans, set_subplans}; + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact [[:a :n 1] [:a :ok true] [:b :n 2] [:c :n 3] [:c :ok true] [:d :n 4] [:d :tag :x]])", + ) + .unwrap(); + db.execute("(rule [(okay ?e) [?e :ok true]])").unwrap(); + db.execute("(rule [(plain ?e) [?e :n ?v] (not (okay ?e) [(< ?v 3)])])") + .unwrap(); + for (q, code) in [ + ( + "[:find ?e :where [?e :n ?v] (not [?e :ok true] (not [?e :tag :x]))]", + "PRS-051", ), - 2 + ( + "[:find ?e :where [?e :n ?v] (not [?f :n ?w] (not-join [?f] [?f :ok true]))]", + "PRS-093", + ), + ( + "[:find ?e :where [?e :n ?v] (not (or [?e :ok true] [?e :tag :x]))]", + "INT-016", + ), + ] { + let err = db.execute(&format!("(query {q})")).expect_err(q); + assert_eq!(err.code(), code, "{q}"); + } + for mode in [Subplans::Choose, Subplans::Hash, Subplans::Correlated] { + let _m = set_subplans(mode); + for (q, n) in [ + ("[:find ?e :where [?e :n ?v] (not (okay ?e) [(< ?v 3)])]", 3), + ("[:find ?e :where (plain ?e)]", 3), + ( + "[:find ?e :where [?e :n ?v] (not-join [?v] (okay ?f) [?f :n ?w] [(> ?w ?v)])]", + 2, + ), + ] { + assert_eq!(rows(&db, &format!("(query {q})")), n, "{q}"); + } + } +} + +/// Constants the planner used to refuse run on the engine (#551 plan, step +/// 9): a magic-set head constant (#608), a value constant in an +/// invocation's entity position, and every constant no cell can equal. +#[test] +fn constants_run_on_the_engine() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :link :b] [:b :link :c] [:a :n 1] [:b :n 2]])") + .unwrap(); + for rule in [ + "(rule [(chain ?x ?y) [?x :link ?y]])", + "(rule [(chain ?x ?z) [?x :link ?y] (chain ?y ?z)])", + "(rule [(named ?n ?e) [?e :name ?n]])", + ] { + db.execute(rule).unwrap(); + } + assert_eq!(rows(&db, "(query [:find ?x :where (chain ?x :c)])"), 2); + assert_eq!(rows(&db, "(query [:find ?y :where (chain :a ?y)])"), 2); + // No rule derives a row: nothing to match. + assert_eq!( + rows(&db, r#"(query [:find ?e :where (named "alice" ?e)])"#), + 0 ); + for q in [ + r#"[:find ?v :where ["a" :n ?v]]"#, + "[:find ?v :where [1 :n ?v]]", + "[:find ?v :where [true :n ?v]]", + "[:find ?v :where [nil :n ?v]]", + "[:find ?v :where [1.5 :n ?v]]", + r#"[:find ?e :where [?e "n" ?v]]"#, + "[:find ?e :where [?e 3 ?v]]", + "[:find ?e :where [?e :n [1 2]]]", + "[:find ?e :where [?e :n {:a 1}]]", + "[:find ?e :where [?e :n (1 2)]]", + "[:find ?e :where [?e :link ?b] [?b :n [1]]]", + ] { + assert_eq!(rows(&db, &format!("(query {q})")), 0, "{q}"); + } + // A derived head entity that is a value fails the query, as on the + // executor. + db.execute(r#"(transact [[:p :name "alice"]])"#).unwrap(); + let err = db + .execute(r#"(query [:find ?e :where (named "alice" ?e)])"#) + .expect_err("a string head entity"); + assert_eq!(err.code(), "QRY-013"); +} + +/// The errors the planner raises keep the codes the executor reports (#551 +/// plan, step 10), after the pseudo-attribute check and before unknown +/// predicates; the parser rejects the other shapes first. +#[test] +fn planner_errors_keep_their_codes() { + use crate::query::datalog::parser::parse_datalog_command; + use crate::query::datalog::types::DatalogCommand; + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :e :b] [:b :e :c] [:a :n 1]])") + .unwrap(); + for rule in [ + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(none) [?x :e ?y]])", + "(rule [(wide ?x ?y ?z) [?x :e ?y] [?y :e ?z]])", + ] { + db.execute(rule).unwrap(); + } + // Arguments after a head's second are ignored, as on the executor. + assert_eq!(rows(&db, "(query [:find ?x ?y :where (wide ?x ?y)])"), 1); + for (q, code) in [ + ("[:find ?x :where (reach ?x ?y ?z)]", "INT-028"), + ( + "[:find ?x :where [?x :n ?v] (or-join [?x] (reach ?x ?y ?z) [?x :n 1])]", + "INT-028", + ), + ("[:find ?x :where (none ?x)]", "INT-022"), + // G and H: the parser rejects them first. + ( + "[:find ?x :where [?x :n ?v] (or (reach ?x ?y ?z) [?x :n 1])]", + "PRS-057", + ), + ( + "[:find ?x :where [?x :n ?v] (or-join [?q] [?q :n 1] [?q :e :b])]", + "INT-018", + ), + // Pseudo-attributes, then the rules, then unknown predicates. + ( + "[:find ?x :where [?x :n ?v] [?x :db/tx-count ?t] (reach ?x ?y ?z) [(no-such? ?v)]]", + "INT-026", + ), + ( + "[:find ?x :where [?x :n ?v] (reach ?x ?y ?z) [(no-such? ?v)]]", + "INT-028", + ), + ( + "[:find ?x :where [?x :n ?v] [?x :db/tx-count ?t] [(no-such? ?v)]]", + "INT-026", + ), + ( + "[:find ?x :where [?x :n ?v] (reach ?x ?y) [(no-such? ?v)]]", + "QRY-007", + ), + ] { + let err = db.execute(&format!("(query {q})")).expect_err(q); + assert_eq!(err.code(), code, "{q}"); + } + // Slots, which a prepared query substitutes first. + for (q, code) in [ + ( + "(query [:find ?e :valid-at $t :where [?e :n ?v]])", + "INT-025", + ), + ("(query [:find ?e :as-of $t :where [?e :n ?v]])", "INT-032"), + ] { + let Ok(DatalogCommand::Query(query)) = parse_datalog_command(q) else { + panic!("a query"); + }; + match super::plan(&query) { + Err(e) => { + assert_eq!(crate::MinigrafError::from(e).code(), code, "{q}") + } + _ => panic!("a planner error"), + } + } + // A registry no definition builds (`register_rule` rejects it): the + // stratification error, INT-054. + let mut registry = crate::query::datalog::rules::RuleRegistry::new(); + for (p, text) in [ + ("p", "(rule [(p ?x ?y) [?x :e ?y] (not (q ?x ?y))])"), + ("q", "(rule [(q ?x ?y) [?x :e ?y] (not (p ?x ?y))])"), + ] { + let Ok(DatalogCommand::Rule(rule)) = parse_datalog_command(text) else { + panic!("a rule"); + }; + registry.insert_unchecked(p, rule); + } + let Ok(DatalogCommand::Query(query)) = + parse_datalog_command("(query [:find ?x :where (p ?x ?y)])") + else { + panic!("a query"); + }; + match super::plan_rules(&query, ®istry, &[]) { + Err(e) => { + assert_eq!(crate::MinigrafError::from(e).code(), "INT-054") + } + _ => panic!("a planner error"), + } } /// A correlated body probes once per outer row from its seed; a hashed one @@ -1274,10 +1577,9 @@ fn disjunction_matches_executor() { } /// Which disjunctions the engine runs (#546 PR 2): `or` / `or-join` whose -/// branches hold patterns, expressions, `not`s and rule invocations (#548); -/// a nested `or`, a predicate the registry may lack, an `or` whose branches -/// bind their own sources' metadata, and a branch `not` reading what only -/// the branch's expression binds stay on the executor (decision 11). +/// branches hold patterns, expressions, `not`s, rule invocations (#548), +/// nested `or`s and predicates (#551). An `or` whose branches bind their own +/// sources' metadata is rejected by the parser (PRS-057). #[test] fn disjunction_routing() { let db = Minigraf::in_memory().unwrap(); @@ -1290,19 +1592,14 @@ fn disjunction_routing() { "(query [:find ?e :where [?e :person/name ?n] (or (and [?e :person/ok true] (not [?e :person/age 21])) [?e :person/age 22])])", "(query [:find ?e :any-valid-time :where [?e :person/name ?n] (or-join [?e] (and [?f :person/age ?a] [?f :db/tx-count ?t]) [?e :person/ok true])])", "(query [:find ?e :where [?e :person/name ?n] (or (okay ?e) [?e :person/age 21])])", - ] { - rows(&db, q); - } - for q in [ "(query [:find ?e :where [?e :person/name ?n] (or (or [?e :person/ok true] [?e :person/age 22]) [?e :person/age 21])])", - "(query [:find ?e :where [?e :person/age ?a] (or (and [?e :person/ok true] [(no-such-pred? ?a)]) [?e :person/age 21])])", - "(query [:find ?e :any-valid-time :where [?e :person/name ?n] (or (and [?e :person/age ?a] [?e :db/tx-count ?t]) (and [?e :person/score ?a] [?e :db/tx-id ?t]))])", - "(query [:find ?e :where [?e :person/age ?a] (or (and [(+ ?a 1) ?b] (not [?f :person/age ?b])) (and [(+ ?a 2) ?b] [?e :person/ok true]))])", ] { - let before = runs(); - let _ = db.execute(q); - assert_eq!(runs(), before, "query stayed on the executor"); + rows(&db, q); } + let err = db + .execute("(query [:find ?e :any-valid-time :where [?e :person/name ?n] (or (and [?e :person/age ?a] [?e :db/tx-count ?t]) (and [?e :person/score ?a] [?e :db/tx-id ?t]))])") + .expect_err("hidden variables differ"); + assert_eq!(err.code(), "PRS-057"); } /// The branch forms the planner chooses: as a `not` body's (spec §4.4, @@ -1789,6 +2086,17 @@ fn rule_query_routing() { } assert_eq!(rows(&db, "(query [:find ?x ?y :where (reach ?x ?y)])"), 3); assert_eq!(rows(&db, "(query [:find ?y :where (reach :a ?y)])"), 2); + assert_eq!(rows(&db, "(query [:find ?x :where (deep ?x ?y)])"), 1); + // A body with no pattern runs on the engine, which finds its head + // entity is a number, as the executor does. + let err = db + .execute("(query [:find ?x ?v :where (one ?x ?v)])") + .expect_err("an integer head entity"); + assert_eq!(err.code(), "QRY-013"); + for (at, n) in [("2020-01-01T00:00:00Z", 0), ("2100-01-01T00:00:00Z", 3)] { + let q = format!("(query [:find ?x ?y :as-of \"{at}\" :where (reach ?x ?y)])"); + assert_eq!(rows(&db, &q), n, "an :as-of timestamp runs on the engine"); + } assert_eq!( rows( &db, @@ -1796,16 +2104,11 @@ fn rule_query_routing() { ), 1 ); - for q in [ - "(query [:find ?x ?y :as-of \"2020-01-01T00:00:00Z\" :where (reach ?x ?y)])", - "(query [:find ?x ?v :where (one ?x ?v)])", - "(query [:find ?x :where (deep ?x ?y)])", - "(query [:find ?x :where (reach ?x ?y ?z)])", - ] { - let before = runs(); - let _ = db.execute(q); - assert_eq!(runs(), before, "query stayed on the executor"); - } + // Three arguments: the executor's INT-028, from the planner. + let err = db + .execute("(query [:find ?x :where (reach ?x ?y ?z)])") + .expect_err("three arguments"); + assert_eq!(err.code(), "INT-028"); let before = runs(); let mut tx = db.begin_write().unwrap(); tx.execute("(transact [[:c :e :d]])").unwrap(); @@ -2144,6 +2447,7 @@ fn pull_once( ids: &mut ids, functions: &functions, derived: None, + bound: &crate::storage::TxBound::All, }; op.next_batch(&mut ctx) } diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 97d1f5e131..a6415650f8 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -94,11 +94,13 @@ impl<'a> DictReader<'a> { } /// Record a known `eid → uuid` pair (the caller looked the eid up by it). + #[cfg(any(test, feature = "test-oracle"))] pub fn seed_entity(&mut self, eid: u64, uuid: Uuid) { self.uuids.insert(eid, uuid); } /// Record a known `iid → ident` pair. + #[cfg(any(test, feature = "test-oracle"))] pub fn seed_ident(&mut self, iid: u32, ident: &str) { self.names.insert(iid, ident.to_string()); } diff --git a/src/storage/mod.rs b/src/storage/mod.rs index e4e14e3b1b..012993a7d9 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -30,6 +30,7 @@ pub(crate) mod verify; use crate::error::{ErrorCode, bail_coded, err_coded}; use anyhow::Result; +use std::sync::Arc; /// Read a 4-byte little-endian u32 from `bytes` at `offset`. fn read_u32_le(bytes: &[u8], offset: usize) -> anyhow::Result { @@ -368,19 +369,23 @@ impl Default for LegacyHeaderV7 { /// order. pub trait CommittedReader: Send + Sync { /// Every committed fact (an EAVT scan). + #[cfg(any(test, feature = "test-oracle"))] fn all_facts(&self) -> Result>; /// Every committed fact of `entity`. + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_entity( &self, entity: &crate::graph::types::EntityId, ) -> Result>; /// Every committed fact of `(entity, attribute)`. + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_entity_attribute( &self, entity: &crate::graph::types::EntityId, attribute: &str, ) -> Result>; /// Every committed fact with `attribute` (an AEVT scan). + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_attribute(&self, attribute: &str) -> Result>; /// The committed facts of `scan` that survive net-assert among the @@ -393,6 +398,7 @@ pub trait CommittedReader: Send + Sync { /// newer than each committed one and a record can only be hidden by a newer /// one. This default reads the history and filters it; `OnDiskReader` /// decides on index keys and translates only the survivors. + #[cfg(any(test, feature = "test-oracle"))] fn live_facts( &self, scan: Scan<'_>, @@ -422,6 +428,81 @@ pub trait CommittedReader: Send + Sync { } } +/// The fact versions a read keeps, by transaction (#551 plan, decision 3). +#[derive(Debug, Clone)] +pub enum TxBound { + /// Every version. + All, + /// The versions with `tx_count <= n`. + Upto(u64), + /// `:as-of t` where `tx_id` does not rise with `tx_count`: committed + /// keys whose `tx_count` is in one of the sorted, disjoint, inclusive + /// ranges `committed` (the transactions with `tx_id <= t`, from the + /// DICT, which holds one `tx_id` per `tx_count`), and pending and staged + /// facts with `tx_id <= t`. + Timestamp { + t: u64, + committed: Arc<[(u64, u64)]>, + }, +} + +impl TxBound { + /// The bound of a counter `:as-of`, or of none. + #[cfg(any(test, feature = "test-oracle"))] + pub fn of(as_of: Option) -> Self { + match as_of { + Some(n) => TxBound::Upto(n), + None => TxBound::All, + } + } + + /// Whether a committed key of transaction `tx` is kept. + pub fn keeps_key(&self, tx: u64) -> bool { + match self { + TxBound::All => true, + TxBound::Upto(n) => tx <= *n, + TxBound::Timestamp { committed, .. } => { + let i = committed.partition_point(|&(_, last)| last < tx); + committed.get(i).is_some_and(|&(first, _)| first <= tx) + } + } + } + + /// The newest transaction before `tx` whose committed keys are kept, if + /// any: where a walk past the newer ones seeks to. + pub fn kept_below(&self, tx: u64) -> Option { + let below = tx.checked_sub(1)?; + match self { + TxBound::All => Some(below), + TxBound::Upto(n) => Some(below.min(*n)), + TxBound::Timestamp { committed, .. } => { + let i = committed.partition_point(|&(first, _)| first <= below); + let (_, last) = *committed.get(i.checked_sub(1)?)?; + Some(last.min(below)) + } + } + } + + /// Whether a pending or staged fact is kept. + pub fn keeps_fact(&self, f: &crate::graph::types::Fact) -> bool { + match self { + TxBound::All => true, + TxBound::Upto(n) => f.tx_count <= *n, + TxBound::Timestamp { t, .. } => f.tx_id <= *t, + } + } +} + +/// How the `tx_id`s of a generation's transactions run (#551 plan, +/// decision 6). +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct TxOrder { + /// Whether no `tx_id` is below the one of an earlier `tx_count`. + pub monotonic: bool, + /// The `(tx_count, tx_id)` of the newest transaction, if there is one. + pub last: Option<(u64, u64)>, +} + /// Key-level reads of one committed generation: the dictionary and the live /// keys of each index (#473 spec §5, §6.1). /// @@ -443,8 +524,18 @@ pub trait KeySource: Send + Sync { fn long_value_ref(&self, s: &str) -> Result>; /// The `tx_id` of the committed transaction `tx_count`. fn tx_id_of(&self, tx_count: u64) -> Result; - /// The keys of `index` that start with `prefix` and survive net-assert at - /// `as_of`, decoded, appended to `out` in key order. + /// How this generation's `tx_id`s run; one walk of the DICT's + /// transactions per reader. + fn tx_order(&self) -> Result; + /// The newest `tx_count` whose `tx_id <= t`, 0 if none. Only for a + /// generation whose `tx_order` is monotonic. + fn last_tx_at(&self, t: u64) -> Result; + /// Append to `out` the transactions with `tx_id <= t` as sorted, + /// disjoint, inclusive `tx_count` ranges. + fn tx_runs(&self, t: u64, out: &mut Vec<(u64, u64)>) -> Result<()>; + /// The keys of `index` that start with `prefix` and survive net-assert + /// among the versions `bound` keeps, decoded, appended to `out` in key + /// order. /// /// Starts after the triple `resume` (from the start when `None`). Stops /// at the first triple boundary once `max` keys are out, and returns the @@ -455,7 +546,7 @@ pub trait KeySource: Send + Sync { index: keys::Index, prefix: &[u8], resume: Option<&[u8]>, - as_of: Option, + bound: &TxBound, max: usize, out: &mut Vec, ) -> Result>>; diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 783c4f3dd6..158d06620b 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -932,6 +932,8 @@ fn encode( mod tests { use super::*; use crate::graph::types::Value; + use crate::query::datalog::types::AsOf; + use crate::storage::TxBound; use crate::storage::backend::FaultInjectingBackend; use crate::storage::backend::MemoryBackend; use crate::storage::btree::collect_leaf_pages; @@ -2502,6 +2504,226 @@ mod tests { } } + /// One fact per transaction `(tx_count, tx_id)` of `txs`, entities from + /// `first`, loaded into `pfs` as `LogWriter` loads them. + fn load_txs(pfs: &PersistentFactStorage, first: u128, txs: &[(u64, u64)]) { + for (i, &(tx_count, tx_id)) in txs.iter().enumerate() { + let fact = Fact { + entity: entity(first + i as u128), + attribute: ":t/n".to_string(), + value: Value::Integer(i as i64), + tx_id, + tx_count, + valid_from: 0, + valid_to: crate::graph::types::VALID_TIME_FOREVER, + asserted: true, + }; + assert!(pfs.storage().load_fact(fact).unwrap(), "loaded"); + } + } + + /// A database whose committed transactions are `committed` and whose + /// pending ones are `pending`. + fn with_txs( + committed: &[(u64, u64)], + pending: &[(u64, u64)], + ) -> PersistentFactStorage { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 32).unwrap(); + load_txs(&pfs, 0, committed); + pfs.mark_dirty(); + pfs.save().unwrap(); + load_txs(&pfs, 1000, pending); + pfs + } + + /// The DICT's transaction reads (#551): `tx_order`, `last_tx_at` with + /// gaps in `tx_count`, before the first and after the last transaction, + /// and `tx_runs` on alternating `tx_id`s, each against every committed + /// fact with the executor's `tx_id <= t` filter. + #[test] + fn dict_transaction_reads_match_a_scan() { + let rising = [(1, 100), (2, 200), (4, 400), (7, 400), (9, 900)]; + let alternating = [(1, 100), (2, 300), (3, 150), (4, 400), (6, 200)]; + for (txs, monotonic) in [ + (&rising[..], true), + (&alternating[..], false), + (&[][..], true), + ] { + let pfs = with_txs(txs, &[]); + let snap = pfs.storage().snapshot().unwrap(); + // An empty save writes a generation too: its DICT has no + // transactions. + let reader = snap.committed.as_ref().expect("a committed generation"); + let src = reader.key_source().expect("keys"); + let order = src.tx_order().unwrap(); + assert_eq!(order.monotonic, monotonic, "tx_order"); + assert_eq!(order.last, txs.last().copied(), "newest transaction"); + assert_eq!(src.tx_order().unwrap(), order, "cached"); + let all = reader.all_facts().unwrap(); + for t in [ + 0, + 99, + 100, + 101, + 150, + 200, + 250, + 300, + 399, + 400, + 401, + 900, + 901, + u64::MAX, + ] { + let kept: BTreeSet = all + .iter() + .filter(|f| f.tx_id <= t) + .map(|f| f.tx_count) + .collect(); + if monotonic { + assert_eq!( + src.last_tx_at(t).unwrap(), + kept.last().copied().unwrap_or(0), + "last_tx_at" + ); + } + let mut runs = Vec::new(); + src.tx_runs(t, &mut runs).unwrap(); + assert!(runs.windows(2).all(|w| w[0].1 < w[1].0), "sorted, disjoint"); + assert!(runs.iter().all(|r| r.0 <= r.1), "inclusive"); + let bound = TxBound::Timestamp { + t, + committed: runs.into(), + }; + for f in &all { + assert_eq!(bound.keeps_key(f.tx_count), f.tx_id <= t, "tx_runs"); + } + for tx in 0..12 { + let below = (0..tx).rev().find(|&c| kept.contains(&c)); + if let Some(b) = bound.kept_below(tx) { + assert!(below <= Some(b), "the newest kept below or later"); + assert!(b < tx, "below the passed-over transaction"); + assert!((b + 1..tx).all(|c| !kept.contains(&c)), "skips none kept"); + } else { + assert!(below.is_none(), "nothing kept below"); + } + } + } + } + } + + /// `Snapshot::tx_bound` keeps the versions the executor's `tx_id <= t` + /// filter keeps (#551), over committed and pending facts, and is a + /// counter bound exactly when `tx_id` rises with `tx_count` over both. + #[test] + fn tx_bound_keeps_what_the_executor_filter_keeps() { + let cases: [(&[(u64, u64)], &[(u64, u64)], bool); 6] = [ + (&[(1, 100), (2, 200), (4, 400)], &[(5, 500), (6, 600)], true), + (&[(1, 100), (2, 200)], &[], true), + (&[], &[(1, 100), (2, 200), (2, 200)], true), + // `tx_id`s fall and rise (a `LogWriter` copy). + (&[(1, 300), (2, 100), (3, 200)], &[(4, 350)], false), + // Pending below committed. + (&[(1, 100), (2, 200)], &[(3, 150)], false), + // Two `tx_id`s in one pending `tx_count` (a read-only v7 open). + (&[(1, 100)], &[(2, 200), (2, 210), (3, 300)], false), + ]; + for (committed, pending, monotonic) in cases { + let pfs = with_txs(committed, pending); + let snap = pfs.storage().snapshot().unwrap(); + let stored = match &snap.committed { + Some(r) => r.all_facts().unwrap(), + None => Vec::new(), + }; + let pending = snap.pending_range(0, usize::MAX).unwrap(); + let all = snap.all_facts().unwrap(); + for t in [ + -5, 0, 99, 100, 150, 199, 200, 205, 210, 250, 300, 350, 400, 500, 600, 700, + ] { + let want: BTreeSet<(Uuid, u64)> = + crate::graph::storage::filter_facts_as_of(all.clone(), &AsOf::Timestamp(t)) + .into_iter() + .map(|f| (f.entity, f.tx_count)) + .collect(); + let bound = snap.tx_bound(t).unwrap(); + assert_eq!( + matches!(bound, TxBound::Upto(_)), + monotonic || t < 0, + "a counter exactly when monotonic" + ); + let got: BTreeSet<(Uuid, u64)> = stored + .iter() + .filter(|f| bound.keeps_key(f.tx_count)) + .chain(pending.iter().filter(|f| bound.keeps_fact(f))) + .map(|f| (f.entity, f.tx_count)) + .collect(); + assert!(got == want, "same versions as the executor"); + } + } + } + + /// `live_keys` under a `TxBound::Timestamp` (#551) equals net-assert + /// over the committed records whose `tx_count` is in its ranges, for + /// several range sets over transactions `1..=now`. + fn assert_live_keys_in_ranges(pfs: &PersistentFactStorage, now: u64) { + use crate::storage::keys::Index; + let snap = pfs.storage().snapshot().unwrap(); + let reader = snap.committed.as_ref().expect("a committed generation"); + let src = reader.key_source().expect("keys"); + let all = reader.all_facts().unwrap(); + let sets: [Vec<(u64, u64)>; 5] = [ + vec![], + vec![(1, now)], + vec![(1, now / 3), (now / 2, now / 2 + 1)], + (1..=now).step_by(2).map(|c| (c, c)).collect(), + vec![(now / 4 + 1, now - 1)], + ]; + let key = |f: &Fact| { + ( + f.entity, + f.attribute.clone(), + f.tx_count, + f.valid_from, + f.valid_to, + ) + }; + for set in sets { + let bound = TxBound::Timestamp { + t: 0, + committed: set.into(), + }; + let want: BTreeSet<_> = crate::graph::storage::net_asserted_facts( + all.iter() + .filter(|f| bound.keeps_key(f.tx_count)) + .cloned() + .collect(), + ) + .iter() + .map(key) + .collect(); + let mut out = Vec::new(); + src.live_keys(Index::Eavt, &[], None, &bound, usize::MAX, &mut out) + .unwrap(); + let got: BTreeSet<_> = out + .iter() + .map(|kf| { + ( + src.uuid_of(kf.e).unwrap(), + src.ident_of(kf.a).unwrap(), + kf.tx_count, + kf.vf, + kf.vt, + ) + }) + .collect(); + assert!( + got == want, + "live keys in ranges equal net-assert over them" + ); + } + } + /// The committed live read of `scan` taken by `live_keys` in calls of at /// most `max` keys, resumed after each, equals one `live_facts` read: the /// same records in the same order, for every `max`. @@ -2547,7 +2769,14 @@ mod tests { loop { let mut out = Vec::new(); resume = src - .live_keys(index, &prefix, resume.as_deref(), as_of, max, &mut out) + .live_keys( + index, + &prefix, + resume.as_deref(), + &crate::storage::TxBound::of(as_of), + max, + &mut out, + ) .unwrap(); calls += 1; for kf in out { @@ -2639,6 +2868,7 @@ mod tests { ]; assert_live_reads_match(&pfs, &model, &scans, &as_ofs); assert_live_keys_resume(&pfs, &scans, &as_ofs); + assert_live_keys_in_ranges(&pfs, now); } // Pending facts on top of committed ones. for _ in 0..12 { diff --git a/src/storage/reader.rs b/src/storage/reader.rs index 5c978bc95a..1cfded2639 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -5,14 +5,18 @@ use crate::error::{ErrorCode, bail_coded}; use crate::graph::types::{EntityId, Fact}; -use crate::storage::btree::{LeafCursor, MutexStorageBackend, prefix_scan}; +#[cfg(any(test, feature = "test-oracle"))] +use crate::storage::Scan; +#[cfg(any(test, feature = "test-oracle"))] +use crate::storage::btree::prefix_scan; +use crate::storage::btree::{LeafCursor, MutexStorageBackend}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, SharedDictCache}; use crate::storage::keys::{self, Index, KeyFact, ValueRef}; use crate::storage::meta::MetaPage; -use crate::storage::{CommittedReader, KeySource, LogSource, Scan, StorageBackend}; +use crate::storage::{CommittedReader, KeySource, LogSource, StorageBackend, TxBound, TxOrder}; use anyhow::Result; -use std::sync::{Arc, Mutex}; +use std::sync::{Arc, Mutex, OnceLock}; /// [`CommittedReader`] over one committed meta's trees. pub struct OnDiskReader { @@ -27,6 +31,8 @@ pub struct OnDiskReader { next_iid: u32, last_tx: u64, shared: SharedDictCache, + /// How the generation's `tx_id`s run, read on first use (#551). + tx_order: OnceLock, } impl OnDiskReader { @@ -43,6 +49,7 @@ impl OnDiskReader { next_iid: meta.next_iid, last_tx: meta.last_checkpointed_tx_count, shared: SharedDictCache::default(), + tx_order: OnceLock::new(), } } @@ -51,6 +58,7 @@ impl OnDiskReader { } /// Facts of every `index` entry starting with `prefix`. + #[cfg(any(test, feature = "test-oracle"))] fn scan( &self, index: Index, @@ -69,9 +77,38 @@ impl OnDiskReader { } impl OnDiskReader { + /// Visit the DICT's transactions `(tx_count, tx_id)` in `tx_count` order, + /// from `from` on (all when `None`), until `visit` returns false. + fn dict_txs( + &self, + from: Option, + visit: &mut dyn FnMut(u64, u64) -> Result, + ) -> Result<()> { + if self.dict_root == 0 { + return Ok(()); + } + let prefix = [keys::DICT_TX]; + let mut cursor = + LeafCursor::new(self.dict_root, Some(&prefix), &self.backend, &self.cache)?; + if let Some(m) = from { + cursor.seek(&keys::dict_tx_key(m))?; + } + while let Some((k, v)) = cursor.next_ref()? { + let Some(rest) = k.strip_prefix(&prefix) else { + break; + }; + let tx_count = keys::Reader::new(rest).uint()?; + if !visit(tx_count, keys::read_uint_bytes(v)?)? { + break; + } + } + Ok(()) + } + /// Facts of `index` entries starting with `prefix` that survive net-assert /// at `as_of`, decided on the key bytes (#379, spec §5.3). Only kept /// entries are decoded and translated through the dictionary. + #[cfg(any(test, feature = "test-oracle"))] fn live_scan( &self, index: Index, @@ -81,7 +118,8 @@ impl OnDiskReader { dict: &mut DictReader<'_>, ) -> Result> { let mut out = Vec::new(); - self.live_walk(index, root, prefix, None, as_of, usize::MAX, &mut |k| { + let bound = TxBound::of(as_of); + self.live_walk(index, root, prefix, None, &bound, usize::MAX, &mut |k| { out.push(dict.fact(&KeyFact::decode(index, k)?)?); Ok(()) })?; @@ -98,14 +136,15 @@ impl OnDiskReader { } /// Visit the keys of `index` entries starting with `prefix` that survive - /// net-assert at `as_of`, in key order, starting after the triple `resume`. + /// net-assert among the versions `bound` keeps, in key order, starting + /// after the triple `resume`. /// /// 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 + /// transaction `bound` keeps 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 + /// triple is hidden. Entries of transactions `bound` does not keep 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. @@ -120,7 +159,7 @@ impl OnDiskReader { root: u64, prefix: &[u8], resume: Option<&[u8]>, - as_of: Option, + bound: &TxBound, max: usize, visit: &mut dyn FnMut(&[u8]) -> Result<()>, ) -> Result>> { @@ -145,7 +184,7 @@ impl OnDiskReader { let step = match cursor.next_ref()? { Some((k, _)) if k.starts_with(prefix) => { if dead && k.starts_with(&triple) { - Step::Pass(Some(0xFF)) + Step::Pass(Seek::Triple) } else { let n = keys::triple_len(index, k)?; let (key_triple, rest) = k.split_at(n); @@ -162,8 +201,11 @@ impl OnDiskReader { dead = false; skipped = 0; } - if as_of.is_some_and(|limit| tx > limit) { - Step::Pass(None) + if !bound.keeps_key(tx) { + Step::Pass(match bound.kept_below(tx) { + Some(older) => Seek::Tx(older), + None => Seek::Triple, + }) } else { let retraction = k.last() == Some(&0); Step::Entry { @@ -184,10 +226,9 @@ impl OnDiskReader { if skipped >= SEEK_AFTER { skipped = 0; let mut target = triple.clone(); - match (past, as_of) { - (Some(b), _) => target.push(b), - (None, Some(limit)) => keys::put_tx_desc(&mut target, limit), - (None, None) => {} + match past { + Seek::Triple => target.push(0xFF), + Seek::Tx(older) => keys::put_tx_desc(&mut target, older), } cursor.seek(&target)?; } @@ -217,13 +258,21 @@ const SEEK_AFTER: usize = 8; /// What the walk does with one entry. enum Step { - /// Pass over it; a seek past the run appends this byte to the triple - /// (`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. + /// Pass over it; a seek past the run goes to `Seek`. + Pass(Seek), + /// An entry of a transaction the bound keeps; `key` is kept for + /// assertions only. Entry { tx: u64, key: Option> }, } +/// Where a seek past passed-over entries of one triple goes. +enum Seek { + /// Past the whole triple. + Triple, + /// To the triple's entries of this transaction and older. + Tx(u64), +} + /// The entries of one triple with one `tx_count`. #[derive(Default)] struct TxGroup { @@ -281,17 +330,76 @@ impl KeySource for OnDiskReader { self.dict().tx_id_of(tx_count) } + fn tx_order(&self) -> Result { + if let Some(order) = self.tx_order.get() { + return Ok(*order); + } + let mut order = TxOrder { + monotonic: true, + last: None, + }; + self.dict_txs(None, &mut |tx_count, tx_id| { + if order.last.is_some_and(|(_, last)| tx_id < last) { + order.monotonic = false; + } + order.last = Some((tx_count, tx_id)); + Ok(true) + })?; + Ok(*self.tx_order.get_or_init(|| order)) + } + + fn last_tx_at(&self, t: u64) -> Result { + // The first transaction at or after `m`, if its `tx_id` is at most + // `t`: true up to the newest transaction with `tx_id <= t`, false + // after it, since `tx_id`s rise with `tx_count` here. + let at_or_before = |m: u64| -> Result { + let mut kept = false; + self.dict_txs(Some(m), &mut |_, tx_id| { + kept = tx_id <= t; + Ok(false) + })?; + Ok(kept) + }; + // The least `m` in `1..=newest + 1` whose first transaction at or + // after it is not kept; that transaction is `m - 1`. + let newest = self.tx_order()?.last.map_or(0, |(tx_count, _)| tx_count); + let (mut lo, mut hi) = (1u64, newest.saturating_add(1)); + while lo < hi { + let mid = lo + (hi - lo) / 2; + if at_or_before(mid)? { + lo = mid + 1; + } else { + hi = mid; + } + } + Ok(lo - 1) + } + + fn tx_runs(&self, t: u64, out: &mut Vec<(u64, u64)>) -> Result<()> { + let mut open: Option<(u64, u64)> = None; + self.dict_txs(None, &mut |tx_count, tx_id| { + match (tx_id <= t, open.as_mut()) { + (true, Some(run)) => run.1 = tx_count, + (true, None) => open = Some((tx_count, tx_count)), + (false, _) => out.extend(open.take()), + } + Ok(true) + })?; + out.extend(open); + Ok(()) + } + fn live_keys( &self, index: Index, prefix: &[u8], resume: Option<&[u8]>, - as_of: Option, + bound: &TxBound, max: usize, out: &mut Vec, ) -> Result>> { let root = self.root(index); - self.live_walk(index, root, prefix, resume, as_of, max, &mut |k| { + self.live_walk(index, root, prefix, resume, bound, max, &mut |k| { out.push(KeyFact::decode(index, k)?); Ok(()) }) @@ -353,6 +461,7 @@ impl CommittedReader for OnDiskReader { Some(self) } + #[cfg(any(test, feature = "test-oracle"))] fn live_facts(&self, scan: Scan<'_>, as_of: Option) -> Result> { let mut dict = self.dict(); let (index, root, prefix) = match scan { @@ -387,6 +496,7 @@ impl CommittedReader for OnDiskReader { self.live_scan(index, root, &prefix, as_of, &mut dict) } + #[cfg(any(test, feature = "test-oracle"))] fn all_facts(&self) -> Result> { if self.eavt_root == 0 { return Ok(Vec::new()); @@ -400,6 +510,7 @@ impl CommittedReader for OnDiskReader { Ok(facts) } + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_entity(&self, entity: &EntityId) -> Result> { let mut dict = self.dict(); let Some(e) = dict.eid_of(entity)? else { @@ -414,6 +525,7 @@ impl CommittedReader for OnDiskReader { ) } + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_entity_attribute(&self, entity: &EntityId, attribute: &str) -> Result> { let mut dict = self.dict(); let (Some(e), Some(a)) = (dict.eid_of(entity)?, dict.iid_of(attribute)?) else { @@ -425,6 +537,7 @@ impl CommittedReader for OnDiskReader { self.scan(Index::Eavt, self.eavt_root, &prefix, &mut dict) } + #[cfg(any(test, feature = "test-oracle"))] fn facts_for_attribute(&self, attribute: &str) -> Result> { let mut dict = self.dict(); let Some(a) = dict.iid_of(attribute)? else { diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index 7db23ff788..84deeeeb29 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -469,15 +469,13 @@ fn test_or_join_falls_back_to_expensive_branch_when_not_fully_covered() { ); } -/// (20b) Proves branch reordering itself (not declaration order) drives the skip: -/// the expensive branch is declared FIRST, but has a genuinely higher `branch_cost` -/// (a 1-bound pattern, cost 100) than the cheap branch (which pairs a 2-bound -/// pattern with an unrelated fully-bound one, so `branch_cost`'s min-over-patterns -/// is 1). If `branch_cost`-based sorting were broken (e.g. reverted to declaration -/// order), the expensive branch — written first — would run before coverage is -/// established and invoke the counter. -#[test] -fn test_or_join_short_circuit_relies_on_cost_sort_not_declaration_order() { +/// (20b) An `or-join` whose costlier branch, declared first, holds a predicate: +/// every entity matches through the cheaper branch alone. The executor skipped +/// the costlier branch once the cheaper one covered every row, so it never +/// called the predicate; the engine runs every branch (#551), so whether the +/// predicate is called is not part of the answer. +#[test] +fn test_or_join_expensive_branch_declared_first() { let db = db(); let calls = Arc::new(AtomicUsize::new(0)); let calls_inner = calls.clone(); @@ -516,12 +514,6 @@ fn test_or_join_short_circuit_relies_on_cost_sort_not_declaration_order() { 3, "all three entities match via the cost-cheaper branch alone" ); - assert_eq!( - calls.load(Ordering::SeqCst), - 0, - "the cost-100 branch must be sorted after the cost-1 branch and then skipped, \ - even though it appears first in the query text" - ); } /// (21) Plain `or` short-circuits too, when it's a pure filter (no branch introduces diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs index 280a3d37ae..9b9c627950 100644 --- a/tests/plan_independence_test.rs +++ b/tests/plan_independence_test.rs @@ -448,6 +448,44 @@ fn or_branch_expression_reads_outer_variable_in_rule_body() { assert_eq!(ints(&r), vec!["i:1", "i:2"], "or-and in a rule body"); } +// ── #551: nested `or`s in branches run on the engine ──────────────────────── + +/// A nested `or` / `or-join` in a branch, one reading outer variables the +/// branch's patterns do not bind (so the branch cannot be hashed), and a +/// rule whose branch nests an `or` around a rule invocation: every plan, +/// hashed or correlated, gives the executor's answer (#551 plan, step 5). +#[test] +fn nested_or_in_a_branch() { + let db = Minigraf::in_memory().unwrap(); + people(&db); + db.execute( + "(rule [(deep ?x ?y) [?x :friend ?y] (or (or (knows ?y ?x) [?y :age 40]) [?x :age 30])])", + ) + .unwrap(); + for (q, n) in [ + ( + "[:find ?n :where [?e :name ?n] (or-join [?e] (and [?e :age ?a] (or [(> ?a 35)] [?e :friend :bob])) [?e :x 1.5])]", + 3, + ), + ( + "[:find ?n :where [?e :name ?n] [?e :age ?a] (or-join [?e ?a] (and [?f :age ?b] (or [(= ?a ?b)] [?e :friend ?f])) [?e :x 1.5])]", + 3, + ), + ( + "[:find ?n :where [?e :name ?n] (or-join [?e] (and [?e :age ?a] (or-join [?a] [(> ?a 35)] [(< ?a 31)])) [?e :y _])]", + 4, + ), + ( + "[:find ?n :where [?e :name ?n] [?e :age ?a] (or-join [?e ?a] (and [?f :age ?b] (or [(< ?a ?b)] [(> ?a 39)])) [?e :x 1.5])]", + 3, + ), + ("[:find ?x ?y :where (deep ?x ?y)]", 3), + ] { + let r = same(&db, &format!("(query {q})")); + assert_eq!(r.len(), n, "{q}"); + } +} + // ── #625: an expression reading a variable only an `or` binds ──────────────── fn issue_625_data(db: &Minigraf) {