Angular源码分析：使用数组来存储节点树、对它进行后序遍历
猫耳山在天边 2019-06-26
使用数组来存储节点树
虽然DOM是以树的方式来组织，但Angular是以平数组的方式来存储view中各个节点（包括DOM节点，也包括Directive节点、Provider节点等）的。
数组中每个节点有一个childCount属性，表示在这个数组项的后面有多少个节点是它的后代。
举个例子，下面的平数组
[
{tagName:'ul',childCount:4},
{tagName:'li',childCount:2},
{tagName:'span',childCount:0},{tagName:'span',childCount:0},
{tagName:'li',childCount:0},
{tagName:'div',childCount:1},
{tagName:'span',childCount:0}
]就能表示这样一个树形结构：
<ul>
<li>
<span></span>
<span></span>
</li>
<li></li>
</ul>
<div>
<span></span>
</div>平数组的“平”是flat的意思，表示这个数据结构是没有嵌套的。（用嵌套数组也可以表示上面的DOM树结构，比如说使用一个children属性来存储子节点组成的数组，但是这会占用更多的内存）至于原因，TOBIAS BOSCH在某次会议中给出了回答：如果以树的方式存储，遍历它的时候，不管使用递归还是非递归的方法，都要维护一个栈。而如果用flat数组方式存储这颗树，使用一个for循环就能遍历，遍历速度更快，且遍历需要更少的内存（仅仅需要维护一个迭代的数组下标i）。
除了遍历时的性能以外，平数组本身也占用更少的内存（因为数组没有嵌套）。
后序遍历
树用平数组表示以后也能进行后序遍历，Angular在callLifecycleHooksChildrenFirst方法中就实现了后序遍历算法（非递归）。
这个方法的作用是：按照后序的顺序，调用view中各个directive、component的生命周期钩子（仅包括ngAfterContentCheck, ngAfterContentInit, ngAfterViewCheck, ngAfterViewInit，其他生命周期钩子不在这里调用）。
在这篇文章我们先不研究这些钩子，我们仅仅专注于后序遍历是怎么实现的。
export function callLifecycleHooksChildrenFirst(view: ViewData, lifecycles: NodeFlags) {
if (!(view.def.nodeFlags & lifecycles)) {
return;
}
const nodes = view.def.nodes;
let initIndex = 0;
for (let i = 0; i < nodes.length; i++) {
const nodeDef = nodes[i];
let parent = nodeDef.parent;
if (!parent && nodeDef.flags & lifecycles) {
// matching root node (e.g. a pipe)
callProviderLifecycles(view, i, nodeDef.flags & lifecycles, initIndex++);
}
if ((nodeDef.childFlags & lifecycles) === 0) {
// no child matches one of the lifecycles
i += nodeDef.childCount;
}
while (parent && (parent.flags & NodeFlags.TypeElement) &&
i === parent.nodeIndex + parent.childCount) {
// last child of an element
if (parent.directChildFlags & lifecycles) {
initIndex = callElementProvidersLifecycles(view, parent, lifecycles, initIndex);
}
parent = parent.parent;
}
}
}第一个判断语句的意思是，如果此view中的所有directive都没有定义我们要调用的lifecycles，直接返回。（view.def.nodeFlags聚合了view中所有节点的nodeFlags）initIndex的作用是记录view已经对哪些节点调用过了init lifecycle hooks，以防止从错误处理中恢复以后第二次调用节点的init钩子。在这篇文章可以不用管它。
接下来就是在for循环中遍历view中的每个节点了，对每个节点nodeDef都获取到它的parent。
nodeDef的下标在[parent.nodeIndex+1, parent.nodeIndex + parent.childCount]范围内。循环中的第一个if语句：
if (!parent && nodeDef.flags & lifecycles) {
// matching root node (e.g. a pipe)
callProviderLifecycles(view, i, nodeDef.flags & lifecycles, initIndex++);
}假如遇到了没有parent的节点，说明它是view的根节点之一，我们要访问它（也就是调用它的lifecycles）。
注意，一般来说后序遍历要求我们在访问节点之前应该确认它的所有子节点已经被访问过（或者根本就没有子节点）。但由于在Angular中，view中的根节点如果有lifecycles可以调用的话，这个节点只能是pipe或者provider，这种节点都不可能有子节点，因此后序遍历可以直接访问这个根节点。循环中的第二个if语句：
if ((nodeDef.childFlags & lifecycles) === 0) {
// no child matches one of the lifecycles
i += nodeDef.childCount;
}如果(nodeDef.childFlags & lifecycles) === 0，也就是说这个nodeDef的所有后代节点都没有符合的lifecycles方法可以调用（用户没有定义ngAfterViewCheck这些方法）（nodeDef.childFlags聚合了nodeDef所有后代节点的nodeFlags），则可以直接跳过nodeDef的所有后代节点：i += nodeDef.childCount，这个语句直接增加for循环的迭代下标，使for循环跳过nodeDef的所有后代节点。
循环中的嵌套循环：
while (parent && (parent.flags & NodeFlags.TypeElement) &&
i === parent.nodeIndex + parent.childCount) {
// last child of an element
if (parent.directChildFlags & lifecycles) {
initIndex = callElementProvidersLifecycles(view, parent, lifecycles, initIndex);
}
parent = parent.parent;
}当i === parent.nodeIndex + parent.childCount成立的时候，意味着当前迭代的节点nodeDef是parent的最后一个后代节点。根据后序遍历的要求，因为parent的所有后代节点都已经访问过，所以此时应该访问parent节点（调用它的钩子）。
访问完parent以后，parent = parent.parent;找到更上层的父节点，继续做i === parent.nodeIndex + parent.childCount的检查（nodeDef可能同时是多个祖先节点的最后一个后代，比如{tagName:'ul',childCount:2},{tagName:'li',childCount:1},{tagName:'span',childCount:0}中，<span>同时是<ul>和<li>的最后一个后代）。
这样继续迭代下去，就能完成对view中所有节点的后序遍历。可以看出，这个后序遍历算法的时间复杂度是O(n)（内层循环不增加复杂度）。
