package gudusoft.gsqlparser.ir.semantic;

import gudusoft.gsqlparser.EDbVendor;
import gudusoft.gsqlparser.EResolverType;
import gudusoft.gsqlparser.TCustomSqlStatement;
import gudusoft.gsqlparser.TGSqlParser;
import gudusoft.gsqlparser.TStatementList;
import gudusoft.gsqlparser.ir.semantic.binding.RelationBinding;
import gudusoft.gsqlparser.ir.semantic.binding.Resolver2NameBindingProvider;
import gudusoft.gsqlparser.ir.semantic.builder.SemanticIRBuilder;
import gudusoft.gsqlparser.ir.semantic.builder.SemanticIRBuilder.SemanticIRBuildException;
import gudusoft.gsqlparser.ir.semantic.catalog.Catalog;
import gudusoft.gsqlparser.ir.semantic.catalog.CatalogColumn;
import gudusoft.gsqlparser.ir.semantic.catalog.CatalogTable;
import gudusoft.gsqlparser.ir.semantic.export.SemanticIRJsonExporter;
import gudusoft.gsqlparser.sqlenv.TSQLEnv;
import gudusoft.gsqlparser.sqlenv.TSQLTable;
import gudusoft.gsqlparser.stmt.TCreateTableSqlStatement;
import gudusoft.gsqlparser.stmt.TCreateViewSqlStatement;
import gudusoft.gsqlparser.stmt.TDeleteSqlStatement;
import gudusoft.gsqlparser.stmt.TInsertSqlStatement;
import gudusoft.gsqlparser.stmt.TMergeSqlStatement;
import gudusoft.gsqlparser.stmt.TSelectSqlStatement;
import gudusoft.gsqlparser.stmt.TUpdateSqlStatement;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Set;

/**
 * Public service wrapper for the Semantic IR pipeline. Given a SQL
 * string and a vendor (and optionally a catalog), returns an
 * {@link AnalysisResult} carrying the built {@link SemanticProgram},
 * its JSON encoding, and any {@link Diagnostic}s emitted during
 * analysis.
 *
 * <p>Slice 75 introduced the packaging surface; slice 76 added the
 * {@link Catalog} DTO overload so external callers can supply catalog
 * metadata without depending on the internal
 * {@link gudusoft.gsqlparser.sqlenv.TSQLEnv} type. Neither slice
 * changes semantic behaviour — the pipeline is:
 * <ol>
 *   <li>{@link TGSqlParser} with {@link EResolverType#RESOLVER2};</li>
 *   <li>{@link SemanticIRBuilder#build} with a
 *       {@link Resolver2NameBindingProvider} (wired to the catalog
 *       when one is supplied);</li>
 *   <li>{@link SemanticIRJsonExporter#toJson} for the JSON form.</li>
 * </ol>
 *
 * <p>Slice 75 supports a single {@code SELECT} statement per
 * {@link #analyze} call. Parse failures, multi-statement input,
 * non-{@code SELECT} input, and builder rejections all surface as
 * structured {@link Diagnostic}s on the result (never as exceptions
 * for the documented failure modes). Unexpected runtime failures
 * inside the analyzer propagate as {@link RuntimeException}s so
 * bugs fail loudly rather than being silently bound to a stable
 * diagnostic message.
 *
 * <p>External callers should branch on
 * {@link AnalysisResult#isSuccessful()} and pattern-match on
 * {@link Diagnostic#getCode()} ({@link DiagnosticCode} is the
 * stable contract); message text remains user-visible English and
 * may change without notice.
 *
 * <p><b>Overload-resolution note.</b> The two 3-arg overloads accept
 * {@link Catalog} or {@link TSQLEnv}; the types are unrelated, so
 * passing a literal {@code null} third argument is ambiguous at
 * compile time. Callers who have no catalog should use the 2-arg
 * {@link #analyze(String, EDbVendor)} overload.
 *
 * <p>This class is stateless and its static methods are safe to
 * call from multiple threads.
 */
public final class SqlSemanticAnalyzer {

