Skip to content

The easy-to-use open source Business Intelligence and Embedded Analytics tool that lets everyone work with data :bar_chart:

98.2 KB
Raw Blame
import json
import logging
import re

import sqlglot

# sqlglot's parser warnings quote raw chunks of the SQL being parsed ("... contains unsupported
# syntax. Falling back to parsing as a 'Command'."); silence them so customer SQL never reaches
# stderr/server logs.
logging.getLogger("sqlglot").setLevel(logging.CRITICAL)
import sqlglot.lineage as lineage
import sqlglot.optimizer as optimizer
import sqlglot.optimizer.qualify as qualify
from sqlglot import exp
from sqlglot.dialects.clickhouse import ClickHouse
from sqlglot.errors import OptimizeError, ParseError
from sqlglot.optimizer.normalize_identifiers import normalize_identifiers

# sqlglot (as of 28.6.0) renders every placeholder in ClickHouse's named-parameter
# syntax `{name: Type}`, so a positional JDBC placeholder `?` (a nameless Placeholder)
# round-trips to `{?: }`, which ClickHouse rejects with "Expected substitution name"
# (Code 62). Compiled queries we rewrite can carry prepared-statement params — e.g.
# workspace table remapping of an incremental transform's checkpoint filter — so keep
# positional placeholders as `?`; named query parameters still take the upstream path.
_clickhouse_placeholder_sql = ClickHouse.Generator.placeholder_sql


def _placeholder_sql_keep_positional(self, expression: exp.Placeholder) -> str:
    if not expression.this:
        return "?"
    return _clickhouse_placeholder_sql(self, expression)


ClickHouse.Generator.placeholder_sql = _placeholder_sql_keep_positional


def is_quoted_identifier(name: str, dialect: str = None) -> bool:
    if not isinstance(name, str):
        return False
    else:
        exp.to_identifier
        # Using dummy_sql instead of exp.to_identifier so dialect can be provided
        dummy_sql = "SELECT 1 AS " + name
        ast = sqlglot.parse_one(dummy_sql, dialect=dialect)
        return ast.expressions[0].args.get("alias").args.get("quoted")

def needs_quoting(name: str, dialect: str = None) -> bool:
    """Check if an identifier needs to be quoted due to special characters."""
    if not name:
        return False
    # Check for common problematic characters
    if '-' in name or ' ' in name:
        return True
    # Starts with a digit
    if name[0].isdigit():
        return True
    # provided rename has quotes
    if is_quoted_identifier(name, dialect=dialect):
        return True
    return False

def unquote_identifier(name: str, dialect: str = None):
    """If name is already a quoted identifier (e.g., `foo` in MySQL, "foo" in Postgres),
    return (unquoted_name, True). Otherwise return (name, False)."""
    if not name:
        return (name, False)
    try:
        dummy_sql = "SELECT 1 AS " + name
        ast = sqlglot.parse_one(dummy_sql, dialect=dialect)
        ident = ast.expressions[0].args.get("alias")
        if ident and ident.quoted:
            return (ident.this, True)
    except:
        pass
    return (name, False)

def temp_table_prefix(table):
    """
    The T-SQL temp table prefix of a table expression: "##" for a global temp table, "#" for a local one, and "" for
    any other table. SQLGlot keeps the prefix as a flag on the identifier rather than in its name.
    """
    identifier = table.this
    if not isinstance(identifier, exp.Identifier):
        return ""
    if identifier.args.get("global_"):
        return "##"
    if identifier.args.get("temporary"):
        return "#"
    return ""

def table_parts(table):
    """
    Extract (catalog, schema, table) 3-tuple from a table expression.
    Returns None if the table doesn't have a valid name (e.g., UDTFs).

    SQLGlot naming:
    - table.catalog → SQL catalog (e.g., BigQuery project, Snowflake database)
    - table.db      → SQL schema (e.g., BigQuery dataset, Postgres schema)
    - table.name    → table name, to which the T-SQL temp table prefix is added (see `temp_table_prefix`)
    """
    name = table.name
    if not isinstance(name, str) or not name:
        # UDTFs and other function-based sources don't have traditional table names
        return None
    return (table.catalog or None, table.db or None, temp_table_prefix(table) + name)

def shadowing_cte_names(node):
    """The CTE names that shadow a table at `node`: those declared by a query `node` sits inside."""
    names = set()
    own = set()
    current = node
    while current is not None:
        # A CTE does not shadow the table its own body reads: `WITH orders AS (SELECT * FROM orders)` selects
        # from the real table. A recursive CTE is the exception -- reading its own name is what recursion is.
        if isinstance(current, exp.CTE) and current.alias:
            declaration = current.parent
            if not (isinstance(declaration, exp.With) and declaration.args.get("recursive")):
                own.add(current.alias.lower())
        # Found by type rather than by arg name, which sqlglot spells `with_` in some versions and `with` in
        # others.
        for value in current.args.values():
            if isinstance(value, exp.With):
                names.update(cte.alias.lower() for cte in value.expressions if cte.alias)
        current = current.parent
    return names - own


def statements(sql, dialect=None):
    """Every statement in `sql`, without the empty ones a stray semicolon leaves behind.

    A caller asking what a query reads, or rewriting what it reads, is asking about the whole string it was handed:
    reading only the first statement answers a question nobody asked, quietly.
    """
    return [ast for ast in sqlglot.parse(sql, read=dialect) if ast is not None]


def _nonempty_statements(stmts):
    """`stmts` from `sqlglot.parse` without the empty ones: a stray semicolon parses as `None`, and a comment after a
    semicolon as a bare `exp.Semicolon`."""
    return [s for s in stmts if s is not None and not isinstance(s, exp.Semicolon)]


def table_references(ast):
    """Every table the statement `ast` names, as sqlglot Table nodes.

    A CTE reference, a derived table, a VALUES clause and a table function are not tables and are left out; the
    table a statement writes -- an INSERT, UPDATE, DELETE or MERGE target -- is one, and is included. This is the
    walk `replace_names` rewrites by, so what a caller is told a query reads is what a rewrite would replace.
    """
    for table in ast.find_all(exp.Table):
        if table_parts(table) is None:
            continue
        if not table.db and not table.catalog and table.name.lower() in shadowing_cte_names(table):
            continue
        yield table


def referenced_tables(sql: str, dialect: str = "postgres") -> str:
    """
    Extract table references from a SQL query.

    Returns a JSON array of [catalog, schema, table] 3-tuples:
    [[null, null, "users"], [null, "public", "orders"], ["myproject", "dataset", "events"]]

    Excludes CTEs, subquery aliases, and UDTFs.

    :param sql: SQL query string
    :param dialect: SQL dialect (postgres, mysql, snowflake, bigquery, redshift, duckdb)

    Examples:
        referenced_tables("SELECT * FROM users")
        => '[[null, null, "users"]]'

        referenced_tables("SELECT * FROM public.users")
        => '[[null, "public", "users"]]'

        referenced_tables("SELECT * FROM myproject.analytics.events", "bigquery")
        => '[["myproject", "analytics", "events"]]'
    """
    tables = {table_parts(table)
              for ast in statements(sql, dialect)
              for table in table_references(ast)}
    # Sort for deterministic output (nulls sort first via empty string)
    return json.dumps(sorted(tables, key=lambda x: (x[0] or "", x[1] or "", x[2])))

def referenced_fields(sql: str, dialect: str = "postgres") -> str:
    """
    Extract field references from a SQL query, returning only fields from actual database tables.

    Returns a JSON array of [catalog, schema, table, field] 4-tuples:
    [[null, null, "users", "id"], [null, "public", "orders", "total"]]

    Includes:
    - Wildcards as [catalog, schema, table, "*"]
    - All specific column references

    Excludes:
    - Fields created in CTEs or subqueries
    - Aliases (returns actual table names, not their aliases)
    - Computed/derived columns

    :param sql: SQL query string
    :param dialect: SQL dialect (postgres, mysql, snowflake, bigquery, redshift, duckdb)

    Examples:
        referenced_fields("SELECT id FROM users", "postgres")
        => '[[null, null, "users", "id"]]'

        referenced_fields("SELECT * FROM public.users", "postgres")
        => '[[null, "public", "users", "*"]]'

        referenced_fields("SELECT * FROM myproject.analytics.events", "bigquery")
        => '[["myproject", "analytics", "events", "*"]]'
    """
    ast = sqlglot.parse_one(sql, read=dialect)
    root_scope = optimizer.build_scope(ast)

    fields = set()

    # Collect all CTE names to exclude them
    cte_names = set()
    for cte in ast.find_all(exp.CTE):
        if cte.alias:
            cte_names.add(cte.alias)

    # Track scopes with unqualified wildcards
    unqualified_wildcard_scopes = []

    # Traverse all scopes to find column references
    for scope in root_scope.traverse():
        # Build a mapping of table aliases to table_parts tuples (catalog, schema, table)
        # Only include actual tables, not CTEs or subqueries
        alias_to_table_parts = {}
        for alias, source in scope.sources.items():
            if isinstance(source, exp.Table):
                table_name = source.name
                # Skip if this is actually a CTE reference
                if table_name and table_name not in cte_names and alias not in cte_names:
                    parts = table_parts(source)
                    if parts is not None:
                        alias_to_table_parts[alias] = parts

        # Check for unqualified wildcards (SELECT * without table qualification)
        if isinstance(scope.expression, exp.Select):
            for expr in scope.expression.expressions:
                if isinstance(expr, exp.Star):
                    unqualified_wildcard_scopes.append((scope, alias_to_table_parts))
                    break

        # Find all column references in this scope
        for column in scope.expression.find_all(exp.Column):
            column_name = column.name
            table_ref = column.table

            # Handle qualified wildcards (e.g., "users.*")
            if column_name == "*":
                if table_ref:
                    parts = alias_to_table_parts.get(table_ref)
                    if parts is not None:
                        # 4-tuple: (catalog, schema, table, field)
                        fields.add(parts + ("*",))
                continue

            # Regular column references
            if table_ref:
                parts = alias_to_table_parts.get(table_ref)
                if parts is not None:
                    fields.add(parts + (column_name,))
            else:
                # Column without explicit table qualifier
                # If there's only one source table, use that
                if len(alias_to_table_parts) == 1:
                    parts = list(alias_to_table_parts.values())[0]
                    fields.add(parts + (column_name,))

    # For scopes with unqualified wildcards, add wildcard entries for all tables
    for scope, alias_to_table_parts in unqualified_wildcard_scopes:
        for parts in alias_to_table_parts.values():
            fields.add(parts + ("*",))

    # Sort for deterministic output: catalog, schema, table, field
    return json.dumps(sorted(fields, key=lambda x: (x[0] or "", x[1] or "", x[2], x[3])))

