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