cure_engine/

lang.rs

//! `Lang` trait：语言适配层。引擎的一切通用逻辑只通过它访问语言 AST。
//!
//! 结构契约：
//! - 节点用稳定句柄 `Id`（语言侧 arena 索引），arena 只追加不回收，`Id` 永不失效；
//! - children 顺序 = 书写/求值顺序（各 kind 的布局见 [`crate::kind::NodeKind`]）；
//! - `check` 阶段允许**追加**新节点（arena push），但不得改动既有结构；
//!   结构变更只允许通过 `Edit` 在应用阶段发生。

use std::fmt::Debug;
use std::hash::Hash;

use crate::effect::Effect;
use crate::kind::{BinOp, LitRef, NodeKind, UnOp};

/// Result of scanning one statement for a name: any-path reads keep the
/// init alive, shadowing declarations reject, and a dominating simple
/// assignment kills it. `None` means the statement neither reads, shadows,
/// nor dominantly writes the name.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum StmtKill<Id> {
    None,
    Read,
    Shadow,
    DomWrite(Id),
}

pub trait Lang {
    /// 稳定节点句柄（通常是 `Copy` 的索引 newtype）。
    type Id: Copy + Eq + Hash + Ord + Debug;
    /// 名字等价类句柄（Java：u32 intern id）。区域扫描的全部名字比较
    /// 走它——语言侧应保证同名字同键、比较为整数等值（无字符串 memcmp）。
    type NameKey: Copy + Eq + Ord + Debug;
    /// 节点在语言 arena 中的稠密下标（供引擎位图/数组索引）。
    fn node_index(&self, id: Self::Id) -> usize;
    /// `node_index` 的逆映射（下标 → Id）。cure-tree 工具包的线性
    /// 扫描（效果表重建、名字键扩展）需要按 arena 下标遍历。
    fn id_of_index(&self, idx: usize) -> Self::Id;

    // ---- 结构 ----

    fn kind(&self, id: Self::Id) -> NodeKind;
    fn children(&self, id: Self::Id) -> &[Self::Id];

    /// 把 `parent` 的第 `index` 个孩子替换为 `new`。
    fn set_child(&mut self, parent: Self::Id, index: usize, new: Self::Id);
    /// 删除 `parent` 的第 `index` 个孩子。
    fn remove_child(&mut self, parent: Self::Id, index: usize);
    /// 从 `node` 的第 `index` 个孩子开始删 `remove` 个、插入 `insert`。
    fn splice(&mut self, node: Self::Id, index: usize, remove: usize, insert: Vec<Self::Id>);

    // ---- 构造 ----

    fn build_return(&mut self, value: Option<Self::Id>) -> Self::Id;
    fn build_block(&mut self, stmts: Vec<Self::Id>) -> Self::Id;
    fn build_unary(&mut self, op: UnOp, operand: Self::Id) -> Self::Id;
    fn build_bool(&mut self, v: bool) -> Self::Id;
    /// 构造整数/long 字面量（常量折叠产物）。`long` 为 true 时带 L 语义。
    fn build_int(&mut self, v: i64, long: bool) -> Self::Id;
    /// 构造二元运算节点（常量折叠 / 取反重写等需要重建比较运算时使用）。
    fn build_bin(&mut self, op: BinOp, l: Self::Id, r: Self::Id) -> Self::Id;
    /// 构造三元表达式 `c ? a : b`（if→ternary 归并）。
    fn build_ternary(&mut self, c: Self::Id, a: Self::Id, b: Self::Id) -> Self::Id;
    /// 构造简单赋值 `target = value`（if→三元赋值归并）。
    fn build_assign(&mut self, target: Self::Id, value: Self::Id) -> Self::Id;
    /// 构造字符串字面量（字符串常量折叠产物）。
    fn build_str(&mut self, s: &str) -> Self::Id;
    /// 构造字符字面量（部分求值产物：`(char)('a'+1)` → 'b'）。
    fn build_char(&mut self, c: char) -> Self::Id;
    /// 深拷贝子树（返回新 Id）。
    fn copy_subtree(&mut self, id: Self::Id) -> Self::Id;

