// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.

import {
    Grammar,
    GrammarRule,
    GrammarPart,
    StringPart,
    VarStringPart,
    VarNumberPart,
    RulesPart,
    PhraseSetPart,
    CompiledSpacingMode,
    getCapturedVariableName,
} from "./grammarTypes.js";
import { NFA, NFABuilder } from "./nfa.js";
import {
    parseValueExpression,
    compileValueExpression,
    ValueExpression,
} from "./environment.js";
import { normalizeToken } from "./nfaMatcher.js";

// Scripts that require a word-boundary separator between adjacent tokens.
// CJK and other logographic/syllabic scripts are NOT included — no separator needed.
// Must be kept in sync with the equivalent regex in grammarMatcher.ts.
const _wordBoundaryScriptRe =
    /\p{Script=Latin}|\p{Script=Cyrillic}|\p{Script=Greek}|\p{Script=Armenian}|\p{Script=Georgian}|\p{Script=Hangul}|\p{Script=Arabic}|\p{Script=Hebrew}|\p{Script=Devanagari}|\p{Script=Bengali}|\p{Script=Tamil}|\p{Script=Telugu}|\p{Script=Kannada}|\p{Script=Malayalam}|\p{Script=Gujarati}|\p{Script=Gurmukhi}|\p{Script=Oriya}|\p{Script=Sinhala}|\p{Script=Ethiopic}|\p{Script=Mongolian}/u;

/**
 * Returns true when a token's first character belongs to a word-boundary script
 * (Latin, Cyrillic, Greek, and similar space-separated scripts).
 * Tokens starting with punctuation ("'s", "'t") or CJK characters return false,
 * meaning they can be directly concatenated onto a preceding token without a space.
 */
function requiresWordBoundaryBefore(token: string): boolean {
    if (token.length === 0) return false;
    const code = token.charCodeAt(0);
    if (code < 128)
        return (code >= 65 && code <= 90) || (code >= 97 && code <= 122);
    return _wordBoundaryScriptRe.test(token[0]);
}

/**
 * Context for compiling a rule, including slot information
 */
interface RuleCompilationContext {
    /** Map from variable name to slot index */
    slotMap: Map<string, number>;
    /** Next available slot index */
    nextSlotIndex: number;
    /** Checked variables set from grammar */
    checkedVariables: Set<string> | undefined;
    /** Parent slot index (for nested rule results) */
    parentSlotIndex: number | undefined;
    /** Action name from the rule's value expression (for completion metadata) */
    completionActionName?: string | undefined;
    /** Map from variable name to property path (for completion metadata) */
    completionPropertyPaths?: Map<string, string> | undefined;
    /** Spacing mode for this rule (controls token boundary behaviour) */
    spacingMode?: CompiledSpacingMode;
    /**
     * When set, compileStringPart deposits non-word-starting tokens here so
     * they can be stored as splitCandidates on the rule entry state.
     * Only populated for optional/auto rules; undefined for required/none.
     */
    splitCandidatesCollector?: Set<string> | undefined;
}

/**
 * Extract completion metadata (actionName and variable→propertyPath map) from a value expression.
 * Only works for ActionExpression values; other expression types are ignored.
 */
function extractCompletionMetadata(expr: ValueExpression): {
    actionName?: string;
    propertyPaths: Map<string, string>;
} {
    const propertyPaths = new Map<string, string>();
    if (expr.type !== "action") {
        return { propertyPaths };
    }
    const actionName = expr.actionName;
    // Walk parameters to find variable references
    for (const [paramName, paramExpr] of expr.parameters) {
        collectVariablePaths(
            paramExpr,
            `parameters.${paramName}`,
            propertyPaths,
        );
    }
    return { actionName, propertyPaths };
}

/**
 * Recursively collect variable name → property path mappings from a value expression.
 */
function collectVariablePaths(
    expr: ValueExpression,
    currentPath: string,
    result: Map<string, string>,
): void {
    switch (expr.type) {
        case "variable":
            if (expr.variableName) {
                result.set(expr.variableName, currentPath);
            }
            break;
        case "object":
            for (const [key, value] of expr.properties) {
                collectVariablePaths(value, `${currentPath}.${key}`, result);
            }
            break;
        case "array":
            // Don't append array index — completion metadata uses the base
            // parameter name (e.g. "parameters.artists" not "parameters.artists[0]")
            for (let i = 0; i < expr.elements.length; i++) {
                collectVariablePaths(expr.elements[i], currentPath, result);
            }
            break;
        case "action":
            for (const [key, value] of expr.parameters) {
                collectVariablePaths(
                    value,
                    `${currentPath}.parameters.${key}`,
                    result,
                );
            }
            break;
    }
}

/**
 * Check if a rule is a passthrough rule (single RulesPart without variable or value)
 * Passthrough rules need normalization: <S> = <C>; becomes <S> = $(_result:<C>) -> _result;
 */
function isPassthroughRule(rule: GrammarRule): boolean {
    // A passthrough rule has:
    // 1. No explicit value expression
    // 2. A single part that is a rules reference without a variable
    if (rule.value) {
        return false; // Has explicit value, not a passthrough
    }
    if (rule.parts.length !== 1) {
        return false; // Multiple parts, not a simple passthrough
    }
    const part = rule.parts[0];
    if (part.type !== "rules") {
        return false; // Not a rules reference
    }
    if (part.variable) {
        return false; // Already has a variable binding
    }
    return true;
}

/**
 * Check if a rule is a single-literal rule (e.g., <KnownProgram> = chrome;)
 * Such rules should implicitly produce the matched literal as their value: -> "chrome"
 */
function isSingleLiteralRule(rule: GrammarRule): { literal: string } | false {
    // A single-literal rule has:
    // 1. No explicit value expression
    // 2. Single part that is a string literal (not a variable or rules reference)
    if (rule.value) {
        return false; // Has explicit value
    }
    if (rule.parts.length !== 1) {
        return false; // Multiple parts
    }
    const part = rule.parts[0];
    if (part.type !== "string") {
        return false; // Not a literal
    }
    if (part.value.length === 0) {
        return false; // Empty string, nothing to capture
    }
    // Return the literal value (joined tokens)
    return { literal: part.value.join(" ") };
}

