#!/usr/bin/env python3
"""Finite, precise teaching heaps. Standard library; stdout only; no production GC.
Incremental mode has only strong fields and single-thread atomic commands.
Ephemeron mode freezes the entire heap and has no finalizers or resurrection.
Dictionary operations use the expected constant-time, fixed-size-ID model.
Diagnostic snapshots/reachability checks are separate from collector-step cost.
"""
from collections import deque, defaultdict
from copy import deepcopy
import json
import random


def require(ok, message):
    if not ok:
        raise ValueError(message)


def index(i, n):
    require(type(i) is int and 0 <= i < n, "invalid slot index")


def validate_heap(heap, roots):
    require(type(heap) is dict and type(roots) is list, "heap/root containers")
    require(all(type(x) is str and x for x in heap), "object IDs are nonempty strings")
    def pointer(p):
        require(p is None or (type(p) is str and p in heap), "invalid pointer")
    for fields in heap.values():
        require(type(fields) is list, "field container")
        for p in fields:
            pointer(p)
    for p in roots:
        pointer(p)
    return pointer


def reachable(heap, roots):
    seen, q = set(), deque(p for p in roots if p is not None)
    while q:
        x = q.popleft()
        require(x in heap, "dangling reachable pointer")
        if x not in seen:
            seen.add(x)
            q.extend(p for p in heap[x] if p is not None)
    return seen


class Incremental:
    def __init__(self, heap, roots, barrier="all"):
        validate_heap(heap, roots)
        require(barrier in ("all", "black", "none"), "barrier policy")
        self.heap, self.roots = deepcopy(heap), list(roots)
        self.barrier = barrier
        self.active = False
        self.begin()

    def begin(self):
        require(not self.active, "cycle already active")
        self.active = True
        self.color = {x: "white" for x in self.heap}
        self.cursor = {x: 0 for x in self.heap}
        self.gray = deque()
        self.steps = self.scanned = 0
        for p in self.roots:
            self.shade(p)

    def shade(self, p):
        if p is not None and self.color[p] == "white":
            self.color[p] = "gray"
            self.gray.append(p)

    def read(self, path):
        require(self.active, "no active cycle")
        if path is None:
            return None
        require(type(path) in (tuple, list) and len(path) > 0, "rooted path required")
        index(path[0], len(self.roots))
        p = self.roots[path[0]]
        for i in path[1:]:
            require(p is not None and p in self.heap, "null/dangling path")
            index(i, len(self.heap[p]))
            p = self.heap[p][i]
        return p

    def store(self, base_path, slot, value_path):
        # Both paths are read before any heap mutation; there is no GC in this command.
        x, p = self.read(base_path), self.read(value_path)
        require(x is not None, "null base")
        index(slot, len(self.heap[x]))
        if self.barrier == "all" or (self.barrier == "black" and self.color[x] == "black"):
            self.shade(p)
        self.heap[x][slot] = p

    def root_store(self, slot, value_path):
        index(slot, len(self.roots))
        p = self.read(value_path)
        # Root publication is shaded even in the field-barrier fault variants.
        self.shade(p)
        self.roots[slot] = p

    def allocate(self, name, fields, root_slot):
        require(self.active, "no active cycle")
        require(type(name) is str and name and name not in self.heap, "fresh ID required")
        require(type(fields) is int and fields >= 0, "invalid field count")
        index(root_slot, len(self.roots))
        self.heap[name] = [None] * fields
        self.color[name], self.cursor[name] = "black", fields
        self.roots[root_slot] = name

    def step(self):
        require(self.active, "no active cycle")
        if not self.gray:
            return False
        x = self.gray[0]
        i = self.cursor[x]
        if i < len(self.heap[x]):
            self.shade(self.heap[x][i])
            self.cursor[x] += 1
            self.scanned += 1
        if self.cursor[x] == len(self.heap[x]):
            self.gray.popleft()
            self.color[x] = "black"
        self.steps += 1
        return True

    def invariant(self):
        require(self.active, "no active cycle")
        require(len(self.gray) == len(set(self.gray)), "duplicate gray entry")
        require(set(self.gray) == {x for x in self.heap if self.color[x] == "gray"}, "gray queue")
        require(all(p is None or self.color[p] != "white" for p in self.roots), "white root")
        for x, fs in self.heap.items():
            i = self.cursor[x]
            require(0 <= i <= len(fs), "cursor")
            if self.color[x] == "black":
                require(i == len(fs), "black cursor")
            if self.color[x] != "white":
                require(all(p is None or self.color[p] != "white" for p in fs[:i]), "white scanned target")
        return True

    def sweep(self):
        require(self.active and not self.gray, "marking incomplete")
        # Deliberately usable by fault demonstrations too: their dangling edge is observable.
        dead = [x for x in self.heap if self.color[x] == "white"]
        for x in dead:
            del self.heap[x]
        self.active = False
        return dead

    def snapshot(self):
        return {"heap": deepcopy(self.heap), "roots": list(self.roots),
                "colors": dict(self.color), "cursors": dict(self.cursor),
                "gray": list(self.gray), "steps": self.steps, "fields_scanned": self.scanned}


