资讯专栏INFORMATION COLUMN

React系列 --- virtualdom diff算法实现分析(三)

sunsmell / 1927人阅读

摘要:所以只针对同层级节点做比较,将复杂度的问题转换成复杂度的问题。

React系列

React系列 --- 简单模拟语法(一)
React系列 --- Jsx, 合成事件与Refs(二)
React系列 --- virtualdom diff算法实现分析(三)
React系列 --- 从Mixin到HOC再到HOOKS(四)
React系列 --- createElement, ReactElement与Component部分源码解析(五)
React系列 --- 从使用React了解Css的各种使用方案(六)

完整代码可查看virtualdom-diff

渲染DOM

经历过PHP模板开发或者JQuery的洗礼的人都知道,它们实现重新渲染采用最简单粗暴的办法就是重新构建DOM替换旧DOM,问题也很明显

性能消耗高

无法保存状态(聚焦,滚动等)

我们先看看创建一个元素所包含的实例属性有多少个

const div = document.createElement("div");
let num = 0;
for (let k in div) {
  num++;
}
console.log(num); // 241

然后浏览器根据CSS规则查找匹配节点,计算合并样式布局,为了避免重新计算一般浏览器会保存这些数据.但这是整个过程下来依然会耗费大量的内存和 CPU 资源.

Virtual DOM

实际也是操作Dom树进行渲染更新,但是它只是针对修改部分进行局部渲染,将影响降到最低,虽然实现方式各有不同,但是大体步骤如下:

用Javascript对象结构描述Dom树结构,然后用它来构建真正的Dom树插入文档

当状态发生改变之后,重新构造新的Javascript对象结构和旧的作对比得出差异

针对差异之处进行重新构建更新视图

无非就是利用Js做一层映射比较,操作简单并且速度远远高于直接比较Dom树

基础工具函数

无非就是一些类型判断,循环遍历的简化函数

function type(obj) {
  return Object.prototype.toString.call(obj).replace(/[objects|]/g, "");
}

function isArray(list) {
  return type(list) === "Array";
}

function isObject(obj) {
  return type(obj) === "Object";
}

function isString(str) {
  return type(str) === "String";
}

function isNotEmptyObj(obj) {
  return isObject(obj) && JSON.stringify(obj) != "{}";
}

function objForEach(obj, fn) {
  isNotEmptyObj(obj) && Object.keys(obj).forEach(fn);
}

function aryForEach(ary, fn) {
  ary.length && ary.forEach(fn);
}

function setAttr(node, key, value) {
  switch (key) {
    case "style":
      node.style.cssText = value;
      break;
    case "value":
      var tagName = node.tagName || "";
      tagName = tagName.toLowerCase();
      if (tagName === "input" || tagName === "textarea") {
        node.value = value;
      } else {
        // if it is not a input or textarea, use `setAttribute` to set
        node.setAttribute(key, value);
      }
      break;
    default:
      node.setAttribute(key, value);
      break;
  }
}

function toArray(data) {
  if (!data) {
    return [];
  }
  const ary = [];
  aryForEach(data, item => {
    ary.push(item);
  });

  return ary;
}

export {
  isArray,
  isObject,
  isString,
  isNotEmptyObj,
  objForEach,
  aryForEach,
  setAttr,
  toArray
};

相关代码可以查看util.js

Javascript对象结构描述

我之前讲JSX的时候举过这么个例子,然后我们就以这个来实现效果吧

123456
"use strict";

React.createElement("div", {
  className: "num",
  index: 1
}, React.createElement("span", null, "123456"));

创建一个Element类负责将Javascript对象结构转换为Dom树结构

import {
  isObject,
  isString,
  isArray,
  isNotEmptyObj,
  objForEach,
  aryForEach
} from "./util";
import { NOKEY } from "./common";

class Element {
  constructor(tagName, props, children) {
    // 解析参数
    this.tagName = tagName;
    // 字段处理,可省略参数
    this.props = isObject(props) ? props : {};
    this.children =
      children ||
      (!isNotEmptyObj(this.props) &&
        ((isString(props) && [props]) || (isArray(props) && props))) ||
      [];
    // 无论void后的表达式是什么,void操作符都会返回undefined
    this.key = props ? props.key : void NOKEY;

    // 计算节点数
    let count = 0;
    aryForEach(this.children, (item, index) => {
      if (item instanceof Element) {
        count += item.count;
      } else {
        this.children[index] = "" + item;
      }
      count++;
    });
    this.count = count;
  }