def serialize_error(e):
    """
    Convert SQLGlot exceptions to structured error dicts.

    Unrecognized error formats fall through to 'unhandled' type - the Clojure
    layer can add more specific handling if needed.
    """

    message = e.args[0]
    assert isinstance(message, str), "Unexpected error format."

    match = re.search(r'^Unknown table:\s*(?P<table>.*)', message)
    if match:
        return {"status": "error",
                "type": "unknown_table",
                "message": match.group(),
                "table": match.group('table')}

    match = re.search(r'''(?P<message>^Column '(?P<column>\S+)' could not be resolved.)(?P<details>.*)''', message)
    if match:
        return {"status": "error",
                "type": "column_not_resolved",
                "message": match.group('message'),
                "column": match.group('column'),
                "details": match.group('details')}

    # ('Invalid expression / Unexpected token. Line 1, Col: 23.\n  complete nonsense \x1b[4mquery\x1b[0m',)
    match = re.search(r'(?P<message>^Invalid expression.*?\.)(?P<details>.*)', message)
    if match:
        return {"status": "error",
                "type": "invalid_expression",
                "message": match.group('message'),
                "details": match.group('details')}

    return {"status": "error",
            "type": "unhandled",
            "message": message}

def validate_query(dialect, sql, default_table_schema, sqlglot_schema_json):
    """
    Validate a SQL query against a schema using sqlglot's qualify optimizer.

    Validation modes:
    - Strict mode (sqlglot_schema provided): Validates columns and tables exist in schema.
      Returns errors for unknown tables, unresolved columns, missing table aliases.
    - Permissive mode (sqlglot_schema is None/empty): Only checks SQL syntax, infers schema
      from query structure. Useful for UDTFs and queries against unknown tables.

    Returns JSON with:
    - If valid: {"status": "ok"}
    - If error: {"status": "error", "type": "...", "message": "...", ...}

    Error types:
    - unknown_table: Table reference not found in schema (strict mode only)
    - column_not_resolved: Column not found (includes 'column' and optionally 'details')
    - invalid_expression: Syntax/parse error
    - unhandled: Other errors

    :param dialect: SQLGlot dialect string (e.g., "postgres", "mysql")
    :param sql: SQL query string to validate
    :param default_table_schema: Default schema for unqualified tables
    :param sqlglot_schema_json: JSON-encoded schema dict {schema: {table: {column: type}}},
                                or None/empty for permissive mode
    """
    status = {"status": "ok"}

    # Decode JSON schema if provided (GraalVM Polyglot passes complex maps as JSON strings)
    sqlglot_schema = json.loads(sqlglot_schema_json) if sqlglot_schema_json else None

    # Determine validation mode based on whether schema is provided
    # - Strict mode: schema provided → validate columns/tables exist
    # - Permissive mode: no schema → only check syntax, infer schema from query
    strict_mode = sqlglot_schema is not None and len(sqlglot_schema) > 0

    try:
        ast = sqlglot.parse_one(sql, read=dialect)
        ast = qualify.qualify(ast,
                            db=default_table_schema,
                            dialect=dialect,
                            schema=sqlglot_schema if strict_mode else None,
                            # In strict mode: don't infer, validate against provided schema
                            # In permissive mode: infer schema from query (handles UDTFs)
                            infer_schema=not strict_mode,
                            # In strict mode: validate that columns can be resolved
                            validate_qualify_columns=strict_mode,
                            sql=sql)
    except ParseError as e:
        status |= serialize_error(e)
    except OptimizeError as e:
        status |= serialize_error(e)

    return json.dumps(status)

#############################################################################
# Experimental (using lineage)
#############################################################################

def is_pure_column(root):
    """
    Check whether the lineage graph is a path of columns terminated by table.

    :param root: The root of the lineage graph
    """
    for node in root.walk():
        expression = node.expression
        downstream = node.downstream

        # We are looking for "path"...
        if len(downstream) > 1:
            return False

        examined = None
        if (isinstance(expression, exp.Alias)):
            examined = expression.this
        else:
            examined = expression

        # ...of `exp.Column`s...
        if isinstance(examined, exp.Column):
            continue
        # ...terminated by the `exp.Table`
        elif isinstance(examined, exp.Table):
            continue
        else:
            return False
    return True

def simple_query(sql: str, dialect: str = None) -> str:
    """
    Check if SQL is a simple SELECT (no LIMIT, OFFSET, or CTEs).

    Used by Workspaces to determine if automatic checkpoints can be inserted.

    Returns a JSON object with:
    - If simple: {"is_simple": true}
    - If not simple: {"is_simple": false, "reason": "..."}

    :param sql: SQL query string to check
    :param dialect: SQL dialect (postgres, mysql, snowflake, bigquery, etc.)

    Examples:
        simple_query("SELECT * FROM users")
        => '{"is_simple": true}'

        simple_query("SELECT * FROM users LIMIT 10")
        => '{"is_simple": false, "reason": "Contains a LIMIT"}'

        simple_query("WITH cte AS (SELECT 1) SELECT * FROM cte")
        => '{"is_simple": false, "reason": "Contains a CTE"}'
    """
    try:
        ast = sqlglot.parse_one(sql, read=dialect)

        # Must be a SELECT or Query type (CTE queries parse as Select with 'with' arg)
        if not isinstance(ast, (exp.Select, exp.Query)):
            return json.dumps({"is_simple": False, "reason": "Not a simple SELECT"})

        # No CTEs (WITH clause) - SQLGlot uses "with_" (with underscore) as the arg name
        if ast.args.get("with_"):
            return json.dumps({"is_simple": False, "reason": "Contains a CTE"})

        # For non-Select Query types (Union, Intersect, etc.), reject
        if not isinstance(ast, exp.Select):
            return json.dumps({"is_simple": False, "reason": "Not a simple SELECT"})

        # No LIMIT
        if ast.args.get("limit"):
            return json.dumps({"is_simple": False, "reason": "Contains a LIMIT"})

        # No OFFSET
        if ast.args.get("offset"):
            return json.dumps({"is_simple": False, "reason": "Contains an OFFSET"})

        return json.dumps({"is_simple": True})
    except ParseError as e:
        return json.dumps({"is_simple": False, "reason": str(e)})
    except Exception as e:
        return json.dumps({"is_simple": False, "reason": f"Unexpected error: {str(e)}"})

def _wrap_base_table(table, alias):
    """Build a self-UNION subquery, aliased `alias`, that scans `table` once but strips any IDENTITY
    property inherited from it (see `add_into_clause`)."""
    bare_table = table.copy()
    bare_table.set("alias", None)
    self_union = exp.union(
        exp.select("*").from_(bare_table.copy()),
        exp.select("*").from_(bare_table.copy()).where("1 = 0"),
        distinct=False,
    )
    return self_union.subquery(alias=alias)

def add_into_clause(sql: str, table_name: str, dialect: str = None) -> str:
    """
    Add an INTO clause to a SELECT statement for SQL Server SELECT INTO syntax, and rewrite every
    base-table reference into a self-UNION subquery so the new table doesn't inherit a source
    column's IDENTITY property.

    Transforms: SELECT * FROM products
    Into:       SELECT * INTO "new_table" FROM (SELECT * FROM products UNION ALL SELECT * FROM products WHERE 1 = 0) AS products

    Used by SQL Server transforms which require SELECT INTO syntax instead of CREATE TABLE AS SELECT.
    A plain `SELECT ... INTO` copies a directly-projected source IDENTITY column onto the new table,
    which later breaks an incremental append (`INSERT INTO <target> SELECT ...`) with SQL Server error
    8101. Wrapping each base table in a self-UNION breaks that IDENTITY lineage -- the UNION's second
    branch is always empty and gets elided by SQL Server's contradiction detection, so each table is
    still scanned once -- without touching filters, ORDER BY, TOP, or query params. CTEs, derived
    tables, table-valued functions, and T-SQL `#`/`##` temp tables are left untouched.

    A table with no explicit alias is wrapped under an alias equal to its bare name, and any column
    in the same scope that referenced it via a schema/catalog-qualified name (e.g. `dbo.products.id`,
    legal only against a real table) has that now-invalid qualifier stripped, since a derived table can
    only be referenced by its single-part alias.

    :param sql: The SELECT SQL query string
    :param table_name: The target table name (already formatted/quoted)
    :param dialect: SQL dialect (e.g., "tsql" for SQL Server)
    :return: Modified SQL string with INTO clause and base tables wrapped

    Examples:
        add_into_clause("SELECT * FROM products", '"PRODUCTS_COPY"', "tsql")
        => 'SELECT * INTO [PRODUCTS_COPY] FROM (SELECT * FROM products UNION ALL SELECT * FROM products WHERE 1 = 0) AS products'
    """
    ast = sqlglot.parse_one(sql, read=dialect)

    if not isinstance(ast, exp.Select):
        raise ValueError("SQL must be a SELECT statement")

    cte_names = {cte.alias for cte in ast.find_all(exp.CTE) if cte.alias}
    seen_ids = set()

    for scope in optimizer.build_scope(ast).traverse():
        scope_replacements = []
        for alias, source in scope.sources.items():
            if not isinstance(source, exp.Table):
                continue
            table_name_only = source.name
            if not table_name_only or table_name_only in cte_names or alias in cte_names:
                continue
            # A T-SQL `#`/`##` temp table has no IDENTITY lineage worth breaking, and its derived-table alias would lose
            # the prefix that qualified column references keep.
            if temp_table_prefix(source):
                continue
            if id(source) in seen_ids:
                continue
            seen_ids.add(id(source))
            scope_replacements.append((source, alias))

        for table, alias in scope_replacements:
            # Columns in this scope may reference the table via a schema/catalog-qualified name
            # (e.g. `dbo.products.id`), which only resolves against a real table. Once the table
            # becomes a derived table it's only reachable by its single-part alias, so strip the
            # now-invalid qualifiers.
            for column in scope.source_columns(alias):
                column.set("db", None)
                column.set("catalog", None)
            table.replace(_wrap_base_table(table, alias))

    # Create the Into expression with the table identifier
    # The table_name is pre-formatted, so parse it to preserve quotes
    into = exp.Into(this=exp.to_table(table_name))

    # Set the into clause on the select
    ast.set("into", into)

    # Generate SQL in the target dialect
    return ast.sql(dialect=dialect)


