Rust 编译器与运行时揭秘

第7章 Trait 静态分发：零成本抽象的编译器实现

作者杨艺韬 · 14,309 字

第7章 Trait 静态分发：零成本抽象的编译器实现

“零成本抽象不是没有代价——代价在编译期全部付清。理解编译器如何在编译期解析每一个 trait 方法调用，你就理解了 Rust 性能承诺的底层机制。”

本章要点

静态分发的本质：编译器在编译期将 trait 方法调用解析为确定的函数地址，运行时零间接跳转
Trait 选择算法：SelectionContext 通过候选组装、求值筛选、确认三阶段找到唯一匹配的 impl
与单态化的衔接：第6章的单态化生成代码副本，本章的 trait 选择决定每份副本中调用哪个 impl
Impl 查找优化：TraitImpls 使用 SimplifiedType 索引实现快速筛选
一致性规则：编译器在 coherence 阶段证明全局不存在重叠 impl
特化：nightly 特性，允许更具体的 impl 覆盖更一般的 impl
关联类型解析：投影机制将 <T as Trait>::Assoc 在编译期规范化为具体类型
性能分析：静态分发生成的汇编与手写代码完全一致

7.1 静态分发的本质：编译期方法解析

当你写下带有 trait bound 的泛型函数时，编译器面临核心问题：x.method() 到底调用哪个函数？

trait Shape { fn area(&self) -> f64; }

struct Circle { radius: f64 }
struct Rectangle { width: f64, height: f64 }

impl Shape for Circle {
    fn area(&self) -> f64 { std::f64::consts::PI * self.radius * self.radius }
}
impl Shape for Rectangle {
    fn area(&self) -> f64 { self.width * self.height }
}

fn print_area<T: Shape>(shape: &T) {
    println!("面积: {}", shape.area());  // 调用哪个 area？
}

fn main() {
    print_area(&Circle { radius: 5.0 });               // 编译器知道 T=Circle
    print_area(&Rectangle { width: 3.0, height: 4.0 }); // 编译器知道 T=Rectangle
}

在 C++ 虚函数中，shape.area() 在运行时通过 vtable 查找。而 Rust 的静态分发中，编译器在编译期就完成了全部决策——调用点 A 直接生成对 <Circle as Shape>::area 的调用，调用点 B 直接生成对 <Rectangle as Shape>::area 的调用。

graph TB
    A["trait 方法调用<br/>shape.area()"] --> B{"编译器判断分发方式"}

    B -->|"泛型 / impl Trait<br/>编译期已知具体类型"| C["静态分发路径"]
    B -->|"dyn Trait<br/>类型被擦除"| D["动态分发路径"]

    C --> C1["Trait 选择 → 候选组装 → 求值筛选 → 确认"]
    C1 --> C2["单态化：生成具体函数"]
    C2 --> C3["直接调用指令 call concrete_fn"]

    D --> D1["构建 fat pointer + 运行时查 vtable"]
    D1 --> D2["间接调用指令 call [vtable+offset]"]

    style C fill:#059669,color:#fff,stroke:none
    style C3 fill:#10b981,color:#fff,stroke:none
    style D fill:#d97706,color:#fff,stroke:none
    style D2 fill:#f59e0b,color:#fff,stroke:none

7.2 Trait 选择算法：三阶段流程

Trait 选择是静态分发的核心，回答根本问题：对于给定的类型 T 和 trait Trait，应该使用哪个 impl？ 在 rustc 中由 SelectionContext 驱动，分为三阶段。

7.2.1 SelectionContext 与候选种类

// compiler/rustc_trait_selection/src/traits/select/mod.rs
pub struct SelectionContext<'cx, 'tcx> {
    pub infcx: &'cx InferCtxt<'tcx>,          // 类型推断上下文
    freshener: TypeFreshener<'cx, 'tcx>,       // 递归检测用
    intercrate_ambiguity_causes: Option<FxIndexSet<IntercrateAmbiguityCause<'tcx>>>,
    query_mode: TraitQueryMode,
}

rustc 定义了丰富的候选种类体系：

// compiler/rustc_middle/src/traits/select.rs
pub enum SelectionCandidate<'tcx> {
    SizedCandidate,                                     // 内建 Sized
    BuiltinCandidate,                                   // 内建 Copy/Clone 等
    ParamCandidate(ty::PolyTraitPredicate<'tcx>),       // where 子句
    ImplCandidate(DefId),                               // 用户 impl
    AutoImplCandidate,                                  // Send/Sync 自动实现
    ProjectionCandidate { idx: usize, kind: AliasBoundKind }, // 投影 bound
    ClosureCandidate { is_const: bool },                // 闭包 Fn trait
    ObjectCandidate(usize),                             // dyn Trait supertrait
    // ... CoroutineCandidate, FutureCandidate 等
}

graph LR
    subgraph "阶段1: 候选组装"
        A1["收集 impl/where子句/内建"] --> A2["SelectionCandidateSet"]
    end
    subgraph "阶段2: 求值筛选"
        B1["evaluate_candidate"] --> B2["winnow_candidates"]
        B2 --> B3["选出唯一候选"]
    end
    subgraph "阶段3: 确认"
        C1["统一类型参数 + 检查嵌套义务"] --> C2["ImplSource"]
    end
    A2 --> B1
    B3 --> C1
    style A2 fill:#3b82f6,color:#fff,stroke:none
    style B3 fill:#8b5cf6,color:#fff,stroke:none
    style C2 fill:#059669,color:#fff,stroke:none

7.2.2 阶段一：候选组装

assemble_candidates 根据 trait 种类采用不同策略。对于 Sized/Copy 等语言级 trait 使用内建规则，对于一般 trait 则遍历 impl 和 where 子句：

// candidate_assembly.rs（简化）
pub(super) fn assemble_candidates<'o>(
    &mut self, stack: &TraitObligationStack<'o, 'tcx>,
) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
    // Self 是推断变量？直接返回歧义
    if obligation.predicate.skip_binder().self_ty().is_ty_var() {
        return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
    }
    let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };

    match tcx.as_lang_item(def_id) {
        Some(LangItem::Sized) => self.assemble_builtin_sized_candidate(..),
        Some(LangItem::Copy | LangItem::Clone) => {
            self.assemble_candidates_from_impls(obligation, &mut candidates);
            self.assemble_builtin_copy_clone_candidate(..);
        }
        _ => {
            self.assemble_candidates_from_impls(obligation, &mut candidates);
            self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
        }
    }
    Ok(candidates)
}

优先级规则至关重要：where 子句候选优先于 impl 候选（保证泛型上下文可预测），内建候选优先于用户 impl，更具体 impl 优先于一般 impl（特化基础）。

7.2.3 阶段二：求值与筛选

编译器对每个候选求值，保留”可能适用”的，再从中选出最佳：

// select/mod.rs（简化关键逻辑）
fn candidate_from_obligation_no_cache(&mut self, stack: &TraitObligationStack<'o, 'tcx>) {
    let candidate_set = self.assemble_candidates(stack)?;
    let mut candidates = self.filter_impls(candidates, stack.obligation);

    if candidates.len() == 1 { return candidates.pop().unwrap(); }

    // 多个候选：逐一求值，过滤掉不适用的
    let evaluated: Vec<_> = candidates.into_iter()
        .filter_map(|c| {
            let eval = self.evaluate_candidate(stack, &c).ok()?;
            eval.may_apply().then(|| EvaluatedCandidate { candidate: c, evaluation: eval })
        }).collect();

    // winnow_candidates 从中选出唯一最佳候选
    self.winnow_candidates(has_non_region_infer, preference_mode, evaluated)
}

TraitObligationStack 维护调用栈检测递归。对于 auto trait（Send/Sync），coinductive 循环被允许——reached_depth 字段追踪循环深度。

7.2.3-bis 源码核对：winnow_candidates 的 5 层优先级 ladder

§7.2.3 提到 winnow_candidates 选最佳候选——但没展开它的内部决策树。打开 compiler/rustc_trait_selection/src/traits/select/mod.rs:1841+ 能看到它实现了一个 5 层优先级阶梯：

fn winnow_candidates(
    &mut self,
    has_non_region_infer: bool,
    candidate_preference_mode: CandidatePreferenceMode,
    mut candidates: Vec<EvaluatedCandidate<'tcx>>,
) -> Option<SelectionCandidate<'tcx>> {
    if candidates.len() == 1 {
        return Some(candidates.pop().unwrap().candidate);
    }

    // Level 1: SizedCandidate 优先于一切（唯一例外的内建 lang item）
    let mut sized_candidates = candidates.iter().filter(|c| matches!(c.candidate, SizedCandidate));
    if let Some(sized_candidate) = sized_candidates.next() {
        debug_assert_eq!(sized_candidates.next(), None);
        if sized_candidate.evaluation.must_apply_modulo_regions() {
            return Some(sized_candidate.candidate.clone());
        } else {
            return None;
        }
    }

    // Level 2: 去重 ParamCandidate（同 trait_ref 多次出现去掉一次）
    'search_victim: loop { ... }

    // Level 3: ProjectionCandidate (alias bounds) 在 marker mode 优先
    if matches!(candidate_preference_mode, CandidatePreferenceMode::Marker) {
        ...
    }

    // Level 4: 非 global ParamCandidate（where-bounds）
    let is_global = |c| c.is_global() && !c.has_bound_vars();
    ...

    // Level 5: alias bounds 比 blanket impl 优先
    ...
}

这 5 层阶梯是 Rust trait 选择的”政策实现”——每一层对应一条长期沉淀的语言决策：

Level 1：Sized 优先——Sized 是 Rust 类型系统的基石、几乎所有泛型 bound 都默认带 T: Sized。让 SizedCandidate 优先选中能避免和用户写的 where-bound 冲突。debug_assert_eq!(sized_candidates.next(), None) 断言永远只有一个 Sized candidate——多个就是 impl 重叠（上层 coherence 已经保证不会发生）。

