diff --git a/CHANGELOG.md b/CHANGELOG.md index 1a014966d..993d3f9b7 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed - **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. ## v2.0.7 — 2026-10-16 diff --git a/CLAUDE.md b/CLAUDE.md index 06910b411..6f8ded8ac 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1273 tests** (1264 passing, 9 ignored; unit + integration + doc). +**1283 tests** (1274 passing, 9 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index a94da24f9..ff147e276 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1273 tests +cargo test # run 1283 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index e7880bf8d..41e098e93 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,264 passing tests and 9 ignored tests (1,273 total), including the golden-file corpus (#391) +**Result**: 1,274 passing tests and 9 ignored tests (1,283 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). +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). For v2.0.5, 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. diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 10db589a1..1dad9eb48 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -26,7 +26,7 @@ use super::functions::FunctionRegistry; use super::matcher::{Bindings, PatternMatcher, edn_to_entity_id, edn_to_value}; use super::rules::RuleRegistry; -use super::types::{AttributeSpec, EdnValue, Pattern, Rule, WhereClause}; +use super::types::{AttributeSpec, EdnValue, Pattern, Rule, ValidAt, WhereClause}; use crate::error::{ErrorCode, err_coded}; use crate::graph::FactStorage; use crate::graph::types::{Fact, Value}; @@ -70,6 +70,8 @@ pub struct RecursiveEvaluator { max_derived_facts: usize, /// Maximum facts the rules may derive in one evaluation; base facts do not count max_results: usize, + /// The value a `:db/valid-at` pattern in a rule body binds (#617) + valid_at: Value, } impl RecursiveEvaluator { @@ -97,9 +99,17 @@ impl RecursiveEvaluator { max_iterations, max_derived_facts, max_results, + valid_at: Value::Null, } } + /// Set the value a `:db/valid-at` pattern in a rule body binds: the + /// query's valid time (#617). Without it the pattern binds `nil`. + pub fn with_valid_at(mut self, valid_at: Value) -> Self { + self.valid_at = valid_at; + self + } + /// Evaluate rules for given predicates using semi-naive fixed-point iteration. /// /// # Arguments @@ -286,7 +296,8 @@ impl RecursiveEvaluator { return Ok(derived); } - let matcher = PatternMatcher::new(current_facts.clone()); + let matcher = + PatternMatcher::new(current_facts.clone()).with_valid_at(self.valid_at.clone()); let bindings = if patterns.is_empty() { // Expr-only rule body: seed with empty binding vec![Bindings::new()] @@ -615,6 +626,8 @@ pub struct StratifiedEvaluator { max_iterations: usize, max_derived_facts: usize, max_results: usize, + /// The value a `:db/valid-at` pattern in a rule body binds (#617) + valid_at: Value, } impl StratifiedEvaluator { @@ -633,9 +646,18 @@ impl StratifiedEvaluator { max_iterations, max_derived_facts, max_results, + valid_at: Value::Null, } } + /// Set the value a `:db/valid-at` pattern binds in rule bodies and their + /// `not` / `not-join` bodies and `or` branches: the query's `:valid-at` + /// value, the current time without one, `nil` for `:any-valid-time` (#617). + pub fn with_valid_at(mut self, valid_at: Value) -> Self { + self.valid_at = valid_at; + self + } + /// Derive all facts for the given predicates, respecting stratification order. pub fn evaluate(&self, predicates: &[String]) -> Result { use crate::query::datalog::stratification::DependencyGraph; @@ -735,7 +757,8 @@ impl StratifiedEvaluator { self.max_iterations, self.max_derived_facts, self.max_results, - ); + ) + .with_valid_at(self.valid_at.clone()); let derived = sub_eval.evaluate_recursive_rules(&stratum_preds)?; // Snapshot existing fact keys so we only load truly new (derived) facts let existing: HashSet<(uuid::Uuid, String, Vec)> = accumulated @@ -839,7 +862,10 @@ impl StratifiedEvaluator { // Compute once; reuse for plan loop, apply_or_clauses, not-body matching. let accumulated_facts: Arc<[Fact]> = Arc::from(accumulated.get_asserted_facts()?); - let matcher = PatternMatcher::from_slice(accumulated_facts.clone()); + let matcher = PatternMatcher::from_slice_with_valid_at( + accumulated_facts.clone(), + self.valid_at.clone(), + ); // Plan: assigns index hints + pushes Expr to earliest binding position. // Not/NotJoin are excluded from plan_clauses above, so `deferred` is @@ -901,13 +927,19 @@ impl StratifiedEvaluator { // FunctionRegistry (UDF registration happens at the db layer). Use the // built-in-only registry so or-branches can still use built-in predicates. let fn_registry = FunctionRegistry::with_builtins(); + // An or branch binds `:db/valid-at` from a `ValidAt`, the + // inverse of the executor's mapping to `self.valid_at`. + let branch_valid_at = match &self.valid_at { + Value::Integer(t) => ValidAt::Timestamp(*t), + _ => ValidAt::AnyValidTime, + }; let expanded = apply_or_clauses( &rule.body, candidates, accumulated_facts.clone(), ®istry_guard, None, - None, + Some(branch_valid_at), &fn_registry, )?; drop(registry_guard); @@ -962,7 +994,10 @@ impl StratifiedEvaluator { }) .collect(); - let not_matcher = PatternMatcher::from_slice(accumulated_facts.clone()); + let not_matcher = PatternMatcher::from_slice_with_valid_at( + accumulated_facts.clone(), + self.valid_at.clone(), + ); let mut not_bindings: Vec = if substituted.is_empty() { vec![binding.clone()] } else { @@ -1008,7 +1043,7 @@ impl StratifiedEvaluator { nj_clauses, &binding, accumulated_facts.clone(), - Value::Null, + self.valid_at.clone(), &fn_guard, ) { continue 'binding; diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index be4206398..95455e1b1 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -702,7 +702,8 @@ impl DatalogExecutor { 1000, // max iterations effective_max_derived, effective_max_results, - ); + ) + .with_valid_at(valid_at_value.clone()); let derived_storage = evaluator.evaluate(&predicates)?; diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index ae1261865..c32cc6ab6 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -41,6 +41,7 @@ impl PatternMatcher { /// asserted facts. The caller is responsible for ensuring the slice contains /// only currently asserted facts (equivalent to `FactStorage::get_asserted_facts()` /// at the snapshot moment). No additional filtering is applied at match time. + #[cfg(test)] pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { PatternMatcher { storage: MatcherStorage::Slice(facts), @@ -59,6 +60,12 @@ impl PatternMatcher { } } + /// Set the value a `:db/valid-at` pattern binds. + pub(crate) fn with_valid_at(mut self, valid_at: Value) -> Self { + self.valid_at_value = valid_at; + self + } + fn get_facts(&self) -> Cow<'_, [Fact]> { match &self.storage { MatcherStorage::Owned(s) => Cow::Owned(s.get_asserted_facts().unwrap_or_default()), diff --git a/tests/recursive_rules_test.rs b/tests/recursive_rules_test.rs index 967b36243..2be4dc4ff 100644 --- a/tests/recursive_rules_test.rs +++ b/tests/recursive_rules_test.rs @@ -503,3 +503,121 @@ fn test_max_results_counts_derived_facts_not_base_facts() { .unwrap_err(); assert_eq!(err.code(), "INT-020"); } + +/// 2030-01-01T00:00:00Z in Unix ms. +const VALID_AT_2030: i64 = 1_893_456_000_000; + +fn result_rows(r: QueryResult) -> Vec> { + match r { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected QueryResults"), + } +} + +/// #617: a `:db/valid-at` pattern in a rule body binds the query's valid time, +/// not `nil` (which failed the head with INT-022). +#[test] +fn test_rule_body_valid_at_binds_query_valid_time() { + let db = Minigraf::in_memory().unwrap(); + exec(&db, "(transact [[:a :n 1]])"); + exec(&db, "(rule [(vt ?e ?t) [?e :n _] [?e :db/valid-at ?t]])"); + + let rows = result_rows(exec( + &db, + r#"(query [:find ?t :valid-at "2030-01-01" :where (vt ?e ?t)])"#, + )); + assert_eq!(rows, vec![vec![Value::Integer(VALID_AT_2030)]]); + + // Bound first argument: the magic-sets path. + let rows = result_rows(exec( + &db, + r#"(query [:find ?t :valid-at "2030-01-01" :where (vt :a ?t)])"#, + )); + assert_eq!(rows, vec![vec![Value::Integer(VALID_AT_2030)]]); + + // No :valid-at: the current time, as outside a rule. + let rows = result_rows(exec(&db, "(query [:find ?t :where (vt ?e ?t)])")); + assert_eq!(rows.len(), 1, "one row"); + assert!( + matches!(rows[0][0], Value::Integer(t) if t > VALID_AT_2030 / 2), + "current time bound" + ); +} + +/// #617: the same in a recursive rule, evaluated semi-naively. +#[test] +fn test_recursive_rule_body_valid_at_binds_query_valid_time() { + let db = Minigraf::in_memory().unwrap(); + exec(&db, "(transact [[:a :next :b] [:b :next :c]])"); + exec( + &db, + "(rule [(reach ?x ?y) [?x :next ?y] [?x :db/valid-at ?t] [(> ?t 0)]])", + ); + exec(&db, "(rule [(reach ?x ?y) [?x :next ?z] (reach ?z ?y)])"); + + let rows = result_rows(exec( + &db, + r#"(query [:find ?y :valid-at "2030-01-01" :where (reach :a ?y)])"#, + )); + assert_eq!(rows.len(), 2, ":a reaches :b and :c"); +} + +/// #617: a `not` body inside a rule binds the query's valid time, so it +/// excludes the entity whose `:t` equals it. +#[test] +fn test_rule_not_body_valid_at_binds_query_valid_time() { + let db = Minigraf::in_memory().unwrap(); + exec( + &db, + "(transact [[:a :t 1893456000000] [:a :n 1] [:b :t 5] [:b :n 2]])", + ); + exec( + &db, + "(rule [(other ?e ?v) [?e :t ?t] [?e :n ?v] (not [?e :db/valid-at ?t])])", + ); + + let rows = result_rows(exec( + &db, + r#"(query [:find ?v :valid-at "2030-01-01" :where (other ?e ?v)])"#, + )); + assert_eq!(rows, vec![vec![Value::Integer(2)]], "not body excludes :a"); +} + +/// #617: the same for a `not-join` body inside a rule. +#[test] +fn test_rule_not_join_body_valid_at_binds_query_valid_time() { + let db = Minigraf::in_memory().unwrap(); + exec(&db, "(transact [[:a :n 1] [:b :n 2]])"); + exec( + &db, + "(rule [(fresh ?e) [?e :n _] (not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])])", + ); + + let rows = result_rows(exec( + &db, + r#"(query [:find ?e :valid-at "2030-01-01" :where (fresh ?e)])"#, + )); + assert_eq!(rows.len(), 0, "not-join body excludes both"); +} + +/// #617: an `or` branch inside a rule binds the query's valid time, not the +/// current time. +#[test] +fn test_rule_or_branch_valid_at_binds_query_valid_time() { + let db = Minigraf::in_memory().unwrap(); + exec(&db, "(transact [[:a :n 1] [:b :n 2]])"); + exec( + &db, + "(rule [(vt ?e ?t) [?e :n _] (or (and [?e :n 1] [?e :db/valid-at ?t]) (and [?e :n 2] [?e :db/valid-at ?t]))])", + ); + + let rows = result_rows(exec( + &db, + r#"(query [:find ?t :valid-at "2030-01-01" :where (vt ?e ?t)])"#, + )); + assert_eq!( + rows, + vec![vec![Value::Integer(VALID_AT_2030)]; 2], + "one row per entity" + ); +}