  render() {
    // 根据tagName构建
    const dom = document.createElement(this.tagName);

    // 设置props
    objForEach(this.props, propName =>
      dom.setAttribute(propName, this.props[propName])
    );

    // 渲染children
    aryForEach(this.children, child => {
      const childDom =
        child instanceof Element
          ? child.render() // 如果子节点也是虚拟DOM,递归构建DOM节点
          : document.createTextNode(child); // 如果字符串,只构建文本节点
      dom.appendChild(childDom);
    });
    return dom;
  }
}

// 改变传参方式,免去手动实例化
export default function CreateElement(tagName, props, children) {
  return new Element( tagName, props, children );
}

新建示例,调用方式如下

// 1. 构建虚拟DOM
const tree = createElement("div", { id: "root" }, [
  createElement("h1", { style: "color: blue" }, ["Tittle1"]),
  createElement("p", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 4 }, ["li4"])
  ])
]);

// 2. 通过虚拟DOM构建真正的DOM
const root = tree.render();
document.body.appendChild(root);

运行之后能正常得出结果了,那么第一步骤算是完成了,具体还有更多不同类型标签,对应事件状态先略过.

界面如图

Javascript结构如图

结构原型如下

相关代码可以查看element.js

diff算法

这是整个实现里面最关键的一步,因为这决定了计算的速度和操作Dom的数量

我们创建新的Dom树作对比

// 3. 生成新的虚拟DOM
const newTree = createElement("div", { id: "container" }, [
  createElement("h1", { style: "color: red" }, ["Title2"]),
  createElement("h3", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 5 }, ["li5"])
  ])
]);

Javascript结构如图

tree diff

传统 diff 算法的复杂度为 O(n^3),但是一般Dom跨层级的情况是非常少见的。所以React 只针对同层级Dom节点做比较,将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

比较大的问题就是当节点跨层级移动并不会进行移动而是直接替换整个节点,所以切记这点性能问题

component diff

某个组件发生变化,会导致自其从上往下整体替换

同一类型组件会进行Virtual DOM进行比较

React提供了一个shouldComponentUpdate决定是否更新

尽可能将动态组件往底层节点迁移,有利于提高性能

element diff

元素操作无非就是几种,我们定义几个类型做状态标记

const REPLACE = "replace";
const REORDER = "reorder";
const PROPS = "props";
const TEXT = "text";
const NOKEY = "no_key"

export {
  REPLACE,
  REORDER,
  PROPS,
  TEXT,
  NOKEY
}

其中NOKEY就是专门给那些没有定义key的组件做默认,React对同一层级的同组子节点,添加唯一 key 进行区分进行位移而不是直接替换,这点对于整体性能尤为关键

我们首先针对不同类型做些区分处理

import { isString, objForEach, aryForEach, isNotEmptyObj } from "./util";
import { REPLACE, REORDER, PROPS, TEXT } from "./common";
import listDiff from "list-diff2";

/**
 *
 * @param {旧Dom树} oTree
 * @param {新Dom树} nTree
 * 返回差异记录
 */
function diff(oTree, nTree) {
  // 节点位置
  let index = 0;
  // 差异记录
  const patches = {};
  dfsWalk(oTree, nTree, index, patches);
  return patches;
}

function dfsWalk(oNode, nNode, index, patches) {
  const currentPatch = [];

  // 首次渲染
  if (nNode === null) return;

  // 都是字符串形式并且不相同直接替换文字
  if (isString(oNode) && isString(nNode)) {
    oNode !== nNode &&
      currentPatch.push({
        type: TEXT,
        content: nNode
      });
    // 同种标签并且key相同
  } else if (oNode.tagName === nNode.tagName && oNode.key === nNode.key) {
    // 至少一方有值
    if (isNotEmptyObj(oNode.props) || isNotEmptyObj(nNode.props)) {
      // 计算props结果
      const propsPatches = diffProps(oNode, nNode);
      // 有差异则重新排序
      propsPatches &&
        currentPatch.push({
          type: PROPS,
          props: propsPatches
        });
    }
    // children对比
    if (
      !(!isNotEmptyObj(nNode.props) && nNode.props.hasOwnProperty("ignore"))
    ) {
      (oNode.children.length || nNode.children.length) &&
        diffChildren(
          oNode.children,
          nNode.children,
          index,
          patches,
          currentPatch
        );
    }
  } else {
    // 都不符合上面情况就直接替换
    currentPatch.push({ type: REPLACE, node: nNode });
  }

  // 最终对比结果
  currentPatch.length && (patches[index] = currentPatch);
}