    // ---- 语义查询 ----

    /// 整棵子树的聚合效果（最坏情况）。语言侧应缓存（见 `prepare`）。
    fn effect(&self, id: Self::Id) -> Effect;
    /// 使 `id` 的聚合效果缓存失效（若有）。引擎在同 pass 批量应用编辑后
    /// 沿祖先链调用——祖先的聚合效果含被改子树，必须失效，
    /// 后续 `effect()` 读取回退为按需重算（子缓存仍有效，代价 O(孩子数)）。
    /// 默认空实现：无缓存的语言每次现算，天然正确。
    fn invalidate_effect(&mut self, _id: Self::Id) {}

    /// `id` 子树的区域事件序列（使用索引，prepare 期间预计算）。
    /// 事件序必须等于 scan_region 原递归的遍历序；返回 None 表示该
    /// 节点无索引（未构建/已失效）——scan_region 回退为原递归遍历。
    /// 引擎在应用编辑后沿祖先链调用 invalidate_effect 使索引失效。
    /// 事件索引一致性自检（惰性重建 B3 调试）：默认空实现。
    fn debug_verify_events(&self, _stmt: Self::Id) {}

    fn region_events(
        &self,
        _id: Self::Id,
    ) -> Option<&[crate::kind::RegionEvent<Self::Id, Self::NameKey>]> {
        None
    }
    /// 节点的名字键（VarRef/VarDecl/ForEach/Catch 等命名节点）；
    /// 无名节点返回 None。
    fn var_key(&self, _id: Self::Id) -> Option<Self::NameKey> {
        None
    }

    /// 两个节点是否指向**同一个存储位置**。默认按名字键（Java 的
    /// 作用域信息由前端 facts 提供）；有绑定解析的后端（TS/JS）应覆盖
    /// 为 BindingId 等值，避免同名遮蔽被当成同一变量。
    fn same_binding(&self, a: Self::Id, b: Self::Id) -> bool {
        match (self.var_key(a), self.var_key(b)) {
            (Some(x), Some(y)) => x == y,
            _ => false,
        }
    }
    /// Syntactic VarRef count for `key` inside this statement subtree.
    /// `None` = no fresh index (unbuilt/stale) — callers fall back to a
    /// recursive walk. Indexed languages return `Some(0)` for a statement
    /// that simply does not mention the name.
    fn stmt_var_ref_count(&self, _stmt: Self::Id, _key: Self::NameKey) -> Option<u32> {
        None
    }
    /// Whether a lambda inside this statement subtree captures `key`.
    /// Same `None` contract as [`Self::stmt_var_ref_count`].
    fn stmt_lambda_captures(&self, _stmt: Self::Id, _key: Self::NameKey) -> Option<bool> {
        None
    }
    /// Precomputed statement-level kill event for `key`. `None` = no fresh
    /// index (callers fall back to [`crate::rules::scan_kill_event`]).
    fn stmt_kill_event(&self, _stmt: Self::Id, _key: Self::NameKey) -> Option<StmtKill<Self::Id>> {
        None
    }
    /// Whether the statement syntactically mentions `key` (VarRef) or
    /// declares it (VarDecl/ForEach/Catch). `None` = no index.
    fn stmt_mentions(&self, _stmt: Self::Id, _key: Self::NameKey) -> Option<bool> {
        None
    }
    /// Whether the statement subtree contains an opaque region. `None` =
    /// no index.
    fn stmt_opaque(&self, _stmt: Self::Id) -> Option<bool> {
        None
    }
    /// 节点是否不透明（内部含不可解析原文，读/写集不可证明）：
    /// Java 的 Raw 节点与匿名类体（anon_raw）。区域用量分析的可靠性
    /// 前提——漏判会导致捕获变量被误删（对抗波 4 抓获）。
    fn is_opaque(&self, _id: Self::Id) -> bool {
        false
    }
    /// 节点自身（不含 children）的效果贡献。
    fn own_effect(&self, id: Self::Id) -> Effect {
        match self.kind(id) {
            NodeKind::Literal
            | NodeKind::Paren
            | NodeKind::This
            | NodeKind::Block
            | NodeKind::Empty
            | NodeKind::VarDecl => Effect::Pure,
            NodeKind::VarRef => Effect::MayRead,
            NodeKind::Member => Effect::MayThrow,
            NodeKind::Index | NodeKind::New => Effect::MayThrow,
            NodeKind::Call => Effect::Unknown,
            NodeKind::Assign => Effect::MayWrite,
            NodeKind::Unary => {
                if self.un_op(id).is_some_and(|o| o.is_incdec()) {
                    Effect::MayWrite
                } else {
                    Effect::Pure
                }
            }
            NodeKind::Binary => {
                if self.bin_op(id).is_some_and(|o| o.may_div_zero()) {
                    Effect::MayThrow
                } else {
                    Effect::Pure
                }
            }
            NodeKind::Return | NodeKind::Throw => Effect::MayThrow,
            NodeKind::Try | NodeKind::ForEach | NodeKind::Assert => Effect::MayThrow,
            NodeKind::Catch | NodeKind::NewArray => Effect::MayThrow,
            NodeKind::Synchronized => Effect::MayWrite,
            NodeKind::Raw => Effect::Unknown,
            _ => Effect::Unknown,
        }
    }

