#!/usr/bin/env python3
"""Explicit decoded-branch predictor protocol, Python 3.10+, standard library.
Trusted actual outcomes; not an ISA executor, clock model or security proof.
"""
import sys
sys.dont_write_bytecode = True
from dataclasses import dataclass, asdict
from itertools import product
import json
import random


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


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


def integer(x): return type(x) is int


def pc_ok(x): return integer(x) and 0 <= x < 2**32 and x % 4 == 0


def successor(pc): return (pc + 4) % 2**32


class TargetBuffer:
    """Store PC tag and aligned target word; low index bits are implicit."""
    def __init__(self, bits=2):
        demand(integer(bits) and 0 <= bits <= 12, 'target bits 0..12')
        self.bits = bits
        self.rows = [None] * (1 << bits)

    def lookup(self, pc):
        demand(pc_ok(pc), 'aligned unsigned 32-bit PC')
        word = pc >> 2
        index, tag = word % len(self.rows), word >> self.bits
        row = self.rows[index]
        return dict(hit=row is not None and row[0] == tag,
                    target=(row[1] << 2) if row is not None and row[0] == tag else None,
                    index=index, tag=tag)

    def train(self, pc, target):
        demand(pc_ok(pc) and pc_ok(target), 'aligned PC and actual target')
        word = pc >> 2
        self.rows[word % len(self.rows)] = (word >> self.bits, target >> 2)

    def snapshot(self): return [None if r is None else list(r) for r in self.rows]


@dataclass(frozen=True)
class RASState:
    cells: tuple
    next: int
    count: int


class ReturnStack:
    """Bounded circular stack. Empty returns None; overflow drops oldest."""
    def __init__(self, capacity=4):
        demand(integer(capacity) and 1 <= capacity <= 4096, 'RAS capacity 1..4096')
        self.capacity = capacity
        self.cells = [None] * capacity
        self.next = self.count = 0

    def push(self, address):
        demand(pc_ok(address), 'return PC')
        self.cells[self.next] = address
        self.next = (self.next + 1) % self.capacity
        self.count = min(self.count + 1, self.capacity)

    def peek(self):
        return self.cells[(self.next - 1) % self.capacity] if self.count else None

    def pop(self):
        if not self.count: return None
        self.next = (self.next - 1) % self.capacity
        self.count -= 1
        return self.cells[self.next]  # contents deliberately remain in inactive cells

    def snapshot(self): return RASState(tuple(self.cells), self.next, self.count)

    def restore(self, state):
        demand(type(state) is RASState and type(state.cells) is tuple and
               len(state.cells) == self.capacity and integer(state.next) and
               0 <= state.next < self.capacity and integer(state.count) and
               0 <= state.count <= self.capacity and
               all(v is None or pc_ok(v) for v in state.cells), 'RAS state shape')
        demand(all(state.cells[(state.next - 1 - k) % self.capacity] is not None
                   for k in range(state.count)), 'active RAS entries must be valid')
        self.cells = list(state.cells)
        self.next, self.count = state.next, state.count

    def logical(self):
        return [self.cells[(self.next - self.count + k) % self.capacity]
                for k in range(self.count)]


@dataclass(frozen=True)
class Ticket:
    serial: int
    pc: int
    kind: str
    history: int
    index: object
    counter: object
    direction: int
    next_pc: int
    target_source: str
    ras_before: RASState


@dataclass
class Pending:
    ticket: Ticket
    resolved: bool = False
    actual: object = None
    target: object = None


