Vue’s DiFF algorithm
preface
We know that Vue uses virtual DOM to reduce the operation times of real DOM, so as to improve the efficiency of page operation. Today we’ll look at how Vue updates the DOM when the page’s data changes. Vue and React use the same algorithm when updating the DOM, which is based on snabbDOM. When the data on the page changes, Vue does not render immediately. Instead, diff algorithm is used to determine which ones do not need to be changed and which ones need to be changed and updated. Only those DOM that need to be updated can be updated. In this way, many unnecessary DOM operations are reduced and performance is greatly improved. Vue uses such an abstract node, VNode, which is a layer of abstraction from the real DOM and does not depend on a certain platform. It can be the browser platform or WEEX, and even the Node platform can also create, delete, modify and other operations on such an abstract DOM tree, which also provides the possibility of front and back end isomorphism.
Vue Updates the view
We know that in Vue 1.x, each data corresponds to a Watcher; In Vue 2.x, a component corresponds to a Watcher, so that when our data changes, The set function triggers Dep’s notify function to notify Watcher to execute the vm._update(vm._render(), hydrating) method to update the view. Let’s take a look at the _update method
Vue.prototype._update = function (vnode: VNode, hydrating? : boolean) {
const vm: Component = this
const prevEl = vm.$el
const prevVnode = vm._vnode
const restoreActiveInstance = setActiveInstance(vm)
vm._vnode = vnode
// Vue.prototype.__patch__ is injected in entry points
// based on the rendering backend used.
/* Back end rendering vue.prototype. __patch__ is used as an entry */
if(! prevVnode) {// initial render
vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)}else {
// updates
vm.$el = vm.__patch__(prevVnode, vnode)
}
restoreActiveInstance()
// update __vue__ reference
/* Update the new instance object's __vue__*/
if (prevEl) {
prevEl.__vue__ = null
}
if (vm.$el) {
vm.$el.__vue__ = vm
}
// if parent is an HOC, update its $el as well
if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
vm.$parent.$el = vm.$el
}
// updated hook is called by the scheduler to ensure that children are
// updated in a parent's updated hook.
}
Copy the codeObviously, we can see that the _update method will patch the old Vnode with the incoming Vnode. Now let’s look at what happens in patch.
patch
The patch function compares the old and new nodes and determines which nodes need to be changed. You can only change these nodes to update the DOM efficiently. Let’s take a look at the code first
return function patch (oldVnode, vnode, hydrating, removeOnly) {
/* Vnode does not exist
if (isUndef(vnode)) {
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
/*oldVnode does not exist, create a new node */
if (isUndef(oldVnode)) {
// empty mount (likely as component), create new root element
isInitialPatch = true
createElm(vnode, insertedVnodeQueue)
} else {
/* Indicates whether the old VNode has nodeType*/
const isRealElement = isDef(oldVnode.nodeType)
if(! isRealElement && sameVnode(oldVnode, vnode)) {// patch existing root node
/* Modify the existing node */ when it is the same node
patchVnode(oldVnode, vnode, insertedVnodeQueue, null.null, removeOnly)
} else {
if (isRealElement) {
// mounting to a real element
// check if this is server-rendered content and if we can perform
// a successful hydration.
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
/* If the old VNode is a rendered element on the server, hydrating is true*/
oldVnode.removeAttribute(SSR_ATTR)
hydrating = true
}
if (isTrue(hydrating)) {
/* Need to merge into the real Dom */
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
/* Call insert hook */
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.')}}// either not server-rendered, or hydration failed.
// create an empty node and replace it
/* If not server-side rendering or merging into the real Dom fails, create an empty VNode to replace it */
oldVnode = emptyNodeAt(oldVnode)
}
// replacing existing element
/* Replace existing element */
const oldElm = oldVnode.elm
const parentElm = nodeOps.parentNode(oldElm)
// create new node
createElm(
vnode,
insertedVnodeQueue,
// extremely rare edge case: do not insert if old element is in a
// leaving transition. Only happens when combining transition +
// keep-alive + HOCs. (#4590)
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
// update parent placeholder node element, recursively
if (isDef(vnode.parent)) {
/* The root node of the component is replaced and the parent node element*/ is iterated
let ancestor = vnode.parent
const patchable = isPatchable(vnode)
while (ancestor) {
for (let i = 0; i < cbs.destroy.length; ++i) {
cbs.destroy[i](ancestor)
}
ancestor.elm = vnode.elm
if (patchable) {
/* Call the create callback */
for (let i = 0; i < cbs.create.length; ++i) {
cbs.create[i](emptyNode, ancestor)
}
/ / # 6513
// invoke insert hooks that may have been merged by create hooks.
// e.g. for directives that uses the "inserted" hook.
const insert = ancestor.data.hook.insert
if (insert.merged) {
// start at index 1 to avoid re-invoking component mounted hook
for (let i = 1; i < insert.fns.length; i++) {
insert.fns[i]()
}
}
} else {
registerRef(ancestor)
}
ancestor = ancestor.parent
}
}
// destroy old node
if (isDef(parentElm)) {
/* Remove the old node */
removeVnodes([oldVnode], 0.0)}else if (isDef(oldVnode.tag)) {
/* Call the destroy hook */
invokeDestroyHook(oldVnode)
}
}
}
/* Call insert hook */
invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
return vnode.elm
}
Copy the code
Vue’s Diff algorithm compares nodes of the same layer, so its time complexity is only O(n), and its algorithm is very efficient. We can also see from the code that sameVnode will be used in patch to determine whether the old node and the new node are the same node. If so, further patchVnode will be carried out; otherwise, a new DOM will be created and the old DOM will be removed.
sameVnode
Now let’s look at how sameVnode determines that two nodes are the same.
/* To determine whether two vnodes are the same, the following conditions must be met: same key, same tag (the name of the tag of the current node), same isComment (whether it is a comment node), same data (the object corresponding to the current node, contains specific data information, is a VNodeData type, When the tag is , the type must be the same */
function sameVnode (a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
a.asyncFactory === b.asyncFactory &&
isUndef(b.asyncFactory.error)
)
)
)
}
// Some browsers do not support dynamically changing type for <input>
// so they need to be treated as different nodes
Some browsers do not support dynamically changing types, so they are treated as different types */
function sameInputType (a, b) {
if(a.tag ! = ='input') return true
let i
const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}
Copy the codeSameVnode determines whether two nodes are the same by comparing the key, tag, annotation Node and data information of two nodes, and makes a separate judgment on the input tag to be compatible with different browsers.
patchVnode
// The diff algorithm compares nodes
function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
/* If two vnodes are the same, return */
if (oldVnode === vnode) {
return
}
if (isDef(vnode.elm) && isDef(ownerArray)) {
// clone reused vnode
vnode = ownerArray[index] = cloneVNode(vnode)
}
const elm = vnode.elm = oldVnode.elm
if (isTrue(oldVnode.isAsyncPlaceholder)) {
if (isDef(vnode.asyncFactory.resolved)) {
hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
} else {
vnode.isAsyncPlaceholder = true
}
return
}
// reuse element for static trees.
// note we only do this if the vnode is cloned -
// if the new node is not cloned it means the render functions have been
// reset by the hot-reload-api and we need to do a proper re-render.
/* If the new VNode is static and its key is the same, and the new VNode is clone or marked once, then replace elm and componentInstance. * /
if (isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
) {
vnode.componentInstance = oldVnode.componentInstance
return
}
// Implement some component hooks
/* If data.hook. Prepatch exists, execute */ first
let i
const data = vnode.data
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
/* I = data.hook. Prepatch, if present, see "./ creation-component componentVNodeHooks". * /
i(oldVnode, vnode)
}
// Check whether the new and old nodes have children
const oldCh = oldVnode.children
const ch = vnode.children
// Attribute update
if (isDef(data) && isPatchable(vnode)) {
[attrFn, classFn,...]
/* Call the update callback and update hook */
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)
}
// Determine whether the element is an element
if (isUndef(vnode.text)) { /* if the VNode has no text */
// Both have children
if (isDef(oldCh) && isDef(ch)) {
/* If both the old and new nodes have children, diff the children nodes and call updateChildren*/
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) {
/* If the old node has no children and the new node has children, clean the elm text and add children */ to the current node
if(process.env.NODE_ENV ! = ='production') {
checkDuplicateKeys(ch)
}
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) {
/* If the new node has no children and the old node has children, remove all ele children */
removeVnodes(oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) {
/* If the new node does not exist, the text */ will be removed
nodeOps.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {/* If the new node is different from the old node, replace the text */
nodeOps.setTextContent(elm, vnode.text)
}
/* Call the Postpatch hook
if (isDef(data)) {
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}
Copy the codeThe process of patchVnode is as follows:
- If oldVnode and Vnode are the same object, then it will return directly and no update is required
- If both the old and new VNodes are static and have the same key (representing the same node), and the new VNode is clone or marked once (marking the V-once property and only rendering once), then just replace Elm and componentInstance.
- If vnode.text is not a text node, and both the new and old nodes have children nodes, and the children nodes of the new and old nodes are different, diff is performed on the child nodes and updateChildren is called, which is also the core of diff.
- If the old node has no children and the new node has children, clear the text of the DOM of the old node first, and then add children to the current DOM node
- When the new node has no children and the old node has children, all children of that DOM node are removed.
- When the old and new nodes have no child nodes, only text replacement.
updateChildren
The DOM of our page is a tree structure. The patchVnode method mentioned above is to reuse the same DOM element. However, if the old VNnode object and the new VNnode object both have child elements, how should we compare the reused elements? So that’s what our updateChild dren method does
/* diff core method, compare optimization */
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
let oldKeyToIdx, idxInOld, vnodeToMove, refElm
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
constcanMove = ! removeOnlyif(process.env.NODE_ENV ! = ='production') {
checkDuplicateKeys(newCh)
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
/* Move to the right */
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
/* Close to the left */
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
/* In the first four cases, when the key is specified, the VNode is determined to be the same. Then, direct patchVnode is used to compare the two nodes of oldCh and newCh. 2*2=4 cases */
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
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)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
/* Create a hash table where the key corresponds to the old VNode key (this is only generated when undefined first time). For example, childre looks like this: [{xx: xx, key: 'key0'}, {xx: Xx, key: 'key1'}, {xx: xx, key: 'key2'}] beginIdx = 0 endIdx = 2 Result {key0:0, key1:1, key2:2} */
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
NewStartVnode Returns the idxInOld of the new VNode if the new VNode has a key and the key can be found in oldVnode */
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
/*newStartVnode does not have a key or the key is not found in the old node to create a new node */
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
/* Get the old node with the same key */
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
/* Run patchVnode*/ if the new VNode is the same as the obtained VNode with the same key
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
/* If there is a new node with the same key as the patchVnode, it will indicate that there is a duplicate key*/
oldCh[idxInOld] = undefined
/* canMove can be inserted directly in front of oldStartVnode */
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// same key but different element. treat as new element
/* Create a new VNode if the new VNode is not a sameVNode with the same key as the VNode found (e.g. with a different tag or input tag of a different type) */
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
OldStartIdx > oldEndIdx = oldStartIdx > oldEndIdx = oldStartIdx > oldEndIdx = oldStartIdx > oldEndIdx = oldStartIdx > oldEndIdx = oldStartIdx > oldEndIdx
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
NewStartIdx > newEndIdx = newStartIdx > newEndIdx = newStartIdx > newEndIdx = newStartIdx > newEndIdx
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codeThe following is a copy of other bloggers’ articles, feel good to write the original address: github.com/liutao/vue2…
At first glance, this piece of code can seem a little confusing. The specific content is actually not complicated, let’s first take a general look at the whole judgment process, and then through a few examples to go through the details.
OldStartIdx, newStartIdx, oldEndIdx, newEndIdx are all Pointers, and I’m sure you know what each one is, and we’re going to move the Pointers all the way through the comparison process.
OldStartVnode, newStartVnode, oldEndVnode, newEndVnode correspond to the VNode they point to.
The while loop stops at the end of the oldCh or newCh traversal, otherwise the loop continues. The whole process is divided into the following situations:
If oldStartVnode is not defined, the starting pointer for the oldCh array traversal is moved back one bit.
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
}
Copy the codeNote: In the seventh case, the value of the same key may be undefined
If oldEndVnode is not defined, the starting pointer for the oldCh array traversal is moved forward one bit.
else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
}
Copy the codeNote: In the seventh case, the value of the same key may be undefined
SameVnode (oldStartVnode, newStartVnode), which determines whether the objects pointed to by the two array start Pointers can be reused. If true, the patchVnode method is called to reuse the DOM elements and recursively compare the child elements, and then the start Pointers of oldCh and newCh are moved one bit back, respectively.
else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
Copy the codeSameVnode (oldEndVnode, newEndVnode), which determines whether the objects pointed to by the two array end Pointers can be reuse. If true, the patchVnode method is called to reuse the DOM elements and recursively compare the child elements, and then the end Pointers of oldCh and newCh are moved one bit forward, respectively.
else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
Copy the code5. SameVnode (oldStartVnode, newEndVnode), which determines whether the objects pointed to by oldCh start pointer and newCh end pointer can be reused. If true, the patchVnode method is called to reuse the DOM element and recursively compare the child elements. Since the reused element is the end element in newCh, it is inserted before oldEndVNode.elm. Finally, the start pointer of oldCh is moved back one bit, and the start pointer of newCh is moved forward one bit respectively.
else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
Copy the code6. SameVnode (oldEndVnode, newStartVnode), which determines whether the object pointed to by oldCh end pointer and newCh start pointer can be reused. If true, the patchVnode method is called to reuse the DOM element and recursively compare the child elements. Since the reused element is the starting element in newCh, it is inserted before oldStartVNode.elm. Finally, the end pointer of oldCh is moved forward one bit, and the start pointer of newCh is moved back one bit.
else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
Copy the codeIf the above six situations are not satisfied, then go here. All of the previous comparisons have been head-to-tail comparisons, but here, it’s a little more complicated, and it’s really all about duplicating elements based on key values.
(1) Iterate over the oldCh array, find the object with key, and generate a new object oldKeyToIdx with key as key and index value as value.
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
function createKeyToOldIdx (children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
Copy the code② Query whether newStartVnode has a key value and oldKeyToIdx has the same key.
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : null
Copy the codeIf newStartVnode does not have the same key or oldKeyToIdx does not have the same key, then the createElm method is called to create a new element, and the starting index of newCh is moved back one bit.
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
}
Copy the codeIf sameVnode(elmToMove, newStartVnode) returns true, it can be reused. In this case, call patchVnode to reuse dom elements and recursively compare sub-elements. Reset oldCh to undefined relative to the element in oldstartVNode.elm, and then insert the current element in front of oldStartVNode.elm, moving newCh’s starting index one bit back. If sameVnode(elmToMove, newStartVnode) returns false, such as a different tag name, then the createElm method is called to create a new element, with the start index of newCh moved back one bit.
elmToMove = oldCh[idxInOld]
if (sameVnode(elmToMove, newStartVnode)) {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
}
Copy the codeReference article:
- Pull hook education
- VirtualDOM and Diff (Vue implementation)
- Patch, the diff