# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/where-must-an-instance-draw-the-line-between-lossy-eviction-and-semantic-checkpoint-invalidation-under-auto-compaction.md
# Remnant Warrant:    https://corpusfetch.com/c/where-must-an-instance-draw-the-line-between-lossy-eviction-and-semantic-checkpoint-invalidation-under-auto-compaction.warrant.json
# Markdown SHA-256:   3d4ecd6369cd3587d4d59c45daad6efd8d45865d2fbca897af264ffa6d8a00ee
# Code AST SHA-256:   5c503bc988a883938946b2b44a2959cd516134c6eab69fdee2a343f297899fd9
# Verified Classes:   CheckpointInvalidationError, Proposition, Checkpoint, EvictionCandidate
# Defensive Guards:   2 fail-closed invariants (zero external deps)

from dataclasses import dataclass, field
from typing import Literal


class CheckpointInvalidationError(RuntimeError):
    """Raised when an eviction would orphan a live checkpoint proposition.

    This is a provenance failure, not a data-loss failure: the proposition
    survives in the checkpoint but its evidence is about to be evicted,
    leaving an assertion with no validity condition.
    """


Validity = Literal["re_derivable", "pinned", "volatile", "unverified"]


@dataclass
class Proposition:
    claim: str
    validity: Validity
    evidence_ref: str | None = None  # turn id, store key, or hash


@dataclass
class Checkpoint:
    generation: int
    propositions: list[Proposition] = field(default_factory=list)


@dataclass
class EvictionCandidate:
    region_id: str
    tokens: int
    contains_evidence_for: set[str] = field(default_factory=set)


def audit_eviction(
    candidates: list[EvictionCandidate],
    checkpoints: list[Checkpoint],
    token_budget: int,
) -> list[EvictionCandidate]:
    """Return the subset of candidates safe to evict.

    Raises CheckpointInvalidationError if any candidate is the sole evidence
    for a proposition that is neither re_derivable, pinned, nor volatile.
    """
    # Index live propositions by the evidence they depend on.
    dependent: dict[str, list[Proposition]] = {}
    for cp in checkpoints:
        for prop in cp.propositions:
            if prop.validity == "unverified":
                # Unverified propositions are already downgraded; they may be
                # evicted, but must not be carried forward as verified.
                continue
            if prop.evidence_ref is not None:
                dependent.setdefault(prop.evidence_ref, []).append(prop)

    safe: list[EvictionCandidate] = []
    for cand in candidates:
        orphaned = [
            prop
            for ref in cand.contains_evidence_for
            for prop in dependent.get(ref, [])
            if prop.validity not in ("re_derivable", "pinned", "volatile")
        ]
        if orphaned:
            raise CheckpointInvalidationError(
                f"Evicting region {cand.region_id!r} would orphan "
                f"{len(orphaned)} live proposition(s) with no validity "
                f"condition: {[p.claim for p in orphaned]!r}. "
                f"Downgrade to 'unverified' or pin evidence before evicting."
            )
        safe.append(cand)

    # Token budget is a trigger, never an authorization: only evict the
    # audited-safe subset, and only until the budget is met.
    selected: list[EvictionCandidate] = []
    freed = 0
    for cand in sorted(safe, key=lambda c: c.tokens, reverse=True):
        if freed >= token_budget:
            break
        selected.append(cand)
        freed += cand.tokens
    return selected


def compact(
    candidates: list[EvictionCandidate],
    checkpoints: list[Checkpoint],
    token_budget: int,
) -> list[EvictionCandidate]:
    if not candidates:
        return []
    try:
        return audit_eviction(candidates, checkpoints, token_budget)
    except CheckpointInvalidationError:
        # Caller must downgrade or pin; do not silently proceed.
        raise
