Re: Find out on which branch a commit was originally made

In message <4C9782A3.5010005@gmail.com>, Artur Skawina writes:

    Received very little testing, i only tried it on a few commits, other
    than the example from this thread, but so far seems to do the right
    thing for all of them.

I've discovered an error case in your pike script's logic (as and if I understand it). If there are multiple children of the commit in question and those two children both merge onto the target branch, the path your program prints is incorrect (specifically, for reference B it prints D and then G--the correct answer is G only or a least D+H). It does not check to see whether a specific reachable merge commit is reachable by the path you have started to print.

----master-----------G------H
                    /      /
                    |     /
 --A-------D-----------F-
          /         |
 ----B---C          |
      \             |
       ----------E--/

    Unpikifying is left as an exercise for the user. ;)

I've converted it to perl and it now handles both your problem (which I now understand, I was distracted by the subject line) and mine (which I now better understand includes yours as well--we use --rebase a lot so don't have many unnamed branches). I'm also being annoyed at git's default merge --ff option which causes the wrong branch to be labeled with the branch name.

Of course it still suffers from reporting branches created after the reference you are interested in was created.

					-Seth Robertson

git://github.com/SethRobertson/git-what-branch.git

---------------------------------------------------------------------- #!/usr/bin/perl # # Tell us what preferred branch a commit was made on and if has not # been made on any preferred branch, the earliest path the commit got # onto a named branch. # # Preferred meaning ignoring branches that are a descendant due to a # merge, close to the answer you would have gotten if you had asked # the question at the moment the commit/tag was made. # # If I am on a release branch and tag a commit, if I ask that question # I should be told the name of the release branch. If I later merge # onto master and ask that question, being told that the tag was also # made on master is disingenious. master is a descendant, but the tag # was not made on master. # # 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: [--allref] [--all] [--quiet] [--reference-branch=branchname] [--reference=reference] <commit-hash/tag>...

--allref
	Consider even remote branches as candidates for the branch a
	reference is on

--all
	Print all reachable branch names (and merge paths)

--quiet
	Print only the branch names, not the merge paths

--reference-branch <branchname>
	The command line arguments/reference are searched to see if
	they can reach this branch.

--reference <hash|tag>
	Specify a particular commit you which you want to
	know how the commit in question was reached
";

my(%OPTIONS); Getopt::Long::Configure("bundling", "no_ignore_case", "no_auto_abbrev", "no_getopt_compat", "require_order"); GetOptions(\%OPTIONS, 'a|allref', 'all', 'quiet', 'debug', 'reference-branch=s', 'reference=s', 'verbose|v+') || die $USAGE;

my ($OPT_A); $OPT_A="-a" if ($OPTIONS{'a'});

if ( $#ARGV < 0 )
{
    print STDERR $USAGE;
    exit(2);
}

my ($MULTI); $MULTI=1 if ( $#ARGV > 0 );

########################################
#
# Describe a hash if necessary
#
sub describep($)
{
  my ($ref) = @_;

  if ($ref =~ /^[0-9a-f]{40}$/)
  {
    my $newref;
    chomp($newref = `git describe $ref`);
    $ref = $newref if ($newref && $? == 0);
  }
  $ref;
}

########################################
#
# 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;
	  }
	}
	unshift(@minp,$id);
	return(@minp);
      }
    }

    $id = $tree->{$id}->{'parent'}->[0];
  }
  ();
}

