from __future__ import annotations

from dataclasses import dataclass
import threading
import time
from typing import Callable, Iterable

from crafting import combine_levels
from models import CraftStep, Identity, InventoryItem, MIN_COMBINE_LEVEL, Plan
from rules import RuleBook


class SearchCancelled(Exception):
    """Raised internally when the user cancels a planner search."""


ProgressCallback = Callable[[dict], None]


@dataclass
class _Candidate:
    identity: Identity
    level: int
    consumed: frozenset[int]
    steps: tuple[CraftStep, ...]
    missing: tuple[Identity, ...]
    source: str
    notes: tuple[str, ...] = ()
    craft_depth: int = 0

    def score(self) -> tuple:
        # Prefer plans that use more of the real inventory.  A slightly longer
        # complete plan is more useful than a one-step suggestion requiring two
        # missing items.  Total operations remain the next tie-breaker.
        return (len(self.missing), len(self.steps), len(self.consumed), -self.level)




def _unique_missing(missing: Iterable[Identity]) -> bool:
    """Return False when a plan assumes two copies of the same missing item.

    An owned copy plus one missing copy is valid. Two actually owned copies are
    valid. What we reject is inventing the same absent identity twice anywhere
    in one plan tree.
    """
    seen: set[str] = set()
    for identity in missing:
        key = identity.key()
        if key in seen:
            return False
        seen.add(key)
    return True


def _candidate_signature(candidate: _Candidate) -> tuple:
    step_signature = tuple(
        (step.left.key(), step.right.key(), step.result.key(), step.result_level)
        for step in candidate.steps
    )
    return (
        candidate.identity.key(),
        candidate.level,
        tuple(sorted(candidate.consumed)),
        tuple(sorted(identity.key() for identity in candidate.missing)),
        step_signature,
    )

def _dedupe(candidates: Iterable[_Candidate], limit: int) -> list[_Candidate]:
    best: dict[tuple, _Candidate] = {}
    for candidate in candidates:
        key = (
            candidate.identity.key(),
            candidate.consumed,
            tuple(sorted(x.key() for x in candidate.missing)),
            candidate.level,
        )
        old = best.get(key)
        if old is None or candidate.score() < old.score():
            best[key] = candidate
    return sorted(best.values(), key=lambda x: x.score())[:limit]


def _depth_diverse(candidates: Iterable[_Candidate], limit: int) -> list[_Candidate]:
    """Keep useful plans from every discovered crafting depth.

    The previous planner globally sorted everything by shortest plan.  Once a
    shallow depth produced dozens of valid candidates, deeper inventory-only
    plans could never reach the UI even when the user explicitly selected a
    larger search depth.  This helper deduplicates first, then reserves space
    for every actual crafting layer before filling any spare slots by score.
    """
    limit = max(1, int(limit))
    unique: dict[tuple, _Candidate] = {}
    for candidate in candidates:
        key = _candidate_signature(candidate)
        old = unique.get(key)
        if old is None or candidate.score() < old.score():
            unique[key] = candidate

    groups: dict[int, list[_Candidate]] = {}
    for candidate in unique.values():
        groups.setdefault(max(0, candidate.craft_depth), []).append(candidate)
    for bucket in groups.values():
        bucket.sort(key=lambda value: value.score())

    depths = sorted(groups)
    selected: list[_Candidate] = []
    # Round-robin is intentionally used instead of one global slice.  It means
    # 50 one-layer plans cannot crowd every two-layer plan out of the result.
    while len(selected) < limit:
        added = False
        for depth in depths:
            bucket = groups[depth]
            if bucket:
                selected.append(bucket.pop(0))
                added = True
                if len(selected) >= limit:
                    break
        if not added:
            break
    return sorted(selected, key=lambda value: (value.craft_depth, value.score()))