def returned_columns_lineage(dialect, sql, default_table_schema, sqlglot_schema_json):
    """
    Extract column lineage from SQL query.

    Args:
        dialect: SQL dialect string (e.g., "postgres", "mysql")
        sql: SQL query string
        default_table_schema: Default schema name (e.g., "public")
        sqlglot_schema_json: JSON-encoded schema map (to avoid GraalVM polyglot issues)

    Returns:
        JSON array of [alias, is_pure, dependencies] tuples
    """
    # Decode schema from JSON (passed from Clojure to avoid polyglot map issues)
    sqlglot_schema = json.loads(sqlglot_schema_json) if sqlglot_schema_json else None

    ast = sqlglot.parse_one(sql, read=dialect)
    ast = qualify.qualify(ast,
                          db=default_table_schema,
                          dialect=dialect,
                          schema=sqlglot_schema,
                          infer_schema=True,
                          sql=sql)

    assert isinstance(ast, exp.Query), "Ast does not represent a `Query`."

    dependencies = []
    for select in ast.named_selects:

        # Note: SQL allows duplicate column aliases (e.g., SELECT 1 AS x, 2 AS x).
        # We track columns by position, not by name, so duplicates are fine.

        select_elm_lineage = lineage.lineage(select, ast.sql(dialect), dialect=dialect)
        is_pure_select = is_pure_column(select_elm_lineage)

        leaves = set()
        for node in select_elm_lineage.walk():
            if (# Leaf nodes of `.walk` are `exp.Table`s. We are interested
                # in the columns selected from those tables (i.e. penultimate
                # level). The condition is intended to examine those columns.
                len(node.downstream) == 1
                and isinstance(node.downstream[0].expression, exp.Table)
                and not node.downstream[0].downstream):
                # For UDTFs/table functions, the penultimate node may not be a Column
                # (e.g., FLATTEN results). Skip these gracefully.
                if not isinstance(node.expression.this, exp.Column):
                    continue
                # Extract table parts (catalog, schema, table) from the source.
                # Note: Schema may be missing when table is aliased to its own name.
                table = table_parts(node.downstream[0].expression)
                # Skip UDTFs and other function-based sources that don't have real table names
                if table is not None:
                    namespaced_column = table + (node.expression.this.name, )
                    leaves.add(namespaced_column)

        dependencies.append((select, is_pure_select, tuple(leaves), ))

    return json.dumps(dependencies)


def fold_keys(mapping):
    """
    Case-insensitive view of a replacement map, for matching an identifier written in another case.

    An identifier names the same thing however it is cased (Metabase treats every database as case-agnostic, see
    `macaw-options`), so `FROM people` must match a key of `PEOPLE`. Keys that differ only in case have no single
    answer, so they are dropped rather than resolved arbitrarily: an exact match still finds them.
    """
    folded = {}
    ambiguous = set()
    for key, value in mapping.items():
        folded_key = tuple(part.lower() if isinstance(part, str) else part for part in key)
        if folded_key in folded and folded[folded_key] != value:
            ambiguous.add(folded_key)
        folded[folded_key] = value
    return {key: value for key, value in folded.items() if key not in ambiguous}


def fold_lookup(folded, key):
    """The value `key` maps to in a [[fold_keys]] map, ignoring the case of every part."""
    return folded.get(tuple(part.lower() if isinstance(part, str) else part for part in key))


def replace_names(sql: str, replacements_json: str, dialect: str = None) -> str:
    """
    Replace schema, table, and column names in a SQL query.

    SECURITY NOTE: Replacement values are injected into the SQL AST without sanitization.
    This is safe because the only caller (workspaces/execute.clj) passes system-generated
    values: isolation schema names (mb__isolation_<slug>_<id>) and table names from
    database metadata. User input never flows into replacement values.

    Args:
        sql: SQL query string
        replacements_json: JSON-encoded map with keys:
            - schemas: {old_schema: new_schema}
            - tables: list of [[{schema?, table}, new_name], ...]
            - columns: list of [[{schema?, table?, column}, new_name], ...]
        dialect: SQL dialect string

    Returns:
        Modified SQL string with replacements applied.

    Examples:
        replace_names("SELECT * FROM people", '{"tables": [[{"table": "people"}, "users"]]}', "postgres")
        => 'SELECT * FROM users'

        replace_names("SELECT id FROM orders", '{"columns": [[{"table": "orders", "column": "id"}, "user_id"]]}')
        => 'SELECT user_id FROM orders'
    """
    replacements = json.loads(replacements_json)
    schemas = replacements.get("schemas") or {}
    # Tables: (db, schema, table) -> replacement. `db` is the catalog (BigQuery project, ClickHouse database, etc),
    # None when the key doesn't name one.
    table_map = {(key.get("db"), key.get("schema"), key["table"]): new_name
                 for key, new_name in replacements.get("tables") or []}
    # Columns: (schema, table, column) -> new name. `table` is None for a key that matches any table.
    column_map = {(key.get("schema"), key.get("table"), key["column"]): new_name
                  for key, new_name in replacements.get("columns") or []}
    folded_schemas = fold_keys({(name,): new_name for name, new_name in schemas.items()})

    def rewrite(ast):
        """The statement `ast` with every replacement applied."""

        # Names a bare column qualifier may refer to instead of a table: table and subquery aliases and CTE names. Folded,
        # because a reference matches a name whatever its case.
        aliases = {node.alias.lower() for node in ast.find_all(exp.Table, exp.Subquery, exp.CTE) if node.alias}

        def part_matches(key_part, ref_part, quoted):
            """Whether one part of a replacement key names the same thing as the reference's."""
            if key_part is None or ref_part is None:
                return key_part is None and ref_part is None
            # A quoted reference is case-significant to the engine — Postgres `"Orders"` is not `orders` — so that part
            # matches only as written. An unquoted one matches whatever its case.
            return key_part == ref_part if quoted else key_part.lower() == ref_part.lower()

        def find_table_replacement(db, schema, table, quoted):
            # Most specific key first: (db, schema, table), then (None, schema, table), then (None, None, table).
            # A key without a db matches a reference in any catalog; a key with one only matches that catalog.
            # Each shape is tried as written before it is tried part by part, so an exact key always wins, and keys that
            # differ only in the case of an unquoted part answer nothing rather than one of them arbitrarily.
            shapes = ((db, schema, table), (None, schema, table), (None, None, table))
            for key in shapes:
                replacement = table_map.get(key)
                if replacement:
                    return replacement
            for key in shapes:
                matched = [table_map[map_key]
                           for map_key in table_map
                           if all(part_matches(map_part, ref_part, was_quoted)
                                  for map_part, ref_part, was_quoted in zip(map_key, key, quoted))]
                if matched:
                    # Keys that differ only in the case of an unquoted part are ambiguous unless they all name the same
                    # replacement, and an ambiguous reference is left alone rather than pointed at one of them.
                    first = matched[0]
                    return first if all(other == first for other in matched) else None
            return None

        def quoted_parts(node, table_arg):
            """Which parts of a table reference the query quoted, in replacement-key order."""
            def quoted(arg):
                value = node.args.get(arg)
                return isinstance(value, exp.Identifier) and value.quoted

            return (quoted("catalog"), quoted("db"), quoted(table_arg))

        def set_identifier(node, arg, name):
            # Sets `arg` of `node` to the identifier `name`, quoted if the identifier it replaces was, if `name` comes
            # quoted, or if `name` needs quoting. Some nodes hold non-Identifier children (e.g. Anonymous), which count
            # as unquoted.
            original = node.args.get(arg)
            original_quoted = isinstance(original, exp.Identifier) and original.quoted
            raw_name, was_quoted = unquote_identifier(name, dialect)
            quoted = original_quoted or was_quoted or needs_quoting(raw_name, dialect)
            node.set(arg, exp.Identifier(this=raw_name, quoted=quoted))

        def replace_table(node, replacement, catalog_arg, schema_arg, table_arg):
            # Applies a table replacement to the name parts `node` keeps under the given args: a Table node keeps them in
            # catalog/db/this, a Column node keeps its qualifier in catalog/db/table. A string replacement renames the
            # table. A {db?, schema?, table?} replacement sets each part it names, and a nil db or schema clears that
            # qualifier, so {:schema nil :table "x"} turns `public.orders` into `x` (matching Macaw).
            if isinstance(replacement, str):
                replacement = {"table": replacement}
            for key, arg in (("db", catalog_arg), ("schema", schema_arg), ("table", table_arg)):
                if replacement.get(key):
                    set_identifier(node, arg, replacement[key])
                elif key != "table" and key in replacement and replacement[key] is None:
                    node.set(arg, None)

        def rename_fn(node):
            if isinstance(node, exp.Table):
                # SQLGlot stores a 3-part name as catalog.db.this: catalog is the BigQuery project or ClickHouse database,
                # db the schema. The replacement is looked up by the original parts, before the schema is renamed.
                db, schema, table = node.catalog or None, node.db, node.name
                new_schema = schemas.get(schema) or fold_lookup(folded_schemas, (schema,)) if schema else None
                if new_schema:
                    set_identifier(node, "db", new_schema)
                # A CTE name shadows a real table of the same name, so an unqualified reference to one declared in an
                # enclosing query names the CTE and must be left alone — renaming it would point the query at the
                # replacement table and silently skip the CTE.
                if not db and not schema and table.lower() in shadowing_cte_names(node):
                    return node
                replacement = find_table_replacement(db, schema, table, quoted_parts(node, "this"))
                if replacement:
                    replace_table(node, replacement, "catalog", "db", "this")

            elif isinstance(node, exp.Column):
                # SQLGlot uses "" (not None) for a missing qualifier part.
                column, table = node.name, node.table
                # A qualifier naming a replaced table (e.g. `public.orders.id`) follows the table. A qualifier without a
                # schema may name an alias instead, which is left alone.
                if table and (node.db or table.lower() not in aliases):
                    replacement = find_table_replacement(
                        node.catalog or None, node.db, table, quoted_parts(node, "table")
                    )
                    if replacement:
                        replace_table(node, replacement, "catalog", "db", "table")
                # A column key matches a column qualified by the key's table, or an unqualified column with any table
                # (the common case: "SELECT id FROM orders" with key {:table "orders" :column "id"}).
                def column_matches(key_table, key_column):
                    return (key_column.lower() == column.lower()
                            and (not table or (key_table or "").lower() == table.lower()))

                new_column = next((new_name
                                   for (_, key_table, key_column), new_name in column_map.items()
                                   if column_matches(key_table, key_column)),
                                  None)
                if new_column:
                    column_quoted = isinstance(node.this, exp.Identifier) and node.this.quoted
                    node.set("this", exp.Identifier(this=new_column, quoted=column_quoted))

            return node

        # Mutated in place rather than through `ast.transform`, whose copy detaches a node from its parents while the
        # function runs — and a CTE only shadows a table for the query that declares it, which is a question about
        # ancestors.
        for table_node in list(ast.find_all(exp.Table)):
            rename_fn(table_node)
        for column_node in list(ast.find_all(exp.Column)):
            rename_fn(column_node)
        return ast.sql(dialect=dialect)

    rewritten = [rewrite(ast) for ast in statements(sql, dialect)]
    return "; ".join(rewritten) if rewritten else sql


