Angular源码分析:使用数组来存储节点树、对它进行后序遍历
使用数组来存储节点树虽然DOM是以树的方式来组织,但Angular是以平数组的方式来存储view中各个节点(包括DOM节点,也包括Directive节点、Provider节点等)的。 [ {tagName:'ul',childCount:4},{tagName:'li',childCount:2},{tagName:'span',childCount:0},{tagName:'div',childCount:1},childCount:0} ] 就能表示这样一个树形结构: <ul> <li> <span></span> <span></span> </li> <li></li> </ul> <div> <span></span> </div>
平数组的“平”是flat的意思,表示这个数据结构是没有嵌套的。(用嵌套数组也可以表示上面的DOM树结构,比如说使用一个
至于原因,TOBIAS BOSCH在某次会议中给出了回答:如果以树的方式存储,遍历它的时候,不管使用递归还是非递归的方法,都要维护一个栈。而如果用flat数组方式存储这颗树,使用一个for循环就能遍历,遍历速度更快,且遍历需要更少的内存(仅仅需要维护一个迭代的数组下标 后序遍历树用平数组表示以后也能进行后序遍历,Angular在callLifecycleHooksChildrenFirst方法中就实现了后序遍历算法(非递归)。 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都没有定义我们要调用的 接下来就是在for循环中遍历view中的每个节点了,对每个节点 可以推理出 循环中的第一个if语句: if (!parent && nodeDef.flags & lifecycles) { // matching root node (e.g. a pipe) callProviderLifecycles(view,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; } 如果 平数组的迭代就用这样的方式来做“ 剪枝”(直接跳过某个节点下面的子树)。Angular迭代平数组的时候经常使用这种技巧。 循环中的嵌套循环: while (parent && (parent.flags & NodeFlags.TypeElement) && i === parent.nodeIndex + parent.childCount) { // last child of an element if (parent.directChildFlags & lifecycles) { initIndex = callElementProvidersLifecycles(view,initIndex); } parent = parent.parent; } 当 这样继续迭代下去,就能完成对view中所有节点的后序遍历。可以看出,这个后序遍历算法的时间复杂度是O(n)(内层循环不增加复杂度)。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |