Подробная серия о происхождении фреймворка — Virtual Dom

внешний интерфейс алгоритм JavaScript React.js

Зачем вам виртуальный дом

Как мы все знаем, манипулирование DOM — это очень требовательная к производительности вещь.В этом случае мы можем рассмотреть возможность имитации объектов DOM через объекты JS.В конце концов, манипулирование объектами JS намного экономит время, чем манипулирование DOM.

Например

// 假设这里模拟一个 ul，其中包含了 5 个 li
[1, 2, 3, 4, 5] 
// 这里替换上面的 li
[1, 2, 5, 4]

Из приведенного выше примера видно, что третий li в предыдущем ul был удален, а четвертый и пятый заменены.

Если вышеуказанные операции соответствуют DOM, то следующий код

// 删除第三个 li
ul.childNodes[2].remove()
// 将第四个 li 和第五个交换位置
let fromNode = ul.childNodes[4]
let toNode = node.childNodes[3]
let cloneFromNode = fromNode.cloneNode(true)
let cloenToNode = toNode.cloneNode(true)
ul.replaceChild(cloneFromNode, toNode)
ul.replaceChild(cloenToNode, fromNode)

Конечно, в реальной работе нам также нужно дать каждому узлу идентификатор, чтобы можно было судить, что это один и тот же узел. Так что это также единственный узел, используемый в официальном списке рекомендаций в Vue и React.keyдля обеспечения производительности.

Таким образом, поскольку объект DOM может быть смоделирован объектом JS, и наоборот, соответствующий объект DOM также может быть отображен объектом JS.

Ниже приведена простая реализация объекта JS, который имитирует объект DOM.

export default class Element {
  /**
   * @param {String} tag 'div'
   * @param {Object} props { class: 'item' }
   * @param {Array} children [ Element1, 'text']
   * @param {String} key option
   */
  constructor(tag, props, children, key) {
    this.tag = tag
    this.props = props
    if (Array.isArray(children)) {
      this.children = children
    } else if (isString(children)) {
      this.key = children
      this.children = null
    }
    if (key) this.key = key
  }
  // 渲染
  render() {
    let root = this._createElement(
      this.tag,
      this.props,
      this.children,
      this.key
    )
    document.body.appendChild(root)
    return root
  }
  create() {
    return this._createElement(this.tag, this.props, this.children, this.key)
  }
  // 创建节点
  _createElement(tag, props, child, key) {
    // 通过 tag 创建节点
    let el = document.createElement(tag)
    // 设置节点属性
    for (const key in props) {
      if (props.hasOwnProperty(key)) {
        const value = props[key]
        el.setAttribute(key, value)
      }
    }
    if (key) {
      el.setAttribute('key', key)
    }
    // 递归添加子节点
    if (child) {
      child.forEach(element => {
        let child
        if (element instanceof Element) {
          child = this._createElement(
            element.tag,
            element.props,
            element.children,
            element.key
          )
        } else {
          child = document.createTextNode(element)
        }
        el.appendChild(child)
      })
    }
    return el
  }
}

Краткое введение в алгоритм Virtual Dom

Теперь, когда мы реализовали DOM с помощью моделирования JS, следующая трудность заключается в том, как оценить разницу между старым объектом и новым объектом.

DOM представляет собой многодревовидную структуру, и если вам нужно полностью сравнить различия между двумя деревьями, требуемая временная сложность будет O(n ^ 3), что определенно неприемлемо. Поэтому команда React оптимизировала алгоритм и добилась сложности O(n) для сравнения различий.

Ключом к достижению сложности O(n) является сравнение только узлов на одном уровне, а не сравнение между уровнями.Это также с учетом того, что в реальном бизнесе элементы DOM редко перемещаются между уровнями.

Таким образом, алгоритм оценки разницы делится на два шага.

  • Во-первых, обход объекта сверху вниз и слева направо, то есть обход дерева в глубину, На этом этапе к каждому узлу будет добавлен индекс, чтобы облегчить окончательный рендеринг разницы.
  • Когда у узла есть дочерние элементы, проверьте, отличаются ли дочерние элементы.

Реализация алгоритма виртуального дома

рекурсия деревьев

Во-первых, давайте реализуем рекурсивный алгоритм дерева.Перед реализацией алгоритма рассмотрим несколько ситуаций, в которых сравниваются два узла.

  1. новый узелtagNameилиkeyВ отличие от старой, эта ситуация означает, что старый узел нужно заменить, и больше не нужно обходить дочерние элементы старого и нового узлов, потому что старый узел удаляется целиком.
  2. новый узелtagNameа такжеkey(вероятно, нет) так же, как и раньше, начать обход поддерева
  3. нет новых узлов, то ничего не делать
import { StateEnums, isString, move } from './util'
import Element from './element'

