简单diff算法

从本章开始，我们将介绍渲染器的核心Diff算法。简单来说，当新旧vnode的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫作Diff算法。我们知道，操作DOM的性能开销通常比较大，而渲染器的核心Diff算法就是为了解决这个问题而诞生的。

减少DOM操作的性能开销

上一章中，当新旧子节点都是一组节点时，我们采用简单粗暴的方式（直接全部卸载旧节点，再挂载新节点）来处理，这会产生极大的性能开销。

以下面的新旧虚拟节点为例：

let oldVnode = {
    type: 'div',
    children: [{
        type: 'p',
        children: 'p1'
    }, {
        type: 'p',
        children: 'p2'
    }, {
        type: 'p',
        children: 'p3'
    }]
}
let newVnode = {
    type: 'div',
    children: [{
        type: 'p',
        children: 'p3'
    }, {
        type: 'p',
        children: 'p4'
    }, {
        type: 'p',
        children: 'p5'
    }]
}

按照之前的做法，会执行6次DOM操作：

• 卸载旧节点，需要进行3次DOM删除操作
• 挂载新节点，需要进行3次DOM添加操作

但我们其实可以观察到，新子节点只是更新了p标签的文本。所以，最理想的更新方式是，直接更新p标签的文本，这样一共只需要进行3次DOM操作。

function patchChildren(n1, n2, container) {
    // 文本子节点
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        // 一组子节点
        if (Array.isArray(n1.children)) {
            // TODO:diff算法
            const oldChildren = n1.children
            const newChildren = n2.children
            const oldLen = oldChildren.length
            const newLen = newChildren.length
            const commonLength = Math.min(oldLen, newLen)
            for (let i = 0; i < commonLength; i++) {
                // 更新
                patch(oldChildren[i], newChildren[i], container)
            }
            // 卸载
            if (newLen < oldLen) {
                for (let i = commonLength; i < oldLen; i++) {
                    unmount(oldChildren[i])
                }
            } else if (newLen > oldLen) {
                // 挂载
                for (let i = commonLength; i < newLen; i++) {
                    patch(null, newChildren[i], container)
                }
            }
        } else {
            // 清空文本
            setElementText(container, '')
            // 挂载新的一组节点
            n2.children.forEach(vnode => patch(null, vnode, container))
        }
    } else if (!n2.children) {
        // 没有子节点
        // ...
    }
}

DOM复用与key的作用

上一节中，我们减少了DOM的操作次数，提升了性能。但仍然有优化空间。假设以下两组新旧子节点：

let oldVnode = {
	type: 'div',
	props: {
		id: 'test',
	},
	children: [
		{
			type: 'p',
			children: '1',
		},
		{
			type: 'span',
			children: '2',
		},
		{
			type: 'div',
			children: '3',
		},
	],
}
let newVnode = {
	type: 'div',
	props: {
		id: 'test',
	},
	children: [
		{
			type: 'span',
			children: '2',
		},
		{
			type: 'div',
			children: '3',
		},
        {
			type: 'p',
			children: '1',
		},
	],
}

如果按照上一节方式处理，则需要操作6次DOM。

• 卸载旧的一组子节点中p节点,挂载新的一组子节点中span节点
• 卸载旧的一组子节点中span节点,挂载新的一组子节点中div节点
• 卸载旧的一组子节点中div节点,挂载新的一组子节点中p节点

但是，观察上述两组新旧子节点，发现只是顺序变了。所以最优的处理方式是，通过DOM的移动来完成子节点的更新，这比不断卸载和挂载的性能更好。但是，想要通过DOM的移动来完成更新，必须要保证一个前提：新旧两组子节点中的确存在可复用的节点。这是key就衍生出来了。

