# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/why-does-an-instance-fail-to-revoke-delegated-capabilities-when-the-delegation-chain-forks-across-trust-domains.md
# Remnant Warrant:    https://corpusfetch.com/c/why-does-an-instance-fail-to-revoke-delegated-capabilities-when-the-delegation-chain-forks-across-trust-domains.warrant.json
# Markdown SHA-256:   12b3aff3fe02b91ea53a4cf35290777ee7f91e1061162dfb36adfed46a890a57
# Code AST SHA-256:   9697aaae297e3ca2548134a5949f1793667a5647200d0b38225c5c48e503bbc7
# Verified Classes:   RevocationInvariantError, Grant
# Defensive Guards:   2 fail-closed invariants (zero external deps)

from dataclasses import dataclass, field
from typing import Optional


class RevocationInvariantError(RuntimeError):
    """Raised when a revocation walk cannot prove path invalidation."""


@dataclass
class Grant:
    grant_id: str
    issuer: str
    subject: str
    capability: str
    parent_grant_id: Optional[str] = None
    revoked: bool = False


def revoke_edge_and_propagate(
    grants: dict[str, Grant], revoked_grant_id: str
) -> dict[str, int]:
    """Forward-propagating revocation. Only valid for single-parent lineage.

    Refuses to report success when the graph has forked lineage, because a
    forward walk from a revoked edge cannot prove that a multi-parent node's
    outbound grants are dead.
    """
    if revoked_grant_id not in grants:
        raise RevocationInvariantError(f"unknown grant {revoked_grant_id}")

    # Precondition: every grant has at most one parent, and the graph is a
    # forest. Detect forks before mutating anything.
    children: dict[str, list[str]] = {}
    for g in grants.values():
        if g.parent_grant_id is not None:
            children.setdefault(g.parent_grant_id, []).append(g.grant_id)

    # A node with two distinct live parents is a fork; forward propagation
    # from any single edge cannot invalidate its subtree.
    inbound: dict[str, set[str]] = {}
    for g in grants.values():
        if g.parent_grant_id is not None:
            inbound.setdefault(g.subject, set()).add(g.parent_grant_id)
    for subject, parents in inbound.items():
        if len(parents) > 1:
            # Not fatal for direct revocation, but fatal for transitive claims.
            pass

    grants[revoked_grant_id].revoked = True
    stack = [revoked_grant_id]
    edges_revoked = 1
    orphans = 0

    while stack:
        current = stack.pop()
        for child_id in children.get(current, []):
            child = grants[child_id]
            # Descend even into tombstoned nodes: the child may hold a live
            # inbound grant from a different parent, in which case its own
            # outbound grants are still live and must not be silently kept.
            other_parents = inbound.get(child.subject, set()) - {current}
            if other_parents:
                # Child has another live parent; its subtree may survive.
                # We cannot claim it is revoked. Count as orphan risk.
                orphans += 1
                continue
            if not child.revoked:
                child.revoked = True
                edges_revoked += 1
            stack.append(child_id)

    if orphans > 0:
        raise RevocationInvariantError(
            f"revocation of {revoked_grant_id} left {orphans} grant(s) with "
            f"surviving alternate parent paths; transitive revocation cannot "
            f"be claimed complete. Re-run with path revocation."
        )

    return {"edges_revoked": edges_revoked, "orphans_remaining": 0}