Simple virtual DOM and diff algorithm

This is the 28th day of my participation in the More Text Challenge. For more details, see more text Challenge

📢 preface

It is well known that interviewers love to test vDOM and DIFF algorithms in front of interviews. For example, it might appear in the following scenario 🤏

Drip drip, the interviewer sent me an invitation for an interview. Accept the invitation 📞

🧑 Interviewer: Do you know the function of key?

🙎 me: The function of key is to ensure the uniqueness of data.

🧑 Interviewer: How to ensure the uniqueness of the data?

🙎 me: just….

🧑 Interviewer: Do you know virtual DOM?

🙎 me: The virtual DOM is… balabala

🧑 interviewer :(seems a bit reasonable) do you know the diff algorithm?

🙎 me: (heart: what… What is diff algorithm??

🧑 Interviewer: This interview is over. Go back and wait for the interview result.

🙋 🙋 🙋

As we all know, the role of key in the front end of the interview is a very common question, but most of the time, we are only floating on the surface of the knowledge, but not to dig into the principle, this time our competitiveness will be pulled down in this. Therefore, in-depth learning of principles is an essential process for improving one’s core competitiveness.

In the next article, we’ll look at the virtual DOM that is popular in interviews and the DIff algorithm behind it.

I. ☂️ Virtual DOM (Vitual DOM)

1. Relationship between virtual DOM (Vitual DOM) and Diff

As we all know, DOM manipulation is very performance intensive. In the early days, we used JQuery to control the timing of DOM manipulation by hand, which was not particularly convenient. Therefore, virtual DOM, or Vitual DOM (hereinafter referred to as VDOM), emerged to solve the problem of DOM operation. Vdom is a hot topic these days, and it’s also a hot topic in the interview, and it’s almost always asked about the virtual DOM in the front end of the interview.

The reason why the question of VDOM is asked is that the current popular VUE and React frameworks are both data-driven views and are implemented based on VDOM. It can be said that VDOM is an important cornerstone for the implementation of VUE and React.

When it comes to VDOM, diff algorithm comes to mind. So what is the relationship between diff algorithm and VDOM?

In fact, VDOM is a big concept, and DIFF algorithm is a part of VDOM. The core value of VDOM lies in minimizing the use scope of DOM. Vdom simulates DOM in the way of JS, then calculates and compares, and finally finds out the smallest update scope to update. So the process of comparison is called diff algorithm. That is to say, they have an inclusive relationship, as shown in the figure below:

It can be said that DIFF algorithm is the most core and key part of VDOM, and the core of the entire VDOM is surrounded by a large number of DIFF algorithms.

With these concepts laid in place, let’s begin to understand what a virtual DOM is.

2. Real DOM rendering process

Before we get into the virtual DOM, let’s take a look at how the real DOM is parsed in a browser. The browser rendering engine workflow is roughly divided into the following four steps:

Create a DOM tree → create a CSSOM tree → generate a Render tree → lay out the Render tree → draw the Render tree.

Step 1: CreateDOMThe tree. The rendering engine first parsesHTMLCode and generateDOMThe tree.
Step 2: CreateCSSOMThe tree. Browse for externalcssFile after the data will look like buildDOMStart building like a treeCSSOMTree, this is exactly the same as the first step.
Step 3: GenerateRenderThe tree. willDOMTrees andCSSOMThe trees are correlated to produce a treeRender(Render) tree.
Step 4: LayoutRenderThe tree. There are theRenderAfter the tree, the browser starts to layout each node of the rendered tree, determining itThe display position on the screen.
Step 5: DrawRenderThe tree. willEach nodeDraw it to the screen.

To show the real DOM rendering process, quote an image from the Internet:

3. What is the Virtual DOM?

When using native JS or JQ to manipulate the real DOM, the browser starts by building the DOM tree and runs through the process. So if you do that, you’re likely to do too many operations. When the number of operations is too many, the previously calculated coordinate values associated with the DOM node and other values will be…… Unconsciously, the performance is wasted, and thus the virtual DOM is created.

4. Solution – VDOM

(1)

As you all know, DOM trees have a certain amount of complexity, so in the process of generating A DOM tree, you will continue to do calculation operations, but the difficulty is that it is actually difficult to reduce the number of calculations.

If you think about it another way, we all know that the execution speed of JS is very, very fast, can you try to convert this calculation into more JS calculation? The answer is yes.

(2) VDOM how to solve the problem: the real DOM into JS object calculation

Assuming that 1000 nodes need to update the DOM in one operation, the virtual DOM will not immediately manipulate the DOM. Instead, the virtual DOM will save the diff contents of the 1000 updates to a local JS object, and then attach the JS object to the DOM tree once. At the end of the day, you do the following, so you avoid a lot of unnecessary calculations.

Therefore, the advantage of using JS objects to simulate DOM nodes is that all page updates are reflected to the virtual DOM first, and in this way, the JS objects in memory ** are manipulated first. It is worth noting that manipulating JS objects in memory is quite fast. Therefore, after all DOM nodes are updated, the final JS object is mapped to the real DOM and then drawn by the browser.

In this way, the problem of slow rendering and high performance consumption of real DOM is solved.

5, using JS to simulate a DOM structure

According to the following HTML code, use v-Node to simulate the DOM structure of the HTML code.

HTML code:

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

Use JAVASCRIPT to simulate the DOM structure of the above code:

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

Using the above code we can analyze that we use tag, props, and children to simulate the DOM tree structure. Using JS to simulate the structure of the DOM tree, the advantage of this is that you can calculate the smallest change, the least manipulation of the DOM.

6. Learn VDOM through SNabbDOM

Vue’s VDOM and DIff algorithms are modified by referring to snabbDOM, an open source library on Github. So we will use this library as an example to learn the idea of VDOM.

(1) What is snabbDOM

snabbdomIs a simple and powerful onevdomLibrary, easy to learn and use;
VueRefer to what it implementsvdom 和 diff ；
Vue3.0Rewrite thevdomCode that optimizes performance.

(2) Brief analysis of SNABbDOM

Let’s take a look at Example on the snabbDOM homepage to get a sense of the idea. Here’s the code:

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");
// The h function inputs a tag, followed by a data, and finally a child element
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!"),]);// The first patch function
// 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!"),]);// The second patch function
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
Copy the code

As we can see from the official example, the h function inputs a tag, then a data, and finally a child element. And function H is the structure of a Vnode (see point 5 above for the structure of Vnode), and it progresses hierarchically one by one. Finally, there is the patch function. The first patch function is used to render elements, and the second patch function is used to compare old and new nodes.

(2) SnabbDOM demo

Next, we introduce the SNABbDOM library in the way of CDN to demonstrate how SNABbDOM operates vDOM. Attach the code:

<! DOCTYPEhtml>
<html>
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <div id="container"></div>
    <button id="btn-change">change</button>

    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-class.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-props.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-style.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-eventlisteners.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script>

    <script>
        const snabbdom = window.snabbdom

        / / define the patch
        const patch = snabbdom.init([
            snabbdom_class,
            snabbdom_props,
            snabbdom_style,
            snabbdom_eventlisteners
        ])

        / / define h
        const h = snabbdom.h

        const container = document.getElementById('container')

        / / generated vnode
        const vnode = h('ul#list', {}, [
            h('li.item', {}, 'Item 1'),
            h('li.item', {}, 'Item 2')
        ])
        patch(container, vnode)

        document.getElementById('btn-change').addEventListener('click'.() = > {
            / / generated newVnode
            const newVnode = h('ul#list', {}, [
                h('li.item', {}, 'Item 1'),
                h('li.item', {}, 'Item B'),
                h('li.item', {}, 'Item 3')
            ])
            patch(vnode, newVnode) // vnode = newVnode → patch = newVnode = patch = newVnode

        })

    </script>
</body>
</html>
Copy the code

Now let’s look at the browser display:

As you can see, the end result is that when we click, instead of rerendering the whole tree, the DOM tree is recompared only to the changed values, and only the changed nodes are finally rendered.

Through this demonstration, I believe you have a certain understanding of the difference between the real DOM and the virtual DOM.

7. Vdom summary

With that said, let’s summarize vDOM:

Can be achieved byJSTo simulate theDOMStructure (vnode);
The old and newvnodeCompare, concludeMinimum update rangeAnd the lastUpdate the DOM;
In data-driven view mode, DOM operation can be effectively controlled.

2. 🧶diff algorithm

As mentioned above, the core value of VDOM is to minimize the scope of DOM use. What is the method of VDOM? It is to simulate the DOM with JS, then calculate and compare, and finally find out the minimum update range to update. So this process of comparison corresponds to the diff algorithm that we often hear about.

Let’s take a look at another aspect of VDOM, the Diff algorithm.

1. Diff algorithm

Diff algorithm is a hot topic in the front end, and it is also the most core and key part of VDOM.
Diff algorithms are common in everyday vUE and React (e.g., Key).

2. Overview of Diff algorithm

diff 即contrast, it is aA wide range ofConcepts, such asLinux diff command,Git diff commandAnd so on.
Two JS objects can also do thisdiff, such asgithubOn theJiff libraryThis library can be used directly to diff two JS objects.
Do two treesdiffAs mentioned abovevdom 和 diff 。

Let’s look at an example 🌰 :

Looking at the two trees above, we can imagine how it does diff. We can see that the tree on the right is going to change the E on the left to X, and we’re going to add a node, H. Therefore, if diff is implemented, we can compare the old node with the new node. If the comparison is the same, we leave it alone. If the comparison is different, modify it. This way, the 5 nodes only need to be modified 2 times instead of 5 times, which is very UpUp.

3, the time complexity of tree diff O(n)³)

