Open pfan123 opened 4 years ago
React 最值得称道部分就是 Virtual DOM 和 Diff ,这两块核心点方便我们更好的抽象化的开发组件,提高渲染效率。
Virtual DOM 是一种编程概念。在这个概念里, UI 以一种理想化的,或者说“虚拟的 DOM TREE”表现形式被保存于内存中,并通过如 ReactDOM 等类库使之与“真实的” DOM 同步。
Shadow DOM 和 Virtual DOM 不一样。Shadow DOM 是一种浏览器技术,主要用于在 web 组件中封装变量和 CSS。Virtual DOM 则是一种由 Javascript 类库基于浏览器 API 实现的概念。
function createElement(tagName, props, ...children) { return { tagName, props, children, } } // vnode { tagName: 'div', props: { className: 'one' }, children: [{tagName: 'li', props: { className: 'kk', children: [...] }}, children: [{tagName: 'li', props: { className: 'zz', children: ['kkk'] }}] } const vnode = createElement('div', {className: 'one'}, createElement('li', {className: 'kk'}, createElement('span', {className: 'txt'}, 'kkk'), createElement('li', {className: 'zz'}, 'kkk') ), createElement('li', {className: 'one'}, 'one') )
JSX 仅仅只是 React.createElement(component, props, ...children) 函数的语法糖,https://reactjs.org/docs/jsx-in-depth.html
React.createElement(component, props, ...children)
React 中此部分 JSX 语法糖,通过 plugin-transform-react-jsx 转换为 React.createElement 函数的语法糖:
React.createElement
遍历 Tree Dom 结构,涉及常用数据算法: 广度优先搜索(breadth-first search,BFS),广度优先遍历(breadth-first traversal,BFT), 深度优先遍历(depth-first traversal,DFT)。笔者这里只讨论:广度优先遍历(breadth-first traversal,BFT), 深度优先遍历(depth-first traversal,DFT)。
广度优先遍历(BFT breadth-first traversal):广度优先遍历是连通图的一种遍历策略,它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。树的广度优先遍历是指优先遍历完某一层的所有节点,然后再依次向下层遍历。
步骤:
广度优先算法的的非递归实现:
function wideTraversal(vnode) { if(!vnode) { throw new Error('Empty Tree') } const nodeList = [] const queue = [] queue.push(vnode) while (queue.length !== 0) { const node = queue.shift() nodeList.push(node) if(node.children){ const children = node.children for (let i = 0; i < children.length; i++) queue.push(children[i]) } } return nodeList }
深度优先遍历(DFT depth-first traversal):树的深度优先遍历是指首先遍历树的某个分支上的所有节点,在遍历另一个分支的节点,对于节点中的分支也这样处理。React 中 Dom Diff 采用的深度优先遍历算法,至于React 为何不使用广度优先遍历得到的答案是可能会导致组件的生命周期乱套。
步骤:
深度优先算法的递归实现:
function deepTraversal(vnode) { if(!vnode) { throw new Error('Empty Tree') } const nodeList = [] walk(vnode, nodeList) return nodeList } function walk(vnode, nodeList = []) { nodeList.push(vnode) if(vnode.children){ const children = vnode.children children.forEach(node => { walk(node, nodeList) }) } }
深度优先算法的非递归实现:
function deepTraversal(vnode) { if(!vnode) { throw new Error('Empty Tree') } const nodeList = [] const stack = [] stack.push(vnode) while (stack.length !== 0) { const node = stack.pop() nodeList.push(node) if(node.children){ const children = node.children for (let i = children.length - 1; i >= 0; i--) stack.push(children[i]) } } return nodeList }
计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法 通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n^3),其中 n 是树中节点的总数。O(n^3) 到底有多可怕,这意味着如果要展示 1000 个节点,就要依次执行上十亿次的比较。这个开销实在是太过高昂。现今的 CPU 每秒钟能执行大约30亿条指令,即便是最高效的实现,也不可能在一秒内计算出差异情况。
O(n^3)
如果 React 只是单纯的引入 diff 算法而没有任何的优化改进,那么其效率是远远无法满足前端渲染所要求的性能。
那么,React diff 到底是如何实现的稳定高效的 diff 呢?
传统 diff 算法的复杂度为 O(n^3),显然这是无法满足性能要求的。React 通过制定大胆的策略,将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。
基于以上三个前提策略,React 分别对 tree diff、component diff 以及 element diff 进行算法优化,事实也证明这三个前提策略是合理且准确的,它保证了整体界面构建的性能。
基于策略一,React 对树的算法进行了简洁明了的优化,即对树进行分层比较,两棵树只会对同一层次的节点进行比较。
既然 DOM 节点跨层级的移动操作少到可以忽略不计,针对这一现象,React 通过 updateDepth 对 Virtual DOM 树进行层级控制,只会对相同颜色方框内的 DOM 节点进行比较,即同一个父节点下的所有子节点。当发现节点已经不存在,则该节点及其子节点会被完全删除掉,不会用于进一步的比较。这样只需要对树进行一次遍历,便能完成整个 DOM 树的比较。
React 是基于组件构建应用的,对于组件间的比较所采取的策略也是简洁高效。
当节点处于同一层级时,React diff 提供了三种节点操作,分别为:INSERT_MARKUP(插入)、MOVE_EXISTING(移动)、TEXT_CONTENT(文本内容)、REMOVE_NODE(删除)。
详情参考 DOMChildrenOperations.js
// virtual-dom function createElement(tagName, props = {}, ...children) { let vnode = {} if(props.hasOwnProperty('key')){ vnode.key = props.key delete props.key } return Object.assign(vnode, { tagName, props, children, }) }
function render (vNode) { const element = document.createElement(vNode.tagName) const props = vNode.props for (const key in props) { const value = props[key] element.setAttribute(key, value) } vNode.children && vNode.children( child => { const childElement = typeof child === 'string' ? document.createTextNode(child) : render(child) element.appendChild(childElement) }) return element } export default render
const vpatch = {} vpatch.REMOVE = 0 vpatch.REPLACE = 1 // node replace vpatch.TEXT = 2 // text replace vpatch.PROPS = 3 vpatch.INSERT = 4 vpatch.REORDER = 5 export default vpatch
/** * 二叉树 diff * @param lastVNode * @param newVNode */ function diff (lastVNode, newVNode) { let index = 0 const patches = {} // patches.old = lastVNode dftWalk(lastVNode, newVNode, index, patches) return patches } /** * 深入优先遍历算法 (depth-first traversal,DFT) * @param {*} lastVNode * @param {*} newVNode * @param {*} index * @param {*} patches */ function dftWalk(lastVNode, newVNode, index, patches) { if (lastVNode === newVNode) { return } const currentPatch = [] // Node is removed if (newVNode === null) { currentPatch.push({ type: patch.REMOVE }) // diff text } else if (_.isString(lastVNode) && _.isString(newVNode)) { if (newVNode !== lastVNode) { currentPatch.push({ type: patch.TEXT, text: newVNode }) } // same node 此处会出行,parentNode 先 moves 处理,childnode 再做一次处理(替换或修改属性) } else if ( newVNode.tagName === lastVNode.tagName // && newVNode.key === lastVNode.key ) { // newVNode.key === lastVNode.key 才会执行 diffChildren if (newVNode.key === lastVNode.key) { const propsPatches = diffProps(lastVNode.props, newVNode.props) if (Object.keys(propsPatches).length > 0) { currentPatch.push({ type: patch.PROPS, props: propsPatches }) } diffChildren( lastVNode.children, newVNode.children, currentPatch, index, patches, ) } else { currentPatch.push({ type: patch.REPLACE, node: newVNode }) } // Nodes are not the same } else { currentPatch.push({ type: patch.REPLACE, node: newVNode }) } if (currentPatch.length) { patches[index] = currentPatch } } function diffChildren (lastChildren, newChildren, apply, index, patches) { const orderedSet = reorder(lastChildren, newChildren) let len = lastChildren.length > newChildren.length ? lastChildren.length : newChildren.length for (var i = 0; i < len; i++) { if (!lastChildren[i]) { // insert node if (newChildren[i] && !orderedSet.moves) { apply.push({ type: patch.INSERT, node: newChildren[i] }) } } else { dftWalk(lastChildren[i], newChildren[i], ++index, patches) } } console.error('orderedSet.moves', orderedSet.moves) if (orderedSet.moves) { apply.push(orderedSet) } } /** * diff vnode props * @param {*} lastProps * @param {*} newProps */ function diffProps (lastProps, newProps) { const propsPatches = {} // Find out diff props for (const key in lastProps) { if (newProps[key] !== lastProps[key]) { propsPatches[key] = newProps[key] } } // Find out new props for (const key in newProps) { if (!lastProps.hasOwnProperty(key)) { propsPatches[key] = newProps[key] } } return propsPatches } /** * List diff, naive left to right reordering * @param {*} lastChildren * @param {*} newChildren * * 原理利用中间数组 simulate, remove得到子集、insert 插入操作完成 * 例 oldList [1,4,6,8,9] newList [0,1,3,5,6] * 转换拿到中间数组按老数组索引 [1, null, 6, null, null ] * remove null 得到子集 [1, 6] * insert 插入完成 */ function reorder(lastChildren, newChildren) { const lastMap = keyIndex(lastChildren) const lastKeys = lastMap.keys const lastFree = lastMap.free if(lastFree.length === lastChildren.length){ return { moves: null } } const newMap = keyIndex(newChildren) const newKeys = newMap.keys const newFree = newMap.free if(newFree.length === newChildren.length){ return { moves: null } } // simulate list to manipulate const children = [] let freeIndex = 0 for (let i = 0 ; i < lastChildren.length; i++) { const item = lastChildren[i] if(item.key){ if(newKeys.hasOwnProperty('key')){ const itemIndex = newKeys[item.key] children.push(newChildren[itemIndex]) } else { children.push(null) } } else { const itemIndex = newFree[freeIndex++] children.push(newChildren[itemIndex] || null) } } const simulate = children.slice() const removes = [] const inserts = [] let j = 0 // remove value is null and no key property while (j < simulate.length) { if (simulate[j] === null || !simulate[j].hasOwnProperty('key')) { const patch = remove(simulate, j) removes.push(patch) } else { j++ } } console.error('simulate', simulate) for (let i = 0 ; i < newChildren.length; i++) { const wantedItem = newChildren[i] const simulateItem = simulate[i] if(wantedItem.key){ if(simulateItem && wantedItem.key !== simulateItem.key){ // key property is not equal, insert, simulateItem add placeholder inserts.push({ type: patch.INSERT, index: i, node: wantedItem, }) simulateItem.splice(i, 1) } } else { // no key property, insert, simulateItem add placeholder inserts.push({ type: patch.INSERT, index: i, node: wantedItem, }) simulateItem && simulateItem.splice(i, 1) } } return { type: patch.REORDER, moves: { removes: removes, inserts: inserts } } } function remove(arr, index) { arr.splice(index, 1) return { type: patch.REMOVE, index, } } /** * Convert list to key-item keyIndex object. * @param {*} children * convert [{id: "a", key: 'a'}, {id: "b", key: 'b'}, {id: "a"}] * result { keys: { a: 0, b: 1}, free: [ 2 ] } */ function keyIndex(children) { var keys = {} var free = [] var length = children.length for (var i = 0; i < length; i++) { var child = children[i] if (child.key) { keys[child.key] = i } else { free.push(i) } } return { keys: keys, // A hash of key name to index free: free // An array of unkeyed item indices } } export default diff
{ "0": [ { "type": 3, "props": { "className": "zz", "height": "20px" } }, { "type": 5, "moves": { "removes": [ { "type": 0, "index": 0 }, { "type": 0, "index": 0 } ], "inserts": [ { "type": 4, "index": 1, "node": { "tagName": "li", "props": { "className": "one" }, "children": [ "one" ] } } ] } } ], "1": [ { "type": 5, "moves": { "removes": [ { "type": 0, "index": 0 }, { "type": 0, "index": 0 } ], "inserts": [ { "type": 4, "index": 2, "node": { "tagName": "li", "props": { "className": "ooo" }, "children": [ "插入节点" ] } } ] } } ], "2": [ { "type": 1, "node": { "key": "1", "tagName": "li", "props": { "className": "teext" }, "children": [ "哈咯" ] } } ], "3": [ { "type": 1, "node": { "key": "2", "tagName": "li", "props": { "className": "zz" }, "children": [ "大家好" ] } } ] }
import patch from './vpatch.js' import render from './render.js' /** * 真实的 Dom 打补钉 * @param {*} rootNode 实际的 DOM * @param {*} patches */ function patch (rootNode, patches) { const walker = { index: 0 } dftWalk(rootNode, walker, patches) } /** * 深入优先遍历算法 (depth-first traversal,DFT) * @param {*} node * @param {*} walker * @param {*} patches */ function dftWalk (node, walker, patches) { const currentPatches = patches[walker.index] || {} node.childNodes && node.childNodes.forEach(child => { walker.index++ dftWalk(child, walker, patches) }) if (currentPatches) { applyPatches(node, currentPatches) } } function applyPatches (node, currentPatches) { currentPatches.forEach(currentPatch => { switch (currentPatch.type) { case patch.REMOVE: node.parentNode.removeChild(node) break case patch.REPLACE: const newNode = currentPatch.node node.parentNode.replaceChild(render(newNode), node) break case patch.TEXT: node.textContent = currentPatch.text break case patch.PROPS: const props = currentPatch.props setProps(node, props) break case patch.INSERT: // parentNode.insertBefore(newNode, referenceNode) const newNode = currentPatch.node node.appendChild(render(newNode)) break case patch.REORDER: reorderChildren(node, currentPatch.moves) break } }) } /** * 设置真实 Dom 属性值 * @param {*} node * @param {*} props */ function setProps (node, props) { for (const key in props) { // void 666 is undefined if (props[key] === void 666) { node.removeAttribute(key) } else { const value = props[key] node.setAttribute(key, value) } } } /** * reorderChildren 处理 list diff render * @param {*} domNode * @param {*} moves */ function reorderChildren(domNode, moves) { for (const i = 0; i < moves.removes.length; i++) { const { index } = moves.removes[i] const node = domNode.childNodes[index] domNode.removeChild(node) } for (const j = 0; j < moves.inserts.length; j++) { const { index, node } = moves.inserts[j] domNode.insertBefore(node, index === domNode.childNodes.length ? null : childNodes[index]) } }
树的广度优先遍历和深度优先遍历
React diff
React’s diff algorithm
snabbdom A virtual DOM library'
浅析虚拟dom原理并实现
virtual-dom--A Virtual DOM and diffing algorithm
simple-virtual-dom
React源码分析与实现(三):实操DOM Diff
深度剖析:如何实现一个 Virtual DOM 算法
fast-diff
React Fiber实现原理
React Fiber为什么使用链表来设计组件树
文章很赞👍,收益匪浅
步骤二:渲染 Virtual Dom 代码中 应该是element.setAttribute 吧
element.setAttribute
React 核心知识点 -- Virtual Dom 与 Diff
React 最值得称道部分就是 Virtual DOM 和 Diff ,这两块核心点方便我们更好的抽象化的开发组件,提高渲染效率。
Virtual Dom
Virtual DOM 是一种编程概念。在这个概念里, UI 以一种理想化的,或者说“虚拟的 DOM TREE”表现形式被保存于内存中,并通过如 ReactDOM 等类库使之与“真实的” DOM 同步。
创建 Virtual Dom
React 中此部分 JSX 语法糖,通过 plugin-transform-react-jsx 转换为
React.createElement
函数的语法糖:Diff 遍历算法
遍历 Tree Dom 结构,涉及常用数据算法: 广度优先搜索(breadth-first search,BFS),广度优先遍历(breadth-first traversal,BFT), 深度优先遍历(depth-first traversal,DFT)。笔者这里只讨论:广度优先遍历(breadth-first traversal,BFT), 深度优先遍历(depth-first traversal,DFT)。
广度优先遍历(breadth-first traversal,BFT)
广度优先遍历(BFT breadth-first traversal):广度优先遍历是连通图的一种遍历策略,它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。树的广度优先遍历是指优先遍历完某一层的所有节点,然后再依次向下层遍历。
步骤:
广度优先算法的的非递归实现:
深度优先遍历(depth-first traversal,DFT)
深度优先遍历(DFT depth-first traversal):树的深度优先遍历是指首先遍历树的某个分支上的所有节点,在遍历另一个分支的节点,对于节点中的分支也这样处理。React 中 Dom Diff 采用的深度优先遍历算法,至于React 为何不使用广度优先遍历得到的答案是可能会导致组件的生命周期乱套。
步骤:
深度优先算法的递归实现:
深度优先算法的非递归实现:
React dom diff 算法
传统 diff 算法
计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法 通过循环递归对节点进行依次对比,效率低下,算法复杂度达到
O(n^3)
,其中 n 是树中节点的总数。O(n^3)
到底有多可怕,这意味着如果要展示 1000 个节点,就要依次执行上十亿次的比较。这个开销实在是太过高昂。现今的 CPU 每秒钟能执行大约30亿条指令,即便是最高效的实现,也不可能在一秒内计算出差异情况。如果 React 只是单纯的引入 diff 算法而没有任何的优化改进,那么其效率是远远无法满足前端渲染所要求的性能。
那么,React diff 到底是如何实现的稳定高效的 diff 呢?
详解 React diff
传统 diff 算法的复杂度为 O(n^3),显然这是无法满足性能要求的。React 通过制定大胆的策略,将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。
diff 策略
基于以上三个前提策略,React 分别对 tree diff、component diff 以及 element diff 进行算法优化,事实也证明这三个前提策略是合理且准确的,它保证了整体界面构建的性能。
tree diff
基于策略一,React 对树的算法进行了简洁明了的优化,即对树进行分层比较,两棵树只会对同一层次的节点进行比较。
既然 DOM 节点跨层级的移动操作少到可以忽略不计,针对这一现象,React 通过 updateDepth 对 Virtual DOM 树进行层级控制,只会对相同颜色方框内的 DOM 节点进行比较,即同一个父节点下的所有子节点。当发现节点已经不存在,则该节点及其子节点会被完全删除掉,不会用于进一步的比较。这样只需要对树进行一次遍历,便能完成整个 DOM 树的比较。
component diff
React 是基于组件构建应用的,对于组件间的比较所采取的策略也是简洁高效。
element diff
当节点处于同一层级时,React diff 提供了三种节点操作,分别为:INSERT_MARKUP(插入)、MOVE_EXISTING(移动)、TEXT_CONTENT(文本内容)、REMOVE_NODE(删除)。
算法实现
步骤一: 创建 Virtual Dom
步骤二:渲染 Virtual Dom
步骤三:Dom Diff
步骤四:收集 patchs
步骤五:更新 patchs,把差异应用到真正的DOM树上
Other Resources
树的广度优先遍历和深度优先遍历
React diff
React’s diff algorithm
snabbdom A virtual DOM library'
浅析虚拟dom原理并实现
virtual-dom--A Virtual DOM and diffing algorithm
simple-virtual-dom
React源码分析与实现(三):实操DOM Diff
深度剖析:如何实现一个 Virtual DOM 算法
fast-diff
React Fiber实现原理
React Fiber为什么使用链表来设计组件树