Алгоритм и принцип сравнения Vue 3.0

Vue.js

Алгоритм сравнения, принятый в Vue 3.0, немного отличается от двустороннего сравнения 2.0. Общий принцип следующий

// c1: a b [ c d e ] f g  
// c2: a b [ d e c h ] f g

Если есть старые и новые дочерние элементы c1 и c2, как указано выше, при различении будет выполняться процесс предварительной обработки.

Сначала сравните спереди назад, когда узлы разные, не сравнивайте в обратном порядке. Затем сравнение выполняется сзади к началу, когда узлы разные, сравнение вперед не выполняется.

После предварительной обработки части c1 и c2, которые действительно нужно различать, выглядят следующим образом:

// c1: c d e
// c2: d e c h

Наконец, «самая длинная возрастающая подпоследовательность» используется для завершения сравнения вышеуказанных разностных частей и повышения эффективности разности.

Обработка одних и тех же передних и задних узлов

Код предварительной обработки выглядит следующим образом:

const patchKeyedChildren = (
    c1,
    c2,
    container,
    parentAnchor,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized
) => {
    let i = 0;  
    const l2 = c2.length
    let e1 = c1.length - 1
    let e2 = c2.length - 1

    // 1. sync from start
    while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = c2[i]
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          parentAnchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
      } else {
        break
      }
      i++
    }

    // 2. sync from end
    while (i <= e1 && i <= e2) {
      const n1 = c1[e1]
      const n2 = c2[e2]
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          parentAnchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
      } else {
        break
      }
      e1--
      e2--
    }
}

Добавляются или удаляются только узлы

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

  • новый узел

Когда i, e1 и e2 удовлетворяют следующему соотношению, можно считать, что существует новый узел

// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
    if (i <= e2) {
        const nextPos = e2 + 1;
        const anchor = nextPos < l2 ? c2[nextPos] : parentAnchor

        while (i <= e2) {
            patch(
                null,
                c2[i],
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG
            )
            i++
        }
    }
} else if {
    //
} else {
    //
}
  • Узел узел

Когда i, e1 и e2 удовлетворяют следующему соотношению, можно считать, что узел был удален.

// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
if (i > e1) {
  //
} else if (i > e2) {
    while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
    }
} else {
    //
}

Узлы перемещаются, добавляются или удаляются

Иногда ситуация может быть не такой простой, как описанная выше, то есть, когда i, e1, e2 не удовлетворяют двум вышеуказанным условиям, нам нужно найти узлы, которые необходимо удалить или добавить, или определить, какие узлы необходимо удалить. взолнованный.

Для этого нам нужно обойти узлы в c1, которые еще не были обработаны, а затем посмотреть, есть ли соответствующий узел (с тем же ключом) в c2. Если нет, это означает, что узел был удален, затем выполните операцию размонтирования.

Во-первых, чтобы быстро подтвердить, имеет ли узел c1 соответствующий узел и его местоположение в c2, установите отображение (ключ: индекс) на узел в c2.

// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [d e c h] f g
// i = 2, e1 = 4, e2 = 5
if (i > e1) {
  //
} else if (i > e2) {
  //
} else {
    const s1 = i
    const s2 = i

    const keyToNewIndexMap = new Map()

    // 5.1 build key:index map for newChildren
    for (i = s2; i <= e2; i++) {
        const nextChild = c2[i]
        if (nextChild.key !== null) {
            keyToNewIndexMap.set(nextChild.key, i)
        }
    }
}

Затем определите следующие переменные

let j 
let patched = 0
const toBePatched = e2 - s2 + 1  // c2 中待处理的节点数目
let moved = false

// used to track whether any node has moved
let maxNewIndexSoFar = 0  // 已遍历的待处理的 c1 节点在 c2 中对应的索引最大值

// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched) // 用于后面求最长递增子序列

for (i = 0; i < toBePatched; i++) {
    newIndexToOldIndexMap[i] = 0
}

