了不起的Virtual-DOM二-使用TypeScript开发简易Virtual-DOM库

jiezi

5 年前

首先欢迎大家关注、点赞、收藏我的掘金账号和 Github 博客，也算是对我的一点鼓励，毕竟写东西没法获得变现，能坚持下去也是靠的是自己的热情和大家的鼓励。之前的文章我们介绍了 MV* 框架的历史以及 React 引入 Virtual DOM 所带来的新的解决思路，俗话说，百闻不如一见，百见不如一干。这篇文章我们将尝试使用去实现一个 Virtual DOM 的最小化实现方案，因为最近刚学了 TypeScript，正好拿来练手。源码地址将在文章最后附录。

无论是 MVC 模式还是后来改进的 MVP 模式以及目前更为常见的 MVVM 模式，其目的都是为了解决 Model 层和 View 如何连接，通过采用各种中间层 (Controller、Presenter、View of Model) 协调 View 与 Model 的关系。但是 React 所倡导的 Virtual DOM 方案却剑走偏锋，即每次 Model 层的变化都会重新渲染 View 层，那么作为开发者而言，只需要处理好数据和视图映射，从而将我们的关注重点集中于数据和数据流的变化，从而极大的降低开发关注度。

实际上我们都知道浏览器对 DOM 的操作所带来的渲染重绘相比于 JavaScript 计算速度肯定是慢上好几个数量级的。假设仅仅只是页面中一个数据的变化就重绘整个页面，那肯定是我们所不能接受的。借鉴计算机学科中最常用的 Cache 思想，我们在低速的 DOM 操作和高速的 JavaScript 执行之间引入了 Virtual DOM，通过对比两个 Virtual DOM 节点的变化，找出其中的变化，从而精准地修改 DOM 节点，在实现思路的同时尽可能地降低操作代价，达到良好的性能体验。

众所周知，把大象装到冰箱需要三步，那么实现一个 Virtual DOM 库需要几步呢？

上图就是我们要实现 Virtual DOM 的基本流程：

创建 Virtual DOM 节点
渲染 Virtual DOM 树
Diff 算法比较两个 Virtual DOM 树，得到结果 Patch
应用 Patch，更新 DOM 树

上面的四个步骤也就基本对应着我们所要实现 Virtual DOM 的四个函数:

createElement
render
diff
applyDiff

乍一看想要实现 Virtual DOM 库可能感觉颇有难度，但是经过仔细的分析，其实将问题转化成实现四个特定功能的函数。其实这种思维方式在我们软件开发中还是非常的实用的，当目标过大而无从下手时，要学会将目标合理拆分。React 所倡导的前端组件化其实就包含这个思想，组件化最重要的两个特点就是：复用和分治，我们往往过于强调复用的特性。其实相比复用，分治才是组件化的精髓，我们通过划分组件，往往使得特定组件仅具有相对较为简单的职责功能，然后通过组合简单的组件成为复杂的功能。相比而言，维护功能职责简单的组件更为容易，也不容易出错。接下来我们要做的就是一步步实现各个函数功能，最终实现一个简单的 Virtural DOM 库。

在此之前，我们首先简要介绍 JSX 的作用，由 React 发扬光大的 JSX 语法使得我们更为方便的在 JavaScript 中创建 HTML，描述 UI 界面。JSX 语法并不是某个库所独有的，而是一种 JavaScript 函数调用的语法糖，JSX 其实相当于 JavaScript + HTML(也被称为 hyperscript，即 hyper + script，hyper 是 HyperText 超文本的简写，而 script 是 JavaScript 的简写)。在 React 中，JSX 语法都会转化成 React.createElement 调用，而在 Preact 中，JSX 语法则会被转成 preact.h 函数调用。

例如在 React 中：

<ul>
    <li> 列表 1 </li>
    <li> 列表 2 </li>
    <li> 列表 3 </li>
</ul>

则会被转化为：

React.createElement(
    'ul',
    null,
    React.createElement('li', null, '列表 1'),
    React.createElement('li', null, '列表 2'),
    React.createElement('li', null, '列表 3')
);

