Re: A better approach to diffing and merging

From: Boyd Stephen Smith Jr. <bss03@volumehost.net>
Date: Nov 29, 2008, 23:40 UTC
Message-ID: <200811291740.06865.bss03@volumehost.net>
In-Reply-To: <823242bd0811291012g15c4d442qa5d7afc9cc762b20@mail.gmail.com>

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.                     ,= ,-_-. =. 
bss03@volumehost.net                      ((_/)o o(\_))
ICQ: 514984 YM/AIM: DaTwinkDaddy           `-'(. .)`-' 
http://iguanasuicide.org/                      \_/