![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
54ab675624166826b71013952bb1efd293d5d0d0
1 /*
2 * Pickaxe
3 *
4 * Copyright (c) 2006, Junio C Hamano
5 */
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"
19 static char blame_usage[] =
20 "git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n"
21 " -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
22 " -b Show blank SHA-1 for boundary commits (Default: off)\n"
23 " -l, --long Show long commit SHA1 (Default: off)\n"
24 " --root Do not treat root commits as boundaries (Default: off)\n"
25 " -t, --time Show raw timestamp (Default: off)\n"
26 " -f, --show-name Show original filename (Default: auto)\n"
27 " -n, --show-number Show original linenumber (Default: off)\n"
28 " -p, --porcelain Show in a format designed for machine consumption\n"
29 " -L n,m Process only line range n,m, counting from 1\n"
30 " -M, -C Find line movements within and across files\n"
31 " --incremental Show blame entries as we find them, incrementally\n"
32 " -S revs-file Use revisions from revs-file instead of calling git-rev-list\n";
34 static int longest_file;
35 static int longest_author;
36 static int max_orig_digits;
37 static int max_digits;
38 static int max_score_digits;
39 static int show_root;
40 static int blank_boundary;
41 static int incremental;
43 #ifndef DEBUG
44 #define DEBUG 0
45 #endif
47 /* stats */
48 static int num_read_blob;
49 static int num_get_patch;
50 static int num_commits;
52 #define PICKAXE_BLAME_MOVE 01
53 #define PICKAXE_BLAME_COPY 02
54 #define PICKAXE_BLAME_COPY_HARDER 04
56 /*
57 * blame for a blame_entry with score lower than these thresholds
58 * is not passed to the parent using move/copy logic.
59 */
60 static unsigned blame_move_score;
61 static unsigned blame_copy_score;
62 #define BLAME_DEFAULT_MOVE_SCORE 20
63 #define BLAME_DEFAULT_COPY_SCORE 40
65 /* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
66 #define METAINFO_SHOWN (1u<<12)
67 #define MORE_THAN_ONE_PATH (1u<<13)
69 /*
70 * One blob in a commit that is being suspected
71 */
72 struct origin {
73 int refcnt;
74 struct commit *commit;
75 mmfile_t file;
76 unsigned char blob_sha1[20];
77 char path[FLEX_ARRAY];
78 };
80 static char *fill_origin_blob(struct origin *o, mmfile_t *file)
81 {
82 if (!o->file.ptr) {
83 char type[10];
84 num_read_blob++;
85 file->ptr = read_sha1_file(o->blob_sha1, type,
86 (unsigned long *)(&(file->size)));
87 o->file = *file;
88 }
89 else
90 *file = o->file;
91 return file->ptr;
92 }
94 static inline struct origin *origin_incref(struct origin *o)
95 {
96 if (o)
97 o->refcnt++;
98 return o;
99 }
101 static void origin_decref(struct origin *o)
102 {
103 if (o && --o->refcnt <= 0) {
104 if (o->file.ptr)
105 free(o->file.ptr);
106 memset(o, 0, sizeof(*o));
107 free(o);
108 }
109 }
111 struct blame_entry {
112 struct blame_entry *prev;
113 struct blame_entry *next;
115 /* the first line of this group in the final image;
116 * internally all line numbers are 0 based.
117 */
118 int lno;
120 /* how many lines this group has */
121 int num_lines;
123 /* the commit that introduced this group into the final image */
124 struct origin *suspect;
126 /* true if the suspect is truly guilty; false while we have not
127 * checked if the group came from one of its parents.
128 */
129 char guilty;
131 /* the line number of the first line of this group in the
132 * suspect's file; internally all line numbers are 0 based.
133 */
134 int s_lno;
136 /* how significant this entry is -- cached to avoid
137 * scanning the lines over and over
138 */
139 unsigned score;
140 };
142 struct scoreboard {
143 /* the final commit (i.e. where we started digging from) */
144 struct commit *final;
146 const char *path;
148 /* the contents in the final; pointed into by buf pointers of
149 * blame_entries
150 */
151 const char *final_buf;
152 unsigned long final_buf_size;
154 /* linked list of blames */
155 struct blame_entry *ent;
157 /* look-up a line in the final buffer */
158 int num_lines;
159 int *lineno;
160 };
162 static int cmp_suspect(struct origin *a, struct origin *b)
163 {
164 int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);
165 if (cmp)
166 return cmp;
167 return strcmp(a->path, b->path);
168 }
170 #define cmp_suspect(a, b) ( ((a)==(b)) ? 0 : cmp_suspect(a,b) )
172 static void sanity_check_refcnt(struct scoreboard *);
174 static void coalesce(struct scoreboard *sb)
175 {
176 struct blame_entry *ent, *next;
178 for (ent = sb->ent; ent && (next = ent->next); ent = next) {
179 if (!cmp_suspect(ent->suspect, next->suspect) &&
180 ent->guilty == next->guilty &&
181 ent->s_lno + ent->num_lines == next->s_lno) {
182 ent->num_lines += next->num_lines;
183 ent->next = next->next;
184 if (ent->next)
185 ent->next->prev = ent;
186 origin_decref(next->suspect);
187 free(next);
188 ent->score = 0;
189 next = ent; /* again */
190 }
191 }
193 if (DEBUG) /* sanity */
194 sanity_check_refcnt(sb);
195 }
197 static struct origin *make_origin(struct commit *commit, const char *path)
198 {
199 struct origin *o;
200 o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
201 o->commit = commit;
202 o->refcnt = 1;
203 strcpy(o->path, path);
204 return o;
205 }
207 static struct origin *get_origin(struct scoreboard *sb,
208 struct commit *commit,
209 const char *path)
210 {
211 struct blame_entry *e;
213 for (e = sb->ent; e; e = e->next) {
214 if (e->suspect->commit == commit &&
215 !strcmp(e->suspect->path, path))
216 return origin_incref(e->suspect);
217 }
218 return make_origin(commit, path);
219 }
221 static int fill_blob_sha1(struct origin *origin)
222 {
223 unsigned mode;
224 char type[10];
226 if (!is_null_sha1(origin->blob_sha1))
227 return 0;
228 if (get_tree_entry(origin->commit->object.sha1,
229 origin->path,
230 origin->blob_sha1, &mode))
231 goto error_out;
232 if (sha1_object_info(origin->blob_sha1, type, NULL) ||
233 strcmp(type, blob_type))
234 goto error_out;
235 return 0;
236 error_out:
237 hashclr(origin->blob_sha1);
238 return -1;
239 }
241 static struct origin *find_origin(struct scoreboard *sb,
242 struct commit *parent,
243 struct origin *origin)
244 {
245 struct origin *porigin = NULL;
246 struct diff_options diff_opts;
247 const char *paths[2];
249 if (parent->util) {
250 /* This is a freestanding copy of origin and not
251 * refcounted.
252 */
253 struct origin *cached = parent->util;
254 if (!strcmp(cached->path, origin->path)) {
255 porigin = get_origin(sb, parent, cached->path);
256 if (porigin->refcnt == 1)
257 hashcpy(porigin->blob_sha1, cached->blob_sha1);
258 return porigin;
259 }
260 /* otherwise it was not very useful; free it */
261 free(parent->util);
262 parent->util = NULL;
263 }
265 /* See if the origin->path is different between parent
266 * and origin first. Most of the time they are the
267 * same and diff-tree is fairly efficient about this.
268 */
269 diff_setup(&diff_opts);
270 diff_opts.recursive = 1;
271 diff_opts.detect_rename = 0;
272 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
273 paths[0] = origin->path;
274 paths[1] = NULL;
276 diff_tree_setup_paths(paths, &diff_opts);
277 if (diff_setup_done(&diff_opts) < 0)
278 die("diff-setup");
279 diff_tree_sha1(parent->tree->object.sha1,
280 origin->commit->tree->object.sha1,
281 "", &diff_opts);
282 diffcore_std(&diff_opts);
284 /* It is either one entry that says "modified", or "created",
285 * or nothing.
286 */
287 if (!diff_queued_diff.nr) {
288 /* The path is the same as parent */
289 porigin = get_origin(sb, parent, origin->path);
290 hashcpy(porigin->blob_sha1, origin->blob_sha1);
291 }
292 else if (diff_queued_diff.nr != 1)
293 die("internal error in blame::find_origin");
294 else {
295 struct diff_filepair *p = diff_queued_diff.queue[0];
296 switch (p->status) {
297 default:
298 die("internal error in blame::find_origin (%c)",
299 p->status);
300 case 'M':
301 porigin = get_origin(sb, parent, origin->path);
302 hashcpy(porigin->blob_sha1, p->one->sha1);
303 break;
304 case 'A':
305 case 'T':
306 /* Did not exist in parent, or type changed */
307 break;
308 }
309 }
310 diff_flush(&diff_opts);
311 if (porigin) {
312 struct origin *cached;
313 cached = make_origin(porigin->commit, porigin->path);
314 hashcpy(cached->blob_sha1, porigin->blob_sha1);
315 parent->util = cached;
316 }
317 return porigin;
318 }
320 static struct origin *find_rename(struct scoreboard *sb,
321 struct commit *parent,
322 struct origin *origin)
323 {
324 struct origin *porigin = NULL;
325 struct diff_options diff_opts;
326 int i;
327 const char *paths[2];
329 diff_setup(&diff_opts);
330 diff_opts.recursive = 1;
331 diff_opts.detect_rename = DIFF_DETECT_RENAME;
332 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
333 diff_opts.single_follow = origin->path;
334 paths[0] = NULL;
335 diff_tree_setup_paths(paths, &diff_opts);
336 if (diff_setup_done(&diff_opts) < 0)
337 die("diff-setup");
338 diff_tree_sha1(parent->tree->object.sha1,
339 origin->commit->tree->object.sha1,
340 "", &diff_opts);
341 diffcore_std(&diff_opts);
343 for (i = 0; i < diff_queued_diff.nr; i++) {
344 struct diff_filepair *p = diff_queued_diff.queue[i];
345 if ((p->status == 'R' || p->status == 'C') &&
346 !strcmp(p->two->path, origin->path)) {
347 porigin = get_origin(sb, parent, p->one->path);
348 hashcpy(porigin->blob_sha1, p->one->sha1);
349 break;
350 }
351 }
352 diff_flush(&diff_opts);
353 return porigin;
354 }
356 struct chunk {
357 /* line number in postimage; up to but not including this
358 * line is the same as preimage
359 */
360 int same;
362 /* preimage line number after this chunk */
363 int p_next;
365 /* postimage line number after this chunk */
366 int t_next;
367 };
369 struct patch {
370 struct chunk *chunks;
371 int num;
372 };
374 struct blame_diff_state {
375 struct xdiff_emit_state xm;
376 struct patch *ret;
377 unsigned hunk_post_context;
378 unsigned hunk_in_pre_context : 1;
379 };
381 static void process_u_diff(void *state_, char *line, unsigned long len)
382 {
383 struct blame_diff_state *state = state_;
384 struct chunk *chunk;
385 int off1, off2, len1, len2, num;
387 num = state->ret->num;
388 if (len < 4 || line[0] != '@' || line[1] != '@') {
389 if (state->hunk_in_pre_context && line[0] == ' ')
390 state->ret->chunks[num - 1].same++;
391 else {
392 state->hunk_in_pre_context = 0;
393 if (line[0] == ' ')
394 state->hunk_post_context++;
395 else
396 state->hunk_post_context = 0;
397 }
398 return;
399 }
401 if (num && state->hunk_post_context) {
402 chunk = &state->ret->chunks[num - 1];
403 chunk->p_next -= state->hunk_post_context;
404 chunk->t_next -= state->hunk_post_context;
405 }
406 state->ret->num = ++num;
407 state->ret->chunks = xrealloc(state->ret->chunks,
408 sizeof(struct chunk) * num);
409 chunk = &state->ret->chunks[num - 1];
410 if (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {
411 state->ret->num--;
412 return;
413 }
415 /* Line numbers in patch output are one based. */
416 off1--;
417 off2--;
419 chunk->same = len2 ? off2 : (off2 + 1);
421 chunk->p_next = off1 + (len1 ? len1 : 1);
422 chunk->t_next = chunk->same + len2;
423 state->hunk_in_pre_context = 1;
424 state->hunk_post_context = 0;
425 }
427 static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
428 int context)
429 {
430 struct blame_diff_state state;
431 xpparam_t xpp;
432 xdemitconf_t xecfg;
433 xdemitcb_t ecb;
435 xpp.flags = XDF_NEED_MINIMAL;
436 xecfg.ctxlen = context;
437 xecfg.flags = 0;
438 ecb.outf = xdiff_outf;
439 ecb.priv = &state;
440 memset(&state, 0, sizeof(state));
441 state.xm.consume = process_u_diff;
442 state.ret = xmalloc(sizeof(struct patch));
443 state.ret->chunks = NULL;
444 state.ret->num = 0;
446 xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);
448 if (state.ret->num) {
449 struct chunk *chunk;
450 chunk = &state.ret->chunks[state.ret->num - 1];
451 chunk->p_next -= state.hunk_post_context;
452 chunk->t_next -= state.hunk_post_context;
453 }
454 return state.ret;
455 }
457 static struct patch *get_patch(struct origin *parent, struct origin *origin)
458 {
459 mmfile_t file_p, file_o;
460 struct patch *patch;
462 fill_origin_blob(parent, &file_p);
463 fill_origin_blob(origin, &file_o);
464 if (!file_p.ptr || !file_o.ptr)
465 return NULL;
466 patch = compare_buffer(&file_p, &file_o, 0);
467 num_get_patch++;
468 return patch;
469 }
471 static void free_patch(struct patch *p)
472 {
473 free(p->chunks);
474 free(p);
475 }
477 static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
478 {
479 struct blame_entry *ent, *prev = NULL;
481 origin_incref(e->suspect);
483 for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
484 prev = ent;
486 /* prev, if not NULL, is the last one that is below e */
487 e->prev = prev;
488 if (prev) {
489 e->next = prev->next;
490 prev->next = e;
491 }
492 else {
493 e->next = sb->ent;
494 sb->ent = e;
495 }
496 if (e->next)
497 e->next->prev = e;
498 }
500 static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
501 {
502 struct blame_entry *p, *n;
504 p = dst->prev;
505 n = dst->next;
506 origin_incref(src->suspect);
507 origin_decref(dst->suspect);
508 memcpy(dst, src, sizeof(*src));
509 dst->prev = p;
510 dst->next = n;
511 dst->score = 0;
512 }
514 static const char *nth_line(struct scoreboard *sb, int lno)
515 {
516 return sb->final_buf + sb->lineno[lno];
517 }
519 static void split_overlap(struct blame_entry *split,
520 struct blame_entry *e,
521 int tlno, int plno, int same,
522 struct origin *parent)
523 {
524 /* it is known that lines between tlno to same came from
525 * parent, and e has an overlap with that range. it also is
526 * known that parent's line plno corresponds to e's line tlno.
527 *
528 * <---- e ----->
529 * <------>
530 * <------------>
531 * <------------>
532 * <------------------>
533 *
534 * Potentially we need to split e into three parts; before
535 * this chunk, the chunk to be blamed for parent, and after
536 * that portion.
537 */
538 int chunk_end_lno;
539 memset(split, 0, sizeof(struct blame_entry [3]));
541 if (e->s_lno < tlno) {
542 /* there is a pre-chunk part not blamed on parent */
543 split[0].suspect = origin_incref(e->suspect);
544 split[0].lno = e->lno;
545 split[0].s_lno = e->s_lno;
546 split[0].num_lines = tlno - e->s_lno;
547 split[1].lno = e->lno + tlno - e->s_lno;
548 split[1].s_lno = plno;
549 }
550 else {
551 split[1].lno = e->lno;
552 split[1].s_lno = plno + (e->s_lno - tlno);
553 }
555 if (same < e->s_lno + e->num_lines) {
556 /* there is a post-chunk part not blamed on parent */
557 split[2].suspect = origin_incref(e->suspect);
558 split[2].lno = e->lno + (same - e->s_lno);
559 split[2].s_lno = e->s_lno + (same - e->s_lno);
560 split[2].num_lines = e->s_lno + e->num_lines - same;
561 chunk_end_lno = split[2].lno;
562 }
563 else
564 chunk_end_lno = e->lno + e->num_lines;
565 split[1].num_lines = chunk_end_lno - split[1].lno;
567 if (split[1].num_lines < 1)
568 return;
569 split[1].suspect = origin_incref(parent);
570 }
572 static void split_blame(struct scoreboard *sb,
573 struct blame_entry *split,
574 struct blame_entry *e)
575 {
576 struct blame_entry *new_entry;
578 if (split[0].suspect && split[2].suspect) {
579 /* we need to split e into two and add another for parent */
580 dup_entry(e, &split[0]);
582 new_entry = xmalloc(sizeof(*new_entry));
583 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
584 add_blame_entry(sb, new_entry);
586 new_entry = xmalloc(sizeof(*new_entry));
587 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
588 add_blame_entry(sb, new_entry);
589 }
590 else if (!split[0].suspect && !split[2].suspect)
591 /* parent covers the entire area */
592 dup_entry(e, &split[1]);
593 else if (split[0].suspect) {
594 dup_entry(e, &split[0]);
596 new_entry = xmalloc(sizeof(*new_entry));
597 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
598 add_blame_entry(sb, new_entry);
599 }
600 else {
601 dup_entry(e, &split[1]);
603 new_entry = xmalloc(sizeof(*new_entry));
604 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
605 add_blame_entry(sb, new_entry);
606 }
608 if (DEBUG) { /* sanity */
609 struct blame_entry *ent;
610 int lno = sb->ent->lno, corrupt = 0;
612 for (ent = sb->ent; ent; ent = ent->next) {
613 if (lno != ent->lno)
614 corrupt = 1;
615 if (ent->s_lno < 0)
616 corrupt = 1;
617 lno += ent->num_lines;
618 }
619 if (corrupt) {
620 lno = sb->ent->lno;
621 for (ent = sb->ent; ent; ent = ent->next) {
622 printf("L %8d l %8d n %8d\n",
623 lno, ent->lno, ent->num_lines);
624 lno = ent->lno + ent->num_lines;
625 }
626 die("oops");
627 }
628 }
629 }
631 static void decref_split(struct blame_entry *split)
632 {
633 int i;
635 for (i = 0; i < 3; i++)
636 origin_decref(split[i].suspect);
637 }
639 static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
640 int tlno, int plno, int same,
641 struct origin *parent)
642 {
643 struct blame_entry split[3];
645 split_overlap(split, e, tlno, plno, same, parent);
646 if (split[1].suspect)
647 split_blame(sb, split, e);
648 decref_split(split);
649 }
651 static int find_last_in_target(struct scoreboard *sb, struct origin *target)
652 {
653 struct blame_entry *e;
654 int last_in_target = -1;
656 for (e = sb->ent; e; e = e->next) {
657 if (e->guilty || cmp_suspect(e->suspect, target))
658 continue;
659 if (last_in_target < e->s_lno + e->num_lines)
660 last_in_target = e->s_lno + e->num_lines;
661 }
662 return last_in_target;
663 }
665 static void blame_chunk(struct scoreboard *sb,
666 int tlno, int plno, int same,
667 struct origin *target, struct origin *parent)
668 {
669 struct blame_entry *e;
671 for (e = sb->ent; e; e = e->next) {
672 if (e->guilty || cmp_suspect(e->suspect, target))
673 continue;
674 if (same <= e->s_lno)
675 continue;
676 if (tlno < e->s_lno + e->num_lines)
677 blame_overlap(sb, e, tlno, plno, same, parent);
678 }
679 }
681 static int pass_blame_to_parent(struct scoreboard *sb,
682 struct origin *target,
683 struct origin *parent)
684 {
685 int i, last_in_target, plno, tlno;
686 struct patch *patch;
688 last_in_target = find_last_in_target(sb, target);
689 if (last_in_target < 0)
690 return 1; /* nothing remains for this target */
692 patch = get_patch(parent, target);
693 plno = tlno = 0;
694 for (i = 0; i < patch->num; i++) {
695 struct chunk *chunk = &patch->chunks[i];
697 blame_chunk(sb, tlno, plno, chunk->same, target, parent);
698 plno = chunk->p_next;
699 tlno = chunk->t_next;
700 }
701 /* rest (i.e. anything above tlno) are the same as parent */
702 blame_chunk(sb, tlno, plno, last_in_target, target, parent);
704 free_patch(patch);
705 return 0;
706 }
708 static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
709 {
710 unsigned score;
711 const char *cp, *ep;
713 if (e->score)
714 return e->score;
716 score = 1;
717 cp = nth_line(sb, e->lno);
718 ep = nth_line(sb, e->lno + e->num_lines);
719 while (cp < ep) {
720 unsigned ch = *((unsigned char *)cp);
721 if (isalnum(ch))
722 score++;
723 cp++;
724 }
725 e->score = score;
726 return score;
727 }
729 static void copy_split_if_better(struct scoreboard *sb,
730 struct blame_entry *best_so_far,
731 struct blame_entry *this)
732 {
733 int i;
735 if (!this[1].suspect)
736 return;
737 if (best_so_far[1].suspect) {
738 if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
739 return;
740 }
742 for (i = 0; i < 3; i++)
743 origin_incref(this[i].suspect);
744 decref_split(best_so_far);
745 memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
746 }
748 static void find_copy_in_blob(struct scoreboard *sb,
749 struct blame_entry *ent,
750 struct origin *parent,
751 struct blame_entry *split,
752 mmfile_t *file_p)
753 {
754 const char *cp;
755 int cnt;
756 mmfile_t file_o;
757 struct patch *patch;
758 int i, plno, tlno;
760 cp = nth_line(sb, ent->lno);
761 file_o.ptr = (char*) cp;
762 cnt = ent->num_lines;
764 while (cnt && cp < sb->final_buf + sb->final_buf_size) {
765 if (*cp++ == '\n')
766 cnt--;
767 }
768 file_o.size = cp - file_o.ptr;
770 patch = compare_buffer(file_p, &file_o, 1);
772 memset(split, 0, sizeof(struct blame_entry [3]));
773 plno = tlno = 0;
774 for (i = 0; i < patch->num; i++) {
775 struct chunk *chunk = &patch->chunks[i];
777 /* tlno to chunk->same are the same as ent */
778 if (ent->num_lines <= tlno)
779 break;
780 if (tlno < chunk->same) {
781 struct blame_entry this[3];
782 split_overlap(this, ent,
783 tlno + ent->s_lno, plno,
784 chunk->same + ent->s_lno,
785 parent);
786 copy_split_if_better(sb, split, this);
787 decref_split(this);
788 }
789 plno = chunk->p_next;
790 tlno = chunk->t_next;
791 }
792 free_patch(patch);
793 }
795 static int find_move_in_parent(struct scoreboard *sb,
796 struct origin *target,
797 struct origin *parent)
798 {
799 int last_in_target, made_progress;
800 struct blame_entry *e, split[3];
801 mmfile_t file_p;
803 last_in_target = find_last_in_target(sb, target);
804 if (last_in_target < 0)
805 return 1; /* nothing remains for this target */
807 fill_origin_blob(parent, &file_p);
808 if (!file_p.ptr)
809 return 0;
811 made_progress = 1;
812 while (made_progress) {
813 made_progress = 0;
814 for (e = sb->ent; e; e = e->next) {
815 if (e->guilty || cmp_suspect(e->suspect, target))
816 continue;
817 find_copy_in_blob(sb, e, parent, split, &file_p);
818 if (split[1].suspect &&
819 blame_move_score < ent_score(sb, &split[1])) {
820 split_blame(sb, split, e);
821 made_progress = 1;
822 }
823 decref_split(split);
824 }
825 }
826 return 0;
827 }
830 struct blame_list {
831 struct blame_entry *ent;
832 struct blame_entry split[3];
833 };
835 static struct blame_list *setup_blame_list(struct scoreboard *sb,
836 struct origin *target,
837 int *num_ents_p)
838 {
839 struct blame_entry *e;
840 int num_ents, i;
841 struct blame_list *blame_list = NULL;
843 /* Count the number of entries the target is suspected for,
844 * and prepare a list of entry and the best split.
845 */
846 for (e = sb->ent, num_ents = 0; e; e = e->next)
847 if (!e->guilty && !cmp_suspect(e->suspect, target))
848 num_ents++;
849 if (num_ents) {
850 blame_list = xcalloc(num_ents, sizeof(struct blame_list));
851 for (e = sb->ent, i = 0; e; e = e->next)
852 if (!e->guilty && !cmp_suspect(e->suspect, target))
853 blame_list[i++].ent = e;
854 }
855 *num_ents_p = num_ents;
856 return blame_list;
857 }
859 static int find_copy_in_parent(struct scoreboard *sb,
860 struct origin *target,
861 struct commit *parent,
862 struct origin *porigin,
863 int opt)
864 {
865 struct diff_options diff_opts;
866 const char *paths[1];
867 int i, j;
868 int retval;
869 struct blame_list *blame_list;
870 int num_ents;
872 blame_list = setup_blame_list(sb, target, &num_ents);
873 if (!blame_list)
874 return 1; /* nothing remains for this target */
876 diff_setup(&diff_opts);
877 diff_opts.recursive = 1;
878 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
880 paths[0] = NULL;
881 diff_tree_setup_paths(paths, &diff_opts);
882 if (diff_setup_done(&diff_opts) < 0)
883 die("diff-setup");
885 /* Try "find copies harder" on new path if requested;
886 * we do not want to use diffcore_rename() actually to
887 * match things up; find_copies_harder is set only to
888 * force diff_tree_sha1() to feed all filepairs to diff_queue,
889 * and this code needs to be after diff_setup_done(), which
890 * usually makes find-copies-harder imply copy detection.
891 */
892 if ((opt & PICKAXE_BLAME_COPY_HARDER) &&
893 (!porigin || strcmp(target->path, porigin->path)))
894 diff_opts.find_copies_harder = 1;
896 diff_tree_sha1(parent->tree->object.sha1,
897 target->commit->tree->object.sha1,
898 "", &diff_opts);
900 if (!diff_opts.find_copies_harder)
901 diffcore_std(&diff_opts);
903 retval = 0;
904 while (1) {
905 int made_progress = 0;
907 for (i = 0; i < diff_queued_diff.nr; i++) {
908 struct diff_filepair *p = diff_queued_diff.queue[i];
909 struct origin *norigin;
910 mmfile_t file_p;
911 struct blame_entry this[3];
913 if (!DIFF_FILE_VALID(p->one))
914 continue; /* does not exist in parent */
915 if (porigin && !strcmp(p->one->path, porigin->path))
916 /* find_move already dealt with this path */
917 continue;
919 norigin = get_origin(sb, parent, p->one->path);
920 hashcpy(norigin->blob_sha1, p->one->sha1);
921 fill_origin_blob(norigin, &file_p);
922 if (!file_p.ptr)
923 continue;
925 for (j = 0; j < num_ents; j++) {
926 find_copy_in_blob(sb, blame_list[j].ent,
927 norigin, this, &file_p);
928 copy_split_if_better(sb, blame_list[j].split,
929 this);
930 decref_split(this);
931 }
932 origin_decref(norigin);
933 }
935 for (j = 0; j < num_ents; j++) {
936 struct blame_entry *split = blame_list[j].split;
937 if (split[1].suspect &&
938 blame_copy_score < ent_score(sb, &split[1])) {
939 split_blame(sb, split, blame_list[j].ent);
940 made_progress = 1;
941 }
942 decref_split(split);
943 }
944 free(blame_list);
946 if (!made_progress)
947 break;
948 blame_list = setup_blame_list(sb, target, &num_ents);
949 if (!blame_list) {
950 retval = 1;
951 break;
952 }
953 }
954 diff_flush(&diff_opts);
956 return retval;
957 }
959 /* The blobs of origin and porigin exactly match, so everything
960 * origin is suspected for can be blamed on the parent.
961 */
962 static void pass_whole_blame(struct scoreboard *sb,
963 struct origin *origin, struct origin *porigin)
964 {
965 struct blame_entry *e;
967 if (!porigin->file.ptr && origin->file.ptr) {
968 /* Steal its file */
969 porigin->file = origin->file;
970 origin->file.ptr = NULL;
971 }
972 for (e = sb->ent; e; e = e->next) {
973 if (cmp_suspect(e->suspect, origin))
974 continue;
975 origin_incref(porigin);
976 origin_decref(e->suspect);
977 e->suspect = porigin;
978 }
979 }
981 #define MAXPARENT 16
983 static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
984 {
985 int i, pass;
986 struct commit *commit = origin->commit;
987 struct commit_list *parent;
988 struct origin *parent_origin[MAXPARENT], *porigin;
990 memset(parent_origin, 0, sizeof(parent_origin));
992 /* The first pass looks for unrenamed path to optimize for
993 * common cases, then we look for renames in the second pass.
994 */
995 for (pass = 0; pass < 2; pass++) {
996 struct origin *(*find)(struct scoreboard *,
997 struct commit *, struct origin *);
998 find = pass ? find_rename : find_origin;
1000 for (i = 0, parent = commit->parents;
1001 i < MAXPARENT && parent;
1002 parent = parent->next, i++) {
1003 struct commit *p = parent->item;
1004 int j, same;
1006 if (parent_origin[i])
1007 continue;
1008 if (parse_commit(p))
1009 continue;
1010 porigin = find(sb, p, origin);
1011 if (!porigin)
1012 continue;
1013 if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
1014 pass_whole_blame(sb, origin, porigin);
1015 origin_decref(porigin);
1016 goto finish;
1017 }
1018 for (j = same = 0; j < i; j++)
1019 if (parent_origin[j] &&
1020 !hashcmp(parent_origin[j]->blob_sha1,
1021 porigin->blob_sha1)) {
1022 same = 1;
1023 break;
1024 }
1025 if (!same)
1026 parent_origin[i] = porigin;
1027 else
1028 origin_decref(porigin);
1029 }
1030 }
1032 num_commits++;
1033 for (i = 0, parent = commit->parents;
1034 i < MAXPARENT && parent;
1035 parent = parent->next, i++) {
1036 struct origin *porigin = parent_origin[i];
1037 if (!porigin)
1038 continue;
1039 if (pass_blame_to_parent(sb, origin, porigin))
1040 goto finish;
1041 }
1043 /*
1044 * Optionally run "miff" to find moves in parents' files here.
1045 */
1046 if (opt & PICKAXE_BLAME_MOVE)
1047 for (i = 0, parent = commit->parents;
1048 i < MAXPARENT && parent;
1049 parent = parent->next, i++) {
1050 struct origin *porigin = parent_origin[i];
1051 if (!porigin)
1052 continue;
1053 if (find_move_in_parent(sb, origin, porigin))
1054 goto finish;
1055 }
1057 /*
1058 * Optionally run "ciff" to find copies from parents' files here.
1059 */
1060 if (opt & PICKAXE_BLAME_COPY)
1061 for (i = 0, parent = commit->parents;
1062 i < MAXPARENT && parent;
1063 parent = parent->next, i++) {
1064 struct origin *porigin = parent_origin[i];
1065 if (find_copy_in_parent(sb, origin, parent->item,
1066 porigin, opt))
1067 goto finish;
1068 }
1070 finish:
1071 for (i = 0; i < MAXPARENT; i++)
1072 origin_decref(parent_origin[i]);
1073 }
1075 struct commit_info
1076 {
1077 char *author;
1078 char *author_mail;
1079 unsigned long author_time;
1080 char *author_tz;
1082 /* filled only when asked for details */
1083 char *committer;
1084 char *committer_mail;
1085 unsigned long committer_time;
1086 char *committer_tz;
1088 char *summary;
1089 };
1091 static void get_ac_line(const char *inbuf, const char *what,
1092 int bufsz, char *person, char **mail,
1093 unsigned long *time, char **tz)
1094 {
1095 int len;
1096 char *tmp, *endp;
1098 tmp = strstr(inbuf, what);
1099 if (!tmp)
1100 goto error_out;
1101 tmp += strlen(what);
1102 endp = strchr(tmp, '\n');
1103 if (!endp)
1104 len = strlen(tmp);
1105 else
1106 len = endp - tmp;
1107 if (bufsz <= len) {
1108 error_out:
1109 /* Ugh */
1110 person = *mail = *tz = "(unknown)";
1111 *time = 0;
1112 return;
1113 }
1114 memcpy(person, tmp, len);
1116 tmp = person;
1117 tmp += len;
1118 *tmp = 0;
1119 while (*tmp != ' ')
1120 tmp--;
1121 *tz = tmp+1;
1123 *tmp = 0;
1124 while (*tmp != ' ')
1125 tmp--;
1126 *time = strtoul(tmp, NULL, 10);
1128 *tmp = 0;
1129 while (*tmp != ' ')
1130 tmp--;
1131 *mail = tmp + 1;
1132 *tmp = 0;
1133 }
1135 static void get_commit_info(struct commit *commit,
1136 struct commit_info *ret,
1137 int detailed)
1138 {
1139 int len;
1140 char *tmp, *endp;
1141 static char author_buf[1024];
1142 static char committer_buf[1024];
1143 static char summary_buf[1024];
1145 /* We've operated without save_commit_buffer, so
1146 * we now need to populate them for output.
1147 */
1148 if (!commit->buffer) {
1149 char type[20];
1150 unsigned long size;
1151 commit->buffer =
1152 read_sha1_file(commit->object.sha1, type, &size);
1153 }
1154 ret->author = author_buf;
1155 get_ac_line(commit->buffer, "\nauthor ",
1156 sizeof(author_buf), author_buf, &ret->author_mail,
1157 &ret->author_time, &ret->author_tz);
1159 if (!detailed)
1160 return;
1162 ret->committer = committer_buf;
1163 get_ac_line(commit->buffer, "\ncommitter ",
1164 sizeof(committer_buf), committer_buf, &ret->committer_mail,
1165 &ret->committer_time, &ret->committer_tz);
1167 ret->summary = summary_buf;
1168 tmp = strstr(commit->buffer, "\n\n");
1169 if (!tmp) {
1170 error_out:
1171 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
1172 return;
1173 }
1174 tmp += 2;
1175 endp = strchr(tmp, '\n');
1176 if (!endp)
1177 goto error_out;
1178 len = endp - tmp;
1179 if (len >= sizeof(summary_buf))
1180 goto error_out;
1181 memcpy(summary_buf, tmp, len);
1182 summary_buf[len] = 0;
1183 }
1185 static void found_guilty_entry(struct blame_entry *ent)
1186 {
1187 if (ent->guilty)
1188 return;
1189 ent->guilty = 1;
1190 if (incremental) {
1191 struct origin *suspect = ent->suspect;
1193 printf("%s %d %d %d\n",
1194 sha1_to_hex(suspect->commit->object.sha1),
1195 ent->s_lno + 1, ent->lno + 1, ent->num_lines);
1196 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1197 struct commit_info ci;
1198 suspect->commit->object.flags |= METAINFO_SHOWN;
1199 get_commit_info(suspect->commit, &ci, 1);
1200 printf("author %s\n", ci.author);
1201 printf("author-mail %s\n", ci.author_mail);
1202 printf("author-time %lu\n", ci.author_time);
1203 printf("author-tz %s\n", ci.author_tz);
1204 printf("committer %s\n", ci.committer);
1205 printf("committer-mail %s\n", ci.committer_mail);
1206 printf("committer-time %lu\n", ci.committer_time);
1207 printf("committer-tz %s\n", ci.committer_tz);
1208 printf("summary %s\n", ci.summary);
1209 if (suspect->commit->object.flags & UNINTERESTING)
1210 printf("boundary\n");
1211 }
1212 printf("filename ");
1213 write_name_quoted(NULL, 0, suspect->path, 1, stdout);
1214 putchar('\n');
1215 }
1216 }
1218 static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)
1219 {
1220 while (1) {
1221 struct blame_entry *ent;
1222 struct commit *commit;
1223 struct origin *suspect = NULL;
1225 /* find one suspect to break down */
1226 for (ent = sb->ent; !suspect && ent; ent = ent->next)
1227 if (!ent->guilty)
1228 suspect = ent->suspect;
1229 if (!suspect)
1230 return; /* all done */
1232 origin_incref(suspect);
1233 commit = suspect->commit;
1234 if (!commit->object.parsed)
1235 parse_commit(commit);
1236 if (!(commit->object.flags & UNINTERESTING) &&
1237 !(revs->max_age != -1 && commit->date < revs->max_age))
1238 pass_blame(sb, suspect, opt);
1239 else {
1240 commit->object.flags |= UNINTERESTING;
1241 if (commit->object.parsed)
1242 mark_parents_uninteresting(commit);
1243 }
1244 /* treat root commit as boundary */
1245 if (!commit->parents && !show_root)
1246 commit->object.flags |= UNINTERESTING;
1248 /* Take responsibility for the remaining entries */
1249 for (ent = sb->ent; ent; ent = ent->next)
1250 if (!cmp_suspect(ent->suspect, suspect))
1251 found_guilty_entry(ent);
1252 origin_decref(suspect);
1254 if (DEBUG) /* sanity */
1255 sanity_check_refcnt(sb);
1256 }
1257 }
1259 static const char *format_time(unsigned long time, const char *tz_str,
1260 int show_raw_time)
1261 {
1262 static char time_buf[128];
1263 time_t t = time;
1264 int minutes, tz;
1265 struct tm *tm;
1267 if (show_raw_time) {
1268 sprintf(time_buf, "%lu %s", time, tz_str);
1269 return time_buf;
1270 }
1272 tz = atoi(tz_str);
1273 minutes = tz < 0 ? -tz : tz;
1274 minutes = (minutes / 100)*60 + (minutes % 100);
1275 minutes = tz < 0 ? -minutes : minutes;
1276 t = time + minutes * 60;
1277 tm = gmtime(&t);
1279 strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
1280 strcat(time_buf, tz_str);
1281 return time_buf;
1282 }
1284 #define OUTPUT_ANNOTATE_COMPAT 001
1285 #define OUTPUT_LONG_OBJECT_NAME 002
1286 #define OUTPUT_RAW_TIMESTAMP 004
1287 #define OUTPUT_PORCELAIN 010
1288 #define OUTPUT_SHOW_NAME 020
1289 #define OUTPUT_SHOW_NUMBER 040
1290 #define OUTPUT_SHOW_SCORE 0100
1292 static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
1293 {
1294 int cnt;
1295 const char *cp;
1296 struct origin *suspect = ent->suspect;
1297 char hex[41];
1299 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1300 printf("%s%c%d %d %d\n",
1301 hex,
1302 ent->guilty ? ' ' : '*', // purely for debugging
1303 ent->s_lno + 1,
1304 ent->lno + 1,
1305 ent->num_lines);
1306 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1307 struct commit_info ci;
1308 suspect->commit->object.flags |= METAINFO_SHOWN;
1309 get_commit_info(suspect->commit, &ci, 1);
1310 printf("author %s\n", ci.author);
1311 printf("author-mail %s\n", ci.author_mail);
1312 printf("author-time %lu\n", ci.author_time);
1313 printf("author-tz %s\n", ci.author_tz);
1314 printf("committer %s\n", ci.committer);
1315 printf("committer-mail %s\n", ci.committer_mail);
1316 printf("committer-time %lu\n", ci.committer_time);
1317 printf("committer-tz %s\n", ci.committer_tz);
1318 printf("filename %s\n", suspect->path);
1319 printf("summary %s\n", ci.summary);
1320 if (suspect->commit->object.flags & UNINTERESTING)
1321 printf("boundary\n");
1322 }
1323 else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
1324 printf("filename %s\n", suspect->path);
1326 cp = nth_line(sb, ent->lno);
1327 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1328 char ch;
1329 if (cnt)
1330 printf("%s %d %d\n", hex,
1331 ent->s_lno + 1 + cnt,
1332 ent->lno + 1 + cnt);
1333 putchar('\t');
1334 do {
1335 ch = *cp++;
1336 putchar(ch);
1337 } while (ch != '\n' &&
1338 cp < sb->final_buf + sb->final_buf_size);
1339 }
1340 }
1342 static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1343 {
1344 int cnt;
1345 const char *cp;
1346 struct origin *suspect = ent->suspect;
1347 struct commit_info ci;
1348 char hex[41];
1349 int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1351 get_commit_info(suspect->commit, &ci, 1);
1352 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1354 cp = nth_line(sb, ent->lno);
1355 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1356 char ch;
1357 int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8;
1359 if (suspect->commit->object.flags & UNINTERESTING) {
1360 if (!blank_boundary) {
1361 length--;
1362 putchar('^');
1363 }
1364 else
1365 memset(hex, ' ', length);
1366 }
1368 printf("%.*s", length, hex);
1369 if (opt & OUTPUT_ANNOTATE_COMPAT)
1370 printf("\t(%10s\t%10s\t%d)", ci.author,
1371 format_time(ci.author_time, ci.author_tz,
1372 show_raw_time),
1373 ent->lno + 1 + cnt);
1374 else {
1375 if (opt & OUTPUT_SHOW_SCORE)
1376 printf(" %*d %02d",
1377 max_score_digits, ent->score,
1378 ent->suspect->refcnt);
1379 if (opt & OUTPUT_SHOW_NAME)
1380 printf(" %-*.*s", longest_file, longest_file,
1381 suspect->path);
1382 if (opt & OUTPUT_SHOW_NUMBER)
1383 printf(" %*d", max_orig_digits,
1384 ent->s_lno + 1 + cnt);
1385 printf(" (%-*.*s %10s %*d) ",
1386 longest_author, longest_author, ci.author,
1387 format_time(ci.author_time, ci.author_tz,
1388 show_raw_time),
1389 max_digits, ent->lno + 1 + cnt);
1390 }
1391 do {
1392 ch = *cp++;
1393 putchar(ch);
1394 } while (ch != '\n' &&
1395 cp < sb->final_buf + sb->final_buf_size);
1396 }
1397 }
1399 static void output(struct scoreboard *sb, int option)
1400 {
1401 struct blame_entry *ent;
1403 if (option & OUTPUT_PORCELAIN) {
1404 for (ent = sb->ent; ent; ent = ent->next) {
1405 struct blame_entry *oth;
1406 struct origin *suspect = ent->suspect;
1407 struct commit *commit = suspect->commit;
1408 if (commit->object.flags & MORE_THAN_ONE_PATH)
1409 continue;
1410 for (oth = ent->next; oth; oth = oth->next) {
1411 if ((oth->suspect->commit != commit) ||
1412 !strcmp(oth->suspect->path, suspect->path))
1413 continue;
1414 commit->object.flags |= MORE_THAN_ONE_PATH;
1415 break;
1416 }
1417 }
1418 }
1420 for (ent = sb->ent; ent; ent = ent->next) {
1421 if (option & OUTPUT_PORCELAIN)
1422 emit_porcelain(sb, ent);
1423 else {
1424 emit_other(sb, ent, option);
1425 }
1426 }
1427 }
1429 static int prepare_lines(struct scoreboard *sb)
1430 {
1431 const char *buf = sb->final_buf;
1432 unsigned long len = sb->final_buf_size;
1433 int num = 0, incomplete = 0, bol = 1;
1435 if (len && buf[len-1] != '\n')
1436 incomplete++; /* incomplete line at the end */
1437 while (len--) {
1438 if (bol) {
1439 sb->lineno = xrealloc(sb->lineno,
1440 sizeof(int* ) * (num + 1));
1441 sb->lineno[num] = buf - sb->final_buf;
1442 bol = 0;
1443 }
1444 if (*buf++ == '\n') {
1445 num++;
1446 bol = 1;
1447 }
1448 }
1449 sb->lineno = xrealloc(sb->lineno,
1450 sizeof(int* ) * (num + incomplete + 1));
1451 sb->lineno[num + incomplete] = buf - sb->final_buf;
1452 sb->num_lines = num + incomplete;
1453 return sb->num_lines;
1454 }
1456 static int read_ancestry(const char *graft_file)
1457 {
1458 FILE *fp = fopen(graft_file, "r");
1459 char buf[1024];
1460 if (!fp)
1461 return -1;
1462 while (fgets(buf, sizeof(buf), fp)) {
1463 /* The format is just "Commit Parent1 Parent2 ...\n" */
1464 int len = strlen(buf);
1465 struct commit_graft *graft = read_graft_line(buf, len);
1466 if (graft)
1467 register_commit_graft(graft, 0);
1468 }
1469 fclose(fp);
1470 return 0;
1471 }
1473 static int lineno_width(int lines)
1474 {
1475 int i, width;
1477 for (width = 1, i = 10; i <= lines + 1; width++)
1478 i *= 10;
1479 return width;
1480 }
1482 static void find_alignment(struct scoreboard *sb, int *option)
1483 {
1484 int longest_src_lines = 0;
1485 int longest_dst_lines = 0;
1486 unsigned largest_score = 0;
1487 struct blame_entry *e;
1489 for (e = sb->ent; e; e = e->next) {
1490 struct origin *suspect = e->suspect;
1491 struct commit_info ci;
1492 int num;
1494 if (strcmp(suspect->path, sb->path))
1495 *option |= OUTPUT_SHOW_NAME;
1496 num = strlen(suspect->path);
1497 if (longest_file < num)
1498 longest_file = num;
1499 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1500 suspect->commit->object.flags |= METAINFO_SHOWN;
1501 get_commit_info(suspect->commit, &ci, 1);
1502 num = strlen(ci.author);
1503 if (longest_author < num)
1504 longest_author = num;
1505 }
1506 num = e->s_lno + e->num_lines;
1507 if (longest_src_lines < num)
1508 longest_src_lines = num;
1509 num = e->lno + e->num_lines;
1510 if (longest_dst_lines < num)
1511 longest_dst_lines = num;
1512 if (largest_score < ent_score(sb, e))
1513 largest_score = ent_score(sb, e);
1514 }
1515 max_orig_digits = lineno_width(longest_src_lines);
1516 max_digits = lineno_width(longest_dst_lines);
1517 max_score_digits = lineno_width(largest_score);
1518 }
1520 static void sanity_check_refcnt(struct scoreboard *sb)
1521 {
1522 int baa = 0;
1523 struct blame_entry *ent;
1525 for (ent = sb->ent; ent; ent = ent->next) {
1526 /* Nobody should have zero or negative refcnt */
1527 if (ent->suspect->refcnt <= 0) {
1528 fprintf(stderr, "%s in %s has negative refcnt %d\n",
1529 ent->suspect->path,
1530 sha1_to_hex(ent->suspect->commit->object.sha1),
1531 ent->suspect->refcnt);
1532 baa = 1;
1533 }
1534 }
1535 for (ent = sb->ent; ent; ent = ent->next) {
1536 /* Mark the ones that haven't been checked */
1537 if (0 < ent->suspect->refcnt)
1538 ent->suspect->refcnt = -ent->suspect->refcnt;
1539 }
1540 for (ent = sb->ent; ent; ent = ent->next) {
1541 /* then pick each and see if they have the the correct
1542 * refcnt.
1543 */
1544 int found;
1545 struct blame_entry *e;
1546 struct origin *suspect = ent->suspect;
1548 if (0 < suspect->refcnt)
1549 continue;
1550 suspect->refcnt = -suspect->refcnt; /* Unmark */
1551 for (found = 0, e = sb->ent; e; e = e->next) {
1552 if (e->suspect != suspect)
1553 continue;
1554 found++;
1555 }
1556 if (suspect->refcnt != found) {
1557 fprintf(stderr, "%s in %s has refcnt %d, not %d\n",
1558 ent->suspect->path,
1559 sha1_to_hex(ent->suspect->commit->object.sha1),
1560 ent->suspect->refcnt, found);
1561 baa = 2;
1562 }
1563 }
1564 if (baa) {
1565 int opt = 0160;
1566 find_alignment(sb, &opt);
1567 output(sb, opt);
1568 die("Baa %d!", baa);
1569 }
1570 }
1572 static int has_path_in_work_tree(const char *path)
1573 {
1574 struct stat st;
1575 return !lstat(path, &st);
1576 }
1578 static unsigned parse_score(const char *arg)
1579 {
1580 char *end;
1581 unsigned long score = strtoul(arg, &end, 10);
1582 if (*end)
1583 return 0;
1584 return score;
1585 }
1587 static const char *add_prefix(const char *prefix, const char *path)
1588 {
1589 if (!prefix || !prefix[0])
1590 return path;
1591 return prefix_path(prefix, strlen(prefix), path);
1592 }
1594 static const char *parse_loc(const char *spec,
1595 struct scoreboard *sb, long lno,
1596 long begin, long *ret)
1597 {
1598 char *term;
1599 const char *line;
1600 long num;
1601 int reg_error;
1602 regex_t regexp;
1603 regmatch_t match[1];
1605 /* Allow "-L <something>,+20" to mean starting at <something>
1606 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
1607 * <something>.
1608 */
1609 if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
1610 num = strtol(spec + 1, &term, 10);
1611 if (term != spec + 1) {
1612 if (spec[0] == '-')
1613 num = 0 - num;
1614 if (0 < num)
1615 *ret = begin + num - 2;
1616 else if (!num)
1617 *ret = begin;
1618 else
1619 *ret = begin + num;
1620 return term;
1621 }
1622 return spec;
1623 }
1624 num = strtol(spec, &term, 10);
1625 if (term != spec) {
1626 *ret = num;
1627 return term;
1628 }
1629 if (spec[0] != '/')
1630 return spec;
1632 /* it could be a regexp of form /.../ */
1633 for (term = (char*) spec + 1; *term && *term != '/'; term++) {
1634 if (*term == '\\')
1635 term++;
1636 }
1637 if (*term != '/')
1638 return spec;
1640 /* try [spec+1 .. term-1] as regexp */
1641 *term = 0;
1642 begin--; /* input is in human terms */
1643 line = nth_line(sb, begin);
1645 if (!(reg_error = regcomp(®exp, spec + 1, REG_NEWLINE)) &&
1646 !(reg_error = regexec(®exp, line, 1, match, 0))) {
1647 const char *cp = line + match[0].rm_so;
1648 const char *nline;
1650 while (begin++ < lno) {
1651 nline = nth_line(sb, begin);
1652 if (line <= cp && cp < nline)
1653 break;
1654 line = nline;
1655 }
1656 *ret = begin;
1657 regfree(®exp);
1658 *term++ = '/';
1659 return term;
1660 }
1661 else {
1662 char errbuf[1024];
1663 regerror(reg_error, ®exp, errbuf, 1024);
1664 die("-L parameter '%s': %s", spec + 1, errbuf);
1665 }
1666 }
1668 static void prepare_blame_range(struct scoreboard *sb,
1669 const char *bottomtop,
1670 long lno,
1671 long *bottom, long *top)
1672 {
1673 const char *term;
1675 term = parse_loc(bottomtop, sb, lno, 1, bottom);
1676 if (*term == ',') {
1677 term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
1678 if (*term)
1679 usage(blame_usage);
1680 }
1681 if (*term)
1682 usage(blame_usage);
1683 }
1685 static int git_blame_config(const char *var, const char *value)
1686 {
1687 if (!strcmp(var, "blame.showroot")) {
1688 show_root = git_config_bool(var, value);
1689 return 0;
1690 }
1691 if (!strcmp(var, "blame.blankboundary")) {
1692 blank_boundary = git_config_bool(var, value);
1693 return 0;
1694 }
1695 return git_default_config(var, value);
1696 }
1698 int cmd_blame(int argc, const char **argv, const char *prefix)
1699 {
1700 struct rev_info revs;
1701 const char *path;
1702 struct scoreboard sb;
1703 struct origin *o;
1704 struct blame_entry *ent;
1705 int i, seen_dashdash, unk, opt;
1706 long bottom, top, lno;
1707 int output_option = 0;
1708 const char *revs_file = NULL;
1709 const char *final_commit_name = NULL;
1710 char type[10];
1711 const char *bottomtop = NULL;
1713 git_config(git_blame_config);
1714 save_commit_buffer = 0;
1716 opt = 0;
1717 seen_dashdash = 0;
1718 for (unk = i = 1; i < argc; i++) {
1719 const char *arg = argv[i];
1720 if (*arg != '-')
1721 break;
1722 else if (!strcmp("-b", arg))
1723 blank_boundary = 1;
1724 else if (!strcmp("--root", arg))
1725 show_root = 1;
1726 else if (!strcmp("-c", arg))
1727 output_option |= OUTPUT_ANNOTATE_COMPAT;
1728 else if (!strcmp("-t", arg))
1729 output_option |= OUTPUT_RAW_TIMESTAMP;
1730 else if (!strcmp("-l", arg))
1731 output_option |= OUTPUT_LONG_OBJECT_NAME;
1732 else if (!strcmp("-S", arg) && ++i < argc)
1733 revs_file = argv[i];
1734 else if (!strncmp("-M", arg, 2)) {
1735 opt |= PICKAXE_BLAME_MOVE;
1736 blame_move_score = parse_score(arg+2);
1737 }
1738 else if (!strncmp("-C", arg, 2)) {
1739 if (opt & PICKAXE_BLAME_COPY)
1740 opt |= PICKAXE_BLAME_COPY_HARDER;
1741 opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
1742 blame_copy_score = parse_score(arg+2);
1743 }
1744 else if (!strncmp("-L", arg, 2)) {
1745 if (!arg[2]) {
1746 if (++i >= argc)
1747 usage(blame_usage);
1748 arg = argv[i];
1749 }
1750 else
1751 arg += 2;
1752 if (bottomtop)
1753 die("More than one '-L n,m' option given");
1754 bottomtop = arg;
1755 }
1756 else if (!strcmp("--incremental", arg))
1757 incremental = 1;
1758 else if (!strcmp("--score-debug", arg))
1759 output_option |= OUTPUT_SHOW_SCORE;
1760 else if (!strcmp("-f", arg) ||
1761 !strcmp("--show-name", arg))
1762 output_option |= OUTPUT_SHOW_NAME;
1763 else if (!strcmp("-n", arg) ||
1764 !strcmp("--show-number", arg))
1765 output_option |= OUTPUT_SHOW_NUMBER;
1766 else if (!strcmp("-p", arg) ||
1767 !strcmp("--porcelain", arg))
1768 output_option |= OUTPUT_PORCELAIN;
1769 else if (!strcmp("--", arg)) {
1770 seen_dashdash = 1;
1771 i++;
1772 break;
1773 }
1774 else
1775 argv[unk++] = arg;
1776 }
1778 if (!blame_move_score)
1779 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
1780 if (!blame_copy_score)
1781 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
1783 /* We have collected options unknown to us in argv[1..unk]
1784 * which are to be passed to revision machinery if we are
1785 * going to do the "bottom" procesing.
1786 *
1787 * The remaining are:
1788 *
1789 * (1) if seen_dashdash, its either
1790 * "-options -- <path>" or
1791 * "-options -- <path> <rev>".
1792 * but the latter is allowed only if there is no
1793 * options that we passed to revision machinery.
1794 *
1795 * (2) otherwise, we may have "--" somewhere later and
1796 * might be looking at the first one of multiple 'rev'
1797 * parameters (e.g. " master ^next ^maint -- path").
1798 * See if there is a dashdash first, and give the
1799 * arguments before that to revision machinery.
1800 * After that there must be one 'path'.
1801 *
1802 * (3) otherwise, its one of the three:
1803 * "-options <path> <rev>"
1804 * "-options <rev> <path>"
1805 * "-options <path>"
1806 * but again the first one is allowed only if
1807 * there is no options that we passed to revision
1808 * machinery.
1809 */
1811 if (seen_dashdash) {
1812 /* (1) */
1813 if (argc <= i)
1814 usage(blame_usage);
1815 path = add_prefix(prefix, argv[i]);
1816 if (i + 1 == argc - 1) {
1817 if (unk != 1)
1818 usage(blame_usage);
1819 argv[unk++] = argv[i + 1];
1820 }
1821 else if (i + 1 != argc)
1822 /* garbage at end */
1823 usage(blame_usage);
1824 }
1825 else {
1826 int j;
1827 for (j = i; !seen_dashdash && j < argc; j++)
1828 if (!strcmp(argv[j], "--"))
1829 seen_dashdash = j;
1830 if (seen_dashdash) {
1831 if (seen_dashdash + 1 != argc - 1)
1832 usage(blame_usage);
1833 path = add_prefix(prefix, argv[seen_dashdash + 1]);
1834 for (j = i; j < seen_dashdash; j++)
1835 argv[unk++] = argv[j];
1836 }
1837 else {
1838 /* (3) */
1839 path = add_prefix(prefix, argv[i]);
1840 if (i + 1 == argc - 1) {
1841 final_commit_name = argv[i + 1];
1843 /* if (unk == 1) we could be getting
1844 * old-style
1845 */
1846 if (unk == 1 && !has_path_in_work_tree(path)) {
1847 path = add_prefix(prefix, argv[i + 1]);
1848 final_commit_name = argv[i];
1849 }
1850 }
1851 else if (i != argc - 1)
1852 usage(blame_usage); /* garbage at end */
1854 if (!has_path_in_work_tree(path))
1855 die("cannot stat path %s: %s",
1856 path, strerror(errno));
1857 }
1858 }
1860 if (final_commit_name)
1861 argv[unk++] = final_commit_name;
1863 /* Now we got rev and path. We do not want the path pruning
1864 * but we may want "bottom" processing.
1865 */
1866 argv[unk++] = "--"; /* terminate the rev name */
1867 argv[unk] = NULL;
1869 init_revisions(&revs, NULL);
1870 setup_revisions(unk, argv, &revs, "HEAD");
1871 memset(&sb, 0, sizeof(sb));
1873 /* There must be one and only one positive commit in the
1874 * revs->pending array.
1875 */
1876 for (i = 0; i < revs.pending.nr; i++) {
1877 struct object *obj = revs.pending.objects[i].item;
1878 if (obj->flags & UNINTERESTING)
1879 continue;
1880 while (obj->type == OBJ_TAG)
1881 obj = deref_tag(obj, NULL, 0);
1882 if (obj->type != OBJ_COMMIT)
1883 die("Non commit %s?",
1884 revs.pending.objects[i].name);
1885 if (sb.final)
1886 die("More than one commit to dig from %s and %s?",
1887 revs.pending.objects[i].name,
1888 final_commit_name);
1889 sb.final = (struct commit *) obj;
1890 final_commit_name = revs.pending.objects[i].name;
1891 }
1893 if (!sb.final) {
1894 /* "--not A B -- path" without anything positive */
1895 unsigned char head_sha1[20];
1897 final_commit_name = "HEAD";
1898 if (get_sha1(final_commit_name, head_sha1))
1899 die("No such ref: HEAD");
1900 sb.final = lookup_commit_reference(head_sha1);
1901 add_pending_object(&revs, &(sb.final->object), "HEAD");
1902 }
1904 /* If we have bottom, this will mark the ancestors of the
1905 * bottom commits we would reach while traversing as
1906 * uninteresting.
1907 */
1908 prepare_revision_walk(&revs);
1910 o = get_origin(&sb, sb.final, path);
1911 if (fill_blob_sha1(o))
1912 die("no such path %s in %s", path, final_commit_name);
1914 sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
1915 num_read_blob++;
1916 lno = prepare_lines(&sb);
1918 bottom = top = 0;
1919 if (bottomtop)
1920 prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);
1921 if (bottom && top && top < bottom) {
1922 long tmp;
1923 tmp = top; top = bottom; bottom = tmp;
1924 }
1925 if (bottom < 1)
1926 bottom = 1;
1927 if (top < 1)
1928 top = lno;
1929 bottom--;
1930 if (lno < top)
1931 die("file %s has only %lu lines", path, lno);
1933 ent = xcalloc(1, sizeof(*ent));
1934 ent->lno = bottom;
1935 ent->num_lines = top - bottom;
1936 ent->suspect = o;
1937 ent->s_lno = bottom;
1939 sb.ent = ent;
1940 sb.path = path;
1942 if (revs_file && read_ancestry(revs_file))
1943 die("reading graft file %s failed: %s",
1944 revs_file, strerror(errno));
1946 assign_blame(&sb, &revs, opt);
1948 if (incremental)
1949 return 0;
1951 coalesce(&sb);
1953 if (!(output_option & OUTPUT_PORCELAIN))
1954 find_alignment(&sb, &output_option);
1956 output(&sb, output_option);
1957 free((void *)sb.final_buf);
1958 for (ent = sb.ent; ent; ) {
1959 struct blame_entry *e = ent->next;
1960 free(ent);
1961 ent = e;
1962 }
1964 if (DEBUG) {
1965 printf("num read blob: %d\n", num_read_blob);
1966 printf("num get patch: %d\n", num_get_patch);
1967 printf("num commits: %d\n", num_commits);
1968 }
1969 return 0;
1970 }