import type { CharRange, FirstSet, Combinator, ParserDef } from '../types.ts'

/**
 * Resolve a NAMED cross-artifact rule reference (`g.Foo`) whose own thunk does not
 * resolve — the shared-shape hole, bound by name at fuse time.
 *
 * A shape module compiles `Ratio: sequence(g.Value, …)` without defining `Value`, so
 * that `lazy`'s thunk throws and every first-set through it degrades to `any`. Once
 * the shape is FUSED with a dialect that defines `Value`, the hole is bound — pass a
 * resolver over the fused winner map and the first-set is the real one.
 *
 * Only NAMED refs are resolvable: an unnamed `ref()` that was never `.define()`d
 * carries no name for anyone to bind, so it stays `any`.
 */
export type RefResolver = (name: string) => Combinator<unknown> | undefined

/** Winner-resolved choice facts shared by table encoding and capability IR. */
export type FinalChoiceClassification = {
  readonly exclusive: boolean
  readonly firstSets: readonly FirstSet[]
  readonly nullable: readonly boolean[]
}

/** Resolve final arm winners before deciding whether a choice is exclusive. */
export function classifyFinalChoice(
  arms: readonly Combinator<unknown>[],
  resolve?: RefResolver,
  activeTrivia?: Combinator<unknown> | null,
): FinalChoiceClassification {
  const firstSets: FirstSet[] = []
  const nullable: boolean[] = []
  let exclusive = true
  // Preserve the encoder's historical per-arm evaluation order: nullability
  // first, then first-set resolution only for a non-nullable arm. Besides
  // keeping compile-time lazy resolution behavior stable, a nullable arm has no
  // usable dispatch class, so resolving its set would mint unused authority.
  for (const arm of arms) {
    const empty = matchesEmpty(arm, new Set(), resolve)
    nullable.push(empty)
    firstSets.push(empty ? { kind: 'any' } : firstSetOf(arm, new Set(), resolve, activeTrivia))
    if (empty) exclusive = false
  }
  if (exclusive) {
    // Match `resolveDispatch` exactly: ASCII has an indexed owner per code;
    // above ASCII the compact table does not index ranges, so a second arm with
    // any high range conservatively declines exclusivity even when disjoint.
    const ascii = new Uint8Array(128)
    let highOwners = 0
    for (let arm = 0; arm < firstSets.length && exclusive; arm++) {
      const first = firstSets[arm]!
      if (first.kind !== 'ranges' || first.ranges.length === 0) { exclusive = false; break }
      let ownsHigh = false
      for (const range of first.ranges) {
        if (range.hi >= 128) ownsHigh = true
        for (let code = Math.max(0, range.lo); code <= Math.min(127, range.hi); code++) {
          if (ascii[code] !== 0) { exclusive = false; break }
          ascii[code] = 1
        }
        if (!exclusive) break
      }
      if (ownsHigh && ++highOwners > 1) exclusive = false
    }
  }
  return { exclusive, firstSets, nullable }
}

/** The compose WINNER a named lazy ref resolves to — the same row the encoder's
 * `lazy` case calls via `winners`/`scopedRef`. Winner-FIRST resolution is what makes
 * first-set / nullability analysis AGREE with emission: a base piece's thunk still
 * closes over its own binding, so a compose OVERRIDE (and any undefined cross-piece
 * ref) would otherwise be invisible to the gate — the reducer reroutes, the recognizer
 * does not. `undefined` → no winner; fall back to the thunk. Monolithic: the winner IS
 * the thunk's target, a no-op. A winner that recurses back to `p` (recursive or
 * self-alias rule) is caught by the shared `seen` guard → `any`, a sound over-approx. */
