第十一章：Contingent：一个完全动态的构建系统

• 作者简介
• 引言
• 问题：构建文档系统
• 构建系统和一致性
• 链接任务以构建图
• 类的正确使用
• 学习连接
• 追踪结果
• 结论

原文信息

• 本章翻译自 Contingent: A Fully Dynamic Build System
• 作者：Brandon Rhodes 和 Daniel Rocco
• 许可协议：Creative Commons Attribution 3.0 Unported

作者简介

Brandon Rhodes 从 20 世纪 90 年代末开始使用 Python，17 年来一直维护着面向业余天文学家的 PyEphem 库。他在 Dropbox 工作，曾为企业客户教授 Python 编程课程，参与了新英格兰野花协会的"Go Botany" Django 网站等项目的咨询工作，并将担任 2016 年和 2017 年 PyCon 大会的主席。Brandon 认为编写良好的代码是一种文学形式，格式优美的代码是平面设计作品，而正确的代码是最透明的思想形式之一。

Daniel Rocco 热爱 Python、咖啡、工艺、烈性黑啤酒、对象和系统设计、波旁威士忌、教学、树木和拉丁吉他。他很高兴能以编写 Python 为生，总是在寻找机会向社区中的其他人学习，并通过分享知识做出贡献。他经常在 PyAtl 上就入门主题、测试、设计和新鲜事物发表演讲；当有人分享新颖、令人惊讶或美丽的想法时，他喜欢看到人们眼中闪现的惊奇和喜悦。Daniel 与一位微生物学家和四位有抱负的火箭专家住在亚特兰大。

引言

构建系统长期以来一直是计算机编程的标准工具。

标准的 make 构建系统是在 1976 年首次开发的，其作者因此获得了 ACM 软件系统奖。它不仅允许你声明一个输出文件依赖于一个（或多个）输入，还允许你递归地执行此操作。例如，一个程序可能依赖于一个对象文件，而该对象文件本身依赖于相应的源代码：

prog: main.o
    cc -o prog main.o

main.o: main.c
    cc -C -o main.o main.c

如果 make 在下次调用时发现 main.c 源代码文件的修改时间比 main.o 更新，那么它不仅会重新构建 main.o 对象文件，还会重新构建 prog 本身。

构建系统是分配给计算机科学本科生的常见学期项目——不仅因为构建系统几乎在所有软件项目中都会使用，还因为它们的构造涉及关于有向图的基本数据结构和算法（本章稍后将更详细地讨论）。

有了数十年的使用和实践经验，人们可能会期望构建系统已经变得完全通用，并准备好应对最奢侈的需求。但事实上，构建工件之间的一种常见交互——动态交叉引用问题——被大多数构建系统处理得如此糟糕，以至于在本章中，我们不仅要复习用于解决 make 问题的经典解决方案和数据结构，还要将该解决方案大幅扩展到一个要求更高的领域。

问题，再次，就是交叉引用。交叉引用往往出现在哪里？在文本文档、文档和印刷书籍中！

问题：构建文档系统

从源文件重建格式化文档的系统似乎总是做太多工作，或者做得太少。

当它们对一个小的编辑做出响应，让你等待不相关的章节被重新解析和重新格式化时，它们做了太多工作。但它们也可能重建得太少，给你留下一个不一致的最终产品。

考虑 Sphinx，这个用于官方 Python 语言文档以及 Python 社区中许多其他项目的文档构建器。Sphinx 项目的 index.rst 通常会包含一个目录：

Table of Contents
=================

.. toctree::

   install.rst
   tutorial.rst
   api.rst

这个章节文件名列表告诉 Sphinx 在构建 index.html 输出文件时包含指向这三个命名章节的链接。它还将包含每个章节中任何小节的链接。去掉标记后，上述标题和 toctree 命令生成的文本可能是：

Table of Contents

  • Installation

  • Newcomers Tutorial
      • Hello, World
      • Adding Logging

  • API Reference
      • Handy Functions
      • Obscure Classes

正如你所看到的，这个目录是来自四个不同文件的信息的混搭。虽然它的基本顺序和结构来自 index.rst，但每个章节和小节的实际标题都是从三个章节源文件本身提取的。

如果你后来重新考虑了教程的章节标题——毕竟，"newcomer"这个词听起来很古怪，就好像你的用户是刚刚抵达拓荒者怀俄明州的定居者——那么你会编辑 tutorial.rst 的第一行并写一些更好的东西：

-Newcomers Tutorial
+Beginners Tutorial
 ==================

 Welcome to the tutorial!
 This text will take you through the basics of...

当你准备重建时，Sphinx 会做得恰到好处！它将重建教程章节本身和索引。（将输出管道传输到 cat 使 Sphinx 在单独的行上宣布每个重建的文件，而不是使用裸回车符重复覆盖单行的进度更新。）

$ make html | cat
writing output... [ 50%] index
writing output... [100%] tutorial

因为 Sphinx 选择重建这两个文档，不仅 tutorial.html 现在在顶部显示其新标题，而且输出的 index.html 将在目录中显示更新的章节标题。Sphinx 重建了所有内容，使输出保持一致。

如果你对 tutorial.rst 的编辑更次要呢？

Beginners Tutorial
==================

-Welcome to the tutorial!
+Welcome to our project tutorial!
 This text will take you through the basics of...

在这种情况下，不需要重建 index.html，因为段落内部的这个小编辑不会改变目录中的任何信息。但事实证明，Sphinx 并不像它最初看起来那么聪明！即使生成的内容完全相同，它仍会执行冗余的 index.html 重建工作。

