check_finite_image_composition.py

"""Finite semantic corroboration; tuple FIFO timings are not native evidence."""
from itertools import product
import json
import random
from check_frozen_row_composition import B, descend, close, lookup, view


def add_right(palette, rows, used, v, w, limit):
    outer = descend(rows, v)
    inner = descend(palette, w)
    slot = view(inner[1])[0]
    if slot is None:
        if used == limit:
            return None
        slot, used = used, used + 1
        palette = close(inner, slot)
    return palette, close(outer, (view(outer[1])[0] or 0) | (1 << slot)), used


def add_left(rows, frozen, u, v):
    outer = descend(rows, u)
    return close(outer, (view(outer[1])[0] or 0) | (lookup(frozen, v) or 0))


def answer(palette, rows, a, b):
    slot = lookup(palette, b)
    return slot is None or not ((lookup(rows, a) or 0) & (1 << slot))


def main():
    names = ['0', '00']
    edges = list(product(names, repeat=2))
    rels = [{e for i, e in enumerate(edges) if mask >> i & 1} for mask in range(16)]
    exhaustive = 0
    for s in rels:
        for r in rels:
            for limit in [1, 2]:
                state = (B, B, 0)
                for v, w in sorted(s):
                    state = add_right(*state, v, w, limit)
                    if state is None:
                        break
                assert (state is None) == (len({w for _, w in s}) > limit)
                if state is None:
                    continue
                palette, frozen, _ = state
                rows = B
                for u, v in sorted(r):
                    rows = add_left(rows, frozen, u, v)
                for a, b in product(names + ['1'], repeat=2):
                    assert answer(palette, rows, a, b) == (not any((a, v) in r and (v, b) in s for v in names))
                    exhaustive += 1
    rng = random.Random(124)
    names = ['0', '00', '1', '01', '1' * 257]
    queries = versions = 0
    for trial in range(40):
        palette, frozen, used = B, B, 0
        rotated = names[trial % len(names):] + names[:trial % len(names)]
        targets = rotated[:(trial % 3) + 1]
        s = set()
        for _ in range(12):
            v, w = rng.choice(names), rng.choice(targets)
            palette, frozen, used = add_right(palette, frozen, used, v, w, 3)
            s.add((v, w))
        previous = s
        snapshots = []
        for depth in range(4):
            rows, relation = B, set()
            for _ in range(12):
                u, v = rng.choice(names), rng.choice(names)
                rows = add_left(rows, frozen, u, v)
                relation.add((u, v))
                expected = {(a, b) for a, mid in relation for k, b in previous if k == mid}
                snapshots.append((rows, expected.copy()))
                versions += 1
            frozen, previous = rows, expected
        for root, expected in snapshots:
            for a, b in product(names + ['1110'], repeat=2):
                assert answer(palette, root, a, b) == ((a, b) not in expected)
                queries += 1
    # An empty factor must erase all contributions, including at later phases.
    assert all(answer(palette, B, a, b) for a, b in product(names, repeat=2))
    print(json.dumps({'status':'pass', 'exhaustive_queries':exhaustive,
                      'retained_versions':versions, 'retained_multifactor_queries':queries,
                      'overflow_checked':True, 'empty_factor_checked':True}))

if __name__ == '__main__':
    main()