Expr-lang项目中的无限循环问题分析与修复

问题背景

在Expr-lang项目中，当使用patcher/value模块结合运算符重载功能时，出现了CPU使用率飙升到100%的无限循环问题。这个问题特别发生在尝试为"shopspring/decimal"库添加运算符支持时。

问题现象

开发者在使用value模块的ValueGetter功能结合运算符重载时，表达式编译器会陷入无限循环状态。具体表现为：

1. 编译过程无法完成
2. CPU使用率迅速达到100%
3. 通过性能分析工具可以看到检查器(checker)被反复调用

问题复现

问题可以通过以下关键代码复现：

env := make(map[string]any)
env["ValueOne"] = &myInt{1}  // 使用value类型
env["ValueTwo"] = &myInt{2}

// 编译会陷入无限循环
program, err := expr.Compile("decimal(ValueOne) * decimal(2)",
    expr.Env(env),
    value.ValueGetter,
    expr.Function("decimal", ...),
    expr.Function("_decimalMul", ...),
    expr.Operator("*", "_decimalMul"),
)

根本原因分析

经过深入分析，发现问题根源在于patcher的执行机制：

1. patcher执行顺序问题：当value patcher先于operator patcher执行时，会导致无限循环
2. ShouldRepeat机制缺陷：operator patcher的ShouldRepeat()持续返回true，导致patcher不断重新执行
3. 非幂等patcher问题：value patcher不是幂等的，每次执行都会修改AST树结构

具体来说，operator patcher的应用会导致所有patcher重新运行，这个设计假设所有patcher都是幂等的。然而value patcher并不满足这个假设，因为它只是将当前节点包装在CallNode中作为参数，当AST树再次遍历时，它又会触发对参数的patcher操作。

解决方案

修复方案包含两个主要部分：

1. 修改operator patcher逻辑：确保operator patcher不会持续触发ShouldRepeat()
2. 优化patcher执行策略：将patcher执行分为两个阶段：
   • 第一阶段：运行所有非可重复patcher（一次性执行）
   • 第二阶段：专门运行可重复patcher（如operator patcher），按需重复执行

这种两阶段执行策略既保留了原有功能，又避免了无限循环问题。

技术影响

这个修复对项目的影响包括：

1. 恢复了value模块与运算符重载功能的兼容性
2. 明确了patcher的执行顺序和幂等性要求
3. 为未来可能添加的复杂patcher提供了更清晰的执行模型

最佳实践建议

基于此问题的经验，建议开发者在实现自定义patcher时：

1. 确保patcher的幂等性：多次应用应产生相同结果
2. 谨慎使用ShouldRepeat接口：明确重复执行的边界条件
3. 考虑patcher之间的相互影响：特别是当多个patcher共同作用于同一AST时

总结

Expr-lang项目中的这个无限循环问题展示了在语言工具开发中AST转换的复杂性。通过分析patcher执行机制和相互作用，找到了既保持功能完整又避免循环的解决方案。这个案例也为处理类似的语言工具问题提供了有价值的参考模式。