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