/**
 * SITE LABELS — the encoder's downward pass over an encoded program.
 *
 * ## The criterion
 *
 * *Any consulting of options at parse time, per rule or per combinator, is a
 * FAIL.* After U4 four consultations remained, and three of them are here:
 * `ctx.trivia` per sequence term, `cstCaptureActive` per leaf, and
 * `hasTrivia`/`needMark` per repetition. (`forCtx`, once per parse at the
 * boundary, is not one of these — it selects the assembly rather than running
 * inside one.)
 *
 * ## Why a label and not a `RunCfg` bit
 *
 * `assemble.ts:213-277` states the rule `RunCfg` is held to: a bit belongs there
 * only when it is FIXED FOR THE LIFETIME OF A PARSE. Neither of these facts is.
 *
 *   - `ctx.trivia` is per-SCOPE. `OP_SCOPE` swaps it mid-parse, so a `RunCfg`
 *     bit would be answering a question that has different answers at different
 *     sites in the same parse.
 *   - `ctx._cstBuf` is per-NODE — `assemble.ts:247-249` records that a previous
 *     lane proposed keying on it and that doing so would have been *incorrect,
 *     not merely redundant*.
 *
 * A site label is strictly stronger than either, and it is what makes both facts
 * legal to resolve: it is computed from the PROGRAM STRUCTURE at encode time,
 * before any option set exists, and it says what is true *at that site* rather
 * than what is true for the parse. `OP_NODE` sets `ctx._cstBuf` unconditionally
 * on entry and restores it on exit, so every site dynamically inside one has
 * `_cstBuf !== undefined` — not because of an option, but because of where it
 * sits in the program.
 *
 * ## The two axes, kept apart
 *
 * The capture label does not compress into one bit, and an earlier attempt to
 * make it one was wrong in both directions:
 *
 *   - `cap` is THREE-VALUED. `OP_NODE` writes `ctx.captureTrivia` a LITERAL —
 *     `readsTrivia || hostCst`, resolved at emit — so a site under a node has it
 *     definitely true OR definitely false. `OP_SCOPE_CAP` only ever sets it true.
 *     Collapsing "definitely off" into "unknown" loses the case that lets
 *     `_skipTrivia` drop its capture arm entirely.
 *   - `buf` is a separate FLAG, because `_cstBuf` and `captureTrivia` are set by
 *     different ops and neither implies the other: `OP_SCOPE_CAP` turns capture
 *     on without opening a buffer, and a builder-less `OP_NODE` opens a buffer
 *     with capture off.
 *
 * ## Asymmetry, deliberately
 *
 * `buf` is TRUE only for "guaranteed present". FALSE means UNKNOWN, never
 * "guaranteed absent" — no root can prove absence, because every entry point
 * (`prog.rules`, and the `extraIps` a scan pool reaches from outside the emitted
 * scope) is called with a context this pass cannot see. Nothing is elided on
 * `buf === false`; it only declines to elide. The same holds for `TRI_UNKNOWN`
 * and `CAP_UNKNOWN`, which are the lattice's top element, not a third fact.
 *
 * That asymmetry is what rules out the unsound version of this pass: eliding a
 * leaf's capture when `hostCst === false`. `OP_NODE` opens `_cstBuf` whatever the
 * host mode is, and those leaves feed `kids` → `build(...)`, so the ONLY thing a
 * label licenses at a leaf is dropping the TEST — never the capture.
 */
import {
  OP_ATTEMPT, OP_CHOICE, OP_DISPATCH, OP_EXPECT, OP_FIELD, OP_GATE, OP_LABEL, OP_LEAF,
  OP_NODE, OP_NODE_TRACK, OP_NOT, OP_OPT, OP_PEEK, OP_REP, OP_REPV, OP_ROUTED, OP_RULE,
  OP_SCOPE, OP_SCOPE_CAP, OP_SCOPE_PLAIN, OP_SEQ, OP_SEQV, OP_SEQX, OP_TOKEN, OP_XFORM,
} from './ops.ts'
import { childSlots } from './child-slots.ts'

