Documentation

A breadth-traversal diff.

It's different from gdiff, as it doesn't produce a flat edit script, but edit script iself is a tree. This makes visualising the diff much simpler.

Examples

Let's start from simple tree. We pretty print them as s-expressions.

>>> let x = Node 'a' [Node 'b' [], Node 'c' [return 'd', return 'e'], Node 'f' []]
>>> ppTree PP.char x
(a b (c d e) f)

If we modify an argument in a tree, we'll notice it's changed:

>>> let y = Node 'a' [Node 'b' [], Node 'c' [return 'x', return 'e'], Node 'f' []]
>>> ppTree PP.char y
(a b (c x e) f)

>>> ppEditTree PP.char (treeDiff x y)
(a b (c -d +x e) f)

If we modify a constructor, the whole sub-trees is replaced, though there might be common subtrees.

>>> let z = Node 'a' [Node 'b' [], Node 'd' [], Node 'f' []]
>>> ppTree PP.char z
(a b d f)

>>> ppEditTree PP.char (treeDiff x z)
(a b -(c d e) +d f)

If we add arguments, they are spotted too:

>>> let w = Node 'a' [Node 'b' [], Node 'c' [return 'd', return 'x', return 'e'], Node 'f' []]
>>> ppTree PP.char w
(a b (c d x e) f)

>>> ppEditTree PP.char (treeDiff x w)
(a b (c d +x e) f)

Type used in the result of treeDiff.

It's essentially a Tree, but the forest list is changed from [tree a] to [Edit (tree a)]. This highlights that treeDiff performs a list diff on each tree level.

List edit operations

The Swp constructor is redundant, but it let us spot a recursion point when performing tree diffs.