class Predictor:
    def __init__(self, m=2, h=2, target_bits=2, ras_capacity=3, capacity=6,
                 initial=1, log=True):
        demand(integer(m) and integer(h) and 0 <= h <= m <= 12 and
               integer(initial) and 0 <= initial <= 3, 'direction configuration')
        demand(integer(capacity) and 1 <= capacity <= 4096 and type(log) is bool,
               'pending capacity/log')
        self.m, self.h, self.capacity = m, h, capacity
        self.counters = [initial] * (1 << m)
        self.btb = TargetBuffer(target_bits)
        self.ras = ReturnStack(ras_capacity)
        self.committed_ras = ReturnStack(ras_capacity)
        self.history = self.committed_history = 0
        self.pending = []
        self.next_serial = 0
        self.events = []
        self.log = log

    def _emit(self, event, **kw):
        if self.log: self.events.append(dict(event=event, **kw))

    def _shift(self, history, bit): return ((history << 1) | bit) % (1 << self.h)

    @staticmethod
    def _ras_effect(stack, kind, pc):
        if kind == 'CALL': stack.push(successor(pc))
        elif kind == 'RET': stack.pop()

    def _find(self, ticket):
        demand(type(ticket) is Ticket, 'ticket type')
        for k, entry in enumerate(self.pending):
            if entry.ticket is ticket: return k, entry
        raise ValueError('canceled, committed, foreign or forged ticket')

    def begin(self, pc, kind):
        demand(pc_ok(pc) and type(kind) is str and kind in ('C', 'J', 'CALL', 'RET'), 'decoded PC/kind')
        if len(self.pending) == self.capacity: return None
        index = ((pc >> 2) % len(self.counters)) ^ (self.history << (self.m - self.h)) if kind == 'C' else None
        counter = self.counters[index] if kind == 'C' else None
        direction = int(counter >= 2) if kind == 'C' else 1
        target = self.btb.lookup(pc)
        if not direction: next_pc, source = successor(pc), 'fallthrough'
        elif kind == 'RET' and self.ras.peek() is not None:
            next_pc, source = self.ras.peek(), 'RAS'
        elif target['hit']: next_pc, source = target['target'], 'BTB'
        else: next_pc, source = successor(pc), 'target-miss-fallback'
        ticket = Ticket(self.next_serial, pc, kind, self.history, index,
                        counter, direction, next_pc, source, self.ras.snapshot())
        self.next_serial += 1
        self.pending.append(Pending(ticket))
        if kind == 'C': self.history = self._shift(self.history, direction)
        self._ras_effect(self.ras, kind, pc)
        if self.log: self._emit('predict', ticket=asdict(ticket), history_after=self.history,
                   ras_after=self.ras.logical(), btb_hit=target['hit'])
        return ticket

    def _restore_before(self, ticket):
        self.history = ticket.history
        self.ras.restore(ticket.ras_before)

    def _commit_training(self, entry):
        t = entry.ticket
        if t.kind == 'C':
            index = t.index  # query-time address, but CURRENT counter value
            self.counters[index] = max(0, min(3, self.counters[index] + (1 if entry.actual else -1)))
        if entry.actual: self.btb.train(t.pc, entry.target)

    def resolve(self, ticket, actual, target=None):
        k, entry = self._find(ticket)
        demand(not entry.resolved, 'already resolved')
        demand(integer(actual) and actual in (0, 1) and
               (ticket.kind == 'C' or actual == 1), 'actual direction')
        demand(pc_ok(target) if actual else target is None, 'actual target contract')
        real_next = target if actual else successor(ticket.pc)
        direction_wrong = actual != ticket.direction
        target_wrong = real_next != ticket.next_pc
        canceled = []
        entry.resolved, entry.actual, entry.target = True, actual, target
        if direction_wrong or target_wrong:
            canceled = [e.ticket.serial for e in self.pending[k+1:]]
            del self.pending[k+1:]
            self._restore_before(ticket)
            if ticket.kind == 'C': self.history = self._shift(self.history, actual)
            self._ras_effect(self.ras, ticket.kind, ticket.pc)
        answer = dict(redirect=direction_wrong or target_wrong,
                      direction_wrong=direction_wrong, next_pc_wrong=target_wrong,
                      next_pc=real_next, canceled=canceled)
        if self.log: self._emit('resolve', serial=ticket.serial, actual=actual, target=target,
                   history_after=self.history, ras_after=self.ras.logical(), **answer)
        return answer

    def commit(self):
        if not self.pending or not self.pending[0].resolved: return None
        entry = self.pending.pop(0)
        self._commit_training(entry)
        t = entry.ticket
        if t.kind == 'C': self.committed_history = self._shift(self.committed_history, entry.actual)
        self._ras_effect(self.committed_ras, t.kind, t.pc)
        if self.log: self._emit('commit', serial=t.serial, index=t.index,
                   counters=list(self.counters), committed_history=self.committed_history,
                   committed_ras=self.committed_ras.logical(), btb=self.btb.snapshot())
        return t

    def flush(self):
        canceled = [e.ticket.serial for e in self.pending]
        self.pending = []
        self.history = self.committed_history
        self.ras.restore(self.committed_ras.snapshot())
        if self.log: self._emit('flush', canceled=canceled, history=self.history, ras=self.ras.logical())
        return canceled

    def state(self):
        return dict(counters=list(self.counters), btb=self.btb.snapshot(),
                    history=self.history, committed_history=self.committed_history,
                    ras=asdict(self.ras.snapshot()), ras_logical=self.ras.logical(),
                    committed_ras=asdict(self.committed_ras.snapshot()),
                    pending=[asdict(e) for e in self.pending], next_serial=self.next_serial)