writing output... [ 50%] index
writing output... [100%] tutorial

你可以在 index.html 的"之前"和"之后"版本上运行 diff 来确认你的小编辑对首页没有影响——然而 Sphinx 还是让你等待它被重建。

你可能甚至不会注意到小型文档的额外重建工作，因为它们很容易编译。但是，当你对长篇、复杂或涉及生成多媒体（如绘图或动画）的文档进行频繁调整和编辑时，对工作流的延迟可能会变得很严重。虽然 Sphinx 至少在努力不在你进行单个更改时重建每个章节——例如，它没有响应你的 tutorial.rst 编辑而重建 install.html 或 api.html——但它做的比必要的要多。

但事实证明，Sphinx 做了更糟糕的事情：它有时做得太少，给你留下了用户可能注意到的不一致输出。

要看到它最简单的失败之一，首先在你的 API 文档顶部添加一个交叉引用：

API Reference
=============

+Before reading this, try reading our :doc:`tutorial`!
+
 The sections below list every function
 and every single class and method offered...

考虑到目录的通常谨慎，Sphinx 将尽职尽责地重建这个 API 参考文档以及你项目的 index.html 主页：

writing output... [ 50%] api
writing output... [100%] index

在 api.html 输出文件中，你可以确认 Sphinx 已经将教程章节的具有吸引力的人类可读标题包含到交叉引用的锚标签中：

<p>Before reading this, try reading our
<a class="reference internal" href="tutorial.html">
  <em>Beginners Tutorial</em>
</a>!</p>

如果你现在对 tutorial.rst 文件顶部的标题进行另一次编辑会怎样？你将使 三个 输出文件失效：

1. tutorial.html 顶部的标题现在已过时，因此需要重建该文件。

2. index.html 中的目录仍然有旧标题，因此该文档需要重建。

3. api.html 第一段中的嵌入式交叉引用仍然有旧的章节标题，也需要重建。

Sphinx 会怎么做？

writing output... [ 50%] index
writing output... [100%] tutorial

哎呀。

只重建了两个文件，不是三个。Sphinx 未能正确重建你的文档。

如果你现在将 HTML 推送到网络上，用户将在 api.html 顶部的交叉引用中看到旧标题，但一旦链接将他们带到 tutorial.html 本身，他们就会看到不同的标题——新的标题。这可能发生在 Sphinx 支持的许多类型的交叉引用中：章节标题、小节标题、段落、类、方法和函数。

构建系统和一致性

上面概述的问题并不是 Sphinx 特有的。它不仅困扰其他文档系统（如 LaTeX），甚至可能困扰仅尝试使用经典的 make 实用程序来指导编译步骤的项目，如果它们的资源恰好以有趣的方式交叉引用的话。

由于这个问题是古老而普遍的，它的解决方案同样具有悠久的历史：

rm -r _build/
make html

如果你删除所有输出，你就能保证完全重建！有些项目甚至将 rm -r 别名为名为 clean 的目标，这样只需快速的 make clean 就能清除一切。

通过消除每个中间或输出资源的每个副本，一个庞大的 rm -r 能够强制构建从头开始，没有任何缓存——没有任何可能导致过时产品的早期状态的记忆。

但我们能开发一种更好的方法吗？

如果你的构建系统是一个持久化进程，它会注意到每个章节标题、每个小节标题以及每个交叉引用的短语从一个文档的源代码传递到另一个文档的文本中？那么它关于在单个源文件更改后是否重建其他文档的决策就可以是精确的，而不是仅仅猜测，并且是正确的，而不是让输出处于不一致的状态。

结果将是一个像旧的静态 make 工具一样的系统，但它会在构建文件时学习文件之间的依赖关系——随着交叉引用的添加、更新和删除，动态地添加和删除依赖关系。

在接下来的章节中，我们将用 Python 构建这样一个工具，名为 Contingent。Contingent 在存在动态依赖关系的情况下保证正确性，同时执行尽可能少的重建步骤。虽然它可以应用于任何问题领域，但我们将针对上面概述的问题的一个小版本运行它。

链接任务以构建图

任何构建系统都需要一种方式来链接输入和输出。例如，我们上面讨论中的三个标记文本，每个都会生成一个相应的 HTML 输出文件。表达这些关系的最自然方式是作为一个框和箭头的集合——或者用数学术语来说，节点和边——形成一个图（图 4.1）。

图 4.1 - 通过解析三个输入文本生成的三个文件

程序员可能用来处理编写构建系统的每种语言都会提供各种数据结构来表示这样的节点和边的图。

我们如何在 Python 中表示这样的图？

Python 语言通过在语言语法中直接支持四种通用数据结构，赋予它们优先权。你可以通过简单地将它们的字面表示输入到源代码中来创建这些四大数据结构的新实例，并且它们的四个类型对象可用作内置符号，无需导入即可使用。

**元组（tuple）**是一个只读序列，用于保存异构数据——元组中的每个槽通常意味着不同的东西。在这里，一个元组将主机名和端口号保持在一起，如果元素重新排序，它将失去意义：

('dropbox.com', 443)

**列表（list）**是一个可变序列，用于保存同质数据——每个项目通常与其同伴具有相同的结构和含义。列表可用于保留数据的原始输入顺序，或者可以重新排列或排序以建立新的、更有用的顺序。

['C', 'Awk', 'TCL', 'Python', 'JavaScript']

