# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/where-must-an-instance-forget-before-it-can-be-audited-the-tombstone-before-erasure-invariant-in-agent-memory-stores.md
# Remnant Warrant:    https://corpusfetch.com/c/where-must-an-instance-forget-before-it-can-be-audited-the-tombstone-before-erasure-invariant-in-agent-memory-stores.warrant.json
# Markdown SHA-256:   6581fbfa260d28a023e51bf96b0ce0a3a4f2c2b73c6eb86d44b51d3216084a61
# Code AST SHA-256:   959634623b432536b65e31a504268a089ab9a719c6edea0e9def36869e485507
# Verified Classes:   ForgetIncompleteError, TombstoneOrderingError, Tombstone, AuditableMemoryStore
# Defensive Guards:   5 fail-closed invariants (zero external deps)

import hashlib
from dataclasses import dataclass, field
from datetime import datetime, timezone
from typing import Iterable


class ForgetIncompleteError(RuntimeError):
    """Raised when an erasure cannot be certified as auditable and complete."""


class TombstoneOrderingError(RuntimeError):
    """Raised when payload destruction is attempted before a durable tombstone."""


@dataclass(frozen=True)
class Tombstone:
    memory_id: str
    content_hash: str
    requested_by: str
    legal_basis: str
    created_at: datetime
    derivations: tuple[str, ...] = field(default_factory=tuple)


class AuditableMemoryStore:
    """Memory store enforcing tombstone-before-erasure over a derivation DAG."""

    def __init__(self) -> None:
        self._payloads: dict[str, bytes] = {}
        self._derivations: dict[str, set[str]] = {}
        self._tombstones: dict[str, Tombstone] = {}
        self._confirmed_destroyed: dict[str, set[str]] = {}

    def put(self, memory_id: str, payload: bytes) -> None:
        self._payloads[memory_id] = payload
        self._derivations.setdefault(memory_id, set())

    def derive(self, source_id: str, derivation_id: str) -> None:
        if source_id in self._tombstones:
            raise ForgetIncompleteError(
                f"cannot derive {derivation_id!r} from forgotten memory {source_id!r}"
            )
        self._derivations.setdefault(source_id, set()).add(derivation_id)

    def forget(
        self,
        memory_id: str,
        requested_by: str,
        legal_basis: str,
        confirmed_destroyed: Iterable[str],
    ) -> Tombstone:
        if memory_id not in self._payloads:
            raise ForgetIncompleteError(
                f"memory {memory_id!r} has no live payload; cannot certify erasure"
            )
        payload = self._payloads[memory_id]
        derivations = tuple(sorted(self._derivations.get(memory_id, set())))

        tombstone = Tombstone(
            memory_id=memory_id,
            content_hash=hashlib.sha256(payload).hexdigest(),
            requested_by=requested_by,
            legal_basis=legal_basis,
            created_at=datetime.now(timezone.utc),
            derivations=derivations,
        )
        # Ordering invariant: tombstone is durable before any payload destruction.
        self._tombstones[memory_id] = tombstone

        confirmed = set(confirmed_destroyed)
        unconfirmed = [d for d in derivations if d not in confirmed]
        if unconfirmed:
            raise ForgetIncompleteError(
                f"forget of {memory_id!r} incomplete: derivations not confirmed "
                f"destroyed: {unconfirmed}"
            )

        del self._payloads[memory_id]
        self._confirmed_destroyed[memory_id] = confirmed
        return tombstone

    def assert_auditable(self, memory_id: str) -> None:
        if memory_id not in self._tombstones:
            raise TombstoneOrderingError(
                f"erasure of {memory_id!r} has no prior tombstone; audit gap"
            )
        tomb = self._tombstones[memory_id]
        missing = [d for d in tomb.derivations if d not in self._confirmed_destroyed[memory_id]]
        if missing:
            raise ForgetIncompleteError(
                f"tombstone for {memory_id!r} not closed over derivations: {missing}"
            )