Merge branch 'fd/asciidoc' into next
[git] / blame.c
1 /*
2  * Copyright (C) 2006, Fredrik Kuivinen <freku045@student.liu.se>
3  */
4
5 #include <assert.h>
6 #include <time.h>
7 #include <sys/time.h>
8 #include <math.h>
9
10 #include "cache.h"
11 #include "refs.h"
12 #include "tag.h"
13 #include "commit.h"
14 #include "tree.h"
15 #include "blob.h"
16 #include "diff.h"
17 #include "revision.h"
18
19 #define DEBUG 0
20
21 static const char blame_usage[] = "[-c] [-l] [--] file [commit]\n"
22         "  -c, --compability Use the same output mode as git-annotate (Default: off)\n"
23         "  -l, --long        Show long commit SHA1 (Default: off)\n"
24         "  -h, --help        This message";
25
26 static struct commit **blame_lines;
27 static int num_blame_lines;
28 static char* blame_contents;
29 static int blame_len;
30
31 struct util_info {
32         int *line_map;
33         unsigned char sha1[20]; /* blob sha, not commit! */
34         char *buf;
35         unsigned long size;
36         int num_lines;
37 //    const char* path;
38 };
39
40 struct chunk {
41         int off1, len1; // ---
42         int off2, len2; // +++
43 };
44
45 struct patch {
46         struct chunk *chunks;
47         int num;
48 };
49
50 static void get_blob(struct commit *commit);
51
52 /* Only used for statistics */
53 static int num_get_patch = 0;
54 static int num_commits = 0;
55 static int patch_time = 0;
56
57 #define TEMPFILE_PATH_LEN 60
58 static struct patch *get_patch(struct commit *commit, struct commit *other)
59 {
60         struct patch *ret;
61         struct util_info *info_c = (struct util_info *)commit->object.util;
62         struct util_info *info_o = (struct util_info *)other->object.util;
63         char tmp_path1[TEMPFILE_PATH_LEN], tmp_path2[TEMPFILE_PATH_LEN];
64         char diff_cmd[TEMPFILE_PATH_LEN*2 + 20];
65         struct timeval tv_start, tv_end;
66         int fd;
67         FILE *fin;
68         char buf[1024];
69
70         ret = xmalloc(sizeof(struct patch));
71         ret->chunks = NULL;
72         ret->num = 0;
73
74         get_blob(commit);
75         get_blob(other);
76
77         gettimeofday(&tv_start, NULL);
78
79         fd = git_mkstemp(tmp_path1, TEMPFILE_PATH_LEN, "git-blame-XXXXXX");
80         if (fd < 0)
81                 die("unable to create temp-file: %s", strerror(errno));
82
83         if (xwrite(fd, info_c->buf, info_c->size) != info_c->size)
84                 die("write failed: %s", strerror(errno));
85         close(fd);
86
87         fd = git_mkstemp(tmp_path2, TEMPFILE_PATH_LEN, "git-blame-XXXXXX");
88         if (fd < 0)
89                 die("unable to create temp-file: %s", strerror(errno));
90
91         if (xwrite(fd, info_o->buf, info_o->size) != info_o->size)
92                 die("write failed: %s", strerror(errno));
93         close(fd);
94
95         sprintf(diff_cmd, "diff -u -U 0 %s %s", tmp_path1, tmp_path2);
96         fin = popen(diff_cmd, "r");
97         if (!fin)
98                 die("popen failed: %s", strerror(errno));
99
100         while (fgets(buf, sizeof(buf), fin)) {
101                 struct chunk *chunk;
102                 char *start, *sp;
103
104                 if (buf[0] != '@' || buf[1] != '@')
105                         continue;
106
107                 if (DEBUG)
108                         printf("chunk line: %s", buf);
109                 ret->num++;
110                 ret->chunks = xrealloc(ret->chunks,
111                                        sizeof(struct chunk) * ret->num);
112                 chunk = &ret->chunks[ret->num - 1];
113
114                 assert(!strncmp(buf, "@@ -", 4));
115
116                 start = buf + 4;
117                 sp = index(start, ' ');
118                 *sp = '\0';
119                 if (index(start, ',')) {
120                         int ret =
121                             sscanf(start, "%d,%d", &chunk->off1, &chunk->len1);
122                         assert(ret == 2);
123                 } else {
124                         int ret = sscanf(start, "%d", &chunk->off1);
125                         assert(ret == 1);
126                         chunk->len1 = 1;
127                 }
128                 *sp = ' ';
129
130                 start = sp + 1;
131                 sp = index(start, ' ');
132                 *sp = '\0';
133                 if (index(start, ',')) {
134                         int ret =
135                             sscanf(start, "%d,%d", &chunk->off2, &chunk->len2);
136                         assert(ret == 2);
137                 } else {
138                         int ret = sscanf(start, "%d", &chunk->off2);
139                         assert(ret == 1);
140                         chunk->len2 = 1;
141                 }
142                 *sp = ' ';
143
144                 if (chunk->len1 == 0)
145                         chunk->off1++;
146                 if (chunk->len2 == 0)
147                         chunk->off2++;
148
149                 if (chunk->off1 > 0)
150                         chunk->off1--;
151                 if (chunk->off2 > 0)
152                         chunk->off2--;
153
154                 assert(chunk->off1 >= 0);
155                 assert(chunk->off2 >= 0);
156         }
157         pclose(fin);
158         unlink(tmp_path1);
159         unlink(tmp_path2);
160
161         gettimeofday(&tv_end, NULL);
162         patch_time += 1000000 * (tv_end.tv_sec - tv_start.tv_sec) +
163                 tv_end.tv_usec - tv_start.tv_usec;
164
165         num_get_patch++;
166         return ret;
167 }
168
169 static void free_patch(struct patch *p)
170 {
171         free(p->chunks);
172         free(p);
173 }
174
175 static int get_blob_sha1_internal(unsigned char *sha1, const char *base,
176                                   int baselen, const char *pathname,
177                                   unsigned mode, int stage);
178
179 static unsigned char blob_sha1[20];
180 static int get_blob_sha1(struct tree *t, const char *pathname,
181                          unsigned char *sha1)
182 {
183         int i;
184         const char *pathspec[2];
185         pathspec[0] = pathname;
186         pathspec[1] = NULL;
187         memset(blob_sha1, 0, sizeof(blob_sha1));
188         read_tree_recursive(t, "", 0, 0, pathspec, get_blob_sha1_internal);
189
190         for (i = 0; i < 20; i++) {
191                 if (blob_sha1[i] != 0)
192                         break;
193         }
194
195         if (i == 20)
196                 return -1;
197
198         memcpy(sha1, blob_sha1, 20);
199         return 0;
200 }
201
202 static int get_blob_sha1_internal(unsigned char *sha1, const char *base,
203                                   int baselen, const char *pathname,
204                                   unsigned mode, int stage)
205 {
206         if (S_ISDIR(mode))
207                 return READ_TREE_RECURSIVE;
208
209         memcpy(blob_sha1, sha1, 20);
210         return -1;
211 }
212
213 static void get_blob(struct commit *commit)
214 {
215         struct util_info *info = commit->object.util;
216         char type[20];
217
218         if (info->buf)
219                 return;
220
221         info->buf = read_sha1_file(info->sha1, type, &info->size);
222
223         assert(!strcmp(type, "blob"));
224 }
225
226 /* For debugging only */
227 static void print_patch(struct patch *p)
228 {
229         int i;
230         printf("Num chunks: %d\n", p->num);
231         for (i = 0; i < p->num; i++) {
232                 printf("%d,%d %d,%d\n", p->chunks[i].off1, p->chunks[i].len1,
233                        p->chunks[i].off2, p->chunks[i].len2);
234         }
235 }
236
237 #if 0
238 /* For debugging only */
239 static void print_map(struct commit *cmit, struct commit *other)
240 {
241         struct util_info *util = cmit->object.util;
242         struct util_info *util2 = other->object.util;
243
244         int i;
245         int max =
246             util->num_lines >
247             util2->num_lines ? util->num_lines : util2->num_lines;
248         int num;
249
250         for (i = 0; i < max; i++) {
251                 printf("i: %d ", i);
252                 num = -1;
253
254                 if (i < util->num_lines) {
255                         num = util->line_map[i];
256                         printf("%d\t", num);
257                 } else
258                         printf("\t");
259
260                 if (i < util2->num_lines) {
261                         int num2 = util2->line_map[i];
262                         printf("%d\t", num2);
263                         if (num != -1 && num2 != num)
264                                 printf("---");
265                 } else
266                         printf("\t");
267
268                 printf("\n");
269         }
270 }
271 #endif
272
273 // p is a patch from commit to other.
274 static void fill_line_map(struct commit *commit, struct commit *other,
275                           struct patch *p)
276 {
277         struct util_info *util = commit->object.util;
278         struct util_info *util2 = other->object.util;
279         int *map = util->line_map;
280         int *map2 = util2->line_map;
281         int cur_chunk = 0;
282         int i1, i2;
283
284         if (p->num && DEBUG)
285                 print_patch(p);
286
287         if (DEBUG)
288                 printf("num lines 1: %d num lines 2: %d\n", util->num_lines,
289                        util2->num_lines);
290
291         for (i1 = 0, i2 = 0; i1 < util->num_lines; i1++, i2++) {
292                 struct chunk *chunk = NULL;
293                 if (cur_chunk < p->num)
294                         chunk = &p->chunks[cur_chunk];
295
296                 if (chunk && chunk->off1 == i1) {
297                         if (DEBUG && i2 != chunk->off2)
298                                 printf("i2: %d off2: %d\n", i2, chunk->off2);
299
300                         assert(i2 == chunk->off2);
301
302                         i1--;
303                         i2--;
304                         if (chunk->len1 > 0)
305                                 i1 += chunk->len1;
306
307                         if (chunk->len2 > 0)
308                                 i2 += chunk->len2;
309
310                         cur_chunk++;
311                 } else {
312                         if (i2 >= util2->num_lines)
313                                 break;
314
315                         if (map[i1] != map2[i2] && map[i1] != -1) {
316                                 if (DEBUG)
317                                         printf("map: i1: %d %d %p i2: %d %d %p\n",
318                                                i1, map[i1],
319                                                i1 != -1 ? blame_lines[map[i1]] : NULL,
320                                                i2, map2[i2],
321                                                i2 != -1 ? blame_lines[map2[i2]] : NULL);
322                                 if (map2[i2] != -1 &&
323                                     blame_lines[map[i1]] &&
324                                     !blame_lines[map2[i2]])
325                                         map[i1] = map2[i2];
326                         }
327
328                         if (map[i1] == -1 && map2[i2] != -1)
329                                 map[i1] = map2[i2];
330                 }
331
332                 if (DEBUG > 1)
333                         printf("l1: %d l2: %d i1: %d i2: %d\n",
334                                map[i1], map2[i2], i1, i2);
335         }
336 }
337
338 static int map_line(struct commit *commit, int line)
339 {
340         struct util_info *info = commit->object.util;
341         assert(line >= 0 && line < info->num_lines);
342         return info->line_map[line];
343 }
344
345 static int fill_util_info(struct commit *commit, const char *path)
346 {
347         struct util_info *util;
348         if (commit->object.util)
349                 return 0;
350
351         util = xmalloc(sizeof(struct util_info));
352
353         if (get_blob_sha1(commit->tree, path, util->sha1)) {
354                 free(util);
355                 return 1;
356         } else {
357                 util->buf = NULL;
358                 util->size = 0;
359                 util->line_map = NULL;
360                 util->num_lines = -1;
361                 commit->object.util = util;
362                 return 0;
363         }
364 }
365
366 static void alloc_line_map(struct commit *commit)
367 {
368         struct util_info *util = commit->object.util;
369         int i;
370
371         if (util->line_map)
372                 return;
373
374         get_blob(commit);
375
376         util->num_lines = 0;
377         for (i = 0; i < util->size; i++) {
378                 if (util->buf[i] == '\n')
379                         util->num_lines++;
380         }
381         if(util->buf[util->size - 1] != '\n')
382                 util->num_lines++;
383
384         util->line_map = xmalloc(sizeof(int) * util->num_lines);
385
386         for (i = 0; i < util->num_lines; i++)
387                 util->line_map[i] = -1;
388 }
389
390 static void init_first_commit(struct commit* commit, const char* filename)
391 {
392         struct util_info* util;
393         int i;
394
395         if (fill_util_info(commit, filename))
396                 die("fill_util_info failed");
397
398         alloc_line_map(commit);
399
400         util = commit->object.util;
401
402         for (i = 0; i < util->num_lines; i++)
403                 util->line_map[i] = i;
404 }
405
406
407 static void process_commits(struct rev_info *rev, const char *path,
408                             struct commit** initial)
409 {
410         int i;
411         struct util_info* util;
412         int lines_left;
413         int *blame_p;
414         int *new_lines;
415         int new_lines_len;
416
417         struct commit* commit = get_revision(rev);
418         assert(commit);
419         init_first_commit(commit, path);
420
421         util = commit->object.util;
422         num_blame_lines = util->num_lines;
423         blame_lines = xmalloc(sizeof(struct commit *) * num_blame_lines);
424         blame_contents = util->buf;
425         blame_len = util->size;
426
427         for (i = 0; i < num_blame_lines; i++)
428                 blame_lines[i] = NULL;
429
430         lines_left = num_blame_lines;
431         blame_p = xmalloc(sizeof(int) * num_blame_lines);
432         new_lines = xmalloc(sizeof(int) * num_blame_lines);
433         do {
434                 struct commit_list *parents;
435                 int num_parents;
436                 struct util_info *util;
437
438                 if (DEBUG)
439                         printf("\nProcessing commit: %d %s\n", num_commits,
440                                sha1_to_hex(commit->object.sha1));
441
442                 if (lines_left == 0)
443                         return;
444
445                 num_commits++;
446                 memset(blame_p, 0, sizeof(int) * num_blame_lines);
447                 new_lines_len = 0;
448                 num_parents = 0;
449                 for (parents = commit->parents;
450                      parents != NULL; parents = parents->next)
451                         num_parents++;
452
453                 if(num_parents == 0)
454                         *initial = commit;
455
456                 if(fill_util_info(commit, path))
457                         continue;
458
459                 alloc_line_map(commit);
460                 util = commit->object.util;
461
462                 for (parents = commit->parents;
463                      parents != NULL; parents = parents->next) {
464                         struct commit *parent = parents->item;
465                         struct patch *patch;
466
467                         if (parse_commit(parent) < 0)
468                                 die("parse_commit error");
469
470                         if (DEBUG)
471                                 printf("parent: %s\n",
472                                        sha1_to_hex(parent->object.sha1));
473
474                         if(fill_util_info(parent, path)) {
475                                 num_parents--;
476                                 continue;
477                         }
478
479                         patch = get_patch(parent, commit);
480                         alloc_line_map(parent);
481                         fill_line_map(parent, commit, patch);
482
483                         for (i = 0; i < patch->num; i++) {
484                             int l;
485                             for (l = 0; l < patch->chunks[i].len2; l++) {
486                                 int mapped_line =
487                                     map_line(commit, patch->chunks[i].off2 + l);
488                                 if (mapped_line != -1) {
489                                     blame_p[mapped_line]++;
490                                     if (blame_p[mapped_line] == num_parents)
491                                         new_lines[new_lines_len++] = mapped_line;
492                                 }
493                             }
494                         }
495                         free_patch(patch);
496                 }
497
498                 if (DEBUG)
499                         printf("parents: %d\n", num_parents);
500
501                 for (i = 0; i < new_lines_len; i++) {
502                         int mapped_line = new_lines[i];
503                         if (blame_lines[mapped_line] == NULL) {
504                                 blame_lines[mapped_line] = commit;
505                                 lines_left--;
506                                 if (DEBUG)
507                                         printf("blame: mapped: %d i: %d\n",
508                                                mapped_line, i);
509                         }
510                 }
511         } while ((commit = get_revision(rev)) != NULL);
512 }
513
514 struct commit_info
515 {
516         char* author;
517         char* author_mail;
518         unsigned long author_time;
519         char* author_tz;
520 };
521
522 static void get_commit_info(struct commit* commit, struct commit_info* ret)
523 {
524         int len;
525         char* tmp;
526         static char author_buf[1024];
527
528         tmp = strstr(commit->buffer, "\nauthor ") + 8;
529         len = index(tmp, '\n') - tmp;
530         ret->author = author_buf;
531         memcpy(ret->author, tmp, len);
532
533         tmp = ret->author;
534         tmp += len;
535         *tmp = 0;
536         while(*tmp != ' ')
537                 tmp--;
538         ret->author_tz = tmp+1;
539
540         *tmp = 0;
541         while(*tmp != ' ')
542                 tmp--;
543         ret->author_time = strtoul(tmp, NULL, 10);
544
545         *tmp = 0;
546         while(*tmp != ' ')
547                 tmp--;
548         ret->author_mail = tmp + 1;
549
550         *tmp = 0;
551 }
552
553 static const char* format_time(unsigned long time, const char* tz_str)
554 {
555         static char time_buf[128];
556         time_t t = time;
557         int minutes, tz;
558         struct tm *tm;
559
560         tz = atoi(tz_str);
561         minutes = tz < 0 ? -tz : tz;
562         minutes = (minutes / 100)*60 + (minutes % 100);
563         minutes = tz < 0 ? -minutes : minutes;
564         t = time + minutes * 60;
565         tm = gmtime(&t);
566
567         strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm);
568         strcat(time_buf, tz_str);
569         return time_buf;
570 }
571
572 int main(int argc, const char **argv)
573 {
574         int i;
575         struct commit *initial = NULL;
576         unsigned char sha1[20];
577
578         const char *filename = NULL, *commit = NULL;
579         char filename_buf[256];
580         int sha1_len = 8;
581         int compability = 0;
582         int options = 1;
583
584         int num_args;
585         const char* args[10];
586         struct rev_info rev;
587
588         struct commit_info ci;
589         const char *buf;
590         int max_digits;
591
592         const char* prefix = setup_git_directory();
593
594         for(i = 1; i < argc; i++) {
595                 if(options) {
596                         if(!strcmp(argv[i], "-h") ||
597                            !strcmp(argv[i], "--help"))
598                                 usage(blame_usage);
599                         else if(!strcmp(argv[i], "-l") ||
600                                 !strcmp(argv[i], "--long")) {
601                                 sha1_len = 40;
602                                 continue;
603                         } else if(!strcmp(argv[i], "-c") ||
604                                   !strcmp(argv[i], "--compability")) {
605                                 compability = 1;
606                                 continue;
607                         } else if(!strcmp(argv[i], "--")) {
608                                 options = 0;
609                                 continue;
610                         } else if(argv[i][0] == '-')
611                                 usage(blame_usage);
612                         else
613                                 options = 0;
614                 }
615
616                 if(!options) {
617                         if(!filename)
618                                 filename = argv[i];
619                         else if(!commit)
620                                 commit = argv[i];
621                         else
622                                 usage(blame_usage);
623                 }
624         }
625
626         if(!filename)
627                 usage(blame_usage);
628         if(!commit)
629                 commit = "HEAD";
630
631         if(prefix)
632                 sprintf(filename_buf, "%s%s", prefix, filename);
633         else
634                 strcpy(filename_buf, filename);
635         filename = filename_buf;
636
637         {
638                 struct commit* c;
639                 if (get_sha1(commit, sha1))
640                         die("get_sha1 failed, commit '%s' not found", commit);
641                 c = lookup_commit_reference(sha1);
642
643                 if (fill_util_info(c, filename)) {
644                         printf("%s not found in %s\n", filename, commit);
645                         return 1;
646                 }
647         }
648
649         num_args = 0;
650         args[num_args++] = NULL;
651         args[num_args++] = "--topo-order";
652         args[num_args++] = "--remove-empty";
653         args[num_args++] = commit;
654         args[num_args++] = "--";
655         args[num_args++] = filename;
656         args[num_args] = NULL;
657
658         setup_revisions(num_args, args, &rev, "HEAD");
659         prepare_revision_walk(&rev);
660         process_commits(&rev, filename, &initial);
661
662         buf = blame_contents;
663         for (max_digits = 1, i = 10; i <= num_blame_lines + 1; max_digits++)
664                 i *= 10;
665
666         for (i = 0; i < num_blame_lines; i++) {
667                 struct commit *c = blame_lines[i];
668                 if (!c)
669                         c = initial;
670
671                 get_commit_info(c, &ci);
672                 fwrite(sha1_to_hex(c->object.sha1), sha1_len, 1, stdout);
673                 if(compability)
674                         printf("\t(%10s\t%10s\t%d)", ci.author,
675                                format_time(ci.author_time, ci.author_tz), i+1);
676                 else
677                         printf(" (%-15.15s %10s %*d) ", ci.author,
678                                format_time(ci.author_time, ci.author_tz),
679                                max_digits, i+1);
680
681                 if(i == num_blame_lines - 1) {
682                         fwrite(buf, blame_len - (buf - blame_contents),
683                                1, stdout);
684                         if(blame_contents[blame_len-1] != '\n')
685                                 putc('\n', stdout);
686                 } else {
687                         char* next_buf = index(buf, '\n') + 1;
688                         fwrite(buf, next_buf - buf, 1, stdout);
689                         buf = next_buf;
690                 }
691         }
692
693         if (DEBUG) {
694                 printf("num get patch: %d\n", num_get_patch);
695                 printf("num commits: %d\n", num_commits);
696                 printf("patch time: %f\n", patch_time / 1000000.0);
697                 printf("initial: %s\n", sha1_to_hex(initial->object.sha1));
698         }
699
700         return 0;
701 }