小白的diff算法试试水之旅0.前言1. 主角1：Element构造函数2. 主角2：render函数3. 大主角： diff函数4. 更新5. 完成

lhyt

发布于 2018-10-31 16:00:42

4280

发布于 2018-10-31 16:00:42

文章被收录于专栏：lhyt前端之路

0.前言

“孩子，你会唱diff算法吗”

“twinkle，twinkle，diff start”

1. 主角1：Element构造函数

先介绍一下虚拟dom的数据结构，我们都知道源码里面有createElement函数，通过他创建虚拟dom，然后调用render函数。还记得VUE脚手架住入口文件那句足够装逼的h=>h(App)吗，其实就是类似createElement(App)这样子的过程。我们看一下他简单的结构：

createElement('ul',{class:'ul'},[
		createElement('li',{class:'li'},['1']),
		createElement('li',{class:'li'},['2'])
	])
复制代码

createElement (type, props, children)传入三个参数，节点类型、属性集合、子节点集合

function Element(type, props, children) {
		this.type = type
		this.props = props
		this.children = children || []
}

function createElement (type, props, children) {
	return new Element(type, props, children)
}
复制代码

复制代码，自己造两个节点打印一下，在控制台观察一下。

2. 主角2：render函数

这个就是把虚拟dom转化为真正的dom的函数。vue里面把虚拟节点叫做vnode，那我们翻版，也要翻版得像一点才行：

function render (vnode) {
	let el = document.createElement(vnode.type)//创建html元素
	for(let key in vnode.props){//遍历虚拟dom的属性集合，给新建的html元素加上
		el.setAttribute(key, vnode.props[key])
	}
	vnode.children&&vnode.children.forEach(child=>{//递归子节点，如果是文本节点则直接插入
			child = (child instanceof Element) ? 
			render(child)://不是文本节点，则递归render
			document.createTextNode(child)
			el.appendChild(child)
		})
	return el
}
复制代码

这个是真正的dom喔，是不是饥渴难耐了，那好，可以试一下document.body.appendChild(el)，看见新节点没

3. 大主角： diff函数

都虚拟dom了，还不diff干啥呢。

function  diff (oldTree, newTree) {
	const patches = {}//差异表记录差异，这个记录一个树的所有差异
	let index = 0//记录开始索引，我们给节点编号用的
	dfswalk(oldTree, newTree, index, patches)//先序深度优先遍历，涉及到树的遍历，这是必须的
	return patches
}

//老节点、新节点、第几个节点、差异表
function dfswalk (oldNode, newNode, index, patches) {
	const currentPatch = []
	//...一系列写入差异的过程
	//最后将当前差异数组写入差异表
	currentPatch.length && (patches[index] = currentPatch)
}
复制代码

3.1 结果预想

我们要的最终结果，大概是旧节点根据patches来变成新节点，最终结果的基本雏形：

let el =  render(vnode)//老的虚拟dom树生成老html节点
document.body.appendChild(el) //挂载dom节点
let patches =  diff(vnode,newvnode) //对虚拟dom进行diff得到差异表
update (el, patches) //老节点根据差异表更新，这个函数包括了dom操作
复制代码

3.2 深度优先搜索

我们现在要开始完善dfs内部的逻辑

考虑几种情况：

两个节点类型一样，那我们应该对比他的属性和子节点（ATTR）
两个节点类型不一样，我们把他视为被替换（REPLACE）
两个节点都是文本节点，直接用等号比吧（TEXT）
节点被删除（DELETE）

function dfswalk (oldNode, newNode, index, patches) {
	const currentPatch = []
	if(!newNode){//判断节点是否被删除，记录被删的index
		currentPatch.push({type: 'REMOVE',index})
	}else if(typeof oldNode === 'string' && typeof newNode === 'string'){//处理文本节点
		if(oldNode !== newNode){
			currentPatch.push({type: 'TEXT',text:newNode})
		}
	}else if(oldNode.type === newNode.type){//如果节点类型相同
		//对比属性
		let patch = props_diff(oldNode.props, newNode.props)
		//如果属性有差异则写入当前的差异数组
		Object.keys(patch).length && (currentPatch.push({type: 'ATTR',patch}))
		//对比子节点
		children_diff(oldNode.children, newNode.children, index, patches)
	}else{//节点类型不同
		currentPatch.push({type: 'REPLACE',newNode})
	}
	//将当前差异数组写入差异表
	currentPatch.length && (patches[index] = currentPatch)
}
复制代码