#############################################################################
# Field References (Macaw-compatible output)
#############################################################################

def field_references(sql: str, dialect: str = "postgres") -> str:
    """
    Extract field references from SQL, returning used and returned fields.

    This is the SQLGlot equivalent of Macaw's field-references function.
    Returns a JSON object with:
    - used_fields: list of field specs from WHERE, JOIN ON, GROUP BY, ORDER BY
    - returned_fields: list of field specs from SELECT clause (ordered)
    - errors: list of validation errors

    Each field spec has:
    - type: single_column, all_columns, custom_field, composite_field, or unknown_columns
    - column: column name (for single_column)
    - alias: column alias (null if none)
    - source_columns: nested list of possible source columns
    - table: table info (for all_columns)
    - used_fields: list of fields used (for custom_field)
    - member_fields: list of fields (for composite_field)
    """
    try:
        ast = sqlglot.parse_one(sql, read=dialect)
    except ParseError:
        return json.dumps({
            "used_fields": [],
            "returned_fields": [],
            "errors": [{"type": "syntax_error"}]
        })

    walker = FieldReferenceWalker(ast, dialect)
    result = walker.walk()

    # Convert sets to lists for JSON serialization
    result["used_fields"] = list(result["used_fields"])
    result["errors"] = list(result["errors"])

    return json.dumps(result, default=_json_default)


def _json_default(obj):
    """JSON serializer for objects not serializable by default json code"""
    if isinstance(obj, set):
        return list(obj)
    if isinstance(obj, frozenset):
        return list(obj)
    raise TypeError(f"Object of type {type(obj)} is not JSON serializable")