let oldVnode = {
	type: 'div',
	props: {
		id: 'test',
	},
	children: [
		{
			type: 'p',
			children: '1',
			key: 1,
		},
		{
			type: 'span',
			children: '2',
			key: 2,
		},
		{
			type: 'div',
			children: '3',
			key: 3,
		},
	],
}
let newVnode = {
	type: 'div',
	props: {
		id: 'test',
	},
	children: [
		{
			type: 'span',
			children: '2',
			key: 2,
		},
		{
			type: 'div',
			children: '3',
			key: 3,
		},
        {
			type: 'p',
			children: '1',
			key: 1,
		},
	],
}
function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        if (Array.isArray(n2.children)) {
            const oldChildren = n1.children
			const newChildren = n2.children
            for (let i = 0; i < newChildren.length; i++) {
				const newVNode = newChildren[i]
                for (let j = 0; j < oldChildren.length; j++) {
                    const oldVNode = oldChildren[j]
                    if (newVNode.key === oldVNode.key) {
                        // 找到可复用的节点，仍然需要调用patch函数更新，以防节点的子节点变更
						patch(oldVNode, newVNode, container)
                        break
                    }
                }
            }
        } else {
            // ...
        }
    } else if (!n2.children) {
        // ...
    }
}

经过上述更新操作后，所有节点对应的真实DOM元素都更新完毕了。但真实DOM仍然保持旧的一组子节点的顺序，因此我们还需要通过移动节点来完成真实DOM顺序的更新。

找到需要移动的元素

如何判断一个节点是否需要移动，以及如何移动。我们采用逆向思维，先想一想什么情况下节点不需要移动？答案很简单，当新旧两组子节点的顺序不变时，即当可复用的节点在旧的一组子节点中的位置索引是一个递增的序列，就不需要移动,反之，则需要移动。

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        if (Array.isArray(n2.children)) {
            const oldChildren = n1.children
			const newChildren = n2.children
            let maxIndex = 0
            for (let i = 0; i < newChildren.length; i++) {
				const newVNode = newChildren[i]
                for (let j = 0; j < oldChildren.length; j++) {
                    const oldVNode = oldChildren[j]
                    if (newVNode.key === oldVNode.key) {
                        // 找到可复用的节点，仍然需要调用patch函数更新，以防节点的子节点变更
						patch(oldVNode, newVNode, container)
                        if (j < maxIndex) {
                            // 非递增，说明newVNode对应的真实DOM需要移动
                            // TODO:移动元素..                            
                        } else {
                            // 递增，不需要移动，保证maxIndex为当前最大索引值
                            maxIndex = j
                        }
                        break
                    }
                }
            }
        } else {
            // ...
        }
    } else if (!n2.children) {
        // ...
    }
}

如何移动元素

上一节中我们找到了需要移动的元素，这里开始移动真实DOM。

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        if (Array.isArray(n2.children)) {
            const oldChildren = n1.children
			const newChildren = n2.children
            let maxIndex = 0
            for (let i = 0; i < newChildren.length; i++) {
				const newVNode = newChildren[i]
                for (let j = 0; j < oldChildren.length; j++) {
                    const oldVNode = oldChildren[j]
                    if (newVNode.key === oldVNode.key) {
                        // 找到可复用的节点，仍然需要调用patch函数更新，以防节点的子节点变更
						patch(oldVNode, newVNode, container)
                        if (j < maxIndex) {
                            // 非递增，说明newVNode对应的真实DOM需要移动
                            // 找到需要移动节点的前一个虚拟节点prevVNode
                            const prevVNode = newChildren[i - 1]
                            // 如果prevVNode不存在，则说明当前newVNode是第一个节点，不需要移动
                            if (prevVNode) {
                                // 获取prevVNode对应真实DOM的下一个兄弟节点，并将其作为锚点
                                const anchor = prevVNode.el.nextSibling
                                // 将newVNode对应的真实DOM插入到锚点元素的前面，也就是prevVNode对应的真实DOM的后面
                                insert(newVNode.el, container, anchor)
                            }                        
                        } else {
                            // 递增，不需要移动，保证maxIndex为当前最大索引值
                            maxIndex = j
                        }
                        break
                    }
                }
            }
        } else {
            // ...
        }
    } else if (!n2.children) {
        // ...
    }
}

添加新元素

本节我们将讨论添加新节点的情况。

let newVNode = {
    type: 'div',
    children: [
        { // 新的子节点
            type: 'div',
            children: '444',
            key: 4,
        },
        {
            type: 'span',
            children: '222',
            key: 2,
        },
        {
            type: 'div',
            children: '3333',
            key: 3,
        },
        {
            type: 'p',
            children: '1111',
            key: 1,
        },
    ],
}

对于新增的节点，在更新时我们应该正确的将它挂载，这主要分为两步：