其中 createElement 的参数依次是元素类型、属性、以及子元素。类型元素可以分为三种，依次是：字符串、函数、类，依次对应于 HTML 固有元素、无状态函数组件 (SFC)、类组件。本篇文章重点只在于阐释 Virtual DOM 基本原理，因此简单起见，我们仅支持 HTML 固有元素，暂不支持无状态函数组件 (SFC)和类组件。

JSX 可以根据使用的框架编译成不同的函数调用，例如 React 的 React.createElement 或者 Preact 的 h，我们可以通过在 JSX 上添加编译注释(Pragma) 来局部改变，例如：

/** @jsx h */
let dom = <div id="foo">Hello!</div>;

通过为 JSX 添加注释 @jsx(这也被成为 Pragma，即编译注释)，可以使得 Babel 在转化 JSX 代码时，将其装换成函数 h 的调用。当然，也可以在工程全局进行配置，比如我们可以在 Babel6 中的.babelrc 文件中设置:

{
  "plugins": [["transform-react-jsx", { "pragma":"h"}]
  ]
}

这样工程中所有用到 JSX 的地方都是被 Babel 转化成使用 h 函数的调用。在 TypeScript 中我们可以通过更改配置文件 tsconfig.json 中的 jsxFactory 来控制 JSX 的编译，具体可参照 TypeScript 中关于 JSX 的文档，不再此处赘述。

根据 Virtual DOM 节点的特点，我们给出 Virtual DOM 节点类描述:

// 类型别名
type TagNameType = string;

type KeyType = string | number | null;

interface PropsType {
    key?: string | number;
    [prop: string]: any;
}

// 类
class VNode {
    // 节点类型
    public tagName: TagNameType;
    // 属性
    public props: PropsType;
    // key
    public key? : KeyType;
    // 子元素
    public children: (VNode | string)[];

    public constructor(tagName: TagNameType) {
        this.tagName = tagName;
        this.key = null;
        this.children = [];
        this.props = {};}
}

其中 tagName 为元素类型，例如：div、p。因为我们暂时仅支持 HTML 固有元素，因此 TagNameType 是字符串类型。props为元素属性，在接口 PropsType 我们规定属性中的 key 值必须为 number 或者 string 或者 null(null 不传 key 属性)，如果对 key 有不明白的同学，欢迎大家阅读我之前的文章：React 技术内幕:key 带来了什么。

接下来让我们看一下 createElement 函数的定义：

function createElement(tagName: TagNameType, props: PropsType, ...children: any[]) {

    let key: KeyType = null;

    if (isNotNull(props)) {if (isKey(props.key)) {
            key = props.key!;
            delete props.key;
        }

        if (isNotNull(props.children)) {children.push(props.children);
            delete props.children;
        }
    }

    const node = new VNode(tagName);
    node.children = flatten(children);
    node.key = key;
    node.props = isNotNull(props) ? props : {};
    return node;
}

如果 props 中含有 key 属性，则会将其从 props 中删除，单独赋值给 VNode 的 key 属性，而处理 props 中的 children 属性主要目的是为了处理以下情况通过 props 中的 children 属性直接传递子元素。而对 children 调用 flatten 主要是为了处理：

const dom = (
    <ul>
    {Array.from({length: 3}).map((val, index)=>{return (<li key={index}> 列表 </li>)
        })
    }
    </ul>
);

在这种情况下 createElement 中的 chilren[0] 是子元素数组，因此我们使用 flatten 函数将其处理普通的子元素数组。

通过 createElement 函数我们就可以将 JSX 转化成 Virtual DOM 节点，写个单元测试验证一下是否正确：

describe('createElement', () => {test('多个子元素 - 数组形式', () => {
        const dom = (
            <ul>
                {Array.from({ length: 2}).map((val, index) => {return <li key={index}></li>;
                    })
                }
            </ul>
        );
        const ul = new VNode('ul');
        ul.children = Array.from({length: 2}).map((val, index) => {const li = new VNode('li');
            li.key = index;
            return li;
        });
        expect(dom).toEqual(ul);
    });
});

运行一下，Bingo，测试通过。

