package gudusoft.gsqlparser.resolver2.namespace;

import gudusoft.gsqlparser.nodes.TCTE;
import gudusoft.gsqlparser.nodes.TObjectName;
import gudusoft.gsqlparser.nodes.TResultColumn;
import gudusoft.gsqlparser.nodes.TResultColumnList;
import gudusoft.gsqlparser.nodes.TTable;
import gudusoft.gsqlparser.resolver2.ColumnLevel;
import gudusoft.gsqlparser.resolver2.matcher.INameMatcher;
import gudusoft.gsqlparser.resolver2.model.ColumnSource;
import gudusoft.gsqlparser.stmt.TSelectSqlStatement;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Namespace representing a Common Table Expression (CTE).
 * Similar to SubqueryNamespace but handles CTE-specific features:
 * - Explicit column list: WITH cte(c1, c2) AS (SELECT ...)
 * - Recursive CTEs
 * - Multiple references within same query
 * - UNION subqueries: columns are pushed through to all UNION branches
 *
 * Example:
 * WITH my_cte(id, name) AS (
 *   SELECT user_id, user_name FROM users
 * )
 * SELECT id, name FROM my_cte;
 */
public class CTENamespace extends AbstractNamespace {

    private final TCTE cte;
    private final String cteName;
    private final TSelectSqlStatement selectStatement;

    /** CTE column list (explicit column names) */
    private final List<String> explicitColumns;

    /** Whether this CTE is recursive */
    private final boolean recursive;

    /** UnionNamespace if this CTE's subquery is a UNION */
    private UnionNamespace unionNamespace;

    /** Inferred columns from star push-down */
    private Map<String, ColumnSource> inferredColumns;

    /** Track inferred column names */
    private Set<String> inferredColumnNames;

    /**
     * The TTable that references this CTE in a FROM clause.
     * Used as fallback for getFinalTable() when there's no underlying physical table.
     * For example: WITH cte AS (SELECT 1 AS col) SELECT col FROM cte
     * The referencing TTable is the 'cte' in the FROM clause.
     */
    private TTable referencingTable;

    // --- perf memo (10x, perf/column-lineage-10x) ---
    // For wide CTE-chain SQL, sync (TSQLResolver2.syncColumnToLegacy) and DataFlowAnalyzer call
    // getFinalTable()/getAllFinalTables() once per column. Before memoization, getAllFinalTables()
    // rebuilt and re-validated a fresh CTENamespace at every CTE-chain level on every call, and
    // getFinalTable()->findTableFromQualifiedStar() re-rendered all W result columns to strings per
    // call => O(W) per call => O(W^2) over W columns (proven O(W^2) via JFR: doValidate->HashMap.put
    // was ~24% of dlineage wall on a wide CTE chain). All three are pure functions of the immutable
    // post-parse AST plus (for getFinalTable/getAllFinalTables) this.referencingTable, whose only
    // mutator is setReferencingTable(). Memoize per instance; invalidate the referencingTable-dependent
    // caches on set. Verified byte-identical over the full dlineage corpus (7,918 files, 0 divergences).
    // Namespaces are single-threaded within one analysis (one analyzer instance per worker thread), so
    // the per-instance caches need no synchronization.
    private boolean qualifiedStarComputed;
    private TTable qualifiedStarCache;
    private boolean finalTableComputed;
    private TTable finalTableCache;
    private boolean allFinalTablesComputed;
    private List<TTable> allFinalTablesCache;

    /**
     * Namespaces for FROM clause tables that support dynamic inference.
     * Used to propagate inferred columns through deeply nested structures.
     * Lazily initialized when needed.
     *
     * Example: WITH cte AS (SELECT * FROM (SELECT * FROM t1 UNION ALL SELECT * FROM t2) sub)
     * The 'sub' subquery namespace is stored here for propagation.
     */
    private List<INamespace> fromClauseNamespaces;

    public CTENamespace(TCTE cte,
                       String cteName,
                       TSelectSqlStatement selectStatement,
                       INameMatcher nameMatcher) {
        super(cte, nameMatcher);
        this.cte = cte;
        this.cteName = cteName;
        this.selectStatement = selectStatement;
        this.explicitColumns = extractExplicitColumns(cte);
        this.recursive = isRecursiveCTE(cte);

        // If the CTE's subquery is a UNION, create a UnionNamespace to handle it
        if (selectStatement != null && selectStatement.isCombinedQuery()) {
            this.unionNamespace = new UnionNamespace(selectStatement, cteName + "_union", nameMatcher);
        }
    }

    public CTENamespace(TCTE cte, String cteName, TSelectSqlStatement selectStatement) {
        this(cte, cteName, selectStatement, null);
    }

    @Override
    public String getDisplayName() {
        return cteName;
    }

    /**
     * Get the TTable that references this CTE in a FROM clause.
     */
    public TTable getReferencingTable() {
        return referencingTable;
    }

    /**
     * {@inheritDoc}
     * For CTENamespace, returns the TTable that references this CTE in the query.
     * This is the immediate source table for columns resolved through this CTE.
     */
    @Override
    public TTable getSourceTable() {
        return referencingTable;
    }

    /**
     * Set the TTable that references this CTE in a FROM clause.
     * Called by ScopeBuilder when a CTE is referenced.
     */
    public void setReferencingTable(TTable table) {
        this.referencingTable = table;
        // getFinalTable()/getAllFinalTables() may return referencingTable as a fallback, so any
        // cached full result is invalidated when the referencing table changes. The
        // qualified-star cache depends only on immutable AST and is left intact.
        this.finalTableComputed = false;
        this.finalTableCache = null;
        this.allFinalTablesComputed = false;
        this.allFinalTablesCache = null;
    }

