Semantic Diff Utilities

Question

I'm trying to find some good examples of semantic diff/merge utilities. The traditional paradigm of comparing source code files works by comparing lines and characters.. but are there any utilities out there (for any language) that actually consider the structure of code when comparing files?

For example, existing diff programs will report "difference found at character 2 of line 125. File x contains v-o-i-d, where file y contains b-o-o-l". A specialized tool should be able to report "Return type of method doSomething() changed from void to bool".

I would argue that this type of semantic information is actually what the user is looking for when comparing code, and should be the goal of next-generation progamming tools. Are there any examples of this in available tools?

Answer 1

Don't know how any tool that cute but would love to hear from it !

Looks like you want a tool that compares the parse tree rather than the source itself....

A first step could be to use a pretty printer before diff, eliminating any difference that affect only presentation and not meaning.

A better one would be to have a representation of the parsed code and diff from there... Anyone knows of good diff algorithm for trees ?

Answer 2

First off, I havent heard of any tool that works like this.

But as pointed out, it seems that youre aiming to compare the source tree rather than the text itself, as diff tools usually does. Maybe the first step is to check how different code completion tools build their trees, such as Visual Assist, and compare them.

Take the base copy and the working copy, build a tree from each and compare the trees.

Answer 3

The solution to this would be on a per language basis. I.e. unless it's designed with a plugin architecture that defers a lot of the parsing of the code into a tree and the semantic comparison to a language specific plugin then it will be very difficult to support multiple languages. What language(s) are you interested in having such a tool for. Personally I'd love one for C#.

For C# there is an assembly diff add-in to Reflector but it only does a diff on the IL not the C#.

You can download the diff add-in here [zip] or go to the project on the codeplex site here.

Answer 4

What you're groping for is a "tree diff". It turns out that this is much harder to do well than a simple line-oriented textual diff, which is really just the comparison of two flat sequences.

"A Fine-Grained XML Structural Comparison Approach" concludes, in part with:

Our theoretical study as well as our experimental evaluation showed that the proposed method yields improved structural similarity results with respect to existing alternatives, while having the same time complexity (O(N^2))

(emphasis mine)

Indeed, if you're looking for more examples of tree differencing I suggest focusing on XML since that's been driving practical developments in that area.

Answer 5

Eclipse has had this feature for a long time. It's called "Structure Compare", and it's very nice. Here is a sample screenshot for Java, followed by another for an XML file:

(Note the minus and plus icons on methods in the upper pane.)

Answer 6

To do "semantic comparisons" well, you need to compare the syntax trees of the languages, and take into account the meaning of symbols. A really good semantic diff would understand the language semantics, and realize when one block of code was equivalent in function to another. Going this far requires a theorem prover, and while it would be extremely cute, isn't presently practical for a real tool.

A workable approximation of this is simply comparing syntax trees, and reporting changes in terms of structures inserted, deleted, moved, or changed. Getting somewhat closer to a "semantic comparison", one could report when an identifier is changed consistently across a block of code.

See http://www.semanticdesigns.com/Products/SmartDifferencer/index.html for a syntax tree-based comparison engine that works with many languages, that does the above approximation.

EDIT Jan 2010: Versions available for C++, C#, Java, PHP, and COBOL. The website shows specific examples for most of these.

EDIT May 2010: Python and JavaScript added.

EDIT Oct 2010: EGL added.

Answer 7

A company called Zynamics offers a binary-level semantic diff tool. It uses a meta-assembly language called REIL to perform graph-theoretic analysis of 2 versions of a binary, and produces a color-coded graph to illustrate differences between them. I am not sure of the price, but I doubt it is free.