Skip to main content

uqa_sql/semantics/view_rewrite/
deferred.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Resolve outer-column substitutions only after the local namespace is known.
8
9use crate::plan::{ExpressionPlan, QueryBlockPlan, QueryPlan, RelationalPlan};
10use crate::{ColumnIdentity, RowSchema, SQLError, ScalarExpr};
11use std::borrow::Cow;
12use std::collections::{BTreeMap, BTreeSet};
13use std::sync::Arc;
14
15mod scope;
16mod sources;
17pub use sources::{resolve_outer_source_rewrites, resolve_outer_sources};
18#[cfg(test)]
19mod tests;
20pub use scope::bind_outer_rewrite_scope;
21
22/// Resolve an expression against its actual local descriptor. The caller retains the accompanying scalar-query arena for evaluation.
23pub fn resolve_outer_expression_rewrites(
24    expression: &mut ScalarExpr,
25    rewrites: &[DeferredOuterRewrite],
26    local: &RowSchema,
27    subqueries: &mut Vec<QueryPlan>,
28) {
29    for rewrite in rewrites {
30        rewrite
31            .in_namespace(local)
32            .expression(expression, subqueries);
33    }
34}
35
36/// An outer-column rewrite retained across an open native row descriptor. Names in an intervening query scope shadow these substitutions, even when their values are NULL.
37#[derive(Debug, Clone)]
38pub struct DeferredOuterRewrite {
39    outer_columns: Arc<BTreeMap<ColumnIdentity, crate::ast::InternalColumnRef>>,
40    replacements: Arc<BTreeMap<ColumnIdentity, OuterReplacement>>,
41    pub(super) shadowed_qualifiers: uqa_core::memory::OwnedSet<String>,
42    pub(super) shadowed_columns: uqa_core::memory::OwnedSet<String>,
43}
44
45#[derive(Debug, Clone)]
46struct OuterReplacement {
47    expression: ExpressionPlan,
48    qualifier: String,
49}
50
51/// Bind a pending rewrite to the complete local source descriptor without changing its retained syntax. An open descriptor cannot decide that an absent name belongs to the outer scope.
52pub fn resolve_outer_rewrites<'a>(
53    block: &'a QueryBlockPlan,
54    local: &RowSchema,
55) -> Cow<'a, QueryBlockPlan> {
56    let open = local.columns_are_open(None);
57    if block.deferred_outer_rewrites.is_empty()
58        || open
59            && !block.deferred_outer_rewrites.iter().any(|rewrite| {
60                rewrite
61                    .replacements
62                    .keys()
63                    .any(|identity| identity.qualifier().is_some())
64            })
65    {
66        return Cow::Borrowed(block);
67    }
68    let mut block = block.clone();
69    for mut rewrite in std::mem::take(&mut block.deferred_outer_rewrites) {
70        rewrite.add_namespace(local);
71        if open {
72            let mut pending = rewrite.clone();
73            Arc::make_mut(&mut pending.replacements)
74                .retain(|identity, _| identity.qualifier().is_none());
75            if !pending.replacements.is_empty() {
76                block.deferred_outer_rewrites.push(pending);
77            }
78            Arc::make_mut(&mut rewrite.replacements)
79                .retain(|identity, _| identity.qualifier().is_some());
80        }
81        rewrite.block(&mut block);
82    }
83    Cow::Owned(block)
84}
85
86impl DeferredOuterRewrite {
87    pub(crate) fn copy_with(
88        &self,
89        copying: &mut crate::plan::copy::Copying<'_>,
90    ) -> Result<Self, SQLError> {
91        Ok(Self {
92            outer_columns: Arc::clone(&self.outer_columns),
93            replacements: Arc::clone(&self.replacements),
94            shadowed_qualifiers: copying.set(&self.shadowed_qualifiers, |copying, name| {
95                copying.text(name)
96            })?,
97            shadowed_columns: copying
98                .set(&self.shadowed_columns, |copying, name| copying.text(name))?,
99        })
100    }
101
102    /// Bind expressions whose original input attributes already have internal identities. Nested query namespaces resolve their own names before consulting these outer replacements.
103    pub(crate) fn from_inputs(inputs: BTreeMap<ColumnIdentity, ExpressionPlan>) -> Self {
104        Self {
105            outer_columns: Arc::new(BTreeMap::new()),
106            replacements: Arc::new(
107                inputs
108                    .into_iter()
109                    .map(|(identity, expression)| {
110                        (
111                            identity,
112                            OuterReplacement {
113                                expression,
114                                qualifier: String::new(),
115                            },
116                        )
117                    })
118                    .collect(),
119            ),
120            shadowed_qualifiers: uqa_core::memory::OwnedSet::new(),
121            shadowed_columns: uqa_core::memory::OwnedSet::new(),
122        }
123    }
124
125    pub(crate) fn bind_expression(&self, expression: &mut ExpressionPlan) {
126        self.expression(&mut expression.scalar, &mut expression.subqueries);
127    }
128
129    pub(super) fn rebase(
130        &mut self,
131        context: &super::correlation::CorrelatedRewriteContext<'_>,
132    ) -> Result<(), SQLError> {
133        for replacement in Arc::make_mut(&mut self.replacements).values_mut() {
134            super::correlation::rewrite_outer_expression(context, &mut replacement.expression)?;
135        }
136        self.capture_outer_columns();
137        Ok(())
138    }
139
140    pub(super) fn capture(
141        context: &super::correlation::CorrelatedRewriteContext<'_>,
142        block: &QueryBlockPlan,
143        shadowed_qualifiers: &BTreeSet<String>,
144        shadowed_columns: &BTreeSet<String>,
145    ) -> Result<Self, SQLError> {
146        let references = column_references(block);
147        let mut replacements = BTreeMap::new();
148        for column in &context.layer.columns {
149            for qualifier in std::iter::once(None).chain(
150                context
151                    .target_qualifiers
152                    .iter()
153                    .map(|qualifier| Some(qualifier.as_str())),
154            ) {
155                let identity = qualifier.map_or_else(
156                    || ColumnIdentity::unqualified(&column.name),
157                    |qualifier| ColumnIdentity::qualified(qualifier, &column.name),
158                );
159                if !references.contains(&identity) {
160                    continue;
161                }
162                let mut subqueries = Vec::new();
163                let scalar = super::embed_layer_expression(
164                    context.services,
165                    &column.expression,
166                    context.layer,
167                    qualifier.unwrap_or(context.default_target_qualifier),
168                    &mut subqueries,
169                )?;
170                replacements.insert(
171                    identity,
172                    OuterReplacement {
173                        expression: ExpressionPlan { scalar, subqueries },
174                        qualifier: qualifier
175                            .unwrap_or(context.default_target_qualifier)
176                            .to_owned(),
177                    },
178                );
179            }
180        }
181        if let Some(source) = context.source {
182            for column in super::schema_public_columns(source) {
183                if !references.contains(&ColumnIdentity::unqualified(&column)) {
184                    continue;
185                }
186                let Some(qualifier) = source
187                    .unqualified_position(&column)
188                    .and_then(|position| source.identity(position))
189                    .and_then(ColumnIdentity::qualifier)
190                else {
191                    continue;
192                };
193                replacements
194                    .entry(ColumnIdentity::unqualified(&column))
195                    .or_insert_with(|| OuterReplacement {
196                        expression: ExpressionPlan {
197                            scalar: ScalarExpr::qualified_column(qualifier, &column),
198                            subqueries: Vec::new(),
199                        },
200                        qualifier: qualifier.to_owned(),
201                    });
202            }
203        }
204        let mut rewrite = Self {
205            outer_columns: Arc::new(BTreeMap::new()),
206            replacements: Arc::new(replacements),
207            shadowed_qualifiers: shadowed_qualifiers.iter().cloned().collect(),
208            shadowed_columns: shadowed_columns.iter().cloned().collect(),
209        };
210        rewrite.capture_outer_columns();
211        Ok(rewrite)
212    }
213
214    pub(crate) fn expressions(&self) -> impl Iterator<Item = &ExpressionPlan> {
215        self.replacements
216            .values()
217            .map(|replacement| &replacement.expression)
218    }
219
220    pub(crate) fn visit_scalar_expressions(&self, visit: &mut dyn FnMut(&ScalarExpr)) {
221        for expression in self.expressions() {
222            visit(&expression.scalar);
223            for query in &expression.subqueries {
224                query.visit_scalar_expressions(visit);
225            }
226        }
227    }
228
229    pub(crate) fn rewrite_scalar_expressions(&mut self, rewrite: &mut dyn FnMut(&mut ScalarExpr)) {
230        for replacement in Arc::make_mut(&mut self.replacements).values_mut() {
231            let expression = &mut replacement.expression;
232            crate::plan::rewrite_scalar_expression(&mut expression.scalar, rewrite);
233            for query in &mut expression.subqueries {
234                query.rewrite_scalar_expressions(rewrite);
235            }
236        }
237    }
238
239    fn add_namespace(&mut self, local: &RowSchema) {
240        self.shadowed_columns
241            .extend(super::schema_public_columns(local));
242        for identity in self.replacements.keys() {
243            match identity.qualifier() {
244                Some(qualifier) if local.has_qualifier(qualifier) => {
245                    self.shadowed_qualifiers.insert(qualifier.to_owned());
246                }
247                None if local.has_unqualified_column(identity.column())
248                    || local.has_qualifier(identity.column()) =>
249                {
250                    self.shadowed_columns.insert(identity.column().to_owned());
251                }
252                _ => {}
253            }
254        }
255    }
256
257    fn in_namespace(&self, local: &RowSchema) -> Self {
258        let mut rewrite = self.clone();
259        rewrite.add_namespace(local);
260        if local.columns_are_open(None) {
261            Arc::make_mut(&mut rewrite.replacements)
262                .retain(|identity, _| identity.qualifier().is_some());
263        }
264        rewrite
265    }
266
267    fn expression(&self, expression: &mut ScalarExpr, subqueries: &mut Vec<QueryPlan>) {
268        crate::plan::rewrite_scalar_expression(expression, &mut |node| {
269            if let ScalarExpr::ScalarSubquery(id)
270            | ScalarExpr::Exists { subquery: id, .. }
271            | ScalarExpr::InSubquery { subquery: id, .. } = node
272            {
273                if let Some(query) = subqueries.get_mut(*id) {
274                    self.query(query);
275                }
276                return;
277            }
278            let identity = match node {
279                ScalarExpr::Column(column) if !self.shadowed_columns.contains(column.as_str()) => {
280                    ColumnIdentity::unqualified(column.as_str())
281                }
282                ScalarExpr::QualifiedStar(qualifier)
283                    if !self.shadowed_qualifiers.contains(qualifier.as_str()) =>
284                {
285                    ColumnIdentity::unqualified(qualifier.as_str())
286                }
287                ScalarExpr::QualifiedColumn { qualifier, column }
288                    if !self.shadowed_qualifiers.contains(qualifier) =>
289                {
290                    ColumnIdentity::qualified(qualifier.as_str(), column.as_str())
291                }
292                _ => return,
293            };
294            let Some(replacement) = self.replacements.get(&identity) else {
295                return;
296            };
297            let offset = subqueries.len();
298            let mut replacement = replacement.clone();
299            self.bind_replacement_columns(&mut replacement);
300            let mut replacement = replacement.expression;
301            crate::plan::rewrite_scalar_expression(
302                &mut replacement.scalar,
303                &mut |node| match node {
304                    ScalarExpr::ScalarSubquery(id)
305                    | ScalarExpr::Exists { subquery: id, .. }
306                    | ScalarExpr::InSubquery { subquery: id, .. } => *id += offset,
307                    _ => {}
308                },
309            );
310            subqueries.extend(replacement.subqueries);
311            *node = replacement.scalar;
312        });
313    }
314
315    fn block(&self, block: &mut QueryBlockPlan) {
316        for expression in block
317            .projections
318            .iter_mut()
319            .map(|projection| &mut projection.expr)
320            .chain(block.r#where.iter_mut())
321            .chain(&mut block.group_by)
322            .chain(block.grouping_sets.iter_mut().flatten())
323            .chain(block.having.iter_mut())
324            .chain(block.order_by.iter_mut().map(|order| &mut order.expr))
325            .chain(block.limit.iter_mut())
326            .chain(block.offset.iter_mut())
327            .chain(&mut block.distinct_on)
328            .chain(
329                block
330                    .windows
331                    .iter_mut()
332                    .flat_map(|window| window.spec.expressions_mut()),
333            )
334        {
335            self.expression(expression, &mut block.subqueries);
336        }
337    }
338
339    fn query(&self, query: &mut QueryPlan) {
340        for cte in &mut query.ctes {
341            if let Some(query) = cte.body.query_mut() {
342                self.query(query);
343            }
344        }
345        match &mut query.root {
346            RelationalPlan::QueryBlock(block) => {
347                if let Some(previous) = block
348                    .deferred_outer_rewrites
349                    .iter_mut()
350                    .find(|previous| Arc::ptr_eq(&previous.outer_columns, &self.outer_columns))
351                {
352                    Arc::make_mut(&mut previous.replacements).extend(
353                        self.replacements
354                            .iter()
355                            .map(|(identity, expression)| (identity.clone(), expression.clone())),
356                    );
357                    previous
358                        .shadowed_columns
359                        .extend(self.shadowed_columns.iter().cloned());
360                    previous
361                        .shadowed_qualifiers
362                        .extend(self.shadowed_qualifiers.iter().cloned());
363                } else {
364                    block.deferred_outer_rewrites.push(self.clone());
365                }
366            }
367            RelationalPlan::Values { rows, subqueries } => {
368                for expression in rows.iter_mut().flatten() {
369                    self.expression(expression, subqueries);
370                }
371            }
372            RelationalPlan::SetOp {
373                left,
374                right,
375                order_by,
376                limit,
377                offset,
378                subqueries,
379                ..
380            } => {
381                self.query(left);
382                self.query(right);
383                for expression in order_by
384                    .iter_mut()
385                    .map(|order| &mut order.expr)
386                    .chain(limit.iter_mut().map(Box::as_mut))
387                    .chain(offset.iter_mut().map(Box::as_mut))
388                {
389                    self.expression(expression, subqueries);
390                }
391            }
392        }
393    }
394}
395
396fn column_references(block: &QueryBlockPlan) -> BTreeSet<ColumnIdentity> {
397    let mut references = BTreeSet::new();
398    let mut visit = |expression: &ScalarExpr| {
399        expression.visit(&mut |node| match node {
400            ScalarExpr::Column(column) => {
401                references.insert(ColumnIdentity::unqualified(column));
402            }
403            ScalarExpr::QualifiedColumn { qualifier, column } => {
404                references.insert(ColumnIdentity::qualified(qualifier, column));
405            }
406            _ => {}
407        });
408    };
409    for expression in block
410        .projections
411        .iter()
412        .map(|projection| &projection.expr)
413        .chain(block.r#where.iter())
414        .chain(&block.group_by)
415        .chain(block.grouping_sets.iter().flatten())
416        .chain(block.having.iter())
417        .chain(block.order_by.iter().map(|order| &order.expr))
418        .chain(block.limit.iter())
419        .chain(block.offset.iter())
420        .chain(&block.distinct_on)
421        .chain(
422            block
423                .windows
424                .iter()
425                .flat_map(|window| window.spec.expressions()),
426        )
427    {
428        visit(expression);
429    }
430    if let Some(source) = &block.from {
431        source.visit_scalar_expressions(&mut visit);
432    }
433    for query in &block.subqueries {
434        query.visit_scalar_expressions(&mut visit);
435    }
436    for rewrite in &block.deferred_outer_rewrites {
437        rewrite.visit_scalar_expressions(&mut visit);
438    }
439    references
440}