**集合（set）**不保留顺序。集合只记住给定值是否已被添加，而不记住添加了多少次，因此是从数据流中删除重复项的首选数据结构。例如，以下两个集合将各有三个元素：

{3, 4, 5}
{3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 5}

**字典（dict）**是一个关联数据结构，用于存储可通过键访问的值。字典让程序员选择索引每个值的键，而不是像元组和列表那样使用自动整数索引。查找由哈希表支持，这意味着无论字典有十几个还是一百万个键，字典键查找的运行速度都相同。

{'ssh': 22, 'telnet': 23, 'domain': 53, 'http': 80}

Python 灵活性的关键在于这四种数据结构是可组合的。程序员可以任意地将它们嵌套在彼此内部，以产生更复杂的数据存储，其规则和语法仍然是底层元组、列表、集合和字典的简单规则和语法。

鉴于我们的每个图边至少需要知道它的起始节点和目标节点，最简单的表示将是一个元组。图 4.1 中的顶部边可能看起来像：

('tutorial.rst', 'tutorial.html')

我们如何存储多个边？虽然我们最初的冲动可能只是将所有边元组放入一个列表中，但这会有缺点。列表会小心地维护顺序，但谈论图中边的绝对顺序是没有意义的。而且列表会很乐意保存完全相同的边的多个副本，即使我们只希望在 tutorial.rst 和 tutorial.html 之间画一条箭头。因此，正确的选择是集合，它会让我们将图 4.1 表示为：

{('tutorial.rst', 'tutorial.html'),
 ('index.rst', 'index.html'),
 ('api.rst', 'api.html')}

这将允许快速迭代所有边，对单个边进行快速插入和删除操作，以及快速检查特定边是否存在的方法。

不幸的是，这些并不是我们需要的唯一操作。

像 Contingent 这样的构建系统需要理解给定节点与连接到它的所有节点之间的关系。例如，当 Contingent 构建博客时，当 api.rst 的内容发生变化时，它需要知道哪些资源（如果有的话）受到该变化的影响，以便最小化执行的工作，同时确保完整的构建。要回答这个问题——"api.rst 的下游有哪些节点？"——我们需要检查 api.rst 的传出边。

但构建依赖关系图需要 Contingent 也关注节点的输入。例如，当构建系统组装输出文档 tutorial.html 时使用了哪些输入？通过观察每个节点的输入，Contingent 可以知道 api.html 依赖于 api.rst，但 tutorial.html 不依赖。随着源的更改和重建的发生，Contingent 重建每个更改节点的传入边，以删除潜在的陈旧边并重新了解这次任务使用了哪些资源。

我们的边集合元组不能轻松回答这两个问题。如果我们需要知道 api.html 与图的其余部分之间的关系，我们将需要遍历整个集合，寻找在 api.html 节点开始或结束的边。

像 Python 的字典这样的关联数据结构将通过允许直接查找特定节点的所有边来使这些任务更容易：

{'tutorial.rst': {('tutorial.rst', 'tutorial.html')},
 'tutorial.html': {('tutorial.rst', 'tutorial.html')},
 'index.rst': {('index.rst', 'index.html')},
 'index.html': {('index.rst', 'index.html')},
 'api.rst': {('api.rst', 'api.html')},
 'api.html': {('api.rst', 'api.html')}}

现在查找特定节点的边将是极快的，代价是必须存储每个边两次：一次在传入边的集合中，一次在传出边的集合中。但是必须手动检查每个集合中的边，以查看哪些是传入的，哪些是传出的。在其边集合中一遍又一遍地命名节点也有点冗余。

解决这两个异议的方法是将传入边和传出边放在各自独立的数据结构中，这也将免除我们为涉及到的每一个边一遍又一遍地提及节点的需要。

incoming = {
    'tutorial.html': {'tutorial.rst'},
    'index.html': {'index.rst'},
    'api.html': {'api.rst'},
}

outgoing = {
    'tutorial.rst': {'tutorial.html'},
    'index.rst': {'index.html'},
    'api.rst': {'api.html'},
}

请注意，outgoing 直接用 Python 语法表示了我们之前在图 4.1 中绘制的内容：左侧的源文档将被构建系统转换为右侧的输出文档。对于这个简单的例子，每个源只指向一个输出——所有输出集合只有一个元素——但我们很快就会看到单个输入节点有多个下游结果的例子。

这个字典集合数据结构中的每个边确实被表示了两次，一次作为一个节点的传出边（tutorial.rst → tutorial.html），再一次作为另一个节点的传入边（tutorial.html ← tutorial.rst）。这两种表示捕获了完全相同的关系，只是从边两端的两个节点的相反角度来看。但作为这种冗余的回报，数据结构支持 Contingent 需要的快速查找。

类的正确使用

在上面关于 Python 数据结构的讨论中，你可能对缺少类感到惊讶。毕竟，类是构建应用程序的常见机制，在其拥护者和批评者之间也是一个争论激烈的话题。类曾被认为足够重要，以至于围绕它们设计了整个教育课程，而大多数流行的编程语言都包含了定义和使用它们的专用语法。

但事实证明，类通常与数据结构设计问题无关。类并没有为我们提供一个完全不同的数据建模范式，而是简单地重复了我们已经看到的数据结构：

• 类实例的实现是一个字典。
• 类实例的使用就像一个可变元组。