/**
 * Normalize a grammar for matching.
 * This converts:
 * - Passthrough rules: <S> = <C>; becomes <S> = $(_result:<C>) -> _result;
 * - Single-literal rules: <S> = chrome; becomes <S> = chrome -> "chrome";
 *
 * Normalization is done as a preprocessing step so matchers don't need special handling.
 * Both completion-based and NFA-based matchers benefit from this normalization.
 *
 * @param grammar The grammar to normalize
 * @returns A new grammar with normalized rules (original is not modified)
 */
export function normalizeGrammar(grammar: Grammar): Grammar {
    // Cache to avoid re-normalizing shared rule arrays (handles recursive grammars)
    const rulesCache = new Map<GrammarRule[], GrammarRule[]>();
    // Top-level dispatch: re-fold all bucket members + the
    // fallback subset into a flat rules alternation, mirroring
    // `stripDispatch` for nested dispatched RulesParts.  The NFA
    // compiler does its own first-token dispatch via
    // `buildFirstTokenIndex`, so the optimizer-only `dispatch`
    // index adds nothing here.
    let topRules = grammar.alternatives;
    if (grammar.dispatch !== undefined) {
        const expanded: GrammarRule[] = [];
        for (const m of grammar.dispatch) {
            for (const bucket of m.tokenMap.values()) {
                for (const r of bucket) expanded.push(r);
            }
        }
        for (const r of grammar.alternatives) expanded.push(r);
        topRules = expanded;
    }
    const out: Grammar = {
        ...grammar,
        alternatives: normalizeRulesArray(topRules, rulesCache),
    };
    delete out.dispatch;
    return out;
}

/**
 * Normalize an array of rules, using cache to handle circular references.
 */
function normalizeRulesArray(
    rules: GrammarRule[],
    cache: Map<GrammarRule[], GrammarRule[]>,
): GrammarRule[] {
    // Check cache first to handle recursive rule references
    const cached = cache.get(rules);
    if (cached !== undefined) {
        return cached;
    }

    // Create the result array and cache it BEFORE normalizing
    // This handles recursive references: when we encounter the same rules array
    // during normalization, we return the (partially filled) cached array
    const result: GrammarRule[] = [];
    cache.set(rules, result);

    // Now normalize each rule
    for (const rule of rules) {
        result.push(normalizeRule(rule, cache));
    }

    return result;
}

/**
 * Normalize a single rule, recursively normalizing any nested rules.
 */
function normalizeRule(
    rule: GrammarRule,
    cache: Map<GrammarRule[], GrammarRule[]>,
): GrammarRule {
    // First, normalize all nested RulesParts
    const normalizedParts = rule.parts.map((part) =>
        normalizePart(part, cache),
    );

    // Check if this is a passthrough rule that needs transformation
    if (isPassthroughRule(rule)) {
        // Transform: <S> = <C>; becomes <S> = $(_result:<C>) -> _result;
        const rulesPart = normalizedParts[0] as RulesPart;
        return {
            parts: [
                {
                    ...rulesPart,
                    variable: "_result", // Add capture variable
                },
            ],
            value: { type: "variable", name: "_result" }, // Add value expression
            spacingMode: rule.spacingMode,
        };
    }

    // Check if this is a single-literal rule that needs transformation
    const singleLiteral = isSingleLiteralRule(rule);
    if (singleLiteral) {
        // Transform: <S> = chrome; becomes <S> = chrome -> "chrome";
        return {
            parts: normalizedParts,
            value: { type: "literal", value: singleLiteral.literal },
            spacingMode: rule.spacingMode,
        };
    }

    // Not a passthrough or single-literal - return with normalized parts
    return {
        ...rule,
        parts: normalizedParts,
    };
}

/**
 * Normalize a grammar part, recursively normalizing nested rules.
 */
function normalizePart(
    part: GrammarPart,
    cache: Map<GrammarRule[], GrammarRule[]>,
): GrammarPart {
    if (part.type !== "rules") {
        return part; // Only RulesParts need normalization
    }
    if (part.dispatch !== undefined) {
        // Strip the optimizer-only `dispatch` index and re-fold all
        // bucket members into a flat `RulesPart` for NFA
        // compilation.  Dispatch is a filter only - rules retain
        // their original parts including the leading token - so the
        // expansion is just a union in
        // `[...buckets.flat()..., ...rules]` order.  The NFA
        // compiler does its own first-token dispatch via
        // `buildFirstTokenIndex`, so the `dispatch` index adds
        // nothing here.
        return normalizePart(stripDispatch(part), cache);
    }

    // Normalize all nested rules within this RulesPart (using cache)
    return {
        ...part,
        alternatives: normalizeRulesArray(part.alternatives, cache),
    };
}

/**
 * Strip the optimizer-only `dispatch` index from a `RulesPart` and
 * re-fold all bucket members into a flat `rules` alternation in
 * `[...buckets.flat()..., ...rules]` order.  The dispatched part
 * stores the original alternation rules unchanged in its
 * `dispatch[*].tokenMap` buckets and in `rules` (the fallback
 * subset); this is just a union back into the canonical order.
 */
function stripDispatch(part: RulesPart): RulesPart {
    if (part.dispatch === undefined) return part;
    const expanded: GrammarRule[] = [];
    for (const m of part.dispatch) {
        for (const suffixRules of m.tokenMap.values()) {
            for (const r of suffixRules) {
                expanded.push(r);
            }
        }
    }
    for (const r of part.alternatives) expanded.push(r);
    const rulesPart: RulesPart = {
        type: "rules",
        alternatives: expanded,
        name: part.name,
        variable: part.variable,
    };
    if (part.optional) rulesPart.optional = true;
    if (part.repeat) rulesPart.repeat = true;
    if (part.tailCall) rulesPart.tailCall = true;
    return rulesPart;
}

/**
 * Check if a rule is a single-variable rule (e.g., <ArtistName> = $(x:wildcard);)
 * Such rules should implicitly produce their variable's value: -> $(x)
 */
