“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”
Record a self-study of the virtual Dom Diff.
What is the Virtual Dom
The virtual DOM is basically a JavaScript object that abstracts the real DOM. The object properties describe the node information. This JavaScript object describes the structure of the DOM tree, which is not a real DOM tree, so it’s called the virtual DOM.
An 🌰
Real Dom
<div class="container">
<h1>hello</h1>
<p>The sun is just right, the breeze is not dry</p>
<p>Go see who you want to see</p>
</div>
Copy the codeVirtual Dom
Vnode = {
sel: "div"./ / selector
props: {class: "container"},
children: [{sel: "h1".props: {},
children: "hello"
},
{
sel: "p".props: {},
children: "The sun is just right, the breeze is gentle."
},
{
sel: "p".props: {},
children: "Go see who you want to see."}}]Copy the codeVirtual Dom Diff
When one or some nodes in the virtual DOM change, a new virtual DOM will be generated. The differentiated optimal solution in the new and old virtual DOM trees is mapped to the real DOM, which is the virtual DOM Diff.
newVnode
newVnode = {
sel: "div".props: {class: "container"},
children: [{sel: "h1".props: {},
children: "hi"
},
{
sel: "p".props: {},
children: "The sun is just right, the breeze is gentle."
},
{
sel: "p".props: {},
children: "Go see who you want to see."}}]Copy the codeSuch as illustration:
How to use the virtual DOM and learn its diff principles
The existing virtual DOM library is used, understood, and learned.
This time I chose snabbdom.js, the virtual DOM library used by vue2. X
The core code
Principle of Diff algorithm
The old and new virtual DOM are compared only across hierarchies, not across hierarchies.
Diff comparison process
When data changes and a new virtual DOM (newVnode) is created, the pathch method is called to diff the old and new virtual DOM, map the result to the real DOM, and then update the view.
A concrete analysis
This is to learn snabbdom.js source code, their own implementation of a simplified version of the virtual DOM, link, interested can understand.
patch
Patch is the entrance of diff, and its main function is to judge whether the old and new virtual DOM are the same node
export default function(oldVnode, newVnode) {
// Check whether oldVnode is a DOM node or a vnode. If it is a DOM node, wrap it as a vnode
if(! oldVnode.sel) { oldVnode = vnode( oldVnode.tagName.toLowerCase(), {}, [],undefined,
oldVnode
);
}
// Check whether oldVnode and newVnode are the same node
if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
console.log('Patch - Old and new nodes are the same node, perform pathVnode, further compare');
patchVnode(oldVnode, newVnode);
}
else {
console.log('Patch - Replace old node with new node if new node is not the same');
/* Convert Vnode to real Dom and replace oldDom with newDom */
const newDomNode = createElement(newVnode);
if (newDomNode && oldVnode.elm) {
// Insert a new node
oldVnode.elm.parentNode.insertBefore(newDomNode, oldVnode.elm);
// Delete the old nodeoldVnode.elm.parentNode.removeChild(oldVnode.elm); }}}Copy the codepatchVnode
The main function of patchVnode is to judge the situation of new and old virtual DOM subsets. Depending on the situation
// Check whether Vnode children is empty
const checkChildrenEmpty = (Vnode) = > {
return !Array.isArray(Vnode.children) || Vnode.children.length === 0;
}
export default function patchVnode(oldVnode, newVnode) {
/** * If newVnode is a text node or children * newVnode is a text node, please empty the oldDom element and add the text content as newVnode. Then we need to further determine whether oldVnode has children nodes. * oldVnode does not contain children, so empty the text content, and convert the children in newVnode into the real Dom and insert it into oldDom. * oldVnode also contains children, so it needs to be refined to make the most elegant diff */
if (newVnode.text) {
if(! checkChildrenEmpty(oldVnode)) { oldVnode.elm.innerHtml ="";
oldVnode.elm.innerText = newVnode.text;
}
else if (newVnode.text !== oldVnode.text) {
oldVnode.elm.innerText = newVnode.text;
}
}
else {
if (checkChildrenEmpty(oldVnode)) {
for (let i = 0; i < newVnode.children.length; i++) {
constch = createElement(newVnode.children[i]); oldVnode.elm.appendChild(ch); }}else{ updateChildren(oldVnode.elm, oldVnode.children, newVnode.children); }}}Copy the codeupdateChildren
UpdateChildren is the most complex and important part of patchVnode, where the comparison between the old and new virtual DOM child nodes takes place.
Comparison method:
The old and new virtual DOM, each group of two Pointers (start and end), are compared according to the different situations in 5, and the view is updated through pointer movement and node comparison.
🌰
template
<- oldVnode ->
<ul>
<li>a</li>
<li>b</li>
<li>c</li>
</ul>
<- newVnode ->
<ul>
<li>d</li>
<li>c</li>
<li>b</li>
<li>e</li>
</ul>
Copy the codeThe representation of the beginning and end double Pointers in the virtual DOM
Algorithm coverage is as follows:
1. OldStart and newStart, if sameVnode is true, further patchVnode, move pointer
2. OldEnd and newEnd, if sameVnode is true, further patchVnode, move pointer
3. OldStart and newEnd, if sameVnode is true, further patchVnode, move pointer
4. OldEnd and newStart, if sameVnode is true, further patchVnode, move pointer
5. If none of the preceding four types match, a Map table is made for all remaining old child nodes based on keys, and then the new VNode keys are used to find whether there are reusable locations.
6. If a group of the old and new virtual DOM is moved first (start > end), you need to insert or delete the specified node
Follow the example above, illustrated
1. In case 5, insert startVnode in the new Vnode before startVnode in the old Vnode. Note: This operation is a real DOM update
The actual DOM and pointer movement at this point
2. If condition 4 is met, insert the node corresponding to oldEndVnode in front of the node corresponding to oldStartVnode to operate the real DOM.
The actual Dom and pointer movement at this point
3. As in Step 2, condition 4 is still met.
The actual Dom situation and pointer movement are as follows
4. The situation is the same as step 1 above and condition 5 is met.
The actual Dom situation and pointer movement
5. NewStart > newEnd indicates that newVnode traversal is complete and the remaining oldVnode nodes need to be removed.
End result:
UpdateChildren source code is as follows
/ * * * *@param {Element} ParentElm Parent node *@param {Array} OldCh Children * in the old Vnode@param {Array} NewCh Children */ in the new vNode
export default function updateChildren(parentElm, oldCh, newCh) {
/** * 5 comparisons: * 1.oldStrat compares with newStrat * 2. OldEnd compares with newEnd * 3. OldStart compares with newEnd * 4. If none of the above logic matches, create a key -> index table that maps all the keys of the old node to the index of the old node, and then use the new vNode's keys to find the location that can be reused in the old node */
// Two Pointers per set (head and tail)
let oldStartIdx = 0,
oldEndIdx = oldCh.length - 1,
newStartIdx = 0,
newEndIdx = newCh.length - 1;
let oldStartVnode = oldCh[0],
oldEndVnode = oldCh[oldEndIdx],
newStartVnode = newCh[0],
newEndVnode = newCh[newEndIdx];
let oldKeyToIdx // The key Map table in the old Vnode
let idxInOld // Check whether the specified Vnode of the new Vnode exists in the old Vnode
let elmToMove // If a vnode corresponding to the new vnode.key exists in the keyMap table, move the vnode
// Start traversal
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// The first is not to judge the hit, but to filter things that have undefined marked
if (oldStartVnode === null || oldCh[oldStartIdx] === undefined) {
oldStartVnode = oldCh[++oldStartIdx]
}
else if (oldEndVnode === null || oldCh[oldEndIdx] === undefined) {
oldEndVnode = oldCh[--oldEndIdx]
}
else if (newStartVnode === null || newCh[newStartIdx] === undefined) {
newStartVnode = newCh[++newStartIdx]
}
else if (newEndVnode === null || newCh[newEndIdx] === undefined) {
newEndVnode = newCh[--newEndIdx]
}
else if (checkSameVnode(oldStartVnode, newStartVnode)) {
// The old - the new
patchVnode(oldStartVnode, newStartVnode);
// The pointer moves
// The corresponding Vnode moves
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
}
else if (checkSameVnode(oldEndVnode, newEndVnode)) {
// Old queen - new queen
patchVnode(oldEndVnode, newEndVnode);
// The pointer moves
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (checkSameVnode(oldStartVnode, newEndVnode)) {
// Old before - new after
patchVnode(oldStartVnode, newEndVnode);
// Move the old pre-DOM behind the current old post-DOM in the real DOM
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
// The pointer moves
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (checkSameVnode(oldEndVnode, newStartVnode)) {
// Old back - new front
patchVnode(oldEndVnode, newStartVnode);
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
else {
// If the first four types are not matched, this logic is used
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // Create index table with key
}
// Check whether there is a new former node in the old - remaining node
idxInOld = oldKeyToIdx[newStartVnode.key];
if(! idxInOld) {// If it does not exist, the node is inserted before the old-former node
const dom = createElement(newStartVnode);
parentElm.insertBefore(dom, oldStartVnode.elm);
// New - the front pointer moves
newStartVnode = newCh[++newStartIdx];
}
else {
elmToMove = oldCh[idxInOld];
// If the selectors are different, insert them directly
if(elmToMove.sel ! == newStartVnode.sel) {const dom = createElement(newStartVnode);
parentElm.insertBefore(dom, oldStartVnode.elm);
}
else {
// If the selector is the same, patchVnode is used
patchVnode(elmToMove, newStartVnode);
oldCh[idxInOld] = null; parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; }}}if (oldStartIdx > oldEndIdx) {
// This indicates that the oldVnode list has been traversed and newVnodeList needs to convert the remaining vNodes into real Dom inserts
let base = oldEndVnode.elm;
for(; newStartIdx <= newEndIdx; ++newStartIdx) { parentElm.insertBefore(createElement(newCh[newStartIdx]), base.nextSibling); base = base.nextSibling; }}else if (newStartIdx > newEndIdx) {
// The newVnode list has been traversed and the oldVnodeList remaining Ndoe needs to be removed
for(; oldStartIdx <= oldEndIdx; ++oldStartIdx) { oldCh[oldStartIdx] && parentElm.removeChild(oldCh[oldStartIdx].elm); }}}Copy the codeRefer to the link
- Snabbdom source code download
- Juejin. Cn/post / 684490…
- Juejin. Cn/post / 699495…