上周，我们介绍了 cubiml 类型检查器前端的实现，即类型检查器负责将抽象语法树转化为双合一类型和约束的部分。今天我们将介绍类型检查器核心，这部分负责实际创建这些类型和约束，并检查它们的一致性。

类型图

在深入实际代码之前，我们先对设计进行概述。

回忆一下， cubiml 的类型系统是极化的，即分为两种类型类，值类型和用类型。前者是针对程序值的类型，后者是针对值用的类型，也就是给定的表达式对其操作数的约束。

类型构造器

除了极化之外，我们还可以通过类型构造器来对类型进行分类。类型构造器允许你从较简单的类型中建立起复杂的类型。例如，如果你有类型 T 和 U，那么函数类型定义为 T -> U 的函数的类型构造器接收 T 作为参数并返回 U。

类型构造器可以认为是接收一些类型作为输入并返回新类型的函数。基础类型，如布尔，可以认为是不接收参数的类型构造器的结果。对于 cubiml 的初始版本，类型系统有四个类型构造器：布尔、函数、记录和 case 类型。布尔是基础类型，而函数构造器有两个参数 - 参数类型和返回类型。记录和 case 构造器有两个参数 - 参数类型和返回类型。记录和 case 构造器接收组件类型的映射，分别对应每个字段或 case。

递归类型

传统上，类型被表示为一棵树，树上的每个节点代表一个类型构造器，每个子节点代表该类型构造器的参数，叶子节点是变量或基础类型，即没有参数的类型构造器。然而，在双合一中，类型被表示为图中的节点，图中可能包含循环，开启递归类型，或作为子组件引用到自己的类型。

显式类型系统语法自然地映射到基于树的方法上，节点对应于解析过的类型语法本身的抽象语法树中的节点。这使得递归类型难以处理语法方面的问题，但幸运的是，我们暂时不用担心这个问题，因为反正我们没有任何引用到类型的语法。基于图的方法使得递归类型在处理实际算法的时候很轻松自然，尽管在语法上表示它们有困难。

在 cubiml 的表示中，类型图中的每个节点都包含了关于它是用哪个类型构造器（如果有的话）定义的信息，我们将其称为类型头。此外，头还可以存储指向图中其他节点的指针，代表该类型的子组件。

除了代表头->组件关系的节点之间的边之外，类型图还包含了另外一种类型的边，流约束。回想一下，流约束表示程序值跟随输入程序中的使用点，并施加了一个约束条件，即值类型必须与相应的用类型兼容。

变量类型

回顾一下，在双合一下，类型变量由一对类型表示 - 用类型和值类型。从概念上讲，用类型表示分配给该变量的类型，而值类型表示从变量中读取的类型。当然，我们需要确保分配给变量的类型与从该变量中读取的类型兼容（即一个子类型）。然而，有形式为 v <= u 的子类型约束（流关系），以及形式为 u <= v 的约束（变量完整性约束），导致子类型约束循环，使得类型检查无法确定。

在立方双合一中，我们通过不在类型图中显式表示变量完整性约束来解决这个问题。相反，它们是通过类型检查算法的行为来隐式维护的。该算法通过确保流关系的传递性来实现。对于每一个变量 (u1，v1)，以及每一个流向 u1 的值类型 v2 和每一个 v1 流向的用类型 u2，我们都会添加 v2 流向 u2 的约束条件。本质上，变量的行为就像类型图中的小隧道或虫洞。无论进入一端的是什么，都会从另一端出来。

注: 这不是唯一可能的解决方案。代数子类型化，引入双合一概念的论文，实际上采取的是相反的方法。在代数子类型化下，变量完整性约束（在论文中被混淆地称为流约束）在类型图中被显式表示，而我们所说的流约束并没有在类型图中显式表示，而是通过类型检查算法的行为隐式维护。不过，我们的方式，使算法更加简单易懂。

