#!/usr/bin/env python3
"""
minisql.py -- a from-scratch SQL SELECT engine. Stdlib only, no third-party imports.

Wizard: null (lane: Codeforge -- hard coding and agentic reasoning).

Scope: exactly the grammar the differential harness `diff_sqlite.py` generates, and
nothing else. Everything outside it raises SqlError.

    SELECT [DISTINCT] <items> FROM <table> [[AS] alias]
      [[INNER|LEFT [OUTER]] JOIN <table> [[AS] alias] ON <expr>]*
      [WHERE <expr>]
      [GROUP BY <expr>, ...]
      [HAVING <expr>]
      [ORDER BY <expr> [ASC|DESC], ...]
      [LIMIT <n> [OFFSET <m>]]

  items : * | alias.* | <expr> [[AS] alias]
  expr  : literals (int, real, 'text', NULL, TRUE, FALSE)
        | column refs (name | alias.name)
        | unary - + NOT ; binary + - * /
        | = <> != < <= > >=   (three-valued)
        | IS [NOT] NULL | [NOT] IN (list) | [NOT] BETWEEN a AND b | [NOT] LIKE 'pat'
        | AND OR | ( expr )
        | CASE WHEN c THEN e [...] [ELSE e] END      (searched CASE only)
        | COUNT(*) COUNT(x) SUM(x) AVG(x) MIN(x) MAX(x)

Semantics implemented deliberately to match SQLite 3.x:
  * NULL propagation, three-valued AND/OR/NOT; WHERE keeps rows whose value is true.
  * storage-class ordering NULL < INTEGER/REAL < TEXT, and the affinity rule: if one
    operand has INTEGER/REAL/NUMERIC affinity and the other has TEXT/BLOB/no affinity,
    numeric affinity is applied to the other operand.
  * integer division truncates toward zero and stays INTEGER; division by zero -> NULL.
  * SUM of no non-NULL values -> NULL (not 0); COUNT(x) ignores NULLs; AVG -> REAL.
  * LIKE is case-insensitive for ASCII only, `%` = any run, `_` = one char.
  * ASC sorts NULLs first, DESC last; comparison is by storage class then value.

The module is written so each semantic decision above lives in its own named function
(compare_values, sort_key, arith_div, agg_sum, agg_count, distinct_key, join_relation,
tri/truthy), because diff_sqlite.py mutates them one at a time to prove its own teeth.
"""

from __future__ import annotations

import re
import sys
from dataclasses import dataclass, replace
from typing import Optional

__all__ = [
    "SqlError", "parse_query", "execute", "run", "Table",
    "compare_values", "sort_key", "arith_div", "agg_sum", "agg_count",
    "distinct_key", "tri", "truthy", "like_match",
]


class SqlError(Exception):
    """Raised for anything outside the supported subset."""


# --------------------------------------------------------------------------
# tokenizer
# --------------------------------------------------------------------------

_KEYWORDS = {
    "SELECT", "DISTINCT", "FROM", "JOIN", "INNER", "LEFT", "OUTER", "ON", "WHERE",
    "GROUP", "BY", "HAVING", "ORDER", "ASC", "DESC", "LIMIT", "OFFSET", "AS",
    "AND", "OR", "NOT", "IS", "NULL", "IN", "BETWEEN", "LIKE", "CASE", "WHEN",
    "THEN", "ELSE", "END", "TRUE", "FALSE",
}
_AGGS = {"COUNT", "SUM", "AVG", "MIN", "MAX"}

_TOKEN_RE = re.compile(
    r"""
      (?P<ws>\s+)
    | (?P<comment>--[^\n]*)
    | (?P<str>'(?:[^']|'')*')
    | (?P<qident>"(?:[^"]|"")*")
    | (?P<num>\d+\.\d*(?:[eE][-+]?\d+)?|\.\d+(?:[eE][-+]?\d+)?|\d+(?:[eE][-+]?\d+)?)
    | (?P<ident>[A-Za-z_][A-Za-z_0-9]*)
    | (?P<op><=|>=|<>|!=|\|\||[-+*/%(),.=<>;])
    """,
    re.VERBOSE,
)


@dataclass
class _Tok:
    kind: str          # 'kw' | 'ident' | 'num' | 'str' | 'op' | 'end'
    text: str          # canonical text (keywords uppercased, idents lowercased)
    value: object = None


def tokenize(sql: str) -> list:
    toks, i, n = [], 0, len(sql)
    while i < n:
        m = _TOKEN_RE.match(sql, i)
        if not m:
            raise SqlError("cannot tokenize at offset %d: %r" % (i, sql[i:i + 12]))
        i = m.end()
        kind = m.lastgroup
        text = m.group()
        if kind in ("ws", "comment"):
            continue
        if kind == "str":
            toks.append(_Tok("str", text, text[1:-1].replace("''", "'")))
        elif kind == "qident":
            toks.append(_Tok("ident", text[1:-1].replace('""', '"').lower()))
        elif kind == "num":
            if "." in text or "e" in text or "E" in text:
                toks.append(_Tok("num", text, float(text)))
            else:
                toks.append(_Tok("num", text, int(text)))
        elif kind == "ident":
            up = text.upper()
            if up in _KEYWORDS:
                toks.append(_Tok("kw", up))
            else:
                toks.append(_Tok("ident", text.lower()))
        else:
            toks.append(_Tok("op", text))
    toks.append(_Tok("end", ""))
    return toks


