虚拟dom和diff算法

本文章原生编写.模拟vue中render和更新dom的diff算法.

创建虚拟dom
通过render函数把虚拟dom转化为真实dom渲染到浏览器.
通过新旧虚拟dom的更新(diff算法).
通过patch打补丁更新dom渲染.

什么是虚拟DOM？

实现虚拟dom

function createElement(type, props, ...children) {
    let key
    if (props.key) {
        key = props.key;
        delete props.key
    }
    //处理文本节点
    children = children.map(vnode => {
        if (typeof vnode === "string") {
            return vNode(undefined, undefined, undefined, [], vnode)
        }
        return vnode
    })
    return vNode(type, props, key, children, text = undefined)
}

function vNode(type, props, key, children, text) {
    return { type, props, key, children, text }
}

创建完虚拟对象,创建render函数把虚拟dom渲染成真实dom.

function render(vNode, container) {
    //传入虚拟dom和真实的容器;
    let ele = createDomElementFrom(vNode);
    container.appendChild(ele);
}

function createDomElementFrom(vNode) { 
    //把虚拟dom转为真实的dom返回
	let { type, props, key, children, text } = vNode;
    if (type) { // 判断是否标签
        //给当前的虚拟对象挂载一个真实dom属性;
        vNode.domElement = document.createElement(type);
        // 添加属性方法
        updateEleProperties(vNode);
        //递归调用子组件
        vNode.children.forEach(element => {
        	render(element, vNode.domElement)
        });
    } else { //文本节点
        vNode.domElement = document.createTextNode(text);
    }
	return vNode.domElement
}

function updateEleProperties(newVnode, oldPros = {}) {
    //oldPros传入这个参数是更新的时候需要做对比.后面会说到.初始渲染为空.
    let element = newVnode.domElement;
    let newProps = newVnode.props;

    // 事件以及其他特殊的属性需要自己再去做其他处理这里只是style举例一下
    for (let key in oldPros) { //首次渲染不会走这
        // 新节点上没有老节点属性, 直接删除
        if (!newProps[key]) {
            delete element[key];
        }
        if (key === "style") {
            let oleStyleProps = oldPros.style || {};
            let a = newProps.style || {};
            for (let key in oleStyleProps) {
                // 新样式节点上没有老样式节点属性, 直接删除
                if (!a[key]) {
                    element.style[key] = '';
                }
            }
        }
    }

    for (let key in newProps) {
        //新节点上新增属性,直接添加
        if (key === 'style') {
            //style特殊属性 
            let newStyleProps = newProps.style || {};
            for (let key in newStyleProps) {
                // 新节点上新增style属性,直接添加 
                element.style[key] = newStyleProps[key];
            }
        } else {
            element[key] = newProps[key];
        }
    }
}

以上render的基本初始渲染已经完事.可以拿在浏览器上运行了.

let oldVnode = createElement("div", { className: "xxx" }, 
                             createElement("span", {}, "我是span标签")
                            );
render(oldVnode, document.querySelector("#app"))

虚拟dom的初始渲染完成,接下来就要实现dom更新的操作了.

dom更新的时候。不能直接说把新的dom直接替换掉旧的dom。这里就需要diff算法来对比新旧节点的差异以及能复用的东西。提高性能.跟vue一样通过patch函数进行打补丁.

function patch(oldVnode, newVnode) { // patch新旧dom更新;打补丁
    if (oldVnode.type !== newVnode.type) { // 新标签类型和旧标签类型不一致,直接替换.
        return oldVnode.domElement.parentNode.replaceChild(createDomElementFrom(newVnode), oldVnode.domElement);
    }

    if (oldVnode.text !== newVnode.text) { //文本不一致
        return oldVnode.domElement.textContent = newVnode.text;
    }

    // 标签一样属性不一致
    let domElement = newVnode.domElement = oldVnode.domElement;//拿到真实dom
    updateEleProperties(newVnode, oldVnode.props);//对比新,旧的props进行更新,这里传了第二个参数就是为了新旧props对比.

    // 对比子节点 三种情况
    if (!newVnode.children.length) {
        // newVnode没有子节点
        domElement.innerHTML = '';
    } else if (oldVnode.children.length && newVnode.children.length) {
        // 新旧都有子节点 - 进入核心diff对比.
        updateChildren(domElement, oldVnode.children, newVnode.children);
    } else {
        //newVnode没有子节点,oldVnode没有子节点
        newVnode.children.forEach((children) => {
            //这里的children是一个虚拟dom需要转化为真实dom直接使用函数转化.
            domElement.appendChild(createDomElementFrom(children))
        })
    }
}

核心diff

代码实现

这里我给说一下代码实现的思路，主要是根据出现的dom更新情况做出判断条件来更新。

