{"thread":{"id":"33905","subject":"Bug when git rev-list options \"--first-parent\" and \"--ancestry-path\" are used together?","startedAt":"2013-05-23T10:07:04Z","lastAt":"2013-05-25T19:54:30Z","messageCount":4,"participants":["Michael Haggerty","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"218246","messageId":"519DEA48.10108@alum.mit.edu","threadId":"33905","inReplyTo":null,"subject":"Bug when git rev-list options \"--first-parent\" and \"--ancestry-path\" are used together?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T10:07:04Z","receivedAt":"2013-05-23T10:07:04Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It seems to me that\n\n     git rev-list --first-parent --ancestry-path A..B\n\nis well-defined and should list the commits in the intersection between\n\n     git rev-list --first-parent                 A..B\n\nand\n\n     git rev-list                --ancestry-path A..B\n\nBut in many cases the first command doesn't provide any output even\nthough there are commits common to the output of the last two commands.\n\nFor example, take as an example the DAG from test t6019:\n\n#          D---E-------F\n#         /     \\       \\\n#    B---C---G---H---I---J\n#   /                     \\\n#  A-------K---------------L--M\n\n(The merges are always downwards; e.g., the first parent of commit L is\nK.)  The command\n\n    git rev-list --first-parent --ancestry-path D..J\n\ndoesn't generate any output, whereas I would expect it to output \"H I\nJ\".  Similarly,\n\n    git rev-list --first-parent --ancestry-path D..M\n\ndoesn't generate any output, whereas I would expect it to output \"L M\".\n\nFor fun, the attached script computes the output for all commit pairs in\nthis DAG and outputs the discrepancies that it finds.  (It should be run\nin directory \"t/trash directory.t6019-rev-list-ancestry-path\" after\nt6019 was run with \"-d\".)\n\nIs this a bug or are my expectations wrong?\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218286","messageId":"7vtxltfwaa.fsf@alter.siamese.dyndns.org","threadId":"33905","inReplyTo":"519DEA48.10108@alum.mit.edu","subject":"Re: Bug when git rev-list options \"--first-parent\" and \"--ancestry-path\" are used together?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-23T17:20:13Z","receivedAt":"2013-05-23T17:20:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> It seems to me that\n>\n>      git rev-list --first-parent --ancestry-path A..B\n>\n> is well-defined and should list the commits in the intersection between\n>\n>      git rev-list --first-parent                 A..B\n>\n> and\n>\n>      git rev-list                --ancestry-path A..B\n>\n> But in many cases the first command doesn't provide any output even\n> though there are commits common to the output of the last two commands.\n>\n> For example, take as an example the DAG from test t6019:\n>\n> #          D---E-------F\n> #         /     \\       \\\n> #    B---C---G---H---I---J\n> #   /                     \\\n> #  A-------K---------------L--M\n>\n> (The merges are always downwards; e.g., the first parent of commit L is\n> K.)  The command\n>\n>     git rev-list --first-parent --ancestry-path D..J\n>\n> doesn't generate any output, whereas I would expect it to output \"H I\n> J\".\n\nAs I do not see how \"only show first-parent chains from near the tip\nbut stop immediately when the chain deviates from the ancestry path\"\ncould be a sensible operation (in other words, I do not offhand\nthink of examples of what useful things you can do with that\ninformation), I actually expect that \"-f-p -a-p D..J\" should error\nout, instead of giving no output.\n\nYou are correct to point out that sometimes -f-p and -a-p _could_ be\ncompatible, e.g. \"-f-p -a-p A..M\", or \"-f-p -a-p B..M\".  But I think\nthe only case that they are compatible is when \"-f-p\" output is a\nstrict subset of what \"-a-p\" without \"-f-p\" would give.\n"},{"id":"218543","messageId":"51A105B3.9020304@alum.mit.edu","threadId":"33905","inReplyTo":"7vtxltfwaa.fsf@alter.siamese.dyndns.org","subject":"Re: Bug when git rev-list options \"--first-parent\" and \"--ancestry-path\" are used together?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-25T18:40:51Z","receivedAt":"2013-05-25T18:40:51Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"[Junio, sorry for the dup; somehow I failed to CC the first version to\nthe mailing list.]\n\nOn 05/23/2013 07:20 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> It seems to me that\n>>\n>>      git rev-list --first-parent --ancestry-path A..B\n>>\n>> is well-defined and should list the commits in the intersection between\n>>\n>>      git rev-list --first-parent                 A..B\n>>\n>> and\n>>\n>>      git rev-list                --ancestry-path A..B\n>>\n>> But in many cases the first command doesn't provide any output even\n>> though there are commits common to the output of the last two commands.\n>>\n>> For example, take as an example the DAG from test t6019:\n>>\n>> #          D---E-------F\n>> #         /     \\       \\\n>> #    B---C---G---H---I---J\n>> #   /                     \\\n>> #  A-------K---------------L--M\n>>\n>> (The merges are always downwards; e.g., the first parent of commit L is\n>> K.)  The command\n>>\n>>     git rev-list --first-parent --ancestry-path D..J\n>>\n>> doesn't generate any output, whereas I would expect it to output \"H I\n>> J\".\n> \n> As I do not see how \"only show first-parent chains from near the tip\n> but stop immediately when the chain deviates from the ancestry path\"\n> could be a sensible operation (in other words, I do not offhand\n> think of examples of what useful things you can do with that\n> information), I actually expect that \"-f-p -a-p D..J\" should error\n> out, instead of giving no output.\n> \n> You are correct to point out that sometimes -f-p and -a-p _could_ be\n> compatible, e.g. \"-f-p -a-p A..M\", or \"-f-p -a-p B..M\".  But I think\n> the only case that they are compatible is when \"-f-p\" output is a\n> strict subset of what \"-a-p\" without \"-f-p\" would give.\n\nI guess I should tell you the application that motivated the use of\nthese options together.  Maybe you can suggest a better approach.\n\nI'm trying to find the most general conditions where an incremental\nmerge [1,2] makes sense.  The simple case is merging two linear\nbranches, call them \"branch\" and \"master\":\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\\n      A - B - C - D      ← branch\n\nMy tool git-imerge does this (conceptually) by constructing the pairwise\nmerges between each commit on master and each commit on branch:\n\no - 0 - 1  - 2  - 3  - 4   ← master\n    |   |    |    |    |\n    A - A1 - A2 - A3 - A4\n    |   |    |    |    |\n    B - B1 - B2 - B3 - B4\n    |   |    |    |    |\n    C - C1 - C2 - C3 - C4\n    |   |    |    |    |\n    D - D1 - D2 - D3 - D4  ← final merge\n    ↑\n  branch\n\nEach of the new items [ABCD][1234] is a merge commit between its\nneighbor above and its neighbor to the left.  The idea is that the\npairwise merges are less likely to conflict, and if they conflict are\nlikely to be easy to reconcile.\n\nI am trying to generalize this approach to a more complicated situation\nwhere the two branches are not linear.\n\nThe current incremental merge algorithm requires that each commit\n0,1,2,3,4 and 0,A,B,C be a direct descendant of its predecessors.\nThat's trivial for linear branches.  But if the situation looks like this:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\\n      A - B - C - D      ← branch\n           \\     /\n            X - Y\n\nthen there is no correct ordering of 0,A,B,C,D,X,Y that has the\ndescendancy property.  So currently I always take use the first-parent\nlist of commits on each branch (i.e., omitting X and Y), which does have\nthat property.\n\nNow assume a slightly more complicated situation, in which master has\nbeen merged to feature branch at some point:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\\n      A - B - C - D      ← branch\n           \\     /\n            X - Y\n\nNow when we do an incremental merge branch into master, how do we\ngenerate the list of commits to put one each axis of the table?  The\nmerge base is \"2\", so I think the best answer is\n\n1- 2 - 3  - 4   ← master\n   |   |    |\n   C - C3 - C4\n   |   |    |\n   D - D3 - D4  ← final merge\n   ↑\n branch\n\nThe simplest way I can think of to generate the list C,D is\n\n    git rev-list --first-parent --ancestry-path 2..D\n\nWe need --ancestry-path to avoid getting commits A and B.  It's still\nnot clear that this is always the best approach but at least it seems\nsafe.  For example, suppose that the first parent of D is Y rather than C:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\\n      A - B - C --.\n           \\       \\\n            X - Y - D    ← branch\n\nIn this case, the above command (it it worked correctly) would just\noutput \"D\".  This is correct and could be used for a (degenerate, in\nthis case) incremental merge [3].\n\nThis is my reason for wanting --first-parent and --ancestry-path to work\ntogether.\n\nFor now I'm just running rev-list twice and computing the intersection\nby hand, but it was surprising that git could not do this for me.\n\nMichael\n\n[1] https://github.com/mhagger/git-imerge\n[2]\nhttp://softwareswirl.blogspot.com/2013/05/git-imerge-practical-introduction.html\n(and references therein)\n[3] It might be more helpful to use C,D in this case rather than just D,\nbut I haven't yet figured out whether this is just a special case or\nwhether it hints at an algorithm that is more clever than\n\"--first-parent --ancestry-path\".\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218545","messageId":"51A116F6.7080907@alum.mit.edu","threadId":"33905","inReplyTo":"7v4nds9rhh.fsf@alter.siamese.dyndns.org","subject":"Re: Bug when git rev-list options \"--first-parent\" and \"--ancestry-path\" are used together?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-25T19:54:30Z","receivedAt":"2013-05-25T19:54:30Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/24/2013 08:12 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> Now assume a slightly more complicated situation, in which master has\n>> been merged to feature branch at some point:\n>>\n>> o - 0 - 1 - 2 - 3 - 4    ← master\n>>      \\       \\\n>>       A - B - C - D      ← branch\n>>            \\     /\n>>             X - Y\n>>\n>> Now when we do an incremental merge branch into master, how do we\n>> generate the list of commits to put one each axis of the table?  The\n>> merge base is \"2\", so I think the best answer is\n>>\n>> 1- 2 - 3  - 4   ← master\n>>    |   |    |\n>>    C - C3 - C4\n>>    |   |    |\n>>    D - D3 - D4  ← final merge\n>>    ↑\n>>  branch\n> \n> I am not sure if that is the best answer, though.\n> \n> After managing to create Cn, if a change between C and D (which come\n> from X and Y) is too complex, wouldn't you want to break down the\n> task to come up with Dn recursively into a smaller subtask of\n> merging X first and then Y on top and finally D?\n\nOK, so let's assume that C3 is done and D3 is giving us problems:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\   \\\n      \\       \\   C3- ?\n       \\       \\ /   /\n        A - B - C - D      ← branch\n             \\     /\n              X - Y\n\nYour proposal is not to merge D directly but rather to merge X then Y.\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\   \\\n      \\       \\   C3 --- X3 - Y3 - D3\n       \\       \\ /      /    /    /\n        A - B - C - D- / -- / ---'   ← the lines here...\n             \\     /  /    /\n              X - Y- / ---'          ← ...and here don't intersect\n               \\    /\n                `--'\n\nThe problem is that the merges that would be required are not able to\ntake advantage of the conflict resolution that was done in D:\n\nThe merge base for X3 would be B.  This is a little bit wrong because X3\nincludes C among its ancestors, so creating X3 requires some of the\nconflicts between X and C (which were resolved once in D) to be resolved\nagain.\n\nThe merge base for Y3 would be X.  Note that Y3 already includes C and Y\namong its ancestors.  Therefore, resolving Y3 involves resolving the\nsame conflicts between Y and C that were already resolved in D.  But\nsince merge Y3 doesn't know about D, the user would be forced to resolve\nthose conflicts again (albeit maybe helped by something like rerere).\n\nAnd merge D3 would have two merge bases, C and Y.  This is related to\nthe fact that there are now two independent known resolutions for\nmerging C and Y, namely D and Y3.\n\nGiven that Y3 in the above scenario needs to include include C (via C3)\nand also Y, it seems to me that this merge is superfluous.  It should\nhave exactly the same content as D3, assuming that the conflicts are\nresolved the same way.  Therefore one could skip Y3 and proceed directly\nto D3:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\   \\\n      \\       \\   C3 --- X3 - D3\n       \\       \\ /      /    /\n        A - B - C - D- / ---'        ← the lines here...\n             \\     /  /\n              X - Y  /               ← ...and here don't intersect\n               \\    /\n                `--'\n\nThis merge could take advantage of the conflict resolution that was done\nin D.  It would have an unambiguous merge base, C.\n\nBut I still think that this approach is not as clean as an incremental\nmerge of two linear branches, because X3 requires some of the same\nconflicts to be resolved as were already resolved in D.\n\nIncidentally, if merge D had been done incrementally and the full\nincremental merge resolution had been kept, then we would have the\nmissing merge CX that would allow us to compute D3 incrementally:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n    |       |   |\n    A - B - C - C3\n        |   |   |\n        X - CX- C3X\n        |   |   |\n        Y - D - D3\n\nI think that all of the required merges have sane merge-bases and take\nadvantage of all of the merges that have been done previously.  This is\nanother case where an incremental merges contains information that can\nbe useful for the future.\n\n>> The simplest way I can think of to generate the list C,D is\n>>\n>>     git rev-list --first-parent --ancestry-path 2..D\n>>\n>> We need --ancestry-path to avoid getting commits A and B.  It's still\n>> not clear that this is always the best approach but at least it seems\n>> safe.\n> \n> Hmm, while I agree that A and B will be omitted by using ancestry\n> path on the example topology, I need to be convinced that it is\n> impossible to end up with disjoint segments of a history in any\n> ancestry graph by combining -f-p and -a-p that way to feel \"safe\".\n\nIf by \"disjoint\" you mean that the history contains gaps, that is\nexactly what happens in the case I described in my last email:\n\no - 0 - 1 - 2 - 3 - 4    ← master\n     \\       \\\n      A - B - C --.\n           \\       \\\n            X - Y - D    ← branch\n\nThe result of \"git rev-list --first-parent --ancestry-path 2..D\" would\nbe only D and commit C would disappear into the \"gap\".\n\nI am willing to accept that for my application, because the incremental\nmerge algorithm can work despite gaps in the history but it cannot work\nif the ancestry property is not met.\n\n>> This is my reason for wanting --first-parent and --ancestry-path to work\n>> together.\n>>\n>> For now I'm just running rev-list twice and computing the intersection\n>> by hand, but it was surprising that git could not do this for me.\n> \n> Wouldn't you be able to read everything you need out of a single\n> \n> \tgit rev-list --left-right --parents master...branch\n> \n> output?\n> \n> By the way, there is a fairly major fixes to the revision traversal\n> machinery that has been parked on pu, which leads to 141efdba57b1\n> (revision.c: make default history consider bottom commits,\n> 2013-05-16).  The topic revises the semantics of ancestry-path to\n> bring more sanity to it.\n> \n> I haven't had time to see how it changes the situation for the use\n> case you described in the message I am responding to, but I think it\n> is worth checking to see how well it meshes with your expectation,\n> and if it doesn't involve Kevin in the design discussion.\n\nI'll look into all of these suggestions; thanks.  I'm also CCing Kevin\non this email.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"}]}