Skip to main content

zero_client/builder/
mod.rs

1//! Builds IVM pipelines from ASTs (`packages/zql/src/builder/builder.ts`).
2//!
3//! Two modes: compute, where every operator runs on the client's own rows,
4//! and the synced client's, which reads aggregates and groups from the rows
5//! the server streams for them (`aggregates_from_source`).
6
7mod pushdown;
8
9pub use pushdown::*;
10
11use crate::ast::{
12    Aggregate as AggregateSpec, AggregateFunction, Ast, Condition, CorrelatedSubquery,
13    CorrelatedSubqueryOperator, Direction, OrderPart, System,
14};
15use crate::ivm::*;
16use crate::json::number;
17use crate::keys::{AGGREGATE_TABLE_PREFIX, aggregate_columns as cols};
18use crate::map::OrderedMap;
19use crate::schema::Column;
20use crate::strings;
21use std::collections::HashSet;
22use std::rc::{Rc, Weak};
23
24/// Connects a pipeline being built to its environment (`BuilderDelegate`).
25pub trait BuilderDelegate {
26    fn get_source(&self, table_name: &str) -> Option<Rc<dyn Source>>;
27    /// Apply `where` filters even when the source applies them all.
28    fn apply_filters_anyway(&self) -> bool {
29        false
30    }
31    /// Allow NOT EXISTS. Only the server does: a client cannot tell a row
32    /// that does not exist from one that is not synced.
33    fn enable_not_exists(&self) -> bool {
34        false
35    }
36    /// Do not copy a parent's conditions on correlation columns into its
37    /// subqueries.
38    fn disable_correlated_predicate_pushdown(&self) -> bool {
39        false
40    }
41    fn map_ast(&self, ast: &Ast) -> Ast {
42        ast.clone()
43    }
44    /// The synced client's mode: an aggregate or a grouping is read from the
45    /// synthetic source the server streams its rows to, rather than computed
46    /// from rows the client doesn't have.
47    fn aggregates_from_source(&self) -> bool {
48        false
49    }
50    /// The source of a relationship aggregate's or a grouped query's rows,
51    /// which the name doesn't describe, made with this shape if it's new.
52    /// `optimistic` lets the client move it when it writes a child row.
53    fn get_aggregate_source(
54        &self,
55        name: &str,
56        _columns: OrderedMap<Column>,
57        _primary_key: Vec<String>,
58        _optimistic: Option<OptimisticAggregate>,
59    ) -> Option<Rc<dyn Source>> {
60        self.get_source(name)
61    }
62    /// The names a synced aggregate row has `table`'s `columns` under: the
63    /// server's, which it computed them with.
64    fn aggregate_key_columns(&self, _table: &str, columns: &[String]) -> Vec<String> {
65        columns.to_vec()
66    }
67}
68
69/// `OptimisticAggregate`: how a mutation of a child row moves a synced
70/// aggregate's row. Registered when a query with a relationship aggregate or
71/// a grouping materializes.
72#[derive(Clone)]
73pub struct OptimisticAggregate {
74    /// The aggregate's table, `aggregate:<queryID>:<alias>` or `…:#group`.
75    pub aggregate_table: String,
76    /// The child table whose mutations move it.
77    pub table: String,
78    /// The correlation (or group) columns of a child row, by client name.
79    pub child_field: Vec<String>,
80    /// The same columns as the aggregate rows name them: server names.
81    pub key_field: Vec<String>,
82    pub aggregate: AggregateSpec,
83    /// The aggregate's `where` as a row predicate; `None` when every child
84    /// row counts.
85    pub predicate: Option<RowPredicate>,
86    /// The rows are a grouped query's groups, keyed by `_0_key`: a group is
87    /// added with its first row and removed with its last.
88    pub grouped: bool,
89}
90
91/// The limit put on EXISTS subqueries: one row is enough, a few more keep a
92/// removal from emptying it.
93pub const EXISTS_LIMIT: f64 = 3.0;
94pub const PERMISSIONS_EXISTS_LIMIT: f64 = 1.0;
95
96type Result<T> = std::result::Result<T, PipelineError>;
97
98fn err<T>(message: impl Into<String>) -> Result<T> {
99    Err(PipelineError::new(message))
100}
101
102/// Builds a pipeline from an AST (`buildPipeline`).
103pub fn build_pipeline(
104    ast: &Ast,
105    delegate: &dyn BuilderDelegate,
106    query_id: &str,
107) -> Result<Rc<dyn Input>> {
108    let mut ast = delegate.map_ast(ast);
109    if ast.group_by.is_some() && ast.aggregate.as_ref().is_some_and(|a| a.distinct.is_some()) {
110        return err("a count of distinct values per group is not supported yet");
111    }
112    // A synced client reads a top-level aggregate's or a grouping's rows
113    // from their source: the table isn't synced, and ordering doesn't apply.
114    if (ast.aggregate.is_some() || ast.group_by.is_some()) && delegate.aggregates_from_source() {
115        return Builder { delegate, query_id }.build(&ast, "", None, false);
116    }
117    if ast.group_by.is_some() || ast.aggregate.as_ref().is_some_and(|a| a.distinct.is_some()) {
118        // A grouping's input is sorted by its columns first, so the rows of
119        // a group are adjacent (see GroupBy).
120        ast.order_by = Some(group_ordering(&ast));
121    }
122    ast = complete_ordering(&ast, &|table| match delegate.get_source(table) {
123        Some(s) => Ok(s.table_schema().primary_key.clone()),
124        None => err(format!("Source not found: {table}")),
125    })?;
126    if !delegate.disable_correlated_predicate_pushdown() {
127        let columns_of = |table: &str| -> OrderedMap<Column> {
128            delegate
129                .get_source(table)
130                .map(|s| s.table_schema().columns.clone())
131                .unwrap_or_default()
132        };
133        ast = push_down_correlated_predicates(&ast, &columns_of);
134    }
135    Builder { delegate, query_id }.build(&ast, "", None, false)
136}
137
138/// Fails if `condition` has a NOT EXISTS outside nested subqueries.
139fn assert_no_not_exists(condition: &Condition) -> Result<()> {
140    match condition {
141        Condition::Simple { .. } => Ok(()),
142        Condition::CorrelatedSubquery {
143            op: CorrelatedSubqueryOperator::NotExists,
144            ..
145        } => err(
146            "not(exists()) is not supported on the client - see https://bugs.rocicorp.dev/issue/3438",
147        ),
148        Condition::CorrelatedSubquery { .. } => Ok(()),
149        Condition::And(cs) | Condition::Or(cs) => cs.iter().try_for_each(assert_no_not_exists),
150    }
151}
152
153struct CsqCondition {
154    related: CorrelatedSubquery,
155    op: CorrelatedSubqueryOperator,
156    flip: Option<bool>,
157}
158
159struct Builder<'a> {
160    delegate: &'a dyn BuilderDelegate,
161    query_id: &'a str,
162}
163
164impl Builder<'_> {
165    fn build(
166        &self,
167        ast_in: &Ast,
168        name: &str,
169        partition_key: Option<&[String]>,
170        is_non_flipped_exists_child: bool,
171    ) -> Result<Rc<dyn Input>> {
172        if ast_in.group_by.is_some() && !name.is_empty() {
173            return err("groupBy is only supported at the top level");
174        }
175        if ast_in.aggregate.is_some()
176            && ast_in.group_by.is_none()
177            && self.delegate.aggregates_from_source()
178        {
179            // The one precomputed row, from `aggregate:<queryID>`.
180            let table = top_level_aggregate_table_name(self.query_id);
181            let Some(source) = self.delegate.get_source(&table) else {
182                return err(format!("Aggregate source not found: {table}"));
183            };
184            let conn = source.connect(
185                Some(vec![OrderPart {
186                    field: cols::KEY.to_owned(),
187                    direction: Direction::Asc,
188                }]),
189                None,
190                None,
191            )?;
192            return Ok(conn);
193        }
194        if ast_in.group_by.is_some() && self.delegate.aggregates_from_source() {
195            return self.group_from_source(ast_in);
196        }
197        let Some(source) = self.delegate.get_source(&ast_in.table) else {
198            return err(format!("Source not found: {}", ast_in.table));
199        };
200        let ast = uniquify_correlated_subquery_condition_aliases(ast_in);
201        if !self.delegate.enable_not_exists()
202            && let Some(w) = &ast.where_
203        {
204            assert_no_not_exists(w)?;
205        }
206
207        let csq_conditions = gather_correlated_subquery_conditions(ast.where_.as_ref());
208        let mut split_edit_keys: HashSet<String> =
209            partition_key.unwrap_or_default().iter().cloned().collect();
210        for csq in &csq_conditions {
211            split_edit_keys.extend(csq.related.correlation.parent_field.iter().cloned());
212        }
213        for csq in ast.related.iter().flatten() {
214            split_edit_keys.extend(csq.correlation.parent_field.iter().cloned());
215        }
216        if is_non_flipped_exists_child {
217            // JS asserts these, which throws.
218            if ast.start.is_some() {
219                return err("EXISTS subqueries must not have start");
220            }
221            if ast.related.is_some() {
222                return err("EXISTS subqueries must not have related");
223            }
224        }
225
226        // Cap needs an unordered connection, but a flipped subquery in the
227        // where builds a UnionFanIn, which needs order. Fall back to Take
228        // then.
229        let use_cap = is_non_flipped_exists_child
230            && !ast
231                .where_
232                .as_ref()
233                .is_some_and(condition_includes_flipped_subquery_at_any_level);
234
235        let sort = if use_cap {
236            None
237        } else {
238            Some(ast.order_by.clone().expect("ordering is complete"))
239        };
240        let conn = source.connect(sort, ast.where_.as_ref(), Some(&split_edit_keys))?;
241        let fully_applied_filters = conn.fully_applied_filters();
242        let mut end: Rc<dyn Input> = conn;
243
244        if let Some(start) = &ast.start {
245            end = Skip::new(end, start);
246        }
247
248        let mut take_gate: Option<Rc<TakeGate>> = None;
249        if ast.limit.is_some() && !use_cap {
250            let gate = TakeGate::new(end);
251            end = gate.clone();
252            take_gate = Some(gate);
253        }
254        let bound_provider = take_gate.clone().map(|g| g as Rc<dyn TakeBoundProvider>);
255
256        // The parent indexes of the EXISTS joins, kept by a JoinIndexTap
257        // after the limit.
258        let mut exists_parent_indexes: Vec<Rc<JoinIndex>> = Vec::new();
259        for csq in csq_conditions.iter().filter(|c| c.flip != Some(true)) {
260            let parent_index = JoinIndex::new(
261                csq.related.correlation.parent_field.clone(),
262                end.get_schema().primary_key.clone(),
263                None,
264            );
265            exists_parent_indexes.push(parent_index.clone());
266            let mut related = csq.related.clone();
267            related.subquery.limit = Some(if related.system == Some(System::Permissions) {
268                PERMISSIONS_EXISTS_LIMIT
269            } else {
270                EXISTS_LIMIT
271            });
272            end = self.apply_correlated_subquery(
273                &related,
274                end,
275                name,
276                true,
277                None,
278                bound_provider.clone(),
279                Some(ExistsJoin {
280                    op: csq.op,
281                    parent_index,
282                }),
283            )?;
284        }
285
286        if let Some(w) = &ast.where_
287            && (!fully_applied_filters || self.delegate.apply_filters_anyway())
288        {
289            end = self.apply_where(
290                end,
291                w,
292                name,
293                partition_key,
294                bound_provider.clone(),
295                &mut exists_parent_indexes,
296                true,
297            )?;
298        }
299
300        if let Some(limit_value) = ast.limit {
301            if !(limit_value >= 0.0 && limit_value.fract() == 0.0) {
302                return err(format!("Invalid limit {}", number::format(limit_value)));
303            }
304            let limit = limit_value as usize;
305            if use_cap {
306                end = Cap::new(end, limit, partition_key.map(<[String]>::to_vec));
307            } else {
308                let take = Take::new(end, limit, partition_key.map(<[String]>::to_vec))?;
309                if let Some(gate) = &take_gate {
310                    gate.set_bound_provider(Rc::downgrade(&take) as Weak<dyn TakeBoundProvider>);
311                    take.set_take_gate(gate);
312                }
313                end = take;
314            }
315        }
316
317        if !exists_parent_indexes.is_empty() {
318            end = JoinIndexTap::new(end, exists_parent_indexes);
319        }
320
321        if ast.group_by.is_some() {
322            // A grouping, compute mode: a distinct is a GroupBy with a count,
323            // which a view doesn't show.
324            if ast.start.is_some() || ast.limit.is_some() || ast.related.is_some() {
325                return err("groupBy does not support start, limit or related");
326            }
327            return Ok(GroupBy::new(
328                end,
329                &group_ordering(&ast),
330                group_table_name(self.query_id),
331                reducer_of(&ast),
332            )?);
333        }
334
335        if let Some(aggregate) = &ast.aggregate {
336            // A top-level aggregate, compute mode: one row, emitted to
337            // `aggregate:<queryID>`, reducing the rows that survive `where`,
338            // `start` and `limit`, so `limit(10).count()` counts at most 10
339            // rows, as in SQL.
340            let count = AggregateSpec::new(AggregateFunction::Count);
341            if aggregate.distinct.is_some() {
342                // A count of the distinct combinations counts a GroupBy's
343                // groups.
344                if ast.start.is_some() || ast.limit.is_some() {
345                    return err("a count of distinct values does not support start or limit");
346                }
347                end = GroupBy::new(
348                    end,
349                    &group_ordering(&ast),
350                    group_table_name(self.query_id),
351                    count.clone(),
352                )?;
353            }
354            let reduced = if aggregate.distinct.is_none() {
355                aggregate.clone()
356            } else {
357                count
358            };
359            return Ok(Aggregate::new(
360                end,
361                Vec::new(),
362                reduced,
363                Some(top_level_aggregate_table_name(self.query_id)),
364            )?);
365        }
366
367        if let Some(related) = &ast.related {
368            // Dedupe by alias, last one wins, keeping the first one's
369            // position.
370            let mut by_alias: Vec<(&str, &CorrelatedSubquery)> = Vec::new();
371            for csq in related {
372                let alias = csq.subquery.alias.as_deref().unwrap_or("");
373                match by_alias.iter_mut().find(|(a, _)| *a == alias) {
374                    Some(entry) => entry.1 = csq,
375                    None => by_alias.push((alias, csq)),
376                }
377            }
378            for (_, csq) in by_alias {
379                end = self.apply_correlated_subquery(
380                    csq,
381                    end,
382                    name,
383                    false,
384                    partition_key,
385                    None,
386                    None,
387                )?;
388            }
389        }
390        Ok(end)
391    }
392
393    #[allow(clippy::too_many_arguments)]
394    fn apply_where(
395        &self,
396        input: Rc<dyn Input>,
397        condition: &Condition,
398        name: &str,
399        parent_partition_key: Option<&[String]>,
400        bound_provider: Option<Rc<dyn TakeBoundProvider>>,
401        exists_parent_indexes: &mut Vec<Rc<JoinIndex>>,
402        track_indexes: bool,
403    ) -> Result<Rc<dyn Input>> {
404        if !condition_includes_flipped_subquery_at_any_level(condition) {
405            return build_filter_pipeline(
406                input,
407                |f| self.apply_filter(f, condition, name),
408                transform_filters(Some(condition)).0,
409            );
410        }
411        self.apply_filter_with_flips(
412            input,
413            condition,
414            name,
415            parent_partition_key,
416            bound_provider,
417            exists_parent_indexes,
418            track_indexes,
419        )
420    }
421
422    #[allow(clippy::too_many_arguments)]
423    fn apply_filter_with_flips(
424        &self,
425        input: Rc<dyn Input>,
426        condition: &Condition,
427        name: &str,
428        parent_partition_key: Option<&[String]>,
429        bound_provider: Option<Rc<dyn TakeBoundProvider>>,
430        exists_parent_indexes: &mut Vec<Rc<JoinIndex>>,
431        track_indexes: bool,
432    ) -> Result<Rc<dyn Input>> {
433        let mut end = input;
434        match condition {
435            Condition::Simple { .. } => panic!("Simple conditions cannot have flips"),
436            Condition::And(conditions) => {
437                let (with_flipped, without_flipped): (Vec<_>, Vec<_>) = conditions
438                    .iter()
439                    .cloned()
440                    .partition(condition_includes_flipped_subquery_at_any_level);
441                if !without_flipped.is_empty() {
442                    let and = Condition::And(without_flipped.clone());
443                    end = build_filter_pipeline(
444                        end,
445                        |f| self.apply_and(f, &without_flipped, name),
446                        transform_filters(Some(&and)).0,
447                    )?;
448                }
449                assert!(!with_flipped.is_empty(), "Impossible to have no flips here");
450                for cond in &with_flipped {
451                    end = self.apply_filter_with_flips(
452                        end,
453                        cond,
454                        name,
455                        parent_partition_key,
456                        bound_provider.clone(),
457                        exists_parent_indexes,
458                        track_indexes,
459                    )?;
460                }
461            }
462            Condition::Or(conditions) => {
463                let (with_flipped, without_flipped): (Vec<_>, Vec<_>) = conditions
464                    .iter()
465                    .cloned()
466                    .partition(condition_includes_flipped_subquery_at_any_level);
467                assert!(!with_flipped.is_empty(), "Impossible to have no flips here");
468                let ufo = UnionFanOut::new(end);
469                let ufo_input: Rc<dyn Input> = ufo.clone();
470                let mut branches: Vec<Rc<dyn Input>> = Vec::new();
471                if !without_flipped.is_empty() {
472                    let or = Condition::Or(without_flipped.clone());
473                    branches.push(build_filter_pipeline(
474                        ufo_input.clone(),
475                        |f| self.apply_or(f, &without_flipped, name),
476                        transform_filters(Some(&or)).0,
477                    )?);
478                }
479                for cond in &with_flipped {
480                    branches.push(self.apply_filter_with_flips(
481                        ufo_input.clone(),
482                        cond,
483                        name,
484                        parent_partition_key,
485                        bound_provider.clone(),
486                        exists_parent_indexes,
487                        track_indexes,
488                    )?);
489                }
490                end = UnionFanIn::new(&ufo, branches);
491            }
492            Condition::CorrelatedSubquery { related: sq, .. } => {
493                let alias = sq
494                    .subquery
495                    .alias
496                    .clone()
497                    .expect("Subquery must have an alias");
498                let child = Builder {
499                    delegate: self.delegate,
500                    query_id: "",
501                }
502                .build(
503                    &sq.subquery,
504                    &format!("{name}.{alias}"),
505                    Some(&sq.correlation.child_field),
506                    false,
507                )?;
508                let parent_index = track_indexes.then(|| {
509                    let index = JoinIndex::new(
510                        sq.correlation.parent_field.clone(),
511                        end.get_schema().primary_key.clone(),
512                        parent_partition_key.map(<[String]>::to_vec),
513                    );
514                    exists_parent_indexes.push(index.clone());
515                    index
516                });
517                end = FlippedJoin::new(FlippedJoinArgs {
518                    parent: end,
519                    child,
520                    parent_key: sq.correlation.parent_field.clone(),
521                    child_key: sq.correlation.child_field.clone(),
522                    relationship_name: alias,
523                    hidden: sq.hidden.unwrap_or(false),
524                    system: sq.system.unwrap_or(System::Client),
525                    parent_partition_key: parent_partition_key.map(<[String]>::to_vec),
526                    bound_provider,
527                    parent_index,
528                });
529            }
530        }
531        Ok(end)
532    }
533
534    fn apply_filter(
535        &self,
536        input: Rc<dyn FilterInput>,
537        condition: &Condition,
538        name: &str,
539    ) -> Result<Rc<dyn FilterInput>> {
540        match condition {
541            Condition::And(cs) => self.apply_and(input, cs, name),
542            Condition::Or(cs) => self.apply_or(input, cs, name),
543            Condition::CorrelatedSubquery { related, op, .. } => {
544                Ok(apply_correlated_subquery_condition(input, related, *op))
545            }
546            Condition::Simple { .. } => Ok(Filter::new(input, create_predicate(condition)?)),
547        }
548    }
549
550    fn apply_and(
551        &self,
552        input: Rc<dyn FilterInput>,
553        conditions: &[Condition],
554        name: &str,
555    ) -> Result<Rc<dyn FilterInput>> {
556        let mut input = input;
557        for c in conditions {
558            input = self.apply_filter(input, c, name)?;
559        }
560        Ok(input)
561    }
562
563    fn apply_or(
564        &self,
565        input: Rc<dyn FilterInput>,
566        conditions: &[Condition],
567        name: &str,
568    ) -> Result<Rc<dyn FilterInput>> {
569        let (other, subquery): (Vec<_>, Vec<_>) = conditions
570            .iter()
571            .cloned()
572            .partition(is_not_and_does_not_contain_subquery);
573        // Without subqueries no fan-out is needed.
574        if subquery.is_empty() {
575            return Ok(Filter::new(input, create_predicate(&Condition::Or(other))?));
576        }
577        let fan_out = FanOut::new(input);
578        let fan_out_input: Rc<dyn FilterInput> = fan_out.clone();
579        let mut branches: Vec<Rc<dyn FilterInput>> = Vec::new();
580        for c in &subquery {
581            branches.push(self.apply_filter(fan_out_input.clone(), c, name)?);
582        }
583        if !other.is_empty() {
584            branches.push(Filter::new(
585                fan_out_input,
586                create_predicate(&Condition::Or(other))?,
587            ));
588        }
589        let fan_in = FanIn::new(&fan_out, branches);
590        fan_out.set_fan_in(&fan_in);
591        Ok(fan_in)
592    }
593
594    #[allow(clippy::too_many_arguments)]
595    /// The source mode of an aggregate relationship: reads the rows the
596    /// server computed from `aggregate:<queryID>:<alias path>`, provisioned
597    /// with the child's column types, and registers how a child row's
598    /// mutation moves them when the row alone can tell.
599    fn aggregate_from_source(
600        &self,
601        sq: &CorrelatedSubquery,
602        aggregate: &AggregateSpec,
603        child_key: &[String],
604        name: &str,
605    ) -> Result<Rc<dyn Input>> {
606        let table = aggregate_table_name(self.query_id, sq, name);
607        let Some(child_source) = self.delegate.get_source(&sq.subquery.table) else {
608            return err(format!("Source not found: {}", sq.subquery.table));
609        };
610        // A junction aggregate's field is on the destination, one hop past
611        // the junction rows that hold the key.
612        let mut input_columns = child_source.table_schema().columns.clone();
613        let junction = sq.subquery.related.as_ref().and_then(|r| r.first());
614        if let Some(dest) = junction {
615            let Some(dest_source) = self.delegate.get_source(&dest.subquery.table) else {
616                return err(format!("Source not found: {}", dest.subquery.table));
617            };
618            for (k, v) in dest_source.table_schema().columns.iter() {
619                input_columns.insert(k.clone(), v.clone());
620            }
621        }
622        let (client_columns, _) =
623            aggregate_source_schema(&input_columns, &sq.correlation.child_field, aggregate)?;
624        let columns = rename_columns(&client_columns, &sq.correlation.child_field, child_key);
625        // Optimism only for count, sum and avg of a direct, unbounded
626        // relationship whose `where` a child row alone decides: otherwise
627        // the server's value stands until it sends another.
628        let mut optimistic = None;
629        if junction.is_none()
630            && is_invertible(aggregate.fn_)
631            && sq.subquery.limit.is_none()
632            && sq.subquery.start.is_none()
633            && let Some(predicate) = per_row_predicate(sq.subquery.where_.as_ref())?
634        {
635            optimistic = Some(OptimisticAggregate {
636                aggregate_table: table.clone(),
637                table: sq.subquery.table.clone(),
638                child_field: sq.correlation.child_field.clone(),
639                key_field: child_key.to_vec(),
640                aggregate: aggregate.clone(),
641                predicate,
642                grouped: false,
643            });
644        }
645        let Some(source) =
646            self.delegate
647                .get_aggregate_source(&table, columns, child_key.to_vec(), optimistic)
648        else {
649            return err(format!("Aggregate source not found: {table}"));
650        };
651        let sort = child_key
652            .iter()
653            .map(|k| OrderPart {
654                field: k.clone(),
655                direction: Direction::Asc,
656            })
657            .collect();
658        Ok(source.connect(Some(sort), None, None)?)
659    }
660
661    /// `groupFromSource`: a synced client reads a grouped query's rows from
662    /// the source the server streams them to.
663    fn group_from_source(&self, ast: &Ast) -> Result<Rc<dyn Input>> {
664        let Some(table_source) = self.delegate.get_source(&ast.table) else {
665            return err(format!("Source not found: {}", ast.table));
666        };
667        let reducer = reducer_of(ast);
668        // The group columns and the aggregated field, under the server's
669        // names.
670        let mut columns = ast.group_by.clone().unwrap_or_default();
671        if let Some(field) = &reducer.field
672            && !columns.contains(field)
673        {
674            columns.push(field.clone());
675        }
676        let names = self.delegate.aggregate_key_columns(&ast.table, &columns);
677        let input_name = |column: &str| -> String {
678            let i = columns
679                .iter()
680                .position(|c| c == column)
681                .expect("a group column");
682            names[i].clone()
683        };
684        let table_columns = &table_source.table_schema().columns;
685        let mut input_columns = OrderedMap::new();
686        for column in &columns {
687            if let Some(c) = table_columns.get(column) {
688                input_columns.insert(input_name(column), c.clone());
689            }
690        }
691        let mut server_aggregate = reducer.clone();
692        server_aggregate.field = server_aggregate.field.as_deref().map(input_name);
693        let ordering: Vec<OrderPart> = group_ordering(ast)
694            .into_iter()
695            .map(|p| OrderPart {
696                field: input_name(&p.field),
697                direction: p.direction,
698            })
699            .collect();
700        let (source_columns, primary_key, sort) =
701            group_source_schema(&input_columns, &ordering, &server_aggregate)?;
702        let table = group_table_name(self.query_id);
703        let optimistic = group_optimistic_delta(ast, &reducer, &table, &input_name)?;
704        let Some(source) = self.delegate.get_aggregate_source(
705            &table,
706            sorted_columns(&source_columns),
707            primary_key,
708            optimistic,
709        ) else {
710            return err(format!("Group source not found: {table}"));
711        };
712        Ok(source.connect(Some(sort), None, None)?)
713    }
714
715    #[allow(clippy::too_many_arguments)]
716    fn apply_correlated_subquery(
717        &self,
718        sq: &CorrelatedSubquery,
719        end: Rc<dyn Input>,
720        name: &str,
721        from_condition: bool,
722        parent_partition_key: Option<&[String]>,
723        bound_provider: Option<Rc<dyn TakeBoundProvider>>,
724        exists: Option<ExistsJoin>,
725    ) -> Result<Rc<dyn Input>> {
726        // Only omitted for conditions: `related` with `limit(0)` still gets
727        // an empty array.
728        if sq.subquery.limit == Some(0.0) && from_condition {
729            return Ok(end);
730        }
731        let alias = sq
732            .subquery
733            .alias
734            .clone()
735            .expect("Subquery must have an alias");
736        if let Some(aggregate) = &sq.aggregate
737            && self.delegate.aggregates_from_source()
738        {
739            // The precomputed rows, one per parent, keyed by the correlation
740            // columns under the server's names.
741            if aggregate.distinct.is_some() {
742                return err("a count of distinct values is not supported in a relationship yet");
743            }
744            let child_key = self
745                .delegate
746                .aggregate_key_columns(&sq.subquery.table, &sq.correlation.child_field);
747            // The server builds its operator with these names and rejects a
748            // collision; so does the client.
749            for column in &child_key {
750                assert_not_synthetic_column(column)?;
751            }
752            let child = self.aggregate_from_source(sq, aggregate, &child_key, name)?;
753            return Ok(Join::new(JoinArgs {
754                parent: end,
755                child,
756                parent_key: sq.correlation.parent_field.clone(),
757                child_key,
758                relationship_name: alias,
759                hidden: sq.hidden.unwrap_or(false),
760                system: sq.system.unwrap_or(System::Client),
761                parent_partition_key: if from_condition {
762                    None
763                } else {
764                    parent_partition_key.map(<[String]>::to_vec)
765                },
766                bound_provider,
767                exists,
768            }));
769        }
770        let mut child = self.build(
771            &sq.subquery,
772            &child_pipeline_name(name, sq),
773            Some(&sq.correlation.child_field),
774            from_condition,
775        )?;
776        if let Some(aggregate) = &sq.aggregate {
777            // An aggregate relationship, compute mode: an Aggregate reduces
778            // the child rows to one row per parent, carrying the correlation
779            // key, so the Join routes it as it would the children.
780            if aggregate.distinct.is_some() {
781                return err("a count of distinct values is not supported in a relationship yet");
782            }
783            let mut aggregated = aggregate.clone();
784            if let Some(dest) = sq.subquery.related.as_ref().and_then(|r| r.first()) {
785                // A junction aggregate: the field lives on the destination,
786                // one hop past the junction row. LiftField copies it (or its
787                // JSON leaf) onto the junction row. `count` never takes this
788                // path: it is a plain count over the junction.
789                let (Some(dest_alias), Some(field)) = (&dest.subquery.alias, &aggregate.field)
790                else {
791                    panic!("a junction aggregate needs a destination alias and a field");
792                };
793                child = LiftField::new(
794                    child,
795                    dest_alias.clone(),
796                    field.clone(),
797                    aggregate.path.is_some().then(|| aggregate.clone()),
798                );
799                aggregated = AggregateSpec {
800                    field: Some(LIFTED_FIELD_COLUMN.to_owned()),
801                    path: None,
802                    ..AggregateSpec::new(aggregate.fn_)
803                };
804            }
805            child = Aggregate::new(
806                child,
807                sq.correlation.child_field.clone(),
808                aggregated,
809                Some(aggregate_table_name(self.query_id, sq, name)),
810            )?;
811        }
812        Ok(Join::new(JoinArgs {
813            parent: end,
814            child,
815            parent_key: sq.correlation.parent_field.clone(),
816            child_key: sq.correlation.child_field.clone(),
817            relationship_name: alias,
818            hidden: sq.hidden.unwrap_or(false),
819            system: sq.system.unwrap_or(System::Client),
820            parent_partition_key: if from_condition {
821                None
822            } else {
823                parent_partition_key.map(<[String]>::to_vec)
824            },
825            bound_provider,
826            exists,
827        }))
828    }
829}
830
831fn build_filter_pipeline(
832    input: Rc<dyn Input>,
833    pipeline: impl FnOnce(Rc<dyn FilterInput>) -> Result<Rc<dyn FilterInput>>,
834    condition: Option<Condition>,
835) -> Result<Rc<dyn Input>> {
836    let start = FilterStart::new(input, condition);
837    let middle = pipeline(start.clone())?;
838    Ok(FilterEnd::new(start, middle))
839}
840
841fn is_not_and_does_not_contain_subquery(condition: &Condition) -> bool {
842    match condition {
843        Condition::CorrelatedSubquery { .. } => false,
844        Condition::Simple { .. } => true,
845        Condition::And(cs) | Condition::Or(cs) => {
846            cs.iter().all(is_not_and_does_not_contain_subquery)
847        }
848    }
849}
850
851fn apply_correlated_subquery_condition(
852    input: Rc<dyn FilterInput>,
853    related: &CorrelatedSubquery,
854    op: CorrelatedSubqueryOperator,
855) -> Rc<dyn FilterInput> {
856    if related.subquery.limit == Some(0.0) {
857        let result = op != CorrelatedSubqueryOperator::Exists;
858        return Filter::new(input, Rc::new(move |_: &Row| result));
859    }
860    let alias = related
861        .subquery
862        .alias
863        .clone()
864        .expect("Subquery must have an alias");
865    Exists::new(input, alias, related.correlation.parent_field.clone(), op)
866}
867
868fn gather_correlated_subquery_conditions(condition: Option<&Condition>) -> Vec<CsqCondition> {
869    fn gather(c: &Condition, out: &mut Vec<CsqCondition>) {
870        match c {
871            Condition::CorrelatedSubquery {
872                related, op, flip, ..
873            } => out.push(CsqCondition {
874                related: related.clone(),
875                op: *op,
876                flip: *flip,
877            }),
878            Condition::And(cs) | Condition::Or(cs) => cs.iter().for_each(|x| gather(x, out)),
879            Condition::Simple { .. } => {}
880        }
881    }
882    let mut out = Vec::new();
883    if let Some(c) = condition {
884        gather(c, &mut out);
885    }
886    out
887}
888
889/// Suffixes the aliases of a where's subqueries with a counter so that each
890/// gets its own relationship.
891fn uniquify_correlated_subquery_condition_aliases(ast: &Ast) -> Ast {
892    let Some(w @ (Condition::And(_) | Condition::Or(_))) = &ast.where_ else {
893        return ast.clone();
894    };
895    fn uniquify(c: &Condition, count: &mut usize) -> Condition {
896        match c {
897            Condition::Simple { .. } => c.clone(),
898            Condition::CorrelatedSubquery {
899                related,
900                op,
901                flip,
902                scalar,
903            } => {
904                let mut related = related.clone();
905                let alias = related.subquery.alias.take().unwrap_or_default();
906                related.subquery.alias = Some(format!("{alias}_{count}"));
907                *count += 1;
908                Condition::CorrelatedSubquery {
909                    related,
910                    op: *op,
911                    flip: *flip,
912                    scalar: *scalar,
913                }
914            }
915            Condition::And(cs) => Condition::And(cs.iter().map(|x| uniquify(x, count)).collect()),
916            Condition::Or(cs) => Condition::Or(cs.iter().map(|x| uniquify(x, count)).collect()),
917        }
918    }
919    let mut result = ast.clone();
920    result.where_ = Some(uniquify(w, &mut 0));
921    result
922}
923
924fn condition_includes_flipped_subquery_at_any_level(c: &Condition) -> bool {
925    match c {
926        Condition::CorrelatedSubquery { flip, .. } => flip.unwrap_or(false),
927        Condition::And(cs) | Condition::Or(cs) => cs
928            .iter()
929            .any(condition_includes_flipped_subquery_at_any_level),
930        Condition::Simple { .. } => false,
931    }
932}
933
934type PrimaryKeyOf<'a> = dyn Fn(&str) -> Result<Vec<String>> + 'a;
935
936/// `completeOrdering`: appends missing primary key columns to every
937/// ordering in the AST.
938pub fn complete_ordering(ast: &Ast, primary_key_of: &PrimaryKeyOf) -> Result<Ast> {
939    let primary_key = primary_key_of(&ast.table)?;
940    let mut result = ast.clone();
941    if let Some(related) = &ast.related {
942        let mut out = Vec::new();
943        for r in related {
944            let mut c = r.clone();
945            c.subquery = Box::new(complete_ordering(&r.subquery, primary_key_of)?);
946            out.push(c);
947        }
948        result.related = Some(out);
949    }
950    if let Some(w) = &ast.where_ {
951        result.where_ = Some(complete_ordering_in_condition(w, primary_key_of)?);
952    }
953    result.order_by = Some(add_primary_keys(&primary_key, ast.order_by.as_deref()));
954    Ok(result)
955}
956
957fn complete_ordering_in_condition(
958    c: &Condition,
959    primary_key_of: &PrimaryKeyOf,
960) -> Result<Condition> {
961    Ok(match c {
962        Condition::Simple { .. } => c.clone(),
963        Condition::CorrelatedSubquery {
964            related,
965            op,
966            flip,
967            scalar,
968        } => {
969            let mut related = related.clone();
970            related.subquery = Box::new(complete_ordering(&related.subquery, primary_key_of)?);
971            Condition::CorrelatedSubquery {
972                related,
973                op: *op,
974                flip: *flip,
975                scalar: *scalar,
976            }
977        }
978        Condition::And(cs) => Condition::And(
979            cs.iter()
980                .map(|x| complete_ordering_in_condition(x, primary_key_of))
981                .collect::<Result<_>>()?,
982        ),
983        Condition::Or(cs) => Condition::Or(
984            cs.iter()
985                .map(|x| complete_ordering_in_condition(x, primary_key_of))
986                .collect::<Result<_>>()?,
987        ),
988    })
989}
990
991fn add_primary_keys(primary_key: &[String], order_by: Option<&[OrderPart]>) -> Vec<OrderPart> {
992    let order_by = order_by.unwrap_or_default();
993    let mut to_add: Vec<&String> = Vec::new();
994    for k in primary_key {
995        if !to_add.contains(&k) && !order_by.iter().any(|p| &p.field == k) {
996            to_add.push(k);
997        }
998    }
999    let mut result = order_by.to_vec();
1000    result.extend(to_add.into_iter().map(|k| OrderPart {
1001        field: k.clone(),
1002        direction: Direction::Asc,
1003    }));
1004    result
1005}
1006
1007/// `childPipelineName`: the parent's pipeline name, a `.`, and the escaped
1008/// alias. An alias can be any string, so it is escaped to keep the path
1009/// unambiguous and free of the `/` and `:` a table name must not contain.
1010fn child_pipeline_name(name: &str, sq: &CorrelatedSubquery) -> String {
1011    format!(
1012        "{name}.{}",
1013        encode_uri_component(sq.subquery.alias.as_deref().unwrap_or(""), true)
1014    )
1015}
1016
1017/// `aggregateTableName`: `aggregate:<queryID>:<alias path>`, the table of an
1018/// aggregate relationship's rows. `parent_name` is the parent's pipeline
1019/// name.
1020pub fn aggregate_table_name(query_id: &str, sq: &CorrelatedSubquery, parent_name: &str) -> String {
1021    let path = child_pipeline_name(parent_name, sq);
1022    format!("{AGGREGATE_TABLE_PREFIX}{query_id}:{}", &path[1..])
1023}
1024
1025/// `topLevelAggregateTableName`: `aggregate:<queryID>`.
1026pub fn top_level_aggregate_table_name(query_id: &str) -> String {
1027    format!("{AGGREGATE_TABLE_PREFIX}{query_id}")
1028}
1029
1030/// `groupTableName`: `aggregate:<queryID>:#group`, the table of a grouped
1031/// query's rows. An escaped alias never has a `#`.
1032pub fn group_table_name(query_id: &str) -> String {
1033    format!("{AGGREGATE_TABLE_PREFIX}{query_id}:#group")
1034}
1035
1036/// `reducerOf`: what a grouped query reduces each group to, its aggregate
1037/// or a count.
1038fn reducer_of(ast: &Ast) -> AggregateSpec {
1039    ast.aggregate
1040        .clone()
1041        .unwrap_or_else(|| AggregateSpec::new(AggregateFunction::Count))
1042}
1043
1044/// `groupViewInput`: the input of a grouped query's view: its rows reduced
1045/// to the group columns and, for a `groupBy()` with an aggregate, the value
1046/// under the function's name, by the names of the pipeline's AST.
1047pub fn group_view_input(
1048    input: Rc<dyn Input>,
1049    ast: &Ast,
1050    delegate: &dyn BuilderDelegate,
1051) -> Result<Rc<dyn Input>> {
1052    let view_names = delegate.map_ast(ast).group_by.unwrap_or_default();
1053    let names = if delegate.aggregates_from_source() {
1054        delegate.aggregate_key_columns(&ast.table, ast.group_by.as_deref().unwrap_or_default())
1055    } else {
1056        view_names.clone()
1057    };
1058    let columns = view_names
1059        .into_iter()
1060        .zip(names)
1061        .map(|(out, from)| ProjectedColumn { out, from })
1062        .collect();
1063    Ok(GroupProjection::new(
1064        input,
1065        columns,
1066        ast.aggregate.as_ref().map(|a| a.fn_.as_str().to_owned()),
1067    )?)
1068}
1069
1070/// `renameColumns`: `columns`, sorted by name, with each of `from` named as
1071/// the same position of `to`.
1072fn rename_columns(
1073    columns: &OrderedMap<Column>,
1074    from: &[String],
1075    to: &[String],
1076) -> OrderedMap<Column> {
1077    let mut sorted: Vec<(&String, &Column)> = columns.iter().collect();
1078    sorted.sort_by(|a, b| strings::utf16(a.0, b.0));
1079    sorted
1080        .into_iter()
1081        .map(|(name, c)| {
1082            let name = from
1083                .iter()
1084                .position(|f| f == name)
1085                .map_or_else(|| name.clone(), |i| to[i].clone());
1086            (name, c.clone())
1087        })
1088        .collect()
1089}
1090
1091/// `columns` sorted by name, as Swift's dictionary of them is.
1092fn sorted_columns(columns: &OrderedMap<Column>) -> OrderedMap<Column> {
1093    rename_columns(columns, &[], &[])
1094}
1095
1096/// A `where` compiled to a predicate on a row alone: `Some(None)` when there
1097/// is none, `None` when it has a subquery, which a row alone can't judge.
1098fn per_row_predicate(condition: Option<&Condition>) -> Result<Option<Option<RowPredicate>>> {
1099    let Some(condition) = condition else {
1100        return Ok(Some(None));
1101    };
1102    let (filters, removed) = transform_filters(Some(condition));
1103    match filters {
1104        Some(filters) if !removed => Ok(Some(Some(create_predicate(&filters)?))),
1105        _ => Ok(None),
1106    }
1107}
1108
1109/// `groupOptimisticDelta`: how a mutation of the table's rows moves a
1110/// grouped query's rows, for count, sum and avg when the `where` can be
1111/// judged from a row alone.
1112fn group_optimistic_delta(
1113    ast: &Ast,
1114    reducer: &AggregateSpec,
1115    table: &str,
1116    input_name: &dyn Fn(&str) -> String,
1117) -> Result<Option<OptimisticAggregate>> {
1118    if !is_invertible(reducer.fn_) {
1119        return Ok(None);
1120    }
1121    let Some(predicate) = per_row_predicate(ast.where_.as_ref())? else {
1122        return Ok(None);
1123    };
1124    // In the group's order, which the server's GroupBy keys a row by.
1125    let columns: Vec<String> = group_ordering(ast).into_iter().map(|p| p.field).collect();
1126    Ok(Some(OptimisticAggregate {
1127        aggregate_table: table.to_owned(),
1128        table: ast.table.clone(),
1129        key_field: columns.iter().map(|c| input_name(c)).collect(),
1130        child_field: columns,
1131        aggregate: reducer.clone(),
1132        predicate,
1133        grouped: true,
1134    }))
1135}
1136
1137/// JS's `encodeURIComponent`: every UTF-8 byte but the letters, digits and
1138/// `-_.!~*'()` as `%XX`; with `escaping_dots`, `.` too.
1139pub fn encode_uri_component(s: &str, escaping_dots: bool) -> String {
1140    const HEX: &[u8; 16] = b"0123456789ABCDEF";
1141    let mut out = String::with_capacity(s.len());
1142    for b in s.bytes() {
1143        match b {
1144            b'A'..=b'Z' | b'a'..=b'z' | b'0'..=b'9' => out.push(b as char),
1145            b'.' if !escaping_dots => out.push('.'),
1146            b'-' | b'_' | b'!' | b'~' | b'*' | b'\'' | b'(' | b')' => out.push(b as char),
1147            _ => {
1148                out.push('%');
1149                out.push(HEX[(b >> 4) as usize] as char);
1150                out.push(HEX[(b & 0xF) as usize] as char);
1151            }
1152        }
1153    }
1154    out
1155}