    /**
     * Current JSON schema version emitted by this analyzer.
     *
     * <p>Implemented as a method (not a {@code public static final
     * String} constant) so binary consumers compiled against one
     * version of this library do NOT silently see the old value
     * after a drop-in JAR upgrade — Java compile-time inlining of
     * String constants would otherwise break the version contract
     * (codex diff-review round-1 Q3).
     *
     * <p>The returned value is always equal to
     * {@link SemanticIRJsonExporter#SCHEMA_VERSION}.
     */
    public static String schemaVersion() {
        return SemanticIRJsonExporter.SCHEMA_VERSION;
    }

    private SqlSemanticAnalyzer() {
        // utility — no instances
    }

    /**
     * Convenience overload — equivalent to {@code analyze(sql, vendor, (TSQLEnv) null)}.
     *
     * <p>Use this when no catalog metadata is available. Slice 76
     * extracted the no-catalog delegation through a private helper so
     * the 2-arg call remains unambiguous after the {@link Catalog}
     * overload was added.
     */
    public static AnalysisResult analyze(String sql, EDbVendor vendor) {
        return analyzeInternal(sql, vendor, (TSQLEnv) null);
    }

    /**
     * Analyze a single {@code SELECT} statement using catalog metadata
     * supplied as a {@link TSQLEnv}.
     *
     * <p>Slice 75's original catalog entry point. Retained as the
     * authoritative pipeline input — slice 76's {@link Catalog} overload
     * bridges to a generated {@code TSQLEnv} internally so identifier
     * semantics (case folding, qualifier expansion, vendor rules) flow
     * through one code path only.
     *
     * <p>Failure modes that return a structured result (never throw):
     * <ul>
     *   <li>parse failure ({@code rc != 0}) →
     *       {@link DiagnosticCode#PARSE_FAILED};</li>
     *   <li>empty statement list (parse rc=0 but no statements) →
     *       {@link DiagnosticCode#PARSE_FAILED};</li>
     *   <li>more than one statement →
     *       {@link DiagnosticCode#MULTIPLE_STATEMENTS_NOT_SUPPORTED};</li>
     *   <li>first statement is not a {@link TSelectSqlStatement} →
     *       {@link DiagnosticCode#STATEMENT_KIND_NOT_SUPPORTED};</li>
     *   <li>builder rejection
     *       ({@link SemanticIRBuildException}) → the diagnostic from
     *       the exception.</li>
     * </ul>
     *
     * <p>Genuine programming errors throw
     * {@link IllegalArgumentException} (null {@code sql} or null
     * {@code vendor}). Unexpected {@link RuntimeException}s from the
     * builder propagate to the caller.
     *
     * @param sql     non-null SQL text (single statement; trailing
     *                statements yield {@link DiagnosticCode#MULTIPLE_STATEMENTS_NOT_SUPPORTED})
     * @param vendor  non-null vendor enum
     * @param catalog optional {@link TSQLEnv} for catalog-backed
     *                resolution; pass {@code null} to disable
     *                catalog lookups (star expansion and similar
     *                catalog-required features will be rejected
     *                with their existing slice-58 / 66 diagnostics).
     *                See the overload-resolution note in the class
     *                javadoc — to pass a literal null, use the 2-arg
     *                {@link #analyze(String, EDbVendor)} overload
     *                instead.
     * @return immutable result with program, json, and diagnostics
     */
    public static AnalysisResult analyze(String sql, EDbVendor vendor,
                                         TSQLEnv catalog) {
        return analyzeInternal(sql, vendor, catalog);
    }

