Skip to content

Fire Code

[译]通过例子学子类型推理(三):类型检查器前端

上周,我们介绍了 cubiml 类型检查器前端背后的高级理论,也就是类型检查器负责将抽象语法树翻译成双合一类型和约束的部分。今天我们就来介绍一下前端的实际实现。

错误处理

上一次,我们看到类型检查器核心如果检测到程序中的错误,会返回一个 TypeError。然而,在某些情况下,编译器需要返回一个与类型无关的错误,例如对未定义变量的引用。你可能想在一个不同的过程中处理这些情况,但是为了保持 cubiml 初始版本的简单性,我们将在类型检查器前端一个单独的过程中处理这些情况。因此,我们首先为语法错误定义一个新的错误类型。

#[derive(Debug)]
pub struct SyntaxError(String);
impl fmt::Display for SyntaxError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str(&self.0)
    }
}
impl error::Error for SyntaxError {}

不幸的是,Rust 中的错误类型需要相当多的模板,但你几乎可以忽略所有这些代码。它所做的只是定义了一个新的错误类型,名为 SyntaxError,它接收并打印字符串错误信息。

更新: 一个有帮助的读者叫我注意 thiserror 库,它大大减少了定义这种基本错误类型所需的模板。还有一个库,anyhow,它提供了一个我们下面定义的 Result<T, Box<dyn error::Error>> 的等价预定义。

前端既可以返回 SyntaxError,也可以返回 TypeError,所以我们需要一个包括这两种类型的返回类型。简单起见,我们使用 Box<dyn error::Error>,它只是一个虚拟指针,指向实现错误接口的任何对象,就像你在 Java、Go 等中做的那样。在 Rust 中组合多个错误类型的“正确”方法是通过定义一个包含每个错误类型成员的枚举(sum 类型),但这样做需要大量的模板。

type Result<T> = std::result::Result<T, Box<dyn error::Error>>;

Result<T, E> 是 Rust 中用于成功时返回 T 或失败时返回错误 E 的函数的类型。由于将在整个文件中使用 Box<dyn error::Error> 作为错误类型,我们定义了一个类型别名,因此可以只说 Result<T> 而不是到处说 Result<T, Box<dyn error::Error>

绑定

接下来,当遍历抽象语法树时,有一个类来跟踪当前作用域中可见变量绑定的推断类型。

struct Bindings {
    m: HashMap<String, Value>,
}
impl Bindings {
    fn new() -> Self {
        Self { m: HashMap::new() }
    }

    fn get(&self, k: &str) -> Option<Value> {
        self.m.get(k).copied()
    }

    fn insert(&mut self, k: String, v: Value) {
        self.m.insert(k.clone(), v);
    }
}

回顾一下,Value 是核心中定义的类型,用来表示程序表达式类型的 cubiml 类型节点。因此 HashMap<String, Value> 只是一个哈希表,它将一个类型(Value)关联到每个变量名(String)。我们的 Bindings 类封装了这个哈希表,并提供了 getinsert 方法分别用于查找变量和设置新的变量绑定。这个包装器现在看起来可能毫无意义,但以后会证明它是有用的。

impl Bindings {
    fn in_child_scope<T>(&mut self, cb: impl FnOnce(&mut Self) -> T) -> T {
        let mut child_scope = Bindings { m: self.m.clone() };
        cb(&mut child_scope)
    }
}

有个方法值得特别一提:in_child_scope。它用于处理下降到一个新作用域,这个新作用域是当前作用域的子作用域,并将一个在子作用域中执行的回调作为参数。在子作用域中,父作用域的所有绑定都是可见的,除非在子作用域中被遮蔽,但是在子作用域中定义的绑定在父作用域中是不可见的。因此,我们需要复制内部的哈希映射以防止变化影响父作用域。现在,只需要创建一个带有当前哈希映射副本的临时的新 Bindings 实例,将其传递给回调,然后返回调用回调的结果。

表达式检查

助手类说完了,现在是前端的主要功能 check_expr 的时候了。