def conditional_collect(heap, roots, weak, ephemerons):
    """ephemerons maps each holder to [key,value]; all slots frozen during this call."""
    pointer = validate_heap(heap, roots)
    require(type(weak) is dict and type(ephemerons) is dict, "special slot containers")
    for h, fs in weak.items():
        require(type(h) is str and h in heap and type(fs) is list, "weak holder")
        for p in fs:
            pointer(p)
    for h, pair in ephemerons.items():
        require(type(h) is str and h in heap and type(pair) is list and len(pair) == 2, "ephemeron")
        for p in pair:
            pointer(p)
    wait = defaultdict(list)
    for h, (k, v) in ephemerons.items():
        if k is not None:
            wait[h].append(h)
            wait[k].append(h)
    live, order, q, fired = set(), [], deque(), set()
    cause, checks, strong_scans = {}, 0, 0
    def mark(x, why):
        if x is not None and x not in live:
            live.add(x)
            order.append(x)
            cause[x] = why
            q.append(x)
    for p in roots:
        mark(p, "root")
    while q:
        x = q.popleft()
        for p in heap[x]:
            strong_scans += 1
            mark(p, ["strong", x])
        for h in wait[x]:
            checks += 1
            k, v = ephemerons[h]
            if h not in fired and h in live and k in live:
                fired.add(h)
                mark(v, ["ephemeron", h, k])
    # No mutator resumes between clearing these slots and freeing the complement.
    out_heap = {x: list(fs) for x, fs in heap.items() if x in live}
    out_weak = {h: [p if p in live else None for p in fs]
                for h, fs in weak.items() if h in live}
    out_eph = {h: list(pair) if pair[0] in live else [None, None]
               for h, pair in ephemerons.items() if h in live}
    return {"heap": out_heap, "roots": list(roots), "weak": out_weak,
            "ephemerons": out_eph, "live_order": order, "cause": cause,
            "freed": [x for x in heap if x not in live],
            "activated": [h for h in ephemerons if h in fired],
            "event_checks": checks, "strong_scans": strong_scans}


def conditional_oracle(heap, roots, eph):
    # Slower independent iteration: rebuild strong reachability then fire all eligible rules.
    live = reachable(heap, roots)
    while True:
        more = [v for h, (k, v) in eph.items() if h in live and k in live and v is not None]
        nxt = reachable(heap, list(live) + more)
        if nxt == live:
            return live
        live = nxt


def barrier_example(policy="all", gray_prefix=False, write_slot=0):
    h = {"A": [None, None] if gray_prefix else [None], "B": ["C"], "C": [], "U": []}
    m = Incremental(h, ["A", "B"], policy)
    trace = [m.snapshot()]
    m.step(); trace.append(m.snapshot())
    m.store((0,), write_slot, (1, 0)); trace.append(m.snapshot())
    m.store((1,), 0, None); trace.append(m.snapshot())
    before = reachable(m.heap, m.roots)
    while m.step():
        trace.append(m.snapshot())
    lost = before - {x for x in m.heap if m.color[x] != "white"}
    dead = m.sweep()
    return {"policy": policy, "gray_prefix": gray_prefix, "write_slot": write_slot, "trace": trace,
            "freed": dead, "lost_reachable": sorted(lost), "final_heap": m.heap}


def ephemeron_fixture():
    names = ["E1", "E2", "Ebad", "W", "K1", "K2", "V1", "V2", "Kbad", "Vbad", "U"]
    h = {x: [] for x in names}
    h["V1"], h["Vbad"] = ["K2"], ["Kbad"]
    roots = ["E1", "E2", "Ebad", "W", "K1"]
    eph = {"E2": ["K2", "V2"], "E1": ["K1", "V1"], "Ebad": ["Kbad", "Vbad"]}
    return h, roots, {"W": ["Kbad"]}, eph


def ephemeron_example():
    h, roots, weak, eph = ephemeron_fixture()
    first = conditional_collect(h, roots, weak, eph)
    second = conditional_collect(first["heap"], roots[:-1], first["weak"], first["ephemerons"])
    return first, second


