/**
 * Precomputed reachability structure (change: optimize-reachability-precompute).
 *
 * Every flagship conclusion OpenLore serves — which tests reach this change
 * (`select_tests`), what has no reaching test (`report_coverage_gaps`), what dies
 * if X is deleted (`find_dead_code`), what a diff's blast radius is
 * (`blast_radius`) — is a reachability question. Before this module each of them
 * re-answered from scratch at tool-call time: rebuild `Map<string, Set<string>>`
 * adjacency over the whole graph, run a BFS whose queue was an array drained with
 * `Array.prototype.shift()` (O(n) per pop), then throw all of it away.
 *
 * The graph only changes at analyze/flush. So the traversal structure is built
 * there, once, and served as lookups:
 *
 *  - **Dense integer node ids.** `nodeIds[i]` ⇆ `indexOf(id)`; every traversal
 *    runs on `Int32Array`s, never on Maps of Sets of strings.
 *  - **CSR adjacency, forward and backward.** `offsets[i]..offsets[i+1]` slices
 *    `targets`, with a parallel `flags` byte per edge slot carrying the
 *    kind/confidence bits the existing filters need (`synthesized`, so
 *    `directResolvedOnly` stays expressible) plus the per-filter forward
 *    *eligibility* bits — `buildAdjacency` grows its forward key set as it walks
 *    the filtered edge list, so whether a forward edge is emitted depends on the
 *    filter AND the edge's position, and that verdict is resolved at build time
 *    per slot. Slots are stored in the original `cg.edges` order within each
 *    source group and are NOT pre-deduplicated, so any filtered view reproduces
 *    `buildAdjacency`'s insertion-ordered `Set` exactly — see
 *    {@link TraversalIndex.neighborIds}.
 *  - **SCC condensation + topological order.** Tarjan (iterative, on the dense
 *    ids) collapses cycles; whole-graph reaches then run as a single array scan
 *    over the condensation DAG in topological order — linear and allocation-free,
 *    with member expansion recovering the exact node-level answer.
 *
 * EQUIVALENCE IS THE CONTRACT. This module changes latency, never answers. Every
 * primitive here is specified against the per-call BFS it replaces
 * (`buildAdjacency` + `bfs`/`reachableFrom`/`reachAll` in `mcp-handlers/`), down
 * to neighbor iteration order and the treatment of seeds that are not in the
 * graph, and `condensation.test.ts` pins that equivalence on randomized graphs.
 *
 * Deliberately NOT borrowed from the reachability-index literature: no
 * interval/2-hop labeling (GRAIL/FERRARI class). Labeling pays off orders of
 * magnitude further up the node count and adds an invalidation liability the
 * condensation walk does not have. If profiling at real monorepo scale ever shows
 * condensation walks insufficient, labeling is a follow-up proposal, not this one.
 */
import type { SerializedCallGraph } from './call-graph.js';
/**
 * The invalidation key binding a persisted structure to the graph it was built
 * from: the SHA-256 of the exact `llm-context.json` content. Writer and reader
 * both derive it from the same bytes, so a structure can never be served over a
 * graph from another generation — and no separate freshness bookkeeping (mtimes,
 * generation counters) can drift out of step with it.
 */
export declare function artifactDigest(contextJson: string): string;
/** Traversal direction: `forward` = caller→callee, `backward` = callee→caller. */
export type Direction = 'forward' | 'backward';
/**
 * The edge filters the traversal handlers already expose. Kept as an options
 * object (rather than a boolean) so a future filter is additive.
 */
