From b7290e4f521e1965a1dbd1af422431361d3142a8 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 14:54:23 +0530 Subject: [PATCH 1/3] feat(query): Filter/Bind, pseudo-attributes, cross-kind constants on the engine (#544) The engine now runs expression clauses and per-fact pseudo-attribute patterns after its scan pattern, in optimizer::plan order, and keyword, UUID and float value constants, reading only the AVET ranges they can match (attribute_kind_prefix from #518's branch). :db/valid-at stays on the executor (a join, #545). INT-026 and QRY-007 are raised before the engine runs, by the executor's own checks. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/query/datalog/executor.rs | 69 +++++--- src/query/engine/batch.rs | 17 ++ src/query/engine/cell.rs | 21 +++ src/query/engine/filter.rs | 82 +++++++++ src/query/engine/mod.rs | 35 +++- src/query/engine/plan.rs | 270 ++++++++++++++++++++++++++--- src/query/engine/project.rs | 3 +- src/query/engine/scan.rs | 194 +++++++++++++++------ src/query/engine/tests.rs | 313 +++++++++++++++++++++++++++++++--- src/storage/keys.rs | 56 ++++++ src/storage/mod.rs | 2 + src/storage/reader.rs | 4 + 12 files changed, 937 insertions(+), 129 deletions(-) create mode 100644 src/query/engine/filter.rs diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 3132e9aa7f..98b2296460 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -15,6 +15,39 @@ use anyhow::Result; use std::collections::HashMap; use std::sync::{Arc, RwLock}; +/// `INT-026`: per-fact pseudo-attributes require `:any-valid-time`. +fn check_per_fact_pseudo_attrs(query: &DatalogQuery) -> Result<()> { + if query_uses_per_fact_pseudo_attr(query) + && !matches!(query.valid_at, Some(ValidAt::AnyValidTime)) + { + return Err(err_coded!(ErrorCode::Int026)); + } + Ok(()) +} + +/// `QRY-007`: surface unknown UDF predicates as errors before processing any +/// rows (matches the behaviour of the former apply_expr_clauses post-pass). +fn check_udf_predicates(query: &DatalogQuery, registry: &FunctionRegistry) -> Result<()> { + for clause in &query.where_clauses { + if let WhereClause::Expr { + expr: Expr::UnaryOp(UnaryOp::Udf(name), _), + .. + } = clause + && registry.get_predicate(name).is_none() + { + bail_coded!(ErrorCode::Qry007, name); + } + } + Ok(()) +} + +/// The clause checks of the executor's own path, for a query the streaming +/// engine runs: its errors come first, from the same code (#473). +fn check_clauses(query: &DatalogQuery, registry: &FunctionRegistry) -> Result<()> { + check_per_fact_pseudo_attrs(query)?; + check_udf_predicates(query, registry) +} + /// Returns true if any where clause (at any depth) contains a per-fact /// pseudo-attribute pattern (ValidFrom / ValidTo / TxCount / TxId). /// Used to enforce the `:any-valid-time` requirement. @@ -514,8 +547,15 @@ impl DatalogExecutor { if self.facts_override.is_none() && let Some(plan) = crate::query::engine::plan(&query) { + let registry = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + check_clauses(&query, ®istry)?; let snapshot = self.read_snapshot()?; - if let Some(result) = crate::query::engine::run(&snapshot, plan) { + let result = crate::query::engine::run(&snapshot, plan, ®istry); + drop(registry); + if let Some(result) = result { #[cfg(any(test, feature = "test-oracle"))] crate::query::engine::oracle::check( &result, @@ -556,12 +596,7 @@ impl DatalogExecutor { None => Value::Integer(now), }; - // Hard-error: per-fact pseudo-attrs require :any-valid-time. - if query_uses_per_fact_pseudo_attr(&query) - && !matches!(query.valid_at, Some(ValidAt::AnyValidTime)) - { - return Err(err_coded!(ErrorCode::Int026)); - } + check_per_fact_pseudo_attrs(&query)?; // Apply temporal filters before pattern matching let filtered_facts = self.filter_facts_for_query(&query)?; @@ -575,18 +610,7 @@ impl DatalogExecutor { .read() .map_err(|_| err_coded!(ErrorCode::Qry008))?; - // Pre-validate UDF predicate names: surface unknown predicates as errors before - // processing any rows (matches the behaviour of the former apply_expr_clauses post-pass). - for clause in &query.where_clauses { - if let WhereClause::Expr { - expr: Expr::UnaryOp(UnaryOp::Udf(name), _), - .. - } = clause - && registry.get_predicate(name).is_none() - { - bail_coded!(ErrorCode::Qry007, name); - } - } + check_udf_predicates(&query, ®istry)?; // Collect Pattern, Expr, Not, and NotJoin top-level clauses for the planner. // Or/OrJoin are extracted separately below and applied as a post-pass. @@ -733,12 +757,7 @@ impl DatalogExecutor { None => Value::Integer(now), }; - // Hard-error: per-fact pseudo-attrs require :any-valid-time. - if query_uses_per_fact_pseudo_attr(&query) - && !matches!(query.valid_at, Some(ValidAt::AnyValidTime)) - { - return Err(err_coded!(ErrorCode::Int026)); - } + check_per_fact_pseudo_attrs(&query)?; // Apply temporal filters before evaluating recursive rules let filtered_facts = self.filter_facts_for_query(&query)?; diff --git a/src/query/engine/batch.rs b/src/query/engine/batch.rs index 84de920368..2cba1a3b19 100644 --- a/src/query/engine/batch.rs +++ b/src/query/engine/batch.rs @@ -27,4 +27,21 @@ impl Batch { } self.len += 1; } + + /// Keep the rows whose entry in `keep` is true. + pub(crate) fn retain(&mut self, keep: &[bool]) { + for col in &mut self.cols { + let mut k = keep.iter(); + col.retain(|_| k.next().copied().unwrap_or(false)); + } + self.len = keep.iter().filter(|&&k| k).count(); + } + + /// Set the column of `slot`: the next new slot, or one already filled. + pub(crate) fn set_col(&mut self, slot: usize, col: Vec) { + match self.cols.get_mut(slot) { + Some(c) => *c = col, + None => self.cols.push(col), + } + } } diff --git a/src/query/engine/cell.rs b/src/query/engine/cell.rs index 27769ca5ff..1b136efd6b 100644 --- a/src/query/engine/cell.rs +++ b/src/query/engine/cell.rs @@ -1,6 +1,10 @@ //! Cells: the values operators exchange (#473 spec §5.2). +use super::ids::IdSpace; +use crate::graph::types::Value; +use crate::storage::KeySource; use crate::storage::keys::{KeyValue, ValueRef}; +use anyhow::Result; use std::sync::Arc; /// One value in a row. Entities and keywords are ids in the query's @@ -42,4 +46,21 @@ impl Cell { KeyValue::Ref(eid) => Cell::Eid(*eid), } } + + /// The cell of a value, with ids from `ids`. + pub(crate) fn of_value( + ids: &mut IdSpace, + keys: Option<&dyn KeySource>, + value: &Value, + ) -> Result { + Ok(match value { + Value::Null => Cell::Val(Scalar::Null), + Value::Boolean(b) => Cell::Val(Scalar::Bool(*b)), + Value::Integer(n) => Cell::Val(Scalar::Int(*n)), + Value::Float(f) => Cell::Val(Scalar::Float(*f)), + Value::String(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), + Value::Keyword(k) => Cell::Iid(ids.iid(keys, k)?), + Value::Ref(u) => Cell::Eid(ids.eid(keys, u)?), + }) + } } diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs new file mode 100644 index 0000000000..1359825a30 --- /dev/null +++ b/src/query/engine/filter.rs @@ -0,0 +1,82 @@ +//! `Filter` and `Bind` (#473 spec §6.1), and the pseudo-attribute patterns +//! on a scanned fact: the clauses after the scan, one batch at a time. +//! +//! An expression sees only the variables it reads, turned into values for +//! the row; a binding expression's result becomes a cell again. + +use super::Ctx; +use super::batch::Batch; +use super::cell::{Cell, Scalar}; +use super::plan::{Step, Term, Vars}; +use super::project::value; +use crate::query::datalog::executor::{eval_expr, is_truthy}; +use crate::query::datalog::types::Expr; +use anyhow::Result; +use std::collections::HashMap; + +/// Apply `step` to `batch`. +pub(crate) fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { + match step { + Step::Pseudo { col, value } => { + let meta = batch.cols.get(*col).cloned().unwrap_or_default(); + match value { + Term::Any => {} + Term::Bind(slot) => batch.set_col(*slot, meta), + Term::Const(n) => { + let want = n.map(|n| Cell::Val(Scalar::Int(n))); + let keep: Vec = meta.iter().map(|c| want.as_ref() == Some(c)).collect(); + batch.retain(&keep); + } + Term::Eq(slot) => { + let other = batch.cols.get(*slot); + let keep: Vec = meta + .iter() + .enumerate() + .map(|(i, c)| other.and_then(|o| o.get(i)) == Some(c)) + .collect(); + batch.retain(&keep); + } + } + } + Step::Filter(expr, vars) => { + let mut keep = Vec::with_capacity(batch.len); + for i in 0..batch.len { + keep.push(eval(expr, vars, &batch, i, ctx)?.is_some_and(|v| is_truthy(&v))); + } + batch.retain(&keep); + } + Step::Bind(expr, vars, slot) => { + let mut keep = Vec::with_capacity(batch.len); + let mut out = Vec::with_capacity(batch.len); + for i in 0..batch.len { + match eval(expr, vars, &batch, i, ctx)? { + Some(v) => { + out.push(Cell::of_value(&mut ctx.ids, ctx.keys, &v)?); + keep.push(true); + } + None => keep.push(false), + } + } + batch.retain(&keep); + batch.set_col(*slot, out); + } + } + Ok(batch) +} + +/// `expr` over row `i`, or `None` where the executor's evaluation fails. +fn eval( + expr: &Expr, + vars: &Vars, + batch: &Batch, + i: usize, + ctx: &mut Ctx<'_>, +) -> Result> { + let mut binding = HashMap::with_capacity(vars.len()); + for (name, slot) in vars { + if let Some(cell) = batch.cols.get(*slot).and_then(|c| c.get(i)) { + binding.insert(name.clone(), value(cell, ctx)?); + } + } + Ok(eval_expr(expr, &binding, Some(ctx.functions)).ok()) +} diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index 7e6882ab7e..e45a33944b 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -8,6 +8,7 @@ mod batch; mod cell; +mod filter; mod ids; #[cfg(any(test, feature = "test-oracle"))] pub(crate) mod oracle; @@ -19,6 +20,7 @@ mod tests; use crate::graph::storage::Snapshot; use crate::query::datalog::executor::QueryResult; +use crate::query::datalog::functions::FunctionRegistry; use crate::storage::KeySource; use anyhow::Result; use ids::IdSpace; @@ -40,30 +42,53 @@ pub(crate) struct Ctx<'a> { /// database. keys: Option<&'a dyn KeySource>, ids: IdSpace, + /// Predicates for expression clauses. + functions: &'a FunctionRegistry, } /// Run `plan` over `snapshot`, or `None` when the snapshot's committed /// reader has no keys (a test reader) and the executor must run it. -pub(crate) fn run(snapshot: &Snapshot, plan: Plan) -> Option> { +pub(crate) fn run( + snapshot: &Snapshot, + plan: Plan, + functions: &FunctionRegistry, +) -> Option> { let keys = match &snapshot.committed { Some(reader) => Some(reader.key_source()?), None => None, }; #[cfg(test)] RUNS.with(|r| r.set(r.get() + 1)); - Some(execute(snapshot, keys, plan)) + Some(execute(snapshot, keys, plan, functions)) } -fn execute(snapshot: &Snapshot, keys: Option<&dyn KeySource>, plan: Plan) -> Result { - let Plan { scan, find, vars } = plan; +fn execute( + snapshot: &Snapshot, + keys: Option<&dyn KeySource>, + plan: Plan, + functions: &FunctionRegistry, +) -> Result { + let Plan { + scan, + steps, + find, + vars, + } = plan; let mut results = Vec::new(); let mut ctx = Ctx { snapshot, keys, ids: IdSpace::new(keys), + functions, }; let mut scan = scan::Scan::new(scan); - while let Some(batch) = scan.next_batch(&mut ctx)? { + while let Some(mut batch) = scan.next_batch(&mut ctx)? { + for step in &steps { + if batch.len == 0 { + break; + } + batch = filter::apply(step, batch, &mut ctx)?; + } results.extend(project::project(&batch, &find, &mut ctx)?); } Ok(QueryResult::QueryResults { vars, results }) diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 1d8195e80b..5d52974863 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -2,13 +2,19 @@ //! operator trees. //! //! #544 runs a query whose `:where` is one pattern with a stored attribute, -//! and whose `:find` holds plain variables. Every other query runs on the -//! existing executor (spec §9). +//! followed by pseudo-attribute patterns on the same entity and expression +//! clauses, and whose `:find` holds plain variables. Every other query runs +//! on the existing executor (spec §9). +//! +//! Clauses run in the order `optimizer::plan` gives the executor, so an +//! expression sees the same variables, and a binding expression overwrites a +//! variable at the same point, as it does there. use crate::graph::types::{EntityId, Value}; use crate::query::datalog::matcher::edn_to_entity_id; +use crate::query::datalog::optimizer; use crate::query::datalog::types::{ - AsOf, AttributeSpec, DatalogQuery, EdnValue, FindSpec, ValidAt, WhereClause, + AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, PseudoAttr, ValidAt, WhereClause, }; use std::collections::HashMap; @@ -24,6 +30,40 @@ pub(crate) enum Term { Const(C), } +/// A constant in the value position, with the executor's matching rules +/// (`PatternMatcher::match_component`). +#[derive(Debug, Clone)] +pub(crate) enum ValueConst { + /// A string, integer, boolean or `nil`: equal values only. + Exact(Value), + /// A keyword: the same keyword, or a ref to the entity it names. + Keyword(String, EntityId), + /// A UUID: a ref to it, or a keyword that names it. + Uuid(EntityId), + /// A float: floats within `f64::EPSILON`. + Float(f64), +} + +impl ValueConst { + pub(crate) fn matches(&self, v: &Value) -> bool { + match (self, v) { + (ValueConst::Exact(c), v) => c == v, + (ValueConst::Keyword(k, _), Value::Keyword(fk)) => k == fk, + (ValueConst::Keyword(_, u), Value::Ref(fu)) | (ValueConst::Uuid(u), Value::Ref(fu)) => { + u == fu + } + (ValueConst::Uuid(u), Value::Keyword(k)) => names(k, u), + (ValueConst::Float(f), Value::Float(ff)) => (f - ff).abs() < f64::EPSILON, + _ => false, + } + } +} + +/// Whether the keyword `k` names the entity `u`. +pub(crate) fn names(k: &str, u: &EntityId) -> bool { + edn_to_entity_id(&EdnValue::Keyword(k.to_string())).is_ok_and(|id| id == *u) +} + /// The valid-time test of a query. #[derive(Debug, Clone, Copy)] pub(crate) enum Valid { @@ -33,26 +73,72 @@ pub(crate) enum Valid { Any, } +/// A per-fact pseudo-attribute: fact metadata as an integer column. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum Meta { + ValidFrom, + ValidTo, + TxCount, + TxId, +} + /// What a `Scan` reads. #[derive(Debug, Clone)] pub(crate) struct ScanSpec { pub(crate) e: Term, pub(crate) a: Term, - pub(crate) v: Term, + pub(crate) v: Term, + /// Metadata columns the scan fills, and their slots. + pub(crate) meta: Vec<(Meta, usize)>, pub(crate) as_of: Option, pub(crate) valid: Valid, - /// Number of variable slots. + /// Number of slots the scan fills. pub(crate) width: usize, } +/// A clause after the scan, in the executor's order. +#[derive(Debug, Clone)] +pub(crate) enum Step { + /// A pseudo-attribute pattern on the scanned fact: its value term over + /// the metadata column `col`. A constant other than an integer never + /// matches. + Pseudo { + col: usize, + value: Term>, + }, + /// `[(pred …)]`: keeps the rows where the expression is truthy. + Filter(Expr, Vars), + /// `[(f …) ?out]`: binds (or overwrites) the slot; drops the rows where + /// the expression fails. + Bind(Expr, Vars, usize), +} + +/// The variables an expression reads that are bound when it runs, by slot. +pub(crate) type Vars = Vec<(String, usize)>; + #[derive(Debug)] pub(crate) struct Plan { pub(crate) scan: ScanSpec, + pub(crate) steps: Vec, /// The slot of each `:find` variable. pub(crate) find: Vec, pub(crate) vars: Vec, } +/// Variable slots, in the order clauses bind them. +#[derive(Default)] +struct Slots { + by_var: HashMap, + len: usize, +} + +impl Slots { + fn add(&mut self) -> usize { + self.len += 1; + self.len - 1 + } +} + /// The plan of `query`, or `None` when the engine does not run it yet. pub(crate) fn plan(query: &DatalogQuery) -> Option { let as_of = match &query.as_of { @@ -67,13 +153,24 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { Some(ValidAt::AnyValidTime) => Valid::Any, Some(ValidAt::Slot(_)) => return None, }; - let [WhereClause::Pattern(p)] = query.where_clauses.as_slice() else { + if !query + .where_clauses + .iter() + .all(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) + { + return None; + } + let (planned, _) = optimizer::plan(query.where_clauses.clone()); + let mut planned = planned.into_iter().map(|(c, _)| c); + let Some(WhereClause::Pattern(p)) = planned.next() else { return None; }; let AttributeSpec::Real(attribute) = &p.attribute else { return None; }; - let mut slots = HashMap::new(); + let rest: Vec = planned.collect(); + + let mut slots = Slots::default(); let e = term(&p.entity, &mut slots, |c| match c { EdnValue::Keyword(_) | EdnValue::Uuid(_) => edn_to_entity_id(c).ok(), _ => None, @@ -82,49 +179,182 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { EdnValue::Keyword(k) => Some(k.clone()), _ => None, })?; - let v = term(&p.value, &mut slots, |c| match c { - EdnValue::String(s) => Some(Value::String(s.clone())), - EdnValue::Integer(n) => Some(Value::Integer(*n)), - EdnValue::Boolean(b) => Some(Value::Boolean(*b)), - EdnValue::Nil => Some(Value::Null), - _ => None, - })?; + let v = term(&p.value, &mut slots, value_const)?; + + // A pseudo-attribute pattern reads the metadata of the fact the scan + // matched only when its entity is the scan's entity term; any other + // pseudo-attribute pattern joins over every fact (#545). + let mut meta: Vec<(Meta, usize)> = Vec::new(); + for c in &rest { + let WhereClause::Pattern(q) = c else { + continue; + }; + let m = match &q.attribute { + AttributeSpec::Pseudo(pa) => meta_of(pa)?, + AttributeSpec::Real(_) => return None, + }; + if !same_entity(&p.entity, &q.entity) { + return None; + } + if !meta.iter().any(|(mm, _)| *mm == m) { + meta.push((m, slots.add())); + } + } + // An expression that rebinds the entity variable would send a later + // pseudo-attribute pattern to another entity. + if !meta.is_empty() + && rest.iter().any(|c| { + matches!(c, WhereClause::Expr { binding: Some(out), .. } + if matches!(&p.entity, EdnValue::Symbol(s) if s == out)) + }) + { + return None; + } + let width = slots.len; + + let mut steps = Vec::with_capacity(rest.len()); + for c in rest { + steps.push(match c { + WhereClause::Pattern(q) => { + let AttributeSpec::Pseudo(pa) = &q.attribute else { + return None; + }; + let m = meta_of(pa)?; + let col = meta.iter().find(|(mm, _)| *mm == m)?.1; + let value = term(&q.value, &mut slots, |c| { + Some(match c { + EdnValue::Integer(n) => Some(*n), + _ => None, + }) + })?; + Step::Pseudo { col, value } + } + WhereClause::Expr { expr, binding } => { + let vars = expr_vars(&expr, &slots); + match binding { + None => Step::Filter(expr, vars), + Some(out) => { + let slot = match slots.by_var.get(&out) { + Some(&s) => s, + None => { + let s = slots.add(); + slots.by_var.insert(out, s); + s + } + }; + Step::Bind(expr, vars, slot) + } + } + } + _ => return None, + }); + } + let mut find = Vec::with_capacity(query.find.len()); for spec in &query.find { let FindSpec::Variable(var) = spec else { return None; }; // The parser rejects a variable no clause binds (PRS-080). - find.push(*slots.get(var)?); + find.push(*slots.by_var.get(var)?); } Some(Plan { scan: ScanSpec { e, a, v, + meta, as_of, valid, - width: slots.len(), + width, }, + steps, find, vars: query.find.iter().map(FindSpec::display_name).collect(), }) } +fn value_const(c: &EdnValue) -> Option { + Some(match c { + EdnValue::String(s) => ValueConst::Exact(Value::String(s.clone())), + EdnValue::Integer(n) => ValueConst::Exact(Value::Integer(*n)), + EdnValue::Boolean(b) => ValueConst::Exact(Value::Boolean(*b)), + EdnValue::Nil => ValueConst::Exact(Value::Null), + // A keyword whose name parses as a UUID names that UUID. + EdnValue::Keyword(k) => ValueConst::Keyword(k.clone(), edn_to_entity_id(c).ok()?), + EdnValue::Uuid(u) => ValueConst::Uuid(*u), + EdnValue::Float(f) => ValueConst::Float(*f), + _ => return None, + }) +} + +/// The metadata column of a per-fact pseudo-attribute; `None` for +/// `:db/valid-at`, which the executor matches against every fact of the +/// entity (a join, #545). +fn meta_of(pa: &PseudoAttr) -> Option { + match pa { + PseudoAttr::ValidFrom => Some(Meta::ValidFrom), + PseudoAttr::ValidTo => Some(Meta::ValidTo), + PseudoAttr::TxCount => Some(Meta::TxCount), + PseudoAttr::TxId => Some(Meta::TxId), + PseudoAttr::ValidAt => None, + } +} + +/// Whether a pseudo-attribute pattern's entity `pseudo` resolves to the +/// entity of the fact the scan pattern's entity `scan` matched. +fn same_entity(scan: &EdnValue, pseudo: &EdnValue) -> bool { + match (scan, pseudo) { + (EdnValue::Symbol(s), EdnValue::Symbol(t)) => { + s.starts_with('?') && !s.starts_with("?_") && s == t + } + (EdnValue::Keyword(_) | EdnValue::Uuid(_), EdnValue::Keyword(_) | EdnValue::Uuid(_)) => { + edn_to_entity_id(scan).ok() == edn_to_entity_id(pseudo).ok() + } + _ => false, + } +} + +/// The variables of `expr` bound so far, with their slots. A variable bound +/// later, or never, is left out: the expression fails on it, as it does in +/// the executor. +fn expr_vars(expr: &Expr, slots: &Slots) -> Vars { + fn walk(expr: &Expr, slots: &Slots, out: &mut Vars) { + match expr { + Expr::Var(v) => { + if let Some(&s) = slots.by_var.get(v) + && !out.iter().any(|(n, _)| n == v) + { + out.push((v.clone(), s)); + } + } + Expr::Lit(_) | Expr::Slot(_) => {} + Expr::BinOp(_, l, r) => { + walk(l, slots, out); + walk(r, slots, out); + } + Expr::UnaryOp(_, inner) => walk(inner, slots, out), + } + } + let mut out = Vec::new(); + walk(expr, slots, &mut out); + out +} + /// The term of one pattern position; `None` for a constant `konst` does not /// take, or a symbol that is not a variable. fn term( edn: &EdnValue, - slots: &mut HashMap, + slots: &mut Slots, konst: impl Fn(&EdnValue) -> Option, ) -> Option> { match edn { EdnValue::Symbol(s) if s == "_" || s.starts_with("?_") => Some(Term::Any), - EdnValue::Symbol(s) if s.starts_with('?') => Some(match slots.get(s) { + EdnValue::Symbol(s) if s.starts_with('?') => Some(match slots.by_var.get(s) { Some(&slot) => Term::Eq(slot), None => { - let slot = slots.len(); - slots.insert(s.clone(), slot); + let slot = slots.add(); + slots.by_var.insert(s.clone(), slot); Term::Bind(slot) } }), diff --git a/src/query/engine/project.rs b/src/query/engine/project.rs index 1aafc01ef8..6826ef0112 100644 --- a/src/query/engine/project.rs +++ b/src/query/engine/project.rs @@ -26,7 +26,8 @@ pub(crate) fn project(batch: &Batch, find: &[usize], ctx: &mut Ctx<'_>) -> Resul Ok(rows) } -fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { +/// The value of `cell`. +pub(crate) fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { Ok(match cell { Cell::Eid(e) => Value::Ref(ctx.ids.uuid(ctx.keys, *e)?), Cell::Iid(i) => Value::Keyword(ctx.ids.name(ctx.keys, *i)?.to_string()), diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 8a615ad278..7460d818d7 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -3,20 +3,19 @@ //! Every pending fact is newer than every committed one, so a triple with a //! pending record in the snapshot (at or before `:as-of`) is decided by its //! pending records alone, and a triple without one by its committed keys -//! (#379). `Scan` reads the committed range first, leaving out the triples a +//! (#379). `Scan` reads the committed ranges first, leaving out the triples a //! pending record decides (the shadow set), then the pending range. use super::batch::Batch; use super::cell::{Cell, Scalar}; -use super::plan::{ScanSpec, Term, Valid}; +use super::plan::{Meta, ScanSpec, Term, Valid, ValueConst, names}; use super::{BATCH_ROWS, Ctx}; use crate::graph::storage::PendingResume; -use crate::graph::types::{Fact, Value}; -use crate::storage::keys::{self, Index, KeyFact, KeyValue, SHORT_STRING_MAX}; +use crate::graph::types::{EntityId, Fact, Value}; +use crate::storage::keys::{self, Index, KeyFact, KeyValue, SHORT_STRING_MAX, ValueKind}; use crate::storage::{KeySource, Scan as Range}; use anyhow::Result; -use std::collections::HashSet; -use std::sync::Arc; +use std::collections::{HashMap, HashSet}; pub(crate) struct Scan { spec: ScanSpec, @@ -34,15 +33,48 @@ enum State { /// The committed half of the read. struct Committed { - index: Index, - prefix: Vec, + /// Key ranges as `(index, prefix)`, read in turn from `next`. + ranges: Vec<(Index, Vec)>, + next: usize, resume: Option>, - /// The value constant when the range does not fix it. - value: Option, + /// The value constant when the ranges do not fix it. + test: Option, /// Triples a pending record decides, as [`keys::entity_attribute_value_prefix`]. shadow: HashSet>, } +/// A value constant over committed key values, with ids resolved. +enum KeyTest { + Exact(KeyValue), + /// A keyword constant: the keyword's ident id, the named entity's id. + Keyword(Option, Option), + /// A UUID constant: its entity id; whether each keyword names it. + Uuid(EntityId, Option, HashMap), + Float(f64), +} + +impl KeyTest { + fn matches(&mut self, keys: &dyn KeySource, v: &KeyValue) -> Result { + Ok(match (self, v) { + (KeyTest::Exact(c), v) => c == v, + (KeyTest::Keyword(Some(i), _), KeyValue::Keyword(fi)) => i == fi, + (KeyTest::Keyword(_, Some(e)) | KeyTest::Uuid(_, Some(e), _), KeyValue::Ref(fe)) => { + e == fe + } + (KeyTest::Uuid(u, _, seen), KeyValue::Keyword(i)) => match seen.get(i) { + Some(&m) => m, + None => { + let m = names(&keys.ident_of(*i)?, u); + seen.insert(*i, m); + m + } + }, + (KeyTest::Float(f), KeyValue::Float(ff)) => (*f - ff).abs() < f64::EPSILON, + _ => false, + }) + } +} + impl Scan { pub(crate) fn new(spec: ScanSpec) -> Self { Scan { @@ -63,20 +95,26 @@ impl Scan { self.state = State::Pending(None); continue; }; + let Some((index, prefix)) = c.ranges.get(c.next) else { + self.state = State::Pending(None); + continue; + }; self.keys_buf.clear(); c.resume = keys.live_keys( - c.index, - &c.prefix, + *index, + prefix, c.resume.as_deref(), self.spec.as_of, BATCH_ROWS, &mut self.keys_buf, )?; + if c.resume.is_none() { + c.next += 1; + } let valid = valid_at(self.spec.valid, ctx); let mut row = vec![None; self.spec.width]; for kf in &self.keys_buf { if !visible(valid, kf.vf, kf.vt) - || c.value.as_ref().is_some_and(|v| *v != kf.v) || (!c.shadow.is_empty() && c.shadow.contains(&keys::entity_attribute_value_prefix( kf.e, kf.a, &kf.v, @@ -84,17 +122,28 @@ impl Scan { { continue; } + if let Some(t) = &mut c.test + && !t.matches(keys, &kf.v)? + { + continue; + } if fill(&self.spec.e, &mut row, || Ok(Cell::Eid(kf.e)))? && fill(&self.spec.a, &mut row, || Ok(Cell::Iid(u64::from(kf.a))))? && fill(&self.spec.v, &mut row, || Ok(Cell::of_key(&kf.v)))? { + for &(m, slot) in &self.spec.meta { + let n = match m { + Meta::ValidFrom => kf.vf, + Meta::ValidTo => kf.vt, + Meta::TxCount => kf.tx_count.cast_signed(), + Meta::TxId => keys.tx_id_of(kf.tx_count)?.cast_signed(), + }; + set(&mut row, slot, n); + } batch.push(&mut row); } row.iter_mut().for_each(|c| *c = None); } - if c.resume.is_none() { - self.state = State::Pending(None); - } } State::Pending(resume) => { self.facts_buf.clear(); @@ -109,7 +158,7 @@ impl Scan { let mut row = vec![None; self.spec.width]; for f in &self.facts_buf { if !visible(valid, f.valid_from, f.valid_to) - || matches!(&self.spec.v, Term::Const(v) if *v != f.value) + || matches!(&self.spec.v, Term::Const(v) if !v.matches(&f.value)) { continue; } @@ -119,8 +168,18 @@ impl Scan { Ok(Cell::Eid(ids.eid(keys, &f.entity)?)) })? && fill(&self.spec.a, &mut row, || { Ok(Cell::Iid(ids.iid(keys, &f.attribute)?)) - })? && fill(&self.spec.v, &mut row, || value_cell(ids, keys, &f.value))? - { + })? && fill(&self.spec.v, &mut row, || { + Cell::of_value(ids, keys, &f.value) + })? { + for &(m, slot) in &self.spec.meta { + let n = match m { + Meta::ValidFrom => f.valid_from, + Meta::ValidTo => f.valid_to, + Meta::TxCount => f.tx_count.cast_signed(), + Meta::TxId => f.tx_id.cast_signed(), + }; + set(&mut row, slot, n); + } batch.push(&mut row); } row.iter_mut().for_each(|c| *c = None); @@ -138,8 +197,14 @@ impl Scan { } } -/// Resolve the committed range of `spec` and the pending triples that -/// shadow it. +fn set(row: &mut [Option], slot: usize, n: i64) { + if let Some(s) = row.get_mut(slot) { + *s = Some(Cell::Val(Scalar::Int(n))); + } +} + +/// Resolve the committed ranges of `spec` and the pending triples that +/// shadow them. fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { let Some(keys) = ctx.keys else { return Ok(State::Pending(None)); @@ -159,24 +224,23 @@ fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { }, _ => None, }; - let v = match &spec.v { - Term::Const(value) => match key_value(keys, value)? { - Some(v) => Some(v), + let test = match &spec.v { + Term::Const(c) => match key_test(keys, c)? { + Some(t) => Some(t), None => return Ok(pending), }, _ => None, }; - let (index, prefix, value) = match (e, a, v) { - (Some(e), Some(a), Some(v)) => ( - Index::Eavt, - keys::entity_attribute_value_prefix(e, a, &v), + let (ranges, test) = match (e, a, test) { + (Some(e), Some(a), Some(KeyTest::Exact(v))) => ( + vec![(Index::Eavt, keys::entity_attribute_value_prefix(e, a, &v))], None, ), - (Some(e), Some(a), None) => (Index::Eavt, keys::entity_attribute_prefix(e, a), None), - (Some(e), None, v) => (Index::Eavt, keys::entity_prefix(e), v), - (None, Some(a), Some(v)) => (Index::Avet, keys::attribute_value_prefix(a, &v), None), - (None, Some(a), None) => (Index::Aevt, keys::attribute_prefix(a), None), - (None, None, v) => (Index::Eavt, Vec::new(), v), + (Some(e), Some(a), t) => (vec![(Index::Eavt, keys::entity_attribute_prefix(e, a))], t), + (Some(e), None, t) => (vec![(Index::Eavt, keys::entity_prefix(e))], t), + (None, Some(a), Some(t)) => avet(a, t), + (None, Some(a), None) => (vec![(Index::Aevt, keys::attribute_prefix(a))], None), + (None, None, t) => (vec![(Index::Eavt, Vec::new())], t), }; let mut shadow = HashSet::new(); for f in ctx.snapshot.pending_records(range(spec), spec.as_of)? { @@ -185,14 +249,55 @@ fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { } } Ok(State::Committed(Committed { - index, - prefix, + ranges, + next: 0, resume: None, - value, + test, shadow, })) } +/// The AVET ranges of attribute `a` that hold every value `t` matches, and +/// the test left for the values they read. +fn avet(a: u32, t: KeyTest) -> (Vec<(Index, Vec)>, Option) { + let value = |v: KeyValue| (Index::Avet, keys::attribute_value_prefix(a, &v)); + let kind = |k: ValueKind| (Index::Avet, keys::attribute_kind_prefix(a, k)); + match t { + KeyTest::Exact(v) => (vec![value(v)], None), + KeyTest::Keyword(i, e) => { + let ranges = i + .map(|i| value(KeyValue::Keyword(i))) + .into_iter() + .chain(e.map(|e| value(KeyValue::Ref(e)))) + .collect(); + (ranges, None) + } + KeyTest::Uuid(u, e, seen) => { + let ranges = e + .map(|e| value(KeyValue::Ref(e))) + .into_iter() + .chain([kind(ValueKind::Keyword)]) + .collect(); + (ranges, Some(KeyTest::Uuid(u, e, seen))) + } + KeyTest::Float(f) => (vec![kind(ValueKind::Float)], Some(KeyTest::Float(f))), + } +} + +/// The test of a value constant over committed keys, or `None` when no +/// committed key can match it. +fn key_test(keys: &dyn KeySource, c: &ValueConst) -> Result> { + Ok(match c { + ValueConst::Exact(v) => key_value(keys, v)?.map(KeyTest::Exact), + ValueConst::Keyword(k, u) => match (keys.iid_of(k)?, keys.eid_of(u)?) { + (None, None) => None, + (i, e) => Some(KeyTest::Keyword(i, e)), + }, + ValueConst::Uuid(u) => Some(KeyTest::Uuid(*u, keys.eid_of(u)?, HashMap::new())), + ValueConst::Float(f) => Some(KeyTest::Float(*f)), + }) +} + /// The pending range of `spec`. fn range(spec: &ScanSpec) -> Range<'_> { match (&spec.e, &spec.a) { @@ -227,23 +332,6 @@ fn key_value(keys: &dyn KeySource, value: &Value) -> Result> { }) } -/// The cell of a pending fact's value. -fn value_cell( - ids: &mut super::ids::IdSpace, - keys: Option<&dyn KeySource>, - value: &Value, -) -> Result { - Ok(match value { - Value::Null => Cell::Val(Scalar::Null), - Value::Boolean(b) => Cell::Val(Scalar::Bool(*b)), - Value::Integer(n) => Cell::Val(Scalar::Int(*n)), - Value::Float(f) => Cell::Val(Scalar::Float(*f)), - Value::String(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), - Value::Keyword(k) => Cell::Iid(ids.iid(keys, k)?), - Value::Ref(u) => Cell::Eid(ids.eid(keys, u)?), - }) -} - /// The valid time a fact must cover, `None` for any. fn valid_at(valid: Valid, ctx: &Ctx<'_>) -> Option { match valid { diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 1fbffcf8ab..6ac4bd6031 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -26,25 +26,39 @@ fn long(tag: u32) -> String { format!("{}{tag}", "a long string kept in a value page ".repeat(3)) } +/// The UUID a keyword entity such as `:p1` stands for. +fn uuid_of(entity: &str) -> uuid::Uuid { + uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, entity.as_bytes()) +} + /// One batch of history, numbered `round`: assertions, retractions, -/// re-assertions in new windows, refs, keywords, long strings. +/// re-assertions in new windows, refs, keywords (one naming an entity by its +/// UUID), floats, long strings. fn write_round(db: &Minigraf, round: u32) { + let scores = ["0.30000000000000004", "1.5", "-0.0", "0.0", "2.5"]; for p in 0..6u32 { let s = (round + p) % 3; + let f = (p + round) % 6; db.execute(&format!( "(transact [[:p{p} :person/status :s{s}] [:p{p} :person/age {age}] \ [:p{p} :person/friend :p{f}] [:p{p} :person/name \"n{p}\"] \ - [:p{p} :person/bio \"{bio}\"] [:p{p} :person/ok {ok}] [:p{p} :person/self :p{p}]])", + [:p{p} :person/bio \"{bio}\"] [:p{p} :person/ok {ok}] [:p{p} :person/self :p{p}] \ + [:p{p} :person/boss #uuid \"{boss}\"] [:p{p} :person/alias :{alias}] \ + [:p{p} :person/score {score}]])", age = 20 + round % 4, - f = (p + round) % 6, bio = long(p % 2), ok = (round + p) % 2 == 0, + boss = uuid_of(&format!(":p{f}")), + alias = uuid_of(&format!(":p{}", (p + 1) % 6)), + score = scores[((round + p) % 5) as usize], )) .unwrap(); if (round + p) % 2 == 0 { db.execute(&format!( - "(retract [[:p{p} :person/status :s{s}] [:p{p} :person/age {}]])", - 20 + round % 4 + "(retract [[:p{p} :person/status :s{s}] [:p{p} :person/age {}] \ + [:p{p} :person/score {}]])", + 20 + round % 4, + scores[((round + p) % 5) as usize], )) .unwrap(); } @@ -60,7 +74,8 @@ fn write_round(db: &Minigraf, round: u32) { /// Every query shape the planner takes, at several `:as-of` and valid times. fn queries(tx: u64) -> Vec { - let shapes = [ + let u1 = uuid_of(":p1"); + let mut shapes: Vec = [ "[?e ?a ?v]", "[?e :person/status ?v]", "[?e :person/bio ?v]", @@ -79,31 +94,137 @@ fn queries(tx: u64) -> Vec { "[:nobody ?a ?v]", "[?e :no/such ?v]", "[?e :person/name \"no such name\"]", - ]; + // Cross-kind constants (#544 PR 2): a keyword matches the keyword and + // a ref to the entity it names; a UUID matches the ref and keywords + // that name it; floats match within an epsilon. + "[?e :person/status :s1]", + "[?e :person/friend :p2]", + "[?e :person/boss :p2]", + "[?e ?a :p3]", + "[:p0 ?a :p1]", + "[:p0 :person/boss :p1]", + "[?e :person/status :no-such-keyword]", + "[?e :person/score 0.3]", + "[?e :person/score 0.0]", + "[?e :person/score -0.0]", + "[?e :person/score 1.5000000000000002]", + "[?e ?a 2.5]", + "[:p1 ?a 1.5]", + "[?e :person/age 21.0]", + ] + .into_iter() + .map(String::from) + .collect(); + for c in [format!("#uuid \"{u1}\""), format!(":{u1}")] { + shapes.push(format!("[?e :person/alias {c}]")); + shapes.push(format!("[?e :person/boss {c}]")); + shapes.push(format!("[?e ?a {c}]")); + shapes.push(format!("[:p0 :person/alias {c}]")); + } let mut out = Vec::new(); - for shape in shapes { + for shape in &shapes { let find = ["?e", "?a", "?v"] .into_iter() .filter(|v| shape.contains(v)) .collect::>(); - if find.is_empty() { - continue; + let find = if find.is_empty() { + "?x".to_string() + } else { + find.join(" ") + }; + // A constant-only pattern answers through an expression binding. + let tail = if find == "?x" { " [(+ 1 2) ?x]" } else { "" }; + for temporal in temporals(tx) { + out.push(format!( + "(query [:find {find} {temporal} :where {shape}{tail}])" + )); } - let find = find.join(" "); - for temporal in [ - String::new(), - ":valid-at :any-valid-time".to_string(), - ":valid-at \"2023-03-01\"".to_string(), - format!(":as-of {} :valid-at :any-valid-time", tx / 2), - format!(":as-of {}", tx.saturating_sub(1)), - ":as-of 1".to_string(), - ] { - out.push(format!("(query [:find {find} {temporal} :where {shape}])")); + } + // Expressions after the scan, and pseudo-attributes of the scanned fact. + let clauses = [ + ("?e ?v", "[?e :person/age ?v] [(> ?v 21)]"), + ("?e ?w", "[?e :person/age ?v] [(+ ?v 1) ?w]"), + ("?e ?v", "[?e :person/age ?v] [(+ ?v 1) ?v]"), + ( + "?e ?w", + "[?e :person/age ?v] [(+ ?v 1) ?w] [(* ?w 2) ?w] [(> ?w 44)]", + ), + ("?e ?w", "[?e :person/age ?v] [(+ ?v 1) ?w] [(+ ?v 2) ?w]"), + ("?e ?v", "[?e :person/bio ?v] [(contains? ?v \"page\")]"), + ("?e ?v", "[?e :person/bio ?v] [(+ ?v 1)]"), + ("?e ?w", "[?e :person/bio ?v] [(/ 1 0) ?w]"), + ("?e ?v", "[?e :person/friend ?v] [(= ?v :p1)]"), + ("?e ?v", "[?e :person/score ?v] [(< ?v 1)]"), + ("?v ?w", "[?e :person/score ?v] [(* ?v 2) ?w]"), + ("?e ?a", "[?e ?a ?v] [(string? ?v)]"), + ("?e", "[?e :person/ok ?v] [(> 2 1)]"), + ("?e", "[?e :person/ok ?v] [(> 1 2)]"), + ("?e ?v", "[?e :person/self ?v] [(= ?e ?v)]"), + ]; + let pseudo = [ + ("?e ?v ?t", "[?e :person/age ?v] [?e :db/tx-count ?t]"), + ( + "?e ?f ?u", + "[?e :person/name ?v] [?e :db/valid-from ?f] [?e :db/valid-to ?u]", + ), + ("?v ?t", "[:p1 :person/name ?v] [:p1 :db/tx-id ?t]"), + ("?a ?t", "[?e ?a ?v] [?e :db/tx-id ?t]"), + ("?e ?v", "[?e :person/age ?v] [?e :db/tx-count 3]"), + ("?e ?v", "[?e :person/age ?v] [?e :db/tx-count \"3\"]"), + ("?e ?v", "[?e :person/age ?v] [?e :db/tx-count ?v]"), + ( + "?e ?t", + "[?e :person/age ?v] [?e :db/tx-count ?t] [?e :db/tx-count ?t]", + ), + ( + "?e ?t", + "[?e :person/age ?v] [?e :db/valid-from ?t] [?e :db/valid-to ?t]", + ), + ( + "?e ?f", + "[?e :person/age ?v] [?e :db/valid-from ?f] [(> ?f 0)]", + ), + ( + "?e ?t", + "[?e :person/age ?v] [(- ?v ?v) ?t] [?e :db/tx-count ?t]", + ), + ( + "?e ?t", + "[?e :person/age ?v] [?e :db/tx-count _] [?e :db/tx-count ?t]", + ), + ]; + let pseudo_temporals = [ + ":valid-at :any-valid-time".to_string(), + format!(":as-of {} :valid-at :any-valid-time", tx / 2), + ]; + for (find, clauses) in clauses { + for temporal in temporals(tx) { + out.push(format!( + "(query [:find {find} {temporal} :where {clauses}])" + )); + } + } + for (find, clauses) in pseudo { + for temporal in &pseudo_temporals { + out.push(format!( + "(query [:find {find} {temporal} :where {clauses}])" + )); } } out } +fn temporals(tx: u64) -> [String; 6] { + [ + String::new(), + ":valid-at :any-valid-time".to_string(), + ":valid-at \"2023-03-01\"".to_string(), + format!(":as-of {} :valid-at :any-valid-time", tx / 2), + format!(":as-of {}", tx.saturating_sub(1)), + ":as-of 1".to_string(), + ] +} + fn check_all(db: &Minigraf) -> usize { let tx = db.current_tx_count(); queries(tx).iter().map(|q| rows(db, q)).sum() @@ -175,7 +296,9 @@ fn engine_reads_many_batches() { } /// The executor still runs what the engine does not: two patterns, -/// aggregates, `:as-of` a timestamp, expressions, keyword and float constants. +/// aggregates, `:as-of` a timestamp, `:db/valid-at`, pseudo-attributes of +/// another entity, a pseudo-attribute pattern planned first, an expression +/// rebinding the entity before a pseudo-attribute pattern. #[test] fn other_queries_stay_on_the_executor() { let db = Minigraf::in_memory().unwrap(); @@ -184,13 +307,153 @@ fn other_queries_stay_on_the_executor() { "(query [:find ?e ?n :where [?e :person/name ?n] [?e :person/age ?a]])", "(query [:find (count ?e) :where [?e :person/name ?n]])", "(query [:find ?e :as-of \"2099-01-01T00:00:00Z\" :where [?e :person/name ?n]])", - "(query [:find ?v :where [?e :person/status ?v] [(= ?v :s1)]])", - "(query [:find ?e :where [?e :person/status :s1]])", - // Floats match within an epsilon, not by key (PR 2). - "(query [:find ?e :where [?e :person/age 21.0]])", + "(query [:find ?e ?t :where [?e :person/name ?n] [?e :db/valid-at ?t]])", + "(query [:find ?e ?t :valid-at :any-valid-time \ + :where [?e :person/friend ?f] [?f :db/tx-count ?t]])", + "(query [:find ?e ?t :valid-at :any-valid-time \ + :where [?e :db/tx-count 1] [?e :person/name ?t]])", + "(query [:find ?e ?t :valid-at :any-valid-time \ + :where [_ :person/name ?e] [_ :db/tx-count ?t]])", + "(query [:find ?n ?t :valid-at :any-valid-time \ + :where [?e :person/name ?n] [(+ 1 2) ?e] [?e :db/tx-count ?t]])", ] { let before = runs(); db.execute(q).unwrap(); assert_eq!(runs(), before, "query stayed on the executor"); } } + +/// The executor's errors come first, from the same checks: a per-fact +/// pseudo-attribute without `:any-valid-time` (INT-026), an unknown +/// predicate (QRY-007). +#[test] +fn engine_queries_raise_the_executor_errors() { + let db = Minigraf::in_memory().unwrap(); + write_round(&db, 0); + for (q, code) in [ + ( + "(query [:find ?e ?t :where [?e :person/age ?v] [?e :db/tx-count ?t]])", + "INT-026", + ), + ( + "(query [:find ?e :where [?e :person/age ?v] [(no-such-pred? ?v)]])", + "QRY-007", + ), + ] { + let before = runs(); + let err = db.execute(q).unwrap_err(); + assert_eq!(crate::MinigrafError::from(err).code(), code); + assert_eq!(runs(), before, "no engine run"); + } +} + +/// A registered predicate runs in the engine's filter. +#[test] +fn engine_filter_runs_registered_predicates() { + let db = Minigraf::in_memory().unwrap(); + write_round(&db, 0); + db.register_predicate( + "even-age?", + |v: &crate::Value| matches!(v, crate::Value::Integer(n) if n % 2 == 0), + ) + .unwrap(); + rows( + &db, + "(query [:find ?e ?v :where [?e :person/age ?v] [(even-age? ?v)]])", + ); +} + +/// Cross-kind constants over committed and pending facts, `:as-of`, +/// retractions and reopen (from #518's branch): each answer agrees with the +/// executor (the oracle), and the expected entities are found. +#[test] +fn cross_kind_constants_read_their_avet_ranges() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("avet.graph"); + let file = Minigraf::open(&path).unwrap(); + let mem = Minigraf::in_memory().unwrap(); + let both = |cmd: &str| { + file.execute(cmd).unwrap(); + mem.execute(cmd).unwrap(); + }; + let (u1, u2) = (uuid_of(":p1"), uuid_of(":p2")); + let long = "a long relation value ".repeat(4); + let batches = [ + vec![ + "(transact [[:p0 :rel :p1] [:p1 :rel :k/x] [:p2 :rel 1.5] [:p3 :rel nil]])".to_string(), + format!(r#"(transact [[:p4 :rel "{long}"] [:p5 :rel 7] [:p5 :rel true]])"#), + ], + vec![ + format!(r#"(transact [[:p1 :rel #uuid "{u2}"]])"#), + "(retract [[:p5 :rel 7]])".to_string(), + r#"(transact [[:p3 :rel "s"]])"#.to_string(), + ], + // Pending on top of committed facts. + vec![ + "(transact [[:p5 :rel 7] [:p0 :rel 1.5]])".to_string(), + "(retract [[:p1 :rel :k/x]])".to_string(), + ], + ]; + for (i, batch) in batches.iter().enumerate() { + for cmd in batch { + both(cmd); + } + if i + 1 < batches.len() { + file.checkpoint().unwrap(); + } + } + let entities = |db: &Minigraf, c: &str| -> Vec { + let before = runs(); + let QueryResult::QueryResults { results, .. } = db + .execute(&format!("(query [:find ?e :where [?e :rel {c}]])")) + .unwrap() + else { + panic!("expected query results"); + }; + assert_eq!(runs(), before + 1, "query ran on the engine"); + let mut es: Vec = results + .iter() + .map(|r| match r.first() { + Some(crate::Value::Ref(u)) => *u, + _ => panic!("expected an entity"), + }) + .collect(); + es.sort(); + es + }; + let ps = |names: &[&str]| -> Vec { + let mut es: Vec = names.iter().map(|n| uuid_of(n)).collect(); + es.sort(); + es + }; + let expected = [ + (":p1".to_string(), ps(&[":p0"])), + (":p2".to_string(), ps(&[":p1"])), + (format!(r#"#uuid "{u1}""#), ps(&[":p0"])), + (format!(r#"#uuid "{u2}""#), ps(&[":p1"])), + (":k/x".to_string(), ps(&[])), + (":nope".to_string(), ps(&[])), + ("1.5".to_string(), ps(&[":p0", ":p2"])), + ("nil".to_string(), ps(&[":p3"])), + ("7".to_string(), ps(&[":p5"])), + ("true".to_string(), ps(&[":p5"])), + (r#""s""#.to_string(), ps(&[":p3"])), + (format!(r#""{long}""#), ps(&[":p4"])), + ]; + let check = |db: &Minigraf| { + for (c, want) in &expected { + assert_eq!(&entities(db, c), want, "entities of a constant"); + let max = db.current_tx_count(); + rows( + db, + &format!("(query [:find ?e :as-of {} :where [?e :rel {c}]])", max - 2), + ); + } + }; + check(&file); + check(&mem); + file.checkpoint().unwrap(); + check(&file); + drop(file); + check(&Minigraf::open(&path).unwrap()); +} diff --git a/src/storage/keys.rs b/src/storage/keys.rs index 721f6d821e..c26004bd35 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -629,6 +629,25 @@ pub fn attribute_value_prefix(a: u32, v: &KeyValue) -> Vec { k } +/// A kind of value whose matches a constant cannot name by one key: floats +/// match within an epsilon, keywords match a UUID constant by the entity +/// they name (#544). +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum ValueKind { + Float, + Keyword, +} + +/// Key prefix of every AVET entry of attribute `a` with a value of `kind`. +pub fn attribute_kind_prefix(a: u32, kind: ValueKind) -> Vec { + let mut k = attribute_prefix(a); + k.push(match kind { + ValueKind::Float => TAG_FLOAT, + ValueKind::Keyword => TAG_KEYWORD, + }); + k +} + // ─── DICT keys (§5.2) ──────────────────────────────────────────────────────── pub const DICT_UUID_TO_EID: u8 = 0x01; @@ -1123,6 +1142,43 @@ mod tests { assert!(!aevt.starts_with(&attribute_prefix(700))); } + #[test] + fn kind_prefixes_bound_exactly_their_kind() { + let avet = |v: KeyValue| { + KeyFact { + e: 300, + a: 7, + v, + tx_count: 5, + vf: 0, + vt: VALID_TIME_FOREVER, + asserted: true, + } + .key(Index::Avet) + .unwrap() + }; + let floats = attribute_kind_prefix(7, ValueKind::Float); + let keywords = attribute_kind_prefix(7, ValueKind::Keyword); + for f in [f64::NEG_INFINITY, -0.0, 0.0, 1.5, f64::NAN] { + let k = avet(KeyValue::Float(f)); + assert!(k.starts_with(&floats) && !k.starts_with(&keywords)); + } + let k = avet(KeyValue::Keyword(3)); + assert!(k.starts_with(&keywords) && !k.starts_with(&floats)); + for other in [ + KeyValue::Int(1), + KeyValue::Ref(3), + KeyValue::Null, + KeyValue::Str("x".into()), + ] { + let k = avet(other); + assert!(!k.starts_with(&floats) && !k.starts_with(&keywords)); + } + assert!( + !avet(KeyValue::Float(1.0)).starts_with(&attribute_kind_prefix(8, ValueKind::Float)) + ); + } + #[test] fn dict_keys_round_trip() { let r = ValueRef { diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 6d4ccc3c7a..e4e14e3b1b 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -441,6 +441,8 @@ pub trait KeySource: Send + Sync { fn long_value(&self, vref: keys::ValueRef) -> Result; /// Where the long string `s` is stored, if a committed fact holds it. fn long_value_ref(&self, s: &str) -> Result>; + /// The `tx_id` of the committed transaction `tx_count`. + fn tx_id_of(&self, tx_count: u64) -> Result; /// The keys of `index` that start with `prefix` and survive net-assert at /// `as_of`, decoded, appended to `out` in key order. /// diff --git a/src/storage/reader.rs b/src/storage/reader.rs index 3a87b72972..5c978bc95a 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -277,6 +277,10 @@ impl KeySource for OnDiskReader { self.dict().find_long_value(s) } + fn tx_id_of(&self, tx_count: u64) -> Result { + self.dict().tx_id_of(tx_count) + } + fn live_keys( &self, index: Index, From a4cf7bad82359aa3306480cff573b3b43f9fdc73 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 14:54:24 +0530 Subject: [PATCH 2/3] docs: engine expressions, pseudo-attributes, cross-kind constants (#544) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 1 + CLAUDE.md | 4 ++-- README.md | 2 +- docs/TEST_COVERAGE.md | 4 ++-- .../plans/2026-10-14-544-operator-core.md | 19 +++++++++++++++++++ 5 files changed, 25 insertions(+), 5 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 3965cb112f..a1fde70b14 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -56,6 +56,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Internal - **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query, and reads inside a `WriteTransaction`, run on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature). +- **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545). - **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. diff --git a/CLAUDE.md b/CLAUDE.md index d063993ebd..8c43ed576d 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -139,7 +139,7 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, plain `:find` variables, today), `scan.rs` (one pattern over a committed key range via `CommittedReader::key_source`/`live_keys`, then the pending range by whole runs), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `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). `DatalogExecutor::execute_query` tries it first. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, then per-fact pseudo-attribute patterns on its entity and expression clauses in `optimizer::plan` order, plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs), `filter.rs` (`Filter`/`Bind` and pseudo-attribute columns over batches), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `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). `DatalogExecutor::execute_query` tries it first. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1477 tests** (1467 passing, 10 ignored; unit + integration + doc). +**1481 tests** (1471 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 6cab5daf35..2c20ab8e26 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 1477 tests +cargo test # run 1481 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 584799f6d6..aa3eb30c33 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-14 with `cargo test --quiet` -**Result**: 1,467 passing tests and 10 ignored tests (1,477 total) +**Result**: 1,471 passing tests and 10 ignored tests (1,481 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). @@ -14,7 +14,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). Query and prepared-query cursors keep their answer and their pages across writes, checkpoints and index rebuilds, and the file stops growing once they close (`tests/cursor_test.rs`); a snapshot leaves out facts appended after it on every scan (`graph::storage`); a crash at every write point of a save with a pinned generation loses no fact and no page, and the reopened database reuses the quarantined ids (`storage::persistent_facts`); the browser withholds free pages a pinned generation may read and releases them once out of force (`storage::pins::split_released`, and a `#[wasm_bindgen_test]` with an open `BrowserDb` cursor). -- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, and checks which queries stay on the executor. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). +- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/docs/superpowers/plans/2026-10-14-544-operator-core.md b/docs/superpowers/plans/2026-10-14-544-operator-core.md index dec7c1cc2f..6a823cdbe1 100644 --- a/docs/superpowers/plans/2026-10-14-544-operator-core.md +++ b/docs/superpowers/plans/2026-10-14-544-operator-core.md @@ -189,6 +189,25 @@ for what it ships. attribute: keyword only; other constants → no rows, as `match_component` gives). - Oracle tests for each (the issue's "cross-kind matching rules pinned by oracle tests"). +### PR 2 deviations +- `:db/valid-at` patterns stay on the executor. Its matcher binds `:db/valid-at` by + scanning every fact of the entity (rows are a bag, one per fact), so it is a join, not + a constant column (#545). +- A pseudo-attribute pattern runs on the engine only if its entity is the scan + pattern's entity term (the same variable, or a constant naming the same entity), it + is planned after the scan pattern, and no expression rebinds that variable: the + executor's hidden-key fast path applies only then; otherwise it joins (#545). +- Steps run in `optimizer::plan` order, and a binding expression overwrites a bound + variable as the executor does (`[(+ ?v 1) ?v]` is accepted by the parser). +- `INT-026` and `QRY-007` are raised before the engine runs, by the executor's own + checks (`check_clauses`); the executor path keeps its order of errors. +- `attribute_string_prefix` is not ported: an exact long string resolves its value ref + through the DICT and uses `attribute_value_prefix`, so nothing would call it. +- With the attribute unbound, cross-kind constants read EAVT (the entity's prefix, or + the whole index) with a residual test, not VAET: a keyword or UUID constant also + matches keyword values, which VAET does not hold. +- `KeySource::tx_id_of` added for `:db/tx-id` on committed rows (decision 5 listed it). + ### 10. Lazy cursor (PR 3) - `Cursor` holds the operator tree and the snapshot; `next_batch(max_rows)` pulls internal batches until `max_rows` rows are ready; errors surface from `next_batch` From 9235c12e97499dcd8d4dba4d446ee3bb8ea95d9a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 15:04:59 +0530 Subject: [PATCH 3/3] test(storage): one assertion for the kind prefix test (#544) Its && asserts left failure branches the coverage gate counts: keys.rs branches 76.4% < 80% floor; now 81.7%. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/storage/keys.rs | 63 ++++++++++++++++++++++++++------------------- 1 file changed, 36 insertions(+), 27 deletions(-) diff --git a/src/storage/keys.rs b/src/storage/keys.rs index c26004bd35..7d2ad1e86e 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -1144,39 +1144,48 @@ mod tests { #[test] fn kind_prefixes_bound_exactly_their_kind() { - let avet = |v: KeyValue| { - KeyFact { - e: 300, - a: 7, - v, - tx_count: 5, - vf: 0, - vt: VALID_TIME_FOREVER, - asserted: true, - } - .key(Index::Avet) - .unwrap() - }; let floats = attribute_kind_prefix(7, ValueKind::Float); let keywords = attribute_kind_prefix(7, ValueKind::Keyword); - for f in [f64::NEG_INFINITY, -0.0, 0.0, 1.5, f64::NAN] { - let k = avet(KeyValue::Float(f)); - assert!(k.starts_with(&floats) && !k.starts_with(&keywords)); - } - let k = avet(KeyValue::Keyword(3)); - assert!(k.starts_with(&keywords) && !k.starts_with(&floats)); - for other in [ + let other_attr = attribute_kind_prefix(8, ValueKind::Float); + let values = [ + KeyValue::Float(f64::NEG_INFINITY), + KeyValue::Float(-0.0), + KeyValue::Float(0.0), + KeyValue::Float(1.5), + KeyValue::Float(f64::NAN), + KeyValue::Keyword(3), KeyValue::Int(1), KeyValue::Ref(3), KeyValue::Null, KeyValue::Str("x".into()), - ] { - let k = avet(other); - assert!(!k.starts_with(&floats) && !k.starts_with(&keywords)); - } - assert!( - !avet(KeyValue::Float(1.0)).starts_with(&attribute_kind_prefix(8, ValueKind::Float)) - ); + ]; + // (in the float range, in the keyword range, in attribute 8's floats) + let got: Vec<(bool, bool, bool)> = values + .into_iter() + .filter_map(|v| { + KeyFact { + e: 300, + a: 7, + v, + tx_count: 5, + vf: 0, + vt: VALID_TIME_FOREVER, + asserted: true, + } + .key(Index::Avet) + }) + .map(|k| { + ( + k.starts_with(&floats), + k.starts_with(&keywords), + k.starts_with(&other_attr), + ) + }) + .collect(); + let mut want = vec![(true, false, false); 5]; + want.push((false, true, false)); + want.extend([(false, false, false); 4]); + assert_eq!(got, want); } #[test]