Ruff 类型检查器（ty）的约束集量化（Quantification）：存在与全称量词的实现与基线测试解析

Ruff 类型检查器ty的约束集量化Quantification存在与全称量词的实现与基线测试解析【免费下载链接】ruffAn extremely fast Python linter and code formatter, written in Rust.项目地址: https://gitcode.com/GitHub_Trending/ru/ruff导读本文围绕仓库中 crates/ty_python_semantic/resources/mdtest/type_properties/quantification.md 这一技术文档展开深入讲解 Ruff 项目中新一代类型检查器 ty 的**约束集量化quantification**机制如何从约束集中消去类型变量typevar得到只引用剩余类型变量的等价约束集以及存在量化∃与全称量化∀在语义上的根本区别。通过通读 7 组基线测试用例C0、E1E6你可以掌握ConstraintSet.exists/ConstraintSet.for_all的调用方式、量词消去在可满足性与特化推断中的行为边界并结合 constraints.rs 的 BDD二叉决策图实现理解其底层原理。一、为什么要量化约束集类型变量带来的语义问题在开始读量化文档之前需要先建立约束集这一概念。ty 的类型检查并非对类型变量直接回答可赋值 / 不可赋值而是回答在什么约束下可赋值。这一点在姊妹文档 constraints.md 中有清晰的论述对不含类型变量的具体类型而言可赋值性等属性要么成立、要么不成立一旦引入类型变量同一个属性可能对某些特化成立、对另一些特化不成立因此必须追问在什么约束下成立。ty 使用**析取范式DNF**表达约束集一个约束集是零个或多个子句clause的并集每个子句是零个或多个单条约束的交集。空并集⋃ {} 0不可满足单个空子句⋃ {⋂ {}} 1恒可满足。单条约束包括范围约束rangeConstraintSet.range(lower, T, upper)要求T特化到某个既为下界超类型又为上界子类型的类型上界约束upper_bound省略下界默认Never形如T ≤ B下界约束lower_bound省略上界默认object形如L ≤ T等式约束equalityT V以及基于交、|并、~非组合出的复合约束集。当某个类型变量只在中间推导中使用、不影响最终结果时我们希望在保留其余变量之间约束关系的前提下把它消掉。这一消去过程就是本文的主题——量化quantification。二、量化语义存在量化与全称量化原文档开篇给出了量化的精确定义量化从约束集中移除类型变量返回一个新的等价约束集该约束集只引用剩余的类型变量。在存在量化exists下只要至少存在一个被移除变量的有效赋值使被量化表达式成立结果即成立在全称量化for_all下只有每一个有效赋值都使表达式成立结果才成立。二者在源码中是明确的对偶关系。constraints.rs 中for_all的实现直接复用了存在抽象并交替取反// 来自 crates/ty_python_semantic/src/types/constraints.rs#L911-L928 pub(crate) fn for_all(self, db, env, builder, to_remove) - Self { if to_remove TypeVarSet::None { return self; } // Universal and existential quantification are duals. self.negate(db, builder) .reduce_inferable(db, env, builder, to_remove) .negate(db, builder) }也就是说∀X. φ等价于¬(∃X. ¬φ)。这种实现方式让for_all直接复用存在量词消去那条经过缓存、单遍完成的实现路径reduce_inferable保持了 BDD 操作的一致性。reduce_inferable的文档注释constraints.rs也印证了这一点被抽象掉的类型变量将从约束集中移除只要原先存在这些变量的任一特化使约束集成立结果就成立。原文档随后用一个表格概括了全部基线用例这是整篇文档的地图CaseFormulaExpected resultC0∃X. X int ∧ A ≤ Invariant[X]Equivalent toA ≤ Invariant[int]E1∃X. U ≤ X ∧ X VEquivalent toU ≤ VE2∃X. A ≤ Invariant[X] ∧ X ≤ BAandBmust admit a commonXE3∃X. A ≤ X ∧ Invariant[X] ≤ BAandBmust admit a commonXE4∃X. C₁(X, Y) ∧ C₂(X, Z)Solutions forYandZremain correlatedE5∃X ∈ {int, str}. C(X, Y, Z)Solutions remain paired with each choiceE6∀Y ∈ Dᵧ. ∃X ∈ Dₓ. R(X, Y)Xmay depend on the choice ofY每个用例都以一段可运行的 Python 代码呈现并配有一段[environment]TOML 前置声明如python-version 3.13说明这些文档同时是 ty_python_semantic 的 mdtest 集成测试用例文档即测试测试即文档。三、测试骨架与配套 API读懂用例代码的前提所有用例共享同一套脚手架例如 C0from ty_extensions import static_assert from ty_extensions._internal import ConstraintSet class Invariant[T]: def get(self) - T: raise NotImplementedError def set(self, value: T) - None: ...这里的Invariant[T]是一个典型的不变容器同时有get/set类型参数既出现在返回位置又出现在入参位置用于构造对X敏感的约束。ConstraintSet各静态方法的语义已在第一节说明static_assert则在编译期断言某个约束集恒真。用例中的reveal_type(body.solutions(inferable...))用于观察给定类型变量集合下所有可满足的特化解solution family。需要特别说明的是代码中的# TODO: revealed: .../# revealed: ...双行注释从注释结构可以推断TODO行代表实现尚未达成的期望输出文档作者对最终正确行为的标注紧随其后的revealed:行则是当前实现的实际输出。读这些用例时二者对照能直观看出 ty 对量词消去支持的成熟度——部分用例如 C0、E1、E4已经实现到与期望一致而另一些如 E2、E3、E5、E6仍标注TODO属于正在完善中的能力。这与源码中ConstraintSetBuilder及相关缓存的存在性相符——BDD 结构constraints.rs依赖 interning 与记忆化memoization保证正确性与效率量化这类敏感操作仍在持续演进。四、基线用例逐个解析C0grounded invariant确定化的不变约束公式∃X. X int ∧ A ≤ Invariant[X]X的所有赋值都有效满足隐式上界object但唯一满足表达式的赋值是X int。因此消去X后结果应当等价于A ≤ Invariant[int]。def grounded[X, A]() - None: # ∃X. X int ∧ A ≤ Invariant[X] body ConstraintSet.equality(X, int) ConstraintSet.upper_bound(A, Invariant[X]) quantified body.exists(tuple[X]) # TODO: revealed: tuple[Solution[Xint, Alist[int]]] # revealed: tuple[Solution[Xint, AInvariant[int] Invariant[Xgrounded]]] reveal_type(body.solutions(inferabletuple[X, A])) # TODO: revealed: tuple[Solution[Alist[int]]] # revealed: tuple[Solution[AInvariant[int]]] reveal_type(quantified.solutions(inferabletuple[A])) # A ≤ Invariant[int] expected ConstraintSet.upper_bound(A, Invariant[int]) static_assert(quantified expected) static_assert(~quantified ~expected)要点body.exists(tuple[X])即对X做存在量化static_assert(quantified expected)与static_assert(~quantified ~expected)是一对强等价断言不仅量化结果与手写的期望约束集相等二者的否定也相等。之所以要断言两次是因为 BDD 语义上φ ψ与¬φ ¬ψ并不总能由单次相等断言覆盖涉及取反后的规约路径成对断言能更严格地锁定量词消去的等价性从实际revealed输出可以看到量词消去后A的解从含X的形态规约为Invariant[int]与手写期望一致说明该用例当前实现已通过。E1relational bridge关系桥公式∃X. U ≤ X ∧ X V。若存在某个X同时满足U ≤ X与X V那么X V代入可得U ≤ V——反之亦然。量词消去应当把这条桥压缩成一条直接约束def relational_bridge[X, U, V]() - None: # ∃X. U ≤ X ∧ X V body ConstraintSet.upper_bound(U, X) ConstraintSet.equality(X, V) quantified body.exists(tuple[X]) # TODO: revealed: tuple[Solution[Vobject, Uobject]] # revealed: tuple[Solution[VUrelational_bridge, UVrelational_bridge]] reveal_type(quantified.solutions(inferabletuple[U, V])) # U ≤ V expected ConstraintSet.upper_bound(U, V) static_assert(quantified expected) static_assert(~quantified ~expected)这个用例的价值在于验证传递性闭合U ≤ X与X V两两组合后即使X被消去U与V之间的顺序关系也必须被保留下来实际输出VU...、UV...表明U、V互相成为对方的上/下界证据量化后依然维持U ≤ V的约束形态。E2open invariant inverse image开放不变约束的逆像公式∃X. A ≤ Invariant[X] ∧ X ≤ B某个特化满足该式当且仅当存在一个X同时兼容A与B。文中给出关键反例——A Invariant[str]且B ≤ int无法满足该式因而必须满足其否定def inverse_image[X, A, B]() - None: # ∃X. A ≤ Invariant[X] ∧ X ≤ B body ConstraintSet.upper_bound(A, Invariant[X]) ConstraintSet.upper_bound(X, B) quantified body.exists(tuple[X]) reveal_type(body.solutions(inferabletuple[X, A, B])) reveal_type(quantified.solutions(inferabletuple[A, B])) # Invariant[str] ≤ A ∧ B ≤ int invalid ConstraintSet.lower_bound(Invariant[str], A) ConstraintSet.upper_bound(B, int) reveal_type((body invalid).solutions(inferabletuple[X, A, B])) reveal_type((quantified invalid).solutions(inferabletuple[A, B])) static_assert(not (quantified invalid)) # TODO: no error # error: [static-assert-error] static_assert((~quantified invalid) invalid)要点static_assert(not (quantified invalid))验证反例与量化结果不相容static_assert((~quantified invalid) invalid)验证否定侧的行为反例必须落在¬quantified中即不相容的组合只能满足否定量化式代码中# error: [static-assert-error]与# TODO: no error的组合表示当前实现尚不能正确判定第二个断言会产生静态断言错误属于文档标注的未完成项这一用例与 E3 共同刻画了开放不变约束open invariant的量词消去难度X同时出现在一个上界位置和一个下界位置时消去必须保留存在共同见证者这一语义。E3witness-sensitive image对见证者敏感的正像公式∃X. A ≤ X ∧ Invariant[X] ≤ BX的每个选择都会决定哪些A、B取值能满足该式。A ≥ int与B ≤ Invariant[str]无法满足它因此必须满足其否定def witness_sensitive[X, A, B]() - None: # ∃X. A ≤ X ∧ Invariant[X] ≤ B body ConstraintSet.lower_bound(A, X) ConstraintSet.lower_bound(Invariant[X], B) quantified body.exists(tuple[X]) reveal_type(body.solutions(inferabletuple[X, A, B])) reveal_type(quantified.solutions(inferabletuple[A, B])) # int ≤ A ∧ B ≤ Invariant[str] invalid ConstraintSet.lower_bound(int, A) ConstraintSet.upper_bound(B, Invariant[str]) reveal_type((body invalid).solutions(inferabletuple[X, A, B])) reveal_type((quantified invalid).solutions(inferabletuple[A, B])) static_assert(not (quantified invalid)) # TODO: no error # error: [static-assert-error] static_assert((~quantified invalid) invalid)与 E2 对称E2 中X处于上界位置A ≤ Invariant[X]、X ≤ BE3 中X处于下界位置A ≤ X、Invariant[X] ≤ B。二者共同检验量词消去在X出现于不同极性时的正确性。文档中revealed: tuple[()]表明目前对quantified.solutions还无法直接枚举出消去后的解族返回空只能在加上反例约束后得到特化输出这正是该用例被标记为演进中的原因。E4correlated visible outputs可见输出的相关性保持C₁关联X与YC₂关联X与Z两条约束必须对同一个X同时成立。两个合法的解族是(Y int, Z Invariant[int])与(Y str, Z Invariant[str])交叉配对(Y int, Z Invariant[str])非法def correlated_outputs[X, Y, Z]() - None: # C₁(X, Y) (X int ∧ Y int) ∨ (X str ∧ Y str) c1_int ConstraintSet.equality(X, int) ConstraintSet.equality(Y, int) c1_str ConstraintSet.equality(X, str) ConstraintSet.equality(Y, str) c1 c1_int | c1_str # C₂(X, Z) (Z Invariant[X]) c2 ConstraintSet.equality(Z, Invariant[X]) # ∃X. C₁(X, Y) ∧ C₂(X, Z) body c1 c2 quantified body.exists(tuple[X]) reveal_type(body.solutions(inferabletuple[X, Y, Z])) # revealed: tuple[Solution[Yint, ZInvariant[int]], Solution[Ystr, ZInvariant[str]]] reveal_type(quantified.solutions(inferabletuple[Y, Z])) # (Y int ∧ Z Invariant[int]) ∨ (Y str ∧ Z Invariant[str]) expected_int ConstraintSet.equality(Y, int) ConstraintSet.equality(Z, Invariant[int]) expected_str ConstraintSet.equality(Y, str) ConstraintSet.equality(Z, Invariant[str]) expected expected_int | expected_str static_assert(quantified expected) static_assert(~quantified ~expected) # (Y int ∧ Z Invariant[str]) invalid_cross ConstraintSet.equality(Y, int) ConstraintSet.equality(Z, Invariant[str]) static_assert(not (quantified invalid_cross)) reveal_type((quantified invalid_cross).solutions(inferabletuple[Y, Z]))这是文档中当前实现完全通过的关键用例之一quantified.solutions精确枚举出两个解族且手写期望expected同样是析取形式通过了static_assert(quantified expected)与否定侧的成对断言。它还验证了量词消去最容易被忽略的性质——被消去的共享变量一旦消去剩余变量之间的相关性必须被保留这里体现为Y int必须搭配Z Invariant[int]。交叉配对被static_assert(not (quantified invalid_cross))明确拒绝。E5finite domain有穷声明域X被声明限定为int或str。每个合法选择给出一个独立的解族X被量化后Y与Z必须在每个解族内保持关联且声明域之外的特化必须被拒绝def finite_domain[X: (int, str), Y, Z]() - None: # ∃X ∈ {int, str}. C(X, Y, Z) # C(X, Y, Z) (Y X) ∧ (Z Invariant[X]) body ConstraintSet.equality(Y, X) ConstraintSet.equality(Z, Invariant[X]) quantified body.exists(tuple[X]) reveal_type(body.solutions(inferabletuple[X, Y, Z])) reveal_type(quantified.solutions(inferabletuple[Y, Z])) # (Y int ∧ Z Invariant[int]) ∨ (Y str ∧ Z Invariant[str]) expected_int ConstraintSet.equality(Y, int) ConstraintSet.equality(Z, Invariant[int]) expected_str ConstraintSet.equality(Y, str) ConstraintSet.equality(Z, Invariant[str]) expected expected_int | expected_str # TODO: no error # error: [static-assert-error] static_assert(quantified expected) # TODO: no error # error: [static-assert-error] static_assert(~quantified ~expected) # (Y int ∧ Z Invariant[str]) invalid_cross ConstraintSet.equality(Y, int) ConstraintSet.equality(Z, Invariant[str]) static_assert(not (quantified invalid_cross)) # (Y bytes ∧ Z Invariant[bytes]) invalid_domain ConstraintSet.equality(Y, bytes) ConstraintSet.equality(Z, Invariant[bytes]) static_assert(not (quantified invalid_domain)) reveal_type((quantified invalid_domain).solutions(inferabletuple[Y, Z]))这个用例引入了声明域declared domainX: (int, str)。注意它与 C0 中隐式上界object的区别——声明域给出的是X的有限候选集。当前实现虽然能在枚举层面给出相关性保持的结果revealed: tuple[Solution[ZInvariant[Y...]]]但手写的析取期望expected及其否定侧断言仍标记为TODO尚未完全通过而域外特化Y bytes与交叉配对均已被static_assert(not ...)正确拒绝。此外被标记为# revealed: None的(quantified invalid_domain).solutions注释行表明当前实现对域外特化与量化后约束的交尚不能稳定给出None无解结果。E6alternation and negative polarity量词交替与负极性X、Y都声明为int或str。对每个合法Y都存在匹配的X但反过来交换量词就需要同一个X对所有Y都成立因而为假。对关系取反则等价于是否存在没有匹配X的Y一个只含int的关系可证明缺少str情形会被拒绝def alternation[X: (int, str), Y: (int, str)]() - None: # R(X, Y) (X int ∧ Y int) ∨ (X str ∧ Y str) x_int ConstraintSet.equality(X, int) x_str ConstraintSet.equality(X, str) y_int ConstraintSet.equality(Y, int) y_str ConstraintSet.equality(Y, str) relation (x_int y_int) | (x_str y_str) # ∀Y. ∃X. R(X, Y) forall_y_exists_x relation.exists(tuple[X]).for_all(tuple[Y]) # TODO: no error # error: [static-assert-error] static_assert(forall_y_exists_x) # TODO: no error # error: [static-assert-error] static_assert(not ~forall_y_exists_x) # ∃X. ∀Y. R(X, Y) exists_x_forall_y relation.for_all(tuple[Y]).exists(tuple[X]) static_assert(not exists_x_forall_y) # ∃Y. ∀X. ¬R(X, Y) counterexample (~relation).for_all(tuple[X]).exists(tuple[Y]) # TODO: no error # error: [static-assert-error] static_assert(not counterexample) static_assert(counterexample ~forall_y_exists_x) int_only x_int y_int missing_str int_only.exists(tuple[X]).for_all(tuple[Y]) static_assert(not missing_str)这是文档中唯一同时演示exists与for_all并用的用例也是逻辑信息密度最高的一节∀Y. ∃X. R(X, Y)对每个Y都能找到匹配的X——对Y int取X int对Y str取X str整体为真当前实现仍标记TODO断言暂未通过∃X. ∀Y. R(X, Y)需要单个X同时匹配所有Y由于R只在X Y时成立不存在这样的X恒为假static_assert(not exists_x_forall_y)已通过反例路径∃Y. ∀X. ¬R(X, Y)要找没有匹配X的Y并断言它等价于¬(∀Y. ∃X. R(X, Y))——这正是量词对偶律在约束集层面的一次实战验证对应源码中for_all通过两次negate复用reduce_inferable的实现missing_str把关系裁剪成只含int的int_only则∀Y 都找到匹配X不再成立str情形缺失static_assert(not missing_str)验证了负极性下缺失分支被正确识别。五、底层实现原理BDD 与抽象遍历量词消去在 constraints.rs 中是一条完整的调用链入口existsconstraints.rs先检查TypeVarSet::None快速返回若 BDD 根节点是终结点AlwaysTrue/AlwaysFalse也直接返回随后以(self, bound_typevars, source_order)为键查exists_cache命中则复用结果否则调用exists_inner并将结果写入缓存。缓存机制与 constraints.rs 附近的一系列*_cache一样都建立在ConstraintSetBuilder的 interning 记忆化之上。BDD 层的exists_innerconstraints.rs调用统一的abstract_inner抽象遍历以约束是否提及被量化类型变量作为移除判定mut |storage, constraint| { storage.constraint_mentions_typevars(db, constraint, bound_typevars) }移除的约束仍会加入路径path从而让蕴含推导sequent map能够传播不提及被量化变量的派生约束——这正是 E1 中U ≤ X ∧ X V消去X后仍能推出U ≤ V的机制。通用的abstract_innerconstraints.rs 起以PathVisitor遍历 BDD对每个内部节点用should_remove谓词判定Keep/Remove。Keep时直接保留子树派生事实可之后重新推导Remove时则跨过该约束继续遍历把不依赖被消去变量的分支合并进结果。remove_noninferableconstraints.rs复用同一遍历按可推断inferable类型变量过滤——它还会保留证据界是裸的可推断类型变量的约束因为I ≤ N这类关系在不同 typevar 排序下可能被编码成不同形态只检查被约束变量会导致丢失信息这一细节保证了量化逻辑不依赖类型变量的内部排序。source_order 的处理reduce_inferableconstraints.rs在消去变量后还会重算源序——被消去类型变量涉及的约束必须离开 source-order 历史否则递归关系会在活图稳定后互相重新引入彼此的量化约束剩余条目保持原有顺序并追加派生事实。这就是 E4/E5 中解族顺序能保持稳定、可读的原因。for_all的对偶实现如第二节所述for_allnegate ∘ reduce_inferable ∘ negateconstraints.rs既符合布尔对偶律也让全称量化共享存在量化的单遍缓存实现。从源码结构可以推断整套机制建立在 BDD 结构之上约束集内部是带三值逻辑true / false / uncertain的决策图negate、and、or分别见 constraints.rs、constraints.rs、constraints.rs与量词消去共享同一存储BDD 的 interning 与记忆化保证了量词消去在大规模约束上的可扩展性。这也解释了文档用例中body.exists(...)、body.for_all(...)、/|/~为何能自由组合——它们本质上是同一棵决策图上的高阶运算。六、边界行为与当前实现状态把七个用例合起来看可以勾勒出 ty 量化能力的现状与边界已稳定通过C0grounded invariant 的确定化、E1关系桥的传递闭合、E4可见输出相关性保持含精确解族枚举与交叉配对拒绝语义正确但结果有待完善E2、E3开放不变约束的正/逆像否定侧断言仍报static-assert-error、E5有穷声明域期望的析取形态与否定侧尚未达成、E6量词交替与负极性∀Y.∃X侧仍标记TODO值得注意的实现限制部分用例在revealed输出中表现为空解族tuple[()]或对域外特化给出非None的解说明存在抽象 声明域 不变容器组合下的解枚举仍在演进。因此本文档非常适合作为 ty 类型系统开发与测试的行为规范每一行static_assert都是可验证的语义承诺每一条# TODO: revealed都是尚未兑现的能力清单。七、如何在仓库中继续深入如果你想亲自验证或继续研究这些用例可以按以下路径定位相关文件本文档主体crates/ty_python_semantic/resources/mdtest/type_properties/quantification.md约束集基础概念DNF、range/upper/lower/equality 约束的完整说明与用例crates/ty_python_semantic/resources/mdtest/type_properties/constraints.md同一目录下的其余属性文档如is_assignable_to.md、materialization.md、is_disjoint_from.md等覆盖了其他类型属性的基线测试可对照阅读量化核心实现crates/ty_python_semantic/src/types/constraints.rs重点看for_all约 L911、reduce_inferable约 L732、exists约 L3504与abstract_inner约 L4888以及ConstraintSetBuilder约 L987的缓存与 source-order 处理这些 mdtest 文档由 ty_python_semantic 的集成测试加载执行仓库中crates/ty_python_semantic/tests下的测试入口文档内[environment] python-version 3.13声明了测试运行所需的 Python 版本环境。结语量化是类型系统从约束集合走向类型推断结果的必经之路它把中间引入的类型变量干净地消除同时把剩余变量之间的相关性、声明域与否定行为精确保留下来。本文从 quantification.md 的 7 组基线用例出发结合 constraints.rs 的 BDD 实现梳理了exists与for_all的语义、调用链与当前实现边界。对类型系统实现者而言这些用例是绝佳的量词消去行为规范对 Rust 学习者而言for_all negate ∘ exists ∘ negate这一对偶实现也是以布尔代数驾驭逻辑运算的简洁范例。【免费下载链接】ruffAn extremely fast Python linter and code formatter, written in Rust.项目地址: https://gitcode.com/GitHub_Trending/ru/ruff创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考