Virtual DOM
DOM manipulation is very performance expensive, and when manipulating the DOM, Reflow and Repaint the DOM and re-render the DOM, as you can see in my previous article —- browser rendering process
Vue and React are data-driven views that only add, delete, or modify data. How does the framework control DOM manipulation?
React and VUE use virtual DOM (VDOM) to solve this problem. The main principle is as follows: Use JS to simulate DOM structure, transfer DOM calculation to JS calculation, use diff algorithm to calculate the smallest changes, and then operate DOM based on the changes to reduce computation.
For example: using javascript objects to represent HTML tree structures:
Below we through snabbDOM this VDOM library source code to learn vDOM and DIFF algorithm, Vue is a reference to its implementation of VDOM and DIFF
First look at the official example
import {
init,
classModule,
propsModule,
styleModule,
eventListenersModule,
h,
} from "snabbdom";
const patch = init([
// Init patch function with chosen modules
classModule, // makes it easy to toggle classes
propsModule, // for setting properties on DOM elements
styleModule, // handles styling on elements with support for animations
eventListenersModule, // attaches event listeners
]);
const container = document.getElementById("container");
const vnode = h("div#container.two.classes", { on: { click: someFn } }, [
h("span", { style: { fontWeight: "bold"}},"This is bold"),
" and this is just normal text",
h("a", { props: { href: "/foo"}},"I'll take you places!"),]);// Patch into empty DOM element -- This modifies the DOM as a side effect
patch(container, vnode);
const newVnode = h(
"div#container.two.classes",
{ on: { click: anotherEventHandler } },
[
h(
"span",
{ style: { fontWeight: "normal".fontStyle: "italic"}},"This is now italic type"
),
" and this is still just normal text",
h("a", { props: { href: "/bar"}},"I'll take you places!"),]);// Second ` patch ` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
Copy the code
There are two key functions:
h
The function returns a vNode, which is a virtual DOM structure represented by a JS object. acceptsel
(selector),data
(JS description of DOM),children
(The child vNode element of the virtual DOM)patch
The vNode () function is used to render the VNode as a real DOM and mount it to the page, and to re-render the DOM using the diff algorithm to compare the differences between the two VNodes.
The vNode structure is as follows:
Conclusion:
- DOM manipulation is very performance-intensive because of redrawing by reflux
- Vue and React are data-driven views. They use JS to simulate the DOM structure (VNode) and transfer DOM calculation to JS calculation. Diff algorithm is used to compare the old and new VNodes to calculate the smallest changes.
- Snabbdom in the library
h
The function generates a vnode,patch
Function to render the DOM and update the DOM using the diff algorithm
The diff algorithm
An overview of the
The process of comparing the diff of two old and new VNodes is mainly done inpatch
Delta function,
If two trees are normally compared, first, tree1 is traversed. Second, traverse tree2; Third, sort, three times, so the time of the tree diff is O (n^3). Let’s say there are 1000 DOM nodes, 100 million computations, and the algorithm is not available
The diff algorithm in the framework is optimized as follows:
- Compare only the same level, not across levels
- If the tag is not the same, delete it and rebuild it. (If the tag is not the same, but the child elements under the tag are the same, we will delete it as long as the tag is not the same, because the complexity of depth comparison is too high.)
- If the tag and key are the same, they are considered the same node and are not compared in depth
Optimization time complexity to O (n)
Next, read the core functions of the source code to understand the general flow of diff
Generate vnode
The h function in the h.ts file is used to generate vNode, let’s take a look at the source code
//h.ts.export function h (sel: any, b? :any, c? :any) :VNode {
var data: VNodeData = {}, children: any.text: any.i: number; .// Ignore details
/ / return vnode
return vnode(sel, data, children, text, undefined);
};
export default h;
Copy the code
Then look at the vnode function:
export function vnode (sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined) :VNode {
let key = data === undefined ? undefined : data.key;
// Returns the virtual DOM of a JS object structure
return { sel, data, children, text, elm, key };
}
Copy the code
- Returns a virtual DOM (vNode) of the JS object structure.
children
和text
Can’t coexist, either in plain text or child elementselm
This is the DOM element that vNode corresponds tokey
Is equivalent tov-for
The inside of thekey
We use itv-for
You need to add them manually
patch
function
The patch function is returned by init (snabbdom.ts)
The analysis is as follows:
return function patch (oldVnode: VNode | Element, vnode: VNode) :VNode {
let i: number.elm: Node, parent: Node;
constinsertedVnodeQueue: VNodeQueue = []; .// The first argument is not vnode
if(! isVnode(oldVnode)) {// Create an empty vNode associated with the DOM element
oldVnode = emptyNodeAt(oldVnode);
}
// Same vnode (key and SEL are equal)
if (sameVnode(oldVnode, vnode)) {
/ / vnode contrast
patchVnode(oldVnode, vnode, insertedVnodeQueue);
// Different vnodes, delete directly rebuild
} else{ elm = oldVnode.elm! ; parent = api.parentNode(elm);/ / reconstruction
createElm(vnode, insertedVnodeQueue);
if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}...// Don't look at the rest of the code
return vnode;
};
Copy the code
- If it is the same vnode (check method is
key
和sel
All equal), executepatchvNode
Delta function, and let’s go ahead and compare - Different Vnodes, delete directly rebuild
SameVnode has the following functions:
function sameVnode (vnode1: VNode, vnode2: VNode) :boolean {
// Key and sel are equal
// undefined === undefined // true
return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}
Copy the code
If there is no key (not v-for), then compare the sel selectors of two vnodes to determine whether they are the sameVnode. If there is a key, compare the sel and key together
Conclusion:
- First execution
patch
,patch(container, vnode);
Create an empty VNode, associate the dom passed in, make both parameters passed in vNodes, and then execute the following logic - If the vNodes have the same tag (SEL) and key, the vNodes are considered to be the same. perform
patchVnode
Methods. - If the tag (SEL) is different for different VNodes, delete the tag and rebuild it without further comparison
patchVnode
function
In the patch function above, if the two VNodes are the same, the patchVnode method is executed to compare the vNodes.
The process of patchVnode is as follows
function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
// Set vnode.elem, the new vNode may not have elm, so assign the old one to it to know which real DOM element needs to be updated
constelm = vnode.elm = oldVnode.elm! ;/ / the old children
let oldCh = oldVnode.children as VNode[];
/ / new children
let ch = vnode.children as VNode[];
if (oldVnode === vnode) return;
// vnode.text === undefined (vnode.children)
if (isUndef(vnode.text)) {
// There are children in both old and new
if (isDef(oldCh) && isDef(ch)) {
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);// New children have, old children do not (old text has)
} else if (isDef(ch)) {
/ / clear the text
if (isDef(oldVnode.text)) api.setTextContent(elm, ' ');
/ / add the children
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
// Old child does, new child does not
} else if (isDef(oldCh)) {
/ / remove the children
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
/ / the old text
} else if (isDef(oldVnode.text)) {
api.setTextContent(elm, ' ');
}
// else : vnode.text ! == undefined (vnode.children have no value)
} else if(oldVnode.text ! == vnode.text) {// Remove old children
if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
}
// Set the new text
api.setTextContent(elm, vnode.text!);
}
}
Copy the code
Conclusion:
- If the new VNode has one
children
, there is notext
(vnode.text === undefined
(text
和children
Cannot coexist)) :- If there are both old and new VNodes
children
, the callupdateChildren()
Method, and then continue to update - If the new
children
Yes, the oldchildren
If no, calladdVnodes()
Method, put the newchildren
Added to theelm
On, - If the new
children
No, the oldchildren
If yes, callremoveVnodes()
Method to remove the old vNodechildren
- There’s only one thing left. Old and new
children
, old VNodes havetext
The new VNode does nottext
Then take itelm
的text
Set to null
- If there are both old and new VNodes
- If the new VNode does not
children
onlytext
, (vnode.text ! == undefined
(vnode.children
No value), and old and newtext
Not the same (oldVnode.text ! == vnode.text
) to remove the old vNodechildren
To replace with that of the new VNodetext
If both vNodes have children, the updateChildren() method needs to be called. The update method is more complicated. The rest of the vNodes simply call the DOM API to add and remove DOM elements. Now let’s talk about the update dren() method
updateChildren
function
Update Dren is complex, so you can just understand the process. Passed the element elm, old children, new chlidren
The caption above represents vNodekey
It is a combination of tag (SEL) and vNode.
The process is shown above
Principle:
- In view of the old and new
ch
Let’s define four indexes,oldStartIdx
,oldEndIdx
,newStartIdx
,newEndIdx
In the loop, IDX will accumulate or decrease, startIdx will accumulate, endIdx will decrease, in the process, the Pointers will slowly move towards the middle, when the Pointers overlap, indicating that the traversal is finished, the loop is finished.
The specific comparison process in each cycle is:
- Execute if one of the following four conditions is the same: start vs. start, end vs. end, or end vs. start
patchVnode()
Function, performs a recursive comparison, and the pointer accumulates or decays and moves to the middle. In the next cycle, the pointer points to the next onechildren
- If none of the above four cases are present, the new node will be taken first
key
Can be corresponding to a node in oldChkey
。- If it doesn’t match, the node is new, just insert it somewhere new.
- If it does, you have to judge
sel
Is it equal, ifsel
It’s not equal, so it still doesn’t match, which means that the node is new, so I’ll insert a new node somewhere. - if
sel
Equal,key
Equal, then continue to execute on the same two nodespatchVnode
Method, recursive comparison.
function updateChildren (parentElm:Node.oldCh:VNode[].newCh:VNode[].insertedVnodeQueue:VNodeQueue){
let oldStartIdx = 0, newStartIdx =0;letOldEndIdx = oldCh. length -1;let oldStartVnode = oldCh[0];letOldEndVnode = oldCh [oldEndIdx];letNewEndIdx = newCh. length -1;let newStartVnode = newCh[0];letNewEndVnode = newCh [newEndIdx];letOldKeyToIdx: KeyToIndexMap |undefined;letIdxInOld:number;letElmToMove: VNode;letBefore:any;while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if(oldStartVnode = =null) {oldStartVnode = oldCh[++oldStartIdx];// Vnode might have been moved left
} else if(oldEndVnode = =null) {oldEndVnode = oldCh[--oldEndIdx]; }else if(newStartVnode = =null) {newStartVnode = newCh[++newStartIdx]; }else if(newEndVnode = =null) {newEndVnode = newCh[--newEndIdx];// Start vs. start
} else if(sameVnode (oldStartVnode, newStartVnode)) {patchVnode (oldStartVnode, newStartVnode, insertedVnodeQueue); OldStartVnode = oldCh [+ + oldStartIdx]; NewStartVnode = newCh [+ + newStartIdx];// End and end comparisons
} else ifPatchVnode (oldEndVnode, newEndVnode) {patchVnode (oldEndVnode, newEndVnode, insertedVnodeQueue); OldEndVnode = oldCh [-- oldEndIdx]; NewEndVnode = newCh [-- newEndIdx];// Start and end comparisons
} else if(sameVnode (oldStartVnode, newEndVnode)) {// Vnode moved rightPatchVnode (oldStartVnode, newEndVnode, insertedVnodeQueue); API. InsertBefore (parentElm, oldStartVnode. elm! , the API. NextSibling (oldEndVnode. Elm!) ); OldStartVnode = oldCh [+ + oldStartIdx]; NewEndVnode = newCh [-- newEndIdx];// Compare the end and the beginning
} else if(sameVnode (oldEndVnode, newStartVnode)) {// Vnode moved leftPatchVnode (oldEndVnode, newStartVnode, insertedVnodeQueue); API. InsertBefore (parentElm, oldEndVnode. elm! , oldStartVnode. Elm!) ; OldEndVnode = oldCh [-- oldEndIdx]; NewStartVnode = newCh [+ + newStartIdx];// None of the above four were hit
} else {
if(oldKeyToIdx = = =undefinedOldKeyToIdx = createKeyToOldIdx (oldCh, oldStartIdx, oldEndIdx); }// Get the new node key, can match the key of a node in oldChIdxInOld = oldKeyToIdx[newStartvNode.keyas string];// It doesn't match
if(isUndef (idxInOld)) {// New elementAPI. InsertBefore (parentElm, createElm (newStartVnode, insertedVnodeQueue), oldStartVnode. Elm!) ; NewStartVnode = newCh [+ + newStartIdx];// It works
} else {
// The node corresponding to the keyElmToMove = oldCh [idxInOld];// sel equal (sameVnode condition)
if(elmToMove. sel ! = = newStartVnode. Sel) {// New elementAPI. InsertBefore (parentElm, createElm (newStartVnode, insertedVnodeQueue), oldStartVnode. Elm!) ;// sel equal, key equal
} elsePatchVnode (elmToMove, newStartVnode, insertedVnodeQueue); oldCh[idxInOld] =undefined as any; API. InsertBefore (parentElm, elmToMove. elm! , oldStartVnode. Elm!) ; } newStartVnode = newCh[++newStartIdx]; }}}if(oldStartIdx < = oldEndIdx | | newStartIdx < = newEndIdx) {if(oldStartIdx > oldEndIdx) {before = newCh[newEndIdx +1] = =null ? null: newCh [newEndIdx +1]. Elm; AddVnodes (parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue); }else{removeVnodes (parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the code
Why does V-for use key
As you can see from the updateChildren function above, the key is a key condition for comparing whether the old and new vNodes are equal
According to the source can be known:
-
If no key is used and Diff finds that no key matches, it assumes that all nodes have been updated, and the algorithm destroys all vNodes and re-renders the new element.
-
If a key in the new node is detected to correspond to a key in the old node, such as swapping positions, there is no need to destroy and re-render, just swap positions. Improved performance
If the key uses a random number, it will not work, because when the random number is updated, it will become new, and all the keys will not correspond, so it will re-render as if there is no write
If the key uses the index of the array, if the original element changes from 1 to 0, then after diff, the problem will be that the algorithm will think that the two elements are not changed, and then it will not update