Rust 编译器与运行时揭秘

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

作者杨艺韬 · 15,485 字 · 发布于 2026-04-16 · 更新于 2026-09-24

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

本章要点

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

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:#047857,color:#fff,stroke:none
    style C3 fill:#10b981,color:#333,stroke:none
    style D fill:#b45309,color:#fff,stroke:none
    style D2 fill:#f59e0b,color:#333,stroke:none

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

Trait 选择是静态分发的核心，回答根本问题：对于给定的类型 T 和 trait Trait，应该使用哪个 impl？ 在 rustc 中由 SelectionContext（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:102-124）驱动，分为三阶段。

7.2.1 SelectionContext 与候选种类

// rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:102
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 定义了丰富的候选种类体系——1.96.0 里 SelectionCandidate 一共 21 个变体，下面只摘常见的几个：

// rust-1.96.0/compiler/rustc_middle/src/traits/select.rs:101
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
    // 余下 13 个：TransmutabilityCandidate / AsyncClosureCandidate /
    // AsyncFnKindHelperCandidate / CoroutineCandidate / FutureCandidate /
    // IteratorCandidate / AsyncIteratorCandidate / FnPointerCandidate /
    // TraitAliasCandidate / TraitUpcastingUnsizeCandidate(usize) /
    // BuiltinObjectCandidate / BuiltinUnsizeCandidate /
    // BikeshedGuaranteedNoDropCandidate
}

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:#2563eb,color:#fff,stroke:none
    style B3 fill:#7c3aed,color:#fff,stroke:none
    style C2 fill:#047857,color:#fff,stroke:none

7.2.2 阶段一：候选组装

assemble_candidates（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs:31）根据 trait 种类采用不同策略。对于 Sized/Copy 等语言级 trait 使用内建规则，对于一般 trait 则遍历 impl；where 子句候选则不分 trait 种类，最后统一收集：

// rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs:31（简化）
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_object_ty(obligation, &mut candidates);
        }
    }
    // match 之后，所有（正极性）trait 都会走下面三步
    self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
    self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
    self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
    Ok(candidates)
}

优先级规则至关重要：非全局的 where 子句候选优先于 impl 候选（保证泛型上下文可预测）；用户 impl 与内建候选同时适用时不分先后，直接判为歧义；多个 impl 同时适用时，才按特化关系保留更具体的那个（prefer_lhs_over_victim 调 specializes）。细节见 §7.21.1。

7.2.3 阶段二：求值与筛选

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

// rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:358（简化关键逻辑）
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（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:127-172）维护调用栈检测递归；filter_impls 在 rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1412、winnow_candidates 在 rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1841。对于 auto trait（Send/Sync），coinductive 循环被允许——reached_depth: Cell<usize> 的作用要说准：它初始等于 depth，一旦求值时撞上循环，就被设成"该循环全体参与者的最小深度"，这些参与者随即放弃缓存自己的结果。源码注释写明这是为 issue #60010 打的补丁——A: AutoTrait 依赖 B: AutoTrait（coinductive，可以）同时又有 C: NonAutoTrait 依赖 A: AutoTrait（non-coinductive，不行）时，B: AutoTrait 的 EvaluatedToOk 是建立在"假设 A: AutoTrait 成立"之上的，不能当成结论缓存。所以它是抑制缓存的标记，不只是"追踪循环深度"。

7.2.4 阶段三：确认

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

// rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/confirmation.rs:34（关键分支）
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（rust-1.96.0/compiler/rustc_trait_selection/src/traits/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);
}

这几行代码处理了 GitHub issue #80691 的具体 bug——caching with lifetime erasure 的 soundness 问题。当 trait predicate 里的 lifetime（比如 &'a T: Foo 里的 'a）被 freshener 擦除成 'erased（compiler/rustc_infer/src/infer/freshen.rs:101-115）时，求值结果如果是 EvaluatedToOk——会被缓存——下次 freshen 后相同的 query 直接返回 cache。

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