新旧节点的props属性比较

/**
 *
 * @param {旧节点} oNode
 * @param {新节点} nNode
 */
function diffProps(oNode, nNode) {
  let isChange = false;
  const oProps = oNode.props;
  const nProps = nNode.props;
  // 节点属性记录
  const propsPatched = {};

  // 替换/新增属性
  objForEach(oProps, key => {
    if (nProps[key] !== oProps[key] || !oProps.hasOwnProperty(key)) {
      !isChange && (isChange = true);
      propsPatched[key] = nProps[key];
    }
  });

  return !isChange ? null : propsPatched;
}

新旧节点的子元素对比

/**
 *  同级对比
 * @param {*} oChildren
 * @param {*} nChildren
 * @param {*} index
 * @param {*} patches
 * @param {*} currentPatch
 */
function diffChildren(oChildren, nChildren, index, patches, currentPatch) {
  // 得出相对简化移动路径
  const diffs = listDiff(oChildren, nChildren, "key");

  // 保留元素
  nChildren = diffs.children;

  // 记录排序位移
  diffs.moves.length &&
    currentPatch.push({ type: REORDER, moves: diffs.moves });

  // 深度遍历
  let leftNode = null;
  let currentNodeIndex = index;
  aryForEach(oChildren, (_item, _index) => {
    const nChild = nChildren[_index];
    currentNodeIndex =
      leftNode && leftNode.count
        ? currentNodeIndex + leftNode.count + 1
        : currentNodeIndex + 1;
    _item !== nChild && dfsWalk(_item, nChild, currentNodeIndex, patches);
    leftNode = _item;
  });
}

深度遍历的原型图如下

其中的listDiff来自于list-diff,能通过关键属性获得最小移动量,moves就是给第三步更新视图做铺垫指示,官方介绍如下

Diff two lists in time O(n). I The algorithm finding the minimal amount of moves is Levenshtein distance which is O(n*m). This algorithm is not the best but is enougth for front-end DOM list manipulation.

This project is mostly influenced by virtual-dom algorithm.

调用对比方式

// 4. 比较两棵虚拟DOM树的不同
const patches = diff(tree, newTree);

得出差异如下

相关代码可以查看diff.js

更新视图

进行深度遍历

import {
  isString,
  isObject,
  objForEach,
  aryForEach,
  setAttr,
  toArray
} from "./util";
import { REPLACE, REORDER, PROPS, TEXT, NOKEY } from "./common";

function patch(node, patches) {
  const walker = { index: 0 };
  dfsWalk(node, walker, patches);
}

// 深度遍历更新
function dfsWalk(node, walker, patches) {
  const currentPatches = patches[walker.index];

  node.childNodes &&
    aryForEach(node.childNodes, item => {
      walker.index++;
      dfsWalk(item, walker, patches);
    });

  currentPatches && applyPatches(node, currentPatches);
}

针对不同标志做对应处理

// 更新类型
function applyPatches(node, currentPatches) {
  aryForEach(currentPatches, item => {
    switch (item.type) {
      case REPLACE:
        const nNode = isString(item.node)
          ? document.createTextNode(item.node)
          : item.node.render();
        node.parentNode.replaceChild(nNode, node);
        break;
      case REORDER:
        reorderChildren(node, item.moves);
        break;
      case PROPS:
        setProps(node, item.props);
        break;
      case TEXT:
        if (node.textContent) {
          // 使用纯文本
          node.textContent = item.content;
        } else {
          // 仅仅对CDATA片段,注释comment,Processing Instruction节点或text节点有效
          node.nodeValue = item.content;
        }
        break;
      default:
        throw new Error("Unknown patch type " + item.type);
    }
  });
}

先说简单的属性替换

// 修改属性
function setProps(node, props) {
  objForEach(props, key => {
    if (props[key] === void NOKEY) {
      node.removeAttribute(key);
    } else {
      setAttr(node, key, props[key]);
    }
  });
}

最后就是列表渲染

