Lesson 44-Virtual DOM Source Code Analysis

Definition and Role of Virtual DOM

Basic Concept of Virtual DOM

Virtual DOM is one of the core concepts of React, representing a lightweight JavaScript object that describes the structure of the real DOM. While not exclusive to React, it has been popularized and widely adopted as a key pattern in modern front-end development.

Essence of Virtual DOM:

• An abstract representation of the real DOM.
• A plain JavaScript object.
• More efficient than direct manipulation of the real DOM.

Why Virtual DOM is Needed:

1. Performance Optimization: Reduces the number of direct real DOM operations.
2. Cross-Platform Capability: The same Virtual DOM can be rendered across different platforms (Web, Native, etc.).
3. Declarative Programming: Developers focus on state changes rather than manual DOM manipulation.

Comparison of Virtual DOM and Real DOM

// Real DOM node
<div id="app" class="container">
  <p>Hello World</p>
</div>

// Corresponding Virtual DOM representation
{
  type: 'div',
  props: {
    id: 'app',
    className: 'container'
  },
  children: [
    {
      type: 'p',
      props: {},
      children: ['Hello World']
    }
  ]
}

// Real DOM node
<div id="app" class="container">
  <p>Hello World</p>
</div>

// Corresponding Virtual DOM representation
{
  type: 'div',
  props: {
    id: 'app',
    className: 'container'
  },
  children: [
    {
      type: 'p',
      props: {},
      children: ['Hello World']
    }
  ]
}

Key Differences:

1. Virtual DOM is an in-memory data structure.
2. Operating on Virtual DOM is significantly faster than on real DOM.
3. Changes in Virtual DOM are eventually applied to the real DOM (via the patch process).

Core Value of Virtual DOM

1. Minimizing DOM Operations:
   • Identifies the minimal set of changes using the Diff algorithm.
   • Updates the real DOM in batches.
2. Cross-Platform Rendering:
   • The same Virtual DOM can be rendered on Web, iOS, Android, and other platforms.
   • React Native is built on this concept.
3. Declarative UI Development:
   • Developers describe the desired UI state.
   • React computes how to transition from the current state to the target state.

Core Logic of the Diff Algorithm

Basic Principles of the Diff Algorithm

React’s Diff algorithm is based on two core assumptions:

1. Similar Tree Structures for Same-Type Components:
   • If components are of the same type, React assumes their subtrees are similar.
   • Subtrees can be recursively compared.
2. Stable Child Elements Identified by Key:
   • The key attribute helps React identify which elements are stable, moved, or deleted.
   • Without keys, React compares child elements in order.

Complexity of the Diff Algorithm:

• Traditional tree comparison algorithms have a time complexity of O(n³).
• React reduces this to O(n) through the two assumptions.

Specific Implementation of the Diff Algorithm

React’s Diff algorithm operates at three levels:

1. Tree Diff:
   • Compares nodes at the same level only.
   • Does not move nodes across levels.
2. Component Diff:
   • For same-type components, compares props and state.
   • For different-type components, unmounts and rebuilds.
3. Element Diff:
   • List element comparison relies on keys.
   • Without keys, compares elements in order.

Simplified Tree Diff Implementation:

function diffTree(oldTree, newTree) {
  // If node types differ, replace the entire subtree
  if (oldTree.type !== newTree.type) {
    return { type: 'REPLACE', node: newTree };
  }

  // Compare property differences
  const propsDiff = diffProps(oldTree.props, newTree.props);

  // Compare child differences
  const childrenDiff = diffChildren(oldTree.children, newTree.children);

  // If there are differences, return update operations
  if (propsDiff.length > 0 || childrenDiff.length > 0) {
    return {
      type: 'UPDATE',
      props: propsDiff,
      children: childrenDiff
    };
  }

  // No differences
  return null;
}

function diffTree(oldTree, newTree) {
  // If node types differ, replace the entire subtree
  if (oldTree.type !== newTree.type) {
    return { type: 'REPLACE', node: newTree };
  }

  // Compare property differences
  const propsDiff = diffProps(oldTree.props, newTree.props);

  // Compare child differences
  const childrenDiff = diffChildren(oldTree.children, newTree.children);

  // If there are differences, return update operations
  if (propsDiff.length > 0 || childrenDiff.length > 0) {
    return {
      type: 'UPDATE',
      props: propsDiff,
      children: childrenDiff
    };
  }

  // No differences
  return null;
}

List Element Diff Algorithm

The Diff algorithm for list elements is the most complex part of React, optimized primarily through keys:

function diffChildren(oldChildren, newChildren) {
  const patches = [];
  const oldMap = createKeyToOldIdx(oldChildren);
  const newMap = createKeyToOldIdx(newChildren);

  // Step 1: Handle deleted and moved nodes
  let lastIndex = 0;
  newChildren.forEach((newChild, newIndex) => {
    const key = newChild.key;
    const oldIndex = oldMap[key];

    if (oldIndex === undefined) {
      // New node
      patches.push({
        type: 'INSERT',
        node: newChild,
        index: newIndex
      });
    } else {
      // Moved node
      if (oldIndex < lastIndex) {
        patches.push({
          type: 'MOVE',
          from: oldIndex,
          to: newIndex
        });
      }
      lastIndex = Math.max(lastIndex, oldIndex);

      // Recursively compare child nodes
      const childPatch = diffTree(oldChildren[oldIndex], newChild);
      if (childPatch) {
        patches.push({
          type: 'UPDATE_CHILD',
          index: newIndex,
          patch: childPatch
        });
      }
    }
  });

  // Step 2: Handle deleted nodes
  oldChildren.forEach((oldChild, oldIndex) => {
    if (!newMap[oldChild.key]) {
      patches.push({
        type: 'REMOVE',
        index: oldIndex
      });
    }
  });

  return patches;
}

function diffChildren(oldChildren, newChildren) {
  const patches = [];
  const oldMap = createKeyToOldIdx(oldChildren);
  const newMap = createKeyToOldIdx(newChildren);

  // Step 1: Handle deleted and moved nodes
  let lastIndex = 0;
  newChildren.forEach((newChild, newIndex) => {
    const key = newChild.key;
    const oldIndex = oldMap[key];

    if (oldIndex === undefined) {
      // New node
      patches.push({
        type: 'INSERT',
        node: newChild,
        index: newIndex
      });
    } else {
      // Moved node
      if (oldIndex < lastIndex) {
        patches.push({
          type: 'MOVE',
          from: oldIndex,
          to: newIndex
        });
      }
      lastIndex = Math.max(lastIndex, oldIndex);

      // Recursively compare child nodes
      const childPatch = diffTree(oldChildren[oldIndex], newChild);
      if (childPatch) {
        patches.push({
          type: 'UPDATE_CHILD',
          index: newIndex,
          patch: childPatch
        });
      }
    }
  });

  // Step 2: Handle deleted nodes
  oldChildren.forEach((oldChild, oldIndex) => {
    if (!newMap[oldChild.key]) {
      patches.push({
        type: 'REMOVE',
        index: oldIndex
      });
    }
  });

  return patches;
}