c7_independent_review.py

#!/usr/bin/env python3
"""Independent hostile checks for the two newest C7 compiler review units."""

from __future__ import annotations

import json
from functools import lru_cache
from itertools import permutations

import c7_base_compiler as base
import c7_typed_language_compiler as dag


def enumerate_maximum_extensions(vertices, adjacency):
    """Enumerate maximum independent sets via maximum cliques in the complement."""
    n = len(vertices)
    universe = (1 << n) - 1
    complement = [universe & ~(adjacency[i] | (1 << i)) for i in range(n)]
    best = 0
    solutions: set[int] = set()
    nodes = 0

    def color_sort(mask):
        order = []
        colors = []
        remaining = mask
        color = 0
        while remaining:
            color += 1
            available = remaining
            while available:
                bit = available & -available
                v = bit.bit_length() - 1
                order.append(v)
                colors.append(color)
                remaining &= ~bit
                available &= ~bit
                available &= ~complement[v]
        return order, colors

    def expand(chosen, candidates):
        nonlocal best, solutions, nodes
        nodes += 1
        if not candidates:
            size = chosen.bit_count()
            if size > best:
                best = size
                solutions = {chosen}
            elif size == best:
                solutions.add(chosen)
            return
        order, colors = color_sort(candidates)
        while order:
            if chosen.bit_count() + colors[-1] < best:
                return
            v = order.pop()
            colors.pop()
            bit = 1 << v
            expand(chosen | bit, candidates & complement[v])
            candidates &= ~bit

    expand(0, universe)
    decoded = [
        {vertices[i] for i in range(n) if mask >> i & 1}
        for mask in sorted(solutions)
    ]
    return best, decoded, nodes


def finite_language_profile(code, order):
    words = {tuple(word[i] for i in order) for word in code}
    length = len(next(iter(words)))
    counts = []
    transitions = 0
    for depth in range(length + 1):
        grouped = {}
        for word in words:
            grouped.setdefault(word[:depth], set()).add(word[depth:])
        residuals = {frozenset(suffixes) for suffixes in grouped.values()}
        counts.append(len(residuals))
        if depth < length:
            transitions += sum(len({suffix[0] for suffix in residual}) for residual in residuals)
    return tuple(counts), sum(counts), transitions


def residual_families(code, depth):
    grouped = {}
    for word in code:
        grouped.setdefault(word[:depth], set()).add(word[depth:])
    return {frozenset(suffixes) for suffixes in grouped.values()}


def typed_sets():
    core, _ = base.circular_core()
    vertices, adjacency = base.extension_graph(core)
    patch, _, _ = base.typed_patch(core, vertices, adjacency)
    code = core | patch
    centers = {x for x, _ in base.PAIRS}
    alternatives = {y for _, y in base.PAIRS}
    ph = {base.PAIRS[i][0] if i in base.J0 else base.PAIRS[i][1] for i in range(8)}
    pv = {base.PAIRS[i][1] if i in base.J0 else base.PAIRS[i][0] for i in range(8)}
    companion = {base.transform_t(word) for word in code}
    companion.remove(base.OLD_COMPANION_POINT)
    companion.add(base.NEW_COMPANION_POINT)

    def category(point):
        hit_h = any(base.closed_confusable(point, endpoint) for endpoint in ph)
        hit_v = any(base.closed_confusable(point, endpoint) for endpoint in pv)
        assert not (hit_h and hit_v)
        return "H" if hit_h else "V" if hit_v else "O"

    return {
        "I": code,
        "B": code - centers,
        "R": centers,
        "Q": alternatives,
        "PH": ph,
        "PV": pv,
        "X": companion,
        "O": {word for word in companion if category(word) == "O"},
        "H": {word for word in companion if category(word) == "H"},
        "V": {word for word in companion if category(word) == "V"},
    }


def concatenate(left, right):
    return {a + b for a in left for b in right}