类通过更漂亮的语法提供键查找，你可以说 graph.incoming 而不是 graph["incoming"]。但在实践中，类实例几乎从不用作通用的键值存储。相反，它们用于通过属性名组织相关但异构的数据，实现细节封装在一致且易记的接口后面。

因此，不是将主机名和端口号放在元组中并必须记住哪个在前哪个在后，你创建一个 Address 类，其实例各有一个 host 和一个 port 属性。然后你可以传递 Address 对象，否则你将使用匿名元组。代码变得更容易阅读和编写。但使用类实例并不会真正改变我们在上面进行数据设计时面临的任何问题；它只是提供了一个更漂亮且不那么匿名的容器。

那么，类的真正价值不在于它们改变了数据设计的科学。类的价值在于它们让你可以向程序的其余部分隐藏你的数据设计！

成功的应用程序设计取决于我们利用 Python 为我们提供的强大内置数据结构的能力，同时最小化我们一次需要记住的细节量。类提供了解决这种明显困境的机制：有效使用时，类围绕系统整体设计的某个小子集提供外观。当在一个子集内工作时——例如一个 Graph——我们可以忘记其他子集的实现细节，只要我们记住它们的接口。通过这种方式，程序员经常发现自己在编写系统的过程中在几个抽象层之间导航，现在使用特定子系统的特定数据模型和实现细节，现在通过其接口连接更高级别的概念。

例如，从外部看，代码可以简单地请求一个新的 Graph 实例：

>>> from contingent import graphlib
>>> g = graphlib.Graph()

而不需要理解 Graph 如何工作的细节。仅使用图的代码在操作图时只看到接口动词——方法调用——例如添加边或执行某些其他操作时：

>>> g.add_edge('index.rst', 'index.html')
>>> g.add_edge('tutorial.rst', 'tutorial.html')
>>> g.add_edge('api.rst', 'api.html')

细心的读者会注意到，我们在没有显式创建"节点"和"边"对象的情况下向图中添加了边，并且这些早期示例中的节点本身只是字符串。来自其他语言和传统，人们可能期望看到系统中所有内容都有用户定义的类和接口：

Graph g = new ConcreteGraph();
Node indexRstNode = new StringNode("index.rst");
Node indexHtmlNode = new StringNode("index.html");
Edge indexEdge = new DirectedEdge(indexRstNode, indexHtmlNode);
g.addEdge(indexEdge);

Python 语言和社区明确而有意地强调使用简单的通用数据结构来解决问题，而不是为我们想要解决的问题的每个微小细节创建自定义类。这是"Pythonic"解决方案概念的一个方面：Pythonic 解决方案试图最小化语法开销并利用 Python 强大的内置工具和广泛的标准库。

考虑到这些因素，让我们回到 Graph 类，检查其设计和实现，以了解数据结构和类接口之间的相互作用。当构造一个新的 Graph 实例时，已经构建了一对字典来使用我们在上一节中概述的逻辑存储边：

class Graph:
    """任务之间构建关系的有向图。"""

    def __init__(self):
        self._inputs_of = defaultdict(set)
        self._consequences_of = defaultdict(set)

属性名 _inputs_of 和 _consequences_of 前面的前导下划线是 Python 社区中的常见约定，用于表示属性是私有的。这种约定是社区建议程序员通过空间和时间相互传递消息和警告的一种方式。认识到需要区分公共和内部对象属性的信号，社区采用单个前导下划线作为一个简洁且相当一致的指示器，告诉其他程序员（包括我们未来的自己）该属性最好被视为类的不可见内部机制的一部分。

为什么我们使用 defaultdict 而不是标准字典？将字典与其他数据结构组合时的一个常见问题是处理缺失的键。使用普通字典，检索不存在的键会引发 KeyError：

>>> consequences_of = {}
>>> consequences_of['index.rst'].add('index.html')
Traceback (most recent call last):
    ...
KeyError: 'index.rst'

使用普通字典需要在整个代码中进行特殊检查来处理这种特定情况，例如在添加新边时：

# 处理"我们还没有见过这个任务"的特殊情况：

if input_task not in self._consequences_of:
    self._consequences_of[input_task] = set()

self._consequences_of[input_task].add(consequence_task)

这种需求非常普遍，以至于 Python 包含了一个特殊的实用程序 defaultdict，它允许你提供一个函数，为不存在的键返回一个值。当我们询问 Graph 尚未见过的边时，我们将得到一个空的 set 而不是异常：

>>> from collections import defaultdict
>>> consequences_of = defaultdict(set)
>>> consequences_of['api.rst']
set()

以这种方式构建我们的实现意味着每个键的首次使用看起来与第二次和后续使用特定键时完全相同：

>>> consequences_of['index.rst'].add('index.html')
>>> 'index.html' in consequences_of['index.rst']
True

鉴于这些技术，让我们检查 add_edge 的实现，我们之前使用它来构建图 4.1 的图。

def add_edge(self, input_task, consequence_task):
    """添加一条边：`consequence_task` 使用 `input_task` 的输出。"""
    self._consequences_of[input_task].add(consequence_task)
    self._inputs_of[consequence_task].add(input_task)

这个方法隐藏了每个新边需要两个（而不是一个）存储步骤的事实，这样我们才能在两个方向上知道它。请注意 add_edge() 如何不知道或不关心以前是否见过任一节点。因为输入和结果数据结构各自都是 defaultdict(set)，add_edge() 方法对节点的新颖性保持幸福的无知——defaultdict 通过即时创建新的 set 对象来处理差异。正如我们上面看到的，如果我们没有使用 defaultdict，add_edge() 将长三倍。更重要的是，理解和推理生成的代码将更加困难。这个实现展示了 Pythonic 方法来解决问题：简单、直接和简洁。

