git-show-merge-path

   1 #! /usr/bin/env pike
   2 // git-show-merge-path <rev> [refs-glob ...]
   3 #define VERSION "2.4"
   4 // git-show-merge-path can tell /if/, /how/ and /when/ a change became visible
   5 // from a certain branch or tag. Or a few hundred thereof.
   6 // Will show all external merge commits starting at <rev> until
   7 // this commit appears on the specified branches. When that happens
   8 // "Appears in <branchlist>" is printed. If <rev> is still
   9 // unreachable from some of the branches then the search continues.
  10 //
  11 // Usage:
  12 //
  13 // ### Show which refs (branches/tags) contain the most recent commit ("HEAD"):
  14 // $ git-show-merge-path
  15 // 99bd348af8af
  16 //           \_ Appears in heads/as/ml-hpet-35
  17 //              Not reachable from 468 refs (use -v option to show them all)
  18 //
  19 // ### Show all refs that have a particular commit:
  20 // $ git-show-merge-path 94f6da84e80c
  21 // 94f6da84e80c x86, vmware: Preset lpj values when on VMware.         100813 20:30
  22 //           \_ Appears in heads/stable/2.6.35.y, remotes/2.6.35.y/HEAD, remotes/2.6.35.y/master, tags/v2.6.35.2 and tags/v2.6.35.3
  23 //              Not reachable from 464 refs (use -v option to show them all)
  24 //
  25 // ### Show all tags that contain a commit:
  26 // $ git-show-merge-path be4a4b6a5d2f7639 tags
  27 // 83163244f845 M: 'master'@$KO/linville/wireless-next-2.6 into for-da 100505 20:14
  28 // 2861a185e3ac M: 'for-davem'@$KO/linville/wireless-next-2.6          100505 22:09
  29 // 1e4b1057121b M: 'master' of /repos/git/net-next-2.6                 100510 16:39
  30 // f8965467f366 M: $KO/davem/net-next-2.6                              100521 04:04
  31 //           \_ Appears in 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
  32 //              Not reachable from 308 refs (use -v option to show them all)
  33 //
  34 // Other exmaples:
  35 //
  36 //
  37 // $ git-show-merge-path <commit> heads    # checks all local branches
  38 // $ git-show-merge-path <commit> tags     # checks all tags
  39 // $ git-show-merge-path <commit> heads/as # checks all local branches named 'as/...'
  40 // $ git-show-merge-path <commit> remotes/name
  41 //                                         # checks all refs of the named remote
  42 // $ git-show-merge-path <commit> remotes  # checks all refs of all remotes
  43 // $ git-show-merge-path <commit> heads/master
  44 //                                         # checks the local 'master' branch
  45 // $ git-show-merge-path <commit> master   # checks all 'master' branches
  46 //                                         # (incl. remotes etc)
  47 // $ git-show-merge-path <commit> 'doh*'   # checks all branches named 'doh...'
  48 // $ git-show-merge-path <commit> 'tags/v2.*' # checks all tags beginning w/ "v2."
  49 // $ git-show-merge-path <commit> '*'      # checks every reference it finds
  50 // $ git-show-merge-path <commit> refs/heads/master # for nonhumans, or situations
  51 //                                         # where the DWIM approach fails.
  52 //
  53 // Note that the ref names it prints are simplified; if unsure, do not
  54 // rely on the DWIM target selection, just give it a full "refs/..." name.
  55 //
  56 // Options:
  57 // -g   Turns on "magic" fast-forward detection. Not reliable, so always run this
  58 //      script without this option first, and compare the '-g' results later.
  59 // -g2  Even more magic. Works best when you request only refs that are all
  60 //      reachable from the commit in question, as this will prevent uninteresting
  61 //      merges (past the real merge point) from being shown. (IOW pick one of the
  62 //      refs printed after the last merge point shown w/o '-g2')
  63 //      Usuful to easily dig out a little bit more info, w/o having to look at the
  64 //      rest of the history.
  65 // -d   git-describe the shown commits; off by default as it's a huge perf hit.
  66
  67
  68 #define die(a...) exit(1, "Aborting; %s"+a)
  69
  70 static mapping commits = ([]);
  71
  72 #define ismerge(c) (sizeof( (c)["parent"] )>1)
  73
  74 void pp_commit(string id) {
  75    mapping c = commits[id];
  76
  77    if (!options["guessff"] || !c )
  78       return;
  79
  80    if (c["parent"] && sizeof(c["parent"])==2) {
  81       string b0, b1;
  82
  83       foreach (mergesub, string form)
  84          if (sscanf(c[""][1], form, b0, b1)==3)
  85             break;
  86       if (!b0 || !b1) {
  87          foreach (mmergesub, string form)
  88             if (sscanf(c[""][1], form, b0)==2)
  89                break;
  90          b1 = "master";
  91       }
  92
  93       if (b0 && b1) {
  94          if ((int)options["guessff"]>=2) {
  95             if (b0!="master") {
  96                c["Branch"] += (["$"+b0:0]);
  97                commits[ c["parent"][0] ]["Branch"] += (["$"+b0:0]);
  98                extrabranches = (["$"+b0:0]) + extrabranches;
  99             }
 100             if (b1!="master") {
 101                c["Branch"] += (["$"+b1:0]);
 102                commits[ c["parent"][0] ]["Branch"] += (["$"+b1:0]);
 103                extrabranches = (["$"+b1:0]) + extrabranches;
 104             }
 105
 106             if (c["Branch"]) {
 107                mapping bm = (["$"+b0:0])&c["Branch"];
 108
 109                if (sizeof(bm) /*&& sizeof((["$"+b1:0])&c["Branch"])*/) {
 110                   commits[ c["parent"][0] ]["Branch"] -= bm;
 111
 112                   if (!commits[ c["parent"][1] ])
 113                      commits[ c["parent"][1] ] = ([ "Branch" : bm ]);
 114                   else
 115                      commits[ c["parent"][1] ]["Branch"] += bm;
 116                }
 117             }
 118          }
 119
 120          if (!c["Branch"])
 121             return;
 122
 123          mapping bm = ([b0:0])&c["Branch"];
 124
 125          if (sizeof(bm) && sizeof(([b1:0])&c["Branch"])) {
 126             if (options["verbose"])
 127                werror(" # Undoing FF @ %.12s %s\n", id, squeeze_subject(c[""][1]));
 128
 129             commits[ c["parent"][0] ]["Branch"] -= bm;
 130
 131             if (!commits[ c["parent"][1] ])
 132                commits[ c["parent"][1] ] = ([ "Branch" : bm ]);
 133             else
 134                commits[ c["parent"][1] ]["Branch"] += bm;
 135          }
 136       }
 137       else
 138          if (options["verbose"])
 139             werror(" # Unsupported merge subject %O\n", c[""][1]);
 140    }
 141 }
 142
 143 array parsecommits(string ... delim) {
 144    array res = ({});
 145    string id;
 146    array lines = run("git", "rev-list", "--format=raw", "--ancestry-path",
 147                                "--boundary", "--date-order", @delim)/"\n";
 148    foreach (lines, string line) {
 149       array words = line/" ";
 150       string h = words[0];
 151       if (h=="commit") {
 152          pp_commit(id);
 153
 154          id = words[1];
 155          if (id[0]=='-') {
 156             if (id[1..]==commit_id)
 157                id = id[1..];
 158          }
 159          else
 160             res += ({id});
 161          if (!commits[id])
 162             commits[id] = ([]);
 163       } else if (h=="") {
 164          if (commits[id])
 165             commits[id][""] += ({line});
 166       }
 167       else {
 168          if (h=="parent") {
 169             string parent = words[1];
 170             if (!commits[parent])
 171                commits[parent] = ([]);
 172             if (!commits[id]["parent"]) // first parent?
 173                if (commits[id]["Branch"]) {
 174                   if (!commits[parent]["Branch"])
 175                      commits[parent]["Branch"] = ([]);
 176                   commits[parent]["Branch"] += commits[id]["Branch"];
 177                }
 178          }
 179          commits[id][h] += words[1..];
 180       }
 181    }
 182    pp_commit(id);
 183    return res;
 184 }
 185
 186 static mapping desc = ([]);
 187
 188 static mapping branchnames = ([]);    // name : id
 189 static mapping extrabranches = ([]);  // name : id
 190
 191 static mapping options = ([]);;
 192 static array option_array = ({
 193    ({ "guessff",  Getopt.MAY_HAVE_ARG, ({"-g"}) }),
 194    ({ "describe", Getopt.MAY_HAVE_ARG, ({"-d", "--describe"}) }),
 195    ({ "verbose",  Getopt.MAY_HAVE_ARG, ({"-v", "--verbose"}) }),
 196    ({ "version",  Getopt.NO_ARG,       ({"-V", "--version"}) }),
 197    ({ "help",     Getopt.NO_ARG,       ({"-h", "--help"}) }),
 198 });
 199 void show_help(string arg0) {
 200    string t =
 201    arg0+" [<rev>] [<refs-glob> ...]\n"
 202    "Options:\n"
 203    " -d, --describe   Show tags preceding commits (slower)\n"
 204    " -g               Extract extra information from merge subjects\n"
 205    " -g2              Extract extra branch names from merge subjects\n"
 206    " -v, --verbose    Show more information about what's happening\n"
 207    " -V, --version    Show version information\n"
 208    " -h, --help       Show this help information\n"
 209    ;
 210    write(t);
 211    exit(0);
 212 }
 213
 214 static string commit_id;
 215
 216 int main(int argc, array argv) {
 217    array oa = Getopt.find_all_options(argv, option_array);
 218    foreach (oa, array a)
 219       options += ([a[0]:a[1]]);
 220    argv = Getopt.get_args(argv);
 221    if (options["version"]) { write(basename(argv[0])+" v" VERSION "\n"); exit(0); }
 222    if (options["help"])    show_help(basename(argv[0]));
 223    if (sizeof(argv)==1)
 224       argv += ({"HEAD"});
 225    if (sizeof(argv)==2)
 226       argv += ({"*"});
 227    commit_id = (run("git", "rev-parse", argv[1])/"\n")[0];
 228    branchnames = git_refs(argv[2..]);
 229    if (sizeof(branchnames)==0)
 230       die("refs not found:%{ \"%s\"%}\n", "", argv[2..]);
 231    foreach (branchnames; string b; string id)
 232       if (commits[id])
 233          commits[id]["Branch"] += ([b:id]);
 234       else
 235          commits[id] = ([ "Branch" : ([b:id]) ]);
 236    array commit_list = parsecommits("^"+commit_id, @values(branchnames));
 237    commit_list += ({commit_id});
 238    commit_list = reverse(commit_list);
 239    desc[commit_id] = 1;
 240    foreach (commit_list, string id) {
 241       mapping c = commits[id];
 242       if (!c)
 243          continue;
 244       if (commits[id]["parent"]) {
 245          foreach (commits[id]["parent"], string parent)
 246             if (desc[parent])
 247                 desc[id] = 1;
 248          if (ismerge(commits[id]))
 249             if (!desc[commits[id]["parent"][0]])
 250                printidline(id);
 251       }
 252       mapping br = commits[id]["Branch"];
 253       if (br) {
 254          mapping reached = br&(branchnames|extrabranches);
 255          if (sizeof(reached)>0) {
 256             array refs = Array.sort_array(indices(reached&branchnames));
 257             if (sizeof(refs)) {
 258                printidline(id);
 259                flush("          \\_ Appears in %s%s\n",
 260                        String.implode_nicely(refs), git_describe(id) );
 261             }
 262             branchnames -= reached;
 263             if (sizeof(branchnames)==0)
 264                exit(0);
 265             refs = Array.sort_array(indices(reached&extrabranches));
 266             if (sizeof(refs)) {
 267                printidline(id);
 268                flush("          \\_ Appears in %s%s\n",
 269                        String.implode_nicely(refs), git_describe(id) );
 270             }
 271             extrabranches -= reached;
 272          }
 273       }
 274       m_delete(commits, id);
 275    }
 276    array refs = Array.sort_array(indices(branchnames));
 277    if (options["verbose"] || sizeof(refs)<10)
 278       write("             Not reachable from %s\n", String.implode_nicely(refs));
 279    else
 280       write("             Not reachable from %d refs (use -v option to show them all)\n",
 281                sizeof(refs));
 282 }
 283
 284 static array outlines = ({});
 285 static mapping shown = ([]);
 286
 287 void printidline(string id) {
 288   int comtime = commits[id]["committer"] && (int)commits[id]["committer"][-2];
 289   string subj = " ";
 290   if (shown[id])
 291      return;
 292   shown[id] = 1;
 293   if (commits[id][""])
 294      subj = commits[id][""][1];
 295   outlines += ({
 296      sprintf("%.12s %-54.54s %.12s\n", id,
 297          squeeze_subject(subj),
 298          comtime?cal->Second(comtime)->format_time_xshort():"")
 299       });
 300 }
 301 void flush(string fmt, string ... args) {
 302    write(outlines*"");
 303    write(fmt, @args);
 304    outlines = ({});
 305 }
 306
 307 string git_describe(string id) {
 308    if (!options["describe"])
 309       return "";
 310    string res = (tryrun("git", "describe", id)/"\n")[0];
 311    if (res=="")
 312       res = (tryrun("git", "describe", "--tags", id)/"\n")[0];
 313    return " ["+res+"]";
 314 }
 315
 316 // Given glob pattern(s) ("m?st*r") return a mapping of
 317 // all matching existing refs (symbolic:dereferenced_id)
 318 mapping git_refs(array patterns) {
 319    mapping res = ([]);
 320    array tags = ({});
 321
 322    foreach (patterns; int i; string pattern)
 323       if (pattern[0..4]!="refs/")
 324          patterns[i] = "*/"+pattern;
 325
 326    foreach (run("git", "show-ref")/"\n", string line) {
 327       array words = line/" ";
 328
 329       if (sizeof(words)<2)
 330          break;
 331       foreach (patterns, string pattern)
 332          if (glob(pattern, words[1]) || glob(pattern+"/*", words[1])) {
 333             if (words[1][0..9]!="refs/tags/")
 334                res += ([ words[1] : words[0] ]);
 335             else
 336                tags += ({words[1]});
 337             break;
 338          }
 339    }
 340    if (sizeof(tags)) {
 341       foreach (run("git", "show-ref", "-d", @tags)/"\n", string line) {
 342          if (line=="")
 343             break;
 344          array words = line/" ";
 345          if (line[sizeof(line)-3..]=="^{}")
 346             res += ([ words[1][..sizeof(words[1])-4] : words[0] ]);
 347          else // Could be a lightweight tag.
 348             if (!res[words[1]])
 349                res += ([ words[1] : words[0] ]);
 350       }
 351    }
 352    string prefix = String.common_prefix(indices(res));
 353    if (prefix!="") {
 354       int preflen = sizeof(prefix);
 355       while (preflen && prefix[preflen-1]!='/')
 356          preflen--;
 357       foreach (res; string in; string val)
 358          res[in[preflen..]] = m_delete(res, in);
 359    }
 360    return res;
 361 }
 362
 363 string squeeze_subject(string subject) {
 364    subject = String.trim_all_whites(subject);
 365    subject = String.expand_tabs(subject);
 366    foreach (sub_from_to, mapping m)
 367       subject = replace(subject, m);
 368    return subject;
 369 }
 370
 371 static array(mapping) sub_from_to =
 372 ({
 373    ([
 374       "Merge branch " : "Merge ",
 375       "Merge remote branch " : "Merge ",
 376       "Merge branches " : "MM:",
 377    ]),
 378    ([
 379       "Merge " : "M: ",
 380       "' of git:": "'@git:",
 381       "' into ": "' => ",
 382    ]),
 383    ([
 384        "git://git.kernel.org/pub/scm/linux/kernel/git/" : "$KO/",
 385        "master.kernel.org:/pub/scm/linux/kernel/git/" : "$KO/",
 386        "commit '" : "C'"
 387    ]),
 388 });
 389
 390 static array mergesub =
 391 ({
 392    "%*[ ]Merge branch '%s' into %s",
 393    "%*[ ]Merge remote branch '%s' into %s",
 394
 395    "%*[ ]Merge commit '%s' into %s",      // Hmm.
 396    "%*[ ]Merge tag '%s' into %s",         // Hmm^2.
 397    "%*[ ]Merge git://%s into %s",
 398    "%*[ ]Merge branch %s into %s",
 399 });
 400
 401 static array mmergesub =
 402 ({
 403    "%*[ ]Merge branch '%s'",
 404    "%*[ ]Merge commit '%s'",              // Hmm.
 405    // project-specific
 406    "%*[ ]Merge git://git.kernel.org/pub/scm/linux/kernel/git/%s",
 407    // Scary? This is here for mostly historical reasons and really old merges:
 408    "%*[ ]Merge ssh://master.kernel.org/pub/scm/linux/kernel/git/%s",
 409    "%*[ ]Merge master.kernel.org:/pub/scm/linux/kernel/git/%s",
 410    "%*[ ]Merge master.kernel.org:/home/%s",
 411    "%*[ ]Merge with /pub/scm/linux/kernel/git/%s",
 412    "%*[ ]Merge with git+ssh://master.kernel.org/pub/scm/linux/kernel/git/%s",
 413    "%*[ ]Merge with ssh://master.kernel.org/pub/scm/linux/kernel/git/%s",
 414    "%*[ ]Merge with http://kernel.org/pub/scm/linux/kernel/git/%s",
 415    "%*[ ]Merge with rsync://rsync.kernel.org/pub/scm/linux/kernel/git/%s",
 416    "%*[ ]Merge of rsync://rsync.kernel.org/pub/scm/linux/kernel/git/%s",
 417    "%*[ ]Merge rsync://rsync.kernel.org/pub/scm/linux/kernel/git/%s",
 418    "%*[ ]Merge with master.kernel.org:/pub/scm/linux/kernel/git/%s",
 419    "%*[ ]Merge of master.kernel.org:/pub/scm/linux/kernel/git/%s",
 420    "%*[ ]Merge of master.kernel.org:/home/%s",
 421    "%*[ ]Automatic merge of rsync://rsync.kernel.org/pub/scm/linux/kernel/git/%s",
 422    "%*[ ]Automatic merge of master.kernel.org:/home/%s",
 423    "%*[ ]Automatic merge of master.kernel.org:/pub/scm/linux/kernel/git/%s",
 424    "%*[ ]Merge HEAD from master.kernel.org:/pub/scm/linux/kernel/git/%s",
 425
 426    // Too generic? Comment them out and run with "-g -v" to look
 427    // for better candidates.
 428    "%*[ ]Merge git://%[^' ]",
 429    //"%*[ ]Merge %[^' ]",
 430 });
 431
 432 string run(string ... cmdline) {
 433 #if __REAL_MAJOR__<7 || __REAL_MAJOR__==7 && __REAL_MINOR__<8
 434    string s = Process.popen(cmdline*" ");
 435    if (s=="")
 436       die("\n", cmdline*" ");
 437    return s;
 438 #else
 439    mapping r;
 440    mixed e = catch { r = Process.run( ({@cmdline}) ); };
 441    if (e || r["exitcode"])
 442       die("", e?e:r["stderr"]);
 443    return r["stdout"];
 444 #endif
 445 }
 446
 447 string tryrun(string ... cmdline) {
 448 #if __REAL_MAJOR__<7 || __REAL_MAJOR__==7 && __REAL_MINOR__<8
 449    return Process.popen(cmdline*" " + " 2>/dev/null");
 450 #else
 451    mapping r;
 452    mixed e = catch { r = Process.run( ({@cmdline}) ); };
 453    if (e || r["exitcode"])
 454       return "";
 455    return r["stdout"];
 456 #endif
 457 }
 458
 459 static object cal = Calendar.ISO.set_timezone(Calendar.Timezone.UTC);