This is the third day of my participation in the August Text Challenge.More challenges in August
The principle of DIff algorithm is depth-first and peer traversal comparison, that is, if a node has child nodes, it will continue to recurse the node for comparison (depth-first), and traverse nodes of that level for comparison only when there are no child nodes on the node (peer traversal comparison). Diff algorithm aims to make minimal changes to the old node to achieve unity with the new node. The node is reused through key, and the operation of adding, deleting and modifying cannot be reused.
Source code analysis
updateChildren
// core/vdom/patch.js
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)
}
// The subscript starts traversing and moves the subscript bidirectionally at the end
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// //////////////////////////////
// Debug tests
let childEl =Array.from(parentElm.children).map(i= >i.innerText)
/////////////////////////////////
// Four ways to compare old and new nodes
// Check whether the sameVnode() method is the same node. Old nodes can be reused and their children need to be compared
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) { // Compare the old and new node headers
console.log('Comparing oldStartVnode, newStartVnode',oldStartVnode.key, newStartVnode.key)
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) { // Compare the old and new node tails
console.log('Comparing oldEndVnode, newEndVnode',oldEndVnode.key, newEndVnode.key)
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Compare the tail of the new node with the head of the old node
console.log('Comparing oldStartVnode, newEndVnode',oldStartVnode.key, newEndVnode.key)
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)) { // Compare the head of the new node with the tail of the old node
console.log('Comparing oldEndVnode, newStartVnode',oldEndVnode.key, newStartVnode.key)
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// None of the four methods are matched
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // Create a hash table for the nodes in the range of the left and right Pointers of the old node. Key corresponds to index
// Find the old node according to the new node's key.
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key] // If the new node has a key, find the index of the old node corresponding to the key
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // The new node does not have a key, traverses the old node, find the same node index as the new node
if (isUndef(idxInOld)) { // This node does not exist in the old node
console.log('Node created',newStartVnode.key)
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) // Create a node
} else { // The new node is found in the old node
vnodeToMove = oldCh[idxInOld]
// The key is the same, and the new node needs to be compared
if (sameVnode(vnodeToMove, newStartVnode)) { // Is the same node
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// Just the same key, but not the same node, as a new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
childEl =Array.from(parentElm.children).map(i= >i.innerText)
}
// Node traversal is complete
// Create the remaining nodes
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
// Remove the remaining nodes
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codesameVnode
This function explains the need for the key, which is undefined when not specified, and avoids using index as the key. Here’s why
Let’s say I have several list itemsliKey is not set or usedindex, then when comparing the old and new nodes, areundefinedEqual, both are equalindexIt’s going to be equal, then a.key === b.keyThis condition must be passed. All the other conditions areliTag, so it will also pass, so representssameVnodeConstant for thetrueSo inupdateChildrenAlways fired when comparing nodes in a functionsameVnode(oldStartVnode, newStartVnode), and then it keeps firingpatchVnodeFunction to constantly change the contents of the node. Each node will be changed, not to achieve the effect of the node translation multiplexing.
// core/vdom/patch.js
function sameVnode (a, b) {
return (
a.key === b.key && / / the same key
a.asyncFactory === b.asyncFactory && (
(
a.tag === b.tag && // Same tag
a.isComment === b.isComment && // All comments
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b) // Input tags have the same type
) || (
isTrue(a.isAsyncPlaceholder) &&
isUndef(b.asyncFactory.error)
)
)
)
}
Copy the codeFor example, the following nodes are compared in sequence without reuse
Old node: A B D New node: A C B ECopy the code
patchVnode
// core/vdom/patch.js
function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
/ /... Other code handling
// The new node has no text
if (isUndef(vnode.text)) {
// All have child nodes
if (isDef(oldCh) && isDef(ch)) {
// The child node is different, continue the recursion
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) { // The new node has child nodes, but the old node does not
if(process.env.NODE_ENV ! = ='production') {
checkDuplicateKeys(ch)
}
// The old node has text, empty the text, and add child nodes to replace the text
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) { // The new node does not have children, but the old node does
removeVnodes(oldCh, 0, oldCh.length - 1) // Remove child nodes from the old node
} else if (isDef(oldVnode.text)) { // There is no child node for either node, and the new node has no text
nodeOps.setTextContent(elm, ' ') // The old node clears the text}}else if(oldVnode.text ! == vnode.text) {// The text of the old and new nodes is different
nodeOps.setTextContent(elm, vnode.text) // Replace the text}}Copy the codeThe sample
The old and new nodes are given respectively to execute in a single step:
Old node: A B D New node: A C B ECopy the code- The first step is to compare nodes A
SameVnode (oldStartVnode, newStartVnode) is triggered. The old and new nodes have the same header pointer, and then the two header Pointers are compared
A B DCopy the code- Step 2 Create a new node C
If no identical node is found in the first four matching methods, the boundary of the node is determined. The same node may exist in the middle part from the first pointer to the last pointer. At this time, the corresponding node in the old node is obtained according to the key of the new node. C node does not exist, need to create, then new section nod pointer +1
A B C DCopy the code-
Step 3 Compare node B
Trigger the +1 nod pointer to old and new sections of sameVnode(oldStartVnode, newStartVnode)
A B C DCopy the code- Step 4 Create node E
This is the same process as creating the C node; The first four matching modes are not triggered, and the same key is not found in the old node. Create a new node C, then head pointer +1
A, B, E, DCopy the code- Step 5 Remove node D
As can be seen from the section nodding the tail pointer, the head pointer of the new node is larger than the tail pointer at this point, and it is necessary to break out of the while loop. In this case, there are redundant nodes in the old node, which need to be removed
Results: A C B ECopy the code
In the process output by the console, the graffiti part is generated when patchVnode recurses the child nodes of this node, which is not concerned
The articles
- [Vue source]–$nextTick and asynchronous rendering (line by line comments)
- [Vue source]–mixin and extend (line by line)
- [Vue source]–Diff algorithm (line by line comment)
- [Vue source]– How to listen for array changes (line by line comment)
- [Vue source]– Reactive (bidirectional binding) principle (line by line comment)
- [Vue source]– what is done for each lifecycle (line by line comments)
- [Vue source]– How to generate virtual DOM (line by line comment)