查询求值模型的详细介绍

本章将更深入地探讨建立在查询上的抽象模型。它不涉及实现细节，而是尝试解释底层逻辑。因此，这里的示例已经精简和简化，没有直接反映出编译器的内部API。

查询是什么

抽象地，我们将编译器关于给定crate的知识视为“数据库”，而查询是向编译器询问有关该问题的方式，即我们“查询”编译器的“数据库”以获取事实。

但是，此编译器数据库有一些特殊之处：它开始为空，并在执行查询时按需填充。因此，如果数据库尚不包含查询，则查询必须知道如何计算其结果。为此，它可以访问创建数据库时预先填充的其他查询和某些输入值。

因此，查询包含以下内容：

标识查询的名称
一个“键”，指定我们要查找的内容
一种结果类型，用于指定产生什么样的结果
一个 "provider"，它是一个函数，用于指定如果数据库中尚不存在结果，该如何计算结果。

例如，type_of查询的名称为type_of，其查询键为DefId，用于标识我们要了解其类型的项目，结果类型为Ty<'tcx>，并且provider是一个函数，只要向其提供查询键，它就能访问数据库其余部分，计算出该键标识的项的类型。

因此，从某种意义上说，查询只是将查询关键字映射到相应结果的函数。但是，为了使其听起来合理，我们必须应用一些限制：

键和结果必须是不可变的值。
provider函数必须是纯函数，即对于相同的键，它必须始终产生相同的结果。
provider函数的参数是键和对“查询上下文”的引用（提供对“数据库”其余部分的访问）。

该数据库是通过“懒惰地”调用查询构建的。 provider将调用其他查询，其结果或者已被缓存或者要通过调用另一个provider进行计算。这些provider调用从概念上形成有向无环图（DAG），在其叶上是创建查询上下文时已知的输入值。

缓存/记忆化

查询调用的结果是“记忆化”的，这意味着查询上下文会将结果缓存在内部表中，并且当再次使用相同的查询键调用查询时，将从缓存中返回结果，而不是再次运行provider。

这种缓存对于提高查询引擎的效率至关重要。没有记忆化，系统将仍然是健全的（也就是说，它将产生相同的结果），但是相同的计算将一遍又一遍地进行。

记忆化是查询提供程序必须为纯函数的主要原因之一。如果调用提供程序函数可能对每个调用产生不同的结果（因为它访问某些全局可变状态），则我们将无法记住结果。

输入数据

当查询上下文刚刚被创建出来时，它是空的：未执行任何查询，也不可能缓存任何结果。但是上下文已经提供了对“输入”数据的访问权限，即在创建上下文之前计算的不可变数据段，并且查询可以访问以执行其计算。当前，此输入数据主要由HIR map，上游crate元数据和调用编译器的命令行选项组成。将来，输入将仅包含命令行选项和源文件列表——HIR map本身将由处理这些源文件的查询提供。

没有输入，查询就没有任何用处，没有任何东西可以计算结果（请记住，查询provider只能访问其他查询和上下文，而不能访问任何其他外部状态或信息）。

对于查询provider，输入数据和其他查询的结果看起来完全相同：它只是告诉上下文“给我X的值”。因为输入数据是不可变的，所以提供者可以在不同的查询调用之间依赖于输入数据，就像查询结果一样。

一些查询的执行过程示例

这个查询调用DAG是如何形成的？在某个时候，编译器驱动程序将创建暂时为空的查询上下文。然后，它将从查询系统外部调用执行其任务所需的查询。看起来类似于以下内容：

fn compile_crate() {
    let cli_options = ...;
    let hir_map = ...;

    // Create the query context `tcx`
    let tcx = TyCtxt::new(cli_options, hir_map);

    // Do type checking by invoking the type check query
    tcx.type_check_crate();
}

type_check_crate 查询 provider 看起来像这样：

