Ninja 构建图模型：Node、Edge、State、Pool

整个 Ninja 在内存里就是一张二部图：一类节点是文件（Node），一类节点是命令（Edge），边相连表示”谁是谁的输入/输出”。这张图是后面所有阶段（脏检查、调度、执行）的共同底座。本文拆解它的四个核心数据结构。前置阅读：架构概述。

        in_edge (唯一)                 out_edges (多个)
   ┌──────────────────┐          ┌──────────────────────┐
   │                  ▼          │                      ▼
 Edge ───outputs──► Node ───────── Node ◄──inputs─── Edge
 (命令)            (文件)          (文件)            (命令)

1. Node：一个文件

struct Node（graph.h:42）代表构建图里的一个文件（源文件或产物）。它的关键成员（graph.h:121-171）：

成员	行	含义
path_	122	规范化后的路径，也是驻留用的 key
slash_bits_	126	记录哪些 / 原本是 \（Windows 反规范化用）
mtime_	132	-1=未检查、0=不存在、>0=mtime
exists_	142	Unknown/Missing/Exists 枚举
dirty_	147	是否过时
dyndep_pending_	151	期待 dyndep 信息但尚未加载
id_	161	DepsLog 分配的密集整数 id
in_edge_	165	唯一生产它的边（源文件为 nullptr）
out_edges_	168	所有把它当输入的边
validation_out_edges_	171	所有把它当 validation（|@）的边

mtime_ 的三态约定值得记住（graph.h:128-132）：-1 表示”还没 stat 过”，0 表示”stat 过、文件不存在”，正数才是真实 mtime。Node::StatIfNecessary（graph.h:53）正是基于 status_known() 做记忆化，保证脏检查遍历里同一个 Node 只 stat 一次。

注意 in_edge_ 是单数：一个文件至多由一条边生产，这个不变量在建图时强制（见 §4）。

2. Edge：一条命令

struct Edge（graph.h:175）是构建的基本工作单元——一条把若干输入变成若干输出的命令。关键成员（graph.h:214-232）：

const Rule* rule_ = nullptr;        // graph.h:214  非拥有，指向规则
Pool* pool_ = nullptr;             // graph.h:215  归属的并发池
std::vector<Node*> inputs_;        // graph.h:216  显式→隐式→order-only 三段
std::vector<Node*> outputs_;       // graph.h:217  显式→隐式 两段
std::vector<Node*> validations_;   // graph.h:218  |@ 校验目标
Node* dyndep_ = nullptr;          // graph.h:219  提供 dyndep 信息的节点
BindingEnv* env_ = nullptr;       // graph.h:220  本边的变量作用域
int64_t critical_path_weight_ = -1;// graph.h:222  关键路径权重（调度优先级）
bool outputs_ready_ = false;       // graph.h:228  输出是否已就绪
bool deps_loaded_ = false;         // graph.h:229  隐式依赖是否已加载

一个澄清：Edge 里没有 EdgeStatus 枚举。它唯一的嵌套枚举是 VisitMark { VisitNone, VisitInStack, VisitDone }（graph.h:176），在脏检查时做 DAG 环检测。边的”构建进度”靠几个 bool 标志（outputs_ready_ 等）以及 Plan 那边独立的 Want 枚举来表达，不在图模型里。

2.1 依赖的三段式存储

这是构建图模型最精巧的地方。Ninja 的 manifest 语法支持三种输入：

build out.o: cc in.c | header.h || generated_dir
#            ^^^^      ^^^^^^^^    ^^^^^^^^^^^^^
#            显式       隐式(|)     order-only(||)

它们不分三个数组存，而是按”显式 → 隐式 → order-only”的顺序塞进同一个 inputs_ 向量，只额外记两个尾部计数 implicit_deps_（graph.h:247）和 order_only_deps_（graph.h:248）。显式数量靠减法得出：

// graph.h:249-255
bool is_implicit(size_t index) {
  return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
      !is_order_only(index);
}
bool is_order_only(size_t index) {
  return index >= inputs_.size() - order_only_deps_;
}

