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

From: Thomas Harning <harningt@gmail.com>
Date: Aug 23, 2008, 02:24 UTC
Message-ID: <85B8045C-A137-4D6C-A724-AA9A281620CD@gmail.com>
In-Reply-To: <17B524E9-FDF9-4585-AFBD-A5304E3A4AA6@gmail.com>

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

Show 25 quoted lines

> 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...