调用者还应该获得一种简单的方式来访问每个边，而无需学习如何遍历我们的数据结构：

def edges(self):
    """将所有边作为 ``(input_task, consequence_task)`` 元组返回。"""
    return [(a, b) for a in self.sorted(self._consequences_of)
                   for b in self.sorted(self._consequences_of[a])]

Graph.sorted() 方法尝试以自然排序顺序（如字母顺序）对节点进行排序，这可以为用户提供稳定的输出顺序。

通过使用这个遍历方法，我们可以看到，在我们之前的三次"add"方法调用之后，g 现在表示我们在图 4.1 中看到的相同图。

>>> from pprint import pprint
>>> pprint(g.edges())
[('api.rst', 'api.html'),
 ('index.rst', 'index.html'),
 ('tutorial.rst', 'tutorial.html')]

既然我们现在有了一个真正的 Python 对象，而不仅仅是一个图，我们可以向它提出有趣的问题！例如，当 Contingent 从源文件构建博客时，当 api.rst 的内容发生变化时，它需要知道"什么依赖于 api.rst？"：

>>> g.immediate_consequences_of('api.rst')
['api.html']

这个 Graph 告诉 Contingent，当 api.rst 改变时，api.html 现在已经过时，必须重建。

那么 index.html 呢？

>>> g.immediate_consequences_of('index.html')
[]

返回了一个空列表，表明 index.html 在图的右边缘，因此如果它发生变化，不需要进一步重建任何东西。由于已经进行了布局数据的工作，这个查询可以非常简单地表达：

def immediate_consequences_of(self, task):
    """返回使用 `task` 作为输入的任务。"""
    return self.sorted(self._consequences_of[task])

图 4.1 忽略了我们在本章开头部分发现的最重要关系之一：文档标题在目录中出现的方式。让我们填充这个细节。我们将为每个需要通过解析输入文件生成然后传递给其他例程的标题字符串创建一个节点：

>>> g.add_edge('api.rst', 'api-title')
>>> g.add_edge('api-title', 'index.html')
>>> g.add_edge('tutorial.rst', 'tutorial-title')
>>> g.add_edge('tutorial-title', 'index.html')

结果是一个图（图 4.2），它可以正确处理我们在本章开头讨论的目录重建。

图 4.2 - 准备在任何提到的标题更改时重建 index.html

这个手动演示说明了我们最终要让 Contingent 为我们做的事情：图 g 捕获了项目文档中各种工件的输入和结果。

学习连接

我们现在有一种方法让 Contingent 跟踪任务和它们之间的关系。然而，如果我们更仔细地看图 4.2，我们会发现它实际上有点含糊不清：api.html 是如何从 api.rst 生成的？我们如何知道 index.html 需要教程的标题？这个依赖关系是如何解决的？

当我们手动构建结果图时，我们对这些想法的直觉理解很有用，但不幸的是计算机不太直观，所以我们需要更精确地说明我们想要什么。

生成输出所需的步骤是什么？这些步骤如何定义和执行？Contingent 如何知道它们之间的连接？

在 Contingent 中，构建任务被建模为函数加参数。函数定义了特定项目理解如何执行的操作。参数提供了具体内容：应该读取哪个源文档，需要哪个博客标题。当它们运行时，这些函数可能会依次调用其他任务函数，传递它们需要答案的任何参数。

为了看到这是如何工作的，我们现在将实际实现本章开头描述的文档构建器。为了防止我们陷入细节的泥潭，对于这个说明，我们将使用简化的输入和输出文档格式。我们的输入文档将在第一行包含标题，其余文本形成正文。交叉引用将只是用反引号括起来的源文件名，在输出时替换为相应文档的标题。

以下是我们示例 index.txt、api.txt 和 tutorial.txt 的内容，展示了我们小文档格式的标题、文档正文和交叉引用：

>>> index = """
... Table of Contents
... -----------------
... * `tutorial.txt`
... * `api.txt`
... """

>>> tutorial = """
... Beginners Tutorial
... ------------------
... Welcome to the tutorial!
... We hope you enjoy it.
... """

>>> api = """
... API Reference
... -------------
... You might want to read
... the `tutorial.txt` first.
... """

现在我们有了一些源材料可以使用，基于 Contingent 的博客构建器需要什么函数？

在上面的简单示例中，HTML 输出文件直接从源文件生成，但在现实系统中，将源转换为标记涉及几个步骤：从磁盘读取原始文本、将文本解析为方便的内部表示、处理作者可能指定的任何指令、解析交叉引用或其他外部依赖项（如包含文件），以及应用一个或多个视图转换以将内部表示转换为其输出形式。

Contingent 通过将任务分组到 Project 中来管理任务，这是一种构建系统的管家，它将自己注入到构建过程的中间，每次一个任务与另一个任务交互时都会记录，以构建所有任务之间关系的图。

>>> from contingent.projectlib import Project, Task
>>> project = Project()
>>> task = project.task

本章开头给出的示例的构建系统可能涉及几个任务。

我们的 read() 任务将假装从磁盘读取文件。由于我们实际上在变量中定义了源文本，它所需要做的就是从文件名转换到相应的文本。

>>> filesystem = {'index.txt': index,
...               'tutorial.txt': tutorial,
...               'api.txt': api}
...
>>> @task
... def read(filename):
...     return filesystem[filename]