我们的方法的一个优点是，由于变量完整性约束是隐式表示的，所以变量表示本身可以折叠成图中的一个节点。我们不使用一对节点，而只使用一个节点，并从上下文中确定变量的哪“边”被引用。当变量节点出现在流约束左侧时，它被视为值类型，而出现在右侧时，它被视为用类型。

类型检查算法

说完这些，核心的类型检查算法出奇的简单。只有两部分 - 类型检查头节点（类型构造器），保持流关系的传递性，我们将在下一篇中介绍。类型检查头只是确保每一方使用相同的类型构造器，然后插入额外的流边来递归地确保相应的子组件类型也是兼容的。

例如，假设有函数值类型 T1 -> U1，流向函数用类型 T2 -> U2。因为两个头都是函数，所以这部分就可以检查出来。然后我们插入流边，说 U1 流向 U2，T2 流向 T1。这样就保证了函数定义的返回值流向调用方返回的值，调用方传递的参数流向函数定义中的参数。

现在来看一些代码

在进入真正的代码之前，还有一些错误处理样板要做。它定义了 TypeError 类型，当检测到类型错误时返回该类型，就像上一篇中定义的 SyntaxError 一样。

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

接下来，我们用类型来表示类型。从概念上讲，每个类型的表示只是图中指向节点的一个指针。然而，使用图指针是不方便的，所以我们只需将图中的每个节点存储在一个巨大的列表中，并使用进入该列表的索引作为“指针”。因此，我们定义内部类型 ID，代表对类型图中节点的引用，作为 usize 的别名，一个无符号整型。

type ID = usize;

#[derive(Copy, Clone, Debug)]
pub struct Value(ID);
#[derive(Copy, Clone, Debug)]
pub struct Use(ID);

为了帮助调用者（即类型检查器前端）预防 bug，我们将 ID 类型包装成两个新的类型，Value 和 Use，分别代表指向解释为值和用类型的节点的指针。在底层图中，节点只是节点，极性由上下文来维护，但我们用不同的类型来包装它们，以防调用者把它们混为一谈。这样就保证了前端看不到底层的整数，只有不透明的值可以传递。

类型头

接下来，头类型的定义，即类型构造器。前缀分别是 V 和 U，表示值和用，以避免命名冲突。

#[derive(Debug, Clone)]
enum VTypeHead {
    VBool,
    VFunc { arg: Use, ret: Value },
    VObj { fields: HashMap<String, Value> },
    VCase { case: (String, Value) },
}
#[derive(Debug, Clone)]
enum UTypeHead {
    UBool,
    UFunc { arg: Value, ret: Use },
    UObj { field: (String, Use) },
    UCase { cases: HashMap<String, Use> },
}

接下来， check_heads，这个函数用于检查头类型的兼容性。

