adityamukho · Oct 19, 2026 · Oct 19, 2026 · Oct 19, 2026
@@ -46,6 +46,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **A `:db/valid-at` pattern in a rule definition binds the query's valid time** (#617). The rule evaluators never received it, so in a rule body the pattern bound `nil` and the query failed with `INT-022`; in a rule's `not` / `not-join` body it bound `nil`, so the negation never matched on it; and in a rule's `or` branch it bound the current time instead of the query's `:valid-at`. Rule bodies, their negation bodies and `or` branches now bind the query's `:valid-at` value, the current time without one, and `nil` under `:any-valid-time`, as patterns outside rules do. v2.x is affected too.
 - **An `or` / `or-join` branch whose expression reads an outer variable matches** (#620). A branch such as `[(> ?v 1)]` in `[?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])` was evaluated on its own from an empty binding and joined back afterwards, so its expression saw `?v` unbound and the branch matched nothing: the `or` silently dropped rows it should keep, in queries and in rule bodies. A branch whose expression reads a variable the branch does not bind itself is now seeded with each incoming row, as branches with `not` / `not-join` already were.
 - **An expression reading a variable only an `or` binds keeps its rows** (#625). The planner places expressions among the patterns and `not`s, and `or` / `or-join` run after them, so an expression such as `[(> ?x 1)]` in `[?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]` ran before `?x` was bound and dropped every row, on the executor, on the streaming engine and in rule bodies. Such an expression now runs after the `or`s, before the `not`s that wait for them, as those `not`s already did.
+- **A rule calling a rule with `not`, `not-join`, `or` or `or-join` gets all its rows** (#628). Stratification put a rule in the same stratum as the rules it calls, and within a stratum the rules without those clauses run first, so `(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])` ran before any `cur` row existed when `cur` had a `not-join`, and returned nothing; a caller that had a `not` or `or` of its own ran before or after its callee depending on the query. A rule now sits in a stratum above any rule with such a clause it calls, unless the two call each other.
 - **An `or` that shares no variable with the earlier clauses returns its cross product** (#610). Such an `or` — `[?x :edge ?z] (or [?p :edge :b] [?p :edge :c])` — returned no rows when no branch had `not`, `not-join` or a pseudo-attribute, because the incoming rows were replaced by the branch results. Each incoming row now joins every branch row, in queries and rule bodies. `or-join` still refuses a join variable no earlier clause binds (INT-018): it filters, it does not bind.
 - **A prepared query keeps a literal `:as-of`, `:valid-at` or `:any-valid-time`** (#603). Binding a prepared query's slots dropped any `:as-of` or `:valid-at` that was not itself a slot, so `PreparedQuery::execute` and `PreparedQuery::query` ran at the current transaction time and valid now: `(query [:find ?v :as-of 1 :where [:a :n ?v]])` prepared returned the current rows, not those at transaction 1, and a prepared per-fact pseudo-attribute query with `:any-valid-time` failed with `INT-026`. Slot forms (`:as-of $tx`, `:valid-at $t`) were not affected. Present since 2026-04-04; fixed on v2.x too.
 - **The wasm32 builds are tested again, and the browser layer no longer panics or drops pages.** The repo split (#231) moved the browser and WASI CI jobs to minigraf-wasm, which only builds the package, so core's own wasm tests stopped running and the wasm32 test build broke unnoticed. A new `wasm.yml` workflow runs the `wasm-bindgen` tests in headless Firefox and Chrome, runs the unit and integration tests on `wasm32-wasip1` under Wasmtime, and lints both targets with `clippy -D warnings`. Fixes found on the way: `BrowserDb` skipped any dirty page it could not read when flushing to IndexedDB and still reported success, and now returns the error (also fixed in v2.0.4, #470). The IndexedDB upgrade callback, the IndexedDB backend handle and the page-buffer lock no longer `unwrap()` (on wasm32 a panic aborts the whole instance). IndexedDB keys that are not whole page numbers are rejected instead of truncated. The nine `BrowserBufferBackend` tests used `#[test]`, which the wasm test runner never runs, and now run. File-only modules (`wal`, `storage::verify`, `storage::dir_sync`) are no longer compiled for wasm32, so the wasm32 builds have no warnings.

@@ -132,7 +132,7 @@ cargo run < demos/demo_negation.txt
    - `executor.rs`: Query executor — temporal filter (tx-time → net-assert → valid-time), not/not-join post-filter
    - `matcher.rs`: Pattern matching with variable unification; `edn_to_value`, `edn_to_entity_id`
    - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator`, `evaluate_not_join`
-   - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection
+   - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628)
    - `rules.rs`: `RuleRegistry` — thread-safe rule management
    - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper
    - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596); `plan_seeded` orders a body with its imported variables counted as bound, and `subplans()` lets tests force the engine's negation bodies and `or` branches hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546)
@@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1592 tests** (1582 passing, 10 ignored; unit + integration + doc).
+**1599 tests** (1589 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.

@@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1592 tests
+cargo test         # run 1599 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```
 

@@ -683,16 +683,7 @@ impl StratifiedEvaluator {
 
             for pred in &stratum_preds {
                 for rule in registry.get_rules(pred) {
-                    let has_not = rule.body.iter().any(|c| {
-                        matches!(
-                            c,
-                            WhereClause::Not(_)
-                                | WhereClause::NotJoin { .. }
-                                | WhereClause::Or(_)
-                                | WhereClause::OrJoin { .. }
-                        )
-                    });
-                    if has_not {
+                    if crate::query::datalog::stratification::has_mixed_clause(&rule.body) {
                         mixed_rules.push((pred.clone(), rule));
                     } else {
                         positive_rules.push((pred.clone(), rule));

@@ -1,6 +1,6 @@
 use crate::error::{ErrorCode, err_coded};
 use anyhow::Result;
-use std::collections::{BTreeMap, HashMap};
+use std::collections::{BTreeMap, BTreeSet, HashMap};
 
 use crate::query::datalog::rules::RuleRegistry;
 use crate::query::datalog::types::WhereClause;
@@ -38,6 +38,21 @@ fn collect_clause_deps(clause: &WhereClause, entry: &mut Vec<(String, bool)>) {
     }
 }
 
+/// Whether a rule body holds a `not`, `not-join`, `or` or `or-join`.
+/// `StratifiedEvaluator` runs such a rule once per stratum, after the
+/// positive-only rules, so a rule that calls one must sit above it (#628).
+pub(crate) fn has_mixed_clause(body: &[WhereClause]) -> bool {
+    body.iter().any(|c| {
+        matches!(
+            c,
+            WhereClause::Not(_)
+                | WhereClause::NotJoin { .. }
+                | WhereClause::Or(_)
+                | WhereClause::OrJoin { .. }
+        )
+    })
+}
+
 // ── Structs ───────────────────────────────────────────────────────────────────
 
 pub struct DependencyGraph {
@@ -46,22 +61,45 @@ pub struct DependencyGraph {
     /// A `BTreeMap` so `stratify()` walks heads in a fixed order and always
     /// reports the same pair for a given negative cycle (#410).
     edges: BTreeMap<String, Vec<(String, bool)>>,
+    /// Predicates with at least one rule for which `has_mixed_clause` holds.
+    mixed: BTreeSet<String>,
 }
 
 impl DependencyGraph {
     pub fn from_rules(registry: &RuleRegistry) -> Self {
         let mut edges: BTreeMap<String, Vec<(String, bool)>> = BTreeMap::new();
+        let mut mixed = BTreeSet::new();
 
         for (head_pred, rules) in registry.all_rules() {
             for rule in rules {
+                if has_mixed_clause(&rule.body) {
+                    mixed.insert(head_pred.to_string());
+                }
                 let entry = edges.entry(head_pred.to_string()).or_default();
                 for clause in &rule.body {
                     collect_clause_deps(clause, entry);
                 }
             }
         }
 
-        DependencyGraph { edges }
+        DependencyGraph { edges, mixed }
+    }
+
+    /// Whether `to` is reachable from `from` through one or more edges.
+    fn reaches(&self, from: &str, to: &str) -> bool {
+        let mut seen: BTreeSet<&str> = BTreeSet::new();
+        let mut stack = vec![from];
+        while let Some(p) = stack.pop() {
+            for (dep, _) in self.edges.get(p).into_iter().flatten() {
+                if dep == to {
+                    return true;
+                }
+                if seen.insert(dep.as_str()) {
+                    stack.push(dep.as_str());
+                }
+            }
+        }
+        false
     }
 
     pub fn stratify(&self) -> Result<HashMap<String, usize>> {
@@ -79,18 +117,31 @@ impl DependencyGraph {
         let mut strata: HashMap<String, usize> =
             all_predicates.into_iter().map(|p| (p, 0)).collect();
 
+        // A positive edge to a mixed predicate also needs a higher stratum,
+        // so the callee's not/or rules finish before the caller runs (#628).
+        // Not on a cycle: recursion through a mixed rule stays in one stratum.
+        let mut raised: BTreeSet<(&str, &str)> = BTreeSet::new();
+        for (head, deps) in &self.edges {
+            for (dep, is_negative) in deps {
+                if !*is_negative && self.mixed.contains(dep) && !self.reaches(dep, head) {
+                    raised.insert((head.as_str(), dep.as_str()));
+                }
+            }
+        }
+
         // Bellman-Ford-style constraint propagation
         let mut changed = true;
         while changed {
             changed = false;
             for (head, deps) in &self.edges {
                 for (dep, is_negative) in deps {
                     let dep_stratum = *strata.get(dep).unwrap_or(&0);
-                    let required = if *is_negative {
-                        dep_stratum.saturating_add(1)
-                    } else {
-                        dep_stratum
-                    };
+                    let required =
+                        if *is_negative || raised.contains(&(head.as_str(), dep.as_str())) {
+                            dep_stratum.saturating_add(1)
+                        } else {
+                            dep_stratum
+                        };
                     let head_stratum = strata.entry(head.clone()).or_insert(0);
                     if required > *head_stratum {
                         *head_stratum = required;
@@ -210,6 +261,57 @@ mod tests {
         assert!(s_eligible > s_rejected);
     }
 
+    #[test]
+    fn test_positive_edge_to_mixed_predicate_raises_caller() {
+        // #628: p →⁺ q, q has a `not`; q must finish before p runs.
        let registry =
+            make_registry_with_rules(vec![positive_rule("p", "q"), negative_rule("q", "r")]);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["p"] > strata["q"], "p above its mixed callee");
+        // A chain through a forwarding rule keeps the order.
+        let registry = make_registry_with_rules(vec![
+            positive_rule("p", "f"),
+            positive_rule("f", "q"),
+            negative_rule("q", "r"),
+        ]);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["f"] > strata["q"], "forwarding rule above q");
+        assert!(strata["p"] >= strata["f"], "p not below f");
+    }
+
+    #[test]
+    fn test_recursion_through_mixed_predicate_stratifies() {
+        // q →⁺ q with a `not` in q's body: a cycle stays in one stratum and is
+        // not rejected as unstratifiable.
+        let (_, base) = base_rule("q");
+        let (_, neg) = negative_rule("q", "r");
+        let (_, rec) = positive_rule("q", "q");
+        let mut mixed_rec = neg;
+        mixed_rec.body.extend(rec.body);
+        let mut registry = RuleRegistry::new();
+        registry.register_rule_unchecked("q".to_string(), base);
+        registry.register_rule_unchecked("q".to_string(), mixed_rec);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["q"] > strata["r"], "q above its negated r");
+    }
+
+    #[test]
+    fn test_caller_of_recursive_mixed_predicate_raised() {
+        // p →⁺ q, where q has a `not` and calls itself: q's cycle does not
+        // reach p, so p still sits above q.
+        let (_, neg) = negative_rule("q", "r");
+        let (_, rec) = positive_rule("q", "q");
+        let mut mixed_rec = neg;
+        mixed_rec.body.extend(rec.body);
+        let mut registry = make_registry_with_rules(vec![positive_rule("p", "q")]);
+        registry.register_rule_unchecked("q".to_string(), mixed_rec);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(
+            strata["p"] > strata["q"],
+            "p above its recursive mixed callee"
+        );
+    }
+
     #[test]
     fn test_negative_cycle_returns_error() {
         // p →⁻ q, q →⁻ p

@@ -554,3 +554,90 @@ fn test_not_join_expression_only_body() {
         .unwrap();
     assert_eq!(result_count(&result), 1, "only :a has ?v <= 1");
 }
+
+// ── #628: a rule calling a rule with `not` / `not-join` / `or` ───────────────
+
+fn issue_628_db() -> Minigraf {
+    let db = in_memory_db();
+    db.execute(
+        "(transact [[:m1 :msg/actor :a1]
+                    [:r1 :run/actor :a1] [:r1 :run/to :s1]
+                    [:r2 :run/actor :a1] [:r2 :run/to :s2] [:r2 :run/done true]])",
+    )
+    .unwrap();
+    db
+}
+
+#[test]
+fn test_rule_calling_not_join_rule() {
+    let db = issue_628_db();
+    db.execute(
+        "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])",
+    )
+    .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    db.execute("(rule [(st3 ?a ?s) (cur ?a ?s)])").unwrap();
+
+    let r = db
+        .execute("(query [:find ?m ?s :where [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "query calling the not-join rule");
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "rule calling the not-join rule");
+    let r = db.execute("(query [:find ?s :where (st :m1 ?s)])").unwrap();
+    assert_eq!(result_count(&r), 1, "literal argument");
+    let r = db
+        .execute("(query [:find ?a ?s :where (st3 ?a ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "forwarding rule");
+}
+
+#[test]
+fn test_rule_calling_not_rule() {
+    let db = issue_628_db();
+    db.execute("(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not [?r :run/done true])])")
+        .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "rule calling the not rule");
+}
+
+#[test]
+fn test_mixed_rule_calling_mixed_rule() {
+    let db = issue_628_db();
+    db.execute(
+        "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])",
+    )
+    .unwrap();
+    db.execute(
+        "(rule [(stm ?m ?s) [?m :msg/actor ?a] (cur ?a ?s) (not-join [?m] [?m :nope true])])",
+    )
+    .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (stm ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "caller alone");
+    let r = db
+        .execute("(query [:find ?m ?s :where (cur ?a ?x) (stm ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "callee asked first");
+}
+
+#[test]
+fn test_rule_calling_or_rule() {
+    let db = issue_628_db();
+    db.execute("(rule [(dest ?a ?s) [?r :run/actor ?a] (or [?r :run/to ?s] [?r :run/from ?s])])")
+        .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (dest ?a ?s)])")
+        .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 2, "rule calling the or rule");
+}