对比属性：

我们传入新节点和老节点的属性集合，进行遍历

function props_diff(oldProp, newProp){
	const patch = {}
	//判断新老属性的差别
	for(let k in oldProp){
		//如果属性不同，写入patch，老属性有，新属性没有或者不同，写入差异表
		oldProp[k] !== newProp[k] && (patch[k] = newProp[k])
	}
	//新节点新属性
	for(let k in newProp){
		//判断老节点的属性在新节点里面是否存在，没有就写入patch
		!oldProp.hasOwnProperty(k) && (patch[k] = newProp[k])
	}	
	return patch
}
复制代码

对比子节点：

let allIndex = 0
function children_diff (oldChildren, newChildren, index, patches) {
	//对每一个子节点深度优先遍历
	oldChildren&&oldChildren.forEach((child,i)=>{
		//allIndex在每一次进dfs的时候要加一，作为唯一key。注意这个是全局的、共有的allIndex，表示节点树的哪一个节点，0是根节点，子节点再走一遍dfs
		dfswalk(child, newChildren[i], ++allIndex, patches)
	})
}
复制代码

4. 更新

前面我们已经大概构思了一个最终雏形：update (el, patches)，我们顺着这条路开始吧

let allPatches //全局存放差异表
//这里是真的html元素喔，接下来是dom操作了
function update (HTMLNode, patches) {//根据差异表更新html元素，vnode转换为真正的节点
	allPatches = patches
	htmlwalk(HTMLNode)//遍历节点，最开始从第一个节点遍历
}
复制代码

let Index = 0//索引从第一个节点开始，同上面的allIndex一样的道理，全局标记
function htmlwalk (HTMLNode) {
	const currentPatch = allPatches[Index++]//遍历一个节点，就下一个节点
	const childNodes = HTMLNode.childNodes
	//有子节点就后序深度优先遍历
	childNodes && childNodes.forEach(node=>{
		htmlwalk (node)
	})
	//对当前的差异数组进行遍历，根据差异还原元素
	currentPatch && currentPatch.length && currentPatch.forEach(patch=>{
		doPatch(HTMLNode, patch)//根据差异还原
	})
}
复制代码

差异还原：

function doPatch (node, patch) {//还原过程，其实就是dom操作
	switch (patch.type) {
		case 'REMOVE' ://熟悉的删除节点操作
		node.parentNode.removeChild(node)
		break
		case 'TEXT' ://熟悉的textContent
		node.textContent = patch.text
		break
		case 'ATTR' :
		for(let k in patch.patch){//熟悉的setAttribute
			const v = patch.patch[k]
			if(v){
				node.setAttribute(k, v)
			}else{
				node.removeAttribute(k)
			}
		}
		break
		case 'REPLACE' ://如果是元素节点，用render渲染出来替换掉。如果是文本，自己新建一个
		const newNode = (patch.newNode instanceof Element) ?
		render(patch.newNode) : document.createTextNode(patch.newNode)
		node.parentNode.replaceChild(newNode, node)
		break						
	}
}
复制代码

5. 完成

已经完成了，我们试一下吧：

//随便命名的，就别计较了
//创建虚拟dom
var v = createElement('ul',{class:'ul'},[
		createElement('li',{class:'li'},['a']),
		createElement('li',{class:'li1'},['b']),
		createElement('li',{class:'a'},['c'])
	])
//dom diff
var d = diff(v,createElement('ul',{class:'ul'},[
		createElement('li',{class:'li'},['aaaaaaaaaaa']),
		createElement('div',{class:'li'},['b']),
                createElement('li',{class:'li'},['b'])
	]))
//vnode渲染成真正的dom
var el =  render(v)
//挂载dom
document.body.appendChild(el)
//diff后更新dom
update (el, d)
复制代码

全部代码：（希望大家别来这里复制，一步步看下来自己做一遍是最好的）

