/**
 * dag.ts — Pure DAG logic for plan step scheduling.
 *
 * Implements the Critical Path Method (CPM):
 *   - Parse plan markdown into a dependency DAG of PlanSteps.
 *   - Compute critical-path priorities (reverse-pass longest-path).
 *   - Identify ready steps (all predecessors done).
 *   - Build scoped prompts for sub-agents (step text + predecessor results only).
 *   - Extract structured step results for lean context propagation.
 *
 * All functions are pure and dependency-free for easy unit testing.
 */
export type StepStatus = "pending" | "in_flight" | "done" | "failed";
export interface PlanStep {
    /** 1-based step number from the plan. */
    id: number;
    /** The step's description text. */
    text: string;
    /** IDs of steps that must complete before this one. */
    dependencies: number[];
    /** Estimated complexity weight (default 1). */
    weight: number;
    /** Current execution status. */
    status: StepStatus;
    /** Result text from the sub-agent (set after completion). */
    result?: string;
    /** Error message if the step failed. */
    error?: string;
}
export declare const STEP_RESULT_OPEN = "=== STEP RESULT (Step";
export declare const STEP_RESULT_CLOSE = "=== END STEP RESULT ===";
/**
 * Extract the structured result block from a sub-agent's raw output.
 *
 * Sub-agents are instructed to end their work with:
 *   === STEP RESULT (Step N) ===
 *   <concise summary>
 *   === END STEP RESULT ===
 *
 * If the block is present, only its inner content is returned (keeps
 * dependent-step prompts lean). If absent, the full text is returned as a
 * fallback so no information is lost.
 */
export declare function extractStepResult(raw: string): string;
/**
 * Parse plan markdown into a list of PlanSteps forming a dependency DAG.
 *
 * Strategy:
 *   - Extract numbered steps from the plan body (both `N. text` list form and
 *     `### Step N — text` heading form).
 *   - Parse `(depends: N, M)` annotations if present.
 *   - If NO step has explicit dependencies, fall back to a linear chain
 *     (step N depends on step N-1) — preserves sequential correctness for
 *     plans written without dependency awareness.
 *   - Steps referencing non-existent predecessors are silently pruned.
 *   - Duplicate step IDs are merged (first occurrence wins; later headings
 *     with the same number are skipped).
 */
export declare function parsePlanToDAG(planMarkdown: string): PlanStep[];
/**
 * Compute critical-path priority for each step in the DAG.
 *
 * CP(v) = max over successors w of [ weight(v→w) + CP(w) ]
 * Base case: terminal steps (no successors) have CP = 0.
 *
 * Returns a Map<stepId, cpPriority> where higher = dispatch first.
 * Complexity: O(|V| + |E|).
 */
export declare function computeCriticalPath(steps: PlanStep[]): Map<number, number>;
/**
 * Get steps that are ready to execute: status is "pending" and all
 * predecessors have status "done".
 *
 * Returns steps sorted by critical-path priority (highest first).
 */
export declare function getReadySteps(steps: PlanStep[], cpMap?: Map<number, number>): PlanStep[];
/**
 * Build the self-similar Nested Sub-Agent Protocol, embedding the project's
 * verification gate command so it propagates verbatim to grandchildren.
 *
 * The gate command is a project-level constant (detected once per plan), so the
 * same command reaches every nesting level when sub-agents copy this protocol
 * verbatim into their own children's prompts.
 */
export declare function buildNestingProtocol(gateCommand?: string | null): string;
/** Backward-compatible re-export for existing code that imports NESTING_PROTOCOL. */
export declare const NESTING_PROTOCOL: string;
/**
 * Build a focused prompt for a sub-agent executing a single plan step.
 *
 * The prompt contains:
 *   1. A brief overall plan summary (for orientation, not full context).
 *   2. Results from all transitive predecessor steps (ancestors) in dependency order.
 *   3. The Nested Sub-Agent Protocol (self-similar — embedded gate command).
 *   4. The step's own task text + result-contract instructions.
 *
 * This is the core context-isolation mechanism: the sub-agent does NOT receive
 * the full parent conversation, only what's relevant to its specific task.
 */
export declare function buildStepPrompt(step: PlanStep, allSteps: PlanStep[], predecessorResults: Map<number, string>, planSummary: string, gateCommand?: string | null): string;
/**
 * Detect deadlocked steps — pending steps whose transitive predecessors
 * include a failed step. Such steps can never become ready and would block
 * execution indefinitely.
 *
 * Uses iterative BFS on the ancestor chain to avoid stack overflow on
 * deeply nested DAGs. Returns an array of step IDs that are deadlocked.
 */
export declare function detectDeadlockedSteps(steps: PlanStep[]): number[];
/**
 * Extract a brief plan summary (first heading + first paragraph, or first 500 chars)
 * for use as orientation context in step prompts.
 */
export declare function extractPlanSummary(planMarkdown: string): string;
//# sourceMappingURL=dag.d.ts.map