blame.c

   1 /*
   2  * Copyright (C) 2006, Fredrik Kuivinen <freku045@student.liu.se>
   3  */
   4
   5 #include <assert.h>
   6 #include <time.h>
   7 #include <sys/time.h>
   8 #include <math.h>
   9
  10 #include "cache.h"
  11 #include "refs.h"
  12 #include "tag.h"
  13 #include "commit.h"
  14 #include "tree.h"
  15 #include "blob.h"
  16 #include "diff.h"
  17 #include "diffcore.h"
  18 #include "revision.h"
  19 #include "xdiff-interface.h"
  20 #include "quote.h"
  21
  22 #define DEBUG 0
  23
  24 static const char blame_usage[] =
  25 "git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-S <revs-file>] [--] file [commit]\n"
  26 "  -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
  27 "  -l, --long          Show long commit SHA1 (Default: off)\n"
  28 "  -t, --time          Show raw timestamp (Default: off)\n"
  29 "  -f, --show-name     Show original filename (Default: auto)\n"
  30 "  -n, --show-number   Show original linenumber (Default: off)\n"
  31 "  -p, --porcelain     Show in a format designed for machine consumption\n"
  32 "  -S revs-file        Use revisions from revs-file instead of calling git-rev-list\n"
  33 "  -h, --help          This message";
  34
  35 static struct commit **blame_lines;
  36 static int num_blame_lines;
  37 static char *blame_contents;
  38 static int blame_len;
  39
  40 struct util_info {
  41         int *line_map;
  42         unsigned char sha1[20]; /* blob sha, not commit! */
  43         char *buf;
  44         unsigned long size;
  45         int num_lines;
  46         const char *pathname;
  47         unsigned meta_given:1;
  48
  49         void *topo_data;
  50 };
  51
  52 struct chunk {
  53         int off1, len1; /* --- */
  54         int off2, len2; /* +++ */
  55 };
  56
  57 struct patch {
  58         struct chunk *chunks;
  59         int num;
  60 };
  61
  62 static void get_blob(struct commit *commit);
  63
  64 /* Only used for statistics */
  65 static int num_get_patch;
  66 static int num_commits;
  67 static int patch_time;
  68
  69 struct blame_diff_state {
  70         struct xdiff_emit_state xm;
  71         struct patch *ret;
  72 };
  73
  74 static void process_u0_diff(void *state_, char *line, unsigned long len)
  75 {
  76         struct blame_diff_state *state = state_;
  77         struct chunk *chunk;
  78
  79         if (len < 4 || line[0] != '@' || line[1] != '@')
  80                 return;
  81
  82         if (DEBUG)
  83                 printf("chunk line: %.*s", (int)len, line);
  84         state->ret->num++;
  85         state->ret->chunks = xrealloc(state->ret->chunks,
  86                                       sizeof(struct chunk) * state->ret->num);
  87         chunk = &state->ret->chunks[state->ret->num - 1];
  88
  89         assert(!strncmp(line, "@@ -", 4));
  90
  91         if (parse_hunk_header(line, len,
  92                               &chunk->off1, &chunk->len1,
  93                               &chunk->off2, &chunk->len2)) {
  94                 state->ret->num--;
  95                 return;
  96         }
  97
  98         if (chunk->len1 == 0)
  99                 chunk->off1++;
 100         if (chunk->len2 == 0)
 101                 chunk->off2++;
 102
 103         if (chunk->off1 > 0)
 104                 chunk->off1--;
 105         if (chunk->off2 > 0)
 106                 chunk->off2--;
 107
 108         assert(chunk->off1 >= 0);
 109         assert(chunk->off2 >= 0);
 110 }
 111
 112 static struct patch *get_patch(struct commit *commit, struct commit *other)
 113 {
 114         struct blame_diff_state state;
 115         xpparam_t xpp;
 116         xdemitconf_t xecfg;
 117         mmfile_t file_c, file_o;
 118         xdemitcb_t ecb;
 119         struct util_info *info_c = (struct util_info *)commit->util;
 120         struct util_info *info_o = (struct util_info *)other->util;
 121         struct timeval tv_start, tv_end;
 122
 123         get_blob(commit);
 124         file_c.ptr = info_c->buf;
 125         file_c.size = info_c->size;
 126
 127         get_blob(other);
 128         file_o.ptr = info_o->buf;
 129         file_o.size = info_o->size;
 130
 131         gettimeofday(&tv_start, NULL);
 132
 133         xpp.flags = XDF_NEED_MINIMAL;
 134         xecfg.ctxlen = 0;
 135         xecfg.flags = 0;
 136         ecb.outf = xdiff_outf;
 137         ecb.priv = &state;
 138         memset(&state, 0, sizeof(state));
 139         state.xm.consume = process_u0_diff;
 140         state.ret = xmalloc(sizeof(struct patch));
 141         state.ret->chunks = NULL;
 142         state.ret->num = 0;
 143
 144         xdl_diff(&file_c, &file_o, &xpp, &xecfg, &ecb);
 145
 146         gettimeofday(&tv_end, NULL);
 147         patch_time += 1000000 * (tv_end.tv_sec - tv_start.tv_sec) +
 148                 tv_end.tv_usec - tv_start.tv_usec;
 149
 150         num_get_patch++;
 151         return state.ret;
 152 }
 153
 154 static void free_patch(struct patch *p)
 155 {
 156         free(p->chunks);
 157         free(p);
 158 }
 159
 160 static int get_blob_sha1_internal(const unsigned char *sha1, const char *base,
 161                                   int baselen, const char *pathname,
 162                                   unsigned mode, int stage);
 163
 164 static unsigned char blob_sha1[20];
 165 static const char *blame_file;
 166 static int get_blob_sha1(struct tree *t, const char *pathname,
 167                          unsigned char *sha1)
 168 {
 169         const char *pathspec[2];
 170         blame_file = pathname;
 171         pathspec[0] = pathname;
 172         pathspec[1] = NULL;
 173         hashclr(blob_sha1);
 174         read_tree_recursive(t, "", 0, 0, pathspec, get_blob_sha1_internal);
 175
 176         if (is_null_sha1(blob_sha1))
 177                 return -1;
 178
 179         hashcpy(sha1, blob_sha1);
 180         return 0;
 181 }
 182
 183 static int get_blob_sha1_internal(const unsigned char *sha1, const char *base,
 184                                   int baselen, const char *pathname,
 185                                   unsigned mode, int stage)
 186 {
 187         if (S_ISDIR(mode))
 188                 return READ_TREE_RECURSIVE;
 189
 190         if (strncmp(blame_file, base, baselen) ||
 191             strcmp(blame_file + baselen, pathname))
 192                 return -1;
 193
 194         hashcpy(blob_sha1, sha1);
 195         return -1;
 196 }
 197
 198 static void get_blob(struct commit *commit)
 199 {
 200         struct util_info *info = commit->util;
 201         char type[20];
 202
 203         if (info->buf)
 204                 return;
 205
 206         info->buf = read_sha1_file(info->sha1, type, &info->size);
 207
 208         assert(!strcmp(type, blob_type));
 209 }
 210
 211 /* For debugging only */
 212 static void print_patch(struct patch *p)
 213 {
 214         int i;
 215         printf("Num chunks: %d\n", p->num);
 216         for (i = 0; i < p->num; i++) {
 217                 printf("%d,%d %d,%d\n", p->chunks[i].off1, p->chunks[i].len1,
 218                        p->chunks[i].off2, p->chunks[i].len2);
 219         }
 220 }
 221
 222 #if DEBUG
 223 /* For debugging only */
 224 static void print_map(struct commit *cmit, struct commit *other)
 225 {
 226         struct util_info *util = cmit->util;
 227         struct util_info *util2 = other->util;
 228
 229         int i;
 230         int max =
 231             util->num_lines >
 232             util2->num_lines ? util->num_lines : util2->num_lines;
 233         int num;
 234
 235         for (i = 0; i < max; i++) {
 236                 printf("i: %d ", i);
 237                 num = -1;
 238
 239                 if (i < util->num_lines) {
 240                         num = util->line_map[i];
 241                         printf("%d\t", num);
 242                 }
 243                 else
 244                         printf("\t");
 245
 246                 if (i < util2->num_lines) {
 247                         int num2 = util2->line_map[i];
 248                         printf("%d\t", num2);
 249                         if (num != -1 && num2 != num)
 250                                 printf("---");
 251                 }
 252                 else
 253                         printf("\t");
 254
 255                 printf("\n");
 256         }
 257 }
 258 #endif
 259
 260 /* p is a patch from commit to other. */
 261 static void fill_line_map(struct commit *commit, struct commit *other,
 262                           struct patch *p)
 263 {
 264         struct util_info *util = commit->util;
 265         struct util_info *util2 = other->util;
 266         int *map = util->line_map;
 267         int *map2 = util2->line_map;
 268         int cur_chunk = 0;
 269         int i1, i2;
 270
 271         if (DEBUG) {
 272                 if (p->num)
 273                         print_patch(p);
 274                 printf("num lines 1: %d num lines 2: %d\n", util->num_lines,
 275                        util2->num_lines);
 276         }
 277
 278         for (i1 = 0, i2 = 0; i1 < util->num_lines; i1++, i2++) {
 279                 struct chunk *chunk = NULL;
 280                 if (cur_chunk < p->num)
 281                         chunk = &p->chunks[cur_chunk];
 282
 283                 if (chunk && chunk->off1 == i1) {
 284                         if (DEBUG && i2 != chunk->off2)
 285                                 printf("i2: %d off2: %d\n", i2, chunk->off2);
 286
 287                         assert(i2 == chunk->off2);
 288
 289                         i1--;
 290                         i2--;
 291                         if (chunk->len1 > 0)
 292                                 i1 += chunk->len1;
 293
 294                         if (chunk->len2 > 0)
 295                                 i2 += chunk->len2;
 296
 297                         cur_chunk++;
 298                 }
 299                 else {
 300                         if (i2 >= util2->num_lines)
 301                                 break;
 302
 303                         if (map[i1] != map2[i2] && map[i1] != -1) {
 304                                 if (DEBUG)
 305                                         printf("map: i1: %d %d %p i2: %d %d %p\n",
 306                                                i1, map[i1],
 307                                                (void *) (i1 != -1 ? blame_lines[map[i1]] : NULL),
 308                                                i2, map2[i2],
 309                                                (void *) (i2 != -1 ? blame_lines[map2[i2]] : NULL));
 310                                 if (map2[i2] != -1 &&
 311                                     blame_lines[map[i1]] &&
 312                                     !blame_lines[map2[i2]])
 313                                         map[i1] = map2[i2];
 314                         }
 315
 316                         if (map[i1] == -1 && map2[i2] != -1)
 317                                 map[i1] = map2[i2];
 318                 }
 319
 320                 if (DEBUG > 1)
 321                         printf("l1: %d l2: %d i1: %d i2: %d\n",
 322                                map[i1], map2[i2], i1, i2);
 323         }
 324 }
 325
 326 static int map_line(struct commit *commit, int line)
 327 {
 328         struct util_info *info = commit->util;
 329         assert(line >= 0 && line < info->num_lines);
 330         return info->line_map[line];
 331 }
 332
 333 static struct util_info *get_util(struct commit *commit)
 334 {
 335         struct util_info *util = commit->util;
 336
 337         if (util)
 338                 return util;
 339
 340         util = xcalloc(1, sizeof(struct util_info));
 341         util->num_lines = -1;
 342         commit->util = util;
 343         return util;
 344 }
 345
 346 static int fill_util_info(struct commit *commit)
 347 {
 348         struct util_info *util = commit->util;
 349
 350         assert(util);
 351         assert(util->pathname);
 352
 353         return !!get_blob_sha1(commit->tree, util->pathname, util->sha1);
 354 }
 355
 356 static void alloc_line_map(struct commit *commit)
 357 {
 358         struct util_info *util = commit->util;
 359         int i;
 360
 361         if (util->line_map)
 362                 return;
 363
 364         get_blob(commit);
 365
 366         util->num_lines = 0;
 367         for (i = 0; i < util->size; i++) {
 368                 if (util->buf[i] == '\n')
 369                         util->num_lines++;
 370         }
 371         if (util->buf[util->size - 1] != '\n')
 372                 util->num_lines++;
 373
 374         util->line_map = xmalloc(sizeof(int) * util->num_lines);
 375
 376         for (i = 0; i < util->num_lines; i++)
 377                 util->line_map[i] = -1;
 378 }
 379
 380 static void init_first_commit(struct commit *commit, const char *filename)
 381 {
 382         struct util_info *util = commit->util;
 383         int i;
 384
 385         util->pathname = filename;
 386         if (fill_util_info(commit))
 387                 die("fill_util_info failed");
 388
 389         alloc_line_map(commit);
 390
 391         util = commit->util;
 392
 393         for (i = 0; i < util->num_lines; i++)
 394                 util->line_map[i] = i;
 395 }
 396
 397 static void process_commits(struct rev_info *rev, const char *path,
 398                             struct commit **initial)
 399 {
 400         int i;
 401         struct util_info *util;
 402         int lines_left;
 403         int *blame_p;
 404         int *new_lines;
 405         int new_lines_len;
 406
 407         struct commit *commit = get_revision(rev);
 408         assert(commit);
 409         init_first_commit(commit, path);
 410
 411         util = commit->util;
 412         num_blame_lines = util->num_lines;
 413         blame_lines = xmalloc(sizeof(struct commit *) * num_blame_lines);
 414         blame_contents = util->buf;
 415         blame_len = util->size;
 416
 417         for (i = 0; i < num_blame_lines; i++)
 418                 blame_lines[i] = NULL;
 419
 420         lines_left = num_blame_lines;
 421         blame_p = xmalloc(sizeof(int) * num_blame_lines);
 422         new_lines = xmalloc(sizeof(int) * num_blame_lines);
 423         do {
 424                 struct commit_list *parents;
 425                 int num_parents;
 426                 struct util_info *util;
 427
 428                 if (DEBUG)
 429                         printf("\nProcessing commit: %d %s\n", num_commits,
 430                                sha1_to_hex(commit->object.sha1));
 431
 432                 if (lines_left == 0)
 433                         return;
 434
 435                 num_commits++;
 436                 memset(blame_p, 0, sizeof(int) * num_blame_lines);
 437                 new_lines_len = 0;
 438                 num_parents = 0;
 439                 for (parents = commit->parents;
 440                      parents != NULL; parents = parents->next)
 441                         num_parents++;
 442
 443                 if (num_parents == 0)
 444                         *initial = commit;
 445
 446                 if (fill_util_info(commit))
 447                         continue;
 448
 449                 alloc_line_map(commit);
 450                 util = commit->util;
 451
 452                 for (parents = commit->parents;
 453                      parents != NULL; parents = parents->next) {
 454                         struct commit *parent = parents->item;
 455                         struct patch *patch;
 456
 457                         if (parse_commit(parent) < 0)
 458                                 die("parse_commit error");
 459
 460                         if (DEBUG)
 461                                 printf("parent: %s\n",
 462                                        sha1_to_hex(parent->object.sha1));
 463
 464                         if (fill_util_info(parent)) {
 465                                 num_parents--;
 466                                 continue;
 467                         }
 468
 469                         patch = get_patch(parent, commit);
 470                         alloc_line_map(parent);
 471                         fill_line_map(parent, commit, patch);
 472
 473                         for (i = 0; i < patch->num; i++) {
 474                             int l;
 475                             for (l = 0; l < patch->chunks[i].len2; l++) {
 476                                 int mapped_line =
 477                                     map_line(commit, patch->chunks[i].off2 + l);
 478                                 if (mapped_line != -1) {
 479                                     blame_p[mapped_line]++;
 480                                     if (blame_p[mapped_line] == num_parents)
 481                                         new_lines[new_lines_len++] = mapped_line;
 482                                 }
 483                             }
 484                         }
 485                         free_patch(patch);
 486                 }
 487
 488                 if (DEBUG)
 489                         printf("parents: %d\n", num_parents);
 490
 491                 for (i = 0; i < new_lines_len; i++) {
 492                         int mapped_line = new_lines[i];
 493                         if (blame_lines[mapped_line] == NULL) {
 494                                 blame_lines[mapped_line] = commit;
 495                                 lines_left--;
 496                                 if (DEBUG)
 497                                         printf("blame: mapped: %d i: %d\n",
 498                                                mapped_line, i);
 499                         }
 500                 }
 501         } while ((commit = get_revision(rev)) != NULL);
 502 }
 503
 504 static int compare_tree_path(struct rev_info *revs,
 505                              struct commit *c1, struct commit *c2)
 506 {
 507         int ret;
 508         const char *paths[2];
 509         struct util_info *util = c2->util;
 510         paths[0] = util->pathname;
 511         paths[1] = NULL;
 512
 513         diff_tree_setup_paths(get_pathspec(revs->prefix, paths),
 514                               &revs->pruning);
 515         ret = rev_compare_tree(revs, c1->tree, c2->tree);
 516         diff_tree_release_paths(&revs->pruning);
 517         return ret;
 518 }
 519
 520 static int same_tree_as_empty_path(struct rev_info *revs, struct tree *t1,
 521                                    const char *path)
 522 {
 523         int ret;
 524         const char *paths[2];
 525         paths[0] = path;
 526         paths[1] = NULL;
 527
 528         diff_tree_setup_paths(get_pathspec(revs->prefix, paths),
 529                               &revs->pruning);
 530         ret = rev_same_tree_as_empty(revs, t1);
 531         diff_tree_release_paths(&revs->pruning);
 532         return ret;
 533 }
 534
 535 static const char *find_rename(struct commit *commit, struct commit *parent)
 536 {
 537         struct util_info *cutil = commit->util;
 538         struct diff_options diff_opts;
 539         const char *paths[1];
 540         int i;
 541
 542         if (DEBUG) {
 543                 printf("find_rename commit: %s ",
 544                        sha1_to_hex(commit->object.sha1));
 545                 puts(sha1_to_hex(parent->object.sha1));
 546         }
 547
 548         diff_setup(&diff_opts);
 549         diff_opts.recursive = 1;
 550         diff_opts.detect_rename = DIFF_DETECT_RENAME;
 551         paths[0] = NULL;
 552         diff_tree_setup_paths(paths, &diff_opts);
 553         if (diff_setup_done(&diff_opts) < 0)
 554                 die("diff_setup_done failed");
 555
 556         diff_tree_sha1(commit->tree->object.sha1, parent->tree->object.sha1,
 557                        "", &diff_opts);
 558         diffcore_std(&diff_opts);
 559
 560         for (i = 0; i < diff_queued_diff.nr; i++) {
 561                 struct diff_filepair *p = diff_queued_diff.queue[i];
 562
 563                 if (p->status == 'R' &&
 564                     !strcmp(p->one->path, cutil->pathname)) {
 565                         if (DEBUG)
 566                                 printf("rename %s -> %s\n",
 567                                        p->one->path, p->two->path);
 568                         return p->two->path;
 569                 }
 570         }
 571
 572         return 0;
 573 }
 574
 575 static void simplify_commit(struct rev_info *revs, struct commit *commit)
 576 {
 577         struct commit_list **pp, *parent;
 578
 579         if (!commit->tree)
 580                 return;
 581
 582         if (!commit->parents) {
 583                 struct util_info *util = commit->util;
 584                 if (!same_tree_as_empty_path(revs, commit->tree,
 585                                              util->pathname))
 586                         commit->object.flags |= TREECHANGE;
 587                 return;
 588         }
 589
 590         pp = &commit->parents;
 591         while ((parent = *pp) != NULL) {
 592                 struct commit *p = parent->item;
 593
 594                 if (p->object.flags & UNINTERESTING) {
 595                         pp = &parent->next;
 596                         continue;
 597                 }
 598
 599                 parse_commit(p);
 600                 switch (compare_tree_path(revs, p, commit)) {
 601                 case REV_TREE_SAME:
 602                         parent->next = NULL;
 603                         commit->parents = parent;
 604                         get_util(p)->pathname = get_util(commit)->pathname;
 605                         return;
 606
 607                 case REV_TREE_NEW:
 608                 {
 609                         struct util_info *util = commit->util;
 610                         if (revs->remove_empty_trees &&
 611                             same_tree_as_empty_path(revs, p->tree,
 612                                                     util->pathname)) {
 613                                 const char *new_name = find_rename(commit, p);
 614                                 if (new_name) {
 615                                         struct util_info *putil = get_util(p);
 616                                         if (!putil->pathname)
 617                                                 putil->pathname = xstrdup(new_name);
 618                                 }
 619                                 else {
 620                                         *pp = parent->next;
 621                                         continue;
 622                                 }
 623                         }
 624                 }
 625
 626                 /* fallthrough */
 627                 case REV_TREE_DIFFERENT:
 628                         pp = &parent->next;
 629                         if (!get_util(p)->pathname)
 630                                 get_util(p)->pathname =
 631                                         get_util(commit)->pathname;
 632                         continue;
 633                 }
 634                 die("bad tree compare for commit %s",
 635                     sha1_to_hex(commit->object.sha1));
 636         }
 637         commit->object.flags |= TREECHANGE;
 638 }
 639
 640 struct commit_info
 641 {
 642         char *author;
 643         char *author_mail;
 644         unsigned long author_time;
 645         char *author_tz;
 646
 647         /* filled only when asked for details */
 648         char *committer;
 649         char *committer_mail;
 650         unsigned long committer_time;
 651         char *committer_tz;
 652
 653         char *summary;
 654 };
 655
 656 static void get_ac_line(const char *inbuf, const char *what,
 657                         int bufsz, char *person, char **mail,
 658                         unsigned long *time, char **tz)
 659 {
 660         int len;
 661         char *tmp, *endp;
 662
 663         tmp = strstr(inbuf, what);
 664         if (!tmp)
 665                 goto error_out;
 666         tmp += strlen(what);
 667         endp = strchr(tmp, '\n');
 668         if (!endp)
 669                 len = strlen(tmp);
 670         else
 671                 len = endp - tmp;
 672         if (bufsz <= len) {
 673         error_out:
 674                 /* Ugh */
 675                 person = *mail = *tz = "(unknown)";
 676                 *time = 0;
 677                 return;
 678         }
 679         memcpy(person, tmp, len);
 680
 681         tmp = person;
 682         tmp += len;
 683         *tmp = 0;
 684         while (*tmp != ' ')
 685                 tmp--;
 686         *tz = tmp+1;
 687
 688         *tmp = 0;
 689         while (*tmp != ' ')
 690                 tmp--;
 691         *time = strtoul(tmp, NULL, 10);
 692
 693         *tmp = 0;
 694         while (*tmp != ' ')
 695                 tmp--;
 696         *mail = tmp + 1;
 697         *tmp = 0;
 698 }
 699
 700 static void get_commit_info(struct commit *commit, struct commit_info *ret, int detailed)
 701 {
 702         int len;
 703         char *tmp, *endp;
 704         static char author_buf[1024];
 705         static char committer_buf[1024];
 706         static char summary_buf[1024];
 707
 708         ret->author = author_buf;
 709         get_ac_line(commit->buffer, "\nauthor ",
 710                     sizeof(author_buf), author_buf, &ret->author_mail,
 711                     &ret->author_time, &ret->author_tz);
 712
 713         if (!detailed)
 714                 return;
 715
 716         ret->committer = committer_buf;
 717         get_ac_line(commit->buffer, "\ncommitter ",
 718                     sizeof(committer_buf), committer_buf, &ret->committer_mail,
 719                     &ret->committer_time, &ret->committer_tz);
 720
 721         ret->summary = summary_buf;
 722         tmp = strstr(commit->buffer, "\n\n");
 723         if (!tmp) {
 724         error_out:
 725                 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
 726                 return;
 727         }
 728         tmp += 2;
 729         endp = strchr(tmp, '\n');
 730         if (!endp)
 731                 goto error_out;
 732         len = endp - tmp;
 733         if (len >= sizeof(summary_buf))
 734                 goto error_out;
 735         memcpy(summary_buf, tmp, len);
 736         summary_buf[len] = 0;
 737 }
 738
 739 static const char *format_time(unsigned long time, const char *tz_str,
 740                                int show_raw_time)
 741 {
 742         static char time_buf[128];
 743         time_t t = time;
 744         int minutes, tz;
 745         struct tm *tm;
 746
 747         if (show_raw_time) {
 748                 sprintf(time_buf, "%lu %s", time, tz_str);
 749                 return time_buf;
 750         }
 751
 752         tz = atoi(tz_str);
 753         minutes = tz < 0 ? -tz : tz;
 754         minutes = (minutes / 100)*60 + (minutes % 100);
 755         minutes = tz < 0 ? -minutes : minutes;
 756         t = time + minutes * 60;
 757         tm = gmtime(&t);
 758
 759         strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
 760         strcat(time_buf, tz_str);
 761         return time_buf;
 762 }
 763
 764 static void topo_setter(struct commit *c, void *data)
 765 {
 766         struct util_info *util = c->util;
 767         util->topo_data = data;
 768 }
 769
 770 static void *topo_getter(struct commit *c)
 771 {
 772         struct util_info *util = c->util;
 773         return util->topo_data;
 774 }
 775
 776 static int read_ancestry(const char *graft_file,
 777                          unsigned char **start_sha1)
 778 {
 779         FILE *fp = fopen(graft_file, "r");
 780         char buf[1024];
 781         if (!fp)
 782                 return -1;
 783         while (fgets(buf, sizeof(buf), fp)) {
 784                 /* The format is just "Commit Parent1 Parent2 ...\n" */
 785                 int len = strlen(buf);
 786                 struct commit_graft *graft = read_graft_line(buf, len);
 787                 register_commit_graft(graft, 0);
 788                 if (!*start_sha1)
 789                         *start_sha1 = graft->sha1;
 790         }
 791         fclose(fp);
 792         return 0;
 793 }
 794
 795 static int lineno_width(int lines)
 796 {
 797         int i, width;
 798
 799         for (width = 1, i = 10; i <= lines + 1; width++)
 800                 i *= 10;
 801         return width;
 802 }
 803
 804 static int find_orig_linenum(struct util_info *u, int lineno)
 805 {
 806         int i;
 807
 808         for (i = 0; i < u->num_lines; i++)
 809                 if (lineno == u->line_map[i])
 810                         return i + 1;
 811         return 0;
 812 }
 813
 814 static void emit_meta(struct commit *c, int lno,
 815                       int sha1_len, int compatibility, int porcelain,
 816                       int show_name, int show_number, int show_raw_time,
 817                       int longest_file, int longest_author,
 818                       int max_digits, int max_orig_digits)
 819 {
 820         struct util_info *u;
 821         int lineno;
 822         struct commit_info ci;
 823
 824         u = c->util;
 825         lineno = find_orig_linenum(u, lno);
 826
 827         if (porcelain) {
 828                 int group_size = -1;
 829                 struct commit *cc = (lno == 0) ? NULL : blame_lines[lno-1];
 830                 if (cc != c) {
 831                         /* This is the beginning of this group */
 832                         int i;
 833                         for (i = lno + 1; i < num_blame_lines; i++)
 834                                 if (blame_lines[i] != c)
 835                                         break;
 836                         group_size = i - lno;
 837                 }
 838                 if (0 < group_size)
 839                         printf("%s %d %d %d\n", sha1_to_hex(c->object.sha1),
 840                                lineno, lno + 1, group_size);
 841                 else
 842                         printf("%s %d %d\n", sha1_to_hex(c->object.sha1),
 843                                lineno, lno + 1);
 844                 if (!u->meta_given) {
 845                         get_commit_info(c, &ci, 1);
 846                         printf("author %s\n", ci.author);
 847                         printf("author-mail %s\n", ci.author_mail);
 848                         printf("author-time %lu\n", ci.author_time);
 849                         printf("author-tz %s\n", ci.author_tz);
 850                         printf("committer %s\n", ci.committer);
 851                         printf("committer-mail %s\n", ci.committer_mail);
 852                         printf("committer-time %lu\n", ci.committer_time);
 853                         printf("committer-tz %s\n", ci.committer_tz);
 854                         printf("filename ");
 855                         if (quote_c_style(u->pathname, NULL, NULL, 0))
 856                                 quote_c_style(u->pathname, NULL, stdout, 0);
 857                         else
 858                                 fputs(u->pathname, stdout);
 859                         printf("\nsummary %s\n", ci.summary);
 860
 861                         u->meta_given = 1;
 862                 }
 863                 putchar('\t');
 864                 return;
 865         }
 866
 867         get_commit_info(c, &ci, 0);
 868         fwrite(sha1_to_hex(c->object.sha1), sha1_len, 1, stdout);
 869         if (compatibility) {
 870                 printf("\t(%10s\t%10s\t%d)", ci.author,
 871                        format_time(ci.author_time, ci.author_tz,
 872                                    show_raw_time),
 873                        lno + 1);
 874         }
 875         else {
 876                 if (show_name)
 877                         printf(" %-*.*s", longest_file, longest_file,
 878                                u->pathname);
 879                 if (show_number)
 880                         printf(" %*d", max_orig_digits,
 881                                lineno);
 882                 printf(" (%-*.*s %10s %*d) ",
 883                        longest_author, longest_author, ci.author,
 884                        format_time(ci.author_time, ci.author_tz,
 885                                    show_raw_time),
 886                        max_digits, lno + 1);
 887         }
 888 }
 889
 890 int main(int argc, const char **argv)
 891 {
 892         int i;
 893         struct commit *initial = NULL;
 894         unsigned char sha1[20], *sha1_p = NULL;
 895
 896         const char *filename = NULL, *commit = NULL;
 897         char filename_buf[256];
 898         int sha1_len = 8;
 899         int compatibility = 0;
 900         int show_raw_time = 0;
 901         int options = 1;
 902         struct commit *start_commit;
 903
 904         const char *args[10];
 905         struct rev_info rev;
 906
 907         struct commit_info ci;
 908         const char *buf;
 909         int max_digits, max_orig_digits;
 910         int longest_file, longest_author, longest_file_lines;
 911         int show_name = 0;
 912         int show_number = 0;
 913         int porcelain = 0;
 914
 915         const char *prefix = setup_git_directory();
 916         git_config(git_default_config);
 917
 918         for (i = 1; i < argc; i++) {
 919                 if (options) {
 920                         if (!strcmp(argv[i], "-h") ||
 921                            !strcmp(argv[i], "--help"))
 922                                 usage(blame_usage);
 923                         if (!strcmp(argv[i], "-l") ||
 924                             !strcmp(argv[i], "--long")) {
 925                                 sha1_len = 40;
 926                                 continue;
 927                         }
 928                         if (!strcmp(argv[i], "-c") ||
 929                             !strcmp(argv[i], "--compatibility")) {
 930                                 compatibility = 1;
 931                                 continue;
 932                         }
 933                         if (!strcmp(argv[i], "-t") ||
 934                             !strcmp(argv[i], "--time")) {
 935                                 show_raw_time = 1;
 936                                 continue;
 937                         }
 938                         if (!strcmp(argv[i], "-S")) {
 939                                 if (i + 1 < argc &&
 940                                     !read_ancestry(argv[i + 1], &sha1_p)) {
 941                                         compatibility = 1;
 942                                         i++;
 943                                         continue;
 944                                 }
 945                                 usage(blame_usage);
 946                         }
 947                         if (!strcmp(argv[i], "-f") ||
 948                             !strcmp(argv[i], "--show-name")) {
 949                                 show_name = 1;
 950                                 continue;
 951                         }
 952                         if (!strcmp(argv[i], "-n") ||
 953                             !strcmp(argv[i], "--show-number")) {
 954                                 show_number = 1;
 955                                 continue;
 956                         }
 957                         if (!strcmp(argv[i], "-p") ||
 958                             !strcmp(argv[i], "--porcelain")) {
 959                                 porcelain = 1;
 960                                 sha1_len = 40;
 961                                 show_raw_time = 1;
 962                                 continue;
 963                         }
 964                         if (!strcmp(argv[i], "--")) {
 965                                 options = 0;
 966                                 continue;
 967                         }
 968                         if (argv[i][0] == '-')
 969                                 usage(blame_usage);
 970                         options = 0;
 971                 }
 972
 973                 if (!options) {
 974                         if (!filename)
 975                                 filename = argv[i];
 976                         else if (!commit)
 977                                 commit = argv[i];
 978                         else
 979                                 usage(blame_usage);
 980                 }
 981         }
 982
 983         if (!filename)
 984                 usage(blame_usage);
 985         if (commit && sha1_p)
 986                 usage(blame_usage);
 987         else if (!commit)
 988                 commit = "HEAD";
 989
 990         if (prefix)
 991                 sprintf(filename_buf, "%s%s", prefix, filename);
 992         else
 993                 strcpy(filename_buf, filename);
 994         filename = filename_buf;
 995
 996         if (!sha1_p) {
 997                 if (get_sha1(commit, sha1))
 998                         die("get_sha1 failed, commit '%s' not found", commit);
 999                 sha1_p = sha1;
1000         }
1001         start_commit = lookup_commit_reference(sha1_p);
1002         get_util(start_commit)->pathname = filename;
1003         if (fill_util_info(start_commit)) {
1004                 printf("%s not found in %s\n", filename, commit);
1005                 return 1;
1006         }
1007
1008         init_revisions(&rev, setup_git_directory());
1009         rev.remove_empty_trees = 1;
1010         rev.topo_order = 1;
1011         rev.prune_fn = simplify_commit;
1012         rev.topo_setter = topo_setter;
1013         rev.topo_getter = topo_getter;
1014         rev.parents = 1;
1015         rev.limited = 1;
1016
1017         commit_list_insert(start_commit, &rev.commits);
1018
1019         args[0] = filename;
1020         args[1] = NULL;
1021         diff_tree_setup_paths(args, &rev.pruning);
1022         prepare_revision_walk(&rev);
1023         process_commits(&rev, filename, &initial);
1024
1025         for (i = 0; i < num_blame_lines; i++)
1026                 if (!blame_lines[i])
1027                         blame_lines[i] = initial;
1028
1029         buf = blame_contents;
1030         max_digits = lineno_width(num_blame_lines);
1031
1032         longest_file = 0;
1033         longest_author = 0;
1034         longest_file_lines = 0;
1035         for (i = 0; i < num_blame_lines; i++) {
1036                 struct commit *c = blame_lines[i];
1037                 struct util_info *u;
1038                 u = c->util;
1039
1040                 if (!show_name && strcmp(filename, u->pathname))
1041                         show_name = 1;
1042                 if (longest_file < strlen(u->pathname))
1043                         longest_file = strlen(u->pathname);
1044                 if (longest_file_lines < u->num_lines)
1045                         longest_file_lines = u->num_lines;
1046                 get_commit_info(c, &ci, 0);
1047                 if (longest_author < strlen(ci.author))
1048                         longest_author = strlen(ci.author);
1049         }
1050
1051         max_orig_digits = lineno_width(longest_file_lines);
1052
1053         for (i = 0; i < num_blame_lines; i++) {
1054                 emit_meta(blame_lines[i], i,
1055                           sha1_len, compatibility, porcelain,
1056                           show_name, show_number, show_raw_time,
1057                           longest_file, longest_author,
1058                           max_digits, max_orig_digits);
1059
1060                 if (i == num_blame_lines - 1) {
1061                         fwrite(buf, blame_len - (buf - blame_contents),
1062                                1, stdout);
1063                         if (blame_contents[blame_len-1] != '\n')
1064                                 putc('\n', stdout);
1065                 }
1066                 else {
1067                         char *next_buf = strchr(buf, '\n') + 1;
1068                         fwrite(buf, next_buf - buf, 1, stdout);
1069                         buf = next_buf;
1070                 }
1071         }
1072
1073         if (DEBUG) {
1074                 printf("num get patch: %d\n", num_get_patch);
1075                 printf("num commits: %d\n", num_commits);
1076                 printf("patch time: %f\n", patch_time / 1000000.0);
1077                 printf("initial: %s\n", sha1_to_hex(initial->object.sha1));
1078         }
1079
1080         return 0;
1081 }