非常棒的JavaScript源码实现

# 解题思路 or 实现原理

# 常规 DOM 渲染

layout-paint.png

我们知道目前所有的浏览器都是遵循类似上面图片所绘制出的工作流, 仅在细节处略有不同。

  • 创建DOM树

    一旦浏览器接收到一个HTML文件, 渲染引擎 (render engine) 就开始解析它, 并根据 HTML 元素 (elements)一一对应地生成DOM节点 (nodes), 组成一棵DOM树。

  • 创建渲染树

    同时, 浏览器也会解析来自外部CSS文件和元素上的inline样式。通常浏览器会为这些样式信息, 连同包含样式信息的DOM树上的节点, 再创建另外一个树, 一般被称作渲染树 (render tree)

  • 创建渲染树背后的故事

    WebKit内核的浏览器上, 处理一个节点的样式的过程称为attachment。DOM树上的每个节点都有一个attach方法, 它接收计算好的样式信息, 返回一个render对象 (又名renderer)

    Attachment 的过程是同步的, 新节点插入 DOM树时, 会调用新节点的attach方法。 构建渲染树时, 由于包含了这些 render 对象, 每个 render 对象都需要计算视觉属性 (visual properties); 这个过程通过计算每个元素的样式属性来完成。

  • 布局 Layout 又被简称为Reflow 构造了渲染树以后, 浏览器引擎开始着手布局 (layout)。布局时, 渲染树上的每个节点根据其在屏幕上应该出现的精确位置, 分配一组屏幕坐标值。

  • 绘制 Painting

    接着, 浏览器将会通过遍历渲染树, 调用每个节点的 paint 方法来绘制这些 render 对象。paint 方法根据浏览器平台, 使用不同的 UI后端API (agnostic UI backend API)。 通过绘制, 最终将在屏幕上展示内容。

DOM操作 真正的问题在于每次操作都会触发布局的改变、DOM树 的修改和渲染。Virtual DOM把管理 DOM碎片这件事情自动化、抽象化了, 使得你无需再去手动处理。

# 什么是 Virtual DOM？

Virtual DOM是对DOM的抽象, 本质上是JavaScript对象, 这个对象就是更加轻量级的对DOM的描述.

# 传统的 diff 算法 和 React 的 diff 算法

  • 传统 diff 算法的复杂度为O(n^3)

  • React diff算法的复杂度为O(n)

# 先序深度遍历

  • 先中后序遍历 -> 遍历根节点的顺序

    • 先序 -> 根, 左, 右

    • 中序 -> 左, 根, 右

    • 后序 -> 左, 右, 根

  • 深度(DFS)遍历 -> 从根节点出发, 沿着左子树方向进行纵向遍历, 直到找到叶子节点为止。然后回溯到前一个节点, 进行右子树节点的遍历, 直到遍历完所有可达节点为止。

  • 广度(BFS)遍历 -> 从根节点出发, 在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

dom-diff-alogrithm.png

# DOM Diff 算法策略

dom-diff-algorithm.svg

# Mini Diff 算法实现

  • 替换

    • 节点替换
    • 属性替换
    • 文本替换
    • 更多尚未实现

  • 移除

    • 节点移除
    • 属性移除
    • 文本移除
    • 更多尚未实现

# Dom Diff 流程

dom-dff.png

# Demo

Link (opens new window)

# 实现代码

Link (opens new window)

index.d.ts

export interface Node {
    type: string;
    props: AnyObject;
    children: Array<Node>;
}

export type AnyObject = {
    [propName: string]: any;
}

export type AnyArray = unknown[];
1
2
3
4
5
6
7
8
9
10
11

utils.ts

const CREATE = 'CREATE';
const REMOVE = 'REMOVE';
const REPLACE = 'REPLACE';
const UPDATE = 'UPDATE';
const SET_PROP = 'SET_PROP';
const REMOVE_PROP = 'REMOVE_PROP';

function isString(str: string): boolean {
  return Object.prototype.toString.call(str) === '[object String]';
}

export { CREATE, REMOVE, REPLACE, UPDATE, SET_PROP, REMOVE_PROP, isString };
1
2
3
4
5
6
7
8
9
10
11
12

render.js

import { diff } from './diff';
import { createElement, patch } from './patch';

function flatten(arr) {
  return [].concat.apply([], arr);
}

function h(type, props, ...children) {
  props = props || {};
  return { type, props, children: flatten(children) };
}


function view(count) {
  const r = [...Array(count).keys()];
  return (
    <ul id="cool" className={`my-class-${count}`}>
      {r.map(n => (
        <li>item {(count * n).toString()}</li>
      ))}
    </ul>
  );
}

function tick(el, count) {
  const patches = diff(view(count + 1), view(count));
  patch(el, patches);
  if (count > 20) {
    return;
  }
  setTimeout(() => tick(el, count + 1), 500);
}

function render(el) {
  el.appendChild(createElement(view(0)));
  setTimeout(() => tick(el, 0), 500);
}

