以Make为例的传统构建系统
传统的构建系统如Make，用户指定项目中所有目标文件(非源文件)的产生方式，储存在makefile文件中。
考虑如下的伪makefile：
1 | main: a.o b.o |
请忽略Make的缺省规则(main的实际依赖会有所不同)。例子中也省略了recipe(info '(make) Rule Syntax')。
每次需要构建整个项目的终极目标或者中间目标时，比如执行make main，Make会检查
构建main的规则，发现main依赖a.o和b.o，而a.o依赖a.c和main.h，b.o依赖b.c和main.h。假设a.c修改了，那么a.o和main都会“过期”，更新main的方式是先重建a.o再重建main。
依赖关系可以表示成这样一张图(directed acyclic graph)：
Make这一类传统构建系统每次执行时都会根据配置文件(比如makefile)中记录的规则建立所有文件的依赖关系，在内部产生一个图(类似上图)。然后取出最终重建目标的所有直接、间接的依赖，按照拓扑序的逆序依次考虑每个节点对应的文件，判断是否过期，如果过期则执行一条recipe重建这个文件。
而判断目标是否过期的方式则是用stat(2)之类的系统调用获取目标及其依赖的时间戳，判断目标的时间戳是否小于依赖的。
重建一个目标执行的重建操作数等于目标的依赖树中“过期”节点的个数。(实际上make可能会重启，导致重建操作数变多。这里不考虑这些)看上去非常优异，但是获取时间戳操作的次数是和依赖树的大小同阶的，达到了线性的时间复杂度。
另一种构建系统
判断是否过期
传统的构建系统对文件的修改状态实际上一无所知，所以每次执行重建操作都得通过检查所有文件时间戳的方式来了解文件是否被修改，从而判定哪些目标需要重建，瓶颈就在于这些时间戳获取操作。
假如有一种方式能够得到文件的修改通知，那么我们就能省去这些时间戳获取操作。
考虑上图，我们修改了a.c，a.c、a.o、main都“过期”了。可以看出，变动a.c之后，只有它的祖先节点对应的文件会变成“过期”状态，其他文件仍然会是新的。
设想这样一个构建系统，以daemon形式运行，读取配置文件产生依赖图，维护一份文件是否“过期”的列表。用户执行构建操作时，客户端会向daemon传递构建任务，daemon根据这份列表判断目标是否需要重建。注意，传统的构建系统是通过检查时间戳来判断是否需要重建的。
我们需要根据文件的修改信息来维护这份列表。当有文件发生修改时，在DAG中找到这个文件对应的节点，将它及其所有祖先标记为“过期”。
高效执行重建操作
能判断目标是否过期还不够，我们需要知道如何重建它。显然不能像传统构建系统那样遍历目标所在的子树。
一种解决方案是让directed acyclic graph只包含“过期”文件对应的节点，那么一开始这张图为空，如下图：
灰色节点实际上不在依赖图中，这里显示出来是为了展示出整张图的全貌，即如果所有文件都过期时图的形态。另外注意一下箭头方向，读完后可以想一下这么做的理由。
修改了a.c之后，更新a.c、a.o、main的过期状态：
这时如果需要构建某个目标，在依赖图中找到目标对应的节点，后续遍历这个节点，对每个访问到的节点执行重建操作。如果依赖图中不存在目标对应的节点，那么就说明目标没有“过期”，不需要做任何重建操作。比如用户要构建a.o，那么就会依次重建a.c和a.o，a.c不是任何规则的目标所以不执行重建操作，a.o是某条规则的目标，重建之。如果要构建main则会依次构建a.c、a.o、main。执行完所有重建操作后删除重建过的节点，仍旧变成空图：
修改main.h之后，main.h、a.o、b.o、main都过期了：
重建b.o。需要删除b.o及其所有直接间接依赖：
小结一下有两条规则：
- 得到文件修改通知后把对应节点及所有祖先(这个祖先是针对全图来说的)加入到依赖图中。
- 重建过的节点都从依赖图中删去。
实际应用
Tup是一个采取了这个技术的构建系统。
文件修改通知可以用Inotify、FAM、Gamin等。
参考文献
Tup项目首页给出的链接：Build System Rules and Algorithms