我们都知道虚拟DOM本质上就是一个diff算法,我们需要拿到两棵树,一个目前的树,一颗未来的树,对比这两棵树,尽量找出他们的最小差异,然后替换这些差异,从而达到减少DOM操作的目的,那么在框架之中一个diff算法到底是如何实现的呢?

diff

我已经把绝大部分的感悟与解释都写到了注释中。

export function diff(dom, vnode, context, mountAll, parent, componentRoot) {
	// 如果第一次进行diff 进行初始化
	if (!diffLevel++) {
		isSvgMode = parent!=null && parent.ownerSVGElement!==undefined;

		hydrating = dom!=null && !(ATTR_KEY in dom);
	}

	let ret = idiff(dom, vnode, context, mountAll, componentRoot);

	// 如果目标父节点变更 重新插入
	if (parent && ret.parentNode!==parent) parent.appendChild(ret);

	if (!--diffLevel) {
		hydrating = false;
		if (!componentRoot) flushMounts();
	}

	return ret;
}


/** diff的核心 主要进行diff对比以及替换 触发生命周期 */
function idiff(dom, vnode, context, mountAll, componentRoot) {
	let out = dom,
		prevSvgMode = isSvgMode;

	if (vnode==null || typeof vnode==='boolean') vnode = '';


	// 最快的情况,Vnode是一个简单的值,替换到原节点之中
	if (typeof vnode==='string' || typeof vnode==='number') {

		// 如果原DOM是文本节点,直接替换nodevalue
		if (dom && dom.splitText!==undefined && dom.parentNode && (!dom._component || componentRoot)) {
			/* istanbul ignore if */ /* Browser quirk that can't be covered: https://github.com/developit/preact/commit/fd4f21f5c45dfd75151bd27b4c217d8003aa5eb9 */
			if (dom.nodeValue!=vnode) {
				dom.nodeValue = vnode;
			}
		}
		else {
			// 如果原DOM并非文本节点,需要手动创建并替换原DOM 并退休一下原DOM
			out = document.createTextNode(vnode);
			if (dom) {
				if (dom.parentNode) dom.parentNode.replaceChild(out, dom);
				recollectNodeTree(dom, true);
			}
		}

		out[ATTR_KEY] = true;

		return out;
	}


	// 如果VNode是函数,则返回一个从Vnode映射而来的组件对象
	let vnodeName = vnode.nodeName;
	if (typeof vnodeName==='function') {
		return buildComponentFromVNode(dom, vnode, context, mountAll);
	}


	isSvgMode = vnodeName==='svg' ? true : vnodeName==='foreignObject' ? false : isSvgMode;


	// 如果原树不合法或者新树需要替换原树,让新树直接替换原树,但保留原树的子元素 以供继续对比 @@第一种主要替换 即相对应的两个节点nodeName不一致
	vnodeName = String(vnodeName);
	if (!dom || !isNamedNode(dom, vnodeName)) {
		out = createNode(vnodeName, isSvgMode);

		if (dom) {
			// 把原树的子元素移动到out中
			while (dom.firstChild) out.appendChild(dom.firstChild);

			// 如果原树有父元素,替换
			if (dom.parentNode) dom.parentNode.replaceChild(out, dom);

			// 让老组件退休,触发生命周期,删除它
			recollectNodeTree(dom, true);
		}
	}


	let fc = out.firstChild,
		props = out[ATTR_KEY],
		vchildren = vnode.children;

	if (props==null) {
		props = out[ATTR_KEY] = {};
		for (let a=out.attributes, i=a.length; i--; ) props[a[i].name] = a[i].value;
	}

	// 最快情况,两棵树相比只是文本节点的变更 替换他们 @@ 第二种主要替换,文本的内容不同
	if (!hydrating && vchildren && vchildren.length===1 && typeof vchildren[0]==='string' && fc!=null && fc.splitText!==undefined && fc.nextSibling==null) {
		if (fc.nodeValue!=vchildren[0]) {
			fc.nodeValue = vchildren[0];
		}
	}
	// 否则:进行Diff算法
	else if (vchildren && vchildren.length || fc!=null) {
		innerDiffNode(out, vchildren, context, mountAll, hydrating || props.dangerouslySetInnerHTML!=null);
	}


	// 对比并更新他们的属性
	diffAttributes(out, vnode.attributes, props);


	isSvgMode = prevSvgMode;

	return out;
}