取新旧子节点的开始索引和结束索引以及对应索引虚拟对象。
通过while循环，条件是新旧子节点的任意一方的开始索引大于结束索引时退出while。while内部就是做一些条件判断（根据节点之间的判断结果）。改变指针的移动以及dom的更新。
1. 新旧开始指针往右一个，结束指针不变。（新头旧头对应）
1. 新旧结束指针往左一个，结束指针不变。（新尾旧尾对应）
2. 新开始指针往右一个，结束指针不变。旧结束指针往左一个，开始指针不变。（新头旧尾对应）
3. 新结束指针往左一个，开始指针不变。旧开始指针往右一个，结束指针不变。（新尾旧头对应）
1. 无规则（有两种情况）
  - 能复用
    - 通过映射表找到key对应的index，把该节点添加到oldStartVnode前。
  - 不能复用的
    - 直接添加到oldStartVnode前。
while循环跳出的条件是最短的队列。剩下需要判断新旧子节点多出的长度。新的比较长就添加反之删除。

function updateChildren(parent, oldChildren, newChildren) {
    let oldStartIndex = 0;
    let oldStartVnode = oldChildren[oldStartIndex];
    let oldEndIndex = oldChildren.length - 1;
    let oldEndVnode = oldChildren[oldEndIndex];

    let newStartIndex = 0;
    let newStartVnode = newChildren[newStartIndex];
    let newEndIndex = newChildren.length - 1;
    let newEndVnode = newChildren[newEndIndex];

    let keyIndexMap = createMapBykeyToIndex(oldChildren); //旧节点key-index映射表

    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        if (isSameNode(oldStartVnode, newStartVnode)) { //条件1
            patch(oldStartVnode, newStartVnode);//打补丁- 更新新旧的props
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
        } else if (isSameNode(oldEndVnode, newEndVnode)) { //条件2
            patch(oldEndVnode, newEndVnode);
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
        } else if (isSameNode(oldStartVnode, newEndVnode)) { //条件3
            patch(oldStartVnode, newEndVnode);
            parent.insertBefore(oldStartVnode.domElement, oldEndVnode.domElement.nextSiblings);
            oldStartVnode = oldChildren[++oldStartIndex];
            newEndVnode = newChildren[--newEndIndex];
        } else if (isSameNode(oldEndVnode, newStartVnode)) { //条件4
            patch(oldEndVnode, newStartVnode);
            parent.insertBefore(oldEndVnode.domElement, oldStartVnode.domElement);
            oldEndVnode = oldChildren[--oldEndIndex];
            newStartVnode = newChildren[++newStartIndex];
        } else {  //无规则对比 条件5
            let index = keyIndexMap[newStartVnode.key];
            if (index == null) {//没有复用的
                // 把虚拟dom转化为真实dom
                parent.insertBefore(createDomElementFrom(newStartVnode), oldStartVnode.domElement);
                newStartVnode = newChildren[++newStartIndex];
            } else {//有复用的
                patch(oldChildren[index], newStartVnode);
                parent.insertBefore(oldChildren[index].domElement, oldStartVnode.domElement);
                newStartVnode = newChildren[++newStartIndex];
                oldChildren[index] = undefined;
            }
        }
    }

    if (newStartIndex <= newEndIndex) {
        // 开始节点相同,多出结尾
        for (let index = newStartIndex; index <= newEndIndex; index++) {
            let beforeElement = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].domElement : null;
            // null插入 相当于appendChild 把虚拟dom转化为真实dom
            parent.insertBefore(createDomElementFrom(newChildren[index]), beforeElement);
        }
    } else if (oldStartIndex <= oldEndIndex) {
        // 老节点比较长,保留了以前的节点-需要删除
        for (let index = oldStartIndex; index <= oldEndIndex; index++) {
            let element = oldChildren[index]
            if (element) {
                parent.removeChild(element.domElement);
            }
        }
    }
}

// 创建映射表
function createMapBykeyToIndex(oldChildren) {
    let map = {};
    for (let index = 0; index < oldChildren.length; index++) {
        let element = oldChildren[index];
        if (element.key) {
            map[element.key] = index
        }
    }
    return map;
}
// 判断节点是否相同
function isSameNode(oleVnode, newVnode) {
    return oleVnode.type === newVnode.type && oleVnode.key === newVnode.key
}

简单的虚拟dom和dom更新时diff算法的应用基本已经完成。可以拿数据到浏览器测试了。

let oldVnode = createElement("div", { className: "xxx" },
                             createElement("li", { key: "A" }, "A"),
                             createElement("li", { key: "B" }, "B"),
                             createElement("li", { key: "C" }, "C"),
                             createElement("li", { key: "D" }, "D")
                            );
render(oldVnode, document.querySelector("#app"))
let newVnode = createElement("div", {},
                             createElement("li", { key: "A" }, "A"),
                             createElement("li", { key: "B" }, "B"),
                             createElement("li", { key: "C" }, "C"),
                             createElement("li", { key: "D", id: "ID" }, "D"),
                             createElement("li", { key: "E" }, "E"),
                            );
setTimeout(() => {
    patch(oldVnode, newVnode)
}, 2000);