My Awesome Project

Appearance

十、Diff算法 ​

0、构造数据 ​

js
import { compileToFunction } from './compiler/index';
import { createElm, patch } from './vdom/patch';

// 1. 创建第一个虚拟节点
let vm1 = new Vue({ data: { name: 'test1' } });
let render1 = compileToFunction(
	`<div>
		<li style="background:red;" key="A">A</li>
		<li style="background:yellow;" key="B">B</li>
		<li style="background:pink;" key="C">C</li>
		<li style="background:green;" key="D">D</li>
		<li style="background:green;" key="F">F</li>
	</div>`
);
let oldVnode = render1.call(vm1);

// 2. 创建第二个虚拟节点
let vm2 = new Vue({ data: { name: 'test2' } });
let render2 = compileToFunction(
	`<div>
		<li style="background:green;" key="M">M</li>
		<li style="background:pink;" key="B">B</li>
		<li style="background:yellow;" key="A">A</li>
		<li style="background:purple;" key="Q">Q</li>
	</div>`
);
let newVnode = render2.call(vm2);

// 3. 通过第一个虚拟节点做首次渲染
let el = createElm(oldVnode)
document.body.appendChild(el);

// 4. 调用patch方法进行对比操作
// 传入新的、老的虚拟节点, 然后用新的虚拟节点对比老的虚拟节点，找到差异，去更新老的dom元素
setTimeout(() => {
    patch(oldVnode, newVnode);
}, 3000);

1、具体思路 ​

  • 通过同层的树节点进⾏比较，⽽非对树进行逐层搜索遍历的⽅式，所以时间复杂度只有O(n)，是⼀种相当高效的算法
  • 同层三件事：增删改，具体规则是：
    1. 新节点(new Vnode)不存在就删
    2. 老节点(old Vnode)不存在就增
    3. 都存在就比较类型，类型不同直接替换、类型相同执行更新

Vue

2、基本比对 ​

(1) 比对标签

js
// 1. 比较两个元素的标签，标签不一样直接替换掉
if (oldVnode.tag !== vnode.tag) {
	// 新的标签替换标签
	return oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el);
}

// 2. 如果标签一样，而里面的文本内容不一致，例如：<div>1</div> <div>2</div>
if (!oldVnode.tag) {
	// 因为文本节点的虚拟节点tag 都是undefined，所以需要!oldVnode.tag来判断
	// 两个文本不一致，直接用新的替换老的
	if (oldVnode.text !== vnode.text) {
		return oldVnode.el.textContent = vnode.text;
	}
}

(2) 比对属性

js
// 3. 标签一样，并且需要开始比对标签的属性和儿子
// 第一步：直接复用节点
let el = vnode.el = oldVnode.el;
// 第二步：新老属性做对比，然后更新属性，用新的虚拟节点的属性和老的比较，去更新节点
updateProperties(vnode, oldVnode.data);

(3) 比对子元素

js
// 4. 比较儿子的几种情况
let oldChildren = oldVnode.children || [];
let newChildren = vnode.children || [];

if (oldChildren.length > 0 && newChildren.length > 0) {
	// (3) 老的有儿子，新的也有儿子，diff算法
	updateChildren(oldChildren, newChildren, el);
} else if (oldChildren.length > 0) {
	// (1) 老的有儿子，新的没有儿子
	el.innerHTML = '';
} else if (newChildren.length > 0) {
	// (2) 老的没有儿子。新的有儿子
	for (let i = 0; i < newChildren.length; i++) {
		let child = newChildren[i];
		el.appendChild(createElm(child));
	}
}

3、优化策略 ​

(1) diff算法

  • 采用双指针操作：一个循环，同时循环老的和新的，哪个先结束，循环就停止，将多余的删除或者添加进去
  • 比对策略：
    1. 老的头部和新的头部比对
    2. 老的尾部和新的尾部比对
    3. 老的头部和新的尾部比对
    4. 老的尾部和新的头部比对
    5. 儿子直接没关系进行暴力比对

