Skip to main content

quarb_sql/
lib.rs

1//! SQL importer for Quarb.
2//!
3//! Translates a SQL `SELECT` statement into an equivalent Quarb
4//! query, following the mapping in the SQL cookbook — in reverse.
5//! The translatable subset covers the single-statement query core;
6//! everything else is refused with an
7//! [`SqlError::Unsupported`] naming the construct, never silently
8//! approximated.
9//!
10//! - `SELECT cols FROM t` → `/t/* | %(::col; …)`; `SELECT *` →
11//!   the row nodes; `SELECT DISTINCT col` → `/t/*::col @| unique`,
12//!   and over several columns the records, `| %(…) @| unique`.
13//! - `WHERE` → a predicate that holds exactly where SQL finds the
14//!   condition TRUE. SQL's logic has a third value for a comparison
15//!   with a NULL, so `<>` is guarded (`::x != null && ::x != "GB"`)
16//!   and a `NOT` is carried inward to the comparisons; `IS [NOT]
17//!   NULL` → `= null` / `!= null`; `[NOT] IN (…)` → a chain of
18//!   equalities; `[NOT] LIKE` → a regex, `%` a run of characters and
19//!   `_` one.
20//! - Aggregates (`COUNT(*)`, `SUM`/`AVG`/`MIN`/`MAX`) → `@|`
21//!   reductions over the piped column, `COUNT(col)` →
22//!   `count(--values)`; `GROUP BY k` → `| .k(::k) @|{.k}` with the
23//!   aggregate folding by the pushed key and `HAVING` a filter
24//!   after it.
25//! - `JOIN t2 ON …` → the every-witness correlation, one thread for
26//!   every pair as SQL has one row: `/t1/* <=>* /t2/*[::b =
27//!   $$0::a]`, the FROM table driving, the ON in the joined
28//!   expression's bracket, the joined side's columns read through
29//!   the witness (`$$1::col`). `LEFT JOIN` → `<=>*?`, which keeps a
30//!   driver with no pair, its WHERE a filter after the join; `RIGHT
31//!   JOIN` is `LEFT` with the tables' places exchanged; `CROSS JOIN`
32//!   is every pair. The ON is any condition.
33//! - `UNION ALL` of single columns of different tables → a branch
34//!   union, `/t/*::a || /u/*::b`; `UNION` the same and `@| unique`.
35//! - `ORDER BY` → `@| sort_by(…)` (`DESC` via `@| reverse`);
36//!   `LIMIT n` → `@| [..n]`.
37//!
38//! Refused: subqueries, window functions, `CASE`, a `FULL` join,
39//! multi-join chains (one `JOIN` translates), `SELECT *` over a
40//! join, `UNION ALL` over one table twice (a branch union keeps one
41//! thread for a node two branches reach), a comparison with a NULL
42//! literal, `HAVING` without `GROUP BY`, aggregate arithmetic
43//! (`SUM(a) + 1`), and any non-`SELECT` statement.
44//!
45//! Each translation is held against SQLite's own answer over one
46//! database (the differential rig of `tests/sql.rs`). What differs
47//! between SQL engines themselves is reported as a
48//! [`Translation::notes`] line rather than refused:
49//!
50//! - Quarb streams records (JSONL), not a result table.
51//! - `LIKE` translates to a case-insensitive regex (matching
52//!   MySQL's and SQLite's default folding; PostgreSQL's `LIKE`
53//!   is case-sensitive).
54//! - `ORDER BY` puts a NULL key last, first under `DESC`, as
55//!   PostgreSQL does; SQLite and MySQL put it first.
56
57mod export;
58pub use export::{
59    ColumnTypes, Dialect, Partial, Pushdown, export, partial_pushdown, partial_pushdown_explained,
60    partial_pushdown_keyed, pushdown, pushdown_explained,
61};
62
63use quarb::diagnostic as d;
64use std::fmt::Write as _;
65
66/// An error translating a SQL statement.
67#[derive(Debug, thiserror::Error)]
68pub enum SqlError {
69    #[error("SQL syntax error: {0}")]
70    Syntax(String),
71    #[error("unsupported SQL construct: {0}")]
72    Unsupported(String),
73    /// A construct of SQL with no Quarb translation: the diagnostic
74    /// code of the reason (`JOIN_NOT_TRANSLATED`; ruling 2026-11-17,
75    /// one word per reason) and the reason.
76    #[error("unsupported SQL construct: {1}")]
77    NotTranslated(&'static str, String),
78    /// SQL can spell the construct, but with provably different
79    /// semantics (NULL propagation, collation, coercion) — the
80    /// refusal names the divergence, not a missing feature.
81    #[error("semantic mismatch: {0}")]
82    Semantics(String),
83    /// A part of a Quarb query the exporter leaves to the engine:
84    /// the word a planner's refusal is told under, whether SQL
85    /// could spell the part with other semantics (`mismatch`) or
86    /// has no form for it, and the reason.
87    #[error("{}: {reason}", class(*.mismatch))]
88    NotPushed {
89        word: Refusal,
90        mismatch: bool,
91        reason: String,
92    },
93}
94
95/// The class an exporter's refusal prints before its reason.
96fn class(mismatch: bool) -> &'static str {
97    if mismatch {
98        "semantic mismatch"
99    } else {
100        "unsupported SQL construct"
101    }
102}
103
104impl SqlError {
105    /// The word and the reason of an exporter's refusal; `None` for
106    /// a syntax error and for an importer's error.
107    pub fn not_pushed(&self) -> Option<(Refusal, &str)> {
108        match self {
109            SqlError::NotPushed { word, reason, .. } => Some((*word, reason)),
110            _ => None,
111        }
112    }
113
114    /// The code and the reason of an importer's refusal, and
115    /// whether `--lenient` translates what was refused: never, the
116    /// SQL bridge has no lenient form.
117    pub fn not_translated(&self) -> Option<(&'static str, &str, bool)> {
118        match self {
119            SqlError::NotTranslated(code, reason) => Some((code, reason, false)),
120            _ => None,
121        }
122    }
123}
124
125/// Why the exporter leaves a part of a Quarb query to the engine:
126/// the first word of the diagnostic code a planner's refusal is told
127/// under (`Sort` is `SORT_NOT_PUSHED`; ruling 2026-11-17, one word
128/// per reason where `NOT_PUSHED` was the one kind). The word names
129/// what the user wrote; the inventory (`langspec/diagnostics.tsv`)
130/// files each under its remedy.
131#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
132pub enum Refusal {
133    /// A sort (`sort_by`, `top`, `reverse`): a database orders text
134    /// by its own collation.
135    Sort,
136    /// A fold, a command over its groups, a HAVING.
137    Fold,
138    /// `unique`: DISTINCT returns rows in no stated order.
139    Unique,
140    /// A selection by position.
141    Take,
142    /// A negation: SQL drops the rows whose column is empty.
143    Negation,
144    /// A regular expression, a substring test, a LIKE.
145    Pattern,
146    /// A condition that follows a reference or navigates.
147    Resolution,
148    /// Navigation beyond a table's rows.
149    Walk,
150    /// A read of the query's own state: a register, the topic, a
151    /// capture, a mark, a pushed value.
152    State,
153    /// A correlation in a form with no JOIN.
154    Join,
155    /// A reducer over row nodes, or one SQL has no aggregate for.
156    Reducer,
157    /// A comparison that would follow the column's declared type
158    /// where the engine follows each value.
159    Type,
160    /// A union of branches.
161    Union,
162    /// An operator, a command or a projection with no SQL form.
163    Operator,
164    /// A name or a literal with no spelling every dialect reads, or
165    /// an empty query.
166    Name,
167    /// A leading condition a partial plan could not send ahead:
168    /// what follows would see the difference.
169    Condition,
170    /// A partial plan with no leading condition to send ahead:
171    /// nothing was refused, there was nothing to push, and no
172    /// diagnostic tells of it.
173    Nothing,
174    /// A whole plan for a query that ends on row nodes: their
175    /// locators are the scan's to write. Nothing the reader wrote
176    /// is refused (the conditions go ahead through the partial
177    /// plan), and no diagnostic tells of it.
178    Nodes,
179}
180
181impl Refusal {
182    /// The diagnostic code; `None` for [`Refusal::Nothing`] and
183    /// [`Refusal::Nodes`].
184    pub fn code(self) -> Option<&'static str> {
185        use quarb::diagnostic as d;
186        Some(match self {
187            Refusal::Sort => d::SORT_NOT_PUSHED,
188            Refusal::Fold => d::FOLD_NOT_PUSHED,
189            Refusal::Unique => d::UNIQUE_NOT_PUSHED,
190            Refusal::Take => d::TAKE_NOT_PUSHED,
191            Refusal::Negation => d::NEGATION_NOT_PUSHED,
192            Refusal::Pattern => d::PATTERN_NOT_PUSHED,
193            Refusal::Resolution => d::RESOLUTION_NOT_PUSHED,
194            Refusal::Walk => d::WALK_NOT_PUSHED,
195            Refusal::State => d::STATE_NOT_PUSHED,
196            Refusal::Join => d::JOIN_NOT_PUSHED,
197            Refusal::Reducer => d::REDUCER_NOT_PUSHED,
198            Refusal::Type => d::TYPE_NOT_PUSHED,
199            Refusal::Union => d::UNION_NOT_PUSHED,
200            Refusal::Operator => d::OPERATOR_NOT_PUSHED,
201            Refusal::Name => d::NAME_NOT_PUSHED,
202            Refusal::Condition => d::CONDITION_NOT_PUSHED,
203            Refusal::Nothing | Refusal::Nodes => return None,
204        })
205    }
206}
207
208/// A successful translation: the Quarb query, plus notes on known
209/// semantic divergences that apply to it.
210#[derive(Debug)]
211pub struct Translation {
212    pub query: String,
213    pub notes: Vec<String>,
214}
215
216// ---------------------------------------------------------------
217// Lexer
218// ---------------------------------------------------------------
219
220#[derive(Debug, Clone, PartialEq)]
221enum Tok {
222    /// A bare identifier or keyword (uppercased for keywords).
223    Word(String),
224    /// A 'string literal'.
225    Str(String),
226    Num(String),
227    Sym(char),
228    /// `<=`, `>=`, `<>`, `!=`
229    Op2(String),
230}
231
232fn lex(input: &str) -> Result<Vec<Tok>, SqlError> {
233    let chars: Vec<char> = input.chars().collect();
234    let mut out = Vec::new();
235    let mut i = 0;
236    while i < chars.len() {
237        let c = chars[i];
238        if c.is_whitespace() {
239            i += 1;
240            continue;
241        }
242        if c == '\'' {
243            let mut s = String::new();
244            i += 1;
245            loop {
246                match chars.get(i) {
247                    Some('\'') if chars.get(i + 1) == Some(&'\'') => {
248                        s.push('\'');
249                        i += 2;
250                    }
251                    Some('\'') => {
252                        i += 1;
253                        break;
254                    }
255                    Some(&ch) => {
256                        s.push(ch);
257                        i += 1;
258                    }
259                    None => return Err(SqlError::Syntax("unterminated string".into())),
260                }
261            }
262            out.push(Tok::Str(s));
263            continue;
264        }
265        if c.is_ascii_digit() {
266            let mut s = String::new();
267            let mut dotted = false;
268            while let Some(&ch) = chars.get(i) {
269                if ch.is_ascii_digit() || (ch == '.' && !dotted) {
270                    dotted |= ch == '.';
271                    s.push(ch);
272                    i += 1;
273                } else {
274                    break;
275                }
276            }
277            out.push(Tok::Num(s));
278            continue;
279        }
280        if c.is_alphabetic() || c == '_' || c == '"' || c == '`' {
281            // Quoted identifiers keep their case; bare words are
282            // identifiers-or-keywords (keywords match uppercased).
283            if c == '"' || c == '`' {
284                let quote = c;
285                let mut s = String::new();
286                let mut closed = false;
287                i += 1;
288                while let Some(&ch) = chars.get(i) {
289                    i += 1;
290                    if ch == quote {
291                        closed = true;
292                        break;
293                    }
294                    s.push(ch);
295                }
296                if !closed {
297                    return Err(SqlError::Syntax("unterminated quoted identifier".into()));
298                }
299                out.push(Tok::Word(s));
300                continue;
301            }
302            let mut s = String::new();
303            while let Some(&ch) = chars.get(i) {
304                if ch.is_alphanumeric() || ch == '_' {
305                    s.push(ch);
306                    i += 1;
307                } else {
308                    break;
309                }
310            }
311            out.push(Tok::Word(s));
312            continue;
313        }
314        if (c == '<' && matches!(chars.get(i + 1), Some('=') | Some('>')))
315            || (c == '>' && chars.get(i + 1) == Some(&'='))
316            || (c == '!' && chars.get(i + 1) == Some(&'='))
317        {
318            out.push(Tok::Op2(format!("{c}{}", chars[i + 1])));
319            i += 2;
320            continue;
321        }
322        if "(),.*=<>;-".contains(c) {
323            out.push(Tok::Sym(c));
324            i += 1;
325            continue;
326        }
327        return Err(SqlError::Syntax(format!("unexpected character '{c}'")));
328    }
329    Ok(out)
330}
331
332// ---------------------------------------------------------------
333// Parser / translator
334// ---------------------------------------------------------------
335
336/// A column reference: optionally table-qualified.
337#[derive(Debug, Clone)]
338struct ColRef {
339    table: Option<String>,
340    column: String,
341}
342
343#[derive(Debug, Clone)]
344enum Scalar {
345    Col(ColRef),
346    Str(String),
347    Num(String),
348    Null,
349}
350
351#[derive(Debug)]
352enum Cond {
353    Cmp(ColRef, String, Scalar),
354    /// An aggregate call compared to a scalar — HAVING only.
355    AggCmp(Agg, Option<ColRef>, String, Scalar),
356    Like(ColRef, String),
357    IsNull(ColRef, bool),
358    In(ColRef, Vec<Scalar>),
359    And(Box<Cond>, Box<Cond>),
360    Or(Box<Cond>, Box<Cond>),
361    Not(Box<Cond>),
362}
363
364#[derive(Debug, Clone, PartialEq)]
365enum Agg {
366    Count,
367    CountCol,
368    Sum,
369    Avg,
370    Min,
371    Max,
372}
373
374/// The aggregate a keyword names, if any.
375fn agg_kw(w: &str) -> Option<Agg> {
376    match w.to_ascii_uppercase().as_str() {
377        "COUNT" => Some(Agg::Count),
378        "SUM" => Some(Agg::Sum),
379        "AVG" => Some(Agg::Avg),
380        "MIN" => Some(Agg::Min),
381        "MAX" => Some(Agg::Max),
382        _ => None,
383    }
384}
385
386#[derive(Debug)]
387enum SelectItem {
388    Star,
389    Col(ColRef, Option<String>),
390    Agg(Agg, Option<ColRef>, Option<String>),
391}
392
393struct Parser {
394    toks: Vec<Tok>,
395    pos: usize,
396}
397
398impl Parser {
399    fn peek(&self) -> Option<&Tok> {
400        self.toks.get(self.pos)
401    }
402
403    fn kw(&mut self, word: &str) -> bool {
404        if matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case(word)) {
405            self.pos += 1;
406            true
407        } else {
408            false
409        }
410    }
411
412    fn expect_kw(&mut self, word: &str) -> Result<(), SqlError> {
413        if self.kw(word) {
414            Ok(())
415        } else {
416            Err(SqlError::Syntax(format!("expected {word}")))
417        }
418    }
419
420    fn sym(&mut self, c: char) -> bool {
421        if self.peek() == Some(&Tok::Sym(c)) {
422            self.pos += 1;
423            true
424        } else {
425            false
426        }
427    }
428
429    fn ident(&mut self) -> Result<String, SqlError> {
430        match self.peek() {
431            Some(Tok::Word(w)) => {
432                let w = w.clone();
433                self.pos += 1;
434                Ok(w)
435            }
436            other => Err(SqlError::Syntax(format!(
437                "expected an identifier, found {other:?}"
438            ))),
439        }
440    }
441
442    fn col_ref(&mut self) -> Result<ColRef, SqlError> {
443        let first = self.ident()?;
444        if self.sym('.') {
445            let column = self.ident()?;
446            Ok(ColRef {
447                table: Some(first),
448                column,
449            })
450        } else {
451            Ok(ColRef {
452                table: None,
453                column: first,
454            })
455        }
456    }
457
458    fn scalar(&mut self) -> Result<Scalar, SqlError> {
459        match self.peek().cloned() {
460            Some(Tok::Str(s)) => {
461                self.pos += 1;
462                Ok(Scalar::Str(s))
463            }
464            Some(Tok::Num(n)) => {
465                self.pos += 1;
466                Ok(Scalar::Num(n))
467            }
468            Some(Tok::Sym('-')) => {
469                self.pos += 1;
470                match self.peek().cloned() {
471                    Some(Tok::Num(n)) => {
472                        self.pos += 1;
473                        Ok(Scalar::Num(format!("-{n}")))
474                    }
475                    _ => Err(SqlError::Syntax("expected a number after '-'".into())),
476                }
477            }
478            Some(Tok::Word(w)) if w.eq_ignore_ascii_case("NULL") => {
479                self.pos += 1;
480                Ok(Scalar::Null)
481            }
482            Some(Tok::Word(_)) => Ok(Scalar::Col(self.col_ref()?)),
483            other => Err(SqlError::Syntax(format!(
484                "expected a value, found {other:?}"
485            ))),
486        }
487    }
488
489    // cond := and_cond (OR and_cond)*
490    fn cond(&mut self) -> Result<Cond, SqlError> {
491        let mut left = self.and_cond()?;
492        while self.kw("OR") {
493            let right = self.and_cond()?;
494            left = Cond::Or(Box::new(left), Box::new(right));
495        }
496        Ok(left)
497    }
498
499    fn and_cond(&mut self) -> Result<Cond, SqlError> {
500        let mut left = self.not_cond()?;
501        while self.kw("AND") {
502            let right = self.not_cond()?;
503            left = Cond::And(Box::new(left), Box::new(right));
504        }
505        Ok(left)
506    }
507
508    fn not_cond(&mut self) -> Result<Cond, SqlError> {
509        if self.kw("NOT") {
510            return Ok(Cond::Not(Box::new(self.not_cond()?)));
511        }
512        if self.sym('(') {
513            let inner = self.cond()?;
514            if !self.sym(')') {
515                return Err(SqlError::Syntax("expected ')'".into()));
516            }
517            return Ok(inner);
518        }
519        self.comparison()
520    }
521
522    /// An aggregate call's argument list: the parser is past the
523    /// name, at `(`. Returns the aggregate (COUNT refined to
524    /// CountCol) and its column, `None` for `(*)`.
525    fn agg_call(&mut self, mut a: Agg) -> Result<(Agg, Option<ColRef>), SqlError> {
526        self.pos += 1; // '('
527        let col = if self.sym('*') {
528            None
529        } else {
530            let c = self.col_ref()?;
531            if a == Agg::Count {
532                a = Agg::CountCol;
533            }
534            Some(c)
535        };
536        if !self.sym(')') {
537            return Err(SqlError::Syntax("expected ')' after aggregate".into()));
538        }
539        Ok((a, col))
540    }
541
542    fn cmp_op(&mut self) -> Result<String, SqlError> {
543        Ok(match self.peek().cloned() {
544            Some(Tok::Sym('=')) => {
545                self.pos += 1;
546                "=".to_string()
547            }
548            Some(Tok::Sym('<')) => {
549                self.pos += 1;
550                "<".to_string()
551            }
552            Some(Tok::Sym('>')) => {
553                self.pos += 1;
554                ">".to_string()
555            }
556            Some(Tok::Op2(o)) => {
557                self.pos += 1;
558                match o.as_str() {
559                    "<>" | "!=" => "!=".to_string(),
560                    other => other.to_string(),
561                }
562            }
563            other => {
564                return Err(SqlError::Syntax(format!(
565                    "expected an operator, found {other:?}"
566                )));
567            }
568        })
569    }
570
571    fn comparison(&mut self) -> Result<Cond, SqlError> {
572        // An aggregate call (`SUM(x) > 5`): meaningful in HAVING,
573        // refused with its own message in WHERE.
574        if let Some(Tok::Word(w)) = self.peek().cloned()
575            && let Some(a) = agg_kw(&w)
576            && matches!(self.toks.get(self.pos + 1), Some(Tok::Sym('(')))
577        {
578            self.pos += 1; // the name
579            let (a, col) = self.agg_call(a)?;
580            let op = self.cmp_op()?;
581            let rhs = self.scalar()?;
582            return Ok(Cond::AggCmp(a, col, op, rhs));
583        }
584        let col = self.col_ref()?;
585        if self.kw("IS") {
586            let not = self.kw("NOT");
587            self.expect_kw("NULL")?;
588            return Ok(Cond::IsNull(col, !not));
589        }
590        // `col NOT LIKE …`, `col NOT IN (…)`: the form, negated
591        let word_is = |t: Option<&Tok>, words: &[&str]| matches!(t, Some(Tok::Word(w)) if words.iter().any(|x| w.eq_ignore_ascii_case(x)));
592        let negated =
593            word_is(self.peek(), &["NOT"]) && word_is(self.toks.get(self.pos + 1), &["LIKE", "IN"]);
594        if negated {
595            self.pos += 1;
596        }
597        let said = |c: Cond| {
598            if negated { Cond::Not(Box::new(c)) } else { c }
599        };
600        if self.kw("LIKE") {
601            match self.peek().cloned() {
602                Some(Tok::Str(p)) => {
603                    self.pos += 1;
604                    return Ok(said(Cond::Like(col, p)));
605                }
606                _ => return Err(SqlError::Syntax("LIKE takes a string pattern".into())),
607            }
608        }
609        if self.kw("IN") {
610            if !self.sym('(') {
611                return Err(SqlError::Syntax("IN takes a parenthesized list".into()));
612            }
613            let mut items = Vec::new();
614            loop {
615                items.push(self.scalar()?);
616                if !self.sym(',') {
617                    break;
618                }
619            }
620            if !self.sym(')') {
621                return Err(SqlError::Syntax("expected ')' after IN list".into()));
622            }
623            return Ok(said(Cond::In(col, items)));
624        }
625        let op = self.cmp_op()?;
626        let rhs = self.scalar()?;
627        Ok(Cond::Cmp(col, op, rhs))
628    }
629}
630
631// ---------------------------------------------------------------
632// Emission
633// ---------------------------------------------------------------
634
635/// How a JOIN treats a row with no pair.
636#[derive(Debug, Clone, Copy, PartialEq, Eq)]
637enum JoinKind {
638    /// Every pair that satisfies the ON.
639    Inner,
640    /// The same, and the driver's rows that have no pair.
641    Left,
642    /// LEFT with the tables' places exchanged; resolved to `Left`
643    /// before anything is emitted.
644    Right,
645    /// Every pair.
646    Cross,
647}
648
649/// The tables in scope: (name, alias). The first is the FROM table
650/// — the driver under driver-first correlation; the second the
651/// JOIN table, whose witness the pipeline reads as `$$1`.
652struct Scope {
653    from: (String, Option<String>),
654    join: Option<(String, Option<String>)>,
655    /// Whether operands are being emitted inside the joined
656    /// expression's ON bracket (driver = `$$0::col`, joined side
657    /// bare) rather than in pipeline position (driver bare,
658    /// joined side = `$$1::col`).
659    on_clause: bool,
660}
661
662impl Scope {
663    /// Whether `col` belongs to the FROM (left) table: qualified by
664    /// its name or alias, or unqualified with no join.
665    fn is_left(&self, col: &ColRef) -> Result<bool, SqlError> {
666        let Some(q) = &col.table else {
667            if self.join.is_some() {
668                return Err(SqlError::NotTranslated(
669                    d::JOIN_NOT_TRANSLATED,
670                    format!("unqualified column '{}' in a JOIN (qualify it)", col.column),
671                ));
672            }
673            return Ok(true);
674        };
675        let matches = |(name, alias): &(String, Option<String>)| {
676            q.eq_ignore_ascii_case(name)
677                || alias.as_ref().is_some_and(|a| q.eq_ignore_ascii_case(a))
678        };
679        if matches(&self.from) {
680            Ok(true)
681        } else if self.join.as_ref().is_some_and(matches) {
682            Ok(false)
683        } else {
684            Err(SqlError::Syntax(format!("unknown table qualifier '{q}'")))
685        }
686    }
687
688    /// The operand for `col`. In pipeline position the driver's
689    /// columns are bare and the joined table's ride its witness
690    /// (`$$1::col`); inside the ON bracket the joined table's are
691    /// bare and the driver is reached as `$$0::col`.
692    fn operand(&self, col: &ColRef) -> Result<String, SqlError> {
693        let key = quarb_key(&col.column)?;
694        Ok(match (self.join.is_some(), self.on_clause) {
695            (false, _) => format!("::{key}"),
696            (true, false) if self.is_left(col)? => format!("::{key}"),
697            (true, false) => format!("$$1::{key}"),
698            (true, true) if self.is_left(col)? => format!("$$0::{key}"),
699            (true, true) => format!("::{key}"),
700        })
701    }
702
703    /// Whether an operand, inside the ON bracket, reads the driver
704    /// (`$$0::col`): a comparison with it is a key comparison of the
705    /// join, which the engine leaves unknown for a null on either
706    /// side.
707    fn keyed(&self, operand: &str) -> bool {
708        self.on_clause && operand.starts_with("$$")
709    }
710
711    /// Whether `c` tests a column of the FROM table for NULL: the one
712    /// condition a join's bracket cannot hold.
713    fn tests_driver_null(&self, c: &Cond) -> bool {
714        match c {
715            Cond::IsNull(col, _) => self.is_left(col).unwrap_or(false),
716            Cond::And(a, b) | Cond::Or(a, b) => {
717                self.tests_driver_null(a) || self.tests_driver_null(b)
718            }
719            Cond::Not(a) => self.tests_driver_null(a),
720            _ => false,
721        }
722    }
723
724    /// This scope, switched to ON-bracket emission.
725    fn on(&self) -> Scope {
726        Scope {
727            from: self.from.clone(),
728            join: self.join.clone(),
729            on_clause: true,
730        }
731    }
732}
733
734/// A SQL string as a Quarb string literal: double-quoted, with the
735/// Quarb lexer's `\"`, `\\`, `\$`, and `` \` `` escapes applied so
736/// the content survives verbatim (`$` would otherwise read as an
737/// interpolation).
738fn quarb_str(s: &str) -> String {
739    let mut out = String::with_capacity(s.len() + 2);
740    out.push('"');
741    for c in s.chars() {
742        if matches!(c, '"' | '\\' | '$' | '`') {
743            out.push('\\');
744        }
745        out.push(c);
746    }
747    out.push('"');
748    out
749}
750
751/// A SQL identifier as a Quarb name (a step matcher or projection
752/// key): bare when it lexes as one, single-quoted otherwise (a
753/// quoted SQL identifier can hold spaces or keywords). A name with
754/// a quote in it does not translate.
755fn quarb_key(name: &str) -> Result<String, SqlError> {
756    let bare = !name.is_empty()
757        && name
758            .chars()
759            .all(|c| c.is_alphanumeric() || matches!(c, '.' | '-' | '_' | '+'))
760        && !name.starts_with('.')
761        && !matches!(name, "and" | "or" | "not");
762    if bare {
763        return Ok(name.to_string());
764    }
765    if name.contains('\'') {
766        return Err(SqlError::NotTranslated(
767            d::NAME_NOT_TRANSLATED,
768            format!("the identifier {name:?} (a quote inside a quoted identifier)"),
769        ));
770    }
771    Ok(format!("'{name}'"))
772}
773
774/// A scalar as a Quarb operand; columns resolve through the scope.
775fn scalar_text(s: &Scalar, scope: &Scope) -> Result<String, SqlError> {
776    Ok(match s {
777        Scalar::Col(c) => scope.operand(c)?,
778        Scalar::Str(v) => quarb_str(v),
779        Scalar::Num(n) => n.clone(),
780        Scalar::Null => "null".to_string(),
781    })
782}
783
784/// The operator that holds exactly where `op` fails, both sides
785/// present.
786fn complement(op: &str) -> &'static str {
787    match op {
788        "=" => "!=",
789        "!=" => "=",
790        "<" => ">=",
791        "<=" => ">",
792        ">" => "<=",
793        _ => "<",
794    }
795}
796
797/// A LIKE pattern as a regex literal. The simple forms keep their
798/// short spelling (`%x%` is a search, `x%` and `%x` anchor one end);
799/// any other pattern is anchored at both ends, `%` any run of
800/// characters and `_` any one, a line break among them.
801fn like_regex(pat: &str) -> String {
802    let inner = pat.trim_matches('%');
803    if !inner.contains('%') && !inner.contains('_') {
804        let esc = regex_escape(inner);
805        return match (pat.starts_with('%'), pat.ends_with('%')) {
806            (true, true) => format!("(/(?i){esc}/)"),
807            (false, true) => format!("(/(?i)^{esc}/)"),
808            (true, false) => format!("(/(?i){esc}$/)"),
809            (false, false) => format!("(/(?i)^{esc}$/)"),
810        };
811    }
812    let mut body = String::new();
813    for c in pat.chars() {
814        match c {
815            '%' => body.push_str(".*"),
816            '_' => body.push('.'),
817            c => body.push_str(&regex_escape(&c.to_string())),
818        }
819    }
820    format!("(/(?is)^{body}$/)")
821}
822
823/// A condition as a Quarb predicate that holds exactly where SQL
824/// finds it TRUE (`truth`), or exactly where SQL finds it FALSE.
825///
826/// SQL's logic has a third value, UNKNOWN, for a comparison with a
827/// NULL, and a row passes WHERE only on TRUE. Quarb's is two-valued:
828/// a NULL differs from 'GB' (`!=` holds), two NULLs are equal, and
829/// the negation of a comparison that failed holds. So a negation is
830/// carried inward to the comparisons (`NOT (a AND b)` is where `a`
831/// is FALSE or `b` is), and a comparison that would hold for a NULL
832/// is guarded: `x <> 'GB'` is `::x != null && ::x != "GB"`. The
833/// ordering comparisons need no guard: none holds for a NULL.
834///
835/// Inside a join's bracket the engine reads a comparison with the
836/// driver as SQL does, unknown for a null on either side (spec:
837/// Correlation), so such a comparison takes no guard there; and a
838/// test of the driver's column for NULL cannot stand there at all
839/// ([`Scope::keyed`]).
840fn emit_cond(
841    c: &Cond,
842    truth: bool,
843    scope: &Scope,
844    notes: &mut Vec<String>,
845) -> Result<String, SqlError> {
846    Ok(match c {
847        Cond::Cmp(col, op, rhs) => {
848            if matches!(rhs, Scalar::Null) {
849                return Err(SqlError::NotTranslated(
850                    d::NULL_NOT_TRANSLATED,
851                    format!(
852                        "a comparison with NULL ('{} {op} NULL' is never true in SQL: write IS \
853                     NULL or IS NOT NULL)",
854                        col.column
855                    ),
856                ));
857            }
858            let op = if truth { op.as_str() } else { complement(op) };
859            let lhs = scope.operand(col)?;
860            let r = scalar_text(rhs, scope)?;
861            match (op, matches!(rhs, Scalar::Col(_))) {
862                // a key comparison of a join condition is unknown
863                // for a null on either side, as SQL's is
864                _ if scope.keyed(&lhs) || scope.keyed(&r) => format!("{lhs} {op} {r}"),
865                ("!=", false) => format!("{lhs} != null && {lhs} != {r}"),
866                ("!=", true) => format!("{lhs} != null && {r} != null && {lhs} != {r}"),
867                ("=", true) => format!("{lhs} != null && {lhs} = {r}"),
868                _ => format!("{lhs} {op} {r}"),
869            }
870        }
871        Cond::AggCmp(..) => {
872            return Err(SqlError::NotTranslated(
873                d::AGGREGATE_NOT_TRANSLATED,
874                "an aggregate in WHERE (SQL puts it in HAVING)".into(),
875            ));
876        }
877        Cond::Like(col, pat) => {
878            let lhs = scope.operand(col)?;
879            let note = "LIKE: translated to a case-insensitive regex (SQL's default \
880                        ASCII case folding)";
881            if !notes.iter().any(|n| n == note) {
882                notes.push(note.to_string());
883            }
884            let regex = like_regex(pat);
885            if truth {
886                format!("{lhs} == {regex}")
887            } else if scope.keyed(&lhs) {
888                format!("{lhs} != {regex}")
889            } else {
890                format!("{lhs} != null && !({lhs} == {regex})")
891            }
892        }
893        Cond::IsNull(col, is_null) => {
894            // `= null` / `!= null`: Quarb's `value_eq` treats NULL
895            // as an ordinary value, so these are exactly SQL's
896            // `IS [NOT] NULL` — truthiness (`not ::c`) would also
897            // drop 0 and ''.
898            let lhs = scope.operand(col)?;
899            if scope.keyed(&lhs) {
900                return Err(SqlError::NotTranslated(
901                    d::JOIN_NOT_TRANSLATED,
902                    format!(
903                        "IS NULL on '{}', the driving table's column, inside ON (a join condition \
904                     leaves a null key unknown: state it in WHERE)",
905                        col.column
906                    ),
907                ));
908            }
909            if *is_null == truth {
910                format!("{lhs} = null")
911            } else {
912                format!("{lhs} != null")
913            }
914        }
915        Cond::In(col, items) => {
916            let lhs = scope.operand(col)?;
917            let has_null = items.iter().any(|i| matches!(i, Scalar::Null));
918            let listed: Vec<&Scalar> = items
919                .iter()
920                .filter(|i| !matches!(i, Scalar::Null))
921                .collect();
922            if truth {
923                // a NULL in the list matches nothing
924                if listed.is_empty() {
925                    return Err(SqlError::NotTranslated(
926                        d::NULL_NOT_TRANSLATED,
927                        "IN over a list of NULL alone (never true in SQL)".into(),
928                    ));
929                }
930                let parts: Vec<String> = listed
931                    .iter()
932                    .map(|s| {
933                        let r = scalar_text(s, scope)?;
934                        let guarded =
935                            matches!(s, Scalar::Col(_)) && !scope.keyed(&lhs) && !scope.keyed(&r);
936                        Ok(if guarded {
937                            format!("{lhs} != null && {lhs} = {r}")
938                        } else {
939                            format!("{lhs} = {r}")
940                        })
941                    })
942                    .collect::<Result<_, SqlError>>()?;
943                format!("({})", parts.join(" || "))
944            } else {
945                if has_null {
946                    return Err(SqlError::NotTranslated(
947                        d::NULL_NOT_TRANSLATED,
948                        "NOT IN over a list with NULL (never true in SQL)".into(),
949                    ));
950                }
951                let mut parts = Vec::new();
952                if !scope.keyed(&lhs) {
953                    parts.push(format!("{lhs} != null"));
954                }
955                for s in listed {
956                    let r = scalar_text(s, scope)?;
957                    if matches!(s, Scalar::Col(_)) && !scope.keyed(&lhs) && !scope.keyed(&r) {
958                        parts.push(format!("{r} != null"));
959                    }
960                    parts.push(format!("{lhs} != {r}"));
961                }
962                parts.join(" && ")
963            }
964        }
965        // AND is TRUE where both are, FALSE where either is; OR the
966        // other way round. `&&` binds tighter than `||`, and a
967        // disjunction carries its own parentheses.
968        Cond::And(a, b) | Cond::Or(a, b) => {
969            let (a, b) = (
970                emit_cond(a, truth, scope, notes)?,
971                emit_cond(b, truth, scope, notes)?,
972            );
973            if matches!(c, Cond::And(..)) == truth {
974                format!("{a} && {b}")
975            } else {
976                format!("({a} || {b})")
977            }
978        }
979        Cond::Not(a) => emit_cond(a, !truth, scope, notes)?,
980    })
981}
982
983fn regex_escape(s: &str) -> String {
984    s.chars()
985        .flat_map(|c| {
986            if "\\.+*?()|[]{}^$/".contains(c) {
987                vec!['\\', c]
988            } else {
989                vec![c]
990            }
991        })
992        .collect()
993}
994
995/// The name an aggregate's field takes where the statement gives
996/// it no alias: the reducer's word.
997fn agg_word(a: &Agg) -> &'static str {
998    match a {
999        Agg::Count | Agg::CountCol => "count",
1000        other => agg_fn(other),
1001    }
1002}
1003
1004/// The reducer an aggregate is, as the query writes it.
1005fn agg_fn(a: &Agg) -> &'static str {
1006    match a {
1007        Agg::Count => "count",
1008        Agg::CountCol => "count(--values)",
1009        Agg::Sum => "sum",
1010        Agg::Avg => "mean",
1011        Agg::Min => "min",
1012        Agg::Max => "max",
1013    }
1014}
1015
1016/// Translate one SQL `SELECT` statement to a Quarb query.
1017pub fn translate(sql: &str) -> Result<Translation, SqlError> {
1018    let toks = lex(sql.trim().trim_end_matches(';'))?;
1019    // A UNION outside every parenthesis joins whole SELECTs.
1020    let mut depth = 0usize;
1021    let mut cuts = Vec::new();
1022    for (i, t) in toks.iter().enumerate() {
1023        match t {
1024            Tok::Sym('(') => depth += 1,
1025            Tok::Sym(')') => depth = depth.saturating_sub(1),
1026            Tok::Word(w) if depth == 0 && w.eq_ignore_ascii_case("UNION") => cuts.push(i),
1027            _ => {}
1028        }
1029    }
1030    if !cuts.is_empty() {
1031        return translate_union(&toks, &cuts);
1032    }
1033    translate_select(toks)
1034}
1035
1036/// `SELECT col FROM t [WHERE …] UNION [ALL] SELECT col FROM u …`,
1037/// with an ORDER BY and a LIMIT of the whole after the last: a
1038/// branch union of the columns, `/t/*[…]::col || /u/*[…]::col`.
1039///
1040/// UNION removes duplicate values, and `@| unique` after the union
1041/// does. UNION ALL keeps every row, and the branch union keeps one
1042/// thread for a node two branches both reach: over two different
1043/// tables no node is shared and the translation is exact; over one
1044/// table twice a row both SELECTs take would answer once where SQL
1045/// answers twice, so that form is refused.
1046fn translate_union(toks: &[Tok], cuts: &[usize]) -> Result<Translation, SqlError> {
1047    let mut notes = Vec::new();
1048    let mut all = None;
1049    let mut parts: Vec<&[Tok]> = Vec::new();
1050    let mut from = 0;
1051    for &cut in cuts {
1052        parts.push(&toks[from..cut]);
1053        let is_all =
1054            matches!(toks.get(cut + 1), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("ALL"));
1055        if all.is_some_and(|a| a != is_all) {
1056            return Err(SqlError::NotTranslated(
1057                d::UNION_NOT_TRANSLATED,
1058                "UNION and UNION ALL in one statement".into(),
1059            ));
1060        }
1061        all = Some(is_all);
1062        from = cut + 1 + usize::from(is_all);
1063    }
1064    parts.push(&toks[from..]);
1065    let all = all.unwrap_or(false);
1066
1067    let mut branches = Vec::new();
1068    let mut tables: Vec<String> = Vec::new();
1069    let mut first_name = String::new();
1070    let mut tail = String::new();
1071    let last = parts.len() - 1;
1072    for (i, part) in parts.iter().enumerate() {
1073        let mut p = Parser {
1074            toks: part.to_vec(),
1075            pos: 0,
1076        };
1077        let shape = || {
1078            SqlError::NotTranslated(
1079                d::UNION_NOT_TRANSLATED,
1080                "a UNION of anything but single columns ('SELECT col FROM t [WHERE …]' on \
1081                 each side)"
1082                    .into(),
1083            )
1084        };
1085        p.expect_kw("SELECT").map_err(|_| shape())?;
1086        if p.kw("DISTINCT") || p.sym('*') {
1087            return Err(shape());
1088        }
1089        if matches!(p.peek(), Some(Tok::Word(w)) if agg_kw(w).is_some())
1090            && matches!(p.toks.get(p.pos + 1), Some(Tok::Sym('(')))
1091        {
1092            return Err(shape());
1093        }
1094        let col = p.col_ref()?;
1095        let alias = p.kw("AS").then(|| p.ident()).transpose()?;
1096        if p.sym(',') {
1097            return Err(shape());
1098        }
1099        p.expect_kw("FROM")?;
1100        let table = p.ident()?;
1101        let table_alias = if p.kw("AS") {
1102            Some(p.ident()?)
1103        } else {
1104            match p.peek() {
1105                Some(Tok::Word(w))
1106                    if !["WHERE", "ORDER", "LIMIT"].contains(&w.to_ascii_uppercase().as_str()) =>
1107                {
1108                    Some(p.ident()?)
1109                }
1110                _ => None,
1111            }
1112        };
1113        let scope = Scope {
1114            from: (table.clone(), table_alias),
1115            join: None,
1116            on_clause: false,
1117        };
1118        let cond = p.kw("WHERE").then(|| p.cond()).transpose()?;
1119        if i == 0 {
1120            first_name = alias.unwrap_or_else(|| col.column.clone());
1121        }
1122        if i == last {
1123            // the whole union's order and limit
1124            if p.kw("ORDER") {
1125                p.expect_kw("BY")?;
1126                let named = match p.peek().cloned() {
1127                    Some(Tok::Num(n)) => {
1128                        p.pos += 1;
1129                        n == "1"
1130                    }
1131                    _ => p.col_ref()?.column.eq_ignore_ascii_case(&first_name),
1132                };
1133                if !named {
1134                    return Err(SqlError::NotTranslated(
1135                        d::UNION_NOT_TRANSLATED,
1136                        format!(
1137                            "ORDER BY of a UNION by anything but its column ('{first_name}', or 1)"
1138                        ),
1139                    ));
1140                }
1141                let desc = p.kw("DESC");
1142                if !desc {
1143                    p.kw("ASC");
1144                }
1145                tail.push_str(" @| sort");
1146                if desc {
1147                    tail.push_str(" @| reverse");
1148                }
1149            }
1150            if p.kw("LIMIT") {
1151                match p.peek().cloned() {
1152                    Some(Tok::Num(n)) => {
1153                        p.pos += 1;
1154                        write!(tail, " @| [..{n}]").unwrap();
1155                    }
1156                    _ => return Err(SqlError::Syntax("LIMIT takes a number".into())),
1157                }
1158            }
1159        }
1160        if p.peek().is_some() {
1161            return Err(shape());
1162        }
1163        if all && tables.iter().any(|t| t.eq_ignore_ascii_case(&table)) {
1164            return Err(SqlError::NotTranslated(
1165                d::UNION_NOT_TRANSLATED,
1166                format!(
1167                    "UNION ALL over the table '{table}' twice (a row both SELECTs take would \
1168                 answer once: a branch union keeps one thread for a node)"
1169                ),
1170            ));
1171        }
1172        tables.push(table.clone());
1173        let mut branch = format!("/{}/*", quarb_key(&table)?);
1174        if let Some(c) = &cond {
1175            write!(branch, "[{}]", emit_cond(c, true, &scope, &mut notes)?).unwrap();
1176        }
1177        write!(branch, "{}", scope.operand(&col)?).unwrap();
1178        branches.push(branch);
1179    }
1180    let mut q = branches.join(" || ");
1181    if !all {
1182        q.push_str(" @| unique");
1183    }
1184    q.push_str(&tail);
1185    Ok(Translation { query: q, notes })
1186}
1187
1188/// One `SELECT`, its tokens lexed.
1189fn translate_select(toks: Vec<Tok>) -> Result<Translation, SqlError> {
1190    let mut p = Parser { toks, pos: 0 };
1191    let mut notes = Vec::new();
1192
1193    p.expect_kw("SELECT").map_err(|_| {
1194        SqlError::NotTranslated(
1195            d::STATEMENT_NOT_TRANSLATED,
1196            "only SELECT statements translate".into(),
1197        )
1198    })?;
1199    let distinct = p.kw("DISTINCT");
1200
1201    // The select list.
1202    let mut items = Vec::new();
1203    loop {
1204        if p.sym('*') {
1205            items.push(SelectItem::Star);
1206        } else if let Some(Tok::Word(w)) = p.peek().cloned() {
1207            if let Some(a) = agg_kw(&w)
1208                && matches!(p.toks.get(p.pos + 1), Some(Tok::Sym('(')))
1209            {
1210                p.pos += 1; // the name
1211                let (a, col) = p.agg_call(a)?;
1212                let alias = p.kw("AS").then(|| p.ident()).transpose()?;
1213                items.push(SelectItem::Agg(a, col, alias));
1214            } else {
1215                let col = p.col_ref()?;
1216                let alias = p.kw("AS").then(|| p.ident()).transpose()?;
1217                items.push(SelectItem::Col(col, alias));
1218            }
1219        } else {
1220            return Err(SqlError::Syntax("expected a select item".into()));
1221        }
1222        if !p.sym(',') {
1223            break;
1224        }
1225    }
1226
1227    p.expect_kw("FROM")?;
1228    let from_table = p.ident()?;
1229    // Keywords that end the FROM clause and so cannot be a bare
1230    // table alias.
1231    const CLAUSE_KEYWORDS: &[&str] = &[
1232        "JOIN", "INNER", "LEFT", "RIGHT", "FULL", "CROSS", "OUTER", "ON", "WHERE", "GROUP",
1233        "ORDER", "LIMIT", "HAVING", "UNION",
1234    ];
1235    let from_alias = if p.kw("AS") {
1236        Some(p.ident()?)
1237    } else {
1238        match p.peek() {
1239            Some(Tok::Word(w)) if !CLAUSE_KEYWORDS.contains(&w.to_ascii_uppercase().as_str()) => {
1240                Some(p.ident()?)
1241            }
1242            _ => None,
1243        }
1244    };
1245
1246    // One optional JOIN. An inner join is every pair that satisfies
1247    // its ON (`<=>*`); LEFT keeps the FROM table's rows that have no
1248    // pair, the joined side null (`<=>*?`); RIGHT is LEFT with the
1249    // tables' places exchanged; CROSS is every pair. FULL has no
1250    // correlation that keeps the unmatched rows of both tables.
1251    if p.kw("FULL") {
1252        return Err(SqlError::NotTranslated(
1253            d::JOIN_NOT_TRANSLATED,
1254            "a FULL JOIN (no correlation keeps the unmatched rows of both tables)".into(),
1255        ));
1256    }
1257    let outer = if p.kw("LEFT") {
1258        Some(JoinKind::Left)
1259    } else if p.kw("RIGHT") {
1260        Some(JoinKind::Right)
1261    } else {
1262        None
1263    };
1264    if outer.is_some() {
1265        p.kw("OUTER");
1266    }
1267    let cross = outer.is_none() && p.kw("CROSS");
1268    let mut join = None;
1269    let mut join_on = None;
1270    let mut kind = JoinKind::Inner;
1271    if outer.is_some()
1272        || cross
1273        || p.kw("INNER")
1274        || matches!(p.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("JOIN"))
1275    {
1276        p.expect_kw("JOIN")?;
1277        let t = p.ident()?;
1278        let alias = if p.kw("AS") {
1279            Some(p.ident()?)
1280        } else {
1281            match p.peek() {
1282                Some(Tok::Word(w))
1283                    if !CLAUSE_KEYWORDS.contains(&w.to_ascii_uppercase().as_str()) =>
1284                {
1285                    Some(p.ident()?)
1286                }
1287                _ => None,
1288            }
1289        };
1290        if cross {
1291            kind = JoinKind::Cross;
1292            if matches!(p.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("ON")) {
1293                return Err(SqlError::NotTranslated(
1294                    d::JOIN_NOT_TRANSLATED,
1295                    "CROSS JOIN with an ON clause (a join with a condition is JOIN … ON)".into(),
1296                ));
1297            }
1298        } else {
1299            kind = outer.unwrap_or(JoinKind::Inner);
1300            p.expect_kw("ON")?;
1301            join_on = Some(p.cond()?);
1302        }
1303        join = Some((t, alias));
1304        if matches!(p.peek(), Some(Tok::Word(w))
1305            if ["JOIN", "INNER", "LEFT", "RIGHT", "FULL", "CROSS"]
1306                .contains(&w.to_ascii_uppercase().as_str()))
1307        {
1308            return Err(SqlError::NotTranslated(
1309                d::JOIN_NOT_TRANSLATED,
1310                "more than one JOIN (chain resolutions with '-->' instead)".into(),
1311            ));
1312        }
1313    }
1314    // RIGHT JOIN: the joined table drives, and the FROM table is the
1315    // side that may be missing.
1316    let (from_table, from_alias, join) = match (kind, join) {
1317        (JoinKind::Right, Some((t, alias))) => {
1318            kind = JoinKind::Left;
1319            (t, alias, Some((from_table, from_alias)))
1320        }
1321        (_, join) => (from_table, from_alias, join),
1322    };
1323
1324    let scope = Scope {
1325        from: (from_table.clone(), from_alias),
1326        join: join.clone(),
1327        on_clause: false,
1328    };
1329
1330    let where_cond = p.kw("WHERE").then(|| p.cond()).transpose()?;
1331    let group_by = p
1332        .kw("GROUP")
1333        .then(|| {
1334            p.expect_kw("BY")?;
1335            p.col_ref()
1336        })
1337        .transpose()?;
1338    let having = p.kw("HAVING").then(|| p.cond()).transpose()?;
1339    let order_by = p
1340        .kw("ORDER")
1341        .then(|| -> Result<(ColRef, bool), SqlError> {
1342            p.expect_kw("BY")?;
1343            let c = p.col_ref()?;
1344            let desc = p.kw("DESC");
1345            if !desc {
1346                p.kw("ASC");
1347            }
1348            Ok((c, desc))
1349        })
1350        .transpose()?;
1351    let limit = p
1352        .kw("LIMIT")
1353        .then(|| match p.peek().cloned() {
1354            Some(Tok::Num(n)) => {
1355                p.pos += 1;
1356                Ok(n)
1357            }
1358            _ => Err(SqlError::Syntax("LIMIT takes a number".into())),
1359        })
1360        .transpose()?;
1361    if let Some(t) = p.peek() {
1362        return Err(SqlError::NotTranslated(
1363            d::CONSTRUCT_NOT_TRANSLATED,
1364            format!("trailing SQL after the query ({t:?})"),
1365        ));
1366    }
1367    if order_by.is_some() {
1368        notes.push(
1369            "ORDER BY: a NULL key sorts last, first under DESC (as PostgreSQL orders it; \
1370             SQLite and MySQL put it first)"
1371                .to_string(),
1372        );
1373    }
1374    if group_by.is_none() && having.is_some() {
1375        return Err(SqlError::NotTranslated(
1376            d::HAVING_NOT_TRANSLATED,
1377            "HAVING without GROUP BY (a whole-table group)".into(),
1378        ));
1379    }
1380
1381    // ---- emit ----
1382    let mut q = String::new();
1383    if let Some((jt, _)) = &join {
1384        // `SELECT *` over a join is the columns of both tables; the
1385        // row nodes would be the driver's alone.
1386        if items.iter().any(|i| matches!(i, SelectItem::Star)) {
1387            return Err(SqlError::NotTranslated(
1388                d::JOIN_NOT_TRANSLATED,
1389                "SELECT * over a JOIN (name the columns: a row node is one table's row)".into(),
1390            ));
1391        }
1392        // The driver is the correlation context; the joined table
1393        // the result context, its ON in the bracket, where the
1394        // driver is `$$0`. Every pair is a thread (`<=>*`), as every
1395        // pair is a row; `<=>*?` keeps a driver with no pair.
1396        let arrow = if kind == JoinKind::Left {
1397            "<=>*?"
1398        } else {
1399            "<=>*"
1400        };
1401        write!(
1402            q,
1403            "/{}/* {arrow} /{}/*",
1404            quarb_key(&from_table)?,
1405            quarb_key(jt)?
1406        )
1407        .unwrap();
1408        let mut inside: Vec<String> = Vec::new();
1409        if let Some(on) = &join_on {
1410            inside.push(emit_cond(on, true, &scope.on(), &mut notes)?);
1411        }
1412        // WHERE reads the joined rows. For an inner join that is the
1413        // ON's own filter, and it rides the bracket (where a source
1414        // takes the whole as one JOIN); after an outer join it must
1415        // see the rows the join kept with no pair, and a test of the
1416        // driver's column for NULL cannot stand in a bracket: there
1417        // it follows the join as a filter.
1418        let after = where_cond
1419            .as_ref()
1420            .filter(|w| kind == JoinKind::Left || scope.tests_driver_null(w));
1421        if after.is_none()
1422            && let Some(w) = &where_cond
1423        {
1424            inside.push(emit_cond(w, true, &scope.on(), &mut notes)?);
1425        }
1426        if !inside.is_empty() {
1427            write!(q, "[{}]", inside.join(" && ")).unwrap();
1428        }
1429        if let Some(w) = after {
1430            write!(q, " | [{}]", emit_cond(w, true, &scope, &mut notes)?).unwrap();
1431        }
1432    } else {
1433        write!(q, "/{}/*", quarb_key(&from_table)?).unwrap();
1434        if let Some(w) = &where_cond {
1435            write!(q, "[{}]", emit_cond(w, true, &scope, &mut notes)?).unwrap();
1436        }
1437    }
1438
1439    // GROUP BY: the aggregate rides the plain pipe.
1440    if let Some(k) = &group_by {
1441        if distinct {
1442            return Err(SqlError::NotTranslated(
1443                d::DISTINCT_NOT_TRANSLATED,
1444                "SELECT DISTINCT with GROUP BY".into(),
1445            ));
1446        }
1447        let aggs: Vec<&SelectItem> = items
1448            .iter()
1449            .filter(|i| matches!(i, SelectItem::Agg(..)))
1450            .collect();
1451        if aggs.len() != 1 {
1452            return Err(SqlError::NotTranslated(
1453                d::GROUP_NOT_TRANSLATED,
1454                "GROUP BY translates with exactly one aggregate in the select list".into(),
1455            ));
1456        }
1457        let SelectItem::Agg(a, col, alias) = aggs[0] else {
1458            unreachable!()
1459        };
1460        // Any plain select item must be the group key — anything
1461        // else would silently vanish from the translation.
1462        let mut key_alias = None;
1463        for item in &items {
1464            match item {
1465                SelectItem::Col(c, ka) if c.column.eq_ignore_ascii_case(&k.column) => {
1466                    key_alias = ka.clone();
1467                }
1468                SelectItem::Col(c, _) => {
1469                    return Err(SqlError::NotTranslated(
1470                        d::GROUP_NOT_TRANSLATED,
1471                        format!(
1472                            "the non-aggregate column '{}' is not the GROUP BY key",
1473                            c.column
1474                        ),
1475                    ));
1476                }
1477                SelectItem::Star => {
1478                    return Err(SqlError::NotTranslated(
1479                        d::GROUP_NOT_TRANSLATED,
1480                        "SELECT * with GROUP BY".into(),
1481                    ));
1482                }
1483                SelectItem::Agg(..) => {}
1484            }
1485        }
1486        // The key is pushed under its name (the alias, else the
1487        // column) and the reduction folds by it: `| .k(::k) @|{.k}
1488        // sum`. SQL's NULL-key group is the fold's null partition.
1489        let key_name = key_alias.clone().unwrap_or_else(|| k.column.clone());
1490        if !plain_register(&key_name) {
1491            return Err(SqlError::NotTranslated(
1492                d::NAME_NOT_TRANSLATED,
1493                format!("the GROUP BY key {key_name:?} (not a plain register name)"),
1494            ));
1495        }
1496        write!(q, " | .{key_name}({})", scope.operand(k)?).unwrap();
1497        // The column an aggregate reads is piped to it; COUNT(col)
1498        // counts its values other than NULL, `count(--values)`.
1499        if let Some(c) = col {
1500            write!(q, " | {}", scope.operand(c)?).unwrap();
1501        }
1502        let name = alias.clone().unwrap_or_else(|| agg_word(a).to_string());
1503        if !plain_register(&name) {
1504            return Err(SqlError::NotTranslated(
1505                d::NAME_NOT_TRANSLATED,
1506                format!("the aggregate alias {name:?} (not a plain register name)"),
1507            ));
1508        }
1509        write!(q, " @|{{.{key_name}}} {} | .{name}", agg_fn(a)).unwrap();
1510        if let Some(h) = &having {
1511            // HAVING refers to the aggregate (an aggregate call,
1512            // its alias, or its function name) or the group key.
1513            let key_field = key_alias.as_deref().unwrap_or(&k.column);
1514            let cond = emit_having(h, a, col.as_ref(), &name, &k.column, key_field)?;
1515            write!(q, " | [{cond}]").unwrap();
1516        }
1517        write!(q, " | %.").unwrap();
1518        // ORDER BY / LIMIT after the grouped form: the sort key is
1519        // a field of the group record, the key or the aggregate.
1520        if let Some((c, desc)) = &order_by {
1521            let field = if c.column.eq_ignore_ascii_case(&k.column) {
1522                key_name.clone()
1523            } else if c.column.eq_ignore_ascii_case(&name) {
1524                name.clone()
1525            } else {
1526                return Err(SqlError::NotTranslated(
1527                    d::SORT_NOT_TRANSLATED,
1528                    format!(
1529                        "ORDER BY '{}': neither the GROUP BY key nor the aggregate",
1530                        c.column
1531                    ),
1532                ));
1533            };
1534            write!(q, " @| sort_by(:{field})").unwrap();
1535            if *desc {
1536                q.push_str(" @| reverse");
1537            }
1538        }
1539        if let Some(n) = &limit {
1540            write!(q, " @| [..{n}]").unwrap();
1541        }
1542        return Ok(Translation { query: q, notes });
1543    } else if items.iter().any(|i| matches!(i, SelectItem::Agg(..))) {
1544        // Bare aggregates over the whole table.
1545        if items.len() != 1 {
1546            return Err(SqlError::NotTranslated(
1547                d::GROUP_NOT_TRANSLATED,
1548                "mixing aggregates and columns without GROUP BY".into(),
1549            ));
1550        }
1551        if distinct {
1552            return Err(SqlError::NotTranslated(
1553                d::DISTINCT_NOT_TRANSLATED,
1554                "SELECT DISTINCT with an aggregate".into(),
1555            ));
1556        }
1557        let SelectItem::Agg(a, col, _) = &items[0] else {
1558            unreachable!()
1559        };
1560        // The column an aggregate reads is piped to it; COUNT(col)
1561        // counts its values other than NULL, `count(--values)`.
1562        if let Some(c) = col {
1563            write!(q, " | {}", scope.operand(c)?).unwrap();
1564        }
1565        write!(q, " @| {}", agg_fn(a)).unwrap();
1566    } else {
1567        // Plain column selection: sort, then DISTINCT's dedup
1568        // (stable, so the sorted order survives), then LIMIT —
1569        // SQL applies DISTINCT before ORDER BY and LIMIT.
1570        if let Some((c, desc)) = &order_by {
1571            write!(q, " @| sort_by({})", scope.operand(c)?).unwrap();
1572            if *desc {
1573                q.push_str(" @| reverse");
1574            }
1575        }
1576        if distinct {
1577            match items.as_slice() {
1578                [SelectItem::Star] => {
1579                    return Err(SqlError::NotTranslated(
1580                        d::DISTINCT_NOT_TRANSLATED,
1581                        "SELECT DISTINCT *".into(),
1582                    ));
1583                }
1584                [SelectItem::Col(c, _)] => {
1585                    write!(q, " | {} @| unique", scope.operand(c)?).unwrap();
1586                }
1587                // several columns: the rows as records, of which
1588                // `unique` keeps the first of each (two NULLs are
1589                // one value there, as they are under DISTINCT)
1590                _ => {
1591                    let fields = record_fields(&items, &scope)?;
1592                    write!(q, " | %({}) @| unique", fields.join("; ")).unwrap();
1593                    notes.push("the result streams as records (JSONL), not a table".to_string());
1594                }
1595            }
1596            if let Some(n) = &limit {
1597                write!(q, " @| [..{n}]").unwrap();
1598            }
1599            return Ok(Translation { query: q, notes });
1600        }
1601        if let Some(n) = &limit {
1602            write!(q, " @| [..{n}]").unwrap();
1603        }
1604        if items.len() == 1 && matches!(items[0], SelectItem::Star) {
1605            // row nodes as-is
1606            notes.push("SELECT *: the result is the row nodes (their locators print)".to_string());
1607        } else {
1608            let fields = record_fields(&items, &scope)?;
1609            write!(q, " | %({})", fields.join("; ")).unwrap();
1610            notes.push("the result streams as records (JSONL), not a table".to_string());
1611        }
1612        return Ok(Translation { query: q, notes });
1613    }
1614
1615    // ORDER BY / LIMIT after the bare aggregate form.
1616    if let Some((c, desc)) = &order_by {
1617        write!(q, " @| sort_by(::{})", quarb_key(&c.column)?).unwrap();
1618        if *desc {
1619            q.push_str(" @| reverse");
1620        }
1621    }
1622    if let Some(n) = &limit {
1623        write!(q, " @| [..{n}]").unwrap();
1624    }
1625    Ok(Translation { query: q, notes })
1626}
1627
1628/// The fields of the record a select list of columns projects: a
1629/// column under its own name, an aliased one under its alias, and a
1630/// joined table's column under its SQL qualifier, so that the two
1631/// sides of a join keep distinct keys.
1632fn record_fields(items: &[SelectItem], scope: &Scope) -> Result<Vec<String>, SqlError> {
1633    let mut fields = Vec::new();
1634    for item in items {
1635        match item {
1636            SelectItem::Star => {
1637                return Err(SqlError::NotTranslated(
1638                    d::CONSTRUCT_NOT_TRANSLATED,
1639                    "mixing * with named columns".into(),
1640                ));
1641            }
1642            SelectItem::Col(c, alias) => {
1643                let op = scope.operand(c)?;
1644                match alias {
1645                    Some(a) => fields.push(format!("{} = {op}", quarb_str(a))),
1646                    None if op.starts_with("$$")
1647                        && op[2..].starts_with(|c: char| c.is_ascii_digit()) =>
1648                    {
1649                        let name = match &c.table {
1650                            Some(t) => format!("{t}.{}", c.column),
1651                            None => c.column.clone(),
1652                        };
1653                        fields.push(format!("{} = {op}", quarb_str(&name)));
1654                    }
1655                    None => fields.push(op),
1656                }
1657            }
1658            SelectItem::Agg(..) => {
1659                return Err(SqlError::NotTranslated(
1660                    d::GROUP_NOT_TRANSLATED,
1661                    "an aggregate beside plain columns in this position".into(),
1662                ));
1663            }
1664        }
1665    }
1666    Ok(fields)
1667}
1668
1669/// A name usable as a bare Quarb register (`.name` / `$.name`).
1670fn plain_register(name: &str) -> bool {
1671    !name.is_empty()
1672        && name
1673            .chars()
1674            .next()
1675            .is_some_and(|c| c.is_alphabetic() || c == '_')
1676        && name.chars().all(|c| c.is_alphanumeric() || c == '_')
1677}
1678
1679/// A HAVING condition: a single comparison whose left side names
1680/// the (single) aggregate — an aggregate call matching the select
1681/// list's, its alias, or its function name (it is the topic's
1682/// pushed register, `$_`) — or the group key (`$.key`).
1683fn emit_having(
1684    c: &Cond,
1685    agg: &Agg,
1686    agg_col: Option<&ColRef>,
1687    agg_name: &str,
1688    key: &str,
1689    key_field: &str,
1690) -> Result<String, SqlError> {
1691    let rhs_text = |rhs: &Scalar| -> Result<String, SqlError> {
1692        match rhs {
1693            Scalar::Col(_) => Err(SqlError::NotTranslated(
1694                d::HAVING_NOT_TRANSLATED,
1695                "HAVING compares against a literal".into(),
1696            )),
1697            Scalar::Str(v) => Ok(quarb_str(v)),
1698            Scalar::Num(n) => Ok(n.clone()),
1699            Scalar::Null => Ok("null".to_string()),
1700        }
1701    };
1702    match c {
1703        Cond::AggCmp(a, col, op, rhs) => {
1704            let same_col = match (col, agg_col) {
1705                (None, None) => true,
1706                (Some(x), Some(y)) => x.column.eq_ignore_ascii_case(&y.column),
1707                _ => false,
1708            };
1709            if a != agg || !same_col {
1710                return Err(SqlError::NotTranslated(
1711                    d::HAVING_NOT_TRANSLATED,
1712                    "HAVING refers to an aggregate not in the select list".into(),
1713                ));
1714            }
1715            Ok(format!("$_ {op} {}", rhs_text(rhs)?))
1716        }
1717        Cond::Cmp(col, op, rhs) => {
1718            let lhs = if col.column.eq_ignore_ascii_case(agg_name) {
1719                "$_".to_string()
1720            } else if col.column.eq_ignore_ascii_case(key) {
1721                if !plain_register(key_field) {
1722                    return Err(SqlError::NotTranslated(
1723                        d::NAME_NOT_TRANSLATED,
1724                        format!(
1725                            "the group key {key_field:?} in HAVING (not a plain register name)"
1726                        ),
1727                    ));
1728                }
1729                format!("$.{key_field}")
1730            } else {
1731                return Err(SqlError::NotTranslated(
1732                    d::HAVING_NOT_TRANSLATED,
1733                    format!(
1734                        "the HAVING column '{}' (name the aggregate or the group key)",
1735                        col.column
1736                    ),
1737                ));
1738            };
1739            Ok(format!("{lhs} {op} {}", rhs_text(rhs)?))
1740        }
1741        _ => Err(SqlError::NotTranslated(
1742            d::HAVING_NOT_TRANSLATED,
1743            "HAVING translates for a single comparison".into(),
1744        )),
1745    }
1746}