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
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -51,6 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Added

- **Bounded sliding row frames** (#183). `:rows N preceding` adds a physical-row frame to window aggregates. Built-in aggregates update the frame in linear time after sorting; registered aggregates replay bounded frames unless the frame covers the whole prefix. The default peer-based frame is unchanged. New parser codes `PRS-124` and `PRS-125` report malformed frames and frames on position functions.
- **`lag` and `lead` window functions** (#182). `(lag ?value :over (:partition-by ?group :order-by ?key))` reads the previous row's value; `lead` reads the next row's. Both use the established total partition order, including named-variable tie breaks, and return `nil` at partition edges. `:desc` reverses the primary key, so the previous row has a higher or equal key. They run over grouped rows after aggregation and before `:distinct`, sorting and pagination. An optional offset or explicit default is not part of this release. The plain `(lag ?v)` and `(lead ?v)` forms remain available to registered user aggregates. `PRS-030` is deprecated and no longer emitted.
- **Optional distinct query results** (#493). A bare `:distinct` flag removes repeated final `:find` tuples after aggregates and windows and before `:order-by`, `:offset` and `:limit`. Queries still return bags by default; `:with` keeps its aggregate grouping behavior. Equality follows `count-distinct` (including one NaN and one floating zero), with canonical `-0.0`/NaN output, also inside sets. The distinct keys count toward `query_memory_limit`; ordered top-k queries still retain a key for every unique tuple they encounter.
- **Fallible and re-entrant user functions** (#180, PR 1). `Minigraf::try_register_predicate` and `Minigraf::try_register_aggregate` take closures that return `Result<_, UdfError>` (`UdfError` is exported at the crate root). A call that returns `Err` fails the query with the new `QRY-014`, ``user function `<name>` failed: <message>``, at the first failing call: it is never read as `false` or `nil`, and no later call of any user function is made for that query. `execute` and `PreparedQuery::execute` return it; a cursor treats it as any other read error, returning the rows of the batches finished before the failure, then the error, then `None`. `register_predicate` and `register_aggregate` are unchanged. A query now reads its functions from a snapshot of the registry taken when it opens, and holds no database lock while a user function runs: a function registered later is not seen by a query or cursor that is already open, and a user function may call back into its own database (query, prepare, read the fact log, write, define rules, register functions, checkpoint, verify, rebuild indexes). Its writes are not seen by the query that called it. Inside a `WriteTransaction` those calls return `INT-001` on that thread, except registration, which runs. Before, a user function that registered a function deadlocked. This is the core of UDF registration in the language bindings, which follows binding by binding.
Expand Down
8 changes: 4 additions & 4 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -135,7 +135,7 @@ cargo run < demos/demo_negation.txt
3. **`src/query/datalog/`** — Datalog engine
- `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join`; `resolve_pseudo_sources` names each per-fact pseudo-attribute's source (nearest earlier same-entity pattern, lexical scope) and its hidden metadata variable `?#<n>.<attr>`, else PRS-081 (#594)
- `parser/statement.rs`: `transact`/`retract` read one fact at a time (#550): `kind_of` dispatches on the first two tokens; one pass keeps today's error order (phases 1 tokens … 6 valid windows, the earliest phase's first error, phase 3 in today's check order); `read_statement` (pass 1) keeps at most `TX_CHUNK_FACTS` materialised facts and the offset after the last, and returns phase 5–6 errors from `Statement::facts`/`Statement::chunks` (one `Chunk` at a time; pass 2 from that offset for a larger statement); `set_tx_chunk_facts` for tests (`minigraf::__tx_chunk_facts` and `__statement_facts_high_water` under `test-hooks`). The `Parser` reads tokens on demand from a `Lexer` (`keep` off checks structure without holding it); `parse_transact`/`parse_retract` remain under `cfg(test)` for the differential tests
- `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 16 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed)
- `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 17 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed)
- `executor.rs`: `DatalogExecutor` — `transact`/`retract`/`rule` commands, and every query on the engine (`open_query`, `open_rule_query`; planner errors after the pseudo-attribute check, then every predicate the query and its rules name, `QRY-007`); its own query path is gone (#551)
- `matcher.rs`: `edn_to_value`, `edn_to_entity_id`
- `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: charged partition indices, in-place total sort, peers) (#547, #765)
Expand Down Expand Up @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1887 tests** (1873 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
**1900 tests** (1885 passing, 15 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 All @@ -227,8 +227,8 @@ See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

Current plan (see `ROADMAP.md` and the milestones):
- **v2.x** (`main`, format v7) now gets only data-integrity and security fixes as patch releases (v2.0.3 is the first); v2.0.2 was the last planned v2.x release.
- **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`.
- **v3.next** (the release after v3.0.0) holds new features (sliding row frames #183, rule persistence #241, OPFS `BrowserDb` #441).
- **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, sliding row frames #183, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`.
- **v3.next** (the release after v3.0.0) holds new features (rule persistence #241; OPFS `BrowserDb` #441).
- Known v2.x data issue: same-transaction multi-valued facts (#371). Fix ships in v3.0.0. All v2.x known issues are listed in pinned issue #421 (`known-issue` label); `data-integrity`/`corruption`/`durability` issues fixed in a v2.x patch stay open until that patch is published; issues fixed on the unreleased `v3` branch close on merge (closing keywords do not fire on `v3`, so close them with `gh issue close`) and stay listed in #421 (CONTRIBUTING.md).
- Support policy and tiers: PHILOSOPHY.md §7 and §10. v2.x gets data-integrity and security fixes for 12 months after v3.0.0. Tier 1 = Rust + Python + browser WASM (from v3.0.0); other bindings are Tier 2.

Expand Down
2 changes: 2 additions & 0 deletions README.md
Original file line number Diff line number Diff line change
Expand Up @@ -30,6 +30,8 @@ Minigraf is a **single-file embedded graph database** that lets you:

For example, `(lag ?salary :over (:partition-by ?dept :order-by ?hire-date))` reads the preceding employee's salary within each department; the first row gets `nil`. `lead` reads the following row.

The unreleased v3.0.0 branch adds bounded sliding windows such as `(avg ?salary :over (:partition-by ?dept :order-by ?hire-date :rows 2 preceding))` (#183).

**Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction.

## Why Datalog?
Expand Down
2 changes: 1 addition & 1 deletion ROADMAP.md
Original file line number Diff line number Diff line change
Expand Up @@ -95,6 +95,7 @@ Scope — query API:

- Optional `:distinct` result tuples, preserving bag output by default (#493; done on `v3`)
- `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0)
- Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182)
- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549).
- Native `:limit N`, `:order-by` and `:offset`, with a top-k `Sort` whose memory follows `N` (#306; done on `v3`, with the 10M-fact acceptance tests moved from #473; spec `docs/superpowers/specs/2026-10-24-limit-order-by-design.md`). Skipping the sort when an index already returns the rows in order is #641 (v3.next).
- Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462.
Expand Down Expand Up @@ -129,7 +130,6 @@ Scope — release-gate testing and documentation:
Additive features, kept out of v3.0.0 so the #371 fix is not held up by them:

- Rule persistence — design first (#241)
- Sliding row frames — `:rows N preceding` (#183; builds on #182)
- OPFS-backed persistent mode for `BrowserDb`: a sync access handle in a dedicated Worker, no in-memory buffer; IndexedDB stays the main-thread backend. Starts at Tier 2 inside the Tier 1 browser binding until it has shipped (#441)
- Temporal graph-traversal research (#273; may result in documentation or a blog post rather than code)

Expand Down
78 changes: 78 additions & 0 deletions benches/minigraf_bench.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1381,6 +1381,83 @@ fn bench_window(c: &mut Criterion) {
}
}

// #183: bounded row frames against the same dataset's default peer frame.
// Run with `cargo bench --bench minigraf_bench -- window_rows/`.
fn bench_window_rows(c: &mut Criterion) {
for &n in &[10_000usize, 100_000] {
// Criterion calls every bench function even when its filter skips the
// group. Build this fixture only when a window_rows case actually runs.
let db = std::sync::OnceLock::new();
let partition_len = n / 100;

for &(shape, partition_by, part_size) in &[
("one", "", n),
("hundred", ":partition-by ?p ", partition_len),
] {
let sqrt = part_size.isqrt();
let widths = [
("default", None),
("zero", Some(0)),
("two", Some(2)),
("sqrt", Some(sqrt)),
("half", Some(part_size / 2)),
("prefix", Some(part_size)),
];
for func in ["sum", "count", "min", "max", "avg", "frame_bench_sum"] {
for &(width_name, width) in &widths {
if func == "frame_bench_sum"
&& ((n == 100_000 && width_name != "prefix")
|| (n == 10_000 && !["zero", "two", "half"].contains(&width_name)))
{
continue;
}
let frame = width.map_or_else(String::new, |w| format!(":rows {w} preceding "));
let query = format!(
"(query [:find ?e ({func} ?v :over ({partition_by}:order-by ?v {frame})) \
:where [?e :val ?v] [?e :part ?p]])"
);
let mut group = c.benchmark_group("window_rows");
group.sample_size(10);
group.throughput(Throughput::Elements(u64::try_from(n).expect("row count")));
let id = format!("{n}/{shape}/{func}/{width_name}");
group.bench_function(BenchmarkId::from_parameter(id), |b| {
let db = db.get_or_init(|| {
let db = helpers::populate_in_memory(n);
// Every comparison sees the same facts, including
// the one hundred equal-sized partition labels.
for start in (0..n).step_by(100) {
let mut command = String::from("(transact [");
for row in start..(start + 100).min(n) {
command.push_str(&format!(
"[:e{row} :part {}]",
row / partition_len
));
}
command.push_str("])");
db.execute(&command).expect("partition facts");
}
db.register_aggregate(
"frame_bench_sum",
|| 0i64,
|sum, value| {
if let minigraf::Value::Integer(v) = value {
*sum += *v;
}
},
|sum, _| minigraf::Value::Integer(*sum),
)
.expect("aggregate registration");
db
});
b.iter(|| black_box(db.execute(black_box(&query)).expect("window query")));
});
group.finish();
}
}
}
}
}

// ── Temporal metadata queries ─────────────────────────────────────────────────

fn bench_temporal_metadata(c: &mut Criterion) {
Expand Down Expand Up @@ -1906,6 +1983,7 @@ criterion_group!(
bench_aggregation,
bench_expr,
bench_window,
bench_window_rows,
bench_temporal_metadata,
bench_udf,
bench_aggregation_extras,
Expand Down
Loading
Loading