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