Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

executable file 575 lines (461 sloc) 15.307 kb
#!/usr/bin/perl
#
# Tell us (by default) the earliest causal path of commits and merges to
# cause the requested commit got onto a named branch. If a commit was
# made directly on a named branch, that obviously is the earliest path.
#
# See the pod documentation below for more information
#
# Thanks to Artur Skawina for his assistance in developing some
# of the algorithms used by this script.
#
# License: GPL v2
# Copyright (c) 2010 Seth Robertson
#
use warnings;
no warnings "uninitialized";
use Getopt::Long;
use strict;
my $USAGE="$0: [[--branches] | [--allbranches] | [--tags] | [--allref]]
[--first-parent] [--first-parent-simple]
[--all] [--quiet] [--reference=reference[,reference]...] [--version]
<commit-SHA/tag>...
";
my(%OPTIONS);
Getopt::Long::Configure("bundling", "no_ignore_case", "no_auto_abbrev", "no_getopt_compat", "require_order");
GetOptions(\%OPTIONS, 'first-parent', 'first-parent-simple', 'branches|b', 'allbranches', 'tags|t', 'allref|a', 'all', 'quiet', 'debug+', 'reference|references=s', 'verbose|v+', 'version', 'topo-order', 'date-order') || die $USAGE;
if ($OPTIONS{'version'})
{
print "$0 version is {UNTAGGED}\n";
exit(0);
}
if ( $#ARGV < 0 )
{
print STDERR $USAGE;
exit(2);
}
my ($MULTI);
$MULTI=1 if ( $#ARGV > 0 );
my(%translation,%TRANSLATION);
our($exitcode) = 0;
$OPTIONS{'first-parent'} = 1 if ($OPTIONS{'first-parent-simple'});
########################################
#
# Describe a hash if necessary
#
sub describep($)
{
my ($ref) = @_;
my ($ret) = $ref;
if ($ref =~ /^[0-9a-f]{40}$/)
{
if ($translation{$ref})
{
my @tmp = @{ $translation{$ref} };
if ($OPTIONS{'first-parent-simple'})
{
$ret = join("\n",@tmp);
}
else
{
$ret = pop(@tmp);
if ($#tmp >= 0)
{
$ret .= "(aka ".join(", ",@tmp).")";
}
}
}
else
{
my $newref;
chomp($newref = `git describe --tags --always $ref`);
$ret = $newref if ($newref && $? == 0);
}
}
$ret;
}
########################################
#
# Find shortest path through a dag
# Return array of shortest path
#
sub find_shortest($$$$);
sub find_shortest($$$$)
{
my ($id,$target,$tree,$mark) = @_;
print STDERR "Looking at node $id\n" if ($OPTIONS{'debug'});
while ($id ne $target)
{
# Is this a merge commit?
if ($#{$tree->{$id}->{'parent'}} > 0)
{
# Is the first parent not a descendant?
if (!$mark->{$tree->{$id}->{'parent'}->[0]})
{
my (@minp);
my ($mindef);
# See which parent is the best connected
foreach my $parent (@{$tree->{$id}->{'parent'}})
{
next unless $mark->{$parent};
my (@tmp) = find_shortest($parent,$target,$tree,$mark);
if (!$mindef || $#minp > $#tmp)
{
@minp = @tmp;
$mindef = 1;
}
}
push(@minp,$id);
return(@minp);
}
}
$id = $tree->{$id}->{'parent'}->[0];
}
();
}
# topo/date sort order
sub myorder
{
my $ret;
if ($OPTIONS{'topo-order'})
{
$ret = $::brt{$a}->{'cnt'} <=> $::brt{$b}->{'cnt'};
return($ret) if ($ret);
}
$ret = $::brt{$a}->{'tstamp'} <=> $::brt{$b}->{'tstamp'};
$ret = (describep($a) cmp describep($b)) if (!$ret);
$ret;
};
my(@references,@REFERENCES);
if ($OPTIONS{'reference'})
{
foreach my $ref (split(',',$OPTIONS{'reference'}))
{
my $tmp = `git rev-list -n 1 $ref 2>/dev/null`;
die "Unknown --reference $ref\n" if ($?);
chomp($tmp);
push(@{$TRANSLATION{$tmp}}, $ref);
push(@REFERENCES,$tmp);
}
}
foreach my $f (@ARGV)
{
print "Looking for $f\n++++++++++++++++++++++++++++++++++++++++\n" if ($MULTI);
%translation = %TRANSLATION;
@references = @REFERENCES;
# Translate into a commit hash
my ($TARGET)=`git rev-list -n 1 $f 2>/dev/null`;
die "Unknown reference $f\n" if ($?);
chomp($TARGET);
my (%first,@second);
if ($OPTIONS{'reference'})
{
map($first{$_}=1,@references);
}
else
{
# Generate first pass list of candidate branches
my $cmd;
my $error;
if ($OPTIONS{'allref'})
{
$cmd = "git tag --contains $f; git branch --no-color -a --contains $f";
$error = "named ref";
}
elsif ($OPTIONS{'tags'})
{
$cmd = "git tag --contains $f";
$error = "tag";
}
elsif ($OPTIONS{'allbranches'})
{
$cmd = "git branch --no-color -a --contains $f";
$error = "branch";
}
else
{
$cmd = "git branch --no-color --contains $f";
$error = "local branch";
}
print STDERR "Running $cmd\n" if ($OPTIONS{'debug'} > 1);
foreach my $ref (grep(s/^\*?\s*// && s/\n// && !/\(no branch\)/ && !/ -\> /,`$cmd`))
{
my $tmp = `git rev-list -n 1 $ref 2>/dev/null`;
die "Unknown --reference $ref\n" if ($?);
chomp($tmp);
push(@{$translation{$tmp}}, $ref);
$first{$tmp} = 1;
}
if (!%first)
{
warn "Commit $f has not merged with any $error yet\n";
$exitcode = 2;
next;
}
}
print STDERR "Considering @{[join(',',map(describep($_),keys %first))]}\n" if ($OPTIONS{'debug'} > 1);
# Look for merge intos to exclude
foreach my $br (keys %first)
{
# Exclude branches that this commit was merged into
if (grep(/$TARGET/,`git rev-list --first-parent $br`))
{
delete($first{$br});
push(@second,$br);
}
}
if ($#second >= 0)
{
# If branch was subsequently forked via `git branch <old> <new>`
# we might have multiple answers. Only one is right, but we
# cannot figure out which is the privledged branch because the
# branch creation information is not preserved.
print join("\n",map(describep($_),@second))."\n";
}
if (($#second < 0 || $OPTIONS{'all'}) && %first)
{
# Commit is on an anonymous branch, find out where it merged
if ($OPTIONS{'first-parent'})
{
warn "Commit $f was not directly on any candidates\n";
$exitcode = 1;
next;
}
my (%brtree);
my (%commits,@commits);
# Discover all "ancestry-path" commits between target and sources/branches
my $cmd = qq(git rev-list --ancestry-path --date-order --format=raw ^"$TARGET" "@{[join('" "',keys %first)]}");
my ($commit);
foreach my $line (`$cmd`)
{
my (@f) = split(/\s+/,$line);
if ($f[0] eq "commit")
{
$commit = $f[1];
$commit =~ s/^-//; # I have never seen this myself, but Artur Skawina wrote code to defend against it
unshift(@commits,$commit);
}
if ($f[0] eq "parent")
{
push(@{$commits{$commit}->{'parent'}},$f[1]);
}
if ($f[0] eq "committer")
{
$commits{$commit}->{'committime'} = $f[$#f-1];
}
}
if ($#commits < 0)
{
warn qq^Cannot get from @{[describep($TARGET)]} to @{[join(", ",map(describep($_),keys %first))]}\n^;
next;
}
print STDERR qq^Found $#commits+1, going from @{[describep($TARGET)]} to @{[join(", ",map(describep($_),keys %first))]}\n^ if ($OPTIONS{'debug'});
my (@path);
# Go through commit list (in forward chonological order)
my (%mark,$cnt);
$mark{$TARGET} = ++$cnt;
foreach my $id (@commits)
{
next unless $commits{$id}->{'parent'};
print STDERR "Forward $id with ".(join(",",@{$commits{$id}->{'parent'}})) if ($OPTIONS{'debug'});
# Check to see if this commit is actually a descent of $TARGET
if (my @old = grep($mark{$_},@{$commits{$id}->{'parent'}}))
{
$mark{$id} = $mark{$old[0]};
print STDERR " mark $mark{$id}" if ($OPTIONS{'debug'});
}
# Is this a merge commit?
if ($#{$commits{$id}->{'parent'}} > 0)
{
# Is the first parent not a descendant? (earliest merge)
if (!$mark{$commits{$id}->{'parent'}->[0]})
{
$mark{$id} = ++$cnt;
}
}
print STDERR "\n" if ($OPTIONS{'debug'});
}
my ($direct);
foreach my $br (keys %first)
{
# Check to make sure we have gone from TARGET or SOURCE via parents
if (!$mark{$br})
{
print STDERR "Did not reach @{[describep($br)]} from @{[describep($TARGET)]}\n" if ($OPTIONS{'debug'});
# Not connected
next;
}
if ($mark{$br} > 1)
{
@path = find_shortest($br,$TARGET,\%commits,\%mark);
$brtree{$br}->{'path'} = \@path;
$brtree{$br}->{'cnt'} = $#path;
$brtree{$br}->{'tstamp'} = $commits{$path[$#path]}->{'committime'};
foreach my $mp (@{$brtree{$br}->{'path'}})
{
push(@{$brtree{$br}->{'committimes'}},$commits{$mp}->{'committime'});
}
}
else
{
if ($OPTIONS{'all'})
{
print "$f is on @{[describep($br)]}\n";
}
else
{
print describep($br)."\n";
}
$direct = 1;
}
}
if (!$direct || $OPTIONS{'all'})
{
local %::brt = %brtree;
my (@brlist) = sort myorder (keys %brtree);
my ($lastts,$last);
foreach my $br (@brlist)
{
next unless (exists($brtree{$br}->{'cnt'}));
if ($lastts != $brtree{$br}->{'tstamp'})
{
last if (!$OPTIONS{'all'} && $lastts);
print "\n" if ($lastts || $direct);
$lastts = $brtree{$br}->{'tstamp'};
if (!$OPTIONS{'quiet'})
{
print "@{[describep($f)]} used the following minimal".($OPTIONS{'topo-order'}?"":" temporal")." path:\n";
my ($maxlen);
foreach my $mp (@{$brtree{$br}->{'path'}})
{
my $newm = describep($mp);
$maxlen = length($newm) if (length($newm) > $maxlen);
}
$last = describep($TARGET);
foreach my $mp (@{$brtree{$br}->{'path'}})
{
my $newm = describep($mp);
my $ctime = shift(@{$brtree{$br}->{'committimes'}});
printf(" merged to %-${maxlen}s \@@{[scalar(localtime($ctime))]}\n",$newm);
$last = $newm;
}
print " $last is on @{[describep($br)]}\n";
next;
}
}
if ($OPTIONS{'quiet'})
{
print describep($br)."\n";
}
else
{
print " $last is on @{[describep($br)]}\n";
}
}
}
}
print "----------------------------------------\n" if ($MULTI);
}
exit($exitcode);
=pod
=head1 NAME
git-what-branch - Discover what branch a particular commit was made on or near
=head1 SYNOPSIS
git-what-branch [[--branches] | [--allbranches] | [--tags] | [--allref]] [--first-parent] [--first-parent-simple] [--all] [--topo-order | --date-order ] [--quiet] [--reference=reference,reference,reference] <commit-hash/tag>...
=head1 OVERVIEW
Tell us (by default) the earliest causal path of commits and merges to
cause the requested commit got onto a named branch. If a commit was
made directly on a named branch, that obviously is the earliest path.
By earliest causal path, we mean the path which merged into a named
branch the earliest, by commit time (unless --topo-order is
specified).
You may specify a particular reference branch or tag or revision to
look at instead of searching (by default) the path for all named
branches. Searching the path for all named branches can take a long
time for an early commit occurring on many branches. If you
specifically name a reference branch or commit, it should normally
take seconds.
=head1 DESCRIPTION
=head2 --branches
The default mode of check the path to any local branch.
=head2 --allbranches
Check the path to any local or remote branch.
=head2 --tags
Check the path to any known tags
=head2 --allref
Check the path to any local or remote branch and to any tag.
=head2 --all
If the commit in question was not made directly on a named branch (in
which case all branch names would be printed), the system picks the
named branch which the commit was merged to first and prints only that
path. With this argument all paths from the commit in question to all
named branches that it was committed onto are printed.
=head2 --first-parent
If the commit in question was not made directly on a named branch, fail.
If the commit was made directly on a named branch, print the branch name or names.
=head2 --first-parent-simple
Same as --first-parent except instead of outputting in the "(aka)"
format if there are multiple differently spelled but otherwise
identical branches, print all directly reachable branches/references
out with one line per branch/reference.
=head2 --topo-order
Instead of selecting the merge path which resulted in the earliest
commit to a named branch, select the merge path which resulted in the
fewest merges. If multiple merge paths have the same distance, use
earliest merge to break ties.
=head2 --date-order
The default ordering where the merge path which resulted in the
earliest commit to a named branch is displayed.
=head2 --quiet
If the commit was not made on a branch, do not print the path from the
commit to the named branch, just print the branch name.
=head2 --reference <tagname/commithash/branchname>
Instead of auto-generating the list of branches/tags to check to see
how the commit in question got there, specify the (comma seperated)
list of tags, branch names, commits, or other references that this
program should use to try and find minimal and early paths to from the
command line references.
=head1 PERFORMANCE
If many branches (e.g. hundreds) contain the commit, the system may
take a long time (for a particular commit in the linux tree, it took 8
second to explore a branch, but there were over 200 candidate
branches) to track down the path to each commit. Selection of a
particular --reference-branch --reference tag to examine will be
hundreds of times faster (if you have hundreds of candidate branches).
=head1 EXAMPLES
# git-what-branch --all 1f9c381fa3e0b9b9042e310c69df87eaf9b46ea4
v2.6.12-rc3-450-g1f9c381 used the following minimal temporal path:
merged to v2.6.12-rc3-461-g84e48b6 @Tue May 3 18:27:24 2005
merged to v2.6.12-rc3-590-gbfd4bda @Thu May 5 08:59:37 2005
v2.6.12-rc3-590-gbfd4bda is on v2.6.12-n
v2.6.12-rc3-590-gbfd4bda is on v2.6.12-rc4-n
[...]
v2.6.12-rc3-590-gbfd4bda is on v2.6.36-rc4-n
v2.6.12-rc3-590-gbfd4bda is on v2.6.36-rc5-n(aka master)
=head1 BUGS
git fast-forward merges make changes to branches without reflecting
that history in a merge commit. This means that when later reviewing
that history, git may label (via --first-parent) the wrong branch as
being named a specific name. Any lies which git makes are reflected
in the output of this program.
Branches which are created after the commit you are interested in has
been merged into another named branch you are interested in cannot be
distinguished from the original branch. Example if you have master
branch, you make commit A, then make a release branch named v1.0,
after branch v1.0 has been created there is no way to know that v1.0
was created later and so both branches will be listed as the branches
that commit A was made on. If git recorded when a branch was created,
we could avoid this problem.
If multiple branches (say due to the previous bug) are candidates and
the commit was NOT made directly on a named branch but rather on an
anonymous branch that was merged, unless you request --all, a
pseudo-random branch will be chosen as the branch advertised via the
merge path.
This program does not take into account the effects of cherry-picking
the commit of interest, only merge operations.
=head1 ACKNOWLEDGMENTS
Thanks to Artur Skawina for his assistance in developing some
of the algorithms used by this script.
=head1 COPYRIGHT/LICENSE
License: GPL v2
Copyright (c) 2010 Seth Robertson
Jump to Line
Something went wrong with that request. Please try again.