深入 Rust 编译器之 trait 解析rustc 旧式 trait solver 的 Selection、Fulfillment 与 Evaluation 机制【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust导读本文基于 Rust 官方编译器 rustc 开发指南中的 Trait resolution (old-style) 一章系统讲解 rustc 中trait 解析trait resolution的完整过程它如何为每一个 trait 引用obligation配对到具体的 impl如何通过 Selection、Fulfillment、Evaluation 三大部件协同工作以及候选收集candidate assembly、winnowing、confirmation 与 codegen 阶段二次选择等核心细节。读完本文你将理解fn clone_sliceT: Clone(...)这类泛型代码的约束在编译器内部是如何被验证的也能在阅读 rustc 源码主要集中在 compiler/rustc_trait_selection/src/traits/时快速定位到对应实现。说明本仓库中的该文档及本章其余小节描述的是 rustc当前旧式trait solver 的工作方式。rustc 正在设计新一代 trait solver其思路详见 chalk 子章节。核心概念从 T: Clone 到 obligationtrait 解析的本质是把每一个对 trait 的引用与一个 impl 配对。例如泛型函数fn clone_sliceT: Clone(x: [T]) - VecT { ... }以及调用let v: Vecisize clone_slice([1, 2, 3])此时 trait 解析的任务就是判断是否存在isize: Clone的 impl。但有些情况下尤其是泛型函数体内我们找不到具体 impl却能断定调用方必须提供某个 impl。看clone_slice的函数体fn clone_sliceT: Clone(x: [T]) - VecT { let mut v Vec::new(); for e in x { v.push((*e).clone()); // (*) } }标有(*)的那一行只有在下述条件成立时才合法T即*e的类型实现了Clone。由于此时不知道T具体是什么自然无法找到具体 impl但根据约束T: Clone可以断言存在一个 impl且该 impl 必须由调用方提供。rustc 用obligation义务一词指代一个需要 impl 的 trait 引用。trait 解析系统解决一个 obligation 的方式就是证明存在一个合适的 impl。这里对应到源码中的TraitObligation与PolyTraitObligation类型compiler/rustc_trait_selection/src/traits/mod.rs 与 compiler/rustc_infer/src/traits/mod.rs 中定义。还有一个值得注意的设计类型检查阶段不存储 trait 选择的结果只验证 trait 选择会成功。等到 codegen 阶段、所有具体类型都已确定时再重复一遍 trait 选择为每个方法调用挑出真正的实现并生成到输出二进制中。这种两遍选择的策略保证了类型检查的纯验证性质同时让单态化后的代码生成可以拿到最终 impl。三大组成部分Selection、Fulfillment、Evaluationtrait 解析由三个主要部分组成组成部分职责源码位置Selection选择决定如何解析一个具体的 obligation例如通过匹配Self类型的 impl 或通过参数环境中的 where 子句选择 impl 可能因 impl 自身的 where 子句产生嵌套 obligation必要时还需评估这些嵌套 obligation 来消除歧义compiler/rustc_trait_selection/src/traits/select/mod.rsFulfillment满足跟踪所有 obligation 是否被完全满足本质是一个待选择的 obligation 工作列表worklist一旦某个 obligation 选择成功就将其移出列表并把其嵌套 obligation 入队同时会对推理变量施加约束compiler/rustc_trait_selection/src/traits/fulfill.rsEvaluation评估在不约束任何推理变量的前提下检查 obligation 是否成立供 Selection 使用位于 compiler/rustc_trait_selection/src/traits/select/mod.rs 的 evaluate 系列逻辑Fulfillment 的载体是FulfillmentContextcompiler/rustc_trait_selection/src/traits/fulfill.rs#L61其内部维护一个ObligationForestPendingPredicateObligation作为 obligation 的森林结构并提供了在类型推断约束全部生成后把剩余歧义 obligation 报为错误的入口。这三者分工明确Selection 解决单条 obligation 怎么解Fulfillment 统筹所有 obligation 是否都解完Evaluation 提供不产生副作用地试探某条约束是否成立的能力供 Selection 在候选过多时做筛选。Selection决定 obligation 能否被解析Selection 是决定一个 obligation 能否被解析、以及如何解析走 impl 还是 where 子句等的过程。主接口是select()函数位于 compiler/rustc_trait_selection/src/traits/select/mod.rs#L293它接收一个 obligation返回SelectionResult可能的结果有三种Ok(Some(selection))—— 可以解析selection指明解析方式若走 impl还可能携带该 impl 要求的嵌套 obligationOk(None)—— 目前还无法确定能否解析最常见于 obligation 中含有未绑定的类型变量例如Vec_中的_Err(err)—— 确定无法解析原因是类型错误或不存在任何可能适用的 impl。从源码可以进一步印证select()内部先对TraitObligation做了一次到PolyTraitObligation的包装调用poly_select随后进行候选收集、过滤filter_impls、以及候选数大于 1 时的 winnowing 流程候选恰好为 1 时直接返回避免多余的 winnowing这既能改善类型推断也能改善错误报告见 compiler/rustc_trait_selection/src/traits/select/mod.rs#L424-L438 附近的注释。选择算法的基本流程分为两大阶段候选收集candidate assembly与确认confirmation。另外要注意一个与生命周期有关的细节由于生命周期推断的工作方式编译器无法即时判断两个生命周期之间的统一或子类型关系是否成立因此selection 过程中不进行生命周期匹配。这体现在子区域subregion赋值是永不失败的——它只会产生可能稍后被判定为错误的生命周期约束与之相对非生命周期约束在 selection 期间就已经检查完毕不可能再直接报错当然它们可能在下游引发其他错误。候选收集Candidate Assembly候选收集阶段搜索所有可能用来满足该 obligation的 impl、where 子句等每一个被称为一个候选candidate。源码实现是SelectionContext::assemble_candidatescompiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs#L32它从多个来源装配候选implassemble_candidates_from_impls见 candidate_assembly.rs、调用方约束/where 子句assemble_candidates_from_caller_bounds、投影类型等。为了避免歧义我们希望最终恰好找到一个确定适用的候选。但有些时候无法判断某个 impl/where 子句是否适用——当 obligation 含有未绑定的推理变量时就会发生这种情况此时SelectionCandidateSet.ambiguous标志会被置位见 compiler/rustc_trait_selection/src/traits/select/mod.rs#L171-L181。决定某个 impl/where 子句等是否适用于某个 obligation 的子例程统称为匹配matching过程。对于 impl 候选匹配就是忽略嵌套 obligation将 impl 头部Self类型与 trait 参数与 obligation 统一unify匹配成功就把它加入候选集合。内置 trait如Copy、Sized、CoerceUnsized在装配候选时则有另外的规则。第一轮装配完成后检查候选集合若候选集合是单元素集则直接结束——这就是作用域内唯一可能适用的 impl否则需要用 where 子句等条件对候选集合做winnowing筛减。Winnowing 借助evaluate_candidatecompiler/rustc_trait_selection/src/traits/select/mod.rs#L1270 附近检查嵌套 obligation 是否可能成立据此淘汰候选如果筛减后仍多于 1 个候选则通过candidate_should_be_dropped_in_favor_of之类的偏好规则对应源码中的winnow_candidates与CandidatePreferenceMode见 compiler/rustc_trait_selection/src/traits/select/mod.rs#L482-L486决定哪些候选让位给其他候选。如果最终集合收敛为唯一无歧义的候选就成功否则结果视为歧义ambiguous。Winnowing解决歧义的具体示例当存在多个 impl 且所有类型都能统一时会发生什么看这个经典例子trait Get { fn get(self) - Self; } implT: Copy Get for T { fn get(self) - T { *self } } implT: Get Get for BoxT { fn get(self) - BoxT { Box::new(T::get(self)) } }调用get(Box::new(1_u16))时Self类型是Boxu16——它同时能统一到两个 impl第一个对所有类型T生效第二个对所有BoxT生效。为了消除歧义编译器执行一轮 winnowing考虑 where 子句并尝试移除候选。本例中第一个 impl 要成立要求Boxu16: Copy而这并不成立。于是 winnowing 之后只剩一个候选可以继续推进。这个例子很好地说明了为什么 winnowing 需要调用evaluate_candidate评估Boxu16: Copy是否成立属于只检查、不约束推理变量的评估是 Selection 安全排除无效候选的基础。where 子句另一条主要解析路径除 impl 之外解析 obligation 的另一条主要途径是where 子句。selection 过程始终被赋予一个 参数环境parameter environment其中包含一组 where 子句——本质上是可以假定为可满足的 obligation 列表。解析时遍历该列表检查当前 obligation 能否在其中找到更精确地说是检查是否存在一个针对同一 trait或某个子 trait、且能与当前 obligation 匹配的 where 子句 obligation。如果找到则认为该 obligation 已满足。对应到源码这就是assemble_candidates_from_caller_boundscompiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs——从调用方参数环境收集候选并在 winnowing 时作为有力的优先项。示例trait A1 { fn do_a1(self); } trait A2 : A1 { ... } trait B { fn do_b(self); } fn fooX: A2 B(x: X) { x.do_a1(); // (*) x.do_b(); // (#) }在foo的函数体内显然可以对x调用A1、A2、B的方法。标(*)的行会产生 obligationX: A1标(#)的行会产生 obligationX: B。同时参数环境中包含两条 where 子句X: A2与X: B。对每条 obligation 都在该 where 子句列表中检索obligationX: B与 where 子句X: B平凡匹配解析 obligationX: A1时注意到X: A2蕴含X: A1因为A2: A1是超 trait 关系从而也能匹配成功。Confirmation统一输出类型参数确认confirmation阶段将 trait 的输出类型参数与 obligation 中的值统一起来可能产生类型错误。实现位于 compiler/rustc_trait_selection/src/traits/select/confirmation.rs#L35SelectionContext::confirm_candidate。假设有Converttrait 的如下变体trait ConvertTarget { fn convert(self) - Target; } impl Convertusize for isize { ... } // isize - usize impl Convertisize for usize { ... } // usize - isize let x: isize ...; let y: char x.convert(); // NOTE: y: char now!Confirmation 阶段会报告错误impl 规定Target是usize而 obligation 给出的是char两者统一失败因此 selection 的结果是错误。这里有一个值得注意的要点候选 impl 是根据Self类型挑选的而 confirmation 是根据本例中的Target类型参数完成的。也就是说候选选择与类型统一分别作用于 trait 引用的不同部分二者共同构成了完整的 trait 解析。Codegen 阶段的再次选择前面提到类型检查阶段不存储 trait 选择的结果。到 codegen 阶段编译器会重新执行 trait 选择为每个方法调用挑选具体 impl。这一步通过查询codegen_select_candidate完成其定义见 compiler/rustc_middle/src/queries.rs#L1628实际调用发生在单态化过程中compiler/rustc_monomorphize/src/lib.rs单态化时用完全单态化的类型环境TypingEnv::fully_monomorphized()发起查询拿到ImplSource::UserDefined后即可确定具体的impl_def_id用于生成代码。由于所有类型此时都已具体化这一次选择不再考虑任何 where 子句——已知每次解析最终都会落到某个具体 impl 上。一个有趣的细节是嵌套 obligation 的处理一般而言codegen 阶段只需要弄清楚哪个候选适用并不关心嵌套 obligation它们已被假定为真。但当前实现仍然会满足所有这些嵌套 obligation原因在于这有时能影响类型推断的结果——因为此时还没有拿到以 impl 类型变量表达的完整替换必须再跑一遍 trait 选择才能把一切弄清楚。结合源码的阅读路线如果你想在源码中亲自走一遍这条调用链可以按以下顺序阅读入口与工作列表compiler/rustc_trait_selection/src/traits/fulfill.rs 中的FulfillmentContext理解 obligation 如何注册、出队、在成功时展开嵌套 obligation选择主流程compiler/rustc_trait_selection/src/traits/select/mod.rs 中的select()/poly_select()、winnow_candidates、evaluate_candidate以及TraitObligationStack它用 freshen 后的 trait 谓词检测递归环防止A: Trait依赖自身的循环被错误缓存见同一文件中关于 #60010 的注释候选装配compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs 中的assemble_candidates及各assemble_candidates_from_*子例程impl、调用方约束、投影类型、内置 trait 等匹配与确认compiler/rustc_trait_selection/src/traits/select/_match.rs 处理 impl 匹配unify impl 头部confirmation.rs 处理输出类型的最终统一codegen 再选择compiler/rustc_middle/src/queries.rs 中的codegen_select_candidate查询定义及 compiler/rustc_monomorphize/src/lib.rs 中的调用方。与之配套的文档还包括参数环境理解 where 子句从何而来、traits 目录下的其他章节如 canonicalization、goals-and-clauses、specialization 等以及指向新 solver 设计的 chalk 子章节。小结本文完整复现了 rustc 开发指南中关于旧式 trait 解析一章的全部内容从 obligation 的定义与类型检查只验证、codegen 再选择的两遍策略到 Selection / Fulfillment / Evaluation 三大部件的分工从候选收集、matching、winnowing 消除歧义的具体示例到 where 子句匹配、confirmation 统一输出类型参数再到 codegen 阶段codegen_select_candidate的二次选择与嵌套 obligation 的再满足。理解这一流程是深入 rustc 类型检查、单态化乃至错误诊断代码的必备基础同时也要留意rustc 正在推进的新一代 trait solver 将逐步取代这里描述的旧式机制。【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考