check_support_component_reuse.py

#!/usr/bin/env python3
"""Finite semantic audit of bounded support-component reuse.

Host-language oracle only: does not implement or certify native deadlines,
old-top allocation, literal routing, or the simultaneous-record compiler.
Exhaustive finite histories and seeded trials compare an online component
builder against independent maximal-alias-block semantics and ordinary sets.
"""
from __future__ import annotations
import itertools
import json
import random
from collections import Counter
from dataclasses import dataclass

COUNTS = Counter()


def words(n):
    return [''.join(x) for x in itertools.product('01', repeat=n)]


def tree(support):
    support = frozenset(support)
    assert support
    if len(support) == 1:
        return support, None, None
    width = len(next(iter(support)))
    split = next(i for i in range(width) if len({x[i] for x in support}) == 2)
    a = tree(x for x in support if x[split] == '0')
    b = tree(x for x in support if x[split] == '1')
    return support, a, b


def view(t, row):
    here = t[0] & row
    if not here:
        return 0
    if here == t[0]:
        return 1
    return (view(t[1], here), view(t[2], here))


def mixed(v):
    return 0 if isinstance(v, int) else 1 + mixed(v[0]) + mixed(v[1])


def oracle_mixed(support, row):
    # Count literal branch coordinates directly; no compressed tree traversal.
    if not support:
        return 0
    n = len(next(iter(support)))
    prefixes = {x[:i] for x in support for i in range(n)}
    count = 0
    for p in prefixes:
        under = {x for x in support if x.startswith(p)}
        children = {x[len(p)] for x in under}
        count += len(children) == 2 and bool(under & row) and bool(under - row)
    return count


def merge(a, b):
    if b == 0 or a == 1:
        return a, 1
    if b == 1 or a == 0:
        return b, 1
    x, cx = merge(a[0], b[0])
    y, cy = merge(a[1], b[1])
    return (x if x == y and isinstance(x, int) else (x, y)), 1 + cx + cy


def decode(t, v):
    if v == 0:
        return frozenset()
    if v == 1:
        return t[0]
    return decode(t[1], v[0]) | decode(t[2], v[1])


@dataclass(frozen=True)
class Snapshot:
    supports: tuple
    rows: tuple

    def semantic(self):
        return dict(self.rows)


class Online:
    def __init__(self, k):
        self.k = k
        self.supports = []
        self.rows = {}
        self.active = None
        self.owner = None
        self.last_alias = None
        self.rejected = False

    def record(self, alias, target):
        if self.rejected:
            return
        if alias != self.last_alias:
            self.active = None
            self.owner = None
        self.last_alias = alias
        component = next((j for j, u in enumerate(self.supports) if target in u), None)
        if component is None:
            if self.active is None:
                if len(self.supports) == self.k:
                    self.rejected = True
                    return
                self.active = len(self.supports)
                self.owner = alias
                self.supports.append(frozenset())
            assert self.owner == alias
            component = self.active
            self.supports[component] = self.supports[component] | {target}
        self.rows[alias] = self.rows.get(alias, frozenset()) | {target}
        if self.active is not None:
            # Only the owner can have received active-component targets.
            u = self.supports[self.active]
            assert u <= self.rows[self.owner]
            assert all(not (r & u) for a, r in self.rows.items() if a != self.owner)

    def snapshot(self):
        return Snapshot(tuple(self.supports), tuple(sorted(self.rows.items())))


def block_oracle(records, k):
    supports = []
    rows = {}
    for alias, block in itertools.groupby(records, key=lambda pair: pair[0]):
        targets = {target for _, target in block}
        old = set().union(*supports) if supports else set()
        novel = targets - old
        if novel:
            if len(supports) == k:
                return None
            supports.append(frozenset(novel))
        rows[alias] = rows.get(alias, frozenset()) | targets
    return tuple(supports), rows


def verify_snapshot(snap, expected):
    assert snap.semantic() == expected
    supports = snap.supports
    assert sum(map(len, supports)) == len(set().union(*supports)) if supports else True
    for alias, row in snap.rows:
        result = set()
        for u in supports:
            t = tree(u)
            v = view(t, row)
            assert mixed(v) == oracle_mixed(u, row)
            assert decode(t, v) == u & row
            result.update(decode(t, v))
            COUNTS['component_views'] += 1
        assert result == row
    COUNTS['snapshots'] += 1


def check_reuse(snap, rng, aliases, n):
    ts = [tree(u) for u in snap.supports]
    rows = snap.semantic()
    compiled = {a: tuple(view(t, r) for t in ts) for a, r in rows.items()}
    empty = tuple(0 for _ in ts)
    sources = ['0', '00', '1']
    committed = {s: empty for s in sources}
    pending = {s: empty for s in sources}
    ordinary = {s: frozenset() for s in sources}
    retained = []
    queries = words(n) + [''] + words(n + 1)
    for step in range(7):
        source = rng.choice(sources)
        alias = rng.choice(aliases)  # Ordinary fixed-width aliases, including absent rows.
        incoming = pending[source]
        results = [merge(a, b) for a, b in zip(committed[source], incoming)]
        calls = sum(c for _, c in results)
        assert calls <= len(ts) + 2 * sum(map(mixed, incoming))
        committed[source] = tuple(v for v, _ in results)
        pending[source] = compiled.get(alias, empty)
        ordinary[source] |= rows.get(alias, frozenset())
        retained.append((committed[source], pending[source], ordinary[source]))
        COUNTS['selections'] += 1
        COUNTS['merge_calls'] += calls
        for a, b, target_set in retained:
            for q in queries:
                # Exact literal membership validates suppressed unary paths.
                actual = any(q in t[0] and q in (decode(t, x) | decode(t, y))
                             for t, x, y in zip(ts, a, b))
                assert actual == (q in target_set)
                COUNTS['immediate_and_retained_queries'] += 1