function isSingleVariableRule(rule: GrammarRule): { variable: string } | false {
    // A single-variable rule has:
    // 1. No explicit value expression
    // 2. Single part that is a wildcard or number with a variable
    if (rule.value) {
        return false; // Has explicit value
    }
    if (rule.parts.length !== 1) {
        return false; // Multiple parts
    }
    const part = rule.parts[0];
    if (part.type === "wildcard" || part.type === "number") {
        if (part.variable) {
            return { variable: part.variable };
        }
    }
    return false;
}

/**
 * Collect all variable names from a rule's parts
 * Returns them in order of appearance
 *
 * For passthrough rules (single RulesPart without variable), adds an implicit "_result" variable
 */
function collectVariables(rule: GrammarRule): string[] {
    const variables: string[] = [];
    const seen = new Set<string>();

    // Check for passthrough rule normalization
    if (isPassthroughRule(rule)) {
        // Add implicit variable for passthrough
        variables.push("_result");
        return variables;
    }

    for (const part of rule.parts) {
        // For nested rules, only the RulesPart's own variable is captured
        // here — the matcher writes the nested rule's value into that slot.
        // We don't recurse into the nested rule's inner parts; they live
        // in their own slot maps.
        const v = getCapturedVariableName(part);
        if (v && !seen.has(v)) {
            seen.add(v);
            variables.push(v);
        }
    }

    return variables;
}

/**
 * Create a slot map for a rule's variables
 */
function createRuleSlotMap(rule: GrammarRule): Map<string, number> {
    const variables = collectVariables(rule);
    const slotMap = new Map<string, number>();
    for (let i = 0; i < variables.length; i++) {
        slotMap.set(variables[i], i);
    }
    return slotMap;
}

/**
 * Create a type map for a rule's variables (variable name -> typeName)
 * Used for type conversion during value expression evaluation
 */
function createRuleTypeMap(rule: GrammarRule): Map<string, string> {
    const typeMap = new Map<string, string>();

    function collectFromPart(part: GrammarPart): void {
        switch (part.type) {
            case "wildcard":
                // VarStringPart has variable and typeName
                if (part.variable && part.typeName) {
                    typeMap.set(part.variable, part.typeName);
                }
                break;
            case "number":
                // VarNumberPart has variable, typeName is implicitly "number"
                if (part.variable) {
                    typeMap.set(part.variable, "number");
                }
                break;
            case "rules":
                // RulesPart has nested rules
                if (part.alternatives) {
                    for (const nestedRule of part.alternatives) {
                        for (const nestedPart of nestedRule.parts) {
                            collectFromPart(nestedPart);
                        }
                    }
                }
                break;
            case "string":
                // Optimizer-introduced capture binds the joined literal
                // tokens (a string) to the named slot.
                if (part.variable) {
                    typeMap.set(part.variable, "string");
                }
                break;
            case "phraseSet":
                // Optimizer-introduced capture binds the matched phrase
                // (a string of joined matched tokens) to the named slot.
                if (part.variable) {
                    typeMap.set(part.variable, "string");
                }
                break;
        }
    }

    for (const part of rule.parts) {
        collectFromPart(part);
    }

    return typeMap;
}

/**
 * Compile a Grammar to an NFA
 *
 * This compiler converts token-based grammar rules into an NFA that can be:
 * 1. Interpreted directly for matching (debugging)
 * 2. Converted to a DFA for faster matching
 * 3. Combined with other NFAs for incremental grammar extension
 */

/**
 * Compile a grammar to an NFA
 * @param grammar The grammar to compile
 * @param name Optional name for debugging
 * @returns An NFA representing the grammar
 */
export function compileGrammarToNFA(grammar: Grammar, name?: string): NFA {
    // Normalize grammar first: convert passthrough rules to explicit form
    // <S> = <C>; becomes <S> = $(_result:<C>) -> _result;
    const normalizedGrammar = normalizeGrammar(grammar);

    const builder = new NFABuilder();

    // Create start state
    const startState = builder.createState(false);

    // Create an accepting state that all rules will lead to
    const acceptState = builder.createState(true);

    // Compile each rule as an alternative path from start to accept
    for (
        let ruleIndex = 0;
        ruleIndex < normalizedGrammar.alternatives.length;
        ruleIndex++
    ) {
        const rule = normalizedGrammar.alternatives[ruleIndex];

        // VALIDATION: Multi-term rules MUST have value expressions
        // Single-term rules can omit value expressions (they inherit from the term)
        if (rule.parts.length > 1 && !rule.value) {
            throw new Error(
                `Grammar rule at index ${ruleIndex} has ${rule.parts.length} terms but no value expression. ` +
                    `Multi-term rules must have an explicit value expression (using ->).`,
            );
        }

        // Check for single-variable rules like <ArtistName> = $(x:wildcard);
        // These should implicitly produce their variable's value: -> x
        let effectiveValue = rule.value;
        if (!effectiveValue) {
            const singleVar = isSingleVariableRule(rule);
            if (singleVar) {
                effectiveValue = { type: "variable", name: singleVar.variable };
            }
        }

        const ruleEntry = builder.createState(false);

        // Mark the rule entry state with the rule index
        builder.getState(ruleEntry).ruleIndex = ruleIndex;

        // Create slot map for this rule FIRST (needed to compile value expression)
        const slotMap = createRuleSlotMap(rule);
        // Always set slot info for Start rules — even rules with no variables
        // need an environment so that nested sub-rules (e.g. optional groups
        // normalized into passthrough wrappers) can correctly pop back to the
        // Start rule's environment/actionValue on exit.
        builder.setStateSlotInfo(ruleEntry, slotMap.size, slotMap);

        // Create type map for type conversion during evaluation
        const typeMap = createRuleTypeMap(rule);

        // Compile and set the effective value expression on the state
        // Parse the raw value node, then compile with slot indices
        let completionActionName: string | undefined;
        let completionPropertyPaths: Map<string, string> | undefined;
        if (effectiveValue) {
            const parsedExpr = parseValueExpression(effectiveValue);
            const compiledExpr = compileValueExpression(
                parsedExpr,
                slotMap,
                typeMap,
            );
            builder.getState(ruleEntry).actionValue = compiledExpr;
            // Also store in actionValues array for priority tracking
            builder.setActionValue(ruleIndex, compiledExpr);

            // Extract completion metadata from the parsed (uncompiled) expression
            const meta = extractCompletionMetadata(parsedExpr);
            completionActionName = meta.actionName;
            if (meta.propertyPaths.size > 0) {
                completionPropertyPaths = meta.propertyPaths;
            }
        }

        builder.addEpsilonTransition(startState, ruleEntry);

        // For optional/auto rules, collect split candidates (non-word-starting tokens
        // such as "'s", "'t", or CJK characters) so matchGrammarWithNFA can pre-split
        // fused input tokens (e.g. "Swift's" → ["Swift", "'s"]).
        // required and none rules don't need this: required never fuses tokens;
        // none is handled at compile time by joining segments into one fused token.
        const needsSplitCandidates =
            rule.spacingMode !== "required" && rule.spacingMode !== "none";
        const splitCandidatesCollector: Set<string> | undefined =
            needsSplitCandidates ? new Set<string>() : undefined;

        // Create compilation context with slot information
        const context: RuleCompilationContext = {
            slotMap,
            nextSlotIndex: slotMap.size,
            checkedVariables: normalizedGrammar.checkedVariables,
            parentSlotIndex: undefined,
            completionActionName,
            completionPropertyPaths,
            spacingMode: rule.spacingMode,
            splitCandidatesCollector,
        };

        const ruleEnd = compileRuleFromStateWithSlots(
            builder,
            normalizedGrammar,
            rule,
            ruleEntry,
            acceptState,
            context,
        );

        // Store collected split candidates on the rule entry state so
        // matchGrammarWithNFA can discover them without re-traversing the graph.
        if (splitCandidatesCollector && splitCandidatesCollector.size > 0) {
            builder.getState(ruleEntry).splitCandidates = Array.from(
                splitCandidatesCollector,
            ).sort((a, b) => b.length - a.length); // longest-first for greedy scan
        }

        // If rule didn't connect to accept state, add epsilon transition
        if (ruleEnd !== acceptState) {
            builder.addEpsilonTransition(ruleEnd, acceptState);
        }
    }

    return builder.build(startState, name);
}