def explicit_two_block_code(sets):
    terms = [
        concatenate(sets["B"], sets["B"]),
        concatenate(sets["R"], sets["O"]),
        concatenate(sets["PH"], sets["H"]),
        concatenate(sets["PV"], sets["V"]),
        concatenate(sets["O"], sets["R"]),
        concatenate(sets["H"], sets["PV"]),
        concatenate(sets["V"], sets["PH"]),
    ]
    assert sum(map(len, terms)) == len(set().union(*terms))
    return set().union(*terms)


def main():
    core, _ = base.circular_core()
    vertices, adjacency = base.extension_graph(core)
    maximum, patches, search_nodes = enumerate_maximum_extensions(vertices, adjacency)
    assert maximum == 40
    assert len(patches) == 8

    profiles = []
    for patch in patches:
        code = core | patch
        best = min(
            (finite_language_profile(code, order)[1], order, finite_language_profile(code, order))
            for order in permutations(range(5))
        )
        profiles.append((base.canonical_hash(code), best))
    minima = sorted(profile[1][0] for profile in profiles)
    assert minima == [128, 129, 129, 129, 130, 130, 130, 132]

    _, _, typed_profile = base.typed_patch(core, vertices, adjacency)
    assert typed_profile == {"O": 321, "H": 26, "V": 20}
    published_hash = "a8d96cb1593aa03058e781c819a5254895ccae4dfc05f35a4ef3e89e6566c9e4"
    published = next(profile for profile in profiles if profile[0] == published_hash)
    assert published[1][0] == 128
    assert published[1][2] == ((1, 7, 49, 61, 9, 1), 128, 424)

    sets = typed_sets()
    direct = explicit_two_block_code(sets)
    assert len(direct) == 134_753
    direct_profile = finite_language_profile(direct, tuple(range(10)))

    factory = dag.Factory()
    package, _ = dag.base_package(factory)
    product = dag.product_package(factory, package, package)
    symbolic = dag.reachable_residuals(factory, product["I"], 10, 500_000)

    # The syntax compiler deliberately performs only canonical syntactic
    # reductions. At depth eight, 107 syntax states denote 93 distinct left
    # quotients. This is the first hostile boundary between compiler size and
    # minimal-DFA size.
    layers = [{product["I"]}]
    for _ in range(8):
        layers.append({
            factory.derivative(state, letter)
            for state in layers[-1]
            for letter in dag.ALPHABET
            if factory.derivative(state, letter) != factory.zero
        })

    @lru_cache(maxsize=None)
    def denote(expression):
        node = factory.nodes[expression]
        if node.kind == "zero":
            return frozenset()
        if node.kind == "eps":
            return frozenset({()})
        if node.kind == "leaf":
            return node.data
        if node.kind == "union":
            return frozenset().union(*(denote(child) for child in node.data))
        if node.kind == "concat":
            result = {()}
            for child in node.data:
                result = {left + right for left in result for right in denote(child)}
            return frozenset(result)
        raise AssertionError(node.kind)

    symbolic_depth8_languages = {denote(state) for state in layers[8]}
    explicit_depth8_languages = residual_families(direct, 8)
    assert symbolic_depth8_languages == explicit_depth8_languages
    assert len(layers[8]) == 107
    assert len(symbolic_depth8_languages) == 93
    assert direct_profile == ((1, 7, 49, 300, 71, 9, 49, 176, 93, 10, 1), 766, 2367)
    assert tuple(symbolic["layer_counts"]) == (1, 7, 49, 300, 71, 9, 49, 176, 107, 10, 1)
    assert symbolic["useful_states_seen"] == 780
    assert symbolic["transitions_seen"] == 2_395

    print(json.dumps({
        "maximum_extension_size": maximum,
        "maximum_extension_count": len(patches),
        "maximum_search_nodes": search_nodes,
        "coordinate_order_profiles_checked": len(patches) * 120,
        "extension_minimal_state_multiset": minima,
        "published_profile": published[1][2],
        "two_block_words": len(direct),
        "two_block_minimal_profile": direct_profile,
        "two_block_symbolic_profile": symbolic,
        "depth8_symbolic_states": len(layers[8]),
        "depth8_distinct_left_quotients": len(symbolic_depth8_languages),
        "symbolic_language_matches_explicit": True,
    }, indent=2, sort_keys=True))


if __name__ == "__main__":
    main()