Skip to main content

uqa_sql/semantics/
ctes.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! CTE scope, reachability, and dependency ordering.
8
9use crate::plan::{CommandPlan, CtePlan, CtePlanBody, QueryPlan, RelationalPlan, SourcePlan};
10use crate::SQLError;
11use std::collections::{BTreeMap, BTreeSet};
12
13/// Decode a source reference into a CTE identifier. Qualified relations never resolve to CTEs.
14pub fn cte_reference_name(reference: &str) -> Option<String> {
15    let (schema, name) = crate::RelationIdentity::parse_reference(reference).ok()?;
16    schema.is_none().then_some(name)
17}
18
19pub fn reachable_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
20    let targets = plan
21        .ctes
22        .iter()
23        .map(|cte| cte.name.clone())
24        .collect::<BTreeSet<_>>();
25    if targets.is_empty() {
26        return BTreeSet::new();
27    }
28
29    let mut reachable = plan
30        .ctes
31        .iter()
32        .filter(|cte| cte.body.modifies_data())
33        .map(|cte| cte.name.clone())
34        .collect::<BTreeSet<_>>();
35    collect_target_cte_references_from_root(&plan.root, &targets, &BTreeSet::new(), &mut reachable);
36
37    let mut expanded = BTreeSet::new();
38    loop {
39        let pending = plan
40            .ctes
41            .iter()
42            .enumerate()
43            .filter(|(_, cte)| reachable.contains(&cte.name) && !expanded.contains(&cte.name))
44            .collect::<Vec<_>>();
45        if pending.is_empty() {
46            break;
47        }
48        for (index, cte) in pending {
49            expanded.insert(cte.name.clone());
50            let visible_dependencies = if cte.recursive {
51                targets.clone()
52            } else {
53                plan.ctes[..index]
54                    .iter()
55                    .map(|dependency| dependency.name.clone())
56                    .collect::<BTreeSet<_>>()
57            };
58            collect_target_cte_references_from_body(
59                &cte.body,
60                &visible_dependencies,
61                &BTreeSet::new(),
62                &mut reachable,
63            );
64        }
65    }
66    reachable
67}
68
69/// The WITH items of `ctes` that the definition of the item at `index` names: the items defined before it, or any item of a recursive list.
70pub fn cte_definition_references(ctes: &[CtePlan], index: usize) -> BTreeSet<String> {
71    let cte = &ctes[index];
72    let visible = if cte.recursive {
73        ctes.iter()
74    } else {
75        ctes[..index].iter()
76    }
77    .map(|cte| cte.name.clone())
78    .collect::<BTreeSet<_>>();
79    let mut references = BTreeSet::new();
80    collect_target_cte_references_from_body(&cte.body, &visible, &BTreeSet::new(), &mut references);
81    references
82}
83
84/// The WITH items of `plan` that its primary query names outside the items' own definitions.
85pub fn primary_query_cte_references(plan: &QueryPlan) -> BTreeSet<String> {
86    let targets = plan
87        .ctes
88        .iter()
89        .map(|cte| cte.name.clone())
90        .collect::<BTreeSet<_>>();
91    let mut references = BTreeSet::new();
92    if !targets.is_empty() {
93        collect_target_cte_references_from_root(
94            &plan.root,
95            &targets,
96            &BTreeSet::new(),
97            &mut references,
98        );
99    }
100    references
101}
102
103/// The WITH items of a data-modifying statement that its own clauses name: the queries and the source relation it evaluates in the scope of `ctes`.
104pub fn primary_command_cte_references(
105    ctes: &[CtePlan],
106    queries: &[&QueryPlan],
107    source: Option<&SourcePlan>,
108) -> BTreeSet<String> {
109    let targets = ctes
110        .iter()
111        .map(|cte| cte.name.clone())
112        .collect::<BTreeSet<_>>();
113    let mut references = BTreeSet::new();
114    if targets.is_empty() {
115        return references;
116    }
117    for query in queries {
118        collect_target_cte_references_from_nested_query(
119            query,
120            &targets,
121            &BTreeSet::new(),
122            &mut references,
123        );
124    }
125    if let Some(source) = source {
126        collect_target_cte_references_from_source(
127            source,
128            &targets,
129            &BTreeSet::new(),
130            &mut references,
131        );
132    }
133    references
134}
135
136pub fn cte_references_own_name(cte: &CtePlan) -> bool {
137    let targets = BTreeSet::from([cte.name.clone()]);
138    let mut references = BTreeSet::new();
139    collect_target_cte_references_from_body(&cte.body, &targets, &BTreeSet::new(), &mut references);
140    references.contains(&cte.name)
141}
142
143pub fn ordered_plan_ctes(plan: &QueryPlan) -> Result<Vec<&CtePlan>, SQLError> {
144    ordered_cte_plans(&plan.ctes)
145}
146
147pub fn ordered_cte_plans(ctes: &[CtePlan]) -> Result<Vec<&CtePlan>, SQLError> {
148    order_cte_plans(ctes.iter().collect())
149}
150
151pub fn order_cte_plans(plans: Vec<&CtePlan>) -> Result<Vec<&CtePlan>, SQLError> {
152    if !plans.iter().any(|cte| cte.recursive) {
153        return Ok(plans);
154    }
155    let targets = plans
156        .iter()
157        .map(|cte| cte.name.clone())
158        .collect::<BTreeSet<_>>();
159    let dependencies = plans
160        .iter()
161        .map(|cte| {
162            let mut references = BTreeSet::new();
163            collect_target_cte_references_from_body(
164                &cte.body,
165                &targets,
166                &BTreeSet::new(),
167                &mut references,
168            );
169            references.remove(&cte.name);
170            references
171        })
172        .collect::<Vec<_>>();
173    let mut emitted = BTreeSet::new();
174    let mut ordered = Vec::with_capacity(plans.len());
175    let mut remaining = (0..plans.len()).collect::<BTreeSet<_>>();
176    while !remaining.is_empty() {
177        let ready = remaining
178            .iter()
179            .copied()
180            .find(|index| dependencies[*index].is_subset(&emitted));
181        let Some(index) = ready else {
182            return Err(SQLError::Routine {
183                sqlstate: "0A000".into(),
184                message: "mutual recursion between WITH items is not implemented".into(),
185            });
186        };
187        remaining.remove(&index);
188        emitted.insert(plans[index].name.clone());
189        ordered.push(plans[index]);
190    }
191    Ok(ordered)
192}
193
194/// Return reachable CTEs with exactly one syntactic reference in the owning query tree. Counting references outside their lexical visibility can only make this set more conservative, never cause a multiply referenced CTE to be streamed as a single-consumer input.
195pub fn single_reference_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
196    let targets = plan
197        .ctes
198        .iter()
199        .map(|cte| cte.name.clone())
200        .collect::<BTreeSet<_>>();
201    let mut counts = targets
202        .iter()
203        .map(|name| (name.clone(), 0usize))
204        .collect::<BTreeMap<_, _>>();
205    count_plan_cte_references(plan, &targets, &mut counts);
206    counts
207        .into_iter()
208        .filter_map(|(name, count)| (count == 1).then_some(name))
209        .collect()
210}
211
212fn count_plan_cte_references(
213    plan: &QueryPlan,
214    targets: &BTreeSet<String>,
215    counts: &mut BTreeMap<String, usize>,
216) {
217    for cte in &plan.ctes {
218        count_cte_body_references(&cte.body, targets, counts);
219    }
220    count_relational_cte_references(&plan.root, targets, counts);
221}
222
223fn count_cte_body_references(
224    body: &CtePlanBody,
225    targets: &BTreeSet<String>,
226    counts: &mut BTreeMap<String, usize>,
227) {
228    match body {
229        CtePlanBody::Query(query) => count_plan_cte_references(query, targets, counts),
230        CtePlanBody::Command(command) => {
231            for cte in command.ctes() {
232                count_cte_body_references(&cte.body, targets, counts);
233            }
234            for query in command.query_inputs() {
235                count_plan_cte_references(query, targets, counts);
236            }
237            if let Some(source) = command.source_input() {
238                count_source_cte_references(source, targets, counts);
239            }
240        }
241    }
242}
243
244fn count_relational_cte_references(
245    plan: &RelationalPlan,
246    targets: &BTreeSet<String>,
247    counts: &mut BTreeMap<String, usize>,
248) {
249    match plan {
250        RelationalPlan::QueryBlock(block) => {
251            if let Some(source) = &block.from {
252                count_source_cte_references(source, targets, counts);
253            }
254            for subquery in &block.subqueries {
255                count_plan_cte_references(subquery, targets, counts);
256            }
257        }
258        RelationalPlan::SetOp {
259            left,
260            right,
261            subqueries,
262            ..
263        } => {
264            count_plan_cte_references(left, targets, counts);
265            count_plan_cte_references(right, targets, counts);
266            for subquery in subqueries {
267                count_plan_cte_references(subquery, targets, counts);
268            }
269        }
270        RelationalPlan::Values { subqueries, .. } => {
271            for subquery in subqueries {
272                count_plan_cte_references(subquery, targets, counts);
273            }
274        }
275    }
276}
277
278fn count_source_cte_references(
279    source: &SourcePlan,
280    targets: &BTreeSet<String>,
281    counts: &mut BTreeMap<String, usize>,
282) {
283    match source {
284        crate::plan::SourcePlan::RetainedRows(_) => {}
285        SourcePlan::Table { name, .. } => {
286            if let Some(name) = cte_reference_name(name).filter(|name| targets.contains(name)) {
287                *counts.entry(name).or_default() += 1;
288            }
289        }
290        SourcePlan::Join { left, right, .. } => {
291            count_source_cte_references(left, targets, counts);
292            count_source_cte_references(right, targets, counts);
293        }
294        SourcePlan::Subquery { body, .. } => {
295            count_plan_cte_references(body, targets, counts);
296        }
297        SourcePlan::Values { .. }
298        | SourcePlan::Function { .. }
299        | SourcePlan::FunctionGroup { .. } => {}
300    }
301}
302
303fn collect_target_cte_references_from_root(
304    root: &RelationalPlan,
305    targets: &BTreeSet<String>,
306    shadowed: &BTreeSet<String>,
307    references: &mut BTreeSet<String>,
308) {
309    match root {
310        RelationalPlan::QueryBlock(block) => {
311            if let Some(source) = &block.from {
312                collect_target_cte_references_from_source(source, targets, shadowed, references);
313            }
314            for subquery in &block.subqueries {
315                collect_target_cte_references_from_nested_query(
316                    subquery, targets, shadowed, references,
317                );
318            }
319        }
320        RelationalPlan::SetOp {
321            left,
322            right,
323            subqueries,
324            ..
325        } => {
326            collect_target_cte_references_from_nested_query(left, targets, shadowed, references);
327            collect_target_cte_references_from_nested_query(right, targets, shadowed, references);
328            for subquery in subqueries {
329                collect_target_cte_references_from_nested_query(
330                    subquery, targets, shadowed, references,
331                );
332            }
333        }
334        RelationalPlan::Values { subqueries, .. } => {
335            for subquery in subqueries {
336                collect_target_cte_references_from_nested_query(
337                    subquery, targets, shadowed, references,
338                );
339            }
340        }
341    }
342}
343
344fn collect_target_cte_references_from_source(
345    source: &SourcePlan,
346    targets: &BTreeSet<String>,
347    shadowed: &BTreeSet<String>,
348    references: &mut BTreeSet<String>,
349) {
350    match source {
351        crate::plan::SourcePlan::RetainedRows(_) => {}
352        SourcePlan::Table { name, .. } => {
353            if let Some(name) = cte_reference_name(name)
354                .filter(|name| targets.contains(name) && !shadowed.contains(name))
355            {
356                references.insert(name);
357            }
358        }
359        SourcePlan::Join { left, right, .. } => {
360            collect_target_cte_references_from_source(left, targets, shadowed, references);
361            collect_target_cte_references_from_source(right, targets, shadowed, references);
362        }
363        SourcePlan::Subquery { body, .. } => {
364            collect_target_cte_references_from_nested_query(body, targets, shadowed, references);
365        }
366        SourcePlan::Values { .. }
367        | SourcePlan::Function { .. }
368        | SourcePlan::FunctionGroup { .. } => {}
369    }
370}
371
372fn collect_target_cte_references_from_command_root(
373    command: &CommandPlan,
374    targets: &BTreeSet<String>,
375    shadowed: &BTreeSet<String>,
376    references: &mut BTreeSet<String>,
377) {
378    for query in command.query_inputs() {
379        collect_target_cte_references_from_nested_query(query, targets, shadowed, references);
380    }
381    if let Some(source) = command.source_input() {
382        collect_target_cte_references_from_source(source, targets, shadowed, references);
383    }
384}
385
386fn collect_target_cte_references_from_body(
387    body: &CtePlanBody,
388    targets: &BTreeSet<String>,
389    shadowed: &BTreeSet<String>,
390    references: &mut BTreeSet<String>,
391) {
392    let CtePlanBody::Command(command) = body else {
393        if let CtePlanBody::Query(query) = body {
394            collect_target_cte_references_from_nested_query(query, targets, shadowed, references);
395        }
396        return;
397    };
398    let locals = command
399        .ctes()
400        .iter()
401        .map(|cte| cte.name.clone())
402        .collect::<BTreeSet<_>>();
403    let mut reachable = command
404        .ctes()
405        .iter()
406        .filter(|cte| cte.body.modifies_data())
407        .map(|cte| cte.name.clone())
408        .collect::<BTreeSet<_>>();
409    collect_target_cte_references_from_command_root(
410        command,
411        &locals,
412        &BTreeSet::new(),
413        &mut reachable,
414    );
415    let mut expanded = BTreeSet::new();
416    loop {
417        let pending = command
418            .ctes()
419            .iter()
420            .enumerate()
421            .filter(|(_, cte)| reachable.contains(&cte.name) && !expanded.contains(&cte.name))
422            .collect::<Vec<_>>();
423        if pending.is_empty() {
424            break;
425        }
426        for (index, cte) in pending {
427            expanded.insert(cte.name.clone());
428            let visible = if cte.recursive {
429                locals.clone()
430            } else {
431                command.ctes()[..index]
432                    .iter()
433                    .map(|cte| cte.name.clone())
434                    .collect()
435            };
436            collect_target_cte_references_from_body(
437                &cte.body,
438                &visible,
439                &BTreeSet::new(),
440                &mut reachable,
441            );
442        }
443    }
444    let mut root_shadowed = shadowed.clone();
445    root_shadowed.extend(locals.iter().cloned());
446    collect_target_cte_references_from_command_root(command, targets, &root_shadowed, references);
447    let mut preceding = shadowed.clone();
448    for cte in command.ctes() {
449        if reachable.contains(&cte.name) {
450            let definition = if cte.recursive {
451                shadowed.union(&locals).cloned().collect()
452            } else {
453                preceding.clone()
454            };
455            collect_target_cte_references_from_body(&cte.body, targets, &definition, references);
456        }
457        preceding.insert(cte.name.clone());
458    }
459}
460
461fn collect_target_cte_references_from_nested_query(
462    plan: &QueryPlan,
463    targets: &BTreeSet<String>,
464    shadowed: &BTreeSet<String>,
465    references: &mut BTreeSet<String>,
466) {
467    let local_reachable = reachable_plan_cte_names(plan);
468    let mut root_shadowed = shadowed.clone();
469    root_shadowed.extend(
470        plan.ctes
471            .iter()
472            .map(|cte| cte.name.clone())
473            .filter(|name| targets.contains(name)),
474    );
475    collect_target_cte_references_from_root(&plan.root, targets, &root_shadowed, references);
476    let recursive_scope = plan.ctes.iter().any(|cte| cte.recursive).then(|| {
477        plan.ctes
478            .iter()
479            .map(|cte| cte.name.clone())
480            .collect::<BTreeSet<_>>()
481    });
482    let mut preceding = BTreeSet::new();
483    for cte in &plan.ctes {
484        if local_reachable.contains(&cte.name) {
485            let mut definition_shadowed = shadowed.clone();
486            if let Some(recursive_scope) = recursive_scope.as_ref() {
487                definition_shadowed.extend(
488                    recursive_scope
489                        .iter()
490                        .filter(|name| targets.contains(*name))
491                        .cloned(),
492                );
493            } else {
494                definition_shadowed.extend(
495                    preceding
496                        .iter()
497                        .filter(|name| targets.contains(*name))
498                        .cloned(),
499                );
500            }
501            collect_target_cte_references_from_body(
502                &cte.body,
503                targets,
504                &definition_shadowed,
505                references,
506            );
507        }
508        preceding.insert(cte.name.clone());
509    }
510}