bisect: make skipped array functions more generic
[git] / builtin-blame.c
1 /*
2  * Blame
3  *
4  * Copyright (c) 2006, Junio C Hamano
5  */
6
7 #include "cache.h"
8 #include "builtin.h"
9 #include "blob.h"
10 #include "commit.h"
11 #include "tag.h"
12 #include "tree-walk.h"
13 #include "diff.h"
14 #include "diffcore.h"
15 #include "revision.h"
16 #include "quote.h"
17 #include "xdiff-interface.h"
18 #include "cache-tree.h"
19 #include "string-list.h"
20 #include "mailmap.h"
21 #include "parse-options.h"
22 #include "utf8.h"
23
24 static char blame_usage[] = "git blame [options] [rev-opts] [rev] [--] file";
25
26 static const char *blame_opt_usage[] = {
27         blame_usage,
28         "",
29         "[rev-opts] are documented in git-rev-list(1)",
30         NULL
31 };
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 static int show_root;
39 static int reverse;
40 static int blank_boundary;
41 static int incremental;
42 static int xdl_opts = XDF_NEED_MINIMAL;
43
44 static enum date_mode blame_date_mode = DATE_ISO8601;
45 static size_t blame_date_width;
46
47 static struct string_list mailmap;
48
49 #ifndef DEBUG
50 #define DEBUG 0
51 #endif
52
53 /* stats */
54 static int num_read_blob;
55 static int num_get_patch;
56 static int num_commits;
57
58 #define PICKAXE_BLAME_MOVE              01
59 #define PICKAXE_BLAME_COPY              02
60 #define PICKAXE_BLAME_COPY_HARDER       04
61 #define PICKAXE_BLAME_COPY_HARDEST      010
62
63 /*
64  * blame for a blame_entry with score lower than these thresholds
65  * is not passed to the parent using move/copy logic.
66  */
67 static unsigned blame_move_score;
68 static unsigned blame_copy_score;
69 #define BLAME_DEFAULT_MOVE_SCORE        20
70 #define BLAME_DEFAULT_COPY_SCORE        40
71
72 /* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
73 #define METAINFO_SHOWN          (1u<<12)
74 #define MORE_THAN_ONE_PATH      (1u<<13)
75
76 /*
77  * One blob in a commit that is being suspected
78  */
79 struct origin {
80         int refcnt;
81         struct origin *previous;
82         struct commit *commit;
83         mmfile_t file;
84         unsigned char blob_sha1[20];
85         char path[FLEX_ARRAY];
86 };
87
88 /*
89  * Given an origin, prepare mmfile_t structure to be used by the
90  * diff machinery
91  */
92 static void fill_origin_blob(struct origin *o, mmfile_t *file)
93 {
94         if (!o->file.ptr) {
95                 enum object_type type;
96                 num_read_blob++;
97                 file->ptr = read_sha1_file(o->blob_sha1, &type,
98                                            (unsigned long *)(&(file->size)));
99                 if (!file->ptr)
100                         die("Cannot read blob %s for path %s",
101                             sha1_to_hex(o->blob_sha1),
102                             o->path);
103                 o->file = *file;
104         }
105         else
106                 *file = o->file;
107 }
108
109 /*
110  * Origin is refcounted and usually we keep the blob contents to be
111  * reused.
112  */
113 static inline struct origin *origin_incref(struct origin *o)
114 {
115         if (o)
116                 o->refcnt++;
117         return o;
118 }
119
120 static void origin_decref(struct origin *o)
121 {
122         if (o && --o->refcnt <= 0) {
123                 if (o->previous)
124                         origin_decref(o->previous);
125                 free(o->file.ptr);
126                 free(o);
127         }
128 }
129
130 static void drop_origin_blob(struct origin *o)
131 {
132         if (o->file.ptr) {
133                 free(o->file.ptr);
134                 o->file.ptr = NULL;
135         }
136 }
137
138 /*
139  * Each group of lines is described by a blame_entry; it can be split
140  * as we pass blame to the parents.  They form a linked list in the
141  * scoreboard structure, sorted by the target line number.
142  */
143 struct blame_entry {
144         struct blame_entry *prev;
145         struct blame_entry *next;
146
147         /* the first line of this group in the final image;
148          * internally all line numbers are 0 based.
149          */
150         int lno;
151
152         /* how many lines this group has */
153         int num_lines;
154
155         /* the commit that introduced this group into the final image */
156         struct origin *suspect;
157
158         /* true if the suspect is truly guilty; false while we have not
159          * checked if the group came from one of its parents.
160          */
161         char guilty;
162
163         /* true if the entry has been scanned for copies in the current parent
164          */
165         char scanned;
166
167         /* the line number of the first line of this group in the
168          * suspect's file; internally all line numbers are 0 based.
169          */
170         int s_lno;
171
172         /* how significant this entry is -- cached to avoid
173          * scanning the lines over and over.
174          */
175         unsigned score;
176 };
177
178 /*
179  * The current state of the blame assignment.
180  */
181 struct scoreboard {
182         /* the final commit (i.e. where we started digging from) */
183         struct commit *final;
184         struct rev_info *revs;
185         const char *path;
186
187         /*
188          * The contents in the final image.
189          * Used by many functions to obtain contents of the nth line,
190          * indexed with scoreboard.lineno[blame_entry.lno].
191          */
192         const char *final_buf;
193         unsigned long final_buf_size;
194
195         /* linked list of blames */
196         struct blame_entry *ent;
197
198         /* look-up a line in the final buffer */
199         int num_lines;
200         int *lineno;
201 };
202
203 static inline int same_suspect(struct origin *a, struct origin *b)
204 {
205         if (a == b)
206                 return 1;
207         if (a->commit != b->commit)
208                 return 0;
209         return !strcmp(a->path, b->path);
210 }
211
212 static void sanity_check_refcnt(struct scoreboard *);
213
214 /*
215  * If two blame entries that are next to each other came from
216  * contiguous lines in the same origin (i.e. <commit, path> pair),
217  * merge them together.
218  */
219 static void coalesce(struct scoreboard *sb)
220 {
221         struct blame_entry *ent, *next;
222
223         for (ent = sb->ent; ent && (next = ent->next); ent = next) {
224                 if (same_suspect(ent->suspect, next->suspect) &&
225                     ent->guilty == next->guilty &&
226                     ent->s_lno + ent->num_lines == next->s_lno) {
227                         ent->num_lines += next->num_lines;
228                         ent->next = next->next;
229                         if (ent->next)
230                                 ent->next->prev = ent;
231                         origin_decref(next->suspect);
232                         free(next);
233                         ent->score = 0;
234                         next = ent; /* again */
235                 }
236         }
237
238         if (DEBUG) /* sanity */
239                 sanity_check_refcnt(sb);
240 }
241
242 /*
243  * Given a commit and a path in it, create a new origin structure.
244  * The callers that add blame to the scoreboard should use
245  * get_origin() to obtain shared, refcounted copy instead of calling
246  * this function directly.
247  */
248 static struct origin *make_origin(struct commit *commit, const char *path)
249 {
250         struct origin *o;
251         o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
252         o->commit = commit;
253         o->refcnt = 1;
254         strcpy(o->path, path);
255         return o;
256 }
257
258 /*
259  * Locate an existing origin or create a new one.
260  */
261 static struct origin *get_origin(struct scoreboard *sb,
262                                  struct commit *commit,
263                                  const char *path)
264 {
265         struct blame_entry *e;
266
267         for (e = sb->ent; e; e = e->next) {
268                 if (e->suspect->commit == commit &&
269                     !strcmp(e->suspect->path, path))
270                         return origin_incref(e->suspect);
271         }
272         return make_origin(commit, path);
273 }
274
275 /*
276  * Fill the blob_sha1 field of an origin if it hasn't, so that later
277  * call to fill_origin_blob() can use it to locate the data.  blob_sha1
278  * for an origin is also used to pass the blame for the entire file to
279  * the parent to detect the case where a child's blob is identical to
280  * that of its parent's.
281  */
282 static int fill_blob_sha1(struct origin *origin)
283 {
284         unsigned mode;
285
286         if (!is_null_sha1(origin->blob_sha1))
287                 return 0;
288         if (get_tree_entry(origin->commit->object.sha1,
289                            origin->path,
290                            origin->blob_sha1, &mode))
291                 goto error_out;
292         if (sha1_object_info(origin->blob_sha1, NULL) != OBJ_BLOB)
293                 goto error_out;
294         return 0;
295  error_out:
296         hashclr(origin->blob_sha1);
297         return -1;
298 }
299
300 /*
301  * We have an origin -- check if the same path exists in the
302  * parent and return an origin structure to represent it.
303  */
304 static struct origin *find_origin(struct scoreboard *sb,
305                                   struct commit *parent,
306                                   struct origin *origin)
307 {
308         struct origin *porigin = NULL;
309         struct diff_options diff_opts;
310         const char *paths[2];
311
312         if (parent->util) {
313                 /*
314                  * Each commit object can cache one origin in that
315                  * commit.  This is a freestanding copy of origin and
316                  * not refcounted.
317                  */
318                 struct origin *cached = parent->util;
319                 if (!strcmp(cached->path, origin->path)) {
320                         /*
321                          * The same path between origin and its parent
322                          * without renaming -- the most common case.
323                          */
324                         porigin = get_origin(sb, parent, cached->path);
325
326                         /*
327                          * If the origin was newly created (i.e. get_origin
328                          * would call make_origin if none is found in the
329                          * scoreboard), it does not know the blob_sha1,
330                          * so copy it.  Otherwise porigin was in the
331                          * scoreboard and already knows blob_sha1.
332                          */
333                         if (porigin->refcnt == 1)
334                                 hashcpy(porigin->blob_sha1, cached->blob_sha1);
335                         return porigin;
336                 }
337                 /* otherwise it was not very useful; free it */
338                 free(parent->util);
339                 parent->util = NULL;
340         }
341
342         /* See if the origin->path is different between parent
343          * and origin first.  Most of the time they are the
344          * same and diff-tree is fairly efficient about this.
345          */
346         diff_setup(&diff_opts);
347         DIFF_OPT_SET(&diff_opts, RECURSIVE);
348         diff_opts.detect_rename = 0;
349         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
350         paths[0] = origin->path;
351         paths[1] = NULL;
352
353         diff_tree_setup_paths(paths, &diff_opts);
354         if (diff_setup_done(&diff_opts) < 0)
355                 die("diff-setup");
356
357         if (is_null_sha1(origin->commit->object.sha1))
358                 do_diff_cache(parent->tree->object.sha1, &diff_opts);
359         else
360                 diff_tree_sha1(parent->tree->object.sha1,
361                                origin->commit->tree->object.sha1,
362                                "", &diff_opts);
363         diffcore_std(&diff_opts);
364
365         /* It is either one entry that says "modified", or "created",
366          * or nothing.
367          */
368         if (!diff_queued_diff.nr) {
369                 /* The path is the same as parent */
370                 porigin = get_origin(sb, parent, origin->path);
371                 hashcpy(porigin->blob_sha1, origin->blob_sha1);
372         }
373         else if (diff_queued_diff.nr != 1)
374                 die("internal error in blame::find_origin");
375         else {
376                 struct diff_filepair *p = diff_queued_diff.queue[0];
377                 switch (p->status) {
378                 default:
379                         die("internal error in blame::find_origin (%c)",
380                             p->status);
381                 case 'M':
382                         porigin = get_origin(sb, parent, origin->path);
383                         hashcpy(porigin->blob_sha1, p->one->sha1);
384                         break;
385                 case 'A':
386                 case 'T':
387                         /* Did not exist in parent, or type changed */
388                         break;
389                 }
390         }
391         diff_flush(&diff_opts);
392         diff_tree_release_paths(&diff_opts);
393         if (porigin) {
394                 /*
395                  * Create a freestanding copy that is not part of
396                  * the refcounted origin found in the scoreboard, and
397                  * cache it in the commit.
398                  */
399                 struct origin *cached;
400
401                 cached = make_origin(porigin->commit, porigin->path);
402                 hashcpy(cached->blob_sha1, porigin->blob_sha1);
403                 parent->util = cached;
404         }
405         return porigin;
406 }
407
408 /*
409  * We have an origin -- find the path that corresponds to it in its
410  * parent and return an origin structure to represent it.
411  */
412 static struct origin *find_rename(struct scoreboard *sb,
413                                   struct commit *parent,
414                                   struct origin *origin)
415 {
416         struct origin *porigin = NULL;
417         struct diff_options diff_opts;
418         int i;
419         const char *paths[2];
420
421         diff_setup(&diff_opts);
422         DIFF_OPT_SET(&diff_opts, RECURSIVE);
423         diff_opts.detect_rename = DIFF_DETECT_RENAME;
424         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
425         diff_opts.single_follow = origin->path;
426         paths[0] = NULL;
427         diff_tree_setup_paths(paths, &diff_opts);
428         if (diff_setup_done(&diff_opts) < 0)
429                 die("diff-setup");
430
431         if (is_null_sha1(origin->commit->object.sha1))
432                 do_diff_cache(parent->tree->object.sha1, &diff_opts);
433         else
434                 diff_tree_sha1(parent->tree->object.sha1,
435                                origin->commit->tree->object.sha1,
436                                "", &diff_opts);
437         diffcore_std(&diff_opts);
438
439         for (i = 0; i < diff_queued_diff.nr; i++) {
440                 struct diff_filepair *p = diff_queued_diff.queue[i];
441                 if ((p->status == 'R' || p->status == 'C') &&
442                     !strcmp(p->two->path, origin->path)) {
443                         porigin = get_origin(sb, parent, p->one->path);
444                         hashcpy(porigin->blob_sha1, p->one->sha1);
445                         break;
446                 }
447         }
448         diff_flush(&diff_opts);
449         diff_tree_release_paths(&diff_opts);
450         return porigin;
451 }
452
453 /*
454  * Link in a new blame entry to the scoreboard.  Entries that cover the
455  * same line range have been removed from the scoreboard previously.
456  */
457 static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
458 {
459         struct blame_entry *ent, *prev = NULL;
460
461         origin_incref(e->suspect);
462
463         for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
464                 prev = ent;
465
466         /* prev, if not NULL, is the last one that is below e */
467         e->prev = prev;
468         if (prev) {
469                 e->next = prev->next;
470                 prev->next = e;
471         }
472         else {
473                 e->next = sb->ent;
474                 sb->ent = e;
475         }
476         if (e->next)
477                 e->next->prev = e;
478 }
479
480 /*
481  * src typically is on-stack; we want to copy the information in it to
482  * a malloced blame_entry that is already on the linked list of the
483  * scoreboard.  The origin of dst loses a refcnt while the origin of src
484  * gains one.
485  */
486 static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
487 {
488         struct blame_entry *p, *n;
489
490         p = dst->prev;
491         n = dst->next;
492         origin_incref(src->suspect);
493         origin_decref(dst->suspect);
494         memcpy(dst, src, sizeof(*src));
495         dst->prev = p;
496         dst->next = n;
497         dst->score = 0;
498 }
499
500 static const char *nth_line(struct scoreboard *sb, int lno)
501 {
502         return sb->final_buf + sb->lineno[lno];
503 }
504
505 /*
506  * It is known that lines between tlno to same came from parent, and e
507  * has an overlap with that range.  it also is known that parent's
508  * line plno corresponds to e's line tlno.
509  *
510  *                <---- e ----->
511  *                   <------>
512  *                   <------------>
513  *             <------------>
514  *             <------------------>
515  *
516  * Split e into potentially three parts; before this chunk, the chunk
517  * to be blamed for the parent, and after that portion.
518  */
519 static void split_overlap(struct blame_entry *split,
520                           struct blame_entry *e,
521                           int tlno, int plno, int same,
522                           struct origin *parent)
523 {
524         int chunk_end_lno;
525         memset(split, 0, sizeof(struct blame_entry [3]));
526
527         if (e->s_lno < tlno) {
528                 /* there is a pre-chunk part not blamed on parent */
529                 split[0].suspect = origin_incref(e->suspect);
530                 split[0].lno = e->lno;
531                 split[0].s_lno = e->s_lno;
532                 split[0].num_lines = tlno - e->s_lno;
533                 split[1].lno = e->lno + tlno - e->s_lno;
534                 split[1].s_lno = plno;
535         }
536         else {
537                 split[1].lno = e->lno;
538                 split[1].s_lno = plno + (e->s_lno - tlno);
539         }
540
541         if (same < e->s_lno + e->num_lines) {
542                 /* there is a post-chunk part not blamed on parent */
543                 split[2].suspect = origin_incref(e->suspect);
544                 split[2].lno = e->lno + (same - e->s_lno);
545                 split[2].s_lno = e->s_lno + (same - e->s_lno);
546                 split[2].num_lines = e->s_lno + e->num_lines - same;
547                 chunk_end_lno = split[2].lno;
548         }
549         else
550                 chunk_end_lno = e->lno + e->num_lines;
551         split[1].num_lines = chunk_end_lno - split[1].lno;
552
553         /*
554          * if it turns out there is nothing to blame the parent for,
555          * forget about the splitting.  !split[1].suspect signals this.
556          */
557         if (split[1].num_lines < 1)
558                 return;
559         split[1].suspect = origin_incref(parent);
560 }
561
562 /*
563  * split_overlap() divided an existing blame e into up to three parts
564  * in split.  Adjust the linked list of blames in the scoreboard to
565  * reflect the split.
566  */
567 static void split_blame(struct scoreboard *sb,
568                         struct blame_entry *split,
569                         struct blame_entry *e)
570 {
571         struct blame_entry *new_entry;
572
573         if (split[0].suspect && split[2].suspect) {
574                 /* The first part (reuse storage for the existing entry e) */
575                 dup_entry(e, &split[0]);
576
577                 /* The last part -- me */
578                 new_entry = xmalloc(sizeof(*new_entry));
579                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
580                 add_blame_entry(sb, new_entry);
581
582                 /* ... and the middle part -- parent */
583                 new_entry = xmalloc(sizeof(*new_entry));
584                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
585                 add_blame_entry(sb, new_entry);
586         }
587         else if (!split[0].suspect && !split[2].suspect)
588                 /*
589                  * The parent covers the entire area; reuse storage for
590                  * e and replace it with the parent.
591                  */
592                 dup_entry(e, &split[1]);
593         else if (split[0].suspect) {
594                 /* me and then parent */
595                 dup_entry(e, &split[0]);
596
597                 new_entry = xmalloc(sizeof(*new_entry));
598                 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
599                 add_blame_entry(sb, new_entry);
600         }
601         else {
602                 /* parent and then me */
603                 dup_entry(e, &split[1]);
604
605                 new_entry = xmalloc(sizeof(*new_entry));
606                 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
607                 add_blame_entry(sb, new_entry);
608         }
609
610         if (DEBUG) { /* sanity */
611                 struct blame_entry *ent;
612                 int lno = sb->ent->lno, corrupt = 0;
613
614                 for (ent = sb->ent; ent; ent = ent->next) {
615                         if (lno != ent->lno)
616                                 corrupt = 1;
617                         if (ent->s_lno < 0)
618                                 corrupt = 1;
619                         lno += ent->num_lines;
620                 }
621                 if (corrupt) {
622                         lno = sb->ent->lno;
623                         for (ent = sb->ent; ent; ent = ent->next) {
624                                 printf("L %8d l %8d n %8d\n",
625                                        lno, ent->lno, ent->num_lines);
626                                 lno = ent->lno + ent->num_lines;
627                         }
628                         die("oops");
629                 }
630         }
631 }
632
633 /*
634  * After splitting the blame, the origins used by the
635  * on-stack blame_entry should lose one refcnt each.
636  */
637 static void decref_split(struct blame_entry *split)
638 {
639         int i;
640
641         for (i = 0; i < 3; i++)
642                 origin_decref(split[i].suspect);
643 }
644
645 /*
646  * Helper for blame_chunk().  blame_entry e is known to overlap with
647  * the patch hunk; split it and pass blame to the parent.
648  */
649 static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
650                           int tlno, int plno, int same,
651                           struct origin *parent)
652 {
653         struct blame_entry split[3];
654
655         split_overlap(split, e, tlno, plno, same, parent);
656         if (split[1].suspect)
657                 split_blame(sb, split, e);
658         decref_split(split);
659 }
660
661 /*
662  * Find the line number of the last line the target is suspected for.
663  */
664 static int find_last_in_target(struct scoreboard *sb, struct origin *target)
665 {
666         struct blame_entry *e;
667         int last_in_target = -1;
668
669         for (e = sb->ent; e; e = e->next) {
670                 if (e->guilty || !same_suspect(e->suspect, target))
671                         continue;
672                 if (last_in_target < e->s_lno + e->num_lines)
673                         last_in_target = e->s_lno + e->num_lines;
674         }
675         return last_in_target;
676 }
677
678 /*
679  * Process one hunk from the patch between the current suspect for
680  * blame_entry e and its parent.  Find and split the overlap, and
681  * pass blame to the overlapping part to the parent.
682  */
683 static void blame_chunk(struct scoreboard *sb,
684                         int tlno, int plno, int same,
685                         struct origin *target, struct origin *parent)
686 {
687         struct blame_entry *e;
688
689         for (e = sb->ent; e; e = e->next) {
690                 if (e->guilty || !same_suspect(e->suspect, target))
691                         continue;
692                 if (same <= e->s_lno)
693                         continue;
694                 if (tlno < e->s_lno + e->num_lines)
695                         blame_overlap(sb, e, tlno, plno, same, parent);
696         }
697 }
698
699 struct blame_chunk_cb_data {
700         struct scoreboard *sb;
701         struct origin *target;
702         struct origin *parent;
703         long plno;
704         long tlno;
705 };
706
707 static void blame_chunk_cb(void *data, long same, long p_next, long t_next)
708 {
709         struct blame_chunk_cb_data *d = data;
710         blame_chunk(d->sb, d->tlno, d->plno, same, d->target, d->parent);
711         d->plno = p_next;
712         d->tlno = t_next;
713 }
714
715 /*
716  * We are looking at the origin 'target' and aiming to pass blame
717  * for the lines it is suspected to its parent.  Run diff to find
718  * which lines came from parent and pass blame for them.
719  */
720 static int pass_blame_to_parent(struct scoreboard *sb,
721                                 struct origin *target,
722                                 struct origin *parent)
723 {
724         int last_in_target;
725         mmfile_t file_p, file_o;
726         struct blame_chunk_cb_data d = { sb, target, parent, 0, 0 };
727         xpparam_t xpp;
728         xdemitconf_t xecfg;
729
730         last_in_target = find_last_in_target(sb, target);
731         if (last_in_target < 0)
732                 return 1; /* nothing remains for this target */
733
734         fill_origin_blob(parent, &file_p);
735         fill_origin_blob(target, &file_o);
736         num_get_patch++;
737
738         memset(&xpp, 0, sizeof(xpp));
739         xpp.flags = xdl_opts;
740         memset(&xecfg, 0, sizeof(xecfg));
741         xecfg.ctxlen = 0;
742         xdi_diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, &xpp, &xecfg);
743         /* The rest (i.e. anything after tlno) are the same as the parent */
744         blame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);
745
746         return 0;
747 }
748
749 /*
750  * The lines in blame_entry after splitting blames many times can become
751  * very small and trivial, and at some point it becomes pointless to
752  * blame the parents.  E.g. "\t\t}\n\t}\n\n" appears everywhere in any
753  * ordinary C program, and it is not worth to say it was copied from
754  * totally unrelated file in the parent.
755  *
756  * Compute how trivial the lines in the blame_entry are.
757  */
758 static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
759 {
760         unsigned score;
761         const char *cp, *ep;
762
763         if (e->score)
764                 return e->score;
765
766         score = 1;
767         cp = nth_line(sb, e->lno);
768         ep = nth_line(sb, e->lno + e->num_lines);
769         while (cp < ep) {
770                 unsigned ch = *((unsigned char *)cp);
771                 if (isalnum(ch))
772                         score++;
773                 cp++;
774         }
775         e->score = score;
776         return score;
777 }
778
779 /*
780  * best_so_far[] and this[] are both a split of an existing blame_entry
781  * that passes blame to the parent.  Maintain best_so_far the best split
782  * so far, by comparing this and best_so_far and copying this into
783  * bst_so_far as needed.
784  */
785 static void copy_split_if_better(struct scoreboard *sb,
786                                  struct blame_entry *best_so_far,
787                                  struct blame_entry *this)
788 {
789         int i;
790
791         if (!this[1].suspect)
792                 return;
793         if (best_so_far[1].suspect) {
794                 if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
795                         return;
796         }
797
798         for (i = 0; i < 3; i++)
799                 origin_incref(this[i].suspect);
800         decref_split(best_so_far);
801         memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
802 }
803
804 /*
805  * We are looking at a part of the final image represented by
806  * ent (tlno and same are offset by ent->s_lno).
807  * tlno is where we are looking at in the final image.
808  * up to (but not including) same match preimage.
809  * plno is where we are looking at in the preimage.
810  *
811  * <-------------- final image ---------------------->
812  *       <------ent------>
813  *         ^tlno ^same
814  *    <---------preimage----->
815  *         ^plno
816  *
817  * All line numbers are 0-based.
818  */
819 static void handle_split(struct scoreboard *sb,
820                          struct blame_entry *ent,
821                          int tlno, int plno, int same,
822                          struct origin *parent,
823                          struct blame_entry *split)
824 {
825         if (ent->num_lines <= tlno)
826                 return;
827         if (tlno < same) {
828                 struct blame_entry this[3];
829                 tlno += ent->s_lno;
830                 same += ent->s_lno;
831                 split_overlap(this, ent, tlno, plno, same, parent);
832                 copy_split_if_better(sb, split, this);
833                 decref_split(this);
834         }
835 }
836
837 struct handle_split_cb_data {
838         struct scoreboard *sb;
839         struct blame_entry *ent;
840         struct origin *parent;
841         struct blame_entry *split;
842         long plno;
843         long tlno;
844 };
845
846 static void handle_split_cb(void *data, long same, long p_next, long t_next)
847 {
848         struct handle_split_cb_data *d = data;
849         handle_split(d->sb, d->ent, d->tlno, d->plno, same, d->parent, d->split);
850         d->plno = p_next;
851         d->tlno = t_next;
852 }
853
854 /*
855  * Find the lines from parent that are the same as ent so that
856  * we can pass blames to it.  file_p has the blob contents for
857  * the parent.
858  */
859 static void find_copy_in_blob(struct scoreboard *sb,
860                               struct blame_entry *ent,
861                               struct origin *parent,
862                               struct blame_entry *split,
863                               mmfile_t *file_p)
864 {
865         const char *cp;
866         int cnt;
867         mmfile_t file_o;
868         struct handle_split_cb_data d = { sb, ent, parent, split, 0, 0 };
869         xpparam_t xpp;
870         xdemitconf_t xecfg;
871
872         /*
873          * Prepare mmfile that contains only the lines in ent.
874          */
875         cp = nth_line(sb, ent->lno);
876         file_o.ptr = (char *) cp;
877         cnt = ent->num_lines;
878
879         while (cnt && cp < sb->final_buf + sb->final_buf_size) {
880                 if (*cp++ == '\n')
881                         cnt--;
882         }
883         file_o.size = cp - file_o.ptr;
884
885         /*
886          * file_o is a part of final image we are annotating.
887          * file_p partially may match that image.
888          */
889         memset(&xpp, 0, sizeof(xpp));
890         xpp.flags = xdl_opts;
891         memset(&xecfg, 0, sizeof(xecfg));
892         xecfg.ctxlen = 1;
893         memset(split, 0, sizeof(struct blame_entry [3]));
894         xdi_diff_hunks(file_p, &file_o, handle_split_cb, &d, &xpp, &xecfg);
895         /* remainder, if any, all match the preimage */
896         handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);
897 }
898
899 /*
900  * See if lines currently target is suspected for can be attributed to
901  * parent.
902  */
903 static int find_move_in_parent(struct scoreboard *sb,
904                                struct origin *target,
905                                struct origin *parent)
906 {
907         int last_in_target, made_progress;
908         struct blame_entry *e, split[3];
909         mmfile_t file_p;
910
911         last_in_target = find_last_in_target(sb, target);
912         if (last_in_target < 0)
913                 return 1; /* nothing remains for this target */
914
915         fill_origin_blob(parent, &file_p);
916         if (!file_p.ptr)
917                 return 0;
918
919         made_progress = 1;
920         while (made_progress) {
921                 made_progress = 0;
922                 for (e = sb->ent; e; e = e->next) {
923                         if (e->guilty || !same_suspect(e->suspect, target) ||
924                             ent_score(sb, e) < blame_move_score)
925                                 continue;
926                         find_copy_in_blob(sb, e, parent, split, &file_p);
927                         if (split[1].suspect &&
928                             blame_move_score < ent_score(sb, &split[1])) {
929                                 split_blame(sb, split, e);
930                                 made_progress = 1;
931                         }
932                         decref_split(split);
933                 }
934         }
935         return 0;
936 }
937
938 struct blame_list {
939         struct blame_entry *ent;
940         struct blame_entry split[3];
941 };
942
943 /*
944  * Count the number of entries the target is suspected for,
945  * and prepare a list of entry and the best split.
946  */
947 static struct blame_list *setup_blame_list(struct scoreboard *sb,
948                                            struct origin *target,
949                                            int min_score,
950                                            int *num_ents_p)
951 {
952         struct blame_entry *e;
953         int num_ents, i;
954         struct blame_list *blame_list = NULL;
955
956         for (e = sb->ent, num_ents = 0; e; e = e->next)
957                 if (!e->scanned && !e->guilty &&
958                     same_suspect(e->suspect, target) &&
959                     min_score < ent_score(sb, e))
960                         num_ents++;
961         if (num_ents) {
962                 blame_list = xcalloc(num_ents, sizeof(struct blame_list));
963                 for (e = sb->ent, i = 0; e; e = e->next)
964                         if (!e->scanned && !e->guilty &&
965                             same_suspect(e->suspect, target) &&
966                             min_score < ent_score(sb, e))
967                                 blame_list[i++].ent = e;
968         }
969         *num_ents_p = num_ents;
970         return blame_list;
971 }
972
973 /*
974  * Reset the scanned status on all entries.
975  */
976 static void reset_scanned_flag(struct scoreboard *sb)
977 {
978         struct blame_entry *e;
979         for (e = sb->ent; e; e = e->next)
980                 e->scanned = 0;
981 }
982
983 /*
984  * For lines target is suspected for, see if we can find code movement
985  * across file boundary from the parent commit.  porigin is the path
986  * in the parent we already tried.
987  */
988 static int find_copy_in_parent(struct scoreboard *sb,
989                                struct origin *target,
990                                struct commit *parent,
991                                struct origin *porigin,
992                                int opt)
993 {
994         struct diff_options diff_opts;
995         const char *paths[1];
996         int i, j;
997         int retval;
998         struct blame_list *blame_list;
999         int num_ents;
1000
1001         blame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);
1002         if (!blame_list)
1003                 return 1; /* nothing remains for this target */
1004
1005         diff_setup(&diff_opts);
1006         DIFF_OPT_SET(&diff_opts, RECURSIVE);
1007         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1008
1009         paths[0] = NULL;
1010         diff_tree_setup_paths(paths, &diff_opts);
1011         if (diff_setup_done(&diff_opts) < 0)
1012                 die("diff-setup");
1013
1014         /* Try "find copies harder" on new path if requested;
1015          * we do not want to use diffcore_rename() actually to
1016          * match things up; find_copies_harder is set only to
1017          * force diff_tree_sha1() to feed all filepairs to diff_queue,
1018          * and this code needs to be after diff_setup_done(), which
1019          * usually makes find-copies-harder imply copy detection.
1020          */
1021         if ((opt & PICKAXE_BLAME_COPY_HARDEST)
1022             || ((opt & PICKAXE_BLAME_COPY_HARDER)
1023                 && (!porigin || strcmp(target->path, porigin->path))))
1024                 DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
1025
1026         if (is_null_sha1(target->commit->object.sha1))
1027                 do_diff_cache(parent->tree->object.sha1, &diff_opts);
1028         else
1029                 diff_tree_sha1(parent->tree->object.sha1,
1030                                target->commit->tree->object.sha1,
1031                                "", &diff_opts);
1032
1033         if (!DIFF_OPT_TST(&diff_opts, FIND_COPIES_HARDER))
1034                 diffcore_std(&diff_opts);
1035
1036         retval = 0;
1037         while (1) {
1038                 int made_progress = 0;
1039
1040                 for (i = 0; i < diff_queued_diff.nr; i++) {
1041                         struct diff_filepair *p = diff_queued_diff.queue[i];
1042                         struct origin *norigin;
1043                         mmfile_t file_p;
1044                         struct blame_entry this[3];
1045
1046                         if (!DIFF_FILE_VALID(p->one))
1047                                 continue; /* does not exist in parent */
1048                         if (S_ISGITLINK(p->one->mode))
1049                                 continue; /* ignore git links */
1050                         if (porigin && !strcmp(p->one->path, porigin->path))
1051                                 /* find_move already dealt with this path */
1052                                 continue;
1053
1054                         norigin = get_origin(sb, parent, p->one->path);
1055                         hashcpy(norigin->blob_sha1, p->one->sha1);
1056                         fill_origin_blob(norigin, &file_p);
1057                         if (!file_p.ptr)
1058                                 continue;
1059
1060                         for (j = 0; j < num_ents; j++) {
1061                                 find_copy_in_blob(sb, blame_list[j].ent,
1062                                                   norigin, this, &file_p);
1063                                 copy_split_if_better(sb, blame_list[j].split,
1064                                                      this);
1065                                 decref_split(this);
1066                         }
1067                         origin_decref(norigin);
1068                 }
1069
1070                 for (j = 0; j < num_ents; j++) {
1071                         struct blame_entry *split = blame_list[j].split;
1072                         if (split[1].suspect &&
1073                             blame_copy_score < ent_score(sb, &split[1])) {
1074                                 split_blame(sb, split, blame_list[j].ent);
1075                                 made_progress = 1;
1076                         }
1077                         else
1078                                 blame_list[j].ent->scanned = 1;
1079                         decref_split(split);
1080                 }
1081                 free(blame_list);
1082
1083                 if (!made_progress)
1084                         break;
1085                 blame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);
1086                 if (!blame_list) {
1087                         retval = 1;
1088                         break;
1089                 }
1090         }
1091         reset_scanned_flag(sb);
1092         diff_flush(&diff_opts);
1093         diff_tree_release_paths(&diff_opts);
1094         return retval;
1095 }
1096
1097 /*
1098  * The blobs of origin and porigin exactly match, so everything
1099  * origin is suspected for can be blamed on the parent.
1100  */
1101 static void pass_whole_blame(struct scoreboard *sb,
1102                              struct origin *origin, struct origin *porigin)
1103 {
1104         struct blame_entry *e;
1105
1106         if (!porigin->file.ptr && origin->file.ptr) {
1107                 /* Steal its file */
1108                 porigin->file = origin->file;
1109                 origin->file.ptr = NULL;
1110         }
1111         for (e = sb->ent; e; e = e->next) {
1112                 if (!same_suspect(e->suspect, origin))
1113                         continue;
1114                 origin_incref(porigin);
1115                 origin_decref(e->suspect);
1116                 e->suspect = porigin;
1117         }
1118 }
1119
1120 /*
1121  * We pass blame from the current commit to its parents.  We keep saying
1122  * "parent" (and "porigin"), but what we mean is to find scapegoat to
1123  * exonerate ourselves.
1124  */
1125 static struct commit_list *first_scapegoat(struct rev_info *revs, struct commit *commit)
1126 {
1127         if (!reverse)
1128                 return commit->parents;
1129         return lookup_decoration(&revs->children, &commit->object);
1130 }
1131
1132 static int num_scapegoats(struct rev_info *revs, struct commit *commit)
1133 {
1134         int cnt;
1135         struct commit_list *l = first_scapegoat(revs, commit);
1136         for (cnt = 0; l; l = l->next)
1137                 cnt++;
1138         return cnt;
1139 }
1140
1141 #define MAXSG 16
1142
1143 static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
1144 {
1145         struct rev_info *revs = sb->revs;
1146         int i, pass, num_sg;
1147         struct commit *commit = origin->commit;
1148         struct commit_list *sg;
1149         struct origin *sg_buf[MAXSG];
1150         struct origin *porigin, **sg_origin = sg_buf;
1151
1152         num_sg = num_scapegoats(revs, commit);
1153         if (!num_sg)
1154                 goto finish;
1155         else if (num_sg < ARRAY_SIZE(sg_buf))
1156                 memset(sg_buf, 0, sizeof(sg_buf));
1157         else
1158                 sg_origin = xcalloc(num_sg, sizeof(*sg_origin));
1159
1160         /*
1161          * The first pass looks for unrenamed path to optimize for
1162          * common cases, then we look for renames in the second pass.
1163          */
1164         for (pass = 0; pass < 2; pass++) {
1165                 struct origin *(*find)(struct scoreboard *,
1166                                        struct commit *, struct origin *);
1167                 find = pass ? find_rename : find_origin;
1168
1169                 for (i = 0, sg = first_scapegoat(revs, commit);
1170                      i < num_sg && sg;
1171                      sg = sg->next, i++) {
1172                         struct commit *p = sg->item;
1173                         int j, same;
1174
1175                         if (sg_origin[i])
1176                                 continue;
1177                         if (parse_commit(p))
1178                                 continue;
1179                         porigin = find(sb, p, origin);
1180                         if (!porigin)
1181                                 continue;
1182                         if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
1183                                 pass_whole_blame(sb, origin, porigin);
1184                                 origin_decref(porigin);
1185                                 goto finish;
1186                         }
1187                         for (j = same = 0; j < i; j++)
1188                                 if (sg_origin[j] &&
1189                                     !hashcmp(sg_origin[j]->blob_sha1,
1190                                              porigin->blob_sha1)) {
1191                                         same = 1;
1192                                         break;
1193                                 }
1194                         if (!same)
1195                                 sg_origin[i] = porigin;
1196                         else
1197                                 origin_decref(porigin);
1198                 }
1199         }
1200
1201         num_commits++;
1202         for (i = 0, sg = first_scapegoat(revs, commit);
1203              i < num_sg && sg;
1204              sg = sg->next, i++) {
1205                 struct origin *porigin = sg_origin[i];
1206                 if (!porigin)
1207                         continue;
1208                 if (!origin->previous) {
1209                         origin_incref(porigin);
1210                         origin->previous = porigin;
1211                 }
1212                 if (pass_blame_to_parent(sb, origin, porigin))
1213                         goto finish;
1214         }
1215
1216         /*
1217          * Optionally find moves in parents' files.
1218          */
1219         if (opt & PICKAXE_BLAME_MOVE)
1220                 for (i = 0, sg = first_scapegoat(revs, commit);
1221                      i < num_sg && sg;
1222                      sg = sg->next, i++) {
1223                         struct origin *porigin = sg_origin[i];
1224                         if (!porigin)
1225                                 continue;
1226                         if (find_move_in_parent(sb, origin, porigin))
1227                                 goto finish;
1228                 }
1229
1230         /*
1231          * Optionally find copies from parents' files.
1232          */
1233         if (opt & PICKAXE_BLAME_COPY)
1234                 for (i = 0, sg = first_scapegoat(revs, commit);
1235                      i < num_sg && sg;
1236                      sg = sg->next, i++) {
1237                         struct origin *porigin = sg_origin[i];
1238                         if (find_copy_in_parent(sb, origin, sg->item,
1239                                                 porigin, opt))
1240                                 goto finish;
1241                 }
1242
1243  finish:
1244         for (i = 0; i < num_sg; i++) {
1245                 if (sg_origin[i]) {
1246                         drop_origin_blob(sg_origin[i]);
1247                         origin_decref(sg_origin[i]);
1248                 }
1249         }
1250         drop_origin_blob(origin);
1251         if (sg_buf != sg_origin)
1252                 free(sg_origin);
1253 }
1254
1255 /*
1256  * Information on commits, used for output.
1257  */
1258 struct commit_info
1259 {
1260         const char *author;
1261         const char *author_mail;
1262         unsigned long author_time;
1263         const char *author_tz;
1264
1265         /* filled only when asked for details */
1266         const char *committer;
1267         const char *committer_mail;
1268         unsigned long committer_time;
1269         const char *committer_tz;
1270
1271         const char *summary;
1272 };
1273
1274 /*
1275  * Parse author/committer line in the commit object buffer
1276  */
1277 static void get_ac_line(const char *inbuf, const char *what,
1278                         int person_len, char *person,
1279                         int mail_len, char *mail,
1280                         unsigned long *time, const char **tz)
1281 {
1282         int len, tzlen, maillen;
1283         char *tmp, *endp, *timepos, *mailpos;
1284
1285         tmp = strstr(inbuf, what);
1286         if (!tmp)
1287                 goto error_out;
1288         tmp += strlen(what);
1289         endp = strchr(tmp, '\n');
1290         if (!endp)
1291                 len = strlen(tmp);
1292         else
1293                 len = endp - tmp;
1294         if (person_len <= len) {
1295         error_out:
1296                 /* Ugh */
1297                 *tz = "(unknown)";
1298                 strcpy(mail, *tz);
1299                 *time = 0;
1300                 return;
1301         }
1302         memcpy(person, tmp, len);
1303
1304         tmp = person;
1305         tmp += len;
1306         *tmp = 0;
1307         while (*tmp != ' ')
1308                 tmp--;
1309         *tz = tmp+1;
1310         tzlen = (person+len)-(tmp+1);
1311
1312         *tmp = 0;
1313         while (*tmp != ' ')
1314                 tmp--;
1315         *time = strtoul(tmp, NULL, 10);
1316         timepos = tmp;
1317
1318         *tmp = 0;
1319         while (*tmp != ' ')
1320                 tmp--;
1321         mailpos = tmp + 1;
1322         *tmp = 0;
1323         maillen = timepos - tmp;
1324         memcpy(mail, mailpos, maillen);
1325
1326         if (!mailmap.nr)
1327                 return;
1328
1329         /*
1330          * mailmap expansion may make the name longer.
1331          * make room by pushing stuff down.
1332          */
1333         tmp = person + person_len - (tzlen + 1);
1334         memmove(tmp, *tz, tzlen);
1335         tmp[tzlen] = 0;
1336         *tz = tmp;
1337
1338         /*
1339          * Now, convert both name and e-mail using mailmap
1340          */
1341         if(map_user(&mailmap, mail+1, mail_len-1, person, tmp-person-1)) {
1342                 /* Add a trailing '>' to email, since map_user returns plain emails
1343                    Note: It already has '<', since we replace from mail+1 */
1344                 mailpos = memchr(mail, '\0', mail_len);
1345                 if (mailpos && mailpos-mail < mail_len - 1) {
1346                         *mailpos = '>';
1347                         *(mailpos+1) = '\0';
1348                 }
1349         }
1350 }
1351
1352 static void get_commit_info(struct commit *commit,
1353                             struct commit_info *ret,
1354                             int detailed)
1355 {
1356         int len;
1357         char *tmp, *endp, *reencoded, *message;
1358         static char author_name[1024];
1359         static char author_mail[1024];
1360         static char committer_name[1024];
1361         static char committer_mail[1024];
1362         static char summary_buf[1024];
1363
1364         /*
1365          * We've operated without save_commit_buffer, so
1366          * we now need to populate them for output.
1367          */
1368         if (!commit->buffer) {
1369                 enum object_type type;
1370                 unsigned long size;
1371                 commit->buffer =
1372                         read_sha1_file(commit->object.sha1, &type, &size);
1373                 if (!commit->buffer)
1374                         die("Cannot read commit %s",
1375                             sha1_to_hex(commit->object.sha1));
1376         }
1377         reencoded = reencode_commit_message(commit, NULL);
1378         message   = reencoded ? reencoded : commit->buffer;
1379         ret->author = author_name;
1380         ret->author_mail = author_mail;
1381         get_ac_line(message, "\nauthor ",
1382                     sizeof(author_name), author_name,
1383                     sizeof(author_mail), author_mail,
1384                     &ret->author_time, &ret->author_tz);
1385
1386         if (!detailed) {
1387                 free(reencoded);
1388                 return;
1389         }
1390
1391         ret->committer = committer_name;
1392         ret->committer_mail = committer_mail;
1393         get_ac_line(message, "\ncommitter ",
1394                     sizeof(committer_name), committer_name,
1395                     sizeof(committer_mail), committer_mail,
1396                     &ret->committer_time, &ret->committer_tz);
1397
1398         ret->summary = summary_buf;
1399         tmp = strstr(message, "\n\n");
1400         if (!tmp) {
1401         error_out:
1402                 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
1403                 free(reencoded);
1404                 return;
1405         }
1406         tmp += 2;
1407         endp = strchr(tmp, '\n');
1408         if (!endp)
1409                 endp = tmp + strlen(tmp);
1410         len = endp - tmp;
1411         if (len >= sizeof(summary_buf) || len == 0)
1412                 goto error_out;
1413         memcpy(summary_buf, tmp, len);
1414         summary_buf[len] = 0;
1415         free(reencoded);
1416 }
1417
1418 /*
1419  * To allow LF and other nonportable characters in pathnames,
1420  * they are c-style quoted as needed.
1421  */
1422 static void write_filename_info(const char *path)
1423 {
1424         printf("filename ");
1425         write_name_quoted(path, stdout, '\n');
1426 }
1427
1428 /*
1429  * Porcelain/Incremental format wants to show a lot of details per
1430  * commit.  Instead of repeating this every line, emit it only once,
1431  * the first time each commit appears in the output.
1432  */
1433 static int emit_one_suspect_detail(struct origin *suspect)
1434 {
1435         struct commit_info ci;
1436
1437         if (suspect->commit->object.flags & METAINFO_SHOWN)
1438                 return 0;
1439
1440         suspect->commit->object.flags |= METAINFO_SHOWN;
1441         get_commit_info(suspect->commit, &ci, 1);
1442         printf("author %s\n", ci.author);
1443         printf("author-mail %s\n", ci.author_mail);
1444         printf("author-time %lu\n", ci.author_time);
1445         printf("author-tz %s\n", ci.author_tz);
1446         printf("committer %s\n", ci.committer);
1447         printf("committer-mail %s\n", ci.committer_mail);
1448         printf("committer-time %lu\n", ci.committer_time);
1449         printf("committer-tz %s\n", ci.committer_tz);
1450         printf("summary %s\n", ci.summary);
1451         if (suspect->commit->object.flags & UNINTERESTING)
1452                 printf("boundary\n");
1453         if (suspect->previous) {
1454                 struct origin *prev = suspect->previous;
1455                 printf("previous %s ", sha1_to_hex(prev->commit->object.sha1));
1456                 write_name_quoted(prev->path, stdout, '\n');
1457         }
1458         return 1;
1459 }
1460
1461 /*
1462  * The blame_entry is found to be guilty for the range.  Mark it
1463  * as such, and show it in incremental output.
1464  */
1465 static void found_guilty_entry(struct blame_entry *ent)
1466 {
1467         if (ent->guilty)
1468                 return;
1469         ent->guilty = 1;
1470         if (incremental) {
1471                 struct origin *suspect = ent->suspect;
1472
1473                 printf("%s %d %d %d\n",
1474                        sha1_to_hex(suspect->commit->object.sha1),
1475                        ent->s_lno + 1, ent->lno + 1, ent->num_lines);
1476                 emit_one_suspect_detail(suspect);
1477                 write_filename_info(suspect->path);
1478                 maybe_flush_or_die(stdout, "stdout");
1479         }
1480 }
1481
1482 /*
1483  * The main loop -- while the scoreboard has lines whose true origin
1484  * is still unknown, pick one blame_entry, and allow its current
1485  * suspect to pass blames to its parents.
1486  */
1487 static void assign_blame(struct scoreboard *sb, int opt)
1488 {
1489         struct rev_info *revs = sb->revs;
1490
1491         while (1) {
1492                 struct blame_entry *ent;
1493                 struct commit *commit;
1494                 struct origin *suspect = NULL;
1495
1496                 /* find one suspect to break down */
1497                 for (ent = sb->ent; !suspect && ent; ent = ent->next)
1498                         if (!ent->guilty)
1499                                 suspect = ent->suspect;
1500                 if (!suspect)
1501                         return; /* all done */
1502
1503                 /*
1504                  * We will use this suspect later in the loop,
1505                  * so hold onto it in the meantime.
1506                  */
1507                 origin_incref(suspect);
1508                 commit = suspect->commit;
1509                 if (!commit->object.parsed)
1510                         parse_commit(commit);
1511                 if (reverse ||
1512                     (!(commit->object.flags & UNINTERESTING) &&
1513                      !(revs->max_age != -1 && commit->date < revs->max_age)))
1514                         pass_blame(sb, suspect, opt);
1515                 else {
1516                         commit->object.flags |= UNINTERESTING;
1517                         if (commit->object.parsed)
1518                                 mark_parents_uninteresting(commit);
1519                 }
1520                 /* treat root commit as boundary */
1521                 if (!commit->parents && !show_root)
1522                         commit->object.flags |= UNINTERESTING;
1523
1524                 /* Take responsibility for the remaining entries */
1525                 for (ent = sb->ent; ent; ent = ent->next)
1526                         if (same_suspect(ent->suspect, suspect))
1527                                 found_guilty_entry(ent);
1528                 origin_decref(suspect);
1529
1530                 if (DEBUG) /* sanity */
1531                         sanity_check_refcnt(sb);
1532         }
1533 }
1534
1535 static const char *format_time(unsigned long time, const char *tz_str,
1536                                int show_raw_time)
1537 {
1538         static char time_buf[128];
1539         const char *time_str;
1540         int time_len;
1541         int tz;
1542
1543         if (show_raw_time) {
1544                 sprintf(time_buf, "%lu %s", time, tz_str);
1545         }
1546         else {
1547                 tz = atoi(tz_str);
1548                 time_str = show_date(time, tz, blame_date_mode);
1549                 time_len = strlen(time_str);
1550                 memcpy(time_buf, time_str, time_len);
1551                 memset(time_buf + time_len, ' ', blame_date_width - time_len);
1552         }
1553         return time_buf;
1554 }
1555
1556 #define OUTPUT_ANNOTATE_COMPAT  001
1557 #define OUTPUT_LONG_OBJECT_NAME 002
1558 #define OUTPUT_RAW_TIMESTAMP    004
1559 #define OUTPUT_PORCELAIN        010
1560 #define OUTPUT_SHOW_NAME        020
1561 #define OUTPUT_SHOW_NUMBER      040
1562 #define OUTPUT_SHOW_SCORE      0100
1563 #define OUTPUT_NO_AUTHOR       0200
1564
1565 static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
1566 {
1567         int cnt;
1568         const char *cp;
1569         struct origin *suspect = ent->suspect;
1570         char hex[41];
1571
1572         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1573         printf("%s%c%d %d %d\n",
1574                hex,
1575                ent->guilty ? ' ' : '*', // purely for debugging
1576                ent->s_lno + 1,
1577                ent->lno + 1,
1578                ent->num_lines);
1579         if (emit_one_suspect_detail(suspect) ||
1580             (suspect->commit->object.flags & MORE_THAN_ONE_PATH))
1581                 write_filename_info(suspect->path);
1582
1583         cp = nth_line(sb, ent->lno);
1584         for (cnt = 0; cnt < ent->num_lines; cnt++) {
1585                 char ch;
1586                 if (cnt)
1587                         printf("%s %d %d\n", hex,
1588                                ent->s_lno + 1 + cnt,
1589                                ent->lno + 1 + cnt);
1590                 putchar('\t');
1591                 do {
1592                         ch = *cp++;
1593                         putchar(ch);
1594                 } while (ch != '\n' &&
1595                          cp < sb->final_buf + sb->final_buf_size);
1596         }
1597 }
1598
1599 static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1600 {
1601         int cnt;
1602         const char *cp;
1603         struct origin *suspect = ent->suspect;
1604         struct commit_info ci;
1605         char hex[41];
1606         int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1607
1608         get_commit_info(suspect->commit, &ci, 1);
1609         strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1610
1611         cp = nth_line(sb, ent->lno);
1612         for (cnt = 0; cnt < ent->num_lines; cnt++) {
1613                 char ch;
1614                 int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8;
1615
1616                 if (suspect->commit->object.flags & UNINTERESTING) {
1617                         if (blank_boundary)
1618                                 memset(hex, ' ', length);
1619                         else if (!(opt & OUTPUT_ANNOTATE_COMPAT)) {
1620                                 length--;
1621                                 putchar('^');
1622                         }
1623                 }
1624
1625                 printf("%.*s", length, hex);
1626                 if (opt & OUTPUT_ANNOTATE_COMPAT)
1627                         printf("\t(%10s\t%10s\t%d)", ci.author,
1628                                format_time(ci.author_time, ci.author_tz,
1629                                            show_raw_time),
1630                                ent->lno + 1 + cnt);
1631                 else {
1632                         if (opt & OUTPUT_SHOW_SCORE)
1633                                 printf(" %*d %02d",
1634                                        max_score_digits, ent->score,
1635                                        ent->suspect->refcnt);
1636                         if (opt & OUTPUT_SHOW_NAME)
1637                                 printf(" %-*.*s", longest_file, longest_file,
1638                                        suspect->path);
1639                         if (opt & OUTPUT_SHOW_NUMBER)
1640                                 printf(" %*d", max_orig_digits,
1641                                        ent->s_lno + 1 + cnt);
1642
1643                         if (!(opt & OUTPUT_NO_AUTHOR)) {
1644                                 int pad = longest_author - utf8_strwidth(ci.author);
1645                                 printf(" (%s%*s %10s",
1646                                        ci.author, pad, "",
1647                                        format_time(ci.author_time,
1648                                                    ci.author_tz,
1649                                                    show_raw_time));
1650                         }
1651                         printf(" %*d) ",
1652                                max_digits, ent->lno + 1 + cnt);
1653                 }
1654                 do {
1655                         ch = *cp++;
1656                         putchar(ch);
1657                 } while (ch != '\n' &&
1658                          cp < sb->final_buf + sb->final_buf_size);
1659         }
1660 }
1661
1662 static void output(struct scoreboard *sb, int option)
1663 {
1664         struct blame_entry *ent;
1665
1666         if (option & OUTPUT_PORCELAIN) {
1667                 for (ent = sb->ent; ent; ent = ent->next) {
1668                         struct blame_entry *oth;
1669                         struct origin *suspect = ent->suspect;
1670                         struct commit *commit = suspect->commit;
1671                         if (commit->object.flags & MORE_THAN_ONE_PATH)
1672                                 continue;
1673                         for (oth = ent->next; oth; oth = oth->next) {
1674                                 if ((oth->suspect->commit != commit) ||
1675                                     !strcmp(oth->suspect->path, suspect->path))
1676                                         continue;
1677                                 commit->object.flags |= MORE_THAN_ONE_PATH;
1678                                 break;
1679                         }
1680                 }
1681         }
1682
1683         for (ent = sb->ent; ent; ent = ent->next) {
1684                 if (option & OUTPUT_PORCELAIN)
1685                         emit_porcelain(sb, ent);
1686                 else {
1687                         emit_other(sb, ent, option);
1688                 }
1689         }
1690 }
1691
1692 /*
1693  * To allow quick access to the contents of nth line in the
1694  * final image, prepare an index in the scoreboard.
1695  */
1696 static int prepare_lines(struct scoreboard *sb)
1697 {
1698         const char *buf = sb->final_buf;
1699         unsigned long len = sb->final_buf_size;
1700         int num = 0, incomplete = 0, bol = 1;
1701
1702         if (len && buf[len-1] != '\n')
1703                 incomplete++; /* incomplete line at the end */
1704         while (len--) {
1705                 if (bol) {
1706                         sb->lineno = xrealloc(sb->lineno,
1707                                               sizeof(int *) * (num + 1));
1708                         sb->lineno[num] = buf - sb->final_buf;
1709                         bol = 0;
1710                 }
1711                 if (*buf++ == '\n') {
1712                         num++;
1713                         bol = 1;
1714                 }
1715         }
1716         sb->lineno = xrealloc(sb->lineno,
1717                               sizeof(int *) * (num + incomplete + 1));
1718         sb->lineno[num + incomplete] = buf - sb->final_buf;
1719         sb->num_lines = num + incomplete;
1720         return sb->num_lines;
1721 }
1722
1723 /*
1724  * Add phony grafts for use with -S; this is primarily to
1725  * support git's cvsserver that wants to give a linear history
1726  * to its clients.
1727  */
1728 static int read_ancestry(const char *graft_file)
1729 {
1730         FILE *fp = fopen(graft_file, "r");
1731         char buf[1024];
1732         if (!fp)
1733                 return -1;
1734         while (fgets(buf, sizeof(buf), fp)) {
1735                 /* The format is just "Commit Parent1 Parent2 ...\n" */
1736                 int len = strlen(buf);
1737                 struct commit_graft *graft = read_graft_line(buf, len);
1738                 if (graft)
1739                         register_commit_graft(graft, 0);
1740         }
1741         fclose(fp);
1742         return 0;
1743 }
1744
1745 /*
1746  * How many columns do we need to show line numbers in decimal?
1747  */
1748 static int lineno_width(int lines)
1749 {
1750         int i, width;
1751
1752         for (width = 1, i = 10; i <= lines + 1; width++)
1753                 i *= 10;
1754         return width;
1755 }
1756
1757 /*
1758  * How many columns do we need to show line numbers, authors,
1759  * and filenames?
1760  */
1761 static void find_alignment(struct scoreboard *sb, int *option)
1762 {
1763         int longest_src_lines = 0;
1764         int longest_dst_lines = 0;
1765         unsigned largest_score = 0;
1766         struct blame_entry *e;
1767
1768         for (e = sb->ent; e; e = e->next) {
1769                 struct origin *suspect = e->suspect;
1770                 struct commit_info ci;
1771                 int num;
1772
1773                 if (strcmp(suspect->path, sb->path))
1774                         *option |= OUTPUT_SHOW_NAME;
1775                 num = strlen(suspect->path);
1776                 if (longest_file < num)
1777                         longest_file = num;
1778                 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1779                         suspect->commit->object.flags |= METAINFO_SHOWN;
1780                         get_commit_info(suspect->commit, &ci, 1);
1781                         num = utf8_strwidth(ci.author);
1782                         if (longest_author < num)
1783                                 longest_author = num;
1784                 }
1785                 num = e->s_lno + e->num_lines;
1786                 if (longest_src_lines < num)
1787                         longest_src_lines = num;
1788                 num = e->lno + e->num_lines;
1789                 if (longest_dst_lines < num)
1790                         longest_dst_lines = num;
1791                 if (largest_score < ent_score(sb, e))
1792                         largest_score = ent_score(sb, e);
1793         }
1794         max_orig_digits = lineno_width(longest_src_lines);
1795         max_digits = lineno_width(longest_dst_lines);
1796         max_score_digits = lineno_width(largest_score);
1797 }
1798
1799 /*
1800  * For debugging -- origin is refcounted, and this asserts that
1801  * we do not underflow.
1802  */
1803 static void sanity_check_refcnt(struct scoreboard *sb)
1804 {
1805         int baa = 0;
1806         struct blame_entry *ent;
1807
1808         for (ent = sb->ent; ent; ent = ent->next) {
1809                 /* Nobody should have zero or negative refcnt */
1810                 if (ent->suspect->refcnt <= 0) {
1811                         fprintf(stderr, "%s in %s has negative refcnt %d\n",
1812                                 ent->suspect->path,
1813                                 sha1_to_hex(ent->suspect->commit->object.sha1),
1814                                 ent->suspect->refcnt);
1815                         baa = 1;
1816                 }
1817         }
1818         if (baa) {
1819                 int opt = 0160;
1820                 find_alignment(sb, &opt);
1821                 output(sb, opt);
1822                 die("Baa %d!", baa);
1823         }
1824 }
1825
1826 /*
1827  * Used for the command line parsing; check if the path exists
1828  * in the working tree.
1829  */
1830 static int has_string_in_work_tree(const char *path)
1831 {
1832         struct stat st;
1833         return !lstat(path, &st);
1834 }
1835
1836 static unsigned parse_score(const char *arg)
1837 {
1838         char *end;
1839         unsigned long score = strtoul(arg, &end, 10);
1840         if (*end)
1841                 return 0;
1842         return score;
1843 }
1844
1845 static const char *add_prefix(const char *prefix, const char *path)
1846 {
1847         return prefix_path(prefix, prefix ? strlen(prefix) : 0, path);
1848 }
1849
1850 /*
1851  * Parsing of (comma separated) one item in the -L option
1852  */
1853 static const char *parse_loc(const char *spec,
1854                              struct scoreboard *sb, long lno,
1855                              long begin, long *ret)
1856 {
1857         char *term;
1858         const char *line;
1859         long num;
1860         int reg_error;
1861         regex_t regexp;
1862         regmatch_t match[1];
1863
1864         /* Allow "-L <something>,+20" to mean starting at <something>
1865          * for 20 lines, or "-L <something>,-5" for 5 lines ending at
1866          * <something>.
1867          */
1868         if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
1869                 num = strtol(spec + 1, &term, 10);
1870                 if (term != spec + 1) {
1871                         if (spec[0] == '-')
1872                                 num = 0 - num;
1873                         if (0 < num)
1874                                 *ret = begin + num - 2;
1875                         else if (!num)
1876                                 *ret = begin;
1877                         else
1878                                 *ret = begin + num;
1879                         return term;
1880                 }
1881                 return spec;
1882         }
1883         num = strtol(spec, &term, 10);
1884         if (term != spec) {
1885                 *ret = num;
1886                 return term;
1887         }
1888         if (spec[0] != '/')
1889                 return spec;
1890
1891         /* it could be a regexp of form /.../ */
1892         for (term = (char *) spec + 1; *term && *term != '/'; term++) {
1893                 if (*term == '\\')
1894                         term++;
1895         }
1896         if (*term != '/')
1897                 return spec;
1898
1899         /* try [spec+1 .. term-1] as regexp */
1900         *term = 0;
1901         begin--; /* input is in human terms */
1902         line = nth_line(sb, begin);
1903
1904         if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
1905             !(reg_error = regexec(&regexp, line, 1, match, 0))) {
1906                 const char *cp = line + match[0].rm_so;
1907                 const char *nline;
1908
1909                 while (begin++ < lno) {
1910                         nline = nth_line(sb, begin);
1911                         if (line <= cp && cp < nline)
1912                                 break;
1913                         line = nline;
1914                 }
1915                 *ret = begin;
1916                 regfree(&regexp);
1917                 *term++ = '/';
1918                 return term;
1919         }
1920         else {
1921                 char errbuf[1024];
1922                 regerror(reg_error, &regexp, errbuf, 1024);
1923                 die("-L parameter '%s': %s", spec + 1, errbuf);
1924         }
1925 }
1926
1927 /*
1928  * Parsing of -L option
1929  */
1930 static void prepare_blame_range(struct scoreboard *sb,
1931                                 const char *bottomtop,
1932                                 long lno,
1933                                 long *bottom, long *top)
1934 {
1935         const char *term;
1936
1937         term = parse_loc(bottomtop, sb, lno, 1, bottom);
1938         if (*term == ',') {
1939                 term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
1940                 if (*term)
1941                         usage(blame_usage);
1942         }
1943         if (*term)
1944                 usage(blame_usage);
1945 }
1946
1947 static int git_blame_config(const char *var, const char *value, void *cb)
1948 {
1949         if (!strcmp(var, "blame.showroot")) {
1950                 show_root = git_config_bool(var, value);
1951                 return 0;
1952         }
1953         if (!strcmp(var, "blame.blankboundary")) {
1954                 blank_boundary = git_config_bool(var, value);
1955                 return 0;
1956         }
1957         if (!strcmp(var, "blame.date")) {
1958                 if (!value)
1959                         return config_error_nonbool(var);
1960                 blame_date_mode = parse_date_format(value);
1961                 return 0;
1962         }
1963         return git_default_config(var, value, cb);
1964 }
1965
1966 /*
1967  * Prepare a dummy commit that represents the work tree (or staged) item.
1968  * Note that annotating work tree item never works in the reverse.
1969  */
1970 static struct commit *fake_working_tree_commit(const char *path, const char *contents_from)
1971 {
1972         struct commit *commit;
1973         struct origin *origin;
1974         unsigned char head_sha1[20];
1975         struct strbuf buf = STRBUF_INIT;
1976         const char *ident;
1977         time_t now;
1978         int size, len;
1979         struct cache_entry *ce;
1980         unsigned mode;
1981
1982         if (get_sha1("HEAD", head_sha1))
1983                 die("No such ref: HEAD");
1984
1985         time(&now);
1986         commit = xcalloc(1, sizeof(*commit));
1987         commit->parents = xcalloc(1, sizeof(*commit->parents));
1988         commit->parents->item = lookup_commit_reference(head_sha1);
1989         commit->object.parsed = 1;
1990         commit->date = now;
1991         commit->object.type = OBJ_COMMIT;
1992
1993         origin = make_origin(commit, path);
1994
1995         if (!contents_from || strcmp("-", contents_from)) {
1996                 struct stat st;
1997                 const char *read_from;
1998
1999                 if (contents_from) {
2000                         if (stat(contents_from, &st) < 0)
2001                                 die("Cannot stat %s", contents_from);
2002                         read_from = contents_from;
2003                 }
2004                 else {
2005                         if (lstat(path, &st) < 0)
2006                                 die("Cannot lstat %s", path);
2007                         read_from = path;
2008                 }
2009                 mode = canon_mode(st.st_mode);
2010                 switch (st.st_mode & S_IFMT) {
2011                 case S_IFREG:
2012                         if (strbuf_read_file(&buf, read_from, st.st_size) != st.st_size)
2013                                 die("cannot open or read %s", read_from);
2014                         break;
2015                 case S_IFLNK:
2016                         if (strbuf_readlink(&buf, read_from, st.st_size) < 0)
2017                                 die("cannot readlink %s", read_from);
2018                         break;
2019                 default:
2020                         die("unsupported file type %s", read_from);
2021                 }
2022         }
2023         else {
2024                 /* Reading from stdin */
2025                 contents_from = "standard input";
2026                 mode = 0;
2027                 if (strbuf_read(&buf, 0, 0) < 0)
2028                         die("read error %s from stdin", strerror(errno));
2029         }
2030         convert_to_git(path, buf.buf, buf.len, &buf, 0);
2031         origin->file.ptr = buf.buf;
2032         origin->file.size = buf.len;
2033         pretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_sha1);
2034         commit->util = origin;
2035
2036         /*
2037          * Read the current index, replace the path entry with
2038          * origin->blob_sha1 without mucking with its mode or type
2039          * bits; we are not going to write this index out -- we just
2040          * want to run "diff-index --cached".
2041          */
2042         discard_cache();
2043         read_cache();
2044
2045         len = strlen(path);
2046         if (!mode) {
2047                 int pos = cache_name_pos(path, len);
2048                 if (0 <= pos)
2049                         mode = active_cache[pos]->ce_mode;
2050                 else
2051                         /* Let's not bother reading from HEAD tree */
2052                         mode = S_IFREG | 0644;
2053         }
2054         size = cache_entry_size(len);
2055         ce = xcalloc(1, size);
2056         hashcpy(ce->sha1, origin->blob_sha1);
2057         memcpy(ce->name, path, len);
2058         ce->ce_flags = create_ce_flags(len, 0);
2059         ce->ce_mode = create_ce_mode(mode);
2060         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
2061
2062         /*
2063          * We are not going to write this out, so this does not matter
2064          * right now, but someday we might optimize diff-index --cached
2065          * with cache-tree information.
2066          */
2067         cache_tree_invalidate_path(active_cache_tree, path);
2068
2069         commit->buffer = xmalloc(400);
2070         ident = fmt_ident("Not Committed Yet", "not.committed.yet", NULL, 0);
2071         snprintf(commit->buffer, 400,
2072                 "tree 0000000000000000000000000000000000000000\n"
2073                 "parent %s\n"
2074                 "author %s\n"
2075                 "committer %s\n\n"
2076                 "Version of %s from %s\n",
2077                 sha1_to_hex(head_sha1),
2078                 ident, ident, path, contents_from ? contents_from : path);
2079         return commit;
2080 }
2081
2082 static const char *prepare_final(struct scoreboard *sb)
2083 {
2084         int i;
2085         const char *final_commit_name = NULL;
2086         struct rev_info *revs = sb->revs;
2087
2088         /*
2089          * There must be one and only one positive commit in the
2090          * revs->pending array.
2091          */
2092         for (i = 0; i < revs->pending.nr; i++) {
2093                 struct object *obj = revs->pending.objects[i].item;
2094                 if (obj->flags & UNINTERESTING)
2095                         continue;
2096                 while (obj->type == OBJ_TAG)
2097                         obj = deref_tag(obj, NULL, 0);
2098                 if (obj->type != OBJ_COMMIT)
2099                         die("Non commit %s?", revs->pending.objects[i].name);
2100                 if (sb->final)
2101                         die("More than one commit to dig from %s and %s?",
2102                             revs->pending.objects[i].name,
2103                             final_commit_name);
2104                 sb->final = (struct commit *) obj;
2105                 final_commit_name = revs->pending.objects[i].name;
2106         }
2107         return final_commit_name;
2108 }
2109
2110 static const char *prepare_initial(struct scoreboard *sb)
2111 {
2112         int i;
2113         const char *final_commit_name = NULL;
2114         struct rev_info *revs = sb->revs;
2115
2116         /*
2117          * There must be one and only one negative commit, and it must be
2118          * the boundary.
2119          */
2120         for (i = 0; i < revs->pending.nr; i++) {
2121                 struct object *obj = revs->pending.objects[i].item;
2122                 if (!(obj->flags & UNINTERESTING))
2123                         continue;
2124                 while (obj->type == OBJ_TAG)
2125                         obj = deref_tag(obj, NULL, 0);
2126                 if (obj->type != OBJ_COMMIT)
2127                         die("Non commit %s?", revs->pending.objects[i].name);
2128                 if (sb->final)
2129                         die("More than one commit to dig down to %s and %s?",
2130                             revs->pending.objects[i].name,
2131                             final_commit_name);
2132                 sb->final = (struct commit *) obj;
2133                 final_commit_name = revs->pending.objects[i].name;
2134         }
2135         if (!final_commit_name)
2136                 die("No commit to dig down to?");
2137         return final_commit_name;
2138 }
2139
2140 static int blame_copy_callback(const struct option *option, const char *arg, int unset)
2141 {
2142         int *opt = option->value;
2143
2144         /*
2145          * -C enables copy from removed files;
2146          * -C -C enables copy from existing files, but only
2147          *       when blaming a new file;
2148          * -C -C -C enables copy from existing files for
2149          *          everybody
2150          */
2151         if (*opt & PICKAXE_BLAME_COPY_HARDER)
2152                 *opt |= PICKAXE_BLAME_COPY_HARDEST;
2153         if (*opt & PICKAXE_BLAME_COPY)
2154                 *opt |= PICKAXE_BLAME_COPY_HARDER;
2155         *opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
2156
2157         if (arg)
2158                 blame_copy_score = parse_score(arg);
2159         return 0;
2160 }
2161
2162 static int blame_move_callback(const struct option *option, const char *arg, int unset)
2163 {
2164         int *opt = option->value;
2165
2166         *opt |= PICKAXE_BLAME_MOVE;
2167
2168         if (arg)
2169                 blame_move_score = parse_score(arg);
2170         return 0;
2171 }
2172
2173 static int blame_bottomtop_callback(const struct option *option, const char *arg, int unset)
2174 {
2175         const char **bottomtop = option->value;
2176         if (!arg)
2177                 return -1;
2178         if (*bottomtop)
2179                 die("More than one '-L n,m' option given");
2180         *bottomtop = arg;
2181         return 0;
2182 }
2183
2184 int cmd_blame(int argc, const char **argv, const char *prefix)
2185 {
2186         struct rev_info revs;
2187         const char *path;
2188         struct scoreboard sb;
2189         struct origin *o;
2190         struct blame_entry *ent;
2191         long dashdash_pos, bottom, top, lno;
2192         const char *final_commit_name = NULL;
2193         enum object_type type;
2194
2195         static const char *bottomtop = NULL;
2196         static int output_option = 0, opt = 0;
2197         static int show_stats = 0;
2198         static const char *revs_file = NULL;
2199         static const char *contents_from = NULL;
2200         static const struct option options[] = {
2201                 OPT_BOOLEAN(0, "incremental", &incremental, "Show blame entries as we find them, incrementally"),
2202                 OPT_BOOLEAN('b', NULL, &blank_boundary, "Show blank SHA-1 for boundary commits (Default: off)"),
2203                 OPT_BOOLEAN(0, "root", &show_root, "Do not treat root commits as boundaries (Default: off)"),
2204                 OPT_BOOLEAN(0, "show-stats", &show_stats, "Show work cost statistics"),
2205                 OPT_BIT(0, "score-debug", &output_option, "Show output score for blame entries", OUTPUT_SHOW_SCORE),
2206                 OPT_BIT('f', "show-name", &output_option, "Show original filename (Default: auto)", OUTPUT_SHOW_NAME),
2207                 OPT_BIT('n', "show-number", &output_option, "Show original linenumber (Default: off)", OUTPUT_SHOW_NUMBER),
2208                 OPT_BIT('p', "porcelain", &output_option, "Show in a format designed for machine consumption", OUTPUT_PORCELAIN),
2209                 OPT_BIT('c', NULL, &output_option, "Use the same output mode as git-annotate (Default: off)", OUTPUT_ANNOTATE_COMPAT),
2210                 OPT_BIT('t', NULL, &output_option, "Show raw timestamp (Default: off)", OUTPUT_RAW_TIMESTAMP),
2211                 OPT_BIT('l', NULL, &output_option, "Show long commit SHA1 (Default: off)", OUTPUT_LONG_OBJECT_NAME),
2212                 OPT_BIT('s', NULL, &output_option, "Suppress author name and timestamp (Default: off)", OUTPUT_NO_AUTHOR),
2213                 OPT_BIT('w', NULL, &xdl_opts, "Ignore whitespace differences", XDF_IGNORE_WHITESPACE),
2214                 OPT_STRING('S', NULL, &revs_file, "file", "Use revisions from <file> instead of calling git-rev-list"),
2215                 OPT_STRING(0, "contents", &contents_from, "file", "Use <file>'s contents as the final image"),
2216                 { OPTION_CALLBACK, 'C', NULL, &opt, "score", "Find line copies within and across files", PARSE_OPT_OPTARG, blame_copy_callback },
2217                 { OPTION_CALLBACK, 'M', NULL, &opt, "score", "Find line movements within and across files", PARSE_OPT_OPTARG, blame_move_callback },
2218                 OPT_CALLBACK('L', NULL, &bottomtop, "n,m", "Process only line range n,m, counting from 1", blame_bottomtop_callback),
2219                 OPT_END()
2220         };
2221
2222         struct parse_opt_ctx_t ctx;
2223         int cmd_is_annotate = !strcmp(argv[0], "annotate");
2224
2225         git_config(git_blame_config, NULL);
2226         init_revisions(&revs, NULL);
2227         revs.date_mode = blame_date_mode;
2228
2229         save_commit_buffer = 0;
2230         dashdash_pos = 0;
2231
2232         parse_options_start(&ctx, argc, argv, PARSE_OPT_KEEP_DASHDASH |
2233                             PARSE_OPT_KEEP_ARGV0);
2234         for (;;) {
2235                 switch (parse_options_step(&ctx, options, blame_opt_usage)) {
2236                 case PARSE_OPT_HELP:
2237                         exit(129);
2238                 case PARSE_OPT_DONE:
2239                         if (ctx.argv[0])
2240                                 dashdash_pos = ctx.cpidx;
2241                         goto parse_done;
2242                 }
2243
2244                 if (!strcmp(ctx.argv[0], "--reverse")) {
2245                         ctx.argv[0] = "--children";
2246                         reverse = 1;
2247                 }
2248                 parse_revision_opt(&revs, &ctx, options, blame_opt_usage);
2249         }
2250 parse_done:
2251         argc = parse_options_end(&ctx);
2252
2253         if (revs_file && read_ancestry(revs_file))
2254                 die("reading graft file %s failed: %s",
2255                     revs_file, strerror(errno));
2256
2257         if (cmd_is_annotate) {
2258                 output_option |= OUTPUT_ANNOTATE_COMPAT;
2259                 blame_date_mode = DATE_ISO8601;
2260         } else {
2261                 blame_date_mode = revs.date_mode;
2262         }
2263
2264         /* The maximum width used to show the dates */
2265         switch (blame_date_mode) {
2266         case DATE_RFC2822:
2267                 blame_date_width = sizeof("Thu, 19 Oct 2006 16:00:04 -0700");
2268                 break;
2269         case DATE_ISO8601:
2270                 blame_date_width = sizeof("2006-10-19 16:00:04 -0700");
2271                 break;
2272         case DATE_RAW:
2273                 blame_date_width = sizeof("1161298804 -0700");
2274                 break;
2275         case DATE_SHORT:
2276                 blame_date_width = sizeof("2006-10-19");
2277                 break;
2278         case DATE_RELATIVE:
2279                 /* "normal" is used as the fallback for "relative" */
2280         case DATE_LOCAL:
2281         case DATE_NORMAL:
2282                 blame_date_width = sizeof("Thu Oct 19 16:00:04 2006 -0700");
2283                 break;
2284         }
2285         blame_date_width -= 1; /* strip the null */
2286
2287         if (DIFF_OPT_TST(&revs.diffopt, FIND_COPIES_HARDER))
2288                 opt |= (PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE |
2289                         PICKAXE_BLAME_COPY_HARDER);
2290
2291         if (!blame_move_score)
2292                 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
2293         if (!blame_copy_score)
2294                 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
2295
2296         /*
2297          * We have collected options unknown to us in argv[1..unk]
2298          * which are to be passed to revision machinery if we are
2299          * going to do the "bottom" processing.
2300          *
2301          * The remaining are:
2302          *
2303          * (1) if dashdash_pos != 0, its either
2304          *     "blame [revisions] -- <path>" or
2305          *     "blame -- <path> <rev>"
2306          *
2307          * (2) otherwise, its one of the two:
2308          *     "blame [revisions] <path>"
2309          *     "blame <path> <rev>"
2310          *
2311          * Note that we must strip out <path> from the arguments: we do not
2312          * want the path pruning but we may want "bottom" processing.
2313          */
2314         if (dashdash_pos) {
2315                 switch (argc - dashdash_pos - 1) {
2316                 case 2: /* (1b) */
2317                         if (argc != 4)
2318                                 usage_with_options(blame_opt_usage, options);
2319                         /* reorder for the new way: <rev> -- <path> */
2320                         argv[1] = argv[3];
2321                         argv[3] = argv[2];
2322                         argv[2] = "--";
2323                         /* FALLTHROUGH */
2324                 case 1: /* (1a) */
2325                         path = add_prefix(prefix, argv[--argc]);
2326                         argv[argc] = NULL;
2327                         break;
2328                 default:
2329                         usage_with_options(blame_opt_usage, options);
2330                 }
2331         } else {
2332                 if (argc < 2)
2333                         usage_with_options(blame_opt_usage, options);
2334                 path = add_prefix(prefix, argv[argc - 1]);
2335                 if (argc == 3 && !has_string_in_work_tree(path)) { /* (2b) */
2336                         path = add_prefix(prefix, argv[1]);
2337                         argv[1] = argv[2];
2338                 }
2339                 argv[argc - 1] = "--";
2340
2341                 setup_work_tree();
2342                 if (!has_string_in_work_tree(path))
2343                         die("cannot stat path %s: %s", path, strerror(errno));
2344         }
2345
2346         setup_revisions(argc, argv, &revs, NULL);
2347         memset(&sb, 0, sizeof(sb));
2348
2349         sb.revs = &revs;
2350         if (!reverse)
2351                 final_commit_name = prepare_final(&sb);
2352         else if (contents_from)
2353                 die("--contents and --children do not blend well.");
2354         else
2355                 final_commit_name = prepare_initial(&sb);
2356
2357         if (!sb.final) {
2358                 /*
2359                  * "--not A B -- path" without anything positive;
2360                  * do not default to HEAD, but use the working tree
2361                  * or "--contents".
2362                  */
2363                 setup_work_tree();
2364                 sb.final = fake_working_tree_commit(path, contents_from);
2365                 add_pending_object(&revs, &(sb.final->object), ":");
2366         }
2367         else if (contents_from)
2368                 die("Cannot use --contents with final commit object name");
2369
2370         /*
2371          * If we have bottom, this will mark the ancestors of the
2372          * bottom commits we would reach while traversing as
2373          * uninteresting.
2374          */
2375         if (prepare_revision_walk(&revs))
2376                 die("revision walk setup failed");
2377
2378         if (is_null_sha1(sb.final->object.sha1)) {
2379                 char *buf;
2380                 o = sb.final->util;
2381                 buf = xmalloc(o->file.size + 1);
2382                 memcpy(buf, o->file.ptr, o->file.size + 1);
2383                 sb.final_buf = buf;
2384                 sb.final_buf_size = o->file.size;
2385         }
2386         else {
2387                 o = get_origin(&sb, sb.final, path);
2388                 if (fill_blob_sha1(o))
2389                         die("no such path %s in %s", path, final_commit_name);
2390
2391                 sb.final_buf = read_sha1_file(o->blob_sha1, &type,
2392                                               &sb.final_buf_size);
2393                 if (!sb.final_buf)
2394                         die("Cannot read blob %s for path %s",
2395                             sha1_to_hex(o->blob_sha1),
2396                             path);
2397         }
2398         num_read_blob++;
2399         lno = prepare_lines(&sb);
2400
2401         bottom = top = 0;
2402         if (bottomtop)
2403                 prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);
2404         if (bottom && top && top < bottom) {
2405                 long tmp;
2406                 tmp = top; top = bottom; bottom = tmp;
2407         }
2408         if (bottom < 1)
2409                 bottom = 1;
2410         if (top < 1)
2411                 top = lno;
2412         bottom--;
2413         if (lno < top)
2414                 die("file %s has only %lu lines", path, lno);
2415
2416         ent = xcalloc(1, sizeof(*ent));
2417         ent->lno = bottom;
2418         ent->num_lines = top - bottom;
2419         ent->suspect = o;
2420         ent->s_lno = bottom;
2421
2422         sb.ent = ent;
2423         sb.path = path;
2424
2425         read_mailmap(&mailmap, NULL);
2426
2427         if (!incremental)
2428                 setup_pager();
2429
2430         assign_blame(&sb, opt);
2431
2432         if (incremental)
2433                 return 0;
2434
2435         coalesce(&sb);
2436
2437         if (!(output_option & OUTPUT_PORCELAIN))
2438                 find_alignment(&sb, &output_option);
2439
2440         output(&sb, output_option);
2441         free((void *)sb.final_buf);
2442         for (ent = sb.ent; ent; ) {
2443                 struct blame_entry *e = ent->next;
2444                 free(ent);
2445                 ent = e;
2446         }
2447
2448         if (show_stats) {
2449                 printf("num read blob: %d\n", num_read_blob);
2450                 printf("num get patch: %d\n", num_get_patch);
2451                 printf("num commits: %d\n", num_commits);
2452         }
2453         return 0;
2454 }