adityamukho · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026 · Oct 24, 2026
@@ -51,6 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 ### Added
 
 - **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.
 - **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<leaf> ?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`.

@@ -215,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1760 tests** (1747 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
+**1775 tests** (1762 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.

@@ -108,7 +108,8 @@ 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?" | "<" | ">" | "=" | "+" | "-" | "*" | "/"  (* token *)
+              | "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
 

@@ -4,9 +4,9 @@
 
 | | Default features | With `--features test-hooks` |
 |---|---|---|
-| **Passing** | 1,747 | 1,765 |
+| **Passing** | 1,762 | 1,780 |
 | **Ignored** | 13 | 14 |
-| **Total** | 1,760 | 1,779 |
+| **Total** | 1,775 | 1,794 |
 
 **Verified**: 2026-10-24 with `cargo test --quiet`.
 
@@ -96,6 +96,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.
 - **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.

@@ -190,17 +190,61 @@ machine, binary size reported (gate is report-only until #551's PR 2). Codex rev
 (`codex exec -s read-only … < /dev/null`), findings checked against the code. PR body without a
 closing keyword; monitor CI until green.
 
-## PR 2 — predicates (outline; detailed after PR 1 merges)
-
-13. `types.rs` `BinOp::{In, NotIn, AnyIn, AllIn, NoneIn}`; parser arm beside `contains?`
-    (`parser.rs:1297`, `1340`); `functions.rs` sentinel names (`functions.rs:93`) so UDFs cannot
-    take them.
-14. `eval_binop`: spec §6 table and type mismatches (`Err(())`), `not-in?` with a non-set is
-    `Err(())`.
-15. Prepared: `BindValue::Val(Value::Set)` in an operand slot and a value slot
-    (`prepared.rs` `substitute`), reused across executes.
-16. Tests (`tests/predicate_expr_test.rs`, `prepared_statements_test.rs`, grammar corpus): the
-    spec §12 predicate list; docs share (`CHANGELOG`, README); review and PR.
+## PR 2 — predicates
+
+#306's implementation has not merged (only its spec, #729), so the `:order-by` over a set column
+test moves to whichever of #306 PR 1 and this PR lands second.
+
+### Step 13. Operators and parser
+
+- `types.rs`: `BinOp::{In, NotIn, AnyIn, AllIn, NoneIn}` after `Contains`, documented as "set
+  predicates — return Boolean"; `test_binop_variants_exist` names them.
+- `parser.rs` `parse_expr`: `"in?" | "not-in?" | "any-in?" | "all-in?" | "none-in?"` join the
+  binary arm (arity `PRS-065` as for `contains?`), mapped in the `op` match; `Contains` stops being
+  the `_` arm (an explicit `"contains?"`, `_` unreachable as in `eval_binop`).
+- `functions.rs`: the five names join the built-in sentinels, so `register_predicate` refuses them
+  as it refuses `contains?`.
+- `grammar.pest` `binary_op`: the five names, longest first where one is a prefix of another (none
+  are); `docs/GRAMMAR.md` regenerated (`UPDATE_GRAMMAR_DOC=1 cargo test --test grammar_doc`);
+  `tests/grammar/valid/query_expr_set_predicates.edn` (filter and binding forms, each op).
+  `TOKENS` is unchanged: the string predicates are not tokens either, so the verifier's cost stays.
+
+### Step 14. Evaluation
+
+`executor.rs` `eval_binop`, the arm after `Matches` (the engine's `Filter`/`Bind` call
+`eval_expr`, so both forms follow):
+
+| op | `(l, r)` accepted | result |
+|---|---|---|
+| `In` / `NotIn` | `l` not a set, `r` a set | `r.contains(&l)` / its negation |
+| `AnyIn` / `NoneIn` | both sets | some element of `l` in `r` / its negation |
+| `AllIn` | both sets | every element of `l` in `r` |
+
+Every other shape is `Err(())`. `ValueSet::contains` is the `BTreeSet` lookup under `Value`'s `Ord`,
+which is the spec's set equality (§2), so NaN, `-0.0`/`0.0` and keyword ≠ ref follow with no special
+case. Iterate the smaller set for `AnyIn`/`NoneIn`; `AllIn` returns false at once when `l` is larger.
+Unit tests in `executor.rs` next to `test_eval_contains_true`: each op true and false, every
+empty-set case of spec §6, each wrong shape.
+
+### Step 15. Prepared sets
+
+No code: `substitute_expr` puts a bound `Value` into the `Expr` (`resolve_val_slot`) and
+`resolve_value_slot` turns a `Value::Set` into `EdnValue::Set` (PR 1). Tests only:
+`BindValue::Val(Value::Set)` as an `in?` operand slot and as a pattern value slot, one prepared query
+executed with two different sets.
+
+### Step 16. Tests, docs, PR
+
+- `tests/set_predicates_test.rs` (file-backed parts behind `#![cfg(not(target_arch = "wasm32"))]`):
+  spec §6 table per scalar type (string, integer, float, boolean, nil, keyword, ref), NaN and `-0.0`,
+  keyword vs ref of the same entity, every empty-set case, each wrong shape in filter and binding
+  form, `not-in?` with a non-set drops the row, stored-attribute operands (pending and after
+  `checkpoint`), `=`/`!=` between sets, `contains?` on a set is still a type mismatch, arity
+  `PRS-065`, `register_predicate("in?")` refused. `collect-set` operands come with PR 3.
+- `tests/prepared_statements_test.rs`: step 15.
+- `CHANGELOG.md` (Unreleased, beside PR 1's entry), README predicate list, `CLAUDE.md` and
+  `docs/TEST_COVERAGE.md` counts.
+- Review as step 12; PR into `v3` without a closing keyword.
 
 ## PR 3 — `collect-set` (outline)
 

@@ -755,6 +755,29 @@ fn eval_binop(op: &BinOp, l: Value, r: Value) -> Result<Value, ()> {
             _ => Err(()),
         },
 
+        // Set predicates (#316): membership is Value's Ord, so NaN, -0.0/0.0 and
+        // keyword != ref need no case here. A scalar where a set is needed, or a set
+        // as in?'s element, is a type mismatch; not-in? then drops the row too.
+        BinOp::In | BinOp::NotIn => match (&l, &r) {
+            (Value::Set(_), _) => Err(()),
+            (x, Value::Set(s)) => Ok(Value::Boolean(s.contains(x) == matches!(op, BinOp::In))),
+            _ => Err(()),
+        },
+        BinOp::AnyIn | BinOp::NoneIn => match (&l, &r) {
+            (Value::Set(a), Value::Set(b)) => {
+                let (small, large) = if a.len() <= b.len() { (a, b) } else { (b, a) };
+                let any = small.iter().any(|x| large.contains(x));
+                Ok(Value::Boolean(any == matches!(op, BinOp::AnyIn)))
+            }
+            _ => Err(()),
+        },
+        BinOp::AllIn => match (&l, &r) {
+            (Value::Set(a), Value::Set(b)) => Ok(Value::Boolean(
+                a.len() <= b.len() && a.iter().all(|x| b.contains(x)),
+            )),
+            _ => Err(()),
+        },
+
         // Eq/Neq handled above
         BinOp::Eq | BinOp::Neq => unreachable!(),
     }