// 列表排序渲染
function reorderChildren(node, moves) {
  const staticNodeList = toArray(node.childNodes);
  const maps = {};

  aryForEach(staticNodeList, node => {
    // Element
    if (node.nodeType === 1) {
      const key = node.getAttribute("key");
      key && (maps[key] = node);
    }
  });

  aryForEach(moves, move => {
    const index = move.index;
    // 0:删除 1:替换
    if (move.type === 0) {
      // 找到对应节点删除
      staticNodeList[index] === node.childNodes[index] &&
        node.removeChild(node.childNodes[index]);
      staticNodeList.splice(index, 1);
    } else if (move.type === 1) {
      let insertNode;
      if (maps[move.item.key]) {
        // 删除并返回节点
        insertNode = node.removeChild(maps[move.item.key]);
        // 获取删除节点位置
        staticNodeList.splice(Array.prototype.indexOf.call(node.childNodes, maps[move.item.key]), 1);
      } else {
        // 创建节点
        insertNode = isObject(move.item)
          ? move.item.render()
          : document.createTextNode(move.item);
      }
      // 同步staticNodeList信息
      staticNodeList.splice(index, 0, insertNode);
      // 操作Dom
      node.insertBefore(insertNode, node.childNodes[index] || null);
    }
  });
}

export default patch;

当这一步完成以后我们可以直接应用查看效果

// 4. 比较两棵虚拟DOM树的不同
const patches = diff(tree, newTree);

// 5. 在真正的DOM元素上应用变更
patch(root, patches);

结果如图

相关代码可以查看patch.js

参考

深度剖析:如何实现一个 Virtual DOM 算法

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/106487.html

相关文章

  • React && VUE Virtual Dom的Diff算法统一之路 snabbd

    摘要:毫无疑问的是算法的复杂度与效率是决定能够带来性能提升效果的关键因素。速度略有损失,但可读性大大提高。因此目前的主流算法趋向一致,在主要思路上,与的方式基本相同。在里面实现了的算法与支持。是唯一添加的方法所以只发生在中。 VirtualDOM是react在组件化开发场景下,针对DOM重排重绘性能瓶颈作出的重要优化方案,而他最具价值的核心功能是如何识别并保存新旧节点数据结构之间差异的方法,...

    shixinzhang 评论0 收藏0
  • 深入React知识点整理(一)

    摘要:以我自己的理解,函数式编程就是以函数为中心,将大段过程拆成一个个函数,组合嵌套使用。越来越多的迹象表明,函数式编程已经不再是学术界的最爱,开始大踏步地在业界投入实用。也许继面向对象编程之后,函数式编程会成为下一个编程的主流范式。 使用React也满一年了,从刚刚会使用到逐渐探究其底层实现,以便学习几招奇技淫巧从而在自己的代码中使用,写出高效的代码。下面整理一些知识点,算是React看书...

    Gilbertat 评论0 收藏0
  • React系列 --- 简单模拟语法(一)

    摘要:系列系列简单模拟语法一系列合成事件与二系列算法实现分析三系列从到再到四系列与部分源码解析五系列从使用了解的各种使用方案六前言我们先不讲什么语法原理先根据效果强行模拟语法使用实现一个简易版的第一步我们先用类 React系列 React系列 --- 简单模拟语法(一)React系列 --- Jsx, 合成事件与Refs(二)React系列 --- virtualdom diff算法实现分析...

    piglei 评论0 收藏0
  • 虚拟DOM与DIFF算法学习

    摘要:比较虚拟与的差异,以及对节点的操作,其实就是树的差异比较,就是对树的节点进行替换。忽略掉这种特殊的情况后,大胆的修改了算法按直系兄弟节点比较比较。这当中对比的细节才是整个算法最精粹的地方。 一、旧社会的页面渲染        在jQuery横行的时代,FEer们,通过各种的方式去对页面的DOM进行操作,计算大小,变化,来让页面生动活泼起来,丰富的DOM操作,让一个表面简单的页面能展示出...

    codergarden 评论0 收藏0
  • React系列 --- Jsx, 合成事件与Refs(二)

    摘要:系列系列简单模拟语法一系列合成事件与二系列算法实现分析三系列从到再到四系列与部分源码解析五系列从使用了解的各种使用方案六的诞生他是的一种扩展语法。这个函数接受组件的实例或元素作为参数,以存储它们并使它们能被其他地方访问。 React系列 React系列 --- 简单模拟语法(一)React系列 --- Jsx, 合成事件与Refs(二)React系列 --- virtualdom di...

    LiuZh 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<