V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iamjiulong
V2EX  ›  前端开发

从零开始实现一个 React(三): diff 算法

  •  
  •   iamjiulong · 2018-04-13 14:02:11 +08:00 · 1365 次点击
    这是一个创建于 2177 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前言

    上一篇文章,我们已经实现了 React 的组件功能,从功能的角度来说已经实现了 React 的核心功能了。

    但是我们的实现方式有很大的问题:每次更新都重新渲染整个应用或者整个组件,DOM 操作十分昂贵,这样性能损耗非常大。

    为了减少 DOM 更新,我们需要找渲染前后真正变化的部分,只更新这一部分 DOM。而对比变化,找出需要更新部分的算法我们称之为diff 算法

    对比策略

    在前面两篇文章后,我们实现了一个 render 方法,它能将虚拟 DOM 渲染成真正的 DOM,我们现在就需要改进它,让它不要再傻乎乎地重新渲染整个 DOM 树,而是找出真正变化的部分。

    这部分很多类 React 框架实现方式都不太一样,有的框架会选择保存上次渲染的虚拟 DOM,然后对比虚拟 DOM 前后的变化,得到一系列更新的数据,然后再将这些更新应用到真正的 DOM 上。

    但也有一些框架会选择直接对比虚拟 DOM 和真实 DOM,这样就不需要额外保存上一次渲染的虚拟 DOM,并且能够一边对比一边更新,这也是我们选择的方式。

    不管是 DOM 还是虚拟 DOM,它们的结构都是一棵树,完全对比两棵树变化的算法时间复杂度是 O(n^3),但是考虑到我们很少会跨层级移动 DOM,所以我们只需要对比同一层级的变化。

    image 只需要对比同一颜色框内的节点

    总而言之,我们的 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 是一个 div,而 vnode 的 tag 的值是'button',那么原来的 div 就没有利用价值了,直接新建一个 button 元素,并将 div 的所有子节点移到 button 下,然后用 replaceChild 方法将 div 替换成 button。

    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.attributes;    // 当前 DOM 的属性
        const attrs = vnode.attrs;     // 虚拟 DOM 的属性
    
        // 如果原来的属性不在新的属性当中,则将其移除掉(属性值设为 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 ) {
                    keyedLen++;
                    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 {
                        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 );
    
        // ...
    }
    

    完整 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 的调试工具中可以看到,闪烁的部分是每次更新的部分,每次点击按钮,都会重新渲染整个组件。 2

    使用 diff

    而实现了 diff 方法后,每次点击按钮,都只会重新渲染变化的部分。 2

    后话

    在这篇文章中我们实现了 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

    上一篇文章

    从零开始实现一个 React (二):组件和生命周期

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2921 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:13 · PVG 22:13 · LAX 07:13 · JFK 10:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.