# --------------------------------------------------------------------------
# parser
# --------------------------------------------------------------------------
# AST nodes are plain tuples; the first element names the node.

class _Parser:
    def __init__(self, toks):
        self.t = toks
        self.i = 0

    # -- helpers ----------------------------------------------------------
    def peek(self, k=0):
        return self.t[min(self.i + k, len(self.t) - 1)]

    def next(self):
        tok = self.t[self.i]
        self.i += 1
        return tok

    def at_kw(self, *names):
        tok = self.peek()
        return tok.kind == "kw" and tok.text in names

    def at_op(self, *ops):
        tok = self.peek()
        return tok.kind == "op" and tok.text in ops

    def eat_kw(self, name):
        if not self.at_kw(name):
            raise SqlError("expected %s, got %r" % (name, self.peek().text))
        return self.next()

    def eat_op(self, op):
        if not self.at_op(op):
            raise SqlError("expected %r, got %r" % (op, self.peek().text))
        return self.next()

    def eat_ident(self):
        tok = self.peek()
        if tok.kind != "ident":
            raise SqlError("expected identifier, got %r" % tok.text)
        return self.next().text

    # -- statements -------------------------------------------------------
    def parse_query(self):
        self.eat_kw("SELECT")
        distinct = False
        if self.at_kw("DISTINCT"):
            self.next()
            distinct = True
        items = [self.parse_item()]
        while self.at_op(","):
            self.next()
            items.append(self.parse_item())
        if not self.at_kw("FROM"):
            # SELECT without FROM: one row, no columns. Constant-expression queries only.
            if self.peek().kind != "end":
                raise SqlError("a SELECT without FROM takes no clauses")
            return {
                "distinct": distinct, "items": items,
                "from": (None, None), "joins": [], "where": None, "group_by": [],
                "having": None, "order_by": [], "limit": None, "offset": None,
            }
        self.next()
        from_tbl, from_alias = self.parse_table_ref()
        joins = []
        while True:
            if self.at_kw("JOIN"):
                self.next()
                kind = "inner"
            elif self.at_kw("INNER"):
                self.next()
                self.eat_kw("JOIN")
                kind = "inner"
            elif self.at_kw("LEFT"):
                self.next()
                if self.at_kw("OUTER"):
                    self.next()
                self.eat_kw("JOIN")
                kind = "left"
            else:
                break
            tbl, alias = self.parse_table_ref()
            self.eat_kw("ON")
            on = self.parse_expr()
            joins.append((kind, tbl, alias, on))
        where = None
        if self.at_kw("WHERE"):
            self.next()
            where = self.parse_expr()
        group_by = []
        if self.at_kw("GROUP"):
            self.next()
            self.eat_kw("BY")
            group_by = [self.parse_expr()]
            while self.at_op(","):
                self.next()
                group_by.append(self.parse_expr())
        having = None
        if self.at_kw("HAVING"):
            self.next()
            having = self.parse_expr()
        order_by = []
        if self.at_kw("ORDER"):
            self.next()
            self.eat_kw("BY")
            while True:
                e = self.parse_expr()
                desc = False
                if self.at_kw("ASC"):
                    self.next()
                elif self.at_kw("DESC"):
                    self.next()
                    desc = True
                order_by.append((e, desc))
                if self.at_op(","):
                    self.next()
                    continue
                break
        limit = offset = None
        if self.at_kw("LIMIT"):
            self.next()
            limit = self.parse_signed_int()
            if self.at_kw("OFFSET"):
                self.next()
                offset = self.parse_signed_int()
        if self.peek().kind != "end":
            raise SqlError("trailing input: %r" % self.peek().text)
        return {
            "distinct": distinct, "items": items,
            "from": (from_tbl, from_alias), "joins": joins,
            "where": where, "group_by": group_by, "having": having,
            "order_by": order_by, "limit": limit, "offset": offset,
        }

    def parse_signed_int(self):
        neg = False
        if self.at_op("-"):
            self.next()
            neg = True
        tok = self.next()
        if tok.kind != "num" or not isinstance(tok.value, int):
            raise SqlError("expected integer, got %r" % tok.text)
        return -tok.value if neg else tok.value

    def parse_table_ref(self):
        name = self.eat_ident()
        alias = name
        if self.at_kw("AS"):
            self.next()
            alias = self.eat_ident()
        elif self.peek().kind == "ident":
            alias = self.eat_ident()
        return name, alias

    def parse_item(self):
        if self.at_op("*"):
            self.next()
            return ("star", None, None)
        if self.peek().kind == "ident" and self.peek(1).kind == "op" and self.peek(1).text == "." \
                and self.peek(2).kind == "op" and self.peek(2).text == "*":
            tbl = self.next().text
            self.next()
            self.next()
            return ("star", tbl, None)
        e = self.parse_expr()
        alias = None
        if self.at_kw("AS"):
            self.next()
            alias = self.eat_ident()
        elif self.peek().kind == "ident":
            alias = self.eat_ident()
        return ("item", e, alias)

    # -- expressions ------------------------------------------------------
    def parse_expr(self):
        return self.parse_or()

    def parse_or(self):
        left = self.parse_and()
        while self.at_kw("OR"):
            self.next()
            left = ("or", left, self.parse_and())
        return left

    def parse_and(self):
        left = self.parse_not()
        while self.at_kw("AND"):
            self.next()
            left = ("and", left, self.parse_not())
        return left

    def parse_not(self):
        if self.at_kw("NOT"):
            self.next()
            return ("not", self.parse_not())
        return self.parse_predicate()

    def parse_predicate(self):
        left = self.parse_additive()
        while True:
            if self.at_op("=", "<>", "!=", "<", "<=", ">", ">="):
                op = self.next().text
                right = self.parse_additive()
                left = ("cmp", op, left, right)
            elif self.at_kw("IS"):
                self.next()
                neg = False
                if self.at_kw("NOT"):
                    self.next()
                    neg = True
                self.eat_kw("NULL")
                left = ("isnull", left, neg)
            elif self.at_kw("IN") or (self.at_kw("NOT") and self.peek(1).kind == "kw"
                                      and self.peek(1).text == "IN"):
                neg = False
                if self.at_kw("NOT"):
                    self.next()
                    neg = True
                self.eat_kw("IN")
                self.eat_op("(")
                items = []
                if not self.at_op(")"):
                    items.append(self.parse_expr())
                    while self.at_op(","):
                        self.next()
                        items.append(self.parse_expr())
                self.eat_op(")")
                left = ("in", left, items, neg)
            elif self.at_kw("BETWEEN") or (self.at_kw("NOT") and self.peek(1).kind == "kw"
                                           and self.peek(1).text == "BETWEEN"):
                neg = False
                if self.at_kw("NOT"):
                    self.next()
                    neg = True
                self.eat_kw("BETWEEN")
                lo = self.parse_additive()
                self.eat_kw("AND")
                hi = self.parse_additive()
                left = ("between", left, lo, hi, neg)
            elif self.at_kw("LIKE") or (self.at_kw("NOT") and self.peek(1).kind == "kw"
                                        and self.peek(1).text == "LIKE"):
                neg = False
                if self.at_kw("NOT"):
                    self.next()
                    neg = True
                self.eat_kw("LIKE")
                left = ("like", left, self.parse_additive(), neg)
            else:
                return left

    def parse_additive(self):
        left = self.parse_multiplicative()
        while self.at_op("+", "-"):
            op = self.next().text
            left = ("binop", op, left, self.parse_multiplicative())
        return left

    def parse_multiplicative(self):
        left = self.parse_unary()
        while self.at_op("*", "/", "%"):
            op = self.next().text
            if op == "%":
                raise SqlError("`%` is out of scope")
            left = ("binop", op, left, self.parse_unary())
        return left

    def parse_unary(self):
        if self.at_op("-"):
            self.next()
            return ("unary", "-", self.parse_unary())
        if self.at_op("+"):
            self.next()
            return ("unary", "+", self.parse_unary())
        return self.parse_primary()

    def parse_primary(self):
        tok = self.peek()
        if tok.kind == "op" and tok.text == "(":
            self.next()
            e = self.parse_expr()
            self.eat_op(")")
            return e
        if tok.kind == "num":
            self.next()
            return ("lit", tok.value)
        if tok.kind == "str":
            self.next()
            return ("lit", tok.value)
        if tok.kind == "kw" and tok.text == "NULL":
            self.next()
            return ("lit", None)
        if tok.kind == "kw" and tok.text in ("TRUE", "FALSE"):
            self.next()
            return ("lit", 1 if tok.text == "TRUE" else 0)
        if tok.kind == "kw" and tok.text == "CASE":
            return self.parse_case()
        if tok.kind == "ident":
            if tok.text.upper() in _AGGS and self.peek(1).kind == "op" and self.peek(1).text == "(":
                return self.parse_aggregate()
            name = self.next().text
            if self.at_op("."):
                self.next()
                col = self.eat_ident()
                return ("col", name, col)
            return ("col", None, name)
        raise SqlError("unexpected token %r" % tok.text)

    def parse_aggregate(self):
        fname = self.next().text.upper()
        self.eat_op("(")
        if self.at_op("*"):
            self.next()
            self.eat_op(")")
            if fname != "COUNT":
                raise SqlError("%s(*) is not a function" % fname)
            return ("agg", "COUNT", None)
        arg = self.parse_expr()
        self.eat_op(")")
        return ("agg", fname, arg)

    def parse_case(self):
        self.eat_kw("CASE")
        if not self.at_kw("WHEN"):
            raise SqlError("only searched CASE is in scope")
        whens = []
        while self.at_kw("WHEN"):
            self.next()
            cond = self.parse_expr()
            self.eat_kw("THEN")
            val = self.parse_expr()
            whens.append((cond, val))
        els = None
        if self.at_kw("ELSE"):
            self.next()
            els = self.parse_expr()
        self.eat_kw("END")
        return ("case", whens, els)