export default function diff(oldDomTree, newDomTree) {
  // 用于记录差异
  let pathchs = {}
  // 一开始的索引为 0
  dfs(oldDomTree, newDomTree, 0, pathchs)
  return pathchs
}

function dfs(oldNode, newNode, index, patches) {
  // 用于保存子树的更改
  let curPatches = []
  // 需要判断三种情况
  // 1.没有新的节点，那么什么都不用做
  // 2.新的节点的 tagName 和 `key` 和旧的不同，就替换
  // 3.新的节点的 tagName 和 key（可能都没有） 和旧的相同，开始遍历子树
  if (!newNode) {
  } else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {
    // 判断属性是否变更
    let props = diffProps(oldNode.props, newNode.props)
    if (props.length) curPatches.push({ type: StateEnums.ChangeProps, props })
    // 遍历子树
    diffChildren(oldNode.children, newNode.children, index, patches)
  } else {
    // 节点不同，需要替换
    curPatches.push({ type: StateEnums.Replace, node: newNode })
  }

  if (curPatches.length) {
    if (patches[index]) {
      patches[index] = patches[index].concat(curPatches)
    } else {
      patches[index] = curPatches
    }
  }
}

Оценка изменений собственности

Изменение атрибута суждения также делится на три этапа.

  1. Повторите старый список свойств, чтобы увидеть, существует ли каждое свойство в новом списке свойств.
  2. Просмотрите новый список атрибутов, чтобы определить, изменилось ли значение атрибута, существующего в обоих списках.
  3. Проверьте, не существует ли свойство во втором шаге со старым списком атрибутов столбца.
function diffProps(oldProps, newProps) {
  // 判断 Props 分以下三步骤
  // 先遍历 oldProps 查看是否存在删除的属性
  // 然后遍历 newProps 查看是否有属性值被修改
  // 最后查看是否有属性新增
  let change = []
  for (const key in oldProps) {
    if (oldProps.hasOwnProperty(key) && !newProps[key]) {
      change.push({
        prop: key
      })
    }
  }
  for (const key in newProps) {
    if (newProps.hasOwnProperty(key)) {
      const prop = newProps[key]
      if (oldProps[key] && oldProps[key] !== newProps[key]) {
        change.push({
          prop: key,
          value: newProps[key]
        })
      } else if (!oldProps[key]) {
        change.push({
          prop: key,
          value: newProps[key]
        })
      }
    }
  }
  return change
}

Реализация алгоритма отличия списка суждений

Этот алгоритм является основным алгоритмом всего виртуального дома, и позвольте мне рассказать вам по порядку. Основные шаги здесь на самом деле аналогичны оценке различий атрибутов и также разделены на три этапа.

  1. Просмотрите старый список узлов, чтобы увидеть, существует ли каждый узел в новом списке узлов.
  2. Пройдитесь по списку новых узлов, чтобы определить, есть ли новый узел.
  3. На втором шаге одновременно определяем, переместился ли узел

PS: Этот алгоритм подходит только дляkeyузел для обработки

function listDiff(oldList, newList, index, patches) {
  // 为了遍历方便，先取出两个 list 的所有 keys
  let oldKeys = getKeys(oldList)
  let newKeys = getKeys(newList)
  let changes = []

  // 用于保存变更后的节点数据
  // 使用该数组保存有以下好处
  // 1.可以正确获得被删除节点索引
  // 2.交换节点位置只需要操作一遍 DOM
  // 3.用于 `diffChildren` 函数中的判断，只需要遍历
  // 两个树中都存在的节点，而对于新增或者删除的节点来说，完全没必要
  // 再去判断一遍
  let list = []
  oldList &&
    oldList.forEach(item => {
      let key = item.key
      if (isString(item)) {
        key = item
      }
      // 寻找新的 children 中是否含有当前节点
      // 没有的话需要删除
      let index = newKeys.indexOf(key)
      if (index === -1) {
        list.push(null)
      } else list.push(key)
    })
  // 遍历变更后的数组
  let length = list.length
  // 因为删除数组元素是会更改索引的
  // 所有从后往前删可以保证索引不变
  for (let i = length - 1; i >= 0; i--) {
    // 判断当前元素是否为空，为空表示需要删除
    if (!list[i]) {
      list.splice(i, 1)
      changes.push({
        type: StateEnums.Remove,
        index: i
      })
    }
  }
  // 遍历新的 list，判断是否有节点新增或移动
  // 同时也对 `list` 做节点新增和移动节点的操作
  newList &&
    newList.forEach((item, i) => {
      let key = item.key
      if (isString(item)) {
        key = item
      }
      // 寻找旧的 children 中是否含有当前节点
      let index = list.indexOf(key)
      // 没找到代表新节点，需要插入
      if (index === -1  || key == null) {
        changes.push({
          type: StateEnums.Insert,
          node: item,
          index: i
        })
        list.splice(i, 0, key)
      } else {
        // 找到了，需要判断是否需要移动
        if (index !== i) {
          changes.push({
            type: StateEnums.Move,
            from: index,
            to: i
          })
          move(list, index, i)
        }
      }
    })
  return { changes, list }
}