def self_check():
    rng = random.Random(1717)
    actions = 0
    for case in range(400):
        names = [str(i) for i in range(8)]
        h = {x: [rng.choice([None] + names) for _ in range(rng.randrange(4))] for x in names}
        m = Incremental(h, rng.choices([None] + names, k=3))
        for t in range(80):
            paths = [(i,) for i in range(3)]
            # Only use legal, bounded rooted paths; the public read permits any finite depth.
            for depth in range(2):
                for path in list(paths):
                    if len(path) == depth + 1:
                        x = m.read(path)
                        if x is not None:
                            paths.extend(path + (i,) for i in range(len(m.heap[x])))
            bases = [p for p in paths if m.read(p) is not None and m.heap[m.read(p)]]
            kind = rng.randrange(5)
            if kind == 0:
                m.step()
            elif kind == 1 and bases:
                b = rng.choice(bases)
                m.store(b, rng.randrange(len(m.heap[m.read(b)])), rng.choice(paths + [None]))
            elif kind == 2:
                m.root_store(rng.randrange(3), rng.choice(paths + [None]))
            elif kind == 3 and t % 8 == 0:
                m.allocate(f"new{t}", rng.randrange(4), rng.randrange(3))
            else:
                m.read(rng.choice(paths))
            m.invariant(); actions += 1
        live = reachable(m.heap, m.roots)
        while m.step():
            m.invariant()
        m.sweep()
        require(live <= set(m.heap), "incremental safety")
        m.begin()
        while m.step():
            m.invariant()
        m.sweep()
        require(set(m.heap) == live, "stable next cycle exactness")
    cases = 0
    for _ in range(6000):
        names = [str(i) for i in range(rng.randrange(1, 10))]
        vals = [None] + names
        h = {x: [rng.choice(vals) for _ in range(rng.randrange(3))] for x in names}
        roots = rng.choices(vals, k=rng.randrange(5))
        eph = {x: rng.choices(vals, k=2) for x in names if rng.randrange(2)}
        weak = {x: rng.choices(vals, k=rng.randrange(3)) for x in names if rng.randrange(2)}
        out = conditional_collect(h, roots, weak, eph)
        live = conditional_oracle(h, roots, eph)
        require(set(out["heap"]) == live, "least fixed point")
        require(out["event_checks"] <= 2 * len(eph), "event work")
        for fs in out["weak"].values():
            require(all(p is None or p in live for p in fs), "cleared weak slots")
        for k, v in out["ephemerons"].values():
            require((k is None and v is None) or (k in live and (v is None or v in live)), "cleared ephemeron")
        cases += 1
    return {"incremental_traces": 400, "mutator_or_collector_actions": actions, "conditional_heaps": cases}


def main():
    examples = [barrier_example(p, g) for g in (False, True) for p in ("all", "black", "none")]
    for e in examples:
        expected_loss = e["policy"] == "none" or (e["policy"] == "black" and e["gray_prefix"])
        require(e["lost_reachable"] == (["C"] if expected_loss else []), "barrier counterexample")
    first, second = ephemeron_example()
    require(len(first["heap"]) == 8 and len(second["heap"]) == 4, "conditional example")
    m = Incremental({"A": []}, ["A", None])
    m.allocate("Fresh", 2, 1); m.root_store(1, None)
    while m.step(): pass
    first_dead = m.sweep(); retained = list(m.heap)
    m.begin()
    while m.step(): pass
    second_dead = m.sweep()
    require(first_dead == [] and second_dead == ["Fresh"], "floating allocation")
    # An unreachable holder must not retain a value even when its key is a root.
    holder = conditional_collect({"E": [], "K": [], "V": []}, ["K"], {}, {"E": ["K", "V"]})
    weak_box = conditional_collect({"E": [], "K": []}, ["E"], {}, {"E": ["K", "K"]})
    require(holder["freed"] == ["E", "V"] and weak_box["freed"] == ["K"], "holder/weak-box boundary")
    pending_write = barrier_example("black", True, 1)
    require(pending_write["lost_reachable"] == [], "unscanned suffix example")
    h, roots, weak, eph = ephemeron_fixture()
    extra_root = conditional_collect(h, roots + ["Kbad"], weak, eph)
    root_removed = conditional_collect(extra_root["heap"], roots, extra_root["weak"], extra_root["ephemerons"])
    require(len(extra_root["heap"]) == 10 and root_removed["freed"] == ["Kbad", "Vbad"], "real root then removal")
    same = conditional_collect({"E": [], "V": []}, ["E"], {}, {"E": ["E", "V"]})
    require(same["activated"] == ["E"] and same["event_checks"] == 2, "holder equals key")
    empty = conditional_collect({}, [], {}, {})
    require(empty["heap"] == {}, "empty heap")
    rejected = 0
    for call in [lambda: Incremental({"A": ["missing"]}, []),
                 lambda: Incremental({"A": []}, ["A"]).read((True,)),
                 lambda: Incremental({"A": []}, ["A"]).allocate("N", True, 0),
                 lambda: conditional_collect({"A": []}, [], {}, {"A": ["missing", None]}),
                 lambda: Incremental({"A": []}, ["A"]).sweep()]:
        try: call()
        except ValueError: rejected += 1
        else: raise RuntimeError("invalid input accepted")
    print(json.dumps({"barrier_examples": examples, "ephemeron_first": first,
          "ephemeron_second": second, "floating": {"retained_first": retained, "freed_second": second_dead},
          "unreachable_holder": holder, "weak_box": weak_box, "pending_write": pending_write,
          "extra_key_root": extra_root, "extra_key_root_removed": root_removed,
          "holder_equals_key": same, "rejected": rejected,
          "checks": self_check()}, ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()