# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/when-must-an-instance-distrust-its-own-memory-provenance-divergence-under-concurrent-agent-write-paths.md
# Remnant Warrant:    https://corpusfetch.com/c/when-must-an-instance-distrust-its-own-memory-provenance-divergence-under-concurrent-agent-write-paths.warrant.json
# Markdown SHA-256:   d4d97e9b89024787ca9dfc696f4a7daf65bfa5f55da2d63f0bdc01c9a55f3898
# Code AST SHA-256:   9bb483686f3cf2759de734bcc6879368e778c7aab91a8d63f39261ae2ead2172
# Verified Classes:   ProvenanceDivergenceError, LogEntry, MemoryStore
# Defensive Guards:   4 fail-closed invariants (zero external deps)

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable


class ProvenanceDivergenceError(RuntimeError):
    """Raised when a record's log-verified chain of custody does not close at a trusted root."""


@dataclass(frozen=True)
class LogEntry:
    record_id: str
    write_path: str
    derived_from: tuple[str, ...]


@dataclass
class MemoryStore:
    log: list[LogEntry] = field(default_factory=list)
    records: dict[str, dict] = field(default_factory=dict)
    trusted_roots: frozenset[str] = frozenset({"human_edit", "tool_result_verified"})
    quarantined: set[str] = field(default_factory=set)


def verify_chain(
    store: MemoryStore,
    record_id: str,
    *,
    _path: tuple[str, ...] = (),
) -> None:
    """Traverse derivation edges to a trusted root. Raises on any divergence."""
    if record_id in _path:
        raise ProvenanceDivergenceError(
            f"provenance cycle detected: {' -> '.join(_path + (record_id,))}"
        )
    entry = next((e for e in reversed(store.log) if e.record_id == record_id), None)
    if entry is None:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} has no log entry; metadata-only provenance is untrusted"
        )
    record = store.records.get(record_id, {})
    claimed = record.get("write_path")
    if claimed is not None and claimed != entry.write_path:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} claims write_path={claimed!r} "
            f"but log shows {entry.write_path!r}"
        )
    if entry.write_path in store.trusted_roots:
        return
    if not entry.derived_from:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} via {entry.write_path!r} has no derivation edges "
            f"and is not a trusted root"
        )
    for parent in entry.derived_from:
        verify_chain(store, parent, _path=_path + (record_id,))


def descendants(store: MemoryStore, record_id: str) -> set[str]:
    out: set[str] = set()
    frontier = [record_id]
    while frontier:
        current = frontier.pop()
        for entry in store.log:
            if current in entry.derived_from and entry.record_id not in out:
                out.add(entry.record_id)
                frontier.append(entry.record_id)
    return out


def quarantine_subtree(store: MemoryStore, root: str) -> set[str]:
    try:
        verify_chain(store, root)
        return set()
    except ProvenanceDivergenceError:
        affected = {root} | descendants(store, root)
        store.quarantined |= affected
        return affected