digression
The topic of this chapter is Update and diff, and this chapter will probably be more theoretical. Before starting this section, I thought it would be worth taking a look at the Vue and React implementation process: update->diff-> Patch ->updateDOM. After the update, the DIFF algorithm will be compared. After the comparison, a patch patch package will be generated, and then DOM will be updated according to this patch package. The patch package identifies the real DOM location by id (or serial number). After locating the DOM location, DOM updates in different situations according to the modified type (such as new node, deleted node, and modified node).
Summary of the diff
What is the diff? Diff is a comparison between two VNode trees, which in my current development phase is actually a comparison between a pre-updated VNode and a post-updated VNode (you can also directly compare the pre-updated DOM to the post-updated VNode), and a comparison between two trees in terms of data structures. The traditional DFS (depth-first traversal) algorithm has a time complexity of O(n2), because every node in tree 1 is compared to every node in tree 2. In our current scenario, that is, comparing two VNode trees, we need to select an optimal operation in addition to traversing the comparison, so the time complexity increases from O(n2) to O(n3), so the time complexity of a traditional diff process is O(n3).
Faced with such high complexity, diff algorithm emerges. React and Vue diff algorithms have a time complexity of O(n). The core of their diff algorithms can be summarized as follows:
- No cross-level comparisons (which is why we try to minimize cross-level operations)
- For different tag elements, their child elements must be different
- For the same tag element, only updates are made
- Children of the same level can be distinguished by keys
By analyzing the above four points, we can know that react and Vue diff algorithms are not optimal at the DOM level. However, they greatly reduce the time complexity by increasing some DOM overhead, and modify DOM performance in a reasonable way (mainly reflected in 1 and 2 points). To keep the time complexity as low as possible (O(n), just one pass).
The createElement method and cloneNode
Here is something that is irrelevant to the topic of this article, because I think of it. Performance optimization issues (also a common interview question) are often encountered in the first rendering of long lists (long, long ones). A common solution is to use Node.cloneNode instead of document.createElement. I don’t know if anyone is like me who initially thought node.clonenode was more efficient than document.createElement. In keeping with the principle of exploring uncharted territory, I deliberately tested:
const app = document.querySelector('#app');
console.time('create');
for(let i = 0; i < 1000000; i++) {
const newEl = document.createElement('div');
app.appendChild(newEl);
}
console.timeEnd('create');
/ / create: 3148.89501953125 ms
Copy the codeHere is a test for cloneNode:
const app = document.querySelector('#app');
console.time('clone');
const newEl = document.createElement('div');
app.appendChild(newEl);
for(let i = 0; i < 1000000 - 1; i++) {
// true indicates deep copy
const newEl_CP = newEl.cloneNode(true);
app.appendChild(newEl_CP);
}
console.timeEnd('clone');
/ / clone: 2832.31982421875 ms
Copy the codeIt can be seen that the time difference between the two nodes is not very big when rendering the same 1 million nodes. Now, if you look at this, you might wonder, in fact, the efficiency of the two methods is not much different, right? At the beginning, I also have the same doubts, and then carefully think about it, is there a problem on the train of thought? With clone, why do I want to do each one? Wouldn’t it be more efficient to clone in groups? Wouldn’t it be more efficient to clone the element with 1000 child nodes and then loop it 1000-1 times? To test this hypothesis, let’s use code:
const app = document.querySelector('#app');
console.time('newClone');
// Fragment is a document fragment that can add its children to the DOM tree without creating additional nodes
// Use Vue
tags and React Fragments to make sense
let fragment = document.createDocumentFragment();
for(let i = 0; i < 1000; i++) {
const newEl = document.createElement('div');
fragment.appendChild(newEl);
}
// Why do I need to copy it first?
// After inserting a fragment into the DOM tree, it can be interpreted as a transition process. All child elements of the fragment are moved into the DOM tree.
// So when app.appendChild(fragment) is called, the fragment is just an empty document fragment
const sourceFragment = fragment.cloneNode(true);
app.appendChild(fragment);
for(let i = 0; i < 1000 - 1; i++) {
const newEl_CP = sourceFragment.cloneNode(true);
app.appendChild(newEl_CP);
}
console.timeEnd('newClone');
/ / newClone: 945.964599609375 ms
Copy the codeAs you can see, using the Fragment +cloneNode approach can greatly reduce the process of producing DOM inserts. I think this is why cloneNode is better than createElement when dealing with long lists.
I implemented the diff algorithm
The DIFF algorithm I have implemented here is not that complicated, so I do not consider the corresponding processing of key for the time being (point 4). In addition, adhering to the simple and crude principle, MY DIff algorithm has directly modified DOM during the diff process, so there is no patch package.
First of all, remember that when I first rendered, this part of the DOM was actually implemented through the VNode and Element classes. So the core of our diff is execution around these two classes: VNodes are used to figure out what changes need to be made, and Element is used to perform those changes, with Element acting as an actor. With this part of the relationship sorted out, let’s go back to our original problem. We need an update method that Watcher can call when updating:
xm.$watcher = new Watcher((a)= > {
xm._callHook.call(xm, 'beforeUpdate');
const newVnodeTree = parseJsxObj(xm.$render());
The update method returns a new vnodeTree,
xm.$vnodeTree = update(xm, newVnodeTree, xm.$vnodeTree);
}, 'render');
Copy the codeTake a look at the update method, which simply calls diff and returns newVNode after processing
export const update = function(xm, newVNode, oldVNode) {
// Comparison of differences
diff(xm, newVNode, oldVNode);
// The newVNode returned here is processed during the diff process, adding the corresponding Element for each VNode
return newVNode;
}
Copy the codeNext is the process of diff. I feel that the following content may not be easy to understand, please read slowly:
/** * @param {Xue} xm Xue This * @param {VNode} newVNode new vnodeTree * @param {VNode} oldVNode old vnodeTree * @param {VNode} ParentVNode newVNode's parentVNode * @param {vnode} nextBroNode the next sibling of the current newVNode, mainly used in insertBefore scenarios */
export const diff = function(xm, newVNode, oldVNode, parentVNode, nextBroNode) {
// Define the type of change
let diffType = ' ';
// The old node does not exist
// Or the old node is null and the new node is not null
if(! oldVNode || (oldVNode.tag ===null&& newVNode.tag ! = =null)) {
// A node is added
diffType = 'addNode';
}
// The new node does not exist
// Or the new node is null and the old node is not null
else if(! newVNode || (oldVNode.tag ! = =null && newVNode.tag === null)) {
// A node is deleted
diffType = 'delNode';
}
// The node label is different
else if(oldVNode.tag ! == newVNode.tag) {// Replace the node
diffType = 'replaceNode';
}
// Replace the old text node with the new text node
else if(newVNode.tag === ' ') {
diffType = 'replaceText';
}
// Compare attributes and events
else {
diffType = 'updateAttrsAndEvents';
}
Call different handlers according to diffType
diffUpdateHandler(diffType, xm, newVNode, oldVNode, parentVNode, nextBroNode);
// Recursively process the child nodes, which is actually the process of comparing the same hierarchy
// In the case of conditional rendering, a null node must be returned if the current condition is falsy for proper processing
// Let VNode know that there is a null placeholder node that will not be rendered
for(let i = 0; i < newVNode.children.length; i++) {
// Next sibling node, in order to insert the new node into the correct position
const nextBroNode = (i === newVNode.children.length - 1)?null : oldVNode.children[i + 1];
// Cache the old node
let oldVNodeParam = oldVNode && oldVNode.children[i];
// For newly added or replaced nodes, their children are considered nonexistent in oldVNode and are inserted directly into the new node
// The child nodes corresponding to different nodes are different
if(diffType === 'addNode') oldVNodeParam = undefined;
/ / recursiondiff(xm, newVNode.children[i], oldVNodeParam, newVNode, nextBroNode); }}Copy the codeThe diffUpdateHandler logic is relatively simple: call different handlers based on different diffType values:
export const diffUpdateHandler = function(diffType, xm, newVNode, oldVNode, parentVNode, nextBroNode) {
switch(diffType) {
case 'addNode': diffAddNode(xm, newVNode, oldVNode, parentVNode, nextBroNode); break;
case 'delNode': diffDelNode(xm, newVNode, oldVNode, parentVNode); break;
case 'replaceNode': diffReplaceNode(xm, newVNode, oldVNode, parentVNode); break;
case 'replaceText': diffUpdateText(xm, newVNode, oldVNode, parentVNode); break;
case 'updateAttrsAndEvents': diffAttribute(xm, newVNode, oldVNode); diffEvent(xm, newVNode, oldVNode); break;
default: warn(`error diffType: ${ diffType }`); }}Copy the codeBefore we look at these handlers, let’s take a look at the improved Element class, which adds a number of methods to handle DOM updates:
class Element {
constructor(vnode, xm) {
this.xm = xm;
// If it is null, no processing is done
if(vnode.tag === null) return;
// Non-text node
if(vnode.tag ! = =' ') {
this.el = document.createElement(vnode.tag);
// Bind attributes
Object.entries(vnode.attrs).forEach(([key, value]) = > {
this.setAttribute(key, value);
});
// Bind events
Object.keys(vnode.events).forEach(key= > {
// Cache the function after bind for subsequent function removal
vnode.events[key] = vnode.events[key].bind(xm);
this.addEventListener(key, vnode.events[key]);
});
}
// Text node
else this.el = document.createTextNode(vnode.text);
}
// Add child nodes
appendChild(element) {
this.el && element.el && this.el.appendChild(element.el);
}
// Remove the child node
removeChild(element) {
this.el && element.el && this.el.removeChild(element.el);
}
// Add attributes for className and style
// class is a reserved word, style takes an object
setAttribute(name, value) {
if(name === 'className') {
this.el.setAttribute('class', value);
}
else if(name === 'style') {
Object.entries(value).forEach(([styleKey, styleValue]) = > {
this.el.style[styleKey] = styleValue; })}else {
this.el.setAttribute(name, value); }}// Add event listener
addEventListener(name, handler) {
this.el.addEventListener(name, handler);
}
// Remove event listening
removeEventListener(name, handler) {
this.el.removeEventListener(name, handler);
}
// Update the text content
updateTextContent(text) {
this.el.textContent = text;
}
// Replace the child node
replaceChild(newElement, oldElement) {
this.el.replaceChild(newElement.el, oldElement.el);
}
// Insert newElement before referenceElement with parent this.el
insertBefore(newElement, referenceElement) {
// insertBefore has another clever use: when the node to be inserted is already in the DOM tree, it is moved to the insertion position
// That is, the node does not need to be removed from its parent before attaching it to another node
// We can apply this feature to list items with key values
this.el.insertBefore(newElement.el, referenceElement && referenceElement.el); }}Copy the codeHaving looked at the Element class, let’s continue the process and look at each of these handlers one by one:
diffAddNode
// Add a node
export const diffAddNode = function(xm, newVNode, oldVNode, parentVNode, nextBroNode) {
// Create a new Element, and also create a DOM object
const newElement = new Element(newVNode, xm);
// Element corresponding to the parent vNode -- that is, the parent node to which newElement needs to be inserted
NextBroNode is the next sibling of newElement. When empty, nextBroNode is inserted directly to the end of the parent's child list
parentVNode.element.insertBefore(newElement, nextBroNode && nextBroNode.element);
The current newVNode specifies the new newElement
newVNode.addElement(newElement);
}
Copy the codediffDelNode
// Delete the old node
export const diffDelNode = function(xm, newVNode, oldVNode, parentVNode) {
// Call removeChild on the parent node to remove the current node
parentVNode.element.removeChild(oldVNode.element);
// The current newVNode specifies an empty Element placeholder object
newVNode.addElement(new Element(new VNode(null), xm));
}
Copy the codediffReplaceNode
// Replace the old node
export const diffReplaceNode = function(xm, newVNode, oldVNode, parentVNode) {
// Create a node
const newElement = new Element(newVNode, xm);
// Replace the old node with the new node
parentVNode.element.replaceChild(newElement, oldVNode.element);
// Specify element for newVNode
newVNode.addElement(newElement);
}
Copy the codediffUpdateText
// Compare text nodes
export const diffUpdateText = function(xm, newVNode, oldVNode, parentVNode) {
if(newVNode.text ! == oldVNode.text) {// No need to create a new text node when updating text, just use the old node
oldVNode.element.updateTextContent(newVNode.text);
}
// Specify element for newVNode
newVNode.addElement(oldVNode.element);
}
Copy the codediffAttribute
// Compare attributes
export const diffAttribute = function(xm, newVNode, oldVNode) {
// Use Set to create all attributes that need to be compared, combining the attributes of the old and new vNodes
const attrs = new Set(Object.keys(newVNode.attrs).concat(Object.keys(oldVNode.attrs)));
// Update attribute values for different attribute values
attrs.forEach(attr= >newVNode.attrs[attr] ! == oldVNode.attrs[attr] && oldVNode.element.setAttribute(attr, newVNode.attrs[attr]));// Specify element for newVNode
newVNode.addElement(oldVNode.element);
}
Copy the codediffEvent
// Compare events
export const diffEvent = function(xm, newVNode, oldVNode) {
// Get all the events you need to compare
const events = new Set(Object.keys(newVNode.events).concat(Object.keys(oldVNode.events)));
events.forEach(event= > {
// When the newVNode and oldVNode events are different
if(newVNode.events[event] ! == oldVNode.events[event]) {// Remove the old event response function
oldVNode.element.removeEventListener(event, oldVNode.events[event]);
// If the response function for the new event exists, add it
if(newVNode.events[event]) {
// Save the new handler after binding this
consthandler = newVNode.events[event] = newVNode.events[event].bind(xm); oldVNode.element.addEventListener(event, handler); }}});// Specify element for newVNode
newVNode.addElement(oldVNode.element);
}
Copy the codeThe demo test
Now that we’re done with the Update section, let’s write a demo to see how it looks so far
import Xue from './src/main';
new Xue({
root: '#app',
data() {
return {
test1: 'i am text1'.test2: {
a: 'i am text2 attr a'}}},methods: {
fn1() {
console.log(this)
console.log('i am fn1')
},
fn2() {
console.log(this)
console.log('i am fn2')
}
},
render() {
return (<div>
{ this.test1 }
<br />
{ this.test2.a }
<br />
{ this.test1 === 'i am text1' ?
'text1 === i am text1' :
'text1 === i am text1 change' }
<br />
{ this.test1 === 'i am text1' ?
null :
<div>i have been rendered when test1 ! == i am text1</div> }
{ this.test1 === 'i am text1' ?
<div>i have been rendered when test1 === i am text1 </div>:
null }
{ this.test1 === 'i am text1' ?
<a>i am a node when text1 === i am text1<span> i am inner</span></a> :
<span>i am a node when text1 === i am text1 change</span> }
<br />
{ this.test1 === 'i am text1' ?
<a>i am a node when text1 === i am text1</a> :
<span>i am a node when text1 === i am text1 change<span> i am inner</span></span> }
<br />
<div onClick={this.test= = ='i am text1' ? this.fn1 : this.fn2}
className={this.test= = ='i am text1' ? 'cls1' : 'cls2'}
id='id1'>
my attrs and events will be change
</div>
</div>);
},
beforeCreate() {
setTimeout((a)= > {
this.test1 = 'i am text1 change';
this.test2.a = 'i am text2 attr a change';
console.log('settimeout');
}, 3000);
setTimeout((a)= > {
this.test1 = 'i am text1';
this.test2.a = 'i am text2 attr a';
console.log('settimeout');
}, 5000)}});Copy the codeFirst apply colours to a drawing
The next chapter: componentization, stay tuned to…… Plus, maybe next week, for reasons you know in this business, it’s hard to top.
Github project address: Click here to jump to
Chapter 1: start from scratch, using the idea of Vue, develop a JS framework of their own (I) : the basic structure of the construction
Chapter two: starting from scratch, using the idea of Vue, the development of a own JS framework (two) : the first rendering
Chapter 4: starting from scratch, using the idea of Vue, develop a own JS framework (4) : componentization and routing components