Best method of detecting if list of commit refs is a parent

Best method of detecting if list of commit refs is a parent

[Thomas Harning Jr.]

I'm working on my 'Stick' git bug-tracking tool and am working on the
functionality to get a list of relevant bug-items at a specific point
in history.

Before I get into figuring out the 'best' way to do this, I thought
I'd at least get the simple single-item case of detecting if a
specific commit can be walked to from another commit... and that
doesn't seem to work as expected.

 git rev-list 0..Y --graph --abbrev-commit --abbrev=4
* Y
*   X
|\
| * d
| * c
| * b
* | E
* | D
* | C
* | B
|/
* A

For example... bug is reported to affect 'B'.. .user is at 'd' and is
wondering if said bug is listed as affecting him.
Command:
git rev-list B..d --graph ..  reports:
* d
* c
* b

... shouldn't this fail as the path from B to d doesn't really exist?
Or is there some better command or algorithm to use.
One mechanism that I thought 'could' work is to show the parents as
well and check that the last listed commit contains B ... but then I
can't take advantage of the no-output option for speed...

Now... into 'best method'...  given a list of N revisions with
associated bug-items, how would one determine the subset that revision
A is affected by.
Basically the bug storage mechanism is a directory structure w/ files
containing bug-items that can have one or more commit references....
to facilitate faster reports, a small database is used as a caching
mechanism to help create a distinct list of commits to worry about and
look up all the items associated w/ the status-processed commit...

Note: bug-items can mean anything from bug reported at X, bug-status
affected by X, or bug-closed at X  (at which case any previous items
related to a given bug could be ignored and not displayed... but
that's deeper implementation...).

I intend this bug tracker to be best-suited to git... but if other bug
trackers could have the mechanisms to provide this commit-tracking,
then those could be dropped in...
As for web interface idea... I'd probably have it "linked" to a
specific branch-head for its status-tracking............

-- 
Thomas Harning Jr.

Re: Best method of detecting if list of commit refs is a parent

[Junio C Hamano]

"Thomas Harning Jr." <harningt@gmail.com> writes:

> I'm working on my 'Stick' git bug-tracking tool and am working on the
> functionality to get a list of relevant bug-items at a specific point
> in history.
>
> Before I get into figuring out the 'best' way to do this, I thought
> I'd at least get the simple single-item case of detecting if a
> specific commit can be walked to from another commit...

It is unclear from your description what you are trying to do here, but if
you want to know if a commit A is reachable from commit B, the standard
way to do so is:

        git merge-base A B

If the output from the command is the object name of commit A, that means
A is reachable from B.  Otherwise A is not reachable from B.

This is because "merge-base" computes the set of ancestors common to A and
B that are not reachable from other ancestors common to A and B.

Examples.

(1) This one is obvious.

        A---o---o---o---B

(2) Merge-base between A and B is M.  The one before M is also an ancestor
    common to A and B, but because it is reachable from M which is another
    ancestor common between A and B, it won't be part of the merge-base
    output.

              o---A
             /
        o---M---o---B

If you have bunch of commits A B C D E F and if you would want to know
which one of them is reachable from X, you could of course run merge-base
once for each of A..F.  Another way to do this would be to run:

	git rev-list A B C D E F ^X

and look at the output.  The ones among A..F that appear in the output are
not reachable from X.  The ones that are reachable from X do not appear in
the output.

This is because "rev-list" outputs everything reachable from the given
commits without ^ prefix, excluding the ones that are reacahble from the
ones prefixed with ^.

Re: Best method of detecting if list of commit refs is a parent

[Thomas Harning]

On Aug 18, 2008, at 12:41 AM, Junio C Hamano wrote:
>
> If you have bunch of commits A B C D E F and if you would want to know
> which one of them is reachable from X, you could of course run merge- 
> base
> once for each of A..F.  Another way to do this would be to run:
>
> 	git rev-list A B C D E F ^X
>
> and look at the output.  The ones among A..F that appear in the  
> output are
> not reachable from X.  The ones that are reachable from X do not  
> appear in
> the output.
>
> This is because "rev-list" outputs everything reachable from the given
> commits without ^ prefix, excluding the ones that are reacahble from  
> the
> ones prefixed with ^.
Perfect!  Now... is there built-in way to invert this to list those  
that 'are' reachable..... Or would the inverse really end up  
calculating the difference between input list and output list?

Re: Best method of detecting if list of commit refs is a parent

[Thomas Harning]

On Aug 18, 2008, at 9:37 AM, Thomas Harning wrote:

> On Aug 18, 2008, at 12:41 AM, Junio C Hamano wrote:
>>
>> If you have bunch of commits A B C D E F and if you would want to  
>> know
>> which one of them is reachable from X, you could of course run  
>> merge-base
>> once for each of A..F.  Another way to do this would be to run:
>>
>> 	git rev-list A B C D E F ^X
>>
>> and look at the output.  The ones among A..F that appear in the  
>> output are
>> not reachable from X.  The ones that are reachable from X do not  
>> appear in
>> the output.
>>
>> This is because "rev-list" outputs everything reachable from the  
>> given
>> commits without ^ prefix, excluding the ones that are reacahble  
>> from the
>> ones prefixed with ^.
> Perfect!  Now... is there built-in way to invert this to list those  
> that 'are' reachable..... Or would the inverse really end up  
> calculating the difference between input list and output list?
>
Hmm... looking at this, git rev-list will also spit out tons of  
'unimportant' commits so bulk handling could be messy.

Given the following general feature/function specifications.. perhaps  
new functionality to git needs to be coded.... or somehow external  
code linking into git needs to be coded (best way to do this?...)

1) Given list of X references, which are in the ancestry of Y?
2) Given list of X references, which are in the ancestry of set Y  
references? (multi-map X->Y)
3) Given reference X, which of set Y are descendants?


Example tree:

          B--o--F
         /
  A--o--O--C--o--o
         \        \
          D--o--o--E

1) X = (A B C D E F)
    Y = F
    OUTPUT: A B F
    Y = E
    OUTPUT: A C D E

2) X = (A B C D E F)
    Y = (A B C D E F)
    OUTPUT:
    A->A
    B->A, B
    C->A, C
    D->A, D
    E->A, C, D, E
    F->A, B, F
3) X = A
    Y = (A B C D E F)
    OUTPUT:
     A B C D E F
    X = C
    OUTPUT:
    C E

It looks like one could calculate these using git rev-list.. but the  
path list could either get quite full of items to handle..
You could also calculate M*N  git rev-list/merge-base to check  
ancestry/decendency...