    /**
     * Whether this (definition) namespace has already been bound to an outer
     * FROM-clause reference. See {@link #createReference()} and Mantis #4545.
     */
    private boolean boundToOuterReference = false;

    public boolean isBoundToOuterReference() {
        return boundToOuterReference;
    }

    public void setBoundToOuterReference(boolean bound) {
        this.boundToOuterReference = bound;
    }

    /**
     * Create an independent per-reference copy of this CTE namespace.
     *
     * <p>The single {@code CTENamespace} registered in the {@code CTEScope}
     * represents the CTE <em>definition</em>. When the same CTE is referenced
     * more than once in a FROM clause with different aliases
     * (e.g. {@code FROM cte a, cte b}), each reference needs its own
     * {@link #referencingTable} so that {@link #getSourceTable()} reports the
     * correct alias. Reusing the single definition instance makes every
     * reference report the <em>last</em> reference's table (Mantis #4545).</p>
     *
     * <p>The returned namespace is a fresh, unvalidated instance built from the
     * same AST ({@code cte}/{@code selectStatement}); its column sources are
     * rebuilt against itself when {@link #validate()} runs, so resolved columns
     * trace back to this reference rather than the shared definition.</p>
     *
     * @return a new {@code CTENamespace} for an additional FROM-clause reference
     */
    public CTENamespace createReference() {
        return new CTENamespace(cte, cteName, selectStatement, nameMatcher);
    }

    @Override
    public TTable getFinalTable() {
        if (finalTableComputed) {
            return finalTableCache;
        }
        TTable computed = computeFinalTable();
        finalTableCache = computed;
        finalTableComputed = true;
        return computed;
    }

    private TTable computeFinalTable() {
        // Trace through the CTE's subquery to find the underlying physical table
        // This is similar to SubqueryNamespace.getFinalTable() but handles CTE chains

        // If this CTE has a UNION subquery, delegate to UnionNamespace
        if (unionNamespace != null) {
            TTable unionTable = unionNamespace.getFinalTable();
            if (unionTable != null) {
                return unionTable;
            }
            // Fallback to referencing table if UNION has no physical tables
            return referencingTable;
        }

        // If no tables in the CTE's SELECT, return the referencing table
        // This handles CTEs like: WITH cte AS (SELECT 1 AS col)
        if (selectStatement == null || selectStatement.tables == null || selectStatement.tables.size() == 0) {
            return referencingTable;
        }

        // Check for qualified star column (e.g., CTE_NAME.*) first
        TTable qualifiedStarTable = findTableFromQualifiedStar();
        if (qualifiedStarTable != null) {
            return qualifiedStarTable;
        }

        // For single-table CTEs, trace to the underlying table
        TTable firstTable = selectStatement.tables.getTable(0);
        if (firstTable == null) {
            return null;
        }

        // If it's a physical table (not a CTE reference), return it
        if (firstTable.getTableType() == gudusoft.gsqlparser.ETableSource.objectname && !firstTable.isCTEName()) {
            return firstTable;
        }

        // If it's a CTE reference, trace through the CTE chain
        if (firstTable.isCTEName() && firstTable.getCTE() != null) {
            return traceTableThroughCTE(firstTable.getCTE());
        }

        // If it's a subquery, trace through it
        if (firstTable.getSubquery() != null) {
            SubqueryNamespace nestedNs = new SubqueryNamespace(
                firstTable.getSubquery(),
                firstTable.getAliasName(),
                nameMatcher
            );
            nestedNs.validate();
            TTable subTable = nestedNs.getFinalTable();
            if (subTable != null) {
                return subTable;
            }
        }

        // If it's a join, get the first base table
        if (firstTable.getTableType() == gudusoft.gsqlparser.ETableSource.join) {
            TTable joinTable = findFirstPhysicalTableFromJoin(firstTable);
            if (joinTable != null) {
                return joinTable;
            }
        }

        // Fallback: return the referencing TTable (the CTE reference in FROM clause)
        // This is used when the CTE doesn't have underlying physical tables,
        // e.g., WITH cte AS (SELECT 1 AS col) - the columns are literals, not from tables
        return referencingTable;
    }

    /**
     * Find the table referenced by a qualified star column in this CTE's SELECT list.
     * Example: SELECT other_cte.* FROM other_cte -> traces to other_cte's underlying table
     */
    private TTable findTableFromQualifiedStar() {
        if (qualifiedStarComputed) {
            return qualifiedStarCache;
        }
        TTable computed = computeTableFromQualifiedStar();
        qualifiedStarCache = computed;
        qualifiedStarComputed = true;
        return computed;
    }

    private TTable computeTableFromQualifiedStar() {
        if (selectStatement == null || selectStatement.getResultColumnList() == null) {
            return null;
        }

        TResultColumnList selectList = selectStatement.getResultColumnList();
        for (int i = 0; i < selectList.size(); i++) {
            TResultColumn resultCol = selectList.getResultColumn(i);
            if (resultCol == null) continue;

            String colStr = resultCol.toString().trim();
            // Check if it's a qualified star (contains . before *)
            if (colStr.endsWith("*") && colStr.contains(".")) {
                int dotIndex = colStr.lastIndexOf('.');
                if (dotIndex > 0) {
                    String tablePrefix = colStr.substring(0, dotIndex).trim();
                    // Find the table with this alias or name
                    TTable matchingTable = findTableByAliasOrName(tablePrefix);
                    if (matchingTable != null) {
                        // If the matching table is a CTE reference, trace through it
                        if (matchingTable.isCTEName() && matchingTable.getCTE() != null) {
                            return traceTableThroughCTE(matchingTable.getCTE());
                        }
                        // If it's a subquery, trace through it
                        if (matchingTable.getSubquery() != null) {
                            SubqueryNamespace nestedNs = new SubqueryNamespace(
                                matchingTable.getSubquery(),
                                matchingTable.getAliasName(),
                                nameMatcher
                            );
                            nestedNs.validate();
                            return nestedNs.getFinalTable();
                        }
                        // If it's a physical table, return it
                        if (matchingTable.getTableType() == gudusoft.gsqlparser.ETableSource.objectname && !matchingTable.isCTEName()) {
                            return matchingTable;
                        }
                    }
                }
            }
        }
        return null;
    }

