"""Deterministic iam-core 1.1 / wire-v2 graph evaluator.

The normative rules are in IAM.md. This implementation intentionally keeps
authentication, predecessor integrity, fork evidence, and semantic application
separate. It has no transport, clock, persistence, or automatic anchor policy.

CLI: python -m reference.iam_graph input.json
Input: {"known_trees": {...}, "anchored_set": [...], "tree": "...",
        "context": "community" | "personal"}
"""

import heapq
import json
from pathlib import Path
import sys

from .iam_verify import (
    ValidationError, canonical_bytes, parse_json, public_key_valid,
    tree_id as compute_tree_id, validate_envelope, validate_envelope_shape,
    verify_signature, record_message,
)


class AnchorError(ValidationError):
    """The supplied graph context or anchored set is incomplete/malformed."""


def _bootstrap(known_trees, tree):
    if not isinstance(known_trees, dict) or tree not in known_trees:
        raise AnchorError("unknown requested community tree")
    envelopes = known_trees[tree]
    if not isinstance(envelopes, list) or not envelopes:
        raise AnchorError("bootstrap must be a nonempty ordered list")
    records, ids, targets = [], set(), set()
    genesis, timestamp = None, None
    try:
        for envelope in envelopes:
            record = validate_envelope(envelope)
            if (record["context"] != "community" or record["kind"] != "ACCEPT"
                    or record["prev"] != "" or record["tree"] != tree):
                raise AnchorError("invalid bootstrap record role")
            if genesis is None:
                genesis, timestamp = record["actor"], record["m"]
            if record["actor"] != genesis or record["m"] != timestamp:
                raise AnchorError("bootstrap actor and timestamp must match")
            if record["target"] in targets or record["target"] == genesis:
                raise AnchorError("bootstrap targets must be distinct and non-genesis")
            records.append(record)
            ids.add(envelope["id"])
            targets.add(record["target"])
        if compute_tree_id(records) != tree:
            raise AnchorError("bootstrap tree id mismatch")
    except ValidationError as exc:
        raise AnchorError(f"invalid bootstrap: {exc}") from exc
    return targets, genesis, ids