class FieldReferenceWalker:
    """
    Walks SQLGlot AST to extract field references matching Macaw's output format.

    Key concepts:
    - sources: Nested list of source tables/subqueries. Outer list = scope levels,
               inner list = same-scope sources (FROM + JOINs).
    - withs: Set of CTE definitions, progressively built.
    """

    def __init__(self, ast, dialect):
        self.ast = ast
        self.dialect = dialect

    def walk(self):
        """Main entry point - returns {used_fields, returned_fields, errors}"""
        return self._process_query(self.ast, outside_sources=[], withs={})

    def _process_query(self, expr, outside_sources, withs):
        """Process a query node (SELECT, UNION, etc.)"""
        if isinstance(expr, exp.Select):
            return self._process_select(expr, outside_sources, withs)
        elif isinstance(expr, exp.Union):
            return self._process_union(expr, outside_sources, withs)
        else:
            # Unknown query type
            return {
                "used_fields": set(),
                "returned_fields": [],
                "errors": {self._syntax_error()}
            }

    def _process_select(self, select_expr, outside_sources, withs):
        """Process a SELECT statement."""
        errors = set()  # Set of frozen errors for deduplication

        # Handle CTEs (WITH clause)
        local_withs = dict(withs)
        with_clause = select_expr.args.get("with_")
        if with_clause:
            is_recursive = with_clause.args.get("recursive")
            for cte in with_clause.expressions:
                cte_name = cte.alias
                cte_body = cte.this

                if is_recursive and isinstance(cte_body, exp.Union):
                    # For recursive CTEs with UNION, process the base case first
                    # to get the returned_fields structure, then process the full body.
                    # The base case is the left side of the UNION.
                    base_result = self._process_query(cte_body.left, outside_sources, local_withs)

                    # Now add the CTE to local_withs with the base case's returned_fields
                    # so the recursive part can reference it.
                    # Mark it as the "current CTE" so we can detect self-references.
                    local_withs[cte_name] = {
                        "names": {"table": cte_name, "table_alias": cte_name},
                        "returned_fields": base_result["returned_fields"],
                        "used_fields": base_result["used_fields"],
                        "errors": base_result["errors"],
                        "is_recursive_cte": True  # Marker survives JOIN aliasing
                    }

                    # Process the full CTE body (UNION) with the CTE now available
                    cte_result = self._process_query(cte_body, outside_sources, local_withs)

                    # Keep is_recursive_cte flag in final entry
                    local_withs[cte_name] = {
                        "names": {"table": cte_name},
                        "returned_fields": cte_result["returned_fields"],
                        "used_fields": cte_result["used_fields"],
                        "errors": cte_result["errors"],
                        "is_recursive_cte": True
                    }
                else:
                    # Non-recursive CTE - just process normally
                    cte_result = self._process_query(cte_body, outside_sources, local_withs)

                    local_withs[cte_name] = {
                        "names": {"table": cte_name},
                        "returned_fields": cte_result["returned_fields"],
                        "used_fields": cte_result["used_fields"],
                        "errors": cte_result["errors"]
                    }
                # cte_result["errors"] is a list of dicts, freeze them for set membership
                for e in cte_result["errors"]:
                    errors.add(self._freeze_field(e) if isinstance(e, dict) else e)

        # Build local sources from FROM + JOINs
        local_sources = self._build_sources(select_expr, outside_sources, local_withs)
        combined_sources = [local_sources] + outside_sources

        # Process returned fields (SELECT clause)
        returned_fields = []
        for select_item in select_expr.expressions:
            fields = self._find_returned_fields(select_item, combined_sources, local_withs)
            for field_result in fields:
                if "col" in field_result:
                    returned_fields.append(field_result["col"])
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # Build sources including SELECT aliases for ORDER BY resolution
        # SELECT aliases should be a separate scope level from table sources,
        # so that source_columns properly nests [select_aliases] [table_sources]
        select_source = {
            "names": None,
            "returned_fields": [f for f in returned_fields if f.get("alias")],
            "used_fields": set(),
            "errors": set()
        }
        sources_with_select = [[select_source]] + [local_sources] + outside_sources

        # Process used fields
        used_fields = set()

        # SELECT clause (references in expressions, not the returned columns themselves)
        for select_item in select_expr.expressions:
            for field_result in self._find_used_fields(select_item, combined_sources, local_withs):
                if "col" in field_result:
                    used_fields.add(self._freeze_field(field_result["col"]))
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # WHERE clause (include select aliases for lineage tracking, matching Macaw)
        where = select_expr.args.get("where")
        if where:
            for field_result in self._find_used_fields(where, sources_with_select, local_withs):
                if "col" in field_result:
                    used_fields.add(self._freeze_field(field_result["col"]))
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # JOIN ON conditions (include select aliases for lineage tracking, matching Macaw)
        for join in select_expr.args.get("joins", []):
            on_clause = join.args.get("on")
            if on_clause:
                for field_result in self._find_used_fields(on_clause, sources_with_select, local_withs):
                    if "col" in field_result:
                        used_fields.add(self._freeze_field(field_result["col"]))
                    if "errors" in field_result:
                        errors.update(field_result["errors"])

        # GROUP BY
        group = select_expr.args.get("group")
        if group:
            for field_result in self._find_used_fields(group, sources_with_select, local_withs):
                if "col" in field_result:
                    used_fields.add(self._freeze_field(field_result["col"]))
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # ORDER BY (can reference SELECT aliases)
        order = select_expr.args.get("order")
        if order:
            for field_result in self._find_used_fields(order, sources_with_select, local_withs):
                if "col" in field_result:
                    used_fields.add(self._freeze_field(field_result["col"]))
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # HAVING clause
        having = select_expr.args.get("having")
        if having:
            for field_result in self._find_used_fields(having, sources_with_select, local_withs):
                if "col" in field_result:
                    used_fields.add(self._freeze_field(field_result["col"]))
                if "errors" in field_result:
                    errors.update(field_result["errors"])

        # Include used_fields from local sources (CTEs)
        for source in local_sources:
            for field in source.get("used_fields", set()):
                if isinstance(field, dict):
                    used_fields.add(self._freeze_field(field))
                else:
                    used_fields.add(field)

        # Include used_fields from CTEs
        for cte_source in local_withs.values():
            for field in cte_source.get("used_fields", set()):
                if isinstance(field, dict):
                    used_fields.add(self._freeze_field(field))
                else:
                    used_fields.add(field)

        return {
            "used_fields": [self._unfreeze_field(f) for f in used_fields],
            "returned_fields": returned_fields,
            "errors": [self._unfreeze_field(e) for e in errors]
        }

    def _process_union(self, union_expr, outside_sources, withs):
        """Process UNION/INTERSECT/EXCEPT - creates composite_field for returned columns."""
        left_result = self._process_query(union_expr.left, outside_sources, withs)
        right_result = self._process_query(union_expr.right, outside_sources, withs)

        # Combine used_fields
        used_fields = set()
        for f in left_result["used_fields"]:
            used_fields.add(self._freeze_field(f) if isinstance(f, dict) else f)
        for f in right_result["used_fields"]:
            used_fields.add(self._freeze_field(f) if isinstance(f, dict) else f)

        # Create composite returned_fields
        returned_fields = []
        left_fields = left_result["returned_fields"]
        right_fields = right_result["returned_fields"]

        for i in range(max(len(left_fields), len(right_fields))):
            left_field = left_fields[i] if i < len(left_fields) else None
            right_field = right_fields[i] if i < len(right_fields) else None

            if left_field:
                alias = left_field.get("alias") or left_field.get("column")
            elif right_field:
                alias = right_field.get("alias") or right_field.get("column")
            else:
                alias = None

            member_fields = []
            if left_field:
                member_fields.append(left_field)
            if right_field:
                member_fields.append(right_field)

            returned_fields.append({
                "type": "composite_field",
                "alias": alias,
                "member_fields": member_fields
            })

        all_errors = set()
        for e in left_result["errors"]:
            if isinstance(e, dict):
                all_errors.add(self._freeze_field(e))
            else:
                all_errors.add(e)
        for e in right_result["errors"]:
            if isinstance(e, dict):
                all_errors.add(self._freeze_field(e))
            else:
                all_errors.add(e)

        return {
            "used_fields": [self._unfreeze_field(f) for f in used_fields],
            "returned_fields": returned_fields,
            "errors": [self._unfreeze_field(e) for e in all_errors]
        }

    def _build_sources(self, select_expr, outside_sources, withs):
        """Build source list from FROM clause and JOINs.

        Note: Macaw processes JOINs first, then appends FROM at the end.
        This affects the order when expanding wildcards.
        """
        sources = []

        # Process JOINs first (matching Macaw's order)
        for join in select_expr.args.get("joins", []):
            source = self._process_source(join.this, outside_sources, withs)
            if source:
                sources.append(source)

        # Then append FROM clause at the end
        from_clause = select_expr.args.get("from_")
        if from_clause:
            source = self._process_source(from_clause.this, outside_sources, withs)
            if source:
                sources.append(source)

        return sources

    def _process_source(self, source_expr, outside_sources, withs):
        """Process a source (table, subquery, or CTE reference)."""
        # Check for table functions first (UDTF or any UDTF subclass like GenerateSeries)
        # Note: isinstance checks for subclasses too, so exp.UDTF catches GenerateSeries
        if isinstance(source_expr, exp.UDTF):
            # Table function (GENERATE_SERIES, etc.)
            alias = source_expr.alias
            return {
                "names": {"table_alias": alias} if alias else None,
                "returned_fields": [{"type": "unknown_columns"}],
                "used_fields": set(),
                "errors": set()
            }

        if isinstance(source_expr, exp.Table):
            table_name = source_expr.name
            table_alias = source_expr.alias

            # Check if it's a CTE reference
            if table_name in withs:
                cte_data = withs[table_name]
                cte_table_info = {"table": table_name}
                if table_alias:
                    cte_table_info["table_alias"] = table_alias
                cte_source = dict(cte_data)
                cte_source["names"] = cte_table_info
                return cte_source

            # A table with empty name but an alias might be a table function result
            # that SQLGlot didn't recognize. Treat as unknown_columns.
            if not table_name and table_alias:
                return {
                    "names": {"table_alias": table_alias},
                    "returned_fields": [{"type": "unknown_columns"}],
                    "used_fields": set(),
                    "errors": set()
                }

            # A table with empty name whose 'this' is a function is a table function
            # that SQLGlot parsed as Table instead of UDTF (e.g., my_function(1, 100))
            if not table_name and isinstance(source_expr.this, exp.Func):
                alias = source_expr.alias
                return {
                    "names": {"table_alias": alias} if alias else None,
                    "returned_fields": [{"type": "unknown_columns"}],
                    "used_fields": set(),
                    "errors": set()
                }

            # Real table
            table_info = {"table": table_name}
            if source_expr.db:
                table_info["schema"] = source_expr.db
            if source_expr.catalog:
                table_info["database"] = source_expr.catalog
            if table_alias:
                table_info["table_alias"] = table_alias

            return {
                "names": table_info,
                "returned_fields": [{"type": "all_columns", "table": table_info}],
                "used_fields": set(),
                "errors": set()
            }

        elif isinstance(source_expr, exp.Subquery):
            subquery_result = self._process_query(source_expr.this, outside_sources, withs)
            alias = source_expr.alias
            subquery_result["names"] = {"table_alias": alias} if alias else None
            return subquery_result

        return None

    def _find_returned_fields(self, expr, sources, withs):
        """Find returned fields from a SELECT expression."""
        # Handle aliases
        if isinstance(expr, exp.Alias):
            inner_results = self._find_returned_fields(expr.this, sources, withs)
            alias = expr.alias
            for result in inner_results:
                if "col" in result:
                    # Shallow-copy before overwriting alias — the same dict may
                    # be referenced as a source-column by other scopes. Mutating
                    # it replaces the inner alias (e.g. "datum") with the outer
                    # alias (e.g. "b"), breaking column resolution upstream.
                    result["col"] = dict(result["col"])
                    result["col"]["alias"] = alias
            return inner_results

        # Unqualified wildcard: SELECT *
        if isinstance(expr, exp.Star):
            results = []
            if sources and sources[0]:
                for source in sources[0]:
                    for field in source.get("returned_fields", []):
                        results.append({"col": field})
            return results

        # Column reference (including table.*)
        if isinstance(expr, exp.Column):
            column_name = expr.name
            table_ref = expr.table

            # Table wildcard: SELECT t.*
            if column_name == "*":
                if table_ref:
                    source = self._find_source({"table": table_ref}, sources)
                    if source:
                        return [{"col": field} for field in source.get("returned_fields", [])]
                    else:
                        return [{"errors": {self._missing_table_alias_error(table_ref)}}]
                return []

            # Regular column
            return self._get_column(sources, expr, return_table_matches=True)

        # Subquery in SELECT
        if isinstance(expr, exp.Subquery):
            subquery_result = self._process_query(expr.this, sources, withs)
            # Single-column subquery returns that column
            if subquery_result["returned_fields"]:
                return [{"col": subquery_result["returned_fields"][0]}]
            return []

        # Everything else is a custom field (function, case, binary expression, etc.)
        used_fields = []
        for result in self._find_used_fields(expr, sources, withs):
            if "col" in result:
                used_fields.append(result["col"])

        alias = expr.alias if hasattr(expr, "alias") and expr.alias else None
        return [{
            "col": {
                "type": "custom_field",
                "alias": alias,
                # Don't freeze - these go directly to returned_fields which isn't unfrozen
                "used_fields": used_fields
            }
        }]

    def _find_used_fields(self, expr, sources, withs):
        """Find fields used in an expression (WHERE, JOIN ON, etc.)."""
        if expr is None:
            return []

        # Column reference
        if isinstance(expr, exp.Column):
            column_name = expr.name
            table_ref = expr.table

            # Table wildcard: t.* - expand to actual fields from source
            if column_name == "*" and table_ref:
                source = self._find_source({"table": table_ref}, sources)
                if source:
                    # Expand wildcard to the actual fields from this source
                    # But skip all_columns and unknown_columns markers -
                    # they don't represent specific used columns
                    results = []
                    for field in source.get("returned_fields", []):
                        ftype = field.get("type")
                        if ftype not in ("all_columns", "unknown_columns"):
                            results.append({"col": field})
                    return results
                # Bad table ref - return empty, error is tracked in _find_returned_fields
                # Don't create a column entry for "*"
                return []

            return self._get_column(sources, expr, return_table_matches=False)

        # Star/wildcard - no used fields
        if isinstance(expr, exp.Star):
            return []

        # Subquery
        if isinstance(expr, exp.Subquery):
            subquery_result = self._process_query(expr.this, sources, withs)
            results = []
            for field in subquery_result["used_fields"]:
                results.append({"col": field})
            return results

        # SELECT in expression context
        if isinstance(expr, exp.Select):
            select_result = self._process_query(expr, sources, withs)
            results = []
            for field in select_result["used_fields"]:
                results.append({"col": field})
            return results

        # Alias - recurse into the aliased expression
        # Only propagate alias if the Alias directly wraps a Column.
        # For complex expressions (functions, etc.), the alias belongs to the
        # expression result, not to the columns used inside.
        if isinstance(expr, exp.Alias):
            results = self._find_used_fields(expr.this, sources, withs)
            # Only add alias if this Alias directly wraps a Column
            if isinstance(expr.this, exp.Column):
                alias = expr.alias
                for result in results:
                    if "col" in result:
                        result["col"]["alias"] = alias
            return results

        # Binary expressions (AND, OR, =, <, >, etc.)
        if isinstance(expr, exp.Binary):
            left = self._find_used_fields(expr.left, sources, withs)
            right = self._find_used_fields(expr.right, sources, withs)
            return left + right

        # Unary expressions (NOT, -, etc.)
        if isinstance(expr, exp.Unary):
            return self._find_used_fields(expr.this, sources, withs)

        # CASE expression
        if isinstance(expr, exp.Case):
            results = []
            # CASE <expr> WHEN...
            if expr.this:
                results.extend(self._find_used_fields(expr.this, sources, withs))
            # WHEN conditions and THEN values
            for ifs in expr.args.get("ifs", []):
                results.extend(self._find_used_fields(ifs.this, sources, withs))
                results.extend(self._find_used_fields(ifs.args.get("true"), sources, withs))
            # ELSE
            if expr.args.get("default"):
                results.extend(self._find_used_fields(expr.args["default"], sources, withs))
            return results

        # BETWEEN
        if isinstance(expr, exp.Between):
            results = []
            results.extend(self._find_used_fields(expr.this, sources, withs))
            results.extend(self._find_used_fields(expr.args.get("low"), sources, withs))
            results.extend(self._find_used_fields(expr.args.get("high"), sources, withs))
            return results

        # IS NULL / IS NOT NULL
        if isinstance(expr, (exp.Is,)):
            return self._find_used_fields(expr.this, sources, withs)

        # IN expression
        if isinstance(expr, exp.In):
            results = self._find_used_fields(expr.this, sources, withs)
            for item in expr.expressions:
                results.extend(self._find_used_fields(item, sources, withs))
            return results

        # EXISTS
        if isinstance(expr, exp.Exists):
            return self._find_used_fields(expr.this, sources, withs)

        # Functions
        if isinstance(expr, exp.Func):
            results = []
            for arg in expr.args.values():
                if isinstance(arg, list):
                    for item in arg:
                        results.extend(self._find_used_fields(item, sources, withs))
                elif isinstance(arg, exp.Expression):
                    results.extend(self._find_used_fields(arg, sources, withs))
            return results

        # Window functions
        if isinstance(expr, exp.Window):
            results = []
            results.extend(self._find_used_fields(expr.this, sources, withs))
            # PARTITION BY
            partition = expr.args.get("partition_by")
            if partition:
                for part in partition:
                    results.extend(self._find_used_fields(part, sources, withs))
            # ORDER BY within window
            order = expr.args.get("order")
            if order:
                results.extend(self._find_used_fields(order, sources, withs))
            return results

        # ORDER BY clause
        if isinstance(expr, exp.Order):
            results = []
            for ordered in expr.expressions:
                results.extend(self._find_used_fields(ordered.this, sources, withs))
            return results

        # GROUP BY clause
        if isinstance(expr, exp.Group):
            results = []
            for item in expr.expressions:
                results.extend(self._find_used_fields(item, sources, withs))
            return results

        # Ordered (for ORDER BY items)
        if isinstance(expr, exp.Ordered):
            return self._find_used_fields(expr.this, sources, withs)

        # Cast
        if isinstance(expr, exp.Cast):
            return self._find_used_fields(expr.this, sources, withs)

        # Paren (parenthesized expression)
        if isinstance(expr, exp.Paren):
            return self._find_used_fields(expr.this, sources, withs)

        # Interval, Literal, etc. - no columns
        if isinstance(expr, (exp.Literal, exp.Interval, exp.DataType, exp.Boolean)):
            return []

        # Identifier (column name without table) - treat as column
        if isinstance(expr, exp.Identifier):
            # Create a fake column to reuse column resolution
            fake_col = exp.Column(this=expr)
            return self._get_column(sources, fake_col, return_table_matches=False)

        # Fallback: try to walk children
        results = []
        for child in expr.iter_expressions():
            results.extend(self._find_used_fields(child, sources, withs))
        return results

    def _get_column(self, sources, column_expr, return_table_matches):
        """Get column reference with source resolution."""
        column_name = column_expr.name
        table_ref = column_expr.table

        # Find valid sources
        if table_ref:
            source = self._find_source({"table": table_ref}, sources)
            valid_sources = [[source]] if source else [[]]
        else:
            valid_sources = sources

        # Build source_columns (nested list of possible sources)
        # Pass through returned_fields from all sources (matching Macaw behavior).
        # This preserves lineage back to original tables through CTEs/subqueries.
        source_columns = []
        for scope_sources in valid_sources:
            if isinstance(scope_sources, list):
                scope_fields = []
                for source in scope_sources:
                    if source and self._source_might_have_column(source, column_name, table_ref):
                        returned_fields = source.get("returned_fields", [])
                        scope_fields.extend(returned_fields)
                if scope_fields:
                    source_columns.append(scope_fields)

        # Check for direct column match in source_columns (matching Macaw)
        # Search in (first source_columns), not in the raw returned_fields
        source_column = None
        if source_columns:
            for field in source_columns[0]:
                field_name = field.get("alias") or field.get("column")
                if field_name and field_name.lower() == column_name.lower():
                    source_column = field
                    break

        # Check for table alias match (SELECT o FROM (SELECT * FROM orders) AS o)
        if not source_column and not table_ref:
            for scope_sources in valid_sources:
                if isinstance(scope_sources, list):
                    for source in scope_sources:
                        if source:
                            names = source.get("names", {})
                            table_alias = names.get("table_alias") if names else None
                            table_name = names.get("table") if names else None
                            if table_alias and table_alias.lower() == column_name.lower():
                                if return_table_matches:
                                    return [{
                                        "col": {
                                            "type": "custom_field",
                                            "alias": column_name,
                                            # Don't freeze - goes directly to returned_fields
                                            "used_fields": list(source.get("returned_fields", []))
                                        }
                                    }]
                                else:
                                    # Table alias match but not returning table matches - empty result
                                    return []
                            if table_name and table_name.lower() == column_name.lower():
                                if return_table_matches:
                                    return [{
                                        "col": {
                                            "type": "custom_field",
                                            "alias": column_name,
                                            # Don't freeze - goes directly to returned_fields
                                            "used_fields": list(source.get("returned_fields", []))
                                        }
                                    }]
                                else:
                                    # Table name match but not returning table matches - empty result
                                    return []

        # Direct column match handling
        # The source_columns in single_column entries already point to the correct source.
        # For custom_field (computed columns like "0 AS level"), we need to create a
        # single_column reference pointing to the source (e.g., the CTE).
        if source_column:
            col_type = source_column.get("type")
            if col_type == "single_column":
                # For recursive CTE self-references (like h.id in recursive CTE),
                # create a CTE reference. For non-recursive CTEs, pass through the
                # matched column (which already has correct source_columns).
                if table_ref and not return_table_matches:
                    source = self._find_source({"table": table_ref}, valid_sources)
                    # Only create CTE reference for RECURSIVE CTEs
                    if source and source.get("is_recursive_cte"):
                        names = source.get("names") or {}
                        table_info = {"table": names.get("table", table_ref)}
                        if names.get("table_alias"):
                            table_info["table_alias"] = names["table_alias"]
                        return [{
                            "col": {
                                "type": "single_column",
                                "column": column_name,
                                "alias": None,
                                "source_columns": [[{"type": "all_columns", "table": table_info}]]
                            }
                        }]
                # For non-recursive CTEs and other cases: pass through matched column
                result_col = dict(source_column)
                # For unqualified reference with multiple scopes: use multi-level source_columns
                if not table_ref and len(source_columns) > 1:
                    result_col["source_columns"] = source_columns
                return [{"col": result_col}]
            elif col_type == "custom_field":
                # Custom field has no source_columns (it's a computed expression).
                # For recursive CTE self-references (like h.level in recursive CTE):
                #   Create single_column with CTE reference
                # For other CTE references (like m.month referencing non-recursive CTE):
                #   Pass through custom_field to preserve structure
                #
                # Detection: is_recursive_cte flag is set during CTE processing
                if table_ref:
                    source = self._find_source({"table": table_ref}, valid_sources)
                    if source and source.get("is_recursive_cte"):
                        names = source.get("names") or {}
                        table_info = {"table": names.get("table", table_ref)}
                        if names.get("table_alias"):
                            table_info["table_alias"] = names["table_alias"]
                        source_ref = [[{"type": "all_columns", "table": table_info}]]
                        return [{
                            "col": {
                                "type": "single_column",
                                "column": column_name,
                                "alias": None,
                                "source_columns": source_ref
                            }
                        }]
                # Copy before returning — callers may mutate the alias
                # (e.g. _find_returned_fields sets alias for outer SELECT AS),
                # and source_column is shared with the source's returned_fields.
                return [{"col": dict(source_column)}]
            # For composite_field, etc.: return as-is to preserve structure
            else:
                return [{"col": source_column}]

        # No direct match - return single_column with source_columns
        errors = set()
        if not source_columns or not any(source_columns):
            # No potential sources found
            if table_ref:
                # Table qualifier doesn't exist - return error only, no col spec
                # (Returning a col with empty source_columns would cause Clojure's
                # resolve-field to generate a redundant missing-column error)
                return [{"errors": {self._missing_table_alias_error(table_ref)}}]
            else:
                errors.add(self._missing_column_error(column_name))

        return [{
            "col": {
                "type": "single_column",
                "column": column_name,
                "alias": None,
                "source_columns": source_columns
            },
            "errors": errors
        }]

    def _find_source(self, search, sources):
        """Find a source matching the search criteria."""
        for scope_sources in sources:
            if isinstance(scope_sources, list):
                for source in scope_sources:
                    if source and self._table_matches(search, source.get("names", {})):
                        return source
        return None

    def _table_matches(self, search, table_names):
        """Check if search criteria match table names."""
        if not table_names:
            return False
        search_table = search.get("table")
        search_schema = search.get("schema")
        search_database = search.get("database")

        # Match by alias first (if no schema/database in search)
        if search_table and not search_schema and not search_database:
            if table_names.get("table_alias") == search_table:
                return True

        # Match by table/schema/database
        if search_table and search_table != table_names.get("table"):
            return False
        if search_schema and search_schema != table_names.get("schema"):
            return False
        if search_database and search_database != table_names.get("database"):
            return False

        return search_table == table_names.get("table")

    def _source_might_have_column(self, source, column_name, table_ref):
        """Check if a source might contain a column."""
        if not source:
            return False

        # If table ref specified, check if it matches (case-insensitive since
        # SQLGlot may lowercase identifiers)
        if table_ref:
            names = source.get("names", {})
            if names:
                table_alias = names.get("table_alias")
                table_name = names.get("table")
                if table_alias and table_alias.lower() == table_ref.lower():
                    return True
                if table_name and table_name.lower() == table_ref.lower():
                    return True
            return False

        # No table ref - source might have column
        return True

    def _freeze_field(self, field):
        """Convert a field dict to a hashable frozenset for use in sets."""
        if field is None:
            return None
        if isinstance(field, (str, int, float, bool)):
            return field
        if isinstance(field, frozenset):
            return field
        if isinstance(field, set):
            return frozenset(self._freeze_field(item) for item in field)
        if isinstance(field, (list, tuple)):
            return tuple(self._freeze_field(item) for item in field)
        if isinstance(field, dict):
            items = []
            for k, v in field.items():
                items.append((k, self._freeze_field(v)))
            return frozenset(items)
        return field

    def _unfreeze_field(self, frozen):
        """Convert a frozen field back to a dict."""
        if frozen is None:
            return None
        if isinstance(frozen, (str, int, float, bool)):
            return frozen

        # frozenset of tuples -> dict
        if isinstance(frozen, frozenset):
            # Check if it looks like a dict (frozenset of 2-tuples)
            try:
                items = list(frozen)
                if items and all(isinstance(item, tuple) and len(item) == 2 for item in items):
                    # It's a frozen dict
                    result = {}
                    for k, v in items:
                        result[k] = self._unfreeze_field(v)
                    return result
                else:
                    # It's a frozen set of items
                    return [self._unfreeze_field(item) for item in frozen]
            except:
                return [self._unfreeze_field(item) for item in frozen]

        # tuple -> list
        if isinstance(frozen, tuple):
            return [self._unfreeze_field(item) for item in frozen]

        # list -> list (recursively unfreeze items)
        if isinstance(frozen, list):
            return [self._unfreeze_field(item) for item in frozen]

        # dict -> dict (recursively unfreeze values)
        if isinstance(frozen, dict):
            return {k: self._unfreeze_field(v) for k, v in frozen.items()}

        return frozen

    def _syntax_error(self):
        """Create a syntax error."""
        return frozenset([("type", "syntax_error")])

    def _missing_table_alias_error(self, table_name):
        """Create a missing table alias error."""
        return frozenset([("type", "missing_table_alias"), ("table", table_name)])

    def _missing_column_error(self, column_name):
        """Create a missing column error."""
        return frozenset([("type", "missing_column"), ("column", column_name)])

