From: Thomas Harning <harningt@gmail.com>
Date: Sat, 23 Aug 2008 02:24:44 GMT
Subject: Re: Best method of detecting if list of commit refs is a parent
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:

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