Why VDOM?

How does the real DOM work

Real DOM rendering is roughly divided into five steps: Create a DOM tree — Create StyleRules — create a Render tree — Lay out — draw.

  1. Using an HTML parser, analyze HTML elements and build a DOM tree (tokenization and tree building).
  2. Using a CSS parser, inline styles on CSS files and elements are analyzed to generate a style sheet for the page.
  3. The third step is to build a Render tree (also known as an Attachment) by associating the DOM tree with the stylesheet. Each DOM node has a attach method that takes style information and returns a Render object (aka renderer). These render objects will eventually be built into a Render tree.
  4. Step 4, with the Render tree, the browser starts laying out the layout and determines the exact coordinates for each node in the Render tree to appear on the display.
  5. Step 5, with the Render tree and node display coordinates in place, call the paint method for each node and draw them.

Updates to the real DOM

When you manipulate the DOM with jQuery, the browser goes through the process from beginning to end, starting with building the DOM tree. In one operation, I needed to update 10 DOM nodes, and the browser received the first DOM request and didn’t know there were nine more updates, so it immediately executed the process and ended up doing 10. For example, after the first calculation, the next DOM update request, the coordinate value of this node changes and the previous calculation is null. Calculating the coordinate values of DOM nodes is a waste of performance. Even though computer hardware is constantly updated, DOM manipulation is still expensive, and frequent manipulation still leads to page stuttering and user experience.

Thus, VDOM was born. Use JS to simulate the DOM structure, calculate the smallest changes, and then manipulate the DOM.

Use VNode to simulate DOM structure

<div id='div1' class='container'>
    <p>vdom</p>
    <ul style='font-size: 20px; '>
        <li>a</li>
    </ul>
</div>
Copy the code

VNode simulation

{
    tag: 'div'.props: {
        id: 'div1'.className: 'container',},children: [{tag: 'p'.children: 'vdom'}, {tag: 'ul'.props: {
                style: 'font-size: 20px'
            },
            children: [{tag: 'li'.children: 'a'},]}]}Copy the code

The diff algorithm

After simulating the DOM with the VDOM, we can use the Diff algorithm to figure out what really changes in the Virtual DOM and only do native DOM manipulation for that part of the Virtual DOM instead of re-rendering the entire page.

Traditional DIff algorithm

Diff algorithm is a broad concept, such as Linux diff command, Git diff, etc. Two JS objects can also do diff. Two more trees do diff, like vDOM diff here.

Take the diff algorithm of trees, for example, by comparing each node in a recursive loop between two trees, the complexity of the algorithm reaches O(n^3), where n is the number of nodes. So, if we want to show 1000 nodes, we need to perform 100 million comparisons… This one is a little scary…

Optimized DIFF algorithm

The optimized DIff algorithm transforms O(n^3) complexity into O(n) complexity through the following strategies:

  1. Compare only the same level, not across levels

  1. If the tag is different, delete it and rebuild it

  1. If the tag and key are the same, they are considered the same node and are not compared in depth.

A combination of VNode and diff algorithms

Vue’s rendering performance compared to React was mentioned in the official documentation as being superior due to its use of snabbDOM.

JavaScript overhead is directly related to the mechanism for evaluating the necessary DOM operations. Although both Vue and React use the Virtual Dom to do this, Vue’s Virtual Dom implementation (copied from SnabbDOM) is much lighter and therefore more efficient than the React implementation.

Let’s take a look at the snabbdom source code

VNode

At the beginning of this article, we used VNode to simulate DOM. What is a VNode?

The Virtual Node of Snabbdom is a pure data object created by the VNode module. The object attributes include:

  • sel
  • data
  • children
  • text
  • elm
  • key

You can see that the Virtual Node uses the following data to create a real Node:

  • The element type
  • Element attributes
  • Element child node
