Last active
August 23, 2017 01:35
-
-
Save blasten/999dc53c62ef0243d90d0bd5e6afe996 to your computer and use it in GitHub Desktop.
Minimalistic tree diffing algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
export const OptCode = { | |
ADD_NODE: 1, | |
SET_PROPERTY: 2, | |
SET_TEXT: 3, | |
REMOVE_PROPERTY: 4, | |
REMOVE_NODE: 5 | |
}; | |
// a = new | |
// b = old | |
// Worst case run time & memory: O(n). | |
export function diff(nodeA, nodeB, exec) { | |
// Fast path. | |
if (isTheExactSubtree(nodeA, nodeB)) { | |
return; | |
} | |
if ( | |
isTextNode(nodeA) && | |
isTextNode(nodeB) && | |
getTextContent(nodeA) != getTextContent(nodeB) | |
) { | |
exec(OptCode.SET_TEXT, [nodeB, nodeA]); | |
return; | |
} | |
if (isSameNodeType(nodeA, nodeB)) { | |
const aProps = getProps(nodeA), | |
bProps = getProps(nodeB), | |
assignedPropSet = new Set(); | |
// Process properties. | |
for (let aPropName of aProps) { | |
const aPropValue = getPropValue(nodeA, aPropName); | |
if (aPropValue !== getPropValue(nodeB, aPropName)) { | |
exec(OptCode.SET_PROPERTY, [nodeB, aPropName, aPropValue]); | |
} | |
assignedPropSet.add(aPropName); | |
} | |
for (let bPropName of bProps) { | |
if (!assignedPropSet.has(bPropName)) { | |
const bPropValue = getPropValue(nodeB, aPropName); | |
exec(OptCode.REMOVE_PROPERTY, [nodeB, bPropName]); | |
} | |
} | |
// Process children. | |
const aChildren = getChildrenList(nodeA), | |
bChildren = getChildrenList(nodeB), | |
bChildrenKeyMap = new Map(); | |
for (let i = 0; i < bChildren.length; i++) { | |
if (hasKey(bChildren[i])) { | |
bChildrenKeyMap.set(getNodeKey(bChildren[i]), bChildren[i]); | |
} else { | |
diff(getChild(aChildren, i), getChild(bChildren, i), opCodes); | |
} | |
} | |
for (let i = 0; i < aChildren.length; i++) { | |
// Try to diff nodes that share the same key. | |
if ( | |
hasKey(aChildren[i]) && | |
bChildrenKeyMap.has(getNodeKey(aChildren[i])) | |
) { | |
const aNodeKey = getNodeKey(aChildren[i]); | |
diff( | |
getChild(aChildren, i), | |
bChildrenKeyMap.get(aNodeKey), | |
opCodes | |
); | |
bChildrenKeyMap.remove(aNodeKey); | |
} else { | |
diff(getChild(aChildren, i), getChild(bChildren, i), opCodes); | |
} | |
} | |
// Remove remaining nodes from nodeB. | |
for (let [bNodeKey, bNodeValue] of bChildrenKeyMap) { | |
diff(null, bNodeValue, opCodes); | |
} | |
return; | |
} | |
if (nodeA == null) { | |
exec(OptCode.REMOVE_NODE, [nodeB]); | |
return; | |
} | |
if (nodeB == null) { | |
exec(OptCode.ADD_NODE, [nodeA]); | |
return; | |
} | |
// Replace nodeB by nodeA. | |
exec(OptCode.REMOVE_NODE, [nodeB]); | |
exec(OptCode.ADD_NODE, [nodeA]); | |
} | |
export function getDiffOptCodes(nodeA, nodeB) { | |
let opCodes = []; | |
diff(nodeA, b, pushOpCode.bind(null, opCodes)); | |
return opCodes; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function isTextNode(node) { | |
return node.nodeType === Node.TEXT_NODE; | |
} | |
function getTextContent(node) { | |
return node.textContent; | |
} | |
function isSameNodeType(nodeA, nodeB) { | |
if (nodeA.nodeType !== nodeB.nodeType || nodeA.nodeType !== Node.ELEMENT_NODE) { | |
return false; | |
} | |
return nodeA.localName === nodeB.localName; | |
} | |
function getPropValue(node, propName) { | |
return node.getAttribute(propName); | |
} | |
function pushOpCode(ops, optCode, args) { | |
ops.push({ optCode, args }); | |
} | |
function getChildrenList(node) { | |
return node.children; | |
} | |
function hasKey(node) { | |
return node.dataset.key !== ""; | |
} | |
function getNodeKey(node) { | |
return node.dataset.key; | |
} | |
function getChild(node, idx) { | |
return node.children[idx]; | |
} | |
function isTheExactSubtree(nodeA, nodeB) { | |
// Strict equality check. | |
return nodeA === nodeB && (nodeA === nodeA || nodeB === nodeB); | |
} | |
function getProps(node) { | |
return Array.from(node.attributes).map(attr => attr.name); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// VDOM Interface | |
// VNode = { | |
// type: String | Function, | |
// textContent: String?, | |
// props: Map<String, Any>, | |
// key: Symbol | |
// } | |
TEXT_NODE = () => {}; | |
function isTextNode(node) { | |
return node.type === TEXT_NODE; | |
} | |
function getTextContent(node) { | |
return node.textContent; | |
} | |
function isSameNodeType(nodeA, nodeB) { | |
return nodeA.type === nodeB.type; | |
} | |
function getPropValue(node, propName) { | |
return node.props[propName]; | |
} | |
function pushOpCode(ops, optCode, args) { | |
ops.push({ optCode, args }); | |
} | |
function getChildrenList(node) { | |
return node.props.children; | |
} | |
function hasKey(node) { | |
return node.key !== ""; | |
} | |
function getNodeKey(node) { | |
return node.key; | |
} | |
function getChild(node, idx) { | |
return node.props.children[idx]; | |
} | |
function isTheExactSubtree(nodeA, nodeB) { | |
// Strict equality check. | |
return nodeA === nodeB && (nodeA === nodeA || nodeB === nodeB); | |
} | |
function getProps(node) { | |
return node.props; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment