rustc 变型（Variance）推断全解：类型与生命周期参数在编译器内部的协变/逆变推导

rustc 变型Variance推断全解类型与生命周期参数在编译器内部的协变/逆变推导【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust变型variance描述的是泛型类型的子类型行为当泛型参数A与B存在子类型关系时TA与TB之间是否也存在子类型关系。本篇文章以 rustc-dev-guide 的 variance 章节 为核心骨架深入讲解 rustc 在类型检查阶段如何推断类型与生命周期参数的变型包括约束生成、格lattice上的不动点求解、依赖图管理以及 trait 对象、vtable 解析和关联类型等历史与边界问题并逐段对照本仓库中 rustc 的真实源码实现compiler/rustc_hir_analysis/src/variance/目录。读完本文你将掌握 rustc 变型推断的完整算法流程、其与 PLDI11 论文的对应关系以及如何用-Z调试属性直接观察任意类型的推断结果。什么是变型Variance在类型检查期间rustc 必须推断类型参数和生命周期参数的变型。变型回答这样一个问题给定Ta/TA当a/A之间具有子类型关系时T的整体是否也相应地具有子类型关系。在 rustc 内部变型被建模为ty::Variance枚举定义于 compiler/rustc_type_ir/src/lib.rspub enum Variance { Covariant, // TA : TB iff A : B -- 如函数返回类型位置 Invariant, // TA : TB iff A B -- 如 mut T 位置 Contravariant, // TA : TB iff B : A -- 如函数参数类型位置 Bivariant, // TA : TB -- 如未使用的类型参数 }本文沿用 rustc-dev-guide 与 PLDI11 论文的记法表示协变covarianceTA : TB当且仅当A : B-表示逆变contravarianceTA : TB当且仅当B : A*表示双变bivariance无论参数关系如何TA与TB总是可以互相替换o表示不变invariance只有当A B时TA与TB才等价。关于变型的一般性背景知识子类型、控制流图等编译器基础术语可参见 rustc-dev-guide 背景知识附录。需要强调的是rustc 的变型推断只考虑类型的定义为了确定定义在类型X上的类型参数的变型编译器只考察X的定义以及它所引用的其他类型的定义而刻意不分析这些类型在代码中的具体使用。这一点在源码中有直接体现——约束收集阶段遍历的是 HIR 中的条目定义tcx.hir_crate_items而非调用点。推断范围哪些条目参与变型推断变型推断只针对**数据结构data types**上的类型参数即 struct、enum、union。对于这些类型变型的含义非常直观它定义了TA是否是TB的子类型对生命周期参数则是Ta与Tb。而以下条目不参与变型推断trait 上的类型参数trait 参数上的变型在语义上确实存在rustc 早期曾经计算过但其含义相当微妙且实践中收益有限因此已被移除。详见本文末尾的附录。函数 / impl 上的类型参数这些参数被实例化后即被遗忘不会持久存在于类型或编译产物中因此讨论其变型没有意义。对应实现位于 compiler/rustc_hir_analysis/src/variance/mod.rs 的variances_of查询中它根据def_kind分发仅对Fn、AssocFn、Enum、Struct、Union、Ctor以及关联类型/不透明类型RPIT计算变型其余条目直接返回空结果。同样的过滤逻辑也出现在约束生成阶段 constraints.rs只有DefKind::Struct | DefKind::Union | DefKind::Enum含枚举的构造函数与DefKind::Fn | DefKind::AssocFn会构建约束其余条目一概跳过。算法总览约束累积 格上的不动点rustc 的变型推断算法取自 PLDI11 论文《Taming the Wildcards: Combining Definition- and Use-Site Variance》Altidor 等人著本文将其称为 The Paper。基本思路非常直接遍历所有被推断的类型定义对类型参数X的每一次使用累积一条约束表示X的变型必须对该使用位置的变型合法迭代地细化refine每个X的变型直到所有约束都被满足。解一定存在在最坏情况下可以把所有类型参数都声明为不变invariant此时所有约束自然成立。以文档中的经典示例为例enum OptionA { Some(A), None } enum OptionalFnB { Some(|B|), None } enum OptionalMapC { Some(|C| - C), None }将生成如下约束1. V(A) 2. V(B) - 3. V(C) 4. V(C) -含义分别是(1)A的变型至多协变(2)B的变型至多逆变(3)(4)C的变型必须同时至多协变且至多逆变。这些约束的合并基于一个变型格variance lattice* Top (bivariant) - o Bottom (invariant)在这个格上最优解为V(A)、V(B)-、V(C)o。注意全不变永远是一个朴素可行解而固定点求解的目标是在保证约束满足的前提下尽量靠近格的顶部双变。为什么需要不动点迭代你可能好奇为何不能简单地一趟遍历直接求出答案原因是一个使用位置的变型本身可能是其他类型参数变型的函数。在完整的一般性情形下约束的形式为V(X) Term Term : | - | * | o | V(X) | Term x Term这里V(X)表示类型/区域参数X相对于其定义类的变型Term x Term即论文中定义的变型变换variance transform如果类型变量X在类型表达式E中的变型是V2而类C的对应类型参数的定义点变型是V1那么X在类型表达式CE中的变型是V3 V1.xform(V2)。因此当C自身的变型还没确定时E中参数的真实变型就是未决的只能先记录一个符号化的变换项等外层变型确定后再代入求解——这正是固定点迭代存在的根本原因。rustc 中xform的实现位于 compiler/rustc_type_ir/src/lib.rs其行为完全对应论文 Figure 1pub fn xform(self, v: Variance) - Variance { match (self, v) { // 第 1 列协变上下文 (Variance::Covariant, Variance::Covariant) Variance::Covariant, (Variance::Covariant, Variance::Contravariant) Variance::Contravariant, (Variance::Covariant, Variance::Invariant) Variance::Invariant, (Variance::Covariant, Variance::Bivariant) Variance::Bivariant, // 第 2 列逆变上下文 (Variance::Contravariant, Variance::Covariant) Variance::Contravariant, (Variance::Contravariant, Variance::Contravariant) Variance::Covariant, (Variance::Contravariant, Variance::Invariant) Variance::Invariant, (Variance::Contravariant, Variance::Bivariant) Variance::Bivariant, // 第 3 列不变上下文吸收一切 (Variance::Invariant, _) Variance::Invariant, // 第 4 列双变上下文保持一切 (Variance::Bivariant, _) Variance::Bivariant, } }源码注释中还给出了两个直观示例在*mut Veci32中环境变型从协变开始*mut T对T不变于是Veci32以Covariant.xform(Invariant) Invariant出现而VecT对T协变故i32的变型是Invariant.xform(Covariant) Invariant。对于fn(*const Veci32, *mut Veci32)函数类型对参数逆变于是指针参数以Covariant.xform(Contravariant) Contravariant出现再经*const T的协变得到Contravariant.xform(Covariant) Contravariant而*mut分支则是Contravariant.xform(Invariant) Invariant。约束生成一次遍历整 crate约束的收集由 constraints.rs 中的add_constraints_from_crate完成L49-L87它遍历tcx.hir_crate_items(())的全部定义对 struct/union/enum含每个变体的构造函数以及函数/关联函数调用build_constraints_for_item。build_constraints_for_itemL94-L141对 ADT 的每个字段以协变环境递归收集约束对函数则遍历其签名。其中有一句被注释掉的关键代码// Not entirely obvious: constraints on structs/enums do not // affect the variance of their type parameters. See discussion // in comment at top of module. // // self.add_constraints_from_generics(generics);这对应文档中where 子句不影响变型的重要结论见下一节。各类型位置的约束规则add_constraints_from_tyL208-L325是约束生成的核心分发函数rustc 为每一类类型位置定义了明确的规则叶子类型bool、char、整数、浮点、str、!、外部类型不产生任何约束引用a T生命周期a与T均以当前环境变型传播若T是mut则走add_constraints_from_mt强制变为不变L471-L487Mutability::Mut→invariant(variance)即mut T中的T不变Mutability::Not→ 原样传播即T协变数组 / 切片 / 元组逐元素传播当前变型数组长度作为 const 参数处理ADTstruct/enumadd_constraints_from_argsL349-L398对每个泛型实参计算variance_decl并做xform若该 ADT 定义在当前 crate其参数变型尚未推断使用符号化的InferredTerm对应语法中的V(X)若来自其他 crate直接查表取该参数的已推断变型常量项生命周期参数按variance_i传播见add_constraints_from_regionconst 参数则始终以不变处理函数指针fn(...) - ...add_constraints_from_sigL420-L431对每个入参做contravariant(variance)对返回类型以原variance传播——这就是函数类型的逆变规则dyn Trait... a对生命周期a协变传播trait 的主参数principal args按add_constraints_from_invariant_args一律不变处理因为 trait 引用始终不变注释Trait are always invariant投影边界projection bounds的 term 也强制不变投影/不透明类型Projection、Inherent、Opaque实参一律按不变处理这正对应文档附录中关联类型使输入全部不变的规则类型参数ty::Param这是约束的落点——add_constraint把参数index必须满足环境变型variance这条约束记录下来。生命周期与 const 参数的特殊处理add_constraints_from_regionL435-L467只对早期参数ReEarlyParam即定义处的生命周期形参产生约束static与高阶绑定区域ReBound不产生约束——因为高层级区域要么是 HRTB 内部、要么是函数晚绑定参数二者都不参与变型推断。const 泛型参数在求解阶段被强制为不变solve.rs中的enforce_const_invarianceL94-L108会递归地把当前与所有父级泛型列表中的 const 参数设为Invariant。where 子句为何不影响变型考虑带 where 子句的泛型定义struct FooT: Bar { ... }一个自然的问题是T相对于Bar的变型是否会影响T相对于Foo的变型rustc 的答案是不会。理由如下假设T相对于Bar不变、相对于Foo协变且存在一个FooX向上转型为FooY其中X : Y。此时虽然X: Bar成立Y: Bar却未必成立——于是这次上转型不合法但失败原因不是变型不匹配而是目标类型FooY本身不成型not well-formed。变型检查时编译器默认所有涉及类型都已经满足成型性well-formedness因此 where 子句的约束被预先吸收不再进入变型方程。这也正是源码中struct/enum 的 where 子句不构建约束一行注释背后的完整论证。求解格上取 GLB 的不动点迭代求解阶段位于 solve.rs初始化L43-L61所有 inferred 初始化为Bivariant格顶最宽松随后用硬编码的 lang items 覆盖。lang items 硬编码terms.rs的lang_itemsL109-L123为少数内置类型直接指定变型PhantomDataT→ 协变vec![ty::Covariant]UnsafeCellT→ 不变vec![ty::Invariant]CovariantUnsafeCellTrustc 内部实验类型→ 协变。 这是mut T之所以不变、CellT之所以不变的底层原因——一切可变性都收敛到UnsafeCell的不变性上。迭代求解L64-L92反复扫描所有约束对每个 inferred 计算new_value glb(variance, old_value)取格上的最大下界直到一轮遍历没有任何变化固定点。注释明确指出迭代次数上界为2CC为约束数每个变量最多改变两次例如先协变后被迫降到不变而约束数与输入规模线性相关因此整个推断过程也是线性时间的。glb函数L16-L34实现了格的合并fn glb(v1: ty::Variance, v2: ty::Variance) - ty::Variance { // * // - // o match (v1, v2) { (ty::Invariant, _) | (_, ty::Invariant) ty::Invariant, (ty::Covariant, ty::Contravariant) ty::Invariant, (ty::Contravariant, ty::Covariant) ty::Invariant, (ty::Covariant, ty::Covariant) ty::Covariant, (ty::Contravariant, ty::Contravariant) ty::Contravariant, (x, ty::Bivariant) | (ty::Bivariant, x) x, } }可见协变 ∧ 逆变 不变任意 ∧ 不变 不变x ∧ 双变 x——这正是格结构的直接编码。OptionalMapC中C同时出现在参数逆变和返回协变位置glb(, -) o最终得到不变。回写结果create_mapL110-L138按inferred_starts记录的连续区间把每个条目的解切分出来存入CrateVariancesMap。这里还有两条收尾规则const 参数全部强制不变见上文函数允许未使用的泛型参数对函数ty::FnDef若某参数解为Bivariant完全未被使用则强制改为Invariant避免出现既没用又双变的奇怪语义。依赖图管理crate_variances 与 variances_of 双查询由于变型推断是整 crate 级的推断如果不加控制其依赖图会变得非常混乱。rustc 的解决办法是将其重构为两个查询querycrate_variances计算当前 crate 中所有条目的变型。对应 mod.rs 第 30-35 行 的实现完整走完三阶段流水线pub(super) fn crate_variances(tcx: TyCtxt_, (): ()) - CrateVariancesMap_ { let arena DroplessArena::default(); let terms_cx terms::determine_parameters_to_be_inferred(tcx, arena); let constraints_cx constraints::add_constraints_from_crate(terms_cx); solve::solve_constraints(constraints_cx) }即① 确定需要推断的参数集合determine_parameters_to_be_inferred见 terms.rs L66-L107它为每个条目的每个泛型参数分配连续递增的InferredIndex并分配符号项② 从整个 crate 收集约束③ 求解并写入结果。variances_of按条目读取单个条目的变型mod.rs L37-L88。它先跳过无泛型条目然后按def_kind分发普通 ADT/函数直接查crate_variances的结果表关联类型与不透明类型RPIT则走专门的variance_of_opaque逻辑。如果你的代码只读取variances_of那么它的依赖就仅限于该特定条目的推断结果。这个设计最终依赖于 增量编译的红-绿算法red-green algorithm每个变型查询实际都间接依赖整个 crate 的所有类型定义经由crate_variances但由于大多数改动不会改变变型推断的真实结果variances_of在重求值后依然会被判为绿色即结果未变、下游无需重算从而把整 crate 推断的依赖代价控制在可接受的范围内。不透明类型RPIT的变型variance_of_opaquemod.rs L97-L226为impl Trait返回类型RPIT单独计算变型规则与 ADT 不同默认情况下RPIT 对类型与 const 泛型不变对生命周期泛型双变注释By default, RPIT are invariant wrt type and const generics, but they are bivariant wrt lifetime generics父级泛型中的生命周期默认标记为未使用双变随后在遍历显式 item 边界时如果某个生命周期真的出现在隐藏类型中则被改写为不变遍历不透明类型的 trait 约束、投影约束与 outlives 约束时会跳过外层不透明类型自身的实参避免自引用误伤但嵌套在内部的递归出现如type Fooa impl PartialEqFooa;仍会被正确收集。调试与验证dump 变型结果rustc 提供了调试属性#[rustc_dump_variances]对应实现位于 dump.rs。对标注了该属性的 struct/enum/union/函数编译器会在诊断中输出形如[T: , a: o, ...]的变型列表另有#[rustc_dump_variances_of_opaques]用于 dump 所有不透明类型的变型。格式逻辑见format_variancesdump.rs L8-L24它把variances_of的结果与恒等泛型实参一一对应打印出来。这是验证我的类型参数到底被推断成什么变型最直接的实验手段读者可以用自举构建的 rustc 对任意小 crate 做实测。附录trait 上的变型历史回顾如前所述rustc 曾经允许 trait 上的变型它根据 trait 类型参数在方法签名中的出现位置计算变型用于表示 trait 对象 vtable 的兼容性以及 trait 边界中虚拟字典的兼容性。移除它的原因包括关联类型的变型语义很不直观——它们可以被投影出来并用于无数种位置很难判断何时允许XA::Bar发生变化甚至很难说清楚那意味着什么更关键的是任何含关联类型的 trait其所有输入都必须不变见下文严重限制了适用面为确保所有 trait 类型参数都有变型而引入的注解MarkerTrait、PhantomFn令人困惑且收益甚微。下面按文档原文保留历史细节说明当时如何解释 trait 变型。变型与对象类型与 struct/enum 类似可以依据A与B的关系来决定两个对象类型TraitA与TraitB的子类型关系。注意对象类型中的Self类型参数被忽略——它是未知的而动态分发保证了被调用的函数总是期望正确的Self类型。但其余类型参数必须谨慎处理否则可能调用到期望一种类型、实际传入另一种的函数。考虑如下 traittrait ConvertToA { fn convertTo(self) - A; }直观上若有两个对象O ConvertToObject与S ConvertToString则S : O因为String : Object。实际算法是逐对比较显式类型参数并遵守各自的变型这里的A只出现在返回位置是协变的因此要求String : Object。之所以可以忽略隐式的Self参数是因为直到调用发生时我们才需要知道它的值而虚拟分发的动态性保证了无论Self绑定为何值被调用的代码都正确。Self因此不同于A调用者必须事先知道A才能确定convertTo()的返回类型。顺带一提rustc 有规则禁止通过对象调用那些Self出现在接收者位置之外的方法。trait 变型与 vtable 解析trait 不仅用于对象也用于判断某个 impl 是否满足某个 trait 边界。设想如下函数与实现fn convertAllA,T:ConvertToA(v: [T]) { ... } impl ConvertToi32 for Object { ... }现在想在字符串数组上调用convertAll并显式指定T Stringlet mut vector vec![string, ...]; convertAll::i32, String(vector);这合法吗换言之能把为Object写的 impl 套用到String上吗答案是可以展开执行过程即可看出convertAll会创建一个指向 vector 元素的指针类型为String随后调用为对象准备的convertTo()实现其类型为fn(self: Object) - i32为self提供String值之所以合法是因为String : Object。回到变型视角问题为Object,i32写的 impl 能否用于期望String,i32的位置可以用字典传递dictionary-passing风格的实现来表述。此时convertAll()接受一个代表 impl 的隐式参数我们拥有的 impl 类型是V_O ConvertToi32 for Object函数原型期望的 impl 类型是V_S ConvertToi32 for String。与普通参数一样只要V_O是V_S的子类型即合法。由于Self参数逆变、A协变可得V_O : V_S iff i32 : i32 String : Object两个条件均满足故合法。变型与关联类型含关联类型或至少含投影表达式的 trait必须对其所有输入保持不变。从子类型的角度看trait 引用之间的子类型T as Trait : U as Trait意味着若已知T as Trait则也已知U as Trait用字典传递的观点看就是T as Trait的字典可以安全地用在期望U as Trait字典的地方。问题在于一旦可以从T as Trait投影出类型这些投影类型与U as Trait投影出的类型之间的关系就完全未知除非T U。使Trait不变恰好保证了这一点。另一个相关原因是如果不让含关联类型的 trait 不变投影就不再是单结果的函数了。考虑trait Identity { type Out; fn foo(self); } implT Identity for T { type Out T; ... }此时static () as Identity::Out可以合法地推出为任意a ()a () as Identity : static () as Identity if static () : a () -- Identity 在 Self 上逆变 if static : a -- 区域子类型规则而强制不变之后static () as Identity::Out恒为static ()若需要更短的a可另行上转型。这一改动曾用于解决相关的旧问题。小结从定义到查询的完整链路rustc 的变型推断是一条清晰的三段式流水线全部收敛在compiler/rustc_hir_analysis/src/variance/目录terms 阶段terms.rs遍历 crate为每个参与推断的条目分配连续编号的推断变量并注册PhantomData/UnsafeCell等硬编码变型constraints 阶段constraints.rs按类型结构的各位置累积形如V(X) Term的约束其中Term由常量、推断变量与TransformTerm即xform构成solve 阶段solve.rs在变型格上迭代取 GLB 直至固定点回写CrateVariancesMap并对 const 参数、函数未用参数做收尾修正。对外暴露的是crate_variances与variances_of两个查询mod.rs前者一次算完整个 crate后者按条目读取并借助红-绿算法控制增量编译的依赖代价。理解这套机制无论是阅读 rustc 类型检查源码、调试#[rustc_dump_variances]输出还是设计自身语言前端中的子类型系统都能获得一份完整可参照的范本。【免费下载链接】rustEmpowering everyone to build reliable and efficient software.项目地址: https://gitcode.com/GitHub_Trending/ru/rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考