Diffing Strategies — Complete Guide

// The tree edit distance problem:
// Finding the minimum number of operations to transform
// one tree into another is O(n^3) in the worst case.
// n = number of nodes, so 1000 nodes = 1 billion operations.

// Frameworks avoid this by making assumptions:
// Assumption 1: Elements of different types produce different trees
// Assumption 2: Keys identify stable elements across renders
// Assumption 3: Elements at the same level can be compared by position

// These assumptions reduce complexity to O(n)
// (linear in the number of elements) for typical cases.

// React's strategy:
// 1. Compare root element types. Different type => full rebuild.
// 2. Same type => update props, recurse into children.
// 3. Children with keys => match by key.
// 4. Children without keys => match by index.
// 5. Component type determines whether to recurse into children.

// Vue's strategy:
// 1. Same element type => patch in place.
// 2. Different element type => mount new, unmount old.
// 3. v-for with :key => keyed children diff.
// 4. v-for without :key => positional children diff.
// 5. Component-level updates via reactive dependencies.

// Preact's strategy:
// 1. Similar to React but with a simpler algorithm.
// 2. Uses a single-pass diff with key matching.
// 3. Component diffing uses shouldComponentUpdate checks.

// Strategy 1: Positional diff (simple, O(n))
function positionalDiff(oldChildren, newChildren) {
    const patches = [];
    const maxLen = Math.max(oldChildren.length, newChildren.length);

    for (let i = 0; i < maxLen; i++) {
        if (i >= oldChildren.length) {
            patches.push({ type: 'INSERT', index: i, vnode: newChildren[i] });
        } else if (i >= newChildren.length) {
            patches.push({ type: 'REMOVE', index: i });
        } else {
            const childPatch = diff(oldChildren[i], newChildren[i]);
            if (childPatch) patches.push({ type: 'UPDATE', index: i, patch: childPatch });
        }
    }
    return patches;
}
// O(n), but can't detect moves or reordering

// Strategy 2: Keyed diff (better for dynamic lists)
function keyedDiff(oldChildren, newChildren) {
    const oldKeys = new Map();
    oldChildren.forEach((child, i) => {
        if (child.key != null) oldKeys.set(child.key, i);
    });

    const patches = [];
    const processed = new Set();

    newChildren.forEach((newChild, newIndex) => {
        if (newChild.key != null && oldKeys.has(newChild.key)) {
            const oldIndex = oldKeys.get(newChild.key);
            if (oldIndex !== newIndex) {
                patches.push({ type: 'MOVE', from: oldIndex, to: newIndex });
            }
            // Update existing
            const oldChild = oldChildren[oldIndex];
            const childPatch = diff(oldChild, newChild);
            if (childPatch) patches.push({ type: 'UPDATE', index: newIndex, patch: childPatch });
            processed.add(oldIndex);
        } else {
            patches.push({ type: 'INSERT', index: newIndex, vnode: newChild });
        }
    });

    // Remove old items not in new
    oldChildren.forEach((child, i) => {
        if (!processed.has(i)) {
            patches.push({ type: 'REMOVE', index: i });
        }
    });

    return patches;
}
// Detects moves, avoids unnecessary re-creation

// Strategy 3: Optimized with component shouldUpdate
function shouldUpdate(oldVNode, newVNode) {
    if (oldVNode.type !== newVNode.type) return true;
    if (oldVNode.key !== newVNode.key) return true;

    // Component-specific optimization
    if (typeof oldVNode.type === 'function') {
        // Check if props changed (shallow comparison)
        return !shallowEqual(oldVNode.props, newVNode.props);
    }

    // DOM elements always update (attributes may change)
    return true;
}

function shallowEqual(objA, objB) {
    if (objA === objB) return true;
    const keysA = Object.keys(objA);
    const keysB = Object.keys(objB);
    if (keysA.length !== keysB.length) return false;
    return keysA.every(key => objA[key] === objB[key]);
}

// Deep tree (more diffing work):
// <App>
//   <Header>
//     <Nav>
//       <Menu>
//         <MenuItem>Home</MenuItem>
//       </Menu>
//     </Nav>
//   </Header>
//   <Main>
//     <Content>
//       <Article>
//         <p>Text</p>
//       </Article>
//     </Content>
//   </Main>
// </App>
// Diffing recurses 6 levels deep for a simple change in <p>

// Shallow tree (less diffing work):
// <App>
//   <Header />
//   <Main>
//     <Article title="Home" body="Text" />
//   </Main>
// </App>
// Only 3 levels of recursion for the same content
// Article component handles its own rendering internally

// React: React.memo for function components
const ExpensiveList = React.memo(function ExpensiveList({ items }) {
    return items.map(item => <li key={item.id}>{item.name}</li>);
});

// ExpensiveList only re-renders when its props change
// (shallow comparison). If the parent re-renders but
// items reference hasn't changed, this subtree is skipped.

// React: shouldComponentUpdate for class components
class OptimizedComponent extends React.Component {
    shouldComponentUpdate(nextProps) {
        // Only re-render when specific props change
        return this.props.data.id !== nextProps.data.id ||
               this.props.data.value !== nextProps.data.value;
    }

    render() {
        return <div>{this.props.data.value}</div>;
    }
}

// Vue: v-memo directive
// <div v-memo="[item.id, item.updatedAt]">
//   {{ item.content }}
// </div>
// Only updates when item.id or item.updatedAt changes