    /**
     * Slice 76 — analyze a single {@code SELECT} statement using
     * catalog metadata supplied as a {@link Catalog} DTO instead of a
     * {@code TSQLEnv}.
     *
     * <p>The DTO is converted to a {@code TSQLEnv} internally; all
     * resolver / identifier behaviour is identical to the
     * {@code TSQLEnv}-flavored overload. The point of this overload is
     * purely to keep the internal {@code TSQLEnv} type off the public
     * API surface for external callers.
     *
     * <p>A {@code null} {@code Catalog} is treated as "no catalog"
     * (equivalent to the 2-arg {@link #analyze(String, EDbVendor)}
     * overload). Note that to pass a literal {@code null} you must use
     * the 2-arg overload — see the overload-resolution note in the
     * class javadoc.
     *
     * @param sql     non-null SQL text
     * @param vendor  non-null vendor enum
     * @param catalog optional DTO catalog (may be {@code null} when the
     *                caller has already typed the reference as
     *                {@code Catalog})
     * @return immutable result with program, json, and diagnostics
     * @since slice 76
     */
    public static AnalysisResult analyze(String sql, EDbVendor vendor,
                                         Catalog catalog) {
        // Validate sql/vendor first so the no-catalog branch matches
        // the 2-arg overload's contract exactly (null sql/vendor throws
        // BEFORE we touch the catalog).
        if (sql == null) {
            throw new IllegalArgumentException("sql must not be null");
        }
        if (vendor == null) {
            throw new IllegalArgumentException("vendor must not be null");
        }
        TSQLEnv env = (catalog == null) ? null : bridgeToTSQLEnv(catalog, vendor);
        AnalysisResult base = analyzeInternal(sql, vendor, env);
        // Slice 77 — catalog-miss WARN diagnostics. The walk only fires
        // when (a) a non-null Catalog was supplied (this overload only),
        // (b) the analyzer otherwise succeeded (program/JSON built; no
        // ERROR-severity diagnostics). The TSQLEnv-flavored overload
        // does NOT route through this walk — pre-slice-76 callers do
        // not observe a behavior change.
        if (catalog == null || !base.isSuccessful()) {
            return base;
        }
        List<Diagnostic> warnings = collectCatalogMissWarnings(
                base.getProgram(), catalog);
        if (warnings.isEmpty()) {
            return base;
        }
        List<Diagnostic> merged = new ArrayList<>(
                base.getDiagnostics().size() + warnings.size());
        merged.addAll(base.getDiagnostics());
        merged.addAll(warnings);
        return new AnalysisResult(base.getSchemaVersion(), base.getProgram(),
                base.getJson(), merged);
    }

