Minimalistic tree diffing algorithm

diff.js

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;
}

dom_impl.js

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);
}

vdom_impl.js

// 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;
}