export interface TraversalFilter {
    /**
     * Strict mode (spec: add-synthesized-dynamic-dispatch-edges): skip synthesized
     * dynamic-dispatch / CHA / override edges so traversal rests only on directly
     * resolved edges. Mirrors `buildAdjacency({ directResolvedOnly: true })`.
     */
    directResolvedOnly?: boolean;
}
/** Serialized-artifact schema version. Bumped when the layout changes. */
export declare const TRAVERSAL_INDEX_VERSION = 2;
/** The compact, precomputed traversal structure. See the module header. */
export interface TraversalIndex {
    /** Number of distinct node ids in the traversal universe. */
    readonly nodeCount: number;
    /** Number of edge slots — the count of `cg.edges` that carry a `calleeId`. */
    readonly edgeCount: number;
    /** Number of strongly-connected components in the condensation. */
    readonly componentCount: number;
    /** Dense index of `id`, or -1 when the id is not in the graph. */
    indexOf(id: string): number;
    /** The id at dense index `i`. */
    idAt(i: number): string;
    hasNode(id: string): boolean;
    /**
     * The condensation component `id` belongs to, or -1 when the id is not in the
     * graph. Components are numbered in Tarjan completion order, which is a reverse
     * topological order of the condensation DAG.
     */
    componentOf(id: string): number;
    /**
     * `id`'s neighbors in `dir`, deduplicated, in exactly the order
     * `buildAdjacency(cg, filter).{forward,backward}.get(id)` yields — i.e. first
     * appearance among the edges that survive `filter`. An id not in the graph
     * yields `[]` (matching `adjacency.get(unknown) ?? []`).
     */
    neighborIds(id: string, dir: Direction, filter?: TraversalFilter): string[];
    /**
     * The number of DISTINCT neighbors of `id` in `dir` — equivalent to
     * `adjacency.get(id)?.size ?? 0`, which is how `find_path` recognizes a call-chain
     * leaf. 0 for an id that is not in the graph.
     */
    degree(id: string, dir: Direction, filter?: TraversalFilter): number;
    /**
     * Unbounded reach from `seeds` in `dir`, seeds included — the replacement for
     * the handlers' `reachAll` / `reachableFrom`. Runs as a topological scan of the
     * condensation DAG in the unfiltered case; a filtered view falls back to an
     * allocation-free CSR BFS (the condensation is built over the whole graph, and
     * a filtered graph can have strictly finer components).
     *
     * `excludeId`, when given, is removed from BOTH the seeds and the traversal —
     * `find_dead_code`'s "what dies if I delete X?" mode.
     *
     * A seed that is not in the graph is still present in the result (depth 0, no
     * expansion), matching the per-call BFS.
     */
    reachAll(seeds: Iterable<string>, dir: Direction, filter?: TraversalFilter, excludeId?: string): Set<string>;
    /**
     * Depth-bounded BFS returning visited id → depth, equivalent to
     * `bfs(seeds, adjacency, maxDepth)`. Neighbors are expanded in CSR (edge)
     * order; pass `sortNeighbors` to expand them in ascending id order instead
     * (what `select_tests` / `analyze_env_impact` do today, which fixes their
     * `parent` chains deterministically).
     */
    bfsDepths(seeds: Iterable<string>, dir: Direction, maxDepth: number, filter?: TraversalFilter, opts?: {
        sortNeighbors?: boolean;
    }): Map<string, number>;
    /**
     * {@link bfsDepths} plus the predecessor each node was first reached from —
     * the `depthOf` + `parent` pair `select_tests` reconstructs its `viaPath` from.
     */
    bfsWithParents(seeds: Iterable<string>, dir: Direction, maxDepth: number, filter?: TraversalFilter, opts?: {
        sortNeighbors?: boolean;
        /**
         * Stop as soon as this id is reached. The result then covers only what was
         * explored up to that point — enough to reconstruct the path TO `stopAt`,
         * which is all a single-target reachability question needs.
         */
        stopAt?: string;
    }): {
        depth: Map<string, number>;
        parent: Map<string, string>;
    };
}
/**
 * Build the traversal index for a serialized call graph.
 *
 * The node universe reproduces `buildAdjacency`'s exactly: every `cg.nodes` id,
 * plus every `calleeId` (external leaves get adjacency entries there too), plus
 * every `callerId` (which appears inside backward adjacency sets even when it is
 * not itself a key). Forward slots are emitted only for callers that are keys in
 * that map — the `forward.get(e.callerId)?.add(...)` optional-chain drop — so an
 * edge from an unknown caller contributes to backward adjacency only, exactly as
 * today.
 */