def parse_query(sql: str) -> dict:
    return _Parser(tokenize(sql)).parse_query()


# --------------------------------------------------------------------------
# semantics -- each decision below is a separate function on purpose
# --------------------------------------------------------------------------

_NUM_AFF = {"INTEGER", "REAL", "NUMERIC"}


def class_rank(v):
    """SQLite storage-class order: NULL < numbers < text < blob."""
    if v is None:
        return 0
    if isinstance(v, (int, float)) and not isinstance(v, bool):
        return 1
    if isinstance(v, str):
        return 2
    raise SqlError("unsupported value type %r" % (type(v),))


_NUM_PREFIX_RE = re.compile(r"[ \t]*[+-]?(?:\d+\.\d*|\.\d+|\d+)(?:[eE][+-]?\d+)?")


def numeric_prefix(v):
    """SQLite's arithmetic coercion of text: the longest numeric *prefix*, else integer 0.

    Measured against sqlite3 3.53.1: `'5abc' + 0` -> 5 (integer), `'5.5' + 0` -> 5.5 (real),
    `'abc' + 0` -> 0 (integer), `'' + 0` -> 0, `' 5 ' + 0` -> 5. Note this is a *prefix*
    parse and is NOT the same rule as affinity conversion, which needs the whole string.
    """
    if isinstance(v, str):
        m = _NUM_PREFIX_RE.match(v)
        if not m:
            return 0
        text = m.group()
        if "." in text or "e" in text or "E" in text:
            return float(text)
        return int(text)
    return v


