diff --git a/CHANGELOG.md b/CHANGELOG.md index a473180912..1fa8a50851 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -54,6 +54,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Set values: `#{...}`** (#316, PR 1 of 3). A fact's value can be a finite set of scalars, `[:alice :user/scopes #{:scope/read :scope/write}]`, written in query text, returned as `Value::Set(ValueSet)`, transacted, retracted and queried by exact value (`[?e :user/scopes #{:scope/write :scope/read}]`), joined on and grouped by. Duplicates are removed and element order does not matter. Two elements are the same when `Value`'s order says so: `0.0` and `-0.0` are one element (`-0.0` is kept), every NaN is one element, a keyword never equals a ref and `1` never equals `1.0`. A set cannot hold a set (`ValueSet::new` fails with the new `API-021`; in query text, `PRS-119`); its elements are literals only (`PRS-120`), and an unclosed `#{` is `PRS-121`. In format v8 a set has value tag `0x08`, after refs; a set whose encoded elements take at most 64 bytes is stored in its index keys, a longer one once in a value page, as a long string is. On a file database a stored set may take up to 4,068 bytes, counting each keyword element as 6 bytes and each ref as 10 (`WAL-003`). The REPL prints sets as `#{...}` and `BrowserDb` returns them as JSON arrays, in `Value`'s order. - **Set-membership predicates** (#316, PR 2 of 3). `[(in? ?role #{:role/admin :role/owner})]` keeps rows whose value is in a set, and `not-in?`, `any-in?` (the two sets share an element), `all-in?` (every element of the first is in the second) and `none-in?` (they share none) complete the five. Each works as a filter or binds a Boolean, `[(any-in? ?scopes #{:scope/write}) ?can-write]`, and takes literal sets, set-valued attributes and bind slots (`BindValue::Val(Value::Set(..))`). Membership is set equality, as for set values: `0.0` is in `#{-0.0}`, NaN is in a set holding NaN, a keyword is not a ref. `in?` of an empty set is false and `not-in?` true; `all-in?` and `none-in?` of an empty first set are true and `any-in?` false. A set where a scalar is needed, or a scalar where a set is needed, is a type mismatch: the filter drops the row and the binding binds nothing, so `not-in?` with a non-set is never true. `contains?` stays string-only. The five names cannot be registered as functions. - **`collect-set`** (#316, PR 3 of 3). `[(collect-set ?e :user/scope) ?scopes]` binds, per row, the set of the values of `[?e :user/scope ?v]` under the query's `:as-of` and `:valid-at`, with retractions applied as for that pattern, and `#{}` when there are none (the row is kept). Combine it with the set predicates: `[(collect-set ?e :user/scope) ?s] [(in? :scope/admin ?s)]`. `?e` must be bound by an earlier clause (`INT-018`); a keyword names its entity, and a value that is no entity gives `#{}`. It works in `:where`, rule bodies, `not-join` bodies and `or` branches; when its output variable is already bound, it keeps the rows where the two sets are equal. It reads stored facts only, never a rule's derived facts. New codes: `PRS-122` (no output variable), `PRS-123` (an operand that is not a `?variable` then an attribute keyword, a bind slot included) and `QRY-015` (a value found is itself a set: bind a set-valued attribute with a pattern). The set it builds counts toward `query_memory_limit` (`QRY-012`). `collect-set` is read only as a whole clause (`PRS-067` inside another expression) and cannot be registered as a function. +- **`BrowserDb` binds sets** (#316). A prepared query's binding can be a set: `{ type: 'set', value: [1, 2] }` or a JS `Set`. Elements are plain values or typed value forms (`{ type: 'keyword', value: ':k' }`); an element that is an entity, tx count, timestamp or any-valid-time form is `API-017`, a set inside a set `API-021`. Any other element, and a plain array as a binding, is a `TypeError`, as for any value that is no bind value. - **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 a02d365051..7690afc78e 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -162,7 +162,7 @@ cargo run < demos/demo_negation.txt 8. **`src/error.rs`** — Structured error codes: `MinigrafError`, `ErrorCategory`, `ErrorCode` registry (PRS/QRY/STG/WAL/API/INT codes); must match `docs/ERROR_REFERENCE.md`. `MinigrafError::invalid_argument` (API-017) and `MinigrafError::closed` (API-018) exist for language bindings -9. **`src/browser/`** — Browser WASM backend (`browser` feature): `buffer.rs` (`BrowserBufferBackend`, in-memory pages with dirty tracking; free pages a pinned generation may read are withheld from release, `pins::split_released`), `indexeddb.rs` (IndexedDB persistence); `BrowserDb.query` returns a `BrowserCursor` (JSON row batches); `BrowserDb.prepare` returns a `BrowserPreparedQuery` (`execute`/`query` with a bindings object, read by `binds.rs`: plain JS values or `{type, value}` forms, #181). Tests here must be `#[wasm_bindgen_test]` (the module only builds for wasm32); `.github/workflows/wasm.yml` runs them in headless browsers, runs the WASI tests under Wasmtime, and lints both wasm targets. New file-backed integration test files need `#![cfg(not(target_arch = "wasm32"))]` +9. **`src/browser/`** — Browser WASM backend (`browser` feature): `buffer.rs` (`BrowserBufferBackend`, in-memory pages with dirty tracking; free pages a pinned generation may read are withheld from release, `pins::split_released`), `indexeddb.rs` (IndexedDB persistence); `BrowserDb.query` returns a `BrowserCursor` (JSON row batches); `BrowserDb.prepare` returns a `BrowserPreparedQuery` (`execute`/`query` with a bindings object, read by `binds.rs`: plain JS values or `{type, value}` forms, #181; a set as `{type: 'set', value: [..]}` or a JS `Set`, #316). Tests here must be `#[wasm_bindgen_test]` (the module only builds for wasm32); `.github/workflows/wasm.yml` runs them in headless browsers, runs the WASI tests under Wasmtime, and lints both wasm targets. New file-backed integration test files need `#![cfg(not(target_arch = "wasm32"))]` ### Data Model diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index eec18c111d..9ee7a691b9 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -455,7 +455,7 @@ These tests compare the database against an independent answer rather than a sin None of these are counted in the summary. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). -- **In a browser** (`wasm-pack test --headless`, Firefox and Chrome): 40 `wasm_bindgen_test` tests. +- **In a browser** (`wasm-pack test --headless`, Firefox and Chrome): 43 `wasm_bindgen_test` tests. - Twenty-five for `BrowserDb`, including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read (#470). - Eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before). - Two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. diff --git a/src/browser/binds.rs b/src/browser/binds.rs index ba65c7c5e9..b26859f452 100644 --- a/src/browser/binds.rs +++ b/src/browser/binds.rs @@ -14,15 +14,20 @@ //! | `{ type: 'txCount', value }` | `TxCount` (an integer `>= 0`) | //! | `{ type: 'timestamp', value }` | `Timestamp` (Unix ms) | //! | `{ type: 'anyValidTime' }` | `AnyValidTime` | +//! | `{ type: 'set', value: [..] }`, a JS `Set` | `Val(Set)` (#316) | //! -//! `null` and `anyValidTime` take no `value`. +//! `null` and `anyValidTime` take no `value`. A set's elements are plain +//! values or typed value forms (`string` … `keyword`); duplicates are dropped. //! //! Any other JavaScript value is a `TypeError`. A typed form whose value does //! not fit its type (a bad UUID, a negative tx count, an integer outside -//! `i64`) is `API-017`. +//! `i64`, a set element in an `entity`, `txCount`, `timestamp` or +//! `anyValidTime` form) is `API-017`; a set element that is a set is +//! `API-021`. A plain array is not a set, neither as a binding nor as an +//! element (`TypeError`). use crate::MinigrafError; -use crate::graph::types::Value; +use crate::graph::types::{Value, ValueSet}; use crate::query::datalog::prepared::BindValue; use js_sys::{Array, Number, Object, Reflect}; use wasm_bindgen::JsCast; @@ -66,6 +71,11 @@ fn read_bind_value(name: &str, v: &JsValue) -> Result { if v.is_bigint() || v.as_f64().is_some() { return Ok(BindValue::Val(number(name, v)?)); } + if let Some(set) = v.dyn_ref::() { + let mut elements = Vec::new(); + set.for_each(&mut |e, _, _| elements.push(e)); + return value_set(name, &format!("slot ${name}"), elements); + } if v.is_object() && !Array::is_array(v) && let Some(kind) = Reflect::get(v, &JsValue::from_str("type"))?.as_string() @@ -74,7 +84,7 @@ fn read_bind_value(name: &str, v: &JsValue) -> Result { return Ok(bind); } Err(type_error(&format!( - "slot ${name}: a bind value is a boolean, number, bigint, string, null or {{type, value}} object" + "slot ${name}: a bind value is a boolean, number, bigint, string, null, Set or {{type, value}} object" ))) } @@ -104,12 +114,34 @@ fn read_typed(name: &str, kind: &str, v: &JsValue) -> Result, } "timestamp" => BindValue::Timestamp(integer(&what(), &value)?), "anyValidTime" if value.is_undefined() => BindValue::AnyValidTime, + "set" => match value.dyn_ref::() { + Some(elements) => value_set(name, &what(), elements.iter().collect())?, + None => return Err(mismatch(&what())), + }, // These two take no value. "null" | "anyValidTime" => return Err(mismatch(&what())), _ => return Ok(None), })) } +/// The set of `elements`, each read as a bind value that must be a value. +/// Element `i` is named `$name[i]` in errors. +fn value_set(name: &str, what: &str, elements: Vec) -> Result { + let values = elements + .iter() + .enumerate() + .map( + |(i, e)| match read_bind_value(&format!("{name}[{i}]"), e)? { + BindValue::Val(v) => Ok(v), + _ => Err(invalid(&format!("{what}: element {i} is not a value"))), + }, + ) + .collect::, _>>()?; + ValueSet::new(values) + .map(|s| BindValue::Val(Value::Set(s))) + .map_err(|e| JsValue::from_str(&e.to_string())) +} + /// A plain `number` or `bigint`: an integer when it is whole, else a float. fn number(name: &str, v: &JsValue) -> Result { if v.is_bigint() || Number::is_integer(v) { diff --git a/src/browser/mod.rs b/src/browser/mod.rs index b1b4784a84..cd1c282530 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -1482,6 +1482,118 @@ mod prepared_tests { assert!(starts_with(&e, "[API-005] "), "transact is not preparable"); } + /// A JS `Set` of `elements`. + fn js_set(elements: &[JsValue]) -> JsValue { + let set = js_sys::Set::new(&JsValue::UNDEFINED); + for e in elements { + set.add(e); + } + set.into() + } + + /// A typed set `{type: 'set', value: [..]}`. + fn typed_set(elements: &[JsValue]) -> JsValue { + typed( + "set", + Some(elements.iter().collect::().into()), + ) + } + + #[wasm_bindgen_test] + async fn sets_bind_and_come_back_as_arrays() { + let db = seeded().await; + db.execute(r#"(transact [[:a :tags #{1 :k "x"}]])"#.to_string()) + .await + .expect("transact"); + let member = db + .prepare("(query [:find ?e :where [?e :n ?n] [(in? ?n $s)]])") + .expect("prepare"); + for (set, want) in [ + (typed_set(&[1.0.into(), 3.0.into()]), 2), + (typed_set(&[2.0.into(), 2.0.into()]), 1), + (js_set(&[2.0.into(), BigInt::from(3i64).into()]), 2), + (typed_set(&[]), 0), + (js_set(&[]), 0), + ] { + let r = member.execute(obj(&[("s", set)])).expect("execute"); + assert_eq!(rows(&r).len(), want, "the set's members match"); + } + + // A set binds a set-valued attribute, element types kept. + let equal = db + .prepare("(query [:find ?e :where [?e :tags $s]])") + .expect("prepare"); + let tags = || { + vec![ + typed("keyword", Some(":k".into())), + JsValue::from_f64(1.0), + JsValue::from_str("x"), + ] + }; + for set in [typed_set(&tags()), js_set(&tags())] { + let r = equal.execute(obj(&[("s", set)])).expect("execute"); + assert_eq!(rows(&r).len(), 1, "an equal set matches"); + } + let r = equal + .execute(obj(&[( + "s", + typed_set(&[":k".into(), 1.0.into(), "x".into()]), + )])) + .expect("execute"); + assert!(rows(&r).is_empty(), "the string \":k\" is no keyword"); + + let out = db + .prepare("(query [:find ?t :where [:a :tags ?t]])") + .expect("prepare"); + let r = rows(&out.execute(obj(&[])).expect("execute")); + assert_eq!( + r[0][0], + serde_json::json!(["x", 1, ":k"]), + "a set is an array in canonical order" + ); + } + + #[wasm_bindgen_test] + async fn bad_sets_are_rejected() { + let db = seeded().await; + let pq = db + .prepare("(query [:find ?e :where [?e :n ?n] [(in? ?n $s)]])") + .expect("prepare"); + for nested in [ + typed_set(&[typed_set(&[1.0.into()])]), + js_set(&[js_set(&[1.0.into()])]), + typed_set(&[js_set(&[])]), + ] { + let e = rejection(pq.execute(obj(&[("s", nested)]))); + assert!(starts_with(&e, "[API-021] "), "a set in a set is API-021"); + } + let a = uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":a").to_string(); + for bad in [ + typed_set(&[typed("entity", Some(a.as_str().into()))]), + typed_set(&[typed("anyValidTime", None)]), + typed("set", Some(JsValue::from_f64(1.0))), + typed("set", None), + ] { + let e = rejection(pq.execute(obj(&[("s", bad)]))); + assert!(starts_with(&e, "[API-017] "), "no set of values is API-017"); + } + for bad in [ + [JsValue::from_f64(1.0)] + .iter() + .collect::() + .into(), + typed_set(&[JsValue::UNDEFINED]), + typed_set(&[Object::new().into()]), + typed_set(&[[JsValue::from_f64(1.0)] + .iter() + .collect::() + .into()]), + ] { + let e = rejection(pq.execute(obj(&[("s", bad)]))); + assert!(e.is_instance_of::(), "a TypeError"); + } + } + #[wasm_bindgen_test] async fn prepared_query_sees_later_writes() { let db = seeded().await;