// File: src/strategies/tree-of-thought.ts
/**
 * Tree-of-Thought Strategy
 *
 * Breadth-first thought expansion: generate multiple candidate thoughts,
 * score each branch, prune below threshold, then select the best path.
 *
 * Phase 1: BFS exploration — generate, score, prune, select best path.
 * Phase 2: Execute selected plan using the shared ReAct kernel.
 */
import { Effect } from "effect";
import { ulid } from "ulid";
import type { ReasoningResult, ReasoningStep } from "../types/index.js";
import { ExecutionError } from "../errors/errors.js";
import type { ReasoningConfig } from "../types/config.js";
import { LLMService } from "@reactive-agents/llm-provider";
import { runKernel } from "../kernel/loop/runner.js";
import { reactKernel } from "../kernel/loop/react-kernel.js";
import { buildKernelInput, type CrossCuttingInput } from "../kernel/state/build-kernel-input.js";
import { resolveStrategyServices, compilePromptOrFallback, publishReasoningStep, makeStrategyEmitLog, emitPhaseEnd } from "../kernel/utils/service-utils.js";
import { parseScore } from "../kernel/capabilities/verify/quality-utils.js";
import {
  extractThinkingSafeContent,
  THINKING_SAFE_MIN_TOKENS,
} from "../kernel/utils/stream-parser.js";
import type { ToolSchema } from "../kernel/capabilities/attend/tool-formatting.js";
import type { ResultCompressionConfig } from "@reactive-agents/tools";
import type { KernelMetaToolsConfig } from "../types/kernel-meta-tools.js";
import { makeStep, buildStrategyResult } from "../kernel/capabilities/sense/step-utils.js";
import { resolveExecutableToolCapabilities } from "../kernel/capabilities/act/tool-capabilities.js";
import { emitKernelStateSnapshot } from "../kernel/utils/diagnostics.js";
import { withEnvContext } from "../context/context-engine.js";
import { classifyTaskComplexity } from "../kernel/capabilities/comprehend/task-complexity.js";
import type { TaskClassification } from "../kernel/capabilities/comprehend/task-classification.js";

// ── Tier-Adaptive ToT Limits ─────────────────────────────────────────────────

/** Per-tier limits for tree-of-thought BFS depth and Phase 2 kernel iterations. */
export interface ToTTierLimit {
  /** Maximum BFS exploration depth (caps the config `depth`). */
  readonly maxBfsDepth: number;
  /** Maximum iterations for Phase 2 ReAct kernel execution. */
  readonly maxPhase2Iterations: number;
  /** Number of consecutive stagnant rounds before early BFS exit. */
  readonly stagnationWindow: number;
}

export const TOT_TIER_LIMITS: Record<"local" | "mid" | "large" | "frontier", ToTTierLimit> = {
  local:    { maxBfsDepth: 2, maxPhase2Iterations: 6,  stagnationWindow: 3 },
  mid:      { maxBfsDepth: 3, maxPhase2Iterations: 8,  stagnationWindow: 3 },
  large:    { maxBfsDepth: 4, maxPhase2Iterations: 10, stagnationWindow: 3 },
  frontier: { maxBfsDepth: 5, maxPhase2Iterations: 12, stagnationWindow: 3 },
};

/** Get the effective BFS depth, capped by tier limits. */
export function getToTDepthForTier(
  configDepth: number,
  tier: "local" | "mid" | "large" | "frontier" | undefined,
): number {
  const limits = TOT_TIER_LIMITS[tier ?? "mid"];
  return Math.min(configDepth, limits.maxBfsDepth);
}

