Line data Source code
1 : //! The table parameters of a session.
2 : //!
3 : //! A table parameter `:foo` in table position reads a table of the session by name: the result of the script
4 : //! `foo.sql` or the attachment `foo.parquet`. Scripts and attachments share one namespace. The planner, the check of
5 : //! the script references, the analyzer and completion find a name the same way.
6 : //!
7 : //! The analyzer reads a table parameter like a table: `TableParameters` holds the output columns of the scripts of a
8 : //! session that are a single SELECT and the columns of the attachments, as table declarations of the reserved
9 : //! catalog entry `TABLE_PARAMETERS_ENTRY_ID`. Every script session of the session holds the same `TableParameters`,
10 : //! an analysis is current only with the table parameters it was analyzed with.
11 :
12 : use crate::analyzer::{AnalyzedScript, ParameterKind};
13 : use crate::catalog::{CatalogEntryId, CatalogTableId, Name, QualifiedCatalogObjectId, QualifiedTableName, TableColumn, TableDeclaration, TableLoc};
14 : use crate::hash::HashMap;
15 : use dashql_buffers::parser::StatementType;
16 : use std::sync::Arc;
17 :
18 : /// The catalog entry of the table parameters, the table `i` is the table parameter `i` of the session
19 : pub const TABLE_PARAMETERS_ENTRY_ID: CatalogEntryId = u32::MAX - 1;
20 :
21 : /// What a name of a table parameter finds, the indexes are those of the names that were searched
22 : #[derive(Clone, Debug, PartialEq, Eq)]
23 : pub enum TableParameterLookup {
24 : /// The index of the name
25 : Found(usize),
26 : /// No name matches
27 : Unknown,
28 : /// Several names match: several have the exact name, or none has it and several differ in case only
29 : Ambiguous(Vec<usize>),
30 : }
31 :
32 : /// Find the name of a table parameter: the only exact name, or the only name that differs in ASCII case. Empty
33 : /// names are never found.
34 538 : pub fn find_table_parameter<'a>(names: impl Iterator<Item = &'a str> + Clone, name: &str) -> TableParameterLookup {
35 572 : let pick = |matches: Vec<usize>| match matches.len() {
36 49 : 0 => None,
37 510 : 1 => Some(TableParameterLookup::Found(matches[0])),
38 13 : _ => Some(TableParameterLookup::Ambiguous(matches)),
39 572 : };
40 1533 : let exact = names.clone().enumerate().filter(|(_, n)| !n.is_empty() && *n == name).map(|(i, _)| i).collect();
41 538 : if let Some(found) = pick(exact) {
42 504 : return found;
43 34 : }
44 94 : let folded = names.enumerate().filter(|(_, n)| !n.is_empty() && n.eq_ignore_ascii_case(name)).map(|(i, _)| i).collect();
45 34 : pick(folded).unwrap_or(TableParameterLookup::Unknown)
46 538 : }
47 :
48 : /// The names that collide: groups of the indexes of names that are equal in ASCII case, in the order of their first
49 : /// name. A table parameter with one of these names is ambiguous at least in case.
50 278 : pub fn colliding_names<'a>(names: impl Iterator<Item = &'a str>) -> Vec<Vec<usize>> {
51 278 : let mut groups: Vec<(String, Vec<usize>)> = Vec::new();
52 278 : let mut by_name: HashMap<String, usize> = HashMap::default();
53 568 : for (i, name) in names.enumerate().filter(|(_, n)| !n.is_empty()) {
54 566 : let key = name.to_ascii_lowercase();
55 566 : match by_name.get(&key) {
56 6 : Some(&group) => groups[group].1.push(i),
57 560 : None => {
58 560 : by_name.insert(key.clone(), groups.len());
59 560 : groups.push((key, vec![i]));
60 560 : }
61 : }
62 : }
63 560 : groups.into_iter().map(|(_, g)| g).filter(|g| g.len() > 1).collect()
64 278 : }
65 :
66 : /// What a table parameter reads
67 : #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
68 : pub enum TableParameterSource {
69 : /// The result of the script with the index in session order
70 : Script(u32),
71 : /// The attachment with the index
72 : Attachment(u32),
73 : }
74 :
75 : /// An attachment of a session that table parameters read
76 : #[derive(Clone, Copy, Debug)]
77 : pub struct TableParameterAttachment<'a> {
78 : /// The name, `foo` for `foo.parquet`
79 : pub name: &'a str,
80 : /// The columns of the file, absent if the host didn't read them
81 : pub columns: Option<&'a [Arc<str>]>,
82 : }
83 :
84 : /// A table parameter of a session
85 : #[derive(Clone, Debug)]
86 : pub struct TableParameter {
87 : /// The name, `foo` for `foo.sql` or `foo.parquet`
88 : pub name: Arc<str>,
89 : /// What the table parameter reads
90 : pub source: TableParameterSource,
91 : /// The columns as a table, absent if a script is no single SELECT or references itself, or if the columns of an
92 : /// attachment are unknown
93 : pub table: Option<TableDeclaration>,
94 : }
95 :
96 : /// The table parameters of a session: the scripts in session order, then the attachments
97 : #[derive(Clone, Debug, Default)]
98 : pub struct TableParameters {
99 : pub entries: Vec<TableParameter>,
100 : }
101 :
102 : impl TableParameters {
103 : /// Find the table parameter of a name, the index of its entry
104 16 : pub fn find(&self, name: &str) -> TableParameterLookup {
105 40 : find_table_parameter(self.entries.iter().map(|s| &*s.name), name)
106 16 : }
107 :
108 : /// The table of a table parameter
109 47 : pub fn table(&self, loc: TableLoc) -> Option<&TableDeclaration> {
110 47 : if loc.entry != TABLE_PARAMETERS_ENTRY_ID {
111 1 : return None;
112 46 : }
113 46 : self.entries.get(loc.index as usize)?.table.as_ref()
114 47 : }
115 :
116 : /// What the table parameter of a table reads
117 5 : pub fn source(&self, loc: TableLoc) -> Option<TableParameterSource> {
118 5 : if loc.entry != TABLE_PARAMETERS_ENTRY_ID {
119 1 : return None;
120 4 : }
121 4 : Some(self.entries.get(loc.index as usize)?.source)
122 5 : }
123 :
124 : /// Do two registries have the same names, sources and columns?
125 7 : pub fn same_as(&self, other: &TableParameters) -> bool {
126 14 : let columns = |t: &Option<TableDeclaration>| t.as_ref().map(|t| t.table_columns.iter().map(|c| c.column_name.text.clone()).collect::<Vec<_>>());
127 7 : self.entries.len() == other.entries.len()
128 6 : && self
129 6 : .entries
130 6 : .iter()
131 6 : .zip(&other.entries)
132 9 : .all(|(l, r)| l.name == r.name && l.source == r.source && columns(&l.table) == columns(&r.table))
133 7 : }
134 :
135 : /// Derive the table parameters of a session from the analyses of its scripts and the columns of its attachments. A
136 : /// script without an analysis keeps the columns of the script with the same name in `previous`. Scripts on a cycle
137 : /// of references have no result: the columns of one would grow with every analysis of the other.
138 23 : pub fn derive(scripts: &[(&str, Option<&AnalyzedScript>)], attachments: &[TableParameterAttachment], previous: Option<&TableParameters>) -> TableParameters {
139 23 : let names = || scripts.iter().map(|(n, _)| *n).chain(attachments.iter().map(|a| a.name));
140 : // The scripts that the terminal query of a script references, attachments reference nothing
141 23 : let edges: Vec<Vec<usize>> = scripts
142 23 : .iter()
143 33 : .map(|(_, analyzed)| {
144 33 : let Some(analyzed) = analyzed else { return Vec::new() };
145 32 : analyzed
146 32 : .parameters
147 32 : .iter()
148 32 : .filter(|p| p.kind == ParameterKind::Table)
149 32 : .filter_map(|p| match find_table_parameter(names(), p.name.as_deref()?) {
150 5 : TableParameterLookup::Found(i) if i < scripts.len() => Some(i),
151 0 : _ => None,
152 5 : })
153 32 : .collect()
154 33 : })
155 23 : .collect();
156 23 : let cyclic = on_cycle(&edges);
157 23 : let mut out = Vec::with_capacity(scripts.len() + attachments.len());
158 33 : for (i, (name, analyzed)) in scripts.iter().enumerate() {
159 33 : let columns = match analyzed {
160 32 : Some(analyzed) => query_columns(analyzed),
161 1 : None => previous
162 1 : .and_then(|p| p.entries.iter().find(|s| matches!(s.source, TableParameterSource::Script(_)) && &*s.name == *name))
163 1 : .and_then(|s| s.table.as_ref())
164 1 : .map(|t| t.table_columns.iter().map(|c| c.column_name.text.clone()).collect()),
165 : };
166 33 : let table = match columns {
167 31 : Some(columns) if !cyclic[i] => Some(result_table(i as u32, name, columns)),
168 4 : _ => None,
169 : };
170 33 : out.push(TableParameter { name: Arc::from(*name), source: TableParameterSource::Script(i as u32), table });
171 : }
172 23 : for (i, attachment) in attachments.iter().enumerate() {
173 16 : let index = (scripts.len() + i) as u32;
174 16 : let table = attachment.columns.map(|columns| result_table(index, attachment.name, columns.to_vec()));
175 16 : out.push(TableParameter { name: Arc::from(attachment.name), source: TableParameterSource::Attachment(i as u32), table });
176 : }
177 23 : TableParameters { entries: out }
178 23 : }
179 : }
180 :
181 : /// The output columns of a script that is a single SELECT
182 32 : fn query_columns(analyzed: &AnalyzedScript) -> Option<Vec<Arc<str>>> {
183 32 : match &analyzed.parsed.statements[..] {
184 31 : [statement] if statement.statement_type == StatementType::SELECT => Some(crate::analyzer::statement_output_columns(analyzed, 0)),
185 2 : _ => None,
186 : }
187 32 : }
188 :
189 : /// The table of the table parameter `index`
190 40 : fn result_table(index: u32, name: &str, columns: Vec<Arc<str>>) -> TableDeclaration {
191 40 : let table_id = CatalogTableId::new(TABLE_PARAMETERS_ENTRY_ID, index);
192 164 : let name_of = |text: Arc<str>| Name { entry: TABLE_PARAMETERS_ENTRY_ID, id: 0, text };
193 40 : let table_name = QualifiedTableName {
194 40 : ast_node_id: None,
195 40 : database_name: name_of(Arc::from("")),
196 40 : schema_name: name_of(Arc::from("")),
197 40 : table_name: name_of(Arc::from(name)),
198 40 : };
199 : /* A table parameter belongs to no database and schema of the catalog */
200 40 : let mut table = TableDeclaration::new(QualifiedCatalogObjectId::schema(0, 0), table_id, table_name);
201 40 : let mut by_name = HashMap::default();
202 44 : for (i, column) in columns.into_iter().enumerate() {
203 44 : by_name.entry(column.clone()).or_insert(i);
204 44 : table.table_columns.push(TableColumn {
205 44 : object_id: QualifiedCatalogObjectId::table_column(table_id, i as u32),
206 44 : table: Some(table_id),
207 44 : ast_node_id: None,
208 44 : column_name: name_of(column),
209 44 : location: None,
210 44 : });
211 44 : }
212 40 : table.table_columns_by_name = by_name;
213 40 : table
214 40 : }
215 :
216 : /// Which nodes of a graph lie on a cycle
217 23 : fn on_cycle(edges: &[Vec<usize>]) -> Vec<bool> {
218 23 : let n = edges.len();
219 : // A node lies on a cycle if it reaches itself
220 23 : (0..n)
221 33 : .map(|start| {
222 33 : let mut seen = vec![false; n];
223 33 : let mut pending: Vec<usize> = edges[start].clone();
224 38 : while let Some(i) = pending.pop() {
225 7 : if i == start {
226 2 : return true;
227 5 : }
228 5 : if i < n && !std::mem::replace(&mut seen[i], true) {
229 5 : pending.extend(&edges[i]);
230 5 : }
231 : }
232 31 : false
233 33 : })
234 23 : .collect()
235 23 : }
236 :
237 : #[cfg(test)]
238 : mod tests {
239 : use super::*;
240 :
241 : #[test]
242 1 : fn exact_then_folded() {
243 1 : let names = ["Foo", "foo", "Bar", ""];
244 1 : assert_eq!(find_table_parameter(names.iter().copied(), "foo"), TableParameterLookup::Found(1));
245 1 : assert_eq!(find_table_parameter(names.iter().copied(), "FOO"), TableParameterLookup::Ambiguous(vec![0, 1]));
246 1 : assert_eq!(find_table_parameter(names.iter().copied(), "bar"), TableParameterLookup::Found(2));
247 1 : assert_eq!(find_table_parameter(names.iter().copied(), "baz"), TableParameterLookup::Unknown);
248 1 : assert_eq!(find_table_parameter(names.iter().copied(), ""), TableParameterLookup::Unknown);
249 1 : }
250 :
251 : #[test]
252 1 : fn exact_duplicates_are_ambiguous() {
253 1 : let names = ["sales", "orders", "sales"];
254 1 : assert_eq!(find_table_parameter(names.iter().copied(), "sales"), TableParameterLookup::Ambiguous(vec![0, 2]));
255 1 : assert_eq!(find_table_parameter(names.iter().copied(), "Orders"), TableParameterLookup::Found(1));
256 1 : }
257 :
258 : #[test]
259 1 : fn collisions_fold_case() {
260 1 : let names = ["Sales", "orders", "", "sales", "", "ORDERS", "x"];
261 1 : assert_eq!(colliding_names(names.iter().copied()), vec![vec![0, 3], vec![1, 5]]);
262 1 : }
263 : }
|
