{"thread":{"id":"23545","subject":"'git notes merge' implementation questions","startedAt":"2010-04-21T07:57:47Z","lastAt":"2010-04-22T08:38:25Z","messageCount":10,"participants":["Johan Herland","Jonathan Nieder","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"140014","messageId":"201004210957.48138.johan@herland.net","threadId":"23545","inReplyTo":null,"subject":"'git notes merge' implementation questions","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-21T07:57:47Z","receivedAt":"2010-04-21T07:57:47Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Hi,\n\nI'm planning the implementation of 'git notes merge', a new 'git notes'\nsubcommand that will (in addition to various options not yet determined)\ntake a <notes_ref> argument, identifying a notes tree to be merged into\nthe _current_ notes_ref (as specified with --ref, $GIT_NOTES_REF,\ncore.notesRef, or defaulted to \"refs/notes/commits\").\n\nThis subcommand will typically be used when pulling notes from remotes.\nWhat follows, are my thoughts on how this command should work, and\nimplementation challenges/problems that I'm not yet sure how to solve:\n\nFor merges between notes refs with no common history the merge should be\na straightforward joining of trees. This also covers the \"history-less\"\nnotes refs, like Peff's notes-cache, and should work whether the notes\nrefs point to parentless commits, or point directly to tree objects (if\nwe want to support that). For merges between notes refs with common\nhistory we want to do a (more or less regular) three-way merge.\n\nIn both cases (with or without common history), conflicts may ensue,\nand these must of course be resolved in some way. Since the notes refs\nhave no accompanying worktree, we must find some other way to resolve\nconflicts. See the discussion on \"conflict resolvers\" below for more\ndetails.\n\nI would like to adapt the current merge machinery to do most of the\nwork for us, but there are some non-trivial challenges in adapting it\nto the needs of the 'git notes merge' command. AFAICS, there are two\nmajor problems:\n\n\n1. Handling different notes-tree fanouts in a merge scenario\n\n   Notes trees adjust their fanout automatically based on the number\n   of notes, and we will inevitably have to merge notes trees with\n   _different_ fanouts. This must be handled in some fashion, so that\n   conflicting notes for the same object - but located at different\n   fanouts - are properly conflict-resolved.\n\n   Possible solution: When building the index, add a callback (within\n   'read-tree'?) that may manipulate each entry added to the index.\n   Provide a callback that simply removes all directory separators,\n   thus normalising all note object names to their 40-char SHA1. As a\n   result, the merge happens in a large flat \"directory\" with no\n   \"subdirs\". When converting the index back into a notes tree, we\n   obviously need to auto-establish an appropriate fanout.\n\n   Remaining problem: How do we still ignore/skip identical subtrees?\n\n   Alternative solution: As a pre-merge step, require that the notes\n   trees are forced/rewritten to a common fanout (rewriting the smaller\n   notes tree into the fanout of the larger notes tree).\n\n\n2. Merging without a worktree\n\n2.1 Problem: 'git merge' operates on the current HEAD.\n\n    Possible solution: Allow 'merge' to update a ref that is not HEAD\n    (i.e. remove HEAD from all merge logic). Instead, allow users to\n    explicitly specify which ref to update (and thus the first parent\n    of the merge).\n\n2.2 Problem: 'git merge' operates on the current index.\n\n    Simple solution: Provide a separate index (using $GIT_INDEX_FILE)\n    in which the merge can take place (possibly using the modified\n    'read-tree' from above)\n\n2.3 Problem: 'git merge' updates the worktree.\n\n    Simple solution:  When 'merge' has prepared an index (containing\n    unmerged entries), _don't_ start looking for a working tree.\n    Instead, invoke conflict resolvers on the unmerged entries (see\n    below).\n\n2.4 Problem: Resolving conflicts without a worktree.\n\n    Possible solution: Conflict resolvers:\n\n    These are functions/programs that resolve unmerged entries in the\n    index without requiring a worktree. There should be several\n    built-in/bundled conflict resolvers, and it should be possible for\n    the user to choose between them, and also to add _additional_\n    (custom) conflict resolvers. The merge machinery should have a\n    simple interface against the conflict resolvers, with 3 inputs\n    (<base SHA1>, <ours SHA1>, <theirs SHA1>) and 1 output\n    (<resulting SHA1>).\n    The bundled conflict resolvers should at least include:\n\n    - \"ours\" (similar to 'git merge-file --ours')\n    - \"theirs\" (similar to 'git merge-file --theirs')\n    - \"union\" (similar to 'git merge-file --union')\n\n    In addition to the fully automatic resolvers, there may be room for\n    additional conflict resolvers that require user interaction:\n\n    - \"edit\" (manually resolve conflicts in an editor)\n    - \"mergetool\" (manually resolve conflicts in the chosen mergetool)\n\n    These resolvers would follow the same interface towards the merge\n    machinery, and the resolvers are thus responsible for preparing\n    whatever temporary file(s) and/or invoking whatever editors,\n    mergetools or other user interactions that are needed.\n\n\nAs you may see from the above, I'm not very familiar with the merge\nmachinery and manipulation of the index (currently struggling to grok\nmerge.c...). I hope to re-use as much as possible of the current merge\nlogic (instead of re-implementing it), but I might be ignorant of\ncertain details that simplifies, or complicates, the implementation of\n'git notes merge'.\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140045","messageId":"20100421171227.GA23794@progeny.tock","threadId":"23545","inReplyTo":"201004210957.48138.johan@herland.net","subject":"Re: 'git notes merge' implementation questions","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-04-21T17:12:27Z","receivedAt":"2010-04-21T17:12:27Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Johan Herland wrote:\n\n> 2. Merging without a worktree\n\nEh, I am not a fan.  I am thinking it might be better to use something\nlike contrib/workdir to make a temporary worktree with its own index\nand HEAD in .git/tmp-merge-notes and let the conflict resolvers work\nthere.\n\nAdvantages:\n\n - easy to debug when something goes wrong\n - merge driver can take other unmerged entries into account\n - (if merging manually) the user is not at the mercy of the program.\n   Instead of being forced to consider the conflicts in the order git\n   wants, she can skip some and go back to them, look at how many\n   there are before deciding to start work, resolve some, reboot to\n   test a new kernel, resolve some more later, and visualize the\n   result.\n - if the unmerged notes are very long, you might need a temporary\n   file anyway\n - maybe some day a kind of rename detection could help cope with\n   situations like propagation of notes after a rebase\n\nDisadvantages:\n\n - setting up a new git dir takes some time\n - a checkout with all notes would be insanely huge.  So somehow one\n   has to find an appropriate subset to check out.\n\n>     Possible solution: Conflict resolvers:\n\nI think you can do an entirely in-index merge with ‘git read-tree’ and\n‘git merge-index’.  If you forbid the per-file merge driver to fail\nthen this sounds like exactly what you’re talking about.\n\nIn my opinion in the case of popping up an editor this is a cruel\nthing to do, but in the other cases it’s a good place to start.\n\nHope that helps,\nJonathan\n"},{"id":"140059","messageId":"7viq7ka3zr.fsf@alter.siamese.dyndns.org","threadId":"23545","inReplyTo":"201004210957.48138.johan@herland.net","subject":"Re: 'git notes merge' implementation questions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-21T21:29:44Z","receivedAt":"2010-04-21T21:29:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> For merges between notes refs with no common history the merge should be\n> a straightforward joining of trees. This also covers the \"history-less\"\n> notes refs, like Peff's notes-cache, and should work whether the notes\n> refs point to parentless commits, or point directly to tree objects (if\n> we want to support that). For merges between notes refs with common\n> history we want to do a (more or less regular) three-way merge.\n\nNote that a \"history-less\" merge is just a special three-way merge\npretending as if their common ancestor is an empty tree.  There is no\npoint in special casing the former.\n\n> In both cases (with or without common history), conflicts may ensue,\n> and these must of course be resolved in some way. Since the notes refs\n> have no accompanying worktree, we must find some other way to resolve\n> conflicts.\n\nI would say we may not even have to \"resolve\" the conflicts in the usual\nsense of the word.\n\nYou can run \"ls-tree\" on three trees, removing '/' from the output to\nobtain the list of objects that are annotated, and do a three-way merge at\nthe object level first.  For the ones that do have diverging changes on\nboth sides, you just run \"git notes append\" to add the data from the other\nside and be done with it ;-).\n\nThat way you don't have to worry about how \"git merge\" merges things, how\nit uses the index, nor how it uses the working tree, as you won't be using\nanything from \"git merge\" at all.\n\nThat would be the first step.\n\nThe second step would be to designate a special directory that would exist\nonly during a conflicted \"notes merge\" in $GIT_DIR, just like MERGE_HEAD\nserves as the signal we are in a conflicted merge.  When\n\n    $ git notes merge <other>\n\nis run, if (and only if) you need a manual merge resolution, you would\ncreate this directory, which will have:\n\n - a temporary index that has the result of the tree level merge, but you\n   will:\n\n   (1) only register the entries that have conflicted; and \n   (2) flatten the fan-out structure.\n\n - files that have conflicted merge result, whose names are 40-byte object\n   names that are annotated; and\n\n - something like MERGE_HEAD to keep track of the <other>, so that you can\n   create a merge commit when concluding the merge.\n\nYou can chdir to the directory and use \"git diff\" and \"git ls-files -u\" to\ninspect the conflicts, and run \"git add <filename>\" to mark a resolved\nnote.\n\nYou would need a separate command (\"git notes commit\" perhaps) to conclude\nthe merge.  At that point, you would iterate over this temporary index\n(which only has conflicted notes), pulling out the list of <object name\nbeing annotated, the annotation>, add these annotates to produce a new\nnotes tree, record that tree as a merge commit in the notes namespace, and\nfinally remove the notes merge working directory.\n"},{"id":"140075","messageId":"201004220155.12747.johan@herland.net","threadId":"23545","inReplyTo":"20100421171227.GA23794@progeny.tock","subject":"Re: 'git notes merge' implementation questions","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-21T23:55:12Z","receivedAt":"2010-04-21T23:55:12Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 21 April 2010, Jonathan Nieder wrote:\n> Johan Herland wrote:\n> > 2. Merging without a worktree\n> \n> Eh, I am not a fan.  I am thinking it might be better to use something\n> like contrib/workdir to make a temporary worktree with its own index\n> and HEAD in .git/tmp-merge-notes and let the conflict resolvers work\n> there.\n> \n> Advantages:\n> \n>  - easy to debug when something goes wrong\n>  - merge driver can take other unmerged entries into account\n>  - (if merging manually) the user is not at the mercy of the program.\n>    Instead of being forced to consider the conflicts in the order git\n>    wants, she can skip some and go back to them, look at how many\n>    there are before deciding to start work, resolve some, reboot to\n>    test a new kernel, resolve some more later, and visualize the\n>    result.\n>  - if the unmerged notes are very long, you might need a temporary\n>    file anyway\n>  - maybe some day a kind of rename detection could help cope with\n>    situations like propagation of notes after a rebase\n> \n> Disadvantages:\n> \n>  - setting up a new git dir takes some time\n>  - a checkout with all notes would be insanely huge.  So somehow one\n>    has to find an appropriate subset to check out.\n> \n> >     Possible solution: Conflict resolvers:\n> I think you can do an entirely in-index merge with ‘git read-tree’ and\n> ‘git merge-index’.  If you forbid the per-file merge driver to fail\n> then this sounds like exactly what you’re talking about.\n> \n> In my opinion in the case of popping up an editor this is a cruel\n> thing to do, but in the other cases it’s a good place to start.\n\nThanks, I'm definitely coming around to the idea that having the user freely \nresolve conflicts in a temporary worktree (that preferably contains only the \nconflicting notes) is better than trying to resolve conflicts _without_ a \nworktree.\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140080","messageId":"201004220208.03706.johan@herland.net","threadId":"23545","inReplyTo":"7viq7ka3zr.fsf@alter.siamese.dyndns.org","subject":"Re: 'git notes merge' implementation questions","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-22T00:08:03Z","receivedAt":"2010-04-22T00:08:03Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 21 April 2010, Junio C Hamano wrote:\n> Johan Herland <johan@herland.net> writes:\n> > For merges between notes refs with no common history the merge should\n> > be a straightforward joining of trees. This also covers the\n> > \"history-less\" notes refs, like Peff's notes-cache, and should work\n> > whether the notes refs point to parentless commits, or point directly\n> > to tree objects (if we want to support that). For merges between notes\n> > refs with common history we want to do a (more or less regular)\n> > three-way merge.\n> \n> Note that a \"history-less\" merge is just a special three-way merge\n> pretending as if their common ancestor is an empty tree.  There is no\n> point in special casing the former.\n\nAgreed.\n\n> > In both cases (with or without common history), conflicts may ensue,\n> > and these must of course be resolved in some way. Since the notes refs\n> > have no accompanying worktree, we must find some other way to resolve\n> > conflicts.\n> \n> I would say we may not even have to \"resolve\" the conflicts in the usual\n> sense of the word.\n> \n> You can run \"ls-tree\" on three trees,\n\nThe three trees you mention are (I assume) <base>, <ours> and <theirs>. What \nif there is more than one merge-base? How do we re-use the recursive \nstrategy's \"pre-merge\" of merge-bases?\n\nNext, we will need to be somewhat careful about using \"ls-tree\", to avoid \nneedlessly unpacking subtrees that are identical between <ours> and \n<theirs>.\n\n> removing '/' from the output to\n> obtain the list of objects that are annotated, and do a three-way merge\n> at the object level first.  For the ones that do have diverging changes\n> on both sides, you just run \"git notes append\" to add the data from the\n> other side and be done with it ;-).\n\nI believe \"git notes append\" might not be suitable for all types of notes, \nand that users would in some cases want to choose other strategies for \nresolving conflicting notes. I'm currently planning to offer three fully \nautomatic resolvers: \"ours\", \"theirs\" and \"union\" (corresponding to the \n_ignore, _overwrite and _concatenate combine_notes functions, respectively, \nin notes.h).\n\n> That way you don't have to worry about how \"git merge\" merges things, how\n> it uses the index, nor how it uses the working tree, as you won't be\n> using anything from \"git merge\" at all.\n\nOk, I'm just worried that it'll force us to re-implement much of the three-\nway merge logic that's already implemented in the merge machinery.\n\n> That would be the first step.\n> \n> The second step would be to designate a special directory that would\n> exist only during a conflicted \"notes merge\" in $GIT_DIR, just like\n> MERGE_HEAD serves as the signal we are in a conflicted merge.  When\n> \n>     $ git notes merge <other>\n> \n> is run, if (and only if) you need a manual merge resolution, you would\n> create this directory, which will have:\n> \n>  - a temporary index that has the result of the tree level merge, but you\n>    will:\n> \n>    (1) only register the entries that have conflicted; and\n>    (2) flatten the fan-out structure.\n> \n>  - files that have conflicted merge result, whose names are 40-byte\n> object names that are annotated; and\n> \n>  - something like MERGE_HEAD to keep track of the <other>, so that you\n> can create a merge commit when concluding the merge.\n> \n> You can chdir to the directory and use \"git diff\" and \"git ls-files -u\"\n> to inspect the conflicts, and run \"git add <filename>\" to mark a\n> resolved note.\n> \n> You would need a separate command (\"git notes commit\" perhaps) to\n> conclude the merge.  At that point, you would iterate over this\n> temporary index (which only has conflicted notes), pulling out the list\n> of <object name being annotated, the annotation>, add these annotates to\n> produce a new notes tree, record that tree as a merge commit in the\n> notes namespace, and finally remove the notes merge working directory.\n\nI agree that this is probably a better way to resolve conflicts in notes \n(i.e. better than designing a way to semi-manually resolve conflicts without \na working tree).\n\nWe're then left with a few fully automatic conflict resolvers (\"ours\", \n\"theirs\" and \"union\") which will always succeed (and therefore need no \nspecial directory), and a \"manual\" resolver which sets up the special \ndirectory as you describe above, and instructs the user to resolve the \nmerge, followed by 'git notes commit' to conclude the merge.\n\n\nThanks for the feedback. (BTW, I'm travelling next week, so don't expect any \nimmediate patches from me).\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140081","messageId":"7v8w8g8hvt.fsf@alter.siamese.dyndns.org","threadId":"23545","inReplyTo":"201004220208.03706.johan@herland.net","subject":"Re: 'git notes merge' implementation questions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-22T00:12:38Z","receivedAt":"2010-04-22T00:12:38Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> Ok, I'm just worried that it'll force us to re-implement much of the three-\n> way merge logic that's already implemented in the merge machinery.\n\nThere is no way around it, as long as you have that variable fan-out in\nthe notes structure.  Changing and unstabilizing \"merge\" for dubious\nbenefit of code reuse is unacceptable, as the part that deals with\nvariable fan-out has no benefit to the regular \"merge\".\n"},{"id":"140083","messageId":"7vzl0w730b.fsf@alter.siamese.dyndns.org","threadId":"23545","inReplyTo":"201004220208.03706.johan@herland.net","subject":"Re: 'git notes merge' implementation questions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-22T00:19:16Z","receivedAt":"2010-04-22T00:19:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> Next, we will need to be somewhat careful about using \"ls-tree\", to avoid \n> needlessly unpacking subtrees that are identical between <ours> and \n> <theirs>.\n\nMy mentioning of \"ls-tree\" is only about what needs to be done at the\nconceptual level.  In practice, assuming that notes trees have mostly the\nsame fan-out structure, you would run \"diff-tree -r\" of (base,ours) and\n(base,theirs) pair _without_ anything fancy like rename detection, and\npick out pieces (one tree may have ab/cdx{36} while the other tree may\nhave abcd/x{36} that are notes about the same object---you treat this as\nif it is a partial ls-tree output that pertains only to the different\nparts, and make canonical \"list of annotated objects\" by removing '/'.\n\nAll of this is very specific to merging \"notes\" and normal \"merge\" does\nnot even want to know about it; I don't think you can avoid doing this\nyourself without touching \"merge\" if you want to merge \"notes\" correctly.\n"},{"id":"140084","messageId":"20100422002641.GA29452@progeny.tock","threadId":"23545","inReplyTo":"201004220155.12747.johan@herland.net","subject":"Re: 'git notes merge' implementation questions","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-04-22T00:26:41Z","receivedAt":"2010-04-22T00:26:41Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Johan Herland wrote:\n\n> Thanks, I'm definitely coming around to the idea that having the user freely \n> resolve conflicts in a temporary worktree (that preferably contains only the \n> conflicting notes) is better than trying to resolve conflicts _without_ a \n> worktree.\n\nJunio did a good job of making both interfaces --- no-resolution and\nresolution-in-a-worktree --- sound very appealing.\n\nThanks for the hard work,\nJonathan\n"},{"id":"140109","messageId":"201004221034.00639.johan@herland.net","threadId":"23545","inReplyTo":"7v8w8g8hvt.fsf@alter.siamese.dyndns.org","subject":"Re: 'git notes merge' implementation questions","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-22T08:34:00Z","receivedAt":"2010-04-22T08:34:00Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 22 April 2010, Junio C Hamano wrote:\n> Johan Herland <johan@herland.net> writes:\n> > Ok, I'm just worried that it'll force us to re-implement much of the\n> > three- way merge logic that's already implemented in the merge\n> > machinery.\n> \n> There is no way around it, as long as you have that variable fan-out in\n> the notes structure.  Changing and unstabilizing \"merge\" for dubious\n> benefit of code reuse is unacceptable, as the part that deals with\n> variable fan-out has no benefit to the regular \"merge\".\n\nUnderstood. At some point I merely contemplated whether a generic \n\"tree_filter\" callback could be added somewhere in the merge machinery, and \nthen whether flattening the fanout could be implemented as such a \n\"tree_filter\" (with an inverse \"tree_filter\" for reconstructing the fanout \nin the merge result). But it seems the costs outweigh the benefits, even \nmore so as I don't yet see any other use case for such a \"tree_filter\".\n\nIn any case, you have already given me lots of other/better options on how \nto implement 'git notes merge'.\n\n\nThanks! :)\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140110","messageId":"201004221038.25487.johan@herland.net","threadId":"23545","inReplyTo":"7vzl0w730b.fsf@alter.siamese.dyndns.org","subject":"Re: 'git notes merge' implementation questions","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-22T08:38:25Z","receivedAt":"2010-04-22T08:38:25Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 22 April 2010, Junio C Hamano wrote:\n> Johan Herland <johan@herland.net> writes:\n> > Next, we will need to be somewhat careful about using \"ls-tree\", to\n> > avoid needlessly unpacking subtrees that are identical between <ours>\n> > and <theirs>.\n> \n> My mentioning of \"ls-tree\" is only about what needs to be done at the\n> conceptual level.  In practice, assuming that notes trees have mostly the\n> same fan-out structure, you would run \"diff-tree -r\" of (base,ours) and\n> (base,theirs) pair _without_ anything fancy like rename detection, and\n> pick out pieces (one tree may have ab/cdx{36} while the other tree may\n> have abcd/x{36} that are notes about the same object---you treat this as\n> if it is a partial ls-tree output that pertains only to the different\n> parts, and make canonical \"list of annotated objects\" by removing '/'.\n\nGot it. Brilliant, and obvious, really, when I think about it...\n\n> All of this is very specific to merging \"notes\" and normal \"merge\" does\n> not even want to know about it; I don't think you can avoid doing this\n> yourself without touching \"merge\" if you want to merge \"notes\" correctly.\n\nAgreed. From your feedback, I now have a much clearer picture on how to \nproceed. Thanks! :)\n\n\nHave fun!\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"}]}