Subject: Re: A better approach to diffing and merging

From: "Boyd Stephen Smith Jr." <[email-masked]>
Date: Sat, 29 Nov 2008 17:40:02 -0600

On Saturday 2008 November 29 12:12, Ian Clarke wrote:
> While I'm no merging expert, it seems that most merging algorithms do
> it on a line-by-line basis, treating source code as nothing but a list
> of lines of text.  It got me thinking, what if the merging algorithm
> understood the structure of the source code it is trying to merge?

Unfortunately, this is hard to do in general.  Not impossible, but very hard.  
Heck, some languages don't really have a formal grammar, or have one that is 
undecidable without doing deeper analysis.  Perl 6 is supposed to have some 
support for language constructs that change the grammar.

Also, this generally takes a lot of time.  Automatic merges are only useful if 
they take less (or only a little more) time than doing the merge manually.  
If your mergetool has to think about something for 30 minutes that you could 
have resolved in 5, it's not normally a "win".

Also, it slightly changes the format of a "patch" file.  Currently, patch 
files are a line-by-line diff.  If you instead made changes based on mapping 
parse trees to parse trees, you'd (probably) want to 
store/transfer/communicate your patches using a different format, to preserve 
the proper amount of "context" and make the patch easy to apply.  (I.e., do 
the hard work once.)

> Any takers? I've set up a Google Group for further discussion, please
> join if interested.

You might look deeper into Darcs development.  This level of 
pluggable "understanding" of the file(s) being modified fits in well with a 
Grand Unified Theory of Patching.  Also "understanding" patches better allows 
Darcs to reorder patches (and calculate "reverse patches") better -- reducing 
the time to do existing automatic merging (or reject the merge as 
non-automatable) and make merges automatic that are currently not handled 
automatically.

I'm not going to come out and discourage you or other from adding the 
functionality to git, but I think there are more useful and practical ways to 
improve git.  (Line-by-line merging is generally "good enough", the worst 
enemy of "good" software.)
-- 
Boyd Stephen Smith Jr.                     ,= ,-_-. =. 
[email-masked]                      ((_/)o o(\_))
ICQ: 514984 YM/AIM: DaTwinkDaddy           `-'(. .)`-' 
http://iguanasuicide.org/                      \_/