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