Start with a rant. Every programmer has heard of the disdain chain, that those who do C look down on those who do C++, those who do C++ look down on those who do Java, and those who do Java look down on those who do.NET. However, all of these look down on the front end! It seems that front-end programmers are at the bottom of the programmer disdain chain. 🙄

Because the output of the front end is visible and tangible, it has caused the phenomenon that anyone can make some comments:

A product manager who only sees the interface can make comments;

The project manager can also have some comments;

The boss who doesn’t know anything can give some advice.

Even the back end can give some advice;

This is the biggest pain in front development… .

Third rate programmers write the UI, second rate programmers write the framework, and first rate programmers write the algorithms. Students together refueling!

Without further ado, let’s get down to business. For better reading and understanding, this paper mainly focuses on the following three points:

  1. What is a Virtual DOM and why do we use it?
  2. What are the advantages of the virtual DOM over the real DOM?
  3. How to calculate dom changes (diff algorithm)?

What is the Virtual DOM and why do we use it?

Virtual DOM is that we use a native JS object to describe a DOM node. Curious students will ask: What does this object look like? Here I’ll take Snabbdom as an example:

There are six properties defined in VNode. For a more intuitive comparison to the real DOM, let’s try printing out all the attributes of a simple div element:

Due to the huge size of the real DOM, modern Web applications are becoming more and more complex and cool (and will operate the DOM more frequently), so the students of front-end development also bring some questions: how to optimize the page, and improve the performance of our Web applications?

Speaking of page optimization, I have to mention how modern browsers work. In how Browsers Work: Behind the Scenes of New Web Browsers, Israeli developers Tali Garsiel and Paul Irish point out that HTML rendering can be broken down into the following steps:

  1. Parsing THE HTML to construct the DOM tree. Parsing the HTML to the DOM tree. Parsing the CSS to the CSSOM tree.

  2. At the same time as the DOM tree is built, the browser also builds another tree structure: the Render Tree, which is a tree of visual elements in their display order and a visual representation of the document. It lets the browser draw the content in the correct order.)

  3. Layout of the Render tree. After the Render tree is built, it enters the “Layout” processing stage, which is to assign each node an exact coordinate that should appear on the screen. In Mozilla, it’s called a Reflow; in WebKit, it’s called a Layout.)

  4. The final stage is Painting the render tree. The rendering engine traverses the rendering tree, and the user interface backend layer draws each node.

     

For a better user experience, the rendering engine strives to bring content to the screen as quickly as possible. It doesn’t have to wait until the entire HTML document is parsed before it starts building the rendering tree and setting up the layout. While receiving and processing the rest of the content from the network, the rendering engine parses some of the content and displays it. Therefore, we need to minimize the adverse impact of rearrangement and redrawing on the user.

How do you assign, value, and style a div element? Did you simply write a bunch of document.getelementById () in your business code? So what’s the problem with directly manipulating the DOM?

  1. Frequent dom manipulation can cause performance problems. From the perspective of the high-level structure of the browser, the rendering engine and javascript parser are independent of each other. We use JS to frequently operate the DOM through functional interfaces to achieve communication. There must be a performance cost.
  2. If we have a lot of DOM operations in JS we’re going to keep triggering the browser’s rendering engine to go through the process all over again. (rearrange, redraw)
  3. In terms of code maintainability, there is a lot of logically-irrelevant code. (Increased maintenance costs)

So how do we change that? Next, let’s welcome our protagonist (pig’s foot, manual funny) -Virtual DOM

What are the advantages of the virtual DOM over the real DOM?

  1. Reduce DOM manipulation (The virtual DOM can combine multiple operations into a single operation. If you add 1000 nodes, the traditional way is to do it one by one. The virtual DOM uses DOM Diff to eliminate unnecessary steps, such as adding 1000 nodes when only 10 nodes are added.)
  2. Cross-platform rendering (The virtual DOM can not only become a real DOM, but also small programs, IOS applications, android applications, because the virtual DOM is essentially just a JS object.)
  3. Server Rendering (SSR)

Good boy! The virtual DOM comes with its own protagonist aura. So let’s get to the point.