/**
 * Compile a single grammar rule starting from a specific state
 * @returns The final state of this rule
 * @deprecated Use compileRuleFromStateWithSlots for new code
 */
function compileRuleFromState(
    builder: NFABuilder,
    grammar: Grammar,
    rule: GrammarRule,
    startState: number,
    finalState: number,
    checkedVariables?: Set<string>,
    overrideVariableName?: string,
): number {
    let currentState = startState;

    // Process each part of the rule sequentially
    for (let i = 0; i < rule.parts.length; i++) {
        const part = rule.parts[i];
        const isLast = i === rule.parts.length - 1;
        const nextState = isLast ? finalState : builder.createState(false);

        currentState = compilePart(
            builder,
            grammar,
            part,
            currentState,
            nextState,
            checkedVariables,
            overrideVariableName,
        );
    }

    return currentState;
}

/**
 * Compile a single grammar rule with slot tracking
 * @returns The final state of this rule
 */
function compileRuleFromStateWithSlots(
    builder: NFABuilder,
    grammar: Grammar,
    rule: GrammarRule,
    startState: number,
    finalState: number,
    context: RuleCompilationContext,
): number {
    let currentState = startState;

    // Process each part of the rule sequentially
    for (let i = 0; i < rule.parts.length; i++) {
        const part = rule.parts[i];
        const isLast = i === rule.parts.length - 1;
        const nextState = isLast ? finalState : builder.createState(false);

        currentState = compilePartWithSlots(
            builder,
            grammar,
            part,
            currentState,
            nextState,
            context,
        );
    }

    return currentState;
}

/**
 * Compile a single grammar part
 * @returns The state after this part
 * @deprecated Use compilePartWithSlots for new code
 */
function compilePart(
    builder: NFABuilder,
    grammar: Grammar,
    part: GrammarPart,
    fromState: number,
    toState: number,
    checkedVariables?: Set<string>,
    overrideVariableName?: string,
): number {
    // Deprecated path has no slot context, so optimizer-introduced
    // captures on string / phraseSet parts (which require a slot to
    // write into) cannot be honored.  Reject loudly rather than silently
    // dropping the binding and producing a wrong action result.
    if (
        (part.type === "string" || part.type === "phraseSet") &&
        part.variable !== undefined
    ) {
        throw new Error(
            `compilePart (deprecated, no slot context) cannot honor capture variable '${part.variable}' on ${part.type}Part — caller must use compilePartWithSlots`,
        );
    }
    switch (part.type) {
        case "string":
            return compileStringPart(builder, part, fromState, toState);

        case "wildcard":
            return compileWildcardPart(
                builder,
                part,
                fromState,
                toState,
                checkedVariables,
                overrideVariableName,
            );

        case "number":
            return compileNumberPart(builder, part, fromState, toState);

        case "rules":
            return compileRulesPart(
                builder,
                grammar,
                part,
                fromState,
                toState,
                checkedVariables,
                overrideVariableName,
            );

        case "phraseSet":
            return compilePhraseSetPartNoSlots(
                builder,
                part,
                fromState,
                toState,
            );

        default:
            throw new Error(`Unknown part type: ${(part as any).type}`);
    }
}

/**
 * Compile a single grammar part with slot tracking
 * @returns The state after this part
 */
function compilePartWithSlots(
    builder: NFABuilder,
    grammar: Grammar,
    part: GrammarPart,
    fromState: number,
    toState: number,
    context: RuleCompilationContext,
): number {
    switch (part.type) {
        case "string":
            return compileStringPart(
                builder,
                part,
                fromState,
                toState,
                context.spacingMode,
                context.splitCandidatesCollector,
                part.variable !== undefined
                    ? context.slotMap.get(part.variable)
                    : undefined,
            );

        case "wildcard":
            return compileWildcardPartWithSlots(
                builder,
                part,
                fromState,
                toState,
                context,
            );

        case "number":
            return compileNumberPartWithSlots(
                builder,
                part,
                fromState,
                toState,
                context,
            );

        case "rules":
            return compileRulesPartWithSlots(
                builder,
                grammar,
                part,
                fromState,
                toState,
                context,
            );

        case "phraseSet":
            return compilePhraseSetPartWithSlots(
                builder,
                part,
                fromState,
                toState,
                context,
            );

        default:
            throw new Error(`Unknown part type: ${(part as any).type}`);
    }
}

