• Derrick Stolee's avatar
    commit-reach: implement get_reachable_subset · fcb2c076
    Derrick Stolee authored
    The existing reachability algorithms in commit-reach.c focus on
    finding merge-bases or determining if all commits in a set X can
    reach at least one commit in a set Y. However, for two commits sets
    X and Y, we may also care about which commits in Y are reachable
    from at least one commit in X.
    
    Implement get_reachable_subset() which answers this question. Given
    two arrays of commits, 'from' and 'to', return a commit_list with
    every commit from the 'to' array that is reachable from at least
    one commit in the 'from' array.
    
    The algorithm is a simple walk starting at the 'from' commits, using
    the PARENT2 flag to indicate "this commit has already been added to
    the walk queue". By marking the 'to' commits with the PARENT1 flag,
    we can determine when we see a commit from the 'to' array. We remove
    the PARENT1 flag as we add that commit to the result list to avoid
    duplicates.
    
    The order of the resulting list is a reverse of the order that the
    commits are discovered in the walk.
    
    There are a couple shortcuts to avoid walking more than we need:
    
    1. We determine the minimum generation number of commits in the
       'to' array. We do not walk commits with generation number
       below this minimum.
    
    2. We count how many distinct commits are in the 'to' array, and
       decrement this count when we discover a 'to' commit during the
       walk. If this number reaches zero, then we can terminate the
       walk.
    
    Tests will be added using the 'test-tool reach' helper in a
    subsequent commit.
    Signed-off-by: 's avatarDerrick Stolee <dstolee@microsoft.com>
    Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
    fcb2c076
commit-reach.h 3.09 KB