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