Tree package:tree-diff

Tree diffing working on containers Tree.

Diffing of (expression) trees. Diffing arbitrary Haskell data. First we convert values to untyped haskell-like expression Expr using generically derivable ToExpr class. Then we can diff two Expr values. The conversion and diffing is done by ediff function. See type and function haddocks for an examples. Interesting modules:

• Data.TreeDiff.Class for a ToExpr class and ediff utility.
• Data.TreeDiff.Golden for golden tests helper
• Data.TreeDiff.QuickCheck for QuickCheck helper

Diffing of (expression) trees. Common diff algorithm works on list structures:

diff :: Eq a => [a] -> [a] -> [Edit a]

This package works on trees.

treeDiff :: Eq a => Tree a -> Tree a -> Edit (EditTree a)

This package also provides a way to diff arbitrary ADTs, using Generics-derivable helpers. This package differs from gdiff, in a two ways: tree-diff doesn't have patch function, and the "edit-script" is a tree itself, which is useful for pretty-printing.

>>> prettyEditExpr $ ediff (Foo 42 [True, False] "old") (Foo 42 [False, False, True] "new")
Foo
{fooBool = [-True, +False, False, +True],
fooInt = 42,
fooString = -"old" +"new"}

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.