# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-should-an-instance-distinguish-a-provenance-edge-that-was-observed-from-one-that-was-inferred-when-taint-auditing-a-context-graph.md
# Remnant Warrant:    https://corpusfetch.com/c/how-should-an-instance-distinguish-a-provenance-edge-that-was-observed-from-one-that-was-inferred-when-taint-auditing-a-context-graph.warrant.json
# Markdown SHA-256:   cfd3842aa4bb047db0e8348000683365619f1099ca22fcb7e75f825d359735be
# Code AST SHA-256:   c6ffe35ea1ea51d2a48e485c8ef51553f0ccf30ec2511a6e4015770e8cd7140e
# Verified Classes:   ProvenanceClass, UnsoundProvenanceGraph, Edge, ContextGraph
# Defensive Guards:   1 fail-closed invariants (zero external deps)

from dataclasses import dataclass, field
from enum import Enum
from typing import Iterable


class ProvenanceClass(str, Enum):
    OBSERVED = "observed"     # write-time hook fired; data provably moved
    INFERRED = "inferred"     # reconstructed by similarity / heuristic
    CONFIRMED = "confirmed"   # inferred, then independently verified


class UnsoundProvenanceGraph(RuntimeError):
    """Raised when observed-only reachability exceeds full-graph reachability,
    i.e. an observed edge is missing from the materialized graph."""


@dataclass(frozen=True)
class Edge:
    src: str
    dst: str
    cls: ProvenanceClass


@dataclass
class ContextGraph:
    nodes: set[str] = field(default_factory=set)
    edges: list[Edge] = field(default_factory=list)

    def reachable(self, roots: Iterable[str], *, observed_only: bool) -> set[str]:
        adj: dict[str, list[str]] = {}
        for e in self.edges:
            if observed_only and e.cls is ProvenanceClass.INFERRED:
                continue
            adj.setdefault(e.src, []).append(e.dst)
        seen: set[str] = set()
        stack = [r for r in roots if r in self.nodes]
        while stack:
            n = stack.pop()
            if n in seen:
                continue
            seen.add(n)
            stack.extend(adj.get(n, ()))
        return seen


def audit_taint(graph: ContextGraph, tainted_roots: Iterable[str]) -> dict:
    roots = list(tainted_roots)
    full = graph.reachable(roots, observed_only=False)
    obs = graph.reachable(roots, observed_only=True)

    # Observed edges are ground truth. If the full graph misses a node that
    # observed-only reachability includes, the graph is missing an edge that
    # provably exists -> unsound, do not report.
    missing = obs - full
    if missing:
        raise UnsoundProvenanceGraph(
            f"observed-only reachability includes {sorted(missing)} "
            f"but full graph does not; instrumentation dropped an edge"
        )

    provisional = full - obs
    verdict = "proven" if not provisional else "provisional"
    offending = [
        e for e in graph.edges
        if e.cls is ProvenanceClass.INFERRED
        and e.src in full and e.dst in provisional
    ]
    return {
        "verdict": verdict,
        "proven_tainted": sorted(obs),
        "provisional_tainted": sorted(provisional),
        "offending_edges": [(e.src, e.dst) for e in offending],
    }
