diff --git a/CHANGELOG.md b/CHANGELOG.md index 28dae4744e..09239aa9ea 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -53,6 +53,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Set values: `#{...}`** (#316, PR 1 of 3). A fact's value can be a finite set of scalars, `[:alice :user/scopes #{:scope/read :scope/write}]`, written in query text, returned as `Value::Set(ValueSet)`, transacted, retracted and queried by exact value (`[?e :user/scopes #{:scope/write :scope/read}]`), joined on and grouped by. Duplicates are removed and element order does not matter. Two elements are the same when `Value`'s order says so: `0.0` and `-0.0` are one element (`-0.0` is kept), every NaN is one element, a keyword never equals a ref and `1` never equals `1.0`. A set cannot hold a set (`ValueSet::new` fails with the new `API-021`; in query text, `PRS-119`); its elements are literals only (`PRS-120`), and an unclosed `#{` is `PRS-121`. In format v8 a set has value tag `0x08`, after refs; a set whose encoded elements take at most 64 bytes is stored in its index keys, a longer one once in a value page, as a long string is. On a file database a stored set may take up to 4,068 bytes, counting each keyword element as 6 bytes and each ref as 10 (`WAL-003`). The REPL prints sets as `#{...}` and `BrowserDb` returns them as JSON arrays, in `Value`'s order. - **Set-membership predicates** (#316, PR 2 of 3). `[(in? ?role #{:role/admin :role/owner})]` keeps rows whose value is in a set, and `not-in?`, `any-in?` (the two sets share an element), `all-in?` (every element of the first is in the second) and `none-in?` (they share none) complete the five. Each works as a filter or binds a Boolean, `[(any-in? ?scopes #{:scope/write}) ?can-write]`, and takes literal sets, set-valued attributes and bind slots (`BindValue::Val(Value::Set(..))`). Membership is set equality, as for set values: `0.0` is in `#{-0.0}`, NaN is in a set holding NaN, a keyword is not a ref. `in?` of an empty set is false and `not-in?` true; `all-in?` and `none-in?` of an empty first set are true and `any-in?` false. A set where a scalar is needed, or a scalar where a set is needed, is a type mismatch: the filter drops the row and the binding binds nothing, so `not-in?` with a non-set is never true. `contains?` stays string-only. The five names cannot be registered as functions. +- **`collect-set`** (#316, PR 3 of 3). `[(collect-set ?e :user/scope) ?scopes]` binds, per row, the set of the values of `[?e :user/scope ?v]` under the query's `:as-of` and `:valid-at`, with retractions applied as for that pattern, and `#{}` when there are none (the row is kept). Combine it with the set predicates: `[(collect-set ?e :user/scope) ?s] [(in? :scope/admin ?s)]`. `?e` must be bound by an earlier clause (`INT-018`); a keyword names its entity, and a value that is no entity gives `#{}`. It works in `:where`, rule bodies, `not-join` bodies and `or` branches; when its output variable is already bound, it keeps the rows where the two sets are equal. It reads stored facts only, never a rule's derived facts. New codes: `PRS-122` (no output variable), `PRS-123` (an operand that is not a `?variable` then an attribute keyword, a bind slot included) and `QRY-015` (a value found is itself a set: bind a set-valued attribute with a pattern). The set it builds counts toward `query_memory_limit` (`QRY-012`). `collect-set` is read only as a whole clause (`PRS-067` inside another expression) and cannot be registered as a function. - **Every query runs on a streaming engine** (#473: #544, #545, #546, #547, #548, #549, #551). The executor, which turned every live fact of each pattern's attribute into a `Fact` before matching, held each row's bindings in a map and copied the database into a `FactStorage` for every rule query, no longer runs queries: its query path, `PatternMatcher` and the old rule evaluators are gone (#551), and the release binary is 1,153 KiB instead of 1,286 KiB (CI's size check). A query is now a tree of operators that pass batches of up to 1,024 rows of ids, read from the index keys, and turn ids into values only for the rows they return (#530). A pattern reads the narrowest key range its constants allow (`[?e :a C]` reads the AVET range of `C`, #518); a later pattern is an `IndexNestedLoopJoin` when its entity is bound and a `HashJoin` otherwise, built on the side with the smaller estimate (with no shared variable, the smaller product, #575); per-fact pseudo-attributes read their source's metadata column (#594). `not` / `not-join` is an `AntiJoin` and `or` / `or-join` a `Union` and `Distinct`: a body or branch with the same rows for every outer row runs once into a hash table, any other runs per outer row from a one-row seed. Aggregates keep one entry per group (one set of accumulators when ungrouped), windows hold their rows, and rule queries derive each stratum's relations semi-naively, with the magic-set rewrite, then read them as patterns. `:as-of` with a time bounds the transaction counter when transaction times rise with it, and otherwise keeps the versions of transactions at or before the time. Cursors (`Minigraf::query`, `PreparedQuery::query`, `BrowserDb.query`) pull one batch at a time, and closing or dropping one stops the work; a cursor still answers from the database as it was when it opened. Every operator that keeps state counts it against `OpenOptions::query_memory_limit` (#549, below). Answers are the executor's, as a bag, except for the changes under Breaking changes: until #551 every query in the test suite was also run by the executor and the answers had to agree, and the answers of the suites that relied on that are recorded in `tests/answers/`. Measured with the #394 envelope at 1M facts, executor → engine, p50 and peak RSS (`docs/BENCHMARKS.md` has every shape at 100K, 1M and 10M): `[?e :name "…"]` 288 ms → 22 µs; an attribute scan of 166,666 rows drained with `next_batch(1000)` 58 → 7 MiB (458 → 7 MiB at 10M); `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs; an entity-bound `not` 760 → 27 ms; `[:find (count ?v) :where [?e ?a ?v]]` 3.01 s → 457 ms and 728 → 7 MiB (6.6 GiB → 7 MiB at 10M); an `or-join` of two hashed branches 1.44 s → 80 ms; `(boss :p ?b)` 43.9 s → 2.14 ms and 2.6 GiB → 4 MiB; the whole transitive closure of `:manager` 51.0 s → 3.21 s and 4.7 GiB → 318 MiB; `:as-of` with a time, a point query, 1.65 s → 0.8 ms and 435 → 4 MiB (17.2 s and 3.6 GiB → 0.9 ms and 5 MiB at 10M). - **Transactions of any size on a file database, in bounded memory** (#473, part 8: #550). `transact` and `retract` are read one fact at a time: the whole command is never tokenized, parsed or materialised at once, and a statement reports the same error code as before whatever its size. A transaction becomes *large* when its facts would pass the new `OpenOptions::transaction_chunk_facts` (default 65,536, kept between 1 and 1,000,000): `Minigraf::execute` of a larger statement, or the `WriteTransaction` statement that takes its staged facts past it. A large transaction holds at most one chunk of facts in memory. It writes them a chunk at a time into copy-on-write trees that become the next generation, and commits as a checkpoint: no WAL entry, and the uncheckpointed facts of earlier transactions go into the same checkpoint. What a large transaction stores is what a small one stores, with two differences you can see: its `tx_id` is the time it became large, not its commit time (a default `:valid-from` takes that time too), and errors from different chunks of one statement come in chunk order. In a large `WriteTransaction` a rejected statement still leaves the transaction usable and the earlier statements' facts as they were; a fact too large to store is rejected at its statement (`WAL-003`) rather than at `commit`; a handle that has failed is refused when the transaction becomes large (`STG-046`) rather than at `commit`; and inside the transaction `:as-of` its own transaction number sees every finished statement, since they share one number (staged statements of a small transaction each have their own until `commit`). A crash at any point before a large transaction's commit leaves the database as it was; the WAL file exists, header only, from before its first page write, so a new file reopens too. The first checkpoint after a WAL is found at open, or after a large transaction is rolled back, now writes a meta page before it deletes the WAL. Measured at 1M facts against v3 before this change (one `execute`, or a `WriteTransaction` of 10 statements): peak memory above the input text goes from 1.3–2.4 GiB to at most 55 MiB at the default (under 10 MiB at 16,384); with sequential entities it is faster (3.9 s from 9.1 s for short values), with random entities about as fast for short values (9.5 s from 11.4 s in one `execute`) and slower for long ones over 10 statements (34 s from 22 s; 16,384 takes up to twice as long as the default with random entities), and a transaction of several statements over random entities can leave the file up to 1.8× larger, since each statement keeps the pages its base references until it ends; later checkpoints reuse that space. - **Queries inside a `WriteTransaction` read through a snapshot** (#550). They no longer copy every committed and pending fact into a new list: they read the committed indexes and the pending facts, with the transaction's staged facts read with the pending ones (or, in a large transaction, its working trees), and run on the streaming engine where it plans them, counted by `query_memory_limit`. diff --git a/CLAUDE.md b/CLAUDE.md index a91954b808..be419b3807 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -147,7 +147,7 @@ cargo run < demos/demo_negation.txt - `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) - `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), `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`), `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), `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), `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), `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`; each entry charged by a per-entry estimate 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. +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`), `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), `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), `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), `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 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. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -215,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1775 tests** (1762 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1792 tests** (1779 passing, 13 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. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index a49dde7705..cc058e61ef 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -138,6 +138,8 @@ with no `CodedError` anywhere in its chain. | PRS-119 | Set literal inside a set literal | Parser | | PRS-120 | Set literal element is not a scalar literal | Parser | | PRS-121 | Unterminated set literal | Parser | +| PRS-122 | collect-set without a binding | Parser | +| PRS-123 | collect-set operand is not a variable and an attribute | Parser | | QRY-001 | Invalid entity | Query Execution | | QRY-002 | Attribute must be a keyword | Query Execution | | QRY-003 | Cannot transact a pseudo-attribute | Query Execution | @@ -151,6 +153,7 @@ with no `CodedError` anywhere in its chain. | QRY-011 | Unknown window function | Query Execution | | QRY-012 | Query memory limit exceeded | Query Execution | | QRY-013 | Rule head entity is not an entity | Query Execution | +| QRY-015 | collect-set found a set value | Query Execution | | STG-001 | Invalid header: too short | Storage | | STG-002 | Invalid magic number: not a .graph file | Storage | | STG-003 | Invalid v4/v5/v6 header too short (deprecated) | Storage | @@ -2194,6 +2197,40 @@ with `PRS-047`. --- +### PRS-122 collect-set without a binding + +**Error text**: `collect-set produces a value; bind it to a variable: [(collect-set ?e :attr) ?out]` + +**Cause**: A `collect-set` clause has no output variable. `collect-set` builds a set value and is not a filter. + +**Resolution**: +- Bind its result: `[(collect-set ?e :user/scope) ?scopes]`, then test it with `in?`, `any-in?` or another predicate. + +**Example**: +```datalog +(query [:find ?e :where [?e :user/name _] [(collect-set ?e :user/scope)]]) +``` + +--- + +### PRS-123 collect-set operand is not a variable and an attribute + +**Error text**: `collect-set takes a ?variable and an attribute keyword; got {}` + +**Cause**: The first operand of `collect-set` must be a logic variable bound to an entity by an earlier clause, and the second an attribute keyword written in the query. A constant entity, a string or a variable attribute, and a `$slot` in either position are rejected. The message names the operand given. + +**Resolution**: +- Bind the entity with a pattern first: `[?e :user/name "alice"] [(collect-set ?e :user/scope) ?s]`. +- Write the attribute as a keyword: `:user/scope`, not `"user/scope"` or `?a`. + +**Example**: +```datalog +(query [:find ?s :where [?e :user/name _] [(collect-set ?e "user/scope") ?s]]) +``` +*`"user/scope"` is a string, not a keyword* + +--- + ## QRY — Query Execution Errors Query execution errors occur after parsing succeeds, during pattern matching, @@ -2407,6 +2444,24 @@ db.execute("(query [:find ?g (count ?e) :where [?e :g ?g]])")?; --- +### QRY-015 collect-set found a set value + +**Error text**: `collect-set over {} found a set value; bind a set-valued attribute with a pattern instead` + +**Cause**: `collect-set` gathers the values of an attribute into a set, and a set cannot hold a set. One of the values it found for the attribute is itself a set. The query fails rather than skip or flatten that value. + +**Resolution**: +- Read a set-valued attribute with a pattern: `[?e :user/scopes ?scopes]` binds the stored set. +- Keep `collect-set` for attributes with one scalar value per fact. + +**Example**: +```datalog +(transact [[:alice :user/scopes #{:scope/read}]]) +(query [:find ?s :where [?e :user/scopes _] [(collect-set ?e :user/scopes) ?s]]) +``` + +--- + ## STG — Storage Errors Storage errors relate to reading or writing the `.graph` file. They typically diff --git a/docs/GRAMMAR.md b/docs/GRAMMAR.md index 5d4cdad599..7f56e27d33 100644 --- a/docs/GRAMMAR.md +++ b/docs/GRAMMAR.md @@ -91,7 +91,7 @@ where-section ::= kw-where where-clause+ where-clause ::= expr-clause | not-clause | not-join-clause | or-clause | or-join-clause | pattern-clause | rule-invocation pattern-clause ::= "[" edn-value edn-value edn-value "]" -expr-clause ::= "[" expr variable? "]" +expr-clause ::= "[" (collect-set variable | expr variable?) "]" not-clause ::= "(" "not" where-clause+ ")" not-join-clause ::= "(" "not-join" join-vars where-clause+ ")" or-clause ::= "(" "or" or-branch+ ")" @@ -102,16 +102,18 @@ and-branch ::= "(" "and" where-clause+ ")" rule-invocation ::= "(" (* not followed by reserved-head *) plain-sym edn-value* ")" (* ── EXPRESSIONS ── *) -expr ::= "(" expr-body ")" -expr-body ::= binary-form | unary-form -unary-form ::= (unary-op | op-sym | plain-sym) expr-arg -binary-form ::= binary-op expr-arg expr-arg -unary-op ::= "string?" | "integer?" | "float?" | "boolean?" | "nil?" (* token *) -binary-op ::= "<=" | ">=" | "!=" | "starts-with?" | "ends-with?" | "contains?" - | "matches?" | "not-in?" | "any-in?" | "all-in?" | "none-in?" | "in?" - | "<" | ">" | "=" | "+" | "-" | "*" | "/" (* token *) -expr-arg ::= expr | set-lit | boolean-lit | nil-lit | float-lit | integer-lit - | string-lit | bind-slot | keyword | variable +expr ::= "(" expr-body ")" +expr-body ::= binary-form | unary-form +unary-form ::= (* not followed by collect-set-head *) (unary-op | op-sym | plain-sym) expr-arg +binary-form ::= binary-op expr-arg expr-arg +collect-set ::= "(" collect-set-head variable keyword ")" +collect-set-head ::= "collect-set" (* not followed by word-cont *) (* token *) +unary-op ::= "string?" | "integer?" | "float?" | "boolean?" | "nil?" (* token *) +binary-op ::= "<=" | ">=" | "!=" | "starts-with?" | "ends-with?" | "contains?" + | "matches?" | "not-in?" | "any-in?" | "all-in?" | "none-in?" | "in?" + | "<" | ">" | "=" | "+" | "-" | "*" | "/" (* token *) +expr-arg ::= expr | set-lit | boolean-lit | nil-lit | float-lit | integer-lit + | string-lit | bind-slot | keyword | variable (* ── TEMPORAL / WITH SECTIONS ── *) as-of-section ::= kw-as-of (integer-lit | string-lit | bind-slot) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 40d080ad28..b88aed8a3e 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,762 | 1,780 | +| **Passing** | 1,779 | 1,797 | | **Ignored** | 13 | 14 | -| **Total** | 1,775 | 1,794 | +| **Total** | 1,792 | 1,811 | **Verified**: 2026-10-24 with `cargo test --quiet`. @@ -97,6 +97,7 @@ These tests compare the database against an independent answer rather than a sin - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests; #287, #371): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag). - **Set values** (`tests/set_values_test.rs`, 8 tests, 10 with `test-hooks`; #316): `#{...}` transacted, queried by exact value, joined on and grouped by, in memory, pending, committed, after WAL replay and reopen, in a large transaction, through the fact log and the log writer; exact retraction; the stored-size limit (`WAL-003`); literal errors (`PRS-119`–`121`); with `test-hooks`, the same answers with reordering on and off, and `#{0.0}` equal to `#{-0.0}` through a constant and a join, committed or pending. Unit tests cover `ValueSet` (dedup, `-0.0` kept, one NaN, `API-021`, `Ord`/`Hash`/`Eq` property test, serde), v8 set keys (inline and long, the 64-byte boundary, decoding, `set_bytes_bound`), long-set dedup and a set record under a string's hash, the pending encoding, `value_order`, parser errors and REPL/JSON output; the model-based test generates sets. - **Set predicates** (`tests/set_predicates_test.rs`, 12 tests; #316): `in?`/`not-in?` per scalar type (string, integer, float, boolean, nil, keyword, ref), `any-in?`/`all-in?`/`none-in?`, filter and binding forms agreeing, every empty-set case, `-0.0`/`0.0` and NaN (through bind slots) as one element, a keyword not a ref to its entity, each wrong operand shape (filter drops, binding binds nothing; `not-in?` with a non-set too), stored operands pending, committed and reopened, `=`/`!=` between sets, `contains?` still string-only, arity `PRS-065`, the names refused by `register_predicate`. `tests/prepared_statements_test.rs` binds sets to an operand slot and a value slot across executes; an `executor.rs` unit test covers `eval_binop`'s arms. +- **`collect-set`** (`tests/collect_set_test.rs`, 16 tests; #316): the values of an attribute; a missing attribute gives `#{}` and keeps the row; one element per value (two valid windows of one triple, `0.0`/`-0.0`); retractions; `:as-of` and `:valid-at`; pending, committed, mixed (a committed fact retracted while pending) and reopened; refs and long strings from a value page; a set-valued attribute `QRY-015`; an unbound or later-bound entity `INT-018`; keyword entities (one naming none) and non-entity cells; in a rule body, `not-join` and `not` bodies and an `or-join` branch; an already-bound output variable; `QRY-012` from the `CollectSet` holder under a small `query_memory_limit`; set predicates and a prepared `any-in?` slot over the result; parse errors (`PRS-065`, `PRS-067` nested, `PRS-068`, `PRS-069`, `PRS-122`, `PRS-123` incl. bind slots); the name refused by `register_predicate`. A `parser.rs` unit test checks the AST; `tests/plan_independence_test.rs` adds seven `collect-set` queries to its matrix. - **B+tree cursor** (v8 storage format PR 1, #374): every scan walks the tree, not the leaf `next_leaf` chain. - Full scans and start positions match the input. - `seek` from the current position lands where a fresh descent from the root would: randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op. diff --git a/docs/superpowers/plans/2026-10-24-316-set-values.md b/docs/superpowers/plans/2026-10-24-316-set-values.md index 6e9b69cb0a..58dcfc3833 100644 --- a/docs/superpowers/plans/2026-10-24-316-set-values.md +++ b/docs/superpowers/plans/2026-10-24-316-set-values.md @@ -246,17 +246,76 @@ executed with two different sets. `docs/TEST_COVERAGE.md` counts. - Review as step 12; PR into `v3` without a closing keyword. -## PR 3 — `collect-set` (outline) - -17. Parse in the expression-clause arm (`parser.rs` `[(..) ?out]`): `PRS-121`, `PRS-122`; - `WhereClause::CollectSet { entity, attr, out }` (a clause, not an `Expr`), counted by - `check_expr_safety` (`parser.rs:1809`, `INT-018`), magic sets and stratification as an - expression clause. -18. `engine/filter.rs` `Step::CollectSet` and planning in `plan.rs` beside `Bind`: per-row EAVT probe - (the `IndexNestedLoopJoin` probe), `keyword_eid` for an `Iid` entity, metered set, `QRY-014`. -19. Tests: the spec §12 `collect-set` list, in rule bodies, `not` bodies and `or` branches, with - reordering on and off (`plan_independence_test.rs`). -20. Docs share; review and PR; close #316 by hand. +## PR 3 — `collect-set` + +Codes: #306 holds `PRS-115`–`118` and #180 holds `QRY-014` (its branch, not yet on `v3`), so the +spec's `PRS-121` (no binding) is **`PRS-122`**, its `PRS-122` (bad operand) is **`PRS-123`** and its +`QRY-014` (set value collected) is **`QRY-015`**. Whichever of these PRs lands second rebases and +keeps its numbers; gaps are allowed (`PRS-114` is followed by `PRS-119` today). + +**Deviation from the outline: `collect-set` is an `Expr`, not a `WhereClause`.** It is +`Expr::CollectSet { entity, attribute }`, which the parser builds only as the whole expression of a +binding clause `[(collect-set ?e :a) ?s]`. The spec (§7.1) asks that it be checked, ordered, rewritten +and stratified as an expression clause, which is what `WhereClause::Expr` already is everywhere: +`check_expr_safety` (`INT-018` for an unbound `?e`), `optimizer::plan` (placed once `?e` is bound, +`Binders::expression` for an already-bound `?s`), magic sets and stratification (no edge), prepared +slots (none). A new clause would repeat each of these. The engine plans it as its own operator. + +### Step 17. Parser + +- `types.rs`: `Expr::CollectSet { entity: String, attribute: String }`, documented as clause-level + only. Each exhaustive `Expr` match gets a real arm: `parser.rs` `expr_vars` and + `optimizer::expr_vars` (`[entity]`), `prepared.rs` `collect_slots_from_expr`/`substitute_expr` + (nothing), `plan.rs` `expr_vars` (the entity's slot), `executor.rs` `eval_expr` (`Err(())`: + never evaluated as an expression). +- `parser.rs` `parse_expr_clause`: a list whose head is the symbol `collect-set` is read here, before + `parse_expr`: three elements else `PRS-065`; `?var` then a keyword literal else `PRS-123` (naming + the operand given, a `$slot` included); then the binding: none is `PRS-122`, others as today + (`PRS-069`, `PRS-068`). `parse_expr` refuses `collect-set` at any arity with `PRS-067`, so a nested + one (`(in? 1 (collect-set ?e :a))`) and a one-operand `[(collect-set ?e) ?s]` never become a UDF. +- `functions.rs`: `collect-set` joins the sentinels, so `register_predicate("collect-set")` is refused. +- `error.rs` + `docs/ERROR_REFERENCE.md`: `PRS-122`, `PRS-123`, `QRY-015` (all three registries, + table and sections). +- `grammar.pest`: `expr_clause = { "[" ~ (collect_set ~ variable | expr ~ variable?) ~ "]" }`, + `collect_set = { "(" ~ "collect-set" ~ variable ~ keyword ~ ")" }`, and `unary_form`'s head refuses + `collect-set`, so pest and the parser agree on every form above; `docs/GRAMMAR.md` regenerated; + `tests/grammar/valid/query_collect_set.edn`, `tests/grammar/invalid/syntax/collect_set_*.edn` (no + binding, nested, string attribute). `TOKENS` unchanged. + +### Step 18. Engine + +- `plan.rs` `Builder::clause`, `WhereClause::Expr` arm: `Expr::CollectSet` becomes + `Step::CollectSet(CollectSpec { entity: usize, inner: ScanSpec, out: usize, mode: Out })`, the + output slot and mode chosen as for `Bind`. `inner` is `[?e :a ?v]` with `e = Bind(0)`, + `a = Const(attr)`, `v = Bind(1)`, the query's `valid`, `derived: None` (stored facts only, spec §7.1). + An entity variable bound by no earlier clause cannot reach the planner (`INT-018`); a missing slot + is `invariant`. +- `engine/collect.rs` (new; `filter.rs`'s `Apply` holds no state, and this one holds a `Scan`): + `CollectSet` operator. Per input row: `JoinKey::of(cell, true)` (an `Iid` through `keyword_eid`); + an `Eid` is probed (`Scan::probe(uuid, dict_eid)`, the `IndexNestedLoopJoin` probe), its value + column read into a `Vec` (`project::value`), each value charged to a `Held` before it is kept + (`value_bytes` + `HASH_ENTRY_OVERHEAD`, `QRY-012`), a set value is `QRY-015`; any other cell gives + `#{}`. `ValueSet::new` deduplicates; the cell is `Cell::Val(Scalar::Set(Arc))`; the charge is + released once the row's cell is made. Output as `Bind`: `Out::New` sets the slot, `Check`/`Replace` + keep rows that are `join_eq` (#596). `rewind`/`close` pass to the child and the scan. `mod.rs` + `build` maps the step to it. + +### Step 19. Tests + +- Unit (`parser.rs`): each code above, `collect-set` nested and one-operand, `register_predicate`. +- `tests/collect_set_test.rs` (file-backed parts behind `#![cfg(not(target_arch = "wasm32"))]`): the + spec §12 list — missing attribute gives `#{}` and keeps the row; dedup; retractions; `:as-of` and + `:valid-at`; pending, committed (after `checkpoint`) and mixed; a set-valued attribute `QRY-015`; + unbound entity `INT-018`; keyword entity (`:alice`) and a non-entity cell (`#{}`); in a rule body, a + `not` body and an `or` branch; out variable already bound (equal keeps, unequal drops); `QRY-012` + under a small `query_memory_limit`; with `in?`/`any-in?` over the result (the PR 2 deferral); a + prepared query with an `in?` slot over it. +- `plan_independence_test.rs`: one `collect-set` query with reordering on and off. + +### Step 20. Docs, review, PR + +`CHANGELOG.md` (beside PR 1–2), README, `CLAUDE.md` (module notes, counts) and `docs/TEST_COVERAGE.md`. +Codex review, then PR into `v3` with no closing keyword; after merge close #316 by hand. ## PR 4 — docs site and bindings diff --git a/src/error.rs b/src/error.rs index 6ce57d4343..9f131f2e86 100644 --- a/src/error.rs +++ b/src/error.rs @@ -164,6 +164,8 @@ pub(crate) enum ErrorCode { Prs119, Prs120, Prs121, + Prs122, + Prs123, Qry001, Qry002, Qry003, @@ -177,6 +179,7 @@ pub(crate) enum ErrorCode { Qry011, Qry012, Qry013, + Qry015, Int000, Stg001, Stg002, @@ -1036,6 +1039,18 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Unterminated set: missing '}'", ErrorCategory::Parser, ), + ( + ErrorCode::Prs122, + "PRS-122", + "collect-set produces a value; bind it to a variable: [(collect-set ?e :attr) ?out]", + ErrorCategory::Parser, + ), + ( + ErrorCode::Prs123, + "PRS-123", + "collect-set takes a ?variable and an attribute keyword; got {}", + ErrorCategory::Parser, + ), ( ErrorCode::Qry001, "QRY-001", @@ -1114,6 +1129,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "rule head entity is not an entity: rule '{}' gives a {} where a ref or a keyword is needed", ErrorCategory::Query, ), + ( + ErrorCode::Qry015, + "QRY-015", + "collect-set over {} found a set value; bind a set-valued attribute with a pattern instead", + ErrorCategory::Query, + ), ( ErrorCode::Int000, "INT-000", @@ -2328,6 +2349,8 @@ mod tests { | ErrorCode::Prs119 | ErrorCode::Prs120 | ErrorCode::Prs121 + | ErrorCode::Prs122 + | ErrorCode::Prs123 | ErrorCode::Qry001 | ErrorCode::Qry002 | ErrorCode::Qry003 @@ -2341,6 +2364,7 @@ mod tests { | ErrorCode::Qry011 | ErrorCode::Qry012 | ErrorCode::Qry013 + | ErrorCode::Qry015 | ErrorCode::Stg001 | ErrorCode::Stg002 | ErrorCode::Stg003 @@ -2597,6 +2621,8 @@ mod tests { ErrorCode::Prs119, ErrorCode::Prs120, ErrorCode::Prs121, + ErrorCode::Prs122, + ErrorCode::Prs123, ErrorCode::Qry001, ErrorCode::Qry002, ErrorCode::Qry003, @@ -2610,6 +2636,7 @@ mod tests { ErrorCode::Qry011, ErrorCode::Qry012, ErrorCode::Qry013, + ErrorCode::Qry015, ErrorCode::Stg001, ErrorCode::Stg002, ErrorCode::Stg003, diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index ebcb60c0ff..7b29ebcc77 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -842,6 +842,8 @@ pub(crate) fn eval_expr( // Unsubstituted bind slot — treat as eval error (unbound variable equivalent). Err(()) } + // The planner runs it as a step of its own (#316). + Expr::CollectSet { .. } => Err(()), } } diff --git a/src/query/datalog/functions.rs b/src/query/datalog/functions.rs index 840312cbb9..22d5371e8d 100644 --- a/src/query/datalog/functions.rs +++ b/src/query/datalog/functions.rs @@ -99,6 +99,7 @@ impl FunctionRegistry { "any-in?", "all-in?", "none-in?", + "collect-set", ] { reg.predicates.insert( name.to_string(), diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index ba5d81acf9..59de58c729 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -186,6 +186,7 @@ pub(crate) fn expr_vars(expr: &Expr) -> Vec { vars } Expr::UnaryOp(_, inner) => expr_vars(inner), + Expr::CollectSet { entity, .. } => vec![entity.clone()], } } diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index fd5d7759de..1065968c09 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -1400,6 +1400,9 @@ fn parse_expr(list: &[EdnValue]) -> Result { Ok(Expr::BinOp(op, Box::new(lhs), Box::new(rhs))) } + // Read only as the whole expression of a clause (`parse_expr_clause`). + "collect-set" => bail_coded!(ErrorCode::Prs067, head), + other => { // Unknown name in 1-arg position: treat as UDF predicate resolved at runtime. // 2-arg unknown forms are still rejected. @@ -1435,8 +1438,14 @@ fn parse_expr_clause(vec: &[EdnValue]) -> Result { "parse_expr_clause called with non-list element 0" ), }; - let expr = parse_expr(inner_list)?; + let collect = matches!(inner_list.first(), Some(EdnValue::Symbol(s)) if s == "collect-set"); + let expr = if collect { + parse_collect_set(inner_list)? + } else { + parse_expr(inner_list)? + }; let binding = match vec.len() { + 1 if collect => bail_coded!(ErrorCode::Prs122), 1 => None, 2 => { let second = vec @@ -1457,6 +1466,41 @@ fn parse_expr_clause(vec: &[EdnValue]) -> Result { Ok(WhereClause::Expr { expr, binding }) } +/// `(collect-set ?e :attr)` (#316): a variable, then an attribute keyword. +fn parse_collect_set(list: &[EdnValue]) -> Result { + let [_, entity, attribute] = list else { + bail_coded!(ErrorCode::Prs065, "collect-set"); + }; + let entity = match entity { + EdnValue::Symbol(v) if v.starts_with('?') => v.clone(), + other => bail_coded!(ErrorCode::Prs123, operand(other)), + }; + let attribute = match attribute { + EdnValue::Keyword(k) => k.clone(), + other => bail_coded!(ErrorCode::Prs123, operand(other)), + }; + Ok(Expr::CollectSet { entity, attribute }) +} + +/// How a `collect-set` operand that is neither reads in an error. +fn operand(edn: &EdnValue) -> String { + match edn { + EdnValue::Symbol(s) => format!("the symbol {s}"), + EdnValue::Keyword(k) => format!("the keyword {k}"), + EdnValue::String(s) => format!("the string {s:?}"), + EdnValue::BindSlot(n) => format!("the bind slot ${n}"), + EdnValue::Integer(n) => format!("the integer {n}"), + EdnValue::Float(f) => format!("the float {f}"), + EdnValue::Boolean(b) => format!("the boolean {b}"), + EdnValue::Nil => "nil".to_string(), + EdnValue::Uuid(_) => "a UUID".to_string(), + EdnValue::Set(_) => "a set".to_string(), + EdnValue::List(_) => "a list".to_string(), + EdnValue::Vector(_) => "a vector".to_string(), + EdnValue::Map(_) => "a map".to_string(), + } +} + /// Parse a list item (EDN List) appearing in a :where clause or rule body. /// Returns Err if the list is empty, has an unknown form, or contains nested `not`. /// Whether `s` can name a rule: a symbol that is neither a variable nor an operator @@ -1849,6 +1893,7 @@ fn expr_vars(expr: &Expr) -> Vec { } Expr::UnaryOp(_, arg) => expr_vars(arg), Expr::Slot(_) => vec![], + Expr::CollectSet { entity, .. } => vec![entity.clone()], } } @@ -3618,6 +3663,33 @@ mod tests { } } + #[test] + fn test_parse_collect_set() { + let input = "(query [:find ?s :where [?e :x _] [(collect-set ?e :user/scope) ?s]])"; + match parse(input).expect("collect-set parses") { + DatalogCommand::Query(q) => match &q.where_clauses[1] { + WhereClause::Expr { + expr: Expr::CollectSet { entity, attribute }, + binding: Some(out), + } => { + assert_eq!(entity, "?e"); + assert_eq!(attribute, ":user/scope"); + assert_eq!(out, "?s"); + } + _ => panic!("expected a collect-set binding clause"), + }, + _ => panic!("expected query"), + } + let code = |clause: &str| { + let input = format!("(query [:find ?e :where [?e :x _] {clause}])"); + crate::MinigrafError::from(parse(&input).expect_err("rejected")).code() + }; + assert_eq!(code("[(collect-set ?e :a)]"), "PRS-122"); + assert_eq!(code("[(collect-set ?e ?a) ?s]"), "PRS-123"); + assert_eq!(code("[(collect-set ?e) ?s]"), "PRS-065"); + assert_eq!(code("[(any-in? #{1} (collect-set ?e :a)) ?s]"), "PRS-067"); + } + #[test] fn test_parse_expr_nested_arithmetic() { // [(+ (* ?a 2) ?b) ?result] diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index 39ae561b5e..7a2cf1d009 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -306,7 +306,7 @@ fn collect_slots_from_expr(expr: &Expr, names: &mut HashSet) { collect_slots_from_expr(r, names); } Expr::UnaryOp(_, arg) => collect_slots_from_expr(arg, names), - Expr::Var(_) | Expr::Lit(_) => {} + Expr::Var(_) | Expr::Lit(_) | Expr::CollectSet { .. } => {} } } @@ -405,7 +405,7 @@ fn substitute_expr(expr: &mut Expr, bindings: &HashMap<&str, &BindValue>) -> Res substitute_expr(rhs, bindings) } Expr::UnaryOp(_, arg) => substitute_expr(arg, bindings), - Expr::Var(_) | Expr::Lit(_) => Ok(()), + Expr::Var(_) | Expr::Lit(_) | Expr::CollectSet { .. } => Ok(()), } } diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 53e0b1292e..2a1d2f24eb 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -240,6 +240,13 @@ pub enum Expr { Slot(String), BinOp(BinOp, Box, Box), UnaryOp(UnaryOp, Box), + /// `(collect-set ?e :attr)` (#316): the set of the values of `[?e :attr ?v]`. + /// Only the whole expression of a binding clause `[(collect-set ?e :a) ?s]`; + /// the engine plans it as its own step, never through `eval_expr`. + CollectSet { + entity: String, + attribute: String, + }, } /// A single element in the :find clause: either a plain variable, an aggregate, or a window function. diff --git a/src/query/engine/collect.rs b/src/query/engine/collect.rs new file mode 100644 index 0000000000..486cb0fe8c --- /dev/null +++ b/src/query/engine/collect.rs @@ -0,0 +1,130 @@ +//! `CollectSet` (#316 spec §7.3): `[(collect-set ?e :a) ?s]`, per row the +//! set of the values of `[e :a ?v]` under the query's view. +//! +//! The values come from a one-entity probe of the pattern's `Scan`, the +//! probe an `IndexNestedLoopJoin` makes for a bound entity. A cell that is +//! no entity, or a keyword naming none, gives `#{}`; the row is kept. + +use super::batch::Batch; +use super::cell::{Cell, JoinKey, Scalar, join_eq}; +use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, growth, value_bytes}; +use super::plan::{CollectSpec, Out}; +use super::project::value; +use super::scan::Scan; +use super::{Counters, Ctx, Operator}; +use crate::error::{ErrorCode, bail_coded}; +use crate::graph::types::{Value, ValueSet}; +use anyhow::Result; +use std::mem::size_of; +use std::sync::Arc; + +pub(crate) struct CollectSet { + child: Box, + inner: Scan, + entity: usize, + attribute: String, + out: usize, + mode: Out, + /// The values of the set being built (#549). + held: Held, + counters: Counters, +} + +impl CollectSet { + pub(crate) fn new(child: Box, spec: CollectSpec, meter: &Arc) -> Self { + CollectSet { + child, + inner: Scan::new(spec.inner), + entity: spec.entity, + attribute: spec.attribute, + out: spec.out, + mode: spec.mode, + held: Held::new(meter, "CollectSet"), + counters: Counters::new("CollectSet"), + } + } + + /// The set of row `i`'s entity. + fn set(&mut self, batch: &Batch, i: usize, ctx: &mut Ctx<'_>) -> Result { + let mut values: Vec = Vec::new(); + let cell = batch.cols.get(self.entity).and_then(|c| c.get(i)); + let entity = match cell { + Some(cell) => JoinKey::of(cell, true, ctx)?, + None => None, + }; + if let Some(JoinKey::Eid(e)) = entity { + let uuid = ctx.ids.uuid(ctx.keys, e)?; + self.inner.probe(uuid, ctx.ids.dict_eid(e)); + while let Some(found) = self.inner.next_batch(ctx)? { + for v in found.cols.get(1).into_iter().flatten() { + let v = value(v, ctx)?; + if let Value::Set(_) = v { + bail_coded!(ErrorCode::Qry015, &self.attribute); + } + let n = value_bytes(&v) + HASH_ENTRY_OVERHEAD; + self.held.charge(n)?; + let refused = growth(values.capacity(), size_of::()); + self.held.reserve(values.try_reserve(1), n, refused)?; + values.push(v); + } + } + } + let set = ValueSet::new(values)?; + self.held.release(); + Ok(Cell::Val(Scalar::Set(Arc::new(set)))) + } +} + +impl Operator for CollectSet { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { + while let Some(mut batch) = self.child.next_batch(ctx)? { + self.counters.rows_in += batch.len as u64; + let mut keep = Vec::with_capacity(batch.len); + let mut out = Vec::with_capacity(batch.len); + for i in 0..batch.len { + let cell = self.set(&batch, i, ctx)?; + let old = match self.mode { + Out::New => None, + Out::Check | Out::Replace => batch.cols.get(self.out).and_then(|c| c.get(i)), + }; + // As `Bind` (#596). + match old { + Some(old) if !join_eq(old, &cell, true, ctx)? => keep.push(false), + Some(old) if self.mode == Out::Check => { + out.push(old.clone()); + keep.push(true); + } + _ => { + out.push(cell); + keep.push(true); + } + } + } + batch.retain(&keep); + batch.set_col(self.out, out); + if batch.len > 0 { + self.counters.out(&batch); + return Ok(Some(batch)); + } + } + Ok(None) + } + + fn rewind(&mut self, seed: &[Cell]) { + self.held.release(); + self.child.rewind(seed); + self.inner.rewind(&[]); + } + + fn close(&mut self) { + self.held.release(); + self.child.close(); + self.inner.close(); + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + self.inner.counters(out); + self.child.counters(out); + } +} diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 2b27dd5bc4..871a88b5fb 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -28,6 +28,7 @@ impl Apply { Step::Filter(..) => "Filter", Step::Bind(..) => "Bind", Step::Join(_) => "Join", + Step::CollectSet(_) => "CollectSet", Step::Anti(_) => "AntiJoin", Step::Union(_) => "Union", Step::Distinct(_) => "Distinct", @@ -131,8 +132,9 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { batch.set_col(*slot, out); } // Joins are operators of their own (`join::Join`, `anti::AntiJoin`, - // `union::Union`, `distinct::Distinct`). + // `union::Union`, `distinct::Distinct`, `collect::CollectSet`). Step::Join(_) + | Step::CollectSet(_) | Step::Anti(_) | Step::Union(_) | Step::Distinct(_) diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index 9709faf746..654ea3b288 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -7,6 +7,7 @@ mod aggregate; mod anti; mod batch; mod cell; +mod collect; mod distinct; mod filter; mod ids; @@ -306,6 +307,7 @@ pub(crate) fn build( for step in steps { root = match step { plan::Step::Join(spec) => Box::new(join::Join::new(root, spec, meter)), + plan::Step::CollectSet(spec) => Box::new(collect::CollectSet::new(root, spec, meter)), plan::Step::Anti(body) => Box::new(anti::AntiJoin::new(root, body, meter)), plan::Step::Union(branches) => Box::new(union::Union::new(root, branches, meter)), plan::Step::Distinct(slots) => Box::new(distinct::Distinct::new(root, slots, meter)), diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 8de251b4b0..d03200e2a5 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -154,6 +154,8 @@ pub(crate) enum Step { Bind(Expr, Vars, usize, Out), /// A later pattern, joined with the rows so far. Join(JoinSpec), + /// `[(collect-set ?e :a) ?s]` (#316 spec §7.3). + CollectSet(CollectSpec), /// `not` / `not-join`: keeps the rows for which the body has no row /// (#546). Anti(Body), @@ -263,6 +265,17 @@ pub(crate) enum JoinKind { Hash { build_inner: bool }, } +/// `[(collect-set ?e :a) ?s]`: per row, the values `inner` (`[e :a ?v]`, +/// probed by the cell at `entity`) finds, as one set bound to `out`. +#[derive(Debug, Clone)] +pub(crate) struct CollectSpec { + pub(crate) entity: usize, + pub(crate) attribute: String, + pub(crate) inner: ScanSpec, + pub(crate) out: usize, + pub(crate) mode: Out, +} + /// What a binding expression does with its slot (#596). #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub(crate) enum Out { @@ -1062,6 +1075,15 @@ impl Builder { let step = match binding { None => Step::Filter(expr, vars), Some(out) => { + let collect = match &expr { + Expr::CollectSet { entity, attribute } => Some(( + self.slots.by_var.get(entity).copied().ok_or_else(|| { + invariant("a collect-set entity bound by no earlier clause") + })?, + attribute.clone(), + )), + _ => None, + }; let replace = match &mut self.binders { Some(b) => b.expression(&expr, &out), None => false, @@ -1080,7 +1102,26 @@ impl Builder { (s, Out::New) } }; - Step::Bind(expr, vars, slot, mode) + match collect { + // Stored facts only, never a rule's relation + // (spec §7.1). + Some((entity, attribute)) => Step::CollectSet(CollectSpec { + entity, + inner: ScanSpec { + e: Term::Bind(0), + a: Term::Const(attribute.clone()), + v: Term::Bind(1), + meta: Vec::new(), + valid, + width: 2, + derived: None, + }, + attribute, + out: slot, + mode, + }), + None => Step::Bind(expr, vars, slot, mode), + } } }; self.steps.push(step); @@ -1507,6 +1548,7 @@ fn expr_vars(expr: &Expr, slots: &Slots) -> Vars { walk(r, slots, out); } Expr::UnaryOp(_, inner) => walk(inner, slots, out), + Expr::CollectSet { entity, .. } => walk(&Expr::Var(entity.clone()), slots, out), } } let mut out = Vec::new(); diff --git a/tests/answers/plan_independence_test.txt b/tests/answers/plan_independence_test.txt index eada47733d..33bc6671f0 100644 --- a/tests/answers/plan_independence_test.txt +++ b/tests/answers/plan_independence_test.txt @@ -207,3 +207,17 @@ two_expressions_on_one_variable_must_agree 97668cd36406f4e7 2 dd65a3c4b543c03a unify_int_never_equals_float 41b785650872d332 1 74e06170401b952a unify_int_never_equals_float 4f08e88811923ed0 1 e120643accc89b65 unify_negative_zero_equals_zero 0395edf0b6b4bc67 1 a6c8dc255a9855d1 +matrix_in_memory 7a8019975ea55541 4 d89f1dbd50b33744 +matrix_in_memory ea16c93a6b929359 3 4cad25c4d4e5443f +matrix_in_memory df83ebfb6bdda705 2 b147cdaa5210f4cf +matrix_in_memory 4f83b907d6c8b1ef 3 a3c5f2126709f82a +matrix_in_memory ff6f6ebf1d29de8d 2 c0b053626c69da28 +matrix_in_memory 4ba34df30fd9c9f9 5 25899f36613700e7 +matrix_in_memory 7f38cadbc3b8b755 5 381ff91cce327d9c +matrix_file_backed_after_checkpoint 7a8019975ea55541 5 88b424ac37cafe92 +matrix_file_backed_after_checkpoint ea16c93a6b929359 4 dffbfc3a5bed853b +matrix_file_backed_after_checkpoint df83ebfb6bdda705 3 187cf54306323406 +matrix_file_backed_after_checkpoint 4f83b907d6c8b1ef 4 5e1bdf768140d943 +matrix_file_backed_after_checkpoint ff6f6ebf1d29de8d 2 c0b053626c69da28 +matrix_file_backed_after_checkpoint 4ba34df30fd9c9f9 10 8a0c14af21731c88 +matrix_file_backed_after_checkpoint 7f38cadbc3b8b755 6 cf1e6f6c35d8cffe diff --git a/tests/collect_set_test.rs b/tests/collect_set_test.rs new file mode 100644 index 0000000000..597b005017 --- /dev/null +++ b/tests/collect_set_test.rs @@ -0,0 +1,429 @@ +//! `collect-set` (#316 spec §7): `[(collect-set ?e :a) ?s]` binds the set of +//! the values of `[?e :a ?v]` under the query's view, `#{}` when there are +//! none. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{BindValue, Minigraf, OpenOptions, QueryResult, Value, ValueSet}; + +fn rows(db: &Minigraf, q: &str) -> Vec> { + match db.execute(q).unwrap() { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected query results"), + } +} + +fn set(values: Vec) -> Value { + Value::Set(ValueSet::new(values).unwrap()) +} + +fn kw(k: &str) -> Value { + Value::Keyword(k.to_string()) +} + +/// The set `q` binds for its one row. +fn one_set(db: &Minigraf, q: &str) -> Value { + let r = rows(db, q); + assert_eq!(r.len(), 1, "one row"); + r[0][0].clone() +} + +fn code(db: &Minigraf, q: &str) -> String { + db.execute(q).err().expect("an error").code().to_string() +} + +fn scopes() -> Minigraf { + let db = Minigraf::in_memory().unwrap(); + db.execute( + r#"(transact [[:alice :user/name "alice"] [:alice :user/scope :scope/read] + [:alice :user/scope :scope/write] [:bob :user/name "bob"]])"#, + ) + .unwrap(); + db +} + +#[test] +fn values_of_the_attribute() { + let db = scopes(); + let s = one_set( + &db, + r#"(query [:find ?s :where [?e :user/name "alice"] [(collect-set ?e :user/scope) ?s]])"#, + ); + assert!( + s == set(vec![kw(":scope/read"), kw(":scope/write")]), + "alice's scopes" + ); +} + +#[test] +fn missing_attribute_gives_empty_set_and_keeps_the_row() { + let db = scopes(); + let s = one_set( + &db, + r#"(query [:find ?s :where [?e :user/name "bob"] [(collect-set ?e :user/scope) ?s]])"#, + ); + assert!(s == set(vec![]), "bob has no scope"); + let r = rows( + &db, + "(query [:find ?n ?s :where [?e :user/name ?n] [(collect-set ?e :user/scope) ?s]])", + ); + assert_eq!(r.len(), 2, "both people are kept"); +} + +#[test] +fn one_element_per_value() { + let db = Minigraf::in_memory().unwrap(); + // The same triple in two valid windows, and values equal as set + // elements: `-0.0` and `0.0` are one, `1` and `1.0` two. + db.execute(r#"(transact {:valid-from "2020-01-01T00:00:00Z" :valid-to "2021-01-01T00:00:00Z"} [[:a :v 1]])"#) + .unwrap(); + db.execute(r#"(transact {:valid-from "2022-01-01T00:00:00Z" :valid-to "2023-01-01T00:00:00Z"} [[:a :v 1]])"#) + .unwrap(); + db.execute("(transact [[:a :name \"a\"] [:b :name \"b\"] [:b :v 0.0] [:b :v 1.0]])") + .unwrap(); + db.execute("(transact [[:b :v -0.0]])").unwrap(); + let a = one_set( + &db, + r#"(query [:find ?s :any-valid-time :where [?e :name "a"] [(collect-set ?e :v) ?s]])"#, + ); + assert!( + a == set(vec![Value::Integer(1)]), + "one element for two windows" + ); + let b = one_set( + &db, + r#"(query [:find ?s :where [?e :name "b"] [(collect-set ?e :v) ?s]])"#, + ); + match b { + Value::Set(s) => assert_eq!(s.len(), 2, "0.0 and -0.0 one element, 1.0 another"), + _ => panic!("a set"), + } +} + +#[test] +fn retractions_apply() { + let db = scopes(); + db.execute("(retract [[:alice :user/scope :scope/write]])") + .unwrap(); + let s = one_set( + &db, + r#"(query [:find ?s :where [?e :user/name "alice"] [(collect-set ?e :user/scope) ?s]])"#, + ); + assert!(s == set(vec![kw(":scope/read")]), "write was retracted"); +} + +#[test] +fn as_of_and_valid_at() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + r#"(transact {:valid-from "2019-01-01T00:00:00Z"} + [[:alice :user/name "alice"] [:alice :user/scope :scope/read] + [:alice :user/scope :scope/write]])"#, + ) + .unwrap(); + db.execute("(transact [[:alice :user/scope :scope/admin]])") + .unwrap(); + db.execute(r#"(transact {:valid-from "2020-01-01T00:00:00Z" :valid-to "2021-01-01T00:00:00Z"} [[:alice :user/scope :scope/old]])"#) + .unwrap(); + let q = |opts: &str| { + one_set( + &db, + &format!( + r#"(query [:find ?s {opts} :where [?e :user/name "alice"] [(collect-set ?e :user/scope) ?s]])"# + ), + ) + }; + assert!( + q(":as-of 1") == set(vec![kw(":scope/read"), kw(":scope/write")]), + "as of the first transaction" + ); + assert!( + q("") + == set(vec![ + kw(":scope/read"), + kw(":scope/write"), + kw(":scope/admin") + ]), + "now: the old scope is no longer valid" + ); + assert!( + q(r#":valid-at "2020-06-01T00:00:00Z""#) + == set(vec![ + kw(":scope/read"), + kw(":scope/write"), + kw(":scope/old") + ]), + "the old scope was valid in 2020, the admin scope not yet" + ); +} + +#[test] +fn pending_committed_and_mixed() { + let dir = tempfile::tempdir().unwrap(); + let file = dir.path().join("c.graph"); + let db = Minigraf::open(&file).unwrap(); + db.execute(r#"(transact [[:alice :user/name "alice"] [:alice :user/scope :scope/read]])"#) + .unwrap(); + let q = + r#"(query [:find ?s :where [?e :user/name "alice"] [(collect-set ?e :user/scope) ?s]])"#; + assert!(one_set(&db, q) == set(vec![kw(":scope/read")]), "pending"); + db.checkpoint().unwrap(); + assert!(one_set(&db, q) == set(vec![kw(":scope/read")]), "committed"); + db.execute("(transact [[:alice :user/scope :scope/write]])") + .unwrap(); + db.execute("(retract [[:alice :user/scope :scope/read]])") + .unwrap(); + assert!( + one_set(&db, q) == set(vec![kw(":scope/write")]), + "committed fact retracted while pending, pending fact added" + ); + db.checkpoint().unwrap(); + drop(db); + let db = Minigraf::open(&file).unwrap(); + assert!(one_set(&db, q) == set(vec![kw(":scope/write")]), "reopened"); +} + +#[test] +fn refs_and_long_strings_are_collected() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("r.graph")).unwrap(); + let long = "x".repeat(100); + db.execute(&format!( + r#"(transact [[:alice :name "alice"] [:bob :name "bob"] + [:alice :bio "{long}"] [:alice :bio "short"]])"# + )) + .unwrap(); + let bob = match &rows(&db, r#"(query [:find ?b :where [?b :name "bob"]])"#)[0][0] { + Value::Ref(u) => *u, + _ => panic!("an entity"), + }; + db.execute(&format!( + r#"(transact [[:alice :knows #uuid "{}"]])"#, + bob.as_hyphenated() + )) + .unwrap(); + db.checkpoint().unwrap(); + let q = |attr: &str| { + one_set( + &db, + &format!( + r#"(query [:find ?s :where [?e :name "alice"] [(collect-set ?e {attr}) ?s]])"# + ), + ) + }; + assert!(q(":knows") == set(vec![Value::Ref(bob)]), "a ref"); + assert!( + q(":bio") + == set(vec![ + Value::String(long.clone()), + Value::String("short".into()) + ]), + "a long string from a value page" + ); +} + +#[test] +fn set_valued_attribute_is_qry_015() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:alice :name \"alice\"] [:alice :user/scopes #{:scope/read}]])") + .unwrap(); + assert_eq!( + code( + &db, + "(query [:find ?s :where [?e :name _] [(collect-set ?e :user/scopes) ?s]])" + ), + "QRY-015" + ); + // The pattern binds the stored set. + let r = rows(&db, "(query [:find ?s :where [?e :user/scopes ?s]])"); + assert_eq!(r.len(), 1, "one stored set"); +} + +#[test] +fn unbound_entity_is_int_018() { + let db = scopes(); + assert_eq!( + code( + &db, + "(query [:find ?s :where [(collect-set ?e :user/scope) ?s]])" + ), + "INT-018" + ); + assert_eq!( + code( + &db, + "(query [:find ?s :where [(collect-set ?e :user/scope) ?s] [?e :user/name _]])" + ), + "INT-018", + "bound by a later clause" + ); +} + +#[test] +fn keyword_entities_and_non_entities() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + r#"(transact [[:alice :friend :bob] [:alice :friend :nobody] [:alice :name "alice"] + [:bob :age 40] [:bob :age 41]])"#, + ) + .unwrap(); + // `:friend` holds keywords: each names an entity, or none. + let r = rows( + &db, + "(query [:find ?f ?s :where [?a :friend ?f] [(collect-set ?f :age) ?s]])", + ); + assert_eq!(r.len(), 2, "both friends kept"); + for row in &r { + let expected = match &row[0] { + Value::Keyword(k) if k == ":bob" => set(vec![Value::Integer(40), Value::Integer(41)]), + Value::Keyword(k) if k == ":nobody" => set(vec![]), + _ => panic!("a friend keyword"), + }; + assert!(row[1] == expected, "ages of the friend"); + } + // A string or an integer is no entity. + for var in ["?n", "?x"] { + let q = format!( + "(query [:find ?s :where [?e :name ?n] [(+ 1 2) ?x] [(collect-set {var} :age) ?s]])" + ); + assert!(one_set(&db, &q) == set(vec![]), "{var} is no entity"); + } +} + +#[test] +fn in_rule_bodies_not_bodies_and_or_branches() { + let db = scopes(); + db.execute( + "(rule [(writer ?e) [?e :user/name _] [(collect-set ?e :user/scope) ?s] [(in? :scope/write ?s)]])", + ) + .unwrap(); + let r = rows(&db, "(query [:find ?e :where (writer ?e)])"); + assert_eq!(r.len(), 1, "alice writes"); + let r = rows( + &db, + "(query [:find ?n :where [?e :user/name ?n] + (not-join [?e] [(collect-set ?e :user/scope) ?s] [(any-in? ?s #{:scope/write})])])", + ); + assert!( + r.len() == 1 && r[0][0] == Value::String("bob".into()), + "bob does not write" + ); + // In `not`, the output variable is bound outside: an already-bound one. + db.execute("(transact [[:none :empty #{}]])").unwrap(); + let r = rows( + &db, + "(query [:find ?n :where [?e :user/name ?n] [:none :empty ?s] + (not [(collect-set ?e :user/scope) ?s])])", + ); + assert!( + r.len() == 1 && r[0][0] == Value::String("alice".into()), + "alice has scopes" + ); + let r = rows( + &db, + "(query [:find ?n :where [?e :user/name ?n] + (or-join [?e] (and [(collect-set ?e :user/scope) ?s] [(= ?s #{})]) [?e :user/name \"alice\"])])", + ); + assert_eq!(r.len(), 2, "bob by the first branch, alice by the second"); +} + +#[test] +fn output_variable_already_bound() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact [[:a :tags #{1 2}] [:a :tag 1] [:a :tag 2] + [:b :tags #{1}] [:b :tag 1] [:b :tag 3]])", + ) + .unwrap(); + for q in [ + "(query [:find ?e :where [?e :tags ?s] [(collect-set ?e :tag) ?s]])", + "(query [:find ?e :where [?e :tag _] [(collect-set ?e :tag) ?s] [?e :tags ?s]])", + ] { + let r = rows(&db, q); + let mut entities: Vec<_> = r.iter().map(|row| row[0].clone()).collect(); + entities.dedup(); + assert_eq!(entities.len(), 1, "only :a's stored set equals its tags"); + } +} + +#[test] +fn memory_limit_is_qry_012() { + let db = OpenOptions::new() + .query_memory_limit(2048) + .open_memory() + .unwrap(); + let facts: String = (0..200).map(|i| format!("[:a :v {i}]")).collect(); + db.execute(&format!("(transact [[:a :name \"a\"] {facts}])")) + .unwrap(); + let err = db + .execute("(query [:find ?s :where [?e :name _] [(collect-set ?e :v) ?s]])") + .err() + .expect("over the limit"); + assert_eq!(err.code(), "QRY-012"); + assert!( + err.to_string().contains("CollectSet"), + "the set is the holder" + ); + // The same values streamed by a pattern hold nothing. + assert_eq!(rows(&db, "(query [:find ?v :where [?e :v ?v]])").len(), 200); +} + +#[test] +fn predicates_over_the_result_and_prepared_slots() { + let db = scopes(); + let r = rows( + &db, + "(query [:find ?n ?w :where [?e :user/name ?n] [(collect-set ?e :user/scope) ?s] + [(all-in? ?s #{:scope/read :scope/write}) ?w]])", + ); + assert_eq!(r.len(), 2, "every set is within, the empty one too"); + assert!( + r.iter().all(|row| row[1] == Value::Boolean(true)), + "all-in? is true for both" + ); + let p = db + .prepare( + "(query [:find ?n :where [?e :user/name ?n] [(collect-set ?e :user/scope) ?s] + [(any-in? ?s $wanted)]])", + ) + .unwrap(); + for (wanted, n) in [(vec![kw(":scope/write")], 1), (vec![kw(":scope/none")], 0)] { + let w = BindValue::Val(set(wanted)); + match p.execute(&[("wanted", w)]).unwrap() { + QueryResult::QueryResults { results, .. } => { + assert_eq!(results.len(), n, "prepared any-in?") + } + _ => panic!("expected query results"), + } + } +} + +#[test] +fn parse_errors() { + let db = scopes(); + let q = |clause: &str| format!("(query [:find ?e :where [?e :user/name _] {clause}])"); + for (clause, expected) in [ + ("[(collect-set ?e :user/scope)]", "PRS-122"), + ("[(collect-set :alice :user/scope) ?s]", "PRS-123"), + ("[(collect-set ?e \"user/scope\") ?s]", "PRS-123"), + ("[(collect-set ?e ?a) ?s]", "PRS-123"), + ("[(collect-set $e :user/scope) ?s]", "PRS-123"), + ("[(collect-set ?e $a) ?s]", "PRS-123"), + ("[(collect-set ?e) ?s]", "PRS-065"), + ("[(collect-set ?e :a :b) ?s]", "PRS-065"), + ("[(collect-set ?e :user/scope) ?s ?t]", "PRS-068"), + ("[(collect-set ?e :user/scope) :s]", "PRS-069"), + ("[(in? :x (collect-set ?e :user/scope)) ?b]", "PRS-067"), + ("[(nil? (collect-set ?e))]", "PRS-067"), + ] { + assert_eq!(code(&db, &q(clause)), expected, "{clause}"); + } +} + +#[test] +fn name_cannot_be_registered() { + let db = Minigraf::in_memory().unwrap(); + assert!( + db.register_predicate("collect-set", |_| true).is_err(), + "collect-set is built in" + ); +} diff --git a/tests/grammar/grammar.pest b/tests/grammar/grammar.pest index 8e0241b82c..0fdb8bba38 100644 --- a/tests/grammar/grammar.pest +++ b/tests/grammar/grammar.pest @@ -163,8 +163,9 @@ where_clause = { // Pattern: exactly [E A V] — three EDN values pattern_clause = { "[" ~ edn_value ~ edn_value ~ edn_value ~ "]" } -// Expression clause: [(expr) ?out?] — first element is a list (the expression) -expr_clause = { "[" ~ expr ~ variable? ~ "]" } +// Expression clause: [(expr) ?out?] — first element is a list (the expression). +// collect-set (#316) is only a whole clause, and always binds. +expr_clause = { "[" ~ (collect_set ~ variable | expr ~ variable?) ~ "]" } // NOT / NOT-JOIN not_clause = { "(" ~ "not" ~ where_clause+ ~ ")" } @@ -183,8 +184,10 @@ rule_invocation = { "(" ~ !reserved_head ~ plain_sym ~ edn_value* ~ ")" } // ── EXPRESSIONS ─────────────────────────────────────────────────────────── expr = { "(" ~ expr_body ~ ")" } expr_body = { binary_form | unary_form } -unary_form = { (unary_op | op_sym | plain_sym) ~ expr_arg } +unary_form = { !collect_set_head ~ (unary_op | op_sym | plain_sym) ~ expr_arg } binary_form = { binary_op ~ expr_arg ~ expr_arg } +collect_set = { "(" ~ collect_set_head ~ variable ~ keyword ~ ")" } +collect_set_head = @{ "collect-set" ~ !word_cont } unary_op = @{ "string?" | "integer?" | "float?" | "boolean?" | "nil?" } binary_op = @{ "<=" | ">=" | "!=" | "starts-with?" | "ends-with?" | "contains?" | "matches?" | diff --git a/tests/grammar/invalid/syntax/collect_set_nested.edn b/tests/grammar/invalid/syntax/collect_set_nested.edn new file mode 100644 index 0000000000..11bff372f9 --- /dev/null +++ b/tests/grammar/invalid/syntax/collect_set_nested.edn @@ -0,0 +1 @@ +(query [:find ?b :where [?e :user/name _] [(in? :x (collect-set ?e :user/scope)) ?b]]) diff --git a/tests/grammar/invalid/syntax/collect_set_no_binding.edn b/tests/grammar/invalid/syntax/collect_set_no_binding.edn new file mode 100644 index 0000000000..7c9c37c661 --- /dev/null +++ b/tests/grammar/invalid/syntax/collect_set_no_binding.edn @@ -0,0 +1 @@ +(query [:find ?e :where [?e :user/name _] [(collect-set ?e :user/scope)]]) diff --git a/tests/grammar/invalid/syntax/collect_set_one_operand.edn b/tests/grammar/invalid/syntax/collect_set_one_operand.edn new file mode 100644 index 0000000000..c4d58bda81 --- /dev/null +++ b/tests/grammar/invalid/syntax/collect_set_one_operand.edn @@ -0,0 +1 @@ +(query [:find ?s :where [?e :user/name _] [(collect-set ?e) ?s]]) diff --git a/tests/grammar/invalid/syntax/collect_set_string_attribute.edn b/tests/grammar/invalid/syntax/collect_set_string_attribute.edn new file mode 100644 index 0000000000..242c128db1 --- /dev/null +++ b/tests/grammar/invalid/syntax/collect_set_string_attribute.edn @@ -0,0 +1 @@ +(query [:find ?s :where [?e :user/name _] [(collect-set ?e "user/scope") ?s]]) diff --git a/tests/grammar/valid/query_collect_set.edn b/tests/grammar/valid/query_collect_set.edn new file mode 100644 index 0000000000..4dab6d14ab --- /dev/null +++ b/tests/grammar/valid/query_collect_set.edn @@ -0,0 +1,4 @@ +(query [:find ?e ?scopes ?admin + :where [?e :user/name _] + [(collect-set ?e :user/scope) ?scopes] + [(in? :scope/admin ?scopes) ?admin]]) diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs index 3de64e2577..9ba5d4c6f3 100644 --- a/tests/plan_independence_test.rs +++ b/tests/plan_independence_test.rs @@ -238,6 +238,15 @@ const MATRIX: &[&str] = &[ // (A fixed `:valid-at`: by default `?t` is each query's "now".) r#"[:find ?b ?t :valid-at "2030-01-01T00:00:00Z" :where [?b :db/valid-at ?t] [?a :friend ?b] [?b :name ?n]]"#, r#"[:find ?b :where [?b :db/valid-at ?t] [?a :friend ?b]]"#, + // collect-set (#316): keyword and ref entities, an empty set, under a + // predicate, in `not-join` and `or-join`, an output a pattern binds. + r#"[:find ?n ?s :where [?e :name ?n] [(collect-set ?e :friend) ?s]]"#, + r#"[:find ?a ?s :where [?a :friend ?b] [(collect-set ?b :age) ?s]]"#, + r#"[:find ?n :where [?e :name ?n] [(collect-set ?e :age) ?s] [(in? 40 ?s)]]"#, + r#"[:find ?n :where [?e :name ?n] (not-join [?e] [(collect-set ?e :friend) ?s] [(= ?s #{})])]"#, + r#"[:find ?n :where [?e :name ?n] (or-join [?e] (and [(collect-set ?e :age) ?s] [(any-in? ?s #{25 30})]) [?e :x _])]"#, + r#"[:find ?e :where [?e :age ?a] [(collect-set ?e :age) ?s] [?f :name _] [(collect-set ?f :age) ?s]]"#, + r#"[:find ?n ?s :any-valid-time :where [?e :name ?n] [(collect-set ?e :age) ?s]]"#, // Time travel. r#"[:find ?n :as-of 1 :where [?e :name ?n] [?e :age ?a]]"#, r#"[:find ?n ?a :valid-at "2020-06-01T00:00:00Z" :where [?e :name ?n] [?e :age ?a]]"#,