helios_sof/sqlquery/
scan.rs

1//! Pure, conservative scanner over SQL text: the `:name` placeholders a
2//! query uses and the tables its `FROM`/`JOIN` clauses read, each located by
3//! line, column, and Unicode-character offset/length (#841, #842).
4//!
5//! This module never executes or fully parses the SQL — it walks the token
6//! stream [`sqlparser::tokenizer::Tokenizer::tokenize_with_location`]
7//! produces and applies a handful of local, position-based rules. That
8//! makes it deliberately less capable than a real parser, in exchange for
9//! never mis-locating (or mis-naming) anything it *does* report: every rule
10//! below is written to favor a false negative (missing a table or
11//! placeholder) over a false positive.
12//!
13//! # What [`scan_sql`] finds
14//!
15//! - **Placeholders**: a [`Token::Colon`] immediately followed — no
16//!   whitespace, per token-span adjacency — by an unquoted [`Token::Word`].
17//!   `::` tokenizes as its own [`Token::DoubleColon`], so a cast never
18//!   matches. Text inside a string literal or a comment is already one
19//!   token to the tokenizer, so nothing inside either is ever inspected.
20//!   Duplicate names (compared with the case SQLite keeps: exact) keep only
21//!   their first occurrence.
22//! - **Tables**: an identifier (bare or double-quoted) is reported when the
23//!   token immediately before it is the keyword `FROM`, the keyword `JOIN`
24//!   (`LEFT`/`INNER`/`CROSS`/… all end in the literal `JOIN` token this
25//!   checks), or a comma inside a `FROM` list that is still open at the
26//!   current parenthesis depth. An identifier immediately followed by `(`
27//!   (a function call, e.g. `json_each(x)`) or by `.` (a qualified
28//!   `schema.table` reference — neither part is reported) is excluded.
29//!   Names declared by a `WITH [RECURSIVE] name AS (...)` clause are
30//!   collected first and never reported as a table reference, wherever they
31//!   are used — but any table the CTE's own body reads is still reported,
32//!   since the body is scanned like any other subquery. Duplicate names
33//!   (compared case-insensitively, like SQLite compares table names) keep
34//!   only their first occurrence's spelling and position.
35//!
36//! # What it deliberately does **not** detect
37//!
38//! - An alias is never reported and never influences whether the table it
39//!   names is reported — this module has no notion of "alias", only of
40//!   "the token after a table reference wasn't `(` or `.`".
41//! - A table named only inside a derived table's `(...)` — `FROM (SELECT *
42//!   FROM t) sub` reports `t` (found by the ordinary `FROM` rule while
43//!   scanning inside the parentheses) but never `sub`.
44//! - `VALUES`, table-valued functions, and any other `FROM` item that is
45//!   not a bare or quoted identifier are silently skipped, not reported as
46//!   errors.
47//! - A three-or-more-part qualified name (`catalog.schema.table`) is
48//!   excluded the same way a two-part one is; neither segment is reported.
49//! - Anything the tokenizer itself cannot lex (see [`ScanError`]) — the
50//!   caller is expected to let SQL parsing report that error instead.
51
52use std::collections::HashSet;
53
54use sqlparser::dialect::SQLiteDialect;
55use sqlparser::keywords::Keyword;
56use sqlparser::tokenizer::{Location, Token, TokenWithSpan, Tokenizer};
57use thiserror::Error;
58
59/// A location inside the scanned SQL text, in two coordinate systems at
60/// once: 1-based `line`/`column` (matching the `Line: N, Column: M` marker
61/// [`sqlparser`]'s own parse errors already use, so a caller that extracts
62/// that marker from one keeps working for the other) and a 0-based
63/// Unicode-`char` `offset`/`length` pair from the start of the text — what
64/// a browser text editor (CodeMirror) indexes with, since it counts code
65/// points, not UTF-8 bytes.
66#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
67pub struct SourcePosition {
68    /// 1-based line number.
69    pub line: usize,
70    /// 1-based column number.
71    pub column: usize,
72    /// 0-based Unicode-character offset from the start of the text.
73    pub offset: usize,
74    /// Length of the located span, in Unicode characters.
75    pub length: usize,
76}
77
78/// A `:name` placeholder the SQL uses, located at the `:`.
79#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
80pub struct Placeholder {
81    /// The parameter name, without the leading `:`, exactly as written —
82    /// SQLite treats named-parameter case as significant.
83    pub name: String,
84    pub position: SourcePosition,
85}
86
87/// A table the SQL reads, located at its identifier (quotes included, when
88/// quoted).
89#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
90pub struct TableRef {
91    /// The table name exactly as written (quotes stripped for a quoted
92    /// identifier, since [`sqlparser`]'s tokenizer already does that);
93    /// compare case-insensitively, as SQLite compares table names.
94    pub name: String,
95    pub position: SourcePosition,
96}
97
98/// The result of scanning one SQL statement: every placeholder and table
99/// reference [`scan_sql`] found, each in first-occurrence order.
100#[derive(Debug, Clone, Default, PartialEq, Eq, serde::Serialize)]
101pub struct ScanResult {
102    pub placeholders: Vec<Placeholder>,
103    pub tables: Vec<TableRef>,
104}
105
106/// A failure to tokenize the SQL text at all. Per this module's contract
107/// (#841), a caller receiving this should skip linting and let the SQL
108/// engine's own parser report the error instead — this scanner never tries
109/// to diagnose *why* the SQL is malformed.
110#[derive(Debug, Error)]
111pub enum ScanError {
112    #[error("SQL tokenizer error: {0}")]
113    Tokenize(String),
114}
115
116/// Scans `sql` for `:name` placeholders and the tables its `FROM`/`JOIN`
117/// clauses read, without executing or fully parsing it. See the module docs
118/// for the exact rules and their limits.
119///
120/// Uses the same [`SQLiteDialect`] the SQL engine itself speaks, so a colon
121/// or an identifier tokenizes identically here and at execution time.
122pub fn scan_sql(sql: &str) -> Result<ScanResult, ScanError> {
123    let dialect = SQLiteDialect {};
124    let tokens = Tokenizer::new(&dialect, sql)
125        .tokenize_with_location()
126        .map_err(|e| ScanError::Tokenize(e.to_string()))?;
127
128    // Every position callers see is computed from this text, so an offset
129    // is always in `char`s, never UTF-8 bytes.
130    let line_starts = compute_line_starts(sql);
131
132    let significant: Vec<&TokenWithSpan> = tokens
133        .iter()
134        .filter(|t| !matches!(t.token, Token::Whitespace(_)))
135        .collect();
136
137    Ok(ScanResult {
138        placeholders: scan_placeholders(&significant, &line_starts),
139        tables: scan_tables(&significant, &line_starts),
140    })
141}
142
143/// Returns the tables `result` found that are not present in
144/// `declared_labels` (compared case-insensitively, like SQLite compares
145/// table names), in the order they first appeared in the SQL.
146pub fn undeclared_tables<'a>(
147    result: &'a ScanResult,
148    declared_labels: &[String],
149) -> Vec<&'a TableRef> {
150    let declared: HashSet<String> = declared_labels.iter().map(|l| l.to_lowercase()).collect();
151    result
152        .tables
153        .iter()
154        .filter(|t| !declared.contains(&t.name.to_lowercase()))
155        .collect()
156}
157
158/// Offset (in `char`s) of the first character of each line, indexed by
159/// `line - 1` — `line_starts[0]` is always `0`. Built by the same rule
160/// [`sqlparser`]'s tokenizer uses to advance its own `line`/`column`
161/// (`\n` starts a new line; every other `char` — not byte — advances the
162/// column), so a [`Location`] it reports always maps back to the exact
163/// offset that produced it.
164fn compute_line_starts(sql: &str) -> Vec<usize> {
165    let mut starts = vec![0usize];
166    for (idx, ch) in sql.chars().enumerate() {
167        if ch == '\n' {
168            starts.push(idx + 1);
169        }
170    }
171    starts
172}
173
174/// Converts a tokenizer [`Location`] (1-based line/column) to a 0-based
175/// `char` offset from the start of the text, using the precomputed
176/// `line_starts` table.
177fn to_offset(line_starts: &[usize], loc: Location) -> usize {
178    let line_idx = (loc.line as usize).saturating_sub(1);
179    let line_start = line_starts
180        .get(line_idx)
181        .copied()
182        .unwrap_or_else(|| line_starts.last().copied().unwrap_or(0));
183    line_start + (loc.column as usize).saturating_sub(1)
184}
185
186fn source_position(line_starts: &[usize], start: Location, end: Location) -> SourcePosition {
187    let offset = to_offset(line_starts, start);
188    let end_offset = to_offset(line_starts, end);
189    SourcePosition {
190        line: start.line as usize,
191        column: start.column as usize,
192        offset,
193        length: end_offset.saturating_sub(offset),
194    }
195}
196
197/// Every `:name` placeholder, first occurrence only (exact-case
198/// dedup — SQLite named-parameter case is significant).
199fn scan_placeholders(tokens: &[&TokenWithSpan], line_starts: &[usize]) -> Vec<Placeholder> {
200    let mut seen = HashSet::new();
201    let mut out = Vec::new();
202    for pair in tokens.windows(2) {
203        let (colon, word) = (pair[0], pair[1]);
204        if !matches!(colon.token, Token::Colon) {
205            continue;
206        }
207        // No gap between the `:` and the identifier — a space (or, in
208        // principle, a comment) in between means this isn't a named
209        // parameter SQLite would recognize either.
210        if colon.span.end != word.span.start {
211            continue;
212        }
213        let Token::Word(w) = &word.token else {
214            continue;
215        };
216        // SQLite named parameters are never quoted identifiers.
217        if w.quote_style.is_some() {
218            continue;
219        }
220        if !seen.insert(w.value.clone()) {
221            continue;
222        }
223        out.push(Placeholder {
224            name: w.value.clone(),
225            position: source_position(line_starts, colon.span.start, word.span.end),
226        });
227    }
228    out
229}
230
231/// Keywords that close an open `FROM` list at the current parenthesis
232/// depth — once one of these appears, a later comma at the same depth is an
233/// expression-list separator (`GROUP BY a, b`, `IN (1, 2)`, …), not another
234/// table reference.
235fn ends_from_list(keyword: Keyword) -> bool {
236    matches!(
237        keyword,
238        Keyword::WHERE
239            | Keyword::GROUP
240            | Keyword::HAVING
241            | Keyword::ORDER
242            | Keyword::LIMIT
243            | Keyword::UNION
244            | Keyword::INTERSECT
245            | Keyword::EXCEPT
246            | Keyword::WINDOW
247    )
248}
249
250/// Every table read via `FROM`/`JOIN`, first occurrence only
251/// (case-insensitive dedup), excluding CTE names, qualified names,
252/// subqueries, and function calls.
253fn scan_tables(tokens: &[&TokenWithSpan], line_starts: &[usize]) -> Vec<TableRef> {
254    let cte_names = collect_cte_names(tokens);
255
256    let mut paren_depth: usize = 0;
257    // One flag per open parenthesis depth: is a `FROM` list still open here?
258    let mut from_active: Vec<bool> = vec![false];
259    let mut seen = HashSet::new();
260    let mut out = Vec::new();
261
262    for (i, tok) in tokens.iter().enumerate() {
263        match &tok.token {
264            Token::LParen => {
265                paren_depth += 1;
266                from_active.push(false);
267            }
268            Token::RParen => {
269                if paren_depth > 0 {
270                    paren_depth -= 1;
271                    from_active.pop();
272                }
273            }
274            Token::Word(w) if w.keyword == Keyword::FROM => {
275                from_active[paren_depth] = true;
276            }
277            Token::Word(w) if ends_from_list(w.keyword) => {
278                from_active[paren_depth] = false;
279            }
280            Token::Word(w) if w.keyword == Keyword::NoKeyword => {
281                let is_candidate = i > 0
282                    && match &tokens[i - 1].token {
283                        Token::Word(pw) => {
284                            pw.keyword == Keyword::FROM || pw.keyword == Keyword::JOIN
285                        }
286                        Token::Comma => from_active[paren_depth],
287                        _ => false,
288                    };
289                if !is_candidate {
290                    continue;
291                }
292                // A function call (`json_each(x)`) or a qualified name
293                // (`schema.table`, `catalog.schema.table`) — neither part
294                // of a qualified name is reported.
295                let excluded = matches!(
296                    tokens.get(i + 1).map(|t| &t.token),
297                    Some(Token::LParen) | Some(Token::Period)
298                );
299                if excluded {
300                    continue;
301                }
302                if cte_names.contains(&w.value.to_lowercase()) {
303                    continue;
304                }
305                if !seen.insert(w.value.to_lowercase()) {
306                    continue;
307                }
308                out.push(TableRef {
309                    name: w.value.clone(),
310                    position: source_position(line_starts, tok.span.start, tok.span.end),
311                });
312            }
313            _ => {}
314        }
315    }
316    out
317}
318
319/// Collects every name a `WITH [RECURSIVE] name [(cols)] AS (...)` clause
320/// declares, lower-cased, so [`scan_tables`] can exclude a later `FROM
321/// name`/`JOIN name` reference to it — the CTE's own body is scanned like
322/// any other parenthesized subquery, so tables *it* reads are still found.
323///
324/// Independent of [`scan_tables`]'s own state machine on purpose: this is a
325/// flat walk that only tracks parenthesis depth, so it can't mis-fire on
326/// the same edge cases (nested subqueries, multiple CTEs) the table scan
327/// has to reason about `FROM`-list activity for.
328fn collect_cte_names(tokens: &[&TokenWithSpan]) -> HashSet<String> {
329    let mut names = HashSet::new();
330    let mut i = 0usize;
331    while i < tokens.len() {
332        let is_with = matches!(&tokens[i].token, Token::Word(w) if w.keyword == Keyword::WITH);
333        if !is_with {
334            i += 1;
335            continue;
336        }
337        i += 1;
338        if matches!(tokens.get(i).map(|t| &t.token), Some(Token::Word(w)) if w.keyword == Keyword::RECURSIVE)
339        {
340            i += 1;
341        }
342        while let Some(Token::Word(name)) = tokens.get(i).map(|t| &t.token) {
343            names.insert(name.value.to_lowercase());
344            i += 1;
345            // Optional explicit column list: `cte(col1, col2) AS (...)`.
346            if matches!(tokens.get(i).map(|t| &t.token), Some(Token::LParen)) {
347                i = skip_balanced_parens(tokens, i);
348            }
349            let is_as = matches!(tokens.get(i).map(|t| &t.token), Some(Token::Word(w)) if w.keyword == Keyword::AS);
350            if !is_as {
351                break;
352            }
353            i += 1;
354            if !matches!(tokens.get(i).map(|t| &t.token), Some(Token::LParen)) {
355                break;
356            }
357            i = skip_balanced_parens(tokens, i);
358            if matches!(tokens.get(i).map(|t| &t.token), Some(Token::Comma)) {
359                i += 1;
360                continue; // another `name AS (...)` follows
361            }
362            break;
363        }
364    }
365    names
366}
367
368/// Given the index of a `(`, returns the index just past its matching `)`.
369/// If the parentheses are unbalanced (malformed SQL that still tokenized),
370/// returns `tokens.len()` — the caller's loop simply ends, which is the
371/// conservative choice for a scanner that never reports on input it isn't
372/// sure it understood.
373fn skip_balanced_parens(tokens: &[&TokenWithSpan], open_paren_idx: usize) -> usize {
374    let mut depth = 0i32;
375    let mut i = open_paren_idx;
376    loop {
377        match tokens.get(i).map(|t| &t.token) {
378            Some(Token::LParen) => depth += 1,
379            Some(Token::RParen) => {
380                depth -= 1;
381                if depth == 0 {
382                    return i + 1;
383                }
384            }
385            Some(_) => {}
386            None => return tokens.len(),
387        }
388        i += 1;
389    }
390}
391
392#[cfg(test)]
393mod tests {
394    use super::*;
395
396    fn names(result: &ScanResult) -> Vec<&str> {
397        result.tables.iter().map(|t| t.name.as_str()).collect()
398    }
399
400    fn placeholder_names(result: &ScanResult) -> Vec<&str> {
401        result
402            .placeholders
403            .iter()
404            .map(|p| p.name.as_str())
405            .collect()
406    }
407
408    #[test]
409    fn simple_from_reports_table_and_position() {
410        let result = scan_sql("SELECT * FROM v").unwrap();
411        assert_eq!(names(&result), vec!["v"]);
412        assert_eq!(result.tables[0].position.line, 1);
413        assert_eq!(result.tables[0].position.column, 15);
414        assert_eq!(result.tables[0].position.offset, 14);
415        assert_eq!(result.tables[0].position.length, 1);
416    }
417
418    #[test]
419    fn join_variants_report_both_sides() {
420        let result = scan_sql("SELECT * FROM a LEFT JOIN b ON a.id = b.id").unwrap();
421        assert_eq!(names(&result), vec!["a", "b"]);
422    }
423
424    #[test]
425    fn comma_list_reports_every_item_ignoring_aliases() {
426        let result = scan_sql("SELECT * FROM a, b c, d AS e").unwrap();
427        assert_eq!(names(&result), vec!["a", "b", "d"]);
428    }
429
430    #[test]
431    fn cte_body_reported_but_cte_reference_excluded() {
432        let result = scan_sql("WITH cte AS (SELECT * FROM t) SELECT * FROM cte").unwrap();
433        assert_eq!(names(&result), vec!["t"]);
434    }
435
436    #[test]
437    fn subquery_in_from_reports_nothing() {
438        let result = scan_sql("SELECT * FROM (SELECT 1) sub").unwrap();
439        assert!(result.tables.is_empty());
440    }
441
442    #[test]
443    fn table_valued_function_reports_nothing() {
444        let result = scan_sql("SELECT * FROM json_each(x)").unwrap();
445        assert!(result.tables.is_empty());
446    }
447
448    #[test]
449    fn quoted_identifier_reports_unquoted_name() {
450        let result = scan_sql(r#"SELECT * FROM "Quoted""#).unwrap();
451        assert_eq!(names(&result), vec!["Quoted"]);
452    }
453
454    #[test]
455    fn qualified_name_reports_nothing() {
456        let result = scan_sql("SELECT * FROM main.t").unwrap();
457        assert!(result.tables.is_empty());
458    }
459
460    #[test]
461    fn dedup_is_case_insensitive_and_keeps_first_spelling() {
462        let result = scan_sql("SELECT * FROM v v2 JOIN V").unwrap();
463        assert_eq!(names(&result), vec!["v"]);
464    }
465
466    #[test]
467    fn placeholder_ignores_literal_and_comment_reports_real_one() {
468        let result = scan_sql("SELECT * WHERE x = ':notaparam' AND y = :ward -- :comment").unwrap();
469        assert_eq!(placeholder_names(&result), vec!["ward"]);
470    }
471
472    #[test]
473    fn double_colon_cast_is_not_a_placeholder() {
474        let result = scan_sql("SELECT x::int").unwrap();
475        assert!(result.placeholders.is_empty());
476    }
477
478    #[test]
479    fn placeholder_dedup_keeps_first_occurrence() {
480        let result = scan_sql("SELECT * WHERE a = :p AND b = :p").unwrap();
481        assert_eq!(result.placeholders.len(), 1);
482    }
483
484    #[test]
485    fn multibyte_text_offsets_count_chars_not_bytes() {
486        // "café" is 4 chars / 5 bytes; the placeholder starts right after it.
487        let sql = "SELECT * WHERE name = 'café' AND x = :p";
488        let result = scan_sql(sql).unwrap();
489        assert_eq!(placeholder_names(&result), vec!["p"]);
490        let pos = result.placeholders[0].position;
491        assert_eq!(pos.offset, sql.chars().count() - 2);
492    }
493
494    #[test]
495    fn multiline_sql_reports_correct_line_and_column() {
496        let sql = "SELECT *\nFROM v\nWHERE x = :p";
497        let result = scan_sql(sql).unwrap();
498        assert_eq!(result.tables[0].position.line, 2);
499        assert_eq!(result.tables[0].position.column, 6);
500        assert_eq!(result.placeholders[0].position.line, 3);
501        assert_eq!(result.placeholders[0].position.column, 11);
502    }
503
504    #[test]
505    fn tokenizer_failure_is_reported_as_scan_error() {
506        // An unterminated string literal cannot be tokenized at all.
507        let err = scan_sql("SELECT 'unterminated").unwrap_err();
508        assert!(matches!(err, ScanError::Tokenize(_)));
509    }
510
511    #[test]
512    fn undeclared_tables_helper_is_case_insensitive_and_ordered() {
513        let result = scan_sql("SELECT * FROM a JOIN B JOIN c").unwrap();
514        let declared = vec!["A".to_string(), "c".to_string()];
515        let undeclared = undeclared_tables(&result, &declared);
516        assert_eq!(
517            undeclared
518                .iter()
519                .map(|t| t.name.as_str())
520                .collect::<Vec<_>>(),
521            vec!["B"]
522        );
523    }
524}
helios_sof/sqlquery/scan.rs

helios_sof/sqlquery/
scan.rs
