check_branching_coefficient_readers.py

#!/usr/bin/env python3
"""Finite independent audit of prepared branching readers, not a native scheduler."""
from dataclasses import dataclass
from collections import Counter
from itertools import product
import json
import random


@dataclass(frozen=True)
class Trie:
    refs: int = 0
    zero: object = None
    one: object = None


@dataclass(frozen=True)
class Profile:
    count: int
    bad: bool
    tail: object


def change(root, word, delta, breadth):
    """Persistent path copy and a separately maintained depth-count profile."""
    changes = [0] * len(word)
    touches = 0

    def walk(node, i):
        nonlocal touches
        touches += 1
        old = node
        node = node or Trie()
        if i == len(word):
            refs = node.refs + delta
            assert refs >= 0
            out = Trie(refs, node.zero, node.one)
        else:
            bit = word[i]
            child = walk(node.one if bit else node.zero, i + 1)
            out = Trie(node.refs, node.zero if bit else child,
                       child if bit else node.one)
        if out.refs == 0 and out.zero is None and out.one is None:
            out = None
        if i:
            changes[i - 1] = int(out is not None) - int(old is not None)
        return out

    new = walk(root, 0)

    def adjust(cell, i):
        nonlocal touches
        if i == len(changes):
            return cell
        touches += 1
        count = (cell.count if cell else 0) + changes[i]
        assert count >= 0
        tail = adjust(cell.tail if cell else None, i + 1)
        return Profile(count, count > LIMIT or bool(tail and tail.bad), tail)

    profile = adjust(breadth, 0)
    assert touches == 2 * len(word) + 1
    return new, profile, touches


def terminals(root, prefix=()):
    if root is None:
        return {}
    out = {prefix: root.refs} if root.refs else {}
    out.update(terminals(root.zero, prefix + (0,)))
    out.update(terminals(root.one, prefix + (1,)))
    return out


def literal_counts(words):
    return [len({w[:t] for w in words if len(w) >= t})
            for t in range(1, max(map(len, words), default=0) + 1)]


def check_profile(profile, words):
    expected = literal_counts(words)
    got = []
    cell = profile
    while cell:
        got.append(cell.count)
        assert cell.bad == (cell.count > LIMIT or bool(cell.tail and cell.tail.bad))
        cell = cell.tail
    assert got[:len(expected)] == expected
    assert not any(got[len(expected):])
    assert bool(profile and profile.bad) == any(x > LIMIT for x in expected)


def advance(frontier, bit):
    out = []
    for node, parity in frontier:
        if node.zero:
            out.append((node.zero, parity))
        if node.one:
            out.append((node.one, parity ^ bit))
    assert len(out) <= LIMIT
    return out


def syndromes(root, query):
    frontier = [(root, 0)] if root else []
    answer = []
    for bit in query:
        frontier = advance(frontier, bit)
        answer.append(tuple(v for node, v in frontier if node.refs))
    return answer


def dot(word, query):
    return sum(a * b for a, b in zip(word, query)) % 2


def conversion(global_root, local_root, masks, bound):
    """Track prefix injection only through ordered child labels, no identities."""
    g = [global_root] if global_root else []
    l = [local_root] if local_root else []
    injection = [0] if local_root else []
    profiles = {}
    for depth in range(1, bound + 1):
        ng, edge_to_slot = [], {}
        for i, node in enumerate(g):
            for bit, child in enumerate((node.zero, node.one)):
                if child:
                    edge_to_slot[i, bit] = len(ng)
                    ng.append(child)
        nl, ni = [], []
        for i, node in enumerate(l):
            for bit, child in enumerate((node.zero, node.one)):
                if child:
                    ni.append(edge_to_slot[injection[i], bit])
                    nl.append(child)
        g, l, injection = ng, nl, ni
        assert len(g) <= LIMIT and len(l) <= LIMIT
        terminal_positions = {i: k for k, i in enumerate(
            i for i, node in enumerate(g) if node.refs)}
        take = [terminal_positions[injection[i]] for i, node in enumerate(l) if node.refs]
        table = masks.get(depth, (0,))
        assert len(table) == 1 << len(take)
        values = {}
        for assignment in product((0, 1), repeat=len(terminal_positions)):
            ix = 0
            for pos in take:
                ix = (ix << 1) | assignment[pos]
            values[assignment] = table[ix]
        profiles[depth] = values
    return profiles


def build(words):
    root = profile = None
    for w in words:
        root, profile, _ = change(root, w, 1, profile)
    return root, profile


