查找包含多个特定提交的Git提交

Question

一般问题：给定一组提交，如何找到包含所有这些提交的祖先提交列表，或者相关地，包含所有这些提交的第一个提交。

我可以通过查找所有集合中的提交的git branch --contains <commit>返回的分支（类似标签）来找到包含这些提交的分支，但是git rev-list没有--contains选项。 实际上，我正在寻找一种将常规的--contains参数与git rev-list组合，并将输出限制为包含所有列出的提交的提交，而不仅仅是其中任何一个提交（这是--contains通常的工作方式）。

具体示例：给定提交a，b，c，如何找到具有所有三个提交的祖先的第一个提交？

例如，给定以下树形结构，如何找到标记为X的提交？

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

我认为使用git rev-list和可能涉及到的<commit1>...<commit2>符号，我可以执行一些操作，但我无法进一步理解。

- me_and

---

我想不到一个简单（高效）的方法来做这件事，除非生成所有合并提交的列表，并逐个测试每个提交以查看是否可以从那里到达所需的每个提交。虽然可以相对容易地编写脚本，但速度会很慢。我认为最近（即1.8+）版本的 git 在一些地方添加了 --contains 选项，这可能会使这个过程变得更加容易。 - twalberg

B和C属于不同的分支吗？ - ShadyKiller

@ShadyKiller：在这个具体的例子中，是的；但一般情况下不是。所有三个提交可能在同一个分支中（在这种情况下，答案只是最新的提交），也可能在不同的分支中。甚至可能有更多或更少的提交；那只是一个相对任意的数字。 - me_and

首先，我非常确定 Git 不包含这样的功能。但是可以使用运行时大约为 O(n) 的脚本来实现，其中 n 是您存储库中提交的数量。但是，您为什么需要这个？您是否意识到这可能会有多个答案？ - Chronial

@Chronial：是的，我知道可能有多个“最早”的提交，它们都有列出的提交作为父提交；这就是为什么我写了“包含所有这些提交的第一个提交（们）” :) - me_and

Answer 1

我猜这个问题的答案是，git不是为此而设计的。Git真的不喜欢“commit的子代”的想法，有一个非常好的理由：它没有很好地定义。因为一个提交并不知道它的子代，所以它是一个非常模糊的集合。您可能实际上没有所有分支在您的repo中，因此缺少一些子代。

Git的内部存储结构也使得查找提交的子代成为一个相当昂贵的操作，因为您必须遍历所有头的修订图，直到它们对应的根或者直到您看到所有要了解其子代的提交。

Git支持的唯一这种概念是一个提交包含另一个提交的想法。但是，这个功能只受到很少的git命令的支持（git branch是其中之一）。而且，当git支持它时，它并不支持任意提交，而只支持分支头。

所有这些可能看起来像是git的一个相当严格的限制，但实际上证明你不需要一个提交的“子代”，而通常只需要知道哪些分支包含特定的提交。

---

话虽如此：如果你真的想得到你的问题的答案，你将不得不编写自己的脚本来找到它。最简单的方法是从git rev-list --parents --reverse --all的输出开始。逐行解析，您将构建一棵树，并为每个节点标记它是否是您正在寻找的提交的子代。通过标记提交本身来实现这一点，然后将该属性传递给所有子代等等。

一旦你有一个已经被标记为包含所有提交的提交，你就可以将它添加到你的“解决方案列表”中，并将其所有子代标记为无效-它们不能再包含任何第一次提交了。这个属性也将传递给它的所有后代。

如果您不存储不包含您要求的任何提交的树的任何部分，则可以在这里节省一些内存。

---

编辑 黑客一些Python代码

#!/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)

- Chronial

Answer 2

一个可能的解决方案：

使用“git merge-base a b c”获取要在调用rev-list中使用的提交作为起点；我们将其称为$MERGE_BASE。

使用“git rev-list $MERGE_BASE..HEAD”调用以列出从它们的共同祖先到HEAD的所有提交。循环遍历此输出（伪代码）：

if commit == a || b || c
  break
else 
  $OLDEST_DESCENDANT = commit
return $OLDEST_DESCENDANT

这将适用于您上面的示例，但如果它们从未合并过，或者在a、b、c中最年轻的提交之后的提交中没有合并，或者如果有多个合并提交将a、b和c组合在一起（如果它们各自驻留在自己的分支上），则会产生误报。还需要一些工作来找到最古老的后代。

然后，您应该按照上述内容以$OLDEST_DESCENDANT开头，并从DAG向HEAD反向进行测试（rev-list --reverse $OLDEST_DESCENDANT~..HEAD），以查看'rev-list $MERGE_BASE~..$OLDEST'的输出是否包含所有所需的提交a、b和c（也许有比rev-list更好的方法来测试它们是否可达）。

正如twalberg所提到的，像这样单独测试提交似乎不太理想且速度较慢，但这是一个开始。与他的合并提交列表方法相比，这种方法的优点在于当所有输入提交都在同一分支上时，它将提供有效的响应。

性能主要受到合并基础、head、X和所需提交集（a、b和c）中最年轻的提交之间的距离的影响。

- Kyle

---

这看起来不错，我只是还没有机会坐下来，好好写伪代码，看看会发生什么。 - me_and

Answer 3

怎么样：

MERGE_BASE=`git merge-base A B C`
git log $MERGE_BASE...HEAD --merges

假设您只有一个合并。即使您有更多的合并，最旧的合并也是包含来自所有三个提交的更改的合并。

- ShadyKiller

---

这仅适用于非常简单的情况，如果修订图具有严重的复杂性（实际上需要这样的命令），则只会得到可能是其中之一的所有可能合并的较小列表。而您正在寻找的提交甚至不一定是合并，而可能是列出的其中一个。 - Chronial

你其实不需要给我一个负一啊 :( 。我至少部分是正确的。 - ShadyKiller