diff --git a/.github/workflows/property-tests.yml b/.github/workflows/property-tests.yml index d12d35fd0c..fdd948138f 100644 --- a/.github/workflows/property-tests.yml +++ b/.github/workflows/property-tests.yml @@ -28,7 +28,10 @@ jobs: set -o pipefail cargo test --test property_test -- --nocapture 2>&1 | tee proptest-output.txt env: - PROPTEST_CASES: 8000000 + # Query properties (#386): 1M in-memory cases (~3 ms each) and a + # tenth as many file-backed ones (~57 ms each, checkpoint and + # reopen), plus 1M of each one-pattern property; ~1.6 h locally. + PROPTEST_CASES: 1000000 RUST_BACKTRACE: 1 - name: Record property-test failure @@ -44,7 +47,7 @@ jobs: echo echo "- Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" echo "- Commit: $GITHUB_SHA" - echo "- Reproduce: \`PROPTEST_CASES=8000000 cargo test --test property_test -- --nocapture\`" + echo "- Reproduce: \`PROPTEST_CASES=1000000 cargo test --test property_test -- --nocapture\`" echo echo "## Test output" echo diff --git a/CLAUDE.md b/CLAUDE.md index cd787330be..afc183bd3b 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1221 tests** (1213 passing, 8 ignored; unit + integration + doc). +**1223 tests** (1215 passing, 8 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 a1aced9279..1fc5aa3747 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1221 tests +cargo test # run 1223 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 38f6762d43..a1009fd755 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,9 @@ **Verified**: 2026-10-08 with `cargo test` -**Result**: 1,213 passing tests and 8 ignored tests (1,221 total), including the golden-file corpus (#391) +**Result**: 1,215 passing tests and 8 ignored tests (1,223 total), including the golden-file corpus (#391) + +`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). The histories leave out the v2.x known issues #371, #435 and #477. `tests/crash_kill_test.rs` kills a child process running a seeded workload under 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, again after a second reopen and after a checkpoint plus reopen (#384). The workload leaves out the v2.x known issues #371 and #435. diff --git a/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md b/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md new file mode 100644 index 0000000000..ac31dc6168 --- /dev/null +++ b/docs/superpowers/specs/2026-10-08-wider-property-tests-design.md @@ -0,0 +1,136 @@ +# Wider property tests — Design + +**Issue:** #386, tracker #383 +**Milestone:** v3.0.0, branch `v3`, with a v2.x backport to `main` (test and CI only; +no library change) + +## 1. Goal + +`tests/property_test.rs` checks query semantics against a reference evaluator, +but only for one-pattern queries over an in-memory database written one fact per +`transact`, and it counts a query error as an empty result. Widen it to joins, +negation, predicates and temporal queries over histories written in batches with +retractions, on both the in-memory and the file-backed database. The sibling +model-based test (#385) covers operation sequences with single-pattern reads; +this test covers query semantics. + +## 2. Shared reference model + +The temporal reference of `tests/model_based_test.rs` (value pool `V`, the time +grid, `Window`/`Effective`, `valid_at`, and `Model` with `verdict`, `records`, +`commit` and `live`) moves unchanged to `tests/reference_model/mod.rs`. Both test +files use it with `mod reference_model;`. One copy of the subtle rules (#435 one +window per triple, #477 latest statement wins, API-011/API-019 verdicts) keeps +the two tests from drifting apart. + +## 3. Histories + +A case writes a history of 1–12 operations to a fresh database: + +| Op | API | +|---|---| +| `Transact` | one `(transact …)` of 1–8 facts, tx- and fact-level windows from the grid | +| `Retract` | one `(retract …)` of 1–4 triples | +| `WriteTx` | `begin_write`, 1–4 transact/retract statements, `commit` | +| `Checkpoint` | `checkpoint()` (file backend only; a no-op in memory) | + +Facts come from the shared pools (4 entities, 3 attributes, 18 values including +refs to the entities), so batches repeat entities and attributes, and retractions +hit live triples. Generated statements are always accepted: an empty or inverted +window is rewritten to start in 2000 and a repeated triple in one statement +keeps one window. Rejections are the model-based test's job; here every write +must succeed. + +## 4. Backends + +- **Memory:** `Minigraf::in_memory()`. +- **File:** `open_with_options` in a temp dir (`SyncMode::Normal`), with the + history's `Checkpoint` ops applied, so the queries read a mix of checkpointed + and pending facts. The queries run once on the open handle, then again after a + drop and reopen (default options or `page_cache_size(4)`). + +## 5. Queries + +Each case runs 1–4 generated queries. A query has: + +- **Patterns:** 1–3 `[E A V]`. `E` is an entity variable (`?e0`–`?e2`) or an + entity constant. `A` is an attribute constant, or rarely `?a`. `V` is a value + variable (`?v0`–`?v2`), an entity variable (a ref join), a pool constant, or + `_`. The small variable pools make patterns share variables, so most queries + with two or three patterns are joins. Every pattern after the first shares a + variable with an earlier one, so there are no cross products. +- **Negation (optional):** `(not [E A V])` over variables already bound, or + `(not-join [?x] [?x A ?fresh])` with a variable already bound. +- **Predicate (optional):** `[(op ?x c)]` or `[(op ?x ?y)]` with `op` in + `< <= > >= = !=`, over bound variables. +- **Temporal:** none, `:as-of N`, `:valid-at T`, both, or `:any-valid-time`. + `N` ranges over 0..=tx count + 1, `T` over the model-based grid. +- **Find:** a non-empty subset of the bound variables. + +## 6. Reference evaluator + +1. Visible facts: `Model::live(as_of)`, then `valid_at` (skipped for + `:any-valid-time`). +2. Patterns: a nested-loop join over the visible facts, one binding map per + combination; `_` matches anything and binds nothing; an entity variable in `V` + matches `V::Ref`. +3. `not` removes a binding when its pattern matches a visible fact; `not-join` + when some visible fact matches with the join variable bound. +4. Predicates follow `eval_binop`: `=`/`!=` compare values structurally; + orderings compare two strings bytewise and numbers as `f64`; any other pair is + a type error that drops the binding (no query error). +5. Project onto the find variables. + +**Comparison.** The engine returns one row per binding, not a set: `[:find ?e +:where [?e :c ?v]]` gives one row per `?v`. When the find covers every variable +and no pattern has `_`, each binding is distinct, so rows are compared as sorted +multisets; a duplicated or dropped fact then shows up. Otherwise rows are +compared as sets, which holds whether the engine keeps bag semantics or moves to +sets. + +Results render as in the model-based test: entities as pool indices, so failure +messages carry no `Uuid` (CodeQL rule). + +## 7. Errors + +Any write, checkpoint, reopen or query error fails the case with its error code. +The three existing properties stay (one fact per `transact`, cheap), with +`if result.is_err() { return vec![]; }` replaced by a failure. + +## 8. Cases and CI + +New properties read `PROPTEST_CASES` (default 256 in normal CI). The file-backed +property runs a tenth of that, since each case touches the disk. Measured per +case: 3 ms in memory, 57 ms file-backed, 0.7 ms for each one-pattern property. +The nightly count drops from 8,000,000 to 1,000,000: about 1.6 h locally, well +inside the 6-hour limit on a slower runner. + +Histories and query constants favour small integers and entities, and drop the +model-based test's hot triple: with the shared generators only 16% of queries +returned rows; with these, about 35% do, over a mean of 13 visible facts. + +Mutation checks during development, each caught: `:valid-at` inclusive at +`:valid-to`; `<` evaluated as `<=`; a predicate type error that keeps the row; +the on-disk read skipping retractions, or not hiding a triple's older +transactions; and, in the reference, `not` ignoring `:as-of` and patterns +ignoring their attribute. (Emitting on-disk retractions as assertions is an +equivalent mutant: the executor's net-assert step drops them.) Minimized +failures become named regression tests in the same file. + +## 9. v2.x backport + +A separate PR to `main` ports the test with a reference limited to v2.x +semantics: + +- No v8 model rules: v2 has no API-011/API-019 (#435, #436), so the generator + never repeats a triple within one transaction and never writes an empty + window. +- #371 (same-transaction multi-valued facts read back as one value): no + transaction writes two values of one entity and attribute, and no batched + retract removes two such values. +- #435 (several valid windows per triple): a triple is never asserted again + while it is live. +- #406/#414 do not apply: generated finds are always bound. + +`verify()` is not called (it does not exist on v2). The PR names these +exclusions. diff --git a/tests/property_test.rs b/tests/property_test.rs index 96bbc48de3..eaa1a3dccd 100644 --- a/tests/property_test.rs +++ b/tests/property_test.rs @@ -1,15 +1,28 @@ -//! Cross-feature property tests (#221). +//! Cross-feature property tests (#221, #386). //! //! Compares Minigraf query results against a deliberately simple reference -//! evaluator for randomly-generated small graphs. +//! evaluator. The first three properties write one fact per `transact` and run +//! one-pattern queries. The others write random histories (batched transacts, +//! retractions, write transactions, checkpoints) and run random queries with +//! joins, `not`/`not-join`, predicates, `:as-of`, `:valid-at` and +//! `:any-valid-time`, in memory and against a file that is reopened. //! //! Run: cargo test --test property_test //! More cases: PROPTEST_CASES=500 cargo test --test property_test +//! +//! Design: docs/superpowers/specs/2026-10-08-wider-property-tests-design.md +//! (v2.x backport: §9; histories leave out the known issues #371, #435, #477) #![cfg(not(target_arch = "wasm32"))] +mod reference_model; + use minigraf::QueryResult; -use minigraf::db::Minigraf; +use minigraf::db::{Minigraf, OpenOptions, SyncMode}; use proptest::prelude::*; +use proptest::test_runner::TestCaseError; +use reference_model::*; +use std::collections::HashMap; +use std::path::Path; use uuid::Uuid; #[derive(Debug, Clone)] @@ -43,12 +56,6 @@ struct TestQuery { negation_attr: Option, } -/// Compute the deterministic UUID for a keyword entity (mirrors `edn_to_entity_id`). -fn entity_uuid(idx: usize) -> Uuid { - let kw = format!(":e{idx}"); - Uuid::new_v5(&Uuid::NAMESPACE_OID, kw.as_bytes()) -} - // ── Reference evaluator (naive, independent of production code) ─────────────── fn ref_eval(facts: &[TestFact], query: &TestQuery) -> Vec { @@ -80,19 +87,23 @@ fn ref_eval(facts: &[TestFact], query: &TestQuery) -> Vec { // ── Minigraf evaluator ──────────────────────────────────────────────────────── -fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Vec { +fn minigraf_eval( + facts: &[TestFact], + query: &TestQuery, + max_entity: usize, +) -> Result, TestCaseError> { // Pre-compute UUID → index mapping for all possible entity indices. - let uuid_to_idx: std::collections::HashMap = - (0..max_entity).map(|i| (entity_uuid(i), i)).collect(); + let uuid_to_idx: HashMap = (0..max_entity).map(|i| (entity_uuid(i), i)).collect(); - let db = Minigraf::in_memory().unwrap(); + let db = Minigraf::in_memory().map_err(|_| TestCaseError::fail("in_memory failed"))?; for fact in facts { let entity_kw = format!(":e{}", fact.entity); let val_edn = fact.value.to_edn(); let attr = &fact.attribute; let edn = format!(r#"(transact [[{entity_kw} {attr} {val_edn}]])"#); - let _ = db.execute(&edn); + db.execute(&edn) + .map_err(|e| TestCaseError::fail(format!("transact failed ({})", e.code())))?; } let val_clause = match &query.value_filter { @@ -108,12 +119,10 @@ fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Ve let attr = &query.attribute; let datalog = format!("(query [:find ?e :where [?e {attr} ?v]{val_clause}{neg_clause}])"); - let result = db.execute(&datalog); - // Skip test cases where the generated query fails to parse/evaluate. - if result.is_err() { - return vec![]; - } - match result.unwrap() { + let result = db + .execute(&datalog) + .map_err(|e| TestCaseError::fail(format!("query failed ({}): {datalog}", e.code())))?; + match result { QueryResult::QueryResults { results, .. } => { let mut entities: Vec = results .into_iter() @@ -125,9 +134,9 @@ fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Ve .collect(); entities.sort(); entities.dedup(); - entities + Ok(entities) } - _ => vec![], + _ => Err(TestCaseError::fail("not a query result")), } } @@ -171,7 +180,7 @@ proptest! { negation_attr: None, }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; prop_assert_eq!(ref_result, mg_result); } @@ -184,7 +193,7 @@ proptest! { negation_attr: Some(":active".to_string()), }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; let neg_entities: std::collections::HashSet = facts .iter() @@ -211,8 +220,806 @@ proptest! { negation_attr: None, }; let ref_result = ref_eval(&facts, &query); - let mg_result = minigraf_eval(&facts, &query, 8); + let mg_result = minigraf_eval(&facts, &query, 8)?; prop_assert!(ref_result.is_empty(), "reference: impossible path must be empty"); prop_assert!(mg_result.is_empty(), "minigraf: impossible path must be empty"); } } + +// ── Histories (#386) ────────────────────────────────────────────────────────── + +/// One write of a history. Every generated statement is accepted. +#[derive(Clone, Debug)] +enum HistoryOp { + Exec(Stmt), + WriteTx(Vec), + /// `checkpoint()` on the file backend; nothing in memory. + Checkpoint, +} + +/// Make a statement acceptable: an empty or inverted window starts in 2000 +/// (API-019), and a triple repeated in one statement keeps its first fact +/// (API-011). Rejections are the model-based test's job. +fn accepted(stmt: Stmt) -> Stmt { + match stmt { + Stmt::Transact { window, facts } => { + let mut kept: Vec = Vec::new(); + for mut f in facts { + if kept.iter().any(|k| k.e == f.e && k.a == f.a && k.v == f.v) { + continue; + } + if !window_is_valid(effective(window, f.window)) { + f.window.vf = Some(0); + } + kept.push(f); + } + Stmt::Transact { + window, + facts: kept, + } + } + retract => retract, + } +} + +/// A value, weighted to small integers and entities so that facts share +/// values and joins on them match. +fn arb_dense_v() -> impl Strategy { + prop_oneof![ + 3 => (0i64..3).prop_map(V::Int), + 2 => (0..ENTITIES).prop_map(V::Ref), + 2 => arb_v(), + ] +} + +fn arb_dense_triple() -> impl Strategy { + (0..ENTITIES, 0..ATTRS.len(), arb_dense_v()) +} + +/// Larger batches than the model-based test's, without its hot triple, so +/// that a history leaves many live facts to join. +fn arb_dense_transact() -> impl Strategy { + ( + arb_window(), + prop::collection::vec((arb_dense_triple(), arb_window()), 1..10), + ) + .prop_map(|(window, facts)| { + accepted(Stmt::Transact { + window, + facts: facts + .into_iter() + .map(|((e, a, v), window)| FactSpec { e, a, v, window }) + .collect(), + }) + }) +} + +fn arb_dense_retract() -> impl Strategy { + prop::collection::vec(arb_dense_triple(), 1..4).prop_map(|facts| Stmt::Retract { facts }) +} + +fn arb_history_op() -> impl Strategy { + prop_oneof![ + 6 => arb_dense_transact().prop_map(HistoryOp::Exec), + 2 => arb_dense_retract().prop_map(HistoryOp::Exec), + 2 => prop::collection::vec( + prop_oneof![3 => arb_dense_transact(), 2 => arb_dense_retract()], + 1..5, + ) + .prop_map(HistoryOp::WriteTx), + 2 => Just(HistoryOp::Checkpoint), + ] +} + +fn arb_history() -> impl Strategy> { + prop::collection::vec(arb_history_op(), 1..17).prop_map(v2_safe) +} + +/// Leave out the writes that hit v2.x known issues (#421): a second value of +/// one entity and attribute in a transaction, by assertion or retraction +/// (#371, which also covers a retract and re-assert in one transaction, +/// #477), and an assertion of a triple that is already live (#435). A +/// retraction followed by an assertion in a later transaction stays. +fn v2_safe(history: Vec) -> Vec { + let mut model = Model::default(); + let mut out = Vec::new(); + for op in history { + let (stmts, write_tx) = match op { + HistoryOp::Exec(stmt) => (vec![stmt], false), + HistoryOp::WriteTx(stmts) => (stmts, true), + HistoryOp::Checkpoint => { + out.push(HistoryOp::Checkpoint); + continue; + } + }; + let live = model.live(None); + let mut touched: Vec<(usize, usize)> = Vec::new(); + let mut kept = Vec::new(); + for stmt in stmts { + match stmt { + Stmt::Transact { window, facts } => { + let mut ok = Vec::new(); + for f in facts { + let is_live = live.iter().any(|l| l.e == f.e && l.a == f.a && l.v == f.v); + if !touched.contains(&(f.e, f.a)) && !is_live { + touched.push((f.e, f.a)); + ok.push(f); + } + } + if !ok.is_empty() { + kept.push(Stmt::Transact { window, facts: ok }); + } + } + Stmt::Retract { facts } => { + let mut ok = Vec::new(); + for (e, a, v) in facts { + if !touched.contains(&(e, a)) { + touched.push((e, a)); + ok.push((e, a, v)); + } + } + if !ok.is_empty() { + kept.push(Stmt::Retract { facts: ok }); + } + } + } + } + if kept.is_empty() { + continue; + } + model.commit(&kept); + out.push(if write_tx { + HistoryOp::WriteTx(kept) + } else { + HistoryOp::Exec(kept.remove(0)) + }); + } + out +} + +// ── Queries (#386) ──────────────────────────────────────────────────────────── + +/// A query variable: entity-like (`?e0`–`?e2`, in E or V position), value +/// (`?v0`–`?v2`, V position only) or the attribute variable `?a`. +#[derive(Clone, Copy, Debug, PartialEq)] +enum Var { + E(u8), + V(u8), + A, +} + +impl Var { + fn name(self) -> String { + match self { + Var::E(i) => format!("?e{i}"), + Var::V(i) => format!("?v{i}"), + Var::A => "?a".to_string(), + } + } +} + +#[derive(Clone, Debug, PartialEq)] +enum Term { + Var(Var), + Entity(usize), + Const(V), + Blank, +} + +#[derive(Clone, Debug)] +struct Pat { + e: Term, + /// `None` is the attribute variable `?a`. + a: Option, + v: Term, +} + +impl Pat { + fn vars(&self) -> Vec { + let mut out = Vec::new(); + if let Term::Var(x) = self.e { + out.push(x); + } + if self.a.is_none() { + out.push(Var::A); + } + if let Term::Var(x) = self.v { + out.push(x); + } + out + } + + fn edn(&self) -> String { + let term = |t: &Term| match t { + Term::Var(x) => x.name(), + Term::Entity(e) => format!(":e{e}"), + Term::Const(v) => v.edn(), + Term::Blank => "_".to_string(), + }; + let a = self.a.map_or("?a".to_string(), |a| ATTRS[a].to_string()); + format!("[{} {a} {}]", term(&self.e), term(&self.v)) + } +} + +#[derive(Clone, Debug)] +enum Neg { + Not(Pat), + /// `(not-join [?x] [?x a v])`, with `v` a fresh `?z` when `None`. + NotJoin { + var: Var, + a: usize, + v: Option, + }, +} + +#[derive(Clone, Copy, Debug)] +enum CmpOp { + Lt, + Le, + Gt, + Ge, + Eq, + Ne, +} + +impl CmpOp { + fn edn(self) -> &'static str { + match self { + CmpOp::Lt => "<", + CmpOp::Le => "<=", + CmpOp::Gt => ">", + CmpOp::Ge => ">=", + CmpOp::Eq => "=", + CmpOp::Ne => "!=", + } + } +} + +#[derive(Clone, Debug)] +enum Operand { + Var(Var), + Const(V), +} + +#[derive(Clone, Debug)] +struct Pred { + op: CmpOp, + l: Var, + r: Operand, +} + +#[derive(Clone, Copy, Debug)] +struct Temporal { + /// Raw `:as-of`; reduced modulo (tx count + 2) when the query runs. + as_of: Option, + at: At, +} + +#[derive(Clone, Copy, Debug)] +enum At { + Now, + /// An index into `AT_YEARS`. + Year(usize), + Any, +} + +#[derive(Clone, Debug)] +struct Query { + pats: Vec, + neg: Option, + pred: Option, + temporal: Temporal, + /// The variables in `:find`, in order. + find: Vec, +} + +/// Variables bound by the patterns, in order of first appearance. +fn bound_vars(pats: &[Pat]) -> Vec { + let mut out: Vec = Vec::new(); + for x in pats.iter().flat_map(Pat::vars) { + if !out.contains(&x) { + out.push(x); + } + } + out +} + +impl Query { + fn edn(&self, tx_count: u64) -> String { + let mut opts = String::new(); + if let Some(n) = self.as_of(tx_count) { + opts.push_str(&format!(":as-of {n} ")); + } + match self.temporal.at { + At::Now => {} + At::Year(i) => opts.push_str(&format!(":valid-at \"{}-01-01\" ", AT_YEARS[i])), + At::Any => opts.push_str(":any-valid-time "), + } + let mut clauses: Vec = self.pats.iter().map(Pat::edn).collect(); + match &self.neg { + None => {} + Some(Neg::Not(p)) => clauses.push(format!("(not {})", p.edn())), + Some(Neg::NotJoin { var, a, v }) => { + let v = v.as_ref().map_or("?z".to_string(), V::edn); + let x = var.name(); + clauses.push(format!("(not-join [{x}] [{x} {} {v}])", ATTRS[*a])); + } + } + if let Some(p) = &self.pred { + let r = match &p.r { + Operand::Var(x) => x.name(), + Operand::Const(v) => v.edn(), + }; + clauses.push(format!("[({} {} {r})]", p.op.edn(), p.l.name())); + } + let find: Vec = self.find.iter().map(|x| x.name()).collect(); + format!( + "(query [:find {} {opts}:where {}])", + find.join(" "), + clauses.join(" ") + ) + } + + fn as_of(&self, tx_count: u64) -> Option { + self.temporal.as_of.map(|n| u64::from(n) % (tx_count + 2)) + } + + /// Rows are compared as multisets when each binding is a distinct row: + /// every variable is in `:find` and no pattern has `_`. + fn distinct_rows(&self) -> bool { + self.find.len() == bound_vars(&self.pats).len() + && self + .pats + .iter() + .all(|p| p.e != Term::Blank && p.v != Term::Blank) + } +} + +fn arb_e_term() -> impl Strategy { + prop_oneof![ + 4 => (0u8..3).prop_map(|i| Term::Var(Var::E(i))), + 1 => (0..ENTITIES).prop_map(Term::Entity), + ] +} + +fn arb_v_term() -> impl Strategy { + prop_oneof![ + 4 => (0u8..3).prop_map(|i| Term::Var(Var::V(i))), + 2 => (0u8..3).prop_map(|i| Term::Var(Var::E(i))), + 1 => arb_dense_v().prop_map(Term::Const), + 1 => Just(Term::Blank), + ] +} + +fn arb_pat() -> impl Strategy { + ( + arb_e_term(), + prop::option::weighted(0.9, 0..ATTRS.len()), + arb_v_term(), + ) + .prop_map(|(e, a, v)| Pat { e, a, v }) +} + +fn arb_cmp() -> impl Strategy { + prop_oneof![ + Just(CmpOp::Lt), + Just(CmpOp::Le), + Just(CmpOp::Gt), + Just(CmpOp::Ge), + Just(CmpOp::Eq), + Just(CmpOp::Ne), + ] +} + +/// Raw query parts; `build_query` turns them into a well-formed query. +type RawQuery = ( + Vec, + Option<(bool, Pat, usize, Option)>, + Option<(CmpOp, bool, V)>, + Temporal, + Vec, + (usize, usize), +); + +fn arb_temporal() -> impl Strategy { + ( + prop::option::weighted(0.4, any::()), + prop_oneof![ + 2 => Just(At::Now), + 2 => (0..AT_YEARS.len()).prop_map(At::Year), + 1 => Just(At::Any), + ], + ) + .prop_map(|(as_of, at)| Temporal { as_of, at }) +} + +fn arb_query() -> impl Strategy { + ( + prop::collection::vec(arb_pat(), 1..4), + prop::option::weighted( + 0.35, + ( + any::(), + arb_pat(), + 0..ATTRS.len(), + prop::option::of(arb_dense_v()), + ), + ), + prop::option::weighted(0.35, (arb_cmp(), any::(), arb_dense_v())), + arb_temporal(), + prop::collection::vec(any::(), 8), + (any::(), any::()), + ) + .prop_map(build_query) +} + +/// Pick the `n`-th (mod len) of `vars` that satisfies `ok`. +fn pick(vars: &[Var], n: usize, ok: impl Fn(Var) -> bool) -> Option { + let cands: Vec = vars.iter().copied().filter(|x| ok(*x)).collect(); + (!cands.is_empty()).then(|| cands[n % cands.len()]) +} + +fn build_query(raw: RawQuery) -> Query { + let (mut pats, neg, pred, temporal, find_mask, (n1, n2)) = raw; + + // At least one variable, so `:find` is not empty. + if bound_vars(&pats).is_empty() { + pats[0].e = Term::Var(Var::E(0)); + } + // Each pattern after the first shares a variable with the ones before it + // when they bind any, so no query is a cross product. + for i in 1..pats.len() { + let before = bound_vars(&pats[..i]); + if before.is_empty() || pats[i].vars().iter().any(|x| before.contains(x)) { + continue; + } + let pat = &mut pats[i]; + if let Some(x) = pick(&before, n1 + i, |x| matches!(x, Var::E(_))) { + pat.e = Term::Var(x); + } else if let Some(x) = pick(&before, n1 + i, |x| x != Var::A) { + pat.v = Term::Var(x); + } else { + pat.a = None; + } + } + let bound = bound_vars(&pats); + + let neg = neg.and_then(|(plain, mut p, a, v)| { + if plain { + // `not` over bound variables only: an unbound one becomes `_`. + let fix = |t: &mut Term, pos_e: bool| { + if let Term::Var(x) = *t + && (!bound.contains(&x) || (pos_e && matches!(x, Var::V(_)))) + { + *t = if pos_e { Term::Entity(0) } else { Term::Blank }; + } + }; + fix(&mut p.e, true); + fix(&mut p.v, false); + if p.a.is_none() && !bound.contains(&Var::A) { + p.a = Some(a); + } + Some(Neg::Not(p)) + } else { + pick(&bound, n2, |x| matches!(x, Var::E(_))).map(|var| Neg::NotJoin { var, a, v }) + } + }); + + let pred = pred.and_then(|(op, var_rhs, c)| { + // Mostly a value variable: orderings over entities are type errors. + let l = pick(&bound, n1, |x| matches!(x, Var::V(_))) + .or_else(|| pick(&bound, n1, |x| x != Var::A))?; + let r = match pick(&bound, n2, |x| x != Var::A && x != l) { + Some(x) if var_rhs => Operand::Var(x), + // Expressions take no `#uuid` literal (PRS-070). + _ if matches!(c, V::Ref(_)) => Operand::Const(V::Int(1)), + _ => Operand::Const(c), + }; + Some(Pred { op, l, r }) + }); + + let mut find: Vec = bound + .iter() + .zip(find_mask.iter().cycle()) + .filter(|(_, keep)| **keep) + .map(|(x, _)| *x) + .collect(); + if find.is_empty() { + find.push(bound[n1 % bound.len()]); + } + + Query { + pats, + neg, + pred, + temporal, + find, + } +} + +// ── Reference query evaluator (#386) ────────────────────────────────────────── + +/// A bound value: a pool value (entities are `V::Ref`) or an attribute. +#[derive(Clone, Debug, PartialEq)] +enum B { + Val(V), + Attr(usize), +} + +impl B { + fn render(&self) -> String { + match self { + B::Val(v) => v.render(), + B::Attr(a) => attr_render(*a), + } + } +} + +type Binding = Vec<(Var, B)>; + +fn lookup(b: &Binding, x: Var) -> Option<&B> { + b.iter().find(|(y, _)| *y == x).map(|(_, v)| v) +} + +/// Unify `term` with `value` under `b`; `None` when they conflict. +fn unify(mut b: Binding, term: &Term, value: B) -> Option { + match term { + Term::Blank => Some(b), + Term::Entity(e) => (value == B::Val(V::Ref(*e))).then_some(b), + Term::Const(c) => (value == B::Val(c.clone())).then_some(b), + Term::Var(x) => match lookup(&b, *x) { + Some(bound) => (*bound == value).then_some(b), + None => { + b.push((*x, value)); + Some(b) + } + }, + } +} + +/// Match one pattern against one fact under `b`. +fn match_fact(b: &Binding, p: &Pat, f: &Live) -> Option { + let mut b = unify(b.clone(), &p.e, B::Val(V::Ref(f.e)))?; + b = match p.a { + Some(a) => (a == f.a).then_some(b)?, + None => unify(b, &Term::Var(Var::A), B::Attr(f.a))?, + }; + unify(b, &p.v, B::Val(f.v.clone())) +} + +/// `eval_binop` for a comparison: `None` is a type error, which drops the row. +fn compare(op: CmpOp, l: &B, r: &B) -> Option { + match op { + CmpOp::Eq => return Some(l == r), + CmpOp::Ne => return Some(l != r), + _ => {} + } + let num = |b: &B| match b { + B::Val(V::Int(n)) => Some(*n as f64), + B::Val(V::Float) => Some(1.5), + _ => None, + }; + let ord = match (l, r) { + (B::Val(V::Str(a)), B::Val(V::Str(b))) => Some(pool_string(*a).cmp(&pool_string(*b))), + _ => num(l)?.partial_cmp(&num(r)?), + }?; + Some(match op { + CmpOp::Lt => ord.is_lt(), + CmpOp::Le => ord.is_le(), + CmpOp::Gt => ord.is_gt(), + CmpOp::Ge => ord.is_ge(), + CmpOp::Eq | CmpOp::Ne => unreachable!(), + }) +} + +fn ref_query(model: &Model, q: &Query) -> Vec { + let at = match q.temporal.at { + At::Now => Some(None), + At::Year(i) => Some(Some(jan1_ms(AT_YEARS[i]))), + At::Any => None, + }; + let facts: Vec = model + .live(q.as_of(model.tx_count)) + .into_iter() + .filter(|l| at.is_none_or(|at| valid_at(l.window, at))) + .collect(); + + let mut bindings: Vec = vec![Vec::new()]; + for p in &q.pats { + bindings = bindings + .iter() + .flat_map(|b| facts.iter().filter_map(|f| match_fact(b, p, f))) + .collect(); + } + match &q.neg { + None => {} + Some(Neg::Not(p)) => { + bindings.retain(|b| !facts.iter().any(|f| match_fact(b, p, f).is_some())); + } + Some(Neg::NotJoin { var, a, v }) => { + bindings.retain(|b| { + let x = lookup(b, *var); + !facts.iter().any(|f| { + x == Some(&B::Val(V::Ref(f.e))) + && f.a == *a + && v.as_ref().is_none_or(|v| *v == f.v) + }) + }); + } + } + if let Some(p) = &q.pred { + bindings.retain(|b| { + let l = lookup(b, p.l); + let r = match &p.r { + Operand::Var(x) => lookup(b, *x).cloned(), + Operand::Const(c) => Some(B::Val(c.clone())), + }; + match (l, r) { + (Some(l), Some(r)) => compare(p.op, l, &r) == Some(true), + _ => false, + } + }); + } + bindings + .iter() + .map(|b| { + q.find + .iter() + .map(|x| lookup(b, *x).map_or("?".to_string(), B::render)) + .collect::>() + .join(" ") + }) + .collect() +} + +// ── Driver (#386) ───────────────────────────────────────────────────────────── + +#[derive(Clone, Copy, Debug)] +enum Reopen { + Default, + SmallCache, +} + +fn open(path: &Path, mode: Reopen) -> Result { + let opts = OpenOptions::new().synchronous(SyncMode::Normal); + let opts = match mode { + Reopen::Default => opts, + Reopen::SmallCache => opts.page_cache_size(4), + }; + Minigraf::open_with_options(path, opts) + .map_err(|e| TestCaseError::fail(format!("open failed ({})", e.code()))) +} + +/// Write `history` to `db` and the model. `Checkpoint` runs only when +/// `checkpoints` is set (the file backend). +fn write_history( + db: &Minigraf, + model: &mut Model, + history: &[HistoryOp], + checkpoints: bool, +) -> Result<(), TestCaseError> { + let fail = |what: &str, i: usize, code: &str| { + TestCaseError::fail(format!("op {i}: {what} failed ({code})")) + }; + for (i, op) in history.iter().enumerate() { + match op { + HistoryOp::Exec(stmt) => { + db.execute(&stmt.edn()) + .map_err(|e| fail("write", i, e.code()))?; + model.commit(std::slice::from_ref(stmt)); + } + HistoryOp::WriteTx(stmts) => { + let mut tx = db.begin_write().map_err(|e| fail("begin", i, e.code()))?; + for stmt in stmts { + tx.execute(&stmt.edn()) + .map_err(|e| fail("statement", i, e.code()))?; + } + tx.commit().map_err(|e| fail("commit", i, e.code()))?; + model.commit(stmts); + } + HistoryOp::Checkpoint => { + if checkpoints { + db.checkpoint() + .map_err(|e| fail("checkpoint", i, e.code()))?; + } + } + } + } + Ok(()) +} + +fn check_queries( + db: &Minigraf, + ctx: &Ctx, + model: &Model, + queries: &[Query], + stage: &str, +) -> Result<(), TestCaseError> { + prop_assert_eq!(db.current_tx_count(), model.tx_count, "{}: tx count", stage); + for q in queries { + let edn = q.edn(model.tx_count); + let got: Vec = ctx + .rows(db, &edn)? + .into_iter() + .map(|r| r.join(" ")) + .collect(); + let want = ref_query(model, q); + if q.distinct_rows() { + prop_assert_eq!(sorted(got), sorted(want), "{}: {}", stage, edn); + } else { + let set = |rows: Vec| { + let mut rows = sorted(rows); + rows.dedup(); + rows + }; + prop_assert_eq!(set(got), set(want), "{}: {}", stage, edn); + } + } + Ok(()) +} + +fn ctx() -> Ctx { + Ctx { + uuids: (0..ENTITIES).map(|i| (entity_uuid(i), i)).collect(), + } +} + +fn run_in_memory(history: &[HistoryOp], queries: &[Query]) -> Result<(), TestCaseError> { + let db = Minigraf::in_memory().map_err(|_| TestCaseError::fail("in_memory failed"))?; + let mut model = Model::default(); + write_history(&db, &mut model, history, false)?; + check_queries(&db, &ctx(), &model, queries, "in memory") +} + +fn run_file_backed( + history: &[HistoryOp], + queries: &[Query], + reopen: Reopen, +) -> Result<(), TestCaseError> { + let dir = tempfile::tempdir().map_err(|_| TestCaseError::fail("tempdir"))?; + let path = dir.path().join("prop.graph"); + let ctx = ctx(); + let mut model = Model::default(); + let db = open(&path, Reopen::Default)?; + write_history(&db, &mut model, history, true)?; + check_queries(&db, &ctx, &model, queries, "file, open")?; + drop(db); + let db = open(&path, reopen)?; + check_queries(&db, &ctx, &model, queries, "file, reopened") +} + +fn cases() -> u32 { + std::env::var("PROPTEST_CASES") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(256) +} + +proptest! { + #![proptest_config(ProptestConfig::with_cases(cases()))] + + /// Joins, negation, predicates and temporal queries over a random history + /// match the reference evaluator. + #[test] + fn query_matches_reference_in_memory( + history in arb_history(), + queries in prop::collection::vec(arb_query(), 1..5), + ) { + run_in_memory(&history, &queries)?; + } +} + +proptest! { + #![proptest_config(ProptestConfig::with_cases((cases() / 10).max(1)))] + + /// The same against a file: checkpoints within the history, and queries + /// both on the open handle and after a reopen. + #[test] + fn query_matches_reference_file_backed( + history in arb_history(), + queries in prop::collection::vec(arb_query(), 1..5), + reopen in prop_oneof![Just(Reopen::Default), Just(Reopen::SmallCache)], + ) { + run_file_backed(&history, &queries, reopen)?; + } +} diff --git a/tests/reference_model/mod.rs b/tests/reference_model/mod.rs new file mode 100644 index 0000000000..42abc8b26e --- /dev/null +++ b/tests/reference_model/mod.rs @@ -0,0 +1,483 @@ +//! Reference model shared by the model-based test (#385) and the property +//! tests (#386): value pools, the valid-time grid, statements, and the +//! bi-temporal log that decides which facts a query sees. +#![allow(dead_code)] + +use minigraf::db::Minigraf; +use minigraf::{MinigrafError, QueryResult, Value}; +use proptest::prelude::*; +use proptest::test_runner::TestCaseError; +use std::collections::HashMap; +use uuid::Uuid; + +// ── Pools ───────────────────────────────────────────────────────────────────── + +pub const ENTITIES: usize = 4; +pub const ATTRS: [&str; 3] = [":a0", ":a1", ":tag/丿"]; + +/// String pool. Indices 3 and 4 are longer than the 64-byte inline limit and +/// share their first 40 bytes; index 5 fills most of a value page. +pub fn pool_string(i: u8) -> String { + match i { + 0 => "x".to_string(), + 1 => "y".to_string(), + 2 => String::new(), + 3 => format!("{}{}", "p".repeat(40), "A".repeat(40)), + 4 => format!("{}{}", "p".repeat(40), "B".repeat(40)), + _ => "z".repeat(3000), + } +} + +/// A value from the pool. Debug output carries pool indices, never a `Uuid`. +#[derive(Clone, Debug, PartialEq)] +pub enum V { + Int(i64), + Bool(bool), + Kw, + Float, + Str(u8), + Ref(usize), +} + +impl V { + pub fn edn(&self) -> String { + match self { + V::Int(n) => n.to_string(), + V::Bool(b) => b.to_string(), + V::Kw => ":k0".to_string(), + V::Float => "1.5".to_string(), + V::Str(i) => format!("\"{}\"", pool_string(*i)), + V::Ref(e) => format!("#uuid \"{}\"", entity_uuid(*e)), + } + } + + pub fn render(&self) -> String { + match self { + V::Int(n) => format!("i{n}"), + V::Bool(b) => format!("b{b}"), + V::Kw => "k:k0".to_string(), + V::Float => "f1.5".to_string(), + V::Str(i) => render_str(&pool_string(*i)), + V::Ref(e) => format!("r{e}"), + } + } +} + +pub fn render_str(s: &str) -> String { + if s.len() <= 16 { + format!("s\"{s}\"") + } else { + let head: String = s.chars().take(4).collect(); + let tail: String = s.chars().skip(s.chars().count() - 4).collect(); + format!("s\"{head}..{tail}\"#{}", s.len()) + } +} + +pub fn entity_uuid(idx: usize) -> Uuid { + Uuid::new_v5(&Uuid::NAMESPACE_OID, format!(":e{idx}").as_bytes()) +} + +/// Render an engine value like the model renders its own (`V::render`). +pub fn render_value(v: &Value, uuids: &HashMap) -> String { + match v { + Value::Integer(n) => format!("i{n}"), + Value::Boolean(b) => format!("b{b}"), + Value::Keyword(k) => format!("k{k}"), + Value::Float(f) => format!("f{f}"), + Value::String(s) => render_str(s), + Value::Ref(u) => match uuids.get(u) { + Some(i) => format!("r{i}"), + None => "r?".to_string(), + }, + Value::Null => "null".to_string(), + } +} + +// ── Time grid ───────────────────────────────────────────────────────────────── + +/// Unix ms of January 1st of `year`, UTC. +pub fn jan1_ms(year: i64) -> i64 { + // Days from 1970-01-01 to year-01-01 (proleptic Gregorian). + let y = year - 1; + let days = + 365 * (y - 1969) + (y / 4 - 1969 / 4) - (y / 100 - 1969 / 100) + (y / 400 - 1969 / 400); + days * 86_400_000 +} + +pub const VF_YEARS: [i64; 4] = [2000, 2002, 2004, 2006]; +pub const VT_YEARS: [i64; 4] = [2003, 2005, 2007, 2200]; +/// `:valid-at` instants: every window bound, plus points before, between and after. +pub const AT_YEARS: [i64; 12] = [ + 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2100, 2300, +]; +pub const FOREVER: i64 = i64::MAX; + +/// An optional `:valid-from` / `:valid-to` (grid indices). +#[derive(Clone, Copy, Debug, Default, PartialEq)] +pub struct Window { + pub vf: Option, + pub vt: Option, +} + +impl Window { + pub fn is_empty(&self) -> bool { + self.vf.is_none() && self.vt.is_none() + } + + pub fn edn(&self) -> String { + let mut parts = Vec::new(); + if let Some(i) = self.vf { + parts.push(format!(":valid-from \"{}-01-01\"", VF_YEARS[i as usize])); + } + if let Some(i) = self.vt { + parts.push(format!(":valid-to \"{}-01-01\"", VT_YEARS[i as usize])); + } + format!("{{{}}}", parts.join(" ")) + } +} + +/// An effective valid-time window: `valid_from` is `None` when it is the +/// transaction time (some instant between 2026 and 2100, before "now"). +pub type Effective = (Option, i64); + +pub fn effective(tx: Window, fact: Window) -> Effective { + let vf = fact.vf.or(tx.vf).map(|i| jan1_ms(VF_YEARS[i as usize])); + let vt = fact + .vt + .or(tx.vt) + .map_or(FOREVER, |i| jan1_ms(VT_YEARS[i as usize])); + (vf, vt) +} + +pub fn window_is_valid((vf, vt): Effective) -> bool { + match vf { + Some(vf) => vf < vt, + None => vt > jan1_ms(2100), + } +} + +/// When to read: `None` = now (no `:valid-at`), `Some(ms)` = a grid instant. +pub fn valid_at(window: Effective, at: Option) -> bool { + let (vf, vt) = window; + match at { + None => vt == FOREVER || vt > jan1_ms(2100), + Some(t) => { + let starts = match vf { + Some(vf) => vf <= t, + None => t >= jan1_ms(2100), + }; + starts && t < vt + } + } +} + +// ── Operations ──────────────────────────────────────────────────────────────── + +#[derive(Clone, Debug)] +pub struct FactSpec { + pub e: usize, + pub a: usize, + pub v: V, + pub window: Window, +} + +#[derive(Clone, Debug)] +pub enum Stmt { + Transact { + window: Window, + facts: Vec, + }, + Retract { + facts: Vec<(usize, usize, V)>, + }, +} + +impl Stmt { + pub fn edn(&self) -> String { + match self { + Stmt::Transact { window, facts } => { + let facts: Vec = facts + .iter() + .map(|f| { + let w = if f.window.is_empty() { + String::new() + } else { + format!(" {}", f.window.edn()) + }; + format!("[:e{} {} {}{w}]", f.e, ATTRS[f.a], f.v.edn()) + }) + .collect(); + let w = if window.is_empty() { + String::new() + } else { + format!("{} ", window.edn()) + }; + format!("(transact {w}[{}])", facts.join(" ")) + } + Stmt::Retract { facts } => { + let facts: Vec = facts + .iter() + .map(|(e, a, v)| format!("[:e{e} {} {}]", ATTRS[*a], v.edn())) + .collect(); + format!("(retract [{}])", facts.join(" ")) + } + } + } +} + +// ── Strategies ──────────────────────────────────────────────────────────────── + +pub fn arb_v() -> impl Strategy { + prop_oneof![ + 3 => (0i64..3).prop_map(V::Int), + 1 => Just(V::Int(i64::MIN)), + 1 => any::().prop_map(V::Bool), + 1 => Just(V::Kw), + 1 => Just(V::Float), + 3 => (0u8..6).prop_map(V::Str), + 2 => (0..ENTITIES).prop_map(V::Ref), + ] +} + +pub fn arb_window() -> impl Strategy { + prop_oneof![ + 3 => Just(Window::default()), + 2 => (prop::option::of(0u8..4), prop::option::of(0u8..4)) + .prop_map(|(vf, vt)| Window { vf, vt }), + ] +} + +/// A triple; often the same hot one, so that a triple builds a history longer +/// than the on-disk scan's seek threshold (8 entries). +pub fn arb_triple() -> impl Strategy { + prop_oneof![ + 2 => (0..ENTITIES, 0..ATTRS.len(), arb_v()), + 1 => Just((0, 0, V::Int(0))), + ] +} + +pub fn arb_transact() -> impl Strategy { + ( + arb_window(), + prop::collection::vec((arb_triple(), arb_window()), 1..6), + prop::option::weighted(0.15, arb_window()), + prop::bool::weighted(0.9), + ) + .prop_map(|(window, facts, repeat, fix_windows)| { + let mut facts: Vec = facts + .into_iter() + .map(|((e, a, v), w)| FactSpec { e, a, v, window: w }) + .collect(); + // Sometimes the same triple twice: an identical repeat or, when the + // windows differ, an API-011 rejection. + if let Some(w) = repeat { + let mut again = facts[0].clone(); + again.window = w; + facts.push(again); + } + // Usually an empty or inverted window is rewritten to start in + // 2000 (every `:valid-to` on the grid is later); otherwise the + // statement is an API-019 rejection (#436). + for f in fix_windows.then_some(&mut facts).into_iter().flatten() { + if !window_is_valid(effective(window, f.window)) { + f.window.vf = Some(0); + } + } + Stmt::Transact { window, facts } + }) +} + +pub fn arb_retract() -> impl Strategy { + prop::collection::vec(arb_triple(), 1..4).prop_map(|facts| Stmt::Retract { facts }) +} + +pub fn arb_stmt() -> impl Strategy { + prop_oneof![3 => arb_transact(), 2 => arb_retract()] +} + +// ── Reference model ─────────────────────────────────────────────────────────── + +#[derive(Clone, Debug)] +pub struct Record { + pub tx: u64, + pub e: usize, + pub a: usize, + pub v: V, + pub window: Effective, + pub asserted: bool, +} + +/// A live fact: one window per triple, from its newest assertion (#435). +#[derive(Clone, Debug)] +pub struct Live { + pub e: usize, + pub a: usize, + pub v: V, + pub window: Effective, + pub tx: u64, +} + +#[derive(Default)] +pub struct Model { + pub log: Vec, + pub tx_count: u64, +} + +impl Model { + /// The error code a statement is rejected with, if any: API-019 for an + /// empty or inverted window (#436), then API-011 for one triple with two + /// windows in the statement. + pub fn verdict(stmt: &Stmt) -> Option<&'static str> { + let Stmt::Transact { window, facts } = stmt else { + return None; + }; + let windows: Vec = facts.iter().map(|f| effective(*window, f.window)).collect(); + if !windows.iter().all(|w| window_is_valid(*w)) { + return Some("API-019"); + } + for (i, x) in facts.iter().enumerate() { + for (j, y) in facts.iter().enumerate().skip(i + 1) { + if x.e == y.e && x.a == y.a && x.v == y.v && windows[i] != windows[j] { + return Some("API-011"); + } + } + } + None + } + + /// The records a committed transaction of accepted `stmts` adds: each + /// triple's records from the last statement that wrote it (#477). + pub fn records(stmts: &[Stmt], tx: u64) -> Vec { + let mut out: Vec<(usize, Record)> = Vec::new(); + for (n, stmt) in stmts.iter().enumerate() { + match stmt { + Stmt::Transact { window, facts } => { + for f in facts { + out.push(( + n, + Record { + tx, + e: f.e, + a: f.a, + v: f.v.clone(), + window: effective(*window, f.window), + asserted: true, + }, + )); + } + } + Stmt::Retract { facts } => { + for (e, a, v) in facts { + out.push(( + n, + Record { + tx, + e: *e, + a: *a, + v: v.clone(), + window: (None, FOREVER), + asserted: false, + }, + )); + } + } + } + } + let last = |r: &Record| { + out.iter() + .filter(|(_, x)| x.e == r.e && x.a == r.a && x.v == r.v) + .map(|(n, _)| *n) + .max() + }; + out.iter() + .filter(|(n, r)| last(r) == Some(*n)) + .map(|(_, r)| r.clone()) + .collect() + } + + /// Apply a committed transaction of accepted statements. + pub fn commit(&mut self, stmts: &[Stmt]) { + if stmts.is_empty() { + return; + } + self.tx_count += 1; + self.log.extend(Self::records(stmts, self.tx_count)); + } + + pub fn live(&self, as_of: Option) -> Vec { + let limit = as_of.unwrap_or(u64::MAX); + let mut out: Vec = Vec::new(); + let mut seen: Vec<(usize, usize, &V)> = Vec::new(); + for r in &self.log { + if seen + .iter() + .any(|(e, a, v)| *e == r.e && *a == r.a && *v == &r.v) + { + continue; + } + seen.push((r.e, r.a, &r.v)); + let same = |x: &&Record| x.tx <= limit && x.e == r.e && x.a == r.a && x.v == r.v; + let newest_assert = self + .log + .iter() + .filter(same) + .filter(|x| x.asserted) + .max_by_key(|x| x.tx); + let newest_retract = self + .log + .iter() + .filter(same) + .filter(|x| !x.asserted) + .map(|x| x.tx) + .max() + .unwrap_or(0); + if let Some(a) = newest_assert.filter(|a| a.tx > newest_retract) { + out.push(Live { + e: a.e, + a: a.a, + v: a.v.clone(), + window: a.window, + tx: a.tx, + }); + } + } + out + } +} + +// ── Checks ──────────────────────────────────────────────────────────────────── + +pub struct Ctx { + pub uuids: HashMap, +} + +impl Ctx { + pub fn rows(&self, db: &Minigraf, query: &str) -> Result>, TestCaseError> { + self.result_rows(db.execute(query), query) + } + + pub fn result_rows( + &self, + result: Result, + query: &str, + ) -> Result>, TestCaseError> { + let result = result + .map_err(|e| TestCaseError::fail(format!("query failed ({}): {query}", e.code())))?; + match result { + QueryResult::QueryResults { results, .. } => Ok(results + .iter() + .map(|row| row.iter().map(|v| render_value(v, &self.uuids)).collect()) + .collect()), + _ => Err(TestCaseError::fail(format!("not a query result: {query}"))), + } + } +} + +pub fn sorted(mut rows: Vec) -> Vec { + rows.sort(); + rows +} + +pub fn attr_render(a: usize) -> String { + format!("k{}", ATTRS[a]) +}