    /// 表达式是否为**原始 boolean** 类型（装箱 Boolean 必须返回 false）。
    fn is_bool(&self, id: Self::Id) -> bool;
    /// 表达式是否具有精确整数类型（byte/short/int/long/char），用于算术恒等式守卫。
    fn is_exact_int(&self, id: Self::Id) -> bool;
    /// 是否为语言层的普通局部变量（可安全删除赋值；字段/全局必须 false）。
    fn is_local_var(&self, id: Self::Id) -> bool {
        self.kind(id) == NodeKind::VarRef
    }

    /// 声明（VarDecl 节点）的类型域是否容纳 int 算术结果。窄类型
    /// （Java byte/short/char）的复合赋值含**隐式收窄**
    /// （`b += K` ≡ `b = (byte)(b + K)`）——把 delta 折回声明会产出
    /// 非法（超域常量）或变义（丢静态类型：`char ch = 99` 内联进
    /// println 打数字而非字符）的字面量。默认 true（宽域语言）。
    fn is_long_decl(&self, _decl: Self::Id) -> bool {
        false
    }
    fn is_wide_decl(&self, _decl: Self::Id) -> bool {
        true
    }

    /// 声明是否为**推断类型**（Java 10 `var`）。推断声明剥除 init 后
    /// 变成 `var x;`——非法源码（obf_fuzz 差分抓获）。剥 init 类规则
    /// 必须拒绝。默认 false。
    fn is_inferred_decl(&self, _decl: Self::Id) -> bool {
        false
    }

    /// 声明是否为字符类型。字符类型变量对 **int 字面量内联类型敏感**：
    /// `char c = 98; println(c)` 打印 'b'，而内联成 `println(98)` 打印
    /// 98——静态类型可被 println / 字符串拼接观察。窄域规则（如
    /// local_propagation）须拒绝非 Char 字面量值出字符声明。
    fn is_char_decl(&self, _decl: Self::Id) -> bool {
        false
    }

    /// 局部传播到**成员访问接收位**是否类型不可靠：声明的静态类型与
    /// init 表达式的静态类型在成员解析上可能不等价（Java raw 泛型：
    /// `List l = m(); l.add("x")` 的 raw 擦除收 Object，内联成
    /// `m().add("x")` 后按泛型收 CAP#1 → javac 硬错——mockito
    /// ReturningDefaultValuesTest 抓获）。仅接收位敏感（实参位 raw↔
    /// 泛型双向兼容）。默认 false（无 raw 泛型的语言）。
    fn receiver_propagation_unsound(
        &self,
        _decl: Self::Id,
        _value: Self::Id,
        _use_parent: Option<Self::Id>,
        _use_at_head: bool,
    ) -> bool {
        false
    }

