Roc 通配符驻留性检查Exhaustiveness 检查器如何处理空类型上的_模式【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/roc本文围绕 Roc 编译器中一个具体而关键的问题展开当模式匹配中出现通配符_或变量绑定时穷举性exhaustiveness检查器如何验证其类型是驻留的inhabited即至少存在一个可能的值。读完本文你将理解 exhaustive.zig 中isInhabited()判断、空类型构造器过滤与开放联合open union扩展链跟随的完整实现机制以及为何不能在构建 Union 时就过滤空构造器这一核心设计决策背后的推理——这直接关系到Try(I64, [])这类类型上Err(_)为何会被正确报告为不可达而非类型错误。问题定义空类型上的通配符不该贡献穷举性Roc 的类型系统允许定义空联合类型empty tag union最典型的就是Try(I64, [])错误类型为空联合意味着Err分支永远不可能构造出任何值。此时如果用户写x : Try(I64, []) match x { Ok(n) n }这个匹配应当被判为穷举的——因为不存在任何会走到Err分支的值。但反过来如果通配符无脑贡献穷举性那么空类型上的任何匹配都可能被错误放行或错误要求补充分支。核心规则是当通配符模式_或变量绑定匹配某类型时穷举性检查器应验证该类型是驻留的空类型上的通配符不应贡献穷举性。该问题在当前仓库中已实现完毕对应的设计记录见 001_wildcard_inhabitedness.md。实现依赖三个协同工作的机制。机制一带类型信息的缺失模式构造当矩阵特化matrix specialization算法走到矩阵为空但列仍在的基例时说明现有分支没有覆盖所有情况算法需要构造一个缺失模式用于向用户报告。关键约束是缺失模式必须携带类型信息类型来源是ColumnTypes。从 checkExhaustiveSketched 附近的缺失模式构造代码可以看到// 基例矩阵为空但仍有列待覆盖 不穷举 if (matrix.isEmpty()) { if (n 0) { return [_]Pattern{}; } // 返回带类型的通配符作为缺失模式 const missing try allocator.alloc(Pattern, n); for (column_types.types, 0..) |col_type, i| { missing[i] .{ .anything col_type }; } return missing; }见 src/check/exhaustive.zigPattern.anything是一个可携带类型变量的变体|maybe_type|因此报告给用户的缺失模式永远可以进一步做驻留性过滤。算法运行过程中的中间通配符可能确实缺少类型信息但它们只存在于矩阵特化的中间产物中永远不会被直接送去做驻留性检查。机制二Pattern.isInhabited()的驻留性判断Pattern.isInhabited 回答这个模式是否可能匹配到某个真实存在的值。对.anything分支的处理是整条链路的枢纽.anything |maybe_type| { if (maybe_type) |type_var| { // 用全面检查判断该类型是否驻留 return isTypeInhabitedWithKnownEmpty(type_store, builtin_idents, type_var, known_empty_vars); } // 无类型信息的通配符只应出现在矩阵特化的中间模式里 // 它们永远不会被检查驻留性。 // 缺失模式始终能从 ColumnTypes 拿到类型信息。 unreachable; },值得注意的是设计演化早期实现中无类型信息的通配符会硬编码return true而当前实现已改为unreachable——因为按机制一的保证正常路径上不存在这种模式若真的走到这里说明不变量被破坏宁可崩溃也不静默放行。这与文档验收标准普通路径上没有对无类型信息通配符的硬编码return true一致。对构造器模式isInhabited的语义是 AND 组合空闭联合无候选项且无 flex 扩展判为不驻留否则要求所有参数模式都驻留.ctor |c| { // 空闭联合是不驻留的 if (c.union_info.alternatives.len 0 and !c.union_info.has_flex_extension) { return false; } // 模式驻留要求所有参数都驻留 for (c.args) |arg| { if (!try arg.isInhabitedWithKnownEmpty(type_store, builtin_idents, known_empty_vars)) return false; } return true; },见 src/check/exhaustive.zig机制三穷举性检查期间跳过不驻留的构造器在 checkExhaustiveSketched 遍历联合的候选项alternatives时对每一个矩阵中尚未覆盖的构造器先取得其参数类型再做驻留性过滤if (!found) { // 跳过的原因是不驻留的构造器无需匹配—— // 不可能存在该构造器的值。 const arg_types try getCtorArgTypes(type_store, builtin_idents, first_col_type, alt.tag_id); if (!try areAllCtorArgTypesInhabitedWithKnownEmpty(type_store, builtin_idents, arg_types, payload_vars_to_close.items)) { continue; } // 继续按该构造器特化矩阵 ... }见 src/check/exhaustive.zig对Try(I64, [])而言Err构造器的参数类型是空联合areAllCtorArgTypesInhabitedWithKnownEmpty返回false于是Err被直接跳过——用户只写Ok分支也算穷举。设计决策为什么过滤必须发生在检查期而非构建期这是文档中强调得最充分的决策点。空构造器不能在构建Union结构的 buildUnionFromTagUnion 阶段就被剔除而必须在穷举性检查阶段checkExhaustiveSketched跳过。原因在于冗余度redundancy检查的依赖x : Try(I64, []) // 错误类型为空Err 不驻留 match x { Err(_) 0 // 应被报告为冗余 / 不可达 Ok(n) n }若在构建 Union 时就过滤掉Err用户显式写出的Err(_)模式会经 findTagId 查找失败返回null编译器只能报出找不到该标签之类的类型错误而不是更有意义的此分支不可达。若保留Err在 Union 中、仅在穷举性检查时跳过模式匹配阶段能找到Err构造器进而把它识别为不可达unreachable/redundant穷举性阶段因跳过它不会要求用户必须写Err分支。两种语义同时成立。换言之Union.alternatives是语法上存在的构造器全集而穷举性检查在其上叠加语义上需要覆盖的子集这一层过滤。驻留性判定算法isTypeInhabitedWithKnownEmpty的 worklist 实现isTypeInhabitedWithKnownEmpty 是判定单个类型是否驻留的核心。文档将其概括为以栈为主的迭代算法当前源码已演进为完整的worklist工作列表算法——源码头注释明确引用了 004_worklist_inhabitedness_algorithm.md 的设计说明目的是避免在深层嵌套类型上递归爆栈。其结构可以概括为一个工作列表 一个布尔结果栈工作项由 WorkItem 定义工作项语义check_type检查一个类型变量是否驻留结果压入结果栈and_combine: u32弹出 N 个结果做 AND 合并N0 时空 AND 视为trueor_combine: u32弹出 N 个结果做 OR 合并N0 时空 OR 视为falsecheck_open_extension结果若为false且扩展是开放的flex/rigid则改判trueleave_nominal检查完名义类型 backing 后登记离栈使非规则的递归应用也能收敛按类型结构的判定规则AND/OR 语义记录 / 元组所有字段都必须驻留AND 语义所有字段类型压入工作列表配一个and_combine任一字段不驻留则整体不驻留。标签联合各 tag 之间是 OR 语义——只要存在某个 tag 的参数全部驻留整个联合就驻留每个 tag 的参数内部是 AND 语义。空标签联合empty_tag_union直接判false空记录unit 类型判true。别名 / 名义类型沿 backing 类型继续检查但内置数值类型I64、U8等有特殊处理——它们的 backing 类型在类型存储中表现为[]空联合若机械地跟随 backing 会得到荒谬的I64 不驻留结论因此源码中显式用builtin_idents.isBuiltinNumericIdent/isBuiltinNumericType直接判为驻留见 src/check/exhaustive.zig。flex / rigid / 函数类型视为驻留——flex 变量尚未被完全约束可能统一为任何类型函数本身就是值。递归类型通过seen集合做环检测递归路径视为驻留能走到递归处说明存在非递归的构造路径名义类型的递归则用active_nominals集合配合leave_nominal工作项收敛。此外known_empty_vars参数把在别处已被证明为空的类型变量作为已知事实传入检查中若遇到这些变量直接返回false避免重复推导参见 varIsKnownEmpty。开放联合Open Union语义当联合类型带有扩展变量extension时穷举的含义会变化isOpenExtension 的判定逻辑是/// 开放联合可能存在超出显式列出构造器之外的构造器。 /// 发生条件是扩展为 /// - flex 变量类型尚未被完全约束可能再统一进更多 tag /// - rigid 变量用户显式声明还可能有更多 tag fn isOpenExtension(type_store: *TypeStore, ext: Var) bool { return switch (content) { .flex, .rigid true, // 两者都是开放 .structure |flat_type| switch (flat_type) { .empty_tag_union false, // 闭联合 .tag_union true, // 嵌套 tag 开放 else false, }, ... }; }flex 扩展类型未被完全约束可能统一进更多 tag视为开放rigid 扩展用户显式写了还可能有其他 tag同样视为开放empty_tag_union扩展闭联合穷举必须覆盖全部已知 tag。开放联合在构建 Union 时会追加一个合成的#Open候选项buildUnionFromTagUnion 中name Ident.Idx.NONE、arity 为 0 的占位构造器并要求模式中存在通配符或显式覆盖该位置才算穷举Union.has_flex_extension字段则保证带 flex 扩展的联合不会因候选项为空而被误判为不驻留也不会把通配符误报为冗余因为还可能统一进更多 tag。扩展链跟随统一产生的分裂标签类型统一unification可能把一个标签联合的 tag 拆散在扩展链上。例如统一[HasEmpty([]), Normal(I64)]与[Normal(I64)]可能得到[Normal(I64), ..ext] 其中 ext [HasEmpty([]), ..]此时 tag 不再全部位于顶层联合的tags里tags只有一层。两处关键代码都显式跟随扩展链buildUnionFromTagUnion循环解析ext若扩展本身是另一个标签联合则继续向下收集 tag扩展为 flex/rigid 时标记开放并停止为empty_tag_union或记录/元组等其他结构时标记闭合并停止为别名则解引用 backing 变量继续并用seen_exts集合做环检测防止死循环。getCtorArgTypes按tag_id在全局收集序列中定位目标 tag逐层推进current_offset与扩展链同样带环检测。它同时负责名义类型的打开openNominalBacking使Try(A, B)这类带类型参数的名义类型返回的是实际类型实参而非 backing 模板的形式参数。findTagId返回的tag_id保存的是 tag 在收集序列中的原始索引而非数组位置正是为了让getCtorArgTypes能据此跨扩展链找回正确的位置。完整工作流程把上述机制串起来一次穷举性检查对空类型的处理路径是构建 UnionbuildUnionFromTagUnion跟随扩展链收集全部 tag包括不驻留的如Err开放联合追加合成#Open项——此阶段不做任何驻留性过滤矩阵特化算法按候选项逐层特化模式矩阵特化中产生的中间通配符可能缺类型信息但不参与驻留性判定跳过不驻留构造器对矩阵未覆盖的构造器checkExhaustiveSketched用areAllCtorArgTypesInhabitedWithKnownEmpty过滤Err(_)之于Try(I64, [])即在此被跳过构造缺失模式若仍有缺口用ColumnTypes中的类型构造带类型的缺失模式驻留性过滤报告缺失模式经过isInhabited()最终落到 worklist 版isTypeInhabitedWithKnownEmpty过滤空类型上的缺失模式如Err(_)永远不会展示给用户。冗余性检查共享同一份Union结构因此能正常把空类型上的显式Err(_)识别为不可达。测试覆盖src/check/test/exhaustiveness_test.zig 中的以下测试逐条对应上述机制测试用例文件内实际名称行号验证点exhaustive - empty error type means only Ok neededL367Try(I64, [])只写Ok即穷举exhaustive - nested Try with empty inner errorL385嵌套的空错误类型工作正常exhaustive - doubly nested empty errorsL403深度嵌套场景redundant - wildcard after complete coverage on type with empty variantL456空变体类型上Ok之后的通配符冗余unmatchable - Err pattern first on empty error type is unreachableL474空错误类型上Err(_)被判不可达而非类型错误unmatchable - pattern on tag with direct empty argL709[HasEmpty([]), Normal(I64)]上HasEmpty(_)冗余non-exhaustive - not all inhabited tags covered with empty argL727[A(I64), B([]), C(Str)]缺C时正确报不穷举小结这套实现的核心可以浓缩为三条不变量缺失模式永远携带ColumnTypes提供的类型信息驻留性判定是纯迭代 worklist 算法且内置数值类型绕开backing 为空联合的陷阱不驻留构造器的过滤只发生在穷举性检查阶段Union结构本身保留完整候选集以支撑冗余度检查。理解这三点基本就理解了 Roc 在空类型模式匹配上的全部关键行为——包括为什么Try(I64, [])上Ok单分支合法而Err(_)分支会被精确地标记为不可达。【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/roc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考