fn check_heads(lhs: &VTypeHead, rhs: &UTypeHead, out: &mut Vec<(Value, Use)>) -> Result<(), TypeError> {

这个函数需要一些解释。每当值类型头流向用类型头时，check_heads 就会被调用，以确保这些类型是兼容的。这些分别作为 lhs 和 rhs 传递。其次，如果头不匹配，它可以返回 TypeError，所以 check_heads 的返回类型是 Result<()，TypeError>。

最后，头检查过程可以引入额外的流约束，如前所述。为了避免不必要的复制和分配，我们通过外部参数 out 而不是函数返回类型来返回新的流边。调用者需要传递指针到持有 (Value，Use) 对的列表，我们为每个需要创建的新流边向该列表追加一个条目。

use UTypeHead::*;
use VTypeHead::*;

match (lhs, rhs) {
    (&VBool, &UBool) => Ok(()),

接下来，我们在输入类型头上进行匹配，根据要处理的类型构造器做不同的事情。第一种情况是最简单的 - 当两边都是布尔型时，不需要进一步的操作。

(&VFunc { arg: arg1, ret: ret1 }, &UFunc { arg: arg2, ret: ret2 }) => {
    out.push((ret1, ret2));
    // 反转顺序，因为参数是逆变的
    out.push((arg2, arg1));
    Ok(())
}

在函数类型的情况下，我们增加从左返回类型到右返回类型，从右参数类型到左参数类型的流边约束。参数类型的流边是反向的，因为函数参数是逆变的。这听起来可能很吓人，但当你考虑到实际需要的关系时，它是有意义的。如前所述，我们需要确保函数定义的返回值流向调用方返回值，而调用方传递的参数流向函数定义中的参数。

(&VObj { fields: ref fields1 }, &UObj { field: (ref name, rhs2) }) => {
    // 检查访问的字段是否被定义
    match fields1.get(name) {
        Some(&lhs2) => {
            out.push((lhs2, rhs2));
            Ok(())
        }
        None => Err(TypeError(format!("Missing field {}", name))),
    }
}

对于记录类型，我们检查右侧访问的字段是否也存在于左侧代表的记录字面量中。如果是，我们在字段类型之间添加一个流边，否则返回 TypeError，因为我们试图访问一个不存在的字段。

(&VCase { case: (ref name, lhs2) }, &UCase { cases: ref cases2 }) => {
    // 检查是否处理了正确的 case
    match cases2.get(name) {
        Some(&rhs2) => {
            out.push((lhs2, rhs2));
            Ok(())
        }
        None => Err(TypeError(format!("Unhandled case {}", name))),
    }
}

Case 类型是记录类型的镜像，处理方式也类似。这次，我们要检查左侧定义的 case 标签是否出现在右面代表的匹配表达式所处理的 case 标签中。

        _ => Err(TypeError("Unexpected types".to_string())),
    }
}

最后，在所有其他情况下，返回 TypeError。如果到达这个分支，意味着两个头使用了不同的类型构造器。例如，可能左边是布尔类型，右边是函数调用。目前，我们只是返回一个通用的消息，并不是特别有用。我们将在以后的文章中介绍添加更好的错误信息。

类型图

#[derive(Debug, Clone)]
enum TypeNode {
    Var,
    Value(VTypeHead),
    Use(UTypeHead),
}

#[derive(Debug, Clone)]
pub struct TypeCheckerCore {
    r: reachability::Reachability,
    types: Vec<TypeNode>,
}

类型图的实现大多是直接的，除了一个细节。回顾一下，类型图可以有两种不同类型的边 - 流边和从类型头到其子组件类型的边。为了简化事情，跟踪流边被抽象成了单独的类，叫做 Reachability。我们将在下一篇文章中介绍它的实现，现在，你只需要知道它的公共接口：

impl Reachability {
    pub fn add_node(&mut self) -> ID;
    pub fn add_edge(&mut self, lhs: ID, rhs: ID, out: &mut Vec<(ID, ID)>);
}

Reachability 在内部维护了一个节点和边的图，以跟踪流关系。与之前一样，节点存储在列表中，所以我们可以使用 ID（无符号整型）作为节点的“指针”。TypeCheckerCore 本身维护了一个单独的节点和类型头边的图。为了避免为图的每一半跟踪单独的“指针” ID，我们保持两个列表 1:1 匹配的不变性，每个类型节点的结果都是在两个列表中相同位置的节点，所以我们可以在 TypeCheckerCore 和 Reachability 之间自由混合 ID。

添加流边可能会导致添加额外的流边，以保持传递性，所以 add_edge 方法会以一个列表作为额外参数，在这个列表中存储所有被添加的边，类似于上面 check_heads “返回”额外边的方式。

接下来是公共构造函数，都很直接。

impl TypeCheckerCore {
    pub fn new() -> Self {
        Self {
            r: Default::default(),
            types: Vec::new(),
        }
    }

    fn new_val(&mut self, val_type: VTypeHead) -> Value {
        let i = self.r.add_node();
        assert!(i == self.types.len());
        self.types.push(TypeNode::Value(val_type));
        Value(i)
    }

    fn new_use(&mut self, constraint: UTypeHead) -> Use {
        let i = self.r.add_node();
        assert!(i == self.types.len());
        self.types.push(TypeNode::Use(constraint));
        Use(i)
    }