interface TreeOfThoughtInput {
  readonly taskDescription: string;
  readonly taskType: string;
  readonly memoryContext: string;
  readonly availableTools: readonly string[];
  readonly availableToolSchemas?: readonly ToolSchema[];
  readonly config: ReasoningConfig;
  /** Custom system prompt for steering agent behavior */
  readonly systemPrompt?: string;
  /** Task ID for event correlation */
  readonly taskId?: string;
  /** Tool result compression config */
  readonly resultCompression?: ResultCompressionConfig;
  /** Agent ID for tool execution attribution. Falls back to "reasoning-agent". */
  readonly agentId?: string;
  /** Session ID for tool execution attribution. Falls back to "reasoning-session". */
  readonly sessionId?: string;
  /** Tools that MUST be called before the agent can declare success */
  readonly requiredTools?: readonly string[];
  /** Classifier-relevant tools — visible/usable but not gate-enforced. MUST be
   *  forwarded to each kernel pass; under lazy tool disclosure the kernel prunes
   *  any tool not in required+relevant+used+discovered+meta, leaving the model
   *  blind to MCP/user tools (see reflexion / spot-test GitHub-MCP regression). */
  readonly relevantTools?: readonly string[];
  /** Max redirects when required tools are missing (default: 2) */
  readonly maxRequiredToolRetries?: number;
  /** Model identifier for routing/entropy scoring */
  readonly modelId?: string;
  /** LLM temperature override */
  readonly temperature?: number;
  readonly synthesisConfig?: import("../context/synthesis-types.js").SynthesisConfig;
  readonly metaTools?: KernelMetaToolsConfig;
  readonly briefResolvedSkills?: readonly { readonly name: string; readonly purpose: string }[];
  /** Model tier for tier-adaptive iteration limits. */
  readonly tier?: "local" | "mid" | "large" | "frontier";
  /**
   * Pre-computed task classification from the upstream `comprehend` pass.
   * When provided, ToT reads complexity/intent from this snapshot and does
   * NOT re-classify (HS-cleanup-2). When absent (direct caller without
   * upstream classification), ToT computes its own — backward-compatible.
   */
  readonly taskClassification?: TaskClassification;
  /**
   * GH #127 — Compose harness pipeline threaded through ToT's BFS-iteration
   * RI dispatchContext so applied decisions emit bridged Compose tags
   * (`control.strategy-evaluated`, `lifecycle.failure`, `nudge.healing-failure`)
   * under this outer strategy. Without this thread, users who register
   * `.withHarness(h => h.tap('control.strategy-evaluated', …))` see
   * kernel-path emissions (reactive) but ToT remains dark. Mirrors the
   * kernel-side wire at `kernel/capabilities/reflect/reactive-observer.ts:306`
   * (HS-112).
   */
  readonly harnessPipeline?: import("@reactive-agents/core").HarnessPipeline;
  // FM-I (#195): cross-cutting fields that must reach every branch kernel.
  /** Budget killswitch limits (budgetLimit/watchdog). */
  readonly budgetLimits?: import("../kernel/capabilities/decide/arbitrator.js").BudgetLimits;
  /** Pre-resolved model calibration — drives steering channel selection. */
  readonly calibration?: import("@reactive-agents/llm-provider").ModelCalibration;
  /** Opt-in per-tool-call rationale auditing. */
  readonly auditRationale?: boolean;
}

interface ThoughtNode {
  readonly id: string;
  readonly content: string;
  readonly score: number;
  readonly depth: number;
  readonly parentId: string | null;
}

export const executeTreeOfThought = (
  input: TreeOfThoughtInput,
): Effect.Effect<
  ReasoningResult,
  ExecutionError,
  LLMService