/**
 * Compile a phraseSet part.
 *
 * Emits a single "phraseSet" NFA transition from fromState to toState.
 * The NFA interpreter resolves the actual phrases at match time, generating
 * one thread per matching phrase — identical to how entity converters work
 * with skipCount for multi-token spans.
 *
 * PhraseSetParts are always non-optional at this level; optionality is handled
 * by the enclosing RulesPart (e.g., from "(<Polite>)?").
 *
 * Two callers exist:
 *  - `compilePhraseSetPartNoSlots` for the deprecated, slot-less compile
 *    path (rejects optimizer-introduced captures upstream — see
 *    `compilePart`).
 *  - `compilePhraseSetPartWithSlots` for the slot-aware path; when
 *    `part.variable` is set the matched phrase tokens are written as a
 *    joined string into the named slot.  See `tryTransition` in
 *    `nfaInterpreter.ts` for the runtime side.
 */
function compilePhraseSetPartNoSlots(
    builder: NFABuilder,
    part: PhraseSetPart,
    fromState: number,
    toState: number,
): number {
    builder.addPhraseSetTransition(fromState, toState, part.matcherName);
    return toState;
}

function compilePhraseSetPartWithSlots(
    builder: NFABuilder,
    part: PhraseSetPart,
    fromState: number,
    toState: number,
    context: RuleCompilationContext,
): number {
    const slotIndex =
        part.variable !== undefined
            ? context.slotMap.get(part.variable)
            : undefined;
    builder.addPhraseSetTransition(
        fromState,
        toState,
        part.matcherName,
        slotIndex,
    );
    return toState;
}

/**
 * Compile a string part (matches specific tokens).
 *
 * spacing=none   → join all segments into one fused token (compile-time concatenation).
 * optional/auto  → emit individual token transitions as usual, but also register each
 *                  non-word-starting token as a split candidate in the collector so
 *                  matchGrammarWithNFA can pre-split fused input (e.g. "Swift's" or
 *                  "黃色汽車") before running the NFA.
 * required/other → emit individual token transitions unchanged (default behaviour).
 */
function compileStringPart(
    builder: NFABuilder,
    part: StringPart,
    fromState: number,
    toState: number,
    spacingMode?: CompiledSpacingMode,
    splitCandidatesCollector?: Set<string>,
    /**
     * Optional slot to write the joined StringPart value into.  When set
     * (an optimizer-introduced capture), the slot receives
     * `part.value.join(" ")` on the FINAL emitted transition — a single
     * write per StringPart, regardless of how many sub-token transitions
     * the chain emits.  See `tryTransition` in `nfaInterpreter.ts` for the
     * runtime side (slotValue overrides the consumed token).
     */
    captureSlotIndex?: number,
): number {
    // Normalize grammar tokens (lowercase + strip trailing punctuation) so they
    // compare correctly against the normalized input tokens from tokenizeRequest().
    const normalized = part.value
        .map(normalizeToken)
        .filter((t) => t.length > 0);

    if (normalized.length === 0) {
        // Empty string - epsilon transition
        builder.addEpsilonTransition(fromState, toState);
        return toState;
    }

    // The captured slot value is the joined ORIGINAL StringPart tokens (not
    // the normalized ones); this matches what `grammarMatcher.ts` writes via
    // `addValue(state, part.variable, part.value.join(" "))`.
    const captureSlotValue =
        captureSlotIndex !== undefined ? part.value.join(" ") : undefined;

    // spacing=none: concatenate all segments into a single fused token.
    // The grammar author expects the input to contain no spaces between these
    // segments, so we emit one token transition for the concatenated form.
    if (spacingMode === "none") {
        const fused = normalized.join("");
        builder.addTokenTransition(
            fromState,
            toState,
            [fused],
            captureSlotIndex,
            captureSlotValue,
        );
        return toState;
    }

    // optional/auto: collect non-word-starting tokens as split candidates.
    // These will be stored on the rule entry state and used by matchGrammarWithNFA
    // to pre-split fused input tokens before running the NFA interpreter.
    if (splitCandidatesCollector) {
        for (const token of normalized) {
            if (!requiresWordBoundaryBefore(token)) {
                splitCandidatesCollector.add(token);
            }
        }
    }

    // Emit individual token transitions (same as before for required/optional/auto).
    if (normalized.length === 1) {
        builder.addTokenTransition(
            fromState,
            toState,
            normalized,
            captureSlotIndex,
            captureSlotValue,
        );
        return toState;
    }

    // For multiple tokens, create a sequence chain
    // Each token must match in order: state1 --token1--> state2 --token2--> ... --> toState
    // The capture slot (if any) is written only on the final transition so the
    // joined StringPart value is recorded once — same single-write semantics as
    // grammarMatcher.ts's `addValue` for a multi-token literal.
    let currentState = fromState;
    for (let i = 0; i < normalized.length; i++) {
        const token = normalized[i];
        const isLast = i === normalized.length - 1;
        const nextState = isLast ? toState : builder.createState(false);
        if (isLast) {
            builder.addTokenTransition(
                currentState,
                nextState,
                [token],
                captureSlotIndex,
                captureSlotValue,
            );
        } else {
            builder.addTokenTransition(currentState, nextState, [token]);
        }
        currentState = nextState;
    }
    return toState;
}

/**
 * Compile a wildcard part (matches any token, captures to variable)
 * @deprecated Use compileWildcardPartWithSlots for new code
 */
