builtin-branch.c: optimize --merged and --no-merged
"git branch --no-merged $commit" used to compute the merge base between
the tip of each and every branch with the named $commit, but this was
wasteful when you have many branches. Inside append_ref() we literally
ran has_commit() between the tip of the branch and the merge_filter_ref.
Instead, we can let the revision machinery traverse the history as if we
are running:
$ git rev-list --branches --not $commit
by queueing the tips of branches we encounter as positive refs (this
mimicks the "--branches" option in the above command line) and then
appending the merge_filter_ref commit as a negative one, and finally
calling prepare_revision_walk() to limit the list..
After the traversal is done, branch tips that are reachable from $commit
are painted UNINTERESTING; they are already fully contained in $commit
(i.e. --merged). Tips that are not painted UNINTERESTING still have
commits that are not reachable from $commit, thus "--no-merged" will show
them.
With an artificial repository that has "master" and 1000 test-$i branches
where they were created by "git branch test-$i master~$i":