構(gòu)建系統(tǒng)是從源文件生成目標(biāo)文件的自動(dòng)化工具鼓鲁，基本上各個(gè)語(yǔ)言中都有磺箕，比如 C 語(yǔ)言中的 make煞烫，本文介紹了一種完全動(dòng)態(tài)的構(gòu)建系統(tǒng)昼窗，利用了圖的思想。另外敷燎，本文的 Python 代碼也值得我們學(xué)習(xí)暂筝。
原文作者
Brandon Rhodes 和 Daniel Rocco。
Brandon Rhodes 在 20 世紀(jì) 90 年代末就開(kāi)始使用 Python硬贯，17 年來(lái)一直在使用 Python 為業(yè)余天文學(xué)家維護(hù) PyEphem 庫(kù)焕襟。他在 Dropbox 工作，教授公司客戶 Python 編程課程饭豹，為新英格蘭野花協(xié)會(huì)的“Go Botany” Django網(wǎng)站 項(xiàng)目提供咨詢鸵赖，并將在2016年和2017年擔(dān)任 PyCon會(huì)議主席。Brandon 認(rèn)為拄衰，編寫(xiě)良好的代碼是一種文學(xué)它褪，那些格式精美的代碼是平面設(shè)計(jì)作品，正確的代碼是最易懂的思想形式之一翘悉。
Daniel Rocco 熱愛(ài) Python茫打、咖啡、工藝镐确、黑啤酒包吝、對(duì)象和系統(tǒng)設(shè)計(jì)，波旁威士忌源葫、教學(xué)诗越、樹(shù)木和拉丁吉他。他靠 Python 謀生息堂，他總是在尋找從社區(qū)的其他人學(xué)習(xí)的機(jī)會(huì)嚷狞，并通過(guò)分享知識(shí)作出貢獻(xiàn)。他經(jīng)常在 PyAtl 上演講介紹性話題荣堰、測(cè)試床未、設(shè)計(jì)和耀眼的產(chǎn)品。他喜歡在有人分享一個(gè)新奇的的想法時(shí)看到人們眼中閃爍著驚奇和喜悅的火花振坚。Daniel 和一個(gè)微生物學(xué)家以及四個(gè)有抱負(fù)的火箭專(zhuān)家住在 Atlanta薇搁。
引言
長(zhǎng)期以來(lái)，構(gòu)建系統(tǒng)一直是計(jì)算機(jī)編程中的標(biāo)準(zhǔn)工具渡八。
標(biāo)準(zhǔn)的 make 構(gòu)建系統(tǒng)于 1976 年首次開(kāi)發(fā)啃洋，為它的作者贏得了 ACM 軟件系統(tǒng)獎(jiǎng)传货。它不僅讓你聲明一個(gè)輸出文件依賴(lài)于一個(gè)（或多個(gè)）輸入文件，而且可以遞歸地進(jìn)行操作宏娄。例如问裕，一個(gè)程序可能依賴(lài)一個(gè)目標(biāo)文件，而目標(biāo)文件又依賴(lài)相應(yīng)的源代碼：
prog: main.o
cc -o prog main.o
main.o: main.c
cc -C -o main.o main.c
make 在下一次調(diào)用時(shí)發(fā)現(xiàn) main.c 源文件的修改時(shí)間比 main.o 更晚孵坚，它不僅會(huì)重建 main.o 對(duì)象文件粮宛，還會(huì)重建 prog 本身。
構(gòu)建系統(tǒng)是分配給本科計(jì)算機(jī)科學(xué)專(zhuān)業(yè)學(xué)生的一個(gè)普通的學(xué)期項(xiàng)目卖宠，這不僅是因?yàn)闃?gòu)建系統(tǒng)幾乎用在所有軟件項(xiàng)目中巍杈，而且因?yàn)闃?gòu)建系統(tǒng)涉及基本數(shù)據(jù)結(jié)構(gòu)和有向圖算法（本文稍后將對(duì)此進(jìn)行詳細(xì)討論）。
在構(gòu)建系統(tǒng)經(jīng)過(guò)數(shù)十年的使用和實(shí)踐之后逗堵，人們可能會(huì)期望它們已完全成為通用的系統(tǒng)秉氧，可以滿足最高的需求。但實(shí)際上蜒秤，構(gòu)建軟件之間的一種常見(jiàn)交互作用（動(dòng)態(tài)交叉引用問(wèn)題）在大多數(shù)構(gòu)建系統(tǒng)中都處理得很差，因此在本文中我們不僅要練習(xí)用于解決 make 的問(wèn)題的經(jīng)典解決方案和數(shù)據(jù)結(jié)構(gòu)亚斋，還要將該解決方案擴(kuò)展到更高需求的領(lǐng)域作媚。
問(wèn)題就是交叉引用，交叉引用出現(xiàn)在哪里帅刊？在文本文檔纸泡、DOC 文檔和印刷書(shū)籍中！
問(wèn)題：構(gòu)建文件系統(tǒng)
從源重建格式化文檔的系統(tǒng)總是做太多或者太少的工作赖瞒。
當(dāng)文檔變動(dòng)很小時(shí)女揭，它們會(huì)讓你等待不相關(guān)的章節(jié)被重新編輯和重新設(shè)置格式，這時(shí)候它們做了太多工作栏饮。但是它們也可能在重新構(gòu)建中做過(guò)少的工作吧兔，給你一個(gè)和要求不一致的最終產(chǎn)品。
考慮一下 Sphinx袍嬉，它是 Python 語(yǔ)言官方文檔和 Python 社區(qū)中許多項(xiàng)目的文檔構(gòu)建器境蔼。Sphinx 項(xiàng)目的 index.rst 通常會(huì)包含一個(gè)目錄表：
Table of Contents
=================
.. toctree::
install.rst
tutorial.rst
api.rst
該章節(jié)文件名列表告訴 Sphinx 在構(gòu)建 index.html 輸出文件時(shí)，需要包括指向三個(gè)章節(jié)中每個(gè)章節(jié)的鏈接伺通。它還將包含指向每一章中任何小節(jié)的鏈接箍土。除去其標(biāo)記，上面的標(biāo)題和 toctree 命令產(chǎn)生的文本可能是：
Table of Contents
? Installation
? Newcomers Tutorial
? Hello, World
? Adding Logging
? API Reference
? Handy Functions
? Obscure Classes
如你所見(jiàn)罐监，此目錄是來(lái)自四個(gè)不同文件的信息的匯總吴藻。雖然其基本順序和結(jié)構(gòu)來(lái)自 index.rst，但每個(gè)章節(jié)的實(shí)際標(biāo)題均從這三章源文件本身中提取弓柱。
如果你考慮修改這個(gè)教程的章節(jié)標(biāo)題沟堡。畢竟侧但，“Newcomer”一詞聽(tīng)起來(lái)很古怪，就像你的用戶是剛來(lái)到 Wyoming 的定居者一樣俊犯。那么你將編輯 tutorial.rst 的第一行來(lái)寫(xiě)出更好的內(nèi)容：
-Newcomers Tutorial
+Beginners Tutorial
==================
Welcome to the tutorial!
This text will take you through the basics of...
當(dāng)你準(zhǔn)備重新構(gòu)建時(shí)，Sphinx 會(huì)做正確的事伤哺！它將重新構(gòu)建教程章節(jié)本身和索引燕侠。（將輸出加入 cat 命令會(huì)使 Sphinx 在單獨(dú)的行上說(shuō)明每個(gè)重新構(gòu)建的文件，而不是使用裸回車(chē)符將這些進(jìn)度更新重復(fù)覆蓋到一行立莉。）
$ make html | cat
writing output... [ 50%] index
writing output... [100%] tutorial
因?yàn)?Sphinx 選擇重新構(gòu)建兩個(gè)文檔绢彤，所以現(xiàn)在除了 tutorial.html 要將其新標(biāo)題放在頂部，index.html 展示的輸出要在目錄中顯示更新的章節(jié)標(biāo)題蜓耻。 Sphinx 已經(jīng)重新構(gòu)建了所有內(nèi)容茫舶，以便輸出保持一致。
如果你對(duì) tutorial.rst 的編輯較小刹淌，該怎么辦饶氏？
Beginners Tutorial
==================
-Welcome to the tutorial!
+Welcome to our project tutorial!
This text will take you through the basics of...
在這種情況下，無(wú)需重新構(gòu)建 index.html有勾，因?yàn)閷?duì)段落內(nèi)部的較小編輯不會(huì)更改目錄中的任何信息疹启。但是事實(shí)證明，Sphinx 不再像前面展示的那樣聰明蔼卡！即使結(jié)果內(nèi)容完全相同喊崖，它也將繼續(xù)執(zhí)行重新構(gòu)建 index.html 的多余工作。
writing output... [ 50%] index
writing output... [100%] tutorial
你可以在 index.html 的“之前”和“之后”版本上運(yùn)行 diff 命令雇逞，以確認(rèn)你的小修改對(duì)首頁(yè)沒(méi)有影響——但是 Sphinx 還是讓你等待它重新構(gòu)建荤懂。
對(duì)于易于編譯的小型文檔你甚至可能沒(méi)有注意到額外的構(gòu)建工作。但是塘砸，當(dāng)你頻繁調(diào)整和編輯冗長(zhǎng)节仿、復(fù)雜的文檔或涉及諸如繪圖或動(dòng)畫(huà)之類(lèi)的多媒體生成的文檔時(shí)，工作流程的延遲會(huì)變得至關(guān)重要谣蠢。雖然 Sphinx 會(huì)在你進(jìn)行一次更改時(shí)努力不重新構(gòu)建每一章粟耻。例如，它沒(méi)有因?yàn)轫憫?yīng)你的 tutorial.rst 編輯而重新構(gòu)建 install.html 或 api.html眉踱，但它所做的超出了必要的范圍挤忙。
事實(shí)證明，Sphinx 甚至?xí)悖河袝r(shí)它做得太少谈喳，給你一個(gè)用戶會(huì)注意到的不一致輸出册烈。
為了查看其中一個(gè)最簡(jiǎn)單的問(wèn)題，請(qǐng)首先在你的 API 文檔的頂部添加一個(gè)交叉引用：
API Reference
=============
+Before reading this, try reading our :doc:`tutorial`!
+
The sections below list every function
and every single class and method offered...
對(duì)于目錄，Sphinx 通常會(huì)格外小心赏僧，將盡職地重新構(gòu)建此 API 參考文檔以及項(xiàng)目的 index.html 主頁(yè)：
writing output... [ 50%] api
writing output... [100%] index
在 api.html 輸出文件中大猛，你可以確認(rèn) Sphinx 是否已將 tutorial 章節(jié)引人入勝的標(biāo)題包含在交叉引用的 anchor 標(biāo)簽中：
<p>Before reading this, try reading our
<a class="reference internal" href="tutorial.html">
<em>Beginners Tutorial</em>
</a>!</p>
如果現(xiàn)在再次對(duì) tutorial.rst 文件頂部的標(biāo)題進(jìn)行編輯怎么辦？你將使三個(gè)輸出文件無(wú)效：
- 現(xiàn)在
tutorial.html頂部的標(biāo)題已過(guò)期淀零，因此需要重新構(gòu)建挽绩。 -
index.html中的目錄仍然具有舊標(biāo)題，因此需要重新構(gòu)建驾中。 -
api.html第一段中嵌入的交叉引用仍然具有舊的章節(jié)標(biāo)題唉堪，還需要重新構(gòu)建。
Sphinx 做了什么肩民？
writing output... [ 50%] index
writing output... [100%] tutorial
哎呀唠亚。
僅重建了兩個(gè)文件，而不是三個(gè)持痰。 Sphinx 無(wú)法正確重新構(gòu)建你的文檔灶搜。
如果現(xiàn)在將 HTML 推送到網(wǎng)絡(luò)，那么用戶將在 api.html 頂部的交叉引用中看到舊標(biāo)題工窍，但一旦鏈接將他們帶到 tutorial.html 本身割卖，便會(huì)看到另一個(gè)標(biāo)題（新標(biāo)題）。Sphinx 支持的多種交叉引用均可能會(huì)發(fā)生這種情況：章標(biāo)題患雏，節(jié)標(biāo)題究珊，段落，類(lèi)纵苛，方法和函數(shù)。
構(gòu)建系統(tǒng)和一致性
上面描述的問(wèn)題并非 Sphinx 特有的言津。它不僅困擾著其它文檔系統(tǒng)（例如 LaTeX）攻人，而且甚至?xí)_那些試圖以古老的 make 編譯的項(xiàng)目，如果它們的資源碰巧進(jìn)行了交叉引用悬槽。
由于該問(wèn)題是古老且普遍存在的怀吻，因此其解決方案的使用壽命也同樣悠長(zhǎng)：
$ rm -r _build/
$ make html
如果刪除所有輸出，則可以保證完全重新構(gòu)建初婆！有些項(xiàng)目甚至將 rm -r 重命名為 clean蓬坡，因此僅需進(jìn)行快速清理就可以清除項(xiàng)目輸出。
通過(guò)消除每個(gè)中間或輸出資源的副本磅叛，龐大的 rm -r 能夠在不緩存任何內(nèi)容的情況下強(qiáng)制重新構(gòu)建屑咳，不會(huì)存儲(chǔ)任何可能會(huì)導(dǎo)致產(chǎn)品過(guò)時(shí)的早期狀態(tài)。
但是弊琴，我們可以開(kāi)發(fā)出更好的方法嗎兆龙？
如果你的構(gòu)建系統(tǒng)是一個(gè)持續(xù)的過(guò)程，當(dāng)它從一個(gè)文檔的源代碼傳遞到另一個(gè)文檔的文本時(shí)敲董，需要注意每個(gè)章節(jié)標(biāo)題和每個(gè)交叉引用的短語(yǔ)紫皇，該怎么辦慰安？它關(guān)于更改單個(gè)源文件后是否需要重新構(gòu)建其他文檔的決定必須是精確的，而不是僅僅憑猜測(cè)聪铺，并且是正確的化焕，而不是使輸出出現(xiàn)不一致?tīng)顟B(tài)。
結(jié)果將是一個(gè)類(lèi)似于舊有的靜態(tài) make 工具的系統(tǒng)铃剔，但是該系統(tǒng)在構(gòu)建文件時(shí)就了解了文件之間的依賴(lài)關(guān)系：在添加撒桨、更新和刪除交叉引用時(shí)動(dòng)態(tài)地添加和刪除了依賴(lài)關(guān)系。
在下面的小節(jié)中番宁，我們將使用 Python 構(gòu)造一個(gè)名為 Contingent 的工具元莫。Contingent 在存在動(dòng)態(tài)依賴(lài)項(xiàng)的情況下保證正確性，同時(shí)執(zhí)行最少的重建步驟蝶押。盡管它可以應(yīng)用于任何問(wèn)題領(lǐng)域踱蠢，但我們將針對(duì)上面提到的一小部分問(wèn)題運(yùn)行它來(lái)解決。
鏈接任務(wù)以制作圖
任何構(gòu)建系統(tǒng)都需要一種鏈接輸入和輸出的方法棋电。例如茎截，在我們上面的討論中，三個(gè)標(biāo)記文本分別產(chǎn)生一個(gè)相應(yīng)的 HTML 輸出文件赶盔。表達(dá)這些關(guān)系最自然的方法是將它們變成一個(gè)框和箭頭（或者用數(shù)學(xué)術(shù)語(yǔ)來(lái)說(shuō)是節(jié)點(diǎn)和邊）組成的圖形企锌。
程序員用來(lái)編寫(xiě)構(gòu)建系統(tǒng)的每種語(yǔ)言都將提供各種數(shù)據(jù)結(jié)構(gòu)，用這些數(shù)據(jù)結(jié)構(gòu)可以表示節(jié)點(diǎn)和邊的圖形于未。
我們?cè)?Python 中如何表示這樣的圖撕攒？
Python 語(yǔ)言通過(guò)直接支持四種通用數(shù)據(jù)結(jié)構(gòu)的語(yǔ)法來(lái)賦予它們優(yōu)先級(jí)。你可以通過(guò)簡(jiǎn)單地在源代碼中鍵入它們的文本表示形式來(lái)創(chuàng)建四大數(shù)據(jù)結(jié)構(gòu)的新實(shí)例烘浦，并且它們四個(gè)類(lèi)型對(duì)象可以作為內(nèi)置符號(hào)抖坪，無(wú)需導(dǎo)入即可使用。
元組(tuple) 是用于保存異構(gòu)數(shù)據(jù)的只讀序列闷叉，元組中的每個(gè)元素通常表示不同的含義擦俐。下面的例子中，元組將主機(jī)名和端口號(hào)放在一起握侧，如果重新排列它將失去其含義：
('dropbox.com', 443)
列表(list) 是一個(gè)用于保存同構(gòu)數(shù)據(jù)的可變序列蚯瞧，每個(gè)項(xiàng)通常具有與其它項(xiàng)有相同的結(jié)構(gòu)和含義。列表既可以保留數(shù)據(jù)的原始輸入順序品擎，也可以重新排列或排序以建立新的更有用的順序埋合。
['C', 'Awk', 'TCL', 'Python', 'JavaScript']
集合(set) 不保留順序。集合僅記住是否已添加給定值孽查，而不記住多少次饥悴，因此可用于從數(shù)據(jù)中刪除重復(fù)項(xiàng)。 例如，以下兩個(gè)集合將各自包含三個(gè)元素：
{3, 4, 5}
{3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 5}
字典dict 是一個(gè)關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)西设，用于存儲(chǔ)通過(guò)鍵可訪問(wèn)的值瓣铣。使用字典，程序員可以選擇對(duì)每個(gè)值進(jìn)行索引的鍵贷揽，而不是像元組和列表那樣使用自動(dòng)整數(shù)索引棠笑。字典的查找由哈希表支持，這意味著無(wú)論字典有十二個(gè)鍵還是一百萬(wàn)個(gè)鍵禽绪，查找都以相同的速度運(yùn)行蓖救。
{'ssh': 22, 'telnet': 23, 'domain': 53, 'http': 80}
Python 靈活性的關(guān)鍵在于這四個(gè)數(shù)據(jù)結(jié)構(gòu)是可以組合的。程序員可以將它們彼此任意嵌套以產(chǎn)生更復(fù)雜的數(shù)據(jù)存儲(chǔ)印屁，其規(guī)則和語(yǔ)法仍然遵循基礎(chǔ)元組循捺，列表，集合和字典中的簡(jiǎn)單規(guī)則雄人。
假設(shè)我們圖的每個(gè)邊都需要至少知道其源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)从橘，那么最簡(jiǎn)單的表示可能就是元組。圖頂部的邊可能看起來(lái)像：
('tutorial.rst', 'tutorial.html')
我們?nèi)绾未鎯?chǔ)多個(gè)邊础钠？雖然我們最初的想法可能是將所有邊元組都放入一個(gè)列表中恰力，但這會(huì)有一些不利條件。列表很小心地保持順序旗吁，但是圖形中邊的絕對(duì)順序是沒(méi)有意義的踩萎。即使我們只希望能夠在 tutorial.rst 和 tutorial.html 之間繪制單個(gè)箭頭，列表也會(huì)保存完全相同的邊的多個(gè)副本很钓。因此香府，正確的選擇是集合，這樣我們將上圖表示為：
{('tutorial.rst', 'tutorial.html'),
('index.rst', 'index.html'),
('api.rst', 'api.html')}
這允許我們?cè)谒羞吷线M(jìn)行快速迭代码倦、對(duì)單個(gè)邊進(jìn)行快速的插入和刪除操作以及快速檢查特定的邊是否存在回还。
當(dāng)然，我們需要做的操作不止這些叹洲。
像 Contingent 這樣的構(gòu)建系統(tǒng)需要了解給定節(jié)點(diǎn)與連接到該節(jié)點(diǎn)的所有節(jié)點(diǎn)之間的關(guān)系。例如工禾，當(dāng) api.rst 發(fā)生更改時(shí)运提，Contingent 需要知道該更改會(huì)影響哪些資源，以最大程度地減少要執(zhí)行的工作闻葵，同時(shí)確保完整的構(gòu)建民泵。要回答這個(gè)問(wèn)題：“ api.rst 下游有哪些節(jié)點(diǎn)？” 槽畔，我們需要檢查 api.rst 傳出的邊栈妆。
但是構(gòu)建依賴(lài)關(guān)系圖要求 Contingent 也要考慮節(jié)點(diǎn)的輸入。例如，當(dāng)構(gòu)建系統(tǒng)組裝輸出文檔 tutorial.html 時(shí)鳞尔，使用了哪些輸入嬉橙？通過(guò)觀察每個(gè)節(jié)點(diǎn)的輸入，Contingent 可以知道 api.html 依賴(lài)于 api.rst寥假，而 tutorial.html 則沒(méi)有市框。當(dāng)源發(fā)生更改并進(jìn)行重新構(gòu)建時(shí)，Contingent 會(huì)重新構(gòu)建每個(gè)更改的節(jié)點(diǎn)的輸入邊糕韧，以刪除不再使用的邊枫振，并重新了解這次任務(wù)使用的資源。
我們的元組集合很難解決這些問(wèn)題中的任何一個(gè)萤彩。如果我們需要了解 api.html 與圖的其余部分之間的關(guān)系粪滤，則需要遍歷整個(gè)集合以查找在 api.html 節(jié)點(diǎn)處開(kāi)始或結(jié)束的邊。
像 Python 的字典這樣的關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)將允許直接從特定節(jié)點(diǎn)查找所有邊雀扶，從而使這個(gè)問(wèn)題變得更加容易：
{'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')}}
現(xiàn)在查找特定節(jié)點(diǎn)的邊會(huì)非痴刃。快，代價(jià)是必須將每條邊存儲(chǔ)兩次：一次存儲(chǔ)在一組傳入邊中怕吴，一次存儲(chǔ)在一組傳出邊中窍侧。但是每一組中的邊都必須手動(dòng)檢查，看哪些是傳入的转绷，哪些是傳出的伟件。在節(jié)點(diǎn)的邊集中反復(fù)命名節(jié)點(diǎn)也有點(diǎn)多余。
解決這兩個(gè)問(wèn)題的方法是將傳入和傳出的邊放在它們各自獨(dú)立的數(shù)據(jù)結(jié)構(gòu)中议经，這也就免除了我們?cè)诿總€(gè)節(jié)點(diǎn)的相關(guān)邊中都必須反復(fù)提到節(jié)點(diǎn)斧账。
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'},
}
請(qǐng)注意，outgoing 直接用 Python 語(yǔ)法表示我們?cè)谇懊鎴D中繪制的內(nèi)容：左側(cè)的源文檔將由構(gòu)建系統(tǒng)轉(zhuǎn)換為右側(cè)的輸出文檔煞肾。對(duì)于這個(gè)簡(jiǎn)單的示例咧织，每個(gè)源只指向一個(gè)輸出，所有輸出集只有一個(gè)元素籍救，但是我們將很快看到一個(gè)輸入節(jié)點(diǎn)具有多個(gè)下游結(jié)果的示例习绢。
在這個(gè)字典的集合數(shù)據(jù)結(jié)構(gòu)中，每個(gè)邊都會(huì)被表示兩次蝙昙，一次作為一個(gè)節(jié)點(diǎn)的輸出邊(tutorial.rst → tutorial.html)又一次成為另一個(gè)的邊緣(tutorial.html ← tutorial.rst). 這兩種表示精確地捕捉到相同的關(guān)系闪萄，只是從邊兩端的兩個(gè)節(jié)點(diǎn)的相反角度。但作為這種冗余的回報(bào)奇颠，這種數(shù)據(jù)結(jié)構(gòu)支持 Contingent 需要的快速查找败去。
類(lèi)的正確使用
你可能會(huì)對(duì)上面討論的 Python 數(shù)據(jù)結(jié)構(gòu)中缺少類(lèi)感到驚訝。畢竟烈拒，類(lèi)是構(gòu)建應(yīng)用程序的一種常見(jiàn)機(jī)制圆裕，也是其擁護(hù)者和批評(píng)者之間激烈辯論的一個(gè)常見(jiàn)主題广鳍。類(lèi)曾經(jīng)被認(rèn)為是非常重要的，以至于整個(gè)教育課程都圍繞著它們而設(shè)計(jì)吓妆，而大多數(shù)流行的編程語(yǔ)言都包含了定義和使用它們的專(zhuān)用語(yǔ)法赊时。
但事實(shí)證明，類(lèi)通常與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)問(wèn)題相關(guān)耿战。類(lèi)不是為我們提供一個(gè)完全替代的數(shù)據(jù)建模范式蛋叼，而是簡(jiǎn)單地重復(fù)我們已經(jīng)看到的數(shù)據(jù)結(jié)構(gòu)：
- 一個(gè)類(lèi)實(shí)例被實(shí)現(xiàn)為dict。
- 一個(gè)類(lèi)實(shí)例就像可變?cè)M一樣使用剂陡。
類(lèi)通過(guò)一個(gè)更優(yōu)雅的語(yǔ)法提供鍵查找狈涮，在這里你可以使用 graph.incoming 而不是 graph["incoming"]。但是鸭栖，在實(shí)踐中歌馍，類(lèi)實(shí)例幾乎從未被用作通用鍵值存儲(chǔ)。相反晕鹊，它們被用來(lái)按屬性名組織相關(guān)但異構(gòu)的數(shù)據(jù)松却，將細(xì)節(jié)封裝在接口后面。
因此溅话，不需要將主機(jī)名和端口號(hào)放在一個(gè)元組中晓锻，并且不必記住哪個(gè)是第一個(gè)，哪個(gè)是第二個(gè)飞几，而是創(chuàng)建一個(gè) Address 類(lèi)砚哆，該類(lèi)的每個(gè)實(shí)例都有一個(gè) host 屬性和一個(gè) port 屬性。然后屑墨，你可以將 Address 對(duì)象傳遞到原本有匿名元組的位置躁锁。代碼變得更易于閱讀和編寫(xiě)。但是使用類(lèi)實(shí)例并不會(huì)真正改變我們?cè)谶M(jìn)行數(shù)據(jù)設(shè)計(jì)時(shí)遇到的任何問(wèn)題卵史；它只是提供了一個(gè)更優(yōu)雅战转、更不匿名的容器。
因此以躯，類(lèi)的真正價(jià)值并不在于它們改變了數(shù)據(jù)設(shè)計(jì)的科學(xué)性槐秧。類(lèi)的價(jià)值在于，它們?cè)试S你對(duì)程序的其余部分隱藏?cái)?shù)據(jù)設(shè)計(jì)忧设！
成功的應(yīng)用程序設(shè)計(jì)取決于我們能否利用 Python 提供的強(qiáng)大的內(nèi)置數(shù)據(jù)結(jié)構(gòu)色鸳，同時(shí)盡可能減少我們?cè)谌魏螘r(shí)候需要記住的細(xì)節(jié)。類(lèi)提供了解決這種明顯的困境的機(jī)制：有效地使用见转，類(lèi)提供了圍繞系統(tǒng)總體設(shè)計(jì)的一些小子集的外觀。當(dāng)我們?cè)谝粋€(gè)子集（例如 Graph）中工作時(shí)蒜哀，只要我們能記住它們的接口斩箫，我們就可以忘記其它子集的實(shí)現(xiàn)細(xì)節(jié)吏砂。通過(guò)這種方式，程序員在編寫(xiě)系統(tǒng)的過(guò)程中經(jīng)常會(huì)發(fā)現(xiàn)自己在幾個(gè)抽象層次之間導(dǎo)航乘客，現(xiàn)在使用特定子系統(tǒng)的特定數(shù)據(jù)模型和實(shí)現(xiàn)細(xì)節(jié)狐血，通過(guò)接口連接更高級(jí)的概念。
例如易核，從外部看匈织，代碼可以簡(jiǎn)單地請(qǐng)求一個(gè)新的 Graph 實(shí)例：
>>> from contingent import graphlib
>>> g = graphlib.Graph()
不需要了解 Graph 如何工作的細(xì)節(jié)。簡(jiǎn)單使用圖的代碼在操作圖時(shí)（如添加邊或執(zhí)行其他操作時(shí)）只看到接口動(dòng)詞（方法調(diào)用）：
>>> g.add_edge('index.rst', 'index.html')
>>> g.add_edge('tutorial.rst', 'tutorial.html')
>>> g.add_edge('api.rst', 'api.html')
細(xì)心的讀者會(huì)注意到牡直，我們?cè)跊](méi)有顯式地創(chuàng)建“節(jié)點(diǎn)”和“邊”對(duì)象的情況下向圖中添加了邊缀匕，并且這些早期示例中的節(jié)點(diǎn)本身只是字符串。來(lái)自其它語(yǔ)言和傳統(tǒng)碰逸，人們可能期望看到系統(tǒng)中所有內(nèi)容的用戶定義類(lèi)和接口：
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 語(yǔ)言和社區(qū)明確而有意地強(qiáng)調(diào)使用簡(jiǎn)單的通用數(shù)據(jù)結(jié)構(gòu)來(lái)解決問(wèn)題乡小，而不是為我們想要處理的問(wèn)題的每一分鐘細(xì)節(jié)創(chuàng)建自定義類(lèi)。這是“Pythonic”解決方案概念的一個(gè)方面：Pythonic 解決方案試圖最大程度的減少語(yǔ)法開(kāi)銷(xiāo)饵史，并利用 Python 強(qiáng)大的內(nèi)置工具和廣泛的標(biāo)準(zhǔn)庫(kù)满钟。
考慮到這些因素，讓我們回到 Graph 類(lèi)胳喷，檢查它的設(shè)計(jì)和實(shí)現(xiàn)湃番，看看數(shù)據(jù)結(jié)構(gòu)和類(lèi)接口之間的相互作用。當(dāng)構(gòu)建一個(gè)新的 Graph 實(shí)例時(shí)吭露，已經(jīng)使用我們?cè)谏弦还?jié)中概述的邏輯構(gòu)建了一對(duì)字典來(lái)存儲(chǔ)邊：
class Graph:
"""構(gòu)建任務(wù)之間關(guān)系的有向圖"""
def __init__(self):
self._inputs_of = defaultdict(set)
self._consequences_of = defaultdict(set)
屬性名 _inputs_of 和 _consequences_of 前面的前導(dǎo)下劃線在 Python 社區(qū)中用來(lái)表示屬性是私有的吠撮。這種約定是社區(qū)建議程序員通過(guò)空間和時(shí)間相互傳遞消息和警告的一種方式。認(rèn)識(shí)到需要標(biāo)記公共對(duì)象屬性和內(nèi)部對(duì)象屬性之間的差異奴饮，社區(qū)采用了單一的前導(dǎo)下劃線作為其它程序員（包括未來(lái)的我們自己）的簡(jiǎn)潔一致的指示符纬向，即屬性最好作為類(lèi)的不可見(jiàn)內(nèi)部機(jī)制的一部分來(lái)處理。
為什么我們要使用 defaultdict 而不是標(biāo)準(zhǔn) dict戴卜？在使用其它數(shù)據(jù)結(jié)構(gòu)編寫(xiě) dict 時(shí)逾条，一個(gè)常見(jiàn)的問(wèn)題是處理缺少的鍵。對(duì)于普通 dict投剥，檢索不存在的鍵會(huì)引發(fā) KeyError：
>>> consequences_of = {}
>>> consequences_of['index.rst'].add('index.html')
Traceback (most recent call last):
...
KeyError: 'index.rst'
使用普通 dict 需要在整個(gè)代碼中進(jìn)行特殊檢查师脂，以處理此特定情況，例如添加新邊時(shí)：
# 處理 “我們還未見(jiàn)過(guò)此任務(wù)” 特殊場(chǎng)景:
if input_task not in self._consequences_of:
self._consequences_of[input_task] = set()
self._consequences_of[input_task].add(consequence_task)
這種需求是如此普遍江锨，以至于 Python 包含一個(gè)特殊的工具 defaultdict吃警，它使你可以提供一個(gè)返回缺少鍵值的函數(shù)。當(dāng)我們?cè)儐?wèn)圖尚未看到的邊時(shí)啄育，我們將獲得一個(gè)空集而不是一個(gè)異常：
>>> from collections import defaultdict
>>> consequences_of = defaultdict(set)
>>> consequences_of['api.rst']
set()
以這種方式構(gòu)建我們的實(shí)現(xiàn)意味著每個(gè)鍵的首次使用看起來(lái)與第二次及以后相同：
>>> consequences_of['index.rst'].add('index.html')
>>> 'index.html' in consequences_of['index.rst']
True
基于這些技術(shù)酌心，讓我們研究一下 add_edge 的實(shí)現(xiàn)，我們前面用它來(lái)構(gòu)建圖挑豌。
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)
這種方法隱藏了以下事實(shí)，即每個(gè)新邊需要兩個(gè)而不是一個(gè)存儲(chǔ)步驟侯勉，這樣我們就可以從兩個(gè)方向知道它鹦筹。請(qǐng)注意 add_edge() 不知道或不關(guān)心之前是否看到過(guò)這兩個(gè)節(jié)點(diǎn)。因?yàn)檩斎牒徒Y(jié)果數(shù)據(jù)結(jié)構(gòu)都是一個(gè) defaultdict(set)址貌，add_edge() 方法不知道節(jié)點(diǎn)是新的铐拐，defaultdict 通過(guò)動(dòng)態(tài)創(chuàng)建一個(gè)新的 set 對(duì)象來(lái)處理差異。正如我們?cè)谏厦婵吹降牧范裕绻皇褂?defaultdict遍蟋，add_edge() 將延長(zhǎng)三倍。更重要的是锹淌，理解和解釋結(jié)果代碼將更加困難匿值。這個(gè)實(shí)現(xiàn)展示了一種解決問(wèn)題的 Pythonic 風(fēng)格方法：簡(jiǎn)單、直接和簡(jiǎn)潔赂摆。
還應(yīng)向調(diào)用方提供訪問(wèn)每個(gè)邊的簡(jiǎn)單方法挟憔，而不必學(xué)習(xí)如何遍歷我們的數(shù)據(jù)結(jié)構(gòu)：
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])]
這個(gè) Graph.sorted() 方法嘗試按自然排序順序（如字母順序）對(duì)節(jié)點(diǎn)進(jìn)行排序，這樣可以為用戶提供穩(wěn)定的輸出順序烟号。
通過(guò)使用這種遍歷方法绊谭，我們可以看到，在前面的三個(gè)“add”方法調(diào)用之后汪拥，g現(xiàn)在表示與上圖中看到的相同的圖达传。
>>> from pprint import pprint
>>> pprint(g.edges())
[('api.rst', 'api.html'),
('index.rst', 'index.html'),
('tutorial.rst', 'tutorial.html')]
我們現(xiàn)在有了一個(gè)真實(shí)的 Python 對(duì)象，而不僅僅是一個(gè)圖迫筑，我們可以問(wèn)它有趣的問(wèn)題宪赶！例如，當(dāng) Contingent 從源文件構(gòu)建博客時(shí)脯燃，它需要知道諸如“什么依賴(lài) api.rst搂妻？”之類(lèi)的信息。當(dāng) api.rst 的內(nèi)容發(fā)生變化時(shí)：
>>> g.immediate_consequences_of('api.rst')
['api.html']
Graph 告訴 Contingent辕棚，當(dāng) api.rst 變化時(shí)欲主，api.html 文件現(xiàn)在已經(jīng)過(guò)時(shí)，必須重新構(gòu)建逝嚎。
index.html 呢扁瓢？
>>> g.immediate_consequences_of('index.html')
[]
返回了一個(gè)空列表，表示 index.html 位于圖的右邊补君，因此如果更改引几，則無(wú)需再重新構(gòu)建。由于已經(jīng)進(jìn)行了數(shù)據(jù)布局工作挽铁，因此可以非常簡(jiǎn)單地表示此查詢：
def immediate_consequences_of(self, task):
"""返回使用 task 作為輸入的任務(wù)"""
return self.sorted(self._consequences_of[task])
>>> from contingent.rendering import as_graphviz
>>> open('figure1.dot', 'w').write(as_graphviz(g)) and None
上圖忽略了我們?cè)诒疚拈_(kāi)頭部分發(fā)現(xiàn)的一個(gè)最重要的關(guān)系：文檔標(biāo)題在目錄中的顯示方式伟桅。讓我們把這個(gè)細(xì)節(jié)填一下硅堆。我們將為每個(gè)需要通過(guò)解析輸入文件生成的標(biāo)題字符串創(chuàng)建一個(gè)節(jié)點(diǎn)，然后傳遞給其他例程之一：
>>> 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')
結(jié)果是一個(gè)圖贿讹，這可以很好地處理重新構(gòu)建我們?cè)诒疚拈_(kāi)頭討論過(guò)的目錄。
這本手冊(cè)演示了我們最終將讓 Contingent 為我們做什么：圖 g 捕捉了項(xiàng)目文檔中各種工件的輸入和結(jié)果够掠。
學(xué)習(xí)聯(lián)系
我們現(xiàn)在有了一種方法讓 Contingent 跟蹤任務(wù)以及它們之間的關(guān)系民褂。如果我們仔細(xì)看一下圖2，然而朝巫，我們看到它實(shí)際上有點(diǎn)波折和模糊：api.rst 是如何產(chǎn)生 api.html 的盅安？我們?nèi)绾沃?index.html 需要 tutorial中的標(biāo)題嗎碧注？這種依賴(lài)關(guān)系是如何解決的？
當(dāng)我們手動(dòng)構(gòu)建結(jié)果圖時(shí)哭廉，我們對(duì)這些想法的直覺(jué)概念起到了作用，但不幸的是相叁，計(jì)算機(jī)并不是非常直觀遵绰，所以我們需要更精確地了解我們想要的東西。
從數(shù)據(jù)源生成輸出需要哪些步驟增淹？這些步驟是如何定義和執(zhí)行的椿访？ Contingent 如何知道它們之間的聯(lián)系？
在 Contingent 中虑润，構(gòu)建任務(wù)被建模為函數(shù)加參數(shù)成玫。這些函數(shù)定義了特定項(xiàng)目理解如何執(zhí)行的動(dòng)作。這些參數(shù)提供了具體的細(xì)節(jié)：應(yīng)該讀取哪個(gè)源文檔拳喻，需要哪個(gè)博客標(biāo)題哭当。當(dāng)它們運(yùn)行時(shí)，這些函數(shù)可能依次調(diào)用其他任務(wù)函數(shù)冗澈，傳遞它們需要答案的任何參數(shù)钦勘。
為了了解這是如何工作的，我們現(xiàn)在將實(shí)現(xiàn)本文開(kāi)頭描述的文檔生成器渗柿。為了防止我們陷入一堆細(xì)節(jié)的泥潭中个盆，我們將使用簡(jiǎn)化的輸入和輸出文檔格式。我們的輸入文檔將由第一行的標(biāo)題組成朵栖，其余部分構(gòu)成正文颊亮。交叉引用只是反引號(hào)包含的源文件，輸出時(shí)用輸出中相應(yīng)文檔的標(biāo)題替換陨溅。
下面是我們示例的 index.txt, api.txt 和 tutorial.txt 的內(nèi)容终惑，說(shuō)明我們的小文檔格式的標(biāo)題、文檔正文的交叉引用：
>>> 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.
... """
既然我們有一些源材料可以使用门扇，那么一個(gè)基于 Contingent 的博客構(gòu)建器需要什么功能呢雹有？
在上面的簡(jiǎn)單示例中偿渡，HTML 輸出文件直接從源代碼開(kāi)始，但在實(shí)際系統(tǒng)中霸奕，將源代碼轉(zhuǎn)換為標(biāo)記需要幾個(gè)步驟：從磁盤(pán)讀取原始文本溜宽，將文本解析為方便的內(nèi)部表示形式，處理作者可能指定的任何指令质帅，解析交叉引用或其他外部依賴(lài)項(xiàng)（如 include 文件）适揉，并應(yīng)用一個(gè)或多個(gè)視圖轉(zhuǎn)換來(lái)將內(nèi)部表示形式轉(zhuǎn)換為其輸出形式。
Contingent 通過(guò)將任務(wù)分組到一個(gè) Project 中來(lái)管理任務(wù)煤惩，Project 是一種構(gòu)建系統(tǒng)的工具嫉嘀，將自身注入到構(gòu)建過(guò)程中間，并記錄每次一個(gè)任務(wù)與另一個(gè)任務(wù)之間的關(guān)系圖魄揉，以構(gòu)建所有任務(wù)之間的關(guān)系圖剪侮。
>>> from contingent.projectlib import Project, Task
>>> project = Project()
>>> task = project.task
本文開(kāi)頭給出的示例的構(gòu)建系統(tǒng)可能涉及一些任務(wù)。
我們的 read() 任務(wù)將假裝從磁盤(pán)讀取文件洛退。由于我們?cè)谧兞恐卸x了源文本瓣俯，因此只需將文件名轉(zhuǎn)換為相應(yīng)的文本即可。
>>> filesystem = {'index.txt': index,
... 'tutorial.txt': tutorial,
... 'api.txt': api}
...
>>> @task
... def read(filename):
... return filesystem[filename]
parse() 任務(wù)根據(jù)文檔格式的規(guī)范解釋文件內(nèi)容的原始文本不狮。我們的格式非常簡(jiǎn)單：文檔的標(biāo)題出現(xiàn)在第一行降铸，其余內(nèi)容被視為文檔的正文。
>>> @task
... def parse(filename):
... lines = read(filename).strip().splitlines()
... title = lines[0]
... body = '\n'.join(lines[
由于格式非常簡(jiǎn)單摇零，所以解析器有點(diǎn)笨推掸，但它說(shuō)明了解析器需要執(zhí)行的解釋責(zé)任。（一般來(lái)說(shuō)驻仅，解析是一個(gè)非常有趣的主題谅畅，很多書(shū)籍都有部分或完全關(guān)于它的內(nèi)容。）在 Sphinx 這樣的系統(tǒng)中噪服，解析器必須理解系統(tǒng)定義的許多標(biāo)記毡泻、指令和命令，將輸入文本轉(zhuǎn)換成系統(tǒng)其他部分可以處理的內(nèi)容粘优。
請(qǐng)注意 parse() 和 read() 之間的連接點(diǎn)仇味，解析的第一個(gè)任務(wù)是將已提供的文件名傳遞給 read()，后者查找并返回該文件的內(nèi)容雹顺。
指定源文件名的 title_of() 任務(wù)返回文檔的標(biāo)題：
>>> @task
... def title_of(filename):
... title, body = parse(filename)
... return title
這個(gè)任務(wù)很好地說(shuō)明了文檔處理系統(tǒng)各個(gè)部分之間的職責(zé)分離丹墨。title_of() 函數(shù)直接從文檔的內(nèi)存表示（在本例中是元組）中工作，而不是利用它自己重新解析整個(gè)文檔來(lái)查找標(biāo)題嬉愧。parse() 函數(shù)根據(jù)系統(tǒng)規(guī)范的約定單獨(dú)生成內(nèi)存中的表示形式贩挣，而其它博客構(gòu)建器處理函數(shù)如 title_of() 只使用其輸出作為其權(quán)限。
如果你習(xí)慣了傳統(tǒng)的面向?qū)ο螅@種面向功能的設(shè)計(jì)可能看起來(lái)有點(diǎn)奇怪王财。在 OO 解決方案中卵迂，parse() 將返回某種 Document 對(duì)象，該對(duì)象的 title_of() 作為方法或?qū)傩匀蘧弧?shí)際上见咒，Sphinx 就是這樣工作的：它的 Parser 子系統(tǒng)生成一個(gè)“Docutils 文檔樹(shù)”對(duì)象，供系統(tǒng)的其他部分使用挂疆。
對(duì)于這些不同的設(shè)計(jì)范例论颅，Contingent 并不固執(zhí)己見(jiàn)，同樣支持這兩種方法囱嫩。在本章中我們將保持簡(jiǎn)單。
最后一個(gè)任務(wù) render() 將文檔的內(nèi)存表示形式轉(zhuǎn)換為輸出形式漏设。實(shí)際上墨闲，它是 parse() 的逆函數(shù)。parse() 獲取符合規(guī)范的輸入文檔并將其轉(zhuǎn)換為內(nèi)存中的表示形式郑口，render() 則獲取內(nèi)存中的表示形式并生成符合某種規(guī)范的輸出文檔鸳碧。
>>> 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)
下面是一個(gè)運(yùn)行示例，它將調(diào)用上述邏輯的每個(gè)階段犬性，渲染 tutorial.txt 以產(chǎn)生輸出：
>>> print(render('tutorial.txt'))
<h1>Beginners Tutorial</h1>
<p>
Welcome to the tutorial!
We hope you enjoy it.
<p>
下面展示了任務(wù)圖瞻离，該圖以傳遞方式連接生成輸出所需的所有任務(wù)，從讀取輸入文件到解析和轉(zhuǎn)換文檔乒裆，并呈現(xiàn)文檔：
事實(shí)證明套利，上圖不是手繪的，而是直接從 Contingent 中產(chǎn)生的鹤耍！Project 對(duì)象可以構(gòu)建此圖肉迫，因?yàn)樗S護(hù)自己的調(diào)用堆棧，類(lèi)似于 Python 維護(hù)的實(shí)時(shí)執(zhí)行幀堆棧稿黄，以便在當(dāng)前函數(shù)返回時(shí)記住哪個(gè)函數(shù)要繼續(xù)運(yùn)行喊衫。
每次調(diào)用一個(gè)新任務(wù)時(shí)，Contingent 可以假定它已經(jīng)被當(dāng)前位于堆棧頂部的任務(wù)調(diào)用杆怕，并且它的輸出將被使用族购。維護(hù)堆棧需要圍繞任務(wù) T 的調(diào)用執(zhí)行幾個(gè)額外的步驟：
- 把 T 推入棧上。
- 執(zhí)行 T陵珍，讓它調(diào)用它需要的任何其它任務(wù)寝杖。
- 從堆棧中彈出 T。
- 返回其結(jié)果撑教。
為了攔截任務(wù)調(diào)用朝墩，Project 利用了 Python 的一個(gè)關(guān)鍵特性：函數(shù)裝飾器。在定義函數(shù)時(shí)，允許裝飾器處理或轉(zhuǎn)換該函數(shù)收苏。Project.task 裝飾器利用此機(jī)會(huì)將每個(gè)任務(wù)打包到另一個(gè)函數(shù)（包裝器）中亿卤，這使包裝器（它將代表 Project 關(guān)注圖和堆棧管理）與關(guān)注文檔處理的任務(wù)函數(shù)之間的職責(zé)明確分離。任務(wù)裝飾器樣板如下所示：
from functools import wraps
def task(function):
@wraps(function)
def wrapper(*args):
# wrapper 正文,會(huì)調(diào)用 function()
return wrapper
這是一個(gè)典型的 Python 裝飾器聲明鹿霸。然后排吴，可以通過(guò)在創(chuàng)建函數(shù)的 def 頂部的 @ 字符將其命名為函數(shù)：
@task
def title_of(filename):
title, body = parse(filename)
return title
完成此定義后，名稱(chēng) title_of 將引用函數(shù)的包裝版本懦鼠。包裝器可以通過(guò)名稱(chēng) function 訪問(wèn)函數(shù)的原始版本钻哩，并在適當(dāng)?shù)臅r(shí)候調(diào)用它。Contingent 包裝器的主體運(yùn)行如下內(nèi)容：
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
此包裝器執(zhí)行幾個(gè)關(guān)鍵的維護(hù)步驟：
- 為了方便起見(jiàn)肛冶，將任務(wù)（一個(gè)函數(shù)及其參數(shù)）打包到一個(gè)小對(duì)象中街氢。此處的
wrapper為任務(wù)函數(shù)的包裝版本命名。 - 如果此任務(wù)已由當(dāng)前正在運(yùn)行的任務(wù)調(diào)用睦袖，請(qǐng)?zhí)砑右粋€(gè)邊以捕獲此任務(wù)是已運(yùn)行任務(wù)的輸入這一事實(shí)珊肃。
- 忘記我們上次所學(xué)的關(guān)于這個(gè)任務(wù)的任何東西，因?yàn)檫@次可能會(huì)做出新的決定——例如馅笙，如果 API 指南的源文本不再提及 Tutorial伦乔，則其
render()將不再要求 Tutorial 文檔的title_of()。 - 將此任務(wù)推入任務(wù)堆棧的頂部董习，以防它在執(zhí)行工作的過(guò)程中調(diào)用其它任務(wù)烈和。
- 調(diào)用
try...finally塊中的任務(wù)，該塊確保我們正確地從堆棧中移除已完成的任務(wù)皿淋，即使它因引發(fā)異常而死亡招刹。 - 返回任務(wù)的返回值，以使此包裝器的調(diào)用者無(wú)法判斷他們沒(méi)有簡(jiǎn)單地調(diào)用普通任務(wù)函數(shù)本身窝趣。
步驟4和5維護(hù)任務(wù)堆棧本身蔗喂，然后由步驟2使用它來(lái)執(zhí)行結(jié)果跟蹤，這是我們首先構(gòu)建任務(wù)堆棧的全部原因高帖。
由于每個(gè)任務(wù)都被它自己的包裝器函數(shù)副本包圍缰儿，所以僅僅調(diào)用和執(zhí)行正常的任務(wù)堆棧就會(huì)產(chǎn)生一個(gè)關(guān)系圖，這是一個(gè)不可見(jiàn)的副作用散址。這就是為什么我們?cè)诙x的每個(gè)處理步驟周?chē)?jǐn)慎地使用包裝器：
@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
感謝這些包裝器乖阵，當(dāng)我們調(diào)用 parse('tutorial.txt') 時(shí)，裝飾器學(xué)習(xí)了 parse 和 read 之間的聯(lián)系预麸。我們可以通過(guò)構(gòu)建另一個(gè) Task 元組并詢問(wèn)如果其輸出值發(fā)生變化會(huì)產(chǎn)生什么后果來(lái)詢問(wèn)這種關(guān)系：
>>> task = Task(read, ('tutorial.txt',))
>>> print(task)
read('tutorial.txt')
>>> project._graph.immediate_consequences_of(task)
[parse('tutorial.txt')]
重讀 tutorial.txt 文件并發(fā)現(xiàn)其內(nèi)容已更改的結(jié)果是我們需要重新執(zhí)行該文檔的 parse() 例程瞪浸。如果我們渲染整個(gè)文檔集會(huì)怎么樣？Contingent 能夠?qū)W習(xí)整個(gè)構(gòu)建過(guò)程嗎吏祸？
>>> 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>
成功了对蒲！從輸出中，我們可以看到，我們的轉(zhuǎn)換用文檔標(biāo)題代替了源文檔中的指令蹈矮，這表明 Contingent 能夠發(fā)現(xiàn)構(gòu)建文檔所需的各種任務(wù)之間的聯(lián)系砰逻。
通過(guò)觀察一個(gè)任務(wù)通過(guò) task 包裝器調(diào)用另一個(gè)任務(wù)，Project 已經(jīng)自動(dòng)學(xué)習(xí)了輸入和結(jié)果的圖泛鸟。因?yàn)樗幸粋€(gè)完整的結(jié)果圖可供使用蝠咆，所以如果任何任務(wù)的輸入發(fā)生變化，Contingent 都知道需要重建的所有內(nèi)容北滥。
追趕結(jié)果
一旦初始構(gòu)建運(yùn)行到完成刚操，Contingent 需要監(jiān)視輸入文件的更改。當(dāng)用戶完成新的編輯并運(yùn)行“保存”時(shí)再芋，需要調(diào)用 read() 方法及其結(jié)果菊霜。
這將要求我們按照與創(chuàng)建圖時(shí)相反的順序來(lái)遍歷圖。你還記得济赎，它是通過(guò)為 API 引用調(diào)用 render() 并調(diào)用 parse() 最終調(diào)用 read() 任務(wù)而構(gòu)建的≌嘉裕現(xiàn)在我們轉(zhuǎn)向另一個(gè)方向：我們知道 read() 現(xiàn)在將返回新內(nèi)容，我們需要弄清楚下游將產(chǎn)生什么結(jié)果联喘。
編譯結(jié)果的過(guò)程是一個(gè)遞歸的過(guò)程，因?yàn)槊總€(gè)結(jié)果本身都可以有依賴(lài)它的任務(wù)辙纬。我們可以通過(guò)重復(fù)調(diào)用圖來(lái)手動(dòng)執(zhí)行這種遞歸豁遭。（請(qǐng)注意，我們?cè)谶@里利用了這樣一個(gè)事實(shí)：Python 提示符保存了最后一個(gè)顯示在名稱(chēng) _下的值贺拣，以便在后續(xù)表達(dá)式中使用蓖谢。）
>>> 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)
[]
這種反復(fù)查找直接結(jié)果的遞歸任務(wù)，只有在我們到達(dá)沒(méi)有進(jìn)一步結(jié)果的任務(wù)時(shí)才停止譬涡，這是一個(gè)足夠基本的圖操作闪幽，它由 Graph 類(lèi)上的方法直接支持：
>>> # 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')]
事實(shí)上，recursive_consequences_of() 試圖更聰明一點(diǎn)涡匀。如果某個(gè)特定任務(wù)作為其它幾個(gè)任務(wù)的下游結(jié)果重復(fù)出現(xiàn)盯腌，則應(yīng)注意在輸出列表中僅提及一次，并將其移到接近末尾的位置陨瘩，以便它只出現(xiàn)在作為其輸入的任務(wù)之后腕够。這種智能由拓?fù)渑判虻慕?jīng)典深度優(yōu)先實(shí)現(xiàn)提供支持，這該法通過(guò)一個(gè)隱藏的遞歸輔助函數(shù)并用 Python 編寫(xiě)舌劳。請(qǐng)查看 graphlib.py 源代碼以獲取細(xì)節(jié)帚湘。
如果在檢測(cè)到變化后，我們小心地在遞歸結(jié)果中重新運(yùn)行每一個(gè)任務(wù)甚淡，那么 Contingent 將能夠避免重建太少大诸。然而，我們的第二個(gè)挑戰(zhàn)是避免重建過(guò)多。請(qǐng)?jiān)俅螀㈤唸D4资柔，我們希望避免每次 tutorial.txt 更改都重建這三個(gè)文檔焙贷，因?yàn)榇蠖鄶?shù)編輯可能不會(huì)影響其標(biāo)題，而只影響其正文建邓。如何做到這一點(diǎn)盈厘？
解決方案是使圖的重新計(jì)算依賴(lài)于緩存。當(dāng)逐步處理更改的遞歸結(jié)果時(shí)官边，我們將只調(diào)用輸入與上次不同的任務(wù)沸手。
此優(yōu)化將涉及最終的數(shù)據(jù)結(jié)構(gòu)。我們將為 Project 提供一個(gè) _todo 集合注簿，用它來(lái)記住至少有一個(gè)輸入值已更改因此需要重新執(zhí)行的任務(wù)契吉。因?yàn)橹挥?_todo 中的任務(wù)過(guò)期，構(gòu)建過(guò)程可以跳過(guò)運(yùn)行任何出現(xiàn)在那里的任務(wù)诡渴。
同樣捐晶，Python 方便統(tǒng)一的設(shè)計(jì)使得這些特性非常容易編寫(xiě)代碼。因?yàn)槿蝿?wù)對(duì)象是可散列的妄辩，所以 _todo 可以是一個(gè)通過(guò)標(biāo)識(shí)記住任務(wù)項(xiàng)的 set 集合惑灵，保證任務(wù)永遠(yuǎn)不會(huì)出現(xiàn)兩次，而以前運(yùn)行的返回值的 _cache 可以是一個(gè)以任務(wù)為鍵的 dict眼耀。
更準(zhǔn)確地說(shuō)英支，只要 _todo 非空，重建步驟就必須保持循環(huán)哮伟。在每個(gè)循環(huán)中干花，它應(yīng)該：
調(diào)用
recursive_consequences_of()并傳入_todo中列出的每個(gè)任務(wù)。返回值不僅是_todo任務(wù)本身的一個(gè)列表楞黄，還包括它們下游的每個(gè)任務(wù)池凄，換句話說(shuō)，如果這次輸出不同鬼廓，可能需要重新執(zhí)行的每個(gè)任務(wù)肿仑。對(duì)于列表中的每個(gè)任務(wù)，請(qǐng)檢查它是否列在
_todo中碎税。如果沒(méi)有柏副，那么我們可以跳過(guò)運(yùn)行它，因?yàn)槲覀冊(cè)谒纳嫌沃匦抡{(diào)用的所有任務(wù)都沒(méi)有產(chǎn)生一個(gè)需要重新計(jì)算任務(wù)的新返回值蚣录。但是割择，對(duì)于在到達(dá)時(shí)確實(shí)在
_todo中列出的任何任務(wù)，我們都需要要求它重新運(yùn)行并重新計(jì)算其返回值萎河。如果任務(wù)包裝函數(shù)檢測(cè)到這個(gè)返回值與舊的緩存值不匹配荔泳，那么則在我們將其返回遞歸結(jié)果列表之前蕉饼，它的下游任務(wù)將自動(dòng)添加到_todo中。
當(dāng)我們到達(dá)列表末尾時(shí)玛歌，每個(gè)可能需要重新運(yùn)行的任務(wù)實(shí)際上都應(yīng)該重新運(yùn)行昧港。但以防萬(wàn)一，我們將檢查 _todo支子，如果它還不是空的创肥，會(huì)再試一次。即使對(duì)于快速變化的依賴(lài)樹(shù)值朋，這也應(yīng)該很快解決叹侄。只有一個(gè)循環(huán)，例如昨登，任務(wù) A 需要任務(wù) B 的輸出趾代，而任務(wù) B 本身也需要任務(wù) A 的輸出，才會(huì)使構(gòu)建器處于無(wú)限循環(huán)中丰辣，并且前提是它們的返回值永遠(yuǎn)不穩(wěn)定撒强。幸運(yùn)的是，實(shí)際的構(gòu)建任務(wù)通常沒(méi)有循環(huán)笙什。
讓我們通過(guò)一個(gè)例子來(lái)跟蹤該系統(tǒng)的行為飘哨。
假設(shè)你編輯 tutorial.txt 同時(shí)更改標(biāo)題和正文內(nèi)容。我們可以通過(guò)修改文件系統(tǒng) dict 中的值來(lái)模擬：
>>> filesystem['tutorial.txt'] = """
... The Coder Tutorial
... ------------------
... This is a new and improved
... introductory paragraph.
... """
現(xiàn)在內(nèi)容已經(jīng)更改琐凭，我們可以要求項(xiàng)目重新運(yùn)行 read() 任務(wù)芽隆，方法是使用它的 cache_off() 上下文管理器暫時(shí)禁止它返回給定任務(wù)和參數(shù)的舊緩存結(jié)果：
>>> with project.cache_off():
... text = read('tutorial.txt')
新的 tutorial 文本現(xiàn)在已讀入緩存。需要重新執(zhí)行多少個(gè)下游任務(wù)淘正？
為了幫助我們回答這個(gè)問(wèn)題，Project 類(lèi)支持一個(gè)簡(jiǎn)單的跟蹤工具臼闻，它將告訴我們?cè)谥亟ㄟ^(guò)程中執(zhí)行了哪些任務(wù)鸿吆。因?yàn)橐陨细臑?tutorial.txt 影響到它的正文和標(biāo)題，所有下游的內(nèi)容都需要重新計(jì)算：
>>> 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述呐，你可以看到惩淳，正如預(yù)期的那樣，每個(gè)任務(wù)都是 read('tutorial.txt') 的直接結(jié)果或下游結(jié)果乓搬。
但是如果我們?cè)俅尉庉嬎祭纾疫@次保留標(biāo)題不變呢？
>>> 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')
這個(gè)小的进肯、有限的更改應(yīng)該不會(huì)對(duì)其他文檔產(chǎn)生影響激蹲。
>>> project.start_tracing()
>>> project.rebuild()
>>> print(project.stop_tracing())
calling parse('tutorial.txt')
calling render('tutorial.txt')
calling title_of('tutorial.txt')
成功！只重建了一個(gè)文檔江掩。title_of() 在給定新的輸入文檔時(shí)返回了相同的值学辱，這意味著所有進(jìn)一步的下游任務(wù)都不會(huì)受到更改的影響乘瓤，并且不會(huì)被重新調(diào)用。
總結(jié)
在某些語(yǔ)言和編程方法下策泣，Contingent 將成為一個(gè)令人窒息的小類(lèi)森林衙傀，問(wèn)題域中的每個(gè)概念都有冗長(zhǎng)的名稱(chēng)。
然而萨咕，在用 Python 編寫(xiě) Contingent 時(shí)统抬，我們跳過(guò)了創(chuàng)建諸如TaskArgument、CachedResult 和 ConsequenceList 之類(lèi)的十幾個(gè)可能的類(lèi)危队。相反聪建，我們借鑒了 Python 使用通用數(shù)據(jù)結(jié)構(gòu)解決一般問(wèn)題的強(qiáng)大傳統(tǒng)，從而使代碼反復(fù)使用核心數(shù)據(jù)結(jié)構(gòu)元組交掏、列表妆偏、集合和字典中的一小部分思想。
但這不會(huì)造成問(wèn)題嗎盅弛？
通用數(shù)據(jù)結(jié)構(gòu)本質(zhì)上也是匿名的钱骂。我們的 project._cache 是一個(gè)集合。Graph 中上游和下游節(jié)點(diǎn)的每個(gè)集合也是如此挪鹏。我們是否有可能看到通用的集合錯(cuò)誤消息而不知道是在項(xiàng)目中還是在圖實(shí)現(xiàn)中查找錯(cuò)誤见秽？
事實(shí)上，我們并沒(méi)有風(fēng)險(xiǎn)讨盒！
由于封裝的謹(jǐn)慎原則解取，只允許 Graph 代碼接觸圖的集合，而 Project 代碼接觸項(xiàng)目的集合返顺。如果在項(xiàng)目的后期階段禀苦，集合操作返回錯(cuò)誤，就不會(huì)有歧義遂鹊。發(fā)生錯(cuò)誤時(shí)最內(nèi)部執(zhí)行方法的名稱(chēng)必然會(huì)將我們指向錯(cuò)誤所涉及的類(lèi)和集合振乏。只要我們將傳統(tǒng)的下劃線放在數(shù)據(jù)結(jié)構(gòu)屬性前面，然后小心不要從類(lèi)外部的代碼中接觸它們秉扑，就沒(méi)有必要為數(shù)據(jù)類(lèi)型的每個(gè)可能的應(yīng)用程序創(chuàng)建 set 的子類(lèi)慧邮。
Contingent 演示了來(lái)自劃時(shí)代的書(shū)籍 Design Patterns 的外觀（Facade）模式對(duì)于精心設(shè)計(jì)的 Python 程序有多么關(guān)鍵。并不是 Python 程序中的每個(gè)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)片段都是自己的類(lèi)舟陆。相反误澳，在代碼的概念性支點(diǎn)處，類(lèi)的使用是有節(jié)制的秦躯，在這種情況下忆谓，一個(gè)大的概念（如依賴(lài)關(guān)系圖的概念）可以被包裝成一個(gè)隱藏在其下面的簡(jiǎn)單泛型數(shù)據(jù)結(jié)構(gòu)細(xì)節(jié)的外觀。
外觀角色之外的代碼列出了它需要的大概念和它想要執(zhí)行的操作踱承。在外觀角色的內(nèi)部陪毡，程序員操縱 Python 編程語(yǔ)言的小而方便的移動(dòng)部件來(lái)實(shí)現(xiàn)操作米母。
