blog
blog copied to clipboard
hujiulong
从零开始实现一个React（三）：diff算法
前言
在上一篇文章，我们已经实现了React的组件功能，从功能的角度来说已经实现了React的核心功能了。
但是我们的实现方式有很大的问题：每次更新都重新渲染整个应用或者整个组件，DOM操作十分昂贵，这样性能损耗非常大。
为了减少DOM更新，我们需要找渲染前后真正变化的部分，只更新这一部分DOM。而对比变化，找出需要更新部分的算法我们称之为diff算法。
对比策略
在前面两篇文章后，我们实现了一个render方法，它能将虚拟DOM渲染成真正的DOM，我们现在就需要改进它，让它不要再傻乎乎地重新渲染整个DOM树，而是找出真正变化的部分。
这部分很多类React框架实现方式都不太一样，有的框架会选择保存上次渲染的虚拟DOM，然后对比虚拟DOM前后的变化，得到一系列更新的数据，然后再将这些更新应用到真正的DOM上。
但也有一些框架会选择直接对比虚拟DOM和真实DOM，这样就不需要额外保存上一次渲染的虚拟DOM，并且能够一边对比一边更新，这也是我们选择的方式。
不管是DOM还是虚拟DOM，它们的结构都是一棵树，完全对比两棵树变化的算法时间复杂度是O(n^3)，但是考虑到我们很少会跨层级移动DOM，所以我们只需要对比同一层级的变化。
只需要对比同一颜色框内的节点
总而言之，我们的diff算法有两个原则：
- 对比当前真实的DOM和虚拟DOM，在对比过程中直接更新真实DOM
- 只对比同一层级的变化
实现
我们需要实现一个diff方法，它的作用是对比真实DOM和虚拟DOM，最后返回更新后的DOM
/**
* @param {HTMLElement} dom 真实DOM
* @param {vnode} vnode 虚拟DOM
* @returns {HTMLElement} 更新后的DOM
*/
function diff( dom, vnode ) {
// ...
}
接下来就要实现这个方法。 在这之前先来回忆一下我们虚拟DOM的结构: 虚拟DOM的结构可以分为三种，分别表示文本、原生DOM节点以及组件。
// 原生DOM节点的vnode
{
tag: 'div',
attrs: {
className: 'container'
},
children: []
}
// 文本节点的vnode
"hello,world"
// 组件的vnode
{
tag: ComponentConstrucotr,
attrs: {
className: 'container'
},
children: []
}
对比文本节点
首先考虑最简单的文本节点，如果当前的DOM就是文本节点，则直接更新内容，否则就新建一个文本节点，并移除掉原来的DOM。
// diff text node
if ( typeof vnode === 'string' ) {
// 如果当前的DOM就是文本节点，则直接更新内容
if ( dom && dom.nodeType === 3 ) { // nodeType: https://developer.mozilla.org/zh-CN/docs/Web/API/Node/nodeType
if ( dom.textContent !== vnode ) {
dom.textContent = vnode;
}
// 如果DOM不是文本节点，则新建一个文本节点DOM，并移除掉原来的
} else {
out = document.createTextNode( vnode );
if ( dom && dom.parentNode ) {
dom.parentNode.replaceChild( out, dom );
}
}
return out;
}
文本节点十分简单，它没有属性，也没有子元素，所以这一步结束后就可以直接返回结果了。
对比非文本DOM节点
如果vnode表示的是一个非文本的DOM节点，那就要分两种情况了： 情况一：如果真实DOM不存在，表示此节点是新增的，或者新旧两个节点的类型不一样，那么就新建一个DOM元素，并将原来的子节点（如果有的话）移动到新建的DOM节点下。
if ( !dom || dom.nodeName.toLowerCase() !== vnode.tag.toLowerCase() ) {
out = document.createElement( vnode.tag );
if ( dom ) {
[ ...dom.childNodes ].map( out.appendChild ); // 将原来的子节点移到新节点下
if ( dom.parentNode ) {
dom.parentNode.replaceChild( out, dom ); // 移除掉原来的DOM对象
}
}
}
情况二：如果真实DOM存在，并且和虚拟DOM是同一类型的，那我们暂时不需要做别的，只需要等待后面对比属性和对比子节点。
对比属性
实际上diff算法不仅仅是找出节点类型的变化，它还要找出来节点的属性以及事件监听的变化。我们将对比属性单独拿出来作为一个方法：
function diffAttributes( dom, vnode ) {
const old = {}; // 当前DOM的属性
const attrs = vnode.attrs; // 虚拟DOM的属性
for ( let i = 0 ; i < dom.attributes.length; i++ ) {
const attr = dom.attributes[ i ];
old[ attr.name ] = attr.value;
}
// 如果原来的属性不在新的属性当中，则将其移除掉（属性值设为undefined）
for ( let name in old ) {
if ( !( name in attrs ) ) {
setAttribute( dom, name, undefined );
}
}
// 更新新的属性值
for ( let name in attrs ) {
if ( old[ name ] !== attrs[ name ] ) {
setAttribute( dom, name, attrs[ name ] );
}
}
}
setAttribute方法的实现参见第一篇文章
对比子节点
节点本身对比完成了，接下来就是对比它的子节点。 这里会面临一个问题，前面我们实现的不同diff方法，都是明确知道哪一个真实DOM和虚拟DOM对比，但是子节点是一个数组，它们可能改变了顺序，或者数量有所变化，我们很难确定要和虚拟DOM对比的是哪一个。 为了简化逻辑，我们可以让用户提供一些线索：给节点设一个key值，重新渲染时对比key值相同的节点。
// diff方法
if ( vnode.children && vnode.children.length > 0 || ( out.childNodes && out.childNodes.length > 0 ) ) {
diffChildren( out, vnode.children );
}
function diffChildren( dom, vchildren ) {
const domChildren = dom.childNodes;
const children = [];
const keyed = {};
// 将有key的节点和没有key的节点分开
if ( domChildren.length > 0 ) {
for ( let i = 0; i < domChildren.length; i++ ) {
const child = domChildren[ i ];
const key = child.key;
if ( key ) {
keyed[ key ] = child;
} else {
children.push( child );
}
}
}
if ( vchildren && vchildren.length > 0 ) {
let min = 0;
let childrenLen = children.length;
for ( let i = 0; i < vchildren.length; i++ ) {
const vchild = vchildren[ i ];
const key = vchild.key;
let child;
// 如果有key，找到对应key值的节点
if ( key ) {
if ( keyed[ key ] ) {
child = keyed[ key ];
keyed[ key ] = undefined;
}
// 如果没有key，则优先找类型相同的节点
} else if ( min < childrenLen ) {
for ( let j = min; j < childrenLen; j++ ) {
let c = children[ j ];
if ( c && isSameNodeType( c, vchild ) ) {
child = c;
children[ j ] = undefined;
if ( j === childrenLen - 1 ) childrenLen--;
if ( j === min ) min++;
break;
}
}
}
// 对比
child = diff( child, vchild );
// 更新DOM
const f = domChildren[ i ];
if ( child && child !== dom && child !== f ) {
// 如果更新前的对应位置为空，说明此节点是新增的
if ( !f ) {
dom.appendChild(child);
// 如果更新后的节点和更新前对应位置的下一个节点一样，说明当前位置的节点被移除了
} else if ( child === f.nextSibling ) {
removeNode( f );
// 将更新后的节点移动到正确的位置
} else {
// 注意insertBefore的用法，第一个参数是要插入的节点，第二个参数是已存在的节点
dom.insertBefore( child, f );
}
}
}
}
}
对比组件
如果vnode是一个组件，我们也单独拿出来作为一个方法:
function diffComponent( dom, vnode ) {
let c = dom && dom._component;
let oldDom = dom;
// 如果组件类型没有变化，则重新set props
if ( c && c.constructor === vnode.tag ) {
setComponentProps( c, vnode.attrs );
dom = c.base;
// 如果组件类型变化，则移除掉原来组件，并渲染新的组件
} else {
if ( c ) {
unmountComponent( c );
oldDom = null;
}
c = createComponent( vnode.tag, vnode.attrs );
setComponentProps( c, vnode.attrs );
dom = c.base;
if ( oldDom && dom !== oldDom ) {
oldDom._component = null;
removeNode( oldDom );
}
}
return dom;
}
下面是相关的工具方法的实现，和上一篇文章的实现相比，只需要修改renderComponent方法的两个地方。
function renderComponent( component ) {
// ...
// base = base = _render( renderer ); // 将_render改成diff
base = diff( component.base, renderer );
// ...
// 去掉这部分
// if ( component.base && component.base.parentNode ) {
// component.base.parentNode.replaceChild( base, component.base );
// }
// ...
}
完整diff实现看这个文件
渲染
现在我们实现了diff方法，我们尝试渲染上一篇文章中定义的Counter组件，来感受一下有无diff方法的不同。
class Counter extends React.Component {
constructor( props ) {
super( props );
this.state = {
num: 1
}
}
onClick() {
this.setState( { num: this.state.num + 1 } );
}
render() {
return (
<div>
<h1>count: { this.state.num }</h1>
<button onClick={ () => this.onClick()}>add</button>
</div>
);
}
}
不使用diff
使用上一篇文章的实现，从chrome的调试工具中可以看到，闪烁的部分是每次更新的部分，每次点击按钮，都会重新渲染整个组件。
使用diff
而实现了diff方法后，每次点击按钮，都只会重新渲染变化的部分。
后话
在这篇文章中我们实现了diff算法，通过它做到了每次只更新需要更新的部分，极大地减少了DOM操作。React实现远比这个要复杂，特别是在React 16之后还引入了Fiber架构，但是主要的思想是一致的。
实现diff算法可以说性能有了很大的提升，但是在别的地方仍然后很多改进的空间：每次调用setState后会立即调用renderComponent重新渲染组件，但现实情况是，我们可能会在极短的时间内多次调用setState。 假设我们在上文的Counter组件中写出了这种代码
onClick() {
for ( let i = 0; i < 100; i++ ) {
this.setState( { num: this.state.num + 1 } );
}
}
那以目前的实现，每次点击都会渲染100次组件，对性能肯定有很大的影响。 下一篇文章我们就要来改进setState方法
这篇文章的代码：https://github.com/hujiulong/simple-react/tree/chapter-3
从零开始实现React系列
React是前端最受欢迎的框架之一，解读其源码的文章非常多，但是我想从另一个角度去解读React：从零开始实现一个React，从API层面实现React的大部分功能，在这个过程中去探索为什么有虚拟DOM、diff、为什么setState这样设计等问题。
整个系列大概会有四篇，我每周会更新一到两篇，我会第一时间在github上更新，有问题需要探讨也请在github上回复我~
博客地址: https://github.com/hujiulong/blog 关注点star，订阅点watch
上一篇文章
下一篇文章
diffAttributes中的这一段好像不太对
for ( let name in old ) {
if ( !( name in attrs ) ) {
setAttribute( dom, name, undefined );
}
}
for...in循环数组循环的是index而不是数组的值，应该用for...of吧，还有name in attrs也是数组的index吧，要找name有没有在attrs是不是应该用attrs.indexOf(name) !== -1呐
Pretty comprehensible! I've scanned through it roughly. Does this diffing algorithm resemble to Preact's one?
@p2227 大部分react-like框架都是对比两个虚拟DOM，例如inferno和react-lite，它们会对比新旧虚拟DOM树，然后得到一个补丁（patches），然后再将补丁更新到真实dom树上。这篇文章是采用preact的做法，对比真实dom和虚拟dom，并且在对比的过程中直接更新真实dom
@yzbaoo 理论上用虚拟dom和真实dom比较效率更高，占用的内存也更少，但是这个可能并不是性能瓶颈，差别不会很大。对比两个虚拟DOM的好处是不依赖浏览器环境，这样可以用于别的环境，例如native或者node(SSR)。
两个问题请教下：
- 对比子节点的时候有一个 keyedLen 是拿来干嘛的？没看到定义的地方
if ( child && child !== dom && child !== f ) {
if ( !f ) {
dom.appendChild(child);
} else if ( child === f.nextSibling ) {// 这一步判断是做什么用的？为什么跟 nextSibling 比较？
removeNode( f );
} else {
dom.insertBefore( child, f );// 这一步又是为什么呢
}
}
问题1： [ ...dom.childNodes ].map( out.appendChild ); 这个没有看懂，麻烦帮忙解读下
问题2： 如果真实DOM和虚拟DOM的类型不同，例如当前真实DOM是一个div，而vnode的tag的值是'button'，那么原来的div就没有利用价值了，直接新建一个button元素，并将div的所有子节点移到button下，然后用replaceChild方法将div替换成button。
是不是先把div下面的子节点全部移到 button，然后在对比 div 子节点和 button的子节点吗？
看过之前的diff算法，一般发现父节点类型不一样，直接移除，然后重新创建。
非常感谢能抽空帮忙解读
@slogeor
问题一
[ ...dom.childNodes ]是将childNodes这个类数组对象转换成数组
如果用ES5的写法就是Array.prototype.splice.call( dom.childNodes );
xx.map( out.appendChild );等价于 xx.map( item => out.appendChild( item ) );
问题二
页面中极少出现变换父节点类型而子节点不变的情况，所以父节点变了，大概率整个DOM子树都变了，没必要再去比对它的子节点