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] [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                  Find line movements within the file\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
  38 #define DEBUG 0
  39
  40 #define PICKAXE_BLAME_MOVE              01
  41
  42 /* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
  43 #define METAINFO_SHOWN          (1u<<12)
  44 #define MORE_THAN_ONE_PATH      (1u<<13)
  45
  46 /*
  47  * One blob in a commit
  48  */
  49 struct origin {
  50         struct commit *commit;
  51         unsigned char blob_sha1[20];
  52         char path[FLEX_ARRAY];
  53 };
  54
  55 struct blame_entry {
  56         struct blame_entry *prev;
  57         struct blame_entry *next;
  58
  59         /* the first line of this group in the final image;
  60          * internally all line numbers are 0 based.
  61          */
  62         int lno;
  63
  64         /* how many lines this group has */
  65         int num_lines;
  66
  67         /* the commit that introduced this group into the final image */
  68         struct origin *suspect;
  69
  70         /* true if the suspect is truly guilty; false while we have not
  71          * checked if the group came from one of its parents.
  72          */
  73         char guilty;
  74
  75         /* the line number of the first line of this group in the
  76          * suspect's file; internally all line numbers are 0 based.
  77          */
  78         int s_lno;
  79 };
  80
  81 struct scoreboard {
  82         /* the final commit (i.e. where we started digging from) */
  83         struct commit *final;
  84
  85         const char *path;
  86
  87         /* the contents in the final; pointed into by buf pointers of
  88          * blame_entries
  89          */
  90         const char *final_buf;
  91         unsigned long final_buf_size;
  92
  93         /* linked list of blames */
  94         struct blame_entry *ent;
  95
  96         int num_lines;
  97         int *lineno;
  98 };
  99
 100 static void coalesce(struct scoreboard *sb)
 101 {
 102         struct blame_entry *ent, *next;
 103
 104         for (ent = sb->ent; ent && (next = ent->next); ent = next) {
 105                 if (ent->suspect == next->suspect &&
 106                     ent->guilty == next->guilty &&
 107                     ent->s_lno + ent->num_lines == next->s_lno) {
 108                         ent->num_lines += next->num_lines;
 109                         ent->next = next->next;
 110                         if (ent->next)
 111                                 ent->next->prev = ent;
 112                         free(next);
 113                         next = ent; /* again */
 114                 }
 115         }
 116 }
 117
 118 static void free_origin(struct origin *o)
 119 {
 120         free(o);
 121 }
 122
 123 static struct origin *find_origin(struct scoreboard *sb,
 124                                   struct commit *commit,
 125                                   const char *path)
 126 {
 127         struct blame_entry *ent;
 128         struct origin *o;
 129         unsigned mode;
 130         char type[10];
 131
 132         for (ent = sb->ent; ent; ent = ent->next) {
 133                 if (ent->suspect->commit == commit &&
 134                     !strcmp(ent->suspect->path, path))
 135                         return ent->suspect;
 136         }
 137
 138         o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
 139         o->commit = commit;
 140         strcpy(o->path, path);
 141         if (get_tree_entry(commit->object.sha1, path, o->blob_sha1, &mode))
 142                 goto err_out;
 143         if (sha1_object_info(o->blob_sha1, type, NULL) ||
 144             strcmp(type, blob_type))
 145                 goto err_out;
 146         return o;
 147  err_out:
 148         free_origin(o);
 149         return NULL;
 150 }
 151
 152 static struct origin *find_rename(struct scoreboard *sb,
 153                                   struct commit *parent,
 154                                   struct origin *origin)
 155 {
 156         struct origin *porigin = NULL;
 157         struct diff_options diff_opts;
 158         int i;
 159         const char *paths[1];
 160
 161         diff_setup(&diff_opts);
 162         diff_opts.recursive = 1;
 163         diff_opts.detect_rename = DIFF_DETECT_RENAME;
 164         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 165         paths[0] = NULL;
 166         diff_tree_setup_paths(paths, &diff_opts);
 167         if (diff_setup_done(&diff_opts) < 0)
 168                 die("diff-setup");
 169         diff_tree_sha1(origin->commit->tree->object.sha1,
 170                        parent->tree->object.sha1,
 171                        "", &diff_opts);
 172         diffcore_std(&diff_opts);
 173
 174         for (i = 0; i < diff_queued_diff.nr; i++) {
 175                 struct diff_filepair *p = diff_queued_diff.queue[i];
 176                 if (p->status == 'R' && !strcmp(p->one->path, origin->path)) {
 177                         porigin = find_origin(sb, parent, p->two->path);
 178                         break;
 179                 }
 180         }
 181         diff_flush(&diff_opts);
 182         return porigin;
 183 }
 184
 185 struct chunk {
 186         /* line number in postimage; up to but not including this
 187          * line is the same as preimage
 188          */
 189         int same;
 190
 191         /* preimage line number after this chunk */
 192         int p_next;
 193
 194         /* postimage line number after this chunk */
 195         int t_next;
 196 };
 197
 198 struct patch {
 199         struct chunk *chunks;
 200         int num;
 201 };
 202
 203 struct blame_diff_state {
 204         struct xdiff_emit_state xm;
 205         struct patch *ret;
 206         unsigned hunk_post_context;
 207         unsigned hunk_in_pre_context : 1;
 208 };
 209
 210 static void process_u_diff(void *state_, char *line, unsigned long len)
 211 {
 212         struct blame_diff_state *state = state_;
 213         struct chunk *chunk;
 214         int off1, off2, len1, len2, num;
 215
 216         if (DEBUG)
 217                 fprintf(stderr, "%.*s", (int) len, line);
 218
 219         num = state->ret->num;
 220         if (len < 4 || line[0] != '@' || line[1] != '@') {
 221                 if (state->hunk_in_pre_context && line[0] == ' ')
 222                         state->ret->chunks[num - 1].same++;
 223                 else {
 224                         state->hunk_in_pre_context = 0;
 225                         if (line[0] == ' ')
 226                                 state->hunk_post_context++;
 227                         else
 228                                 state->hunk_post_context = 0;
 229                 }
 230                 return;
 231         }
 232
 233         if (num && state->hunk_post_context) {
 234                 chunk = &state->ret->chunks[num - 1];
 235                 chunk->p_next -= state->hunk_post_context;
 236                 chunk->t_next -= state->hunk_post_context;
 237         }
 238         state->ret->num = ++num;
 239         state->ret->chunks = xrealloc(state->ret->chunks,
 240                                       sizeof(struct chunk) * num);
 241         chunk = &state->ret->chunks[num - 1];
 242         if (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {
 243                 state->ret->num--;
 244                 return;
 245         }
 246
 247         /* Line numbers in patch output are one based. */
 248         off1--;
 249         off2--;
 250
 251         chunk->same = len2 ? off2 : (off2 + 1);
 252
 253         chunk->p_next = off1 + (len1 ? len1 : 1);
 254         chunk->t_next = chunk->same + len2;
 255         state->hunk_in_pre_context = 1;
 256         state->hunk_post_context = 0;
 257 }
 258
 259 static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
 260                                     int context)
 261 {
 262         struct blame_diff_state state;
 263         xpparam_t xpp;
 264         xdemitconf_t xecfg;
 265         xdemitcb_t ecb;
 266
 267         xpp.flags = XDF_NEED_MINIMAL;
 268         xecfg.ctxlen = context;
 269         xecfg.flags = 0;
 270         ecb.outf = xdiff_outf;
 271         ecb.priv = &state;
 272         memset(&state, 0, sizeof(state));
 273         state.xm.consume = process_u_diff;
 274         state.ret = xmalloc(sizeof(struct patch));
 275         state.ret->chunks = NULL;
 276         state.ret->num = 0;
 277
 278         xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);
 279
 280         if (state.ret->num) {
 281                 struct chunk *chunk;
 282                 chunk = &state.ret->chunks[state.ret->num - 1];
 283                 chunk->p_next -= state.hunk_post_context;
 284                 chunk->t_next -= state.hunk_post_context;
 285         }
 286         return state.ret;
 287 }
 288
 289 static struct patch *get_patch(struct origin *parent, struct origin *origin)
 290 {
 291         mmfile_t file_p, file_o;
 292         char type[10];
 293         char *blob_p, *blob_o;
 294         struct patch *patch;
 295
 296         if (DEBUG) fprintf(stderr, "get patch %.8s %.8s\n",
 297                            sha1_to_hex(parent->commit->object.sha1),
 298                            sha1_to_hex(origin->commit->object.sha1));
 299
 300         blob_p = read_sha1_file(parent->blob_sha1, type,
 301                                 (unsigned long *) &file_p.size);
 302         blob_o = read_sha1_file(origin->blob_sha1, type,
 303                                 (unsigned long *) &file_o.size);
 304         file_p.ptr = blob_p;
 305         file_o.ptr = blob_o;
 306         if (!file_p.ptr || !file_o.ptr) {
 307                 free(blob_p);
 308                 free(blob_o);
 309                 return NULL;
 310         }
 311
 312         patch = compare_buffer(&file_p, &file_o, 0);
 313         free(blob_p);
 314         free(blob_o);
 315         return patch;
 316 }
 317
 318 static void free_patch(struct patch *p)
 319 {
 320         free(p->chunks);
 321         free(p);
 322 }
 323
 324 static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
 325 {
 326         struct blame_entry *ent, *prev = NULL;
 327
 328         for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
 329                 prev = ent;
 330
 331         /* prev, if not NULL, is the last one that is below e */
 332         e->prev = prev;
 333         if (prev) {
 334                 e->next = prev->next;
 335                 prev->next = e;
 336         }
 337         else {
 338                 e->next = sb->ent;
 339                 sb->ent = e;
 340         }
 341         if (e->next)
 342                 e->next->prev = e;
 343 }
 344
 345 static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
 346 {
 347         struct blame_entry *p, *n;
 348         p = dst->prev;
 349         n = dst->next;
 350         memcpy(dst, src, sizeof(*src));
 351         dst->prev = p;
 352         dst->next = n;
 353 }
 354
 355 static const char *nth_line(struct scoreboard *sb, int lno)
 356 {
 357         return sb->final_buf + sb->lineno[lno];
 358 }
 359
 360 static void split_overlap(struct blame_entry split[3],
 361                           struct blame_entry *e,
 362                           int tlno, int plno, int same,
 363                           struct origin *parent)
 364 {
 365         /* it is known that lines between tlno to same came from
 366          * parent, and e has an overlap with that range.  it also is
 367          * known that parent's line plno corresponds to e's line tlno.
 368          *
 369          *                <---- e ----->
 370          *                   <------>
 371          *                   <------------>
 372          *             <------------>
 373          *             <------------------>
 374          *
 375          * Potentially we need to split e into three parts; before
 376          * this chunk, the chunk to be blamed for parent, and after
 377          * that portion.
 378          */
 379         int chunk_end_lno;
 380         memset(split, 0, sizeof(struct blame_entry [3]));
 381
 382         if (e->s_lno < tlno) {
 383                 /* there is a pre-chunk part not blamed on parent */
 384                 split[0].suspect = e->suspect;
 385                 split[0].lno = e->lno;
 386                 split[0].s_lno = e->s_lno;
 387                 split[0].num_lines = tlno - e->s_lno;
 388                 split[1].lno = e->lno + tlno - e->s_lno;
 389                 split[1].s_lno = plno;
 390         }
 391         else {
 392                 split[1].lno = e->lno;
 393                 split[1].s_lno = plno + (e->s_lno - tlno);
 394         }
 395
 396         if (same < e->s_lno + e->num_lines) {
 397                 /* there is a post-chunk part not blamed on parent */
 398                 split[2].suspect = e->suspect;
 399                 split[2].lno = e->lno + (same - e->s_lno);
 400                 split[2].s_lno = e->s_lno + (same - e->s_lno);
 401                 split[2].num_lines = e->s_lno + e->num_lines - same;
 402                 chunk_end_lno = split[2].lno;
 403         }
 404         else
 405                 chunk_end_lno = e->lno + e->num_lines;
 406         split[1].num_lines = chunk_end_lno - split[1].lno;
 407
 408         if (split[1].num_lines < 1)
 409                 return;
 410         split[1].suspect = parent;
 411 }
 412
 413 static void split_blame(struct scoreboard *sb,
 414                         struct blame_entry split[3],
 415                         struct blame_entry *e)
 416 {
 417         struct blame_entry *new_entry;
 418
 419         if (split[0].suspect && split[2].suspect) {
 420                 /* we need to split e into two and add another for parent */
 421                 dup_entry(e, &split[0]);
 422
 423                 new_entry = xmalloc(sizeof(*new_entry));
 424                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 425                 add_blame_entry(sb, new_entry);
 426
 427                 new_entry = xmalloc(sizeof(*new_entry));
 428                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 429                 add_blame_entry(sb, new_entry);
 430         }
 431         else if (!split[0].suspect && !split[2].suspect)
 432                 /* parent covers the entire area */
 433                 dup_entry(e, &split[1]);
 434         else if (split[0].suspect) {
 435                 dup_entry(e, &split[0]);
 436
 437                 new_entry = xmalloc(sizeof(*new_entry));
 438                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 439                 add_blame_entry(sb, new_entry);
 440         }
 441         else {
 442                 dup_entry(e, &split[1]);
 443
 444                 new_entry = xmalloc(sizeof(*new_entry));
 445                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 446                 add_blame_entry(sb, new_entry);
 447         }
 448
 449         if (DEBUG) {
 450                 struct blame_entry *ent;
 451                 int lno = 0, corrupt = 0;
 452
 453                 for (ent = sb->ent; ent; ent = ent->next) {
 454                         if (lno != ent->lno)
 455                                 corrupt = 1;
 456                         if (ent->s_lno < 0)
 457                                 corrupt = 1;
 458                         lno += ent->num_lines;
 459                 }
 460                 if (corrupt) {
 461                         lno = 0;
 462                         for (ent = sb->ent; ent; ent = ent->next) {
 463                                 printf("L %8d l %8d n %8d\n",
 464                                        lno, ent->lno, ent->num_lines);
 465                                 lno = ent->lno + ent->num_lines;
 466                         }
 467                         die("oops");
 468                 }
 469         }
 470 }
 471
 472 static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
 473                           int tlno, int plno, int same,
 474                           struct origin *parent)
 475 {
 476         struct blame_entry split[3];
 477
 478         split_overlap(split, e, tlno, plno, same, parent);
 479         if (!split[1].suspect)
 480                 return;
 481         split_blame(sb, split, e);
 482 }
 483
 484 static int find_last_in_target(struct scoreboard *sb, struct origin *target)
 485 {
 486         struct blame_entry *e;
 487         int last_in_target = -1;
 488
 489         for (e = sb->ent; e; e = e->next) {
 490                 if (e->guilty || e->suspect != target)
 491                         continue;
 492                 if (last_in_target < e->s_lno + e->num_lines)
 493                         last_in_target = e->s_lno + e->num_lines;
 494         }
 495         return last_in_target;
 496 }
 497
 498 static void blame_chunk(struct scoreboard *sb,
 499                         int tlno, int plno, int same,
 500                         struct origin *target, struct origin *parent)
 501 {
 502         struct blame_entry *e, *n;
 503
 504         for (e = sb->ent; e; e = n) {
 505                 n = e->next;
 506                 if (e->guilty || e->suspect != target)
 507                         continue;
 508                 if (same <= e->s_lno)
 509                         continue;
 510                 if (tlno < e->s_lno + e->num_lines)
 511                         blame_overlap(sb, e, tlno, plno, same, parent);
 512         }
 513 }
 514
 515 static int pass_blame_to_parent(struct scoreboard *sb,
 516                                 struct origin *target,
 517                                 struct origin *parent)
 518 {
 519         int i, last_in_target, plno, tlno;
 520         struct patch *patch;
 521
 522         last_in_target = find_last_in_target(sb, target);
 523         if (last_in_target < 0)
 524                 return 1; /* nothing remains for this target */
 525
 526         patch = get_patch(parent, target);
 527         plno = tlno = 0;
 528         for (i = 0; i < patch->num; i++) {
 529                 struct chunk *chunk = &patch->chunks[i];
 530
 531                 if (DEBUG)
 532                         fprintf(stderr,
 533                                 "plno = %d, tlno = %d, "
 534                                 "same as parent up to %d, resync %d and %d\n",
 535                                 plno, tlno,
 536                                 chunk->same, chunk->p_next, chunk->t_next);
 537                 blame_chunk(sb, tlno, plno, chunk->same, target, parent);
 538                 plno = chunk->p_next;
 539                 tlno = chunk->t_next;
 540         }
 541         /* rest (i.e. anything above tlno) are the same as parent */
 542         blame_chunk(sb, tlno, plno, last_in_target, target, parent);
 543
 544         free_patch(patch);
 545         return 0;
 546 }
 547
 548 static void copy_split_if_better(struct blame_entry best_so_far[3],
 549                                  struct blame_entry this[3])
 550 {
 551         if (!this[1].suspect)
 552                 return;
 553         if (best_so_far[1].suspect &&
 554             (this[1].num_lines < best_so_far[1].num_lines))
 555                 return;
 556         memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
 557 }
 558
 559 static void find_copy_in_blob(struct scoreboard *sb,
 560                               struct blame_entry *ent,
 561                               struct origin *parent,
 562                               struct blame_entry split[3],
 563                               mmfile_t *file_p)
 564 {
 565         const char *cp;
 566         int cnt;
 567         mmfile_t file_o;
 568         struct patch *patch;
 569         int i, plno, tlno;
 570
 571         cp = nth_line(sb, ent->lno);
 572         file_o.ptr = (char*) cp;
 573         cnt = ent->num_lines;
 574
 575         while (cnt && cp < sb->final_buf + sb->final_buf_size) {
 576                 if (*cp++ == '\n')
 577                         cnt--;
 578         }
 579         file_o.size = cp - file_o.ptr;
 580
 581         patch = compare_buffer(file_p, &file_o, 1);
 582
 583         memset(split, 0, sizeof(struct blame_entry [3]));
 584         plno = tlno = 0;
 585         for (i = 0; i < patch->num; i++) {
 586                 struct chunk *chunk = &patch->chunks[i];
 587
 588                 /* tlno to chunk->same are the same as ent */
 589                 if (ent->num_lines <= tlno)
 590                         break;
 591                 if (tlno < chunk->same) {
 592                         struct blame_entry this[3];
 593                         split_overlap(this, ent,
 594                                       tlno + ent->s_lno, plno,
 595                                       chunk->same + ent->s_lno,
 596                                       parent);
 597                         copy_split_if_better(split, this);
 598                 }
 599                 plno = chunk->p_next;
 600                 tlno = chunk->t_next;
 601         }
 602         free_patch(patch);
 603 }
 604
 605 static int find_move_in_parent(struct scoreboard *sb,
 606                                struct origin *target,
 607                                struct origin *parent)
 608 {
 609         int last_in_target;
 610         struct blame_entry *ent, split[3];
 611         mmfile_t file_p;
 612         char type[10];
 613         char *blob_p;
 614
 615         last_in_target = find_last_in_target(sb, target);
 616         if (last_in_target < 0)
 617                 return 1; /* nothing remains for this target */
 618
 619         blob_p = read_sha1_file(parent->blob_sha1, type,
 620                                 (unsigned long *) &file_p.size);
 621         file_p.ptr = blob_p;
 622         if (!file_p.ptr) {
 623                 free(blob_p);
 624                 return 0;
 625         }
 626
 627         for (ent = sb->ent; ent; ent = ent->next) {
 628                 if (ent->suspect != target || ent->guilty)
 629                         continue;
 630                 find_copy_in_blob(sb, ent, parent, split, &file_p);
 631                 if (split[1].suspect)
 632                         split_blame(sb, split, ent);
 633         }
 634         free(blob_p);
 635         return 0;
 636 }
 637
 638 #define MAXPARENT 16
 639
 640 static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
 641 {
 642         int i;
 643         struct commit *commit = origin->commit;
 644         struct commit_list *parent;
 645         struct origin *parent_origin[MAXPARENT], *porigin;
 646
 647         memset(parent_origin, 0, sizeof(parent_origin));
 648         for (i = 0, parent = commit->parents;
 649              i < MAXPARENT && parent;
 650              parent = parent->next, i++) {
 651                 struct commit *p = parent->item;
 652
 653                 if (parse_commit(p))
 654                         continue;
 655                 porigin = find_origin(sb, parent->item, origin->path);
 656                 if (!porigin)
 657                         porigin = find_rename(sb, parent->item, origin);
 658                 if (!porigin)
 659                         continue;
 660                 if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
 661                         struct blame_entry *e;
 662                         for (e = sb->ent; e; e = e->next)
 663                                 if (e->suspect == origin)
 664                                         e->suspect = porigin;
 665                         /* now everything blamed for origin is blamed for
 666                          * porigin, we do not need to keep it anymore.
 667                          * Do not free porigin (or the ones we got from
 668                          * earlier round); they may still be used elsewhere.
 669                          */
 670                         free_origin(origin);
 671                         return;
 672                 }
 673                 parent_origin[i] = porigin;
 674         }
 675
 676         for (i = 0, parent = commit->parents;
 677              i < MAXPARENT && parent;
 678              parent = parent->next, i++) {
 679                 struct origin *porigin = parent_origin[i];
 680                 if (!porigin)
 681                         continue;
 682                 if (pass_blame_to_parent(sb, origin, porigin))
 683                         return;
 684         }
 685
 686         /*
 687          * Optionally run "miff" to find moves in parents' files here.
 688          */
 689         if (opt & PICKAXE_BLAME_MOVE)
 690                 for (i = 0, parent = commit->parents;
 691                      i < MAXPARENT && parent;
 692                      parent = parent->next, i++) {
 693                         struct origin *porigin = parent_origin[i];
 694                         if (!porigin)
 695                                 continue;
 696                         if (find_move_in_parent(sb, origin, porigin))
 697                                 return;
 698                 }
 699
 700 }
 701
 702 static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)
 703 {
 704         while (1) {
 705                 struct blame_entry *ent;
 706                 struct commit *commit;
 707                 struct origin *suspect = NULL;
 708
 709                 /* find one suspect to break down */
 710                 for (ent = sb->ent; !suspect && ent; ent = ent->next)
 711                         if (!ent->guilty)
 712                                 suspect = ent->suspect;
 713                 if (!suspect)
 714                         return; /* all done */
 715
 716                 commit = suspect->commit;
 717                 parse_commit(commit);
 718                 if (!(commit->object.flags & UNINTERESTING) &&
 719                     !(revs->max_age != -1 && commit->date  < revs->max_age))
 720                         pass_blame(sb, suspect, opt);
 721
 722                 /* Take responsibility for the remaining entries */
 723                 for (ent = sb->ent; ent; ent = ent->next)
 724                         if (ent->suspect == suspect)
 725                                 ent->guilty = 1;
 726         }
 727 }
 728
 729 static const char *format_time(unsigned long time, const char *tz_str,
 730                                int show_raw_time)
 731 {
 732         static char time_buf[128];
 733         time_t t = time;
 734         int minutes, tz;
 735         struct tm *tm;
 736
 737         if (show_raw_time) {
 738                 sprintf(time_buf, "%lu %s", time, tz_str);
 739                 return time_buf;
 740         }
 741
 742         tz = atoi(tz_str);
 743         minutes = tz < 0 ? -tz : tz;
 744         minutes = (minutes / 100)*60 + (minutes % 100);
 745         minutes = tz < 0 ? -minutes : minutes;
 746         t = time + minutes * 60;
 747         tm = gmtime(&t);
 748
 749         strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
 750         strcat(time_buf, tz_str);
 751         return time_buf;
 752 }
 753
 754 struct commit_info
 755 {
 756         char *author;
 757         char *author_mail;
 758         unsigned long author_time;
 759         char *author_tz;
 760
 761         /* filled only when asked for details */
 762         char *committer;
 763         char *committer_mail;
 764         unsigned long committer_time;
 765         char *committer_tz;
 766
 767         char *summary;
 768 };
 769
 770 static void get_ac_line(const char *inbuf, const char *what,
 771                         int bufsz, char *person, char **mail,
 772                         unsigned long *time, char **tz)
 773 {
 774         int len;
 775         char *tmp, *endp;
 776
 777         tmp = strstr(inbuf, what);
 778         if (!tmp)
 779                 goto error_out;
 780         tmp += strlen(what);
 781         endp = strchr(tmp, '\n');
 782         if (!endp)
 783                 len = strlen(tmp);
 784         else
 785                 len = endp - tmp;
 786         if (bufsz <= len) {
 787         error_out:
 788                 /* Ugh */
 789                 person = *mail = *tz = "(unknown)";
 790                 *time = 0;
 791                 return;
 792         }
 793         memcpy(person, tmp, len);
 794
 795         tmp = person;
 796         tmp += len;
 797         *tmp = 0;
 798         while (*tmp != ' ')
 799                 tmp--;
 800         *tz = tmp+1;
 801
 802         *tmp = 0;
 803         while (*tmp != ' ')
 804                 tmp--;
 805         *time = strtoul(tmp, NULL, 10);
 806
 807         *tmp = 0;
 808         while (*tmp != ' ')
 809                 tmp--;
 810         *mail = tmp + 1;
 811         *tmp = 0;
 812 }
 813
 814 static void get_commit_info(struct commit *commit,
 815                             struct commit_info *ret,
 816                             int detailed)
 817 {
 818         int len;
 819         char *tmp, *endp;
 820         static char author_buf[1024];
 821         static char committer_buf[1024];
 822         static char summary_buf[1024];
 823
 824         ret->author = author_buf;
 825         get_ac_line(commit->buffer, "\nauthor ",
 826                     sizeof(author_buf), author_buf, &ret->author_mail,
 827                     &ret->author_time, &ret->author_tz);
 828
 829         if (!detailed)
 830                 return;
 831
 832         ret->committer = committer_buf;
 833         get_ac_line(commit->buffer, "\ncommitter ",
 834                     sizeof(committer_buf), committer_buf, &ret->committer_mail,
 835                     &ret->committer_time, &ret->committer_tz);
 836
 837         ret->summary = summary_buf;
 838         tmp = strstr(commit->buffer, "\n\n");
 839         if (!tmp) {
 840         error_out:
 841                 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
 842                 return;
 843         }
 844         tmp += 2;
 845         endp = strchr(tmp, '\n');
 846         if (!endp)
 847                 goto error_out;
 848         len = endp - tmp;
 849         if (len >= sizeof(summary_buf))
 850                 goto error_out;
 851         memcpy(summary_buf, tmp, len);
 852         summary_buf[len] = 0;
 853 }
 854
 855 #define OUTPUT_ANNOTATE_COMPAT  001
 856 #define OUTPUT_LONG_OBJECT_NAME 002
 857 #define OUTPUT_RAW_TIMESTAMP    004
 858 #define OUTPUT_PORCELAIN        010
 859 #define OUTPUT_SHOW_NAME        020
 860 #define OUTPUT_SHOW_NUMBER      040
 861
 862 static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
 863 {
 864         int cnt;
 865         const char *cp;
 866         struct origin *suspect = ent->suspect;
 867         char hex[41];
 868
 869         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
 870         printf("%s%c%d %d %d\n",
 871                hex,
 872                ent->guilty ? ' ' : '*', // purely for debugging
 873                ent->s_lno + 1,
 874                ent->lno + 1,
 875                ent->num_lines);
 876         if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
 877                 struct commit_info ci;
 878                 suspect->commit->object.flags |= METAINFO_SHOWN;
 879                 get_commit_info(suspect->commit, &ci, 1);
 880                 printf("author %s\n", ci.author);
 881                 printf("author-mail %s\n", ci.author_mail);
 882                 printf("author-time %lu\n", ci.author_time);
 883                 printf("author-tz %s\n", ci.author_tz);
 884                 printf("committer %s\n", ci.committer);
 885                 printf("committer-mail %s\n", ci.committer_mail);
 886                 printf("committer-time %lu\n", ci.committer_time);
 887                 printf("committer-tz %s\n", ci.committer_tz);
 888                 printf("filename %s\n", suspect->path);
 889                 printf("summary %s\n", ci.summary);
 890         }
 891         else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
 892                 printf("filename %s\n", suspect->path);
 893
 894         cp = nth_line(sb, ent->lno);
 895         for (cnt = 0; cnt < ent->num_lines; cnt++) {
 896                 char ch;
 897                 if (cnt)
 898                         printf("%s %d %d\n", hex,
 899                                ent->s_lno + 1 + cnt,
 900                                ent->lno + 1 + cnt);
 901                 putchar('\t');
 902                 do {
 903                         ch = *cp++;
 904                         putchar(ch);
 905                 } while (ch != '\n' &&
 906                          cp < sb->final_buf + sb->final_buf_size);
 907         }
 908 }
 909
 910 static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
 911 {
 912         int cnt;
 913         const char *cp;
 914         struct origin *suspect = ent->suspect;
 915         struct commit_info ci;
 916         char hex[41];
 917         int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
 918
 919         get_commit_info(suspect->commit, &ci, 1);
 920         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
 921
 922         cp = nth_line(sb, ent->lno);
 923         for (cnt = 0; cnt < ent->num_lines; cnt++) {
 924                 char ch;
 925
 926                 printf("%.*s", (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8, hex);
 927                 if (opt & OUTPUT_ANNOTATE_COMPAT)
 928                         printf("\t(%10s\t%10s\t%d)", ci.author,
 929                                format_time(ci.author_time, ci.author_tz,
 930                                            show_raw_time),
 931                                ent->lno + 1 + cnt);
 932                 else {
 933                         if (opt & OUTPUT_SHOW_NAME)
 934                                 printf(" %-*.*s", longest_file, longest_file,
 935                                        suspect->path);
 936                         if (opt & OUTPUT_SHOW_NUMBER)
 937                                 printf(" %*d", max_orig_digits,
 938                                        ent->s_lno + 1 + cnt);
 939                         printf(" (%-*.*s %10s %*d) ",
 940                                longest_author, longest_author, ci.author,
 941                                format_time(ci.author_time, ci.author_tz,
 942                                            show_raw_time),
 943                                max_digits, ent->lno + 1 + cnt);
 944                 }
 945                 do {
 946                         ch = *cp++;
 947                         putchar(ch);
 948                 } while (ch != '\n' &&
 949                          cp < sb->final_buf + sb->final_buf_size);
 950         }
 951 }
 952
 953 static void output(struct scoreboard *sb, int option)
 954 {
 955         struct blame_entry *ent;
 956
 957         if (option & OUTPUT_PORCELAIN) {
 958                 for (ent = sb->ent; ent; ent = ent->next) {
 959                         struct blame_entry *oth;
 960                         struct origin *suspect = ent->suspect;
 961                         struct commit *commit = suspect->commit;
 962                         if (commit->object.flags & MORE_THAN_ONE_PATH)
 963                                 continue;
 964                         for (oth = ent->next; oth; oth = oth->next) {
 965                                 if ((oth->suspect->commit != commit) ||
 966                                     !strcmp(oth->suspect->path, suspect->path))
 967                                         continue;
 968                                 commit->object.flags |= MORE_THAN_ONE_PATH;
 969                                 break;
 970                         }
 971                 }
 972         }
 973
 974         for (ent = sb->ent; ent; ent = ent->next) {
 975                 if (option & OUTPUT_PORCELAIN)
 976                         emit_porcelain(sb, ent);
 977                 else
 978                         emit_other(sb, ent, option);
 979         }
 980 }
 981
 982 static int prepare_lines(struct scoreboard *sb)
 983 {
 984         const char *buf = sb->final_buf;
 985         unsigned long len = sb->final_buf_size;
 986         int num = 0, incomplete = 0, bol = 1;
 987
 988         if (len && buf[len-1] != '\n')
 989                 incomplete++; /* incomplete line at the end */
 990         while (len--) {
 991                 if (bol) {
 992                         sb->lineno = xrealloc(sb->lineno,
 993                                               sizeof(int* ) * (num + 1));
 994                         sb->lineno[num] = buf - sb->final_buf;
 995                         bol = 0;
 996                 }
 997                 if (*buf++ == '\n') {
 998                         num++;
 999                         bol = 1;
1000                 }
1001         }
1002         sb->num_lines = num + incomplete;
1003         return sb->num_lines;
1004 }
1005
1006 static int read_ancestry(const char *graft_file)
1007 {
1008         FILE *fp = fopen(graft_file, "r");
1009         char buf[1024];
1010         if (!fp)
1011                 return -1;
1012         while (fgets(buf, sizeof(buf), fp)) {
1013                 /* The format is just "Commit Parent1 Parent2 ...\n" */
1014                 int len = strlen(buf);
1015                 struct commit_graft *graft = read_graft_line(buf, len);
1016                 register_commit_graft(graft, 0);
1017         }
1018         fclose(fp);
1019         return 0;
1020 }
1021
1022 static int lineno_width(int lines)
1023 {
1024         int i, width;
1025
1026         for (width = 1, i = 10; i <= lines + 1; width++)
1027                 i *= 10;
1028         return width;
1029 }
1030
1031 static void find_alignment(struct scoreboard *sb, int *option)
1032 {
1033         int longest_src_lines = 0;
1034         int longest_dst_lines = 0;
1035         struct blame_entry *e;
1036
1037         for (e = sb->ent; e; e = e->next) {
1038                 struct origin *suspect = e->suspect;
1039                 struct commit_info ci;
1040                 int num;
1041
1042                 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1043                         suspect->commit->object.flags |= METAINFO_SHOWN;
1044                         get_commit_info(suspect->commit, &ci, 1);
1045                         if (strcmp(suspect->path, sb->path))
1046                                 *option |= OUTPUT_SHOW_NAME;
1047                         num = strlen(suspect->path);
1048                         if (longest_file < num)
1049                                 longest_file = num;
1050                         num = strlen(ci.author);
1051                         if (longest_author < num)
1052                                 longest_author = num;
1053                 }
1054                 num = e->s_lno + e->num_lines;
1055                 if (longest_src_lines < num)
1056                         longest_src_lines = num;
1057                 num = e->lno + e->num_lines;
1058                 if (longest_dst_lines < num)
1059                         longest_dst_lines = num;
1060         }
1061         max_orig_digits = lineno_width(longest_src_lines);
1062         max_digits = lineno_width(longest_dst_lines);
1063 }
1064
1065 static int has_path_in_work_tree(const char *path)
1066 {
1067         struct stat st;
1068         return !lstat(path, &st);
1069 }
1070
1071 int cmd_pickaxe(int argc, const char **argv, const char *prefix)
1072 {
1073         struct rev_info revs;
1074         const char *path;
1075         struct scoreboard sb;
1076         struct origin *o;
1077         struct blame_entry *ent;
1078         int i, seen_dashdash, unk, opt;
1079         long bottom, top, lno;
1080         int output_option = 0;
1081         const char *revs_file = NULL;
1082         const char *final_commit_name = NULL;
1083         char type[10];
1084
1085         opt = 0;
1086         bottom = top = 0;
1087         seen_dashdash = 0;
1088         for (unk = i = 1; i < argc; i++) {
1089                 const char *arg = argv[i];
1090                 if (*arg != '-')
1091                         break;
1092                 else if (!strcmp("-c", arg))
1093                         output_option |= OUTPUT_ANNOTATE_COMPAT;
1094                 else if (!strcmp("-t", arg))
1095                         output_option |= OUTPUT_RAW_TIMESTAMP;
1096                 else if (!strcmp("-l", arg))
1097                         output_option |= OUTPUT_LONG_OBJECT_NAME;
1098                 else if (!strcmp("-S", arg) && ++i < argc)
1099                         revs_file = argv[i];
1100                 else if (!strcmp("-M", arg))
1101                         opt |= PICKAXE_BLAME_MOVE;
1102                 else if (!strcmp("-L", arg) && ++i < argc) {
1103                         char *term;
1104                         arg = argv[i];
1105                         if (bottom || top)
1106                                 die("More than one '-L n,m' option given");
1107                         bottom = strtol(arg, &term, 10);
1108                         if (*term == ',') {
1109                                 top = strtol(term + 1, &term, 10);
1110                                 if (*term)
1111                                         usage(pickaxe_usage);
1112                         }
1113                         if (bottom && top && top < bottom) {
1114                                 unsigned long tmp;
1115                                 tmp = top; top = bottom; bottom = tmp;
1116                         }
1117                 }
1118                 else if (!strcmp("-f", arg) ||
1119                          !strcmp("--show-name", arg))
1120                         output_option |= OUTPUT_SHOW_NAME;
1121                 else if (!strcmp("-n", arg) ||
1122                          !strcmp("--show-number", arg))
1123                         output_option |= OUTPUT_SHOW_NUMBER;
1124                 else if (!strcmp("-p", arg) ||
1125                          !strcmp("--porcelain", arg))
1126                         output_option |= OUTPUT_PORCELAIN;
1127                 else if (!strcmp("--", arg)) {
1128                         seen_dashdash = 1;
1129                         i++;
1130                         break;
1131                 }
1132                 else
1133                         argv[unk++] = arg;
1134         }
1135
1136         /* We have collected options unknown to us in argv[1..unk]
1137          * which are to be passed to revision machinery if we are
1138          * going to do the "bottom" procesing.
1139          *
1140          * The remaining are:
1141          *
1142          * (1) if seen_dashdash, its either
1143          *     "-options -- <path>" or
1144          *     "-options -- <path> <rev>".
1145          *     but the latter is allowed only if there is no
1146          *     options that we passed to revision machinery.
1147          *
1148          * (2) otherwise, we may have "--" somewhere later and
1149          *     might be looking at the first one of multiple 'rev'
1150          *     parameters (e.g. " master ^next ^maint -- path").
1151          *     See if there is a dashdash first, and give the
1152          *     arguments before that to revision machinery.
1153          *     After that there must be one 'path'.
1154          *
1155          * (3) otherwise, its one of the three:
1156          *     "-options <path> <rev>"
1157          *     "-options <rev> <path>"
1158          *     "-options <path>"
1159          *     but again the first one is allowed only if
1160          *     there is no options that we passed to revision
1161          *     machinery.
1162          */
1163
1164         if (seen_dashdash) {
1165                 /* (1) */
1166                 if (argc <= i)
1167                         usage(pickaxe_usage);
1168                 path = argv[i];
1169                 if (i + 1 == argc - 1) {
1170                         if (unk != 1)
1171                                 usage(pickaxe_usage);
1172                         argv[unk++] = argv[i + 1];
1173                 }
1174                 else if (i + 1 != argc)
1175                         /* garbage at end */
1176                         usage(pickaxe_usage);
1177         }
1178         else {
1179                 int j;
1180                 for (j = i; !seen_dashdash && j < argc; j++)
1181                         if (!strcmp(argv[j], "--"))
1182                                 seen_dashdash = j;
1183                 if (seen_dashdash) {
1184                         if (seen_dashdash + 1 != argc - 1)
1185                                 usage(pickaxe_usage);
1186                         path = argv[seen_dashdash + 1];
1187                         for (j = i; j < seen_dashdash; j++)
1188                                 argv[unk++] = argv[j];
1189                 }
1190                 else {
1191                         /* (3) */
1192                         path = argv[i];
1193                         if (i + 1 == argc - 1) {
1194                                 final_commit_name = argv[i + 1];
1195
1196                                 /* if (unk == 1) we could be getting
1197                                  * old-style
1198                                  */
1199                                 if (unk == 1 && !has_path_in_work_tree(path)) {
1200                                         path = argv[i + 1];
1201                                         final_commit_name = argv[i];
1202                                 }
1203                         }
1204                         else if (i != argc - 1)
1205                                 usage(pickaxe_usage); /* garbage at end */
1206
1207                         if (!has_path_in_work_tree(path))
1208                                 die("cannot stat path %s: %s",
1209                                     path, strerror(errno));
1210                 }
1211         }
1212
1213         if (final_commit_name)
1214                 argv[unk++] = final_commit_name;
1215
1216         /* Now we got rev and path.  We do not want the path pruning
1217          * but we may want "bottom" processing.
1218          */
1219         argv[unk] = NULL;
1220
1221         init_revisions(&revs, NULL);
1222         setup_revisions(unk, argv, &revs, "HEAD");
1223         memset(&sb, 0, sizeof(sb));
1224
1225         /* There must be one and only one positive commit in the
1226          * revs->pending array.
1227          */
1228         for (i = 0; i < revs.pending.nr; i++) {
1229                 struct object *obj = revs.pending.objects[i].item;
1230                 if (obj->flags & UNINTERESTING)
1231                         continue;
1232                 while (obj->type == OBJ_TAG)
1233                         obj = deref_tag(obj, NULL, 0);
1234                 if (obj->type != OBJ_COMMIT)
1235                         die("Non commit %s?",
1236                             revs.pending.objects[i].name);
1237                 if (sb.final)
1238                         die("More than one commit to dig from %s and %s?",
1239                             revs.pending.objects[i].name,
1240                             final_commit_name);
1241                 sb.final = (struct commit *) obj;
1242                 final_commit_name = revs.pending.objects[i].name;
1243         }
1244
1245         if (!sb.final) {
1246                 /* "--not A B -- path" without anything positive */
1247                 unsigned char head_sha1[20];
1248
1249                 final_commit_name = "HEAD";
1250                 if (get_sha1(final_commit_name, head_sha1))
1251                         die("No such ref: HEAD");
1252                 sb.final = lookup_commit_reference(head_sha1);
1253                 add_pending_object(&revs, &(sb.final->object), "HEAD");
1254         }
1255
1256         /* If we have bottom, this will mark the ancestors of the
1257          * bottom commits we would reach while traversing as
1258          * uninteresting.
1259          */
1260         prepare_revision_walk(&revs);
1261
1262         o = find_origin(&sb, sb.final, path);
1263         if (!o)
1264                 die("no such path %s in %s", path, final_commit_name);
1265
1266         sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
1267         lno = prepare_lines(&sb);
1268
1269         if (bottom < 1)
1270                 bottom = 1;
1271         if (top < 1)
1272                 top = lno;
1273         bottom--;
1274         if (lno < top)
1275                 die("file %s has only %lu lines", path, lno);
1276
1277         ent = xcalloc(1, sizeof(*ent));
1278         ent->lno = bottom;
1279         ent->num_lines = top - bottom;
1280         ent->suspect = o;
1281         ent->s_lno = bottom;
1282
1283         sb.ent = ent;
1284         sb.path = path;
1285
1286         if (revs_file && read_ancestry(revs_file))
1287                 die("reading graft file %s failed: %s",
1288                     revs_file, strerror(errno));
1289
1290         assign_blame(&sb, &revs, opt);
1291
1292         coalesce(&sb);
1293
1294         if (!(output_option & OUTPUT_PORCELAIN))
1295                 find_alignment(&sb, &output_option);
1296
1297         output(&sb, output_option);
1298         free((void *)sb.final_buf);
1299         for (ent = sb.ent; ent; ) {
1300                 struct blame_entry *e = ent->next;
1301                 free(ent);
1302                 ent = e;
1303         }
1304         return 0;
1305 }