def apply_numeric_affinity(v):
    """SQLite numeric affinity: a text value that looks wholly numeric becomes a number."""
    if isinstance(v, str):
        s = v.strip()
        if not s:
            return v
        try:
            return int(s)
        except ValueError:
            pass
        try:
            return float(s)
        except ValueError:
            return v
    return v


def apply_text_affinity(v):
    """SQLite's TEXT affinity conversion: a number compared against a TEXT-affinity column
    becomes its text form. Measured: `s = 10` is TRUE for s='10' while `s = 10.0` is FALSE
    (the real converts to '10.0'), so a float must render with SQLite's own shortest form."""
    if v is None or isinstance(v, str):
        return v
    if isinstance(v, bool):
        return str(int(v))
    if isinstance(v, int):
        return str(v)
    if isinstance(v, float):
        if v == int(v) and abs(v) < 1e16:
            return "%.1f" % v
        return repr(v)
    raise SqlError("cannot apply TEXT affinity to %r" % (type(v),))


def compare_values(a, b, aff_a=None, aff_b=None):
    """-1/0/1, or None when either side is NULL. Applies SQLite's two affinity rules first:

      * one side INTEGER/REAL/NUMERIC affinity, the other TEXT/BLOB/none -> numeric affinity
        is applied to the other side;
      * one side TEXT affinity, the other none -> TEXT affinity is applied to the other side.
    """
    if a is None or b is None:
        return None
    if aff_a in _NUM_AFF and aff_b not in _NUM_AFF:
        b = apply_numeric_affinity(b)
    elif aff_b in _NUM_AFF and aff_a not in _NUM_AFF:
        a = apply_numeric_affinity(a)
    elif aff_a == "TEXT" and aff_b is None:
        b = apply_text_affinity(b)
    elif aff_b == "TEXT" and aff_a is None:
        a = apply_text_affinity(a)
    ra, rb = class_rank(a), class_rank(b)
    if ra != rb:
        return -1 if ra < rb else 1
    if a == b:
        return 0
    return -1 if a < b else 1


def sort_key(v):
    """Ordering key for ORDER BY / MIN / MAX: class rank then value (NULLs first ascending)."""
    r = class_rank(v)
    return (r, 0 if v is None else v)


def tri(v):
    """Truth value of an expression as 1/0/None (three-valued)."""
    if v is None:
        return None
    if isinstance(v, bool):
        return 1 if v else 0
    if isinstance(v, (int, float)):
        return 1 if v != 0 else 0
    if isinstance(v, str):
        n = apply_numeric_affinity(v)
        if isinstance(n, (int, float)) and not isinstance(n, bool):
            return 1 if n != 0 else 0
        return 0
    raise SqlError("cannot test truth of %r" % (type(v),))


def truthy(v):
    return tri(v) == 1


def arith_div(a, b):
    """SQLite `/`: integer when both are integers, truncating toward zero; x/0 -> NULL."""
    if a is None or b is None:
        return None
    a, b = numeric_prefix(a), numeric_prefix(b)
    if b == 0:
        return None
    if isinstance(a, int) and isinstance(b, int):
        q = abs(a) // abs(b)
        return -q if (a < 0) != (b < 0) else q
    return a / b


def arith(op, a, b):
    if a is None or b is None:
        return None
    a, b = numeric_prefix(a), numeric_prefix(b)
    if op == "/":
        return arith_div(a, b)
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    raise SqlError("unknown operator %r" % op)


def agg_numeric(v):
    """Aggregate coercion: numbers pass, text becomes numeric only if the WHOLE string is
    numeric; otherwise it counts as REAL 0.0. Measured: `SUM(s)` over {'10', NULL, 'abc'}
    is 10.0 REAL (so 'abc' contributed 0.0 and made the total real), not 10 INTEGER."""
    if isinstance(v, str):
        n = apply_numeric_affinity(v)
        return n if isinstance(n, (int, float)) else 0.0
    return v


def agg_count(values, n_rows):
    """COUNT(expr): number of non-NULL values."""
    return sum(1 for v in values if v is not None)


