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