上周，我们介绍了 cubiml 类型检查器核心的实现，也就是类型检查器维护程序类型图、检查和传播类型约束的部分。然而，类型检查器核心中有一块，即流检查器，留下了。今天，我们将介绍 cubiml 类型推理算法的最后一块 - 流检查器的实现。

类型图

回想一下，在 cubiml 中，类型用指向可变的、可能是循环的图中的节点指针来表示。图中有两种可能的边类型。第一种是代表结构类型组件的边。例如，如果节点代表函数类型，它将有指向该函数的相应参数类型和返回类型的边。

第二种类型的边是流边，代表给定值类型的程序值流向给定用类型的用约束，因此值类型必须与该用类型兼容。此外，变量被表示为图中的中间节点，类型推理算法负责确保流转关系是传递的。

类型检查器核心分为两部分。第一部分在上周的文章中介绍，包括每个图节点所代表的类型信息，以及从类型构造器“头”到其组件类型的关系。今天介绍的第二部分，只负责跟踪流边和维护流边的传递性。它被封装在名为 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 ，因为它解决了*(定向)增量可达性问题*，一个关于图的通用问题，它要求你保持传递性，即对于所有的边 a ->b 和 b ->c，也有一条边 a ->c ，因为边是由外部源插入的。

天真算法

首先，我们将尝试用最简单的算法来解决增量可达性问题，不管速度如何。每当一条新边 A -> B 插入图中时，我们首先检查这条边是否已经存在（如果存在，那么显然不需要做什么）。如果插入了一条新边，我们可能需要插入额外的边来保持传递性。

具体来说，对于每个有边 C -> A 的节点 C，需要插入边 C -> B。同样，对于每个有边 B -> D 的节点 D，需要插入边 A -> D。最后，需要插入所有 C -> D 形式的边。为了做到这一点，需要一种方法来轻松地找到给定节点有边的所有节点（称为下集）和有边的到给定节点的所有节点，即上集。这就导致了一个相当简单的算法。

type ID = usize;
#[derive(Debug, Default, Clone)]
pub struct Reachability {
    upsets: Vec<HashSet<ID>>,
    downsets: Vec<HashSet<ID>>,
}

为了表示图的状态，只需将每个节点的上集和下集直接存储为 HashSet。upsets 和 downsets 字段存储了哈希集的列表，分别给出了每个节点的上集或下集的索引。

pub fn add_node(&mut self) -> ID {
    let i = self.upsets.len();

    let mut set = HashSet::with_capacity(1);
    set.insert(i);

    self.upsets.push(set.clone());
    self.downsets.push(set);
    i
}

add_node 的实现很简单 - 只需在每个列表中添加一个新的集合并返回新的索引。有一个小小的复杂之处。正如最初所说，有三种类型的边要添加：C -> B，A -> D，和 C -> D，其中 A -> B 是原始边，C 是 A 上集的任何成员，D 是 B 下集的任何成员。为了简化算法，我们把每个节点都存储在它自己的上集和下集中，因此我们只需要担心一种边，即 C -> D 边。

pub fn add_edge(&mut self, lhs: ID, rhs: ID, out: &mut Vec<(ID, ID)>) {
    if self.downsets[lhs].contains(&rhs) {
        return;
    }

    // 获取 lhs 的所有祖先，包括 lhs 本身
    let mut lhs_set: Vec<ID> = self.upsets[lhs].iter().cloned().collect();
    lhs_set.sort_unstable();

    // 获取 rhs 的所有后裔，包括 rhs 本身
    let mut rhs_set: Vec<ID> = self.downsets[rhs].iter().cloned().collect();
    rhs_set.sort_unstable();

    for &lhs2 in &lhs_set {
        for &rhs2 in &rhs_set {
            if self.downsets[lhs2].insert(rhs2) {
                self.upsets[rhs2].insert(lhs2);
                out.push((lhs2, rhs2));
            }
        }
    }
}

最后，add_edge 的实现。很简单 - 要插入边 lhs -> rhs，首先检查这个边是否已经存在。如果它不存在，就从 upsets[lhs] 的每个成员到 downsets[rhs] 的每个成员插入一个新边。

值得注意的是对 sort_unstable 的调用。Rust 的 HashSet 是随机排序的，这意味着如果在迭代之前不对集进行排序，就会以随机的顺序插入新的边，并以随机的顺序返回给调用者。这本身并不是不正确的，但它有一些不理想的效果。例如，如果输入程序恰好有多个类型错误，那么以随机顺序处理流边会导致检测到随机类型错误并报告给用户。同一编译器对同一代码的不同运行可能会有不同的结果，这显然是个坏主意。确保代码是确定性的，还有很多其他的好处，比如让代码更容易调试，确保更可预测的性能。

天真算法的复杂性

上面的代码是可行的，但速度慢、效率低。如果 n 是图中的节点数，那么每个上集和下集的大小可能达到 n，这意味着在上集和下集中迭代每个对的结果可达 n^2 对。因此，每个单独边插入的最坏情况复杂度为 O(n^2)。由于最多可以有 O(n^2) 条边，所以天真可达性算法的总体复杂度为 O(n^4)。

这与原代数子类型化论文中的去掉指数部分(let 多态和简化)的算法的 O(n^4) 复杂度相似。代数子类型化做了很多不同的事情，所以两者并不能直接比较，但是 O(n^4) 的缓慢来自于一个非常相似的问题。幸运的是，在立方双合一的情况下，加快类型检查算法的速度就像选择更快的可达性算法一样简单。

生成树算法

已发表的最快的增量可达性问题算法来自于一篇1986年的论文，其最坏情况下的复杂度为 O(n^3)，因此将“立方”放在了立方双合一中。这个算法要复杂得多，它涉及到将每个节点的下集表示为生成树，而不是普通的哈希集。尽管这篇论文已经发表了 34 年，但目前还没有更快的算法。事实上，似乎 O(n^3) 是这个问题的最佳可能，尽管证明复杂性的无条件下限是众所周知的困难。

cubiml 的最初版本使用了这种算法。然而，在编写本教程的过程中，我偶然发现了一个更好的算法，在一篇所有内容的指针别名分析论文中。(感谢 Reddit！) 当然这个算法仍然需要 O(n^3) 时间，但它比生成树算法简单得多，所以它是今天要使用和介绍的算法。(如果你好奇，你可以在这里看到生成树算法的原始实现)。

最终算法

这个算法与天真算法基本相同，只是没有插入所有的 C -> D 边，也就没有迭代每条边插入的 O(n^2) 对，而是只递归地插入 C -> B 和 A -> D 边。但在进入这个问题之前，我们要先定义一个辅助数据结构。

有序集

回想一下，Rust 的 HashSet 是随机排序的，所以为了保持天真算法中的确定性行为，我们在迭代之前对集合进行了排序。然而，有一个更好的解决方案。我们不只使用 HashSet，还维护一个集合和一个有序列表。每当插入一个元素时，就把它插入到集合并追加到列表中。每当需要对值进行迭代时，只需对列表进行迭代，而列表是确定有序的。(我们仍然需要这个集合，这样就可以在常数时间内检查值是否已经存在，但不再需要迭代这个集合)。

struct OrderedSet<T> {
    v: Vec<T>,
    s: HashSet<T>,
}
impl<T: Eq + std::hash::Hash + Clone> OrderedSet<T> {
    fn insert(&mut self, value: T) -> bool {
        if self.s.insert(value.clone()) {
            self.v.push(value);
            true
        } else {
            false
        }
    }

    fn iter(&self) -> std::slice::Iter<T> {
        self.v.iter()
    }
}

事实上，这个模式非常有用，我已经把它包装在上面的 OrderedSet 类中。这让我们可以在任何地方使用 OrderedSet 代替 HashSet，并获得确定性行为。

注: 许多语言都提供了开箱即用的有序集。例如，Java 有 LinkedHashSet。在 JavaScript 和 Python 3.6+ 中，原生的集合类型是自动有序的。由于需要处理集的删除，这些实现略有不同，再加上需要保持插入顺序，而不是任何任意的确定性顺序，这意味着使用的列表必须是链表，而不是数组列表（Vec）。使用链表具有相同的渐近复杂度，但在实际中要慢得多，即具有较高的常数因子，所以如果可以的话，最好避免这样做，如本例。

立方可达性

说完这些，实际算法出奇的简单。首先，Reachability 和 add_node 的定义与之前基本相同，只是不再将每个节点添加到它自己的上集和下集中。相反，上集和下集一开始是空的。(Default::default() 返回类型的默认值，在这种情况下是空集)。

pub struct Reachability {
    upsets: Vec<OrderedSet<ID>>,
    downsets: Vec<OrderedSet<ID>>,
}
impl Reachability {
    pub fn add_node(&mut self) -> ID {
        let i = self.upsets.len();
        self.upsets.push(Default::default());
        self.downsets.push(Default::default());
        i
    }
}

概念上，当插入边 A -> B 时，首先检查该边是否已经存在。如果没有，就插入它，然后检查上下集。对于 A 上集中的每个 C，递归调用 add_edge(C，B)。对于 B 下集中的每个 D，递归调用 add_edge(A，D)。它是如此简单，以至于用代码描述比用散文描述几乎更容易。

一个复杂的问题是，实际实现是迭代的，而不是递归的。我们没有实际递归地调用 add_edge，只是维护一个待插入边的栈，然后从栈中弹出项并处理它们，直到栈为空。

pub fn add_edge(&mut self, lhs: ID, rhs: ID, out: &mut Vec<(ID, ID)>) {
    let mut work = vec![(lhs, rhs)];

    while let Some((lhs, rhs)) = work.pop() {
        // 如果边已经存在，插入返回 false
        if !self.downsets[lhs].insert(rhs) {
            continue;
        }
        self.upsets[rhs].insert(lhs);
        // 通知调用者增加了一个新边
        out.push((lhs, rhs));

        for &lhs2 in self.upsets[lhs].iter() {
            work.push((lhs2, rhs));
        }
        for &rhs2 in self.downsets[rhs].iter() {
            work.push((lhs, rhs2));
        }
    }
}

就算法复杂度而言，每插入一个边，不管这个边是来自外部调用者还是我们自己的递归调用，我们都会迭代最大大小 O(n) 的 upsets[lhs] 和 downsets[rhs]。因此，每次边插入都要做 O(n) 的工作。由于最多存在 O(n^2) 条边，这导致 O(n^3) 的总体最坏情况复杂度，因此，这是立方双合一名字的由来。

代码生成

类型检查完成后，实现编译器剩下的唯一一步就是实际生成代码，这样输入的程序才能被执行。这很复杂、繁琐，而且与你所实现的特定编译器高度相关，我在这里就不赘述了，但你可以在这里和这里查看 cubiml 生成代码的初始版本。

我们现在已经经历了一个完整的例子，在一个最小编程语言中实现了立方双合一来检查类型。然而，现在这个语言还不是很有用。下周，我们将在该语言中添加整型、浮点型、字符串字面量和运算符。