将 Virtual DOM 树渲染成真实 DOM 函数也并不复杂：

const renderDOM = function (vnode: VNodeChildType) {if (isVNode(vnode)) {let node = document.createElement(vnode.tagName);
        // 设置元素属性
        for (const prop of Object.keys(vnode.props)) {let value = vnode.props[prop];
            if (prop === 'style') {value = transformStyleToString(value);
            }
            node.setAttribute(prop, value);
        }

        for (const child of vnode.children) {node.appendChild(renderDOM(child));
        }

        return node;
    }

    if (typeof vnode === 'number') {return document.createTextNode(String(vnode));
    }
    return document.createTextNode(vnode);

};

const render = function (vnode: VNode, root: HTMLElement) {const dom = renderDOM(vnode);
    root.appendChild(dom);
    return dom;
}

其中逻辑并不复杂，只需要特殊提及一点，元素中 style 属性较为特殊，style属性用来通过 CSS 为元素指定样式。在通过 getAttribute() 访问时，返回的 style 特性值中包含的是 CSS 文本，而通过属性来访问它则会返回一个对象。因此在这里我们通过 setAttribute 函数设置元素样式前，通过 transformStyleToString 函数将样式从对象改变为字符串类型，并且将驼峰式的样式属性转化为普通的 CSS 样式属性，具体可见函数定义：

const transformStyleToString = function (style) {
    // 若是文本类型则直接返回
    if (isString(style)) {return style;}
    // 若是对象类型则转为字符串
    if (isObject(style)) {return Object.keys(style).reduce((acc, key) => {let cssKey = key.replace(/[A-Z]/g, match => `-${match.toLowerCase()}`);
            return acc + `${cssKey}: ${style[key]};`;
        }, '');
    }
    return '';
};

Diff 算法可能是 Virtual DOM 中相对较为复杂的部分，当然我们只是为了实现一个简易的 Virtual DOM 系统，并不需要过于复杂的实现，下面只是我自己的一种实现策略，并不具有普遍性。Diff 算法目的是为了比较两棵 Virtual DOM 树的差异，传统 diff 算法的复杂度为 O(n^3)，实际上前端 DOM 树结构具有其自身的特定，因此衍生了各种各样的启发式算法，并将 Diff 算法的时间复杂度降低到 O(n)。

所谓的启发式算法是指：在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时，利用过去的经验，选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。而在 Diff 中启发式算法主要是依赖于下列条件：

同级比较
同元素比较
子元素比较

同级比较是指，我们仅会对比同一层次的节点，而忽略跨层级的 DOM 移动操作。对于同一层次节点的增加和删除，我们则不会进一步比较其子节点，这样只需要对树遍历一遍即可。

以上图为例，父节点从 ul 变为 p 节点，即使 ul 大部分节点也可以重用，但我们并不会跨层级比较，因此我们会重新渲染 div 及其子节点。

同元素比较是指，当遇到元素类型变化时，不会比较两个组件的不同，直接创建新的元素。

以上图为例，父节点从 ul 变为 ol 节点，即使 ul 子节点并未发生改变，但我们认为元素类型从 ul 改变为ol，虽然子节点未发生改变，我们并不会比较子节点，直接创建新的节点。

子元素比较是指，当节点处于同一层级时，我们认为存在以下的节点操作：

插入节点(INSERT_MARKUP)
删除节点(REMOVE_NODE)
移动节点(MOVE_EXISTING)

以上图为例，假设之前的 Virtual DOM 树为 Old Tree。

当比较第一个子元素 div 时，因为 New Tree 中的 div 与同位置 Old Tree 中的 div 节点类型一致，则我们认为前后变化中对应位置的节点仍是同一个，则我们会继续比较节点属性及其及其子节点。

当比较第二个子元素时，因为 p 节点含有 key 属性，且 key = 2 的节点也存在于 Old Tree，并且前后两个 key = 2 的节点类型是一致的，因此我们认为 New Tree 中 key = 2 的p元素是由 Old Tree 中第三个子元素移动 (MOVE_EXISTING) 而来。