export declare function buildTraversalIndex(cg: SerializedCallGraph): TraversalIndex;
/**
 * The persisted form. `nodeIds` carries the string universe; every other array is
 * a base64-encoded typed-array buffer. `contextDigest` binds the structure to the
 * exact bytes of the `llm-context.json` it was built from — a structure whose
 * digest does not match the graph being served is discarded, never traversed, so
 * it can never survive a graph it was not built from.
 */
export interface SerializedTraversalIndex {
    version: number;
    /** SHA-256 of the llm-context.json content this structure was built from. */
    contextDigest: string;
    /**
     * SHA-256 over this structure's OWN payload (`nodeIds` + every array).
     *
     * `contextDigest` binds the structure to the right graph; it says nothing about
     * whether the structure's own bytes survived the trip. Length checks alone do
     * not close that: a single flipped base64 character keeps every array the right
     * length and silently changes reachability answers — an out-of-range `targets`
     * entry made `neighborIds` yield `undefined`, and a corrupted `component` made a
     * live node report as unreachable, i.e. a false "dead code" conclusion. Hashing
     * the payload (~2 ms on a 1.2 MB artifact) turns that whole class into a clean
     * refusal-and-rebuild.
     */
    payloadDigest: string;
    /** Typed arrays are host-endian; a foreign-endian artifact is rejected. */
    littleEndian: boolean;
    nodeCount: number;
    /** Component counts, per direction (the two condensations can differ). */
    componentCounts: {
        forward: number;
        backward: number;
    };
    nodeIds: string[];
    arrays: Record<string, string>;
}
/** Serialize an index built by {@link buildTraversalIndex}, bound to `contextDigest`. */
export declare function serializeTraversalIndex(cg: SerializedCallGraph, contextDigest: string): string;
/**
 * Build and persist the structure for `cg` next to the analysis artifacts, stamped
 * with the digest of the `llm-context.json` content it accompanies. The single
 * writer both surfaces use — a full `analyze` (artifact-generator) and an
 * incremental watcher flush — so the two can never disagree about the layout or
 * the invalidation key.
 *
 * The write is atomic (temp + rename); the caller owns any lock discipline.
 */
export declare function writeTraversalIndexArtifact(outputDir: string, cg: SerializedCallGraph, 
/**
 * Digest of the `llm-context.json` bytes this structure accompanies. Takes the DIGEST rather than
 * the JSON because that content is now streamed to disk and never exists as one string — it is
 * too large to, on the repositories this matters for (see `json-stream.ts`).
 */
contextDigest: string): Promise<void>;
/**
 * Rehydrate a persisted index, or return null when it cannot be trusted: wrong
 * schema version, foreign endianness, a `contextDigest` that does not match the
 * graph being served, a payload that does not match its own digest, or any
 * structural inconsistency. Null means "rebuild in memory" — a wrong structure is
 * never preferred to a slower correct one.
 *
 * Validation is deliberately layered, because each layer catches a class the one
 * before it cannot:
 *  - `contextDigest`  — the structure belongs to ANOTHER graph generation.
 *  - `payloadDigest`  — the structure's own bytes were altered (bitrot, a partial
 *                       write, a hand edit that kept every length intact).
 *  - shape + range    — a hand-edited artifact whose digest was recomputed. Every
 *                       array that INDEXES another is bounds-checked here, so no
 *                       traversal can read past the end of a typed array and hand
 *                       back an `undefined` id or a silently truncated reach.
 */
export declare function deserializeTraversalIndex(raw: string, expectedDigest: string): TraversalIndex | null;
//# sourceMappingURL=condensation.d.ts.map