Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -11,6 +11,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

- **A `:db/valid-at` pattern in a `not-join` body binds the query's valid time on every path** (#615). When the body also held an expression, sat in an `or` branch, or ran in a query that invokes a rule, the body bound `nil`, so `(not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])` never matched and excluded nothing; without the expression the same body excluded every entity. It now binds the query's `:valid-at` value (or the current time) as the other paths do. Present since v0.13.1.
- **A `:db/valid-at` pattern in a rule definition binds the query's valid time** (#617). The rule evaluators never received it, so in a rule body the pattern bound `nil` and the query failed with `INT-022`; in a rule's `not` / `not-join` body it bound `nil`, so the negation never matched on it; and in a rule's `or` branch it bound the current time instead of the query's `:valid-at`. Rule bodies, their negation bodies and `or` branches now bind the query's `:valid-at` value, the current time without one, and `nil` under `:any-valid-time`, as patterns outside rules do.
- **An expression reading a variable only an `or` binds keeps its rows** (#625). The planner places expressions among the patterns and `not`s, and `or` / `or-join` run after them, so an expression such as `[(> ?x 1)]` in `[?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]` ran before `?x` was bound and dropped every row, in queries and in rule bodies. Such an expression now runs after the `or`s, before the `not`s that wait for them, as those `not`s already did.
- **An `or` / `or-join` branch whose expression reads an outer variable matches** (#620). A branch such as `[(> ?v 1)]` in `[?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])` was evaluated on its own from an empty binding and joined back afterwards, so its expression saw `?v` unbound and the branch matched nothing: the `or` silently dropped rows it should keep, in queries and in rule bodies. A branch whose expression reads a variable the branch does not bind itself is now seeded with each incoming row (an `or-join` branch with the row's join variables).

## v2.0.7 — 2026-10-16
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint.

## Test Coverage

**1289 tests** (1280 passing, 9 ignored; unit + integration + doc).
**1293 tests** (1284 passing, 9 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1289 tests
cargo test # run 1293 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
4 changes: 2 additions & 2 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@

**Verified**: 2026-10-16 with `cargo test`

**Result**: 1,280 passing tests and 9 ignored tests (1,289 total), including the golden-file corpus (#391)
**Result**: 1,284 passing tests and 9 ignored tests (1,293 total), including the golden-file corpus (#391)

For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, 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 a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617).

Expand All @@ -18,7 +18,7 @@ For v2.0.5, torn-WAL-tail tests (#513) check that opening a WAL writer cuts off

`tests/magic_sets_test.rs` checks rule queries with a literal argument where some call site cannot carry the magic-sets demand (#608): a rule-body call with an argument nothing binds yet, the same rule called with free arguments, a call from a rule called with free arguments, calls inside `or` and `not`, a fully literal call, and a call bound only by a variable; `magic_sets.rs` unit tests check the adornment each shape solves to.

`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`.
`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`. Expressions reading a variable only an `or` binds, including a chain and a `not` after them, keep their rows in queries, with rules and in rule bodies (#625); optimizer unit tests cover deferring them ahead of the deferred `not`s.

Not counted above: the `BrowserDb` tests run only on wasm32 with `wasm-bindgen-test` in a browser. Two of them check that the IndexedDB flush returns every page a write dirtied, and that a dirty page that cannot be read is an error rather than left out.

Expand Down
15 changes: 12 additions & 3 deletions src/query/datalog/evaluator.rs
Original file line number Diff line number Diff line change
Expand Up @@ -868,9 +868,10 @@ impl StratifiedEvaluator {
);

// Plan: assigns index hints + pushes Expr to earliest binding position.
// Not/NotJoin are excluded from plan_clauses above, so `deferred` is
// always empty here — rule bodies keep their existing not-filter path.
let (planned, _deferred) = crate::query::datalog::optimizer::plan(
// Not/NotJoin are excluded from plan_clauses above, so `deferred` holds
// only expressions whose variables an Or/OrJoin binds (#625); they run
// after the or pass. Rule bodies keep their existing not-filter path.
let (planned, deferred) = crate::query::datalog::optimizer::plan(
plan_clauses,
&crate::storage::index::Indexes::new(),
);
Expand Down Expand Up @@ -945,6 +946,14 @@ impl StratifiedEvaluator {
drop(registry_guard);
expanded
};
let candidates = {
let fn_guard = self
.functions
.read()
.map_err(|_| err_coded!(ErrorCode::Qry008))?;
let exprs: Vec<&WhereClause> = deferred.iter().collect();
apply_expr_clauses_in_evaluator(candidates, &exprs, &fn_guard)
};

// Build temp_eval once per rule (outside the binding loop);
// instantiate_head_public only uses storage, not the registry.
Expand Down
19 changes: 14 additions & 5 deletions src/query/datalog/executor.rs
Original file line number Diff line number Diff line change
Expand Up @@ -595,15 +595,20 @@ impl DatalogExecutor {
)?;
drop(rules_guard);

// 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.
// Apply Not/NotJoin clauses the planner couldn't place inline (#248), and
// expressions (#625) — 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; expressions cost 0 and come first, so a
// stable sort keeps them ahead of the nots, in text order.
#[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);
for clause in deferred_not_clauses {
bindings = match clause {
c @ WhereClause::Expr { .. } => {
apply_expr_clauses(bindings, std::slice::from_ref(&c), &registry)?
}
WhereClause::Not(body) => apply_not_clause(
bindings,
&body,
Expand Down Expand Up @@ -846,8 +851,9 @@ impl DatalogExecutor {
)?;
drop(rules_guard);

// Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their
// variables are only bound by the Or/OrJoin pass above. (The StratifiedEvaluator
// Apply Not/NotJoin clauses the planner couldn't place inline (#248), and
// expressions (#625) — their variables are only bound by the Or/OrJoin pass
// above. Expressions come first, as 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))]
Expand All @@ -856,6 +862,9 @@ impl DatalogExecutor {
deferred_not_clauses.sort_by_key(optimizer::clause_cost);
for clause in deferred_not_clauses {
bindings = match clause {
c @ WhereClause::Expr { .. } => {
apply_expr_clauses(bindings, std::slice::from_ref(&c), &registry)?
}
WhereClause::Not(body) => apply_not_clause_derived(
bindings,
&body,
Expand Down
88 changes: 67 additions & 21 deletions src/query/datalog/optimizer.rs
Original file line number Diff line number Diff line change
Expand Up @@ -165,6 +165,11 @@ fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet<String>
/// clause, which the executor applies after this plan) and must be evaluated by the
/// executor's post-filter instead, to avoid running it before its dependency is bound.
///
/// An `Expr` reading a variable that no pattern in the list and no `Expr` placed
/// before it binds is deferred the same way (#625), ahead of the deferred
/// `Not`/`NotJoin` clauses and in text order, since a deferred `not` may read what
/// it binds.
///
/// Returns `(interleaved, deferred)` where `interleaved` pairs each Pattern with
/// `Some(hint)` and each Expr/Not/NotJoin with `None`.
pub fn plan(
Expand Down Expand Up @@ -208,16 +213,33 @@ pub fn plan(
.collect();

// Push each Expr to the earliest position where all its variables are bound.
// An Expr reading a variable that no pattern here and no Expr placed before
// it binds depends on a source outside this list (an Or/OrJoin, #625): it is
// deferred, ahead of the deferred nots, which may read what it binds.
let mut deferred: Vec<WhereClause> = Vec::new();
let mut placeable: std::collections::HashSet<String> = result
.iter()
.flat_map(|(c, _)| match c {
WhereClause::Pattern(p) => pattern_bound_vars(p),
_ => Vec::new(),
})
.collect();
for expr_clause in exprs {
let vars: std::collections::HashSet<String> =
if let WhereClause::Expr { expr, .. } = &expr_clause {
expr_vars(expr).into_iter().collect()
let (vars, out): (std::collections::HashSet<String>, Option<String>) =
if let WhereClause::Expr { expr, binding } = &expr_clause {
(expr_vars(expr).into_iter().collect(), binding.clone())
} else {
Default::default()
};
if !vars.is_subset(&placeable) {
deferred.push(expr_clause);
continue;
}
placeable.extend(out);

let mut bound: std::collections::HashSet<String> = Default::default();
// Default: append at end (covers no-var Exprs and vars never bound by any pattern).
// Default: append at end (covers no-var Exprs and Exprs reading what an
// Expr placed earlier binds).
let mut insert_pos = result.len();

if !vars.is_empty() {
Expand All @@ -243,7 +265,6 @@ pub fn plan(
#[cfg(not(feature = "wasm"))]
not_clauses.sort_by_key(|c| std::cmp::Reverse(clause_cost(c)));

let mut deferred: Vec<WhereClause> = Vec::new();
for nc in not_clauses {
let required: std::collections::HashSet<String> = match &nc {
// `?_`-prefixed vars are the wildcard idiom (e.g. `(not [?e :attr ?_x])`)
Expand Down Expand Up @@ -601,26 +622,51 @@ mod tests {
);
}

#[cfg(not(feature = "wasm"))]
#[test]
fn test_expr_unbound_var_goes_to_end() {
use crate::storage::index::Indexes;
// ?x is never bound by any pattern
let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v")));
let expr = WhereClause::Expr {
fn gt(v: &str, n: i64, binding: Option<&str>) -> WhereClause {
WhereClause::Expr {
expr: Expr::BinOp(
BinOp::Gt,
Box::new(Expr::Var("?x".to_string())),
Box::new(Expr::Lit(Value::Integer(0))),
Box::new(Expr::Var(v.to_string())),
Box::new(Expr::Lit(Value::Integer(n))),
),
binding: None,
};
let (planned, _deferred) = plan(vec![p1, expr], &Indexes::new());
assert_eq!(planned.len(), 2);
assert!(
matches!(planned[1].0, WhereClause::Expr { .. }),
"Expr with unbound var must be last"
binding: binding.map(str::to_string),
}
}

#[test]
fn test_expr_unbound_var_is_deferred() {
use crate::storage::index::Indexes;
// ?x is never bound by any pattern: an Or binds it, after the plan (#625).
let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v")));
let expr = gt("?x", 0, None);
let (planned, deferred) = plan(vec![p1, expr.clone()], &Indexes::new());
assert_eq!(planned.len(), 1, "the Expr must not be planned");
assert_eq!(deferred, vec![expr]);
}

#[test]
fn test_expr_reading_placed_expr_output_is_planned() {
use crate::storage::index::Indexes;
// ?y comes from an Expr whose input a pattern binds: both are planned.
let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v")));
let (bind, read) = (gt("?v", 0, Some("?y")), gt("?y", 0, None));
let (planned, deferred) = plan(vec![p1, bind, read], &Indexes::new());
assert!(deferred.is_empty());
assert_eq!(planned.len(), 3);
}

#[test]
fn test_deferred_exprs_come_before_deferred_nots_in_text_order() {
use crate::storage::index::Indexes;
let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v")));
let not_clause = WhereClause::Not(vec![gt("?y", 0, None)]);
let (bind, read) = (gt("?x", 0, Some("?y")), gt("?y", 0, None));
let (planned, deferred) = plan(
vec![p1, not_clause.clone(), bind.clone(), read.clone()],
&Indexes::new(),
);
assert_eq!(planned.len(), 1);
assert_eq!(deferred, vec![bind, read, not_clause]);
}

// ── Not/NotJoin push-down (#248) ─────────────────────────────────────
Expand Down
38 changes: 38 additions & 0 deletions tests/disjunction_test.rs
Original file line number Diff line number Diff line change
Expand Up @@ -866,3 +866,41 @@ fn test_or_branch_expression_reads_outer_variable_in_rule_body() {
let r = int_rows(&db, "(query [:find ?w :where (pick ?e ?w)])");
assert_eq!(r, vec!["1", "2"], "or-and in a rule body");
}

// ── #625: an expression reading a variable only an `or` binds ────────────────

fn issue_625_db() -> Minigraf {
let db = db();
db.execute("(transact [[:a :n 1] [:b :n 2] [:c :ok true]])")
.unwrap();
db
}

#[test]
fn test_expression_after_or_reads_or_bound_variable() {
let db = issue_625_db();
let r = db
.execute("(query [:find ?e ?x :where [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])")
.unwrap();
assert_eq!(result_count(&r), 1, "only :b has ?x over 1");
let r = db
.execute(
"(query [:find ?y :where [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(+ ?x 10) ?y] (not [(> ?y 11)])])",
)
.unwrap();
assert_eq!(result_count(&r), 1, "the not sees the expression's ?y");
}

#[test]
fn test_expression_after_or_reads_or_bound_variable_with_rules() {
let db = issue_625_db();
db.execute("(rule [(num ?e) [?e :n _]])").unwrap();
db.execute("(rule [(big ?e ?x) [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])")
.unwrap();
let r = db
.execute("(query [:find ?x :where (num ?e) (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])")
.unwrap();
assert_eq!(result_count(&r), 1, "query calling a rule");
let r = db.execute("(query [:find ?x :where (big ?e ?x)])").unwrap();
assert_eq!(result_count(&r), 1, "rule body");
}
Loading