diff --git a/CHANGELOG.md b/CHANGELOG.md index 0fa2e4c4c0..7a7334c7ec 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -78,6 +78,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed +- **Window partition scratch obeys `query_memory_limit`** (#765). Each window now charges its partition row indices while they coexist with input rows and earlier result columns, returns `QRY-012` if reserving them fails, and releases the charge after the window or on error. An in-place total sort removes the stable sort's uncharged merge buffer; partition and row order are unchanged. - **An expression's `=` and `!=` equate a keyword with a ref to the entity it names** (#744). Patterns, joins, `not` bodies and `or` branches treat the keyword `:bob` as equal to a ref to the entity `:bob` names, but `[(= ?g :bob)]` compared the two values as they are, so with `?g` bound to that ref it kept no row and `[(!= ?g :bob)]` kept the row: the same question answered differently by how the query was written, with no error. `=` and `!=` now compare as joins do, in queries, rule bodies, `not` clauses and binding expressions, against a keyword constant, a keyword value or a bound `Val(Ref)`. A keyword still equals only the same keyword, and `<`, `>`, `<=` and `>=` on a keyword or a ref are still a type mismatch (no row). - **`checkpoint`, `verify` and `rebuild_indexes` inside a `WriteTransaction` return `INT-001` instead of deadlocking** (#734). Called on a thread that holds a `WriteTransaction`, they waited on the write lock that the transaction already held, so the thread hung. They now return `INT-001`, as `execute`, `query`, `fact_log` and `begin_write` already did, and the transaction stays usable. `prepare` and `PreparedQuery::execute`/`query` make the same check; they could not deadlock, but they ran inside the transaction where `execute`/`query` refused. `checkpoint` deadlocked in every release since `WriteTransaction` was added; the fix for it and for the prepared calls ships in v2.x too. - **A float constant in a pattern matches equal floats only** (#706). A float written in a pattern's value position, or bound to a `$slot` of a prepared query, matched every stored float within an absolute `f64::EPSILON` (about `2.2e-16`), so `[?e :m/x 0.0]` returned an entity whose `:m/x` is `1e-17`, while `[?e :m/x ?v] [(= ?v 0.0)]` did not. Above 1.0 the epsilon is smaller than the gap between adjacent floats, so only floats smaller than about `2.2e-16` in magnitude were affected: every one of them matched `0.0`, and `1e-20` matched `5e-20`. Float constants now compare by IEEE `==`, as joins, predicates and the indexes do: `0.0` matches `-0.0` and nothing else changes. The fix covers patterns in queries, rule bodies and `not` / `or` bodies, on the executor and the streaming engine. Nothing stored was wrong. The same fix ships in v2.0.10. diff --git a/CLAUDE.md b/CLAUDE.md index dd88db88cc..19230f77ab 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -138,7 +138,7 @@ cargo run < demos/demo_negation.txt - `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) - `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: partitions, sort, peers) (#547) + - `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) - `functions.rs`: `FunctionRegistry` (built-ins and UDFs; `Clone` shares the closures), `Functions` — the registry a database shares, `RwLock>`: a query takes a `snapshot()` when it opens and holds no lock while a UDF runs, so UDFs may call back into the database; registration copies, inserts and swaps (#180). `UdfError`: a `try_register_*` closure's failure, `QRY-014`; `eval_expr`'s `EvalError` is `NoValue` (row dropped) or `Udf` (query fails) - `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits and their errors - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628) @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1880 tests** (1866 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1887 tests** (1873 passing, 14 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/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index 25c9e7378c..c2801fe5b8 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -1345,6 +1345,23 @@ fn bench_window(c: &mut Criterion) { group.finish(); } + // Each distinct :val is its own partition (#765): measures partition + // membership construction and sorting without aggregate work. + { + let mut group = c.benchmark_group("window/many_partitions"); + group.sample_size(10); + for &(label, n) in SCALES { + group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| { + let db = helpers::populate_in_memory(n); + b.iter(|| { + db.execute("(query [:find ?e (row-number :over (:partition-by ?v :order-by ?v)) :where [?e :val ?v]])") + .unwrap() + }); + }); + } + group.finish(); + } + // row_number: row number function — similar overhead to rank. { let mut group = c.benchmark_group("window/row_number"); diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index de8e735884..1cbd4acf08 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,860 | 1,891 | +| **Passing** | 1,873 | 1,904 | | **Ignored** | 14 | 15 | -| **Total** | 1,874 | 1,906 | +| **Total** | 1,887 | 1,919 | **Verified**: 2026-10-26 with `cargo test --quiet` (and `--features test-hooks`). @@ -389,6 +389,7 @@ These tests compare the database against an independent answer rather than a sin - `QRY-012` names the holder over the limit (each operator, `IdSpace`, `Recursive`, `Distinct` and `Relations`), and its allocator form through the `try_reserve` test hook; - a cursor returns rows, then `QRY-012`, then nothing; `rewind` and `close` release; - the planner builds a keyless join on the side with the smaller product estimate (#575's shape, a selective outer side, a tie, reordering off). + - Five engine unit tests (#765) cover the exact limit while partition indices overlap input and prior window results, allocator refusal and charge release on errors, empty input, and unchanged row-number, rank, lag and lead over tied rows and interleaved float partitions. - `meter.rs` (4 unit tests) checks charge, release, drop, peak and the allocator form. - `Aggregate` charges its sorted map of groups until every row is built, and lets its hash table and group rows go first, with `sum-distinct` members charged once (`aggregate_finish_charges_its_sorted_groups`, `aggregate_finish_keeps_sum_distinct_members_charged_once`). - **Join rules** (`tests/join_rules_test.rs`, 15 tests; #545, #744) diff --git a/src/query/datalog/aggregate.rs b/src/query/datalog/aggregate.rs index aa78fe3fdc..c02cf8fff6 100644 --- a/src/query/datalog/aggregate.rs +++ b/src/query/datalog/aggregate.rs @@ -667,6 +667,8 @@ pub(crate) struct WindowColumn { /// engine's meter type. pub(crate) trait WindowColumnMeter { fn charge(&mut self, bytes: usize) -> Result<()>; + fn uncharge(&mut self, bytes: usize); + /// On refusal, release `charged` and return `QRY-012`. fn reserve( &mut self, result: std::result::Result<(), TryReserveError>, @@ -677,6 +679,36 @@ pub(crate) trait WindowColumnMeter { fn charge_payload(&mut self, value: &Value) -> Result; } +/// The row-index allocation held while a window is sorted and evaluated. +/// The vector is declared after this guard, so it is dropped before its +/// charge is released on every return path. +struct WindowScratch<'a, M: WindowColumnMeter> { + meter: &'a mut M, + bytes: usize, +} + +impl<'a, M: WindowColumnMeter> WindowScratch<'a, M> { + fn new(meter: &'a mut M, bytes: usize) -> Result { + meter.charge(bytes)?; + Ok(Self { meter, bytes }) + } + + fn reserve(&mut self, result: std::result::Result<(), TryReserveError>) -> Result<()> { + let result = self.meter.reserve(result, self.bytes, self.bytes); + if result.is_err() { + // WindowColumnMeter::reserve has already undone this charge. + self.bytes = 0; + } + result + } +} + +impl Drop for WindowScratch<'_, M> { + fn drop(&mut self) { + self.meter.uncharge(self.bytes); + } +} + /// The value of each window of `find` for each row (spec §4), one list per /// window in `:find` order, by row position. `rows` holds each row's /// values of the [`named_vars`] of `find`, which hold every variable a @@ -710,10 +742,40 @@ pub(crate) fn windows( }; let var = ws.var.as_deref().and_then(col); let order = col(&ws.order_by); - let mut partitions: BTreeMap<&Value, Vec> = BTreeMap::new(); - for r in 0..rows.len() { - let part = ws.partition_by.as_deref().and_then(col); - partitions.entry(read(r, part)).or_default().push(r); + let part = ws.partition_by.as_deref().and_then(col); + let index_bytes = rows + .len() + .checked_mul(size_of::()) + .ok_or_else(|| err_coded!(ErrorCode::Qry012, "Window row-index size overflow"))?; + let mut scratch = WindowScratch::new(meter, index_bytes)?; + let mut keyed = Vec::new(); + scratch.reserve(keyed.try_reserve_exact(rows.len()))?; + keyed.extend(0..rows.len()); + let row_cmp = |a: usize, b: usize| { + let by_key = match ws.order { + Order::Asc => value_order(read(a, order), read(b, order)), + Order::Desc => value_order(read(b, order), read(a, order)), + }; + by_key + .then_with(|| { + rows.get(a) + .into_iter() + .flatten() + .zip(rows.get(b).into_iter().flatten()) + .map(|(x, y)| value_order(x, y)) + .find(|o| o.is_ne()) + .unwrap_or(Ordering::Equal) + }) + .then(a.cmp(&b)) + }; + if let Some(partition_col) = part { + keyed.sort_unstable_by(|&a, &b| { + read(a, Some(partition_col)) + .cmp(read(b, Some(partition_col))) + .then_with(|| row_cmp(a, b)) + }); + } else { + keyed.sort_unstable_by(|&a, &b| row_cmp(a, b)); } // Charge slots before allocating, then payloads as each slot is @@ -721,47 +783,48 @@ pub(crate) fn windows( let slots = rows.len().saturating_mul(size_of::()); let entry = size_of::(); let charged = slots.saturating_add(entry); - meter.charge(charged)?; - meter.reserve(out.try_reserve(1), charged, entry)?; + scratch.meter.charge(charged)?; + scratch.meter.reserve(out.try_reserve(1), charged, entry)?; let mut values = Vec::new(); - meter.reserve(values.try_reserve_exact(rows.len()), charged, slots)?; + scratch + .meter + .reserve(values.try_reserve_exact(rows.len()), charged, slots)?; values.resize(rows.len(), Value::Null); let mut bytes = slots; - for mut keyed in partitions.into_values() { - keyed.sort_by(|&a, &b| { - let by_key = match ws.order { - Order::Asc => value_order(read(a, order), read(b, order)), - Order::Desc => value_order(read(b, order), read(a, order)), - }; - by_key - .then_with(|| { - rows.get(a) - .into_iter() - .flatten() - .zip(rows.get(b).into_iter().flatten()) - .map(|(x, y)| value_order(x, y)) - .find(|o| o.is_ne()) - .unwrap_or(Ordering::Equal) + let mut offset = 0; + while let Some(&first) = keyed.get(offset) { + let end = part.map_or(keyed.len(), |partition_col| { + keyed + .iter() + .skip(offset + 1) + .position(|&r| { + read(r, Some(partition_col)) + .cmp(read(first, Some(partition_col))) + .is_ne() }) - .then(a.cmp(&b)) + .map_or(keyed.len(), |n| offset + 1 + n) }); + let partition = keyed + .get(offset..end) + .ok_or_else(|| err_coded!(ErrorCode::Int032, "window partition bounds invalid"))?; // Row offsets use the physical row order, not aggregate peer groups. if matches!(ws.func, WindowFunc::Lag | WindowFunc::Lead) { - for (pos, &row) in keyed.iter().enumerate() { + for (pos, &row) in partition.iter().enumerate() { let adjacent = if matches!(ws.func, WindowFunc::Lag) { pos.checked_sub(1) } else { pos.checked_add(1) }; - let neighbor = adjacent.and_then(|p| keyed.get(p)); + let neighbor = adjacent.and_then(|p| partition.get(p)); let source = neighbor.map_or(&NULL, |&r| read(r, var)); - let payload = meter.charge_payload(source)?; + let payload = scratch.meter.charge_payload(source)?; bytes = bytes.saturating_add(payload); if let Some(v) = values.get_mut(row) { *v = source.clone(); } } + offset = end; continue; } @@ -770,19 +833,19 @@ pub(crate) fn windows( _ => Some(Running::new(ws, registry)?), }; let mut start = 0; - while let Some(&first) = keyed.get(start) { - let end = keyed + while let Some(&first) = partition.get(start) { + let peer_end = partition .iter() .skip(start + 1) .position(|&r| value_order(read(r, order), read(first, order)).is_ne()) - .map_or(keyed.len(), |n| start + 1 + n); - let peers = keyed.get(start..end).unwrap_or(&[]); + .map_or(partition.len(), |n| start + 1 + n); + let peers = partition.get(start..peer_end).unwrap_or(&[]); if let Some(acc) = running.as_mut() { for &r in peers { acc.step(read(r, var))?; } } - for (pos, &r) in (start..end).zip(peers) { + for (pos, &r) in (start..peer_end).zip(peers) { let (value, payload) = match (&running, &ws.func) { (Some(acc @ (Running::Min(_) | Running::Max(_))), _) => { let best = match acc { @@ -791,12 +854,12 @@ pub(crate) fn windows( } _ => unreachable!(), }; - let payload = meter.charge_payload(best)?; + let payload = scratch.meter.charge_payload(best)?; (acc.value()?, payload) } (Some(acc), _) => { let value = acc.value()?; - let payload = meter.charge_payload(&value)?; + let payload = scratch.meter.charge_payload(&value)?; (value, payload) } (None, WindowFunc::RowNumber) => (position(pos)?, 0), @@ -807,8 +870,9 @@ pub(crate) fn windows( *v = value; } } - start = end; + start = peer_end; } + offset = end; } out.push(WindowColumn { values, bytes }); } diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 8c111eafef..7ec8559ba2 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -2693,6 +2693,254 @@ fn window_result_column_allocator_refusal_is_qry_012() { assert_eq!(meter.used(), 0); } +/// #765: each window's row-index scratch overlaps the input and earlier +/// result columns. The exact limit must include all three. +#[test] +fn window_partition_indices_count_toward_query_memory_limit() { + use super::meter::Held; + use crate::query::datalog::aggregate::{WindowColumn, windows}; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFunc, WindowSpec}; + use std::mem::size_of; + + const N: usize = 512; + let window = FindSpec::Window(WindowSpec { + func: WindowFunc::RowNumber, + var: None, + partition_by: Some("?p".into()), + order_by: "?o".into(), + order: Order::Asc, + }); + let find = vec![FindSpec::Variable("?p".into()), window.clone(), window]; + let rows: Vec> = (0..N) + .rev() + .map(|n| { + vec![ + crate::Value::Integer(n as i64), + crate::Value::Integer(n as i64), + ] + }) + .collect(); + let column_bytes = size_of::() + N * size_of::(); + let indices_bytes = N * size_of::(); + let input_bytes = N * size_of::>(); + let registry = FunctionRegistry::with_builtins(); + + let meter = super::Meter::new(input_bytes + 2 * column_bytes + indices_bytes - 1); + let mut input = Held::new(&meter, "Window"); + input.charge(input_bytes).unwrap(); + let mut held = Held::new(&meter, "Window"); + let err = match windows(&find, &rows, ®istry, &mut held) { + Ok(_) => panic!("partition indices must count toward the query limit"), + Err(err) => err, + }; + assert_eq!(crate::MinigrafError::from(err).code(), "QRY-012"); + assert_eq!( + meter.used(), + input_bytes + column_bytes, + "the second window's scratch is released on error" + ); + held.release(); + input.release(); + assert_eq!(meter.used(), 0); + + let meter = super::Meter::new(input_bytes + 2 * column_bytes + indices_bytes); + let mut input = Held::new(&meter, "Window"); + input.charge(input_bytes).unwrap(); + let mut held = Held::new(&meter, "Window"); + let columns = windows(&find, &rows, ®istry, &mut held).unwrap(); + assert_eq!(columns.len(), 2); + assert_eq!(meter.peak(), input_bytes + 2 * column_bytes + indices_bytes); + assert_eq!( + meter.used(), + input_bytes + 2 * column_bytes, + "scratch is released after the window" + ); + drop(columns); + held.uncharge(2 * column_bytes); + input.release(); + assert_eq!(meter.used(), 0); +} + +/// #765: an allocator refusal while reserving partition indices reports the +/// Window holder and restores its prior meter state. +#[test] +fn window_partition_index_allocator_refusal_is_qry_012() { + use super::meter::Held; + use crate::query::datalog::aggregate::windows; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFunc, WindowSpec}; + + const N: usize = 128; + let find = [FindSpec::Window(WindowSpec { + func: WindowFunc::RowNumber, + var: None, + partition_by: None, + order_by: "?o".into(), + order: Order::Asc, + })]; + let rows = vec![vec![crate::Value::Integer(1)]; N]; + let meter = super::Meter::unlimited(); + let mut held = Held::new(&meter, "Window"); + super::meter::FAIL_RESERVE.with(|f| f.set(Some("Window"))); + let result = windows(&find, &rows, &FunctionRegistry::with_builtins(), &mut held); + super::meter::FAIL_RESERVE.with(|f| f.set(None)); + let err = match result { + Ok(_) => panic!("partition index allocation must fail"), + Err(err) => err, + }; + let err = crate::MinigrafError::from(err); + assert_eq!(err.code(), "QRY-012"); + assert!(err.to_string().contains(&format!( + "allocator refused {} bytes for Window", + N * std::mem::size_of::() + ))); + assert_eq!(meter.used(), 0); +} + +/// A later window error releases the partition index while retaining the +/// already-charged result slots for the caller's error cleanup. +#[test] +fn window_partition_indices_release_on_running_error() { + use super::meter::Held; + use crate::query::datalog::aggregate::{WindowColumn, windows}; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFunc, WindowSpec}; + + const N: usize = 32; + let find = [FindSpec::Window(WindowSpec { + func: WindowFunc::Udf("missing".into()), + var: Some("?v".into()), + partition_by: None, + order_by: "?v".into(), + order: Order::Asc, + })]; + let rows = vec![vec![crate::Value::Integer(1)]; N]; + let meter = super::Meter::unlimited(); + let mut held = Held::new(&meter, "Window"); + let err = match windows(&find, &rows, &FunctionRegistry::with_builtins(), &mut held) { + Ok(_) => panic!("unknown running aggregate must fail"), + Err(err) => err, + }; + assert_eq!(crate::MinigrafError::from(err).code(), "INT-030"); + assert_eq!( + meter.used(), + std::mem::size_of::() + N * std::mem::size_of::(), + "partition scratch was released before error cleanup" + ); + held.release(); + assert_eq!(meter.used(), 0); +} + +#[test] +fn empty_window_does_not_charge_partition_indices() { + use super::meter::Held; + use crate::query::datalog::aggregate::{WindowColumn, windows}; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFunc, WindowSpec}; + + let find = [FindSpec::Window(WindowSpec { + func: WindowFunc::Rank, + var: None, + partition_by: None, + order_by: "?v".into(), + order: Order::Asc, + })]; + let meter = super::Meter::unlimited(); + let mut held = Held::new(&meter, "Window"); + let columns = windows(&find, &[], &FunctionRegistry::with_builtins(), &mut held).unwrap(); + assert_eq!(columns.len(), 1); + assert!(columns[0].values.is_empty()); + assert_eq!(meter.peak(), std::mem::size_of::()); + drop(columns); + held.release(); + assert_eq!(meter.used(), 0); +} + +/// #765: replacing stable partition sorts must preserve peers and adjacent +/// rows across interleaved partitions, including float keys equal under Ord. +#[test] +fn window_partition_sort_preserves_positions_peers_and_neighbors() { + use super::meter::Held; + use crate::query::datalog::aggregate::windows; + use crate::query::datalog::functions::FunctionRegistry; + use crate::query::datalog::types::{FindSpec, Order, WindowFunc, WindowSpec}; + + const N: usize = 256; + let mut find: Vec = ["?id", "?p", "?o", "?v"] + .into_iter() + .map(|v| FindSpec::Variable(v.into())) + .collect(); + for func in [ + WindowFunc::RowNumber, + WindowFunc::Rank, + WindowFunc::Lag, + WindowFunc::Lead, + ] { + find.push(FindSpec::Window(WindowSpec { + var: matches!(func, WindowFunc::Lag | WindowFunc::Lead).then(|| "?v".into()), + func, + partition_by: Some("?p".into()), + order_by: "?o".into(), + order: Order::Asc, + })); + } + let rows: Vec> = (0..N) + .map(|r| { + let id = (r * 73) % N; + let partition = match r % 4 { + 0 => crate::Value::Float(if r % 8 == 0 { -0.0 } else { 0.0 }), + 1 => crate::Value::Float(if r % 8 == 1 { f64::NAN } else { -f64::NAN }), + 2 => crate::Value::Integer(1), + _ => crate::Value::Float(1.0), + }; + vec![ + crate::Value::Integer(id as i64), + partition, + crate::Value::Integer((id % 5) as i64), + crate::Value::Integer((1000 + id) as i64), + ] + }) + .collect(); + + let mut expected = vec![vec![crate::Value::Null; N]; 4]; + for partition in 0..4 { + let mut indices: Vec = (0..N).filter(|r| r % 4 == partition).collect(); + indices.sort_by_key(|&r| { + let id = (r * 73) % N; + (id % 5, id) + }); + for (pos, &r) in indices.iter().enumerate() { + let order = ((r * 73) % N) % 5; + let first_peer = indices + .iter() + .position(|&p| ((p * 73) % N) % 5 == order) + .unwrap(); + expected[0][r] = crate::Value::Integer((pos + 1) as i64); + expected[1][r] = crate::Value::Integer((first_peer + 1) as i64); + for (column, neighbor) in [(2, pos.checked_sub(1)), (3, Some(pos + 1))] { + if let Some(&other) = neighbor.and_then(|i| indices.get(i)) { + expected[column][r] = crate::Value::Integer((1000 + (other * 73) % N) as i64); + } + } + } + } + + let meter = super::Meter::unlimited(); + let mut held = Held::new(&meter, "Window"); + let columns = windows(&find, &rows, &FunctionRegistry::with_builtins(), &mut held).unwrap(); + assert_eq!(columns.len(), 4); + for (column, want) in columns.iter().zip(&expected) { + assert!( + column.values == *want, + "window values preserve physical order" + ); + } + drop(columns); + held.release(); + assert_eq!(meter.used(), 0); +} + /// A refused allocation is `QRY-012` naming the holder (spec §4, second /// form), through the test hook. #[test] diff --git a/src/query/engine/window.rs b/src/query/engine/window.rs index e52ff62c8e..150b401ab6 100644 --- a/src/query/engine/window.rs +++ b/src/query/engine/window.rs @@ -198,6 +198,10 @@ impl WindowColumnMeter for Held { Held::charge(self, bytes) } + fn uncharge(&mut self, bytes: usize) { + Held::uncharge(self, bytes); + } + fn reserve( &mut self, result: std::result::Result<(), TryReserveError>,