For the tree, the original time complexity is O(n3). So where does this O(n3) come from?

First, walk through Tree1; Second, iterate over Tree2; Finally, the tree is sorted. So n by n by n, you get to O of n3.

So let’s say I have 1,000 nodes to operate on, that’s 1,000 to the third power a billion times, so this algorithm for trees is not going to work. So how do we solve this? So let’s move on.

4. Optimize time complexity to O(n)

Since the time complexity of the tree is O(n3), we try to optimize its time complexity from O(n3) to O(n) to operate vDOM nodes. This optimization process is actually called diff algorithm. With the Diff algorithm, we can optimize the time complexity from O(n3) to O(n). The specific idea of diff algorithm is as follows:

Only compare the same level, not across levels;
tagIf they are not the same, they will be deleted directly and no further comparison will be made.
tag 和 keyThey are both the sameThe same nodeNo more depth comparison.

Three, 🎩 deep diff algorithm source code

1. Generate a VNode

To review snabbDOM, the diff comparison starts with the h function, which inputs a tag, then a data, and finally a child element. In addition, the h function is a vnode structure, and it progresses hierarchically. Finally, there is the patch function. The first patch function is used to render elements, and the second patch function is used to compare old and new nodes.

Let’s look at how it generates vNodes.

Cloning a snabbdom code down first, open the SRC | h.t s files, directly to see h function, specific code is as follows:

export function h(sel: string) :VNode;
export function h(sel: string, data: VNodeData | null) :VNode;
export function h(sel: string, children: VNodeChildren) :VNode;
export function h(
  sel: string,
  data: VNodeData | null,
  children: VNodeChildren
) :VNode;
export function h(sel: any, b? : any, c? : any) :VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  if(c ! = =undefined) {
    if(b ! = =null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c;
    } else if(c && c.sel) { children = [c]; }}else if(b ! = =undefined&& b ! = =null) {
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b;
    } else if (b && b.sel) {
      children = [b];
    } else{ data = b; }}if(children ! = =undefined) {
    for (i = 0; i < children.length; ++i) {
      if (is.primitive(children[i]))
        children[i] = vnode(
          undefined.undefined.undefined,
          children[i],
          undefined); }}if (
    sel[0= = ="s" &&
    sel[1= = ="v" &&
    sel[2= = ="g" &&
    (sel.length === 3 || sel[3= = ="." || sel[3= = ="#")
  ) {
    addNS(data, children, sel);
  }
  // Return vnode. This vnode corresponds to the Vnode in patch
  return vnode(sel, data, children, text, undefined);
}

Copy the code

We see in the last line that h returns a vNode function. After we continue to find vnode files in SRC | vnode. Ts file. Attach the most critical part of the code:

export function vnode(
  sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined
) :VNode {
  const key = data === undefined ? undefined : data.key;
  // Return an object
  // ELM indicates which DOM element corresponds to the vNode structure
  // Key can be understood as the key we use when v-for
  return { sel, data, children, text, elm, key };
}
Copy the code

Again, at the last line, you can see that vNode is actually returning an object. And in this object, there are six elements. Among them, the four elements sel, data, children and text correspond to the structure corresponding to vnode mentioned above (point 5 of the first point). Elm represents the DOM element corresponding to the vnode structure, and the final key can be understood as the key used when we use V-for. At the same time, it should be noted that key may not only be used in V-for, but can be used in various scenarios such as defining components.

2. Patch function

After looking at vNode, let’s look at how to compare vNode with patch function. From the official document we can locate the patch function in the SRC | init. Ts file, we found the init. Ts file. Similarly, we locate the patch function, and the specific code is as follows:

// Return a patch function
  return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    // Execute the pre hook. Hook is the life cycle of the DOM node
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // The first argument is not a vNode, but a DOM element
    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
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } 
    // Delete vnode from vnode
    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

Reading the code above, we can see that the first parameter is not a Vnode, but a DOM element. In this case, we need to create an empty vnode to associate with the DOM element.

After having the first Vnode, we can compare the new and old nodes in the second patch. The comparison between the new node and the new node is to judge whether the key and SEL are the same first. If they are the same, the pathVNode function is used to compare the new node and the new node. If it is a different VNode, delete the rebuild directly.

3. PatchVnode function

Above, we mentioned that the patchVnode function compares the old and new nodes. The following is a detailed analysis of patchVnode. Also in the SRC | init. Ts file, attach patchVnode function code:

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    // Execute prepatch hook
    consthook = vnode.data? .hook; hook? .prepatch? .(oldVnode, vnode);/ / set the vnode. Elem
    constelm = (vnode.elm = oldVnode.elm)! ;/ / the old children
    const oldCh = oldVnode.children as VNode[];
    / / new children
    const ch = vnode.children as VNode[];

    // Return if the new and old nodes are equal
    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 (vnode.children); Children and text can only exist together.)
    if (isUndef(vnode.text)) {
      // Both new and old Vnodes have children
      if (isDef(oldCh) && isDef(ch)) {
        // updateChildren: both have children
        if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);// New vnode has chindren, old vnode has no children (old vnode has text)
      } else if (isDef(ch)) {
        // Clear the text of the old vnode
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        / / add the children
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        // The old vnode has children, the new vnode has no children
      } else if (isDef(oldCh)) {
        // Remove children from the old vnode
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        // Old vnodes have text
      } else if (isDef(oldVnode.text)) {
        api.setTextContent(elm, "");
      }

      // else: vnode.text ! = undefined (vnode.text has a value, old vnode.children has no value)
    } else if(oldVnode.text ! == vnode.text) {// Remove children from the old vnode
      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

Reading the above source code, we can know:

(1) When the old Vnode has text, it means that the old children has no value, and the new Vnode’s text has a value. At this time, we delete the children of the old vnode, delete the end of the new vnode set the text;

(2) When both new and old nodes have children, we need to update them, namely, operate the updateChildren function. We’ll talk about that later.

(3) If the new Vnode has children but the old Vnode has no children, it means that the old Vnode has text. Therefore, it is necessary to clear the text of the old Vnode and add new children to it.

(4) If the old Vnode has children but the new Vnode does not, remove the children of the old Vnode.

(5) If both the old and new nodes have text, the new vnode’s text value is directly assigned to the old Vnode’s text.

Take a look at the image below:

4, updateChildren function

When we analyzed pathVnode we talked about using the updateChildren function to update the children of the new and old nodes. Let’s look at this function:

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];

        // Start and start contrast
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];

        // Compare the end and end
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];

        // Compare the beginning and end
      } 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 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];// The above four missed
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }

        // Select * from oldCh; // Select * from oldCh
        idxInOld = oldKeyToIdx[newStartVnode.key as string];

        // There is no corresponding
        if (isUndef(idxInOld)) {
          // New elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ;// The corresponding
        } else {
          // The node corresponding to the key
          elmToMove = oldCh[idxInOld];

          // Sel is equal (sameVnode condition)
          if(elmToMove.sel ! == newStartVnode.sel) {// sel is not equal, maybe just key is equal; That doesn't help. We have to rebuild the New Elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ;// sel is equal, key is equal; Run the patchVnode function
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined asany; 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

Let’s start with two pictures:

If you look at Figure 1, what update Dren does is compare the old and new nodes, and if they’re the same, don’t update them, and if they’re different, update them.

Looking at Figure 2, the update is done by comparing oldStartIdx, newStartIdx, oldEndIdx, and newEndIdx to determine whether the update operation is required.

So how do these four values compare? So let’s move on.

Reading the source code, we can analyze how to update the nodes by comparing the four types of nodes.

First, the old start node oldStartIdx is compared to the new start node newStartIdx. Second, the old start node oldStartIdx is compared to the new end node newEndIdx. Third, the old end node oldEndIdx is compared to the new start node newStartIdx. Fourth, the old end node oldEndIdx is compared to the new end node newEndIdx.

If none of the above four comparisons is matched, the key of the new node is taken and then the key is checked to see if it corresponds to the key of a node in oldCh. If there is no corresponding, the element is rebuilt directly. If sel and key are equal, the patchVnode function will be executed. If they are not equal, the same as before, and the element can only be reconstructed.

Four, 🩸 conclusion

The core concepts of VDOM are mainly h, vnode, patch, diff, and key. In my opinion, the whole diff comparison revolves around these functions, so it is important to understand these core concepts. Another, more important value of VDOM is data-driven views. Vdom allows data to drive views by controlling the operations of the DOM.

So much for virtual DOM and Diff! Hope to be helpful to everyone!

Follow the public account Monday research office, and share the learning dry goods irregularly, so as not to get lost on the way to study ~

If this post was useful to you, be sure to like it and follow it

See you next time! 🥂 🥂 🥂

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

How much do you know about virtual DOM? Read the Diff algorithm in depth

Simple virtual DOM and diff algorithm

📢 preface

I. ☂️ Virtual DOM (Vitual DOM)

1. Relationship between virtual DOM (Vitual DOM) and Diff

2. Real DOM rendering process

3. What is the Virtual DOM?

4. Solution – VDOM

(1)

(2) VDOM how to solve the problem: the real DOM into JS object calculation

5, using JS to simulate a DOM structure

6. Learn VDOM through SNabbDOM

(1) What is snabbDOM

(2) Brief analysis of SNABbDOM

(2) SnabbDOM demo

7. Vdom summary

2. 🧶diff algorithm

1. Diff algorithm

2. Overview of Diff algorithm

3, the time complexity of tree diff O(n)³)

4. Optimize time complexity to O(n)

Three, 🎩 deep diff algorithm source code

1. Generate a VNode

2. Patch function

3. PatchVnode function

4, updateChildren function

Four, 🩸 conclusion

How much do you know about virtual DOM? Read the Diff algorithm in depth

Simple virtual DOM and diff algorithm

📢 preface

I. ☂️ Virtual DOM (Vitual DOM)

1. Relationship between virtual DOM (Vitual DOM) and Diff

2. Real DOM rendering process

3. What is the Virtual DOM?

4. Solution – VDOM

(1)

(2) VDOM how to solve the problem: the real DOM into JS object calculation

5, using JS to simulate a DOM structure

6. Learn VDOM through SNabbDOM

(1) What is snabbDOM

(2) Brief analysis of SNABbDOM

(2) SnabbDOM demo

7. Vdom summary

2. 🧶diff algorithm

1. Diff algorithm

2. Overview of Diff algorithm

3, the time complexity of tree diff O(n)3)

4. Optimize time complexity to O(n)

Three, 🎩 deep diff algorithm source code

1. Generate a VNode

2. Patch function

3. PatchVnode function

4, updateChildren function

Four, 🩸 conclusion

Related Posts

Use globalThis to access global variables

Vue+Element tables are exported as Excel files through the front end

Bytedance favorite test front: CSS basics

3, the time complexity of tree diff O(n)³)