Vue

(2) 代码实现

js
// src\vdom\patch.js

// 判断是否为相同的虚拟节点
function isSameVnode(oldVnode, newVnode) {
    return oldVnode.tag == newVnode.tag && oldVnode.key == newVnode.key;
}

// 比对儿子
function updateChildren(oldChildren, newChildren, parent) {
    // vue2 采用双指针操作
    // 一个循环，同时循环老的和新的，那个新结束，循环就停止，将多余的删除或者添加进去

    // 老节点
    let oldStartIndex = 0; // 开始索引
    let oldStartVnode = oldChildren[0]; // 开始节点
    let oldEndIndex = oldChildren.length - 1; // 结束索引
    let oldEndVnode = oldChildren[oldEndIndex]; // 结束节点

    // 新节点
    let newStartIndex = 0; // 开始索引
    let newStartVnode = newChildren[0]; // 开始节点
    let newEndIndex = newChildren.length - 1; // 结束索引
    let newEndVnode = newChildren[newEndIndex]; // 结束节点

    function makeIndexByKey(children) {
        let map = {};
        children.forEach((item, index) => {
            if (item.key) {
                map[item.key] = index; // {A:0, B:1, C:2, D:3}
            }
        });
        return map;
    }
    let map = makeIndexByKey(oldChildren);

    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        if (!oldStartVnode) {
            // 如果指针指向null，需要跳过这些节点
            // 从左往右遍历的情况
            oldStartVnode = oldChildren[++oldStartIndex];
        } else if (!oldEndVnode) {
            // 如果指针指向null，需要跳过这些节点
            // 从右往左遍历的情况
            oldEndVnode = oldChildren[--oldEndIndex];
        } else if (isSameVnode(oldStartVnode, newStartVnode)) {
            // 1. 老的头部和新的头部比较
            // 从左往右开始比对，如果两个是同一个元素，比对儿子，更新属性和再去更新子节点
            patch(oldStartVnode, newStartVnode);
            // 向后移动指针
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
        } else if (isSameVnode(oldEndVnode, newEndVnode)) {
            // 2. 老的尾部和新的尾部比较
            // 从右往左开始比对，如果两个是同一个元素，比对儿子，更新属性和再去更新子节点
            patch(oldEndVnode, newEndVnode);
            // 向前移动指针
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
        } else if (isSameVnode(oldStartVnode, newEndVnode)) {
            // 3. 老的头部和新的尾部比较
            patch(oldStartVnode, newEndVnode);
            // 将老的当前元素插入到尾部的下一个元素的前面
            parent.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
            // 移动指针：老的开始指针从左往右移动(向后移动)，新的尾部指针从右往左移动(往前移动)
            oldStartVnode = oldChildren[++oldStartIndex];
            newEndVnode = newChildren[--newEndIndex];
        } else if (isSameVnode(oldEndVnode, newStartVnode)) {
            // 4. 老的尾部和新的头部比较
            patch(oldEndVnode, newStartVnode);
            // 将当前元素插入到尾部的下一个元素的前面
            parent.insertBefore(oldEndVnode.el, oldStartVnode.el);
            // 移动指针：老的尾部指针从右往左移动(往前移动),新的开始指针从左往右移动(向后移动)
            oldEndVnode = oldChildren[--oldEndIndex];
            newStartVnode = newChildren[++newStartIndex];
        } else {
            // 5. 儿子之前没关系：暴力比对
            // 拿到新的开头的虚拟节点的key，去老的中找
            let moveIndex = map[newStartVnode.key];
            if (moveIndex == undefined) {
                // 没有复用的key，不需要移动老节点，只需要将新的节点插入到老节点的开头就行了
                parent.insertBefore(createElm(newStartVnode), oldStartVnode.el);
            } else {
                // 有复用的key，需要先移动老节点，然后再将老节点原来的索引位置置为null，方便最后删除
                let moveVnode = oldChildren[moveIndex];
                oldChildren[moveIndex] = null;
                parent.insertBefore(moveVnode.el, oldStartVnode.el);
                // 可能老节点和新节点的属性和儿子不一样，需要比较属性和儿子
                patch(moveVnode, newStartVnode);
            }
            // 往后移动指针，用新的不停地去老的里面找 
            newStartVnode = newChildren[++newStartIndex];
        }

        // 反转节点，头部移动到尾部，尾部移动到头部
        // 为什么要有key，不能用index作为key?
        // key没变，元素复用，但是内容发生了变化
    }

    // 新节点中多余的元素添加到父亲中，从新节点的结束指针开始到末尾
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            // 将多余的元素插入进去，可能是向前添加，也可能向后添加
            // parent.appendChild(createElm(newChildren[i]));
            // 向后插入：ele = null
            // 向前插入：ele就是当前向谁前面插入
            let ele = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].el;
            parent.insertBefore(createElm(newChildren[i]), ele);
        }
    }

    // 老的节点还没有处理的，说明这些老节点是不需要的节点
    // 如果这里面有null，说明这个节点已经被处理过了，就跳过
    if (oldStartIndex <= oldEndIndex) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            let child = oldChildren[i];
            if (child != undefined) {
                parent.removeChild(child.el);
            }
        }
    }
}
js
// src\vdom\patch.js

