oort-core 类型检查与推断算法¶
状态:as-implemented 参考(2026-11-22,含返回推断、泛型 ADT、单继承与静态接口)。 本文描述
oort-core静态检查器当前实现的双向检查与局部推断算法,作为 OP 0005 主线后续切片(泛型、ADT、FFI)的 算法基线。
0. 文档分工¶
| 文档 | 角色 |
|---|---|
| 本文(14) | 已实现算法:双向检查、局部推断、返回推断的机制与规则 |
| spec 11 | 规范性语言参考:哪些构造合法、诊断是什么 |
| implementation 09 | 检查器代码结构:visitor、作用域、模块导入、诊断管线 |
| design 03 | 未来完整类型系统:渐进类型边界、泛型、Phase-2 HM |
| OP 0017 | 薄探针决策:为什么选局部双向检查而非 HM |
本文与 design 03 的分工:design 03 描绘远期(全程序 HM、泛型单态化、健全 边界);本文只描述已经落地的局部版本。二者不重复。
1. 局部双向检查¶
检查器采用双向类型检查(bidirectional typing)的局部版本,两个方向:
check(expr, expected):已知期望类型,验证表达式符合它;infer(expr):无期望类型,从表达式推出类型。
实现上二者统一在 CoreTypeChecker._check_expr(node, expected):
expected = UnknownType 即 infer 模式。对 if/块/match 等分支构造,
expected 非 Unknown 时下推到各分支(_check_if_expected /
_check_block_expected / _check_match);否则走合成(infer)路径,用
join_types 合并分支类型。
取舍依据(OP 0017 已引):Pierce & Turner 的 local type inference 与 Dunfield & Krishnaswami 的 bidirectional typing 综述都支持「局部双向检查 足以覆盖实用场景,无需全程序 HM」。Oort 不做全程序 HM:签名边界清晰、错误 信息可定位、模块化编译简单;HM 留作 design 03 的 Phase-2 可选扩展。
2. 类型格与合并¶
静态类型独立于运行时 OortType(semantics/core/types.py):
PrimitiveType:Int/Float/Bool/String/Unit;- 集合:
ListType/SetType/DictType/TupleType(结构相等); FunctionType(params, ret)(frozen)、ClassType/AdtType(名义相等, 注册后填充以支持递归;ClassType.bases表示单继承,见 §11)、ModuleType;UnknownType:错误恢复类型,与任何类型双向兼容(is_assignable恒真), 用于抑制级联诊断;NeverType:底类型(bottom),表示不能正常落到的表达式(return、break、continue)。
两个关键运算:
is_assignable(expected, actual):Unknown 双向兼容;Never 可赋给任何类型; 其余 Primitive 严格相等,无 Int→Float 提升;类沿bases判定名义子类型; 函数类型参数逆变、返回协变;ADT 按声明处变型逐参比较。join_types(left, right):分支/返回类型的最小上界(LUB)。Unknown 吸收一切、 Never 是单位元、相等取自身、同类沿基类链取最近公共祖先;没有公共上界的 组合(含 Int/Float)返回 None。不做数值提升——混合分支报错而非隐式转换。
为什么 join 不合并到 Object?¶
直觉上 if c { 1 } else { "s" } 类似乎可以推成「Object」,但当前刻意不这么做:
- 静态模型没有顶类型。类有名义子类型与基类 LUB,但 Primitive/集合/ADT
之间没有统一的静态
Object/Any;is_assignable对 Primitive 严格相等, 对类沿bases,对 ADT 按变型。运行时虽有object_type作为类继承的根, 静态检查器刻意不建模它。没有公共上界的组合只能返回 None。 - 即便推出 Object 也是死胡同。静态子集没有向下转型/类型测试/按类型匹配,
Object 值既不能调 Int 也不能调 String 的方法,什么都做不了;只会把错误从分支处
推迟到使用处(
v + 1才报「Object 不支持 +」),更难定位。在分支处直接报 「Int 和 String 不兼容」更符合「错误就地归责」(blame)。 - 与「显式优于隐式」一致。连 Int→Float 都不偷偷提升,合并到 Object 属隐式向上 宽化,同样拒绝。
- 「Int 或 String」的正确表达是和类型/ADT,而非 Object:
enum IntOrStr { I(Int), S(String) }+match取用,显式、类型安全、可消费。 Object/any 是跨方言动态边界的逃生舱,不是静态合并工具。
跨语言对照:这是没有 union 类型的语言的共同选择——Rust/Haskell 同样报错、
引导用 enum;TypeScript 因有 union 才推出 number | string。待 Oort 引入 union
或更依赖 ADT,此规则再议。
3. expected-type 传播¶
期望类型从这些位置下推:变量标注、赋值 RHS、return 值、函数体尾表达式、
调用实参、槽初始化器。下推目标是分支构造的最后表达式:
if两分支、块最后一条语句、match各 arm 体;- 空集合字面量(
[]/{:}/{.})必须靠期望类型定元素类型,否则报Cannot infer the element type of an empty List; add a type annotation.。
只作用于最后一条语句:_check_statements_expected 对非尾部语句纯 infer。
NeverType 一旦出现(某路径 return),后续语句不再贡献类型(saw_never),
整块类型为 Never——这是「所有路径返回」检测的基础。
4. 局部推断¶
val x = expr无标注时 inferexpr;Unknown静默(错误恢复),Never/Module/Unit不能作为变量推断类型(Unit只能做函数返回)。- 推断类型写入
node.metadata["type"],供-t astm展示。 - 函数签名在检查函数体之前安装,因此自递归调用可解析;顶层按源码顺序 可见,不支持前向引用/互递归(spec 11)。
5. 函数返回类型推断(2026-11-22)¶
范围:顶层 def、do lambda 与类方法可省略返回标注;__init__ 固定
Unit。参数仍强制标注。顶层 def/lambda 为第一切片,类方法为第二切片(依赖序推断)。
算法(_build_signature / _check_function_body / visit_return_expr):
- 缺标注时以
ret = Unknown占位建签名并先 declare(自递归 lookup 需要), 进入 infer 模式;压一个_ReturnInfer帧到_infer_stack(与函数体嵌套 平行,lambda 嵌套时内层遮蔽外层)。 - 以
expected = Unknown检查函数体;visit_return_expr把每个return表达式的类型收进帧(bare return 记 Unit)。 - 收尾:候选 = 收集到的 return 类型 +(体类型非 Never 时的尾表达式类型),
用
join_types折叠。 - 体期间已有错误 → ret=Unknown,不追加诊断(级联抑制);
- join 冲突 →
The return types of function 'f' are incompatible: X and Y.; - 空体/Unit 尾 → Unit;全路径 return → 只用 return 集合。
FunctionTypefrozen,故重建签名并回填NameInfo.type与node.metadata["type"];module_exports在模块末尾快照,推断结果自动 正确跨模块导出。
lambda 期望下推:val f: (Int) -> Int = do(x: Int) { x } 中,期望函数类型
的返回分支经 _build_signature 的 default_return 挂钩传入(check 模式);
无期望时 lambda 与 def 一样从体推断。
自递归仍需标注:推断期间递归调用拿到占位 Unknown,会经算术/join 吸收导致
推断坍缩,无法可靠定类型。因此检测到自引用(_mark_recursive_call 命中正在
推断的帧)且缺标注时报:
Recursive function 'f' requires a return type annotation in oort-core; add '-> T'.
前向/互递归本就被拒,无需处理。
5.1 类方法:依赖序(拓扑)推断¶
方法与顶层 def 的关键差异:方法前向/互调用合法(类两遍检查先把全部签名装入
class_type.methods,再查体),没有顶层「源码顺序可见」那层保护。若朴素按源码
顺序推断,方法 A 调用尚未推断的方法 B 会拿到 Unknown 占位,经算术/join 吸收导致
A 的推断静默坍缩(无诊断)。为此方法采用依赖序推断
(_infer_and_check_methods / _method_dependencies):
- 第一遍对缺标注方法以
infer_return=True建 Unknown 占位签名。 - 依赖扫描:遍历每个缺标注方法体,收集引用到的同类方法名(
this.m()、 其他实例上的调用、方法作值;按属性名保守匹配)。 - 拓扑排序(Kahn):被调方法先推断;每推断一个就回填
class_type.methods(可变元组重赋值,this共享同一 ClassType 对象,立即全局可见)与stmt.metadata["type"]。拓扑序保证推断时不碰 Unknown 占位。 - 递归环(含自环=自递归)无法拓扑排序 → 这些方法报
Recursive method 'C.m' requires a return type annotation in oort-core; add '-> T'.再以占位签名查体(保留其他错误检查)。 - 已标注方法与
__init__最后查体,调用点类型不陈旧。
__init__(forced Unit)、构造器类型、确定赋值分析、槽初始化器均不受影响。
6. 跨语言对比:返回推断与递归标注¶
| 语言 | 函数返回推断 | 递归函数是否需显式返回类型 |
|---|---|---|
| Rust | 否(命名函数须写 -> T,省略即 ()) |
恒需标注 |
| Swift | 是(从体推断) | 复杂递归有时需要 |
| Kotlin | 是(单表达式/从体) | 是(递归/互递归需显式) |
| Scala | 是(从体) | 是(recursive method needs result type) |
| TypeScript | 是 | 否(可推断,有限制) |
| Oort | 是(def + lambda + 类方法) | 是(递归函数/方法需 -> T) |
Oort 的递归规则对齐 Kotlin/Scala。共同根因:推断靠分析函数体,而递归调用的 类型又依赖函数自身返回类型,形成循环依赖——编译器以「要求显式标注」解开。 这正是本切片用「占位 Unknown + 检测自引用」而非定点迭代/占位类型变量的原因: 贴合 OP 0017 局部推断哲学,避免 HM 式复杂度。
依据: - Kotlin 官方文档 · Functions: 递归/互递归函数应显式写返回类型; - Why does Scala require a return type for recursive functions? 与 Scala Type Inference: 递归方法无法推断结果类型。
7. 泛型 ADT、变型与内建 ADT(增量 A/B/C,2026-11-22)¶
泛型 enum E[T] 与声明处变型的已实现算法。设计取舍见
OP 0022 §2–§5;此处只记录落地形态。
表示。声明与应用分离:AdtTemplate(origin, name, params, constructors)
是类型构造器,AdtType(template, args) 是应用(Option[Int])。模板在解析
载荷前注册,所以 MyList[T] 的自递归载荷直接引用同一模板;载荷里只出现本模板的
TypeParameterType,嵌套泛型一律写成已应用类型(AdtType(option, (B,))),
substitute() 因此不会被内层参数捕获。单态 enum 是 params=() 的特例。
构造器方案。每个构造器是 ForallType(params, body):有载荷时 body 为
(payload...) -> AdtType(template, params),零参时为 AdtType(...)。
实例化。只有两处信息来源,不做 HM:
- check 模式:
_check_expr在期望是同模板AdtType时拦截 Call/Name, 用期望实参建立参数绑定,再以代换后的载荷检查实参——空字面量因此有期望 (Some([])、Cons(1, Nil)在MyList[Int]标注下可用)。 - infer 模式:
_check_generic_call先推断实参类型,再用unify()做受限 一阶合一求解参数;未绑定参数报硬错误(对齐 Rust E0282),冲突报 “同一参数被推断为 X 与 Y”。unify只在构造器与实参类型之间工作,不泛化、 不做 occurs check(本切片不会产生无限类型)。
裸泛型构造器作值只在期望是函数类型时实例化(val f: (Int) -> Option[Int] =
Some);否则 visit_name 报“无法推断类型实参”。
match。_instantiated_payload 把 scrutinee 的实参代入构造器载荷后再
检查子模式;穷尽性仍按模板的构造器名集合。运行时完全擦除:variant 名 +
payload,解释器与 VM 均不读类型参数。
声明处变型(增量 B)。TypeParameterType 带 Variance(不变/协变/逆变)。
文法用两个独立标签
(in_variance=IN | out_variance=identifier)? name=identifier:ANTLR 不允许同一
标签混用 token 与 rule,且 out 保持普通标识符(val out = 1 合法);其他
变型文本由 AST builder 报错。声明解析完 payload 后 _check_enum_variance
做极性检查:payload 起始极性 +1(构造器产出数据);FunctionType 参数取反、
返回不变;内建集合(不可变)保持极性;嵌套 AdtType 按
AdtType.variance_at(i) 复合(协变保持、逆变取反、不变型把极性压成 0)。
_variance_violation 返回第一个非法出现的极性:out 要求 +1,in 要求 −1,
0 表示不变位置(对两者都非法)。is_assignable 对同模板实参按变型逐参比较
(协变正向、逆变反向、不变双向)。类子类型落地后,变型关系在 Derived 与
Base 的实参之间可观察;接口子类型见 §12。
与内建容器的关系(非显然)。List[T]/Set[T]/Dict[K, V]/Tuple[...]
不是这套模板机制的实例:它们是 ListType 等硬编码的结构化静态类型,
由 _resolve_container_type 按名字白名单特判。泛型 ADT 走
AdtTemplate/AdtType,两者不共用实现。运行时的 List 等也只是每种容器一个
无参数的 OortType(type_system.py),类型参数只存在于检查器抽象域。
未来若统一,属于类型系统重构,不在增量 A 范围内。
内建 Option / Result(增量 C)。semantics/core/prelude.py 用 AST 节点
构造 Option[out T] 与 Result[out T, out E];Compiler._run_input 与
compile_unit_details 在语义分析前注入(-t ast 不注入)。注入节点
synthetic=True,AST dump 跳过;declaration_origin="<core-prelude>" 固定
名义 origin,使跨模块的 Option[Int] 相等。检查器把预置构造器标为
from_prelude:模块导出过滤它们,用户重定义类型/构造器/顶层名报 prelude
诊断。运行时照常执行注入的 enum;模块环境仍含这些绑定,但静态导出过滤后
检查器不允许访问。
至此 OP 0022 的 A/B/C 全部落地;后续是对象模型与 FFI。
8. 完整模式匹配(OP 0023,2026-11-22)¶
语法:字面量(Int/Float/String/Bool,可带 -)、元组(()、(p1, p2);
(p) 是分组)、或模式 p1 | p2、守卫 pattern if cond => body。match 的
scrutinee 可为 enum、Bool、Int、Float、String 或 Tuple。
检查。_check_pattern 按期望类型递归:字面量要求类型精确一致;元组要求
TupleType 且元数相同;或模式各分支必须绑定相同的名字集合与双向可赋值的
类型;守卫在 arm 作用域内按 Bool 检查。每个 PatternResult 返回绑定、归一化
alternatives 与 failed。
嵌套穷尽性。归一化为 _NormPattern(wild / ctor / literal)。
_missing_witness 是 Maranget usefulness 的 witness 版本:
- 完整签名:ADT 构造器集合、
Bool的{true, false}、元组的单构造器; Int/Float/String 是无限域,字面量集合永不完整。 - 或模式在 alternatives 中展开为矩阵多行;守卫 arm 不入矩阵(守卫可能为假, 与 OCaml/Scala 的保守处理一致)。
- 矩阵含全 wild 行时直接视为覆盖;这也是递归 ADT 上搜索的终止条件。
- 缺失时报告 witness:
Some(false)、(false, _)、_。
后端。HIR Pattern 增加 literal_*/tuple/or 与 value;MatchArm 增加
guard_index(守卫编译为独立函数,参数为 pattern 绑定)。.obc 写出 v2
(字面量值 + guard 字段),读取仍兼容 v1。VM 逐 arm 匹配;守卫失败继续下一个
arm(不回溯或模式其他分支);解释器同语义。决策树编译(Maranget 2008)留作
独立性能切片,当前使用顺序匹配。
9. 相等(OP 0024,2026-11-22)¶
- ADT:结构值相等(同 enum 类型名、同构造器、载荷递归值相等);键语义按
OortADT.__eq__/__hash__(Bool/Int 严格、Int/Float 键不同)实现,值语义由values_equal单独实现。 - 静态类实例:身份相等(Object 的默认
==/哈希),可用于容器与键。 - checker 前置:
_supports_value_equality递归允许 ADT/类并拒绝函数载荷;_is_valid_key_type对 ADT 递归检查 key-safe 载荷;同类型要求由_check_equality校验。 - 跨模块预置
Option按 enum 类型名比较,checked 代码不会混淆同名用户 enum。
10. 跨模块类型(OP 0025 增量 A,2026-11-22)¶
目标:值导出之外增加类型导出,使导入模块的类/enum 能出现在标注中, 同时不引入运行时类型值或“类型导入擦除”机制。
类型导出快照。ModuleType 与 CoreModuleInfo 增加
type_exports: tuple[(name, Type | AdtTemplate), ...](与值 exports 分开,
get_type 查询)。visit_module 在检查结束时只快照本模块声明的
ClassType 与 AdtTemplate:预置 Option/Result 被过滤,导入的类型不
再导出。CompiledUnit 携带同一快照,供 ModuleResolver 返回。
导入绑定。
import "m" as m的值绑定是ModuleType;在类型标注里,m.C/m.E查type_exports,值位置仍查值导出。from "m" import C(类)先declare构造器值,成功后再把同一ClassType写入检查器的imported_types;resolve_annotation(Name)查这张表,因此类导入在值与类型两个位置同名可用。from "m" import E(enum 类型名)只有类型导出:报'E' is a type-only export; use 'm.E' to name the type.,不建立值绑定。- 类型空间冲突(本地类/enum、保留名、重复导入类型)在检查期报错;导入类型
不会进入
self.classes/self.enums,避免污染本地名义表。
类型解析。resolve_annotation 新增 Attribute 分支
(_resolve_qualified_type)与 imported_types 分支;
_resolve_container_type 的基类型接受 m.E,把导出的 AdtTemplate
交给统一的 _apply_type_arguments(实参数目、泛型 payload 代换仍复用
OP 0022 的路径);非泛型类型加实参、值导出当类型、缺失类型都有专用诊断。
擦除边界。类型标注不进入 HIR/字节码,m.Type 从不在运行时求值;
普通 import 仍是值导入,from enum 类型名在检查期即被拒绝。因此后端零改动,
.obc 格式不变。
与对象模型的关系。这是 OP 0025 的 A 增量;单继承(bases、子类型、
super、函数参数逆变)是 B 增量(见 §11),接口见 §12,访问器仍留后续。
11. 单继承(OP 0025 增量 B,2026-11-22)¶
类型模型。ClassType 增加 bases: tuple[ClassType, ...](本切片至多一个)、
mro() 迭代祖先链、slot()/method() 沿链查找(方法覆盖由派生类优先)、
all_slots() 基类优先。名义相等仍按 (origin, name);is_subclass_of 按
祖先链。is_assignable(Base, Derived)、join_types 取最近公共基类;函数参数
同时改为逆变(有子类型后 (Derived)->R 不能赋给 (Base)->R)。
检查顺序。基类在注册新类之前解析,因此自继承/前向基类得到
Unknown type;基类必须是 ClassType(enum/集合/标量给专用诊断)。槽在
派生类中禁止重声明且不得与继承方法同名;方法不得与继承槽同名。
覆盖。方法覆盖要求参数元组精确相同;返回允许协变
(is_assignable(base_ret, derived_ret))。覆盖检查在方法返回推断完成后运行,
因此未标注返回的派生方法也参与比较。
构造与确定赋值。基类槽先按运行时 MRO 执行初始化器;派生类 __init__ 的
SlotFact 同时包含继承槽(from_base=True)和自身槽。继承槽若没有初始化器,
必须由 this.slot = ... 或 super.__init__(...) 覆盖;分析器把
super.__init__ 调用视为对所有基类未初始化槽赋值(重复调用对只读槽报错)。
无 __init__ 的派生类要求继承槽都有初始化器,且禁止继承带参数的构造器
(运行时 Class() 会沿 MRO 调用该构造器,静态构造签名必须一致)。
super。检查器在 visit_attribute 中识别 super.attr 的 AST 形态,
不构造新的静态值类型:super.method 查基类方法签名,super.__init__ 只在
子类 __init__ 中合法并按基类 __init__ 签名检查;slot 访问、无基类、缺方法
都有专用诊断。HIR/VM 的 SUPER 与运行时 MRO 无需改动。
与对象模型其余部分。多继承、属性访问器仍显式拒绝;接口见 §12;类实例 身份相等和键语义不变。
12. 静态接口(OP 0026,2026-11-22)¶
范围:只有方法签名、没有状态/构造器/方法体的名义接口;类通过
class C < Base, I1, I2 实现,接口通过 interface J < I1, I2 继承。
类型模型。新增 InterfaceType(origin, name, interfaces, methods):
interface_closure() 做带访问集合的深度优先遍历,extends_interface/
method/all_methods 沿父接口查找并合并同签名方法。ClassType.interfaces
记录直接实现;implements_interface 沿类的 mro() 检查每一层的直接接口,
因此基类实现会被派生类继承。is_assignable(Interface, Class) 与
is_assignable(Interface, Interface) 分别按实现/继承判断;反向
Class ← Interface 为假。接口不参与 join_types 的 LUB(多个共同接口时
选择不确定)。
声明与实现检查。接口名共享类型命名空间;接口基项必须是接口,父接口的
同名方法签名冲突在接口声明处报错。类的 base 列表先解析类型种类:至多一个
ClassType 且必须在首位,其余 InterfaceType;重复接口、非类非接口项、
类基项位置错误均有专用诊断。类实现接口的全部方法(含父接口要求):参数元组
精确一致,返回协变;缺方法/签名不符定位到接口与方法名。接口不进入类 MRO,
super 语义不变。
擦除。检查器在接口 base 表达式上写 metadata["interface_base"];
HIR 降低与 eval 解释器都跳过这些项。接口声明在 HIR 中不产生指令,解释器
执行时直接返回 null。接口类型标注不进入 HIR/字节码,.obc 不变。
模块。接口加入 OP 0025 的类型导出快照;m.I 可用于标注/基类;
from "m" import I 与 enum 类型名一样被拒绝(type-only 导出)。接口类型
可出现在参数/变量/返回值/槽/集合/ADT 载荷;接口值运行时仍是类实例,按
身份相等/作键,print 仍拒绝类实例。
13. 边界与后续¶
- 决策树编译 / 对象模型 / FFI 边界:OP 0005/0023 后续切片,建立在本文的 双向检查 + 局部推断基线上。
- 方法依赖扫描的保守性:按属性名匹配同类方法(不看 receiver 类型),可能给 「调用其他类同名方法」多加一条依赖约束——只会更保守(偶尔多要求标注),不会 不健全。精确化需 receiver 类型信息,留作后续。
- 全程序 HM:design 03 Phase-2 可选扩展,当前不做。