    pub fn var(&mut self) -> (Value, Use) {
        let i = self.r.add_node();
        assert!(i == self.types.len());
        self.types.push(TypeNode::Var);
        (Value(i), Use(i))
    }

    pub fn bool(&mut self) -> Value {
        self.new_val(VTypeHead::VBool)
    }
    pub fn bool_use(&mut self) -> Use {
        self.new_use(UTypeHead::UBool)
    }

    pub fn func(&mut self, arg: Use, ret: Value) -> Value {
        self.new_val(VTypeHead::VFunc { arg, ret })
    }
    pub fn func_use(&mut self, arg: Value, ret: Use) -> Use {
        self.new_use(UTypeHead::UFunc { arg, ret })
    }

    pub fn obj(&mut self, fields: Vec<(String, Value)>) -> Value {
        let fields = fields.into_iter().collect();
        self.new_val(VTypeHead::VObj { fields })
    }
    pub fn obj_use(&mut self, field: (String, Use)) -> Use {
        self.new_use(UTypeHead::UObj { field })
    }

    pub fn case(&mut self, case: (String, Value)) -> Value {
        self.new_val(VTypeHead::VCase { case })
    }
    pub fn case_use(&mut self, cases: Vec<(String, Use)>) -> Use {
        let cases = cases.into_iter().collect();
        self.new_use(UTypeHead::UCase { cases })
    }
}

这里需要注意的是 let fields = fields.into_iter().collect(); 这一行，它将字段从 Vec 转换为 HashMap，因为 obj 方法接收（名称，类型）字段对列表，但类型头将字段存储为映射。同样，对于 case_use 方法也是如此。

最后，flow 方法，所有的神奇都发生在这里。

pub fn flow(&mut self, lhs: Value, rhs: Use) -> Result<(), TypeError> {
    let mut pending_edges = vec![(lhs, rhs)];
    let mut type_pairs_to_check = Vec::new();
    while let Some((lhs, rhs)) = pending_edges.pop() {
        self.r.add_edge(lhs.0, rhs.0, &mut type_pairs_to_check);

        // 检查添加该边是否导致任何新的类型对需要检查
        while let Some((lhs, rhs)) = type_pairs_to_check.pop() {
            if let TypeNode::Value(lhs_head) = &self.types[lhs] {
                if let TypeNode::Use(rhs_head) = &self.types[rhs] {
                    check_heads(lhs_head, rhs_head, &mut pending_edges)?;
                }
            }
        }
    }
    assert!(pending_edges.is_empty() && type_pairs_to_check.is_empty());
    Ok(())
}

这个方法本质上只是在循环中调用 add_edge 和 check_heads，直到收敛。为了添加一个流边，我们调用 add_edge，如果还没有的话，就添加这个边，以及保持流传递性所需的任何额外边。每当添加一条流边时，我们还需要检查这些节点头的一致性。然而，头检查过程本身可能需要添加新的流边。

因此，我们维护了两个工作列表。pending_edges 是需要在可到达性图中插入的流边列表。type_pairs_to_check 是已经添加的、仍然需要进行类型检查的边列表。最初，type_pairs_to_check 是空的，pending_edges 只包含单个对，作为 flow 方法的输入给出。

只要 pending_edges 非空，我们就从中弹出一项，并将其传递给 add_edge，后者可能会将对插入到 type_pairs_to_check。只要 type_pairs_to_check 非空，我们就从中弹出一项，检查每个末端是否是类型头，如果是，就在其上调用 check_heads，这可能会依次把对插入到 pending_edges 中。如果 check_heads 返回 TypeError，就停止并将错误返回给调用者(这就是最后那个小 ? 的作用)，否则，就继续循环，直到处理完所有的待处理工作。

现在我们已经涵盖了实现子类型推理所需的几乎所有代码。在下一篇中，我们将介绍最后一块拼图 - Reachability 的实现。