package gudusoft.gsqlparser.lineage.v2.producer;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;

import gudusoft.gsqlparser.EDbVendor;
import gudusoft.gsqlparser.EExpressionType;
import gudusoft.gsqlparser.EJoinType;
import gudusoft.gsqlparser.ESetOperatorType;
import gudusoft.gsqlparser.ETableSource;
import gudusoft.gsqlparser.ETokenType;
import gudusoft.gsqlparser.lineage.v2.shape.TDb2ReturnStmt;
import gudusoft.gsqlparser.lineage.v2.shape.TMssqlReturn;
import gudusoft.gsqlparser.lineage.v2.shape.TReturnStmt;
import gudusoft.gsqlparser.lineage.v2.shape.TCreateFunctionStmt;
import gudusoft.gsqlparser.lineage.v2.shape.TDoExecuteBlockStmt;
import gudusoft.gsqlparser.lineage.v2.shape.TCommonBlock;
import gudusoft.gsqlparser.lineage.v2.shape.TMssqlBlock;
import gudusoft.gsqlparser.lineage.v2.shape.TStoredProcedureSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.ShapeBuilder;
import gudusoft.gsqlparser.lineage.v2.shape.TCTE;
import gudusoft.gsqlparser.lineage.v2.shape.TCaseExpression;
import gudusoft.gsqlparser.lineage.v2.shape.TCreateMaterializedSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TCreateTableOption;
import gudusoft.gsqlparser.lineage.v2.shape.TCreateTableSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TCreateViewSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TCustomSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TDeleteSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TExpression;
import gudusoft.gsqlparser.lineage.v2.shape.TExpressionList;
import gudusoft.gsqlparser.lineage.v2.shape.TFunctionCall;
import gudusoft.gsqlparser.lineage.v2.shape.TGroupBy;
import gudusoft.gsqlparser.lineage.v2.shape.THierarchical;
import gudusoft.gsqlparser.lineage.v2.shape.TInsertCondition;
import gudusoft.gsqlparser.lineage.v2.shape.TInsertIntoValue;
import gudusoft.gsqlparser.lineage.v2.shape.TInsertSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TJoin;
import gudusoft.gsqlparser.lineage.v2.shape.TJoinItem;
import gudusoft.gsqlparser.lineage.v2.shape.TJoinList;
import gudusoft.gsqlparser.lineage.v2.shape.TMergeSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TMergeWhenClause;
import gudusoft.gsqlparser.lineage.v2.shape.TMultiTarget;
import gudusoft.gsqlparser.lineage.v2.shape.TObjectName;
import gudusoft.gsqlparser.lineage.v2.shape.TOutputClause;
import gudusoft.gsqlparser.lineage.v2.shape.TPTNodeList;
import gudusoft.gsqlparser.lineage.v2.shape.TParseTreeNode;
import gudusoft.gsqlparser.lineage.v2.shape.TParseTreeVisitor;
import gudusoft.gsqlparser.lineage.v2.shape.TPivotClause;
import gudusoft.gsqlparser.lineage.v2.shape.TPivotInClause;
import gudusoft.gsqlparser.lineage.v2.shape.TReturningClause;
import gudusoft.gsqlparser.lineage.v2.shape.TSelectSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TSourceToken;
import gudusoft.gsqlparser.lineage.v2.shape.TLateralView;
import gudusoft.gsqlparser.lineage.v2.shape.TTable;
import gudusoft.gsqlparser.lineage.v2.shape.TUnnestClause;
import gudusoft.gsqlparser.lineage.v2.shape.TUpdateSqlStatement;
import gudusoft.gsqlparser.lineage.v2.shape.TWhenClauseItem;
import gudusoft.gsqlparser.lineage.v2.shape.TWindowDef;
import gudusoft.gsqlparser.lineage.v2.shape.TWindowDefinition;
import gudusoft.gsqlparser.lineage.v2.shape.TWindowSpecification;

/**
 * The {@code sqllr-path-1} paths of one statement ({@code lineage-spec/algorithms/path-v1.md}).
 *
 * <p>PATH-V1 anchors a reference at "the innermost step whose construct contains the first character of the
 * reference" (Section 6.1), so this index records, for every step the statement emits, the text range of its
 * construct and its path, and answers {@link #anchor} by the innermost range containing an offset. Steps are
 * assigned top down from the parse tree with explicit work queues: the clauses of a query block and the steps of a
 * data-changing statement have their parent fixed by Sections 3 and 4; expression steps ({@code FUNCTION_ARG},
 * {@code CASE_*}, {@code SUBQUERY}, {@code WINDOW}) take the innermost enclosing step of their clause as parent.
 * GSP's {@code TParseTreeNode.parent} is not used: it is set in only a few places.</p>
 *
 * <p>Forms PATH-V1 does not cover (Section 2, item 3) are recorded as uncovered ranges; a reference inside one has
 * no {@code sqllr-path-1} anchor ({@link Anchor#isCovered()} is false), and the producer publishes nothing anchored
 * there (plan 06, decision 1). A column reference that lands directly on a statement, query block or FROM-item step
 * sits in a clause or table modifier this index does not know (MODEL, MATCH_RECOGNIZE, SAMPLE, table hints, OUTPUT,
 * time travel): {@link #anchorColumn} reports it uncovered rather than inventing a path.</p>
 *
 * @since 4.2.17
 */
public final class PathIndex {

    /** The anchor of an offset: a path, or the fact that it lies in an uncovered form or outside the statement. */
    public static final class Anchor {
        private final String path;
        private final String uncoveredForm;

        Anchor(String path, String uncoveredForm) {
            this.path = path;
            this.uncoveredForm = uncoveredForm;
        }

        /** The {@code sqllr-path-1} path; {@code null} when not covered. */
        public String getPath() {
            return path;
        }

        public boolean isCovered() {
            return path != null;
        }

        /** The uncovered form that contains the offset, or {@code null}. */
        public String getUncoveredForm() {
            return uncoveredForm;
        }

        @Override
        public String toString() {
            return path != null ? path : "UNCOVERED " + uncoveredForm;
        }
    }

    /** One step's construct. */
    static final class Construct {
        final String code;
        int index;
        final int start;
        final int end;
        Construct parent;
        /** For expression steps: the clause step whose expressions are searched for the innermost parent. */
        final Construct scope;
        final int order;
        String path;
        int depth = -1;
        final List<Construct> textChildren = new ArrayList<Construct>();

        Construct(String code, int index, int start, int end, Construct parent, Construct scope, int order) {
            this.code = code;
            this.index = index;
            this.start = start;
            this.end = end;
            this.parent = parent;
            this.scope = scope;
            this.order = order;
        }

        boolean contains(int offset) {
            return start <= offset && offset < end;
        }

        boolean containsRange(Construct other) {
            return start <= other.start && other.end <= end;
        }

        int length() {
            return end - start;
        }
    }

    private static final class Uncovered {
        final String form;
        final int start;
        final int end;

        Uncovered(String form, int start, int end) {
            this.form = form;
            this.start = start;
            this.end = end;
        }
    }

    /** Steps on which a column reference never lands in a covered form. */
    private static final Set<String> NOT_A_COLUMN_ANCHOR = new HashSet<String>(Arrays.asList("SELECT", "INSERT",
            "UPDATE", "DELETE", "MERGE", "CREATE_TABLE", "CREATE_VIEW", "SUBQUERY", "CTE", "BRANCH", "SET_OP", "WITH",
            "FROM", "JOIN", "TARGET", "USING", "LATERAL"));

    /** Functions whose FIRST operand can be a bare date-part keyword (SQL Server, Snowflake, MySQL), not an operand. */
    private static final Set<String> FIRST_IS_DATE_PART = new HashSet<String>(Arrays.asList("DATEADD", "DATEDIFF",
            "DATEDIFF_BIG", "DATEPART", "DATENAME", "DATETRUNC", "DATE_BUCKET", "DATE_PART", "DATE_TRUNC",
            "TIMESTAMPADD", "TIMESTAMPDIFF", "TIMEADD", "TIMEDIFF", "TIME_SLICE"));

    /** Functions whose LAST operand can be a bare date-part keyword (BigQuery), not an operand. */
    private static final Set<String> LAST_IS_DATE_PART = new HashSet<String>(Arrays.asList("DATE_DIFF",
            "DATETIME_DIFF", "TIMESTAMP_DIFF", "TIME_DIFF", "DATE_TRUNC", "DATETIME_TRUNC", "TIMESTAMP_TRUNC",
            "TIME_TRUNC", "LAST_DAY"));

    private static final Set<String> DATE_PARTS = new HashSet<String>(Arrays.asList("YEAR", "YY", "YYYY", "YEARS",
            "QUARTER", "QQ", "Q", "QUARTERS", "MONTH", "MM", "M", "MONTHS", "DAYOFYEAR", "DY", "Y", "DAY", "DD", "D",
            "DAYS", "WEEK", "WK", "WW", "WEEKS", "WEEKDAY", "DW", "HOUR", "HH", "HOURS", "MINUTE", "MI", "N", "MINUTES",
            "SECOND", "SS", "S", "SECONDS", "MILLISECOND", "MS", "MILLISECONDS", "MICROSECOND", "MCS", "MICROSECONDS",
            "NANOSECOND", "NS", "NANOSECONDS", "ISO_WEEK", "ISOWK", "ISOWW", "ISOWEEK", "ISOYEAR", "TZOFFSET", "TZ",
            "DAYOFWEEK", "DAYOFMONTH", "EPOCH", "DATE", "TIME", "DATETIME", "TIMESTAMP", "CENTURY", "DECADE",
            "MILLENNIUM", "YEAROFWEEK", "YEAROFWEEKISO", "WEEKISO", "WEEKOFYEAR"));

    private final String statementStep;
    private final EDbVendor vendor;
    private final List<Construct> constructs = new ArrayList<Construct>();
    private final List<Uncovered> uncovered = new ArrayList<Uncovered>();
    private final Map<TSelectSqlStatement, Construct> blocks = new IdentityHashMap<TSelectSqlStatement, Construct>();
    private final SourceText text;
    private final List<Construct> roots = new ArrayList<Construct>();
    private final Deque<Object[]> work = new ArrayDeque<Object[]>();
    private Construct root;
    private boolean statementUncovered;
    private String statementUncoveredForm;

    private PathIndex(SourceText text, String statementStep, EDbVendor vendor) {
        this.text = text;
        this.statementStep = statementStep;
        this.vendor = vendor;
    }