function winnerForRef(p: Combinator<unknown>, resolve: RefResolver | undefined): Combinator<unknown> | undefined {
  if (resolve === undefined) return undefined
  const name = (p as unknown as { _ruleName?: string })._ruleName
  const w = name === undefined ? undefined : resolve(name)
  // Skip a winner that merely wraps THIS reference (a transparent rules()/parser()
  // alias): resolving to it is a self-hop, not an override — matches the encoder's
  // own `winnerWrapsReference` guard so first-set analysis agrees with emission.
  if (w === undefined || w === p) return undefined
  let cur = w
  for (const seen = new Set<Combinator<unknown>>(); !seen.has(cur); ) {
    if (cur === p) return undefined
    seen.add(cur)
    const cd = cur._def as ParserDef
    if (cd.tag !== 'grammar' && cd.tag !== 'trivia') return w
    cur = cd.parser
  }
  return w
}

export function union(a: FirstSet, b: FirstSet): FirstSet {
  if (a.kind === 'any' || b.kind === 'any') return { kind: 'any' }
  if (a.kind === 'empty') return b
  if (b.kind === 'empty') return a
  return { kind: 'ranges', ranges: mergeRanges([...a.ranges, ...b.ranges]) }
}

export function intersects(a: FirstSet, b: FirstSet): boolean {
  if (a.kind === 'any' || b.kind === 'any') return true
  if (a.kind === 'empty' || b.kind === 'empty') return false
  for (const ra of a.ranges) {
    for (const rb of b.ranges) {
      if (ra.lo <= rb.hi && rb.lo <= ra.hi) return true
    }
  }
  return false
}

export function fromChar(code: number): FirstSet {
  return fromRange(code, code)
}

/**
 * True when `combinator`'s first set admits the code point at `input[pos]` (or its
 * first set is `any`). The runtime counterpart of codegen's `firstSetCond` guard —
 * used by the interpreter's first-set fail-fast in `optional`/`many`/`attempt`/
 * `node` to reject a doomed sub-parse before doing any setup. Returns `false` at EOF.
 */
export function startsFirstSet(combinator: Combinator<unknown>, input: string, pos: number): boolean {
  const fs = combinator._meta.firstSet
  if (fs.kind === 'any') return true
  if (fs.kind === 'empty') return false
  const code = input.codePointAt(pos)
  if (code === undefined) return false
  for (const r of fs.ranges) if (code >= r.lo && code <= r.hi) return true
  return false
}

export function fromRange(lo: number, hi: number): FirstSet {
  return { kind: 'ranges', ranges: [{ lo, hi }] }
}

export function any(): FirstSet {
  return { kind: 'any' }
}

export function empty(): FirstSet {
  return { kind: 'empty' }
}

/**
 * Can this parser SUCCEED consuming zero characters (nullable / matches-empty)?
 * Used to compute a sound sequence first-set: a nullable leading term lets the
 * NEXT term's first chars start the whole sequence. MUST err toward `true` when
 * unsure — over-estimating nullability only widens the (over-approximated) first
 * set, which stays sound; under-estimating would drop valid start chars and make
 * first-char dispatch skip a matching arm.
 */
export function matchesEmpty(
  p: Combinator<unknown>,
  seen: Set<Combinator<unknown>> = new Set(),
  resolve?: RefResolver,
): boolean {
  // RECURSION-STACK guard: a mutually-nullable ref cycle (e.g.
  // `A = oneOrMore(B); B = oneOrMore(A)`) would recurse forever. Treat a node
  // re-entered on the CURRENT path as nullable — the safe (`true`) default.
  // Remove it on exit: a shared DAG child reached later through a sibling is not
  // a cycle. Keeping every completed node in `seen` made an eleven-arm choice of
  // non-nullable `@` rules report nullable merely because the arms shared leaves.
  if (seen.has(p)) return true
  seen.add(p)
  try {
    return matchesEmptyBody(p, seen, resolve)
  } finally {
    seen.delete(p)
  }
}