Level 2：ParamCandidate 去重——'search_victim: loop 是个奇怪的标签命名，但功能清晰：找到任何一对相等的 ParamCandidate 就 remove 一个、重新开始循环。super-trait 展开会产生重复的 trait_ref——trait Foo: Bar 和 trait Bar 都给当前 self type 提供 Bar 的 candidate——不去重会导致后续 ambiguity 报错。

Level 3：Marker mode 下 alias bounds 优先——auto trait（Send/Sync）、Sized、default trait 等”标记类”trait 用 alias bound 优先于 where bound。这条规则的存在是为了让 trait object 的 super-trait 选择行为可预测。

Level 4：non-global ParamCandidate 优先于 global——T: Trait (with bound vars) 优先于 i32: Trait (no bound vars)。这条规则源自 RFC #50825——保证 generic 上下文里 where-bound 总能被选中、不被同样在 std 里的 global impl 抢走。注释里直接写了 “see #50825 for why we need to handle global where-bounds like this”——这是 Rust 团队多次踩坑后才确立的规则。

Level 5：alias bound > blanket impl——这条注释直接写明 “fairly arbitrary but once again necessary for backwards compatibility”。Rust 编译器里 backwards compatibility 是头号约束——任何看起来”奇怪”的优先级规则背后都有一个 stable 之后不能改的 RFC。

这 5 层 ladder 的存在反映了 Rust 类型系统经过 10 年磨合的政策结晶——每一条都对应过 issue、争论、RFC——最终落到这 100 行代码里。协议层的 RFC 实现需要一辈子的时间——从这段代码能感受到。

7.2.3-ter 源码核对：assemble_candidates_from_impls 的三层 fast reject

§7.2.2 给的 candidate 组装是高层视角。真实 assemble_candidates_from_impls（candidate_assembly.rs:600-643）有三层 fast reject 在创建 candidate 前就过滤掉不可能匹配的 impl：

fn assemble_candidates_from_impls(
    &mut self,
    obligation: &PolyTraitObligation<'tcx>,
    candidates: &mut SelectionCandidateSet<'tcx>,
) {
    let drcx = DeepRejectCtxt::relate_rigid_infer(self.tcx());
    let obligation_args = obligation.predicate.skip_binder().trait_ref.args;
    self.tcx().for_each_relevant_impl(
        obligation.predicate.def_id(),
        obligation.predicate.skip_binder().trait_ref.self_ty(),
        |impl_def_id| {
            // 第 1 层：DeepRejectCtxt fast reject
            let impl_trait_header = self.tcx().impl_trait_header(impl_def_id);
            if !drcx.args_may_unify(
                obligation_args,
                impl_trait_header.trait_ref.skip_binder().args,
            ) {
                return;  // 类型参数完全不可能 unify、跳过
            }

            // 第 2 层：default impl 永远不算 candidate
            if self.tcx().defaultness(impl_def_id).is_default() {
                return;
            }

            // 第 3 层：reject_fn_ptr_impls 特殊路径
            if self.reject_fn_ptr_impls(impl_def_id, obligation, ...) {
                return;
            }

            // 通过三层 reject 后才真正 probe + match
            self.infcx.probe(|_| {
                if let Ok(_args) = self.match_impl(impl_def_id, impl_trait_header, obligation) {
                    candidates.vec.push(ImplCandidate(impl_def_id));
                }
            });
        },
    );
}

三层 reject 的工程价值——让 trait selection 在大型项目里保持高效：

Layer 1：DeepRejectCtxt + args_may_unify——通过快速类型形状比较判断”两个 trait_ref 的参数是否有可能 unify”。比如 Vec<i32>: Foo<String> 和 impl<T> Foo<U> for Vec<T> 的参数 String 和 U 是否能 unify？deep reject 用 O(深度) 的快速形状匹配判定——避免昂贵的 full unification。

Layer 2：default impl 跳过——#[default] impl Trait for T { ... } 是 specialization 特性。default impl 永远不是 trait 选择的”证明”——总有一个非 default 的 impl 会 also apply。所以 default impl 不进 candidate 集合——这条规则确保 trait selection 在 specialization 启用时不会陷入 default impl 的歧义。

Layer 3：fn pointer impl 特殊路径——reject_fn_ptr_impls（candidate_assembly.rs:650+）专门拒绝 impl<T: FnPtr> Trait for T 这种 blanket impl 在 self type 不是 FnPtr 时被错误考虑。注释解释了原因（第 645-648 行）：“avoids reporting that the self type does not implement FnPtr, when we wanted to report that it doesn’t implement Trait”——改善编译器错误消息的可读性——是给用户的”错误诊断质量”投入。

通过三层 reject 后才走 infcx.probe + match_impl——这是真正昂贵的全 unification 步骤。rustc 的 trait selection 通过这种”fast reject + slow match”的组合让大型项目编译时间可控——一个有 100 个 impl 的 trait 在某次 obligation 求解时可能只有 2-3 个 impl 通过 reject、走 match——99% 的工作被剔除在 fast path 里。

读懂这种 fast/slow path 划分对你写自己的代码也有启发——编译器优化经常表现为”先做廉价检查、后做昂贵计算”——你的业务代码遇到 N 选 1 的搜索时也应该先做 cheap filter。

7.2.4 阶段三：确认

选出唯一候选后，确认阶段统一类型参数并收集嵌套义务：

// select/confirmation.rs（关键分支）
pub(super) fn confirm_candidate(&mut self, obligation: &PolyTraitObligation<'tcx>,
    candidate: SelectionCandidate<'tcx>) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
    Ok(match candidate {
        ParamCandidate(param) => ImplSource::Param(
            self.confirm_param_candidate(obligation, param.map_bound(|t| t.trait_ref))
        ),
        ImplCandidate(impl_def_id) => ImplSource::UserDefined(
            self.confirm_impl_candidate(obligation, impl_def_id)
        ),
        BuiltinCandidate => ImplSource::Builtin(BuiltinImplSource::Misc,
            self.confirm_builtin_candidate(obligation)
        ),
        // ... 闭包、协程等其他候选的确认
    })
}

7.2.5 源码核对：evaluate_candidate 的 ModuloRegions 缓存策略

evaluate_candidate（select/mod.rs:1279-1310）的最后几行藏着一个为 lifetime erasure 服务的特殊缓存逻辑：

// If we erased any lifetimes, then we want to use
// `EvaluatedToOkModuloRegions` instead of `EvaluatedToOk`
// as your final result. The result will be cached using
// the freshened trait predicate as a key, so we need
// our result to be correct by *any* choice of original lifetimes,
// not just the lifetime choice for this particular (non-erased)
// predicate.
// See issue #80691
if stack.fresh_trait_pred.has_erased_regions() {
    result = result.max(EvaluatedToOkModuloRegions);
}

这条 5 行代码处理了 GitHub issue #80691 的具体 bug——caching with lifetime erasure 的 soundness 问题。当 trait predicate 里有 lifetime（比如 &'a T: Foo）被擦除成 freshener variable 时，求值结果如果是 EvaluatedToOk——会被缓存——下次同样 freshener 的 query 直接返回 cache。

但 EvaluatedToOk 暗示”无 lifetime 限制也成立”——这对带具体 lifetime 的原 predicate 来说可能是错的（具体 lifetime 才让它成立）。所以代码用 result.max(EvaluatedToOkModuloRegions) 把结果降级到 ModuloRegions——明确告诉 cache 消费者”这个结果不保证 lifetime 维度的正确性、需要再做 region check”。

这种”为 cache key 的不精确性付出运行时代价”是 rustc 类型检查的常见 pattern——lifetime 信息不进 cache key（否则 cache 命中率太低）、但结果要标注”可能需要后续 region 验证”。Issue #80691 链接是这条代码的”血书”——一个真实 bug 让团队学到这条规则。

7.2.6 源码核对：can_use_global_caches 与 evaluation_cache 的双层缓存

evaluate_candidate 后面的 check_evaluation_cache / insert_evaluation_cache（select/mod.rs:1312-1360）实现了一个双层缓存：

fn check_evaluation_cache(...) -> Option<EvaluationResult> {
    if self.can_use_global_caches(param_env, trait_pred) {
        let key = (infcx.typing_env(param_env), trait_pred);
        if let Some(res) = tcx.evaluation_cache.get(&key, tcx) {
            Some(res)   // ← global cache hit
        } else {
            None
        }
    } else {
        self.infcx.evaluation_cache.get(&(param_env, trait_pred), tcx)  // ← local cache
    }
}

fn insert_evaluation_cache(...) {
    // Avoid caching results that depend on more than just the trait-ref
    if result.is_stack_dependent() {
        return;
    }

    if self.can_use_global_caches(param_env, trait_pred) {
        tcx.evaluation_cache.insert(...)   // ← 写到 global
    } else {
        self.infcx.evaluation_cache.insert(...)   // ← 写到 local
    }
}

两层缓存的语义：

Global cache（tcx.evaluation_cache）：跨编译单元、跨 query 复用。条件是 trait_pred 不依赖任何 inference variable（即 “普适真理”）——比如 Vec<i32>: Clone 是真理、可以 global 缓存。

Local cache（infcx.evaluation_cache）：只在当前 InferCtxt 范围有效。当 trait_pred 含 inference variable（比如 Vec<?T>: Clone）——结果依赖 ?T 怎么 instantiate——只能 local 缓存。

is_stack_dependent() 是另一道防线——如果求值过程触发了 cycle detection、结果由 cycle 当前状态决定——完全不缓存（避免缓存”半完成”的递归结果）。

这种”多级 cache + 严格 invalidation 条件”是 rustc 性能的支柱之一——一个大型 Rust crate 编译时 trait selection 可能被调用百万次、绝大多数都命中 cache。没有这套缓存、Rust 编译时间至少翻 5 倍。

读到这一层你会理解为什么 Rust 团队反复警告 “generic 滥用会让编译时间炸”——每一个新的 generic instantiation 都增加了 inference variable、降低 cache 命中率、要走 expensive 的 evaluation 路径。性能的隐形成本在 trait system 里被精算——你的代码风格直接影响编译速度。

7.2.7 源码核对：confirm_impl_candidate 的 rematch + ensure_sufficient_stack