function compileWildcardPart(
    builder: NFABuilder,
    part: VarStringPart,
    fromState: number,
    toState: number,
    checkedVariables?: Set<string>,
    overrideVariableName?: string,
): number {
    // Use override variable name if provided, otherwise use the part's variable name
    // This allows outer rules to override inner rule variable names for proper capture
    const variableName = overrideVariableName ?? part.variable;

    // Determine if this wildcard is checked
    // A wildcard is checked if:
    // 1. It has a non-string typeName (entity type like MusicDevice, Ordinal, etc.)
    // 2. It's in the checkedVariables set (has checked_wildcard paramSpec)
    const hasEntityType =
        part.typeName &&
        part.typeName !== "string" &&
        part.typeName !== "wildcard";
    const hasCheckedParamSpec = checkedVariables?.has(variableName) ?? false;
    const isChecked = hasEntityType || hasCheckedParamSpec;

    if (part.optional) {
        // Optional wildcard: can skip via epsilon or match one or more tokens
        // fromState --epsilon--> toState (skip)
        // fromState --wildcard--> loopState --wildcard--> loopState (consume 1+ tokens)
        //                         loopState --epsilon--> toState (exit)
        builder.addEpsilonTransition(fromState, toState); // Skip option

        const loopState = builder.createState(false);

        // First token: fromState -> loopState
        builder.addWildcardTransition(
            fromState,
            loopState,
            variableName,
            part.typeName,
            isChecked,
        );

        // Loop: loopState -> loopState (consume more tokens)
        builder.addWildcardTransition(
            loopState,
            loopState,
            variableName,
            part.typeName,
            isChecked,
        );

        // Exit: loopState -> toState
        builder.addEpsilonTransition(loopState, toState);

        return toState;
    }

    // Required wildcard - matches one or more tokens
    // Create a loop structure:
    // fromState --wildcard--> loopState --wildcard--> loopState (loop for more tokens)
    //                         loopState --epsilon--> toState (exit after consuming tokens)
    const loopState = builder.createState(false);

    // First token: fromState -> loopState
    builder.addWildcardTransition(
        fromState,
        loopState,
        variableName,
        part.typeName,
        isChecked,
    );

    // Loop: loopState -> loopState (consume more tokens)
    builder.addWildcardTransition(
        loopState,
        loopState,
        variableName,
        part.typeName,
        isChecked,
    );

    // Exit: loopState -> toState
    builder.addEpsilonTransition(loopState, toState);

    return toState;
}

/**
 * Compile a number part (matches numeric tokens)
 * @deprecated Use compileNumberPartWithSlots for new code
 */
function compileNumberPart(
    builder: NFABuilder,
    part: VarNumberPart,
    fromState: number,
    toState: number,
): number {
    // For now, treat numbers as wildcards with type constraint
    // A more sophisticated version could have a "number" transition type
    if (part.optional) {
        builder.addEpsilonTransition(fromState, toState);
        builder.addWildcardTransition(
            fromState,
            toState,
            part.variable,
            "number",
        );
        return toState;
    }

    builder.addWildcardTransition(fromState, toState, part.variable, "number");
    return toState;
}

/**
 * Compile a wildcard part with slot tracking
 */
function compileWildcardPartWithSlots(
    builder: NFABuilder,
    part: VarStringPart,
    fromState: number,
    toState: number,
    context: RuleCompilationContext,
): number {
    // Use the part's variable name directly (passthrough normalization handles overrides)
    const variableName = part.variable;

    // Get slot index for this variable
    const slotIndex = context.slotMap.get(variableName);

    // Determine if this wildcard is checked
    const hasEntityType =
        part.typeName &&
        part.typeName !== "string" &&
        part.typeName !== "wildcard";
    const hasCheckedParamSpec =
        context.checkedVariables?.has(variableName) ?? false;
    const isChecked = hasEntityType || hasCheckedParamSpec;

    // Completion metadata for checked wildcards
    const completionActionName = isChecked
        ? context.completionActionName
        : undefined;
    const completionPropertyPath = isChecked
        ? context.completionPropertyPaths?.get(variableName)
        : undefined;

    if (part.optional) {
        // Optional wildcard: can skip via epsilon or match one or more tokens
        builder.addEpsilonTransition(fromState, toState);

        const loopState = builder.createState(false);

        // First token: fromState -> loopState (not appending)
        builder.addWildcardTransition(
            fromState,
            loopState,
            variableName,
            part.typeName,
            isChecked,
            slotIndex,
            false, // First token, don't append
            completionActionName,
            completionPropertyPath,
        );

        // Loop: loopState -> loopState (append to slot)
        // No completion metadata — same rationale as required wildcard.
        builder.addWildcardTransition(
            loopState,
            loopState,
            variableName,
            part.typeName,
            isChecked,
            slotIndex,
            true, // Subsequent tokens, append
        );

        builder.addEpsilonTransition(loopState, toState);

        return toState;
    }

    // Required wildcard - matches one or more tokens
    const loopState = builder.createState(false);

    // First token: fromState -> loopState (not appending)
    builder.addWildcardTransition(
        fromState,
        loopState,
        variableName,
        part.typeName,
        isChecked,
        slotIndex,
        false, // First token, don't append
        completionActionName,
        completionPropertyPath,
    );

    // Loop: loopState -> loopState (append to slot)
    // No completion metadata on self-loop: property completions should only
    // fire at the entry point (fromState), not after tokens have already been
    // consumed.  Wildcard is token+ so once in the loop, completions come
    // from whatever follows the wildcard (e.g. "by"), not from the wildcard
    // entity list again.
    builder.addWildcardTransition(
        loopState,
        loopState,
        variableName,
        part.typeName,
        isChecked,
        slotIndex,
        true, // Subsequent tokens, append
    );

    builder.addEpsilonTransition(loopState, toState);

    return toState;
}

/**
 * Compile a number part with slot tracking
 */
function compileNumberPartWithSlots(
    builder: NFABuilder,
    part: VarNumberPart,
    fromState: number,
    toState: number,
    context: RuleCompilationContext,
): number {
    // Get slot index for this variable
    const slotIndex = context.slotMap.get(part.variable);

    if (part.optional) {
        builder.addEpsilonTransition(fromState, toState);
        builder.addWildcardTransition(
            fromState,
            toState,
            part.variable,
            "number",
            false, // Numbers are not "checked" in the same way
            slotIndex,
            false,
        );
        return toState;
    }

    builder.addWildcardTransition(
        fromState,
        toState,
        part.variable,
        "number",
        false,
        slotIndex,
        false,
    );
    return toState;
}