// The VNode function is used to convert input to VNode
    / * * * *@param Sel selector *@param Data Bound data *@param Children array of child nodes *@param Text Indicates the current text node content *@param Elm's reference to a real DOM element@returns {{sel: *, data: *, children: *, text: *, elm: *, key: undefined}} * /
function vnode(sel, data, children, text, elm) {
     var key = data === undefined ? undefined : data.key;
      return { sel: sel, data: data, children: children,
          text: text, elm: elm, key: key };
}
Copy the code

However, Snabbdom does not expose vNodes to us directly. Instead, it wraps them in h, which handles arguments:

h(sel,[data],[children],[text]) => vnode
Copy the code

Snabbdom source code can be seen, in fact, there are these functions:

export function h(sel: string) :VNode; 
export function h(sel: string, data: VNodeData) :VNode; 
export function h(sel: string, text: string) :VNode; 
export function h(sel: string, children: Array<VNode | undefined | null>) :VNode; 
export function h(sel: string, data: VNodeData, text: string) :VNode; 
export function h(sel: string, data: VNodeData, children: Array<VNode | undefined | null>) :VNode; 
Copy the code

patch

Once the vNode is created, the next step is to call patch() to render the real DOM.

Patch is returned by the init function of snabbDOM. Snabbdom. init passes in modules arrays, which extend snabbDOM’s ability to create complex DOM.

Patch on the source code

return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    
    // Perform callback pre hook (DOM lifecycle)
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // The first argument is not vnode
    if(! isVnode(oldVnode)) {// Create an empty vNode associated with the DOM element
      oldVnode = emptyNodeAt(oldVnode);
    }

    // Same vnode (same key and sel)
    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } 
    // Delete different vnodes
    else{ elm = oldVnode.elm! ; parent = api.parentNode(elm)as Node;

      / / reconstruction
      createElm(vnode, insertedVnodeQueue);

      if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]); }for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
Copy the code

Check whether oldVnode and Vnode are the same first. If so, patchVnode can be executed; otherwise, create a new DOM and delete the old DOM. It is easy to determine whether the source code is identical, according to the optimized diff algorithm strategy 1 and 3, only compare the key and tag at the same level:

function sameVnode(vnode1: VNode, vnode2: VNode) :boolean {
  const isSameKey = vnode1.key === vnode2.key;
  constisSameIs = vnode1.data? .is === vnode2.data? .is;const isSameSel = vnode1.sel === vnode2.sel;

  return isSameSel && isSameKey && isSameIs;
}
Copy the code

If they are the same, patchVnode is invoked for comparison.

