How to view the number of DAGs in a Git Repository and the branches associated with each DAG?

user_2913494 0
Viewed 88

I know that you can create orphan branches in Git by passing the --orphan option to git-checkout and that this effectively creates two separate DAGs in your Git repository since the orphan branch isn't connected to the history of the main branch; however, is there any way to figure out how many DAGs are in a given repo if multiple orphan branches were created?

Furthermore, is there a way to figure out which branches (head refs) in a repository are pointing to which DAG? That is, can you group branches based on what DAG the commit they are pointing to is a part of?

This question is more hypothetical than practical since I have no need to do something like this, but I was curious nonetheless.

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

will find all the roots.

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

will find all the refs that trace back to any particular root (to get machine-readable you'll need some scraping, most compact with GNU would be awk 1 RS='\n+| -> |, ').

So this will dump the sets of tips that trace back to each root into 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

And that's the git-specific part of the problem, what's left is to identify the disjoint graphs from these sets. Common elements in any two tip sets join the graphs,

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

has three tips, tools and doc-html share no roots but each of their graphs is joined to the master tip, there's just one connected DAG here if you look at the whole thing. sort tips-*|uniq -c|sort -n|tail -1 will tell you the largest number of roots joined to any one tip, echo $roots|wc -w will tell you how many roots there are, if they match, you've got one joined history, if they don't you've got work left to do.

On any kind of industrial scale I'd hit the books for graph theory on identifying disjoint sets, but incrementally merging a list of provisionally-disjoint sets looks efficient enough for light duty, which in this context means "probably everything", and it's in range for basic unix tools. For a real one-off you don't even need awk for this, just a plain old shell script with shell arrays tracking the sets. isdisjoint() { return $(( 0 == `sort $*|uniq -d|wc -l` )); } and the like.

user_12907310

AFAIK Git does not track individual DAG roots. Here's a method off the top of my head to find them in pseudo-code.

# 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
user_146600
Related