From de105e13459ec2d6ad7d90517457d69a9267d182 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 09:40:10 +0530 Subject: [PATCH 1/5] docs(plan): #316 set values implementation plan Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF --- .../plans/2026-10-24-316-set-values.md | 222 ++++++++++++++++++ 1 file changed, 222 insertions(+) create mode 100644 docs/superpowers/plans/2026-10-24-316-set-values.md diff --git a/docs/superpowers/plans/2026-10-24-316-set-values.md b/docs/superpowers/plans/2026-10-24-316-set-values.md new file mode 100644 index 0000000000..81b05ec1ad --- /dev/null +++ b/docs/superpowers/plans/2026-10-24-316-set-values.md @@ -0,0 +1,222 @@ +# Set values and set-membership predicates (#316) — Plan + +Spec: `docs/superpowers/specs/2026-10-24-set-values-design.md` (merged as #732, `3f4a5911`), called +"the spec" below. PRs target `v3`, merge commits. #316 closes by hand after PR 3 (closing keywords do +not fire on `v3`). + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–12: set values end to end, exact-value transact/retract/query (spec §3–5, §8, §9) | `feat/316-set-values` | +| 2 | 13–16: the five predicates and prepared sets (spec §6) | `feat/316-set-predicates` | +| 3 | 17–20: `collect-set` (spec §7) | `feat/316-collect-set` | +| 4 | docs site, then one PR per binding (spec §9, §13) | per repo | + +Each PR leaves `v3` with no unused code outside `cfg(test)`, updates the test counts, and runs +`cargo test`, `cargo clippy --all-targets` (both wasm targets as `wasm.yml` does) and the Kani suite +on the bench machine before it is raised. #306 runs in another session: whichever of the two lands a +step that touches `parser.rs`, `grammar.pest`, `verifier.rs` (`TOKENS` length) or `error.rs` second +rebases, and takes the next free codes. + +## Decisions not fixed by the spec + +1. **Long-value reads become byte reads.** `DictReader::long_value` returns `String` and fails + `STG-036` on non-UTF-8 bytes (`dict.rs:203`), and `find_long_value` compares candidates as strings + (`dict.rs:219`). A set record is not UTF-8, so a string whose `hash64` collides with a set's would + fail instead of missing. Add `DictReader::long_bytes(vref) -> Result>` (the cache keyed by + `ValueRef` holds bytes), make `long_value` a UTF-8 view of it, and make the dedup lookup + `find_long_bytes(&[u8])`, comparing bytes. `KeySource` gains `long_bytes` and `long_bytes_ref`; + `long_value_ref(s)` becomes `long_bytes_ref(s.as_bytes())`. +2. **The `Encoder` stages long values as bytes.** `new_values: Vec` / `new_long: + HashMap` (`dict.rs:376-394`) become `Vec` keyed by bytes, where + `LongValue { bytes, kind: Str | Set { prefix } }`, so `finish` builds `keys::long_str` or + `keys::long_set` from the returned ref. One dedup table serves both kinds (spec §4.2). +3. **A set's v8 element encoding needs ids first.** `Encoder::value` for `Value::Set` assigns each + keyword and ref element's id with `self.iid` / `self.eid` (as the scalar arms do), builds each + element's `KeyValue` (`Str` for every string, whatever its length), encodes and sorts them + (`keys::set_elements(&[KeyValue]) -> Vec`), then inlines (`KeyValue::Set`) or stages a long + value. `keys::set_bytes_bound(&ValueSet) -> usize` (spec §3, no ids) lives in `keys.rs` next to it, + so the WAL check and the encoder share one definition. +4. **Committed sets are decoded at scan.** `Cell::of_key` stays infallible and has no DICT access, so + the committed scan (`scan.rs:462`) calls a new `Cell::of_key_with(&kf.v, ctx.keys)` that is + `of_key` for every other value and, for `Set`/`LongSet`, decodes elements through + `KeySource::ident_of`/`uuid_of` (and `long_bytes`) into `Scalar::Set(Arc)` (spec §8). + `Cell::of_value` maps `Value::Set` straight to it. +5. **Golden corpus.** The spec's §12 asks for a golden-file entry with sets. The corpus is v7 files + (`tests/golden/`, never regenerated), and v7 has no sets, so there is nothing to add. The + reopen, checkpoint and WAL-replay tests of step 6 cover persistence instead. +6. **`Value` match sites outside the crate's API.** `Value` becomes `#[non_exhaustive]`, which only + affects other crates. Inside the crate every exhaustive match gets a real `Set` arm, never `_`, so + the compiler finds each one: `types.rs`, `aggregate.rs`, `functions.rs`, `executor.rs`, `repl.rs`, + `engine/project.rs`, `engine/cell.rs`, `engine/scan.rs`, `engine/plan.rs`, `prepared.rs`, + `parser.rs`, `matcher.rs`, `db.rs`, `browser/mod.rs`, `storage/{index,keys,dict,verify}.rs`. + Examples and tests in this repo that match exhaustively also get an arm. + +## PR 1 — set values + +### Step 1. `ValueSet` and `Value::Set` + +- `graph/types.rs`: `ValueSet` (spec §3) with `new`, `iter`, `len`, `is_empty`, `contains`, + `IntoIterator for &ValueSet`; `new` uses `get` + `replace` for the `value_order`-least float + (spec §3, "Inserting an equal float"). `Value::Set(ValueSet)` after `Null`; `#[non_exhaustive]` + on `Value`. Discriminant 7 in `Ord`'s cross-variant arm (`types.rs:160`); `Set` arms in `Ord` + (lexicographic over `iter()`), `Hash` (len, then elements), the docs table above `Value`, and + `as_*` helpers (none returns a set; add `as_set`). +- Serde: `impl Serialize for ValueSet` (seq) and a hand-written `Deserialize` that collects + `Vec` and calls `new`, mapping `API-021` to a serde error. +- `error.rs`: `Api021` ("a set cannot hold a set"), four sites as `Api020`; `ERROR_REFERENCE.md`. +- `lib.rs`: re-export `ValueSet` beside `Value`. +- Tests (`types.rs` unit): dedup; `#{0.0 -0.0}` and `#{-0.0 0.0}` hold `-0.0` (check + `is_sign_negative`); several NaNs give one; nested set `API-021`; proptest over random scalar sets: + `a == b ⇒ hash(a) == hash(b)`, `cmp` antisymmetric and transitive, `new` independent of insertion + order; postcard round trip; postcard of a non-canonical sequence restores the order; postcard of a + nested set fails; postcard of each pre-existing variant unchanged (bytes fixed in the test). + +### Step 2. `value_order` and aggregates + +- `aggregate.rs`: `class(Set) = 6`; a `Set` arm in `value_order` (elements sorted by + `value_order`, lexicographic, proper prefix less). The other `Value` matches in `aggregate.rs` + treat a set as a keyword is treated (`sum`/`avg` type rules). +- `functions.rs`: the `Value` matches get `Set` arms with the keyword behaviour. +- Tests: `value_order` is a total order over a mixed proptest sample including sets; `min`/`max` + over set values. + +### Step 3. Parser + +- Tokenizer (`parser.rs:181`): `#` then `{` is `Token::SetOpen`; the tag loop is unchanged + otherwise. `parse_edn`: `SetOpen` reads values to `}` into `EdnValue::Set(Vec)`; + a nested `SetOpen` is `PRS-119`; a symbol, vector, list, map or bind slot element is `PRS-120`. +- `types.rs` (`datalog`): `EdnValue::Set`; its `Display`/`edn_to_string` arm (`parser.rs:1984`) + prints `#{..}`. +- `matcher.rs::edn_to_value`: `Set` → `Value::Set(ValueSet::new(elements' edn_to_value))`. +- `parse_expr_arg` (`parser.rs:1240`): `Set` → `Expr::Lit(Value::Set(..))`. +- `parser/statement.rs`: fact values go through `edn_to_value`, so a set value needs no change + beyond a test; entity/attribute positions reject it with today's codes. +- `error.rs`: `Prs119`, `Prs120` (next free when the PR opens; #306 holds 115–118). +- Tests (`parser.rs` unit, `tests/error_codes_prs_test.rs`): empty, duplicates, every scalar kind, + `#uuid` inside, `#uuid` directly after `#{`, whitespace and commas, unterminated `#{1`, each new + code, a set in entity and attribute position. + +### Step 4. Grammar and verifier + +- `grammar.pest`: `set_lit = { "#{" ~ edn_value* ~ "}" }` in `edn_value` (`grammar.pest:81`). +- Corpus: `tests/grammar/valid/transact_set.edn`, `query_set_constant.edn`, `set_empty.edn`; + `tests/grammar/invalid/syntax/set_unterminated.edn`; `tests/grammar/invalid/semantic/` + `set_nested.edn`, `set_variable.edn`. +- `verifier.rs`: `"#{"` in `TOKENS` (length + 1); `SEMANTIC` entries for `PRS-119` (witness + `#{#{}}`) and `PRS-120` (witness `#{?x}`). Run bound 3 locally and bound 4 on the bench machine. + +### Step 5. Pending encoding and WAL + +- `index.rs::encode_value`: `Set` → `0x07`, then per element in canonical order a `u32` BE length + and its `encode_value` (spec §4.3). +- `keys.rs`: `set_bytes_bound` (decision 3). +- `wal.rs::check_fact_size` (`wal.rs:149`): a `Set` arm, `set_bytes_bound > MAX_VALUE_BYTES` is + `WAL-003`; each keyword element over `MAX_IDENT_BYTES` is `WAL-003`. Widen the `WAL-003` message + to name the value kind; `ERROR_REFERENCE.md`. +- Tests: `encode_value` of equal sets equal, of sets differing in one element different, of + `#{"ab"}` vs `#{"a" "b"}` different; WAL accepts a set at the bound and rejects one byte over + (`tests/error_codes_wal_test.rs`); a WAL entry holding sets replays after a simulated crash + (`wal_test.rs`). + +### Step 6. v8 keys, value pages, DICT + +- `keys.rs`: `TAG_SET = 0x08`; `KeyValue::Set(Vec)` and `LongSet { prefix, hash, vref }`; + `set_elements`, `long_set`; `put_value` arms (spec §4.1 table); `Reader::value` decodes both forms + (inline: unescape to `00 00`, then elements until the end; long: as `string()` does after `00 01`); + `skip_value` (`keys.rs:369`) skips `TAG_SET` as `TAG_STRING`. `ValueKind` (`keys.rs:645`) gets + `Set` if AVET range building names kinds. +- `dict.rs`: decisions 1–3; `DictReader::fact` (`dict.rs:233`) decodes `Set`/`LongSet` into + `Value::Set` through `name_of`/`uuid_of`/`long_bytes`. +- `reader.rs`: `KeySource` methods of decision 1. +- `verify.rs` (`verify.rs:281`, `385`): `LongSet` refs are walked and counted as `LongStr` refs are; + a record that does not decode as a set's elements is reported (the existing long-value finding). +- Tests (`keys.rs`, `dict.rs`, `persistent_facts.rs` unit; `tests/integrity_test.rs`): round trip of + inline sets at 63/64/65 element-encoding bytes; long set with a long string element; equal long + sets written in two checkpoints share one value page; a set and a string with equal bytes; + keyword and ref elements across checkpoint and reopen (ids assigned in the same checkpoint and in + an earlier one); `verify` clean on a file with inline and long sets, and reports a corrupted set + record. + +### Step 7. Kani + +- `index/verification.rs`: `encode_value` injective over sets of at most two `Integer`/`Boolean` + elements. `keys/verification.rs`: `set_elements` of a two-element set independent of input + order. No decoder or string harness (CLAUDE.md). Run the whole suite on the bench machine and + record peak memory in the PR. + +### Step 8. Engine cells, joins, scans + +- `engine/cell.rs`: `Scalar::Set(Arc)`, `JoinKey::Set(Arc)` (hash and eq via + `Value`'s), `of_key_with` (decision 4), `of_value` arm. +- `engine/scan.rs`: the committed scan uses `of_key_with`; a set constant (`ValueConst::Exact`, + `scan.rs:596`, `656`) is encoded for AVET as a long string constant is: inline when every element's + id exists (`iid_of`/`eid_of`), else the committed part reads nothing; long through + `long_bytes_ref`. +- `engine/plan.rs`: `ValueConst::matches` arm (exact). +- `engine/project.rs`: `Scalar::Set` → `Value::Set`. +- Tests (`engine/tests.rs`, `tests/multi_value_test.rs`): a set constant in a pattern, committed + (AVET and per-fact paths, forced with `optimizer::set_reorder`) and pending; join on a set column + between committed and pending rows; `count-distinct` and grouping by a set; `or`/`not` keys on a + set column; retraction of a set value, `:as-of` before and after it, `:valid-at` windows. + +### Step 9. Output + +- `repl.rs::format_value`: `#{..}` in canonical order, `#{}` when empty. +- `browser/mod.rs::value_to_json`: array in canonical order (`#[wasm_bindgen_test]` in the browser + tests). +- `Display`/`Debug` for `ValueSet` as `#{..}`. +- Tests: REPL formatting of empty, mixed, nested-in-row output; JSON array order. + +### Step 10. Integration tests + +`tests/set_values_test.rs` (native, `#![cfg(not(target_arch = "wasm32"))]`): transact a set, query +it back (in-memory and file, before and after checkpoint and reopen); exact-match retraction; +cursor (`Minigraf::query`) and fact log return sets; `LogWriter` copies a file with sets +(`verify` clean); a `WriteTransaction` that becomes large (`transaction_chunk_facts` small) with +sets. Model-based test (`model_based_test.rs` value strategy, `prop_oneof!` at line 37) gains small +sets of scalars, with the reference model comparing by `Value`. + +### Step 11. Docs (PR 1 share) + +`CHANGELOG.md` (Added: set values; Changed: `Value` is `#[non_exhaustive]`, format v8 value tag +`0x08`), `docs/ERROR_REFERENCE.md` (`API-021`, `PRS-119`, `PRS-120`, `WAL-003` text), +`CLAUDE.md` (data model block, module notes for `keys.rs`/`dict.rs`/`value_pages.rs`, test count), +`README.md` (value types), `docs/TEST_COVERAGE.md`. + +### Step 12. Review and PR + +`cargo test`, clippy (native and wasm), `wasm.yml`'s browser tests via the PR, Kani on the bench +machine, binary size reported (gate is report-only until #551's PR 2). Codex review +(`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 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 4 — docs site and bindings + +- `minigraf-docs`: `content/datalog-reference.md` (set literals, predicates, `collect-set`, + `@since v3.0.0`), `content/architecture.md` (Set row in the value table), `content/comparison.md`. +- Bindings (`v3` branches of python, c, node, java, swift, android): `value_to_json` set arm (array) + and a wildcard arm, consumer test returning a set; bump the core git-rev pin. From 14ad5eb3abd78e4abd0d82c54563d3135dcb8a18 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 13:07:29 +0530 Subject: [PATCH 2/5] feat(values): set values end to end (#316) Value::Set(ValueSet), #{...} literals in the parser and the pest grammar, v8 key tag 0x08 (inline up to 64 bytes, else a value page), pending encoding, WAL size check, engine cells and joins, REPL and JSON output. API-021, PRS-119, PRS-120, PRS-121. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF --- docs/ERROR_REFERENCE.md | 73 ++++- docs/GRAMMAR.md | 13 +- src/browser/mod.rs | 1 + src/error.rs | 36 ++ src/graph/types.rs | 308 +++++++++++++++++- src/lib.rs | 2 +- src/query/datalog/aggregate.rs | 26 +- src/query/datalog/matcher.rs | 11 +- src/query/datalog/parser.rs | 44 +++ src/query/datalog/parser/verifier.rs | 8 +- src/query/datalog/prepared.rs | 1 + src/query/datalog/types.rs | 2 + src/query/engine/cell.rs | 28 +- src/query/engine/plan.rs | 6 +- src/query/engine/project.rs | 3 +- src/query/engine/recursive.rs | 1 + src/query/engine/scan.rs | 24 +- src/repl.rs | 4 + src/storage/dict.rs | 140 ++++++-- src/storage/index.rs | 12 + src/storage/keys.rs | 179 +++++++++- src/storage/mod.rs | 6 + src/storage/reader.rs | 8 + src/storage/verify.rs | 27 +- src/wal.rs | 21 +- tests/answers/mod.rs | 5 + tests/golden_corpus_test.rs | 2 + tests/grammar/grammar.pest | 9 +- tests/grammar/invalid/syntax/set_nested.edn | 1 + .../invalid/syntax/set_space_after_hash.edn | 1 + .../invalid/syntax/set_unterminated.edn | 1 + .../invalid/syntax/set_variable_element.edn | 1 + .../grammar/valid/query_expr_set_operand.edn | 3 + tests/grammar/valid/query_set_constant.edn | 2 + tests/grammar/valid/transact_set.edn | 3 + tests/live_reads_test.rs | 1 + tests/plan_independence_test.rs | 2 + tests/reference_model/mod.rs | 8 + tests/set_values_test.rs | 266 +++++++++++++++ tests/soak_test.rs | 8 + 40 files changed, 1220 insertions(+), 77 deletions(-) create mode 100644 tests/grammar/invalid/syntax/set_nested.edn create mode 100644 tests/grammar/invalid/syntax/set_space_after_hash.edn create mode 100644 tests/grammar/invalid/syntax/set_unterminated.edn create mode 100644 tests/grammar/invalid/syntax/set_variable_element.edn create mode 100644 tests/grammar/valid/query_expr_set_operand.edn create mode 100644 tests/grammar/valid/query_set_constant.edn create mode 100644 tests/grammar/valid/transact_set.edn create mode 100644 tests/set_values_test.rs diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 8bd05bbadd..6ea57662de 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -135,6 +135,9 @@ with no `CodedError` anywhere in its chain. | PRS-112 | Empty query section | Parser | | PRS-113 | Unknown query keyword | Parser | | PRS-114 | Rule head argument is not a variable | Parser | +| 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 | | QRY-001 | Invalid entity | Query Execution | | QRY-002 | Attribute must be a keyword | Query Execution | | QRY-003 | Cannot transact a pseudo-attribute | Query Execution | @@ -222,6 +225,7 @@ with no `CodedError` anywhere in its chain. | API-018 | Call on a closed binding object | Database API | | API-019 | Empty or inverted valid-time window | Database API | | API-020 | Assertion and retraction of one fact in one log-writer transaction | Database API | +| API-021 | Set value holds a set | Database API | | INT-000 | Unclassified internal error | Internal | | INT-001 | WriteTransaction already in progress on this thread | Internal | | INT-002 | Invalid entity (API layer) | Internal | @@ -2137,6 +2141,56 @@ with `PRS-047`. --- +### PRS-119 Set literal inside a set literal + +**Error text**: `a set literal cannot hold a set` + +**Cause**: A set literal `#{...}` has another set literal among its elements. Sets hold scalar values only (#316). + +**Resolution**: +- Flatten the elements into one set, or store each inner set as its own attribute value. + +**Example**: +```datalog +(transact [[:alice :user/scopes #{#{:scope/read}}]]) +``` +*`#{:scope/read}` is a set inside a set* + +--- + +### PRS-120 Set literal element is not a scalar literal + +**Error text**: `a set literal holds only strings, numbers, booleans, keywords, #uuid literals and nil; got {}` + +**Cause**: An element of a set literal is a variable, a bind slot, a symbol, a vector, a list or a map. A set literal is a constant: its elements are literals (#316). + +**Resolution**: +- Write the elements as literals, or pass the whole set through a bind slot: `$scopes` bound to `BindValue::Val(Value::Set(..))`. + +**Example**: +```datalog +(query [:find ?e :where [?e :user/scopes #{?x}]]) +``` +*`?x` is a variable* + +--- + +### PRS-121 Unterminated set literal + +**Error text**: `Unterminated set: missing '}'` + +**Cause**: The input ends inside a set literal `#{...}`. + +**Resolution**: +- Close the set with `}`. + +**Example**: +```datalog +(transact [[:alice :user/scopes #{:scope/read +``` + +--- + ## QRY — Query Execution Errors Query execution errors occur after parsing succeeds, during pattern matching, @@ -2970,7 +3024,7 @@ The WAL is replayed on open and deleted on checkpoint. **Error text**: `Value of {} bytes exceeds the maximum of {} bytes. Store large payloads externally and reference them with a Value::String URL/path or Value::Ref entity ID.` -**Cause**: A string value is longer than `MAX_VALUE_BYTES` (4,068 bytes, one value page), or an attribute name or keyword value is longer than 1,024 bytes. This typically means a `Value::String` contains very large content such as raw document text, a base64-encoded image, or binary data. `LogWriter::append` checks the same limits. In-memory databases have no WAL and no limit. +**Cause**: A string value is longer than `MAX_VALUE_BYTES` (4,068 bytes, one value page), a set value's stored form may be longer than that, or an attribute name or keyword value (a keyword in a set included) is longer than 1,024 bytes. A set's size counts each string element's bytes plus three (and one per zero byte), each keyword element as 6 bytes and each ref element as 10, each integer as up to 10 and each float as 9. This typically means a `Value::String` contains very large content such as raw document text, a base64-encoded image, or binary data. `LogWriter::append` checks the same limits. In-memory databases have no WAL and no limit. **Resolution**: - Store large payloads in an external file or object store. @@ -3372,6 +3426,23 @@ let mut log = src.fact_log(&FactFilter::new())?; --- +### API-021 Set value holds a set + +**Error text**: `a set cannot hold a set; its elements must be strings, numbers, booleans, refs, keywords or nil` + +**Cause**: `ValueSet::new` was given a `Value::Set` among its elements. Sets hold scalar values only (#316). + +**Resolution**: +- Build the set from scalar values. To relate several sets, store each one as its own attribute value. + +**Example**: +```rust +let inner = Value::Set(ValueSet::default()); +ValueSet::new(vec![inner]) // API-021 +``` + +--- + ## INT — Internal Errors Internal errors are invariant violations or edge cases that are not expected diff --git a/docs/GRAMMAR.md b/docs/GRAMMAR.md index c0eb83b1a4..a530f55541 100644 --- a/docs/GRAMMAR.md +++ b/docs/GRAMMAR.md @@ -38,6 +38,9 @@ str-char ::= "\" ("n" | "t" | "r" | '"' | "\" | any-char) | (* not followed by '"' | "\" *) any-char string-lit ::= '"' str-char* '"' (* token *) uuid-lit ::= "#uuid" string-lit +set-elem ::= uuid-lit | boolean-lit | nil-lit | float-lit | integer-lit | string-lit + | keyword +set-lit ::= "#{" set-elem* "}" bind-slot ::= "$" (letter | numeral | "_" | "-")+ (* token *) keyword ::= ":" word-cont+ (* token *) variable ::= "?" word-cont* (* token *) @@ -47,9 +50,9 @@ plain-sym ::= (* not followed by boolean-lit *) (* not followed by nil-lit *) | "-" (* not followed by numeral *) word-cont+ (* token *) (* ── EDN VALUE (any EDN atom or container) ── *) -edn-value ::= uuid-lit | boolean-lit | nil-lit | float-lit | integer-lit | string-lit - | bind-slot | keyword | op-sym | variable | plain-sym | edn-list - | edn-vector | edn-map +edn-value ::= set-lit | uuid-lit | boolean-lit | nil-lit | float-lit | integer-lit + | string-lit | bind-slot | keyword | op-sym | variable | plain-sym + | edn-list | edn-vector | edn-map edn-list ::= "(" edn-value* ")" edn-vector ::= "[" edn-value* "]" edn-map ::= "{" (edn-value edn-value)* "}" @@ -106,8 +109,8 @@ 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 *) -expr-arg ::= expr | boolean-lit | nil-lit | float-lit | integer-lit | string-lit - | bind-slot | keyword | variable +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/src/browser/mod.rs b/src/browser/mod.rs index df063a45b9..9847b26d61 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -530,6 +530,7 @@ fn value_to_json(v: &crate::graph::types::Value) -> serde_json::Value { Value::Ref(uuid) => JVal::String(uuid.to_string()), Value::Keyword(k) => JVal::String(k.clone()), Value::Null => JVal::Null, + Value::Set(s) => JVal::Array(s.iter().map(value_to_json).collect()), } } diff --git a/src/error.rs b/src/error.rs index 57a5d4294a..85664655f7 100644 --- a/src/error.rs +++ b/src/error.rs @@ -161,6 +161,9 @@ pub(crate) enum ErrorCode { Prs112, Prs113, Prs114, + Prs119, + Prs120, + Prs121, Qry001, Qry002, Qry003, @@ -258,6 +261,7 @@ pub(crate) enum ErrorCode { Api018, Api019, Api020, + Api021, Int001, Int002, Int003, @@ -1005,6 +1009,24 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Rule head argument must be a variable, got {}", ErrorCategory::Parser, ), + ( + ErrorCode::Prs119, + "PRS-119", + "a set literal cannot hold a set", + ErrorCategory::Parser, + ), + ( + ErrorCode::Prs120, + "PRS-120", + "a set literal holds only strings, numbers, booleans, keywords, #uuid literals and nil; got {}", + ErrorCategory::Parser, + ), + ( + ErrorCode::Prs121, + "PRS-121", + "Unterminated set: missing '}'", + ErrorCategory::Parser, + ), ( ErrorCode::Qry001, "QRY-001", @@ -1533,6 +1555,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "one transaction both asserts and retracts the same value of {}; keep only the record that decides it", ErrorCategory::Api, ), + ( + ErrorCode::Api021, + "API-021", + "a set cannot hold a set; its elements must be strings, numbers, booleans, refs, keywords or nil", + ErrorCategory::Api, + ), ( ErrorCode::Int001, "INT-001", @@ -2270,6 +2298,9 @@ mod tests { | ErrorCode::Prs112 | ErrorCode::Prs113 | ErrorCode::Prs114 + | ErrorCode::Prs119 + | ErrorCode::Prs120 + | ErrorCode::Prs121 | ErrorCode::Qry001 | ErrorCode::Qry002 | ErrorCode::Qry003 @@ -2357,6 +2388,7 @@ mod tests { | ErrorCode::Api018 | ErrorCode::Api019 | ErrorCode::Api020 + | ErrorCode::Api021 | ErrorCode::Int001 | ErrorCode::Int002 | ErrorCode::Int003 @@ -2532,6 +2564,9 @@ mod tests { ErrorCode::Prs112, ErrorCode::Prs113, ErrorCode::Prs114, + ErrorCode::Prs119, + ErrorCode::Prs120, + ErrorCode::Prs121, ErrorCode::Qry001, ErrorCode::Qry002, ErrorCode::Qry003, @@ -2619,6 +2654,7 @@ mod tests { ErrorCode::Api018, ErrorCode::Api019, ErrorCode::Api020, + ErrorCode::Api021, ErrorCode::Int001, ErrorCode::Int002, ErrorCode::Int003, diff --git a/src/graph/types.rs b/src/graph/types.rs index be25ea038a..e658cb6345 100644 --- a/src/graph/types.rs +++ b/src/graph/types.rs @@ -1,6 +1,10 @@ +use std::collections::BTreeSet; + use serde::{Deserialize, Serialize}; use uuid::Uuid; +use crate::error::{ErrorCode, MinigrafError, err_coded}; + // ============================================================================ // Datalog EAV Model (Phase 3+) // ============================================================================ @@ -65,7 +69,12 @@ pub(crate) type Attribute = String; /// | `Ref` | keyword entity or UUID | `:alice`, `#uuid "550e8400-..."` | /// | `Keyword` | colon-prefixed | `:status/active`, `:red` | /// | `Null` | `nil` | `nil` | +/// | `Set` | `#{...}` of the above | `#{:role/admin :role/editor}` | +/// +/// New variants may be added in later releases, so a `match` outside this +/// crate needs a wildcard arm. #[derive(Debug, Clone, Serialize, Deserialize, PartialEq)] +#[non_exhaustive] pub enum Value { /// A UTF-8 string. Datalog literal: `"hello"`. String(String), @@ -83,6 +92,9 @@ pub enum Value { Keyword(String), /// An absent value. Datalog literal: `nil`. Null, + /// A finite set of the values above (never of sets). Datalog literal: + /// `#{1 2 3}`. + Set(ValueSet), } impl Eq for Value {} @@ -112,6 +124,7 @@ impl std::hash::Hash for Value { Value::Ref(r) => r.hash(state), Value::Keyword(k) => k.hash(state), Value::Null => {} + Value::Set(s) => s.hash(state), } } } @@ -131,7 +144,10 @@ impl PartialOrd for Value { /// /// # Cross-Variant Ordering /// Values of different variants are ordered by discriminant: -/// - String (0) < Integer (1) < Float (2) < Boolean (3) < Ref (4) < Keyword (5) < Null (6) +/// - String (0) < Integer (1) < Float (2) < Boolean (3) < Ref (4) < Keyword (5) < Null (6) < Set (7) +/// +/// Two sets compare by their elements in this order, lexicographically; a +/// set that is a proper prefix of another is less. impl Ord for Value { fn cmp(&self, other: &Self) -> std::cmp::Ordering { // Simple variant ordering using match @@ -154,6 +170,7 @@ impl Ord for Value { (Value::Ref(a), Value::Ref(b)) => a.cmp(b), (Value::Keyword(a), Value::Keyword(b)) => a.cmp(b), (Value::Null, Value::Null) => std::cmp::Ordering::Equal, + (Value::Set(a), Value::Set(b)) => a.cmp(b), // Different variants — order by a stable integer discriminant so // the total order is deterministic and does not depend on stack // addresses (the previous implementation used pointer values here, @@ -168,6 +185,7 @@ impl Ord for Value { Value::Ref(_) => 4, Value::Keyword(_) => 5, Value::Null => 6, + Value::Set(_) => 7, } } discriminant(self).cmp(&discriminant(other)) @@ -229,6 +247,118 @@ impl Value { pub fn is_null(&self) -> bool { matches!(self, Value::Null) } + + /// Extract the set if this is a Set variant + pub fn as_set(&self) -> Option<&ValueSet> { + match self { + Value::Set(s) => Some(s), + _ => None, + } + } +} + +/// A finite set of values, none of them a set (#316). +/// +/// Two elements are the same element when [`Value`]'s `Ord` says they are +/// equal: `-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`. +/// Iteration is in `Value`'s order. +#[derive(Clone, Default, PartialOrd, Ord)] +pub struct ValueSet(BTreeSet); + +impl ValueSet { + /// The set of `values`, duplicates removed. A set among them is API-021. + pub fn new(values: impl IntoIterator) -> Result { + let mut set = BTreeSet::new(); + for v in values { + if matches!(v, Value::Set(_)) { + return Err(MinigrafError::from(err_coded!(ErrorCode::Api021))); + } + // `0.0` and `-0.0` are one element: keep `-0.0`, the least of the + // two by `value_order`, whichever came first. + let replace = match (&v, set.get(&v)) { + (Value::Float(new), Some(Value::Float(old))) => { + *new == 0.0 && new.is_sign_negative() && !old.is_sign_negative() + } + (_, Some(_)) => false, + (_, None) => true, + }; + if replace { + set.replace(v); + } + } + Ok(ValueSet(set)) + } + + /// The elements, in `Value`'s order. + pub fn iter(&self) -> impl Iterator { + self.0.iter() + } + + /// The number of elements. + pub fn len(&self) -> usize { + self.0.len() + } + + /// True when the set has no elements. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + /// True when `v` is an element. + pub fn contains(&self, v: &Value) -> bool { + self.0.contains(v) + } +} + +impl<'a> IntoIterator for &'a ValueSet { + type Item = &'a Value; + type IntoIter = std::collections::btree_set::Iter<'a, Value>; + + fn into_iter(self) -> Self::IntoIter { + self.0.iter() + } +} + +/// Equal when every element is equal under `Value`'s `Ord`, so a set holding +/// a NaN equals itself. +impl PartialEq for ValueSet { + fn eq(&self, other: &Self) -> bool { + self.cmp(other) == std::cmp::Ordering::Equal + } +} + +impl Eq for ValueSet {} + +impl std::hash::Hash for ValueSet { + fn hash(&self, state: &mut H) { + self.0.len().hash(state); + for v in &self.0 { + v.hash(state); + } + } +} + +impl std::fmt::Debug for ValueSet { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.write_str("#")?; + f.debug_set().entries(self.0.iter()).finish() + } +} + +impl Serialize for ValueSet { + fn serialize(&self, serializer: S) -> Result { + serializer.collect_seq(self.0.iter()) + } +} + +/// Read through [`ValueSet::new`], so the order is restored and a nested set +/// is an error, whatever the input. +impl<'de> Deserialize<'de> for ValueSet { + fn deserialize>(deserializer: D) -> Result { + let values = Vec::::deserialize(deserializer)?; + ValueSet::new(values).map_err(serde::de::Error::custom) + } } /// Sentinel value for open-ended valid time (a fact is valid "forever"). @@ -751,4 +881,180 @@ mod tests { "-1.0 and 1.0" ); } + + // ── ValueSet (#316) ────────────────────────────────────────────────────── + + fn set(values: Vec) -> ValueSet { + ValueSet::new(values).unwrap() + } + + #[test] + fn value_set_removes_duplicates() { + let s = set(vec![ + Value::Integer(1), + Value::Integer(1), + Value::Keyword(":a".into()), + Value::Keyword(":a".into()), + ]); + assert_eq!(s.len(), 2, "two distinct elements"); + assert!(s.contains(&Value::Integer(1)), "holds 1"); + assert!(!s.contains(&Value::Float(1.0)), "1.0 is not 1"); + } + + #[test] + fn value_set_keeps_negative_zero_whatever_the_order() { + for values in [ + vec![Value::Float(0.0), Value::Float(-0.0)], + vec![Value::Float(-0.0), Value::Float(0.0)], + ] { + let s = set(values); + assert_eq!(s.len(), 1, "one zero"); + let Some(Value::Float(z)) = s.iter().next() else { + panic!("a float element"); + }; + assert!(z.is_sign_negative(), "-0.0 is kept"); + } + } + + #[test] + fn value_set_holds_one_nan() { + let s = set(vec![ + Value::Float(f64::NAN), + Value::Float(-f64::NAN), + Value::Float(f64::NAN), + ]); + assert_eq!(s.len(), 1, "one NaN"); + assert!(s.contains(&Value::Float(f64::NAN)), "NaN is a member"); + assert_eq!(s, s.clone(), "a set holding NaN equals itself"); + } + + #[test] + fn value_set_rejects_a_set_element() { + let inner = Value::Set(ValueSet::default()); + let err = ValueSet::new(vec![Value::Integer(1), inner]).unwrap_err(); + assert_eq!(err.code(), "API-021"); + } + + #[test] + fn value_set_keyword_never_equals_ref() { + let u = Uuid::new_v5(&Uuid::NAMESPACE_OID, b":a"); + let s = set(vec![Value::Keyword(":a".into())]); + assert!(!s.contains(&Value::Ref(u)), "a ref is not the keyword"); + } + + #[test] + fn value_set_iterates_in_value_order() { + let s = set(vec![ + Value::Null, + Value::Integer(2), + Value::String("b".into()), + Value::Integer(1), + ]); + let got: Vec = s.iter().cloned().collect(); + let mut want = got.clone(); + want.sort(); + assert!(got == want, "canonical order"); + assert!( + matches!(got.first(), Some(Value::String(_))), + "strings first" + ); + } + + #[test] + fn sets_order_after_every_scalar_and_by_elements() { + let empty = Value::Set(ValueSet::default()); + for v in [ + Value::String("z".into()), + Value::Integer(i64::MAX), + Value::Null, + Value::Keyword(":z".into()), + ] { + assert_eq!(v.cmp(&empty), std::cmp::Ordering::Less, "scalar before set"); + } + let a = Value::Set(set(vec![Value::Integer(1)])); + let ab = Value::Set(set(vec![Value::Integer(1), Value::Integer(2)])); + let b = Value::Set(set(vec![Value::Integer(2)])); + assert!(empty < a && a < ab && ab < b, "lexicographic, prefix first"); + } + + #[test] + fn value_set_serde_round_trip_and_validation() { + let s = Value::Set(set(vec![ + Value::Integer(3), + Value::String("x".into()), + Value::Keyword(":k".into()), + ])); + let bytes = postcard::to_allocvec(&s).unwrap(); + let back: Value = postcard::from_bytes(&bytes).unwrap(); + assert!(back == s, "round trip"); + + // Out of order and with a duplicate: restored by `ValueSet::new`. + let raw = vec![Value::Integer(3), Value::Integer(1), Value::Integer(3)]; + let mut bytes = vec![7u8]; // variant index of `Value::Set` + bytes.extend(postcard::to_allocvec(&raw).unwrap()); + let back: Value = postcard::from_bytes(&bytes).unwrap(); + assert!( + back == Value::Set(set(vec![Value::Integer(1), Value::Integer(3)])), + "canonical after decode" + ); + + // A nested set is refused. + let nested = vec![Value::Set(ValueSet::default())]; + let mut bytes = vec![7u8]; + bytes.extend(postcard::to_allocvec(&nested).unwrap()); + assert!(postcard::from_bytes::(&bytes).is_err(), "nested set"); + } + + /// The serde variant indices of the variants before `Set` are unchanged, + /// so WAL entries written before #316 decode as before. + #[test] + fn value_serde_encoding_of_old_variants_is_unchanged() { + let cases: [(Value, &[u8]); 4] = [ + (Value::String("a".into()), &[0, 1, b'a']), + (Value::Integer(1), &[1, 2]), + (Value::Keyword(":a".into()), &[5, 2, b':', b'a']), + (Value::Null, &[6]), + ]; + for (v, want) in cases { + assert_eq!( + postcard::to_allocvec(&v).unwrap(), + want.to_vec(), + "encoding" + ); + } + } + + proptest::proptest! { + #[test] + fn value_set_ord_hash_and_eq_agree( + xs in proptest::collection::vec(scalar(), 0..6), + ys in proptest::collection::vec(scalar(), 0..6), + ) { + use std::hash::{BuildHasher, RandomState}; + let h = RandomState::new(); + let a = set(xs.clone()); + let b = set(ys); + let mut rev = xs; + rev.reverse(); + let a2 = set(rev); + proptest::prop_assert!(a == a2, "insertion order does not matter"); + proptest::prop_assert_eq!(h.hash_one(&a), h.hash_one(&a2)); + proptest::prop_assert_eq!(a.cmp(&b), b.cmp(&a).reverse()); + if a == b { + proptest::prop_assert_eq!(h.hash_one(&a), h.hash_one(&b)); + } + } + } + + fn scalar() -> impl proptest::strategy::Strategy { + use proptest::prelude::*; + prop_oneof![ + (-3i64..3).prop_map(Value::Integer), + prop_oneof![Just(0.0), Just(-0.0), Just(f64::NAN), Just(1.5)].prop_map(Value::Float), + "[ab]{0,2}".prop_map(Value::String), + "[ab]{1,2}".prop_map(|s| Value::Keyword(format!(":{s}"))), + any::().prop_map(Value::Boolean), + Just(Value::Null), + ] + } } diff --git a/src/lib.rs b/src/lib.rs index afb08236c7..3eb2f87019 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -110,7 +110,7 @@ pub use error::{ErrorCategory, MinigrafError}; pub use repl::Repl; // EAV value types — users construct and match on these -pub use graph::types::{EntityId, Value}; +pub use graph::types::{EntityId, Value, ValueSet}; // Query result types pub use cursor::{Batch, Cursor}; diff --git a/src/query/datalog/aggregate.rs b/src/query/datalog/aggregate.rs index 816d789b98..8f0419197f 100644 --- a/src/query/datalog/aggregate.rs +++ b/src/query/datalog/aggregate.rs @@ -12,7 +12,7 @@ use std::cmp::Ordering; use std::collections::{BTreeMap, BTreeSet}; /// The class of a value in [`value_order`]: numbers, strings, booleans, -/// refs, keywords, `nil`. +/// refs, keywords, `nil`, sets. fn class(v: &Value) -> u8 { match v { Value::Integer(_) | Value::Float(_) => 0, @@ -21,13 +21,16 @@ fn class(v: &Value) -> u8 { Value::Ref(_) => 3, Value::Keyword(_) => 4, Value::Null => 5, + Value::Set(_) => 6, } } /// The total order of values (spec §3.1): numbers by exact numeric value /// (an `Integer` before an equal `Float`, floats then by `f64::total_cmp`, -/// NaN after every other number), then strings, booleans, refs, keywords -/// and `nil`. `Equal` only for identical values. +/// NaN after every other number), then strings, booleans, refs, keywords, +/// `nil` and sets. Two sets compare by their elements sorted in this order, +/// lexicographically, a proper prefix first (#316). `Equal` only for +/// identical values. pub(crate) fn value_order(a: &Value, b: &Value) -> Ordering { match (a, b) { (Value::Integer(x), Value::Integer(y)) => x.cmp(y), @@ -47,6 +50,17 @@ pub(crate) fn value_order(a: &Value, b: &Value) -> Ordering { (Value::Ref(x), Value::Ref(y)) => x.as_bytes().cmp(y.as_bytes()), (Value::Keyword(x), Value::Keyword(y)) => x.cmp(y), (Value::Null, Value::Null) => Ordering::Equal, + (Value::Set(x), Value::Set(y)) => { + let mut xs: Vec<&Value> = x.iter().collect(); + let mut ys: Vec<&Value> = y.iter().collect(); + xs.sort_by(|p, q| value_order(p, q)); + ys.sort_by(|p, q| value_order(p, q)); + xs.iter() + .zip(&ys) + .map(|(p, q)| value_order(p, q)) + .find(|o| o.is_ne()) + .unwrap_or_else(|| xs.len().cmp(&ys.len())) + } _ => class(a).cmp(&class(b)), } } @@ -323,12 +337,13 @@ pub(crate) fn type_name(v: &Value) -> &'static str { Value::Ref(_) => "Ref", Value::Keyword(_) => "Keyword", Value::Null => "Null", + Value::Set(_) => "Set", } } /// Variant kinds, in `Value`'s declaration order, for `INT-043`. -const KINDS: [&str; 7] = [ - "String", "Integer", "Float", "Boolean", "Ref", "Keyword", "Null", +const KINDS: [&str; 8] = [ + "String", "Integer", "Float", "Boolean", "Ref", "Keyword", "Null", "Set", ]; fn kind(v: &Value) -> u8 { @@ -340,6 +355,7 @@ fn kind(v: &Value) -> u8 { Value::Ref(_) => 4, Value::Keyword(_) => 5, Value::Null => 6, + Value::Set(_) => 7, } } diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index e2d800bd08..6f853b1ea4 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -1,5 +1,5 @@ use super::types::EdnValue; -use crate::graph::types::{EntityId, Value}; +use crate::graph::types::{EntityId, Value, ValueSet}; use uuid::Uuid; /// Convert EdnValue to Value for storage @@ -12,6 +12,15 @@ pub fn edn_to_value(edn: &EdnValue) -> Result { EdnValue::Keyword(k) => Ok(Value::Keyword(k.clone())), EdnValue::Uuid(u) => Ok(Value::Ref(*u)), EdnValue::Nil => Ok(Value::Null), + EdnValue::Set(elements) => { + let values = elements + .iter() + .map(edn_to_value) + .collect::, String>>()?; + ValueSet::new(values) + .map(Value::Set) + .map_err(|e| e.to_string()) + } EdnValue::Symbol(s) if s.starts_with('?') => { Err(format!("Cannot convert unbound variable {} to value", s)) } diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index 6ba88dcfb1..e2ec2ffcb8 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -26,6 +26,8 @@ enum Token { Float(f64), Boolean(bool), TaggedLiteral(String), // e.g., "#uuid" + /// `#{`, which opens a set literal (#316). + SetOpen, Nil, BindSlot(String), // $identifier — named bind slot for PreparedQuery } @@ -180,6 +182,10 @@ impl<'a> Lexer<'a> { // Tagged literals (start with #) '#' => { self.bump(); + if self.peek_char() == Some('{') { + self.bump(); + return Ok(Some(Token::SetOpen)); + } let mut tag = String::new(); while let Some(ch) = self.peek_char() { if ch.is_alphanumeric() || ch == '-' { @@ -405,6 +411,7 @@ impl<'a> Parser<'a> { Some(Token::LeftParen) => self.parse_list(), Some(Token::LeftBracket) => self.parse_vector(), Some(Token::LeftBrace) => self.parse_map(), + Some(Token::SetOpen) => self.parse_set(), Some(Token::Keyword(_)) => { if let Some(Token::Keyword(k)) = self.advance() { Ok(EdnValue::Keyword(k)) @@ -486,6 +493,40 @@ impl<'a> Parser<'a> { } } + /// `#{ v* }` (#316): its elements are scalar literals; a nested set is + /// PRS-119, any other element PRS-120. + fn parse_set(&mut self) -> Result { + self.advance(); // consume #{ + let mut elements = Vec::new(); + + while let Some(token) = self.peek() { + match token { + Token::RightBrace => { + self.advance(); // consume } + return Ok(EdnValue::Set(elements)); + } + Token::SetOpen => bail_coded!(ErrorCode::Prs119), + _ => {} + } + let value = self.parse_value()?; + match value { + EdnValue::String(_) + | EdnValue::Integer(_) + | EdnValue::Float(_) + | EdnValue::Boolean(_) + | EdnValue::Keyword(_) + | EdnValue::Uuid(_) + | EdnValue::Nil => {} + other => bail_coded!(ErrorCode::Prs120, format!("{other:?}")), + } + if self.keep { + elements.push(value); + } + } + + bail_coded!(ErrorCode::Prs121); + } + fn parse_vector(&mut self) -> Result { self.advance(); // consume [ let mut elements = Vec::new(); @@ -1246,6 +1287,9 @@ fn parse_expr_arg(edn: &EdnValue) -> Result { EdnValue::Boolean(b) => Ok(Expr::Lit(Value::Boolean(*b))), EdnValue::Nil => Ok(Expr::Lit(Value::Null)), EdnValue::Keyword(k) => Ok(Expr::Lit(Value::Keyword(k.clone()))), + EdnValue::Set(_) => Ok(Expr::Lit( + super::matcher::edn_to_value(edn).map_err(|e| err_coded!(ErrorCode::Prs070, e))?, + )), EdnValue::List(inner) => parse_expr(inner), EdnValue::BindSlot(name) => Ok(Expr::Slot(name.clone())), other => { diff --git a/src/query/datalog/parser/verifier.rs b/src/query/datalog/parser/verifier.rs index 88cae239f1..1b7072eafe 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; 32] = [ +const TOKENS: [&str; 33] = [ "(", ")", "[", @@ -99,6 +99,7 @@ const TOKENS: [&str; 32] = [ "<", "$s", "#uuid \"550e8400-e29b-41d4-a716-446655440000\"", + "#{", ]; /// Bracket token → `(kind, opens)`. @@ -497,8 +498,9 @@ fn filler_counts_match_the_spec() { } n }; - assert_eq!(count(3), 18_516); - assert_eq!(count(4), 487_678); + // 33 tokens: the #643 spec's 32 and `#{` (#316). + assert_eq!(count(3), 20_686); + assert_eq!(count(4), 565_267); } #[test] diff --git a/src/query/datalog/prepared.rs b/src/query/datalog/prepared.rs index 5108230b79..a61b5c59f1 100644 --- a/src/query/datalog/prepared.rs +++ b/src/query/datalog/prepared.rs @@ -495,6 +495,7 @@ fn value_to_edn(v: &Value) -> EdnValue { Value::Keyword(k) => EdnValue::Keyword(k.clone()), Value::Ref(u) => EdnValue::Uuid(*u), Value::Null => EdnValue::Nil, + Value::Set(s) => EdnValue::Set(s.iter().map(value_to_edn).collect()), } } diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs index 531f002ca1..045037de2c 100644 --- a/src/query/datalog/types.rs +++ b/src/query/datalog/types.rs @@ -25,6 +25,8 @@ pub enum EdnValue { List(Vec), /// Map: {:key val ...} Map(Vec<(EdnValue, EdnValue)>), + /// Set: #{...} of scalar literals (#316) + Set(Vec), /// Null/nil Nil, /// A named bind slot: `$identifier`. diff --git a/src/query/engine/cell.rs b/src/query/engine/cell.rs index 532d57dc1e..d34188978c 100644 --- a/src/query/engine/cell.rs +++ b/src/query/engine/cell.rs @@ -2,7 +2,7 @@ use super::Ctx; use super::ids::IdSpace; -use crate::graph::types::Value; +use crate::graph::types::{Value, ValueSet}; use crate::storage::KeySource; use crate::storage::keys::{KeyValue, SHORT_STRING_MAX, ValueRef}; use anyhow::Result; @@ -31,12 +31,14 @@ pub(crate) enum Scalar { Str(Arc), /// A committed string over 64 bytes, by where it is stored. Long(ValueRef), + /// A set, decoded: committed sets when they are scanned (#316). + Set(Arc), } impl Cell { - /// The cell of a committed key value. - pub(crate) fn of_key(v: &KeyValue) -> Cell { - match v { + /// The cell of a committed key value. A set is decoded through `keys`. + pub(crate) fn of_key(v: &KeyValue, keys: &dyn KeySource) -> Result { + Ok(match v { KeyValue::Null => Cell::Val(Scalar::Null), KeyValue::Bool(b) => Cell::Val(Scalar::Bool(*b)), KeyValue::Int(n) => Cell::Val(Scalar::Int(*n)), @@ -45,7 +47,17 @@ impl Cell { KeyValue::LongStr { vref, .. } => Cell::Val(Scalar::Long(*vref)), KeyValue::Keyword(iid) => Cell::Iid(u64::from(*iid)), KeyValue::Ref(eid) => Cell::Eid(*eid), - } + KeyValue::Set(_) | KeyValue::LongSet { .. } => { + let set = crate::storage::keys::decode_set( + v, + |vref| keys.long_bytes(vref), + |iid| keys.ident_of(iid), + |eid| keys.uuid_of(eid), + )? + .unwrap_or_default(); + Cell::Val(Scalar::Set(Arc::new(set))) + } + }) } /// The cell of a value, with ids from `ids`. A string over 64 bytes @@ -70,6 +82,7 @@ impl Cell { Value::String(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), Value::Keyword(k) => Cell::Iid(ids.iid(keys, k)?), Value::Ref(u) => Cell::Eid(ids.eid(keys, u)?), + Value::Set(s) => Cell::Val(Scalar::Set(Arc::new(s.clone()))), }) } } @@ -88,6 +101,9 @@ pub(crate) enum JoinKey { Float(u64), Str(Arc), Long(ValueRef), + /// Sets are equal when their elements are, as `Value`'s `Ord` compares + /// them: a keyword element never equals a ref element (#316). + Set(Arc), } impl JoinKey { @@ -106,6 +122,7 @@ impl JoinKey { Cell::Val(Scalar::Float(f)) => JoinKey::Float(if *f == 0.0 { 0 } else { f.to_bits() }), Cell::Val(Scalar::Str(s)) => JoinKey::Str(s.clone()), Cell::Val(Scalar::Long(vref)) => JoinKey::Long(*vref), + Cell::Val(Scalar::Set(s)) => JoinKey::Set(s.clone()), })) } } @@ -125,6 +142,7 @@ impl JoinKey { Cell::Val(Scalar::Float(f)) => JoinKey::Float(if *f == 0.0 { 0 } else { f.to_bits() }), Cell::Val(Scalar::Str(s)) => JoinKey::Str(s.clone()), Cell::Val(Scalar::Long(vref)) => JoinKey::Long(*vref), + Cell::Val(Scalar::Set(s)) => JoinKey::Set(s.clone()), } } } diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index befb68d0ab..8de251b4b0 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -62,7 +62,7 @@ pub(crate) enum Term { /// had. #[derive(Debug, Clone)] pub(crate) enum ValueConst { - /// A string, integer, boolean or `nil`: equal values only. + /// A string, integer, boolean, `nil` or set: equal values only. Exact(Value), /// A keyword: the same keyword, or a ref to the entity it names. Keyword(String, EntityId), @@ -1451,6 +1451,10 @@ fn value_const(c: &EdnValue) -> Option { EdnValue::Keyword(k) => ValueConst::Keyword(k.clone(), edn_to_entity_id(c).ok()?), EdnValue::Uuid(u) => ValueConst::Uuid(*u), EdnValue::Float(f) => ValueConst::Float(*f), + // Equal sets only: no keyword-ref or float rule inside a set (#316). + EdnValue::Set(_) => { + ValueConst::Exact(crate::query::datalog::matcher::edn_to_value(c).ok()?) + } _ => return None, }) } diff --git a/src/query/engine/project.rs b/src/query/engine/project.rs index 6826ef0112..8eaf79f4f2 100644 --- a/src/query/engine/project.rs +++ b/src/query/engine/project.rs @@ -6,7 +6,7 @@ use super::Ctx; use super::batch::Batch; use super::cell::{Cell, Scalar}; -use crate::graph::types::Value; +use crate::graph::types::{Value, ValueSet}; use anyhow::Result; /// The rows of `batch`, with the cells of the slots `find` as values. @@ -36,6 +36,7 @@ pub(crate) fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { Cell::Val(Scalar::Int(n)) => Value::Integer(*n), Cell::Val(Scalar::Float(f)) => Value::Float(*f), Cell::Val(Scalar::Str(s)) => Value::String(s.to_string()), + Cell::Val(Scalar::Set(s)) => Value::Set(ValueSet::clone(s)), Cell::Val(Scalar::Long(vref)) => match ctx.keys { Some(k) => Value::String(k.long_value(*vref)?), None => { diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index 47c9f637b6..f842fe9732 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -263,6 +263,7 @@ fn entity<'c>( Scalar::Int(_) => "Integer", Scalar::Float(_) => "Float", Scalar::Str(_) | Scalar::Long(_) => "String", + Scalar::Set(_) => "Set", }, None => return Err(unbound("?")), }, diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index afd394665f..3008881491 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -459,7 +459,7 @@ impl Operator for Scan { } if fill(&self.spec.e, &mut row, || Ok(Cell::Eid(kf.e)))? && fill(&self.spec.a, &mut row, || Ok(Cell::Iid(u64::from(kf.a))))? - && fill(&self.spec.v, &mut row, || Ok(Cell::of_key(&kf.v)))? + && fill(&self.spec.v, &mut row, || Cell::of_key(&kf.v, keys))? { for &(m, slot) in &self.spec.meta { let n = match m { @@ -819,6 +819,28 @@ fn key_value(keys: &dyn KeySource, value: &Value) -> Result> { Value::String(s) => keys.long_value_ref(s)?.map(|vref| keys::long_str(s, vref)), Value::Keyword(k) => keys.iid_of(k)?.map(KeyValue::Keyword), Value::Ref(u) => keys.eid_of(u)?.map(KeyValue::Ref), + // As the checkpoint's `Encoder` writes it; a keyword or ref element + // the generation does not hold means no committed key can (#316). + Value::Set(set) => { + let mut elements = Vec::with_capacity(set.len()); + for e in set { + let k = match e { + Value::String(s) => Some(KeyValue::Str(s.clone())), + e => key_value(keys, e)?, + }; + match k { + Some(k) => elements.push(k), + None => return Ok(None), + } + } + let bytes = keys::set_elements(&elements); + if bytes.len() <= SHORT_STRING_MAX { + Some(KeyValue::Set(bytes)) + } else { + keys.long_bytes_ref(&bytes)? + .map(|vref| keys::long_set(&bytes, vref)) + } + } }) } diff --git a/src/repl.rs b/src/repl.rs index 694e76f4e4..14772da39a 100644 --- a/src/repl.rs +++ b/src/repl.rs @@ -225,6 +225,10 @@ impl<'a> Repl<'a> { Value::Ref(uuid) => format!("#uuid {}", uuid), Value::Keyword(k) => k.clone(), Value::Null => "nil".to_string(), + Value::Set(s) => { + let elements: Vec = s.iter().map(Self::format_value).collect(); + format!("#{{{}}}", elements.join(" ")) + } } } } diff --git a/src/storage/dict.rs b/src/storage/dict.rs index a4c385f2c3..13a8be5ab1 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -69,7 +69,7 @@ pub struct DictReader<'a> { uuids: HashMap, names: HashMap, tx_ids: HashMap, - long_values: HashMap, + long_values: HashMap>, } impl<'a> DictReader<'a> { @@ -200,36 +200,65 @@ impl<'a> DictReader<'a> { .ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("transaction {tx_count}"))) } - pub fn long_value(&mut self, vref: ValueRef) -> Result { - if let Some(s) = self.long_values.get(&vref) { - return Ok(s.clone()); + /// The bytes of the long value at `vref`: a long string's, or a long + /// set's element encoding (#316). + pub fn long_bytes(&mut self, vref: ValueRef) -> Result> { + if let Some(b) = self.long_values.get(&vref) { + return Ok(b.clone()); } let bytes = read_value(vref, self.backend, self.cache)?; - let s = String::from_utf8(bytes).map_err(|_| { + self.long_values.insert(vref, bytes.clone()); + Ok(bytes) + } + + pub fn long_value(&mut self, vref: ValueRef) -> Result { + String::from_utf8(self.long_bytes(vref)?).map_err(|_| { err_coded!( ErrorCode::Stg036, format!("long value {}:{} not UTF-8", vref.page, vref.slot) ) - })?; - self.long_values.insert(vref, s.clone()); - Ok(s) + }) } - /// The committed long value equal to `s`, if any (§6.3 dedup). - pub fn find_long_value(&mut self, s: &str) -> Result> { + /// The committed long value with these bytes, if any (§6.3 dedup). It + /// compares bytes, so a long string and a long set never fail on each + /// other's records. + pub fn find_long_bytes(&mut self, bytes: &[u8]) -> Result> { if self.root == 0 { return Ok(None); } - let prefix = keys::dict_long_value_prefix(keys::hash64(s.as_bytes())); + let prefix = keys::dict_long_value_prefix(keys::hash64(bytes)); for (k, _) in btree::prefix_scan(self.root, &prefix, self.backend, self.cache)? { let vref = keys::dict_long_value_ref(&k)?; - if self.long_value(vref)? == s { + if self.long_bytes(vref)? == bytes { return Ok(Some(vref)); } } Ok(None) } + /// The committed long string equal to `s`, if any. + pub fn find_long_value(&mut self, s: &str) -> Result> { + self.find_long_bytes(s.as_bytes()) + } + + /// The set a committed key value holds, `None` if it is not a set. + pub fn set_of(&mut self, v: &KeyValue) -> Result> { + let long = match v { + KeyValue::LongSet { vref, .. } => Some(self.long_bytes(*vref)?), + _ => None, + }; + // `decode_set` takes three closures over one reader: read the long + // bytes first, then name the elements one lookup at a time. + let names = std::cell::RefCell::new(self); + keys::decode_set( + v, + |_| long.ok_or_else(|| err_coded!(ErrorCode::Int049, "long set without bytes")), + |iid| names.borrow_mut().name_of(iid), + |eid| names.borrow_mut().uuid_of(eid), + ) + } + /// Translate an index entry back into a fact. pub fn fact(&mut self, kf: &KeyFact) -> Result { let value = match &kf.v { @@ -241,6 +270,10 @@ impl<'a> DictReader<'a> { KeyValue::LongStr { vref, .. } => Value::String(self.long_value(*vref)?), KeyValue::Keyword(iid) => Value::Keyword(self.name_of(*iid)?), KeyValue::Ref(eid) => Value::Ref(self.uuid_of(*eid)?), + KeyValue::Set(_) | KeyValue::LongSet { .. } => Value::Set( + self.set_of(&kf.v)? + .ok_or_else(|| err_coded!(ErrorCode::Int049, "set key without a set"))?, + ), }; Ok(Fact { entity: self.uuid_of(kf.e)?, @@ -261,6 +294,22 @@ enum StagedValue { NewLong(usize), } +/// A long value this checkpoint writes: a string's bytes, or a set's element +/// encoding (#316). +struct NewLong { + bytes: Vec, + set: bool, +} + +/// The key form of a long string's or set's `bytes` stored at `vref`. +fn long_key(bytes: &[u8], set: bool, vref: ValueRef) -> KeyValue { + if set { + keys::long_set(bytes, vref) + } else { + keys::long_bytes(bytes, vref) + } +} + /// A fact with its ids assigned. struct Staged { e: u64, @@ -288,8 +337,8 @@ pub struct Encoder { eids: HashMap, iids: HashMap, txs: HashMap, - new_long: HashMap, - new_values: Vec, + new_long: HashMap, usize>, + new_values: Vec, dict: Vec, staged: Vec, } @@ -380,27 +429,54 @@ impl Encoder { Value::Integer(n) => KeyValue::Int(*n), Value::Float(f) => KeyValue::Float(*f), Value::String(s) if s.len() <= SHORT_STRING_MAX => KeyValue::Str(s.clone()), - Value::String(s) => { - if s.len() > keys::MAX_VALUE_BYTES { - bail_coded!(ErrorCode::Wal003, s.len(), keys::MAX_VALUE_BYTES); - } - if let Some(i) = self.new_long.get(s) { - return Ok(StagedValue::NewLong(*i)); + Value::String(s) => return self.long(s.as_bytes(), false, dict), + Value::Keyword(k) => KeyValue::Keyword(self.iid(k, dict)?), + Value::Ref(u) => KeyValue::Ref(self.eid(*u, dict)?), + Value::Set(set) => { + let mut elements = Vec::with_capacity(set.len()); + for e in set { + elements.push(match e { + // A string element is written in full, whatever its length. + Value::String(s) => KeyValue::Str(s.clone()), + e => match self.value(e, dict)? { + StagedValue::Ready(k) => k, + StagedValue::NewLong(_) => { + bail_coded!(ErrorCode::Int049, "set element staged as long") + } + }, + }); } - if let Some(vref) = dict.find_long_value(s)? { - keys::long_str(s, vref) + let bytes = keys::set_elements(&elements); + if bytes.len() <= SHORT_STRING_MAX { + KeyValue::Set(bytes) } else { - let i = self.new_values.len(); - self.new_values.push(s.clone()); - self.new_long.insert(s.clone(), i); - return Ok(StagedValue::NewLong(i)); + return self.long(&bytes, true, dict); } } - Value::Keyword(k) => KeyValue::Keyword(self.iid(k, dict)?), - Value::Ref(u) => KeyValue::Ref(self.eid(*u, dict)?), })) } + /// The staged form of a long value: an existing record's ref, or a new + /// record written by [`Encoder::finish`]. + fn long(&mut self, bytes: &[u8], set: bool, dict: &mut DictReader<'_>) -> Result { + if bytes.len() > keys::MAX_VALUE_BYTES { + bail_coded!(ErrorCode::Wal003, bytes.len(), keys::MAX_VALUE_BYTES); + } + if let Some(i) = self.new_long.get(bytes) { + return Ok(StagedValue::NewLong(*i)); + } + if let Some(vref) = dict.find_long_bytes(bytes)? { + return Ok(StagedValue::Ready(long_key(bytes, set, vref))); + } + let i = self.new_values.len(); + self.new_values.push(NewLong { + bytes: bytes.to_vec(), + set, + }); + self.new_long.insert(bytes.to_vec(), i); + Ok(StagedValue::NewLong(i)) + } + /// Assign ids for `fact`, reading the committed dictionary. pub fn stage(&mut self, fact: &Fact, dict: &mut DictReader<'_>) -> Result<()> { let e = self.eid(fact.entity, dict)?; @@ -428,13 +504,13 @@ impl Encoder { ) -> Result { let mut writer = ValueWriter::new(); let mut new_refs = Vec::with_capacity(self.new_values.len()); - for s in &self.new_values { - let vref = writer.push(s.as_bytes(), alloc, backend, cache)?; + for v in &self.new_values { + let vref = writer.push(&v.bytes, alloc, backend, cache)?; self.dict.push(( - keys::dict_long_value_key(keys::hash64(s.as_bytes()), vref), + keys::dict_long_value_key(keys::hash64(&v.bytes), vref), Vec::new(), )); - new_refs.push(keys::long_str(s, vref)); + new_refs.push(long_key(&v.bytes, v.set, vref)); } writer.flush(alloc, backend, cache)?; diff --git a/src/storage/index.rs b/src/storage/index.rs index 7cd7673cdd..79e595b7a9 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -78,6 +78,18 @@ pub fn encode_value(v: &Value) -> Vec { bytes.extend_from_slice(id.as_bytes()); bytes } + // Each element's length keeps the boundaries, so equal encodings + // mean equal elements, one by one (#316). + Value::Set(set) => { + let mut bytes = vec![0x07]; + for e in set { + let enc = encode_value(e); + let len = u32::try_from(enc.len()).unwrap_or(u32::MAX); + bytes.extend_from_slice(&len.to_be_bytes()); + bytes.extend_from_slice(&enc); + } + bytes + } } } diff --git a/src/storage/keys.rs b/src/storage/keys.rs index b37787a7ab..427614b47b 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -221,7 +221,7 @@ pub fn put_valid_to(out: &mut Vec, vt: i64) { // ─── Values (§6.2) ─────────────────────────────────────────────────────────── /// Value type tags, in the cross-type order Null < Boolean < Integer < Float < -/// String < Keyword < Ref. +/// String < Keyword < Ref < Set. const TAG_NULL: u8 = 0x01; const TAG_BOOL: u8 = 0x02; const TAG_INT: u8 = 0x03; @@ -229,6 +229,7 @@ const TAG_FLOAT: u8 = 0x04; const TAG_STRING: u8 = 0x05; const TAG_KEYWORD: u8 = 0x06; const TAG_REF: u8 = 0x07; +const TAG_SET: u8 = 0x08; /// Where a long string is stored: a record in a value page (§6.3). #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] @@ -254,6 +255,15 @@ pub enum KeyValue { }, Keyword(u32), Ref(u64), + /// A set whose element encoding ([`set_elements`]) is at most + /// [`SHORT_STRING_MAX`] bytes: that encoding (#316). + Set(Vec), + /// A set with a longer element encoding, by where it is stored. + LongSet { + prefix: Vec, + hash: u64, + vref: ValueRef, + }, } /// The order-preserving bit transform for floats, with NaN canonicalised. @@ -335,12 +345,139 @@ pub fn put_value(out: &mut Vec, v: &KeyValue) { out.push(TAG_REF); put_uint(out, *eid); } + KeyValue::Set(elements) => { + out.push(TAG_SET); + put_escaped(out, elements); + out.extend_from_slice(&[0x00, 0x00]); + } + KeyValue::LongSet { prefix, hash, vref } => { + out.push(TAG_SET); + put_escaped(out, prefix); + out.extend_from_slice(&[0x00, 0x01]); + out.extend_from_slice(&hash.to_be_bytes()); + out.extend_from_slice(&vref.page.to_be_bytes()); + out.extend_from_slice(&vref.slot.to_be_bytes()); + } + } +} + +/// The element encoding of a set (#316): the key encoding of each element, +/// sorted, concatenated. Every element is a scalar, and a string is written +/// in full whatever its length. Each encoding is prefix-free (the tag fixes +/// its form, an integer or id carries its length in its type byte, a float +/// is 8 bytes, a string ends at its first unescaped `00 00`), so the bytes +/// decode back to their elements ([`set_elements_decode`]). +pub fn set_elements(elements: &[KeyValue]) -> Vec { + let mut encoded: Vec> = elements + .iter() + .map(|e| { + let mut b = Vec::new(); + put_value(&mut b, e); + b + }) + .collect(); + encoded.sort(); + encoded.dedup(); + encoded.concat() +} + +/// The elements of a set's element encoding. +pub fn set_elements_decode(bytes: &[u8]) -> Result> { + let mut r = Reader::new(bytes); + let mut out = Vec::new(); + while !r.is_empty() { + let v = r.value()?; + if matches!( + v, + KeyValue::LongStr { .. } | KeyValue::Set(_) | KeyValue::LongSet { .. } + ) { + bail_coded!(ErrorCode::Int049, "set element is not a scalar"); + } + out.push(v); + } + Ok(out) +} + +/// The key form of a set with element encoding `bytes` stored at `vref`. +pub fn long_set(bytes: &[u8], vref: ValueRef) -> KeyValue { + KeyValue::LongSet { + prefix: bytes.get(..LONG_PREFIX).unwrap_or(bytes).to_vec(), + hash: hash64(bytes), + vref, + } +} + +/// The set a committed key value holds, its keywords and refs named through +/// `ident` and `uuid`, and a long set's element encoding read through `long`. +/// `None` when `v` is not a set. +pub fn decode_set( + v: &KeyValue, + long: impl FnOnce(ValueRef) -> Result>, + mut ident: impl FnMut(u32) -> Result, + mut uuid: impl FnMut(u64) -> Result, +) -> Result> { + use crate::graph::types::{Value, ValueSet}; + let elements = match v { + KeyValue::Set(bytes) => set_elements_decode(bytes)?, + KeyValue::LongSet { vref, .. } => set_elements_decode(&long(*vref)?)?, + _ => return Ok(None), + }; + let mut values = Vec::with_capacity(elements.len()); + for e in elements { + values.push(match e { + KeyValue::Null => Value::Null, + KeyValue::Bool(b) => Value::Boolean(b), + KeyValue::Int(n) => Value::Integer(n), + KeyValue::Float(f) => Value::Float(f), + KeyValue::Str(s) => Value::String(s), + KeyValue::Keyword(iid) => Value::Keyword(ident(iid)?), + KeyValue::Ref(eid) => Value::Ref(uuid(eid)?), + // `set_elements_decode` returns scalars only. + KeyValue::LongStr { .. } | KeyValue::Set(_) | KeyValue::LongSet { .. } => { + bail_coded!(ErrorCode::Int049, "set element is not a scalar") + } + }); } + Ok(Some(ValueSet::new(values).map_err(|_| { + err_coded!(ErrorCode::Int049, "set holds a set") + })?)) +} + +/// An upper bound of the element encoding of `set` that needs no ids: each +/// keyword counted as 6 bytes and each ref as 10, their longest encodings. +/// A set the WAL takes under [`MAX_VALUE_BYTES`] by this bound always fits +/// one value page at checkpoint. +pub fn set_bytes_bound(set: &crate::graph::types::ValueSet) -> usize { + use crate::graph::types::Value; + set.iter() + .map(|v| match v { + Value::Keyword(_) => 6, + Value::Ref(_) => 10, + Value::Null => 1, + Value::Boolean(_) => 2, + Value::Float(_) => 9, + Value::Integer(n) => { + let mut b = Vec::new(); + put_int(&mut b, *n); + 1 + b.len() + } + Value::String(s) => { + let zeros = s.bytes().filter(|b| *b == 0).count(); + 1 + s.len() + zeros + 2 + } + // A set holds no set (`ValueSet::new`). + Value::Set(_) => 0, + }) + .sum() } /// The key form of a long string: its first [`LONG_PREFIX`] bytes and hash. pub fn long_str(s: &str, vref: ValueRef) -> KeyValue { - let bytes = s.as_bytes(); + long_bytes(s.as_bytes(), vref) +} + +/// The key form of a long string with UTF-8 `bytes`. +pub fn long_bytes(bytes: &[u8], vref: ValueRef) -> KeyValue { KeyValue::LongStr { prefix: bytes.get(..LONG_PREFIX).unwrap_or(bytes).to_vec(), hash: hash64(bytes), @@ -356,7 +493,17 @@ impl Reader<'_> { TAG_BOOL => KeyValue::Bool(self.byte()? != 0), TAG_INT => KeyValue::Int(self.int()?), TAG_FLOAT => KeyValue::Float(float_from_bits(self.be(8)?)), - TAG_STRING => self.string()?, + TAG_STRING => match self.escaped()? { + Escaped::Short(bytes) => KeyValue::Str( + String::from_utf8(bytes) + .map_err(|_| err_coded!(ErrorCode::Int049, "key string not UTF-8"))?, + ), + Escaped::Long { prefix, hash, vref } => KeyValue::LongStr { prefix, hash, vref }, + }, + TAG_SET => match self.escaped()? { + Escaped::Short(bytes) => KeyValue::Set(bytes), + Escaped::Long { prefix, hash, vref } => KeyValue::LongSet { prefix, hash, vref }, + }, TAG_KEYWORD => KeyValue::Keyword( u32::try_from(self.uint()?) .map_err(|_| err_coded!(ErrorCode::Int049, "iid out of range"))?, @@ -382,7 +529,7 @@ impl Reader<'_> { TAG_KEYWORD | TAG_REF => { self.uint()?; } - TAG_STRING => loop { + TAG_STRING | TAG_SET => loop { if self.byte()? != 0 { continue; } @@ -404,7 +551,9 @@ impl Reader<'_> { Ok(()) } - fn string(&mut self) -> Result { + /// The escaped bytes of a string or set, and its long-value reference + /// when it has one. + fn escaped(&mut self) -> Result { let mut bytes = Vec::new(); loop { let b = self.byte()?; @@ -414,17 +563,13 @@ impl Reader<'_> { } match self.byte()? { 0xFF => bytes.push(0), - 0x00 => { - let s = String::from_utf8(bytes) - .map_err(|_| err_coded!(ErrorCode::Int049, "key string not UTF-8"))?; - return Ok(KeyValue::Str(s)); - } + 0x00 => return Ok(Escaped::Short(bytes)), 0x01 => { let hash = self.be(8)?; let page = self.be(8)?; let slot = u16::try_from(self.be(2)?) .map_err(|_| err_coded!(ErrorCode::Int049, "slot out of range"))?; - return Ok(KeyValue::LongStr { + return Ok(Escaped::Long { prefix: bytes, hash, vref: ValueRef { page, slot }, @@ -436,6 +581,17 @@ impl Reader<'_> { } } +/// A string's or set's bytes in a key: all of them, or a prefix and where +/// the whole value is stored. +enum Escaped { + Short(Vec), + Long { + prefix: Vec, + hash: u64, + vref: ValueRef, + }, +} + // ─── Index keys (§5.2) ─────────────────────────────────────────────────────── /// The four index trees. @@ -898,6 +1054,7 @@ mod tests { KeyValue::Str(_) | KeyValue::LongStr { .. } => 4, KeyValue::Keyword(_) => 5, KeyValue::Ref(_) => 6, + KeyValue::Set(_) | KeyValue::LongSet { .. } => 7, } } diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 1f3c8b4f16..377e5a7d01 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -522,6 +522,12 @@ pub trait KeySource: Send + Sync { fn long_value(&self, vref: keys::ValueRef) -> Result; /// Where the long string `s` is stored, if a committed fact holds it. fn long_value_ref(&self, s: &str) -> Result>; + /// The bytes stored at `vref`: a long string's, or a long set's element + /// encoding (#316). + fn long_bytes(&self, vref: keys::ValueRef) -> Result>; + /// Where a long value with these bytes is stored, if a committed fact + /// holds it. + fn long_bytes_ref(&self, bytes: &[u8]) -> Result>; /// The `tx_id` of the committed transaction `tx_count`. fn tx_id_of(&self, tx_count: u64) -> Result; /// How this generation's `tx_id`s run; one walk of the DICT's diff --git a/src/storage/reader.rs b/src/storage/reader.rs index c882767979..5e096a307b 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -326,6 +326,14 @@ impl KeySource for OnDiskReader { self.dict().find_long_value(s) } + fn long_bytes(&self, vref: ValueRef) -> Result> { + self.dict().long_bytes(vref) + } + + fn long_bytes_ref(&self, bytes: &[u8]) -> Result> { + self.dict().find_long_bytes(bytes) + } + fn tx_id_of(&self, tx_count: u64) -> Result { self.dict().tx_id_of(tx_count) } diff --git a/src/storage/verify.rs b/src/storage/verify.rs index 06bfdfdfe5..b9a707b5c0 100644 --- a/src/storage/verify.rs +++ b/src/storage/verify.rs @@ -278,9 +278,26 @@ impl<'a> Walker<'a> { KeyValue::Keyword(i) => { ids.iids.insert(i); } - KeyValue::LongStr { prefix, hash, vref } => { + KeyValue::LongStr { prefix, hash, vref } + | KeyValue::LongSet { prefix, hash, vref } => { ids.long.insert(vref, (hash, prefix)); } + // An inline set's keyword and ref elements must be in + // the DICT too (#316). A long set's are checked when + // its record is read. + KeyValue::Set(bytes) => { + for e in keys::set_elements_decode(&bytes)? { + match e { + KeyValue::Ref(t) => { + ids.eids.insert(t); + } + KeyValue::Keyword(i) => { + ids.iids.insert(i); + } + _ => {} + } + } + } _ => {} } } @@ -371,17 +388,19 @@ impl<'a> Walker<'a> { .map(u64::from_be_bytes) .ok_or_else(|| bad("long-value key too short".to_string()))?; let bytes = read_value(vref, backend, cache)?; + // A long string's bytes, or a long set's element + // encoding (#316). if bytes.len() <= SHORT_STRING_MAX || keys::hash64(&bytes) != hash - || std::str::from_utf8(&bytes).is_err() + || (std::str::from_utf8(&bytes).is_err() + && keys::set_elements_decode(&bytes).is_err()) { return Err(bad(format!( "long value {}:{} does not match its entry", vref.page, vref.slot ))); } - let prefix = - keys::long_str(std::str::from_utf8(&bytes).unwrap_or_default(), vref); + let prefix = keys::long_bytes(&bytes, vref); let KeyValue::LongStr { prefix, .. } = prefix else { return Err(err_coded!(ErrorCode::Int049, "long_str shape")); }; diff --git a/src/wal.rs b/src/wal.rs index 85b3f75794..63795763de 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -31,7 +31,7 @@ use crate::graph::types::{Fact, Value}; use crate::storage::dir_sync::sync_parent_dir; #[cfg(test)] use crate::storage::fault::{self, Action, Site}; -use crate::storage::keys::{MAX_IDENT_BYTES, MAX_VALUE_BYTES}; +use crate::storage::keys::{MAX_IDENT_BYTES, MAX_VALUE_BYTES, set_bytes_bound}; use anyhow::Result; use std::fs::{File, OpenOptions}; use std::io::{self, Read, Seek, SeekFrom, Write}; @@ -143,8 +143,9 @@ fn check_wal_header_length(file: &mut File) -> Result { // ─── Entry serialization ──────────────────────────────────────────────────── /// Reject a fact a checkpoint could not store (WAL-003): a string value longer -/// than one value page's payload, or an attribute or keyword longer than an -/// ident may be (spec §6.3). +/// than one value page's payload, a set whose element encoding may be longer +/// (#316), or an attribute or keyword (a set's keyword elements too) longer +/// than an ident may be (spec §6.3). pub(crate) fn check_fact_size(fact: &Fact) -> Result<()> { if fact.attribute.len() > MAX_IDENT_BYTES { bail_coded!(ErrorCode::Wal003, fact.attribute.len(), MAX_IDENT_BYTES); @@ -156,6 +157,20 @@ pub(crate) fn check_fact_size(fact: &Fact) -> Result<()> { Value::Keyword(k) if k.len() > MAX_IDENT_BYTES => { bail_coded!(ErrorCode::Wal003, k.len(), MAX_IDENT_BYTES) } + Value::Set(set) => { + for e in set { + if let Value::Keyword(k) = e + && k.len() > MAX_IDENT_BYTES + { + bail_coded!(ErrorCode::Wal003, k.len(), MAX_IDENT_BYTES) + } + } + let n = set_bytes_bound(set); + if n > MAX_VALUE_BYTES { + bail_coded!(ErrorCode::Wal003, n, MAX_VALUE_BYTES) + } + Ok(()) + } _ => Ok(()), } } diff --git a/tests/answers/mod.rs b/tests/answers/mod.rs index 3570ecf76c..44ce56428d 100644 --- a/tests/answers/mod.rs +++ b/tests/answers/mod.rs @@ -30,6 +30,11 @@ fn key(v: &Value) -> String { Value::Ref(u) => format!("r:{}", u.as_hyphenated()), Value::Keyword(k) => format!("k:{k}"), Value::Null => "nil".to_string(), + Value::Set(s) => format!("S:{{{}}}", s.iter().map(key).collect::>().join(" ")), + // `Value` is non-exhaustive outside the crate; this file is also + // compiled inside it, where the arm is unreachable. + #[allow(unreachable_patterns)] + _ => "?".to_string(), } } diff --git a/tests/golden_corpus_test.rs b/tests/golden_corpus_test.rs index 4a323c0f38..cdc89ca2d9 100644 --- a/tests/golden_corpus_test.rs +++ b/tests/golden_corpus_test.rs @@ -42,6 +42,8 @@ fn render(v: &Value) -> String { Value::Null => "nil".to_string(), // Entity ids are not a stable output; manifests never return them. Value::Ref(_) => "#ref".to_string(), + // v7 files hold no sets (#316). + _ => "#other".to_string(), } } diff --git a/tests/grammar/grammar.pest b/tests/grammar/grammar.pest index 5622ab7612..6022dd7a23 100644 --- a/tests/grammar/grammar.pest +++ b/tests/grammar/grammar.pest @@ -55,6 +55,11 @@ string_lit = @{ "\"" ~ str_char* ~ "\"" } // Content validation (RFC 4122 format) is a semantic check — pest accepts any string. uuid_lit = { "#uuid" ~ string_lit } +// Set literal (#316): "#{" with no space inside, then scalar literals only. +// A nested set (PRS-119) and any other element (PRS-120) are syntax errors here. +set_elem = _{ uuid_lit | boolean_lit | nil_lit | float_lit | integer_lit | string_lit | keyword } +set_lit = { "#{" ~ set_elem* ~ "}" } + // Prepared-query bind slot: $name bind_slot = @{ "$" ~ (ALPHABETIC | NUMBER | "_" | "-")+ } @@ -79,7 +84,7 @@ plain_sym = @{ // ── EDN VALUE (any EDN atom or container) ───────────────────────────────── // Order matters: more specific alternatives first to avoid ambiguity. edn_value = { - uuid_lit | boolean_lit | nil_lit | float_lit | integer_lit | string_lit | + set_lit | uuid_lit | boolean_lit | nil_lit | float_lit | integer_lit | string_lit | bind_slot | keyword | op_sym | variable | plain_sym | edn_list | edn_vector | edn_map } @@ -186,7 +191,7 @@ binary_op = @{ "<" | ">" | "=" | "+" | "-" | "*" | "/" } expr_arg = { - expr | boolean_lit | nil_lit | float_lit | integer_lit | + expr | set_lit | boolean_lit | nil_lit | float_lit | integer_lit | string_lit | bind_slot | keyword | variable } diff --git a/tests/grammar/invalid/syntax/set_nested.edn b/tests/grammar/invalid/syntax/set_nested.edn new file mode 100644 index 0000000000..1b2b799c90 --- /dev/null +++ b/tests/grammar/invalid/syntax/set_nested.edn @@ -0,0 +1 @@ +(transact [[:alice :user/scopes #{#{:scope/read}}]]) diff --git a/tests/grammar/invalid/syntax/set_space_after_hash.edn b/tests/grammar/invalid/syntax/set_space_after_hash.edn new file mode 100644 index 0000000000..60f3e7c9e0 --- /dev/null +++ b/tests/grammar/invalid/syntax/set_space_after_hash.edn @@ -0,0 +1 @@ +(transact [[:alice :user/scopes # {:scope/read}]]) diff --git a/tests/grammar/invalid/syntax/set_unterminated.edn b/tests/grammar/invalid/syntax/set_unterminated.edn new file mode 100644 index 0000000000..f5d80db5b5 --- /dev/null +++ b/tests/grammar/invalid/syntax/set_unterminated.edn @@ -0,0 +1 @@ +(transact [[:alice :user/scopes #{:scope/read]]) diff --git a/tests/grammar/invalid/syntax/set_variable_element.edn b/tests/grammar/invalid/syntax/set_variable_element.edn new file mode 100644 index 0000000000..8f79128ecc --- /dev/null +++ b/tests/grammar/invalid/syntax/set_variable_element.edn @@ -0,0 +1 @@ +(query [:find ?e :where [?e :user/scopes #{?x}]]) diff --git a/tests/grammar/valid/query_expr_set_operand.edn b/tests/grammar/valid/query_expr_set_operand.edn new file mode 100644 index 0000000000..66891dba40 --- /dev/null +++ b/tests/grammar/valid/query_expr_set_operand.edn @@ -0,0 +1,3 @@ +(query [:find ?e + :where [?e :user/scopes ?s] + [(= ?s #{:scope/read})]]) diff --git a/tests/grammar/valid/query_set_constant.edn b/tests/grammar/valid/query_set_constant.edn new file mode 100644 index 0000000000..c63e6cb726 --- /dev/null +++ b/tests/grammar/valid/query_set_constant.edn @@ -0,0 +1,2 @@ +(query [:find ?e + :where [?e :user/scopes #{:scope/write :scope/read}]]) diff --git a/tests/grammar/valid/transact_set.edn b/tests/grammar/valid/transact_set.edn new file mode 100644 index 0000000000..acfeaecf9c --- /dev/null +++ b/tests/grammar/valid/transact_set.edn @@ -0,0 +1,3 @@ +(transact [[:alice :user/scopes #{:scope/read :scope/write}] + [:bob :user/tags #{"a" 1 1.5 true nil #uuid "550e8400-e29b-41d4-a716-446655440000"}] + [:carol :user/scopes #{}]]) diff --git a/tests/live_reads_test.rs b/tests/live_reads_test.rs index fbeb4653a3..ab9c500132 100644 --- a/tests/live_reads_test.rs +++ b/tests/live_reads_test.rs @@ -23,6 +23,7 @@ fn rows(db: &Minigraf, query: &str) -> Vec { Value::Float(f) => f.to_string(), Value::Null => "nil".to_string(), Value::Ref(_) => "ref".to_string(), + _ => "other".to_string(), }) .collect::>() .join("|") diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs index 92e6f3a397..3de64e2577 100644 --- a/tests/plan_independence_test.rs +++ b/tests/plan_independence_test.rs @@ -25,6 +25,8 @@ fn key(v: &Value) -> String { Value::Ref(u) => format!("r:{}", u.as_hyphenated()), Value::Keyword(k) => format!("k:{k}"), Value::Null => "nil".to_string(), + Value::Set(s) => format!("S:{{{}}}", s.iter().map(key).collect::>().join(" ")), + _ => "?".to_string(), } } diff --git a/tests/reference_model/mod.rs b/tests/reference_model/mod.rs index afb248c660..8735b5b9b6 100644 --- a/tests/reference_model/mod.rs +++ b/tests/reference_model/mod.rs @@ -91,6 +91,14 @@ pub fn render_value(v: &Value, uuids: &HashMap) -> String { None => "r?".to_string(), }, Value::Null => "null".to_string(), + Value::Set(s) => format!( + "#{{{}}}", + s.iter() + .map(|e| render_value(e, uuids)) + .collect::>() + .join(" ") + ), + _ => "?".to_string(), } } diff --git a/tests/set_values_test.rs b/tests/set_values_test.rs new file mode 100644 index 0000000000..f1ebe89b70 --- /dev/null +++ b/tests/set_values_test.rs @@ -0,0 +1,266 @@ +//! Set values (#316): transact, query, retract and persist `#{...}`, through +//! the pending store, a checkpoint, a reopen, WAL replay, the fact log and +//! the log writer. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{FactFilter, LogWriter, 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()) +} + +/// A string element long enough that its set goes to a value page. +fn long_text() -> String { + "x".repeat(100) +} + +const FACTS: &str = r#"(transact [[:alice :user/scopes #{:scope/write :scope/read :scope/read}] + [:bob :user/scopes #{}] + [:carol :user/tags #{1 1.5 "a" true nil -0.0 0.0}] + [:dave :user/notes #{"LONG" :k/a 7}] + [:erin :user/friends #{:alice :bob}]])"#; + +fn load(db: &Minigraf) { + db.execute(&FACTS.replace("LONG", &long_text())).unwrap(); +} + +/// Every check, on whatever state `db` is in. +fn check(db: &Minigraf, phase: &str) { + let alice = rows(db, "(query [:find ?s :where [:alice :user/scopes ?s]])"); + assert_eq!(alice.len(), 1, "{phase}: one alice set"); + assert!( + alice[0][0] == set(vec![kw(":scope/read"), kw(":scope/write")]), + "{phase}: alice's set, duplicates removed" + ); + + let bob = rows(db, "(query [:find ?s :where [:bob :user/scopes ?s]])"); + assert!(bob[0][0] == set(vec![]), "{phase}: empty set"); + + let carol = rows(db, "(query [:find ?s :where [:carol :user/tags ?s]])"); + let Value::Set(tags) = &carol[0][0] else { + panic!("{phase}: carol's tags are a set"); + }; + assert_eq!(tags.len(), 6, "{phase}: 0.0 and -0.0 are one element"); + let zero = tags + .iter() + .find_map(|v| match v { + Value::Float(f) if *f == 0.0 => Some(*f), + _ => None, + }) + .expect("a zero"); + assert!(zero.is_sign_negative(), "{phase}: -0.0 is kept"); + + let dave = rows(db, "(query [:find ?s :where [:dave :user/notes ?s]])"); + assert!( + dave[0][0] + == set(vec![ + Value::String(long_text()), + kw(":k/a"), + Value::Integer(7) + ]), + "{phase}: long set with a long string element" + ); + + let erin = rows(db, "(query [:find ?s :where [:erin :user/friends ?s]])"); + assert!( + erin[0][0] == set(vec![kw(":alice"), kw(":bob")]), + "{phase}: keyword elements stay keywords" + ); + + // A set constant in a pattern matches the equal set, in any order. + let by_value = rows( + db, + "(query [:find ?e :where [?e :user/scopes #{:scope/write :scope/read}]])", + ); + assert_eq!(by_value.len(), 1, "{phase}: alice by her set"); + let empty = rows(db, "(query [:find ?e :where [?e :user/scopes #{}]])"); + assert_eq!(empty.len(), 1, "{phase}: bob by the empty set"); + let long = rows( + db, + &format!( + r#"(query [:find ?e :where [?e :user/notes #{{7 :k/a "{}"}}]])"#, + long_text() + ), + ); + assert_eq!(long.len(), 1, "{phase}: dave by his long set"); + let none = rows( + db, + "(query [:find ?e :where [?e :user/scopes #{:scope/read}]])", + ); + assert!(none.is_empty(), "{phase}: a subset is not equal"); + let unknown = rows( + db, + "(query [:find ?e :where [?e :user/scopes #{:scope/never-stored}]])", + ); + assert!(unknown.is_empty(), "{phase}: an element no fact holds"); + + // A join on a set column, and `=` between sets. + let same = rows( + db, + "(query [:find ?a ?b :where [?a :user/scopes ?s] [?b :user/scopes ?s]])", + ); + assert_eq!(same.len(), 2, "{phase}: each set joins only itself"); + let eq = rows( + db, + "(query [:find ?e :where [?e :user/scopes ?s] [(= ?s #{:scope/read :scope/write})]])", + ); + assert_eq!(eq.len(), 1, "{phase}: = between sets"); + + // Grouping and counting by a set. + let n = rows( + db, + "(query [:find (count-distinct ?s) :where [?e :user/scopes ?s]])", + ); + assert!(n[0][0] == Value::Integer(2), "{phase}: two distinct sets"); +} + +#[test] +fn sets_in_memory() { + let db = Minigraf::in_memory().unwrap(); + load(&db); + check(&db, "memory"); +} + +#[test] +fn sets_survive_checkpoint_reopen_and_wal_replay() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("sets.graph"); + { + let db = Minigraf::open(&path).unwrap(); + load(&db); + check(&db, "pending"); + db.checkpoint().unwrap(); + check(&db, "committed"); + // The same sets again, after their ids and value page exist. + db.execute(r#"(transact [[:frank :user/scopes #{:scope/read :scope/write}]])"#) + .unwrap(); + let both = rows( + &db, + "(query [:find ?e :where [?e :user/scopes #{:scope/write :scope/read}]])", + ); + assert_eq!(both.len(), 2, "committed and pending set join"); + db.execute(r#"(retract [[:frank :user/scopes #{:scope/read :scope/write}]])"#) + .unwrap(); + } + { + let db = Minigraf::open(&path).unwrap(); + check(&db, "after WAL replay"); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + check(&db, "reopened"); + assert!(db.verify().unwrap().is_ok(), "verify is clean"); +} + +#[test] +fn retracting_a_set_value_is_exact() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :tags #{1 2}] [:a :tags #{3}]])") + .unwrap(); + db.execute("(retract [[:a :tags #{2 1}]])").unwrap(); + let left = rows(&db, "(query [:find ?s :where [:a :tags ?s]])"); + assert_eq!(left.len(), 1, "one set left"); + assert!(left[0][0] == set(vec![Value::Integer(3)]), "#{{3}} is left"); + let before = rows(&db, "(query [:find ?s :as-of 1 :where [:a :tags ?s]])"); + assert_eq!(before.len(), 2, "both before the retraction"); +} + +#[test] +fn fact_log_and_log_writer_copy_sets() { + let dir = tempfile::tempdir().unwrap(); + let src_path = dir.path().join("src.graph"); + let out = dir.path().join("out.graph"); + let src = Minigraf::open(&src_path).unwrap(); + load(&src); + src.checkpoint().unwrap(); + let records: Vec<_> = src + .fact_log(&FactFilter::new()) + .unwrap() + .collect::>() + .unwrap(); + assert!( + records.iter().all(|r| matches!(r.value, Value::Set(_))), + "every record holds a set" + ); + let mut w = LogWriter::create(&out, OpenOptions::new()).unwrap(); + for rec in &records { + w.append(rec).unwrap(); + } + w.finish().unwrap(); + let copy = Minigraf::open(&out).unwrap(); + check(©, "log writer copy"); + assert!(copy.verify().unwrap().is_ok(), "copy verifies"); +} + +#[test] +fn a_large_transaction_writes_sets() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("large.graph"); + let db = + Minigraf::open_with_options(&path, OpenOptions::new().transaction_chunk_facts(2)).unwrap(); + load(&db); + check(&db, "large transaction"); + drop(db); + let db = Minigraf::open(&path).unwrap(); + check(&db, "large transaction reopened"); +} + +#[test] +fn an_oversized_set_is_wal_003() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("big.graph")).unwrap(); + // 4,068 bytes is the limit: 80 strings of 50 bytes count 53 each. + let elements: Vec = (0..80).map(|i| format!("\"{i:050}\"")).collect(); + let err = db + .execute(&format!( + "(transact [[:a :big #{{{}}}]])", + elements.join(" ") + )) + .unwrap_err(); + assert_eq!(err.code(), "WAL-003"); + // 76 of them fit: 76 * 53 = 4,028. + let elements: Vec = (0..76).map(|i| format!("\"{i:050}\"")).collect(); + db.execute(&format!( + "(transact [[:a :big #{{{}}}]])", + elements.join(" ") + )) + .unwrap(); + db.checkpoint().unwrap(); + let back = rows(&db, "(query [:find ?s :where [:a :big ?s]])"); + let Value::Set(s) = &back[0][0] else { + panic!("a set"); + }; + assert_eq!(s.len(), 76, "every element back"); +} + +#[test] +fn set_literal_errors() { + let db = Minigraf::in_memory().unwrap(); + for (input, code) in [ + ("(transact [[:a :b #{#{1}}]])", "PRS-119"), + ("(query [:find ?e :where [?e :b #{?x}]])", "PRS-120"), + ("(transact [[:a :b #{1 [2]}]])", "PRS-120"), + ("(transact [[:a :b #{1", "PRS-121"), + ("(transact [[:a :b # {1}]])", "PRS-073"), + ] { + assert_eq!(db.execute(input).unwrap_err().code(), code, "{input}"); + } +} + +#[test] +fn a_set_is_not_an_entity_or_attribute() { + let db = Minigraf::in_memory().unwrap(); + assert!(db.execute("(transact [[#{1} :b 1]])").is_err(), "entity"); + assert!(db.execute("(transact [[:a #{1} 1]])").is_err(), "attribute"); +} diff --git a/tests/soak_test.rs b/tests/soak_test.rs index a59e40884e..9acd134789 100644 --- a/tests/soak_test.rs +++ b/tests/soak_test.rs @@ -138,6 +138,14 @@ fn render_value(v: &Value, names: &HashMap) -> String { Value::Boolean(b) => format!("b{b}"), Value::Float(f) => format!("f{f}"), Value::Null => "null".to_string(), + Value::Set(s) => format!( + "#{{{}}}", + s.iter() + .map(|e| render_value(e, names)) + .collect::>() + .join(" ") + ), + _ => "?".to_string(), } } From 09b80ee74b63e99d1a392027dcbd16a8b2af8820 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 13:41:35 +0530 Subject: [PATCH 3/5] test(values): set values unit, integration and model tests; docs (#316) Set constants with a zero element probe both zero signs, committed or pending, and in value joins. Kani: a set_elements harness used 100 GB and did not finish, so the keys unit tests cover set encodings. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF --- CHANGELOG.md | 2 + CLAUDE.md | 11 ++- docs/TEST_COVERAGE.md | 5 +- src/browser/mod.rs | 19 +++++ src/graph/types.rs | 3 + src/query/datalog/aggregate/tests.rs | 32 ++++++++ src/query/datalog/parser.rs | 43 ++++++++++ src/query/engine/scan.rs | 42 +++++++++- src/repl.rs | 13 +++ src/storage/dict.rs | 78 ++++++++++++++++++ src/storage/index.rs | 27 +++++++ src/storage/keys.rs | 115 +++++++++++++++++++++++++++ src/storage/keys/verification.rs | 4 +- tests/reference_model/mod.rs | 43 ++++++++-- tests/set_values_test.rs | 84 +++++++++++++++++++ 15 files changed, 505 insertions(+), 16 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 3ca142f693..d821b01122 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,6 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Breaking changes +- **`Value` is `#[non_exhaustive]` and has a `Set` variant** (#316). A `match` on `Value` outside the crate needs a wildcard arm, so later value kinds are not breaking changes. - **File format v8** (#287, #371). Index keys now include the encoded value and the assert/retract flag. A v7 file (written by v2.x) is re-indexed and upgraded to v8 the first time it is opened; the upgrade is one-way and v2.x cannot open a v8 file (`STG-006`). Bindings users get this upgrade silently on open. - **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`. - **Covering indexes with dictionary-coded keys** (v8 storage format, PR 3 of 5; #433). Every index entry now holds the whole fact as a byte-comparable key, so a query reads only index pages, never a separate fact page. Entities and idents (attribute names and keyword values) get sequential internal ids from a dictionary stored in the file, and strings longer than 64 bytes are stored once in value pages and deduplicated. Fact pages are gone. A file with 100,000 facts (10 attributes per entity) takes 88 bytes per fact, down from 314. Facts from committed data now come back in internal-id order (entity, then attribute) rather than insertion or UUID order; query results are sets, and code that relied on an order must sort. New codes `STG-036` (dictionary entry missing) and `STG-037` (one transaction with two timestamps: a checkpoint or v7 upgrade refuses to change a stored timestamp). Files written by a v3.0.0 development build before this change fail with `STG-032`. @@ -48,6 +49,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. - **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 671f0ae7f8..df65adc184 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -117,11 +117,11 @@ cargo run < demos/demo_negation.txt - `backend/fault_inject.rs`: `FaultInjectingBackend` — injects I/O errors for durability tests (test builds only) - `fault.rs`: thread-local fault plan (test builds only, #390) — EIO, torn/short writes, sticky ENOSPC, failed fsync with or without lost writes, at the k-th write or sync of `FileBackend`, the WAL and `sync_parent_dir`; driven by `src/fault_matrix.rs` - `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value`; `index/verification.rs`: Kani proofs of `encode_value` (`#[cfg(kani)]`, #627) - - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES`; `keys/verification.rs`: Kani proofs that the key encoders preserve order (`#[cfg(kani)]`, #627; `kani.yml` runs them on encoder PRs and nightly) + - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES`; sets (#316): tag `0x08`, element encoding (`set_elements`: each element's key encoding, sorted) inline up to 64 bytes, else `LongSet` in a value page, `decode_set`, `set_bytes_bound` (the WAL's id-free size bound); `keys/verification.rs`: Kani proofs that the key encoders preserve order (`#[cfg(kani)]`, #627; `kani.yml` runs them on encoder PRs and nightly) - `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_update` (copy-on-write inserts and deletes; an emptied leaf or node leaves its parent, an emptied tree is root 0; #550) and `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - - `value_pages.rs`: append-only value pages for strings over 64 bytes + - `value_pages.rs`: append-only value pages for strings over 64 bytes and sets whose element encoding is over 64 bytes (#316; DICT dedup compares bytes, `long_bytes`/`find_long_bytes`) - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) among the versions a `TxBound` keeps; `tx_order` (cached per reader), `last_tx_at`, `tx_runs` over the DICT's transactions (#551) - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373) - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator (skips quarantined ids), free-list chain @@ -178,8 +178,11 @@ struct Fact { asserted: bool, } +#[non_exhaustive] enum Value { String(String), Integer(i64), Float(f64), Boolean(bool), - Ref(Uuid), Keyword(String), Null } + Ref(Uuid), Keyword(String), Null, Set(ValueSet) } +// ValueSet: a BTreeSet of scalars (never a set), deduplicated by Value's Ord +// (-0.0 = 0.0 keeping -0.0, one NaN, keyword != ref); literal #{...} (#316) ``` **Important**: `tx_count` (sequential 1, 2, 3…) is what `:as-of N` compares against. The REPL displays `tx_id` (Unix ms). A single `(transact [...])` command increments `tx_count` once regardless of how many facts it contains (`transact_batch`). @@ -212,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1716 tests** (1703 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1747 tests** (1734 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/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 8de85e9b2a..83f088adb3 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,703 | 1,719 | +| **Passing** | 1,734 | 1,752 | | **Ignored** | 13 | 14 | -| **Total** | 1,716 | 1,733 | +| **Total** | 1,747 | 1,766 | **Verified**: 2026-10-24 with `cargo test --quiet`. @@ -95,6 +95,7 @@ These tests compare the database against an independent answer rather than a sin ### Format v8 pages and keys - **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. - **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/src/browser/mod.rs b/src/browser/mod.rs index 9847b26d61..5375ecf1b8 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -564,6 +564,25 @@ mod tests { } // #673: a rejection carries the same error code as the native API. + #[wasm_bindgen_test] + fn a_set_is_a_json_array_in_canonical_order() { + use crate::graph::types::{Value, ValueSet}; + let set = ValueSet::new(vec![ + Value::Integer(2), + Value::Keyword(":k".into()), + Value::String("a".into()), + ]) + .unwrap(); + assert_eq!( + value_to_json(&Value::Set(set)).to_string(), + r#"["a",2,":k"]"# + ); + assert_eq!( + value_to_json(&Value::Set(ValueSet::default())).to_string(), + "[]" + ); + } + #[wasm_bindgen_test] async fn execute_errors_carry_their_code() { let db = BrowserDb::open_in_memory().expect("open_in_memory"); diff --git a/src/graph/types.rs b/src/graph/types.rs index e658cb6345..16844568e8 100644 --- a/src/graph/types.rs +++ b/src/graph/types.rs @@ -1024,6 +1024,8 @@ mod tests { } } + // proptest is a native-only dev-dependency. + #[cfg(not(target_arch = "wasm32"))] proptest::proptest! { #[test] fn value_set_ord_hash_and_eq_agree( @@ -1046,6 +1048,7 @@ mod tests { } } + #[cfg(not(target_arch = "wasm32"))] fn scalar() -> impl proptest::strategy::Strategy { use proptest::prelude::*; prop_oneof![ diff --git a/src/query/datalog/aggregate/tests.rs b/src/query/datalog/aggregate/tests.rs index 81b94bbc54..0582fdf1e8 100644 --- a/src/query/datalog/aggregate/tests.rs +++ b/src/query/datalog/aggregate/tests.rs @@ -91,6 +91,19 @@ fn value_order_is_a_total_order() { kw(":b"), Value::Null, ]; + // Sets (#316); no zero or NaN element, whose equal sets differ in bits. + let set = |v: Vec| Value::Set(crate::graph::types::ValueSet::new(v).unwrap()); + let grid: Vec = grid + .into_iter() + .chain([ + set(vec![]), + set(vec![i(1)]), + set(vec![i(1), Value::String("a".into())]), + set(vec![f(1.5), kw(":a")]), + set(vec![i(2)]), + set(vec![Value::Null]), + ]) + .collect(); for a in &grid { for b in &grid { let ab = value_order(a, b); @@ -405,3 +418,22 @@ fn named_vars_in_find_order() { ); assert_eq!(named_vars(&find), vec!["?d"]); } + +#[test] +fn value_order_puts_sets_last_and_orders_them_by_elements() { + use crate::graph::types::ValueSet; + let set = |v: Vec| Value::Set(ValueSet::new(v).unwrap()); + let empty = set(vec![]); + for v in [i(1), f(f64::NAN), kw(":z"), Value::Null] { + assert_eq!(value_order(&v, &empty), Ordering::Less, "scalar first"); + } + // Elements sorted by value_order: 1 before "a" (numbers first), unlike + // Value's Ord (strings first). + let a = set(vec![Value::String("a".into()), i(1)]); + let b = set(vec![i(2)]); + assert_eq!(value_order(&a, &b), Ordering::Less, "1 < 2 decides"); + assert_eq!(value_order(&b, &a), Ordering::Greater, "antisymmetric"); + assert_eq!(value_order(&a, &a.clone()), Ordering::Equal, "reflexive"); + let prefix = set(vec![i(1)]); + assert_eq!(value_order(&prefix, &a), Ordering::Less, "prefix first"); +} diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs index e2ec2ffcb8..c2b24ac7f3 100644 --- a/src/query/datalog/parser.rs +++ b/src/query/datalog/parser.rs @@ -2391,6 +2391,49 @@ mod tests { ); } + #[test] + fn set_literals_parse() { + let v = + parse_edn(r#"#{1 1.5 "a" :k true nil #uuid "550e8400-e29b-41d4-a716-446655440000" 1}"#) + .unwrap(); + let EdnValue::Set(elements) = v else { + panic!("a set"); + }; + assert_eq!(elements.len(), 8, "duplicates are kept until edn_to_value"); + assert!(matches!(parse_edn("#{}").unwrap(), EdnValue::Set(e) if e.is_empty())); + assert!(matches!(parse_edn("#{,1 ,2,}").unwrap(), EdnValue::Set(e) if e.len() == 2)); + // `#uuid` right after `#{`, and `#{` right after a value. + assert!(parse_edn(r#"#{#uuid "550e8400-e29b-41d4-a716-446655440000"}"#).is_ok()); + assert!(parse_edn("[1#{2}]").is_ok()); + } + + #[test] + fn set_literal_errors_have_codes() { + let code = |s: &str| crate::MinigrafError::from(parse_edn(s).unwrap_err()).code(); + assert_eq!(code("#{#{}}"), "PRS-119"); + assert_eq!(code("#{1 #{2}}"), "PRS-119"); + for s in ["#{?x}", "#{$s}", "#{[1]}", "#{(f)}", "#{{:a 1}}", "#{foo}"] { + assert_eq!(code(s), "PRS-120", "{s}"); + } + assert_eq!(code("#{1"), "PRS-121"); + assert_eq!(code("# {1}"), "PRS-073"); + } + + #[test] + fn set_literal_in_an_expression_is_a_literal() { + let cmd = + parse_datalog_command("(query [:find ?e :where [?e :s ?s] [(= ?s #{:a :b :a})]])") + .unwrap(); + let DatalogCommand::Query(q) = cmd else { + panic!("a query"); + }; + let found = q.where_clauses.iter().any(|c| { + matches!(c, WhereClause::Expr { expr: Expr::BinOp(_, _, r), .. } + if matches!(&**r, Expr::Lit(Value::Set(s)) if s.len() == 2)) + }); + assert!(found, "the set is a literal with duplicates removed"); + } + #[test] fn test_tokenize_tagged_literal_length_limit() { let long_tag = "#".to_string() + &"x".repeat(MAX_SYMBOL_LENGTH + 1); diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 3008881491..c4dadd9443 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -17,7 +17,7 @@ use super::plan::{Meta, ScanSpec, Term, Valid, ValueConst, names}; use super::relation::Range as Rows; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::storage::PendingResume; -use crate::graph::types::{EntityId, Fact, Value}; +use crate::graph::types::{EntityId, Fact, Value, ValueSet}; use crate::storage::index::encode_value; use crate::storage::keys::{self, Index, KeyFact, KeyValue, SHORT_STRING_MAX, ValueKind}; use crate::storage::{KeySource, Scan as Range}; @@ -145,6 +145,9 @@ enum KeyTest { /// A UUID constant: its entity id; whether each keyword names it. Uuid(EntityId, Option, HashMap), Float(f64), + /// A set constant with a zero element: `0.0` and `-0.0` are one element + /// of equal sets but two keys, so either key matches (#316). + AnyOf(Vec), } impl KeyTest { @@ -164,6 +167,7 @@ impl KeyTest { } }, (KeyTest::Float(f), KeyValue::Float(ff)) => f == ff, + (KeyTest::AnyOf(cs), v) => cs.contains(v), _ => false, }) } @@ -363,10 +367,30 @@ fn candidates( } Cell::Val(Scalar::Float(f)) if f.is_nan() => Vec::new(), Cell::Val(Scalar::Float(f)) if *f == 0.0 => vec![Value::Float(*f), Value::Float(-*f)], + Cell::Val(Scalar::Set(set)) => zero_signs(set)?.into_iter().map(Value::Set).collect(), Cell::Val(_) => vec![super::project::value(cell, ctx)?], })) } +/// The forms of `set` that keys can hold: itself, and when it has a zero +/// element (at most one: `0.0` and `-0.0` are one element), the same set +/// with that zero of each sign (#316). +fn zero_signs(set: &ValueSet) -> Result> { + if !set.contains(&Value::Float(0.0)) { + return Ok(vec![set.clone()]); + } + [0.0, -0.0] + .into_iter() + .map(|zero| { + let values = set.iter().map(|e| match e { + Value::Float(f) if *f == 0.0 => Value::Float(zero), + e => e.clone(), + }); + ValueSet::new(values).map_err(anyhow::Error::from) + }) + .collect() +} + /// Whether any live committed value of attribute `a` is a keyword: read /// once per query. fn has_keywords(a: u32, ctx: &mut Ctx<'_>) -> Result { @@ -719,6 +743,12 @@ fn open( vec![(Index::Eavt, keys::entity_attribute_value_prefix(e, a, &v))], None, ), + (Some(e), Some(a), Some(KeyTest::AnyOf(vs))) => ( + vs.iter() + .map(|v| (Index::Eavt, keys::entity_attribute_value_prefix(e, a, v))) + .collect(), + None, + ), (Some(e), Some(a), t) => (vec![(Index::Eavt, keys::entity_attribute_prefix(e, a))], t), (Some(e), None, t) => (vec![(Index::Eavt, keys::entity_prefix(e))], t), (None, Some(a), Some(t)) => avet(a, t), @@ -750,6 +780,7 @@ fn avet(a: u32, t: KeyTest) -> (Vec<(Index, Vec)>, Option) { let kind = |k: ValueKind| (Index::Avet, keys::attribute_kind_prefix(a, k)); match t { KeyTest::Exact(v) => (vec![value(v)], None), + KeyTest::AnyOf(vs) => (vs.into_iter().map(value).collect(), None), KeyTest::Keyword(i, e) => { let ranges = i .map(|i| value(KeyValue::Keyword(i))) @@ -774,6 +805,15 @@ fn avet(a: u32, t: KeyTest) -> (Vec<(Index, Vec)>, Option) { /// committed key can match it. fn key_test(keys: &dyn KeySource, c: &ValueConst) -> Result> { Ok(match c { + ValueConst::Exact(Value::Set(set)) if set.contains(&Value::Float(0.0)) => { + let mut alts = Vec::with_capacity(2); + for signed in zero_signs(set)? { + if let Some(k) = key_value(keys, &Value::Set(signed))? { + alts.push(k); + } + } + (!alts.is_empty()).then_some(KeyTest::AnyOf(alts)) + } ValueConst::Exact(v) => key_value(keys, v)?.map(KeyTest::Exact), ValueConst::Keyword(k, u) => match (keys.iid_of(k)?, keys.eid_of(u)?) { (None, None) => None, diff --git a/src/repl.rs b/src/repl.rs index 14772da39a..5f57fcc069 100644 --- a/src/repl.rs +++ b/src/repl.rs @@ -512,6 +512,19 @@ mod tests { // --- Direct tests for format_value --- + #[test] + fn format_value_set() { + use crate::graph::types::{Value, ValueSet}; + let set = ValueSet::new(vec![ + Value::Integer(2), + Value::String("a".into()), + Value::Keyword(":k".into()), + ]) + .unwrap(); + assert_eq!(Repl::format_value(&Value::Set(set)), "#{\"a\" 2 :k}"); + assert_eq!(Repl::format_value(&Value::Set(ValueSet::default())), "#{}"); + } + #[test] fn format_value_string() { use crate::graph::types::Value; diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 13a8be5ab1..91712f44d2 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -774,6 +774,84 @@ mod tests { assert!(!enc2.dict.iter().any(|(k, _)| is_long_value_entry(k))); } + fn long_set_value() -> Value { + use crate::graph::types::ValueSet; + Value::Set( + ValueSet::new(vec![ + Value::String("s".repeat(80)), + Value::Keyword(":k/a".into()), + Value::Integer(9), + ]) + .unwrap(), + ) + } + + #[test] + fn long_sets_are_deduplicated_and_read_back() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(256); + let facts = vec![ + fact(1, ":s", long_set_value(), 1), + fact(2, ":s", long_set_value(), 1), + ]; + let (root, enc) = checkpoint(&mut backend, &cache, 0, (1, 1), &facts); + let pages_after_first = backend.page_count().unwrap(); + let long_entries = enc + .dict + .iter() + .filter(|(k, _)| is_long_value_entry(k)) + .count(); + assert_eq!(long_entries, 1, "one stored copy within a checkpoint"); + + let again = vec![fact(3, ":s", long_set_value(), 2)]; + let mut enc2 = Encoder::new(enc.next_eid, enc.next_iid); + { + let mut dict = DictReader::new(root, &backend, &cache); + enc2.stage(&again[0], &mut dict).unwrap(); + } + let mut alloc = PageAllocator::new(Vec::new(), pages_after_first, 2); + let enc2 = enc2.finish(&mut alloc, &mut backend, &cache).unwrap(); + assert_eq!(alloc.next_append(), pages_after_first, "no new value page"); + + // The new fact's key points at the existing record. + let (key, _) = enc2.index[0].first().expect("an EAVT entry"); + let kf = KeyFact::decode(Index::Eavt, key).unwrap(); + assert!(matches!(kf.v, KeyValue::LongSet { .. }), "a long set key"); + } + + #[test] + fn a_set_record_under_a_strings_hash_is_not_an_error() { + // A long set's record is not UTF-8. Filed under a long string's hash, + // the string lookup must skip it, not fail (#316). + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(256); + let s = "c".repeat(100); + let set_bytes = keys::set_elements(&[KeyValue::Int(1), KeyValue::Str("d".repeat(90))]); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let mut w = ValueWriter::new(); + let r_set = w + .push(&set_bytes, &mut alloc, &mut backend, &cache) + .unwrap(); + let r_str = w + .push(s.as_bytes(), &mut alloc, &mut backend, &cache) + .unwrap(); + w.flush(&mut alloc, &mut backend, &cache).unwrap(); + let h = keys::hash64(s.as_bytes()); + let mut entries = vec![ + (keys::dict_long_value_key(h, r_set), Vec::new()), + (keys::dict_long_value_key(h, r_str), Vec::new()), + ]; + entries.sort(); + let root = btree::build_btree(entries, &mut backend, &cache, &mut alloc).unwrap(); + let mut dict = DictReader::new(root, &backend, &cache); + assert_eq!(dict.find_long_value(&s).unwrap(), Some(r_str)); + assert_eq!( + dict.find_long_bytes(&set_bytes).unwrap(), + None, + "wrong hash" + ); + } + #[test] fn hash_collisions_still_find_the_right_value() { // Two DICT 0x06 entries under one hash: dedup compares full values. diff --git a/src/storage/index.rs b/src/storage/index.rs index 79e595b7a9..badb1c863f 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -220,6 +220,33 @@ mod tests { use crate::graph::types::{Fact, VALID_TIME_FOREVER, Value}; use uuid::Uuid; + #[test] + fn set_encoding_keeps_element_boundaries() { + use crate::graph::types::ValueSet; + let set = |v: Vec| encode_value(&Value::Set(ValueSet::new(v).unwrap())); + let s = |x: &str| Value::String(x.to_string()); + assert_ne!( + set(vec![s("ab")]), + set(vec![s("a"), s("b")]), + "one string vs two" + ); + assert_ne!( + set(vec![s("a")]), + set(vec![s("a"), s("")]), + "an empty element" + ); + assert_eq!( + set(vec![Value::Integer(2), Value::Integer(1)]), + set(vec![Value::Integer(1), Value::Integer(2)]), + "order does not matter" + ); + assert_ne!( + set(vec![]), + encode_value(&Value::Null), + "empty set is not nil" + ); + } + fn fact_at(entity: Uuid, attr: &str, value: Value, asserted: bool) -> Fact { let mut f = Fact::with_valid_time( entity, diff --git a/src/storage/keys.rs b/src/storage/keys.rs index 427614b47b..483adbe076 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -447,6 +447,8 @@ pub fn decode_set( /// keyword counted as 6 bytes and each ref as 10, their longest encodings. /// A set the WAL takes under [`MAX_VALUE_BYTES`] by this bound always fits /// one value page at checkpoint. +// Its one caller, the WAL, is not compiled for wasm32. +#[cfg(not(target_arch = "wasm32"))] pub fn set_bytes_bound(set: &crate::graph::types::ValueSet) -> usize { use crate::graph::types::Value; set.iter() @@ -1149,6 +1151,119 @@ mod tests { assert_eq!(Reader::new(&e).value().unwrap(), v); } + // ── Sets (#316) ────────────────────────────────────────────────────────── + + fn set_of(elements: &[KeyValue]) -> KeyValue { + let bytes = set_elements(elements); + if bytes.len() <= SHORT_STRING_MAX { + KeyValue::Set(bytes) + } else { + long_set(&bytes, ValueRef { page: 5, slot: 2 }) + } + } + + #[test] + fn sets_round_trip_inline_and_long() { + let small = vec![ + KeyValue::Int(-3), + KeyValue::Keyword(7), + KeyValue::Str("a\0b".into()), + KeyValue::Null, + KeyValue::Ref(u64::MAX), + KeyValue::Float(-0.0), + KeyValue::Bool(true), + ]; + let big = vec![KeyValue::Str("y".repeat(200)), KeyValue::Int(1)]; + for elements in [small, big, vec![]] { + let v = set_of(&elements); + let e = enc_value(&v); + let mut r = Reader::new(&e); + let back = r.value().unwrap(); + assert!(r.is_empty(), "set is self-delimiting"); + assert_eq!(back, v, "round trip"); + let mut r = Reader::new(&e); + r.skip_value().unwrap(); + assert!(r.is_empty(), "skip_value skips the whole set"); + if let KeyValue::Set(bytes) = &back { + let mut want = elements.clone(); + want.sort_by_key(enc_value); + assert_eq!(set_elements_decode(bytes).unwrap(), want, "elements back"); + } + } + } + + #[test] + fn set_element_encoding_is_independent_of_order() { + let mut rng = Rng(31); + for _ in 0..500 { + let mut elements: Vec = (0..rng.below(5)) + .map(|_| random_value(&mut rng)) + .filter(|v| !matches!(v, KeyValue::LongStr { .. })) + .collect(); + let a = set_elements(&elements); + elements.reverse(); + assert_eq!(set_elements(&elements), a, "order does not matter"); + assert!( + set_elements_decode(&a).unwrap().len() <= elements.len(), + "decodes back" + ); + } + } + + #[test] + fn sets_inline_up_to_64_element_bytes() { + // One string element of n bytes encodes as n + 3. + for (n, inline) in [(60, true), (61, true), (62, false)] { + let v = set_of(&[KeyValue::Str("z".repeat(n))]); + assert_eq!(matches!(v, KeyValue::Set(_)), inline, "{n}-byte string"); + } + } + + #[test] + fn a_long_set_holds_no_set_or_long_string_element() { + let mut nested = Vec::new(); + put_value(&mut nested, &KeyValue::Set(vec![])); + assert!(set_elements_decode(&nested).is_err(), "a set element"); + let mut long = Vec::new(); + put_value( + &mut long, + &long_str(&"q".repeat(80), ValueRef { page: 1, slot: 1 }), + ); + assert!(set_elements_decode(&long).is_err(), "a long-string element"); + } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn set_bytes_bound_covers_the_largest_ids() { + use crate::graph::types::{Value, ValueSet}; + let set = ValueSet::new(vec![ + Value::Keyword(":k".into()), + Value::Ref(Uuid::nil()), + Value::Integer(i64::MIN), + Value::Integer(5), + Value::Float(1.5), + Value::String("a\0".into()), + Value::Boolean(false), + Value::Null, + ]) + .unwrap(); + let worst = vec![ + KeyValue::Keyword(u32::MAX), + KeyValue::Ref(u64::MAX), + KeyValue::Int(i64::MIN), + KeyValue::Int(5), + KeyValue::Float(1.5), + KeyValue::Str("a\0".into()), + KeyValue::Bool(false), + KeyValue::Null, + ]; + assert_eq!( + set_bytes_bound(&set), + set_elements(&worst).len(), + "exact at the largest ids" + ); + } + #[test] fn long_strings_order_by_prefix_when_prefixes_differ() { let r = ValueRef { page: 9, slot: 1 }; diff --git a/src/storage/keys/verification.rs b/src/storage/keys/verification.rs index ac5d3a8ac0..fd0d71fb83 100644 --- a/src/storage/keys/verification.rs +++ b/src/storage/keys/verification.rs @@ -3,7 +3,9 @@ //! Each harness proves its property for every input of the given types. Only //! the encoders are covered: CBMC does not finish on the `Reader` decoders //! (their error paths build an `anyhow::Error`) or on variable-length strings, -//! so the fuzz and property tests cover those. +//! so the fuzz and property tests cover those. Set element encodings (#316) +//! are variable-length too: a harness over two integer elements used 100 GB +//! and failed at its 10-minute timeout, so the `keys` unit tests cover them. use super::*; diff --git a/tests/reference_model/mod.rs b/tests/reference_model/mod.rs index 8735b5b9b6..7df00edb2f 100644 --- a/tests/reference_model/mod.rs +++ b/tests/reference_model/mod.rs @@ -38,9 +38,21 @@ pub enum V { Float, Str(u8), Ref(usize), + /// A set of scalars (#316), deduplicated and sorted by rendering so that + /// equal sets are equal `V`s. + Set(Vec), } impl V { + /// The set of `elements`, as the engine would hold it. + pub fn set(elements: Vec) -> V { + let mut by_render: Vec<(String, V)> = + elements.into_iter().map(|e| (e.render(), e)).collect(); + by_render.sort_by(|a, b| a.0.cmp(&b.0)); + by_render.dedup_by(|a, b| a.0 == b.0); + V::Set(by_render.into_iter().map(|(_, e)| e).collect()) + } + pub fn edn(&self) -> String { match self { V::Int(n) => n.to_string(), @@ -49,6 +61,10 @@ impl V { V::Float => "1.5".to_string(), V::Str(i) => format!("\"{}\"", pool_string(*i)), V::Ref(e) => format!("#uuid \"{}\"", entity_uuid(*e)), + V::Set(es) => format!( + "#{{{}}}", + es.iter().map(V::edn).collect::>().join(" ") + ), } } @@ -60,6 +76,10 @@ impl V { V::Float => "f1.5".to_string(), V::Str(i) => render_str(&pool_string(*i)), V::Ref(e) => format!("r{e}"), + V::Set(es) => format!( + "#{{{}}}", + es.iter().map(V::render).collect::>().join(" ") + ), } } } @@ -91,13 +111,12 @@ pub fn render_value(v: &Value, uuids: &HashMap) -> String { None => "r?".to_string(), }, Value::Null => "null".to_string(), - Value::Set(s) => format!( - "#{{{}}}", - s.iter() - .map(|e| render_value(e, uuids)) - .collect::>() - .join(" ") - ), + // Sorted by rendering, as `V::set` sorts. + Value::Set(s) => { + let mut es: Vec = s.iter().map(|e| render_value(e, uuids)).collect(); + es.sort(); + format!("#{{{}}}", es.join(" ")) + } _ => "?".to_string(), } } @@ -236,7 +255,7 @@ impl Stmt { // ── Strategies ──────────────────────────────────────────────────────────────── -pub fn arb_v() -> impl Strategy { +fn arb_scalar() -> impl Strategy { prop_oneof![ 3 => (0i64..3).prop_map(V::Int), 1 => Just(V::Int(i64::MIN)), @@ -248,6 +267,14 @@ pub fn arb_v() -> impl Strategy { ] } +pub fn arb_v() -> impl Strategy { + prop_oneof![ + 13 => arb_scalar(), + // Small sets, some of them long (pool strings over 64 bytes). + 2 => prop::collection::vec(arb_scalar(), 0..4).prop_map(V::set), + ] +} + pub fn arb_window() -> impl Strategy { prop_oneof![ 3 => Just(Window::default()), diff --git a/tests/set_values_test.rs b/tests/set_values_test.rs index f1ebe89b70..6960acf858 100644 --- a/tests/set_values_test.rs +++ b/tests/set_values_test.rs @@ -264,3 +264,87 @@ fn a_set_is_not_an_entity_or_attribute() { assert!(db.execute("(transact [[#{1} :b 1]])").is_err(), "entity"); assert!(db.execute("(transact [[:a #{1} 1]])").is_err(), "attribute"); } + +/// Each set query returns the same rows with clause reordering on and off, +/// committed and pending (#596). The expected counts are checked too. +#[cfg(feature = "test-hooks")] +#[test] +fn set_queries_are_plan_independent() { + let queries: [(&str, usize); 6] = [ + ( + "(query [:find ?e :where [?e :user/scopes #{:scope/write :scope/read}]])", + 2, + ), + ( + "(query [:find ?a ?b :where [?a :user/scopes ?s] [?b :user/scopes ?s]])", + 5, + ), + ( + "(query [:find ?e ?s :where [?e :user/scopes ?s] [?f :user/friends #{:alice :bob}]])", + 3, + ), + ( + "(query [:find ?e :where [?e :user/scopes ?s] (not [?e :user/scopes #{}])])", + 2, + ), + ( + r#"(query [:find ?e :where (or [?e :user/scopes #{}] [?e :user/tags #{1 1.5 "a" true nil 0.0}])])"#, + 2, + ), + ( + "(query [:find (count ?e) ?s :where [?e :user/scopes ?s]])", + 2, + ), + ]; + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("plans.graph")).unwrap(); + load(&db); + db.checkpoint().unwrap(); + // A pending fact with the same set as a committed one. + db.execute("(transact [[:frank :user/scopes #{:scope/read :scope/write}]])") + .unwrap(); + for (q, want) in queries { + let mut bags = Vec::new(); + for reorder in [true, false] { + let _g = minigraf::__reorder(reorder); + let mut bag: Vec = rows(&db, q) + .iter() + .map(|r| { + r.iter() + .map(|v| format!("{v:?}")) + .collect::>() + .join("|") + }) + .collect(); + bag.sort(); + bags.push(bag); + } + assert_eq!(bags[0].len(), want, "row count for {q}"); + assert!(bags[0] == bags[1], "reordering on and off agree for {q}"); + } +} + +/// `#{0.0}` and `#{-0.0}` are equal sets but different keys: a constant and +/// a join find either, committed or pending, whatever the plan. +#[cfg(feature = "test-hooks")] +#[test] +fn sets_with_a_zero_of_either_sign_are_equal() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("zero.graph")).unwrap(); + db.execute("(transact [[:p :z #{-0.0 1}]])").unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:q :w #{0.0 1}]])").unwrap(); + for reorder in [true, false] { + let _g = minigraf::__reorder(reorder); + for q in [ + "(query [:find ?a :where [?a :z #{0.0 1}]])", + "(query [:find ?a :where [?a :z #{-0.0 1}]])", + "(query [:find ?a :where [?a :w #{-0.0 1}]])", + "(query [:find ?a :where [:p :z #{0.0 1}] [?a :z _]])", + "(query [:find ?a ?b :where [?a :w ?s] [?b :z ?s]])", + "(query [:find ?a ?b :where [?b :z ?s] [?a :w ?s]])", + ] { + assert_eq!(rows(&db, q).len(), 1, "reorder {reorder}: {q}"); + } + } +} From 9a3455db42509e090c854d83ddbbbaac8219de4e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 13:43:42 +0530 Subject: [PATCH 4/5] fix(storage): a long string and a long set with equal bytes keep their kinds (#316) Found by review: the checkpoint's staged long values were deduplicated by bytes with one kind per record, so the second of the two got the first's key form. The record is still shared; each reference keeps its kind. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF --- CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/storage/dict.rs | 88 +++++++++++++++++++++++++++++++------------ 3 files changed, 67 insertions(+), 27 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index df65adc184..de254d983a 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -215,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1747 tests** (1734 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1748 tests** (1735 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/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 83f088adb3..82885a1c93 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,734 | 1,752 | +| **Passing** | 1,735 | 1,753 | | **Ignored** | 13 | 14 | -| **Total** | 1,747 | 1,766 | +| **Total** | 1,748 | 1,767 | **Verified**: 2026-10-24 with `cargo test --quiet`. diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 91712f44d2..323ee968b1 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -291,14 +291,10 @@ impl<'a> DictReader<'a> { /// A value after staging: ready, or a long value still to be written. enum StagedValue { Ready(KeyValue), - NewLong(usize), -} - -/// A long value this checkpoint writes: a string's bytes, or a set's element -/// encoding (#316). -struct NewLong { - bytes: Vec, - set: bool, + /// The index of a record this checkpoint writes, and whether this value + /// is a set. A string and a set with the same bytes share the record; + /// each keeps its own kind (#316). + NewLong(usize, bool), } /// The key form of a long string's or set's `bytes` stored at `vref`. @@ -338,7 +334,9 @@ pub struct Encoder { iids: HashMap, txs: HashMap, new_long: HashMap, usize>, - new_values: Vec, + /// Long values this checkpoint writes: a string's bytes, or a set's + /// element encoding (#316). + new_values: Vec>, dict: Vec, staged: Vec, } @@ -440,7 +438,7 @@ impl Encoder { Value::String(s) => KeyValue::Str(s.clone()), e => match self.value(e, dict)? { StagedValue::Ready(k) => k, - StagedValue::NewLong(_) => { + StagedValue::NewLong(..) => { bail_coded!(ErrorCode::Int049, "set element staged as long") } }, @@ -463,18 +461,15 @@ impl Encoder { bail_coded!(ErrorCode::Wal003, bytes.len(), keys::MAX_VALUE_BYTES); } if let Some(i) = self.new_long.get(bytes) { - return Ok(StagedValue::NewLong(*i)); + return Ok(StagedValue::NewLong(*i, set)); } if let Some(vref) = dict.find_long_bytes(bytes)? { return Ok(StagedValue::Ready(long_key(bytes, set, vref))); } let i = self.new_values.len(); - self.new_values.push(NewLong { - bytes: bytes.to_vec(), - set, - }); + self.new_values.push(bytes.to_vec()); self.new_long.insert(bytes.to_vec(), i); - Ok(StagedValue::NewLong(i)) + Ok(StagedValue::NewLong(i, set)) } /// Assign ids for `fact`, reading the committed dictionary. @@ -504,13 +499,13 @@ impl Encoder { ) -> Result { let mut writer = ValueWriter::new(); let mut new_refs = Vec::with_capacity(self.new_values.len()); - for v in &self.new_values { - let vref = writer.push(&v.bytes, alloc, backend, cache)?; + for bytes in &self.new_values { + let vref = writer.push(bytes, alloc, backend, cache)?; self.dict.push(( - keys::dict_long_value_key(keys::hash64(&v.bytes), vref), + keys::dict_long_value_key(keys::hash64(bytes), vref), Vec::new(), )); - new_refs.push(long_key(&v.bytes, v.set, vref)); + new_refs.push(vref); } writer.flush(alloc, backend, cache)?; @@ -518,10 +513,10 @@ impl Encoder { for st in self.staged { let v = match st.v { StagedValue::Ready(v) => v, - StagedValue::NewLong(i) => new_refs - .get(i) - .cloned() - .ok_or_else(|| err_coded!(ErrorCode::Int049, "staged long value missing"))?, + StagedValue::NewLong(i, set) => match (new_refs.get(i), self.new_values.get(i)) { + (Some(vref), Some(bytes)) => long_key(bytes, set, *vref), + _ => bail_coded!(ErrorCode::Int049, "staged long value missing"), + }, }; let kf = KeyFact { e: st.e, @@ -819,6 +814,51 @@ mod tests { assert!(matches!(kf.v, KeyValue::LongSet { .. }), "a long set key"); } + #[test] + fn a_string_and_a_set_with_equal_bytes_keep_their_kinds() { + use crate::graph::types::ValueSet; + // A string whose bytes are a set's element encoding (NUL is UTF-8). + let elements = [KeyValue::Str("e".repeat(80))]; + let bytes = keys::set_elements(&elements); + let s = String::from_utf8(bytes.clone()).unwrap(); + let set = Value::Set(ValueSet::new(vec![Value::String("e".repeat(80))]).unwrap()); + for facts in [ + vec![ + fact(1, ":v", Value::String(s.clone()), 1), + fact(2, ":v", set.clone(), 1), + ], + vec![ + fact(2, ":v", set.clone(), 1), + fact(1, ":v", Value::String(s.clone()), 1), + ], + ] { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(256); + let (_, enc) = checkpoint(&mut backend, &cache, 0, (1, 1), &facts); + let long_entries = enc + .dict + .iter() + .filter(|(k, _)| is_long_value_entry(k)) + .count(); + assert_eq!(long_entries, 1, "one shared record"); + let kinds: Vec = enc.index[0] + .iter() + .map(|(k, _)| { + matches!( + KeyFact::decode(Index::Eavt, k).unwrap().v, + KeyValue::LongSet { .. } + ) + }) + .collect(); + assert_eq!(kinds.len(), 2, "two entries"); + assert_eq!( + kinds.iter().filter(|s| **s).count(), + 1, + "one set key, one string key" + ); + } + } + #[test] fn a_set_record_under_a_strings_hash_is_not_an_error() { // A long set's record is not UTF-8. Filed under a long string's hash, From 300ac545884860680a0e554bbb03f837a6c3b8d1 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 13:57:21 +0530 Subject: [PATCH 5/5] test(wal): set size and keyword-element checks (#316) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01TcpoiFyFeQQQELL872LfQF --- CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 4 ++-- src/wal.rs | 26 ++++++++++++++++++++++++++ 3 files changed, 29 insertions(+), 3 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index de254d983a..7c1e85cf6e 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -215,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1748 tests** (1735 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1749 tests** (1736 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/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 82885a1c93..535841937d 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,735 | 1,753 | +| **Passing** | 1,736 | 1,754 | | **Ignored** | 13 | 14 | -| **Total** | 1,748 | 1,767 | +| **Total** | 1,749 | 1,768 | **Verified**: 2026-10-24 with `cargo test --quiet`. diff --git a/src/wal.rs b/src/wal.rs index 63795763de..2cc3249c45 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -900,6 +900,32 @@ mod tests { assert_eq!(tx_counts(&path), [1, 4]); } + /// A set's size bound and its keyword elements are checked (#316). + #[test] + fn check_fact_size_checks_sets() { + use crate::graph::types::ValueSet; + let code = |v: Value| { + check_fact_size(&make_fact(Uuid::new_v4(), ":s", v, 1)) + .map_err(|e| crate::MinigrafError::from(e).code()) + }; + let set = |v: Vec| Value::Set(ValueSet::new(v).unwrap()); + // A keyword element longer than an ident may be. + let long_kw = format!(":{}", "k".repeat(MAX_IDENT_BYTES)); + assert_eq!(code(set(vec![Value::Keyword(long_kw)])), Err("WAL-003")); + // At the bound: one string element of n bytes counts n + 3. + let at = MAX_VALUE_BYTES - 3; + assert_eq!(code(set(vec![Value::String("s".repeat(at))])), Ok(())); + assert_eq!( + code(set(vec![Value::String("s".repeat(at + 1))])), + Err("WAL-003") + ); + // Short keywords and other elements pass. + assert_eq!( + code(set(vec![Value::Keyword(":a".into()), Value::Integer(1)])), + Ok(()) + ); + } + #[test] fn test_wal_rejected_entry_does_not_poison_the_writer() { let dir = tempfile::tempdir().unwrap();