def reachable_identity_closure(
    items: list[InventoryItem],
    rules: RuleBook,
    rounds: int = 8,
    cap: int = 8000,
    interrupt: Callable[[], None] | None = None,
    progress: ProgressCallback | None = None,
) -> set[str]:
    identities = {item.identity.key(): item.identity for item in items if item.level >= MIN_COMBINE_LEVEL}
    frontier = list(identities.values())
    checks = 0
    for round_index in range(rounds):
        if progress is not None:
            progress({
                "kind": "activity",
                "phase": "closure",
                "message": (
                    f"Rozszerzanie grafu osiągalności — runda {round_index + 1}/{rounds}, "
                    f"znanych tożsamości: {len(identities):,}"
                ),
                "checks": checks,
                "identities": len(identities),
            })
        current = list(identities.values())
        new: list[Identity] = []
        for left in frontier:
            for right in current:
                checks += 1
                if interrupt is not None and checks % 256 == 0:
                    interrupt()
                if progress is not None and checks % 4096 == 0:
                    progress({
                        "kind": "activity",
                        "phase": "closure",
                        "message": (
                            f"Graf osiągalności: sprawdzono {checks:,} połączeń, "
                            f"znanych tożsamości: {len(identities):,}"
                        ),
                        "checks": checks,
                        "identities": len(identities),
                    })
                result, _notes = rules.combine_identity(left, right)
                if result and result.key() not in identities:
                    identities[result.key()] = result
                    new.append(result)
                    if len(identities) >= cap:
                        if progress is not None:
                            progress({
                                "kind": "log",
                                "phase": "closure",
                                "message": f"Osiągnięto limit grafu: {cap:,} tożsamości.",
                            })
                        return set(identities)
        if not new:
            break
        frontier = new
    return set(identities)


