Line data Source code
1 : //! Name resolution.
2 : //!
3 : //! The visit collects table references, derived tables, column references, result targets, CTEs and
4 : //! declarations bottom-up and groups them into name scopes. Finish resolves the names of all scopes,
5 : //! populates derived tables, assigns statement ids and runs the schema inference.
6 : //!
7 : //! Column refs resolve against the FROM items of a scope (tables, CTEs, derived tables), each with
8 : //! its ordered columns. Expression subqueries see the FROM items of their parents, derived tables and
9 : //! CTEs only those above their parent, lateral derived tables also the FROM items before them.
10 : //!
11 : //! The node states hold vectors of ids, and merging a child moves its entries to the end.
12 :
13 : use super::state::{quote_identifier, AnalysisState};
14 : use super::types::*;
15 : use crate::catalog::*;
16 : use crate::table_parameters::{TableParameterLookup, TABLE_PARAMETERS_ENTRY_ID};
17 : use dashql_buffers::analyzer::{AnalyzerErrorSeverity, AnalyzerErrorType, NameTag, SemanticNodeMarkerType};
18 : use dashql_buffers::parser::{AttributeKey as K, JoinType, Node, NodeType, StatementType, SymbolSpan};
19 : use dashql_parser::attrs;
20 : use crate::hash::{HashMap, HashSet};
21 : use std::ops::Range;
22 : use std::sync::Arc;
23 :
24 : /// The maximum number of tables a reference may resolve to
25 : const MAX_TABLE_REF_AMBIGUITY: usize = 100;
26 :
27 : /// A table column collected from a column definition
28 : #[derive(Clone)]
29 : struct PendingColumn {
30 : /// The AST node id of the column definition
31 : ast_node_id: u32,
32 : /// The column name
33 : column_name: Name,
34 : }
35 :
36 : /// The state of a node during name resolution
37 : #[derive(Default)]
38 : struct NodeState {
39 : /// The scopes created in the subtree that have no parent scope yet
40 : child_scopes: Vec<ScopeId>,
41 : /// The column definitions of a CREATE TABLE
42 : table_columns: Vec<PendingColumn>,
43 : /// The table references not yet attached to a scope
44 : table_references: Vec<TableRefId>,
45 : /// The column ref expressions not yet attached to a scope
46 : column_references: Vec<ExprId>,
47 : /// The result targets of the enclosing SELECT
48 : result_targets: Vec<ResultTarget>,
49 : /// The CTE definitions of the enclosing WITH clause
50 : ctes: Vec<CteDefinition>,
51 : /// The derived tables, the FROM items of the next scope
52 : derived_tables: Vec<ScopeSource>,
53 : /// The joins with USING or NATURAL of the next scope
54 : using_joins: Vec<UsingJoin>,
55 : }
56 :
57 : /// Move the entries of a list to the end of another one. Takes over the buffer if the destination is
58 : /// empty, so states move up the tree without copying.
59 : #[inline]
60 495120 : fn append<T>(dst: &mut Vec<T>, src: &mut Vec<T>) {
61 495120 : if dst.is_empty() {
62 478471 : std::mem::swap(dst, src);
63 478471 : } else {
64 16649 : dst.append(src);
65 16649 : }
66 495120 : }
67 :
68 : impl NodeState {
69 61890 : fn merge(&mut self, other: &mut NodeState) {
70 61890 : append(&mut self.child_scopes, &mut other.child_scopes);
71 61890 : append(&mut self.table_columns, &mut other.table_columns);
72 61890 : append(&mut self.table_references, &mut other.table_references);
73 61890 : append(&mut self.column_references, &mut other.column_references);
74 61890 : append(&mut self.result_targets, &mut other.result_targets);
75 61890 : append(&mut self.ctes, &mut other.ctes);
76 61890 : append(&mut self.derived_tables, &mut other.derived_tables);
77 61890 : append(&mut self.using_joins, &mut other.using_joins);
78 61890 : }
79 :
80 5610 : fn clear(&mut self) {
81 5610 : *self = NodeState::default();
82 5610 : }
83 : }
84 :
85 : /// A join with USING, or NATURAL that uses all common columns. The USING columns of both inputs
86 : /// are one column of the join.
87 : struct UsingJoin {
88 : /// The AST node id of the joined table
89 : ast_node_id: u32,
90 : /// The USING columns, all common columns of a NATURAL join if None
91 : using: Option<Vec<Arc<str>>>,
92 : }
93 :
94 : impl UsingJoin {
95 9 : fn uses(&self, column_name: &str) -> bool {
96 9 : self.using.as_ref().is_none_or(|using| using.iter().any(|c| &**c == column_name))
97 9 : }
98 : }
99 :
100 : /// The result of looking up a column ref in the FROM items of a scope
101 : #[derive(Clone, Copy, PartialEq, Eq)]
102 : enum Lookup {
103 : Resolved,
104 : Ambiguous,
105 : Missing,
106 : }
107 :
108 : /// How a column ref sees the output columns of its own scope
109 : #[derive(Clone, Copy, PartialEq, Eq)]
110 : enum OutputNames {
111 : Invisible,
112 : /// A bare name in ORDER BY refers to an output column before a FROM item column
113 : Preferred,
114 : /// A bare name in GROUP BY refers to an output column if no FROM item has the column
115 : Fallback,
116 : }
117 :
118 : /// A declaration whose columns are derived after its SELECT scope is resolved
119 : struct PendingDerivedTable {
120 : /// The table declaration (index into the table declarations of the script)
121 : table: u32,
122 : /// The AST node id of the SELECT that defines the columns
123 : select_node_id: u32,
124 : /// The declared column names, they rename the leading output columns
125 : column_aliases: Vec<Name>,
126 : }
127 :
128 : /// The root scopes.
129 : ///
130 : /// The set iterates in insertion order, and erasing moves the last element into the hole (see
131 : /// docs/design/core_quirks.md).
132 : #[derive(Default)]
133 : struct RootScopes {
134 : /// The root scopes in insertion order
135 : values: Vec<ScopeId>,
136 : /// The position of every root scope in the values
137 : positions: HashMap<ScopeId, usize>,
138 : }
139 :
140 : impl RootScopes {
141 5595 : fn insert(&mut self, scope: ScopeId) {
142 5595 : if self.positions.contains_key(&scope) {
143 0 : return;
144 5595 : }
145 5595 : self.positions.insert(scope, self.values.len());
146 5595 : self.values.push(scope);
147 5595 : }
148 :
149 580 : fn erase(&mut self, scope: ScopeId) {
150 580 : let Some(pos) = self.positions.remove(&scope) else { return };
151 580 : let last = self.values.pop().unwrap();
152 580 : if pos < self.values.len() {
153 70 : self.values[pos] = last;
154 70 : self.positions.insert(last, pos);
155 510 : }
156 580 : }
157 : }
158 :
159 : /// The pass that groups names into scopes and resolves tables and columns
160 : pub(super) struct NameResolutionPass {
161 : /// The state of every AST node
162 : node_states: Vec<NodeState>,
163 : /// Does the script contain property graph syntax?
164 : has_graph_syntax: bool,
165 : /// The scopes without a parent scope
166 : root_scopes: RootScopes,
167 : /// The table declarations whose columns are derived after resolution
168 : pending_derived_tables: Vec<PendingDerivedTable>,
169 : /// The joins with USING or NATURAL of the scopes
170 : using_joins: HashMap<ScopeId, Vec<UsingJoin>>,
171 : /// The column refs that were reported as ambiguous
172 : ambiguous_column_refs: HashSet<ExprId>,
173 : }
174 :
175 : impl NameResolutionPass {
176 3734 : pub fn new(state: &AnalysisState) -> Self {
177 3734 : let mut node_states = Vec::with_capacity(state.ast.len());
178 3734 : node_states.resize_with(state.ast.len(), NodeState::default);
179 3734 : let has_graph_syntax = state
180 3734 : .ast
181 3734 : .iter()
182 78636 : .any(|n| matches!(n.node_type(), NodeType::OBJECT_SQL_PROPERTY_GRAPH | NodeType::OBJECT_SQL_GRAPH_TABLE));
183 3734 : Self {
184 3734 : node_states,
185 3734 : has_graph_syntax,
186 3734 : root_scopes: RootScopes::default(),
187 3734 : pending_derived_tables: Vec::new(),
188 3734 : using_joins: HashMap::default(),
189 3734 : ambiguous_column_refs: HashSet::default(),
190 3734 : }
191 3734 : }
192 :
193 : /// Merge the states of all children of a node
194 73038 : fn merge_child_states(&mut self, dst: &mut NodeState, node: &Node) {
195 73038 : let begin = node.children_begin_or_value() as usize;
196 73038 : for child in begin..begin + node.children_count() as usize {
197 60158 : dst.merge(&mut self.node_states[child]);
198 60158 : }
199 73038 : }
200 :
201 : /// Create a naming scope
202 5595 : fn create_scope(&mut self, state: &mut AnalysisState, target: &mut NodeState, scope_root: u32) -> ScopeId {
203 5595 : let scope_id = state.out.name_scopes.len() as ScopeId;
204 5595 : state.out.name_scopes_by_root_node.entry(scope_root).or_insert(scope_id);
205 5595 : for &child in &target.child_scopes {
206 580 : state.out.name_scopes[child as usize].parent_scope = Some(scope_id);
207 580 : self.root_scopes.erase(child);
208 580 : }
209 5611 : for &expr in &target.column_references {
210 2656 : if let Some(column_ref) = state.out.expressions[expr as usize].column_ref_mut() {
211 2656 : column_ref.ast_scope_root = Some(scope_root);
212 2656 : }
213 : }
214 5597 : for &table_ref in &target.table_references {
215 2534 : state.out.table_references[table_ref as usize].ast_scope_root = Some(scope_root);
216 2534 : }
217 5595 : let using_joins = std::mem::take(&mut target.using_joins);
218 5595 : if !using_joins.is_empty() {
219 46 : self.using_joins.insert(scope_id, using_joins);
220 5549 : }
221 5595 : state.out.name_scopes.push(NameScope {
222 5595 : name_scope_id: scope_id,
223 5595 : ast_node_id: scope_root,
224 5595 : child_scopes: std::mem::take(&mut target.child_scopes),
225 5595 : expressions: std::mem::take(&mut target.column_references),
226 5595 : table_references: std::mem::take(&mut target.table_references),
227 5595 : // The table refs are added when they are resolved
228 5595 : sources: std::mem::take(&mut target.derived_tables),
229 5595 : ..Default::default()
230 5595 : });
231 : // Start a new scope
232 5595 : target.clear();
233 5595 : target.child_scopes.push(scope_id);
234 5595 : self.root_scopes.insert(scope_id);
235 5595 : scope_id
236 5595 : }
237 :
238 : /// Register a schema and its database
239 1919 : fn register_schema(state: &mut AnalysisState, database_name: &Name, schema_name: &Name) -> QualifiedCatalogObjectId {
240 1919 : let db_id = match state.out.entry.databases_by_name.get(&database_name.text) {
241 668 : Some(&i) => state.out.entry.database_references[i].object_id,
242 : None => {
243 1251 : let db_id = state.catalog.reserve_database_id(&database_name.text);
244 1251 : let index = state.out.entry.database_references.len();
245 1251 : state.entry_mut().database_references.push(DatabaseReference {
246 1251 : object_id: db_id,
247 1251 : database_name: database_name.text.clone(),
248 1251 : database_alias: Arc::from(""),
249 1251 : });
250 1251 : state.entry_mut().databases_by_name.insert(database_name.text.clone(), index);
251 1251 : state.resolve_name(database_name, CatalogObjectRef::Database(state.loc(index)));
252 1251 : db_id
253 : }
254 : };
255 1919 : let key = (database_name.text.clone(), schema_name.text.clone());
256 1919 : match state.out.entry.schemas_by_qualified_name.get(&key) {
257 655 : Some(&i) => state.out.entry.schema_references[i].object_id,
258 : None => {
259 1264 : let schema_id = state.catalog.reserve_schema_id(&database_name.text, &schema_name.text, db_id);
260 1264 : let index = state.out.entry.schema_references.len();
261 1264 : state.entry_mut().schema_references.push(SchemaReference {
262 1264 : object_id: schema_id,
263 1264 : database_name: database_name.text.clone(),
264 1264 : schema_name: schema_name.text.clone(),
265 1264 : });
266 1264 : state.entry_mut().schemas_by_qualified_name.insert(key, index);
267 1264 : state.resolve_name(schema_name, CatalogObjectRef::Schema(state.loc(index)));
268 1264 : schema_id
269 : }
270 : }
271 1919 : }
272 :
273 1949 : fn is_explain(state: &AnalysisState, statement_id: Option<u32>) -> bool {
274 1949 : statement_id
275 1949 : .and_then(|id| state.parsed.statements.get(id as usize))
276 1949 : .is_some_and(|s| s.statement_type == StatementType::EXPLAIN)
277 1949 : }
278 :
279 : /// Register a table-like declaration backed by a SELECT scope
280 180 : fn register_derived_table(
281 180 : &mut self,
282 180 : state: &mut AnalysisState,
283 180 : declaration_node: &Node,
284 180 : name_node: Option<&Node>,
285 180 : columns_node: Option<&Node>,
286 180 : select_node: &Node,
287 180 : ) {
288 180 : let declaration_id = state.node_id(declaration_node);
289 : // EXPLAIN describes a declaration, publishing it would create a phantom catalog producer
290 180 : if Self::is_explain(state, state.find_statement_id(declaration_id)) {
291 24 : return;
292 156 : }
293 156 : let Some(table_name) = state.read_qualified_table_name(name_node) else { return };
294 156 : let schema_id = Self::register_schema(state, &table_name.database_name, &table_name.schema_name);
295 156 : let index = state.out.entry.table_declarations.len() as u32;
296 156 : let table_id = state.reserve_table_id(&table_name);
297 156 : let name = table_name.table_name.clone();
298 156 : let mut table = TableDeclaration::new(schema_id, table_id, table_name);
299 156 : table.ast_node_id = Some(declaration_id);
300 156 : table.ast_statement_id = state.find_statement_id(declaration_id);
301 156 : table.ast_scope_root = Some(state.node_id(select_node));
302 156 : table.is_view = declaration_node.node_type() == NodeType::OBJECT_SQL_VIEW;
303 156 : table.location = name_node.map(|n| state.text_span(*n.symbol_span()));
304 156 : state.entry_mut().table_declarations.push(table);
305 156 : state.resolve_name(&name, CatalogObjectRef::Table(TableLoc { entry: state.entry_id, index }));
306 :
307 156 : let mut column_aliases = Vec::new();
308 156 : if let Some(columns) = columns_node.filter(|n| n.node_type() == NodeType::ARRAY) {
309 5 : for column in state.children(columns) {
310 5 : if column.node_type() != NodeType::NAME {
311 0 : continue;
312 5 : }
313 5 : let name = state.node_name(column);
314 5 : state.tag(&name, NameTag::COLUMN_NAME);
315 5 : column_aliases.push(name);
316 : }
317 153 : }
318 156 : self.pending_derived_tables.push(PendingDerivedTable {
319 156 : table: index,
320 156 : select_node_id: state.node_id(select_node),
321 156 : column_aliases,
322 156 : });
323 180 : }
324 :
325 : /// Materialize a pending declaration after its SELECT scope has output columns
326 156 : fn populate_derived_table(state: &mut AnalysisState, pending: &PendingDerivedTable, scope: ScopeId) {
327 156 : let mut output_scope = scope;
328 : {
329 156 : let s = &state.out.name_scopes[scope as usize];
330 156 : if s.output_columns.is_empty() && !s.child_scopes.is_empty() {
331 0 : output_scope = s.child_scopes[0];
332 156 : }
333 : }
334 156 : let outputs = &state.out.name_scopes[output_scope as usize].output_columns;
335 156 : let column_names: Vec<Name> = if !pending.column_aliases.is_empty() {
336 3 : let count = pending.column_aliases.len().min(outputs.len());
337 3 : pending.column_aliases[..count].to_vec()
338 : } else {
339 : // A declared table has unique column names
340 153 : let mut seen = HashSet::default();
341 153 : outputs
342 153 : .iter()
343 173 : .filter(|o| !o.column_name.text.is_empty() && seen.insert(o.column_name.text.clone()))
344 171 : .map(|o| o.column_name.clone())
345 153 : .collect()
346 : };
347 156 : let table_index = pending.table;
348 156 : let table_id = state.out.entry.table_declarations[table_index as usize].table_id();
349 156 : let column_ids = state.reserve_column_ids(table_id, column_names.iter().map(|n| &n.text));
350 176 : for (column_index, column_name) in column_names.into_iter().enumerate() {
351 132 : let table = &mut state.entry_mut().table_declarations[table_index as usize];
352 132 : table.table_columns_by_name.entry(column_name.text.clone()).or_insert(column_index);
353 132 : table.table_columns.push(TableColumn {
354 132 : object_id: QualifiedCatalogObjectId::table_column(table_id, column_ids[column_index]),
355 132 : table: Some(table_id),
356 132 : ast_node_id: None,
357 132 : column_name: column_name.clone(),
358 132 : location: None,
359 132 : });
360 132 : let loc = ColumnLoc {
361 132 : table: TableLoc { entry: state.entry_id, index: table_index },
362 132 : column: column_index as u32,
363 132 : };
364 132 : state.resolve_name(&column_name, CatalogObjectRef::Column(loc));
365 132 : }
366 156 : }
367 :
368 : /// The alias under which a table reference is registered in its scope
369 2523 : fn table_ref_alias(table_ref: &TableReference, fallback: &Arc<str>) -> Arc<str> {
370 2523 : match &table_ref.alias {
371 193 : Some((alias, _)) => alias.text.clone(),
372 2330 : None => fallback.clone(),
373 : }
374 2523 : }
375 :
376 : /// Read an alias clause, the alias name with its location and the column names
377 2606 : fn read_alias(state: &mut AnalysisState, alias: Option<&Node>) -> (Option<(Name, SymbolSpan)>, Vec<Name>) {
378 265 : let (name, columns) = match alias {
379 265 : Some(alias) if alias.node_type() == NodeType::NAME => (Some(alias), None),
380 9 : Some(alias) if alias.node_type() == NodeType::OBJECT_SQL_ALIAS => {
381 9 : let [name, columns] = attrs!(state.children(alias), [K::SQL_ALIAS_NAME, K::SQL_ALIAS_COLUMN_NAMES]);
382 9 : (name.filter(|n| n.node_type() == NodeType::NAME), columns.filter(|n| n.node_type() == NodeType::ARRAY))
383 : }
384 2341 : _ => return (None, Vec::new()),
385 : };
386 265 : let name = name.map(|node| {
387 265 : let name = state.node_name(node);
388 265 : state.tag(&name, NameTag::TABLE_ALIAS);
389 265 : (name, *node.symbol_span())
390 265 : });
391 265 : let mut column_aliases = Vec::new();
392 265 : for column in columns.map(|c| state.children(c)).unwrap_or_default() {
393 13 : if column.node_type() == NodeType::NAME {
394 13 : let column_name = state.node_name(column);
395 13 : state.tag(&column_name, NameTag::COLUMN_NAME);
396 13 : column_aliases.push(column_name);
397 13 : }
398 : }
399 265 : (name, column_aliases)
400 2606 : }
401 :
402 : /// The FROM item of a table parameter `:foo` that reads the result of the script `foo.sql` or the attachment
403 : /// `foo.parquet`, None if the parameter is positional, the target of a write, ambiguous, or names no table parameter
404 : /// with columns
405 845 : fn table_parameter_source(state: &mut AnalysisState, node_id: u32, node: &Node, table_node: Option<&Node>, alias_node: Option<&Node>) -> Option<(ScopeSource, TableRefId)> {
406 845 : let parameter = table_node.filter(|n| n.node_type() == NodeType::OBJECT_SQL_PARAMETER_REF)?;
407 694 : if matches!(node.attribute_key(), K::SQL_INSERT_TARGET | K::SQL_DELETE_TARGET) {
408 21 : return None;
409 673 : }
410 673 : let results = state.out.table_parameters.clone()?;
411 16 : let [name] = attrs!(state.children(parameter), [K::SQL_PARAMETER_NAME]);
412 16 : let name = name.and_then(|n| state.read_name_path(n).last().map(|&id| state.name(id).text))?;
413 16 : let name: Arc<str> = match name.strip_prefix('\'').and_then(|n| n.strip_suffix('\'')) {
414 0 : Some(inner) => inner.into(),
415 16 : None => name,
416 : };
417 16 : let TableParameterLookup::Found(index) = results.find(&name) else { return None };
418 12 : let table = results.entries[index].table.as_ref()?;
419 11 : let (alias, column_aliases) = Self::read_alias(state, alias_node);
420 : // A table reference that is resolved already, the cursor, the focus and the semantic spans see the parameter
421 : // like a table. Scope resolution, the planner and the script references skip it.
422 11 : let id = state.out.table_references.len() as TableRefId;
423 11 : state.out.table_references.push(TableReference {
424 11 : table_reference_id: ExternalObjectId::new(state.entry_id, id),
425 11 : ast_node_id: node_id,
426 11 : location: Some(*node.symbol_span()),
427 11 : ast_statement_id: None,
428 11 : ast_scope_root: None,
429 11 : alias: alias.clone(),
430 11 : column_aliases: column_aliases.clone(),
431 11 : inner: Some(RelationExpression {
432 11 : table_name: table.table_name.clone(),
433 11 : resolved_table: Some(ResolvedTableEntry {
434 11 : table_name: table.table_name.clone(),
435 11 : catalog_schema_id: table.catalog_schema_id,
436 11 : catalog_table_id: table.object_id,
437 11 : referenced_catalog_version: table.catalog_version,
438 11 : }),
439 11 : resolved_alternatives: Vec::new(),
440 11 : }),
441 11 : role: TableRole::Read,
442 11 : });
443 11 : state.mark(node_id, SemanticNodeMarkerType::TABLE_REFERENCE);
444 11 : let source = ScopeSource {
445 11 : ast_node_id: node_id,
446 11 : name: Some(alias.map(|(alias, _)| alias.text).unwrap_or(name)),
447 11 : column_aliases,
448 11 : table: ReferencedTable::Table(TableLoc { entry: TABLE_PARAMETERS_ENTRY_ID, index: index as u32 }),
449 : };
450 11 : Some((source, id))
451 845 : }
452 :
453 : /// Is a FROM item a table parameter?
454 5208 : fn is_table_parameter(source: &ScopeSource) -> bool {
455 3990 : matches!(source.table, ReferencedTable::Table(loc) if loc.entry == TABLE_PARAMETERS_ENTRY_ID)
456 5208 : }
457 :
458 : /// Add a FROM item to a scope, unless its name is taken
459 2604 : fn add_source(state: &mut AnalysisState, scope: ScopeId, source: ScopeSource) {
460 2604 : if let Some(name) = &source.name {
461 2599 : if state.out.name_scopes[scope as usize].source(name).is_some() {
462 8 : let message = format!("duplicate table alias {}", quote_identifier(name));
463 8 : state.add_error(AnalyzerErrorType::DUPLICATE_TABLE_ALIAS, AnalyzerErrorSeverity::ERROR, source.ast_node_id, message);
464 8 : return;
465 2591 : }
466 5 : }
467 2596 : state.out.name_scopes[scope as usize].sources.push(source);
468 2604 : }
469 :
470 : /// Resolve all table refs in a scope and register the FROM items
471 5595 : fn resolve_table_refs_in_scope(state: &mut AnalysisState, scope: ScopeId) {
472 : // The derived tables were added when the scope was created
473 5595 : let mut sources = std::mem::take(&mut state.out.name_scopes[scope as usize].sources);
474 5595 : let table_refs = state.out.name_scopes[scope as usize].table_references.clone();
475 5597 : for table_ref_id in table_refs {
476 2534 : let table_ref = &state.out.table_references[table_ref_id as usize];
477 2534 : let Some(relation) = &table_ref.inner else { continue };
478 : // The result of a script is a FROM item already
479 2534 : if table_ref.reads_table_parameter() {
480 11 : continue;
481 2523 : }
482 2523 : if relation.resolved_table.is_some() {
483 0 : continue;
484 2523 : }
485 2523 : let table_name = relation.table_name.clone();
486 2523 : let ref_name = table_name.table_name.text.clone();
487 2523 : let role = table_ref.role;
488 2523 : let reference_offset = state.ast[table_ref.ast_node_id as usize].symbol_span().offset();
489 2523 : let source = |table_ref: &TableReference, name: Arc<str>, table: ReferencedTable| ScopeSource {
490 2523 : ast_node_id: table_ref.ast_node_id,
491 2523 : name: Some(name),
492 2523 : column_aliases: table_ref.column_aliases.clone(),
493 2523 : table,
494 2523 : };
495 :
496 : // Does the table ref match a CTE definition in this or any parent scope?
497 2523 : let mut matched_cte = None;
498 2523 : let mut s = Some(scope);
499 5190 : while let Some(sid) = s {
500 2808 : let candidate = &state.out.name_scopes[sid as usize];
501 2808 : if let Some(index) = candidate.cte_definitions.get_index(&ref_name) {
502 145 : let mut visible = true;
503 145 : if !candidate.ctes_recursive {
504 116 : let definition = &state.ast[candidate.cte_definitions.at(index).definition_node_id as usize];
505 116 : let span = definition.symbol_span();
506 116 : let definition_end = span.offset() + span.length();
507 116 : visible = reference_offset > definition_end;
508 116 : }
509 145 : if visible {
510 141 : matched_cte = Some(CteLoc {
511 141 : scope: sid,
512 141 : index: index as u32,
513 141 : });
514 141 : break;
515 4 : }
516 2663 : }
517 2667 : s = candidate.parent_scope;
518 : }
519 2523 : if let (Some(cte), TableRole::Read) = (matched_cte, role) {
520 140 : let table_ref = &state.out.table_references[table_ref_id as usize];
521 140 : sources.push(source(table_ref, Self::table_ref_alias(table_ref, &ref_name), ReferencedTable::Cte(cte)));
522 140 : continue;
523 2383 : }
524 :
525 : // Resolve as a table of the own script, then through the catalog
526 2383 : let mut resolved = Vec::new();
527 2383 : state.out.entry.resolve_table(&table_name, &mut resolved, MAX_TABLE_REF_AMBIGUITY);
528 2383 : if resolved.is_empty() {
529 2206 : state.catalog.resolve_table(&table_name, state.entry_id, &mut resolved, MAX_TABLE_REF_AMBIGUITY);
530 2211 : }
531 2383 : if let Some(&best_loc) = resolved.first() {
532 1984 : let entries: Vec<ResolvedTableEntry> = resolved
533 1984 : .iter()
534 1998 : .filter_map(|&loc| state.table(loc))
535 1984 : .map(|t| ResolvedTableEntry {
536 1998 : table_name: t.table_name.clone(),
537 1998 : catalog_schema_id: t.catalog_schema_id,
538 1998 : catalog_table_id: t.object_id,
539 1998 : referenced_catalog_version: t.catalog_version,
540 1998 : })
541 1984 : .collect();
542 1984 : let best_name = entries[0].table_name.table_name.text.clone();
543 1984 : let relation = state.out.table_references[table_ref_id as usize].inner.as_mut().unwrap();
544 1984 : let mut entries = entries.into_iter();
545 1984 : relation.resolved_table = entries.next();
546 1984 : relation.resolved_alternatives.extend(entries);
547 1984 : let table_ref = &state.out.table_references[table_ref_id as usize];
548 1984 : sources.push(source(table_ref, Self::table_ref_alias(table_ref, &best_name), ReferencedTable::Table(best_loc)));
549 1984 : continue;
550 399 : }
551 :
552 : // Neither a CTE nor in the catalog. Register an unresolved relation so that columns used
553 : // against it can be associated for schema inference.
554 399 : let table_ref = &state.out.table_references[table_ref_id as usize];
555 399 : let unresolved = ReferencedTable::Unresolved(UnresolvedRelation {
556 399 : table_ref: table_ref_id,
557 399 : table_name,
558 399 : });
559 399 : sources.push(source(table_ref, Self::table_ref_alias(table_ref, &ref_name), unresolved));
560 : }
561 : // Register the FROM items in FROM order, table refs follow the nodes of earlier FROM items in
562 : // the post-order AST
563 5595 : sources.sort_by_key(|s| s.ast_node_id);
564 : // The result of a script yields its name to the other FROM items, the planner renames its common table
565 : // expression as well
566 5597 : let taken: HashSet<Arc<str>> = sources.iter().filter(|s| !Self::is_table_parameter(s)).filter_map(|s| s.name.clone()).collect();
567 5597 : for source in sources.iter_mut().filter(|s| Self::is_table_parameter(s)) {
568 11 : if source.name.as_ref().is_some_and(|n| taken.contains(n)) {
569 1 : source.name = None;
570 10 : }
571 : }
572 5597 : for source in sources {
573 2604 : Self::add_source(state, scope, source);
574 2604 : }
575 5595 : }
576 :
577 : /// Find a column among the columns of a FROM item, the column aliases rename the leading columns
578 3299 : fn find_column(aliases: &[Name], column_count: usize, column_name: &str, by_name: Option<usize>) -> Option<usize> {
579 3299 : match aliases.iter().position(|a| &*a.text == column_name) {
580 71 : Some(column) => (column < column_count).then_some(column),
581 3228 : None => by_name.filter(|&column| column >= aliases.len()),
582 : }
583 3299 : }
584 :
585 : /// Resolve a column against the output columns of a scope
586 225 : fn resolve_scope_column(state: &AnalysisState, scope: ScopeId, aliases: &[Name], column_name: &str) -> ColumnResolution {
587 225 : let s = &state.out.name_scopes[scope as usize];
588 225 : let by_name = s.output_columns_by_name.get(column_name).copied();
589 225 : match Self::find_column(aliases, s.output_columns.len(), column_name, by_name) {
590 141 : Some(column) => ColumnResolution::ScopeColumn {
591 141 : scope,
592 141 : column: column as u32,
593 141 : },
594 84 : None => ColumnResolution::Unresolved,
595 : }
596 225 : }
597 :
598 : /// Resolve a column against a FROM item
599 3705 : fn resolve_column(state: &AnalysisState, source: &ScopeSource, column_name: &str) -> ColumnResolution {
600 3705 : match &source.table {
601 3074 : ReferencedTable::Table(loc) => {
602 3074 : let Some(table) = state.table(*loc) else { return ColumnResolution::Unresolved };
603 3074 : let by_name = table.table_columns_by_name.get(column_name).copied();
604 3074 : match Self::find_column(&source.column_aliases, table.table_columns.len(), column_name, by_name) {
605 1903 : Some(column) => ColumnResolution::TableColumn(ColumnLoc {
606 1903 : table: *loc,
607 1903 : column: column as u32,
608 1903 : }),
609 1171 : None => ColumnResolution::Unresolved,
610 : }
611 : }
612 : // An unresolved relation has an unknown schema
613 406 : ReferencedTable::Unresolved(_) => ColumnResolution::Unresolved,
614 127 : ReferencedTable::Cte(loc) => {
615 127 : let cte = state.out.name_scopes[loc.scope as usize].cte_definitions.at(loc.index as usize);
616 127 : let Some(child) = cte.child_scope else {
617 0 : return ColumnResolution::Unresolved;
618 : };
619 127 : let aliases = if source.column_aliases.is_empty() { &cte.column_aliases } else { &source.column_aliases };
620 127 : Self::resolve_scope_column(state, child, aliases, column_name)
621 : }
622 98 : ReferencedTable::Subquery(child) => Self::resolve_scope_column(state, *child, &source.column_aliases, column_name),
623 : }
624 3705 : }
625 :
626 : /// Is a node within the subtree of another one?
627 15 : fn is_within(state: &AnalysisState, mut node_id: u32, ancestor: u32) -> bool {
628 : // Parents follow their children in the post-order AST
629 43 : while node_id < ancestor {
630 28 : let parent = state.ast[node_id as usize].parent();
631 : // Statement roots are their own parents
632 28 : if parent == node_id || parent as usize >= state.ast.len() {
633 0 : return false;
634 28 : }
635 28 : node_id = parent;
636 : }
637 15 : node_id == ancestor
638 15 : }
639 :
640 : /// Do the FROM items that have a column all lie within a join that uses it?
641 36 : fn is_using_column(&self, state: &AnalysisState, scope: ScopeId, source_nodes: &[u32], column_name: &str) -> bool {
642 36 : let Some(joins) = self.using_joins.get(&scope) else { return false };
643 9 : joins.iter().any(|join| {
644 15 : join.uses(column_name) && source_nodes.iter().all(|&node_id| Self::is_within(state, node_id, join.ast_node_id))
645 9 : })
646 36 : }
647 :
648 : /// Look up a column ref in the visible FROM items of a scope
649 3472 : fn try_resolve_column_in_scope(&mut self, state: &mut AnalysisState, expr: ExprId, target: ScopeId, visibility: SourceVisibility) -> Lookup {
650 3472 : let Some(column_ref) = state.out.expressions[expr as usize].column_ref() else { return Lookup::Missing };
651 3472 : let column_name = column_ref.column_name.column_name.text.clone();
652 3472 : let alias = column_ref.column_name.table_alias.as_ref().map(|a| a.text.clone());
653 3472 : let scope = &state.out.name_scopes[target as usize];
654 4522 : let mut sources = scope.sources.iter().filter(|s| visibility.sees(s));
655 :
656 3472 : if let Some(alias) = alias {
657 613 : let Some(source) = sources.find(|s| s.name.as_deref() == Some(&*alias)) else { return Lookup::Missing };
658 310 : let resolution = Self::resolve_column(state, source, &column_name);
659 310 : if !resolution.is_resolved() {
660 112 : return Lookup::Missing;
661 198 : }
662 198 : state.out.expressions[expr as usize].column_ref_mut().unwrap().resolved = resolution;
663 198 : return Lookup::Resolved;
664 2941 : }
665 :
666 : // No table alias, scan all FROM items for the column and check for ambiguity
667 2941 : let mut candidates = Vec::new();
668 3893 : for source in sources {
669 3395 : let resolution = Self::resolve_column(state, source, &column_name);
670 3395 : if resolution.is_resolved() {
671 1846 : candidates.push((source.ast_node_id, source.name.clone(), resolution));
672 2534 : }
673 : }
674 2941 : let resolution = match candidates.as_slice() {
675 2941 : [] => return Lookup::Missing,
676 1773 : [(_, _, resolution)] => *resolution,
677 : // A USING column resolves to the column of the first input
678 36 : [(_, _, resolution), ..]
679 36 : if self.is_using_column(state, target, &candidates.iter().map(|c| c.0).collect::<Vec<_>>(), &column_name) =>
680 : {
681 6 : *resolution
682 : }
683 : _ => {
684 30 : let mut message = String::from("column reference is ambiguous, candidates: ");
685 61 : for (i, (_, table_name, _)) in candidates.iter().enumerate() {
686 61 : if i > 0 {
687 31 : message.push_str(", ");
688 31 : }
689 61 : match table_name {
690 60 : Some(table_name) => message.push_str("e_identifier(table_name)),
691 1 : None => message.push_str("(subquery)"),
692 : }
693 61 : message.push('.');
694 61 : message.push_str("e_identifier(&column_name));
695 : }
696 30 : let node_id = state.out.expressions[expr as usize].ast_node_id;
697 30 : state.add_error(AnalyzerErrorType::COLUMN_REF_AMBIGUOUS, AnalyzerErrorSeverity::ERROR, node_id, message);
698 30 : self.ambiguous_column_refs.insert(expr);
699 30 : return Lookup::Ambiguous;
700 : }
701 : };
702 1779 : state.out.expressions[expr as usize].column_ref_mut().unwrap().resolved = resolution;
703 1779 : Lookup::Resolved
704 3472 : }
705 :
706 : /// Try to resolve a column ref against the output columns of a scope
707 60 : fn try_resolve_column_from_outputs(state: &mut AnalysisState, expr: ExprId, target: ScopeId) -> bool {
708 60 : let Some(column_ref) = state.out.expressions[expr as usize].column_ref() else { return false };
709 60 : if column_ref.column_name.table_alias.is_some() {
710 0 : return false;
711 60 : }
712 60 : let scope = &state.out.name_scopes[target as usize];
713 60 : match scope.output_columns_by_name.get(&column_ref.column_name.column_name.text) {
714 57 : Some(&column) => {
715 57 : state.out.expressions[expr as usize].column_ref_mut().unwrap().resolved = ColumnResolution::ScopeColumn {
716 57 : scope: target,
717 57 : column: column as u32,
718 57 : };
719 57 : true
720 : }
721 3 : None => false,
722 : }
723 60 : }
724 :
725 7968 : fn is_unresolved_column_ref(state: &AnalysisState, expr: ExprId) -> bool {
726 7968 : state.out.expressions[expr as usize].column_ref().is_some_and(|c| !c.resolved.is_resolved())
727 7968 : }
728 :
729 : /// How a column ref sees the output columns of its scope
730 2656 : fn output_names(state: &AnalysisState, expr: ExprId) -> OutputNames {
731 2656 : let node = &state.ast[state.out.expressions[expr as usize].ast_node_id as usize];
732 2656 : let (output_names, list_key) = match node.attribute_key() {
733 49 : K::SQL_ORDER_VALUE => (OutputNames::Preferred, K::SQL_SELECT_ORDER),
734 59 : K::SQL_GROUP_BY_ITEM_ARG => (OutputNames::Fallback, K::SQL_SELECT_GROUPS),
735 2548 : _ => return OutputNames::Invisible,
736 : };
737 : // The item must be in the clause of the SELECT, not in a window or an aggregate
738 108 : let list = state.ast.get(node.parent() as usize).and_then(|item| state.ast.get(item.parent() as usize));
739 108 : if list.is_some_and(|list| list.attribute_key() == list_key) {
740 104 : output_names
741 : } else {
742 4 : OutputNames::Invisible
743 : }
744 2656 : }
745 :
746 : /// Resolve column refs against the FROM items and the output columns of the own scope
747 5595 : fn resolve_column_refs_locally(&mut self, state: &mut AnalysisState, scope: ScopeId) {
748 5595 : let exprs = state.out.name_scopes[scope as usize].expressions.clone();
749 5611 : for expr in exprs {
750 2656 : if !Self::is_unresolved_column_ref(state, expr) {
751 0 : continue;
752 2656 : }
753 2656 : match Self::output_names(state, expr) {
754 2552 : OutputNames::Invisible => {
755 2552 : self.try_resolve_column_in_scope(state, expr, scope, SourceVisibility::All);
756 2552 : }
757 : OutputNames::Preferred => {
758 45 : if !Self::try_resolve_column_from_outputs(state, expr, scope) {
759 1 : self.try_resolve_column_in_scope(state, expr, scope, SourceVisibility::All);
760 44 : }
761 : }
762 : OutputNames::Fallback => {
763 59 : if self.try_resolve_column_in_scope(state, expr, scope, SourceVisibility::All) == Lookup::Missing {
764 15 : Self::try_resolve_column_from_outputs(state, expr, scope);
765 54 : }
766 : }
767 : }
768 : }
769 5595 : }
770 :
771 : /// Resolve column refs by walking up the parent scopes
772 5595 : fn resolve_column_refs_from_parents(&mut self, state: &mut AnalysisState, scope: ScopeId) {
773 5595 : let exprs = state.out.name_scopes[scope as usize].expressions.clone();
774 5611 : for expr in exprs {
775 2656 : if Self::is_unresolved_column_ref(state, expr) && !self.ambiguous_column_refs.contains(&expr) {
776 639 : self.resolve_from_parent_chain(state, expr, scope);
777 2066 : }
778 : }
779 5595 : }
780 :
781 : /// Try the FROM items that a scope sees in its parent scopes, stopping at correlation barriers
782 715 : fn resolve_from_parent_chain(&mut self, state: &mut AnalysisState, expr: ExprId, scope: ScopeId) -> bool {
783 715 : let mut current = scope;
784 : loop {
785 785 : let s = &state.out.name_scopes[current as usize];
786 785 : let (Some(parent), false) = (s.parent_scope, s.column_correlation_barrier) else { return false };
787 115 : match self.try_resolve_column_in_scope(state, expr, parent, s.parent_visibility) {
788 45 : Lookup::Resolved => return true,
789 0 : Lookup::Ambiguous => return false,
790 70 : Lookup::Missing => current = parent,
791 : }
792 : }
793 715 : }
794 :
795 : /// Attach parsed CTE definitions to a scope
796 3856 : fn attach_ctes(state: &mut AnalysisState, scope: ScopeId, ctes: Vec<CteDefinition>) {
797 3856 : for cte in ctes {
798 134 : let Some(&child_scope) = state.out.name_scopes_by_root_node.get(&cte.select_node_id) else { continue };
799 : // A CTE cannot correlate with the FROM items of the statement it is attached to
800 134 : state.out.name_scopes[child_scope as usize].parent_visibility = SourceVisibility::None;
801 134 : let mut column_aliases = Vec::new();
802 134 : if let Some(columns_node_id) = cte.columns_node_id.filter(|_| cte.columns_count > 0) {
803 19 : let columns = &state.ast[columns_node_id as usize];
804 24 : for ci in 0..cte.columns_count as u32 {
805 24 : let column = &state.ast[(columns.children_begin_or_value() + ci) as usize];
806 24 : if column.node_type() == NodeType::NAME {
807 24 : column_aliases.push(state.node_name(column));
808 24 : }
809 : }
810 115 : }
811 134 : let definition = ResolvedCte {
812 134 : cte_name: cte.cte_name.clone(),
813 134 : child_scope: Some(child_scope),
814 134 : definition_node_id: cte.ast_node_id,
815 134 : column_aliases,
816 134 : };
817 134 : let s = &mut state.out.name_scopes[scope as usize];
818 134 : s.cte_definitions.insert(cte.cte_name.text.clone(), definition);
819 134 : s.cte_definition_nodes.entry(cte.cte_name.text.clone()).or_insert(cte.ast_node_id);
820 : }
821 3856 : }
822 :
823 : /// Look up a FROM item by name in a scope and in the parent scopes it sees
824 267 : fn lookup_source_in_scope_chain<'s>(state: &'s AnalysisState, scope: ScopeId, name: &str) -> Option<&'s ScopeSource> {
825 267 : let mut current = scope;
826 267 : let mut visibility = SourceVisibility::All;
827 : loop {
828 300 : let s = &state.out.name_scopes[current as usize];
829 312 : if let Some(source) = s.sources.iter().find(|x| visibility.sees(x) && x.name.as_deref() == Some(name)) {
830 114 : return Some(source);
831 186 : }
832 186 : let (Some(parent), false) = (s.parent_scope, s.column_correlation_barrier) else { return None };
833 33 : visibility = s.parent_visibility;
834 33 : current = parent;
835 : }
836 267 : }
837 :
838 : /// Resolve qualified column refs whose qualifier is not a table in scope as field accesses of
839 : /// row-typed columns
840 5595 : fn resolve_row_field_accesses(&mut self, state: &mut AnalysisState, scope: ScopeId) {
841 5595 : let exprs = state.out.name_scopes[scope as usize].expressions.clone();
842 5611 : for expr in exprs {
843 2656 : let Some(column_ref) = state.out.expressions[expr as usize].column_ref() else { continue };
844 2656 : if column_ref.resolved.is_resolved() {
845 2031 : continue;
846 625 : }
847 625 : let Some(qualifier) = column_ref.column_name.table_alias.clone() else { continue };
848 135 : if Self::lookup_source_in_scope_chain(state, scope, &qualifier.text).is_some() {
849 57 : continue;
850 78 : }
851 : // In p.x, p is not a table in scope but may be a row-typed column with a field x
852 78 : let qualified = column_ref.column_name.clone();
853 78 : {
854 78 : let column_ref = state.out.expressions[expr as usize].column_ref_mut().unwrap();
855 78 : column_ref.column_name.table_alias = None;
856 78 : column_ref.column_name.column_name = qualifier.clone();
857 78 : }
858 78 : let resolved = self.try_resolve_column_in_scope(state, expr, scope, SourceVisibility::All) == Lookup::Resolved
859 76 : || self.resolve_from_parent_chain(state, expr, scope);
860 78 : if resolved {
861 3 : state.tag(&qualifier, NameTag::COLUMN_NAME);
862 75 : } else {
863 75 : state.out.expressions[expr as usize].column_ref_mut().unwrap().column_name = qualified;
864 75 : }
865 : }
866 5595 : }
867 :
868 : /// Associate still-unresolved column refs with unresolved tables in scope
869 5595 : fn associate_unresolved_columns(state: &mut AnalysisState, scope: ScopeId) {
870 5595 : let s = &state.out.name_scopes[scope as usize];
871 : // The unresolved relations of this scope in FROM order
872 5595 : let local_unresolved: Vec<InferenceCandidate> = s
873 5595 : .sources
874 5595 : .iter()
875 5597 : .filter_map(|source| match &source.table {
876 398 : ReferencedTable::Unresolved(rel) => Some(InferenceCandidate {
877 398 : table_name: rel.table_name.clone(),
878 398 : table_ref: rel.table_ref,
879 398 : }),
880 2198 : _ => None,
881 2596 : })
882 5595 : .collect();
883 :
884 5611 : for expr in s.expressions.clone() {
885 2656 : let expression = &state.out.expressions[expr as usize];
886 2656 : let Some(column_ref) = expression.column_ref() else { continue };
887 2656 : if column_ref.resolved.is_resolved() || column_ref.inferred.is_some() {
888 2034 : continue;
889 622 : }
890 622 : let column_name = column_ref.column_name.column_name.clone();
891 622 : let constraint = match &column_ref.column_name.table_alias {
892 : // Alias-qualified, the owner is pinned to whatever the alias refers to
893 132 : Some(alias) => {
894 34 : let Some(ReferencedTable::Unresolved(rel)) =
895 132 : Self::lookup_source_in_scope_chain(state, scope, &alias.text).map(|s| &s.table)
896 : else {
897 98 : continue;
898 : };
899 34 : InferenceConstraint {
900 34 : kind: InferenceConstraintKind::Forced,
901 34 : expression_id: expression.expression_id,
902 34 : column_name,
903 34 : candidates: vec![InferenceCandidate {
904 34 : table_name: rel.table_name.clone(),
905 34 : table_ref: rel.table_ref,
906 34 : }],
907 34 : }
908 : }
909 : // Unqualified, the candidates are the unresolved tables in scope
910 : None => {
911 490 : if local_unresolved.is_empty() {
912 339 : continue;
913 151 : }
914 : InferenceConstraint {
915 151 : kind: if local_unresolved.len() == 1 {
916 140 : InferenceConstraintKind::Forced
917 : } else {
918 11 : InferenceConstraintKind::Disjunctive
919 : },
920 151 : expression_id: expression.expression_id,
921 151 : column_name,
922 151 : candidates: local_unresolved.clone(),
923 : }
924 : }
925 : };
926 185 : state.out.inference_constraints.push(constraint);
927 : }
928 5595 : }
929 :
930 : /// The columns of a FROM item, as a star forwards them
931 1024 : fn source_columns(state: &AnalysisState, source: &ScopeSource) -> Vec<ScopeColumn> {
932 1024 : let scope_columns = |scope: ScopeId| state.out.name_scopes[scope as usize].output_columns.clone();
933 1024 : let mut columns = match &source.table {
934 654 : ReferencedTable::Table(loc) => match state.table(*loc) {
935 654 : Some(table) => table
936 654 : .table_columns
937 654 : .iter()
938 654 : .enumerate()
939 654 : .map(|(ci, column)| ScopeColumn {
940 860 : column_name: column.column_name.clone(),
941 860 : source: ScopeColumnSource::TableColumn(ColumnLoc {
942 860 : table: *loc,
943 860 : column: ci as u32,
944 860 : }),
945 860 : })
946 654 : .collect(),
947 0 : None => Vec::new(),
948 : },
949 : // An unresolved relation has an unknown schema
950 265 : ReferencedTable::Unresolved(_) => Vec::new(),
951 85 : ReferencedTable::Cte(loc) => {
952 85 : let cte = state.out.name_scopes[loc.scope as usize].cte_definitions.at(loc.index as usize);
953 85 : let mut columns = cte.child_scope.map(scope_columns).unwrap_or_default();
954 85 : for (column, alias) in columns.iter_mut().zip(&cte.column_aliases) {
955 14 : column.column_name = alias.clone();
956 14 : }
957 85 : columns
958 : }
959 20 : ReferencedTable::Subquery(child) => scope_columns(*child),
960 : };
961 1024 : for (column, alias) in columns.iter_mut().zip(&source.column_aliases) {
962 0 : column.column_name = alias.clone();
963 0 : }
964 1024 : columns
965 1024 : }
966 :
967 : /// Populate the output columns of a scope from its result targets
968 5595 : fn populate_output_columns(state: &mut AnalysisState, scope: ScopeId) {
969 5595 : let mut columns = Vec::new();
970 5595 : let scope_node = &state.ast[state.out.name_scopes[scope as usize].ast_node_id as usize];
971 5595 : let [combine_inputs, values] = attrs!(state.children(scope_node), [K::SQL_COMBINE_INPUT, K::SQL_SELECT_VALUES]);
972 5595 : if let Some(combine_inputs) = combine_inputs.filter(|n| n.children_count() > 0) {
973 : // Set operations expose the column names of the left input
974 20 : if let Some(&left) = state.out.name_scopes_by_root_node.get(&combine_inputs.children_begin_or_value()) {
975 20 : columns = state.out.name_scopes[left as usize].output_columns.clone();
976 20 : }
977 5575 : }
978 : // The columns of VALUES are unnamed, aliases of a derived table can name them
979 5595 : if let Some(row) = values.and_then(|v| state.children(v).first()).filter(|r| r.node_type() == NodeType::ARRAY) {
980 254 : for value in state.children(row) {
981 254 : columns.push(ScopeColumn {
982 254 : column_name: state.empty_name(),
983 254 : source: match state.expression_of(state.node_id(value)) {
984 254 : Some(expr) => ScopeColumnSource::Expression(expr),
985 0 : None => ScopeColumnSource::Computed,
986 : },
987 : });
988 : }
989 5378 : }
990 5595 : let mut result_targets = std::mem::take(&mut state.out.name_scopes[scope as usize].result_targets);
991 5618 : for rt in result_targets.iter_mut() {
992 3884 : if rt.is_star {
993 : // Forward the columns of all FROM items, or of the qualified one
994 1317 : let s = &state.out.name_scopes[scope as usize];
995 1361 : for source in &s.sources {
996 1027 : if rt.star_qualifier.as_ref().is_none_or(|q| source.name.as_deref() == Some(q.text())) {
997 1024 : columns.extend(Self::source_columns(state, source));
998 1024 : }
999 : }
1000 1317 : continue;
1001 2567 : }
1002 2567 : let mut expr = rt.expression_id;
1003 2567 : if expr.is_none() {
1004 1047 : let rt_node = &state.ast[rt.ast_node_id as usize];
1005 1047 : let [value] = attrs!(state.children(rt_node), [K::SQL_RESULT_TARGET_VALUE]);
1006 1047 : if let Some(value) = value {
1007 1047 : expr = state.expression_of(state.node_id(value));
1008 1047 : rt.expression_id = expr;
1009 1047 : }
1010 1520 : }
1011 2567 : columns.push(ScopeColumn {
1012 2567 : column_name: rt.column_name.clone().unwrap_or_else(|| state.empty_name()),
1013 : // Computed columns keep their position for column aliases
1014 2567 : source: match expr {
1015 2466 : Some(expr) => ScopeColumnSource::Expression(expr),
1016 101 : None => ScopeColumnSource::Computed,
1017 : },
1018 : });
1019 : }
1020 5595 : let s = &mut state.out.name_scopes[scope as usize];
1021 5595 : s.result_targets = result_targets;
1022 : // A name refers to its first column, references to later ones would be ambiguous
1023 5624 : for column in columns {
1024 3814 : if !column.column_name.text.is_empty() {
1025 2863 : s.output_columns_by_name.entry(column.column_name.text.clone()).or_insert(s.output_columns.len());
1026 2875 : }
1027 3814 : s.output_columns.push(column);
1028 : }
1029 5595 : }
1030 :
1031 : /// Resolve all names
1032 3734 : fn resolve_names(&mut self, state: &mut AnalysisState) {
1033 3734 : let roots = self.root_scopes.values.clone();
1034 :
1035 : // Pass 1, bottom-up: resolve the table refs, populate the output columns for the parent, then
1036 : // resolve the column refs against the own scope
1037 5101 : let mut dfs: Vec<(ScopeId, bool)> = roots.iter().map(|&r| (r, false)).collect();
1038 14924 : while let Some(top) = dfs.last_mut() {
1039 11190 : let scope = top.0;
1040 11190 : if !top.1 {
1041 5595 : top.1 = true;
1042 : // Push children in reverse order so that earlier siblings are processed first
1043 5595 : let children = state.out.name_scopes[scope as usize].child_scopes.clone();
1044 5595 : dfs.extend(children.iter().rev().map(|&c| (c, false)));
1045 5595 : } else {
1046 5595 : dfs.pop();
1047 5595 : Self::resolve_table_refs_in_scope(state, scope);
1048 5595 : Self::populate_output_columns(state, scope);
1049 5595 : self.resolve_column_refs_locally(state, scope);
1050 5595 : }
1051 : }
1052 :
1053 : // Pass 2, top-down: resolve the remaining column refs through the parent scopes
1054 3734 : let mut dfs: Vec<ScopeId> = roots.clone();
1055 9329 : while let Some(scope) = dfs.pop() {
1056 : // Recursive CTE outputs are available only after the bottom-up pass
1057 5611 : for expr in state.out.name_scopes[scope as usize].expressions.clone() {
1058 2656 : if Self::is_unresolved_column_ref(state, expr) && !self.ambiguous_column_refs.contains(&expr) {
1059 667 : self.try_resolve_column_in_scope(state, expr, scope, SourceVisibility::All);
1060 2038 : }
1061 : }
1062 5595 : self.resolve_column_refs_from_parents(state, scope);
1063 5595 : self.resolve_row_field_accesses(state, scope);
1064 5595 : dfs.extend(state.out.name_scopes[scope as usize].child_scopes.iter().copied());
1065 : }
1066 :
1067 : // Pass 3: associate the remaining unresolved columns with unresolved tables, in scope order
1068 5681 : for scope in 0..state.out.name_scopes.len() {
1069 5595 : Self::associate_unresolved_columns(state, scope as ScopeId);
1070 5595 : }
1071 3734 : }
1072 :
1073 : /// Is the node nested inside syntax-only property graph syntax?
1074 13509 : fn is_inside_graph_syntax(&self, state: &AnalysisState, ast_node_id: u32) -> bool {
1075 13509 : if !self.has_graph_syntax {
1076 13436 : return false;
1077 73 : }
1078 73 : let mut node_id = ast_node_id;
1079 73 : for _ in 0..state.ast.len() {
1080 212 : let parent = state.ast[node_id as usize].parent();
1081 212 : if parent as usize >= state.ast.len() {
1082 0 : return false;
1083 212 : }
1084 212 : match state.ast[parent as usize].node_type() {
1085 46 : NodeType::OBJECT_SQL_PROPERTY_GRAPH | NodeType::OBJECT_SQL_GRAPH_TABLE => return true,
1086 : // Statement roots are their own parents
1087 166 : _ if parent == node_id => return false,
1088 139 : _ => node_id = parent,
1089 : }
1090 : }
1091 0 : false
1092 13509 : }
1093 :
1094 3589 : pub fn visit(&mut self, state: &mut AnalysisState, morsel: Range<usize>) {
1095 78912 : for node_id in morsel {
1096 78912 : let node = &state.ast[node_id];
1097 78912 : let mut node_state = std::mem::take(&mut self.node_states[node_id]);
1098 78912 : self.visit_node(state, node, node_id as u32, &mut node_state);
1099 78912 : self.node_states[node_id] = node_state;
1100 78912 : }
1101 3589 : }
1102 :
1103 78912 : fn visit_node(&mut self, state: &mut AnalysisState, node: &Node, node_id: u32, node_state: &mut NodeState) {
1104 78912 : match node.node_type() {
1105 : NodeType::OBJECT_SQL_COLUMN_DEF => {
1106 4059 : let parent = node.parent() as usize;
1107 4059 : if parent < state.ast.len() {
1108 : // Fields of descriptors and row types are not table columns
1109 4059 : let key = state.ast[parent].attribute_key();
1110 4059 : if key == K::SQL_DESCRIPTOR_COLUMNS || key == K::SQL_ROW_TYPE_FIELDS {
1111 13 : return;
1112 4046 : }
1113 0 : }
1114 4046 : let [name] = attrs!(state.children(node), [K::SQL_COLUMN_DEF_NAME]);
1115 4046 : if let Some(name) = name.filter(|n| n.node_type() == NodeType::NAME) {
1116 4046 : let name = state.node_name(name);
1117 4046 : state.tag(&name, NameTag::COLUMN_NAME);
1118 4046 : node_state.table_columns.push(PendingColumn {
1119 4046 : ast_node_id: node_id,
1120 4046 : column_name: name,
1121 4046 : });
1122 4046 : }
1123 : }
1124 :
1125 : NodeType::OBJECT_SQL_COLUMN_REF => {
1126 2687 : if self.is_inside_graph_syntax(state, node_id) {
1127 16 : return;
1128 2671 : }
1129 : // The qualifier of t.* names a FROM item, the result target reads it
1130 2671 : if Self::is_star_qualifier(state, node) {
1131 6 : return;
1132 2665 : }
1133 2665 : let [path] = attrs!(state.children(node), [K::SQL_COLUMN_REF_PATH]);
1134 2665 : if let Some(column_name) = state.read_qualified_column_name(path) {
1135 2665 : let column_ref = ColumnRef {
1136 2665 : column_name,
1137 2665 : ast_scope_root: None,
1138 2665 : resolved: ColumnResolution::Unresolved,
1139 2665 : resolved_ids: None,
1140 2665 : inferred: None,
1141 2665 : };
1142 2665 : let expr = state.add_expression(node_id, *node.symbol_span(), ExpressionInner::ColumnRef(column_ref));
1143 2665 : node_state.column_references.push(expr);
1144 2665 : state.expression_index[node_id as usize] = Some(expr);
1145 2665 : state.mark(node_id, SemanticNodeMarkerType::COLUMN_REFERENCE);
1146 2665 : }
1147 : // Column refs may be recursive
1148 2665 : self.merge_child_states(node_state, node);
1149 : }
1150 :
1151 : NodeType::OBJECT_SQL_TABLEREF => {
1152 3385 : if self.is_inside_graph_syntax(state, node_id) {
1153 15 : return;
1154 3370 : }
1155 3370 : let [name_node, alias_node, table_node, lateral] = attrs!(state.children(node), [
1156 : K::SQL_TABLEREF_NAME,
1157 : K::SQL_TABLEREF_ALIAS,
1158 : K::SQL_TABLEREF_TABLE,
1159 : K::SQL_TABLEREF_LATERAL,
1160 : ]);
1161 3370 : if let Some(name) = state.read_qualified_table_name(name_node) {
1162 2525 : let (alias, column_aliases) = Self::read_alias(state, alias_node);
1163 2525 : let id = state.out.table_references.len() as TableRefId;
1164 2525 : state.out.table_references.push(TableReference {
1165 2525 : table_reference_id: ExternalObjectId::new(state.entry_id, id),
1166 2525 : ast_node_id: node_id,
1167 2525 : location: Some(*node.symbol_span()),
1168 2525 : ast_statement_id: None,
1169 2525 : ast_scope_root: None,
1170 2525 : alias,
1171 2525 : column_aliases,
1172 2525 : inner: Some(RelationExpression {
1173 2525 : table_name: name,
1174 2525 : resolved_table: None,
1175 2525 : resolved_alternatives: Vec::new(),
1176 2525 : }),
1177 2525 : role: TableRole::Read,
1178 2525 : });
1179 2525 : node_state.table_references.push(id);
1180 2525 : state.mark(node_id, SemanticNodeMarkerType::TABLE_REFERENCE);
1181 2542 : } else if let Some((source, table_ref)) = Self::table_parameter_source(state, node_id, node, table_node, alias_node) {
1182 11 : // A table parameter that reads the result of a script of the session
1183 11 : node_state.derived_tables.push(source);
1184 11 : node_state.table_references.push(table_ref);
1185 835 : } else if let Some(select) = table_node.filter(|n| n.node_type() == NodeType::OBJECT_SQL_SELECT) {
1186 : // A derived table, the scope of its SELECT is a FROM item
1187 70 : if let Some(&child) = state.out.name_scopes_by_root_node.get(&state.node_id(select)) {
1188 70 : let (alias, column_aliases) = Self::read_alias(state, alias_node);
1189 70 : state.out.name_scopes[child as usize].parent_visibility = match lateral {
1190 4 : Some(_) => SourceVisibility::Before(node_id),
1191 66 : None => SourceVisibility::None,
1192 : };
1193 70 : node_state.derived_tables.push(ScopeSource {
1194 70 : ast_node_id: node_id,
1195 70 : name: alias.map(|(name, _)| name.text),
1196 70 : column_aliases,
1197 70 : table: ReferencedTable::Subquery(child),
1198 : });
1199 0 : }
1200 764 : }
1201 : // Table refs may be recursive
1202 3370 : self.merge_child_states(node_state, node);
1203 : }
1204 :
1205 : NodeType::OBJECT_SQL_RESULT_TARGET => {
1206 3900 : if self.is_inside_graph_syntax(state, node_id) {
1207 14 : return;
1208 3886 : }
1209 3886 : self.merge_child_states(node_state, node);
1210 3886 : let [value, name, star] = attrs!(state.children(node), [
1211 : K::SQL_RESULT_TARGET_VALUE,
1212 : K::SQL_RESULT_TARGET_NAME,
1213 : K::SQL_RESULT_TARGET_STAR,
1214 : ]);
1215 3886 : let mut rt = ResultTarget {
1216 3886 : ast_node_id: node_id,
1217 3886 : ..Default::default()
1218 3886 : };
1219 3886 : if star.is_some() {
1220 1319 : rt.is_star = true;
1221 1319 : let [path] = value.map(|v| attrs!(state.children(v), [K::SQL_COLUMN_REF_PATH])).unwrap_or([None]);
1222 1319 : if let Some(&qualifier) = path.map(|p| state.read_name_path(p)).unwrap_or_default().last() {
1223 6 : let qualifier = state.name(qualifier);
1224 6 : state.tag(&qualifier, NameTag::TABLE_ALIAS);
1225 6 : rt.star_qualifier = Some(qualifier);
1226 1313 : }
1227 : } else {
1228 2567 : if let Some(name) = name.filter(|n| n.node_type() == NodeType::NAME) {
1229 420 : rt.column_name = Some(state.node_name(name));
1230 2169 : }
1231 2567 : if let Some(expr) = value.and_then(|v| state.expression_of(state.node_id(v))) {
1232 1520 : rt.expression_id = Some(expr);
1233 1520 : if rt.column_name.is_none() {
1234 1462 : if let Some(column_ref) = state.out.expressions[expr as usize].column_ref() {
1235 1462 : rt.column_name = Some(column_ref.column_name.column_name.clone());
1236 1462 : }
1237 58 : }
1238 1047 : }
1239 : }
1240 3886 : node_state.result_targets.push(rt);
1241 : }
1242 :
1243 : NodeType::OBJECT_SQL_CTE => {
1244 142 : let [name, columns, statement] =
1245 142 : attrs!(state.children(node), [K::SQL_CTE_NAME, K::SQL_CTE_COLUMNS, K::SQL_CTE_STATEMENT]);
1246 142 : self.merge_child_states(node_state, node);
1247 142 : if let (Some(name), Some(statement)) = (name.filter(|n| n.node_type() == NodeType::NAME), statement) {
1248 134 : node_state.ctes.push(CteDefinition {
1249 134 : cte_name: state.node_name(name),
1250 134 : select_node_id: state.node_id(statement),
1251 134 : columns_node_id: columns.map(|c| state.node_id(c)),
1252 134 : columns_count: columns.map(|c| c.children_count() as u16).unwrap_or(0),
1253 134 : ast_node_id: node_id,
1254 : });
1255 8 : }
1256 : }
1257 :
1258 : NodeType::OBJECT_SQL_SELECT => {
1259 3537 : if self.is_inside_graph_syntax(state, node_id) {
1260 1 : return;
1261 3536 : }
1262 3536 : self.merge_child_states(node_state, node);
1263 3536 : let result_targets = std::mem::take(&mut node_state.result_targets);
1264 3536 : let ctes = std::mem::take(&mut node_state.ctes);
1265 3536 : let scope = self.create_scope(state, node_state, node_id);
1266 3536 : let [recursive] = attrs!(state.children(node), [K::SQL_SELECT_WITH_RECURSIVE]);
1267 3536 : {
1268 3536 : let s = &mut state.out.name_scopes[scope as usize];
1269 3536 : s.result_targets.extend(result_targets);
1270 3536 : // Completion needs the declaration order and the recursive visibility of CTEs
1271 3536 : s.ctes_recursive = recursive.is_some();
1272 3536 : }
1273 3536 : Self::attach_ctes(state, scope, ctes);
1274 3536 : let [into] = attrs!(state.children(node), [K::SQL_SELECT_INTO]);
1275 3536 : if let Some(into) = into.filter(|n| n.node_type() == NodeType::OBJECT_SQL_INTO) {
1276 23 : let [into_name] = attrs!(state.children(into), [K::SQL_TEMP_NAME]);
1277 23 : self.register_derived_table(state, into, into_name, None, node);
1278 3513 : }
1279 : }
1280 :
1281 : NodeType::OBJECT_SQL_INSERT => {
1282 268 : let [target, columns, source, default_values, returning, recursive] = attrs!(state.children(node), [
1283 : K::SQL_INSERT_TARGET,
1284 : K::SQL_INSERT_COLUMNS,
1285 : K::SQL_INSERT_SOURCE,
1286 : K::SQL_INSERT_DEFAULT_VALUES,
1287 : K::SQL_INSERT_RETURNING,
1288 : K::SQL_SELECT_WITH_RECURSIVE,
1289 : ]);
1290 268 : let target_ref = target.and_then(|t| self.node_states[state.node_id(t) as usize].table_references.first().copied());
1291 268 : let Some(target_ref) = target_ref else {
1292 14 : self.merge_child_states(node_state, node);
1293 14 : return;
1294 : };
1295 254 : state.out.table_references[target_ref as usize].role = TableRole::Write;
1296 :
1297 254 : self.merge_child_states(node_state, node);
1298 254 : let result_targets = std::mem::take(&mut node_state.result_targets);
1299 254 : let ctes = std::mem::take(&mut node_state.ctes);
1300 254 : let scope = self.create_scope(state, node_state, node_id);
1301 254 : {
1302 254 : let s = &mut state.out.name_scopes[scope as usize];
1303 254 : s.result_targets.extend(result_targets);
1304 254 : s.ctes_recursive = recursive.is_some();
1305 254 : }
1306 254 : Self::attach_ctes(state, scope, ctes);
1307 254 : if let Some(source) = source {
1308 253 : if let Some(&source_scope) = state.out.name_scopes_by_root_node.get(&state.node_id(source)) {
1309 253 : state.out.name_scopes[source_scope as usize].column_correlation_barrier = true;
1310 253 : }
1311 1 : }
1312 254 : self.set_cte_correlation_barriers(state, scope);
1313 :
1314 254 : let mut insert = InsertStatement {
1315 254 : ast_node_id: node_id,
1316 254 : ast_statement_id: state.find_statement_id(node_id),
1317 254 : target: target_ref,
1318 254 : source_ast_node_id: source.map(|s| state.node_id(s)),
1319 254 : default_values: default_values.is_some(),
1320 254 : returning: returning.is_some(),
1321 254 : target_columns: Vec::new(),
1322 : };
1323 254 : if let Some(columns) = columns.filter(|n| n.node_type() == NodeType::ARRAY) {
1324 13 : for column in state.children(columns) {
1325 13 : if column.node_type() != NodeType::NAME {
1326 0 : continue;
1327 13 : }
1328 13 : let name = state.node_name(column);
1329 13 : state.tag(&name, NameTag::COLUMN_NAME);
1330 13 : insert.target_columns.push(InsertTargetColumn {
1331 13 : ast_node_id: state.node_id(column),
1332 13 : column_name: name,
1333 13 : resolved: None,
1334 13 : });
1335 : }
1336 245 : }
1337 254 : state.out.insert_statements.push(insert);
1338 : }
1339 :
1340 : NodeType::OBJECT_SQL_DELETE => {
1341 66 : let [target, recursive] = attrs!(state.children(node), [K::SQL_DELETE_TARGET, K::SQL_SELECT_WITH_RECURSIVE]);
1342 66 : if let Some(target) = target {
1343 66 : for &table_ref in &self.node_states[state.node_id(target) as usize].table_references {
1344 59 : state.out.table_references[table_ref as usize].role = TableRole::Write;
1345 59 : }
1346 0 : }
1347 66 : self.merge_child_states(node_state, node);
1348 66 : let result_targets = std::mem::take(&mut node_state.result_targets);
1349 66 : let ctes = std::mem::take(&mut node_state.ctes);
1350 66 : let scope = self.create_scope(state, node_state, node_id);
1351 66 : {
1352 66 : let s = &mut state.out.name_scopes[scope as usize];
1353 66 : s.result_targets.extend(result_targets);
1354 66 : s.ctes_recursive = recursive.is_some();
1355 66 : }
1356 66 : Self::attach_ctes(state, scope, ctes);
1357 : // CTE definitions cannot correlate to the DELETE target or USING relations
1358 66 : self.set_cte_correlation_barriers(state, scope);
1359 : }
1360 :
1361 : NodeType::OBJECT_SQL_JOINED_TABLE => {
1362 68 : self.merge_child_states(node_state, node);
1363 68 : let [join_type, using] = attrs!(state.children(node), [K::SQL_JOIN_TYPE, K::SQL_JOIN_USING]);
1364 68 : if let Some(using) = using.filter(|n| n.node_type() == NodeType::ARRAY) {
1365 44 : let mut columns = Vec::new();
1366 44 : for column in state.children(using) {
1367 44 : if column.node_type() == NodeType::NAME {
1368 44 : let name = state.node_name(column);
1369 44 : state.tag(&name, NameTag::COLUMN_NAME);
1370 44 : columns.push(name.text);
1371 44 : }
1372 : }
1373 44 : node_state.using_joins.push(UsingJoin {
1374 44 : ast_node_id: node_id,
1375 44 : using: Some(columns),
1376 44 : });
1377 24 : } else if join_type.is_some_and(|t| t.children_begin_or_value() as u8 & JoinType::NATURAL_.0 != 0) {
1378 2 : node_state.using_joins.push(UsingJoin {
1379 2 : ast_node_id: node_id,
1380 2 : using: None,
1381 2 : });
1382 23 : }
1383 : }
1384 :
1385 : NodeType::OBJECT_SQL_CREATE => {
1386 1739 : if Self::is_explain(state, state.find_statement_id(node_id)) {
1387 6 : self.merge_child_states(node_state, node);
1388 6 : self.create_scope(state, node_state, node_id);
1389 6 : return;
1390 1733 : }
1391 1733 : let [name_node, elements] =
1392 1733 : attrs!(state.children(node), [K::SQL_CREATE_TABLE_NAME, K::SQL_CREATE_TABLE_ELEMENTS]);
1393 1733 : let Some(table_name) = state.read_qualified_table_name(name_node) else { return };
1394 1733 : let schema_id = Self::register_schema(state, &table_name.database_name, &table_name.schema_name);
1395 1733 : let index = state.out.entry.table_declarations.len() as u32;
1396 1733 : let table_id = state.reserve_table_id(&table_name);
1397 : // Only the elements are merged
1398 1733 : if let Some(elements) = elements {
1399 1732 : let elements_id = state.node_id(elements) as usize;
1400 1732 : node_state.merge(&mut self.node_states[elements_id]);
1401 1732 : }
1402 1733 : let mut columns = std::mem::take(&mut node_state.table_columns);
1403 : // Sort the columns by name.
1404 : // The sort is stable, duplicate names keep their declaration order.
1405 6206 : columns.sort_by(|l, r| l.column_name.text.as_bytes().cmp(r.column_name.text.as_bytes()));
1406 1733 : self.create_scope(state, node_state, node_id);
1407 :
1408 1733 : let name = table_name.table_name.clone();
1409 1733 : let mut table = TableDeclaration::new(schema_id, table_id, table_name);
1410 1733 : table.ast_node_id = Some(node_id);
1411 1733 : table.ast_statement_id = state.find_statement_id(node_id);
1412 1733 : table.location = name_node.map(|n| state.text_span(*n.symbol_span()));
1413 1733 : let column_ids = state.reserve_column_ids(table_id, columns.iter().map(|c| &c.column_name.text));
1414 4040 : for (column_index, column) in columns.iter().enumerate() {
1415 4040 : table.table_columns_by_name.entry(column.column_name.text.clone()).or_insert(column_index);
1416 4040 : table.table_columns.push(TableColumn {
1417 4040 : object_id: QualifiedCatalogObjectId::table_column(table_id, column_ids[column_index]),
1418 4040 : table: Some(table_id),
1419 4040 : ast_node_id: Some(column.ast_node_id),
1420 4040 : column_name: column.column_name.clone(),
1421 4040 : location: Some(state.text_span(*state.ast[column.ast_node_id as usize].symbol_span())),
1422 4040 : });
1423 4040 : }
1424 1733 : state.entry_mut().table_declarations.push(table);
1425 1733 : state.resolve_name(&name, CatalogObjectRef::Table(TableLoc { entry: state.entry_id, index }));
1426 4040 : for (column_index, column) in columns.iter().enumerate() {
1427 4040 : let loc = ColumnLoc {
1428 4040 : table: TableLoc { entry: state.entry_id, index },
1429 4040 : column: column_index as u32,
1430 4040 : };
1431 4040 : state.resolve_name(&column.column_name, CatalogObjectRef::Column(loc));
1432 4040 : }
1433 : }
1434 :
1435 : NodeType::OBJECT_SQL_CREATE_FUNCTION => {
1436 30 : if Self::is_explain(state, state.find_statement_id(node_id)) {
1437 0 : self.merge_child_states(node_state, node);
1438 0 : return;
1439 30 : }
1440 30 : let [name_node, params, returns, is_aggregate] = attrs!(state.children(node), [
1441 : K::SQL_CREATE_FUNCTION_NAME,
1442 : K::SQL_CREATE_FUNCTION_PARAMS,
1443 : K::SQL_CREATE_FUNCTION_RETURNS,
1444 : K::SQL_CREATE_FUNCTION_IS_AGGREGATE,
1445 : ]);
1446 30 : let Some(function_name) = state.read_qualified_function_name(name_node) else { return };
1447 30 : let schema_id = Self::register_schema(state, &function_name.database_name, &function_name.schema_name);
1448 30 : let index = state.out.entry.function_declarations.len() as u32;
1449 30 : let function_id = state.reserve_function_id(&function_name);
1450 30 : let return_type: Arc<str> = returns.map(|r| Arc::from(state.text_at(*r.symbol_span()))).unwrap_or_else(|| Arc::from(""));
1451 30 : let mut declaration = FunctionDeclaration {
1452 30 : object_id: QualifiedCatalogObjectId::function(function_id),
1453 30 : catalog_schema_id: schema_id,
1454 30 : is_aggregate: is_aggregate.is_some(),
1455 30 : ast_node_id: Some(node_id),
1456 30 : ast_statement_id: None,
1457 30 : function_name: function_name.clone(),
1458 30 : params: Vec::new(),
1459 30 : return_type,
1460 30 : location: name_node.map(|n| state.text_span(*n.symbol_span())),
1461 : };
1462 30 : if let Some(params) = params.filter(|n| n.node_type() == NodeType::ARRAY) {
1463 28 : for param in state.children(params) {
1464 28 : if param.node_type() != NodeType::OBJECT_SQL_FUNCTION_PARAM {
1465 0 : continue;
1466 28 : }
1467 28 : let [param_name, param_type] =
1468 28 : attrs!(state.children(param), [K::SQL_FUNCTION_PARAM_NAME, K::SQL_FUNCTION_PARAM_TYPE]);
1469 28 : let Some(param_name) = param_name.filter(|n| n.node_type() == NodeType::NAME) else { continue };
1470 28 : let param_type = param_type.map(|t| state.text_at(*t.symbol_span())).unwrap_or("");
1471 28 : declaration.params.push(FunctionParam {
1472 28 : ast_node_id: Some(state.node_id(param)),
1473 28 : param_name: state.node_name(param_name),
1474 28 : param_type: Arc::from(param_type),
1475 28 : });
1476 : }
1477 4 : }
1478 30 : state.entry_mut().function_declarations.push(declaration);
1479 30 : state.tag(&function_name.function_name, NameTag::FUNCTION_NAME);
1480 30 : state.resolve_name(&function_name.function_name, CatalogObjectRef::Function(state.loc(index as usize)));
1481 : }
1482 :
1483 : NodeType::OBJECT_SQL_CREATE_AS | NodeType::OBJECT_SQL_VIEW => {
1484 157 : let [name, columns, statement] = if node.node_type() == NodeType::OBJECT_SQL_CREATE_AS {
1485 79 : attrs!(state.children(node), [K::SQL_CREATE_AS_NAME, K::SQL_CREATE_AS_COLUMNS, K::SQL_CREATE_AS_STATEMENT])
1486 : } else {
1487 78 : attrs!(state.children(node), [K::SQL_VIEW_NAME, K::SQL_VIEW_COLUMNS, K::SQL_VIEW_STATEMENT])
1488 : };
1489 157 : if let Some(statement) = statement.filter(|n| n.node_type() == NodeType::OBJECT_SQL_SELECT) {
1490 157 : self.register_derived_table(state, node, name, columns, statement);
1491 157 : }
1492 157 : self.merge_child_states(node_state, node);
1493 : }
1494 :
1495 15 : NodeType::OBJECT_SQL_PROPERTY_GRAPH | NodeType::OBJECT_SQL_GRAPH_TABLE => {
1496 15 : // Property graph analysis is syntax-only. Keep graph-local references in the
1497 15 : // analyzed buffers, but prevent them from entering or affecting an SQL scope.
1498 15 : self.merge_child_states(node_state, node);
1499 15 : node_state.clear();
1500 15 : }
1501 :
1502 : // By default, merge child states into the node state
1503 58859 : _ => self.merge_child_states(node_state, node),
1504 : }
1505 78912 : }
1506 :
1507 : /// Is a column ref the qualifier of a star result target (`t.*`)?
1508 2671 : fn is_star_qualifier(state: &AnalysisState, node: &Node) -> bool {
1509 2671 : if node.attribute_key() != K::SQL_RESULT_TARGET_VALUE {
1510 1144 : return false;
1511 1527 : }
1512 1527 : let Some(target) = state.ast.get(node.parent() as usize) else { return false };
1513 1527 : let [star] = attrs!(state.children(target), [K::SQL_RESULT_TARGET_STAR]);
1514 1527 : target.node_type() == NodeType::OBJECT_SQL_RESULT_TARGET && star.is_some()
1515 2671 : }
1516 :
1517 : /// Mark the CTEs of a scope as correlation barriers
1518 320 : fn set_cte_correlation_barriers(&self, state: &mut AnalysisState, scope: ScopeId) {
1519 320 : let children: Vec<ScopeId> = state.out.name_scopes[scope as usize]
1520 320 : .cte_definitions
1521 320 : .iter()
1522 320 : .filter_map(|(_, cte)| cte.child_scope)
1523 320 : .collect();
1524 320 : for child in children {
1525 18 : state.out.name_scopes[child as usize].column_correlation_barrier = true;
1526 18 : }
1527 320 : }
1528 :
1529 3734 : pub fn finish(&mut self, state: &mut AnalysisState) {
1530 : // Index the tables and functions
1531 3734 : state.entry_mut().index_declarations();
1532 :
1533 : // Assign statement ids to scopes before resolving ordered script-local names
1534 5681 : for i in 0..state.out.name_scopes.len() {
1535 5595 : let node_id = state.out.name_scopes[i].ast_node_id;
1536 5595 : state.out.name_scopes[i].ast_statement_id = state.find_statement_id(node_id);
1537 5595 : }
1538 :
1539 : // Resolve all names
1540 3734 : self.resolve_names(state);
1541 :
1542 3734 : for pending in std::mem::take(&mut self.pending_derived_tables) {
1543 156 : if let Some(&scope) = state.out.name_scopes_by_root_node.get(&pending.select_node_id) {
1544 156 : Self::populate_derived_table(state, &pending, scope);
1545 156 : }
1546 : }
1547 :
1548 : // Assign statement ids, the objects are ordered by their AST nodes
1549 3734 : if !state.parsed.statements.is_empty() {
1550 3530 : let statements = &state.parsed.statements;
1551 14120 : let assign = |nodes: &mut dyn Iterator<Item = (u32, &mut Option<u32>)>| {
1552 14120 : let mut statement_id = 0usize;
1553 14120 : let mut statement_begin = statements[0].nodes_begin;
1554 14120 : let mut statement_end = statement_begin + statements[0].node_count;
1555 16419 : for (ast_node_id, statement) in nodes {
1556 17332 : while statement_end <= ast_node_id && statement_id < statements.len() {
1557 3303 : statement_id += 1;
1558 3303 : if statement_id == statements.len() {
1559 0 : break;
1560 3303 : }
1561 3303 : statement_begin = statements[statement_id].nodes_begin;
1562 3303 : statement_end = statement_begin + statements[statement_id].node_count;
1563 : }
1564 14029 : if statement_id == statements.len() {
1565 0 : break;
1566 14029 : }
1567 14029 : if statement_begin <= ast_node_id {
1568 13972 : *statement = Some(statement_id as u32);
1569 13972 : }
1570 : }
1571 14120 : };
1572 3539 : assign(&mut state.out.table_references.iter_mut().map(|r| (r.ast_node_id, &mut r.ast_statement_id)));
1573 6036 : assign(&mut state.out.expressions.iter_mut().map(|e| (e.ast_node_id, &mut e.ast_statement_id)));
1574 3530 : let mut scope_statements: Vec<Option<u32>> = vec![None; state.out.name_scopes.len()];
1575 3530 : assign(
1576 3530 : &mut state
1577 3530 : .out
1578 3530 : .name_scopes
1579 3530 : .iter()
1580 3530 : .zip(scope_statements.iter_mut())
1581 5587 : .map(|(s, statement)| (s.ast_node_id, statement)),
1582 : );
1583 5587 : for (scope, statement) in state.out.name_scopes.iter_mut().zip(scope_statements) {
1584 5587 : if statement.is_some() {
1585 5587 : scope.ast_statement_id = statement;
1586 5587 : }
1587 : }
1588 3530 : assign(
1589 3530 : &mut Arc::make_mut(&mut state.out.entry)
1590 3530 : .function_declarations
1591 3530 : .iter_mut()
1592 3530 : .filter_map(|f| Some((f.ast_node_id?, &mut f.ast_statement_id))),
1593 : );
1594 204 : }
1595 :
1596 : // Index the columns of the table declarations
1597 3734 : state.entry_mut().index_table_columns();
1598 :
1599 : // Solve the schema-inference constraints
1600 3734 : Self::run_schema_inference(state);
1601 3734 : Self::resolve_insert_target_columns(state);
1602 3734 : Self::compute_resolved_column_ids(state);
1603 3734 : }
1604 :
1605 : /// Bind explicit INSERT target columns after target-table resolution
1606 3734 : fn resolve_insert_target_columns(state: &mut AnalysisState) {
1607 3734 : for i in 0..state.out.insert_statements.len() {
1608 254 : let target = state.out.insert_statements[i].target;
1609 254 : let Some(resolved) = state.out.table_references[target as usize].inner.as_ref().and_then(|r| r.resolved_table.as_ref()) else {
1610 3 : continue;
1611 : };
1612 251 : let table_id = resolved.catalog_table_id.unpack_table_id();
1613 251 : let loc = if table_id.origin == state.entry_id {
1614 30 : state.out.entry.table_loc_by_id(table_id)
1615 : } else {
1616 221 : state.catalog.entry(table_id.origin).and_then(|e| e.data().table_loc_by_id(table_id))
1617 : };
1618 251 : let Some(loc) = loc else { continue };
1619 251 : let Some(table) = state.table(loc) else { continue };
1620 251 : let resolved: Vec<Option<ColumnLoc>> = state.out.insert_statements[i]
1621 251 : .target_columns
1622 251 : .iter()
1623 252 : .map(|c| {
1624 12 : table.table_columns_by_name.get(&c.column_name.text).map(|&column| ColumnLoc {
1625 10 : table: loc,
1626 10 : column: column as u32,
1627 10 : })
1628 12 : })
1629 251 : .collect();
1630 252 : for (column, resolved) in state.out.insert_statements[i].target_columns.iter_mut().zip(resolved) {
1631 12 : if resolved.is_some() {
1632 10 : column.resolved = resolved;
1633 11 : }
1634 : }
1635 : }
1636 3734 : }
1637 :
1638 : /// The catalog ids of a resolved column
1639 2665 : fn resolved_column_ids(state: &AnalysisState, resolution: ColumnResolution) -> Option<ResolvedColumnIds> {
1640 2665 : let table_column_ids = |loc: ColumnLoc| {
1641 1941 : let table = state.table(loc.table)?;
1642 1941 : let column = table.table_columns.get(loc.column as usize)?;
1643 1941 : Some(ResolvedColumnIds {
1644 1941 : catalog_schema_id: table.catalog_schema_id,
1645 1941 : catalog_table_column_id: column.object_id,
1646 1941 : referenced_catalog_version: table.catalog_version,
1647 1941 : })
1648 1941 : };
1649 2665 : let mut current = resolution;
1650 2665 : for _ in 0..256 {
1651 2788 : match current {
1652 658 : ColumnResolution::Unresolved => return None,
1653 1924 : ColumnResolution::TableColumn(loc) => return table_column_ids(loc),
1654 206 : ColumnResolution::ScopeColumn { scope, column } => {
1655 206 : let column = state.out.name_scopes[scope as usize].output_columns.get(column as usize)?;
1656 206 : match column.source {
1657 17 : ScopeColumnSource::TableColumn(loc) => return table_column_ids(loc),
1658 9 : ScopeColumnSource::Computed => return None,
1659 180 : ScopeColumnSource::Expression(expr) => {
1660 180 : current = state.out.expressions[expr as usize].column_ref()?.resolved;
1661 : }
1662 : }
1663 : }
1664 : }
1665 : }
1666 0 : None
1667 2665 : }
1668 :
1669 3734 : fn compute_resolved_column_ids(state: &mut AnalysisState) {
1670 6148 : for i in 0..state.out.expressions.len() {
1671 5894 : let Some(column_ref) = state.out.expressions[i].column_ref() else { continue };
1672 2665 : let ids = Self::resolved_column_ids(state, column_ref.resolved);
1673 2665 : state.out.expressions[i].column_ref_mut().unwrap().resolved_ids = ids;
1674 : }
1675 3734 : }
1676 :
1677 : /// Solve the schema-inference constraints into inferred table schemas
1678 3734 : fn run_schema_inference(state: &mut AnalysisState) {
1679 3734 : let constraints = std::mem::take(&mut state.out.inference_constraints);
1680 3734 : if constraints.is_empty() {
1681 3618 : return;
1682 116 : }
1683 116 : let out = &mut state.out;
1684 :
1685 184 : fn get_or_create_schema(out: &mut super::AnalyzedScript, table_name: &QualifiedTableName) -> usize {
1686 184 : let key = table_name.key();
1687 184 : if let Some(&i) = out.inferred_table_schemas_by_name.get(&key) {
1688 60 : return i;
1689 124 : }
1690 124 : out.inferred_table_schemas.push(InferredTableSchema {
1691 124 : table_name: table_name.clone(),
1692 124 : confidence: InferenceConfidence::None,
1693 124 : columns: Vec::new(),
1694 124 : columns_by_name: HashMap::default(),
1695 124 : });
1696 124 : let i = out.inferred_table_schemas.len() - 1;
1697 124 : out.inferred_table_schemas_by_name.insert(key, i);
1698 124 : i
1699 184 : }
1700 184 : fn add_column(schema: &mut InferredTableSchema, column: &Name, confidence: InferenceConfidence) -> usize {
1701 184 : if let Some(&i) = schema.columns_by_name.get(&column.text) {
1702 16 : let c = &mut schema.columns[i];
1703 16 : c.confidence = c.confidence.max(confidence);
1704 16 : schema.confidence = schema.confidence.max(confidence);
1705 16 : return i;
1706 168 : }
1707 168 : let i = schema.columns.len();
1708 168 : schema.columns_by_name.insert(column.text.clone(), i);
1709 168 : schema.columns.push(InferredColumn {
1710 168 : column_name: column.clone(),
1711 168 : confidence,
1712 168 : candidate_table_names: Vec::new(),
1713 168 : });
1714 168 : schema.confidence = schema.confidence.max(confidence);
1715 168 : i
1716 184 : }
1717 117 : let has_confident_column = |out: &super::AnalyzedScript, table_name: &QualifiedTableName, column: &str| {
1718 22 : let Some(&i) = out.inferred_table_schemas_by_name.get(&table_name.key()) else { return false };
1719 2 : let schema = &out.inferred_table_schemas[i];
1720 2 : schema
1721 2 : .columns_by_name
1722 2 : .get(column)
1723 2 : .is_some_and(|&c| schema.columns[c].confidence == InferenceConfidence::Confident)
1724 22 : };
1725 185 : let write_owner = |out: &mut super::AnalyzedScript, expr: u32, owner: &InferenceCandidate, confidence| {
1726 185 : if let Some(column_ref) = out.expressions.get_mut(expr as usize).and_then(|e| e.column_ref_mut()) {
1727 185 : column_ref.inferred = Some(InferredOwner {
1728 185 : table_ref: owner.table_ref,
1729 185 : table_name: owner.table_name.clone(),
1730 185 : confidence,
1731 185 : });
1732 185 : }
1733 185 : };
1734 :
1735 116 : let mut resolved = vec![false; constraints.len()];
1736 :
1737 : // Step 1: seed the forced constraints
1738 185 : for (i, c) in constraints.iter().enumerate() {
1739 185 : if c.kind == InferenceConstraintKind::Forced && !c.candidates.is_empty() {
1740 174 : let candidate = &c.candidates[0];
1741 174 : let schema = get_or_create_schema(out, &candidate.table_name);
1742 174 : add_column(&mut out.inferred_table_schemas[schema], &c.column_name, InferenceConfidence::Confident);
1743 174 : write_owner(out, c.expression_id, candidate, InferenceConfidence::Confident);
1744 174 : resolved[i] = true;
1745 174 : }
1746 : }
1747 :
1748 : // Step 2: propagate over disjunctive constraints to a fixpoint. A disjunction is explained
1749 : // when exactly one candidate confidently owns its column.
1750 116 : let mut changed = true;
1751 233 : while changed {
1752 117 : changed = false;
1753 187 : for (i, c) in constraints.iter().enumerate() {
1754 187 : if resolved[i] || c.kind != InferenceConstraintKind::Disjunctive {
1755 176 : continue;
1756 11 : }
1757 11 : let owners: Vec<&InferenceCandidate> = c
1758 11 : .candidates
1759 11 : .iter()
1760 22 : .filter(|candidate| has_confident_column(out, &candidate.table_name, &c.column_name.text))
1761 11 : .collect();
1762 11 : if owners.is_empty() {
1763 10 : continue;
1764 1 : }
1765 : // Several owners make the use ambiguous, record a best guess
1766 1 : let confidence = if owners.len() == 1 {
1767 1 : InferenceConfidence::Confident
1768 : } else {
1769 0 : InferenceConfidence::Candidate
1770 : };
1771 1 : write_owner(out, c.expression_id, owners[0], confidence);
1772 1 : resolved[i] = true;
1773 1 : changed = true;
1774 : }
1775 : }
1776 :
1777 : // Step 3: assign the residual disjunctions to the candidate with the most inferred columns
1778 185 : for (i, c) in constraints.iter().enumerate() {
1779 185 : if resolved[i] || c.kind != InferenceConstraintKind::Disjunctive {
1780 175 : continue;
1781 10 : }
1782 10 : if c.candidates.is_empty() || c.candidates.len() > MAX_TABLE_REF_AMBIGUITY {
1783 0 : resolved[i] = true;
1784 0 : continue;
1785 10 : }
1786 10 : let mut best = 0;
1787 10 : let mut best_columns = 0;
1788 20 : for (ci, candidate) in c.candidates.iter().enumerate() {
1789 20 : let n = out
1790 20 : .inferred_table_schemas_by_name
1791 20 : .get(&candidate.table_name.key())
1792 20 : .map(|&s| out.inferred_table_schemas[s].columns.len())
1793 20 : .unwrap_or(0);
1794 20 : if n > best_columns {
1795 3 : best_columns = n;
1796 3 : best = ci;
1797 17 : }
1798 : }
1799 10 : let schema = get_or_create_schema(out, &c.candidates[best].table_name);
1800 10 : let schema = &mut out.inferred_table_schemas[schema];
1801 10 : let column = add_column(schema, &c.column_name, InferenceConfidence::Candidate);
1802 20 : for (ci, candidate) in c.candidates.iter().enumerate() {
1803 20 : if ci != best {
1804 10 : schema.columns[column].candidate_table_names.push(candidate.table_name.clone());
1805 10 : }
1806 : }
1807 10 : write_owner(out, c.expression_id, &c.candidates[best], InferenceConfidence::Candidate);
1808 10 : resolved[i] = true;
1809 : }
1810 116 : state.out.inference_constraints = constraints;
1811 3734 : }
1812 : }
|