function matchesEmptyBody(
  p: Combinator<unknown>,
  seen: Set<Combinator<unknown>>,
  resolve: RefResolver | undefined,
): boolean {
  const me = (c: Combinator<unknown>): boolean => matchesEmpty(c, seen, resolve)
  const d = p._def as ParserDef
  switch (d.tag) {
    case 'literal':   return d.value.length === 0
    case 'keywords':  return false
    // The routed token itself is the selector's match, never empty; a fallback can be.
    case 'routed':    return d.fallback === undefined ? false : me(d.fallback)
    case 'regex':
      // Precise: does the pattern admit a zero-length match? (`a*`, `a?`, `a|`, …)
      try { const m = new RegExp(d.source).exec(''); return m != null && m[0] === '' }
      catch { return true }
    case 'many':
    case 'optional':
    case 'not':
    case 'peek':     return true          // zero repetitions / absent / lookahead
    // Default `sepBy` is `(item (sep item)*)?` — it MATCHES THE EMPTY STRING.
    // Any `min >= 1` requires that many ITEMS, so it is nullable only when the
    // item is. (Keying this off `min === 1` reported every `{ min: 2 }` list as
    // nullable — safe, but wrong, and it put a bogus `nullable-prefix` note on
    // the gating diagnostic for a list that can never match empty.)
    case 'sepBy':     return d.min >= 1 ? me(d.parser) : true
    case 'oneOrMore': return me(d.parser)
    case 'sequence':  return d.parsers.every(me)
    case 'choice':
      return d.parsers.some(me)
    case 'dispatch':
      return me(d.selector)
    case 'transform':
    case 'label':
    case 'trivia':
    case 'token':
    case 'leaf':
    case 'expect':
    case 'withCtx':
    case 'node':
    case 'grammar':
    case 'recover':   return me(d.parser)
    case 'lazy': {
      const w = winnerForRef(p, resolve)
      if (w !== undefined) return me(w)
      try { return me(d.thunk()) }
      catch { return true }
    }
    default:          return true          // scanTo / guard / unknown → assume nullable (safe)
  }
}

/**
 * A ZERO-WIDTH ASSERTION never consumes input, so it contributes NOTHING to a
 * sequence's first-set — the first consumed char comes from the following
 * non-nullable term. `not(X)` reports `firstSet: any()` (it cannot know what it
 * forbids), which would otherwise poison a sequence's first-set to `any` and kill
 * first-char dispatch of the whole arm. Skipping its contribution is SOUND: a
 * first-set used for dispatch gating must stay a correct SUPERSET of the rule's
 * true first chars, and `not(X) Y` can only start with a char in firstSet(Y) — the
 * assertion only NARROWS the language (it forbids a full match ahead), it never
 * widens the set of possible first chars beyond Y. So firstSet(Y) is a sound (and
 * tighter) superset.
 *
 * The POSITIVE lookahead `peek(X)` is zero-width too, but it is NOT in this
 * predicate: unlike `not`, it knows what it requires, so its first-set is a real
 * constraint that must be INTERSECTED into the sequence's set rather than dropped
 * (see `isPositiveLookahead` and `sequenceFirstSet`).
 */
export function isZeroWidthAssertion(p: Combinator<unknown>): boolean {
  // `adjacency` joins `not` for the same reason: `adjacent()`/`notAdjacent()` are
  // zero-width tests of the gap BEHIND the cursor, so they constrain nothing about
  // the first char ahead and must not contribute their `any` to the sequence.
  return p._tag === 'not' || p._tag === 'adjacency'
}

/**
 * A POSITIVE zero-width assertion (`peek(X)`). It consumes nothing, so like
 * `not(X)` it does not contribute a first char of its own — but it does REQUIRE
 * that X match here, so `peek(X) Y` can only start with a char in
 * firstSet(X) ∩ firstSet(Y). That intersection is what makes a leading `peek()`
 * gate its choice arm; `not(not(X))`, the only previous spelling, reports `any()`
 * and poisons the dispatch instead.
 *
 * Soundness: first-sets are SUPERSETS of the true first chars, and
 * (A ⊇ a) ∧ (B ⊇ b) ⇒ A ∩ B ⊇ a ∩ b — so intersecting stays a superset and can
 * never skip a real match. A NULLABLE body succeeds on the empty string and
 * therefore constrains nothing; `peek()` reports `any()` in that case, which the
 * intersection treats as "no constraint".
 */
