{"thread":{"id":"43939","subject":"Are --first-parent and --ancestry-path compatible rev-list options?","startedAt":"2016-08-26T21:23:54Z","lastAt":"2016-09-01T22:21:05Z","messageCount":6,"participants":["Philip Oakley","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"300307","messageId":"2FA1998250474E76A386B82AD635E56A@PhilipOakley","threadId":"43939","inReplyTo":null,"subject":"Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2016-08-26T21:23:46Z","receivedAt":"2016-08-26T21:23:54Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"While trying to answer a Stack Overflow question I thought I could \ncontribute to, I've found a scenario that I don't understand that may be a \nbug.\n\nIn http://stackoverflow.com/questions/39144006/identify-merge-into-master \nMvG asked how to find the point at which a commit on a feature branch was \nlater merged into the main-line.\n\nAfter some discussion it appeared that\n    `git log --oneline  --first-parent --merges --reverse  --ancestry-path \n:/j..  | head -1`\nshould find the point that 'j' was merged into master (when on master), \nhowever it appears that --first-parent and --ancestry-path interact badly to \nproduce no output in the example, but if either is dropped, the expected \ncommit is shown.\n\nWhat am I missing?\n--\nPhilip\n\n\nThe commit graph. We are looking for F based on knowing J.\n\n. A - B - C - D -- E -- F -- G - H    <-first parent, --merges (C,F,H)\n.  \\  |  /    \\        /    /\n.   ----Z     |       /    /\n.     |       |       |   /\n.      \\       \\     /   /\n.       I -[J]- K - L - M             <-since J, children of J\n.        \\         /\n.         N - O - P\n\n# Steps to reproduce the extended example from\n# http://stackoverflow.com/q/39144006/1468366\n\ngit init .\necho a > txt\ngit add txt\ngit commit -m a\necho a > txt; git commit -a -m a\necho b > txt; git commit -a -m b\ngit checkout -b side :/a\necho z > txt; git commit -a -m z\ngit checkout master\ngit merge :/z; echo c > txt; git add -u; git commit -m c\n\n#echo c > txt; git commit -a -m c\necho d > txt; git commit -a -m d\necho e > txt; git commit -a -m e\ngit checkout -b 2nd :/b\necho i > txt; git commit -a -m i\necho j > txt; git commit -a -m j\ngit merge :/d; echo k > txt; git add -u; git commit -m k\ngit checkout -b 3rd :/i\necho n > txt; git commit -a -m n\necho o > txt; git commit -a -m o\necho p > txt; git commit -a -m p\ngit checkout 2nd\ngit merge :/p; echo l > txt; git add -u; git commit -m l\necho m > txt; git commit -a -m m\ngit checkout master\ngit merge :/l; echo f > txt; git add -u; git commit -m f\ngit merge :/m; echo g > txt; git add -u; git commit -m g\necho h > txt; git commit -a -m h\n\ngit log --oneline  --first-parent --merges --reverse  --ancestry-path :/j.. \n| head -5\n\n# why does this not work --ancestry-path and --first-parent appear to clash.\n\ncode available as \nhttps://gist.github.com/PhilipOakley/58f344f910e50b72f5a8a2bd55b6c175\n\n"},{"id":"300315","messageId":"xmqqfuprdtwh.fsf@gitster.mtv.corp.google.com","threadId":"43939","inReplyTo":"2FA1998250474E76A386B82AD635E56A@PhilipOakley","subject":"Re: Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-26T22:53:18Z","receivedAt":"2016-08-26T22:53:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" <philipoakley@iee.org> writes:\n\n> The commit graph. We are looking for F based on knowing J.\n>\n> . A - B - C - D -- E -- F -- G - H    <-first parent, --merges (C,F,H)\n> .  \\  |  /    \\        /    /\n> .   ----Z     |       /    /\n> .     |       |       |   /\n> .      \\       \\     /   /\n> .       I -[J]- K - L - M             <-since J, children of J\n> .        \\         /\n> .         N - O - P\n\nI think these two operations are fundamentally incompatible.\n\nBecause the first-parent traversal is what the name says, i.e.,\nforbids the positive side of revision traversal to stray into side\nbranches, the positive side of a traversal that begins at H will not\nsee M, L and K.  The negative side would traverse in the normal way\nto paint commits starting J and its ancestors as UNINTERESTING, so\nthe traversal over the artificial \"first-parent only\" history, i.e.\nH, G, F, E, D, C, B, A would eventually stop before showing an\nancestor of J.\n\nOn the other hand, to compute the ancestry-path, you need to make a\nfull traversal of the real history to find a subgraph J..H and then\npost-process it to cull paths that do not contain J.\n"},{"id":"300333","messageId":"CD6AE25418644EB688D4488F8AB40155@PhilipOakley","threadId":"43939","inReplyTo":"xmqqfuprdtwh.fsf@gitster.mtv.corp.google.com","subject":"Re: Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2016-08-27T11:04:08Z","receivedAt":"2016-08-27T11:06:41Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Junio C Hamano\" <gitster@pobox.com>\n> \"Philip Oakley\" <philipoakley@iee.org> writes:\n>\n>> The commit graph. We are looking for F based on knowing J.\n>>\n>> . A - B - C - D -- E -- F -- G - H    <-first parent, --merges (C,F,H)\n>> .  \\  |  /    \\        /    /\n>> .   ----Z     |       /    /\n>> .     |       |       |   /\n>> .      \\       \\     /   /\n>> .       I -[J]- K - L - M             <-since J, children of J\n>> .        \\         /\n>> .         N - O - P\n>\n> I think these two operations are fundamentally incompatible.\n\nIf I run them independently, they both find the desired INTERESTED commit, \nhence the expectation that together they will still find that commit as an \nintersection between the two sets.\n\n>\n> Because the first-parent traversal is what the name says, i.e.,\n> forbids the positive side of revision traversal to stray into side\n> branches, the positive side of a traversal that begins at H will not\n> see M, L and K.\n\nBut it does see F the ultimately desired commit.\nPhilip@PhilipOakley MINGW32 /usr/src/test (master)\n\n$ git log --oneline --first-parent --merges :/j..\n\nd089efa g\n\nac811d4 f\n\n1db59e5 c\n\nThen we have:\n--ancestry-path\n    Limit the displayed commits to those directly on the ancestry chain \nbetween the \"from\" and \"to\" commits in the given commit range.\n\nSo one would expect, from a user viewepoint that this is commit selection, \nnot internal algorithm implementation, that it would only list G and F, and \nthe C would not be displayed.\n\n>  The negative side would traverse in the normal way\n> to paint commits starting J and its ancestors as UNINTERESTING, so\n> the traversal over the artificial \"first-parent only\" history, i.e.\n> H, G, F, E, D, C, B, A would eventually stop before showing an\n> ancestor of J.\n>\n\n> On the other hand, to compute the ancestry-path, you need to make a\n> full traversal of the real history to find a subgraph J..H and then\n> post-process it to cull paths that do not contain J.\n\nThe culling order isn't clear. It's easy to expect that --first parent is a \ncull.\nThe documentation implies (to me) this different computation.\n\n\nThis explains why its happening, but it does feel rather contrary to user \n(rather than developer) expectation. It's the confusion between traversal \nlimiting and marking a commit as Interesting (i.e. UNINTERSTING has two \nmeanings which may not align when multiple options are given.)\n\nIt does seem odd that in the Git world, with its feature branch approach, \nthat this hasn't come up before. I know that I haven't even bothered to try \nthis 'search', and just use gitk to manually follow the breadcrumbs.\n\nPerhaps a `--first-parent-ancestor` option to determine the places where a \ncommit from a feature series was merged in to the mainline would be rather \nhelpful.\n> --\nPhilip \n\n"},{"id":"300822","messageId":"1BC836ACA8C741AD9732122B3B198752@PhilipOakley","threadId":"43939","inReplyTo":"xmqq8tvby19a.fsf@gitster.mtv.corp.google.com","subject":"Re: Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2016-09-01T20:48:14Z","receivedAt":"2016-09-01T20:56:29Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Junio,\n\nFrom: \"Junio C Hamano\" <gitster@pobox.com>\n> \"Philip Oakley\" <philipoakley@iee.org> writes:\n>\n>> From: \"Junio C Hamano\" <gitster@pobox.com>\n>>> \"Philip Oakley\" <philipoakley@iee.org> writes:\n>>>\n>>>> The commit graph. We are looking for F based on knowing J.\n>>>>\n>>>> . A - B - C - D -- E -- F -- G - H    <-first parent, --merges (C,F,H)\n>>>> .  \\  |  /    \\        /    /\n>>>> .   ----Z     |       /    /\n>>>> .     |       |       |   /\n>>>> .      \\       \\     /   /\n>>>> .       I -[J]- K - L - M             <-since J, children of J\n>>>> .        \\         /\n>>>> .         N - O - P\n>>>\n>>> I think these two operations are fundamentally incompatible.\n>>\n>> If I run them independently, they both find the desired INTERESTED\n>> commit, hence the expectation that together they will still find that\n>> commit as an intersection between the two sets.\n>>\n>>>\n>>> Because the first-parent traversal is what the name says, i.e.,\n>>> forbids the positive side of revision traversal to stray into side\n>>> branches, the positive side of a traversal that begins at H will not\n>>> see M, L and K.\n>>\n>> But it does see F the ultimately desired commit.\n>\n> You are doing --merges --first-parent, right?  Traversing only the\n> first-parent chain on the positive side, while excluding J's\n> ancestor by traversing the negative side without being limited to\n> the first-parent chain, would paint B and its ancestors as\n> uninteresting on the first-parent chain, so among H, G, F, E, D and\n> C, which are the survivors on the first-parent chain that are still\n> not UNINTERESTIN, the last one you would find that is a merge is F.\n>\n> So I do not see any room for \"But\" to come in here...\n>\n\nThe confusion is between the \"As required\" and \"as coded\" viewpoints (this \nis regular dayjob problem of allegedly having 'requirement specifications').\n\nYou have rightly described the algorithm as currently implemented, while I \nwas was trying to state a requirement (based on a user question).\n\nThe user question was, given a commit 'J', and a future commit 'H' \n(typically a branch tip such as 'master'), find those commits that are :\nA) merges\nB) on the first parent DAG chain of the future commit 'H'\nC) children of the given commit 'J'\n\ni.e. the points on master where the feature J (and it's children) could have \nbrought in some effect to master.\n\nEach of the three conditions match one of the revision list options, but the \nimplemented logic does not produce the AND effect that could be expected. \nEssentially it (the user's desire vs the coding implementation) is a case \nwhere (depending on the viewpoint) we get the 'denying the antecedent' \nfallacy.\n\nJust because a commit is not --first-parent does not mean that revison \nwalking (in this case) should stop. The user is interested in the ancestry \npath, so from that perspective the the walk should carry on through the \nother parents till its reaches the TRULY_DISINTERESTED line, or reaches J.\n\n\nWith the current implementation one appears to need to script a search \nthrough all the first parent merges and then prune out those that aren't \nmerge-base is-ancestor commits, which is what the OP ended up having to do.\n\n\nI haven't had any time to look into the rev-walk code itself, but is this \nsomething that could be coded (new option) or is the double-duty problem \nwith UNINTERESTING too hard baked into the code?\n--\nPhilip\n\n"},{"id":"300835","messageId":"xmqq8tvby19a.fsf@gitster.mtv.corp.google.com","threadId":"43939","inReplyTo":"CD6AE25418644EB688D4488F8AB40155@PhilipOakley","subject":"Re: Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-01T17:32:17Z","receivedAt":"2016-09-01T21:12:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" <philipoakley@iee.org> writes:\n\n> From: \"Junio C Hamano\" <gitster@pobox.com>\n>> \"Philip Oakley\" <philipoakley@iee.org> writes:\n>>\n>>> The commit graph. We are looking for F based on knowing J.\n>>>\n>>> . A - B - C - D -- E -- F -- G - H    <-first parent, --merges (C,F,H)\n>>> .  \\  |  /    \\        /    /\n>>> .   ----Z     |       /    /\n>>> .     |       |       |   /\n>>> .      \\       \\     /   /\n>>> .       I -[J]- K - L - M             <-since J, children of J\n>>> .        \\         /\n>>> .         N - O - P\n>>\n>> I think these two operations are fundamentally incompatible.\n>\n> If I run them independently, they both find the desired INTERESTED\n> commit, hence the expectation that together they will still find that\n> commit as an intersection between the two sets.\n>\n>>\n>> Because the first-parent traversal is what the name says, i.e.,\n>> forbids the positive side of revision traversal to stray into side\n>> branches, the positive side of a traversal that begins at H will not\n>> see M, L and K.\n>\n> But it does see F the ultimately desired commit.\n\nYou are doing --merges --first-parent, right?  Traversing only the\nfirst-parent chain on the positive side, while excluding J's\nancestor by traversing the negative side without being limited to\nthe first-parent chain, would paint B and its ancestors as\nuninteresting on the first-parent chain, so among H, G, F, E, D and\nC, which are the survivors on the first-parent chain that are still\nnot UNINTERESTIN, the last one you would find that is a merge is F.\n\nSo I do not see any room for \"But\" to come in here...\n"},{"id":"300848","messageId":"xmqqd1knuura.fsf@gitster.mtv.corp.google.com","threadId":"43939","inReplyTo":"1BC836ACA8C741AD9732122B3B198752@PhilipOakley","subject":"Re: Are --first-parent and --ancestry-path compatible rev-list options?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-01T22:20:57Z","receivedAt":"2016-09-01T22:21:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" <philipoakley@iee.org> writes:\n\n> The user question was, given a commit 'J', and a future commit 'H'\n> (typically a branch tip such as 'master'), find those commits that are\n> :\n> A) merges\n> B) on the first parent DAG chain of the future commit 'H'\n> C) children of the given commit 'J'\n\nThe answer then is that there is no such single step operation.\n\nIn the picture, if D or E were a merge from a side branch that does\nnot have anything to do with 'J', \"log --first-parent --merges\" will\nnot exclude it (i.e. C won't be fulfilled by --first-parent --merges).\n\n"}]}