/**
 * DAG -- receipt DAG merge and canonical linearization.
 *
 * Salvaged from `@kit/core`.
 *
 * @module
 */
import { Effect } from 'effect';
import type { ReceiptEnvelope } from './receipt.js';
/** Single vertex in a {@link ReceiptDAG}: an envelope plus its parent and child hashes. */
export interface DAGNode {
    readonly envelope: ReceiptEnvelope;
    readonly parents: ReadonlyArray<string>;
    readonly children: ReadonlyArray<string>;
}
/**
 * Immutable snapshot of the receipt DAG: the set of known nodes, the current
 * head(s), and the genesis anchor if any.
 */
export interface ReceiptDAG {
    readonly nodes: ReadonlyMap<string, DAGNode>;
    readonly heads: ReadonlyArray<string>;
    readonly genesis: string | null;
}
/** Result of a DAG merge: the updated graph, the hashes that were newly added, and whether a fork was observed. */
export interface MergeResult {
    readonly dag: ReceiptDAG;
    readonly added: ReadonlyArray<string>;
    readonly forked: boolean;
}
/** Detail record describing a single-writer fork-rule violation. */
export interface ForkViolation {
    readonly actor: string;
    readonly prevHash: string;
    readonly existing: string;
    readonly attempted: string;
}
/**
 * Result of {@link checkpoint}: the spliced (compacted) DAG, the genesis-shaped
 * checkpoint attestation envelope (returned OUT-OF-BAND, never an ingested node),
 * and the hashes that were dropped (watermark + its transitive ancestors).
 */
export interface CheckpointResult {
    readonly dag: ReceiptDAG;
    readonly checkpoint: ReceiptEnvelope;
    readonly dropped: ReadonlyArray<string>;
}
/**
 * Create an empty receipt DAG with no nodes or heads.
 *
 * @example
 * ```ts
 * const dag = DAG.empty();
 * // dag.nodes.size === 0
 * // dag.heads.length === 0
 * ```
 */
export declare const empty: () => ReceiptDAG;
/**
 * Ingest a single receipt envelope into the DAG.
 *
 * Adds the envelope as a node, wires parent/child edges, and recalculates
 * head nodes. Idempotent -- returns the same DAG if the hash already exists.
 *
 * @example
 * ```ts
 * let dag = DAG.empty();
 * dag = DAG.ingest(dag, envelope);
 * // dag.nodes.size === 1
 * ```
 */
export declare const ingest: (dag: ReceiptDAG, envelope: ReceiptEnvelope) => ReceiptDAG;
/**
 * Ingest multiple receipt envelopes into the DAG in order.
 *
 * @example
 * ```ts
 * const dag = DAG.ingestAll(DAG.empty(), [envelope1, envelope2]);
 * // dag.nodes.size === 2
 * ```
 */
export declare const ingestAll: (dag: ReceiptDAG, envelopes: ReadonlyArray<ReceiptEnvelope>) => ReceiptDAG;
/**
 * Build a DAG from an array of receipt envelopes.
 *
 * @example
 * ```ts
 * const dag = DAG.fromReceipts(envelopes);
 * // dag.nodes.size === envelopes.length
 * ```
 */
export declare const fromReceipts: (envelopes: ReadonlyArray<ReceiptEnvelope>) => ReceiptDAG;
/**
 * Check whether ingesting an envelope would violate the anti-fork rule.
 *
 * The anti-fork rule prevents a single actor from creating two children
 * of the same parent node. Returns a ForkViolation descriptor or null.
 *
 * @example
 * ```ts
 * const violation = DAG.checkForkRule(dag, envelope);
 * if (violation) {
 *   console.error(`Fork by actor ${violation.actor}`);
 * }
 * ```
 */
export declare const checkForkRule: (dag: ReceiptDAG, envelope: ReceiptEnvelope) => ForkViolation | null;
/**
 * Produce a deterministic topological ordering of all envelopes in the DAG.
 *
 * Kahn's algorithm with stable ordering: sortedInsert maintains tiebreak order in the
 * ready queue, guaranteeing deterministic topological sort across replicas.
 *
 * @example
 * ```ts
 * const dag = DAG.fromReceipts(envelopes);
 * const ordered = DAG.linearize(dag);
 * // ordered is a deterministic total order of all envelopes
 * ```
 */
export declare const linearize: (dag: ReceiptDAG) => ReadonlyArray<ReceiptEnvelope>;
/**
 * Linearize the DAG and return only envelopes after a given hash.
 *
 * @example
 * ```ts
 * const newEntries = DAG.linearizeFrom(dag, lastSeenHash);
 * // newEntries contains only envelopes after lastSeenHash
 * ```
 */
export declare const linearizeFrom: (dag: ReceiptDAG, afterHash: string) => ReadonlyArray<ReceiptEnvelope>;
/** Default bound for long-lived session DAG growth — pins the pruning policy. */
export declare const DEFAULT_MAX_DAG_NODES = 10000;
/**
 * Prune a DAG to at most `maxNodes` envelopes, retaining the most recent tail of
 * the canonical linear order. Used by long-lived LLM sessions to cap memory shape.
 */
export declare const pruneToBound: (dag: ReceiptDAG, maxNodes?: number) => ReceiptDAG;
/**
 * Get all head (childless) envelopes in the DAG.
 *
 * @example
 * ```ts
 * const heads = DAG.getHeads(dag);
 * // heads.length > 0 for non-empty DAGs
 * ```
 */
export declare const getHeads: (dag: ReceiptDAG) => ReadonlyArray<ReceiptEnvelope>;
/**
 * Get the single canonical head of the DAG via deterministic tiebreaking.
 *
 * @example
 * ```ts
 * const head = DAG.canonicalHead(dag);
 * // head is the deterministically chosen head envelope, or null if empty
 * ```
 */
export declare const canonicalHead: (dag: ReceiptDAG) => ReceiptEnvelope | null;
/**
 * Check whether the DAG has multiple heads (i.e., is in a forked state).
 *
 * @example
 * ```ts
 * if (DAG.isFork(dag)) {
 *   console.log('DAG has diverged, needs merge');
 * }
 * ```
 */
export declare const isFork: (dag: ReceiptDAG) => boolean;
/**
 * Get all ancestor hashes of a given node (transitive parents).
 *
 * @example
 * ```ts
 * const anc = DAG.ancestors(dag, headHash);
 * // anc contains all hashes reachable by following parent edges
 * ```
 */
export declare const ancestors: (dag: ReceiptDAG, hash: string) => ReadonlyArray<string>;
/**
 * Check whether node `a` is an ancestor of node `b` in the DAG.
 *
 * @example
 * ```ts
 * const yes = DAG.isAncestor(dag, genesisHash, headHash);
 * // yes === true (genesis is ancestor of everything)
 * ```
 */
export declare const isAncestor: (dag: ReceiptDAG, a: string, b: string) => boolean;
/**
 * Find the latest common ancestor of two nodes in the DAG.
 *
 * @example
 * ```ts
 * const lca = DAG.commonAncestor(dag, hashA, hashB);
 * // lca is the hash of the most recent shared ancestor, or null
 * ```
 */
export declare const commonAncestor: (dag: ReceiptDAG, a: string, b: string) => string | null;
/**
 * Return the number of nodes in the DAG.
 *
 * @example
 * ```ts
 * const n = DAG.size(dag);
 * // n === dag.nodes.size
 * ```
 */
export declare const size: (dag: ReceiptDAG) => number;
/**
 * Merge remote envelopes into a local DAG, enforcing the anti-fork rule.
 *
 * Returns the updated DAG, list of newly added hashes, and whether the
 * result is forked. Throws on anti-fork violations.
 *
 * @example
 * ```ts
 * const result = DAG.merge(localDag, remoteEnvelopes);
 * // result.dag -- updated DAG
 * // result.added -- newly ingested hashes
 * // result.forked -- true if DAG has multiple heads
 * ```
 */
export declare const merge: (local: ReceiptDAG, remote: ReadonlyArray<ReceiptEnvelope>) => MergeResult;
/**
 * Splice a checkpoint out of the DAG by REBUILDING FROM THE SURVIVORS.
 *
 * DROP-ONLY — never re-points a retained node's parents (a node's parents are
 * derived from the content-hash-bearing `previous`, a SHA-256 input; mutating
 * them would forge identity). We instead collect every retained envelope and
 * `fromReceipts` them afresh, so the spliced DAG EQUALS a fresh reload by
 * construction. `genesis` collapses to `null` naturally once the old root is
 * dropped — `dag.genesis` has no production readers.
 *
 * @example
 * ```ts
 * const compacted = DAG.spliceCheckpoint(dag, new Set([oldRoot, ...ancestors]));
 * // compacted deep-equals DAG.fromReceipts(retainedEnvelopes)
 * ```
 */
