分析分析Vue3patch核心算法patchKeyedChildren定位：runtime-core>renderer>baseCreateRenderer>patchKeyedChildrenpatchKeyedChildren是patch算法中比较复杂的一段，也是vue技术栈面试的高频点。起初，我粗略地阅读了vue3.0beta版本中的源代码。后来在《vue设计与分析》看了霍春阳的分析。本文将简要分析并做一个记录。首先在子列表中比较patchKeyedChildren，有key就进入。逻辑大致分为5步。这个看官方源码。从评论中可以看出第一步。从前向后遍历的步骤是从节点组的头部遍历到尾部。如果在遍历过程中遇到相似的节点，则进行补丁比较。否则退出遍历，记录本次遍历的最新一次遍历。下标while(i<=e1&&i<=e2){constn1=c1[i]constn2=(c2[i]=optimized?cloneIfMounted(c2[i]asVNode):normalizeVNode(c2[i]))if(isSameVNodeType(n1,n2)){patch(n1,n2,container,null,parentComponent,parentSuspense,isSVG,slotScopeIds,optimized)}else{break}i++}第二步从后往前遍历，从后往前遍历toback在遍历之前，如果遇到第一步记录的下标就停止，然后在遍历过程中，如果遇到相似的节点，就直接进行patch比较。如果不相同，则直接退出遍历，记录旧节点组和新节点组。尾指针while(i<=e1&&i<=e2){constn1=c1[e1]constn2=(c2[e2]=optimized?cloneIfMounted(c2[e2]asVNode):归一化VNode(c2[e2]))if(isSameVNodeType(n1,n2)){patch(n1,n2,container,null,parentComponent,parentSuspense,isSVG,slotScopeIds,optimized)}else{break}e1--e2--}第三步，检查旧节点组。这一步是检查前两步遍历完是否已经遍历完旧的节点组。如果遍历了，那么没有遍历过的新的节点组就是新的dom，可以认为是new的。添加节点进行挂载处理if(i>e1){if(i<=e2){constnextPos=e2+1constanchor=nextPose2){//旧的子节点还没有被遍历while(i<=e1){unmount(c1[i],parentComponent,parentSuspense,true)i++}}步骤5、未知序列如果新旧节点组都没有遍历过，说明存在未知序列，可能存在位移等，需要进一步处理先创建一个记录新旧节点对应关系的数组//toBePatched为新序列e2-s2+1constnewIndexToOldIndexMap=newArray(toBePatched)for(i=0;i=toBePatched){unmount(prevChild,parentComponent,parentSuspense,true)continue}letnewIndex//具有相同新旧节点键索引的新节点if(prevChild.key!=null){newIndex=keyToNewIndexMap.get(prevChild.key)}else{for(j=s2;j<=e2;j++){if(newIndexToOldIndexMap[j-s2]===0&&isSameVNodeType(prevChild,c2[j]asVNode)){newIndex=jbreak}}}//如果newIndex为空，则表示没有新节点对应找到旧节点，直接卸载if(newIndex===undefined){unmount(prevChild,parentComponent,parentSuspense,true)}else{//更新新旧节点关系表newIndexToOldIndexMap[newIndex-s2]=i+1/***这里的maxNexIndexSoFar是记录每个patch的最大索引*也用于判断是否位移已经发生了，因为如果新节点的索引小于最大索引，则意味着发生了位移*例如：*(ab)c*(acb)*新旧序列比较b和c时，由于c最新的newIndex已经小于b对应的newIndex，所以会记录需要位移*/if(newIndex>=maxNewIndexSoFar){maxNewIndexSoFar=newIndex}else{moved=true}patch(prevChild,c2[newIndex]asVNode,container,null,parentComponent,parentSuspense,isSVG,slotScopeIds,optimized)patched++}}遍历完成旧序列后，需要判断如何移位。首先根据新旧节点关系表生成最长递增子序列（这个算法就不说了，比较复杂，可以看精读《DOM diff 最长上升子序列》），然后倒序遍历新的子节点//FinallyLongincreasingsubsequenceconstincreasingNewIndexSequence=moved?getSequence(newIndexToOldIndexMap):EMPTY_ARRj=increasingNewIndexSequence.length-1//从新序列的末尾向前遍历，目的是将最后遍历的节点作为anchorfor(i=toBePatched-1;i>=0;i--){constnextIndex=s2+iconstnextChild=c2[nextIndex]asVNode//如果是序列的最后一个节点，则anchor为父节点对应的anchor，否则为前一个子节点constanchor=nextIndex+1