/** Apply child and attribute changes between a VNode and a DOM Node to the DOM.
 *	@param {Element} dom			Element whose children should be compared & mutated
 *	@param {Array} vchildren		Array of VNodes to compare to `dom.childNodes`
 *	@param {Object} context			Implicitly descendant context object (from most recent `getChildContext()`)
 *	@param {Boolean} mountAll
 *	@param {Boolean} isHydrating	If `true`, consumes externally created elements similar to hydration
 */
function innerDiffNode(dom, vchildren, context, mountAll, isHydrating) {
	let originalChildren = dom.childNodes,
		children = [],
		keyed = {},
		keyedLen = 0,
		min = 0,
		len = originalChildren.length,
		childrenLen = 0,
		vlen = vchildren ? vchildren.length : 0,
		j, c, f, vchild, child;

	// 建造一个key 和 chidren的表 用来建立和新节点树之间的联系
	if (len!==0) {
		for (let i=0; i<len; i++) {
			let child = originalChildren[i],
				props = child[ATTR_KEY],
				key = vlen && props ? child._component ? child._component.__key : props.key : null;
			if (key!=null) {
				keyedLen++;
				keyed[key] = child;
			}
			else if (props || (child.splitText!==undefined ? (isHydrating ? child.nodeValue.trim() : true) : isHydrating)) {
				children[childrenLen++] = child;
			}
		}
	}

	if (vlen!==0) {
		for (let i=0; i<vlen; i++) {
			vchild = vchildren[i];
			child = null;

			// 如果具有key 通过key来找到两个对应的 需要比较的节点
			let key = vchild.key;
			if (key!=null) {
				if (keyedLen && keyed[key]!==undefined) {
					child = keyed[key];
					keyed[key] = undefined;
					keyedLen--;
				}
			}
			// 没有key 就通过nodeType来找到对应关系
			else if (!child && min<childrenLen) {
				for (j=min; j<childrenLen; j++) {
					if (children[j]!==undefined && isSameNodeType(c = children[j], vchild, isHydrating)) {
						child = c;
						children[j] = undefined;
						if (j===childrenLen-1) childrenLen--;
						if (j===min) min++;
						break;
					}
				}
			}

			// 递归调用,继续比较这两颗子树,有可能直接替换,也有可能很相似,会继续diff递归 返回一棵更新后的DOM树
			child = idiff(child, vchild, context, mountAll);
			
			// 收尾工作,测试差异 并更新DOM  注意 Node 是一种动态的引用
			f = originalChildren[i];
			if (child && child!==dom && child!==f) {
				if (f==null) { // 原来的节点被删除
					dom.appendChild(child);
				} 
				else if (child===f.nextSibling) {
					removeNode(f);
				}
				else {
					dom.insertBefore(child, f);
				}
			}
		}
	}


	// 删除多余的有key的原树子节点
	if (keyedLen) {
		for (let i in keyed) if (keyed[i]!==undefined) recollectNodeTree(keyed[i], false);
	}

	// 删除多余的无Key的原子树节点
	while (min<=childrenLen) {
		if ((child = children[childrenLen--])!==undefined) recollectNodeTree(child, false);
	}
}

这个diff算法与我之前的想象有很大的差异,我原本所想的diff算法应该是比较两颗虚拟DOM树,然后建立一个差异表,对表进行查询,然后找到差异点进行DOM更新,但在实际查看和思考之后,却发现这些框架的diff实现绝对是最高效的,因为他把diff判断和DOM操作融合到同一时间进行,这将非常大的减少不必要的时间。

他的本质是一棵真实DOM树与Vnode节点树的diff,从而更新真实DOM树,在这其中还会顺便出触发一些组件的生命周期函数。他的算法是一个深度优先的递归算法。

那么,我们已经了解diff函数如何运行,他又是如何被触发的呢,谁来交给diff参数呢? 这就要涉及到MVVC另外的一个重要概念 组件