def agg_sum(values):
    """SUM: NULL when there is no non-NULL value; INTEGER when every value is an integer."""
    vals = [agg_numeric(v) for v in values if v is not None]
    if not vals:
        return None
    if all(isinstance(v, int) for v in vals):
        return sum(vals)
    return float(sum(vals))


def agg_avg(values):
    vals = [agg_numeric(v) for v in values if v is not None]
    if not vals:
        return None
    return float(sum(vals)) / len(vals)


def agg_minmax(values, want_max):
    vals = [v for v in values if v is not None]
    if not vals:
        return None
    best = vals[0]
    for v in vals[1:]:
        c = compare_values(v, best)
        if (c > 0) if want_max else (c < 0):
            best = v
    return best


_LIKE_CACHE = {}


def like_match(value, pattern):
    """SQLite LIKE: ASCII-case-insensitive, `%` = any run, `_` = exactly one character."""
    if value is None or pattern is None:
        return None
    if not isinstance(value, str):
        value = str(value)
    rx = _LIKE_CACHE.get(pattern)
    if rx is None:
        out = ["(?s)\\A"]
        for ch in pattern:
            if ch == "%":
                out.append(".*")
            elif ch == "_":
                out.append(".")
            else:
                out.append(re.escape(ch))
        out.append("\\Z")
        rx = re.compile("".join(out), re.IGNORECASE | re.ASCII)
        _LIKE_CACHE[pattern] = rx
    return 1 if rx.match(value) else 0


def distinct_key(row):
    """Equality for DISTINCT / GROUP BY: numbers unify (5 == 5.0), text and NULL by identity."""
    key = []
    for v in row:
        if v is None:
            key.append((0, None))
        elif isinstance(v, (int, float)) and not isinstance(v, bool):
            key.append((1, float(v)))
        elif isinstance(v, str):
            key.append((2, v))
        else:
            raise SqlError("unsupported value in DISTINCT: %r" % (type(v),))
    return tuple(key)


def join_relation(left, right, kind, on_eval):
    """Nested-loop join. `kind` is 'inner' or 'left'; unmatched left rows get NULL right side."""
    out = []
    n_right_cols = len(right.cols)
    for lrow in left.rows:
        matched = False
        for rrow in right.rows:
            combined = lrow + rrow
            if truthy(on_eval(combined)):
                matched = True
                out.append(combined)
        if kind == "left" and not matched:
            out.append(lrow + [None] * n_right_cols)
    return Relation(left.cols + right.cols, out)


# --------------------------------------------------------------------------
# relations / evaluation
# --------------------------------------------------------------------------

@dataclass
class Table:
    cols: list          # [(name, declared_type)]
    rows: list          # [[value, ...], ...]


@dataclass
class Relation:
    cols: list          # [(table_alias, column_name), ...]
    rows: list          # [] is used for the index-only scaffold built before a join
    index: Optional[dict] = None    # name -> [idx]; set by _build_index


@dataclass
class _Ctx:
    rel: Relation
    values: list
    group: Optional[list] = None    # list of value-lists when in an aggregate context
    index: Optional[dict] = None    # name -> [idx] built once per relation


def _build_index(rel):
    idx = {}
    for i, (tbl, col) in enumerate(rel.cols):
        idx.setdefault(col, []).append(i)
        idx.setdefault(tbl + "." + col, [i])
    return idx


def _resolve(ctx, tbl, col):
    key = col if tbl is None else tbl + "." + col
    hits = ctx.index.get(key)
    if not hits:
        raise SqlError("no such column: %s" % key)
    if len(hits) > 1:
        raise SqlError("ambiguous column: %s" % key)
    return hits[0]


def affinity_of(node):
    """Only a bare column reference carries affinity in this engine."""
    if node[0] == "col":
        return node[3] if len(node) > 3 else None
    return None


def has_aggregate(node):
    k = node[0]
    if k == "agg":
        return True
    for sub in node[1:]:
        if isinstance(sub, tuple) and sub and isinstance(sub[0], str):
            if has_aggregate(sub):
                return True
        elif isinstance(sub, list):
            for x in sub:
                if isinstance(x, tuple) and x and isinstance(x[0], str) and has_aggregate(x):
                    return True
                if isinstance(x, tuple) and x and isinstance(x[0], tuple):
                    for y in x:
                        if isinstance(y, tuple) and y and isinstance(y[0], str) and has_aggregate(y):
                            return True
    return False


