尧图网页设计 
Rust 编译器的 Chalk 新式 trait 求解器把 trait 系统当作逻辑程序来求解【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust导读本文以 rustc-dev-guide 的 traits 章节 为核心系统讲解 Rust 编译器中的Chalk-based trait solving基于 Chalk 的新式 trait 求解它如何把 Rust 的 trait 系统重新表述为一套逻辑程序用类似 Prolog 的推理规则去求解 trait 义务obligation从而为 GAT泛型关联类型、specialization 等硬特性铺路。读完本文你将掌握 Chalk 的核心思想lowering 到逻辑、Goal/Clause 形式化定义、canonical 查询与规范化、它在 rustc 中的落地位置compiler/rustc_traits与各查询 provider以及它与当前默认 trait 求解器的关系。Chalk 是什么一个实验性的 trait 求解器Chalk-based trait solving 章节开宗明义Chalk 是 Rust 的一个实验性 trait 求解器由 rustc 的 Types 团队推进开发。它的长期目标是让一大批在旧求解器里极难实现的 trait 系统特性与 bug 修复变得可行典型代表就是GATsgeneric associated types泛型关联类型与specialization特化。需要说明的是rustc-dev-guide 原文记载于 2022 年 5 月前后此后 rustc 中实际推进的新求解器路线经历了演进但 Chalk 所奠定的逻辑编程视角把 trait 系统当成逻辑程序至今仍是理解 rustc trait 系统设计与下一代求解器rustc_next_trait_solver的基石。Chalk 方法的关键观察是Rust 的 trait 系统本质上就是一套逻辑它可以被映射到标准的逻辑推理规则上然后我们就能以非常类似于 Prolog 求解器的方式去寻找这些推理规则的解。不过在具体落地上标准的 Prolog 规则又称Horn 子句并不完全够用需要一种更具表达力的变体——也就是后文会展开的FOHHfirst-order hereditary harrop子句。设计发生在两个地方新式 trait 求解的设计工作并行发生在两个仓库/目录chalk实验设计层在 chalk 仓库中试验 trait 系统的新思想与设计rustc工程落地层一旦逻辑规则在 chalk 中确定下来就把它实现进 rustc——在 lowering降低模块中把 struct、trait、impl 声明映射为逻辑推理规则。在当前的 rustc 源码中这一落地主要体现在 compiler/rustc_traits/src/lib.rs 及其各子模块后文详述以及 rustc_middle/src/traits/mod.rs 中 Goal/Clause 等类型的定义。核心思想把 Rust traits 降低成逻辑详细推导见 Lowering to logic 章节。核心步骤是把 trait 与 impl 声明映射成逻辑推理规则绝大部分情况下这些规则就是 Horn 子句。trait 与 impl 的 Horn 子句化看一个最简单的例子声明一个 trait 和几个 impltrait Clone { } impl Clone for usize { } implT Clone for VecT where T: Clone { }用 Prolog 风格的记号可以映射为Clone(usize). Clone(Vec?T) :- Clone(?T). // 记号 A :- B 表示 若 B 为真则 A 为真。 // 换句话说B 蕴含 A。在 Prolog 术语里Clone(Foo)其中Foo是某个 Rust 类型是一个谓词predicate表达类型Foo实现了Clone这件事。这些规则被称为program clauses程序子句它们规定了该谓词在什么条件下可以被证明即被视为真。于是证明Clone(VecVecusize)就是规则的递归应用Clone(VecVecusize)可证如果Clone(Vecusize)可证如果Clone(usize)可证。确实可证因为存在直接 impl。反过来尝试证明Clone(VecBar)会失败因为没有Bar: Clone的 implClone(VecBar)可证如果Clone(Bar)可证。但不可证因为没有任何适用规则。这个映射可以轻松扩展到带多个输入类型的泛型 trait。例如EqT表示Self可以与类型T的值相等trait EqT { ... } impl Equsize for usize { } implT: EqU EqVecU for VecT { }映射为Eq(usize, usize). Eq(Vec?T, Vec?U) :- Eq(?T, ?U).类型检查普通函数goal 从何而来上面展示了如何从 traits/impls推导出证明 goal 的规则但类型检查关心的是另一面需要被证明的 goal 本身。这些 goal 正是由类型检查过程产生的。考虑类型检查如下函数fn foo() { bar::usize() } fn barU: EqU() { }bar带有一个 where 子句U: EqU因此foo要调用bar::usize()就必须证明usize: Equsize。我们可以定义一个谓词描述bar何时良构well-formedbarWellFormed(?U) :- Eq(?U, ?U).于是foo类型检查通过当且仅当bar::usize良构fooTypeChecks :- barWellFormed(usize).证明fooTypeChecks会成功fooTypeChecks可证如果barWellFormed(usize)可证如果Eq(usize, usize)因 impl 而可证。类型检查泛型函数超越 Horn 子句FOHH普通非泛型函数用Horn 子句 Rust 的类型相等就够了但泛型函数需要一种比 Prolog 更强的 goal 概念。把foo改造成泛型fn fooT: EqT() { bar::T() } fn barU: EqU() { }要检查foo的函数体我们必须把类型T保持抽象即检查foo的函数体对所有类型T都是类型安全的而不只是对某个具体类型。逻辑上可以这样表达fooTypeChecks :- // 对所有类型 T... forallT { // ...如果我们假设 Eq(T, T) 可证... if (Eq(T, T)) { // ...那么我们就能证明 barWellFormed(T) 成立。 barWellFormed(T) } }.问题在于标准 Horn 子句不允许在 goal 里出现全称量化forall和蕴含if虽然很多 Prolog 引擎以扩展形式支持它们。因此需要接受所谓的first-order hereditary harropFOHH子句——这个长名字说白了就是在体部body里带有forall和if的标准 Horn 子句。知道这个正式名称是有价值的学术界有大量工作讨论如何高效处理 FOHH 子句例如 Gopalan Nadathur 关于 Hereditary Harrop Formulas 证明过程的经典论文其参考文献列于 Chalk Book 的 bibliography。幸运的是支持 FOHH 并不真的很难而一旦做到我们就能轻易地用逻辑来描述foo这类泛型函数的类型检查规则。Goal 与 Clause 的形式化定义Goals and clauses 章节给出了严谨的元结构。用逻辑编程的术语说goal 是你必须证明的东西clause 是你已知为真的东西。Rust 的求解器基于 heredity harropHH子句的扩展——它在传统 Prolog Horn 子句之上增加了几项超能力。元结构Meta structuregoal 与 clause 互相引用、递归定义Goal DomainGoal // 见下方小节 | Goal Goal | Goal || Goal | existsK { Goal } // 存在量化 | forallK { Goal } // 全称量化 | if (Clause) { Goal } // 蕴含 | true // 平凡为真 | ambiguous // 永远不可证 Clause DomainGoal | Clause :- Goal // 若能证明 Goal则 Clause 为真 | Clause Clause | forallK { Clause } K type // 一种 kind | lifetime这类 goal 的证明过程本质上是深度优先搜索Nadathur 的论文给出了细节。在代码层面这些类型定义于 rustc 的 rustc_middle/src/traits/mod.rschalk 侧则定义于 chalk-ir crate。Domain goalstrait 逻辑的原子Domain goals域目标是 trait 逻辑的原子。把 clause 的定义稍微展平可以看到 clause 总是形如forallK1, ..., Kn { DomainGoal :- Goal }也就是说domain goals 正是 clause 的左侧LHS——在最细粒度上domain goals 就是 trait 求解器最终要去证明的东西。为了定义 domain goals先引入两个基础概念trait referencetrait 引用trait 的名字加上合适的输入P0..PnTraitRef P0: TraitNameP1..Pn例如u32: Display、VecT: IntoIterator都是 trait 引用。注意 Rust 表面语法还允许关联类型绑定如VecT: IntoIteratorItem T那不属于 trait 引用的范畴。projection投影一个关联项引用及其输入Projection P0 as TraitNameP1..Pn::AssocItemPn1..Pm由此DomainGoal定义如下DomainGoal Holds(WhereClause) | FromEnv(TraitRef) | FromEnv(Type) | WellFormed(TraitRef) | WellFormed(Type) | Normalize(Projection - Type) WhereClause Implemented(TraitRef) | ProjectionEq(Projection Type) | Outlives(Type: Region) | Outlives(Region: Region)其中WhereClause指 Rust 用户真的能在 Rust 程序里写出来的where 子句这个抽象只是为了方便——有时我们只想处理 Rust 中可书写的 domain goals。逐个拆解Implemented(TraitRef)例如Implemented(i32: Copy)当给定输入类型与生命周期下 trait 已实现时为真。ProjectionEq(Projection Type)例如ProjectionEqT as Iterator::Item u8关联类型Projection等于Type可以通过规范化normalization或占位关联类型来证明。Normalize(Projection - Type)例如T as Iterator::Item - u8关联类型Projection可以规范化为Type。Normalize蕴含ProjectionEq但反之不然一般而言证明Normalize(T as Trait::Item - U)还需要证明Implemented(T: Trait)。FromEnv(TraitRef)例如FromEnv(Self: Addi32)内层的TraitRef被假定为真即它可以由当前作用域内的 where 子句推导出来。例如fn loud_cloneT: Clone(stuff: T) - T { println!(cloning!); stuff.clone() }在函数体内我们有FromEnv(T: Clone)。作用域 where 子句是嵌套的impl 体内的函数体也会继承 impl 的 where 子句。FromEnv(TraitRef)蕴含Implemented(TraitRef)但反之不然——这个区分对implied bounds隐含边界至关重要。FromEnv(Type)例如FromEnv(HashSetK)内层类型被假定为良构即它是函数或 impl 的输入类型struct HashSetK where K: Hash { ... } fn loud_insertK(set: mut HashSetK, item: K) { println!(inserting!); set.insert(item); }由于HashSetK是loud_insert的输入类型我们在函数体内假定它良构于是有FromEnv(HashSetK)。又因为HashSet声明时带有K: Hash的 where 子句FromEnv(HashSetK)蕴含Implemented(K: Hash)——所以我们不必在loud_insert上重复这个边界而是自动假定其为真。WellFormed(Item)给定条目良构。可以是类型WellFormed(Veci32)在 Rust 中为真WellFormed(Vecstr)为假因为str不是Sized也可以是 trait 引用如WellFormed(Veci32: Clone)。良构性对 implied bounds 很关键loud_clone之所以可以假定FromEnv(T: Clone)是因为我们在每个调用点同时验证WellFormed(T: Clone)loud_insert同理。Outlives(Type: Region)、Outlives(Region: Region)例如Outlives(a str: b)、Outlives(a: static)左侧类型/区域存活outlive右侧区域。余归纳目标Coinductive goals系统中大多数 goal 是**归纳inductive**的不允许循环推理。例如子句Implemented(Foo: Bar) :- Implemented(Foo: Bar).按归纳理解该子句毫无用处要证明Implemented(Foo: Bar)就得递归证明它自己循环无穷无尽求解器会在此终止只是把Implemented(Foo: Bar)视为未知为真。但有些 goal 是**余归纳co-inductive**的循环是允许的。Auto traits 是典型例子。考虑Sendtrait 与如下结构体struct Foo { next: OptionBoxFoo }auto traits 的默认规则是Foo是Send当且仅当其字段类型是Send。于是有规则Implemented(Foo: Send) :- Implemented(OptionBoxFoo: Send).证明OptionBoxFoo: Send会循环地要求证明Foo: Send——这是个循环但没关系我们确实认为Foo: Send成立尽管它引用了自身。直觉是余归纳 trait 用于枚举固定的一组可能性。对 auto traits我们枚举的是从给定起点可达的类型集合Foo可达OptionBoxFoo进而可达BoxFoo、Foo循环闭合。除 auto traits 外WellFormed谓词也是余归纳的用于达成类似的枚举所有情形模式参见 implied bounds 章节的说明。Canonical 查询rustc 与交互式 Prolog的差异Canonical queries 与 Canonicalization 两章解释了 trait 系统的入口canonical query。传统 Prolog 的交互式查询传统 Prolog 系统会枚举所有可能答案。给出查询?- Veci32: AsRef?U求解器可能回答Veci32: AsRef[i32]问 continue? (y/n)按y可能得到下一个答案Veci32: AsRefVeci32来自反射 implimplT AsRefT for T再按y可能得到no。有些查询答案无穷多——比如?- Vec?U: Clone会不断给出Veci32: Clone、VecBoxi32: Clone、VecBoxBoxi32: Clone……直到内存耗尽。rustc 的 trait 查询寻找无歧义答案rustc 的 trait 查询做法不同它不枚举所有答案而是寻找**无歧义unambiguous**的答案。当它给出某个类型变量的值时意味着在当前 impl 与 where 子句集合下这是唯一可证的实例化。trait 查询的响应通常是ResultQueryResultT, NoSolutionErr(NoSolution)查询为假、无任何答案如Boxi32: Copy。Ok(QueryResult)包含四部分信息Certainty确定性Proven已知为真如Veci32: Clone、Rc?T: Clone或Ambiguous尚无法判定真假通常因为缺少更多类型信息如Vec?T: Clone。Var values变量值原查询中每个未绑定推理变量的取值Prolog 中需要靠反解得到rustc 直接给出替换。Region constraints区域约束输入生命周期之间必须成立的关系。Value类型T的附加值对某些专门查询如关联类型规范化用来携带额外结果通常只是()。示例Borrow trait 的两个查询考虑Borrowtrait 的两个 impl显式写出Sized边界以便说明implT BorrowT for T where T: ?Sized implT Borrow[T] for VecT where T: Sized例 1——类型检查fn fooA, B(a: A, vec_b: OptionB) where A: BorrowB { } fn main() { let mut t: Vec_ vec![]; // Type: Vec?T let mut u: Option_ None; // Type: Option?U foo(t, u); // 要求 Vec?T: Borrow?U ... }Vec?T: Borrow?U存在多个解?U Vec?T、?U [?T]、?T u32, ?U [u32]……因此返回Certainty:Ambiguous——尚不能确定是否成立Var values:[?T ?T, ?U ?U]——没学到任何变量取值。类型检查中这不是立即报错检查器会扣住这条义务Vec?T: Borrow?U等待若?T、?U后来被其他来源约束就再次发起查询。例 2——给u赋值fn fooA, B(a: A, vec_b: OptionB) where A: BorrowB { } fn main() { let mut t: Vec_ vec![]; // Type: Vec?T let mut u: Option_ None; // Type: Option?U foo(t, u); // Vec?T: Borrow?U ambiguous u Some(vec![]); // ?U Vec?V }赋值迫使?U与Vec?V统一。类型检查器回头处理之前扣住的义务Vec?T: Borrow?U此时?U已有值查询刷新为Vec?T: BorrowVec?V这次只有一个适用 impl反射 implimplT BorrowT for T where T: ?Sized于是回答Certainty:ProvenVar values:[?T ?T, ?V ?T]——义务成立且?T与?V是同一类型但还不知道具体是什么类型。事实上函数到此结束类型检查器会报错t与u的元素类型虽已互相绑定但依然未知。Canonicalization把推理变量与其环境隔离Canonicalization 是实现 canonical queries 的关键把推理值与其上下文隔离。概念非常简单每个推理变量要么未绑定还不知道类型要么绑定已知。要隔离一个含有类型/区域的数据结构T只需遍历其中出现的未绑定变量把它们替换成从零编号、固定顺序的canonical variablescanonical 占位符。例如类型X (?T, ?U)?T、?U是互不相同的未绑定推理变量其 canonical 形式是(?0, ?1)Y (?U, ?T)也规范化为(?0, ?1)但Z (?T, ?T)规范化为(?0, ?0)。推理变量的确切身份不重要——除非它被重复使用。这既改善缓存也能在 trait 解析中检测循环两个 trait 查询若有相同的 canonical 形式就会得到相同答案答案以 canonical 变量表达再映射回原变量。完整的 canonical 查询流程1. Canonicalize 查询。求解?A: Foostatic, ?B?A、?B未绑定。trait 系统通常忽略生命周期、平等对待因此 canonicalize 时也会把自由生命周期替换为 canonical 变量注意static在这里是自由生命周期——我们只在该 trait 引用的语境中考虑它而不是整个程序的 typing context。结果是?0: Foo?1, ?2也写作forT,L,T { ?0: Foo?1, ?2 }其中T表示类型变量、L表示生命周期变量。canonicalize方法同时返回CanonicalVarValues数组 OV记录各 canonical 变量的原始值[?A, static, ?B]这个 OV 在处理查询响应时需要用到。2. 执行查询。构造好 canonical 查询后创建全新推理上下文用替换 S 实例化 canonical 查询——为每个 canonical 变量分配一个合适 kind 的全新推理变量。对示例查询S 可能是S [?A, ?B, ?C]替换后得到完全实例化的查询?A: Foo?B, ?C。求解器求解它得到Proven/Ambiguous的确定性值并对新建的推理变量产生副作用。例如若只有唯一 implimpla, X Fooa, X for VecX where X: a { ... }则会新建?D、?E并统一?B ?D、?A Vec?E、?C ?E同时积累区域约束?E: ?D。最后要提升这些值出查询的推理上下文——做法是对查询结果再次 canonicalize。3. Canonicalize 查询结果。复用替换 S在求解后刷新它S [Vec?E, ?D, ?E]这些正是原查询三个输入变量的新值但混入了?E这类新变量。再次 canonicalize 整个查询响应 QR 让它们消失QR { certainty: Proven, var_values: [Vec?E, ?D, ?E] region_constraints: [?E: ?D], value: (), }结果为Canonical(QR) forT, L { certainty: Proven, var_values: [Vec?0, ?1, ?0] region_constraints: [?0: ?1], value: (), }微妙之处canonicalize 查询结果时自由生命周期不做特殊处理——两处?D被转换成同一个 canonical 变量?1这与原查询每个自由生命周期都变成全新 canonical 变量形成对比。4. 处理 canonical 结果。把结果应用回原始上下文概念上分三步——(a) 用全新推理变量实例化结果中的每个 canonical 变量(b) 将结果值与原值统一?A与Vec?C、static与?D、?B与?C(c) 记录区域约束?C: static供稍后验证。rustc 实际做的是该过程的轻度优化变体不急于实例化全部 canonical 值而是遍历值向量遇到值恰好是 canonical 变量的情形直接反解如values[2]是?C就推导?C : ?B、?D : static拿不到值的部分才创建推理变量。在 rustc 中的落地rustc_traits 查询 providerChalk 的规则被实现进 rustc 后直接的表现是 compiler/rustc_traits crate——从源码结构看它是一个独立的查询 provider 集合承载与主求解器代码无关的查询。其 lib.rs 将各模块的 provider 注册进Providersdropck_outlivesdrop check 相关的 outlives 查询evaluate_obligation义务求值implied_outlives_bounds隐含的 outlives 边界normalize_projection_ty投影类型规范化normalize_erasing_regions擦除区域后的规范化type_op类型操作查询另有codegen_select_candidate代码生成阶段的候选选择与coroutine_hidden_types协程隐藏类型。以 implied_outlives_bounds.rs 为典型示例该文件头注释明确指出不要直接调用此查询参见rustc_trait_selection::traits::implied_outlives_bounds其实现通过enter_canonical_trait_query进入 canonical trait 查询框架把ParamEnvAnd { param_env, value: ImpliedOutlivesBounds { ty } }交给query_compute_implied_outlives_bounds计算最终返回CanonicalQueryResponseVecOutlivesBound。这正体现了本章所述的 canonical 查询模式在真实 rustc 查询系统中的运用输入被 canonicalize输出是 canonical 化的QueryResponse。配套机制implied boundsImplied bounds 章节解释了与求解器配套的隐含边界机制——fn fooa, T(x: a T)可以自由假定T: a成立而不必显式写出。它分两类显式隐含边界由inferred_outlives_of计算见 compiler/rustc_hir_analysis/src/outlives/mod.rs只有 ADT 和 CTA 拥有通过inferred_outlives_crate查询中的不动点算法计算insert_required_clauses_to_be_wf处理所有 ADT 字段insert_outlives_clause分解 outlives 子句且不会添加static要求。隐式隐含边界由于尚不能在 binder 中处理蕴含这些边界不会加入受影响的ParamEnv而是在词法区域解析OutlivesEnvironment::from_normalized_bounds与 MIR borrowckUniversalRegionRelationsBuilder::add_implied_bounds中单独添加其假设约束由implied_outlives_bounds查询从wf::obligations中直接提取。证明侧则通过发出WellFormed谓词来保证所有使用类型良构——但由于实例化 impl 时不能发出WellFormed谓词否则引发求解器循环且缺少高阶区域 binder 的隐含边界目前存在若干已知 soundness 缺口如 [#25860]、[#84591]、[#100051] 所描述的通过子类型、超 trait 向上转换、投影规范化等路径。配套机制缓存Trait 选择结果会缓存但过程复杂即使 trait 引用中的类型未完全已知也希望可缓存此时 trait 选择会同时影响类型变量因此缓存的不只是结果还要能重放其对类型变量的副作用。大致思路详见 Caching先把所有未绑定推理变量替换为占位符usize : Foo$t→usize : Foo$0再查缓存命中则取下一步动作如应用 impl #22未命中则从头走选择流程并记录缓存项。微妙之处在于结果会随作用域内 where 子句变化因此存在本地缓存挂在ParamEnv上与全局缓存挂在tcx上两个缓存决定用哪个缓存的规则非常保守只要作用域里有任何 where 子句就用本地缓存历史上更细粒度区分导致过 #22019、#18290 之类的诡异 bug。文档记载该简单规则在编译 rustc 自身时命中率约 95%注意rustc-dev-guide 亦标注pick_candidate_cache在新版本中可能已不存在本节更多是理解缓存设计的历史与原则。与旧式求解器的关系Traits 章节目录 明确指出resolution.md描述的是当前默认求解器的工作方式而 chalk 章节描述的是正在设计中的新式求解器。二者在术语上也有对照旧式求解器讲 selection选择、fulfillment履行、evaluation求值三大件其中 selection 又分为candidate assembly候选装配与confirmation确认两个阶段通过 winnowing利用 where 子句与条件剔除候选解决多候选歧义而 Chalk 路线则把同一套问题重新表述为 goal/clause 的证明搜索。可以说Chalk 的目标不是推翻 trait 系统要回答的问题而是为这些问题提供一套更接近逻辑编程、表达能力更强的求解框架以便实现 GATs、specialization 等对旧算法而言硬骨头级别的特性。小结与进一步阅读Chalk-based trait solving 的完整图景可以概括为四层思想层trait 系统 ≈ 逻辑trait/impl 可降低为 Horn 子句泛型函数需要 FOHHforallif形式层Goal/Clause 递归元结构 七类 DomainGoalImplemented、ProjectionEq、Normalize、FromEnv×2、WellFormed×2、Outlives×2 余归纳目标auto traits、WellFormed机制层canonical query——canonicalize 查询 → 实例化求解 → canonicalize 结果 → 回填原上下文配合 implied bounds 与双层缓存实现层compiler/rustc_traits 以 canonical trait 查询框架落地各 provider如implied_outlives_bounds。感兴趣的读者可继续深入 rustc-dev-guide 的 traits 目录 下的其余章节lowering-to-logic、goals-and-clauses、canonical-queries、canonicalization、implied-bounds、caching、resolution或直接阅读 compiler/rustc_traits 与 rustc_trait_selection 的源码观察这些逻辑规则如何被编译进 rustc 并支撑日常的类型检查。【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Rust 编译器的 Chalk 新式 trait 求解器：把 trait 系统当作逻辑程序来求解
Rust 编译器的 Chalk 新式 trait 求解器把 trait 系统当作逻辑程序来求解【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust导读本文以 rustc-dev-guide 的 traits 章节 为核心系统讲解 Rust 编译器中的Chalk-based trait solving基于 Chalk 的新式 trait 求解它如何把 Rust 的 trait 系统重新表述为一套逻辑程序用类似 Prolog 的推理规则去求解 trait 义务obligation从而为 GAT泛型关联类型、specialization 等硬特性铺路。读完本文你将掌握 Chalk 的核心思想lowering 到逻辑、Goal/Clause 形式化定义、canonical 查询与规范化、它在 rustc 中的落地位置compiler/rustc_traits与各查询 provider以及它与当前默认 trait 求解器的关系。Chalk 是什么一个实验性的 trait 求解器Chalk-based trait solving 章节开宗明义Chalk 是 Rust 的一个实验性 trait 求解器由 rustc 的 Types 团队推进开发。它的长期目标是让一大批在旧求解器里极难实现的 trait 系统特性与 bug 修复变得可行典型代表就是GATsgeneric associated types泛型关联类型与specialization特化。需要说明的是rustc-dev-guide 原文记载于 2022 年 5 月前后此后 rustc 中实际推进的新求解器路线经历了演进但 Chalk 所奠定的逻辑编程视角把 trait 系统当成逻辑程序至今仍是理解 rustc trait 系统设计与下一代求解器rustc_next_trait_solver的基石。Chalk 方法的关键观察是Rust 的 trait 系统本质上就是一套逻辑它可以被映射到标准的逻辑推理规则上然后我们就能以非常类似于 Prolog 求解器的方式去寻找这些推理规则的解。不过在具体落地上标准的 Prolog 规则又称Horn 子句并不完全够用需要一种更具表达力的变体——也就是后文会展开的FOHHfirst-order hereditary harrop子句。设计发生在两个地方新式 trait 求解的设计工作并行发生在两个仓库/目录chalk实验设计层在 chalk 仓库中试验 trait 系统的新思想与设计rustc工程落地层一旦逻辑规则在 chalk 中确定下来就把它实现进 rustc——在 lowering降低模块中把 struct、trait、impl 声明映射为逻辑推理规则。在当前的 rustc 源码中这一落地主要体现在 compiler/rustc_traits/src/lib.rs 及其各子模块后文详述以及 rustc_middle/src/traits/mod.rs 中 Goal/Clause 等类型的定义。核心思想把 Rust traits 降低成逻辑详细推导见 Lowering to logic 章节。核心步骤是把 trait 与 impl 声明映射成逻辑推理规则绝大部分情况下这些规则就是 Horn 子句。trait 与 impl 的 Horn 子句化看一个最简单的例子声明一个 trait 和几个 impltrait Clone { } impl Clone for usize { } implT Clone for VecT where T: Clone { }用 Prolog 风格的记号可以映射为Clone(usize). Clone(Vec?T) :- Clone(?T). // 记号 A :- B 表示 若 B 为真则 A 为真。 // 换句话说B 蕴含 A。在 Prolog 术语里Clone(Foo)其中Foo是某个 Rust 类型是一个谓词predicate表达类型Foo实现了Clone这件事。这些规则被称为program clauses程序子句它们规定了该谓词在什么条件下可以被证明即被视为真。于是证明Clone(VecVecusize)就是规则的递归应用Clone(VecVecusize)可证如果Clone(Vecusize)可证如果Clone(usize)可证。确实可证因为存在直接 impl。反过来尝试证明Clone(VecBar)会失败因为没有Bar: Clone的 implClone(VecBar)可证如果Clone(Bar)可证。但不可证因为没有任何适用规则。这个映射可以轻松扩展到带多个输入类型的泛型 trait。例如EqT表示Self可以与类型T的值相等trait EqT { ... } impl Equsize for usize { } implT: EqU EqVecU for VecT { }映射为Eq(usize, usize). Eq(Vec?T, Vec?U) :- Eq(?T, ?U).类型检查普通函数goal 从何而来上面展示了如何从 traits/impls推导出证明 goal 的规则但类型检查关心的是另一面需要被证明的 goal 本身。这些 goal 正是由类型检查过程产生的。考虑类型检查如下函数fn foo() { bar::usize() } fn barU: EqU() { }bar带有一个 where 子句U: EqU因此foo要调用bar::usize()就必须证明usize: Equsize。我们可以定义一个谓词描述bar何时良构well-formedbarWellFormed(?U) :- Eq(?U, ?U).于是foo类型检查通过当且仅当bar::usize良构fooTypeChecks :- barWellFormed(usize).证明fooTypeChecks会成功fooTypeChecks可证如果barWellFormed(usize)可证如果Eq(usize, usize)因 impl 而可证。类型检查泛型函数超越 Horn 子句FOHH普通非泛型函数用Horn 子句 Rust 的类型相等就够了但泛型函数需要一种比 Prolog 更强的 goal 概念。把foo改造成泛型fn fooT: EqT() { bar::T() } fn barU: EqU() { }要检查foo的函数体我们必须把类型T保持抽象即检查foo的函数体对所有类型T都是类型安全的而不只是对某个具体类型。逻辑上可以这样表达fooTypeChecks :- // 对所有类型 T... forallT { // ...如果我们假设 Eq(T, T) 可证... if (Eq(T, T)) { // ...那么我们就能证明 barWellFormed(T) 成立。 barWellFormed(T) } }.问题在于标准 Horn 子句不允许在 goal 里出现全称量化forall和蕴含if虽然很多 Prolog 引擎以扩展形式支持它们。因此需要接受所谓的first-order hereditary harropFOHH子句——这个长名字说白了就是在体部body里带有forall和if的标准 Horn 子句。知道这个正式名称是有价值的学术界有大量工作讨论如何高效处理 FOHH 子句例如 Gopalan Nadathur 关于 Hereditary Harrop Formulas 证明过程的经典论文其参考文献列于 Chalk Book 的 bibliography。幸运的是支持 FOHH 并不真的很难而一旦做到我们就能轻易地用逻辑来描述foo这类泛型函数的类型检查规则。Goal 与 Clause 的形式化定义Goals and clauses 章节给出了严谨的元结构。用逻辑编程的术语说goal 是你必须证明的东西clause 是你已知为真的东西。Rust 的求解器基于 heredity harropHH子句的扩展——它在传统 Prolog Horn 子句之上增加了几项超能力。元结构Meta structuregoal 与 clause 互相引用、递归定义Goal DomainGoal // 见下方小节 | Goal Goal | Goal || Goal | existsK { Goal } // 存在量化 | forallK { Goal } // 全称量化 | if (Clause) { Goal } // 蕴含 | true // 平凡为真 | ambiguous // 永远不可证 Clause DomainGoal | Clause :- Goal // 若能证明 Goal则 Clause 为真 | Clause Clause | forallK { Clause } K type // 一种 kind | lifetime这类 goal 的证明过程本质上是深度优先搜索Nadathur 的论文给出了细节。在代码层面这些类型定义于 rustc 的 rustc_middle/src/traits/mod.rschalk 侧则定义于 chalk-ir crate。Domain goalstrait 逻辑的原子Domain goals域目标是 trait 逻辑的原子。把 clause 的定义稍微展平可以看到 clause 总是形如forallK1, ..., Kn { DomainGoal :- Goal }也就是说domain goals 正是 clause 的左侧LHS——在最细粒度上domain goals 就是 trait 求解器最终要去证明的东西。为了定义 domain goals先引入两个基础概念trait referencetrait 引用trait 的名字加上合适的输入P0..PnTraitRef P0: TraitNameP1..Pn例如u32: Display、VecT: IntoIterator都是 trait 引用。注意 Rust 表面语法还允许关联类型绑定如VecT: IntoIteratorItem T那不属于 trait 引用的范畴。projection投影一个关联项引用及其输入Projection P0 as TraitNameP1..Pn::AssocItemPn1..Pm由此DomainGoal定义如下DomainGoal Holds(WhereClause) | FromEnv(TraitRef) | FromEnv(Type) | WellFormed(TraitRef) | WellFormed(Type) | Normalize(Projection - Type) WhereClause Implemented(TraitRef) | ProjectionEq(Projection Type) | Outlives(Type: Region) | Outlives(Region: Region)其中WhereClause指 Rust 用户真的能在 Rust 程序里写出来的where 子句这个抽象只是为了方便——有时我们只想处理 Rust 中可书写的 domain goals。逐个拆解Implemented(TraitRef)例如Implemented(i32: Copy)当给定输入类型与生命周期下 trait 已实现时为真。ProjectionEq(Projection Type)例如ProjectionEqT as Iterator::Item u8关联类型Projection等于Type可以通过规范化normalization或占位关联类型来证明。Normalize(Projection - Type)例如T as Iterator::Item - u8关联类型Projection可以规范化为Type。Normalize蕴含ProjectionEq但反之不然一般而言证明Normalize(T as Trait::Item - U)还需要证明Implemented(T: Trait)。FromEnv(TraitRef)例如FromEnv(Self: Addi32)内层的TraitRef被假定为真即它可以由当前作用域内的 where 子句推导出来。例如fn loud_cloneT: Clone(stuff: T) - T { println!(cloning!); stuff.clone() }在函数体内我们有FromEnv(T: Clone)。作用域 where 子句是嵌套的impl 体内的函数体也会继承 impl 的 where 子句。FromEnv(TraitRef)蕴含Implemented(TraitRef)但反之不然——这个区分对implied bounds隐含边界至关重要。FromEnv(Type)例如FromEnv(HashSetK)内层类型被假定为良构即它是函数或 impl 的输入类型struct HashSetK where K: Hash { ... } fn loud_insertK(set: mut HashSetK, item: K) { println!(inserting!); set.insert(item); }由于HashSetK是loud_insert的输入类型我们在函数体内假定它良构于是有FromEnv(HashSetK)。又因为HashSet声明时带有K: Hash的 where 子句FromEnv(HashSetK)蕴含Implemented(K: Hash)——所以我们不必在loud_insert上重复这个边界而是自动假定其为真。WellFormed(Item)给定条目良构。可以是类型WellFormed(Veci32)在 Rust 中为真WellFormed(Vecstr)为假因为str不是Sized也可以是 trait 引用如WellFormed(Veci32: Clone)。良构性对 implied bounds 很关键loud_clone之所以可以假定FromEnv(T: Clone)是因为我们在每个调用点同时验证WellFormed(T: Clone)loud_insert同理。Outlives(Type: Region)、Outlives(Region: Region)例如Outlives(a str: b)、Outlives(a: static)左侧类型/区域存活outlive右侧区域。余归纳目标Coinductive goals系统中大多数 goal 是**归纳inductive**的不允许循环推理。例如子句Implemented(Foo: Bar) :- Implemented(Foo: Bar).按归纳理解该子句毫无用处要证明Implemented(Foo: Bar)就得递归证明它自己循环无穷无尽求解器会在此终止只是把Implemented(Foo: Bar)视为未知为真。但有些 goal 是**余归纳co-inductive**的循环是允许的。Auto traits 是典型例子。考虑Sendtrait 与如下结构体struct Foo { next: OptionBoxFoo }auto traits 的默认规则是Foo是Send当且仅当其字段类型是Send。于是有规则Implemented(Foo: Send) :- Implemented(OptionBoxFoo: Send).证明OptionBoxFoo: Send会循环地要求证明Foo: Send——这是个循环但没关系我们确实认为Foo: Send成立尽管它引用了自身。直觉是余归纳 trait 用于枚举固定的一组可能性。对 auto traits我们枚举的是从给定起点可达的类型集合Foo可达OptionBoxFoo进而可达BoxFoo、Foo循环闭合。除 auto traits 外WellFormed谓词也是余归纳的用于达成类似的枚举所有情形模式参见 implied bounds 章节的说明。Canonical 查询rustc 与交互式 Prolog的差异Canonical queries 与 Canonicalization 两章解释了 trait 系统的入口canonical query。传统 Prolog 的交互式查询传统 Prolog 系统会枚举所有可能答案。给出查询?- Veci32: AsRef?U求解器可能回答Veci32: AsRef[i32]问 continue? (y/n)按y可能得到下一个答案Veci32: AsRefVeci32来自反射 implimplT AsRefT for T再按y可能得到no。有些查询答案无穷多——比如?- Vec?U: Clone会不断给出Veci32: Clone、VecBoxi32: Clone、VecBoxBoxi32: Clone……直到内存耗尽。rustc 的 trait 查询寻找无歧义答案rustc 的 trait 查询做法不同它不枚举所有答案而是寻找**无歧义unambiguous**的答案。当它给出某个类型变量的值时意味着在当前 impl 与 where 子句集合下这是唯一可证的实例化。trait 查询的响应通常是ResultQueryResultT, NoSolutionErr(NoSolution)查询为假、无任何答案如Boxi32: Copy。Ok(QueryResult)包含四部分信息Certainty确定性Proven已知为真如Veci32: Clone、Rc?T: Clone或Ambiguous尚无法判定真假通常因为缺少更多类型信息如Vec?T: Clone。Var values变量值原查询中每个未绑定推理变量的取值Prolog 中需要靠反解得到rustc 直接给出替换。Region constraints区域约束输入生命周期之间必须成立的关系。Value类型T的附加值对某些专门查询如关联类型规范化用来携带额外结果通常只是()。示例Borrow trait 的两个查询考虑Borrowtrait 的两个 impl显式写出Sized边界以便说明implT BorrowT for T where T: ?Sized implT Borrow[T] for VecT where T: Sized例 1——类型检查fn fooA, B(a: A, vec_b: OptionB) where A: BorrowB { } fn main() { let mut t: Vec_ vec![]; // Type: Vec?T let mut u: Option_ None; // Type: Option?U foo(t, u); // 要求 Vec?T: Borrow?U ... }Vec?T: Borrow?U存在多个解?U Vec?T、?U [?T]、?T u32, ?U [u32]……因此返回Certainty:Ambiguous——尚不能确定是否成立Var values:[?T ?T, ?U ?U]——没学到任何变量取值。类型检查中这不是立即报错检查器会扣住这条义务Vec?T: Borrow?U等待若?T、?U后来被其他来源约束就再次发起查询。例 2——给u赋值fn fooA, B(a: A, vec_b: OptionB) where A: BorrowB { } fn main() { let mut t: Vec_ vec![]; // Type: Vec?T let mut u: Option_ None; // Type: Option?U foo(t, u); // Vec?T: Borrow?U ambiguous u Some(vec![]); // ?U Vec?V }赋值迫使?U与Vec?V统一。类型检查器回头处理之前扣住的义务Vec?T: Borrow?U此时?U已有值查询刷新为Vec?T: BorrowVec?V这次只有一个适用 impl反射 implimplT BorrowT for T where T: ?Sized于是回答Certainty:ProvenVar values:[?T ?T, ?V ?T]——义务成立且?T与?V是同一类型但还不知道具体是什么类型。事实上函数到此结束类型检查器会报错t与u的元素类型虽已互相绑定但依然未知。Canonicalization把推理变量与其环境隔离Canonicalization 是实现 canonical queries 的关键把推理值与其上下文隔离。概念非常简单每个推理变量要么未绑定还不知道类型要么绑定已知。要隔离一个含有类型/区域的数据结构T只需遍历其中出现的未绑定变量把它们替换成从零编号、固定顺序的canonical variablescanonical 占位符。例如类型X (?T, ?U)?T、?U是互不相同的未绑定推理变量其 canonical 形式是(?0, ?1)Y (?U, ?T)也规范化为(?0, ?1)但Z (?T, ?T)规范化为(?0, ?0)。推理变量的确切身份不重要——除非它被重复使用。这既改善缓存也能在 trait 解析中检测循环两个 trait 查询若有相同的 canonical 形式就会得到相同答案答案以 canonical 变量表达再映射回原变量。完整的 canonical 查询流程1. Canonicalize 查询。求解?A: Foostatic, ?B?A、?B未绑定。trait 系统通常忽略生命周期、平等对待因此 canonicalize 时也会把自由生命周期替换为 canonical 变量注意static在这里是自由生命周期——我们只在该 trait 引用的语境中考虑它而不是整个程序的 typing context。结果是?0: Foo?1, ?2也写作forT,L,T { ?0: Foo?1, ?2 }其中T表示类型变量、L表示生命周期变量。canonicalize方法同时返回CanonicalVarValues数组 OV记录各 canonical 变量的原始值[?A, static, ?B]这个 OV 在处理查询响应时需要用到。2. 执行查询。构造好 canonical 查询后创建全新推理上下文用替换 S 实例化 canonical 查询——为每个 canonical 变量分配一个合适 kind 的全新推理变量。对示例查询S 可能是S [?A, ?B, ?C]替换后得到完全实例化的查询?A: Foo?B, ?C。求解器求解它得到Proven/Ambiguous的确定性值并对新建的推理变量产生副作用。例如若只有唯一 implimpla, X Fooa, X for VecX where X: a { ... }则会新建?D、?E并统一?B ?D、?A Vec?E、?C ?E同时积累区域约束?E: ?D。最后要提升这些值出查询的推理上下文——做法是对查询结果再次 canonicalize。3. Canonicalize 查询结果。复用替换 S在求解后刷新它S [Vec?E, ?D, ?E]这些正是原查询三个输入变量的新值但混入了?E这类新变量。再次 canonicalize 整个查询响应 QR 让它们消失QR { certainty: Proven, var_values: [Vec?E, ?D, ?E] region_constraints: [?E: ?D], value: (), }结果为Canonical(QR) forT, L { certainty: Proven, var_values: [Vec?0, ?1, ?0] region_constraints: [?0: ?1], value: (), }微妙之处canonicalize 查询结果时自由生命周期不做特殊处理——两处?D被转换成同一个 canonical 变量?1这与原查询每个自由生命周期都变成全新 canonical 变量形成对比。4. 处理 canonical 结果。把结果应用回原始上下文概念上分三步——(a) 用全新推理变量实例化结果中的每个 canonical 变量(b) 将结果值与原值统一?A与Vec?C、static与?D、?B与?C(c) 记录区域约束?C: static供稍后验证。rustc 实际做的是该过程的轻度优化变体不急于实例化全部 canonical 值而是遍历值向量遇到值恰好是 canonical 变量的情形直接反解如values[2]是?C就推导?C : ?B、?D : static拿不到值的部分才创建推理变量。在 rustc 中的落地rustc_traits 查询 providerChalk 的规则被实现进 rustc 后直接的表现是 compiler/rustc_traits crate——从源码结构看它是一个独立的查询 provider 集合承载与主求解器代码无关的查询。其 lib.rs 将各模块的 provider 注册进Providersdropck_outlivesdrop check 相关的 outlives 查询evaluate_obligation义务求值implied_outlives_bounds隐含的 outlives 边界normalize_projection_ty投影类型规范化normalize_erasing_regions擦除区域后的规范化type_op类型操作查询另有codegen_select_candidate代码生成阶段的候选选择与coroutine_hidden_types协程隐藏类型。以 implied_outlives_bounds.rs 为典型示例该文件头注释明确指出不要直接调用此查询参见rustc_trait_selection::traits::implied_outlives_bounds其实现通过enter_canonical_trait_query进入 canonical trait 查询框架把ParamEnvAnd { param_env, value: ImpliedOutlivesBounds { ty } }交给query_compute_implied_outlives_bounds计算最终返回CanonicalQueryResponseVecOutlivesBound。这正体现了本章所述的 canonical 查询模式在真实 rustc 查询系统中的运用输入被 canonicalize输出是 canonical 化的QueryResponse。配套机制implied boundsImplied bounds 章节解释了与求解器配套的隐含边界机制——fn fooa, T(x: a T)可以自由假定T: a成立而不必显式写出。它分两类显式隐含边界由inferred_outlives_of计算见 compiler/rustc_hir_analysis/src/outlives/mod.rs只有 ADT 和 CTA 拥有通过inferred_outlives_crate查询中的不动点算法计算insert_required_clauses_to_be_wf处理所有 ADT 字段insert_outlives_clause分解 outlives 子句且不会添加static要求。隐式隐含边界由于尚不能在 binder 中处理蕴含这些边界不会加入受影响的ParamEnv而是在词法区域解析OutlivesEnvironment::from_normalized_bounds与 MIR borrowckUniversalRegionRelationsBuilder::add_implied_bounds中单独添加其假设约束由implied_outlives_bounds查询从wf::obligations中直接提取。证明侧则通过发出WellFormed谓词来保证所有使用类型良构——但由于实例化 impl 时不能发出WellFormed谓词否则引发求解器循环且缺少高阶区域 binder 的隐含边界目前存在若干已知 soundness 缺口如 [#25860]、[#84591]、[#100051] 所描述的通过子类型、超 trait 向上转换、投影规范化等路径。配套机制缓存Trait 选择结果会缓存但过程复杂即使 trait 引用中的类型未完全已知也希望可缓存此时 trait 选择会同时影响类型变量因此缓存的不只是结果还要能重放其对类型变量的副作用。大致思路详见 Caching先把所有未绑定推理变量替换为占位符usize : Foo$t→usize : Foo$0再查缓存命中则取下一步动作如应用 impl #22未命中则从头走选择流程并记录缓存项。微妙之处在于结果会随作用域内 where 子句变化因此存在本地缓存挂在ParamEnv上与全局缓存挂在tcx上两个缓存决定用哪个缓存的规则非常保守只要作用域里有任何 where 子句就用本地缓存历史上更细粒度区分导致过 #22019、#18290 之类的诡异 bug。文档记载该简单规则在编译 rustc 自身时命中率约 95%注意rustc-dev-guide 亦标注pick_candidate_cache在新版本中可能已不存在本节更多是理解缓存设计的历史与原则。与旧式求解器的关系Traits 章节目录 明确指出resolution.md描述的是当前默认求解器的工作方式而 chalk 章节描述的是正在设计中的新式求解器。二者在术语上也有对照旧式求解器讲 selection选择、fulfillment履行、evaluation求值三大件其中 selection 又分为candidate assembly候选装配与confirmation确认两个阶段通过 winnowing利用 where 子句与条件剔除候选解决多候选歧义而 Chalk 路线则把同一套问题重新表述为 goal/clause 的证明搜索。可以说Chalk 的目标不是推翻 trait 系统要回答的问题而是为这些问题提供一套更接近逻辑编程、表达能力更强的求解框架以便实现 GATs、specialization 等对旧算法而言硬骨头级别的特性。小结与进一步阅读Chalk-based trait solving 的完整图景可以概括为四层思想层trait 系统 ≈ 逻辑trait/impl 可降低为 Horn 子句泛型函数需要 FOHHforallif形式层Goal/Clause 递归元结构 七类 DomainGoalImplemented、ProjectionEq、Normalize、FromEnv×2、WellFormed×2、Outlives×2 余归纳目标auto traits、WellFormed机制层canonical query——canonicalize 查询 → 实例化求解 → canonicalize 结果 → 回填原上下文配合 implied bounds 与双层缓存实现层compiler/rustc_traits 以 canonical trait 查询框架落地各 provider如implied_outlives_bounds。感兴趣的读者可继续深入 rustc-dev-guide 的 traits 目录 下的其余章节lowering-to-logic、goals-and-clauses、canonical-queries、canonicalization、implied-bounds、caching、resolution或直接阅读 compiler/rustc_traits 与 rustc_trait_selection 的源码观察这些逻辑规则如何被编译进 rustc 并支撑日常的类型检查。【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考