{"thread":{"id":"15064","subject":"Best method of detecting if list of commit refs is a parent","startedAt":"2008-08-18T02:24:20Z","lastAt":"2008-08-23T02:24:44Z","messageCount":4,"participants":["Thomas Harning Jr.","Junio C Hamano","Thomas Harning"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"87509","messageId":"e47324780808171924j237688faj9e13740f89e75fdf@mail.gmail.com","threadId":"15064","inReplyTo":null,"subject":"Best method of detecting if list of commit refs is a parent","fromName":"Thomas Harning Jr.","fromEmail":"harningt@gmail.com","sentAt":"2008-08-18T02:24:20Z","receivedAt":"2008-08-18T02:24:20Z","isPatch":false,"sender":{"key":"harningt@gmail.com","avatar":"https://gravatar.com/avatar/a79ddd43da8c8f1f899cd75b7b95cc5f3b2ba5643400468988b1a12c86b75d08?d=mp&s=160"},"body":"I'm working on my 'Stick' git bug-tracking tool and am working on the\nfunctionality to get a list of relevant bug-items at a specific point\nin history.\n\nBefore I get into figuring out the 'best' way to do this, I thought\nI'd at least get the simple single-item case of detecting if a\nspecific commit can be walked to from another commit... and that\ndoesn't seem to work as expected.\n\n git rev-list 0..Y --graph --abbrev-commit --abbrev=4\n* Y\n*   X\n|\\\n| * d\n| * c\n| * b\n* | E\n* | D\n* | C\n* | B\n|/\n* A\n\nFor example... bug is reported to affect 'B'.. .user is at 'd' and is\nwondering if said bug is listed as affecting him.\nCommand:\ngit rev-list B..d --graph ..  reports:\n* d\n* c\n* b\n\n... shouldn't this fail as the path from B to d doesn't really exist?\nOr is there some better command or algorithm to use.\nOne mechanism that I thought 'could' work is to show the parents as\nwell and check that the last listed commit contains B ... but then I\ncan't take advantage of the no-output option for speed...\n\nNow... into 'best method'...  given a list of N revisions with\nassociated bug-items, how would one determine the subset that revision\nA is affected by.\nBasically the bug storage mechanism is a directory structure w/ files\ncontaining bug-items that can have one or more commit references....\nto facilitate faster reports, a small database is used as a caching\nmechanism to help create a distinct list of commits to worry about and\nlook up all the items associated w/ the status-processed commit...\n\nNote: bug-items can mean anything from bug reported at X, bug-status\naffected by X, or bug-closed at X  (at which case any previous items\nrelated to a given bug could be ignored and not displayed... but\nthat's deeper implementation...).\n\nI intend this bug tracker to be best-suited to git... but if other bug\ntrackers could have the mechanisms to provide this commit-tracking,\nthen those could be dropped in...\nAs for web interface idea... I'd probably have it \"linked\" to a\nspecific branch-head for its status-tracking............\n\n-- \nThomas Harning Jr.\n"},{"id":"87510","messageId":"7vfxp3ndec.fsf@gitster.siamese.dyndns.org","threadId":"15064","inReplyTo":"e47324780808171924j237688faj9e13740f89e75fdf@mail.gmail.com","subject":"Re: Best method of detecting if list of commit refs is a parent","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-08-18T04:41:15Z","receivedAt":"2008-08-18T04:41:15Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Thomas Harning Jr.\" <harningt@gmail.com> writes:\n\n> I'm working on my 'Stick' git bug-tracking tool and am working on the\n> functionality to get a list of relevant bug-items at a specific point\n> in history.\n>\n> Before I get into figuring out the 'best' way to do this, I thought\n> I'd at least get the simple single-item case of detecting if a\n> specific commit can be walked to from another commit...\n\nIt is unclear from your description what you are trying to do here, but if\nyou want to know if a commit A is reachable from commit B, the standard\nway to do so is:\n\n        git merge-base A B\n\nIf the output from the command is the object name of commit A, that means\nA is reachable from B.  Otherwise A is not reachable from B.\n\nThis is because \"merge-base\" computes the set of ancestors common to A and\nB that are not reachable from other ancestors common to A and B.\n\nExamples.\n\n(1) This one is obvious.\n\n        A---o---o---o---B\n\n(2) Merge-base between A and B is M.  The one before M is also an ancestor\n    common to A and B, but because it is reachable from M which is another\n    ancestor common between A and B, it won't be part of the merge-base\n    output.\n\n              o---A\n             /\n        o---M---o---B\n\nIf you have bunch of commits A B C D E F and if you would want to know\nwhich one of them is reachable from X, you could of course run merge-base\nonce for each of A..F.  Another way to do this would be to run:\n\n\tgit rev-list A B C D E F ^X\n\nand look at the output.  The ones among A..F that appear in the output are\nnot reachable from X.  The ones that are reachable from X do not appear in\nthe output.\n\nThis is because \"rev-list\" outputs everything reachable from the given\ncommits without ^ prefix, excluding the ones that are reacahble from the\nones prefixed with ^.\n"},{"id":"87538","messageId":"17B524E9-FDF9-4585-AFBD-A5304E3A4AA6@gmail.com","threadId":"15064","inReplyTo":"7vfxp3ndec.fsf@gitster.siamese.dyndns.org","subject":"Re: Best method of detecting if list of commit refs is a parent","fromName":"Thomas Harning","fromEmail":"harningt@gmail.com","sentAt":"2008-08-18T13:37:25Z","receivedAt":"2008-08-18T13:37:25Z","isPatch":false,"sender":{"key":"harningt@gmail.com","avatar":"https://gravatar.com/avatar/a79ddd43da8c8f1f899cd75b7b95cc5f3b2ba5643400468988b1a12c86b75d08?d=mp&s=160"},"body":"On Aug 18, 2008, at 12:41 AM, Junio C Hamano wrote:\n>\n> If you have bunch of commits A B C D E F and if you would want to know\n> which one of them is reachable from X, you could of course run merge- \n> base\n> once for each of A..F.  Another way to do this would be to run:\n>\n> \tgit rev-list A B C D E F ^X\n>\n> and look at the output.  The ones among A..F that appear in the  \n> output are\n> not reachable from X.  The ones that are reachable from X do not  \n> appear in\n> the output.\n>\n> This is because \"rev-list\" outputs everything reachable from the given\n> commits without ^ prefix, excluding the ones that are reacahble from  \n> the\n> ones prefixed with ^.\nPerfect!  Now... is there built-in way to invert this to list those  \nthat 'are' reachable..... Or would the inverse really end up  \ncalculating the difference between input list and output list?\n"},{"id":"88246","messageId":"85B8045C-A137-4D6C-A724-AA9A281620CD@gmail.com","threadId":"15064","inReplyTo":"17B524E9-FDF9-4585-AFBD-A5304E3A4AA6@gmail.com","subject":"Re: Best method of detecting if list of commit refs is a parent","fromName":"Thomas Harning","fromEmail":"harningt@gmail.com","sentAt":"2008-08-23T02:24:44Z","receivedAt":"2008-08-23T02:24:44Z","isPatch":false,"sender":{"key":"harningt@gmail.com","avatar":"https://gravatar.com/avatar/a79ddd43da8c8f1f899cd75b7b95cc5f3b2ba5643400468988b1a12c86b75d08?d=mp&s=160"},"body":"\nOn Aug 18, 2008, at 9:37 AM, Thomas Harning wrote:\n\n> On Aug 18, 2008, at 12:41 AM, Junio C Hamano wrote:\n>>\n>> If you have bunch of commits A B C D E F and if you would want to  \n>> know\n>> which one of them is reachable from X, you could of course run  \n>> merge-base\n>> once for each of A..F.  Another way to do this would be to run:\n>>\n>> \tgit rev-list A B C D E F ^X\n>>\n>> and look at the output.  The ones among A..F that appear in the  \n>> output are\n>> not reachable from X.  The ones that are reachable from X do not  \n>> appear in\n>> the output.\n>>\n>> This is because \"rev-list\" outputs everything reachable from the  \n>> given\n>> commits without ^ prefix, excluding the ones that are reacahble  \n>> from the\n>> ones prefixed with ^.\n> Perfect!  Now... is there built-in way to invert this to list those  \n> that 'are' reachable..... Or would the inverse really end up  \n> calculating the difference between input list and output list?\n>\nHmm... looking at this, git rev-list will also spit out tons of  \n'unimportant' commits so bulk handling could be messy.\n\nGiven the following general feature/function specifications.. perhaps  \nnew functionality to git needs to be coded.... or somehow external  \ncode linking into git needs to be coded (best way to do this?...)\n\n1) Given list of X references, which are in the ancestry of Y?\n2) Given list of X references, which are in the ancestry of set Y  \nreferences? (multi-map X->Y)\n3) Given reference X, which of set Y are descendants?\n\n\nExample tree:\n\n          B--o--F\n         /\n  A--o--O--C--o--o\n         \\        \\\n          D--o--o--E\n\n1) X = (A B C D E F)\n    Y = F\n    OUTPUT: A B F\n    Y = E\n    OUTPUT: A C D E\n\n2) X = (A B C D E F)\n    Y = (A B C D E F)\n    OUTPUT:\n    A->A\n    B->A, B\n    C->A, C\n    D->A, D\n    E->A, C, D, E\n    F->A, B, F\n3) X = A\n    Y = (A B C D E F)\n    OUTPUT:\n     A B C D E F\n    X = C\n    OUTPUT:\n    C E\n\nIt looks like one could calculate these using git rev-list.. but the  \npath list could either get quite full of items to handle..\nYou could also calculate M*N  git rev-list/merge-base to check  \nancestry/decendency...\n"}]}