#############################################################################
# Transpile sql
#############################################################################

_METABASE_TEMPLATE_RE = re.compile(r"\{\{|\[\[")

def has_metabase_templates(sql: str) -> bool:
    """Detect if SQL contains any Metabase template syntax.

    Metabase templates include:
    - {{variable}} - basic variables
    - {{#model_id}} - model references
    - {{snippet: name}} - SQL snippets
    - [[optional clause]] - optional filter clauses

    We skip validation for templated queries because accurately normalizing
    all template types for parsing is brittle. For example, model references
    can appear as subqueries in CTEs or EXISTS clauses, not just FROM clauses.
    """
    return bool(_METABASE_TEMPLATE_RE.search(sql))

# Reserved words that cannot appear as bare identifiers in the target dialect, for the
# dialects whose sqlglot generator ships an empty RESERVED_KEYWORDS set. Sourced from the
# vendors' reserved-word documentation. Dialects absent here fall back to sqlglot's own
# per-dialect generator set; where that is empty too (e.g. SQLite, whose double-quote
# quirk turns an unresolved quoted identifier into a string literal), identifiers pass
# through untouched and the warehouse reports its own error.
_DIALECT_RESERVED = {
    'postgres': frozenset("""
        all analyse analyze and any array as asc asymmetric authorization binary both case
        cast check collate collation column concurrently constraint create cross
        current_catalog current_date current_role current_schema current_time
        current_timestamp current_user default deferrable desc distinct do else end except
        false fetch for foreign freeze from full grant group having ilike in initially
        inner intersect into is isnull join lateral leading left like limit localtime
        localtimestamp natural not notnull null offset on only or order outer overlaps
        placing primary references returning right select session_user similar some
        symmetric system_user table tablesample then to trailing true union unique user
        using variadic verbose when where window with
    """.split()),
    'snowflake': frozenset("""
        account all alter and any as between by case cast check column connect connection
        constraint create cross current current_date current_time current_timestamp
        current_user database delete distinct drop else exists false following for from
        full grant group gscluster having ilike in increment inner insert intersect into
        is issue join lateral left like localtime localtimestamp minus natural not null
        of on or order organization qualify regexp revoke right rlike row rows sample
        schema select set some start table tablesample then to trigger true try_cast
        union unique update using values view when whenever where with
    """.split()),
    'oracle': frozenset("""
        access add all alter and any as asc audit between by char check cluster column
        column_value comment compress connect create current date decimal default delete
        desc distinct drop else exclusive exists file float for from grant group having
        identified immediate in increment index initial insert integer intersect into is
        level like lock long maxextents minus mlslabel mode modify nested_table_id noaudit
        nocompress not nowait null number of offline on online option or order pctfree
        prior public raw rename resource revoke row rowid rownum rows select session set
        share size smallint start successful synonym sysdate table then to trigger uid
        union unique update user validate values varchar varchar2 view whenever where with
    """.split()),
}