§7.2.4 讲了确认阶段的整体流程。confirm_impl_candidate（confirmation.rs:428-449）的真实实现展示了两个工程细节：

fn confirm_impl_candidate(
    &mut self,
    obligation: &PolyTraitObligation<'tcx>,
    impl_def_id: DefId,
) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
    debug!(?obligation, ?impl_def_id, "confirm_impl_candidate");

    // First, create the generic parameters by matching the impl again,
    // this time not in a probe.
    let args = self.rematch_impl(impl_def_id, obligation);
    debug!(?args, "impl args");
    ensure_sufficient_stack(|| {
        self.vtable_impl(
            impl_def_id,
            args,
            &obligation.cause,
            obligation.recursion_depth + 1,
            obligation.param_env,
            obligation.predicate,
        )
    })
}

两条工程细节：

1、rematch_impl 不在 probe 里——§7.2.3-ter 提过 assemble_candidates_from_impls 用 infcx.probe(|_| match_impl(...)) 做匹配——probe 会回滚 inference 状态。confirm 阶段需要真正应用 unification——所以重新 match 一次（不在 probe 里）、让推断结果固化。

这种”先在 probe 里探测、确认是这个 candidate 后再 commit”的双 match pattern 确保 trait selection 不会留下 inference 副作用——如果某个 candidate 只是被求值评估、不是最终选中的——所有 inference 变量恢复初始状态。否则 trait selection 就成了 inference state mutation 的源头、不可预测。

2、ensure_sufficient_stack(|| ...)——这是 rustc 防 stack overflow 的标准 pattern。复杂的 trait 求解（特别是带有大量嵌套 obligation 的）能让递归深度达数百层——超过 OS 默认的 8MB 栈会段错误。ensure_sufficient_stack 会检测当前栈剩余、不够时切换到 stacker crate 提供的辅助栈——让递归继续而不 OOM。

任何写复杂 AST 处理 / 编译器 / 类型检查 / 树遍历代码的 Rust 项目都应该考虑用 stacker crate——Rust 默认 8MB 栈对深度递归不够、必须主动管理。rustc 在 trait selection、name resolution、HIR lowering 等多处用 ensure_sufficient_stack——是它能处理大型 codebase 的基础。

vtable_impl（confirmation.rs:451-481）紧接其后——构造完整的 ImplSource、把所有 nested obligation 收集进 impl_obligations。这些 nested obligation 会被加入 obligation queue、继续递归求解——形成 trait selection 的”波浪式”展开。每个 nested obligation 又走一遍三阶段流程——整个 trait system 是 fixed-point computation——直到所有 obligation 都求解完才停止。

7.3 Impl 查找：两级索引的高效设计

一个 trait 可能有成百上千个 impl（如 Display、From）。编译器不能逐一做完整统一检查。

7.3.1 TraitImpls 数据结构

rustc 使用精巧的两级索引：

// compiler/rustc_middle/src/ty/trait_def.rs
pub struct TraitImpls {
    blanket_impls: Vec<DefId>,                              // impl<T: Bound> Trait for T
    non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>, // 按类型"指纹"索引
}

SimplifiedType 是类型的粗粒度指纹：i32 → Int(I32)，Vec<String> → Adt(vec_def_id)，类型参数 T → 无法简化（归入 blanket）。

7.3.2 for_each_relevant_impl：快速筛选

// compiler/rustc_middle/src/ty/trait_def.rs
pub fn for_each_relevant_impl(self, trait_def_id: DefId, self_ty: Ty<'tcx>, mut f: impl FnMut(DefId)) {
    let impls = self.trait_impls_of(trait_def_id);
    // blanket impls 总是潜在候选
    for &impl_def_id in impls.blanket_impls.iter() { f(impl_def_id); }
    // non-blanket impls：按 SimplifiedType 过滤
    if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsRigid) {
        if let Some(impls) = impls.non_blanket_impls.get(&simp) {
            for &impl_def_id in impls { f(impl_def_id); }
        }
    } else {
        // 无法简化（推断变量等）：检查所有
        for &impl_def_id in impls.non_blanket_impls.values().flatten() { f(impl_def_id); }
    }
}

查找 Vec<i32>: Display 时，Vec<i32> 简化为 Adt(vec_def_id)，只检查 Self 类型同为 Vec 的 impls，impl Display for i32 等无关 impl 被直接跳过。

注意 TreatParams 的不对称：构建索引时用 InstantiateWithInfer（使 blanket impl 正确归类），查询时用 AsRigid（精确匹配）。如果把 impl<T> Trait for T 中的 T 也简化了，就会错误地放入某个具体类型的桶中，导致查找遗漏。

7.3.3 impl 索引的构建

impl 索引通过查询系统 trait_impls_of 懒加载并缓存。构建时遍历当前 crate 和所有依赖 crate 的 impl：

// compiler/rustc_middle/src/ty/trait_def.rs
pub(super) fn trait_impls_of_provider(tcx: TyCtxt<'_>, trait_id: DefId) -> TraitImpls {
    let mut impls = TraitImpls::default();
    // 从依赖 crate 的元数据收集
    if !trait_id.is_local() {
        for &cnum in tcx.crates(()).iter() {
            for &(impl_def_id, simplified_self_ty) in
                tcx.implementations_of_trait((cnum, trait_id)).iter() {
                match simplified_self_ty {
                    Some(st) => impls.non_blanket_impls.entry(st).or_default().push(impl_def_id),
                    None => impls.blanket_impls.push(impl_def_id),
                }
            }
        }
    }
    // 从当前 crate 收集，对 Self 类型做 simplify_type 分类
    for &impl_def_id in tcx.local_trait_impls(trait_id) {
        let impl_self_ty = tcx.type_of(impl_def_id.to_def_id()).instantiate_identity();
        match fast_reject::simplify_type(tcx, impl_self_ty, TreatParams::InstantiateWithInfer) {
            Some(st) => impls.non_blanket_impls.entry(st).or_default().push(impl_def_id.to_def_id()),
            None => impls.blanket_impls.push(impl_def_id.to_def_id()),
        }
    }
    impls
}

7.3.4 源码核对：for_each_relevant_impl 的 blanket vs non_blanket 双索引

§7.3 提了 TraitImpls 的两级索引。打开 compiler/rustc_middle/src/ty/trait_def.rs:150-219，真实的数据结构和遍历逻辑值得逐行读：

pub struct TraitImpls {
    blanket_impls: Vec<DefId>,
    /// Impls indexed by their simplified self type, for fast lookup.
    non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>,
}

pub fn for_each_relevant_impl(
    self,
    trait_def_id: DefId,
    self_ty: Ty<'tcx>,
    mut f: impl FnMut(DefId),
) {
    let impls = self.trait_impls_of(trait_def_id);

    // 第 1 步：所有 blanket impls 都要检查
    for &impl_def_id in impls.blanket_impls.iter() {
        f(impl_def_id);
    }

    // 第 2 步：non_blanket impls 走 SimplifiedType 索引
    if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsRigid) {
        if let Some(impls) = impls.non_blanket_impls.get(&simp) {
            for &impl_def_id in impls {
                f(impl_def_id);
            }
        }
    } else {
        // self_ty 无法 simplify（比如是 inference variable）→ 必须扫所有 non_blanket
        for &impl_def_id in impls.non_blanket_impls.values().flatten() {
            f(impl_def_id);
        }
    }
}

四条工程 insight：

1、blanket vs non-blanket 的语义区分：

blanket impl：impl<T> Trait for T where T: Bound 这种”对几乎所有类型都适用”的 impl——self type 是个 type parameter。
non-blanket impl：impl Trait for ConcreteType 这种”只对特定类型”的 impl——self type 是具体类型或带具体头部的复合类型。

两者数据结构完全不同——blanket 用 Vec（数量少、要全扫）、non-blanket 用 SimplifiedType-indexed HashMap（数量多、按 self type 头部精确查找）。这种”按数量级和访问模式分别用不同数据结构”的设计是性能工程的标准做法。

2、fast_reject::simplify_type(.., TreatParams::AsRigid)——把任意类型简化成 SimplifiedType（比如 Vec<i32> → Adt(Vec)、&str → Ref(Str)）。SimplifiedType 是个比 full Type 小得多的 enum——能直接做 hash key。

注释里的精彩 insight（第 202-205 行）：

“This way, when searching for some impl for T: Clone, we do not look at any impls whose outer level is not a parameter or projection. Especially for things like T: Clone this is incredibly useful as we would otherwise look at all the impls of Clone for Option<T>, Vec<T>, ConcreteType and so on.”

——Clone 有几百个具体类型的 impl，按 self type 索引让 Option<T>: Clone 的查询只看 Option 那个 bucket、不扫 Vec/HashMap/etc。性能差几个数量级。

3、TreatParams::AsRigid vs InstantiateWithInfer——查询时用 AsRigid（type parameter 当 rigid 类型）、插入时用 InstantiateWithInfer（type parameter 当 inference 变量）。两个语义的反对称——查询时倾向严格 reject（“这个 impl 一定能匹配吗”）、插入时倾向宽松 accept（“这个 impl 可能匹配什么”）——保证了 sound（不会漏掉真匹配）和精确（不会误带不匹配）的平衡。

4、else 分支的 fallback：当 self_ty 无法 simplify（最常见是它是个 inference variable）——必须扫所有 non_blanket impls。这是查询性能的最差情况——所以 rustc 反复鼓励用户早做类型注解——let x: Vec<i32> = ... 比 let x = ...; let _: Vec<i32> = x; 在编译时间上有差别。

注释里的 FIXME（第 191-195 行）暴露了一个长期 known issue——这个查询依赖 trait 的所有 impl 集合、对增量编译不友好。任何一个新 impl 加进来都让 cache invalidate。改善方向（separate blanket / non-blanket query）已经被注明、等待未来重构。

7.4 与单态化的衔接

第6章的单态化为每个具体类型生成函数副本。trait 选择决定副本中的方法调用指向哪里。衔接点在 resolve_associated_item：

