From b9c379a3ded2d8769d421193d2e78885c1cff530 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 15 Oct 2026 10:35:50 +0530 Subject: [PATCH] fix(query): a pseudo-attribute reads the nearest earlier pattern with its entity (#594) :db/valid-from, :db/valid-to, :db/tx-count and :db/tx-id read the fact of the last pattern the planner ran on the same entity (per-entity __f* keys), so the answer depended on the plan, and with no such pattern matched every fact of the entity. Now parser::resolve_pseudo_sources names each one's source at parse time: the nearest earlier pattern in the text with the same entity term and a stored attribute, in its own clause list, then before each enclosing not/or (not-join/or-join only for a listed variable, which gains the hidden variable), never past a rule body; PRS-081 when there is none. The source binds a hidden variable ?#. (Pattern::meta); the pseudo-attribute pattern binds or checks against it (Pattern::pseudo_source, substituted to the metadata in not bodies) and never scans. The optimizer places it after its source; not/or bodies that read metadata take the per-row paths (or-join gains one). The engine's scans fill the hidden variable's column; the per-row Step::Pseudo choice and the [e _ _] fallback for per-fact attributes are gone. :db/valid-at is unchanged. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 4 +- CLAUDE.md | 6 +- README.md | 2 +- docs/ERROR_REFERENCE.md | 17 ++ docs/TEST_COVERAGE.md | 3 +- src/error.rs | 9 + src/query/datalog/evaluator.rs | 7 +- src/query/datalog/executor.rs | 76 +++++++- src/query/datalog/matcher.rs | 255 ++++++++++++------------ src/query/datalog/optimizer.rs | 80 ++++++++ src/query/datalog/parser.rs | 331 +++++++++++++++++++++++++++++++- src/query/datalog/types.rs | 28 +++ src/query/engine/filter.rs | 61 +----- src/query/engine/plan.rs | 219 +++++---------------- src/query/engine/tests.rs | 54 ++++-- tests/plan_independence_test.rs | 22 ++- tests/pseudo_source_test.rs | 306 +++++++++++++++++++++++++++++ tests/temporal_metadata_test.rs | 10 +- 18 files changed, 1099 insertions(+), 391 deletions(-) create mode 100644 tests/pseudo_source_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 85418434bf..dc918dd381 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -24,6 +24,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **The `uuid` dependency no longer enables `v4`** (#439). The library only makes v5 UUIDs, so the `v4` feature and, on browser wasm, `js` are gone from its `uuid` dependency, and with them `getrandom`. A crate that called `Uuid::new_v4` only because Cargo feature unification turned `v4` on through minigraf must now enable `uuid/v4` itself. The release binary shrinks by 48 bytes. - **Join answers no longer depend on the query plan** (#545). Two cases changed. A join on a float value now pairs `0.0` with `-0.0`, as a shared variable compared after the join key already did; before, `Value`'s hash told them apart, so the join key never paired them. NaN still equals nothing. Float constants in a pattern still match within `f64::EPSILON`. And a variable bound to a keyword by one pattern and to the ref of the entity the keyword names by another, which already joined, now returns the kind from the first of those patterns in the `:where` text. Before, it returned the kind from the pattern the planner ran first, so the answer could change with the selectivity of the other patterns, and differed under the `wasm` feature, which does not reorder. For example, with `[:alice :friend :bob]` stored as a keyword, `[:find ?b :where [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob`, because the planner runs the pattern with two constants first, and now returns the keyword `:bob`. Expression bindings follow the next entry (#596). The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged. - **An expression binding a variable that another clause binds keeps only the rows where the two agree** (#596). `[(f …) ?x]` used to overwrite `?x` wherever the planner ran it, so when a pattern also bound `?x` the answer depended on whether that pattern ran first, and differed under the `wasm` feature, which does not reorder. Now the expression unifies: the row is kept when its result equals `?x`'s value, with the join equality of #545 (floats by IEEE `==`, a keyword equal to a ref to the entity it names, an integer never equal to a float, NaN equal to nothing). For example, with `[:a :age 30] [:b :age 40] [:p1 :score 41]`, `[:find ?a ?x :where [?e :age ?a] [:p1 :score ?x] [(+ ?a 1) ?x]]` returned `[30 31] [40 41]` natively and now returns `[40 41]`, as it did under `wasm`. `[(+ ?v 1) ?v]` never matches, and two expressions binding one variable must agree. When the two values differ only as keyword and ref, the variable returns the value of the first clause in the `:where` text that binds it, expressions included. This applies to `or` branches, `not` bodies and rule bodies too, on the executor and on the streaming engine. +- **A per-fact pseudo-attribute reads the nearest pattern before it with the same entity** (#594). `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read the metadata of one fact: the one matched by their *source*, chosen when the query, rule or prepared query is parsed, as the nearest pattern before them in the `:where` text with the same entity term and a stored attribute (a keyword, or a variable as in `[?e ?a _]`). The search starts in the pseudo-attribute's own clause list and moves outwards, before each enclosing `not` / `or`; it crosses a `not-join` / `or-join` only for an entity variable in its join variables, and stops at a rule body, which never reads its caller's patterns. Terms are the same when they are one variable, one `$slot`, or constants naming one entity (`:alice` and its UUID). Before, they read the last pattern *the planner ran* that matched the entity, so the answer depended on the plan and differed under the `wasm` feature: in `[?e :person/name ?n] [?e :person/age ?a] [?e :db/tx-count ?t]`, `?t` could be the tx-count of either fact, and is now the `:person/age` fact's. Three further changes follow: (1) with no source, the query fails at parse time with the new `PRS-081` instead of matching every visible fact of the entity (`[?e :db/tx-count ?t]` before `[?e :person/name ?n]`, a `_` entity, a pseudo-attribute in a rule body whose only candidate is in the caller); to read every fact of an entity, write `[?e ?a _]` before it; (2) inside `not`, `not-join`, `or` and `or-join`, a pseudo-attribute reads the outer fact, so `[?e :person/name ?n] (not [?e :db/tx-count 1])` excludes the entities whose *name* fact is from tx 1, where before the body matched any fact of the entity; (3) rows that differ only in a source fact's metadata are no longer merged by `or`. `:db/valid-at` is unchanged. The pseudo-attribute pattern now binds or checks a value; it never scans facts, so the planner places it after its source rather than by selectivity. ### Added @@ -62,7 +63,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545). - **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change. - **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`). -- **Pseudo-attributes across joins and `:db/valid-at` run on the streaming engine** (#473, part 3: #545, third PR). A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads, as the executor does, the fact of the last pattern before it in the planner's order that matched its entity: the scans of those patterns fill metadata columns and the pattern picks one per row. The engine runs it when its entity term is the entity term of an earlier pattern, or when no pattern with a stored attribute runs before it; then, and for every `:db/valid-at` pattern, it joins with every visible fact of its entity, as `[e _ _]` would, with the metadata or the query's valid time as a column. Other shapes (a pseudo-attribute pattern on an entity that no earlier pattern has as its entity, a `_` entity) stay on the executor; that the answer depends on the plan order is tracked in #594. Measured at 10M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` 34 s → 56 µs and 6.0–7.5 GiB → 4 MiB (3.2 s → 56 µs at 1M). Results are unchanged (`test-oracle`). +- **Pseudo-attributes across joins and `:db/valid-at` run on the streaming engine** (#473, part 3: #545, third PR). A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads the metadata of its source (#594, above): the source's scan or join fills a metadata column from the fact's key, and the pattern binds or checks against it. A `:db/valid-at` pattern joins with every visible fact of its entity, as `[e _ _]` would, with the query's valid time as a column. Measured at 10M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` 34 s → 56 µs and 6.0–7.5 GiB → 4 MiB (3.2 s → 56 µs at 1M). Results are unchanged (`test-oracle`). - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. @@ -76,6 +77,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Weekly soak test at scale (#392).** `tests/soak_test.rs` grows a file-backed database to 10M live facts in batches of 1–2,000 facts (multi-valued tags and shard values in one transaction, strings over 64 bytes, refs), then churns it for the rest of a 5-hour budget at 50 transactions a second: retracts and re-asserts of random facts, and long retract/assert histories on 32 hot entities. It checkpoints every 20–200 transactions and reopens every 2–10 minutes, half from a checkpointed file and half replaying the WAL. Every 10 minutes, after every reopen, and between churn writes it checks samples against a reference that derives each entity's facts from its number and keeps only what was retracted: EAVT per entity, entity and attribute on the tags, AVET by unique name, AEVT over a sparse attribute, `:as-of` on hot entities, and the transaction counter; a full scan runs in a child process at 2M facts (so its memory does not hide a leak), and `verify()` at the end. It fails if RSS after a reopen grows past 1.25× the baseline plus 256 MiB. Metrics (file size, open and checkpoint time, RSS and peak RSS, p50/p99 per query path) go to a JSON-lines file that `.github/workflows/soak.yml` uploads weekly, alternating `main` and `v3`. `soak_short` runs the same driver at 20K facts in the per-PR suite. Found #518: attribute-and-value patterns scan the whole attribute. - **Coverage gates that gate (#396).** The per-module gate in `coverage-gates.yml` had never checked anything: the instrumented test run failed (the lock tests could not find `pid_ns_helper`), the report it grepped was empty, and every module was skipped with a warning, so the job passed. It also read `cargo llvm-cov --text`, which has no per-file percentages, and named `btree_v6`, which v3 no longer has. The job now runs the whole suite with branch coverage on a pinned nightly, fails if any test fails, and checks each file's line and branch percentage against `coverage-thresholds.toml` with `scripts/coverage_gates.py`; a file missing from the report, or without branch data, fails. The thresholds file covers the WAL, `db.rs`, the fact log and log writer, every storage file, and the evaluator, executor and stratification, with floors at the measured values less one point. It also lists the paths left uncovered on purpose (invariant checks, browser-only and Windows-only paths). New tests cover the WAL's fact-size and fact-count limits (the old fact-size test changed bytes inside the fact and never reached the limit), a WAL opened in a missing directory, a failed cut of a torn WAL tail, short v7 pages and slots past the count, backup meta pages of another generation or length, a torn first meta with data in page 1, `save` with nothing pending, `into_backend` with pending facts, `rebuild_indexes` with nothing checkpointed, unsorted or repeated B+tree input, a stored key inserted with another value, a tree pointer to a page of another type, the read-only `MutexStorageBackend`, and two threads missing the same page in the page cache (before, only a lucky race reached that path). Branch coverage of `wal.rs` went from 83% to 95%, `packed_pages.rs` from 86% to 100%, `persistent_facts.rs` from 82% to 88%, and `btree.rs` from 85% to 85.5%. A follow-up brought the storage files the issue named to 90% branch coverage or more: `btree.rs` to 95.7%, `persistent_facts.rs` to 91.7% and `index.rs` to 100%, with floors raised to match. New tests cover a leaf packing retried around one large entry, an entry larger than a page, separators over the fill target, an insert into a tree whose root points to itself, auto-save on drop, a torn first meta with a blank page 1, and an unreadable page past the meta's page count. Splitting internal nodes is now one pass: the old retry loop could not run, because the balanced cut always leaves each node within the fill target. The workflow pins cargo-llvm-cov 0.9.1, since 0.8.x missed the library's unit tests under the pinned nightly and reported much lower numbers. - **Performance envelope at 100K–10M facts (#394).** `examples/perf_envelope.rs` builds and caches fixtures of 100K, 1M and 10M facts (six attributes per entity, a ref tree, two valid-time windows, an entity with 1,000 versions). It reports open and checkpoint times, RSS, and p50/p99 latency for twelve query shapes, each shape in its own process. It builds with a new `envelope` Cargo profile (`release` at opt-level 3, as an application compiles the library; `release` itself is opt-level "z"). `docs/BENCHMARKS.md` and the README publish the results: point lookups and single-entity time travel stay flat (12–14 µs at 10M facts). Scans, aggregations and joins grow linearly with the attributes they touch. Rule queries are supported to 100K facts only. A Python FFI round trip (`bench/envelope.py` in minigraf-python) adds about 70 µs per query. `.github/workflows/envelope.yml` runs 100K and 1M on demand, and a 10K smoke pass on PRs that change the harness. The nightly Criterion `query/*` groups gain 100K and 1M scales. Profiling at 1M facts found #528, #529, #530, #531 and #532. +- **Pseudo-attribute sources (#594).** `tests/pseudo_source_test.rs` covers the source rule (nearest earlier pattern in the text, two pseudo-attributes sharing one, every fact through `[?e ?a _]`, constants by entity id, `$slot`s by name), `PRS-081` for each shape with no source, reading the outer fact from `not`, `not-join` (listed and unlisted variable), `or` (never a sibling branch) and `or-join`, closed rule bodies, and `:db/valid-at`. Parser, optimizer and matcher unit tests cover the hidden variables, their placement and the join variables a crossed `not-join` gains. The plan-independence matrix gains the pseudo-attribute shapes. - **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off. - `tests/snapshot_atomicity_test.rs` races a writer against a reader: a query must see each transaction whole, whether written with `execute` or a `WriteTransaction` (#554), and must read one state for all its patterns (#555), in memory and on file. It also runs the v2.x checkpoint race from #558, which never failed on v3: copy-on-write checkpoints do not overwrite pages a published reader uses. - **The `datalog_eval` fuzz guard counts partial bindings** (#597). The guard skipped inputs whose patterns join to more than 50,000 rows, counting only the rows after the last pattern. A `not-join` body still runs on the executor pattern by pattern in text order, so a 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and ran past the 60-second timeout. The guard now counts the bindings after every pattern. On the `v3` corpus (4,783 inputs) coverage drops by 7 of 9,719 edges. The input is added as a seed, as is the `btree_page` input of the cursor fix above. diff --git a/CLAUDE.md b/CLAUDE.md index a6ac87981e..2794a0afaa 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -128,7 +128,7 @@ cargo run < demos/demo_negation.txt - `persistent_facts.rs`: `PersistentFactStorage` — v8 save/load, auto-migration v7→v8 3. **`src/query/datalog/`** — Datalog engine - - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join` + - `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) - `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` - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator`, `evaluate_not_join` @@ -139,7 +139,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 and expression clauses in `optimizer::plan` order; a pseudo-attribute pattern reads the metadata column of the last earlier pattern that matched its entity, chosen per row, or joins as `[e _ _]` when none runs before it, as `:db/valid-at` always does; plain `:find` variables, today), `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), `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), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`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), beside the executor until #551: `plan.rs` (which queries it runs: patterns and expression clauses in `optimizer::plan` order; 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, today), `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), `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), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`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. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1514 tests** (1504 passing, 10 ignored; unit + integration + doc). +**1532 tests** (1522 passing, 10 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index bd8b518c71..c0855efe7a 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1514 tests +cargo test # run 1532 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index e44d9c1122..dc0c55b517 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -101,6 +101,7 @@ with no `CodedError` anywhere in its chain. | PRS-078 | Query rejects unexpected trailing argument(s) | Parser | | PRS-079 | Rule rejects unexpected trailing argument(s) | Parser | | PRS-080 | :find variable not bound in :where | Parser | +| PRS-081 | Pseudo-attribute has no source pattern | Parser | | QRY-001 | Invalid entity | Query Execution | | QRY-002 | Attribute must be a keyword | Query Execution | | QRY-003 | Cannot transact a pseudo-attribute | Query Execution | @@ -1579,6 +1580,22 @@ $<4097-char-slot-name> ``` *`?n` is never bound; use `?name`* +### PRS-081 Pseudo-attribute has no source pattern + +**Error text**: `{} on {} has no pattern before it, with the same entity, that reads a stored attribute; add one (e.g. [{} ?a _]) before it` + +**Cause**: A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads the metadata of one fact: the fact matched by its *source*, the nearest pattern before it in the query text with the same entity term and a stored attribute (a keyword, or a variable such as `[?e ?a ?v]`). The search starts in the pseudo-attribute's own clause list and continues outwards, before each enclosing `not`, `or`, `not-join` or `or-join`; it crosses a `not-join` or `or-join` only for an entity variable listed in its join variables, and it stops at a rule body, which never reads its caller's patterns. A pattern after the pseudo-attribute never counts, a sibling `or` branch is never searched, and a `_` entity never has a source. Entity terms are the same when they are the same variable, the same `$slot`, or constants naming the same entity (`:alice` and its UUID). Before v3.0.0 such a pattern matched every visible fact of the entity instead, and which fact a pseudo-attribute read could depend on the plan. + +**Resolution**: +- Put a pattern with the same entity term before the pseudo-attribute pattern. +- To read the metadata of every fact of an entity, write `[?e ?a _]` before it. + +**Example**: +```datalog +(query [:find ?t :any-valid-time :where [?e :db/tx-count ?t] [?e :person/name "Alice"]]) +``` +*Move `[?e :person/name "Alice"]` before `[?e :db/tx-count ?t]`* + --- ## QRY — Query Execution Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index ea90528d61..ab794cd18e 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-15 with `cargo test --quiet` -**Result**: 1,504 passing tests and 10 ignored tests (1,514 total) +**Result**: 1,522 passing tests and 10 ignored tests (1,532 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). @@ -16,6 +16,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). Query and prepared-query cursors keep their answer and their pages across writes, checkpoints and index rebuilds, and the file stops growing once they close (`tests/cursor_test.rs`); a snapshot leaves out facts appended after it on every scan (`graph::storage`); a crash at every write point of a save with a pinned generation loses no fact and no page, and the reopened database reuses the quarantined ids (`storage::persistent_facts`); the browser withholds free pages a pinned generation may read and releases them once out of force (`storage::pins::split_released`, and a `#[wasm_bindgen_test]` with an open `BrowserDb` cursor). - **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). Lazy cursors (`cursor::tests`, #544 PR 3): one pull reads one internal batch of the scan (operator counters), rows left in a batch need no pull, a closed stream reads nothing more, a filter's counters chain, and a cursor's answer is unchanged by writes and by checkpoints that free the leaves it has yet to read (file-backed) or by later writes (in memory); a read error after some rows are gathered comes on the next call, then the cursor ends (`query::engine::tests`). DICT lookups are cached for one pull only, and provisional ids keep their values across pulls (`query::engine::ids`). Joins (#545 PR 2): the oracle matrix adds two- and three-pattern joins on the entity (`IndexNestedLoopJoin`), value and attribute positions (`HashJoin`), cross products, keywords and refs of one entity in both text orders, UUID-named keywords, attributes that name entities, floats `0.0`/`-0.0`, long strings committed and pending, and expressions between joins, at every temporal; joins whose answers span many batches (one probe with more than a batch of matches, cross products, tables built on either side); the planner's join choice; a keyword's entity id (`query::engine::ids`). Pseudo-attributes across joins (#545 PR 3): the metadata of the last pattern before them that matched their entity, chosen per row (a pattern on another entity variable that equals theirs on some rows only, constant entities), pseudo-attribute patterns planned before any pattern with a stored attribute (joined with every fact of their entity, including cross products), and `:db/valid-at` at every temporal with variables, `nil` and integer constants; which pseudo-attribute shapes stay on the executor. - **Join rules** (`tests/join_rules_test.rs`, 10 tests; #545): a join on a float value pairs `0.0` with `-0.0`, through the hash key and as a shared variable, and a float constant still matches within epsilon; a variable bound to a keyword by one pattern and to the ref of the same entity by another returns the kind from the first pattern in `:where` text order, when the planner runs the patterns in another order, through the attribute position, before and after a rule call, and with a repeated pattern; an expression binding unifies with a pattern binding the same variable, and the first binder in the text, pattern or expression, gives the value (#596); a pseudo-attribute pattern never replaces a value (native plan order only: under `wasm` the pattern runs first and binds the variable). Under the `test-oracle` feature the joins among them also run on the streaming engine. A unit test checks that `-0.0` and `0.0` hash alike. +- **Pseudo-attribute sources** (`tests/pseudo_source_test.rs`, 12 tests; #594): a per-fact pseudo-attribute reads the nearest earlier pattern in the text with the same entity term (#594's example in both text orders), two pseudo-attributes share a source, `[:alice ?a _]` gives one row per fact, constant and bound value terms check, `:alice` and its UUID are one term while `?e` and `:alice` are not, PRS-081 for a pattern after it, alone, `_`/`?_x` entities, another entity's pattern and a rule call; a `not` body reads the outer fact (and a source inside the body), `not-join` crosses for a listed variable only, `or` branches read the outer fact and never a sibling, `or-join`, closed rule bodies, `$slot`s by name at prepare time, and `:db/valid-at` once per fact. Parser unit tests check the hidden variables (`?#.`), the join variable a crossed `not-join` gains, and the PRS-081 text; an optimizer test places a pseudo-attribute pattern after its source and the pattern binding its value; matcher tests read the hidden variable, a substituted integer, and nothing without a source; the engine tests run the sourced shapes and check PRS-081 for the old fallback shapes. The plan-independence matrix gains eleven pseudo-attribute shapes. - **Plan independence** (`tests/plan_independence_test.rs`, 7 tests, `test-oracle` feature only; #596): a matrix of queries (joins in both text orders, cross products, keyword and ref, floats, long strings, filter and binding expressions, recursive rules and rules with `not`, `or`/`or-join` including the #250 short-circuit shapes, placed and deferred `not`/`not-join`, aggregates, `:as-of`, `:valid-at`, `:any-valid-time`), in memory and on file after a checkpoint and a reopen, through `execute` and a cursor, gives the same bag of rows with clause reordering on and off (`minigraf::__reorder`); #596's example and the unification cases (an expression whose output is its input, two expressions on one variable, integer vs float, `-0.0` vs `0.0`). Under `test-oracle` the model-based and property tests also rerun every generated query with reordering off. Unit tests cover `apply_expr` (equal, different, integer vs float, NaN, `-0.0`/`0.0` with and without replacing, keyword vs ref both ways, a failing expression), `Binders::expression`, the switch (source order kept, per thread, restored on drop), and the engine planner's `Bind` modes and build side with the switch off; the engine's join matrix gains six unification shapes. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/src/error.rs b/src/error.rs index 22c725198c..98ace72cf0 100644 --- a/src/error.rs +++ b/src/error.rs @@ -127,6 +127,7 @@ pub(crate) enum ErrorCode { Prs078, Prs079, Prs080, + Prs081, Qry001, Qry002, Qry003, @@ -765,6 +766,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ ":find variable {} not bound in :where", ErrorCategory::Parser, ), + ( + ErrorCode::Prs081, + "PRS-081", + "{} on {} has no pattern before it, with the same entity, that reads a stored attribute; add one (e.g. [{} ?a _]) before it", + ErrorCategory::Parser, + ), ( ErrorCode::Qry001, "QRY-001", @@ -1984,6 +1991,7 @@ mod tests { | ErrorCode::Prs078 | ErrorCode::Prs079 | ErrorCode::Prs080 + | ErrorCode::Prs081 | ErrorCode::Qry001 | ErrorCode::Qry002 | ErrorCode::Qry003 @@ -2210,6 +2218,7 @@ mod tests { ErrorCode::Prs078, ErrorCode::Prs079, ErrorCode::Prs080, + ErrorCode::Prs081, ErrorCode::Qry001, ErrorCode::Qry002, ErrorCode::Qry003, diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 00b2b79230..d50b0ee230 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -442,8 +442,11 @@ pub fn substitute_pattern(pattern: &Pattern, binding: &Bindings) -> Pattern { entity: substitute_value(&pattern.entity, binding), attribute, value: substitute_value(&pattern.value, binding), - valid_from: pattern.valid_from, - valid_to: pattern.valid_to, + pseudo_source: pattern + .pseudo_source + .as_ref() + .map(|v| substitute_value(v, binding)), + ..pattern.clone() } } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index eed1ec5266..6da0e0ec85 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1143,9 +1143,12 @@ fn apply_not_clause( valid_at_value: Value, registry: &FunctionRegistry, ) -> Vec { + // Expressions, and pseudo-attributes that may read an outer source + // (#594), need the outer row: no exclusion set matched without it. let has_expr = not_body .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); + .any(|c| matches!(c, WhereClause::Expr { .. })) + || reads_metadata(not_body); let patterns: Vec = not_body .iter() .filter_map(|c| match c { @@ -1175,8 +1178,7 @@ fn apply_not_clause( let exclusion_set: std::collections::HashSet> = matcher .match_patterns(&patterns) .into_iter() - .map(|mut b| { - b.retain(|k, _| !k.starts_with("__f")); + .map(|b| { let mut kv: Vec<(String, Value)> = b .into_iter() .map(|(k, v)| (k, normalize_value(&v))) @@ -1232,9 +1234,12 @@ fn apply_not_join_clause( valid_at_value: Value, registry: &FunctionRegistry, ) -> Vec { + // Expressions, and pseudo-attributes that may read an outer source + // (#594), need the outer row: no exclusion set matched without it. let has_expr = nj_clauses .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); + .any(|c| matches!(c, WhereClause::Expr { .. })) + || reads_metadata(nj_clauses); let patterns: Vec = nj_clauses .iter() .filter_map(|c| match c { @@ -1421,6 +1426,20 @@ fn apply_not_clause_derived( .collect() } +/// 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`. +pub(crate) fn reads_metadata(clauses: &[WhereClause]) -> bool { + clauses.iter().any(|c| match c { + WhereClause::Pattern(p) => p.pseudo_source.is_some(), + WhereClause::Not(body) | WhereClause::NotJoin { clauses: body, .. } => reads_metadata(body), + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + branches.iter().any(|b| reads_metadata(b)) + } + WhereClause::Expr { .. } | WhereClause::RuleInvocation { .. } => false, + }) +} + /// 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). @@ -2076,9 +2095,12 @@ pub(crate) fn apply_or_clauses( // If any branch contains Not/NotJoin clauses (which need bound variables // from the outer scope to evaluate correctly), fall back to the classic // seeded-branch evaluation to preserve correctness. + // So does a branch whose pseudo-attribute may read an outer + // source's metadata (#594). let any_branch_has_not = sorted_or_branches.iter().any(|b| { b.iter() .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) + || reads_metadata(b) }); if any_branch_has_not { @@ -2309,6 +2331,50 @@ pub(crate) fn apply_or_clauses( } } + // A branch whose pseudo-attribute may read an outer source's + // metadata (#594) needs it from the outer row: evaluate the + // branches per row, seeded with its join variables only (the + // others are fresh inside), and keep the distinct rows some + // branch matches, as the joined path below does. + if sorted_oj_branches.iter().any(|b| reads_metadata(b)) { + let mut seen: std::collections::HashSet> = + std::collections::HashSet::new(); + let mut result: Vec = Vec::new(); + for incoming in &bindings { + let seed: Binding = join_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + let mut matched = false; + for branch in &sorted_oj_branches { + if !evaluate_branch( + branch, + vec![seed.clone()], + storage.clone(), + rules, + as_of.clone(), + valid_at.clone(), + registry, + )? + .is_empty() + { + matched = true; + break; + } + } + let mut key: Vec<_> = incoming + .iter() + .map(|(k, v)| (k.clone(), v.clone())) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if matched && seen.insert(key) { + result.push(incoming.clone()); + } + } + bindings = result; + continue; + } + let empty_seed: Vec = vec![HashMap::new()]; let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); @@ -5560,7 +5626,7 @@ mod expr_eval_tests { // Lines 348-350: hard-error guard in execute_query_with_rules // Per-fact pseudo-attr without :any-valid-time in a rules query let err_cmd = parse_datalog_command( - "(query [:find ?e ?vf :where (tagged ?e) [?e :db/valid-from ?vf]])", + "(query [:find ?e ?vf :where (tagged ?e) [?e ?a _] [?e :db/valid-from ?vf]])", ) .expect("err query parse failed"); let err_result = executor.execute(err_cmd); diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index 703673bb13..8f7db1729e 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -61,6 +61,12 @@ impl PatternMatcher { /// Match a single pattern against all facts in storage /// Returns a list of bindings, one for each matching fact pub fn match_pattern(&self, pattern: &Pattern) -> Vec { + if Self::reads_source(pattern) { + return self + .match_pseudo(pattern, &HashMap::new()) + .into_iter() + .collect(); + } let mut results = Vec::new(); // Get all currently asserted facts @@ -99,35 +105,17 @@ impl PatternMatcher { if !self.match_component(&pattern.value, &fact.value, &mut bindings) { return None; } - // Store hidden fact-metadata keys so that subsequent pseudo-attr patterns - // for the same entity can read per-fact temporal/tx metadata without - // cross-joining against every other fact for the entity. - // Keys are prefixed with `__f` and namespaced by entity UUID to avoid - // collisions across entities. They are never referenced in :find, so they - // are silently filtered out during result extraction. - let eid = fact.entity.to_string(); - bindings.insert(format!("__fvf_{}", eid), Value::Integer(fact.valid_from)); - bindings.insert(format!("__fvt_{}", eid), Value::Integer(fact.valid_to)); - bindings.insert( - format!("__ftc_{}", eid), - Value::Integer(fact.tx_count.cast_signed()), - ); - bindings.insert( - format!("__fti_{}", eid), - Value::Integer(fact.tx_id.cast_signed()), - ); + // A source of pseudo-attribute patterns binds its hidden + // metadata variables from this fact (#594). + for (attr, var) in &pattern.meta { + bindings.insert(var.clone(), Self::metadata(fact, attr)); + } } - AttributeSpec::Pseudo(pseudo) => { - // Pseudo-attribute: skip stored attribute match; bind fact metadata - // field to the value position variable (or match against a constant). - let pseudo_value = match pseudo { - PseudoAttr::ValidFrom => Value::Integer(fact.valid_from), - PseudoAttr::ValidTo => Value::Integer(fact.valid_to), - PseudoAttr::TxCount => Value::Integer(fact.tx_count.cast_signed()), - PseudoAttr::TxId => Value::Integer(fact.tx_id.cast_signed()), - PseudoAttr::ValidAt => self.valid_at_value.clone(), - }; - if !self.match_component(&pattern.value, &pseudo_value, &mut bindings) { + AttributeSpec::Pseudo(_) => { + // `:db/valid-at`: the query's valid time, with every fact of + // the entity, as `[e _ _]` would. Per-fact pseudo-attributes + // read their source (`match_pseudo`) and never get here. + if !self.match_component(&pattern.value, &self.valid_at_value, &mut bindings) { return None; } } @@ -136,6 +124,46 @@ impl PatternMatcher { Some(bindings) } + /// The metadata `attr` of `fact`. `:db/valid-at` is not per fact; it + /// never names a hidden variable. + fn metadata(fact: &Fact, attr: &PseudoAttr) -> Value { + Value::Integer(match attr { + PseudoAttr::ValidFrom | PseudoAttr::ValidAt => fact.valid_from, + PseudoAttr::ValidTo => fact.valid_to, + PseudoAttr::TxCount => fact.tx_count.cast_signed(), + PseudoAttr::TxId => fact.tx_id.cast_signed(), + }) + } + + /// Whether `pattern` is a per-fact pseudo-attribute pattern, which reads + /// its source's metadata (#594) instead of matching facts. + fn reads_source(pattern: &Pattern) -> bool { + matches!(&pattern.attribute, AttributeSpec::Pseudo(a) if a.is_per_fact()) + } + + /// A per-fact pseudo-attribute pattern over the row `existing`: its value + /// term bound to, or compared with, the metadata its source bound (the + /// hidden variable, or the integer a substitution put in its place). No + /// row when the source did not bind it, which the parser rules out. + fn match_pseudo(&self, pattern: &Pattern, existing: &Bindings) -> Option { + let meta = match pattern.pseudo_source.as_ref()? { + EdnValue::Symbol(v) => existing.get(v)?.clone(), + other => edn_to_value(other).ok()?, + }; + let mut row = existing.clone(); + match &pattern.value { + EdnValue::Symbol(v) if v.starts_with('?') && !v.starts_with("?_") => match row.get(v) { + Some(old) => (Self::normalize_join_value(old) == Self::normalize_join_value(&meta)) + .then_some(row), + None => { + row.insert(v.clone(), meta); + Some(row) + } + }, + other => self.match_component(other, &meta, &mut row).then_some(row), + } + } + /// Match a pattern component (entity, attribute, or value) against a fact value /// Returns true if match succeeds, updating bindings for variables fn match_component( @@ -436,10 +464,6 @@ impl PatternMatcher { let mut merged = existing.clone(); let mut consistent = true; for (var, val) in candidate { - if var.starts_with("__f") { - merged.insert(var.clone(), val.clone()); - continue; - } if let Some(merged_val) = merged.get(var) { // Compare using normalized values so that keyword entity // references (e.g., Keyword(":d-bad") stored as a value in @@ -492,40 +516,8 @@ impl PatternMatcher { existing: &Bindings, rebind: &[String], ) -> Vec { - // Fast path for pseudo-attr patterns: when a preceding real-attr pattern stored - // hidden fact-metadata keys (e.g. `__fvf_`), use them directly instead of - // scanning all facts and cross-joining. This ensures pseudo-attr patterns are - // correlated with the specific fact matched by the preceding real-attr pattern. - if let AttributeSpec::Pseudo(pseudo) = &pattern.attribute { - // Resolve the entity component to a UUID using existing bindings - let resolved_entity = self.apply_binding_to_component(&pattern.entity, existing); - let entity_uuid_opt: Option = match &resolved_entity { - EdnValue::Uuid(u) => Some(*u), - EdnValue::Keyword(k) => edn_to_entity_id(&EdnValue::Keyword(k.clone())).ok(), - _ => None, - }; - if let Some(uuid) = entity_uuid_opt { - let eid = uuid.to_string(); - let hidden_key = match pseudo { - PseudoAttr::ValidFrom => format!("__fvf_{}", eid), - PseudoAttr::ValidTo => format!("__fvt_{}", eid), - PseudoAttr::TxCount => format!("__ftc_{}", eid), - PseudoAttr::TxId => format!("__fti_{}", eid), - // ValidAt is a query-level constant (not per-fact); fall through to - // the normal scan path so each fact produces one binding (all - // identical). Task 5 (executor) will inject the correct value. - PseudoAttr::ValidAt => { - return self.match_pattern_with_bindings_scan(pattern, existing, rebind); - } - }; - if let Some(stored_value) = existing.get(&hidden_key) { - let mut new_bindings = existing.clone(); - if self.match_component(&pattern.value, stored_value, &mut new_bindings) { - return vec![new_bindings]; - } - return vec![]; - } - } + if Self::reads_source(pattern) { + return self.match_pseudo(pattern, existing).into_iter().collect(); } // Default: scan all facts @@ -554,14 +546,8 @@ impl PatternMatcher { self.match_fact_against_pattern(fact, &resolved_pattern) { // Check that additional bindings are consistent with existing. - // Hidden fact-metadata keys (prefixed `__f`) are always overwritten - // and are excluded from the consistency check. let mut consistent = true; for (var, val) in &additional_bindings { - if var.starts_with("__f") { - // Hidden metadata keys: always overwrite, never conflict-check. - continue; - } if matches!(existing.get(var), Some(existing_val) if existing_val != val) { consistent = false; break; @@ -569,7 +555,6 @@ impl PatternMatcher { } if consistent { - // Merge bindings (hidden keys are overwritten by the new fact's values) new_bindings.extend(additional_bindings); // A substituted variable matched as a constant; take the // fact's value at its first position instead. @@ -613,8 +598,11 @@ impl PatternMatcher { entity: self.apply_binding_to_component(&pattern.entity, bindings), attribute, value: self.apply_binding_to_component(&pattern.value, bindings), - valid_from: pattern.valid_from, - valid_to: pattern.valid_to, + pseudo_source: pattern + .pseudo_source + .as_ref() + .map(|v| self.apply_binding_to_component(v, bindings)), + ..pattern.clone() } } @@ -1121,13 +1109,15 @@ mod tests { Arc::from(net_asserted_facts(storage.get_all_facts().unwrap())); let matcher = PatternMatcher::from_slice(all_facts.clone()); - // First pattern: [?e :item/label _] + // First pattern: [?e :item/label _], the source of the second (#594). let p1 = Pattern { entity: EdnValue::Symbol("?e".to_string()), attribute: AttributeSpec::Real(EdnValue::Keyword(":item/label".to_string())), value: EdnValue::Symbol("_".to_string()), valid_from: None, valid_to: None, + meta: vec![(PseudoAttr::ValidFrom, "?#0.valid-from".to_string())], + pseudo_source: None, }; let r1 = matcher.match_pattern(&p1); assert_eq!(r1.len(), 1, "first pattern should bind ?e"); @@ -1139,6 +1129,8 @@ mod tests { value: EdnValue::Symbol("?vf".to_string()), valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: Some(EdnValue::Symbol("?#0.valid-from".to_string())), }; let r2 = matcher.match_patterns_seeded(&[p2], r1); assert_eq!(r2.len(), 1, "second pattern should bind ?vf"); @@ -1146,9 +1138,9 @@ mod tests { } #[test] - fn test_pseudo_attr_valid_to_tx_count_tx_id_scan_path() { - // Exercises matcher.rs lines 120-122: ValidTo/TxCount/TxId arms in - // match_fact_against_pattern (scan path — no hidden keys seeded). + fn test_pseudo_attr_valid_to_tx_count_tx_id_read_their_source() { + // A source binds one hidden variable per pseudo-attribute that reads + // it; each pseudo-attribute pattern reads its own (#594). use crate::graph::storage::net_asserted_facts; use crate::graph::types::Value as GValue; use std::sync::Arc; @@ -1168,49 +1160,58 @@ mod tests { let all_facts: Arc<[Fact]> = Arc::from(net_asserted_facts(storage.get_all_facts().unwrap())); + let fact = all_facts[0].clone(); let matcher = PatternMatcher::from_slice(all_facts); - // Each test uses a UUID entity + wildcard value so the entity check passes - // and no hidden key is seeded → falls through to scan → hits line 120/121/122. - - // Line 120: ValidTo - let p_vt = Pattern { - entity: EdnValue::Uuid(alice_id), - attribute: AttributeSpec::Pseudo(PseudoAttr::ValidTo), - value: EdnValue::Symbol("?vt".to_string()), - valid_from: None, - valid_to: None, - }; - let r_vt = matcher.match_pattern(&p_vt); - assert_eq!(r_vt.len(), 1, "ValidTo scan should bind one result"); - - // Line 121: TxCount - let p_tc = Pattern { + let source = Pattern { entity: EdnValue::Uuid(alice_id), - attribute: AttributeSpec::Pseudo(PseudoAttr::TxCount), - value: EdnValue::Symbol("?tc".to_string()), + attribute: AttributeSpec::Real(EdnValue::Keyword(":item/label".to_string())), + value: EdnValue::Symbol("_".to_string()), valid_from: None, valid_to: None, + meta: vec![ + (PseudoAttr::ValidTo, "?#0.valid-to".to_string()), + (PseudoAttr::TxCount, "?#0.tx-count".to_string()), + (PseudoAttr::TxId, "?#0.tx-id".to_string()), + ], + pseudo_source: None, }; - let r_tc = matcher.match_pattern(&p_tc); - assert_eq!(r_tc.len(), 1, "TxCount scan should bind one result"); - - // Line 122: TxId - let p_ti = Pattern { + let reader = |attr: PseudoAttr, var: &str, hidden: &str| Pattern { entity: EdnValue::Uuid(alice_id), - attribute: AttributeSpec::Pseudo(PseudoAttr::TxId), - value: EdnValue::Symbol("?ti".to_string()), + attribute: AttributeSpec::Pseudo(attr), + value: EdnValue::Symbol(var.to_string()), valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: Some(EdnValue::Symbol(hidden.to_string())), }; - let r_ti = matcher.match_pattern(&p_ti); - assert_eq!(r_ti.len(), 1, "TxId scan should bind one result"); + let rows = matcher.match_patterns_seeded( + &[ + source, + reader(PseudoAttr::ValidTo, "?vt", "?#0.valid-to"), + reader(PseudoAttr::TxCount, "?tc", "?#0.tx-count"), + reader(PseudoAttr::TxId, "?ti", "?#0.tx-id"), + ], + vec![HashMap::new()], + ); + assert_eq!(rows.len(), 1, "one row, from the source's one fact"); + assert_eq!(rows[0].get("?vt"), Some(&GValue::Integer(fact.valid_to))); + assert_eq!( + rows[0].get("?tc"), + Some(&GValue::Integer(fact.tx_count.cast_signed())) + ); + assert_eq!( + rows[0].get("?ti"), + Some(&GValue::Integer(fact.tx_id.cast_signed())) + ); } #[test] - fn test_pseudo_attr_entity_non_uuid_non_keyword_falls_through() { - // Exercises matcher.rs line 302: `_ => None` when resolved entity is - // neither Uuid nor Keyword — falls through to scan path. + fn test_pseudo_attr_without_source_matches_nothing() { + // A per-fact pseudo-attribute pattern never scans facts: with no + // source (the parser refuses that, PRS-081), or a source variable the + // row does not bind, it gives no row (#594). A substituted source + // (an integer) is compared directly. use crate::graph::storage::net_asserted_facts; use crate::graph::types::Value as GValue; use std::sync::Arc; @@ -1232,25 +1233,29 @@ mod tests { Arc::from(net_asserted_facts(storage.get_all_facts().unwrap())); let matcher = PatternMatcher::from_slice(all_facts); - // Entity is an Integer — neither Uuid nor Keyword → `_ => None` path - let pattern = Pattern { - entity: EdnValue::Integer(99), + let pattern = |source: Option, value: EdnValue| Pattern { + entity: EdnValue::Uuid(alice_id), attribute: AttributeSpec::Pseudo(PseudoAttr::ValidFrom), - value: EdnValue::Symbol("?vf".to_string()), + value, valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: source, }; - // Falls through to scan; Integer entity won't match any stored UUID → 0 results - let results = matcher.match_pattern(&pattern); - assert_eq!( - results.len(), - 0, - "non-uuid/keyword entity should yield no matches" - ); + let vf = || EdnValue::Symbol("?vf".to_string()); + assert!(matcher.match_pattern(&pattern(None, vf())).is_empty()); + let unbound = pattern(Some(EdnValue::Symbol("?#0.valid-from".to_string())), vf()); + assert!(matcher.match_pattern(&unbound).is_empty()); + let substituted = pattern(Some(EdnValue::Integer(7)), vf()); + let rows = matcher.match_pattern(&substituted); + assert_eq!(rows.len(), 1); + assert_eq!(rows[0].get("?vf"), Some(&GValue::Integer(7))); + let other = pattern(Some(EdnValue::Integer(7)), EdnValue::Integer(8)); + assert!(matcher.match_pattern(&other).is_empty()); } #[test] - fn test_pseudo_attr_hidden_key_value_mismatch_returns_empty() { + fn test_pseudo_attr_hidden_var_value_mismatch_returns_empty() { // Exercises matcher.rs line 323: `return vec![]` when the stored hidden-key // value doesn't match the pattern value component. use crate::graph::storage::net_asserted_facts; @@ -1274,25 +1279,29 @@ mod tests { Arc::from(net_asserted_facts(storage.get_all_facts().unwrap())); let matcher = PatternMatcher::from_slice(all_facts.clone()); - // Seed bindings with the real-attr pattern so hidden keys are populated + // Seed bindings with the source, which binds the hidden variable. let p1 = Pattern { entity: EdnValue::Symbol("?e".to_string()), attribute: AttributeSpec::Real(EdnValue::Keyword(":item/label".to_string())), value: EdnValue::Symbol("_".to_string()), valid_from: None, valid_to: None, + meta: vec![(PseudoAttr::ValidFrom, "?#0.valid-from".to_string())], + pseudo_source: None, }; let seeded = matcher.match_pattern(&p1); assert_eq!(seeded.len(), 1, "seed should match one fact"); // Ask for :db/valid-from with an impossible constant value (-999) - // The hidden key exists but -999 won't match the real valid_from → vec![] + // The hidden variable is bound but -999 won't match it → vec![] let p2 = Pattern { entity: EdnValue::Symbol("?e".to_string()), attribute: AttributeSpec::Pseudo(PseudoAttr::ValidFrom), value: EdnValue::Integer(-999), valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: Some(EdnValue::Symbol("?#0.valid-from".to_string())), }; let results = matcher.match_patterns_seeded(&[p2], seeded); assert_eq!( diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index be2180504f..c405545353 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -155,6 +155,9 @@ fn pattern_bound_vars(p: &Pattern) -> Vec { { vars.push(s.clone()); } + // The hidden metadata variables a source binds, or a pseudo-attribute + // pattern reads (#594). + vars.extend(p.hidden_vars().map(str::to_string)); vars } @@ -213,11 +216,15 @@ pub fn plan( ) -> (Vec<(WhereClause, Option)>, Vec) { // Separate into patterns (with hints), exprs, and not/not-join clauses. let mut patterns: Vec<(WhereClause, IndexHint)> = Vec::new(); + let mut pseudos: Vec = Vec::new(); let mut exprs: Vec = Vec::new(); let mut not_clauses: Vec = Vec::new(); for clause in clauses { match &clause { + WhereClause::Pattern(p) if matches!(&p.attribute, AttributeSpec::Pseudo(a) if a.is_per_fact()) => { + pseudos.push(clause) + } WhereClause::Pattern(p) => { let hint = select_index(p); patterns.push((clause, hint)); @@ -248,6 +255,44 @@ pub fn plan( .map(|(clause, hint)| (clause, Some(hint))) .collect(); + // Place each per-fact pseudo-attribute pattern (#594) after the pattern + // that binds the metadata it reads (its source) and, when another pattern + // binds its value variable, after that one too, so that it checks rather + // than binds. It scans nothing, so selectivity does not order it. + let pattern_vars: std::collections::HashSet = result + .iter() + .filter_map(|(c, _)| match c { + WhereClause::Pattern(p) => Some(pattern_bound_vars(p)), + _ => None, + }) + .flatten() + .collect(); + for clause in pseudos { + let WhereClause::Pattern(p) = &clause else { + continue; + }; + let mut required: std::collections::HashSet = + p.hidden_vars().map(str::to_string).collect(); + if let EdnValue::Symbol(v) = &p.value + && pattern_vars.contains(v) + { + required.insert(v.clone()); + } + let hint = select_index(p); + let mut bound: std::collections::HashSet = Default::default(); + let mut insert_pos = result.len(); + for (pos, (c, _)) in result.iter().enumerate() { + if let WhereClause::Pattern(q) = c { + bound.extend(pattern_bound_vars(q)); + if required.is_subset(&bound) { + insert_pos = pos + 1; + break; + } + } + } + result.insert(insert_pos, (clause, Some(hint))); + } + // Push each Expr to the earliest position where all its variables are bound. for expr_clause in exprs { let vars: std::collections::HashSet = @@ -401,6 +446,8 @@ mod tests { use crate::query::datalog::types::{BinOp, EdnValue, Expr, Pattern, WhereClause}; use uuid::Uuid; + use crate::query::datalog::types::PseudoAttr; + fn make_pattern(entity: EdnValue, attribute: EdnValue, value: EdnValue) -> Pattern { Pattern::new(entity, attribute, value) } @@ -492,6 +539,39 @@ mod tests { ); } + #[test] + fn test_pseudo_attribute_runs_after_its_source() { + // [?e :age ?a] (source) [?e :db/tx-count ?t] [:p :score ?t]: the + // pseudo-attribute waits for its source and for the pattern that + // binds ?t, whatever the selectivity order (#594). + let mut source = make_pattern(var("e"), kw(":age"), var("a")); + source.meta = vec![(PseudoAttr::TxCount, "?#0.tx-count".to_string())]; + let mut pseudo = Pattern::pseudo(var("e"), PseudoAttr::TxCount, var("t")); + pseudo.pseudo_source = Some(EdnValue::Symbol("?#0.tx-count".to_string())); + let score = make_pattern(entity_lit(), kw(":score"), var("t")); + let (planned, _) = plan(vec![ + WhereClause::Pattern(source.clone()), + WhereClause::Pattern(pseudo.clone()), + WhereClause::Pattern(score.clone()), + ]); + let at = |p: &Pattern| { + planned + .iter() + .position(|(c, _)| matches!(c, WhereClause::Pattern(q) if q == p)) + .unwrap() + }; + assert!(at(&pseudo) > at(&source)); + assert!(at(&pseudo) > at(&score)); + // A `not` whose body reads the source waits for it too. + let mut in_not = pseudo.clone(); + in_not.value = EdnValue::Integer(1); + let (planned, _) = plan(vec![ + WhereClause::Pattern(source.clone()), + WhereClause::Not(vec![WhereClause::Pattern(in_not)]), + ]); + assert!(matches!(planned[1].0, WhereClause::Not(_))); + } + #[test] fn test_reorder_off_keeps_source_order() { let p1 = make_pattern(var("e"), kw(":age"), var("a")); diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index de3b3d9683..833faf20ee 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -911,6 +911,8 @@ fn parse_query(elements: &[EdnValue]) -> Result { i += 1; } + resolve_pseudo_sources(&mut where_clauses)?; + // Safety check: all variables in (not ...) and (not-join ...) must be bound by outer clauses let outer_bound: std::collections::HashSet = where_clauses .iter() @@ -1597,6 +1599,7 @@ fn outer_vars_from_clause(clause: &WhereClause) -> Vec { { vars.push(name.to_string()); } + vars.extend(p.hidden_vars().map(str::to_string)); vars } WhereClause::RuleInvocation { args, .. } => args @@ -1652,7 +1655,13 @@ fn outer_vars_from_clause(clause: &WhereClause) -> Vec { /// Collect all variable names that appear inside a Not clause. fn vars_in_not(clause: &WhereClause) -> Vec { match clause { - WhereClause::Not(inner) => inner.iter().flat_map(outer_vars_from_clause).collect(), + // Hidden metadata variables (#594) are resolved by construction: a + // body may bind its own, which no outer clause binds. + WhereClause::Not(inner) => inner + .iter() + .flat_map(outer_vars_from_clause) + .filter(|v| !v.starts_with("?#")) + .collect(), _ => vec![], } } @@ -1809,6 +1818,238 @@ fn check_expr_safety_with_bound( Ok(()) } +// ── Pseudo-attribute sources (#594) ────────────────────────────────────────── + +/// An entity term as the source search compares it (spec §2 of the #594 +/// design): variables and `$slot`s by name, constants by the entity they name. +#[derive(Clone, PartialEq)] +enum EntityTerm { + Var(String), + Slot(String), + Eid(Uuid), +} + +fn entity_term(e: &EdnValue) -> Option { + match e { + EdnValue::Symbol(s) if s.starts_with('?') && !s.starts_with("?_") => { + Some(EntityTerm::Var(s.clone())) + } + EdnValue::BindSlot(n) => Some(EntityTerm::Slot(n.clone())), + EdnValue::Keyword(_) | EdnValue::Uuid(_) => { + crate::query::datalog::matcher::edn_to_entity_id(e) + .ok() + .map(EntityTerm::Eid) + } + _ => None, + } +} + +/// A pattern with a stored attribute, a possible source. +#[derive(Clone)] +struct Candidate { + path: Vec, + term: EntityTerm, + /// Its position in a walk of the whole query: names its hidden variables. + n: usize, +} + +/// A clause list's containing clause, as seen from inside it. +struct Level { + /// The candidates before the containing clause, in the enclosing list. + before: Vec, + /// `Some` for `not-join` / `or-join`: only these variables cross it. + join: Option>, + /// The containing clause. + at: Vec, +} + +/// One per-fact pseudo-attribute pattern and its source. +struct Resolved { + pseudo: Vec, + source: Vec, + n: usize, + attr: PseudoAttr, + /// The `not-join` / `or-join` clauses between them. + crossed: Vec>, +} + +/// The nearest candidate for `term`: in the list so far, then outwards before +/// each containing clause, crossing a `-join` only for a listed variable. +fn find_source<'a>( + term: &EntityTerm, + here: &'a [Candidate], + stack: &'a [Level], +) -> Option<(&'a Candidate, Vec>)> { + if let Some(c) = here.iter().rev().find(|c| c.term == *term) { + return Some((c, Vec::new())); + } + let mut crossed = Vec::new(); + for level in stack.iter().rev() { + if let Some(vars) = &level.join { + match term { + EntityTerm::Var(v) if vars.contains(v) => crossed.push(level.at.clone()), + _ => return None, + } + } + if let Some(c) = level.before.iter().rev().find(|c| c.term == *term) { + return Some((c, crossed)); + } + } + None +} + +fn entity_text(e: &EdnValue) -> String { + match e { + EdnValue::Symbol(s) => s.clone(), + EdnValue::Keyword(k) => k.clone(), + EdnValue::Uuid(u) => format!("#uuid \"{u}\""), + EdnValue::BindSlot(n) => format!("${n}"), + _ => "_".to_string(), + } +} + +fn walk_sources( + list: &[WhereClause], + prefix: &[usize], + stack: &mut Vec, + next: &mut usize, + out: &mut Vec, +) -> Result<()> { + let mut here: Vec = Vec::new(); + for (i, clause) in list.iter().enumerate() { + let mut path = prefix.to_vec(); + path.push(i); + match clause { + WhereClause::Pattern(p) => match &p.attribute { + AttributeSpec::Pseudo(attr) if attr.is_per_fact() => { + let found = entity_term(&p.entity).and_then(|t| { + find_source(&t, &here, stack).map(|(c, crossed)| (c.clone(), crossed)) + }); + let Some((source, crossed)) = found else { + let e = entity_text(&p.entity); + bail_coded!(ErrorCode::Prs081, attr.as_keyword(), e, e); + }; + out.push(Resolved { + pseudo: path, + source: source.path, + n: source.n, + attr: attr.clone(), + crossed, + }); + } + AttributeSpec::Pseudo(_) => {} + AttributeSpec::Real(_) => { + if let Some(term) = entity_term(&p.entity) { + here.push(Candidate { + path, + term, + n: *next, + }); + *next += 1; + } + } + }, + WhereClause::Not(body) => { + stack.push(Level { + before: here.clone(), + join: None, + at: path.clone(), + }); + let r = walk_sources(body, &path, stack, next, out); + stack.pop(); + r?; + } + WhereClause::NotJoin { join_vars, clauses } => { + stack.push(Level { + before: here.clone(), + join: Some(join_vars.clone()), + at: path.clone(), + }); + let r = walk_sources(clauses, &path, stack, next, out); + stack.pop(); + r?; + } + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + let join = match clause { + WhereClause::OrJoin { join_vars, .. } => Some(join_vars.clone()), + _ => None, + }; + for (b, branch) in branches.iter().enumerate() { + let mut branch_path = path.clone(); + branch_path.push(b); + stack.push(Level { + before: here.clone(), + join: join.clone(), + at: path.clone(), + }); + let r = walk_sources(branch, &branch_path, stack, next, out); + stack.pop(); + r?; + } + } + WhereClause::RuleInvocation { .. } | WhereClause::Expr { .. } => {} + } + } + Ok(()) +} + +/// The clause at `path`: a clause index per list, and a branch index after +/// each `or` / `or-join`. +fn clause_at_mut<'a>(list: &'a mut [WhereClause], path: &[usize]) -> Option<&'a mut WhereClause> { + let (&i, rest) = path.split_first()?; + let clause = list.get_mut(i)?; + if rest.is_empty() { + return Some(clause); + } + match clause { + WhereClause::Not(body) | WhereClause::NotJoin { clauses: body, .. } => { + clause_at_mut(body, rest) + } + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + let (&b, rest) = rest.split_first()?; + clause_at_mut(branches.get_mut(b)?, rest) + } + _ => None, + } +} + +/// Give every per-fact pseudo-attribute pattern in `clauses` (a query's +/// `:where` or a rule body) its source (#594): the nearest pattern before it +/// in the text with the same entity term and a stored attribute, in its own +/// clause list and then outwards before each containing `not` / `or` +/// (`not-join` / `or-join` only for a listed entity variable). The source +/// binds a hidden variable `?#.` to its fact's metadata; the pseudo +/// pattern reads it; a crossed `-join` lists it. PRS-081 when there is none. +pub(crate) fn resolve_pseudo_sources(clauses: &mut [WhereClause]) -> Result<()> { + let mut resolved = Vec::new(); + walk_sources(clauses, &[], &mut Vec::new(), &mut 0, &mut resolved)?; + for r in resolved { + let name = format!( + "?#{}.{}", + r.n, + r.attr.as_keyword().trim_start_matches(":db/") + ); + if let Some(WhereClause::Pattern(source)) = clause_at_mut(clauses, &r.source) + && !source.meta.iter().any(|(a, _)| *a == r.attr) + { + source.meta.push((r.attr.clone(), name.clone())); + } + if let Some(WhereClause::Pattern(p)) = clause_at_mut(clauses, &r.pseudo) { + p.pseudo_source = Some(EdnValue::Symbol(name.clone())); + } + for at in &r.crossed { + if let Some( + WhereClause::NotJoin { join_vars, .. } | WhereClause::OrJoin { join_vars, .. }, + ) = clause_at_mut(clauses, at) + && !join_vars.contains(&name) + { + join_vars.push(name.clone()); + } + } + } + Ok(()) +} + fn parse_rule(elements: &[EdnValue]) -> Result { // Rule syntax: (rule [(predicate ?args) [pattern1] [pattern2] ...]) // elements[0] = Vector with head (list) + body (patterns/rule calls) @@ -1891,6 +2132,8 @@ fn parse_rule(elements: &[EdnValue]) -> Result { ); } + resolve_pseudo_sources(&mut body_clauses)?; + // Safety check: variables in (not ...) must be bound by the rule head or outer body clauses let mut outer_bound: std::collections::HashSet = std::collections::HashSet::new(); // Head args count as binding sites @@ -3080,6 +3323,92 @@ mod tests { parse_datalog_command(s) } + fn where_of(s: &str) -> Vec { + match parse(s).expect("parse") { + DatalogCommand::Query(q) => q.where_clauses, + _ => panic!("expected a query"), + } + } + + fn pattern_of(c: &WhereClause) -> &Pattern { + match c { + WhereClause::Pattern(p) => p, + _ => panic!("expected a pattern"), + } + } + + fn reads(p: &Pattern) -> Option<&str> { + p.pseudo_source.as_ref().and_then(|s| s.as_variable()) + } + + #[test] + fn pseudo_source_is_the_nearest_earlier_same_entity_pattern() { + let w = where_of( + "(query [:find ?t :any-valid-time :where \ + [?e :a ?x] [?f :b ?y] [?e :c ?z] [?e :db/tx-count ?t] [?e :db/valid-to ?u]])", + ); + // Candidates are numbered in walk order: [?e :c ?z] is #2. + let source = pattern_of(&w[2]); + assert_eq!( + source.meta, + vec![ + (PseudoAttr::TxCount, "?#2.tx-count".to_string()), + (PseudoAttr::ValidTo, "?#2.valid-to".to_string()), + ] + ); + assert!(pattern_of(&w[0]).meta.is_empty()); + assert_eq!(reads(pattern_of(&w[3])), Some("?#2.tx-count")); + assert_eq!(reads(pattern_of(&w[4])), Some("?#2.valid-to")); + } + + #[test] + fn pseudo_source_crossing_a_not_join_is_listed() { + let w = where_of( + "(query [:find ?e :any-valid-time :where \ + [?e :a ?x] (not-join [?e] [?e :db/tx-count 1])])", + ); + let WhereClause::NotJoin { join_vars, clauses } = &w[1] else { + panic!("expected not-join"); + }; + assert_eq!( + join_vars, + &vec!["?e".to_string(), "?#0.tx-count".to_string()] + ); + assert_eq!(reads(pattern_of(&clauses[0])), Some("?#0.tx-count")); + // Through `not` nothing is listed. + let w = where_of( + "(query [:find ?e :any-valid-time :where [?e :a ?x] (not [?e :db/tx-count 1])])", + ); + let WhereClause::Not(body) = &w[1] else { + panic!("expected not"); + }; + assert_eq!(reads(pattern_of(&body[0])), Some("?#0.tx-count")); + } + + #[test] + fn pseudo_source_in_an_or_branch_is_its_own_or_outer() { + let w = where_of( + "(query [:find ?e :any-valid-time :where \ + [?e :a ?x] (or [?e :b 1] [?e :db/tx-count 1])])", + ); + let WhereClause::Or(branches) = &w[1] else { + panic!("expected or"); + }; + // The second branch reads the outer pattern, not the first branch's. + assert_eq!(reads(pattern_of(&branches[1][0])), Some("?#0.tx-count")); + assert!(pattern_of(&branches[0][0]).meta.is_empty()); + } + + #[test] + fn pseudo_source_missing_is_prs_081() { + let err = + parse("(query [:find ?t :any-valid-time :where [?e :db/tx-count ?t] [?e :a ?x]])") + .expect_err("no source"); + assert!(err.to_string().contains(":db/tx-count on ?e")); + let err = parse("(rule [(r ?e ?t) [?e :db/tx-id ?t]])").expect_err("rule body closed"); + assert!(err.to_string().contains(":db/tx-id on ?e")); + } + #[test] fn test_parse_expr_lt_filter() { // [(< ?v 100)] — filter clause diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 3e96de9a5d..717cf47d06 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -336,9 +336,27 @@ pub struct Pattern { pub valid_from: Option, /// Per-fact valid-time override (millis since epoch). None = use transaction-level default. pub valid_to: Option, + /// The hidden metadata variables this pattern binds from the fact it + /// matches, one per per-fact pseudo-attribute that reads it (#594): set by + /// `parser::resolve_pseudo_sources`, empty otherwise. + pub meta: Vec<(PseudoAttr, String)>, + /// For a per-fact pseudo-attribute pattern: the hidden variable of its + /// source pattern (a symbol), which it reads from the row instead of + /// scanning facts (#594), or the metadata itself once a `not` body or a + /// prepared query has substituted the variable (an integer). + pub pseudo_source: Option, } impl Pattern { + /// The hidden metadata variables this pattern binds, and the one it + /// reads (#594). + pub(crate) fn hidden_vars(&self) -> impl Iterator { + self.meta + .iter() + .map(|(_, v)| v.as_str()) + .chain(self.pseudo_source.iter().filter_map(|s| s.as_variable())) + } + pub fn new(entity: EdnValue, attribute: EdnValue, value: EdnValue) -> Self { Pattern { entity, @@ -346,6 +364,8 @@ impl Pattern { value, valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: None, } } @@ -357,6 +377,8 @@ impl Pattern { value, valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: None, } } @@ -369,6 +391,8 @@ impl Pattern { value, valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: None, } } @@ -386,6 +410,8 @@ impl Pattern { value, valid_from, valid_to, + meta: Vec::new(), + pseudo_source: None, } } @@ -415,6 +441,8 @@ impl Pattern { .ok_or_else(|| "Pattern missing value (index 2)".to_string())?, valid_from: None, valid_to: None, + meta: Vec::new(), + pseudo_source: None, }) } } diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 57087cb4f6..281ad90566 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -6,7 +6,7 @@ use super::batch::Batch; use super::cell::{Cell, join_eq}; -use super::plan::{Entity, Out, Step, Term, Vars}; +use super::plan::{Out, Step, Term, Vars}; use super::project::value; use super::{Counters, Ctx, Operator}; use crate::query::datalog::executor::{eval_expr, is_truthy}; @@ -63,12 +63,8 @@ impl Operator for Apply { /// Apply `step` to `batch`. fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { match step { - Step::Pseudo { - cols, - entity, - value, - } => { - let meta = pick(cols, entity.as_ref(), &batch, ctx)?; + Step::Pseudo { col, value } => { + let meta = batch.cols.get(*col).cloned().unwrap_or_default(); match value { Term::Any => {} Term::Bind(slot) => batch.set_col(*slot, meta), @@ -130,57 +126,6 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { Ok(batch) } -/// The metadata a pseudo-attribute pattern reads in each row of `batch`: -/// from the first of `cols` with no entity, or whose entity is join-equal to -/// `entity` (decision 4 of the #545 plan). -fn pick( - cols: &[(Option, usize)], - entity: Option<&Entity>, - batch: &Batch, - ctx: &mut Ctx<'_>, -) -> Result> { - if let [(None, col)] = cols { - return Ok(batch.cols.get(*col).cloned().unwrap_or_default()); - } - let mut out = Vec::with_capacity(batch.len); - for i in 0..batch.len { - let want = match entity { - Some(e) => entity_cell(e, batch, i, ctx)?, - None => None, - }; - for (e, col) in cols { - let matched = match (e, &want) { - (None, _) => true, - (Some(e), Some(w)) => match entity_cell(e, batch, i, ctx)? { - Some(c) => join_eq(&c, w, true, ctx)?, - None => false, - }, - (Some(_), None) => false, - }; - if matched { - if let Some(c) = batch.cols.get(*col).and_then(|c| c.get(i)) { - out.push(c.clone()); - } - break; - } - } - } - Ok(out) -} - -/// The cell of `entity` in row `i`. -fn entity_cell( - entity: &Entity, - batch: &Batch, - i: usize, - ctx: &mut Ctx<'_>, -) -> Result> { - Ok(match entity { - Entity::Slot(s) => batch.cols.get(*s).and_then(|c| c.get(i)).cloned(), - Entity::Const(u) => Some(Cell::Eid(ctx.ids.eid(ctx.keys, u)?)), - }) -} - /// `expr` over row `i`, or `None` where the executor's evaluation fails. fn eval( expr: &Expr, diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index e49d7dbaf1..fb5d1e20c8 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -13,14 +13,12 @@ //! a variable already bound, a `HashJoin` otherwise (decision 3 of the #545 //! plan). //! -//! A per-fact pseudo-attribute pattern reads, as the executor does, the fact -//! of the last pattern with a stored attribute before it that matched the -//! same entity (decision 4 of the #545 plan): one of the metadata columns -//! those patterns' scans fill, chosen per row. The engine runs it when the -//! pattern's entity term is the entity term of such a pattern, so that one -//! always exists, or when no such pattern runs before it. A pseudo-attribute -//! pattern of the second kind, and every `:db/valid-at` pattern, joins with -//! every visible fact of its entity, as `[e _ _]` does. +//! A per-fact pseudo-attribute pattern reads the metadata of the fact its +//! source matched (#594): the parser names the source, which binds a hidden +//! variable per pseudo-attribute, and its scan or join fills that slot from +//! the fact's key. The pseudo-attribute pattern binds or checks its value +//! against the slot. A `:db/valid-at` pattern joins with every visible fact +//! of its entity, as `[e _ _]` does, with the query's valid time as a column. use super::cell::Scalar; use crate::graph::types::{EntityId, Value}; @@ -99,13 +97,6 @@ pub(crate) enum Meta { ValidAt, } -/// The entity a pattern matched, in a row: a slot, or a constant. -#[derive(Debug, Clone)] -pub(crate) enum Entity { - Slot(usize), - Const(EntityId), -} - /// What a `Scan` reads. #[derive(Debug, Clone)] pub(crate) struct ScanSpec { @@ -123,13 +114,10 @@ pub(crate) struct ScanSpec { /// A clause after the scan, in the executor's order. #[derive(Debug, Clone)] pub(crate) enum Step { - /// A pseudo-attribute pattern: its value term over a metadata column. - /// The row's column is the first of `cols` with no entity, or whose - /// entity is join-equal to `entity`. A constant other than an integer or - /// `nil` never matches. + /// A pseudo-attribute pattern: its value term over the metadata column + /// `col`. A constant other than an integer or `nil` never matches. Pseudo { - cols: Vec<(Option, usize)>, - entity: Option, + col: usize, value: Term>, }, /// `[(pred …)]`: keeps the rows where the expression is truthy. @@ -254,44 +242,25 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { let mut binders = Binders::new(&query.where_clauses, Vec::new()); let (planned, _) = optimizer::plan(query.where_clauses.clone()); let all: Vec = planned.into_iter().map(|(c, _)| c).collect(); - let (forms, needs) = pseudo_forms(&all)?; - let mut slots = Slots::default(); - // Each clause placed so far. - let mut done: Vec = Vec::with_capacity(all.len()); let mut outer_patterns: Vec = Vec::new(); let mut scan = None; let mut steps = Vec::with_capacity(all.len()); - for (i, c) in all.into_iter().enumerate() { - let need = needs.get(i).map_or(&[][..], Vec::as_slice); - let mut metas: Vec<(Meta, usize)> = Vec::new(); - let mut entity = None; + for c in all { match c { WhereClause::Pattern(q) => { let rebind = binders.pattern(&q); - let form = forms.get(&i); - if let Some(PseudoForm::Fast { cols }) = form { - let cols = cols - .iter() - .map(|&(j, compare)| { - let (metas, entity) = done.get(j)?; - let col = metas.iter().find(|(m, _)| Some(*m) == meta(&q))?.1; - let entity = if compare { Some(entity.clone()?) } else { None }; - Some((entity, col)) - }) - .collect::>>()?; - let entity = entity_of(&q.entity, &slots); + 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 = *slots.by_var.get(source)?; let value = term(&q.value, &mut slots, OTHER, pseudo_const)?; - steps.push(Step::Pseudo { - cols, - entity, - value, - }); - done.push((metas, None)); + steps.push(Step::Pseudo { col, value }); continue; } - // A pattern with a stored attribute, or a pseudo-attribute - // pattern read as `[e _ _]` and its metadata. + // A pattern with a stored attribute, or `:db/valid-at` read + // as `[e _ _]` and the query's valid time. let any = EdnValue::Symbol("_".to_string()); let (attribute, scanned) = match &q.attribute { AttributeSpec::Real(a) => (a.clone(), q.clone()), @@ -300,15 +269,28 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { Pattern::new(q.entity.clone(), any.clone(), any.clone()), ), }; - let mut wants: Vec = need.to_vec(); - if let Some(m) = form.and(meta(&q)) { - wants.push(m); + // The metadata columns: the hidden variables of a source, or + // the valid time. + let mut wants: Vec<(Meta, Option<&str>)> = q + .meta + .iter() + .map(|(a, v)| (meta_of(a), Some(v.as_str()))) + .collect(); + if pseudo.is_some() { + wants.push((Meta::ValidAt, None)); } + let mut metas: Vec<(Meta, usize)> = Vec::new(); if scan.is_none() { let e = term(&scanned.entity, &mut slots, OTHER, entity_const)?; let a = term(&attribute, &mut slots, ATTRIBUTE, attribute_const)?; let v = term(&scanned.value, &mut slots, OTHER, value_const)?; - metas = wants.iter().map(|&m| (m, slots.add(OTHER))).collect(); + for &(m, var) in &wants { + let slot = slots.add(OTHER); + if let Some(var) = var { + slots.by_var.insert(var.to_string(), slot); + } + metas.push((m, slot)); + } scan = Some(ScanSpec { e, a, @@ -320,12 +302,16 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { }); } else { let mut join = join(&scanned, &attribute, &mut slots, &rebind, as_of, valid)?; - for &m in &wants { + for &(m, var) in &wants { let local = join.inner.width; join.inner.width += 1; join.inner.meta.push((m, local)); join.new.push(local); - metas.push((m, slots.add(OTHER))); + let slot = slots.add(OTHER); + if let Some(var) = var { + slots.by_var.insert(var.to_string(), slot); + } + metas.push((m, slot)); } if let JoinKind::Hash { build_inner } = &mut join.kind { // With the test switch off, always the inner pattern @@ -337,16 +323,11 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { } steps.push(Step::Join(join)); } - entity = entity_of(&q.entity, &slots); outer_patterns.push(WhereClause::Pattern(q.clone())); - if form.is_some() { + if pseudo.is_some() { let col = metas.last()?.1; let value = term(&q.value, &mut slots, OTHER, pseudo_const)?; - steps.push(Step::Pseudo { - cols: vec![(None, col)], - entity: None, - value, - }); + steps.push(Step::Pseudo { col, value }); } } WhereClause::Expr { expr, binding } => { @@ -378,7 +359,6 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { } _ => return None, } - done.push((metas, entity)); } let scan = scan?; @@ -516,105 +496,16 @@ fn meta(p: &Pattern) -> Option { let AttributeSpec::Pseudo(pa) = &p.attribute else { return None; }; - Some(match pa { + Some(meta_of(pa)) +} + +fn meta_of(pa: &PseudoAttr) -> Meta { + match pa { PseudoAttr::ValidFrom => Meta::ValidFrom, PseudoAttr::ValidTo => Meta::ValidTo, PseudoAttr::TxCount => Meta::TxCount, PseudoAttr::TxId => Meta::TxId, PseudoAttr::ValidAt => Meta::ValidAt, - }) -} - -/// A clause the planner has placed: the metadata slots its scan fills, and -/// its entity. -type Ran = (Vec<(Meta, usize)>, Option); - -/// The form of each pseudo-attribute pattern, by clause index. -type Forms = HashMap; - -/// How a pseudo-attribute pattern runs. -enum PseudoForm { - /// It reads the metadata of an earlier pattern: of the first of `cols` - /// (clause indexes, last first) that matched its entity, where the flag - /// says whether the entity must be compared. The last one is the latest - /// pattern with the same entity term, which always did. - Fast { cols: Vec<(usize, bool)> }, - /// It joins with every visible fact of its entity. - Join, -} - -/// The form of each pseudo-attribute pattern of `all` (clauses in plan -/// order), by index, and the metadata each pattern's scan must fill; `None` -/// when one of them reads a pattern chosen by the row in a way the engine -/// does not reproduce, so the executor runs the query. -fn pseudo_forms(all: &[WhereClause]) -> Option<(Forms, Vec>)> { - let pattern = |c: &WhereClause| match c { - WhereClause::Pattern(p) => Some(p.clone()), - _ => None, - }; - let patterns: Vec> = all.iter().map(pattern).collect(); - let mut forms = HashMap::new(); - let mut needs = vec![Vec::new(); all.len()]; - for (i, q) in patterns.iter().enumerate() { - let Some(m) = q.as_ref().and_then(meta) else { - continue; - }; - let Some(q) = q else { continue }; - // Earlier patterns with a stored attribute: the executor's per-entity - // metadata of the fact each matched, the latest kept. - let reals: Vec<(usize, &Pattern)> = patterns - .iter() - .take(i) - .enumerate() - .filter_map(|(j, p)| p.as_ref().map(|p| (j, p))) - .filter(|(_, p)| matches!(p.attribute, AttributeSpec::Real(_))) - .collect(); - if m == Meta::ValidAt || reals.is_empty() { - forms.insert(i, PseudoForm::Join); - continue; - } - let last = reals - .iter() - .rposition(|(_, p)| same_entity(&p.entity, &q.entity))?; - let mut cols = Vec::new(); - for &(j, p) in reals.iter().skip(last + 1).rev() { - match (&p.entity, &q.entity) { - (EdnValue::Symbol(s), _) if s == "_" || s.starts_with("?_") => return None, - (EdnValue::Symbol(_), _) | (_, EdnValue::Symbol(_)) => cols.push((j, true)), - // Two constants naming different entities. - _ => {} - } - } - cols.push((reals.get(last)?.0, false)); - for &(j, _) in &cols { - if let Some(n) = needs.get_mut(j) - && !n.contains(&m) - { - n.push(m); - } - } - forms.insert(i, PseudoForm::Fast { cols }); - } - // An expression that rebinds an entity variable would send a later - // pseudo-attribute pattern to the metadata of another entity. - if !forms.is_empty() - && all.iter().any(|c| { - matches!(c, WhereClause::Expr { binding: Some(out), .. } - if patterns.iter().flatten().any( - |p| matches!(&p.entity, EdnValue::Symbol(s) if s == out))) - }) - { - return None; - } - Some((forms, needs)) -} - -/// The entity `edn` gives a row: a bound variable's slot, or a constant. -fn entity_of(edn: &EdnValue, slots: &Slots) -> Option { - match edn { - EdnValue::Symbol(s) => slots.by_var.get(s).map(|&s| Entity::Slot(s)), - EdnValue::Keyword(_) | EdnValue::Uuid(_) => edn_to_entity_id(edn).ok().map(Entity::Const), - _ => None, } } @@ -629,20 +520,6 @@ fn pseudo_const(c: &EdnValue) -> Option> { }) } -/// Whether two entity terms name the same entity in every row: one -/// variable, or constants naming one entity. -fn same_entity(a: &EdnValue, b: &EdnValue) -> bool { - match (a, b) { - (EdnValue::Symbol(s), EdnValue::Symbol(t)) => { - s.starts_with('?') && !s.starts_with("?_") && s == t - } - (EdnValue::Keyword(_) | EdnValue::Uuid(_), EdnValue::Keyword(_) | EdnValue::Uuid(_)) => { - edn_to_entity_id(a).ok() == edn_to_entity_id(b).ok() - } - _ => false, - } -} - /// The variables of `expr` bound so far, with their slots. A variable bound /// later, or never, is left out: the expression fails on it, as it does in /// the executor. diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 965fa13c51..b2aac37954 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -194,10 +194,9 @@ fn queries(tx: u64) -> Vec { "[?e :person/age ?v] [?e :db/tx-count _] [?e :db/tx-count ?t]", ), ]; - // Pseudo-attributes across joins (#545): the metadata of the last - // pattern before them, in plan order, that matched their entity, chosen - // per row; pseudo-attribute patterns with no such pattern before them - // join with every fact of their entity. + // Pseudo-attributes across joins (#545, #594): the metadata of their + // source, the nearest pattern before them in the text with the same + // entity term, whatever the plan runs first. let pseudo_joins = [ "[?e :person/name ?n] [?e :person/age ?a] [?e :db/tx-count ?t]", "[?e :person/age ?a] [?e :db/tx-count ?t] [?e :person/name ?n] [?e :db/valid-from ?f]", @@ -209,11 +208,15 @@ fn queries(tx: u64) -> Vec { "[?e :person/self ?x] [:p1 :person/age ?a] [:p1 :db/tx-count ?t]", "[?e :person/self ?x] [:p1 :person/age ?a] [?e :db/tx-count ?t]", "[?e :person/friend :p1] [:p1 :person/age ?a] [?e :db/tx-count ?t]", - "[?e :db/tx-count ?t] [?e :person/age ?a]", - "[?e :db/tx-count 1] [?e :person/name ?n]", - "[?e :db/tx-count 2] [?f :db/tx-count 2] [?e :person/self ?f]", - "[?e :db/valid-from ?f] [?e :db/valid-to ?u]", - "[:p1 :db/tx-count ?t]", + "[?e ?b _] [?e :db/tx-count ?t] [?e :person/age ?a]", + "[?e ?b _] [?e :db/tx-count 1] [?e :person/name ?n]", + "[?e ?b _] [?e :db/tx-count 2] [?f ?c _] [?f :db/tx-count 2] [?e :person/self ?f]", + "[?e ?b _] [?e :db/valid-from ?f] [?e :db/valid-to ?u]", + "[:p1 ?b _] [:p1 :db/tx-count ?t]", + "[:p1 :person/age ?a] [#uuid \"{p1}\" :db/tx-count ?t]", + "[?e :person/name ?n] [(+ 1 2) ?e] [?e :db/tx-count ?t]", + "[?e :person/name \"n1\"] [_ :person/age ?a] [?e :db/tx-count ?t]", + "[?e :person/age ?a] [?e :person/name ?n] [?e :db/tx-count ?t] [?e :db/tx-id ?i]", "[?e :person/age ?a] [?f :person/age ?a] [?f :db/tx-count ?t] [?e :db/tx-count ?t]", "[?e :person/age ?a] [(+ ?a 1) ?b] [?e :db/tx-id ?t] [(> ?t 0)]", ]; @@ -255,7 +258,8 @@ fn queries(tx: u64) -> Vec { } } for clauses in pseudo_joins { - let find = vars_of(clauses); + let clauses = clauses.replace("{p1}", &uuid_of(":p1").to_string()); + let find = vars_of(&clauses); for temporal in &pseudo_temporals { out.push(format!( "(query [:find {find} {temporal} :where {clauses}])" @@ -421,9 +425,7 @@ fn engine_reads_many_batches() { } /// The executor still runs what the engine does not: aggregates, `:as-of` a -/// timestamp, a pseudo-attribute pattern whose metadata comes from a pattern -/// chosen per row in a way the engine does not reproduce (another entity's -/// pattern before it, a `_` entity), an expression rebinding an entity. +/// timestamp. #[test] fn other_queries_stay_on_the_executor() { let db = Minigraf::in_memory().unwrap(); @@ -431,20 +433,32 @@ fn other_queries_stay_on_the_executor() { for q in [ "(query [:find (count ?e) :where [?e :person/name ?n]])", "(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"); + } +} + +/// A pseudo-attribute pattern with no source is refused at parse time +/// (#594): another entity's pattern before it, a `_` entity, an entity an +/// expression binds, none before it. +#[test] +fn pseudo_attributes_without_a_source_are_prs_081() { + let db = Minigraf::in_memory().unwrap(); + write_round(&db, 0); + for q in [ "(query [:find ?e ?t :valid-at :any-valid-time \ :where [?e :person/friend ?f] [?f :db/tx-count ?t]])", "(query [:find ?e ?t :valid-at :any-valid-time \ :where [_ :person/name ?e] [_ :db/tx-count ?t]])", - "(query [:find ?n ?t :valid-at :any-valid-time \ - :where [?e :person/name ?n] [(+ 1 2) ?e] [?e :db/tx-count ?t]])", - "(query [:find ?e ?t :valid-at :any-valid-time \ - :where [?e :person/name \"n1\"] [_ :person/age ?a] [?e :db/tx-count ?t]])", "(query [:find ?e ?t :valid-at :any-valid-time \ :where [?e :person/age ?a] [(+ ?a 1) ?b] [?b :db/tx-count ?t]])", + "(query [:find ?e ?t :valid-at :any-valid-time \ + :where [?e :db/tx-count ?t] [?e :person/age ?a]])", ] { - let before = runs(); - db.execute(q).unwrap(); - assert_eq!(runs(), before, "query stayed on the executor"); + let err = db.execute(q).unwrap_err(); + assert_eq!(crate::MinigrafError::from(err).code(), "PRS-081"); } } diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs index 796bb00324..4d3fab6cc7 100644 --- a/tests/plan_independence_test.rs +++ b/tests/plan_independence_test.rs @@ -6,10 +6,7 @@ //! (`minigraf::__reorder`), and all four answers must be the same bag. With //! the `test-oracle` feature, every query the streaming engine runs is also //! run by the executor and must agree, so each run compares the two as well. -//! -//! Per-fact pseudo-attributes (`:db/valid-from`, `:db/valid-to`, -//! `:db/tx-count`, `:db/tx-id`) whose source depends on the plan are #594 and -//! are left out of this matrix until it is fixed. +//! Per-fact pseudo-attributes read the source the parser names (#594). #![cfg(all(feature = "test-oracle", not(target_arch = "wasm32")))] use minigraf::{Minigraf, QueryResult, Value}; @@ -113,6 +110,8 @@ fn people(db: &Minigraf) { .unwrap(); db.execute("(rule [(lonely ?e) [?e :name _] (not [?e :friend _])])") .unwrap(); + db.execute("(rule [(stamped ?e ?t) [?e :name _] [?e :db/tx-count ?t]])") + .unwrap(); } /// Queries whose answers must not depend on the plan. @@ -160,6 +159,19 @@ const MATRIX: &[&str] = &[ r#"[:find ?n :where [?e :name ?n] [?e :age ?a] (not-join [?a] [?f :age ?a] [?f :friend :carol])]"#, // Aggregates. r#"[:find ?a (count ?e) :where [?e :age ?a] [?e :name _]]"#, + // Per-fact pseudo-attributes (#594): #594's example in both text orders, + // across joins, in `not`, `not-join`, `or`, `or-join` and rule bodies. + r#"[:find ?n ?t :any-valid-time :where [?e :name ?n] [?e :age ?a] [?e :db/tx-count ?t]]"#, + r#"[:find ?n ?t :any-valid-time :where [?e :age ?a] [?e :name ?n] [?e :db/tx-count ?t]]"#, + r#"[:find ?n ?t :any-valid-time :where [?e :name "Alice"] [?e :age ?a] [?e :name ?n] [?e :db/tx-id ?t]]"#, + r#"[:find ?e ?t ?f :any-valid-time :where [?e :friend ?b] [?b :name ?n] [?e :db/tx-count ?t] [?e :db/valid-from ?f]]"#, + r#"[:find ?e ?a ?t :any-valid-time :where [?e ?a _] [?e :db/tx-count ?t]]"#, + r#"[:find ?e ?t :any-valid-time :where [?e :age ?a] [?p :score ?t] [?e :db/tx-count ?t]]"#, + r#"[:find ?n :any-valid-time :where [?e :name ?n] (not [?e :db/tx-count 1])]"#, + r#"[:find ?n :any-valid-time :where [?e :name ?n] (not-join [?e] [?e :db/valid-to ?u] [(< ?u 0)])]"#, + r#"[:find ?n :any-valid-time :where [?e :name ?n] (or [?e :db/tx-count 1] [?e :age 40])]"#, + r#"[:find ?n :any-valid-time :where [?e :name ?n] (or-join [?e] [?e :db/tx-count 1] [?e :friend _])]"#, + r#"[:find ?e ?t :any-valid-time :where (stamped ?e ?t) [?e :age ?a]]"#, // Time travel. r#"[:find ?n :as-of 1 :where [?e :name ?n] [?e :age ?a]]"#, r#"[:find ?n ?a :valid-at "2020-06-01T00:00:00Z" :where [?e :name ?n] [?e :age ?a]]"#, @@ -203,6 +215,8 @@ fn matrix_file_backed_after_checkpoint() { .unwrap(); db.execute("(rule [(lonely ?e) [?e :name _] (not [?e :friend _])])") .unwrap(); + db.execute("(rule [(stamped ?e ?t) [?e :name _] [?e :db/tx-count ?t]])") + .unwrap(); run_matrix(&db); } diff --git a/tests/pseudo_source_test.rs b/tests/pseudo_source_test.rs new file mode 100644 index 0000000000..162dab6a52 --- /dev/null +++ b/tests/pseudo_source_test.rs @@ -0,0 +1,306 @@ +//! Pseudo-attribute sources (#594, design +//! `docs/superpowers/specs/2026-10-15-plan-independent-answers-design.md` +//! §3.1–3.3): a per-fact pseudo-attribute (`:db/valid-from`, `:db/valid-to`, +//! `:db/tx-count`, `:db/tx-id`) reads the fact of the nearest pattern before +//! it in the text with the same entity term and a stored attribute, in its own +//! clause list and then outwards before each containing `not` / `or` +//! (`not-join` / `or-join` only for a listed entity variable), never past a +//! rule body; with none the query is PRS-081. + +use minigraf::{Minigraf, QueryResult, Value}; + +fn rows(r: QueryResult) -> Vec> { + match r { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected QueryResults"), + } +} + +fn query(db: &Minigraf, q: &str) -> Vec> { + let mut r = rows(db.execute(&format!("(query {q})")).expect("query")); + r.sort_by_key(|row| { + row.iter() + .map(|v| match v { + Value::Integer(i) => format!("{i:020}"), + Value::String(s) => s.clone(), + _ => String::new(), + }) + .collect::>() + }); + r +} + +fn code(db: &Minigraf, q: &str) -> &'static str { + db.execute(&format!("(query {q})")) + .expect_err("query must fail") + .code() +} + +fn int(v: &Value) -> i64 { + match v { + Value::Integer(i) => *i, + _ => panic!("expected an integer"), + } +} + +fn s(v: &str) -> Value { + Value::String(v.to_string()) +} + +fn alice() -> uuid::Uuid { + uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":alice") +} + +/// tx 1: Alice's name (valid from 2020); tx 2: her age (valid from 2021); +/// tx 3: Bob's name; tx 4: Alice's friend; tx 5: a count of 3. +fn db() -> Minigraf { + let db = Minigraf::in_memory().unwrap(); + db.execute(r#"(transact {:valid-from "2020-01-01"} [[:alice :person/name "Alice"]])"#) + .unwrap(); + db.execute(r#"(transact {:valid-from "2021-01-01"} [[:alice :person/age 30]])"#) + .unwrap(); + db.execute(r#"(transact [[:bob :person/name "Bob"]])"#) + .unwrap(); + db.execute(r#"(transact [[:alice :person/friend :bob]])"#) + .unwrap(); + db.execute(r#"(transact [[:k :count 3]])"#).unwrap(); + db +} + +const ANY: &str = ":any-valid-time"; + +#[test] +fn nearest_earlier_pattern_in_the_text_is_the_source() { + let db = db(); + // #594's example: the age pattern is nearest, whatever runs last. + let r = query( + &db, + &format!( + "[:find ?n ?t {ANY} :where [?e :person/name ?n] [?e :person/age ?a] [?e :db/tx-count ?t]]" + ), + ); + assert_eq!( + r, + vec![vec![s("Alice"), Value::Integer(2)]], + "age fact, tx 2" + ); + let r = query( + &db, + &format!( + "[:find ?n ?t {ANY} :where [?e :person/age ?a] [?e :person/name ?n] [?e :db/tx-count ?t]]" + ), + ); + assert_eq!( + r, + vec![vec![s("Alice"), Value::Integer(1)]], + "name fact, tx 1" + ); +} + +#[test] +fn two_pseudo_attributes_share_a_source() { + let db = db(); + let r = query( + &db, + &format!( + "[:find ?t ?f {ANY} :where [?e :person/age _] [?e :db/tx-count ?t] [?e :db/valid-from ?f]]" + ), + ); + assert_eq!(r.len(), 1); + assert_eq!(int(&r[0][0]), 2); + assert_eq!(int(&r[0][1]), 1_609_459_200_000, "2021-01-01"); +} + +#[test] +fn every_fact_of_an_entity_through_a_variable_attribute() { + let db = db(); + // One row per fact of :alice: name (1), age (2), friend (4). + let r = query( + &db, + &format!("[:find ?a ?t {ANY} :where [:alice ?a _] [:alice :db/tx-count ?t]]"), + ); + let ts: Vec = r.iter().map(|row| int(&row[1])).collect(); + assert_eq!(ts, vec![1, 2, 4]); +} + +#[test] +fn constant_and_bound_values_check_the_metadata() { + let db = db(); + let r = query( + &db, + &format!("[:find ?n {ANY} :where [?e :person/name ?n] [?e :db/tx-count 3]]"), + ); + assert_eq!(r, vec![vec![s("Bob")]]); + // `?t` is bound by `[?k :count ?t]` first: the pseudo-attribute checks. + let r = query( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] [?k :count ?t] [?e :db/tx-count ?t]]" + ), + ); + assert_eq!(r, vec![vec![s("Bob")]]); +} + +#[test] +fn constants_name_the_same_entity_by_id() { + let db = db(); + let r = query( + &db, + &format!( + r#"[:find ?t {ANY} :where [:alice :person/age _] [#uuid "{}" :db/tx-count ?t]]"#, + alice() + ), + ); + assert_eq!(r, vec![vec![Value::Integer(2)]]); + // A variable and a constant are never the same term. + assert_eq!( + code( + &db, + &format!("[:find ?t {ANY} :where [?e :person/age _] [:alice :db/tx-count ?t]]") + ), + "PRS-081" + ); +} + +#[test] +fn no_source_is_prs_081() { + let db = db(); + for q in [ + // The pattern is after the pseudo-attribute. + "[:find ?t :any-valid-time :where [?e :db/tx-count ?t] [?e :person/name ?n]]", + // Alone. + "[:find ?t :any-valid-time :where [:alice :db/valid-to ?t]]", + // `_` and `?_` entities are never the same as anything. + "[:find ?t :any-valid-time :where [_ :person/name ?n] [_ :db/tx-id ?t]]", + "[:find ?t :any-valid-time :where [?_x :person/name ?n] [?_x :db/tx-id ?t]]", + // Another entity's pattern. + "[:find ?t :any-valid-time :where [?e :person/friend ?f] [?f :db/tx-count ?t]]", + // A rule call is not a source. + "[:find ?t :any-valid-time :where (knows ?e ?f) [?e :db/tx-count ?t]]", + ] { + assert_eq!(code(&db, q), "PRS-081", "{q}"); + } +} + +#[test] +fn a_not_body_reads_the_outer_fact() { + let db = db(); + // Alice's name fact is tx 1, Bob's tx 3: the body reads the outer + // `[?e :person/name ?n]` fact, not any fact of the entity. + let r = query( + &db, + &format!("[:find ?n {ANY} :where [?e :person/name ?n] (not [?e :db/tx-count 1])]"), + ); + assert_eq!(r, vec![vec![s("Bob")]]); + let r = query( + &db, + &format!("[:find ?n {ANY} :where [?e :person/name ?n] (not [?e :db/tx-count 2])]"), + ); + assert_eq!(r.len(), 2, "no name fact is tx 2"); + // A source inside the body. + let r = query( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (not [?e :person/age _] [?e :db/tx-count 2])]" + ), + ); + assert_eq!(r, vec![vec![s("Bob")]]); +} + +#[test] +fn not_join_crosses_only_for_a_listed_variable() { + let db = db(); + let r = query( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (not-join [?e] [?e :db/tx-count 1])]" + ), + ); + assert_eq!(r, vec![vec![s("Bob")]]); + // `?e` is not listed: inside it is fresh, with no source. + assert_eq!( + code( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (not-join [?n] [?e :db/tx-count 1])]" + ) + ), + "PRS-081" + ); +} + +#[test] +fn or_branches_read_the_outer_fact_never_a_sibling() { + let db = db(); + let r = query( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (or [?e :db/tx-count 1] [?e :db/tx-count 3])]" + ), + ); + assert_eq!(r.len(), 2); + // The second branch reads the name fact (tx 1), not the first branch's + // age pattern (tx 2), so nothing matches. + let r = query( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (or [?e :person/age 99] [?e :db/tx-count 2])]" + ), + ); + assert!(r.is_empty()); + let r = query( + &db, + &format!("[:find ?n {ANY} :where [?e :person/name ?n] (or-join [?e] [?e :db/tx-count 3])]"), + ); + assert_eq!(r, vec![vec![s("Bob")]]); + assert_eq!( + code( + &db, + &format!( + "[:find ?n {ANY} :where [?e :person/name ?n] (or-join [?n] [?e :db/tx-count 3])]" + ) + ), + "PRS-081" + ); +} + +#[test] +fn rule_bodies_are_closed() { + let db = db(); + let err = db + .execute("(rule [(stamp ?e ?t) [?e :db/tx-count ?t]])") + .expect_err("no source in the body"); + assert_eq!(err.code(), "PRS-081"); + db.execute("(rule [(stamp ?e ?t) [?e :person/name _] [?e :db/tx-count ?t]])") + .unwrap(); + // The caller's age pattern is not the source: the body's name fact is. + let r = query( + &db, + &format!("[:find ?t {ANY} :where [?e :person/age _] (stamp ?e ?t)]"), + ); + assert_eq!(r, vec![vec![Value::Integer(1)]]); +} + +#[test] +fn prepared_slots_compare_by_name() { + let db = db(); + // Resolved on the template, before any value is bound: the same slot is + // the same term, whatever it is bound to later. + db.prepare("(query [:find ?t :any-valid-time :where [$p :person/age _] [$p :db/tx-count ?t]])") + .expect("same slot"); + let err = db + .prepare( + "(query [:find ?t :any-valid-time :where [$p :person/age _] [$q :db/tx-count ?t]])", + ) + .expect_err("different slots"); + assert_eq!(err.code(), "PRS-081"); +} + +#[test] +fn valid_at_is_unchanged() { + let db = db(); + // `:db/valid-at` needs no source: the query's valid time, once per + // visible fact of the entity (name, age, friend). + let r = query(&db, "[:find ?v :where [:alice :db/valid-at ?v]]"); + assert_eq!(r.len(), 3, "one row per fact"); +} diff --git a/tests/temporal_metadata_test.rs b/tests/temporal_metadata_test.rs index d2124ec54a..2cc7747cb7 100644 --- a/tests/temporal_metadata_test.rs +++ b/tests/temporal_metadata_test.rs @@ -458,12 +458,20 @@ fn pseudo_attr_as_sole_pattern() { db.execute(r#"(transact {:valid-from "2022-01-01"} [[:alice :person/name "Alice"]])"#) .unwrap(); + // With no pattern before it, a pseudo-attribute has no fact to read + // (#594): PRS-081. + let err = db + .execute(r#"(query [:find ?vf :any-valid-time :where [:alice :db/valid-from ?vf]])"#) + .unwrap_err(); + assert_eq!(err.code(), "PRS-081"); + + // `[:alice ?a _]` reads every fact of the entity. let r = db .execute( r#" (query [:find ?vf :any-valid-time - :where [:alice :db/valid-from ?vf]]) + :where [:alice ?a _] [:alice :db/valid-from ?vf]]) "#, ) .unwrap();