Comparing Mathematica expressions like diff

Question

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.

---

To answer @Rojo's question:

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.)

Answer 1

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}, 
     Heads -> True
  ] //. 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}] :=
   MapThread[diffPositions, {{fst, sec}, alignSerialized[fst, sec]}];

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;
     MapThread[dress[##, f] &, {wrapped, diffpos}]
   ];

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[
    getTestFileCode::badfile = 
      "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]]}
          }, 
          result /; Head[result] === TestFileCode
        ]
      ];
    getTestFileCode[_String] := "" /; Message[getTestFileCode::badfile];
    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}, 
     Heads -> True
  ] //. 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}] :=
   MapThread[diffPositions, {{fst, sec}, alignSerialized[fst, sec]}];

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;
     MapThread[dress[##, f] &, {wrapped, diffpos}]
   ];

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}
    ]
  ]];

Answer 2

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"]];

System`Dump`showStringDiff[notebook1, notebook2]

Answer 3

For diff'ing code fragments/expressions, you can copy-and-paste as "Plain Text" into Quick Diff (online) or into WinMerge (PC-based), ref. https://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.)