function isPositiveLookahead(
  p: Combinator<unknown>,
): p is Combinator<unknown> & { _def: Extract<ParserDef, { tag: 'peek' }> } {
  return p._tag === 'peek'
}

/** Intersect a lookahead constraint into an accumulator; `any` = no constraint. */
function narrowBy(acc: FirstSet | null, constraint: FirstSet): FirstSet | null {
  if (constraint.kind === 'any') return acc
  if (acc === null) return constraint
  if (acc.kind === 'any') return constraint
  if (acc.kind === 'empty' || constraint.kind === 'empty') return { kind: 'empty' }
  const ranges: CharRange[] = []
  for (const a of acc.ranges) for (const b of constraint.ranges) {
    const lo = Math.max(a.lo, b.lo)
    const hi = Math.min(a.hi, b.hi)
    if (lo <= hi) ranges.push({ lo, hi })
  }
  return ranges.length === 0 ? { kind: 'empty' } : { kind: 'ranges', ranges }
}

/**
 * Apply the accumulated `peek()` constraints to a sequence's first-set. When the
 * consuming terms contributed NOTHING (the sequence is all zero-width/nullable,
 * e.g. a bare `peek(X)` arm), the assertion IS the first-set: the sequence can
 * only succeed — even zero-width — where X matches.
 */
function applyAssertion(fs: FirstSet, assertion: FirstSet | null): FirstSet {
  return assertion === null ? fs : fs.kind === 'empty' ? assertion : narrowBy(fs, assertion)!
}

/**
 * First-set of a sequence: union each term's first-set through the NULLABLE
 * PREFIX — a leading `optional(…)` / `many(…)` / nullable term can be skipped, so
 * the sequence can begin with a LATER term's first char. Stop at (and include)
 * the first non-nullable term. (`parsers[0].firstSet` alone under-approximates
 * and silently breaks first-char dispatch — see the InterpolatedSelector bug.)
 * A leading zero-width assertion (`not(…)`) is nullable but contributes NOTHING to
 * the first-set (see `isZeroWidthAssertion`) — its `any` must not poison the union.
 */
function sequenceSet(
  parsers: readonly Combinator<unknown>[],
  fs: (p: Combinator<unknown>) => FirstSet,
  empties: (p: Combinator<unknown>) => boolean,
  trivia?: Combinator<unknown> | null,
): FirstSet {
  const afterBoundary = (i: number): FirstSet => {
    const rest = at(i)
    return trivia ? union(rest, fs(trivia)) : rest
  }
  const at = (i: number): FirstSet => {
    const p = parsers[i]!
    if (isPositiveLookahead(p)) {
      const constraint = fs(p)
      return i + 1 === parsers.length
        ? constraint
        : applyAssertion(afterBoundary(i + 1), constraint)
    }
    if (isZeroWidthAssertion(p)) {
      return i + 1 === parsers.length ? empty() : afterBoundary(i + 1)
    }
    const first = fs(p)
    if (!empties(p) || i + 1 === parsers.length) return first
    return union(first, afterBoundary(i + 1))
  }
  return at(0)
}

export function sequenceFirstSet(parsers: readonly Combinator<unknown>[]): FirstSet {
  return sequenceSet(parsers, p => p._meta.firstSet, matchesEmpty)
}

/**
 * Deep first-set that RESOLVES `lazy`/`ref` combinators to their targets. The
 * combinators bake `_meta.firstSet` at CONSTRUCTION, when a `ref()` still reads
 * `any()` (define() never updates it) — so a `choice`/`sequence` built over refs
 * caches a spuriously-`any` first-set and loses first-char dispatch. Recomputing
 * here, following refs, recovers the real set. Over-approximates on cycles /
 * unknown constructs (returns `any`) — always sound: a wider set only means "try
 * this arm for more first chars", never skips a real match.
 *
 * SOUND ONLY where refs are FINAL (monolithic compile). Under compose OVERRIDE a
 * referenced rule can be replaced with a WIDER first-set, so a baked deep set
 * would wrongly skip valid input — the compose path defers dispatch to fuse time.
 *
 * `resolve` binds NAMED cross-artifact holes (`g.Foo`) against a fused winner map —
 * see `RefResolver`. Diagnostic-only today: it is what lets the gating analysis ask
 * the question at the site where the hole actually HAS an answer.
 */