fn type_check_crate_provider(tcx, _key: ()) {
    let list_of_hir_items = tcx.hir_map.list_of_items();

    for item_def_id in list_of_hir_items {
        tcx.type_check_item(item_def_id);
    }
}

我们看到，type_check_crate查询访问输入数据（tcx.hir_map.list_of_items()）并调用其他查询（ type_check_item）。 type_check_item调用本身将访问输入数据和/或调用其他查询，因此最后，查询调用的DAG将从最初执行的节点向后构建：

         (2)                                                 (1)
  list_of_all_hir_items <----------------------------- type_check_crate()
                                                               |
    (5)             (4)                  (3)                   |
  Hir(foo) <--- type_of(foo) <--- type_check_item(foo) <-------+
                                      |                        |
                    +-----------------+                        |
                    |                                          |
    (7)             v  (6)                  (8)                |
  Hir(bar) <--- type_of(bar) <--- type_check_item(bar) <-------+

// (x) denotes invocation order

我们还看到通常可以从缓存中读取查询结果：type_check_item(foo)调用时已经计算出了type_of(bar)，因此当type_check_item(bar)需要它时，它已经在缓存中了。

只要上下文存在，查询结果就会保留在查询上下文中。因此，如果编译器驱动程序稍后调用另一个查询，则上面的图将仍然存在，并且已经执行的查询将不必重新执行。

环

前面我们曾说过，查询调用构成了DAG。但是，类似如下查询的provider很容易导致形成有环图：

fn cyclic_query_provider(tcx, key) -> u32 {
  // Invoke the same query with the same key again
  tcx.cyclic_query(key)
}

由于查询provider是常规函数，因此其行为将与预期的一样：求值将陷入无限递归中。这样的查询也不可能会有用。但是，有时某些类型的无效用户输入可能导致以循环方式调用查询。查询引擎包括对循环调用的检查，并且由于循环是不可恢复的错误，因此将中止执行，并显示尽可能可读的“cycle error”消息。

"窃取" 查询

一些查询的结果包装在Steal<T>结构中。这些查询的行为与常规查询完全相同，但有一个例外：它们的结果有时是从缓存中“窃取”来的，这意味着程序的其他部分正在拥有该所有权，并且该结果无法再访问。

这种窃取机制纯粹是作为性能优化而存在的，因为某些结果值的克隆成本太高（例如，函数的MIR）。结果窃取似乎违反了查询结果必须是不可变的条件（毕竟，我们将结果值移出了缓存），但是只要无法观察到该突变就可以。这可以通过两件事来实现：

在结果被窃取之前，我们确保eager地运行所有可能需要读取该结果的查询。必须通过手动调用这些查询来完成此操作。
每当查询尝试访问被窃取的结果时，我们都会使编译器ICE，以使这种情况不会被忽略。

由于需要手动干预，因此这不是理想的工作方式，因此应谨慎使用它，并且仅在众所周知哪些查询可以访问给定结果的情况下使用。然而，实际上，窃取并没有成为很大的维护负担。

总结一下：“窃取查询”以受控方式破坏了一些规则。但是有检查确保不会悄悄地出错。

查询的并行执行

查询模型具有一些属性，这些属性使得并行求值多个查询实际上可行，而无需花费太多精力：

查询provider可以访问的所有数据都是通过查询上下文访问的，因此查询上下文可以确保同步访问。
查询结果必须是不可变的，以便不同线程可以同时安全地使用它们。

nightly编译器已经实现了并行查询求值，如下所示：

当求值查询foo时，foo的缓存表被锁定。

如果已经有结果，我们可以克隆它，释放锁，然后就这样完成了查询。
如果没有缓存条目并且没有其他活动中的查询调用正在计算这一结果，则将该键标记为“进行中”，释放锁并开始求值。
如果正在对同一个键进行另一个查询调用，我们将释放锁，并阻塞线程，直到另一个调用计算出我们正在等待的结果。这不会造成死锁，因为如前所述，查询调用形成了DAG。总会有一些线程可以进展。

Guide to Rustc Development