Skip to main content

dsl_resolve/
resolver.rs

1//! Walk a parsed statement and produce its [`Scope`].
2//!
3//! Resolution is one pass: every FROM / JOIN reference adds a binding
4//! under both its alias (if present) and its bare table name. Subsequent
5//! lookups by either form resolve to the same row.
6
7use crate::binding::Binding;
8use crate::scope::Scope;
9use dsl_parse::{Statement, StatementKind, TableRef};
10
11/// Resolve every statement in `stmts`. Returns one [`Scope`] per statement,
12/// in matching order, so callers can index by statement position.
13///
14/// CTE column projections are populated as empty `Vec`s -- use
15/// [`resolve_with_source`] if you have the raw source text and want the
16/// resolver to extract projection column names from each CTE body.
17pub fn resolve(stmts: &[Statement]) -> Vec<Scope> {
18  stmts.iter().map(|s| resolve_one(s, None)).collect()
19}
20
21/// Resolve as above, but use `source` to populate `Scope.cte_columns`
22/// with the projection column names declared by each CTE body's outer
23/// SELECT. Best-effort -- subqueries / function calls / `*` show up as
24/// empty Vecs.
25pub fn resolve_with_source(stmts: &[Statement], source: &str) -> Vec<Scope> {
26  stmts.iter().map(|s| resolve_one(s, Some(source))).collect()
27}
28
29fn resolve_one(stmt: &Statement, source: Option<&str>) -> Scope {
30  let mut scope = Scope::default();
31  match &stmt.kind {
32    StatementKind::Select(s) => {
33      // Bind CTE names first so they're visible to FROM lookups
34      // when the same CTE appears later in the same SELECT.
35      for name in &s.cte_names {
36        add_synthetic(&mut scope, name);
37        let cols = match source {
38          Some(src) => extract_cte_columns(src, stmt, name),
39          None => Vec::new(),
40        };
41        scope.cte_columns.entry(name.clone()).or_insert(cols);
42      }
43      for t in &s.from {
44        add(&mut scope, t);
45      }
46      for j in &s.joins {
47        add(&mut scope, &j.table);
48      }
49    },
50    StatementKind::Update(u) => {
51      add(&mut scope, &u.table);
52      for t in &u.from_tables {
53        add(&mut scope, t);
54      }
55    },
56    StatementKind::Delete(d) => {
57      add(&mut scope, &d.table);
58      for t in &d.using_tables {
59        add(&mut scope, t);
60      }
61    },
62    StatementKind::Insert(i) => add(&mut scope, &i.table),
63    _ => {},
64  }
65  scope
66}
67
68/// Find `WITH [RECURSIVE] <name> [(col, ...)] AS [MATERIALIZED] (...)`
69/// inside the statement source and return the projection column names.
70///
71/// Two cases:
72///   - explicit column list after the CTE name -- use those names
73///   - else parse the inner SELECT projection and extract aliases
74fn extract_cte_columns(source: &str, stmt: &Statement, name: &str) -> Vec<String> {
75  let start: usize = u32::from(stmt.range.start()) as usize;
76  let end: usize = (u32::from(stmt.range.end()) as usize).min(source.len());
77  let body = &source[start..end];
78  let upper = body.to_ascii_uppercase();
79  let bytes = body.as_bytes();
80  let n = bytes.len();
81  let name_up = name.to_ascii_uppercase();
82  // Skip `WITH` (and optional `RECURSIVE`).
83  let mut i = match upper.find("WITH") {
84    Some(p) => p + 4,
85    None => return Vec::new(),
86  };
87  loop {
88    while i < n && bytes[i].is_ascii_whitespace() {
89      i += 1;
90    }
91    if i + 9 <= n && upper[i..i + 9] == *"RECURSIVE" {
92      i += 9;
93      while i < n && bytes[i].is_ascii_whitespace() {
94        i += 1;
95      }
96    }
97    // Read CTE name.
98    let name_start = i;
99    while i < n && is_word(bytes[i] as char) {
100      i += 1;
101    }
102    if name_start == i {
103      return Vec::new();
104    }
105    let cur_name = &upper[name_start..i];
106    let is_target = cur_name == name_up;
107    while i < n && bytes[i].is_ascii_whitespace() {
108      i += 1;
109    }
110    // Optional `(col, ...)`.
111    let mut explicit_cols: Vec<String> = Vec::new();
112    if i < n && bytes[i] == b'(' {
113      let list_start = i + 1;
114      let mut depth = 1i32;
115      i += 1;
116      while i < n && depth > 0 {
117        match bytes[i] {
118          b'(' => depth += 1,
119          b')' => depth -= 1,
120          _ => {},
121        }
122        if depth == 0 {
123          break;
124        }
125        i += 1;
126      }
127      if is_target {
128        let raw = &body[list_start..i];
129        explicit_cols =
130          raw.split(',').map(|s| s.trim().trim_matches('"').to_string()).filter(|s| !s.is_empty()).collect();
131      }
132      i += 1; // past `)`
133      while i < n && bytes[i].is_ascii_whitespace() {
134        i += 1;
135      }
136    }
137    // `AS`.
138    if i + 2 > n || !body[i..i + 2].eq_ignore_ascii_case("AS") {
139      return explicit_cols;
140    }
141    i += 2;
142    while i < n && bytes[i].is_ascii_whitespace() {
143      i += 1;
144    }
145    for kw in ["NOT MATERIALIZED", "MATERIALIZED"] {
146      if i + kw.len() <= n && body[i..i + kw.len()].eq_ignore_ascii_case(kw) {
147        i += kw.len();
148        while i < n && bytes[i].is_ascii_whitespace() {
149          i += 1;
150        }
151        break;
152      }
153    }
154    if i >= n || bytes[i] != b'(' {
155      return explicit_cols;
156    }
157    let body_open = i + 1;
158    let mut depth = 1i32;
159    let mut j = body_open;
160    while j < n && depth > 0 {
161      match bytes[j] {
162        b'(' => depth += 1,
163        b')' => depth -= 1,
164        b'\'' => {
165          j += 1;
166          while j < n && bytes[j] != b'\'' {
167            j += 1;
168          }
169        },
170        _ => {},
171      }
172      if depth == 0 {
173        break;
174      }
175      j += 1;
176    }
177    if j >= n {
178      return explicit_cols;
179    }
180    if is_target {
181      if !explicit_cols.is_empty() {
182        return explicit_cols;
183      }
184      let cte_body = &body[body_open..j];
185      return projection_columns(cte_body);
186    }
187    // Not our CTE -- skip past `,` and continue with the next CTE.
188    i = j + 1;
189    while i < n && bytes[i].is_ascii_whitespace() {
190      i += 1;
191    }
192    if i >= n || bytes[i] != b',' {
193      return Vec::new();
194    }
195    i += 1;
196  }
197}
198
199/// Extract projection column names from a CTE body. Looks for the
200/// outermost `SELECT ...` and parses each comma-separated projection.
201///
202/// The scan tracks paren depth and skips string literals, double-quoted
203/// identifiers, dollar-quoted strings (`$tag$...$tag$`), line comments
204/// (`-- ...`), and block comments (`/* ... */`) so that keywords or
205/// commas inside any of those don't affect projection boundaries.
206fn projection_columns(cte_body: &str) -> Vec<String> {
207  let bytes = cte_body.as_bytes();
208  let n = bytes.len();
209  // Find outer SELECT, skipping comments and strings.
210  let Some(sel) = find_keyword_outside(bytes, 0, b"SELECT") else { return Vec::new() };
211  let proj_start = sel + 6;
212  // Find top-level FROM at depth 0, outside strings/comments.
213  let from_at = find_keyword_outside(bytes, proj_start, b"FROM").unwrap_or(n);
214  let proj_text = &cte_body[proj_start..from_at];
215  // Split on top-level commas, also skipping strings/comments.
216  let pbytes = proj_text.as_bytes();
217  let pn = pbytes.len();
218  let mut out: Vec<String> = Vec::new();
219  let mut depth = 0i32;
220  let mut start = 0usize;
221  let mut i = 0usize;
222  while i < pn {
223    if let Some(skip) = skip_string_or_comment(pbytes, i) {
224      i = skip;
225      continue;
226    }
227    match pbytes[i] {
228      b'(' => depth += 1,
229      b')' => depth -= 1,
230      b',' if depth == 0 => {
231        out.push(alias_of(&proj_text[start..i]));
232        start = i + 1;
233      },
234      _ => {},
235    }
236    i += 1;
237  }
238  if start < pn {
239    out.push(alias_of(&proj_text[start..]));
240  }
241  out.into_iter().filter(|s| !s.is_empty()).collect()
242}
243
244/// Return new cursor past a string literal, identifier quote, dollar-quote,
245/// or comment starting at `i`. Returns `None` if `i` is not such a span.
246fn skip_string_or_comment(bytes: &[u8], i: usize) -> Option<usize> {
247  let n = bytes.len();
248  if i >= n {
249    return None;
250  }
251  match bytes[i] {
252    // Single-quoted string. Doubled '' is an escaped quote.
253    b'\'' => {
254      let mut j = i + 1;
255      while j < n {
256        if bytes[j] == b'\'' {
257          if j + 1 < n && bytes[j + 1] == b'\'' {
258            j += 2;
259            continue;
260          }
261          return Some(j + 1);
262        }
263        j += 1;
264      }
265      Some(n)
266    },
267    // Double-quoted identifier. Doubled "" is an escaped quote.
268    b'"' => {
269      let mut j = i + 1;
270      while j < n {
271        if bytes[j] == b'"' {
272          if j + 1 < n && bytes[j + 1] == b'"' {
273            j += 2;
274            continue;
275          }
276          return Some(j + 1);
277        }
278        j += 1;
279      }
280      Some(n)
281    },
282    // Line comment `-- ...` to end of line.
283    b'-' if i + 1 < n && bytes[i + 1] == b'-' => {
284      let mut j = i + 2;
285      while j < n && bytes[j] != b'\n' {
286        j += 1;
287      }
288      Some(j)
289    },
290    // Block comment `/* ... */` (non-nested -- good enough for projection scan).
291    b'/' if i + 1 < n && bytes[i + 1] == b'*' => {
292      let mut j = i + 2;
293      while j + 1 < n && !(bytes[j] == b'*' && bytes[j + 1] == b'/') {
294        j += 1;
295      }
296      Some((j + 2).min(n))
297    },
298    // Dollar-quoted string `$tag$ ... $tag$` (tag may be empty).
299    b'$' => {
300      // Read optional tag of [A-Za-z0-9_]* until next `$`.
301      let mut j = i + 1;
302      while j < n && (bytes[j].is_ascii_alphanumeric() || bytes[j] == b'_') {
303        j += 1;
304      }
305      if j >= n || bytes[j] != b'$' {
306        return None;
307      }
308      let tag = &bytes[i..j + 1]; // includes both `$`s
309      let body_start = j + 1;
310      let mut k = body_start;
311      while k + tag.len() <= n {
312        if &bytes[k..k + tag.len()] == tag {
313          return Some(k + tag.len());
314        }
315        k += 1;
316      }
317      Some(n)
318    },
319    _ => None,
320  }
321}
322
323/// Find `kw` (case-insensitive) as a word-bounded match at depth 0,
324/// outside strings/comments. `kw` must be uppercase ASCII.
325/// For `FROM`, requires whitespace on the left side; right side allows
326/// whitespace, `(`, or end-of-input.
327fn find_keyword_outside(bytes: &[u8], from: usize, kw: &[u8]) -> Option<usize> {
328  let n = bytes.len();
329  let klen = kw.len();
330  let mut depth = 0i32;
331  let mut i = from;
332  while i + klen <= n {
333    if let Some(skip) = skip_string_or_comment(bytes, i) {
334      i = skip;
335      continue;
336    }
337    match bytes[i] {
338      b'(' => {
339        depth += 1;
340        i += 1;
341        continue;
342      },
343      b')' => {
344        depth -= 1;
345        i += 1;
346        continue;
347      },
348      _ => {},
349    }
350    if depth == 0 {
351      // Word-boundary check on the left.
352      let left_ok = i == from || !is_ident_byte(bytes[i - 1]);
353      if left_ok {
354        let mut matched = true;
355        for (off, kb) in kw.iter().enumerate() {
356          if bytes[i + off].to_ascii_uppercase() != *kb {
357            matched = false;
358            break;
359          }
360        }
361        if matched {
362          let right_ok = i + klen == n || !is_ident_byte(bytes[i + klen]);
363          if right_ok {
364            return Some(i);
365          }
366        }
367      }
368    }
369    i += 1;
370  }
371  None
372}
373
374fn is_ident_byte(b: u8) -> bool {
375  b.is_ascii_alphanumeric() || b == b'_'
376}
377
378/// Return the alias of a projection expression: `expr AS alias` ->
379/// `alias`; `t.col` -> `col`; `col` -> `col`; `*` -> empty.
380fn alias_of(proj: &str) -> String {
381  let trimmed = proj.trim();
382  if trimmed == "*" {
383    return String::new();
384  }
385  let upper = trimmed.to_ascii_uppercase();
386  if let Some(at) = upper.rfind(" AS ") {
387    return trimmed[at + 4..].trim().trim_matches('"').to_string();
388  }
389  // Trailing identifier-only alias (no `AS`).
390  let bytes = trimmed.as_bytes();
391  let n = bytes.len();
392  // Walk back over an identifier.
393  let mut end = n;
394  while end > 0 && (bytes[end - 1].is_ascii_alphanumeric() || bytes[end - 1] == b'_') {
395    end -= 1;
396  }
397  let tail = &trimmed[end..];
398  // If preceded by whitespace and there's a non-id chunk before, treat
399  // tail as alias.
400  if !tail.is_empty()
401    && end > 0
402    && bytes[end - 1].is_ascii_whitespace()
403    && tail.chars().next().is_some_and(|c| c.is_alphabetic() || c == '_')
404  {
405    return tail.trim().trim_matches('"').to_string();
406  }
407  // Otherwise treat the whole projection as a column reference.
408  let tail = trimmed.rsplit('.').next().unwrap_or(trimmed).trim().trim_matches('"');
409  tail.to_string()
410}
411
412fn is_word(c: char) -> bool {
413  c.is_alphanumeric() || c == '_'
414}
415
416/// Bind a synthetic table reference (CTE / subquery alias). Columns of
417/// the underlying body aren't resolved yet -- a future pass can promote
418/// these from name-only to fully-typed bindings.
419fn add_synthetic(scope: &mut Scope, name: &str) {
420  if name.is_empty() {
421    return;
422  }
423  let table = dsl_parse::TableRef { name: name.to_string(), ..Default::default() };
424  scope.bindings.entry(name.to_string()).or_insert(Binding { alias: name.to_string(), table });
425}
426
427fn add(scope: &mut Scope, table: &TableRef) {
428  if table.name.is_empty() {
429    return;
430  }
431  let entry = Binding { alias: table.alias.clone().unwrap_or_else(|| table.name.clone()), table: table.clone() };
432  if let Some(alias) = &table.alias {
433    scope.bindings.insert(alias.clone(), entry.clone());
434  }
435  // Always also bind by the unaliased name so users can reference the
436  // table without an alias inside the same query.
437  scope.bindings.entry(table.name.clone()).or_insert(entry);
438}