    /**
     * Slice 76 internal pipeline. The three public overloads delegate
     * here with explicit typing to defeat overload-resolution
     * ambiguity for {@code null} arguments (codex plan-review round 2).
     */
    private static AnalysisResult analyzeInternal(String sql, EDbVendor vendor,
                                                  TSQLEnv catalog) {
        // IllegalArgumentException — not NPE — matches the javadoc
        // contract; codex diff-review (slice 75) round-1 Q4 flagged
        // Objects.requireNonNull as enshrining the wrong exception
        // type in the public API.
        if (sql == null) {
            throw new IllegalArgumentException("sql must not be null");
        }
        if (vendor == null) {
            throw new IllegalArgumentException("vendor must not be null");
        }

        TGSqlParser parser = new TGSqlParser(vendor);
        parser.setResolverType(EResolverType.RESOLVER2);
        if (catalog != null) {
            parser.setSqlEnv(catalog);
        }
        parser.sqltext = sql;

        int rc = parser.parse();
        if (rc != 0) {
            String errorMessage = parser.getErrormessage();
            if (errorMessage == null || errorMessage.isEmpty()) {
                errorMessage = "parser returned non-zero rc=" + rc;
            }
            return rejectionResult(Diagnostic.error(
                    DiagnosticCode.PARSE_FAILED,
                    "SQL parse failed: " + errorMessage));
        }

        TStatementList stmts = parser.sqlstatements;
        if (stmts == null || stmts.size() == 0) {
            return rejectionResult(Diagnostic.error(
                    DiagnosticCode.PARSE_FAILED,
                    "SQL parse returned no statements"));
        }
        if (stmts.size() > 1) {
            return rejectionResult(Diagnostic.error(
                    DiagnosticCode.MULTIPLE_STATEMENTS_NOT_SUPPORTED,
                    "SqlSemanticAnalyzer.analyze supports exactly one "
                            + "statement per call; received " + stmts.size()));
        }

        TCustomSqlStatement first = stmts.get(0);
        // Slice 78 — admit single-target INSERT INTO target SELECT in
        // addition to standalone SELECT. Slice 79 (D3) adds CTAS
        // (TCreateTableSqlStatement) and CREATE VIEW
        // (TCreateViewSqlStatement). Slice 80 (D9) adds single-target
        // UPDATE (TUpdateSqlStatement). Slice 81 (D11) adds single-
        // target DELETE (TDeleteSqlStatement). Slice 94 (D6) adds
        // single-target MERGE (TMergeSqlStatement). The builders
        // themselves reject VALUES / DEFAULT VALUES / Oracle INSERT
        // ALL / Hive multi-insert with structured INSERT_* codes;
        // CREATE TABLE / CREATE VIEW without AS SELECT reject with
        // CREATE_AS_NO_SOURCE_SELECT; joined / cross-table UPDATE and
        // other UPDATE shapes reject with UPDATE_* codes; joined /
        // multi-target DELETE and other DELETE shapes reject with
        // DELETE_* codes; MERGE shapes outside the slice-94 skeleton
        // reject with MERGE_* codes. Remaining DDL (CREATE INDEX,
        // CREATE PROCEDURE, etc.) still reject here with
        // STATEMENT_KIND_NOT_SUPPORTED until a later slice.
        boolean isSelect = first instanceof TSelectSqlStatement;
        boolean isInsert = first instanceof TInsertSqlStatement;
        boolean isCreateTable = first instanceof TCreateTableSqlStatement;
        boolean isCreateView = first instanceof TCreateViewSqlStatement;
        boolean isUpdate = first instanceof TUpdateSqlStatement;
        boolean isDelete = first instanceof TDeleteSqlStatement;
        boolean isMerge = first instanceof TMergeSqlStatement;
        if (!isSelect && !isInsert && !isCreateTable && !isCreateView
                && !isUpdate && !isDelete && !isMerge) {
            return rejectionResult(Diagnostic.error(
                    DiagnosticCode.STATEMENT_KIND_NOT_SUPPORTED,
                    "SqlSemanticAnalyzer.analyze supports SELECT, INSERT, "
                            + "UPDATE, DELETE, MERGE, CREATE TABLE AS SELECT, "
                            + "and CREATE VIEW AS SELECT; received "
                            + first.getClass().getSimpleName()));
        }

        Resolver2NameBindingProvider provider = (catalog != null)
                ? new Resolver2NameBindingProvider(catalog)
                : new Resolver2NameBindingProvider();

        SemanticProgram program;
        try {
            if (isSelect) {
                program = SemanticIRBuilder.build((TSelectSqlStatement) first, provider);
            } else if (isInsert) {
                program = SemanticIRBuilder.buildInsert((TInsertSqlStatement) first, provider);
            } else if (isCreateTable) {
                program = SemanticIRBuilder.buildCreateTable(
                        (TCreateTableSqlStatement) first, provider);
            } else if (isCreateView) {
                program = SemanticIRBuilder.buildCreateView(
                        (TCreateViewSqlStatement) first, provider);
            } else if (isUpdate) {
                program = SemanticIRBuilder.buildUpdate(
                        (TUpdateSqlStatement) first, provider);
            } else if (isDelete) {
                program = SemanticIRBuilder.buildDelete(
                        (TDeleteSqlStatement) first, provider);
            } else {
                program = SemanticIRBuilder.buildMerge(
                        (TMergeSqlStatement) first, provider);
            }
        } catch (SemanticIRBuildException ex) {
            return rejectionResult(ex.getDiagnostic());
        }

        String json = SemanticIRJsonExporter.toJson(program);
        return new AnalysisResult(schemaVersion(), program, json,
                Collections.<Diagnostic>emptyList());
    }

    /**
     * Slice 76 bridge — translate a {@link Catalog} DTO into a fresh
     * {@link TSQLEnv} so the rest of the pipeline (resolver,
     * identifier service, star expansion via {@code searchTable}) is
     * unchanged.
     *
     * <p>Allocates a new anonymous {@code TSQLEnv} subclass with an
     * empty {@code initSQLEnv()} for each call — codex round-1 Q5
     * verdict: rebuild on every call. The bridge is cheap (one
     * subclass instantiation + N table registrations), Catalog
     * instances are small, and memoization would introduce
     * thread-safety / stale-state risks for no measurable gain.
     */
    private static TSQLEnv bridgeToTSQLEnv(Catalog catalog, EDbVendor vendor) {
        TSQLEnv env = new TSQLEnv(vendor) {
            @Override public void initSQLEnv() {}
        };
        for (CatalogTable table : catalog.getTables()) {
            // fromDDL=false so TSQLEnv.addTable does not gate the
            // registration behind isEnableGetMetadataFromDDL().
            TSQLTable tbl = env.addTable(table.getName(), false);
            if (tbl == null) {
                // Defensive: TSQLEnv.addTable returns null only when
                // fromDDL=true AND enableGetMetadataFromDDL=false; we
                // pass fromDDL=false so this path should be
                // unreachable. Skip silently to keep slice 76 a
                // pure-packaging slice.
                continue;
            }
            for (CatalogColumn column : table.getColumns()) {
                tbl.addColumn(column.getName());
            }
        }
        return env;
    }