// 创建节点
export function createElm(vnode) {
    let { tag, children, key, data, text } = vnode;
    if (typeof tag == 'string') {
        // 创建元素，放到vnode.el上
        vnode.el = document.createElement(tag);

        // 只有元素才有属性
        updateProperties(vnode);

        // 遍历儿子，将儿子渲染后的结果放到父亲中
        children.forEach(child => {
            vnode.el.appendChild(createElm(child));
        })
    } else {
        // 创建文本，放到vnode.el上
        vnode.el = document.createTextNode(text);
    }
    return vnode.el;
}

// 更新属性的方法
function updateProperties(vnode, oldProps = {}) {
    // 当前的真实节点
    let el = vnode.el;
    // 获取当前节点的属性(新的属性)
    let newProps = vnode.data || {};

    // 老的有，新的没有，需要删除属性
    for (let key in oldProps) {
        if (!newProps[key]) {
            //  移除真实dom的属性
            el.removeAttribute(key);
        }
    }

    // 样式处理,老的 style={color:red} 新的 style={background:Red}
    let newStyle = newProps.style || {};
    let oldStyle = oldProps.style || {};
    // 老的样式中有，新的没有，删除老的样式
    for (let key in oldStyle) {
        if (!newStyle[key]) {
            el.style[key] = '';
        }
    }

    // 新的有，直接用新的去更新
    for (let key in newProps) {
        if (key == 'style') { // {color: red}
            // 样式需要遍历添加
            for (let styleName in newProps.style) {
                el.style[styleName] = newProps.style[styleName];
            }
        } else if (key == 'class') {
            // class直接添加
            el.className = newProps[key];
        } else {
            // 属性就需要利用方法添加，值就是对应的值
            el.setAttribute(key, newProps[key]);
        }
    }
}

4、更新操作 ​

js
// src\lifecycle.js

export function lifecycleMixin(Vue) {
    Vue.prototype._update = function(vnode) {
        const vm = this;

        // 需要区分首次渲染还是更新
        const prevVnode = vm._vnode;
        if (!prevVnode) {
            // 用新创建的元素，替换老的vm.$el
            vm.$el = patch(vm.$el, vnode);
        } else {
            // 上一次的vnode和本次做对比
            vm.$el = patch(prevVnode, vnode);
        }
        // 保存上一次的vnode
        vm._vnode = vnode;
    }
}

Released under the MIT License.

Copyright © 2019-present Evan You