# Comparing Mathematica expressions like diff

I am looking for a way to compare (or "diff") two Mathematica expressions, similarly to how to diff utility can compare two text files and report the differences.

Has anyone already written such a thing? Do you know of existing implementations? I wanted to check before trying to implement it.

The Workbench's MUnit tester has something like this but I'm not sure how to invoke it separately from the testing UI. Also, I'd need something that works on held expressions as well.

A first and simplest implementation would detect "point-differences". Assuming that the two expressions have identical structure, it would detect the leaf that differs. For example, if the expressions are

Hold@{1, f[2, g[3, 4^5]]}

Hold@{1, f[2, g[3, 4.^5]]}


it would report that the difference is at position {1, 2, 2, 2, 1} (because 4 =!= 4.)

A second and improved version (what I'm really looking for) would also handle additions and deletions, i.e. in

{1,2,3,4,5}

{1,2,4,5}


it would be able to match up the 4,5 part and understand that only 3 has been deleted. This would of course work also if 1,2,... are compound expressions and not atoms, and would also work at deeper levels.

I need something that works on expressions and not on text, and respects the expression structure. (E.g. an atomic expression should be treated as an atom and not a set of characters. Line breaks, spaces and different notation forms such as f@x and f[x] should be handled or ignored appropriately.)

-
(This is not for diffing code, but unfortunately I still need it to work on held expressions) – Szabolcs May 1 '13 at 3:31
Do you have a clear idea of how it would ideally work? – Rojo May 1 '13 at 4:54
@Rojo See edit. – Szabolcs May 1 '13 at 13:05
I have developed similar functionality, but it was subject to even stronger requirements that one could take one expression and a diff structure, and be able to exactly reconstruct the other one. Do you need this feature, or would it be enough to just mark places where expressions are different, visually, for both expressions (in which case the code may be made much simpler)? – Leonid Shifrin May 1 '13 at 14:47
@Leonid I just need to see the difference clearly. I don't need to reconstruct the expression. – Szabolcs May 1 '13 at 15:31

### Implementation

The following implementation is based on expression serialization and SequenceAlignment built-in function. The idea is to break expressions into constituent parts, then align these part sequences, and then determine the positions where the expressions are different.

The auxiliary heads we will need are inert heads diff and myHold, the latter being HoldAll:

ClearAll[myHold,diff];
SetAttributes[myHold, HoldAll];


The following function will wrap expression in myHold (to prevent evaluation of parts) and record positions of all parts in a new expression:

ClearAll[expressionWrapIndex];
expressionWrapIndex[expression_Hold] :=
MapIndexed[
myHold,
expression,
{0, Infinity},
] //. myHold[expr : f_myHold[x___myHold], _] :> expr;


Here is an example:

expressionWrapIndex[Hold[a = 1]]

(* myHold[Hold, {0}][myHold[Set, {1, 0}][myHold[a, {1, 1}], myHold[1, {1, 2}]]] *)


The following function will "serialize" an expression obtained by calling expressionWrapIndex:

ClearAll[serialize];
serialize[expr_] := Cases[expr, _myHold, Infinity, Heads -> True];


for example:

serialize@expressionWrapIndex[Hold[a = 1]]

(* {myHold[Hold, {0}], myHold[Set, {1, 0}], myHold[a, {1, 1}], myHold[1, {1, 2}]} *)


The following function will align two serialized sequences of held parts:

ClearAll[alignSerialized];
alignSerialized[fst : {__myHold}, sec : {__myHold}] :=
Transpose[
Fold[
Replace[#, #2, {1}] &,
Apply[SequenceAlignment, {fst, sec} /. myHold[x_, pos_] :> myHold[x]],
{l : {_List, _List} :> diff @@@ l, l : {___myHold} :> {l, l}}
]
];


for example:

serialized =
Map[serialize@expressionWrapIndex@# &, {Hold[a = 1; b = 2], Hold[c = 1; d = 2]}];
aligned = alignSerialized @@ serialized

(*
{
{{myHold[Hold], myHold[CompoundExpression], myHold[Set]},
diff[myHold[a]], {myHold[1], myHold[Set]}, diff[myHold[b]], {myHold[2]}},
{{myHold[Hold], myHold[CompoundExpression], myHold[Set]},
diff[myHold[c]], {myHold[1], myHold[Set]}, diff[myHold[d]], {myHold[2]}}
}
*)


The head diff signals that we have a part in one expression which is different from its counterpart in another expression (can be also missing there).

The following function will find positions in original (wrapped in myHold) expressions of parts that are different:

ClearAll[diffPositions];
diffPositions[serparts_, alignedPart_] :=
With[{rules = Dispatch@Thread[Range[Length[#]] -> #] &@serparts},
Fold[
Cases[#, #2, Infinity] &,
Module[{n = 0}, alignedPart /. part_myHold :> ++n],
{d_diff :> (d /. rules), myHold[_, pos_] :> pos}
]];


for example, here are the positions where the first expression from the previous example has parts different from the other expression:

diffPositions[First@serialized, First@aligned]

(* {{1, 1, 1}, {1, 2, 1}} *)


The following function automates the application of a previous one to both expressions being compared:

ClearAll[diffPositionsInWrapped];
diffPositionsInWrapped[fst : {__myHold}, sec : {__myHold}] :=


For example:

diffPositionsInWrapped@@serialized

(* {{{1,1,1},{1,2,1}},{{1,1,1},{1,2,1}}} *)


The following function dresses sub-expressions at certain positions in an expression (wrapped in myHold), in some function f, without evaluating any parts:

ClearAll[dress];
dress[wrapped_, pos_List, f_] :=
Module[{ff},
Fold[
ReplaceRepeated,
MapAt[ff, wrapped, pos],
{
myHold[x_, _] :> x,
ff[x_][args___] :>
With[{eval = ff[myHold[x][myHold[args] //. ff[t_] :> t]]},
eval /; True],
h_[left___, myHold[x___], right___] :> h[left, x, right]
}
] /. myHold[x_] :> x /. ff[x__] :>
With[{eval = f[myHold[x]]}, eval /; True] /. myHold[x_] :> x
];


This function could have certainly be written better, I post here the first version I got to work.

Using the previous examples:

dress[
expressionWrapIndex@Hold[a = 1; b = 2],
diffPositions[First@serialized, First@aligned],
f]

(* Hold[f[a] = 1; f[b] = 2] *)


The following function takes two (held) expressions and returns their diff, which is, those expressions with parts that differ wrapped into an arbitrary function f:

ClearAll[showDiff];
showDiff[fst_, sec_, f_] :=
Module[{wrapped, ser, diffpos, ff},
wrapped = Map[expressionWrapIndex, {fst, sec}];
ser = Map[serialize, wrapped];
diffpos = diffPositionsInWrapped @@ ser;
];


It basically combines all the steps we considered before. For example:

showDiff[Hold[a=1;b=2],Hold[c=1;d=2],f]

(* {Hold[f[a]=1;f[b]=2],Hold[f[c]=1;f[d]=2]} *)


The following function serves to visualize the diff in some custom way:

ClearAll[visualExprDiff];
Options[visualExprDiff] = {Width -> 400};
visualExprDiff[fst_Hold, sec_Hold, opts : OptionsPattern[]] :=
Framed @ Pane[Grid[
List@Replace[
showDiff[fst, sec, Framed[Style[#, Red], Background -> LightYellow] &],
Hold[arg_] :>Framed@Pane[HoldForm[arg],OptionValue[Width],Scrollbars->True],
{1}
]
]];


For example:

visualExprDiff[Hold[a = 1; b = 2], Hold[c = 1; d = 2]]


### More examples

Here is a somewhat larger example:

expr =
Hold[
g[x_, y_] := (x + y)^2;
f[x_] := With[{result = x^2}, result /; result < 100];
a := ff[expr : f_[x___myHold], _] :> expr;
];

newexpr =
Hold[
f[x_] := With[{result = x^2, y = 1}, result /; result < 100];
aa := ff[expr : f_myHold[x___myHold], _] :> expr
];


Now using our function:

visualExprDiff[expr, newexpr]


Yet larger example:

newCode =
Hold[
"The test file does not comply with the accepted test file structure";
getTestFileCode[testFileName_String, opts___?OptionQ] :=
With[{filecontent = getTestFileContent[testFileName, opts]},
With[{result =
stripOffCompoundExpressionsNew[filecontent] /. {
Hold[
init_InitCode,
tests___Test?(Function[test, testValidQ[Hold[test]], HoldAll])
] :> TestFileCode[init, AllTests[tests]]}
},
]
];
getTestFileCode[___] := $Failed; ];  and oldCode = Hold[ Options[getTestFileCode] = {ShortPathName -> True}; getTestFileCode[testFileName_String, opts___?OptionQ] := With[{filecontent = getTestFileContent[testFileName, opts]}, With[{result = stripOffCompoundExpressions[filecontent] /. { Hold[ init_InitCode, tests___Test?(Function[test, testValidQ[Hold[test]],HoldAll])] :> TestFileCode[init, AllTests[tests]]} }, result /; Head[result] === TestFileCode ] ]; getTestFileCode[___] :=$Failed;
];


and now:

visualExprDiff[newCode, oldCode]


### Full code

Here I will once again supply all the code. Later I will make this a package and place it on Github, then I will remove this section.

ClearAll[myHold,diff];
SetAttributes[myHold, HoldAll];

ClearAll[expressionWrapIndex];
expressionWrapIndex[expression_Hold] :=
MapIndexed[
myHold,
expression,
{0, Infinity},
] //. myHold[expr : f_myHold[x___myHold], _] :> expr;

ClearAll[serialize];
serialize[expr_] := Cases[expr, _myHold, Infinity, Heads -> True];

ClearAll[alignSerialized];
alignSerialized[fst : {__myHold}, sec : {__myHold}] :=
Transpose[
Fold[
Replace[#, #2, {1}] &,
Apply[SequenceAlignment, {fst, sec} /. myHold[x_, pos_] :> myHold[x]],
{l : {_List, _List} :> diff @@@ l, l : {___myHold} :> {l, l}}
]
];

ClearAll[diffPositions];
diffPositions[serparts_, alignedPart_] :=
With[{rules = Dispatch@Thread[Range[Length[#]] -> #] &@serparts},
Fold[
Cases[#, #2, Infinity] &,
Module[{n = 0}, alignedPart /. part_myHold :> ++n],
{d_diff :> (d /. rules), myHold[_, pos_] :> pos}
]];

ClearAll[diffPositionsInWrapped];
diffPositionsInWrapped[fst : {__myHold}, sec : {__myHold}] :=

ClearAll[dress];
dress[wrapped_, pos_List, f_] :=
Module[{ff},
Fold[
ReplaceRepeated,
MapAt[ff, wrapped, pos],
{
myHold[x_, _] :> x,
ff[x_][args___] :>
With[{eval = ff[myHold[x][myHold[args] //. ff[t_] :> t]]},
eval /; True],
h_[left___, myHold[x___], right___] :> h[left, x, right]
}
] /. myHold[x_] :> x /. ff[x__] :>
With[{eval = f[myHold[x]]}, eval /; True] /. myHold[x_] :> x
];

ClearAll[showDiff];
showDiff[fst_, sec_, f_] :=
Module[{wrapped, ser, diffpos, ff},
wrapped = Map[expressionWrapIndex, {fst, sec}];
ser = Map[serialize, wrapped];
diffpos = diffPositionsInWrapped @@ ser;
];

ClearAll[visualExprDiff];
Options[visualExprDiff] = {Width -> 400};
visualExprDiff[fst_Hold, sec_Hold, opts : OptionsPattern[]] :=
Framed @ Pane[Grid[
List@Replace[
showDiff[fst, sec, Framed[Style[#, Red], Background -> LightYellow] &],
Hold[arg_] :>Framed@Pane[HoldForm[arg],OptionValue[Width],Scrollbars->True],
{1}
]
]];

-
I always get slightly excited when I see a new post from you, and rarely am I disappointed. I'll enjoy reading this later. – Mr.Wizard May 1 '13 at 20:57
@Mr.Wizard Sounds good :-). Thanks for the upvote. – Leonid Shifrin May 1 '13 at 20:58
Very nice! Is this a step in the direction of an undo function? – Sjoerd C. de Vries May 3 '13 at 22:02
@SjoerdC.deVries Yes, one can say that. Although, for the purposes of undo, one would need a more advanced version of this, that would reconstruct one expression exactly from another one and the diff structure. But in the past I have developed this sort of diff as well, could probably improve that and bring up to date. – Leonid Shifrin May 4 '13 at 11:24

If you can convert expressions to text form, there's a possible answer here. I sometimes use it to compare notebooks:

notebook1 =
StringJoin[
Import["/tmp/freaky-illusion.nb", "Plaintext"]];
notebook2 =
StringJoin[
Import["/tmp/freaky-illusion-1.nb", "Plaintext"]];

SystemDumpshowStringDiff[notebook1, notebook2]


-
@szabolcs I see that my answer is no longer very applicable to the question, since you don't want to go to text form. I'll leave it here, because I liked rm's linked answer... – cormullion May 1 '13 at 14:47
Please leave your answer. It's not exactly what I'm looking for but it's valuable information. I should have made it more clear that I'm looking for expression diff and not text diff. – Szabolcs May 1 '13 at 15:42

For diff'ing code fragments/expressions, you can copy-and-paste as "Plain Text" into Quick Diff (online) or into WinMerge (PC-based), ref. http://stackoverflow.com/q/15655828/879601 (also mentions a Mac-based method using Bash).

E.g. WinMerge:-

(For diff'ing packages and notebooks I favour CSDiff.)

-