function Element(type, props, children) {
		this.type = type
		this.props = props
		this.children = children || []
}

function createElement (type, props, children) {
	return new Element(type, props, children)
}
//将vnode转化为真正的dom
function render (vnode) {
	let el = document.createElement(vnode.type)
	for(let key in vnode.props){
		el.setAttribute(key, vnode.props[key])
	}
	vnode.children&&vnode.children.forEach(child=>{//递归节点，如果是文本节点则直接插入
			child = (child instanceof Element) ? 
			render(child):
			document.createTextNode(child)
			el.appendChild(child)
		})
	return el
}
let allIndex = 0

function  diff (oldTree, newTree) {
	const patches = {}//差异表记录差异
	let index = 0//记录开始索引
	dfswalk(oldTree, newTree, index, patches)//先序深度优先遍历
	return patches
}

function dfswalk (oldNode, newNode, index, patches) {
	const currentPatch = []
	if(!newNode){//判断节点是否被删除，记录被删的index
		currentPatch.push({type: 'REMOVE',index})
	}else if(typeof oldNode === 'string' && typeof newNode === 'string'){//处理文本节点
		if(oldNode !== newNode){
			currentPatch.push({type: 'TEXT',text:newNode})
		}
	}else if(oldNode.type === newNode.type){//如果节点类型相同
		//对比属性
		let patch = props_diff(oldNode.props, newNode.props)
		//如果属性有差异则写入当前的差异数组
		Object.keys(patch).length && (currentPatch.push({type: 'ATTR',patch}))
		//对比子节点
		children_diff(oldNode.children, newNode.children, index, patches)
	}else{//节点类型不同
		currentPatch.push({type: 'REPLACE',newNode})
	}
	//将当前差异数组写入差异表
	currentPatch.length && (patches[index] = currentPatch)
}

function children_diff (oldChildren, newChildren, index, patches) {
	//对每一个子节点深度优先遍历
	oldChildren.forEach((child,i)=>{
		//index在每一次进dfs的时候要加一，作为唯一key
		dfswalk(child, newChildren[i], ++allIndex, patches)
	})
}

function props_diff(oldProp, newProp){
	const patch = {}
	//判断新老属性的差别
	for(let k in oldProp){
		//如果属性不同，写入patch
		oldProp[k] !== newProp[k] && (patch[k] = newProp[k])
	}
	//新节点新属性
	for(let k in newProp){
		//判断老节点的属性在新节点里面是否存在，没有就写入patch
		!oldProp.hasOwnProperty(k) && (patch[k] = newProp[k])
	}	
	return patch
}

let allPatches//根据差异还原dom，记录差异表
let Index = 0//索引从第一个节点开始
function update (HTMLNode, patches) {//根据差异表更新html元素，vnode转换为真正的节点
	allPatches = patches
	htmlwalk(HTMLNode)//遍历节点，最开始从第一个节点遍历
}

function htmlwalk (HTMLNode) {
	const currentPatch = allPatches[Index++]//遍历一个节点，就下一个节点
	const childNodes = HTMLNode.childNodes
	//有子节点就后序dfs
	childNodes && childNodes.forEach(node=>{
		htmlwalk (node)
	})
	//对当前的差异数组进行遍历，根据差异还原元素
	currentPatch && currentPatch.length && currentPatch.forEach(patch=>{
		doPatch(HTMLNode, patch)
	})
}

function doPatch (node, patch) {
	switch (patch.type) {
		case 'REMOVE' :
		node.parentNode.removeChild(node)
		break
		case 'TEXT' :
		node.textContent = patch.text
		break
		case 'ATTR' :
		for(let k in patch.patch){
			const v = patch.patch[k]
			if(v){
				node.setAttribute(k, v)
			}else{
				node.removeAttribute(k)
			}
		}
		break
		case 'REPLACE' :
		const newNode = (patch.newNode instanceof Element) ?
		render(patch.newNode) : document.createTextNode(patch.newNode)
		node.parentNode.replaceChild(newNode, node)
		break						
	}
}
复制代码

过程差不多是这样子的。我写的有很多bug，别吐槽了，我懂，以后会更新的

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年06月13日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度