    /**
     * Find a table in the FROM clause by alias or name.
     */
    private TTable findTableByAliasOrName(String nameOrAlias) {
        if (selectStatement == null || selectStatement.tables == null) {
            return null;
        }

        for (int i = 0; i < selectStatement.tables.size(); i++) {
            TTable table = selectStatement.tables.getTable(i);
            if (table == null) continue;

            // Check alias
            String alias = table.getAliasName();
            if (alias != null && nameMatcher.matches(alias, nameOrAlias)) {
                return table;
            }

            // Check table name
            if (table.getTableName() != null && nameMatcher.matches(table.getTableName().toString(), nameOrAlias)) {
                return table;
            }
        }
        return null;
    }

    /**
     * Trace through a CTE to find its underlying physical table.
     * This handles CTE chains like: CTE1 -> CTE2 -> CTE3 -> physical_table
     */
    private TTable traceTableThroughCTE(TCTE cteNode) {
        return traceTableThroughCTE(cteNode, new HashSet<TCTE>());
    }

    private TTable traceTableThroughCTE(TCTE cteNode, java.util.Set<TCTE> visited) {
        if (cteNode == null || cteNode.getSubquery() == null) {
            return null;
        }

        // Detect circular CTE references
        if (!visited.add(cteNode)) {
            return null;
        }

        TSelectSqlStatement cteSubquery = cteNode.getSubquery();

        // Handle UNION in the CTE
        if (cteSubquery.isCombinedQuery()) {
            // For UNION, trace the left branch
            TSelectSqlStatement leftStmt = cteSubquery.getLeftStmt();
            if (leftStmt != null && leftStmt.tables != null && leftStmt.tables.size() > 0) {
                cteSubquery = leftStmt;
            }
        }

        if (cteSubquery.tables == null || cteSubquery.tables.size() == 0) {
            return null;
        }

        TTable firstTable = cteSubquery.tables.getTable(0);
        if (firstTable == null) {
            return null;
        }

        // If it's a physical table (not CTE), we found it
        if (firstTable.getTableType() == gudusoft.gsqlparser.ETableSource.objectname && !firstTable.isCTEName()) {
            return firstTable;
        }

        // If it's another CTE reference, continue tracing
        if (firstTable.isCTEName() && firstTable.getCTE() != null) {
            return traceTableThroughCTE(firstTable.getCTE(), visited);
        }

        // If it's a subquery, trace through it
        if (firstTable.getSubquery() != null) {
            SubqueryNamespace nestedNs = new SubqueryNamespace(
                firstTable.getSubquery(),
                firstTable.getAliasName(),
                nameMatcher
            );
            nestedNs.validate();
            return nestedNs.getFinalTable();
        }

        // If it's a join, get the first base table
        if (firstTable.getTableType() == gudusoft.gsqlparser.ETableSource.join) {
            return findFirstPhysicalTableFromJoin(firstTable);
        }

        return null;
    }

    /**
     * Find the first physical table from a JOIN expression.
     */
    private TTable findFirstPhysicalTableFromJoin(TTable joinTable) {
        if (joinTable == null || joinTable.getJoinExpr() == null) {
            return null;
        }

        gudusoft.gsqlparser.nodes.TJoinExpr joinExpr = joinTable.getJoinExpr();

        // Check left side first
        TTable leftTable = joinExpr.getLeftTable();
        if (leftTable != null) {
            if (leftTable.getTableType() == gudusoft.gsqlparser.ETableSource.objectname && !leftTable.isCTEName()) {
                return leftTable;
            }
            if (leftTable.isCTEName() && leftTable.getCTE() != null) {
                TTable traced = traceTableThroughCTE(leftTable.getCTE());
                if (traced != null) return traced;
            }
            if (leftTable.getSubquery() != null) {
                SubqueryNamespace nestedNs = new SubqueryNamespace(
                    leftTable.getSubquery(),
                    leftTable.getAliasName(),
                    nameMatcher
                );
                nestedNs.validate();
                return nestedNs.getFinalTable();
            }
            if (leftTable.getTableType() == gudusoft.gsqlparser.ETableSource.join) {
                return findFirstPhysicalTableFromJoin(leftTable);
            }
        }

        // Check right side
        TTable rightTable = joinExpr.getRightTable();
        if (rightTable != null) {
            if (rightTable.getTableType() == gudusoft.gsqlparser.ETableSource.objectname && !rightTable.isCTEName()) {
                return rightTable;
            }
            if (rightTable.isCTEName() && rightTable.getCTE() != null) {
                return traceTableThroughCTE(rightTable.getCTE());
            }
        }

        return null;
    }

    @Override
    public List<TTable> getAllFinalTables() {
        if (allFinalTablesComputed) {
            return allFinalTablesCache;
        }
        List<TTable> computed = computeAllFinalTables();
        // Cache an immutable snapshot so callers cannot mutate the shared result.
        allFinalTablesCache = (computed == null)
            ? null
            : Collections.unmodifiableList(new ArrayList<>(computed));
        allFinalTablesComputed = true;
        return allFinalTablesCache;
    }