Snabbdom contains a very simple, high-performance, extensible core of only about 200 lines (the official introduction, but take a look at the init.ts file for 333 lines of code 😁). It provides a feature-rich modular architecture that can be extended with custom modules. To keep the core simple, all non-essential functionality is delegated to modules. (vue.js inside especially big is also borrowed from Snabbdom to transform the virtual DOM. To understand the rationale behind vue.js, it is highly recommended to take a look at Snabbdom’s source code.

Apart from module functions, the principle of Snabbdom is actually very simple. The process from creating virtual DOM to creating real DOM on the page can be roughly divided into the following two steps:

  1. Create a VNode (JS object) using the h() function to record the real DOM.
  2. Use init() to set the module to return patch(). The patch function takes two parameters patch(oldVnode, newVnode). The first is the DOM element or vnode that represents the current view. The second is the VNode that represents the updated new view. The patch method updates the changed content to the real DOM tree and returns vNode for use as oldVnode in the next update.

Git directory:

Init. Ts file:

To demonstrate, I’ll write a simple example. Create a new directory diff and create index1.js and index. HTML files in this folder.

Index1. Js file:

import { init } from ".. /.. /build/package/init.js"; import { classModule } from ".. /.. /build/package/modules/class.js"; import { heroModule } from ".. /.. /build/package/modules/hero.js"; import { styleModule } from ".. /.. /build/package/modules/style.js"; import { eventListenersModule } from ".. /.. /build/package/modules/eventlisteners.js"; import { h } from ".. /.. /build/package/h.js"; let patch = init([classModule, heroModule, styleModule, eventListenersModule]); let oldVnode = null; let app = document.querySelector("#test"); let vnode = h("ul.father", [ h("li.children", { key: 1, style: { color: "red" } }, "A"), h("li.children", { key: 2 }, "B"), h("li.children", { key: 3 }, "C"), h("li.children", { key: 4 }, "D"), h("li.children", { key: 5, style: { color: "blue" } }, "E"), ]); oldVnode = patch(app, vnode);Copy the code

The index.html file:

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-width, Initial =1.0" /> <meta http-equiv=" x-uA-compatible "content="ie=edge" /> <title> Diff algorithm </title> </head> <body> <div id="test"></div> <script type="module" src="./index1.js"></script> </body> </html>Copy the code

When we’re done, we open it up in the browser, and you can see that the page generates the unordered list that we just wrote.

Ok, so that’s the whole process from creating a virtual DOM to generating a real DOM (are you obsolete?). . So let’s look at what dom Diff is.

How to calculate dom changes (diff algorithm)?

Diff algorithm is an inevitable product of virtual DOM technology: It compares the old and new virtual DOM (DIFF) and updates the changed places on the real DOM. It is rare to move or update a parent node to a subnode during DOM operations, so the Diff algorithm is used to compare children at the same level. Two characteristics of Diff algorithm:

  1. Diff occurs on a node of the same level (sameVnode: oldvNode.key === newvNode.key && oldvNode.sel === newvNode.sel) ** **
  2. The Diff algorithm is depth-first (going all the way down the DOM tree, comparing peers first)

The core of snAbbDOM’s diff algorithm is updateChildren(). The function of updateChildren() is to update the DOM by comparing the children of the new and old nodes.

Function updateChildren (parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {// user defined hook function let oldStartIdx = 0 // start of old node let newStartIdx = 0 // start of new node let oldEndIdx = oldch.length-1 // End of the old node let oldStartVnode = oldCh[0] Child let oldEndVnode = oldCh[oldEndIdx] Child let newEndIdx = end of the old node Let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx] // End child let of the new node OldKeyToIdx: KeyToIndexMap | undefined / / according to the old node array to generate the corresponding key and the index map object let idxInOld: Let elmToMove: VNode // Let before: 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] } else if (sameVnode(oldStartVnode, NewStartVnode)) {//oldStartVnode/newStartVnode (old start node/new start node) same // Call patchVnode() to compare and update nodes // move back the old start and new start indexes oldStartIdx++ / oldEndIdx++ patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, NewEndVnode)) {//oldEndVnode/newEndVnode (old end node/new end node) same // Call patchVnode() to compare and update nodes // move oldStartIdx-- forward oldStartIdx-- / oldEndIdx-- patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, NewEndVnode)) {// Vnode Moved Right //oldStartVnode/newEndVnode (old start node/new end node) Same // Call patchVnode() to compare and update the node // Put OldStartVnode DOM element, PatchVnode (oldStartVnode, newEndVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldstartVNode.elm! , api.nextSibling(oldEndVnode.elm!) ) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldEndVnode, NewStartVnode)) {// Vnode Moved left // oldEndVnode/newStartVnode (old end node/new start node) Same // Call patchVnode() to compare and update the node // Handle OldEndVnode DOM element, PatchVnode (oldEndVnode, newStartVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldendVNode.elm! , oldStartVnode.elm!) OldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx]} else { If newStartNode is not found, newStartNode is the new node. // Create the DOM element corresponding to the new node. Insert into the DOM tree // If found // Determine whether the sel selector of the new node is the same as that of the old node found // If not, the node has been modified // Recreate the corresponding DOM element and insert into the DOM tree // If the same, The DOM element corresponding to elmToMove, If (oldKeyToIdx === undefined) {oldKeyToIdx = createKeyToOldIdx(oldCh, oldCh, oldCh, oldCh); oldStartIdx, oldEndIdx) } idxInOld = oldKeyToIdx[newStartVnode.key as string] if (isUndef(idxInOld)) { // New element api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!) } else { elmToMove = oldCh[idxInOld] if (elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!) } else { patchVnode(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 Before = newCh[newEndIdx + 1] == null? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, } else {removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)}}Copy the code

We can actually think of the new and old children as two arrays, so that we can understand more vividly when sorting and comparing. As shown in figure:

In fact, the process of DIff can be divided into five cases, which are described as follows:

(1) The old start node is the same as the new start node —-sameVnode(oldStartVnode, newStartVnode). Key === newStartVnode**.key &&** oldStartVnode**. Sel ===** newStartVnode**.sel) **

Processing steps:

  1. Call patchVnode() to compare and update nodes

  2. Move the old and new start indexes back (++oldStartIdx/ ++newStartIdx)

** (2), **** The old end node is the same as the new end node —-**sameVnode(oldEndVnode, newEndVnode)

Processing steps:

  1. Call patchVnode() to compare and update nodes

  2. Move the old and new ending indexes forward (–oldStartIdx / –oldEndIdx)

**sameVnode(oldStartVnode, newEndVnode) **sameVnode(oldStartVnode, newEndVnode)

Processing steps:

  1. Call patchVnode() to compare and update nodes

  2. Move the old start node to the end

  3. Move the old start index back and the new end index forward (++oldStartIdx / –newEndIdx)

**sameVnode(oldEndVnode, newStartVnode) **sameVnode(oldEndVnode, newStartVnode)

Processing steps:

  1. Call patchVnode() to compare and update nodes

  2. Move the old end node to the front

  3. Move the old ending index forward and the new ending index back (–oldEndIdx / ++newStartIdx)

(five), the above four cases do not meet

** Processing steps: **

  1. Use the key of newStartNode to find the same node in the old node array
  2. If it is not found, it is a new node. Insert newStartNode before oldStartVnode.

3. If it is found and the new node has the same selectors (sel) as the old node found. Call patchVnode() and move the node corresponding to elmToMove to the left.

4. If it is found, and the new node has different selectors (sel) than the old node found. The old node has been modified, and a real DOM element corresponding to the vnode is recreated and put in the current location.

5. When the loop is over and all the child nodes of the old node are traversed (oldStartIdx > oldEndIdx), it indicates that the new node is left. Insert the remaining nodes to the right in batches.

6. When the loop is over and all the child nodes of the new node are traversed (oldStartIdx <= oldEndIdx), the old node is left, and the remaining nodes are deleted in batches.

So that clears up the whole idea of diff’s algorithm. Code words are not easy, if there are mistakes, please help to point out. Thank you very much!