def eval_expr(node, ctx):
    k = node[0]
    if k == "lit":
        return node[1]
    if k == "col":
        tbl, col = node[1], node[2]
        i = _resolve(ctx, tbl, col)
        return ctx.values[i]
    if k == "star":
        raise SqlError("* is only valid in the select list")
    if k == "unary":
        v = eval_expr(node[2], ctx)
        if v is None:
            return None
        if node[1] == "+":
            return v
        if isinstance(v, str):
            raise SqlError("unary - on text is out of scope")
        return -v
    if k == "binop":
        return arith(node[1], eval_expr(node[2], ctx), eval_expr(node[3], ctx))
    if k == "cmp":
        return _eval_cmp(node, ctx)
    if k == "isnull":
        v = eval_expr(node[1], ctx)
        return 1 if ((v is None) != bool(node[2])) else 0
    if k == "in":
        return _eval_in(node, ctx)
    if k == "between":
        lo = eval_expr(node[2], ctx)
        hi = eval_expr(node[3], ctx)
        aff = affinity_of(node[1])
        ge = _cmp_result(eval_expr(node[1], ctx), lo, aff, affinity_of(node[2]), ">=")
        le = _cmp_result(eval_expr(node[1], ctx), hi, aff, affinity_of(node[3]), "<=")
        r = _tri_and(ge, le)
        return _tri_not(r) if node[4] else r
    if k == "like":
        r = like_match(eval_expr(node[1], ctx), eval_expr(node[2], ctx))
        return _tri_not(r) if node[3] else r
    if k == "and":
        return _tri_and(eval_expr(node[1], ctx), eval_expr(node[2], ctx))
    if k == "or":
        return _tri_or(eval_expr(node[1], ctx), eval_expr(node[2], ctx))
    if k == "not":
        return _tri_not(eval_expr(node[1], ctx))
    if k == "case":
        for cond, val in node[1]:
            if truthy(eval_expr(cond, ctx)):
                return eval_expr(val, ctx)
        return None if node[2] is None else eval_expr(node[2], ctx)
    if k == "agg":
        return _eval_agg(node, ctx)
    raise SqlError("cannot evaluate node %r" % (k,))


def _cmp_result(a, b, aff_a, aff_b, op):
    c = compare_values(a, b, aff_a, aff_b)
    if c is None:
        return None
    if op == "=":
        return 1 if c == 0 else 0
    if op in ("<>", "!="):
        return 1 if c != 0 else 0
    if op == "<":
        return 1 if c < 0 else 0
    if op == "<=":
        return 1 if c <= 0 else 0
    if op == ">":
        return 1 if c > 0 else 0
    if op == ">=":
        return 1 if c >= 0 else 0
    raise SqlError("unknown comparison %r" % op)


def _eval_cmp(node, ctx):
    return _cmp_result(
        eval_expr(node[2], ctx), eval_expr(node[3], ctx),
        affinity_of(node[2]), affinity_of(node[3]), node[1],
    )


def _eval_in(node, ctx):
    """SQLite IN: a match is TRUE; otherwise NULL if any list element is NULL; else FALSE.
    `NOT IN` is the three-valued negation of that, so `3 NOT IN (1,2,NULL)` is NULL."""
    target = eval_expr(node[1], ctx)
    aff = affinity_of(node[1])
    saw_null = False
    for item in node[2]:
        v = eval_expr(item, ctx)
        c = compare_values(target, v, aff, affinity_of(item))
        if c is None:
            saw_null = True
        elif c == 0:
            return 0 if node[3] else 1
    r = None if saw_null else 0
    return _tri_not(r) if node[3] else r


def _tri_and(a, b):
    ta, tb = tri(a), tri(b)
    if ta == 0 or tb == 0:
        return 0
    if ta is None or tb is None:
        return None
    return 1


def _tri_or(a, b):
    ta, tb = tri(a), tri(b)
    if ta == 1 or tb == 1:
        return 1
    if ta is None or tb is None:
        return None
    return 0


def _tri_not(a):
    ta = tri(a)
    return None if ta is None else 1 - ta


def _eval_agg(node, ctx):
    fname, arg = node[1], node[2]
    if ctx.group is None:
        raise SqlError("aggregate %s outside an aggregate context" % fname)
    if fname == "COUNT" and arg is None:
        return len(ctx.group)
    values = []
    for rv in ctx.group:
        values.append(eval_expr(arg, replace(ctx, values=rv, group=None)))
    if fname == "COUNT":
        return agg_count(values, len(ctx.group))
    if fname == "SUM":
        return agg_sum(values)
    if fname == "AVG":
        return agg_avg(values)
    if fname == "MIN":
        return agg_minmax(values, False)
    if fname == "MAX":
        return agg_minmax(values, True)
    raise SqlError("unknown aggregate %s" % fname)


# --------------------------------------------------------------------------
# query execution
# --------------------------------------------------------------------------

def _build_from(q, tables):
    tname, alias = q["from"]
    if tname is None:
        return Relation([], [[]])          # SELECT without FROM: exactly one empty row
    if tname not in tables:
        raise SqlError("no such table: %s" % tname)
    decl = {c: ty for t in tables.values() for c, ty in t.cols}
    t = tables[tname]
    rel = Relation([(alias, c) for c, _ in t.cols], [list(r) for r in t.rows])
    rel.index = _build_index(rel)
    for kind, jtname, jalias, on in q["joins"]:
        if jtname not in tables:
            raise SqlError("no such table: %s" % jtname)
        jt = tables[jtname]
        right = Relation([(jalias, c) for c, _ in jt.cols], [list(r) for r in jt.rows])
        right.index = _build_index(right)
        combined_cols = rel.cols + right.cols
        combined_index = _build_index(Relation(combined_cols, []))
        # the ON clause gets the declared affinities too: `text_col <> 20` means `<> '20'`
        col_aff = {i: decl.get(c) for i, (_a, c) in enumerate(combined_cols)}

        def on_eval(combined, _on=on, _cols=combined_cols, _idx=combined_index, _aff=col_aff):
            ctx = _Ctx(Relation(_cols, []), combined, None, _idx)
            return eval_expr(_tag(_on, ctx, _aff), ctx)

        rel = join_relation(rel, right, kind, on_eval)
        rel.index = _build_index(rel)
    return rel