parse() 任务根据我们文档格式的规范解释文件内容的原始文本。我们的格式非常简单：文档的标题出现在第一行，其余内容被视为文档的正文。

>>> @task
... def parse(filename):
...     lines = read(filename).strip().splitlines()
...     title = lines[0]
...     body = '\n'.join(lines[2:])
...     return title, body

因为格式如此简单，解析器有点愚蠢，但它说明了解析器需要承担的解释职责。（一般来说，解析是一个非常有趣的主题，已经有许多书籍部分或完全关于它。）在像 Sphinx 这样的系统中，解析器必须理解系统定义的许多标记标记、指令和命令，将输入文本转换为系统其余部分可以使用的内容。

注意 parse() 和 read() 之间的连接点——解析的第一个任务是将其收到的文件名传递给 read()，它会找到并返回该文件的内容。

title_of() 任务，给定一个源文件名，返回文档的标题：

>>> @task
... def title_of(filename):
...     title, body = parse(filename)
...     return title

这个任务很好地说明了文档处理系统各部分之间的职责分离。title_of() 函数直接从文档的内存表示工作——在这种情况下是一个元组——而不是承担再次解析整个文档只是为了找到标题的任务。parse() 函数单独产生内存表示，根据系统规范的约定，系统的其余文档构建处理函数（如 title_of()）只需使用其输出作为其权威。

如果你来自正统的面向对象传统，这种面向函数的设计可能看起来有点奇怪。在面向对象的解决方案中，parse() 将返回某种 Document 对象，它将 title_of() 作为方法或属性。事实上，Sphinx 正是这样工作的：它的 Parser 子系统为系统的其他部分产生一个"Docutils 文档树"对象来使用。

Contingent 对这些不同的设计范式没有偏见，同样支持这两种方法。对于本章，我们保持简单。

最后一个任务 render() 将文档的内存表示转换为输出形式。实际上，它是 parse() 的逆操作。parse() 获取符合规范的输入文档并将其转换为内存表示，而 render() 获取内存表示并产生符合某些规范的输出文档。

>>> import re
>>>
>>> LINK = '<a href="{}">{}</a>'
>>> PAGE = '<h1>{}</h1>\n<p>\n{}\n<p>'
>>>
>>> def make_link(match):
...     filename = match.group(1)
...     return LINK.format(filename, title_of(filename))
...
>>> @task
... def render(filename):
...     title, body = parse(filename)
...     body = re.sub(r'`([^`]+)`', make_link, body)
...     return PAGE.format(title, body)

这是一个示例运行，将调用上述逻辑的每个阶段——渲染 tutorial.txt 以生成其输出：

>>> print(render('tutorial.txt'))
<h1>Beginners Tutorial</h1>
<p>
Welcome to the tutorial!
We hope you enjoy it.
<p>

图 4.3 说明了传递连接生成输出所需的所有任务的任务图，从读取输入文件，到解析和转换文档，再到渲染它：

图 4.3 - 任务图

事实证明，图 4.3 不是为本章手绘的，而是直接从 Contingent 生成的！构建这个图对于 Project 对象是可能的，因为它维护自己的调用栈，类似于 Python 维护的活动执行帧栈，用于记住当当前函数返回时要继续运行哪个函数。

每次调用新任务时，Contingent 可以假设它已被调用——并且其输出将被使用——由当前栈顶的任务。维护栈将需要几个额外的步骤围绕任务 T 的调用：

1. 将 T 推入栈。
2. 执行 T，让它调用它需要的任何其他任务。
3. 将 T 从栈中弹出。
4. 返回其结果。

为了拦截任务调用，Project 利用了 Python 的一个关键特性：函数装饰器。装饰器被允许在函数被定义的时刻处理或转换函数。Project.task 装饰器利用这个机会将每个任务打包在另一个函数中，一个包装器，它允许包装器（将代表 Project 担心图和栈管理）和我们专注于文档处理的任务函数之间的职责清晰分离。这是 task 装饰器样板的样子：

from functools import wraps

def task(function):
    @wraps(function)
    def wrapper(*args):
        # wrapper 主体，将调用 function()
    return wrapper

这是一个完全典型的 Python 装饰器声明。然后可以通过在创建函数的 def 顶部的 @ 字符后命名它来将其应用于函数：

@task
def title_of(filename):
    title, body = parse(filename)
    return title

当这个定义完成时，名称 title_of 将引用函数的包装版本。包装器可以通过名称 function 访问函数的原始版本，在适当的时候调用它。Contingent 包装器的主体运行如下：

def task(function):
    @wraps(function)
    def wrapper(*args):
        task = Task(wrapper, args)
        if self.task_stack:
            self._graph.add_edge(task, self.task_stack[-1])
        self._graph.clear_inputs_of(task)
        self._task_stack.append(task)
        try:
            value = function(*args)
        finally:
            self._task_stack.pop()

        return value
    return wrapper

这个包装器执行几个关键的维护步骤：

1. 将任务——函数加上其参数——打包成一个小对象以方便使用。这里的 wrapper 命名了任务函数的包装版本。

2. 如果这个任务已被当前正在进行的任务调用，添加一条边来捕获这个任务是已运行任务的输入这一事实。

3. 忘记我们上次可能了解到的关于任务的任何信息，因为它这次可能会做出新的决定——例如，如果 API 指南的源文本不再提到教程，那么它的 render() 将不再请求教程文档的 title_of()。

