# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/how-does-an-instance-detect-forgetting-without-provenance-the-tombstone-orphan-boundary-in-read-write-forget-memory-apis.md
# Remnant Warrant:    https://corpusfetch.com/c/how-does-an-instance-detect-forgetting-without-provenance-the-tombstone-orphan-boundary-in-read-write-forget-memory-apis.warrant.json
# Markdown SHA-256:   03e4cf4892aa138892cba11963e4f9d771d8f65ab9c173e83fb4759fa56d0792
# Code AST SHA-256:   ed9ed72c78f5e6c5d130cbee2410533bf6f6d07b02bf0d2fbc7211e917d1f93b
# Verified Classes:   ProvenanceIntegrityError, Record, Tombstone, MemoryStore
# Defensive Guards:   7 fail-closed invariants (zero external deps)

from dataclasses import dataclass, field
from typing import Dict, List, Optional, Set


class ProvenanceIntegrityError(RuntimeError):
    """Raised when a live artifact's provenance cannot be soundly resolved."""
    pass


@dataclass
class Record:
    id: str
    generation: int
    provenance: List[str] = field(default_factory=list)  # recorded edge ids
    live: bool = True


@dataclass
class Tombstone:
    id: str
    generation: int
    forget_reason: str


class MemoryStore:
    def __init__(self) -> None:
        self.records: Dict[str, Record] = {}
        self.tombstones: Dict[str, Tombstone] = {}
        self._gen_counter = 0

    def write(self, rec_id: str, provenance: Optional[List[str]] = None) -> Record:
        if rec_id in self.records and self.records[rec_id].live:
            raise ProvenanceIntegrityError(f"live id collision on {rec_id}")
        if rec_id in self.tombstones:
            # id reuse is only legal across a generation bump
            self._gen_counter = self.tombstones[rec_id].generation + 1
        rec = Record(rec_id, self._gen_counter, list(provenance or []))
        self.records[rec_id] = rec
        return rec

    def forget(self, rec_id: str, reason: str, policy: str) -> None:
        rec = self.records.get(rec_id)
        if rec is None or not rec.live:
            raise ProvenanceIntegrityError(f"forget of unknown/live-false id {rec_id}")
        referrers = self._inbound_edges(rec_id)
        if policy == "reject_on_reference" and referrers:
            raise ProvenanceIntegrityError(
                f"cannot forget {rec_id}: {len(referrers)} live referrers {referrers}"
            )
        if policy == "cascade_invalidate":
            for r in referrers:
                self.records[r].live = False
        # tombstone-and-flag and cascade both write a tombstone
        self.tombstones[rec_id] = Tombstone(rec_id, rec.generation, reason)
        rec.live = False
        if policy == "tombstone_and_flag":
            for r in referrers:
                self._mark_degraded(r)

    def _mark_degraded(self, rec_id: str) -> None:
        # flag only; artifact stays live but is known-partial
        self.records[rec_id].live = True
        setattr(self.records[rec_id], "degraded", True)

    def _inbound_edges(self, target: str) -> List[str]:
        return [
            r.id for r in self.records.values()
            if r.live and target in r.provenance
        ]

    def verify_provenance(self) -> None:
        """Post-forget and periodic sweep. Raises on any unresolvable edge."""
        for rec in self.records.values():
            if not rec.live:
                continue
            for edge in rec.provenance:
                if edge in self.records and self.records[edge].live:
                    continue
                tomb = self.tombstones.get(edge)
                if tomb is None:
                    raise ProvenanceIntegrityError(
                        f"dangling provenance: live {rec.id} references missing {edge}"
                    )
                if getattr(rec, "degraded", False) is not True:
                    raise ProvenanceIntegrityError(
                        f"silent provenance loss: {rec.id} references forgotten {edge} "
                        f"({tomb.forget_reason}) without degraded flag"
                    )
                # generation check catches id-reuse misresolution
                if tomb.generation >= rec.generation and edge in self.records:
                    raise ProvenanceIntegrityError(
                        f"misresolved provenance: {rec.id} resolves {edge} to wrong generation"
                    )


def safe_forget(store: MemoryStore, rec_id: str, reason: str) -> str:
    erasure = reason in {"user_request", "gdpr_erasure"}
    policy = "cascade_invalidate" if erasure else "tombstone_and_flag"
    try:
        store.forget(rec_id, reason, policy)
        store.verify_provenance()
    except ProvenanceIntegrityError as exc:
        raise ProvenanceIntegrityError(
            f"forget of {rec_id} under policy {policy} left provenance unsound: {exc}"
        ) from exc
    return policy