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