From 97f27dfcf4e5684808203086520e82a53aa3ec6f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 21 Oct 2026 01:24:46 +0530 Subject: [PATCH 1/2] feat(engine): rule queries on the streaming engine (#548) Recursive derives each stratum's relations by semi-naive rounds over id rows: round 1 reads every relation in full; later rounds run each rule once per top-level invocation of its stratum (that one Delta, those before Old, after Full); a rule reading its stratum otherwise runs in full every round. Scans read derived rows after the committed and pending ranges, with nil metadata. Rule bodies and the query body plan with the existing Builder, rule invocations read as patterns. Rule queries route to the engine unless the executor must run them (write transaction, :as-of timestamp, a body the engine does not plan). Binary-size gate raised to 1,260 KiB until #551. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_019kY61Y11gcRD91Y6b7jbGT --- .github/workflows/binary-size.yml | 9 +- PHILOSOPHY.md | 6 +- src/query/datalog/evaluator.rs | 28 +-- src/query/datalog/executor.rs | 95 ++++++- src/query/engine/cell.rs | 11 + src/query/engine/mod.rs | 85 ++++++- src/query/engine/plan.rs | 395 ++++++++++++++++++++++++++++-- src/query/engine/recursive.rs | 218 +++++++++++++++++ src/query/engine/relation.rs | 202 +++++++++++++++ src/query/engine/scan.rs | 128 ++++++++++ src/query/engine/tests.rs | 98 +++++++- tests/recursive_engine_test.rs | 355 +++++++++++++++++++++++++++ 12 files changed, 1573 insertions(+), 57 deletions(-) create mode 100644 src/query/engine/recursive.rs create mode 100644 src/query/engine/relation.rs create mode 100644 tests/recursive_engine_test.rs diff --git a/.github/workflows/binary-size.yml b/.github/workflows/binary-size.yml index 643e0b0a1c..526d4bb9ed 100644 --- a/.github/workflows/binary-size.yml +++ b/.github/workflows/binary-size.yml @@ -14,10 +14,11 @@ jobs: name: Check release binary size runs-on: ubuntu-latest env: - # 1230 KiB: 1200 KiB (raised from 1 MiB for #277's structured error codes) plus a - # temporary 30 KiB while the streaming engine and the executor both ship (#473). - # Back to 1200 KiB when #551 removes the executor's query path. See PHILOSOPHY.md §4. - SIZE_LIMIT_BYTES: 1259520 + # 1260 KiB: 1200 KiB (raised from 1 MiB for #277's structured error codes) plus a + # temporary 60 KiB while the streaming engine and the executor both ship (#473; + # 30 KiB more for rule queries on the engine, #548). Back to 1200 KiB when #551 + # removes the executor's query path. See PHILOSOPHY.md §4. + SIZE_LIMIT_BYTES: 1290240 steps: - name: Checkout code uses: actions/checkout@v4 diff --git a/PHILOSOPHY.md b/PHILOSOPHY.md index 4b4ed5441a..bf1fdd350a 100644 --- a/PHILOSOPHY.md +++ b/PHILOSOPHY.md @@ -113,9 +113,9 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s #277's structured error codes — 130 documented codes across 6 categories cannot fit in 1MB even with opt-level="z", LTO, codegen-units=1, and strip=symbols all already applied; see CI's `binary-size.yml` for the - enforced limit). On the v3 branch the gate allows a temporary 30 KiB more - (1,230 KiB) while the streaming engine and the old executor both ship - (#473); it returns to 1,200 KiB when #551 removes the executor's query path + enforced limit). On the v3 branch the gate allows a temporary 60 KiB more + (1,260 KiB) while the streaming engine and the old executor both ship + (#473; rule queries on the engine added 30 KiB, #548); it returns to 1,200 KiB when #551 removes the executor's query path - No runtime dependencies (no JVM, no Python, no Node.js) **Anti-pattern**: Requiring external services, libraries, or runtimes to function. diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index d05b8f26ba..4c815f80ab 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -44,7 +44,7 @@ pub const DEFAULT_MAX_ITERATIONS: usize = 1000; pub const DEFAULT_MAX_DERIVED_FACTS: usize = 1_000_000; /// `INT-020` for a rule query that derived more than `limit` facts (#553). -fn derived_facts_exceeded(limit: usize) -> anyhow::Error { +pub(crate) fn derived_facts_exceeded(limit: usize) -> anyhow::Error { err_coded!( ErrorCode::Int020, format!( @@ -53,6 +53,16 @@ fn derived_facts_exceeded(limit: usize) -> anyhow::Error { ) } +/// `INT-020` for a stratum still deriving facts after `limit` rounds. +pub(crate) fn iterations_exceeded(limit: usize) -> anyhow::Error { + err_coded!( + ErrorCode::Int020, + format!( + "Max iterations ({limit}) exceeded. Possible infinite recursion or cycle in rules." + ) + ) +} + /// Recursive evaluator for Datalog rules using semi-naive evaluation. /// /// # Examples @@ -155,13 +165,7 @@ impl RecursiveEvaluator { iteration += 1; if iteration > self.max_iterations { - return Err(err_coded!( - ErrorCode::Int020, - format!( - "Max iterations ({}) exceeded. Possible infinite recursion or cycle in rules.", - self.max_iterations - ) - )); + return Err(iterations_exceeded(self.max_iterations)); } // Evaluate rules once, get new facts @@ -701,13 +705,7 @@ impl StratifiedEvaluator { loop { pass += 1; if pass > self.max_iterations { - return Err(err_coded!( - ErrorCode::Int020, - format!( - "Max iterations ({}) exceeded. Possible infinite recursion or cycle in rules.", - self.max_iterations - ) - )); + return Err(iterations_exceeded(self.max_iterations)); } // Evaluate positive-only rules via RecursiveEvaluator diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index c0ca92e774..ee1c0a4b4a 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -552,6 +552,13 @@ impl DatalogExecutor { // Check if query uses rules if query.uses_rules() { + // The engine runs the rule queries it plans (#548); reads inside + // a write transaction stay here (#550). + if self.facts_override.is_none() + && let Some(answer) = self.open_rule_query(&query)? + { + return Ok(answer); + } // Use StratifiedEvaluator for queries with rule invocations (handles negation and strata) return self.execute_query_with_rules(query).map(Answer::Result); } @@ -596,6 +603,86 @@ impl DatalogExecutor { self.execute_query_on_executor(query).map(Answer::Result) } + /// A rule query on the streaming engine (#548), or `None` when the + /// engine does not plan it. Its errors come in the executor's order: + /// pseudo-attributes, then the rules, then unknown predicates. + fn open_rule_query(&self, query: &DatalogQuery) -> Result> { + let plan = { + let registry = self + .rules + .read() + .map_err(|_| err_coded!(ErrorCode::Qry009))?; + match crate::query::datalog::magic_sets::rewrite(query, ®istry) { + Some((rewritten, seeds)) => { + let attrs: Vec<&str> = seeds.iter().map(|(_, a, _)| a.as_str()).collect(); + crate::query::engine::plan_rules(query, &rewritten, &attrs) + .map(|plan| (plan, seeds)) + } + None => { + crate::query::engine::plan_rules(query, ®istry, &[]).map(|p| (p, vec![])) + } + } + }; + let Some((plan, seeds)) = plan else { + return Ok(None); + }; + check_per_fact_pseudo_attrs(query)?; + let limits = crate::query::engine::Limits { + max_iterations: crate::query::datalog::evaluator::DEFAULT_MAX_ITERATIONS, + max_derived_facts: self.derived_limit(query), + }; + let snapshot = self.read_snapshot()?; + let open = |plan| -> Result> { + let stream = crate::query::engine::open_rules( + snapshot.clone(), + plan, + &seeds, + self.functions.clone(), + limits, + )?; + if stream.is_some() { + let registry = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + check_udf_predicates(query, ®istry)?; + } + Ok(stream) + }; + // The comparison drains a second stream, so the one returned stays + // unread. + #[cfg(any(test, feature = "test-oracle"))] + { + let again = open(plan.clone()); + if !matches!(again, Ok(None)) { + crate::query::engine::oracle::check( + &again.and_then(|s| { + s.map_or_else(|| Err(err_coded!(ErrorCode::Int049)), |s| s.collect()) + }), + &self + .oracle(snapshot.clone()) + .execute_query_with_rules(query.clone()), + ); + } + } + let Some(stream) = open(plan)? else { + return Ok(None); + }; + #[cfg(test)] + crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); + Ok(Some(Answer::Stream(Box::new(stream)))) + } + + /// The most facts `query`'s rules may derive: a per-query limit replaces + /// the executor's; `:max-results` is a deprecated alias of + /// `:max-derived-facts`, and the lower of the two applies (#553). + fn derived_limit(&self, query: &DatalogQuery) -> usize { + match (query.max_derived_facts, query.max_results) { + (None, None) => self.max_derived_facts, + (a, b) => a.unwrap_or(usize::MAX).min(b.unwrap_or(usize::MAX)), + } + } + /// This executor over `snapshot`, for the engine's oracle (#473 spec §9). #[cfg(any(test, feature = "test-oracle"))] fn oracle(&self, snapshot: Snapshot) -> DatalogExecutor { @@ -803,13 +890,7 @@ impl DatalogExecutor { filtered_storage.load_fact(fact)?; } - // A per-query limit replaces the executor's; `:max-results` is a - // deprecated alias of `:max-derived-facts`, and the lower of the two - // applies (#553). - let effective_max_derived = match (query.max_derived_facts, query.max_results) { - (None, None) => self.max_derived_facts, - (a, b) => a.unwrap_or(usize::MAX).min(b.unwrap_or(usize::MAX)), - }; + let effective_max_derived = self.derived_limit(&query); // Apply magic sets rewriting for demand-driven recursive evaluation. // Returns None for all-free queries — zero overhead path. diff --git a/src/query/engine/cell.rs b/src/query/engine/cell.rs index fd3fd39175..532d57dc1e 100644 --- a/src/query/engine/cell.rs +++ b/src/query/engine/cell.rs @@ -129,6 +129,17 @@ impl JoinKey { } } +impl JoinKey { + /// The key of `cell` as a relation tells facts apart (#548 spec §3.2): + /// as [`JoinKey::group`], except that `-0.0` is not `0.0`. + pub(crate) fn ident(cell: &Cell) -> JoinKey { + match cell { + Cell::Val(Scalar::Float(f)) if !f.is_nan() => JoinKey::Float(f.to_bits()), + cell => JoinKey::group(cell), + } + } +} + /// Whether `a` and `b` are join-equal (#473 spec §5.4). pub(crate) fn join_eq(a: &Cell, b: &Cell, normalise: bool, ctx: &mut Ctx<'_>) -> Result { Ok( diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index 2249708de4..3bbe5e5d94 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -18,6 +18,8 @@ mod join; pub(crate) mod oracle; mod plan; mod project; +mod recursive; +mod relation; mod scan; mod seed; #[cfg(all(test, not(target_arch = "wasm32")))] @@ -27,14 +29,15 @@ mod window; use crate::error::{ErrorCode, err_coded}; use crate::graph::storage::Snapshot; -use crate::graph::types::Value; +use crate::graph::types::{EntityId, Value}; use crate::query::datalog::executor::QueryResult; use crate::query::datalog::functions::FunctionRegistry; use crate::storage::{CommittedReader, KeySource}; use anyhow::Result; use batch::Batch; use ids::IdSpace; -pub(crate) use plan::{Plan, plan}; +pub(crate) use plan::{Plan, plan, plan_rules}; +pub(crate) use recursive::Limits; use std::sync::{Arc, RwLock}; #[cfg(test)] @@ -55,6 +58,8 @@ pub(crate) struct Ctx<'a> { ids: &'a mut IdSpace, /// Predicates for expression clauses. functions: &'a FunctionRegistry, + /// In a rule query, the relations its rules derived (#548). + derived: Option<&'a relation::Relations>, } /// What one operator has done (spec §6.3): rows it read or received, rows @@ -113,6 +118,8 @@ pub(crate) struct Stream { /// row's ids into values in its first pull, and the rows it returns /// later read the same ids again (#547). hold_ids: bool, + /// In a rule query, the relations its rules derived (#548). + relations: Option, closed: bool, } @@ -138,6 +145,73 @@ pub(crate) fn open( None => None, }; let ids = IdSpace::new(keys); + Some(stream(snapshot, ids, plan, functions, None)) +} + +/// Open the rule query `plan` over `snapshot`: derive its relations, with +/// the magic seeds `seeds` as rows, then open its body (#548). `None` as +/// [`open`]; an error from the rules fails the query here. +pub(crate) fn open_rules( + snapshot: Snapshot, + plan: plan::RulesPlan, + seeds: &[(EntityId, String, Value)], + functions: Arc>, + limits: recursive::Limits, +) -> Result> { + let (ids, relations) = { + let keys = match &snapshot.committed { + Some(reader) => match reader.key_source() { + Some(k) => Some(k), + None => return Ok(None), + }, + None => None, + }; + let mut ids = IdSpace::new(keys); + let iids = plan + .evaluated + .attrs + .iter() + .map(|a| ids.iid(keys, a)) + .collect::>>()?; + let mut rels = relation::Relations::new(iids); + for (e, a, v) in seeds { + if let Some(&rel) = plan.evaluated.by_attr.get(a) { + let row = [ + cell::Cell::Eid(ids.eid(keys, e)?), + cell::Cell::of_value(&mut ids, keys, v)?, + ]; + rels.add(rel, row); + } + } + rels.end_round(); + let functions = functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + let reads = recursive::Reads { + snapshot: &snapshot, + keys, + functions: &functions, + }; + recursive::evaluate(&plan, &mut rels, &reads, &mut ids, limits)?; + (ids, rels) + }; + Ok(Some(stream( + snapshot, + ids, + plan.body, + functions, + Some(relations), + ))) +} + +/// The stream of `plan` over `snapshot`. +fn stream( + snapshot: Snapshot, + ids: IdSpace, + plan: Plan, + functions: Arc>, + relations: Option, +) -> Stream { let Plan { source, steps, @@ -146,7 +220,7 @@ pub(crate) fn open( } = plan; let hold_ids = steps.iter().any(|s| matches!(s, plan::Step::Window { .. })); let root = build(source, steps); - Some(Stream { + Stream { snapshot, ids, functions, @@ -155,8 +229,9 @@ pub(crate) fn open( vars, project: Counters::new("Project"), hold_ids, + relations, closed: false, - }) + } } /// The operator tree of a plan's source and steps. @@ -198,6 +273,7 @@ impl Stream { vars: vec!["?x".to_string()], project: Counters::new("Project"), hold_ids: false, + relations: None, closed: false, } } @@ -234,6 +310,7 @@ impl Stream { .and_then(CommittedReader::key_source), ids: &mut self.ids, functions: &functions, + derived: self.relations.as_ref(), }; let Some(batch) = self.root.next_batch(&mut ctx)? else { return Ok(None); diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index a8bc87ef26..cd6b37edb8 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -22,16 +22,21 @@ //! of its entity, as `[e _ _]` does, with the query's valid time as a column. use super::cell::Scalar; +use super::relation::{Derived, Range}; use crate::graph::types::{EntityId, Value}; use crate::query::datalog::aggregate::named_vars; +use crate::query::datalog::evaluator::rule_invocation_to_pattern; use crate::query::datalog::executor::Binders; use crate::query::datalog::matcher::edn_to_entity_id; use crate::query::datalog::optimizer; +use crate::query::datalog::rules::RuleRegistry; +use crate::query::datalog::stratification::DependencyGraph; use crate::query::datalog::types::{ AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, PseudoAttr, UnaryOp, ValidAt, WhereClause, }; use std::collections::{HashMap, HashSet}; +use std::sync::Arc; /// One position of a pattern. #[derive(Debug, Clone)] @@ -111,6 +116,9 @@ pub(crate) struct ScanSpec { pub(crate) valid: Valid, /// Number of slots the scan fills. pub(crate) width: usize, + /// In a rule query, the derived rows read after the stored facts + /// (#548 spec §5.2). + pub(crate) derived: Option, } /// A clause after the scan, in the executor's order. @@ -285,12 +293,13 @@ impl Slots { } } -/// The plan of `query`, or `None` when the engine does not run it yet. -pub(crate) fn plan(query: &DatalogQuery) -> Option { +/// The `:as-of` counter and valid-time test of `query`, or `None` when the +/// engine does not run it: a timestamp is not a key bound, and a slot is +/// resolved before this. +fn temporal(query: &DatalogQuery) -> Option<(Option, Valid)> { let as_of = match &query.as_of { None => None, Some(AsOf::Counter(n)) => Some(*n), - // A timestamp is not a key bound; a slot is resolved before this. Some(AsOf::Timestamp(_) | AsOf::Slot(_)) => return None, }; let valid = match &query.valid_at { @@ -299,7 +308,20 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { Some(ValidAt::AnyValidTime) => Valid::Any, Some(ValidAt::Slot(_)) => return None, }; - if !query.where_clauses.iter().all(|c| { + Some((as_of, valid)) +} + +/// The plan of `query`, or `None` when the engine does not run it yet. +pub(crate) fn plan(query: &DatalogQuery) -> Option { + plan_with(query, None) +} + +/// Add the steps of `clauses`, a `:where` or a rule body, to `b`: the +/// clauses `optimizer::plan` places, in its order, then the `or`s, then the +/// deferred ones. With `first`, that pattern runs first (a rule body's delta, +/// #548 spec §5.3). +fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) -> Option<()> { + if !clauses.iter().all(|c| { matches!( c, WhereClause::Pattern(_) @@ -312,18 +334,21 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { }) { return None; } - let mut b = Builder::new( - Some(Binders::new(&query.where_clauses, Vec::new())), - as_of, - valid, - ); - let (planned, deferred) = optimizer::plan(query.where_clauses.clone()); + let (mut planned, deferred) = optimizer::plan(clauses.to_vec()); + if let Some(p) = first.filter(|_| optimizer::reorder()) + && let Some(i) = planned + .iter() + .position(|(c, _)| matches!(c, WhereClause::Pattern(q) if q == p)) + { + let c = planned.remove(i); + planned.insert(0, c); + } for (c, _) in planned { b.clause(c)?; } // `or` / `or-join` after the clauses the plan places, in text order, as // on the executor (spec §5.1). - for c in &query.where_clauses { + for c in clauses { if matches!(c, WhereClause::Or(_) | WhereClause::OrJoin { .. }) { b.clause(c.clone())?; } @@ -333,6 +358,20 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { for c in sorted(deferred) { b.clause(c)?; } + Some(()) +} + +/// The plan of `query`, whose scans also read the relations `evaluated` +/// when it is a rule query (#548). +fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Option { + let (as_of, valid) = temporal(query)?; + let mut b = Builder::new( + Some(Binders::new(&query.where_clauses, Vec::new())), + as_of, + valid, + evaluated, + ); + clauses(&mut b, &query.where_clauses, None)?; // The parser rejects a variable no clause binds (PRS-080, PRS-022, // PRS-023); one only some `or` branches bind has no slot here. @@ -440,6 +479,275 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { Some(plan) } +/// A rule query on the engine (#548 spec §5): the relations, the rules of +/// each stratum in ascending order, and the query body. +#[derive(Debug, Clone)] +pub(crate) struct RulesPlan { + pub(crate) evaluated: Arc, + /// Each stratum with rules: its relations, and its rules. + pub(crate) strata: Vec<(Vec, Vec)>, + pub(crate) as_of: Option, + pub(crate) valid: Valid, + pub(crate) body: Plan, +} + +/// One rule: its runs in round 1 and the rounds after (spec §5.3). +#[derive(Debug, Clone)] +pub(crate) struct RulePlan { + /// The relation of its head. + pub(crate) rel: usize, + pub(crate) predicate: String, + /// Every read `Full`: round 1, and every round of a naive rule. + pub(crate) full: RuleRun, + /// One run per top-level invocation of its stratum, for rounds after + /// the first; empty for a rule without one, which runs in round 1 only. + pub(crate) deltas: Vec, + pub(crate) naive: bool, +} + +/// A rule body's plan and where its rows hold the head's arguments. +#[derive(Debug, Clone)] +pub(crate) struct RuleRun { + pub(crate) plan: Plan, + pub(crate) entity: HeadArg, + /// `None` for a one-argument head, whose value is `true`. + pub(crate) value: Option, +} + +/// A head argument: a variable (PRS-114 rejects any other). +#[derive(Debug, Clone)] +pub(crate) enum HeadArg { + Slot(usize), + /// A variable the body does not bind (`INT-022` once a row reaches it). + Unbound(String), +} + +/// The plan of a rule query: `query` and every rule it evaluates in +/// `registry` (the magic-set rewrite's, when it ran), whose relations also +/// hold the attributes `seeds` (magic seeds). `None` when the engine does not +/// run it: a body it does not plan, an `:as-of` timestamp, a slot, a +/// stratification error or an invocation of three or more arguments, which +/// the executor reports. +pub(crate) fn plan_rules( + query: &DatalogQuery, + registry: &RuleRegistry, + seeds: &[&str], +) -> Option { + let (as_of, valid) = temporal(query)?; + let strata = DependencyGraph::from_rules(registry).stratify().ok()?; + // Every predicate the query invokes, and those their rules invoke, as + // `StratifiedEvaluator::evaluate` collects them. + let mut preds: Vec = Vec::new(); + for (p, _) in query.get_rule_invocations() { + if !preds.contains(&p) { + preds.push(p); + } + } + let mut i = 0; + while let Some(p) = preds.get(i).cloned() { + for rule in registry.get_rules(&p) { + for c in &rule.body { + for dep in c.rule_invocations() { + if !preds.iter().any(|q| q == dep) { + preds.push(dep.to_string()); + } + } + } + } + i += 1; + } + let mut attrs: Vec = preds.iter().map(|p| format!(":{p}")).collect(); + for a in seeds { + if !attrs.iter().any(|b| b == a) { + attrs.push((*a).to_string()); + } + } + let evaluated = Arc::new(Evaluated { + by_attr: attrs + .iter() + .enumerate() + .map(|(i, a)| (a.clone(), i)) + .collect(), + attrs, + }); + let stratum = |p: &str| strata.get(p).copied().unwrap_or(0); + let top = preds.iter().map(|p| stratum(p)).max().unwrap_or(0); + let mut planned = Vec::new(); + for s in 0..=top { + let in_stratum: HashSet = preds + .iter() + .filter(|p| stratum(p) == s) + .map(|p| format!(":{p}")) + .collect(); + let mut rels = Vec::new(); + let mut rules = Vec::new(); + for (rel, p) in preds.iter().enumerate().filter(|(_, p)| stratum(p) == s) { + rels.push(rel); + for rule in registry.get_rules(p) { + rules.push(rule_plan( + &rule.head, + &rule.body, + rel, + p, + &in_stratum, + as_of, + valid, + &evaluated, + )?); + } + } + if !rels.is_empty() { + planned.push((rels, rules)); + } + } + let mut body_query = query.clone(); + body_query.where_clauses = calls_as_patterns(&query.where_clauses)?; + let body = plan_with(&body_query, Some(evaluated.clone()))?; + Some(RulesPlan { + evaluated, + strata: planned, + as_of, + valid, + body, + }) +} + +/// The plan of one rule of predicate `predicate` (relation `rel`), whose +/// stratum holds the relations of the attributes `stratum`. +#[allow(clippy::too_many_arguments)] +fn rule_plan( + head: &[EdnValue], + body: &[WhereClause], + rel: usize, + predicate: &str, + stratum: &HashSet, + as_of: Option, + valid: Valid, + evaluated: &Arc, +) -> Option { + // The executor reports a head without arguments; a fourth is ignored + // there. + if !(2..=3).contains(&head.len()) { + return None; + } + let naive = naive(body, stratum, false); + let clauses = calls_as_patterns(body)?; + // The top-level invocations of the stratum, in text order. + let own: Vec = body + .iter() + .filter_map(|c| match c { + WhereClause::RuleInvocation { predicate, args } + if stratum.contains(&format!(":{predicate}")) => + { + rule_invocation_to_pattern(predicate, args).ok() + } + _ => None, + }) + .collect(); + let run = |ranges: Vec<(Pattern, Range)>, first: Option<&Pattern>| -> Option { + let mut b = Builder::new(None, as_of, valid, Some(evaluated.clone())); + b.ranges = ranges; + self::clauses(&mut b, &clauses, first)?; + let slots = std::mem::take(&mut b.slots.by_var); + let arg = |e: &EdnValue| match e { + EdnValue::Symbol(v) if v.starts_with('?') => Some(match slots.get(v) { + Some(&s) => HeadArg::Slot(s), + None => HeadArg::Unbound(v.clone()), + }), + _ => None, + }; + Some(RuleRun { + entity: arg(head.get(1)?)?, + value: match head.get(2) { + Some(v) => Some(arg(v)?), + None => None, + }, + plan: b.finish()?, + }) + }; + let full = run(Vec::new(), None)?; + let mut deltas = Vec::new(); + if !naive { + for (i, delta) in own.iter().enumerate() { + let ranges = own + .iter() + .enumerate() + .map(|(j, p)| { + let range = match j.cmp(&i) { + std::cmp::Ordering::Less => Range::Old, + std::cmp::Ordering::Equal => Range::Delta, + std::cmp::Ordering::Greater => Range::Full, + }; + (p.clone(), range) + }) + .collect(); + deltas.push(run(ranges, Some(delta))?); + } + } + Some(RulePlan { + rel, + predicate: predicate.to_string(), + full, + deltas, + naive, + }) +} + +/// Whether a rule body reads a relation of its stratum (the attributes +/// `stratum`) other than through a top-level invocation, outside `not` and +/// `not-join` (spec §5.3): it is then evaluated in full every round. +fn naive(body: &[WhereClause], stratum: &HashSet, in_or: bool) -> bool { + body.iter().any(|c| match c { + WhereClause::Pattern(p) => match &p.attribute { + AttributeSpec::Real(EdnValue::Keyword(a)) => stratum.contains(a), + AttributeSpec::Real(_) => true, + AttributeSpec::Pseudo(pa) => !pa.is_per_fact(), + }, + WhereClause::RuleInvocation { predicate, .. } => { + in_or && stratum.contains(&format!(":{predicate}")) + } + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + branches.iter().any(|b| naive(b, stratum, true)) + } + WhereClause::Not(_) | WhereClause::NotJoin { .. } | WhereClause::Expr { .. } => false, + }) +} + +/// `clauses` with every rule invocation, at any depth, read as its pattern +/// (`rule_invocation_to_pattern`), as the executor matches it. +fn calls_as_patterns(clauses: &[WhereClause]) -> Option> { + let all = |branches: &[Vec]| { + branches + .iter() + .map(|b| calls_as_patterns(b)) + .collect::>>() + }; + clauses + .iter() + .map(|c| { + Some(match c { + WhereClause::RuleInvocation { predicate, args } => { + WhereClause::Pattern(rule_invocation_to_pattern(predicate, args).ok()?) + } + WhereClause::Not(body) => WhereClause::Not(calls_as_patterns(body)?), + WhereClause::NotJoin { join_vars, clauses } => WhereClause::NotJoin { + join_vars: join_vars.clone(), + clauses: calls_as_patterns(clauses)?, + }, + WhereClause::Or(branches) => WhereClause::Or(all(branches)?), + WhereClause::OrJoin { + join_vars, + branches, + } => WhereClause::OrJoin { + join_vars: join_vars.clone(), + branches: all(branches)?, + }, + c => c.clone(), + }) + }) + .collect() +} + /// Builds the operator steps of one clause list: a query's `:where`, or a /// body. struct Builder { @@ -457,10 +765,60 @@ struct Builder { front: Vec, /// The stored-attribute patterns so far, for the `HashJoin` build side. outer_patterns: Vec, + /// In a rule query, the evaluated predicates every scan also reads + /// (#548 spec §5.2); bodies inherit them. + evaluated: Option>, + /// The ranges of this clause list's own patterns that do not read + /// `Full`, taken by the first equal pattern planned (a rule body's + /// top-level invocations, spec §5.3). Equal patterns may take each + /// other's range: a join does not depend on their order. + ranges: Vec<(Pattern, Range)>, +} + +/// The relations of a rule query, by attribute. +#[derive(Debug, Default)] +pub(crate) struct Evaluated { + /// The relation of each evaluated predicate `p`, by `:p`. + pub(crate) by_attr: HashMap, + /// The attributes of the relations, in relation order. + pub(crate) attrs: Vec, +} + +impl Evaluated { + /// What a scan of `attribute` in pattern `q` reads of the relations. + fn derived( + &self, + q: &Pattern, + attribute: &EdnValue, + ranges: &mut Vec<(Pattern, Range)>, + ) -> Option { + match attribute { + EdnValue::Keyword(a) => { + let rel = *self.by_attr.get(a)?; + let range = match ranges.iter().position(|(p, _)| p == q) { + Some(i) => ranges.swap_remove(i).1, + None => Range::Full, + }; + Some(Derived { + rels: vec![rel], + range, + }) + } + _ => Some(Derived { + rels: (0..self.attrs.len()).collect(), + range: Range::Full, + }), + } + } } impl Builder { - fn new(binders: Option, as_of: Option, valid: Valid) -> Self { + fn new( + binders: Option, + as_of: Option, + valid: Valid, + evaluated: Option>, + ) -> Self { Builder { slots: Slots::default(), binders, @@ -470,6 +828,8 @@ impl Builder { steps: Vec::new(), front: Vec::new(), outer_patterns: Vec::new(), + evaluated, + ranges: Vec::new(), } } @@ -523,6 +883,10 @@ impl Builder { if pseudo.is_some() { wants.push((Meta::ValidAt, None)); } + let derived = match &self.evaluated { + Some(e) => e.derived(&q, &attribute, &mut self.ranges), + None => None, + }; let slots = &mut self.slots; let mut metas: Vec<(Meta, usize)> = Vec::new(); if self.source.is_none() { @@ -544,10 +908,12 @@ impl Builder { as_of, valid, width: slots.len(), + derived, })); self.steps.append(&mut self.front); } else { let mut join = join(&scanned, &attribute, slots, &rebind, as_of, valid)?; + join.inner.derived = derived; for &(m, var) in &wants { let local = join.inner.width; join.inner.width += 1; @@ -747,7 +1113,7 @@ impl Builder { }; let (as_of, valid) = (self.as_of, self.valid); if hash { - let mut b = Builder::new(None, as_of, valid); + let mut b = Builder::new(None, as_of, valid, self.evaluated.clone()); let (planned, deferred) = optimizer::plan(body.to_vec()); for (c, _) in planned { b.clause(c)?; @@ -772,7 +1138,7 @@ impl Builder { let plan = Box::new(b.finish()?); return Some((Body::Hashed { plan, keys }, slots)); } - let mut b = Builder::new(None, as_of, valid); + let mut b = Builder::new(None, as_of, valid, self.evaluated.clone()); for (v, outer) in &imports { let s = b.slots.add(self.slots.kind(*outer)); b.slots.by_var.insert(v.clone(), s); @@ -951,6 +1317,7 @@ fn join( as_of, valid, width: local.len(), + derived: None, }, kind: match probe { Some(k) => JoinKind::Probe(k), diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs new file mode 100644 index 0000000000..bc83e2319b --- /dev/null +++ b/src/query/engine/recursive.rs @@ -0,0 +1,218 @@ +//! `Recursive` (#548 spec §5.3): the relations of a rule query, derived +//! stratum by stratum by semi-naive rounds before its body runs. +//! +//! Round 1 runs every rule with every read `Full`. A later round runs each +//! rule once per top-level invocation of its stratum, that invocation read +//! as `Delta`, those before it `Old` and those after it `Full`, so every head +//! it gives uses a fact the last round derived; a naive rule runs in full +//! every round. A head is new when its relation does not know it; new heads +//! are appended when the round ends, and a round that appends nothing ends +//! the stratum. + +use super::cell::{Cell, JoinKey, Scalar}; +use super::ids::IdSpace; +use super::plan::{HeadArg, RuleRun, RulesPlan, ScanSpec, Term}; +use super::relation::Relations; +use super::scan::Scan; +use super::{Ctx, Operator, build}; +use crate::error::{ErrorCode, err_coded}; +use crate::graph::storage::Snapshot; +use crate::query::datalog::evaluator::{derived_facts_exceeded, iterations_exceeded}; +use crate::query::datalog::functions::FunctionRegistry; +use crate::storage::KeySource; +use anyhow::Result; +use std::collections::HashSet; + +/// The limits of one rule query (spec §3.5). +#[derive(Debug, Clone, Copy)] +pub(crate) struct Limits { + pub(crate) max_iterations: usize, + /// Facts the rules may derive in total; stored facts and magic seeds do + /// not count. + pub(crate) max_derived_facts: usize, +} + +/// What every body run reads. +pub(crate) struct Reads<'a> { + pub(crate) snapshot: &'a Snapshot, + pub(crate) keys: Option<&'a dyn KeySource>, + pub(crate) functions: &'a FunctionRegistry, +} + +/// Derive every relation of `plan` into `rels`. +pub(crate) fn evaluate( + plan: &RulesPlan, + rels: &mut Relations, + reads: &Reads<'_>, + ids: &mut IdSpace, + limits: Limits, +) -> Result<()> { + let mut derived = 0usize; + for (stratum_rels, rules) in &plan.strata { + for &rel in stratum_rels { + know_stored(plan, rel, rels, reads, ids)?; + } + let mut round = 0; + loop { + round += 1; + if round > limits.max_iterations { + return Err(iterations_exceeded(limits.max_iterations)); + } + for rule in rules { + let runs: &[RuleRun] = if round == 1 || rule.naive { + std::slice::from_ref(&rule.full) + } else { + &rule.deltas + }; + for run in runs { + for row in heads(run, &rule.predicate, rule.rel, rels, reads, ids)? { + if rels.add(rule.rel, row) { + derived += 1; + if derived > limits.max_derived_facts { + return Err(derived_facts_exceeded(limits.max_derived_facts)); + } + } + } + } + } + if !rels.end_round() { + break; + } + } + } + Ok(()) +} + +/// Record the stored facts of relation `rel`, so that a head equal to one +/// is not derived (spec §5.1). +fn know_stored( + plan: &RulesPlan, + rel: usize, + rels: &mut Relations, + reads: &Reads<'_>, + ids: &mut IdSpace, +) -> Result<()> { + let Some(attr) = plan.evaluated.attrs.get(rel) else { + return Ok(()); + }; + let mut scan = Scan::new(ScanSpec { + e: Term::Bind(0), + a: Term::Const(attr.clone()), + v: Term::Bind(1), + meta: Vec::new(), + as_of: plan.as_of, + valid: plan.valid, + width: 2, + derived: None, + }); + let mut stored = Vec::new(); + { + let mut ctx = ctx(reads, ids, None); + while let Some(batch) = scan.next_batch(&mut ctx)? { + let (Some(es), Some(vs)) = (batch.cols.first(), batch.cols.get(1)) else { + continue; + }; + stored.extend(es.iter().cloned().zip(vs.iter().cloned())); + } + } + ids.end_pull(); + for (e, v) in stored { + rels.know(rel, &[e, v]); + } + Ok(()) +} + +/// The heads one run of a rule's body gives that `rels` does not know yet, +/// each once. +fn heads( + run: &RuleRun, + predicate: &str, + rel: usize, + rels: &Relations, + reads: &Reads<'_>, + ids: &mut IdSpace, +) -> Result> { + let mut out = Vec::new(); + let mut seen: HashSet<[JoinKey; 2]> = HashSet::new(); + { + let mut ctx = ctx(reads, ids, Some(rels)); + let mut root = build(run.plan.source.clone(), run.plan.steps.clone()); + while let Some(batch) = root.next_batch(&mut ctx)? { + for i in 0..batch.len { + let cell = |slot: usize| batch.cols.get(slot).and_then(|c| c.get(i)); + let row = [ + entity(&run.entity, predicate, cell, &mut ctx)?, + value(run.value.as_ref(), cell)?, + ]; + if !rels.known(rel, &row) + && seen.insert([JoinKey::ident(&row[0]), JoinKey::ident(&row[1])]) + { + out.push(row); + } + } + } + root.close(); + } + ids.end_pull(); + Ok(out) +} + +fn ctx<'a>(reads: &Reads<'a>, ids: &'a mut IdSpace, derived: Option<&'a Relations>) -> Ctx<'a> { + Ctx { + snapshot: reads.snapshot, + keys: reads.keys, + ids, + functions: reads.functions, + derived, + } +} + +/// The head's entity cell (spec §5.3): an entity, or the entity a keyword +/// names; anything else is `QRY-013`. +fn entity<'c>( + arg: &HeadArg, + predicate: &str, + cell: impl Fn(usize) -> Option<&'c Cell>, + ctx: &mut Ctx<'_>, +) -> Result { + let kind = match arg { + HeadArg::Unbound(v) => return Err(unbound(v)), + HeadArg::Slot(s) => match cell(*s) { + Some(Cell::Eid(e)) => return Ok(Cell::Eid(*e)), + Some(Cell::Iid(i)) => return Ok(Cell::Eid(ctx.ids.keyword_eid(ctx.keys, *i)?)), + Some(Cell::Val(v)) => match v { + // The executor reads a `nil` back as a symbol. + Scalar::Null => "symbol", + Scalar::Bool(_) => "Boolean", + Scalar::Int(_) => "Integer", + Scalar::Float(_) => "Float", + Scalar::Str(_) | Scalar::Long(_) => "String", + }, + None => return Err(unbound("?")), + }, + }; + Err(err_coded!(ErrorCode::Qry013, predicate, kind)) +} + +/// The head's value cell: any value but `nil`, which the executor cannot +/// read back (`INT-022`); `true` for a one-argument head. +fn value<'c>(arg: Option<&HeadArg>, cell: impl Fn(usize) -> Option<&'c Cell>) -> Result { + match arg { + None => Ok(Cell::Val(Scalar::Bool(true))), + Some(HeadArg::Unbound(v)) => Err(unbound(v)), + Some(HeadArg::Slot(s)) => match cell(*s) { + Some(Cell::Val(Scalar::Null)) | None => Err(err_coded!( + ErrorCode::Int022, + "Failed to convert value: nil" + )), + Some(c) => Ok(c.clone()), + }, + } +} + +fn unbound(var: &str) -> anyhow::Error { + err_coded!( + ErrorCode::Int022, + format!("Unbound variable in rule head: {var}") + ) +} diff --git a/src/query/engine/relation.rs b/src/query/engine/relation.rs new file mode 100644 index 0000000000..41981c22d9 --- /dev/null +++ b/src/query/engine/relation.rs @@ -0,0 +1,202 @@ +//! The relations of a rule query (#548 spec §5.1): per evaluated predicate, +//! the facts its rules derive, as rows of two cells (entity, value). +//! +//! Rows are appended at the end of each round, so the relation as of a +//! round is a prefix of its rows and the round's delta a range of them: +//! `Old` is `..start`, `Delta` is `start..end`, `Full` is `..end`. A row is +//! new when no stored fact and no earlier row has the same entity and value +//! (spec §3.2), as [`JoinKey::ident`] compares cells. + +use super::cell::{Cell, JoinKey}; +use std::collections::{HashMap, HashSet}; + +/// Which rows of a relation a scan reads (spec §5.2). +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum Range { + /// Stored facts and every derived row so far. + Full, + /// Stored facts and the rows derived before the last round. + Old, + /// The rows the last round derived, and no stored fact. + Delta, +} + +/// The derived rows a scan reads after the stored facts: those of the +/// relations `rels` (indexes into [`Relations`]), in `range`. +#[derive(Debug, Clone)] +pub(crate) struct Derived { + pub(crate) rels: Vec, + pub(crate) range: Range, +} + +pub(crate) struct Relations { + rels: Vec, +} + +struct Rel { + /// The id of the attribute `:p` in the query's id space. + iid: u64, + rows: Vec<[Cell; 2]>, + /// Stored facts and rows, and the rows of the round under way. + ident: HashSet<[JoinKey; 2]>, + /// Row positions by entity id. + by_entity: HashMap>, + /// The rows of the round under way, appended at its end. + next: Vec<[Cell; 2]>, + start: usize, + end: usize, +} + +impl Relations { + /// Empty relations, one per attribute id in `iids`. + pub(crate) fn new(iids: impl IntoIterator) -> Self { + Relations { + rels: iids + .into_iter() + .map(|iid| Rel { + iid, + rows: Vec::new(), + ident: HashSet::new(), + by_entity: HashMap::new(), + next: Vec::new(), + start: 0, + end: 0, + }) + .collect(), + } + } + + /// The attribute id of relation `rel`. + pub(crate) fn iid(&self, rel: usize) -> Option { + self.rels.get(rel).map(|r| r.iid) + } + + /// Record a stored fact of relation `rel`: a row equal to it is not new. + pub(crate) fn know(&mut self, rel: usize, row: &[Cell; 2]) { + if let Some(r) = self.rels.get_mut(rel) { + r.ident.insert(key(row)); + } + } + + /// Whether `row` is already a stored fact or a row of `rel`, this + /// round's included. + pub(crate) fn known(&self, rel: usize, row: &[Cell; 2]) -> bool { + self.rels + .get(rel) + .is_none_or(|r| r.ident.contains(&key(row))) + } + + /// Add `row` to `rel` at the end of the round, unless it is known. + /// Returns whether it was new. + pub(crate) fn add(&mut self, rel: usize, row: [Cell; 2]) -> bool { + let Some(r) = self.rels.get_mut(rel) else { + return false; + }; + if !r.ident.insert(key(&row)) { + return false; + } + r.next.push(row); + true + } + + /// End a round: append every relation's new rows, which become the + /// delta. Returns whether any row was appended. + pub(crate) fn end_round(&mut self) -> bool { + let mut any = false; + for r in &mut self.rels { + r.start = r.end; + any |= !r.next.is_empty(); + for row in r.next.drain(..) { + if let Cell::Eid(e) = row[0] { + r.by_entity.entry(e).or_default().push(r.rows.len()); + } + r.rows.push(row); + } + r.end = r.rows.len(); + } + any + } + + /// The positions of `rel`'s rows in `range`. + pub(crate) fn span(&self, rel: usize, range: Range) -> std::ops::Range { + let Some(r) = self.rels.get(rel) else { + return 0..0; + }; + match range { + Range::Full => 0..r.end, + Range::Old => 0..r.start, + Range::Delta => r.start..r.end, + } + } + + /// The positions of `rel`'s rows whose entity is `eid`, in any range. + pub(crate) fn of_entity(&self, rel: usize, eid: u64) -> &[usize] { + self.rels + .get(rel) + .and_then(|r| r.by_entity.get(&eid)) + .map_or(&[], Vec::as_slice) + } + + pub(crate) fn row(&self, rel: usize, at: usize) -> Option<&[Cell; 2]> { + self.rels.get(rel).and_then(|r| r.rows.get(at)) + } + + /// Rows held, for tests. + #[cfg(test)] + pub(crate) fn len(&self, rel: usize) -> usize { + self.rels.get(rel).map_or(0, |r| r.rows.len()) + } +} + +fn key(row: &[Cell; 2]) -> [JoinKey; 2] { + [JoinKey::ident(&row[0]), JoinKey::ident(&row[1])] +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::query::engine::cell::Scalar; + + fn row(e: u64, v: Scalar) -> [Cell; 2] { + [Cell::Eid(e), Cell::Val(v)] + } + + /// Spec §3.2: kinds distinct, `-0.0` distinct from `0.0`, one NaN, a + /// keyword distinct from the entity it names. + #[test] + fn identity_of_rows() { + let mut r = Relations::new([7]); + assert!(r.add(0, row(1, Scalar::Float(0.0)))); + assert!(r.add(0, row(1, Scalar::Float(-0.0))), "-0.0 is new"); + assert!(!r.add(0, row(1, Scalar::Float(0.0))), "0.0 again"); + assert!(r.add(0, row(1, Scalar::Float(f64::NAN)))); + assert!(!r.add(0, row(1, Scalar::Float(-f64::NAN))), "one NaN"); + assert!(r.add(0, row(1, Scalar::Int(0))), "integer is not float"); + assert!(r.add(0, [Cell::Eid(1), Cell::Iid(5)])); + assert!(r.add(0, [Cell::Eid(1), Cell::Eid(5)]), "ref is not keyword"); + r.know(0, &row(2, Scalar::Bool(true))); + assert!(!r.add(0, row(2, Scalar::Bool(true))), "stored fact"); + assert!(r.known(0, &row(1, Scalar::Int(0)))); + } + + #[test] + fn rounds_give_old_delta_and_full() { + let mut r = Relations::new([7]); + r.add(0, row(1, Scalar::Int(1))); + assert_eq!(r.span(0, Range::Full), 0..0, "not before the round ends"); + assert!(r.end_round()); + assert_eq!(r.span(0, Range::Delta), 0..1); + r.add(0, row(1, Scalar::Int(2))); + r.add(0, row(2, Scalar::Int(3))); + assert!(r.end_round()); + assert_eq!(r.span(0, Range::Old), 0..1); + assert_eq!(r.span(0, Range::Delta), 1..3); + assert_eq!(r.span(0, Range::Full), 0..3); + assert_eq!(r.of_entity(0, 1), &[0, 1]); + assert!(!r.end_round()); + assert_eq!(r.span(0, Range::Delta), 3..3); + assert_eq!(r.span(0, Range::Old), 0..3); + assert_eq!(r.len(0), 3); + assert_eq!(r.iid(0), Some(7)); + } +} diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 779a71eb67..57d6123780 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -5,10 +5,15 @@ //! pending records alone, and a triple without one by its committed keys //! (#379). `Scan` reads the committed ranges first, leaving out the triples a //! pending record decides (the shadow set), then the pending range. +//! +//! In a rule query, a scan then reads the rows of the relations its pattern +//! names (#548 spec §5.2); a `Delta` read reads those rows only. A derived +//! row is visible at every time and has no metadata (`nil`). use super::batch::Batch; use super::cell::{Cell, Scalar}; use super::plan::{Meta, ScanSpec, Term, Valid, ValueConst, names}; +use super::relation::Range as Rows; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::storage::PendingResume; use crate::graph::types::{EntityId, Fact, Value}; @@ -36,9 +41,23 @@ enum State { Start, Committed(Committed), Pending(Option), + Derived(Derived), Done, } +/// Where the read of derived rows is. +#[derive(Default)] +struct Derived { + /// The relation read, as an index into the spec's. + k: usize, + /// The next position: in the relation's rows, or in its rows of the + /// entity read. + at: usize, + /// The entity read (a probe's, or a constant's) and the cell of an + /// exact value constant, resolved on the first pull. + resolved: Option<(Option, Option)>, +} + /// The committed half of the read. struct Committed { /// Key ranges as `(index, prefix)`, read in turn from `next`. @@ -117,6 +136,15 @@ impl Operator for Scan { loop { let mut batch = Batch::new(self.spec.width); match &mut self.state { + State::Start + if self + .spec + .derived + .as_ref() + .is_some_and(|d| d.range == Rows::Delta) => + { + self.state = State::Derived(Derived::default()); + } State::Start => { if self.consts.is_none() && let Some(keys) = ctx.keys @@ -224,6 +252,15 @@ impl Operator for Scan { row.iter_mut().for_each(|c| *c = None); } if !more { + self.state = if self.spec.derived.is_some() { + State::Derived(Derived::default()) + } else { + State::Done + }; + } + } + State::Derived(d) => { + if !derived(&self.spec, self.probe.as_ref(), d, &mut batch, ctx)? { self.state = State::Done; } } @@ -253,6 +290,97 @@ impl Operator for Scan { } } +/// Read derived rows of `spec` into `batch` until it is full; `false` once +/// every relation has been read. +fn derived( + spec: &ScanSpec, + probe: Option<&(EntityId, Option)>, + d: &mut Derived, + batch: &mut Batch, + ctx: &mut Ctx<'_>, +) -> Result { + let (Some(read), Some(rels)) = (&spec.derived, ctx.derived) else { + return Ok(false); + }; + let (target, exact) = match &d.resolved { + Some(r) => r.clone(), + None => { + let target = match (probe, &spec.e) { + (Some((u, _)), _) | (None, Term::Const(u)) => Some(ctx.ids.eid(ctx.keys, u)?), + _ => None, + }; + let exact = match &spec.v { + Term::Const(ValueConst::Exact(v)) => Some(Cell::of_value(ctx.ids, ctx.keys, v)?), + _ => None, + }; + d.resolved = Some((target, exact.clone())); + (target, exact) + } + }; + let valid = valid_at(spec.valid, ctx); + let mut row = vec![None; spec.width]; + while batch.len < BATCH_ROWS { + let Some(&rel) = read.rels.get(d.k) else { + return Ok(false); + }; + let span = rels.span(rel, read.range); + let pos = match target { + Some(e) => rels.of_entity(rel, e).get(d.at).copied(), + None => Some(span.start + d.at).filter(|p| *p < span.end), + }; + let Some(pos) = pos else { + d.k += 1; + d.at = 0; + continue; + }; + d.at += 1; + let (Some(r), Some(iid)) = (rels.row(rel, pos), rels.iid(rel)) else { + continue; + }; + if !span.contains(&pos) { + continue; + } + let keeps = match (&spec.v, &exact) { + (_, Some(c)) => r[1] == *c, + (Term::Const(c), None) => cell_matches(c, &r[1], ctx)?, + _ => true, + }; + if keeps + && fill(&spec.e, &mut row, || Ok(r[0].clone()))? + && fill(&spec.a, &mut row, || Ok(Cell::Iid(iid)))? + && fill(&spec.v, &mut row, || Ok(r[1].clone()))? + { + for &(m, slot) in &spec.meta { + set( + &mut row, + slot, + if m == Meta::ValidAt { valid } else { None }, + ); + } + // `set` gives `nil` for `None`; the valid time under + // `:any-valid-time` is `nil` too. + batch.push(&mut row); + } + row.iter_mut().for_each(|c| *c = None); + } + Ok(true) +} + +/// Whether the derived cell `cell` matches the value constant `c`, as +/// [`ValueConst::matches`] matches its value. +fn cell_matches(c: &ValueConst, cell: &Cell, ctx: &mut Ctx<'_>) -> Result { + Ok(match (c, cell) { + (ValueConst::Exact(v), cell) => Cell::of_value(ctx.ids, ctx.keys, v)? == *cell, + (ValueConst::Keyword(k, _), Cell::Iid(i)) => *ctx.ids.name(ctx.keys, *i)? == **k, + (ValueConst::Keyword(_, u) | ValueConst::Uuid(u), Cell::Eid(e)) => { + ctx.ids.uuid(ctx.keys, *e)? == *u + } + (ValueConst::Uuid(u), Cell::Iid(i)) => names(&ctx.ids.name(ctx.keys, *i)?, u), + (ValueConst::Float(f), Cell::Val(Scalar::Float(ff))) => (f - ff).abs() < f64::EPSILON, + _ => false, + }) +} + /// Fill a metadata slot: an integer, or `nil` for the valid time under /// `:any-valid-time`. fn set(row: &mut [Option], slot: usize, n: Option) { diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 6904c7bdab..8823496bd6 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -1020,8 +1020,8 @@ fn planner_chooses_the_body_form() { assert_eq!(forms(constant), ["correlated"]); } -/// Which negations the engine runs (#546): every `not` / `not-join` -/// without a rule invocation. +/// Which negations the engine runs (#546): every `not` / `not-join`, with +/// a rule invocation too since rule queries run here (#548). #[test] fn negation_routing() { let db = Minigraf::in_memory().unwrap(); @@ -1032,14 +1032,10 @@ fn negation_routing() { "(query [:find ?e :where [?e :person/name ?n] (not [?e :person/ok true])])", "(query [:find ?e :where [?e :person/name ?n] (not [:p1 :person/ok true])])", "(query [:find ?e :where [?e :person/age ?a] [(+ ?a 1) ?b] (not-join [?b] [?f :person/age ?b])])", + "(query [:find ?e :where [?e :person/name ?n] (not (okay ?e))])", ] { rows(&db, q); } - for q in ["(query [:find ?e :where [?e :person/name ?n] (not (okay ?e))])"] { - let before = runs(); - db.execute(q).unwrap(); - assert_eq!(runs(), before, "query stayed on the executor"); - } } /// `not` filters and never deduplicates (spec §3.1): rows with the same @@ -1278,8 +1274,8 @@ fn disjunction_matches_executor() { } /// Which disjunctions the engine runs (#546 PR 2): `or` / `or-join` whose -/// branches hold patterns, expressions and `not`s; a rule invocation, a -/// nested `or`, a predicate the registry may lack, an `or` whose branches +/// branches hold patterns, expressions, `not`s and rule invocations (#548); +/// a nested `or`, a predicate the registry may lack, an `or` whose branches /// bind their own sources' metadata, and a branch `not` reading what only /// the branch's expression binds stay on the executor (decision 11). #[test] @@ -1293,11 +1289,11 @@ fn disjunction_routing() { "(query [:find ?e :where (or [?e :person/ok true] [?e :person/age 21])])", "(query [:find ?e :where [?e :person/name ?n] (or (and [?e :person/ok true] (not [?e :person/age 21])) [?e :person/age 22])])", "(query [:find ?e :any-valid-time :where [?e :person/name ?n] (or-join [?e] (and [?f :person/age ?a] [?f :db/tx-count ?t]) [?e :person/ok true])])", + "(query [:find ?e :where [?e :person/name ?n] (or (okay ?e) [?e :person/age 21])])", ] { rows(&db, q); } for q in [ - "(query [:find ?e :where [?e :person/name ?n] (or (okay ?e) [?e :person/age 21])])", "(query [:find ?e :where [?e :person/name ?n] (or (or [?e :person/ok true] [?e :person/age 22]) [?e :person/age 21])])", "(query [:find ?e :where [?e :person/age ?a] (or (and [?e :person/ok true] [(no-such-pred? ?a)]) [?e :person/age 21])])", "(query [:find ?e :any-valid-time :where [?e :person/name ?n] (or (and [?e :person/age ?a] [?e :db/tx-count ?t]) (and [?e :person/score ?a] [?e :db/tx-id ?t]))])", @@ -1774,3 +1770,85 @@ fn window_routing() { 0 ); } + +/// Which rule queries the engine runs (#548 spec §5.5): those whose body and +/// every evaluated rule body it plans, outside a write transaction and +/// without an `:as-of` timestamp. +#[test] +fn rule_query_routing() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :e :b] [:b :e :c] [:c :n 1]])") + .unwrap(); + for rule in [ + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(reach ?x ?z) [?x :e ?y] (reach ?y ?z)])", + "(rule [(one ?x ?v) [(+ 0 1) ?v] [(+ 0 2) ?x]])", + "(rule [(deep ?x ?y) [?x :e ?y] (or (or [?y :e ?x] [?y :n 1]) [?x :n 2])])", + ] { + db.execute(rule).unwrap(); + } + assert_eq!(rows(&db, "(query [:find ?x ?y :where (reach ?x ?y)])"), 3); + assert_eq!(rows(&db, "(query [:find ?y :where (reach :a ?y)])"), 2); + assert_eq!( + rows( + &db, + "(query [:find ?x :where [?x :e ?y] (not-join [?y] (reach ?y ?z))])" + ), + 1 + ); + for q in [ + "(query [:find ?x ?y :as-of \"2020-01-01T00:00:00Z\" :where (reach ?x ?y)])", + "(query [:find ?x ?v :where (one ?x ?v)])", + "(query [:find ?x :where (deep ?x ?y)])", + "(query [:find ?x :where (reach ?x ?y ?z)])", + ] { + let before = runs(); + let _ = db.execute(q); + assert_eq!(runs(), before, "query stayed on the executor"); + } + let before = runs(); + let mut tx = db.begin_write().unwrap(); + tx.execute("(transact [[:c :e :d]])").unwrap(); + tx.execute("(query [:find ?x ?y :where (reach ?x ?y)])") + .unwrap(); + tx.rollback(); + assert_eq!(runs(), before, "a write transaction reads on the executor"); +} + +/// The relations a rule query derives are read after the committed and +/// pending facts, in batches, on every scan kind (#548 spec §5.2). +#[test] +fn rule_queries_read_derived_rows_in_batches() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("rules.graph")).unwrap(); + // A chain of 60 nodes: 1,770 reach facts, more than one batch. + let edges: String = (0..59) + .map(|i| format!("[:n{i} :e :n{}]", i + 1)) + .collect::>() + .join(" "); + db.execute(&format!("(transact [{edges}])")).unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :e ?y]])").unwrap(); + db.execute("(rule [(reach ?x ?z) (reach ?x ?y) [?y :e ?z]])") + .unwrap(); + for _ in 0..2 { + assert_eq!( + rows(&db, "(query [:find ?x ?y :where (reach ?x ?y)])"), + 1770 + ); + assert_eq!(rows(&db, "(query [:find ?y :where (reach :n0 ?y)])"), 59); + assert_eq!( + rows(&db, "(query [:find ?x ?a :where [?x :e :n5] [?x ?a ?y]])"), + 1, + "no rule invoked: no derived rows" + ); + assert_eq!( + rows( + &db, + "(query [:find ?x ?y :where [?x :reach ?y] (reach ?x ?y)])" + ), + 1770, + "a pattern of the relation" + ); + db.checkpoint().unwrap(); + } +} diff --git a/tests/recursive_engine_test.rs b/tests/recursive_engine_test.rs new file mode 100644 index 0000000000..ce977eb4ca --- /dev/null +++ b/tests/recursive_engine_test.rs @@ -0,0 +1,355 @@ +//! Rule queries on the streaming engine (#548 spec §7). Each query runs on +//! an in-memory database, on a file with its facts pending, and on the same +//! file after a checkpoint; under the `test-oracle` feature the executor +//! runs it too and must agree. +// +// File-backed (Minigraf::open, tempfile): native only, like the other file tests. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult, Value}; + +/// The databases a test reads: in memory, a file, and the file again once +/// checkpointed. +struct Dbs { + mem: Minigraf, + file: Minigraf, + _dir: tempfile::TempDir, +} + +impl Dbs { + fn new(commands: &[&str]) -> Dbs { + let dir = tempfile::tempdir().unwrap(); + let mem = Minigraf::in_memory().unwrap(); + let file = Minigraf::open(dir.path().join("rules.graph")).unwrap(); + for db in [&mem, &file] { + for c in commands { + db.execute(c).expect("setup command"); + } + } + Dbs { + mem, + file, + _dir: dir, + } + } + + /// The rows of `query`, the same on every database. + fn rows(&self, query: &str) -> Vec> { + let mut all = Vec::new(); + for db in [&self.mem, &self.file] { + all.push(sorted(rows(db, query))); + } + self.file.checkpoint().unwrap(); + all.push(sorted(rows(&self.file, query))); + assert!(all[0] == all[1], "in memory and pending agree"); + assert!(all[1] == all[2], "pending and committed agree"); + all.swap_remove(0) + } + + fn count(&self, query: &str) -> usize { + self.rows(query).len() + } + + /// The error code of `query`, the same on every database. + fn err(&self, query: &str) -> String { + let codes: Vec = [&self.mem, &self.file] + .iter() + .map(|db| match db.execute(query) { + Ok(_) => panic!("expected an error"), + Err(e) => e.code().to_string(), + }) + .collect(); + assert_eq!(codes[0], codes[1], "same error on both databases"); + codes[0].clone() + } +} + +fn rows(db: &Minigraf, query: &str) -> Vec> { + match db.execute(query).expect("query") { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected query results"), + } +} + +fn sorted(mut rows: Vec>) -> Vec> { + rows.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal)); + rows +} + +const CHAIN: &str = "(transact [[:a :e :b] [:b :e :c] [:c :e :d]])"; + +#[test] +fn linear_and_non_linear_transitive_closure() { + let db = Dbs::new(&[ + CHAIN, + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(reach ?x ?z) [?x :e ?y] (reach ?y ?z)])", + "(rule [(tc ?x ?y) [?x :e ?y]])", + "(rule [(tc ?x ?z) (tc ?x ?y) (tc ?y ?z)])", + ]); + assert_eq!(db.count("(query [:find ?x ?y :where (reach ?x ?y)])"), 6); + assert_eq!(db.count("(query [:find ?x ?y :where (tc ?x ?y)])"), 6); + assert_eq!( + db.count("(query [:find ?x ?y :where (reach ?x ?y) (tc ?x ?y)])"), + 6, + "both relations in one body" + ); +} + +#[test] +fn mutual_recursion() { + let db = Dbs::new(&[ + "(transact [[:n0 :next :n1] [:n1 :next :n2] [:n2 :next :n3] [:n3 :next :n4] [:n4 :next :n5]])", + "(rule [(odd ?x ?y) [?x :next ?y]])", + "(rule [(odd ?x ?z) (even ?x ?y) [?y :next ?z]])", + "(rule [(even ?x ?z) (odd ?x ?y) [?y :next ?z]])", + ]); + assert_eq!(db.count("(query [:find ?x ?y :where (odd ?x ?y)])"), 9); + assert_eq!(db.count("(query [:find ?x ?y :where (even ?x ?y)])"), 6); +} + +/// #633's cases: a stratum whose `not` and `or` rules recurse. +#[test] +fn recursion_through_not_and_or_rules() { + let db = Dbs::new(&[ + CHAIN, + "(transact [[:c :blocked true] [:b :f :x]])", + "(rule [(r ?x ?y) [?x :e ?y]])", + "(rule [(r ?x ?z) (r ?x ?y) [?y :e ?z] (not [?z :blocked true])])", + "(rule [(s ?x ?y) (or [?x :e ?y] [?x :f ?y])])", + "(rule [(s ?x ?z) (s ?x ?y) (or [?y :e ?z] [?y :f ?z])])", + // Mutual recursion through a mixed rule. + "(rule [(m ?x ?y) [?x :e ?y]])", + "(rule [(m ?x ?z) (n ?x ?y) [?y :e ?z]])", + "(rule [(n ?x ?y) (m ?x ?y) (not [?y :blocked true])])", + ]); + // a-b, b-c, c-d and b-d; a-c and a-d go through the blocked c. + assert_eq!(db.count("(query [:find ?x ?y :where (r ?x ?y)])"), 4); + // Every pair of the chain, and a-x, b-x. + assert_eq!(db.count("(query [:find ?x ?y :where (s ?x ?y)])"), 8); + // m: the three edges, a-c (n a-b, b-e-c) and b-d? n b-c is blocked: no. + assert_eq!(db.count("(query [:find ?x ?y :where (m ?x ?y)])"), 4); +} + +/// Rules that read their own stratum other than through a top-level +/// invocation run in full every round (spec §5.3). +#[test] +fn naive_rules() { + let db = Dbs::new(&[ + CHAIN, + "(transact [[:b :f :z]])", + "(rule [(o ?x ?y) [?x :e ?y]])", + "(rule [(o ?x ?z) [?x :e ?y] (or (o ?y ?z) [?y :f ?z])])", + "(rule [(p ?x ?y) [?x :e ?y]])", + "(rule [(p ?x ?z) [?x :e ?y] [?y :p ?z]])", + "(rule [(q ?x ?y) [?x :e ?y]])", + "(rule [(q ?x ?z) [?x :e ?y] [?y ?a ?z] [(= ?a :q)]])", + ]); + // The chain's 6 pairs, and a-z through b's :f. + assert_eq!(db.count("(query [:find ?x ?y :where (o ?x ?y)])"), 7); + assert_eq!(db.count("(query [:find ?x ?y :where (p ?x ?y)])"), 6); + assert_eq!(db.count("(query [:find ?x ?y :where (q ?x ?y)])"), 6); +} + +/// Derived facts are visible as stored ones (spec §3.1). +#[test] +fn merged_visibility() { + let db = Dbs::new(&[ + CHAIN, + "(transact [[:x :reach :y]])", + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(reach ?x ?z) [?x :e ?y] (reach ?y ?z)])", + ]); + assert_eq!( + db.count("(query [:find ?x ?y :where (reach ?x ?y)])"), + 7, + "the stored :reach fact too" + ); + let attrs: std::collections::BTreeSet = db + .rows("(query [:find ?a :where (reach :a ?y) [:a ?a ?v]])") + .into_iter() + .filter_map(|r| match r.first() { + Some(Value::Keyword(k)) => Some(k.clone()), + _ => None, + }) + .collect(); + assert!( + attrs.contains(":e") && attrs.contains(":reach") && attrs.len() == 3, + ":e, the derived :reach and the magic seed's attribute" + ); + assert_eq!( + db.count("(query [:find ?y :where (reach ?x ?y) [?x :reach ?y]])"), + 7, + "a pattern of the relation reads the derived facts" + ); + // With a literal, the magic-set rewrite runs: only a's reach is derived. + assert_eq!(db.count("(query [:find ?y :where (reach :a ?y)])"), 3); + assert_eq!( + db.count("(query [:find ?y :where (reach :b ?y) (not [:x :reach ?y])])"), + 2 + ); +} + +/// Relations are sets, values compared as stored (spec §3.2). +#[test] +fn identity_of_derived_facts() { + let alice = uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":alice"); + let long = "a long string kept in a value page ".repeat(3); + let db = Dbs::new(&[ + &format!( + r#"(transact [[:k :kw :alice] [:k :rf #uuid "{alice}"] [:k :f 0.0] [:k :g -0.0] + [:k :s "{long}"] [:k :t "{long}"] [:k :p 1]])"# + ), + "(rule [(v ?x ?v) [?x :kw ?v]])", + "(rule [(v ?x ?v) [?x :rf ?v]])", + "(rule [(fl ?x ?v) [?x :f ?v]])", + "(rule [(fl ?x ?v) [?x :g ?v]])", + "(rule [(st ?x ?v) [?x :s ?v]])", + "(rule [(st ?x ?v) [?x :t ?v]])", + "(rule [(p ?x ?v) [?x :e ?v]])", + "(rule [(p ?x ?one) [?x :kw ?v] [(+ 0 1) ?one]])", + ]); + assert_eq!( + db.count("(query [:find ?v :where (v :k ?v)])"), + 2, + "a keyword is not a ref" + ); + assert_eq!( + db.count("(query [:find ?x ?v :where (fl ?x ?v)])"), + 2, + "-0.0 is not 0.0" + ); + assert_eq!( + db.count("(query [:find ?v :where (st :k ?v)])"), + 1, + "one long string" + ); + let QueryResult::QueryResults { results, .. } = db + .mem + .execute("(query [:find (count ?v) :where (p :k ?v)])") + .unwrap() + else { + panic!("expected query results"); + }; + assert_eq!( + results, + vec![vec![Value::Integer(1)]], + "a head equal to a stored fact is not derived again" + ); +} + +/// A derived fact has no metadata (spec §3.3). +#[test] +fn derived_metadata_is_nil() { + let db = Dbs::new(&[ + CHAIN, + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(reach ?x ?z) [?x :e ?y] (reach ?y ?z)])", + ]); + let rows = db.rows( + "(query [:find ?x ?y ?t :any-valid-time :where (reach ?x ?y) [?x :reach ?y] [?x :db/tx-count ?t]])", + ); + assert_eq!(rows.len(), 6); + assert!(rows.iter().all(|r| r[2] == Value::Null), "nil metadata"); + assert_eq!( + db.count( + "(query [:find ?x :any-valid-time :where (reach ?x ?y) [?x :reach ?y] [?x :db/tx-count 1]])" + ), + 0, + "a constant never matches nil" + ); + assert_eq!( + db.count("(query [:find ?x ?y :where (reach ?x ?y) [?x :db/valid-at ?v]])"), + 20, + ":db/valid-at joins every fact of ?x, derived ones too: a 3 x 4, b 2 x 3, c 1 x 2" + ); +} + +#[test] +fn heads() { + let db = Dbs::new(&[ + CHAIN, + r#"(transact [[:a :name "a"] [:b :ok true]])"#, + "(rule [(flag ?x) [?x :ok true]])", + "(rule [(bad ?n ?x) [?x :name ?n]])", + "(rule [(gap ?x ?y) [?x :e ?z]])", + "(rule [(kw ?y ?x) [?x :e ?y]])", + ]); + assert_eq!( + db.rows("(query [:find ?x ?v :where (flag ?x) [?x :flag ?v]])") + .first() + .map(|r| r[1].clone()), + Some(Value::Boolean(true)), + "a one-argument head derives true" + ); + assert_eq!( + db.err("(query [:find ?x :where (bad ?x ?y)])"), + "QRY-013", + "a string is not an entity" + ); + assert_eq!( + db.err("(query [:find ?x :where (gap ?x ?y)])"), + "INT-022", + "an unbound head variable" + ); + assert_eq!( + db.count("(query [:find ?x ?y :where (kw ?x ?y)])"), + 3, + "a keyword head entity names an entity" + ); +} + +#[test] +fn limits() { + let db = Dbs::new(&[ + "(transact [[:c :zero 0]])", + "(rule [(cnt ?c ?n) [?c :zero ?n]])", + "(rule [(cnt ?c ?m) (cnt ?c ?n) [(+ ?n 1) ?m]])", + ]); + assert_eq!( + db.err("(query [:find ?n :where (cnt :c ?n)])"), + "INT-020", + "rounds" + ); + assert_eq!( + db.err("(query [:find ?n :where (cnt ?c ?n) :max-derived-facts 5])"), + "INT-020", + "derived facts" + ); +} + +#[test] +fn rule_queries_with_every_operator() { + let db = Dbs::new(&[ + CHAIN, + "(transact [[:a :w 1] [:b :w 2] [:c :w 3] [:d :w 4]])", + "(rule [(reach ?x ?y) [?x :e ?y]])", + "(rule [(reach ?x ?z) [?x :e ?y] (reach ?y ?z)])", + ]); + assert_eq!( + db.rows("(query [:find ?x (count ?y) :where (reach ?x ?y)])") + .len(), + 3, + "aggregate" + ); + assert_eq!( + db.count("(query [:find ?x ?y :where (reach ?x ?y) [?y :w ?w] [(> ?w 2)]])"), + 5, + "expression" + ); + assert_eq!( + db.count("(query [:find ?x :where [?x :w ?w] (not-join [?x] (reach ?x ?y))])"), + 1, + "not of an invocation" + ); + assert_eq!( + db.count("(query [:find ?x ?y :where [?x :w ?w] (or (reach ?x ?y) [?x :e ?y])])"), + 6, + "or of an invocation" + ); + assert_eq!( + db.count("(query [:find ?x ?y (sum ?w :over (:partition-by ?x :order-by ?y)) :where (reach ?x ?y) [?y :w ?w]])"), + 6, + "window" + ); +} From 5df6d8945b2c0ecb9d88acd02134c25e94955b2c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 21 Oct 2026 01:32:54 +0530 Subject: [PATCH 2/2] docs: rule queries on the engine in CHANGELOG, counts and module notes (#548) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_019kY61Y11gcRD91Y6b7jbGT --- CHANGELOG.md | 2 ++ CLAUDE.md | 4 ++-- README.md | 2 +- docs/TEST_COVERAGE.md | 5 +++-- 4 files changed, 8 insertions(+), 5 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index ee4b95fc70..b90ca3320f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -97,6 +97,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **`not` and `not-join` run on the streaming engine** (#473, part 4: #546, first PR). An `AntiJoin` keeps the outer rows for which the body has no row; it never deduplicates. A body that has the same rows for every outer row (its expressions and pseudo-attributes read only variables its own patterns bind) runs once, and its rows' values of the variables it shares with the outer row form a hash set. Any other body, and one whose first pattern's entity comes from the outer row, runs once per outer row from a one-row seed of the values it imports, stopping at its first row: an entity-bound body costs one index probe per row and holds nothing. Bodies are ordered with the imported variables counted as bound. Queries whose negation holds a rule invocation stay on the executor. Measured (#394 envelope, p50 and peak RSS): an entity-bound `not` (`[?e :group 7] (not [?e :age 7])`, run per row) 760 ms → 27 ms and 222 → 6 MiB at 1M facts, 8.7 s → 0.29 s and 1.2 GiB → 6 MiB at 10M; a `not-join` keyed on a value whose body has an expression (`(not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])`, hashed) 1.29 s → 5.8 ms at 100K, over 60 s → 53 ms and 171 → 7 MiB at 1M, over 60 s → 0.57 s and 1.5 GiB → 9 MiB at 10M. Other workloads unchanged. Results are unchanged (`test-oracle`). - **Aggregates run on the streaming engine** (#473, part 5: #547, second PR). Queries with aggregates in `:find`, with or without `:with`, now run on the engine when their `:where` does. An `Aggregate` operator keeps one entry per group in a hash table, keyed on the grouping cells as groups compare values, and steps each aggregate as rows arrive: a query with no grouping variable holds one set of accumulators, whatever the input size. `count` reads only whether a cell is `nil` and `count-distinct` keeps the keys of its cells, so neither turns ids into values; other aggregates read values. When the input ends, the groups are sorted by their values, finished in that order and returned in batches. Measured (#394 envelope, p50 and peak RSS): `[:find (count ?v) :where [?e ?a ?v]]` 207 ms → 44 ms and 97 → 7 MiB at 100K facts, 3.01 s → 457 ms and 728 → 7 MiB at 1M, 29.6 s → 4.46 s and 6.6 GiB → 7 MiB at 10M; `[:find ?g (count ?e) :where [?e :group ?g]]` 31 → 5.9 ms at 100K, 397 → 61 ms and 97 → 7 MiB at 1M, 4.51 s → 614 ms and 901 → 7 MiB at 10M. Other workloads unchanged. Results are unchanged apart from the float group value above (`test-oracle`). - **Window functions run on the streaming engine** (#473, part 5: #547, third PR). Queries with window functions in `:find`, alone or over an aggregate's groups, now run on the engine when their `:where` does. A `Window` operator holds each input row's returned cells and the values of the variables the windows read, then computes every window with the code the executor runs (partitions, the sort, peers) and returns the rows in input order. Measured (#394 envelope, p50 and peak RSS): `[:find ?e (rank :over (:order-by ?a)) :where [?e :age ?a]]` 41.5 → 32.8 ms and 19 → 16 MiB at 100K facts, 601 → 434 ms and 140 → 109 MiB at 1M, 7.89 s → 5.65 s and 1,257 → 1,030 MiB at 10M. A window holds every row by nature, so memory still grows with the input. Other workloads unchanged. Results are unchanged (`test-oracle`). +- **Rule queries run on the streaming engine** (#473, part 6: #548, second PR). A query that invokes a rule, at any depth, now runs on the engine when its body and the body of every rule it evaluates do. Each evaluated predicate has a relation: the facts its rules derive, held as rows of ids, a set (a fact derived twice, or equal to a stored fact, is kept once). `Recursive` derives the relations stratum by stratum before the body runs. Round 1 runs every rule over all facts; each later round runs a rule once per top-level invocation of its own stratum, that invocation reading only the facts the last round derived, so a fact is derived from new facts only (semi-naive). A rule that reads its own stratum otherwise (in an `or` branch, through a `[?x :p ?y]` or `[?x ?a ?v]` pattern, or `:db/valid-at`) runs over all facts every round. Scans read a relation's rows after the committed and pending facts, with `nil` metadata; entity probes use the relation's index. The query body is planned as any engine query, rule invocations read as patterns of their relations. The executor's `FactStorage` copy of the database for each rule query is gone on this path. Queries inside a write transaction, with an `:as-of` timestamp, or with a rule body the engine does not plan (an expression-only body, a nested `or`) stay on the executor. The binary-size gate on `v3` is 1,260 KiB until #551 removes the executor's query path (it was 1,230 KiB; this adds about 34 KiB). Measured (#394 envelope at 100K facts, p50 and peak RSS): `recursive_ancestors` (`(boss :p ?b)`, five ancestors through the magic-set rewrite) 2.72 s → 1.40 ms and 253 → 4 MiB. Other workloads unchanged. Results are unchanged (`test-oracle`). - **`or` and `or-join` run on the streaming engine** (#473, part 4: #546, second PR). A `Union` extends each outer row by every row of every branch; a `Distinct` then keeps one of each set of equal rows, comparing values as the executor does (`0.0` equals `-0.0`, a keyword never equals a ref, a row holding NaN is never a duplicate). Each branch is planned as a `not` body is: a branch with the same rows for every outer row runs once, into a table of its rows by their values of the variables it shares with the outer row; any other branch, and one whose first pattern's entity comes from the outer row, runs per outer row from a one-row seed. When the branches bind no new variable (every `or-join`, and an `or` that only filters), an outer row is returned once, from the first branch that has a row. A query whose first clause to run is an `or` starts from the empty row. These stay on the executor: a branch with a rule invocation, a nested `or`, or a predicate the function registry may not have; an `or` whose branches bind their own patterns' metadata; and a branch whose `not` reads a variable only the branch's expression binds. Measured (#394 envelope, p50 and peak RSS): an `or-join` of two branches keyed on a value (`[?e :group 7] [?e :age ?a] (or-join [?a] (and [?f :group 17] [?f :age ?a] [(< ?a 30)]) (and [?g :group 27] [?g :age ?a] [(> ?a 60)]))`, both hashed) 111 ms → 8.3 ms at 100K facts, 1.44 s → 80 ms and 306 → 7 MiB at 1M, 17.1 s → 0.86 s and 1.9 GiB → 12 MiB at 10M. Other workloads unchanged. Results are unchanged (`test-oracle`). - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. @@ -113,6 +114,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Performance envelope at 100K–10M facts (#394).** `examples/perf_envelope.rs` builds and caches fixtures of 100K, 1M and 10M facts (six attributes per entity, a ref tree, two valid-time windows, an entity with 1,000 versions). It reports open and checkpoint times, RSS, and p50/p99 latency for twelve query shapes, each shape in its own process. It builds with a new `envelope` Cargo profile (`release` at opt-level 3, as an application compiles the library; `release` itself is opt-level "z"). `docs/BENCHMARKS.md` and the README publish the results: point lookups and single-entity time travel stay flat (12–14 µs at 10M facts). Scans, aggregations and joins grow linearly with the attributes they touch. Rule queries are supported to 100K facts only. A Python FFI round trip (`bench/envelope.py` in minigraf-python) adds about 70 µs per query. `.github/workflows/envelope.yml` runs 100K and 1M on demand, and a 10K smoke pass on PRs that change the harness. The nightly Criterion `query/*` groups gain 100K and 1M scales. Profiling at 1M facts found #528, #529, #530, #531 and #532. - **Pseudo-attribute sources (#594).** `tests/pseudo_source_test.rs` covers the source rule (nearest earlier pattern in the text, two pseudo-attributes sharing one, every fact through `[?e ?a _]`, constants by entity id, `$slot`s by name), `PRS-081` for each shape with no source, reading the outer fact from `not`, `not-join` (listed and unlisted variable), `or` (never a sibling branch) and `or-join`, closed rule bodies, and `:db/valid-at`. Parser, optimizer and matcher unit tests cover the hidden variables, their placement and the join variables a crossed `not-join` gains. The plan-independence matrix gains the pseudo-attribute shapes. - **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off. +- **Rule queries on the engine (#548).** `tests/recursive_engine_test.rs` (10 tests) runs rule queries in memory, on a file with pending facts and after a checkpoint, and under `test-oracle` against the executor: transitive closure (linear and non-linear), mutual recursion, strata whose `not` and `or` rules recurse, rules that read their stratum outside a top-level invocation, derived facts seen by every pattern, the identity of derived facts, `nil` metadata, heads, both `INT-020` limits, and rule queries with aggregates, `not-join`, `or` and windows. Every existing rule suite (`recursive_rules_test`, `negation_test`, `disjunction_test`, `magic_sets_test`, the model-based and property tests) now runs its rule queries on the engine with the oracle. Engine unit tests cover routing and derived rows read across batches. - **Negation bodies in both forms (#546).** A second test-only switch (`minigraf::__subplans`, `test-oracle` feature) forces the engine's `not` / `not-join` bodies to run hashed or correlated. `tests/plan_independence_test.rs` runs every query with the body forms chosen, forced hashed and forced correlated, each with reordering on and off; its matrix gains negations over floats near zero, `0.0` and `-0.0`, keywords and refs of one entity, long strings, bodies reading an imported variable they do not bind, variable-free bodies and `:db/valid-at`. `tests/negation_equality_test.rs` checks the changed answers on every executor path, in memory and after a checkpoint. The property test's rerun also forces hashed bodies. Engine unit tests cover the form the planner picks, routing, multiplicity, failing expressions in bodies, and that a hashed body is read once and a correlated one probes once per row. - **Disjunctions (#546).** `tests/or_equality_test.rs` checks the changed `or` / `or-join` answers through `execute` and a cursor, in memory and after a checkpoint. `tests/plan_independence_test.rs` gains disjunctions (keywords meeting refs, floats near zero, long strings as keys, branches naming different outer variables or no join variable, a branch with `not`, an `or` with nothing before it, a cross product, `:db/valid-at` in a branch), run with branches chosen, forced hashed and forced correlated. The property test generates `or` and `or-join` over bound variables, with a reference evaluator that deduplicates the rows they keep. Engine unit tests run every disjunction shape with each branch form forced against the executor, and cover routing, the form the planner picks, `Distinct`, and that a hashed branch is read once. - **Aggregates and windows (#547).** `src/query/datalog/aggregate.rs` unit tests check every accumulator over every order of small inputs (exact float sums against hand-computed values, cancellation, subnormals, signed zeros, infinities and NaN, integer saturation, errors decided at the end) and that the value order is total. `tests/aggregate_window_rules_test.rs` checks the changed answers; `tests/plan_independence_test.rs` gains aggregate, window and mixed queries over ties, keywords and refs, and floats. diff --git a/CLAUDE.md b/CLAUDE.md index 707608515d..3609913e71 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -141,7 +141,7 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns, expression clauses, `not`/`not-join` and `or`/`or-join` without rule invocations, in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `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`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a rule query whose every evaluated rule body plans), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `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`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -206,7 +206,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1687 tests** (1677 passing, 10 ignored; unit + integration + doc). +**1701 tests** (1691 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 0bd58d83f9..3046d315f2 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 1687 tests +cargo test # run 1701 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 188a5ad0a2..0020d106a9 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,9 +2,9 @@ ## Coverage Summary -**Verified**: 2026-10-20 with `cargo test --quiet` +**Verified**: 2026-10-21 with `cargo test --quiet` -**Result**: 1,677 passing tests and 10 ignored tests (1,687 total) +**Result**: 1,691 passing tests and 10 ignored tests (1,701 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628). Tests in `tests/not_join_test.rs` check that recursion through a rule with `not`, `not-join` or `or`, directly or through another rule, returns every row along a chain, and that the `not` still removes the rows it should; evaluator unit tests check that such recursion stops at its fixpoint that `max_iterations` and `max_results` end one that does not with INT-020, and that `max_results` counts the facts every pass derives, not only the mixed rule's (#633). @@ -18,6 +18,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Magic-sets demand** (#608): `tests/magic_sets_test.rs` checks rule queries with a literal argument where some call site cannot carry the demand — 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. - **`or` with no shared variable** (#610): `tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product, 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. - **Prepared time travel** (#603): `tests/prepared_statements_test.rs` runs literal `:as-of` (counter and timestamp), `:valid-at`, `:any-valid-time` and a per-fact pseudo-attribute query through `execute`, a prepared `execute` and a prepared cursor, which must agree; a `prepared.rs` unit test checks that `substitute` keeps non-slot `:as-of` and `:valid-at`. +- **Rule queries on the engine** (`tests/recursive_engine_test.rs`, 10 tests; #548): linear and non-linear transitive closure, mutual recursion, strata whose `not` and `or` rules recurse (#633's cases), naive rules (a same-stratum read in an `or` branch, through a `:p` pattern, through `[?y ?a ?z]`), derived facts visible to every pattern and the magic-set predicate's attribute, identity of derived facts (keyword vs ref, `-0.0` vs `0.0`, long strings, a head equal to a stored fact), `nil` metadata and `:db/valid-at` over derived facts, one-argument heads, `QRY-013` and `INT-022` heads, both `INT-020` limits, and rule queries with aggregates, expressions, `not-join`, `or` and windows; each in memory, on a file with pending facts and after a checkpoint, and under `test-oracle` against the executor. Engine unit tests check routing (`:as-of` timestamp, an unplannable rule body, a three-argument call and a write transaction stay on the executor) and derived rows read across batches before and after a checkpoint; `relation.rs` unit tests check row identity and the `Old` / `Delta` / `Full` ranges. - **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 gives a variable its value, even when it runs first (#606; the plan-independence matrix checks it with reordering off). Under the `test-oracle` feature the joins among them also run on the streaming engine. A unit test checks that `-0.0` and `0.0` hash alike. - **Pseudo-attribute sources** (`tests/pseudo_source_test.rs`, 12 tests; #594): a per-fact pseudo-attribute reads the nearest earlier pattern in the text with the same entity term (#594's example in both text orders), two pseudo-attributes share a source, `[:alice ?a _]` gives one row per fact, constant and bound value terms check, `:alice` and its UUID are one term while `?e` and `:alice` are not, PRS-081 for a pattern after it, alone, `_`/`?_x` entities, another entity's pattern and a rule call; a `not` body reads the outer fact (and a source inside the body), `not-join` crosses for a listed variable only, `or` branches read the outer fact and never a sibling, `or-join`, closed rule bodies, `$slot`s by name at prepare time, and `:db/valid-at` once per fact. Parser unit tests check the hidden variables (`?#.`), the join variable a crossed `not-join` gains, and the PRS-081 text; an optimizer test places a pseudo-attribute pattern after its source and the pattern binding its value; matcher tests read the hidden variable, a substituted integer, and nothing without a source; the engine tests run the sourced shapes and check PRS-081 for the old fallback shapes. The plan-independence matrix gains eleven pseudo-attribute shapes. - **Negation equality** (`tests/negation_equality_test.rs`, 5 tests; #546): a value a `not` / `not-join` body takes from the outer row compares by join equality on every path (exclusion set, per-row body with an expression, a query that invokes a rule, a rule body): `1e-20` and `2e-20` differ, `0.0` equals `-0.0`, a keyword imported into an entity position equals the ref, and a float literal in the body still matches within `f64::EPSILON`; through `execute` and a cursor, in memory and after a checkpoint. Engine unit tests (`src/query/engine/tests.rs`, 6 more) run every negation shape (hashed and correlated bodies, keys on entity, value and attribute positions, floats, keywords and refs, long strings, bodies reading an imported variable, variable-free bodies, per-fact pseudo-attributes and `:db/valid-at` in bodies, deferred and repeated negations) at six temporal settings with each body form forced and reordering on and off, in memory and on file before and after checkpoints, against the executor; and check the form the planner picks, routing, multiplicity, failing expressions and unknown predicates in bodies, and that a hashed body is read once while a correlated one probes once per outer row. Optimizer unit tests cover `plan_seeded` and the `SUBPLANS` switch.