Carbon 语言impl选择终止算法以严格超集规则替代递归限制【免费下载链接】carbon-langCarbon Languages main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang本篇技术指南深入解析 Carbon 语言提案 p002687如何为impl声明选择impl selection设计一个可预测、可证明终止的算法以替代传统编译器中递归深度上限的粗暴方案。读完本文你将掌握 Carbon 如何用基本类型计数 严格更复杂判定度量查询复杂度、如何处理整数与choice类型等非类型参数、如何用数学归纳法证明算法必然终止以及该规则在 toolchain/check/impl_lookup.cpp 中的实际落地状态。问题背景递归限制为什么不够好考虑下面这条impl声明interface I; impl forall [T:! type where Optional(.Self) is I] T as I;i32是T的一个合法取值因此i32实现I的前提是Optional(i32)实现I而这条impl声明可能同样被用于给Optional(i32)提供对I的实现——但这又要求Optional(Optional(i32))实现I。如此无穷嵌套下去如果没有约束编译器就会陷入死循环。终止规则termination rule的职责就是在这种情况下直接报告错误而不是被无限循环困住。早期设计沿用了 Rust 与 C 的做法设置一个递归深度上限。但递归限制存在几个系统性缺陷错误发现太迟循环往往要重复很多次之后才会撞到深度上限且上限越大问题暴露得越晚错误信息也随之臃肿难懂。理想的终止规则应当以最小化的方式识别循环——这既能降低编译耗时也能让错误消息尽可能简短、可理解。重构引发假性失败某些原本合法的重构会无意中加深递归深度触发本不该出现的失败而常见的修复方式是调大递归上限这又让前一个问题更严重。违背可预测性目标递归上限的存在使得远处代码的行为是否会改变不可预测这与 Carbon 在 generics 可预测性目标 中的承诺相悖。需要特别说明的是判断一组impl声明是否会终止在一般情形下等价于停机问题是不可判定的。因此任何终止规则都必然存在误报spurious failure——即代码本可正常结束却被判为错误。设计的目标不是消除误报而是让判定准则在实践中真实出现的代码上保持正确。历史脉络从递归限制到本提案第一个终止规则随提案 #920: Generic parameterized impls (details 5) 引入同样借鉴了 Rust 和 C。当时的文档就承认了递归限制的问题只是还没有找到替代方案。此后替代方案经过了多轮公开讨论2022-04-13 的开放讨论由提案 #1088: Generic details 10: interface-implemented requirements 中的一个问题引发issue #2458: Infinite recursion during impl selection 汇总了包括 2023-02-07 在内的多轮讨论结论。PR #2602 曾将该规则在 Carbon 的 Explorer早期解释器实现中落地而本提案PR #2687正式确立了这套算法的设计。该设计随后被写入正式设计文档 docs/design/generics/details.md 的 Termination rule 一节其中以 issue #2880 跟踪已知的、实际代码中本可终止却被误拒的问题。核心提案基本类型计数与严格更复杂判定本提案用一条新规则替换终止准则在重新考虑同一条impl声明时impl查询中的类型绝不能变得严格更复杂。一组类型的复杂度如何度量答案是统计每种基本类型base type出现的次数。基本类型即去掉参数后的类型名。例如查询Pair(Optional(i32), bool) impls AddWith(Optional(i32))中包含的基本类型有PairOptional出现 2 次i32出现 2 次boolAddWith于是严格更复杂的定义是至少一个计数增加且没有任何计数减少。因此Optional(Optional(i32))比Optional(i32)严格更复杂Optional与i32的计数都增加但Optional(Optional(i32))并不比Optional(bool)严格更复杂Optional计数增加但i32计数减少为 0。把每个基本类型计数看作多维空间中的一个点这条规则的本质是在查询序列中复杂度向量只能只增不减地移动一旦出现任何方向的下降就脱离严格更复杂的判定范围。与 acyclic 规则协同一个循环例子这条严格更复杂规则需要与 acyclic 规则查询不能原样重复配合使用两者结合才能证明终止。看回开头的例子interface I; impl forall [T:! type where Optional(.Self) is I] T as I;该impl声明匹配查询i32 impls I的前提是Optional(i32) impls I。而后者是一个严格更复杂的查询——它包含起始查询的全部基本类型i32和I还多了一个Optional。因此一步之后就能给出错误而不是等到撞上很大的递归上限。错误消息还能明确指出问题所在我们从没有Optional的查询走到了有一个Optional的查询且没有任何计数减少。需要强调的是该规则仅在同一条impl声明以严格更复杂的查询被重新考虑时才触发失败。如果因为存在更特化的impl声明、被类型结构重叠规则优先选中从而根本不会考虑第一条声明则不会报错impl forall [T:! type where Optional(.Self) is I] T as I; impl Optional(bool) as I; // OK, because we never consider the first impl // declaration when looking for Optional(bool) impls I. let U:! I bool; // Error: cycle with i32 impls I depending on // Optional(i32) impls I, using the same impl // declaration, as before. let V:! I i32;该规则对重构同样稳健这是设计时明确追求的三大特性不依赖impl声明如何参数化只看查询本身不依赖查询链的长度不依赖类型表达式复杂度如树的深度这类度量。细节一非类型参数的处理基本类型计数只覆盖类型参数对非类型参数non-type arguments必须扩展出额外的键key。这些键与基本类型分属独立的命名空间整型值以整型类型名为键以绝对值为计数。也就是说整型参数的复杂度随绝对值增大而上升。例如2和-3同时作为i32类型参数的取值时i32这个键的计数为5|2| |-3|。choice类型的每个选项每个选项option都是自己的键统计使用该选项的值出现次数选项自带的参数再作为独立键记录。例如值.Some(7)类型为Optional(i32)会被记录为键.Some计数1和键i32计数7。可变参数variadic还有一个独立的键命名空间挂靠在基本类型之下用来统计可变参数的个数。这是为了防御这样的场景可变参数类型V接受任意多个i32参数从而产生无限多个互不相同的实例V(0)、V(0, 0)、V(0, 0, 0)、……其中该命名空间中的tuple键用于统计元组值的分量总数各分量的取值再通过各自的键来追踪。对于未被上述规则覆盖的非类型参数值会从查询中整体删除即不参与终止算法的复杂度判定。这样做的必然结果是两个仅因这类非类型参数而不同的查询会被视为同一查询从而被 acyclic 规则拒绝。否则我们就能构造出无限多个非类型参数值来规避终止判定——这是设计中必须堵住的漏洞。细节二终止性证明一个数学归纳论证本规则能否保证终止需要严谨证明。这里给出原提案的完整论证思路。把一段有限或无限类型表达式序列称为好good的如果没有后一个元素比某个前一个元素严格更复杂且没有任何类型表达式重复出现。要证明的是任何键集合有限的好序列都是有限的。证明的第一步是化简可以只考虑不重复任何键多重集multiset的好序列因为给定一个键多重集最多只能对应有限多个类型——若所有类型都没有可变参数列表那么对基本类型的每一种排列至多对应一个类型若存在可变参数类型则把不同排列数乘以可能的元数arity组合数得到一个保守的有限上界而元数组合数有限是因为忽略非类型参数后总元数必须等于类型中基本类型数减 1。随后用对键的个数N的归纳法完成证明N 1类型映射为单一键的多重集可用该键的出现次数表示。这个数在序列中非负且递减因此序列长度以首元素取值为界必然有限。归纳步假设N个键的好序列有限证明N1个键的也有限首个元素可表示为非负整数(N1)元组(i_0, i_1, ..., i_N)。其后的每个元素必定落在由以下方程给出的某个超平面余维数为 1中x_0 0, x_0 1, ..., x_0 i_0 - 1共i_0个不同的方程每个定义独立超平面x_1 0, x_1 1, ..., x_1 i_1 - 1……x_N 0, x_N 1, ..., x_N i_N - 1因为任何不落在这些超平面中的点其全部分量都 ≥ 首元素若是好序列就不可能出现在其中。而序列在每个超平面上的子序列由归纳假设都是有限的。序列在这个有限个有限集合的并集中不重复地访问点因此必然有限。结论任何有N1个不同键的好序列都是有限的归纳完成。该构造给出的界并非完全紧致因为超平面之间存在重叠不过一旦把重叠考虑进去界就是紧的——按各点 L1 范数分量之和的降序访问超平面并集中的所有点即可构造出达到上界的序列。本段论证文字源自 issue #2458 的评论。仓库中的落地实现与测试佐证该算法的实际落地情况可以从当前仓库源码中核实。核心实现在 toolchain/check/impl_lookup.cpp函数FindAndDiagnoseImplLookupCycleimpl_lookup.cpp 第 163-206 行负责检测并诊断impl查找中的循环。其注释明确引用 acyclic 规则通过查看之前的查找是否具有完全相同的类型输入来发现违规query_facet_type_const_id编码了被查找的整个 facet 类型包括泛型接口的特定参数。一旦命中会发出ImplLookupCycle诊断cycle found in search for impl of ... for type ...并对栈上每个活跃的impl声明追加ImplLookupCycleNote说明determining if this impl clause matches。循环检测所依赖的查找栈由 context.h 第 243-251 行 的ImplLookupStackEntry结构定义每个条目记录查询的query_self_const_id、query_facet_type_const_id、正在考察的impl位置以及是否已报告过循环。需要如实指出截至当前仓库版本impl_lookup.cpp第 176-178 行仍保留TODO说明严格更复杂的完整终止规则即本提案的复杂度度量部分在toolchain/check中尚未完全实现目前生效的主要是 acyclic 规则部分。测试方面toolchain/check/testdata/impl/lookup/impl_cycle.carbon 集中验证了各类循环场景的报错行为fail_impl_simple_cycle第 13-40 行impl forall [T: Z] T as Z与自身形成依赖循环对Point as Z报ImplLookupCycle错误并附带说明是哪条impl声明在匹配fail_impl_simple_where_cycle第 42-66 行impl forall [T: type where .Self impls Z] T as Z通过where约束产生自依赖同样被检测fail_impl_simple_two_interfaces第 68 行起两个接口Z Y约束下形成循环的情形。这些测试可以通过 Bazel 单独运行验证例如bazel test //toolchain/testing:file_test --test_arg--file_teststoolchain/check/testdata/impl/lookup/impl_cycle.carbon。设计动机与 Carbon 核心目标对齐本提案在 Rationale 一节 明确列出了它所推进的 Carbon 项目目标语言工具与生态通过提升诊断质量尽早、精准地报告循环错误信息简短可懂来改善工具链体验软件与语言演进所选规则避免因重构引入失败尤其是那些发生在被重构文件之外的失败易于阅读、理解和编写的代码规则本身相对简单编写代码时可预测且允许相互独立的模块组合而不触发意外错误。从形式设计文档 docs/design/generics/details.md#termination-rule 的对比说明也可以看到Rust 用递归上限解决同样问题与 C 编译器终止模板递归的方式类似而这与 Carbon 泛型可预测性目标相抵触——因为解析一个impl查询所需步骤数的增加可能导致远处代码撞上递归上限。Carbon 的方案则能识别循环中的最小步骤使错误消息尽可能短小易懂。备选方案回顾原提案在确定最终规则之前系统评估了五个备选方案每个都有明确取舍备选 1用类型树深度度量复杂度禁止查询中类型树深度增加深度可在查询中度量也可在用于参数化impl声明的类型取值中度量。缺点本可安全进行的重构可能触发虚假的终止错误——例如把String替换为参数化类型的别名BasicString(Char8)会改变未参与重构文件中的类型树深度。备选 2分别考虑impl声明中的每个类型参数不度量整个impl查询的复杂度而是分别度量单条impl声明中各参数的值。优点是终止规则导致的误报更少但被否决因为规则更复杂、且对impl声明如何参数化敏感这同样有重构引入失败之虞——在没有证据表明误报在实践中有多严重之前不引入这种变更。备选 3把被实现接口中的类型视为独立命名空间将查询的类型部分与接口部分分别放在不同命名空间计数误报比备选 2 少且不像备选 2 那样对参数化方式敏感。当前不选它是因为规则更难以解释但如果未来实践表明值得支持更多用例会重新考虑。备选 4要求某个计数必须减少直接禁止类型多重集重复可简化终止论证。但被否决因为需要支持这类把项洗牌成某种规范形式的impl声明impl forall [T:! I(Optional(.Self))] Optional(T) as I(T);这里Optional(bool) impls I(bool)的前提是bool impls I(Optional(bool))。此类规则只能应用有限多次且被认为可能在实践中自然出现值得支持。备选 5要求非类型值保持不变对不具整型或choice类型的非类型参数值要求其保持恒定。这引发一系列边界情况例如类型构造器被调用次数不同时如何识别同一个参数。最终选择的现行规则更简单、接受更多用例这些参数的值可以自由变化只是在终止检测的意义上不产生不同的类型表达式。总结Carbon 语言以基本类型计数 严格超集判定为核心为impl选择构造了一个可证明终止、对重构稳健、诊断友好的终止规则查询复杂度只增不减即报错配合 acyclic 规则杜绝查询重复数学归纳法保证任何有限键集合下的必然终止。这一设计已被采纳进正式设计文档并在工具链的循环检测ImplLookupCycle诊断中部分落地、由 impl_cycle.carbon 等测试用例守护而完整复杂度度量部分仍在 toolchain/check/impl_lookup.cpp 中以待办形式推进。对于语言实现者和类型系统研究者这套用复杂度单调性代替硬性深度上限的思路本身就是一份值得借鉴的终止性设计样本。【免费下载链接】carbon-langCarbon Languages main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Carbon 语言 `impl` 选择终止算法：以“严格超集“规则替代递归限制
Carbon 语言impl选择终止算法以严格超集规则替代递归限制【免费下载链接】carbon-langCarbon Languages main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang本篇技术指南深入解析 Carbon 语言提案 p002687如何为impl声明选择impl selection设计一个可预测、可证明终止的算法以替代传统编译器中递归深度上限的粗暴方案。读完本文你将掌握 Carbon 如何用基本类型计数 严格更复杂判定度量查询复杂度、如何处理整数与choice类型等非类型参数、如何用数学归纳法证明算法必然终止以及该规则在 toolchain/check/impl_lookup.cpp 中的实际落地状态。问题背景递归限制为什么不够好考虑下面这条impl声明interface I; impl forall [T:! type where Optional(.Self) is I] T as I;i32是T的一个合法取值因此i32实现I的前提是Optional(i32)实现I而这条impl声明可能同样被用于给Optional(i32)提供对I的实现——但这又要求Optional(Optional(i32))实现I。如此无穷嵌套下去如果没有约束编译器就会陷入死循环。终止规则termination rule的职责就是在这种情况下直接报告错误而不是被无限循环困住。早期设计沿用了 Rust 与 C 的做法设置一个递归深度上限。但递归限制存在几个系统性缺陷错误发现太迟循环往往要重复很多次之后才会撞到深度上限且上限越大问题暴露得越晚错误信息也随之臃肿难懂。理想的终止规则应当以最小化的方式识别循环——这既能降低编译耗时也能让错误消息尽可能简短、可理解。重构引发假性失败某些原本合法的重构会无意中加深递归深度触发本不该出现的失败而常见的修复方式是调大递归上限这又让前一个问题更严重。违背可预测性目标递归上限的存在使得远处代码的行为是否会改变不可预测这与 Carbon 在 generics 可预测性目标 中的承诺相悖。需要特别说明的是判断一组impl声明是否会终止在一般情形下等价于停机问题是不可判定的。因此任何终止规则都必然存在误报spurious failure——即代码本可正常结束却被判为错误。设计的目标不是消除误报而是让判定准则在实践中真实出现的代码上保持正确。历史脉络从递归限制到本提案第一个终止规则随提案 #920: Generic parameterized impls (details 5) 引入同样借鉴了 Rust 和 C。当时的文档就承认了递归限制的问题只是还没有找到替代方案。此后替代方案经过了多轮公开讨论2022-04-13 的开放讨论由提案 #1088: Generic details 10: interface-implemented requirements 中的一个问题引发issue #2458: Infinite recursion during impl selection 汇总了包括 2023-02-07 在内的多轮讨论结论。PR #2602 曾将该规则在 Carbon 的 Explorer早期解释器实现中落地而本提案PR #2687正式确立了这套算法的设计。该设计随后被写入正式设计文档 docs/design/generics/details.md 的 Termination rule 一节其中以 issue #2880 跟踪已知的、实际代码中本可终止却被误拒的问题。核心提案基本类型计数与严格更复杂判定本提案用一条新规则替换终止准则在重新考虑同一条impl声明时impl查询中的类型绝不能变得严格更复杂。一组类型的复杂度如何度量答案是统计每种基本类型base type出现的次数。基本类型即去掉参数后的类型名。例如查询Pair(Optional(i32), bool) impls AddWith(Optional(i32))中包含的基本类型有PairOptional出现 2 次i32出现 2 次boolAddWith于是严格更复杂的定义是至少一个计数增加且没有任何计数减少。因此Optional(Optional(i32))比Optional(i32)严格更复杂Optional与i32的计数都增加但Optional(Optional(i32))并不比Optional(bool)严格更复杂Optional计数增加但i32计数减少为 0。把每个基本类型计数看作多维空间中的一个点这条规则的本质是在查询序列中复杂度向量只能只增不减地移动一旦出现任何方向的下降就脱离严格更复杂的判定范围。与 acyclic 规则协同一个循环例子这条严格更复杂规则需要与 acyclic 规则查询不能原样重复配合使用两者结合才能证明终止。看回开头的例子interface I; impl forall [T:! type where Optional(.Self) is I] T as I;该impl声明匹配查询i32 impls I的前提是Optional(i32) impls I。而后者是一个严格更复杂的查询——它包含起始查询的全部基本类型i32和I还多了一个Optional。因此一步之后就能给出错误而不是等到撞上很大的递归上限。错误消息还能明确指出问题所在我们从没有Optional的查询走到了有一个Optional的查询且没有任何计数减少。需要强调的是该规则仅在同一条impl声明以严格更复杂的查询被重新考虑时才触发失败。如果因为存在更特化的impl声明、被类型结构重叠规则优先选中从而根本不会考虑第一条声明则不会报错impl forall [T:! type where Optional(.Self) is I] T as I; impl Optional(bool) as I; // OK, because we never consider the first impl // declaration when looking for Optional(bool) impls I. let U:! I bool; // Error: cycle with i32 impls I depending on // Optional(i32) impls I, using the same impl // declaration, as before. let V:! I i32;该规则对重构同样稳健这是设计时明确追求的三大特性不依赖impl声明如何参数化只看查询本身不依赖查询链的长度不依赖类型表达式复杂度如树的深度这类度量。细节一非类型参数的处理基本类型计数只覆盖类型参数对非类型参数non-type arguments必须扩展出额外的键key。这些键与基本类型分属独立的命名空间整型值以整型类型名为键以绝对值为计数。也就是说整型参数的复杂度随绝对值增大而上升。例如2和-3同时作为i32类型参数的取值时i32这个键的计数为5|2| |-3|。choice类型的每个选项每个选项option都是自己的键统计使用该选项的值出现次数选项自带的参数再作为独立键记录。例如值.Some(7)类型为Optional(i32)会被记录为键.Some计数1和键i32计数7。可变参数variadic还有一个独立的键命名空间挂靠在基本类型之下用来统计可变参数的个数。这是为了防御这样的场景可变参数类型V接受任意多个i32参数从而产生无限多个互不相同的实例V(0)、V(0, 0)、V(0, 0, 0)、……其中该命名空间中的tuple键用于统计元组值的分量总数各分量的取值再通过各自的键来追踪。对于未被上述规则覆盖的非类型参数值会从查询中整体删除即不参与终止算法的复杂度判定。这样做的必然结果是两个仅因这类非类型参数而不同的查询会被视为同一查询从而被 acyclic 规则拒绝。否则我们就能构造出无限多个非类型参数值来规避终止判定——这是设计中必须堵住的漏洞。细节二终止性证明一个数学归纳论证本规则能否保证终止需要严谨证明。这里给出原提案的完整论证思路。把一段有限或无限类型表达式序列称为好good的如果没有后一个元素比某个前一个元素严格更复杂且没有任何类型表达式重复出现。要证明的是任何键集合有限的好序列都是有限的。证明的第一步是化简可以只考虑不重复任何键多重集multiset的好序列因为给定一个键多重集最多只能对应有限多个类型——若所有类型都没有可变参数列表那么对基本类型的每一种排列至多对应一个类型若存在可变参数类型则把不同排列数乘以可能的元数arity组合数得到一个保守的有限上界而元数组合数有限是因为忽略非类型参数后总元数必须等于类型中基本类型数减 1。随后用对键的个数N的归纳法完成证明N 1类型映射为单一键的多重集可用该键的出现次数表示。这个数在序列中非负且递减因此序列长度以首元素取值为界必然有限。归纳步假设N个键的好序列有限证明N1个键的也有限首个元素可表示为非负整数(N1)元组(i_0, i_1, ..., i_N)。其后的每个元素必定落在由以下方程给出的某个超平面余维数为 1中x_0 0, x_0 1, ..., x_0 i_0 - 1共i_0个不同的方程每个定义独立超平面x_1 0, x_1 1, ..., x_1 i_1 - 1……x_N 0, x_N 1, ..., x_N i_N - 1因为任何不落在这些超平面中的点其全部分量都 ≥ 首元素若是好序列就不可能出现在其中。而序列在每个超平面上的子序列由归纳假设都是有限的。序列在这个有限个有限集合的并集中不重复地访问点因此必然有限。结论任何有N1个不同键的好序列都是有限的归纳完成。该构造给出的界并非完全紧致因为超平面之间存在重叠不过一旦把重叠考虑进去界就是紧的——按各点 L1 范数分量之和的降序访问超平面并集中的所有点即可构造出达到上界的序列。本段论证文字源自 issue #2458 的评论。仓库中的落地实现与测试佐证该算法的实际落地情况可以从当前仓库源码中核实。核心实现在 toolchain/check/impl_lookup.cpp函数FindAndDiagnoseImplLookupCycleimpl_lookup.cpp 第 163-206 行负责检测并诊断impl查找中的循环。其注释明确引用 acyclic 规则通过查看之前的查找是否具有完全相同的类型输入来发现违规query_facet_type_const_id编码了被查找的整个 facet 类型包括泛型接口的特定参数。一旦命中会发出ImplLookupCycle诊断cycle found in search for impl of ... for type ...并对栈上每个活跃的impl声明追加ImplLookupCycleNote说明determining if this impl clause matches。循环检测所依赖的查找栈由 context.h 第 243-251 行 的ImplLookupStackEntry结构定义每个条目记录查询的query_self_const_id、query_facet_type_const_id、正在考察的impl位置以及是否已报告过循环。需要如实指出截至当前仓库版本impl_lookup.cpp第 176-178 行仍保留TODO说明严格更复杂的完整终止规则即本提案的复杂度度量部分在toolchain/check中尚未完全实现目前生效的主要是 acyclic 规则部分。测试方面toolchain/check/testdata/impl/lookup/impl_cycle.carbon 集中验证了各类循环场景的报错行为fail_impl_simple_cycle第 13-40 行impl forall [T: Z] T as Z与自身形成依赖循环对Point as Z报ImplLookupCycle错误并附带说明是哪条impl声明在匹配fail_impl_simple_where_cycle第 42-66 行impl forall [T: type where .Self impls Z] T as Z通过where约束产生自依赖同样被检测fail_impl_simple_two_interfaces第 68 行起两个接口Z Y约束下形成循环的情形。这些测试可以通过 Bazel 单独运行验证例如bazel test //toolchain/testing:file_test --test_arg--file_teststoolchain/check/testdata/impl/lookup/impl_cycle.carbon。设计动机与 Carbon 核心目标对齐本提案在 Rationale 一节 明确列出了它所推进的 Carbon 项目目标语言工具与生态通过提升诊断质量尽早、精准地报告循环错误信息简短可懂来改善工具链体验软件与语言演进所选规则避免因重构引入失败尤其是那些发生在被重构文件之外的失败易于阅读、理解和编写的代码规则本身相对简单编写代码时可预测且允许相互独立的模块组合而不触发意外错误。从形式设计文档 docs/design/generics/details.md#termination-rule 的对比说明也可以看到Rust 用递归上限解决同样问题与 C 编译器终止模板递归的方式类似而这与 Carbon 泛型可预测性目标相抵触——因为解析一个impl查询所需步骤数的增加可能导致远处代码撞上递归上限。Carbon 的方案则能识别循环中的最小步骤使错误消息尽可能短小易懂。备选方案回顾原提案在确定最终规则之前系统评估了五个备选方案每个都有明确取舍备选 1用类型树深度度量复杂度禁止查询中类型树深度增加深度可在查询中度量也可在用于参数化impl声明的类型取值中度量。缺点本可安全进行的重构可能触发虚假的终止错误——例如把String替换为参数化类型的别名BasicString(Char8)会改变未参与重构文件中的类型树深度。备选 2分别考虑impl声明中的每个类型参数不度量整个impl查询的复杂度而是分别度量单条impl声明中各参数的值。优点是终止规则导致的误报更少但被否决因为规则更复杂、且对impl声明如何参数化敏感这同样有重构引入失败之虞——在没有证据表明误报在实践中有多严重之前不引入这种变更。备选 3把被实现接口中的类型视为独立命名空间将查询的类型部分与接口部分分别放在不同命名空间计数误报比备选 2 少且不像备选 2 那样对参数化方式敏感。当前不选它是因为规则更难以解释但如果未来实践表明值得支持更多用例会重新考虑。备选 4要求某个计数必须减少直接禁止类型多重集重复可简化终止论证。但被否决因为需要支持这类把项洗牌成某种规范形式的impl声明impl forall [T:! I(Optional(.Self))] Optional(T) as I(T);这里Optional(bool) impls I(bool)的前提是bool impls I(Optional(bool))。此类规则只能应用有限多次且被认为可能在实践中自然出现值得支持。备选 5要求非类型值保持不变对不具整型或choice类型的非类型参数值要求其保持恒定。这引发一系列边界情况例如类型构造器被调用次数不同时如何识别同一个参数。最终选择的现行规则更简单、接受更多用例这些参数的值可以自由变化只是在终止检测的意义上不产生不同的类型表达式。总结Carbon 语言以基本类型计数 严格超集判定为核心为impl选择构造了一个可证明终止、对重构稳健、诊断友好的终止规则查询复杂度只增不减即报错配合 acyclic 规则杜绝查询重复数学归纳法保证任何有限键集合下的必然终止。这一设计已被采纳进正式设计文档并在工具链的循环检测ImplLookupCycle诊断中部分落地、由 impl_cycle.carbon 等测试用例守护而完整复杂度度量部分仍在 toolchain/check/impl_lookup.cpp 中以待办形式推进。对于语言实现者和类型系统研究者这套用复杂度单调性代替硬性深度上限的思路本身就是一份值得借鉴的终止性设计样本。【免费下载链接】carbon-langCarbon Languages main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考