> =>
  Effect.gen(function* () {
    const services = yield* resolveStrategyServices;
    const { llm, promptService, eventBus } = services;

    const emitLog = makeStrategyEmitLog("reasoning/src/strategies/tree-of-thought.ts:emitLog");

    const { breadth, depth, pruningThreshold } =
      input.config.strategies.treeOfThought;
    const capabilitySnapshot = yield* resolveExecutableToolCapabilities({
      availableToolSchemas: input.availableToolSchemas,
      metaTools: input.metaTools,
    });
    // FM-I (#195): run-wide cross-cutting bundle, built once, fed to every
    // branch kernel via buildKernelInput. Previously these branch kernels
    // dropped harnessPipeline/budgetLimits/calibration/auditRationale.
    const crossCutting: CrossCuttingInput = {
      resultCompression: input.resultCompression,
      agentId: input.agentId,
      sessionId: input.sessionId,
      requiredTools: input.requiredTools,
      relevantTools: input.relevantTools,
      maxRequiredToolRetries: input.maxRequiredToolRetries,
      synthesisConfig: input.synthesisConfig,
      metaTools: input.metaTools,
      briefResolvedSkills: input.briefResolvedSkills,
      modelId: input.modelId,
      harnessPipeline: input.harnessPipeline,
      budgetLimits: input.budgetLimits,
      calibration: input.calibration,
      auditRationale: input.auditRationale,
    };
    const maxCost = input.config.strategies.treeOfThought.maxCost;
    const steps: ReasoningStep[] = [];
    const start = Date.now();
    // Explore wall-clock budget (graceful degradation). The BFS explore phase
    // makes many serial expansion+scoring LLM calls; on slow thinking models it
    // can run minutes and starve Phase 2 (the react execute) of time before an
    // external timeout kills the run with 0 output. Bounding explore on the
    // wall-clock leaves room for Phase 2 to always emit a best-so-far answer.
    // Env-overridable; default 120s sits comfortably under typical run timeouts.
    const exploreBudgetMs = Number(process.env.RA_TOT_EXPLORE_BUDGET_MS ?? 120_000);
    let totalTokens = 0;
    let totalCost = 0;

    // ── HS-110 / M3 cost gate (sweep-2026-05-23) ──
    //
    // ToT BFS exploration ran on every task regardless of complexity. Probe
    // evidence showed ToT × trivial tasks costing 3.3× reactive (frontier) and
    // 23× reactive (local-tier) for identical answers. Direct anti-mission #6
    // violation ("NOT a system that spends cost without proportional return").
    //
    // Gate: classify the task pre-execution. If trivial with high confidence,
    // skip the BFS exploration entirely and delegate to the same react kernel
    // ToT's Phase 2 would have used — without a `priorContext` from a wasted
    // exploration phase. Moderate/complex tasks fall through to full BFS.
    const skipBfsForTrivial =
      input.config.strategies.treeOfThought.skipBfsForTrivial !== false;
    // HS-cleanup-2: prefer upstream classification when threaded; classify
    // locally only when invoked outside the engine path.
    const complexityVerdict =
      input.taskClassification?.complexity ??
      classifyTaskComplexity(input.taskDescription);
    const SKIP_BFS_CONFIDENCE = 0.7;
    if (
      skipBfsForTrivial &&
      complexityVerdict.complexity === "trivial" &&
      complexityVerdict.confidence >= SKIP_BFS_CONFIDENCE
    ) {
      yield* emitLog({
        _tag: "phase_started",
        phase: "tree-of-thought:bfs-skipped",
        timestamp: new Date(),
      });
      steps.push(
        makeStep(
          "observation",
          `[TOT] BFS exploration skipped — task classified ${complexityVerdict.complexity} (${complexityVerdict.reason}, confidence=${complexityVerdict.confidence.toFixed(2)}). Delegating to react kernel directly.`,
          { frameworkInstrumentation: "tot-marker" },
        ),
      );

      const tierLimitsForSkip = TOT_TIER_LIMITS[input.tier ?? "mid"];
      const skipExecState = yield* runKernel(reactKernel, buildKernelInput(crossCutting, {
        task: input.taskDescription,
        systemPrompt: input.systemPrompt,
        availableToolSchemas: capabilitySnapshot.availableToolSchemas,
        allToolSchemas: capabilitySnapshot.allToolSchemas,
        temperature: 0.7,
      }), {
        maxIterations: tierLimitsForSkip.maxPhase2Iterations,
        strategy: "tree-of-thought",
        kernelType: "react",
        taskId: input.taskId,
        kernelPass: "tree-of-thought:bfs-skipped",
        modelId: input.modelId,
        taskDescription: input.taskDescription,
        temperature: 0.7,
      });

      totalTokens += skipExecState.tokens;
      totalCost += skipExecState.cost;
      steps.push(...skipExecState.steps);
      const skipFinalOutput =
        skipExecState.output ??
        [...skipExecState.steps]
          .filter((s) => s.type === "thought")
          .pop()?.content ??
        null;

      yield* emitLog({
        _tag: "completion",
        success: !!skipFinalOutput,
        summary: skipFinalOutput
          ? "Tree-of-thought completed via cost-gated skip (trivial task)"
          : "Tree-of-thought failed via cost-gated skip path",
        timestamp: new Date(),
      });

      return buildStrategyResult({
        strategy: "tree-of-thought",
        steps,
        output: skipFinalOutput || null,
        status: skipFinalOutput ? "completed" : "partial",
        start,
        totalTokens,
        totalCost,
        extraMetadata: {
          bfsSkipped: true,
          bfsSkipReason: complexityVerdict.reason,
          bfsSkipConfidence: complexityVerdict.confidence,
        },
      });
    }

    // All thought nodes across the tree
    let allNodes: ThoughtNode[] = [];

    // Current frontier (nodes at current depth to expand)
    let frontier: ThoughtNode[] = [
      {
        id: ulid(),
        content: `Root: ${input.taskDescription}`,
        score: 1.0,
        depth: 0,
        parentId: null,
      },
    ];

    yield* emitLog({ _tag: "phase_started", phase: "tree-of-thought:explore", timestamp: new Date() });

    steps.push(makeStep("thought", `[TOT] Starting tree exploration: breadth=${breadth}, depth=${depth}, pruningThreshold=${pruningThreshold}`, { frameworkInstrumentation: "tot-marker" }));

    // ── Tier-adaptive depth cap ──
    const tierLimits = TOT_TIER_LIMITS[input.tier ?? "mid"];
    const effectiveDepth = Math.min(depth, tierLimits.maxBfsDepth);

    // ── W5 FIX-5: ToT outer-loop early-stop wiring ──
    // Per-strategy RI budget mirrors plan-execute's perStrategyRiBudget so the
    // dispatcher's suppression gates (maxFiresPerRun, maxInterventionTokenBudget)
    // see real counts across BFS depth levels. Pre-W5, ToT silently ignored
    // dispatcher early-stop signals — the outer for-loop ran to completion
    // even when the controller had decided to terminate. Audit M2 verdict +
    // FIX-5 / NS §2.5 architectural alignment.
    let perStrategyEarlyStop = false;
    const perStrategyRiBudget = {
      interventionsFiredThisRun: 0,
      tokensSpentOnInterventions: 0,
    };

    // ── BFS expansion ──
    let bestScorePerDepth: number[] = [];
    for (let d = 1; d <= effectiveDepth; d++) {
      const nextFrontier: ThoughtNode[] = [];

      // HS-113 / E2: outer-loop snapshot at each BFS depth boundary.
      yield* emitKernelStateSnapshot({
        state: {
          status: "thinking" as const,
          steps: steps.map((s) => ({ type: s.type })),
          toolsUsed: new Set<string>(),
          tokens: totalTokens,
          cost: totalCost,
        },
        taskId: input.taskId ?? "tree-of-thought",
        iteration: d,
        outerLoopName: "tree-of-thought:explore",
        outerIter: d,
      });

      // Budget guard: abort exploration if cost exceeds limit
      if (maxCost !== undefined && totalCost >= maxCost) {
        steps.push(makeStep("observation", `[TOT] Budget guard: cost $${totalCost.toFixed(4)} reached limit $${maxCost.toFixed(4)}. Stopping exploration.`, { frameworkInstrumentation: "tot-marker" }));
        break;
      }

      // Wall-clock guard: stop exploring once the explore budget is spent so
      // Phase 2 (best-path execution) still runs and emits a best-so-far answer
      // instead of the whole run being killed mid-explore with 0 output.
      const exploreElapsed = Date.now() - start;
      if (exploreElapsed >= exploreBudgetMs) {
        steps.push(makeStep("observation", `[TOT] Wall-clock guard: explore phase ${Math.round(exploreElapsed / 1000)}s reached budget ${Math.round(exploreBudgetMs / 1000)}s. Stopping exploration; executing best path so far.`, { frameworkInstrumentation: "tot-marker" }));
        break;
      }

      for (const parent of frontier) {
        // Generate `breadth` candidate thoughts from this parent
        const expansionResponse = yield* llm
          .complete({
            messages: [
              {
                role: "user",
                content: buildExpansionPrompt(
                  input,
                  parent,
                  breadth,
                  getAncestorPath(allNodes, parent),
                ),
              },
            ],
            systemPrompt: withEnvContext(
              yield* compilePromptOrFallback(
                promptService,
                "reasoning.tree-of-thought-expand",
                { task: input.taskDescription, breadth },
                input.systemPrompt
                  ? `${input.systemPrompt}\n\nYou are exploring solution paths for: ${input.taskDescription}. Generate ${breadth} distinct approaches.`
                  : `You are exploring solution paths for: ${input.taskDescription}. Generate ${breadth} distinct approaches.`,
              ),
            ),
            maxTokens: Math.max(800 * breadth, THINKING_SAFE_MIN_TOKENS),
            temperature: 0.8,
          })
          .pipe(
            Effect.mapError(
              (err) =>
                new ExecutionError({
                  strategy: "tree-of-thought",
                  message: `Expansion failed at depth ${d}`,
                  step: d,
                  cause: err,
                }),
            ),
          );

        totalTokens += expansionResponse.usage.totalTokens;
        totalCost += expansionResponse.usage.estimatedCost;

        // Thinking-safe extraction: rescues candidates trapped inside <think>
        // (strict upgrade vs bare stripThinking).
        const candidates = parseCandidates(
          extractThinkingSafeContent(expansionResponse).content,
          breadth,
        );

        // ── Batch scoring ──
        // Score ALL candidates of this parent in ONE call. They share the same
        // ancestor path, so per-candidate calls re-sent the task + path + rubric
        // B times (the dominant ToT token cost — local tiers have no prompt
        // caching). Budget guard runs once before the single call.
        let scores: number[] = candidates.map(() => 0.5);
        if (maxCost !== undefined && totalCost >= maxCost) {
          steps.push(makeStep("observation", `[TOT] Budget guard: cost $${totalCost.toFixed(4)} reached limit $${maxCost.toFixed(4)}. Stopping scoring.`, { frameworkInstrumentation: "tot-marker" }));
        } else if (candidates.length > 0) {
          const scoringSystemPrompt = yield* compilePromptOrFallback(
            promptService,
            "reasoning.tree-of-thought-score",
            {},
            input.systemPrompt
              ? `${input.systemPrompt}\n\nYou are evaluating reasoning paths. Rate each candidate's promise on a scale of 0.0 to 1.0.`
              : "You are evaluating reasoning paths. Rate each candidate's promise on a scale of 0.0 to 1.0.",
          );
          const ancestorPath = getAncestorPath(allNodes, parent);

          // One score-evaluation call for the whole parent. Budget must cover a
          // thinking model's single reasoning pass + N score lines — too tight a
          // budget truncates `<think>` before any score is emitted, collapsing
          // every candidate to the 0.5 default. Scale headroom with breadth.
          const scoreResponse = yield* llm
            .complete({
              messages: [
                { role: "user", content: buildBatchScoringPrompt(input.taskDescription, candidates, ancestorPath) },
              ],
              systemPrompt: scoringSystemPrompt,
              maxTokens: THINKING_SAFE_MIN_TOKENS + 512 * candidates.length,
              temperature: 0.2,
            })
            .pipe(
              Effect.mapError(
                (err) =>
                  new ExecutionError({
                    strategy: "tree-of-thought",
                    message: `Scoring failed at depth ${d}`,
                    step: d,
                    cause: err,
                  }),
              ),
            );

          totalTokens += scoreResponse.usage.totalTokens;
          totalCost += scoreResponse.usage.estimatedCost;

          const batchRaw = extractThinkingSafeContent(scoreResponse).content;
          const batch = parseBatchScoresDetailed(batchRaw, candidates.length);
          scores = batch.scores;

          // Fallback: the batch response carried no usable scores (e.g. a
          // thinking model truncated mid-`<think>`). Re-score each candidate
          // alone — one candidate fits the budget, so it parses reliably. Costs
          // the batching savings on that parent but never ships an all-0.5
          // collapse that makes pruning blind.
          if (!batch.ok) {
            for (let ci = 0; ci < candidates.length; ci++) {
              const single = yield* llm
                .complete({
                  messages: [
                    { role: "user", content: buildBatchScoringPrompt(input.taskDescription, [candidates[ci]!], ancestorPath) },
                  ],
                  systemPrompt: scoringSystemPrompt,
                  maxTokens: THINKING_SAFE_MIN_TOKENS,
                  temperature: 0.2,
                })
                .pipe(
                  Effect.mapError(
                    (err) =>
                      new ExecutionError({
                        strategy: "tree-of-thought",
                        message: `Scoring failed at depth ${d}`,
                        step: d,
                        cause: err,
                      }),
                  ),
                );
              totalTokens += single.usage.totalTokens;
              totalCost += single.usage.estimatedCost;
              scores[ci] = parseScore(extractThinkingSafeContent(single).content);
            }
          }
        }

        // Materialize nodes from the batched scores.
        for (let ci = 0; ci < candidates.length; ci++) {
          const candidate = candidates[ci]!;
          const score = scores[ci] ?? 0.5;

          const node: ThoughtNode = {
            id: ulid(),
            content: candidate,
            score,
            depth: d,
            parentId: parent.id,
          };

          allNodes.push(node);

          steps.push(makeStep("thought", `[TOT d=${d}] score=${score.toFixed(2)}: ${candidate.substring(0, 100)}...`));

          yield* publishReasoningStep(eventBus, {
            _tag: "ReasoningStepCompleted",
            taskId: input.taskId ?? "tree-of-thought",
            strategy: "tree-of-thought",
            step: steps.length,
            totalSteps: depth * breadth,
            thought: `[TOT d=${d}] score=${score.toFixed(2)}: ${candidate.substring(0, 100)}...`,
            kernelPass: "tree-of-thought:explore",
          });

          // Prune: only keep nodes above threshold
          if (score >= pruningThreshold) {
            nextFrontier.push(node);
          }
        }
      }

      // ── Score stagnation check ──
      const nodesThisRound = allNodes.filter((n) => n.depth === d);
      const bestThisRound = nodesThisRound.length > 0
        ? Math.max(...nodesThisRound.map((n) => n.score))
        : 0;
      bestScorePerDepth.push(bestThisRound);

      if (bestScorePerDepth.length >= tierLimits.stagnationWindow) {
        const window = bestScorePerDepth.slice(-tierLimits.stagnationWindow);
        const maxInWindow = Math.max(...window);
        const minInWindow = Math.min(...window);
        if (maxInWindow - minInWindow < 0.05) {
          steps.push(makeStep("observation", `[TOT] Score stagnation detected: best scores ${window.map((s) => s.toFixed(2)).join(", ")} over ${tierLimits.stagnationWindow} rounds. Forcing convergence.`, { frameworkInstrumentation: "tot-marker" }));
          break;
        }
      }

      // If all paths pruned, try adaptive pruning before giving up
      if (nextFrontier.length === 0) {
        // Adaptive pruning: lower threshold by 0.15 before giving up entirely
        const adaptiveThreshold = Math.max(0.15, pruningThreshold - 0.15);
        const nodesAtThisDepth = allNodes.filter((n) => n.depth === d);
        const rescued = nodesAtThisDepth
          .filter((n) => n.score >= adaptiveThreshold)
          .sort((a, b) => b.score - a.score)
          .slice(0, breadth);

        if (rescued.length > 0) {
          steps.push(makeStep("observation", `[TOT] Adaptive pruning at depth ${d}: threshold ${pruningThreshold} → ${adaptiveThreshold}, rescued ${rescued.length} path(s).`, { frameworkInstrumentation: "tot-marker" }));
          frontier = rescued;
          continue;
        }

        // Log the adaptive attempt even when no paths could be rescued
        steps.push(makeStep("observation", `[TOT] Adaptive pruning at depth ${d}: threshold ${pruningThreshold} → ${adaptiveThreshold}, no paths above adaptive threshold. Selecting best from all explored nodes.`, { frameworkInstrumentation: "tot-marker" }));
        break;
      }


      // Sort by score and keep top `breadth` nodes for next depth
      frontier = nextFrontier
        .sort((a, b) => b.score - a.score)
        .slice(0, breadth);

      // ── W5 FIX-5: dispatcher early-stop check at end of depth ──
      // Score the best thought of this depth via entropySensor, evaluate
      // decisions through the reactive controller, dispatch any patches.
      // Watch for early-stop. Mirrors plan-execute.ts:605,716,741.
      if (
        services.reactiveController._tag === "Some" &&
        services.dispatcher._tag === "Some" &&
        services.entropySensor._tag === "Some" &&
        frontier.length > 0
      ) {
        const bestNode = frontier[0]!;
        const syntheticState = {
          taskId: input.taskId ?? "tree-of-thought",
          strategy: "tree-of-thought",
          kernelType: "tree-of-thought",
          steps: steps.map((rs) => ({
            type: rs.type,
            ...(rs.content != null ? { content: rs.content } : {}),
          })),
          toolsUsed: new Set<string>(),
          iteration: d,
          tokens: totalTokens,
          status: "observing",
          output: null,
          error: null,
          meta: {} as Record<string, unknown>,
        };
        const scoreResult = yield* services.entropySensor.value
          .score({
            thought: bestNode.content,
            taskDescription: input.taskDescription ?? "",
            strategy: "tree-of-thought",
            iteration: d,
            maxIterations: effectiveDepth,
            modelId: input.modelId ?? "unknown",
            temperature: input.temperature ?? 0,
            kernelState: syntheticState,
          })
          .pipe(Effect.catchAll(() => Effect.succeed(null)));
        if (scoreResult !== null) {
          const sources = (scoreResult as Record<string, unknown>)["sources"] as Record<string, number> | undefined;
          const decisions = yield* services.reactiveController.value
            .evaluate({
              entropyHistory: [{
                composite: scoreResult.composite,
                trajectory: scoreResult.trajectory,
              }],
              iteration: d,
              maxIterations: effectiveDepth,
              strategy: "tree-of-thought",
              calibration: { highEntropyThreshold: 0.8, convergenceThreshold: 0.4, calibrated: false, sampleCount: 0 },
              config: { earlyStop: true, contextCompression: false, strategySwitch: false },
              contextPressure: sources?.["contextPressure"] ?? 0,
              behavioralLoopScore: sources?.["behavioral"] ?? 0,
              currentTemperature: input.temperature,
            })
            .pipe(Effect.catchAll(() => Effect.succeed([])));
          if (decisions.length > 0) {
            const dispatchContext = {
              iteration: d,
              entropyScore: {
                composite: scoreResult.composite,
                token: 0,
                structural: sources?.["structural"] ?? 0,
                semantic: sources?.["semantic"] ?? 0,
                behavioral: sources?.["behavioral"] ?? 0,
                contextPressure: sources?.["contextPressure"] ?? 0,
              },
              recentDecisions: decisions as readonly { readonly decision: string; readonly reason: string }[],
              budget: {
                interventionsFiredThisRun: perStrategyRiBudget.interventionsFiredThisRun,
                tokensSpentOnInterventions: perStrategyRiBudget.tokensSpentOnInterventions,
              },
              // GH #127 — bridge applied RI decisions into Compose tags on
              // ToT's BFS exploration loop. No-op when absent.
              harnessPipeline: input.harnessPipeline,
            };
            const dispatchResult = yield* services.dispatcher.value
              .dispatch(decisions as readonly { readonly decision: string; readonly reason: string }[], {}, dispatchContext)
              .pipe(Effect.catchAll(() => Effect.succeed({ appliedPatches: [], skipped: [], totalCost: { tokens: 0, latencyMs: 0 } })));
            perStrategyRiBudget.interventionsFiredThisRun += dispatchResult.appliedPatches.length;
            perStrategyRiBudget.tokensSpentOnInterventions += dispatchResult.totalCost.tokens;
            for (const { patch } of dispatchResult.appliedPatches) {
              if (patch.kind === "early-stop") perStrategyEarlyStop = true;
            }
          }
        }
      }

      if (perStrategyEarlyStop) {
        steps.push(makeStep("observation", `[TOT] Dispatcher early-stop signal received at depth ${d} — terminating exploration.`, { frameworkInstrumentation: "tot-marker" }));
        break;
      }
    }

    // ── Select best path ──
    const bestLeaf = [...allNodes, ...frontier].sort(
      (a, b) => b.score - a.score,
    )[0];

    if (!bestLeaf) {
      return buildStrategyResult({
        strategy: "tree-of-thought",
        steps,
        output: null,
        status: "partial",
        start,
        totalTokens,
        totalCost,
      });
    }

    // Reconstruct the full path
    const bestPath = getAncestorPath(allNodes, bestLeaf);

    steps.push(makeStep("observation", `[TOT] Best path (score=${bestLeaf.score.toFixed(2)}): ${bestPath.join(" -> ")}`, { frameworkInstrumentation: "tot-marker" }));

    yield* emitPhaseEnd({ emitLog, phase: "tree-of-thought:explore", startedAt: start, totalTokens });

    yield* emitLog({ _tag: "phase_started", phase: "tree-of-thought:execute", timestamp: new Date() });

    // ── Phase 2: Execute best path using ReAct kernel ──
    const bestPathSummary = bestPath.join("\n→ ");
    const execState = yield* runKernel(reactKernel, buildKernelInput(crossCutting, {
      task: input.taskDescription,
      systemPrompt: input.systemPrompt
        ? `${input.systemPrompt}\n\nYou are a systematic problem solver. Execute the given approach to produce a final answer.`
        : "You are a systematic problem solver. Execute the given approach to produce a final answer.",
      availableToolSchemas: capabilitySnapshot.availableToolSchemas,
      allToolSchemas: capabilitySnapshot.allToolSchemas,
      priorContext: `Selected Approach (from planning phase):\n${bestPathSummary}`,
      temperature: 0.7,
    }), {
      maxIterations: tierLimits.maxPhase2Iterations,
      strategy: "tree-of-thought",
      kernelType: "react",
      taskId: input.taskId,
      kernelPass: "tree-of-thought:execute",
      modelId: input.modelId,
      taskDescription: input.taskDescription,
      temperature: 0.7,
    });

    totalTokens += execState.tokens;
    totalCost += execState.cost;
    steps.push(...execState.steps);
    const finalOutput = execState.output
      ?? [...execState.steps].filter((s) => s.type === "thought").pop()?.content
      ?? null;

    yield* emitPhaseEnd({ emitLog, phase: "tree-of-thought:execute", startedAt: start });

    yield* emitLog({
      _tag: "completion",
      success: !!finalOutput,
      summary: finalOutput ? "Tree-of-thought completed successfully" : "Tree-of-thought failed to produce output",
      timestamp: new Date(),
    });

    return buildStrategyResult({
      strategy: "tree-of-thought",
      steps,
      output: finalOutput || null,
      status: finalOutput ? "completed" : "partial",
      start,
      totalTokens,
      totalCost,
    });
  });

