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