From 1d3f5bc87e21833f96cfb7b674b84b91e747d92b Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 15 Oct 2026 08:40:10 +0530 Subject: [PATCH 1/3] docs: plan for plan-independent answers (#594, #596) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- .../2026-10-15-594-596-plan-independence.md | 218 ++++++++++++++++++ 1 file changed, 218 insertions(+) create mode 100644 docs/superpowers/plans/2026-10-15-594-596-plan-independence.md diff --git a/docs/superpowers/plans/2026-10-15-594-596-plan-independence.md b/docs/superpowers/plans/2026-10-15-594-596-plan-independence.md new file mode 100644 index 0000000000..ee3c64c7b1 --- /dev/null +++ b/docs/superpowers/plans/2026-10-15-594-596-plan-independence.md @@ -0,0 +1,218 @@ +# Plan-independent answers (#594, #596) — Plan + +Spec: `docs/superpowers/specs/2026-10-15-plan-independent-answers-design.md`. PRs target +`v3`. #594 and #596 close by hand (`gh issue close`) when their PR merges. No closing +keyword for #473. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–6: the `REORDER` switch, the differential test, expressions unify (#596) | `feat/596-unify` | +| 2 | 7–13: pseudo-attribute sources at parse time, PRS-081 (#594) | `feat/594-pseudo-sources` | +| 3 | 14–17: every build reorders; the `wasm` feature becomes a no-op | `feat/reorder-everywhere` | + +Each PR leaves `v3` with no unused code, and updates the test counts and `CHANGELOG.md` +for what it ships. Each has a docs-site PR (`../minigraf-docs`). + +## Where the native build differs from `wasm` today + +"`wasm`" here is the Cargo feature, not the target. No first-party build enables it: +`minigraf-wasm` depends on `minigraf` with `browser` only, and `wasm.yml` builds and tests +wasm32 without it, so the browser and WASI builds already reorder. Only builds that ask +for `--features wasm` themselves, and docs.rs (`all-features = true`), keep source order. + +Every place is a `#[cfg(not(feature = "wasm"))]` block or a cost choice: + +| Place | What it does natively | +|---|---| +| `optimizer::plan` | stable sort of patterns by `selectivity_score`; `not`/`not-join` sort by `clause_cost` before placement | +| `execute_query_on_executor`, `execute_query_with_rules` | deferred `not`/`not-join` sort by `clause_cost` | +| `evaluator.rs` (stratified loop, rules with negation) | `not` and `not-join` bodies sorted by `clause_cost` | +| `apply_or_clauses` (`or`, `or-join`) | branches sorted by `branch_cost`; the #250 short-circuits (plain `or` when it is a pure filter; `or-join` once every required key has a match) | +| `engine/plan.rs` | `HashJoin` build side by `branch_cost` (not `wasm`-gated: it runs under `wasm` too) | + +## Design decisions not fixed by the spec + +1. **The switch is a function, not a `cfg`.** `optimizer::reorder() -> bool` replaces each + `#[cfg(not(feature = "wasm"))]` above with `if optimizer::reorder()`. It is + `!cfg!(feature = "wasm")`, and, under `cfg(test)` or `test-oracle`, also the thread-local + `REORDER` (default on). Release builds get a constant, so the code they compile is + today's. `selectivity_score` loses its `cfg` and the `allow(dead_code)` attributes on + the cost functions go. +2. **The #250 short-circuits are under the switch too.** Spec §4.5 lists the sorts; the + short-circuits are also native-only, and an answer that depends on them is a bug by + spec §1, so the differential test should cover them. +3. **Switch off builds the `HashJoin` on the inner pattern.** "As under `wasm`" would keep + the cost choice, which `wasm` makes today; a fixed side gives the differential test a + second build side to compare. Only row order can differ. +4. **Test hook.** `minigraf::__reorder(on: bool) -> ReorderGuard`, `#[doc(hidden)]`, under + `test-oracle` only; the guard restores the previous value on drop, so a panicking test + leaves the thread as it found it. +5. **One unify helper.** `executor::bind_expr(b: &mut Binding, var: &str, v: Value, replace: + bool) -> bool`: unbound → insert, keep; bound → keep only if `normalize_join_value` + of both is equal, and insert `v` when `replace`. All four executor paths and the + evaluator call it (`apply_expr_clauses_in_evaluator` keeps its own loop but uses the + helper). `normalize_join_value` becomes `pub(crate)`. +6. **`Binders` records expressions in text order.** `Binders::new` also collects each + top-level `Expr` with a binding and its `:where` index; `by_var` becomes + `HashMap`. `Binders::expression(&mut self, clause: &WhereClause) -> bool` + takes the expression by value equality (`Expr: PartialEq`, as patterns are found + today), records its position when the variable is new or the expression is earlier + in the text than its binder, and returns whether it replaces (spec §3.5). Paths + without `Binders` (`or` branches, `not` bodies, rule bodies) pass `replace = false`. +7. **The engine's `Step::Bind` gets a mode.** `Bind(expr, vars, slot, Out)` with + `Out::New`, `Out::Check` or `Out::Replace`, fixed by the planner from `Slots` and + `Binders`. `Check`/`Replace` compare with `cell::join_eq(…, normalise = true)`, as the + executor normalises every bound variable. NaN never matches. +8. **The model-based and property reruns live in the test files.** `tests/reference_model` + is compiled by the `ops_sequence` fuzz target too, which has no `test-oracle` feature. PR 3 changes no binding: none enables `wasm`. + The driver takes the query runner as a parameter; `model_based_test.rs` and + `property_test.rs` pass one that, under `test-oracle`, also runs with the switch off + and requires the same bag. +9. **(PR 2) Bodies that read an outer source match seeded.** `not_body_matches` and + `evaluate_not_join` match substituted patterns from an empty seed and merge the outer + row afterwards. A pseudo-attribute pattern needs the hidden variable while it + matches, so when a body holds one, they seed with the outer row + (`match_patterns_seeded`). The `apply_not_clause`/`apply_not_join_clause` exclusion-set + fast paths and the `or` empty-seed fast path are skipped for such bodies (spec §4.1). + +10. **(PR 3) Reorder on every build; keep `wasm` as a no-op.** The feature was added in 6.1 + for small browser datasets and "deterministic, debuggable" order (`selectivity_score`'s + comment). The sort costs microseconds per query against a scan it can avoid, the + native order is deterministic too (stable sort, static scores), and after PRs 1–2 the + plan cannot change an answer. Removing the feature from `Cargo.toml` would break any + build that names it, so it stays declared, does nothing, and is marked deprecated + (CHANGELOG; removal is a v4 question). PR 3 waits for PR 2: before it, dropping the + gate changes answers for #594's shapes under `--features wasm`. + +## Steps + +### 1. The switch (PR 1) +- `optimizer::reorder`, `REORDER`, `ReorderGuard`, `minigraf::__reorder` (decisions 1, 4). +- Every place in the table above goes through `reorder()` (decisions 2, 3). +- Unit tests: `plan` keeps source order with the switch off; the switch is per thread. +- Clippy with `--features wasm` and for `wasm32` (no dead code, no unused `mut`). + +### 2. Differential test (PR 1) +- `tests/plan_independence_test.rs`, `#![cfg(all(feature = "test-oracle", not(target_arch = "wasm32")))]`. +- A helper runs one query through `Minigraf::execute` and `Minigraf::query` (cursor, + drained) with the switch on and off; all four answers must be the same bag (rows + sorted by a value key built without `Debug`). Under `test-oracle` the engine's oracle + also compares engine and executor on each run. +- The matrix: patterns in both text orders, three-way joins, cross products, + expressions (filter and binding), rule invocations (recursive and with `not`), + `or`/`or-join` (including the #250 pure-filter and covered-key shapes), `not`/`not-join` + (placed and deferred), keyword vs ref, `0.0`/`-0.0`, long strings, `:as-of` and + `:valid-at`; in-memory and file-backed after a checkpoint. +- #594 shapes (a per-fact pseudo-attribute with more than one candidate pattern, or none + before it) are left out, with a comment naming #594. +- A failure the matrix finds that is not #594 or #596 gets its own issue (v3.0.0). + +### 3. Expressions unify in the executor and evaluator (PR 1) +- `bind_expr` (decision 5) in: the two plan loops (`execute_query_on_executor`, + `execute_query_with_rules`, with `Binders::expression`, decision 6), + `apply_expr_clauses` (`evaluate_branch`, `not` bodies), `apply_expr_clauses_in_evaluator` + (`RecursiveEvaluator`, `evaluate_not_join`), and the stratified loop's `Expr` arm. +- `Binders::pattern`: an expression's position now counts like a pattern's (no more + `None` = "fixed"). +- Unit tests per path: keyword/ref pair (and which value is returned, both text orders), + `-0.0`/`0.0`, NaN, `1` vs `1.0`, `[(+ ?v 1) ?v]`, two expressions on one variable, a + failing expression. + +### 4. Expressions unify in the engine (PR 1) +- `Step::Bind` with `Out` (decision 7); planner picks the mode. Module doc of `plan.rs` + and `Step::Bind`'s doc no longer say "overwrites". +- `engine/tests.rs`: the same cases on the engine, plus the oracle agreeing. + +### 5. Reruns in the generated tests (PR 1) +- Decision 8: the #385 model-based test and the #386 query property tests. + +### 6. PR 1 checks and docs +- `CHANGELOG.md` (v3.0.0, Breaking changes): spec §6 rule 4, with #596's example. +- `cargo fmt`; clippy native, `--features wasm`, `browser`/wasm32; + `cargo test`; `cargo test --features test-oracle`; `cargo test --features wasm`. +- Fuzz crate builds (`cargo check` in `fuzz/`), since `reference_model` changed. +- Test counts: `CLAUDE.md`, `docs/TEST_COVERAGE.md`, `README.md`; `CLAUDE.md` module list + (`optimizer.rs` switch; engine `filter.rs` `Bind`). +- Docs site: `content/datalog-reference.md` expression clauses, `@since v3.0.0` / + `@until v3.0.0`. +- Codex review; comment on #596; close #596 by hand after merge. + +### 7. Hidden variables on `Pattern` (PR 2) +- `Pattern::meta: Vec<(PseudoAttr, String)>`, `Pattern::pseudo_source: Option`, + empty from every constructor. `prepared::substitute`, `substitute_pattern` and + magic-sets copy them unchanged (check every struct literal of `Pattern`). + +### 8. `resolve_pseudo_sources` and PRS-081 (PR 2) +- `parser.rs`: the pass of spec §4.1 over `:where`, rule bodies and prepared templates, + with the enclosing-list stack and the §3.2 crossing rule; appends hidden variables to + `not-join`/`or-join` join variables it crosses. Runs before `check_not_safety`. Entity + terms compare as spec §2 (`edn_to_entity_id` for constants, slot names for `$slot`). +- `ErrorCode::Prs081` in `src/error.rs` (category, message, registry list) and + `docs/ERROR_REFERENCE.md` (table row and section). +- Parser tests: spec §7 PR 2 list. + +### 9. Executor (PR 2) +- `matcher.rs`: a source binds its `meta` variables on both join paths (hash and nested + loop) and in `match_pattern`; a `pseudo_source` pattern is a bind-or-compare on the + row, never a scan. The `__fvf_`/`__fvt_`/`__ftc_`/`__fti_` keys and their fast path and + fallback go; so do the `__f` retains in `apply_not_clause`/`apply_not_join_clause`. +- `optimizer::plan`: pseudo-attribute patterns are placed like expressions (spec §4.2); + a `not` whose body reads a hidden variable waits for its source. +- Decision 9 for `not`/`not-join` bodies and `or` branches. + +### 10. Engine (PR 2) +- `plan.rs`: a source's scan or join fills one metadata column per `meta` entry, the + hidden variable's slot. `Step::Pseudo { slot, value }` binds or compares. `pseudo_forms`, + the per-row `pick` and the `[e _ _]` form for per-fact attributes go; `:db/valid-at` + keeps its `[e _ _]` join. Module doc and `CLAUDE.md` module list updated. + +### 11. Tests (PR 2) +- Spec §7 PR 2 list; the pseudo-attribute shapes join the differential matrix. +- Existing tests that relied on the fallback or plan order (`temporal_metadata_test.rs`, + `point_query_history_test.rs`, `statement_order_test.rs`, `error_codes_prs_test.rs`, + the matcher, executor, parser, `db.rs` and engine unit tests; spec §7 names + `bitemporal_test.rs` and `join_rules_test.rs`, which hold no per-fact pseudo-attribute): + each change listed in the PR body. +- `cargo test --features wasm` runs #594's examples without reordering. + +### 12. Measurement (PR 2) +- #394 envelope on the bench machine, idle: `join_2_pseudo` at 1M no slower than after + #545 PR 3 (56 µs at 10M); point queries unchanged. Binary size (`binary-size.yml`). + +### 13. PR 2 checks and docs +- As step 6, plus `CHANGELOG.md` spec §6 rules 1–3 and PRS-081. +- Docs site: `content/datalog-reference.md` pseudo-attributes (`@since`/`@until v3.0.0`), + `content/architecture.md` query-engine section. +- Codex review; close #594 by hand after merge; next is #546. + +### 14. Remove the gate (PR 3, decision 10) +- `optimizer::reorder()` is `true`, or the thread-local `REORDER` under `cfg(test)` / + `test-oracle`. Every `cfg(feature = "wasm")` / `cfg_attr(feature = "wasm", …)` in + `src/query/` goes. `wasm = []` stays in `Cargo.toml` with a comment saying it is a no-op. +- The `#[cfg(not(feature = "wasm"))]` optimizer unit tests lose the gate; tests that + checked source order under `wasm` set the switch off instead. + +### 15. Tests (PR 3) +- The differential test stays the only source-order path and must still pass. +- The plan-dependent shapes from PRs 1–2 pass natively, on wasm32 (`wasm.yml`, WASI), and + with `--features wasm` (now the same plan). + +### 16. Measurement (PR 3) +- #394 envelope at 100K and 1M with `--features wasm`, before and after: no slower on any + shape (expect the multi-pattern shapes to gain). Binary size for `browser`/wasm32 + (`binary-size.yml`). + +### 17. PR 3 checks and docs +- `CHANGELOG.md` (v3.0.0): the `wasm` feature no longer changes query planning; + deprecated. +- `CLAUDE.md` module list (`optimizer.rs`: "disabled under `wasm` feature" goes), + `README.md` and the docs site (`content/architecture.md` optimizer section, + `content/use-cases.md` browser notes) under `@since v3.0.0` / `@until v3.0.0`. +- The 6.1 and 2026-05-15 optimizer specs stay as they are (frozen records). +- Codex review. + +## Bindings + +PRS-081 is a new code but bindings surface codes as strings (as PRS-080 did), and no +public API changes, so no binding cascade. `minigraf::__reorder` exists only under the +`test-oracle` feature. PR 3 changes no binding: none enables `wasm`. From b0925f9301dc8b23ba2e2b8f7fc32b4e52bb8f6a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 15 Oct 2026 08:52:10 +0530 Subject: [PATCH 2/3] feat(query): test-only switch to turn clause reordering off (#596) optimizer::reorder() replaces every cfg(not(feature = "wasm")) reordering site: pattern selectivity sort, not/not-join cost sorts, or/or-join branch sorts and their #250 short-circuits, and the engine's HashJoin build side (off: build on the inner pattern). Release builds compile a constant. Under cfg(test) or test-oracle a thread-local switch turns it off; minigraf::__reorder exposes it to integration tests (test-oracle only). Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/lib.rs | 14 ++++ src/query/datalog/evaluator.rs | 27 ++++---- src/query/datalog/executor.rs | 70 ++++++++++--------- src/query/datalog/optimizer.rs | 121 ++++++++++++++++++++++++++------- src/query/engine/plan.rs | 6 +- 5 files changed, 164 insertions(+), 74 deletions(-) diff --git a/src/lib.rs b/src/lib.rs index 2075af39e5..cbb4ebef02 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -120,3 +120,17 @@ pub use query::datalog::types::{AsOf, ValidAt}; // Prepared statements pub use query::datalog::prepared::{BindValue, PreparedQuery}; + +// Plan-independence tests (#596): run queries without reordering. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub use query::datalog::optimizer::ReorderGuard; + +/// Turns clause reordering on or off for queries on this thread until the +/// returned guard drops. Only for tests that check no answer depends on the +/// plan (#596); built with the `test-oracle` feature only. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub fn __reorder(on: bool) -> ReorderGuard { + query::datalog::optimizer::set_reorder(on) +} diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 13db500611..355dfa5062 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -798,7 +798,6 @@ impl StratifiedEvaluator { } } - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut not_clauses: Vec> = rule .body .iter() @@ -808,7 +807,6 @@ impl StratifiedEvaluator { }) .collect(); - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut not_join_clauses: Vec<(Vec, Vec)> = rule .body .iter() @@ -821,18 +819,19 @@ impl StratifiedEvaluator { .collect(); // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(|body| { - crate::query::datalog::optimizer::clause_cost(&WhereClause::Not(body.clone())) - }); - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_join_clauses.sort_by_key(|(vars, clauses)| { - crate::query::datalog::optimizer::clause_cost(&WhereClause::NotJoin { - join_vars: vars.clone(), - clauses: clauses.clone(), - }) - }); + if crate::query::datalog::optimizer::reorder() { + not_clauses.sort_by_key(|body| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::Not( + body.clone(), + )) + }); + not_join_clauses.sort_by_key(|(vars, clauses)| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::NotJoin { + join_vars: vars.clone(), + clauses: clauses.clone(), + }) + }); + } // Compute once; reuse for plan loop, apply_or_clauses, not-body matching. let accumulated_facts: Arc<[Fact]> = Arc::from(accumulated.get_asserted_facts()?); diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index ff79c5e9c7..21737b275c 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -742,10 +742,10 @@ impl DatalogExecutor { // Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their // variables are only bound by the Or/OrJoin pass above, so they must run here, // after it. Sorted cheapest-first, same as the pre-#248 post-filter ordering. - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut deferred_not_clauses = deferred_not_clauses; - #[cfg(not(feature = "wasm"))] - deferred_not_clauses.sort_by_key(optimizer::clause_cost); + if optimizer::reorder() { + deferred_not_clauses.sort_by_key(optimizer::clause_cost); + } for clause in deferred_not_clauses { bindings = match clause { WhereClause::Not(body) => apply_not_clause( @@ -1004,10 +1004,10 @@ impl DatalogExecutor { // variables are only bound by the Or/OrJoin pass above. (The StratifiedEvaluator // handles `not`/`not-join` in rule bodies; this handles them appearing directly // in the query body alongside rule invocations.) - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut deferred_not_clauses = deferred_not_clauses; - #[cfg(not(feature = "wasm"))] - deferred_not_clauses.sort_by_key(optimizer::clause_cost); + if optimizer::reorder() { + deferred_not_clauses.sort_by_key(optimizer::clause_cost); + } for clause in deferred_not_clauses { bindings = match clause { WhereClause::Not(body) => apply_not_clause_derived( @@ -2054,13 +2054,13 @@ pub(crate) fn apply_or_clauses( match clause { WhereClause::Or(branches) => { let sorted_or_branches: Vec<&Vec> = { - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut b: Vec<&Vec> = branches.iter().collect(); // Sort branches by cost ascending so cheaper branches evaluate first, // maximizing the chance the short-circuit below fires early (#250). // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - b.sort_by_key(|br| optimizer::branch_cost(br)); + if optimizer::reorder() { + b.sort_by_key(|br| optimizer::branch_cost(br)); + } b }; // If any branch contains Not/NotJoin clauses (which need bound variables @@ -2112,12 +2112,16 @@ pub(crate) fn apply_or_clauses( // Variable names already bound in the incoming scope — used below to detect // whether a branch introduces a *new* variable (#250 short-circuit gating). - #[cfg(not(feature = "wasm"))] - let incoming_var_names: std::collections::HashSet = bindings - .iter() - .flat_map(|b| b.keys().cloned()) - .filter(|k| !k.starts_with("__")) - .collect(); + let reorder = optimizer::reorder(); + let incoming_var_names: std::collections::HashSet = if reorder { + bindings + .iter() + .flat_map(|b| b.keys().cloned()) + .filter(|k| !k.starts_with("__")) + .collect() + } else { + Default::default() + }; for branch in &sorted_or_branches { let branch_result = evaluate_branch( @@ -2151,8 +2155,7 @@ pub(crate) fn apply_or_clauses( // scope — i.e. this `or` is a pure filter (all branches bind the same // new-var set per the parser's or-safety check), so any further match on // an already-covered key would just re-derive an identical row. - #[cfg(not(feature = "wasm"))] - { + if reorder { let branch_var_names: std::collections::HashSet<&str> = union_bindings .iter() .flat_map(|bb| bb.keys().map(|k| k.as_str())) @@ -2275,13 +2278,13 @@ pub(crate) fn apply_or_clauses( continue; } let sorted_oj_branches: Vec<&Vec> = { - #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut b: Vec<&Vec> = branches.iter().collect(); // Sort branches by cost ascending so cheaper branches evaluate first, // maximizing the chance the short-circuit below fires early (#250). // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - b.sort_by_key(|br| optimizer::branch_cost(br)); + if optimizer::reorder() { + b.sort_by_key(|br| optimizer::branch_cost(br)); + } b }; let outer_keys: std::collections::HashSet = @@ -2309,16 +2312,20 @@ pub(crate) fn apply_or_clauses( // only add a row identical to one already merged, which the dedup below // would drop anyway — unlike plain `or`, this holds regardless of what the // branch itself binds internally. - #[cfg(not(feature = "wasm"))] - let required_keys: std::collections::HashSet> = bindings - .iter() - .map(|incoming| { - join_vars - .iter() - .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) - .collect::>() - }) - .collect(); + let reorder = optimizer::reorder(); + let required_keys: std::collections::HashSet> = if reorder { + bindings + .iter() + .map(|incoming| { + join_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect::>() + }) + .collect() + } else { + Default::default() + }; for branch in &sorted_oj_branches { let branch_result = evaluate_branch( @@ -2348,8 +2355,7 @@ pub(crate) fn apply_or_clauses( } } - #[cfg(not(feature = "wasm"))] - if required_keys.iter().all(|k| branch_map.contains_key(k)) { + if reorder && required_keys.iter().all(|k| branch_map.contains_key(k)) { break; } } diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index 2c1ade8d95..62ca694dc4 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -2,9 +2,50 @@ //! //! `plan()` is the single entry point. It assigns an `IndexHint` to each //! pattern and (outside the `wasm` feature) sorts patterns by selectivity. +//! +//! [`reorder`] says whether this build reorders: patterns, `not`/`not-join` +//! clauses and `or` branches by cost, the `or` short-circuits (#250), and the +//! engine's `HashJoin` build side. Tests turn it off per thread to check that +//! no answer depends on the plan (#596). use crate::query::datalog::types::{AttributeSpec, EdnValue, Expr, Pattern, WhereClause}; +#[cfg(any(test, feature = "test-oracle"))] +thread_local! { + /// Whether queries on this thread reorder; tests only. + static REORDER: std::cell::Cell = const { std::cell::Cell::new(true) }; +} + +/// Whether queries reorder clauses by cost: never under the `wasm` feature, +/// and, in tests, only while this thread's switch is on ([`set_reorder`]). +#[inline] +pub(crate) fn reorder() -> bool { + #[cfg(any(test, feature = "test-oracle"))] + if !REORDER.with(std::cell::Cell::get) { + return false; + } + !cfg!(feature = "wasm") +} + +/// Turns reordering on or off for queries on this thread until the guard +/// drops, which restores the previous setting. +#[cfg(any(test, feature = "test-oracle"))] +pub(crate) fn set_reorder(on: bool) -> ReorderGuard { + ReorderGuard(REORDER.with(|r| r.replace(on))) +} + +/// Restores the previous [`set_reorder`] setting on drop. +#[cfg(any(test, feature = "test-oracle"))] +#[must_use = "reordering is restored when the guard drops"] +pub struct ReorderGuard(bool); + +#[cfg(any(test, feature = "test-oracle"))] +impl Drop for ReorderGuard { + fn drop(&mut self) { + REORDER.with(|r| r.set(self.0)); + } +} + /// Which covering index to use for a given pattern. #[derive(Debug, Clone, PartialEq, Eq)] pub enum IndexHint { @@ -40,10 +81,10 @@ fn attr_is_index_bound(a: &AttributeSpec) -> bool { /// Count the number of non-variable components in a pattern. /// Higher score = more selective. /// -/// Gated on non-wasm: WASM/browser targets typically work with small datasets where -/// the overhead of computing scores and sorting can equal or exceed the benefit. -/// Source order is preserved on WASM for deterministic, debuggable query behaviour. -#[cfg(not(feature = "wasm"))] +/// Not used under the `wasm` feature ([`reorder`]): WASM/browser targets typically +/// work with small datasets where the overhead of computing scores and sorting can +/// equal or exceed the benefit. Source order is preserved there for deterministic, +/// debuggable query behaviour. fn selectivity_score(p: &Pattern) -> u8 { let e = !is_variable(&p.entity); let a = attr_is_index_bound(&p.attribute); @@ -188,17 +229,18 @@ pub fn plan( } } - // Stable sort patterns by selectivity descending (non-wasm only). + // Stable sort patterns by selectivity descending (when reordering). // Preserves original order for ties, ensuring deterministic output. // WASM omission: see selectivity_score() — small datasets, determinism. - #[cfg(not(feature = "wasm"))] - patterns.sort_by_key(|(clause, _)| { - if let WhereClause::Pattern(p) = clause { - std::cmp::Reverse(selectivity_score(p)) - } else { - std::cmp::Reverse(0u8) - } - }); + if reorder() { + patterns.sort_by_key(|(clause, _)| { + if let WhereClause::Pattern(p) = clause { + std::cmp::Reverse(selectivity_score(p)) + } else { + std::cmp::Reverse(0u8) + } + }); + } // Start with sorted patterns only. let mut result: Vec<(WhereClause, Option)> = patterns @@ -239,8 +281,9 @@ pub fn plan( // processing in descending cost order lands the cheapest clause at `pos` last — // i.e. final relative order at any shared insertion point comes out ascending // (cheapest first), mirroring the executor's previous post-filter ordering. - #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(|c| std::cmp::Reverse(clause_cost(c))); + if reorder() { + not_clauses.sort_by_key(|c| std::cmp::Reverse(clause_cost(c))); + } let mut deferred: Vec = Vec::new(); for nc in not_clauses { @@ -295,9 +338,7 @@ pub fn plan( /// Static 4-tier cardinality estimate for a single pattern. /// /// Derived from selectivity_score but returns u64 cost (lower = cheaper) rather -/// than a selectivity score. Available on all targets; on WASM the dead_code lint -/// is suppressed because the sorting call-sites are omitted there. -#[cfg_attr(feature = "wasm", allow(dead_code))] +/// than a selectivity score. fn pattern_cost(p: &Pattern) -> u64 { let e = !is_variable(&p.entity); let a = attr_is_index_bound(&p.attribute); @@ -316,10 +357,6 @@ fn pattern_cost(p: &Pattern) -> u64 { /// /// Rationale for `min`: In a multi-pattern join the most selective pattern dominates — /// the join cannot produce more rows than the smallest input. -/// -/// Available on all targets; on WASM the dead_code lint is suppressed because -/// the sorting call-sites are omitted there. -#[cfg_attr(feature = "wasm", allow(dead_code))] pub fn branch_cost(branch: &[WhereClause]) -> u64 { branch .iter() @@ -345,10 +382,6 @@ pub fn branch_cost(branch: &[WhereClause]) -> u64 { /// | `Or(branches)` | sum of `branch_cost` per branch | /// | `OrJoin{branches}` | sum of `branch_cost` per branch | /// | other | `u64::MAX` (defensive; not expected in practice) | -/// -/// Available on all targets; on WASM the dead_code lint is suppressed because -/// the sorting call-sites are omitted there. -#[cfg_attr(feature = "wasm", allow(dead_code))] pub fn clause_cost(clause: &WhereClause) -> u64 { match clause { WhereClause::Pattern(p) => pattern_cost(p), @@ -459,6 +492,42 @@ mod tests { ); } + #[test] + fn test_reorder_off_keeps_source_order() { + let p1 = make_pattern(var("e"), kw(":age"), var("a")); + let p2 = make_pattern(entity_lit(), kw(":name"), var("v")); + let _off = set_reorder(false); + assert!(!reorder()); + let (planned, _deferred) = plan(vec![ + WhereClause::Pattern(p1.clone()), + WhereClause::Pattern(p2.clone()), + ]); + let order: Vec<&Pattern> = planned + .iter() + .filter_map(|(c, _)| match c { + WhereClause::Pattern(p) => Some(p), + _ => None, + }) + .collect(); + assert!(order == vec![&p1, &p2], "source order kept"); + } + + #[test] + fn test_reorder_switch_is_per_thread_and_restored() { + { + let _off = set_reorder(false); + assert!(!reorder()); + let other = std::thread::spawn(reorder).join().unwrap(); + assert_eq!(other, !cfg!(feature = "wasm"), "other thread unaffected"); + { + let _on = set_reorder(true); + assert_eq!(reorder(), !cfg!(feature = "wasm")); + } + assert!(!reorder(), "inner guard restores off"); + } + assert_eq!(reorder(), !cfg!(feature = "wasm"), "restored on drop"); + } + // ── expr_vars() ────────────────────────────────────────────────────────── #[test] diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 8e8b8b554e..71db3aaf1b 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -314,8 +314,10 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { metas.push((m, slots.add(OTHER))); } if let JoinKind::Hash { build_inner } = &mut join.kind { - *build_inner = optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) - <= optimizer::branch_cost(&outer_patterns); + // Off: always the inner pattern (decision 3 of the #596 plan). + *build_inner = !optimizer::reorder() + || optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) + <= optimizer::branch_cost(&outer_patterns); } steps.push(Step::Join(join)); } From bed7e36e0f6990373640543986323084f3bccacc Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 15 Oct 2026 09:42:59 +0530 Subject: [PATCH 3/3] fix(query): an expression binding a bound variable unifies (#596) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit [(f …) ?x] used to overwrite ?x wherever the planner ran it, so when a pattern also bound ?x the answer depended on the plan (native vs the wasm feature). It now keeps only the rows where its result equals ?x's value, with the join equality of #545 (IEEE == floats, keyword equals the ref of the entity it names, int never equals float, NaN equals nothing), in the executor's plan loops, or branches, not bodies, the evaluator and the engine's Step::Bind (Out::New/Check/Replace). Binders records expressions by text position: the first binder in :where gives the value. tests/plan_independence_test.rs (test-oracle) runs a query matrix with reordering on and off through execute and a cursor; the model-based and property tests rerun every query with reordering off. Gates the #250 short-circuit tests to non-wasm (they already failed under --features wasm). 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/TEST_COVERAGE.md | 5 +- src/query/datalog/evaluator.rs | 35 +--- src/query/datalog/executor.rs | 252 ++++++++++++++++++++++------- src/query/datalog/matcher.rs | 2 +- src/query/datalog/optimizer.rs | 8 +- src/query/engine/filter.rs | 26 ++- src/query/engine/plan.rs | 43 +++-- src/query/engine/tests.rs | 58 +++++++ tests/disjunction_test.rs | 6 + tests/join_rules_test.rs | 19 ++- tests/model_based_test.rs | 14 +- tests/plan_independence_test.rs | 278 ++++++++++++++++++++++++++++++++ tests/property_test.rs | 13 ++ tests/reference_model/mod.rs | 27 +++- 17 files changed, 677 insertions(+), 121 deletions(-) create mode 100644 tests/plan_independence_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 4188a770f1..85418434bf 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -22,7 +22,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **An unknown aggregate or window function is an error whatever the data** (#414). Aggregate and window function names in `:find` are now resolved before the query runs: an unknown aggregate fails with the new `QRY-010` and an unknown window function with the new `QRY-011`, even on an empty database or when no row matches. Before, such a query returned no results until a row matched and then failed with `INT-029`/`INT-030`, which stay registered for internal inconsistencies only. - **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one `transact` is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both. - **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`. An expression that binds a variable still sets its value where it runs, and later patterns keep that value. The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged. +- **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. ### Added @@ -75,6 +76,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. +- **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 31fe6a0f9c..a6ac87981e 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -135,11 +135,11 @@ cargo run < demos/demo_negation.txt - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection - `rules.rs`: `RuleRegistry` — thread-safe rule management - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper - - `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature + - `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature. `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596) - `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), `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 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. 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 -**1507 tests** (1497 passing, 10 ignored; unit + integration + doc). +**1514 tests** (1504 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 215f6c0487..bd8b518c71 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 1507 tests +cargo test # run 1514 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 6dfdc04a6b..ea90528d61 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,497 passing tests and 10 ignored tests (1,507 total) +**Result**: 1,504 passing tests and 10 ignored tests (1,514 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). @@ -15,7 +15,8 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling (including a B+tree node that points back up, which fails a scan with `INT-049` instead of looping; #597), and fault injection. - **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 is kept by a later join, and 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. +- **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. +- **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/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 355dfa5062..00b2b79230 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -569,31 +569,20 @@ pub fn evaluate_not_join( /// Apply WhereClause::Expr clauses to a list of bindings. /// /// Filter-form (`binding: None`) drops rows where the expr is not truthy or errors. -/// Binding-form (`binding: Some(var)`) extends the row with the computed value. +/// Binding-form (`binding: Some(var)`) extends the row with the computed value, +/// or keeps it only if an existing value of the variable is equal (#596). fn apply_expr_clauses_in_evaluator( bindings: Vec, expr_clauses: &[&WhereClause], registry: &FunctionRegistry, ) -> Vec { - use crate::query::datalog::executor::{eval_expr, is_truthy}; + use crate::query::datalog::executor::apply_expr; bindings .into_iter() .filter_map(|mut b| { for clause in expr_clauses { if let WhereClause::Expr { expr, binding: out } = clause { - match eval_expr(expr, &b, Some(registry)) { - Ok(value) => match out { - None => { - if !is_truthy(&value) { - return None; - } - } - Some(var) => { - b.insert(var.clone(), value); - } - }, - Err(_) => return None, - } + b = apply_expr(expr, out.as_deref(), b, registry, false)?; } } Some(b) @@ -862,21 +851,11 @@ impl StratifiedEvaluator { ); } WhereClause::Expr { expr, binding: out } => { - use crate::query::datalog::executor::{eval_expr, is_truthy}; + use crate::query::datalog::executor::apply_expr; candidates = candidates .into_iter() - .filter_map(|mut b| match eval_expr(&expr, &b, Some(&fn_guard)) { - Ok(v) => { - if let Some(var) = &out { - b.insert(var.clone(), v); - Some(b) - } else if is_truthy(&v) { - Some(b) - } else { - None - } - } - Err(_) => None, + .filter_map(|b| { + apply_expr(&expr, out.as_deref(), b, &fn_guard, false) }) .collect(); } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 21737b275c..eed1ec5266 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -680,24 +680,12 @@ impl DatalogExecutor { ); } WhereClause::Expr { expr, binding: out } => { - if let Some(var) = &out { - binders.expression(var); - } + let replace = out + .as_deref() + .is_some_and(|var| binders.expression(&expr, var)); bindings = bindings .into_iter() - .filter_map(|mut b| match eval_expr(&expr, &b, Some(®istry)) { - Ok(v) => { - if let Some(var) = &out { - b.insert(var.clone(), v); - Some(b) - } else if is_truthy(&v) { - Some(b) - } else { - None - } - } - Err(_) => None, - }) + .filter_map(|b| apply_expr(&expr, out.as_deref(), b, ®istry, replace)) .collect(); } WhereClause::Not(body) => { @@ -942,24 +930,12 @@ impl DatalogExecutor { ); } WhereClause::Expr { expr, binding: out } => { - if let Some(var) = &out { - binders.expression(var); - } + let replace = out + .as_deref() + .is_some_and(|var| binders.expression(&expr, var)); bindings = bindings .into_iter() - .filter_map(|mut b| match eval_expr(&expr, &b, Some(®istry)) { - Ok(v) => { - if let Some(var) = &out { - b.insert(var.clone(), v); - Some(b) - } else if is_truthy(&v) { - Some(b) - } else { - None - } - } - Err(_) => None, - }) + .filter_map(|b| apply_expr(&expr, out.as_deref(), b, ®istry, replace)) .collect(); } WhereClause::Not(body) => { @@ -1491,16 +1467,18 @@ type Binding = std::collections::HashMap; /// A variable that several patterns bind takes its value from the first of /// them in the query text, whatever order the planner runs them in: a /// keyword and the ref of the entity it names are equal in a join, but are -/// returned as they were bound. An expression binding overwrites the value -/// where the planner places it, and later patterns keep it. A -/// pseudo-attribute pattern never replaces a value. +/// returned as they were bound. An expression binding is a binder like a +/// pattern: when the variable is already bound it keeps the rows where its +/// result is equal (#596), and gives the value when it is first in the text. +/// A pseudo-attribute pattern never replaces a value. pub(crate) struct Binders { /// Each top-level pattern (rule calls as patterns) and its position in /// `:where`; taken as the planner hands them out. text: Vec<(Pattern, usize)>, - /// The position of the pattern each variable's value came from; `None` - /// once an expression has bound it. - by_var: HashMap>, + /// Each top-level binding expression, its variable and its position. + exprs: Vec<(Expr, String, usize)>, + /// The position of the clause each variable's value came from. + by_var: HashMap, } impl Binders { @@ -1514,8 +1492,20 @@ impl Binders { }) .collect(); text.extend(rule_patterns); + let exprs = where_clauses + .iter() + .enumerate() + .filter_map(|(i, c)| match c { + WhereClause::Expr { + expr, + binding: Some(var), + } => Some((expr.clone(), var.clone(), i)), + _ => None, + }) + .collect(); Binders { text, + exprs, by_var: HashMap::new(), } } @@ -1543,10 +1533,10 @@ impl Binders { } match self.by_var.get(v) { None => { - self.by_var.insert(v.clone(), Some(at)); + self.by_var.insert(v.clone(), at); } - Some(Some(b)) if real && at < *b => { - self.by_var.insert(v.clone(), Some(at)); + Some(b) if real && at < *b => { + self.by_var.insert(v.clone(), at); if !rebind.contains(v) { rebind.push(v.clone()); } @@ -1557,9 +1547,29 @@ impl Binders { rebind } - /// Record an expression binding `var`. - pub(crate) fn expression(&mut self, var: &str) { - self.by_var.insert(var.to_string(), None); + /// Record the expression `expr` binding `var`, run next, and return + /// whether its value replaces the one a clause already gave `var`: when + /// that clause is later in the text. + pub(crate) fn expression(&mut self, expr: &Expr, var: &str) -> bool { + let at = match self + .exprs + .iter() + .position(|(e, v, _)| e == expr && v == var) + { + Some(i) => self.exprs.swap_remove(i).2, + None => usize::MAX, + }; + match self.by_var.get(var) { + None => { + self.by_var.insert(var.to_string(), at); + false + } + Some(b) if at < *b => { + self.by_var.insert(var.to_string(), at); + true + } + Some(_) => false, + } } } @@ -2606,7 +2616,8 @@ pub(crate) fn eval_expr( /// Apply all WhereClause::Expr clauses from `where_clauses` to `bindings`. /// /// Filter-form (`binding: None`) drops the row if the expr is not truthy or errors. -/// Binding-form (`binding: Some(var)`) extends the row with the computed value. +/// Binding-form (`binding: Some(var)`) extends the row with the computed value, +/// or keeps it only if an existing value of the variable is equal (#596). /// Type mismatches and errors silently drop the row. /// /// Pre-validates UDF predicate names: returns `Err` if a named UDF predicate is not @@ -2632,25 +2643,47 @@ pub(crate) fn apply_expr_clauses( if let WhereClause::Expr { expr, binding: out } = clause { bindings = bindings .into_iter() - .filter_map(|mut b| match eval_expr(expr, &b, Some(registry)) { - Ok(v) => { - if let Some(var) = out { - b.insert(var.clone(), v); - Some(b) - } else if is_truthy(&v) { - Some(b) - } else { - None - } - } - Err(()) => None, - }) + .filter_map(|b| apply_expr(expr, out.as_deref(), b, registry, false)) .collect(); } } Ok(bindings) } +/// One expression clause over the row `b`: `None` drops the row. +/// +/// A filter (`out` is `None`) keeps the row when the result is truthy. A +/// binding keeps it with `out` bound to the result, or, when `b` already binds +/// `out`, only if the two are equal as a join compares them (#596): floats by +/// IEEE `==`, a keyword equal to a ref to the entity it names, an integer +/// never equal to a float. `replace` then takes the result as the value +/// (`Binders::expression`). A failing expression drops the row. +pub(crate) fn apply_expr( + expr: &Expr, + out: Option<&str>, + mut b: Binding, + registry: &FunctionRegistry, + replace: bool, +) -> Option { + let v = eval_expr(expr, &b, Some(registry)).ok()?; + let Some(var) = out else { + return is_truthy(&v).then_some(b); + }; + match b.get(var) { + Some(old) + if PatternMatcher::normalize_join_value(old) + != PatternMatcher::normalize_join_value(&v) => + { + None + } + Some(_) if !replace => Some(b), + _ => { + b.insert(var.to_string(), v); + Some(b) + } + } +} + #[cfg(test)] mod tests { use super::*; @@ -4597,6 +4630,109 @@ mod expr_eval_tests { assert_eq!(result[0].get("?v"), Some(&Value::Integer(50))); } + /// `apply_expr` of a literal bound to `?x` over a row binding `?x` to + /// `old`: whether the row is kept, and `?x` afterwards. + fn unify(old: Value, new: Value, replace: bool) -> Option { + let row = apply_expr( + &Expr::Lit(new), + Some("?x"), + b(&[("?x", old)]), + &FunctionRegistry::with_builtins(), + replace, + )?; + row.get("?x").cloned() + } + + #[test] + fn test_apply_expr_unifies_a_bound_variable() { + // #596: equal keeps the row, different drops it. + assert_eq!( + unify(Value::Integer(41), Value::Integer(41), false), + Some(Value::Integer(41)) + ); + assert!(unify(Value::Integer(41), Value::Integer(31), false).is_none()); + assert!(unify(Value::Integer(41), Value::Integer(31), true).is_none()); + // An integer never equals a float; NaN equals nothing. + assert!(unify(Value::Integer(1), Value::Float(1.0), false).is_none()); + assert!(unify(Value::Float(f64::NAN), Value::Float(f64::NAN), false).is_none()); + // IEEE `==`: -0.0 equals 0.0; the old value stays unless `replace`. + assert!(matches!( + unify(Value::Float(-0.0), Value::Float(0.0), false), + Some(Value::Float(f)) if f.is_sign_negative() + )); + assert!(matches!( + unify(Value::Float(-0.0), Value::Float(0.0), true), + Some(Value::Float(f)) if f.is_sign_positive() + )); + } + + #[test] + fn test_apply_expr_unifies_keyword_with_ref() { + let bob = crate::query::datalog::matcher::edn_to_entity_id(&EdnValue::Keyword( + ":bob".to_string(), + )) + .unwrap(); + let kw = || Value::Keyword(":bob".to_string()); + assert!(matches!( + unify(Value::Ref(bob), kw(), false), + Some(Value::Ref(_)) + )); + assert!(matches!( + unify(Value::Ref(bob), kw(), true), + Some(Value::Keyword(_)) + )); + assert!(matches!( + unify(kw(), Value::Ref(bob), false), + Some(Value::Keyword(_)) + )); + assert!(unify(Value::Keyword(":carol".to_string()), Value::Ref(bob), false).is_none()); + } + + #[test] + fn test_apply_expr_failure_drops_row() { + let div = Expr::BinOp( + BinOp::Div, + Box::new(Expr::Lit(Value::Integer(1))), + Box::new(Expr::Lit(Value::Integer(0))), + ); + let row = apply_expr( + &div, + Some("?x"), + b(&[]), + &FunctionRegistry::with_builtins(), + false, + ); + assert!(row.is_none()); + } + + #[test] + fn test_binders_expression_replaces_only_when_earlier_in_text() { + use crate::query::datalog::types::WhereClause; + let expr = Expr::Lit(Value::Integer(1)); + let bind = WhereClause::Expr { + expr: expr.clone(), + binding: Some("?x".to_string()), + }; + let pat = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":score".to_string()), + EdnValue::Symbol("?x".to_string()), + ); + // The expression is first in the text and runs after the pattern. + let mut binders = Binders::new(&[bind.clone(), WhereClause::Pattern(pat.clone())], vec![]); + assert!(binders.pattern(&pat).is_empty()); + assert!(binders.expression(&expr, "?x"), "earlier in the text"); + // The pattern is first in the text: the expression only checks. + let mut binders = Binders::new(&[WhereClause::Pattern(pat.clone()), bind.clone()], vec![]); + assert!(binders.pattern(&pat).is_empty()); + assert!(!binders.expression(&expr, "?x"), "later in the text"); + // An expression that runs first binds; a later-run, text-earlier + // pattern then gives the value. + let mut binders = Binders::new(&[WhereClause::Pattern(pat.clone()), bind], vec![]); + assert!(!binders.expression(&expr, "?x")); + assert_eq!(binders.pattern(&pat), vec!["?x".to_string()]); + } + #[test] fn test_apply_expr_binding_extends_row() { // [(+ ?a ?b) ?sum] — binds ?sum diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index d8f1f58921..703673bb13 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -475,7 +475,7 @@ impl PatternMatcher { /// to the same key. Used only for key comparison — does NOT affect what is /// stored in merged output bindings (the original `val` is always inserted into /// the result binding, never the normalized form). - fn normalize_join_value(val: &Value) -> Value { + pub(crate) fn normalize_join_value(val: &Value) -> Value { if let Value::Keyword(k) = val && let Ok(uuid) = edn_to_entity_id(&EdnValue::Keyword(k.clone())) { diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index 62ca694dc4..be2180504f 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -517,8 +517,12 @@ mod tests { { let _off = set_reorder(false); assert!(!reorder()); - let other = std::thread::spawn(reorder).join().unwrap(); - assert_eq!(other, !cfg!(feature = "wasm"), "other thread unaffected"); + // wasm32 test runners have no threads. + #[cfg(not(target_arch = "wasm32"))] + { + let other = std::thread::spawn(reorder).join().unwrap(); + assert_eq!(other, !cfg!(feature = "wasm"), "other thread unaffected"); + } { let _on = set_reorder(true); assert_eq!(reorder(), !cfg!(feature = "wasm")); diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 0bc3f4320a..57087cb4f6 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, Step, Term, Vars}; +use super::plan::{Entity, Out, Step, Term, Vars}; use super::project::value; use super::{Counters, Ctx, Operator}; use crate::query::datalog::executor::{eval_expr, is_truthy}; @@ -95,16 +95,30 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { } batch.retain(&keep); } - Step::Bind(expr, vars, slot) => { + Step::Bind(expr, vars, slot, mode) => { let mut keep = Vec::with_capacity(batch.len); let mut out = Vec::with_capacity(batch.len); for i in 0..batch.len { - match eval(expr, vars, &batch, i, ctx)? { - Some(v) => { - out.push(Cell::of_value(ctx.ids, ctx.keys, &v)?); + let Some(v) = eval(expr, vars, &batch, i, ctx)? else { + keep.push(false); + continue; + }; + let cell = Cell::of_value(ctx.ids, ctx.keys, &v)?; + let old = match mode { + Out::New => None, + Out::Check | Out::Replace => batch.cols.get(*slot).and_then(|c| c.get(i)), + }; + match old { + // The executor normalises every bound variable (#596). + Some(old) if !join_eq(old, &cell, true, ctx)? => keep.push(false), + Some(old) if *mode == Out::Check => { + out.push(old.clone()); + keep.push(true); + } + _ => { + out.push(cell); keep.push(true); } - None => keep.push(false), } } batch.retain(&keep); diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 71db3aaf1b..e49d7dbaf1 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -6,8 +6,9 @@ //! runs on the existing executor (spec §9). //! //! Clauses run in the order `optimizer::plan` gives the executor, so an -//! expression sees the same variables, and a binding expression overwrites a -//! variable at the same point, as it does there. The first pattern is a +//! expression sees the same variables as it does there. A binding expression +//! whose variable is already bound keeps the rows where its result is equal +//! (#596). The first pattern is a //! `Scan`; each later one a join: an `IndexNestedLoopJoin` when its entity is //! a variable already bound, a `HashJoin` otherwise (decision 3 of the #545 //! plan). @@ -133,9 +134,9 @@ pub(crate) enum Step { }, /// `[(pred …)]`: keeps the rows where the expression is truthy. Filter(Expr, Vars), - /// `[(f …) ?out]`: binds (or overwrites) the slot; drops the rows where - /// the expression fails. - Bind(Expr, Vars, usize), + /// `[(f …) ?out]`: binds the slot, or keeps the rows where the result is + /// equal to its cell; drops the rows where the expression fails. + Bind(Expr, Vars, usize, Out), /// A later pattern, joined with the rows so far. Join(JoinSpec), } @@ -181,6 +182,19 @@ pub(crate) enum JoinKind { Hash { build_inner: bool }, } +/// What a binding expression does with its slot (#596). +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum Out { + /// The slot is new: the result fills it. + New, + /// The slot is bound: keep the rows where the result is join-equal. + Check, + /// As `Check`, and the result replaces the cell: the expression is + /// earlier in the text than the clause that bound it (decision 2 of the + /// #545 plan). + Replace, +} + /// The variables an expression reads that are bound when it runs, by slot. pub(crate) type Vars = Vec<(String, usize)>; @@ -314,8 +328,10 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { metas.push((m, slots.add(OTHER))); } if let JoinKind::Hash { build_inner } = &mut join.kind { - // Off: always the inner pattern (decision 3 of the #596 plan). - *build_inner = !optimizer::reorder() + // With the test switch off, always the inner pattern + // (decision 3 of the #596 plan); `wasm` keeps the cost choice. + let cost = optimizer::reorder() || cfg!(feature = "wasm"); + *build_inner = !cost || optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) <= optimizer::branch_cost(&outer_patterns); } @@ -339,21 +355,22 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { let step = match binding { None => Step::Filter(expr, vars), Some(out) => { - binders.expression(&out); - let slot = match slots.by_var.get(&out) { - Some(&s) => { + let replace = binders.expression(&expr, &out); + let (slot, mode) = match slots.by_var.get(&out) { + Some(&s) if replace => { if let Some(k) = slots.kinds.get_mut(s) { *k |= OTHER; } - s + (s, Out::Replace) } + Some(&s) => (s, Out::Check), None => { let s = slots.add(OTHER); slots.by_var.insert(out, s); - s + (s, Out::New) } }; - Step::Bind(expr, vars, slot) + Step::Bind(expr, vars, slot, mode) } }; scan.as_ref()?; diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 542242a6ff..965fa13c51 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -318,6 +318,13 @@ fn joins() -> Vec<&'static str> { "[?e :person/score ?s] [(- 0.0 ?s) ?t] [?f :person/score ?t]", "[?e :person/boss ?b] [(+ 18 3) ?b] [?f :person/age ?b]", "[?e :person/age ?a] [(+ ?a 1) ?a] [?f :person/age ?a]", + // An expression binding a bound variable unifies (#596). + "[?e :person/age ?a] [:p1 :person/age ?x] [(+ ?a 1) ?x]", + "[?e :person/age ?a] [(+ ?a 0) ?a]", + "[?e :person/age ?a] [(* ?a 2) ?x] [(+ ?a ?a) ?x]", + "[?e :person/age ?a] [(* ?a 2) ?x] [(+ ?a 1) ?x]", + "[?e :person/score ?s] [(* ?s 1.0) ?s]", + "[?e :person/score ?s] [(- 0.0 ?s) ?t] [?f :person/score ?t] [(- 0.0 ?t) ?s]", ] } @@ -717,6 +724,57 @@ fn planner_chooses_the_join() { kinds("(query [:find ?e :where [?e :a ?x] [?f ?x ?y]])"), ["hash inner=false"] ); + // With the test switch off the table is always built on the inner + // pattern (`wasm` keeps the cost choice). + let _off = crate::query::datalog::optimizer::set_reorder(false); + if !cfg!(feature = "wasm") { + assert_eq!( + kinds("(query [:find ?e :where [?e :a 1] [?f :b ?y] [?f :c ?e]])"), + ["hash inner=true", "probe"] + ); + } +} + +#[test] +fn planner_binds_checks_or_replaces_an_expression_output() { + use super::plan::{Out, Step, plan}; + use crate::query::datalog::parser::parse_datalog_command; + use crate::query::datalog::types::DatalogCommand; + let modes = |q: &str| -> Vec { + let Ok(DatalogCommand::Query(query)) = parse_datalog_command(q) else { + panic!("expected a query"); + }; + let plan = plan(&query).expect("an engine plan"); + plan.steps + .iter() + .filter_map(|s| match s { + Step::Bind(_, _, _, m) => Some(*m), + _ => None, + }) + .collect() + }; + assert_eq!( + modes("(query [:find ?b :where [?e :a ?a] [(+ ?a 1) ?b]])"), + [Out::New] + ); + // The pattern binding ?x is first in the text and in the plan. + assert_eq!( + modes("(query [:find ?x :where [?f :b ?x] [?e :a ?a] [(+ ?a 1) ?x]])"), + [Out::Check] + ); + // [:p :b ?x] runs first (natively), but the expression is earlier in the text. + let _on = crate::query::datalog::optimizer::set_reorder(true); + if crate::query::datalog::optimizer::reorder() { + assert_eq!( + modes("(query [:find ?x :where [?e :a ?a] [(+ ?a 1) ?x] [:p :b ?x]])"), + [Out::Replace] + ); + } + let _off = crate::query::datalog::optimizer::set_reorder(false); + assert_eq!( + modes("(query [:find ?x :where [?e :a ?a] [(+ ?a 1) ?x] [:p :b ?x]])"), + [Out::New] + ); } /// Joins whose answers span many batches: one probe with more than a batch diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index a5f25c6e1b..79d8682f34 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -388,6 +388,8 @@ fn test_or_join_does_not_return_duplicate_bindings() { /// before merging, so a branch can't smuggle in a new distinguishing variable): /// once the cheap branch covers every incoming join-var key, the expensive branch /// (guarded by a call-counting predicate) must never run. +// The #250 short-circuits are native-only (`optimizer::reorder`). +#[cfg(not(feature = "wasm"))] #[test] fn test_or_join_short_circuits_expensive_branch_when_fully_covered() { let db = db(); @@ -476,6 +478,8 @@ fn test_or_join_falls_back_to_expensive_branch_when_not_fully_covered() { /// is 1). If `branch_cost`-based sorting were broken (e.g. reverted to declaration /// order), the expensive branch — written first — would run before coverage is /// established and invoke the counter. +// The #250 short-circuits are native-only (`optimizer::reorder`). +#[cfg(not(feature = "wasm"))] #[test] fn test_or_join_short_circuit_relies_on_cost_sort_not_declaration_order() { let db = db(); @@ -526,6 +530,8 @@ fn test_or_join_short_circuit_relies_on_cost_sort_not_declaration_order() { /// (21) Plain `or` short-circuits too, when it's a pure filter (no branch introduces /// a variable beyond what's already bound in the incoming scope). +// The #250 short-circuits are native-only (`optimizer::reorder`). +#[cfg(not(feature = "wasm"))] #[test] fn test_or_short_circuits_pure_filter_when_fully_covered() { let db = db(); diff --git a/tests/join_rules_test.rs b/tests/join_rules_test.rs index fc67274df9..d68e713c1c 100644 --- a/tests/join_rules_test.rs +++ b/tests/join_rules_test.rs @@ -109,18 +109,29 @@ fn keyword_or_ref_through_the_attribute_position() { } #[test] -fn expression_binding_is_kept_by_later_joins() { +fn expression_binding_unifies_and_the_first_binder_gives_the_value() { let db = Minigraf::in_memory().unwrap(); db.execute("(transact [[:f :m 0.0] [:e :n 0.0] [:g :k 0.0]])") .unwrap(); - // Plan: `[:f :m ?v]` binds `?v`, `[:e :n ?w]`, the expression - // overwrites `?v` with -0.0, then `[?g :k ?v]` joins on it. That pattern - // comes first in the text, but an expression's value is kept. + // Plan: `[:f :m ?v]` binds `?v`, `[:e :n ?w]`, the expression's -0.0 + // equals it (#596), then `[?g :k ?v]` joins on it. That pattern comes + // first in the text, so its 0.0 is returned. let r = query( &db, "[:find ?v :where [?g :k ?v] [:f :m ?v] [:e :n ?w] [(* ?w -1.0) ?v]]", ); assert_eq!(r.len(), 1); + assert!( + matches!(r[0][0], Value::Float(f) if f == 0.0 && f.is_sign_positive()), + "the first pattern's 0.0" + ); + // Natively `[:f :m ?v]` runs first; the expression, earlier in the + // text, gives its -0.0. + let r = query( + &db, + "[:find ?v :where [?x :n ?w] [(* ?w -1.0) ?v] [:f :m ?v]]", + ); + assert_eq!(r.len(), 1); assert!( matches!(r[0][0], Value::Float(f) if f == 0.0 && f.is_sign_negative()), "the expression's -0.0" diff --git a/tests/model_based_test.rs b/tests/model_based_test.rs index 94ec1b1408..09475e1965 100644 --- a/tests/model_based_test.rs +++ b/tests/model_based_test.rs @@ -19,6 +19,18 @@ mod reference_model; use proptest::prelude::*; use reference_model::*; +/// With `test-oracle`, every query also runs without clause reordering and +/// must give the same rows (#596). +fn source_order() -> Option { + #[cfg(feature = "test-oracle")] + return Some(|db, q| { + let _off = minigraf::__reorder(false); + db.execute(q) + }); + #[cfg(not(feature = "test-oracle"))] + None +} + // ── Strategies ──────────────────────────────────────────────────────────────── fn arb_op() -> impl Strategy { @@ -101,7 +113,7 @@ proptest! { /// Every read after every step matches the reference model. #[test] fn file_backed_db_matches_model(steps in arb_steps()) { - run(&steps, Checks::All)?; + run_with(&steps, Checks::All, source_order())?; } } diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs new file mode 100644 index 0000000000..796bb00324 --- /dev/null +++ b/tests/plan_independence_test.rs @@ -0,0 +1,278 @@ +//! Every plan returns the same rows the same number of times (#596, design +//! `docs/superpowers/specs/2026-10-15-plan-independent-answers-design.md`). +//! +//! Each query runs through `Minigraf::execute` and through a drained +//! `Minigraf::query` cursor, with clause reordering on and off +//! (`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. +#![cfg(all(feature = "test-oracle", not(target_arch = "wasm32")))] + +use minigraf::{Minigraf, QueryResult, Value}; + +/// A value as text, without `Debug` (CodeQL `rust/cleartext-logging`). +fn key(v: &Value) -> String { + match v { + Value::String(s) => format!("s:{s}"), + Value::Integer(i) => format!("i:{i}"), + Value::Float(f) => format!("f:{:016x}", f.to_bits()), + Value::Boolean(b) => format!("b:{b}"), + Value::Ref(u) => format!("r:{}", u.as_hyphenated()), + Value::Keyword(k) => format!("k:{k}"), + Value::Null => "nil".to_string(), + } +} + +fn bag(rows: &[Vec]) -> Vec> { + let mut b: Vec> = rows.iter().map(|r| r.iter().map(key).collect()).collect(); + b.sort(); + b +} + +fn executed(db: &Minigraf, q: &str) -> Vec> { + match db.execute(q).expect("query") { + QueryResult::QueryResults { results, .. } => bag(&results), + _ => panic!("expected QueryResults"), + } +} + +fn pulled(db: &Minigraf, q: &str) -> Vec> { + let mut cursor = db.query(q).expect("query"); + let mut rows = Vec::new(); + while let Some(batch) = cursor.next_batch(7).expect("batch") { + rows.extend(batch.rows().iter().cloned()); + } + bag(&rows) +} + +/// The answer to `q`, or how the plans disagree. +fn check(db: &Minigraf, q: &str) -> Result>, String> { + let on = { + let _g = minigraf::__reorder(true); + executed(db, q) + }; + let runs = [ + ("cursor, reordering", { + let _g = minigraf::__reorder(true); + pulled(db, q) + }), + ("execute, source order", { + let _g = minigraf::__reorder(false); + executed(db, q) + }), + ("cursor, source order", { + let _g = minigraf::__reorder(false); + pulled(db, q) + }), + ]; + for (name, rows) in runs { + if rows != on { + return Err(format!( + "{name}: {} rows, reordering execute: {} rows, for {q}", + rows.len(), + on.len() + )); + } + } + Ok(on) +} + +/// The answer to `q`, after checking that every plan gives it. +fn same(db: &Minigraf, q: &str) -> Vec> { + check(db, q).unwrap_or_else(|e| panic!("{e}")) +} + +fn bob() -> uuid::Uuid { + uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":bob") +} + +fn people(db: &Minigraf) { + let long_a = "a".repeat(80); + let long_b = "b".repeat(80); + db.execute(&format!( + r#"(transact [[:alice :name "Alice"] [:alice :age 30] [:alice :friend :bob] + [:bob :name "Bob"] [:bob :age 40] [:bob :friend :carol] + [:carol :name "Carol"] [:carol :age 40] [:carol :friend #uuid "{}"] + [:dave :name "Dave"] [:dave :age 25] + [:p1 :score 41] [:p2 :score 31] [:p3 :score 41.0] + [:alice :x 0.0] [:bob :y -0.0] [:carol :x 1.5] [:dave :y 1.5] + [:alice :bio "{long_a}"] [:bob :motto "{long_a}"] [:carol :motto "{long_b}"]])"#, + bob().as_hyphenated() + )) + .unwrap(); + db.execute(r#"(transact {:valid-from "2020-01-01T00:00:00Z" :valid-to "2021-01-01T00:00:00Z"} [[:erin :name "Erin"] [:erin :age 50]])"#) + .unwrap(); + db.execute("(retract [[:dave :age 25]])").unwrap(); + db.execute("(rule [(knows ?a ?b) [?a :friend ?b]])") + .unwrap(); + db.execute("(rule [(knows ?a ?c) [?a :friend ?b] (knows ?b ?c)])") + .unwrap(); + db.execute("(rule [(lonely ?e) [?e :name _] (not [?e :friend _])])") + .unwrap(); +} + +/// Queries whose answers must not depend on the plan. +const MATRIX: &[&str] = &[ + // Patterns, joins, cross products. + r#"[:find ?n ?a :where [?e :name ?n] [?e :age ?a]]"#, + r#"[:find ?n ?a :where [?e :age ?a] [?e :name ?n]]"#, + r#"[:find ?n :where [?e :age ?a] [?e :name "Alice"] [?e :name ?n]]"#, + r#"[:find ?n ?fn :where [?e :friend ?f] [?f :name ?fn] [?e :name ?n]]"#, + r#"[:find ?n ?m :where [?e :name ?n] [?f :score ?m]]"#, + r#"[:find ?e ?f :where [?e :age ?a] [?f :age ?a]]"#, + // Keyword or ref (#545 decision 2), both text orders. + r#"[:find ?b ?n :where [?a :friend ?b] [?b :name ?n]]"#, + r#"[:find ?b ?n :where [?b :name ?n] [?a :friend ?b]]"#, + // Floats: 0.0 and -0.0 join; an integer never equals a float. + r#"[:find ?e ?f :where [?e :x ?v] [?f :y ?v]]"#, + r#"[:find ?e ?f :where [?e :score ?v] [?f :score ?v]]"#, + // Long strings. + r#"[:find ?e ?f :where [?e :bio ?s] [?f :motto ?s]]"#, + // Filter and binding expressions. + r#"[:find ?n :where [?e :age ?a] [(> ?a 30)] [?e :name ?n]]"#, + r#"[:find ?n ?b :where [?e :age ?a] [(+ ?a 1) ?b] [?e :name ?n]]"#, + // #596: an expression binding a variable a pattern binds unifies. + r#"[:find ?a ?x :where [?e :age ?a] [:p1 :score ?x] [(+ ?a 1) ?x]]"#, + r#"[:find ?e ?s :where [?e :age ?a] [(+ ?a 1) ?s] [?p :score ?s]]"#, + r#"[:find ?e :where [?e :age ?v] [(+ ?v 1) ?v]]"#, + r#"[:find ?e ?x :where [?e :age ?a] [(+ ?a 1) ?x] [(- ?a -1) ?x]]"#, + r#"[:find ?e ?x :where [?e :age ?a] [(+ ?a 1) ?x] [(* ?a 2) ?x]]"#, + r#"[:find ?e ?x :where [?e :age ?a] [(+ ?a 1.0) ?x] [?p :score ?x]]"#, + // Rules: recursive, and with negation. + r#"[:find ?x ?y :where (knows ?x ?y)]"#, + r#"[:find ?n ?y :where (knows ?x ?y) [?x :name ?n]]"#, + r#"[:find ?n :where (lonely ?e) [?e :name ?n]]"#, + r#"[:find ?n ?b :where (knows ?x ?y) [?x :age ?a] [(+ ?a 1) ?b] [?x :name ?n]]"#, + // or / or-join, including #250's pure-filter and covered-key shapes. + r#"[:find ?n :where [?e :name ?n] (or [?e :age 40] [?e :friend :bob])]"#, + r#"[:find ?n :where [?e :name ?n] (or [?e :name "Alice"] [?e :name "Bob"])]"#, + r#"[:find ?n ?v :where [?e :name ?n] (or [?e :age ?v] [?e :x ?v])]"#, + r#"[:find ?n :where [?e :name ?n] (or-join [?e] [?e :friend ?f] [?e :x ?s])]"#, + r#"[:find ?n :where [?e :name ?n] (or-join [?e] [?e :age 40] [?e :friend _])]"#, + // not / not-join, placed and deferred. + r#"[:find ?n :where [?e :name ?n] (not [?e :friend _])]"#, + r#"[:find ?n :where [?e :name ?n] (not-join [?e] [?e :friend ?f] [?f :age 40])]"#, + r#"[:find ?n :where [?e :name ?n] (or [?e :age ?a] [?e :score ?a]) (not [(> ?a 35)])]"#, + 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 _]]"#, + // 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]]"#, + r#"[:find ?n ?a :any-valid-time :where [?e :name ?n] [?e :age ?a]]"#, +]; + +fn run_matrix(db: &Minigraf) { + let failures: Vec = MATRIX + .iter() + .filter_map(|q| check(db, &format!("(query {q})")).err()) + .collect(); + assert!(failures.is_empty(), "{}", failures.join("\n")); +} + +#[test] +fn matrix_in_memory() { + let db = Minigraf::in_memory().unwrap(); + people(&db); + run_matrix(&db); +} + +#[test] +fn matrix_file_backed_after_checkpoint() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("plan.graph"); + { + let db = Minigraf::open(&path).unwrap(); + people(&db); + db.checkpoint().unwrap(); + // Pending facts over committed ones. + db.execute( + r#"(transact [[:frank :name "Frank"] [:frank :age 40] [:frank :friend :alice]])"#, + ) + .unwrap(); + run_matrix(&db); + } + let db = Minigraf::open(&path).unwrap(); + db.execute("(rule [(knows ?a ?b) [?a :friend ?b]])") + .unwrap(); + db.execute("(rule [(knows ?a ?c) [?a :friend ?b] (knows ?b ?c)])") + .unwrap(); + db.execute("(rule [(lonely ?e) [?e :name _] (not [?e :friend _])])") + .unwrap(); + run_matrix(&db); +} + +// ── #596: expression bindings unify ────────────────────────────────────────── + +#[test] +fn issue_596_example() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :age 30] [:b :age 40] [:p1 :score 41]])") + .unwrap(); + let r = same( + &db, + "(query [:find ?a ?x :where [?e :age ?a] [:p1 :score ?x] [(+ ?a 1) ?x]])", + ); + assert_eq!( + r, + vec![vec!["i:40".to_string(), "i:41".to_string()]], + "only the row where ?a + 1 is the score" + ); +} + +#[test] +fn expression_output_equal_to_its_input_never_matches() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :age 30]])").unwrap(); + let r = same(&db, "(query [:find ?e :where [?e :age ?v] [(+ ?v 1) ?v]])"); + assert!(r.is_empty(), "?v + 1 is never ?v"); +} + +#[test] +fn two_expressions_on_one_variable_must_agree() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :age 0] [:b :age 3]])").unwrap(); + // 2a = a + a for every a; a + 1 = 2a only for a = 1 (none here). + let r = same( + &db, + "(query [:find ?a ?x :where [?e :age ?a] [(* ?a 2) ?x] [(+ ?a ?a) ?x]])", + ); + assert_eq!(r.len(), 2, "both agree for every age"); + let r = same( + &db, + "(query [:find ?a ?x :where [?e :age ?a] [(* ?a 2) ?x] [(+ ?a 1) ?x]])", + ); + assert!(r.is_empty(), "they never agree here"); +} + +#[test] +fn unify_int_never_equals_float() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :age 40] [:p :score 41] [:q :score 41.0]])") + .unwrap(); + let r = same( + &db, + "(query [:find ?p :where [?e :age ?a] [(+ ?a 1) ?x] [?p :score ?x]])", + ); + assert_eq!(r.len(), 1, "41 matches 41, not 41.0"); + let r = same( + &db, + "(query [:find ?p :where [?e :age ?a] [(+ ?a 1.0) ?x] [?p :score ?x]])", + ); + assert_eq!(r.len(), 1, "41.0 matches 41.0, not 41"); +} + +#[test] +fn unify_negative_zero_equals_zero() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :x 0.0] [:b :y -0.0]])").unwrap(); + let r = same( + &db, + "(query [:find ?e ?f :where [?e :x ?v] [(* ?v 1.0) ?w] [?f :y ?w]])", + ); + assert_eq!(r.len(), 1, "0.0 unifies with -0.0"); +} diff --git a/tests/property_test.rs b/tests/property_test.rs index 9bb9eef436..ebde7effb6 100644 --- a/tests/property_test.rs +++ b/tests/property_test.rs @@ -898,9 +898,22 @@ fn check_queries( fn ctx() -> Ctx { Ctx { uuids: (0..ENTITIES).map(|i| (entity_uuid(i), i)).collect(), + rerun: source_order(), } } +/// With `test-oracle`, every query also runs without clause reordering and +/// must give the same rows (#596). +fn source_order() -> Option { + #[cfg(feature = "test-oracle")] + return Some(|db, q| { + let _off = minigraf::__reorder(false); + db.execute(q) + }); + #[cfg(not(feature = "test-oracle"))] + None +} + fn run_in_memory(history: &[HistoryOp], queries: &[Query]) -> Result<(), TestCaseError> { let db = Minigraf::in_memory().map_err(|_| TestCaseError::fail("in_memory failed"))?; let mut model = Model::default(); diff --git a/tests/reference_model/mod.rs b/tests/reference_model/mod.rs index c99a0e0d42..afb248c660 100644 --- a/tests/reference_model/mod.rs +++ b/tests/reference_model/mod.rs @@ -448,13 +448,32 @@ impl Model { // ── Checks ──────────────────────────────────────────────────────────────────── +/// Runs a query another way, e.g. without clause reordering (#596). +pub type Rerun = fn(&Minigraf, &str) -> Result; + pub struct Ctx { pub uuids: HashMap, + /// When set, every query also runs this way and must give the same bag. + pub rerun: Option, } impl Ctx { pub fn rows(&self, db: &Minigraf, query: &str) -> Result>, TestCaseError> { - self.result_rows(db.execute(query), query) + let rows = self.result_rows(db.execute(query), query)?; + if let Some(rerun) = self.rerun { + let mut again = self.result_rows(rerun(db, query), query)?; + let mut first = rows.clone(); + first.sort(); + again.sort(); + if again != first { + return Err(TestCaseError::fail(format!( + "rows depend on the plan ({} vs {}): {query}", + first.len(), + again.len() + ))); + } + } + Ok(rows) } pub fn result_rows( @@ -798,10 +817,16 @@ pub fn expect_outcome( pub const IN_TX_QUERY: &str = "(query [:find ?e ?a ?v :any-valid-time :where [?e ?a ?v]])"; pub fn run(steps: &[Step], checks: Checks) -> Result<(), TestCaseError> { + run_with(steps, checks, None) +} + +/// [`run`], with every query also run by `rerun` ([`Ctx::rerun`]). +pub fn run_with(steps: &[Step], checks: Checks, rerun: Option) -> Result<(), TestCaseError> { let dir = tempfile::tempdir().map_err(|_| TestCaseError::fail("tempdir"))?; let mut path = dir.path().join("model.graph"); let ctx = Ctx { uuids: (0..ENTITIES).map(|i| (entity_uuid(i), i)).collect(), + rerun, }; let mut model = Model::default(); let mut db = Some(open(&path, OpenMode::Default)?);