This makes me wonder if anyone has implemented diff by comparing the Abstract Syntax Trees of the two code-bases. I guess it's probably easier than regular diff (assuming you've already got the ASTs from somewhere).
I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines.
Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
Tree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N).
Tree diff is harder because the range of operations is bigger.
React.js cheats by insisting on keys for arrays so matching is much easier.