@@ -2251,6 +2274,51 @@ mod expr_eval_tests {
         );
     }
 
+    #[test]
+    fn test_eval_set_predicates() {
+        let set = |v: &[i64]| {
+            Value::Set(
+                crate::graph::types::ValueSet::new(v.iter().map(|i| Value::Integer(*i))).unwrap(),
+            )
+        };
+        let b = |x: bool| Ok(Value::Boolean(x));
+        assert_eq!(
+            eval_binop(&BinOp::In, Value::Integer(1), set(&[1, 2])),
+            b(true)
+        );
+        assert_eq!(
+            eval_binop(&BinOp::In, Value::Integer(3), set(&[1, 2])),
+            b(false)
+        );
+        assert_eq!(
+            eval_binop(&BinOp::NotIn, Value::Integer(3), set(&[1, 2])),
+            b(true)
+        );
+        assert_eq!(
+            eval_binop(&BinOp::NotIn, Value::Integer(1), set(&[])),
+            b(true)
+        );
+        assert_eq!(eval_binop(&BinOp::AnyIn, set(&[1, 2]), set(&[2])), b(true));
+        assert_eq!(eval_binop(&BinOp::AnyIn, set(&[2]), set(&[1, 3])), b(false));
+        assert_eq!(eval_binop(&BinOp::AllIn, set(&[]), set(&[])), b(true));
+        assert_eq!(eval_binop(&BinOp::AllIn, set(&[1, 2]), set(&[1])), b(false));
+        assert_eq!(eval_binop(&BinOp::NoneIn, set(&[1, 2]), set(&[3])), b(true));
+        assert_eq!(
+            eval_binop(&BinOp::NoneIn, set(&[3]), set(&[1, 2, 3])),
+            b(false)
+        );
+        // Wrong shapes.
+        assert_eq!(eval_binop(&BinOp::In, set(&[1]), set(&[1])), Err(()));
+        assert_eq!(
+            eval_binop(&BinOp::NotIn, Value::Integer(1), Value::Integer(1)),
+            Err(())
+        );
+        for op in [BinOp::AnyIn, BinOp::AllIn, BinOp::NoneIn] {
+            assert_eq!(eval_binop(&op, Value::Integer(1), set(&[1])), Err(()));
+            assert_eq!(eval_binop(&op, set(&[1]), Value::Integer(1)), Err(()));
+        }
+    }
+
     #[test]
     fn test_eval_matches_true() {
         let re = regex_lite::Regex::new("^[^@]+@[^@]+$").unwrap();

@@ -94,6 +94,11 @@ impl FunctionRegistry {
             "ends-with?",
             "contains?",
             "matches?",
+            "in?",
+            "not-in?",
+            "any-in?",
+            "all-in?",
+            "none-in?",
         ] {
             reg.predicates.insert(
                 name.to_string(),