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