AWK 书中 60 行实现的 Make
在 Aho、Weinberger 和 Kernighan 合著的经典著作《The AWK Programming Language》中，第 7 章末尾用几页篇幅展示了一个简化版的 Make 工具——全部代码仅用一页 AWK 就写成了。
在展开之前，先提一下，第二版的 AWK 图书将于下月出版。Brian Kernighan 对其做了出色的更新，最引人注目的是一章关于探索性数据分析的新内容，并为此给 AWK 加入了完善的 CSV 支持。我很荣幸受邀审阅了第二版的草稿。
即使在 2023 年，AWK 在数据探索方面依然表现出色，尤其是新增的 --csv 选项。CSV 模式也已加入到 Gawk（GNU AWK）——AWK 安装最广泛的版本中。我自己的 GoAWK 实现早已具备完善的 CSV 支持，我也已添加 --csv 选项以与其他版本保持一致。
第二版中依然保留了这个 Make 程序，不过为了提高可读性加入了一些“空格与花括号”——这让代码从 50 行增加到了 62 行，改动见此。
本文将介绍这个 Make 程序，以说明 AWK 不仅擅长写一行命令，也完全可以作为脚本语言来使用——至于是否应该这么做，则是另一回事。
接下来，我会对比同一个程序用 Python 实现会是什么样子，并简要讨论在这类任务中何时该选 AWK、何时该选 Python。
不用多说，这纯粹是一次学习练习（对我和读者而言），并非推荐大家真的用它来构建项目！
原始 AWK 版本
第二版是这样引入这个 Make 程序的。（顺便说一句，我觉得这里用“target”这个词容易让人困惑——我认为用“source”或“dependency”会更合适。）
本节将开发一个简易的更新程序，它仿照 Unix 的
make命令，基于上一节介绍的深度优先搜索技术。要使用这个更新器，必须明确描述系统由哪些组件构成、它们之间如何相互依赖，以及构建它们需要哪些命令。我们假设这些依赖和命令都存放在一个名为
makefile的文件中，其中包含一系列形如下面的规则name: t1 t2 ... tn commands规则的第一行是依赖关系，表明程序或文件 name 依赖于目标 t1、t2、…、tn，其中每个 ti 都是一个文件名或另一个 name。每条依赖关系之后可以跟一行或多行 commands，列出生成 name 所需的命令。下面是一个
makefile示例，对应一个包含两个 C 文件a.c、b.c和一个yacc文法文件c.y的小型程序，这是典型的程序开发场景。prog: a.o b.o c.o gcc a.o b.o c.o -ly -o prog a.o: prog.h a.c gcc -c prog.h a.c b.o: prog.h b.c gcc -c prog.h b.c c.o: c.c gcc -c c.c c.c: c.y yacc c.y mv y.tab.c c.c print: pr prog.h a.c b.c c.y第一行表明
prog依赖于目标文件a.o、b.o和c.o。第二行说明prog是通过 C 编译器命令gcc将a.o、b.o、c.o以及yacc库y链接生成prog。下一条规则（第三行）指出a.o依赖于目标prog.h和a.c，并通过编译这些目标来生成；b.o亦然。文件c.o依赖于c.c，而c.c又依赖于c.y，后者需要用yacc解析器生成器来处理。最后，名称make总会执行其关联动作，在此例中就是用pr命令打印全部源文件。
makefile中的依赖关系可以用图来表示：只要存在一条依赖规则，左边是 x，右边的目标中有一个是 y，就在节点 x 到节点 y 之间连一条边。对于没有目标的规则，则会创建一个左侧名称对应的无后继节点。对于上面的makefile，依赖图如下：prog print / | \ / | \ a.o b.o c.o / \ / \ \ / \/ \ \ a.c prog.h b.c c.c | c.y
当然，这是一个高度简化的 Make 版本，但依然具备输出、依赖和构建命令这些核心概念。
在了解其工作原理之前，我在下方附上了完整源代码，内容与 AWK 图书第二版中完全一致。点击加粗文字可展开代码，或直接跳到“工作原理”一节查看详细讲解。
AWK 书中的 Make 程序（完整源代码）。
BEGIN {
while (getline <"makefile" > 0) {
if ($0 ~ /^[A-Za-z]/) { # $1: $2 $3 ...
sub(/:/, "")
if (++names[nm = $1] > 1)
error(nm " is multiply defined")
for (i = 2; i <= NF; i++) # remember targets
slist[nm, ++scnt[nm]] = $i
} else if ($0 ~ /^\t/) { # remember cmd for
cmd[nm] = cmd[nm] $0 "\n" # current name
} else if (NF > 0) {
error("illegal line in makefile: " $0)
}
}
ages() # compute initial ages
if (ARGV[1] in names) {
if (update(ARGV[1]) == 0)
print ARGV[1] " is up to date"
} else {
error(ARGV[1] " is not in makefile")
}
}
function ages( f,n,t) {
for (t = 1; ("ls -t" | getline f) > 0; t++)
age[f] = t # all existing files get an age
close("ls -t")
for (n in names)
if (!(n in age)) # if n has not been created
age[n] = 9999 # make n really old
}
function update(n, changed,i,s) {
if (!(n in age))
error(n " does not exist")
if (!(n in names))
return 0
changed = 0
visited[n] = 1
for (i = 1; i <= scnt[n]; i++) {
if (visited[s = slist[n, i]] == 0)
update(s)
else if (visited[s] == 1)
error(s " and " n " are circularly defined")
if (age[s] <= age[n])
changed++
}
visited[n] = 2
if (changed || scnt[n] == 0) {
printf("%s", cmd[n])
system(cmd[n]) # execute cmd associated with n
ages() # recompute all ages
age[n] = 0 # make n very new
return 1
}
return 0
}
function error(s) { print "error: " s; exit }工作原理
书中有对程序工作原理的说明，但这里我会用自己的话来解释，重点关注我觉得有意思的部分。
BEGIN 块是这类程序的主入口。与大多数隐式从标准输入读取行的 AWK 程序不同，这个程序用显式的 getline 循环来读取 makefile：
BEGIN {
while (getline <"makefile" > 0) {
if ($0 ~ /^[A-Za-z]/) { # $1: $2 $3 ...
sub(/:/, "")
if (++names[nm = $1] > 1)
error(nm " is multiply defined")
for (i = 2; i <= NF; i++) # remember targets
slist[nm, ++scnt[nm]] = $i
} else if ($0 ~ /^\t/) { # remember cmd for
cmd[nm] = cmd[nm] $0 "\n" # current name
} else if (NF > 0) {
error("illegal line in makefile: " $0)
}
}
...
}getline <filename 是一种重定向写法，首次执行时会打开 makefile，并逐行读取直至结束。如果当前行（$0）以字母开头（/^[A-Za-z]/），则被视为 name: targets 形式的规则。
sub(/:/, "") 调用会去掉当前行中的冒号（在双参数形式的 sub 中，$0 是隐含参数）。
接下来我们通过检查 names 数组来确保该规则尚未定义过。AWK 中的数组实际上是关联数组，也就是早期对键值映射的称呼。
内部的 for 循环将每个 target（即依赖）加入 slist / scnt 数据结构。这其实是一个映射的列表，但为了绕开 AWK 不支持嵌套集合的限制，被展平成了这种形式。循环体非常简洁：
for (i = 2; i <= NF; i++)
slist[nm, ++scnt[nm]] = $i这段循环遍历每个依赖：即该行中从第 2 个字段到 NF（该行的字段数）的每一个字段 $i。
对每个依赖，先将当前规则（nm）对应的源数量 scnt[nm] 加一，然后把依赖 $i 存入 slist，以名称和计数作为多键索引。AWK 通过将多个键用 SUBSEP 分隔符（默认为 "\x1c"）拼接成一个键，来模拟多维或多键数组。
循环结束后，以 prog 为例，slist 和 scnt 会呈现如下形态：
slist
a.o,1: prog.h
a.o,2: a.c
b.o,1: prog.h
b.o,2: b.c
c.c,1: c.y
c.o,1: c.c
prog,1: a.o
prog,2: b.o
prog,3: c.o
scnt
a.o: 2
b.o: 2
c.c: 1
c.o: 1
prog: 3回到上层，如果一行以制表符开头，则它是命令，于是将其追加到对应名称的命令字符串中：
cmd[nm] = cmd[nm] $0 "\n"否则，如果该行不是空行（NF > 0），则视为 makefile 错误。
最后，在 while 循环中读完 makefile 后，我们调用 ages() 计算当前目录下所有文件的“新旧程度”，然后调用 update(ARGV[1]) 去更新命令行传入的规则：
BEGIN {
...
ages() # compute initial ages
if (ARGV[1] in names) {
if (update(ARGV[1]) == 0)
print ARGV[1] " is up to date"
} else {
error(ARGV[1] " is not in makefile")
}
}ages 函数开始变得有意思了：
function ages( f,n,t) {
for (t = 1; ("ls -t" | getline f) > 0; t++)
age[f] = t # all existing files get an age
close("ls -t")
for (n in names)
if (!(n in age)) # if n has not been created
age[n] = 9999 # make n really old
}参数名 f、n、t 前面空了一大段，用来表明它们实际上是局部变量，而非预期的实参。这是 AWK 的一个怪癖（Kernighan 对此也感到后悔）：定义局部变量的唯一方式就是把它们写成函数参数，而当调用时传入的实参数量少于形参数量时，多余的参数会取默认值（数值默认为 0，字符串默认为 ""）。因此你在 AWK 函数定义中会经常看到这种多余的空格。
接下来的一点很巧妙：AWK 支持类似 shell 的 | 语法，将某个程序的输出通过管道一次一行地用 getline 读入变量（这里是 f）。ls -t 命令会按修改时间从新到旧列出当前目录下的文件。
在将每个文件的“年龄”赋给 age[f] 的循环之后，我们调用 close 关闭 ls -t 管道，以避免打开过多文件句柄。
最后，我们遍历所有规则名，给尚未创建的文件的 age[n] 赋一个任意的大数，假装它们非常“旧”，从而需要被更新。
接下来是递归的 update 函数，这里是算法的核心所在：
function update(n, changed,i,s) {
if (!(n in age))
error(n " does not exist")
if (!(n in names))
return 0
changed = 0
visited[n] = 1
for (i = 1; i <= scnt[n]; i++) {
if (visited[s = slist[n, i]] == 0)
update(s)
else if (visited[s] == 1)
error(s " and " n " are circularly defined")
if (age[s] <= age[n])
changed++
}
visited[n] = 2
if (changed || scnt[n] == 0) {
printf("%s", cmd[n])
system(cmd[n]) # execute cmd associated with n
ages() # recompute all ages
age[n] = 0 # make n very new
return 1
}
return 0
}同样，注意参数列表：n 是预期的实参（要更新的名称），而 changed,i,s 则是局部变量。
在完成初始检查后，我们通过从 slist[n, 1] 遍历到 slist[n, scnt[n]] 来循环依赖列表。如果该依赖尚未访问过，就通过递归调用 update 对依赖图进行深度优先遍历，看看是否需要先更新该依赖：
if (visited[s = slist[n, i]] == 0)
update(s)递归的终止条件是顶部附近的 if (!(n in names)) return 0 语句。当要更新的文件不在规则名列表中时，我们就停止——这对应依赖图中的叶子节点。
语句 if (age[s] <= age[n]) changed++ 会在任一依赖比当前正在更新的文件更新时，将 changed 计数加一。
遍历循环结束后，如果任一依赖或子依赖发生了变化，我们就用 system() 执行关联命令，重新计算所有文件的年龄，并向调用者返回 1，表示确实进行了更新。
scnt[n] == 0 这一条件处理的是被更新规则未指定任何依赖的情况，就像示例中的 print 规则。此时总是重新执行其命令。
就这样！一个用一页 AWK 实现的极简 Make 就完成了。
Python 版本
出于兴趣，我把书中的 AWK 版 Make 移植到了 Python，代码附在下方。同样，点击加粗文字即可展开程序。
我移植的 Python 版 Make 程序（完整源代码）。
import os, re, sys
slist = {} # slist[name] is list of rule's sources
cmd = {} # cmd[name] is shell command to run for rule
def main():
for line in open('makefile'):
if re.match('[A-Za-z]', line):
line = line.replace(':', '')
fields = line.split()
nm = fields[0]
if nm in slist:
error(f'{nm} is multiply defined')
slist[nm] = fields[1:] # remember targets
elif line.startswith('\t'): # remember cmd for current name
cmd[nm] = cmd.get(nm, '') + line
elif line.strip():
error(f'illegal line in makefile: {line}')
if sys.argv[1] in slist:
if not update(sys.argv[1]):
print(sys.argv[1], 'is up to date')
else:
error(f'{sys.argv[1]} is not in makefile')
def mtime(n):
try:
return os.stat(n).st_mtime
except FileNotFoundError:
return 0 # mark as old if it doesn't exist
def update(n, visited={}):
ntime = mtime(n)
if n not in slist and ntime == 0:
error(f'{n} does not exist')
if n not in slist:
return 0
changed = False
visited[n] = 1
for s in slist.get(n, []):
if s not in visited:
update(s)
elif visited[s] == 1:
error(f'{s} and {n} are circularly defined')
if mtime(s) > ntime:
changed = True
visited[n] = 2
if changed or len(slist.get(n, [])) == 0:
print(cmd[n], end='')
os.system(cmd[n]) # execute cmd associated with n
return 1
return 0
def error(msg):
print('error:', msg, file=sys.stderr)
sys.exit(1)
if __name__ == '__main__':
main()它在结构上与原版 AWK 版本非常相似，不过我做了两处简化，我认为这样更易于理解：
- 更简单的数据结构，避免
slist/scnt的别扭写法——在 Python 中我们只需使用字典套列表即可。（查看 diff。） - 更直接地通过
os.stat()获取文件修改时间（mtime）来判断新旧，而不是使用ls -t的技巧。这也省去了age映射和ages函数。（查看 diff。）
这并非有意为之，但即使算上 import 语句和 if __name__ == '__main__' 这一固定写法，它也只有 58 行代码——基本上与 AWK 程序长度相当。
在编写 Python 版本时，我意识到也可以用类似方式简化 AWK 版本：
- 在概念上，直接将
slist存为 AWK 数组更为简单：一个键值映射，键是规则名，值是以空格分隔的依赖列表字符串（就像在makefile中那样）。需要时可以用split将依赖字符串转为列表（一个从 1 到依赖数量的数组）。这样就完全不需要scnt和names了。（查看 diff。） - 与 Python 版本类似，我们可以直接通过调用外部命令
stat来获取 mtime，而不是用ls -t按年龄顺序列出所有文件。我使用了stat --format %y来实现。我认为这是 GNU 扩展，因此可移植性不如ls -t，但它更简单，也避免了重新计算age数组的需要。（查看 diff。）
更新：Volodymyr Gubarkov 指出，stat 版本“增加了多次外部进程调用”，他说得很对。它或许更直接，但速度明显更慢。
顺带一提，修改后的版本比原版少了四行。我觉得更简单的 slist 更清晰，也更喜欢直接获取 mtime 的方式，尽管我也意识到 stat --format 缺乏可移植性是个缺点（macOS 上的 stat 看起来很不一样）。
结论
AWK 版 Make 程序是一段精巧的代码，展示了 AWK 即使对于中等规模的脚本也是一门非常实用的语言。
不过，Python 在处理这类任务时无疑是更优雅的语言：它拥有更丰富的数据类型、像 os.stat 这样更趁手的工具，以及无需怪异语法就能使用的局部变量。
我认为 AWK 非常出色，但它就应该留在它最擅长的领域：探索性数据分析和一行式数据提取脚本。
作为早已具备原生 CSV 支持的 GoAWK 的作者，我尤其高兴地看到 Kernighan 的“one true AWK”和 Gawk 都以 --csv 选项的形式获得了完善的 CSV 支持。Kernighan 对 AWK 的更新很快就会被合并，Gawk 也将在即将发布的 5.3.0 版本中加入这一功能。
你也可以在 GitHub 上查看我的 awkmake 仓库，其中包含了 AWK 书中 Make 程序与我的 Python 版本的完整源码，以及一个基于书中示例的可运行示例项目。
评论
登录后参与讨论