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