译自《Kati internals》
这是关于Kati内部结构的非正式文档。本文不是一个Kati或GNU make的综合文档。本文档解释了其他程序员可能感兴趣的一些随机主题。
动机
Kati的动机是加快Android平台构建。特别是其增长的构建时间是主要的焦点。 Android平台的构建系统是一个非常独特的系统。它提供了一个DSL (ab)，使用Turing完整的GNU make。 DSL允许开发人员以描述性的方式编写构建规则，但缺点是复杂和缓慢。
当我们说构建系统缓慢时，我们考虑 “空构建(null build)” 和 “完整构建(full build)”。 空构建是一个不做任何事情的构建，因为所有的输出文件都是最新的。完整构建是构建一切的构建，因为没有任何东西已经构建好。日常开发中的实际构建位于空构建和完整构建之间。下面的大多数基准测试都是基于空构建。
对于Android，我的相当强大的工作站，使用GNU make，空构建花了约100秒。这意味着你需要等待〜100秒来查看更改单个C文件时是否有编译错误。公平地说，事情并没有那么糟糕。因为有称为mm/mmm的工具。它们允许开发人员构建一个单独的模块。当它们忽略模块之间的依赖关系时，它们很快。但是，你需要有足够的经验才能正确使用它们。你应该知道哪些模块将受到你的更改的影响。如果你更改一些东西时可以只要输入“make”，那将会更好。
这就是为什么我们开始这个项目的原因。我们决定从头创建一个GNU make克隆，但还有一些其他选项。一个选择是用更好的格式替换所有的Android.mk文件。实际上这是一个长期的项目。Kati计划成为一个短期项目。另一个选择是hack GNU make，而不是开发克隆。我们没有采取这个选择，因为我们认为由于历史原因，GNU make的源代码有点复杂。它是用老式C编写的，对于某些未知的架构等都有很多ifdef。
目前，Kati的主要模式是--ninja模式。 Kati自己不用执行build命令，而是生成build.ninja文件，而ninja实际上运行命令。在Kati成为当前形式之前，有一些往返。一些实验成功，其他一些失败。我们甚至改变了Kati的语言。起初，我们在Go中写了Kati。我们天真地期望我们可以用Go获得足够的性能。我猜到以下至少一个语句是真的：
- GNU make对于计算重的Makefile不是非常优化，2. 为我们的目的选择Go有点快了，或3. 我们可以提出一些Android的构建系统的优化技巧。至于3，一些这样的优化成功了，但是性能的提升没有取消Go的缓慢。
Go的性能表现会有点有趣的话题。我没有详细研究性能差异，但是似乎我们使用Go的方式，以及Go语言本身使得Kati的Go版本变慢。对于我们的错，我认为Go版本比C++版本有更多的不必要的字符串分配。至于Go本身，似乎GC是主要的展示器。例如，Android的构建系统定义了大约一百万个变量，缓冲区将永远不会被释放。 IIRC，这种分配格局对于非代际GC（non-generational）是不利的。
Go版本和测试用例是由ukai和我写的，C++重写主要由我完成。本文档的其余部分主要是关于C++版本。
整体架构
Kati由以下组件组成：
- 解析器（Parser）
- 评估器（Evaluator）
- 依赖构建器（Dependency builder）
- 执行器（Executor）
- Ninja生成器（Ninja generator）
Makefile有一些由零个或多个表达式组成的语句。有两个解析器和两个评估器， 一个用于语句，另一个用于表达式。
GNU make的大部分用户可能不太关心评估器。但是，GNU make的评估器非常强大，并且是图灵完整的。对于Android的空构建（null build），大部分时间都花在这个阶段。其他任务，例如构建依赖关系图和调用构建目标的stat函数，并不是瓶颈。这将是一个非常具体的Android特性。 Android的构建系统使用了大量的GNU make黑魔法。
评估器输出构建规则(build rules)和变量表(variable table)的列表。依赖构建器从构建规则列表中创建依赖图(dependency graph)。注意这一步不使用变量表。
然后将使用执行器或Ninja生成器。无论哪种方式，Kati再次为命令行运行其评估器。该变量表再次用于此步骤。
我们将仔细查看每个组件。 GNU make是一种与现代语言不同的语言。让我们来看看。
语句分析器
我不是100％肯定，但我认为GNU make同时进行解析和评估Makefile，但是Kati有两个阶段用于解析和评估。这种设计的原因是为了性能。对于Android构建，Kati（或GNU make)需要读取〜3k个文件〜50k次。读取最多的文件需要读取〜5k次。浪费时间一次次地解析这些文件。当需要再次评估Makefile时，Kati可以重新使用已解析的结果。如果我们停止缓存已解析的结果，则对于Android的构建，Kati将会慢两倍。缓存已解析的语句在file_cache.cc中完成。
语句解析器在parser.cc中定义。在Kati中，有四种语句：
- 规则（Rules）
- 赋值（Assignments）
- 命令（Commands）
- Make指令（Make directives）
它们的数据结构在stmt.h中定义。以下是这些语句的示例：
VAR := yay! # An assignment
all: # A rule
echo $(VAR) # A command
include xxx.mk # A make directive (include)
除了include指令之外，还有ifeq/ifneq/ifdef/ifndef指令和export/unexport指令。另外，在Kati内部还使用“解析错误语句（parse error statement）”。由于GNU make不显示不被采用的分支中的解析错误，因此我们需要将解析错误延迟到评估时间。
上下文相关解析器
解析make语句的棘手之处在于，解析取决于评估时的上下文。请参阅以下Makefile块：
$(VAR)
X=hoge echo $${X}
在$(VAR)被评估之前，你无法判断第二行是否为命令或赋值。如果$(VAR)是一个规则语句，则第二行是一个命令，否则它是一个赋值。如果在此之前的上一行是
VAR := target:
第二行将成为一个命令。
由于某些原因，仅用于规则，GNU make会在决定语句类型之前展开表达式。将赋值或指令（assignments or directives）存储在变量中将使其不能用作赋值或指令。例如
ASSIGN := A=B
$(ASSIGN):
不为A赋值B，但定义了一个构建规则，其目标是A = B。
无论如何，因为以tab字符开头的一行可以是一个命令语句（command statement）或其他语句，这取决于上一行的评估结果，所以有时Kati的解析器不能分辨一行的语句类型。在这种情况下，Kati的解析器推测创建一个命令语句对象，也保留原始行。如果事实证明该行实际上不是命令语句，则评估器将重新运行解析器。
行连结和注释
在大多数编程语言中，反斜杠字符的行连接和注释在语言实现的早期阶段处理。然而，GNU make根据解析/评估上下文（parse/eval context）改变了它们的行为。例如，以下Makefile输出“has space”和“hasnospace”：
VAR := has\
space
all:
echo $(VAR)
echo has\
nospace
GNU make通常在行之间插入空格，但对于命令行，它不会。正如我们在上一小节中看到的，有时候Kati不能分辨一行是一个命令语句。这意味着我们在评估语句后应该处理它们。类似的讨论也适用于注释。 GNU make通常去掉（trims）在'#'之后的字符，但对命令行中的'#'不起作用。
我们在Kati的代码库的testcase目录中有一堆关于注释/反斜杠相关的测试用例。
表达式的解析器
一个语句可能有一个或多个表达式。语句中的表达式数目取决于语句的类型。例如，
A := $(X)
这是一个赋值语句，它有两个表达式 ：A和$(X)。表达式及其解析器的类型在expr.cc中定义。像其他编程语言一样，一个表达式（an expression）是一棵表达式的树（a tree of expressions）。叶子表达式（leaf expression）的类型是文字（literal），变量引用（variable reference），替代引用（substitution references）或make函数（make functions）。
如所写的，反斜杠和注释根据上下文来改变它们的行为。在这个阶段，Kati处理他们。ParseExprOpt是上下文的枚举。
作为旧系统的一个本质，GNU make是非常宽容的。由于某种原因，它允许某种没有成对匹配的括号对（unmatched pairs of parentheses）。例如，GNU make不认为$($ foo)是一个错误 - 这是对变量$(foo)的引用。如果你有一些解析器的经验，你可能会想知道怎么会实现这样的解析器能允许这样的表达式。似乎GNU有意地允许这样：
http://git.savannah.gnu.org/cgit/make.git/tree/expand.c#n285
没有人会有意使用这个功能。然而，不幸的是，由于GNU make允许这一点，一些Makefile有不匹配的括号，所以Kati不应该为他们引发一个错误。
GNU make有一堆功能。大多数用户只能使用简单的例如$(wildcard ...)和$(subst ...)。还有更复杂的功能，如$(if ...)和$(call ...)，这使得GNU make是图灵完整的。 make函数定义在func.cc中。虽然func.cc不短，但实现相当简单。关于函数，我记得只有一个比较奇怪的地方。 GNU make对$(if ...)，$(and ...)和$(or ...)的解析稍作了改变。请参阅func.h中的trim_space和trim_right_space_1st，以及如何在expr.cc中使用它们。
语句的评估器
语句的评估器定义在eval.cc中。如书面所述，有四种语句：
- 规则（Rules）
- 赋值（Assignments）
- 命令（Commands）
- Make指令（Make directives）
命令和指令之间没有什么棘手的。规则语句有一些不同形式，在第三个解析器评估表达式之后应该进行解析。这将在下一节讨论。
GNU make中的赋值有点棘手。 GNU make中有两种变量 - 简单变量和递归变量。请参阅以下代码段：
A = $(info world!) # recursive
B := $(info Hello,) # simple
$(A)
$(B)
此代码按此顺序输出“Hello,”和“world！”。递归变量的评估被延迟，直到引用变量。所以第一行是递归变量的赋值，不输出任何内容。在第一行之后，变量$(A)的内容将是$(info world！)。第二行中的赋值使用:=，这意味着这是一个简单变量赋值。对于简单变量，右侧将立即进行评估。所以“Hello,”将被输出，$(B)的值将是一个空字符串，因为$(info ...)返回一个空字符串。然后，当第三行$(A)被评估时，将显示“world!”，最后第四行不执行任何操作，因为$(B)是一个空字符串。
还有两种赋值（即+=和?=)。这些赋值保留原始变量的类型。只有当赋值的左侧已经被定义并且是一个简单变量时，才能对它们进行评估。
规则解析器
评估规则语句后，Kati需要解析评估结果。规则声明实际上可以是以下四件事：
- 一个规则
- 一个目标特定变量
- 一个空行
- 一个错误（没有冒号的非空格字符)
解析它们主要是在rule.cc中完成的。
规则
一个规则就像all: hello.exe。你应该熟悉它。有几种规则，如模式规则（pattern rules），双冒号规则（double colon rules）和仅顺序依赖（order only dependencies），但它们不会使规则解析器复杂化。
使解析器复杂化的一个特性是分号。你可以在规则的同一行上编写第一个构建命令。例如，
target:
echo hi!
和
target: ; echo hi!
具有相同的含义。这是棘手的，因为在实际调用命令之前，Kati不应该评估命令中的表达式。因为表达式评估的结果，可以出现分号，有一些边角情形。一个棘手的例子：
all: $(info foo) ; $(info bar)
$(info baz)
应该按此顺序输出foo，baz，然后bar，但是
VAR := all: $(info foo) ; $(info bar)
$(VAR)
$(info baz)
输出foo，bar，然后baz。
再次，对于分号后面的命令行，Kati还应该更改反斜杠和注释的处理方式。
target: has\
space ; echo no\
space
上面的例子说，target依赖于两个目标，has和space，而为了构建target，echo nospace应该被执行。
目标特定变量
你可能不熟悉目标特定变量（target specific variables）。此功能允许你定义只能从指定目标的命令中引用的变量。请参阅以下代码：
VAR := X
target1: VAR := Y
target1:
echo $(VAR)
target2:
echo $(VAR)
在这个例子中，target1显示Y而target2显示X。我认为这个功能有点类似于其他编程语言中的命名空间。如果为非叶目标（non-leaf target）指定了目标特定变量，则即使在先决条件目标（prerequisite targets）的构建命令中也将使用该变量。
一般来说，我喜欢GNU make，但这是唯一不喜欢的GNU make的功能。请参阅以下Makefile：
hello: CFLAGS := -g
hello: hello.o
gcc $(CFLAGS) $< -o $@
hello.o: hello.c
gcc $(CFLAGS) -c $< -o $@
如果你为目标hello运行make，则CFLAGS会应用于两个命令：
$ make hello
gcc -g -c hello.c -o hello.o
gcc -g hello.o -o hello
但是，当你只构建hello.o时不会使用给hello的CFLAGS：
$ make hello.o
gcc -c hello.c -o hello.o
当具有不同目标特定变量的两个目标取决于相同的目标时，事情可能会更糟。构建结果将不一致。我认为没有对非叶目标（non-leaf targets）的这个功能的有效使用案例。
我们回到解析上来。像分号一样，我们需要延迟递归变量赋值的右侧的评估。它的实现与分号非常相似，但是赋值和分号的组合使得解析有点棘手。一个例子：
target1: ;X=Y echo $(X) # A rule with a command
target2: X=;Y echo $(X) # A target specific variable
表达式的评估器（Evaluator for expressions）
表达式的评估在expr.cc，func.cc和command.cc中完成。这个步骤的代码量相当大，特别是因为GNU make函数的数量。然而，他们的实现是相当简单的。
一个棘手的功能是$(wildcard ...)。似乎GNU make正在为此功能进行某种优化，命令中的$(wildcard ...)似乎在命令的评估阶段之前进行评估。 C++ Kati和Go Kati两者都以不同的方式与GNU make的行为不同，但似乎这种不兼容性对于Android构建还是OK的。
对Android进行了一个重要的优化。 Android的构建系统有很多$(shell find ...)调用来创建一个目录下的所有.java/.mk文件的列表，它们很慢。为此，Kati有一个GNU find的内置仿真器。该find仿真器遍历目录树并创建内存中的目录树（in-memory directory tree）。然后，该find仿真器使用缓存的树返回find命令的结果。对于我的环境来说，find命令模拟器使得Kati比AOSP快了1.6倍。
命令中的一些IO相关功能的实现在Ninja生成模式下是棘手的。这将在后面描述。
依赖构建器（Dependency builder）
现在我们得到一个规则列表和一个变量表。dep.cc使用规则列表构建依赖图。我认为这个步骤是GNU make对普通用户应该做的。
这个步骤与其他组件类似，相当复杂，但没有什么奇怪的。 GNU make有三种规则：
- 明确规则（explicit rule）
- 隐式规则（implicit rule）
- 后缀规则（suffix rule）
以下代码显示了三种类型：
all: foo.o
foo.o:
echo explicit
%.o:
echo implicit
.c.o:
echo suffix
在上面的例子中，所有这三个规则都匹配目标foo.o。 GNU make首先确定明确规则。当目标没有明确的规则时，它将使用具有较长模式字符串的隐式规则。后缀规则仅在没有明确/隐式规则时使用。
Android有超过一千个隐式规则，有成千上万的目标。使用一个天真的O(NM)算法来匹配它们太慢了。Kati用一个特技加速这一步。
多个没有命令的规则应该合并到有命令的规则中。例如：
foo.o: foo.h
%.o: %.c
$(CC) -c $< -o $@
foo.o不仅取决于foo.c，还取决于foo.h。
执行器（Executor）
C++ Kati的执行器很简单。这在exec.cc中定义。这仅对于测试是有用的，因为它缺少构建系统的一些重要功能（例如并行构建)。
命令中的表达式在这个阶段进行了评估。当他们进行评估时，应考虑目标特定变量（target specific variables）和一些特殊变量（例如$<和$@)。由command.cc处理它们。该文件由执行器和Ninja生成器使用。
当涉及+=和目标特定变量时，此阶段的评估是棘手的。这是一个示例代码：
all: test1 test2 test3 test4
A:=X
B=X
X:=foo
test1: A+=$(X)
test1:
@echo $(A) # X bar
test2: B+=$(X)
test2:
@echo $(B) # X bar
test3: A:=
test3: A+=$(X)
test3:
@echo $(A) # foo
test4: B=
test4: B+=$(X)
test4:
@echo $(B) # bar
X:=bar
这里test3的$(A)是一个简单变量。虽然全局范围内的$(A)是简单变量，但test1中的$(A)是一个递归变量。这意味着全局变量的类型不会影响目标特定变量的类型。但是，test1的结果（“X bar”）显示目标特定变量的值连接到（concatenated）全局变量的值。
Ninja生成器（Ninja generator）
ninja.cc使用其他组件的结果生成一个ninja文件。这一步实际上是相当复杂的，因为Kati需要将GNU make的功能映射到Ninja。
GNU make中的构建规则可能有多个命令，而ninja始终是单个命令。为了减轻这种情况，Ninja生成器将多个命令转换为(cmd1) && (cmd2) && ...。Kati也应该转义一些ninja和shell的特殊字符。
更麻烦的是在命令中的$(shell ...)。当前Kati的实现将其转换为shell的$(...)。这适用于许多情况。但是当$(shell ...)的结果传递给另一个make函数时，这种方法将无法正常工作。例如
all:
echo $(if $(shell echo),FAIL,PASS)
应该输出PASS，因为$(shell echo)的结果是一个空字符串。 GNU make和Kati的执行器模式正确输出PASS。然而，Kati的Ninja生成器生成出一个显示失败的ninja文件。
我为这个问题写了几个实验补丁，但是它们的运行不好。目前的Kati实现具有Android特定的解决方法。有关详细信息，请参阅func.cc中的HasNoIoInShellScript。
Ninja再生（Ninja regeneration）
C++ Kati有--regen标志。如果指定了此标志，则Kati会检查你的环境中的任何内容是否在上次运行后发生更改。如果Kati认为它不需要重新生成Ninja文件，它会很快完成。对于Android，第一次运行Kati需要〜30秒，但第二次运行只需要〜1秒。
Kati认为，当更改以下任一项时，需要重新生成Ninja文件：
- 传递给Kati的命令行标志
- 用于生成上一个ninja文件的Makefile的时间戳
- 评估Makefile时使用的环境变量
- $(wildcard ...)的结果
- $(shell ...)的结果
快速做最后一个检查不是微不足道的。由于$(shell find ...)的缓慢，在Android的构建系统中运行$(shell ...)需要〜18秒。因此，对于由Kati的find仿真器执行的查找命令，Kati通过跟find命令本身一起存储遍历目录的时间戳。对于每个查找命令，Kati检查它们的时间戳。如果它们没有改变，则Kati跳过重新运行find命令。
在此检查过程中，Kati不运行$(shell date ...)和$(shell echo ...)。前者总是改变，所以没有意义重新运行它们。 Android使用后者创建一个文件，其结果是空字符串。我们不想更新这些文件以获取空字符串。
待做事项（TODO）
一个大的TODO是由$(MAKE)调用的sub-makes。我写了一些实验性的补丁，但是还没有什么值得可以用来一写的。