def execute(sql_or_query, tables):
    """Run a query against {name: Table} and return (column_names, rows)."""
    q = sql_or_query if isinstance(sql_or_query, dict) else parse_query(sql_or_query)
    rel = _build_from(q, tables)

    # affinity lookup for column refs (position -> declared type)
    decl = {}
    for t in tables.values():
        for cname, ctype in t.cols:
            decl[cname] = ctype
    col_aff = {i: decl.get(c) for i, (_a, c) in enumerate(rel.cols)}

    rows = rel.rows
    if q["where"] is not None:
        kept = []
        for rv in rows:
            ctx = _Ctx(rel, rv, None, rel.index)
            if truthy(_eval_with_affinity(q["where"], ctx, col_aff)):
                kept.append(rv)
        rows = kept

    agg_context = bool(q["group_by"]) \
        or any(it[0] == "item" and has_aggregate(it[1]) for it in q["items"]) \
        or (q["having"] is not None and has_aggregate(q["having"])) \
        or any(has_aggregate(e) for e, _ in q["order_by"])

    out_names, out_exprs = _expand_items(q["items"], rel)

    # SQLite resolves a select-list alias inside GROUP BY / HAVING / ORDER BY; substitute it
    # with the aliased expression so `HAVING n > 1` means `HAVING COUNT(*) > 1`.
    alias_expr = {}
    for (nm, _e), e in zip(zip(out_names, out_exprs), out_exprs):
        if nm:
            alias_expr.setdefault(nm, e)

    def sub_alias(node):
        if node[0] == "col" and node[1] is None and node[2] in alias_expr:
            return alias_expr[node[2]]
        out = [node[0]]
        for s in node[1:]:
            if isinstance(s, tuple) and s and isinstance(s[0], str):
                out.append(sub_alias(s))
            elif isinstance(s, list):
                out.append([sub_alias(x) if (isinstance(x, tuple) and x and isinstance(x[0], str))
                            else x for x in s])
            else:
                out.append(s)
        return tuple(out)

    group_by = [sub_alias(e) for e in q["group_by"]]
    having = sub_alias(q["having"]) if q["having"] is not None else None

    produced = []      # (values, ctx)
    if agg_context:
        if group_by:
            groups = []
            seen = {}
            for rv in rows:
                ctx = _Ctx(rel, rv, None, rel.index)
                key = distinct_key([_eval_with_affinity(e, ctx, col_aff) for e in group_by])
                if key in seen:
                    groups[seen[key]][1].append(rv)
                else:
                    seen[key] = len(groups)
                    groups.append((rv, [rv]))
        else:
            # a bare aggregate over zero rows still yields exactly one row (COUNT 0 / SUM NULL)
            groups = [(rows[0] if rows else [], rows)]
        for first, grp in groups:
            ctx = _Ctx(rel, first, grp, rel.index)
            if having is not None and not truthy(_eval_with_affinity(having, ctx, col_aff)):
                continue
            vals = [_eval_with_affinity(e, ctx, col_aff) for e in out_exprs]
            produced.append((vals, ctx))
    else:
        for rv in rows:
            ctx = _Ctx(rel, rv, None, rel.index)
            vals = [_eval_with_affinity(e, ctx, col_aff) for e in out_exprs]
            produced.append((vals, ctx))

    if q["distinct"]:
        seen, uniq = set(), []
        for vals, ctx in produced:
            k = distinct_key(vals)
            if k not in seen:
                seen.add(k)
                uniq.append((vals, ctx))
        produced = uniq

    if q["order_by"]:
        alias_pos = {}
        for i, (nm, _e) in enumerate(zip(out_names, out_exprs)):
            if nm:
                alias_pos.setdefault(nm, i)
        keys = []
        for vals, ctx in produced:
            row_key = []
            for e, desc in q["order_by"]:
                e = sub_alias(e)
                if e[0] == "col" and e[1] is None and e[2] in alias_pos:
                    v = vals[alias_pos[e[2]]]
                else:
                    v = _eval_with_affinity(e, ctx, col_aff)
                row_key.append((sort_key(v), desc))
            keys.append(row_key)
        order = sorted(range(len(produced)),
                       key=lambda i: _order_tuple(keys[i]))
        produced = [produced[i] for i in order]

    if q["limit"] is not None:
        start = q["offset"] or 0
        produced = produced[start:start + q["limit"]] if q["limit"] >= 0 else produced[start:]
    elif q["offset"]:
        produced = produced[q["offset"]:]

    return out_names, [v for v, _ in produced]


class _Desc:
    __slots__ = ("v",)

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        return other.v < self.v

    def __eq__(self, other):
        return other.v == self.v


def _order_tuple(row_key):
    return tuple(_Desc(k) if desc else k for k, desc in row_key)


def _eval_with_affinity(node, ctx, col_aff):
    return eval_expr(_tag(node, ctx, col_aff), ctx)