输出同理：outputs_ 按”显式 → 隐式”存，只记一个 implicit_outs_（graph.h:262），隐式输出不进 $out：

// graph.h:263-265
bool is_implicit_out(size_t index) const {
  return index >= outputs_.size() - implicit_outs_;
}

这三种依赖的语义差别（在 增量构建 里会用到）：

类型	语法	进 $in？	mtime 参与脏检查？
显式输入	build o: r a b	✅	✅
隐式输入	| h1 h2	❌	✅
order-only	|| d	❌	❌（只保证先后顺序）

order-only 依赖只保证”d 先于本边构建”，但 d 变新不会让本边变脏——典型用于”先建好目录”这类不影响产物内容的前置条件。

2.2 边的关键方法

实现都在 graph.cc：

• AllInputsReady()（graph.cc:395）——任一输入的生产边尚未 outputs_ready 则返回 false。
• EvaluateCommand(incl_rsp_file)（graph.cc:515）——展开 command 变量，可选拼接 rspfile。
• GetBinding / GetBindingBool（graph.cc:525）——通过 EdgeEnv 查变量（见 Manifest 解析）。
• is_phony()（graph.cc:577）、use_console()（graph.cc:581）。

$in/$out 不是预先存好的字符串，而是在求值时由 EdgeEnv::LookupVariable（graph.cc:423）按上面的计数实时切片合成：

// graph.cc:425-432
int explicit_deps_count =                       // $in 只取显式输入
    edge_->inputs_.size() - edge_->implicit_deps_ - edge_->order_only_deps_;
int explicit_outs_count =                       // $out 只取显式输出
    edge_->outputs_.size() - edge_->implicit_outs_;

2.3 隐式依赖回填时如何维持分段不变量

当从 depfile/deps log 加载到新的隐式依赖时（依赖发现），它们必须插在”隐式段之后、order-only 段之前”，否则上面的下标算法就乱了。代码用一个精确的插入位置维护这个不变量（graph.cc:766）：

edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
                     nodes, nodes + node_count);   // 插在 order-only 尾段之前
edge->implicit_deps_ += node_count;                // 隐式计数增加

3. Rule：命令模板

struct Rule（定义在 eval_env.h:66，不在 graph.h）是一组未展开的变量绑定（command、depfile、description 等）：

struct Rule {
  // ...
  static bool IsReservedBinding(const std::string& var);   // eval_env.h:77
 private:
  std::string name_;                                       // eval_env.h:85
  typedef std::map<std::string, EvalString> Bindings;      // eval_env.h:86
  Bindings bindings_;                                      // 值是未求值的 EvalString
  bool phony_ = false;                                     // eval_env.h:88
};

规则里的值存成 EvalString（已切分的 token 列表，eval_env.h:35），延迟到每条边求值时才结合该边的作用域展开。IsReservedBinding（eval_env.cc:77）是合法规则变量名的白名单：command, depfile, dyndep, description, deps, generator, pool, restat, rspfile, rspfile_content, msvc_deps_prefix。

Edge::rule_ 是非拥有指针（graph.h:214），规则本身由 BindingEnv::rules_（eval_env.h:117，map<string, unique_ptr<const Rule>>）拥有。内置的 phony 规则由 Rule::Phony()（eval_env.cc:66）创建。

4. State：全局图与字符串驻留

class State（state.h:95）持有整张图：

typedef ExternalStringHashMap<Node*>::Type Paths;  // state.h:131
Paths paths_;                                      // state.h:132  路径 → Node
std::map<std::string, Pool*> pools_;               // state.h:135
std::vector<Edge*> edges_;                          // state.h:138
BindingEnv bindings_;                               // state.h:140  根作用域
std::vector<Node*> defaults_;                       // state.h:141  默认目标
static Pool kDefaultPool; static Pool kConsolePool; // state.h:96-97

4.1 路径驻留（interning）

GetNode 保证同一路径全程只有一个 Node 对象（state.cc:95）：

