git.oblomov.eu Git - git/blob - builtin-blame.c

   1 /*
   2  * Pickaxe
   3  *
   4  * Copyright (c) 2006, Junio C Hamano
   5  */
   6
   7 #include "cache.h"
   8 #include "builtin.h"
   9 #include "blob.h"
  10 #include "commit.h"
  11 #include "tag.h"
  12 #include "tree-walk.h"
  13 #include "diff.h"
  14 #include "diffcore.h"
  15 #include "revision.h"
  16 #include "quote.h"
  17 #include "xdiff-interface.h"
  18
  19 static char blame_usage[] =
  20 "git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n"
  21 "  -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
  22 "  -b                  Show blank SHA-1 for boundary commits (Default: off)\n"
  23 "  -l, --long          Show long commit SHA1 (Default: off)\n"
  24 "  --root              Do not treat root commits as boundaries (Default: off)\n"
  25 "  -t, --time          Show raw timestamp (Default: off)\n"
  26 "  -f, --show-name     Show original filename (Default: auto)\n"
  27 "  -n, --show-number   Show original linenumber (Default: off)\n"
  28 "  -p, --porcelain     Show in a format designed for machine consumption\n"
  29 "  -L n,m              Process only line range n,m, counting from 1\n"
  30 "  -M, -C              Find line movements within and across files\n"
  31 "  --incremental       Show blame entries as we find them, incrementally\n"
  32 "  -S revs-file        Use revisions from revs-file instead of calling git-rev-list\n";
  33
  34 static int longest_file;
  35 static int longest_author;
  36 static int max_orig_digits;
  37 static int max_digits;
  38 static int max_score_digits;
  39 static int show_root;
  40 static int blank_boundary;
  41 static int incremental;
  42
  43 #ifndef DEBUG
  44 #define DEBUG 0
  45 #endif
  46
  47 /* stats */
  48 static int num_read_blob;
  49 static int num_get_patch;
  50 static int num_commits;
  51
  52 #define PICKAXE_BLAME_MOVE              01
  53 #define PICKAXE_BLAME_COPY              02
  54 #define PICKAXE_BLAME_COPY_HARDER       04
  55
  56 /*
  57  * blame for a blame_entry with score lower than these thresholds
  58  * is not passed to the parent using move/copy logic.
  59  */
  60 static unsigned blame_move_score;
  61 static unsigned blame_copy_score;
  62 #define BLAME_DEFAULT_MOVE_SCORE        20
  63 #define BLAME_DEFAULT_COPY_SCORE        40
  64
  65 /* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
  66 #define METAINFO_SHOWN          (1u<<12)
  67 #define MORE_THAN_ONE_PATH      (1u<<13)
  68
  69 /*
  70  * One blob in a commit that is being suspected
  71  */
  72 struct origin {
  73         int refcnt;
  74         struct commit *commit;
  75         mmfile_t file;
  76         unsigned char blob_sha1[20];
  77         char path[FLEX_ARRAY];
  78 };
  79
  80 static char *fill_origin_blob(struct origin *o, mmfile_t *file)
  81 {
  82         if (!o->file.ptr) {
  83                 char type[10];
  84                 num_read_blob++;
  85                 file->ptr = read_sha1_file(o->blob_sha1, type,
  86                                            (unsigned long *)(&(file->size)));
  87                 o->file = *file;
  88         }
  89         else
  90                 *file = o->file;
  91         return file->ptr;
  92 }
  93
  94 static inline struct origin *origin_incref(struct origin *o)
  95 {
  96         if (o)
  97                 o->refcnt++;
  98         return o;
  99 }
 100
 101 static void origin_decref(struct origin *o)
 102 {
 103         if (o && --o->refcnt <= 0) {
 104                 if (o->file.ptr)
 105                         free(o->file.ptr);
 106                 memset(o, 0, sizeof(*o));
 107                 free(o);
 108         }
 109 }
 110
 111 struct blame_entry {
 112         struct blame_entry *prev;
 113         struct blame_entry *next;
 114
 115         /* the first line of this group in the final image;
 116          * internally all line numbers are 0 based.
 117          */
 118         int lno;
 119
 120         /* how many lines this group has */
 121         int num_lines;
 122
 123         /* the commit that introduced this group into the final image */
 124         struct origin *suspect;
 125
 126         /* true if the suspect is truly guilty; false while we have not
 127          * checked if the group came from one of its parents.
 128          */
 129         char guilty;
 130
 131         /* the line number of the first line of this group in the
 132          * suspect's file; internally all line numbers are 0 based.
 133          */
 134         int s_lno;
 135
 136         /* how significant this entry is -- cached to avoid
 137          * scanning the lines over and over
 138          */
 139         unsigned score;
 140 };
 141
 142 struct scoreboard {
 143         /* the final commit (i.e. where we started digging from) */
 144         struct commit *final;
 145
 146         const char *path;
 147
 148         /* the contents in the final; pointed into by buf pointers of
 149          * blame_entries
 150          */
 151         const char *final_buf;
 152         unsigned long final_buf_size;
 153
 154         /* linked list of blames */
 155         struct blame_entry *ent;
 156
 157         /* look-up a line in the final buffer */
 158         int num_lines;
 159         int *lineno;
 160 };
 161
 162 static int cmp_suspect(struct origin *a, struct origin *b)
 163 {
 164         int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);
 165         if (cmp)
 166                 return cmp;
 167         return strcmp(a->path, b->path);
 168 }
 169
 170 #define cmp_suspect(a, b) ( ((a)==(b)) ? 0 : cmp_suspect(a,b) )
 171
 172 static void sanity_check_refcnt(struct scoreboard *);
 173
 174 static void coalesce(struct scoreboard *sb)
 175 {
 176         struct blame_entry *ent, *next;
 177
 178         for (ent = sb->ent; ent && (next = ent->next); ent = next) {
 179                 if (!cmp_suspect(ent->suspect, next->suspect) &&
 180                     ent->guilty == next->guilty &&
 181                     ent->s_lno + ent->num_lines == next->s_lno) {
 182                         ent->num_lines += next->num_lines;
 183                         ent->next = next->next;
 184                         if (ent->next)
 185                                 ent->next->prev = ent;
 186                         origin_decref(next->suspect);
 187                         free(next);
 188                         ent->score = 0;
 189                         next = ent; /* again */
 190                 }
 191         }
 192
 193         if (DEBUG) /* sanity */
 194                 sanity_check_refcnt(sb);
 195 }
 196
 197 static struct origin *make_origin(struct commit *commit, const char *path)
 198 {
 199         struct origin *o;
 200         o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
 201         o->commit = commit;
 202         o->refcnt = 1;
 203         strcpy(o->path, path);
 204         return o;
 205 }
 206
 207 static struct origin *get_origin(struct scoreboard *sb,
 208                                  struct commit *commit,
 209                                  const char *path)
 210 {
 211         struct blame_entry *e;
 212
 213         for (e = sb->ent; e; e = e->next) {
 214                 if (e->suspect->commit == commit &&
 215                     !strcmp(e->suspect->path, path))
 216                         return origin_incref(e->suspect);
 217         }
 218         return make_origin(commit, path);
 219 }
 220
 221 static int fill_blob_sha1(struct origin *origin)
 222 {
 223         unsigned mode;
 224         char type[10];
 225
 226         if (!is_null_sha1(origin->blob_sha1))
 227                 return 0;
 228         if (get_tree_entry(origin->commit->object.sha1,
 229                            origin->path,
 230                            origin->blob_sha1, &mode))
 231                 goto error_out;
 232         if (sha1_object_info(origin->blob_sha1, type, NULL) ||
 233             strcmp(type, blob_type))
 234                 goto error_out;
 235         return 0;
 236  error_out:
 237         hashclr(origin->blob_sha1);
 238         return -1;
 239 }
 240
 241 static struct origin *find_origin(struct scoreboard *sb,
 242                                   struct commit *parent,
 243                                   struct origin *origin)
 244 {
 245         struct origin *porigin = NULL;
 246         struct diff_options diff_opts;
 247         const char *paths[2];
 248
 249         if (parent->util) {
 250                 /* This is a freestanding copy of origin and not
 251                  * refcounted.
 252                  */
 253                 struct origin *cached = parent->util;
 254                 if (!strcmp(cached->path, origin->path)) {
 255                         porigin = get_origin(sb, parent, cached->path);
 256                         if (porigin->refcnt == 1)
 257                                 hashcpy(porigin->blob_sha1, cached->blob_sha1);
 258                         return porigin;
 259                 }
 260                 /* otherwise it was not very useful; free it */
 261                 free(parent->util);
 262                 parent->util = NULL;
 263         }
 264
 265         /* See if the origin->path is different between parent
 266          * and origin first.  Most of the time they are the
 267          * same and diff-tree is fairly efficient about this.
 268          */
 269         diff_setup(&diff_opts);
 270         diff_opts.recursive = 1;
 271         diff_opts.detect_rename = 0;
 272         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 273         paths[0] = origin->path;
 274         paths[1] = NULL;
 275
 276         diff_tree_setup_paths(paths, &diff_opts);
 277         if (diff_setup_done(&diff_opts) < 0)
 278                 die("diff-setup");
 279         diff_tree_sha1(parent->tree->object.sha1,
 280                        origin->commit->tree->object.sha1,
 281                        "", &diff_opts);
 282         diffcore_std(&diff_opts);
 283
 284         /* It is either one entry that says "modified", or "created",
 285          * or nothing.
 286          */
 287         if (!diff_queued_diff.nr) {
 288                 /* The path is the same as parent */
 289                 porigin = get_origin(sb, parent, origin->path);
 290                 hashcpy(porigin->blob_sha1, origin->blob_sha1);
 291         }
 292         else if (diff_queued_diff.nr != 1)
 293                 die("internal error in blame::find_origin");
 294         else {
 295                 struct diff_filepair *p = diff_queued_diff.queue[0];
 296                 switch (p->status) {
 297                 default:
 298                         die("internal error in blame::find_origin (%c)",
 299                             p->status);
 300                 case 'M':
 301                         porigin = get_origin(sb, parent, origin->path);
 302                         hashcpy(porigin->blob_sha1, p->one->sha1);
 303                         break;
 304                 case 'A':
 305                 case 'T':
 306                         /* Did not exist in parent, or type changed */
 307                         break;
 308                 }
 309         }
 310         diff_flush(&diff_opts);
 311         if (porigin) {
 312                 struct origin *cached;
 313                 cached = make_origin(porigin->commit, porigin->path);
 314                 hashcpy(cached->blob_sha1, porigin->blob_sha1);
 315                 parent->util = cached;
 316         }
 317         return porigin;
 318 }
 319
 320 static struct origin *find_rename(struct scoreboard *sb,
 321                                   struct commit *parent,
 322                                   struct origin *origin)
 323 {
 324         struct origin *porigin = NULL;
 325         struct diff_options diff_opts;
 326         int i;
 327         const char *paths[2];
 328
 329         diff_setup(&diff_opts);
 330         diff_opts.recursive = 1;
 331         diff_opts.detect_rename = DIFF_DETECT_RENAME;
 332         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 333         diff_opts.single_follow = origin->path;
 334         paths[0] = NULL;
 335         diff_tree_setup_paths(paths, &diff_opts);
 336         if (diff_setup_done(&diff_opts) < 0)
 337                 die("diff-setup");
 338         diff_tree_sha1(parent->tree->object.sha1,
 339                        origin->commit->tree->object.sha1,
 340                        "", &diff_opts);
 341         diffcore_std(&diff_opts);
 342
 343         for (i = 0; i < diff_queued_diff.nr; i++) {
 344                 struct diff_filepair *p = diff_queued_diff.queue[i];
 345                 if ((p->status == 'R' || p->status == 'C') &&
 346                     !strcmp(p->two->path, origin->path)) {
 347                         porigin = get_origin(sb, parent, p->one->path);
 348                         hashcpy(porigin->blob_sha1, p->one->sha1);
 349                         break;
 350                 }
 351         }
 352         diff_flush(&diff_opts);
 353         return porigin;
 354 }
 355
 356 struct chunk {
 357         /* line number in postimage; up to but not including this
 358          * line is the same as preimage
 359          */
 360         int same;
 361
 362         /* preimage line number after this chunk */
 363         int p_next;
 364
 365         /* postimage line number after this chunk */
 366         int t_next;
 367 };
 368
 369 struct patch {
 370         struct chunk *chunks;
 371         int num;
 372 };
 373
 374 struct blame_diff_state {
 375         struct xdiff_emit_state xm;
 376         struct patch *ret;
 377         unsigned hunk_post_context;
 378         unsigned hunk_in_pre_context : 1;
 379 };
 380
 381 static void process_u_diff(void *state_, char *line, unsigned long len)
 382 {
 383         struct blame_diff_state *state = state_;
 384         struct chunk *chunk;
 385         int off1, off2, len1, len2, num;
 386
 387         num = state->ret->num;
 388         if (len < 4 || line[0] != '@' || line[1] != '@') {
 389                 if (state->hunk_in_pre_context && line[0] == ' ')
 390                         state->ret->chunks[num - 1].same++;
 391                 else {
 392                         state->hunk_in_pre_context = 0;
 393                         if (line[0] == ' ')
 394                                 state->hunk_post_context++;
 395                         else
 396                                 state->hunk_post_context = 0;
 397                 }
 398                 return;
 399         }
 400
 401         if (num && state->hunk_post_context) {
 402                 chunk = &state->ret->chunks[num - 1];
 403                 chunk->p_next -= state->hunk_post_context;
 404                 chunk->t_next -= state->hunk_post_context;
 405         }
 406         state->ret->num = ++num;
 407         state->ret->chunks = xrealloc(state->ret->chunks,
 408                                       sizeof(struct chunk) * num);
 409         chunk = &state->ret->chunks[num - 1];
 410         if (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {
 411                 state->ret->num--;
 412                 return;
 413         }
 414
 415         /* Line numbers in patch output are one based. */
 416         off1--;
 417         off2--;
 418
 419         chunk->same = len2 ? off2 : (off2 + 1);
 420
 421         chunk->p_next = off1 + (len1 ? len1 : 1);
 422         chunk->t_next = chunk->same + len2;
 423         state->hunk_in_pre_context = 1;
 424         state->hunk_post_context = 0;
 425 }
 426
 427 static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
 428                                     int context)
 429 {
 430         struct blame_diff_state state;
 431         xpparam_t xpp;
 432         xdemitconf_t xecfg;
 433         xdemitcb_t ecb;
 434
 435         xpp.flags = XDF_NEED_MINIMAL;
 436         xecfg.ctxlen = context;
 437         xecfg.flags = 0;
 438         ecb.outf = xdiff_outf;
 439         ecb.priv = &state;
 440         memset(&state, 0, sizeof(state));
 441         state.xm.consume = process_u_diff;
 442         state.ret = xmalloc(sizeof(struct patch));
 443         state.ret->chunks = NULL;
 444         state.ret->num = 0;
 445
 446         xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);
 447
 448         if (state.ret->num) {
 449                 struct chunk *chunk;
 450                 chunk = &state.ret->chunks[state.ret->num - 1];
 451                 chunk->p_next -= state.hunk_post_context;
 452                 chunk->t_next -= state.hunk_post_context;
 453         }
 454         return state.ret;
 455 }
 456
 457 static struct patch *get_patch(struct origin *parent, struct origin *origin)
 458 {
 459         mmfile_t file_p, file_o;
 460         struct patch *patch;
 461
 462         fill_origin_blob(parent, &file_p);
 463         fill_origin_blob(origin, &file_o);
 464         if (!file_p.ptr || !file_o.ptr)
 465                 return NULL;
 466         patch = compare_buffer(&file_p, &file_o, 0);
 467         num_get_patch++;
 468         return patch;
 469 }
 470
 471 static void free_patch(struct patch *p)
 472 {
 473         free(p->chunks);
 474         free(p);
 475 }
 476
 477 static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
 478 {
 479         struct blame_entry *ent, *prev = NULL;
 480
 481         origin_incref(e->suspect);
 482
 483         for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
 484                 prev = ent;
 485
 486         /* prev, if not NULL, is the last one that is below e */
 487         e->prev = prev;
 488         if (prev) {
 489                 e->next = prev->next;
 490                 prev->next = e;
 491         }
 492         else {
 493                 e->next = sb->ent;
 494                 sb->ent = e;
 495         }
 496         if (e->next)
 497                 e->next->prev = e;
 498 }
 499
 500 static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
 501 {
 502         struct blame_entry *p, *n;
 503
 504         p = dst->prev;
 505         n = dst->next;
 506         origin_incref(src->suspect);
 507         origin_decref(dst->suspect);
 508         memcpy(dst, src, sizeof(*src));
 509         dst->prev = p;
 510         dst->next = n;
 511         dst->score = 0;
 512 }
 513
 514 static const char *nth_line(struct scoreboard *sb, int lno)
 515 {
 516         return sb->final_buf + sb->lineno[lno];
 517 }
 518
 519 static void split_overlap(struct blame_entry *split,
 520                           struct blame_entry *e,
 521                           int tlno, int plno, int same,
 522                           struct origin *parent)
 523 {
 524         /* it is known that lines between tlno to same came from
 525          * parent, and e has an overlap with that range.  it also is
 526          * known that parent's line plno corresponds to e's line tlno.
 527          *
 528          *                <---- e ----->
 529          *                   <------>
 530          *                   <------------>
 531          *             <------------>
 532          *             <------------------>
 533          *
 534          * Potentially we need to split e into three parts; before
 535          * this chunk, the chunk to be blamed for parent, and after
 536          * that portion.
 537          */
 538         int chunk_end_lno;
 539         memset(split, 0, sizeof(struct blame_entry [3]));
 540
 541         if (e->s_lno < tlno) {
 542                 /* there is a pre-chunk part not blamed on parent */
 543                 split[0].suspect = origin_incref(e->suspect);
 544                 split[0].lno = e->lno;
 545                 split[0].s_lno = e->s_lno;
 546                 split[0].num_lines = tlno - e->s_lno;
 547                 split[1].lno = e->lno + tlno - e->s_lno;
 548                 split[1].s_lno = plno;
 549         }
 550         else {
 551                 split[1].lno = e->lno;
 552                 split[1].s_lno = plno + (e->s_lno - tlno);
 553         }
 554
 555         if (same < e->s_lno + e->num_lines) {
 556                 /* there is a post-chunk part not blamed on parent */
 557                 split[2].suspect = origin_incref(e->suspect);
 558                 split[2].lno = e->lno + (same - e->s_lno);
 559                 split[2].s_lno = e->s_lno + (same - e->s_lno);
 560                 split[2].num_lines = e->s_lno + e->num_lines - same;
 561                 chunk_end_lno = split[2].lno;
 562         }
 563         else
 564                 chunk_end_lno = e->lno + e->num_lines;
 565         split[1].num_lines = chunk_end_lno - split[1].lno;
 566
 567         if (split[1].num_lines < 1)
 568                 return;
 569         split[1].suspect = origin_incref(parent);
 570 }
 571
 572 static void split_blame(struct scoreboard *sb,
 573                         struct blame_entry *split,
 574                         struct blame_entry *e)
 575 {
 576         struct blame_entry *new_entry;
 577
 578         if (split[0].suspect && split[2].suspect) {
 579                 /* we need to split e into two and add another for parent */
 580                 dup_entry(e, &split[0]);
 581
 582                 new_entry = xmalloc(sizeof(*new_entry));
 583                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 584                 add_blame_entry(sb, new_entry);
 585
 586                 new_entry = xmalloc(sizeof(*new_entry));
 587                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 588                 add_blame_entry(sb, new_entry);
 589         }
 590         else if (!split[0].suspect && !split[2].suspect)
 591                 /* parent covers the entire area */
 592                 dup_entry(e, &split[1]);
 593         else if (split[0].suspect) {
 594                 dup_entry(e, &split[0]);
 595
 596                 new_entry = xmalloc(sizeof(*new_entry));
 597                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 598                 add_blame_entry(sb, new_entry);
 599         }
 600         else {
 601                 dup_entry(e, &split[1]);
 602
 603                 new_entry = xmalloc(sizeof(*new_entry));
 604                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 605                 add_blame_entry(sb, new_entry);
 606         }
 607
 608         if (DEBUG) { /* sanity */
 609                 struct blame_entry *ent;
 610                 int lno = sb->ent->lno, corrupt = 0;
 611
 612                 for (ent = sb->ent; ent; ent = ent->next) {
 613                         if (lno != ent->lno)
 614                                 corrupt = 1;
 615                         if (ent->s_lno < 0)
 616                                 corrupt = 1;
 617                         lno += ent->num_lines;
 618                 }
 619                 if (corrupt) {
 620                         lno = sb->ent->lno;
 621                         for (ent = sb->ent; ent; ent = ent->next) {
 622                                 printf("L %8d l %8d n %8d\n",
 623                                        lno, ent->lno, ent->num_lines);
 624                                 lno = ent->lno + ent->num_lines;
 625                         }
 626                         die("oops");
 627                 }
 628         }
 629 }
 630
 631 static void decref_split(struct blame_entry *split)
 632 {
 633         int i;
 634
 635         for (i = 0; i < 3; i++)
 636                 origin_decref(split[i].suspect);
 637 }
 638
 639 static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
 640                           int tlno, int plno, int same,
 641                           struct origin *parent)
 642 {
 643         struct blame_entry split[3];
 644
 645         split_overlap(split, e, tlno, plno, same, parent);
 646         if (split[1].suspect)
 647                 split_blame(sb, split, e);
 648         decref_split(split);
 649 }
 650
 651 static int find_last_in_target(struct scoreboard *sb, struct origin *target)
 652 {
 653         struct blame_entry *e;
 654         int last_in_target = -1;
 655
 656         for (e = sb->ent; e; e = e->next) {
 657                 if (e->guilty || cmp_suspect(e->suspect, target))
 658                         continue;
 659                 if (last_in_target < e->s_lno + e->num_lines)
 660                         last_in_target = e->s_lno + e->num_lines;
 661         }
 662         return last_in_target;
 663 }
 664
 665 static void blame_chunk(struct scoreboard *sb,
 666                         int tlno, int plno, int same,
 667                         struct origin *target, struct origin *parent)
 668 {
 669         struct blame_entry *e;
 670
 671         for (e = sb->ent; e; e = e->next) {
 672                 if (e->guilty || cmp_suspect(e->suspect, target))
 673                         continue;
 674                 if (same <= e->s_lno)
 675                         continue;
 676                 if (tlno < e->s_lno + e->num_lines)
 677                         blame_overlap(sb, e, tlno, plno, same, parent);
 678         }
 679 }
 680
 681 static int pass_blame_to_parent(struct scoreboard *sb,
 682                                 struct origin *target,
 683                                 struct origin *parent)
 684 {
 685         int i, last_in_target, plno, tlno;
 686         struct patch *patch;
 687
 688         last_in_target = find_last_in_target(sb, target);
 689         if (last_in_target < 0)
 690                 return 1; /* nothing remains for this target */
 691
 692         patch = get_patch(parent, target);
 693         plno = tlno = 0;
 694         for (i = 0; i < patch->num; i++) {
 695                 struct chunk *chunk = &patch->chunks[i];
 696
 697                 blame_chunk(sb, tlno, plno, chunk->same, target, parent);
 698                 plno = chunk->p_next;
 699                 tlno = chunk->t_next;
 700         }
 701         /* rest (i.e. anything above tlno) are the same as parent */
 702         blame_chunk(sb, tlno, plno, last_in_target, target, parent);
 703
 704         free_patch(patch);
 705         return 0;
 706 }
 707
 708 static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
 709 {
 710         unsigned score;
 711         const char *cp, *ep;
 712
 713         if (e->score)
 714                 return e->score;
 715
 716         score = 1;
 717         cp = nth_line(sb, e->lno);
 718         ep = nth_line(sb, e->lno + e->num_lines);
 719         while (cp < ep) {
 720                 unsigned ch = *((unsigned char *)cp);
 721                 if (isalnum(ch))
 722                         score++;
 723                 cp++;
 724         }
 725         e->score = score;
 726         return score;
 727 }
 728
 729 static void copy_split_if_better(struct scoreboard *sb,
 730                                  struct blame_entry *best_so_far,
 731                                  struct blame_entry *this)
 732 {
 733         int i;
 734
 735         if (!this[1].suspect)
 736                 return;
 737         if (best_so_far[1].suspect) {
 738                 if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
 739                         return;
 740         }
 741
 742         for (i = 0; i < 3; i++)
 743                 origin_incref(this[i].suspect);
 744         decref_split(best_so_far);
 745         memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
 746 }
 747
 748 static void find_copy_in_blob(struct scoreboard *sb,
 749                               struct blame_entry *ent,
 750                               struct origin *parent,
 751                               struct blame_entry *split,
 752                               mmfile_t *file_p)
 753 {
 754         const char *cp;
 755         int cnt;
 756         mmfile_t file_o;
 757         struct patch *patch;
 758         int i, plno, tlno;
 759
 760         cp = nth_line(sb, ent->lno);
 761         file_o.ptr = (char*) cp;
 762         cnt = ent->num_lines;
 763
 764         while (cnt && cp < sb->final_buf + sb->final_buf_size) {
 765                 if (*cp++ == '\n')
 766                         cnt--;
 767         }
 768         file_o.size = cp - file_o.ptr;
 769
 770         patch = compare_buffer(file_p, &file_o, 1);
 771
 772         memset(split, 0, sizeof(struct blame_entry [3]));
 773         plno = tlno = 0;
 774         for (i = 0; i < patch->num; i++) {
 775                 struct chunk *chunk = &patch->chunks[i];
 776
 777                 /* tlno to chunk->same are the same as ent */
 778                 if (ent->num_lines <= tlno)
 779                         break;
 780                 if (tlno < chunk->same) {
 781                         struct blame_entry this[3];
 782                         split_overlap(this, ent,
 783                                       tlno + ent->s_lno, plno,
 784                                       chunk->same + ent->s_lno,
 785                                       parent);
 786                         copy_split_if_better(sb, split, this);
 787                         decref_split(this);
 788                 }
 789                 plno = chunk->p_next;
 790                 tlno = chunk->t_next;
 791         }
 792         free_patch(patch);
 793 }
 794
 795 static int find_move_in_parent(struct scoreboard *sb,
 796                                struct origin *target,
 797                                struct origin *parent)
 798 {
 799         int last_in_target, made_progress;
 800         struct blame_entry *e, split[3];
 801         mmfile_t file_p;
 802
 803         last_in_target = find_last_in_target(sb, target);
 804         if (last_in_target < 0)
 805                 return 1; /* nothing remains for this target */
 806
 807         fill_origin_blob(parent, &file_p);
 808         if (!file_p.ptr)
 809                 return 0;
 810
 811         made_progress = 1;
 812         while (made_progress) {
 813                 made_progress = 0;
 814                 for (e = sb->ent; e; e = e->next) {
 815                         if (e->guilty || cmp_suspect(e->suspect, target))
 816                                 continue;
 817                         find_copy_in_blob(sb, e, parent, split, &file_p);
 818                         if (split[1].suspect &&
 819                             blame_move_score < ent_score(sb, &split[1])) {
 820                                 split_blame(sb, split, e);
 821                                 made_progress = 1;
 822                         }
 823                         decref_split(split);
 824                 }
 825         }
 826         return 0;
 827 }
 828
 829
 830 struct blame_list {
 831         struct blame_entry *ent;
 832         struct blame_entry split[3];
 833 };
 834
 835 static struct blame_list *setup_blame_list(struct scoreboard *sb,
 836                                            struct origin *target,
 837                                            int *num_ents_p)
 838 {
 839         struct blame_entry *e;
 840         int num_ents, i;
 841         struct blame_list *blame_list = NULL;
 842
 843         /* Count the number of entries the target is suspected for,
 844          * and prepare a list of entry and the best split.
 845          */
 846         for (e = sb->ent, num_ents = 0; e; e = e->next)
 847                 if (!e->guilty && !cmp_suspect(e->suspect, target))
 848                         num_ents++;
 849         if (num_ents) {
 850                 blame_list = xcalloc(num_ents, sizeof(struct blame_list));
 851                 for (e = sb->ent, i = 0; e; e = e->next)
 852                         if (!e->guilty && !cmp_suspect(e->suspect, target))
 853                                 blame_list[i++].ent = e;
 854         }
 855         *num_ents_p = num_ents;
 856         return blame_list;
 857 }
 858
 859 static int find_copy_in_parent(struct scoreboard *sb,
 860                                struct origin *target,
 861                                struct commit *parent,
 862                                struct origin *porigin,
 863                                int opt)
 864 {
 865         struct diff_options diff_opts;
 866         const char *paths[1];
 867         int i, j;
 868         int retval;
 869         struct blame_list *blame_list;
 870         int num_ents;
 871
 872         blame_list = setup_blame_list(sb, target, &num_ents);
 873         if (!blame_list)
 874                 return 1; /* nothing remains for this target */
 875
 876         diff_setup(&diff_opts);
 877         diff_opts.recursive = 1;
 878         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 879
 880         paths[0] = NULL;
 881         diff_tree_setup_paths(paths, &diff_opts);
 882         if (diff_setup_done(&diff_opts) < 0)
 883                 die("diff-setup");
 884
 885         /* Try "find copies harder" on new path if requested;
 886          * we do not want to use diffcore_rename() actually to
 887          * match things up; find_copies_harder is set only to
 888          * force diff_tree_sha1() to feed all filepairs to diff_queue,
 889          * and this code needs to be after diff_setup_done(), which
 890          * usually makes find-copies-harder imply copy detection.
 891          */
 892         if ((opt & PICKAXE_BLAME_COPY_HARDER) &&
 893             (!porigin || strcmp(target->path, porigin->path)))
 894                 diff_opts.find_copies_harder = 1;
 895
 896         diff_tree_sha1(parent->tree->object.sha1,
 897                        target->commit->tree->object.sha1,
 898                        "", &diff_opts);
 899
 900         if (!diff_opts.find_copies_harder)
 901                 diffcore_std(&diff_opts);
 902
 903         retval = 0;
 904         while (1) {
 905                 int made_progress = 0;
 906
 907                 for (i = 0; i < diff_queued_diff.nr; i++) {
 908                         struct diff_filepair *p = diff_queued_diff.queue[i];
 909                         struct origin *norigin;
 910                         mmfile_t file_p;
 911                         struct blame_entry this[3];
 912
 913                         if (!DIFF_FILE_VALID(p->one))
 914                                 continue; /* does not exist in parent */
 915                         if (porigin && !strcmp(p->one->path, porigin->path))
 916                                 /* find_move already dealt with this path */
 917                                 continue;
 918
 919                         norigin = get_origin(sb, parent, p->one->path);
 920                         hashcpy(norigin->blob_sha1, p->one->sha1);
 921                         fill_origin_blob(norigin, &file_p);
 922                         if (!file_p.ptr)
 923                                 continue;
 924
 925                         for (j = 0; j < num_ents; j++) {
 926                                 find_copy_in_blob(sb, blame_list[j].ent,
 927                                                   norigin, this, &file_p);
 928                                 copy_split_if_better(sb, blame_list[j].split,
 929                                                      this);
 930                                 decref_split(this);
 931                         }
 932                         origin_decref(norigin);
 933                 }
 934
 935                 for (j = 0; j < num_ents; j++) {
 936                         struct blame_entry *split = blame_list[j].split;
 937                         if (split[1].suspect &&
 938                             blame_copy_score < ent_score(sb, &split[1])) {
 939                                 split_blame(sb, split, blame_list[j].ent);
 940                                 made_progress = 1;
 941                         }
 942                         decref_split(split);
 943                 }
 944                 free(blame_list);
 945
 946                 if (!made_progress)
 947                         break;
 948                 blame_list = setup_blame_list(sb, target, &num_ents);
 949                 if (!blame_list) {
 950                         retval = 1;
 951                         break;
 952                 }
 953         }
 954         diff_flush(&diff_opts);
 955
 956         return retval;
 957 }
 958
 959 /* The blobs of origin and porigin exactly match, so everything
 960  * origin is suspected for can be blamed on the parent.
 961  */
 962 static void pass_whole_blame(struct scoreboard *sb,
 963                              struct origin *origin, struct origin *porigin)
 964 {
 965         struct blame_entry *e;
 966
 967         if (!porigin->file.ptr && origin->file.ptr) {
 968                 /* Steal its file */
 969                 porigin->file = origin->file;
 970                 origin->file.ptr = NULL;
 971         }
 972         for (e = sb->ent; e; e = e->next) {
 973                 if (cmp_suspect(e->suspect, origin))
 974                         continue;
 975                 origin_incref(porigin);
 976                 origin_decref(e->suspect);
 977                 e->suspect = porigin;
 978         }
 979 }
 980
 981 #define MAXPARENT 16
 982
 983 static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
 984 {
 985         int i, pass;
 986         struct commit *commit = origin->commit;
 987         struct commit_list *parent;
 988         struct origin *parent_origin[MAXPARENT], *porigin;
 989
 990         memset(parent_origin, 0, sizeof(parent_origin));
 991
 992         /* The first pass looks for unrenamed path to optimize for
 993          * common cases, then we look for renames in the second pass.
 994          */
 995         for (pass = 0; pass < 2; pass++) {
 996                 struct origin *(*find)(struct scoreboard *,
 997                                        struct commit *, struct origin *);
 998                 find = pass ? find_rename : find_origin;
 999
1000                 for (i = 0, parent = commit->parents;
1001                      i < MAXPARENT && parent;
1002                      parent = parent->next, i++) {
1003                         struct commit *p = parent->item;
1004                         int j, same;
1005
1006                         if (parent_origin[i])
1007                                 continue;
1008                         if (parse_commit(p))
1009                                 continue;
1010                         porigin = find(sb, p, origin);
1011                         if (!porigin)
1012                                 continue;
1013                         if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
1014                                 pass_whole_blame(sb, origin, porigin);
1015                                 origin_decref(porigin);
1016                                 goto finish;
1017                         }
1018                         for (j = same = 0; j < i; j++)
1019                                 if (parent_origin[j] &&
1020                                     !hashcmp(parent_origin[j]->blob_sha1,
1021                                              porigin->blob_sha1)) {
1022                                         same = 1;
1023                                         break;
1024                                 }
1025                         if (!same)
1026                                 parent_origin[i] = porigin;
1027                         else
1028                                 origin_decref(porigin);
1029                 }
1030         }
1031
1032         num_commits++;
1033         for (i = 0, parent = commit->parents;
1034              i < MAXPARENT && parent;
1035              parent = parent->next, i++) {
1036                 struct origin *porigin = parent_origin[i];
1037                 if (!porigin)
1038                         continue;
1039                 if (pass_blame_to_parent(sb, origin, porigin))
1040                         goto finish;
1041         }
1042
1043         /*
1044          * Optionally run "miff" to find moves in parents' files here.
1045          */
1046         if (opt & PICKAXE_BLAME_MOVE)
1047                 for (i = 0, parent = commit->parents;
1048                      i < MAXPARENT && parent;
1049                      parent = parent->next, i++) {
1050                         struct origin *porigin = parent_origin[i];
1051                         if (!porigin)
1052                                 continue;
1053                         if (find_move_in_parent(sb, origin, porigin))
1054                                 goto finish;
1055                 }
1056
1057         /*
1058          * Optionally run "ciff" to find copies from parents' files here.
1059          */
1060         if (opt & PICKAXE_BLAME_COPY)
1061                 for (i = 0, parent = commit->parents;
1062                      i < MAXPARENT && parent;
1063                      parent = parent->next, i++) {
1064                         struct origin *porigin = parent_origin[i];
1065                         if (find_copy_in_parent(sb, origin, parent->item,
1066                                                 porigin, opt))
1067                                 goto finish;
1068                 }
1069
1070  finish:
1071         for (i = 0; i < MAXPARENT; i++)
1072                 origin_decref(parent_origin[i]);
1073 }
1074
1075 struct commit_info
1076 {
1077         char *author;
1078         char *author_mail;
1079         unsigned long author_time;
1080         char *author_tz;
1081
1082         /* filled only when asked for details */
1083         char *committer;
1084         char *committer_mail;
1085         unsigned long committer_time;
1086         char *committer_tz;
1087
1088         char *summary;
1089 };
1090
1091 static void get_ac_line(const char *inbuf, const char *what,
1092                         int bufsz, char *person, char **mail,
1093                         unsigned long *time, char **tz)
1094 {
1095         int len;
1096         char *tmp, *endp;
1097
1098         tmp = strstr(inbuf, what);
1099         if (!tmp)
1100                 goto error_out;
1101         tmp += strlen(what);
1102         endp = strchr(tmp, '\n');
1103         if (!endp)
1104                 len = strlen(tmp);
1105         else
1106                 len = endp - tmp;
1107         if (bufsz <= len) {
1108         error_out:
1109                 /* Ugh */
1110                 person = *mail = *tz = "(unknown)";
1111                 *time = 0;
1112                 return;
1113         }
1114         memcpy(person, tmp, len);
1115
1116         tmp = person;
1117         tmp += len;
1118         *tmp = 0;
1119         while (*tmp != ' ')
1120                 tmp--;
1121         *tz = tmp+1;
1122
1123         *tmp = 0;
1124         while (*tmp != ' ')
1125                 tmp--;
1126         *time = strtoul(tmp, NULL, 10);
1127
1128         *tmp = 0;
1129         while (*tmp != ' ')
1130                 tmp--;
1131         *mail = tmp + 1;
1132         *tmp = 0;
1133 }
1134
1135 static void get_commit_info(struct commit *commit,
1136                             struct commit_info *ret,
1137                             int detailed)
1138 {
1139         int len;
1140         char *tmp, *endp;
1141         static char author_buf[1024];
1142         static char committer_buf[1024];
1143         static char summary_buf[1024];
1144
1145         /* We've operated without save_commit_buffer, so
1146          * we now need to populate them for output.
1147          */
1148         if (!commit->buffer) {
1149                 char type[20];
1150                 unsigned long size;
1151                 commit->buffer =
1152                         read_sha1_file(commit->object.sha1, type, &size);
1153         }
1154         ret->author = author_buf;
1155         get_ac_line(commit->buffer, "\nauthor ",
1156                     sizeof(author_buf), author_buf, &ret->author_mail,
1157                     &ret->author_time, &ret->author_tz);
1158
1159         if (!detailed)
1160                 return;
1161
1162         ret->committer = committer_buf;
1163         get_ac_line(commit->buffer, "\ncommitter ",
1164                     sizeof(committer_buf), committer_buf, &ret->committer_mail,
1165                     &ret->committer_time, &ret->committer_tz);
1166
1167         ret->summary = summary_buf;
1168         tmp = strstr(commit->buffer, "\n\n");
1169         if (!tmp) {
1170         error_out:
1171                 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
1172                 return;
1173         }
1174         tmp += 2;
1175         endp = strchr(tmp, '\n');
1176         if (!endp)
1177                 goto error_out;
1178         len = endp - tmp;
1179         if (len >= sizeof(summary_buf))
1180                 goto error_out;
1181         memcpy(summary_buf, tmp, len);
1182         summary_buf[len] = 0;
1183 }
1184
1185 static void write_filename_info(const char *path)
1186 {
1187         printf("filename ");
1188         write_name_quoted(NULL, 0, path, 1, stdout);
1189         putchar('\n');
1190 }
1191
1192 static void found_guilty_entry(struct blame_entry *ent)
1193 {
1194         if (ent->guilty)
1195                 return;
1196         ent->guilty = 1;
1197         if (incremental) {
1198                 struct origin *suspect = ent->suspect;
1199
1200                 printf("%s %d %d %d\n",
1201                        sha1_to_hex(suspect->commit->object.sha1),
1202                        ent->s_lno + 1, ent->lno + 1, ent->num_lines);
1203                 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1204                         struct commit_info ci;
1205                         suspect->commit->object.flags |= METAINFO_SHOWN;
1206                         get_commit_info(suspect->commit, &ci, 1);
1207                         printf("author %s\n", ci.author);
1208                         printf("author-mail %s\n", ci.author_mail);
1209                         printf("author-time %lu\n", ci.author_time);
1210                         printf("author-tz %s\n", ci.author_tz);
1211                         printf("committer %s\n", ci.committer);
1212                         printf("committer-mail %s\n", ci.committer_mail);
1213                         printf("committer-time %lu\n", ci.committer_time);
1214                         printf("committer-tz %s\n", ci.committer_tz);
1215                         printf("summary %s\n", ci.summary);
1216                         if (suspect->commit->object.flags & UNINTERESTING)
1217                                 printf("boundary\n");
1218                 }
1219                 write_filename_info(suspect->path);
1220         }
1221 }
1222
1223 static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)
1224 {
1225         while (1) {
1226                 struct blame_entry *ent;
1227                 struct commit *commit;
1228                 struct origin *suspect = NULL;
1229
1230                 /* find one suspect to break down */
1231                 for (ent = sb->ent; !suspect && ent; ent = ent->next)
1232                         if (!ent->guilty)
1233                                 suspect = ent->suspect;
1234                 if (!suspect)
1235                         return; /* all done */
1236
1237                 origin_incref(suspect);
1238                 commit = suspect->commit;
1239                 if (!commit->object.parsed)
1240                         parse_commit(commit);
1241                 if (!(commit->object.flags & UNINTERESTING) &&
1242                     !(revs->max_age != -1 && commit->date  < revs->max_age))
1243                         pass_blame(sb, suspect, opt);
1244                 else {
1245                         commit->object.flags |= UNINTERESTING;
1246                         if (commit->object.parsed)
1247                                 mark_parents_uninteresting(commit);
1248                 }
1249                 /* treat root commit as boundary */
1250                 if (!commit->parents && !show_root)
1251                         commit->object.flags |= UNINTERESTING;
1252
1253                 /* Take responsibility for the remaining entries */
1254                 for (ent = sb->ent; ent; ent = ent->next)
1255                         if (!cmp_suspect(ent->suspect, suspect))
1256                                 found_guilty_entry(ent);
1257                 origin_decref(suspect);
1258
1259                 if (DEBUG) /* sanity */
1260                         sanity_check_refcnt(sb);
1261         }
1262 }
1263
1264 static const char *format_time(unsigned long time, const char *tz_str,
1265                                int show_raw_time)
1266 {
1267         static char time_buf[128];
1268         time_t t = time;
1269         int minutes, tz;
1270         struct tm *tm;
1271
1272         if (show_raw_time) {
1273                 sprintf(time_buf, "%lu %s", time, tz_str);
1274                 return time_buf;
1275         }
1276
1277         tz = atoi(tz_str);
1278         minutes = tz < 0 ? -tz : tz;
1279         minutes = (minutes / 100)*60 + (minutes % 100);
1280         minutes = tz < 0 ? -minutes : minutes;
1281         t = time + minutes * 60;
1282         tm = gmtime(&t);
1283
1284         strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
1285         strcat(time_buf, tz_str);
1286         return time_buf;
1287 }
1288
1289 #define OUTPUT_ANNOTATE_COMPAT  001
1290 #define OUTPUT_LONG_OBJECT_NAME 002
1291 #define OUTPUT_RAW_TIMESTAMP    004
1292 #define OUTPUT_PORCELAIN        010
1293 #define OUTPUT_SHOW_NAME        020
1294 #define OUTPUT_SHOW_NUMBER      040
1295 #define OUTPUT_SHOW_SCORE      0100
1296
1297 static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
1298 {
1299         int cnt;
1300         const char *cp;
1301         struct origin *suspect = ent->suspect;
1302         char hex[41];
1303
1304         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1305         printf("%s%c%d %d %d\n",
1306                hex,
1307                ent->guilty ? ' ' : '*', // purely for debugging
1308                ent->s_lno + 1,
1309                ent->lno + 1,
1310                ent->num_lines);
1311         if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1312                 struct commit_info ci;
1313                 suspect->commit->object.flags |= METAINFO_SHOWN;
1314                 get_commit_info(suspect->commit, &ci, 1);
1315                 printf("author %s\n", ci.author);
1316                 printf("author-mail %s\n", ci.author_mail);
1317                 printf("author-time %lu\n", ci.author_time);
1318                 printf("author-tz %s\n", ci.author_tz);
1319                 printf("committer %s\n", ci.committer);
1320                 printf("committer-mail %s\n", ci.committer_mail);
1321                 printf("committer-time %lu\n", ci.committer_time);
1322                 printf("committer-tz %s\n", ci.committer_tz);
1323                 write_filename_info(suspect->path);
1324                 printf("summary %s\n", ci.summary);
1325                 if (suspect->commit->object.flags & UNINTERESTING)
1326                         printf("boundary\n");
1327         }
1328         else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
1329                 write_filename_info(suspect->path);
1330
1331         cp = nth_line(sb, ent->lno);
1332         for (cnt = 0; cnt < ent->num_lines; cnt++) {
1333                 char ch;
1334                 if (cnt)
1335                         printf("%s %d %d\n", hex,
1336                                ent->s_lno + 1 + cnt,
1337                                ent->lno + 1 + cnt);
1338                 putchar('\t');
1339                 do {
1340                         ch = *cp++;
1341                         putchar(ch);
1342                 } while (ch != '\n' &&
1343                          cp < sb->final_buf + sb->final_buf_size);
1344         }
1345 }
1346
1347 static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1348 {
1349         int cnt;
1350         const char *cp;
1351         struct origin *suspect = ent->suspect;
1352         struct commit_info ci;
1353         char hex[41];
1354         int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1355
1356         get_commit_info(suspect->commit, &ci, 1);
1357         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1358
1359         cp = nth_line(sb, ent->lno);
1360         for (cnt = 0; cnt < ent->num_lines; cnt++) {
1361                 char ch;
1362                 int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8;
1363
1364                 if (suspect->commit->object.flags & UNINTERESTING) {
1365                         if (!blank_boundary) {
1366                                 length--;
1367                                 putchar('^');
1368                         }
1369                         else
1370                                 memset(hex, ' ', length);
1371                 }
1372
1373                 printf("%.*s", length, hex);
1374                 if (opt & OUTPUT_ANNOTATE_COMPAT)
1375                         printf("\t(%10s\t%10s\t%d)", ci.author,
1376                                format_time(ci.author_time, ci.author_tz,
1377                                            show_raw_time),
1378                                ent->lno + 1 + cnt);
1379                 else {
1380                         if (opt & OUTPUT_SHOW_SCORE)
1381                                 printf(" %*d %02d",
1382                                        max_score_digits, ent->score,
1383                                        ent->suspect->refcnt);
1384                         if (opt & OUTPUT_SHOW_NAME)
1385                                 printf(" %-*.*s", longest_file, longest_file,
1386                                        suspect->path);
1387                         if (opt & OUTPUT_SHOW_NUMBER)
1388                                 printf(" %*d", max_orig_digits,
1389                                        ent->s_lno + 1 + cnt);
1390                         printf(" (%-*.*s %10s %*d) ",
1391                                longest_author, longest_author, ci.author,
1392                                format_time(ci.author_time, ci.author_tz,
1393                                            show_raw_time),
1394                                max_digits, ent->lno + 1 + cnt);
1395                 }
1396                 do {
1397                         ch = *cp++;
1398                         putchar(ch);
1399                 } while (ch != '\n' &&
1400                          cp < sb->final_buf + sb->final_buf_size);
1401         }
1402 }
1403
1404 static void output(struct scoreboard *sb, int option)
1405 {
1406         struct blame_entry *ent;
1407
1408         if (option & OUTPUT_PORCELAIN) {
1409                 for (ent = sb->ent; ent; ent = ent->next) {
1410                         struct blame_entry *oth;
1411                         struct origin *suspect = ent->suspect;
1412                         struct commit *commit = suspect->commit;
1413                         if (commit->object.flags & MORE_THAN_ONE_PATH)
1414                                 continue;
1415                         for (oth = ent->next; oth; oth = oth->next) {
1416                                 if ((oth->suspect->commit != commit) ||
1417                                     !strcmp(oth->suspect->path, suspect->path))
1418                                         continue;
1419                                 commit->object.flags |= MORE_THAN_ONE_PATH;
1420                                 break;
1421                         }
1422                 }
1423         }
1424
1425         for (ent = sb->ent; ent; ent = ent->next) {
1426                 if (option & OUTPUT_PORCELAIN)
1427                         emit_porcelain(sb, ent);
1428                 else {
1429                         emit_other(sb, ent, option);
1430                 }
1431         }
1432 }
1433
1434 static int prepare_lines(struct scoreboard *sb)
1435 {
1436         const char *buf = sb->final_buf;
1437         unsigned long len = sb->final_buf_size;
1438         int num = 0, incomplete = 0, bol = 1;
1439
1440         if (len && buf[len-1] != '\n')
1441                 incomplete++; /* incomplete line at the end */
1442         while (len--) {
1443                 if (bol) {
1444                         sb->lineno = xrealloc(sb->lineno,
1445                                               sizeof(int* ) * (num + 1));
1446                         sb->lineno[num] = buf - sb->final_buf;
1447                         bol = 0;
1448                 }
1449                 if (*buf++ == '\n') {
1450                         num++;
1451                         bol = 1;
1452                 }
1453         }
1454         sb->lineno = xrealloc(sb->lineno,
1455                               sizeof(int* ) * (num + incomplete + 1));
1456         sb->lineno[num + incomplete] = buf - sb->final_buf;
1457         sb->num_lines = num + incomplete;
1458         return sb->num_lines;
1459 }
1460
1461 static int read_ancestry(const char *graft_file)
1462 {
1463         FILE *fp = fopen(graft_file, "r");
1464         char buf[1024];
1465         if (!fp)
1466                 return -1;
1467         while (fgets(buf, sizeof(buf), fp)) {
1468                 /* The format is just "Commit Parent1 Parent2 ...\n" */
1469                 int len = strlen(buf);
1470                 struct commit_graft *graft = read_graft_line(buf, len);
1471                 if (graft)
1472                         register_commit_graft(graft, 0);
1473         }
1474         fclose(fp);
1475         return 0;
1476 }
1477
1478 static int lineno_width(int lines)
1479 {
1480         int i, width;
1481
1482         for (width = 1, i = 10; i <= lines + 1; width++)
1483                 i *= 10;
1484         return width;
1485 }
1486
1487 static void find_alignment(struct scoreboard *sb, int *option)
1488 {
1489         int longest_src_lines = 0;
1490         int longest_dst_lines = 0;
1491         unsigned largest_score = 0;
1492         struct blame_entry *e;
1493
1494         for (e = sb->ent; e; e = e->next) {
1495                 struct origin *suspect = e->suspect;
1496                 struct commit_info ci;
1497                 int num;
1498
1499                 if (strcmp(suspect->path, sb->path))
1500                         *option |= OUTPUT_SHOW_NAME;
1501                 num = strlen(suspect->path);
1502                 if (longest_file < num)
1503                         longest_file = num;
1504                 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1505                         suspect->commit->object.flags |= METAINFO_SHOWN;
1506                         get_commit_info(suspect->commit, &ci, 1);
1507                         num = strlen(ci.author);
1508                         if (longest_author < num)
1509                                 longest_author = num;
1510                 }
1511                 num = e->s_lno + e->num_lines;
1512                 if (longest_src_lines < num)
1513                         longest_src_lines = num;
1514                 num = e->lno + e->num_lines;
1515                 if (longest_dst_lines < num)
1516                         longest_dst_lines = num;
1517                 if (largest_score < ent_score(sb, e))
1518                         largest_score = ent_score(sb, e);
1519         }
1520         max_orig_digits = lineno_width(longest_src_lines);
1521         max_digits = lineno_width(longest_dst_lines);
1522         max_score_digits = lineno_width(largest_score);
1523 }
1524
1525 static void sanity_check_refcnt(struct scoreboard *sb)
1526 {
1527         int baa = 0;
1528         struct blame_entry *ent;
1529
1530         for (ent = sb->ent; ent; ent = ent->next) {
1531                 /* Nobody should have zero or negative refcnt */
1532                 if (ent->suspect->refcnt <= 0) {
1533                         fprintf(stderr, "%s in %s has negative refcnt %d\n",
1534                                 ent->suspect->path,
1535                                 sha1_to_hex(ent->suspect->commit->object.sha1),
1536                                 ent->suspect->refcnt);
1537                         baa = 1;
1538                 }
1539         }
1540         for (ent = sb->ent; ent; ent = ent->next) {
1541                 /* Mark the ones that haven't been checked */
1542                 if (0 < ent->suspect->refcnt)
1543                         ent->suspect->refcnt = -ent->suspect->refcnt;
1544         }
1545         for (ent = sb->ent; ent; ent = ent->next) {
1546                 /* then pick each and see if they have the the correct
1547                  * refcnt.
1548                  */
1549                 int found;
1550                 struct blame_entry *e;
1551                 struct origin *suspect = ent->suspect;
1552
1553                 if (0 < suspect->refcnt)
1554                         continue;
1555                 suspect->refcnt = -suspect->refcnt; /* Unmark */
1556                 for (found = 0, e = sb->ent; e; e = e->next) {
1557                         if (e->suspect != suspect)
1558                                 continue;
1559                         found++;
1560                 }
1561                 if (suspect->refcnt != found) {
1562                         fprintf(stderr, "%s in %s has refcnt %d, not %d\n",
1563                                 ent->suspect->path,
1564                                 sha1_to_hex(ent->suspect->commit->object.sha1),
1565                                 ent->suspect->refcnt, found);
1566                         baa = 2;
1567                 }
1568         }
1569         if (baa) {
1570                 int opt = 0160;
1571                 find_alignment(sb, &opt);
1572                 output(sb, opt);
1573                 die("Baa %d!", baa);
1574         }
1575 }
1576
1577 static int has_path_in_work_tree(const char *path)
1578 {
1579         struct stat st;
1580         return !lstat(path, &st);
1581 }
1582
1583 static unsigned parse_score(const char *arg)
1584 {
1585         char *end;
1586         unsigned long score = strtoul(arg, &end, 10);
1587         if (*end)
1588                 return 0;
1589         return score;
1590 }
1591
1592 static const char *add_prefix(const char *prefix, const char *path)
1593 {
1594         if (!prefix || !prefix[0])
1595                 return path;
1596         return prefix_path(prefix, strlen(prefix), path);
1597 }
1598
1599 static const char *parse_loc(const char *spec,
1600                              struct scoreboard *sb, long lno,
1601                              long begin, long *ret)
1602 {
1603         char *term;
1604         const char *line;
1605         long num;
1606         int reg_error;
1607         regex_t regexp;
1608         regmatch_t match[1];
1609
1610         /* Allow "-L <something>,+20" to mean starting at <something>
1611          * for 20 lines, or "-L <something>,-5" for 5 lines ending at
1612          * <something>.
1613          */
1614         if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
1615                 num = strtol(spec + 1, &term, 10);
1616                 if (term != spec + 1) {
1617                         if (spec[0] == '-')
1618                                 num = 0 - num;
1619                         if (0 < num)
1620                                 *ret = begin + num - 2;
1621                         else if (!num)
1622                                 *ret = begin;
1623                         else
1624                                 *ret = begin + num;
1625                         return term;
1626                 }
1627                 return spec;
1628         }
1629         num = strtol(spec, &term, 10);
1630         if (term != spec) {
1631                 *ret = num;
1632                 return term;
1633         }
1634         if (spec[0] != '/')
1635                 return spec;
1636
1637         /* it could be a regexp of form /.../ */
1638         for (term = (char*) spec + 1; *term && *term != '/'; term++) {
1639                 if (*term == '\\')
1640                         term++;
1641         }
1642         if (*term != '/')
1643                 return spec;
1644
1645         /* try [spec+1 .. term-1] as regexp */
1646         *term = 0;
1647         begin--; /* input is in human terms */
1648         line = nth_line(sb, begin);
1649
1650         if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
1651             !(reg_error = regexec(&regexp, line, 1, match, 0))) {
1652                 const char *cp = line + match[0].rm_so;
1653                 const char *nline;
1654
1655                 while (begin++ < lno) {
1656                         nline = nth_line(sb, begin);
1657                         if (line <= cp && cp < nline)
1658                                 break;
1659                         line = nline;
1660                 }
1661                 *ret = begin;
1662                 regfree(&regexp);
1663                 *term++ = '/';
1664                 return term;
1665         }
1666         else {
1667                 char errbuf[1024];
1668                 regerror(reg_error, &regexp, errbuf, 1024);
1669                 die("-L parameter '%s': %s", spec + 1, errbuf);
1670         }
1671 }
1672
1673 static void prepare_blame_range(struct scoreboard *sb,
1674                                 const char *bottomtop,
1675                                 long lno,
1676                                 long *bottom, long *top)
1677 {
1678         const char *term;
1679
1680         term = parse_loc(bottomtop, sb, lno, 1, bottom);
1681         if (*term == ',') {
1682                 term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
1683                 if (*term)
1684                         usage(blame_usage);
1685         }
1686         if (*term)
1687                 usage(blame_usage);
1688 }
1689
1690 static int git_blame_config(const char *var, const char *value)
1691 {
1692         if (!strcmp(var, "blame.showroot")) {
1693                 show_root = git_config_bool(var, value);
1694                 return 0;
1695         }
1696         if (!strcmp(var, "blame.blankboundary")) {
1697                 blank_boundary = git_config_bool(var, value);
1698                 return 0;
1699         }
1700         return git_default_config(var, value);
1701 }
1702
1703 int cmd_blame(int argc, const char **argv, const char *prefix)
1704 {
1705         struct rev_info revs;
1706         const char *path;
1707         struct scoreboard sb;
1708         struct origin *o;
1709         struct blame_entry *ent;
1710         int i, seen_dashdash, unk, opt;
1711         long bottom, top, lno;
1712         int output_option = 0;
1713         const char *revs_file = NULL;
1714         const char *final_commit_name = NULL;
1715         char type[10];
1716         const char *bottomtop = NULL;
1717
1718         git_config(git_blame_config);
1719         save_commit_buffer = 0;
1720
1721         opt = 0;
1722         seen_dashdash = 0;
1723         for (unk = i = 1; i < argc; i++) {
1724                 const char *arg = argv[i];
1725                 if (*arg != '-')
1726                         break;
1727                 else if (!strcmp("-b", arg))
1728                         blank_boundary = 1;
1729                 else if (!strcmp("--root", arg))
1730                         show_root = 1;
1731                 else if (!strcmp("-c", arg))
1732                         output_option |= OUTPUT_ANNOTATE_COMPAT;
1733                 else if (!strcmp("-t", arg))
1734                         output_option |= OUTPUT_RAW_TIMESTAMP;
1735                 else if (!strcmp("-l", arg))
1736                         output_option |= OUTPUT_LONG_OBJECT_NAME;
1737                 else if (!strcmp("-S", arg) && ++i < argc)
1738                         revs_file = argv[i];
1739                 else if (!strncmp("-M", arg, 2)) {
1740                         opt |= PICKAXE_BLAME_MOVE;
1741                         blame_move_score = parse_score(arg+2);
1742                 }
1743                 else if (!strncmp("-C", arg, 2)) {
1744                         if (opt & PICKAXE_BLAME_COPY)
1745                                 opt |= PICKAXE_BLAME_COPY_HARDER;
1746                         opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
1747                         blame_copy_score = parse_score(arg+2);
1748                 }
1749                 else if (!strncmp("-L", arg, 2)) {
1750                         if (!arg[2]) {
1751                                 if (++i >= argc)
1752                                         usage(blame_usage);
1753                                 arg = argv[i];
1754                         }
1755                         else
1756                                 arg += 2;
1757                         if (bottomtop)
1758                                 die("More than one '-L n,m' option given");
1759                         bottomtop = arg;
1760                 }
1761                 else if (!strcmp("--incremental", arg))
1762                         incremental = 1;
1763                 else if (!strcmp("--score-debug", arg))
1764                         output_option |= OUTPUT_SHOW_SCORE;
1765                 else if (!strcmp("-f", arg) ||
1766                          !strcmp("--show-name", arg))
1767                         output_option |= OUTPUT_SHOW_NAME;
1768                 else if (!strcmp("-n", arg) ||
1769                          !strcmp("--show-number", arg))
1770                         output_option |= OUTPUT_SHOW_NUMBER;
1771                 else if (!strcmp("-p", arg) ||
1772                          !strcmp("--porcelain", arg))
1773                         output_option |= OUTPUT_PORCELAIN;
1774                 else if (!strcmp("--", arg)) {
1775                         seen_dashdash = 1;
1776                         i++;
1777                         break;
1778                 }
1779                 else
1780                         argv[unk++] = arg;
1781         }
1782
1783         if (!incremental)
1784                 setup_pager();
1785
1786         if (!blame_move_score)
1787                 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
1788         if (!blame_copy_score)
1789                 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
1790
1791         /* We have collected options unknown to us in argv[1..unk]
1792          * which are to be passed to revision machinery if we are
1793          * going to do the "bottom" procesing.
1794          *
1795          * The remaining are:
1796          *
1797          * (1) if seen_dashdash, its either
1798          *     "-options -- <path>" or
1799          *     "-options -- <path> <rev>".
1800          *     but the latter is allowed only if there is no
1801          *     options that we passed to revision machinery.
1802          *
1803          * (2) otherwise, we may have "--" somewhere later and
1804          *     might be looking at the first one of multiple 'rev'
1805          *     parameters (e.g. " master ^next ^maint -- path").
1806          *     See if there is a dashdash first, and give the
1807          *     arguments before that to revision machinery.
1808          *     After that there must be one 'path'.
1809          *
1810          * (3) otherwise, its one of the three:
1811          *     "-options <path> <rev>"
1812          *     "-options <rev> <path>"
1813          *     "-options <path>"
1814          *     but again the first one is allowed only if
1815          *     there is no options that we passed to revision
1816          *     machinery.
1817          */
1818
1819         if (seen_dashdash) {
1820                 /* (1) */
1821                 if (argc <= i)
1822                         usage(blame_usage);
1823                 path = add_prefix(prefix, argv[i]);
1824                 if (i + 1 == argc - 1) {
1825                         if (unk != 1)
1826                                 usage(blame_usage);
1827                         argv[unk++] = argv[i + 1];
1828                 }
1829                 else if (i + 1 != argc)
1830                         /* garbage at end */
1831                         usage(blame_usage);
1832         }
1833         else {
1834                 int j;
1835                 for (j = i; !seen_dashdash && j < argc; j++)
1836                         if (!strcmp(argv[j], "--"))
1837                                 seen_dashdash = j;
1838                 if (seen_dashdash) {
1839                         if (seen_dashdash + 1 != argc - 1)
1840                                 usage(blame_usage);
1841                         path = add_prefix(prefix, argv[seen_dashdash + 1]);
1842                         for (j = i; j < seen_dashdash; j++)
1843                                 argv[unk++] = argv[j];
1844                 }
1845                 else {
1846                         /* (3) */
1847                         path = add_prefix(prefix, argv[i]);
1848                         if (i + 1 == argc - 1) {
1849                                 final_commit_name = argv[i + 1];
1850
1851                                 /* if (unk == 1) we could be getting
1852                                  * old-style
1853                                  */
1854                                 if (unk == 1 && !has_path_in_work_tree(path)) {
1855                                         path = add_prefix(prefix, argv[i + 1]);
1856                                         final_commit_name = argv[i];
1857                                 }
1858                         }
1859                         else if (i != argc - 1)
1860                                 usage(blame_usage); /* garbage at end */
1861
1862                         if (!has_path_in_work_tree(path))
1863                                 die("cannot stat path %s: %s",
1864                                     path, strerror(errno));
1865                 }
1866         }
1867
1868         if (final_commit_name)
1869                 argv[unk++] = final_commit_name;
1870
1871         /* Now we got rev and path.  We do not want the path pruning
1872          * but we may want "bottom" processing.
1873          */
1874         argv[unk++] = "--"; /* terminate the rev name */
1875         argv[unk] = NULL;
1876
1877         init_revisions(&revs, NULL);
1878         setup_revisions(unk, argv, &revs, "HEAD");
1879         memset(&sb, 0, sizeof(sb));
1880
1881         /* There must be one and only one positive commit in the
1882          * revs->pending array.
1883          */
1884         for (i = 0; i < revs.pending.nr; i++) {
1885                 struct object *obj = revs.pending.objects[i].item;
1886                 if (obj->flags & UNINTERESTING)
1887                         continue;
1888                 while (obj->type == OBJ_TAG)
1889                         obj = deref_tag(obj, NULL, 0);
1890                 if (obj->type != OBJ_COMMIT)
1891                         die("Non commit %s?",
1892                             revs.pending.objects[i].name);
1893                 if (sb.final)
1894                         die("More than one commit to dig from %s and %s?",
1895                             revs.pending.objects[i].name,
1896                             final_commit_name);
1897                 sb.final = (struct commit *) obj;
1898                 final_commit_name = revs.pending.objects[i].name;
1899         }
1900
1901         if (!sb.final) {
1902                 /* "--not A B -- path" without anything positive */
1903                 unsigned char head_sha1[20];
1904
1905                 final_commit_name = "HEAD";
1906                 if (get_sha1(final_commit_name, head_sha1))
1907                         die("No such ref: HEAD");
1908                 sb.final = lookup_commit_reference(head_sha1);
1909                 add_pending_object(&revs, &(sb.final->object), "HEAD");
1910         }
1911
1912         /* If we have bottom, this will mark the ancestors of the
1913          * bottom commits we would reach while traversing as
1914          * uninteresting.
1915          */
1916         prepare_revision_walk(&revs);
1917
1918         o = get_origin(&sb, sb.final, path);
1919         if (fill_blob_sha1(o))
1920                 die("no such path %s in %s", path, final_commit_name);
1921
1922         sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
1923         num_read_blob++;
1924         lno = prepare_lines(&sb);
1925
1926         bottom = top = 0;
1927         if (bottomtop)
1928                 prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);
1929         if (bottom && top && top < bottom) {
1930                 long tmp;
1931                 tmp = top; top = bottom; bottom = tmp;
1932         }
1933         if (bottom < 1)
1934                 bottom = 1;
1935         if (top < 1)
1936                 top = lno;
1937         bottom--;
1938         if (lno < top)
1939                 die("file %s has only %lu lines", path, lno);
1940
1941         ent = xcalloc(1, sizeof(*ent));
1942         ent->lno = bottom;
1943         ent->num_lines = top - bottom;
1944         ent->suspect = o;
1945         ent->s_lno = bottom;
1946
1947         sb.ent = ent;
1948         sb.path = path;
1949
1950         if (revs_file && read_ancestry(revs_file))
1951                 die("reading graft file %s failed: %s",
1952                     revs_file, strerror(errno));
1953
1954         assign_blame(&sb, &revs, opt);
1955
1956         if (incremental)
1957                 return 0;
1958
1959         coalesce(&sb);
1960
1961         if (!(output_option & OUTPUT_PORCELAIN))
1962                 find_alignment(&sb, &output_option);
1963
1964         output(&sb, output_option);
1965         free((void *)sb.final_buf);
1966         for (ent = sb.ent; ent; ) {
1967                 struct blame_entry *e = ent->next;
1968                 free(ent);
1969                 ent = e;
1970         }
1971
1972         if (DEBUG) {
1973                 printf("num read blob: %d\n", num_read_blob);
1974                 printf("num get patch: %d\n", num_get_patch);
1975                 printf("num commits: %d\n", num_commits);
1976         }
1977         return 0;
1978 }