Deep Dive into Vue.js Virtual DOM Diff Algorithm and Source Code Analysis

This article provides a comprehensive analysis of the diff algorithm used in virtual DOM, specifically for Vue.js, covering the logic and source code implementation.

1. Preparation - Virtual Node Depth-First and Same-Level Comparison

The diff method uses depth-first traversal and same-level comparison. Each virtual node is compared at the same level (corresponding to the same parent element in the DOM). The algorithm compares nodes level by level, ensuring that child nodes are fully processed before moving to siblings.

2. Simple Judgment - sameVnode Function

The sameVnode function determines whether two virtual nodes are the same. It uses two key elements: key (developer-defined) and sel (element tagName + element id + element class). The sel is constructed from the vNode creation function.

3. Building Indexes

The algorithm builds an index map from the old array to efficiently look up nodes during comparison.

4. Element Handling Strategy

The algorithm tries to minimize DOM additions/deletions. For same vnodes, it performs patch operations to update content while preserving the DOM element.

5. Comparison Process

The algorithm uses an O(n) while loop with two main comparison strategies:

Head-Tail Comparison: Uses four pointers (oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) and compares nodes at head-head, tail-tail, and head-tail positions.

Index Comparison (Worst Case - O(n)): When head-tail comparison fails due to additions/deletions, it builds an index object from the old array and performs position matching.

After the main loop, if the new array is exhausted but old array remains, it performs batch deletion. If the old array is exhausted but new array remains, it performs batch insertion.

6. Key Points Summary

The core algorithm combines head-tail comparison with index-based matching to efficiently compute the minimum number of DOM operations.

7. Vue 3.0 Optimizations

Vue 3.0 introduces static type VNodes - if a vnode is of static type, it skips the update entirely and just changes the reference. This includes comment types and the new Fragment type.

8. Practical Application

The author implemented a similar diff algorithm for array change detection, providing detailed information about which elements changed and their positions during update, add, and delete operations.