export { render };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

diff.ts

import {
  CREATE,
  REMOVE,
  REPLACE,
  UPDATE,
  SET_PROP,
  REMOVE_PROP
} from './utils';

import { Node, AnyObject, AnyArray } from './index';

function changed(node1: Node | any, node2: Node | any): boolean {
  return (
    typeof node1 !== typeof node2 ||
    node1.type !== node2.type ||
    (typeof node1 !== 'string' && node1 !== node2)
  );
}

function diffProps(oldProps: AnyObject, newProps: AnyObject): AnyArray {
  const patches: AnyArray = [];
  const props: AnyObject = Object.assign({}, oldProps, newProps);
  Object.keys(props).forEach(key => {
    const oldValue: any = oldProps[key];
    const newValue: any = newProps[key];

    if (!newValue) {
      patches.push({
        type: REMOVE_PROP,
        name,
        value: oldValue
      });
    } else if (!oldValue || oldValue !== newValue) {
      patches.push({
        type: SET_PROP,
        name,
        value: newValue
      });
    }
  });
  return patches;
}

function diffChildren(oldChildren: AnyArray, newChildren: AnyArray): AnyArray {
  const patches: AnyArray = [];
  const patchesLength: number = Math.max(newChildren.length, oldChildren.length);

  for (let i = 0; i < patchesLength; i++) {
    patches[i] = diff(oldChildren, newChildren);
  }
  return patches;
}

function diff(oldNode: Node | any, newNode: Node | any): AnyObject | undefined {
  if (!oldNode) {
    return { type: CREATE, newNode };
  }

  if (!newNode) {
    return { type: REMOVE };
  }

  if (changed(oldNode, newNode)) {
    return { type: REPLACE, newNode };
  }

  if (oldNode.type !== newNode.type) {
    return {
      type: UPDATE,
      props: diffProps(oldNode.props, newNode.props),
      children: diffChildren(oldNode.children, newNode.children)
    };
  }
}

export { changed, diffProps, diffChildren, diff };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

patch.ts

import {
  CREATE,
  REMOVE,
  REPLACE,
  UPDATE,
  SET_PROP,
  REMOVE_PROP,
  isString
} from './utils';

import { Node, AnyObject, AnyArray } from './index';

function createElement(node: Node | any) {
  if (isString(node)) {
    return document.createTextNode(node + '');
  }
  const el = document.createElement(node.type);
  setProps(el, node.props || {});
  node.children &&
    node.children.map(createElement).forEach(el.appendChild.bind(el));

  return el;
}

function setProp(target, name: string, value: AnyObject): void {
  if (name.toLowerCase() === 'classname') {
    name = 'class';
  }
  target.setAttribute(name, value);
}

function setProps(target, props: AnyObject) {
  Object.keys(props).forEach(name => {
    setProp(target, name, props[name]);
  });
}

function removeProp(target, name: string, value: AnyObject): void {
  if (name.toLowerCase() === 'classname') {
    name = 'class';
  }
  target.removeAttribute(name);
}

function patchProps(parent, patches: AnyArray): void {
  patches.forEach((patch: AnyObject) => {
    const {type, name, value} = patch;
    if (type === SET_PROP) {
      setProp(parent, name, value)
    }
    if (type === REMOVE_PROP) {
      removeProp(parent, name, value)
    }
  });
}

function patch(parent, patches: AnyObject, index: number = 0) {
  if (!patches) {
    return;
  }
  const el = parent.children[index];

  switch (patches.type) {
    case CREATE: {
      const { newNode } = patches;
      const newEl = document.createElement(newNode);
      return parent.appendChild(newEl);
    }
    case REMOVE: {
      return parent.removeChild(el);
    }
    case REPLACE: {
      const { newNode } = patches;
      const newEl = createElement(newNode);
      return parent.replaceChild(newEl, el);
    }
    case UPDATE: {
      const { props, children } = patches;
      patchProps(el, props);
      children.forEach((child, idx) => {
        patch(el, child, idx);
      });
    }
  }
}

export { createElement, setProp, setProps, removeProp, patchProps, patch };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

# 参考

# Diff 相关

Diff Strategies (opens new window)

React Diffing 算法 (opens new window)

React's diff algorithm - Christopher Chedeau (opens new window)

React Dom Diff (opens new window)

Under-the-hood-ReactJS (opens new window)

babel-plugin-transform-react-jsx (opens new window)

diff 算法原理概述 (opens new window)

React 源码剖析系列 － 不可思议的 react diff (opens new window)

# Virtual DOM 相关

snabbdom (opens new window)

How to write your own Virtual DOM (opens new window)

Mini Virtual DOM 实现 (opens new window)

virtual-dom (opens new window)

解析 snabbdom 源码 (opens new window)

为什么要使用 Virtual DOM (opens new window) -> 中文版 (opens new window)

浏览器的工作原理：新式网络浏览器幕后揭秘 (opens new window)

← 手写Promise →