Затем пройдитесь по узлам, которые должны быть обработаны в c1, и оцените, есть ли узел с тем же ключом в c2.

  • Нет, значит нода удалена, размонтируйте.
  • Да, вызовите функцию исправления. И запишите индекс узла в c1. При этом фиксируется максимальный индекс узла в c2, если позиция индекса узла в c2 меньше этого максимального индекса, значит, есть элемент, который нужно переместить.
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
for (i = s1; i <= e1; i++) {
    const prevChild = c1[i]

    // (A)

    let newIndex 
    if (prevChild.key !== null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
        for (j = s2; i <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j])
            ) {
              newIndex = j
              break
            }
        }
    }

    if (newIndex === void 0) {
        unmount(prevChild, parentComponent, parentSuspense, true)
    } else {
        newIndexToOldIndexMap[newIndex  - s2] = i + 1  // (B)

        if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex
        } else {
            moved = true
        }
        patch(
            prevChild,
            c2[i],
            container,
            null,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized
        )

        patched++  // (C)
    }
}

Все ли узлы в c1 должны найти соответствующие узлы в c2, а затем вызвать patch?

Обратите внимание на код выше(C), Мы обновим количество пропатченных узлов, а затем, когдаpatched > toBePatched, можно считать, что узлы в c1, которые нужно пройти дальше, избыточны, просто удалите их напрямую.

Итак, в приведенном выше(A)нужно добавить код

if (patched >= toBePatched) {
    // all new children have been patched so this can only be a removal
    unmount(prevChild, parentComponent, parentSuspense, true)
    continue
}

Вот трудная часть для понимания.

В начале мы сказали, что после предварительной обработки оставшиеся узлы будут использовать самую длинную возрастающую подпоследовательность для повышения эффективности сравнения.

Основная цель решения самой длинной возрастающей подпоследовательности - уменьшить перемещение элементов dom, что также можно понимать как наименьшую операцию dom.

Во-первых, нам нужно решить, чтобы получить самую длинную возрастающую подпоследовательность

// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR 

Давайте посмотрим, каково здесь значение newIndexToOldIndexMap.

В сочетании с конкретным примером предположим, что c1 и c2 такие, как показано на следующем рисунке.

image

определить и инициализироватьnewIndexToOldIndexMap

const newIndexToOldIndexMap = new Array(toBePatched)

for (i = 0; i < toBePatched; i++) {
    newIndexToOldIndexMap[i] = 0
}

toBePatchedТо есть после предварительной обработки количество узлов, подлежащих обработке в c2. В соответствии с примером здесь будет

toBePatched = 4
newIndexToOldIndexMap = [0, 0, 0, 0]

обратите внимание на выше5.2Код, обходящий узлы в c1(B)где есть

// 这里是 i + 1,不是 i 
// 因为 0 是一个特殊值,表示这个是新增的节点
newIndexToOldIndexMap[newIndex  - s2] = i + 1  // (B)

Итак, после обработки узлов в c1 будет

moved = true
newIndexToOldIndexMap = [4, 5, 3, 0]

Так,increasingNewIndexSequenceЗначениеgetSequence(newIndexToOldIndexMap)Возвращаемое значение

// [4, 5, 3, 0]  --> 最长递增子序列是 [4, 5] 
// 对应的索引是 [0, 1]
increasingNewIndexSequence = [0, 1]

После решения самой длинной возрастающей подпоследовательности остается пройтись по ожидающим узлам в c2, чтобы определить, является ли узел новым дополнением и нужно ли его переместить.

j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 注意:这里是从后往前遍历
for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex]
    const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1]).el : parentAnchor

    // newIndexToOldIndexMap 里的值默认初始化为 0 
    // 这里 === 0 表示 c2 中的节点在 c1 中没有对应的节点,属于新增
    if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG
        )
    } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        
        // j < 0  --> 最长递增子序列为 [] 
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor, MoveType.REORDER)
        } else {
            j--
        }
    }
}

самая длинная возрастающая подпоследовательность

В информатике,самая длинная возрастающая подпоследовательностьЗадача (самая длинная возрастающая подпоследовательность) состоит в том, чтобы найти такую ​​подпоследовательность в заданной последовательности значений, чтобы значения элементов этой подпоследовательности возрастали по очереди, а длина этой подпоследовательности была как можно больше. Элементы самой длинной возрастающей подпоследовательности не обязательно являются смежными в исходной последовательности. -- Википедия

对于以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最长递增子序列为

0, 2, 6, 9, 11, 15.

值得注意的是原始序列的最长递增子序列并不一定唯一,对于该原始序列,实际上还有以下两个最长递增子序列

0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15

наконец

До сих пор был проанализирован код различий Vue 3.0, добро пожаловать на совместное обсуждение.

Конкретный код:renderer.ts

Оригинальный адрес:Алгоритм и принцип сравнения Vue 3.0