export declare const spliceCheckpoint: (dag: ReceiptDAG, dropSet: ReadonlySet<string>) => ReceiptDAG;
/**
 * Compact the DAG below a watermark, returning a checkpoint attestation.
 *
 * DROP-ONLY reclamation: drops the watermark `W` plus all of its transitive
 * ancestors, leaving every retained node's content-addressed identity intact.
 * Async because minting the checkpoint hashes via `crypto.subtle` — kept off the
 * hot path by construction.
 *
 * Preconditions:
 * - `W` must be a known node (`dag.checkpoint.unknown-watermark` otherwise).
 * - DOMINANCE: every parent edge that crosses the drop boundary (a dropped
 *   parent of a retained child) must land on `W`, else `W` does not dominate the
 *   dropped region and reclaiming it would orphan a survivor
 *   (`dag.checkpoint.not-dominated`).
 *
 * The checkpoint is a real genesis-shaped {@link ReceiptEnvelope}
 * (`previous = GENESIS`, `subject.id = "czap/checkpoint:<W>"` committing the
 * watermark, `timestamp` = HLC-max over the dropped envelopes), hashed via
 * `Receipt.hashEnvelope` so two replicas that reach the same `W` mint a
 * byte-identical attestation. It is RETURNED OUT-OF-BAND, never inserted as a
 * node (which would spuriously read as a second head / fork).
 *
 * @example
 * ```ts
 * const { dag: compacted, checkpoint, dropped } = yield* DAG.checkpoint(dag, { below: W });
 * // compacted has `dropped.length` fewer nodes; `checkpoint.subject.id` commits W
 * ```
 */
export declare const checkpoint: (dag: ReceiptDAG, options: {
    readonly below: string;
}) => Effect.Effect<CheckpointResult>;
/**
 * DAG namespace -- receipt DAG merge and canonical linearization.
 *
 * Build, query, and merge directed acyclic graphs of receipt envelopes.
 * Supports deterministic linearization, fork detection, ancestor queries,
 * and anti-fork rule enforcement.
 *
 * @example
 * ```ts
 * import { DAG } from '@czap/core';
 *
 * const dag = DAG.fromReceipts(envelopes);
 * const ordered = DAG.linearize(dag);
 * const forked = DAG.isFork(dag);
 * const result = DAG.merge(dag, remoteEnvelopes);
 * ```
 */
export declare const DAG: {
    empty: () => ReceiptDAG;
    ingest: (dag: ReceiptDAG, envelope: ReceiptEnvelope) => ReceiptDAG;
    ingestAll: (dag: ReceiptDAG, envelopes: ReadonlyArray<ReceiptEnvelope>) => ReceiptDAG;
    fromReceipts: (envelopes: ReadonlyArray<ReceiptEnvelope>) => ReceiptDAG;
    checkForkRule: (dag: ReceiptDAG, envelope: ReceiptEnvelope) => ForkViolation | null;
    linearize: (dag: ReceiptDAG) => ReadonlyArray<ReceiptEnvelope>;
    linearizeFrom: (dag: ReceiptDAG, afterHash: string) => ReadonlyArray<ReceiptEnvelope>;
    pruneToBound: (dag: ReceiptDAG, maxNodes?: number) => ReceiptDAG;
    getHeads: (dag: ReceiptDAG) => ReadonlyArray<ReceiptEnvelope>;
    canonicalHead: (dag: ReceiptDAG) => ReceiptEnvelope | null;
    isFork: (dag: ReceiptDAG) => boolean;
    ancestors: (dag: ReceiptDAG, hash: string) => ReadonlyArray<string>;
    isAncestor: (dag: ReceiptDAG, a: string, b: string) => boolean;
    commonAncestor: (dag: ReceiptDAG, a: string, b: string) => string | null;
    size: (dag: ReceiptDAG) => number;
    merge: (local: ReceiptDAG, remote: ReadonlyArray<ReceiptEnvelope>) => MergeResult;
    checkpoint: (dag: ReceiptDAG, options: {
        readonly below: string;
    }) => Effect.Effect<CheckpointResult>;
    spliceCheckpoint: (dag: ReceiptDAG, dropSet: ReadonlySet<string>) => ReceiptDAG;
};
export declare namespace DAG {
    /** Alias for {@link DAGNode}. */
    type Node = DAGNode;
    /** Alias for {@link ReceiptDAG}. */
    type Graph = ReceiptDAG;
    /** Alias for {@link MergeResult}. */
    type Merge = MergeResult;
    /** Alias for {@link ForkViolation}. */
    type Fork = ForkViolation;
    /** The genesis-shaped checkpoint attestation a compaction emits out-of-band. */
    type Checkpoint = {
        readonly envelope: ReceiptEnvelope;
        readonly dropped: readonly string[];
        readonly watermark: string;
    };
    /** Alias for {@link CheckpointResult}. */
    type CompactResult = CheckpointResult;
}
//# sourceMappingURL=dag.d.ts.map