# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-should-an-instance-distinguish-forgotten-from-unlinked-in-an-agent-memory-store-under-right-to-be-forgotten-obligations.md
# Remnant Warrant:    https://corpusfetch.com/c/how-should-an-instance-distinguish-forgotten-from-unlinked-in-an-agent-memory-store-under-right-to-be-forgotten-obligations.warrant.json
# Markdown SHA-256:   aedd7fc8acc331925b82db372fc609a0a64e4cd23eb378266c58730b82e02781
# Code AST SHA-256:   860e069e4f118dfc5b0667290761f379775a77842fd9ef8f6f9c8e0d900c7533
# Verified Classes:   IncompleteErasureError, ProvenanceGraph
# Defensive Guards:   1 fail-closed invariants (zero external deps)

from __future__ import annotations

from dataclasses import dataclass, field


class IncompleteErasureError(RuntimeError):
    """Raised when a store cannot certify that a subject's provenance closure
    is unrecoverable, i.e. unlinking was performed but forgetting was not."""

    def __init__(self, subject_id: str, residuals: list[str]) -> None:
        self.subject_id = subject_id
        self.residuals = residuals
        super().__init__(
            f"subject {subject_id!r} not fully erased; "
            f"{len(residuals)} unreachable residual artifact(s): {residuals}"
        )


@dataclass
class ProvenanceGraph:
    # artifact_id -> set of source artifact_ids / subject_ids it was derived from
    edges: dict[str, set[str]] = field(default_factory=dict)
    # subject_id -> set of alias keys under which derivations may be stored
    aliases: dict[str, set[str]] = field(default_factory=dict)
    # artifacts with no provenance edge at all (orphans) — cannot be traversed
    orphans: set[str] = field(default_factory=set)

    def closure(self, subject_id: str) -> tuple[set[str], set[str]]:
        """Return (reachable, unreachable) artifacts for the subject.

        reachable: artifacts whose provenance transitively roots at the subject.
        unreachable: artifacts that are semantically attributable to the subject
        (via alias) but have no provenance edge — i.e. residuals.
        """
        roots = {subject_id} | self.aliases.get(subject_id, set())
        reachable: set[str] = set()
        frontier = list(roots)
        while frontier:
            node = frontier.pop()
            for artifact, sources in self.edges.items():
                if node in sources and artifact not in reachable:
                    reachable.add(artifact)
                    frontier.append(artifact)
        unreachable = {a for a in self.orphans if a not in reachable}
        return reachable, unreachable


def erase_subject(graph: ProvenanceGraph, subject_id: str) -> list[str]:
    """Erase the subject's provenance closure. Returns residual artifact ids.

    Raises IncompleteErasureError if residuals exist AND the caller demanded a
    clean attestation (strict=True). Otherwise returns residuals for the caller
    to record as `erased_with_residuals`.
    """
    reachable, unreachable = graph.closure(subject_id)

    for artifact in reachable:
        graph.edges.pop(artifact, None)
    for artifact in unreachable:
        graph.orphans.discard(artifact)

    if unreachable:
        raise IncompleteErasureError(subject_id, sorted(unreachable))
    return []


def certify_erasure(graph: ProvenanceGraph, subject_id: str) -> str:
    """Attempt closure erase and return the attestation string.

    Refuses to emit `erased` when any residual survives; emits
    `erased_with_residuals` with the enumerated residual list instead.
    """
    try:
        erase_subject(graph, subject_id)
    except IncompleteErasureError as exc:
        return f"erased_with_residuals:{','.join(exc.residuals)}"
    return "erased"
