1. The timing of virtual DOM comparison
-
1. In the rendering process, processElement is executed to processElement nodes, and internal calls to updateElement are made to compare the before and after dom nodes (in this case, both virtual dom nodes exist before and after the change). Inside the updateElement function is the whole process of virtual DOM comparison
-
2. Process the DOM root node first and run the processElement function to process the DOM root node comparison in two cases
- IsSameVnode judged that the results of n1 virtual DOM node before and n2 virtual DOM node after the change were not equal, so it was necessary to reconstruct the element node according to n2 virtual DOM node after the change, which was consistent with the element mount process in the initial rendering process
N1 and n2 are equal. N2 overuses the DOM node of N1, updates the props attribute of the root node through patchProps, and then invokes patchChildren to compare child elementsCopy the code
- 3. Code implementation
// Process element nodes
const processElement = (n1, n2, container, ancher) = > {
// Mount or update the element node according to whether n1 is null
if (n1 == null) {
mountElement(n2, container, ancher);
} else {
// The virtual DOM is not null before and after the changeupdateElement(n1, n2, container); }}// Update the node, starting from the root node
const updateElement = (n1, n2, container) = > {
N1 and n2 are the same node
// Delete the node with hostRemove and reset n1 to null,
const el = n2.el = n1.el;
if(n1 && ! isSameVnode(n1, n2)) {// hostRemove removes the current node by calling removeChild
hostRemove(el);
n1 = null;
}
// Because after n1 is reset to NULL, the first parameter of patch is passed null, which follows the same process as the first dom rendering
if (n1 == null) {
patch(null, n2, container)
} else {
// Update the attributes first
patchProps(n1, n2, el);
// Then compare the child elementspatchChildren(n1, n2, el); }}// Compare element attributes
const patchProps = (n1, n2, el) = > {
// Attributes of the new object
const prevProps = n1.props || {};
// Attributes of the old object
const nextProps = n2.props || {};
// prevProps and nextProps are not equal
if(prevProps ! == nextProps) {// If it exists in the new property, the property needs to be set
for (let key in nextProps) {
if(prevProps[key] ! == nextProps[key]) {// Update a new attributehostPatchProps(el, key, prevProps[key], nextProps[key]); }}// The old attribute does not exist in the new attribute
for (let key in prevProps) {
if(! (keyin nextProps)) {
// Delete the old attributes
hostPatchProps(el, key, prevProps[key], null); }}}}export function hostPatchProps (el, key, oldVal = null, newVal = null) {
switch (key) {
case "class":
// The attribute is class
patchClass(el, newVal)
break;
case "style":
// The attribute is style
patchStyle(el, oldVal, newVal);
break;
default:
// Ordinary DOM attributes
patchAttr(el, key, newVal);
break; }}function patchClass (el, val) {
if (val == null) {
// When null, there is no class
val = "";
}
// Set the latest class value
el.className = val;
}
function patchStyle (el, oldVal, newVal) {
// Set the attributes for the element with the latest style
for (let key in newVal) {
el.style[key] = newVal[key];
}
// Attributes do not exist in the new style, they exist in the old style, the latest is dominant,You need to remove the old style attribute that originally existed on the reused elementfor (let key in oldVal) {
if(! (keyin newVal)) {
el.style[key] = ""; }}}function patchAttr (el, key, val) {
if(! val) {// if val has no value, the attribute is deleted
el.removeAttribute(key);
} else {
// If val exists, set the current attribute, regardless of whether the original attribute existsel.setAttribute(key, val); }}Copy the code2. Execute patchChildren to compare child element DOM
- Firstly, the child elements C1 and C2 of virtual DOM nodes N1 and n2 before and after the change are obtained, and the shapFlag of N1 and n2 is obtained as prveShapFlag and nextShapFlag to determine the type of child nodes
2. There are two types of virtual DOM child nodes: text type and array type
1. If the new virtual DOM child node is a text type, then the child node is a text node. Regardless of whether the child node of the old virtual DOM node is a text type or an array type, the DOM element directly sets the child node as a text node with textContentCopy the code
2. If the child nodes of the new virtual DOM are arrays, two cases need to be distinguished: 1. The child node type of the old virtual DOM is also an array type, so patchKeyChildren needs to be called to compare the differences of the child nodes in detail, just like the DOM comparison process in VUe2 2. The old virtual DOM node type is text. You only need to delete the original text node of the element, then loop through the new virtual DOM child node, and mount the child node to the DOM through pathCopy the code
3. Code implementation
// Compare child elements
const patchChildren = (n1, n2, container) = > {
const c1 = n1.children;
const c2 = n2.children;
const prveShapFlag = n1.shapFlag;
const nextShapFlag = n2.shapFlag;
// The types of child elements are arrays and strings, so there are four cases
// 1. C2 is a string and c1 is a string
// 2. C2 is a string and c1 is an array
// 3. C2 is an array and c1 is a string
// 4. C2 is array, c1 is array
if (nextShapFlag & shapFlags.TEXT_CHILD) {
// If c2 is a string, regardless of whether C1 is a string or an array, just set the new value with textContent
// If c1 and c2 are both strings, they are equal
if (c1 !== c2) {
hostSetElementText(container, c2);
}
} else if (nextShapFlag & shapFlags.ARRAY_CHILD) {
if (prveShapFlag & shapFlags.ARRAY_CHILD) {
// c2 is an array. C1 is an array
patchKeyChildren(c1, c2, container)
}
if (prveShapFlag & shapFlags.TEXT_CHILD) {
// c1 is a string, delete the string first, then loop over the new element
hostSetElementText(container, "");
for (let i = 0; i < c2.length; i++) {
// Mount each new child element
patch(null, c2[i], container); }}}}Copy the code3. PatchKeyChildren conducts multiple complex cases in which the child elements of both the old and new virtual DOM are used
- First, the length of the new virtual DOM child node is L2 and the number of the old and new virtual DOM child nodes e1 and e2
const patchKeyChildren = (c1, c2, container) = > {
// Count the number of elements that have been compared since position 0
let i = 0;
// nextIndex is null when nextIndex is greater than l2
const l2 = c2.length;
// The number of old children
let e1 = c1.length - 1;
// New number of child nodes
let e2 = l2 - 1;
}
Copy the code- First start from the position of the child nodes c1 and c2 0 cycle comparison, circulation conditions for I less than the number of child nodes of c1 and c2, if from the head start, child nodes are same i++ record number and get the same node under a child node of c1 and c2, compare again, until the contrast began to emerge from the head end child nodes are not equal
const patchKeyChildren = (c1, c2, container) = > {
/ /... Precode omission
/* 1. Prev [a, b, c] next [a, b, c, d] = 1; e1=2; e2 = 3 */
while (i <= e1 && i <= e2) {
// On the same node, move the I pointer backward, when the nodes are not out of the loop at the same time
const n1 = c1[i];
const n2 = c2[i];
if (isSameVnode(n1, n2)) {
// The nodes are the same but the attributes are not necessarily the same, so it needs to be updated and recursed
patch(n1, n2, container);
} else {
break; } i++; }}Copy the code- After the head is not the same, start from the tail comparison, tail comparison if the same E1 –, E2 –. The tail comparison ends when the front and back virtual DOM are different or I is greater than E1 or E2
const patchKeyChildren = (c1, c2, container) = > {
/ /... Precode omission
while (i <= e1 && i <= e2) {
// On the same node, move the e1 and e2 Pointers forward, when the nodes are not out of the loop at the same time
const n1 = c1[e1];
const n2 = c2[e2];
if (isSameVnode(n1, n2)) {
// The nodes are the same but the attributes are not necessarily the same, so it needs to be updated and recursed
patch(n1, n2, container);
} else {
break;
}
e1--;
e2--
}
}
Copy the code- After the comparison of steps 2 and 3 is completed, the following situation may occur
- If I > E1, e1’s virtual DOM nodes are all traversed. If I > E1 and I >e2 are traversed, E2’s virtual DOM nodes are also traversed. E1 and E2 have been traversed in steps 2 and 3
2. If I > E1, I <=e2 indicates that e1 traversal is completed and e2 still has elements, indicating that new elements are added to the virtual DOM after the change. The new elements need to be inserted into the new DOM at the current positionCopy the code
3. I >e2 indicates that the traversal of the new virtual DOM node is complete, and I <=e1 indicates that the traversal of the old virtual DOM node is not complete and there are remaining elements, which are unnecessary nodes and need to be deletedCopy the code
4. I < E1&& I <e2 indicates that both the old and new virtual DOM have not been traversed and there are remaining elements, so it is necessary to compare and contrast each item of the remaining elements, which is the most complex DOM comparisonCopy the code
Code implementationCopy the code const patchKeyChildren = (c1, c2, container) = > {
/ /... Precode omission
if (i > e1) {
// The old virtual DOM traversal is complete, and the new virtual DOM has some remaining elements.Loop the number of remaining elements and mount the new element directlywhile (i <= e2) {
// Get the next element dom, insertBefore,
// change ancher to null insertBefore when the element length exceeds e2
let nextPos = e2 + 1;
const ancher = nextPos < l2 ? c2[nextPos].el : null;
patch(null, c2[i], container, ancher); i++; }}else if (i > e2) {
// The new virtual DOM traversal is complete. The old virtual DOM has remaining elements. The remaining elements are not needed
while (i <= e1) {
// hostRemove calls removeChild to remove a nodehostRemove(c1[i].el); i++; }}else {
// Here is the most complex DOM comparison for case 4}}Copy the code4. The old and new virtual DOM elements have not been completely traversed, and there is a comparison of the remaining elements
1. The key and index mapping table 2 of the new virtual DOM should be established first. Loop through the old virtual DOM nodes, updating and deleting nodes, and find the node 3 that needs to be moved. Finally, a new DOM node is added and the minimum increment subsequence is used to handle the need to move the element to the correct positionCopy the codeThis compares the case to the overall code
const patchKeyChildren = (c1, c2, container) = > {
/ /... Precode omission
if (i > e1) {
} else if (i > e2) {
} else {
// Here is the most complex DOM comparison for case 4
// The middle element is unknown
let s1 = i;
let s2 = i;
// create a mapping table for the new node key and index to find elements
const keytoNewIndexMap = new Map(a);for (i = s2; i <= e2; i++) {
const key = c2[i].key;
keytoNewIndexMap.set(key, i);
}
let j;
// The number of dom comparisons
let patched = 0;
// The number of elements to be compared
let toBePatched = e2 - s2 + 1;
let moved = false; // Check whether there is a move operation
let maxNewIndexSoFar = 0; //
const newIndexToOldIndex = new Array(toBePatched).fill(0);
// Loop through the old virtual DOM to find the index of the new node corresponding to the key of the current old node
// If the old node does not have a key value, use newIndexToOldIndex to set ing's oldIndex
If the value is 0, it indicates that the tag is not found. If the value is 0, it indicates that the tag is not found
// determine the same item
let newIndex;
// Process the old virtual DOM, update and delete elements, and find elements that need to be moved
for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
// need to handle redundant nodes left over from old elements, patched greater than or equal to toBePatched,There are unnecessary child nodes on the old node// Uninstall it if you don't need it
if (patched >= toBePatched) {
hostRemove(prevChild.el);
}
if(prevChild.key ! =null) {
// The old node has a key value. Go directly to the mapping table to find the new sequence position of the element
newIndex = keytoNewIndexMap.get(prevChild.key);
} else {
// If the old node has no key value, check whether the corresponding value of newIndexToOldIndex is 0
// The object element is not found, then check whether the tag is equal
for (j = s2; j < toBePatched; j++) {
if (newIndexToOldIndex[j] == 0 &&
isSameVnode(prevChild, c2[j + s2])) {
newIndex = j;
break; }}}if (newIndex == undefined) {
// If the index of the new element is not found, the element does not exist
hostRemove(prevChild.el)
} else {
// 0 is a special identifier, so I +1 is required
newIndexToOldIndex[newIndex - s2] = i + 1;
// Save the current sequence
if (maxNewIndexSoFar >= newIndex) {
// If maxNewIndexSoFar is greater than newIndex, an element has been shifted
// Because maxNewIndexSoFar is always the newIndex that stores the old node found in the new node,
// The old node is always incrementing. If the position is not moved, the new node should also be incrementing
moved = true;
} else {
maxNewIndexSoFar = newIndex;
}
// newIndex has a value indicating that the current element needs to be updated
patch(prevChild, c2[newIndex], container);
// Record the elements compared
patched++
}
}
// Use the longest increasing subsequence to determine the least element displacement
const increasingNewIndexSequence =
moved ? getSequence(newIndexToOldIndex) : [];
j = increasingNewIndexSequence.length;
// Flashback through the elements to compare
// After the last comparison element is retrieved, that element sequence is used as a reference for DOM manipulation
for (i = toBePatched - 1; i >= 0; i--) {
// 0 is the new element, just find the reference to insert
const nextIndex = s2 + i;
const nextChild = c2[nextIndex];
const ancher = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;
if (newIndexToOldIndex[i] == 0) {
patch(null, c2[s2 + i], container, ancher)
} else if (moved) {
// If it is not new, do not move it
if (j < 0|| i ! == increasingNewIndexSequence[j]) {//j is the array length of the longest increment subsequence. When j<0, I must be movedNeed to move hostInsert(nextchild.el, container, ancher)} if I is not in the longest increasing subsequenceelse {
In other cases, no need to move the node, just point j-- j-- to the item before the longest increasing subsequence
j--;
}
}
}
}
}
Copy the codeStep by step code and step disassembly
- First, record the starting position I of the new and old virtual DOM, s1 and S2 respectively. Then create a map mapping table to record the relationship between key and index of each new virtual DOM node
2. Record the elements to be compared with patched, toBePatched, Moved, maxNewIndexSoFar record the maximum index that has been compared. MaxNewIndexSoFar is used to determine whether the element has been moved, and newIndexToOldIndex is used to record the index pair relationship between new and old virtual DOM nodes
let s1 = i;
let s2 = i;
// create a mapping table for the new node key and index to find elements
const keytoNewIndexMap = new Map(a);for (i = s2; i <= e2; i++) {
const key = c2[i].key;
keytoNewIndexMap.set(key, i);
}
let j;
// The number of dom comparisons
let patched = 0;
// The number of elements to be compared
let toBePatched = e2 - s2 + 1;
let moved = false; // Check whether there is a move operation
let maxNewIndexSoFar = 0; //
const newIndexToOldIndex = new Array(toBePatched).fill(0);
Copy the code3. Loop through the remaining elements of the old virtual DOM to find the elements that need to be deleted and updated
1. Loop the DOM and handle boundaries. If the number of patched patched patched is greater than or equal to the number to be compared toBePatched, delete the remaining elements of the old virtual DOMCopy the code for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
// need to handle redundant nodes left over from old elements, patched greater than or equal to toBePatched,
// It indicates that there are unnecessary child nodes. Uninstall them if they are not needed
if (patched >= toBePatched) {
// Delete the element directly
hostRemove(prevChild.el);
}
/ /...
}
Copy the code2. Find out the position index of the old DOM node corresponding to the new virtual DOM node (the old node is found in the new virtual DOM, indicating that it is the same element, which can be reused, but the index of the new virtual DOM should be used as the final position of the element), which can be divided into the situation with key value and without key value: If there is a key, you can use the created keytoNewIndexMap to obtain the index of the new node corresponding to the old node (the index is the final location of the node). There is no key value. If the value of j in newIndexToOldIndex is 0 and isSameVnode is used to determine whether the tag name is equal, the element c2[j + s2] and prevChild are the same element. PrevChild's index, reuse the current nodeCopy the code if(prevChild.key ! =null) {
// The old node has a key value. Go directly to the mapping table to find the new sequence position of the element
newIndex = keytoNewIndexMap.get(prevChild.key);
} else {
// If the old node has no key value, check whether the corresponding value of newIndexToOldIndex is 0
// The object element is not found, then check whether the tag is equal
for (j = s2; j < toBePatched; j++) {
if (newIndexToOldIndex[j] == 0 && isSameVnode(prevChild, c2[j + s2])) {
newIndex = j;
break; }}}Copy the code- If newIndex does not exist, the old virtual DOM does not exist in the new virtual DOM. Delete the prevChild element of the old node directly. If newIndex exists, it means that the old virtual DOM node can be reused, and the attribute of the element can be directly updated through patch method. The element position movement is not dealt with here, and the next step is the process of the longest increasing subsequence
if (newIndex == undefined) {
// If the index of the new element is not found, the element does not exist
hostRemove(prevChild.el)
} else {
// newIndexToOldIndex Records the location of the new node and the old node, is
0 is a special identifier, so I +1 is required
newIndexToOldIndex[newIndex - s2] = i + 1;
// Save the current sequence
if (maxNewIndexSoFar >= newIndex) {
// If maxNewIndexSoFar is greater than newIndex, an element has been shifted
// Because maxNewIndexSoFar is always the newIndex that stores the old node found in the new node,
// The old node is always incrementing. If the position is not moved, the new node should also be incrementing
moved = true;
} else {
// Record the last index
maxNewIndexSoFar = newIndex;
}
// newIndex has a value indicating that the current element needs to be updated
patch(prevChild, c2[newIndex], container);
// Record the number of elements compared
patched++
}
Copy the code-
The process of adding and moving elements is a flashback comparison process, as the next DOM node of the comparison element needs to be retrieved as a reference to insert into the document
- First, determine whether the element needs to be moved based on moved. If it needs to be moved, execute getSequence to get the longest increasing subsequence. Then, backtrack through the nodes that need to be compared in the new virtual DOM
- Obtain the sequence nextIndex of the last node of the uncompared node, and obtain the last virtual node nextChild, and obtain the symbol of the inserted node. Refer to ancher (the next element node is c2[nextIndex + 1].el, which exceeds the length of C2. Ancher = null)
- If newIndexToOldIndex[I] == 0, it indicates that the current new virtual DOM node is a new element, which can be directly mounted by creating an element with patch
- If newIndexToOldIndex [I]! == 0 and moved=true means the current node is a reusable element and needs to be moved
// Use the longest increasing subsequence to determine the least element displacement
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndex) : [];
j = increasingNewIndexSequence.length;
// Flashback through the elements to compare
// After the last comparison element is retrieved, that element sequence is used as a reference for DOM manipulation
for (i = toBePatched - 1; i >= 0; i--) {
// 0 is the new element, just find the reference to insert
const nextIndex = s2 + i;
const nextChild = c2[nextIndex];
const ancher = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;
if (newIndexToOldIndex[i] == 0) {
patch(null, c2[s2 + i], container, ancher)
} else if (moved) {
// If it is not new, do not move it
/ / I and increasingNewIndexSequence [j] position need to move without equal
if (j < 0|| i ! == increasingNewIndexSequence[j]) {//j is the array length of the longest incrementing subsequence. When j<0, I must move the desired element.I need to move hostInsert(nextchild.el, container, ancher)} if I is not in the longest increasing subsequenceelse {
In other cases, no need to move the node, just point j-- j-- to the item before the longest increasing subsequencej--; }}}Copy the codeGit address
The code links to the miniVue3 folder for a simple implementation of vue3 code