    // ---- 外部事实（front-end facts）----------------------------------
    //
    // 语言无关的「前端断言」词汇：持有 IR/类型/数据流信息的调用方
    //（反编译前端等）对源码层**可见变量与被调成员**的权威陈述。引擎
    // 规则保持形状驱动——事实只用于**放宽守卫**（替代源码层保守扫
    // 描/回退），永不引入源码无法自证的新改写方向，语义保持承诺不
    // 变。默认实现 = 无事实（保守，纯源码模式）。
    //
    // 携带方式由各语言 crate 自定（本 trait 只定义查询面）；事实的
    // 生命周期是**编译单元**——换单元必须清空/替换。

    /// 变量（按名字键）在源码外**无隐藏写**且全部可见写恰为一次
    /// （单一定义）。传播/钻石折叠据此跳过写窗口扫描。
    fn fact_single_def(&self, _key: Self::NameKey) -> bool {
        false
    }
    /// 变量（按名字键）的读点恰为一次（前端权威计数）。传播据此
    /// 免句法引用计数兜底。
    fn fact_single_use(&self, _key: Self::NameKey) -> bool {
        false
    }
    /// 变量（按名字键）的静态类型为原始布尔。类型敏感的布尔折叠
    /// 据此放行 int 形状。
    fn fact_bool_valued(&self, _key: Self::NameKey) -> bool {
        false
    }
    /// 按被调成员名的副作用上限（池级/IR 分析：纯方法调用、无抛
    /// 字段读等）。`None` = 未知（保守）。条件折叠/短路重建据此
    /// 放行含调用的条件。
    fn fact_call_effect(&self, _name: &str) -> Option<Effect> {
        None
    }