这种"cache key 不精确、就在结果上降级"是 rustc 类型检查的常见 pattern——lifetime 信息不进 cache key，但结果要标注"可能需要后续 region 验证"。注释里的 issue #80691 就是促成这条规则的那个真实 bug。

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

evaluate_candidate 后面的 check_evaluation_cache（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1312）/ insert_evaluation_cache（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1332，is_stack_dependent() 的短路在 rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1341）实现了一个双层缓存：

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）：挂在 TyCtxt 上，在本次编译里跨 InferCtxt、跨 query 复用。条件是 param_env 和 trait_pred 都不含 inference variable（即 "普适真理"），并且当前 typing mode 允许（coherence 阶段一律不用 global cache，正在定义 opaque type 时也有限制，见 can_use_global_caches）——比如 Vec<i32>: Clone 是真理、可以 global 缓存。

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

is_stack_dependent() 是另一道防线——如果结果是 EvaluatedToAmbigStackDependent（涉及推断变量的递归让求值无法得出确切结论、结果取决于当前求值栈）——完全不缓存（避免缓存"半完成"的递归结果）。

这种"多级 cache + 严格 invalidation 条件"是 rustc 性能的支柱之一——大型 crate 编译时 trait selection 会被反复调用，缓存命中率直接决定类型检查阶段的耗时——can_use_global_caches（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/mod.rs:1491）那几行判断因此是热路径上最关键的分支之一。

读到这一层可以推断：泛型和 trait bound 用得越重，类型检查时要证明的义务越多，其中含推断变量的只能走局部缓存、每个 InferCtxt 重新求值，编译时间也就随之上涨。代码风格会影响编译速度，具体多少要用 -Zself-profile 量。

7.2.7 源码核对：confirm_impl_candidate 的 rematch + ensure_sufficient_stack

§7.2.4 讲了确认阶段的整体流程。confirm_impl_candidate（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/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.21.2 提过 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 的）能让递归深度达数百层——超出 rustc 编译线程默认的 8MB 栈（compiler/rustc_interface/src/util.rs:103 的 DEFAULT_STACK_SIZE）就会栈溢出。ensure_sufficient_stack（compiler/rustc_data_structures/src/stack.rs:20）会检测当前栈剩余、不够时通过 stacker crate 另分配一段新栈——让递归继续而不栈溢出。

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

vtable_impl（rust-1.96.0/compiler/rustc_trait_selection/src/traits/select/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:101
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:135
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（精确匹配）。如果构建索引时也用 AsRigid，impl<T> Trait for T 中的 T 会被简化成 Placeholder、放进 Placeholder 这个桶，查询 i32: Trait 时就找不到它，导致查找遗漏。

7.3.3 impl 索引的构建

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

// compiler/rustc_middle/src/ty/trait_def.rs:200（简化：if let 改写为 match）
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:100-167，真实的数据结构和遍历逻辑值得逐行读（下面的块摘自该行段的首尾两处，中间的访问器已按标记略去，行内中文注释是本专栏所加）：

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

// …（中间是 impl TraitImpls 的 is_empty / blanket_impls / non_blanket_impls
//     等访问器，与本节论点无关，此处略去）

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(Not)，只保留最外层）。SimplifiedType 是个比 full Type 小得多的 enum——能直接做 hash key。

注释里的精彩 insight（第 152-155 行）：

"This way, when searching for some impl for T: Trait, 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；查询 T: Clone（T 是泛型参数）时则只看 blanket impls，所有 non-blanket 都跳过。

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。这是查询性能的最差情况。

