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