This is the third day of my participation in the August Text Challenge.More challenges in August
One, foreword
In the previous part, diff algorithm-node comparison was introduced, mainly involving the following points:
- Diff algorithm, comparison method and node reuse are introduced
- Diff algorithm of outer node is implemented
- How to replace and update different nodes
- How to reuse the same node update: text, element, style
This paper, diff algorithm – comparison optimization
Second, compare the son node
1. Review
In the previous part, two virtual nodes were constructed to simulate the effect of V-IF, and the reuse of outer nodes was realized through patch comparison
let vm1 = new Vue({
data() {
return { name: 'Brave'}}})let render1 = compileToFunction('<div style="color:blue">{{name}}</div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);
let vm2 = new Vue({
data() {
return { name: 'BraveWang'}}})let render2 = compileToFunction('<div style="color:red">{{name}}</div>');
let newVnode = render2.call(vm2);
setTimeout(() = > {
patch(oldVnode, newVnode);
}, 1000);
Copy the codeExecution Result:
Blue text when initialized
Updated to red text
Problem found: Only the style of the outer div was updated, but the name was not updated to BraveWang, that is, only the comparison and attribute update of the first layer node were made, and no deep diff comparison was carried outCopy the code2. How to compare son nodes
Take out the “new son node” and “old son node” and compare them one by one
//src/vdom/patch.js
/** * Insert the virtual node into the element after converting it into a real node@param {*} El the current real element id#app *@param {*} Vnode Virtual node *@returns New real element */
export function patch(oldVnode, vnode) {
const isRealElement = oldVnode.nodeType;
if(isRealElement){
// 1, create a real node based on the virtual node
const elm = createElm(vnode);
// 2, replace the old node with the real node
const parentNode = oldVnode.parentNode;
parentNode.insertBefore(elm, oldVnode.nextSibling);
parentNode.removeChild(oldVnode);
return elm;
}else{// diff: comparison between old and new virtual nodes
if(! isSameVnode(oldVnode, vnode)){return oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el);
}
let el = vnode.el = oldVnode.el;
if(! oldVnode.tag){if(oldVnode.text ! == vnode.text){return el.textContent = vnode.text;
}else{
return;
}
}
updateProperties(vnode, oldVnode.data);
// TODO:Compare son nodes...
let oldChildren = oldVnode.children || {};
letnewChildren = vnode.children || {}; }}Copy the code3. Several cases of new and old son nodes
- Situation 1: The old one has a son, the new one doesn’t
- Situation 2: The old has no son, the new has a son
- Situation 3: Both parents have sons
Situation 1: The old one has a son, the new one doesn’t
Solution: Simply delete the redundant old DOM elementsCopy the code// src/vdom/patch.js#patch.// Compare son nodes
let oldChildren = oldVnode.children || {};
let newChildren = vnode.children || {};
// Situation 1: The old has a son, the new has no son; Delete unnecessary old DOM elements.
if(oldChildren.length > 0 && newChildren.length == 0) {// Better handling: Since there may be components in the child nodes, encapsulate the removeChildNodes method and delete all the child nodes
el.innerHTML = ' ';// Write violence directly empty;
}
Copy the codeNote: The innerHTML is written with violence; Since the child nodes may contain components, it is better to encapsulate a removeChildNodes method that removes all the child nodes
Test method:
let vm1 = new Vue({
data() {
return { name: 'Brave'}}})let render1 = compileToFunction('<div style="color:blue">{{name}}</div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);
let vm2 = new Vue({
data() {
return { name: 'BraveWang'}}})let render2 = compileToFunction('<div style="color:red"></div>');
let newVnode = render2.call(vm2);
setTimeout(() = > {
patch(oldVnode, newVnode);
}, 1000);
Copy the codeSituation 2: The old has no son, the new has a son
Solution: Directly put the new child node into the corresponding old node.Copy the code//src/vdom/patch.js#patch.// Compare son nodes
let oldChildren = oldVnode.children || {};
let newChildren = vnode.children || {};
// Situation 1: The old has a son, the new has no son; Delete unnecessary old DOM elements.
if(oldChildren.length > 0 && newChildren.length == 0){
el.innerHTML = ' ';
// Situation 2: The old has no son, the new has a son; Add the new child node to the corresponding old node
}else if(oldChildren.length == 0 && newChildren.length > 0){
newChildren.forEach((child) = >{// Note that child is a virtual node and needs to become a real node
let childElm = createElm(child); // Create a real node based on the new virtual node
el.appendChild(childElm);// Put the generated real node into the DOM})}Copy the codeNote: Child in newChildren is a virtual node. Run createElm(child) to create a real node
Testing:
let vm1 = new Vue({
data() {
return { name: 'Brave'}}})let render1 = compileToFunction('<div style="color:blue"></div>');
let oldVnode = render1.call(vm1)
let el1 = createElm(oldVnode);
document.body.appendChild(el1);
let vm2 = new Vue({
data() {
return { name: 'BraveWang'}}})let render2 = compileToFunction('<div style="color:red">{{name}}</div>');
let newVnode = render2.call(vm2);
setTimeout(() = > {
patch(oldVnode, newVnode);
}, 1000);
Copy the codeSituation 3: Both parents have sons
Treatment method: DiFF comparison was performedCopy the code// src/vdom/patch.js#patch.// Compare son nodes
let oldChildren = oldVnode.children || {};
let newChildren = vnode.children || {};
// Situation 1: The old has a son, the new has no son; Just kill the old DOM element.
if(oldChildren.length > 0 && newChildren.length == 0){
el.innerHTML = ' ';
// Situation 2: The old has no son, the new has a son; Add the new child node to the corresponding old node
}else if(oldChildren.length == 0 && newChildren.length > 0){
newChildren.forEach((child) = >{
let childElm = createElm(child);
el.appendChild(childElm);
})
// Situation 3: Both parents have sons
}else{
// The core logic of diff comparison
updateChildren(el, oldChildren, newChildren);
}
Copy the codeThere’s a special treatment for the “old node has sons, new node has no sons” and “old node has no sons, new node has sons” and then, when both the old node and the new node have sons, we have to do a diff comparison; So, update Dren is the heart of the Diff algorithm
Three, the new old son diff comparison of the core logic updateChildren method
1. Introduction of diff comparison scheme between new and old sons
Continuing, when both the old node and the new node have sons, it is necessary to compare the old node with the new one
The comparison scheme of new and old virtual nodes is as follows: Use the dual-pointer method to compare the new and old virtual nodes in sequence
Each time the node comparison is completed, if the head node moves the pointer backward, the tail node moves the pointer forward;
The comparison is not completed until one side is traversed.
That is, “old head pointer and tail pointer overlap” or “new head pointer and tail pointer overlap”;
Here, in order to improve the performance of the DIff algorithm, the most performance-consuming “out-of-order comparison” is not directly used.
But combined with the daily use of the scene, priority is given to the special exception of four special cases: head, tail, head and tail
- Head to head comparison, move the head pointer backward;
- Comparing tail to tail, move the tail pointer forward;
- Head and tail comparison, the head pointer moves backward, the tail pointer moves forward;
- Comparing tail and tail, the tail pointer is moved backward and the head pointer is moved forward;
In each comparison, priority is given to comparison attempts of head, tail, head and tail. Out-of-order comparison is performed only when none of them hits
2. Several special cases of DIff comparison (head, tail, head, tail)
Note: Four cases need to be illustrated, a separate article: Article 31 - DIFF algorithm - Comparison optimization (ii)Copy the codeExcept for these four special cases, it’s out of order
Although it is out of order comparison, the goal is still to maximize node reuse and improve rendering performance.
Note: Out-of-order alignment how to reuse nodes, a separate article: 32 - Diff algorithm - out-of-order alignmentCopy the codeFour, the end
This paper, diff algorithm-comparison optimization (part 1), mainly involves the following points:
- How to compare son nodes is introduced.
- Three possible situations and code implementation of new and old son nodes;
- Diff scheme introduction and processing logic analysis when both old and new nodes have sons;
Diff Algorithm-Comparison Optimization (Part 2)