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//! Ordinary name-returning adapters for the shared borrowed CTE analysis.
8
9use super::cte_order::{
10    analysis::CteAnalysis,
11    order_cte_plans_with_control,
12    references::{self, External, Selection},
13};
14use crate::plan::{CommandPlan, CtePlan, CtePlanBody, QueryPlan, SourcePlan};
15use crate::SQLError;
16use std::{cell::RefCell, collections::BTreeSet};
17use uqa_core::{
18    memory::{Produced, ProductionControl, ProductionVec},
19    RelationIdentity, RelationName,
20};
21
22/// Decode a source reference into a CTE identifier. Qualified relations never resolve to CTEs.
23pub fn cte_reference_name(reference: &str) -> Option<String> {
24    let (schema, name) = crate::RelationIdentity::parse_reference(reference).ok()?;
25    schema.is_none().then_some(name)
26}
27
28pub fn reachable_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
29    reachable_statement_cte_names(&plan.ctes, primary_query_cte_references(plan))
30}
31
32/// The WITH items a command reads, plus every data-modifying item and their dependencies.
33pub fn reachable_command_cte_names(command: &CommandPlan) -> BTreeSet<String> {
34    reachable_statement_cte_names(
35        command.ctes(),
36        primary_command_cte_references(
37            command.ctes(),
38            command.query_inputs(),
39            command.source_input(),
40        ),
41    )
42}
43
44/// Resolve the shared dependency closure. Unreferenced SELECT items do not run, even when they contain volatile functions.
45pub fn reachable_statement_cte_names(
46    ctes: &[CtePlan],
47    mut reachable: BTreeSet<String>,
48) -> BTreeSet<String> {
49    if ctes.is_empty() {
50        return BTreeSet::new();
51    }
52    let mut analysis = CteAnalysis::new(ctes, ProductionControl::uncontrolled())
53        .expect("ordinary CTE dependencies");
54    analysis
55        .set_primary_names(reachable.iter().map(String::as_str))
56        .expect("ordinary CTE roots");
57    let selected = analysis.reachable().expect("ordinary CTE reachability");
58    reachable.extend(
59        ctes.iter()
60            .enumerate()
61            .filter(|(index, _)| selected[*index])
62            .map(|(_, cte)| cte.name.clone()),
63    );
64    reachable
65}
66
67/// The WITH items visible to and named by one definition, respecting nested WITH scopes.
68pub fn cte_definition_references(ctes: &[CtePlan], index: usize) -> BTreeSet<String> {
69    let cte = &ctes[index];
70    let ceiling = if cte.recursive { ctes.len() } else { index };
71    collect_names(
72        ctes[..ceiling].iter().map(|cte| cte.name.as_str()),
73        |external| {
74            references::body(
75                &cte.body,
76                external,
77                ProductionControl::uncontrolled(),
78                Selection::Reachable,
79            )
80        },
81    )
82}
83
84/// The WITH items that the primary query names outside the items' own definitions.
85pub fn primary_query_cte_references(plan: &QueryPlan) -> BTreeSet<String> {
86    primary_query_cte_references_with_control(plan, ProductionControl::uncontrolled())
87        .expect("ordinary CTE references")
88        .iter()
89        .map(|name| (*name).to_owned())
90        .collect()
91}
92
93pub fn primary_query_cte_references_with_control<'p>(
94    plan: &'p QueryPlan,
95    control: ProductionControl<'_>,
96) -> Result<Produced<Vec<&'p str>>, SQLError> {
97    collect_names_with_control(
98        plan.ctes.iter().map(|cte| cte.name.as_str()),
99        |external| references::query_root(&plan.root, external, control, Selection::Reachable),
100        control,
101    )
102}
103
104/// The WITH items named by a command's own query arenas and source input.
105pub fn primary_command_cte_references<'a>(
106    ctes: &[CtePlan],
107    queries: impl IntoIterator<Item = &'a QueryPlan>,
108    source: Option<&SourcePlan>,
109) -> BTreeSet<String> {
110    primary_command_cte_references_with_control(
111        ctes,
112        queries,
113        source,
114        ProductionControl::uncontrolled(),
115    )
116    .expect("ordinary CTE references")
117    .iter()
118    .map(|name| (*name).to_owned())
119    .collect()
120}
121
122pub fn primary_command_cte_references_with_control<'p, 'q>(
123    ctes: &'p [CtePlan],
124    queries: impl IntoIterator<Item = &'q QueryPlan>,
125    source: Option<&SourcePlan>,
126    control: ProductionControl<'_>,
127) -> Result<Produced<Vec<&'p str>>, SQLError> {
128    collect_names_with_control(
129        ctes.iter().map(|cte| cte.name.as_str()),
130        |external| {
131            references::command_root(queries, source, external, control, Selection::Reachable)
132        },
133        control,
134    )
135}
136
137pub fn reachable_statement_ctes_with_control<'p, 'n>(
138    ctes: &'p [CtePlan],
139    primary: impl IntoIterator<Item = &'n str>,
140    control: ProductionControl<'_>,
141) -> Result<Produced<Vec<&'p CtePlan>>, SQLError> {
142    let mut analysis = CteAnalysis::new(ctes, control)?;
143    analysis.set_primary_names(primary)?;
144    let selected = analysis.reachable()?;
145    let mut plans = ProductionVec::new(control);
146    for (index, plan) in ctes.iter().enumerate() {
147        control.check()?;
148        if selected[index] {
149            plans.push_copy(plan)?;
150        }
151    }
152    Ok(plans.finish()?)
153}
154
155/// Only recursive definitions can reference their own binding.
156pub fn cte_references_own_name(cte: &CtePlan) -> bool {
157    cte_references_own_name_with_control(cte, ProductionControl::uncontrolled())
158        .expect("ordinary CTE self reference")
159}
160
161pub fn cte_references_own_name_with_control(
162    cte: &CtePlan,
163    control: ProductionControl<'_>,
164) -> Result<bool, SQLError> {
165    control.check()?;
166    if !cte.recursive {
167        return Ok(false);
168    }
169    let found = std::cell::Cell::new(false);
170    references::body(
171        &cte.body,
172        &|reference| {
173            control.check()?;
174            if RelationIdentity::borrowed_reference(reference).is_some_and(|reference| {
175                reference.schema.is_none() && reference.name == RelationName::decoded(&cte.name)
176            }) {
177                found.set(true);
178            }
179            Ok(())
180        },
181        control,
182        Selection::Reachable,
183    )?;
184    Ok(found.get())
185}
186
187/// Already-visible bindings read by a definition, respecting nested WITH scopes.
188pub fn cte_external_references(body: &CtePlanBody, visible: &BTreeSet<String>) -> BTreeSet<String> {
189    collect_names(visible.iter().map(String::as_str), |external| {
190        references::body(
191            body,
192            external,
193            ProductionControl::uncontrolled(),
194            Selection::Reachable,
195        )
196    })
197}
198
199fn collect_names<'a>(
200    names: impl Iterator<Item = &'a str>,
201    visit: impl FnOnce(&External<'_>) -> Result<(), SQLError>,
202) -> BTreeSet<String> {
203    collect_names_with_control(names, visit, ProductionControl::uncontrolled())
204        .expect("ordinary CTE references")
205        .iter()
206        .map(|name| (*name).to_owned())
207        .collect()
208}
209
210fn collect_names_with_control<'p>(
211    names: impl Iterator<Item = &'p str>,
212    visit: impl FnOnce(&External<'_>) -> Result<(), SQLError>,
213    control: ProductionControl<'_>,
214) -> Result<Produced<Vec<&'p str>>, SQLError> {
215    let mut retained = ProductionVec::new(control);
216    let mut selected = ProductionVec::new(control);
217    let mut result = ProductionVec::new(control);
218    for name in names {
219        retained.push_copy((RelationName::decoded(name), name))?;
220        selected.push_copy(false)?;
221    }
222    if retained.is_empty() {
223        return Ok(result.finish()?);
224    }
225    retained
226        .as_mut_slice()
227        .sort_unstable_by(|left, right| left.0.cmp(&right.0));
228    let selected = RefCell::new(selected);
229    visit(&|reference| {
230        control.check()?;
231        if let Some(reference) = RelationIdentity::borrowed_reference(reference)
232            .filter(|reference| reference.schema.is_none())
233        {
234            if let Ok(index) = retained.binary_search_by(|(name, _)| name.cmp(&reference.name)) {
235                selected.borrow_mut().as_mut_slice()[index] = true;
236            }
237        }
238        Ok(())
239    })?;
240    for ((_, name), selected) in retained.iter().zip(selected.into_inner().iter()) {
241        control.check()?;
242        if *selected {
243            result.push_copy(*name)?;
244        }
245    }
246    Ok(result.finish()?)
247}
248
249pub fn ordered_plan_ctes(plan: &QueryPlan) -> Result<Vec<&CtePlan>, SQLError> {
250    ordered_cte_plans(&plan.ctes)
251}
252
253pub fn ordered_cte_plans(ctes: &[CtePlan]) -> Result<Vec<&CtePlan>, SQLError> {
254    Ok(
255        order_cte_plans_with_control(ctes, ProductionControl::uncontrolled())?
256            .into_uncontrolled()
257            .expect("ordinary CTE order"),
258    )
259}
260
261pub fn order_cte_plans(plans: Vec<&CtePlan>) -> Result<Vec<&CtePlan>, SQLError> {
262    if !plans.iter().any(|plan| plan.recursive) {
263        return Ok(plans);
264    }
265    Ok(
266        order_cte_plans_with_control(plans, ProductionControl::uncontrolled())?
267            .into_uncontrolled()
268            .expect("ordinary CTE order"),
269    )
270}
271
272/// Definitions with exactly one syntactic reference to their own binding, including references in unread nested definitions.
273pub fn single_reference_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
274    let analysis = CteAnalysis::query(plan, ProductionControl::uncontrolled())
275        .expect("ordinary CTE reference counts");
276    plan.ctes
277        .iter()
278        .enumerate()
279        .filter(|(index, _)| analysis.single_reference(*index))
280        .map(|(_, cte)| cte.name.clone())
281        .collect()
282}