    /** The statement step code of a statement, or {@code null} when PATH-V1 has none for it. */
    public static String statementStep(TCustomSqlStatement stmt) {
        if (stmt instanceof TSelectSqlStatement) {
            return "SELECT";
        }
        if (stmt instanceof TInsertSqlStatement) {
            return "INSERT";
        }
        if (stmt instanceof TUpdateSqlStatement) {
            return "UPDATE";
        }
        if (stmt instanceof TDeleteSqlStatement) {
            return "DELETE";
        }
        if (stmt instanceof TMergeSqlStatement) {
            return "MERGE";
        }
        if (stmt instanceof TCreateTableSqlStatement) {
            return "CREATE_TABLE";
        }
        if (stmt instanceof TCreateViewSqlStatement || stmt instanceof TCreateMaterializedSqlStatement) {
            return "CREATE_VIEW";
        }
        if (isRoutineDefinition(stmt)) {
            return "CREATE_ROUTINE"; // for the values it returns and the procedural parts of its body (Sections 3.5, 3.6)
        }
        if (isBlock(stmt)) {
            return "BLOCK"; // for the procedural parts of its body (Section 3.6)
        }
        if (Procedural.isStandaloneAssignment(stmt)) {
            return "ASSIGNMENT"; // SET @v = e, DECLARE @v INT = e outside every body (Section 3.6)
        }
        if (DocumentBuilder.isDynamicSite(stmt)) {
            return "EXECUTE"; // dynamic execution, with its arguments (the text and the values it binds, slice 12)
        }
        if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TCallStatement
                || stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TDb2CallStmt || isPlsqlCall(stmt)) {
            return "CALL"; // a call of a routine, with its arguments (plan 09 slice 12)
        }
        if (isProcedureExecute(stmt)) {
            return "EXECUTE"; // SQL Server EXEC of a named procedure, with its arguments (plan 09 slice 12)
        }
        return null;
    }

    /**
     * A PL/SQL procedure call written as a statement ({@code p(a, b);}, {@code pkg.p(x => 1);}), as opposed to the
     * DBMS_SQL.PARSE call that carries dynamic SQL text (a dynamic site).
     */
    static boolean isPlsqlCall(TCustomSqlStatement stmt) {
        return stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt
                && ((gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt) stmt).getExpr() != null
                && ((gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt) stmt).getExpr().getFunctionCall() != null
                && !DocumentBuilder.isDynamicSite(stmt);
    }

    /** A SQL Server EXEC of a named procedure, as opposed to an EXEC of dynamic SQL text (a dynamic site). */
    static boolean isProcedureExecute(TCustomSqlStatement stmt) {
        return stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TMssqlExecute
                && ((gudusoft.gsqlparser.lineage.v2.shape.TMssqlExecute) stmt).getModuleName() != null
                && !DocumentBuilder.isDynamicSite(stmt);
    }

    /**
     * The arguments of a call statement, in text order (plan 09 slice 12): of a SQL Server EXEC, each parameter's value
     * (a named one's value); of a CALL, each argument (a named one {@code p => v} as written, one operand).
     */
    static List<TExpression> callArguments(TCustomSqlStatement stmt) {
        List<TExpression> out = new ArrayList<TExpression>();
        if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TMssqlExecute) {
            gudusoft.gsqlparser.lineage.v2.shape.TExecParameterList list =
                    ((gudusoft.gsqlparser.lineage.v2.shape.TMssqlExecute) stmt).getParameters();
            for (int i = 0; list != null && i < list.size(); i++) {
                gudusoft.gsqlparser.lineage.v2.shape.TExecParameter x = list.getExecParameter(i);
                out.add(x == null ? null : x.getParameterValue());
            }
        } else if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TCallStatement) {
            TExpressionList args = ((gudusoft.gsqlparser.lineage.v2.shape.TCallStatement) stmt).getArgs();
            for (int i = 0; args != null && i < args.size(); i++) {
                out.add(args.getExpression(i));
            }
        } else if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TDb2CallStmt) {
            TExpressionList args = ((gudusoft.gsqlparser.lineage.v2.shape.TDb2CallStmt) stmt).getParameters();
            for (int i = 0; args != null && i < args.size(); i++) {
                out.add(args.getExpression(i));
            }
        } else if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TExecImmeStmt) {
            // EXECUTE IMMEDIATE text USING a, b: the text, then the bound values
            gudusoft.gsqlparser.lineage.v2.shape.TExecImmeStmt e = (gudusoft.gsqlparser.lineage.v2.shape.TExecImmeStmt) stmt;
            out.add(e.getDynamicStringExpr());
            for (int i = 0; e.getBindArguments() != null && i < e.getBindArguments().size(); i++) {
                gudusoft.gsqlparser.lineage.v2.shape.TBindArgument arg = e.getBindArguments().getBindArgument(i);
                out.add(arg == null ? null : arg.getBindArgumentExpr());
            }
        } else if (stmt instanceof gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt
                && ((gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt) stmt).getExpr() != null
                && ((gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt) stmt).getExpr().getFunctionCall() != null) {
            TExpressionList args = ((gudusoft.gsqlparser.lineage.v2.shape.TBasicStmt) stmt).getExpr().getFunctionCall()
                    .getArgs();
            for (int i = 0; args != null && i < args.size(); i++) {
                out.add(args.getExpression(i));
            }
        }
        return out;
    }

    /**
     * An anonymous block that runs where it stands (DECLARE ... BEGIN ... END, BEGIN ... END, PostgreSQL DO), or a
     * control-flow statement outside every body (SQL Server IF and WHILE of a batch).
     */
    static boolean isBlock(TCustomSqlStatement stmt) {
        // a control-flow statement is a statement of the document only outside every body (plan 09 slice 8): there it
        // runs where it stands, as a block does
        return stmt instanceof TMssqlBlock || stmt instanceof TCommonBlock || stmt instanceof TDoExecuteBlockStmt
                || Procedural.isControlBlock(stmt);
    }

    /** A routine definition (CREATE FUNCTION, CREATE PROCEDURE), not a block that runs where it stands. */
    static boolean isRoutineDefinition(TCustomSqlStatement stmt) {
        return stmt instanceof TStoredProcedureSqlStatement && !(stmt instanceof TMssqlBlock
                || stmt instanceof TCommonBlock || stmt instanceof TDoExecuteBlockStmt);
    }

    /**
     * The values a routine definition returns, in the order of their RETURN[k] steps (path-v1.md, Section 3.5): the
     * expression of a function whose body is one expression; otherwise each RETURN with a value of its own body in
     * text order, through blocks and control flow but not into a nested routine definition, and not a RETURN of a
     * query (RETURN QUERY, a RETURN whose value is a statement) or of nothing. Shared by the paths and the statement
     * graph, so both read one rule.
     */
    static List<TExpression> returnValues(TCustomSqlStatement routine) {
        return returnsValue(routine) ? valuesReturned(routine) : new ArrayList<TExpression>();
    }

    /**
     * Whether a routine definition can return a value (Codex S7 #12): a function, and the procedures whose RETURN
     * gives the caller a value: SQL Server and Sybase (the status), DB2 SQL PL (the status), Snowflake (RETURNS). The
     * database rejects a RETURN with a value in an Oracle, MySQL or PostgreSQL procedure and in a trigger.
     */
    static boolean returnsValue(TCustomSqlStatement routine) {
        if (!isRoutineDefinition(routine)) {
            return false;
        }
        // the parse's statement type names the definition (sstcreatefunction, sstmssqlcreateprocedure, ...)
        String type = String.valueOf(routine.sqlstatementtype).toLowerCase(Locale.ROOT);
        if (type.contains("trigger")) {
            return false;
        }
        if (type.contains("function")) {
            return true;
        }
        EDbVendor vendor = routine.dbvendor;
        return type.contains("procedure") && (vendor == EDbVendor.dbvmssql || vendor == EDbVendor.dbvazuresql
                || vendor == EDbVendor.dbvsybase || vendor == EDbVendor.dbvsybasease || vendor == EDbVendor.dbvdb2
                || vendor == EDbVendor.dbvsnowflake);
    }

    /** The value a RETURN statement gives, or null: none, or a query (RETURN QUERY, RETURN (SELECT ...), RETURN SELECT). */
    static TExpression returnedValue(TCustomSqlStatement ret) {
        TExpression value = rawReturnValue(ret);
        return value == null || returnsQuery(ret) || returnsNext(ret) || queryExecute(ret) ? null : value;
    }

    /** PL/pgSQL {@code RETURN NEXT}, with or without an operand: one row of the set a function returns. */
    static boolean returnsNext(TCustomSqlStatement ret) {
        if (!(ret instanceof TReturnStmt) || ret.getStartToken() == null) {
            return false;
        }
        TSourceToken next = nextSolidToken(ret.getStartToken());
        return next != null && "NEXT".equalsIgnoreCase(next.getAstext()); // non-identifier-compare: keyword
    }

    /**
     * PL/pgSQL {@code RETURN NEXT}, {@code RETURN QUERY} and {@code RETURN QUERY EXECUTE}: they add rows to the set the
     * function returns and execution goes on after them, so they are no jump (Codex 13f #2).
     */
    static boolean appendsRows(TCustomSqlStatement ret) {
        return returnsNext(ret) || returnsRows(ret) || queryExecute(ret);
    }

    /** PL/pgSQL {@code RETURN QUERY EXECUTE}: the rows of dynamic SQL text. */
    static boolean queryExecute(TCustomSqlStatement ret) {
        if (!(ret instanceof TReturnStmt) || ret.getStartToken() == null) {
            return false;
        }
        TSourceToken next = nextSolidToken(ret.getStartToken());
        TSourceToken after = next == null ? null : nextSolidToken(next);
        return next != null && after != null && "QUERY".equalsIgnoreCase(next.getAstext()) // non-identifier-compare: keyword
                && "EXECUTE".equalsIgnoreCase(after.getAstext()); // non-identifier-compare: keyword
    }

    /**
     * Whether a routine's {@code RETURN NEXT} is modelled (plan 09 slice 13f; path-v1 Section 3.5, fold-v1 Section 4.7,
     * item 8): a PostgreSQL-family function that returns a set of rows ({@code RETURNS TABLE}, {@code RETURNS SETOF}).
     */
    static boolean nextModelled(TCustomSqlStatement routine) {
        if (!(routine instanceof TCreateFunctionStmt) || !DocumentBuilder.postgresFamily(routine.dbvendor)) {
            return false;
        }
        TCreateFunctionStmt f = (TCreateFunctionStmt) routine;
        if (f.getReturnsType() == gudusoft.gsqlparser.EFunctionReturnsType.frtInlineTableValue) {
            return true;
        }
        return f.getReturnDataType() != null && DocumentBuilder.hasWord(f.getReturnDataType(), "SETOF");
    }

    /**
     * A RETURN of a table that path-v1 does not cover (Section 2, item 3), never a value: RETURN QUERY EXECUTE (Codex
     * 13d #3: its command text was taken for the value returned), and RETURN NEXT of a routine that does not return a
     * set of rows of the PostgreSQL family, which the database rejects; the form's words, or null.
     */
    static String unmodelledRowReturn(TCustomSqlStatement routine, TCustomSqlStatement ret) {
        if (queryExecute(ret)) {
            return "RETURN QUERY EXECUTE";
        }
        return returnsNext(ret) && !nextModelled(routine) ? "RETURN NEXT" : null;
    }

    /**
     * The steps RETURN[k] of a routine in order (path-v1 Section 3.5): {the RETURN statement, or null for an expression
     * body; its value, or null}: each RETURN with a value {@link #returnValues} lists, and each RETURN NEXT of a routine
     * that models it ({@link #nextModelled}), with its operand or without one (plan 09 slice 13f), in text order.
     */
    static List<Object[]> returnSteps(TCustomSqlStatement routine) {
        List<Object[]> out = new ArrayList<Object[]>();
        if (!returnsValue(routine)) {
            return out;
        }
        if (routine instanceof TCreateFunctionStmt && ((TCreateFunctionStmt) routine).getSqlExpression() != null) {
            out.add(new Object[] {null, ((TCreateFunctionStmt) routine).getSqlExpression()});
            return out;
        }
        boolean next = nextModelled(routine);
        for (TCustomSqlStatement ret : returnsOf(routine)) {
            if (returnsNext(ret) || queryExecute(ret)) {
                // RETURN NEXT (slice 13f); RETURN QUERY EXECUTE, whose command expression follows RETURN[k] and
                // whose literal text is a derived unit with RETURN[k] its site (slice 13g)
                if (next) {
                    out.add(new Object[] {ret, rawReturnValue(ret)});
                }
                continue;
            }
            TExpression value = valueOf(routine, ret);
            if (value != null) {
                out.add(new Object[] {ret, value});
            }
        }
        return out;
    }

    /** The expression a RETURN gives, a query included (not DB2's RETURN of a subquery), or null. */
    private static TExpression rawReturnValue(TCustomSqlStatement ret) {
        return ret instanceof TReturnStmt ? ((TReturnStmt) ret).getExpression()
                : ret instanceof TMssqlReturn ? ((TMssqlReturn) ret).getReturnExpr()
                : ret instanceof TDb2ReturnStmt && ((TDb2ReturnStmt) ret).getSubquery() == null
                ? ((TDb2ReturnStmt) ret).getReturnExpr() : null;
    }

    /**
     * PL/pgSQL {@code RETURN QUERY q} (not {@code RETURN QUERY EXECUTE}): the query's rows are rows of the set the
     * function returns (plan 09 slice 8).
     */
    static boolean returnsRows(TCustomSqlStatement ret) {
        if (!(ret instanceof TReturnStmt) || ret.getStartToken() == null) {
            return false;
        }
        TSourceToken next = nextSolidToken(ret.getStartToken());
        TSourceToken after = next == null ? null : nextSolidToken(next);
        return next != null && "QUERY".equalsIgnoreCase(next.getAstext()) // non-identifier-compare: keyword
                && (after == null || !"EXECUTE".equalsIgnoreCase(after.getAstext())); // non-identifier-compare: keyword
    }

    /**
     * Whether a RETURN of a query is one the paths and the graph model (plan 09 slice 8; path-v1.md, Section 3.5):
     * PL/pgSQL RETURN QUERY q, whose rows the function returns, and RETURN (SELECT ...) of a function that returns
     * one value, a scalar subquery; not an inline table function's RETURN SELECT, RETURN QUERY EXECUTE or DB2's RETURN
     * of a subquery.
     */
    static boolean modelledQueryReturn(TCustomSqlStatement routine, TCustomSqlStatement ret) {
        if (inlineTableQuery(routine, ret) != null) {
            return true; // an inline table function's RETURN of its query (Section 3.5)
        }
        if (!returnsQuery(ret) || rawReturnValue(ret) == null) {
            return false;
        }
        if (returnsRows(ret)) {
            return true;
        }
        if (ret instanceof TReturnStmt && "QUERY".equalsIgnoreCase( // non-identifier-compare: keyword
                String.valueOf(nextSolidToken(ret.getStartToken()) == null ? null
                        : nextSolidToken(ret.getStartToken()).getAstext()))) {
            return false; // RETURN QUERY EXECUTE: dynamic SQL
        }
        return routine instanceof TCreateFunctionStmt && ((TCreateFunctionStmt) routine).getReturnsType()
                != gudusoft.gsqlparser.EFunctionReturnsType.frtInlineTableValue;
    }

    /**
     * A SQL Server inline table function: {@code RETURNS TABLE AS RETURN SELECT ...} or {@code RETURN (SELECT ...)},
     * no declared return table (plan 09 phase C; path-v1 Section 3.5). Its RETURN's query gives the rows the
     * function returns, as PL/pgSQL's RETURN QUERY does.
     */
    static boolean inlineTable(TCustomSqlStatement routine) {
        if (!(routine instanceof TCreateFunctionStmt) || (routine.dbvendor != EDbVendor.dbvmssql
                && routine.dbvendor != EDbVendor.dbvazuresql)) {
            return false;
        }
        TCreateFunctionStmt f = (TCreateFunctionStmt) routine;
        return f.getReturnsType() == gudusoft.gsqlparser.EFunctionReturnsType.frtInlineTableValue
                && (f.getReturnTableDefinitions() == null || f.getReturnTableDefinitions().size() == 0);
    }

    /** The query an inline table function's RETURN gives (in parentheses or not), or null. */
    static TSelectSqlStatement inlineTableQuery(TCustomSqlStatement routine, TCustomSqlStatement ret) {
        if (!(ret instanceof TMssqlReturn) || !inlineTable(routine)) {
            return null;
        }
        TExpression value = ((TMssqlReturn) ret).getReturnExpr();
        if (value != null) {
            return queryOf(value);
        }
        return ret.getStatements() != null && ret.getStatements().size() == 1
                && ret.getStatements().get(0) instanceof TSelectSqlStatement
                ? (TSelectSqlStatement) ret.getStatements().get(0) : null;
    }

    /**
     * The RETURN of an inline table function written without parentheses ({@code RETURN SELECT ...}), whose query is
     * no expression: {RETURN, query}, or null. Its step is RETURN[0] with the query as SUBQUERY[0] below it.
     */
    static Object[] inlineBareReturn(TCustomSqlStatement routine) {
        if (!inlineTable(routine)) {
            return null;
        }
        for (TCustomSqlStatement ret : returnsOf(routine)) {
            if (((TMssqlReturn) ret).getReturnExpr() == null && inlineTableQuery(routine, ret) != null) {
                return new Object[] {ret, inlineTableQuery(routine, ret)};
            }
        }
        return null;
    }

    /** The RETURN statements of a routine's own body, in text order (whatever they return). */
    static List<TCustomSqlStatement> returnStatementsOf(TCustomSqlStatement routine) {
        return returnsOf(routine);
    }

    /** Whether a RETURN of the routine returns rows: PL/pgSQL RETURN QUERY, or an inline table function's query. */
    static boolean returnsRows(TCustomSqlStatement routine, TCustomSqlStatement ret) {
        return returnsRows(ret) || inlineTableQuery(routine, ret) != null;
    }

    /** The query an expression is as a whole (through parentheses), or null. */
    static TSelectSqlStatement queryOf(TExpression value) {
        TExpression e = value;
        while (e != null && e.getExpressionType() == EExpressionType.parenthesis_t && e.getLeftOperand() != null) {
            e = e.getLeftOperand();
        }
        return e != null && e.getExpressionType() == EExpressionType.subquery_t ? e.getSubQuery() : null;
    }

    /** The RETURN statement of each value {@link #returnValues} lists, in the same order (null for an expression body). */
    static List<TCustomSqlStatement> returnStatements(TCustomSqlStatement routine) {
        List<TCustomSqlStatement> out = new ArrayList<TCustomSqlStatement>();
        if (!returnsValue(routine)) {
            return out;
        }
        if (routine instanceof TCreateFunctionStmt && ((TCreateFunctionStmt) routine).getSqlExpression() != null) {
            out.add(null);
            return out;
        }
        for (TCustomSqlStatement ret : returnsOf(routine)) {
            if (valueOf(routine, ret) != null) {
                out.add(ret);
            }
        }
        return out;
    }

    /** The value one RETURN of the routine's own body gives in RETURN[k] (Section 3.5), or null. */
    private static TExpression valueOf(TCustomSqlStatement routine, TCustomSqlStatement ret) {
        return returnsQuery(ret) ? (modelledQueryReturn(routine, ret) ? rawReturnValue(ret) : null)
                : returnedValue(ret);
    }

    /**
     * Whether a RETURN returns a query (Codex S7 #4): RETURN QUERY, DB2 RETURN of a subquery, or a value that is a
     * query as a whole (an inline table function's RETURN SELECT, RETURN (SELECT ...)). A scalar expression with a
     * subquery inside it (COALESCE((SELECT ...), @p)) returns a value: its other inputs are read.
     */
    static boolean returnsQuery(TCustomSqlStatement ret) {
        if (ret instanceof TDb2ReturnStmt && ((TDb2ReturnStmt) ret).getSubquery() != null) {
            return true;
        }
        TExpression value = ret instanceof TReturnStmt ? ((TReturnStmt) ret).getExpression()
                : ret instanceof TMssqlReturn ? ((TMssqlReturn) ret).getReturnExpr() : null;
        if (value == null) {
            return ret.getStatements() != null && ret.getStatements().size() > 0;
        }
        while (value.getExpressionType() == EExpressionType.parenthesis_t && value.getLeftOperand() != null) {
            value = value.getLeftOperand();
        }
        return value.getExpressionType() == EExpressionType.subquery_t;
    }

    /** The values of the RETURNs of a routine's own body (or its expression body), whatever the routine may return. */
    static List<TExpression> valuesReturned(TCustomSqlStatement routine) {
        List<TExpression> out = new ArrayList<TExpression>();
        if (!isRoutineDefinition(routine)) {
            return out;
        }
        if (routine instanceof TCreateFunctionStmt && ((TCreateFunctionStmt) routine).getSqlExpression() != null) {
            out.add(((TCreateFunctionStmt) routine).getSqlExpression());
            return out;
        }
        for (TCustomSqlStatement ret : returnsOf(routine)) {
            TExpression value = valueOf(routine, ret);
            if (value != null) {
                out.add(value);
            }
        }
        return out;
    }

    /** The RETURN statements of a routine's own body in text order, through blocks and control flow. */
    private static List<TCustomSqlStatement> returnsOf(TCustomSqlStatement routine) {
        List<TCustomSqlStatement> found = new ArrayList<TCustomSqlStatement>();
        Deque<TCustomSqlStatement> pending = new ArrayDeque<TCustomSqlStatement>();
        pending.push(routine);
        while (!pending.isEmpty()) {
            TCustomSqlStatement container = pending.pop();
            for (int i = 0; container.getStatements() != null && i < container.getStatements().size(); i++) {
                TCustomSqlStatement child = container.getStatements().get(i);
                if (child == null || isRoutineDefinition(child)) {
                    continue; // a nested routine's RETURNs are its own
                }
                if (child instanceof TReturnStmt || child instanceof TMssqlReturn || child instanceof TDb2ReturnStmt) {
                    found.add(child);
                    continue;
                }
                pending.push(child);
            }
        }
        Collections.sort(found, new Comparator<TCustomSqlStatement>() {
            @Override
            public int compare(TCustomSqlStatement a, TCustomSqlStatement b) {
                return Integer.compare(a.getStartToken() == null ? 0 : a.getStartToken().posinlist,
                        b.getStartToken() == null ? 0 : b.getStartToken().posinlist);
            }
        });
        return found;
    }

    /**
     * The paths of one statement.
     *
     * @param stmt the statement
     * @param text the text of the source unit the statement's tokens are positioned in
     * @param step the statement step to use when {@link #statementStep} has none ({@code COPY}, {@code CALL},
     *             {@code EXECUTE}), or {@code null}: the statement then has no covered anchor at all
     */
    public static PathIndex build(TCustomSqlStatement stmt, SourceText text, String step) {
        String code = statementStep(stmt);
        PathIndex index = new PathIndex(text, code != null ? code : step, stmt.dbvendor);
        index.build(stmt, code != null);
        return index;
    }

    /**
     * The same for a statement of dynamic SQL text: the analysis moves its tokens' lines and columns to the site, so
     * positions come from the tokens' offsets into the text.
     */
    public static PathIndex buildByOffset(TCustomSqlStatement stmt, SourceText text) {
        String code = statementStep(stmt);
        PathIndex index = new PathIndex(text, code, stmt.dbvendor);
        index.byOffset = true;
        index.build(stmt, code != null);
        return index;
    }

    /** Positions from token offsets (a statement of dynamic SQL text) instead of lines and columns. */
    private boolean byOffset;

    private int tokenOffset(TSourceToken token) {
        if (byOffset) {
            return token.offset < 0 ? -1 : (int) token.offset;
        }
        return text.lexerOffset(token.lineNo, token.columnNo);
    }

    /** {@link #build(TCustomSqlStatement, SourceText, String)} with no fallback statement step. */
    public static PathIndex build(TCustomSqlStatement stmt, SourceText text) {
        return build(stmt, text, null);
    }

    /**
     * The paths of a statement a caller holds as a live parse tree (a parse with no analysis): the tree is projected
     * first (plan 09, slice 1b), and the live overloads of {@link #anchorColumn} and {@link #blockPath} take its nodes.
     */
    public static PathIndex build(gudusoft.gsqlparser.TCustomSqlStatement stmt, SourceText text) {
        ShapeBuilder projection =
                ShapeBuilder.projectKeepingLive(stmt);
        PathIndex index = build((TCustomSqlStatement) projection.shape().root(), text, null);
        index.projection = projection;
        return index;
    }

    /** The projection of a live tree {@link #build(gudusoft.gsqlparser.TCustomSqlStatement, SourceText)} took. */
    private ShapeBuilder projection;

    private <T> T mirrorOf(Object live, Class<T> type) {
        if (projection == null) {
            throw new IllegalStateException("the index was built from a projection, not from a live tree");
        }
        return type.cast(projection.mirrorOf(live));
    }

    /** The statement step path, such as {@code INSERT[0]}, or {@code null} when the statement has none. */
    public String getStatementPath() {
        return statementStep == null ? null : statementStep + "[0]";
    }

    /** The path of a query block (the {@code QUERY_BLOCK} scope path), or {@code null} when not indexed. */
    public String blockPath(TSelectSqlStatement block) {
        Construct c = blocks.get(block);
        return c == null ? null : c.path;
    }

    /** {@link #blockPath(TSelectSqlStatement)} of a live query block of the tree the index was built from. */
    public String blockPath(gudusoft.gsqlparser.stmt.TSelectSqlStatement block) {
        return blockPath(mirrorOf(block, TSelectSqlStatement.class));
    }

    /** Every indexed query block and its path, in no particular order. */
    public Map<TSelectSqlStatement, String> blockPaths() {
        Map<TSelectSqlStatement, String> out = new IdentityHashMap<TSelectSqlStatement, String>();
        for (Map.Entry<TSelectSqlStatement, Construct> e : blocks.entrySet()) {
            out.put(e.getKey(), e.getValue().path);
        }
        return out;
    }

    /** The innermost query block path that is a prefix of (or equal to) a path, or {@code null}. */
    public String enclosingBlockPath(String path) {
        if (path == null) {
            return null;
        }
        String best = null;
        for (Construct c : blocks.values()) {
            String p = c.path;
            if ((path.equals(p) || path.startsWith(p + "/")) && (best == null || p.length() > best.length())) {
                best = p;
            }
        }
        return best;
    }

    /** Whether every part of the statement is in a covered form. */
    public boolean isFullyCovered() {
        return !statementUncovered && uncovered.isEmpty();
    }

    /** The anchor of the reference whose first character is at the UTF-16 offset. */
    public Anchor anchor(int offset) {
        if (statementUncovered) {
            return new Anchor(null, statementUncoveredForm);
        }
        for (Uncovered u : uncovered) {
            if (u.start <= offset && offset < u.end) {
                return new Anchor(null, u.form);
            }
        }
        Construct best = null;
        List<Construct> level = roots;
        while (true) {
            Construct hit = find(level, offset);
            if (hit == null) {
                break;
            }
            best = hit;
            level = hit.textChildren;
        }
        if (best == null) {
            return new Anchor(null, "OUTSIDE_STATEMENT");
        }
        return new Anchor(best.path, null);
    }

    /** The child of a sorted, disjoint level that contains the offset, or null. */
    private static Construct find(List<Construct> level, int offset) {
        int low = 0;
        int high = level.size() - 1;
        int candidate = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (level.get(mid).start <= offset) {
                candidate = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        for (int i = candidate; i >= 0 && i >= candidate - 2; i--) {
            if (level.get(i).contains(offset)) {
                return level.get(i);
            }
        }
        return null;
    }

    /** The anchor of the first character of a token. */
    public Anchor anchor(TSourceToken token) {
        int offset = token == null ? -1 : tokenOffset(token);
        return offset < 0 ? new Anchor(null, "UNPOSITIONED") : anchor(offset);
    }

    /** The anchor of the first token of a node. */
    public Anchor anchor(TParseTreeNode node) {
        return anchor(node == null ? null : node.getStartToken());
    }

    /** {@link #anchorColumn(TObjectName)} of a live column reference of the tree the index was built from. */
    public Anchor anchorColumn(gudusoft.gsqlparser.nodes.TObjectName column) {
        return anchorColumn(mirrorOf(column, TObjectName.class));
    }

    /**
     * The anchor of a column reference: as {@link #anchor(TParseTreeNode)}, but a column that lands directly on a
     * statement, query block, WITH, FROM, JOIN, TARGET or USING step is in a construct this index does not model
     * and is reported uncovered.
     */
    public Anchor anchorColumn(TObjectName column) {
        Anchor a = anchor(column);
        if (!a.isCovered()) {
            return a;
        }
        String last = a.getPath().substring(a.getPath().lastIndexOf('/') + 1);
        String code = last.substring(0, last.indexOf('['));
        if (NOT_A_COLUMN_ANCHOR.contains(code)) {
            return new Anchor(null, "UNMODELLED CLAUSE AT " + a.getPath());
        }
        return a;
    }

    // ---------------------------------------------------------------------------------------------
    // Building
    // ---------------------------------------------------------------------------------------------

    private int start(TParseTreeNode node) {
        if (node == null || node.getStartToken() == null) {
            return -1;
        }
        TSourceToken t = node.getStartToken();
        return tokenOffset(t);
    }

    private int end(TParseTreeNode node) {
        if (node == null || node.getEndToken() == null) {
            return -1;
        }
        TSourceToken t = node.getEndToken();
        int offset = tokenOffset(t);
        return offset < 0 ? -1 : offset + (t.getAstext() == null ? 0 : t.getAstext().length());
    }

    private int offsetOf(TSourceToken token) {
        return token == null ? -1 : tokenOffset(token);
    }

    private static TSourceToken previousSolid(TSourceToken token) {
        TSourceToken t = token == null ? null : token.getPrevTokenInChain();
        while (t != null && (t.tokentype == ETokenType.ttwhitespace || t.tokentype == ETokenType.ttreturn
                || t.tokentype == ETokenType.ttsimplecomment || t.tokentype == ETokenType.ttbracketedcomment)) {
            t = t.getPrevTokenInChain();
        }
        return t;
    }

    /** The offset of the keyword just before a node when it is one of the given words, or the node's start. */
    private int keywordStart(TParseTreeNode node, String... keywords) {
        int s = start(node);
        TSourceToken t = node == null ? null : previousSolid(node.getStartToken());
        for (int hops = 0; hops < 3 && t != null; hops++) {
            for (String keyword : keywords) {
                if (keyword.equalsIgnoreCase(t.getAstext())) { // non-identifier-compare: SQL keyword text
                    int o = offsetOf(t);
                    if (o >= 0 && o < s) {
                        s = o;
                    }
                    return s;
                }
            }
            t = previousSolid(t);
        }
        return s;
    }

    private Construct add(String code, int index, int start, int end, Construct parent) {
        if (start < 0 || end < start) {
            return null;
        }
        Construct c = new Construct(code, index, start, end, parent, null, constructs.size());
        constructs.add(c);
        return c;
    }

    private Construct add(String code, int index, TParseTreeNode node, Construct parent) {
        return add(code, index, start(node), end(node), parent);
    }

    /** An expression step whose parent is the innermost step of {@code scope} that contains it. */
    private Construct addExpression(String code, int index, int start, int end, Construct scope) {
        if (start < 0 || end < start) {
            return null;
        }
        Construct c = new Construct(code, index, start, end, null, scope, constructs.size());
        constructs.add(c);
        return c;
    }

    private void markUncovered(String form, TParseTreeNode node) {
        markUncovered(form, start(node), end(node));
    }

    private void markUncovered(String form, int s, int e) {
        if (s >= 0 && e >= s) {
            uncovered.add(new Uncovered(form, s, e));
        }
    }

    private void build(TCustomSqlStatement stmt, boolean covered) {
        if (statementStep == null) {
            statementUncovered = true;
            statementUncoveredForm = "STATEMENT " + stmt.sqlstatementtype;
            return;
        }
        root = add(statementStep, 0, stmt, null);
        if (root == null) {
            statementUncovered = true;
            statementUncoveredForm = "UNPOSITIONED";
            return;
        }
        if (!covered) {
            // COPY, CALL, EXECUTE: the statement step only; their arguments are not covered
            uncovered.add(new Uncovered("ARGUMENTS OF " + statementStep, root.start, root.end));
            finish();
            return;
        }
        dmlCtes = coveredDmlCtes(stmt);
        try {
            if (stmt instanceof TSelectSqlStatement) {
                queryExpression((TSelectSqlStatement) stmt, root);
            } else if (stmt instanceof TInsertSqlStatement) {
                insert((TInsertSqlStatement) stmt);
            } else if (stmt instanceof TUpdateSqlStatement) {
                update((TUpdateSqlStatement) stmt);
            } else if (stmt instanceof TDeleteSqlStatement) {
                delete((TDeleteSqlStatement) stmt);
            } else if (stmt instanceof TMergeSqlStatement) {
                merge((TMergeSqlStatement) stmt);
            } else if (stmt instanceof TCreateTableSqlStatement) {
                createTable((TCreateTableSqlStatement) stmt);
            } else if (stmt instanceof TCreateViewSqlStatement) {
                TCreateViewSqlStatement view = (TCreateViewSqlStatement) stmt;
                createView(view, view.getViewName(), view.getViewAliasClause(), view.getSubquery());
            } else if (stmt instanceof TCreateMaterializedSqlStatement) {
                TCreateMaterializedSqlStatement view = (TCreateMaterializedSqlStatement) stmt;
                createView(view, view.getViewName(), view.getViewAliasClause(), view.getSubquery());
            } else if (isRoutineDefinition(stmt) || isBlock(stmt)) {
                List<Object[]> steps = returnSteps(stmt);
                for (int k = 0; k < steps.size(); k++) {
                    TExpression value = (TExpression) steps.get(k)[1];
                    if (value != null) {
                        expressions(add("RETURN", k, value, root), value);
                    } else {
                        add("RETURN", k, (TCustomSqlStatement) steps.get(k)[0], root); // RETURN NEXT without an operand
                    }
                }
                Object[] bare = inlineBareReturn(stmt);
                if (bare != null) {
                    // RETURN SELECT ... of an inline table function: RETURN[0], its query SUBQUERY[0] below it
                    Construct ret = add("RETURN", 0, (TCustomSqlStatement) bare[0], root);
                    Construct sub = ret == null ? null : add("SUBQUERY", 0, (TSelectSqlStatement) bare[1], ret);
                    if (sub != null) {
                        work.push(new Object[] {bare[1], sub});
                    }
                }
                procedural(Procedural.of(stmt));
            } else if ("ASSIGNMENT".equals(statementStep)) {
                procedural(Procedural.standalone(stmt));
            } else if ("CALL".equals(statementStep) || "EXECUTE".equals(statementStep)) {
                callArgumentSteps(stmt, root);
            }
            drain();
            returning(stmt);
        } catch (RuntimeException e) {
            // a parse tree this index cannot walk (GSP leaves some children null): nothing is covered
            statementUncovered = true;
            statementUncoveredForm = "UNTRAVERSABLE PARSE TREE (" + e.getClass().getSimpleName() + ")";
            return;
        }
        finish();
        markUnmodelledIdentifiers(stmt);
    }

    /**
     * The procedural parts of a routine's or a block's own body, or of a standalone assignment (Section 3.6): ASSIGN[k]
     * with its value's expression steps, or with the query of a SQL Server SELECT @v = ... as SUBQUERY[0]; CONDITION[k]
     * with its expression steps; CURSOR[c] introducing the cursor's query; FETCH[f] with nothing below it.
     */
    private void procedural(Procedural parts) {
        for (int k = 0; k < parts.assigns.size(); k++) {
            Procedural.Assign a = parts.assigns.get(k);
            int end = a.last == null ? -1 : offsetOf(a.last);
            Construct c = add("ASSIGN", k, offsetOf(a.first),
                    end < 0 ? -1 : end + (a.last.getAstext() == null ? 0 : a.last.getAstext().length()), root);
            if (c == null) {
                continue;
            }
            if (a.query != null) {
                Construct query = add("SUBQUERY", 0, a.query, c);
                if (query != null) {
                    work.push(new Object[] {a.query, query});
                }
            } else {
                expressions(c, a.value);
            }
        }
        for (int k = 0; k < parts.conditions.size(); k++) {
            Procedural.Condition c = parts.conditions.get(k);
            expressions(add("CONDITION", k, c.expr, root), c.expr);
        }
        for (int k = 0; k < parts.cursors.size(); k++) {
            Procedural.Cursor c = parts.cursors.get(k);
            Construct cursor = add("CURSOR", k, c.query, root);
            if (cursor != null) {
                work.push(new Object[] {c.query, cursor});
            }
        }
        for (int k = 0; k < parts.fetches.size(); k++) {
            add("FETCH", k, parts.fetches.get(k).node, root);
        }
    }

    private void drain() {
        while (!work.isEmpty()) {
            Object[] item = work.pop();
            queryExpression((TSelectSqlStatement) item[0], (Construct) item[1]);
        }
    }

    private void with(TCustomSqlStatement stmt, Construct parent) {
        if (stmt.getCteList() == null || stmt.getCteList().size() == 0) {
            return;
        }
        Construct with = add("WITH", 0, stmt.getCteList(), parent);
        if (with == null) {
            return;
        }
        for (int c = 0; c < stmt.getCteList().size(); c++) {
            TCTE cte = stmt.getCteList().getCTE(c);
            Construct cc = add("CTE", c, cte, with);
            if (cc == null) {
                continue;
            }
            if (cte.getColumnList() != null) {
                add("COLUMN_LIST", 0, cte.getColumnList(), cc);
            }
            if (cte.getSubquery() != null) {
                work.push(new Object[] {cte.getSubquery(), cc});
            } else if (coveredHere(cte)) {
                dataChangingBody(cte, cc);
            } else {
                markUncovered("CTE BODY", cte);
            }
        }
    }

    /**
     * The data-changing statement a CTE's body is (plan 09 slice 13e; path-v1 Section 3.2, item 6): its step, INSERT[0],
     * UPDATE[0] or DELETE[0] directly below CTE[c], then its own clauses below that step, as the statement step's of a
     * statement of its own would be; its RETURNING is RETURNING[0] below it.
     */
    private void dataChangingBody(TCTE cte, Construct cc) {
        TCustomSqlStatement body = dataChanging(cte);
        String step = body instanceof TInsertSqlStatement ? "INSERT" : body instanceof TUpdateSqlStatement ? "UPDATE"
                : body instanceof TMergeSqlStatement ? "MERGE" : "DELETE";
        int bodyStart = start(body);
        int bodyEnd = end(body);
        if (bodyStart >= 0 && bodyEnd < 0 && cte.getEndToken() != null) {
            // the parse gives no end to a body such as DELETE FROM t (Codex 13e #1): it ends at the CTE's ")"
            bodyEnd = offsetOf(cte.getEndToken());
        }
        Construct dml = bodyStart < 0 || bodyEnd < bodyStart ? null : add(step, 0, bodyStart, bodyEnd, cc);
        if (dml == null) {
            markUncovered("CTE BODY", cte);
            return;
        }
        Construct savedRoot = root;
        TParseTreeNode savedOwn = ownReturning;
        root = dml;
        ownReturning = null;
        try {
            if (body instanceof TInsertSqlStatement) {
                insert((TInsertSqlStatement) body);
            } else if (body instanceof TUpdateSqlStatement) {
                update((TUpdateSqlStatement) body);
            } else if (body instanceof TMergeSqlStatement) {
                merge((TMergeSqlStatement) body);
            } else {
                delete((TDeleteSqlStatement) body);
            }
            if (ownReturning != null) {
                ownedReturnings.add(Integer.valueOf(start(ownReturning)));
            }
            dmlCteSteps.put(cte, dml);
        } finally {
            root = savedRoot;
            ownReturning = savedOwn;
        }
    }

    /** The covered data-changing CTEs of the statement ({@link #coveredDmlCtes}), in WITH order. */
    private List<TCTE> dmlCtes = java.util.Collections.<TCTE>emptyList();

    /** Their statement steps, CTE[c]/UPDATE[0] and the like, once indexed (paths are set by finish()). */
    private final Map<TCTE, Construct> dmlCteSteps = new java.util.IdentityHashMap<TCTE, Construct>();

    private boolean coveredHere(TCTE cte) {
        for (TCTE c : dmlCtes) {
            if (c == cte) {
                return true;
            }
        }
        return false;
    }

    /** The starts of the RETURNING clauses covered besides the statement's own: the covered CTE's. */
    private final java.util.Set<Integer> ownedReturnings = new java.util.HashSet<Integer>();

    /** The path of the step of a covered data-changing CTE's statement (CTE[c]/UPDATE[0]), or null. */
    public String getDmlCtePath(TCTE cte) {
        Construct step = dmlCteSteps.get(cte);
        return step == null ? null : step.path;
    }

    /** The INSERT, UPDATE, DELETE or MERGE (PostgreSQL 17, slice 13i) a CTE's body is, or null (a query). */
    static TCustomSqlStatement dataChanging(TCTE cte) {
        TCustomSqlStatement body = cte == null || cte.getSubquery() != null ? null : cte.getPreparableStmt();
        return body instanceof TInsertSqlStatement || body instanceof TUpdateSqlStatement
                || body instanceof TDeleteSqlStatement || body instanceof TMergeSqlStatement ? body : null;
    }

    /**
     * The data-changing CTEs the paths and the graph cover (plan 09 slices 13e, 13h and 13i, owner rulings 2026-10-17
     * and 2026-10-18; fold-v1 Section 4.8, item 7): the PostgreSQL family's
     * {@code WITH d AS (INSERT/UPDATE/DELETE ... [RETURNING ...])}, every one of the WITH of a query, INSERT, UPDATE,
     * DELETE or MERGE, in WITH order, each with its own model (an INSERT inside an INSERT included). A target is
     * always a table and a body never reads its own CTE: the parse binds them so (TCustomSqlStatement.unbindCteTarget,
     * TCTE.unbindSelfReferences, measured on PostgreSQL 17); a parse that still binds one to a CTE is not covered,
     * said, never read as the CTE. One rule for the paths and the graph.
     */
    static List<TCTE> coveredDmlCtes(TCustomSqlStatement stmt) {
        if (stmt == null || !dmlCteDialect(stmt.dbvendor)) {
            return Collections.<TCTE>emptyList();
        }
        if (!(stmt instanceof TSelectSqlStatement || stmt instanceof TInsertSqlStatement
                || stmt instanceof TUpdateSqlStatement || stmt instanceof TDeleteSqlStatement
                || stmt instanceof TMergeSqlStatement) || stmt.getCteList() == null
                || (stmt instanceof TInsertSqlStatement && ((TInsertSqlStatement) stmt).isMultiTableInsert())) {
            return Collections.<TCTE>emptyList();
        }
        List<TCTE> out = new ArrayList<TCTE>();
        for (int c = 0; c < stmt.getCteList().size(); c++) {
            TCTE cte = stmt.getCteList().getCTE(c);
            TCustomSqlStatement body = dataChanging(cte);
            if (body == null || boundToCte(body.getTargetTable()) || boundToCte(stmt.getTargetTable())) {
                continue;
            }
            boolean self = false;
            for (int i = 0; body.tables != null && i < body.tables.size(); i++) {
                TTable t = body.tables.getTable(i);
                self |= t != null && t.isCTEName() && t.getCTE() == cte;
            }
            if (!self) {
                out.add(cte);
            }
        }
        return out;
    }

    /**
     * The dialects whose data-changing CTEs are covered: PostgreSQL, Greenplum and EDB (GaussDB parses them too but its
     * rules are not verified: not covered, said).
     */
    static boolean dmlCteDialect(EDbVendor v) {
        return v == EDbVendor.dbvpostgresql || v == EDbVendor.dbvgreenplum || v == EDbVendor.dbvedb;
    }

    /** Whether the parse bound a target to a CTE (it does not for the PostgreSQL family: a guard, never a guess). */
    private static boolean boundToCte(TTable target) {
        return target != null && target.isCTEName();
    }

    private void queryExpression(TSelectSqlStatement s, Construct in) {
        blocks.put(s, in);
        with(s, in);
        if (s.getValueClause() != null) {
            // a VALUES list used as a query (plan 09 slice 11): its rows are VALUES[r] below the step that introduces
            // the query expression
            if (s.getValueClause().getRows() == null || s.getValueClause().getRows().isEmpty()) {
                markUncovered("VALUES AS A QUERY", s);
            } else {
                valuesRows(s.getValueClause().getRows(), in);
            }
            return;
        }
        if (isSetOperation(s)) {
            if (mixesPrecedence(s)) {
                // GSP groups A UNION B INTERSECT C left to right; the SQL standard (and these dialects) bind
                // INTERSECT tighter, so the parse tree's branches are not the query's: no path is published
                markUncovered("SET OPERATION PRECEDENCE", s);
                return;
            }
            int[] range = setRange(s);
            Construct setOp = add("SET_OP", 0, range[0], range[1], in);
            if (setOp == null) {
                return;
            }
            List<TSelectSqlStatement> operands = operands(s);
            for (int b = 0; b < operands.size(); b++) {
                TSelectSqlStatement operand = operands.get(b);
                Construct branch = add("BRANCH", b, operand, setOp);
                if (branch != null) {
                    work.push(new Object[] {operand, branch});
                }
            }
            if (s.getOrderbyClause() != null) {
                expressions(add("ORDER_BY", 0, s.getOrderbyClause(), setOp), s.getOrderbyClause());
            }
            limits(s, setOp);
            return;
        }
        block(s, in);
    }

    private static boolean isSetOperation(TSelectSqlStatement s) {
        return s.getSetOperatorType() != null && s.getSetOperatorType() != ESetOperatorType.none
                && s.getLeftStmt() != null && s.getRightStmt() != null;
    }

    /**
     * Whether an unparenthesized chain mixes INTERSECT with UNION/EXCEPT/MINUS in a dialect that binds INTERSECT
     * tighter (all six portable dialects but Oracle, where the set operators have equal precedence).
     */
    private boolean mixesPrecedence(TSelectSqlStatement s) {
        if (vendor == EDbVendor.dbvoracle) {
            return false;
        }
        boolean intersect = false;
        boolean other = false;
        Deque<TSelectSqlStatement> stack = new ArrayDeque<TSelectSqlStatement>();
        stack.push(s);
        while (!stack.isEmpty()) {
            TSelectSqlStatement x = stack.pop();
            if (!isSetOperation(x) || (x != s && x.getParenthesisCount() > 0)) {
                continue;
            }
            if (x.getSetOperatorType() == ESetOperatorType.intersect) {
                intersect = true;
            } else {
                other = true;
            }
            stack.push(x.getLeftStmt());
            stack.push(x.getRightStmt());
        }
        return intersect && other;
    }

    /** From the first operand to the end of the set operation, excluding a WITH clause written before it. */
    private int[] setRange(TSelectSqlStatement s) {
        TSelectSqlStatement first = s;
        while (isSetOperation(first)) {
            first = first.getLeftStmt();
        }
        return new int[] {start(first), end(s)};
    }

    /**
     * The operands of one {@code SET_OP}: a chain of one operator with the same {@code ALL}/{@code DISTINCT} form and
     * no parentheses is flattened, in text order (Section 3.2, item 3).
     */
    private List<TSelectSqlStatement> operands(TSelectSqlStatement s) {
        List<TSelectSqlStatement> out = new ArrayList<TSelectSqlStatement>();
        Deque<TSelectSqlStatement> stack = new ArrayDeque<TSelectSqlStatement>();
        stack.push(s.getRightStmt());
        TSelectSqlStatement left = s.getLeftStmt();
        while (isSetOperation(left) && left.getSetOperatorType() == s.getSetOperatorType() && left.isAll() == s.isAll()
                && left.getParenthesisCount() == 0 && (left.getCteList() == null || left.getCteList().size() == 0)
                && left.getOrderbyClause() == null) {
            stack.push(left.getRightStmt());
            left = left.getLeftStmt();
        }
        out.add(left);
        while (!stack.isEmpty()) {
            out.add(stack.pop());
        }
        return out;
    }

    private void block(TSelectSqlStatement s, Construct in) {
        if (s.getResultColumnList() != null) {
            expressions(add("SELECT_LIST", 0, s.getResultColumnList(), in), s.getResultColumnList());
        }
        if (s.getJoins() != null && s.getJoins().size() > 0) {
            fromClause("FROM", s.getJoins(), keywordOffset(s.getJoins(), "FROM"), in);
        }
        if (s.getWhereClause() != null) {
            expressions(add("WHERE", 0, s.getWhereClause(), in), s.getWhereClause());
        }
        TGroupBy groupBy = s.getGroupByClause();
        if (groupBy != null) {
            if (groupBy.getItems() != null && groupBy.getItems().size() > 0) {
                int st = groupBy.getGROUP() != null ? offsetOf(groupBy.getGROUP()) : start(groupBy.getItems());
                expressions(add("GROUP_BY", 0, st, end(groupBy.getItems()), in), groupBy.getItems());
            }
            if (groupBy.getHavingClause() != null) {
                int st = groupBy.getHAVING() != null ? offsetOf(groupBy.getHAVING()) : start(groupBy.getHavingClause());
                expressions(add("HAVING", 0, st, end(groupBy.getHavingClause()), in), groupBy.getHavingClause());
            }
        }
        if (s.getQualifyClause() != null) {
            expressions(add("QUALIFY", 0, s.getQualifyClause(), in), s.getQualifyClause());
        }
        if (s.getOrderbyClause() != null) {
            expressions(add("ORDER_BY", 0, s.getOrderbyClause(), in), s.getOrderbyClause());
        }
        limits(s, in);
        if (s.getWindowClause() != null) {
            if (s.getWindowClause().getWindowDefs() != null) {
                for (int w = 0; w < s.getWindowClause().getWindowDefs().size(); w++) {
                    TWindowDef definition = (TWindowDef) s.getWindowClause().getWindowDefs().getElement(w);
                    windowParts(add("WINDOW", w, definition, in), definition.getPartitionClause(),
                            definition.getOrderBy());
                }
            } else if (s.getWindowClause().getWindowDefinitions() != null) {
                for (int w = 0; w < s.getWindowClause().getWindowDefinitions().size(); w++) {
                    TWindowDefinition definition =
                            (TWindowDefinition) s.getWindowClause()
                                    .getWindowDefinitions().getElement(w);
                    Construct window = add("WINDOW", w, definition, in);
                    TWindowSpecification spec = definition.getWindowSpecification();
                    if (spec != null) {
                        windowParts(window, spec.getPartitionClause(), spec.getOrderBy());
                    }
                }
            }
        }
        THierarchical hierarchical = s.getHierarchicalClause();
        if (hierarchical != null) {
            markUncovered("CONNECT BY", hierarchical);
        }
    }

    /** The offset of a keyword written just before the node (such as FROM before the first table). */
    private int keywordOffset(TParseTreeNode node, String keyword) {
        TParseTreeNode first = node;
        if (node instanceof TJoinList && ((TJoinList) node).size() > 0) {
            first = ((TJoinList) node).getJoin(0);
            if (first.getStartToken() == null) {
                first = ((TJoinList) node).getJoin(0).getTable();
            }
        }
        return keywordStart(first, keyword) < start(first) ? keywordStart(first, keyword) : -1;
    }

    /** TOP, LIMIT, OFFSET and FETCH are one LIMIT step; each fragment is a construct with that path. */
    private void limits(TSelectSqlStatement s, Construct in) {
        TParseTreeNode[] parts = {s.getTopClause(), s.getLimitClause(), s.getOffsetClause(), s.getFetchFirstClause()};
        for (TParseTreeNode part : parts) {
            if (part != null) {
                expressions(add("LIMIT", 0, part, in), part);
            }
        }
    }

    /** {@code FROM}, {@code USING} below DELETE/MERGE, or the target list of UPDATE: joins and derived tables. */
    private Construct fromClause(String code, TJoinList joins, int keywordAt, Construct in) {
        int[] range = joinListRange(joins);
        if (range == null) {
            return null;
        }
        Construct from = add(code, 0, keywordAt >= 0 && keywordAt < range[0] ? keywordAt : range[0], range[1], in);
        if (from == null) {
            return null;
        }
        joinsAndTables(joins, from);
        return from;
    }

    private int[] joinListRange(TJoinList joins) {
        int st = -1;
        int en = -1;
        for (int i = 0; i < joins.size(); i++) {
            TJoin join = joins.getJoin(i);
            TParseTreeNode[] parts = {join, join.getTable()};
            for (TParseTreeNode part : parts) {
                int ps = start(part);
                int pe = end(part);
                if (ps >= 0 && pe >= ps) {
                    st = st < 0 ? ps : Math.min(st, ps);
                    en = Math.max(en, pe);
                }
            }
            if (join.getJoinItems() != null) {
                for (int k = 0; k < join.getJoinItems().size(); k++) {
                    TJoinItem item = join.getJoinItems().getJoinItem(k);
                    int ps = start(item);
                    int pe = Math.max(end(item), end(item.getOnCondition()));
                    if (ps >= 0 && pe >= ps) {
                        st = st < 0 ? ps : Math.min(st, ps);
                        en = Math.max(en, pe);
                    }
                }
            }
        }
        return st < 0 ? null : new int[] {st, en};
    }

    private void joinsAndTables(TParseTreeNode node, Construct from) {
        final List<TJoinItem> joinItems = new ArrayList<TJoinItem>();
        final List<TTable> tables = new ArrayList<TTable>();
        final List<TSelectSqlStatement> selects = new ArrayList<TSelectSqlStatement>();
        final List<TPivotClause> pivots = new ArrayList<TPivotClause>();
        node.acceptChildren(new TParseTreeVisitor() {
            @Override
            public void preVisit(TJoinItem item) {
                joinItems.add(item);
            }

            @Override
            public void preVisit(TTable table) {
                tables.add(table);
            }

            @Override
            public void preVisit(TSelectSqlStatement stmt) {
                selects.add(stmt);
            }

            @Override
            public void preVisit(TPivotClause pivot) {
                pivots.add(pivot);
            }
        });
        List<TSelectSqlStatement> outer = outermost(selects);
        // JOIN[j]: the join items outside every derived table, in text order of their JOIN keyword; an APPLY is no
        // JOIN keyword (its item is a lateral item of the clause, LATERAL[l] below FROM[0], plan 09 slice 11)
        List<TJoinItem> items = new ArrayList<TJoinItem>();
        final List<TTable> applied = new ArrayList<TTable>();
        for (TJoinItem item : joinItems) {
            if (containedInAny(item, outer)) {
                continue;
            }
            if (item.getJoinType() == EJoinType.crossapply || item.getJoinType() == EJoinType.outerapply) {
                if (item.getTable() != null) {
                    applied.add(item.getTable());
                }
                continue;
            }
            items.add(item);
        }
        Collections.sort(items, new Comparator<TJoinItem>() {
            @Override
            public int compare(TJoinItem a, TJoinItem b) {
                return Integer.compare(start(a), start(b));
            }
        });
        List<Construct> joinConstructs = new ArrayList<Construct>();
        for (int j = 0; j < items.size(); j++) {
            TJoinItem item = items.get(j);
            int en = Math.max(end(item), end(item.getOnCondition()));
            if (item.getUsingColumns() != null) {
                en = Math.max(en, end(item.getUsingColumns()));
            }
            Construct join = add("JOIN", j, keywordStart(item, "JOIN"), en, from);
            if (join == null) {
                continue;
            }
            joinConstructs.add(join);
            if (item.getOnCondition() != null) {
                expressions(add("ON", 0, keywordStart(item.getOnCondition(), "ON"), end(item.getOnCondition()), join),
                        item.getOnCondition());
            }
            if (item.getUsingColumns() != null) {
                add("USING", 0, keywordStart(item.getUsingColumns(), "USING"), end(item.getUsingColumns()), join);
            }
        }
        final List<TPivotClause> covered = new ArrayList<TPivotClause>();
        for (TTable table : tables) {
            if (table.getSubquery() == null ? containedInAny(table, outer) : !outer.contains(table.getSubquery())) {
                continue;
            }
            List<TPivotClause> operators = pivotClauses(table);
            if (!operators.isEmpty()) {
                // PATH-V1 PIVOT[p] (plan 09 slice 10): the operators below the step of the item they apply to, in text
                // order; the item itself (a table name, or a derived table, SUBQUERY[k]) is reached as an item of its own
                Construct parent = from;
                for (Construct join : joinConstructs) {
                    if (join.contains(start(table)) && (parent == from || join.length() < parent.length())) {
                        parent = join;
                    }
                }
                for (TPivotClause pivot : operators) {
                    Construct op = add("PIVOT", -1, keywordStart(pivot, "PIVOT", "UNPIVOT"), end(pivot), parent);
                    if (op == null) {
                        continue;
                    }
                    covered.add(pivot);
                    if (pivot.getAggregation_function_list() != null) {
                        expressions(op, pivot.getAggregation_function_list());
                    } else if (pivot.getAggregation_function() != null) {
                        expressions(op, pivot.getAggregation_function());
                    }
                    TPivotInClause in = pivot.getPivotInClause();
                    if (in != null && in.getSubQuery() != null) {
                        Construct sub = add("SUBQUERY", -1, in.getSubQuery(), op);
                        if (sub != null) {
                            work.push(new Object[] {in.getSubQuery(), sub});
                        }
                    }
                }
                continue;
            }
            if (lateralItem(table, applied, from, joinConstructs)) {
                continue;
            }
            String form = uncoveredTableForm(table);
            if (form != null) {
                markUncovered(form, table);
                continue;
            }
            TSourceToken pattern = matchRecognizeToken(table);
            if (pattern != null) {
                // path-v1 Section 2, item 3: the clause (its partition, measures, pattern and definitions) is not
                // covered; the item's rows are its table's (doc 10, Section 2.1), its columns are not (StatementGraph)
                markUncovered("MATCH_RECOGNIZE", offsetOf(pattern), end(table));
            }
            if (table.getSubquery() != null) {
                Construct parent = from;
                for (Construct join : joinConstructs) {
                    if (join.contains(start(table)) && (parent == from || join.length() < parent.length())) {
                        parent = join;
                    }
                }
                Construct sub = add("SUBQUERY", -1, table.getSubquery(), parent);
                if (sub != null) {
                    work.push(new Object[] {table.getSubquery(), sub});
                }
            }
        }
        for (TPivotClause pivot : pivots) {
            if (!containedInAny(pivot, outer) && !covered.contains(pivot)) {
                markUncovered("PIVOT", pivot);
            }
        }
    }

    /**
     * PATH-V1 {@code LATERAL[l]} (plan 09 slice 11): a lateral item of a FROM clause, below the step of the item
     * (FROM[0], or the JOIN[j] that introduces it), numbered in text order among the lateral items below that step: a
     * derived table written after LATERAL or the right side of an APPLY (its query is SUBQUERY[0] below it), and a call
     * in FROM (a table function, TABLE(...), UNNEST, a Hive-family LATERAL VIEW), whose operands are FUNCTION_ARG[k]
     * below it (Section 5, item 1: TABLE(f(x)) is f's call as FUNCTION_ARG[0]). A VALUES list used as a FROM item is
     * a derived table, SUBQUERY[k], whose rows are VALUES[r]. Its Hive LATERAL VIEWs follow a table name. Returns
     * whether the item was one of these.
     */
    private boolean lateralItem(TTable table, List<TTable> applied, Construct from, List<Construct> joinConstructs) {
        Construct parent = from;
        // an APPLY's item is directly below FROM[0] even inside a parenthesized join tree (APPLY is no JOIN keyword;
        // Codex slice 11 #10)
        for (Construct join : applied.contains(table) ? Collections.<Construct>emptyList() : joinConstructs) {
            if (join.contains(start(table)) && (parent == from || join.length() < parent.length())) {
                parent = join;
            }
        }
        if (table.getTableType() == ETableSource.objectname && table.getLateralViewList() != null) {
            for (TLateralView view : table.getLateralViewList()) {
                Construct lateral = add("LATERAL", -1, view, from);
                if (lateral != null && view.getUdtf() != null) {
                    tableCall(lateral, view.getUdtf());
                }
            }
            return false; // the table itself is an item of its own
        }
        ETableSource type = table.getTableType();
        boolean query = table.getSubquery() != null && (applied.contains(table) || "LATERAL".equals(lateralKeyword(table)));
        if (query) {
            int st = keywordStart(table, "LATERAL");
            Construct lateral = add("LATERAL", -1, Math.min(st >= 0 ? st : start(table), start(table.getSubquery())),
                    Math.max(end(table), end(table.getSubquery())), parent);
            Construct sub = lateral == null ? null : add("SUBQUERY", 0, table.getSubquery(), lateral);
            if (sub != null) {
                work.push(new Object[] {table.getSubquery(), sub});
            }
            return true;
        }
        if (type == ETableSource.function || type == ETableSource.unnest || type == ETableSource.tableExpr) {
            int st = keywordStart(table, "LATERAL");
            Construct lateral = add("LATERAL", -1, st >= 0 ? st : start(table), end(table), parent);
            if (lateral == null) {
                return true;
            }
            if (type == ETableSource.function && table.getFuncCall() != null) {
                tableCall(lateral, table.getFuncCall());
            } else if (type == ETableSource.unnest && table.getUnnestClause() != null) {
                // UNNEST(a, b) is a call: its arrays are its operands (an expression, or the column of the legacy
                // UNNEST(t.arr), in the order TableFunctionLayout reads them)
                List<TParseTreeNode> arrays = unnestArrays(table.getUnnestClause());
                for (int k = 0; k < arrays.size(); k++) {
                    addExpression("FUNCTION_ARG", k, start(arrays.get(k)), end(arrays.get(k)), lateral);
                    expressions(lateral, arrays.get(k));
                }
            } else if (type == ETableSource.tableExpr && table.getTableExpr() != null) {
                // Oracle TABLE(collection): a call whose one operand is the collection
                addExpression("FUNCTION_ARG", 0, start(table.getTableExpr()), end(table.getTableExpr()), lateral);
                expressions(lateral, table.getTableExpr());
            }
            return true;
        }
        if (type == ETableSource.rowList || (type == ETableSource.subquery && table.getSubquery() == null
                && table.getValueClause() != null)) {
            Construct sub = add("SUBQUERY", -1, table, parent);
            if (sub != null) {
                valuesRows(valueRows(table), sub);
            }
            return true;
        }
        return false;
    }

    /**
     * The operands of a call in FROM, FUNCTION_ARG[k] below its LATERAL[l] (Section 5, item 1): each argument as
     * written, a named argument ({@code input => x}) whole. Read from the call's arguments: a vendor's own call class
     * (Snowflake's FLATTEN) is not a call the expression visitor lists.
     */
    private void tableCall(Construct lateral, TFunctionCall call) {
        TExpressionList args = call.getArgs();
        for (int k = 0; args != null && k < args.size(); k++) {
            TExpression arg = args.getExpression(k);
            if (arg != null && start(arg) >= 0) {
                addExpression("FUNCTION_ARG", k, start(arg), end(arg), lateral);
                expressions(lateral, arg);
            }
        }
    }

    /** The arrays of an UNNEST, as {@code TableFunctionLayout.unnestArrays} reads them. */
    private static List<TParseTreeNode> unnestArrays(TUnnestClause clause) {
        List<TParseTreeNode> arrays = new ArrayList<TParseTreeNode>();
        if (clause.getExprList() != null && clause.getExprList().size() > 0) {
            for (int i = 0; i < clause.getExprList().size(); i++) {
                arrays.add(clause.getExprList().getExpression(i));
            }
        } else if (clause.getArrayExpr() != null) {
            arrays.add(clause.getArrayExpr());
        } else if (clause.getColumns() != null) {
            for (int i = 0; i < clause.getColumns().size(); i++) {
                arrays.add(clause.getColumns().getObjectName(i));
            }
        }
        return arrays;
    }

    /** "LATERAL" when that keyword stands before a derived table (or between its start and its query), else null. */
    private String lateralKeyword(TTable table) {
        TSourceToken before = previousSolid(table.getStartToken());
        if (before != null && "LATERAL".equalsIgnoreCase(before.getAstext())) { // non-identifier-compare: keyword
            return "LATERAL";
        }
        if (table.getSubquery() != null && table.getStartToken() != null) {
            int subStart = start(table.getSubquery());
            for (TSourceToken t = table.getStartToken(); t != null && offsetOf(t) >= 0 && offsetOf(t) < subStart;
                    t = t.getNextTokenInChain()) {
                if ("LATERAL".equalsIgnoreCase(t.getAstext())) { // non-identifier-compare: keyword
                    return "LATERAL";
                }
            }
        }
        return null;
    }

    /** The rows of a VALUES list used as a FROM item: its value clause's, or its row list's. */
    private List<TParseTreeNode> valueRows(TTable table) {
        List<TParseTreeNode> rows = new ArrayList<TParseTreeNode>();
        if (table.getValueClause() != null && table.getValueClause().getRows() != null
                && !table.getValueClause().getRows().isEmpty()) {
            rows.addAll(table.getValueClause().getRows());
        } else if (table.getRowList() != null) {
            for (int r = 0; r < table.getRowList().size(); r++) {
                rows.add(table.getRowList().getMultiTarget(r));
            }
        }
        return rows;
    }

    /** VALUES[r] (plan 09 slice 11): the r-th row of a VALUES list used as a query, directly below its step. */
    private void valuesRows(List<? extends TParseTreeNode> rows, Construct in) {
        for (int r = 0; r < rows.size(); r++) {
            TParseTreeNode row = rows.get(r);
            Construct c = add("VALUES", r, row, in);
            if (c != null) {
                expressions(c, row);
            }
        }
    }

    /**
     * The one PIVOT or UNPIVOT operator a FROM item applies to its table or derived table (plan 09 slice 10), or null:
     * an item with no operator, with several chained operators, or a Teradata TD_UNPIVOT table operator.
     */
    static TPivotClause singlePivot(TTable table) {
        List<TPivotClause> clauses = pivotClauses(table);
        return clauses.size() == 1 ? clauses.get(0) : null;
    }

    /**
     * The PIVOT and UNPIVOT operators a FROM item applies to its table or derived table, in text order (a chain has
     * several), or none: an item with no operator, or a Teradata TD_UNPIVOT table operator.
     */
    static List<TPivotClause> pivotClauses(TTable table) {
        List<TPivotClause> out = new ArrayList<TPivotClause>();
        if (table == null || table.getTableType() != ETableSource.pivoted_table || table.getPivotedTable() == null
                || table.getPivotedTable().getTableSource() == null) {
            return out;
        }
        TPTNodeList clauses = table.getPivotedTable().getPivotClauseList();
        for (int i = 0; clauses != null && i < clauses.size(); i++) {
            if (!(clauses.getElement(i) instanceof TPivotClause)) {
                return new ArrayList<TPivotClause>();
            }
            out.add((TPivotClause) clauses.getElement(i));
        }
        return out;
    }

    /**
     * The PATH-V1 form a table source is not covered by, or null for a table name or a derived table (lateral items
     * and VALUES lists are steps of their own: {@link #lateralItem}).
     */
    private String uncoveredTableForm(TTable table) {
        ETableSource type = table.getTableType();
        if (table.getPivotClause() != null || type == ETableSource.pivoted_table || type == ETableSource.td_unpivot) {
            return "PIVOT";
        }
        if (type == ETableSource.subquery || table.getSubquery() != null || type == ETableSource.objectname
                || type == ETableSource.join || type == ETableSource.lateralView) {
            // a LATERAL VIEW's table: its step is the view's own, made with the table it follows
            return null;
        }
        return "TABLE " + type;
    }

    /**
     * Whether a FROM item carries a MATCH_RECOGNIZE clause. GSP keeps no node for it: the item's tokens run over the
     * clause, whose result has the partition columns and the measures, never the table's other columns.
     */
    static boolean matchRecognize(TTable item) {
        return item != null && item.getTableType() != ETableSource.function && matchRecognizeToken(item) != null;
    }

    /**
     * Why a column read through a MATCH_RECOGNIZE item is not the table's column of that name, or null when it is
     * (plan 09 slice 13j). The result has the PARTITION BY columns and the measures; ALL ROWS PER MATCH keeps every
     * other column of the table too. A measure takes its name from its alias, so a name a measure carries is never
     * the table's column, and with ONE ROW PER MATCH a name no PARTITION BY item carries is none of the result's.
     * The clause has no node: its tokens are read at depth one of its parentheses.
     */
    static String matchRecognizeColumn(TTable item, EDbVendor vendor, String column) {
        TSourceToken keyword = matchRecognizeToken(item);
        String over = item.getTableName() == null ? "the table" : item.getTableName().toString();
        String unknown = "may name a measure of MATCH_RECOGNIZE over " + over + ", whose columns are not published yet";
        if (keyword == null) {
            return unknown;
        }
        List<TSourceToken> solid = new ArrayList<TSourceToken>();
        for (int i = keyword.posinlist + 1; i < keyword.container.size(); i++) {
            TSourceToken t = keyword.container.get(i);
            if (!blank(t)) {
                solid.add(t);
            }
            if (t == item.getEndToken()) {
                break;
            }
        }
        List<TSourceToken> partition = new ArrayList<TSourceToken>();
        List<TSourceToken> measures = new ArrayList<TSourceToken>();
        boolean allRows = false;
        boolean closed = false;
        String clause = "";
        TSourceToken last = null; // the last solid token of the measure being read: its alias
        int depth = 0;
        for (int i = 0; i < solid.size() && !closed; i++) {
            TSourceToken t = solid.get(i);
            String text = t.getAstext();
            String k = text.toUpperCase(Locale.ROOT);
            boolean word = t.tokentype != ETokenType.ttdqstring && t.tokentype != ETokenType.ttsqstring;
            if ("(".equals(text)) {
                depth++;
                if (depth > 1 && "MEASURES".equals(clause)) {
                    last = t;
                }
            } else if (")".equals(text)) {
                depth--;
                closed = depth == 0;
                if (!closed && "MEASURES".equals(clause)) {
                    last = t;
                }
            } else if (depth == 1 && word && !"DEFINE".equals(clause) && ("PARTITION".equals(k) || "ORDER".equals(k)
                    || "MEASURES".equals(k) || "ONE".equals(k) || "ALL".equals(k) || "AFTER".equals(k)
                    || "PATTERN".equals(k) || "SUBSET".equals(k) || "DEFINE".equals(k))) {
                if ("MEASURES".equals(clause)) {
                    if (last == null) {
                        return unknown;
                    }
                    measures.add(last);
                }
                last = null;
                clause = k;
                allRows |= "ALL".equals(k) && i + 1 < solid.size()
                        && "ROWS".equals(solid.get(i + 1).getAstext().toUpperCase(Locale.ROOT));
            } else if ("MEASURES".equals(clause)) {
                if (depth == 1 && ",".equals(text)) {
                    if (last == null) {
                        return unknown;
                    }
                    measures.add(last);
                    last = null;
                } else {
                    last = t;
                }
            } else if (depth == 1 && "PARTITION".equals(clause) && !"BY".equals(k) && !",".equals(text)) {
                if (".".equals(text)) {
                    if (!partition.isEmpty()) {
                        partition.remove(partition.size() - 1); // a qualifier: the column is the part after it
                    }
                } else {
                    partition.add(t);
                }
            }
        }
        if (!closed) {
            return unknown;
        }
        if ("MEASURES".equals(clause)) {
            if (last == null) {
                return unknown;
            }
            measures.add(last);
        }
        for (TSourceToken alias : measures) {
            if (alias.tokentype != ETokenType.ttidentifier && alias.tokentype != ETokenType.ttdqstring
                    && alias.tokentype != ETokenType.ttkeyword) {
                return unknown; // a measure that does not end in a name: its alias is not read
            }
            if (gudusoft.gsqlparser.util.SQLUtil.sameName(vendor,
                    gudusoft.gsqlparser.sqlenv.ESQLDataObjectType.dotColumn, alias.getAstext(), column)) {
                return "names a measure of MATCH_RECOGNIZE over " + over + ", whose value is not published yet";
            }
        }
        if (allRows) {
            return null;
        }
        for (TSourceToken name : partition) {
            if (gudusoft.gsqlparser.util.SQLUtil.sameName(vendor,
                    gudusoft.gsqlparser.sqlenv.ESQLDataObjectType.dotColumn, name.getAstext(), column)) {
                return null;
            }
        }
        return "is no PARTITION BY column or measure of MATCH_RECOGNIZE over " + over + " (ONE ROW PER MATCH): the "
                + "result has no such column";
    }

    private static boolean blank(TSourceToken t) {
        return t.tokentype == ETokenType.ttwhitespace || t.tokentype == ETokenType.ttreturn
                || t.tokentype == ETokenType.ttsimplecomment || t.tokentype == ETokenType.ttbracketedcomment;
    }

    /** Whether the tokens of a node name MATCH_RECOGNIZE anywhere (a cheap test before {@link #matchRecognize}). */
    static boolean mentionsMatchRecognize(TParseTreeNode node) {
        TSourceToken start = node == null ? null : node.getStartToken();
        TSourceToken end = node == null ? null : node.getEndToken();
        if (start == null || end == null || start.container == null || end.container != start.container) {
            return true; // no range to scan: ask item by item
        }
        for (int i = start.posinlist; i <= end.posinlist && i < start.container.size(); i++) {
            if ("MATCH_RECOGNIZE".equalsIgnoreCase(start.container.get(i).getAstext())) { // non-identifier-compare: keyword
                return true;
            }
        }
        return false;
    }

    /** The MATCH_RECOGNIZE keyword of a FROM item followed by its parenthesis, or null. */
    private static TSourceToken matchRecognizeToken(TTable item) {
        TSourceToken start = item == null ? null : item.getStartToken();
        TSourceToken end = item == null ? null : item.getEndToken();
        if (start == null || end == null || start.container == null || end.container != start.container) {
            return null;
        }
        int depth = 0;
        for (int i = start.posinlist; i <= end.posinlist && i < start.container.size(); i++) {
            TSourceToken t = start.container.get(i);
            if ("(".equals(t.getAstext())) {
                depth++;
            } else if (")".equals(t.getAstext())) {
                depth--;
            }
            // the item's own clause, never one of a query or a call nested in it (Codex 13j #2)
            if (depth != 0 || !"MATCH_RECOGNIZE".equalsIgnoreCase(t.getAstext())) { // non-identifier-compare: keyword
                continue;
            }
            for (int j = i + 1; j <= end.posinlist && j < start.container.size(); j++) {
                TSourceToken n = start.container.get(j);
                if (!blank(n)) {
                    if ("(".equals(n.getAstext())) {
                        return t;
                    }
                    break;
                }
            }
        }
        return null;
    }

    private List<TSelectSqlStatement> outermost(List<TSelectSqlStatement> selects) {
        List<int[]> ranges = new ArrayList<int[]>();
        for (TSelectSqlStatement s : selects) {
            ranges.add(new int[] {start(s), end(s)});
        }
        List<TSelectSqlStatement> out = new ArrayList<TSelectSqlStatement>();
        for (int i = 0; i < selects.size(); i++) {
            boolean inner = false;
            for (int j = 0; j < selects.size() && !inner; j++) {
                if (i != j && ranges.get(j)[0] <= ranges.get(i)[0] && ranges.get(i)[1] <= ranges.get(j)[1]
                        && (ranges.get(j)[0] < ranges.get(i)[0] || ranges.get(i)[1] < ranges.get(j)[1] || j < i)) {
                    inner = true;
                }
            }
            if (!inner) {
                out.add(selects.get(i));
            }
        }
        return out;
    }

    /** Whether the whole node lies within one of the statements (a join item can start at a derived table's paren). */
    private boolean containedInAny(TParseTreeNode node, List<TSelectSqlStatement> selects) {
        int ns = start(node);
        int ne = Math.max(end(node), node instanceof TJoinItem ? end(((TJoinItem) node).getOnCondition()) : -1);
        for (TSelectSqlStatement s : selects) {
            if (start(s) <= ns && ne <= end(s)) {
                return true;
            }
        }
        return false;
    }

    private boolean insideAny(int offset, List<TSelectSqlStatement> selects) {
        for (TSelectSqlStatement s : selects) {
            if (start(s) <= offset && offset < end(s)) {
                return true;
            }
        }
        return false;
    }

    /**
     * The expression steps of one clause (Section 5): calls and their operands, CASE parts, subqueries and OVER
     * clauses. Nodes inside a subquery are left to that subquery's own query expression.
     */
    private void expressions(final Construct clause, TParseTreeNode node) {
        if (clause == null || node == null) {
            return;
        }
        final List<TFunctionCall> calls = new ArrayList<TFunctionCall>();
        final List<TCaseExpression> cases = new ArrayList<TCaseExpression>();
        final List<TExpression> exprs = new ArrayList<TExpression>();
        final List<TSelectSqlStatement> selects = new ArrayList<TSelectSqlStatement>();
        final List<TParseTreeNode> notCovered = new ArrayList<TParseTreeNode>();
        node.acceptChildren(new TParseTreeVisitor() {
            @Override
            public void preVisit(TFunctionCall call) {
                calls.add(call);
            }

            @Override
            public void preVisit(TCaseExpression expr) {
                cases.add(expr);
            }

            @Override
            public void preVisit(TExpression expr) {
                exprs.add(expr);
            }

            @Override
            public void preVisit(TSelectSqlStatement stmt) {
                selects.add(stmt);
            }

            @Override
            public void preVisit(TPivotClause pivot) {
                notCovered.add(pivot);
            }

            @Override
            public void preVisit(TReturningClause returning) {
                notCovered.add(returning);
            }

            @Override
            public void preVisit(TOutputClause output) {
                notCovered.add(output);
            }
        });
        if (node instanceof TExpression) {
            TExpression e = (TExpression) node;
            if (exprs.isEmpty() || exprs.get(0) != e) {
                exprs.add(0, e); // TExpression.acceptChildren visits the node itself first: never list it twice
            }
            if (e.getFunctionCall() != null && !calls.contains(e.getFunctionCall())) {
                calls.add(0, e.getFunctionCall());
            }
            if (e.getCaseExpression() != null && !cases.contains(e.getCaseExpression())) {
                cases.add(0, e.getCaseExpression());
            }
            if (e.getSubQuery() != null && !selects.contains(e.getSubQuery())) {
                selects.add(0, e.getSubQuery());
            }
        }
        List<TSelectSqlStatement> outer = outermost(selects);
        for (TSelectSqlStatement sub : outer) {
            Construct c = addExpression("SUBQUERY", -1, start(sub), end(sub), clause);
            if (c != null) {
                work.push(new Object[] {sub, c});
            }
        }
        for (TParseTreeNode n : notCovered) {
            if (!insideAny(start(n), outer)) {
                markUncovered(n instanceof TPivotClause ? "PIVOT" : n instanceof TOutputClause ? "OUTPUT" : "RETURNING",
                        n);
            }
        }
        for (TExpression e : exprs) {
            if (e.getExpressionType() == EExpressionType.lambda_t && !insideAny(start(e), outer)) {
                markUncovered("LAMBDA", e);
            }
        }
        for (TCaseExpression k : cases) {
            if (insideAny(start(k), outer) || k.getWhenClauseItemList() == null) {
                continue;
            }
            for (int i = 0; i < k.getWhenClauseItemList().size(); i++) {
                TWhenClauseItem when = k.getWhenClauseItemList().getWhenClauseItem(i);
                if (when.getComparison_expr() != null) {
                    addExpression("CASE_WHEN", i, start(when.getComparison_expr()), end(when.getComparison_expr()),
                            clause);
                }
                if (when.getReturn_expr() != null) {
                    addExpression("CASE_THEN", i, start(when.getReturn_expr()), end(when.getReturn_expr()), clause);
                }
            }
            if (k.getElse_expr() != null) {
                addExpression("CASE_ELSE", 0, start(k.getElse_expr()), end(k.getElse_expr()), clause);
            }
        }
        ExpressionTree tree = new ExpressionTree(exprs, outer);
        for (TFunctionCall call : calls) {
            if (insideAny(start(call), outer)) {
                continue;
            }
            List<int[]> excluded = new ArrayList<int[]>();
            TWindowDef over = call.getWindowDef();
            if (over != null && start(over) >= 0) {
                int[] window = {start(over), end(over)};
                excluded.add(window);
                if (over.getWithinGroup() != null && !over.isIncludingOverClause()) {
                    // SQL Server keeps WITHIN GROUP in the window definition
                    markUncovered("WITHIN GROUP", window[0], window[1]);
                } else if (over.getName() == null || over.getPartitionClause() != null || over.getOrderBy() != null) {
                    Construct w = addExpression("WINDOW", 0, window[0], window[1], clause);
                    windowParts(w, over.getPartitionClause(), over.getOrderBy());
                }
            }
            if (call.getFilterClause() != null) {
                markUncovered("AGGREGATE FILTER", call.getFilterClause());
                excluded.add(new int[] {start(call.getFilterClause()), end(call.getFilterClause())});
            }
            if (call.getWithinGroup() != null) {
                markUncovered("WITHIN GROUP", call.getWithinGroup());
                excluded.add(new int[] {start(call.getWithinGroup()), end(call.getWithinGroup())});
            }
            if (call.getTrimArgument() != null) {
                int k = 0;
                TExpression[] trimOperands = {call.getTrimArgument().getTrimCharacter(),
                    call.getTrimArgument().getStringExpression()};
                for (TExpression operand : trimOperands) {
                    if (operand != null && start(operand) >= 0) {
                        addExpression("FUNCTION_ARG", k++, start(operand), end(operand), clause);
                    }
                }
                // the visitor does not walk the trim character: its calls, CASEs and subqueries get their steps here
                if (call.getTrimArgument().getTrimCharacter() != null) {
                    expressions(clause, call.getTrimArgument().getTrimCharacter());
                }
                continue;
            }
            List<TExpression> operands = tree.operandsOf(call, excluded);
            for (int k = 0; k < operands.size(); k++) {
                addExpression("FUNCTION_ARG", k, start(operands.get(k)), end(operands.get(k)), clause);
            }
        }
    }

    /**
     * The TExpression nodes of one clause as a containment forest (their text ranges nest), so the operands of a
     * call are the children of its own expression node: no scan of every expression per call.
     */
    private final class ExpressionTree {
        private final Map<TExpression, List<TExpression>> children = new IdentityHashMap<TExpression, List<TExpression>>();
        private final Map<Long, TExpression> byRange = new HashMap<Long, TExpression>();

        private final List<TExpression> all;

        ExpressionTree(List<TExpression> exprs, List<TSelectSqlStatement> outer) {
            List<TExpression> list = new ArrayList<TExpression>();
            final Map<TExpression, Integer> order = new IdentityHashMap<TExpression, Integer>();
            for (TExpression e : exprs) {
                // one node per object: a node listed twice would be its own child, and operandsOf would never end
                if (start(e) >= 0 && end(e) >= start(e) && !insideAny(start(e), outer) && !order.containsKey(e)) {
                    order.put(e, Integer.valueOf(list.size()));
                    list.add(e);
                }
            }
            Collections.sort(list, new Comparator<TExpression>() {
                @Override
                public int compare(TExpression a, TExpression b) {
                    int c = Integer.compare(start(a), start(b));
                    if (c != 0) {
                        return c;
                    }
                    c = Integer.compare(end(b), end(a));
                    return c != 0 ? c : order.get(a).compareTo(order.get(b));
                }
            });
            this.all = list;
            Deque<TExpression> stack = new ArrayDeque<TExpression>();
            for (TExpression e : list) {
                while (!stack.isEmpty() && !(start(stack.peek()) <= start(e) && end(e) <= end(stack.peek()))) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    List<TExpression> kids = children.get(stack.peek());
                    if (kids == null) {
                        kids = new ArrayList<TExpression>();
                        children.put(stack.peek(), kids);
                    }
                    kids.add(e);
                }
                stack.push(e);
                Long key = Long.valueOf(((long) start(e) << 32) | (end(e) & 0xffffffffL));
                if (!byRange.containsKey(key) && e.getExpressionType() == EExpressionType.function_t) {
                    byRange.put(key, e);
                }
            }
        }

        /**
         * The outermost expressions strictly inside a range, for a call whose own expression node is not in the
         * tree (its range differs from the call's): a scan of the clause, used only then.
         */
        private List<TExpression> maximalWithin(int from, int to) {
            List<TExpression> out = new ArrayList<TExpression>();
            int lastEnd = -1;
            for (TExpression e : all) { // sorted by start, then end descending
                int es = start(e);
                int ee = end(e);
                if (es < from || ee > to || (es == from && ee == to) || es < lastEnd) {
                    continue;
                }
                out.add(e);
                lastEnd = ee;
            }
            return out;
        }

        /** The expression operands of a call, in text order (Section 5, item 1). */
        List<TExpression> operandsOf(TFunctionCall call, List<int[]> excluded) {
            List<TExpression> out = new ArrayList<TExpression>();
            int callStart = start(call);
            int callEnd = end(call);
            int nameEnd = end(call.getFunctionName());
            TExpression self = byRange.get(Long.valueOf(((long) callStart << 32) | (callEnd & 0xffffffffL)));
            List<TExpression> candidates = self != null ? children.get(self) : null;
            if (candidates == null) {
                candidates = maximalWithin(callStart, callEnd);
            }
            // a child with the same range as the call is the call itself again (a wrapper): use its children
            while (candidates.size() == 1 && start(candidates.get(0)) == callStart && end(candidates.get(0)) == callEnd) {
                List<TExpression> next = children.get(candidates.get(0));
                if (next == null) {
                    return out;
                }
                candidates = next;
            }
            String name = functionName(call);
            for (TExpression e : candidates) {
                int es = start(e);
                if (es < nameEnd || end(e) > callEnd || insideAnyRange(es, excluded) || isWildcard(e)
                        || isKeywordOnly(e)) {
                    continue;
                }
                out.add(e);
            }
            if (!out.isEmpty() && FIRST_IS_DATE_PART.contains(name) && isDatePart(out.get(0))) {
                out.remove(0);
            } else if (!out.isEmpty() && LAST_IS_DATE_PART.contains(name) && isDatePart(out.get(out.size() - 1))) {
                out.remove(out.size() - 1);
            }
            return out;
        }
    }

    private static String functionName(TFunctionCall call) {
        if (call.getFunctionName() == null) {
            return "";
        }
        String name = call.getFunctionName().getObjectString();
        if (name == null || name.isEmpty()) {
            name = call.getFunctionName().toString();
        }
        return name.toUpperCase(Locale.ROOT); // non-identifier-compare: built-in function names
    }

    private static boolean insideAnyRange(int offset, List<int[]> ranges) {
        for (int[] r : ranges) {
            if (r[0] <= offset && offset < r[1]) {
                return true;
            }
        }
        return false;
    }

    /** The {@code *} of {@code COUNT(*)}: a wildcard, decided by the parse (its part token is an asterisk). */
    private static boolean isWildcard(TExpression e) {
        if (e.getStartToken() != null && e.getStartToken() == e.getEndToken()
                && e.getStartToken().tokentype == ETokenType.ttasterisk) {
            return true;
        }
        TObjectName name = e.getObjectOperand();
        return e.getExpressionType() == EExpressionType.simple_object_name_t && name != null
                && name.getPartToken() != null && name.getPartToken().tokentype == ETokenType.ttasterisk;
    }

    /** A date-part name such as {@code day} in {@code DATEADD(day, n, d)}: an unqualified name, not an operand. */
    private static boolean isDatePart(TExpression e) {
        if (e.getExpressionType() != EExpressionType.simple_object_name_t || e.getObjectOperand() == null) {
            return false;
        }
        TObjectName name = e.getObjectOperand();
        if (name.getObjectToken() != null || e.getStartToken() != e.getEndToken()) {
            return false;
        }
        String text = e.getStartToken().getAstext();
        return text != null && DATE_PARTS.contains(text.toUpperCase(Locale.ROOT)); // non-identifier-compare: keyword
    }

    /** A date-part or similar keyword that the grammar wraps in an expression is not an operand. */
    private static boolean isKeywordOnly(TExpression e) {
        TSourceToken st = e.getStartToken();
        TSourceToken et = e.getEndToken();
        if (st == null || st != et) {
            return false;
        }
        return st.tokentype == ETokenType.ttkeyword
                && e.getExpressionType() != EExpressionType.simple_object_name_t
                && e.getExpressionType() != EExpressionType.simple_constant_t;
    }

    private void windowParts(Construct window, TParseTreeNode partition, TParseTreeNode orderBy) {
        if (window == null) {
            return;
        }
        if (partition != null) {
            Construct p = add("PARTITION_BY", 0, partition, window);
            if (p != null && window.scope == null) {
                expressions(p, partition); // a named window: its own clause scope
            }
        }
        if (orderBy != null) {
            Construct o = add("ORDER_BY", 0, orderBy, window);
            if (o != null && window.scope == null) {
                expressions(o, orderBy);
            }
        }
    }

    private void insert(TInsertSqlStatement stmt) {
        with(stmt, root);
        if (stmt.isMultiTableInsert()) {
            // INSERT ALL / INSERT FIRST: sqllr-path-1 has no step for an INTO clause or its WHEN condition (Section 2,
            // item 3); the parse's target table is one of the INTO targets, never TARGET[0] (plan 09 slice 5)
            uncoveredInto(stmt.getInsertIntoValues());
            TPTNodeList conditions = stmt.getInsertConditions();
            for (int i = 0; conditions != null && i < conditions.size(); i++) {
                Object condition = conditions.getElement(i);
                if (condition instanceof TInsertCondition) {
                    markUncovered("MULTI-TABLE INSERT WHEN", (TInsertCondition) condition);
                }
            }
            uncoveredInto(stmt.getElseIntoValues());
            if (stmt.getSubQuery() != null) {
                Construct select = add("SELECT", 0, stmt.getSubQuery(), root);
                if (select != null) {
                    work.push(new Object[] {stmt.getSubQuery(), select});
                }
            }
            return;
        }
        if (stmt.getTargetTable() != null) {
            add("TARGET", 0, stmt.getTargetTable(), root);
        }
        if (stmt.getColumnList() != null && stmt.getColumnList().size() > 0) {
            add("COLUMN_LIST", 0, stmt.getColumnList(), root);
        }
        if (stmt.getSubQuery() != null) {
            Construct select = add("SELECT", 0, stmt.getSubQuery(), root);
            if (select != null) {
                work.push(new Object[] {stmt.getSubQuery(), select});
            }
        }
        if (stmt.getValues() != null) {
            for (int r = 0; r < stmt.getValues().size(); r++) {
                TMultiTarget row = stmt.getValues().getMultiTarget(r);
                expressions(add("VALUES", r, row, root), row);
            }
        }
        if (stmt.getExecuteStmt() != null && isProcedureExecute(stmt.getExecuteStmt())) {
            // INSERT ... EXEC p args: the call is EXECUTE[0] below INSERT[0], its arguments below it (slice 12)
            Construct call = add("EXECUTE", 0, stmt.getExecuteStmt(), root);
            if (call != null) {
                callArgumentSteps(stmt.getExecuteStmt(), call);
            }
        }
        returnedRows(stmt);
    }

    /** The arguments of a call as FUNCTION_ARG[k] below its step, in text order, with their expression steps. */
    private void callArgumentSteps(TCustomSqlStatement call, Construct parent) {
        List<TExpression> args = callArguments(call);
        for (int k = 0; k < args.size(); k++) {
            if (args.get(k) != null) {
                expressions(add("FUNCTION_ARG", k, args.get(k), parent), args.get(k));
            }
        }
    }

    /** The RETURNING or OUTPUT clause RETURNING[0] covers (returnedRows), or null. */
    private TParseTreeNode ownReturning;

    /**
     * The rows an INSERT, UPDATE or DELETE returns (PATH-V1 Section 3.4, plan 09 Section 10 Q6): RETURNING[0] below
     * the statement step over its RETURNING (PostgreSQL, SQLite, Oracle's RETURNING ... INTO) or OUTPUT (SQL Server)
     * clause, with the items' expression steps below it; for OUTPUT ... INTO h, the table as TARGET[0] and its column
     * list as COLUMN_LIST[0] below RETURNING[0]. Oracle's INTO variables are names at RETURNING[0] itself. A statement
     * the parse gives both clauses is left uncovered.
     */
    private void returnedRows(TCustomSqlStatement stmt) {
        TOutputClause output = stmt.getOutputClause();
        TReturningClause returning = stmt.getReturningClause();
        if (output != null && returning != null) {
            return;
        }
        if (output != null) {
            Construct c = add("RETURNING", 0, output, root);
            if (c == null) {
                return;
            }
            ownReturning = output;
            if (output.getSelectItemList() != null) {
                expressions(c, output.getSelectItemList());
            }
            if (output.getIntoTable() != null) {
                add("TARGET", 0, output.getIntoTable(), c);
            }
            if (output.getIntoColumnList() != null && output.getIntoColumnList().size() > 0) {
                add("COLUMN_LIST", 0, output.getIntoColumnList(), c);
            }
        } else if (returning != null) {
            Construct c = add("RETURNING", 0, returning, root);
            if (c == null) {
                return;
            }
            ownReturning = returning;
            if (returning.getResultExprList() != null) {
                expressions(c, returning.getResultExprList());
            }
            if (returning.getColumnValueList() != null) {
                expressions(c, returning.getColumnValueList());
            }
            if (returning.getVariableList() != null) {
                expressions(c, returning.getVariableList());
            }
        }
    }

    /**
     * Every RETURNING and OUTPUT clause of the statement but the one RETURNING[0] covers is not covered: a MERGE's, a
     * nested data-changing statement's (PostgreSQL WITH d AS (DELETE ... RETURNING ...)).
     */
    private void returning(TCustomSqlStatement stmt) {
        final int own = ownReturning == null ? -1 : start(ownReturning);
        stmt.acceptChildren(new TParseTreeVisitor() {
            @Override
            public void preVisit(TReturningClause returning) {
                if (start(returning) != own && !ownedReturnings.contains(Integer.valueOf(start(returning)))) {
                    markUncovered("RETURNING", returning);
                }
            }

            @Override
            public void preVisit(TOutputClause output) {
                if (start(output) != own) {
                    markUncovered("OUTPUT", output);
                }
            }
        });
        if (stmt.getOutputClause() != null && start(stmt.getOutputClause()) != own) {
            markUncovered("OUTPUT", stmt.getOutputClause());
        }
    }

    private void update(TUpdateSqlStatement stmt) {
        with(stmt, root);
        int setAt = offsetOf(statementKeywordAfter(stmt, "SET", -1));
        int fromAt = offsetOf(statementKeywordAfter(stmt, "FROM", setAt));
        TJoinList joins = stmt.getJoins();
        int[] joinRange = joins == null || joins.size() == 0 ? null : joinListRange(joins);
        if (joinRange != null && fromAt >= 0 && joinRange[0] > fromAt) {
            // UPDATE t SET ... FROM u: GSP keeps the FROM list in getJoins()
            fromClause("FROM", joins, fromAt, root);
            if (stmt.getTargetTable() != null) {
                dmlTarget(stmt.getTargetTable());
            }
        } else if (joinRange != null && (setAt < 0 || joinRange[0] < setAt)) {
            // UPDATE t1, t2 SET / UPDATE t1 JOIN t2 ON ... SET: the target list
            fromClause("TARGET", joins, -1, root);
        } else if (stmt.getTargetTable() != null) {
            dmlTarget(stmt.getTargetTable());
        }
        if (stmt.getReferenceJoins() != null && stmt.getReferenceJoins().size() > 0) {
            fromClause("FROM", stmt.getReferenceJoins(), fromAt, root);
        }
        if (stmt.getResultColumnList() != null) {
            int st = setAt >= 0 ? setAt : start(stmt.getResultColumnList());
            expressions(add("SET", 0, st, end(stmt.getResultColumnList()), root), stmt.getResultColumnList());
        }
        if (stmt.getWhereClause() != null) {
            expressions(add("WHERE", 0, stmt.getWhereClause(), root), stmt.getWhereClause());
        }
        dmlRowLimit(stmt, stmt.getOrderByClause(), stmt.getLimitClause());
        returnedRows(stmt);
    }

    /**
     * The ORDER BY and the row limit (LIMIT, TOP) that choose the rows an UPDATE or DELETE changes (MySQL {@code ...
     * ORDER BY b LIMIT 10}, SQL Server {@code TOP (@n)}): ORDER_BY[0] and LIMIT[0] below the statement step, one LIMIT
     * step for every form of the limit (PATH-V1 Section 3.4, plan 09 slice 9-rest).
     */
    private void dmlRowLimit(TCustomSqlStatement stmt, gudusoft.gsqlparser.lineage.v2.shape.TOrderBy orderBy,
            TParseTreeNode limit) {
        if (orderBy != null) {
            expressions(add("ORDER_BY", 0, orderBy, root), orderBy);
        }
        for (TParseTreeNode part : new TParseTreeNode[] {stmt.getTopClause(), limit}) {
            if (part != null) {
                expressions(add("LIMIT", 0, part, root), part);
            }
        }
    }

    /**
     * The token a DELETE writes its target with: the first word after DELETE that is not FROM, ONLY, a TOP clause or
     * a MySQL modifier ({@code DELETE a FROM t a}: {@code a}; {@code DELETE FROM d.t}: {@code d}). Shared by the paths
     * (TARGET[0]) and the statement graph (the anchor of the DELETE's effect), so both read one rule.
     */
    static TSourceToken deleteTarget(TDeleteSqlStatement stmt) {
        TSourceToken t = stmt.getStartToken();
        TSourceToken last = stmt.getEndToken();
        boolean afterDelete = false;
        boolean afterOnly = false;
        int depth = 0;
        int targetDepth = 0;
        while (t != null) {
            String s = t.getAstext();
            if ("(".equals(s)) {
                if (afterDelete && afterOnly && depth == 0) {
                    targetDepth = 1; // PostgreSQL DELETE FROM ONLY (t): the target is inside the parentheses
                }
                depth++;
            } else if (")".equals(s)) {
                depth--;
            } else if (depth == targetDepth && t.tokentype != gudusoft.gsqlparser.ETokenType.ttwhitespace
                    && t.tokentype != gudusoft.gsqlparser.ETokenType.ttreturn
                    && t.tokentype != gudusoft.gsqlparser.ETokenType.ttsimplecomment
                    && t.tokentype != gudusoft.gsqlparser.ETokenType.ttbracketedcomment) {
                if (!afterDelete) {
                    // Teradata abbreviates DELETE as DEL (Codex slice 9 #9)
                    afterDelete = "DELETE".equalsIgnoreCase(s) // non-identifier-compare: SQL keyword text
                            || "DEL".equalsIgnoreCase(s); // non-identifier-compare: SQL keyword text
                } else if (t.tokentype == gudusoft.gsqlparser.ETokenType.ttidentifier
                        || !isDeleteModifier(s)) {
                    return t;
                } else {
                    afterOnly = "ONLY".equalsIgnoreCase(s); // non-identifier-compare: SQL keyword text
                }
            }
            if (t == last) {
                break;
            }
            t = t.getNextTokenInChain();
        }
        return null;
    }

    private static boolean isDeleteModifier(String s) {
        for (String m : new String[] {"FROM", "ONLY", "TOP", "PERCENT", "LOW_PRIORITY", "QUICK", "IGNORE"}) {
            if (m.equalsIgnoreCase(s)) { // non-identifier-compare: SQL keyword text
                return true;
            }
        }
        return false;
    }

    /** The first statement-level keyword token after a UTF-16 offset (or anywhere when the offset is negative). */
    private TSourceToken statementKeywordAfter(TCustomSqlStatement stmt, String keyword, int after) {
        TSourceToken t = stmt.getStartToken();
        TSourceToken last = stmt.getEndToken();
        int depth = 0;
        while (t != null) {
            String s = t.getAstext();
            if ("(".equals(s)) {
                depth++;
            } else if (")".equals(s)) {
                depth--;
            } else if (depth == 0 && keyword.equalsIgnoreCase(s) && offsetOf(t) > after) { // non-identifier-compare: SQL keyword text
                return t;
            }
            if (t == last) {
                break;
            }
            t = t.getNextTokenInChain();
        }
        return null;
    }

    /**
     * TARGET[0] of an UPDATE, DELETE or MERGE, and below it SUBQUERY[0] when the target is a query (an inline view:
     * Oracle UPDATE (SELECT ...) v, DELETE FROM (SELECT ...), MERGE INTO (SELECT ...) d; PATH-V1 Section 3.4, slice 6).
     */
    private Construct dmlTarget(TTable target) {
        Construct c = add("TARGET", 0, target, root);
        if (c != null && target.getSubquery() != null) {
            Construct sub = add("SUBQUERY", 0, target.getSubquery(), c);
            if (sub != null) {
                work.push(new Object[] {target.getSubquery(), sub});
            }
        }
        return c;
    }

    private void uncoveredInto(TPTNodeList list) {
        for (int i = 0; list != null && i < list.size(); i++) {
            Object into = list.getElement(i);
            if (into instanceof TInsertIntoValue) {
                markUncovered("MULTI-TABLE INSERT INTO", (TInsertIntoValue) into);
            }
        }
    }

    private void delete(TDeleteSqlStatement stmt) {
        with(stmt, root);
        TJoinList list = stmt.getReferenceJoins() != null && stmt.getReferenceJoins().size() > 0
                ? stmt.getReferenceJoins() : stmt.getJoins();
        int[] range = list == null || list.size() == 0 ? null : joinListRange(list);
        int targetStart = start(stmt.getTargetTable());
        if (range != null && targetStart >= range[0] && targetStart < range[1]) {
            // SQL Server, Teradata DELETE a FROM t a JOIN ...: the parse's target is the FROM item the written target
            // names, so TARGET[0] is the name written after DELETE and the FROM list is the FROM clause (slice 9)
            TSourceToken written = deleteTarget(stmt);
            int writtenAt = offsetOf(written);
            if (written != null && writtenAt < range[0]) {
                add("TARGET", 0, writtenAt, writtenAt + written.getAstext().length(), root);
            }
            TSourceToken from = null;
            for (TSourceToken t = statementKeywordAfter(stmt, "FROM", -1); t != null && offsetOf(t) < range[0];
                    t = statementKeywordAfter(stmt, "FROM", offsetOf(t))) {
                from = t; // the last FROM before the list
            }
            fromClause("FROM", list, offsetOf(from), root);
            if (stmt.getWhereClause() != null) {
                expressions(add("WHERE", 0, stmt.getWhereClause(), root), stmt.getWhereClause());
            }
            dmlRowLimit(stmt, stmt.getOrderByClause(), stmt.getLimitClause());
            returnedRows(stmt);
            return;
        }
        int targetEnd = end(stmt.getTargetTable());
        int[] targetList = list == stmt.getReferenceJoins() && stmt.getJoins() != null && stmt.getJoins().size() > 1
                ? joinListRange(stmt.getJoins()) : null;
        if (targetList != null && range != null && targetList[1] <= range[0]) {
            // MySQL DELETE t1, t2 FROM ... / DELETE FROM t1, t2 USING ...: the list of tables whose rows are deleted
            // is TARGET[0], as an UPDATE's table list is (PATH-V1 Section 3.4, plan 09 slice 9-rest)
            add("TARGET", 0, targetList[0], targetList[1], root);
            targetEnd = targetList[1];
        } else if (stmt.getTargetTable() != null) {
            dmlTarget(stmt.getTargetTable());
        }
        if (range != null && range[0] >= targetEnd) {
            int usingAt = offsetOf(statementKeywordAfter(stmt, "USING", targetEnd - 1));
            int fromAt = offsetOf(statementKeywordAfter(stmt, "FROM", targetEnd - 1));
            boolean using = usingAt >= 0 && usingAt < range[0] && (fromAt < 0 || usingAt > fromAt || fromAt > range[0]);
            fromClause(using ? "USING" : "FROM", list, using ? usingAt : fromAt, root);
        }
        if (stmt.getWhereClause() != null) {
            expressions(add("WHERE", 0, stmt.getWhereClause(), root), stmt.getWhereClause());
        }
        dmlRowLimit(stmt, stmt.getOrderByClause(), stmt.getLimitClause());
        returnedRows(stmt);
    }

    private void merge(TMergeSqlStatement stmt) {
        with(stmt, root);
        Construct target = stmt.getTargetTable() == null ? null : dmlTarget(stmt.getTargetTable());
        TTable using = stmt.getUsingTable();
        if (using != null) {
            String form = uncoveredTableForm(using);
            if (target != null && start(using) == target.start && end(using) == target.end) {
                markUncovered("MERGE SOURCE (range equals the target)", using);
            } else if (form != null) {
                markUncovered(form, using);
            } else {
                Construct u = add("USING", 0, keywordStart(using, "USING"), end(using), root);
                if (u != null && using.getSubquery() != null) {
                    Construct sub = add("SUBQUERY", 0, using.getSubquery(), u);
                    if (sub != null) {
                        work.push(new Object[] {using.getSubquery(), sub});
                    }
                }
            }
        }
        if (stmt.getCondition() != null) {
            expressions(add("ON", 0, stmt.getCondition(), root), stmt.getCondition());
        }
        if (stmt.getWhenClauses() != null) {
            for (int w = 0; w < stmt.getWhenClauses().size(); w++) {
                TMergeWhenClause when = (TMergeWhenClause) stmt.getWhenClauses().getElement(w);
                Construct wc = add("WHEN", w, when, root);
                if (wc == null) {
                    continue;
                }
                if (when.getCondition() != null) {
                    expressions(wc, when.getCondition());
                }
                // Oracle writes a WHEN clause's condition after its action (UPDATE SET ... WHERE c, DELETE WHERE c,
                // INSERT ... VALUES (...) WHERE c): conditions of the WHEN clause, directly below it (slice 6)
                if (when.getUpdateClause() != null && when.getUpdateClause().getUpdateWhereClause() != null) {
                    expressions(wc, when.getUpdateClause().getUpdateWhereClause());
                }
                if (when.getUpdateClause() != null && when.getUpdateClause().getDeleteWhereClause() != null) {
                    expressions(wc, when.getUpdateClause().getDeleteWhereClause());
                }
                if (when.getInsertClause() != null && when.getInsertClause().getInsertWhereClause() != null) {
                    expressions(wc, when.getInsertClause().getInsertWhereClause());
                }
                if (when.getUpdateClause() != null && when.getUpdateClause().getUpdateColumnList() != null) {
                    expressions(add("SET", 0, when.getUpdateClause().getUpdateColumnList(), wc),
                            when.getUpdateClause().getUpdateColumnList());
                }
                if (when.getInsertClause() != null) {
                    if (when.getInsertClause().getColumnList() != null) {
                        add("COLUMN_LIST", 0, when.getInsertClause().getColumnList(), wc);
                    }
                    if (when.getInsertClause().getValuelist() != null) {
                        expressions(add("VALUES", 0, when.getInsertClause().getValuelist(), wc),
                                when.getInsertClause().getValuelist());
                    }
                }
            }
        }
        if (stmt.getReturningClause() != null) {
            markUncovered("RETURNING", stmt.getReturningClause());
        }
    }

    private void createTable(TCreateTableSqlStatement stmt) {
        with(stmt, root);
        if (stmt.getTargetTable() != null) {
            add("TARGET", 0, stmt.getTargetTable(), root);
        }
        if (stmt.getSubQuery() == null) {
            List<Source> sources = createSources(stmt);
            for (int s = 0; s < sources.size(); s++) {
                Source source = sources.get(s);
                TSourceToken last = source.last;
                int end = offsetOf(last);
                add("SOURCE", s, offsetOf(source.first), end < 0 ? -1
                        : end + (last.getAstext() == null ? 0 : last.getAstext().length()), root);
            }
            return;
        }
        if (stmt.getColumnList() != null && stmt.getColumnList().size() > 0
                && start(stmt.getColumnList()) < start(stmt.getSubQuery())) {
            add("COLUMN_LIST", 0, stmt.getColumnList(), root);
        }
        Construct select = add("SELECT", 0, stmt.getSubQuery(), root);
        if (select != null) {
            work.push(new Object[] {stmt.getSubQuery(), select});
        }
    }

    /**
     * One source a CREATE TABLE without a query copies or reads (PATH-V1 {@code SOURCE[s]}, plan 09 slice 2): the
     * relation of a CLONE ({@link #name}), or a storage location literal ({@link #literal} as written).
     */
    static final class Source {
        final TSourceToken first;
        final TSourceToken last;
        final TObjectName name;
        final String literal;

        Source(TSourceToken first, TSourceToken last, TObjectName name, String literal) {
            this.first = first;
            this.last = last;
            this.name = name;
            this.literal = literal;
        }
    }

    /**
     * The sources of a CREATE TABLE without a query, in text order: the CLONE source; the LOCATION or
     * external_location literal; each URI literal of BigQuery {@code uris} (found among the option's string tokens,
     * as the parse keeps the list as text). The producer reads its sources in this order (StatementGraph), so the
     * index of {@code SOURCE[s]} and the source a statement reads agree.
     */
    static List<Source> createSources(TCreateTableSqlStatement stmt) {
        List<Source> out = new ArrayList<Source>();
        if (stmt.getSubQuery() != null) {
            return out;
        }
        TObjectName clone = stmt.getCloneSourceTable();
        if (clone != null && clone.getStartToken() != null) {
            out.add(new Source(clone.getStartToken(), clone.getEndToken(), clone, null));
        }
        TObjectName location = stmt.getTableLocation();
        if (location != null && location.getStartToken() != null) {
            TSourceToken t = location.getStartToken();
            out.add(new Source(t, t, null, t.getAstext()));
        }
        for (int i = 0; stmt.getTableOptions() != null && i < stmt.getTableOptions().size(); i++) {
            TCreateTableOption option = stmt.getTableOptions().get(i);
            if (option.getCreateTableOptionType() != gudusoft.gsqlparser.ECreateTableOption.etoBigQueryExternal
                    || option.getUris() == null || option.getStartToken() == null || option.getEndToken() == null) {
                continue;
            }
            List<String> uris = option.getUris();
            TSourceToken t = option.getStartToken();
            int k = 0;
            while (t != null && k < uris.size()) {
                if ((t.tokentype == ETokenType.ttsqstring || t.tokentype == ETokenType.ttdqstring)
                        && uris.get(k).equals(t.getAstext())) { // token text: the parse keeps each URI as written
                    out.add(new Source(t, t, null, t.getAstext()));
                    k++;
                }
                if (t == option.getEndToken()) {
                    break;
                }
                t = t.getNextTokenInChain();
            }
        }
        TSourceToken path = optionsPath(stmt);
        if (path != null) {
            out.add(new Source(path, path, null, path.getAstext()));
        }
        Collections.sort(out, new java.util.Comparator<Source>() {
            @Override
            public int compare(Source a, Source b) {
                return Integer.compare(a.first.posinlist, b.first.posinlist);
            }
        });
        return out;
    }

    /**
     * The literal of the {@code path} option of {@code OPTIONS (...)} (Spark SQL, Databricks
     * {@code CREATE TABLE ... USING <format> OPTIONS (path '...')}): where the table's files are. The parse keeps the
     * options as text, so they are read from the tokens before the statement's query, if it has one.
     */
    static TSourceToken optionsPath(TCreateTableSqlStatement stmt) {
        TSourceToken end = stmt.getSubQuery() != null && stmt.getSubQuery().getStartToken() != null
                ? stmt.getSubQuery().getStartToken() : stmt.getEndToken();
        for (TSourceToken t = stmt.getStartToken(); t != null; t = t.getNextTokenInChain()) {
            TSourceToken open = "OPTIONS".equalsIgnoreCase(t.getAstext()) ? nextSolidToken(t) : null; // non-identifier-compare: keyword
            if (open != null && "(".equals(open.getAstext())) {
                int depth = 0;
                for (TSourceToken u = open; u != null && u != end; u = u.getNextTokenInChain()) {
                    if ("(".equals(u.getAstext())) {
                        depth++;
                    } else if (")".equals(u.getAstext())) {
                        if (--depth == 0) {
                            break;
                        }
                    } else if (depth == 1 && isPathKey(u)) {
                        TSourceToken v = nextSolidToken(u);
                        if (v != null && "=".equals(v.getAstext())) {
                            v = nextSolidToken(v);
                        }
                        if (v != null && (v.tokentype == ETokenType.ttsqstring || v.tokentype == ETokenType.ttdqstring)) {
                            return v;
                        }
                    }
                }
            }
            if (t == end) {
                break;
            }
        }
        return null;
    }

    /** An option key {@code path}, written as a word or as a string ({@code 'path'}). */
    private static boolean isPathKey(TSourceToken t) {
        String text = t.getAstext();
        if (text == null) {
            return false;
        }
        if (text.length() == 6 && (text.charAt(0) == '\'' || text.charAt(0) == '"') && text.charAt(5) == text.charAt(0)) {
            text = text.substring(1, 5);
        }
        return "PATH".equalsIgnoreCase(text); // non-identifier-compare: an option key, not an object name
    }

    private static TSourceToken nextSolidToken(TSourceToken token) {
        TSourceToken t = token == null ? null : token.getNextTokenInChain();
        while (t != null && (t.tokentype == ETokenType.ttwhitespace || t.tokentype == ETokenType.ttreturn
                || t.tokentype == ETokenType.ttsimplecomment || t.tokentype == ETokenType.ttbracketedcomment)) {
            t = t.getNextTokenInChain();
        }
        return t;
    }

    private void createView(TCustomSqlStatement stmt, TObjectName name, TParseTreeNode columns,
            TSelectSqlStatement query) {
        with(stmt, root);
        if (name != null) {
            add("TARGET", 0, name, root);
        }
        if (columns != null) {
            add("COLUMN_LIST", 0, columns, root);
        }
        if (query != null) {
            Construct select = add("SELECT", 0, query, root);
            if (select != null) {
                work.push(new Object[] {query, select});
            }
        }
    }

    // ---------------------------------------------------------------------------------------------
    // Finishing: parents, indexes, paths, lookup tree
    // ---------------------------------------------------------------------------------------------

    /** Resolve expression parents, number the counted steps, compute every path and the lookup tree. */
    private void finish() {
        resolveExpressionParents();
        assignPaths();
        buildLookup();
    }

    /** Steps that hold clauses, never a name: an identifier landing on one is in a clause this index does not know. */
    private static final Set<String> BLOCK_STEPS = new HashSet<String>(Arrays.asList("SELECT", "INSERT", "UPDATE",
            "DELETE", "MERGE", "CREATE_TABLE", "CREATE_VIEW", "SUBQUERY", "CTE", "BRANCH", "SET_OP", "WITH"));

    /**
     * Marks every identifier token of the statement that lands directly on a statement or query block step as
     * uncovered: it belongs to a clause GSP parses but this index does not model (Oracle MODEL, FOR UPDATE OF,
     * BigQuery FOR SYSTEM_TIME, table options), so no path of PATH-V1 describes it.
     */
    private void markUnmodelledIdentifiers(TCustomSqlStatement stmt) {
        TSourceToken last = stmt.getEndToken();
        for (TSourceToken t = stmt.getStartToken(); t != null; t = t.getNextTokenInChain()) {
            ETokenType type = t.tokentype;
            if (type == ETokenType.ttidentifier || type == ETokenType.ttdqstring || type == ETokenType.ttdbstring
                    || type == ETokenType.ttbrstring) {
                int o = offsetOf(t);
                if (o >= 0) {
                    Construct innermost = innermost(o);
                    if (innermost != null && BLOCK_STEPS.contains(innermost.code)) {
                        markUncovered("UNMODELLED CLAUSE", o, o + t.getAstext().length());
                    }
                }
            }
            if (t == last) {
                break;
            }
        }
    }

    private Construct innermost(int offset) {
        Construct best = null;
        List<Construct> level = roots;
        while (true) {
            Construct hit = find(level, offset);
            if (hit == null) {
                return best;
            }
            best = hit;
            level = hit.textChildren;
        }
    }

    /**
     * Each expression step's parent is the innermost step of its clause that contains it; a stack sweep over the
     * clause's steps sorted by (start, end descending, rank) finds it in n log n.
     */
    private void resolveExpressionParents() {
        Map<Construct, List<Construct>> byClause = new IdentityHashMap<Construct, List<Construct>>();
        for (Construct c : constructs) {
            Construct clause = c.scope != null ? c.scope
                    : c.parent != null && "WINDOW".equals(c.parent.code) && c.parent.scope != null ? c.parent.scope : null;
            if (clause == null) {
                continue;
            }
            List<Construct> list = byClause.get(clause);
            if (list == null) {
                list = new ArrayList<Construct>();
                byClause.put(clause, list);
            }
            list.add(c);
        }
        for (Map.Entry<Construct, List<Construct>> entry : byClause.entrySet()) {
            Construct clause = entry.getKey();
            List<Construct> list = entry.getValue();
            Collections.sort(list, new Comparator<Construct>() {
                @Override
                public int compare(Construct a, Construct b) {
                    int c = Integer.compare(a.start, b.start);
                    if (c != 0) {
                        return c;
                    }
                    c = Integer.compare(b.end, a.end);
                    if (c != 0) {
                        return c;
                    }
                    c = Integer.compare(rank(a), rank(b));
                    return c != 0 ? c : Integer.compare(a.order, b.order);
                }
            });
            Deque<Construct> stack = new ArrayDeque<Construct>();
            for (Construct c : list) {
                while (!stack.isEmpty() && !stack.peek().containsRange(c)) {
                    stack.pop();
                }
                if (c.parent == null) {
                    c.parent = stack.isEmpty() ? clause : stack.peek();
                }
                stack.push(c);
            }
        }
    }

    /** Nesting rank for equal ranges: an operand step encloses a subquery written as the whole operand. */
    private static int rank(Construct c) {
        return "SUBQUERY".equals(c.code) ? 2 : 1;
    }

    private int depth(Construct c) {
        if (c.depth >= 0) {
            return c.depth;
        }
        int d = 0;
        for (Construct p = c.parent; p != null; p = p.parent) {
            d++;
            if (d > constructs.size()) {
                throw new IllegalStateException("cyclic construct parents");
            }
        }
        c.depth = d;
        return d;
    }

    /**
     * Paths level by level; {@code SUBQUERY[k]} and {@code PIVOT[p]} count the subqueries and the operators directly
     * below the same step, in text order,
     * where "the same step" is its path (TOP, LIMIT, OFFSET and FETCH fragments are one {@code LIMIT[0]} step).
     */
    private void assignPaths() {
        List<Construct> ordered = new ArrayList<Construct>(constructs);
        final Map<Construct, Integer> depths = new IdentityHashMap<Construct, Integer>();
        for (Construct c : ordered) {
            depths.put(c, Integer.valueOf(depth(c)));
        }
        Collections.sort(ordered, new Comparator<Construct>() {
            @Override
            public int compare(Construct a, Construct b) {
                int c = depths.get(a).compareTo(depths.get(b));
                return c != 0 ? c : Integer.compare(a.start, b.start);
            }
        });
        int i = 0;
        while (i < ordered.size()) {
            int d = depths.get(ordered.get(i)).intValue();
            int j = i;
            while (j < ordered.size() && depths.get(ordered.get(j)).intValue() == d) {
                j++;
            }
            Map<String, Integer> counters = new HashMap<String, Integer>();
            for (int k = i; k < j; k++) {
                Construct c = ordered.get(k); // ordered by start within the level
                if (("SUBQUERY".equals(c.code) || "PIVOT".equals(c.code) || "LATERAL".equals(c.code)) && c.index < 0) {
                    // PIVOT[p] counts the operators below the same step, in text order (a chain: PIVOT[0], PIVOT[1])
                    String key = c.code + "|" + (c.parent == null ? "" : c.parent.path);
                    Integer n = counters.get(key);
                    c.index = n == null ? 0 : n.intValue();
                    counters.put(key, Integer.valueOf(c.index + 1));
                }
                c.path = (c.parent == null ? "" : c.parent.path + "/") + c.code + "[" + Math.max(c.index, 0) + "]";
            }
            i = j;
        }
    }

    /** The containment forest of construct ranges, for {@link #anchor} by binary search. */
    private void buildLookup() {
        List<Construct> sorted = new ArrayList<Construct>(constructs);
        Collections.sort(sorted, new Comparator<Construct>() {
            @Override
            public int compare(Construct a, Construct b) {
                int c = Integer.compare(a.start, b.start);
                if (c != 0) {
                    return c;
                }
                c = Integer.compare(b.end, a.end);
                return c != 0 ? c : Integer.compare(depth(a), depth(b));
            }
        });
        Deque<Construct> stack = new ArrayDeque<Construct>();
        for (Construct c : sorted) {
            if (c.end <= c.start) {
                continue; // an empty range contains no offset
            }
            while (!stack.isEmpty() && !stack.peek().containsRange(c)) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                roots.add(c);
            } else {
                stack.peek().textChildren.add(c);
            }
            stack.push(c);
        }
    }

    /** The constructs, for tests: path, start, end. */
    List<String> describe() {
        List<String> out = new ArrayList<String>();
        for (Construct c : constructs) {
            out.add(c.path + " " + c.start + ".." + c.end);
        }
        for (Uncovered u : uncovered) {
            out.add("UNCOVERED " + u.form + " " + u.start + ".." + u.end);
        }
        return out;
    }
}