    fn bin_op(&self, id: Self::Id) -> Option<BinOp>;
    fn un_op(&self, id: Self::Id) -> Option<UnOp>;
    fn literal(&self, id: Self::Id) -> Option<LitRef<'_>>;
    /// 变量相关名字：VarRef / VarDecl 读写的名字，以及 ForEach / Catch 的**声明绑定名**。
    fn var_name(&self, id: Self::Id) -> Option<&str>;
    /// 成员访问/方法引用的**成员名**（x.f / x.m() / X::m 的 f/m 部分）。
    /// 结构相等性比较用（var_name 只覆盖 VarRef——x.a 与 x.b 曾被误判
    /// 相等 → ternary_fold 删除活分支，Types.java Rewriter.high 抓获）。
    fn member_name(&self, _id: Self::Id) -> Option<&str> {
        None
    }
    /// VarRef 值替换进 cast/instanceof 类型判定位后的**可编译性**裁决
    /// （传播守卫）。引擎只判形状（沿 Paren 链首遇 Cast/InstanceOf，
    /// 见 typed_position）——类型相容性归语言侧：值的声明类型未解析
    /// （自由名——反编译残缺作用域常态）→ 未知类型可 cast 到任何
    /// 引用类型，恒可编译；声明类型与目标类型同名 → 恒合法；其余
    /// 交给语言的类型知识（Java：Object 任一侧放行，否则保守拒绝——
    /// interface/子类关系不可判）。默认 true（无静态类型判定位的语言）。
    fn var_cast_position_ok(&self, _value: Self::Id, _typed: Self::Id) -> bool {
        true
    }
    /// 子树是否含**可提升/条件初始化声明**（JS 的 `if (c) function f(){}`
    /// ——Annex B：绑定被 var 提升但初始化条件化；搬移/删除该声明改变
    /// 语义）。ConstCondition 的 then 解包 / else 丢弃需拒绝。
    /// 默认 false（Java 无嵌套函数声明）。
    fn contains_hoisted_decl(&self, _root: Self::Id) -> bool {
        false
    }
    /// 块展开是否改变 Annex B 块级函数声明的提升语义（TS 判直接孩子；
    /// Java 恒 false）。
    fn block_hoists_decl(&self, _block: Self::Id) -> bool {
        false
    }
    /// 是否为**标签模板**节点（tagged template literal）。标签位的
    /// `this` 绑定取决于 tag 是 Reference 还是值——折臂/短路改写会
    /// 改变 this（`(true ? obj.f : null)\`\`` vs `obj.f\`\``）。
    fn is_tagged_template(&self, _id: Self::Id) -> bool {
        false
    }
    /// 赋值目标位的 Paren 是否**语义显著**（JS 具名求值：`(fn) = function(){}`
    /// 不推断 name，删括号会改变 Function.prototype.name）。
    fn assign_target_paren_required(&self, _inner: Self::Id) -> bool {
        false
    }
    /// 局部传播的值形态是否**稳定**（复制到使用点不改变求值时间语义）。
    /// Java：任意表达式（类型系统/纯读假设——引擎既有扫描保证）。
    /// JS：仅字面量（全局/闭包变量可在外层被改写；`var local2 = y; …
    /// y 变化 …; return {local2}` 内联会读到新值——Test262 eval 家族抓获）。
    fn local_propagation_value_ok(&self, _decl: Self::Id, _value: Self::Id) -> bool {
        true
    }
    /// 语句子树是否含**规则不可见**的原文区域（Raw/类表达式/解构模式）。
    fn stmt_has_opaque_region(&self, _stmt: Self::Id) -> bool {
        false
    }
    /// 值子树是否读取**可能未解析**的名字（未声明全局 → 求值抛
    /// ReferenceError）。死存储/死声明删除会把这次抛异常一并删掉
    ///（JS `var o = {notDefined};`——Test262 object/not-defined 抓获）。
    fn value_may_throw_unresolved(&self, _value: Self::Id) -> bool {
        false
    }
    /// 声明删除规则（dead_decl）是否允许删除该声明。Java：允许；
    /// TS：仅 `var`（let/const/using 的 TDZ/词法遮蔽/dispose 语义会因
    /// 删除而改变——Test262 annexB block-decl 家族抓获）。
    fn dead_decl_allowed(&self, _decl: Self::Id) -> bool {
        true
    }
    /// 函数边界（λ 捕获扫描用）：Java 为 Lambda；TS 还含函数声明
    /// （FuncStmt——`function i(){ use(x) }` 对 x 是按引用捕获）。
    fn is_function_like(&self, id: Self::Id) -> bool {
        self.kind(id) == NodeKind::Lambda
    }
    /// Paren 的**语法必要性**（paren_removal 守卫）：该内层形态在
    /// 紧位置（二元/一元运算数位）是否必须带括号——产生式约束，
    /// 优先级序表达不了。JS：箭头/对象字面量/Raw 形态在运算数位
    /// 语法必需括号（`a ?? (() => true)`）。默认 false（打印层
    /// 优先级模型完备的语言——如 Java）。
    fn grammar_paren_required(&self, _inner: Self::Id) -> bool {
        false
    }
    /// `!!x ≡ x` 恒等式在**本语言**是否成立（DoubleNot 规则守卫）。
    /// 蕴含 x 为布尔值。Java：`!` 操作数必须 boolean——可编译的 !!x
    /// 其 x 恒 boolean → 恒成立。JS：!x 是布尔胁迫（!!0 === false
    /// ≠ 0）→ 仅语法级布尔（is_bool）成立。默认取 is_bool（保守）。
    fn double_not_sound(&self, operand: Self::Id) -> bool {
        self.is_bool(operand)
    }
    /// 节点**负载**等价（NodeData 中的非孩子字段：New.ty/anon_raw、
    /// Cast.ty、InstanceOf.ty/bind、Lambda.params_raw、VarDecl.ty 等）。
    /// structurally_equal 用——负载不比较曾把 `cond ? new FairSync() :
    /// new NonfairSync()`（参数相同、类型不同）判相等折叠：JDK 语料
    /// 90 处真实误折（ReentrantReadWriteLock 锁公平性、DirectByteBuffer
    /// 字节序、instanceof 守卫 cast → CCE，5 例运行时行为改变证实）。
    fn payload_equal(&self, _a: Self::Id, _b: Self::Id) -> bool {
        true
    }
    /// 名字是否是本单元声明的字段（字段读的可移动性判定——局部/参数
    /// 不可被调用改变，字段可以）。默认 false（名字未声明 → 当作可移动，
    /// 手工构建的 AST 无作用域解析时不会误伤）。
    fn is_field_name(&self, _name: &str) -> bool {
        false
    }
    /// 子树内是否含**模式绑定**（Java instanceof pattern：绑定作用域按
    /// JLS 6.3 流可达性可越出语句本身到 enclosing block——块展平/语句
    /// 移动类规则须拒绝。默认 false（无模式绑定的语言）。
    fn has_pattern_bindings(&self, _root: Self::Id) -> bool {
        false
    }
    /// 赋值运算（`=` 之外的复合赋值也在此表达；None 表示简单赋值）。
    fn assign_op(&self, _id: Self::Id) -> Option<BinOp> {
        None
    }

