Subject: git-show-merge-path v1.0

From: Artur Skawina <[email-masked]>
Date: Fri, 24 Sep 2010 21:03:54 +0200

This started as a quick graph walking hack, but evolved into something that
can actually be useful.

git-show-merge-path can tell /if/, /how/ and /when/ a change became visible
from a certain branch or tag. Or a few hundred thereof.

"git-show-merge-path <commit> <targets>".

$ git-show-merge-path <commit> heads    # checks all local branches
$ git-show-merge-path <commit> tags     # checks all tags
$ git-show-merge-path <commit> heads/as # checks all local branches named 'as/...'
$ git-show-merge-path <commit> remotes/name
                                        # checks all refs of the named remote
$ git-show-merge-path <commit> remotes  # checks all refs of all remotes
$ git-show-merge-path <commit> heads/master
                                        # checks the local 'master' branch
$ git-show-merge-path <commit> master   # checks all 'master' branches
                                        # (incl. remotes etc)
$ git-show-merge-path <commit> 'doh*'   # checks all branches named 'doh...'
$ git-show-merge-path <commit> 'tags/v2.*' # checks all tags beginning w/ "v2."
$ git-show-merge-path <commit> '*'      # checks every reference it finds
$ git-show-merge-path <commit> refs/heads/master # for nonhumans, or situations
                                        # where the DWIM approach fails.

Eg inside a git.git clone "git-show-merge-path 829ef38 next" will say
how 829ef38 merged into 'origin/next' and "git-show-merge-path 829ef38 origin"
will report the status vs all the branches in that repo;

$ git-show-merge-path 829ef38 origin
12f7559e0634 M: 'dm/mergetool-vimdiff' => next                        100922 16:36
          \_ Merged into next and pu [v1.7.3-60-g12f7559]
             Not reachable from HEAD, html, maint, man, master and todo

Checking which release included some change could look like this:

$ git-show-merge-path 657b6245b tags
44f9e6c6bc50 M: 'nouveau/for-airlied' => drm-linus                    091223 00:28
f42ecb2808db M: 'drm-linus'@$KO/airlied/drm-2.6                       091223 16:59
          \_ Merged into v2.6.33, v2.6.33-rc2, v2.6.33-rc3, v2.6.33-rc4, v2.6.33-rc5,
 v2.6.33-rc6, v2.6.33-rc7, v2.6.33-rc8, v2.6.33.1, v2.6.33.2, v2.6.34, v2.6.34-rc1,
 v2.6.34-rc2, v2.6.34-rc3, v2.6.34-rc4, v2.6.34-rc5, v2.6.34-rc6, v2.6.34-rc7, v2.6.34.1,
 v2.6.35, v2.6.35-rc1, v2.6.35-rc2, v2.6.35-rc3, v2.6.35-rc4, v2.6.35-rc5, v2.6.35-rc6,
 v2.6.35.1, v2.6.35.2, v2.6.35.3, v2.6.36-rc1 and v2.6.36-rc2 [v2.6.33-rc1-266-gf42ecb2]
[followed by some uninteresting merges, and a long list of tagged releases which
 do not contain this commit]

Note that the ref names it prints are simplified; if unsure, do not
rely on the DWIM target selection, just give it a full "refs/..." name.

artur

----------------------------------------------------------------------
#! /usr/bin/env pike
// git-show-merge-path <rev> [long-lived-branch(es)]
// v. 1.0
// 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)

static mapping commits = ([]);

array parsecommits(string ... delim) {
   array res = ({});
   string id;
   array lines = run("git", "rev-list", "--format=raw", "--ancestry-path",
                                        "--date-order", @delim)/"\n";
   foreach (lines, string line) {
      array words = line/" ";
      string h = words[0];
      if (h=="commit") {
         id = words[1];
         if (!commits[id])
            commits[id] = ([]);
         res += ({id});
         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"]) {
            string firstparent = words[1];
            if (!commits[firstparent])
               commits[firstparent] = ([ "Branch" : commits[id]["Branch"] ]);
            else
               commits[firstparent]["Branch"] += commits[id]["Branch"];
         }
         commits[id][h] += words[1..];
      }
   }
   return res;
}

static mapping desc = ([]);

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

int main(int argc, array argv) {
   argv[1] = (run("git", "rev-parse", argv[1])/"\n")[0];
   if (argc==2)
      argv += ({"master"});
   branchnames = git_refs(argv[2..]);
   if (sizeof(branchnames)==0)
      die("refs not found:%{ \"%s\"%}\n", "", argv[2..]);
   foreach (branchnames; string b; string v)
      livebranches[v] += ([b:v]);
   array commit_list = parsecommits("^"+argv[1], @indices(livebranches));
   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]]) {
               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 (mapping reached = commits[id]["Branch"]) {
            reached = reached&branchnames;
            if (sizeof(reached)>0) {
               branchnames -= reached;
	       array refs = Array.sort_array(indices(reached));
               write("          \\_ Merged into %s [%s]\n",
	               String.implode_nicely(refs),
		       git_describe(id) );
               if (sizeof(branchnames)==0)
                  exit(0);
            }
         }
      }
      m_delete(commits, id);
   }
   array refs = Array.sort_array(indices(branchnames));
   write("             Not reachable from %s\n", String.implode_nicely(refs));
}

// This can slow us down almost twice; open coding it
// into the history walk would be possible, but i'm
// not doing that for only a few 100ms gain (total)...
string git_describe(string id) {
   return (run("git", "describe", id)/"\n")[0];
}

// Given glob pattern(s) ("m?st*r") return a mapping of
// all matching existing refs (symbolic:dereferenced_id)
mapping git_refs(array patterns) {
   mapping res = ([]);
   array tags = ({});

   foreach (patterns; int i; string pattern)
      if (pattern[0..4]!="refs/")
         patterns[i] = "*/"+pattern;
      
   foreach (run("git", "show-ref", "-d")/"\n", string line) {
      array words = line/" ";
      
      if (sizeof(words)<2)
         break;
      foreach (patterns, string pattern)
         if (glob(pattern, words[1]) || glob(pattern+"/*", words[1])) {
            if (words[1][0..9]!="refs/tags/")
               res += ([ words[1] : words[0] ]);
            else
               tags += ({words[1]});
            break;
         }
   }
   
   if (sizeof(tags)) {
      foreach (run("git", "show-ref", "-d", @tags)/"\n", string line)
         if (line[sizeof(line)-3..]=="^{}") {
            array words = line/" ";
            res += ([ words[1][..sizeof(words[1])-4] : words[0] ]);
         }
   }
   
   string prefix = String.common_prefix(indices(res));
   if (prefix!="") {
      int preflen = sizeof(prefix);
      while (preflen && prefix[preflen-1]!='/')
         preflen--;
      foreach (res; string in; string val)
         res[in[preflen..]] = m_delete(res, in);
   }
   return res;
}

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'"
   ]),
});

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 object cal = Calendar.ISO.set_timezone(Calendar.Timezone.UTC);
----------------------------------------------------------------------