likes
comments
collection
share

关于diff算法的学习

作者站长头像
站长
· 阅读数 80

前言

diff算法在前端框架中(vue、react...)非常常见，近期对该算法进行了学习，分享一下学习的心得和过程，若有不足之处请各位看官大佬批评指正(#^.^#)

  • 目的：对比新老dom，以最小的代价更新dom
  • 特点：
    1. 平级对比，降低复杂度，diff算法复杂度是 O(n)。关于复杂度可以参考聊聊 Vue 的双端 diff 算法
    2. 深度优先
    3. 先序遍历
  • 主要过程（参考：让虚拟DOM和DOM-diff不再成为你的绊脚石）：
    1. js对象(类似vue的render函数)-->虚拟dom
    2. 虚拟dom-->真实dom
    3. diff：若修改了虚拟dom，则比较两棵虚拟dom树的差别，得到补丁
    4. 将补丁打入到真实dom中
  • 项目地址-dev

项目结构

关于diff算法的学习

虚拟dom的实现

1. 目标

首先我们通过一张图表示出我们目标dom树 关于diff算法的学习 所生成的dom树为下图 关于diff算法的学习

2. 代码实现

将上图转换为代码，其中createElement函数相当于vue中的render函数

const vDom1 = createElement('ul', { class: 'list',
  style: "width: 300px;height: 300px;background-color: orange"
}, [
  createElement('li', { class: 'item','data-index':0 },
   [createElement('p',{class: 'text'},['第一个列表项'])
  ]),
  createElement('li', { class: 'item','data-index': 1 }, 
  [createElement('p',{class: 'text'},[
    createElement('span',{class:'title'},[])])
  ]),
  createElement('li',{class: 'item','data-index': 2 },['第三个列表项'])
])

createElement函数实现其实非常的简单

// 创建虚拟dom
function createElement(tag, props, children) {
  return new Element(tag, props, children)
}

// 创建元素类
class Element {
  constructor(tag, props, children) {
    this.tag = tag
    this.props = props
    this.children = children
  }
}

3. 代码解析

创建出的每个虚拟dom节点都是Element类的实例或是文本，具有三个属性：标签(tag)、属性(props)和子节点(children)

虚拟dom渲染成真实dom

1. 目标

解析虚拟dom每个节点的标签和属性，创建真实dom

2. 代码实现

// 创建真实dom
function render(vDom) {
  const {tag,props,children} = vDom
  const dom = document.createElement(tag)
  for(let key in props){
    // 赋予属性
    setAttr(dom,key,props[key])
  }
  if(children&&children.length){
    children.forEach(child=>{
      const childDom = child instanceof Element?render(child):document.createTextNode(child)
      // 将创建的节点放置
      dom.appendChild(childDom)
    })
  }
  return dom
}

// 赋予属性
function setAttr(dom,key,value){
  const tagName = dom.tagName.toLowerCase()
  switch (key){
    // 输入框的值
    case 'value':
      if(agName === 'input'||tagName === 'textarea'){
        dom.value = value
      }else {
        dom.setAttribute(key,value)
      }
    break
    // 样式
    case 'style':
      dom.style.cssText = value
    break
    // 默认设置属性
    default: 
    dom.setAttribute(key,value)
  }
}

// 渲染dom，在入口文件调用该方法，将渲染出的真实节点挂载至app
function renderDom(el,target){
  target.appendChild(el)
}

3. 代码解析

  • 解析生成虚拟dom：
    1. 根据标签tag创建节点；
    2. 遍历属性props，使用setAttr方法处理属性值；
    3. 遍历孩子children，若子节点是Element的实例，则进行递归，不是则为文本节点
  • 属性解析setAttr方法：
    1. 在输入框中的value属性，需要特殊处理
    2. style样式属性需要特殊处理
    3. 其他的属性都可以使用js提供的setAttribute方法进行实现

diff算法

千呼万唤始出来，终于到了亲爱的diff算法

1. 目标

我们要在原先的虚拟dom树上进行修改，其次需要diff算法找出变化项（补丁），具体变化如下图所示，标绿色的是更改过的dom节点 关于diff算法的学习 我们需要使用diff算法生成以下补丁对象，key是每一个节点对应的index，value是一个该节点需要补丁的数组 关于diff算法的学习

2. 代码实现

一般一个dom节点有四种变化类型，remove-->dom节点删除；text-->文本变更；replace-->dom节点替换；attr-->dom节点属性值变更

const REMOVE = 'remove',
  TEXT = 'text',
  REPLACE = 'replace',
  ATTR = 'attr'

以下是对每个节点进行同级比较，获取补丁对象

// 遍历dom的index
let diffIndex = 0

// diff算法
function domDiff(oldVDom, newVDom) {
  // 返回的补丁
  const patches = {}
  // 初始的树index
  let index = 0
  // 递归函数
  diffWalk(oldVDom, newVDom, index, patches)
  return patches
}

function diffWalk(oldVDom, newVDom, index, patches) {
  // 该节点的补丁
  let patchList = []
  if (!newVDom) {
    // 新节点被删除(无子节点)
    patchList.push({
      type: REMOVE,
      index
    })
    if(oldVDom.children) {
      // 被删除子节点的孩子不遍历
      oldVDom.children = []
    }
  }else if(isString(newVDom)&&isString(oldVDom)){
    // 文本替换(无子节点)
    if(newVDom !== oldVDom){
      patchList.push({
        type: TEXT,
        text: newVDom
      })
    }
  }else if(newVDom.tag === oldVDom.tag){
    // 生成diff属性对象
    let props = diffAttr(oldVDom.props,newVDom.props)
    if(Object.keys(props).length>0){
      patchList.push({
        type: ATTR,
        attr: props
      })
    }
    // 遍历子节点
    diffChildren(oldVDom.children,newVDom.children,patches)
  }else {
    // 标签不一致，被新节点替代
    patchList.push({
      type: REPLACE,
      node: newVDom
    })
  }
  if(patchList.length >0){
    // 若存在不定数组，则将其放进大补丁
    patches[index] = patchList
  }
}

// 字符串判断
function isString(str){
  return typeof str === 'string'
}

// 属性修改
function diffAttr(oldProps,newProps){
  // 目的：生成一个dom属性改变部分的对象
  const attr = {}
  for(let key in oldProps){
    // 修改：同key不同value则更新
    if(oldProps[key] !== newProps[key]){
      attr[key] = newProps[key]
    }
  }
  for(let key in newProps){
    // 新增
    if(!oldProps.hasOwnProperty(key)){
      attr[key] = newProps[key]
    }
  }
  return attr
}
// 子节点遍历
function diffChildren(oldNode,newNode,patches){
  oldNode.map((item,idx)=>{
    diffWalk(item,newNode[idx],++diffIndex,patches)
  })
}

3. 代码解析

  • diffIndex是用于保存整个dom树当前进行diff算法的节点index，patches是diff算法需要输出的整个补丁，index是初始化的index，就是第一个比较的dom
  • 我们使用diffWalk方法对整个dom树进行递归遍历
  • diffWalk方法针对当前所比较的节点进行操作：
    1. patchList保存的是该节点所有的变化，即该节点的补丁
    2. 根据4种变化类型，对新旧节点的对比进行判定
    3. 若patchList有值，说明该节点是有变化的，存在补丁，将其放入大补丁包patches中
  • 新旧节点的判定过程，对应上述操作的2：
    1. remove：newDom不存在则说明该节点被移除，若该节点被移除，其子节点则不进行diff算法
    2. text：如果newDom和oldDom都为文本且不相等，则说明文本进行了修改
    3. attr：如果newDom和oldDom的标签相等，则使用diffAttr方法检测属性是否有变化；若新旧节点标签相等，则使用diffChildren方法对其各自子节点进行遍历（深度优先）
    4. replace：如果newDom和oldDom标签不一致，则说明旧节点已经被新节点替代
  • 属性检测--diffAttr方法：
    1. 声明attr--属性补丁
    2. 更新：遍历oldProps对象，如果新旧节点的同名属性值不一致则将新节点的属性值存入attr
    3. 新增：遍历newProps对象，若key值不存在与oldProps中，则将新节点的属性值存入attr
  • 子节点遍历--diffChildren方法：
    1. 遍历oldNode（旧子节点数组），与新节点数组对应idx进行对比（同层对比）
    2. ++diffIndex说明需要将diffIndex先加1后，diffIndex才是当前新旧节点的索引。因为节点为0的时候已经进行过了diff操作，即中序遍历

打补丁patch

实际上跟diff算法差不多，同样是递归遍历，

1. 目标

生成变化后的虚拟dom

2. 代码实现

// 大补丁
let finalPatch = {}
// 当前遍历dom的id
let index = 0

// 打补丁
function doPatch(rDom,patch) {
  finalPatch = patch
  patchWalk(rDom)
  return rDom
}

// 节点遍历，从根节点开始
function patchWalk(rNode){
  // 获取该节点对应的补丁
  let rnPatch = finalPatch[index++],
        childNodes = rNode.childNodes;
  // 遍历孩子
  [...childNodes].map(item=>{
    patchWalk(item)
  })
  if(rnPatch){
    // 给该节点打补丁
    patchAction(rNode,rnPatch)
  }
}

function patchAction(rNode,rnPatch) {

  rnPatch.forEach(item=>{
    switch (item.type){
      case REMOVE:
        // 去除
        rNode.parentNode.removeChild(rNode)
      break
      case TEXT:
        // 文本变化
        rNode.textContent = item.text
      break
      case REPLACE:
        // 节点代替
        const replaceDom = item.node instanceof Element ? 
        render(item.node) : document.createTextNode(item.node)
        rNode.parentNode.replaceChild(replaceDom,rNode)
      break
      case ATTR:
        // 属性更新
        for(let key in item.attr){
          setAttr(rNode,key,item.attr[key])
        }
      break
      default:
        break
    }
  })
}

3. 代码解析

  • 对真实节点rDom进行遍历
  • dom节点的子节点是类数组，需要扩展运算符转换为真实数组
  • patchAction方法是根据4个操作进行解析：
    1. remove：使用removeChild将其自身去除
    2. text：更改节点的textContent
    3. replace： 检查该补丁的node是否是Element的实例，是则渲染节点，不是则创建文本节点。使用replaceChild替换dom节点
    4. attr：更新属性

总结

今天就写到这里啦，文章较长，感谢各位看官的耐心浏览

  • 最后再次说一下4个步骤：

    1. js对象(类似vue的render函数)-->虚拟dom
    2. 虚拟dom-->真实dom
    3. diff：若修改了虚拟dom，则比较两棵虚拟dom树的差别，得到补丁
    4. 将补丁打入到真实dom中

  • 墙裂推荐b站up主：小野森森，他有对diff算法进行深入说明，本文都是参考了小野老师讲解的视频

  • 如有问题可留言讨论

转载自:https://juejin.cn/post/7159486064917708808
评论
请登录