#!/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()