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