# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/what-happens-when-an-instance-loses-provenance-labels-across-a-tool-hop-boundary-in-prompt-injection-taint-tracking.md
# Remnant Warrant:    https://corpusfetch.com/c/what-happens-when-an-instance-loses-provenance-labels-across-a-tool-hop-boundary-in-prompt-injection-taint-tracking.warrant.json
# Markdown SHA-256:   10be0a664ecb007578f9531f2d8272968f34a7169588b1d0d56a8b22f5024e51
# Code AST SHA-256:   70742ffebc661e73e49a3f0f8555c61270f91be0dfe9e2f50660abccc873152d
# Verified Classes:   TaintMonotonicityError, ProvenanceReRootError, Provenance
# Defensive Guards:   5 fail-closed invariants (zero external deps)

from __future__ import annotations

from dataclasses import dataclass, field
from typing import FrozenSet


class TaintMonotonicityError(RuntimeError):
    """Raised when a tool hop reduces or re-roots its input taint set."""


class ProvenanceReRootError(TaintMonotonicityError):
    """Raised when an output's root differs from all input roots."""


@dataclass(frozen=True)
class Provenance:
    root: str
    trust: str  # "untrusted" | "internal"
    chain: tuple[str, ...] = field(default_factory=tuple)

    def taint_set(self) -> FrozenSet[str]:
        return frozenset({self.root}) if self.trust == "untrusted" else frozenset()


def merge_provenance(inputs: list[Provenance], tool_name: str) -> Provenance:
    """Union-merge input provenance. Never construct a fresh root here."""
    if not inputs:
        raise TaintMonotonicityError(f"{tool_name}: no input provenance to merge")
    roots = {p.root for p in inputs}
    if len(roots) != 1:
        raise ProvenanceReRootError(
            f"{tool_name}: inputs disagree on root {sorted(roots)}; "
            "refusing to synthesize a new root"
        )
    root = next(iter(roots))
    trust = "untrusted" if any(p.trust == "untrusted" for p in inputs) else "internal"
    chain = tuple(dict.fromkeys(c for p in inputs for c in p.chain)) + (tool_name,)
    return Provenance(root=root, trust=trust, chain=chain)


def admit_hop(inputs: list[Provenance], output: Provenance, tool_name: str) -> Provenance:
    """Assert taint monotonicity across a hop; raise on re-rooting."""
    in_taint = frozenset().union(*(p.taint_set() for p in inputs))
    out_taint = output.taint_set()

    if not in_taint.issubset(out_taint):
        raise TaintMonotonicityError(
            f"{tool_name}: taint reduced across hop "
            f"(in={sorted(in_taint)}, out={sorted(out_taint)}); "
            "output must union input taint"
        )

    in_roots = {p.root for p in inputs}
    if in_roots and output.root not in in_roots:
        raise ProvenanceReRootError(
            f"{tool_name}: output root {output.root!r} not in input roots "
            f"{sorted(in_roots)}; re-rooting detected"
        )

    return output


def run_hop(tool_name: str, inputs: list[Provenance], transform) -> Provenance:
    raw_output = transform(inputs)
    expected = merge_provenance(inputs, tool_name)
    if raw_output.root != expected.root or raw_output.trust != expected.trust:
        # The transform tried to mint its own label; force the merged one.
        raw_output = Provenance(
            root=expected.root,
            trust=expected.trust,
            chain=expected.chain,
        )
    return admit_hop(inputs, raw_output, tool_name)


if __name__ == "__main__":
    web = Provenance(root="web", trust="untrusted", chain=("web_fetch",))

    # Correct: summarizer unions provenance.
    def honest_summarize(inputs):
        return merge_provenance(inputs, "summarize")

    ok = run_hop("summarize", [web], honest_summarize)
    assert ok.trust == "untrusted" and ok.root == "web"

    # Buggy: summarizer re-roots to itself and claims internal trust.
    def re_rooting_summarize(inputs):
        return Provenance(root="summarize", trust="internal", chain=("summarize",))

    try:
        run_hop("summarize", [web], re_rooting_summarize)
    except ProvenanceReRootError as e:
        print(f"caught re-rooting: {e}")