/** No scope on this path installs a known trivia — the lattice's top element. */
export const TRI_UNKNOWN = -2
/** `ctx.trivia === undefined` is guaranteed here. */
export const TRI_NONE = -1
/** Any value `>= 0` is a trivia slot index, guaranteed installed here. */

/** `ctx.captureTrivia` is not known at this site. */
export const CAP_UNKNOWN = 0
/** `ctx.captureTrivia` is guaranteed NOT `true` here. */
export const CAP_OFF = 1
/** `ctx.captureTrivia === true` is guaranteed here. */
export const CAP_ON = 2

/** Buffer raw-entry mode is not provable at this site. */
export const RAW_UNKNOWN = 0
/** Buffer retains raw entry values. */
export const RAW_CAPTURE = 1
/** Buffer retains only a raw source-order count. */
export const RAW_OMIT = 2

export type SiteLabel = {
  /** `TRI_UNKNOWN`, `TRI_NONE`, or the trivia slot the enclosing scope installed. */
  readonly tri: number
  /**
   * `ctx._cstBuf !== undefined` is GUARANTEED. False means unknown — see the
   * asymmetry note in this file's header. Never read as "guaranteed absent".
   */
  readonly buf: boolean
  /** `RAW_UNKNOWN` / `RAW_CAPTURE` / `RAW_OMIT`. */
  readonly raw: number
  /** `CAP_UNKNOWN` / `CAP_OFF` / `CAP_ON`. */
  readonly cap: number
}

/** The lattice's top: every entry point starts here. */
export const TOP: SiteLabel = { tri: TRI_UNKNOWN, buf: false, raw: RAW_UNKNOWN, cap: CAP_UNKNOWN }

function meet(a: SiteLabel, b: SiteLabel): SiteLabel {
  const tri = a.tri === b.tri ? a.tri : TRI_UNKNOWN
  const buf = a.buf && b.buf
  const raw = a.raw === b.raw ? a.raw : RAW_UNKNOWN
  const cap = a.cap === b.cap ? a.cap : CAP_UNKNOWN
  if (tri === a.tri && buf === a.buf && raw === a.raw && cap === a.cap) return a
  return { tri, buf, raw, cap }
}

/**
 * The sites reachable from `roots` THROUGH THE SHARED EDGE TABLE.
 *
 * Not `inspect.ts`'s `reachableIps`: that one walks a whole program from its rule
 * entries, and the emitter's question is about the set IT will lower — the rule
 * entries plus the scan pool's `extraIps`. Different ROOTS, same EDGES, and the
 * edges now live in `child-slots.ts` so the two answers cannot drift when an
 * opcode is added to one and not the other. That drift is the failure this file's
 * header used to warn about while guarding only against it happening within this
 * file; the copy it warned about was in `inspect.ts` the whole time.
 *
 * `childSlots`'s false return (an opcode it does not know) is ignored here: the
 * site resolves to `TOP` through `labelAt`, and the enclosing assembly is
 * unemittable regardless.
 */
export function reachableSites(code: Int32Array, roots: Iterable<number>): Set<number> {
  const seen = new Set<number>()
  const stack = [...roots]
  const kids: number[] = []
  while (stack.length > 0) {
    const ip = stack.pop()!
    if (seen.has(ip)) continue
    seen.add(ip)
    kids.length = 0
    childSlots(code, ip, kids)
    for (const c of kids) stack.push(c)
  }
  return seen
}

/**
 * What a site hands DOWN to its children. Every op but the two that write the
 * context passes its own label through unchanged.
 */