// compiler/rustc_ty_utils/src/instance.rs
fn resolve_associated_item<'tcx>(tcx: TyCtxt<'tcx>, trait_item_id: DefId,
    typing_env: ty::TypingEnv<'tcx>, trait_id: DefId, rcvr_args: GenericArgsRef<'tcx>,
) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
    let trait_ref = ty::TraitRef::from_assoc(tcx, trait_id, rcvr_args);
    let vtbl = tcx.codegen_select_candidate(typing_env.as_query_input(trait_ref))?;

    match vtbl {
        traits::ImplSource::UserDefined(impl_data) => {
            let trait_def = tcx.trait_def(trait_def_id);
            // 通过特化图找到最具体的实现（叶节点）
            let leaf_def = trait_def.ancestors(tcx, impl_data.impl_def_id)?
                .leaf_def(tcx, trait_item_id).unwrap();

            // 非特化项总是可用；特化默认项需等到 PostAnalysis
            let eligible = leaf_def.is_final() || (
                matches!(typing_env.typing_mode(), ty::TypingMode::PostAnalysis)
                && !trait_ref.still_further_specializable()
            );
            if !eligible { return Ok(None); }

            // translate_args：将泛型参数从 trait 空间转换到 impl 空间
            let args = rcvr_args.rebase_onto(tcx, trait_def_id, impl_data.args);
            let args = translate_args(&infcx, param_env, impl_data.impl_def_id, args, leaf_def.defining_node);
            Some(ty::Instance::new_raw(leaf_def.item.def_id, args))
        }
        // ...
    }
}

translate_args 处理 trait 与 impl 之间不同的泛型参数结构。例如 trait Foo<A> + impl<T: Clone> Foo<T> for Vec<T>，解析 <Vec<String> as Foo<String>>::bar 时需将 trait 参数 (Self=Vec<String>, A=String) 映射到 impl 参数 T=String。

sequenceDiagram
    participant Mono as 单态化
    participant TSelect as Trait 选择
    participant Lookup as Impl 查找
    participant Codegen as 代码生成

    Mono->>TSelect: 解析 <String as Greet>::hello
    TSelect->>Lookup: 查找 String: Greet
    Lookup->>Lookup: SimplifiedType::Adt(String)
    Lookup-->>TSelect: ImplCandidate(impl_def_id)
    TSelect->>TSelect: confirm → ImplSource::UserDefined
    TSelect-->>Mono: {impl_def_id, args}
    Mono->>Codegen: resolve_associated_item
    Codegen->>Codegen: translate_args + Instance::new_raw
    Note over Codegen: 生成 call <String as Greet>::hello（直接调用）

7.5 一致性规则与孤儿规则

一致性保证关键不变量：对任意 (Type, Trait) 对，全局最多一个 impl。

7.5.1 孤儿规则

要写 impl Trait for Type，要么 Trait 定义在当前 crate，要么 Type 定义在当前 crate。#[fundamental] 类型（&T、Box<T>）可以”看穿”——你可以为 &MyType 实现外部 trait。

impl Display for MyType { ... }           // 合法：MyType 是本地类型
impl Display for MyWrapper<Vec<i32>> { }  // 合法：MyWrapper 是本地类型
// impl Display for Vec<i32> { ... }      // 非法！两者都不是本地类型

7.5.2 重叠检查

编译器必须证明不存在两个 impl 同时适用于同一类型：

// compiler/rustc_trait_selection/src/traits/coherence.rs
pub fn overlapping_trait_impls(tcx: TyCtxt<'_>, impl1_def_id: DefId, impl2_def_id: DefId,
    skip_leak_check: SkipLeakCheck, overlap_mode: OverlapMode,
) -> Option<OverlapResult<'_>> {
    // 快速排除：DeepRejectCtxt 比较类型结构，不创建推断上下文
    let impl1_args = tcx.impl_trait_ref(impl1_def_id).skip_binder().args;
    let impl2_args = tcx.impl_trait_ref(impl2_def_id).skip_binder().args;
    if !DeepRejectCtxt::relate_infer_infer(tcx).args_may_unify(impl1_args, impl2_args) {
        return None; // 类型结构不同，不可能重叠
    }
    // 完整检查：创建推断上下文，尝试统一两个 impl 的参数
    overlapping_impls(tcx, impl1_def_id, impl2_def_id, skip_leak_check, overlap_mode, true)
}

DeepRejectCtxt 是高效的预筛选器——impl Trait for Vec<i32> vs impl Trait for HashMap<K,V> 外层类型不同，直接排除；vs impl<T> Trait for Vec<T> 外层相同，需要完整检查。

ImplHeader 包含 impl 头部的全部信息（Self 类型、trait ref、谓词），一致性检查还要保守地考虑下游 crate 未来可能添加的 impl。

7.5.3 源码核对：overlapping_impls 的”双跑诊断”模式

§7.5 提到 coherence 阶段做 overlap 检查。打开 compiler/rustc_trait_selection/src/traits/coherence.rs:155-198 能看到一个为诊断质量妥协的双跑设计：

fn overlapping_impls(...) -> Option<OverlapResult<'_>> {
    if tcx.next_trait_solver_in_coherence() {
        overlap(tcx, TrackAmbiguityCauses::Yes, ...)
    } else {
        // 老 trait solver 路径
        let _overlap_with_bad_diagnostics = overlap(
            tcx, TrackAmbiguityCauses::No, ...,
        )?;

        // In the case where we detect an error, run the check again, but
        // this time tracking intercrate ambiguity causes for better
        // diagnostics. (These take time and can lead to false errors.)
        let overlap = overlap(
            tcx, TrackAmbiguityCauses::Yes, ...,
        ).unwrap();
        Some(overlap)
    }
}

老 trait solver 跑两次 overlap 检查：

第一次 TrackAmbiguityCauses::No——快速判定”是否重叠”——不收集诊断信息
如果第一次发现重叠（? 之后还有值）——再跑一次 TrackAmbiguityCauses::Yes——这次慢但收集所有 ambiguity cause 用于错误消息

注释里点明动机（第 184-186 行）：“These take time and can lead to false errors”——详细诊断收集慢、还可能产生误报。所以快速路径先确认”确实有 overlap”——再花时间生成详细诊断。

这条 pattern 在错误诊断的工程实践里普遍——快路径检测、慢路径解释。Rust 编译器其他地方也有：name resolution 的 “did you mean …?” 建议、type inference 的 expected/found 详细类型显示——都是这种”先确认错误、再花时间生成 user-friendly 信息”的二阶段。

next_trait_solver_in_coherence() 这个 feature flag 暗示了——新 trait solver（chalk-based）已经把诊断和判定合一了，不需要这种双跑——这是 rustc 团队多年优化的进展之一。

7.5.4 源码核对：fresh_impl_header 的 inference variable 注入

fresh_impl_header（coherence.rs:201-221）展示了 overlap 检查的核心技术——用 inference variables 替代 impl 的所有 type parameters：

fn fresh_impl_header<'tcx>(
    infcx: &InferCtxt<'tcx>,
    impl_def_id: DefId,
    is_of_trait: bool,
) -> ImplHeader<'tcx> {
    let tcx = infcx.tcx;
    let impl_args = infcx.fresh_args_for_item(DUMMY_SP, impl_def_id);

    ImplHeader {
        impl_def_id,
        impl_args,
        self_ty: tcx.type_of(impl_def_id).instantiate(tcx, impl_args),
        trait_ref: is_of_trait.then(|| tcx.impl_trait_ref(impl_def_id).instantiate(tcx, impl_args)),
        predicates: tcx.predicates_of(impl_def_id).instantiate(tcx, impl_args)
            .iter().map(|(c, _)| c.as_predicate()).collect(),
    }
}

fresh_args_for_item 给每个 generic parameter 生成一个 fresh inference variable——impl<T: Foo> Bar for Vec<T> 在 overlap 检查时变成 impl<?T0> Bar for Vec<?T0> where ?T0: Foo。

为什么用 inference variable？因为 overlap 检查的本质是：“两个 impl 是否存在某个 substitution 让它们同时适用”。把两个 impl 的 generic params 都替换成 fresh inference variables、然后尝试 unify 两者的 self_ty——如果 unify 成功、就有重叠；失败、不重叠。

举例：

impl 1: impl<T> Foo for Vec<T> → 替换成 Foo for Vec<?T0>
impl 2: impl Foo for Vec<i32> → Foo for Vec<i32>

unify Vec<?T0> 和 Vec<i32>——成功（?T0 = i32）——所以两个 impl 重叠（具体类型 Vec<i32> 同时被两个 impl 覆盖）。

这种”用 inference variable 替代 generic、然后尝试 unify”是类型论里 “unification problem” 的标准做法——也用在 Hindley-Milner 类型推断、Prolog 求解、SQL 查询优化等场景。Rust 把它落到 trait coherence 检查里——保证全局任何具体类型最多被一个 trait impl 覆盖——这是 Rust 类型系统 soundness 的基础之一。

7.6 特化：更具体的 impl 覆盖更一般的

特化（#![feature(specialization)]/#![feature(min_specialization)]）允许重叠 impl，选择更具体的：

#![feature(specialization)]
trait Serialize { fn serialize(&self) -> Vec<u8>; }

impl<T: Debug> Serialize for T {
    default fn serialize(&self) -> Vec<u8> { format!("{:?}", self).into_bytes() }
}
impl Serialize for String {
    fn serialize(&self) -> Vec<u8> { self.as_bytes().to_vec() }  // 更高效
}

7.6.1 特化图与 specializes 检查

编译器通过特化图管理 impl 优先级——树状结构，根节点是 trait 定义，子节点是更具体的 impl：

// compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
enum Inserted<'tcx> {
    BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>),
    ReplaceChildren(Vec<DefId>),    // 新 impl 特化了现有子节点
    ShouldRecurseOn(DefId),         // 新 impl 是某子节点的进一步特化
}

specializes 函数通过蕴含检查验证特化关系：在 specializing impl 的 where 子句环境下，证明 parent impl 也成立。直觉上，A 特化 B 意味着 A 适用的所有类型 B 也适用，但 B 适用的某些类型 A 不适用。

