Subject: Re: Find out on which branch a commit was originally made) (was ANNOUNCE git-what-branch)

From: Artur Skawina <[email-masked]>
Date: Thu, 23 Sep 2010 23:32:07 +0200

On 09/23/10 15:26, Ævar Arnfjörð Bjarmason wrote:
> On Thu, Sep 23, 2010 at 13:14, Stephen Bash <[email-masked]> wrote:
>>> From: "Seth Robertson" <[email-masked]>
>>> ... I wanted something completely different. Something more
>>> like: if a bug was introduced in commit X, what releases or branches
>>> has it contaminated (or more positively, if a feature was introduced,
>>> where was it made available). The simple case is figuring out on
>>> which branch a commit was originally made.
> 
>> Wait... When you restate the problem that way, isn't
>> git-{branch,tag} --contains the right answer?  I'm curious how you
>> (and others) would differentiate the approaches...
> 
> git-{branch,tag} *is* the right answer, the problem here was that the
> original reporter wanted to *delete* the original branch, or otherwise
> not make it available, but still find out what it was.
> 
> The workaround is to walk the tree from a merge commit, but I think a
> better solution is to just push the refs to your topic branches
> somewhere and keep them in an archive/ namespace. Then if you need to
> go digging you can always add the archive as a remote and go
> git-{branch,tag} --contains.

While this was my initial suggestion too, there are several valid reasons
for wanting such functionality. One is obviously to ease adaptation for 
users switching from other vcses, where branches are much more "special".
Another is that maintaining fine enough granularity in tag/branch naming
may not be that easy, not to mention the namespace clutter that causes and
that large scale omissions are practically impossible to fix retroactively.

But that's not all, consider:

$ time git-show-merge-path 0c357544b0d `git for-each-ref refs/remotes/origin --format='%(refname)'| sed -e 's,refs/remotes/,,'`
f88bdb1c315a M: 'ab/test' => next                                     100818 21:07
# Merged into origin/next
a2c6726417db M: 'ab/test-2'                                           100904 15:15
# Merged into origin/master, origin/HEAD and origin/pu
# Not reachable from origin/html, origin/man, origin/maint and origin/todo
0m0.333s user   0m0.010s system   0m0.355s elapsed   96.82% CPU

$ time git branch -r --contains 0c357544b0d
  remotes/origin/HEAD -> origin/master
  remotes/origin/master
  remotes/origin/next
  remotes/origin/pu
0m0.283s user   0m0.013s system   0m0.303s elapsed   97.84% CPU
$

both commands have approximately the same cost, except the first one gives you
much more information.

Or, using the kernel repo: [1]

$ time git-show-merge-path 86ab04c8c1df51df master release  
b1bc81a0ef86 M: 'master'@$KO/linville/wireless-next-2.6               090607 11:24
36432dae73cf M: 'master'@$KO/davem/net-next-2.6                       090611 14:00
2ed0e21b30b5 M: $KO/davem/net-next-2.6                                090615 16:40
# Merged into release and master
0m3.056s user   0m0.207s system   0m3.154s elapsed   103.46% CPU
$

Script below; w/ one or two args works like the previous git-find-branch-for,
except it's ~two times faster for expensive queries and does that silly five 
old branch request in <13s, for *all* 150 heads; <10s for master alone; also
this one won't show extra merges that happened after the commit arrived on the
branch. When ran w/ more then one branch name, will print the merge points
and/or unreachability info for all of them, as in the above git.git example.

There's still a bug in there somewhere; finding it before blindly transforming
it into perl might be a good idea ;) I'll fix it when i'll encounter it in .rl,
right now i don't remember the random commit (in git.git) which confused it...
Still no ff-detection, mostly due to lack of (real) test case.

artur

[1] yes, 36432dae73cf could be omitted, but i can't convince myself that it
/should/ be. Implementing the filtering would be simple and cheap, but i think
i want to know that another path to master exists.

---------------------------------------------------------------------------------
#! /usr/bin/env pike
// git-show-merge-path <rev> [long-lived-branch(es)]
// v. 0.99
// Will show all external merge commits starting at <rev> until
// this commit appears on the specified branches. When that happens
// "# Merged into <branchlist>" is printed. If <rev> is still
// unreachable from some of the branches then the search continues.
// If at least one of the branches does not contain <rev> then $0
// can and will print *all* merges (ie it won't stop at the last
// of the given branches containing this commit), followed by 
// "# Not reachable from <branchlist>". This is a feature (can be
// used to find leaks outside of the given branches).
//
#define die(a...) exit(1, "Aborting; %s"+a)

