Brandon Rhodes 从 20 世纪 90 年代后期开始使用 Python，并在 17 年间一直维护着供业余天文学家使用的 PyEphem 库。他供职于 Dropbox，为企业客户教授 Python 编程课程，并参与了新英格兰野花协会的“Go Botany”Django 网站等项目的咨询工作，并且将在 2016 年和 2017 年担任 PyCon 大会主席。Brandon 认为，写得好的代码是一种文学形式，格式优美的代码是一件图形设计作品，而正确的代码是最透明的思维形式之一。
Daniel Rocco 热爱 Python、咖啡、工艺啤酒、对象和系统设计、波旁威士忌、教学、树木和拉丁吉他。他很高兴能够以编写 Python 为生，并且始终在寻找机会从社区中的其他人那里学习，并通过分享知识做出贡献。他是 PyAtl 上的常客，主要讲解入门主题、测试、设计和炫酷的东西；当有人分享新颖、令人惊讶或美好的想法时，他喜欢看到人们眼中闪烁着惊奇和喜悦的光芒。Daniel 与一位微生物学家和四个有抱负的火箭爱好者住在亚特兰大。
构建系统长期以来一直是计算机编程中的标准工具。
标准的 make 构建系统（其作者曾获得 ACM 软件系统奖）最初开发于 1976 年。它不仅允许您声明输出文件依赖于一个（或多个）输入文件，还可以递归地执行此操作。例如，一个程序可能依赖于一个目标文件，而该目标文件本身又依赖于相应的源代码。
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，但每个章节和部分的实际标题是从三个章节源文件本身提取的。
如果您稍后重新考虑教程的章节标题——毕竟，“新手”这个词听起来很古旧，就好像您的用户是刚刚抵达怀俄明州先锋地区的定居者——那么您将编辑 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 文件顶部的标题进行另一个编辑会怎样？您将使 *三个* 输出文件失效
tutorial.html 顶部的标题已过时，因此需要重建该文件。
index.html 中的目录仍然包含旧标题，因此需要重建该文档。
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 语言通过在语言语法中直接支持它们来优先考虑四大通用数据结构。您可以通过简单地将它们的文字表示输入到源代码中来创建这些四大数据结构的新实例，并且它们的四个类型对象作为内置符号可用，无需导入即可使用。
元组是一个只读序列，用于保存异构数据——元组中的每个槽通常表示不同的含义。这里，一个元组将主机名和端口号组合在一起，如果元素的顺序被重新排列，它就会失去意义。
('dropbox.com', 443)列表是一个可变序列，用于保存同构数据——每个项目通常与其同类具有相同的结构和含义。列表可以用来保留数据的原始输入顺序，也可以重新排列或排序以建立新的更有用的顺序。
['C', 'Awk', 'TCL', 'Python', 'JavaScript']集合不保留顺序。集合只记住是否添加了给定的值，而不是添加了多少次，因此它是从数据流中删除重复项的首选数据结构。例如，以下两个集合将分别包含三个元素。
{3, 4, 5}
{3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 5}字典是一种关联数据结构，用于存储可以通过键访问的值。字典允许程序员选择每个值索引的键，而不是像元组和列表那样使用自动整数索引。查找由哈希表支持，这意味着字典键查找的速度与字典包含十几个键还是一百万个键相同。
{'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 这样的构建系统需要了解给定节点与其连接的所有节点之间的关系。例如，当 api.rst 发生更改时，Contingent 需要知道哪些资产（如果有）受到该更改的影响，以便最大程度地减少执行的工作量，同时确保构建完整。为了回答这个问题——“哪些节点在下游 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:
"""A directed graph of the relationships among build tasks."""
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'使用普通字典需要在整个代码中进行特殊检查以处理这种情况，例如在添加新边时
# Special case to handle “we have not seen this task yet”:
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):
"""Add an edge: `consequence_task` uses the output of `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()的代码长度将增加三倍。更重要的是，生成的代码将更难以理解和推理。这种实现展示了一种Python式的解决问题的方法：简单、直接和简洁。
调用者也应该有一种简单的方法来访问每条边，而无需学习如何遍历我们的数据结构。
def edges(self):
"""Return all edges as ``(input_task, consequence_task)`` tuples."""
return [(a, b) for a in self.sorted(self._consequences_of)
for b in self.sorted(self._consequences_of[a])]Graph.sorted()方法尝试以自然排序顺序（例如字母顺序）对节点进行排序，这可以为用户提供稳定的输出顺序。
通过使用这种遍历方法，我们可以看到，在前面三次“添加”方法调用之后，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):
"""Return the tasks that use `task` as an input."""
return self.sorted(self._consequences_of[task]) >>> from contingent.rendering import as_graphviz
>>> open('figure1.dot', 'w').write(as_graphviz(g)) and None图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周围执行几个额外的步骤。
为了拦截任务调用，Project利用了Python的一个关键特性：函数装饰器。装饰器允许在定义函数时对其进行处理或转换。Project.task装饰器利用此机会将每个任务打包到另一个函数（一个包装器）中，这允许在包装器（它将代表Project处理图和栈管理）和专注于文档处理的任务函数之间进行清晰的职责分离。以下是task装饰器样板代码的样子。
from functools import wraps
def task(function):
@wraps(function)
def wrapper(*args):
# wrapper body, that will call 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此包装器执行几个关键的维护步骤。
将任务（函数及其参数）打包到一个小对象中以方便使用。此处的wrapper命名了任务函数的包装版本。
如果此任务已被正在进行的当前任务调用，则添加一条边以捕获此任务是正在运行的任务的输入这一事实。
忘记我们上次关于此任务可能学到的任何东西，因为它这次可能会做出新的决策——例如，如果API指南的源文本不再提及教程，则其render()将不再请求教程文档的title_of()。
将此任务推送到任务栈的顶部，以防它在执行其工作的过程中决定依次调用更多任务。
在 try...finally 代码块内调用任务，确保即使任务因引发异常而终止，我们也能正确地将其从栈中移除。
返回任务的返回值，这样调用此包装器的代码将无法分辨它们是否只是简单地调用了普通任务函数本身。
步骤 4 和 5 维护任务栈本身，然后步骤 2 使用它来执行后果跟踪，而这正是我们构建任务栈的根本原因。
由于每个任务都被其自身的包装函数副本包围，因此仅仅调用和执行正常的任务栈就会产生一个关系图作为不可见的副作用。这就是为什么我们小心地对定义的每个处理步骤都使用了包装器。
@task
def read(filename):
# body of read
@task
def parse(filename):
# body of parse
@task
def title_of(filename):
# body of title_of
@task
def render(filename):
# body of 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 类的方法直接支持它。
>>> # Secretly adjust pprint to a narrower-than-usual width:
>>> _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.
... """现在内容已更改，我们可以要求 Project 重新运行 read() 任务，方法是使用其 cache_off() 上下文管理器，该管理器暂时禁用其返回给定任务和参数的旧缓存结果的意愿。
>>> 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 演示了来自具有开创性意义的《设计模式》一书的 Facade 模式对于设计良好的 Python 程序至关重要。并非 Python 程序中的每个数据结构和数据片段都必须是它自己的类。相反，类是谨慎使用的，在代码的概念枢纽处，一个大的想法——例如依赖图的概念——可以封装到一个 Facade 中，隐藏其下方的简单通用数据结构的细节。
Facade 外部的代码命名它需要的概念和它想要执行的操作。在 Facade 内部，程序员操作 Python 编程语言的小而方便的移动部件来使操作发生。