    // ---- 字面量折叠语义（数值/字符串语义全权归属语言侧）----
    //
    // 引擎规则只做**形态**匹配（双字面量、算符类别、代价门槛）；一切
    // 数值语义——宽度与环绕、除零策略、移位掩码、字符串拼接的强制
    // 转换规则——由这些钩子的语言实现决定。默认全部不折（保守）。

    /// 字面量二元折叠：算术/位运算/移位（`+ - * / % << >> >>> & | ^`）
    /// 与字符串拼接。操作数为字面量节点 id；返回折叠产物节点。
    fn fold_lit_bin(&mut self, _op: BinOp, _l: Self::Id, _r: Self::Id) -> Option<Self::Id> {
        None
    }

    /// 字面量比较折叠（如 `1 < 2`）。可比较的字面量种类与字符串比较
    /// 语义（引用比较 vs 值比较）由语言侧决定；返回布尔结果。
    fn fold_lit_cmp(&mut self, _op: BinOp, _l: Self::Id, _r: Self::Id) -> Option<bool> {
        None
    }

    /// 负数值字面量的取反（`-(-lit)` 外层负消除）。宽度溢出时必须
    /// 返回 None 拒绝折叠（如 Java i32 的 `-(-2147483648)`）。
    /// 默认实现按 i64 拒绝 `i64::MIN` 取反（防 debug panic / release 回绕）。
    fn fold_lit_neg(&mut self, v: i64, _wide: bool) -> Option<i64> {
        v.checked_neg()
    }

    /// 常量重结合合并：`(x op1 K1) op2 K2` 的常量合并结果。
    /// 语言侧负责宽度回绕（Java i32 的 `K1+K2` 溢出必须回绕，否则
    /// 产物是非法字面量）。
    fn reassoc_delta(
        &mut self,
        _op1: BinOp,
        _k1: i64,
        _op2: BinOp,
        _k2: i64,
        _wide: bool,
    ) -> Option<ReassocOutcome<Self::Id>> {
        None
    }

    /// 每轮扫描前由引擎调用；语言侧在此刷新缓存（效果表、变量类型表等）。
    /// `root` 是本轮简化的根（通常是方法体），语言侧可据此做作用域分析。
    fn prepare(&mut self, _root: Self::Id) {}

    /// 节点成本权重（用于“改写必须严格降本”的门槛）。
    fn cost_weight(&self, kind: NodeKind) -> u64 {
        crate::cost::default_weight(kind)
    }
}

/// [`Lang::reassoc_delta`] 的合并结果。
#[derive(Clone, Copy, Debug)]
pub enum ReassocOutcome<Id> {
    /// 合并为中性元（`(x+K1)-K1` 类）→ 直接替换为 `x`。
    Neutral,
    /// 合并后的常量字面量节点 + 建议算符（`x op lit`；负常量由语言侧
    /// 决定用 `Sub` 正字面量还是 `Add` 负字面量表达）。
    Lit(Id, BinOp),
}