查找两次提交的第一个普通孩子 [英] Find first common child of two commits
问题描述
:
A
T / \
i B C
m : :
e D E
\ /
| F
V :
git merge-base B E允许查找两个提交的公共祖先A在哪里.有没有办法找到两个分支再次合并的提交F?
此问题不一定是唯一的答案，因此您必须决定一些约束和/或启发式方法，或者接受一个以上的可能性下游"合并.问题的核心与多个合并基础候选者的问题相同-使用git merge-base --all列出所有候选者，否则Git只会选择算法中首先弹出的那个.我们可以这样做，也可以找到所有最佳合并候选者.
您已经绘制了我通常倾向于横向渲染的内容，例如:
B--...--D
/ \
A F--G--H <-- branch1
\ /
C--...--E <-- branch2
但是我们可能会有这个:
B--C---D--E--... <-- branch1
/ \ /
A X
\ / \
F--G---H--I--... <-- branch2
在这种情况下，如果同时允许同时考虑branch1和branch2，则两个合并D和H都是分支合并位置"的候选者.即使您不这样做，如果branch2之后又合并回branch1:
B--C---D--E---J--... <-- branch1
/ \ / /
A X /
\ / \ /
F--G---H--I--... <-- branch2
然后从branch1开始(或以branch1结尾)，D和H都是同样不错的候选人.
无论如何，我们在这里需要枚举以您要考虑的一个或所有分支结束的提交.为此，我们可以使用例如:
git rev-list --ancestry-path ^B ^E branch1 branch2
这会找到branch1 或 branch2的祖先提交，也是提交B 或提交E的后代. >
要真正获得正确的答案，我们要添加--children.这样，我们将获得每个提交的哈希ID，以及该提交的子对象(沿相同方向). Git通过遍历链接时反转从孩子到父母的反向连接来实现--children，这已经足够了；但是我们看不到提交B或E.这是一个问题.为了显示它们，我们可以添加--boundary.这是不理想的:--boundary有时包含一些我们不想要的提交.幸运的是，它们都标记有-，因此我们可以通过剔除那些我们不在乎的提交来排除额外的边界提交.
我将不显示任何内容，但是如果您这样做了，您现在将获得一个列表，每行一个条目，每个节点(顶点)及其连接到其子节点的边.现在，您可以问这些(V，E)集形成的DAG的LCA是什么?
如果我们可以仅使用Git的LCA算法，那就太好了，但是Git无法在任意图上调用它-我们只能在提交上调用它，而实际的提交有父级，而不是子级.因此，您将必须自己编写.请参见在有向无环图中找到最低共同祖先的算法?(不幸的是，该方法没有公认的答案). 此算法在第一次脸红时看起来是正确的；它在图形中具有LCA的两个标准定义之一.
但是，如果我们愿意解决一个不太好的答案，那么在大多数情况下，通过添加--topo-order可以得到足够的东西(以确保父母在所有孩子之后都出来了)和--merges(忽略所有不是合并提交的内容).这将获得所有合并的列表.
我在这里建立了一个带有简单案例的测试库:
$ git log --all --decorate --oneline --graph
* 91fcef6 (HEAD -> master) J
* d1e5905 I
* 5bf18a0 merge
|\
| * 49b2ba7 (sidebr) D
| * 725e5ea C
| * 36b830d (tag: B) B
* | 198a982 (tag: G) G
* | 216bc01 F
* | e905e59 E
|/
* 5df9428 initial
因此，我现在可以使用B和G来命名提交B和G，而我想要沿该方向移动"的分支就是master.所以:
$ git rev-list --topo-order --merges --ancestry-path ^B ^G master
5bf18a0797dfd78107928a9a4095f357cfabe914
last 行是最接近两次提交的合并.在这种情况下，这也是唯一的一行，这就是我们想要的合并.
一旦我们将其绘制出来，这里的缺陷就很明显了.假设我有一个更复杂的图形，例如:
I--J
/ \
H M--N
/ \ / \
/ K--L \
/ \
A P--Q <-- master
\ /
\ C--D /
\ / \ /
B G--O
\ /
E--F
如果我现在运行git rev-list --topo-order --merges --ancestry-path ^B ^H master，我将列举commit P，然后依次列举G和M.因此， last 行将是commit G或commit M，尽管这两个都是合并，但它们不符合正确的标准:它们不符合不能合并B和H.只有提交P会这样做.
因此，要检查您是否有正确的答案(不处理多个LCA问题)，应从此git rev-list命令中提取每条输出线(可能以相反的顺序(考虑添加--reverse))，然后查看如果两个提交都是每个提交的祖先.像G和M这样的内部"合并将只有一个提交作为祖先.要进行is-ancestor测试，请使用git merge-base --is-ancestor:
if git merge-base --is-ancestor $commit1 $mergecommit &&
git merge-base --is-ancestor $commit2 $mergecommit; then
... we've found a correct candidate
else
... move on to another candidate
fi
:
A
T / \
i B C
m : :
e D E
\ /
| F
V :
git merge-base B E allows to find where a the common ancestor A of the two commits. Is there a way to find the commit F where the two branches are merged again?
There isn't necessarily a unique answer to this problem, so you have to decide on a few constraints and/or heuristics, or accept the possibility more than one "downstream" merge. The heart of the problem is the same as the problem of multiple merge base candidates—use git merge-base --all to list them all, otherwise Git just picks whichever one pops up first in its algorithm. We can do the same, or find all best merge candidates.
You've drawn what I usually prefer to render sideways as, e.g.:
B--...--D
/ \
A F--G--H <-- branch1
\ /
C--...--E <-- branch2
but we might have this:
B--C---D--E--... <-- branch1
/ \ /
A X
\ / \
F--G---H--I--... <-- branch2
In this case both merges D and H are equally good candidates for "the place where the branches re-merge" if you allow both branch1 and branch2 to be considered. Even if you don't, if branch2 merges back into branch1 later:
B--C---D--E---J--... <-- branch1
/ \ / /
A X /
\ / \ /
F--G---H--I--... <-- branch2
then just starting from (or ending at) branch1, both D and H are equally good candidates.
In any case, what we need here is to enumerate commits that end in one or all of the branches you want to consider. To do that, we can use, e.g.:
git rev-list --ancestry-path ^B ^E branch1 branch2
This finds commits that are ancestors of branch1 or branch2, and are also descendants of commit B or of commit E.
To really get the right answer, we want to add --children. That way we'll get the hash ID of each commit, along with the children of that commit that go in this same direction. Git achieves the --children by reversing the backwards connections from the children to the parents as it traverses the links, which is good enough; but we won't see commits B or E. This is kind of a problem. To get them shown, we can add --boundary. This is not ideal: --boundary sometimes includes some commits we don't want. Fortunately, they're all marked with - so we can exclude extra boundary commits by knocking out ones that aren't the commits we care about.
I'm not going to show any of that, but if you did that, you would now have a list, one entry per line, of each node (vertex) and its edges that connect to its children. You can now ask What is the LCA of the DAG formed by these (V,E) sets?
It would be nice if we could just use Git's LCA algorithm, but Git does not have a way to invoke it on arbitrary graphs—we can only invoke it on commits, and the actual commits have parents, not children. So you will have to write your own. See Algorithm to find lowest common ancestor in directed acyclic graph? (which, unfortunately, has no accepted answer). This algorithm looks correct at first blush; it has one of the two standard definitions for LCA in a graph.
If we're willing to settle for a not-nearly-as-good answer, though, we can get something that's probably sufficient in most cases by adding --topo-order (to make sure parents come out after all their children) and --merges (to omit everything that's not a merge commit). This will get a list of all merges.
I have made here a test repository with a simple case:
$ git log --all --decorate --oneline --graph
* 91fcef6 (HEAD -> master) J
* d1e5905 I
* 5bf18a0 merge
|\
| * 49b2ba7 (sidebr) D
| * 725e5ea C
| * 36b830d (tag: B) B
* | 198a982 (tag: G) G
* | 216bc01 F
* | e905e59 E
|/
* 5df9428 initial
So I can now name commits B and G using B and G, and the branch I want for a "move in this direction" is just master. So:
$ git rev-list --topo-order --merges --ancestry-path ^B ^G master
5bf18a0797dfd78107928a9a4095f357cfabe914
The last line here is the merge that's "closest" to the two commits. In this case, that's also the only line, and that's the merge we want.
The flaw here is clear enough once we draw it. Suppose I had a more complex graph, such as:
I--J
/ \
H M--N
/ \ / \
/ K--L \
/ \
A P--Q <-- master
\ /
\ C--D /
\ / \ /
B G--O
\ /
E--F
If I now run git rev-list --topo-order --merges --ancestry-path ^B ^H master, I'll enumerate commit P, then both G and M in some order. So the last line will either be commit G or commit M, and while both of these are merges, they don't meet the right criterion: they don't merge B and H. Only commit P does that.
Hence, to check whether you have a right answer—without handling the multiple LCA issue—you should take each of the output lines from this git rev-list command, probably in reverse order (consider adding --reverse), and see if both commits are ancestors of each. "Internal" merges like G and M will have only one commit as an ancestor. To do the is-ancestor test, use git merge-base --is-ancestor:
if git merge-base --is-ancestor $commit1 $mergecommit &&
git merge-base --is-ancestor $commit2 $mergecommit; then
... we've found a correct candidate
else
... move on to another candidate
fi
这篇关于查找两次提交的第一个普通孩子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
