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