    /**
     * Slice 79 — kind-aware WARN message for a missing-target catalog
     * miss. Mirrors the slice-77 FROM-relation walk's wording style.
     * Falls back to a generic "target relation '...'" label when the
     * statement kind is not one of the known write-side kinds.
     * Slice 80 adds the {@code "UPDATE"} branch; slice 81 adds the
     * {@code "DELETE"} branch alongside the existing INSERT /
     * CREATE_TABLE / CREATE_VIEW / UPDATE kinds. Slice 94 adds the
     * {@code "MERGE"} branch.
     */
    private static String targetWarnMessage(String stmtKind, String relName) {
        String label;
        if ("INSERT".equals(stmtKind)) {
            label = "INSERT target";
        } else if ("CREATE_TABLE".equals(stmtKind)) {
            label = "CTAS target";
        } else if ("CREATE_VIEW".equals(stmtKind)) {
            label = "CREATE VIEW target";
        } else if ("UPDATE".equals(stmtKind)) {
            label = "UPDATE target";
        } else if ("DELETE".equals(stmtKind)) {
            label = "DELETE target";
        } else if ("MERGE".equals(stmtKind)) {
            label = "MERGE target";
        } else {
            // Defensive — only INSERT / CREATE_TABLE / CREATE_VIEW /
            // UPDATE / DELETE / MERGE statements set target on
            // StatementGraph, but future statement kinds may also
            // carry one.
            label = "target";
        }
        return label + " relation '" + relName
                + "' is not declared in the supplied catalog";
    }

    private static AnalysisResult rejectionResult(Diagnostic d) {
        List<Diagnostic> list = new ArrayList<>(1);
        list.add(d);
        return new AnalysisResult(schemaVersion(), null, null, list);
    }

