check_hybrid_composition.py

"""Assessment129: finite transactional semantics, not native timing evidence."""
from itertools import product, permutations
import json
import check_prefix_decoding as p
import check_pending_substitution as n
from check_frozen_row_composition import B, lookup, insert


def provisional(joint, counts, v, w, k, clock):
    j, q = ((), joint), ((), counts)
    queue, state, bad = tuple(v), False, False
    for bit in w:
        state, emit = p.tick(state, bit, clock)
        label = 'E'
        if emit:
            label = queue[0] if queue else 'P'
            queue = queue[1:]
        for c in p.code(bit, label):
            j = p.step(j, c)
        old = p.view(j[1])[0] or (False, False)
        j = p.setvalue(j, (True, old[1]))
        q = p.step(q, bit)
        count = min(k + 1, (p.view(q[1])[0] or 0) + (not old[0]))
        bad |= count > k
        q = p.setvalue(q, count)
    bad |= bool(queue)
    j = p.setvalue(j, (True, True))
    return p.finish(j), p.finish(q), bad


def prepare(pairs, d=1, s=0, k=1, clock='all'):
    near = joint = counts = B
    for v, w in pairs:
        # Both alternatives start from committed roots. Classification is late.
        candidate = n.add_right(near, v, w, d, s)
        jj, cc, bad = provisional(joint, counts, v, w, k, clock)
        if abs(n.cls(v) - n.cls(w)) <= s:
            if candidate is None:
                return None
            near = candidate
        else:
            if bad:
                return None
            joint, counts = jj, cc
    return near, joint, counts


def valid(pairs, d, s, k, clock):
    rows, far = {}, []
    for v, w in set(pairs):
        if abs(n.cls(v) - n.cls(w)) <= s:
            rows.setdefault(v, set()).add(w)
        else:
            far.append((v, w))
    width = p.oracle(far, clock)
    return all(len(row) <= d for row in rows.values()) and width is not None and max(width.values(), default=0) <= k


def audit(pairs, probes, d=1, s=0, k=1, clock='all'):
    packed = prepare(pairs, d, s, k, clock)
    assert (packed is not None) == valid(pairs, d, s, k, clock)
    if packed is None:
        return 0, 0
    frozen, joint, counts = packed
    far = [(v,w) for v,w in pairs if abs(n.cls(v)-n.cls(w)) > s]
    for prefix, count in p.oracle(far, clock).items():
        assert lookup(counts, prefix) == count
    names = sorted({v for v,w in pairs})
    near_rows = direct_rows = B
    snapshots = [(near_rows, direct_rows, set())]
    marked = set()
    for i, v in enumerate(names + names[:1]):
        u = str(i % 2)
        near_rows = n.add_left(near_rows, frozen, u, v, d, s)
        row = lookup(direct_rows, u) or B
        direct_rows = insert(direct_rows, u, insert(row, v, True))
        marked = marked | {(u, v)}
        snapshots.append((near_rows, direct_rows, marked))
    comparisons = 0
    for oldnear, olddirect, oldmarks in snapshots:
        for u in ('0','1','00'):
            index = lookup(oldnear, u) or {}
            row = lookup(olddirect, u) or B
            for w in probes:
                got = n.index_contains(index, w) or p.query(joint, row, w, k, clock)
                want = any((u,v) in oldmarks and ww == w for v,ww in pairs)
                assert got == want, (pairs, u, w, oldmarks)
                comparisons += 1
    return len(snapshots), comparisons


def main():
    # Includes ignored near width overflow, far near-degree overflow, contraction,
    # duplicate rows, late class choice, and invalid far source exhaustion.
    edges = [('0','0'),('1','0'),('0','1'),('0','0000'),('1','0000'),
             ('0','1000'),('00','0'),('00','01'),('00','0000'),('01','1000')]
    probes = ['0','1','00','01','0000','1000','000','1111']
    cases = versions = queries = 0
    for mask in range(1 << len(edges)):
        pairs = [e for i,e in enumerate(edges) if mask >> i & 1]
        for d,k in ((1,1),(2,1),(1,2)):
            for ordered in (pairs, list(reversed(pairs))):
                vv, qq = audit(ordered + ordered[:1], probes, d=d, k=k)
                cases += 1; versions += vv; queries += qq
    # A near contraction can violate the far length test and must still commit.
    for pairs in ([('000','00')], [('0','0'),('1','0')],
                  [('0','0'),('0','0000'),('0','1000')]):
        vv,qq = audit(pairs, probes + ['00']); cases += 1; versions += vv; queries += qq
    # Non-ticking clock and far rejection are checked independently.
    for pairs in ([('0','00010'),('1','00011'),('0','1')], [('00','0000')]):
        vv,qq = audit(pairs, probes+['00010','00011'], clock='skip'); cases += 1; versions += vv; queries += qq
    # Functional family: near reversal and far expansion in disjoint name lanes.
    mixtures = []
    for h in range(2,7):
        bits = [''.join(x) for x in product('01', repeat=h)]
        pairs = [('0'+x, '0'+x[::-1]) for x in bits]
        pairs += [('1'+x, '1'+x+'0'*(8*h*h)) for x in bits]
        assert len({v for v,w in pairs}) == len(pairs)
        assert prepare(pairs) is not None
        width = max(p.oracle(pairs, 'all').values())
        span = max(abs(n.cls(v)-n.cls(w)) for v,w in pairs)
        assert width >= 2**(h//2) and span > 0
        # Sparse query set, every retained version: both alternatives and misses.
        vv,qq = audit(pairs, [pairs[0][1], pairs[-1][1], '111'])
        versions += vv; queries += qq
        mixtures.append({'h':h,'whole_width':width,'whole_class_span':span})
    print(json.dumps({'contract_cases':cases,'retained_versions':versions,
                      'queries':queries,'functional_mixtures':mixtures,
                      'native_timing_evidence':False}, indent=2))

if __name__ == '__main__':
    main()