// ─── Private Helpers ───

function buildExpansionPrompt(
  input: TreeOfThoughtInput,
  parent: ThoughtNode,
  breadth: number,
  ancestorPath: string[],
): string {
  const contextStr = ancestorPath.length > 0
    ? `\nReasoning so far:\n${ancestorPath.join("\n→ ")}`
    : "";

  const toolStr =
    input.availableToolSchemas && input.availableToolSchemas.length > 0
      ? `\nAvailable tools: ${input.availableToolSchemas.map((t) => t.name).join(", ")}`
      : input.availableTools.length > 0
        ? `\nAvailable tools: ${input.availableTools.join(", ")}`
        : "";

  const toolHint = input.availableTools.length > 0
    ? " — reference specific tools where relevant"
    : "";

  return `Current thought: ${parent.content}${contextStr}${toolStr}

Generate exactly ${breadth} distinct next thoughts or approaches to continue solving this task.
Format each as a numbered item (1., 2., etc.).
Each should explore a meaningfully different direction${toolHint}.`;
}

/**
 * Batch scoring prompt: score every candidate of one parent in a SINGLE call.
 * Per-candidate scoring re-sent the task + ancestor path + rubric once per
 * candidate (B× token bloat — the dominant ToT cost on local tiers with no
 * prompt caching). Candidates share the same parent, so the ancestor path is
 * identical for all of them: send it ONCE here.
 */
