Merge branch 'jc/diff' 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
9 #include "cache.h"
10 #include "refs.h"
11 #include "tag.h"
12 #include "commit.h"
13 #include "tree.h"
14 #include "blob.h"
15 #include "diff.h"
16 #include "revision.h"
17
18 #define DEBUG 0
19
20 struct commit **blame_lines;
21 int num_blame_lines;
22
23 struct util_info {
24         int *line_map;
25         unsigned char sha1[20]; /* blob sha, not commit! */
26         char *buf;
27         unsigned long size;
28         int num_lines;
29 //    const char* path;
30 };
31
32 struct chunk {
33         int off1, len1; // ---
34         int off2, len2; // +++
35 };
36
37 struct patch {
38         struct chunk *chunks;
39         int num;
40 };
41
42 static void get_blob(struct commit *commit);
43
44 /* Only used for statistics */
45 static int num_get_patch = 0;
46 static int num_commits = 0;
47 static int patch_time = 0;
48
49 #define TEMPFILE_PATH_LEN 60
50 static struct patch *get_patch(struct commit *commit, struct commit *other)
51 {
52         struct patch *ret;
53         struct util_info *info_c = (struct util_info *)commit->object.util;
54         struct util_info *info_o = (struct util_info *)other->object.util;
55         char tmp_path1[TEMPFILE_PATH_LEN], tmp_path2[TEMPFILE_PATH_LEN];
56         char diff_cmd[TEMPFILE_PATH_LEN*2 + 20];
57         struct timeval tv_start, tv_end;
58         int fd;
59         FILE *fin;
60         char buf[1024];
61
62         ret = xmalloc(sizeof(struct patch));
63         ret->chunks = NULL;
64         ret->num = 0;
65
66         get_blob(commit);
67         get_blob(other);
68
69         gettimeofday(&tv_start, NULL);
70
71         fd = git_mkstemp(tmp_path1, TEMPFILE_PATH_LEN, "git-blame-XXXXXX");
72         if (fd < 0)
73                 die("unable to create temp-file: %s", strerror(errno));
74
75         if (xwrite(fd, info_c->buf, info_c->size) != info_c->size)
76                 die("write failed: %s", strerror(errno));
77         close(fd);
78
79         fd = git_mkstemp(tmp_path2, 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_o->buf, info_o->size) != info_o->size)
84                 die("write failed: %s", strerror(errno));
85         close(fd);
86
87         sprintf(diff_cmd, "diff -u0 %s %s", tmp_path1, tmp_path2);
88         fin = popen(diff_cmd, "r");
89         if (!fin)
90                 die("popen failed: %s", strerror(errno));
91
92         while (fgets(buf, sizeof(buf), fin)) {
93                 struct chunk *chunk;
94                 char *start, *sp;
95
96                 if (buf[0] != '@' || buf[1] != '@')
97                         continue;
98
99                 if (DEBUG)
100                         printf("chunk line: %s", buf);
101                 ret->num++;
102                 ret->chunks = xrealloc(ret->chunks,
103                                        sizeof(struct chunk) * ret->num);
104                 chunk = &ret->chunks[ret->num - 1];
105
106                 assert(!strncmp(buf, "@@ -", 4));
107
108                 start = buf + 4;
109                 sp = index(start, ' ');
110                 *sp = '\0';
111                 if (index(start, ',')) {
112                         int ret =
113                             sscanf(start, "%d,%d", &chunk->off1, &chunk->len1);
114                         assert(ret == 2);
115                 } else {
116                         int ret = sscanf(start, "%d", &chunk->off1);
117                         assert(ret == 1);
118                         chunk->len1 = 1;
119                 }
120                 *sp = ' ';
121
122                 start = sp + 1;
123                 sp = index(start, ' ');
124                 *sp = '\0';
125                 if (index(start, ',')) {
126                         int ret =
127                             sscanf(start, "%d,%d", &chunk->off2, &chunk->len2);
128                         assert(ret == 2);
129                 } else {
130                         int ret = sscanf(start, "%d", &chunk->off2);
131                         assert(ret == 1);
132                         chunk->len2 = 1;
133                 }
134                 *sp = ' ';
135
136                 if (chunk->len1 == 0)
137                         chunk->off1++;
138                 if (chunk->len2 == 0)
139                         chunk->off2++;
140
141                 if (chunk->off1 > 0)
142                         chunk->off1--;
143                 if (chunk->off2 > 0)
144                         chunk->off2--;
145
146                 assert(chunk->off1 >= 0);
147                 assert(chunk->off2 >= 0);
148         }
149         pclose(fin);
150         unlink(tmp_path1);
151         unlink(tmp_path2);
152
153         gettimeofday(&tv_end, NULL);
154         patch_time += 1000000 * (tv_end.tv_sec - tv_start.tv_sec) +
155                 tv_end.tv_usec - tv_start.tv_usec;
156
157         num_get_patch++;
158         return ret;
159 }
160
161 static void free_patch(struct patch *p)
162 {
163         free(p->chunks);
164         free(p);
165 }
166
167 static int get_blob_sha1_internal(unsigned char *sha1, const char *base,
168                                   int baselen, const char *pathname,
169                                   unsigned mode, int stage);
170
171 static unsigned char blob_sha1[20];
172 static int get_blob_sha1(struct tree *t, const char *pathname,
173                          unsigned char *sha1)
174 {
175         int i;
176         const char *pathspec[2];
177         pathspec[0] = pathname;
178         pathspec[1] = NULL;
179         memset(blob_sha1, 0, sizeof(blob_sha1));
180         read_tree_recursive(t, "", 0, 0, pathspec, get_blob_sha1_internal);
181
182         for (i = 0; i < 20; i++) {
183                 if (blob_sha1[i] != 0)
184                         break;
185         }
186
187         if (i == 20)
188                 return -1;
189
190         memcpy(sha1, blob_sha1, 20);
191         return 0;
192 }
193
194 static int get_blob_sha1_internal(unsigned char *sha1, const char *base,
195                                   int baselen, const char *pathname,
196                                   unsigned mode, int stage)
197 {
198         if (S_ISDIR(mode))
199                 return READ_TREE_RECURSIVE;
200
201         memcpy(blob_sha1, sha1, 20);
202         return -1;
203 }
204
205 static void get_blob(struct commit *commit)
206 {
207         struct util_info *info = commit->object.util;
208         char type[20];
209
210         if (info->buf)
211                 return;
212
213         info->buf = read_sha1_file(info->sha1, type, &info->size);
214
215         assert(!strcmp(type, "blob"));
216 }
217
218 /* For debugging only */
219 static void print_patch(struct patch *p)
220 {
221         int i;
222         printf("Num chunks: %d\n", p->num);
223         for (i = 0; i < p->num; i++) {
224                 printf("%d,%d %d,%d\n", p->chunks[i].off1, p->chunks[i].len1,
225                        p->chunks[i].off2, p->chunks[i].len2);
226         }
227 }
228
229 /* For debugging only */
230 static void print_map(struct commit *cmit, struct commit *other)
231 {
232         struct util_info *util = cmit->object.util;
233         struct util_info *util2 = other->object.util;
234
235         int i;
236         int max =
237             util->num_lines >
238             util2->num_lines ? util->num_lines : util2->num_lines;
239         int num;
240
241         for (i = 0; i < max; i++) {
242                 printf("i: %d ", i);
243                 num = -1;
244
245                 if (i < util->num_lines) {
246                         num = util->line_map[i];
247                         printf("%d\t", num);
248                 } else
249                         printf("\t");
250
251                 if (i < util2->num_lines) {
252                         int num2 = util2->line_map[i];
253                         printf("%d\t", num2);
254                         if (num != -1 && num2 != num)
255                                 printf("---");
256                 } else
257                         printf("\t");
258
259                 printf("\n");
260         }
261 }
262
263 // p is a patch from commit to other.
264 static void fill_line_map(struct commit *commit, struct commit *other,
265                           struct patch *p)
266 {
267         struct util_info *util = commit->object.util;
268         struct util_info *util2 = other->object.util;
269         int *map = util->line_map;
270         int *map2 = util2->line_map;
271         int cur_chunk = 0;
272         int i1, i2;
273
274         if (p->num && DEBUG)
275                 print_patch(p);
276
277         if (DEBUG)
278                 printf("num lines 1: %d num lines 2: %d\n", util->num_lines,
279                        util2->num_lines);
280
281         for (i1 = 0, i2 = 0; i1 < util->num_lines; i1++, i2++) {
282                 struct chunk *chunk = NULL;
283                 if (cur_chunk < p->num)
284                         chunk = &p->chunks[cur_chunk];
285
286                 if (chunk && chunk->off1 == i1) {
287                         if (DEBUG && i2 != chunk->off2)
288                                 printf("i2: %d off2: %d\n", i2, chunk->off2);
289
290                         assert(i2 == chunk->off2);
291
292                         i1--;
293                         i2--;
294                         if (chunk->len1 > 0)
295                                 i1 += chunk->len1;
296
297                         if (chunk->len2 > 0)
298                                 i2 += chunk->len2;
299
300                         cur_chunk++;
301                 } else {
302                         if (i2 >= util2->num_lines)
303                                 break;
304
305                         if (map[i1] != map2[i2] && map[i1] != -1) {
306                                 if (DEBUG)
307                                         printf("map: i1: %d %d %p i2: %d %d %p\n",
308                                                i1, map[i1],
309                                                i1 != -1 ? blame_lines[map[i1]] : NULL,
310                                                i2, map2[i2],
311                                                i2 != -1 ? blame_lines[map2[i2]] : NULL);
312                                 if (map2[i2] != -1 &&
313                                     blame_lines[map[i1]] &&
314                                     !blame_lines[map2[i2]])
315                                         map[i1] = map2[i2];
316                         }
317
318                         if (map[i1] == -1 && map2[i2] != -1)
319                                 map[i1] = map2[i2];
320                 }
321
322                 if (DEBUG > 1)
323                         printf("l1: %d l2: %d i1: %d i2: %d\n",
324                                map[i1], map2[i2], i1, i2);
325         }
326 }
327
328 static int map_line(struct commit *commit, int line)
329 {
330         struct util_info *info = commit->object.util;
331         assert(line >= 0 && line < info->num_lines);
332         return info->line_map[line];
333 }
334
335 static int fill_util_info(struct commit *commit, const char *path)
336 {
337         struct util_info *util;
338         if (commit->object.util)
339                 return 0;
340
341         util = xmalloc(sizeof(struct util_info));
342
343         if (get_blob_sha1(commit->tree, path, util->sha1)) {
344                 free(util);
345                 return 1;
346         } else {
347                 util->buf = NULL;
348                 util->size = 0;
349                 util->line_map = NULL;
350                 util->num_lines = -1;
351                 commit->object.util = util;
352                 return 0;
353         }
354 }
355
356 static void alloc_line_map(struct commit *commit)
357 {
358         struct util_info *util = commit->object.util;
359         int i;
360
361         if (util->line_map)
362                 return;
363
364         get_blob(commit);
365
366         util->num_lines = 0;
367         for (i = 0; i < util->size; i++) {
368                 if (util->buf[i] == '\n')
369                         util->num_lines++;
370         }
371         if(util->buf[util->size - 1] != '\n')
372                 util->num_lines++;
373
374         util->line_map = xmalloc(sizeof(int) * util->num_lines);
375
376         for (i = 0; i < util->num_lines; i++)
377                 util->line_map[i] = -1;
378 }
379
380 static void init_first_commit(struct commit* commit, const char* filename)
381 {
382         struct util_info* util;
383         int i;
384
385         if (fill_util_info(commit, filename))
386                 die("fill_util_info failed");
387
388         alloc_line_map(commit);
389
390         util = commit->object.util;
391         num_blame_lines = util->num_lines;
392
393         for (i = 0; i < num_blame_lines; i++)
394                 util->line_map[i] = i;
395 }
396
397
398 static void process_commits(struct rev_info *rev, const char *path,
399                             struct commit** initial)
400 {
401         int i;
402         struct util_info* util;
403         int lines_left;
404         int *blame_p;
405         int *new_lines;
406         int new_lines_len;
407
408         struct commit* commit = get_revision(rev);
409         assert(commit);
410         init_first_commit(commit, path);
411
412         util = commit->object.util;
413         num_blame_lines = util->num_lines;
414         blame_lines = xmalloc(sizeof(struct commit *) * num_blame_lines);
415         for (i = 0; i < num_blame_lines; i++)
416                 blame_lines[i] = NULL;
417
418         lines_left = num_blame_lines;
419         blame_p = xmalloc(sizeof(int) * num_blame_lines);
420         new_lines = xmalloc(sizeof(int) * num_blame_lines);
421         do {
422                 struct commit_list *parents;
423                 int num_parents;
424                 struct util_info *util;
425
426                 if (DEBUG)
427                         printf("\nProcessing commit: %d %s\n", num_commits,
428                                sha1_to_hex(commit->object.sha1));
429
430                 if (lines_left == 0)
431                         return;
432
433                 num_commits++;
434                 memset(blame_p, 0, sizeof(int) * num_blame_lines);
435                 new_lines_len = 0;
436                 num_parents = 0;
437                 for (parents = commit->parents;
438                      parents != NULL; parents = parents->next)
439                         num_parents++;
440
441                 if(num_parents == 0)
442                         *initial = commit;
443
444                 if(fill_util_info(commit, path))
445                         continue;
446
447                 alloc_line_map(commit);
448                 util = commit->object.util;
449
450                 for (parents = commit->parents;
451                      parents != NULL; parents = parents->next) {
452                         struct commit *parent = parents->item;
453                         struct patch *patch;
454
455                         if (parse_commit(parent) < 0)
456                                 die("parse_commit error");
457
458                         if (DEBUG)
459                                 printf("parent: %s\n",
460                                        sha1_to_hex(parent->object.sha1));
461
462                         if(fill_util_info(parent, path)) {
463                                 num_parents--;
464                                 continue;
465                         }
466
467                         patch = get_patch(parent, commit);
468                         alloc_line_map(parent);
469                         fill_line_map(parent, commit, patch);
470
471                         for (i = 0; i < patch->num; i++) {
472                             int l;
473                             for (l = 0; l < patch->chunks[i].len2; l++) {
474                                 int mapped_line =
475                                     map_line(commit, patch->chunks[i].off2 + l);
476                                 if (mapped_line != -1) {
477                                     blame_p[mapped_line]++;
478                                     if (blame_p[mapped_line] == num_parents)
479                                         new_lines[new_lines_len++] = mapped_line;
480                                 }
481                             }
482                         }
483                         free_patch(patch);
484                 }
485
486                 if (DEBUG)
487                         printf("parents: %d\n", num_parents);
488
489                 for (i = 0; i < new_lines_len; i++) {
490                         int mapped_line = new_lines[i];
491                         if (blame_lines[mapped_line] == NULL) {
492                                 blame_lines[mapped_line] = commit;
493                                 lines_left--;
494                                 if (DEBUG)
495                                         printf("blame: mapped: %d i: %d\n",
496                                                mapped_line, i);
497                         }
498                 }
499         } while ((commit = get_revision(rev)) != NULL);
500 }
501
502 int main(int argc, const char **argv)
503 {
504         int i;
505         struct commit *initial = NULL;
506         unsigned char sha1[20];
507         const char* filename;
508         int num_args;
509         const char* args[10];
510         struct rev_info rev;
511
512         setup_git_directory();
513
514         if (argc != 3)
515                 die("Usage: blame commit-ish file");
516
517
518         filename = argv[2];
519
520         {
521                 struct commit* commit;
522                 if (get_sha1(argv[1], sha1))
523                         die("get_sha1 failed");
524                 commit = lookup_commit_reference(sha1);
525
526                 if (fill_util_info(commit, filename)) {
527                         printf("%s not found in %s\n", filename, argv[1]);
528                         return 1;
529                 }
530         }
531
532         num_args = 0;
533         args[num_args++] = NULL;
534         args[num_args++] = "--topo-order";
535         args[num_args++] = "--remove-empty";
536         args[num_args++] = argv[1];
537         args[num_args++] = "--";
538         args[num_args++] = filename;
539         args[num_args] = NULL;
540
541         setup_revisions(num_args, args, &rev, "HEAD");
542         prepare_revision_walk(&rev);
543         process_commits(&rev, filename, &initial);
544
545         for (i = 0; i < num_blame_lines; i++) {
546                 struct commit *c = blame_lines[i];
547                 if (!c)
548                         c = initial;
549
550                 printf("%d %.8s\n", i, sha1_to_hex(c->object.sha1));
551 // printf("%d %s\n", i, find_unique_abbrev(blame_lines[i]->object.sha1, 6));
552         }
553
554         if (DEBUG) {
555                 printf("num get patch: %d\n", num_get_patch);
556                 printf("num commits: %d\n", num_commits);
557                 printf("patch time: %f\n", patch_time / 1000000.0);
558                 printf("initial: %s\n", sha1_to_hex(initial->object.sha1));
559         }
560
561         return 0;
562 }