export function firstSetOf(
  p: Combinator<unknown>,
  seen: Set<Combinator<unknown>> = new Set(),
  resolve?: RefResolver,
  activeTrivia?: Combinator<unknown> | null,
): FirstSet {
  // `seen` is the current recursion path, not a global visited set. A completed
  // shared child must be analysed again for a sibling; only a back-edge on this
  // path is a cycle and needs the safe `any` over-approximation.
  if (seen.has(p)) return any()               // cycle → any (safe over-approximation)
  seen.add(p)
  try {
    return firstSetBody(p, seen, resolve, activeTrivia)
  } finally {
    seen.delete(p)
  }
}

function firstSetBody(
  p: Combinator<unknown>,
  seen: Set<Combinator<unknown>>,
  resolve: RefResolver | undefined,
  activeTrivia: Combinator<unknown> | null | undefined,
): FirstSet {
  const fs = (c: Combinator<unknown>): FirstSet => firstSetOf(c, seen, resolve, activeTrivia)
  const empties = (c: Combinator<unknown>): boolean => matchesEmpty(c, new Set(), resolve)
  const d = p._def as ParserDef
  switch (d.tag) {
    case 'literal':
    case 'regex':
    case 'keywords':  return p._meta.firstSet  // terminals: no refs, cached set is exact
    case 'dispatch':  return fs(d.selector)
    case 'lazy': {
      const w = winnerForRef(p, resolve)
      if (w !== undefined) return fs(w)
      try { return fs(d.thunk()) }
      catch { return any() }
    }
    case 'choice': {
      let out: FirstSet = empty()
      for (const arm of d.parsers) out = union(out, fs(arm))
      return out
    }
    case 'sequence': {
      // A zero-width or nullable term leaves the cursor at its current position,
      // while every later term first skips active trivia. The sequence can
      // therefore start with that trivia or with the later term. A positive
      // lookahead still constrains both possibilities at the cursor where it ran:
      //
      //   peek ∩ (later ∪ trivia)
      //
      // Recurse at every term boundary because a lookahead after another
      // zero-width term runs after trivia has advanced, not at the sequence's
      // original cursor.
      return sequenceSet(d.parsers, fs, empties, activeTrivia)
    }
    case 'peek': {
      // Deep-resolve the body: a `ref()` reads `any()` at CONSTRUCTION, so the
      // shallow `_meta.firstSet` baked into the assertion would lose the gate.
      const inner = d.parser
      return empties(inner) ? any() : fs(inner)
    }
    case 'oneOrMore':
    case 'many':
    case 'optional':
    case 'transform':
    case 'label':
    case 'trivia':
    case 'token':
    case 'leaf':
    case 'node':
    case 'sepBy':
    case 'expect':    return fs(d.parser)
    case 'grammar':   return firstSetOf(
      d.parser,
      seen,
      resolve,
      d.clearTrivia ? null : (d.triviaParser ?? activeTrivia),
    )
    default:          return p._meta.firstSet  // not / scanTo / guard / withCtx / recover / unknown
  }
}

function mergeRanges(ranges: CharRange[]): CharRange[] {
  if (ranges.length === 0) return []
  const sorted = [...ranges].sort((a, b) => a.lo - b.lo)
  // Always copy — never alias input objects
  const out: CharRange[] = [{ lo: sorted[0]!.lo, hi: sorted[0]!.hi }]
  for (let i = 1; i < sorted.length; i++) {
    const top = out[out.length - 1]!
    const cur = sorted[i]!
    if (cur.lo <= top.hi + 1) {
      if (cur.hi > top.hi) top.hi = cur.hi
    } else {
      out.push({ lo: cur.lo, hi: cur.hi })
    }
  }
  return out
}