# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-should-an-instance-treat-a-forget-operation-as-incomplete-until-downstream-context-derived-from-the-forgotten-memory-is-invalidated.md
# Remnant Warrant:    https://corpusfetch.com/c/how-should-an-instance-treat-a-forget-operation-as-incomplete-until-downstream-context-derived-from-the-forgotten-memory-is-invalidated.warrant.json
# Markdown SHA-256:   1d0dd1d0afaf8b13a90960bd328f9fffbd6fd237b557057023b6e49f12a7bfae
# Code AST SHA-256:   1873cbde6145c40ec806c4a98840bc0a5856f02d3a60085f10efe87393b46ec3
# Verified Classes:   DeletionVerificationError, ReceiptState, ProvenanceGraph, ForgetReceipt
# Defensive Guards:   3 fail-closed invariants (zero external deps)

from __future__ import annotations

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


class DeletionVerificationError(RuntimeError):
    """Raised when a forget receipt is asserted as verified but derivations remain live."""


class ReceiptState(str, Enum):
    PROVISIONAL = "provisional"   # source deleted, derivations not enumerated
    FINAL = "final"               # source deleted, derivation closure invalidated


@dataclass
class ProvenanceGraph:
    # edges: derivation_id -> set of source_ids it was derived from
    edges: dict[str, set[str]] = field(default_factory=dict)
    tainted: set[str] = field(default_factory=set)

    def derivations_of(self, source_id: str) -> set[str]:
        return {d for d, srcs in self.edges.items() if source_id in srcs}

    def transitive_derivations(self, source_id: str) -> set[str]:
        seen: set[str] = set()
        frontier = [source_id]
        while frontier:
            cur = frontier.pop()
            for d in self.derivations_of(cur):
                if d not in seen:
                    seen.add(d)
                    frontier.append(d)
        return seen


@dataclass
class ForgetReceipt:
    source_id: str
    state: ReceiptState
    invalidated: set[str]
    residual: set[str]


def forget(
    source_id: str,
    graph: ProvenanceGraph,
    *,
    enumeration_complete: bool,
) -> ForgetReceipt:
    """
    Two-phase forget. Phase 1 deletes the source (assumed done by caller).
    Phase 2 invalidates the transitive derivation closure.
    """
    if not enumeration_complete:
        # We cannot prove non-retrievability; do not claim it.
        return ForgetReceipt(
            source_id=source_id,
            state=ReceiptState.PROVISIONAL,
            invalidated=set(),
            residual=set(),
        )

    derivations = graph.transitive_derivations(source_id)
    for d in derivations:
        graph.tainted.add(d)

    return ForgetReceipt(
        source_id=source_id,
        state=ReceiptState.FINAL,
        invalidated=derivations,
        residual=set(),
    )


def assert_verified_deletion(receipt: ForgetReceipt) -> None:
    """Gate before reporting 'deleted' to a user or compliance system."""
    if receipt.state is not ReceiptState.FINAL:
        raise DeletionVerificationError(
            f"forget({receipt.source_id}) is {receipt.state.value}: "
            "derivations were not enumerated; cannot claim verified deletion"
        )
    if receipt.residual:
        raise DeletionVerificationError(
            f"forget({receipt.source_id}) left live derivations: {sorted(receipt.residual)}"
        )


def retrieve(derivation_id: str, graph: ProvenanceGraph) -> str:
    if derivation_id in graph.tainted:
        raise DeletionVerificationError(
            f"derivation {derivation_id} is tainted by a forgotten source; "
            "treat as cache miss and evict"
        )
    return f"content-of:{derivation_id}"
