git-pickaxe: improve "best match" heuristics
[git/git.git] / builtin-pickaxe.c
CommitLineData
cee7f245
JH
1/*
2 * Pickaxe
3 *
4 * Copyright (c) 2006, Junio C Hamano
5 */
6
7#include "cache.h"
8#include "builtin.h"
9#include "blob.h"
10#include "commit.h"
11#include "tag.h"
12#include "tree-walk.h"
13#include "diff.h"
14#include "diffcore.h"
15#include "revision.h"
16#include "xdiff-interface.h"
17
18#include <time.h>
19#include <sys/time.h>
20
21static char pickaxe_usage[] =
18abd745 22"git-pickaxe [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n"
cee7f245
JH
23" -c, --compatibility Use the same output mode as git-annotate (Default: off)\n"
24" -l, --long Show long commit SHA1 (Default: off)\n"
25" -t, --time Show raw timestamp (Default: off)\n"
26" -f, --show-name Show original filename (Default: auto)\n"
27" -n, --show-number Show original linenumber (Default: off)\n"
28" -p, --porcelain Show in a format designed for machine consumption\n"
29" -L n,m Process only line range n,m, counting from 1\n"
18abd745 30" -M, -C Find line movements within and across files\n"
cee7f245
JH
31" -S revs-file Use revisions from revs-file instead of calling git-rev-list\n";
32
33static int longest_file;
34static int longest_author;
35static int max_orig_digits;
36static int max_digits;
5ff62c30 37static int max_score_digits;
cee7f245 38
d24bba80 39#define PICKAXE_BLAME_MOVE 01
18abd745
JH
40#define PICKAXE_BLAME_COPY 02
41#define PICKAXE_BLAME_COPY_HARDER 04
d24bba80 42
cee7f245
JH
43/* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
44#define METAINFO_SHOWN (1u<<12)
45#define MORE_THAN_ONE_PATH (1u<<13)
46
47/*
48 * One blob in a commit
49 */
50struct origin {
51 struct commit *commit;
52 unsigned char blob_sha1[20];
53 char path[FLEX_ARRAY];
54};
55
56struct blame_entry {
57 struct blame_entry *prev;
58 struct blame_entry *next;
59
60 /* the first line of this group in the final image;
61 * internally all line numbers are 0 based.
62 */
63 int lno;
64
65 /* how many lines this group has */
66 int num_lines;
67
68 /* the commit that introduced this group into the final image */
69 struct origin *suspect;
70
71 /* true if the suspect is truly guilty; false while we have not
72 * checked if the group came from one of its parents.
73 */
74 char guilty;
75
76 /* the line number of the first line of this group in the
77 * suspect's file; internally all line numbers are 0 based.
78 */
79 int s_lno;
5ff62c30
JH
80
81 /* how significant this entry is -- cached to avoid
82 * scanning the lines over and over
83 */
84 unsigned score;
cee7f245
JH
85};
86
87struct scoreboard {
88 /* the final commit (i.e. where we started digging from) */
89 struct commit *final;
90
91 const char *path;
92
93 /* the contents in the final; pointed into by buf pointers of
94 * blame_entries
95 */
96 const char *final_buf;
97 unsigned long final_buf_size;
98
99 /* linked list of blames */
100 struct blame_entry *ent;
101
102 int num_lines;
103 int *lineno;
104};
105
106static void coalesce(struct scoreboard *sb)
107{
108 struct blame_entry *ent, *next;
109
110 for (ent = sb->ent; ent && (next = ent->next); ent = next) {
111 if (ent->suspect == next->suspect &&
112 ent->guilty == next->guilty &&
113 ent->s_lno + ent->num_lines == next->s_lno) {
114 ent->num_lines += next->num_lines;
115 ent->next = next->next;
116 if (ent->next)
117 ent->next->prev = ent;
118 free(next);
119 next = ent; /* again */
120 }
121 }
122}
123
124static void free_origin(struct origin *o)
125{
126 free(o);
127}
128
129static struct origin *find_origin(struct scoreboard *sb,
130 struct commit *commit,
131 const char *path)
132{
133 struct blame_entry *ent;
134 struct origin *o;
135 unsigned mode;
136 char type[10];
137
138 for (ent = sb->ent; ent; ent = ent->next) {
139 if (ent->suspect->commit == commit &&
140 !strcmp(ent->suspect->path, path))
141 return ent->suspect;
142 }
143
144 o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
145 o->commit = commit;
146 strcpy(o->path, path);
147 if (get_tree_entry(commit->object.sha1, path, o->blob_sha1, &mode))
148 goto err_out;
149 if (sha1_object_info(o->blob_sha1, type, NULL) ||
150 strcmp(type, blob_type))
151 goto err_out;
152 return o;
153 err_out:
154 free_origin(o);
155 return NULL;
156}
157
158static struct origin *find_rename(struct scoreboard *sb,
159 struct commit *parent,
160 struct origin *origin)
161{
162 struct origin *porigin = NULL;
163 struct diff_options diff_opts;
164 int i;
165 const char *paths[1];
166
167 diff_setup(&diff_opts);
168 diff_opts.recursive = 1;
169 diff_opts.detect_rename = DIFF_DETECT_RENAME;
170 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
171 paths[0] = NULL;
172 diff_tree_setup_paths(paths, &diff_opts);
173 if (diff_setup_done(&diff_opts) < 0)
174 die("diff-setup");
175 diff_tree_sha1(origin->commit->tree->object.sha1,
176 parent->tree->object.sha1,
177 "", &diff_opts);
178 diffcore_std(&diff_opts);
179
180 for (i = 0; i < diff_queued_diff.nr; i++) {
181 struct diff_filepair *p = diff_queued_diff.queue[i];
182 if (p->status == 'R' && !strcmp(p->one->path, origin->path)) {
183 porigin = find_origin(sb, parent, p->two->path);
184 break;
185 }
186 }
187 diff_flush(&diff_opts);
188 return porigin;
189}
190
191struct chunk {
192 /* line number in postimage; up to but not including this
193 * line is the same as preimage
194 */
195 int same;
196
197 /* preimage line number after this chunk */
198 int p_next;
199
200 /* postimage line number after this chunk */
201 int t_next;
202};
203
204struct patch {
205 struct chunk *chunks;
206 int num;
207};
208
209struct blame_diff_state {
210 struct xdiff_emit_state xm;
211 struct patch *ret;
212 unsigned hunk_post_context;
213 unsigned hunk_in_pre_context : 1;
214};
215
216static void process_u_diff(void *state_, char *line, unsigned long len)
217{
218 struct blame_diff_state *state = state_;
219 struct chunk *chunk;
220 int off1, off2, len1, len2, num;
221
cee7f245
JH
222 num = state->ret->num;
223 if (len < 4 || line[0] != '@' || line[1] != '@') {
224 if (state->hunk_in_pre_context && line[0] == ' ')
225 state->ret->chunks[num - 1].same++;
226 else {
227 state->hunk_in_pre_context = 0;
228 if (line[0] == ' ')
229 state->hunk_post_context++;
230 else
231 state->hunk_post_context = 0;
232 }
233 return;
234 }
235
236 if (num && state->hunk_post_context) {
237 chunk = &state->ret->chunks[num - 1];
238 chunk->p_next -= state->hunk_post_context;
239 chunk->t_next -= state->hunk_post_context;
240 }
241 state->ret->num = ++num;
242 state->ret->chunks = xrealloc(state->ret->chunks,
243 sizeof(struct chunk) * num);
244 chunk = &state->ret->chunks[num - 1];
245 if (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {
246 state->ret->num--;
247 return;
248 }
249
250 /* Line numbers in patch output are one based. */
251 off1--;
252 off2--;
253
254 chunk->same = len2 ? off2 : (off2 + 1);
255
256 chunk->p_next = off1 + (len1 ? len1 : 1);
257 chunk->t_next = chunk->same + len2;
258 state->hunk_in_pre_context = 1;
259 state->hunk_post_context = 0;
260}
261
262static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
263 int context)
264{
265 struct blame_diff_state state;
266 xpparam_t xpp;
267 xdemitconf_t xecfg;
268 xdemitcb_t ecb;
269
270 xpp.flags = XDF_NEED_MINIMAL;
271 xecfg.ctxlen = context;
272 xecfg.flags = 0;
273 ecb.outf = xdiff_outf;
274 ecb.priv = &state;
275 memset(&state, 0, sizeof(state));
276 state.xm.consume = process_u_diff;
277 state.ret = xmalloc(sizeof(struct patch));
278 state.ret->chunks = NULL;
279 state.ret->num = 0;
280
281 xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);
282
283 if (state.ret->num) {
284 struct chunk *chunk;
285 chunk = &state.ret->chunks[state.ret->num - 1];
286 chunk->p_next -= state.hunk_post_context;
287 chunk->t_next -= state.hunk_post_context;
288 }
289 return state.ret;
290}
291
292static struct patch *get_patch(struct origin *parent, struct origin *origin)
293{
294 mmfile_t file_p, file_o;
295 char type[10];
296 char *blob_p, *blob_o;
297 struct patch *patch;
298
cee7f245
JH
299 blob_p = read_sha1_file(parent->blob_sha1, type,
300 (unsigned long *) &file_p.size);
301 blob_o = read_sha1_file(origin->blob_sha1, type,
302 (unsigned long *) &file_o.size);
303 file_p.ptr = blob_p;
304 file_o.ptr = blob_o;
305 if (!file_p.ptr || !file_o.ptr) {
306 free(blob_p);
307 free(blob_o);
308 return NULL;
309 }
310
311 patch = compare_buffer(&file_p, &file_o, 0);
312 free(blob_p);
313 free(blob_o);
314 return patch;
315}
316
317static void free_patch(struct patch *p)
318{
319 free(p->chunks);
320 free(p);
321}
322
323static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
324{
325 struct blame_entry *ent, *prev = NULL;
326
327 for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
328 prev = ent;
329
330 /* prev, if not NULL, is the last one that is below e */
331 e->prev = prev;
332 if (prev) {
333 e->next = prev->next;
334 prev->next = e;
335 }
336 else {
337 e->next = sb->ent;
338 sb->ent = e;
339 }
340 if (e->next)
341 e->next->prev = e;
342}
343
344static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
345{
346 struct blame_entry *p, *n;
347 p = dst->prev;
348 n = dst->next;
349 memcpy(dst, src, sizeof(*src));
350 dst->prev = p;
351 dst->next = n;
5ff62c30 352 dst->score = 0;
cee7f245
JH
353}
354
355static const char *nth_line(struct scoreboard *sb, int lno)
356{
357 return sb->final_buf + sb->lineno[lno];
358}
359
360static void split_overlap(struct blame_entry split[3],
361 struct blame_entry *e,
362 int tlno, int plno, int same,
363 struct origin *parent)
364{
365 /* it is known that lines between tlno to same came from
366 * parent, and e has an overlap with that range. it also is
367 * known that parent's line plno corresponds to e's line tlno.
368 *
369 * <---- e ----->
370 * <------>
371 * <------------>
372 * <------------>
373 * <------------------>
374 *
375 * Potentially we need to split e into three parts; before
376 * this chunk, the chunk to be blamed for parent, and after
377 * that portion.
378 */
379 int chunk_end_lno;
380 memset(split, 0, sizeof(struct blame_entry [3]));
381
382 if (e->s_lno < tlno) {
383 /* there is a pre-chunk part not blamed on parent */
384 split[0].suspect = e->suspect;
385 split[0].lno = e->lno;
386 split[0].s_lno = e->s_lno;
387 split[0].num_lines = tlno - e->s_lno;
388 split[1].lno = e->lno + tlno - e->s_lno;
389 split[1].s_lno = plno;
390 }
391 else {
392 split[1].lno = e->lno;
393 split[1].s_lno = plno + (e->s_lno - tlno);
394 }
395
396 if (same < e->s_lno + e->num_lines) {
397 /* there is a post-chunk part not blamed on parent */
398 split[2].suspect = e->suspect;
399 split[2].lno = e->lno + (same - e->s_lno);
400 split[2].s_lno = e->s_lno + (same - e->s_lno);
401 split[2].num_lines = e->s_lno + e->num_lines - same;
402 chunk_end_lno = split[2].lno;
403 }
404 else
405 chunk_end_lno = e->lno + e->num_lines;
406 split[1].num_lines = chunk_end_lno - split[1].lno;
407
408 if (split[1].num_lines < 1)
409 return;
410 split[1].suspect = parent;
411}
412
413static void split_blame(struct scoreboard *sb,
414 struct blame_entry split[3],
415 struct blame_entry *e)
416{
417 struct blame_entry *new_entry;
418
419 if (split[0].suspect && split[2].suspect) {
420 /* we need to split e into two and add another for parent */
421 dup_entry(e, &split[0]);
422
423 new_entry = xmalloc(sizeof(*new_entry));
424 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
425 add_blame_entry(sb, new_entry);
426
427 new_entry = xmalloc(sizeof(*new_entry));
428 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
429 add_blame_entry(sb, new_entry);
430 }
431 else if (!split[0].suspect && !split[2].suspect)
432 /* parent covers the entire area */
433 dup_entry(e, &split[1]);
434 else if (split[0].suspect) {
435 dup_entry(e, &split[0]);
436
437 new_entry = xmalloc(sizeof(*new_entry));
438 memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
439 add_blame_entry(sb, new_entry);
440 }
441 else {
442 dup_entry(e, &split[1]);
443
444 new_entry = xmalloc(sizeof(*new_entry));
445 memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
446 add_blame_entry(sb, new_entry);
447 }
448
5ff62c30 449 if (1) { /* sanity */
cee7f245
JH
450 struct blame_entry *ent;
451 int lno = 0, corrupt = 0;
452
453 for (ent = sb->ent; ent; ent = ent->next) {
454 if (lno != ent->lno)
455 corrupt = 1;
456 if (ent->s_lno < 0)
457 corrupt = 1;
458 lno += ent->num_lines;
459 }
460 if (corrupt) {
461 lno = 0;
462 for (ent = sb->ent; ent; ent = ent->next) {
463 printf("L %8d l %8d n %8d\n",
464 lno, ent->lno, ent->num_lines);
465 lno = ent->lno + ent->num_lines;
466 }
467 die("oops");
468 }
469 }
470}
471
472static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
473 int tlno, int plno, int same,
474 struct origin *parent)
475{
476 struct blame_entry split[3];
477
478 split_overlap(split, e, tlno, plno, same, parent);
479 if (!split[1].suspect)
480 return;
481 split_blame(sb, split, e);
482}
483
484static int find_last_in_target(struct scoreboard *sb, struct origin *target)
485{
486 struct blame_entry *e;
487 int last_in_target = -1;
488
489 for (e = sb->ent; e; e = e->next) {
490 if (e->guilty || e->suspect != target)
491 continue;
492 if (last_in_target < e->s_lno + e->num_lines)
493 last_in_target = e->s_lno + e->num_lines;
494 }
495 return last_in_target;
496}
497
498static void blame_chunk(struct scoreboard *sb,
499 int tlno, int plno, int same,
500 struct origin *target, struct origin *parent)
501{
502 struct blame_entry *e, *n;
503
504 for (e = sb->ent; e; e = n) {
505 n = e->next;
506 if (e->guilty || e->suspect != target)
507 continue;
508 if (same <= e->s_lno)
509 continue;
510 if (tlno < e->s_lno + e->num_lines)
511 blame_overlap(sb, e, tlno, plno, same, parent);
512 }
513}
514
515static int pass_blame_to_parent(struct scoreboard *sb,
516 struct origin *target,
517 struct origin *parent)
518{
519 int i, last_in_target, plno, tlno;
520 struct patch *patch;
521
522 last_in_target = find_last_in_target(sb, target);
523 if (last_in_target < 0)
524 return 1; /* nothing remains for this target */
525
526 patch = get_patch(parent, target);
527 plno = tlno = 0;
528 for (i = 0; i < patch->num; i++) {
529 struct chunk *chunk = &patch->chunks[i];
530
cee7f245
JH
531 blame_chunk(sb, tlno, plno, chunk->same, target, parent);
532 plno = chunk->p_next;
533 tlno = chunk->t_next;
534 }
535 /* rest (i.e. anything above tlno) are the same as parent */
536 blame_chunk(sb, tlno, plno, last_in_target, target, parent);
537
538 free_patch(patch);
539 return 0;
540}
541
5ff62c30
JH
542static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
543{
544 unsigned score;
545 const char *cp, *ep;
546
547 if (e->score)
548 return e->score;
549
550 score = 0;
551 cp = nth_line(sb, e->lno);
552 ep = nth_line(sb, e->lno + e->num_lines);
553 while (cp < ep) {
554 unsigned ch = *((unsigned char *)cp);
555 if (isalnum(ch))
556 score++;
557 cp++;
558 }
559 e->score = score;
560 return score;
561}
562
563static void copy_split_if_better(struct scoreboard *sb,
564 struct blame_entry best_so_far[3],
d24bba80
JH
565 struct blame_entry this[3])
566{
567 if (!this[1].suspect)
568 return;
5ff62c30
JH
569 if (best_so_far[1].suspect) {
570 if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
571 return;
572 }
d24bba80
JH
573 memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
574}
575
576static void find_copy_in_blob(struct scoreboard *sb,
577 struct blame_entry *ent,
578 struct origin *parent,
579 struct blame_entry split[3],
580 mmfile_t *file_p)
581{
582 const char *cp;
583 int cnt;
584 mmfile_t file_o;
585 struct patch *patch;
586 int i, plno, tlno;
587
588 cp = nth_line(sb, ent->lno);
589 file_o.ptr = (char*) cp;
590 cnt = ent->num_lines;
591
592 while (cnt && cp < sb->final_buf + sb->final_buf_size) {
593 if (*cp++ == '\n')
594 cnt--;
595 }
596 file_o.size = cp - file_o.ptr;
597
598 patch = compare_buffer(file_p, &file_o, 1);
599
600 memset(split, 0, sizeof(struct blame_entry [3]));
601 plno = tlno = 0;
602 for (i = 0; i < patch->num; i++) {
603 struct chunk *chunk = &patch->chunks[i];
604
605 /* tlno to chunk->same are the same as ent */
606 if (ent->num_lines <= tlno)
607 break;
608 if (tlno < chunk->same) {
609 struct blame_entry this[3];
610 split_overlap(this, ent,
611 tlno + ent->s_lno, plno,
612 chunk->same + ent->s_lno,
613 parent);
5ff62c30 614 copy_split_if_better(sb, split, this);
d24bba80
JH
615 }
616 plno = chunk->p_next;
617 tlno = chunk->t_next;
618 }
619 free_patch(patch);
620}
621
622static int find_move_in_parent(struct scoreboard *sb,
623 struct origin *target,
624 struct origin *parent)
625{
626 int last_in_target;
627 struct blame_entry *ent, split[3];
628 mmfile_t file_p;
629 char type[10];
630 char *blob_p;
631
632 last_in_target = find_last_in_target(sb, target);
633 if (last_in_target < 0)
634 return 1; /* nothing remains for this target */
635
636 blob_p = read_sha1_file(parent->blob_sha1, type,
637 (unsigned long *) &file_p.size);
638 file_p.ptr = blob_p;
639 if (!file_p.ptr) {
640 free(blob_p);
641 return 0;
642 }
643
644 for (ent = sb->ent; ent; ent = ent->next) {
645 if (ent->suspect != target || ent->guilty)
646 continue;
647 find_copy_in_blob(sb, ent, parent, split, &file_p);
648 if (split[1].suspect)
649 split_blame(sb, split, ent);
650 }
651 free(blob_p);
652 return 0;
653}
654
18abd745
JH
655static int find_copy_in_parent(struct scoreboard *sb,
656 struct origin *target,
657 struct commit *parent,
658 struct origin *porigin,
659 int opt)
660{
661 struct diff_options diff_opts;
662 const char *paths[1];
663 struct blame_entry *ent;
664 int i;
665
666 if (find_last_in_target(sb, target) < 0)
667 return 1; /* nothing remains for this target */
668
669 diff_setup(&diff_opts);
670 diff_opts.recursive = 1;
671 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
672
673 /* Try "find copies harder" on new path */
674 if ((opt & PICKAXE_BLAME_COPY_HARDER) &&
675 (!porigin || strcmp(target->path, porigin->path))) {
676 diff_opts.detect_rename = DIFF_DETECT_COPY;
677 diff_opts.find_copies_harder = 1;
678 }
679 paths[0] = NULL;
680 diff_tree_setup_paths(paths, &diff_opts);
681 if (diff_setup_done(&diff_opts) < 0)
682 die("diff-setup");
683 diff_tree_sha1(parent->tree->object.sha1,
684 target->commit->tree->object.sha1,
685 "", &diff_opts);
686 diffcore_std(&diff_opts);
687
688 for (ent = sb->ent; ent; ent = ent->next) {
689 struct blame_entry split[3];
690 if (ent->suspect != target || ent->guilty)
691 continue;
692
693 memset(split, 0, sizeof(split));
694 for (i = 0; i < diff_queued_diff.nr; i++) {
695 struct diff_filepair *p = diff_queued_diff.queue[i];
696 struct origin *norigin;
697 mmfile_t file_p;
698 char type[10];
699 char *blob;
700 struct blame_entry this[3];
701
702 if (!DIFF_FILE_VALID(p->one))
703 continue; /* does not exist in parent */
704 if (porigin && !strcmp(p->one->path, porigin->path))
705 /* find_move already dealt with this path */
706 continue;
707 norigin = find_origin(sb, parent, p->one->path);
708
709 blob = read_sha1_file(norigin->blob_sha1, type,
710 (unsigned long *) &file_p.size);
711 file_p.ptr = blob;
712 if (!file_p.ptr) {
713 free(blob);
714 continue;
715 }
716 find_copy_in_blob(sb, ent, norigin, this, &file_p);
5ff62c30 717 copy_split_if_better(sb, split, this);
18abd745
JH
718 }
719 if (split[1].suspect)
720 split_blame(sb, split, ent);
721 }
722 diff_flush(&diff_opts);
723
724 return 0;
725}
726
cee7f245
JH
727#define MAXPARENT 16
728
d24bba80 729static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
cee7f245
JH
730{
731 int i;
732 struct commit *commit = origin->commit;
733 struct commit_list *parent;
734 struct origin *parent_origin[MAXPARENT], *porigin;
735
736 memset(parent_origin, 0, sizeof(parent_origin));
737 for (i = 0, parent = commit->parents;
738 i < MAXPARENT && parent;
739 parent = parent->next, i++) {
740 struct commit *p = parent->item;
741
742 if (parse_commit(p))
743 continue;
744 porigin = find_origin(sb, parent->item, origin->path);
745 if (!porigin)
746 porigin = find_rename(sb, parent->item, origin);
747 if (!porigin)
748 continue;
749 if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
750 struct blame_entry *e;
751 for (e = sb->ent; e; e = e->next)
752 if (e->suspect == origin)
753 e->suspect = porigin;
754 /* now everything blamed for origin is blamed for
755 * porigin, we do not need to keep it anymore.
756 * Do not free porigin (or the ones we got from
757 * earlier round); they may still be used elsewhere.
758 */
759 free_origin(origin);
760 return;
761 }
762 parent_origin[i] = porigin;
763 }
764
765 for (i = 0, parent = commit->parents;
766 i < MAXPARENT && parent;
767 parent = parent->next, i++) {
768 struct origin *porigin = parent_origin[i];
769 if (!porigin)
770 continue;
771 if (pass_blame_to_parent(sb, origin, porigin))
772 return;
773 }
d24bba80
JH
774
775 /*
776 * Optionally run "miff" to find moves in parents' files here.
777 */
778 if (opt & PICKAXE_BLAME_MOVE)
779 for (i = 0, parent = commit->parents;
780 i < MAXPARENT && parent;
781 parent = parent->next, i++) {
782 struct origin *porigin = parent_origin[i];
783 if (!porigin)
784 continue;
785 if (find_move_in_parent(sb, origin, porigin))
786 return;
787 }
788
18abd745
JH
789 /*
790 * Optionally run "ciff" to find copies from parents' files here.
791 */
792 if (opt & PICKAXE_BLAME_COPY)
793 for (i = 0, parent = commit->parents;
794 i < MAXPARENT && parent;
795 parent = parent->next, i++) {
796 struct origin *porigin = parent_origin[i];
797 if (find_copy_in_parent(sb, origin, parent->item,
798 porigin, opt))
799 return;
800 }
cee7f245
JH
801}
802
d24bba80 803static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)
cee7f245
JH
804{
805 while (1) {
806 struct blame_entry *ent;
807 struct commit *commit;
808 struct origin *suspect = NULL;
809
810 /* find one suspect to break down */
811 for (ent = sb->ent; !suspect && ent; ent = ent->next)
812 if (!ent->guilty)
813 suspect = ent->suspect;
814 if (!suspect)
815 return; /* all done */
816
817 commit = suspect->commit;
818 parse_commit(commit);
819 if (!(commit->object.flags & UNINTERESTING) &&
820 !(revs->max_age != -1 && commit->date < revs->max_age))
d24bba80 821 pass_blame(sb, suspect, opt);
cee7f245
JH
822
823 /* Take responsibility for the remaining entries */
824 for (ent = sb->ent; ent; ent = ent->next)
825 if (ent->suspect == suspect)
826 ent->guilty = 1;
827 }
828}
829
830static const char *format_time(unsigned long time, const char *tz_str,
831 int show_raw_time)
832{
833 static char time_buf[128];
834 time_t t = time;
835 int minutes, tz;
836 struct tm *tm;
837
838 if (show_raw_time) {
839 sprintf(time_buf, "%lu %s", time, tz_str);
840 return time_buf;
841 }
842
843 tz = atoi(tz_str);
844 minutes = tz < 0 ? -tz : tz;
845 minutes = (minutes / 100)*60 + (minutes % 100);
846 minutes = tz < 0 ? -minutes : minutes;
847 t = time + minutes * 60;
848 tm = gmtime(&t);
849
850 strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
851 strcat(time_buf, tz_str);
852 return time_buf;
853}
854
855struct commit_info
856{
857 char *author;
858 char *author_mail;
859 unsigned long author_time;
860 char *author_tz;
861
862 /* filled only when asked for details */
863 char *committer;
864 char *committer_mail;
865 unsigned long committer_time;
866 char *committer_tz;
867
868 char *summary;
869};
870
871static void get_ac_line(const char *inbuf, const char *what,
872 int bufsz, char *person, char **mail,
873 unsigned long *time, char **tz)
874{
875 int len;
876 char *tmp, *endp;
877
878 tmp = strstr(inbuf, what);
879 if (!tmp)
880 goto error_out;
881 tmp += strlen(what);
882 endp = strchr(tmp, '\n');
883 if (!endp)
884 len = strlen(tmp);
885 else
886 len = endp - tmp;
887 if (bufsz <= len) {
888 error_out:
889 /* Ugh */
890 person = *mail = *tz = "(unknown)";
891 *time = 0;
892 return;
893 }
894 memcpy(person, tmp, len);
895
896 tmp = person;
897 tmp += len;
898 *tmp = 0;
899 while (*tmp != ' ')
900 tmp--;
901 *tz = tmp+1;
902
903 *tmp = 0;
904 while (*tmp != ' ')
905 tmp--;
906 *time = strtoul(tmp, NULL, 10);
907
908 *tmp = 0;
909 while (*tmp != ' ')
910 tmp--;
911 *mail = tmp + 1;
912 *tmp = 0;
913}
914
915static void get_commit_info(struct commit *commit,
916 struct commit_info *ret,
917 int detailed)
918{
919 int len;
920 char *tmp, *endp;
921 static char author_buf[1024];
922 static char committer_buf[1024];
923 static char summary_buf[1024];
924
925 ret->author = author_buf;
926 get_ac_line(commit->buffer, "\nauthor ",
927 sizeof(author_buf), author_buf, &ret->author_mail,
928 &ret->author_time, &ret->author_tz);
929
930 if (!detailed)
931 return;
932
933 ret->committer = committer_buf;
934 get_ac_line(commit->buffer, "\ncommitter ",
935 sizeof(committer_buf), committer_buf, &ret->committer_mail,
936 &ret->committer_time, &ret->committer_tz);
937
938 ret->summary = summary_buf;
939 tmp = strstr(commit->buffer, "\n\n");
940 if (!tmp) {
941 error_out:
942 sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1));
943 return;
944 }
945 tmp += 2;
946 endp = strchr(tmp, '\n');
947 if (!endp)
948 goto error_out;
949 len = endp - tmp;
950 if (len >= sizeof(summary_buf))
951 goto error_out;
952 memcpy(summary_buf, tmp, len);
953 summary_buf[len] = 0;
954}
955
956#define OUTPUT_ANNOTATE_COMPAT 001
957#define OUTPUT_LONG_OBJECT_NAME 002
958#define OUTPUT_RAW_TIMESTAMP 004
959#define OUTPUT_PORCELAIN 010
960#define OUTPUT_SHOW_NAME 020
961#define OUTPUT_SHOW_NUMBER 040
5ff62c30 962#define OUTPUT_SHOW_SCORE 0100
cee7f245
JH
963
964static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent)
965{
966 int cnt;
967 const char *cp;
968 struct origin *suspect = ent->suspect;
969 char hex[41];
970
971 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
972 printf("%s%c%d %d %d\n",
973 hex,
974 ent->guilty ? ' ' : '*', // purely for debugging
975 ent->s_lno + 1,
976 ent->lno + 1,
977 ent->num_lines);
978 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
979 struct commit_info ci;
980 suspect->commit->object.flags |= METAINFO_SHOWN;
981 get_commit_info(suspect->commit, &ci, 1);
982 printf("author %s\n", ci.author);
983 printf("author-mail %s\n", ci.author_mail);
984 printf("author-time %lu\n", ci.author_time);
985 printf("author-tz %s\n", ci.author_tz);
986 printf("committer %s\n", ci.committer);
987 printf("committer-mail %s\n", ci.committer_mail);
988 printf("committer-time %lu\n", ci.committer_time);
989 printf("committer-tz %s\n", ci.committer_tz);
990 printf("filename %s\n", suspect->path);
991 printf("summary %s\n", ci.summary);
992 }
993 else if (suspect->commit->object.flags & MORE_THAN_ONE_PATH)
994 printf("filename %s\n", suspect->path);
995
996 cp = nth_line(sb, ent->lno);
997 for (cnt = 0; cnt < ent->num_lines; cnt++) {
998 char ch;
999 if (cnt)
1000 printf("%s %d %d\n", hex,
1001 ent->s_lno + 1 + cnt,
1002 ent->lno + 1 + cnt);
1003 putchar('\t');
1004 do {
1005 ch = *cp++;
1006 putchar(ch);
1007 } while (ch != '\n' &&
1008 cp < sb->final_buf + sb->final_buf_size);
1009 }
1010}
1011
1012static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1013{
1014 int cnt;
1015 const char *cp;
1016 struct origin *suspect = ent->suspect;
1017 struct commit_info ci;
1018 char hex[41];
1019 int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1020
1021 get_commit_info(suspect->commit, &ci, 1);
1022 strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1023
1024 cp = nth_line(sb, ent->lno);
1025 for (cnt = 0; cnt < ent->num_lines; cnt++) {
1026 char ch;
1027
1028 printf("%.*s", (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : 8, hex);
1029 if (opt & OUTPUT_ANNOTATE_COMPAT)
1030 printf("\t(%10s\t%10s\t%d)", ci.author,
1031 format_time(ci.author_time, ci.author_tz,
1032 show_raw_time),
1033 ent->lno + 1 + cnt);
1034 else {
5ff62c30
JH
1035 if (opt & OUTPUT_SHOW_SCORE)
1036 printf(" %*d", max_score_digits, ent->score);
cee7f245
JH
1037 if (opt & OUTPUT_SHOW_NAME)
1038 printf(" %-*.*s", longest_file, longest_file,
1039 suspect->path);
1040 if (opt & OUTPUT_SHOW_NUMBER)
1041 printf(" %*d", max_orig_digits,
1042 ent->s_lno + 1 + cnt);
1043 printf(" (%-*.*s %10s %*d) ",
1044 longest_author, longest_author, ci.author,
1045 format_time(ci.author_time, ci.author_tz,
1046 show_raw_time),
1047 max_digits, ent->lno + 1 + cnt);
1048 }
1049 do {
1050 ch = *cp++;
1051 putchar(ch);
1052 } while (ch != '\n' &&
1053 cp < sb->final_buf + sb->final_buf_size);
1054 }
1055}
1056
1057static void output(struct scoreboard *sb, int option)
1058{
1059 struct blame_entry *ent;
1060
1061 if (option & OUTPUT_PORCELAIN) {
1062 for (ent = sb->ent; ent; ent = ent->next) {
1063 struct blame_entry *oth;
1064 struct origin *suspect = ent->suspect;
1065 struct commit *commit = suspect->commit;
1066 if (commit->object.flags & MORE_THAN_ONE_PATH)
1067 continue;
1068 for (oth = ent->next; oth; oth = oth->next) {
1069 if ((oth->suspect->commit != commit) ||
1070 !strcmp(oth->suspect->path, suspect->path))
1071 continue;
1072 commit->object.flags |= MORE_THAN_ONE_PATH;
1073 break;
1074 }
1075 }
1076 }
1077
1078 for (ent = sb->ent; ent; ent = ent->next) {
1079 if (option & OUTPUT_PORCELAIN)
1080 emit_porcelain(sb, ent);
5ff62c30 1081 else {
cee7f245 1082 emit_other(sb, ent, option);
5ff62c30 1083 }
cee7f245
JH
1084 }
1085}
1086
1087static int prepare_lines(struct scoreboard *sb)
1088{
1089 const char *buf = sb->final_buf;
1090 unsigned long len = sb->final_buf_size;
1091 int num = 0, incomplete = 0, bol = 1;
1092
1093 if (len && buf[len-1] != '\n')
1094 incomplete++; /* incomplete line at the end */
1095 while (len--) {
1096 if (bol) {
1097 sb->lineno = xrealloc(sb->lineno,
1098 sizeof(int* ) * (num + 1));
1099 sb->lineno[num] = buf - sb->final_buf;
1100 bol = 0;
1101 }
1102 if (*buf++ == '\n') {
1103 num++;
1104 bol = 1;
1105 }
1106 }
1ca6ca87
JH
1107 sb->lineno = xrealloc(sb->lineno,
1108 sizeof(int* ) * (num + incomplete + 1));
1109 sb->lineno[num + incomplete] = buf - sb->final_buf;
cee7f245
JH
1110 sb->num_lines = num + incomplete;
1111 return sb->num_lines;
1112}
1113
1114static int read_ancestry(const char *graft_file)
1115{
1116 FILE *fp = fopen(graft_file, "r");
1117 char buf[1024];
1118 if (!fp)
1119 return -1;
1120 while (fgets(buf, sizeof(buf), fp)) {
1121 /* The format is just "Commit Parent1 Parent2 ...\n" */
1122 int len = strlen(buf);
1123 struct commit_graft *graft = read_graft_line(buf, len);
1124 register_commit_graft(graft, 0);
1125 }
1126 fclose(fp);
1127 return 0;
1128}
1129
1130static int lineno_width(int lines)
1131{
1132 int i, width;
1133
1134 for (width = 1, i = 10; i <= lines + 1; width++)
1135 i *= 10;
1136 return width;
1137}
1138
1139static void find_alignment(struct scoreboard *sb, int *option)
1140{
1141 int longest_src_lines = 0;
1142 int longest_dst_lines = 0;
5ff62c30 1143 unsigned largest_score = 0;
cee7f245
JH
1144 struct blame_entry *e;
1145
1146 for (e = sb->ent; e; e = e->next) {
1147 struct origin *suspect = e->suspect;
1148 struct commit_info ci;
1149 int num;
1150
1151 if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1152 suspect->commit->object.flags |= METAINFO_SHOWN;
1153 get_commit_info(suspect->commit, &ci, 1);
1154 if (strcmp(suspect->path, sb->path))
1155 *option |= OUTPUT_SHOW_NAME;
1156 num = strlen(suspect->path);
1157 if (longest_file < num)
1158 longest_file = num;
1159 num = strlen(ci.author);
1160 if (longest_author < num)
1161 longest_author = num;
1162 }
1163 num = e->s_lno + e->num_lines;
1164 if (longest_src_lines < num)
1165 longest_src_lines = num;
1166 num = e->lno + e->num_lines;
1167 if (longest_dst_lines < num)
1168 longest_dst_lines = num;
5ff62c30
JH
1169 if (largest_score < ent_score(sb, e))
1170 largest_score = ent_score(sb, e);
cee7f245
JH
1171 }
1172 max_orig_digits = lineno_width(longest_src_lines);
1173 max_digits = lineno_width(longest_dst_lines);
5ff62c30 1174 max_score_digits = lineno_width(largest_score);
cee7f245
JH
1175}
1176
1177static int has_path_in_work_tree(const char *path)
1178{
1179 struct stat st;
1180 return !lstat(path, &st);
1181}
1182
1183int cmd_pickaxe(int argc, const char **argv, const char *prefix)
1184{
1185 struct rev_info revs;
1186 const char *path;
1187 struct scoreboard sb;
1188 struct origin *o;
1189 struct blame_entry *ent;
d24bba80 1190 int i, seen_dashdash, unk, opt;
cee7f245
JH
1191 long bottom, top, lno;
1192 int output_option = 0;
1193 const char *revs_file = NULL;
1194 const char *final_commit_name = NULL;
1195 char type[10];
1196
d24bba80 1197 opt = 0;
cee7f245
JH
1198 bottom = top = 0;
1199 seen_dashdash = 0;
1200 for (unk = i = 1; i < argc; i++) {
1201 const char *arg = argv[i];
1202 if (*arg != '-')
1203 break;
1204 else if (!strcmp("-c", arg))
1205 output_option |= OUTPUT_ANNOTATE_COMPAT;
1206 else if (!strcmp("-t", arg))
1207 output_option |= OUTPUT_RAW_TIMESTAMP;
1208 else if (!strcmp("-l", arg))
1209 output_option |= OUTPUT_LONG_OBJECT_NAME;
1210 else if (!strcmp("-S", arg) && ++i < argc)
1211 revs_file = argv[i];
d24bba80
JH
1212 else if (!strcmp("-M", arg))
1213 opt |= PICKAXE_BLAME_MOVE;
18abd745
JH
1214 else if (!strcmp("-C", arg)) {
1215 if (opt & PICKAXE_BLAME_COPY)
1216 opt |= PICKAXE_BLAME_COPY_HARDER;
1217 opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
1218 }
cee7f245
JH
1219 else if (!strcmp("-L", arg) && ++i < argc) {
1220 char *term;
1221 arg = argv[i];
1222 if (bottom || top)
1223 die("More than one '-L n,m' option given");
1224 bottom = strtol(arg, &term, 10);
1225 if (*term == ',') {
1226 top = strtol(term + 1, &term, 10);
1227 if (*term)
1228 usage(pickaxe_usage);
1229 }
1230 if (bottom && top && top < bottom) {
1231 unsigned long tmp;
1232 tmp = top; top = bottom; bottom = tmp;
1233 }
1234 }
5ff62c30
JH
1235 else if (!strcmp("--score-debug", arg))
1236 output_option |= OUTPUT_SHOW_SCORE;
cee7f245
JH
1237 else if (!strcmp("-f", arg) ||
1238 !strcmp("--show-name", arg))
1239 output_option |= OUTPUT_SHOW_NAME;
1240 else if (!strcmp("-n", arg) ||
1241 !strcmp("--show-number", arg))
1242 output_option |= OUTPUT_SHOW_NUMBER;
1243 else if (!strcmp("-p", arg) ||
1244 !strcmp("--porcelain", arg))
1245 output_option |= OUTPUT_PORCELAIN;
1246 else if (!strcmp("--", arg)) {
1247 seen_dashdash = 1;
1248 i++;
1249 break;
1250 }
1251 else
1252 argv[unk++] = arg;
1253 }
1254
1255 /* We have collected options unknown to us in argv[1..unk]
1256 * which are to be passed to revision machinery if we are
1257 * going to do the "bottom" procesing.
1258 *
1259 * The remaining are:
1260 *
1261 * (1) if seen_dashdash, its either
1262 * "-options -- <path>" or
1263 * "-options -- <path> <rev>".
1264 * but the latter is allowed only if there is no
1265 * options that we passed to revision machinery.
1266 *
1267 * (2) otherwise, we may have "--" somewhere later and
1268 * might be looking at the first one of multiple 'rev'
1269 * parameters (e.g. " master ^next ^maint -- path").
1270 * See if there is a dashdash first, and give the
1271 * arguments before that to revision machinery.
1272 * After that there must be one 'path'.
1273 *
1274 * (3) otherwise, its one of the three:
1275 * "-options <path> <rev>"
1276 * "-options <rev> <path>"
1277 * "-options <path>"
1278 * but again the first one is allowed only if
1279 * there is no options that we passed to revision
1280 * machinery.
1281 */
1282
1283 if (seen_dashdash) {
1284 /* (1) */
1285 if (argc <= i)
1286 usage(pickaxe_usage);
1287 path = argv[i];
1288 if (i + 1 == argc - 1) {
1289 if (unk != 1)
1290 usage(pickaxe_usage);
1291 argv[unk++] = argv[i + 1];
1292 }
1293 else if (i + 1 != argc)
1294 /* garbage at end */
1295 usage(pickaxe_usage);
1296 }
1297 else {
1298 int j;
1299 for (j = i; !seen_dashdash && j < argc; j++)
1300 if (!strcmp(argv[j], "--"))
1301 seen_dashdash = j;
1302 if (seen_dashdash) {
1303 if (seen_dashdash + 1 != argc - 1)
1304 usage(pickaxe_usage);
1305 path = argv[seen_dashdash + 1];
1306 for (j = i; j < seen_dashdash; j++)
1307 argv[unk++] = argv[j];
1308 }
1309 else {
1310 /* (3) */
1311 path = argv[i];
1312 if (i + 1 == argc - 1) {
1313 final_commit_name = argv[i + 1];
1314
1315 /* if (unk == 1) we could be getting
1316 * old-style
1317 */
1318 if (unk == 1 && !has_path_in_work_tree(path)) {
1319 path = argv[i + 1];
1320 final_commit_name = argv[i];
1321 }
1322 }
1323 else if (i != argc - 1)
1324 usage(pickaxe_usage); /* garbage at end */
1325
1326 if (!has_path_in_work_tree(path))
1327 die("cannot stat path %s: %s",
1328 path, strerror(errno));
1329 }
1330 }
1331
1332 if (final_commit_name)
1333 argv[unk++] = final_commit_name;
1334
1335 /* Now we got rev and path. We do not want the path pruning
1336 * but we may want "bottom" processing.
1337 */
1338 argv[unk] = NULL;
1339
1340 init_revisions(&revs, NULL);
1341 setup_revisions(unk, argv, &revs, "HEAD");
1342 memset(&sb, 0, sizeof(sb));
1343
1344 /* There must be one and only one positive commit in the
1345 * revs->pending array.
1346 */
1347 for (i = 0; i < revs.pending.nr; i++) {
1348 struct object *obj = revs.pending.objects[i].item;
1349 if (obj->flags & UNINTERESTING)
1350 continue;
1351 while (obj->type == OBJ_TAG)
1352 obj = deref_tag(obj, NULL, 0);
1353 if (obj->type != OBJ_COMMIT)
1354 die("Non commit %s?",
1355 revs.pending.objects[i].name);
1356 if (sb.final)
1357 die("More than one commit to dig from %s and %s?",
1358 revs.pending.objects[i].name,
1359 final_commit_name);
1360 sb.final = (struct commit *) obj;
1361 final_commit_name = revs.pending.objects[i].name;
1362 }
1363
1364 if (!sb.final) {
1365 /* "--not A B -- path" without anything positive */
1366 unsigned char head_sha1[20];
1367
1368 final_commit_name = "HEAD";
1369 if (get_sha1(final_commit_name, head_sha1))
1370 die("No such ref: HEAD");
1371 sb.final = lookup_commit_reference(head_sha1);
1372 add_pending_object(&revs, &(sb.final->object), "HEAD");
1373 }
1374
1375 /* If we have bottom, this will mark the ancestors of the
1376 * bottom commits we would reach while traversing as
1377 * uninteresting.
1378 */
1379 prepare_revision_walk(&revs);
1380
1381 o = find_origin(&sb, sb.final, path);
1382 if (!o)
1383 die("no such path %s in %s", path, final_commit_name);
1384
1385 sb.final_buf = read_sha1_file(o->blob_sha1, type, &sb.final_buf_size);
1386 lno = prepare_lines(&sb);
1387
1388 if (bottom < 1)
1389 bottom = 1;
1390 if (top < 1)
1391 top = lno;
1392 bottom--;
1393 if (lno < top)
1394 die("file %s has only %lu lines", path, lno);
1395
1396 ent = xcalloc(1, sizeof(*ent));
1397 ent->lno = bottom;
1398 ent->num_lines = top - bottom;
1399 ent->suspect = o;
1400 ent->s_lno = bottom;
1401
1402 sb.ent = ent;
1403 sb.path = path;
1404
1405 if (revs_file && read_ancestry(revs_file))
1406 die("reading graft file %s failed: %s",
1407 revs_file, strerror(errno));
1408
d24bba80 1409 assign_blame(&sb, &revs, opt);
cee7f245
JH
1410
1411 coalesce(&sb);
1412
1413 if (!(output_option & OUTPUT_PORCELAIN))
1414 find_alignment(&sb, &output_option);
1415
1416 output(&sb, output_option);
1417 free((void *)sb.final_buf);
1418 for (ent = sb.ent; ent; ) {
1419 struct blame_entry *e = ent->next;
1420 free(ent);
1421 ent = e;
1422 }
1423 return 0;
1424}