def main():
    global LIMIT
    rng = random.Random(167)
    counts = Counter()
    LIMIT = 4
    root = profile = None
    literal = Counter()
    versions = []
    universe = [tuple(rng.randrange(2) for _ in range(n)) for n in range(1, 13) for _ in range(8)]
    for _ in range(3000):
        if literal and rng.randrange(3) == 0:
            w = rng.choice(list(literal))
            delta = -1
        else:
            w, delta = rng.choice(universe), 1
        root, profile, touches = change(root, w, delta, profile)
        literal[w] += delta
        if not literal[w]:
            del literal[w]
        check_profile(profile, literal)
        counts['updates'] += 1
        counts['path_and_profile_visits'] += touches
        counts['wide_intermediate_versions'] += bool(profile and profile.bad)
        if rng.randrange(37) == 0:
            versions.append((root, profile, dict(literal)))
    # Delete everything but a final prefix-compatible family. Multiplicity is exact.
    for w, refs in list(literal.items()):
        for _ in range(refs):
            root, profile, _ = change(root, w, -1, profile)
            literal[w] -= 1
            if not literal[w]:
                del literal[w]
            check_profile(profile, literal)
            counts['recovery_deletions'] += 1
    assert root is None and not profile.bad
    for old_root, old_profile, words in versions:
        check_profile(old_profile, words)
        assert terminals(old_root) == words
        counts['retained_versions'] += 1
    # Final-rank examples: at each width supports use the first two coordinates.
    global_words = set()
    rows = []
    for _ in range(25):
        words, masks = set(), {}
        for n in range(2, 11):
            available = sorted(tuple(a) + (0,) * (n - 2)
                               for a in ((0, 1), (1, 0), (1, 1)))
            chosen = [w for w in available if rng.randrange(2)]
            words.update(chosen)
            masks[n] = tuple(rng.randrange(2) for _ in range(1 << len(chosen)))
        rows.append((words, masks))
        global_words.update(words)
    groot, gp = build(global_words)
    check_profile(gp, global_words)
    assert not gp.bad
    for words, masks in rows:
        lroot, lp = build(words)
        conv = conversion(groot, lroot, masks, 12)
        for n in range(1, 13):
            for _ in range(30):
                query = tuple(rng.randrange(2) for _ in range(n))
                gs = syndromes(groot, query)
                ls = syndromes(lroot, query)
                for t in range(1, n + 1):
                    gexpected = tuple(dot(w, query[:t]) for w in sorted(global_words) if len(w) == t)
                    lexpected = tuple(dot(w, query[:t]) for w in sorted(words) if len(w) == t)
                    assert gs[t - 1] == gexpected and ls[t - 1] == lexpected
                    ix = 0
                    for v in lexpected:
                        ix = (ix << 1) | v
                    expected = masks.get(t, (0,))[ix]
                    assert conv[t][gexpected] == expected
                    counts['converted_prefix_answers'] += 1
                counts['queries'] += 1
    # Irregular branch/termination patterns exercise frontier renumbering.
    for _ in range(100):
        frontier, all_words = [()], set()
        for depth in range(1, 10):
            children = [p + (bit,) for p in frontier for bit in (0, 1)]
            rng.shuffle(children)
            frontier = sorted(children[:rng.randint(1, min(LIMIT, len(children)))])
            all_words.update(p for p in frontier if any(p) and rng.randrange(3) == 0)
        gr, _ = build(all_words)
        subset = {w for w in all_words if rng.randrange(2)}
        lr, _ = build(subset)
        tables = {n: tuple(rng.randrange(2) for _ in range(1 << sum(len(w) == n for w in subset)))
                  for n in range(1, 10)}
        converted = conversion(gr, lr, tables, 11)
        for _ in range(20):
            query = tuple(rng.randrange(2) for _ in range(11))
            got = syndromes(gr, query)
            for t in range(1, 12):
                expected = tuple(dot(w, query[:t]) for w in sorted(all_words) if len(w) == t)
                assert got[t - 1] == expected
                local = tuple(dot(w, query[:t]) for w in sorted(subset) if len(w) == t)
                index = 0
                for bit in local:
                    index = 2 * index + bit
                assert converted[t][expected] == tables.get(t, (0,))[index]
                counts['irregular_frontier_answers'] += 1
    # Constant masks survive empty coefficient frontiers.
    empty = conversion(None, None, {3: (1,), 7: (1,)}, 10)
    assert [empty[t][()] for t in range(1, 11)] == [0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
    # Short deletions cannot change longer suffix breadth, even while wide.
    for depth in (8, 12, 16):
        words = {(1,) + tuple((i >> j) & 1 for j in range(depth - 1)) for i in range(16)}
        rr, pp = build(words)
        rr, pp, _ = change(rr, (0, 0), 1, pp)
        suffix = pp.tail.tail
        rr, pp, _ = change(rr, (0, 0), -1, pp)
        assert pp.tail.tail is suffix  # Implementation sharing check, never a semantic channel.
        check_profile(pp, words)
        counts['unchanged_suffix_checks'] += 1
    # Breadth four need not mean rank at most two.
    independent = {tuple(int(i == j) for i in range(4)) for j in range(4)}
    ir, ip = build(independent)
    assert not ip.bad and literal_counts(independent)[-1] == 4
    for query in product((0, 1), repeat=4):
        assert syndromes(ir, query)[-1] == tuple(dot(w, query) for w in sorted(independent))
        counts['broader_gate_queries'] += 1
    # Different widths expire, allowing unbounded total coefficient rank.
    rolling = {tuple(int(i == n - 1) for i in range(n)) for n in range(2, 33)}
    rr, rp = build(rolling)
    assert not rp.bad and max(literal_counts(rolling)) <= 2
    for _ in range(100):
        query = tuple(rng.randrange(2) for _ in range(35))
        got = syndromes(rr, query)
        for t in range(1, 36):
            assert got[t - 1] == tuple(dot(w, query[:t]) for w in sorted(rolling) if len(w) == t)
            counts['rolling_width_answers'] += 1
    # Count alone cannot discharge a last delayed point.
    candidate = {(0, 0), (0, 1)}
    observed = {(0, 0), (1, 0)}
    assert len(candidate) == len(observed) and candidate != observed
    print(json.dumps({'status': 'passed', **dict(sorted(counts.items()))}, indent=2))


if __name__ == '__main__':
    main()