diff --git a/.github/workflows/binary-size.yml b/.github/workflows/binary-size.yml index 7c7ddcb03..91a79d5a3 100644 --- a/.github/workflows/binary-size.yml +++ b/.github/workflows/binary-size.yml @@ -14,7 +14,7 @@ jobs: name: Check distribution binary size runs-on: ubuntu-latest env: - SIZE_LIMIT_BYTES: 1263616 # 1234 KiB — #277 error codes, #306 top-k, #723 ancestor join planning; see PHILOSOPHY.md §4 + SIZE_LIMIT_BYTES: 1269760 # 1240 KiB — #277 error codes, #306 top-k, #723 ancestor join planning, #870/#861 query limit keywords; see PHILOSOPHY.md §4 steps: - name: Checkout code uses: actions/checkout@v4 diff --git a/CHANGELOG.md b/CHANGELOG.md index 7cd8ca2dc..045fd07cd 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -11,8 +11,12 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **`OpenOptions::allow_overrides`** (#869, part of #862): the embedder lists, as `Overridable` variants, the query keywords that may override the database's settings. The default, `Overridable::DEFAULTS` (`MaxDerivedFacts`, `MaxResults`), allows every keyword that could do so before, so no query changes. A query using a keyword the list leaves out is refused with the new **API-025** before it runs, from `execute`, `query`, `prepare` and `WriteTransaction::execute`; the list replaces the defaults rather than adding to them, and is not stored in the file. `BrowserDb` takes no options and uses the defaults. `Overridable` is `#[non_exhaustive]`. +- **`: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). + ### 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. + - **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). diff --git a/CLAUDE.md b/CLAUDE.md index 41e981068..37ab97383 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -42,7 +42,7 @@ Minigraf follows the "SQLite for bi-temporal graph databases" philosophy: - **Zero-configuration** - No setup, no config files, just works - **Embedded-first** - Library not server, in-process execution - **Single-file database** - One portable `.graph` file -- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,234 KiB enforced on v3 since #723; see PHILOSOPHY.md §4) +- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,240 KiB enforced on v3 since #870; see PHILOSOPHY.md §4) - **Cross-platform** - Native, WASM, mobile, embedded - **Reliability over features** - Do less, do it perfectly - **Bi-temporal first-class** - Time travel is a core feature, not addon @@ -163,7 +163,7 @@ 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`); 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`; 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) - `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) @@ -171,9 +171,9 @@ cargo run < demos/demo_negation.txt - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits 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` literal or slot, #306), `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) 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) + - `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) - `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. @@ -183,7 +183,7 @@ 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`) and `check_overrides`, called after parsing at every query entry point (`BrowserDb` uses `DEFAULTS`) + - `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`) - `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 -**2071 tests** (2050 active, 21 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**2094 tests** (2073 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/PHILOSOPHY.md b/PHILOSOPHY.md index 4fea25687..6185def96 100644 --- a/PHILOSOPHY.md +++ b/PHILOSOPHY.md @@ -119,6 +119,10 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s The approved #723 ancestor-join optimization raises it to 1,234 KiB: the measured increase is 2,720 bytes, avoiding a whole-attribute value map for selective in-memory recursion without adding a storage index. + The #862 limit keywords raise it to 1,240 KiB: `:query-memory-limit`, + limit bind slots and the `PreparedQuery` setters (#870) measured +672 + bytes, 312 over the old gate, and the limit leaves room for + `:max-iterations` (#861), which is built the same way. The gate builds the x86_64 Linux CLI with cargo-dist's `dist` profile, the one releases ship. From v3.0.0 `dist` keeps release's full LTO rather than thin LTO, 7–31% smaller per target (#796; sizes per target diff --git a/docs/CONFIGURATION.md b/docs/CONFIGURATION.md index fb3f9c300..9c86f9669 100644 --- a/docs/CONFIGURATION.md +++ b/docs/CONFIGURATION.md @@ -17,9 +17,9 @@ code are not gated. | `OpenOptions` field | Default | Also changed by | Semantics of an override | |---|---|---|---| -| `max_derived_facts` | 1,000,000 | query text: `:max-derived-facts N` | Replaces the database value for that query, up or down | -| `max_results` (deprecated) | no limit of its own | query text: `:max-results N` | Alone, replaces the database value; with `:max-derived-facts`, the lower applies | -| `query_memory_limit` | no limit | — (query keyword and `PreparedQuery` setter planned, #870) | — | +| `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) | — | | `transaction_chunk_facts` | 65,536 | — (per-transaction `TxOptions` planned, #871) | — | | `synchronous` | `SyncMode::Full` | — (per-transaction `TxOptions` planned, #871) | — | @@ -41,6 +41,7 @@ database's settings, as `Overridable` variants: |---|---|---| | `Overridable::MaxDerivedFacts` | `:max-derived-facts` | yes | | `Overridable::MaxResults` | `:max-results` | yes | +| `Overridable::QueryMemoryLimit` | `:query-memory-limit` | no | The default, `Overridable::DEFAULTS`, allows every keyword that could override a setting before the list existed, so existing queries keep @@ -78,5 +79,55 @@ let opts = OpenOptions::new().allow_overrides( ``` `Overridable` is `#[non_exhaustive]`: later releases add variants for new -keywords, such as `:query-memory-limit` (#870, not in `DEFAULTS`) and -`:max-iterations` (#861, in `DEFAULTS`). +keywords, such as `:max-iterations` (#861, in `DEFAULTS`). + +`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 +change the limit: + +```rust +use minigraf::{OpenOptions, Overridable}; + +let db = OpenOptions::new() + .query_memory_limit(64 << 20) + .allow_overrides(Overridable::DEFAULTS.iter().copied().chain([Overridable::QueryMemoryLimit])) + .open_memory()?; +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 +`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) | +| `: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` +refuse a query with an unbound slot (`API-010`). + +`:query-memory-limit 0` lets a query run only if it holds no state: no hash +join, aggregate, sort, distinct set or rule relation, and no entity ids to +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`. + +## `PreparedQuery` setters + +`PreparedQuery::with_max_derived_facts(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 +keyword in the prepared text, literal or slot, still overrides the setter. +`usize::MAX` means no limit. + +```rust +let pq = db + .prepare("(query [:find ?x ?y :where (reach ?x ?y)])")? + .with_max_derived_facts(10_000) + .with_query_memory_limit(16 << 20); +let rows = pq.execute(&[])?; +``` diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 7fefa70ff..79c33ed71 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -255,7 +255,7 @@ with no `CodedError` anywhere in its chain. | INT-012 | Duplicate query option | Internal | | INT-013 | Query option requires a value | Internal | | INT-014 | Query option must be >= 1 | Internal | -| INT-015 | Query option must be a positive integer | Internal | +| INT-015 | Query option must be a non-negative integer | Internal | | INT-016 | (or)/(or-join) nested inside (not)/(not-join) | Internal | | INT-017 | Pseudo-attribute not valid in this position | Internal | | INT-018 | Variable not bound by any outer/earlier clause | Internal | @@ -3848,8 +3848,9 @@ 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`, `:limit`, -`:offset`, `:order-by` or `:distinct` more than once. +**Cause**: A query specified `:max-derived-facts`, `:max-results`, +`:query-memory-limit`, `:limit`, `:offset`, `:order-by` or `:distinct` more +than once. **Resolution**: - Specify each query option at most once. @@ -3858,31 +3859,35 @@ clause, `not`/`not-join`/`or`/`or-join`, a rule invocation, or `and`). The **Error text**: `{} requires a value` -**Cause**: A query option keyword (`:max-derived-facts` or `:max-results`) -was present with no following value. +**Cause**: A query option keyword (`:max-derived-facts`, `:max-results` or +`:query-memory-limit`) was present with no following value. **Resolution**: -- Supply a positive integer value after the option keyword. +- Supply an integer value or a `$slot` after the option keyword. ### INT-014 Query option must be >= 1 **Error text**: `{} must be >= 1` **Cause**: `:max-derived-facts` or `:max-results` was given a value less -than 1. +than 1, as a literal or as a prepared query's bind value. **Resolution**: - Use a value of 1 or greater. -### INT-015 Query option must be a positive integer +### INT-015 Query option must be a non-negative integer -**Error text**: `{} must be a positive integer` +**Error text**: `{} must be a non-negative integer` **Cause**: `:max-derived-facts` or `:max-results` was given a non-integer -value. +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 a positive integer literal. +- Supply an integer literal or a `$slot`: at least 1 for + `:max-derived-facts` and `:max-results`, at least 0 for + `:query-memory-limit`. ### INT-016 (or)/(or-join) nested inside (not)/(not-join) diff --git a/docs/GRAMMAR.md b/docs/GRAMMAR.md index 2df37160b..230940442 100644 --- a/docs/GRAMMAR.md +++ b/docs/GRAMMAR.md @@ -10,28 +10,29 @@ EBNF has no lookahead, so a pest lookahead appears as a comment: `(* not followe ```ebnf (* ── WORD-BOUNDARY HELPER ── *) -word-cont ::= letter | numeral | "?" | "_" | "-" | "/" -kw-find ::= ":find" (* not followed by word-cont *) (* token *) -kw-where ::= ":where" (* not followed by word-cont *) (* token *) -kw-with ::= ":with" (* not followed by word-cont *) (* token *) -kw-as-of ::= ":as-of" (* not followed by word-cont *) (* token *) -kw-valid-at ::= ":valid-at" (* not followed by word-cont *) (* token *) -kw-any-valid-time ::= ":any-valid-time" (* not followed by word-cont *) (* token *) -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-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 *) -kw-over ::= ":over" (* not followed by word-cont *) (* token *) -kw-rows ::= ":rows" (* not followed by word-cont *) (* token *) -kw-partition-by ::= ":partition-by" (* not followed by word-cont *) (* token *) -kw-order-by ::= ":order-by" (* not followed by word-cont *) (* token *) -kw-desc ::= ":desc" (* not followed by word-cont *) (* token *) -kw-asc ::= ":asc" (* not followed by word-cont *) (* token *) -kw-valid-from ::= ":valid-from" (* not followed by word-cont *) (* token *) -kw-valid-to ::= ":valid-to" (* not followed by word-cont *) (* token *) -reserved-head ::= ("not-join" | "not" | "or-join" | "or") (* not followed by word-cont *) (* token *) -and-head ::= "and" (* not followed by word-cont *) (* token *) +word-cont ::= letter | numeral | "?" | "_" | "-" | "/" +kw-find ::= ":find" (* not followed by word-cont *) (* token *) +kw-where ::= ":where" (* not followed by word-cont *) (* token *) +kw-with ::= ":with" (* not followed by word-cont *) (* token *) +kw-as-of ::= ":as-of" (* not followed by word-cont *) (* token *) +kw-valid-at ::= ":valid-at" (* not followed by word-cont *) (* token *) +kw-any-valid-time ::= ":any-valid-time" (* not followed by word-cont *) (* token *) +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-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 *) +kw-over ::= ":over" (* not followed by word-cont *) (* token *) +kw-rows ::= ":rows" (* not followed by word-cont *) (* token *) +kw-partition-by ::= ":partition-by" (* not followed by word-cont *) (* token *) +kw-order-by ::= ":order-by" (* not followed by word-cont *) (* token *) +kw-desc ::= ":desc" (* not followed by word-cont *) (* token *) +kw-asc ::= ":asc" (* not followed by word-cont *) (* token *) +kw-valid-from ::= ":valid-from" (* not followed by word-cont *) (* token *) +kw-valid-to ::= ":valid-to" (* not followed by word-cont *) (* token *) +reserved-head ::= ("not-join" | "not" | "or-join" | "or") (* not followed by word-cont *) (* token *) +and-head ::= "and" (* not followed by word-cont *) (* token *) (* ── EDN PRIMITIVES ── *) boolean-lit ::= ("true" | "false") (* not followed by word-cont *) (* token *) @@ -80,8 +81,8 @@ 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 | limit-section | offset-section - | order-by-section | distinct-section + | max-results-section | query-memory-limit-section | limit-section + | offset-section | order-by-section | distinct-section (* ── FIND SECTION ── *) find-section ::= kw-find find-spec+ @@ -123,17 +124,18 @@ expr-arg ::= expr | set-lit | boolean-lit | nil-lit | float-lit | intege | string-lit | bind-slot | keyword | variable (* ── TEMPORAL / WITH SECTIONS ── *) -as-of-section ::= kw-as-of (integer-lit | string-lit | bind-slot) -valid-at-section ::= kw-valid-at (string-lit | kw-any-valid-time | bind-slot) -any-valid-time-section ::= kw-any-valid-time -with-section ::= kw-with variable+ -max-derived-facts-section ::= kw-max-derived-facts integer-lit -max-results-section ::= kw-max-results integer-lit -limit-section ::= kw-limit (integer-lit | bind-slot) -offset-section ::= kw-offset (integer-lit | bind-slot) -distinct-section ::= kw-distinct -order-by-section ::= kw-order-by "[" order-entry+ "]" -order-entry ::= find-spec (kw-asc | kw-desc)? +as-of-section ::= kw-as-of (integer-lit | string-lit | bind-slot) +valid-at-section ::= kw-valid-at (string-lit | kw-any-valid-time | bind-slot) +any-valid-time-section ::= kw-any-valid-time +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) +limit-section ::= kw-limit (integer-lit | bind-slot) +offset-section ::= kw-offset (integer-lit | bind-slot) +distinct-section ::= kw-distinct +order-by-section ::= kw-order-by "[" order-entry+ "]" +order-entry ::= find-spec (kw-asc | kw-desc)? (* ── RULE ── *) rule-cmd ::= "(" "rule" rule-vector ")" diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index ab082c56e..7d965de61 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,12 +4,12 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Active** | 2,050 | 2,085 | +| **Active** | 2,073 | 2,108 | | **Ignored** | 21 | 24 | -| **Total** | 2,071 | 2,109 | +| **Total** | 2,094 | 2,132 | Counts above are the current Cargo test inventory (active versus ignored), -including #777, #789, #781, #794, #795, #837, #865 and #869 (Linux). Verification results below identify which suites ran. +including #777, #789, #781, #794, #795, #837, #865, #869 and #870 (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 @@ -642,6 +642,7 @@ These are not `#[test]`s; run them with `cargo kani` or `.github/workflows/kani. - Thirteen new `tests/grammar/invalid/syntax/` fixtures. - **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. ## Browser and WASI diff --git a/docs/superpowers/plans/2026-11-06-870-query-memory-limit.md b/docs/superpowers/plans/2026-11-06-870-query-memory-limit.md new file mode 100644 index 000000000..a72641dc7 --- /dev/null +++ b/docs/superpowers/plans/2026-11-06-870-query-memory-limit.md @@ -0,0 +1,102 @@ +# #870 plan: `:query-memory-limit`, limit bind slots, `PreparedQuery` setters + +Spec: `docs/superpowers/specs/2026-11-06-862-override-audit-design.md` §3–§5, §9 (PR 2 of §8), merged in #868. +Branch `feat/870-memory-limit` off `v3` at `b79ff1d6` (after #869). One PR to `v3`, with `Refs #870, #862` in its body. Closing keywords do not fire on `v3`, so close #870 with `gh issue close` after the merge. + +## 1. Types (`types.rs`) + +- `DatalogQuery::max_derived_facts` and `max_results` become `Option`. A new field, `query_memory_limit: Option`, is added. `Count` keeps its two variants (`Literal(usize)`, `Slot(String)`), and its doc now lists every keyword that uses it. +- `Count::literal(&self, option) -> Result` returns the literal, or the invariant error `plan.rs` uses today when a slot reaches the planner. `plan.rs`'s `count` closure calls it. + +## 2. Parser (`parser.rs`) + +- `:max-derived-facts` / `:max-results`: as today (INT-012 duplicate, INT-013 missing, INT-014 for `< 1`, INT-015 for a non-integer), plus `EdnValue::BindSlot` → `Count::Slot`. +- `:query-memory-limit`: the same arm shape. `Integer(n) if n >= 0` → `Literal`, `BindSlot` → `Slot`, a negative integer or a non-integer → INT-015. INT-012/013 as above. +- **Deviation 1.** INT-015's text is `{} must be a positive integer`. That is wrong for `:query-memory-limit`, where 0 is allowed. Change the text to `{} must be a non-negative integer`, both in `error.rs` and in `ERROR_REFERENCE.md`. The heading becomes "Query option must be a non-negative integer", and the cause lists all three keywords. The code is unchanged, and for the two older keywords the new text is still true (INT-014 then rejects 0). + +## 3. Gate (`overrides.rs`) + +- Add `Overridable::QueryMemoryLimit` (keyword `:query-memory-limit`, name `QueryMemoryLimit`). It is not added to `DEFAULTS`. +- `check_overrides` checks in a fixed order: `MaxDerivedFacts`, `MaxResults`, `QueryMemoryLimit`. Presence is `is_some()`, so a slot counts as presence. +- BrowserDb calls the check with `DEFAULTS` (#869), so it refuses `:query-memory-limit` with API-025 and needs no other change. + +## 4. Executor (`executor.rs`) + +- `derived_limit` reads the literals through `Count::literal`, and so returns `Result`. +- Add `memory_limit(query) -> Result`, which returns the keyword's literal if the query has one and otherwise the executor's `query_memory_limit`. Both `open` (passed to `engine::open`) and `open_rule_query` (`Limits::query_memory`) use it. +- No `db.rs` change is needed: every entry point (`execute`, `query`, `WriteTransaction::execute`, prepared) ends up in these two functions. + +## 5. Slots (`prepared.rs`) + +- `collect_slot_names` also collects the three limit slots. That way `reject_unbound_slots` gives API-010 on `execute`/`query`, and `bind` gives API-022 for a missing value. +- `substitute` resolves each one with `resolve_limit_slot(name, keyword, min, bindings)`: + - `Val(Integer(n))` with `n >= min` → `Literal`. + - `n < min`: INT-014 for `min == 1`, INT-015 for `min == 0`, matching the literal form. + - Any other type → API-024 (`Val(Integer)` expected). + - Missing → API-022. +- `min` is 1 for `:max-derived-facts`/`:max-results` and 0 for `:query-memory-limit`. + +## 6. Setters (`prepared.rs`) + +```rust +impl PreparedQuery { + /// Replace the database's `max_derived_facts` for this statement. An allowed + /// `:max-derived-facts` / `:max-results` in the query still overrides it. + pub fn with_max_derived_facts(mut self, n: usize) -> Self { self.limits.0 = n; self } + /// Replace the database's `query_memory_limit` for this statement. + pub fn with_query_memory_limit(mut self, bytes: usize) -> Self { self.limits.1 = bytes; self } +} +``` + +Both are infallible and ungated. `usize::MAX` means no limit, and `0` behaves as at open. Doc tests on both. + +## 7. Grammar and verifier + +- `grammar.pest`: add `kw_query_memory_limit = @{ ":query-memory-limit" ~ !word_cont }`. `max_derived_facts_section` and `max_results_section` take `(integer_lit | bind_slot)`. Add `query_memory_limit_section = { kw_query_memory_limit ~ (integer_lit | bind_slot) }` to the `query_section` alternatives. If the grammar has a keyword list for `word` exclusion, add it there too. +- Regenerate `docs/GRAMMAR.md` (`tests/grammar_doc.rs` bless mode). +- Corpus: `tests/grammar/valid/query_memory_limit.edn` and `query_limit_slots.edn` (slots on all three keywords), plus `tests/grammar/invalid/` seeds if that directory takes them (e.g. `:query-memory-limit :x`). Add a fuzz seed in `fuzz/corpus/datalog_parser/`. +- Verifier: add `":query-memory-limit"` to `TOKENS` (40 → 41). Add `SEMANTIC` INT-015 with the witness `(query [:find ?x :where [?x :a ?y] :query-memory-limit -1])`. +- Run bound 4 on the bench machine. Record the case count and time in the PR body (+~10% fillers). + +## 8. Tests + +`tests/limit_keywords_test.rs` (`#![cfg(not(target_arch = "wasm32"))]`). Assertions are on `code()` only. + +1. **Memory keyword lowers.** A hash-join query passes at the open default, and `:query-memory-limit 1024` makes it fail with QRY-012 (handle allows `QueryMemoryLimit`). +2. **Memory keyword raises.** At open `query_memory_limit(1024)` the same query fails, and with `:query-memory-limit 100000000` it passes. +3. **Zero.** With `:query-memory-limit 0`, a single-pattern scan with a `[(> ?v 1)]` filter returns its rows, while a hash-join query and an aggregate (`count` grouped) fail with QRY-012. A rule query under 0 fails with QRY-012. +4. **Gate.** By default `:query-memory-limit` is refused with API-025 (`execute`, `query`, `prepare`, `WriteTransaction::execute`). It is allowed when listed. `allow_overrides([])` refuses `:max-derived-facts $n` at prepare. +5. **Validation.** Duplicate → INT-012, missing → INT-013, `-1` → INT-015, `"x"` → INT-015. +6. **Slots.** One prepared rule query run with `n` = 1 and with `n` = 1000 for `:max-derived-facts $n` gives INT-020 then rows. The same holds for `:max-results $n`. With `:query-memory-limit $m`, `m` = 0 fails and `m` = `i64::MAX` passes. + - Errors: `Val(String)` → API-024; missing → API-022; `n = 0` on `:max-derived-facts` → INT-014; `m = -1` → INT-015. + - `execute` with a limit slot → API-010. +7. **Setters.** `with_max_derived_facts(1)` makes a rule query fail (INT-020), and `with_max_derived_facts(1000)` on a database opened at `max_derived_facts(1)` passes. A keyword overrides the setter: setter 1 with `:max-derived-facts 1000` passes. `with_query_memory_limit(1024)` makes a join fail and `with_query_memory_limit(usize::MAX)` on a 1024 database passes. Setters work under `allow_overrides([])`, and they also apply to `PreparedQuery::query` (cursor). +8. **Unit.** `check_overrides` order with all three keywords present; parser unit tests for the slot forms and INT codes; `Count::literal` on a slot. +9. **BrowserDb.** A `#[wasm_bindgen_test]` showing `:query-memory-limit` is refused with API-025. + +TDD: write each group failing first, then implement. + +## 9. Docs (same PR) + +- `docs/CONFIGURATION.md`: the `query_memory_limit` row is now done (keyword + setter); `max_derived_facts` gets `$slot` and the setter; a `:query-memory-limit` example; the "planned (#870)" notes are removed. +- `docs/ERROR_REFERENCE.md`: the new INT-015 text (deviation 1), and the INT-012..015 causes mention `:query-memory-limit`. +- `CHANGELOG.md [Unreleased]` Added: `:query-memory-limit`, limit slots, the setters, `Overridable::QueryMemoryLimit`. Changed: the INT-015 text. +- Test counts in `docs/TEST_COVERAGE.md` and `CLAUDE.md`. In `CLAUDE.md`, the `prepared.rs`/`types.rs` lines mention the limit slots and setters. +- Docs site (`../minigraf-docs`), under ``: `datalog-reference.md` gets the keyword and slot forms, and `performance-tuning.md` gets the setters and the table row. + +## 10. Verification + +- `cargo fmt`; `cargo clippy --all-targets -- -D warnings`. +- Full `cargo test` on the bench machine, plus `--features test-hooks`. +- `cargo build --target wasm32-unknown-unknown --features browser`. +- **Size gate.** Only ~360 B of headroom is left under 1,234 KiB. Measure `--profile dist`, and if it is over, ask the maintainer before raising the gate (with the measured delta). +- Codex review is skipped (quota out until 2026-11-11). Then watch CI until it is green. + +After merge: #861 (`MaxIterations`, reusing `resolve_limit_slot` and the setter pattern), then #872. + +## Deviations found while implementing + +2. **Zero is narrower than spec §3 says.** The meter counts entity ids (`IdSpace`) as held state. Uncheckpointed facts take provisional ids, and a returned entity resolves one. So under `:query-memory-limit 0`, the only query that runs is a value-only one over checkpointed facts. The §8 test 3 "scan-and-filter returns rows" holds only in that case. The tests and docs say so. +3. **`clippy::large_enum_variant` on `DatalogCommand`.** Three `Option` fields push `Query` over the lint threshold. A command is parsed once and moved, so the lint is allowed with a reason instead of boxing the query. +4. **Grammar conformance** opens its handle with every `Overridable` listed, so an API-025 refusal of a valid corpus entry is not reported as a parse error. +5. **Size.** The dist binary is 1,263,928 B, +672 B over base `b79ff1d6` and 312 B over the 1,234 KiB gate. The maintainer chose to raise the gate to 1,240 KiB (1,269,760 B), which leaves room for #861. diff --git a/fuzz/corpus/datalog_parser/09be6f57fcf3d1c36b20951eb8d5f2ce09eddb8f b/fuzz/corpus/datalog_parser/09be6f57fcf3d1c36b20951eb8d5f2ce09eddb8f new file mode 100644 index 000000000..4b9865888 --- /dev/null +++ b/fuzz/corpus/datalog_parser/09be6f57fcf3d1c36b20951eb8d5f2ce09eddb8f @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit $m :max-derived-facts $d]) \ No newline at end of file diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 89237028a..3ed1c1070 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -739,6 +739,20 @@ mod tests { } } + // #870: `:query-memory-limit` is not in the default list, so BrowserDb + // refuses it. + #[wasm_bindgen_test] + async fn query_memory_limit_keyword_is_refused() { + let db = BrowserDb::open_in_memory().expect("open_in_memory"); + let err = db + .execute("(query [:find ?x :where [?e :a ?x] :query-memory-limit 1000])".to_string()) + .await + .expect_err("refused"); + let text = err.as_string().expect("rejection is a string"); + assert!(text.starts_with("[API-025] "), "rejection is API-025"); + assert!(text.contains(":query-memory-limit"), "names the keyword"); + } + #[wasm_bindgen_test] async fn in_memory_transact_and_query() { let db = BrowserDb::open_in_memory().expect("open_in_memory"); diff --git a/src/error.rs b/src/error.rs index 8cfa97489..37eb3ed52 100644 --- a/src/error.rs +++ b/src/error.rs @@ -1755,7 +1755,7 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ ( ErrorCode::Int015, "INT-015", - "{} must be a positive integer", + "{} must be a non-negative integer", ErrorCategory::Internal, ), ( diff --git a/src/overrides.rs b/src/overrides.rs index 6ac4258ce..59ed146f3 100644 --- a/src/overrides.rs +++ b/src/overrides.rs @@ -21,6 +21,11 @@ pub enum Overridable { MaxDerivedFacts, /// `:max-results N`, the deprecated alias of `:max-derived-facts`. MaxResults, + /// `:query-memory-limit N`, which overrides + /// [`OpenOptions::query_memory_limit`](crate::OpenOptions::query_memory_limit) + /// (#870). Not in [`DEFAULTS`](Self::DEFAULTS): query text can raise the + /// limit that keeps it from exhausting memory. + QueryMemoryLimit, } impl Overridable { @@ -35,6 +40,7 @@ impl Overridable { match self { Overridable::MaxDerivedFacts => ":max-derived-facts", Overridable::MaxResults => ":max-results", + Overridable::QueryMemoryLimit => ":query-memory-limit", } } @@ -42,6 +48,7 @@ impl Overridable { match self { Overridable::MaxDerivedFacts => "MaxDerivedFacts", Overridable::MaxResults => "MaxResults", + Overridable::QueryMemoryLimit => "QueryMemoryLimit", } } } @@ -57,6 +64,10 @@ pub(crate) fn check_overrides(query: &DatalogQuery, allowed: &[Overridable]) -> query.max_derived_facts.is_some(), ), (Overridable::MaxResults, query.max_results.is_some()), + ( + Overridable::QueryMemoryLimit, + query.query_memory_limit.is_some(), + ), ]; for (setting, used) in present { if used && !allowed.contains(&setting) { @@ -95,6 +106,30 @@ mod tests { assert!(!err.to_string().contains(":max-results")); } + #[test] + 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])", + ); + let first = |allowed: &[Overridable]| { + crate::MinigrafError::from(check_overrides(&q, allowed).expect_err("refused")) + .to_string() + }; + assert!(first(&[]).contains(":max-derived-facts")); + assert!(first(&[Overridable::MaxDerivedFacts]).contains(":max-results")); + let last = first(Overridable::DEFAULTS); + assert!(last.contains(":query-memory-limit")); + assert!(last.contains("Overridable::QueryMemoryLimit")); + let all: Vec<_> = Overridable::DEFAULTS + .iter() + .copied() + .chain([Overridable::QueryMemoryLimit]) + .collect(); + check_overrides(&q, &all).expect("all listed"); + assert!(!Overridable::DEFAULTS.contains(&Overridable::QueryMemoryLimit)); + } + #[test] fn listed_and_absent_keywords_pass() { let both = diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 41f3b0b58..d6ed401a2 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -341,8 +341,12 @@ impl DatalogExecutor { }; check_clauses(&query, &functions)?; let snapshot = self.read_snapshot()?; - let stream = - crate::query::engine::open(snapshot.clone(), plan, functions, self.query_memory_limit)?; + let stream = crate::query::engine::open( + snapshot.clone(), + plan, + functions, + self.memory_limit(&query)?, + )?; #[cfg(test)] crate::query::engine::RUNS.with(|r| r.set(r.get() + 1)); Ok(Answer::Stream(Box::new(stream))) @@ -382,8 +386,8 @@ impl DatalogExecutor { check_per_fact_pseudo_attrs(query)?; let limits = crate::query::engine::Limits { max_iterations: crate::query::datalog::evaluator::DEFAULT_MAX_ITERATIONS, - max_derived_facts: self.derived_limit(query), - query_memory: self.query_memory_limit, + max_derived_facts: self.derived_limit(query)?, + query_memory: self.memory_limit(query)?, }; let snapshot = self.read_snapshot()?; // The keywords the query's rule calls name as entities (#721). @@ -423,10 +427,23 @@ impl DatalogExecutor { /// The most facts `query`'s rules may derive: a per-query limit replaces /// the executor's; `:max-results` is a deprecated alias of /// `:max-derived-facts`, and the lower of the two applies (#553). - fn derived_limit(&self, query: &DatalogQuery) -> usize { - match (query.max_derived_facts, query.max_results) { + fn derived_limit(&self, query: &DatalogQuery) -> Result { + let limit = |c: &Option, option| match c { + Some(c) => c.literal(option), + None => Ok(usize::MAX), + }; + Ok(match (&query.max_derived_facts, &query.max_results) { (None, None) => self.max_derived_facts, - (a, b) => a.unwrap_or(usize::MAX).min(b.unwrap_or(usize::MAX)), + (a, b) => limit(a, ":max-derived-facts")?.min(limit(b, ":max-results")?), + }) + } + + /// The most bytes `query` may hold: its `:query-memory-limit` replaces + /// the executor's (#870). + 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), } } @@ -1532,6 +1549,7 @@ mod tests { with_vars: Vec::new(), max_derived_facts: None, max_results: None, + query_memory_limit: None, limit: None, offset: None, order_by: Vec::new(), @@ -1594,6 +1612,7 @@ mod tests { with_vars: Vec::new(), max_derived_facts: None, max_results: None, + query_memory_limit: None, limit: None, offset: None, order_by: Vec::new(), diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index a6322bf92..526eb39f8 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -897,8 +897,9 @@ fn parse_query(elements: &[EdnValue]) -> Result { let mut current_clause: Option<&str> = None; let mut query_as_of: Option = None; let mut query_valid_at: Option = None; - let mut query_max_derived_facts: Option = None; - let mut query_max_results: Option = None; + 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_limit: Option = None; let mut query_offset: Option = None; let mut query_order_by: Option> = None; @@ -981,55 +982,33 @@ fn parse_query(elements: &[EdnValue]) -> Result { i += 1; continue; } - ":max-derived-facts" => { + ":max-derived-facts" | ":max-results" | ":query-memory-limit" => { current_clause = None; - if query_max_derived_facts.is_some() { - bail_coded!(ErrorCode::Int012, ":max-derived-facts"); - } - i += 1; - let val = query_vector - .get(i) - .ok_or_else(|| err_coded!(ErrorCode::Int013, ":max-derived-facts"))?; - match val { - EdnValue::Integer(n) if *n >= 1 => { - #[allow(clippy::cast_sign_loss, clippy::cast_possible_truncation)] - { - query_max_derived_facts = Some(*n as usize); - } - } - EdnValue::Integer(_) => { - bail_coded!(ErrorCode::Int014, ":max-derived-facts"); - } - _other => { - bail_coded!(ErrorCode::Int015, ":max-derived-facts"); - } - } - i += 1; - continue; - } - ":max-results" => { - current_clause = None; - if query_max_results.is_some() { - bail_coded!(ErrorCode::Int012, ":max-results"); + let (target, min) = match keyword { + ":max-derived-facts" => (&mut query_max_derived_facts, 1), + ":max-results" => (&mut query_max_results, 1), + _ => (&mut query_query_memory_limit, 0), + }; + if target.is_some() { + bail_coded!(ErrorCode::Int012, keyword); } i += 1; let val = query_vector .get(i) - .ok_or_else(|| err_coded!(ErrorCode::Int013, ":max-results"))?; - match val { - EdnValue::Integer(n) if *n >= 1 => { - #[allow(clippy::cast_sign_loss, clippy::cast_possible_truncation)] - { - query_max_results = Some(*n as usize); - } + .ok_or_else(|| err_coded!(ErrorCode::Int013, keyword))?; + *target = Some(match val { + EdnValue::Integer(n) if *n >= min => { + Count::Literal(usize::try_from(*n).unwrap_or(usize::MAX)) } - EdnValue::Integer(_) => { - bail_coded!(ErrorCode::Int014, ":max-results"); + // Only the two older keywords reject zero (INT-014). + EdnValue::Integer(_) if min == 1 => { + bail_coded!(ErrorCode::Int014, keyword); } + EdnValue::BindSlot(name) => Count::Slot(name.clone()), _other => { - bail_coded!(ErrorCode::Int015, ":max-results"); + bail_coded!(ErrorCode::Int015, keyword); } - } + }); i += 1; continue; } @@ -1254,6 +1233,7 @@ fn parse_query(elements: &[EdnValue]) -> Result { query.with_vars = with_vars; query.max_derived_facts = query_max_derived_facts; query.max_results = query_max_results; + query.query_memory_limit = query_query_memory_limit; query.limit = query_limit; query.offset = query_offset; query.order_by = order_by; @@ -3110,7 +3090,7 @@ mod tests { assert!(result.is_ok(), "should parse :max-derived-facts"); match result.unwrap() { DatalogCommand::Query(q) => { - assert_eq!(q.max_derived_facts, Some(500_000)); + assert_eq!(q.max_derived_facts, Some(Count::Literal(500_000))); assert_eq!(q.max_results, None); } _ => panic!("expected Query"), @@ -3125,7 +3105,7 @@ mod tests { match result.unwrap() { DatalogCommand::Query(q) => { assert_eq!(q.max_derived_facts, None); - assert_eq!(q.max_results, Some(9_999)); + assert_eq!(q.max_results, Some(Count::Literal(9_999))); } _ => panic!("expected Query"), } @@ -3139,8 +3119,8 @@ mod tests { assert!(result.is_ok(), "should parse both limit keys"); match result.unwrap() { DatalogCommand::Query(q) => { - assert_eq!(q.max_derived_facts, Some(1_000_000)); - assert_eq!(q.max_results, Some(100)); + assert_eq!(q.max_derived_facts, Some(Count::Literal(1_000_000))); + assert_eq!(q.max_results, Some(Count::Literal(100))); } _ => panic!("expected Query"), } @@ -3383,6 +3363,53 @@ mod tests { } } + #[test] + fn limit_keywords_take_slots_and_query_memory_limit_zero() { + let input = "(query [:find ?x :where [?x :a :b] :max-derived-facts $d \ + :max-results $r :query-memory-limit $m])"; + match parse_datalog_command(input).expect("slots") { + DatalogCommand::Query(q) => { + assert_eq!(q.max_derived_facts, Some(Count::Slot("d".into()))); + assert_eq!(q.max_results, Some(Count::Slot("r".into()))); + assert_eq!(q.query_memory_limit, Some(Count::Slot("m".into()))); + } + _ => panic!("expected a query"), + } + let input = "(query [:find ?x :where [?x :a :b] :query-memory-limit 0])"; + match parse_datalog_command(input).expect("zero") { + DatalogCommand::Query(q) => { + assert_eq!(q.query_memory_limit, Some(Count::Literal(0))); + } + _ => panic!("expected a query"), + } + } + + #[test] + fn query_memory_limit_errors() { + let code = |opt: &str| { + let input = format!("(query [:find ?x :where [?x :a :b] {opt}])"); + crate::MinigrafError::from(parse_datalog_command(&input).expect_err(opt)) + .code() + .to_string() + }; + assert_eq!( + code(":query-memory-limit 1 :query-memory-limit 2"), + "INT-012" + ); + assert_eq!(code(":query-memory-limit"), "INT-013"); + assert_eq!(code(":query-memory-limit -1"), "INT-015"); + assert_eq!(code(":query-memory-limit :x"), "INT-015"); + assert_eq!(code(":max-derived-facts 0"), "INT-014"); + } + + #[test] + fn count_literal_refuses_a_slot() { + assert_eq!(Count::Literal(3).literal(":x").expect("literal"), 3); + let err = + crate::MinigrafError::from(Count::Slot("s".into()).literal(":x").expect_err("slot")); + assert_eq!(err.code(), "INT-032"); + } + #[test] fn test_parse_max_derived_facts_non_integer_rejected() { let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts "a lot"])"#; @@ -3390,7 +3417,7 @@ mod tests { assert!(result.is_err(), "non-integer should be rejected"); let msg = result.unwrap_err().to_string(); assert!( - msg.contains(":max-derived-facts must be a positive integer"), + msg.contains(":max-derived-facts must be a non-negative integer"), "wrong error: {}", msg ); @@ -3403,7 +3430,7 @@ mod tests { assert!(result.is_err(), "non-integer should be rejected"); let msg = result.unwrap_err().to_string(); assert!( - msg.contains(":max-results must be a positive integer"), + msg.contains(":max-results must be a non-negative integer"), "wrong error: {}", msg ); @@ -3484,7 +3511,7 @@ mod tests { let result = parse_datalog_command(input); assert!(result.is_ok(), "order should not matter"); match result.unwrap() { - DatalogCommand::Query(q) => assert_eq!(q.max_derived_facts, Some(42)), + DatalogCommand::Query(q) => assert_eq!(q.max_derived_facts, Some(Count::Literal(42))), _ => panic!("expected Query"), } } diff --git a/src/query/datalog/parser/verifier.rs b/src/query/datalog/parser/verifier.rs index 90be92045..5b6041ac4 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; 40] = [ +const TOKENS: [&str; 41] = [ "(", ")", "[", @@ -90,6 +90,7 @@ const TOKENS: [&str; 40] = [ ":order-by", ":limit", ":offset", + ":query-memory-limit", ":distinct", ":asc", ":desc", @@ -235,6 +236,12 @@ const SEMANTIC: &[Semantic] = &[ code: "PRS-115", witness: "(query [:find ?x :where [?x :a ?y] :limit -1])", }, + // parse_query: a negative `:query-memory-limit` (`integer_lit` takes a + // sign, #870). + Semantic { + code: "INT-015", + witness: "(query [:find ?x :where [?x :a ?y] :query-memory-limit -1])", + }, // parse_query: `:offset` without `:order-by` (#306). Semantic { code: "PRS-116", @@ -544,10 +551,11 @@ fn filler_counts_match_the_spec() { } n }; - // 40 tokens: the #643 spec's 32, `#{` (#316), `:limit`, `:offset`, - // `:asc`, `:desc` (#306), `:distinct` (#493), and `:rows`, `preceding` (#183). - assert_eq!(count(3), 40_804); - assert_eq!(count(4), 1_397_966); + // 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); } #[test] diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index 00c565eb3..554502c12 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -82,7 +82,8 @@ pub struct PreparedQuery { fact_storage: FactStorage, rules: Arc>, functions: Arc, - /// The database's `max_derived_facts` and `query_memory_limit`. + /// The database's `max_derived_facts` and `query_memory_limit`, or the + /// setters' values (#870). limits: (usize, usize), } @@ -95,6 +96,49 @@ impl std::fmt::Debug for PreparedQuery { } impl PreparedQuery { + /// Replace the database's + /// [`max_derived_facts`](crate::OpenOptions::max_derived_facts) for this + /// statement (#870). An allowed `:max-derived-facts` or `:max-results` in + /// the query still overrides it. `usize::MAX` means no limit. + /// + /// Not gated by [`OpenOptions::allow_overrides`](crate::OpenOptions::allow_overrides): + /// it is application code, not query text. + /// + /// ``` + /// # 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(); + /// let pq = db.prepare("(query [:find ?x ?y :where (reach ?x ?y)])").unwrap(); + /// let err = pq.with_max_derived_facts(1).execute(&[]).unwrap_err(); + /// assert_eq!(err.code(), "INT-020"); + /// ``` + pub fn with_max_derived_facts(mut self, n: usize) -> Self { + self.limits.0 = n; + self + } + + /// Replace the database's + /// [`query_memory_limit`](crate::OpenOptions::query_memory_limit) for this + /// statement (#870). An allowed `:query-memory-limit` in the query still + /// overrides it. `usize::MAX` means no limit; `0` lets only queries that + /// hold no state run. + /// + /// Not gated by [`OpenOptions::allow_overrides`](crate::OpenOptions::allow_overrides). + /// + /// ``` + /// # use minigraf::Minigraf; + /// let db = Minigraf::in_memory().unwrap(); + /// db.execute("(transact [[:a :v 1] [:b :v 1]])").unwrap(); + /// let pq = db.prepare("(query [:find ?v (count ?e) :where [?e :v ?v]])").unwrap(); + /// let err = pq.with_query_memory_limit(16).execute(&[]).unwrap_err(); + /// assert_eq!(err.code(), "QRY-012"); + /// ``` + pub fn with_query_memory_limit(mut self, bytes: usize) -> Self { + self.limits.1 = bytes; + self + } + /// Substitute bind values and execute against the current database state. /// /// Extra bindings not referenced by the query are silently ignored. @@ -250,7 +294,13 @@ fn collect_slot_names(query: &DatalogQuery) -> Vec { if let Some(ValidAt::Slot(name)) = &query.valid_at { names.insert(name.clone()); } - for count in [&query.limit, &query.offset] { + for count in [ + &query.limit, + &query.offset, + &query.max_derived_facts, + &query.max_results, + &query.query_memory_limit, + ] { if let Some(Count::Slot(name)) = count { names.insert(name.clone()); } @@ -340,6 +390,17 @@ fn substitute( query.offset = Some(resolve_count_slot(name, ":offset", bindings)?); } + // The limit keywords (#870): the literal form's range and codes. + for (target, option, min) in [ + (&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), + ] { + if let Some(Count::Slot(name)) = target { + *target = Some(resolve_limit_slot(name, option, min, bindings)?); + } + } + for clause in &mut query.where_clauses { substitute_where_clause(clause, bindings)?; } @@ -513,6 +574,33 @@ fn resolve_count_slot( } } +/// A limit keyword's slot (#870): `Val(Integer(n))` with `n >= min`; below +/// it, INT-014 (`min` 1) or INT-015 (`min` 0), as for a literal. +fn resolve_limit_slot( + name: &str, + option: &str, + min: i64, + bindings: &HashMap<&str, &BindValue>, +) -> Result { + match bindings.get(name) { + Some(BindValue::Val(Value::Integer(n))) if *n >= min => { + Ok(Count::Literal(usize::try_from(*n).unwrap_or(usize::MAX))) + } + Some(BindValue::Val(Value::Integer(_))) if min == 1 => { + bail_coded!(ErrorCode::Int014, option) + } + Some(BindValue::Val(Value::Integer(_))) => bail_coded!(ErrorCode::Int015, option), + Some(other) => bail_coded!( + ErrorCode::Api024, + name, + option, + "Val(Integer)", + bind_value_type_name(other) + ), + None => bail_coded!(ErrorCode::Api022, name), + } +} + fn resolve_valid_at_slot(name: &str, bindings: &HashMap<&str, &BindValue>) -> Result { match bindings.get(name) { Some(BindValue::Timestamp(t)) => Ok(ValidAt::Timestamp(*t)), diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 87d5a972b..d98288cd3 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -580,10 +580,13 @@ pub struct DatalogQuery { /// Per-query `:max-derived-facts`: the most facts the query's rules may /// derive in total, base facts not counted (#553). With neither this nor /// `max_results`, the executor's limit (from `OpenOptions`) applies. - pub max_derived_facts: Option, + pub max_derived_facts: Option, /// Per-query `:max-results`, a deprecated alias of `:max-derived-facts`; /// with both, the lower applies (#553). It never limited returned rows. - pub max_results: Option, + pub max_results: Option, + /// Per-query `:query-memory-limit`: replaces the executor's + /// `query_memory_limit` for this query (#870). + pub query_memory_limit: Option, /// `:limit`: the most rows the query returns (#306). pub limit: Option, /// `:offset`: the rows of the ordered answer skipped before `:limit`'s @@ -597,14 +600,29 @@ pub struct DatalogQuery { pub distinct: bool, } -/// The value of `:limit` or `:offset` (#306): a literal, or a bind slot a -/// prepared query fills. +/// The value of `:limit`, `:offset` (#306), `:max-derived-facts`, +/// `:max-results` or `:query-memory-limit` (#870): a literal, or a bind slot +/// a prepared query fills. #[derive(Debug, Clone, PartialEq, Eq)] pub enum Count { Literal(usize), Slot(String), } +impl Count { + /// The literal. `execute` rejects an unbound slot (API-010) and a + /// prepared query fills every slot, so a slot here is an invariant error. + pub(crate) fn literal(&self, option: &str) -> anyhow::Result { + match self { + Count::Literal(n) => Ok(*n), + Count::Slot(_) => Err(crate::error::err_coded!( + crate::error::ErrorCode::Int032, + format!("a {option} slot reached the planner") + )), + } + } +} + impl DatalogQuery { pub fn new(find: Vec, where_clauses: Vec) -> Self { DatalogQuery { @@ -615,6 +633,7 @@ impl DatalogQuery { with_vars: Vec::new(), max_derived_facts: None, max_results: None, + query_memory_limit: None, limit: None, offset: None, order_by: Vec::new(), @@ -633,6 +652,7 @@ impl DatalogQuery { with_vars: Vec::new(), max_derived_facts: None, max_results: None, + query_memory_limit: None, limit: None, offset: None, order_by: Vec::new(), @@ -800,6 +820,9 @@ pub enum ValidAt { } /// A Datalog command (top-level form) +// A command is parsed once and moved into the executor, never stored in +// bulk, so boxing the query would only add an allocation (#870). +#[allow(clippy::large_enum_variant)] #[derive(Debug, Clone, PartialEq)] pub enum DatalogCommand { /// Execute a query diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index f7fb987db..7bc867958 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -626,11 +626,7 @@ fn plan_with(query: &DatalogQuery, evaluated: Option>) -> Result< // After `finish`, which may still add the steps of a clause list with // no pattern. `execute` rejects an unbound slot (API-010); a prepared // query fills it. - let count = |c: &Option, option: &str| match c { - None => Ok(None), - Some(Count::Literal(n)) => Ok(Some(*n)), - Some(Count::Slot(_)) => Err(invariant(&format!("a {option} slot reached the planner"))), - }; + let count = |c: &Option, option: &str| c.as_ref().map(|c| c.literal(option)).transpose(); let (limit, offset) = ( count(&query.limit, ":limit")?, count(&query.offset, ":offset")?, diff --git a/tests/grammar/grammar.pest b/tests/grammar/grammar.pest index e12e492ae..abf074ef2 100644 --- a/tests/grammar/grammar.pest +++ b/tests/grammar/grammar.pest @@ -19,6 +19,7 @@ kw_valid_at = @{ ":valid-at" ~ !word_cont } 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_limit = @{ ":limit" ~ !word_cont } kw_offset = @{ ":offset" ~ !word_cont } kw_distinct = @{ ":distinct" ~ !word_cont } @@ -132,7 +133,8 @@ 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 | limit_section | + max_derived_facts_section | max_results_section | + query_memory_limit_section | limit_section | offset_section | order_by_section | distinct_section } @@ -213,8 +215,9 @@ as_of_section = { kw_as_of ~ (integer_lit | string_lit | bind_slot) } valid_at_section = { kw_valid_at ~ (string_lit | kw_any_valid_time | bind_slot) } any_valid_time_section = { kw_any_valid_time } with_section = { kw_with ~ variable+ } -max_derived_facts_section = { kw_max_derived_facts ~ integer_lit } -max_results_section = { kw_max_results ~ integer_lit } +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) } 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/query_memory_limit_negative.edn b/tests/grammar/invalid/semantic/query_memory_limit_negative.edn new file mode 100644 index 000000000..5d389fffc --- /dev/null +++ b/tests/grammar/invalid/semantic/query_memory_limit_negative.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit -1]) diff --git a/tests/grammar/invalid/semantic/query_memory_limit_twice.edn b/tests/grammar/invalid/semantic/query_memory_limit_twice.edn new file mode 100644 index 000000000..ed42bfab1 --- /dev/null +++ b/tests/grammar/invalid/semantic/query_memory_limit_twice.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit 1 :query-memory-limit 1]) diff --git a/tests/grammar/invalid/syntax/query_memory_limit_missing.edn b/tests/grammar/invalid/syntax/query_memory_limit_missing.edn new file mode 100644 index 000000000..3cc3ae00d --- /dev/null +++ b/tests/grammar/invalid/syntax/query_memory_limit_missing.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit]) diff --git a/tests/grammar/invalid/syntax/query_memory_limit_string.edn b/tests/grammar/invalid/syntax/query_memory_limit_string.edn new file mode 100644 index 000000000..bdd5c3096 --- /dev/null +++ b/tests/grammar/invalid/syntax/query_memory_limit_string.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit "big"]) diff --git a/tests/grammar/valid/query_limit_keyword_slots.edn b/tests/grammar/valid/query_limit_keyword_slots.edn new file mode 100644 index 000000000..60d049283 --- /dev/null +++ b/tests/grammar/valid/query_limit_keyword_slots.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :max-derived-facts $d :max-results $r :query-memory-limit $m]) diff --git a/tests/grammar/valid/query_memory_limit.edn b/tests/grammar/valid/query_memory_limit.edn new file mode 100644 index 000000000..9bab6c2d9 --- /dev/null +++ b/tests/grammar/valid/query_memory_limit.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit 1048576]) diff --git a/tests/grammar/valid/query_memory_limit_zero.edn b/tests/grammar/valid/query_memory_limit_zero.edn new file mode 100644 index 000000000..214067bcf --- /dev/null +++ b/tests/grammar/valid/query_memory_limit_zero.edn @@ -0,0 +1 @@ +(query [:find ?x :where [?x :a :b] :query-memory-limit 0]) diff --git a/tests/grammar_conformance.rs b/tests/grammar_conformance.rs index 84b6375da..15e563217 100644 --- a/tests/grammar_conformance.rs +++ b/tests/grammar_conformance.rs @@ -26,10 +26,19 @@ fn pest_accepts(input: &str) -> bool { /// /// Uses `db.prepare()` for `(query ...)` commands so that bind-slot /// templates parse correctly without needing substituted values at test time. -/// Uses `db.execute()` for transact / retract / rule. +/// Uses `db.execute()` for transact / retract / rule. The handle allows every +/// override keyword, so `allow_overrides` (API-025, #869) is not a parse error. fn parser_accepts(input: &str) -> bool { + use minigraf::Overridable; let input = input.trim(); - let Ok(db) = minigraf::Minigraf::in_memory() else { + let all = Overridable::DEFAULTS + .iter() + .copied() + .chain([Overridable::QueryMemoryLimit]); + let Ok(db) = minigraf::OpenOptions::new() + .allow_overrides(all) + .open_memory() + else { return false; }; if input.starts_with("(query") { diff --git a/tests/limit_keywords_test.rs b/tests/limit_keywords_test.rs new file mode 100644 index 000000000..920d12767 --- /dev/null +++ b/tests/limit_keywords_test.rs @@ -0,0 +1,353 @@ +#![cfg(not(target_arch = "wasm32"))] +//! `:query-memory-limit`, bind slots on the limit keywords and the +//! `PreparedQuery` limit setters (#870, spec #862 §3–§5). + +use minigraf::{BindValue, Minigraf, MinigrafError, OpenOptions, Overridable, QueryResult, Value}; + +const RULES: [&str; 2] = [ + "(rule [(reach ?x ?y) [?x :edge ?y]])", + "(rule [(reach ?x ?y) [?x :edge ?z] (reach ?z ?y)])", +]; +/// Holds aggregate groups: fails under a small memory limit. +const GROUPED: &str = "(query [:find ?x (count ?y) :where [?e :v ?x] [?e :w ?y]])"; +/// Projects only integers: holds no state. +const VALUES: &str = "(query [:find ?x :where [?e :v ?x] [(> ?x 1)]])"; +/// Derives 10 facts: a chain of 4 edges reaches 4 + 3 + 2 + 1 pairs. +const REACH: &str = "(query [:find ?x ?y :where (reach ?x ?y)])"; + +fn with_memory_keyword() -> OpenOptions { + OpenOptions::new().allow_overrides( + Overridable::DEFAULTS + .iter() + .copied() + .chain([Overridable::QueryMemoryLimit]), + ) +} + +fn load(db: &Minigraf) { + let facts: String = (0..40) + .map(|i| format!("[:p{i} :v {}] [:p{i} :w {i}]", i % 5)) + .collect(); + db.execute(&format!("(transact [{facts}])")) + .expect("transact"); + db.execute("(transact [[:a :edge :b] [:b :edge :c] [:c :edge :d] [:d :edge :e]])") + .expect("edges"); + for rule in RULES { + db.execute(rule).expect("rule"); + } +} + +fn setup(opts: OpenOptions) -> Minigraf { + let db = opts.open_memory().expect("open"); + load(&db); + db +} + +fn rows(r: QueryResult) -> usize { + match r { + QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("expected query results"), + } +} + +fn code(r: Result) -> &'static str { + r.err().expect("an error").code() +} + +fn with(query: &str, opt: &str) -> String { + let (head, _) = query.rsplit_once("])").expect("query vector"); + format!("{head} {opt}])") +} + +fn int(n: i64) -> BindValue { + BindValue::Val(Value::Integer(n)) +} + +// ─── :query-memory-limit ───────────────────────────────────────────────────── + +#[test] +fn memory_keyword_lowers_the_database_limit() { + let db = setup(with_memory_keyword()); + assert_eq!(rows(db.execute(GROUPED).expect("unlimited")), 5); + assert_eq!( + code(db.execute(&with(GROUPED, ":query-memory-limit 64"))), + "QRY-012" + ); +} + +#[test] +fn memory_keyword_raises_the_database_limit() { + let db = setup(with_memory_keyword().query_memory_limit(64)); + assert_eq!(code(db.execute(GROUPED)), "QRY-012"); + let q = with(GROUPED, ":query-memory-limit 100000000"); + assert_eq!(rows(db.execute(&q).expect("raised")), 5); + assert_eq!(db.query(&q).expect("cursor").count(), 5); +} + +#[test] +fn memory_keyword_zero_refuses_every_stateful_query() { + let db = setup(with_memory_keyword()); + // Uncheckpointed facts take provisional ids, which is state. + assert_eq!( + code(db.execute(&with(VALUES, ":query-memory-limit 0"))), + "QRY-012" + ); + assert_eq!( + code(db.execute(&with(GROUPED, ":query-memory-limit 0"))), + "QRY-012" + ); + assert_eq!( + code(db.execute(&with(REACH, ":query-memory-limit 0"))), + "QRY-012" + ); +} + +#[test] +fn memory_keyword_applies_in_a_write_transaction() { + let db = setup(with_memory_keyword()); + let mut tx = db.begin_write().expect("begin"); + assert_eq!( + code(tx.execute(&with(GROUPED, ":query-memory-limit 64"))), + "QRY-012" + ); + tx.rollback(); +} + +#[test] +fn memory_keyword_is_refused_by_default() { + let db = setup(OpenOptions::new()); + let q = with(VALUES, ":query-memory-limit 1000000"); + let refused = |e: MinigrafError| { + assert_eq!(e.code(), "API-025"); + assert!( + e.to_string().contains(":query-memory-limit"), + "names the keyword" + ); + assert!( + e.to_string().contains("QueryMemoryLimit"), + "names the variant" + ); + }; + refused(db.execute(&q).err().expect("execute")); + refused(db.query(&q).err().expect("query")); + refused(db.prepare(&q).err().expect("prepare")); + refused( + db.prepare(&with(VALUES, ":query-memory-limit $m")) + .err() + .expect("slot"), + ); + let mut tx = db.begin_write().expect("begin"); + refused(tx.execute(&q).err().expect("tx")); + tx.rollback(); +} + +#[test] +fn memory_keyword_alone_in_the_list_refuses_the_others() { + let db = setup(OpenOptions::new().allow_overrides([Overridable::QueryMemoryLimit])); + assert_eq!( + rows( + db.execute(&with(VALUES, ":query-memory-limit 1000000")) + .expect("allowed") + ), + 24 + ); + assert_eq!( + code(db.execute(&with(REACH, ":max-derived-facts 100"))), + "API-025" + ); +} + +#[test] +fn memory_keyword_validation() { + let db = setup(with_memory_keyword()); + for (opt, want) in [ + (":query-memory-limit 1 :query-memory-limit 1", "INT-012"), + (":query-memory-limit", "INT-013"), + (":query-memory-limit -1", "INT-015"), + (":query-memory-limit \"x\"", "INT-015"), + (":query-memory-limit 1.5", "INT-015"), + ] { + assert_eq!(code(db.execute(&with(VALUES, opt))), want, "{opt}"); + } +} + +#[test] +fn memory_keyword_on_a_file_database() { + let dir = tempfile::tempdir().expect("tempdir"); + let path = dir.path().join("k.graph"); + let db = with_memory_keyword().path(&path).open().expect("open"); + load(&db); + db.checkpoint().expect("checkpoint"); + // Checkpointed facts need no ids unless a row returns an entity. + assert_eq!( + rows( + db.execute(&with(VALUES, ":query-memory-limit 0")) + .expect("stateless") + ), + 24 + ); + let zero = db + .prepare(VALUES) + .expect("prepare") + .with_query_memory_limit(0); + assert_eq!(rows(zero.execute(&[]).expect("setter 0")), 24); + let entities = "(query [:find ?e :where [?e :v ?x] [(> ?x 1)] :query-memory-limit 0])"; + assert_eq!(code(db.execute(entities)), "QRY-012"); + assert_eq!( + code(db.execute(&with(GROUPED, ":query-memory-limit 0"))), + "QRY-012" + ); + assert_eq!( + code(db.execute(&with(GROUPED, ":query-memory-limit 64"))), + "QRY-012" + ); +} + +// ─── Bind slots ────────────────────────────────────────────────────────────── + +#[test] +fn derived_facts_slot_changes_per_execution() { + let db = setup(OpenOptions::new()); + for kw in [":max-derived-facts", ":max-results"] { + let pq = db + .prepare(&with(REACH, &format!("{kw} $n"))) + .expect("prepare"); + assert_eq!(code(pq.execute(&[("n", int(1))])), "INT-020", "{kw} 1"); + assert_eq!( + rows(pq.execute(&[("n", int(1000))]).expect("1000")), + 10, + "{kw} 1000" + ); + assert_eq!(pq.query(&[("n", int(1000))]).expect("cursor").count(), 10); + } +} + +#[test] +fn memory_slot_changes_per_execution() { + let db = setup(with_memory_keyword()); + let pq = db + .prepare(&with(GROUPED, ":query-memory-limit $m")) + .expect("prepare"); + assert_eq!(code(pq.execute(&[("m", int(0))])), "QRY-012"); + assert_eq!(rows(pq.execute(&[("m", int(i64::MAX))]).expect("max")), 5); +} + +#[test] +fn limit_slot_errors() { + let db = setup(with_memory_keyword()); + let derived = db + .prepare(&with(REACH, ":max-derived-facts $n")) + .expect("prepare"); + let memory = db + .prepare(&with(GROUPED, ":query-memory-limit $m")) + .expect("prepare"); + let string = BindValue::Val(Value::String("x".into())); + assert_eq!(code(derived.execute(&[("n", string.clone())])), "API-024"); + assert_eq!( + code(derived.execute(&[("n", BindValue::TxCount(5))])), + "API-024" + ); + assert_eq!(code(derived.execute(&[])), "API-022"); + assert_eq!(code(derived.execute(&[("n", int(0))])), "INT-014"); + assert_eq!(code(memory.execute(&[("m", string)])), "API-024"); + assert_eq!(code(memory.execute(&[("m", int(-1))])), "INT-015"); + assert_eq!(code(memory.execute(&[])), "API-022"); + let results = db + .prepare(&with(REACH, ":max-results $n")) + .expect("prepare"); + assert_eq!(code(results.execute(&[("n", int(-3))])), "INT-014"); +} + +#[test] +fn unbound_limit_slots_are_refused_by_execute() { + let db = setup(with_memory_keyword()); + for opt in [ + ":max-derived-facts $n", + ":max-results $n", + ":query-memory-limit $n", + ] { + let q = with(REACH, opt); + assert_eq!(code(db.execute(&q)), "API-010", "{opt}"); + assert_eq!( + db.query(&q).err().expect("query").code(), + "API-010", + "{opt}" + ); + } +} + +#[test] +fn empty_list_refuses_slots_at_prepare() { + let db = setup(OpenOptions::new().allow_overrides([])); + for opt in [":max-derived-facts $n", ":max-results $n"] { + let err = db.prepare(&with(REACH, opt)).err().expect("refused"); + assert_eq!(err.code(), "API-025", "{opt}"); + } +} + +// ─── Setters ───────────────────────────────────────────────────────────────── + +#[test] +fn derived_facts_setter_replaces_the_database_value() { + let db = setup(OpenOptions::new()); + let low = db + .prepare(REACH) + .expect("prepare") + .with_max_derived_facts(1); + assert_eq!(code(low.execute(&[])), "INT-020"); + assert_eq!(low.query(&[]).err().expect("cursor").code(), "INT-020"); + + let db = setup(OpenOptions::new().max_derived_facts(1)); + assert_eq!(code(db.execute(REACH)), "INT-020"); + let high = db + .prepare(REACH) + .expect("prepare") + .with_max_derived_facts(1000); + assert_eq!(rows(high.execute(&[]).expect("raised")), 10); +} + +#[test] +fn keyword_overrides_the_setter() { + let db = setup(OpenOptions::new()); + let pq = db + .prepare(&with(REACH, ":max-derived-facts 1000")) + .expect("prepare") + .with_max_derived_facts(1); + assert_eq!(rows(pq.execute(&[]).expect("keyword wins")), 10); + + let db = setup(with_memory_keyword()); + let pq = db + .prepare(&with(GROUPED, ":query-memory-limit $m")) + .expect("prepare") + .with_query_memory_limit(usize::MAX); + assert_eq!(code(pq.execute(&[("m", int(64))])), "QRY-012"); +} + +#[test] +fn memory_setter_replaces_the_database_value() { + let db = setup(OpenOptions::new()); + let low = db + .prepare(GROUPED) + .expect("prepare") + .with_query_memory_limit(64); + assert_eq!(code(low.execute(&[])), "QRY-012"); + + let db = setup(OpenOptions::new().query_memory_limit(64)); + let high = db + .prepare(GROUPED) + .expect("prepare") + .with_query_memory_limit(usize::MAX); + assert_eq!(rows(high.execute(&[]).expect("raised")), 5); + assert_eq!(high.query(&[]).expect("cursor").count(), 5); +} + +#[test] +fn setters_are_not_gated() { + let db = setup(OpenOptions::new().allow_overrides([]).max_derived_facts(1)); + let pq = db + .prepare(REACH) + .expect("prepare") + .with_max_derived_facts(1000) + .with_query_memory_limit(usize::MAX); + assert_eq!(rows(pq.execute(&[]).expect("setters")), 10); +}