From dde61a2044e12950c70af9bf7428a0c26cd6b591 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 6 Nov 2026 16:06:09 +0530 Subject: [PATCH] feat: configurable recursion round limit (#861) OpenOptions::max_iterations sets the most rounds one stratum of a rule query may run; the default rises from a fixed 1,000 to 1,000,000, equal to max_derived_facts (a round that continues derived a new fact, so the derived-facts limit binds first). :max-iterations N|$slot replaces it per query, gated by Overridable::MaxIterations (in DEFAULTS); PreparedQuery::with_max_iterations replaces it per statement, ungated. Rounds stay per stratum. INT-020's round message says how to raise it. The database, executor, prepared queries and BrowserDb now carry one engine::Limits. Grammar, GRAMMAR.md, corpus, fuzz seed, verifier (42 tokens), docs and counts updated. Refs #861, #862 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01H2a7QoYX6tc5G3sKVzvLjD --- CHANGELOG.md | 6 + CLAUDE.md | 14 +- docs/CONFIGURATION.md | 22 ++- docs/ERROR_REFERENCE.md | 31 +-- docs/GRAMMAR.md | 7 +- docs/TEST_COVERAGE.md | 7 +- .../plans/2026-11-06-861-max-iterations.md | 67 +++++++ .../74d3f1815468c9507803f399d37f385934852f1e | 1 + src/browser/mod.rs | 25 ++- src/db.rs | 59 +++--- src/overrides.rs | 23 ++- src/query/datalog/evaluator.rs | 9 +- src/query/datalog/executor.rs | 65 +++---- src/query/datalog/parser.rs | 29 ++- src/query/datalog/parser/verifier.rs | 13 +- src/query/datalog/prepared.rs | 38 +++- src/query/datalog/types.rs | 8 +- src/query/engine/recursive.rs | 12 ++ tests/allow_overrides_test.rs | 6 +- tests/grammar/grammar.pest | 4 +- .../invalid/semantic/max_iterations_twice.edn | 1 + .../invalid/semantic/max_iterations_zero.edn | 1 + .../invalid/syntax/max_iterations_missing.edn | 1 + .../invalid/syntax/max_iterations_string.edn | 1 + tests/grammar/valid/max_iterations.edn | 1 + tests/grammar/valid/max_iterations_slot.edn | 1 + tests/limit_keywords_test.rs | 179 ++++++++++++++++++ 27 files changed, 508 insertions(+), 123 deletions(-) create mode 100644 docs/superpowers/plans/2026-11-06-861-max-iterations.md create mode 100644 fuzz/corpus/datalog_parser/74d3f1815468c9507803f399d37f385934852f1e create mode 100644 tests/grammar/invalid/semantic/max_iterations_twice.edn create mode 100644 tests/grammar/invalid/semantic/max_iterations_zero.edn create mode 100644 tests/grammar/invalid/syntax/max_iterations_missing.edn create mode 100644 tests/grammar/invalid/syntax/max_iterations_string.edn create mode 100644 tests/grammar/valid/max_iterations.edn create mode 100644 tests/grammar/valid/max_iterations_slot.edn diff --git a/CHANGELOG.md b/CHANGELOG.md index 045fd07cd4..e831114ac2 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -13,10 +13,14 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **`:query-memory-limit`, limit bind slots and `PreparedQuery` limit setters** (#870, part of #862). `:query-memory-limit N` replaces `OpenOptions::query_memory_limit` for one query, up or down; `0` is allowed and lets only a query that holds no state run (QRY-012 otherwise). It is gated by the new `Overridable::QueryMemoryLimit`, which is **not** in `Overridable::DEFAULTS`, so a database refuses it with API-025 unless the embedder lists it; `BrowserDb` always refuses it. `:max-derived-facts`, `:max-results` and `:query-memory-limit` take a `$slot` filled with `BindValue::Val(Value::Integer(n))` (INT-014/INT-015 out of range as for a literal, API-024 for another type, API-022 when missing). `PreparedQuery::with_max_derived_facts` and `with_query_memory_limit` replace the database values for one statement; they are not gated, and an allowed keyword still overrides them. See [docs/CONFIGURATION.md](docs/CONFIGURATION.md). The v3 binary-size gate rises from 1,234 to 1,240 KiB (+672 B measured here; the rest is room for #861). +- **Configurable recursion round limit** (#861, part of #862). `OpenOptions::max_iterations` sets the most rounds one stratum of a rule query may run (default 1,000,000, see Breaking changes); `:max-iterations N` or `$slot` replaces it for one query, up or down (INT-012/013/014/015 as for `:max-derived-facts`), gated by the new `Overridable::MaxIterations`, which **is** in `Overridable::DEFAULTS`; `PreparedQuery::with_max_iterations` replaces it for one statement, ungated, and an allowed keyword still overrides it. Rounds are still counted per stratum. See [docs/CONFIGURATION.md](docs/CONFIGURATION.md). + ### Changed - **INT-015 text** (#870): `{} must be a positive integer` is now `{} must be a non-negative integer`, because `:query-memory-limit` accepts 0. The code and when `:max-derived-facts`/`:max-results` raise it are unchanged. +- **INT-020 round-limit text** (#861): `Max iterations (N) exceeded. Possible infinite recursion or cycle in rules.` now reads `Max iterations (N) exceeded. A stratum's rules were still deriving new facts after N rounds; raise the limit with :max-iterations N or OpenOptions::max_iterations.` The code is unchanged. + - **Ordinary average** (#777): `(avg ?v)` no longer raises PRS-027. Grouped and ungrouped queries use the same numeric population and arithmetic as window `avg`: skip nil and nonnumeric values, sum exactly, round the total once to Float, then divide by the numeric count. Integer totals are not saturated. Results are Float, or nil for an existing group without numbers; no matching rows yields no rows. The total can overflow before division, and division rounds separately. Existing window behavior is unchanged. Retained exact-sum allocations for ordinary `sum` and `avg` are now charged to the query memory limit. - **Align ordinary aggregate value handling with windows** (#789, v3.0.0). @@ -76,6 +80,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Breaking changes +- **The recursion round limit defaults to 1,000,000 instead of 1,000** (#861). A stratum only starts another round after deriving a new fact, so its rounds never exceed the facts it derives plus one; with the round default equal to `max_derived_facts`' 1,000,000, the derived-facts limit is reached first. A rule query that needed more than 1,000 rounds — for example a transitive closure over a chain of more than about 1,000 edges — used to fail with INT-020 and now returns its rows. Set `OpenOptions::max_iterations(1_000)` to keep the old limit. + - **`Value` is `#[non_exhaustive]` and has a `Set` variant** (#316). A `match` on `Value` outside the crate needs a wildcard arm, so later value kinds are not breaking changes. - **File format v8** (#287, #371). Index keys now include the encoded value and the assert/retract flag. A v7 file (written by v2.x) is re-indexed and upgraded to v8 the first time it is opened; the upgrade is one-way and v2.x cannot open a v8 file (`STG-006`). Bindings users get this upgrade silently on open. - **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`. diff --git a/CLAUDE.md b/CLAUDE.md index 37ab973831..43513d37e2 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -163,17 +163,17 @@ cargo run < demos/demo_negation.txt 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#.`, else PRS-081 (#594) - `parser/statement.rs`: `transact`/`retract` read one fact at a time (#550): `kind_of` dispatches on the first two tokens; one pass keeps today's error order (phases 1 tokens … 6 valid windows, the earliest phase's first error, phase 3 in today's check order); `read_statement` (pass 1) keeps at most `TX_CHUNK_FACTS` materialised facts and the offset after the last, and returns phase 5–6 errors from `Statement::facts`/`Statement::chunks` (one `Chunk` at a time; pass 2 from that offset for a larger statement); `set_tx_chunk_facts` for tests (`minigraf::__tx_chunk_facts` and `__statement_facts_high_water` under `test-hooks`). The `Parser` reads tokens on demand from a `Lexer` (`keep` off checks structure without holding it); `parse_transact`/`parse_retract` remain under `cfg(test)` for the differential tests - - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 17 command templates (`parse_datalog_command`; 41 tokens); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) + - `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 17 command templates (`parse_datalog_command`; 42 tokens); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed) - `executor.rs`: `DatalogExecutor` — `transact`/`retract`/`rule` commands, and every query on the engine (`open_query`, `open_rule_query`; planner errors after the pseudo-attribute check, then every predicate the query and its rules name, `QRY-007`); its own query path is gone (#551) - `matcher.rs`: `edn_to_value`, `edn_to_entity_id` - `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: charged partition indices, in-place total sort, peers) (#547, #765) - `functions.rs`: `FunctionRegistry` (built-ins and UDFs; `Clone` shares the closures), `Functions` — the registry a database shares, `RwLock>`: a query takes a `snapshot()` when it opens and holds no lock while a UDF runs, so UDFs may call back into the database; registration copies, inserts and swaps (#180). `UdfError`: a `try_register_*` closure's failure, `QRY-014`; `eval_expr`'s `EvalError` is `NoValue` (row dropped) or `Udf` (query fails) - - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits and their errors + - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits (`DEFAULT_MAX_ITERATIONS` = `DEFAULT_MAX_DERIVED_FACTS` = 1,000,000, #861) and their errors - `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`, `Count` (`:limit`/`:offset` (#306) and `:max-derived-facts`/`:max-results`/`:query-memory-limit` (#870) literal or slot), `DatalogQuery::order_by` (`:find` elements with `Order`, #306), `DatalogQuery::distinct` (default-false bare flag, #493), `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper + - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `Count` (`:limit`/`:offset` (#306) and `:max-derived-facts`/`:max-results`/`:query-memory-limit` (#870)/`:max-iterations` (#861) literal or slot), `DatalogQuery::order_by` (`:find` elements with `Order`, #306), `DatalogQuery::distinct` (default-false bare flag, #493), `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-hooks`, #596); `plan_seeded` orders a body with its imported variables counted as bound, `plan_after` orders a rule body's clauses after its delta, each joining on a variable bound before it where one can (#694), and `subplans()` lets tests force the engine's negation bodies and `or` branches hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546) - - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`; `Entity` and `Val(Ref)` fit each other's slots, bind mistakes are `API-022`/`023`/`024` (#181); a `:limit $n` or `:offset $o` slot takes `Val(Integer(n >= 0))` (`resolve_count_slot`, #306); limit-keyword slots follow their literal range (`resolve_limit_slot`, #870); `with_max_derived_facts`/`with_query_memory_limit` replace the database limits for one statement, ungated (#870) + - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`; `Entity` and `Val(Ref)` fit each other's slots, bind mistakes are `API-022`/`023`/`024` (#181); a `:limit $n` or `:offset $o` slot takes `Val(Integer(n >= 0))` (`resolve_count_slot`, #306); limit-keyword slots follow their literal range (`resolve_limit_slot`, #870); `with_max_derived_facts`/`with_query_memory_limit`/`with_max_iterations` replace the database limits for one statement, ungated (#870, #861) - `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), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `collect.rs` (`CollectSet`, #316: `[(collect-set ?e :a) ?s]` per row probes `[e :a ?v]` as an `IndexNestedLoopJoin` does and binds the values as one set, `#{}` when none, metered; `Expr::CollectSet`, parsed only as a whole binding clause), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`; #641/#781 certify a complete grouping tuple as `Grouping::Ordered`: count/count-distinct/sum/avg, fixed-scalar extrema and Integer/nil sum-distinct; one varying ordered slot plus permitted scalar constants/repetitions, including :with (which retains Sort), no window/callback/CollectSet; one active group, bounded output batches, shared finish_group, internal DICT-cache eviction; unproved arguments and registered finalizers keep full-drain validation), `order.rs` and `order/arguments.rs` (#641/#781: snapshot-bound grouping/order and argument-domain proofs of the complete result order; safe committed integer/float/Boolean ranges can set the private `ScanSpec.index` hint to AVET and omit Sort, with `plan.find` restored from Sort.cols; entity-and-attribute scans retain EAVT; pending/staged records in that range, callbacks and CollectSet keep the original strategies; DICT comparators prove only window partition adjacency, never final Sort or aggregate group order; mixed integer/float keys can prove grouping order but keep Sort, and unique group keys discharge tie suffixes; `minigraf::__input_order` forces fallback under `test-hooks`), `sort.rs` (`Sort`, #306: the `:find` columns as values, in the full order of `:order-by` — its keys, then every other `:find` column ascending, by `datalog::aggregate::row_order`/`value_order`; under a `:limit` a heap of the best `offset + limit` rows; reads its whole input, dropping the DICT lookups after each batch, metered; its rows turned back into cells only as returned), `limit.rs` (`Limit`, #306: skips `offset` rows, passes on at most `limit`, then closes its child so nothing below reads more; planned after the last step, after `Builder::finish`, and after `Sort`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order; #641 resolves compatible built-in windows to `WindowPartitioned`, retaining one partition and charged lookahead, coalescing completed partitions into bounded output batches, evicting DICT caches at internal input/result boundaries; full-input mode keeps query-lifetime caches), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare; `:distinct` adds `DistinctFind` after aggregates/windows and before sorting/pagination, keyed on final `:find` columns by aggregate-group equality, with canonical float zero/NaN output including set elements, #493), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only; bounded stack UUID hints share DICT paths, with cache insertion and charges in projection order, #530), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`, the set a `CollectSet` builds; each entry charged by a per-entry estimate including retained set elements and strings before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. @@ -182,8 +182,8 @@ cargo run < demos/demo_negation.txt 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input) -6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`, `OpenOptions::read_only` (#429: shared lock, nothing written, writes are `API-014`), `OpenOptions::query_memory_limit` (#549: `QRY-012`, off by default), `OpenOptions::transaction_chunk_facts` (#550), `OpenOptions::allow_overrides` (#869: which query keywords may override settings, `API-025`; see `docs/CONFIGURATION.md`) - - `src/overrides.rs`: `Overridable` (`DEFAULTS`, `keyword`; `QueryMemoryLimit` not in `DEFAULTS`, #870) and `check_overrides`, called after parsing at every query entry point (`BrowserDb` uses `DEFAULTS`) +6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`, `OpenOptions::read_only` (#429: shared lock, nothing written, writes are `API-014`), `OpenOptions::query_memory_limit` (#549: `QRY-012`, off by default), `OpenOptions::transaction_chunk_facts` (#550), `OpenOptions::max_iterations` (#861: rounds per stratum, default 1,000,000), `OpenOptions::allow_overrides` (#869: which query keywords may override settings, `API-025`; see `docs/CONFIGURATION.md`) + - `src/overrides.rs`: `Overridable` (`DEFAULTS`, `keyword`; `QueryMemoryLimit` not in `DEFAULTS`, #870; `MaxIterations` in it, #861) and `check_overrides`, called after parsing at every query entry point (`BrowserDb` uses `DEFAULTS`) - `src/cursor.rs`: `Cursor` / `Batch` — owned, `Send` cursor returned by `Minigraf::query` and `PreparedQuery::query` (#432); pulls engine queries one internal batch at a time (`close`/drop stops the work; a read error after some rows comes on the next call), other queries computed at open; holds a `Snapshot` (one state of the store, its committed generation pinned, #543) until dropped - `src/fact_log.rs`: `FactLog` / `FactFilter` / `FactRecord` / `FactOrder` — every fact version streamed by `Minigraf::fact_log` (#430): tx order (multi-pass, bounded window) or storage order, key-level filters; an open log pins the committed generation (`storage::pins`), so checkpoints run but do not reuse its pages (`API-013` deprecated, #543) - `src/log_writer.rs`: `LogWriter` — builds a new file from `FactRecord`s with their tx and valid-time kept (#431): tx-ordered appends with holes (`API-015`/`API-016`), batched copy-on-write checkpoints at tx boundaries, no WAL, built at `.partial` and renamed by `finish` (`STG-043` if the target exists) @@ -245,7 +245,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**2094 tests** (2073 active, 21 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**2104 tests** (2083 active, 21 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. The #760 deterministic storage suite adds three native unit tests in a separate `--cfg minigraf_shuttle` build, outside the default count. Run only `graph::storage::deterministic::` with that cfg; ordinary unit tests do not enter its scheduler. `deterministic-schedules.yml` runs relevant v3 PRs on Linux/macOS/Windows plus Linux MSRV, and larger nightly/manual searches with replay artifacts. The identical main workflow activates the v3 schedule after both PRs merge. See `docs/testing/deterministic-schedules.md` for scope, controls and findings. diff --git a/docs/CONFIGURATION.md b/docs/CONFIGURATION.md index 9c86f96699..0217413eb4 100644 --- a/docs/CONFIGURATION.md +++ b/docs/CONFIGURATION.md @@ -20,7 +20,7 @@ code are not gated. | `max_derived_facts` | 1,000,000 | query text: `:max-derived-facts N` or `$slot`; code: `PreparedQuery::with_max_derived_facts` | Replaces the database value for that query, up or down; a keyword overrides the setter | | `max_results` (deprecated) | no limit of its own | query text: `:max-results N` or `$slot` | Alone, replaces the database value; with `:max-derived-facts`, the lower applies | | `query_memory_limit` | no limit | query text: `:query-memory-limit N` or `$slot` (not in `DEFAULTS`); code: `PreparedQuery::with_query_memory_limit` | Replaces the database value for that query, up or down; a keyword overrides the setter | -| round limit | 1000, fixed | — (`OpenOptions::max_iterations` and `:max-iterations` planned, #861) | — | +| `max_iterations` | 1,000,000 rounds per stratum | query text: `:max-iterations N` or `$slot`; code: `PreparedQuery::with_max_iterations` | Replaces the database value for that query, up or down; a keyword overrides the setter | | `transaction_chunk_facts` | 65,536 | — (per-transaction `TxOptions` planned, #871) | — | | `synchronous` | `SyncMode::Full` | — (per-transaction `TxOptions` planned, #871) | — | | `wal_checkpoint_threshold` | 1000 | open only | Database-wide checkpoint policy | @@ -42,6 +42,7 @@ database's settings, as `Overridable` variants: | `Overridable::MaxDerivedFacts` | `:max-derived-facts` | yes | | `Overridable::MaxResults` | `:max-results` | yes | | `Overridable::QueryMemoryLimit` | `:query-memory-limit` | no | +| `Overridable::MaxIterations` | `:max-iterations` | yes | The default, `Overridable::DEFAULTS`, allows every keyword that could override a setting before the list existed, so existing queries keep @@ -79,7 +80,8 @@ let opts = OpenOptions::new().allow_overrides( ``` `Overridable` is `#[non_exhaustive]`: later releases add variants for new -keywords, such as `:max-iterations` (#861, in `DEFAULTS`). +keywords. `MaxIterations` (#861) joined `DEFAULTS` in v3.0.0, so its keyword +works without configuration. `QueryMemoryLimit` is left out of `DEFAULTS` because the keyword can raise the limit that keeps a query from exhausting memory. List it to let query text @@ -97,13 +99,13 @@ db.execute("(query [:find ?x :where [?e :v ?x] :query-memory-limit 1048576])")?; ## Limit keywords -`:max-derived-facts N`, `:max-results N` and `:query-memory-limit N` take an -integer or a `$slot` that a prepared query fills with +`:max-derived-facts N`, `:max-results N`, `:max-iterations N` and +`:query-memory-limit N` take an integer or a `$slot` that a prepared query fills with `BindValue::Val(Value::Integer(n))`: | Keyword | Range | Out of range | Other value | |---|---|---|---| -| `:max-derived-facts`, `:max-results` | `n >= 1` | `INT-014` | `INT-015` (literal), `API-024` (bind value) | +| `:max-derived-facts`, `:max-results`, `:max-iterations` | `n >= 1` | `INT-014` | `INT-015` (literal), `API-024` (bind value) | | `:query-memory-limit` | `n >= 0` (bytes) | `INT-015` | `INT-015` (literal), `API-024` (bind value) | A missing bind value is `API-022`. `Minigraf::execute` and `Minigraf::query` @@ -115,9 +117,17 @@ resolve. Uncheckpointed facts and returned entities need ids, so in practice only a query over checkpointed facts that returns values runs under 0; any other query fails at once with `QRY-012`. +`max_iterations` counts the rounds of each stratum of a rule query +separately, not their total. A stratum starts another round only after +deriving a new fact, so its rounds never exceed the facts it derives plus one: +at the defaults (both 1,000,000) `max_derived_facts` is reached first, and +`max_iterations` matters only when lowered. `0` fails every rule query with +`INT-020`. + ## `PreparedQuery` setters -`PreparedQuery::with_max_derived_facts(n)` and +`PreparedQuery::with_max_derived_facts(n)`, +`PreparedQuery::with_max_iterations(n)` and `PreparedQuery::with_query_memory_limit(bytes)` replace the database values that were copied when the query was prepared, for that statement. They are application code, so `allow_overrides` does not gate them. An allowed diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 79c33ed717..229f270356 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -3849,8 +3849,8 @@ clause, `not`/`not-join`/`or`/`or-join`, a rule invocation, or `and`). The **Error text**: `duplicate {}` **Cause**: A query specified `:max-derived-facts`, `:max-results`, -`:query-memory-limit`, `:limit`, `:offset`, `:order-by` or `:distinct` more -than once. +`:query-memory-limit`, `:max-iterations`, `:limit`, `:offset`, `:order-by` or +`:distinct` more than once. **Resolution**: - Specify each query option at most once. @@ -3859,8 +3859,9 @@ than once. **Error text**: `{} requires a value` -**Cause**: A query option keyword (`:max-derived-facts`, `:max-results` or -`:query-memory-limit`) was present with no following value. +**Cause**: A query option keyword (`:max-derived-facts`, `:max-results`, +`:query-memory-limit` or `:max-iterations`) was present with no following +value. **Resolution**: - Supply an integer value or a `$slot` after the option keyword. @@ -3869,8 +3870,9 @@ than once. **Error text**: `{} must be >= 1` -**Cause**: `:max-derived-facts` or `:max-results` was given a value less -than 1, as a literal or as a prepared query's bind value. +**Cause**: `:max-derived-facts`, `:max-results` or `:max-iterations` (#861) +was given a value less than 1, as a literal or as a prepared query's bind +value. **Resolution**: - Use a value of 1 or greater. @@ -3879,14 +3881,14 @@ than 1, as a literal or as a prepared query's bind value. **Error text**: `{} must be a non-negative integer` -**Cause**: `:max-derived-facts` or `:max-results` was given a non-integer -value, or `:query-memory-limit` was given a negative or non-integer value, as +**Cause**: `:max-derived-facts`, `:max-results` or `:max-iterations` was +given a non-integer value, or `:query-memory-limit` was given a negative or non-integer value, as a literal or as a prepared query's bind value. (Before #870 the text said "positive integer".) **Resolution**: - Supply an integer literal or a `$slot`: at least 1 for - `:max-derived-facts` and `:max-results`, at least 0 for + `:max-derived-facts`, `:max-results` and `:max-iterations`, at least 0 for `:query-memory-limit`. ### INT-016 (or)/(or-join) nested inside (not)/(not-join) @@ -3941,8 +3943,9 @@ matches on `INT-019` for those errors must match the new codes. **Error text**: `evaluator: iteration or derived-fact limit exceeded: {}` -**Cause**: The recursive rule evaluator exceeded its maximum iteration count -(1,000), or its rules derived more facts in total than `max_derived_facts` +**Cause**: A stratum of the query's rules was still deriving new facts after +its round limit (`OpenOptions::max_iterations` or `:max-iterations`, default +1,000,000, counted per stratum; 1,000 and fixed before v3.0.0, #861), or its rules derived more facts in total than `max_derived_facts` allows (`OpenOptions::max_derived_facts` or `:max-derived-facts`, default 1,000,000; the database's own facts do not count) — guards against infinite recursion/cycles or runaway-generating rules. `max_results` / `:max-results` @@ -3956,8 +3959,10 @@ exceeded`. From v3.0.0 there is one limit, on the total (#553). **Resolution**: - Check the rule for an unintended cycle (e.g. `(ancestor ?x ?y) [?x :parent ?y]` combined with a cyclic `:parent` graph). Raise - `max_derived_facts` (or `:max-derived-facts` on the query) if the workload - is legitimately large. + `max_derived_facts` (or `:max-derived-facts` on the query), or for the + round message `max_iterations` (or `:max-iterations`), if the workload is + legitimately large. Before #861 the round message read `Possible infinite + recursion or cycle in rules.` ### INT-021 Evaluator: unsupported where-clause in evaluate_rule diff --git a/docs/GRAMMAR.md b/docs/GRAMMAR.md index 2309404428..9c14e6cc43 100644 --- a/docs/GRAMMAR.md +++ b/docs/GRAMMAR.md @@ -20,6 +20,7 @@ kw-any-valid-time ::= ":any-valid-time" (* not followed by word-cont *) (* kw-max-derived-facts ::= ":max-derived-facts" (* not followed by word-cont *) (* token *) kw-max-results ::= ":max-results" (* not followed by word-cont *) (* token *) kw-query-memory-limit ::= ":query-memory-limit" (* not followed by word-cont *) (* token *) +kw-max-iterations ::= ":max-iterations" (* not followed by word-cont *) (* token *) kw-limit ::= ":limit" (* not followed by word-cont *) (* token *) kw-offset ::= ":offset" (* not followed by word-cont *) (* token *) kw-distinct ::= ":distinct" (* not followed by word-cont *) (* token *) @@ -81,8 +82,9 @@ query-cmd ::= "(" "query" query-vector ")" query-vector ::= "[" query-section+ "]" query-section ::= find-section | where-section | as-of-section | valid-at-section | any-valid-time-section | with-section | max-derived-facts-section - | max-results-section | query-memory-limit-section | limit-section - | offset-section | order-by-section | distinct-section + | max-results-section | query-memory-limit-section + | max-iterations-section | limit-section | offset-section + | order-by-section | distinct-section (* ── FIND SECTION ── *) find-section ::= kw-find find-spec+ @@ -131,6 +133,7 @@ with-section ::= kw-with variable+ max-derived-facts-section ::= kw-max-derived-facts (integer-lit | bind-slot) max-results-section ::= kw-max-results (integer-lit | bind-slot) query-memory-limit-section ::= kw-query-memory-limit (integer-lit | bind-slot) +max-iterations-section ::= kw-max-iterations (integer-lit | bind-slot) limit-section ::= kw-limit (integer-lit | bind-slot) offset-section ::= kw-offset (integer-lit | bind-slot) distinct-section ::= kw-distinct diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 7d965de612..36900d4df0 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,12 +4,12 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Active** | 2,073 | 2,108 | +| **Active** | 2,083 | 2,118 | | **Ignored** | 21 | 24 | -| **Total** | 2,094 | 2,132 | +| **Total** | 2,104 | 2,142 | Counts above are the current Cargo test inventory (active versus ignored), -including #777, #789, #781, #794, #795, #837, #865, #869 and #870 (Linux). Verification results below identify which suites ran. +including #777, #789, #781, #794, #795, #837, #865, #869, #870 and #861 (Linux). Verification results below identify which suites ran. **#838 manual migration verification**: the [manual sweep](benchmarks/838-migration/README.md) checks every fixture value and cursor snapshot before accepting timings, including @@ -643,6 +643,7 @@ These are not `#[test]`s; run them with `cargo kani` or `.github/workflows/kani. - **Grammar page** (`tests/grammar_doc.rs`, 10 tests; #643): `docs/GRAMMAR.md` matches the EBNF rendered from `tests/grammar/grammar.pest`. Each rendering rule is checked on a small grammar: sequence, choice and grouping, names and builtins, `SOI`/`EOI` dropped, lookaheads as comments, bounded repetition, quoting, token marks, section titles, line breaking, the whitespace note and the comment note it joins. - **`OpenOptions::allow_overrides`** (#869; `tests/allow_overrides_test.rs`, 6 tests; `src/overrides.rs`, 2 unit tests; 1 doc test on `OpenOptions::allow_overrides`): the defaults allow `:max-derived-facts` and `:max-results`; an empty list refuses each with `API-025` from `execute`, `query`, `prepare` and `WriteTransaction::execute`, and queries without them still run; a list replaces the defaults; a refused statement leaves the write transaction usable; `DEFAULTS` read back, chained and with duplicates; the list holds on a file database and is not persisted; `:max-derived-facts` is reported first when both keywords are refused. API-025's registration and documentation are checked by the registry tests. - **`:query-memory-limit`, limit slots and `PreparedQuery` setters** (#870; `tests/limit_keywords_test.rs`, 17 tests; parser 3 unit tests, `src/overrides.rs` 1 unit test; 2 doc tests on the setters; 1 `#[wasm_bindgen_test]` in `src/browser/mod.rs`): the keyword lowers and raises the database limit (execute, cursor, write transaction); under 0 every stateful query fails with `QRY-012`, while a value-only query over checkpointed facts runs (keyword and setter); it is refused by default with `API-025` (literal and slot, every entry point, `BrowserDb`) and the list replaces the defaults; `INT-012`/`013`/`015` validation; slots on all three keywords change the outcome per execution, with `API-024`/`API-022`/`INT-014`/`INT-015` bind errors and `API-010` on `execute`/`query`; the setters replace the database value, a keyword overrides them, and they are not gated; `check_overrides` order over three keywords; `Count::literal` on a slot is `INT-032`. Grammar corpus: 3 valid, 2 syntax, 2 semantic fixtures; verifier 41 tokens and an `INT-015` witness; one `datalog_parser` fuzz seed. +- **`:max-iterations`, `OpenOptions::max_iterations` and `PreparedQuery::with_max_iterations`** (#861; `tests/limit_keywords_test.rs`, 8 tests; parser 1 unit test; `src/overrides.rs` order test extended; 1 doc test on the setter; 1 `#[wasm_bindgen_test]` in `src/browser/mod.rs`; `tests/allow_overrides_test.rs` pins the new `DEFAULTS`): a 1,500-round chain passes at the new 1,000,000 default (over the old fixed 1,000); the option, keyword (execute, write transaction) and setter each set the limit up or down, the keyword over the setter, with the 4-edge chain's 5-round boundary checked both ways and `0` failing; rounds are counted per stratum (two 5-round strata pass at 5); `INT-020` names `:max-iterations` and `OpenOptions::max_iterations`; the keyword is in `DEFAULTS` and refused with `API-025` under an empty list (execute, query, prepare); `INT-012`/`013`/`014`/`015` validation; slot outcomes per execution with `INT-014`/`API-024`/`API-022` bind errors and `API-010` on `execute`; the setter is ungated and applies to cursors. Grammar corpus: 2 valid, 2 syntax, 2 semantic fixtures; verifier 42 tokens; one `datalog_parser` fuzz seed. ## Browser and WASI diff --git a/docs/superpowers/plans/2026-11-06-861-max-iterations.md b/docs/superpowers/plans/2026-11-06-861-max-iterations.md new file mode 100644 index 0000000000..4d076118c5 --- /dev/null +++ b/docs/superpowers/plans/2026-11-06-861-max-iterations.md @@ -0,0 +1,67 @@ +# #861 plan: configurable recursion round limit + +Spec: `docs/superpowers/specs/2026-11-06-862-override-audit-design.md` §1–§5 (the `MaxIterations` rows), and the decisions posted on #861 (2026-11-06). +Branch `feat/861-max-iterations` off `v3` at `83fbaa8d` (after #870). One PR to `v3`, with `Refs #861, #862` in its body. Closing keywords do not fire on `v3`, so close #861 with `gh issue close` after the merge. + +## Decisions (from #861) + +- Default rounds per stratum: 1,000 → **1,000,000**, equal to `DEFAULT_MAX_DERIVED_FACTS`. A round that continues has derived at least one new fact, so rounds per stratum ≤ derived facts + 1 and, at equal defaults, the derived-facts limit binds first. v3 answer change: chains of more than ~500 edges now return rows instead of INT-020 (CHANGELOG Breaking changes). +- Rounds stay counted per stratum (`src/query/engine/recursive.rs`). +- `:max-iterations N` replaces the database value for that query, up or down. +- The INT-020 round message says how to raise the limit. +- Size gate: raise by the measured growth only if over 1,240 KiB and ≤ 4 KiB; more needs approval. + +## 1. Limits plumbing + +- `engine::Limits` (`max_iterations`, `max_derived_facts`, `query_memory`) becomes the one type for a query's limits. `DatalogExecutor` keeps a `Limits` instead of two fields; `set_limits(Limits)`; `PreparedQuery::limits: Limits`; `prepare_query(…, Limits)`. +- `OpenOptions::limits(&self) -> Limits` (private) replaces the four `(derived_fact_limit(), query_memory_limit)` pairs in `db.rs`. +- `DEFAULT_MAX_ITERATIONS` = 1,000,000, no longer `#[allow(dead_code)]`. + +## 2. `OpenOptions::max_iterations` + +Public field `max_iterations: usize` (default `DEFAULT_MAX_ITERATIONS`) and builder `max_iterations(n)`. `0` fails every rule query with INT-020 (the first round is over the limit); documented, not rejected, like `max_derived_facts(0)`. + +## 3. Query keyword + +- `DatalogQuery::max_iterations: Option`. Parser arm joins the limit-keyword arm with min 1: INT-012 duplicate, INT-013 missing, INT-014 for `< 1`, INT-015 non-integer, `$slot` → `Count::Slot`. +- Executor `iteration_limit(query) -> Result`: the literal, else the executor's. +- `Overridable::MaxIterations` (`:max-iterations`), in `DEFAULTS`; `check_overrides` checks it after `MaxResults`, before `QueryMemoryLimit`. +- Slots: `collect_slot_names` and `substitute` (via `resolve_limit_slot`, min 1). +- `PreparedQuery::with_max_iterations(n)`, ungated; an allowed keyword overrides it. Doc test. + +## 4. INT-020 message + +`Max iterations ({limit}) exceeded. A stratum's rules were still deriving new facts after {limit} rounds; raise the limit with :max-iterations N or OpenOptions::max_iterations.` (`ERROR_REFERENCE.md` updated.) + +## 5. Grammar and verifier + +`kw_max_iterations` + `max_iterations_section` in `grammar.pest`; `GRAMMAR.md` regenerated; corpus `valid/max_iterations.edn` (literal and slot), `invalid/semantic/max_iterations_zero.edn`, `max_iterations_twice.edn`, `invalid/syntax/max_iterations_missing.edn`; fuzz seed; verifier TOKENS 41 → 42 with new filler counts. Bound 4 on the bench machine. + +## 6. Tests (TDD, `tests/limit_keywords_test.rs`, codes only) + +1. A chain of 1,500 edges: the transitive rule returns rows at the default (was INT-020 at 1,000 rounds). +2. `OpenOptions::max_iterations(3)` → INT-020 on the 4-edge chain; the message names `:max-iterations`. `max_iterations(10)` passes. +3. `:max-iterations 3` lowers, `:max-iterations 10` raises on a `max_iterations(3)` database. +4. Gate: `allow_overrides([])` refuses `:max-iterations` with API-025; `DEFAULTS` allows it. +5. Validation: INT-012/013/014/015. +6. Slot: `$n` = 3 fails, 10 passes; `0` → INT-014; `Val(String)` → API-024. +7. Setter: `with_max_iterations(3)` fails, keyword overrides the setter, ungated under `allow_overrides([])`, applies to `PreparedQuery::query`. +8. Unit: `check_overrides` order with all four keywords; parser unit test for the slot form. +9. Rounds are per stratum: two strata of 3 rounds each pass at `max_iterations(4)` (a total count would fail). + +## 7. Docs + +`docs/CONFIGURATION.md` (round-limit row, `allow_overrides` table, limit-keyword table, setters), `ERROR_REFERENCE.md` (INT-012..015 causes, INT-020), `CHANGELOG.md` (Added; Breaking: default 1,000 → 1,000,000; Changed: INT-020 text), `CLAUDE.md` + `docs/TEST_COVERAGE.md` counts and module lines, docs site (`datalog-reference.md`, `performance-tuning.md`, `@since v3.0.0`). + +## 8. Verification + +`cargo fmt`, `cargo clippy --all-targets -- -D warnings`, full tests plain and `--features test-hooks` on the bench machine, wasm32 browser build, `--profile dist` size vs the 1,240 KiB gate. Codex review skipped (quota out until 2026-11-11). CI green. + +## Deviations found while implementing + +1. **Dead constructor removed.** `DatalogExecutor::new_with_limits` (crate-private, `#[allow(dead_code)]`, no callers) is deleted rather than given a third limit; `engine::Limits` gains `Default` (the `OpenOptions` defaults), which the executor constructors and `BrowserDb::prepare` use. +2. **Boundary.** A stratum runs one more round than the chain depth: the 4-edge chain derives in rounds 1–4 and round 5 finds nothing new, so it needs `max_iterations` 5 (4 fails). Tests use that calibrated value (`REACH_ROUNDS`). +3. **BrowserDb test.** A `#[wasm_bindgen_test]` checks `:max-iterations` runs by default (it is in `DEFAULTS`) and that a low value is INT-020. +4. **`allow_overrides_test` pinned `DEFAULTS`.** `defaults_read_back_and_compose` asserted the two-variant list; it now lists `MaxIterations` too (the intended change). +5. **Size.** `--profile dist` grows 624 B over base `83fbaa8d` (local stable 1.94: 1,300,968 → 1,301,592 B). CI measured the base at 1,263,928 B in #874, so about 5 KiB stays under the 1,240 KiB gate; no gate change. +6. **Bench.** The primary bench machine was saturated, so the suites ran on the alternate: plain 2,083 active / 21 ignored, test-hooks 2,118 / 24; verifier bound 4 clean (430 s). diff --git a/fuzz/corpus/datalog_parser/74d3f1815468c9507803f399d37f385934852f1e b/fuzz/corpus/datalog_parser/74d3f1815468c9507803f399d37f385934852f1e new file mode 100644 index 0000000000..37f664e46c --- /dev/null +++ b/fuzz/corpus/datalog_parser/74d3f1815468c9507803f399d37f385934852f1e @@ -0,0 +1 @@ +(query [:find ?x ?y :where (reach ?x ?y) :max-iterations $n]) \ No newline at end of file diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 3ed1c10709..f151514726 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -331,10 +331,7 @@ impl BrowserDb { inner.fact_storage.clone(), inner.rules.clone(), inner.functions.clone(), - ( - crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, - usize::MAX, - ), + crate::query::engine::Limits::default(), ) } @@ -753,6 +750,26 @@ mod tests { assert!(text.contains(":query-memory-limit"), "names the keyword"); } + // #861: `:max-iterations` is in the default list, so BrowserDb runs it. + #[wasm_bindgen_test] + async fn max_iterations_keyword_is_allowed() { + let db = BrowserDb::open_in_memory().expect("open_in_memory"); + db.execute("(transact [[:a :edge :b] [:b :edge :c]])".to_string()) + .await + .expect("transact"); + db.execute("(rule [(reach ?x ?y) [?x :edge ?y]])".to_string()) + .await + .expect("rule"); + db.execute("(rule [(reach ?x ?y) [?x :edge ?z] (reach ?z ?y)])".to_string()) + .await + .expect("rule"); + let q = |n: u32| format!("(query [:find ?x ?y :where (reach ?x ?y) :max-iterations {n}])"); + db.execute(q(10)).await.expect("allowed"); + let err = db.execute(q(1)).await.expect_err("over the limit"); + let text = err.as_string().expect("rejection is a string"); + assert!(text.starts_with("[INT-020] "), "rejection is INT-020"); + } + #[wasm_bindgen_test] async fn in_memory_transact_and_query() { let db = BrowserDb::open_in_memory().expect("open_in_memory"); diff --git a/src/db.rs b/src/db.rs index 9384b1a75e..058fc12d63 100644 --- a/src/db.rs +++ b/src/db.rs @@ -21,7 +21,7 @@ use crate::graph::FactStorage; use crate::graph::storage::Snapshot; use crate::graph::types::Value; use crate::overrides::{Overridable, check_overrides}; -use crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS; +use crate::query::datalog::evaluator::{DEFAULT_MAX_DERIVED_FACTS, DEFAULT_MAX_ITERATIONS}; use crate::query::datalog::executor::DatalogExecutor; use crate::query::datalog::executor::QueryResult; use crate::query::datalog::functions::{Functions, UdfError, udf_aggregate, udf_predicate}; @@ -149,6 +149,14 @@ pub struct OpenOptions { note = "use `max_derived_facts`; the lower of the two applies" )] pub max_results: usize, + /// The most rounds one stratum of a rule query may run (#861). Defaults + /// to 1,000,000, the same as [`max_derived_facts`](Self::max_derived_facts): + /// a stratum only starts another round after deriving a new fact, so at + /// the defaults the derived-facts limit is reached first. A stratum + /// still deriving facts after this many rounds fails with `INT-020`; + /// `0` fails every rule query. Overridden per query by + /// `:max-iterations N`. + pub max_iterations: usize, /// Open even when the filesystem cannot lock files at all. /// /// Defaults to `false`, which refuses to open rather than run without the @@ -234,6 +242,7 @@ impl Default for OpenOptions { page_cache_size: 256, max_derived_facts: DEFAULT_MAX_DERIVED_FACTS, max_results: usize::MAX, + max_iterations: DEFAULT_MAX_ITERATIONS, allow_unlocked: false, synchronous: SyncMode::Full, read_only: false, @@ -294,6 +303,14 @@ impl OpenOptions { self } + /// Set the most rounds one stratum of a rule query may run. See + /// [`OpenOptions::max_iterations`]. + #[must_use] + pub fn max_iterations(mut self, n: usize) -> Self { + self.max_iterations = n; + self + } + /// Set the most bytes one query may hold. See /// [`OpenOptions::query_memory_limit`]. #[must_use] @@ -310,11 +327,15 @@ impl OpenOptions { self } - /// The limit rule queries run with: the lower of `max_derived_facts` and - /// its deprecated alias `max_results` (#553). + /// The limits queries run with; the derived-facts limit is the lower of + /// `max_derived_facts` and its deprecated alias `max_results` (#553). #[allow(deprecated)] - fn derived_fact_limit(&self) -> usize { - self.max_derived_facts.min(self.max_results) + fn limits(&self) -> crate::query::engine::Limits { + crate::query::engine::Limits { + max_iterations: self.max_iterations, + max_derived_facts: self.max_derived_facts.min(self.max_results), + query_memory: self.query_memory_limit, + } } /// Set the query keywords that may override this database's settings. @@ -985,10 +1006,7 @@ impl Minigraf { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits( - self.inner.options.derived_fact_limit(), - self.inner.options.query_memory_limit, - ); + executor.set_limits(self.inner.options.limits()); executor.set_snapshot(snapshot); executor } @@ -1410,10 +1428,7 @@ impl Minigraf { self.inner.fact_storage.clone(), self.inner.rules.clone(), self.inner.functions.clone(), - ( - self.inner.options.derived_fact_limit(), - self.inner.options.query_memory_limit, - ), + self.inner.options.limits(), ) } @@ -1828,10 +1843,7 @@ impl<'a> WriteTransaction<'a> { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits( - self.inner.options.derived_fact_limit(), - self.inner.options.query_memory_limit, - ); + executor.set_limits(self.inner.options.limits()); executor.set_snapshot(self.read_snapshot()?); executor.execute(cmd) } @@ -1967,10 +1979,7 @@ impl<'a> WriteTransaction<'a> { self.inner.rules.clone(), self.inner.functions.clone(), ); - executor.set_limits( - self.inner.options.derived_fact_limit(), - self.inner.options.query_memory_limit, - ); + executor.set_limits(self.inner.options.limits()); executor.execute(DatalogCommand::Rule(rule)) } @@ -2729,6 +2738,7 @@ mod tests { page_cache_size: 256, max_derived_facts: 100_000, max_results: 1_000_000, + max_iterations: 1_000, allow_unlocked: false, synchronous: SyncMode::Full, read_only: false, @@ -3355,12 +3365,13 @@ mod tests { fn max_derived_facts_alone_raises_the_limit_above_the_default() { // The alias has no limit of its own unless set (#553). let opts = OpenOptions::default().max_derived_facts(2_000_000); - assert_eq!(opts.derived_fact_limit(), 2_000_000); - assert_eq!(OpenOptions::default().derived_fact_limit(), 1_000_000); + assert_eq!(opts.limits().max_derived_facts, 2_000_000); + assert_eq!(OpenOptions::default().limits().max_derived_facts, 1_000_000); assert_eq!( OpenOptions::default() .max_results(2_000_000) - .derived_fact_limit(), + .limits() + .max_derived_facts, 1_000_000, "the alias does not raise the limit" ); diff --git a/src/overrides.rs b/src/overrides.rs index 59ed146f31..e7e43273de 100644 --- a/src/overrides.rs +++ b/src/overrides.rs @@ -26,14 +26,22 @@ pub enum Overridable { /// (#870). Not in [`DEFAULTS`](Self::DEFAULTS): query text can raise the /// limit that keeps it from exhausting memory. QueryMemoryLimit, + /// `:max-iterations N`, which overrides + /// [`OpenOptions::max_iterations`](crate::OpenOptions::max_iterations) + /// (#861). + MaxIterations, } impl Overridable { /// The list a database uses when /// [`OpenOptions::allow_overrides`](crate::OpenOptions::allow_overrides) - /// is not set: every keyword that could override a setting before #862. - pub const DEFAULTS: &'static [Overridable] = - &[Overridable::MaxDerivedFacts, Overridable::MaxResults]; + /// is not set: every keyword that could override a setting before #862, + /// and `:max-iterations` (#861). + pub const DEFAULTS: &'static [Overridable] = &[ + Overridable::MaxDerivedFacts, + Overridable::MaxResults, + Overridable::MaxIterations, + ]; /// The query keyword this variant gates, e.g. `":max-derived-facts"`. pub fn keyword(self) -> &'static str { @@ -41,6 +49,7 @@ impl Overridable { Overridable::MaxDerivedFacts => ":max-derived-facts", Overridable::MaxResults => ":max-results", Overridable::QueryMemoryLimit => ":query-memory-limit", + Overridable::MaxIterations => ":max-iterations", } } @@ -49,6 +58,7 @@ impl Overridable { Overridable::MaxDerivedFacts => "MaxDerivedFacts", Overridable::MaxResults => "MaxResults", Overridable::QueryMemoryLimit => "QueryMemoryLimit", + Overridable::MaxIterations => "MaxIterations", } } } @@ -64,6 +74,7 @@ pub(crate) fn check_overrides(query: &DatalogQuery, allowed: &[Overridable]) -> query.max_derived_facts.is_some(), ), (Overridable::MaxResults, query.max_results.is_some()), + (Overridable::MaxIterations, query.max_iterations.is_some()), ( Overridable::QueryMemoryLimit, query.query_memory_limit.is_some(), @@ -110,7 +121,7 @@ mod tests { fn checks_in_a_fixed_order() { let q = query( "(query [:find ?e :where [?e :a ?v] :query-memory-limit 9 \ - :max-results 5 :max-derived-facts 5])", + :max-iterations 3 :max-results 5 :max-derived-facts 5])", ); let first = |allowed: &[Overridable]| { crate::MinigrafError::from(check_overrides(&q, allowed).expect_err("refused")) @@ -118,6 +129,10 @@ mod tests { }; assert!(first(&[]).contains(":max-derived-facts")); assert!(first(&[Overridable::MaxDerivedFacts]).contains(":max-results")); + assert!( + first(&[Overridable::MaxDerivedFacts, Overridable::MaxResults]) + .contains(":max-iterations") + ); let last = first(Overridable::DEFAULTS); assert!(last.contains(":query-memory-limit")); assert!(last.contains("Overridable::QueryMemoryLimit")); diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 40880d3efd..7ab9216eaf 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -2,9 +2,10 @@ use super::types::{EdnValue, Pattern}; use crate::error::{ErrorCode, err_coded}; use anyhow::Result; -/// Default maximum iterations for recursive evaluation (kept for reference). -#[allow(dead_code)] -pub const DEFAULT_MAX_ITERATIONS: usize = 1000; +/// Default maximum rounds of one stratum of a rule query (#861): equal to +/// [`DEFAULT_MAX_DERIVED_FACTS`], since a round that continues derived a new +/// fact, so at the defaults the derived-facts limit is reached first. +pub const DEFAULT_MAX_ITERATIONS: usize = 1_000_000; /// Default maximum facts the rules of one query may derive in total; base /// facts do not count (#553). pub const DEFAULT_MAX_DERIVED_FACTS: usize = 1_000_000; @@ -24,7 +25,7 @@ pub(crate) fn iterations_exceeded(limit: usize) -> anyhow::Error { err_coded!( ErrorCode::Int020, format!( - "Max iterations ({limit}) exceeded. Possible infinite recursion or cycle in rules." + "Max iterations ({limit}) exceeded. A stratum's rules were still deriving new facts after {limit} rounds; raise the limit with :max-iterations N or OpenOptions::max_iterations." ) ) } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index d6ed401a2f..c902c3e561 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -124,10 +124,10 @@ pub struct DatalogExecutor { rules: Arc>, /// The functions; each query reads one snapshot of them (#180). functions: Arc, - /// The most facts a rule query may derive, base facts not counted (#553). - max_derived_facts: usize, - /// The most bytes an engine query may hold (#549). - query_memory_limit: usize, + /// The database's limits (`OpenOptions`): rounds per stratum (#861), + /// facts a rule query may derive, base facts not counted (#553), and + /// bytes a query may hold (#549). A query's keywords replace them. + limits: crate::query::engine::Limits, } impl DatalogExecutor { @@ -138,8 +138,7 @@ impl DatalogExecutor { snapshot: None, rules: Arc::new(RwLock::new(RuleRegistry::new())), functions: Arc::new(Functions::with_builtins()), - max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, - query_memory_limit: usize::MAX, + limits: crate::query::engine::Limits::default(), } } @@ -156,8 +155,7 @@ impl DatalogExecutor { snapshot: None, rules, functions, - max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, - query_memory_limit: usize::MAX, + limits: crate::query::engine::Limits::default(), } } @@ -169,32 +167,12 @@ impl DatalogExecutor { Self::new_with_rules_and_functions(storage, rules, Arc::new(Functions::with_builtins())) } - /// Create a `DatalogExecutor` with custom complexity limits. - /// - /// Used by `Minigraf` when `OpenOptions` specifies non-default limits. - #[allow(dead_code)] - pub fn new_with_limits( - storage: FactStorage, - rules: Arc>, - functions: Arc, - max_derived_facts: usize, - ) -> Self { - DatalogExecutor { - storage, - snapshot: None, - rules, - functions, - max_derived_facts, - query_memory_limit: usize::MAX, - } - } - - /// Set the most facts a rule query may derive, base facts not counted - /// (`OpenOptions::max_derived_facts`, #553), and the most bytes a query - /// on the engine may hold (`OpenOptions::query_memory_limit`, #549). - pub fn set_limits(&mut self, max_derived_facts: usize, query_memory_limit: usize) { - self.max_derived_facts = max_derived_facts; - self.query_memory_limit = query_memory_limit; + /// Set the database's limits: rounds per stratum + /// (`OpenOptions::max_iterations`, #861), facts a rule query may derive + /// (`OpenOptions::max_derived_facts`, #553) and bytes a query may hold + /// (`OpenOptions::query_memory_limit`, #549). + pub(crate) fn set_limits(&mut self, limits: crate::query::engine::Limits) { + self.limits = limits; } /// Read every fact from `snapshot`, so the queries of this executor see @@ -385,7 +363,7 @@ impl DatalogExecutor { }; check_per_fact_pseudo_attrs(query)?; let limits = crate::query::engine::Limits { - max_iterations: crate::query::datalog::evaluator::DEFAULT_MAX_ITERATIONS, + max_iterations: self.iteration_limit(query)?, max_derived_facts: self.derived_limit(query)?, query_memory: self.memory_limit(query)?, }; @@ -433,7 +411,7 @@ impl DatalogExecutor { None => Ok(usize::MAX), }; Ok(match (&query.max_derived_facts, &query.max_results) { - (None, None) => self.max_derived_facts, + (None, None) => self.limits.max_derived_facts, (a, b) => limit(a, ":max-derived-facts")?.min(limit(b, ":max-results")?), }) } @@ -443,7 +421,16 @@ impl DatalogExecutor { fn memory_limit(&self, query: &DatalogQuery) -> Result { match &query.query_memory_limit { Some(c) => c.literal(":query-memory-limit"), - None => Ok(self.query_memory_limit), + None => Ok(self.limits.query_memory), + } + } + + /// The most rounds a stratum of `query`'s rules may run: its + /// `:max-iterations` replaces the executor's (#861). + fn iteration_limit(&self, query: &DatalogQuery) -> Result { + match &query.max_iterations { + Some(c) => c.literal(":max-iterations"), + None => Ok(self.limits.max_iterations), } } @@ -1550,6 +1537,7 @@ mod tests { max_derived_facts: None, max_results: None, query_memory_limit: None, + max_iterations: None, limit: None, offset: None, order_by: Vec::new(), @@ -1613,6 +1601,7 @@ mod tests { max_derived_facts: None, max_results: None, query_memory_limit: None, + max_iterations: None, limit: None, offset: None, order_by: Vec::new(), @@ -2011,7 +2000,7 @@ mod tests { rules.clone(), functions.clone(), ); - executor.set_limits(1_000_000, usize::MAX); + executor.set_limits(crate::query::engine::Limits::default()); executor .execute(parse_datalog_command(r#"(rule [(reachable ?x ?y) [?x :edge ?y]])"#).unwrap()) diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index 526eb39f80..8143691c0e 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -900,6 +900,7 @@ fn parse_query(elements: &[EdnValue]) -> Result { let mut query_max_derived_facts: Option = None; let mut query_max_results: Option = None; let mut query_query_memory_limit: Option = None; + let mut query_max_iterations: Option = None; let mut query_limit: Option = None; let mut query_offset: Option = None; let mut query_order_by: Option> = None; @@ -982,11 +983,15 @@ fn parse_query(elements: &[EdnValue]) -> Result { i += 1; continue; } - ":max-derived-facts" | ":max-results" | ":query-memory-limit" => { + ":max-derived-facts" + | ":max-results" + | ":query-memory-limit" + | ":max-iterations" => { current_clause = None; let (target, min) = match keyword { ":max-derived-facts" => (&mut query_max_derived_facts, 1), ":max-results" => (&mut query_max_results, 1), + ":max-iterations" => (&mut query_max_iterations, 1), _ => (&mut query_query_memory_limit, 0), }; if target.is_some() { @@ -1000,7 +1005,7 @@ fn parse_query(elements: &[EdnValue]) -> Result { EdnValue::Integer(n) if *n >= min => { Count::Literal(usize::try_from(*n).unwrap_or(usize::MAX)) } - // Only the two older keywords reject zero (INT-014). + // Every keyword but `:query-memory-limit` rejects zero (INT-014). EdnValue::Integer(_) if min == 1 => { bail_coded!(ErrorCode::Int014, keyword); } @@ -1234,6 +1239,7 @@ fn parse_query(elements: &[EdnValue]) -> Result { query.max_derived_facts = query_max_derived_facts; query.max_results = query_max_results; query.query_memory_limit = query_query_memory_limit; + query.max_iterations = query_max_iterations; query.limit = query_limit; query.offset = query_offset; query.order_by = order_by; @@ -3384,6 +3390,25 @@ mod tests { } } + #[test] + fn max_iterations_takes_a_literal_or_a_slot() { + for (input, want) in [ + ( + "(query [:find ?x :where [?x :a :b] :max-iterations 7])", + Count::Literal(7), + ), + ( + "(query [:find ?x :where [?x :a :b] :max-iterations $n])", + Count::Slot("n".into()), + ), + ] { + match parse_datalog_command(input).expect("parses") { + DatalogCommand::Query(q) => assert_eq!(q.max_iterations, Some(want)), + _ => panic!("expected a query"), + } + } + } + #[test] fn query_memory_limit_errors() { let code = |opt: &str| { diff --git a/src/query/datalog/parser/verifier.rs b/src/query/datalog/parser/verifier.rs index 5b6041ac4d..92c6dadad7 100644 --- a/src/query/datalog/parser/verifier.rs +++ b/src/query/datalog/parser/verifier.rs @@ -66,7 +66,7 @@ fn alphabet() -> Vec { a } -const TOKENS: [&str; 41] = [ +const TOKENS: [&str; 42] = [ "(", ")", "[", @@ -91,6 +91,7 @@ const TOKENS: [&str; 41] = [ ":limit", ":offset", ":query-memory-limit", + ":max-iterations", ":distinct", ":asc", ":desc", @@ -551,11 +552,11 @@ fn filler_counts_match_the_spec() { } n }; - // 41 tokens: the #643 spec's 32, `#{` (#316), `:limit`, `:offset`, - // `:asc`, `:desc` (#306), `:distinct` (#493), `:rows`, `preceding` (#183) - // and `:query-memory-limit` (#870). - assert_eq!(count(3), 44_454); - assert_eq!(count(4), 1_567_147); + // 42 tokens: the #643 spec's 32, `#{` (#316), `:limit`, `:offset`, + // `:asc`, `:desc` (#306), `:distinct` (#493), `:rows`, `preceding` (#183), + // `:query-memory-limit` (#870) and `:max-iterations` (#861). + assert_eq!(count(3), 48_316); + assert_eq!(count(4), 1_751_278); } #[test] diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index 554502c12c..aebd6ddc46 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -82,9 +82,9 @@ pub struct PreparedQuery { fact_storage: FactStorage, rules: Arc>, functions: Arc, - /// The database's `max_derived_facts` and `query_memory_limit`, or the - /// setters' values (#870). - limits: (usize, usize), + /// The database's `max_iterations`, `max_derived_facts` and + /// `query_memory_limit`, or the setters' values (#870, #861). + limits: crate::query::engine::Limits, } impl std::fmt::Debug for PreparedQuery { @@ -114,7 +114,7 @@ impl PreparedQuery { /// assert_eq!(err.code(), "INT-020"); /// ``` pub fn with_max_derived_facts(mut self, n: usize) -> Self { - self.limits.0 = n; + self.limits.max_derived_facts = n; self } @@ -135,7 +135,29 @@ impl PreparedQuery { /// assert_eq!(err.code(), "QRY-012"); /// ``` pub fn with_query_memory_limit(mut self, bytes: usize) -> Self { - self.limits.1 = bytes; + self.limits.query_memory = bytes; + self + } + + /// Replace the database's + /// [`max_iterations`](crate::OpenOptions::max_iterations) for this + /// statement (#861). An allowed `:max-iterations` in the query still + /// overrides it. + /// + /// Not gated by [`OpenOptions::allow_overrides`](crate::OpenOptions::allow_overrides). + /// + /// ``` + /// # use minigraf::Minigraf; + /// let db = Minigraf::in_memory().unwrap(); + /// db.execute("(transact [[:a :edge :b] [:b :edge :c]])").unwrap(); + /// db.execute("(rule [(reach ?x ?y) [?x :edge ?y]])").unwrap(); + /// db.execute("(rule [(reach ?x ?y) [?x :edge ?z] (reach ?z ?y)])").unwrap(); + /// let pq = db.prepare("(query [:find ?x ?y :where (reach ?x ?y)])").unwrap(); + /// let err = pq.with_max_iterations(1).execute(&[]).unwrap_err(); + /// assert_eq!(err.code(), "INT-020"); + /// ``` + pub fn with_max_iterations(mut self, n: usize) -> Self { + self.limits.max_iterations = n; self } @@ -207,7 +229,7 @@ impl PreparedQuery { self.rules.clone(), self.functions.clone(), ); - executor.set_limits(self.limits.0, self.limits.1); + executor.set_limits(self.limits); executor.set_snapshot(snapshot); Ok((executor, DatalogCommand::Query(filled_query))) } @@ -220,7 +242,7 @@ pub(crate) fn prepare_query( fact_storage: FactStorage, rules: Arc>, functions: Arc, - limits: (usize, usize), + limits: crate::query::engine::Limits, ) -> Result { validate_no_attribute_slots(&query)?; let slot_names = collect_slot_names(&query); @@ -300,6 +322,7 @@ fn collect_slot_names(query: &DatalogQuery) -> Vec { &query.max_derived_facts, &query.max_results, &query.query_memory_limit, + &query.max_iterations, ] { if let Some(Count::Slot(name)) = count { names.insert(name.clone()); @@ -395,6 +418,7 @@ fn substitute( (&mut query.max_derived_facts, ":max-derived-facts", 1), (&mut query.max_results, ":max-results", 1), (&mut query.query_memory_limit, ":query-memory-limit", 0), + (&mut query.max_iterations, ":max-iterations", 1), ] { if let Some(Count::Slot(name)) = target { *target = Some(resolve_limit_slot(name, option, min, bindings)?); diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index d98288cd39..b201d147ee 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -587,6 +587,9 @@ pub struct DatalogQuery { /// Per-query `:query-memory-limit`: replaces the executor's /// `query_memory_limit` for this query (#870). pub query_memory_limit: Option, + /// Per-query `:max-iterations`: replaces the executor's rounds per + /// stratum for this query (#861). + pub max_iterations: Option, /// `:limit`: the most rows the query returns (#306). pub limit: Option, /// `:offset`: the rows of the ordered answer skipped before `:limit`'s @@ -601,7 +604,8 @@ pub struct DatalogQuery { } /// The value of `:limit`, `:offset` (#306), `:max-derived-facts`, -/// `:max-results` or `:query-memory-limit` (#870): a literal, or a bind slot +/// `:max-results`, `:query-memory-limit` (#870) or `:max-iterations` (#861): +/// a literal, or a bind slot /// a prepared query fills. #[derive(Debug, Clone, PartialEq, Eq)] pub enum Count { @@ -634,6 +638,7 @@ impl DatalogQuery { max_derived_facts: None, max_results: None, query_memory_limit: None, + max_iterations: None, limit: None, offset: None, order_by: Vec::new(), @@ -653,6 +658,7 @@ impl DatalogQuery { max_derived_facts: None, max_results: None, query_memory_limit: None, + max_iterations: None, limit: None, offset: None, order_by: Vec::new(), diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index dc04856f35..61dd485e29 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -32,6 +32,7 @@ use std::sync::Arc; /// The limits of one rule query (spec §3.5). #[derive(Debug, Clone, Copy)] pub(crate) struct Limits { + /// Rounds of one stratum (#861). pub(crate) max_iterations: usize, /// Facts the rules may derive in total; stored facts and magic seeds do /// not count. @@ -40,6 +41,17 @@ pub(crate) struct Limits { pub(crate) query_memory: usize, } +impl Default for Limits { + /// The defaults of [`OpenOptions`](crate::OpenOptions). + fn default() -> Self { + Limits { + max_iterations: crate::query::datalog::evaluator::DEFAULT_MAX_ITERATIONS, + max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS, + query_memory: usize::MAX, + } + } +} + /// What every body run reads. pub(crate) struct Reads<'a> { pub(crate) snapshot: &'a Snapshot, diff --git a/tests/allow_overrides_test.rs b/tests/allow_overrides_test.rs index e46521bbe8..22ea7ff751 100644 --- a/tests/allow_overrides_test.rs +++ b/tests/allow_overrides_test.rs @@ -95,7 +95,11 @@ fn defaults_read_back_and_compose() { ); assert_eq!( Overridable::DEFAULTS, - &[Overridable::MaxDerivedFacts, Overridable::MaxResults] + &[ + Overridable::MaxDerivedFacts, + Overridable::MaxResults, + Overridable::MaxIterations + ] ); assert_eq!(Overridable::MaxDerivedFacts.keyword(), ":max-derived-facts"); assert_eq!(Overridable::MaxResults.keyword(), ":max-results"); diff --git a/tests/grammar/grammar.pest b/tests/grammar/grammar.pest index abf074ef2c..d0b140f6d1 100644 --- a/tests/grammar/grammar.pest +++ b/tests/grammar/grammar.pest @@ -20,6 +20,7 @@ kw_any_valid_time = @{ ":any-valid-time" ~ !word_cont } kw_max_derived_facts = @{ ":max-derived-facts" ~ !word_cont } kw_max_results = @{ ":max-results" ~ !word_cont } kw_query_memory_limit = @{ ":query-memory-limit" ~ !word_cont } +kw_max_iterations = @{ ":max-iterations" ~ !word_cont } kw_limit = @{ ":limit" ~ !word_cont } kw_offset = @{ ":offset" ~ !word_cont } kw_distinct = @{ ":distinct" ~ !word_cont } @@ -134,7 +135,7 @@ query_section = { find_section | where_section | as_of_section | valid_at_section | any_valid_time_section | with_section | max_derived_facts_section | max_results_section | - query_memory_limit_section | limit_section | + query_memory_limit_section | max_iterations_section | limit_section | offset_section | order_by_section | distinct_section } @@ -218,6 +219,7 @@ with_section = { kw_with ~ variable+ } max_derived_facts_section = { kw_max_derived_facts ~ (integer_lit | bind_slot) } max_results_section = { kw_max_results ~ (integer_lit | bind_slot) } query_memory_limit_section = { kw_query_memory_limit ~ (integer_lit | bind_slot) } +max_iterations_section = { kw_max_iterations ~ (integer_lit | bind_slot) } limit_section = { kw_limit ~ (integer_lit | bind_slot) } offset_section = { kw_offset ~ (integer_lit | bind_slot) } distinct_section = { kw_distinct } diff --git a/tests/grammar/invalid/semantic/max_iterations_twice.edn b/tests/grammar/invalid/semantic/max_iterations_twice.edn new file mode 100644 index 0000000000..8bee842cfd --- /dev/null +++ b/tests/grammar/invalid/semantic/max_iterations_twice.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations 1 :max-iterations 1]) diff --git a/tests/grammar/invalid/semantic/max_iterations_zero.edn b/tests/grammar/invalid/semantic/max_iterations_zero.edn new file mode 100644 index 0000000000..34f62815a3 --- /dev/null +++ b/tests/grammar/invalid/semantic/max_iterations_zero.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations 0]) diff --git a/tests/grammar/invalid/syntax/max_iterations_missing.edn b/tests/grammar/invalid/syntax/max_iterations_missing.edn new file mode 100644 index 0000000000..87fd085793 --- /dev/null +++ b/tests/grammar/invalid/syntax/max_iterations_missing.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations]) diff --git a/tests/grammar/invalid/syntax/max_iterations_string.edn b/tests/grammar/invalid/syntax/max_iterations_string.edn new file mode 100644 index 0000000000..5594755f8b --- /dev/null +++ b/tests/grammar/invalid/syntax/max_iterations_string.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations "many"]) diff --git a/tests/grammar/valid/max_iterations.edn b/tests/grammar/valid/max_iterations.edn new file mode 100644 index 0000000000..a5b1a565cb --- /dev/null +++ b/tests/grammar/valid/max_iterations.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations 5000]) diff --git a/tests/grammar/valid/max_iterations_slot.edn b/tests/grammar/valid/max_iterations_slot.edn new file mode 100644 index 0000000000..55645c2afd --- /dev/null +++ b/tests/grammar/valid/max_iterations_slot.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-iterations $n]) diff --git a/tests/limit_keywords_test.rs b/tests/limit_keywords_test.rs index 920d127672..31fdba4970 100644 --- a/tests/limit_keywords_test.rs +++ b/tests/limit_keywords_test.rs @@ -351,3 +351,182 @@ fn setters_are_not_gated() { .with_query_memory_limit(usize::MAX); assert_eq!(rows(pq.execute(&[]).expect("setters")), 10); } + +// ─── :max-iterations (#861) ────────────────────────────────────────────────── + +/// Rounds the 4-edge chain's `reach` stratum needs (calibrated: one fewer fails). +const REACH_ROUNDS: i64 = 5; + +fn with_iterations(query: &str, n: i64) -> String { + with(query, &format!(":max-iterations {n}")) +} + +#[test] +fn default_round_limit_allows_long_chains() { + // 1,500 rounds: over the old fixed limit of 1,000, under 1,000,000. + let db = Minigraf::in_memory().expect("open"); + let edges: String = (0..1500) + .map(|i| format!("[:n{i} :next :n{}]", i + 1)) + .collect(); + db.execute(&format!("(transact [{edges}])")).expect("edges"); + db.execute("(rule [(down ?y) [:n0 :next ?y]])") + .expect("rule"); + db.execute("(rule [(down ?y) (down ?x) [?x :next ?y]])") + .expect("rule"); + let r = db + .execute("(query [:find ?y :where (down ?y)])") + .expect("long chain"); + assert_eq!(rows(r), 1500); +} + +#[test] +fn open_option_sets_the_round_limit() { + let db = setup(OpenOptions::new().max_iterations(REACH_ROUNDS as usize - 1)); + let err = db.execute(REACH).err().expect("over the limit"); + assert_eq!(err.code(), "INT-020"); + let text = err.to_string(); + assert!(text.contains(":max-iterations"), "says how to raise it"); + assert!( + text.contains("OpenOptions::max_iterations"), + "names the option" + ); + let db = setup(OpenOptions::new().max_iterations(REACH_ROUNDS as usize)); + assert_eq!(rows(db.execute(REACH).expect("at the limit")), 10); + let db = setup(OpenOptions::new().max_iterations(0)); + assert_eq!(code(db.execute(REACH)), "INT-020"); +} + +#[test] +fn iterations_keyword_replaces_the_database_value() { + let db = setup(OpenOptions::new()); + assert_eq!( + code(db.execute(&with_iterations(REACH, REACH_ROUNDS - 1))), + "INT-020" + ); + let db = setup(OpenOptions::new().max_iterations(1)); + assert_eq!(code(db.execute(REACH)), "INT-020"); + assert_eq!( + rows( + db.execute(&with_iterations(REACH, REACH_ROUNDS)) + .expect("raised") + ), + 10 + ); + let mut tx = db.begin_write().expect("tx"); + assert_eq!( + rows( + tx.execute(&with_iterations(REACH, REACH_ROUNDS)) + .expect("in tx") + ), + 10 + ); + tx.rollback(); +} + +#[test] +fn rounds_are_counted_per_stratum() { + let db = setup(OpenOptions::new()); + db.execute("(transact [[:f :edge2 :g] [:g :edge2 :h] [:h :edge2 :i] [:i :edge2 :j]])") + .expect("edges2"); + db.execute("(rule [(reach2 ?x ?y) [?x :edge2 ?y] (not (reach ?x ?y))])") + .expect("rule"); + db.execute("(rule [(reach2 ?x ?y) [?x :edge2 ?z] (reach2 ?z ?y)])") + .expect("rule"); + let q = "(query [:find ?x ?y :where (reach2 ?x ?y)])"; + // Two strata of REACH_ROUNDS each: a total count would need twice as many. + assert_eq!( + rows( + db.execute(&with_iterations(q, REACH_ROUNDS)) + .expect("per stratum") + ), + 10 + ); + assert_eq!( + code(db.execute(&with_iterations(q, REACH_ROUNDS - 1))), + "INT-020" + ); +} + +#[test] +fn iterations_keyword_is_in_the_defaults_and_gated() { + assert!(Overridable::DEFAULTS.contains(&Overridable::MaxIterations)); + assert_eq!(Overridable::MaxIterations.keyword(), ":max-iterations"); + let db = setup(OpenOptions::new().allow_overrides([])); + let q = with_iterations(REACH, 10); + assert_eq!(code(db.execute(&q)), "API-025"); + assert_eq!(db.query(&q).err().expect("query").code(), "API-025"); + assert_eq!(db.prepare(&q).err().expect("prepare").code(), "API-025"); + let err = db.execute(&q).err().expect("refused").to_string(); + assert!( + err.contains("Overridable::MaxIterations"), + "names the variant" + ); + let db = setup(OpenOptions::new().allow_overrides([Overridable::MaxIterations])); + assert_eq!(rows(db.execute(&q).expect("listed")), 10); +} + +#[test] +fn iterations_keyword_validation() { + let db = setup(OpenOptions::new()); + for (opt, want) in [ + (":max-iterations 3 :max-iterations 4", "INT-012"), + (":max-iterations", "INT-013"), + (":max-iterations 0", "INT-014"), + (":max-iterations -2", "INT-014"), + (":max-iterations \"x\"", "INT-015"), + ] { + assert_eq!(code(db.execute(&with(REACH, opt))), want, "{opt}"); + } +} + +#[test] +fn iterations_slot_changes_per_execution() { + let db = setup(OpenOptions::new()); + let pq = db + .prepare(&with(REACH, ":max-iterations $n")) + .expect("prepare"); + assert_eq!(code(pq.execute(&[("n", int(REACH_ROUNDS - 1))])), "INT-020"); + assert_eq!( + rows(pq.execute(&[("n", int(REACH_ROUNDS))]).expect("ok")), + 10 + ); + assert_eq!( + pq.query(&[("n", int(REACH_ROUNDS))]) + .expect("cursor") + .count(), + 10 + ); + assert_eq!(code(pq.execute(&[("n", int(0))])), "INT-014"); + let string = BindValue::Val(Value::String("x".into())); + assert_eq!(code(pq.execute(&[("n", string)])), "API-024"); + assert_eq!(code(pq.execute(&[])), "API-022"); + assert_eq!( + code(db.execute(&with(REACH, ":max-iterations $n"))), + "API-010" + ); +} + +#[test] +fn iterations_setter_replaces_the_database_value() { + let db = setup(OpenOptions::new()); + let low = db + .prepare(REACH) + .expect("prepare") + .with_max_iterations(REACH_ROUNDS as usize - 1); + assert_eq!(code(low.execute(&[])), "INT-020"); + assert_eq!(low.query(&[]).err().expect("cursor").code(), "INT-020"); + + let db = setup(OpenOptions::new().allow_overrides([]).max_iterations(1)); + let high = db + .prepare(REACH) + .expect("prepare") + .with_max_iterations(REACH_ROUNDS as usize); + assert_eq!(rows(high.execute(&[]).expect("ungated")), 10); + + let db = setup(OpenOptions::new()); + let pq = db + .prepare(&with_iterations(REACH, REACH_ROUNDS)) + .expect("prepare") + .with_max_iterations(1); + assert_eq!(rows(pq.execute(&[]).expect("keyword wins")), 10); +}