当比较第三个子元素时，因为 p 节点含有 key = 3 且 Old Tree 中并不含有 key = 3 的同类型节点，则我们认为改节点属于插入节点(INSERT_MARKUP)。

当我们比较 a 元素的子节点时，因为 New Tree 中已经不存在该位置的节点，因此我们认为改节点属于删除节点(REMOVE_NODE)。

当比较两棵 Virtual DOM 树时，我们需要记录两棵 Virtual DOM 树的区别，我们将其称为 Patch，因为我们需要记录的是树节点的差异，因此我们也可以将Patch 同类化一个树结构。根据 Patch 类特点，我们给 Patch 类的定义:

class Patch {
    // 节点变化类型
    public types: OPERATOR_TYPE[];
    // 子元素 Patch 集合
    public children: Patch[];
    // 存储带渲染的新节点
    public node: VNode | string | null;
    // 存储属性改变
    public modifyProps: ModifyProps[];
    // 文本改变
    public modifyString: string;
    // 节点移动，搭配 `MOVE_EXISTING` 使用
    public removeIndex: number;

    public constructor(types?: (OPERATOR_TYPE | OPERATOR_TYPE[])) {this.types = [];
        this.children = [];
        this.node = null;
        this.modifyProps = [];
        this.modifyString = '';
        this.removeIndex = 0;

        if (types) {types instanceof Array ? this.types.push(...types) : this.types.push(types);
        }
    }
    
    // 省略类方法实现
    // addType
    // addModifyProps
    // addChildPatch
    // setNode
    // setModifyString
    // setRemoveIndex
}

其中 types 属性用于存储变化类型，注意同一个 Patch 可能存在多种变化类型，因此我们使用数组存储。Patch存在以下几种类型：

export const enum OPERATOR_TYPE {
    INSERT_MARKUP,
    MOVE_EXISTING,
    REMOVE_NODE,
    PROPS_CHANG,
    TEXT_CHANGE
}

其中 INSERT_MARKUP、MOVE_EXISTING、REMOVE_NODE 我们都已经介绍过，而 PROPS_CHANG 表示节点属性发生改变，例如 id 属性变化。而 TEXT_CHANGE 适用于文本节点，表示文本节点内容发生改变。例如文本节点内容从 Hello! 改变为Hello World。

node属性用于存储待渲染的节点类型类型，搭配 INSERT_MARKUP 使用。removeIndex属性表示当前节点是从同层序号节点位置移动而来，搭配 MOVE_EXISTING 使用。modifyString表示文本节点变化后的内容，搭配 TEXT_CHANGE 使用。modifyProps表示属性改变的数组，搭配 PROPS_CHANGE 使用。其中 ModifyProps 接口描述为:

const enum PROP_TYPE {
    ADD, // 新增属性
    DELETE, // 删除属性
    MODIFY // 属性改变
}

interface ModifyProps {
    type: PROP_TYPE;
    key?: string;
    value?: any;
}

完事具备，让我们开始实现 diff 函数

// 用于返回子元素数组 NodeList 中 key-node 集合(Map)
function getChildrenKeyMap(children: VNodeChildType[]) {let map = new Map();
    each(children, child => {if (isVNode(child) && isKey(child.key)) {map.set(child.key, child);
        }
    });
    return map;
}

// 返回给定 key 值对应节点所在位置
function getChildIndexByKey(children: VNodeChildType[], key) {return findIndex(children, child => (isVNode(child) && child.key === key));
}