注释里的 FIXME（第 141-145 行）暴露了一个长期 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:103（简化）
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); }

            // rebase_onto：trait 空间的参数换成选中 impl 的参数；
            // translate_args：方法若定义在被特化的父 impl 里，再把参数翻译到那个 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))
        }
        // ...
    }
}

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——这组 impl 参数由 trait 选择给出（impl_data.args），rebase_onto 把它拼到方法自身的泛型参数前面。translate_args（compiler/rustc_trait_selection/src/traits/specialize/mod.rs:84）处理的是特化：方法实际定义在被特化的父 impl 里（leaf_def.defining_node）时，把选中 impl 的参数翻译成父 impl 的参数。源码注释举的例子是：选中 impl<V> Foo for (V, V) 且 V=u32，翻译到 impl<T, U> Foo for (T, U) 就得到 T=U=u32。

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:131
// （:110 是同文件另一个函数折行签名的返回类型行）
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() 读的是 -Znext-solver 的 coherence 开关，而这个开关在 1.96 的 NextSolverConfig 里默认就是 true（compiler/rustc_session/src/config.rs:994-1000）——也就是说 coherence 阶段默认已经走新求解器，上面那条双跑分支只在用 -Znext-solver=no 显式关掉新求解器时才生效（compiler/rustc_session/src/options.rs:1669-1681）。新求解器把诊断和判定合一了，不需要这种双跑——这是 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 两者的 impl header（trait impl 就是整个 trait_ref，含 self_ty）——unify 失败、不重叠；unify 成功后，还要看两个 impl 的 where 子句在这组替换下有没有哪条肯定不成立（impl_intersection_has_impossible_obligation，compiler/rustc_trait_selection/src/traits/coherence.rs:284-304 的 overlap 函数），排除不掉才判为重叠。

举例：

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)]
use std::fmt::Debug;

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:26
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:85
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:236 起的 specializes 函数实现了RFC 1210 的精确算法（下面是简化版，省略了对 specializing impl 自身 trait_ref 的规范化，以及末尾针对 const impl 的附加检查）：

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();
    if !errors.is_empty() {
        return false;
    }
    // ……（省略：parent 是 const impl 时，要求 specializing impl 也是 const 且条件不更严）
    true
}

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。impl 的 polarity 由 tcx.impl_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 关系。

源码第 267 行的注释直接写着 "See RFC 1210 for more details and justification"——RFC 1210 在 2016 年就被接受，specialization 至今仍是 unstable feature。stable 化卡在哪里？ 主要是生命周期参数参与 specialization 时的 soundness 问题：由于生命周期在 codegen 前会被擦除，"哪个 impl 更具体"的判断不能依赖生命周期，否则会得到不 sound 的类型系统。这也是 min_specialization（只允许对带 rustc_specialization_trait 标记的 trait 特化）先落地、完整 specialization 至今卡在 nightly 的原因。

读这段代码能让你理解为什么 Rust 的 stabilization 这么慢——特性要在已知的 corner case 下都论证 sound 才会稳定。这种保守是为了尽量不把 soundness 问题带进 stable。

7.7 关联类型解析

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

// compiler/rustc_trait_selection/src/traits/project.rs:52
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 在最前。注释里特别标明（第 674-676 行）："Make sure that the following procedures are kept in order"，并说明 ParamEnv 必须排第一，因为它优先级最高。真正享有优先权的只有 ParamEnv：push_candidate（compiler/rustc_trait_selection/src/traits/project.rs:86-126）里，已有 ParamEnv 候选时后来的非 ParamEnv 候选一律丢弃；其余几类之间（以及两个不同的 ParamEnv 候选之间）再出现第二个，就转成 Ambiguous。where-bound 永远优先于 impl——和 §7.21.1 讲的 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 表示候选不唯一。但它并不立刻报错：opt_normalize_projection_term 收到 TooManyCandidates 后只把投影缓存记为 ambiguous、返回 Ok(None)（compiler/rustc_trait_selection/src/traits/project.rs:417-421），等推断取得进展后再试；到最后仍然定不下来，才作为歧义错误报告，让用户加类型注解或 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:61
pub struct FulfillmentContext<'tcx, E: 'tcx> {
    predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
    usable_in_snapshot: usize,
    _errors: PhantomData<E>,
}

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

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

// 示意（按 rustc_middle 的类型别名写）；实际定义在
// compiler/rustc_type_ir/src/predicate_kind.rs:18，以 Interner 为泛型参数
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 与单态化协同效果显著：