foreach my $f (@ARGV)
{
  print "Looking for $f\n++++++++++++++++++++++++++++++++++++++++\n" if ($MULTI);

  # 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'})
  {
    my $tmp = `git rev-list -n 1 $OPTIONS{'reference'} 2>/dev/null`;
    die "Unknown --reference $OPTIONS{'reference'}\n" if ($?);
    chomp($tmp);
    @first = ($tmp);
  }
  else
  {
    # Generate first pass list of candidate branches
    @first = grep(s/^\*?\s+// && s/\n// && !/ -\> / && (!$OPTIONS{'reference-branch'} || $OPTIONS{'reference-branch'} eq $_),`git branch $OPT_A --contains $f`);

    if ($#first < 0)
    {
      my $msg = "any named branch";
      $msg = "any local named branch" unless ($OPTIONS{'a'});
      $msg = "branch $OPTIONS{'reference-branch'}" if ($OPTIONS{'reference-branch'});
      die "Commit $f has not merged onto $msg yet\n";
    }
  }

  # Shortcut if we might only need direct commit branches
  if (!$OPTIONS{'all'})
  {
    # Look for merge intos to exclude
    foreach my $br (@first)
    {
      # Exclude branches that this commit was merged into
      push(@second,$br) if (grep(/$TARGET/,`git rev-list --first-parent $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",@second)."\n";
  }
  else
  {
    # Commit is on an anonymous branch, find out where it merged

    my (%brtree,%min);
    foreach my $br (@first)
    {
      my (%commits,@commits);
      my $SOURCE = `git rev-list -n 1 $br 2>/dev/null`;
      die "Cannot find branch reference.  Huh?\n" if ($?);
      chomp($SOURCE);
      print STDERR "Checking branch $br\n" if ($OPTIONS{'debug'});

      # Discover all "ancestry-path" commits between target and branch
      my $cmd = qq^git rev-list --ancestry-path --date-order --format=raw "$TARGET".."$br"^;
      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];
	}
      }

      print STDERR "Found $#commits+1\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'};

	# Check to see if this commit is actually a descent of $TARGET
	if (grep($mark{$_},@{$commits{$id}->{'parent'}}))
	{
	  $mark{$id} = ++$cnt;
	}

	# 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]})
	  {
	    push(@path,$id);
	  }
	}
      }

      # Check to make sure we have gone from TARGET or SOURCE via parents
      if (!$mark{$SOURCE})
      {
	# Not connected
	next;
      }

      print STDERR "Found $#path+1 initial path entries\n" if ($OPTIONS{'debug'});

      if ($#path >= 0)
      {
	my $id = $path[$#path];
	@path = find_shortest($id,$TARGET,\%commits,\%mark);
	$brtree{$br}->{'path'} = \@path;
	$brtree{$br}->{'cnt'} = $#path;
	$brtree{$br}->{'tstamp'} = $commits{$id}->{'committime'};

	if ($OPTIONS{'all'})
	{
	  if ($OPTIONS{'quiet'})
	  {
	    print "$br\n";
	  }
	  else
	  {
	    print "* $TARGET first merged onto $br using the following path:\n";
	    my $last = describep($TARGET);
	    foreach my $mp (@{$brtree{$br}->{'path'}})
	    {
	      my $newm = describep($mp);
	      print "  $last merged up at $newm (@{[scalar(localtime($commits{$mp}->{'committime'}))]})\n";
	      $last = $newm;
	    }
	    print "  $last is on $br\n";
	  }
	}
	else
	{
	  if (!defined($min{'tstamp'}) || $min{'tstamp'} > $brtree{br}->{'tstamp'})
	  {
	    %min = %{$brtree{$br}};
	    $min{'br'} = $br;
	    $min{'commits'} = \%commits;
	  }
	}
      }
      else
      {
	if ($OPTIONS{'all'})
	{
	  print "$TARGET is on $br\n";
	}
	else
	{
	  print "$br\n";
	}
	$min{'tstamp'} = 0;
	delete($min{'br'});
      }
    }

    if (!$OPTIONS{'all'})
    {
      if ($min{'br'})
      {
	if ($OPTIONS{'quiet'})
	{
	  print "$min{'br'}\n";
	}
	else
	{
	  print "$f first merged onto $min{'br'} using the following minimal path:\n";
	  my $last = describep($TARGET);
	  foreach my $br (@{$min{'path'}})
	  {
	    my $newm = describep($br);
	    print "  $last merged up at $newm (@{[scalar(localtime($min{'commits'}->{$br}->{'committime'}))]})\n";
	    $last = $newm;
	  }
	  print "  $last is on $min{'br'}\n";
	}
      }
      else
      {
	print "Could not find $f connected anywhere\n" unless defined($min{'tstamp'});
      }
    }
  }
  print "----------------------------------------\n" if ($MULTI);
}