    private List<TTable> computeAllFinalTables() {
        // If this CTE has a UNION subquery, delegate to the UnionNamespace
        if (unionNamespace != null) {
            return unionNamespace.getAllFinalTables();
        }

        // Check if this CTE references another CTE (which might be a UNION)
        if (selectStatement != null && selectStatement.tables != null && selectStatement.tables.size() > 0) {
            TTable firstTable = selectStatement.tables.getTable(0);
            if (firstTable != null && firstTable.isCTEName() && firstTable.getCTE() != null) {
                TCTE referencedCTE = firstTable.getCTE();
                if (referencedCTE.getSubquery() != null) {
                    // Create a namespace for the referenced CTE to get its tables
                    CTENamespace referencedNs = new CTENamespace(
                        referencedCTE,
                        referencedCTE.getTableName() != null ? referencedCTE.getTableName().toString() : "cte",
                        referencedCTE.getSubquery(),
                        nameMatcher
                    );
                    referencedNs.validate();
                    // This will trace through the CTE chain to get all tables
                    // including from UNION branches
                    return referencedNs.getAllFinalTables();
                }
            }
        }

        // For non-UNION, non-CTE-reference CTEs, return the single final table
        TTable finalTable = getFinalTable();
        if (finalTable != null) {
            return Collections.singletonList(finalTable);
        }

        return Collections.emptyList();
    }

    @Override
    protected void doValidate() {
        columnSources = new LinkedHashMap<>();

        if (selectStatement == null || selectStatement.getResultColumnList() == null) {
            return;
        }

        TResultColumnList selectList = selectStatement.getResultColumnList();

        // If CTE has explicit column list, use it
        if (!explicitColumns.isEmpty()) {
            validateWithExplicitColumns(selectList);
        } else {
            // No explicit columns, derive from SELECT list
            validateWithImplicitColumns(selectList);
        }
    }

    /**
     * Validate CTE with explicit column list.
     * Example: WITH cte(c1, c2, c3) AS (SELECT a, b, c FROM t)
     *
     * Two cases are handled:
     *
     * 1. **Position-based (Snowflake pattern)**: CTE explicit column list + SELECT *
     *    Example: WITH cte(c1, c2, c3) AS (SELECT * FROM Employees)
     *    - c1/c2/c3 are positional aliases for star expansion
     *    - Without metadata: c1 -> Employees.*, c2 -> Employees.*, c3 -> Employees.*
     *    - With metadata: c1 -> Employees.<col_1>, c2 -> Employees.<col_2>, etc.
     *
     * 2. **Direct mapping**: CTE explicit column list + named columns
     *    Example: WITH cte(c1, c2) AS (SELECT id, name FROM t)
     *    - c1 -> t.id, c2 -> t.name (1:1 positional mapping)
     *
     * @see <a href="star_column_pushdown.md#cte-explicit-column-list--select--snowflake-case">
     *      Documentation: CTE Explicit Column List + SELECT *</a>
     */
    private void validateWithExplicitColumns(TResultColumnList selectList) {
        // Check if the SELECT list contains only star column(s) - the position-based pattern
        StarColumnInfo starInfo = analyzeStarColumns(selectList);

        if (starInfo.isSingleStar()) {
            // Position-based case: CTE(c1,c2,c3) AS (SELECT * FROM t)
            // The column names c1/c2/c3 are positional aliases, not real column names
            handleExplicitColumnsWithStar(starInfo.getStarColumn(), starInfo.getStarQualifier());
        } else {
            // Direct mapping case: CTE(c1,c2) AS (SELECT id, name FROM t)
            // Each explicit column maps to corresponding SELECT list item by position
            handleExplicitColumnsWithDirectMapping(selectList);
        }
    }

    /**
     * Handle CTE explicit columns when SELECT list is a star.
     * This is the position-based (Snowflake) pattern.
     *
     * @param starColumn the star column (* or table.*)
     * @param starQualifier the table qualifier if qualified star (e.g., "src" for "src.*"), or null
     */
    private void handleExplicitColumnsWithStar(TResultColumn starColumn, String starQualifier) {
        // Try ordinal mapping if metadata is available
        List<String> ordinalColumns = tryOrdinalMapping(starQualifier);

        if (ordinalColumns != null && ordinalColumns.size() >= explicitColumns.size()) {
            // Metadata available - use ordinal mapping: c1 -> Employees.<col_1>
            for (int i = 0; i < explicitColumns.size(); i++) {
                String cteColName = explicitColumns.get(i);
                String baseColName = ordinalColumns.get(i);

                ColumnSource source = new ColumnSource(
                    this,
                    cteColName,
                    starColumn,      // Reference to star column
                    1.0,             // High confidence - ordinal mapping from metadata
                    "cte_explicit_column_ordinal:" + baseColName
                );
                columnSources.put(cteColName, source);
            }
        } else {
            // No metadata - fallback to star reference: c1 -> Employees.*
            for (String colName : explicitColumns) {
                ColumnSource source = new ColumnSource(
                    this,
                    colName,
                    starColumn,      // Reference to star column
                    0.8,             // Lower confidence - ordinal mapping unknown
                    "cte_explicit_column_via_star"
                );
                columnSources.put(colName, source);
            }
        }
    }