// library/alloc/src/string.rs:2891 —— 真实的 blanket impl 只是转发到内部特化 trait
impl<T: fmt::Display + ?Sized> ToString for T {
    #[inline]
    fn to_string(&self) -> String {
        <Self as SpecToString>::spec_to_string(self)
    }
}

// 同文件 line 2904 起，SpecToString 的 default（可被特化覆盖）实现：
impl<T: fmt::Display + ?Sized> SpecToString for T {
    #[inline]
    default fn spec_to_string(&self) -> String {
        let mut buf = String::new();
        let mut formatter =
            core::fmt::Formatter::new(&mut buf, core::fmt::FormattingOptions::new());
        // Bypass format_args!() to avoid write_str with zero-length strs
        fmt::Display::fmt(self, &mut formatter)
            .expect("a Display implementation returned an error unexpectedly");
        buf
    }
}

// 单态化为没有专门 SpecToString 的类型（例如用户自定义的 Point: Display）后：
// fn <Point as ToString>::to_string(self: &Point) -> String {
//     // 走 default 的 spec_to_string，其中的 Display::fmt
//     // 被静态解析为 <Point as Display>::fmt —— 直接调用！
//     ...
// }
// （i32 等整数类型有自己的 SpecToString impl，不经过 Formatter，见下文）

顺带一提，这里的 SpecToString 正是 §7.6 讲的 min_specialization 在标准库里的典型用法——str、char、各整数类型都有各自的 impl SpecToString，覆盖掉走 Formatter 的通用路径。

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

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

考虑以下代码：

