Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -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`.
Expand Down Expand Up @@ -49,6 +50,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<leaf> ?b)` 43.9 s → 2.14 ms and 2.6 GiB → 4 MiB; the whole transitive closure of `:manager` 51.0 s → 3.21 s and 4.7 GiB → 318 MiB; `:as-of` with a time, a point query, 1.65 s → 0.8 ms and 435 → 4 MiB (17.2 s and 3.6 GiB → 0.9 ms and 5 MiB at 10M).
- **Transactions of any size on a file database, in bounded memory** (#473, part 8: #550). `transact` and `retract` are read one fact at a time: the whole command is never tokenized, parsed or materialised at once, and a statement reports the same error code as before whatever its size. A transaction becomes *large* when its facts would pass the new `OpenOptions::transaction_chunk_facts` (default 65,536, kept between 1 and 1,000,000): `Minigraf::execute` of a larger statement, or the `WriteTransaction` statement that takes its staged facts past it. A large transaction holds at most one chunk of facts in memory. It writes them a chunk at a time into copy-on-write trees that become the next generation, and commits as a checkpoint: no WAL entry, and the uncheckpointed facts of earlier transactions go into the same checkpoint. What a large transaction stores is what a small one stores, with two differences you can see: its `tx_id` is the time it became large, not its commit time (a default `:valid-from` takes that time too), and errors from different chunks of one statement come in chunk order. In a large `WriteTransaction` a rejected statement still leaves the transaction usable and the earlier statements' facts as they were; a fact too large to store is rejected at its statement (`WAL-003`) rather than at `commit`; a handle that has failed is refused when the transaction becomes large (`STG-046`) rather than at `commit`; and inside the transaction `:as-of` its own transaction number sees every finished statement, since they share one number (staged statements of a small transaction each have their own until `commit`). A crash at any point before a large transaction's commit leaves the database as it was; the WAL file exists, header only, from before its first page write, so a new file reopens too. The first checkpoint after a WAL is found at open, or after a large transaction is rolled back, now writes a meta page before it deletes the WAL. Measured at 1M facts against v3 before this change (one `execute`, or a `WriteTransaction` of 10 statements): peak memory above the input text goes from 1.3–2.4 GiB to at most 55 MiB at the default (under 10 MiB at 16,384); with sequential entities it is faster (3.9 s from 9.1 s for short values), with random entities about as fast for short values (9.5 s from 11.4 s in one `execute`) and slower for long ones over 10 statements (34 s from 22 s; 16,384 takes up to twice as long as the default with random entities), and a transaction of several statements over random entities can leave the file up to 1.8× larger, since each statement keeps the pages its base references until it ends; later checkpoints reuse that space.
- **Queries inside a `WriteTransaction` read through a snapshot** (#550). They no longer copy every committed and pending fact into a new list: they read the committed indexes and the pending facts, with the transaction's staged facts read with the pending ones (or, in a large transaction, its working trees), and run on the streaming engine where it plans them, counted by `query_memory_limit`.
Expand Down
11 changes: 7 additions & 4 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -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
Expand Down Expand Up @@ -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`).
Expand Down Expand Up @@ -212,7 +215,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1720 tests** (1707 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
**1753 tests** (1740 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.
Expand Down
73 changes: 72 additions & 1 deletion docs/ERROR_REFERENCE.md
Original file line number Diff line number Diff line change
Expand Up @@ -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 |
Expand Down Expand Up @@ -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 |
| API-022 | Missing bind value for slot | Database API |
| API-023 | Bind slot not permitted in attribute position | Database API |
| API-024 | Bind slot type mismatch | Database API |
Expand Down Expand Up @@ -2140,6 +2144,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,
Expand Down Expand Up @@ -2973,7 +3027,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.
Expand Down Expand Up @@ -3373,6 +3427,23 @@ let mut log = src.fact_log(&FactFilter::new())?;

**Scenario**: An offline purge copies a database migrated from v2.x through `fact_log()` and `LogWriter`, and one of its transactions retracted and re-asserted a fact.

### 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
```

---

### API-022 Missing bind value for slot

**Error text**: `missing bind value for slot '${}'`
Expand Down
Loading
Loading