4. 将这个任务推到任务栈的顶部，以防它决定在做其工作的过程中调用更多任务。

5. 在 try...finally 块中调用任务，确保我们正确地从栈中删除完成的任务，即使它因引发异常而死亡。

6. 返回任务的返回值，这样这个包装器的调用者将无法分辨他们没有简单地调用普通任务函数本身。

步骤 4 和 5 维护任务栈本身，然后步骤 2 使用它来执行结果跟踪，这是我们首先构建任务栈的全部原因。

由于每个任务都被其自己的包装器函数副本包围，任务正常栈的简单调用和执行将作为不可见的副作用产生关系图。这就是为什么我们小心地在我们定义的每个处理步骤周围使用包装器：

@task
def read(filename):
    # read 的主体

@task
def parse(filename):
    # parse 的主体

@task
def title_of(filename):
    # title_of 的主体

@task
def render(filename):
    # render 的主体

多亏了这些包装器，当我们调用 parse('tutorial.txt') 时，装饰器学习了 parse 和 read 之间的连接。我们可以通过构建另一个 Task 元组并询问如果其输出值发生变化会产生什么结果来询问这种关系：

>>> task = Task(read, ('tutorial.txt',))
>>> print(task)
read('tutorial.txt')
>>> project._graph.immediate_consequences_of(task)
[parse('tutorial.txt')]

重新读取 tutorial.txt 文件并发现其内容已更改的结果是我们需要为该文档重新执行 parse() 例程。如果我们渲染整套文档会发生什么？Contingent 能够学习整个构建过程吗？

>>> for filename in 'index.txt', 'tutorial.txt', 'api.txt':
...     print(render(filename))
...     print('=' * 30)
...
<h1>Table of Contents</h1>
<p>
* <a href="tutorial.txt">Beginners Tutorial</a>
* <a href="api.txt">API Reference</a>
<p>
==============================
<h1>Beginners Tutorial</h1>
<p>
Welcome to the tutorial!
We hope you enjoy it.
<p>
==============================
<h1>API Reference</h1>
<p>
You might want to read
the <a href="tutorial.txt">Beginners Tutorial</a> first.
<p>
==============================

它成功了！从输出中，我们可以看到我们的转换用相应文档的文档标题替换了源文档中的指令，这表明 Contingent 能够发现构建我们文档所需的各种任务之间的连接。

图 4.4 - 输入文件和 HTML 输出之间的完整关系集

通过观察一个任务通过 task 包装器机制调用另一个任务，Project 自动学习了输入和结果的图。由于它有一个完整的结果图，Contingent 知道如果任何任务的输入发生变化，需要重建的所有内容。

追踪结果

一旦初始构建运行完成，Contingent 需要监视输入文件的更改。当用户完成新的编辑并运行"保存"时，read() 方法及其结果都需要被调用。

这将要求我们以与创建图时相反的顺序遍历图。回想一下，它是通过调用 API 参考的 render() 来构建的，该调用调用 parse()，最后调用 read() 任务。现在我们反过来：我们知道 read() 现在将返回新内容，我们需要找出下游有什么结果。

编译结果的过程是递归的，因为每个结果本身都可以有依赖于它的进一步任务。我们可以通过重复调用图来手动执行这个递归。（请注意，我们在这里利用了 Python 提示符将上次显示的值保存在名称 _ 下以供后续表达式使用的事实。）

>>> task = Task(read, ('api.txt',))
>>> project._graph.immediate_consequences_of(task)
[parse('api.txt')]
>>> t1, = _
>>> project._graph.immediate_consequences_of(t1)
[render('api.txt'), title_of('api.txt')]
>>> t2, t3 = _
>>> project._graph.immediate_consequences_of(t2)
[]
>>> project._graph.immediate_consequences_of(t3)
[render('index.txt')]
>>> t4, = _
>>> project._graph.immediate_consequences_of(t4)
[]

这个递归任务——反复寻找直接结果并且只在我们到达没有进一步结果的任务时停止——是一个足够基本的图操作，它由 Graph 类的一个方法直接支持：

>>> # 偷偷地将 pprint 调整为比平常更窄的宽度：
>>> _pprint = pprint
>>> pprint = lambda x: _pprint(x, width=40)
>>> pprint(project._graph.recursive_consequences_of([task]))
[parse('api.txt'),
 render('api.txt'),
 title_of('api.txt'),
 render('index.txt')]

事实上，recursive_consequences_of() 试图变得有点聪明。如果一个特定的任务作为其他几个任务的下游结果重复出现，那么它会小心地只在输出列表中提到它一次，并将其移到末尾，使其只在作为其输入的任务之后出现。这种智能由拓扑排序的经典深度优先实现提供支持，这是一种算法，通过隐藏的递归辅助函数在 Python 中编写起来相当容易。查看 graphlib.py 源代码了解详细信息。

如果在检测到更改时，我们小心地重新运行递归结果中的每个任务，那么 Contingent 将能够避免重建得太少。然而，我们的第二个挑战是避免重建得太多。再次参考图 4.4。我们希望避免每次更改 tutorial.txt 时都重建所有三个文档，因为大多数编辑可能不会影响其标题，而只会影响其正文。这如何实现？

解决方案是使图重新计算依赖于缓存。当向前遍历更改的递归结果时，我们只会调用其输入与上次不同的任务。

这种优化将涉及最终的数据结构。我们将给 Project 一个 _todo 集合，用于记住至少有一个输入值已更改因此需要重新执行的每个任务。因为只有 _todo 中的任务是过时的，构建过程可以跳过运行任何任务，除非它们出现在那里。

