Find Git commits that contain multiple specific commits

Question

General problem: Given a set of commits, how do I find the list of commits that have all those commits as ancestors, or relatedly, the first commit(s) that contain all those commits.

I can find branches (similarly tags) that contain the commits by looking for branches that are returned by git branch --contains <commit> for all the commits in the set, but git rev-list doesn't have a --contains option. Effectively, I'm looking for a way of combining the regular --contains arguments with git rev-list, and limiting the output to commits that contain all the listed commits, not any one of them (which is how --contains works normally).

Specific example: Given commits a, b, c, how can I find the first commit that has all three commits in its ancestry?

For example, given the below tree, how do I find the commit marked X?

* (master)
|
X
|\
a *
| |
b c
|/
*
|
*

I assume there's some magic I can do with git rev-list, and possibly involving the <commit1>...<commit2> notation, but I can't work out further than that.

Answer 1

I guess the answer to that question is that git was not made for this. Git really doesn’t like the idea of “children of a commit”, and there is a very good reason for that: it’s not very well defined. Because a commit doesn’t know a about its children it’s a very vague set. You might not actually have all the branches in your repo and so are missing some children.

Gits internal storage structure also makes finding the children of a commit a rather expensive operation, as you have to walk the revision graph of all heads to either their corresponding roots or till you saw all the commits whose children you want to know about.

The only concept of that kind that git supports is the idea of one commit containing another commit. But this feature is only supported by very few git commands (git branch being one of them). And where git supports it, it does not support it for arbitrary commits, but only branch heads.

This all might seem like a rather harsh limitation of git, but in practice it turns out that you don’t need the “children” of a commit but usually only need to know which branches contain a specific commit.

---

That all said: If your really want to get the answer to your question, you will have to write your own script that finds it. The easiest way to go by this is to start with the output of git rev-list --parents --reverse --all. Parsing that line by line, you would build a tree, and for each node mark whether it is a child of the commits you are looking for. You do this by marking the commits themselves once you meet them and then carrying that property on to all their children and so on.

Once you have a commit that’s marked as containing all the commits, you add it to your “solution list” and mark all its children as dead – they can’t contain any first commits any more. This property will then also be passed on to all its descendants.

You can save a bit of memory here if you don’t store any parts of the tree that don’t contain any of the commits you asked for.

---

edit Hacked some python code

#!/usr/bin/python -O
import os
import sys

if len(sys.argv) < 2:
    print ("USAGE: {0} <list-of-revs>".format([sys.argv[0]]))
    exit(1)

rev_list = os.popen('git rev-list --parents --reverse --all')

looking_for = os.popen('git rev-parse {0}'
                       .format(" ".join(sys.argv[1:]))).read().splitlines()
solutions = set()
commits = {}

for line in rev_list:
    line = line.strip().split(" ")
    commit = set()
    sha = line[0]
    for parent in line[1:]:
        if not parent in commits:
            continue
        commit.update(commits[parent])
        if parent in solutions:
            commit.add("dead")
    if sha in looking_for:
        commit.add(sha)
    if not "dead" in commit and commit.issuperset(looking_for):
        solutions.add(sha)
    # only keep commit if it's a child of looking_for
    if len(commit) > 0:
        commits[sha] = commit

print "\n".join(solutions)