preface
Vue should be the most widely used front-end framework in China, mainly because of its low learning cost and easy to use. Most developers probably only need to go through the documentation once to get started.
I used to be one of them. Vue has been used for a long time, but it has been stuck in the use stage without exploring its underlying implementation principles and design ideas.
What is the difference between life without pursuit and salted fish? Then roll up your sleeves and you’re done! (An important reason is that more and more people learn the source code, I do not want to be their volume dead, that can only work hard volume dead others ðŸ˜)
Hope to learn through Vue3 source code series, record their own learning process experience summary, in order to review in the future. If there is an incorrect place in the article, I hope the various big men will correct it.
Virtual DOM
What is the virtual DOM? Simple to do, is to use JS to describe the real DOM object structure. (Vue uses ATS to form an abstract syntax tree during compilation)
The advantage of this is that some useless information in the DOM is discarded, which makes the entire tree structure of the DOM simpler and clearer, and makes DOM manipulation more flexible.
Old rules, for example 🌰 :
The real DOM
<ul id="list">
<li class="item">Zhang SAN</li>
<li class="item">Li si</li>
<li class="item">Cathy</li>
</ul>
Copy the codeVirtual DOM
{
tag:'ul'.props: {id:'list' },
children: [{tag: 'li'.props: {class:'item'}, children:'Joe' },
{ tag: 'li'.props: {class:'item'}, children:'bill' },
{ tag: 'li'.props: {class:'item'}, children:'Cathy'}}]Copy the codeIf you change Wang Wu to Zhao 6, the new virtual DOM will become:
{
tag:'ul'.props: {id:'list' },
children: [{tag: 'li'.props: {class:'item'}, children:'Joe' },
{ tag: 'li'.props: {class:'item'}, children:'bill' },
{ tag: 'li'.props: {class:'item'}, children:'Daisy'}}]Copy the codeIt has long been said that Vue’s high performance is due to the use of the virtual DOM. Is it really better to replace the old virtual DOM with a new virtual DOM than to replace the real DOM? Let’s compare the two processes:
As we can see in the second method, simply replacing the old virtual DOM with the new virtual DOM and rendering it to the real DOM is no better in terms of performance than rendering the real DOM.
The real situation is that Vue compares the old and new virtual DOM through a differentiated algorithm to find out the virtual DOM nodes that need to be changed. In the real DOM structure, only the DOM nodes that need to be changed are operated.
Therefore, a more precise statement should be that the performance of operating the real DOM through the differentiated algorithm of the virtual DOM is higher than that of directly operating the real DOM. The differentiation algorithm of virtual DOM is the Diff algorithm that we will talk about next.
Instead of just learning the Diff algorithm in Vue3, learning the Diff algorithm of Vue2 and Vue3 at the same time should be able to better understand the optimization points of Vue3
Diff’s basic principles
You’re only comparing at the same level, not across levels
Only nodes of the same type are compared. If the nodes are not of the same type, the old nodes are destroyed and new nodes are created
// Vue3 /packages/runtime-core/src/vnode.ts
export function isSameVNodeType(n1: VNode, n2: VNode) :boolean {
return n1.type === n2.type && n1.key === n2.key
}
Copy the codeVirtual DOM Diff algorithm in Vue2
Let’s take a look at some of Vue2’s core code related to the virtual DOM
Patch (The core flow is in this function)
The patch method compares whether the new and old virtual nodes are of the same type
- Yes: Use patchVnode to perform a deeper comparison
- If no, replace the old node with the new one
// /src/core/vdom/patch.js
/ * * *@param OldVnode The old virtual DOM node, which may not exist or may be a DOM object *@param Vnode new virtual DOM node *@param Hydrating is server side rendering@param RemoveOnly is */ for transition-group
function patch(oldVnode, vnode, hydrating, removeOnly) {
if (isUndef(vnode)) {
// If there is no new node but the old one exists, the destroy hook is triggered directly
if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
return;
}
let isInitialPatch = false;
const insertedVnodeQueue = [];
if (isUndef(oldVnode)) {
// If the old node does not exist, create a new node
isInitialPatch = true;
createElm(vnode, insertedVnodeQueue);
} else {
// When both old and new nodes exist
// Check whether the old node is a real node (dom element nodeType is 1)
const isRealElement = isDef(oldVnode.nodeType);
// Compare nodes of the same type
if(! isRealElement && sameVnode(oldVnode, vnode)) {// If the old node is not a real node and the old node is the same node, the comparison is further modified
patchVnode(oldVnode, vnode, insertedVnodeQueue, null.null, removeOnly);
} else {
// The old node is not a real element, or the old and new nodes are not the same node
if (isRealElement) {
// Mount real elements and handle server-side rendering.
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
oldVnode.removeAttribute(SSR_ATTR);
hydrating = true;
}
if (isTrue(hydrating)) {
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
invokeInsertHook(vnode, insertedVnodeQueue, true);
return oldVnode;
} else if(process.env.NODE_ENV ! = ='production') {
warn(
'The client-side rendered virtual DOM tree is not matching ' +
'server-rendered content. This is likely caused by incorrect ' +
'HTML markup, for example nesting block-level elements inside ' +
'<p>, or missing <tbody>. Bailing hydration and performing ' +
'full client-side render.'); }}// Instead of server rendering or server rendering failure, oldVnode is converted to VNode objects.
oldVnode = emptyNodeAt(oldVnode);
}
// The real DOM of the old node
const oldElm = oldVnode.elm;
// The parent of the old node
const parentElm = nodeOps.parentNode(oldElm);
// Create a DOM node based on the new vNode and mount it to the parent node
createElm(
vnode,
insertedVnodeQueue,
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
);
// Recursively update the parent component placeholder, only the component's rendering VNode has vNode.parent
// Consider this case:
// Parent-component template is:
//
//
sameVnode
The someVnode method determines whether a node is of the same type
// Vue2 /src/core/vdom/patch.js
// Compare key and tag names
function sameVnode (a, b) {
return (
a.key === b.key && // Check whether the label name is the same
a.asyncFactory === b.asyncFactory && ( // Are both asynchronous factory methods
(
a.tag === b.tag && // Check whether the label name is the same
a.isComment === b.isComment && // whether all are comment nodes
isDef(a.data) === isDef(b.data) && // Whether data is defined
sameInputType(a, b) // When the label is input, the type must be the same
) || (
isTrue(a.isAsyncPlaceholder) && // Whether there are asynchronous placeholder nodes
isUndef(b.asyncFactory.error)
)
)
)
}
Copy the codepatchVnode
If the old and new nodes are SamevNodes, the DOM node is not recreated, but the original DOM node is patched through the patchVnode method.
The rough logic of the patch is this:
-
If oldVnode and vNode are the same reference object, return it directly
-
If oldVnode isAsyncPlaceholder is true, the current node isAsyncPlaceholder
-
If oldVnode and vnode are static nodes with equal keys, and vnode is a clone or v-once, copy oldvNode. elm and oldvNode. child to vnode, and return
-
If the vNode is not a text node, proceed as follows:
-
If both vNode and oldVnode have child nodes and the child nodes are not the same reference object, updateChildren is called to update the child node
-
If only vNodes have child nodes, create child nodes (addVnodes)
-
If only oldvNodes have child nodes, remove the child node (removeVnodes)
-
If oldVnode is a text node, delete the text directly from the DOM
-
-
If vNode is a text node, and the text content is different from oldVnode, the text on the DOM is updated directly
/ * * *@param OldVnode The old virtual DOM node *@param Vnode new virtual DOM node *@param InsertedVnodeQueue Queue for inserting a node@param ownerArray
* @param index
* @param removeOnly* /
function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
// If the old node and the new node are the same reference object, it is returned directly
if (oldVnode === vnode) {
return;
}
// If the elm property of the virtual node is present, then it is rendered. If the ownerArray is present, then there are children. If both are true, clone a vNode
if (isDef(vnode.elm) && isDef(ownerArray)) {
vnode = ownerArray[index] = cloneVNode(vnode);
}
const elm = (vnode.elm = oldVnode.elm);
// Whether oldVnode has asynchronous placeholders
if (isTrue(oldVnode.isAsyncPlaceholder)) {
// Whether vNode has asynchronous factory functions, mainly used by asynchronous components
if (isDef(vnode.asyncFactory.resolved)) {
hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
} else {
vnode.isAsyncPlaceholder = true;
}
return;
}
// Handle static nodes
// oldVnode and vnode are static nodes with the same key attribute, and vnode is a clone of the virtual DOM or a component with V-once
// Updates the componentInstance property and returns it directly, indicating that the entire component has not changed
if (
isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
) {
vnode.componentInstance = oldVnode.componentInstance;
return;
}
let i;
const data = vnode.data;
// When a vNode is a component, the hook contains init, prepatch, insert, and destroy
// init instantiates the child component
// prepatch updates child components
// Insert calls the 'Mounted' life cycle of a child component, or triggers the component's activated life cycle when keepAlive exists
// Destroy calls the child's 'destroyed' life cycle or triggers the component's Deactivated life cycle when 'keepAlive' exists
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
i(oldVnode, vnode);
}
const oldCh = oldVnode.children;
const ch = vnode.children;
UpdateAttrs, updateClass, updateDOMListeners, updateDOMProps, updateStyle, updateDrectives
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
}
if (isUndef(vnode.text)) {
Vnode is not a text component
if (isDef(oldCh) && isDef(ch)) {
// oldVnode and vNode both have child nodes, and if the child nodes are not the same reference object, update the child node
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly); }else if (isDef(ch)) {
// If oldVnode does not have children and vnode does
// When oldVnode is a text node, empty text is used first
// Then create child nodes
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ');
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
// If oldVnode has child nodes and vnode does not, delete the child nodes
removeVnodes(oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) {
// If oldVnode is a text node, it is null
nodeOps.setTextContent(elm, ' '); }}else if(oldVnode.text ! == vnode.text) {// If vNode is a text node and the oldVnode text content is different, the text on the DOM is updated directly
nodeOps.setTextContent(elm, vnode.text);
}
if (isDef(data)) {
// Call the postPatch hook
if(isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode); }}Copy the codeUpdateChildren (Diff)
UpdateChildren should be the most important method in the patch process. It is mainly used to compare the child nodes of the old and new virtual DOM. Diff algorithm is introduced in this process. The comparison method is the head to tail pointer method (or two-end comparison method),
NewS, NewE, OldS and OldE respectively represent the start and end indexes of the old and new arrays of two child nodes. Pin-wise comparison is conducted according to OldS and NewS, OldE and NewE, OldS and NewE, OldE and NewS, and the comparison follows the following principles:
- OldS and NewS have the same type of node (sameVnode) with unchanged position, and both OldS and NewS are +1
- OldE and NewE have the same type of node (sameVnode), the position is unchanged, OldE and NewE are -1
- OldS and NewE have the same type of node (sameVnode). After OldS moves to OldE, OldS +1, NewE -1
- OldE and NewS have the same type of node (sameVnode). Before OldE moves to OldS, NewS +1, OLDE-1
- If the preceding four conditions are not met, the index table between OldS and OldE is generated according to the key, and the node key pointed to by NewS is searched in the index table to find whether the node is between OldS and OldE: If so, move to the front of OldS directly, and set the old node as undefined. If not, after creation, move to the front of OldS, NewS +1
- When the old node is traversed first (OldS > OldE), the nodes between [NewS, NewE] are inserted into the real DOM (before the node of NewS+1)
- When the new node is traversed first (NewS > NewE), nodes between [OldS, OldE] are removed from the real DOM
Do you feel confused? Don’t panic, let’s go through a few legends to understand the process, and finally look at the code.
We can see:
- The old child nodes are a, B, and c
- The new children are a, C, and b
- NewS, NewE, OldS, and OldE represent the start and end position indexes of the old and new child node arrays respectively
First comparison:
It can be seen that OldS and NewS point to node A of the same type (rule 1 is used), the position of the node does not need to be moved, and both OldS and NewS are +1
Second comparison:
- OldS and NewS do not point to the same type of node (rule 1 does not apply)
- OldE and NewE do not point to the same type of node (rule 2 does not apply)
- OldS and NewE refer to the same type of node B (rule 3 applies). We move OldS after OldE, OldS +1, NewE -1
It is important to note that we are manipulating real DOM nodes by moving node positions
Third comparison:
OldS and NewS point to node C of the same type (rule 1 applies), and the position of the node does not need to be moved. Meanwhile, both OldS and NewS +1
At this point, OldS is greater than OldE and NewS is greater than NewE, indicating that both the old and new child nodes have been checked.
What if there are more new child nodes than old child nodes?
As shown above, we can see several things:
- The new child node has one more C node than the old one
- In the new child nodes, the positions of d and d are changed
First comparison:
It can be seen that OldS and NewS point to node A of the same type (rule 1 is used), the position of the node does not need to be moved, and both OldS and NewS are +1
Second comparison:
- OldS and NewS do not point to the same type of node (rule 1 does not apply)
- OldE and NewE do not point to the same type of node (rule 2 does not apply)
- OldS and NewE refer to node B of the same type (rule 3 applies). We move OldS after OldE, OldS +1, NewE -1
Third comparison:
- OldS and NewS do not point to the same type of node (rule 1 does not apply)
- OldE and NewE refer to the same type of node (rule 2 applies), the node position is unchanged, OldE and NewE are -1
At this point, OldS is greater than OldE, indicating that the old child node has been traversed, while NewS is equal to NewE, the new child node has not been traversed, and the new child node is more than the old child node, so more child nodes need to be inserted into the real DOM.
The important thing to note here is where the extra child nodes are inserted. As per rule 6, you need to insert before the node of NewS+1. At this point, NewS points to C and becomes D after +1, so it needs to be inserted before the real DOM node corresponding to D.
There are more old child nodes than new child nodes, which is just to remove the redundant nodes directly. The logic is relatively simple, so there is no separate example.
Finally, let’s look at a more complicated case:
First comparison:
- OldS and NewS do not point to the same type of node (rule 1 does not apply)
- OldE and NewE do not point to the same type of node (rule 2 does not apply)
- OldS and NewE do not refer to the same type of node (rule 3 does not apply)
- OldE and NewS point to the same type of node (rule 4 applies). Before OldE moves to OldS, NewS +1, OLDE-1
Second comparison:
- OldS and NewS do not point to the same type of node (rule 1 does not apply)
- OldE and NewE do not point to the same type of node (rule 2 does not apply)
- OldS and NewE do not refer to the same type of node (rule 3 does not apply)
- OldE and NewS do not point to the same type of node (rule 4 does not apply)
If the first four rules are not met, then we can only judge the action by rule 5. Remember rule 5?
The index table between OldS and OldE is generated according to the key, and whether the node is between OldS and OldE is searched in the index table through the key pointing to the node by NewS: if so, move to the front of OldS directly, and set the old node as undefined; if not, move to the front of OldS after creation. NewS +1
- {b:0, D :1, c:2}
- The key of the node pointed to by NewS is E, which cannot be found in the index table, so the node is not between OldS and OldE
- Create the real DOM of the node and insert it before the real DOM that OldS points to, NewS +1
Third comparison:
- OldS and NewS point to the same type of node (rule 1 applies), the node position remains unchanged, and both OldS and NewS +1
The fourth comparison: the same as the second comparison, not detailed description, directly above
At this point, NewS is greater than NewE, indicating that the new child node has been traversed, while OldS is smaller than OldE, indicating that there are redundant old child nodes to be removed.
So far, we have a general understanding of the Diff algorithm for the virtual DOM in Vue2 through the legend. Let’s look at the code again:
/ * * *@param ParentElm Parent node *@param OldCh An array of children of the old VNode *@param NewCh Array of children of the new VNode *@param insertedVnodeQueue
* @param removeOnly* /
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0;
let newStartIdx = 0;
// The last index of the old child node
let oldEndIdx = oldCh.length - 1;
// First old child node
let oldStartVnode = oldCh[0];
// The last old child node
let oldEndVnode = oldCh[oldEndIdx];
// The last index of the new child node
let newEndIdx = newCh.length - 1;
// First new child node
let newStartVnode = newCh[0];
// The last new child node
let newEndVnode = newCh[newEndIdx];
let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
constcanMove = ! removeOnly;while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// oldStartVnode and oldEndVnode are undefined because the logic in the last else may set the old child node to undefined (one of the cases of rule 5)
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// oldStartVnode and newStartVnode are the same VNode (Rule 1)
// Use patchVnode to patch
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// oldEndVnode and newEndVnode are the same VNode (rule 2)
// Use patchVnode to patch
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// oldStartVnode and newEndVnode are the same VNode (rule 3)
// Patch with patchVnode and move the node
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
);
canMove &&
nodeOps.insertBefore(
parentElm,
oldStartVnode.elm,
nodeOps.nextSibling(oldEndVnode.elm)
);
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// oldEndVnode and newStartVnode are the same VNode (Rule 4)
// Patch with patchVnode and move the node
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
canMove &&
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
// Handle rule 5
// Create index between OldS and OldE based on key
if (isUndef(oldKeyToIdx))
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
// Find if the new child is between oldStartIdx and oldEndIdx
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
if (isUndef(idxInOld)) {
// If the new child node does not exist, a new real DOM node is created and inserted before the real DOM node corresponding to oldStartVnode
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
);
} else {
// If a new child node exists, move it directly before the actual DOM node corresponding to oldStartVnode and set the old node to undefined
// The key is the same, but the node type is different
vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
oldCh[idxInOld] = undefined;
canMove &&
nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
} else {
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false, newCh, newStartIdx ); } } newStartVnode = newCh[++newStartIdx]; }}if (oldStartIdx > oldEndIdx) {
// If newChildren has redundant nodes, add these new nodes
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm;
addVnodes(
parentElm,
refElm,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
);
} else if (newStartIdx > newEndIdx) {
// If newChildren is traversed, there are redundant nodes in oldChildrenremoveVnodes(oldCh, oldStartIdx, oldEndIdx); }}Copy the codeVirtual DOM Diff algorithm in Vue3
patch
The core process is also in the patch function. Let’s take a look at the internal logic
// /packages/runtime-core/src/renderer.ts
const patch: PatchFn = (
n1,
n2,
container,
anchor = null,
parentComponent = null,
parentSuspense = null,
isSVG = false,
slotScopeIds = null,
optimized = false
) = > {
// If the old and new vNodes are the same object, no processing is performed
if (n1 === n2) {
return;
}
// If the old VNode exists and the new VNode is not of the same type, uninstall the old VNode
if(n1 && ! isSameVNodeType(n1, n2)) { anchor = getNextHostNode(n1); unmount(n1, parentComponent, parentSuspense,true);
n1 = null;
}
// If patchFlag of the new VNode is BAIL, it will not be optimized during diff
if (n2.patchFlag === PatchFlags.BAIL) {
optimized = false;
n2.dynamicChildren = null;
}
const { type, ref, shapeFlag } = n2;
// Processing varies according to the VNode type
switch (type) {
case Text: // Text node
processText(n1, n2, container, anchor);
break;
case Comment: // Comment the node
processCommentNode(n1, n2, container, anchor);
break;
case Static: // Static node
if (n1 == null) {
// If the old VNode does not exist, mount the new node directly
mountStaticNode(n2, container, anchor, isSVG);
} else if (__DEV__) {
patchStaticNode(n1, n2, container, isSVG);
}
break;
case Fragment: // // Fragment node
processFragment(
n1,
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
break;
default:
if (shapeFlag & ShapeFlags.ELEMENT) { // Element node
processElement(
n1,
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else if (shapeFlag & ShapeFlags.COMPONENT) { // Component type node
processComponent(
n1,
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else if (shapeFlag & ShapeFlags.TELEPORT) { // Teleport node
(type as typeof TeleportImpl).process(
n1 as TeleportVNode,
n2 as TeleportVNode,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized,
internals
);
} else if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) { Suspense type nodes
(type as typeof SuspenseImpl).process(
n1,
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized,
internals
);
} else if (__DEV__) {
warn('Invalid VNode type:'.type.` (The ${typeof type}) `); }}// set ref
if(ref ! =null && parentComponent) {
setRef(ref, n1 && n1.ref, parentSuspense, n2 || n1, !n2);
}
};
Copy the codeisSameVNodeType
// /packages/runtime-core/src/vnode.ts
export function isSameVNodeType(n1: VNode, n2: VNode) :boolean {
if (
__DEV__ &&
n2.shapeFlag & ShapeFlags.COMPONENT &&
hmrDirtyComponents.has(n2.type as ConcreteComponent)
) { // Logic in development mode is ignored
return false
}
// The vNodes are of the same type only when the types and keys of the old and new VNodes are the same
return n1.type === n2.type && n1.key === n2.key
}
Copy the codePatchFlags
Vue2 will perform full diff for VNode during patch phase, but we know that some nodes only declare dynamic text or dynamic class/style, so there is no need to perform full diff.
Therefore, VUe3 has optimized this part. After the AST tree is generated, corresponding patchFlag will be added to the VNode generation according to the characteristics of the node, so as to achieve targeted update of the node.
Let’s first look at the definition of PatchFlags:
// /packages/shared/src/patchFlags.ts
export const enum PatchFlags {
// Dynamic text node
// Decimal: 1
// Binary: 0000 0000 0001
TEXT = 1./ / dynamic class
// Decimal: 2
// binary: 0000 0000 0010
CLASS = 1 << 1./ / dynamic style
// Decimal: 4
// binary: 0000 0000 0100
STYLE = 1 << 2.// Dynamic property, but does not contain class name and style. If it is a component, it can include the class name and style
// Decimal: 8
// binary: 0000 0000 1000
PROPS = 1 << 3.// Has a dynamic key property. When the key changes, a full diff comparison is required.
// Decimal: 16
// Binary: 0000 0001 0000
FULL_PROPS = 1 << 4.// A node with a listening event
// Decimal: 32
// Binary: 0000 0010 0000
HYDRATE_EVENTS = 1 << 5.// A fragment that does not change the order of child nodes
// Decimal: 64
// Binary: 0000 0100 0000
STABLE_FRAGMENT = 1 << 6.// Fragment with key attribute or fragment with key
// Decimal: 128
// Binary: 0000 1000 0000
KEYED_FRAGMENT = 1 << 7.// The child node does not have a key fragment
// Decimal: 256
// Binary: 0001 0000 0000
UNKEYED_FRAGMENT = 1 << 8.// a node will only make non-props comparisons
// Decimal: 512
// binary: 0010 0000 0000
NEED_PATCH = 1 << 9./ / dynamic slot
// Decimal: 1024
// binary: 0100 0000 0000
DYNAMIC_SLOTS = 1 << 10.// Identifies the fragment created by placing a * comment at the root level of the template. This is a developer only flag because * comments are stripped out in production.
// Decimal: 2048
// binary: 1000 0000 0000
DEV_ROOT_FRAGMENT = 1 << 11.// Static node
HOISTED = -1.// Indicates that optimization mode should be exited during diff
BAIL = -2,}Copy the codePatchFlag is divided into two categories:
- When the value of patchFlag is greater than 0, it means that the corresponding element can be optimized to generate or update in patchVNode or Render.
- When the value of patchFlag is less than 0, it means that the corresponding element needs to be diff in patchVNode, that is, the comparison and update process of recursive traversal of VNode tree is carried out.
The specific use of PatchFlags will be discussed in combination with specific codes later.
ShapeFlags
ShapeFlag literally translates to ShapeFlag. It is used to flag the shape (exactly what kind of node) of a node, such as normal elements, function components, normal components, Keep Alive routing components, etc. In order to help render, different patch operations can be performed according to the enumeration values of different ShapeFlag.
// /packages/shared/src/shapeFlags.ts
export const enum ShapeFlags {
ELEMENT = 1.// Common elements
FUNCTIONAL_COMPONENT = 1 << 1.// Function components
STATEFUL_COMPONENT = 1 << 2.// Stateful components
TEXT_CHILDREN = 1 << 3.// The child nodes are text elements
ARRAY_CHILDREN = 1 << 4.// Child nodes are list elements
SLOTS_CHILDREN = 1 << 5.// The child node is a slot
TELEPORT = 1 << 6./ / teleport components
SUSPENSE = 1 << 7./ / suspense components
COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8.// Can be kept alive components
COMPONENT_KEPT_ALIVE = 1 << 9.// The component that has been kept alive
COMPONENT = ShapeFlags.STATEFUL_COMPONENT | ShapeFlags.FUNCTIONAL_COMPONENT / / component
}
Copy the codeThe specific use of ShapeFlags will also be discussed later in combination with the specific code.
processElement
ProcessElement is used to processElement nodes. The logic is simple: if the old node does not exist, mount the new node directly. If both the old and new nodes exist, the patch operation is performed.
// /packages/runtime-core/src/renderer.ts
const processElement = (
n1: VNode | null,
n2: VNode,
container: RendererElement,
anchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
isSVG = isSVG || (n2.type as string) = = ='svg'
if (n1 == null) { // No old node, directly mount the new node
mountElement(
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else { // The patch operation is performed on both the old and new nodes
patchElement(
n1,
n2,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
}
}
Copy the codepatchElement
PatchElement updates the element’s child nodes, as well as its props, class, style, and so on
// /packages/runtime-core/src/renderer.ts
const patchElement = (
n1: VNode,
n2: VNode,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
constel = (n2.el = n1.el!) ;let { patchFlag, dynamicChildren, dirs } = n2;
// if n2 has no patchFlag, set it to FULL_PROPS
patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS;
const oldProps = n1.props || EMPTY_OBJ;
const newProps = n2.props || EMPTY_OBJ;
let vnodeHook: VNodeHook | undefined | null;
// Triggers the onVnodeBeforeUpdate hook for VNode
if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
invokeVNodeHook(vnodeHook, parentComponent, n2, n1);
}
// Triggers the beforeUpdate hook of the directive
if (dirs) {
invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate');
}
// When in development mode and hot update, do full diff
if (__DEV__ && isHmrUpdating) {
patchFlag = 0;
optimized = false;
dynamicChildren = null;
}
constareChildrenSVG = isSVG && n2.type ! = ='foreignObject';
if (dynamicChildren) {
// Target update, update only dynamic child nodespatchBlockChildren( n1.dynamicChildren! , dynamicChildren, el, parentComponent, parentSuspense, areChildrenSVG, slotScopeIds );if(__DEV__ && parentComponent && parentComponent.type.__hmrId) { traverseStaticChildren(n1, n2); }}else if(! optimized) {// No dynamic child node, do full diff
patchChildren(
n1,
n2,
el,
null,
parentComponent,
parentSuspense,
areChildrenSVG,
slotScopeIds,
false
);
}
// Patch node properties
if (patchFlag > 0) {
if (patchFlag & PatchFlags.FULL_PROPS) {
// FULL_PROPS means that the property contains the dynamically changing property key, i.e. the property name itself is dynamic, e.g. :[foo]="bar"
// Since the attribute name itself is dynamically indeterminate, the unique correspondence between the old and new attributes cannot be guaranteed, so new attributes need to be mounted and invalid old attributes unloaded
// Therefore, we can only do full diff for the old and new attributes to ensure the accuracy of attribute update
patchProps(
el,
n2,
oldProps,
newProps,
parentComponent,
parentSuspense,
isSVG
);
} else {
// Dynamic class binding
if (patchFlag & PatchFlags.CLASS) {
if(oldProps.class ! == newProps.class) { hostPatchProp(el,'class'.null, newProps.class, isSVG); }}// Dynamic style binding
if (patchFlag & PatchFlags.STYLE) {
hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG);
}
// PROPS represents general dynamic properties other than dynamic class and style, which are collected in dynamicProps during compilation
// At run time, just target the properties recorded in dynamicProps
if (patchFlag & PatchFlags.PROPS) {
// if the flag is present then dynamicProps must be non-null
constpropsToUpdate = n2.dynamicProps! ;for (let i = 0; i < propsToUpdate.length; i++) {
const key = propsToUpdate[i];
const prev = oldProps[key];
const next = newProps[key];
// #1471 force patch value
if(next ! == prev || key ==='value') {
hostPatchProp(
el,
key,
prev,
next,
isSVG,
n1.children asVNode[], parentComponent, parentSuspense, unmountChildren ); }}}}// Dynamic text node
if (patchFlag & PatchFlags.TEXT) {
if(n1.children ! == n2.children) { hostSetElementText(el, n2.childrenas string); }}}else if(! optimized && dynamicChildren ==null) {
// Do full diff when no optimization is done and there are no dynamic child nodes
patchProps(
el,
n2,
oldProps,
newProps,
parentComponent,
parentSuspense,
isSVG
);
}
if ((vnodeHook = newProps.onVnodeUpdated) || dirs) {
// Trigger lifecycle hook after patch rendering (trigger in nextTick)
queuePostRenderEffect(() = > {
vnodeHook && invokeVNodeHook(vnodeHook, parentComponent, n2, n1);
dirs && invokeDirectiveHook(n2, n1, parentComponent, 'updated'); }, parentSuspense); }};Copy the codeThe main processing flow of the whole function:
- Check whether the new VNode has dynamic child nodes. If yes, patch only the dynamic child nodes. If not, do the full diff
- If the patch flag exists, different patches are made for node attributes according to patchFlag
- When patchFlag is FULL_PROPS, the element contains a dynamic attribute key and needs to perform full props diff.
- If patchFlag is CLASS and the classes of the new and old nodes are inconsistent, the CLASS is patched.
- When patchFlag is set to STYLE, the STYLE will be updated.
- When patchFlag is PROPS, the element has dynamic PROPS or attrs, and the dynamic attributes of the new node are extracted and all keys in the attributes are traversed. When the new and old attributes are inconsistent, or the key needs to be forcibly updated, HostPatchProp is called to update the properties.
- When patchFlag is TEXT, it means that the child node of the element is TEXT. If the TEXT in the old and new nodes is inconsistent, hostSetElementText is called to update directly.
- When the patch does not exist, the optimization flag does not exist, and the dynamic child node does not exist, the props is diff in full
patchBlockChildren
<div>
<span class="title">This is article list</span>
<ul>
<li>First static Li</li>
<li v-for="article in article_list" :key="article.id"> {{ article.title }}</li>
</ul>
</div>
Copy the codeArticle_list
article_list = [{
id: 1.title: 'First article'
}]
Copy the codeWhen article_list changes, diff operation is required for all nodes, including span and the first LI, according to vue2 patch process. These two elements are static and cannot change. Therefore, in VUe3, dynamic child nodes (blocks) are extracted and only dynamic child nodes are updated to improve performance.
const result = {
type: Symbol(Fragment),
patchFlag: 64.children: [{type: 'span'.patchFlag: -1. }, {type: 'ul'.patchFlag: 0.children: [{type: 'li'.patchFlag: -1. }, {type: Symbol(Fragment),
children: [{type: 'li'.patchFlag: 1. }, {type: 'li'.patchFlag: 1. }]}],dynamicChildren: [{type: Symbol(Fragment),
patchFlag: 128.children: [{type: 'li'.patchFlag: 1. }, {type: 'li'.patchFlag: 1. }]}]}Copy the codeNote: dynamicChildren collects not only the direct dynamicChildren, but also the dynamic nodes in all the children
Let’s look at the implementation of patchBlockChildren:
// /packages/runtime-core/src/renderer.ts
const patchBlockChildren: PatchBlockChildrenFn = (oldChildren, newChildren, fallbackContainer, parentComponent, parentSuspense, isSVG, slotScopeIds) = > {
for (let i = 0; i < newChildren.length; i++) {
const oldVNode = oldChildren[i];
const newVNode = newChildren[i];
// In the process of patch, there are several cases that need to provide the real parent container of the node to accurately patch:
// 1. Fragment type: The Fragment is not a real container. Its children depend on the real parent container
// 2. The old and new vNodes are not of the same type: the replacement node depends on the real parent container
// 3. Component VNode or Teleport component VNode: Components can be anything, so a real parent container is required
constcontainer = oldVNode.el && (oldVNode.type === Fragment || ! isSameVNodeType(oldVNode, newVNode) || oldVNode.shapeFlag & (ShapeFlags.COMPONENT | ShapeFlags.TELEPORT)) ? hostParentNode(oldVNode.el)! : fallbackContainer; patch( oldVNode, newVNode, container,null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
true); }};Copy the codepatchChildren
We have introduced a variety of optimization of patch process before, but in any case, there will always be a scene where full Diff is needed. At this time, optimization of Diff algorithm is crucial to improve the performance of Vue3.
When we talked about the Diff algorithm of Vue2 before, key is one of the factors to judge whether it is the same type of node. It is also the same in Vue3. As the unique identifier of VNode, Vue3 divides node key into two types:
- A sequence of all unmarked child nodes for the key attribute
- Some or all of the sequences of children of the key attribute are marked
Let’s take a look at the implementation of patchChildren:
const patchChildren: PatchChildrenFn = (
n1,
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized = false
) = > {
const c1 = n1 && n1.children;
const prevShapeFlag = n1 ? n1.shapeFlag : 0;
const c2 = n2.children;
const { patchFlag, shapeFlag } = n2;
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
// All or part of the child node sequence of the key attribute is marked
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
return;
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// A sequence of all unmarked child nodes
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
return; }}// Children have three possibilities:
// 1. Text node
// 2. Array node
/ / 3. Empty
if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
// When the new child is a text child
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// If the old child node is an array, unmount the old child node
unmountChildren(c1 as VNode[], parentComponent, parentSuspense);
}
if(c2 ! == c1) {// Update the new text child node directly
hostSetElementText(container, c2 as string); }}else {
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// When the old child is an array
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// If the new child node is also an array, do the full diff
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else {
// If the new child node is empty, the old child node is unloaded directly
unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true); }}else {
// If the old child node is a text node, empty it
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
hostSetElementText(container, ' ');
}
// When the new child node is an array, mount it directly
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
mountChildren(
c2 asVNodeArrayChildren, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ); }}}};Copy the codepatchUnkeyedChildren
Diff of all the child nodes without the key attribute is very simple. Patch the child nodes in sequence and mount or uninstall the redundant nodes
const patchUnkeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
anchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
c1 = c1 || EMPTY_ARR;
c2 = c2 || EMPTY_ARR;
const oldLength = c1.length;
const newLength = c2.length;
const commonLength = Math.min(oldLength, newLength);
let i;
// Patch in sequence on the common part of the old and new child nodes
for (i = 0; i < commonLength; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]));
patch(
c1[i],
nextChild,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
}
if (oldLength > newLength) {
// If there are too many old child nodes, unload the redundant old child nodes
unmountChildren(
c1,
parentComponent,
parentSuspense,
true.false,
commonLength
);
} else {
// If there are too many new child nodes, mount the excess new child nodesmountChildren( c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, commonLength ); }};Copy the codepatchKeyedChildren
Now we finally get to the core part, Vue3 has a substantial improvement in the Diff algorithm, remember the Diff algorithm for Vue2? If you can’t remember, go back!
Vue3’s Diff algorithm consists of several parts: preprocessing, greedy algorithm + binary search and backtracking, and also introduces the concept of the longest increasing subsequence. Since the patchKeyedChildren function is quite large, we only focus on the code related to each part when explaining it.
pretreatment
- The comparison is traversed backwards from the head of the old and new child nodes (isSameVNodeType). If the nodes are of the same type, the patch operation is performed; if not, the traversal is terminated immediately
- The comparison is traversed from the end of the old and new child nodes in sequence (isSameVNodeType). If the nodes are of the same type, the patch operation is performed; if not, the traversal is terminated immediately
Let’s take a look at the relevant code:
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // The old child node tail index
let e2 = l2 - 1; // The new child node tail index
// Traverses from head to tail, terminating traversal after either of the old and new child nodes are traversed
// If a node of the same type (both type and key are equal) is encountered during traversal, patch operation is performed directly; otherwise, traversal is immediately skipped
// in this case, I records the index of the subsequence when the traversal is broken
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]));
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else {
break;
}
i++;
}
// Traversal from tail to head, traversal stops when either E1 or E2 encounters I
// If a node of the same type (both type and key are equal) is encountered during traversal, patch operation is performed directly; otherwise, traversal is immediately skipped
// At this point, E1 and E2 record the latest tail-index positions of the old and new child nodes
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]));
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else {
break;
}
e1--;
e2--;
}
// Ignore irrelevant code for now
};
Copy the codeLet’s take a closer look at the picture:
Preconditioning
Post pretreatment
End to end processing
When preprocessing before and after, it is possible to encounter old and new child nodes, such as I >e1 or I >e2, which means that there are old child nodes to be unmounted or new child nodes to be mounted. Let’s look at how the code handles this:
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // The old child node tail index
let e2 = l2 - 1; // The new child node tail index
// Preprocessing
// post preprocessing
// The pointer to the old child node collides. The pointer to the new child node does not collide
// nodes are new nodes that need to be mounted
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor;
while (i <= e2) {
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] asVNode) : normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ); i++; }}}// The Pointers of the old child node do not collide. The Pointers of the new child node collide
// nodes are redundant and need to be uninstalled
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true); i++; }}else {
// There are unknown sequences that need to be processed}};Copy the codeLongest increasing subsequence
After preprocessing, what is left is the unknown sequence of child nodes. So what do we do with these nodes? Let’s start with a new concept: longest increasing subsequence
A longest increasing subsequence is a subsequence that, within a given sequence of values, is found in such a way that the elements of the subsequence increase in value in such a way that the length of the subsequence is as large as possible. Elements in the longest increasing subsequence are not necessarily continuous in the original sequence.
const array = [10.9.2.5.3.7.101.18]
// The longest incrementing subsequence of array is [2, 5, 7, 101], [2, 5, 7, 18], [2, 3, 7, 101], and length is 4
Copy the codeSo how do you find the longest increasing subsequence in a sequence of numbers? Vue3 uses greedy algorithm + binary search
Greedy algorithm: also known as greedy algorithm, at each step of the selection, always choose the current best method.
Let’s look at an example:
The greedy algorithm rules are: if the current value is greater than the last digit of the selected result, it is directly added later, if the current value is smaller, it is directly replaced by the first value greater than it
Let’s break down the process:
- When initialized, place the first value of the array sequence, 10, into the result array, where result is **[10]**
- On the first pass, the second value of the numeric sequence is 9, which is smaller than the last value of result (10). As a rule, replace 10 with 9, and result is [9].
- On the second pass, the third value of the numeric sequence is 2, which is less than the last value of result (9). As a rule, replace 9 with 2, and result is [2].
- On the third pass, the fourth value of the sequence is 5, which is larger than the last value of result (2). As a rule, put result directly, and result is [2, 5].
- On the fourth pass, the fifth value of the numeric sequence is 3, which is smaller than the last value of result (5). As a rule, we need to replace the first value of result that is greater than it. Therefore, we need to replace 5 with 3, and result is [2, 3].
- On the fifth pass, the sixth value of the sequence is 7, which is larger than the last value of result (3). As a rule, we put result directly, where result is [2, 3, 7].
- On the sixth pass, the seventh value of the sequence is 101, which is larger than the last value of result (7). As a rule, we put result directly, which is [2, 3, 7, 101].
- On the seventh iteration, the eighth value of the numeric sequence is 18, which is smaller than the last value of result (101). As a rule, we need to replace the first value of result that is greater than it, so we need to replace 101 with 18, where result is [2, 3, 7, 18].
But the final result of this algorithm may not be what we want. Let’s take a look at an example:
Why is this a problem? That’s because in the process, we’re only looking for the best solution for each iteration, and we’re not thinking about the global best solution.
Next, we use Vue3 code to explain the Diff process and how it solves this problem.
As shown in the figure above, we can see that after the pretreatment of head and tail:
- I =2, e1=5, e2=5
- Node F needs to be unmounted, and node I needs to be mounted
For the new sequence of child nodes, create a Map that stores the key=>index relationship
In this step, the old Vnode can quickly match with the new vnode with the same key and patch
// There are unknown sequences that need to be processed
const s1 = i; // The old child sequence header pointer
const s2 = i; // New child node sequence header pointer
// Iterate over the new sequence of child nodes, and record the key=>index of the node
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map(a);for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]));
if(nextChild.key ! =null) {
// Ignore debug mode codekeyToNewIndexMap.set(nextChild.key, i); }}Copy the codeThe keyToNewIndexMap stores the following data:
D => 2
E => 3
C => 4
I => 5
Traverses the old child node sequence from the head, and determines whether the old VNode exists in the new child node sequence through the key. If yes, patch the node. If no, uninstall the node
let j;
let patched = 0; // Record the number of nodes that have been patched in the new sequence
const toBePatched = e2 - s2 + 1; // The total number of nodes that require patch in the new sequence
let moved = false; // Record whether the new VNode has moved relative to the old VNode
// When the old sequence pointer is advanced sequentially for the patch of the old and new nodes, the old node corresponds to the new node index is recorded
If the relative position of the new node corresponding to the two adjacent old nodes is unchanged, then newIndex
// It should be incremented; otherwise, if newIndex becomes smaller, it means that two adjacent old nodes are new
// The relative position of the node is changed, so there must be a node shift
let maxNewIndexSoFar = 0;
// Use an array to record the old node index
// Array records are used to create the longest incrementing subsequence, so that the nodes that need to be moved are placed in the correct position in the least number of times
// 0 indicates that the new node has no corresponding old node. To distinguish the old node index = 0 from 0 indicating that there is no corresponding node, the corresponding old node index is +1
const newIndexToOldIndexMap = new Array(toBePatched);
// Initialize the array with each child element being 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;
// Start traversing the old node
for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
if (patched >= toBePatched) {
// When old nodes locate new nodes, patch is executed and patched + 1 is enabled
// Patched >= toBePatched, new child node sequences have been patched
// Unmount the remaining old nodes
unmount(prevChild, parentComponent, parentSuspense, true);
continue;
}
let newIndex;
if(prevChild.key ! =null) {
// If the old node has a key, find the index of the new node with the same key
newIndex = keyToNewIndexMap.get(prevChild.key);
} else {
// If the old node has no key, find a similar new node in the new child node sequence without key (type equal).
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] asNode)) {newIndex = j;break; }}}if (newIndex === undefined) {
// if newIndex is undefined, the new node corresponding to the old node is not found. Uninstall the old node directly
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
// Add the index of the old node to the array containing the new node (+ 1)
newIndexToOldIndexMap[newIndex - s2] = i + 1;
// maxNewIndexSoFar Records the maximum index value of the new node corresponding to the current old node
// newIndex is incremented, indicating that the relative position of the new node corresponding to the adjacent old node does not change, so there is no need to move the node
// Once maxNewIndexSoFar becomes smaller, it indicates that the relative positions of adjacent nodes change, and the new sequence of child nodes must move
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
moved = true;
}
// patch old and new nodes
patch(
prevChild,
c2[newIndex] asNode, the container,null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
// patched Count +1patched++; }}Copy the codeAt this point, the corresponding relationship between the old and new index nodes stored in newIndexToOldIndexMap is:
- I is the new node, so it’s 0
- The F node was not found in the new child node sequence, so it was unloaded directly
- The index of C in the old sequence of child nodes is 2, and if you add 1, it becomes 3 (D, E are similar).
Mount the new node and move the other nodes to the correct position
In this section, Vue3 finds as many old index increasing nodes as possible in the NewindexTools IndexMap by using the longest increasing subsequence. Because we refer to the order between the old nodes to move the new node, we find the most inconvenient old nodes, so the new node needs to move the least times.
Let’s try to find the longest increasing subsequence of Newindex Tools IndexMap using the algorithm introduced earlier. Does something feel wrong? The result is [0, 3], which should be [4, 5] according to our assumption, because D and E are the two nodes whose positions have not changed.
Let’s look at the algorithm for the longest increasing subsequence:
function getSequence(arr: number[]) :number[] {
// When iterating through the ARR, each operation result pushes or replaces the value
// place the first item of the result index in p
// When we finally do a backtrace, we can find the previous item through the array p through the last item
const p = arr.slice();
const result = [0]; // An array of indexes that record the longest growing subsequence
/ * * * assumption is arr,4,5,3 [2], the p and,4,5,3 [2] * result is [0] * /
let i, j, u, v, c;
const len = arr.length;
for (i = 0; i < len; i++) {
const arrI = arr[i];
// 0 is a special placeholder, indicating that a new node is added and does not participate in calculation
if(arrI ! = =0) {
// j is the last item in the subsequence index. Compare the value of j in the original data arr with the current value arrI
// If arrI is large, set the value of arrI at the corresponding position in p to the last item in the result array
// The push item (index I) is stored in the corresponding position of p.
// And push the arrI index I to result
j = result[result.length - 1];
if (arr[j] < arrI) {
p[i] = j;
result.push(i);
continue;
}
u = 0;
v = result.length - 1;
// If arrI is small, find the first value in result that is greater than it by binary search and replace it
while (u < v) {
c = (u + v) >> 1;
if (arr[result[c]] < arrI) {
u = c + 1;
} else{ v = c; }}if (arrI < arr[result[u]]) {
if (u > 0) {
P [I] = j
p[i] = result[u - 1]; } result[u] = i; }}}/ * * * first traversal * p = result,4,5,3 [2] = [0] * second traversal * p = result,0,5,3 [2] = [0, 1] third traversal * * p = result,0,1,3 [2] = [0] P = [2,0,1,0] result = [0,3,2] */
u = result.length;
v = result[u - 1];
/** * u = 3, v = 2 */
// perform backtracking fixes
while (u-- > 0) {
result[u] = v;
// The last item records its previous item in p, so fetch the previous item and place it in result
v = p[v];
/** result = [0,3,2] v = 1 * second result = [0,1,2] v = 0 * third result = [0, 2] v = 2 */
}
return result;
}
Copy the codeIt is important to note here that getSequence takes an array of indexes of the longest increasing subsequence
The data of newIndexToOldIndexMap we obtained in the previous step is [4, 5, 3, 0]. We disassemble the process in steps:
Do first traversal 
Backtracking we correct by backtracking
We end up with the longest increasing subsequence index [0, 1]
Finally, let’s look at how to mount and move nodes using this index:
// Get the index of the longest increasing subsequence of newIndexToOldIndexMap
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR;
j = increasingNewIndexSequence.length - 1;
// The end of the new sequence is traversed forward to use the patched nodes as anchor points for DOM operations
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i;
const nextChild = c2[nextIndex] as VNode;
// Get the anchor point, using the DOM element of the next node as the anchor point, if it is already the last node, then
// Anchor points are external incoming anchor points
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor;
if (newIndexToOldIndexMap[i] === 0) {
// If the value of the index is 0, it indicates that the node is new and needs to be mounted
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else if (moved) {
// When to move a node:
// 1. Node sequence in reverse order (no longest stable subsequence)
// 2. The current new node index is different from the current stable sub-sequence index, indicating that the relative position of the node has changed
if (j < 0|| i ! == increasingNewIndexSequence[j]) {// Move the DOM of the new node with the anchor as the insertion position
move(nextChild, container, anchor, MoveType.REORDER);
} else {
The new node does not need to move, because the index in the longest stable subsequence represents
// The index corresponding to the new node has no relative position changej--; }}}Copy the codeFirst traversal
- NextIndex is 5, corresponding to node I
- Take H as the anchor point
- If newIndexToOldIndexMap[3] is 0, it indicates that I is a new node and needs to be mounted
Let’s do it the second time
- NextIndex is 4, corresponding to node C
- I as the anchor point
- I is 2, not in the index array [0, 1] of the oldest sequence, indicating the need to move
- With I as the anchor, it moves in front of I
The third and fourth pass
- The third and fourth iterations, where I is 1 and 0 respectively, are in the index array [0, 1] of the oldest sequence and do not need to be moved
conclusion
So far, the Diff algorithm of Vue3 virtual Dom has been sorted out. The whole logic is complicated, and it took me two days to sort it out. There will certainly be not thorough understanding of the place, but also hope that you leave a message to correct.