def _quote_reserved_identifiers(expression, dialect):
    """Quote identifiers that collide with the target dialect's reserved words.

    The identifier is folded first, the way the server would have folded the bare name,
    so the quoting never changes what it resolves to; it only stops the server from
    reading it as a keyword. Only words reserved in the specific target dialect are
    touched: a generic list would misfire, e.g. quoting `user` on SQLite, where USER is
    not a keyword and the quoted form of a nonexistent column silently becomes a string
    literal instead of an error.
    """
    # `dialect` may carry options (`postgres, normalization_strategy=lowercase`), so key off the class.
    reserved = (dialect.generator_class.RESERVED_KEYWORDS
                | _DIALECT_RESERVED.get(type(dialect).__name__.lower(), frozenset()))
    if reserved:
        for ident in expression.find_all(exp.Identifier):
            if not ident.quoted and ident.name.lower() in reserved:
                normalize_identifiers(ident, dialect=dialect)
                ident.set('quoted', True)
    return expression

def transpile_sql(sql: str, from_dialect: str = None, to_dialect: str = None):
    """Transpile sql string from one dialect to another.

    Identifiers keep the quoting they were written with: an unquoted identifier stays
    unquoted, so the database folds it exactly as it would have folded the input.
    Quoting everything (identify=True) would instead freeze the written casing, which
    breaks on dialects that fold unquoted identifiers (Snowflake uppercases, Postgres
    lowercases). The tradeoff runs the other way for objects created with quoted
    mixed-case names (ORMs emit CREATE TABLE "Orders"): those only resolve when the
    model also writes them quoted, since the bare name folds away from the stored one.
    The one exception to pass-through is an identifier that collides with the target
    dialect's reserved words: it is quoted, folded first so the quoting cannot change
    what it resolves to.

    Args:
        sql: SQL query string
        from_dialect: source sql dialect
        to_dialect: target sql dialect

    Returns:
        JSON string with keys transpiled_sql and status on success.
        On failure the object contains keys status and error_message, and reason
        'multiple_statements' when the SQL holds more than one statement.
    """
    result = {}
    if has_metabase_templates(sql):
        result['transpiled_sql'] = sql
        result['status'] = 'skipped'
        result['reason'] = 'contains_templates'
    elif not from_dialect or not to_dialect:
        result['transpiled_sql'] = sql
        result['status'] = 'skipped'
        result['reason'] = 'missing_dialect'
    else:
        try:
            write = sqlglot.Dialect.get_or_raise(to_dialect)
            expressions = _nonempty_statements(sqlglot.parse(sql, read=from_dialect))

            if len(expressions) > 1:
                result['status'] = 'error'
                result['reason'] = 'multiple_statements'
                result['error_message'] = 'Multiple SQL statements are not supported. Please provide a single query.'
            else:
                ast = _quote_reserved_identifiers(expressions[0], write)
                result['transpiled_sql'] = write.generate(ast, copy=False, pretty=True)
                result['status'] = 'success'
        except Exception as e:
            result['status'] = 'error'
            result['error_message'] = e.args[0]

    return json.dumps(result)

def _split_placeholder_casts(sql: str, dialect: str = None) -> str:
    """sqlglot's tokenizer treats `?::` as a single token in every dialect, but only Databricks'
    parser consumes it (the `expr?::type` try-cast operator). So a JDBC parameter followed by a
    cast (e.g. `select ?::text`) gets treated as this single token and fails to be parsed in every
    other dialect. To work around this we rewrite `?::` to `? ::` outside Databricks (#81373).
    """
    if dialect == "databricks" or "?::" not in sql:
        return sql
    try:
        tokens = sqlglot.tokenize(sql, read=dialect)
    except Exception:
        return sql
    # Insert right-to-left so earlier token offsets stay valid.
    for tok in reversed(tokens):
        if tok.token_type == sqlglot.TokenType.QDCOLON:
            sql = sql[: tok.start + 1] + " " + sql[tok.start + 1 :]
    return sql


# Nodes that write, lock, or run something other than a query. A SELECT can hold some of these: `SELECT ... INTO`
# creates a table, `FOR UPDATE`/`FOR SHARE` take row locks, and Postgres lets a CTE body be a DELETE ... RETURNING.
# Spark and Hive's `SELECT TRANSFORM (...) USING '<command>'` pipes rows through a program on the cluster.
_NOT_READ_ONLY_NODES = (
    exp.DML, exp.DDL, exp.Into, exp.Lock, exp.Command, exp.Set, exp.Grant, exp.Revoke, exp.Drop, exp.Alter,
    exp.TruncateTable, exp.Transaction, exp.Commit, exp.Rollback, exp.Use, exp.Execute, exp.LoadData, exp.Kill,
    exp.Pragma, exp.Cache, exp.Uncache, exp.Refresh, exp.Analyze, exp.NextValueFor, exp.QueryTransform,
)

# Writes a SELECT can make through a built-in function. Advancing a sequence is one: sqlglot parses only the
# SQL-standard `NEXT VALUE FOR` as its own node; Postgres and Redshift spell it as a function, Oracle and Snowflake as
# a `.NEXTVAL` pseudo-column, and Snowflake also as the table function `TABLE(GETNEXTVAL(seq))`. Postgres large objects
# are another, and any role can create one by default.
_WRITE_FUNCTIONS = frozenset(
    {
        # sequences
        "nextval", "setval", "getnextval",
        # Postgres large objects
        "lo_creat", "lo_create", "lo_from_bytea", "lo_put", "lowrite", "lo_truncate", "lo_truncate64", "lo_unlink",
        "lo_import", "lo_export",
    }
)

# Built-in functions that reach past the query that calls them: they take a lock that can outlive it, change the
# session's settings, signal or stop another session, hold the connection waiting, or act outside the database.
_SESSION_EFFECT_FUNCTIONS = frozenset(
    {
        # Postgres advisory locks
        "pg_advisory_lock", "pg_advisory_lock_shared", "pg_try_advisory_lock", "pg_try_advisory_lock_shared",
        "pg_advisory_xact_lock", "pg_advisory_xact_lock_shared", "pg_try_advisory_xact_lock",
        "pg_try_advisory_xact_lock_shared", "pg_advisory_unlock", "pg_advisory_unlock_shared",
        "pg_advisory_unlock_all",
        # MySQL named locks
        "get_lock", "release_lock", "release_all_locks",
        # session settings and signals
        "set_config", "pg_notify", "pg_terminate_backend", "pg_cancel_backend", "pg_reload_conf",
        # Postgres dblink: a named connection stays open on the session
        "dblink_connect", "dblink_connect_u",
        # Snowflake: stop another session's work
        "system$cancel_query", "system$cancel_all_queries", "system$abort_session", "system$abort_transaction",
        # waiting
        "pg_sleep", "pg_sleep_for", "pg_sleep_until", "sleep", "benchmark", "sleepeachrow", "system$wait",
        "master_pos_wait", "source_pos_wait", "wait_for_executed_gtid_set", "wait_until_sql_thread_after_gtids",
        # running a program, Java code or a request outside the database
        "executable", "reflect", "java_method", "http_request", "system$send_email",
    }
)


def _function_name(node: exp.Expression):
    """The lower-case name of the function `node` calls, or None when it is not a function call."""
    if isinstance(node, exp.Anonymous):
        return node.name.lower()
    # None of the names in `_SESSION_EFFECT_FUNCTIONS` has a node of its own today. This keeps the list working if a
    # sqlglot upgrade gives one of them its own node.
    if isinstance(node, exp.Func):
        return node.sql_name().lower()
    return None


def _session_effect_function(stmt: exp.Expression):
    """The name of the first function in `stmt` that is one of `_SESSION_EFFECT_FUNCTIONS`, or None."""
    for node in stmt.walk():
        name = _function_name(node)
        if name in _SESSION_EFFECT_FUNCTIONS:
            return name
    return None


# Functions that take a SQL string and run it. The parser reads that string as an opaque literal, so a write, a lock,
# or a session change hidden inside it escapes the checks above: `query_to_xml('SELECT pg_advisory_lock(1)')` and
# `dblink_exec(conn, 'DELETE ...')` both read as a plain SELECT. The wrapper is refused whatever the string holds, so
# the string is never trusted. These names are distinctive, so matching across dialects costs no real query. Oracle's
# package functions (`dbms_xmlgen.getxml`, `utl_http.request`) are the same hazard but collapse to a bare name that
# could collide with an innocent column function, so they are left to the connection-level work instead.
_SQL_EXECUTING_FUNCTIONS = frozenset(
    {
        # Postgres query-to-xml family
        "query_to_xml", "query_to_xmlschema", "query_to_xml_and_xmlschema", "cursor_to_xml", "cursor_to_xmlschema",
        # Postgres full-text and tablefunc helpers that run a passed query
        "ts_stat", "ts_rewrite", "crosstab", "crosstab2", "crosstab3", "crosstab4", "connectby",
        # Postgres dblink
        "dblink", "dblink_exec", "dblink_send_query", "dblink_fetch", "dblink_open",
        # SQL Server linked-server and ad hoc access
        "openquery", "openrowset", "opendatasource",
        # BigQuery federated query
        "external_query",
        # Snowflake: run a SQL string as a table function
        "to_query",
    }
)


def _sql_executing_function(stmt: exp.Expression):
    """The name of the first function in `stmt` that is one of `_SQL_EXECUTING_FUNCTIONS`, or None."""
    for node in stmt.walk():
        name = _function_name(node)
        if name in _SQL_EXECUTING_FUNCTIONS:
            return name
        # Trino passes a query through to a connector's database with `TABLE(catalog.system.query(query => '...'))`.
        # The name `query` alone is too common to refuse, so it counts only under a `system` schema.
        if (
            isinstance(node, exp.Dot)
            and node.this.name.lower() == "system"
            and _function_name(node.expression) == "query"
        ):
            return "system.query"
    return None


def _dynamic_function_call(stmt: exp.Expression) -> bool:
    """Whether `stmt` calls a function named by Snowflake's `IDENTIFIER(...)`, as in `IDENTIFIER('f')(1)`."""
    # Name checks never see this name, a string or a variable, so the call is refused whatever it names.
    # Only the call form has an `expressions` arg, which holds the call's arguments, possibly none.
    # A table or column name such as `IDENTIFIER('t')` has no such arg.
    return any("expressions" in node.args for node in stmt.find_all(exp.DynamicIdentifier))


# SQL Server table hints that take update or exclusive locks, or hold shared ones to the end of the transaction.
# `NOLOCK`, `INDEX(...)` and the rest only steer how a plain read runs.
_LOCKING_TABLE_HINTS = frozenset(
    {"UPDLOCK", "XLOCK", "TABLOCK", "TABLOCKX", "HOLDLOCK", "SERIALIZABLE", "REPEATABLEREAD"}
)


def _writes_or_locks(node: exp.Expression) -> bool:
    if isinstance(node, _NOT_READ_ONLY_NODES):
        return True
    if isinstance(node, exp.Anonymous):
        return node.name.lower() in _WRITE_FUNCTIONS
    # MySQL assigns a user variable inside a SELECT with `@x := ...`, and the value outlives the query on a pooled
    # connection. A bare name on the left is a named argument instead, as in DuckDB and Postgres, and changes nothing.
    # The variable is searched for, not just checked for on top: a dotted name, `@x.y`, parses as a `Dot` around it.
    if isinstance(node, exp.PropertyEQ):
        return node.this.find(exp.Parameter) is not None
    if isinstance(node, exp.Column):
        return bool(node.table) and node.name.lower() == "nextval"
    if isinstance(node, exp.WithTableHint):
        return any(hint.name.upper() in _LOCKING_TABLE_HINTS for hint in node.expressions)
    # SQL Server still honours a hint written without WITH, `FROM t (TABLOCKX)`, which parses as a call to a
    # table-valued function named `t`.
    if isinstance(node, exp.Table) and isinstance(node.this, exp.Anonymous):
        return any(
            isinstance(arg, exp.Column) and not arg.table and arg.name.upper() in _LOCKING_TABLE_HINTS
            for arg in node.this.expressions
        )
    return False


# Any other function with side effects, a user-defined one included, passes this check: `_SESSION_EFFECT_FUNCTIONS`
# names the built-in ones known to matter, and no list of names can be complete. Grants on the database credential
# are what keep such a function from writing. The read-only flag on the QP's connection does not on every driver:
# the Postgres driver applies it only to a transaction, and the QP runs a read under autocommit.
def _read_only(stmt: exp.Expression) -> bool:
    return not any(_writes_or_locks(node) for node in stmt.walk())


# Words that start a T-SQL statement. SQL Server ends a SELECT at one of them without a semicolon, while sqlglot
# reads a bare one as a table alias: `SELECT 1 FROM t EXEC('...')` parses as one SELECT and runs as two statements.
# All are reserved words there, so a query can only use one as a name inside brackets or quotes.
# `MERGE`, `FETCH` and `USE` are left out: they also appear in join hints, `OFFSET ... FETCH` and `USE HINT`.
_TSQL_STATEMENT_WORDS = frozenset(
    {
        "ALTER", "BACKUP", "BEGIN", "BULK", "CHECKPOINT", "CLOSE", "COMMIT", "CREATE", "DBCC", "DEALLOCATE",
        "DECLARE", "DELETE", "DENY", "DROP", "EXEC", "EXECUTE", "GOTO", "GRANT", "INSERT", "KILL", "OPEN", "PRINT",
        "RAISERROR", "READTEXT", "RECONFIGURE", "RESTORE", "REVERT", "REVOKE", "ROLLBACK", "SAVE", "SET", "SHUTDOWN",
        "THROW", "TRUNCATE", "UPDATE", "UPDATETEXT", "WAITFOR", "WRITETEXT",
    }
)

# Dialects whose server runs the body of a `/*! ... */` comment as SQL, and reads `--` as a comment only when
# whitespace follows it.
_MYSQL_FAMILY_DIALECTS = frozenset({"mysql", "mariadb", "singlestore", "starrocks", "doris", "tidb"})


def _hidden_sql(sql: str, dialect: str, select: bool):
    """`(reason, detail)` when `sql` holds text its database would run and sqlglot would not parse as a statement of
    its own, else None.

    The MySQL marks are looked for in the raw text, string literals included. Finding where a literal ends would need
    the parser again, and MySQL's `NO_BACKSLASH_ESCAPES` mode ends one where sqlglot does not: after a backslash,
    sqlglot reads a quote as part of the literal and MySQL in that mode reads it as the literal's end. A backslash
    before a quote is refused for that reason, since everything after it may be SQL the parser took for text.

    A `U&"..."` identifier is refused in every dialect. Postgres reads its escapes, so `U&"pg_\\0073leep"` names
    `pg_sleep`, and sqlglot keeps them, so the function checks above never see the name. Like the MySQL marks, it is
    looked for in the raw text.

    The T-SQL statement words are looked for only when `select` says the statement is a SELECT, since a write
    statement starts with one.
    """
    if re.search(r"(?<![\w\$])[uU]&\"", sql) is not None:
        return ("unicode-identifier", None)
    if dialect == "tsql" and select:
        quoted = (sqlglot.TokenType.STRING, sqlglot.TokenType.NATIONAL_STRING, sqlglot.TokenType.IDENTIFIER)
        for tok in sqlglot.tokenize(sql, read=dialect):
            if tok.token_type not in quoted and tok.text.upper() in _TSQL_STATEMENT_WORDS:
                return ("statement-word", tok.text.upper())
    if dialect in _MYSQL_FAMILY_DIALECTS:
        if "/*!" in sql or "/*M!" in sql:
            return ("executable-comment", None)
        if re.search(r"--(?=\S)", sql) is not None:
            return ("bare-dash-comment", None)
        if re.search(r"\\['\"`]", sql) is not None:
            return ("backslash-quote", None)
    return None


def _unbracketed(stmt: exp.Expression) -> exp.Expression:
    """`stmt` without the brackets around the whole query: `(SELECT 1)` parses as a subquery with no alias."""
    while isinstance(stmt, exp.Subquery) and not stmt.alias:
        stmt = stmt.this
    return stmt


def _statement_reason(stmt: exp.Expression, sql: str, dialect: str):
    """`(reason, detail)` for why `stmt`, parsed from `sql`, fails the checks every statement type shares, else None."""
    function = _session_effect_function(stmt)
    if function is not None:
        return ("session-function", function)
    executor = _sql_executing_function(stmt)
    if executor is not None:
        return ("sql-executing-function", executor)
    if _dynamic_function_call(stmt):
        return ("dynamic-function-call", None)
    return _hidden_sql(sql, dialect, isinstance(_unbracketed(stmt), (exp.Select, exp.SetOperation)))


def _not_read_only_reason(stmts, sql: str, dialect: str):
    """`(reason, detail)` for why `stmts`, parsed from `sql`, are not one read-only SELECT, else None."""
    if not stmts:
        return ("not-a-select", None)
    if len(stmts) != 1:
        return ("multiple-statements", None)
    if not isinstance(_unbracketed(stmts[0]), (exp.Select, exp.SetOperation)):
        return ("not-a-select", None)
    if not _read_only(stmts[0]):
        return ("writes-or-locks", None)
    return _statement_reason(stmts[0], sql, dialect)


def is_single_stmt_of_type(sql: str, stmt_type: str = "read", dialect: str = None) -> str:
    """Validates that a query is a single read statement (SELECT) or a single write statement (INSERT, UPDATE, DELETE)
    and returns the query reconstructed from the parsed AST.

    Every mode applies the checks the statement types share.
    `stmt_type` "read-only" is stricter than "read": the SELECT must also hold nothing that writes or locks anywhere in
    its tree, and statements holding only a comment after the last semicolon are not counted. When the statement is
    refused for what it holds, `reason` says why, with `reason_detail` for the reasons that have one.
    """
    result = {"is_single_stmt?": False, "allowed_stmt_type?": False}
    try:
        stmts = sqlglot.parse(_split_placeholder_casts(sql, dialect), read=dialect)
        allowed_types = (exp.Select, exp.SetOperation)
        if stmt_type == "read-only":
            stmts = _nonempty_statements(stmts)
        elif stmt_type != "read":
            allowed_types = (exp.Update, exp.Insert, exp.Delete)
        if stmt_type == "read-only":
            problem = _not_read_only_reason(stmts, sql, dialect)
        elif len(stmts) == 1:
            problem = _statement_reason(stmts[0], sql, dialect)
        else:
            problem = None
        if problem is not None:
            result["reason"], result["reason_detail"] = problem
        if len(stmts) == 1:
            result["is_single_stmt?"] = True
            if isinstance(_unbracketed(stmts[0]), allowed_types) and problem is None:
                result["allowed_stmt_type?"] = True
            result["sql"] = stmts[0].sql(dialect=dialect) if dialect else stmts[0].sql()
    except Exception as e:
        result["error"] = str(e)
    if stmt_type == "read-only" and "error" in result:
        result["reason"] = "unparseable"
    return json.dumps(result)