    /**
     * Handle CTE explicit columns with direct positional mapping to SELECT list.
     *
     * @param selectList the SELECT list to map from
     */
    private void handleExplicitColumnsWithDirectMapping(TResultColumnList selectList) {
        int columnCount = Math.min(explicitColumns.size(), selectList.size());

        for (int i = 0; i < columnCount; i++) {
            String colName = explicitColumns.get(i);
            TResultColumn resultCol = selectList.getResultColumn(i);

            ColumnSource source = new ColumnSource(
                this,
                colName,
                resultCol,
                1.0,  // Definite - direct positional mapping
                "cte_explicit_column"
            );

            columnSources.put(colName, source);
        }
    }

    /**
     * Try to get ordered column names from metadata for ordinal mapping.
     *
     * @param starQualifier the table qualifier (e.g., "src"), or null for unqualified star
     * @return ordered list of column names from metadata, or null if not available
     */
    private List<String> tryOrdinalMapping(String starQualifier) {
        // TODO: When metadata (TSQLEnv/DDL) is available, return ordered column list
        // For now, return null to use the fallback (star reference)
        //
        // Future implementation:
        // 1. Find the source table namespace by starQualifier
        // 2. Get its column sources (which use LinkedHashMap for insertion order)
        // 3. Return the column names in order
        return null;
    }

    /**
     * Analyze star columns in the SELECT list.
     * Determines if the SELECT is a single star column pattern.
     */
    private StarColumnInfo analyzeStarColumns(TResultColumnList selectList) {
        if (selectList == null || selectList.size() == 0) {
            return new StarColumnInfo();
        }

        // Check for single star column pattern
        if (selectList.size() == 1) {
            TResultColumn rc = selectList.getResultColumn(0);
            if (isStarColumn(rc)) {
                String qualifier = getStarQualifier(rc);
                return new StarColumnInfo(rc, qualifier);
            }
        }

        return new StarColumnInfo();
    }

    /**
     * Check if a result column is a star column (* or table.*)
     */
    private boolean isStarColumn(TResultColumn rc) {
        if (rc == null) {
            return false;
        }
        String str = rc.toString();
        return str != null && (str.equals("*") || str.endsWith(".*"));
    }

    /**
     * Get the qualifier from a qualified star (src.* returns "src")
     */
    private String getStarQualifier(TResultColumn rc) {
        if (rc == null) {
            return null;
        }
        String str = rc.toString();
        if (str != null && str.endsWith(".*") && str.length() > 2) {
            return str.substring(0, str.length() - 2);
        }
        return null;
    }

    /**
     * Helper class to hold star column analysis results.
     */
    private static class StarColumnInfo {
        private final TResultColumn starColumn;
        private final String starQualifier;

        StarColumnInfo() {
            this.starColumn = null;
            this.starQualifier = null;
        }

        StarColumnInfo(TResultColumn starColumn, String starQualifier) {
            this.starColumn = starColumn;
            this.starQualifier = starQualifier;
        }

        boolean isSingleStar() {
            return starColumn != null;
        }

        TResultColumn getStarColumn() {
            return starColumn;
        }

        String getStarQualifier() {
            return starQualifier;
        }
    }

    /**
     * Validate CTE without explicit column list.
     * Example: WITH cte AS (SELECT id, name FROM users)
     */
    private void validateWithImplicitColumns(TResultColumnList selectList) {
        for (int i = 0; i < selectList.size(); i++) {
            TResultColumn resultCol = selectList.getResultColumn(i);

            // Determine column name
            String colName = getColumnName(resultCol);
            if (colName == null) {
                colName = "col_" + (i + 1);
            }

            // Create column source
            ColumnSource source = new ColumnSource(
                this,
                colName,
                resultCol,
                1.0,  // Definite - from SELECT list
                "cte_implicit_column"
            );

            columnSources.put(colName, source);
        }
    }

    /**
     * Extract column name from TResultColumn
     */
    private String getColumnName(TResultColumn resultCol) {
        // Check for alias
        if (resultCol.getAliasClause() != null &&
            resultCol.getAliasClause().getAliasName() != null) {
            return resultCol.getAliasClause().getAliasName().toString();
        }

        // Check for simple column reference
        if (resultCol.getExpr() != null) {
            gudusoft.gsqlparser.nodes.TExpression expr = resultCol.getExpr();
            if (expr.getExpressionType() == gudusoft.gsqlparser.EExpressionType.simple_object_name_t) {
                TObjectName objName = expr.getObjectOperand();
                if (objName != null) {
                    return objName.getColumnNameOnly();
                }
            }
        }

        return null;
    }

    /**
     * Extract explicit column list from CTE
     */
    private List<String> extractExplicitColumns(TCTE cte) {
        List<String> columns = new ArrayList<>();

        if (cte != null && cte.getColumnList() != null) {
            for (int i = 0; i < cte.getColumnList().size(); i++) {
                TObjectName colName = cte.getColumnList().getObjectName(i);
                if (colName != null) {
                    columns.add(colName.toString());
                }
            }
        }

        return columns;
    }

    /**
     * Check if this is a recursive CTE
     */
    private boolean isRecursiveCTE(TCTE cte) {
        if (cte == null) {
            return false;
        }
        return cte.isRecursive();
    }

    public TCTE getCTE() {
        return cte;
    }

    @Override
    public TSelectSqlStatement getSelectStatement() {
        return selectStatement;
    }

