Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -41,6 +41,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

A lone `-` stays the subtraction operator; the grammar now lists it with the other operators. The verifier's #651 entries are removed.
- **One rule limit, `max_derived_facts`, on the total facts a rule query derives** (#553). `OpenOptions::max_derived_facts` and `:max-derived-facts` now limit every fact the rules of one query derive, across iterations and strata (the database's own facts do not count); they used to limit the new facts of one iteration. `OpenOptions::max_results` and `:max-results`, which already limited the total (#528), are deprecated aliases of it (`#[deprecated]` on the Rust field and builder method); the lower of the two applies, and a per-query value still replaces the database's. `OpenOptions::max_results` now defaults to no limit of its own, so it can lower the limit but not raise it: a caller who raised `max_results` above 1,000,000 must raise `max_derived_facts` instead. Neither ever limited the rows a query returns, whatever the name said; `:limit` (#306) will. A caller who lowered `max_derived_facts` to cap each iteration now caps the total, so a long recursion whose iterations each stayed under the limit can now fail with `INT-020`. The `INT-020` text now reads `evaluator: iteration or derived-fact limit exceeded: Max derived facts (N) exceeded. …`. The 1,000-iteration limit and the 1,000,000 default are unchanged.
- **A rule head whose entity is not an entity fails with `QRY-013`** (#548). A rule head's first argument is the entity of the fact it derives and must be a ref or a keyword; a string, number, boolean or `nil` there now fails the query with the new code `QRY-013` (`rule head entity is not an entity: rule 'named' gives a String where a ref or a keyword is needed`). A positive rule used to fail with `INT-022`, and a rule with `not`, `not-join`, `or` or `or-join` silently dropped the row. A head variable the body does not bind now fails with `INT-022` on the `not`/`or` path too, which also dropped the row.
- **A fact a rule derives has no metadata** (#548). `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read from a derived fact (`(reach ?x ?y) [?x :reach ?y] [?x :db/tx-count ?c]`) now bind `nil`, and a constant (`[?x :db/tx-count 1]`) never matches one; a stored fact with the same attribute keeps its own. They used to bind the rule evaluator's working values: the time the query ran, forever, and a counter of its own. `:db/valid-at` still binds the query's valid time.

### Added

Expand All @@ -53,6 +55,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Fixed

- **An `or` branch in a rule body knows the registered predicates** (#548). A rule with `or`/`or-join` evaluated its branches with the built-in functions only, so a predicate registered with `register_predicate` in a branch (`(or [(big? ?v)] [?x :special true])`) was unknown there. Branches now get the database's functions, as the rest of the rule body does.
- **A pseudo-attribute in a rule body reads the stored fact** (#661). In a rule without `not`, `not-join`, `or` or `or-join`, `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read the rule evaluator's working copy of the fact: valid-from was the time the query ran, valid-to forever, and the tx-count and tx-id those of the copy. With `[:a :edge :b]` valid from 2020-01-01 to 2021-01-01, `(rule [(vf ?x ?t) [?x :edge ?y] [?x :db/valid-from ?t]])` returned the query's time for `:a`; it now returns 2020-01-01, as the same pattern in a query body does. Stored data was never affected. Present since v0.15.0; fixed on v2.x too.
- **Rule queries with a literal argument return every row** (#608). Magic-sets rewriting restricts a rule to the facts its callers demand, but it took each rule's bound arguments from the first call it saw and assumed every other call matched. A call that did not — the same rule called with free arguments elsewhere in the query, a call inside `or` or `not`, a call from a rule the query calls with free arguments, or a rule-body call whose argument nothing bound yet — either failed with `INT-022` (`(chain ?x :c)` with `(chain ?x ?y) :- (link ?x ?m) (chain ?m ?y)`) or silently returned too few rows (`(link ?x :c) (link ?p ?q)` returned only the `:c` edges for `?p ?q`). A query with both arguments literal next to another rule call also lost its rows. The demand on each rule is now the one every call site supplies, and a rule some call site reads in full is evaluated in full. Present since v1.2.0.
- **A `:db/valid-at` pattern in a `not-join` body binds the query's valid time on every path** (#615). When the body also held an expression, sat in an `or` branch, or ran in a query that invokes a rule, the body bound `nil`, so `(not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])` never matched and excluded nothing; without the expression the same body excluded every entity. It now binds the query's `:valid-at` value (or the current time) as the other paths do. Present since v0.13.1; v2.x is affected too.
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -206,7 +206,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1681 tests** (1671 passing, 10 ignored; unit + integration + doc).
**1687 tests** (1677 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.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1681 tests
cargo test # run 1687 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
18 changes: 18 additions & 0 deletions docs/ERROR_REFERENCE.md
Original file line number Diff line number Diff line change
Expand Up @@ -146,6 +146,7 @@ with no `CodedError` anywhere in its chain.
| QRY-009 | Rules lock poisoned | Query Execution |
| QRY-010 | Unknown aggregate function | Query Execution |
| QRY-011 | Unknown window function | Query Execution |
| QRY-013 | Rule head entity is not an entity | Query Execution |
| STG-001 | Invalid header: too short | Storage |
| STG-002 | Invalid magic number: not a .graph file | Storage |
| STG-003 | Invalid v4/v5/v6 header too short (deprecated) | Storage |
Expand Down Expand Up @@ -2305,6 +2306,23 @@ predicate evaluation, or fact transacting.
```
*`frob` is not a window built-in; register it first*

### QRY-013 Rule head entity is not an entity

**Error text**: `rule head entity is not an entity: rule '{}' gives a {} where a ref or a keyword is needed`

**Cause**: A rule produced a head whose first argument, the entity of the fact it derives, is not an entity: a string, a number, a boolean or `nil`. Only a ref, or a keyword (which names the entity `uuidv5(keyword)`), is an entity. The head's second argument, the value, may be any value. The query that invoked the rule fails, whether the rule has `not`/`not-join`/`or`/`or-join` clauses or not. Before v3.0.0 a positive rule failed with INT-022 and a rule with `not`/`or` clauses silently dropped the row. (QRY-012 is reserved.)

**Resolution**:
- Put an entity variable first in the head: `(owner ?item ?person)`, not `(owner ?name ?item)` where `?name` binds a string.
- To derive a fact about a value, keep the entity first and the value second.

**Example**:
```datalog
(rule [(named ?n ?e) [?e :name ?n]])
(query [:find ?e :where (named ?n ?e)])
```
*`?n` binds a string, so rule `named` gives a String as its entity*

---

## STG — Storage Errors
Expand Down
2 changes: 1 addition & 1 deletion docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

111 changes: 111 additions & 0 deletions docs/superpowers/plans/2026-10-20-548-recursive.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,111 @@
# Recursive rules on the streaming engine (#548) — Plan

Spec: `docs/superpowers/specs/2026-10-20-recursive-engine-design.md`. PRs target `v3`. None
uses a closing keyword for #473; #548 closes by hand after PR 3. Prerequisites merged:
#553 (#663, one total `max_derived_facts`) and #661 (#665, pseudo-attributes in rule bodies
read the stored fact).

| PR | Steps | Branch |
|---|---|---|
| 1 | 1–7: executor rule fixes (spec §4) | `fix/548-executor-rules` |
| 2 | 8–15: `Recursive` and rule queries on the engine (spec §5) | `feat/548-recursive` |
| 3 | 16–19: acceptance and measurement (spec §7) | `feat/548-acceptance` |

Each PR leaves `v3` with no unused code, updates the test counts and `CHANGELOG.md` for what
it ships, and has a docs-site PR (`../minigraf-docs`) when it changes documented behaviour
(PR 1 does; PR 2 changes no answer; PR 3 adds measurements only).

## Design decisions not fixed by the spec

1. **How a derived fact is marked.** `Fact::new(…, 0)` already gives tx-count 0, tx-id 0,
valid-from 0 and valid-to forever. `RecursiveEvaluator` loads its delta with
`FactStorage::load_facts` and `StratifiedEvaluator`'s mixed pass with `load_fact`,
instead of `FactStorage::transact`, so the mark survives; the positive pass already
copied facts with `load_fact`. `FactStorage::transact` has no other non-test caller and
becomes `#[cfg(test)]` (writes go through `transact_batch`).
2. **Where `nil` is decided.** `PatternMatcher::metadata` returns `Value::Null` for a
tx-count-0 fact, for every per-fact pseudo-attribute. No stored fact has tx-count 0:
the counter starts at 1, the v1 migration on v2.x numbered from 1, and `LogWriter`
rejects 0 (`API-015`). Magic seeds also have tx-count 0 and are query-local; they bind
`nil` too, which matches spec §3.3 (they are not stored facts of the snapshot).
`:db/valid-at` is not per fact and is unchanged.
3. **`QRY-013`'s text** names the predicate and the kind of the value:
`rule head entity is not an entity: rule '{}' gives a {} where a ref or a keyword is
needed`, the kind from `aggregate::type_name` (made `pub(crate)`), `symbol` for a bare
symbol in the head. `QRY-012` stays reserved for #549 (a comment in `ErrorCode`).
4. **The mixed pass propagates `instantiate_head`'s error** (`?`), so an unbound head
variable is `INT-022` there too (spec §3.4), with the same text as the positive path.
5. **The function registry in rule-body `or` branches** is a read guard on
`StratifiedEvaluator::functions`, taken where `FunctionRegistry::with_builtins()` was.

## PR 1 — executor rule fixes

1. `ErrorCode::Qry013` in `src/error.rs` (enum, `REGISTRY`, the exhaustive match, `ALL`),
row and section in `docs/ERROR_REFERENCE.md`.
2. `RecursiveEvaluator::instantiate_head`: entity conversion failure is `QRY-013`.
3. `StratifiedEvaluator` mixed pass: `instantiate_head_public(…)?` replaces
`if let Ok(fact)`.
4. Derived facts tx-count 0 (decision 1); `FactStorage::transact` test-only.
5. `PatternMatcher::metadata`: `nil` for tx-count 0 (decision 2).
6. Mixed-pass `or` branches get the database's registry (decision 5).
7. Tests (`tests/recursive_rules_test.rs`): `QRY-013` on the positive, magic-set, `not`,
`not-join`, `or` and nested-`not-join` paths; keyword and ref heads still derive;
`INT-022` for an unbound head variable on both paths; `nil` metadata for facts derived
by positive and `not` rules, a stored fact of the same attribute keeping its own, a
constant matching only the stored fact; a registered predicate in a rule-body `or`
branch. Unit test `test_head_entity_must_be_an_entity` (string, integer, bare symbol;
a keyword head gives tx-count 0). `CHANGELOG.md` (two breaking entries, one fixed),
counts. Docs-site PR (`v3/548-executor-rules`): the rule-head error and the metadata
rule, `@since v3.0.0`. UniFFI binding PRs follow the new `ErrorCode` once merged.

## PR 2 — `Recursive` and rule queries on the engine

8. **Relation store** (`src/query/engine/relation.rs`): per evaluated predicate an
append-only `Vec` of `[Cell; 2]` rows, an identity `HashSet` (spec §3.2: floats by
bits with `-0.0` ≠ `0.0` and one NaN; a keyword `Iid` distinct from the `Eid` it names;
long strings by content), an entity-key index to row positions, and round boundaries
(`start_k`, `end_k`). Seeding: each stratum predicate's identity set from one scan of
its stored facts; magic seeds appended as rows before round 1. Unit tests for identity
and ranges.
9. **Derived scan source** (`plan.rs` `ScanSpec`, `scan.rs`): `derived: Option<Derived>`
with the predicates read (one for `:p`, every evaluated one for a variable or `_`
attribute, the attribute cell the ident of `:p`) and a `Range` (`Full`, `Old`,
`Delta`). `Full`/`Old` read committed, pending, then derived rows; `Delta` derived
rows only. Derived rows fill metadata columns with `nil`; entity probes use the
relation's index. Constants and bound values filter as on the other sources.
10. **Rule bodies as plans**: a `Builder` entry that plans a rule body (invocations as
`rule_invocation_to_pattern` patterns) and ends in a head projection of two cells
(entity checked as spec §5.3: `Eid`, or `Iid` via `IdSpace::keyword_eid`, else
`QRY-013`; one-argument heads project `true`). `None` (executor) when a body cannot
be planned.
11. **`Recursive`** (`src/query/engine/recursive.rs`): strata from `stratify()` over the
evaluated predicates (`all_preds` as `StratifiedEvaluator::evaluate`); round 1 every
rule `Full`; round `k > 1` one variant per same-stratum top-level invocation
(`Delta` / `Old` before / `Full` after); naive rules (spec §5.3's list, found on the
parsed body) every round, all `Full`; heads checked against the identity set,
appended at the round's end, each counted against `max_derived_facts`; `INT-020`
after `max_iterations` rounds (the empty round counts).
12. **Query body**: planned as any engine query after `Recursive`, every scan with the
derived source `Full`.
13. **Routing** (`DatalogExecutor::open_query`): a rule query goes to the engine when its
body and every evaluated rule body plan, it has no `:as-of` timestamp and no slot left,
and it is not in a write transaction (`facts_override`); else the executor. The oracle
compares both (bags, or both errors).
14. **Tests**: `tests/recursive_engine_test.rs` (spec §7's list), every query also through
the oracle; existing rule suites (`recursive_rules_test`, `negation_test`,
`disjunction_test`, `magic_sets_test`, model and property tests) now reach the engine.
15. **Binary size** against the 1,230 KiB gate (v3 ~1,211 KiB); if over, the PR says by
how much and why before the gate moves. `CHANGELOG.md` Internal entry, counts, envelope
smoke at 100K.

## PR 3 — acceptance and measurement

16. Acceptance test: a layered graph (63 layers of 50 nodes, complete bipartite edges
between neighbours, ≈ 5M `reach` facts in 63 rounds) completes with peak RSS
proportional to the derived relation; `max_derived_facts` stops a runaway rule with
`INT-020`. Ignored by default (run in the soak/bench job), as other large tests.
17. Envelope `recursive` shape (transitive closure at 100K, 1M, 10M base facts) in
`examples/perf_envelope.rs`.
18. Bench machine A/B (engine against `origin/v3`, `numactl` one node, idle machine):
wall time and peak RSS; #379 point queries must not regress.
19. Results in `CHANGELOG.md`; close #548 by hand.
10 changes: 10 additions & 0 deletions src/error.rs
Original file line number Diff line number Diff line change
Expand Up @@ -172,6 +172,8 @@ pub(crate) enum ErrorCode {
Qry009,
Qry010,
Qry011,
// QRY-012 is reserved for the query memory limit (#549).
Qry013,
Int000,
Stg001,
Stg002,
Expand Down Expand Up @@ -1069,6 +1071,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[
"unknown window function '{}' — register it with register_aggregate() before querying",
ErrorCategory::Query,
),
(
ErrorCode::Qry013,
"QRY-013",
"rule head entity is not an entity: rule '{}' gives a {} where a ref or a keyword is needed",
ErrorCategory::Query,
),
(
ErrorCode::Int000,
"INT-000",
Expand Down Expand Up @@ -2267,6 +2275,7 @@ mod tests {
| ErrorCode::Qry009
| ErrorCode::Qry010
| ErrorCode::Qry011
| ErrorCode::Qry013
| ErrorCode::Stg001
| ErrorCode::Stg002
| ErrorCode::Stg003
Expand Down Expand Up @@ -2527,6 +2536,7 @@ mod tests {
ErrorCode::Qry009,
ErrorCode::Qry010,
ErrorCode::Qry011,
ErrorCode::Qry013,
ErrorCode::Stg001,
ErrorCode::Stg002,
ErrorCode::Stg003,
Expand Down
4 changes: 4 additions & 0 deletions src/graph/storage.rs
Original file line number Diff line number Diff line change
Expand Up @@ -428,6 +428,10 @@ impl FactStorage {
///
/// # Returns
/// The TxId (timestamp) assigned to these facts
///
/// Test-only since rules stopped transacting derived facts (#548);
/// writes go through `transact_batch`.
#[cfg(test)]
pub(crate) fn transact(
&self,
fact_tuples: Vec<(EntityId, Attribute, Value)>,
Expand Down
2 changes: 1 addition & 1 deletion src/query/datalog/aggregate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -314,7 +314,7 @@ fn canonical(v: &Value) -> Value {
}

/// The type name used in error messages.
fn type_name(v: &Value) -> &'static str {
pub(crate) fn type_name(v: &Value) -> &'static str {
match v {
Value::String(_) => "String",
Value::Integer(_) => "Integer",
Expand Down
Loading
Loading