def evaluate(known_trees, anchored_set, tree, context):
    """Evaluate exactly one complete scope, returning state and dispositions.

    A correct-id envelope with invalid signature can satisfy *existence* of a
    predecessor, but never authentication. Its authenticated descendants are
    rejected through their invalid predecessor chain. Bad shape or claimed id
    has no authority and does not satisfy closure. Every candidate signature is
    checked before logical-id deduplication; a bad duplicate cannot shadow a
    valid signature variant of the same canonical record.
    """
    if context not in ("community", "personal"):
        raise AnchorError("unknown requested context")
    if not isinstance(anchored_set, list):
        raise AnchorError("anchored_set must be an envelope list")
    if context == "community":
        axiomatic, genesis, bootstrap_ids = _bootstrap(known_trees, tree)
    else:
        if not public_key_valid(tree):
            raise AnchorError("invalid personal implicit root public key")
        axiomatic, genesis, bootstrap_ids = {tree}, None, set()

    records, authenticated = {}, set()
    for envelope in anchored_set:
        if isinstance(envelope, dict) and isinstance(envelope.get("record"), dict):
            version = envelope["record"].get("v")
            if type(version) is int and version != 2:
                # A recognized old/new wire version is an input-contract error,
                # not a malformed record silently removed from an old history.
                raise AnchorError("unsupported record wire version")
        try:
            record = validate_envelope_shape(envelope, check_id=True)
        except (ValidationError, TypeError, KeyError):
            # Do not use, report, index, or follow an unverified claimed id.
            continue
        rid = envelope["id"]
        if record["tree"] != tree or record["context"] != context:
            raise AnchorError("anchor contains a record outside requested scope")
        if rid in bootstrap_ids:
            raise AnchorError("anchor contains a bootstrap record")
        if rid in records and canonical_bytes(records[rid]) != canonical_bytes(record):
            raise AnchorError("one id identifies conflicting record content")
        # Authenticate *each* envelope before retaining a logical id. Signature
        # bytes are not record identity and never enter the fork relation.
        valid_signature = verify_signature(
            record["actor"], record_message(record), envelope["sig"])
        if valid_signature:
            authenticated.add(rid)
        records[rid] = record

    children = {rid: [] for rid in records}
    for rid, record in records.items():
        prev = record["prev"]
        if not prev:
            continue
        if prev not in records:
            raise AnchorError("anchor is not closed under correctly identified prev")
        predecessor = records[prev]
        if (record["tree"], record["context"], record["actor"]) != (
                predecessor["tree"], predecessor["context"], predecessor["actor"]):
            raise AnchorError("prev points outside its actor chain")
        children[prev].append(rid)

    sibling_groups = {}
    for rid in authenticated:
        record = records[rid]
        key = (record["tree"], record["context"], record["actor"], record["prev"])
        sibling_groups.setdefault(key, set()).add(rid)
    fork_children = set().union(*(group for group in sibling_groups.values()
                                 if len(group) > 1)) if sibling_groups else set()

    edges, departed = set(), set()
    chain_valid, rejected, applied = {}, {}, []

    def members():
        found = set(axiomatic)
        while True:
            grown = found | {child for parent, child in edges if parent in found}
            if grown == found:
                return found
            found = grown

    def reachable(source, target):
        # Include all active edges, including edges lacking an axiomatic path.
        visited, pending = set(), [source]
        while pending:
            node = pending.pop()
            if node == target:
                return True
            if node in visited:
                continue
            visited.add(node)
            pending.extend(child for parent, child in edges if parent == node)
        return False

    ready = [(r["m"], rid) for rid, r in records.items() if r["prev"] == ""]
    heapq.heapify(ready)
    while ready:
        _, rid = heapq.heappop(ready)
        record = records[rid]
        for child in children[rid]:
            heapq.heappush(ready, (records[child]["m"], child))
        prev = record["prev"]
        reason = None
        if rid not in authenticated:
            reason = "signature"
        elif rid in fork_children:
            reason = "fork"
        elif prev and not chain_valid[prev]:
            reason = "invalid_predecessor"
        elif prev and record["m"] < records[prev]["m"]:
            reason = "monotonicity"
        elif genesis is not None and record["actor"] == genesis:
            reason = "reserved_genesis_actor"
        chain_valid[rid] = reason is None
        if reason is not None:
            rejected[rid] = reason
            continue

        actor, target, kind = record["actor"], record["target"], record["kind"]
        current = members()
        valid = actor in current
        if kind == "ACCEPT":
            valid = (valid and actor not in departed and target not in departed
                     and target != genesis and (actor, target) not in edges
                     and not reachable(target, actor))
        elif kind == "REVOKE":
            valid = valid and actor != target and (actor, target) in edges
        elif kind == "LEAVE":
            valid = valid and context == "community" and actor == target
        if not valid:
            rejected[rid] = "semantic"
            continue
        if kind == "ACCEPT":
            edges.add((actor, target))
        elif kind == "REVOKE":
            edges.remove((actor, target))
        else:
            edges = {(parent, child) for parent, child in edges
                     if actor != parent and actor != child}
            axiomatic.discard(actor)
            departed.add(actor)
        applied.append(rid)

    if len(chain_valid) != len(records):
        raise AnchorError("prev dependency graph contains an unresolved cycle")
    return {
        "members": sorted(members()), "axiomatic": sorted(axiomatic),
        "departed": sorted(departed), "edges": sorted(map(list, edges)),
        "applied": applied, "rejected": dict(sorted(rejected.items())),
    }


def main():
    if len(sys.argv) != 2:
        raise SystemExit("usage: python -m reference.iam_graph input.json")
    data = parse_json(Path(sys.argv[1]).read_bytes())
    result = evaluate(data["known_trees"], data["anchored_set"],
                      data["tree"], data["context"])
    print(json.dumps(result, indent=2, sort_keys=True))


if __name__ == "__main__":
    main()