class EventOracle:
    """Unbounded branch-bit lists, ordinary list stacks, full-PC target dictionary.
    Replay from committed records after every event; no checkpoint restore logic.
    """
    def __init__(self, predictor, initial=1):
        self.p = predictor
        self.initial = initial
        self.done = []
        self.active = []

    def fold(self, records):
        bits, stack = [], []
        for row in records:
            t, actual, target = row
            bit = t.direction if actual is None else actual
            if t.kind == 'C': bits.append(bit)
            elif t.kind == 'CALL': stack = (stack + [successor(t.pc)])[-self.p.ras.capacity:]
            elif t.kind == 'RET' and stack: stack.pop()
        return bits, stack

    def number(self, bits):
        return sum(bit * 2**k for k, bit in enumerate(reversed(bits[-self.p.h:]))) if self.p.h else 0

    def trained(self):
        table = [self.initial] * len(self.p.counters)
        targets = {}
        for t, actual, target in self.done:
            if t.kind == 'C': table[t.index] = min(3, table[t.index]+1) if actual else max(0, table[t.index]-1)
            if actual: targets[(t.pc//4) % len(self.p.btb.rows)] = (t.pc, target)
        return table, targets

    def before_begin(self, pc, kind):
        bits, stack = self.fold(self.done + self.active)
        table, targets = self.trained()
        hist = self.number(bits)
        # Deliberately construct the XOR index one bit at a time.
        index = sum((((pc//4 >> i) & 1) ^ (((hist >> (i-(self.p.m-self.p.h))) & 1)
                     if i >= self.p.m-self.p.h else 0)) << i for i in range(self.p.m)) if kind == 'C' else None
        counter = table[index] if kind == 'C' else None
        direction = int(counter >= 2) if kind == 'C' else 1
        row = targets.get((pc//4) % len(self.p.btb.rows))
        if not direction: nxt, src = successor(pc), 'fallthrough'
        elif kind == 'RET' and stack: nxt, src = stack[-1], 'RAS'
        elif row is not None and row[0] == pc: nxt, src = row[1], 'BTB'
        else: nxt, src = successor(pc), 'target-miss-fallback'
        return hist, index, counter, direction, nxt, src

    def begin(self, pc, kind):
        expected = self.before_begin(pc, kind)
        ticket = self.p.begin(pc, kind)
        if len(self.active) == self.p.capacity: require(ticket is None, 'queue capacity'); return None
        require((ticket.history, ticket.index, ticket.counter, ticket.direction,
                 ticket.next_pc, ticket.target_source) == expected, 'prediction oracle')
        self.active.append([ticket, None, None]); self.check(); return ticket

    def resolve(self, ticket, actual, target=None):
        k = next(i for i, r in enumerate(self.active) if r[0] is ticket)
        mismatch = actual != ticket.direction or (target if actual else successor(ticket.pc)) != ticket.next_pc
        killed = [r[0].serial for r in self.active[k+1:]] if mismatch else []
        out = self.p.resolve(ticket, actual, target)
        self.active[k][1:] = actual, target
        if mismatch: del self.active[k+1:]
        require(out['canceled'] == killed and out['redirect'] == mismatch, 'cancellation oracle')
        self.check(); return out

    def commit(self):
        ready = self.active and self.active[0][1] is not None
        token = self.p.commit()
        if ready:
            row = self.active.pop(0); require(token is row[0], 'FIFO commit'); self.done.append(row)
        else: require(token is None, 'unresolved head')
        self.check(); return token

    def flush(self):
        expected = [r[0].serial for r in self.active]
        require(self.p.flush() == expected, 'flush cancellation'); self.active = []; self.check()

    def check(self):
        bits, stack = self.fold(self.done + self.active)
        cbits, cstack = self.fold(self.done)
        require((self.p.history, self.p.ras.logical()) == (self.number(bits), stack), 'speculative replay invariant')
        require((self.p.committed_history, self.p.committed_ras.logical()) == (self.number(cbits), cstack), 'committed replay invariant')
        table, targets = self.trained()
        require(self.p.counters == table, 'commit-only current-counter training')
        rows = [None] * len(self.p.btb.rows)
        for slot,(pc,target) in targets.items(): rows[slot] = [pc//4 //len(rows), target//4]
        require(self.p.btb.snapshot() == rows, 'commit-only target training')
        require([e.ticket.serial for e in self.p.pending] == [r[0].serial for r in self.active], 'pending identities')


def rejected_unchanged(p, action):
    before = json.dumps(dict(state=p.state(), events=p.events), sort_keys=True)
    try: action()
    except ValueError: pass
    else: raise AssertionError('invalid action accepted')
    require(before == json.dumps(dict(state=p.state(), events=p.events), sort_keys=True),
            'rejected action mutated state or log')


def target_fixture():
    b = TargetBuffer(2)
    rows = [dict(action='cold', pc=0x100, result=b.lookup(0x100))]
    b.train(0x100, 0x200)
    rows.append(dict(action='train100', table=b.snapshot(), own=b.lookup(0x100), collision=b.lookup(0x110)))
    require(b.lookup(0x100)['target'] == 0x200 and not b.lookup(0x110)['hit'], 'BTB tags')
    b.train(0x110, 0x300)
    rows.append(dict(action='replace110', table=b.snapshot(), old=b.lookup(0x100), new=b.lookup(0x110)))
    require(not b.lookup(0x100)['hit'] and b.lookup(0x110)['target'] == 0x300, 'direct-mapped replacement')
    p = Predictor(); o = EventOracle(p)
    predictions = []
    for actual_target in (0x200, 0x300, 0x200, 0x300):
        t = o.begin(0x100, 'J')
        outcome = o.resolve(t, 1, actual_target); o.commit()
        predictions.append(dict(predicted=t.next_pc, source=t.target_source,
                                actual=actual_target, wrong=outcome['next_pc_wrong']))
    require(all(x['wrong'] for x in predictions), 'same-site changing targets')
    return dict(collisions=rows, alternating=predictions, events=p.events)


def ras_fixture():
    p = Predictor(ras_capacity=3); o = EventOracle(p)
    for pc, target in ((0x100, 0x120), (0x120, 0x400)):
        t=o.begin(pc,'CALL');o.resolve(t,1,target);o.commit()
    first=o.begin(0x400,'RET');o.resolve(first,1,0x124);o.commit()
    second=o.begin(0x400,'RET'); last_btb=p.btb.lookup(0x400)
    o.resolve(second,1,0x104);o.commit()
    require((first.next_pc,second.next_pc,last_btb['target'])==(0x124,0x104,0x124),'nested shared return site')
    ring=ReturnStack(3)
    for address in (0x104,0x204,0x304):ring.push(address)
    saved=ring.snapshot()
    ring.push(0x404);ring.push(0x504)
    overwritten=ring.snapshot()
    bad=ReturnStack(3);bad.restore(overwritten)
    bad.next,bad.count=saved.next,saved.count
    pointer_only=[bad.pop() for _ in range(3)]
    # Save old top as well: two deeper cells still contain wrong-path values.
    top=ReturnStack(3);top.restore(overwritten)
    top.next,top.count=saved.next,saved.count
    top.cells[(saved.next-1)%3]=saved.cells[(saved.next-1)%3]
    pointer_top=[top.pop() for _ in range(3)]
    ring.restore(saved);full=[ring.pop() for _ in range(4)]
    require(pointer_only==pointer_top==[0x304,0x504,0x404] and full==[0x304,0x204,0x104,None],'full RAS content repair')
    overflow=ReturnStack(2)
    for address in (0x104,0x204,0x304):overflow.push(address)
    loss=[overflow.pop() for _ in range(3)]
    require(loss==[0x304,0x204,None],'bounded overflow loses oldest')
    return dict(events=p.events,second_return_btb=last_btb,
                saved=asdict(saved),overwritten=asdict(overwritten),
                pointer_only_returns=pointer_only,pointer_plus_top_returns=pointer_top,
                full_restore_returns=full,overflow_returns=loss)


def out_of_order_fixture():
    p=Predictor();o=EventOracle(p)
    for pc,target in ((0x100,0x200),(0x200,0x300)):
        t=o.begin(pc,'CALL');o.resolve(t,1,target);o.commit()
    a=o.begin(0x300,'C');b=o.begin(0x304,'CALL');c=o.begin(0x400,'RET')
    require(c.next_pc==0x308,'young return prediction')
    o.resolve(c,1,0x308);require(o.commit() is None,'younger resolved cannot commit')
    b_result=o.resolve(b,1,0x500)
    require(b_result['canceled']==[c.serial] and not b_result['direction_wrong'],'call target-only recovery')
    a_result=o.resolve(a,1,0x600)
    require(a_result['canceled']==[b.serial] and a_result['direction_wrong'],'older recovery replaces younger')
    require(p.ras.logical()==[0x104,0x204] and p.history==1,'oldest repaired state')
    o.commit()
    for stale in (a,b,c):rejected_unchanged(p,lambda stale=stale:p.resolve(stale,1,0x600))
    return dict(events=p.events,final=p.state(),stale_rejections=3)


def timing_fixtures():
    # Different directions may lead to exactly the same numerical next PC.
    p=Predictor();o=EventOracle(p)
    t=o.begin(0x100,'C');young=o.begin(0x104,'C');r=o.resolve(t,1,0x104)
    require(r['direction_wrong'] and not r['next_pc_wrong'] and r['canceled']==[young.serial] and p.history==1,'same-PC direction repair')
    o.commit();same=dict(events=p.events,final=p.state())
    # Correct direction, stale target. Seed target through the real commit API.
    p=Predictor(initial=2);o=EventOracle(p,2)
    seed=o.begin(0x100,'J');o.resolve(seed,1,0x300);o.commit()
    t=o.begin(0x100,'C');o.begin(0x104,'C');r=o.resolve(t,1,0x400)
    require(not r['direction_wrong'] and r['next_pc_wrong'],'target-only error')
    o.commit();target_only=dict(events=p.events,final=p.state())
    # Both tickets captured counter 1. Their commits must accumulate 1->2->1.
    p=Predictor(m=0,h=0);o=EventOracle(p)
    a=o.begin(0x100,'C');o.resolve(a,1,0x200)
    b=o.begin(0x104,'C');o.resolve(b,0)
    o.commit();after_first=list(p.counters);o.commit()
    require(a.counter==b.counter==1 and after_first==[2] and p.counters==[1],'current-counter sequential training')
    current=dict(events=p.events,after_first=after_first,final=p.state())
    # Committed state survives a whole-machine flush; all pending tickets die.
    p=Predictor();o=EventOracle(p)
    t=o.begin(0x100,'CALL');o.resolve(t,1,0x200);o.commit()
    t=o.begin(0x200,'C');o.resolve(t,1,0x300);o.commit()
    a=o.begin(0x300,'RET');b=o.begin(0x304,'C')
    o.resolve(b,b.direction,b.next_pc if b.direction else None)
    tables=(list(p.counters),p.btb.snapshot());o.flush()
    require(p.history==1 and p.ras.logical()==[0x104] and tables==(p.counters,p.btb.snapshot()),'committed flush state')
    for ticket in (a,b):rejected_unchanged(p,lambda ticket=ticket:p.resolve(ticket,1,0x400))
    flush=dict(events=p.events,final=p.state())
    return dict(equal_next_pc=same,target_only=target_only,current_counter=current,flush=flush)


def exhaustive_tables_and_stacks():
    counts=dict(target_states=0,target_queries=0,target_updates=0,ras_states=0,ras_transitions=0,ras_restores=0)
    row_options=(None,(0,0),(0,1),(1,0),(1,1))
    for bits in range(3):
        n=1<<bits
        for rows in product(row_options,repeat=n):
            b=TargetBuffer(bits);b.rows=list(rows);counts['target_states']+=1
            for pc in range(0,4*(2*n+1),4):
                slot=(pc//4)%n;row=rows[slot]
                expected=None if row is None or row[0]*n+slot!=pc//4 else row[1]*4
                got=b.lookup(pc)
                require(got['hit']==(expected is not None) and got['target']==expected,'exhaustive BTB query')
                counts['target_queries']+=1
                for target in (0,4,2**32-4):
                    b.rows=list(rows);b.train(pc,target)
                    want=list(rows);want[slot]=(pc//4//n,target//4)
                    require(b.rows==want,'exhaustive BTB train');counts['target_updates']+=1
                b.rows=list(rows)
    # Explore all reachable physical ring states over two return addresses.
    # Expected logical contents use ordinary lists, with no ring arithmetic.
    for capacity in range(1,5):
        initial=ReturnStack(capacity).snapshot();todo=[(initial,[])];seen={initial}
        while todo:
            saved,logical=todo.pop();counts['ras_states']+=1
            for operation in ('pop',0,4):
                s=ReturnStack(capacity);s.restore(saved);lst=list(logical)
                if operation=='pop': expected=lst.pop() if lst else None;require(s.pop()==expected,'RAS pop')
                else:s.push(operation);lst=(lst+[operation])[-capacity:]
                require(s.logical()==lst and s.peek()==(lst[-1] if lst else None),'RAS list equivalence')
                counts['ras_transitions']+=1
                nxt=s.snapshot()
                if nxt not in seen:seen.add(nxt);todo.append((nxt,lst))
                for value in (8,12,16,20,24):s.push(value)
                s.pop();s.restore(saved)
                require(s.snapshot()==saved and s.logical()==logical,'snapshot restores all cells')
                counts['ras_restores']+=1
    return counts


def invalid_fixtures():
    constructors=[lambda:Predictor(m=True),lambda:Predictor(m=1,h=2),lambda:Predictor(initial=4),
                  lambda:Predictor(capacity=0),lambda:Predictor(log=1),lambda:TargetBuffer(-1),
                  lambda:ReturnStack(0)]
    count=0
    for action in constructors:
        try:action()
        except ValueError:count+=1
        else:raise AssertionError('invalid constructor')
    p=Predictor(capacity=2);a=p.begin(0x100,'C');b=p.begin(0x104,'CALL')
    full_before=json.dumps(dict(state=p.state(),events=p.events),sort_keys=True)
    require(p.begin(0x108,'RET') is None,'full queue returns unavailable')
    require(full_before==json.dumps(dict(state=p.state(),events=p.events),sort_keys=True),'full queue is unchanged')
    foreign=Predictor().begin(0x100,'C');forged=Ticket(**asdict(a))
    actions=[lambda:p.begin(True,'C'),lambda:p.begin(3,'J'),lambda:p.begin(2**32,'C'),
             lambda:p.begin(0,'unknown'),lambda:p.resolve(a,True,0),lambda:p.resolve(a,1,3),
             lambda:p.resolve(a,0,0),lambda:p.resolve(b,0),lambda:p.resolve(foreign,0),
             lambda:p.resolve(forged,0),lambda:p.resolve(None,0)]
    for action in actions:rejected_unchanged(p,action);count+=1
    p.resolve(b,1,b.next_pc)
    rejected_unchanged(p,lambda:p.resolve(b,1,b.next_pc));count+=1
    p.flush()
    for token in (a,b):rejected_unchanged(p,lambda token=token:p.resolve(token,0));count+=1
    stack=ReturnStack(2);stack.push(4);saved=stack.snapshot()
    badstates=[RASState((None,None),0,1),RASState((4,),0,1),RASState((4,None),True,1),RASState((3,None),1,1),RASState((4,None),1,3)]
    for state in badstates:
        try:stack.restore(state)
        except ValueError:count+=1
        else:raise AssertionError('invalid RAS import')
        require(stack.snapshot()==saved,'RAS reject atomic')
    p=Predictor();o=EventOracle(p);wrap=o.begin(2**32-4,'CALL')
    require(wrap.next_pc==0 and p.ras.logical()==[0],'successor wraps 32 bits')
    o.resolve(wrap,1,0);o.commit()
    return dict(rejected=count,wrap_call=p.events)


def randomized_protocol():
    rng=random.Random(24024);counts=dict(configurations=0,events=0,predictions=0,resolutions=0,commits=0,flushes=0,stale_rejections=0)
    for case in range(900):
        m=rng.randrange(5);h=rng.randrange(m+1);initial=rng.randrange(4)
        p=Predictor(m=m,h=h,target_bits=rng.randrange(4),ras_capacity=rng.randrange(1,5),capacity=rng.randrange(1,7),initial=initial,log=False)
        o=EventOracle(p,initial);retired_or_killed=[]
        for step in range(100):
            before=[r[0] for r in o.active]
            action=rng.randrange(10)
            unresolved=[r[0] for r in o.active if r[1] is None]
            if action<4:
                t=o.begin(rng.choice([0,4,8,12,0x100,0x110,2**32-4]),rng.choice(['C','J','CALL','RET']))
                if t is not None:counts['predictions']+=1
            elif action<7 and unresolved:
                t=rng.choice(unresolved)
                actual=(rng.randrange(2) if t.kind=='C' else 1)
                target=(t.next_pc if rng.random()<.65 else rng.choice([0,4,8,0x200,0x300])) if actual else None
                o.resolve(t,actual,target);counts['resolutions']+=1
            elif action<9:
                if o.commit() is not None:counts['commits']+=1
            else:o.flush();counts['flushes']+=1
            live=[r[0] for r in o.active]
            retired_or_killed.extend(t for t in before if not any(t is v for v in live))
            if retired_or_killed and rng.random()<.12:
                stale=rng.choice(retired_or_killed)
                rejected_unchanged(p,lambda:p.resolve(stale,1,0));counts['stale_rejections']+=1
            counts['events']+=1
        o.flush();counts['configurations']+=1
    return counts


def external_faults():
    class RecomputeIndex(Predictor):
        def _commit_training(self, e):
            if e.ticket.kind=='C':
                wrong=(e.ticket.pc//4 % len(self.counters)) ^ (self.history<<(self.m-self.h))
                self.counters[wrong]=max(0,min(3,self.counters[wrong]+(1 if e.actual else -1)))
            if e.actual:self.btb.train(e.ticket.pc,e.target)
    class CapturedCounter(Predictor):
        def _commit_training(self,e):
            if e.ticket.kind=='C':self.counters[e.ticket.index]=max(0,min(3,e.ticket.counter+(1 if e.actual else -1)))
            if e.actual:self.btb.train(e.ticket.pc,e.target)
    class PointerOnly(Predictor):
        def _restore_before(self,t):
            self.history=t.history;self.ras.next=t.ras_before.next;self.ras.count=t.ras_before.count
    class PrematureTraining(Predictor):
        def resolve(self,t,actual,target=None):
            result=super().resolve(t,actual,target)
            self._commit_training(self._find(t)[1]);return result
    failures=[]
    for label,kind in [('recomputed index',RecomputeIndex),('captured counter',CapturedCounter),('pointer-only RAS repair',PointerOnly),('resolution-time training',PrematureTraining)]:
        try:
            p=kind(m=0,h=0) if kind is CapturedCounter else kind()
            o=EventOracle(p)
            if kind is PointerOnly:
                for pc in (0x100,0x200,0x300):
                    t=o.begin(pc,'CALL');o.resolve(t,1,pc+4);o.commit()
                a=o.begin(0x400,'C');o.begin(0x500,'CALL');o.begin(0x600,'CALL');o.resolve(a,1,0x800)
            elif kind is CapturedCounter:
                a=o.begin(0x100,'C');o.resolve(a,1,0x200)
                b=o.begin(0x104,'C');o.resolve(b,0);o.commit();o.commit()
            else:
                a=o.begin(0x100,'C');o.resolve(a,1,0x200);o.commit()
        except AssertionError as error:failures.append(dict(fault=label,caught=str(error)))
        else:raise AssertionError('mutant survived '+label)
    return failures


def main():
    return dict(status='PASS',target_buffer=target_fixture(),return_stack=ras_fixture(),
                out_of_order=out_of_order_fixture(),timing=timing_fixtures(),
                exhaustive=exhaustive_tables_and_stacks(),invalid=invalid_fixtures(),
                random=randomized_protocol(),external_mutants=external_faults())


if __name__=='__main__':
    print(json.dumps(main(),ensure_ascii=False,indent=2,sort_keys=True))