    @Override
    public boolean hasStarColumn() {
        // If this CTE has a UNION subquery, delegate to the UnionNamespace
        if (unionNamespace != null) {
            return unionNamespace.hasStarColumn();
        }

        if (selectStatement == null || selectStatement.getResultColumnList() == null) {
            return false;
        }

        TResultColumnList selectList = selectStatement.getResultColumnList();
        for (int i = 0; i < selectList.size(); i++) {
            TResultColumn resultCol = selectList.getResultColumn(i);
            if (resultCol != null && resultCol.toString().endsWith("*")) {
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean supportsDynamicInference() {
        return hasStarColumn();
    }

    /**
     * Slice S4 (plan §5.5): a CTE's derived schema is authoritative once the
     * CTE has validated and produced at least one named column source. CTEs
     * with explicit column lists are always FOUND once validated; CTEs that
     * simply propagate {@code SELECT *} produce derived columns from the
     * underlying namespace and only become FOUND when those columns are
     * known. Recursive CTEs and unresolved cyclic references stay
     * METADATA_UNAVAILABLE — S9 will refine this contract.
     */
    @Override
    public MetadataState getMetadataState() {
        ensureValidated();
        if (columnSources != null && !columnSources.isEmpty()) {
            return MetadataState.FOUND;
        }
        return MetadataState.METADATA_UNAVAILABLE;
    }

    @Override
    public boolean addInferredColumn(String columnName, double confidence, String evidence) {
        if (columnName == null || columnName.isEmpty()) {
            return false;
        }

        // Initialize maps if needed
        if (inferredColumns == null) {
            inferredColumns = new LinkedHashMap<>();
        }
        if (inferredColumnNames == null) {
            inferredColumnNames = new HashSet<>();
        }

        // Slice S1: dedupe via matcher-aware helper so per-vendor identifier
        // rules govern collision detection. Without this, BigQuery / MySQL
        // (case-insensitive columns) accept "MyCol" and "MYCOL" as two entries
        // and downstream lookups become non-deterministic. Codex round 2:
        // the storage key is the raw (exposedName) form so two matcher-distinct
        // identifiers that happen to normalize equally (e.g. Postgres quoted
        // "mycol" vs unquoted MYCOL) keep separate entries.
        if (containsColumnByMatcher(columnSources, columnName)) {
            return false;
        }
        if (containsColumnByMatcher(inferredColumns, columnName)) {
            return false;
        }

        // Collect candidate tables - get ALL final tables from the CTE chain
        // This handles both UNION CTEs and CTEs that reference other CTEs
        java.util.List<TTable> candidateTables = new java.util.ArrayList<>();

        // Get all final tables from this CTE's namespace (handles UNION and CTE chains)
        java.util.List<TTable> allTables = this.getAllFinalTables();
        for (TTable table : allTables) {
            if (table != null && !candidateTables.contains(table)) {
                candidateTables.add(table);
            }
        }

        // Create inferred column source WITH candidate tables if applicable
        ColumnSource source = new ColumnSource(
            this,
            columnName,
            null,
            confidence,
            evidence,
            null,  // overrideTable
            (candidateTables != null && !candidateTables.isEmpty()) ? candidateTables : null
        );

        inferredColumns.put(columnName, source);
        inferredColumnNames.add(columnName);

        // Propagate to nested namespaces if this CTE has SELECT * from subqueries/unions
        propagateToNestedNamespaces(columnName, confidence, evidence);

        // NOTE: Propagation to referenced CTEs (CTE chains like cte2 -> cte1) is handled
        // by NamespaceEnhancer.propagateThroughCTEChains() which has access to the actual
        // namespace instances from the scope tree. We don't do it here because creating
        // new CTENamespace instances would not affect the actual instances used for resolution.

        return true;
    }

    /**
     * Propagate an inferred column to nested namespaces.
     *
     * This is a unified algorithm that handles:
     * 1. Direct UNION subqueries (CTE body is a UNION)
     * 2. SELECT * FROM (UNION) patterns
     * 3. SELECT * FROM (subquery) patterns
     * 4. Deeply nested structures with JOINs
     *
     * The propagation is recursive - each namespace that receives the column
     * will further propagate to its own nested namespaces.
     *
     * @param columnName The column name to propagate
     * @param confidence Confidence score
     * @param evidence Evidence string for debugging
     */
    private void propagateToNestedNamespaces(String columnName, double confidence, String evidence) {
        // Case 1: Direct UNION subquery (CTE body is a UNION)
        if (unionNamespace != null) {
            if (gudusoft.gsqlparser.TBaseType.DUMP_RESOLVER_LOG_TO_CONSOLE) {
                System.out.println("[CTENamespace] Propagating '" + columnName + "' to direct unionNamespace in " + cteName);
            }
            unionNamespace.addInferredColumn(columnName, confidence, evidence + "_cte_union_propagate");
            return;
        }

        // Case 2: CTE has SELECT * from nested structures (subqueries, unions in FROM clause)
        // Only propagate if the CTE's SELECT list contains a star column
        if (!hasStarColumn()) {
            if (gudusoft.gsqlparser.TBaseType.DUMP_RESOLVER_LOG_TO_CONSOLE) {
                System.out.println("[CTENamespace] No star column in " + cteName + ", skipping FROM clause propagation");
            }
            return;
        }

        // Get or create namespaces for FROM clause tables
        List<INamespace> fromNamespaces = getOrCreateFromClauseNamespaces();
        if (fromNamespaces.isEmpty()) {
            if (gudusoft.gsqlparser.TBaseType.DUMP_RESOLVER_LOG_TO_CONSOLE) {
                System.out.println("[CTENamespace] No FROM clause namespaces with dynamic inference in " + cteName);
            }
            return;
        }

        // Propagate to each FROM clause namespace
        for (INamespace ns : fromNamespaces) {
            if (ns.supportsDynamicInference()) {
                if (gudusoft.gsqlparser.TBaseType.DUMP_RESOLVER_LOG_TO_CONSOLE) {
                    System.out.println("[CTENamespace] Propagating '" + columnName + "' to FROM clause namespace " +
                        ns.getDisplayName() + " in " + cteName);
                }
                // The nested namespace's addInferredColumn will recursively propagate further
                ns.addInferredColumn(columnName, confidence, evidence + "_cte_from_propagate");
            }
        }
    }

    @Override
    public Set<String> getInferredColumns() {
        if (inferredColumnNames == null) {
            return Collections.emptySet();
        }
        return Collections.unmodifiableSet(inferredColumnNames);
    }

    /**
     * Binding-diagnostic view of the CTE output schema.
     *
     * <p>This deliberately differs from {@link #hasColumn(String)}, which has
     * legacy compatibility fallbacks that may infer hidden base-table columns
     * for lineage. Binding diagnostics need the SQL-visible CTE projection:
     * explicit CTE column names, named projection columns, and star/pushdown
     * inferred output columns are visible; hidden base-table inferences are
     * not.</p>
     */
    public ColumnLevel hasAuthoritativeOutputColumn(String columnName) {
        ensureValidated();

        if (columnName == null || columnName.isEmpty()) {
            return ColumnLevel.MAYBE;
        }

        if (containsColumnByMatcher(columnSources, columnName)) {
            return ColumnLevel.EXISTS;
        }

        if (!explicitColumns.isEmpty()) {
            return ColumnLevel.NOT_EXISTS;
        }

        if (containsAuthoritativeInferredColumn(columnName)) {
            return ColumnLevel.EXISTS;
        }

        if (hasStarColumn()) {
            return ColumnLevel.MAYBE;
        }

        if (columnSources != null && !columnSources.isEmpty()) {
            return ColumnLevel.NOT_EXISTS;
        }

        return ColumnLevel.MAYBE;
    }

    /**
     * Diagnostic-only sibling of the matcher-aware contains check that
     * additionally filters out the legacy {@code inferred_from_cte_base_table}
     * entries (which represent hidden base-table columns, not the CTE's
     * SQL-visible projection). Matches must still respect per-vendor identifier
     * rules so quoted Oracle / Postgres identifiers don't get folded.
     */
    private boolean containsAuthoritativeInferredColumn(String columnName) {
        if (inferredColumns == null || inferredColumns.isEmpty()) {
            return false;
        }
        for (ColumnSource candidate : inferredColumns.values()) {
            // Codex round 1: compare against the exposedName (original case,
            // quotes preserved) instead of the normalized key, so quoted
            // vs unquoted distinctions are honored on Oracle / Postgres /
            // Snowflake / Hive / Teradata.
            String exposed = candidate != null ? candidate.getExposedName() : null;
            if (exposed == null || !nameMatcher.matches(exposed, columnName)) {
                continue;
            }
            String evidence = candidate.getEvidence();
            if ("inferred_from_cte_base_table".equals(evidence)) {
                continue;
            }
            return true;
        }
        return false;
    }

    @Override
    public ColumnLevel hasColumn(String columnName) {
        ensureValidated();

        // Check in explicit columns
        if (containsColumnByMatcher(columnSources, columnName)) {
            return ColumnLevel.EXISTS;
        }

        // Check in inferred columns. The map is raw-keyed (= ColumnSource.
        // exposedName); the matcher-aware helper applies per-dialect rules
        // including SQL Server COLLATION_BASED. Round 2 reverted from
        // normalized keys because two matcher-distinct identifiers can
        // normalize to the same key (Postgres "mycol" vs MYCOL).
        if (containsColumnByMatcher(inferredColumns, columnName)) {
            return ColumnLevel.EXISTS;
        }

        // If has star column, unknown columns MAYBE exist
        if (hasStarColumn()) {
            return ColumnLevel.MAYBE;
        }

        // If the CTE has explicit column definitions like "cte(c1, c2, c3)", then ONLY
        // those columns exist - don't return MAYBE for other columns.
        // This prevents ambiguous resolution when a CTE with explicit columns is joined
        // with another table.
        if (!explicitColumns.isEmpty()) {
            return ColumnLevel.NOT_EXISTS;
        }

        // For CTEs without explicit columns AND without star columns, check if underlying
        // tables might have the column. This handles cases like referencing columns from
        // the CTE's base tables that aren't explicitly selected in the CTE's SELECT list.
        if (selectStatement != null && selectStatement.tables != null) {
            for (int i = 0; i < selectStatement.tables.size(); i++) {
                TTable table = selectStatement.tables.getTable(i);
                if (table != null && table.getTableType() == gudusoft.gsqlparser.ETableSource.objectname) {
                    // The CTE has a base table - column might exist there
                    return ColumnLevel.MAYBE;
                }
            }
        }

        return ColumnLevel.NOT_EXISTS;
    }

    @Override
    public ColumnSource resolveColumn(String columnName) {
        ensureValidated();

        // First check explicit columns
        ColumnSource source = super.resolveColumn(columnName);
        if (source != null) {
            return source;
        }

        // Then check inferred columns. Slice S1 + codex round 2: the map is
        // raw-keyed (= ColumnSource.exposedName), so the exact-match probe
        // is O(1) for the same identifier queried again. For case-only-
        // different references, the matcher loop walks values via
        // getExposedName() so quote state is preserved on quoted-sensitive
        // dialects (Oracle / Postgres / Snowflake / Hive / Teradata).
        if (inferredColumns != null) {
            ColumnSource exact = inferredColumns.get(columnName);
            if (exact != null) {
                return exact;
            }
            for (ColumnSource entry : inferredColumns.values()) {
                String exposed = entry != null ? entry.getExposedName() : null;
                if (exposed != null && nameMatcher.matches(exposed, columnName)) {
                    return entry;
                }
            }
        }

        // If has star column, auto-infer this column
        if (hasStarColumn()) {
            boolean added = addInferredColumn(columnName, 0.8, "auto_inferred_from_reference");
            if (added && inferredColumns != null) {
                return inferredColumns.get(columnName);
            }
        }

        // For CTEs without star columns, check if underlying base tables might have the column.
        // This handles references to columns that aren't explicitly selected in the CTE's SELECT list.
        if (selectStatement != null && selectStatement.tables != null) {
            for (int i = 0; i < selectStatement.tables.size(); i++) {
                TTable table = selectStatement.tables.getTable(i);
                if (table != null && table.getTableType() == gudusoft.gsqlparser.ETableSource.objectname) {
                    // Create an inferred column source that traces to the base table
                    boolean added = addInferredColumn(columnName, 0.6, "inferred_from_cte_base_table");
                    if (added && inferredColumns != null) {
                        return inferredColumns.get(columnName);
                    }
                    break;
                }
            }
        }

        return null;
    }

    /**
     * Get the UnionNamespace if this CTE's subquery is a UNION.
     */
    public UnionNamespace getUnionNamespace() {
        return unionNamespace;
    }

    /**
     * Get or create namespaces for FROM clause tables that support dynamic inference.
     * This handles cases like: WITH cte AS (SELECT * FROM (UNION) sub)
     * where the CTE body is not directly a UNION but contains a subquery with UNION.
     *
     * The namespaces are lazily created and cached for reuse.
     *
     * @return List of namespaces that support dynamic inference (may be empty)
     */
    private List<INamespace> getOrCreateFromClauseNamespaces() {
        if (fromClauseNamespaces != null) {
            return fromClauseNamespaces;
        }

        fromClauseNamespaces = new ArrayList<>();

        if (selectStatement == null || selectStatement.tables == null) {
            return fromClauseNamespaces;
        }

        // Iterate through FROM clause tables and create namespaces for those that
        // could have star columns (subqueries, unions, CTE references)
        for (int i = 0; i < selectStatement.tables.size(); i++) {
            TTable table = selectStatement.tables.getTable(i);
            if (table == null) continue;

            INamespace ns = createNamespaceForTable(table);
            if (ns != null && ns.supportsDynamicInference()) {
                fromClauseNamespaces.add(ns);
            }
        }

        return fromClauseNamespaces;
    }

    /**
     * Create an appropriate namespace for a table in the FROM clause.
     * Handles subqueries (including UNION), CTE references, and joins recursively.
     *
     * @param table The table from the FROM clause
     * @return INamespace for the table, or null if not applicable
     */
    private INamespace createNamespaceForTable(TTable table) {
        if (table == null) return null;

        // Handle subquery tables
        if (table.getSubquery() != null) {
            TSelectSqlStatement subquery = table.getSubquery();
            String alias = table.getAliasName();

            // Check if subquery is a UNION/INTERSECT/EXCEPT
            if (subquery.isCombinedQuery()) {
                UnionNamespace unionNs = new UnionNamespace(subquery, alias, nameMatcher);
                return unionNs;
            } else {
                // Regular subquery - create SubqueryNamespace
                SubqueryNamespace subNs = new SubqueryNamespace(subquery, alias, nameMatcher);
                subNs.validate();
                return subNs;
            }
        }

        // Handle CTE references - these are handled by NamespaceEnhancer.propagateThroughCTEChains()
        // We don't create new CTENamespace here because we need the actual instances from scope tree

        // Handle JOIN tables - recursively collect from join expressions
        if (table.getTableType() == gudusoft.gsqlparser.ETableSource.join) {
            return createNamespaceForJoin(table);
        }

        return null;
    }

    /**
     * Create namespaces for tables within a JOIN expression.
     * Returns a composite namespace that wraps all namespaces from the join.
     *
     * @param joinTable The JOIN table
     * @return INamespace that wraps join namespaces, or null
     */
    private INamespace createNamespaceForJoin(TTable joinTable) {
        if (joinTable == null || joinTable.getJoinExpr() == null) {
            return null;
        }

        gudusoft.gsqlparser.nodes.TJoinExpr joinExpr = joinTable.getJoinExpr();

        // Collect namespaces from both sides of the join
        List<INamespace> joinNamespaces = new ArrayList<>();

        // Left side
        TTable leftTable = joinExpr.getLeftTable();
        if (leftTable != null) {
            INamespace leftNs = createNamespaceForTable(leftTable);
            if (leftNs != null && leftNs.supportsDynamicInference()) {
                joinNamespaces.add(leftNs);
            }
        }

        // Right side
        TTable rightTable = joinExpr.getRightTable();
        if (rightTable != null) {
            INamespace rightNs = createNamespaceForTable(rightTable);
            if (rightNs != null && rightNs.supportsDynamicInference()) {
                joinNamespaces.add(rightNs);
            }
        }

        // If we found namespaces, add them to fromClauseNamespaces directly
        // (we don't create a composite namespace, just add the individual ones)
        if (!joinNamespaces.isEmpty()) {
            fromClauseNamespaces.addAll(joinNamespaces);
        }

        return null; // Individual namespaces added directly to fromClauseNamespaces
    }

    public List<String> getExplicitColumns() {
        return new ArrayList<>(explicitColumns);
    }

    public boolean isRecursive() {
        return recursive;
    }

    @Override
    public String toString() {
        return String.format("CTENamespace(%s, columns=%d, recursive=%s)",
            cteName,
            columnSources != null ? columnSources.size() : explicitColumns.size(),
            recursive
        );
    }
}