string run(string ... cmdline) {
#if __REAL_MAJOR__<7 || __REAL_MAJOR__==7 && __REAL_MINOR__<8
   string s = Process.popen(cmdline*" ");
   if (s=="")
      die("\n", cmdline*" ");
   return s;
#else
   mapping r;
   mixed e = catch { r = Process.run( ({@cmdline}) ); };
   if (e || r["exitcode"])
      die("", e?e:r["stderr"]);
   return r["stdout"];
#endif
}

static mapping commits = ([]);

array parsecommits(string ... delim) {
   array res = ({});
   string id;
   array lines = run("git", "rev-list", "--format=raw",  "--ancestry-path",
                                        "--topo-order", @delim)/"\n";
   mapping branchkids = ([]);
   foreach (lines, string line) {
      array words = line/" ";
      string h = words[0];
      if (h=="commit") {
         id = words[1];
	 commits[id] = ([]);
	 res += ({id});
	 if (mapping bs = m_delete(branchkids, id))
	    commits[id]["Branch"] += bs;
	 if (mapping bs = livebranches[id])
	    commits[id]["Branch"] += bs;
      } else if (h=="") {
         if (commits[id])
            commits[id][""] += ({line});
      }
      else {
         if (h=="parent" && !commits[id]["parent"] && commits[id]["Branch"]) {
            if (branchkids[words[1]])
               branchkids[words[1]] += commits[id]["Branch"];
	    else
               branchkids[words[1]] = commits[id]["Branch"];
         }
         commits[id][h] += words[1..];
      }
   }
   return res;
}

static mapping desc = ([]);

static mapping livebranches = ([]); // id : array(name)
static mapping branchnames = ([]);  // name : void

int main(int argc, array argv) {
   argv[1] = (run("git", "rev-parse", argv[1])/"\n")[0];
   if (argc==2)
      argv += ({"master"});
   for (int i=2; i<sizeof(argv); i++) {
      string ref = argv[i];
      string refid = (run("git", "rev-parse", argv[i])/"\n")[0];
      livebranches[refid] += ([ ref : refid ]);
      branchnames[ref] = refid;
      argv[i] = refid;
   }
   array commit_list = parsecommits("^"+argv[1], @argv[2..]);
   commit_list = reverse(commit_list);
   desc[argv[1]] = 1;
   foreach (commit_list, string id) {
      if (commits[id]["parent"]) {
         foreach (commits[id]["parent"], string parent)
            if (desc[parent])
        	desc[id] = 1;
	 if (sizeof(commits[id]["parent"])>1)
            if (!desc[commits[id]["parent"][0]]) {
	       mapping reached = ([]);
	       if (commits[id]["Branch"])
	          reached = commits[id]["Branch"]&branchnames;
	       int comtime = (int)commits[id]["committer"][-2];
               write("%.12s %-56.56s %.12s\n", id, 
	              squeeze_subject(commits[id][""][1]),
		      cal->Second(comtime)->format_time_xshort() );
               if (sizeof(reached)>0) {
	          branchnames -= reached;
                  write("# Merged into %s\n", 
		          String.implode_nicely(indices(reached)) );
		  if (sizeof(branchnames)==0)
		     exit(0);
	       }
	    }
      }
      m_delete(commits, id);
   }
   write("# Not reachable from %s\n",  String.implode_nicely(indices(branchnames)) );
}

string squeeze_subject(string subject) {

   subject = String.trim_all_whites(subject);
   subject = String.expand_tabs(subject);
   foreach (sub_from_to, mapping m)
      subject = replace(subject, m);
   return subject;
}

static array(mapping) sub_from_to =
({
   ([ 
      "Merge branch " : "Merge ",
      "Merge remote branch " : "Merge ",
      "Merge branches " : "MM:",
   ]),
   ([ 
      "Merge " : "M: ",
      "' of git:": "'@git:",
      "' into ": "' => ",
   ]),
   ([ 
       "git://git.kernel.org/pub/scm/linux/kernel/git/" : "$KO/",
       "commit '" : "C'"
   ]),
});

static object cal = Calendar.ISO.set_timezone(Calendar.Timezone.UTC);

---------------------------------------------------------------------------------