def _tag(node, ctx, col_aff):
    """Recursively attach declared affinities to bare column refs (see affinity_of)."""
    k = node[0]
    if k == "col":
        i = _resolve(ctx, node[1], node[2])
        return ("col", node[1], node[2], col_aff.get(i))
    if k == "agg":
        return node
    out = [k]
    for sub in node[1:]:
        if isinstance(sub, tuple) and sub and isinstance(sub[0], str):
            out.append(_tag(sub, ctx, col_aff))
        elif isinstance(sub, list):
            new = []
            for x in sub:
                if isinstance(x, tuple) and x and isinstance(x[0], str):
                    new.append(_tag(x, ctx, col_aff))
                elif isinstance(x, tuple) and x and isinstance(x[0], tuple):
                    new.append(tuple(_tag(y, ctx, col_aff) if isinstance(y, tuple)
                                     else y for y in x))
                else:
                    new.append(x)
            out.append(new)
        else:
            out.append(sub)
    return tuple(out)


def _expand_items(items, rel):
    names, exprs = [], []
    for it in items:
        if it[0] == "star":
            tbl = it[1]
            for (_alias, col) in rel.cols:
                if tbl is None or _alias == tbl:
                    names.append(col)
                    exprs.append(("col", _alias, col))
            continue
        e, alias = it[1], it[2]
        if alias:
            names.append(alias)
        elif e[0] == "col":
            names.append(e[2])
        else:
            names.append(None)
        exprs.append(e)
    return names, exprs


def run(sql, tables):
    """Convenience: execute SQL text against {name: Table}."""
    return execute(sql, tables)


def table_from(cols, rows):
    return Table([(c, t) for c, t in cols], [list(r) for r in rows])


# --------------------------------------------------------------------------
# selftest -- the differential harness in diff_sqlite.py is the real teeth
# --------------------------------------------------------------------------

_SELFTEST = [
    ("SELECT 1 + 2 * 3", [], [[7]]),
    ("SELECT 7 / 2", [], [[3]]),
    ("SELECT -7 / 2", [], [[-3]]),
    ("SELECT 7.0 / 2", [], [[3.5]]),
    ("SELECT 1 / 0", [], [[None]]),
    ("SELECT NULL = NULL", [], [[None]]),
    ("SELECT 1 IS NULL", [], [[0]]),
    ("SELECT NULL IS NULL", [], [[1]]),
    ("SELECT 'a' < 5", [], [[0]]),
    ("SELECT 5 < 'a'", [], [[1]]),
    ("SELECT '5abc' + 0", [], [[5]]),
    ("SELECT 'a' + 0", [], [[0]]),
    ("SELECT '5.5' + 0", [], [[5.5]]),
    ("SELECT 'abc' LIKE 'A%'", [], [[1]]),
    ("SELECT 'abc' LIKE 'a_c'", [], [[1]]),
    ("SELECT 'abc' NOT LIKE 'b%'", [], [[1]]),
    ("SELECT 2 IN (1, 2, NULL)", [], [[1]]),
    ("SELECT 3 IN (1, 2, NULL)", [], [[None]]),
    ("SELECT 3 NOT IN (1, 2, NULL)", [], [[None]]),
    ("SELECT 3 NOT IN (1, 2)", [], [[1]]),
    ("SELECT 2 BETWEEN 1 AND 3", [], [[1]]),
    ("SELECT CASE WHEN 1 = 2 THEN 'a' ELSE 'b' END", [], [['b']]),
]


def _selftest():
    tables = {
        "t": table_from([("id", "INTEGER"), ("s", "TEXT")], [[1, "a"], [2, None], [3, "c"]]),
    }
    fails = 0
    for sql, _t, want in _SELFTEST:
        got = execute(sql, tables)[1]
        if got != want:
            fails += 1
            print("SELFTEST FAIL: %s -> %r (want %r)" % (sql, got, want))
    extra = [
        ("SELECT COUNT(*), COUNT(s), SUM(id) FROM t", [[3, 2, 6]]),
        ("SELECT SUM(s) FROM t", [[0.0]]),          # text coerces to REAL 0.0
        ("SELECT SUM(id) FROM t WHERE id > 99", [[None]]),
        ("SELECT * FROM t ORDER BY s", [[2, None], [1, "a"], [3, "c"]]),
        ("SELECT s, COUNT(*) AS n FROM t GROUP BY s ORDER BY n, s",
         [[None, 1], ["a", 1], ["c", 1]]),
        ("SELECT s, COUNT(*) AS n FROM t GROUP BY s HAVING n > 1", []),
        ("SELECT id FROM t WHERE s IS NULL", [[2]]),
        ("SELECT id FROM t ORDER BY id DESC LIMIT 2", [[3], [2]]),
        ("SELECT id FROM t ORDER BY id LIMIT 2 OFFSET 1", [[2], [3]]),
        ("SELECT id FROM t ORDER BY id LIMIT -1 OFFSET 1", [[2], [3]]),
    ]
    for sql, want in extra:
        try:
            got = execute(sql, tables)[1]
        except SqlError as exc:
            got = "SqlError: %s" % exc
        if got != want:
            fails += 1
            print("SELFTEST FAIL: %s -> %r (want %r)" % (sql, got, want))
    print("selftest: %d/%d" % (len(_SELFTEST) + len(extra) - fails, len(_SELFTEST) + len(extra)))
    return 0 if fails == 0 else 1


if __name__ == "__main__":
    if "--selftest" in sys.argv:
        sys.exit(_selftest())
    print(__doc__.strip().splitlines()[1])
    print("usage: minisql.py --selftest   (the differential battery is diff_sqlite.py)")