function buildBatchScoringPrompt(
  taskDescription: string,
  candidates: string[],
  ancestorPath: string[],
): string {
  const pathStr = ancestorPath.length > 0
    ? `\nPrevious reasoning:\n${ancestorPath.join("\n→ ")}`
    : "";

  const numbered = candidates
    .map((c, i) => `${i + 1}. ${c}`)
    .join("\n");

  return `Task: ${taskDescription}${pathStr}

Candidate thoughts:
${numbered}

Rate each candidate thought on a scale from 0.0 to 1.0:
- 1.0 = Directly leads to a correct, complete solution
- 0.7 = Promising direction, needs more development
- 0.5 = Plausible but uncertain
- 0.3 = Unlikely to lead to a good solution
- 0.0 = Clearly wrong or irrelevant

Respond with one line per candidate in the form \`N: SCORE\` (e.g. \`1: 0.8\`), using the candidate numbers above. Output only those lines.`;
}

/** A bare score token a model emits as the WHOLE answer for one candidate:
 *  `0.8`, `1`, `.7`, `75%`, `4/5`. Deliberately strict — prose like
 *  `**Analyze the request**` or `Approach via caching` must NOT qualify, so a
 *  truncated chain-of-thought is detected as a parse failure (→ fallback)
 *  rather than silently scored 0.5. */
