# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-should-an-instance-distinguish-transitive-prompt-injection-taint-from-legitimate-tool-data-provenance-in-multi-hop-invocation-graphs.md
# Remnant Warrant:    https://corpusfetch.com/c/how-should-an-instance-distinguish-transitive-prompt-injection-taint-from-legitimate-tool-data-provenance-in-multi-hop-invocation-graphs.warrant.json
# Markdown SHA-256:   174497437e77bbf590dadf73c586e629f6d47cbd612c694f0c1880d16534be48
# Code AST SHA-256:   a99b45c2ce85e1c42550dd8bd0e34226010ec1a9a38d9e0b4b7236b1ecac0de2
# Verified Classes:   TaintViolation, Node, LineageGraph
# Defensive Guards:   3 fail-closed invariants (zero external deps)

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable


class TaintViolation(RuntimeError):
    """Raised when a tainted value reaches a sink without declassification."""


@dataclass(frozen=True)
class Node:
    node_id: str
    tool_id: str
    inputs: tuple[str, ...]  # node_ids of inputs
    declassifies: bool = False


class LineageGraph:
    """Tracks derivation, not byte identity. Taint = reachability from untrusted root."""

    def __init__(self) -> None:
        self._nodes: dict[str, Node] = {}
        self._untrusted_roots: set[str] = set()

    def add_root(self, node_id: str, tool_id: str, untrusted: bool) -> None:
        self._nodes[node_id] = Node(node_id=node_id, tool_id=tool_id, inputs=())
        if untrusted:
            self._untrusted_roots.add(node_id)

    def add_derived(
        self, node_id: str, tool_id: str, inputs: Iterable[str], declassifies: bool = False
    ) -> None:
        inputs = tuple(inputs)
        for i in inputs:
            if i not in self._nodes:
                raise TaintViolation(f"unknown input node {i!r} for {node_id!r}")
        self._nodes[node_id] = Node(
            node_id=node_id, tool_id=tool_id, inputs=inputs, declassifies=declassifies
        )

    def is_tainted(self, node_id: str) -> bool:
        """True iff some derivation path from an untrusted root reaches node_id
        without crossing a declassification checkpoint."""
        if node_id not in self._nodes:
            raise TaintViolation(f"unknown node {node_id!r}")
        seen: set[str] = set()
        stack: list[str] = [node_id]
        while stack:
            cur = stack.pop()
            if cur in seen:
                continue
            seen.add(cur)
            if cur in self._untrusted_roots:
                return True
            node = self._nodes[cur]
            if node.declassifies:
                continue  # checkpoint: do not traverse further upstream
            stack.extend(node.inputs)
        return False

    def assert_sink_safe(self, sink_arg_node: str, sink_tool: str) -> None:
        if self.is_tainted(sink_arg_node):
            path = self._derivation_path(sink_arg_node)
            raise TaintViolation(
                f"sink {sink_tool!r} received tainted argument {sink_arg_node!r}; "
                f"derivation path: {' -> '.join(path)}. "
                f"Route through a proven declassifier or refuse the call."
            )

    def _derivation_path(self, node_id: str) -> list[str]:
        # BFS shortest tainted path for the error message.
        from collections import deque

        q: deque[list[str]] = deque([[node_id]])
        seen: set[str] = set()
        while q:
            path = q.popleft()
            cur = path[-1]
            if cur in seen:
                continue
            seen.add(cur)
            if cur in self._untrusted_roots:
                return list(reversed(path))
            node = self._nodes[cur]
            if node.declassifies:
                continue
            for parent in node.inputs:
                q.append(path + [parent])
        return [node_id]


def run_three_hop_demo() -> None:
    g = LineageGraph()
    # Hop 0: untrusted web fetch.
    g.add_root("fetch_1", tool_id="fetch_url", untrusted=True)
    # Hop 1: summarizer. NOT a declassifier (natural-language output).
    g.add_derived("summ_1", tool_id="summarize", inputs=["fetch_1"], declassifies=False)
    # Hop 2: email body. The string looks clean; lineage says otherwise.
    g.add_derived("email_body_1", tool_id="format_as_json", inputs=["summ_1"])
    # Sink: must refuse.
    g.assert_sink_safe("email_body_1", sink_tool="send_email")


if __name__ == "__main__":
    try:
        run_three_hop_demo()
    except TaintViolation as exc:
        print(f"BLOCKED: {exc}")
