rerere: fix breakage of resolving.
[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
18#include <time.h>
19#include <sys/time.h>
931233bc 20#include <regex.h>
cee7f245 21
acca687f
JH
22static char blame_usage[] =
23"git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n"
cee7f245
JH
24" -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
25" -l, --long Show long commit SHA1 (Default: off)\n"
26" -t, --time Show raw timestamp (Default: off)\n"
27" -f, --show-name Show original filename (Default: auto)\n"
28" -n, --show-number Show original linenumber (Default: off)\n"
29" -p, --porcelain Show in a format designed for machine consumption\n"
30" -L n,m Process only line range n,m, counting from 1\n"
18abd745 31" -M, -C Find line movements within and across files\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;
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 }
cee7f245
JH
1098
1099 /* Take responsibility for the remaining entries */
1100 for (ent = sb->ent; ent; ent = ent->next)
46014766 1101 if (!cmp_suspect(ent->suspect, suspect))
cee7f245 1102 ent->guilty = 1;
54a4c617 1103 origin_decref(suspect);
ae86ad65
JH
1104
1105 if (DEBUG) /* sanity */
1106 sanity_check_refcnt(sb);
cee7f245
JH
1107 }
1108}
1109
1110static const char *format_time(unsigned long time, const char *tz_str,
1111 int show_raw_time)
1112{
1113 static char time_buf[128];
1114 time_t t = time;
1115 int minutes, tz;
1116 struct tm *tm;
1117
1118 if (show_raw_time) {
1119 sprintf(time_buf, "%lu %s", time, tz_str);
1120 return time_buf;
1121 }
1122
1123 tz = atoi(tz_str);
1124 minutes = tz < 0 ? -tz : tz;
1125 minutes = (minutes / 100)*60 + (minutes % 100);
1126 minutes = tz < 0 ? -minutes : minutes;
1127 t = time + minutes * 60;
1128 tm = gmtime(&t);
1129
1130 strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
1131 strcat(time_buf, tz_str);
1132 return time_buf;
1133}
1134
1135struct commit_info
1136{
1137 char *author;
1138 char *author_mail;
1139 unsigned long author_time;
1140 char *author_tz;
1141
1142 /* filled only when asked for details */
1143 char *committer;
1144 char *committer_mail;
1145 unsigned long committer_time;
1146 char *committer_tz;
1147
1148 char *summary;
1149};
1150
1151static void get_ac_line(const char *inbuf, const char *what,
1152 int bufsz, char *person, char **mail,
1153 unsigned long *time, char **tz)
1154{
1155 int len;
1156 char *tmp, *endp;
1157
1158 tmp = strstr(inbuf, what);
1159 if (!tmp)
1160 goto error_out;
1161 tmp += strlen(what);
1162 endp = strchr(tmp, '\n');
1163 if (!endp)
1164 len = strlen(tmp);
1165 else
1166 len = endp - tmp;
1167 if (bufsz <= len) {
1168 error_out:
1169 /* Ugh */
1170 person = *mail = *tz = "(unknown)";
1171 *time = 0;
1172 return;
1173 }
1174 memcpy(person, tmp, len);
1175
1176 tmp = person;
1177 tmp += len;
1178 *tmp = 0;
1179 while (*tmp != ' ')
1180 tmp--;
1181 *tz = tmp+1;
1182
1183 *tmp = 0;
1184 while (*tmp != ' ')
1185 tmp--;
1186 *time = strtoul(tmp, NULL, 10);
1187
1188 *tmp = 0;
1189 while (*tmp != ' ')
1190 tmp--;
1191 *mail = tmp + 1;
1192 *tmp = 0;
1193}
1194
1195static void get_commit_info(struct commit *commit,
1196 struct commit_info *ret,
1197 int detailed)
1198{
1199 int len;
1200 char *tmp, *endp;
1201 static char author_buf[1024];
1202 static char committer_buf[1024];
1203 static char summary_buf[1024];
1204
612702e8
JH
1205 /* We've operated without save_commit_buffer, so
1206 * we now need to populate them for output.
1207 */
1208 if (!commit->buffer) {
1209 char type[20];
1210 unsigned long size;
1211 commit->buffer =
1212 read_sha1_file(commit->object.sha1, type, &size);
1213 }
cee7f245
JH
1214 ret->author = author_buf;
1215 get_ac_line(commit->buffer, "\nauthor ",
1216 sizeof(author_buf), author_buf, &ret->author_mail,
1217 &ret->author_time, &ret->author_tz);
1218
1219 if (!detailed)
1220 return;
1221
1222 ret->committer = committer_buf;
1223 get_ac_line(commit->buffer, "\ncommitter ",
1224 sizeof(committer_buf), committer_buf, &ret->committer_mail,
1225 &ret->committer_time, &ret->committer_tz);
1226
1227 ret->summary = summary_buf;
1228 tmp = strstr(commit->buffer, "\n\n");
1229 if (!tmp) {
1230 error_out:
1231 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
1232 return;
1233 }
1234 tmp += 2;
1235 endp = strchr(tmp, '\n');
1236 if (!endp)
1237 goto error_out;
1238 len = endp - tmp;
1239 if (len >= sizeof(summary_buf))
1240 goto error_out;
1241 memcpy(summary_buf, tmp, len);
1242 summary_buf[len] = 0;
1243}
1244
1245#define OUTPUT_ANNOTATE_COMPAT 001
1246#define OUTPUT_LONG_OBJECT_NAME 002
1247#define OUTPUT_RAW_TIMESTAMP 004
1248#define OUTPUT_PORCELAIN 010
1249#define OUTPUT_SHOW_NAME 020
1250#define OUTPUT_SHOW_NUMBER 040
5ff62c30 1251#define OUTPUT_SHOW_SCORE 0100
cee7f245
JH
1252
1253static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
1254{
1255 int cnt;
1256 const char *cp;
1257 struct origin *suspect = ent->suspect;
1258 char hex[41];
1259
1260 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1261 printf("%s%c%d %d %d\n",
1262 hex,
1263 ent->guilty ? ' ' : '*', // purely for debugging
1264 ent->s_lno + 1,
1265 ent->lno + 1,
1266 ent->num_lines);
1267 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1268 struct commit_info ci;
1269 suspect->commit->object.flags |= METAINFO_SHOWN;
1270 get_commit_info(suspect->commit, &ci, 1);
1271 printf("author %s\n", ci.author);
1272 printf("author-mail %s\n", ci.author_mail);
1273 printf("author-time %lu\n", ci.author_time);
1274 printf("author-tz %s\n", ci.author_tz);
1275 printf("committer %s\n", ci.committer);
1276 printf("committer-mail %s\n", ci.committer_mail);
1277 printf("committer-time %lu\n", ci.committer_time);
1278 printf("committer-tz %s\n", ci.committer_tz);
1279 printf("filename %s\n", suspect->path);
1280 printf("summary %s\n", ci.summary);
b11121d9
JH
1281 if (suspect->commit->object.flags & UNINTERESTING)
1282 printf("boundary\n");
cee7f245
JH
1283 }
1284 else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
1285 printf("filename %s\n", suspect->path);
1286
1287 cp = nth_line(sb, ent->lno);
1288 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1289 char ch;
1290 if (cnt)
1291 printf("%s %d %d\n", hex,
1292 ent->s_lno + 1 + cnt,
1293 ent->lno + 1 + cnt);
1294 putchar('\t');
1295 do {
1296 ch = *cp++;
1297 putchar(ch);
1298 } while (ch != '\n' &&
1299 cp < sb->final_buf + sb->final_buf_size);
1300 }
1301}
1302
1303static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1304{
1305 int cnt;
1306 const char *cp;
1307 struct origin *suspect = ent->suspect;
1308 struct commit_info ci;
1309 char hex[41];
1310 int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1311
1312 get_commit_info(suspect->commit, &ci, 1);
1313 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1314
1315 cp = nth_line(sb, ent->lno);
1316 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1317 char ch;
b11121d9
JH
1318 int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8;
1319
1320 if (suspect->commit->object.flags & UNINTERESTING) {
1321 length--;
1322 putchar('^');
1323 }
cee7f245 1324
b11121d9 1325 printf("%.*s", length, hex);
cee7f245
JH
1326 if (opt & OUTPUT_ANNOTATE_COMPAT)
1327 printf("\t(%10s\t%10s\t%d)", ci.author,
1328 format_time(ci.author_time, ci.author_tz,
1329 show_raw_time),
1330 ent->lno + 1 + cnt);
1331 else {
5ff62c30 1332 if (opt & OUTPUT_SHOW_SCORE)
54a4c617
JH
1333 printf(" %*d %02d",
1334 max_score_digits, ent->score,
1335 ent->suspect->refcnt);
cee7f245
JH
1336 if (opt & OUTPUT_SHOW_NAME)
1337 printf(" %-*.*s", longest_file, longest_file,
1338 suspect->path);
1339 if (opt & OUTPUT_SHOW_NUMBER)
1340 printf(" %*d", max_orig_digits,
1341 ent->s_lno + 1 + cnt);
1342 printf(" (%-*.*s %10s %*d) ",
1343 longest_author, longest_author, ci.author,
1344 format_time(ci.author_time, ci.author_tz,
1345 show_raw_time),
1346 max_digits, ent->lno + 1 + cnt);
1347 }
1348 do {
1349 ch = *cp++;
1350 putchar(ch);
1351 } while (ch != '\n' &&
1352 cp < sb->final_buf + sb->final_buf_size);
1353 }
1354}
1355
1356static void output(struct scoreboard *sb, int option)
1357{
1358 struct blame_entry *ent;
1359
1360 if (option & OUTPUT_PORCELAIN) {
1361 for (ent = sb->ent; ent; ent = ent->next) {
1362 struct blame_entry *oth;
1363 struct origin *suspect = ent->suspect;
1364 struct commit *commit = suspect->commit;
1365 if (commit->object.flags & MORE_THAN_ONE_PATH)
1366 continue;
1367 for (oth = ent->next; oth; oth = oth->next) {
1368 if ((oth->suspect->commit != commit) ||
1369 !strcmp(oth->suspect->path, suspect->path))
1370 continue;
1371 commit->object.flags |= MORE_THAN_ONE_PATH;
1372 break;
1373 }
1374 }
1375 }
1376
1377 for (ent = sb->ent; ent; ent = ent->next) {
1378 if (option & OUTPUT_PORCELAIN)
1379 emit_porcelain(sb, ent);
5ff62c30 1380 else {
cee7f245 1381 emit_other(sb, ent, option);
5ff62c30 1382 }
cee7f245
JH
1383 }
1384}
1385
1386static int prepare_lines(struct scoreboard *sb)
1387{
1388 const char *buf = sb->final_buf;
1389 unsigned long len = sb->final_buf_size;
1390 int num = 0, incomplete = 0, bol = 1;
1391
1392 if (len && buf[len-1] != '\n')
1393 incomplete++; /* incomplete line at the end */
1394 while (len--) {
1395 if (bol) {
1396 sb->lineno = xrealloc(sb->lineno,
1397 sizeof(int* ) * (num + 1));
1398 sb->lineno[num] = buf - sb->final_buf;
1399 bol = 0;
1400 }
1401 if (*buf++ == '\n') {
1402 num++;
1403 bol = 1;
1404 }
1405 }
1ca6ca87
JH
1406 sb->lineno = xrealloc(sb->lineno,
1407 sizeof(int* ) * (num + incomplete + 1));
1408 sb->lineno[num + incomplete] = buf - sb->final_buf;
cee7f245
JH
1409 sb->num_lines = num + incomplete;
1410 return sb->num_lines;
1411}
1412
1413static int read_ancestry(const char *graft_file)
1414{
1415 FILE *fp = fopen(graft_file, "r");
1416 char buf[1024];
1417 if (!fp)
1418 return -1;
1419 while (fgets(buf, sizeof(buf), fp)) {
1420 /* The format is just "Commit Parent1 Parent2 ...\n" */
1421 int len = strlen(buf);
1422 struct commit_graft *graft = read_graft_line(buf, len);
8eaf7986
JH
1423 if (graft)
1424 register_commit_graft(graft, 0);
cee7f245
JH
1425 }
1426 fclose(fp);
1427 return 0;
1428}
1429
1430static int lineno_width(int lines)
1431{
1432 int i, width;
1433
1434 for (width = 1, i = 10; i <= lines + 1; width++)
1435 i *= 10;
1436 return width;
1437}
1438
1439static void find_alignment(struct scoreboard *sb, int *option)
1440{
1441 int longest_src_lines = 0;
1442 int longest_dst_lines = 0;
5ff62c30 1443 unsigned largest_score = 0;
cee7f245
JH
1444 struct blame_entry *e;
1445
1446 for (e = sb->ent; e; e = e->next) {
1447 struct origin *suspect = e->suspect;
1448 struct commit_info ci;
1449 int num;
1450
ab3bb800
JH
1451 if (strcmp(suspect->path, sb->path))
1452 *option |= OUTPUT_SHOW_NAME;
1453 num = strlen(suspect->path);
1454 if (longest_file < num)
1455 longest_file = num;
cee7f245
JH
1456 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1457 suspect->commit->object.flags |= METAINFO_SHOWN;
1458 get_commit_info(suspect->commit, &ci, 1);
cee7f245
JH
1459 num = strlen(ci.author);
1460 if (longest_author < num)
1461 longest_author = num;
1462 }
1463 num = e->s_lno + e->num_lines;
1464 if (longest_src_lines < num)
1465 longest_src_lines = num;
1466 num = e->lno + e->num_lines;
1467 if (longest_dst_lines < num)
1468 longest_dst_lines = num;
5ff62c30
JH
1469 if (largest_score < ent_score(sb, e))
1470 largest_score = ent_score(sb, e);
cee7f245
JH
1471 }
1472 max_orig_digits = lineno_width(longest_src_lines);
1473 max_digits = lineno_width(longest_dst_lines);
5ff62c30 1474 max_score_digits = lineno_width(largest_score);
cee7f245
JH
1475}
1476
54a4c617
JH
1477static void sanity_check_refcnt(struct scoreboard *sb)
1478{
1479 int baa = 0;
1480 struct blame_entry *ent;
1481
1482 for (ent = sb->ent; ent; ent = ent->next) {
ae86ad65 1483 /* Nobody should have zero or negative refcnt */
854b97f6
JH
1484 if (ent->suspect->refcnt <= 0) {
1485 fprintf(stderr, "%s in %s has negative refcnt %d\n",
1486 ent->suspect->path,
1487 sha1_to_hex(ent->suspect->commit->object.sha1),
1488 ent->suspect->refcnt);
ae86ad65 1489 baa = 1;
854b97f6 1490 }
ae86ad65
JH
1491 }
1492 for (ent = sb->ent; ent; ent = ent->next) {
1493 /* Mark the ones that haven't been checked */
54a4c617
JH
1494 if (0 < ent->suspect->refcnt)
1495 ent->suspect->refcnt = -ent->suspect->refcnt;
54a4c617
JH
1496 }
1497 for (ent = sb->ent; ent; ent = ent->next) {
0d981c67 1498 /* then pick each and see if they have the the correct
854b97f6 1499 * refcnt.
54a4c617
JH
1500 */
1501 int found;
1502 struct blame_entry *e;
1503 struct origin *suspect = ent->suspect;
1504
1505 if (0 < suspect->refcnt)
1506 continue;
ae86ad65 1507 suspect->refcnt = -suspect->refcnt; /* Unmark */
54a4c617
JH
1508 for (found = 0, e = sb->ent; e; e = e->next) {
1509 if (e->suspect != suspect)
1510 continue;
1511 found++;
1512 }
854b97f6
JH
1513 if (suspect->refcnt != found) {
1514 fprintf(stderr, "%s in %s has refcnt %d, not %d\n",
1515 ent->suspect->path,
1516 sha1_to_hex(ent->suspect->commit->object.sha1),
1517 ent->suspect->refcnt, found);
1518 baa = 2;
1519 }
54a4c617
JH
1520 }
1521 if (baa) {
1522 int opt = 0160;
1523 find_alignment(sb, &opt);
1524 output(sb, opt);
854b97f6 1525 die("Baa %d!", baa);
54a4c617
JH
1526 }
1527}
1528
cee7f245
JH
1529static int has_path_in_work_tree(const char *path)
1530{
1531 struct stat st;
1532 return !lstat(path, &st);
1533}
1534
4a0fc95f
JH
1535static unsigned parse_score(const char *arg)
1536{
1537 char *end;
1538 unsigned long score = strtoul(arg, &end, 10);
1539 if (*end)
1540 return 0;
1541 return score;
1542}
1543
20239bae
JK
1544static const char *add_prefix(const char *prefix, const char *path)
1545{
1546 if (!prefix || !prefix[0])
1547 return path;
1548 return prefix_path(prefix, strlen(prefix), path);
1549}
1550
931233bc
JH
1551static const char *parse_loc(const char *spec,
1552 struct scoreboard *sb, long lno,
1553 long begin, long *ret)
1554{
1555 char *term;
1556 const char *line;
1557 long num;
1558 int reg_error;
1559 regex_t regexp;
1560 regmatch_t match[1];
1561
7bd9641d
JH
1562 /* Allow "-L <something>,+20" to mean starting at <something>
1563 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
1564 * <something>.
1565 */
1566 if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
1567 num = strtol(spec + 1, &term, 10);
1568 if (term != spec + 1) {
1569 if (spec[0] == '-')
1570 num = 0 - num;
1571 if (0 < num)
1572 *ret = begin + num - 2;
1573 else if (!num)
1574 *ret = begin;
1575 else
1576 *ret = begin + num;
1577 return term;
1578 }
1579 return spec;
1580 }
931233bc
JH
1581 num = strtol(spec, &term, 10);
1582 if (term != spec) {
1583 *ret = num;
1584 return term;
1585 }
1586 if (spec[0] != '/')
1587 return spec;
1588
1589 /* it could be a regexp of form /.../ */
1590 for (term = (char*) spec + 1; *term && *term != '/'; term++) {
1591 if (*term == '\\')
1592 term++;
1593 }
1594 if (*term != '/')
1595 return spec;
1596
1597 /* try [spec+1 .. term-1] as regexp */
1598 *term = 0;
1599 begin--; /* input is in human terms */
1600 line = nth_line(sb, begin);
1601
1602 if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
1603 !(reg_error = regexec(&regexp, line, 1, match, 0))) {
1604 const char *cp = line + match[0].rm_so;
1605 const char *nline;
1606
1607 while (begin++ < lno) {
1608 nline = nth_line(sb, begin);
1609 if (line <= cp && cp < nline)
1610 break;
1611 line = nline;
1612 }
1613 *ret = begin;
1614 regfree(&regexp);
1615 *term++ = '/';
1616 return term;
1617 }
1618 else {
1619 char errbuf[1024];
1620 regerror(reg_error, &regexp, errbuf, 1024);
1621 die("-L parameter '%s': %s", spec + 1, errbuf);
1622 }
1623}
1624
1625static void prepare_blame_range(struct scoreboard *sb,
1626 const char *bottomtop,
1627 long lno,
1628 long *bottom, long *top)
1629{
1630 const char *term;
1631
1632 term = parse_loc(bottomtop, sb, lno, 1, bottom);
1633 if (*term == ',') {
1634 term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
1635 if (*term)
acca687f 1636 usage(blame_usage);
931233bc
JH
1637 }
1638 if (*term)
acca687f 1639 usage(blame_usage);
931233bc
JH
1640}
1641
acca687f 1642int cmd_blame(int argc, const char **argv, const char *prefix)
cee7f245
JH
1643{
1644 struct rev_info revs;
1645 const char *path;
1646 struct scoreboard sb;
1647 struct origin *o;
1648 struct blame_entry *ent;
d24bba80 1649 int i, seen_dashdash, unk, opt;
cee7f245
JH
1650 long bottom, top, lno;
1651 int output_option = 0;
1652 const char *revs_file = NULL;
1653 const char *final_commit_name = NULL;
1654 char type[10];
931233bc 1655 const char *bottomtop = NULL;
cee7f245 1656
612702e8
JH
1657 save_commit_buffer = 0;
1658
d24bba80 1659 opt = 0;
cee7f245
JH
1660 seen_dashdash = 0;
1661 for (unk = i = 1; i < argc; i++) {
1662 const char *arg = argv[i];
1663 if (*arg != '-')
1664 break;
1665 else if (!strcmp("-c", arg))
1666 output_option |= OUTPUT_ANNOTATE_COMPAT;
1667 else if (!strcmp("-t", arg))
1668 output_option |= OUTPUT_RAW_TIMESTAMP;
1669 else if (!strcmp("-l", arg))
1670 output_option |= OUTPUT_LONG_OBJECT_NAME;
1671 else if (!strcmp("-S", arg) && ++i < argc)
1672 revs_file = argv[i];
4a0fc95f 1673 else if (!strncmp("-M", arg, 2)) {
d24bba80 1674 opt |= PICKAXE_BLAME_MOVE;
4a0fc95f
JH
1675 blame_move_score = parse_score(arg+2);
1676 }
1677 else if (!strncmp("-C", arg, 2)) {
18abd745
JH
1678 if (opt & PICKAXE_BLAME_COPY)
1679 opt |= PICKAXE_BLAME_COPY_HARDER;
1680 opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
4a0fc95f 1681 blame_copy_score = parse_score(arg+2);
18abd745 1682 }
2c40f984 1683 else if (!strncmp("-L", arg, 2)) {
2c40f984
JH
1684 if (!arg[2]) {
1685 if (++i >= argc)
acca687f 1686 usage(blame_usage);
2c40f984
JH
1687 arg = argv[i];
1688 }
1689 else
1690 arg += 2;
931233bc 1691 if (bottomtop)
cee7f245 1692 die("More than one '-L n,m' option given");
931233bc 1693 bottomtop = arg;
cee7f245 1694 }
5ff62c30
JH
1695 else if (!strcmp("--score-debug", arg))
1696 output_option |= OUTPUT_SHOW_SCORE;
cee7f245
JH
1697 else if (!strcmp("-f", arg) ||
1698 !strcmp("--show-name", arg))
1699 output_option |= OUTPUT_SHOW_NAME;
1700 else if (!strcmp("-n", arg) ||
1701 !strcmp("--show-number", arg))
1702 output_option |= OUTPUT_SHOW_NUMBER;
1703 else if (!strcmp("-p", arg) ||
1704 !strcmp("--porcelain", arg))
1705 output_option |= OUTPUT_PORCELAIN;
1706 else if (!strcmp("--", arg)) {
1707 seen_dashdash = 1;
1708 i++;
1709 break;
1710 }
1711 else
1712 argv[unk++] = arg;
1713 }
1714
4a0fc95f
JH
1715 if (!blame_move_score)
1716 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
1717 if (!blame_copy_score)
1718 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
1719
cee7f245
JH
1720 /* We have collected options unknown to us in argv[1..unk]
1721 * which are to be passed to revision machinery if we are
1722 * going to do the "bottom" procesing.
1723 *
1724 * The remaining are:
1725 *
1726 * (1) if seen_dashdash, its either
1727 * "-options -- <path>" or
1728 * "-options -- <path> <rev>".
1729 * but the latter is allowed only if there is no
1730 * options that we passed to revision machinery.
1731 *
1732 * (2) otherwise, we may have "--" somewhere later and
1733 * might be looking at the first one of multiple 'rev'
1734 * parameters (e.g. " master ^next ^maint -- path").
1735 * See if there is a dashdash first, and give the
1736 * arguments before that to revision machinery.
1737 * After that there must be one 'path'.
1738 *
1739 * (3) otherwise, its one of the three:
1740 * "-options <path> <rev>"
1741 * "-options <rev> <path>"
1742 * "-options <path>"
1743 * but again the first one is allowed only if
1744 * there is no options that we passed to revision
1745 * machinery.
1746 */
1747
1748 if (seen_dashdash) {
1749 /* (1) */
1750 if (argc <= i)
acca687f 1751 usage(blame_usage);
20239bae 1752 path = add_prefix(prefix, argv[i]);
cee7f245
JH
1753 if (i + 1 == argc - 1) {
1754 if (unk != 1)
acca687f 1755 usage(blame_usage);
cee7f245
JH
1756 argv[unk++] = argv[i + 1];
1757 }
1758 else if (i + 1 != argc)
1759 /* garbage at end */
acca687f 1760 usage(blame_usage);
cee7f245
JH
1761 }
1762 else {
1763 int j;
1764 for (j = i; !seen_dashdash && j < argc; j++)
1765 if (!strcmp(argv[j], "--"))
1766 seen_dashdash = j;
1767 if (seen_dashdash) {
1768 if (seen_dashdash + 1 != argc - 1)
acca687f 1769 usage(blame_usage);
20239bae 1770 path = add_prefix(prefix, argv[seen_dashdash + 1]);
cee7f245
JH
1771 for (j = i; j < seen_dashdash; j++)
1772 argv[unk++] = argv[j];
1773 }
1774 else {
1775 /* (3) */
20239bae 1776 path = add_prefix(prefix, argv[i]);
cee7f245
JH
1777 if (i + 1 == argc - 1) {
1778 final_commit_name = argv[i + 1];
1779
1780 /* if (unk == 1) we could be getting
1781 * old-style
1782 */
1783 if (unk == 1 && !has_path_in_work_tree(path)) {
20239bae 1784 path = add_prefix(prefix, argv[i + 1]);
cee7f245
JH
1785 final_commit_name = argv[i];
1786 }
1787 }
1788 else if (i != argc - 1)
acca687f 1789 usage(blame_usage); /* garbage at end */
cee7f245
JH
1790
1791 if (!has_path_in_work_tree(path))
1792 die("cannot stat path %s: %s",
1793 path, strerror(errno));
1794 }
1795 }
1796
1797 if (final_commit_name)
1798 argv[unk++] = final_commit_name;
1799
1800 /* Now we got rev and path. We do not want the path pruning
1801 * but we may want "bottom" processing.
1802 */
6bee4e40 1803 argv[unk++] = "--"; /* terminate the rev name */
cee7f245
JH
1804 argv[unk] = NULL;
1805
1806 init_revisions(&revs, NULL);
1807 setup_revisions(unk, argv, &revs, "HEAD");
1808 memset(&sb, 0, sizeof(sb));
1809
1810 /* There must be one and only one positive commit in the
1811 * revs->pending array.
1812 */
1813 for (i = 0; i < revs.pending.nr; i++) {
1814 struct object *obj = revs.pending.objects[i].item;
1815 if (obj->flags & UNINTERESTING)
1816 continue;
1817 while (obj->type == OBJ_TAG)
1818 obj = deref_tag(obj, NULL, 0);
1819 if (obj->type != OBJ_COMMIT)
1820 die("Non commit %s?",
1821 revs.pending.objects[i].name);
1822 if (sb.final)
1823 die("More than one commit to dig from %s and %s?",
1824 revs.pending.objects[i].name,
1825 final_commit_name);
1826 sb.final = (struct commit *) obj;
1827 final_commit_name = revs.pending.objects[i].name;
1828 }
1829
1830 if (!sb.final) {
1831 /* "--not A B -- path" without anything positive */
1832 unsigned char head_sha1[20];
1833
1834 final_commit_name = "HEAD";
1835 if (get_sha1(final_commit_name, head_sha1))
1836 die("No such ref: HEAD");
1837 sb.final = lookup_commit_reference(head_sha1);
1838 add_pending_object(&revs, &(sb.final->object), "HEAD");
1839 }
1840
1841 /* If we have bottom, this will mark the ancestors of the
1842 * bottom commits we would reach while traversing as
1843 * uninteresting.
1844 */
1845 prepare_revision_walk(&revs);
1846
f6c0e191
JH
1847 o = get_origin(&sb, sb.final, path);
1848 if (fill_blob_sha1(o))
cee7f245
JH
1849 die("no such path %s in %s", path, final_commit_name);
1850
1851 sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
c2e525d9 1852 num_read_blob++;
cee7f245
JH
1853 lno = prepare_lines(&sb);
1854
931233bc
JH
1855 bottom = top = 0;
1856 if (bottomtop)
1857 prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);
1858 if (bottom && top && top < bottom) {
1859 long tmp;
1860 tmp = top; top = bottom; bottom = tmp;
1861 }
cee7f245
JH
1862 if (bottom < 1)
1863 bottom = 1;
1864 if (top < 1)
1865 top = lno;
1866 bottom--;
1867 if (lno < top)
1868 die("file %s has only %lu lines", path, lno);
1869
1870 ent = xcalloc(1, sizeof(*ent));
1871 ent->lno = bottom;
1872 ent->num_lines = top - bottom;
1873 ent->suspect = o;
1874 ent->s_lno = bottom;
1875
1876 sb.ent = ent;
1877 sb.path = path;
1878
1879 if (revs_file && read_ancestry(revs_file))
1880 die("reading graft file %s failed: %s",
1881 revs_file, strerror(errno));
1882
d24bba80 1883 assign_blame(&sb, &revs, opt);
cee7f245
JH
1884
1885 coalesce(&sb);
1886
1887 if (!(output_option & OUTPUT_PORCELAIN))
1888 find_alignment(&sb, &output_option);
1889
1890 output(&sb, output_option);
1891 free((void *)sb.final_buf);
1892 for (ent = sb.ent; ent; ) {
1893 struct blame_entry *e = ent->next;
1894 free(ent);
1895 ent = e;
1896 }
c2e525d9
JH
1897
1898 if (DEBUG) {
1899 printf("num read blob: %d\n", num_read_blob);
1900 printf("num get patch: %d\n", num_get_patch);
1901 printf("num commits: %d\n", num_commits);
1902 }
cee7f245
JH
1903 return 0;
1904}