同样，Python 方便统一的设计使这些功能非常容易编码。因为任务对象是可哈希的，_todo 可以简单地是一个通过身份记住任务项的集合——保证任务永远不会出现两次——而 _cache 的先前运行的返回值可以是一个以任务为键的字典。

更准确地说，重建步骤必须在 _todo 非空时保持循环。在每次循环中，它应该：

• 调用 recursive_consequences_of() 并传入 _todo 中列出的每个任务。返回值不仅是 _todo 任务本身的列表，还有它们下游的每个任务——换句话说，如果这次输出结果不同，可能需要重新执行的每个任务。

• 对于列表中的每个任务，检查它是否列在 _todo 中。如果没有，那么我们可以跳过运行它，因为我们在其上游重新调用的任务都没有产生需要任务重新计算的新返回值。

• 但对于我们到达时确实列在 _todo 中的任何任务，我们需要要求它重新运行并重新计算其返回值。如果任务包装器函数检测到此返回值与旧的缓存值不匹配，那么其下游任务将在我们到达列表中的它们之前自动添加到 _todo 中。

到我们到达列表末尾时，每个可能需要重新运行的任务实际上应该已经重新运行了。但为了以防万一，我们将检查 _todo，如果它还不是空的，再试一次。即使对于快速变化的依赖树，这应该很快稳定下来。只有一个循环——例如，任务 A 需要任务 B 的输出，而任务 B 本身需要任务 A 的输出——可以让构建器陷入无限循环，并且只有在它们的返回值从不稳定的情况下。幸运的是，现实世界的构建任务通常没有循环。

让我们通过一个例子来追踪这个系统的行为。

假设你编辑 tutorial.txt 并更改标题和正文内容。我们可以通过修改 filesystem 字典中的值来模拟这一点：

>>> filesystem['tutorial.txt'] = """
... The Coder Tutorial
... ------------------
... This is a new and improved
... introductory paragraph.
... """

现在内容已更改，我们可以通过使用其 cache_off() 上下文管理器来要求 Project 重新运行 read() 任务，该管理器暂时禁用其为给定任务和参数返回旧缓存结果的意愿：

>>> with project.cache_off():
...     text = read('tutorial.txt')

新的教程文本现在已被读入缓存。需要重新执行多少下游任务？

为了帮助我们回答这个问题，Project 类支持一个简单的跟踪工具，它会告诉我们在重建过程中执行了哪些任务。由于上述对 tutorial.txt 的更改会影响其正文和标题，所以下游的所有内容都需要重新计算：

>>> project.start_tracing()
>>> project.rebuild()
>>> print(project.stop_tracing())
calling parse('tutorial.txt')
calling render('tutorial.txt')
calling title_of('tutorial.txt')
calling render('api.txt')
calling render('index.txt')

回顾图 4.4，你可以看到，正如预期的那样，这是 read('tutorial.txt') 的直接或下游结果的每个任务。

但是如果我们再次编辑它，但这次保持标题不变呢？

>>> filesystem['tutorial.txt'] = """
... The Coder Tutorial
... ------------------
... Welcome to the coder tutorial!
... It should be read top to bottom.
... """
>>> with project.cache_off():
...     text = read('tutorial.txt')

这个小而有限的更改应该不会对其他文档产生影响。

>>> project.start_tracing()
>>> project.rebuild()
>>> print(project.stop_tracing())
calling parse('tutorial.txt')
calling render('tutorial.txt')
calling title_of('tutorial.txt')

成功！只有一个文档被重建。title_of() 在给定新的输入文档后仍然返回相同的值这一事实意味着所有进一步的下游任务都与更改隔离，不会被重新调用。

结论

在某些语言和编程方法下，Contingent 将是一个令人窒息的小类森林，对问题领域中的每个概念都给予冗长的名称。

然而，在用 Python 编程 Contingent 时，我们跳过了创建十几个可能的类，如 TaskArgument 和 CachedResult 和 ConsequenceList。相反，我们利用 Python 用通用数据结构解决通用问题的强大传统，产生的代码反复使用来自核心数据结构元组、列表、集合和字典的一小组想法。

但这不会造成问题吗？

通用数据结构本质上也是匿名的。我们的 project._cache 是一个集合。Graph 内部每个上游和下游节点的集合也是如此。我们是否有危险看到通用的 set 错误消息而不知道是在项目还是图实现中查找错误？

事实上，我们没有危险！

多亏了封装的仔细纪律——只允许 Graph 代码触及图的集合，Project 代码触及项目的集合——如果集合操作在项目的后期阶段返回错误，将永远不会有歧义。错误时刻执行的最内层方法的名称将必然将我们引导到确切的类和涉及错误的集合。不需要为数据类型的每个可能应用创建 set 的子类，只要我们在数据结构属性前放置传统的下划线，然后小心不要从类外部的代码触及它们。

Contingent 展示了来自《设计模式》这本划时代著作的外观模式对于设计良好的 Python 程序是多么关键。并非 Python 程序中的每个数据结构和数据片段都能成为自己的类。相反，类被谨慎使用，在代码中的概念关键点——例如依赖图的想法——可以包装到一个外观中，该外观隐藏了下面简单通用数据结构的细节。

外观之外的代码命名它需要的大概念和它想要执行的操作。在外观内部，程序员操纵 Python 编程语言的小而方便的活动部件来实现操作。