diff-trees

diff-trees

For diffing ordered trees

A single diffTrees function is exported:

declare function diffTrees<TValue>(
  treeA: TreeNode<{ value: TValue }>,
  treeB: TreeNode<{ value: TValue }>
): DiffTree<TValue>;

It takes two trees of type TreeNode:

type TreeNode<TValues> = {
  id: string;
  children: TreeNode<TValues>[];
} & TValues;

And produces a single tree of type DiffTree which is an array containing one or two DiffTreeNodes. The second DiffTreeNode is included if the root of the tree was deleted.

type DiffTree<TValue> =
  | [DiffTreeNode<TValue>]
  | [DiffTreeNode<TValue>, DiffTreeNode<TValue>];

type DiffTreeNode<TValue> = Omit<TreeNode<{ value: TValue }>, 'children'> & {
  change: Change;
  children: DiffTreeNode<TValue>[];
};

Where a Change is:

type Change =
  | [ChangeType.Unchanged]
  | [ChangeType.Inserted]
  | [ChangeType.Deleted]
  | [ChangeType.Updated]
  | [ChangeType.Moved]
  | [ChangeType.Moved, ChangeType.Updated];

• ChangeType.Unchanged denotes unchanged nodes.
• ChangeType.Inserted denotes new nodes.
• ChangeType.Deleted denotes deleted nodes.
• ChangeType.Updated denotes nodes where the value changed.
• ChangeType.Moved denotes nodes that moved to another subtree or changed place within the same subtree.

The value in a TreeNode can is generic. If the value has changed, the DiffTreeNode is annotated with ChangeType.Updated. By default, values are compared using strict equality (===). To change how values are compared, add a custom valueEquality function to the optional options object:

declare function diffTrees<TValue>(
  treeA: TreeNode<{ value: TValue }>,
  treeB: TreeNode<{ value: TValue }>,
  options?: {
    valueEquality: (a: TValue, b: TValue) => boolean;
  }
): DiffTreeNode<TValue>;

Examples

diffTrees(
  { id: '1', value: 'a', children: [] },
  { id: '1', value: 'a', children: [] }
);

// =>

[
  {
    id: '1',
    value: 'a',
    children: [],
    change: [ChangeType.Unchanged],
  },
];

diffTrees(
  { id: '1', value: 'a', children: [] },
  { id: '2', value: 'b', children: [] }
);

// =>

[
  {
    id: '2',
    value: 'b',
    children: [],
    change: [ChangeType.Inserted],
  },
  {
    id: '1',
    value: '1',
    children: [],
    change: [ChangeType.Deleted],
  },
];

diffTrees(
  { id: '1', value: 'a', children: [] },
  { id: '1', value: 'a', children: [{ id: '2', value: 'b', children: [] }] }
);

// =>

[
  {
    id: '1',
    value: 'a',
    change: [ChangeType.Unchanged],
    children: [
      { id: '2', value: 'b', change: [ChangeType.Inserted], children: [] },
    ],
  },
];

diffTrees(
  {
    id: '1',
    value: 'a',
    children: [
      { id: '2', value: 'b', children: [] },
      { id: '3', value: 'c', children: [] },
    ],
  },
  {
    id: '1',
    value: 'a',
    children: [
      { id: '3', value: 'c2', children: [] },
      { id: '2', value: 'b', children: [] },
    ],
  }
);

// =>

[
  {
    id: '1',
    value: 'a',
    change: [ChangeType.Unchanged],
    children: [
      {
        id: '3',
        value: 'c2',
        change: [ChangeType.Moved, ChangeType.Updated],
        children: [],
      },
      {
        id: '2',
        value: 'b',
        change: [ChangeType.Moved],
        children: [],
      },
    ],
  },
];