Graph TB start [patch function is invoked] -- > conditionA or DOM node} {oldVnode is virtual node conditionA - the DOM node - > operationA] [oldVnode packing into virtual node OperationA - > conditionB} {judging oldVnode and newVnode is a same node conditionA -- -- > is a virtual node conditionB conditionB - not - > ConditionB conditionB -- yes --> operationC

patchVnode

Let’s start with patchVnode

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    // Execute prepatch hooks, similar to lifecycle hooks
    consthook = vnode.data? .hook; hook? .prepatch? .(oldVnode, vnode);// Set the vNode element to the same value as the old one
    constelm = (vnode.elm = oldVnode.elm)! ;//old children
    const oldCh = oldVnode.children as VNode[];
    //new children
    const ch = vnode.children as VNode[];
    
    if (oldVnode === vnode) return;
    
    / / the hooks
    if(vnode.data ! = =undefined) {
      for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode); vnode.data.hook? .update? .(oldVnode, vnode); }// vnode.text === undefined meaning vnode.children! == undefined
    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); }// Old children do not, new children do
      else if (isDef(ch)) {
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      } 
      // Old children do, new children do not
      else if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      } 
      // The old text has a value, the new one does not
      else if (isDef(oldVnode.text)) {
        api.setTextContent(elm, ""); }}// vnode.text ! == undefined means vnode.children === undefined
    else if(oldVnode.text ! == vnode.text) {// Remove the old text
      if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
      // Set the new textapi.setTextContent(elm, vnode.text!) ; } hook? .postpatch? .(oldVnode, vnode); }Copy the code
Graph TB condition1 (newVnode condition2) condition1 (newVnode condition2) Condition2 condition3{newVnode condition3 condition3} condition3 condition3 condition3{newVnode condition3 condition3 condition3 condition3 Condition2 --> condition4{oldVnode --> condition4 --> condition3 --> condition2 --> condition4{oldVnode --> condition4 --> condition3 --> condition3 --> condition4 --> condition4 UpdateChildren op4 [call]

updateChildren

The key and core of patchVnode is updateChildren(). This method is the main place to implement the DIff algorithm.

function updateChildren(parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    let oldKeyToIdx: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: 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];
      }
      
      // Compare the old and new start vNodes
      else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } 
      
      // Compare the old and new end vNodes
      else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } 
      
      // Compare the old start vnode with the new end vnode
      else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Vnode moved rightpatchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue); api.insertBefore( parentElm, oldStartVnode.elm! , api.nextSibling(oldEndVnode.elm!) ); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; }// Compare the old end vnode with the new start vnode
      else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved leftpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue); api.insertBefore(parentElm, oldEndVnode.elm! , oldStartVnode.elm!) ; oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; }// Other circumstances
      else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        
        // Check whether the new node's key corresponds to a node's key in old children
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        
        // New elements need to be created
        if (isUndef(idxInOld)) {
          // New elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }// It works
        else {
          elmToMove = oldCh[idxInOld];
          // Compare selectors, not equal
          if(elmToMove.sel ! == newStartVnode.sel) {//new elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }/ / the selector is equal
          else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined asany; api.insertBefore(parentElm, elmToMove.elm! , oldStartVnode.elm!) ; } } newStartVnode = newCh[++newStartIdx]; }}/ / end
    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

The code is a bit more complex and may be easier to understand in the diagram above.

OldCh and newCh values when updateChildren() is called.

Define oldStartIdx, oldEndIdx, newStartIdx newEndIdx

So let’s compare the four scenarios,

  1. OldVnode start and newVnode start, if true, oldStartIdx++ newStartIdx++ is moved after patch
  2. OldVnode end and newVnode end, if true, move tail pointer oldEndIdx– newEndIdx– after patch
  3. OldVnode start and newVnode end, if true, the node pointing to newEndIdx moves after oldStartIdx oldStartIdx++ newEndIdx–
  4. OldEndIdx — newStartIdx++ if oldEndIdx– newStartIdx++ if oldEndIdx– newStartIdx++

Of course, if none of the above four conditions are met, then the key needs to be traversed. If found, patchVNode() is added, if not found.

At the end of the comparison, a judgment is made.

  1. NewVnode has a surplus. Whatever is left in the new node is inserted after or before the old oldEnd node
  2. There are still nodes in the oldVnode, delete them directly.

The flow chart looks like this

Graph of TD start [patch function is invoked] -- > conditionA or DOM node} {oldVnode is virtual node conditionA - the DOM node - > operationA] [oldVnode packing into virtual node OperationA - > conditionB} {judging oldVnode and newVnode is a same node conditionA -- -- > is a virtual node conditionB conditionB - not - > OperationB [delete oldVnode violence, insert newVnode] conditionB -- - > condition1 {oldVnode and newVnode whether the same object} condition1 -- - > Condition1 condition2{newVnode condition2} condition2 condition1 {newVnode condition2} condition2 condition2 Condition3 {newVnode condition3 -> op1 condition3 -> op2 condition2 -> newVnode condition3 -> condition3 Condition4 {oldVnode have children} condition4 -- no --> op3 condition4 --> op4 Op5 [several situation hit] -- > condition5 {} whether there is any remaining items condition5 - all over the old node - > create a new element insert condition5 - all over the new node - > delete all remaining old node