fn check_expr(engine: &mut TypeCheckerCore, bindings: &mut Bindings, expr: &ast::Expr) -> Result<Value> {
    use ast::Expr::*;
    match expr {

这个函数接收类型检查器核心的实例、上面定义的绑定类和要处理的 AST 表达式节点,并返回表达式的推断类型(如果适用,则返回语法或类型错误)。我们首先对 expr 进行匹配。回想一下,ast::Expr 是个枚举,具有语言语法中每种表达式的成员(函数定义、函数调用、记录、字段访问、let 绑定等),所以我们需要提供代码来处理每一个成员,并推断该种表达式的类型。

回忆一下,TypeCheckerCore 有如下接口。

impl TypeCheckerCore {
    pub fn var(&mut self) -> (Value, Use);

    pub fn bool(&mut self) -> Value;
    pub fn bool_use(&mut self) -> Use;

    pub fn func(&mut self, arg: Use, ret: Value) -> Value;
    pub fn func_use(&mut self, arg: Value, ret: Use) -> Use;

    pub fn obj(&mut self, fields: Vec<(String, Value)>) -> Value;
    pub fn obj_use(&mut self, field: (String, Use)) -> Use;

    pub fn case(&mut self, case: (String, Value)) -> Value;
    pub fn case_use(&mut self, cases: Vec<(String, Use)>) -> Use;

    pub fn flow(&mut self, lhs: Value, rhs: Use) -> Result<(), TypeError>;
}

核心的大部分方法都是用来构造类型的。对于每一种类型,布尔、函数、记录(这里对象称为 obj)和 case 型,都有一对相应的构造方法来创建该类型的值型和用型。var 方法创建了一个类型变量,用于表示程序流的中间状态。最后是 flow 方法,它在刚才构造的类型节点之间创建子类型约束。flow 接收值类型用类型,表示该值跟随用的约束,因此必须与该用法兼容。如果传递的类型不兼容,它将返回类型错误,成功后不返回任何内容。

我们先从最简单的 check_expr case 开始 - 变量和字面量。

变量和字面量

Literal(val) => {
    use ast::Literal::*;
    Ok(match val {
        Bool(_) => engine.bool(),
    })
}
Variable(name) => bindings
    .get(name.as_str())
    .ok_or_else(|| SyntaxError(format!("Undefined variable {}", name)).into()),

字面量 case 只匹配字面量的种类,并返回相应的类型。目前只有一种类型的字面量 - 布尔。为了创建布尔值类型,我们在类型检查器核心实例上调用 bool 方法,这里以变量 engine 的形式传递,以避免与定义了类 TypeCheckerCore模块 core 混淆。

变量 case 只在当前作用域的绑定中查找变量名称,并返回相关的类型,如果该名称在当前可见的绑定中没有定义,则返回“未定义变量”语法错误。

记录和 case 字面量

Record(fields) => {
    let mut field_names = HashSet::with_capacity(fields.len());
    let mut field_type_pairs = Vec::with_capacity(fields.len());
    for (name, expr) in fields {
        if !field_names.insert(&*name) {
            return Err(SyntaxError(format!("Repeated field name {}", name)).into());
        }

        let t = check_expr(engine, bindings, expr)?;
        field_type_pairs.push((name.clone(), t));
    }
    Ok(engine.obj(field_type_pairs))
}
Case(tag, val_expr) => {
    let val_type = check_expr(engine, bindings, val_expr)?;
    Ok(engine.case((tag.clone(), val_type)))
}

记录字面量表达式定义了一个新的对象,将任何数量的子表达式包装成字段。AST 中的每个记录节点都包含一个 Vec(列表),其中包含(name,expr)对,为其每个字段指定了名称和表达式节点。同样,为了创建记录值类型,需要收集(名称,值类型)对的列表来传递给记录类型构造器方法。

记录 case 的逻辑很简单:对于每个字段,调用子表达式的 check_expr 来获取它的类型,然后将得到的(名称,类型)对列表传给 engine.obj() 来创建一个记录类型并返回。我们还维护了一组以前见过的字段名,所以可以检测某个字段名是否重复,并在这种情况下返回语法错误。

case 字面量的逻辑非常相似,不同之处在于它甚至更简单,因为 case 字面量表达式仅包装单个表达式。

If 表达式

If(cond_expr, then_expr, else_expr) => {
    let cond_type = check_expr(engine, bindings, cond_expr)?;
    let bound = engine.bool_use();
    engine.flow(cond_type, bound)?;

    let then_type = check_expr(engine, bindings, then_expr)?;
    let else_type = check_expr(engine, bindings, else_expr)?;

    let (merged, merged_bound) = engine.var();
    engine.flow(then_type, merged_bound)?;
    engine.flow(else_type, merged_bound)?;
    Ok(merged)
}

if 表达式节点有三个子表达式:条件、then 分支和 else 分支。首先,我们要求条件必须是布尔类型。要做到这一点,我们首先像之前一样对子表达式调用 check_expr 来获取它的类型。然后调用 engine.bool_use() 来创建一个布尔用类型,再调用 engine.flow() 表示条件的类型跟随布尔用法。

假设这样就可以了,现在来处理分支。在运行时,if 表达式会求值到其中一个分支子表达式的值,但并不确定是哪个。因此,从某种意义上说,if 表达式的类型可能是其任何分支子表达式的类型。然而,我们只能推断出每个表达式的单一类型,所以需要一种方法来合并或联合子表达式的类型。

在双合一中,联合值类型不是显式表示的。相反,它们隐含在流图中。为了做到这一点,我们使用 engine.var() 创建一个中间的类型变量节点,添加从每个子表达式的类型到变量的流边缘,然后将变量作为整个 if 表达式的类型返回。由于流转关系是可传递的,所以 if 表达式类型流向的任何用法也会有每个子表达式的类型流向它,从而保证了所需的约束。

字段访问

FieldAccess(lhs_expr, name) => {
    let lhs_type = check_expr(engine, bindings, lhs_expr)?;

    let (field_type, field_bound) = engine.var();
    let bound = engine.obj_use((name.clone(), field_bound));
    engine.flow(lhs_type, bound)?;
    Ok(field_type)
}

字段访问逻辑是前面所有情况的一点组合。当你使用 a.foo 时,那就是 a 记录用法。与布尔用法不同,但就像记录值类型一样,记录用类型有一个子类型,特别是,子类型是一个(字段名、用类型)对。

棘手的是提供哪种类型给构造器作为字段的用类型。实际上,我们在这里使用了一个临时变量。回想一下,一个变量由两半组成,即用和值。假设新变量具有值 v 和用 u,我们正在处理表达式 a.foo,其中子表达式 a 具有类型 t

我们将列表 [("foo",u)] 传递给记录用法构造器方法 engine.obj_use(),创建记录用类型 {foo=u}。然后创建从 t{foo=u} 的流约束,返回 v 作为整个表达式 a.foo 的类型。因此,如果 a.foo 的类型 v 跟随某个用法 u',则 u' 所代表的约束将从 v 向后传播到 u,然后再传播到 t 的任何 foo 字段。

关于结构类型的子组件的额外流边是如何被添加的,具体的机制将在后面实现类型检查器核心的时候介绍。现在,只要知道每当记录值类型 {foo=v} 跟随记录用类型 {foo=u} 时,类型检查器就会插入一个从 vu 的流边,对于函数和 case 类型的子组件也是如此。

匹配表达式

Match(match_expr, cases) => {
    let match_type = check_expr(engine, bindings, match_expr)?;
    let (result_type, result_bound) = engine.var();

    let mut case_names = HashSet::with_capacity(cases.len());
    let mut case_type_pairs = Vec::with_capacity(cases.len());
    for ((tag, name), rhs_expr) in cases {
        if !case_names.insert(&*name) {
            return Err(SyntaxError(format!("Repeated match case {}", name)).into());
        }

        let (wrapped_type, wrapped_bound) = engine.var();
        case_type_pairs.push((tag.clone(), wrapped_bound));

        let rhs_type = bindings.in_child_scope(|bindings| {
            bindings.insert(name.clone(), wrapped_type);
            check_expr(engine, bindings, rhs_expr)
        })?;
        engine.flow(rhs_type, result_bound)?;
    }

    let bound = engine.case_use(case_type_pairs);
    engine.flow(match_type, bound)?;

    Ok(result_type)
}

这可能看起来很吓人,但实际上它与之前的情况很相似。主要区别是,我们现在还必须处理变量绑定和作用域。

回想一下,匹配表达式的样子是这样的:

let calculate_area = fun shape ->
    match shape with
          `Circle circle_val -> circle_val.rad *. circle_val.rad *. 3.1415926
        | `Rectangle rect_val -> rect_val.length *. rect_val.height

calculate_area `Circle {rad=6.7}
calculate_area `Rectangle {height=1.1; length=2.2}

这个匹配表达式有两个分支,分别用于 CircleRectangle 的情况。匹配表达式的每个分支由标签、变量名、->主体组成。主题是一个表达式,包含了当选择该匹配分支时将执行的代码,而该表达式的值就是匹配表达式整体在该情况下将求得的值。

最关键的是,在匹配分支的主体内,可以使用一个新的变量绑定,其名称是在分支的左侧给出的,其值等于原 case 对象所封装的值。例如,当我们调用 calculate_area `Circle {rad=6.7} 时,匹配表达式的 Circle 分支将被选择。这样就会在变量 circle_val 的值为 {rad=6.7} 的特殊作用域中执行表达式 circle_val.rad *. circle_val.rad *. 3.1415926。同样的,选择 Rectangle 分支会在包含变量 rect_val 的作用域中执行该分支的主体,以此类推。

let rhs_type = bindings.in_child_scope(|bindings| {
    bindings.insert(name.clone(), wrapped_type);
    check_expr(engine, bindings, rhs_expr)
})?;

为了实现变量作用域,我们使用 Bindingin_child_scope 方法,如前所述。因此,上面的代码调用了 in_child_scope,传递了在该作用域中执行的回调(上面缩进块中的所有内容)。在该作用域中,首先插入新的绑定,名称为 name,类型为 wrapped_type。由于 bindings.insert 的调用发生在回调的主体中,所以它看到了包含原始绑定映射副本的子作用域 Bindings 对象。由于插入是在绑定的副本上进行的,所以调用 in_child_scope 完成后,变化就会消失,不会影响父作用域中的绑定。

最后,回调在代表该匹配分支主体的表达式上递归调用 check_expr 并返回结果。结果被 bindings.in_child_scope() 本身返回,而产生的值类型被分配给变量 rhs_type

除了作用域技巧外,Match 处理器的代码和前面的情况类似,但还是有点复杂,所以我再一步一步地讲一遍。

let match_type = check_expr(engine, bindings, match_expr)?;

首先,我们得到输入到匹配表达式的子表达式的类型。这是运行时将被匹配的值,它的类型将跟随将在这里构建的巨大的 case 用类型。在下面的匹配示例中,子表达式将是 shape 变量。

match shape with
      `Circle circle_val -> circle_val.rad *. circle_val.rad *. 3.1415926
    | `Rectangle rect_val -> rect_val.length *. rect_val.height
let (result_type, result_bound) = engine.var();

接下来我们为匹配表达式的结果创建一个临时变量。result_type 将是整个匹配表达式的类型,而 result_bound 将是每个匹配分支的每个主题类型将跟随的用法。基本上,我们要取每个匹配分支类型的联合,就像前面的 if 表达式例子一样。

let mut case_names = HashSet::with_capacity(cases.len());
let mut case_type_pairs = Vec::with_capacity(cases.len());
for ((tag, name), rhs_expr) in cases {
    if !case_names.insert(&*name) {
        return Err(SyntaxError(format!("Repeated match case {}", name)).into());
    }

与前面的记录和 case 示例一样,核心的 case_usage 构造器方法接收了一个 (tag, usage) 对的列表。case_type_pairs 是将要创建的这些对的列表,而 case_names 是一个额外的集合,用于跟踪我们已经看到的标记,以便可以在匹配表达式中标记名称重复的情况下返回语法错误,就像之前处理记录字面量中重复字段名时一样。

let (wrapped_type, wrapped_bound) = engine.var();
case_type_pairs.push((tag.clone(), wrapped_bound));

对于每个分支,我们都会创建另一个临时变量 (wrapped_type,wrapped_bound)wrapped_bound 是添加到 (tag, usage) 对列表中的用,这些用将被传递给大的 case_usage 构造器,而 wrapped_type 则是相应的值类型,它代表了匹配分支主体进行类型检查时输入的包装值的类型。这与 a.foo 的例子类似,只是我们为每个匹配分支单独设置了一个变量,并且由此产生的值类型被传递给匹配分支的主体,而不是作为整个表达式的类型直接返回。

let rhs_type = bindings.in_child_scope(|bindings| {
    bindings.insert(name.clone(), wrapped_type);
    check_expr(engine, bindings, rhs_expr)
})?;
engine.flow(rhs_type, result_bound)?;

如前所述,我们在子作用域中推断主题的子表达式的类型,子作用域中存在一个名为 name 、类型为 wrapped_type 的变量。最后,我们从主题类型向结果变量添加一个流边。(记住,这就是我们将所有匹配分支的主体类型联合在一起的方式)。

let bound = engine.case_use(case_type_pairs);
engine.flow(match_type, bound)?;
Ok(result_type)

最后,我们将创建的对列表传给 engine.case_use 来创建一个巨大的 case 用类型,并添加一个从输入类型到该用法的流约束。然后返回 result_type (所有匹配分支主题类型的联合)作为整个匹配表达式的类型。

噢! 幸运的是,如果你能够做到这一点,剩下的情况应该很简单。

函数定义和函数调用

FuncDef(arg_name, body_expr) => {
    let (arg_type, arg_bound) = engine.var();
    let body_type = bindings.in_child_scope(|bindings| {
        bindings.insert(arg_name.clone(), arg_type);
        check_expr(engine, bindings, body_expr)
    })?;
    Ok(engine.func(arg_bound, body_type))
}
Call(func_expr, arg_expr) => {
    let func_type = check_expr(engine, bindings, func_expr)?;
    let arg_type = check_expr(engine, bindings, arg_expr)?;

    let (ret_type, ret_bound) = engine.var();
    let bound = engine.func_use(arg_type, ret_bound);
    engine.flow(func_type, bound)?;
    Ok(ret_type)
}

如前所述,函数的处理方式与记录和 case 非常相似。但是,有一个转折 - 函数参数是逆变的,也就是说,函数值类型的参数类型是用类型,函数用类型的参数是值类型

对于函数定义,我们首先创建一个代表函数参数的临时变量 (arg_type,arg_bound)。然后,在一个子作用域内对函数体进行类型检查,该子作用域包含一个名为 arg_name 、类型为 arg_type 的绑定。最后,返回函数值类型 engine.func(arg_bound, body_type)

对于函数调用,我们首先用 check_expr 得到两个子表达式的类型。然后创建临时变量 (ret_type, ret_bound) 来表示函数调用的返回类型。最后,添加从 func_type 到用法 engine.func_use(arg_type, ret_bound) 的流约束,并返回 ret_type 作为整个调用表达式的类型。

Let 表达式

Let((name, var_expr), rest_expr) => {
    let var_type = check_expr(engine, bindings, var_expr)?;
    bindings.in_child_scope(|bindings| {
        bindings.insert(name.clone(), var_type);
        check_expr(engine, bindings, rest_expr)
    })
}

Let 表达式也很直接。我们只需要得到变量定义表达式的类型,然后在子作用域中对 let 表达式的主体进行类型检查,子作用域内使用结果类型定义该变量。

注: 这里介绍的类型检查算法使得 let 表达式具有单态性。我们将在后面的文章中介绍如何实现 let 多态性。如果你不熟悉 let 多态性,暂时不用担心。所有的一切都会及时解释。

Let rec 表达式 (单一定义)

递归的 let 表达式比较复杂,因为它们可以包含多个变量定义。因此,我们先来看看如何处理只包含一个变量定义的 let-rec。

LetRec(defs, rest_expr) => bindings.in_child_scope(|bindings| {
    let (ref name, ref expr) = defs[0]; // 目前只处理一个变量定义

    let (temp_type, temp_bound) = engine.var();
    bindings.insert(name.clone(), temp_type);

    let var_type = check_expr(engine, bindings, expr)?;
    engine.flow(var_type, temp_bound)?;

    check_expr(engine, bindings, rest_expr)
}),

带有单个变量的递归 let 表达式和常规 let 表达式一样,只是变量的定义可以看到自己的绑定。为了处理这个问题,我们创建一个临时类型变量,并在对 let 变量的定义进行类型检查将其添加到绑定中。一旦有了定义的类型,我们就添加从变量类型到创建的临时变量的流约束,从而确保它们是相同的。其余的处理(对主体进行类型检查)与之前的方法相同。

Let rec 表达式 (多重定义)

LetRec(defs, rest_expr) => bindings.in_child_scope(|bindings| {
    let mut temp_bounds = Vec::with_capacity(defs.len());
    for (name, _) in defs {
        let (temp_type, temp_bound) = engine.var();
        bindings.insert(name.clone(), temp_type);
        temp_bounds.push(temp_bound);
    }

    for ((_, expr), bound) in defs.iter().zip(temp_bounds) {
        let var_type = check_expr(engine, bindings, expr)?;
        engine.flow(var_type, bound)?;
    }

    check_expr(engine, bindings, rest_expr)
}),

递归 let 表达式的实际处理器代码与此类似,但由于需要处理多个变量而变得复杂。我们为 let rec 中定义的每个变量创建临时类型变量。然而,let rec 中的每个变量定义都能看到该 let rec 定义的每个其他变量。因此,需要在对任何一个变量定义进行类型检查之前,将所有临时变量插入到绑定中,因此,我们需要将临时变量的副本存储在列表中,以便以后插入流边来关闭循环。剩下的就直接了当了。

类型检查器前端的核心 check_expr 的实现就到此为止。(噢!)只剩下一些细节需要总结。

高效绑定

上面给出的 Bindings 实现有个问题 - 每次下降进入子作用域时都复制整个绑定映射是非常低效的。幸运的是,有更好的解决方案。

由于代码在任何给定的时间只访问单个作用域的绑定,所以起初需要复制绑定的唯一原因是为了防止在子作用域中所作的更改影响父作用域中的绑定。然而,有一种替代方法可以做到这一点 - 跟踪在子作用域中所作的更改,并在离开子作用域时撤销它们。

为了做到这一点,我们维护一个变化的栈。每当为映射中以前不存在的名称插入绑定时,我们都会记下该名称,以便在退出时将其删除。每当为映射中以前已经存在的名称插入绑定时,我们都会记下该名称和映射中被新插入的值覆盖的旧值,以便在退出时用该名称将旧值添加回映射中。方便的是,Rust 的哈希映射实现中的 insert 方法在插入一个已经存在于映射中的键时,会返回旧值,所以很容易做到这一点。

struct Bindings {
    m: HashMap<String, Value>,
    changes: Vec<(String, Option<Value>)>,
}
impl Bindings {
    fn new() -> Self {
        Self {
            m: HashMap::new(),
            changes: Vec::new(),
        }
    }

    fn get(&self, k: &str) -> Option<Value> {
        self.m.get(k).copied()
    }

    fn insert(&mut self, k: String, v: Value) {
        let old = self.m.insert(k.clone(), v);
        self.changes.push((k, old));
    }

    fn unwind(&mut self, n: usize) {
        while self.changes.len() > n {
            let (k, old) = self.changes.pop().unwrap();
            match old {
                Some(v) => self.m.insert(k, v),
                None => self.m.remove(&k),
            };
        }
    }

    fn in_child_scope<T>(&mut self, cb: impl FnOnce(&mut Self) -> T) -> T {
        let n = self.changes.len();
        let res = cb(self);
        self.unwind(n);
        res
    }
}

以上是 Bindings 的较快实现。我们在名为 changesVec (列表,这里用作栈)中跟踪变化。get 方法不变,而 insert 方法将插入的键和旧值(如果有的话)添加到变化栈中。

如上所述,新的 unwind 方法撤销了截至给定点的变化。最后,in_child_scope 方法现在记下进入时变化栈的大小,并在回调返回后、返回调用者前展开到该点。

检查顶层定义

check_expr 函数推断表达式的类型,但是 cubiml 也允许在代码顶层使用不是表达式的定义。回想一下,顶层定义可以是普通的表达式,也可以是没有主体(in <expr> 部分)的 letlet rec 定义。

fn check_toplevel(engine: &mut TypeCheckerCore, bindings: &mut Bindings, def: &ast::TopLevel) -> Result<()> {
    use ast::TopLevel::*;
    match def {
        Expr(expr) => {
            check_expr(engine, bindings, expr)?;
        }
        LetDef((name, var_expr)) => {
            let var_type = check_expr(engine, bindings, var_expr)?;
            bindings.insert(name.clone(), var_type);
        }
        LetRecDef(defs) => {
            let mut temp_bounds = Vec::with_capacity(defs.len());
            for (name, _) in defs {
                let (temp_type, temp_bound) = engine.var();
                bindings.insert(name.clone(), temp_type);
                temp_bounds.push(temp_bound);
            }

            for ((_, expr), bound) in defs.iter().zip(temp_bounds) {
                let var_type = check_expr(engine, bindings, expr)?;
                engine.flow(var_type, bound)?;
            }
        }
    };
    Ok(())
}

check_toplevel 基本上与之前看到的代码相同,除了在顶层定义中定义的变量会被添加到全局作用域中,而不是只在定义的主体中可见。因此,没有对 in_child_scope 的调用。

TypeckState

最后,我们有一个封装类 TypeckState,它封装了上面看到的所有代码,并为调用者提供了一个更方便的接口。

pub struct TypeckState {
    core: TypeCheckerCore,
    bindings: Bindings,
}
impl TypeckState {
    pub fn new() -> Self {
        Self {
            core: TypeCheckerCore::new(),
            bindings: Bindings::new(),
        }
    }

    pub fn check_script(&mut self, parsed: &[ast::TopLevel]) -> Result<()> {
        // 创建整个类型状态的临时副本,这样就可以在脚本包含错误时回滚所有的更改
        let mut temp = self.core.clone();

        for item in parsed {
            if let Err(e) = check_toplevel(&mut self.core, &mut self.bindings, item) {
                // 回滚对类型状态和绑定的更改
                std::mem::swap(&mut self.core, &mut temp);
                self.bindings.unwind(0);
                return Err(e);
            }
        }

        // 现在脚本类型检查成功了,将全局定义从变更回滚列表中删除,使其永久化
        self.bindings.changes.clear();
        Ok(())
    }
}

这里还有最后一个微妙的地方。当定义被输入到 REPL 中时,它们可能包含错误。包含错误的定义不会被实际执行,所以它们定义的任何全局变量都不应该被后续代码使用。因此,在类型检查开始之前,我们先把所有的状态复制一份,如果有错误就把所有的事情都撤销。

cubiml 类型检查器前端的实现到此结束。下周,我们将开始类型检查器核心的实现,这样你就能看到那些 engine.flow() 调用实际在底层做什么。