function diffProps(preProps: PropsType, nextProps: PropsType) {// return [...addPropResult, ...deletePropResult, ...modifyPropResult];
    // 返回 Props 比较数组结果，如果不存在 Props 变化则返回空数组。}

function diff(preNode: VNode | null, nextNode: VNode) {const patch = new Patch();

    // 若节点类型不一致或者之前的元素为空，则直接重新创建该节点及其子节点
    if (preNode === null || preNode.tagName !== nextNode.tagName) {return patch.addType(OPERATOR_TYPE.INSERT_MARKUP).setNode(nextNode);
    }

    // 前后两个虚拟节点类型一致，则需要比较属性是否一致
    const propsCompareResult = diffProps(preNode.props, nextNode.props);

    if (isNotEmptyArray(propsCompareResult)) {patch.addType(OPERATOR_TYPE.PROPS_CHANGE).addModifyProps(propsCompareResult);
    }

    // 如果上一个子元素不为空，且下一个子元素全为空，则需要清除所有子元素
    if (isEmptyArray(nextNode.children) && isNotEmptyArray(preNode.children)) {return patch.addChildPatch(preNode.children.map(() => new Patch(OPERATOR_TYPE.REMOVE_NODE)));
    }

    const preChildrenKeyMap = getChildrenKeyMap(preNode.children);

    // 遍历处理子元素
    each(nextNode.children, (child, index) => {
        const nextChild = child;
        const preChild = isNotNull(preNode.children[index]) ? preNode.children[index] : null;

        // 如果当前子节点是字符串类型
        if (isString(nextChild)) {
            // 之前对应节点也是字符串
            if (isString(preChild)) {if (nextChild === preChild) {return patch.addChildPatch(new Patch());
                } else {return patch.addChildPatch((new Patch(OPERATOR_TYPE.TEXT_CHANGE).setModifyString(nextChild)));
                }
            } else {
                // 之前对应节点不是字符串，则需要创建新的节点
                return patch.addChildPatch((new Patch(OPERATOR_TYPE.INSERT_MARKUP)).setNode(nextChild));
            }
        }

        // 若当前的子节点中存在 key 属性
        if (isVNode(nextChild) && isKey(nextChild.key)) {
            // 如果上一个同层虚拟 DOM 节点中存在相同 key 且元素类型相同的节点
            if (preChildrenKeyMap.has(nextChild.key) && preChildrenKeyMap.get(nextChild.key).tagName === nextChild.tagName) {
                // 如果前后两个元素的 key 值和元素类型相等
                const preSameKeyChild = preChildrenKeyMap.get(nextChild.key);
                const sameKeyIndex = getChildIndexByKey(preNode.children, nextChild.key);
                const childPatch = diff(preSameKeyChild, nextChild);
                if (sameKeyIndex !== index) {childPatch.addType(OPERATOR_TYPE.MOVE_EXISTING).setRemoveIndex(sameKeyIndex);
                }
                return patch.addChildPatch(childPatch);
            } else {
                // 直接创建新的元素
                return patch.addChildPatch((new Patch(OPERATOR_TYPE.INSERT_MARKUP).setNode(nextChild)));
            }
        }

        // 子节点中不存在 key 属性
        // 若前后相同位置的节点是 非 VNode(字符串) 或者 存在 key 值(nextChild 不含有 key) 或者是 节点类型不同，则直接创建新节点
        if (!isVNode(preChild) || isKey(preChild.key) || preChild.tagName !== nextChild.tagName) {return patch.addChildPatch((new Patch(OPERATOR_TYPE.INSERT_MARKUP)).setNode(nextChild));
        }

        return patch.addChildPatch(diff(preChild, nextChild));
    });

    // 如果存在 nextChildren 个数少于 preChildren，则需要补充删除节点
    if (preNode.children.length > nextNode.children.length) {patch.addChildPatch(Array.from({ length: preNode.children.length - nextNode.children.length}, () => new Patch(OPERATOR_TYPE.REMOVE_NODE)));
    }
    return patch;
}

我们简单举例下图场景，分别给 new Tree 和old Tree调用 diff 算法，则会生成图中所示的Patch Tree:

applyDiff函数的实现则相对要简单的多，我们只要对照Patch Tree，对之前渲染的 DOM 树进行修改即可。

function applyChildDiff(actualDOM: HTMLElement, patch: Patch) {
    // 因为 removeIndex 是基于 old Tree 中的序号位置，因此我们需要提前备份节点节点顺序关系
    const childrenDOM = map(actualDOM.childNodes, child => child);
    const childrenPatch = patch.children;

    for (let index = 0; index < actualDOM.childNodes.length; index++) {const childPatch = childrenPatch[index];
        let childDOM = childrenDOM[index];
        if (contains(childPatch.types, OPERATOR_TYPE.MOVE_EXISTING)) {const insertDOM = childrenDOM[childPatch.removeIndex];
            actualDOM.insertBefore(insertDOM, childDOM);
            childDOM = insertDOM;
        }
        innerApplyDiff(childDOM, childPatch, actualDOM);
    }
}

function innerApplyDiff(actualDOM: HTMLElement | Text, patch: Patch, parentDOM: HTMLElement) {
    // 处理 INSERT_MARKUP，直接创建新节点替换之前节点
    if (contains(patch.types, OPERATOR_TYPE.INSERT_MARKUP)) {const replaceDOM = renderDOM(patch.node!);
        parentDOM.replaceChild(replaceDOM, actualDOM);
        return replaceDOM;
    }
    // 处理 REMOVE_NODE，直接删除当前节点
    if (contains(patch.types, OPERATOR_TYPE.REMOVE_NODE)) {parentDOM.removeChild(actualDOM);
        return null;
    }
    // 处理 TEXT_CHANGE
    if (contains(patch.types, OPERATOR_TYPE.TEXT_CHANGE)) {
        actualDOM.nodeValue = patch.modifyString;
        return actualDOM;
    }
    // 处理 PROPS_CHANGE
    if (contains(patch.types, OPERATOR_TYPE.PROPS_CHANGE)) {each(patch.modifyProps, function (modifyProp) {
            let key = modifyProp.key;
            let value = modifyProp.value;
            switch (modifyProp.type) {
                case PROP_TYPE.ADD:
                case PROP_TYPE.MODIFY:
                    if (key === 'style') {value = transformStyleToString(value);
                    }
                    actualDOM.setAttribute(key, value);
                    break;
                case PROP_TYPE.DELETE:
                    actualDOM.removeAttribute(key);
                    break;
            }
        });
    }

    if (isHTMLElement(actualDOM)) {applyChildDiff(actualDOM, patch);
    }

    return actualDOM;
}

function applyDiff (actualDOM: HTMLElement | Text, patch: Patch) {if (!(actualDOM.parentNode instanceof HTMLElement)) {throw Error('DOM 元素未渲染');
    }
    return applyDiff(actualDOM, patch, actualDOM.parentNode);
}

现在我们的 Virtual DOM 库已经基本完成，我们起个名字就叫 Vom，让我们尝试使用一下:

import Vom from '../index';

function getRandomArray(length) {return Array.from(new Array(length).keys()).sort(() => Math.random() - 0.5);
}

function getRandomColor() {const colors = ['blue', 'red', 'green'];
    return colors[(new Date().getSeconds()) % colors.length];
}

function getJSX() {
    return (
        <div>
            <p> 这是一个由 Vom 渲染的界面 </p>
            <p>
                <span style={{color: getRandomColor() }}> 现在时间: {Date().toString()}</span>
            </p>
            <p> 下面是一个顺序动态变化的有序列表：</p>
            <ul>
                {getRandomArray(10).map((key) => {return <li key={key}> 列表序号: {key} </li>;
                    })
                }
            </ul>
        </div>
    );
}

let preNode = getJSX();
let actualDom = Vom.render(preNode, document.body);

setInterval(() => {const nextNode = getJSX();
    const patch = Vom.diff(preNode, nextNode);
    actualDom = Vom.applyDiff(actualDom, patch)!;
    preNode = nextNode;
}, 1000);

到目前为止我们已经实现一个 Virtual DOM 的基本功能，本篇文章重点还是在讲述 Virtual DOM 基本原理，实现方面相对比较简陋，如有不正确之处，望各位见谅。代码已经上传 Github:Vom。写作不易，愿大家能多多支持，关注我的 Github 博客，关注、点赞、收藏素质三连哦！希望这篇文章能对你有些许帮助，愿共同学习！

了不起的Virtual-DOM二-使用TypeScript开发简易Virtual-DOM库

前言

回顾

创建 Virtual DOM 节点

渲染 Virtual DOM 树

Diff 算法

同级比较

同元素比较

子元素比较

Patch

Diff 函数简要实现

应用 Patch 更新 DOM 树

Virtual DOM 使用演示

结尾