mirror/BFM-decomp
1
0
Fork 0
mirror of https://github.com/Druthulu/BFM-decomp synced 2026-10-01 07:40:42 -04:00
Code Issues Packages Projects Releases Wiki Activity
Files
main
BFM-decomp/tools/delever_search.py
T

1077 lines
62 KiB
Python
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
#!/usr/bin/env python3
"""delever_search.py — rung G of the lever ladder: the GUIDED search for a lever-free body (Phase 36, S101).
tools/delever_search.py --plan [--limit N] [--only X ...] [--score] # the residue's exemplars; --score = their starting distance
tools/delever_search.py --run [--limit K] [--only X ...] [-j W] [--beam B] [--depth D] [--cap C] [--budget M] [--label gN]
tools/delever_search.py --positive-control TU FN [--moves 1|2] # perturb a MATCHING body, require the search to return to 0
tools/delever_search.py --try TU FN FILE [--body] # score a candidate WITHOUT writing the tree (an agent's loop)
tools/delever_search.py --status
tools/delever_search.py --selftest
WHY. Rung R (`delever --recipes`) is BLIND: it generates ~57 one-move candidates per body, asks the oracle "IDENTICAL?" and throws
everything else away — 134 of 134 on a class whose shape rung D had just found, 0 of 300 where no shape was known (S100, cookbook
§454a): a replication engine, not a discovery engine. Rung D (decomp-permuter) discovers, but as a random walk that reprints the
source. This engine sits between them: the SAME candidate generators, the SAME oracle, but every candidate is SCORED by its masked
mismatch count against the target, the residual is CLASSIFIED to choose the move families, and the search hill-climbs — two- and
three-move compositions guided by the gradient — instead of guessing once.
THE SCORER IS THE ORACLE'S OWN OBJECT. A candidate TU text is compiled through the recipe of ONE object (a header: its first
includer's), the function's instructions are read out of that scratch object (`objdump -drz`, 35 ms on the largest overlay object)
and compared, relocation-masked with reloc-operand equality (`masked_diff.diff_object_object`), with the same function in the fleet
run's baseline object under `build/`. That target is the tree's own bytes — proven by the SHA1 check, carrying the candidates'
relocations by construction — so no listing is assembled, no TU isolated, no cpp expanded (the two instrument classes that cost rung D
two campaigns, §454). Whole-object equality on EVERY recipe of the TU stays the bank verdict (`delever --apply-body`), and the clean
fleet run (R22) gates the batch as it gates every batch of this phase.
THE SEARCH. Beam `B` (3), depth `D` (3), per-node cap `C` (48), budget `M` compiles (400). Node = a TU text with its score and the
move path that made it. Children are generated by the families the residual's class selects (REG on the caller-saved bank → the
commutative swap, the temp inlined/introduced, the initializer split; REG on the callee-saved bank → declaration order/move first;
COUNT → the temp moves; ORDER → the block wrap and the adjacent swap), ranked by score; a child worse than its parent is dropped, a
child with the parent's score and the parent's diff signature (a no-effect move) goes to the tail. The first score-0 child is
verified on every recipe and banked; siblings of its text class are then given the same shape by `delever --propagate`, serially,
after the parallel phase (a sibling lives in a TU another worker may own).
THE CONTROLS (R39/R40/R56), before a yield is believed: every body starts by scoring the tree's OWN text — it must score 0 and be
byte-identical, or the harness is not measuring this function (UNCALIBRATED, recorded); `--positive-control` perturbs a lever-free
MATCHING body by one or two generator moves, requires the perturbed text to score > 0, and requires the search to find its way back to
0 without ever writing the tree; `--selftest` runs the classifier on synthetic instruction streams and the beam on a stub scorer whose
answer needs three composed moves. The evidence of every attempt is `.run/P36/engine/outcomes.jsonl` and a per-body trace under
`.run/P36/engine/trace/` (every scored candidate: the move, the parent's score, its score, its class) — the byte record lane B's
compiler-source hypotheses are checked against.
NEVER RUN A LONG CAMPAIGN AS A HARNESS BACKGROUND TASK (the low-memory guard kills it): `setsid nohup nice -n 10 … &` + a Monitor.
A worker owns a whole translation unit (the oracle writes candidates into the real source path); headers run serially after the TUs.
`pkill -f` never with a literal your own command line contains (R79).
"""
import argparse
import collections
import difflib
import json
import os
import pathlib
import random
import re
import subprocess
import sys
import threading
import time
from concurrent.futures import ThreadPoolExecutor
REPO = pathlib.Path(__file__).resolve().parent.parent
sys.path.insert(0, str(REPO / "tools"))
import delever as dl # noqa: E402
import delever_oracle as oracle # noqa: E402
import lever_census as lc # noqa: E402
import masked_diff as md # noqa: E402
import share_census as sc # noqa: E402
RUN = REPO / ".run" / "P36" / "engine"
OUTCOMES = RUN / "outcomes.jsonl"
TRACE = RUN / "trace"
OBJ = RUN / "obj"
PY = str(REPO / ".venv" / "bin" / "python")
_LOCK = threading.Lock()
REGNAME = {0: "zero", 1: "at", 2: "v0", 3: "v1", 4: "a0", 5: "a1", 6: "a2", 7: "a3", 8: "t0", 9: "t1", 10: "t2", 11: "t3",
12: "t4", 13: "t5", 14: "t6", 15: "t7", 16: "s0", 17: "s1", 18: "s2", 19: "s3", 20: "s4", 21: "s5", 22: "s6",
23: "s7", 24: "t8", 25: "t9", 26: "k0", 27: "k1", 28: "gp", 29: "sp", 30: "fp", 31: "ra"}
CALLEE = set(range(16, 24)) | {30}
CALLER = set(range(2, 16)) | {24, 25}
# the move families per residual class, in trial order (the first is the one the class's byte-proven exemplar closed on).
# R19 leads EVERY class since S102: it is the only family that can change a call's arity, it emits a handful of
# candidates and only for calls whose declaration provably disagrees with the callee's definition, and six independent
# agent cracks say it is the largest single class in the residue. It costs nothing when it does not apply.
FAMILIES = {
# lane B's map (`.run/P36/engine/residual_moves.md`, S101, gcc 2.7.2 source): the caller-saved swap is decided in
# local-alloc's block_alloc/combine_regs by which dying pseudo the operand ties to — the temp inlined/introduced first; a
# constant-operand commutative swap is undone by fold (fold-const.c) and only a var/var swap can reach the allocator.
# R15 (the sink) is the arm-scoped form of the same tie: a value set in every arm of an if/else chain is a CROSS-BLOCK
# pseudo local-alloc never gives a quantity, so the arm holds two quantities and takes block_alloc's unrolled case 2;
# sinking makes it three, and case 3 falls through into case 2 and undoes its own exchange (T7 agent a1, func_80156044).
"REG-caller": ("R19", "R25", "R26", "R23", "R24", "R21", "R6", "R20", "R16", "R8", "R15", "R17", "R5", "R18", "R10", "R12", "R14", "R13", "R3", "R7", "R9", "R2", "R4", "R22", "R44", "R45", "R46"),
# the s-bank order is global.c's allocno_compare (ref weight x live length), declaration order only on an exact tie
"REG-callee": ("R19", "R25", "R26", "R23", "R24", "R21", "R20", "R2", "R4", "R3", "R6", "R16", "R8", "R15", "R18", "R12", "R7", "R9", "R17", "R10", "R14", "R13", "R5", "R22", "R44", "R45", "R46"),
"REG-mixed": ("R19", "R25", "R26", "R23", "R24", "R21", "R6", "R20", "R16", "R2", "R15", "R17", "R18", "R5", "R10", "R4", "R3", "R8", "R12", "R13", "R14", "R7", "R9", "R22", "R44", "R45", "R46"),
# a copy dies to cse's canon_reg or the local-alloc tie unless its destination changes MODE (the width); an address
# pseudo lives when a pointer local is used twice; a value named once is computed once; a short PARAMETER is extended in place
"COUNT": ("R19", "R25", "R26", "R22", "R44", "R45", "R21", "R20", "R12", "R16", "R14", "R15", "R6", "R8", "R3", "R18", "R7", "R17", "R5", "R13", "R9", "R10", "R2", "R4", "R23", "R24", "R46"),
# statement order IS the schedule among equal-priority insns (rank_for_schedule's LUID tie-break); do-while is a barrier
# R17 is the DIRECTED form of the run-split R9 reaches only by luck: agent a2 measured 2,271 compiles for R9 to find it
# in func_80168828 and R16+R17 reproduce the same close in ten.
"ORDER": ("R19", "R25", "R46", "R17", "R18", "R20", "R21", "R9", "R7", "R13", "R3", "R16", "R6", "R8", "R5", "R12", "R14", "R10", "R15", "R2", "R4", "R22", "R23", "R24", "R26", "R44", "R45"),
"MIXED": dl.ALL_FAMILIES,
"OTHER": dl.ALL_FAMILIES,
}
class Unstrippable(Exception):
pass
# ----------------------------------------------------------------------------------------------------------------------
# the residual's class, from two instruction streams
# ----------------------------------------------------------------------------------------------------------------------
def shape(i):
"""the instruction with its register fields zeroed (a reloc-masked immediate too) — two words of one shape differ only
in which registers they name."""
w, kind = i["word"], i["reloc_kind"]
op = w >> 26
if op == 0:
return ("R", w & 63, (w >> 6) & 31)
if op in (2, 3):
return ("J", op, i.get("reloc_op") or "")
if op == 18: # cop2: rs = the sub-op, rt = the CPU register, the rest cop fields
return ("C", w & ~(31 << 16))
return ("I", op, (w & 0xFFFF) if kind is None else ("rel", i.get("reloc_op") or ""))
def regs_of(i):
w = i["word"]
op = w >> 26
if op == 0:
return ((w >> 21) & 31, (w >> 16) & 31, (w >> 11) & 31)
if op in (2, 3):
return ()
if op == 18:
return ((w >> 16) & 31,)
return ((w >> 21) & 31, (w >> 16) & 31)
def masked_word(i):
"""the comparable form of one instruction: the reloc-masked word, the reloc operand (symbol+addend) and an internal `j`'s
target — equality of two streams of these ⟺ masked_diff.diff_object_object == 0 (the same rule, R33)."""
return (i["word"] & md.mask_for(i["word"], i["reloc_kind"]), i.get("reloc_op") or "", i.get("jrel"))
def classify(mine, tgt):
"""dict(kind, bank, score, n_mine, n_tgt, positions, pairs) — kind in REG | COUNT | ORDER | MIXED | OTHER | IDENTICAL;
bank (REG only) in caller | callee | mixed, from the register pairs that differ.
THE SCORE IS AN EDIT DISTANCE, NOT A POSITIONAL COUNT. The positional mismatch count (`match_one`'s closeness) reads a
one-instruction shift as "everything after it" — the two-move positive control at S101 read 43 for one inlined temp — so a
hill-climb on it cannot see that a candidate moved the residual from 43 shifted words to 2 real ones. difflib's opcodes over
the masked words give the real delta (insertions, deletions, replaced blocks); a replace block whose words keep their shape
(opcode, immediate, function code) and change only their register fields is the REG class."""
a, b = [masked_word(i) for i in mine], [masked_word(i) for i in tgt]
if a == b:
return dict(kind="IDENTICAL", bank=None, score=0, n_mine=len(mine), n_tgt=len(tgt), positions=[], pairs=[])
ops = [op for op in difflib.SequenceMatcher(None, a, b, autojunk=False).get_opcodes() if op[0] != "equal"]
score = sum(max(i2 - i1, j2 - j1) for _, i1, i2, j1, j2 in ops)
pos = [i for _, i1, i2, _, _ in ops for i in range(i1, max(i2, i1 + 1))]
pairs = collections.Counter()
count = any(t in ("insert", "delete") or (i2 - i1) != (j2 - j1) for t, i1, i2, j1, j2 in ops)
n_rep = n_reg = 0
for t, i1, i2, j1, j2 in ops:
if t != "replace" or (i2 - i1) != (j2 - j1):
continue
for k in range(i2 - i1):
n_rep += 1
if shape(mine[i1 + k]) == shape(tgt[j1 + k]):
n_reg += 1
for x, y in zip(regs_of(mine[i1 + k]), regs_of(tgt[j1 + k])):
if x != y:
pairs[(x, y)] += 1
if len(a) == len(b) and sorted(a) == sorted(b):
kind = "ORDER" # a pure reorder reads as delete+insert to difflib: test it first
elif count:
kind = "COUNT"
elif n_rep and n_reg == n_rep:
kind = "REG"
else:
kind = "MIXED" if n_reg else "OTHER"
regs = {x for x, _ in pairs} | {y for _, y in pairs}
bank = None
if kind == "REG":
callee, caller = bool(regs & CALLEE), bool(regs & CALLER)
bank = "mixed" if callee and caller else "callee" if callee else "caller"
return dict(kind=kind, bank=bank, score=score, n_mine=len(mine), n_tgt=len(tgt), positions=pos[:24],
pairs=[(REGNAME.get(x, x), REGNAME.get(y, y), n) for (x, y), n in pairs.most_common(8)])
def family_key(cls):
if cls["kind"] == "REG":
return f"REG-{cls['bank']}"
return cls["kind"] if cls["kind"] in FAMILIES else "OTHER"
def signature(cls):
"""what the diff looks like, independent of the text that produced it — two candidates with one signature moved nothing
relative to each other."""
return (cls["kind"], cls["n_mine"], tuple(cls["positions"]), tuple(cls["pairs"]))
# ----------------------------------------------------------------------------------------------------------------------
# the scorer: one compile through the oracle's recipe, the function's instructions against the baseline object's
# ----------------------------------------------------------------------------------------------------------------------
class Scorer:
def __init__(self, tu, fn, recs, tag, inflight):
if not recs:
raise Unstrippable([("<recipe>", 0, f"no recipe compiles {tu}")])
self.tu, self.fn, self.recs, self.tag = tu, fn, recs, tag
self.primary = recs[0]
self.header = tu.endswith(".h")
self.path = REPO / tu
self.inflight = inflight
base = oracle.baseline_path(self.primary["obj"]) # the snapshot when one exists: `make clean` must not wipe a live score
if not base.exists():
raise Unstrippable([("<baseline>", 0, f"{self.primary['obj']} missing — run the fleet build first (R56)")])
self.base_bytes = base.read_bytes()
dump = subprocess.run([md.OBJDUMP, "-drz", "-j", ".text", str(base)], capture_output=True, text=True).stdout
if f"<{fn}>:" not in dump:
raise Unstrippable([("<baseline>", 0, f"{fn} is not a label of {self.primary['obj']}")])
self.tgt = md.insns_from_object(str(base), fn)
self.compiles = 0
self.seconds = 0.0
OBJ.mkdir(parents=True, exist_ok=True)
# PER TU, not per tag (S101 run g4s): the tag was the TU's index modulo the worker count, not a worker id, so two
# TUs could share `g0.o` at the same moment and one worker objdumped the other's object — a byte-identical body read
# as 14,871 mismatches (UNCALIBRATED), and any candidate scored in that window was noise. A worker owns a whole TU,
# so a name keyed by the TU cannot collide. The bank was never at risk: it re-verifies whole-object equality itself.
self.scratch = OBJ / f"{tag}__{tu.replace('/', '_')}.o"
def score(self, text):
"""dict(score, ident, cls, seconds, err) — score None on a compile failure (R61: not judged is not a distance)."""
raw, st = self.path.read_text(errors="surrogateescape"), self.path.stat()
with _LOCK:
self.inflight[self.tu] = raw
dl.INFLIGHT.write_text(json.dumps(self.inflight))
try:
data, dt, err = oracle.compile_obj(self.primary, text, tag=self.tag, write_path=(self.tu if self.header else None))
finally:
dl.restore_file(self.path, raw, st)
with _LOCK:
self.inflight.pop(self.tu, None)
if self.inflight:
dl.INFLIGHT.write_text(json.dumps(self.inflight))
else:
dl.INFLIGHT.unlink(missing_ok=True)
self.compiles += 1
self.seconds += dt
if data is None:
return dict(score=None, ident=False, cls=None, seconds=dt,
err=("COMPILE-CRASH" if err.startswith("CRASH:") else "COMPILE-ERROR") + ": " + err[:120])
p = self.scratch
p.write_bytes(data)
mine = md.insns_from_object(str(p), self.fn)
cls = classify(mine, self.tgt)
return dict(score=cls["score"], ident=(data == self.base_bytes), cls=cls, seconds=dt, err="")
def verify_all(self, text):
"""the bank verdict: IDENTICAL on every recipe of the file (a twin's object; every includer of a header)."""
raw, st = self.path.read_text(errors="surrogateescape"), self.path.stat()
try:
return oracle.judge_all(self.recs, text, tag=self.tag + "v", write_path=(self.tu if self.header else None))
finally:
dl.restore_file(self.path, raw, st)
# ----------------------------------------------------------------------------------------------------------------------
# the population and the seed
# ----------------------------------------------------------------------------------------------------------------------
_sites = None
def sites_by_body():
global _sites
with _LOCK:
if _sites is None:
built = collections.defaultdict(list)
for s in dl.load_sites():
if s.get("fn"):
built[(s["tu"], s["fn"])].append(s)
_sites = built
return _sites
AB_KINDS = {"pin", "barrier", "launder", "keepalive", "instruction", "gte-lever", "asm-body"}
def lever_free_body(tu, raw, fn, sites):
"""the TU with every class A/B site of THIS body rewritten away (rung A's edits, nothing else — the file-scope asm and every
other body untouched, since the scorer compares whole objects too). A class C/D site the tree still carries (a byte-needed
`volatile` cast or bare `register`) STAYS: decision 3 keeps it as ordinary C, unmarked and ledgered, so the search starts
from the spelling the original plausibly had rather than paying to remove what the phase does not ask removed (S101: the
engine had been stripping a needed `volatile` cast and searching for a reload the cast already produced)."""
m, ls = dl.same_len_mask(raw), dl.line_starts(raw)
edits = []
for s in sites:
if s["cls"] not in "AB":
continue
if (s["cls"], s["kind"]) not in dl.REMOVABLE:
if s["kind"] in dl.DEFERRED_KINDS:
raise Unstrippable([(s["kind"], s["line"], "asm-body: T7's work")])
continue
try:
edits += dl.site_edits(raw, m, ls, s)
except dl.Refuse as ex:
raise Unstrippable([(s["kind"], s["line"], str(ex)[:120])])
if not edits:
return raw
try:
out = dl.apply_edits(raw, edits)
except dl.Refuse as ex:
raise Unstrippable([("<combination>", 0, str(ex)[:120])])
# R43 (S104 e24, func_80180E24): a deleted lever line that OPENED a multi-line comment left the comment's tail as code — the
# start text did not compile, and every sweep read the class as UNSCORED, never as refused. Refuse instead.
if out.count("/*") - out.count("*/") != raw.count("/*") - raw.count("*/"):
raise Unstrippable([("<comment>", 0, "a stripped lever line opened or closed a block comment")])
return out
def load_outcomes():
rows = []
if OUTCOMES.exists():
for l in OUTCOMES.read_text().splitlines():
if l.strip():
rows.append(json.loads(l))
return rows
def outcome_append(row):
RUN.mkdir(parents=True, exist_ok=True)
with _LOCK, open(OUTCOMES, "a") as f:
f.write(json.dumps(row) + "\n")
def matches(ex, only):
if not only:
return True
return any(o == ex["fn"] or o == ex["tu"] or o in ex["tu"] or (ex["nhash"] or "").startswith(o) or o == ex["alias"] for o in only)
def exemplars(only=(), limit=None, include_done=False):
"""one exemplar per RESIDUE text class of the delever ledger, largest class first, then fewest NEEDED sites."""
cur, order = {}, []
for r in dl.load_ledger():
k = (r.get("tu"), r.get("fn"))
if not k[0] or not k[1]:
continue
if k not in cur:
order.append(k)
cur[k] = r
groups = collections.OrderedDict()
nohash = 0
for k in order:
r = cur[k]
if r.get("verdict") != "RESIDUE" or r["fn"] == dl.FILE_SCOPE_FN:
continue
# THE PHASE'S NUMBER is pins + asm statements: a body whose only NEEDED sites are class C/D (a byte-needed `volatile`, a bare
# `register`) is done (decision 3) and is not drawn — the T4 close counted 498 such bodies, and g3 spent searches on them
if not any(s.get("verdict") == "NEEDED" and s.get("kind") in AB_KINDS for s in r.get("sites", [])):
continue
nh = r.get("nhash_after") or r.get("nhash_before")
if not nh:
nohash += 1
continue
groups.setdefault(nh, []).append((k, r))
if nohash:
sys.exit(f"delever_search: {nohash} RESIDUE row(s) carry no text hash — run `tools/delever.py --repair-nhash` first (R43)")
done = set() if include_done else {o["nhash"] for o in load_outcomes() if o.get("kind") == "attempt"}
out = []
for nh, members in groups.items():
if nh in done:
continue
(tu, fn), r = members[0]
needed = [s for s in r.get("sites", []) if s.get("verdict") == "NEEDED"]
out.append(dict(nhash=nh, tu=tu, fn=fn, alias=(r.get("aliases") or [None])[0], copies=len(members), needed=len(needed),
kinds=sorted({s["kind"] for s in needed}), regs=sorted({s.get("detail", "") for s in needed if s["kind"] == "pin"}),
members=[dict(tu=t, fn=f) for (t, f), _ in members], row=r))
out.sort(key=lambda e: (-e["copies"], e["needed"], e["tu"], e["fn"]))
out = [e for e in out if matches(e, only)]
return out[:limit] if limit else out
def recs_for(tu, by_src, inc):
return [r for t_ in inc.get(tu, []) for r in by_src.get(t_, [])] if tu.endswith(".h") else by_src.get(tu, [])
# ----------------------------------------------------------------------------------------------------------------------
# the search
# ----------------------------------------------------------------------------------------------------------------------
def body_span(text, tu, fn):
d_ = next((r for r in sc.scan_text(text, tu, shared_defs=None) if r["form"] == "def" and r["name"] == fn), None)
return d_
def rank(cands, fam_order, cls, d_):
"""ROUND-ROBIN across the families in the class's order, locality within a family. A strict family-first order starved
every later family under the cap: the S101 one-move control was perturbed by one R9 swap and its inverse sat behind 64
block-wrap candidates, so depth 1 never saw it and the search paid 142 compiles for a two-move detour. Within a family
the candidates nearest the residual go first (the changed block's index mapped onto the body's lines by fraction — a
tie-break, never the decider)."""
est = []
if cls and cls.get("positions") and d_ and cls["n_mine"]:
span = d_["end"] - d_["line"]
est = [d_["line"] + p / cls["n_mine"] * span for p in cls["positions"]]
def dist(item):
m = re.search(r"@(\d+)$", item[1])
return min((abs(int(m.group(1)) - e) for e in est), default=0) if m else 0
groups = collections.OrderedDict((f, []) for f in fam_order)
for c in cands:
groups.setdefault(c[0], []).append(c)
for g in groups.values():
g.sort(key=dist)
out = []
while any(groups.values()):
for g in groups.values():
if g:
out.append(g.pop(0))
return out
def search(seed, scorer_fn, gen_fn, beam=3, depth=3, cap=48, budget=400, trace=None, log=None):
"""the beam. scorer_fn(text) -> dict(score, ident, cls, err); gen_fn(text, cls) -> [(rec, desc, text)] ranked.
Returns dict(verdict, best, start, compiles, path, text, node_cls) — verdict MATCH | NO-MATCH | BUDGET | UNSCORED."""
s0 = scorer_fn(seed)
compiles = 1
if s0["score"] is None:
return dict(verdict="UNSCORED", best=None, start=None, compiles=compiles, path=[], text=seed, err=s0.get("err", ""))
if s0["score"] == 0 and s0["ident"]:
return dict(verdict="MATCH", best=0, start=0, compiles=compiles, path=[], text=seed, node_cls=s0["cls"])
frontier = [dict(text=seed, score=s0["score"], cls=s0["cls"], path=[])]
best = frontier[0]
seen = {seed}
for d in range(depth):
children = []
for parent in frontier:
psig = signature(parent["cls"])
cands = gen_fn(parent["text"], parent["cls"])[:cap]
for rec, desc, ctext in cands:
if ctext in seen:
continue
seen.add(ctext)
if compiles >= budget:
break
r = scorer_fn(ctext)
compiles += 1
row = dict(depth=d + 1, move=f"{rec} {desc}", parent=parent["score"], score=r["score"],
kind=(r["cls"]["kind"] if r["cls"] else r.get("err", "")[:14]), ident=r["ident"])
if trace is not None:
trace.append(row)
if r["score"] is None:
continue
child = dict(text=ctext, score=r["score"], cls=r["cls"], path=parent["path"] + [f"{rec} {desc}"],
noop=(r["score"] == parent["score"] and signature(r["cls"]) == psig))
if r["score"] == 0 and r["ident"]:
if log:
log(f" depth {d + 1}: score 0 by {' + '.join(child['path'])}")
return dict(verdict="MATCH", best=0, start=s0["score"], compiles=compiles, path=child["path"],
text=ctext, node_cls=r["cls"])
if r["score"] <= parent["score"]:
children.append(child)
if compiles >= budget:
break
if not children:
break
children.sort(key=lambda c: (c["score"], c["noop"]))
if children[0]["score"] < best["score"]:
best = children[0]
if log:
log(f" depth {d + 1}: {len(children)} kept of the scored, best {children[0]['score']} "
f"({' + '.join(children[0]['path'])}) · {compiles} compiles")
frontier = children[:beam]
if compiles >= budget:
return dict(verdict="BUDGET", best=best["score"], start=s0["score"], compiles=compiles, path=best["path"],
text=best["text"], node_cls=best["cls"])
return dict(verdict="NO-MATCH", best=best["score"], start=s0["score"], compiles=compiles, path=best["path"],
text=best["text"], node_cls=best["cls"])
def make_gen(tu, fn, names):
def gen(text, cls):
fam = FAMILIES[family_key(cls)] if cls else dl.ALL_FAMILIES
cands = dl.recipe_candidates(text, tu, fn, names, cap=None, families=fam)
return rank(cands, fam, cls, body_span(text, tu, fn))
return gen
# ----------------------------------------------------------------------------------------------------------------------
# one exemplar, end to end
# ----------------------------------------------------------------------------------------------------------------------
def run_body(ex, a, tag, by_src, inc, inflight, log):
tu, fn = ex["tu"], ex["fn"]
t0 = time.time()
row = dict(kind="attempt", ts=time.strftime("%Y-%m-%d %H:%M:%S"), label=a.label, nhash=ex["nhash"], tu=tu, fn=fn,
alias=ex["alias"], copies=ex["copies"], needed=ex["needed"], kinds=ex["kinds"], regs=ex.get("regs", []),
beam=a.beam, depth=a.depth, cap=a.cap, budget=a.budget)
sites = sites_by_body().get((tu, fn), [])
raw = (REPO / tu).read_text(errors="surrogateescape")
try:
if not sites:
raise Unstrippable([("<census>", 0, "no site in the census for this body (stale? rerun lever_census --sites)")])
free = lever_free_body(tu, raw, fn, sites)
scorer = Scorer(tu, fn, recs_for(tu, by_src, inc), tag, inflight)
except Unstrippable as u:
row.update(verdict="UNSTRIPPABLE", why=u.args[0][:4], seconds=round(time.time() - t0, 1))
outcome_append(row)
log(f" {ex['alias']}__{fn}: UNSTRIPPABLE — {u.args[0][:2]}")
return row
# THE CONTROL (R56): the tree's own text must score 0 AND be byte-identical, or this harness is not measuring this function
ctl = scorer.score(raw)
if ctl["score"] != 0 or not ctl["ident"]:
row.update(verdict="UNCALIBRATED", control=dict(score=ctl["score"], ident=ctl["ident"], err=ctl.get("err", "")),
seconds=round(time.time() - t0, 1))
outcome_append(row)
log(f" {ex['alias']}__{fn}: UNCALIBRATED — the tree's own text scores {ctl['score']} ident={ctl['ident']} {ctl.get('err', '')[:80]}")
return row
names = dl.pin_names(sites)
trace = []
res = search(free, scorer.score, make_gen(tu, fn, names), beam=a.beam, depth=a.depth, cap=a.cap, budget=a.budget,
trace=trace, log=log)
if res["verdict"] == "MATCH":
# the bank verdict: every recipe of the file, then the proven apply path (the ledger row with before/after text)
v, dt, err = scorer.verify_all(res["text"])
body = None
if v != "IDENTICAL":
res["verdict"] = "ONE-OBJECT-ONLY" # R34: the one-object score said 0, the file's other objects disagree
row["verify"] = f"{v} {err[:120]}"
else:
d_ = body_span(res["text"], tu, fn)
ls = dl.line_starts(res["text"])
body = res["text"][ls[d_["line"] - 1]:ls[d_["end"]]]
# THE BANK IS BODY-ONLY (apply_body_core splices the definition; --propagate remaps that body to siblings), so
# a candidate that also edited lines outside the definition verifies at 0 and can never be banked. Say so in
# its own words instead of letting the bank fail on `conflicting types` (S102 run s4, func_80136824: 288
# compiles to a real score 0, then a BANK-REFUSED that read like a bad body). R14 no longer generates these.
d0 = body_span(free, tu, fn)
l0 = dl.line_starts(free)
outside_now = res["text"][:ls[d_["line"] - 1]] + res["text"][ls[d_["end"]]:]
outside_before = free[:l0[d0["line"] - 1]] + free[l0[d0["end"]]:]
if outside_now != outside_before:
res["verdict"] = "OUT-OF-BODY"
row["verify"] = "the candidate edits lines outside the definition; the bank is body-only"
body = None
if res["verdict"] == "MATCH" and body is not None:
bf = RUN / "bodies" / f"{(ex['alias'] or 'x')}__{fn}.c"
bf.parent.mkdir(parents=True, exist_ok=True)
bf.write_text(body, errors="surrogateescape") # the record of what was handed to the bank
# IN PROCESS (S101): the bank used to be a subprocess that re-imported delever.py (an edit mid-run broke a bank)
# and reloaded the recipes/includers each time
with _LOCK: # the ledger append and the source write, one bank at a time
ok_, line = dl.apply_body_core(tu, fn, body, a.label, "G", source=bf.relative_to(REPO).as_posix())
row["banked"] = ok_
row["bank_line"] = line[:220]
if not ok_:
res["verdict"] = "BANK-REFUSED"
row.update(verdict=res["verdict"], start=res.get("start"), best=res.get("best"), compiles=res["compiles"],
path=res.get("path", []), start_cls=(trace and None) or None, seconds=round(time.time() - t0, 1),
oracle_seconds=round(scorer.seconds, 1))
if res.get("node_cls"):
row["best_cls"] = {k: v for k, v in res["node_cls"].items() if k != "positions"}
if trace:
TRACE.mkdir(parents=True, exist_ok=True)
with open(TRACE / f"{(ex['alias'] or 'x')}__{fn}.jsonl", "w") as f:
f.write(json.dumps(dict(kind="seed", start=res.get("start"), tu=tu, fn=fn, label=a.label)) + "\n")
for t in trace:
f.write(json.dumps(t) + "\n")
outcome_append(row)
log(f" {ex['alias']}__{fn}: {row['verdict']} start={row['start']} best={row['best']} compiles={row['compiles']} "
f"({row['seconds']}s, {ex['copies']} copies, {ex['needed']} needed"
+ (f", {' + '.join(row['path'])}" if row['path'] else "") + ")")
return row
def cmd_run(a):
dl.ensure_census(a.jobs)
ok, why = oracle.calibration_current()
if not ok:
sys.exit(f"delever_search --run: calibration not current ({why})")
clean, dirty = dl.src_clean()
if not clean and not a.dirty_ok:
sys.exit(f"delever_search --run: src/ is dirty (commit or --restore first):\n{dirty[:400]}")
by_src = oracle.recipes_by_src(oracle.load_recipes()["recipes"])
inc = dl.includers()
ex = exemplars(a.only, a.limit, a.include_done)
if not ex:
print("delever_search --run: no drawable exemplar (every class attempted, or --only matched none) (R68)")
return 1
inflight = {}
RUN.mkdir(parents=True, exist_ok=True)
print(f"delever_search --run: {len(ex)} exemplars ({sum(e['copies'] for e in ex):,} bodies behind them), {a.jobs} worker(s), "
f"beam {a.beam} × depth {a.depth} × cap {a.cap}, budget {a.budget} compiles per body, label {a.label}", flush=True)
t0 = time.time()
def log(msg):
print(msg, flush=True)
# a worker owns a whole TU: exemplars grouped by TU; headers serial after the TUs
by_tu = collections.OrderedDict()
for e in ex:
by_tu.setdefault(e["tu"], []).append(e)
# BOTTOM-UP WITHIN A FILE (rung R's rule): a bank shifts the lines of every body below it, and the census positions the
# lever-free rewrite starts from were taken before the run — run g1 lost func_80142EC0 to a `token mismatch` after
# func_801424E4 was banked above it in the same TU
sb = sites_by_body()
for tu in by_tu:
by_tu[tu].sort(key=lambda e: -min((s["line"] for s in sb.get((e["tu"], e["fn"]), [])), default=0))
tus = [t for t in by_tu if not t.endswith(".h")]
hdrs = [t for t in by_tu if t.endswith(".h")]
rows = []
def work(item):
n, tu = item
return [run_body(e, a, f"g{n % max(1, a.jobs)}", by_src, inc, inflight, log) for e in by_tu[tu]]
with ThreadPoolExecutor(max_workers=max(1, a.jobs)) as pool:
for res in pool.map(work, list(enumerate(tus))):
rows += res
for tu in hdrs:
rows += work((0, tu))
won = [r for r in rows if r["verdict"] == "MATCH" and r.get("banked")]
# propagation, serially after the parallel phase: a sibling lives in a TU another worker may have owned
if a.propagate and won:
for r in won:
ns = argparse.Namespace(propagate=[r["tu"], r["fn"]], label=a.label + "p", only=[], limit=None)
try:
okn, n, bad = dl.propagate(ns) # in process (S101): no subprocess per sibling
line = f"delever --propagate: {okn} of {n} sibling(s) banked, {bad} refused"
rc = 0 if okn else 1
except SystemExit as e: # "no banked reshape" — the refusal is the line
line, rc = str(e), 2
r["propagate_line"] = line[:200]
outcome_append(dict(kind="propagate", ts=time.strftime("%Y-%m-%d %H:%M:%S"), label=a.label, tu=r["tu"], fn=r["fn"],
nhash=r["nhash"], line=line[:300], rc=rc))
log(f" propagate {r['alias']}__{r['fn']}: {line[:160]}")
v = collections.Counter(r["verdict"] for r in rows)
print(f"\nsearch: {len(won)} of {len(rows)} exemplars matched lever-free in {(time.time() - t0) / 3600:.2f} h "
f"({sum(r['copies'] for r in won):,} of {sum(r['copies'] for r in rows):,} bodies behind them; "
f"{sum(r.get('compiles', 0) for r in rows):,} compiles) — " + " · ".join(f"{k} {n}" for k, n in v.most_common()))
return 0
# ----------------------------------------------------------------------------------------------------------------------
# --plan, --status, --positive-control
# ----------------------------------------------------------------------------------------------------------------------
def cmd_plan(a):
ex = exemplars(a.only, a.limit, a.include_done)
tot = exemplars(include_done=True)
print(f"delever_search --plan: {len(ex)} exemplars drawable of {len(tot)} residue classes "
f"({sum(e['copies'] for e in ex):,} bodies behind them)")
if a.score:
by_src = oracle.recipes_by_src(oracle.load_recipes()["recipes"])
inc = dl.includers()
for e in ex[:a.show]:
line = (f" {e['copies']:4d} copies · {e['needed']:2d} needed {','.join(e['kinds']):<26} {','.join(e.get('regs', [])) or '-':<12} "
f"{e['alias']} {e['tu']}:{e['fn']}")
if a.score:
try:
sites = sites_by_body().get((e["tu"], e["fn"]), [])
raw = (REPO / e["tu"]).read_text(errors="surrogateescape")
free = lever_free_body(e["tu"], raw, e["fn"], sites)
sc_ = Scorer(e["tu"], e["fn"], recs_for(e["tu"], by_src, inc), "plan", {})
ctl = sc_.score(raw)
r = sc_.score(free)
line += (f" · control {ctl['score']}/{'id' if ctl['ident'] else 'DIFF'} · start {r['score']} "
f"{family_key(r['cls']) if r['cls'] else r.get('err', '')[:30]} {r['cls']['pairs'][:3] if r['cls'] else ''}")
except Unstrippable as u:
line += f" · UNSTRIPPABLE {u.args[0][:1]}"
print(line, flush=True)
if len(ex) > a.show:
print(f" … {len(ex) - a.show} more")
return 0
def explain(a):
"""--explain TU FN: the lever-free body's residual, read — its class, every differing block as mnemonics (mine vs the
target), the NEEDED sites with their lines — and, with --path "move1|move2", the residual after those moves are applied in
order (a move is named exactly as the trace names it). No writes; one compile per text scored."""
tu, fn = a.explain
by_src = oracle.recipes_by_src(oracle.load_recipes()["recipes"])
inc = dl.includers()
raw = (REPO / tu).read_text(errors="surrogateescape")
sites = sites_by_body().get((tu, fn), [])
scorer = Scorer(tu, fn, recs_for(tu, by_src, inc), "ex", {})
names = dl.pin_names(sites)
text = lever_free_body(tu, raw, fn, sites)
for mv in [m.strip() for m in (a.path or "").split("|") if m.strip()]:
cands = dl.recipe_candidates(text, tu, fn, names, cap=None, families=dl.ALL_FAMILIES)
hit = next((c for c in cands if f"{c[0]} {c[1]}" == mv), None)
if hit is None:
sys.exit(f"delever_search --explain: no candidate named `{mv}` on the current text (have: {[f'{c[0]} {c[1]}' for c in cands[:12]]} …)")
text = hit[2]
r = scorer.score(text)
if r["score"] is None:
print(f"{tu}:{fn}: {r['err']}")
return 1
cls = r["cls"]
print(f"{tu}:{fn}: score {r['score']} ({family_key(cls)}; mine {cls['n_mine']} ins, target {cls['n_tgt']}) ident={r['ident']}"
+ (f" after {a.path}" if a.path else ""))
if cls["pairs"]:
print(" register pairs (mine -> target, count):", ", ".join(f"{x}->{y} x{n}" for x, y, n in cls["pairs"]))
row = latest_row(tu, fn) or {}
for s in sites:
v = next((d for d in row.get("sites", []) if d.get("line") == s["line"]), None)
tag = (v or {}).get("verdict", "?")
print(f" site {s['kind']:11s} {s.get('detail', ''):5s} line {s['line']:5d} {tag:8s} {s.get('text', '')[:70]}")
mine = md.insns_from_object(str(scorer.scratch), fn)
aa, bb = [masked_word(i) for i in mine], [masked_word(i) for i in scorer.tgt]
for t, i1, i2, j1, j2 in difflib.SequenceMatcher(None, aa, bb, autojunk=False).get_opcodes():
if t == "equal":
continue
print(f" {t:7s} mine[{i1}:{i2}] target[{j1}:{j2}]")
for k in range(max(i2 - i1, j2 - j1)):
m_ = mine[i1 + k]["mnem"] if i1 + k < i2 else "--"
t_ = scorer.tgt[j1 + k]["mnem"] if j1 + k < j2 else "--"
print(f" {i1 + k:4d} {m_:34s} | {t_}")
return 0
def score_file(a):
"""--try: `_score_file` with its per-call scratch removed afterwards (unless --keep, which prints where the candidate
object is — agents asked for both: parallel same-function scoring, and the object to dump)."""
try:
return _score_file(a)
finally:
tu, fn, _ = a.try_
base = RUN / "score"
pid = f"p{os.getpid()}"
dirs = list(base.glob(f"*__{fn}/{pid}"))
if getattr(a, "keep", False):
for d in dirs:
print(f" --keep: candidate object {d / 'cand.o'}")
else:
import shutil
for d in dirs:
shutil.rmtree(d, ignore_errors=True)
for o in oracle.SCRATCH.glob(f"*.score_*_{fn}_{pid}.o"):
try:
o.unlink()
except OSError:
pass
def _score_file(a):
"""--try TU FN FILE: FILE is a candidate text of the WHOLE translation unit (or, with --body, of the function's definition
alone, spliced into the tree's TU); it is compiled through the TU's own recipe with the source path swapped for a scratch copy
(`-I<the TU's directory>` added so its relative includes resolve) and the function's instructions are compared with the fleet
run's baseline object — the same score, class and mnemonic diff as --explain, WITHOUT writing the tree. This is the loop an
agent runs on its own candidate (T7, one agent at a time): zero tree writes, so any number may run at once; the bank itself
stays the coordinator's (`delever.apply_body_core` on the real recipe)."""
tu, fn, path = a.try_
by_src = oracle.recipes_by_src(oracle.load_recipes()["recipes"])
inc = dl.includers()
recs = recs_for(tu, by_src, inc)
if not recs:
sys.exit(f"delever_search --try: no recipe compiles {tu}")
text = pathlib.Path(path).read_text(errors="surrogateescape")
raw = (REPO / tu).read_text(errors="surrogateescape")
if a.body:
d_ = body_span(raw, tu, fn)
if d_ is None:
sys.exit(f"delever_search --try: {fn} is not defined in {tu}")
ls = dl.line_starts(raw)
text = raw[:ls[d_["line"] - 1]] + text.rstrip("\n") + "\n" + raw[ls[d_["end"]]:]
rec = recs[0]
src_dir = os.path.dirname(rec["src"] if not tu.endswith(".h") else tu)
# PER CALL, not per function (S103): two `--try` runs of the SAME function shared this directory and one of them read
# the other's object — agents c19, c21 and c22 each wrote a private parallel scorer to get around it. The directory is
# removed afterwards unless --keep (which prints the object's path, the other thing agents asked for).
scratch_dir = RUN / "score" / f"{rec['alias']}__{fn}" / f"p{os.getpid()}"
scratch_dir.mkdir(parents=True, exist_ok=True)
scratch_src = scratch_dir / os.path.basename(rec["src"])
# a header candidate: the includer compiles with the header swapped in through a scratch include dir that shadows it
if tu.endswith(".h"):
shadow = scratch_dir / "inc"
(shadow / os.path.dirname(os.path.relpath(tu, os.path.dirname(rec["src"])))).mkdir(parents=True, exist_ok=True)
(shadow / os.path.relpath(tu, os.path.dirname(rec["src"]))).write_text(text, errors="surrogateescape")
scratch_src.write_text(raw if False else (REPO / rec["src"]).read_text(errors="surrogateescape"), errors="surrogateescape")
# the INCLUDER's directory too, after the shadow: its own `#include "../shared/engine_prelude.h"` resolves only
# from there (the scratch copy sits in scratch_dir, whose `../shared` does not exist). Without it every header-TU
# candidate was a COMPILE-ERROR — S103's regen pass found 24 of 24 such classes unscorable, none ever judged.
extra = f"-I{shadow.as_posix()} -I{os.path.dirname(rec['src'])} -I{src_dir}"
else:
scratch_src.write_text(text, errors="surrogateescape")
extra = f"-I{src_dir}"
pipeline = rec["pipeline"].replace(" " + rec["src"], " " + scratch_src.as_posix(), 1).replace("-Iinclude", f"-Iinclude {extra}", 1)
mod = dict(rec, pipeline=pipeline, src=scratch_src.as_posix())
# THE TAG IS PER FUNCTION, not per file. compile_obj names its scratch object `<obj>.<tag>.o`, so with a constant tag
# two agents scoring different functions of the SAME translation unit write and read one object — T7's burst of 20
# (S102) put nine agents in one file and two of them reported it independently: spurious COMPILE-ERRORs, and one agent
# scored four candidates against another agent's function before the echoed TU/FN line gave it away.
tag = "score_" + re.sub(r"\W+", "_", f"{rec['alias']}_{fn}") + f"_p{os.getpid()}"
data, dt, err = oracle.compile_obj(mod, None, tag=tag)
if data is None:
print(f"{tu}:{fn}: {'COMPILE-CRASH' if err.startswith('CRASH:') else 'COMPILE-ERROR'} — {err[:300]}")
return 2
base = oracle.baseline_path(rec["obj"]) # ditto: an agent scoring during an R22 gate must still see a baseline
tgt = md.insns_from_object(str(base), fn)
p = scratch_dir / "cand.o"
p.write_bytes(data)
mine = md.insns_from_object(str(p), fn)
cls = classify(mine, tgt)
print(f"{tu}:{fn}: score {cls['score']} ({family_key(cls)}; mine {cls['n_mine']} ins, target {cls['n_tgt']}) — "
f"{'MATCH (the function is byte-identical; the bank judges the whole object)' if cls['score'] == 0 else 'not yet'}")
if cls["pairs"]:
print(" register pairs (mine -> target, count):", ", ".join(f"{x}->{y} x{n}" for x, y, n in cls["pairs"]))
aa, bb = [masked_word(i) for i in mine], [masked_word(i) for i in tgt]
for t, i1, i2, j1, j2 in difflib.SequenceMatcher(None, aa, bb, autojunk=False).get_opcodes():
if t == "equal":
continue
print(f" {t:7s} mine[{i1}:{i2}] target[{j1}:{j2}]")
for k in range(max(i2 - i1, j2 - j1)):
m_ = mine[i1 + k]["mnem"] if i1 + k < i2 else "--"
t_ = tgt[j1 + k]["mnem"] if j1 + k < j2 else "--"
print(f" {i1 + k:4d} {m_:34s} | {t_}")
return 0 if cls["score"] == 0 else 1
def latest_row(tu, fn):
row = None
for r in dl.load_ledger():
if r.get("tu") == tu and r.get("fn") == fn:
row = r
return row
def cmd_status(a):
outs = load_outcomes()
att = [o for o in outs if o.get("kind") == "attempt"]
v = collections.Counter(o.get("verdict") for o in att)
left = exemplars()
print(f"delever_search --status: {len(att)} attempts {dict(v)} · {sum(1 for o in att if o.get('banked'))} banked · "
f"{len(left)} residue classes not yet attempted ({sum(e['copies'] for e in left):,} bodies)")
for o in att:
if o.get("verdict") == "MATCH":
print(f" MATCH {o['alias']}__{o['fn']} ({o['copies']} copies, start {o.get('start')}, {o.get('compiles')} compiles, "
f"{' + '.join(o.get('path', []))})")
return 0
def positive_control(a):
"""perturb a body the tree already matches by one or two generator moves; the search must find its way back to 0.
Never writes the tree (the scorer restores after every compile; nothing is banked)."""
tu, fn = a.positive_control
raw = (REPO / tu).read_text(errors="surrogateescape")
d_ = body_span(raw, tu, fn)
if d_ is None:
sys.exit(f"delever_search --positive-control: {fn} is not defined in {tu}")
by_src = oracle.recipes_by_src(oracle.load_recipes()["recipes"])
inc = dl.includers()
scorer = Scorer(tu, fn, recs_for(tu, by_src, inc), "pc", {})
ctl = scorer.score(raw)
print(f"positive control {tu}:{fn}: the tree's own text scores {ctl['score']} ident={ctl['ident']}", flush=True)
if ctl["score"] != 0 or not ctl["ident"]:
sys.exit("delever_search --positive-control: the UNPERTURBED body does not score 0 — calibrate/build first (R56)")
names = dl.pin_names(sites_by_body().get((tu, fn), []))
gen = make_gen(tu, fn, names)
text, moves = raw, []
rng = random.Random(a.seed)
for k in range(a.moves):
cands = dl.recipe_candidates(text, tu, fn, names, cap=None, families=dl.ALL_FAMILIES)
rng.shuffle(cands)
picked = None
for rec, desc, ctext in cands[:40]:
r = scorer.score(ctext)
if r["score"] is not None and r["score"] > 0 and (k == 0 or r["score"] != scorer.score(text)["score"]):
picked = (rec, desc, ctext, r["score"])
break
if picked is None:
sys.exit(f"delever_search --positive-control: no generator move perturbs {fn} at step {k + 1} — pick another body")
moves.append(f"{picked[0]} {picked[1]}")
text = picked[2]
print(f" perturbed by {moves[-1]} -> score {picked[3]}", flush=True)
trace = []
res = search(text, scorer.score, gen, beam=a.beam, depth=a.depth, cap=a.cap, budget=a.budget, trace=trace,
log=lambda m: print(m, flush=True))
ok = res["verdict"] == "MATCH"
print(f"positive control: {'PASS' if ok else 'FAIL'} — perturbed by {' + '.join(moves)} (start {res.get('start')}), "
f"{res['verdict']} after {res['compiles']} compiles" + (f" by {' + '.join(res['path'])}" if ok else f" (best {res.get('best')})"))
outcome_append(dict(kind="positive-control", ts=time.strftime("%Y-%m-%d %H:%M:%S"), tu=tu, fn=fn, moves=moves,
verdict=res["verdict"], start=res.get("start"), compiles=res["compiles"], path=res.get("path", []),
seconds=round(scorer.seconds, 1)))
return 0 if ok else 1
# ----------------------------------------------------------------------------------------------------------------------
# --selftest: the classifier on synthetic streams, the beam on a stub scorer whose answer needs three composed moves
# ----------------------------------------------------------------------------------------------------------------------
def _ins(word, reloc_kind=None, reloc_op=None):
return dict(off=0, word=word, mnem="", reloc_kind=reloc_kind, reloc_op=reloc_op, jrel=None)
def selftest():
ok = True
def fail(msg):
nonlocal ok
ok = False
print("selftest:", msg)
# and v0,v1,v0 (00621024) vs and v0,v0,v1 (00431024): one REG position, caller-saved pairs
tgt = [_ins(0x8E230044), _ins(0x2402FFDF), _ins(0x00431024)]
mine = [_ins(0x8E220044), _ins(0x2403FFDF), _ins(0x00621024)]
c = classify(mine, tgt)
if c["kind"] != "REG" or c["bank"] != "caller" or c["score"] != 3:
fail(f"REG-caller classification wrong: {c}")
# The invariant, not a fixed window (widening the window once per new generator hid what it was for): the temp move
# leads, and every TARGETED caller-saved lever — R5 the commutative swap, R15 the sink, R16 the constant holder —
# is drawn before the BLIND families that permute declarations or statements wholesale (R9, R2, R4).
caller = FAMILIES["REG-caller"]
# R19 leads (the only family that can change a call's arity, and free when it does not apply), R6 the temp move is
# still near the front, and every TARGETED lever precedes every BLIND family. The window is deliberately loose: it
# was widened once per new generator until it stopped expressing anything, so it now states the ORDERING RULE only.
# and every TARGETED lever before every BLIND family that permutes declarations or statements wholesale.
targeted, blind = {"R5", "R15", "R16", "R19"}, {"R9", "R2", "R4"}
if family_key(c) != "REG-caller" or caller[0] != "R19" or "R6" not in caller[:4] or not targeted <= set(caller) \
or max(caller.index(t) for t in targeted) > min(caller.index(b) for b in blind):
fail(f"REG-caller family wrong: {family_key(c)} {caller}")
# a callee-saved swap: addu s0,a0,zero vs addu s1,a0,zero
c = classify([_ins(0x00808021)], [_ins(0x00808821)])
if c["kind"] != "REG" or c["bank"] != "callee":
fail(f"REG-callee classification wrong: {c}")
# COUNT: one extra move
c = classify([_ins(0x00808021), _ins(0x8E220044)], [_ins(0x8E220044)])
if c["kind"] != "COUNT":
fail(f"COUNT classification wrong: {c}")
# ORDER: the same two words swapped
c = classify([_ins(0x8E220044), _ins(0x2403FFDF)], [_ins(0x2403FFDF), _ins(0x8E220044)])
if c["kind"] != "ORDER":
fail(f"ORDER classification wrong: {c}")
# a reloc-masked pair with the same symbol is not a mismatch; a different symbol is
c = classify([_ins(0x3C040000, "HI16", "D_800A0000")], [_ins(0x3C040000, "HI16", "D_800A0000")])
if c["kind"] != "IDENTICAL":
fail(f"masked reloc read as a mismatch: {c}")
c = classify([_ins(0x3C040000, "HI16", "D_800A0000")], [_ins(0x3C040000, "HI16", "D_800A0004")])
if c["score"] != 1:
fail(f"a different reloc symbol not counted: {c}")
# the beam on a stub: a text is "a,b,c"; the target (2,1,3); score = L1 distance; moves = ±1 on one coordinate, tagged
# by family so the ranking has something to order; the start (1,0,2) is THREE moves away -> depth 3 must find it
target = (2, 1, 3)
def parse(t):
return tuple(int(x) for x in t.split(","))
def stub_score(t):
v = parse(t)
s = sum(abs(x - y) for x, y in zip(v, target))
return dict(score=s, ident=(s == 0), cls=dict(kind=("IDENTICAL" if s == 0 else "OTHER"), bank=None, score=s, n_mine=3,
n_tgt=3, positions=[i for i in range(3) if v[i] != target[i]], pairs=[]),
seconds=0.0, err="")
def stub_gen(t, cls):
v = parse(t)
out = []
for i in range(3):
for dlt in (1, -1):
w = list(v)
w[i] += dlt
out.append((("R5", "R7", "R2")[i], f"coord{i}{'+' if dlt > 0 else '-'} @{i + 1}", ",".join(map(str, w))))
return out
calls = dict(n=0)
def counting(t):
calls["n"] += 1
return stub_score(t)
res = search("1,0,2", counting, stub_gen, beam=2, depth=3, cap=6, budget=200)
if res["verdict"] != "MATCH" or len(res["path"]) != 3 or res["compiles"] != calls["n"]:
fail(f"the beam did not compose three moves: {res}")
res = search("1,0,2", stub_score, stub_gen, beam=2, depth=2, cap=6, budget=200)
if res["verdict"] != "NO-MATCH" or res["best"] != 1:
fail(f"depth 2 should end NO-MATCH at distance 1: {res}")
res = search("1,0,2", stub_score, stub_gen, beam=2, depth=3, cap=6, budget=4)
if res["verdict"] != "BUDGET" or res["compiles"] > 4:
fail(f"the budget did not stop the search: {res}")
res = search("2,1,3", stub_score, stub_gen)
if res["verdict"] != "MATCH" or res["compiles"] != 1:
fail(f"a seed at distance 0 must be MATCH in one score: {res}")
# the generators on a fixture body: R8 introduces a typed temp, R9 swaps adjacent statements, both through the real parser
fix = ("s32 f(s32 *p, s32 q)\n{\n s32 a;\n s32 b;\n a = *(s32 *)(p + 4) & q;\n b = q + 1;\n return a + b;\n}\n")
cands = dl.recipe_candidates(fix, "src/x.c", "f", [], cap=None, families=("R8", "R9"))
r8 = [c for c in cands if c[0] == "R8"]
r9 = [c for c in cands if c[0] == "R9"]
temp = [c for c in r8 if c[1].startswith("temp")]
base = [c for c in r8 if c[1].startswith("base")]
if len(temp) != 1 or "s32 tmp0;" not in temp[0][2] or "tmp0 = *(s32 *)(p + 4);" not in temp[0][2] or "a = tmp0 & q;" not in temp[0][2]:
fail(f"R8 did not hoist the dereference into a typed temp: {temp[:1]}")
if len(base) != 1 or "tmp0 = p + 4;" not in base[0][2] or "a = *(s32 *)tmp0 & q;" not in base[0][2]:
fail(f"R8 did not hoist the dereference's base into an address local: {base[:1]}")
if len(r9) != 1 or " b = q + 1;\n a = *(s32 *)(p + 4) & q;\n" not in r9[0][2]:
fail(f"R9 did not swap the two adjacent statements: {r9[:1]}")
default = dl.recipe_candidates(fix, "src/x.c", "f", [], cap=None)
if any(c[0] in ("R8", "R9", "R10", "R12", "R13") for c in default):
fail("rung R's default family set grew — R8..R13 must stay the engine's until measured")
# R10 on a void-parameter function must yield nothing; on (s32 *p, s32 q) one copy per parameter, pointer spelled `s32 *p2`
fix2 = ("s32 g(void)\n{\n s32 d;\n d = 1;\n return d;\n}\n")
if dl.recipe_candidates(fix2, "src/x.c", "g", [], cap=None, families=("R10",)):
fail("R10 generated a parameter copy for a (void) function")
r10 = dl.recipe_candidates(fix, "src/x.c", "f", [], cap=None, families=("R10",))
if len(r10) != 2 or "s32 *p2;" not in r10[0][2] or "p2 = p;" not in r10[0][2] or "*(s32 *)(p2 + 4)" not in r10[0][2]:
fail(f"R10 parameter copies wrong: {[(c[0], c[1]) for c in r10]}")
# R12 widens/narrows a local; R13 reassociates a +/- chain; R8 names a repeated RHS once
fix3 = ("s32 h(s32 *p, s32 q)\n{\n s32 a;\n u16 w;\n a = q + *(s32 *)(p + 4) - w;\n"
" *(s16 *)(p + 28) = -a;\n *(s16 *)(p + 24) = -a;\n return a;\n}\n")
r12 = dl.recipe_candidates(fix3, "src/x.c", "h", [], cap=None, families=("R12",))
if [c[1] for c in r12] != ["width a s32->u16 @3", "width a s32->s16 @3", "width a s32->u8 @3",
"width w u16->s32 @4", "width w u16->s16 @4", "width w u16->u8 @4"]:
fail(f"R12 widths wrong: {[c[1] for c in r12]}")
# R14 changes a PARAMETER's width in the header; R8's shared base names one address local for two dereferences of one base
r14 = dl.recipe_candidates(fix3, "src/x.c", "h", [], cap=None, families=("R14",))
if [c[1] for c in r14] != ["param-width q s32->s16 @1", "param-width q s32->u16 @1", "param-width q s32->u8 @1"] \
or "s32 h(s32 *p, s16 q)" not in r14[0][2]:
fail(f"R14 parameter widths wrong: {[c[1] for c in r14]}")
fix4 = ("s32 m(s32 *p, s32 q)\n{\n s32 a;\n a = *(s32 *)(p + 4) & q;\n *(u16 *)(p + 4) = q;\n return a;\n}\n")
sb = [c for c in dl.recipe_candidates(fix4, "src/x.c", "m", [], cap=None, families=("R8",)) if c[1].startswith("base-shared")]
if len(sb) != 1 or "tmp0 = p + 4;" not in sb[0][2] or "a = *(s32 *)tmp0 & q;" not in sb[0][2] or "*(u16 *)tmp0 = q;" not in sb[0][2]:
fail(f"R8 shared base wrong: {[(c[1], c[2]) for c in sb][:1]}")
fix5 = ("s32 k(s32 param_2)\n{\n u8 *src;\n src = (u8 *)((u32)param_2);\n return src[3];\n}\n")
al = [c for c in dl.recipe_candidates(fix5, "src/x.c", "k", [], cap=None, families=("R10",)) if c[1].startswith("param-alias")]
if len(al) != 1 or "return param_2[3];" not in al[0][2] or "src = " in al[0][2]:
fail(f"R10 alias through a cast wrong: {[(c[1], c[2]) for c in al][:1]}")
r13 = dl.recipe_candidates(fix3, "src/x.c", "h", [], cap=None, families=("R13",))
if len(r13) != 1 or "a = q - w + *(s32 *)(p + 4);" not in r13[0][2]:
fail(f"R13 reassociation wrong: {[(c[1], c[2].split(chr(10))[4]) for c in r13]}")
cse = [c for c in dl.recipe_candidates(fix3, "src/x.c", "h", [], cap=None, families=("R8",)) if c[1].startswith("cse")]
if len(cse) != 1 or "tmp0 = -a;" not in cse[0][2] or cse[0][2].count("= tmp0;") != 2:
fail(f"R8 common subexpression wrong: {[(c[1]) for c in cse]}")
print(f"delever_search --selftest: {'OK' if ok else 'FAILED'} — classifier 6 cases, beam 4 cases, generators R8/R9")
return ok
def main():
ap = argparse.ArgumentParser()
g = ap.add_mutually_exclusive_group(required=True)
g.add_argument("--plan", action="store_true")
g.add_argument("--run", action="store_true")
g.add_argument("--positive-control", nargs=2, metavar=("TU", "FN"))
g.add_argument("--status", action="store_true")
g.add_argument("--explain", nargs=2, metavar=("TU", "FN"), help="read one body's residual (no writes)")
g.add_argument("--try", dest="try_", nargs=3, metavar=("TU", "FN", "FILE"), help="score a candidate TU text (or --body: a body) WITHOUT writing the tree")
g.add_argument("--selftest", action="store_true")
ap.add_argument("--path", help="--explain: moves to apply first, `|`-separated, named as the trace names them")
ap.add_argument("--body", action="store_true", help="--try: FILE holds the function's definition only")
ap.add_argument("--keep", action="store_true", help="--try: keep the per-call scratch and print the candidate object path")
ap.add_argument("--only", nargs="*", default=[], help="fn, TU (substring), alias or nhash prefix")
ap.add_argument("--limit", type=int)
ap.add_argument("--show", type=int, default=25)
ap.add_argument("--score", action="store_true", help="--plan: score each listed exemplar's lever-free text (one compile each + the control)")
ap.add_argument("--beam", type=int, default=3)
ap.add_argument("--depth", type=int, default=3)
ap.add_argument("--cap", type=int, default=48, help="candidates scored per node")
ap.add_argument("--budget", type=int, default=400, help="compiles per body")
ap.add_argument("--moves", type=int, default=1, help="--positive-control: how many perturbing moves")
ap.add_argument("--seed", type=int, default=1)
ap.add_argument("--label", default="g1")
ap.add_argument("--propagate", action=argparse.BooleanOptionalAction, default=True, help="spread each bank to its class (serial, after the run)")
ap.add_argument("--dirty-ok", action="store_true")
ap.add_argument("--include-done", action="store_true", help="draw classes that already have an outcome row")
ap.add_argument("-j", "--jobs", type=int, default=8)
a = ap.parse_args()
os.chdir(REPO)
RUN.mkdir(parents=True, exist_ok=True)
if a.selftest:
return 0 if selftest() else 1
if a.plan:
return cmd_plan(a)
if a.status:
return cmd_status(a)
if a.explain:
return explain(a)
if a.try_:
return score_file(a)
if a.positive_control:
return positive_control(a)
if a.run:
return cmd_run(a)
if __name__ == "__main__":
sys.exit(main())
Reference in New Issue View Git Blame Copy Permalink