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
21static 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
26static struct commit **blame_lines;
27static int num_blame_lines;
28static char* blame_contents;
29static int blame_len;
30
31struct 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
40struct chunk {
41 int off1, len1; // ---
42 int off2, len2; // +++
43};
44
45struct patch {
46 struct chunk *chunks;
47 int num;
48};
49
50static void get_blob(struct commit *commit);
51
52/* Only used for statistics */
53static int num_get_patch = 0;
54static int num_commits = 0;
55static int patch_time = 0;
56
57#define TEMPFILE_PATH_LEN 60
58static 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
169static void free_patch(struct patch *p)
170{
171 free(p->chunks);
172 free(p);
173}
174
175static int get_blob_sha1_internal(unsigned char *sha1, const char *base,
176 int baselen, const char *pathname,
177 unsigned mode, int stage);
178
179static unsigned char blob_sha1[20];
180static 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
202static 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
213static 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 */
227static 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 */
239static 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.
274static 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
338static 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
345static 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
366static 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
390static 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
407static 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
514struct commit_info
515{
516 char* author;
517 char* author_mail;
518 unsigned long author_time;
519 char* author_tz;
520};
521
522static 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
553static 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
572int 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}