# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-must-an-instance-detect-deadlock-at-the-delegation-layer-before-workers-starve.md
# Remnant Warrant:    https://corpusfetch.com/c/how-must-an-instance-detect-deadlock-at-the-delegation-layer-before-workers-starve.warrant.json
# Markdown SHA-256:   6ddcb0c597b5fb99382c42f19b88fe3af7a475006d3a167e4ad70965a7091b1c
# Code AST SHA-256:   09a25cf7be356df6fdc8a7ba514c68c90b57940e997db459b5345ac3bbef2229
# Verified Classes:   DeadlockVerdict, WorkerState, DelegationPolicy, DelegationManifest, DelegationDeadlockGuard
# Defensive Guards:   1 fail-closed invariants (zero external deps)

from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class DeadlockVerdict(Enum):
    PROGRESSING = auto()
    DEADLOCK_DETECTED = auto()
    LIVELOCK_DETECTED = auto()
    STARVATION_RISK = auto()

@dataclass(frozen=True)
class WorkerState:
    worker_id: str
    is_executing: bool
    waiting_on: frozenset[str]
    redelegation_count: int

@dataclass(frozen=True)
class DelegationPolicy:
    max_redelegation_count: int
    max_wait_depth: int

@dataclass(frozen=True)
class DelegationManifest:
    verdict: DeadlockVerdict
    cycle_signature: tuple[str, ...]
    directive: str
    manifest_digest: str

class DelegationDeadlockGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_workers(
        cls, workers: tuple[WorkerState, ...], policy: DelegationPolicy
    ) -> DelegationManifest:
        
        if not workers:
            raise ValueError("Worker set cannot be empty.")

        # Gate 1: Livelock check
        for worker in workers:
            if worker.redelegation_count > policy.max_redelegation_count:
                return DelegationManifest(
                    verdict=DeadlockVerdict.LIVELOCK_DETECTED,
                    cycle_signature=(worker.worker_id,),
                    directive=f"HALT: Worker {worker.worker_id} exceeded {policy.max_redelegation_count} re-delegations.",
                    manifest_digest=cls._hash(f"LIVELOCK:{worker.worker_id}")
                )

        # Gate 2: Progress check
        if any(w.is_executing for w in workers):
            return DelegationManifest(
                verdict=DeadlockVerdict.PROGRESSING,
                cycle_signature=tuple(),
                directive="PROCEED: At least one worker is executing. System is progressing.",
                manifest_digest=cls._hash("PROGRESSING")
            )

        # Gate 3: Cycle detection (DFS on wait graph)
        wait_map = {w.worker_id: list(w.waiting_on) for w in workers}
        
        def find_cycle(node: str, path: list[str], visited: set[str]) -> list[str] | None:
            if node in path:
                return path[path.index(node):] + [node]
            if node in visited:
                return None
            visited.add(node)
            path.append(node)
            for neighbor in wait_map.get(node, []):
                cycle = find_cycle(neighbor, path, visited)
                if cycle:
                    return cycle
            path.pop()
            return None

        visited: set[str] = set()
        for worker in workers:
            cycle = find_cycle(worker.worker_id, [], visited)
            if cycle:
                return DelegationManifest(
                    verdict=DeadlockVerdict.DEADLOCK_DETECTED,
                    cycle_signature=tuple(cycle),
                    directive=f"HALT: Deadlock cycle detected: {' -> '.join(cycle)}. Break cycle by aborting lowest-priority edge.",
                    manifest_digest=cls._hash(f"CYCLE:{'->'.join(cycle)}")
                )

        # Gate 4: Starvation risk
        return DelegationManifest(
            verdict=DeadlockVerdict.STARVATION_RISK,
            cycle_signature=tuple(),
            directive="WARN: All workers waiting but no cycle detected. Likely waiting on external dependency.",
            manifest_digest=cls._hash("STARVATION")
        )