1use super::*;
5use crate::ast::{Aggregate as AggregateSpec, Ast, Direction, OrderPart};
6use crate::json::{self, Object, Value};
7use crate::keys::aggregate_columns as cols;
8use crate::map::OrderedMap;
9use crate::schema::{Column, ValueType};
10use std::cell::{Cell, RefCell};
11use std::collections::HashMap;
12use std::rc::{Rc, Weak};
13
14pub type GroupSchema = (OrderedMap<Column>, Vec<String>, Vec<OrderPart>);
16
17pub fn group_source_schema(
24 input_columns: &OrderedMap<Column>,
25 ordering: &[OrderPart],
26 aggregate: &AggregateSpec,
27) -> Result<GroupSchema, PipelineError> {
28 let group_key: Vec<String> = ordering.iter().map(|p| p.field.clone()).collect();
29 let (mut columns, _) = aggregate_source_schema(input_columns, &group_key, aggregate)?;
30 let string = Column {
31 type_: ValueType::String,
32 optional: false,
33 server_name: None,
34 };
35 columns.insert(cols::KEY, string);
36 if carries_components(aggregate.fn_) {
37 columns.insert(
38 cols::ROWS,
39 Column {
40 type_: ValueType::Number,
41 optional: false,
42 server_name: None,
43 },
44 );
45 }
46 let mut sort = ordering.to_vec();
49 sort.push(OrderPart {
50 field: cols::KEY.to_owned(),
51 direction: Direction::Asc,
52 });
53 Ok((columns, vec![cols::KEY.to_owned()], sort))
54}
55
56pub fn group_key(values: &[Value]) -> String {
59 if values.len() == 1 {
60 value_to_key(&values[0])
61 } else {
62 json::stringify(&Value::Array(values.to_vec()))
63 }
64}
65
66pub fn group_ordering(ast: &Ast) -> Vec<OrderPart> {
70 let columns: &[String] = ast
71 .group_by
72 .as_deref()
73 .or_else(|| ast.aggregate.as_ref().and_then(|a| a.distinct.as_deref()))
74 .unwrap_or_default();
75 let mut ordering: Vec<OrderPart> = Vec::new();
76 for part in ast.order_by.as_deref().unwrap_or_default() {
77 if columns.contains(&part.field) && !ordering.iter().any(|p| p.field == part.field) {
78 ordering.push(part.clone());
79 }
80 }
81 for column in columns {
82 if !ordering.iter().any(|p| &p.field == column) {
83 ordering.push(OrderPart {
84 field: column.clone(),
85 direction: Direction::Asc,
86 });
87 }
88 }
89 ordering
90}
91
92pub struct GroupBy {
103 me: Weak<GroupBy>,
104 input: Rc<dyn Input>,
105 columns: Vec<String>,
106 reducer: Reducer,
107 carries_rows: bool,
109 schema: Rc<SourceSchema>,
110 storage: RefCell<HashMap<String, AggState>>,
111 hydrated: Cell<bool>,
113 dirty_groups: RefCell<Vec<(String, Row)>>,
117 output: RefCell<Weak<dyn Output>>,
118}
119
120impl GroupBy {
121 pub fn new(
124 input: Rc<dyn Input>,
125 ordering: &[OrderPart],
126 table_name: impl Into<String>,
127 aggregate: AggregateSpec,
128 ) -> Result<Rc<Self>, PipelineError> {
129 let reducer = Reducer::new(aggregate)?;
130 if ordering.is_empty() {
131 return Err(PipelineError::new("GroupBy: needs at least one column"));
132 }
133 let input_schema = input.get_schema();
134 let input_sort = input_schema.sort.as_deref().unwrap_or_default();
135 let sorted = ordering.iter().enumerate().all(|(i, part)| {
136 input_sort
137 .get(i)
138 .is_some_and(|s| s.field == part.field && s.direction == part.direction)
139 });
140 if !sorted {
141 return Err(PipelineError::new(
142 "GroupBy: the input must be sorted by the group columns first",
143 ));
144 }
145 let (columns, primary_key, sort) =
146 group_source_schema(&input_schema.columns, ordering, &reducer.aggregate)?;
147 let schema = Rc::new(SourceSchema {
148 table_name: table_name.into(),
149 columns,
150 primary_key,
151 relationships: Vec::new(),
152 is_hidden: false,
153 system: input_schema.system,
154 compare_rows: make_comparator(&sort, false),
155 sort: Some(sort),
156 });
157 let carries_rows = carries_components(reducer.fn_());
158 let op = Rc::new_cyclic(|me| GroupBy {
159 me: me.clone(),
160 input: input.clone(),
161 columns: ordering.iter().map(|p| p.field.clone()).collect(),
162 reducer,
163 carries_rows,
164 schema,
165 storage: RefCell::default(),
166 hydrated: Cell::new(false),
167 dirty_groups: RefCell::default(),
168 output: RefCell::new(no_output()),
169 });
170 input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
171 Ok(op)
172 }
173
174 fn emit(&self, change: Change) {
175 let out = self.output.borrow().upgrade();
176 if let Some(out) = out {
177 out.push(change, self);
178 }
179 }
180
181 fn group_values(&self, row: &Row) -> Vec<Value> {
182 self.columns
183 .iter()
184 .map(|c| row.get(c).cloned().unwrap_or(Value::Null))
185 .collect()
186 }
187
188 fn stored(&self, key: &str) -> Option<AggState> {
189 self.storage.borrow().get(key).cloned()
190 }
191
192 fn store(&self, values: &[Value], state: AggState) -> Node {
194 let node = self.make_node(values, &state);
195 self.storage.borrow_mut().insert(group_key(values), state);
196 node
197 }
198
199 fn make_node(&self, values: &[Value], state: &AggState) -> Node {
200 let mut row = Object::new();
201 for (c, v) in self.columns.iter().zip(values) {
202 row.insert(c.clone(), v.clone());
203 }
204 row.insert(cols::KEY, Value::String(group_key(values)));
205 self.reducer.write_payload(&mut row, state);
206 if self.carries_rows {
207 row.insert(cols::ROWS, Value::Number(state.count as f64));
208 }
209 Node::new(Rc::new(row))
210 }
211
212 fn is_dirty(&self, key: &str) -> bool {
213 self.dirty_groups.borrow().iter().any(|(k, _)| k == key)
214 }
215
216 fn mark_dirty(&self, key: &str, row: &Row) {
218 let mut dirty = self.dirty_groups.borrow_mut();
219 match dirty.iter_mut().find(|(k, _)| k == key) {
220 Some(entry) => entry.1 = row.clone(),
221 None => dirty.push((key.to_owned(), row.clone())),
222 }
223 }
224
225 fn emit_if_changed(&self, values: &[Value], stored: &AggState, state: AggState) {
227 let changed = self.reducer.changed(stored, &state)
228 || (self.carries_rows && stored.count != state.count);
229 let node = self.make_node(values, &state);
230 self.storage.borrow_mut().insert(group_key(values), state);
231 if changed {
233 self.emit(Change::Edit {
234 node,
235 old_node: self.make_node(values, stored),
236 });
237 }
238 }
239
240 fn add(&self, row: &Row) {
241 let values = self.group_values(row);
242 let key = group_key(&values);
243 let Some(stored) = self.stored(&key) else {
244 let mut state = AggState::default();
245 self.reducer.contribute(&mut state, row);
246 let node = self.store(&values, state);
247 return self.emit(Change::Add(node));
248 };
249 let mut state = stored.clone();
250 if self.is_dirty(&key) {
251 state.count += 1;
253 self.storage.borrow_mut().insert(key, state);
254 return;
255 }
256 self.reducer.contribute(&mut state, row);
257 self.emit_if_changed(&values, &stored, state);
258 }
259
260 fn remove(&self, row: &Row) {
261 let values = self.group_values(row);
262 let key = group_key(&values);
263 let Some(stored) = self.stored(&key) else {
264 return report("GroupBy: removed a row of a group it lacks");
265 };
266 if stored.count == 1 {
267 self.storage.borrow_mut().remove(&key);
268 self.dirty_groups.borrow_mut().retain(|(k, _)| *k != key);
269 return self.emit(Change::Remove(self.make_node(&values, &stored)));
270 }
271 let mut state = stored.clone();
272 if is_invertible(self.reducer.fn_()) {
273 self.reducer.apply_invertible(&mut state, row, -1, false);
274 } else if self.is_dirty(&key)
275 || !self
276 .reducer
277 .push_extreme(&mut state, &Change::Remove(Node::new(row.clone())))
278 {
279 self.mark_dirty(&key, row);
281 let mut kept = stored;
282 kept.count -= 1;
283 self.storage.borrow_mut().insert(key, kept);
284 return;
285 }
286 self.emit_if_changed(&values, &stored, state);
287 }
288
289 fn update(&self, old_row: &Row, row: &Row) {
291 let values = self.group_values(row);
292 let key = group_key(&values);
293 let Some(stored) = self.stored(&key) else {
294 return;
295 };
296 if self.is_dirty(&key) || self.reducer.same_value(old_row, row) {
297 return;
298 }
299 if !is_invertible(self.reducer.fn_()) {
300 return self.mark_dirty(&key, row);
302 }
303 let mut state = stored.clone();
304 self.reducer.apply_invertible(&mut state, old_row, -1, true);
305 self.reducer.apply_invertible(&mut state, row, 1, true);
306 self.emit_if_changed(&values, &stored, state);
307 }
308
309 fn constraint(&self, row: &Row) -> Option<Constraint> {
313 let mut constraint: Option<Constraint> = None;
314 for c in &self.columns {
315 match row.get(c) {
316 None | Some(Value::Null) => {}
317 Some(v) => constraint
318 .get_or_insert_with(Constraint::default)
319 .set(c, Some(v.clone())),
320 }
321 }
322 constraint
323 }
324
325 fn fetch_now(self: &Rc<Self>, req: &FetchRequest) -> NodeStream {
326 if req.constraint.is_some() || req.start.is_some() || req.reverse {
328 report("GroupBy: fetch takes no constraint, start or reverse");
329 return empty();
330 }
331 self.hydrated.set(true);
332 let me = self.clone();
333 let mut first: Option<Row> = None;
335 let mut state = AggState::default();
336 let mut it = self.input.fetch(&FetchRequest::default());
337 let mut done = false;
338 Box::new(std::iter::from_fn(move || {
339 while !done {
340 let Some(node) = it.next() else {
341 done = true;
342 let first = first.take()?;
343 let values = me.group_values(&first);
344 return Some(me.store(&values, std::mem::take(&mut state)));
345 };
346 if let Some(current) = &first
347 && row_equals_for_compound_key(current, &node.row, &me.columns)
348 {
349 me.reducer.contribute(&mut state, &node.row);
350 continue;
351 }
352 let finished = first.take().map(|f| {
353 let values = me.group_values(&f);
354 me.store(&values, std::mem::take(&mut state))
355 });
356 first = Some(node.row.clone());
357 me.reducer.contribute(&mut state, &node.row);
358 if finished.is_some() {
359 return finished;
360 }
361 }
362 None
363 }))
364 }
365}
366
367impl InputBase for GroupBy {
368 fn get_schema(&self) -> Rc<SourceSchema> {
369 self.schema.clone()
370 }
371 fn destroy(&self) {
372 self.input.destroy()
373 }
374}
375
376impl Input for GroupBy {
377 fn set_output(&self, output: Weak<dyn Output>) {
378 *self.output.borrow_mut() = output;
379 }
380
381 fn fetch(&self, req: &FetchRequest) -> NodeStream {
382 let me = self.me.clone();
383 let req = req.clone();
384 lazy(move || -> NodeStream {
385 match me.upgrade() {
386 Some(me) => me.fetch_now(&req),
387 None => empty(),
388 }
389 })
390 }
391}
392
393impl Output for GroupBy {
394 fn push(&self, change: Change, _pusher: &dyn InputBase) {
395 if !self.hydrated.get() {
396 return;
397 }
398 match change {
399 Change::Add(node) => self.add(&node.row),
400 Change::Remove(node) => self.remove(&node.row),
401 Change::Edit { node, old_node } => {
402 if row_equals_for_compound_key(&old_node.row, &node.row, &self.columns) {
403 self.update(&old_node.row, &node.row);
404 } else {
405 self.remove(&old_node.row);
406 self.add(&node.row);
407 }
408 }
409 Change::Child(..) => {}
411 }
412 }
413
414 fn reconcile(&self, _pusher: &dyn InputBase) {
415 let dirty = std::mem::take(&mut *self.dirty_groups.borrow_mut());
416 for (key, group_row) in dirty {
417 let Some(stored) = self.stored(&key) else {
419 continue;
420 };
421 let mut state = AggState::default();
422 for node in self.input.fetch(&FetchRequest {
423 constraint: self.constraint(&group_row),
424 ..FetchRequest::default()
425 }) {
426 if row_equals_for_compound_key(&node.row, &group_row, &self.columns) {
427 self.reducer.contribute(&mut state, &node.row);
428 }
429 }
430 self.emit_if_changed(&self.group_values(&group_row), &stored, state);
431 }
432 let out = self.output.borrow().upgrade();
433 if let Some(out) = out {
434 out.reconcile(self);
435 }
436 }
437}
438
439#[derive(Clone, Debug)]
442pub struct ProjectedColumn {
443 pub out: String,
444 pub from: String,
445}
446
447pub struct GroupProjection {
453 input: Rc<dyn Input>,
454 projection: Rc<(Vec<ProjectedColumn>, Option<String>)>,
455 schema: Rc<SourceSchema>,
456 output: RefCell<Weak<dyn Output>>,
457}
458
459fn project(projection: &(Vec<ProjectedColumn>, Option<String>), node: &Node) -> Node {
460 let (columns, value_name) = projection;
461 let mut row = Object::new();
462 for c in columns {
463 if let Some(v) = node.row.get(&c.from) {
464 row.insert(c.out.clone(), v.clone());
465 }
466 }
467 if let Some(name) = value_name
468 && let Some(v) = node.row.get(cols::VALUE)
469 {
470 row.insert(name.clone(), v.clone());
471 }
472 Node::new(Rc::new(row))
473}
474
475impl GroupProjection {
476 pub fn new(
477 input: Rc<dyn Input>,
478 columns: Vec<ProjectedColumn>,
479 value_name: Option<String>,
480 ) -> Result<Rc<Self>, PipelineError> {
481 if let Some(name) = &value_name
484 && columns.iter().any(|c| &c.out == name)
485 {
486 return Err(PipelineError::new(format!(
487 "groupBy(): the column \"{name}\" has the same name as the {name}() value"
488 )));
489 }
490 let input_schema = input.get_schema();
491 let view_name = |field: &str| columns.iter().find(|c| c.from == field).map(|c| &c.out);
492 let sort: Vec<OrderPart> = input_schema
493 .sort
494 .as_deref()
495 .unwrap_or_default()
496 .iter()
497 .filter_map(|p| {
498 view_name(&p.field).map(|out| OrderPart {
499 field: out.clone(),
500 direction: p.direction,
501 })
502 })
503 .collect();
504 let mut view_columns = OrderedMap::new();
505 for c in &columns {
506 if let Some(col) = input_schema.columns.get(&c.from) {
507 view_columns.insert(c.out.clone(), col.clone());
508 }
509 }
510 if let Some(name) = &value_name
511 && let Some(col) = input_schema.columns.get(cols::VALUE)
512 {
513 view_columns.insert(name.clone(), col.clone());
514 }
515 let schema = Rc::new(SourceSchema {
516 table_name: input_schema.table_name.clone(),
517 columns: view_columns,
518 primary_key: columns.iter().map(|c| c.out.clone()).collect(),
519 relationships: Vec::new(),
520 is_hidden: false,
521 system: input_schema.system,
522 compare_rows: make_comparator(&sort, false),
523 sort: Some(sort),
524 });
525 let op = Rc::new(GroupProjection {
526 input: input.clone(),
527 projection: Rc::new((columns, value_name)),
528 schema,
529 output: RefCell::new(no_output()),
530 });
531 input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
532 Ok(op)
533 }
534
535 fn emit(&self, change: Change) {
536 let out = self.output.borrow().upgrade();
537 if let Some(out) = out {
538 out.push(change, self);
539 }
540 }
541}
542
543impl InputBase for GroupProjection {
544 fn get_schema(&self) -> Rc<SourceSchema> {
545 self.schema.clone()
546 }
547 fn destroy(&self) {
548 self.input.destroy()
549 }
550}
551
552impl Input for GroupProjection {
553 fn set_output(&self, output: Weak<dyn Output>) {
554 *self.output.borrow_mut() = output;
555 }
556
557 fn fetch(&self, req: &FetchRequest) -> NodeStream {
558 let projection = self.projection.clone();
559 Box::new(self.input.fetch(req).map(move |n| project(&projection, &n)))
560 }
561}
562
563impl Output for GroupProjection {
564 fn push(&self, change: Change, _pusher: &dyn InputBase) {
565 let p = &self.projection;
566 match change {
567 Change::Add(n) => self.emit(Change::Add(project(p, &n))),
568 Change::Remove(n) => self.emit(Change::Remove(project(p, &n))),
569 Change::Edit { node, old_node } => {
570 if p.1.is_none()
573 || identical(node.row.get(cols::VALUE), old_node.row.get(cols::VALUE))
574 {
575 return;
576 }
577 self.emit(Change::Edit {
578 node: project(p, &node),
579 old_node: project(p, &old_node),
580 });
581 }
582 Change::Child(..) => {}
583 }
584 }
585
586 fn reconcile(&self, _pusher: &dyn InputBase) {
587 let out = self.output.borrow().upgrade();
588 if let Some(out) = out {
589 out.reconcile(self);
590 }
591 }
592}