{"thread":{"id":"16521","subject":"A better approach to diffing and merging","startedAt":"2008-11-29T18:12:05Z","lastAt":"2008-12-02T08:37:26Z","messageCount":7,"participants":["Ian Clarke","Boyd Stephen Smith Jr.","Brian Dessent","Miklos Vajna","Karl Hasselström","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"96731","messageId":"823242bd0811291012g15c4d442qa5d7afc9cc762b20@mail.gmail.com","threadId":"16521","inReplyTo":null,"subject":"A better approach to diffing and merging","fromName":"Ian Clarke","fromEmail":"ian.clarke@gmail.com","sentAt":"2008-11-29T18:12:05Z","receivedAt":"2008-11-29T18:12:05Z","isPatch":false,"sender":{"key":"ian.clarke@gmail.com","avatar":null},"body":"Apologies if this is off-topic, but I recently had an idea for a\nbetter way to do diffs and merging which I thought may be of interest\nto those on this list.\n\nI described it in a blog entry here: http://budurl.com/jyt6\n\nFor your convenience text is pasted below (although missing a few hyperlinks):\n\nA plan for better source code diffs and merging\n======================================\n\nI've been using Subversion for years, but a few months ago I was\nreally starting to feel the limitations of being able to create and\nmerge branches easily. I'd heard that Git made this very easy indeed,\nand so I decided to try it.\n\nAnyway, this isn't yet another \"I discovered Git and now I've achieved\nself-actualization\" blog post, so to cut a long story short, I now use\ngit for everything (together with the excellent GitHub).\n\nEven though merging is a lot better with Git than Subversion, I've\nstill found myself getting into situations where it requires a lot of\nwork to merge a branch back into another branch, and it got me\nthinking about better ways to do merging.\n\nWhile I'm no merging expert, it seems that most merging algorithms do\nit on a line-by-line basis, treating source code as nothing but a list\nof lines of text.  It got me thinking, what if the merging algorithm\nunderstood the structure of the source code it is trying to merge?\n\nSo the idea is this:\n\nProvide the merge algorithm with the grammar of the programming\nlanguage, perhaps in the form of a Bison grammar file, or some other\nstandardized way to represent a grammar.\n\nThe merge algorithm then uses this to parse the files to be diffed\nand/or merged into trees, and then the diff and merge are treated as\noperations on these trees.  These operations may include creating,\ndeleting, or moving nodes or branches, renaming nodes, etc.  There has\nbeen quite a bit (pdf) of academic research on this topic, although I\nhaven't yet found off-the-shelf code that will do what we need.\nStill, it shouldn't be terribly hard to implement.\n\nThe beauty of this approach is that the merge algorithm should be far\nless likely to be confused by formatting changes, and much more likely\nto correctly identify what has changed.\n\nI can't think of any reason that such a tool wouldn't work in the\nexact same way as existing diff/merge tools from the programmer's\nperspective. The tool would automatically select the correct grammar\nbased on the file extension, or fall-back to line-based diffs if the\nextension is unrecognized (or the file isn't valid for the selected\ngrammar). Thus, it should be trivial to use this new tool with\nexisting version control systems.\n\nI'd love to have the time to implement this, although regretfully it\nis at the bottom of a very large pile of \"some day\" projects.  I think\nthis is an interesting enough idea, and one that would be immediately\nuseful, that if I put it out there someone somewhere might be able to\nmake it a reality.\n\nAny takers? I've set up a Google Group for further discussion, please\njoin if interested.\n"},{"id":"96745","messageId":"200811291740.06865.bss03@volumehost.net","threadId":"16521","inReplyTo":"823242bd0811291012g15c4d442qa5d7afc9cc762b20@mail.gmail.com","subject":"Re: A better approach to diffing and merging","fromName":"Boyd Stephen Smith Jr.","fromEmail":"bss03@volumehost.net","sentAt":"2008-11-29T23:40:02Z","receivedAt":"2008-11-29T23:40:02Z","isPatch":false,"sender":{"key":"bss03@volumehost.net","avatar":"https://gravatar.com/avatar/74fa10b37dfd44462a6a30c4d4e3bda26ab7991ddb0d8ab24b022714a8ecb918?d=mp&s=160"},"body":"On Saturday 2008 November 29 12:12, Ian Clarke wrote:\n> While I'm no merging expert, it seems that most merging algorithms do\n> it on a line-by-line basis, treating source code as nothing but a list\n> of lines of text.  It got me thinking, what if the merging algorithm\n> understood the structure of the source code it is trying to merge?\n\nUnfortunately, this is hard to do in general.  Not impossible, but very hard.  \nHeck, some languages don't really have a formal grammar, or have one that is \nundecidable without doing deeper analysis.  Perl 6 is supposed to have some \nsupport for language constructs that change the grammar.\n\nAlso, this generally takes a lot of time.  Automatic merges are only useful if \nthey take less (or only a little more) time than doing the merge manually.  \nIf your mergetool has to think about something for 30 minutes that you could \nhave resolved in 5, it's not normally a \"win\".\n\nAlso, it slightly changes the format of a \"patch\" file.  Currently, patch \nfiles are a line-by-line diff.  If you instead made changes based on mapping \nparse trees to parse trees, you'd (probably) want to \nstore/transfer/communicate your patches using a different format, to preserve \nthe proper amount of \"context\" and make the patch easy to apply.  (I.e., do \nthe hard work once.)\n\n> Any takers? I've set up a Google Group for further discussion, please\n> join if interested.\n\nYou might look deeper into Darcs development.  This level of \npluggable \"understanding\" of the file(s) being modified fits in well with a \nGrand Unified Theory of Patching.  Also \"understanding\" patches better allows \nDarcs to reorder patches (and calculate \"reverse patches\") better -- reducing \nthe time to do existing automatic merging (or reject the merge as \nnon-automatable) and make merges automatic that are currently not handled \nautomatically.\n\nI'm not going to come out and discourage you or other from adding the \nfunctionality to git, but I think there are more useful and practical ways to \nimprove git.  (Line-by-line merging is generally \"good enough\", the worst \nenemy of \"good\" software.)\n-- \nBoyd Stephen Smith Jr.                     ,= ,-_-. =. \nbss03@volumehost.net                      ((_/)o o(\\_))\nICQ: 514984 YM/AIM: DaTwinkDaddy           `-'(. .)`-' \nhttp://iguanasuicide.org/                      \\_/     \n"},{"id":"96757","messageId":"4931F2DC.CE9B1E35@dessent.net","threadId":"16521","inReplyTo":"823242bd0811291012g15c4d442qa5d7afc9cc762b20@mail.gmail.com","subject":"Re: A better approach to diffing and merging","fromName":"Brian Dessent","fromEmail":"brian@dessent.net","sentAt":"2008-11-30T01:56:44Z","receivedAt":"2008-11-30T01:56:44Z","isPatch":false,"sender":{"key":"brian@dessent.net","avatar":null},"body":"Ian Clarke wrote:\n\n> Provide the merge algorithm with the grammar of the programming\n> language, perhaps in the form of a Bison grammar file, or some other\n> standardized way to represent a grammar.\n> \n> The merge algorithm then uses this to parse the files to be diffed\n> and/or merged into trees, and then the diff and merge are treated as\n> operations on these trees.  These operations may include creating,\n> deleting, or moving nodes or branches, renaming nodes, etc.  There has\n> been quite a bit (pdf) of academic research on this topic, although I\n> haven't yet found off-the-shelf code that will do what we need.\n> Still, it shouldn't be terribly hard to implement.\n\nThere's a huge flaw in that approach for C/C++: in order to parse C/C++\nyou have to first preprocess it -- consider the twisty mazes that\n#ifdef/#else/#endif can create.  But in order to preprocess source code\nyou need a whole heap of extra information that is not in the repository\n(or if it is, cannot be automatically extracted.)\n\nFor example, you'd have to know all the -D/-U/-I flags that the makefile\nor the user might pass to the compiler.  You'd have to replicate the\ncompiler's complicated header search path algorithm, which can depend on\nthe directives in the code as well as command line arguments,\nenvironment variables, and values specific to the toolchain.  (Don't\nforget that you can have code in a repository that's meant to be\ncross-compiled and which uses a toolchain that has its own headers and\nnot the ones in /usr/include.)  You'd have to know all the built-in\npredefined symbols of that toolchain, e.g. what's the value of\n__GNUC_MINOR__ or __GNUC_PATCHLEVEL__, is __mips__ or __i386__ defined,\nand on and on.  And of course the natural conclusion of this\nprogression: a change can be perfectly grammatically correct for one\nparticular platform/toolchain/setting of CFLAGS, and completely broken\nfor another.  There's no way for a VCS to know any of this, it takes\nhuman comprehension.\n\nIf you look at a tool like doxygen that attempts to parse C/C++, it\ndon't actually do full preprocessing, only a very limited subset: it\nonly expands macros that the user names as relevant in the config file,\nand it only preprocesses included headers that match a pathspec the user\nprovides.  Consequently it cannot fully parse the code to see if it's\ngrammatically correct, only to the limited extent that it can infer the\nlocation where things appear to be defined.  And it is easily confused,\ne.g. it will \"see\" code in both halves of an #ifdef section if it wasn't\ntold anything about the value of the macro in the config file, which can\ncause it to incorrectly think that a function or variable was defined\nthere when in reality that section was discarded.\n\nThe idea may have value for langauges that are easy to parse and do not\nhave all this preprocessor cruft, but I just don't see how it would be\nable to provide anything useful for non-trivial changes to real world\nC/C++, which require human eyes to decipher.\n\nBrian\n"},{"id":"96758","messageId":"20081130025408.GO19355@genesis.frugalware.org","threadId":"16521","inReplyTo":"200811291740.06865.bss03@volumehost.net","subject":"Re: A better approach to diffing and merging","fromName":"Miklos Vajna","fromEmail":"vmiklos@frugalware.org","sentAt":"2008-11-30T02:54:08Z","receivedAt":"2008-11-30T02:54:08Z","isPatch":false,"sender":{"key":"vmiklos@frugalware.org","avatar":"https://gravatar.com/avatar/401c1cbbb3a5d13e650c691a2c71d6fd0b80df1a01bc74d9f1972675dd58f2bd?d=mp&s=160"},"body":"On Sat, Nov 29, 2008 at 05:40:02PM -0600, \"Boyd Stephen Smith Jr.\" <bss03@volumehost.net> wrote:\n> You might look deeper into Darcs development.  This level of \n> pluggable \"understanding\" of the file(s) being modified fits in well with a \n> Grand Unified Theory of Patching.  Also \"understanding\" patches better allows \n> Darcs to reorder patches (and calculate \"reverse patches\") better -- reducing \n> the time to do existing automatic merging (or reject the merge as \n> non-automatable) and make merges automatic that are currently not handled \n> automatically.\n> \n> I'm not going to come out and discourage you or other from adding the \n> functionality to git, but I think there are more useful and practical ways to \n> improve git.  (Line-by-line merging is generally \"good enough\", the worst \n> enemy of \"good\" software.)\n\nI think this was already discussed:\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/60457/focus=60512\n\nIf you mean just looking at the code moves/copies between the trees (but\nno other history), then a merge strategy which makes use of git blame's\ncode move/copy detection would be indeed nice, though nobody created it\nso far.\n"},{"id":"96822","messageId":"20081201095449.GA30857@diana.vm.bytemark.co.uk","threadId":"16521","inReplyTo":"4931F2DC.CE9B1E35@dessent.net","subject":"Re: A better approach to diffing and merging","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2008-12-01T09:54:49Z","receivedAt":"2008-12-01T09:54:49Z","isPatch":false,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2008-11-29 17:56:44 -0800, Brian Dessent wrote:\n\n> Ian Clarke wrote:\n>\n> > Provide the merge algorithm with the grammar of the programming\n> > language, perhaps in the form of a Bison grammar file, or some\n> > other standardized way to represent a grammar.\n>\n> There's a huge flaw in that approach for C/C++: in order to parse\n> C/C++ you have to first preprocess it -- consider the twisty mazes\n> that #ifdef/#else/#endif can create. But in order to preprocess\n> source code you need a whole heap of extra information that is not\n> in the repository (or if it is, cannot be automatically extracted.)\n\nBut it's probably not necessary to parse the input files exactly. All\nyou have to do is parse it well enough that the diff of the parse\ntrees is interesting.\n\nAnd in practice, you'd probably also generate the \"normal\" diff, and\nthen fall back to that one if the parse tree diff was worse.\n\n> The idea may have value for langauges that are easy to parse and do\n> not have all this preprocessor cruft, but I just don't see how it\n> would be able to provide anything useful for non-trivial changes to\n> real world C/C++, which require human eyes to decipher.\n\nI think it could work. But there would be quite a bit of heuristics\ninvolved to get the \"approximate\" parsing right, so I'm pretty sure\nthere's no way to find out without actually trying to build the thing.\n\n-- \nKarl Hasselström, kha@treskal.com\n      www.treskal.com/kalle\n"},{"id":"96828","messageId":"m3y6z0i0mu.fsf@localhost.localdomain","threadId":"16521","inReplyTo":"823242bd0811291012g15c4d442qa5d7afc9cc762b20@mail.gmail.com","subject":"Re: A better approach to diffing and merging","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-12-01T11:41:38Z","receivedAt":"2008-12-01T11:41:38Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"\"Ian Clarke\" <ian.clarke@gmail.com> writes:\n\n> Apologies if this is off-topic, but I recently had an idea for a\n> better way to do diffs and merging which I thought may be of interest\n> to those on this list.\n\n[...]\n> While I'm no merging expert, it seems that most merging algorithms do\n> it on a line-by-line basis, treating source code as nothing but a list\n> of lines of text.  It got me thinking, what if the merging algorithm\n> understood the structure of the source code it is trying to merge?\n> \n> So the idea is this:\n> \n> Provide the merge algorithm with the grammar of the programming\n> language, perhaps in the form of a Bison grammar file, or some other\n> standardized way to represent a grammar.\n> \n> The merge algorithm then uses this to parse the files to be diffed\n> and/or merged into trees, and then the diff and merge are treated as\n> operations on these trees.  These operations may include creating,\n> deleting, or moving nodes or branches, renaming nodes, etc.  There has\n> been quite a bit (pdf) of academic research on this topic, although I\n> haven't yet found off-the-shelf code that will do what we need.\n\nFirst, as Brian Dessent said it would be hard to generate parse tree\nin the presence of compile-time configuration (using preprocessor\nin C/C++, but in principle this applies to programs in any language;\nnot only you have to know conditionals, but also compile options).\nAnd for dynamic languages you would have to take care about\nself-modifying programs.\n\nSecond, from what I understand we have _good_, established algorithms\nfor merging sequences (which includes sequence of lines, or sequence\nof words), and for merging special kinds of trees that are\nrepresentations of directory structure.  I haven't read link to\nmentioned research, but I think that it is still unproven research,\nand not something well established and well tested.\n\nThird, it would require embedding knowledge about various programming\nlanguages (including C, shell, Perl, TeX) and document formats\n(including XML, HTML, AsciiDoc) in version control system...\n\n> Still, it shouldn't be terribly hard to implement.\n\nSo, try to provide us with some proof-of-concept patches, then.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"96934","messageId":"20081202083726.GA17563@diana.vm.bytemark.co.uk","threadId":"16521","inReplyTo":"m3y6z0i0mu.fsf@localhost.localdomain","subject":"Re: A better approach to diffing and merging","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2008-12-02T08:37:26Z","receivedAt":"2008-12-02T08:37:26Z","isPatch":false,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2008-12-01 03:41:38 -0800, Jakub Narebski wrote:\n\n> Third, it would require embedding knowledge about various programming\n> languages (including C, shell, Perl, TeX) and document formats\n> (including XML, HTML, AsciiDoc) in version control system...\n\nReally? I was under the impression that you could specify external\ndiff and merge programs in .gitattributes, which would be precisely\nthe right way to hook this stuff into git.\n\n-- \nKarl Hasselström, kha@treskal.com\n      www.treskal.com/kalle\n"}]}