    /**
     * Slice 77 — walk the built {@link SemanticProgram} and report
     * FROM relations that the supplied {@link Catalog} DTO does not
     * declare. The walk satisfies the relation half of §8.1.4 row C3's
     * "missing table/column can be diagnosed" requirement.
     *
     * <p>Column-miss is intentionally NOT a slice-77 WARN: when the
     * catalog declares the relation but not a referenced column, the
     * {@code TSQLResolver2} pipeline already rejects with
     * {@link DiagnosticCode#COLUMN_BINDING_NON_EXACT} (the resolver's
     * NOT_FOUND status surfaces as that ERROR). Callers can pattern-
     * match on {@code COLUMN_BINDING_NON_EXACT} with a non-null
     * {@code Catalog} supplied to detect that case; lifting it to a
     * WARN would require relaxing the resolver, which is a larger
     * design change deferred to a future slice.
     *
     * <p>Emitted relation-miss diagnostics are {@link Severity#WARN
     * WARN}-severity so {@link AnalysisResult#isSuccessful()} continues
     * to return {@code true}; consumers pattern-match on
     * {@link DiagnosticCode#RELATION_NOT_FOUND_IN_CATALOG}.
     *
     * <p>Matching rules:
     * <ul>
     *   <li>Only {@link RelationKind#TABLE} relations are checked.
     *       CTE / SUBQUERY / UNION / OUTER_REFERENCE bindings have no
     *       catalog presence by construction.</li>
     *   <li>Relation match: case-insensitive bare-name on
     *       {@link RelationBinding#getQualifiedName()}. The bridge in
     *       {@link #bridgeToTSQLEnv} routes through TSQLEnv identifier
     *       folding, and {@code Resolver2NameBindingProvider.bindRelation}
     *       returns the AST spelling — case-insensitive matching keeps
     *       the WARN consistent with the resolver's actual lookup.</li>
     *   <li>Dedup: same missing relation referenced from multiple
     *       statements emits one warning.</li>
     * </ul>
     *
     * <p>Each {@link StatementGraph} in {@link SemanticProgram#getStatements()}
     * is walked once at the top level; CTE / scalar-subquery /
     * set-op-branch bodies are emitted as their own statements before
     * the outer SELECT (see {@code SemanticIRBuilder}'s extraction
     * helpers), so a single flat iteration here covers every built
     * statement.
     */
    private static List<Diagnostic> collectCatalogMissWarnings(
            SemanticProgram program, Catalog catalog) {
        if (program == null || catalog == null) {
            return Collections.emptyList();
        }
        // Build a case-insensitive bare-name index of the catalog DTO
        // once per analyze() call. First-match wins on duplicate names
        // (matches Catalog.findTable's first-match contract; the DTO
        // itself does not currently enforce table-name uniqueness).
        Set<String> tableNameKeys = new HashSet<>();
        for (CatalogTable t : catalog.getTables()) {
            if (t != null) {
                tableNameKeys.add(t.getName().toLowerCase(Locale.ROOT));
            }
        }
        List<Diagnostic> out = new ArrayList<>();
        // Dedup ACROSS the whole program: a CTE body and the outer
        // SELECT both referencing the same missing relation should not
        // double-fire. Keys are case-insensitive on the qualifier.
        Set<String> emitted = new HashSet<>();
        // Slice 83 — two-pass walk to generalise slice 82's
        // within-statement target-before-relations ordering to
        // cross-statement ordering. Pass 1 walks every statement's
        // target; pass 2 walks every statement's TABLE-kind relations.
        // The flat `emitted` set carries dedup across passes so a
        // target-side miss always shadows a same-named FROM-side miss,
        // regardless of which statement carries the FROM-side miss.
        //
        // Concretely: MSSQL `UPDATE t SET ... FROM t JOIN (SELECT c FROM t) sub
        // ON ...` extracts the inner SELECT as a separate statement with
        // relations=[t] (TABLE-kind). Without the two-pass walk, the
        // single-pass would process the SELECT first, emit "FROM
        // relation 't' …" for t, and then skip the UPDATE-target-`t`
        // because 't' is already in `emitted`. The kind-aware
        // "UPDATE target relation 't' …" message would never fire.
        //
        // Slices 77-82 invariants preserved by the two-pass walk:
        //  - SELECT has target=null → pass 1 is a no-op for SELECT.
        //  - INSERT / CTAS / CREATE VIEW carry SUBQUERY-kind relations
        //    → skipped by the kind filter in pass 2 (no collision).
        //  - Single-target UPDATE / DELETE (slice 80 / 81) carry
        //    empty relations[] → no collision possible.
        //  - Joined UPDATE (slice 82) within-statement: pass 1 walks
        //    target first, pass 2 walks the same statement's relations
        //    and finds the target's name already in `emitted` → skip.
        //    Identical to slice 82's within-statement ordering.

        // Pass 1: walk every statement's target across the whole
        // program. A target-side miss wins over a same-named
        // FROM-side miss in any statement.
        for (StatementGraph stmt : program.getStatements()) {
            TargetRelation target = stmt.getTarget();
            if (target == null) continue;
            RelationBinding tb = target.getBinding();
            String tn = tb.getQualifiedName();
            String tkey = tn.toLowerCase(Locale.ROOT);
            if (!tableNameKeys.contains(tkey) && emitted.add(tkey)) {
                out.add(Diagnostic.warn(
                        DiagnosticCode.RELATION_NOT_FOUND_IN_CATALOG,
                        targetWarnMessage(stmt.getKind(), tn)));
            }
        }
        // Pass 2: walk every statement's TABLE-kind relations across
        // the whole program. Targets emitted in pass 1 dedup these
        // entries via the shared `emitted` set.
        for (StatementGraph stmt : program.getStatements()) {
            for (RelationSource rs : stmt.getRelations()) {
                RelationBinding b = rs.getBinding();
                if (b == null || b.getKind() != RelationKind.TABLE) {
                    continue;
                }
                String tableName = b.getQualifiedName();
                String key = tableName.toLowerCase(Locale.ROOT);
                if (tableNameKeys.contains(key)) {
                    continue;
                }
                if (emitted.add(key)) {
                    out.add(Diagnostic.warn(
                            DiagnosticCode.RELATION_NOT_FOUND_IN_CATALOG,
                            "FROM relation '" + tableName
                                    + "' is not declared in the supplied catalog"));
                }
            }
        }
        return out;
    }
}