/**
 * Compile a rules part (nested grammar rules)
 * @deprecated Use compileRulesPartWithSlots for new code
 */
function compileRulesPart(
    builder: NFABuilder,
    grammar: Grammar,
    part: RulesPart,
    fromState: number,
    toState: number,
    checkedVariables?: Set<string>,
    overrideVariableName?: string,
): number {
    if (part.tailCall) {
        throw new Error(
            `compileRulesPart: tail RulesParts are not supported by the NFA compiler ` +
                `(part.name='${part.name ?? "<unnamed>"}'). ` +
                "Disable `tailFactoring` in the grammar optimizer for NFA/DFA paths.",
        );
    }
    if (part.alternatives.length === 0) {
        // Empty rules - epsilon transition
        builder.addEpsilonTransition(fromState, toState);
        return toState;
    }

    // Create entry and exit states for the nested rules
    const nestedEntry = builder.createState(false);
    const nestedExit = builder.createState(false);

    // Connect entry
    builder.addEpsilonTransition(fromState, nestedEntry);

    // If this RulesPart has a variable name (e.g., $(trackName:<TrackPhrase>)),
    // use it to override variable names in nested wildcards.
    // This ensures captures use the outer variable name instead of inner ones.
    const nestedOverride = part.variable ?? overrideVariableName;

    // Compile each nested rule as an alternative
    for (const rule of part.alternatives) {
        const ruleEntry = builder.createState(false);

        // Try to find this nested rule in the main grammar to get its rule index
        // Match based on whether the rule has an action value
        if (rule.value) {
            const ruleIndex = findRuleIndex(grammar, rule);
            if (ruleIndex !== -1) {
                builder.getState(ruleEntry).ruleIndex = ruleIndex;
            }
            // Always store the action value on the entry state for nested rules
            // This ensures we can return the correct action even if ruleIndex matching fails
            builder.getState(ruleEntry).actionValue = rule.value;
        }

        builder.addEpsilonTransition(nestedEntry, ruleEntry);
        compileRuleFromState(
            builder,
            grammar,
            rule,
            ruleEntry,
            nestedExit,
            checkedVariables,
            nestedOverride,
        );
    }

    // Connect exit
    if (part.optional) {
        // Optional (and Kleene star): can skip the entire nested section
        builder.addEpsilonTransition(fromState, toState);
    }
    if (part.repeat) {
        // Kleene star )* or Kleene plus )+: loop back from nestedExit to nestedEntry for another iteration
        builder.addEpsilonTransition(nestedExit, nestedEntry);
    }
    builder.addEpsilonTransition(nestedExit, toState);

    return toState;
}

/**
 * Compile a rules part with slot tracking
 * Each nested rule gets its own slot map and environment
 */
