{"thread":{"id":"38000","subject":"Reachability lists in git","startedAt":"2014-11-18T19:03:44Z","lastAt":"2014-11-18T21:37:47Z","messageCount":14,"participants":["Alan Stern","Jonathan Nieder","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"252106","messageId":"Pine.LNX.4.44L0.1411181354320.4374-100000@iolanthe.rowland.org","threadId":"38000","inReplyTo":null,"subject":"Reachability lists in git","fromName":"Alan Stern","fromEmail":"stern@rowland.harvard.edu","sentAt":"2014-11-18T19:03:44Z","receivedAt":"2014-11-18T19:03:44Z","isPatch":false,"sender":{"key":"stern@rowland.harvard.edu","avatar":null},"body":"The \"git rev-list A ^B\" command lists all the commits that are\nreachable from A but not from B. Is there a comparable command for the\nconverse relation, that is, a command to list all the commits that A is\nreachable from but B isn't?\n\nAnd if there is such a command, can the output be limited to just the \nlatest commits? That is, list commit X if and only if A is reachable \nfrom X, B isn't reachable from X, and B is reachable from each of X's \nchildren?\n\nThanks,\n\nAlan Stern\n"},{"id":"252112","messageId":"20141118194129.GI6527@google.com","threadId":"38000","inReplyTo":"Pine.LNX.4.44L0.1411181354320.4374-100000@iolanthe.rowland.org","subject":"Re: Reachability lists in git","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-11-18T19:41:29Z","receivedAt":"2014-11-18T19:41:29Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nAlan Stern wrote:\n\n> The \"git rev-list A ^B\" command lists all the commits that are\n> reachable from A but not from B. Is there a comparable command for the\n> converse relation, that is, a command to list all the commits that A is\n> reachable from but B isn't?\n>\n> And if there is such a command, can the output be limited to just the\n> latest commits? That is, list commit X if and only if A is reachable\n> from X, B isn't reachable from X, and B is reachable from each of X's\n> children?\n\nSomeone else can answer your direct question, but you've got my\ncuriosity. What is the application?\n\n--ancestry-path is my current favorite tool for walking-forward needs.\n\nCurious,\nJonathan\n"},{"id":"252118","messageId":"xmqqzjbouv0y.fsf@gitster.dls.corp.google.com","threadId":"38000","inReplyTo":"20141118194129.GI6527@google.com","subject":"Re: Reachability lists in git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-11-18T20:13:33Z","receivedAt":"2014-11-18T20:13:33Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder writes:\n\n> --ancestry-path is my current favorite tool for walking-forward needs.\n\nCurious. I often want to answer this question:\n\n Commit 982ac87 was reported to be faulty. What topic was it on\n and at which point was it merged to 'master'?\n\n - What is the 'bottom' of the topic, that is, the commit\n reachable from the faulty commit that was already on 'master'\n when the faulty commit was written the first time?\n\n - What is the 'top' of the topic, that is, were there more\n commits made on top to build on the faulty commit on the\n topic before the whole thing was merged to 'master'?\n\n - Were there follow-up fixes and enhancements on the topic\n after the topic was merged to 'master' (this is harder)?\n\nAnd my experiments with --ancestry-path has been less than ideal.\n"},{"id":"252120","messageId":"20141118202250.GK6527@google.com","threadId":"38000","inReplyTo":"xmqqzjbouv0y.fsf@gitster.dls.corp.google.com","subject":"Re: Reachability lists in git","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-11-18T20:22:51Z","receivedAt":"2014-11-18T20:22:51Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Junio C Hamano wrote:\n> Jonathan Nieder writes:\n\n>> --ancestry-path is my current favorite tool for walking-forward needs.\n>\n> Curious. I often want to answer this question:\n[...]\n> And my experiments with --ancestry-path has been less than ideal.\n\nThanks for an example. I've found it works okay interactively, less\nso for scripted use (so I wish there were something better, though I\nhaven't sketched out what that something better would look like).\n\n> Commit 982ac87 was reported to be faulty. What topic was it on\n> and at which point was it merged to 'master'?\n\n $ git log --graph --ancestry-path 982ac87^..origin/master\n[...]\n * | commit f30366b27a91dbc18328bccf3067cdfad4f0cfbc\n |/ Merge: 97fefaf efa5f82\n | Author: Junio C Hamano \n | Date: Wed Apr 3 09:34:04 2013 -0700\n |\n | Merge branch 'jc/directory-attrs-regression-fix'\n |\n | Fix 1.8.1.x regression that stopped matching \"dir\" (without\n | trailing slash) to a directory \"dir\".\n |\n | * jc/directory-attrs-regression-fix:\n | t: check that a pattern without trailing slash matches a directory\n | dir.c::match_pathname(): pay attention to the length of string parameters\n | dir.c::match_pathname(): adjust patternlen when shifting pattern\n | dir.c::match_basename(): pay attention to the length of string parameters\n | attr.c::path_matches(): special case paths that end with a slash\n | attr.c::path_matches(): the basename is part of the pathname\n[...]\n |\n * commit 982ac87316a1cf5126888157bdcbfa32268ebe47\n Author: Jeff King \n Date: Thu Mar 28 17:47:47 2013 -0400\n\n dir.c::match_pathname(): adjust patternlen when shifting pattern\n\n> - What is the 'bottom' of the topic, that is, the commit\n> reachable from the faulty commit that was already on 'master'\n> when the faulty commit was written the first time?\n\n $ git tag the-merge f30366b27a91dbc18328bccf3067cdfad4f0cfbc\n $ git merge-base 982ac87 the-merge^\n 9db9eecfe5c2490d17c0d4bd5452e4cb1d0948c5\n\n> - What is the 'top' of the topic, that is, were there more\n> commits made on top to build on the faulty commit on the\n> topic before the whole thing was merged to 'master'?\n\n $ git log --oneline 982ac87..the-merge^2\n efa5f82 t: check that a pattern without trailing slash matches a directory\n ab3aebc dir.c::match_pathname(): pay attention to the length of string parameters\n\n> - Were there follow-up fixes and enhancements on the topic\n> after the topic was merged to 'master' (this is harder)?\n\nThere's only one line coming out of the-merge^2 in the ancestry-path\ngraph, so there were no such follow-up fixes.\n\nJonathan\n"},{"id":"252121","messageId":"20141118202737.GL6527@google.com","threadId":"38000","inReplyTo":"20141118202250.GK6527@google.com","subject":"Re: Reachability lists in git","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-11-18T20:27:37Z","receivedAt":"2014-11-18T20:27:37Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Nieder wrote:\n> Junio C Hamano wrote:\n\n>> - Were there follow-up fixes and enhancements on the topic\n>> after the topic was merged to 'master' (this is harder)?\n>\n> There's only one line coming out of the-merge^2 in the ancestry-path\n> graph, so there were no such follow-up fixes.\n\nOr rather, there are two lines, but the second is just a merge of the\nsame topic to maint-1.8.1.\n\nAnd here following the railroad tracks becomes tedious. gitk has a\nnicer interface for \"list children\" and \"go to child\".\n"},{"id":"252122","messageId":"Pine.LNX.4.44L0.1411181523320.879-100000@iolanthe.rowland.org","threadId":"38000","inReplyTo":"20141118194129.GI6527@google.com","subject":"Re: Reachability lists in git","fromName":"Alan Stern","fromEmail":"stern@rowland.harvard.edu","sentAt":"2014-11-18T20:29:09Z","receivedAt":"2014-11-18T20:29:09Z","isPatch":false,"sender":{"key":"stern@rowland.harvard.edu","avatar":null},"body":"On Tue, 18 Nov 2014, Jonathan Nieder wrote:\n\n> Hi,\n> \n> Alan Stern wrote:\n> \n> > The \"git rev-list A ^B\" command lists all the commits that are\n> > reachable from A but not from B. Is there a comparable command for the\n> > converse relation, that is, a command to list all the commits that A is\n> > reachable from but B isn't?\n> >\n> > And if there is such a command, can the output be limited to just the\n> > latest commits? That is, list commit X if and only if A is reachable\n> > from X, B isn't reachable from X, and B is reachable from each of X's\n> > children?\n> \n> Someone else can answer your direct question, but you've got my\n> curiosity. What is the application?\n\nTracking down regressions. Bisection isn't perfect. Suppose a\nbisection run ends up saying that B is the first bad commit. It's easy\nenough to build B and test it, to verify that it really is bad.\n\nBut to be sure that B introduced the fault, it would help to find the\nlatest commit that doesn't include B's changes -- that is, the latest\ncommit that B isn't reachable from (or the maximal elements in the set\nof all such commits). This is also important in cases where there are\nmultiple bugs and you want to investigate only the commits that don't\ninclude one of the bugs.\n\nAlan Stern\n"},{"id":"252124","messageId":"20141118203204.GM6527@google.com","threadId":"38000","inReplyTo":"Pine.LNX.4.44L0.1411181523320.879-100000@iolanthe.rowland.org","subject":"Re: Reachability lists in git","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-11-18T20:32:04Z","receivedAt":"2014-11-18T20:32:04Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Alan Stern wrote:\n\n> Tracking down regressions. Bisection isn't perfect. Suppose a\n> bisection run ends up saying that B is the first bad commit. It's easy\n> enough to build B and test it, to verify that it really is bad.\n>\n> But to be sure that B introduced the fault, it would help to find the\n> latest commit that doesn't include B's changes -- that is, the latest\n> commit that B isn't reachable from (or the maximal elements in the set\n> of all such commits).\n\nIsn't that B^ (or B^ and B^2, if B is a merge)?\n"},{"id":"252125","messageId":"xmqqmw7ouu3v.fsf@gitster.dls.corp.google.com","threadId":"38000","inReplyTo":"20141118202250.GK6527@google.com","subject":"Re: Reachability lists in git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-11-18T20:33:24Z","receivedAt":"2014-11-18T20:33:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder writes:\n\n> Junio C Hamano wrote:\n>> Jonathan Nieder writes:\n>\n>>> --ancestry-path is my current favorite tool for walking-forward needs.\n>>\n>> Curious. I often want to answer this question:\n> [...]\n>> And my experiments with --ancestry-path has been less than ideal.\n>\n> Thanks for an example. I've found it works okay interactively, less\n> so for scripted use (so I wish there were something better, though I\n> haven't sketched out what that something better would look like).\n>\n>> Commit 982ac87 was reported to be faulty. What topic was it on\n>> and at which point was it merged to 'master'?\n>\n> $ git log --graph --ancestry-path 982ac87^..origin/master\n\nYup, that is what I've been using and was wishing that there would\nbe better alternatives.\n"},{"id":"252126","messageId":"Pine.LNX.4.44L0.1411181541590.2918-100000@iolanthe.rowland.org","threadId":"38000","inReplyTo":"20141118203204.GM6527@google.com","subject":"Re: Reachability lists in git","fromName":"Alan Stern","fromEmail":"stern@rowland.harvard.edu","sentAt":"2014-11-18T20:45:43Z","receivedAt":"2014-11-18T20:45:43Z","isPatch":false,"sender":{"key":"stern@rowland.harvard.edu","avatar":null},"body":"On Tue, 18 Nov 2014, Jonathan Nieder wrote:\n\n> Alan Stern wrote:\n> \n> > Tracking down regressions. Bisection isn't perfect. Suppose a\n> > bisection run ends up saying that B is the first bad commit. It's easy\n> > enough to build B and test it, to verify that it really is bad.\n> >\n> > But to be sure that B introduced the fault, it would help to find the\n> > latest commit that doesn't include B's changes -- that is, the latest\n> > commit that B isn't reachable from (or the maximal elements in the set\n> > of all such commits).\n> \n> Isn't that B^ (or B^ and B^2, if B is a merge)?\n\nNo. Here's a simple example:\n\n Y\n /\n /\n X--B\n\nIn this diagram, X = B^. But B isn't reachable from either X or Y, \nwhereas it is reachable from one of X's children (namely Y). Therefore \nY is the unique maximal commit which B is not reachable from.\n\nAlan Stern\n"},{"id":"252130","messageId":"xmqqa93ousme.fsf@gitster.dls.corp.google.com","threadId":"38000","inReplyTo":"Pine.LNX.4.44L0.1411181541590.2918-100000@iolanthe.rowland.org","subject":"Re: Reachability lists in git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-11-18T21:05:29Z","receivedAt":"2014-11-18T21:05:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alan Stern writes:\n\n> On Tue, 18 Nov 2014, Jonathan Nieder wrote:\n>\n>> Alan Stern wrote:\n>> \n>> > Tracking down regressions. Bisection isn't perfect. Suppose a\n>> > bisection run ends up saying that B is the first bad commit. It's easy\n>> > enough to build B and test it, to verify that it really is bad.\n>> >\n>> > But to be sure that B introduced the fault, it would help to find the\n>> > latest commit that doesn't include B's changes -- that is, the latest\n>> > commit that B isn't reachable from (or the maximal elements in the set\n>> > of all such commits).\n>> \n>> Isn't that B^ (or B^ and B^2, if B is a merge)?\n>\n> No. Here's a simple example:\n>\n> Y\n> /\n> /\n> X--B\n>\n> In this diagram, X = B^. But B isn't reachable from either X or Y, \n> whereas it is reachable from one of X's children (namely Y).\n\nAround here when we draw history horizontally we place parents on\nthe left hand side and the children on the right hand side. X is\nB's parent and does not include B's changes. Y is not B's parent.\nY is a child of X so it has all the imperfection of X inherited to\nit (except the ones that is fixed by Y itself), but there is no way\nit inherited the bug B introduced relative to X.\n\nWhy do you say B is reachable from Y?\n\nIf you mean that B is a merge between X and Y, then that is already\ncovered by what Jonathan wrote \"(or B^ and B^2 if B is a merge)\".\n\n X----Y\n \\ \\\n .----B\n\nAdmittedly it is a needless merge (there should normally be one or\nmore commits between X and B on the other branch to make a merge B\nworthwhile---you could just have fast forwarded Y to B), but that\ndoes not break the reachability or bisectability in any way.\n\nConfused...\n"},{"id":"252131","messageId":"xmqq61ecusbs.fsf@gitster.dls.corp.google.com","threadId":"38000","inReplyTo":"xmqqa93ousme.fsf@gitster.dls.corp.google.com","subject":"Re: Reachability lists in git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-11-18T21:11:51Z","receivedAt":"2014-11-18T21:11:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Alan Stern writes:\n>\n>> On Tue, 18 Nov 2014, Jonathan Nieder wrote:\n>>\n>>> Alan Stern wrote:\n>>> \n>>> > Tracking down regressions. Bisection isn't perfect. Suppose a\n>>> > bisection run ends up saying that B is the first bad commit. It's easy\n>>> > enough to build B and test it, to verify that it really is bad.\n>>> >\n>>> > But to be sure that B introduced the fault, it would help to find the\n>>> > latest commit that doesn't include B's changes -- that is, the latest\n>>> > commit that B isn't reachable from (or the maximal elements in the set\n>>> > of all such commits).\n>>> \n>>> Isn't that B^ (or B^ and B^2, if B is a merge)?\n>>\n>> No. Here's a simple example:\n>>\n>> Y\n>> /\n>> /\n>> X--B\n>>\n>> In this diagram, X = B^. But B isn't reachable from either X or Y, \n>> whereas it is reachable from one of X's children (namely Y).\n> ...\n>\n> Why do you say B is reachable from Y?\n>\n> If you mean that B is a merge between X and Y, then that is already\n> covered by what Jonathan wrote \"(or B^ and B^2 if B is a merge)\".\n>\n> X----Y\n> \\ \\\n> .----B\n> ...\n\nNo, that cannot be what you meant. I was confused. The above\npicture does not make B reachable from Y (it is the other way\naround: B reaches Y). The topology where B isn't reachable from\neither X or Y and is reachable from Y would be\n\n\tX---Y\ti.e. B = Y^2, X = Y^1 = B^1 \n \\ / \n B\n\nIf B is broken, and X is not, then Y would be contaminated by the\nbreakage B introduces relative to X, unless Y is an evil merge and\nfixed that breakage while merging.\n\nIn any case, even if Y is found to be broken, its parent B is\nalready broken, so that does not place the blame on Y, does it?\n\nStill confused why you feel Y is any significant...\n"},{"id":"252134","messageId":"Pine.LNX.4.44L0.1411181610070.2918-100000@iolanthe.rowland.org","threadId":"38000","inReplyTo":"xmqqa93ousme.fsf@gitster.dls.corp.google.com","subject":"Re: Reachability lists in git","fromName":"Alan Stern","fromEmail":"stern@rowland.harvard.edu","sentAt":"2014-11-18T21:16:57Z","receivedAt":"2014-11-18T21:16:57Z","isPatch":false,"sender":{"key":"stern@rowland.harvard.edu","avatar":null},"body":"On Tue, 18 Nov 2014, Junio C Hamano wrote:\n\n> Alan Stern writes:\n> \n> > On Tue, 18 Nov 2014, Jonathan Nieder wrote:\n> >\n> >> Alan Stern wrote:\n> >> \n> >> > Tracking down regressions. Bisection isn't perfect. Suppose a\n> >> > bisection run ends up saying that B is the first bad commit. It's easy\n> >> > enough to build B and test it, to verify that it really is bad.\n> >> >\n> >> > But to be sure that B introduced the fault, it would help to find the\n> >> > latest commit that doesn't include B's changes -- that is, the latest\n> >> > commit that B isn't reachable from (or the maximal elements in the set\n> >> > of all such commits).\n> >> \n> >> Isn't that B^ (or B^ and B^2, if B is a merge)?\n> >\n> > No. Here's a simple example:\n> >\n> > Y\n> > /\n> > /\n> > X--B\n> >\n> > In this diagram, X = B^. But B isn't reachable from either X or Y, \n> > whereas it is reachable from one of X's children (namely Y).\n> \n> Around here when we draw history horizontally we place parents on\n> the left hand side and the children on the right hand side. X is\n> B's parent and does not include B's changes. Y is not B's parent.\n> Y is a child of X so it has all the imperfection of X inherited to\n> it (except the ones that is fixed by Y itself), but there is no way\n> it inherited the bug B introduced relative to X.\n> \n> Why do you say B is reachable from Y?\n\nI omitted a negation by mistake, sorry. I meant to say: \"But B isn't\nreachable from either X or Y, and it isn't reachable from one of X's\nchildren (namely Y).\"\n\nThus, if B introduced a bug, that bug would not be present in Y. But Y \nmight be better for testing than X, because Y might fix some other \nproblems that are present in X.\n\nAlan Stern\n"},{"id":"252135","messageId":"xmqq1tp0uru5.fsf@gitster.dls.corp.google.com","threadId":"38000","inReplyTo":"Pine.LNX.4.44L0.1411181610070.2918-100000@iolanthe.rowland.org","subject":"Re: Reachability lists in git","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-11-18T21:22:26Z","receivedAt":"2014-11-18T21:22:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alan Stern writes:\n\n>> > No. Here's a simple example:\n>> >\n>> > Y\n>> > /\n>> > /\n>> > X--B\n>> >\n>> > In this diagram, X = B^. But B isn't reachable from either X or Y, \n>> > whereas it is reachable from one of X's children (namely Y).\n> ...\n> Thus, if B introduced a bug, that bug would not be present in Y. But Y \n> might be better for testing than X, because Y might fix some other \n> problems that are present in X.\n\nThe problem with that line of reasoning is that in real life there\nwill be unbound number of Y's that forked from a point before\nsomebody wrote B. Which one among these Y's would you pick and why?\n\nIf Y has fixed another problem that is present in X and make it\neasier to test, Z, a direct descendant of Y (i.e. Z^1 = Y), may have\nfixed yet another problem that is unrelated to the problem B\nintroduced and it may make the result even easier to test. Where do\nyou stop?\n\nStill confused...\n"},{"id":"252138","messageId":"Pine.LNX.4.44L0.1411181634080.2918-100000@iolanthe.rowland.org","threadId":"38000","inReplyTo":"xmqq1tp0uru5.fsf@gitster.dls.corp.google.com","subject":"Re: Reachability lists in git","fromName":"Alan Stern","fromEmail":"stern@rowland.harvard.edu","sentAt":"2014-11-18T21:37:47Z","receivedAt":"2014-11-18T21:37:47Z","isPatch":false,"sender":{"key":"stern@rowland.harvard.edu","avatar":null},"body":"On Tue, 18 Nov 2014, Junio C Hamano wrote:\n\n> Alan Stern writes:\n> \n> >> > No. Here's a simple example:\n> >> >\n> >> > Y\n> >> > /\n> >> > /\n> >> > X--B\n> >> >\n> >> > In this diagram, X = B^. But B isn't reachable from either X or Y, \n> >> > whereas it is reachable from one of X's children (namely Y).\n> > ...\n> > Thus, if B introduced a bug, that bug would not be present in Y. But Y \n> > might be better for testing than X, because Y might fix some other \n> > problems that are present in X.\n> \n> The problem with that line of reasoning is that in real life there\n> will be unbound number of Y's that forked from a point before\n> somebody wrote B. Which one among these Y's would you pick and why?\n\nI don't know. But I would like to see what is available. I might even \nmerge all those commits and test that (if there aren't any bad \nconflicts).\n\n> If Y has fixed another problem that is present in X and make it\n> easier to test, Z, a direct descendant of Y (i.e. Z^1 = Y), may have\n> fixed yet another problem that is unrelated to the problem B\n> introduced and it may make the result even easier to test. Where do\n> you stop?\n\nIf Y is maximal among the comments that B isn't reachable from and Z^ = \nY then, by definition, B _is_ reachable from Z. Therefore the bug \nintroduced in B will be present in Z, unless it got fixed somewhere in \nbetween. Either way, Z is not a good candidate for testing whereas Y \nis.\n\nAlan Stern\n"}]}