const SCORE_TOKEN_RE = /^(?:[01](?:\.\d+)?|\.\d+|\d{1,3}\s*%|\d+\s*\/\s*\d+)$/;

/**
 * Parse batched scores into `{ scores, ok }`. `ok=false` signals the response
 * carried no usable per-candidate scores (e.g. a thinking model spent its whole
 * budget on `<think>` and got truncated before emitting any) — the caller then
 * falls back to reliable per-candidate scoring instead of shipping a silent
 * all-0.5 collapse that makes BFS pruning non-discriminating.
 *
 * Accepts two formats, both requiring genuinely numeric score bodies:
 *   1. Indexed `N: SCORE` lines (the prompt's requested format).
 *   2. Every non-empty line is a bare score token (handles `0.8\n0.7\n0.6`
 *      and a single `0.8` broadcast to all candidates).
 */
function parseBatchScoresDetailed(
  text: string,
  count: number,
): { scores: number[]; ok: boolean } {
  const stripped = text.replace(/<think>[\s\S]*?<\/think>/gi, "").trim();
  const source = stripped.length > 0 ? stripped : text.trim();
  const lines = source.split("\n").map((l) => l.trim()).filter((l) => l.length > 0);
  const fail = { scores: Array.from({ length: count }, () => 0.5), ok: false };
  if (lines.length === 0) return fail;

  // (1) Indexed `N: <score-token>` — body must START with a score token, so
  // numbered thinking lists (`1. **Analyze**`) are rejected, not mis-scored.
  const byIndex = new Map<number, number>();
  for (const line of lines) {
    const m = line.match(/^(\d+)\s*[:.\)\-]\s*(.+)$/);
    if (m) {
      const idx = Number(m[1]);
      const body = m[2]!.trim();
      const tok = body.match(/^([01](?:\.\d+)?|\.\d+|\d{1,3}\s*%|\d+\s*\/\s*\d+)\b/);
      if (idx >= 1 && idx <= count && tok) {
        byIndex.set(idx, parseScore(tok[1]!));
      }
    }
  }
  if (byIndex.size > 0) {
    return {
      scores: Array.from({ length: count }, (_, i) => byIndex.get(i + 1) ?? 0.5),
      ok: true,
    };
  }

  // (2) Every line is a bare score token.
  if (lines.every((l) => SCORE_TOKEN_RE.test(l))) {
    if (lines.length === 1) {
      const s = parseScore(lines[0]!);
      return { scores: Array.from({ length: count }, () => s), ok: true };
    }
    return {
      scores: Array.from({ length: count }, (_, i) =>
        lines[i] !== undefined ? parseScore(lines[i]!) : 0.5,
      ),
      ok: true,
    };
  }

  return fail;
}

/** Thin wrapper returning just the score array (the `ok` flag is internal). */
export function parseBatchScores(text: string, count: number): number[] {
  return parseBatchScoresDetailed(text, count).scores;
}

function parseCandidates(text: string, expectedCount: number): string[] {
  const lines = text.split("\n");
  const candidates: string[] = [];
  for (const line of lines) {
    const match = line.match(/^\s*\d+[\.\)]\s+(.+)/);
    if (match) {
      candidates.push(match[1].trim());
    }
  }
  // If parsing failed, split into chunks
  if (candidates.length === 0) {
    return [text.trim()];
  }
  return candidates.slice(0, expectedCount);
}

function getAncestorPath(
  allNodes: ThoughtNode[],
  node: ThoughtNode,
): string[] {
  const path: string[] = [node.content];
  let current: ThoughtNode | undefined = node;

  while (current?.parentId) {
    current = allNodes.find((n) => n.id === current!.parentId);
    if (current) {
      path.unshift(current.content);
    }
  }

  return path;
}