Node* State::GetNode(StringPiece path, uint64_t slash_bits) {
  Node* node = LookupNode(path);
  if (node) return node;                        // 命中：复用
  node = new Node(path.AsString(), slash_bits);
  paths_[node->path()] = node;                  // key 借用 Node 拥有的 string
  return node;
}

关键技巧：哈希表的 key 是 StringPiece，借用 Node 自己拥有的 std::string（node->path()），所以路径字符串不会被存两份——这就是 Ninja 的字符串驻留机制。底层哈希表是 ExternalStringHashMap（hash_map.h:42），用第三方开放寻址表 emhash8 + rapidhash：

// hash_map.h:42-45
template<typename V>
struct ExternalStringHashMap {
  typedef emhash8::HashMap<StringPiece, V> Type;
};

“External”（外部）正是指 key 字符串存在别处（Node 里），表本身零拷贝。

4.2 建图与单生产者不变量

• AddEdge（state.cc:85）new 一个 Edge，设规则、默认 pool、根作用域、单调 id，压进 edges_。
• AddIn（state.cc:128）把节点加进 edge->inputs_，并 node->AddOutEdge(edge)。
• AddOut（state.cc:135）——这里强制单生产者不变量：若目标节点已有 in_edge()，报错 “multiple rules generate”；否则 node->set_in_edge(edge)。

RootNodes（state.cc:169）= 没有 out_edges 的输出节点（即最终产物）。DefaultNodes（state.cc:187）= defaults_，为空时退化为 RootNodes——这就是 ninja 不带参数时构建什么的来源。Reset（state.cc:191）清空每次运行的临时状态（mtime、outputs_ready_ 等）但保留图结构，供重建循环复用。

5. Pool：图层面的并发限制

class Pool（state.h:40）给”一组边”设并发上限：

bool ShouldDelayEdge() const { return depth_ != 0; }   // state.h:51  depth 0 = 无限
// ...
int current_use_;  // state.h:75  已调度边的权重和
int depth_;        // state.h:76  容量
DelayedEdges delayed_; // state.h:91  被延迟的边（按 WeightedEdgeCmp 排序）

机制实现在 state.cc:26-62：EdgeScheduled/EdgeFinished 增减 current_use_；DelayEdge 把超额的边塞进 delayed_ 集合；RetrieveReadyEdges（state.cc:41）在有容量时按优先级放出延迟的边，遇到第一个会超容量的就停。由于 Edge::weight() 恒为 1（graph.h:236），depth_ 实际就是池内最大并发边数。

两个内置 pool（state.cc:64）：kDefaultPool("", 0)（深度 0 = 无限，默认）和 kConsolePool("console", 1)（深度 1，串行、独占终端）。Edge::use_console()（graph.cc:581）就是判断 pool() == &kConsolePool。

注意：图模型只提供这套”延迟/放出”机制，真正调用它的是 Plan（见 构建执行流程）。

5.1 调度优先级：EdgePriorityQueue

就绪边不是 FIFO，而是按关键路径权重排优先级。EdgePriorityQueue（graph.h:423）是个 std::priority_queue，比较器 EdgePriorityLess（graph.h:402）按 critical_path_weight() 高者优先、id 小者次之。权重由 Plan::ComputeCriticalPath（build.cc:472）算出——先调度最长依赖链上的边，能最大化后续并行、缩短总时间。

6. 小结：行号速查

结构	位置
Node（成员）	graph.h:42（121-171）
Edge（成员）	graph.h:175（214-232）
依赖三段式下标	graph.h:249、graph.h:263
隐式依赖回填插入点	graph.cc:766
Rule	eval_env.h:66
State（成员）	state.h:95
路径驻留 GetNode	state.cc:95
单生产者 AddOut	state.cc:135
自定义哈希表	hash_map.h:42
Pool	state.h:40、实现 state.cc:26
优先队列	graph.h:402

下一篇 Manifest 解析 看这张图是如何从 build.ninja 文本构造出来的。