function compileRulesPartWithSlots(
    builder: NFABuilder,
    grammar: Grammar,
    part: RulesPart,
    fromState: number,
    toState: number,
    context: RuleCompilationContext,
): number {
    if (part.tailCall) {
        throw new Error(
            `compileRulesPartWithSlots: tail RulesParts are not supported by the NFA compiler ` +
                `(part.name='${part.name ?? "<unnamed>"}'). ` +
                "Disable `tailFactoring` in the grammar optimizer for NFA/DFA paths.",
        );
    }
    if (part.alternatives.length === 0) {
        // Empty rules - epsilon transition
        builder.addEpsilonTransition(fromState, toState);
        return toState;
    }

    // Create entry and exit states for the nested rules
    const nestedEntry = builder.createState(false);
    const nestedExit = builder.createState(false);

    // Connect entry
    builder.addEpsilonTransition(fromState, nestedEntry);

    // Determine the variable name for this nested rule's result
    // Only use the explicit variable from the part - no implicit override inheritance
    // (Passthrough normalization is done upfront, so we don't need overrideVariableName)
    const effectiveVariable = part.variable;

    // If we have a variable, find its slot in the parent environment
    const parentSlotIndex = effectiveVariable
        ? context.slotMap.get(effectiveVariable)
        : undefined;

    // Annotate nested entry state with completion metadata from parent context
    // This allows the completion system to identify property completions
    // when the user types a prefix that reaches a nested rules reference
    if (effectiveVariable && context.completionActionName) {
        const propertyPath =
            context.completionPropertyPaths?.get(effectiveVariable);
        if (propertyPath) {
            const entryState = builder.getState(nestedEntry);
            entryState.completionActionName = context.completionActionName;
            entryState.completionPropertyPath = propertyPath;
        }
    }

    // Track whether any rule in this RulesPart created an environment
    // (needed to decide whether to pop environment on exit)
    let anyRuleCreatedEnvironment = false;

    // Compile each nested rule as an alternative
    for (const rule of part.alternatives) {
        const ruleEntry = builder.createState(false);

        // Create a new slot map for the nested rule FIRST (needed for compilation)
        const nestedSlotMap = createRuleSlotMap(rule);

        // Compile and store the action value on the entry state FIRST
        // We need to know if there's a value before deciding about environments
        // Passthrough normalization is done upfront, so rules already have explicit values
        // Just check for single-variable rules like <ArtistName> = $(x:wildcard);
        let effectiveValue = rule.value;
        if (!effectiveValue) {
            const singleVar = isSingleVariableRule(rule);
            if (singleVar) {
                effectiveValue = { type: "variable", name: singleVar.variable };
            }
        }

        let compiledValue: ValueExpression | undefined;
        let nestedCompletionActionName: string | undefined;
        let nestedCompletionPropertyPaths: Map<string, string> | undefined;
        if (effectiveValue) {
            const ruleIndex = findRuleIndex(grammar, rule);
            if (ruleIndex !== -1) {
                builder.getState(ruleEntry).ruleIndex = ruleIndex;
            }
            // Create type map for type conversion during evaluation
            const nestedTypeMap = createRuleTypeMap(rule);
            // Parse and compile the value expression with slot indices
            const parsedExpr = parseValueExpression(effectiveValue);
            compiledValue = compileValueExpression(
                parsedExpr,
                nestedSlotMap,
                nestedTypeMap,
            );
            builder.getState(ruleEntry).actionValue = compiledValue;

            // Extract completion metadata from the nested rule's value expression
            // so that deeper nested rule references get properly annotated
            const meta = extractCompletionMetadata(parsedExpr);
            nestedCompletionActionName = meta.actionName;
            if (meta.propertyPaths.size > 0) {
                nestedCompletionPropertyPaths = meta.propertyPaths;
            }
        }

        // Set slot info on the entry state if either:
        // 1. The nested rule has variables (nestedSlotMap.size > 0)
        // 2. We need to write to parent AND have a value to write
        // Only create an environment when actually needed
        const needsEnvironment =
            nestedSlotMap.size > 0 ||
            (parentSlotIndex !== undefined && compiledValue !== undefined);
        if (needsEnvironment) {
            builder.setStateSlotInfo(
                ruleEntry,
                nestedSlotMap.size,
                nestedSlotMap,
            );
            anyRuleCreatedEnvironment = true;
        }

        // Only set parentSlotIndex if this rule has a value to write to parent
        // Rules without values (like string literals) should not set this
        if (parentSlotIndex !== undefined && compiledValue !== undefined) {
            builder.setStateParentSlotIndex(ruleEntry, parentSlotIndex);
        }

        builder.addEpsilonTransition(nestedEntry, ruleEntry);

        // Create new context for the nested rule
        // IMPORTANT: Don't propagate parentSlotIndex - each rule level computes its own
        // based on its variable capture. This prevents deeper rules from incorrectly
        // inheriting parent slot indices.
        // Completion metadata: use the nested rule's own metadata if available,
        // otherwise fall back to the parent context's metadata.
        // Spacing: inherit the nested rule's own spacingMode (falling back to parent
        // so sub-rules within an optional/auto rule collect candidates into the same set).
        // splitCandidatesCollector: share the parent's collector so tokens from nested
        // rules are included in the top-level rule's split candidate set.
        const nestedContext: RuleCompilationContext = {
            slotMap: nestedSlotMap,
            nextSlotIndex: nestedSlotMap.size,
            checkedVariables: context.checkedVariables,
            parentSlotIndex: undefined, // Each level computes its own from part.variable
            completionActionName:
                nestedCompletionActionName ?? context.completionActionName,
            completionPropertyPaths:
                nestedCompletionPropertyPaths ??
                context.completionPropertyPaths,
            spacingMode: rule.spacingMode ?? context.spacingMode,
            splitCandidatesCollector: context.splitCandidatesCollector,
        };

        // If we need to write to parent, create a per-rule exit state
        // and add a writeToParent epsilon from there to the shared exit
        if (parentSlotIndex !== undefined && compiledValue) {
            const ruleExit = builder.createState(false);
            compileRuleFromStateWithSlots(
                builder,
                grammar,
                rule,
                ruleEntry,
                ruleExit,
                nestedContext,
            );
            // Add epsilon with writeToParent - pass the COMPILED value expression
            builder.addEpsilonWithWriteToParent(
                ruleExit,
                nestedExit,
                compiledValue,
            );
        } else {
            compileRuleFromStateWithSlots(
                builder,
                grammar,
                rule,
                ruleEntry,
                nestedExit,
                nestedContext,
            );
        }
    }

    // Connect exit
    if (part.optional) {
        // Optional (and Kleene star): can skip the entire nested section
        builder.addEpsilonTransition(fromState, toState);
    }
    if (part.repeat) {
        // Kleene star )* or Kleene plus )+: loop back from nestedExit to nestedEntry for another iteration
        builder.addEpsilonTransition(nestedExit, nestedEntry);
    }

    // If no parent slot index (nested rule doesn't write to parent), we need to
    // pop the environment when exiting. This handles cases like (<Item>)? where
    // the parent doesn't capture the result but nested rules still create environments.
    // IMPORTANT: Only pop if at least one rule actually created an environment.
    // Rules like (the)? don't create environments and shouldn't trigger a pop.
    if (parentSlotIndex === undefined && anyRuleCreatedEnvironment) {
        builder.addEpsilonWithPopEnvironment(nestedExit, toState);
    } else {
        builder.addEpsilonTransition(nestedExit, toState);
    }

    return toState;
}

/**
 * Find the index of a rule in the grammar's rules array
 * Returns -1 if not found
 */
function findRuleIndex(grammar: Grammar, rule: GrammarRule): number {
    // Match based on rule value (action object)
    // This is a simple comparison - we could make it more sophisticated
    for (let i = 0; i < grammar.alternatives.length; i++) {
        const grammarRule = grammar.alternatives[i];
        if (grammarRule.value && rulesMatch(grammarRule, rule)) {
            return i;
        }
    }
    return -1;
}

/**
 * Check if two rules match (simplified comparison based on value)
 */
function rulesMatch(rule1: GrammarRule, rule2: GrammarRule): boolean {
    // For now, use a simple identity check
    // In practice, nested rules are often the same object references
    return rule1 === rule2;
}

/**
 * Compile a single grammar rule to a standalone NFA
 * Useful for incremental grammar building
 */
export function compileRuleToNFA(rule: GrammarRule, name?: string): NFA {
    const builder = new NFABuilder();
    const startState = builder.createState(false);
    const acceptState = builder.createState(true);

    // Normalize unconditionally so single-rule compilation matches
    // `compileGrammarToNFA`'s behavior: passthrough rules acquire
    // their `_result` capture and single-literal rules acquire their
    // implicit `-> "literal"` value, and dispatched `RulesPart`s
    // (which the NFA compiler doesn't understand directly) are
    // expanded back into a flat plain `RulesPart`.
    const ruleToCompile = normalizeGrammar({ alternatives: [rule] })
        .alternatives[0];
    const grammar: Grammar = { alternatives: [ruleToCompile] };

    compileRuleFromState(
        builder,
        grammar,
        ruleToCompile,
        startState,
        acceptState,
    );

    return builder.build(startState, name);
}
