002. AST 编译优化与 N-ary 展平策略¶

背景¶

在 ADR-001 中，我们决定从基于闭包的求值引擎转向基于 AST 的编译方案。

初版 AST 实现解决了「逻辑黑盒」问题，并解锁了 Trace / Skip 等高级特性，但在处理大规模规则组合（例如深度 1000+）时，又撞上了两个关键的性能瓶颈。

这听起来颇为反常。现实场景里，这样的东西几乎不可能出现：

运行时 RecursionError：生成的 AST 仍是一棵深层嵌套的二叉树结构——Call(Call(...))——导致 Python 解释器在执行时撞上递归上限。

??? info "closure_recursion"
```
  ![closure_recursion](../assets/closure_recursion.png)
```
构建开销爆炸：Python 的位运算 & 是左结合的，使得构建 A & B & C ... 这样的链时产生元组复制开销。构建一条 2000 节点的规则要花 100ms 以上，显著慢于 Python 原生的 import 开销。

??? info "初版 AST 的构建开销显著高于闭包。"
```
  ![prof](../assets/first_version_ast_prof.png)
```

我们需要一个能同时做到原生 Python 执行速度、极低构建开销、不受递归深度限制、中间过程可观测的架构。

探索¶

重构过程中我们尝试了几种方案：

闭包方案：链式 lambda 函数。执行速度可接受，但深度 >1000 时撞上递归上限，也无法支持 Tracing 或完整的 Audit 求值。
朴素 AST 方案：在 __and__ 里实时维护扁平的 children 列表。虽然生成了扁平的运行时代码，但构建时的内存复制带来无法接受的性能开销。
惰性构建 + 编译期展平：把展平的计算负担从构建期转移到编译期。这是最终采用的方案。

决策¶

1. 惰性二叉构建¶

为解决构建性能问题，我们把 __and__ 和 __or__ 的实现退化为简单的二叉树构建。

A & B 不再尝试合并列表，而是直接生成包含 (self, other) 的二叉节点。每个 & 从 O(N)（元组复制）降到 O(1)（二叉节点分配），N 规则链的构建是 O(N) 而非 O(N²)。我们还引入了静态方法 Predicate.all([...]) 与 Predicate.any([...])，借助底层 tuple(list) 实现真正的批量分配。

2. 智能编译器¶

由于构建期现在生成的是「左倾二叉树」，直接编译会产生低效、易栈溢出的代码。我们在 Compiler 里引入了一个迭代式链收集器（Iterative Chain Collector）。

编译器遇到 AND/OR 节点时，贪婪地向左下钻（迭代式 drill-down），把嵌套的二叉结构重建成扁平列表 [Leaf_1, Leaf_2, ..., Leaf_N]，生成 ast.BoolOp(values=[...])（N-ary）。Python 解释器以零栈帧开销线性执行这个扁平结构。

3. 分层执行策略¶

默认使用 Predicate.all/any + Compiler。对默认场景（开启短路、关闭 Trace），编译后的 Runner 通过 __slots__ 缓存，后续调用零开销。

结果与基准¶

我们在不同深度下对三种实现做了基准测试。本地 pytest-benchmark 因 GC 干扰方差很大；CodSpeed 在受控环境下提供权威测量。

指标	朴素 Python(`def`)	闭包（旧）	当前（AST）
构建（D=100）	~2.4µs	~40µs（慢 17x）	~3.7µs(1.5x)
构建（D=1000）	~23µs	~443µs(127x)	~5.8µs（快 4x）
运行（D=100）	~2.4µs	~40µs（慢 17x）	~2.5µs(1.07x)
运行（D=20）	~534ns	~4.3µs（慢 8x）	~698ns(1.3x)
最大深度	1000(RecursionError)	1000（栈溢出）	∞（迭代式）

主要成果¶

深度 1000 时，当前实现的构建比手写 Python 快 4x、比闭包快 127x（消除了 O(N²) 的元组复制）。运行时落在原生 Python（def）7% 以内，同时保持完整可观测性；闭包在同等深度下慢 17x。迭代式编译彻底移除了 Python 1000 帧的递归限制。

权衡：当前实现为 Trace / Audit 能力付出了约 7% 的小幅运行时成本。对于追求绝对最小开销的热路径，可考虑关闭 tracing，或在浅链（D<50）上直接用朴素 Python。

局限与注意¶

尽管性能指标出色，我们的设计仍有取舍，当前测试也有盲区：

异构树开销。编译器优化对纯 AND 或纯 OR 链（同构链）最有效（目前也只针对这一场景设计了基准——欢迎贡献）。规则树高度交错时（例如 (A & B) | (C & D) | ...），编译器无法做大规模展平，会退化为普通的递归编译。正确性不受影响，但编译时间会略增。
基准偏差。当前基准（test_stability.py）主要针对「深度 2000 的纯 AND 链」——编译器的甜点区。对于现实中「宽而浅」或「复杂嵌套」的规则树，性能收益可能不像深链那样显著（但仍优于闭包方案）。
高级特性的开销未量化。开启 trace=True 或 short_circuit=False 会注入额外的辅助函数。我们尚未为 Trace 模式建立严格基准，但预计会比默认模式慢 2–5x（源于对象分配与字符串格式化），这是可观测性的必要成本。
依赖静态类型检查。为追求极致构建性能，Predicate.all 移除了运行时类型检查（isinstance），完全依赖静态类型检查器（mypy / pyright / ty）保证参数正确。非 Predicate 对象被强行塞进列表时，错误会推迟到编译期或运行时才暴露。

现实意义¶

真实业务场景里，规则执行往往是 I/O 密集的（拉取用户画像、查数据库），引擎本身 15µs 的执行时间相对网络延迟可以忽略。基准深度 2000 是压力测试，不是使用模式；现实业务规则很少超过 10–20 层，处理无限深度的能力是可靠性保证，不是日常需求。

这次架构大改的首要动机是可观测性与灵活性，而不只是裸速度。我们接受 AST 操作的极小开销，以换取硬编码 Python 逻辑无法提供的能力：类型安全、可复用的规则块（is_adult、is_admin）可以被隔离测试；透明的 Tracing 与 Auditing 中间件能告诉用户在复杂链路中究竟是哪条谓词失败了；规则可以被序列化、更新，而无需重新部署（规划于后续版本）。