Make fsck and fsck-objects be builtins.
[git/git.git] / builtin-blame.c
CommitLineData
cee7f245
JH
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"
717d1462 16#include "quote.h"
cee7f245
JH
17#include "xdiff-interface.h"
18
acca687f
JH
19static char blame_usage[] =
20"git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n"
cee7f245 21" -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
4c10a5ca 22" -b Show blank SHA-1 for boundary commits (Default: off)\n"
cee7f245 23" -l, --long Show long commit SHA1 (Default: off)\n"
4c10a5ca 24" --root Do not treat root commits as boundaries (Default: off)\n"
cee7f245
JH
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"
18abd745 30" -M, -C Find line movements within and across files\n"
717d1462 31" --incremental Show blame entries as we find them, incrementally\n"
cee7f245
JH
32" -S revs-file Use revisions from revs-file instead of calling git-rev-list\n";
33
34static int longest_file;
35static int longest_author;
36static int max_orig_digits;
37static int max_digits;
5ff62c30 38static int max_score_digits;
4c10a5ca
JH
39static int show_root;
40static int blank_boundary;
717d1462 41static int incremental;
cee7f245 42
54a4c617
JH
43#ifndef DEBUG
44#define DEBUG 0
45#endif
46
c2e525d9
JH
47/* stats */
48static int num_read_blob;
49static int num_get_patch;
50static int num_commits;
51
d24bba80 52#define PICKAXE_BLAME_MOVE 01
18abd745
JH
53#define PICKAXE_BLAME_COPY 02
54#define PICKAXE_BLAME_COPY_HARDER 04
d24bba80 55
4a0fc95f
JH
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 */
60static unsigned blame_move_score;
61static unsigned blame_copy_score;
62#define BLAME_DEFAULT_MOVE_SCORE 20
63#define BLAME_DEFAULT_COPY_SCORE 40
64
cee7f245
JH
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)
68
69/*
54a4c617 70 * One blob in a commit that is being suspected
cee7f245
JH
71 */
72struct origin {
54a4c617 73 int refcnt;
cee7f245 74 struct commit *commit;
c2e525d9 75 mmfile_t file;
cee7f245
JH
76 unsigned char blob_sha1[20];
77 char path[FLEX_ARRAY];
78};
79
c2e525d9
JH
80static 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}
93
54a4c617
JH
94static inline struct origin *origin_incref(struct origin *o)
95{
96 if (o)
97 o->refcnt++;
98 return o;
99}
100
101static void origin_decref(struct origin *o)
102{
103 if (o && --o->refcnt <= 0) {
c2e525d9
JH
104 if (o->file.ptr)
105 free(o->file.ptr);
54a4c617
JH
106 memset(o, 0, sizeof(*o));
107 free(o);
108 }
109}
110
cee7f245
JH
111struct blame_entry {
112 struct blame_entry *prev;
113 struct blame_entry *next;
114
115 /* the first line of this group in the final image;
116 * internally all line numbers are 0 based.
117 */
118 int lno;
119
120 /* how many lines this group has */
121 int num_lines;
122
123 /* the commit that introduced this group into the final image */
124 struct origin *suspect;
125
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;
130
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;
5ff62c30
JH
135
136 /* how significant this entry is -- cached to avoid
137 * scanning the lines over and over
138 */
139 unsigned score;
cee7f245
JH
140};
141
142struct scoreboard {
143 /* the final commit (i.e. where we started digging from) */
144 struct commit *final;
145
146 const char *path;
147
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;
153
154 /* linked list of blames */
155 struct blame_entry *ent;
156
612702e8 157 /* look-up a line in the final buffer */
cee7f245
JH
158 int num_lines;
159 int *lineno;
160};
161
46014766
JH
162static 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}
169
0d981c67
JH
170#define cmp_suspect(a, b) ( ((a)==(b)) ? 0 : cmp_suspect(a,b) )
171
54a4c617
JH
172static void sanity_check_refcnt(struct scoreboard *);
173
cee7f245
JH
174static void coalesce(struct scoreboard *sb)
175{
176 struct blame_entry *ent, *next;
177
178 for (ent = sb->ent; ent && (next = ent->next); ent = next) {
46014766 179 if (!cmp_suspect(ent->suspect, next->suspect) &&
cee7f245
JH
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;
54a4c617 186 origin_decref(next->suspect);
cee7f245 187 free(next);
46014766 188 ent->score = 0;
cee7f245
JH
189 next = ent; /* again */
190 }
191 }
54a4c617
JH
192
193 if (DEBUG) /* sanity */
194 sanity_check_refcnt(sb);
cee7f245
JH
195}
196
854b97f6
JH
197static 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}
206
f6c0e191
JH
207static struct origin *get_origin(struct scoreboard *sb,
208 struct commit *commit,
209 const char *path)
cee7f245 210{
f6c0e191 211 struct blame_entry *e;
cee7f245 212
f6c0e191
JH
213 for (e = sb->ent; e; e = e->next) {
214 if (e->suspect->commit == commit &&
215 !strcmp(e->suspect->path, path))
54a4c617 216 return origin_incref(e->suspect);
cee7f245 217 }
854b97f6 218 return make_origin(commit, path);
cee7f245
JH
219}
220
f6c0e191
JH
221static int fill_blob_sha1(struct origin *origin)
222{
223 unsigned mode;
224 char type[10];
225
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}
240
241static struct origin *find_origin(struct scoreboard *sb,
cee7f245
JH
242 struct commit *parent,
243 struct origin *origin)
244{
245 struct origin *porigin = NULL;
246 struct diff_options diff_opts;
f6c0e191
JH
247 const char *paths[2];
248
0d981c67 249 if (parent->util) {
854b97f6
JH
250 /* This is a freestanding copy of origin and not
251 * refcounted.
252 */
0d981c67 253 struct origin *cached = parent->util;
854b97f6
JH
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;
0d981c67
JH
263 }
264
f6c0e191
JH
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;
275
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);
283
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)
acca687f 293 die("internal error in blame::find_origin");
f6c0e191
JH
294 else {
295 struct diff_filepair *p = diff_queued_diff.queue[0];
296 switch (p->status) {
297 default:
acca687f 298 die("internal error in blame::find_origin (%c)",
f6c0e191
JH
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);
0d981c67 311 if (porigin) {
854b97f6
JH
312 struct origin *cached;
313 cached = make_origin(porigin->commit, porigin->path);
314 hashcpy(cached->blob_sha1, porigin->blob_sha1);
315 parent->util = cached;
0d981c67 316 }
f69e743d
JH
317 return porigin;
318}
f6c0e191 319
f69e743d
JH
320static 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];
cee7f245
JH
328
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;
2f3f8b21 333 diff_opts.single_follow = origin->path;
cee7f245
JH
334 paths[0] = NULL;
335 diff_tree_setup_paths(paths, &diff_opts);
336 if (diff_setup_done(&diff_opts) < 0)
337 die("diff-setup");
f6c0e191
JH
338 diff_tree_sha1(parent->tree->object.sha1,
339 origin->commit->tree->object.sha1,
cee7f245
JH
340 "", &diff_opts);
341 diffcore_std(&diff_opts);
342
343 for (i = 0; i < diff_queued_diff.nr; i++) {
344 struct diff_filepair *p = diff_queued_diff.queue[i];
612702e8 345 if ((p->status == 'R' || p->status == 'C') &&
f6c0e191
JH
346 !strcmp(p->two->path, origin->path)) {
347 porigin = get_origin(sb, parent, p->one->path);
348 hashcpy(porigin->blob_sha1, p->one->sha1);
cee7f245
JH
349 break;
350 }
351 }
352 diff_flush(&diff_opts);
353 return porigin;
354}
355
356struct chunk {
357 /* line number in postimage; up to but not including this
358 * line is the same as preimage
359 */
360 int same;
361
362 /* preimage line number after this chunk */
363 int p_next;
364
365 /* postimage line number after this chunk */
366 int t_next;
367};
368
369struct patch {
370 struct chunk *chunks;
371 int num;
372};
373
374struct 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};
380
381static 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;
386
cee7f245
JH
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 }
400
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 }
414
415 /* Line numbers in patch output are one based. */
416 off1--;
417 off2--;
418
419 chunk->same = len2 ? off2 : (off2 + 1);
420
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}
426
427static 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;
434
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;
445
446 xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);
447
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}
456
457static struct patch *get_patch(struct origin *parent, struct origin *origin)
458{
459 mmfile_t file_p, file_o;
cee7f245
JH
460 struct patch *patch;
461
c2e525d9
JH
462 fill_origin_blob(parent, &file_p);
463 fill_origin_blob(origin, &file_o);
464 if (!file_p.ptr || !file_o.ptr)
cee7f245 465 return NULL;
cee7f245 466 patch = compare_buffer(&file_p, &file_o, 0);
c2e525d9 467 num_get_patch++;
cee7f245
JH
468 return patch;
469}
470
471static void free_patch(struct patch *p)
472{
473 free(p->chunks);
474 free(p);
475}
476
477static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
478{
479 struct blame_entry *ent, *prev = NULL;
480
54a4c617
JH
481 origin_incref(e->suspect);
482
cee7f245
JH
483 for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
484 prev = ent;
485
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}
499
500static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
501{
502 struct blame_entry *p, *n;
54a4c617 503
cee7f245
JH
504 p = dst->prev;
505 n = dst->next;
54a4c617
JH
506 origin_incref(src->suspect);
507 origin_decref(dst->suspect);
cee7f245
JH
508 memcpy(dst, src, sizeof(*src));
509 dst->prev = p;
510 dst->next = n;
5ff62c30 511 dst->score = 0;
cee7f245
JH
512}
513
514static const char *nth_line(struct scoreboard *sb, int lno)
515{
516 return sb->final_buf + sb->lineno[lno];
517}
518
54a4c617 519static void split_overlap(struct blame_entry *split,
cee7f245
JH
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]));
540
541 if (e->s_lno < tlno) {
542 /* there is a pre-chunk part not blamed on parent */
54a4c617 543 split[0].suspect = origin_incref(e->suspect);
cee7f245
JH
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 }
554
555 if (same < e->s_lno + e->num_lines) {
556 /* there is a post-chunk part not blamed on parent */
54a4c617 557 split[2].suspect = origin_incref(e->suspect);
cee7f245
JH
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;
566
567 if (split[1].num_lines < 1)
568 return;
54a4c617 569 split[1].suspect = origin_incref(parent);
cee7f245
JH
570}
571
572static void split_blame(struct scoreboard *sb,
54a4c617 573 struct blame_entry *split,
cee7f245
JH
574 struct blame_entry *e)
575{
576 struct blame_entry *new_entry;
577
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]);
581
582 new_entry = xmalloc(sizeof(*new_entry));
583 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
584 add_blame_entry(sb, new_entry);
585
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]);
595
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]);
602
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 }
607
54a4c617 608 if (DEBUG) { /* sanity */
cee7f245 609 struct blame_entry *ent;
612702e8 610 int lno = sb->ent->lno, corrupt = 0;
cee7f245
JH
611
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) {
612702e8 620 lno = sb->ent->lno;
cee7f245
JH
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}
630
54a4c617
JH
631static void decref_split(struct blame_entry *split)
632{
633 int i;
634
635 for (i = 0; i < 3; i++)
636 origin_decref(split[i].suspect);
637}
638
cee7f245
JH
639static 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];
644
645 split_overlap(split, e, tlno, plno, same, parent);
54a4c617
JH
646 if (split[1].suspect)
647 split_blame(sb, split, e);
648 decref_split(split);
cee7f245
JH
649}
650
651static int find_last_in_target(struct scoreboard *sb, struct origin *target)
652{
653 struct blame_entry *e;
654 int last_in_target = -1;
655
656 for (e = sb->ent; e; e = e->next) {
46014766 657 if (e->guilty || cmp_suspect(e->suspect, target))
cee7f245
JH
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}
664
665static void blame_chunk(struct scoreboard *sb,
666 int tlno, int plno, int same,
667 struct origin *target, struct origin *parent)
668{
612702e8 669 struct blame_entry *e;
cee7f245 670
612702e8 671 for (e = sb->ent; e; e = e->next) {
46014766 672 if (e->guilty || cmp_suspect(e->suspect, target))
cee7f245
JH
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}
680
681static 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;
687
688 last_in_target = find_last_in_target(sb, target);
689 if (last_in_target < 0)
690 return 1; /* nothing remains for this target */
691
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];
696
cee7f245
JH
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);
703
704 free_patch(patch);
705 return 0;
706}
707
5ff62c30
JH
708static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
709{
710 unsigned score;
711 const char *cp, *ep;
712
713 if (e->score)
714 return e->score;
715
612702e8 716 score = 1;
5ff62c30
JH
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}
728
729static void copy_split_if_better(struct scoreboard *sb,
54a4c617
JH
730 struct blame_entry *best_so_far,
731 struct blame_entry *this)
d24bba80 732{
54a4c617
JH
733 int i;
734
d24bba80
JH
735 if (!this[1].suspect)
736 return;
5ff62c30
JH
737 if (best_so_far[1].suspect) {
738 if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
739 return;
740 }
54a4c617
JH
741
742 for (i = 0; i < 3; i++)
743 origin_incref(this[i].suspect);
744 decref_split(best_so_far);
d24bba80
JH
745 memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
746}
747
748static void find_copy_in_blob(struct scoreboard *sb,
749 struct blame_entry *ent,
750 struct origin *parent,
54a4c617 751 struct blame_entry *split,
d24bba80
JH
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;
759
760 cp = nth_line(sb, ent->lno);
761 file_o.ptr = (char*) cp;
762 cnt = ent->num_lines;
763
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;
769
770 patch = compare_buffer(file_p, &file_o, 1);
771
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];
776
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);
5ff62c30 786 copy_split_if_better(sb, split, this);
54a4c617 787 decref_split(this);
d24bba80
JH
788 }
789 plno = chunk->p_next;
790 tlno = chunk->t_next;
791 }
792 free_patch(patch);
793}
794
795static int find_move_in_parent(struct scoreboard *sb,
796 struct origin *target,
797 struct origin *parent)
798{
650e2f67 799 int last_in_target, made_progress;
46014766 800 struct blame_entry *e, split[3];
d24bba80 801 mmfile_t file_p;
d24bba80
JH
802
803 last_in_target = find_last_in_target(sb, target);
804 if (last_in_target < 0)
805 return 1; /* nothing remains for this target */
806
c2e525d9
JH
807 fill_origin_blob(parent, &file_p);
808 if (!file_p.ptr)
d24bba80 809 return 0;
d24bba80 810
650e2f67
JH
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 }
d24bba80 825 }
d24bba80
JH
826 return 0;
827}
828
33494784
JH
829
830struct blame_list {
831 struct blame_entry *ent;
832 struct blame_entry split[3];
833};
834
835static 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;
842
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}
858
18abd745
JH
859static 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];
aec8fa1f 867 int i, j;
33494784
JH
868 int retval;
869 struct blame_list *blame_list;
aec8fa1f 870 int num_ents;
18abd745 871
33494784
JH
872 blame_list = setup_blame_list(sb, target, &num_ents);
873 if (!blame_list)
18abd745
JH
874 return 1; /* nothing remains for this target */
875
876 diff_setup(&diff_opts);
877 diff_opts.recursive = 1;
878 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
879
18abd745
JH
880 paths[0] = NULL;
881 diff_tree_setup_paths(paths, &diff_opts);
882 if (diff_setup_done(&diff_opts) < 0)
883 die("diff-setup");
33494784
JH
884
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;
895
18abd745
JH
896 diff_tree_sha1(parent->tree->object.sha1,
897 target->commit->tree->object.sha1,
898 "", &diff_opts);
18abd745 899
33494784
JH
900 if (!diff_opts.find_copies_harder)
901 diffcore_std(&diff_opts);
18abd745 902
33494784
JH
903 retval = 0;
904 while (1) {
905 int made_progress = 0;
906
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;
33494784
JH
911 struct blame_entry this[3];
912
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;
918
919 norigin = get_origin(sb, parent, p->one->path);
920 hashcpy(norigin->blob_sha1, p->one->sha1);
c2e525d9 921 fill_origin_blob(norigin, &file_p);
33494784
JH
922 if (!file_p.ptr)
923 continue;
924
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 }
33494784
JH
932 origin_decref(norigin);
933 }
18abd745 934
aec8fa1f 935 for (j = 0; j < num_ents; j++) {
33494784
JH
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);
18abd745 943 }
33494784 944 free(blame_list);
aec8fa1f 945
33494784
JH
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 }
18abd745 953 }
33494784 954 diff_flush(&diff_opts);
18abd745 955
33494784 956 return retval;
18abd745
JH
957}
958
c2e525d9
JH
959/* The blobs of origin and porigin exactly match, so everything
960 * origin is suspected for can be blamed on the parent.
961 */
962static void pass_whole_blame(struct scoreboard *sb,
963 struct origin *origin, struct origin *porigin)
964{
965 struct blame_entry *e;
966
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}
980
cee7f245
JH
981#define MAXPARENT 16
982
d24bba80 983static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
cee7f245 984{
f69e743d 985 int i, pass;
cee7f245
JH
986 struct commit *commit = origin->commit;
987 struct commit_list *parent;
988 struct origin *parent_origin[MAXPARENT], *porigin;
989
990 memset(parent_origin, 0, sizeof(parent_origin));
cee7f245 991
f69e743d
JH
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;
999
1000 for (i = 0, parent = commit->parents;
1001 i < MAXPARENT && parent;
1002 parent = parent->next, i++) {
1003 struct commit *p = parent->item;
0421d9f8 1004 int j, same;
f69e743d
JH
1005
1006 if (parent_origin[i])
1007 continue;
1008 if (parse_commit(p))
1009 continue;
0d981c67 1010 porigin = find(sb, p, origin);
f69e743d
JH
1011 if (!porigin)
1012 continue;
1013 if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
c2e525d9 1014 pass_whole_blame(sb, origin, porigin);
f69e743d
JH
1015 origin_decref(porigin);
1016 goto finish;
1017 }
0421d9f8 1018 for (j = same = 0; j < i; j++)
33494784
JH
1019 if (parent_origin[j] &&
1020 !hashcmp(parent_origin[j]->blob_sha1,
0421d9f8
JH
1021 porigin->blob_sha1)) {
1022 same = 1;
1023 break;
1024 }
1025 if (!same)
1026 parent_origin[i] = porigin;
1027 else
1028 origin_decref(porigin);
cee7f245 1029 }
cee7f245
JH
1030 }
1031
c2e525d9 1032 num_commits++;
cee7f245
JH
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))
54a4c617 1040 goto finish;
cee7f245 1041 }
d24bba80
JH
1042
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))
54a4c617 1054 goto finish;
d24bba80
JH
1055 }
1056
18abd745
JH
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))
54a4c617 1067 goto finish;
18abd745 1068 }
54a4c617
JH
1069
1070 finish:
1071 for (i = 0; i < MAXPARENT; i++)
1072 origin_decref(parent_origin[i]);
cee7f245
JH
1073}
1074
cee7f245
JH
1075struct commit_info
1076{
1077 char *author;
1078 char *author_mail;
1079 unsigned long author_time;
1080 char *author_tz;
1081
1082 /* filled only when asked for details */
1083 char *committer;
1084 char *committer_mail;
1085 unsigned long committer_time;
1086 char *committer_tz;
1087
1088 char *summary;
1089};
1090
1091static 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;
1097
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);
1115
1116 tmp = person;
1117 tmp += len;
1118 *tmp = 0;
1119 while (*tmp != ' ')
1120 tmp--;
1121 *tz = tmp+1;
1122
1123 *tmp = 0;
1124 while (*tmp != ' ')
1125 tmp--;
1126 *time = strtoul(tmp, NULL, 10);
1127
1128 *tmp = 0;
1129 while (*tmp != ' ')
1130 tmp--;
1131 *mail = tmp + 1;
1132 *tmp = 0;
1133}
1134
1135static 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];
1144
612702e8
JH
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 }
cee7f245
JH
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);
1158
1159 if (!detailed)
1160 return;
1161
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);
1166
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}
1184
46e5e69d
JH
1185static void write_filename_info(const char *path)
1186{
1187 printf("filename ");
1188 write_name_quoted(NULL, 0, path, 1, stdout);
1189 putchar('\n');
1190}
1191
717d1462
LT
1192static void found_guilty_entry(struct blame_entry *ent)
1193{
1194 if (ent->guilty)
1195 return;
1196 ent->guilty = 1;
1197 if (incremental) {
1198 struct origin *suspect = ent->suspect;
1199
1200 printf("%s %d %d %d\n",
1201 sha1_to_hex(suspect->commit->object.sha1),
1202 ent->s_lno + 1, ent->lno + 1, ent->num_lines);
1203 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1204 struct commit_info ci;
1205 suspect->commit->object.flags |= METAINFO_SHOWN;
1206 get_commit_info(suspect->commit, &ci, 1);
1207 printf("author %s\n", ci.author);
1208 printf("author-mail %s\n", ci.author_mail);
1209 printf("author-time %lu\n", ci.author_time);
1210 printf("author-tz %s\n", ci.author_tz);
1211 printf("committer %s\n", ci.committer);
1212 printf("committer-mail %s\n", ci.committer_mail);
1213 printf("committer-time %lu\n", ci.committer_time);
1214 printf("committer-tz %s\n", ci.committer_tz);
1215 printf("summary %s\n", ci.summary);
1216 if (suspect->commit->object.flags & UNINTERESTING)
1217 printf("boundary\n");
1218 }
46e5e69d 1219 write_filename_info(suspect->path);
717d1462
LT
1220 }
1221}
1222
1223static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)
1224{
1225 while (1) {
1226 struct blame_entry *ent;
1227 struct commit *commit;
1228 struct origin *suspect = NULL;
1229
1230 /* find one suspect to break down */
1231 for (ent = sb->ent; !suspect && ent; ent = ent->next)
1232 if (!ent->guilty)
1233 suspect = ent->suspect;
1234 if (!suspect)
1235 return; /* all done */
1236
1237 origin_incref(suspect);
1238 commit = suspect->commit;
1239 if (!commit->object.parsed)
1240 parse_commit(commit);
1241 if (!(commit->object.flags & UNINTERESTING) &&
1242 !(revs->max_age != -1 && commit->date < revs->max_age))
1243 pass_blame(sb, suspect, opt);
1244 else {
1245 commit->object.flags |= UNINTERESTING;
1246 if (commit->object.parsed)
1247 mark_parents_uninteresting(commit);
1248 }
1249 /* treat root commit as boundary */
1250 if (!commit->parents && !show_root)
1251 commit->object.flags |= UNINTERESTING;
1252
1253 /* Take responsibility for the remaining entries */
1254 for (ent = sb->ent; ent; ent = ent->next)
1255 if (!cmp_suspect(ent->suspect, suspect))
1256 found_guilty_entry(ent);
1257 origin_decref(suspect);
1258
1259 if (DEBUG) /* sanity */
1260 sanity_check_refcnt(sb);
1261 }
1262}
1263
1264static const char *format_time(unsigned long time, const char *tz_str,
1265 int show_raw_time)
1266{
1267 static char time_buf[128];
1268 time_t t = time;
1269 int minutes, tz;
1270 struct tm *tm;
1271
1272 if (show_raw_time) {
1273 sprintf(time_buf, "%lu %s", time, tz_str);
1274 return time_buf;
1275 }
1276
1277 tz = atoi(tz_str);
1278 minutes = tz < 0 ? -tz : tz;
1279 minutes = (minutes / 100)*60 + (minutes % 100);
1280 minutes = tz < 0 ? -minutes : minutes;
1281 t = time + minutes * 60;
1282 tm = gmtime(&t);
1283
1284 strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
1285 strcat(time_buf, tz_str);
1286 return time_buf;
1287}
1288
cee7f245
JH
1289#define OUTPUT_ANNOTATE_COMPAT 001
1290#define OUTPUT_LONG_OBJECT_NAME 002
1291#define OUTPUT_RAW_TIMESTAMP 004
1292#define OUTPUT_PORCELAIN 010
1293#define OUTPUT_SHOW_NAME 020
1294#define OUTPUT_SHOW_NUMBER 040
5ff62c30 1295#define OUTPUT_SHOW_SCORE 0100
cee7f245
JH
1296
1297static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
1298{
1299 int cnt;
1300 const char *cp;
1301 struct origin *suspect = ent->suspect;
1302 char hex[41];
1303
1304 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1305 printf("%s%c%d %d %d\n",
1306 hex,
1307 ent->guilty ? ' ' : '*', // purely for debugging
1308 ent->s_lno + 1,
1309 ent->lno + 1,
1310 ent->num_lines);
1311 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1312 struct commit_info ci;
1313 suspect->commit->object.flags |= METAINFO_SHOWN;
1314 get_commit_info(suspect->commit, &ci, 1);
1315 printf("author %s\n", ci.author);
1316 printf("author-mail %s\n", ci.author_mail);
1317 printf("author-time %lu\n", ci.author_time);
1318 printf("author-tz %s\n", ci.author_tz);
1319 printf("committer %s\n", ci.committer);
1320 printf("committer-mail %s\n", ci.committer_mail);
1321 printf("committer-time %lu\n", ci.committer_time);
1322 printf("committer-tz %s\n", ci.committer_tz);
46e5e69d 1323 write_filename_info(suspect->path);
cee7f245 1324 printf("summary %s\n", ci.summary);
b11121d9
JH
1325 if (suspect->commit->object.flags & UNINTERESTING)
1326 printf("boundary\n");
cee7f245
JH
1327 }
1328 else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
46e5e69d 1329 write_filename_info(suspect->path);
cee7f245
JH
1330
1331 cp = nth_line(sb, ent->lno);
1332 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1333 char ch;
1334 if (cnt)
1335 printf("%s %d %d\n", hex,
1336 ent->s_lno + 1 + cnt,
1337 ent->lno + 1 + cnt);
1338 putchar('\t');
1339 do {
1340 ch = *cp++;
1341 putchar(ch);
1342 } while (ch != '\n' &&
1343 cp < sb->final_buf + sb->final_buf_size);
1344 }
1345}
1346
1347static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1348{
1349 int cnt;
1350 const char *cp;
1351 struct origin *suspect = ent->suspect;
1352 struct commit_info ci;
1353 char hex[41];
1354 int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1355
1356 get_commit_info(suspect->commit, &ci, 1);
1357 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1358
1359 cp = nth_line(sb, ent->lno);
1360 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1361 char ch;
b11121d9
JH
1362 int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8;
1363
1364 if (suspect->commit->object.flags & UNINTERESTING) {
4c10a5ca
JH
1365 if (!blank_boundary) {
1366 length--;
1367 putchar('^');
1368 }
1369 else
1370 memset(hex, ' ', length);
b11121d9 1371 }
cee7f245 1372
b11121d9 1373 printf("%.*s", length, hex);
cee7f245
JH
1374 if (opt & OUTPUT_ANNOTATE_COMPAT)
1375 printf("\t(%10s\t%10s\t%d)", ci.author,
1376 format_time(ci.author_time, ci.author_tz,
1377 show_raw_time),
1378 ent->lno + 1 + cnt);
1379 else {
5ff62c30 1380 if (opt & OUTPUT_SHOW_SCORE)
54a4c617
JH
1381 printf(" %*d %02d",
1382 max_score_digits, ent->score,
1383 ent->suspect->refcnt);
cee7f245
JH
1384 if (opt & OUTPUT_SHOW_NAME)
1385 printf(" %-*.*s", longest_file, longest_file,
1386 suspect->path);
1387 if (opt & OUTPUT_SHOW_NUMBER)
1388 printf(" %*d", max_orig_digits,
1389 ent->s_lno + 1 + cnt);
1390 printf(" (%-*.*s %10s %*d) ",
1391 longest_author, longest_author, ci.author,
1392 format_time(ci.author_time, ci.author_tz,
1393 show_raw_time),
1394 max_digits, ent->lno + 1 + cnt);
1395 }
1396 do {
1397 ch = *cp++;
1398 putchar(ch);
1399 } while (ch != '\n' &&
1400 cp < sb->final_buf + sb->final_buf_size);
1401 }
1402}
1403
1404static void output(struct scoreboard *sb, int option)
1405{
1406 struct blame_entry *ent;
1407
1408 if (option & OUTPUT_PORCELAIN) {
1409 for (ent = sb->ent; ent; ent = ent->next) {
1410 struct blame_entry *oth;
1411 struct origin *suspect = ent->suspect;
1412 struct commit *commit = suspect->commit;
1413 if (commit->object.flags & MORE_THAN_ONE_PATH)
1414 continue;
1415 for (oth = ent->next; oth; oth = oth->next) {
1416 if ((oth->suspect->commit != commit) ||
1417 !strcmp(oth->suspect->path, suspect->path))
1418 continue;
1419 commit->object.flags |= MORE_THAN_ONE_PATH;
1420 break;
1421 }
1422 }
1423 }
1424
1425 for (ent = sb->ent; ent; ent = ent->next) {
1426 if (option & OUTPUT_PORCELAIN)
1427 emit_porcelain(sb, ent);
5ff62c30 1428 else {
cee7f245 1429 emit_other(sb, ent, option);
5ff62c30 1430 }
cee7f245
JH
1431 }
1432}
1433
1434static int prepare_lines(struct scoreboard *sb)
1435{
1436 const char *buf = sb->final_buf;
1437 unsigned long len = sb->final_buf_size;
1438 int num = 0, incomplete = 0, bol = 1;
1439
1440 if (len && buf[len-1] != '\n')
1441 incomplete++; /* incomplete line at the end */
1442 while (len--) {
1443 if (bol) {
1444 sb->lineno = xrealloc(sb->lineno,
1445 sizeof(int* ) * (num + 1));
1446 sb->lineno[num] = buf - sb->final_buf;
1447 bol = 0;
1448 }
1449 if (*buf++ == '\n') {
1450 num++;
1451 bol = 1;
1452 }
1453 }
1ca6ca87
JH
1454 sb->lineno = xrealloc(sb->lineno,
1455 sizeof(int* ) * (num + incomplete + 1));
1456 sb->lineno[num + incomplete] = buf - sb->final_buf;
cee7f245
JH
1457 sb->num_lines = num + incomplete;
1458 return sb->num_lines;
1459}
1460
1461static int read_ancestry(const char *graft_file)
1462{
1463 FILE *fp = fopen(graft_file, "r");
1464 char buf[1024];
1465 if (!fp)
1466 return -1;
1467 while (fgets(buf, sizeof(buf), fp)) {
1468 /* The format is just "Commit Parent1 Parent2 ...\n" */
1469 int len = strlen(buf);
1470 struct commit_graft *graft = read_graft_line(buf, len);
8eaf7986
JH
1471 if (graft)
1472 register_commit_graft(graft, 0);
cee7f245
JH
1473 }
1474 fclose(fp);
1475 return 0;
1476}
1477
1478static int lineno_width(int lines)
1479{
1480 int i, width;
1481
1482 for (width = 1, i = 10; i <= lines + 1; width++)
1483 i *= 10;
1484 return width;
1485}
1486
1487static void find_alignment(struct scoreboard *sb, int *option)
1488{
1489 int longest_src_lines = 0;
1490 int longest_dst_lines = 0;
5ff62c30 1491 unsigned largest_score = 0;
cee7f245
JH
1492 struct blame_entry *e;
1493
1494 for (e = sb->ent; e; e = e->next) {
1495 struct origin *suspect = e->suspect;
1496 struct commit_info ci;
1497 int num;
1498
ab3bb800
JH
1499 if (strcmp(suspect->path, sb->path))
1500 *option |= OUTPUT_SHOW_NAME;
1501 num = strlen(suspect->path);
1502 if (longest_file < num)
1503 longest_file = num;
cee7f245
JH
1504 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1505 suspect->commit->object.flags |= METAINFO_SHOWN;
1506 get_commit_info(suspect->commit, &ci, 1);
cee7f245
JH
1507 num = strlen(ci.author);
1508 if (longest_author < num)
1509 longest_author = num;
1510 }
1511 num = e->s_lno + e->num_lines;
1512 if (longest_src_lines < num)
1513 longest_src_lines = num;
1514 num = e->lno + e->num_lines;
1515 if (longest_dst_lines < num)
1516 longest_dst_lines = num;
5ff62c30
JH
1517 if (largest_score < ent_score(sb, e))
1518 largest_score = ent_score(sb, e);
cee7f245
JH
1519 }
1520 max_orig_digits = lineno_width(longest_src_lines);
1521 max_digits = lineno_width(longest_dst_lines);
5ff62c30 1522 max_score_digits = lineno_width(largest_score);
cee7f245
JH
1523}
1524
54a4c617
JH
1525static void sanity_check_refcnt(struct scoreboard *sb)
1526{
1527 int baa = 0;
1528 struct blame_entry *ent;
1529
1530 for (ent = sb->ent; ent; ent = ent->next) {
ae86ad65 1531 /* Nobody should have zero or negative refcnt */
854b97f6
JH
1532 if (ent->suspect->refcnt <= 0) {
1533 fprintf(stderr, "%s in %s has negative refcnt %d\n",
1534 ent->suspect->path,
1535 sha1_to_hex(ent->suspect->commit->object.sha1),
1536 ent->suspect->refcnt);
ae86ad65 1537 baa = 1;
854b97f6 1538 }
ae86ad65
JH
1539 }
1540 for (ent = sb->ent; ent; ent = ent->next) {
1541 /* Mark the ones that haven't been checked */
54a4c617
JH
1542 if (0 < ent->suspect->refcnt)
1543 ent->suspect->refcnt = -ent->suspect->refcnt;
54a4c617
JH
1544 }
1545 for (ent = sb->ent; ent; ent = ent->next) {
0d981c67 1546 /* then pick each and see if they have the the correct
854b97f6 1547 * refcnt.
54a4c617
JH
1548 */
1549 int found;
1550 struct blame_entry *e;
1551 struct origin *suspect = ent->suspect;
1552
1553 if (0 < suspect->refcnt)
1554 continue;
ae86ad65 1555 suspect->refcnt = -suspect->refcnt; /* Unmark */
54a4c617
JH
1556 for (found = 0, e = sb->ent; e; e = e->next) {
1557 if (e->suspect != suspect)
1558 continue;
1559 found++;
1560 }
854b97f6
JH
1561 if (suspect->refcnt != found) {
1562 fprintf(stderr, "%s in %s has refcnt %d, not %d\n",
1563 ent->suspect->path,
1564 sha1_to_hex(ent->suspect->commit->object.sha1),
1565 ent->suspect->refcnt, found);
1566 baa = 2;
1567 }
54a4c617
JH
1568 }
1569 if (baa) {
1570 int opt = 0160;
1571 find_alignment(sb, &opt);
1572 output(sb, opt);
854b97f6 1573 die("Baa %d!", baa);
54a4c617
JH
1574 }
1575}
1576
cee7f245
JH
1577static int has_path_in_work_tree(const char *path)
1578{
1579 struct stat st;
1580 return !lstat(path, &st);
1581}
1582
4a0fc95f
JH
1583static unsigned parse_score(const char *arg)
1584{
1585 char *end;
1586 unsigned long score = strtoul(arg, &end, 10);
1587 if (*end)
1588 return 0;
1589 return score;
1590}
1591
20239bae
JK
1592static const char *add_prefix(const char *prefix, const char *path)
1593{
1594 if (!prefix || !prefix[0])
1595 return path;
1596 return prefix_path(prefix, strlen(prefix), path);
1597}
1598
931233bc
JH
1599static const char *parse_loc(const char *spec,
1600 struct scoreboard *sb, long lno,
1601 long begin, long *ret)
1602{
1603 char *term;
1604 const char *line;
1605 long num;
1606 int reg_error;
1607 regex_t regexp;
1608 regmatch_t match[1];
1609
7bd9641d
JH
1610 /* Allow "-L <something>,+20" to mean starting at <something>
1611 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
1612 * <something>.
1613 */
1614 if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
1615 num = strtol(spec + 1, &term, 10);
1616 if (term != spec + 1) {
1617 if (spec[0] == '-')
1618 num = 0 - num;
1619 if (0 < num)
1620 *ret = begin + num - 2;
1621 else if (!num)
1622 *ret = begin;
1623 else
1624 *ret = begin + num;
1625 return term;
1626 }
1627 return spec;
1628 }
931233bc
JH
1629 num = strtol(spec, &term, 10);
1630 if (term != spec) {
1631 *ret = num;
1632 return term;
1633 }
1634 if (spec[0] != '/')
1635 return spec;
1636
1637 /* it could be a regexp of form /.../ */
1638 for (term = (char*) spec + 1; *term && *term != '/'; term++) {
1639 if (*term == '\\')
1640 term++;
1641 }
1642 if (*term != '/')
1643 return spec;
1644
1645 /* try [spec+1 .. term-1] as regexp */
1646 *term = 0;
1647 begin--; /* input is in human terms */
1648 line = nth_line(sb, begin);
1649
1650 if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
1651 !(reg_error = regexec(&regexp, line, 1, match, 0))) {
1652 const char *cp = line + match[0].rm_so;
1653 const char *nline;
1654
1655 while (begin++ < lno) {
1656 nline = nth_line(sb, begin);
1657 if (line <= cp && cp < nline)
1658 break;
1659 line = nline;
1660 }
1661 *ret = begin;
1662 regfree(&regexp);
1663 *term++ = '/';
1664 return term;
1665 }
1666 else {
1667 char errbuf[1024];
1668 regerror(reg_error, &regexp, errbuf, 1024);
1669 die("-L parameter '%s': %s", spec + 1, errbuf);
1670 }
1671}
1672
1673static void prepare_blame_range(struct scoreboard *sb,
1674 const char *bottomtop,
1675 long lno,
1676 long *bottom, long *top)
1677{
1678 const char *term;
1679
1680 term = parse_loc(bottomtop, sb, lno, 1, bottom);
1681 if (*term == ',') {
1682 term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
1683 if (*term)
acca687f 1684 usage(blame_usage);
931233bc
JH
1685 }
1686 if (*term)
acca687f 1687 usage(blame_usage);
931233bc
JH
1688}
1689
4c10a5ca
JH
1690static int git_blame_config(const char *var, const char *value)
1691{
1692 if (!strcmp(var, "blame.showroot")) {
1693 show_root = git_config_bool(var, value);
1694 return 0;
1695 }
1696 if (!strcmp(var, "blame.blankboundary")) {
1697 blank_boundary = git_config_bool(var, value);
1698 return 0;
1699 }
1700 return git_default_config(var, value);
1701}
1702
acca687f 1703int cmd_blame(int argc, const char **argv, const char *prefix)
cee7f245
JH
1704{
1705 struct rev_info revs;
1706 const char *path;
1707 struct scoreboard sb;
1708 struct origin *o;
1709 struct blame_entry *ent;
d24bba80 1710 int i, seen_dashdash, unk, opt;
cee7f245
JH
1711 long bottom, top, lno;
1712 int output_option = 0;
1713 const char *revs_file = NULL;
1714 const char *final_commit_name = NULL;
1715 char type[10];
931233bc 1716 const char *bottomtop = NULL;
cee7f245 1717
4c10a5ca 1718 git_config(git_blame_config);
612702e8
JH
1719 save_commit_buffer = 0;
1720
d24bba80 1721 opt = 0;
cee7f245
JH
1722 seen_dashdash = 0;
1723 for (unk = i = 1; i < argc; i++) {
1724 const char *arg = argv[i];
1725 if (*arg != '-')
1726 break;
4c10a5ca
JH
1727 else if (!strcmp("-b", arg))
1728 blank_boundary = 1;
1729 else if (!strcmp("--root", arg))
1730 show_root = 1;
cee7f245
JH
1731 else if (!strcmp("-c", arg))
1732 output_option |= OUTPUT_ANNOTATE_COMPAT;
1733 else if (!strcmp("-t", arg))
1734 output_option |= OUTPUT_RAW_TIMESTAMP;
1735 else if (!strcmp("-l", arg))
1736 output_option |= OUTPUT_LONG_OBJECT_NAME;
1737 else if (!strcmp("-S", arg) && ++i < argc)
1738 revs_file = argv[i];
4a0fc95f 1739 else if (!strncmp("-M", arg, 2)) {
d24bba80 1740 opt |= PICKAXE_BLAME_MOVE;
4a0fc95f
JH
1741 blame_move_score = parse_score(arg+2);
1742 }
1743 else if (!strncmp("-C", arg, 2)) {
18abd745
JH
1744 if (opt & PICKAXE_BLAME_COPY)
1745 opt |= PICKAXE_BLAME_COPY_HARDER;
1746 opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
4a0fc95f 1747 blame_copy_score = parse_score(arg+2);
18abd745 1748 }
2c40f984 1749 else if (!strncmp("-L", arg, 2)) {
2c40f984
JH
1750 if (!arg[2]) {
1751 if (++i >= argc)
acca687f 1752 usage(blame_usage);
2c40f984
JH
1753 arg = argv[i];
1754 }
1755 else
1756 arg += 2;
931233bc 1757 if (bottomtop)
cee7f245 1758 die("More than one '-L n,m' option given");
931233bc 1759 bottomtop = arg;
cee7f245 1760 }
717d1462
LT
1761 else if (!strcmp("--incremental", arg))
1762 incremental = 1;
5ff62c30
JH
1763 else if (!strcmp("--score-debug", arg))
1764 output_option |= OUTPUT_SHOW_SCORE;
cee7f245
JH
1765 else if (!strcmp("-f", arg) ||
1766 !strcmp("--show-name", arg))
1767 output_option |= OUTPUT_SHOW_NAME;
1768 else if (!strcmp("-n", arg) ||
1769 !strcmp("--show-number", arg))
1770 output_option |= OUTPUT_SHOW_NUMBER;
1771 else if (!strcmp("-p", arg) ||
1772 !strcmp("--porcelain", arg))
1773 output_option |= OUTPUT_PORCELAIN;
1774 else if (!strcmp("--", arg)) {
1775 seen_dashdash = 1;
1776 i++;
1777 break;
1778 }
1779 else
1780 argv[unk++] = arg;
1781 }
1782
4f0219a4
RS
1783 if (!incremental)
1784 setup_pager();
1785
4a0fc95f
JH
1786 if (!blame_move_score)
1787 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
1788 if (!blame_copy_score)
1789 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
1790
cee7f245
JH
1791 /* We have collected options unknown to us in argv[1..unk]
1792 * which are to be passed to revision machinery if we are
1793 * going to do the "bottom" procesing.
1794 *
1795 * The remaining are:
1796 *
1797 * (1) if seen_dashdash, its either
1798 * "-options -- <path>" or
1799 * "-options -- <path> <rev>".
1800 * but the latter is allowed only if there is no
1801 * options that we passed to revision machinery.
1802 *
1803 * (2) otherwise, we may have "--" somewhere later and
1804 * might be looking at the first one of multiple 'rev'
1805 * parameters (e.g. " master ^next ^maint -- path").
1806 * See if there is a dashdash first, and give the
1807 * arguments before that to revision machinery.
1808 * After that there must be one 'path'.
1809 *
1810 * (3) otherwise, its one of the three:
1811 * "-options <path> <rev>"
1812 * "-options <rev> <path>"
1813 * "-options <path>"
1814 * but again the first one is allowed only if
1815 * there is no options that we passed to revision
1816 * machinery.
1817 */
1818
1819 if (seen_dashdash) {
1820 /* (1) */
1821 if (argc <= i)
acca687f 1822 usage(blame_usage);
20239bae 1823 path = add_prefix(prefix, argv[i]);
cee7f245
JH
1824 if (i + 1 == argc - 1) {
1825 if (unk != 1)
acca687f 1826 usage(blame_usage);
cee7f245
JH
1827 argv[unk++] = argv[i + 1];
1828 }
1829 else if (i + 1 != argc)
1830 /* garbage at end */
acca687f 1831 usage(blame_usage);
cee7f245
JH
1832 }
1833 else {
1834 int j;
1835 for (j = i; !seen_dashdash && j < argc; j++)
1836 if (!strcmp(argv[j], "--"))
1837 seen_dashdash = j;
1838 if (seen_dashdash) {
1839 if (seen_dashdash + 1 != argc - 1)
acca687f 1840 usage(blame_usage);
20239bae 1841 path = add_prefix(prefix, argv[seen_dashdash + 1]);
cee7f245
JH
1842 for (j = i; j < seen_dashdash; j++)
1843 argv[unk++] = argv[j];
1844 }
1845 else {
1846 /* (3) */
20239bae 1847 path = add_prefix(prefix, argv[i]);
cee7f245
JH
1848 if (i + 1 == argc - 1) {
1849 final_commit_name = argv[i + 1];
1850
1851 /* if (unk == 1) we could be getting
1852 * old-style
1853 */
1854 if (unk == 1 && !has_path_in_work_tree(path)) {
20239bae 1855 path = add_prefix(prefix, argv[i + 1]);
cee7f245
JH
1856 final_commit_name = argv[i];
1857 }
1858 }
1859 else if (i != argc - 1)
acca687f 1860 usage(blame_usage); /* garbage at end */
cee7f245
JH
1861
1862 if (!has_path_in_work_tree(path))
1863 die("cannot stat path %s: %s",
1864 path, strerror(errno));
1865 }
1866 }
1867
1868 if (final_commit_name)
1869 argv[unk++] = final_commit_name;
1870
1871 /* Now we got rev and path. We do not want the path pruning
1872 * but we may want "bottom" processing.
1873 */
6bee4e40 1874 argv[unk++] = "--"; /* terminate the rev name */
cee7f245
JH
1875 argv[unk] = NULL;
1876
1877 init_revisions(&revs, NULL);
1878 setup_revisions(unk, argv, &revs, "HEAD");
1879 memset(&sb, 0, sizeof(sb));
1880
1881 /* There must be one and only one positive commit in the
1882 * revs->pending array.
1883 */
1884 for (i = 0; i < revs.pending.nr; i++) {
1885 struct object *obj = revs.pending.objects[i].item;
1886 if (obj->flags & UNINTERESTING)
1887 continue;
1888 while (obj->type == OBJ_TAG)
1889 obj = deref_tag(obj, NULL, 0);
1890 if (obj->type != OBJ_COMMIT)
1891 die("Non commit %s?",
1892 revs.pending.objects[i].name);
1893 if (sb.final)
1894 die("More than one commit to dig from %s and %s?",
1895 revs.pending.objects[i].name,
1896 final_commit_name);
1897 sb.final = (struct commit *) obj;
1898 final_commit_name = revs.pending.objects[i].name;
1899 }
1900
1901 if (!sb.final) {
1902 /* "--not A B -- path" without anything positive */
1903 unsigned char head_sha1[20];
1904
1905 final_commit_name = "HEAD";
1906 if (get_sha1(final_commit_name, head_sha1))
1907 die("No such ref: HEAD");
1908 sb.final = lookup_commit_reference(head_sha1);
1909 add_pending_object(&revs, &(sb.final->object), "HEAD");
1910 }
1911
1912 /* If we have bottom, this will mark the ancestors of the
1913 * bottom commits we would reach while traversing as
1914 * uninteresting.
1915 */
1916 prepare_revision_walk(&revs);
1917
f6c0e191
JH
1918 o = get_origin(&sb, sb.final, path);
1919 if (fill_blob_sha1(o))
cee7f245
JH
1920 die("no such path %s in %s", path, final_commit_name);
1921
1922 sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
c2e525d9 1923 num_read_blob++;
cee7f245
JH
1924 lno = prepare_lines(&sb);
1925
931233bc
JH
1926 bottom = top = 0;
1927 if (bottomtop)
1928 prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);
1929 if (bottom && top && top < bottom) {
1930 long tmp;
1931 tmp = top; top = bottom; bottom = tmp;
1932 }
cee7f245
JH
1933 if (bottom < 1)
1934 bottom = 1;
1935 if (top < 1)
1936 top = lno;
1937 bottom--;
1938 if (lno < top)
1939 die("file %s has only %lu lines", path, lno);
1940
1941 ent = xcalloc(1, sizeof(*ent));
1942 ent->lno = bottom;
1943 ent->num_lines = top - bottom;
1944 ent->suspect = o;
1945 ent->s_lno = bottom;
1946
1947 sb.ent = ent;
1948 sb.path = path;
1949
1950 if (revs_file && read_ancestry(revs_file))
1951 die("reading graft file %s failed: %s",
1952 revs_file, strerror(errno));
1953
d24bba80 1954 assign_blame(&sb, &revs, opt);
cee7f245 1955
717d1462
LT
1956 if (incremental)
1957 return 0;
1958
cee7f245
JH
1959 coalesce(&sb);
1960
1961 if (!(output_option & OUTPUT_PORCELAIN))
1962 find_alignment(&sb, &output_option);
1963
1964 output(&sb, output_option);
1965 free((void *)sb.final_buf);
1966 for (ent = sb.ent; ent; ) {
1967 struct blame_entry *e = ent->next;
1968 free(ent);
1969 ent = e;
1970 }
c2e525d9
JH
1971
1972 if (DEBUG) {
1973 printf("num read blob: %d\n", num_read_blob);
1974 printf("num get patch: %d\n", num_get_patch);
1975 printf("num commits: %d\n", num_commits);
1976 }
cee7f245
JH
1977 return 0;
1978}