// compiler/rustc_middle/src/ty/trait_def.rs
pub enum TraitSpecializationKind {
    None,            // 默认：不允许特化
    Marker,          // 无方法的 marker trait，安全特化
    AlwaysApplicable, // 生命周期无关的"总是适用" trait
}

min_specialization 比 specialization 更保守——只允许对特定标记 trait 特化，避免健全性问题。标准库内部大量使用它优化性能关键路径。

7.6.2 源码核对：specializes 函数的 5 步证明算法

§7.6 给了特化的高层概念。compiler/rustc_trait_selection/src/traits/specialize/mod.rs:237+ 的 specializes 函数实现了RFC 1210 的精确算法：

pub(super) fn specializes(
    tcx: TyCtxt<'_>,
    (specializing_impl_def_id, parent_impl_def_id): (DefId, DefId),
) -> bool {
    // Step 0: feature gate 检查
    if !tcx.specialization_enabled_in(specializing_impl_def_id.krate) {
        let span = tcx.def_span(specializing_impl_def_id);
        if !span.allows_unstable(sym::specialization)
            && !span.allows_unstable(sym::min_specialization)
        {
            return false;
        }
    }

    // Step 1: polarity 检查（negative 不能 specialize positive）
    if specializing_impl_trait_header.polarity != tcx.impl_polarity(parent_impl_def_id) {
        return false;
    }

    // Step 2: 用 specializing impl 的 ParamEnv（最严约束环境）
    let param_env = tcx.param_env(specializing_impl_def_id);
    let infcx = tcx.infer_ctxt().build(TypingMode::non_body_analysis());

    // Step 3: 把 parent impl 的 generic 替换成 fresh inference vars
    let parent_args = infcx.fresh_args_for_item(DUMMY_SP, parent_impl_def_id);
    let parent_impl_trait_ref = ocx.normalize(...);

    // Step 4: 尝试 unify 两个 trait_ref
    let Ok(()) = ocx.eq(cause, param_env, specializing_impl_trait_ref, parent_impl_trait_ref) else {
        return false;
    };

    // Step 5: 检查 specializing impl 的环境能不能证明 parent impl 的 where clauses
    let predicates = infcx.tcx.predicates_of(parent_impl_def_id).instantiate(infcx.tcx, parent_args);
    let obligations = predicates_for_generics(...);
    ocx.register_obligations(obligations);

    let errors = ocx.evaluate_obligations_error_on_ambiguity();
    errors.is_empty()
}

5 步证明的逻辑链：

Step 0：feature gate——specialization 还是 unstable feature、要 #![feature(specialization)] 或 min_specialization。源码先检查这个 gate 是否启用——未启用直接 return false。

Step 1：polarity——negative impl（impl !Send for T）和 positive impl 不能互相 specialize。这是 §7.5.4 讲过的 polarity 概念在 specialization 检查里的应用。

Step 2：用 specializing impl 的 ParamEnv——这是关键设计：用更严格那一方的环境检查另一方是否能成立。如果 impl<T: Send> Foo for Vec<T> 是 specializing、impl<T> Foo for Vec<T> 是 parent——用 T: Send 的环境去证明 T 无约束的 parent 能成立——显然能。反过来不行（无约束环境无法证明 T: Send）。

Step 3：parent impl 用 fresh inference vars——和 §7.5.4 fresh_impl_header 同样的 unification trick——让 unify 算法找到具体 substitution。

Step 4：unify trait_refs——两个 impl 的 self_ty + trait args 必须能 unify。如果不能 unify、根本不是同一个 trait 的同一个 type 的两个 impl、谈不上 specialization。

Step 5：证明 parent 的 where clauses——这是 RFC 1210 的核心条件。如果 specializing 的环境能蕴含 parent 的所有 where clauses——specializing 是 parent 的”更严格版本”——成立 specialization 关系。

注释里直接引用了 “RFC 1210 for more details and justification”——这是 5 年多前的 RFC、specialization 至今仍是 unstable feature。stable 化卡在哪里？ 主要是 lifetime 参数下 specialization 的 soundness 问题——一个有名的反例叫 “issue #28999”——会导致类型系统不 sound。team 至今没找到通用解、所以 specialization 卡在 nightly。

读这段代码能让你理解为什么 Rust 的 stabilization 这么慢——每个 feature 都要在所有 corner case 下证明 sound——不像其他语言”看着工作就发布”。这种保守是 Rust 类型系统在 production 里几乎不出现 soundness bug 的原因。

7.7 关联类型解析

编译器需要将 <T as Iterator>::Item 解析为具体类型，称为投影规范化，代码在 project.rs：