function getKeys(list) {
  let keys = []
  let text
  list &&
    list.forEach(item => {
      let key
      if (isString(item)) {
        key = [item]
      } else if (item instanceof Element) {
        key = item.key
      }
      keys.push(key)
    })
  return keys
}

Обход дочерних элементов для маркировки

Для этой функции основными функциями являются две

  1. Определить разницу между двумя списками
  2. отметить узел

В целом, функция, реализованная этой функцией, очень проста.

function diffChildren(oldChild, newChild, index, patches) {
  let { changes, list } = listDiff(oldChild, newChild, index, patches)
  if (changes.length) {
    if (patches[index]) {
      patches[index] = patches[index].concat(changes)
    } else {
      patches[index] = changes
    }
  }
  // 记录上一个遍历过的节点
  let last = null
  oldChild &&
    oldChild.forEach((item, i) => {
      let child = item && item.children
      if (child) {
        index =
          last && last.children ? index + last.children.length + 1 : index + 1
        let keyIndex = list.indexOf(item.key)
        let node = newChild[keyIndex]
        // 只遍历新旧中都存在的节点，其他新增或者删除的没必要遍历
        if (node) {
          dfs(item, node, index, patches)
        }
      } else index += 1
      last = item
    })
}

Различия в рендеринге

С помощью предыдущего алгоритма мы уже можем нарисовать разницу между двумя деревьями. Теперь, когда мы знаем разницу, нам нужно локально обновить DOM Давайте взглянем на последний шаг алгоритма Virtual Dom.

Эта функция имеет две основные функции

  1. Пройдите глубоко по дереву и вытащите те, которые нужно изменить.
  2. Обновите DOM локально

В целом, эта часть кода по-прежнему очень проста для понимания.

let index = 0
export default function patch(node, patchs) {
  let changes = patchs[index]
  let childNodes = node && node.childNodes
  // 这里的深度遍历和 diff 中是一样的
  if (!childNodes) index += 1
  if (changes && changes.length && patchs[index]) {
    changeDom(node, changes)
  }
  let last = null
  if (childNodes && childNodes.length) {
    childNodes.forEach((item, i) => {
      index =
        last && last.children ? index + last.children.length + 1 : index + 1
      patch(item, patchs)
      last = item
    })
  }
}

function changeDom(node, changes, noChild) {
  changes &&
    changes.forEach(change => {
      let { type } = change
      switch (type) {
        case StateEnums.ChangeProps:
          let { props } = change
          props.forEach(item => {
            if (item.value) {
              node.setAttribute(item.prop, item.value)
            } else {
              node.removeAttribute(item.prop)
            }
          })
          break
        case StateEnums.Remove:
          node.childNodes[change.index].remove()
          break
        case StateEnums.Insert:
          let dom
          if (isString(change.node)) {
            dom = document.createTextNode(change.node)
          } else if (change.node instanceof Element) {
            dom = change.node.create()
          }
          node.insertBefore(dom, node.childNodes[change.index])
          break
        case StateEnums.Replace:
          node.parentNode.replaceChild(change.node.create(), node)
          break
        case StateEnums.Move:
          let fromNode = node.childNodes[change.from]
          let toNode = node.childNodes[change.to]
          let cloneFromNode = fromNode.cloneNode(true)
          let cloenToNode = toNode.cloneNode(true)
          node.replaceChild(cloneFromNode, toNode)
          node.replaceChild(cloenToNode, fromNode)
          break
        default:
          break
      }
    })
}

наконец

Алгоритм реализации Virtual Dom состоит из следующих трех шагов.

  1. Имитация создания объектов DOM через JS
  2. Определить разницу между двумя объектами
  3. Различия в рендеринге
let test4 = new Element('div', { class: 'my-div' }, ['test4'])
let test5 = new Element('ul', { class: 'my-div' }, ['test5'])

let test1 = new Element('div', { class: 'my-div' }, [test4])

let test2 = new Element('div', { id: '11' }, [test5, test4])

let root = test1.render()

let pathchs = diff(test1, test2)
console.log(pathchs)

setTimeout(() => {
  console.log('开始更新')
  patch(root, pathchs)
  console.log('结束更新')
}, 1000)

Конечно, текущая реализация все еще немного грубовата, но этого достаточно для понимания алгоритма Виртуального дома.

Вы можете найти код в статье наздесьчитать. Обновленные статьи этой серии будут обновляться в этом репозитории, кому интересно, могут обратить внимание.

Содержанием следующей статьи будет управление состоянием, так что следите за обновлениями.

Наконец, прикрепите мой общедоступный номер

Категории