class Planner:
    def __init__(self, rules: RuleBook):
        self.rules = rules
        self.last_status = "idle"
        self.last_elapsed = 0.0
        self.last_timed_out = False
        self.last_cancelled = False
        self.last_depth = 0
        self.last_timeout_seconds = 0.0
        self.last_stats: dict[str, int] = {}
        self._cancel_event = threading.Event()

    def request_cancel(self) -> None:
        self._cancel_event.set()

    def find_plans(
        self,
        target: Identity,
        items: list[InventoryItem],
        max_depth: int = 5,
        top_k: int = 5,
        timeout_seconds: float | None = 10.0,
        allow_missing: bool = False,
        minimum_level: int = 0,
        progress_callback: ProgressCallback | None = None,
        stop_at_first_success: bool = True,
    ) -> list[Plan]:
        started = time.monotonic()
        # The search is intentionally capped at five crafting layers. In practice,
        # larger values explode combinatorially and do not produce useful results.
        max_depth = max(1, min(5, int(max_depth)))

        if timeout_seconds is None:
            normalized_timeout: float | None = None
        else:
            try:
                parsed_timeout = float(timeout_seconds)
            except (TypeError, ValueError):
                parsed_timeout = 30.0
            normalized_timeout = None if parsed_timeout <= 0 else max(1.0, parsed_timeout)

        deadline = None if normalized_timeout is None else started + normalized_timeout
        self._cancel_event.clear()
        self.last_status = "searching"
        self.last_elapsed = 0.0
        self.last_timed_out = False
        self.last_cancelled = False
        self.last_depth = max_depth
        self.last_timeout_seconds = normalized_timeout or 0.0
        self.last_stats = {
            "closure_checks": 0,
            "direct_pair_checks": 0,
            "direct_results": 0,
            "nodes": 0,
            "cache_hits": 0,
            "recipes": 0,
            "candidate_merges": 0,
            "root_candidates": 0,
        }

        last_activity_emit = 0.0
        last_trace_emit = 0.0

        def emit(kind: str, message: str = "", force: bool = False, **payload) -> None:
            nonlocal last_activity_emit, last_trace_emit
            if progress_callback is None:
                return
            now = time.monotonic()
            if kind == "activity":
                if not force and now - last_activity_emit < 0.10:
                    return
                last_activity_emit = now
            elif kind == "trace":
                if not force and now - last_trace_emit < 0.18:
                    return
                last_trace_emit = now
            event = {
                "kind": kind,
                "message": message,
                "elapsed": now - started,
                "depth": max_depth,
                **payload,
            }
            try:
                progress_callback(event)
            except Exception:
                # A broken UI callback must never break the planner itself.
                pass

        def timeout_label(seconds: float | None) -> str:
            if seconds is None:
                return "bez limitu czasu"
            if seconds >= 60 and seconds % 60 == 0:
                return f"limit {seconds / 60:g} min"
            return f"limit {seconds:g} s"

        emit(
            "start",
            f"Start wyszukiwania: {self.rules.identity_display(target)} | głębokość do {max_depth} | "
            + timeout_label(normalized_timeout)
            + (" | stop po pierwszym trafieniu" if stop_at_first_success else " | pełne przeszukanie głębokości"),
            force=True,
            percent=0,
            mode="determinate",
        )

        def check_interrupted() -> None:
            if self._cancel_event.is_set():
                raise SearchCancelled
            if deadline is not None and time.monotonic() > deadline:
                raise TimeoutError

        published_candidates: dict[tuple, _Candidate] = {}

        def candidate_to_plan(candidate: _Candidate) -> Plan:
            return Plan(
                target=target,
                steps=list(candidate.steps),
                consumed_item_ids=[items[i].db_id or i for i in sorted(candidate.consumed)],
                missing=list(candidate.missing),
                result_level=candidate.level,
                notes=list(dict.fromkeys(candidate.notes)),
                craft_depth=candidate.craft_depth,
            )

        def publish_candidate(candidate: _Candidate, *, found_depth: int) -> None:
            if candidate.level < minimum_level or not _unique_missing(candidate.missing):
                return
            signature = _candidate_signature(candidate)
            old_candidate = published_candidates.get(signature)
            if old_candidate is not None and old_candidate.score() <= candidate.score():
                return
            published_candidates[signature] = candidate
            if stop_at_first_success:
                ranked = sorted(published_candidates.values(), key=lambda value: value.score())
                keep_limit = max(top_k * 4, 40)
                keep = {_candidate_signature(value) for value in ranked[:keep_limit]}
            else:
                # Keep a healthy slice from every actual plan depth.  Without
                # this, dozens of depth-1 results could delete all depth-2/3
                # candidates before the UI ever receives them.
                keep_limit = max(top_k * max_depth * 2, 100)
                keep = {
                    _candidate_signature(value)
                    for value in _depth_diverse(published_candidates.values(), keep_limit)
                }
            if len(published_candidates) > len(keep):
                for key in list(published_candidates):
                    if key not in keep:
                        published_candidates.pop(key, None)
            plan = candidate_to_plan(candidate)
            actual_depth = candidate.craft_depth or found_depth
            emit(
                "plan",
                f"Plan na żywo: {plan.step_count} kroków, warstw: {actual_depth}, braków: {plan.missing_count}.",
                force=True,
                phase="search",
                mode="indeterminate",
                plan=plan,
                found_depth=actual_depth,
                plans_found=len(published_candidates),
                **self.last_stats,
            )

        # Only items from the target category and the matching legendary pool can
        # ever participate. Restricting the search here avoids millions of pointless
        # cross-category checks in the old forward-closure stage.
        eligible_indices = tuple(
            index
            for index, item in enumerate(items)
            if item.identity.category == target.category
            and item.identity.legendary == target.legendary
        )
        relevant_items = [items[index] for index in eligible_indices]
        cache: dict[tuple, list[_Candidate]] = {}
        total_pair_slots = max(1, len(eligible_indices) * (len(eligible_indices) - 1) // 2)
        owned_identity_keys = {item.identity.key() for item in relevant_items if item.level >= MIN_COMBINE_LEVEL}
        owned_components: dict[tuple[str, bool], dict[str, set[str]]] = {}
        for item in relevant_items:
            if item.level < MIN_COMBINE_LEVEL:
                continue
            key = (item.identity.category, item.identity.legendary)
            bucket = owned_components.setdefault(key, {"base": set(), "prefix": set(), "suffix": set()})
            bucket["base"].add(item.identity.base)
            bucket["prefix"].add(item.identity.prefix)
            bucket["suffix"].add(item.identity.suffix)

        def identity_affinity(identity: Identity, direct_keys: set[str]) -> int:
            score = 120 if identity.key() in direct_keys else (80 if identity.key() in owned_identity_keys else 0)
            bucket = owned_components.get((identity.category, identity.legendary), {})
            score += 14 if identity.base in bucket.get("base", set()) else 0
            score += 6 if identity.prefix in bucket.get("prefix", set()) else 0
            score += 6 if identity.suffix in bucket.get("suffix", set()) else 0
            return score

        # Fast path: if the exact target already exists at the requested level,
        # return immediately instead of building any search index.
        for index in eligible_indices:
            item = items[index]
            if item.identity == target and item.level >= minimum_level:
                self.last_elapsed = time.monotonic() - started
                self.last_status = "found"
                plan = Plan(
                    target=target,
                    steps=[],
                    consumed_item_ids=[item.db_id or index],
                    missing=[],
                    result_level=item.level,
                    notes=["Cel już znajduje się w ekwipunku."],
                    craft_depth=0,
                )
                emit(
                    "plan",
                    "Plan na żywo: cel już znajduje się w ekwipunku.",
                    force=True,
                    phase="complete",
                    percent=100,
                    mode="determinate",
                    plan=plan,
                    found_depth=0,
                    plans_found=1,
                )
                emit(
                    "log",
                    f"Cel już znajduje się w ekwipunku: {self.rules.identity_display(target)}.",
                    force=True,
                    phase="complete",
                    percent=100,
                    mode="determinate",
                )
                emit(
                    "complete",
                    f"Koniec: cel istnieje w ekwipunku, czas={self.last_elapsed:.2f} s.",
                    force=True,
                    phase="complete",
                    percent=100,
                    mode="determinate",
                    status="found",
                    plans=1,
                    **self.last_stats,
                )
                return [plan]

        try:
            if not allow_missing:
                emit(
                    "phase",
                    "Etap 1/3: buduję graf tożsamości osiągalnych z aktualnego ekwipunku…",
                    force=True,
                    phase="closure",
                    percent=5,
                    mode="determinate",
                )

                def closure_progress(event: dict) -> None:
                    self.last_stats["closure_checks"] = int(event.get("checks", self.last_stats["closure_checks"]))
                    emit(
                        event.get("kind", "activity"),
                        event.get("message", ""),
                        phase="closure",
                        percent=15,
                        mode="determinate",
                        checks=self.last_stats["closure_checks"],
                        identities=event.get("identities", 0),
                    )

                reachable = reachable_identity_closure(
                    relevant_items,
                    self.rules,
                    rounds=max_depth,
                    cap=6000,
                    interrupt=check_interrupted,
                    progress=closure_progress,
                )
                emit(
                    "log",
                    f"Graf osiągalności gotowy: {len(reachable):,} tożsamości.",
                    force=True,
                    phase="closure",
                    percent=22,
                    mode="determinate",
                )
            else:
                reachable = None
                emit(
                    "phase",
                    "Etap 1/3 pominięty: tryb „Plan z brakami” nie ogranicza grafu do posiadanych przedmiotów.",
                    force=True,
                    phase="closure",
                    percent=22,
                    mode="determinate",
                )

            # Build the physical-inventory direct-pair index once. The old planner
            # rescanned every O(n²) pair for every recursive subproblem, which made
            # deeper searches explode even on medium inventories.
            emit(
                "phase",
                f"Etap 2/3: indeksuję fizyczne pary ekwipunku ({total_pair_slots:,} możliwych par)…",
                force=True,
                phase="direct-index",
                percent=25,
                mode="determinate",
            )
            direct_by_result: dict[str, list[tuple[int, int, int, tuple[str, ...]]]] = {}
            pair_checks = 0
            direct_results = 0
            report_every = max(128, total_pair_slots // 100)
            for left_position, left_idx in enumerate(eligible_indices):
                check_interrupted()
                left_item = items[left_idx]
                if left_item.level < MIN_COMBINE_LEVEL:
                    continue
                for right_idx in eligible_indices[left_position + 1:]:
                    pair_checks += 1
                    self.last_stats["direct_pair_checks"] = pair_checks
                    if pair_checks % 256 == 0:
                        check_interrupted()
                    if pair_checks % report_every == 0:
                        percent = 25 + min(20, int(20 * pair_checks / total_pair_slots))
                        emit(
                            "activity",
                            f"Indeks par: {pair_checks:,}/{total_pair_slots:,}; poprawnych wyników: {direct_results:,}",
                            phase="direct-index",
                            percent=percent,
                            mode="determinate",
                            current=pair_checks,
                            total=total_pair_slots,
                            direct_results=direct_results,
                        )
                    right_item = items[right_idx]
                    if right_item.level < MIN_COMBINE_LEVEL:
                        continue
                    direct_result, direct_notes = self.rules.combine_identity(left_item.identity, right_item.identity)
                    if direct_result is None:
                        continue
                    result_level = combine_levels(
                        left_item.identity,
                        left_item.level,
                        right_item.identity,
                        right_item.level,
                    )
                    direct_by_result.setdefault(direct_result.key(), []).append(
                        (left_idx, right_idx, result_level, tuple(direct_notes))
                    )
                    direct_results += 1
                    self.last_stats["direct_results"] = direct_results

            emit(
                "log",
                f"Indeks par gotowy: {pair_checks:,} sprawdzeń, {direct_results:,} poprawnych połączeń, "
                f"{len(direct_by_result):,} różnych wyników.",
                force=True,
                phase="direct-index",
                percent=45,
                mode="determinate",
            )
            emit(
                "phase",
                "Etap 3/3: przeszukuję graf receptur i składników…",
                force=True,
                phase="search",
                percent=45,
                mode="indeterminate",
            )

            search_stats = self.last_stats
            current_depth = 0

            def report_search_activity(wanted: Identity, depth: int, message: str = "") -> None:
                base_message = (
                    f"Węzły: {search_stats['nodes']:,} | cache: {search_stats['cache_hits']:,} | "
                    f"receptury: {search_stats['recipes']:,} | łączenia kandydatów: {search_stats['candidate_merges']:,}"
                )
                if message:
                    base_message += f" | {message}"
                emit(
                    "activity",
                    base_message,
                    phase="search",
                    mode="indeterminate",
                    wanted=self.rules.identity_display(wanted),
                    search_depth=depth,
                    **search_stats,
                )

            def solve(
                wanted: Identity,
                available: frozenset[int],
                depth: int,
                path: frozenset[str],
                root: bool = False,
            ) -> list[_Candidate]:
                check_interrupted()
                search_stats["nodes"] += 1
                if search_stats["nodes"] % 64 == 0:
                    report_search_activity(wanted, depth)

                cache_key = (wanted.key(), tuple(sorted(available)), depth, allow_missing, root)
                if cache_key in cache:
                    search_stats["cache_hits"] += 1
                    return cache[cache_key]

                candidates: list[_Candidate] = []
                for idx in available:
                    item = items[idx]
                    if item.identity == wanted:
                        if root or item.level >= MIN_COMBINE_LEVEL:
                            candidates.append(
                                _Candidate(wanted, item.level, frozenset({idx}), (), (), f"item:{idx}")
                            )
                            if root:
                                emit(
                                    "log",
                                    f"Cel już istnieje w ekwipunku: {self.rules.identity_display(wanted)}.",
                                    force=True,
                                    phase="search",
                                    mode="indeterminate",
                                )

                # In missing-material mode a missing item is always a valid leaf.
                # Keeping this candidate from the start lets the planner produce an
                # actionable shallow plan quickly, while deeper branches compete only
                # if they reduce the number of missing leaves.
                if allow_missing and not root:
                    candidates.append(
                        _Candidate(
                            wanted,
                            MIN_COMBINE_LEVEL,
                            frozenset(),
                            (),
                            (wanted,),
                            "missing",
                            ("Brakujący przedmiot przyjęty na minimalnym poziomie Zwykły +1",),
                        )
                    )

                # Fast path: use the precomputed direct-pair index and only check
                # whether both physical copies are still available in this branch.
                if depth > 0:
                    for left_idx, right_idx, result_level, direct_notes in direct_by_result.get(wanted.key(), []):
                        check_interrupted()
                        if left_idx not in available or right_idx not in available:
                            continue
                        left_item = items[left_idx]
                        right_item = items[right_idx]
                        step = CraftStep(
                            left=left_item.identity,
                            right=right_item.identity,
                            result=wanted,
                            left_source=f"item:{left_idx}",
                            right_source=f"item:{right_idx}",
                            result_level=result_level,
                        )
                        direct_candidate = _Candidate(
                            wanted,
                            result_level,
                            frozenset({left_idx, right_idx}),
                            (step,),
                            (),
                            "step:0",
                            direct_notes,
                            craft_depth=1,
                        )
                        candidates.append(direct_candidate)
                        if root:
                            publish_candidate(direct_candidate, found_depth=current_depth)
                            emit(
                                "log",
                                "Bezpośredni craft: "
                                f"{self.rules.identity_display(left_item.identity)} + "
                                f"{self.rules.identity_display(right_item.identity)} → "
                                f"{self.rules.identity_display(wanted)}",
                                force=True,
                                phase="search",
                                mode="indeterminate",
                            )
                    candidates = _dedupe(candidates, top_k * 5)

                # Depth is defined as the number of crafting operations available
                # on the longest branch. Therefore depth=1 must allow one split of
                # the target into two leaf ingredients.
                if depth > 0 and wanted.key() not in path:
                    recipes = self.rules.reverse_recipes(wanted, reachable=reachable, limit=1200)
                    search_stats["recipes"] += len(recipes)
                    # Prefer recipes whose ingredients already occur directly in inventory.
                    direct_keys = {
                        items[i].identity.key()
                        for i in available
                        if items[i].level >= MIN_COMBINE_LEVEL
                    }
                    recipes.sort(
                        key=lambda pair: -(
                            identity_affinity(pair[0], direct_keys)
                            + identity_affinity(pair[1], direct_keys)
                        )
                    )
                    recipe_limit = (90 if root else 45) if allow_missing else 180
                    recipe_count = min(recipe_limit, len(recipes))
                    if root:
                        emit(
                            "log",
                            f"Dla celu znaleziono {len(recipes):,} wariantów rozkładu; analizuję najlepsze {recipe_count:,}.",
                            force=True,
                            phase="search",
                            mode="indeterminate",
                        )
                    for recipe_index, (left_identity, right_identity) in enumerate(recipes[:recipe_limit], 1):
                        check_interrupted()
                        if recipe_index <= 3 or recipe_index % 25 == 0:
                            emit(
                                "trace",
                                f"[głębokość {depth}] {self.rules.identity_display(wanted)} ← "
                                f"{self.rules.identity_display(left_identity)} + "
                                f"{self.rules.identity_display(right_identity)} "
                                f"({recipe_index}/{recipe_count})",
                                phase="search",
                                mode="indeterminate",
                                recipe_index=recipe_index,
                                recipe_total=recipe_count,
                                wanted=self.rules.identity_display(wanted),
                            )
                        left_candidates = solve(
                            left_identity,
                            available,
                            depth - 1,
                            path | {wanted.key()},
                            False,
                        )
                        for left in left_candidates[: top_k * 2]:
                            remaining = available - left.consumed
                            right_candidates = solve(
                                right_identity,
                                remaining,
                                depth - 1,
                                path | {wanted.key()},
                                False,
                            )
                            for right in right_candidates[: top_k * 2]:
                                check_interrupted()

                                # Do not let missing-material mode manufacture a
                                # meaningless self-upgrade plan from two copies of
                                # the target that are both merely assumed missing.
                                #
                                # Example to reject:
                                #   missing X + missing X -> X (+1)
                                #
                                # The identical-item recipe remains valid when at
                                # least one physical copy is actually owned, because
                                # then the plan is actionable: owned X + missing X.
                                if (
                                    allow_missing
                                    and left_identity == wanted
                                    and right_identity == wanted
                                    and not left.consumed
                                    and not right.consumed
                                    and not left.steps
                                    and not right.steps
                                    and left.missing
                                    and right.missing
                                ):
                                    if root:
                                        emit(
                                            "trace",
                                            "Pomijam pustą pętlę: dwa nieposiadane egzemplarze celu "
                                            "nie mogą być jedynym planem jego wytworzenia.",
                                            phase="search",
                                            mode="indeterminate",
                                            wanted=self.rules.identity_display(wanted),
                                        )
                                    continue

                                search_stats["candidate_merges"] += 1
                                if search_stats["candidate_merges"] % 128 == 0:
                                    report_search_activity(wanted, depth)
                                if left.level < MIN_COMBINE_LEVEL or right.level < MIN_COMBINE_LEVEL:
                                    continue
                                actual_result, notes = self.rules.combine_identity(
                                    left.identity,
                                    right.identity,
                                )
                                if actual_result != wanted:
                                    continue
                                result_level = combine_levels(
                                    left.identity,
                                    left.level,
                                    right.identity,
                                    right.level,
                                )
                                step = CraftStep(
                                    left=left.identity,
                                    right=right.identity,
                                    result=wanted,
                                    left_source=left.source,
                                    right_source=right.source,
                                    result_level=result_level,
                                )
                                all_steps = left.steps + right.steps + (step,)
                                combined_missing = left.missing + right.missing
                                # Never propose a plan that assumes two copies of the
                                # same absent item. Owned duplicates and an owned copy
                                # plus one missing copy remain valid.
                                if not _unique_missing(combined_missing):
                                    if root:
                                        emit(
                                            "trace",
                                            "Pomijam plan wymagający dwóch identycznych brakujących przedmiotów.",
                                            phase="search",
                                            mode="indeterminate",
                                            wanted=self.rules.identity_display(wanted),
                                        )
                                    continue
                                merged_candidate = _Candidate(
                                    wanted,
                                    result_level,
                                    left.consumed | right.consumed,
                                    all_steps,
                                    combined_missing,
                                    f"step:{len(all_steps) - 1}",
                                    left.notes + right.notes + tuple(notes),
                                    craft_depth=1 + max(left.craft_depth, right.craft_depth),
                                )
                                candidates.append(merged_candidate)
                                if root:
                                    publish_candidate(merged_candidate, found_depth=current_depth)
                                    search_stats["root_candidates"] += 1
                                    root_count = search_stats["root_candidates"]
                                    if root_count <= 3 or root_count % 10 == 0:
                                        emit(
                                            "log",
                                            f"Plan kandydujący #{root_count}: {len(all_steps)} kroków, "
                                            f"braków: {len(left.missing) + len(right.missing)}.",
                                            force=True,
                                            phase="search",
                                            mode="indeterminate",
                                        )
                        candidates = _dedupe(candidates, top_k * 5)

                # A safety fallback for future rule changes. Normally missing
                # leaves were already added before recursion above.
                if allow_missing and not root and not candidates:
                    candidates.append(
                        _Candidate(
                            wanted,
                            MIN_COMBINE_LEVEL,
                            frozenset(),
                            (),
                            (wanted,),
                            "missing",
                            ("Brakujący przedmiot przyjęty na minimalnym poziomie Zwykły +1",),
                        )
                    )

                candidates = [candidate for candidate in candidates if not root or candidate.level >= minimum_level]
                result = _dedupe(candidates, top_k * 4)
                cache[cache_key] = result
                return result

            # Iterative deepening still publishes shallow plans immediately.  The
            # caller can either preserve the old fast behaviour (stop after the
            # first successful layer) or explicitly search through every selected
            # depth so that intermediate inventory crafts are not skipped.
            raw: list[_Candidate] = []
            raw_pool: list[_Candidate] = []
            available_root = frozenset(eligible_indices)
            for depth_limit in range(1, max_depth + 1):
                current_depth = depth_limit
                emit(
                    "phase",
                    f"Przeszukuję głębokość {depth_limit}/{max_depth}…",
                    force=True,
                    phase="search",
                    mode="indeterminate",
                    search_depth=depth_limit,
                    plans_found=len(published_candidates),
                )
                depth_candidates = solve(target, available_root, depth_limit, frozenset(), True)
                depth_candidates = [
                    candidate
                    for candidate in depth_candidates
                    if candidate.level >= minimum_level and _unique_missing(candidate.missing)
                ]
                for candidate in depth_candidates:
                    publish_candidate(candidate, found_depth=depth_limit)
                if depth_candidates:
                    raw_pool.extend(depth_candidates)
                    raw_pool.extend(published_candidates.values())
                    if stop_at_first_success:
                        raw = _dedupe(raw_pool, max(top_k * 4, 40))
                        emit(
                            "log",
                            f"Znaleziono plany przy najmniejszej skutecznej głębokości {depth_limit}; "
                            "tryb szybkiego zatrzymania nie rozwija dłuższych tras.",
                            force=True,
                            phase="search",
                            mode="indeterminate",
                            plans_found=len(raw),
                        )
                        break
                    raw = _depth_diverse(raw_pool, max(top_k * max_depth * 2, 100))
                    emit(
                        "log",
                        f"Głębokość {depth_limit} zakończona: zachowano {len(raw)} różnych planów; "
                        f"kontynuuję do ustawionej głębokości {max_depth}.",
                        force=True,
                        phase="search",
                        mode="indeterminate",
                        plans_found=len(raw),
                    )
            if not raw:
                if stop_at_first_success:
                    raw = _dedupe(published_candidates.values(), max(top_k * 4, 40))
                else:
                    raw = _depth_diverse(
                        published_candidates.values(),
                        max(top_k * max_depth * 2, 100),
                    )
        except TimeoutError:
            self.last_timed_out = True
            emit(
                "log",
                "Osiągnięto limit czasu — zatrzymuję wyszukiwanie i zachowuję plany znalezione dotychczas.",
                force=True,
                phase="search",
                mode="determinate",
                percent=100,
                plans_found=len(published_candidates),
            )
            if stop_at_first_success:
                raw = _dedupe(published_candidates.values(), max(top_k * 4, 40))
            else:
                raw = _depth_diverse(
                    published_candidates.values(),
                    max(top_k * max_depth * 2, 100),
                )
        except SearchCancelled:
            self.last_cancelled = True
            emit(
                "log",
                "Wyszukiwanie anulowane — zachowuję plany znalezione dotychczas.",
                force=True,
                phase="search",
                mode="determinate",
                percent=100,
                plans_found=len(published_candidates),
            )
            if stop_at_first_success:
                raw = _dedupe(published_candidates.values(), max(top_k * 4, 40))
            else:
                raw = _depth_diverse(
                    published_candidates.values(),
                    max(top_k * max_depth * 2, 100),
                )

        selected_candidates = (
            _dedupe(raw, top_k)
            if stop_at_first_success
            else _depth_diverse(raw, top_k)
        )
        plans: list[Plan] = [candidate_to_plan(candidate) for candidate in selected_candidates]
        self.last_elapsed = time.monotonic() - started
        if plans:
            self.last_status = "found"
        elif self.last_cancelled:
            self.last_status = "cancelled"
        elif self.last_timed_out:
            self.last_status = "timeout"
        else:
            self.last_status = "exhausted"

        emit(
            "complete",
            f"Koniec: status={self.last_status}, planów={len(plans)}, czas={self.last_elapsed:.1f} s, "
            f"węzłów={self.last_stats['nodes']:,}, receptur={self.last_stats['recipes']:,}.",
            force=True,
            phase="complete",
            percent=100,
            mode="determinate",
            status=self.last_status,
            plans=len(plans),
            **self.last_stats,
        )
        return plans
