跳到主要内容

霍春阳版

2023年08月30日
柏拉文
越努力，越幸运

一、实现​

1.1 patchKeyedChildren()​

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

    while (i <= e1 && i <= e2) {
      const n1 = c1[i];
      const n2 = c2[i];
      if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, container, null);
      } else {
        break;
      }
      i++;
    }

    while (i <= e1 && i <= e2) {
      const n1 = c1[e1];
      const n2 = c2[e2];
      if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, container, null);
      } else {
        break;
      }
      e1--;
      e2--;
    }

    if (i > e1) {
      if (i <= e2) {
        const nextPos = e2 + 1;
        const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
        while (i <= e2) {
          patch(null, c2[i], container, anchor);
          i++;
        }
      }
    } else if (i > e2) {
      while (i <= e1) {
        unmount(c1[i]);
        i++;
      }
    } else {
      const s1 = i;
      const s2 = i;

      const keyToNewIndexMap = new Map();
      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;
      let moved = false;
      let maxNewIndexSoFar = 0;
      const newIndexToOldIndexMap = new Array(toBePatched);
      for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

      for (i = s1; i <= e1; i++) {
        const prevChild = c1[i];
        if (patched >= toBePatched) {
          unmount(prevChild);
          continue;
        }
        let newIndex;
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key);
        } else {
          for (j = s2; j <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j])
            ) {
              newIndex = j;
              break;
            }
          }
        }
        if (newIndex === undefined) {
          unmount(prevChild);
        } else {
          newIndexToOldIndexMap[newIndex - s2] = i + 1;
          if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex;
          } else {
            moved = true;
          }
          patch(prevChild, c2[newIndex], container, null);
          patched++;
        }
      }

      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR;
      j = increasingNewIndexSequence.length - 1;
      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;
        if (newIndexToOldIndexMap[i] === 0) {
          patch(null, nextChild, container, anchor);
        } else if (moved) {
          if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild);
          } else {
            j--;
          }
        }
      }
    }
};

1.2 getSequence()​

function getSequence(nums) {
  let len = 1;
  const { length } = nums;
  const d = new Array(nums.length + 1);
  d[len] = 0;
  for (let i = 1; i < length; i++) {
    const num = nums[i];
    if (nums[d[len]] < num) {
      d[++len] = i;
    } else {
      let left = 1;
      let right = len;
      let pos = 0;
      while (left <= right) {
        let middle = (left + right) >> 1;
        if (nums[d[middle]] < num) {
          pos = middle;
          left = middle + 1;
        } else {
          right = middle - 1;
        }
      }
      d[pos + 1] = i;
    }
  }
  return d.filter(i => i != null);
}

二、测试​

2.1 从左往右​

从左往右 针对 (a b) c ---> (a b) d e , 测试如下:

const renderOps = {
  setText(el, text) {
    el.nodeValue = text;
  },
  createText(text) {
    return document.createTextNode(text);
  },
  createComment(comment) {
    return document.createComment(comment);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  }
};

const renderer = createRenderer({ ...renderOps, patchProp });

const oldData = ['a', 'b', 'c'];
const vnode = {
  type: 'div',
  shapeFlag: 9,
  children: oldData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
};
renderer.render(vnode, document.querySelector('#app'));

setTimeout(() => {
  const newData = ['a', 'b', 'd', 'e'];
  const vnode = {
    type: 'div',
    shapeFlag: 9,
    children: newData.map(item => ({
      type: 'div',
      shapeFlag: 9,
      children: item
    }))
  };
  renderer.render(vnode, document.querySelector('#app'));
}, 3000);

2.2 从右往左​

从左往右 针对 a (b c) ---> d e (b c) , 测试如下:

const renderOps = {
  setText(el, text) {
    el.nodeValue = text;
  },
  createText(text) {
    return document.createTextNode(text);
  },
  createComment(comment) {
    return document.createComment(comment);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  }
};

const renderer = createRenderer({ ...renderOps, patchProp });

const oldData = ['a','b','c'];
const vnode = {
  type: 'div',
  shapeFlag: 9,
  children: oldData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
};

renderer.render(vnode, document.querySelector('#app'));

setTimeout(() => {
  const newData = ['d','e','b','c'];
  const vnode = {
    type: 'div',
    shapeFlag: 9,
    children: newData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
  };
  
  renderer.render(vnode, document.querySelector('#app'));
}, 3000);

2.3 新节点多于旧节点​

从左往右 针对 (a b) ---> (a b) c 或者 (a b) ---> c (a b), 测试如下:

const renderOps = {
  setText(el, text) {
    el.nodeValue = text;
  },
  createText(text) {
    return document.createTextNode(text);
  },
  createComment(comment) {
    return document.createComment(comment);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  }
};

const renderer = createRenderer({ ...renderOps, patchProp });

const oldData = ['a', 'b', 'c'];
const vnode = {
  type: 'div',
  shapeFlag: 9,
  children: oldData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
};
renderer.render(vnode, document.querySelector('#app'));

setTimeout(() => {
  const newData = ['a', 'b', 'd', 'e'];
  const vnode = {
    type: 'div',
    shapeFlag: 9,
    children: newData.map(item => ({
      type: 'div',
      shapeFlag: 9,
      children: item
    }))
  };
  renderer.render(vnode, document.querySelector('#app'));
}, 3000);

2.4 旧节点多于新节点​

从左往右 针对 (a b) c ---> (a b) 或者 a (b c) ---> (b c) , 测试如下:

const renderOps = {
  setText(el, text) {
    el.nodeValue = text;
  },
  createText(text) {
    return document.createTextNode(text);
  },
  createComment(comment) {
    return document.createComment(comment);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  }
};

const renderer = createRenderer({ ...renderOps, patchProp });

const oldData = ['a','b','c'];
const vnode = {
  type: 'div',
  shapeFlag: 9,
  children: oldData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
};

renderer.render(vnode, document.querySelector('#app'));

setTimeout(() => {
  const newData = ['a','b'];
  const vnode = {
    type: 'div',
    shapeFlag: 9,
    children: newData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
  };

  renderer.render(vnode, document.querySelector('#app'));
}, 3000);

2.5 新旧节点乱序排序​

从左往右 针对 a b [c d e] f g ---> a b [e d c h] f g , 测试如下:

const renderOps = {
  setText(el, text) {
    el.nodeValue = text;
  },
  createText(text) {
    return document.createTextNode(text);
  },
  createComment(comment) {
    return document.createComment(comment);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  }
};

const renderer = createRenderer({ ...renderOps, patchProp });

const oldData = ['a','b','c','d','e','f','g'];
const vnode = {
  type: 'div',
  shapeFlag: 9,
  children: oldData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
};

renderer.render(vnode, document.querySelector('#app'));

setTimeout(() => {
  const newData = ['a','b','e','d','c','h','f','g'];
  const vnode = {
    type: 'div',
    shapeFlag: 9,
    children: newData.map(item => ({ type: 'div', shapeFlag: 9, children: item }))
  };

  renderer.render(vnode, document.querySelector('#app'));
}, 3000);