function transfer(code: Int32Array, ip: number, at: SiteLabel, hostCst: boolean): SiteLabel {
  const op = code[ip]
  if (op === OP_SCOPE || op === OP_SCOPE_CAP || op === OP_SCOPE_PLAIN) {
    const ki = code[ip + 1]!
    const tri = ki < 0 ? TRI_NONE : ki
    // `OP_SCOPE_CAP` is an OR with the inherited context, never a switch-off
    // (`encode.ts:1153-1158`), so it can only ever raise `cap` to `CAP_ON`.
    const cap = op === OP_SCOPE_CAP ? CAP_ON : at.cap
    if (tri === at.tri && cap === at.cap) return at
    return { tri, buf: at.buf, raw: at.raw, cap }
  }
  if (op === OP_NODE || op === OP_NODE_TRACK) {
    const flags = code[ip + 3]!
    const directChildren = !hostCst && op === OP_NODE && code[ip + 1]! >= 0 && code[ip + 4]! < 0
      && (flags === 2 || flags === 18 || flags === 34)
    if (directChildren) {
      // The confirmed low-arity builder projection installs split child/leaf
      // arrays instead of a CstCaptureBuf. Descendants still capture, but they
      // must take the generic collector branch rather than dereference `_cstBuf`.
      // False means UNKNOWN in this lattice, which is exactly the safe answer.
      return { tri: at.tri, buf: false, raw: RAW_UNKNOWN, cap: CAP_OFF }
    }
    // `ctx._cstBuf = buf` and `ctx.captureTrivia = <literal>`, both unconditional
    // — `emit-assembly.ts`'s `OP_NODE` body opens the buffer before it descends
    // and closes it after, whatever the host mode is.
    const cap = ((flags & 4) !== 0 || hostCst) ? CAP_ON : CAP_OFF
    const raw = !hostCst && code[ip + 1]! >= 0 && code[ip + 4]! < 0 && (flags & 2) !== 0
      ? RAW_OMIT
      : RAW_CAPTURE
    if (at.buf && raw === at.raw && cap === at.cap) return at
    return { tri: at.tri, buf: true, raw, cap }
  }
  // THE TWO BOUNDARIES clear every capture sink for their child and contribute
  // ONE leaf for the whole match; `token()` clears `ctx.trivia` as well. So a
  // site inside either has NO open `_cstBuf`.
  //
  // The label can only say `buf: false`, which this lattice reads as UNKNOWN
  // rather than as "guaranteed absent" (see the asymmetry note above). That is
  // the SOUND direction and it is the one that matters: `_rbBuf` and
  // `_pushLeafBuf` dereference `ctx._cstBuf` with no null test, so a site that
  // inherited `buf: true` through a `token()` would throw on the first rollback.
  // Losing the elision inside a token is the price; being wrong there is not
  // an option.
  if (op === OP_TOKEN) {
    if (at.tri === TRI_NONE && !at.buf) return at
    return { tri: TRI_NONE, buf: false, raw: RAW_UNKNOWN, cap: at.cap }
  }
  if (op === OP_LEAF) {
    if (!at.buf) return at
    return { tri: at.tri, buf: false, raw: RAW_UNKNOWN, cap: at.cap }
  }
  return at
}

/** A site's label, or `TOP` for anything the walk did not reach. */
export type SiteLabels = { at: (ip: number) => SiteLabel }

/**
 * Compute a label for every site reachable from `roots`.
 *
 * A worklist to a fixpoint, because the program has cycles (a recursive rule is
 * a back-edge into a site already in flight) and because a site shared by two
 * parents must carry the MEET of what both hand it — a downward pass that simply
 * overwrote would give a shared site whichever parent it happened to visit last,
 * and the emitted body for that site is ONE body serving both.
 *
 * The meet only ever moves a label toward `TOP`, and `TOP` is absorbing, so the
 * lattice has height three and the walk terminates.
 */
export function computeSiteLabels(
  code: Int32Array,
  roots: Iterable<number>,
  hostCst: boolean,
): SiteLabels {
  const labels = new Map<number, SiteLabel>()
  const work: number[] = []

  const push = (ip: number, l: SiteLabel): void => {
    const cur = labels.get(ip)
    if (cur === undefined) {
      labels.set(ip, l)
      work.push(ip)
      return
    }
    const next = meet(cur, l)
    if (next === cur) return
    labels.set(ip, next)
    work.push(ip)
  }

  for (const r of roots) push(r, TOP)

  const kids: number[] = []
  while (work.length > 0) {
    const ip = work.pop()!
    const down = transfer(code, ip, labels.get(ip)!, hostCst)
    kids.length = 0
    childSlots(code, ip, kids)
    for (const c of kids) push(c, down)
  }

  return { at: (ip: number): SiteLabel => labels.get(ip) ?? TOP }
}