「编译器正确性与验证」

# 一个典型的误编译 bug: 常量折叠算错了
def fold_constant_div(a, b):
    if b == 0:
        return "错误: 除以零未处理 -> 未定义行为"
    if a % b != 0:
        return f"{a} / {b} 精确除法失败, 应保留余数"   # 编译器错误地省略了余数
    return a // b

# 错误实现: 编译器把 (x / 2) * 2 折叠成 x, 但 x 为奇数时结果不同
def buggy_fold_mul_div(x):
    return x                       # 误认为 (x//2)*2 == x

def correct_mul_div(x):
    return (x // 2) * 2            # 奇数时 != x

for x in [0, 1, 2, 3, 4]:
    if buggy_fold_mul_div(x) != correct_mul_div(x):
        print(f"x={x}: 正确结果 {correct_mul_div(x)}, 误编译为 {buggy_fold_mul_div(x)}")

import random

def random_expr(depth=0):
    """随机生成一个算术表达式 (仅演示, 不保证类型安全)."""
    if depth > 3:
        return str(random.randint(0, 9))
    op = random.choice(["+", "-", "*", "//"])
    left = random_expr(depth + 1)
    right = random_expr(depth + 1)
    return f"({left} {op} {right})"

def fuzz_compiler(n=10, seed=42):
    random.seed(seed)
    for i in range(n):
        prog = f"result = {random_expr()}"
        try:
            compile(prog, "<fuzz>", "exec")
            print(f"[{i:02d}] 编译通过: {prog}")
        except Exception as e:
            print(f"[{i:02d}] 编译器异常: {type(e).__name__}: {e}")

fuzz_compiler()

import subprocess

def run_with_gcc(src):   return "gcc: exit 0, output=7"
def run_with_clang(src): return "clang: exit 0, output=9"

def differential_test(program):
    r1, r2 = run_with_gcc(program), run_with_clang(program)
    if r1 != r2:
        return f"分歧! 同一程序不同输出:\n  {r1}\n  {r2}"
    return f"一致: {r1}"

print(differential_test("int main(){return 3+4;}"))

# 同一编译器, -O0 vs -O3 对拍
def run_opt_level(src, opt):
    # 简化: 不同优化级别应该语义一致
    return f"opt={opt} -> {sum(map(ord, src)) % 10}"

for opt in ["-O0", "-O3"]:
    print(run_opt_level("int f(int x){return x*2;}", opt))

GOLDEN = {"test_add.py": "7", "test_loop.py": "55"}   # 存档的期望输出

def run_golden_tests(compiler_impl):
    failures = []
    for name, expected in GOLDEN.items():
        got = compiler_impl(name)
        status = "PASS" if got == expected else f"FAIL (期望 {expected}, 得到 {got})"
        print(f"  {name}: {status}")
        if got != expected:
            failures.append(name)
    return failures

def current_impl(test_name):
    return {"test_add.py": "7", "test_loop.py": "55"}[test_name]

run_golden_tests(current_impl)

# 更新黄金文件 = 显式确认行为变更
def approve_change(test_name, new_output):
    old = GOLDEN.get(test_name)
    print(f"确认变更: {test_name} {old} -> {new_output}")
    GOLDEN[test_name] = new_output   # 人工 review 后才覆盖

approve_change("test_loop.py", "60")

# 用断言模拟"可证明性质": 语义保持(Semantic Preservation)
def compile_expr(ast):
    """把表达式树编译成指令树, 保持 '求值结果不变' 这一性质."""
    if isinstance(ast, int):
        return ("const", ast)
    return ("add", compile_expr(ast[1]), compile_expr(ast[2]))

def eval_ast(ast):
    return ast if isinstance(ast, int) else eval_ast(ast[1]) + eval_ast(ast[2])

def eval_code(code):
    return code[1] if code[0] == "const" else eval_code(code[1]) + eval_code(code[2])

for expr in [3, (1, 2), (1, (2, 3)), ((1, 2), 3)]:
    code = compile_expr(expr)
    assert eval_ast(expr) == eval_code(code), "语义保持被破坏!"
print("全部通过: 编译前后求值一致 (semantic preservation)")

def optimize_based_on_ub(expr):
    """编译器假设 '无有符号溢出', 把 x+1>x 折叠成恒真."""
    if expr == "x + 1 > x":
        return "true (基于无溢出假设)"
    return expr

# 但实际程序里 x 真的溢出了
x = 2147483647
actual = (x + 1 > x)            # Python 无溢出, 这里为 False
compiled = optimize_based_on_ub("x + 1 > x")
print(f"程序直觉: {actual}")
print(f"优化结果: {compiled}")

# 用例精简: delta debugging 的核心循环
def minimize(input_str, bug_test):
    """不断尝试删掉一半字符, 直到最小复现."""
    n = 1
    while n < len(input_str):
        candidate = input_str[:n] + input_str[n + 1:]
        if bug_test(candidate):
            input_str = candidate
        else:
            n += 1
    return input_str

def triggers_bug(code):
    return "0//0" in code           # 触发除零误编译

min_code = minimize("return (0//0) + 9999999;", triggers_bug)
print("最小复现:", min_code)

# 覆盖率驱动的模糊: 命中新路径才保留变异
def coverage_fuzz(seed, cov_hist, mutate):
    for _ in range(100):
        variant = mutate(seed)
        cov = hash(variant) % 1000
        if cov not in cov_hist:
            cov_hist.add(cov)       # 探索到新路径, 保留
            seed = variant
    return seed

print("模糊后种子:", coverage_fuzz("int x=0;", {0}, lambda s: s + "+1"))