如何查看Git Repository中的DAG数量以及与每个DAG关联的分支？

Question

我知道您可以通过将--orphan选项传递给git-checkout来在Git中创建孤立分支，这将在您的Git存储库中有效地创建两个单独的DAG，因为孤立分支没有连接到主分支的历史记录；然而，如果创建了多个孤立分支，有没有办法计算出在给定的存储库中有多少DAG？

此外，有没有办法找出存储库中的哪些分支(头引用)指向哪个DAG？也就是说，您可以根据分支所指向的提交是哪个DAG的一部分对分支进行分组吗？

这个问题更多的是假设而不是实际，因为我不需要做这样的事情，但我还是很好奇。

Answer 1

git rev-list --all --max-parents=0

会找到所有的根。

git log --all --ancestry-path ^$root --pretty=%D --simplify-by-decoration

我会找到所有可以追溯到特定根目录的refs (为了让机器可读，你需要一些抓取，对于GNU来说最紧凑的应该是awk 1 RS='\n+| -> |, ')。

因此，这会将追溯到每个根目录的提示集转储到tips-$root中

roots=`git rev-list --all --max-parents=0`
for root in $roots; do
        git log --all --ancestry-path ^$root --pretty=%D \
        | awk 1 RS='\n+|, | -> ' >tips-$root
done

这就是问题的git特定部分，剩下的就是从这些集合中识别不相交的图。任意两个尖端集合中的公共元素连接图，

A--\     tools
*---B    master
C--/     doc-html

有三个提示，tools和doc-html没有共享的根，但他们的每个图都连接到master提示，如果你查看整个过程，这里只有一个连接的DAG。sort tips-*|uniq -c|sort -n|tail -1会告诉你连接到任何一个提示的根的最大数量，echo $roots|wc -w会告诉你有多少个根，如果它们匹配，你就有一个连接的历史，如果它们不匹配，你就有工作要做。

在任何一种工业规模上，我都会去读图论中关于识别不相交集合的书籍，但增量地合并临时不相交集合的列表对于轻量级来说看起来足够有效，在本文中这意味着“可能一切”，它在基本unix工具的范围内。对于真正的一次性操作，您甚至不需要awk来实现这一点，只需要一个普通的旧式shell脚本，其中包含跟踪集合的shell数组。isdisjoint() { return $(( 0 == `sort $*|uniq -d|wc -l` )); }等。

Answer 2

AFAIK Git不跟踪单个DAG根。这里有一个我想不到的方法，可以用伪代码找到它们。

# Get a list of all branches.
branches = `git branch`

# Store an empty list of roots.
roots = []

while branches
  # Pick a branch, any branch.
  branch = branches.pop

  # Find its root and add it to the list.
  root = `git log --topo-order --oneline #{branch} | tail -1`
  roots << root

  # Remove any branches which contain the root.
  branches -= `git branch --contains #{root}`
end

p roots