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    cte_external_references_with_control(
190        body,
191        visible.iter().map(String::as_str),
192        ProductionControl::uncontrolled(),
193    )
194    .expect("ordinary external CTE references")
195    .iter()
196    .map(|name| (*name).to_owned())
197    .collect()
198}
199
200/// Select borrowed enclosing names under the invoking allowance, preserving reachable nested WITH semantics and identifier decoding.
201pub fn cte_external_references_with_control<'p>(
202    body: &CtePlanBody,
203    visible: impl Iterator<Item = &'p str>,
204    control: ProductionControl<'_>,
205) -> Result<Produced<Vec<&'p str>>, SQLError> {
206    collect_names_with_control(
207        visible,
208        |external| references::body(body, external, control, Selection::Reachable),
209        control,
210    )
211}
212
213fn collect_names<'a>(
214    names: impl Iterator<Item = &'a str>,
215    visit: impl FnOnce(&External<'_>) -> Result<(), SQLError>,
216) -> BTreeSet<String> {
217    collect_names_with_control(names, visit, ProductionControl::uncontrolled())
218        .expect("ordinary CTE references")
219        .iter()
220        .map(|name| (*name).to_owned())
221        .collect()
222}
223
224fn collect_names_with_control<'p>(
225    names: impl Iterator<Item = &'p str>,
226    visit: impl FnOnce(&External<'_>) -> Result<(), SQLError>,
227    control: ProductionControl<'_>,
228) -> Result<Produced<Vec<&'p str>>, SQLError> {
229    let mut retained = ProductionVec::new(control);
230    let mut selected = ProductionVec::new(control);
231    let mut result = ProductionVec::new(control);
232    for name in names {
233        retained.push_copy((RelationName::decoded(name), name))?;
234        selected.push_copy(false)?;
235    }
236    if retained.is_empty() {
237        return Ok(result.finish()?);
238    }
239    retained
240        .as_mut_slice()
241        .sort_unstable_by(|left, right| left.0.cmp(&right.0));
242    let selected = RefCell::new(selected);
243    visit(&|reference| {
244        control.check()?;
245        if let Some(reference) = RelationIdentity::borrowed_reference(reference)
246            .filter(|reference| reference.schema.is_none())
247        {
248            if let Ok(index) = retained.binary_search_by(|(name, _)| name.cmp(&reference.name)) {
249                selected.borrow_mut().as_mut_slice()[index] = true;
250            }
251        }
252        Ok(())
253    })?;
254    for ((_, name), selected) in retained.iter().zip(selected.into_inner().iter()) {
255        control.check()?;
256        if *selected {
257            result.push_copy(*name)?;
258        }
259    }
260    Ok(result.finish()?)
261}
262
263pub fn ordered_plan_ctes(plan: &QueryPlan) -> Result<Vec<&CtePlan>, SQLError> {
264    ordered_cte_plans(&plan.ctes)
265}
266
267pub fn ordered_cte_plans(ctes: &[CtePlan]) -> Result<Vec<&CtePlan>, SQLError> {
268    Ok(
269        order_cte_plans_with_control(ctes, ProductionControl::uncontrolled())?
270            .into_uncontrolled()
271            .expect("ordinary CTE order"),
272    )
273}
274
275pub fn order_cte_plans(plans: Vec<&CtePlan>) -> Result<Vec<&CtePlan>, SQLError> {
276    if !plans.iter().any(|plan| plan.recursive) {
277        return Ok(plans);
278    }
279    Ok(
280        order_cte_plans_with_control(plans, ProductionControl::uncontrolled())?
281            .into_uncontrolled()
282            .expect("ordinary CTE order"),
283    )
284}
285
286/// Definitions with exactly one syntactic reference to their own binding, including references in unread nested definitions.
287pub fn single_reference_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
288    let analysis = CteAnalysis::query(plan, ProductionControl::uncontrolled())
289        .expect("ordinary CTE reference counts");
290    plan.ctes
291        .iter()
292        .enumerate()
293        .filter(|(index, _)| analysis.single_reference(*index))
294        .map(|(_, cte)| cte.name.clone())
295        .collect()
296}