background

Vue introduced the virtual DOM in version 2.0. The virtual DOM algorithm is modified based on the SNabbDOM algorithm. See github.com/vuejs/vue/b… Comment section. In order to understand Vue, you must understand the virtual DOM. This article focuses on what the virtual DOM is, why it is used, and how it is implemented.

What is the virtual DOM

Use JavaScript to simulate the DOM tree to form a virtual DOM tree, as shown in the HTML structure

<ul style="color:#000"> <li> Apple </li> <li> banana </li> <li> Orange </li> </ul>Copy the code

You can use the following JS representation

{
    sel: 'ul',
    data: { style: {color: '# 000'}}, // children: [// child {sel:'li', text: 'apple'},
        {sel: 'li', text: 'banana'},
        {sel: 'li', text: 'orange'}}]Copy the code

Why use the virtual DOM

Direct manipulation of the DOM is slow and inefficient. The browser’s rendering process involves parsing the HTML to build the DOM tree -> build the Render tree -> layout the render tree -> draw the render tree, and every DOM change from building the render tree to layout to rendering has to be redone. Reference documentation

The advantages of the virtual DOM are as follows: 1. Developers no longer care about the DOM and only care about data, improving development efficiency. 2. Minimize DOM operations to improve execution efficiency.

The advantage of the virtual DOM is not that it is faster to manipulate the DOM, but that it can minimize real DOM operations by comparing the virtual DOM, refer to the documentation

The realization of virtual DOM

Implementing the virtual DOM involves the following three steps

  1. Use JavaScript to simulate DOM tree to form a virtual DOM tree

  2. Compare the old and new virtual DOM trees when the component state is updated

  3. Apply the difference to the real DOM

3.1 Use JavaScript to simulate DOM tree to form virtual DOM tree

The virtual DOM object contains the following properties:

  • Sel: selector
  • Data: binding data (attribute/props/eventlistner/class/the dataset/hook)
  • Children: array of child nodes
  • Text: indicates the current text node content
  • Elm: A reference to a real DOM element
  • Key: Used to optimize DOM operations

Reference github.com/snabbdom/sn…

3.2 Compare the old and new virtual DOM trees when the component state is updated

Given any two trees, find the least number of transformation steps. But the standard Diff algorithm requires O(n^3).

This is obviously insufficient for performance, given the front-end operations — we rarely change nodes across levels, usually modifying node attributes, adjusting the order of children, adding children, and so on. When comparing virtual DOM trees, if a node is found to no longer exist, the node and its children are completely removed and not used for further comparison. This allows you to compare the entire DOM tree with only one walk through the tree.

Virtual DOM only compares nodes of the same level, and its complexity is reduced to O(n). In addition, only the key and SEL are the same, which means the same node.

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}
Copy the code

Example: The nodes in the following figure change from left to right

The virtual DOM does this

A.destroy(); 
A = new A(); 
A.append(new B()); 
A.append(new C()); 
D.append(A);
Copy the code

Rather than

A.parent.remove(A);
D.append(A);
Copy the code
3.3 Apply the difference to the real DOM
  1. If the old node is not present, the new node is inserted
  2. If the new node does not exist, the old node is deleted
  3. If the old and new are the same (key and SEL are the same):
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    ...
    const elm = vnode.elm = (oldVnode.elm as Node);
    let oldCh = oldVnode.children;
    let ch = vnode.children;
    if (oldVnode === vnode) return; // undefined...if(isUndef(vnode.text)) {// The new node is not a textNodeif(isDef(oldCh) &&isdef (ch)) {// If all the children exist, updateChildren diff the childrenif(oldCh ! == ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue); }else if(isDef(ch)) {// The old node has no children, and the new node has children. Add the children of the new nodeif (isDef(oldVnode.text)) api.setTextContent(elm, ' ');
        addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
      } else if(isDef(oldCh)) {// The new node has no children, and the old node has children. RemoveVnodes (elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length-1); }else if(isDef(oldvNode.text)) {// The old and new nodes have no children. Update text API. SetTextContent (elm,' '); }}else if(oldVnode.text ! == vnode.text) {api.settextContent (elm, vnode.text as string); }... }Copy the code

Let me give you an example

If two elements are the same (key and SEL), its children are judged, and four variables are maintained in the process

  • OldStartIdx => Old header index
  • OldEndIdx => Old tail index
  • NewStartIdx => New header index
  • NewEndIdx => New tail index

For example, children in the following figure are represented by ABCDEF -> ADGCEF. It is assumed that sel of children are the same and set with key. The key of A is A, the key of B is B, and so on

The circular judgment is as follows:

  • Step1: compare the first element (oldStart/newStart), if the same, move to continue, otherwise step2
  • Step2: compare the last element (oldEnd/newEnd), if the same, move forward to continue, otherwise step3
  • Step3: compare the first and last elements (oldStart/newEnd), if the same, move the elements and continue, otherwise step4
  • Step4: compare the last and first elements (oldEnd/newStart), if the same, move the elements and continue, otherwise step5
  • Step5: check whether newStart exists in the old node. If it exists, move it; otherwise, add it
  • Finally: Delete redundant old nodes or insert redundant new nodes

See the source github.com/snabbdom/sn…

Why maintain four variables? What are the advantages? Are two variables ok? Leave a question here.

The first step

OldStart === newStart, perform 3.3 above. And oldStartIdx++ newStartIdx++.

The second step

OldEnd === newEnd, perform 3.3 above. And oldEndIdx–, newEndIdx–.

The third step

As above, oldEnd === newEnd, then perform 3.3 above. NewEndIdx, and oldEndIdx – -.

The fourth step

  1. oldStart ! == newStart
  2. oldEnd ! == newEnd
  3. oldStart ! == newEnd
  4. oldEnd === newStart

OldEnd === newStart, insert oldEnd before oldStart and perform 3.3 above. And oldEndIdx – newStartIdx++.

Step 5

The beginning and end elements are different! Determines whether newStart exists in the old element, moves if it does, or inserts the new element otherwise

OldKeyToIdx = [B, C] // All elements G from oldStartIdx to oldEndIdxin [B, C] ? NO!
Copy the code

Insert newStart before oldStart and perform 3.3 above. And newStartIdx++.

Step 6

Same as above. H in [B, C] ? NO! Insert newStart before oldStart and perform 3.3. And newStartIdx++.

Step 7

The traversal of the new node is complete. Out of the loop, delete B and C in turn. The end of the

At this point, the loop loop completes. Now answer the above question, why maintain four variables? What are the advantages? Are two variables ok? Of course, two variables are ok. The advantage of four variables is that four variables can better deal with the insertion scenario. Such as:

  • ABCDEF -> GABCDEF scene
  • ABCDEF -> BCDEFA scene

Reference documentation

  • Github.com/snabbdom/sn…
  • calendar.perfplanet.com/2013/diff/
  • Segmentfault.com/a/119000000…
  • Segmentfault.com/a/119000000…
  • www.zhihu.com/question/29…
  • www.infoq.com/cn/articles…