编写一个make

　　一、简介

　　How to make a "make"?在进行实现前，应该先对make有一个最基本的了解。这里稍作简介：当一个程序的源文件较少时，对其进行修改并重新生成可执行文件并不复杂，只要将这些文件名作为参数传递给编译器即可;当一个项目的源文件越来越多，对于源文件的修改，必然要重新生成一些中间文件。这时，如果把没有修改的源文件也重新编译，势必会浪费很多时间。make可以根据makefile文件提供的文件依赖，决定哪些中间文件需要重新编译，哪些不需要， 从而节约了大量的时间。

　　因此，实现make，需要提供的功能是：通过处理读入的makefile文件的内容，梳理文件依赖、并执行相应指令。以下分别介绍。包括自己编写的hash表以及一个测试用例，全部代码已托管至github：。

　　二、功能实现：makefile的分析和获得文件依赖

　　(1)makefile的基本格式

　　图片来源：Makefiles in Linux: An Overview

　　上图是一个makefile文件的一个单元，不考虑makefile中的变量，每个makefile都由这样的单元组成。其中：

　　第一行，目标文件名，一个分隔的:号，以空格分隔的一连续的文件名。目标文件依赖于后面的所有文件。

　　第二行至第N+1行，对应需要执行的命令。

　　可以看出，文件分析的重点是这部分的第一行;后续的行直接执行对应的命令即可。第一行中指出了target是依赖于file1...fileN的，这个依赖关系是判断是否需要重新编译target的依据。如果filex比target新，那么意味着filex在生成target之后进行了改动，必须重新编译target。对于target不存在的情况，可以认为target是最旧的，也需要进行编译。

　　(2)文件新旧的依据：Linux时间戳

　　正如(1)中提到的，判断时需要一个文件新旧的指标。makefile使用了时间戳(timestamp)的概念， 利用时间戳的先后判断哪个文件比较新，具体使用的就是修改时间这个指标，可以获得指定文件的修改时间。对于不存在的文件，则认为它的修改时间是最老的，也即0，总是比其他文件旧。这个函数可以写成：

　　time_t GetModifiedTimestamp(char *path)

　　{

　　struct stat attr;

　　if(stat(path,&attr) == -1)

　　return 0;

　　return attr.st_mtime;

　　}

　　更多关于Linux时间戳的信息，可以参考：linux Makefile时间戳。

　　(3)文件依赖的分析

　　假如依赖只有一行，那么很简单，依次检查各个文件是否比目标文件新，然后就可以决定是否需要重新编译了。但实际中往往比较复杂，举个稍微简单点的例子：

　　#忽略依赖行下面的命令行

　　something : x y z

　　x : a b

　　y : b c

　　z : d e

　　如果a更新了，make something时只需要重新编译x就行了;如果b更新了，make something时不仅需要重新编译x，还要重新编译y。上面的文件依赖可以表示为：

　　可以看出，make时，需要检查所有与其有依赖的文件的时间戳，而这个过程是递归的。在这个图示的启发下，很容易想到使用图这一数据结构来表示文件依赖。结合实际情况，邻接链表表示的有向图比较合适。图中的结点代表了一个源文件或目标文件，也有可能是“clean”这样的单纯的命令。为了加快结点的插入和查找，使用hash表来存放各个结点是一个合适的选择。这相当于把哈希表和邻接表结合在了一起，即：哈希表存放代表文件的结点，结点的邻接表指向文件依赖中的其他结点。

　　这时回到时间戳先后的分析问题，使用深度优先搜索算法(DFS)，就可以递归地判断当前顶点的时间戳是否是最新的，如果不是，那么需要重新编译。在DFS这个递归过程中，所有需要更新的结点都会通过重新编译变成最新的，而源文件代表的结点没有邻接结点，不必更新。同时DFS还能找出这个有向图中是否有环，有环时，文件依赖非法，不执行任何动作。使用DFS判断有向图是否有环可以参考《算法导论(第二版)》22.3节“深度优先搜索”中“边的分类”和22.4节“拓扑排序”的引理22.11。同时要注意，这里用了DFS的一个特性：在退出一个结点时才标记为BLACK，这时才与它的后续结点中时间戳最新的进行比较。

　　有向图中需要区分两种结点：目标文件结点(含clean)和源文件结点。前者存在文件依赖，并且需要执行一行或多行命令;后者不存在文件依赖，不需要执行命令。因此结点的结构体为：