• 找到新增的节点
• 将新增节点挂载到正确的位置

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        if (Array.isArray(n2.children)) {
            const oldChildren = n1.children
			const newChildren = n2.children
            let maxIndex = 0
            for (let i = 0; i < newChildren.length; i++) {
				const newVNode = newChildren[i]
                let find = false
                for (let j = 0; j < oldChildren.length; j++) {
                    const oldVNode = oldChildren[j]
                    if (newVNode.key === oldVNode.key) {
                        find = true
                        // 找到可复用的节点，仍然需要调用patch函数更新，以防节点的子节点变更
						patch(oldVNode, newVNode, container)
                        if (j < maxIndex) {
                            // 非递增，说明newVNode对应的真实DOM需要移动
                            // 找到需要移动节点的前一个虚拟节点prevVNode
                            const prevVNode = newChildren[i - 1]
                            // 如果prevVNode不存在，则说明当前newVNode是第一个节点，不需要移动
                            if (prevVNode) {
                                // 获取prevVNode对应真实DOM的下一个兄弟节点，并将其作为锚点
                                const anchor = prevVNode.el.nextSibling
                                // 将newVNode对应的真实DOM插入到锚点元素的前面，也就是prevVNode对应的真实DOM的后面
                                insert(newVNode.el, container, anchor)
                            }                        
                        } else {
                            // 递增，不需要移动，保证maxIndex为当前最大索引值
                            maxIndex = j
                        }
                        break
                    }
                }
                // 在一组旧节点中，没有找到可复用的新子节点，则挂载
                if(!find) {
                    // 找到锚点位置
                    let anchor = null
                    const prevVNode = newChildren[i - 1]
                    if (prevVNode) {
                        anchor = prevVNode.el.nextSibling
                    } else {
                        anchor = container.firstChild
                    }
                    // 挂载新节点
                    patch(null, newVNode, container, anchor)
                }
            }
        } else {
            // ...
        }
    } else if (!n2.children) {
        // ...
    }
}

移除不存在的元素

本节我们将讨论移除节点的情况。

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
        // ...
    } else if (Array.isArray(n2.children)) {
        if (Array.isArray(n2.children)) {
            const oldChildren = n1.children
			const newChildren = n2.children
            let maxIndex = 0
            for (let i = 0; i < newChildren.length; i++) {
				const newVNode = newChildren[i]
                let find = false
                for (let j = 0; j < oldChildren.length; j++) {
                    const oldVNode = oldChildren[j]
                    if (newVNode.key === oldVNode.key) {
                        find = true
                        // 找到可复用的节点，仍然需要调用patch函数更新，以防节点的子节点变更
						patch(oldVNode, newVNode, container)
                        if (j < maxIndex) {
                            // 非递增，说明newVNode对应的真实DOM需要移动
                            // 找到需要移动节点的前一个虚拟节点prevVNode
                            const prevVNode = newChildren[i - 1]
                            // 如果prevVNode不存在，则说明当前newVNode是第一个节点，不需要移动
                            if (prevVNode) {
                                // 获取prevVNode对应真实DOM的下一个兄弟节点，并将其作为锚点
                                const anchor = prevVNode.el.nextSibling
                                // 将newVNode对应的真实DOM插入到锚点元素的前面，也就是prevVNode对应的真实DOM的后面
                                insert(newVNode.el, container, anchor)
                            }                        
                        } else {
                            // 递增，不需要移动，保证maxIndex为当前最大索引值
                            maxIndex = j
                        }
                        break
                    }
                }
                // 在一组旧节点中，没有找到可复用的新子节点，则挂载
                if(!find) {
                    // 找到锚点位置
                    let anchor = null
                    const prevVNode = newChildren[i - 1]
                    if (prevVNode) {
                        anchor = prevVNode.el.nextSibling
                    } else {
                        anchor = container.firstChild
                    }
                    // 挂载新节点
                    patch(null, newVNode, container, anchor)
                }
            }
            // 卸载不存在与新的一组字节中中的旧的子节点
            for (let i = 0; i < oldChildren.length; i++) {
                const has = newChildren.find(vnode => vnode.key === oldChildren[i].key)
                !has && unmount(oldChildren[i])
            }
        } else {
            // ...
        }
    } else if (!n2.children) {
        // ...
    }
}