check_selector_shadow.py

"""Finite audit of tree-shaped eager shadows, not a native time model.

Each immutable terminal owns a direct payload. Updating class c repairs ALL its
terminal aliases and their ancestors; untouched nodes must remain shared.
A separate suffix index demonstrates the quotient escape for the same family.
"""
from dataclasses import dataclass
from itertools import product

@dataclass(frozen=True, eq=False)
class Node:
    left: object = None
    right: object = None
    value: object = None


def build(depth, classify, prefix=''):
    if not depth:
        return Node(value=(classify(prefix), 0))
    return Node(build(depth-1, classify, prefix+'0'),
                build(depth-1, classify, prefix+'1'))


def update(t, c, v):
    if t.value is not None:
        return (Node(value=(c, v)), 1) if t.value[0] == c else (t, 0)
    l, a = update(t.left, c, v)
    r, b = update(t.right, c, v)
    return (Node(l, r), a+b+1) if a+b else (t, 0)


def read(t, bits):
    for b in bits:
        t = t.left if b == '0' else t.right
    return t.value


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


def oracle_closure(all_words, classify, c):
    return {w[:j] for w in all_words if classify(w) == c
            for j in range(len(w)+1)}


def run():
    stats = dict(updates=0, snapshot_reads=0, closure_nodes=0,
                 suffix_reads=0, families=0)
    for k in range(1, 6):
        ws, cs = words(2*k), words(k)
        f = lambda w: w[-k:]
        root = build(2*k, f)
        suffix = build(k, lambda w: w)
        values = {c: 0 for c in cs}
        snapshots = [(root, suffix, values.copy())]
        for step, c in enumerate(cs + list(reversed(cs)), 1):
            root, cost = update(root, c, step)
            suffix, small_cost = update(suffix, c, step)
            assert cost == len(oracle_closure(ws, f, c))
            assert cost == (k+2)*2**k-1
            assert small_cost == k+1
            values[c] = step
            snapshots.append((root, suffix, values.copy()))
            stats['updates'] += 1
            stats['closure_nodes'] += cost
        for old, small, expected in snapshots:
            for w in ws:
                assert read(old, w) == (f(w), expected[f(w)])
                assert read(small, w[-k:]) == read(old, w)
                stats['snapshot_reads'] += 1
                stats['suffix_reads'] += 1
        stats['families'] += 1
    # Exhaust all two-class labelings at depth three: exact ancestor closure
    # does not depend on a convenient structured example.
    ws = words(3)
    for labels in product(range(2), repeat=len(ws)):
        mapping = dict(zip(ws, labels))
        old = build(3, mapping.__getitem__)
        for c in range(2):
            new, cost = update(old, c, 7)
            assert cost == len(oracle_closure(ws, mapping.__getitem__, c))
            for w in ws:
                assert read(old, w) == (mapping[w], 0)
                assert read(new, w) == (mapping[w], 7 if mapping[w] == c else 0)
                stats['snapshot_reads'] += 1
            stats['updates'] += 1
            stats['closure_nodes'] += cost
    print(stats)

if __name__ == '__main__':
    run()