def check_history(records, k, width, rng, reuse=False):
    online = Online(k)
    ordinary = {}
    snapshots = []
    for i, (a, x) in enumerate(records):
        online.record(a, x)
        oracle = block_oracle(records[:i + 1], k)
        assert online.rejected == (oracle is None)
        if online.rejected:
            COUNTS['component_limit_rejections'] += 1
            return
        ordinary[a] = ordinary.get(a, frozenset()) | {x}
        snap = online.snapshot()
        assert (snap.supports, snap.semantic()) == oracle
        snapshots.append((snap, dict(ordinary)))
        # Retained older meanings must survive later owner support growth.
        for old, old_meaning in snapshots:
            verify_snapshot(old, old_meaning)
    snap = online.snapshot()
    for c in (1, 2):
        direct = all(sum(oracle_mixed(u, r) for u in snap.supports) <= c * width
                     for r in ordinary.values())
        structural = all(sum(mixed(view(tree(u), r)) for u in snap.supports) <= c * width
                         for r in ordinary.values())
        assert structural == direct
        COUNTS['budget_acceptances' if direct else 'budget_rejections'] += 1
    if reuse:
        check_reuse(snap, rng, words(width), len(records[0][1]) if records else 2)
    COUNTS['accepted_histories'] += 1


def main():
    rng = random.Random(216)
    alphabet = list(itertools.product(words(1), words(2)))
    for length in range(5):
        for records in itertools.product(alphabet, repeat=length):
            for k in (1, 2, 3):
                check_history(records, k, 1, rng)
                COUNTS['exhaustive_histories'] += 1
    for _ in range(1200):
        n, width, k = rng.randint(1, 4), rng.randint(1, 3), rng.randint(1, 3)
        aliases, targets = words(width), words(n)
        records = [(rng.choice(aliases), rng.choice(targets))
                   for _ in range(rng.randint(1, 20))]
        check_history(records, k, width, rng, reuse=True)
        COUNTS['random_histories'] += 1
    # Same alias owns a later component; intervening records use only old support.
    cases = [
        [('00', '000'), ('01', '000'), ('00', '001'), ('00', '000')],
        [('0', '000'), ('0', '001'), ('1', '000'), ('1', '111'), ('1', '001')],
        [('0', '000'), ('0', '000'), ('1', '000')],
        [('0', '000'), ('1', '001'), ('0', '111')],
    ]
    for records in cases:
        for k in (1, 2, 3):
            check_history(records, k, len(records[0][0]), rng, reuse=True)
            COUNTS['targeted_histories'] += 1
    # One new support point leaves an old row unchanged but can inflate its
    # mixed-coordinate budget along every formerly FULL ancestor on the path.
    universe = words(3)
    for mask in range(1, (1 << len(universe)) - 1):
        u = {q for i, q in enumerate(universe) if mask >> i & 1}
        ul = sorted(u)
        for row_mask in range(1 << len(ul)):
            row = {q for i, q in enumerate(ul) if row_mask >> i & 1}
            for q in set(universe) - u:
                enlarged = u | {q}
                delta = 0
                for i in range(3):
                    p = q[:i]
                    old_under = {x for x in u if x.startswith(p)}
                    now_under = old_under | {q}
                    is_branch = len({x[i] for x in now_under}) == 2
                    old_branch = len({x[i] for x in old_under}) == 2
                    delta += is_branch and (bool(old_under) and old_under <= row
                                            if old_branch else bool(old_under & row))
                assert oracle_mixed(enlarged, row) - oracle_mixed(u, row) == delta
                COUNTS['one_point_growth_checks'] += 1
    for d in range(1, 10):
        # Comb support: all old ancestors on the distinguished leaf are FULL.
        q = '0' * (d + 1)
        u = {'0' * i + '1' + '0' * (d - i) for i in range(d + 1)}
        assert oracle_mixed(u, u) == 0
        assert oracle_mixed(u | {q}, u) == d + 1
        COUNTS['linear_budget_inflation_stresses'] += 1
    print(json.dumps({'seed': 216, 'counts': dict(sorted(COUNTS.items())),
        'scope': 'All histories of length 0..4 over two one-bit aliases and four two-bit targets, K=1..3; 1200 seeded histories; targeted leading-zero and reused-owner cases.',
        'limits': 'Host semantic audit, not a native-machine implementation or proof of deadlines, allocation, pointer routing, compiler interfaces, or unbounded correctness.'}, indent=2))


if __name__ == '__main__':
    main()