trait Doubler { fn double(&self) -> i64; }
impl Doubler for i64 {
    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，rustc 1.96.0 -C opt-level=2，Intel 语法；为了单独看到这个实例，实测时给它加了 #[inline(never)] 并在别处用 i64 调用一次）：

static_dispatch:
    mov     rax, qword ptr [rdi]    ; 读取 *x
    add     rax, rax                ; double() 已内联，x * 2 被优化为自加
    ret

dynamic_dispatch 的汇编：

dynamic_dispatch:
    jmp     qword ptr [rsi + 24]    ; rsi = vtable 指针，从方法槽位取地址后间接跳转（尾调用）；rdi 已经是数据指针

特征	静态分发	动态分发
调用指令	`call concrete_fn`（直接，或内联后没有调用）	`call`/`jmp qword ptr [vtable+24]`（间接）
可否内联	可以	一般不能（除非优化器能确定具体类型、完成去虚化）
分支预测	目标固定，无需预测跳转目标	依赖间接跳转预测，可能 miss
额外内存访问	0 次	至少 1 次（读 vtable 槽位）

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

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

7.11 TraitDef：Trait 的编译器表示

// compiler/rustc_middle/src/ty/trait_def.rs:19
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` 的真实 14 字段与 edition-gated 方法派发

上面代码块给的是"摘要版"——真实 TraitDef（compiler/rustc_middle/src/ty/trait_def.rs:19-80）有 14 个字段，其中几个反映了 Rust 标准库和语言演化过程里不得不插入的边缘补丁：

pub struct TraitDef {
    pub def_id: DefId,
    pub safety: hir::Safety,
    pub constness: hir::Constness,
    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 个字段）漏掉的 4 个字段里有 2 个是edition 补丁，值得专门讲清楚——它们是 Rust 少有的"因为标准库要改但 edition 不允许破坏兼容而插入的编译器级开关"。

skip_array_during_method_dispatch: bool（line 54-57）：

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

TraitSpecializationKind 的三种值（compiler/rustc_middle/src/ty/trait_def.rs:85-98）：

pub enum TraitSpecializationKind {
    None,              // 默认：不允许 specialize
    Marker,            // 无方法、对 Marker trait 允许（Sized/FusedIterator）
    AlwaysApplicable,  // #[rustc_specialization_trait] 标记的 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 才能做到"用户调 v.into_iter().collect::<Vec<_>>() 时直接复用原来的缓冲区、不重新分配"这种优化（library/alloc/src/vec/spec_from_iter.rs 里 impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T>）、但 specialization 稳定化经过多年讨论仍然不敢放出来给用户——rustc_specialization_trait 的硬限制是折中——让标准库内部用、用户感知为"collect 就是快"、但不暴露不安全的一般 specialization 语法。

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

7.12 完整流程总结

graph TB
    subgraph "1. 类型检查"
        A1["推断 T = Circle"] --> A2["生成义务 Circle: Shape"]
        A2 --> A3["FulfillmentContext 验证"]
    end
    subgraph "2. Trait 选择"
        B1["assemble_candidates"] --> B2["找到 ImplCandidate"]
        B2 --> B3["confirm → ImplSource::UserDefined"]
    end
    subgraph "3. 单态化 + 代码生成"
        C1["生成 print_area::&lt;Circle&gt;"] --> C2["resolve_associated_item"]
        C2 --> C3["translate_args → Instance"]
        C3 --> C4["emit call &lt;Circle as Shape&gt;::area"]
    end
    A3 --> B1
    B3 --> C1
    style A3 fill:#2563eb,color:#fff,stroke:none
    style B3 fill:#7c3aed,color:#fff,stroke:none
    style C4 fill:#047857,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 内部使用非原子引用计数，标准库为它写了 impl !Send for Rc<T, A>，library/alloc/src/rc.rs:330）。在一致性检查中，coherence.rs 的 impl_intersection_has_negative_obligation 函数利用负面 trait bound 证明两个 impl 互斥：

// 示意（Rust 目前没有 `T: !Send` 这种否定 bound 语法，
// 下面只是表达 coherence 内部的推理形态）：
impl<T: Send> Process for T { ... }
// 若能声明「T 不是 Send」的另一个 impl，两者互斥、不重叠

编译器实际能利用的是 impl !Send for Foo 这种否定 impl（#![feature(negative_impls)]）： impl_intersection_has_negative_obligation（compiler/rustc_trait_selection/src/traits/coherence.rs:492）在两个 impl 的交集上尝试证明某个否定义务成立，成立即判定二者不可能同时适用。这条路径还要求 crate 打开 #![feature(with_negative_coherence)]：只有这时 OverlapMode 才是 WithNegative/Strict（compiler/rustc_middle/src/traits/specialization_graph.rs:62-81），overlap 才会调用它（compiler/rustc_trait_selection/src/traits/coherence.rs:250）；stable 下的重叠检查不会拿否定 impl 来证明互斥。

7.14 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。

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

理解多语言对照后再看 Rust trait——你会发现它的设计是在零成本、严格 sound、显式 trait 关系这几个目标之间做的取舍。

7.15 几条 rustc trait 系统里"反直觉"的事实

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

1、Vec<T>: Clone 不一定是真理——只有 T: Clone 才是。这意味着 trait selection 要先 dispatch 到 Vec 的 impl impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A>、再递归求解 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、trait 求解本身会溢出，但溢出的是编译器不是你的程序。impl<T> Trait for T where T: Trait 这种"自身递归"的 impl 在求解 Foo: Trait 时会展开成无穷的 Foo: Trait 义务——编译器靠 recursion_limit（默认 128）截断，报 error[E0275]: overflow evaluating the requirement，而不是让程序在运行时栈溢出。真正会在运行时无穷递归的是方法体互相调用——那属于 MIR/codegen 层，trait selection 不做终止性检查。

4、Box<dyn Trait> 本身并不实现 Trait——方法调用靠的是自动解引用。对自己定义的 trait，除非显式写了 impl Trait for Box<dyn Trait>，本章 §7.2.2 讲的 ImplCandidate 收集找不到 Box<dyn Trait>: Trait——把 Box<dyn Trait> 传给 fn need<T: Trait>(_: T) 会报 E0277。b.method() 能调通，是因为方法探测会沿自动解引用链逐步尝试接收者类型（compiler/rustc_hir_typeck/src/method/probe.rs），Box<dyn Trait> 解引用一步得到 dyn Trait——对 Box 这一步是编译器内建的解引用（compiler/rustc_middle/src/ty/sty.rs:1567 的 builtin_deref），不经过 Deref trait——再在 dyn Trait 上找到方法、经 vtable 调用。这条机制让 trait method 在 Box<dyn Trait> 上的"正常调用"实际上经过了自动解引用 + vtable lookup 两步。

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

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

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

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

Old solver（1.96 除 coherence 外默认仍在用的）：

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

Next solver（独立 crate compiler/rustc_next_trait_solver，1.96 里 10213 行；设计受 chalk 启发但并非直接使用 chalk）：

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

切换是渐进式的：NextSolverConfig（compiler/rustc_session/src/config.rs:994-1000）里 coherence: bool = true、globally: bool = false——1.96 里新求解器已经在 coherence 阶段默认启用，但尚未全局启用；全局启用要靠 -Znext-solver=globally 显式打开。

为什么 rustc 团队愿意在这上面投入多年？因为 trait system 的 unsoundness 是不能容忍的——一个 unsoundness 就能让 safe Rust 代码 segfault、违反 Rust 的核心承诺。new solver 用统一的 canonicalization 和搜索图缓存重写求解过程，目标之一就是修掉这些 unsoundness。

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

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

本节不给具体百分比——公开可核实的分阶段耗时数据依赖具体 crate 和机器，任何"典型比例"都是猜测。要看真实数字，rustc 自带了工具：

# 每个 query / pass 的自身耗时，含 trait selection 相关的 evaluate_obligation、
# codegen_select_candidate、normalize_canonicalized_projection 等
cargo +nightly rustc -- -Ztime-passes
cargo +nightly rustc -- -Zself-profile
# 用 measureme 的 summarize 工具读 .mm_profdata

可以从源码结构上确定的是：trait selection 不是只在 codegen 前跑一次的独立阶段，而是嵌在类型检查里被反复调用的 query——本章 §7.2.6 讲的双层 evaluation_cache 之所以存在，正是因为它的调用次数足够大到必须缓存。

cargo check 比 cargo build 快，主要是省略了 codegen + linking——但 trait selection 这部分仍然要做（它是 type checking 的一部分）。所以 cargo check 的下限就在那里。

这也解释了泛型 API 的编译期代价：泛型和 trait bound 越多，类型检查时要证明的义务越多，其中含推断变量的只能走局部缓存、走更贵的求值路径。优雅的 API 有编译时间代价——具体涨多少，只能用 -Zself-profile 在你自己的项目上量。

7.18 本章源码定位索引

为便于读者按图索骥（对应 Rust 1.96.0 的 compiler/ 源码）：

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

源码版本：Rust 1.96.0（compiler/ 子目录）。

7.19 本章与全专栏体系的呼应

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

与第 1 章（编译管线 / HIR 降级）的衔接：HIR 阶段把用户写的 x.method() 表达式记下来——但不解析方法。type-check 阶段把方法调用解析到 trait 方法、登记 T: Trait 这类义务，由本章的 trait selection 证明它们成立；泛型上下文里具体落到哪个 impl，要等单态化时由 resolve_associated_item（§7.4）选定。HIR 是"问题陈述"、本章是"问题求解"（第 1 章 §1.6 讲 AST → HIR 降级）。

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

与第 3、4 章（借用检查与生命周期）的接口：本章 §7.2.5 提到 EvaluatedToOkModuloRegions 把 lifetime 维度的检查推迟到 region check 阶段——trait selection 不解决 lifetime 问题——第 3、4 章讲的借用检查器和区域推断接手。这种"分阶段解决不同维度"的设计是 rustc 编译器架构的核心。

与第 1 章 §1.8（HIR → MIR 降级）的衔接：MIR 构建阶段并不把调用改写成 impl 方法——即使 Self 类型是具体的，MIR 里写的仍是 trait 方法，如 <Circle as Shape>::area(...)，泛型函数里则是 <T as Shape>::area(...)（rustc 1.96.0 -Zunpretty=mir 实测）。本章产出的 ImplSource 包含被选中的 impl_def_id + generic args，在单态化 / 代码生成时由 resolve_associated_item 用来把这个 trait 方法换成具体的 impl 方法 Instance。static dispatch 的"零成本"在这一步真正落地——换成具体 Instance 后，生成的就是直接的 LLVM call。

与第 17 章（增量编译）的协作：本章 §7.2.6 讲过 evaluation_cache 的双层设计——两层缓存的条目都带着求值对应的 DepNodeIndex（insert_evaluation_cache 的 dep_node 参数），命中时据此登记依赖（compiler/rustc_middle/src/traits/cache.rs:48-49 的 read_index），保证缓存结果与增量编译的依赖图一致。在 trait 求解之上，evaluate_obligation、codegen_select_candidate 这些 query 本身又受增量编译的红绿算法管理，小改动后不必全部重算。

跨 crate 依赖：crate 元数据：跨 crate 的 trait impl 通过 rustc_metadata 产出的 crate metadata 传递——本章 for_each_relevant_impl 调的 tcx.trait_impls_of 内部对每个依赖 crate 调 implementations_of_trait，从 metadata 读出 (impl DefId, SimplifiedType) 列表，再组装成 TraitImpls（§7.3.3）。Trait impl 信息是跨 crate 的、必须通过 metadata 持久化——这条接口设计决定了 Rust 的"独立编译 + 全局类型检查"能并存。

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

7.20 本章小结

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

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

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

7.21 源码核对

本章正文为了讲清主干做过简化。这一节把正文里每一处简化，逐条对回真实源码—— 路径、行号、以及正文没有展开的边界条件。想核对的读者可以照着逐条验证。

7.21.1 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 优先
    ...

    // 之后还有：ObjectCandidate、TraitUpcastingUnsizeCandidate 各取下标最小者；
    // 多个 ImplCandidate 之间按特化（prefer_lhs_over_victim）取舍，
    // impl 与内建候选并存则判歧义
    ...
}

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

Level 1：Sized 优先——Sized 是 Rust 类型系统的基石、几乎所有泛型 bound 都默认带 T: Sized。让 SizedCandidate 优先选中能避免和用户写的 where-bound 冲突。debug_assert_eq!(sized_candidates.next(), None) 断言永远只有一个 Sized candidate——源码注释的解释是，多个 Sized 候选就会互相重叠。

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）、sizedness trait、default trait 这几类 goal 用 CandidatePreferenceMode::Marker，此时 alias bound（关联类型 / opaque type 自身声明的 bound）优先于 where bound；其余 trait 用 Default 模式（compiler/rustc_type_ir/src/solve/mod.rs:115-133）。

Level 4：non-global ParamCandidate 优先——非全局的 where-bound（如 T: Trait，含泛型参数）优先于后面的 alias bound 和 impl；全局 where-bound（如 i32: Trait，不含泛型参数和 bound vars）不享有这个优先级，与非全局的同时出现则判歧义。源码第 1925-1926 行的注释直接写了 "Our handling of where-bounds is generally fairly messy but necessary for backwards compatibility, see #50825 for why we need to handle global where-bounds like this"——对全局 where-bound 的这种处理，是为了向后兼容。

Level 5：alias bound > blanket impl——这条注释直接写明 "fairly arbitrary but once again necessary for backwards compatibility"。backwards compatibility 是 Rust 编译器的重要约束——看起来"奇怪"的优先级规则背后，往往是 stable 之后不能再改的既有行为。

这套 ladder 反映了 Rust 类型系统多年磨合的政策结晶——最终落到 winnow_candidates 这两百来行代码里。

7.21.2 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, U> Foo<U> for Vec<T> 的参数 String 和 U 是否能 unify？deep reject 用 O(深度) 的快速形状匹配判定——避免昂贵的 full unification。

Layer 2：default impl 跳过——default impl<T> 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"的组合让大型项目编译时间可控——一个有上百个 impl 的 trait，在某次 obligation 求解时往往只有少数 impl 能通过 reject 走到 match——绝大部分工作被剔除在 fast path 里。