// compiler/rustc_trait_selection/src/traits/project.rs
enum ProjectionCandidate<'tcx> {
    ParamEnv(ty::PolyProjectionPredicate<'tcx>), // where 子句
    TraitDef(ty::PolyProjectionPredicate<'tcx>), // trait 定义中的 bound
    Object(ty::PolyProjectionPredicate<'tcx>),   // dyn Trait bound
    Select(Selection<'tcx>),                      // 来自 impl
}

ParamEnv 候选始终优先于 impl 候选。这保证了泛型上下文正确性：

trait Foo { type Output; }
impl<T> Foo for T { type Output = T; }
fn bar<T: Foo<Output = String>>(x: T) {
    // <T as Foo>::Output 应该是 String（where 子句），不是 T（blanket impl）
}

规范化流程：先通过 trait 选择找到 impl → 从 impl 获取关联类型定义 → 与期望类型统一。

// project.rs（简化核心流程）
fn project_and_unify_term<'cx, 'tcx>(selcx: &mut SelectionContext<'cx, 'tcx>,
    obligation: &ProjectionObligation<'tcx>) -> ProjectAndUnifyResult<'tcx> {
    // 第1步：通过 trait 选择找到 impl，获取关联类型的具体定义
    let normalized = opt_normalize_projection_term(selcx, obligation.param_env,
        obligation.predicate.projection_term, ...)?;
    // 第2步：将规范化结果与期望类型统一
    match infcx.at(&obligation.cause, obligation.param_env)
        .eq(DefineOpaqueTypes::Yes, normalized, obligation.predicate.term) {
        Ok(InferOk { obligations, .. }) => ProjectAndUnifyResult::Holds(obligations),
        Err(err) => ProjectAndUnifyResult::MismatchedProjectionTypes(err),
    }
}

7.7.1 源码核对：project 函数的 4 路 candidate 收集

§7.7 讲了关联类型解析。打开 compiler/rustc_trait_selection/src/traits/project.rs:650-707 能看到 project 函数的完整结构——4 路 candidate 收集 + 优先级控制：

fn project<'cx, 'tcx>(
    selcx: &mut SelectionContext<'cx, 'tcx>,
    obligation: &ProjectionTermObligation<'tcx>,
) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
    // 递归限制检查
    if !selcx.tcx().recursion_limit().value_within_limit(obligation.recursion_depth) {
        return Err(ProjectionError::TraitSelectionError(SelectionError::Overflow(
            OverflowError::Canonical,
        )));
    }

    // 早返回：含 type/const error 的 obligation 直接返回 error term
    if let Err(guar) = obligation.predicate.non_region_error_reported() {
        return Ok(Projected::Progress(Progress::error_for_term(...)));
    }

    let mut candidates = ProjectionCandidateSet::None;

    // 路径 1：从 ParamEnv 收集（where 子句、最高优先）
    assemble_candidates_from_param_env(selcx, obligation, &mut candidates);

    // 路径 2：从 trait def 收集（trait 定义里的关联类型 bound）
    assemble_candidates_from_trait_def(selcx, obligation, &mut candidates);

    // 路径 3：从 dyn Trait object 收集
    assemble_candidates_from_object_ty(selcx, obligation, &mut candidates);

    // 路径 4：从 impl 收集（仅当不是 Object candidate）
    if let ProjectionCandidateSet::Single(ProjectionCandidate::Object(_)) = candidates {
        // Avoid normalization cycle from selection
    } else {
        assemble_candidates_from_impls(selcx, obligation, &mut candidates);
    };

    match candidates {
        ProjectionCandidateSet::Single(candidate) => confirm_candidate(...),
        ProjectionCandidateSet::None => Ok(Projected::NoProgress(term)),  // 不能进展、保留 unprojected
        ProjectionCandidateSet::Error(e) => Err(ProjectionError::TraitSelectionError(e)),
        ProjectionCandidateSet::Ambiguous => Err(ProjectionError::TooManyCandidates),
    }
}

四条值得读懂的细节：

1、4 路 candidate 的优先级——ParamEnv > trait_def > object > impl。注释里特别标明（第 674-676 行）：“Make sure that the following procedures are kept in order. ParamEnv needs to be first because it has highest priority”。where-bound 永远优先于 impl——和 §7.2.3-bis 讲的 trait selection winnow 优先级是同一原则（让泛型上下文可预测）。

2、object 与 impl 的互斥：当唯一 candidate 是 Object 时不再收集 impl——避免 “object_ty 的 impl 又触发对同一 dyn Trait 的 normalization、形成 cycle” 的死循环。FIXME(lazy_normalization) 注释暗示——未来 lazy normalization 实施后这条特殊处理可以删掉。这种”为现有架构限制做的临时妥协”在编译器代码里很常见——FIXME 注释是它的”还债清单”。

3、Projected::NoProgress(term) vs Error：找不到 candidate 时不报错、而是返回”未投影”的 term。比如 <T as Iterator>::Item（T 是泛型）——本就不该立刻投影出具体类型——把 unresolved alias type 透传给上层、等更多约束注入再回头试。这是 “延迟决策” 在类型推断里的应用——不是所有 query 都必须立刻有答案、有时候”还不知道”是合法答案。

4、ProjectionCandidateSet::Ambiguous → TooManyCandidates 错：和 NoProgress 不同——Ambiguous 表示有多个等价 candidate——这是真正的歧义、必须报错让用户加更多类型注解或 where bound。

这条 4 路收集 + 优先级 ladder 的设计和 §7.2 讲的 trait selection 是同一个心智模型——type system 多个组件用相同的”多 candidate + 优先级 + 单选”模式。理解一处就能推广到其他 query 的实现。

7.8 Where 子句与 Trait Bound 验证

调用带 trait bound 的函数时，编译器生成义务并通过 FulfillmentContext 验证：

fn process<T: Clone + Debug + Send>(item: T) { ... }
// process(Rc::new(42)) 生成三个义务：
// Rc<i32>: Clone → 成功 | Rc<i32>: Debug → 成功 | Rc<i32>: Send → 失败！

// compiler/rustc_trait_selection/src/traits/fulfill.rs
pub struct FulfillmentContext<'tcx, E: 'tcx> {
    predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
    usable_in_snapshot: usize,
    _errors: PhantomData<E>,
}

ObligationForest 以森林形式组织义务，支持增量处理——遇歧义时挂起，获得更多类型信息后重试。

编译器的谓词体系区分 Predicate（广义）和 Clause（where 子句子集）：

pub enum ClauseKind<'tcx> {
    Trait(TraitPredicate<'tcx>),              // T: Trait
    Projection(ProjectionPredicate<'tcx>),     // <T as Trait>::Assoc = U
    TypeOutlives(TypeOutlivesPredicate<'tcx>), // T: 'a
    RegionOutlives(RegionOutlivesPredicate<'tcx>), // 'a: 'b
    // ...
}

7.9 Blanket 实现的编译器处理

impl<T: Display> ToString for T 这类 blanket impl 在 TraitImpls 中存储于 blanket_impls 向量——无法被 SimplifiedType 索引，任何查找都必须考虑。

查找 String: ToString 时：找到 blanket impl → 代入 T=String → 产生嵌套义务 String: Display → 解析成功。

Blanket impl 与单态化协同效果显著：

// 源码中的 blanket impl
impl<T: Display> ToString for T {
    fn to_string(&self) -> String {
        let mut buf = String::new();
        fmt::Write::write_fmt(&mut buf, format_args!("{}", self)).unwrap();
        buf
    }
}

// 单态化为 T=i32 后，编译器生成：
// fn <i32 as ToString>::to_string(self: &i32) -> String {
//     // Display::fmt 被静态解析为 <i32 as Display>::fmt —— 直接调用！
//     ...
// }

每个副本中的 Display::fmt 调用都被静态分发到对应类型的具体实现。这就是 blanket impl + 单态化 + 静态分发三者协作的结果。

7.10 性能分析：零成本的汇编级证明

考虑以下代码：

trait Doubler { fn double(&self) -> i64; }
impl Doubler for i64 {
    #[inline(never)]
    fn double(&self) -> i64 { self * 2 }
}
fn static_dispatch<T: Doubler>(x: &T) -> i64 { x.double() }
fn dynamic_dispatch(x: &dyn Doubler) -> i64 { x.double() }

static_dispatch::<i64> 的汇编（x86-64, -O2）：

static_dispatch:
    mov     rax, qword ptr [rdi]    ; 读取 *x
    shl     rax, 1                  ; 乘2优化为左移（内联后）
    ret

dynamic_dispatch 的汇编：

dynamic_dispatch:
    mov     rax, qword ptr [rsi + 24]  ; vtable 加载函数指针
    mov     rdi, qword ptr [rdi]       ; 加载数据指针
    call    rax                         ; 间接调用！
    ret

特征	静态分发	动态分发
调用指令	`call concrete_fn`（直接）	`call rax`（间接）
可否内联	可以	不可能
分支预测	100% 命中	可能 miss
额外内存访问	0 次	2 次

静态分发的真正威力在于内联后的优化级联：x.double() 内联为 x * 2 → 迭代器融合为单循环 → SIMD 向量化 → 循环展开。动态分发因无法内联，这些优化全部失效。

代价在编译期：N 个类型实例化同一泛型函数 → O(N) 倍编译时间和二进制大小。

7.11 TraitDef：Trait 的编译器表示

// compiler/rustc_middle/src/ty/trait_def.rs
pub struct TraitDef {
    pub def_id: DefId,
    pub safety: hir::Safety,                  // safe / unsafe trait
    pub constness: hir::Constness,            // const trait
    pub has_auto_impl: bool,                  // Send/Sync 等 auto trait
    pub is_marker: bool,                      // marker trait: impl 允许重叠
    pub is_coinductive: bool,                 // 允许求解器循环
    pub is_fundamental: bool,                 // 影响孤儿规则
    pub specialization_kind: TraitSpecializationKind,
    pub deny_explicit_impl: bool,             // 完全内建 trait
    pub must_implement_one_of: Option<Box<[Ident]>>,
    // ...
}

关键字段的影响：is_coinductive 允许 auto trait 的递归证明（struct Node { children: Vec<Node> } 中的 Node: Send 循环）；is_marker 允许 marker trait 的 impl 重叠（无方法体，无歧义）；is_fundamental 修改孤儿规则使 &MyType 可实现外部 trait。

7.11.1 `TraitDef` 的真实 13 字段与 edition-gated 方法派发

上面表格给的是”摘要版”——真实 TraitDef（rustc_middle/src/ty/trait_def.rs:20）有 13 个字段，其中几个反映了 Rust 标准库和语言演化过程里不得不插入的边缘补丁：

pub struct TraitDef {
    pub def_id: DefId,
    pub safety: hir::Safety,
    pub constness: hir::Constness,
    pub impl_restriction: ImplRestrictionKind,              // 7.5 节讲的孤儿规则的 mod 级扩展
    pub paren_sugar: bool,                                   // #[rustc_paren_sugar]
    pub has_auto_impl: bool,
    pub is_marker: bool,
    pub is_coinductive: bool,
    pub is_fundamental: bool,
    pub skip_array_during_method_dispatch: bool,            // ← edition 补丁 A
    pub skip_boxed_slice_during_method_dispatch: bool,      // ← edition 补丁 B
    pub specialization_kind: TraitSpecializationKind,
    pub must_implement_one_of: Option<Box<[Ident]>>,
    pub force_dyn_incompatible: Option<Span>,               // 手动标记 dyn 不兼容
    pub deny_explicit_impl: bool,
}

原文 10 字段版本漏掉的 3 个字段里有 2 个是edition 补丁，值得专门讲清楚——它们是 Rust 少有的”因为标准库要改但 edition 不允许破坏兼容而插入的编译器级开关”。

skip_array_during_method_dispatch: bool（line 58-61）：

/// If `true`, then this trait has the `#[rustc_skip_during_method_dispatch(array)]`
/// attribute, indicating that editions before 2021 should not consider this trait
/// during method dispatch if the receiver is an array.

这是 IntoIterator 专用的补丁。Rust 2021 之前 array.into_iter() 由于历史原因返回迭代器 &T 而不是 T（因为 &[T; N]: IntoIterator<Item=&T> 比 [T; N]: IntoIterator<Item=T> 早存在、避免改变 method resolution 会破坏老代码）。2021 edition 修复了这个——但老代码库在 2021 之前的 edition 下编译时、必须仍然看到老行为。skip_array_during_method_dispatch=true 在 IntoIterator 上被 #[rustc_skip_during_method_dispatch(array)] 设置、让 2021 之前的 edition 在 array 接收者上跳过这个 trait——method resolver 会去找 &[T; N]::into_iter() 而不是 [T; N]::into_iter()。

skip_boxed_slice_during_method_dispatch: bool（line 63-66）是 2024 edition 的对称补丁——同样是 IntoIterator，Box<[T]> 在 2024 之前调 .into_iter() 走 slice 迭代器返回 &T、之后才走 Box<[T]>::IntoIterator 返回 T。两个字段合起来表达 “同一 trait 在不同 edition 下方法派发行为不一致”——这是 Rust edition 系统在编译器内部的真实落地方式：不是一个全局开关、而是一个一个 trait 里单独打补丁。

TraitSpecializationKind 的三种值（trait_def.rs:89-102）：

pub enum TraitSpecializationKind {
    None,              // 默认：不允许 specialize
    Marker,            // 无方法、对 Marker trait 允许（Sized/FusedIterator）
    AlwaysApplicable,  // #[rustc_specialization_trait] 标记的 impl "always applicable"
}

specialization_kind = None 是绝大多数 trait 的默认——用户代码里基本看不到 specialization（nightly 特性、没稳定）。但标准库内部大量依赖 specialization——Extend、Iterator::collect、ToString 等都有”针对 Vec<T>/String/&str 的特化高效 impl”。AlwaysApplicable 是这些标准库内部用的”安全版 specialization”——要求所有 impl 对任意生命周期都适用（避免了普通 specialization 的 lifetime-unsound 问题）。

这个 enum 的存在是 Rust 语言稳定性和标准库性能之间张力的一个证据：标准库需要 specialization 才能做到”用户调 vec.iter().collect::<Vec<_>>() 性能等同 vec.clone()”这种优化、但 specialization 稳定化经过多年讨论仍然不敢放出来给用户——rustc_specialization_trait 的硬限制是折中——让标准库内部用、用户感知为”Vec::collect 就是快”、但不暴露不安全的一般 specialization 语法。

这 13 字段的 struct 是Rust 语言设计的历史见证物——每个字段都对应一个真实的语言演化决定或标准库工程需要。阅读它远比单独读”trait 是什么”的教程更能理解 Rust 是怎么在保持稳定性的前提下持续演化的。

7.12 完整流程总结

graph TB
    subgraph "1. 类型检查"
        A1["推断 T = Article"] --> A2["生成义务 Article: Summary"]
        A2 --> A3["FulfillmentContext 验证"]
    end
    subgraph "2. Trait 选择"
        B1["assemble_candidates"] --> B2["找到 ImplCandidate"]
        B2 --> B3["confirm → ImplSource::UserDefined"]
    end
    subgraph "3. 单态化 + 代码生成"
        C1["生成 notify::Article"] --> C2["resolve_associated_item"]
        C2 --> C3["translate_args → Instance"]
        C3 --> C4["emit call Article::summarize"]
    end
    A3 --> B1
    B3 --> C1
    style A3 fill:#3b82f6,color:#fff,stroke:none
    style B3 fill:#8b5cf6,color:#fff,stroke:none
    style C4 fill:#059669,color:#fff,stroke:none

7.13 边界情况

推断变量与歧义：let x = Default::default() 中 Self 是推断变量，编译器返回歧义，挂起义务等待类型信息。添加 let _: i32 = x 后推断解析，义务满足。ObligationForest 支持这种增量处理——义务在多个推断步骤间反复被尝试求解。

递归与 coinduction：考虑 struct Node { value: i32, children: Vec<Node> } 检查 Node: Send：需要 i32: Send（是）且 Vec<Node>: Send，而后者需要 Node: Send——形成循环。对于 coinductive auto trait，编译器允许此循环并视为成功。TraitObligationStack 的 reached_depth 追踪循环深度，参与循环的节点放弃缓存以避免错误结果。

负面推理：编译器可推断 Rc<i32>: !Send（因为 Rc 内部使用非原子引用计数）。在一致性检查中，coherence.rs 的 impl_intersection_has_negative_obligation 函数利用负面 trait bound 证明两个 impl 互斥：

// 理论上（需要 negative_impls 特性）：
impl<T: Send> Process for T { ... }
impl<T: !Send> Process for T { ... }
// 不重叠：T: Send 和 T: !Send 互斥

7.12.1 trait selection 在其他语言里的对应

理解 rustc 的 trait selection 后看其他语言的”类似机制”会有醍醐灌顶感——所有静态类型语言都需要解决类似问题、但解法各不相同：

Haskell type classes：trait 概念的鼻祖。Haskell 的 type class 选择走 “dictionary passing”——编译期为每个 class instance 生成一个 dictionary（虚函数表）、call site 推断需要哪个 dictionary 并传给 callee。Haskell 类似 Rust 的 dyn dispatch——但因为 Haskell 不区分 static/dynamic dispatch、Rust 显式有两种模式。

C++ concepts (C++20)：和 Rust trait bound 最接近。requires 子句声明类型需要满足的约束。但 C++ concept 不像 Rust 一样做 coherence check——两个互相重叠的 concept impl 不会编译错、是 SFINAE 风格的”哪个最 specific 选哪个”。Rust 的 coherence 严格性是它优于 C++ 的地方之一。

Swift protocols：和 Rust trait 几乎 1:1。但 Swift 默认走 dynamic dispatch（除非用 final 标注或 generic）——Rust 是反过来（默认 static、用 dyn 才动态）。哪种默认更好是有争议的——Swift 选 dynamic 是为了 ABI stability、Rust 选 static 是为了零成本。

Java/Kotlin interface：纯 dynamic dispatch、没有 static dispatch 选项。性能上一定有 vtable 开销。但 JIT 能做 “speculative inlining”——HotSpot 跑一会儿后能动态消除大部分 vtable 调用。Rust 把”消除间接”的工作放在编译期、Java 放在 runtime——两条路殊途同归。

Go interface：“structural typing”——任何类型只要实现了 interface 要求的方法、自动满足 interface。不需要显式声明 impl Trait for Type——这是和 Rust 最大的区别。Go 的灵活换来了”我的类型实现了哪些 interface？“难以静态查询——Rust 的显式 impl 让 IDE 能精确告诉你。

TypeScript structural types：和 Go 类似的 structural typing、但只在编译期有意义（运行时是 JS、没有类型）。所以 TypeScript 没有 trait selection 这个概念——所有 dispatch 都是 JS 的 method lookup。

通过这些对比能看出 trait selection 是 Rust 独特之处——其他语言要么没这个概念（Java/Go）、要么有但更宽松（C++ concept）、要么走不同 dispatch 模型（Haskell/Swift）。Rust 的 “显式 impl + 严格 coherence + 静态 dispatch 默认” 三结合是 Rust 性能 + 安全的核心来源——也是它编译慢的原因。

理解多语言对照后再看 Rust trait——你会觉得它的设计不是”想这么做”、而是”必须这么做”——为了零成本 + 严格 sound + 显式 trait 关系——只能是这套架构。

7.12.2 几条 rustc trait 系统里”反直觉”的事实

读完本章你应该获得几条”反直觉但真实”的关于 Rust trait 系统的事实——这些在普通 Rust 教程里不会讲、但真正影响你的代码设计：

1、Vec<T>: Clone 不一定是真理——只有 T: Clone 才是。这意味着 trait selection 要先 dispatch 到 Vec 的 blanket impl impl<T: Clone> Clone for Vec<T>、再递归求解 T: Clone——可能产出 T: Clone 这条 sub-obligation 让上层处理。trait selection 不是”yes/no”返回——是”yes/no/conditional with sub-obligations”。

2、'static: 'static 是 trivial 的、但 T: 'static 涉及 lifetime check——不在 trait selection 范围内。本章 §7.2.5 提过这点——lifetime 维度由 region check 单独处理。这也是为什么 where T: 'static bound 不会变慢 trait selection——它走另一条路径。

3、impl<T> Trait for T where T: Trait 可以编译过——但运行时无穷递归。trait selection 算法不验证 impl body 的 termination——它只看 impl header 是否一致。所以这种”自身递归”的 impl 编译期不报错、运行时栈溢出。Rust 的 termination check 只在 const evaluation 里有、运行时代码不查。

4、Box<dyn Trait> 不是 dyn Trait 的 impl——是 deref coercion。本章 §7.4 讲的 ImplCandidate 收集永远不会找到 Box<dyn Trait>: Trait 这种 impl——它的工作原理是 Box<T> 通过 Deref<Target = T> 让 *box 表现得像 T——method call 通过 deref 链找到 dyn Trait 的 vtable。这条机制让 trait method 在 Box<dyn Trait> 上的”正常调用”实际上经过了 deref coercion + vtable lookup 两步。

5、auto trait（Send/Sync）不需要 impl 块——它们靠结构化推断自动 derive。一个 struct 是 Send 的当且仅当它的所有字段都是 Send。本章 §7.2.1 列的 AutoImplCandidate 就是这个机制——一个独立的 candidate 类型、不需要用户写 impl。

这 5 条事实里至少 3 条会在你写复杂 Rust 代码时遇到——理解它们的源码层原理让你遇到时知道为什么这样、能调整代码绕开。

7.12.3 trait selection 的演进——从 old solver 到 next solver

读本章时你可能注意到 §7.5.3 的 tcx.next_trait_solver_in_coherence() 这种 feature flag——这指向 rustc 内部正在进行的一项重大重构：

Old solver（当前 stable 用的）：

基于 RFC 1.0 的设计、十多年前实现
命令式风格、每个 query 都有专门函数
缓存策略复杂（local/global/stack-dependent 多套）
对某些 corner case（高阶生命周期、coinductive trait）有 known unsoundness

Next solver（chalk-based、正在开发）：

基于 logic programming（Prolog 风格）
声明式表达 trait rules
统一的 cache + canonicalization
修正 old solver 的多个 unsoundness

切换是渐进式的——先在 coherence 里试用（next_trait_solver_in_coherence()），再扩展到 normalization、再扩展到普通 obligation——计划要 2-3 年才完全替换 old solver。

为什么 rustc 团队愿意花 2-3 年做这个？因为 trait system 的 unsoundness 是不能容忍的——一个 unsoundness 就能让 safe Rust 代码 segfault、违反 Rust 的核心承诺。new solver 用更严格的形式化基础（Chalk’s predicate calculus）让证明更可靠。

读这本书时如果你看到 enable_old_solver / next_trait_solver / chalk_solve 等命名——它们都指向这个迁移。未来 5 年 rustc 的 trait system 会经历这场缓慢但深刻的重构——本章讲的算法细节也会演化。但核心心智模型（候选组装、求值、确认；优先级 ladder；fast reject；inference variable）会保留——因为它们对应的是类型论本质问题、不是某个 solver 实现的细节。

7.12.4 编译期 vs 运行期：trait 选择的耗时分布

读完本章后给读者一组具体数字、感受 trait selection 在 Rust 编译时间里的占比：

典型大型 Rust 项目（如 rustc 自身、cargo、tokio）：

编译阶段	占总编译时间%
Lexing + Parsing	1-3%
HIR lowering	2-5%
Type inference + trait selection	30-60%
MIR construction + optimization	10-15%
Borrow checking	5-10%
Codegen (LLVM)	20-40%
Linking	5-15%

trait selection 是 Rust 编译时间的最大单一消耗——往往超过 LLVM codegen。这就是为什么 Rust 编译慢——不是 LLVM 慢、是类型系统复杂。

C++ 的对比：C++ 模板实例化也慢——这是 “C++ 编译慢” 的主因——但 C++ 没有 Rust 的 trait coherence + specialization + auto trait + projection 等多套机制。Rust 的 trait 系统比 C++ 模板更强大、所以也更慢。

cargo check 之所以快得多（比 cargo build 快 5-10x）——主要是省略了 codegen + linking——但 trait selection 这部分仍然要做（因为它是 type checking 的一部分）。所以 cargo check 的下限就在那里——没法再快很多。

这条数据让你能合理预估”我加了一个 generic API、编译时间会涨多少”——新增 generic 函数对编译时间是 1.05-1.20x、新增 trait + 多个 impl 是 1.10-1.50x。这是 Rust 在 ergonomic 和 compile-time 之间的根本权衡——优雅的 API 有编译时间代价。

7.12.5 给应用 Rust 开发者的 trait 设计启示

读完本章对编译器内部的理解后，能给你写应用代码时的 trait 设计提供 6 条直接启示：

1、能用 generic 就别用 trait object——本章 §7.4 讲过 generic 走 static dispatch、零成本；trait object 走 vtable、有间接调用开销 + cache miss。在性能敏感路径上 generic 是默认答案。只有需要异构集合（Vec<Box<dyn Trait>>）或类型擦除（动态插件）才用 trait object。

2、避免 deeply nested generics——fn foo<T: Iterator<Item = U>, U: Display> 比 fn foo<I: Iterator<Item: Display>> 慢编译。本章 §7.2.6 讲过 evaluation_cache 的 inference variable 影响——nested generics 让 inference variable 多、cache 命中率低、编译时间炸。

3、where bound 顺序无所谓但写法影响诊断——本章 §7.2.3-bis 讲 winnow 的 5 层 ladder 对 where bound 是按”非 global 优先”——你写的顺序不影响优先级但影响错误消息的友好度。把最具体的 bound 写在前面让 rustc 报错时优先指向它。

4、impl<T> Trait for T where T: Bound 是 blanket impl——慎用。本章 §7.3.4 讲 blanket impl 在 for_each_relevant_impl 里全扫——大量 blanket impl 会让 trait selection 变慢。如果你的库提供 50+ blanket impl、用户编译会很慢。改用 generic helper functions 或者更具体的 impl 集合。

5、关联类型 vs generic 参数——本章 §7.7 讲过 projection。关联类型让 trait 一对一（一个类型只能 impl 一次）、generic 参数让 trait 一对多。如果一个 trait 你希望”每个类型只 impl 一次的语义”——用关联类型。Iterator/Future/Add 都是这个模式的标准例子。

6、#[derive] 优于手写 impl——derive 宏生成的 impl 通常已经被高度优化（#[derive(Clone)] 对 Copy 类型生成的 impl 最终被 inline 成 memcpy）。手写 impl 时容易少加 #[inline] 之类的属性、影响性能。优先用 derive、确实需要定制时再手写。

这 6 条启示来自本章的源码细节——理解编译器内部让你能反向推断 API 设计应该长什么样。这是从”会用 trait”到”懂 trait 设计”的跨越。

7.13.0 读完本章能回答的具体问题清单

作为本章掌握度自测：

Trait selection 的三阶段是什么？为什么这么分？（§7.2——assemble/evaluate/confirm，分别对应”找候选/筛候选/应用候选”）
winnow_candidates 的 5 层优先级 ladder 是什么？（§7.2.3-bis——Sized→ParamCandidate dedupe→alias bound (Marker mode)→non-global where→alias bound > blanket）
assemble_candidates_from_impls 的三层 fast reject 分别是什么？（§7.2.3-ter——DeepReject、default impl、fn pointer impl）
EvaluatedToOkModuloRegions 是什么？为什么要这个状态？（§7.2.5——issue #80691、cache key 不带 lifetime 信息时的降级标记）
rustc 的 evaluation_cache 为什么分 global 和 local 两层？（§7.2.6——global 缓存普适真理、local 缓存 inference variable 相关）
TraitImpls 的 blanket vs non_blanket 索引为什么用不同数据结构？（§7.3.4——数量级 + 访问模式不同）
for_each_relevant_impl 在 self_ty 是 inference variable 时怎么处理？（§7.3.4——fallback 扫所有 non_blanket，性能最差）
overlapping_impls 为什么”双跑”？（§7.5.3——快路径检测 + 慢路径生成详细诊断）
fresh_impl_header 用 inference variable 替换 generic 是为了什么？（§7.5.4——unification problem 的标准做法、判 overlap 即 unify 是否成功）
specializes 函数的 5 步证明是什么？（§7.6.2——feature gate + polarity + 用严格环境 + parent fresh args + unify + 证 where clauses）
project 函数的 4 路 candidate 优先级？（§7.7.1——ParamEnv > trait_def > object > impl）
Projected::NoProgress(term) 表达什么语义？（§7.7.1——延迟决策、还不能确定时透传 unprojected 给上层）

能答 8 条以上——你对 rustc trait system 的理解已经超越大多数 Rust 应用开发者。这种深度的编译器知识在 unsafe Rust 库设计、trait API 的 ergonomic 优化、proc macro 写作等场景下都是稀缺技能。

7.13.1 本章源码定位索引

为便于读者按图索骥（基于 rustc nightly 2024-2025 master）：

主题	源文件	关键行号/位置
SelectionContext	`compiler/rustc_trait_selection/src/traits/select/mod.rs`	102-160
evaluate_candidate	同上	1279-1310
check/insert_evaluation_cache	同上	1312-1360
winnow_candidates 5 层 ladder	同上	1841+
assemble_candidates_from_impls	`select/candidate_assembly.rs`	600-643
reject_fn_ptr_impls	同上	650+
confirm_impl_candidate	`select/confirmation.rs`	428-449
vtable_impl + nested obligations	同上	451-481
TraitImpls + for_each_relevant_impl	`compiler/rustc_middle/src/ty/trait_def.rs`	150-219
overlapping_impls 双跑	`compiler/rustc_trait_selection/src/traits/coherence.rs`	155-198
fresh_impl_header inference vars	同上	201-221

源码版本：rustc nightly（compiler 子目录）。

7.13.2 本章与全书体系的呼应

Trait selection 是 Rust 类型系统的”心脏”——它和书中其他章节的接口比表面看起来更深：

与第 5 章（HIR）的衔接：HIR 阶段把用户写的 x.method() 表达式记下来——但不解析方法。本章的 trait selection 在 type-check 阶段被调用、给每个方法调用查出真正调用哪个 impl。HIR 是”问题陈述”、本章是”问题求解”。

与第 6 章（单态化）的衔接：单态化按”具体类型组合”生成代码副本——每份副本里调用哪个 impl 由本章的 trait selection 决定。两章合起来构成 Rust”零成本抽象”的完整证据：单态化保证”同样的代码对每种类型独立生成”、trait selection 保证”每份代码里调用的方法是确定的具体函数”。

与第 8 章（lifetime/borrow check）的接口：本章 §7.2.5 提到 EvaluatedToOkModuloRegions 把 lifetime 维度的检查推迟到 region check 阶段——trait selection 不解决 lifetime 问题——下一章的 borrow checker 接手。这种”分阶段解决不同维度”的设计是 rustc 编译器架构的核心。

与第 9 章（MIR 构建）的产出：本章产出的 ImplSource 包含被选中的 impl_def_id + generic args——这些信息被 MIR 构建阶段用来 emit 直接的 function call instruction。static dispatch 的”零成本”在这一步真正落地——MIR 里 Call(impl_method, args) 就是直接的 LLVM call。

与第 13 章（incremental compilation）的协作：本章 §7.2.6 讲过 evaluation_cache 的双层设计——global cache 进 incr query system、local cache 不进。incremental 编译能让 trait selection 在小改动后只重算少量 query——避免 100% 重做——这是大型 Rust 项目可工作的基础。

与第 17 章（Crate 元数据）的依赖：跨 crate 的 trait impl 通过 crate metadata 传递——本章 for_each_relevant_impl 调的 tcx.trait_impls_of 内部从 metadata 反序列化出 TraitImpls 结构。Trait impl 信息是跨 crate 的、必须通过 metadata 持久化——这条接口设计决定了 Rust 的”独立编译 + 全局类型检查”能并存。

读完本章 + 这 5 个接口，你能把 rustc 的整个类型检查链路在脑海里画出来——从 HIR 到 MIR 经过哪些阶段、每阶段做什么、依赖什么 query——这是看懂 rustc 全貌的关键。

7.14 本章小结

本章深入 rustc 源码解析了 trait 静态分发的完整机制。SelectionContext 的三阶段选择算法是核心引擎；TraitImpls 的两级索引实现高效 impl 查找；一致性规则从制度层面保证选择确定性；特化图管理 impl 优先级；投影规范化处理关联类型；resolve_associated_item 连接 trait 选择与代码生成。

最终结果是：静态分发生成的机器码与手写等效代码完全一致，零间接调用、可内联、可触发后续优化级联。这就是”零成本抽象”的编译器实现。

下一章我们将深入 dyn Trait 的内部——fat pointer 内存布局、vtable 构建过程，以及动态分发的完整编译器实现。

第7章 Trait 静态分发：零成本抽象的编译器实现

7.1 静态分发的本质：编译期方法解析

7.2 Trait 选择算法：三阶段流程

7.2.1 SelectionContext 与候选种类

7.2.2 阶段一：候选组装

7.2.3 阶段二：求值与筛选

7.2.3-bis 源码核对：winnow_candidates 的 5 层优先级 ladder

7.2.3-ter 源码核对：assemble_candidates_from_impls 的三层 fast reject

7.2.4 阶段三：确认

7.2.5 源码核对：evaluate_candidate 的 ModuloRegions 缓存策略

7.2.6 源码核对：can_use_global_caches 与 evaluation_cache 的双层缓存

7.2.7 源码核对：confirm_impl_candidate 的 rematch + ensure_sufficient_stack

7.3 Impl 查找：两级索引的高效设计

7.3.1 TraitImpls 数据结构

7.3.2 for_each_relevant_impl：快速筛选

7.3.3 impl 索引的构建

7.3.4 源码核对：for_each_relevant_impl 的 blanket vs non_blanket 双索引

7.4 与单态化的衔接

7.5 一致性规则与孤儿规则

7.5.1 孤儿规则

7.5.2 重叠检查

7.5.3 源码核对：overlapping_impls 的”双跑诊断”模式

7.5.4 源码核对：fresh_impl_header 的 inference variable 注入

7.6 特化：更具体的 impl 覆盖更一般的

7.6.1 特化图与 specializes 检查

7.6.2 源码核对：specializes 函数的 5 步证明算法

7.7 关联类型解析

7.7.1 源码核对：project 函数的 4 路 candidate 收集

7.8 Where 子句与 Trait Bound 验证

7.9 Blanket 实现的编译器处理

7.10 性能分析：零成本的汇编级证明

7.11 TraitDef：Trait 的编译器表示

7.11.1 TraitDef 的真实 13 字段与 edition-gated 方法派发

7.12 完整流程总结

7.13 边界情况

7.12.1 trait selection 在其他语言里的对应

7.12.2 几条 rustc trait 系统里”反直觉”的事实

7.12.3 trait selection 的演进——从 old solver 到 next solver

7.12.4 编译期 vs 运行期：trait 选择的耗时分布

7.12.5 给应用 Rust 开发者的 trait 设计启示

7.13.0 读完本章能回答的具体问题清单

7.13.1 本章源码定位索引

7.13.2 本章与全书体系的呼应

7.14 本章小结

7.11.1 `TraitDef` 的真实 13 字段与 edition-gated 方法派发