Merge branch 'ml/cvsserver' into next
[git.git] / blame.c
1 #include <assert.h>
2
3 #include "cache.h"
4 #include "refs.h"
5 #include "tag.h"
6 #include "commit.h"
7 #include "tree.h"
8 #include "blob.h"
9 #include "diff.h"
10
11 #define DEBUG 0
12
13 struct commit** blame_lines;
14 int num_blame_lines;
15
16 struct util_info
17 {
18     int* line_map;
19     int num_lines;
20     unsigned char sha1[20]; /* blob sha, not commit! */
21     char* buf;
22     unsigned long size;
23 //    const char* path;
24 };
25
26 struct chunk
27 {
28     int off1, len1; // ---
29     int off2, len2; // +++
30 };
31
32 struct patch
33 {
34     struct chunk* chunks;
35     int num;
36 };
37
38 static void get_blob(struct commit* commit);
39
40 int num_get_patch = 0;
41 int num_commits = 0;
42
43 struct patch* get_patch(struct commit* commit, struct commit* other)
44 {
45     struct patch* ret = xmalloc(sizeof(struct patch));
46     ret->chunks = NULL;
47     ret->num = 0;
48
49     struct util_info* info_c = (struct util_info*) commit->object.util;
50     struct util_info* info_o = (struct util_info*) other->object.util;
51
52     if(!memcmp(info_c->sha1, info_o->sha1, 20))
53         return ret;
54
55     get_blob(commit);
56     get_blob(other);
57
58     FILE* fout = fopen("/tmp/git-blame-tmp1", "w");
59     if(!fout)
60         die("fopen tmp1 failed: %s", strerror(errno));
61
62     if(fwrite(info_c->buf, info_c->size, 1, fout) != 1)
63         die("fwrite 1 failed: %s", strerror(errno));
64     fclose(fout);
65
66     fout = fopen("/tmp/git-blame-tmp2", "w");
67     if(!fout)
68         die("fopen tmp2 failed: %s", strerror(errno));
69
70     if(fwrite(info_o->buf, info_o->size, 1, fout) != 1)
71         die("fwrite 2 failed: %s", strerror(errno));
72     fclose(fout);
73
74     FILE* fin = popen("diff -u0 /tmp/git-blame-tmp1 /tmp/git-blame-tmp2", "r");
75     if(!fin)
76         die("popen failed: %s", strerror(errno));
77
78     char buf[1024];
79     while(fgets(buf, sizeof(buf), fin)) {
80         if(buf[0] != '@' || buf[1] != '@')
81             continue;
82
83         if(DEBUG)
84             printf("chunk line: %s", buf);
85         ret->num++;
86         ret->chunks = xrealloc(ret->chunks, sizeof(struct chunk)*ret->num);
87         struct chunk* chunk = &ret->chunks[ret->num-1];
88
89         assert(!strncmp(buf, "@@ -", 4));
90
91         char* start = buf+4;
92         char* sp = index(start, ' ');
93         *sp = '\0';
94         if(index(start, ',')) {
95             int ret = sscanf(start, "%d,%d", &chunk->off1, &chunk->len1);
96             assert(ret == 2);
97         } else {
98             int ret = sscanf(start, "%d", &chunk->off1);
99             assert(ret == 1);
100             chunk->len1 = 1;
101         }
102         *sp = ' ';
103
104         start = sp+1;
105         sp = index(start, ' ');
106         *sp = '\0';
107         if(index(start, ',')) {
108             int ret = sscanf(start, "%d,%d", &chunk->off2, &chunk->len2);
109             assert(ret == 2);
110         } else {
111             int ret = sscanf(start, "%d", &chunk->off2);
112             assert(ret == 1);
113             chunk->len2 = 1;
114         }
115         *sp = ' ';
116
117         if(chunk->off1 > 0)
118             chunk->off1 -= 1;
119         if(chunk->off2 > 0)
120             chunk->off2 -= 1;
121
122         assert(chunk->off1 >= 0);
123         assert(chunk->off2 >= 0);
124     }
125     fclose(fin);
126
127     num_get_patch++;
128     return ret;
129 }
130
131 void free_patch(struct patch* p)
132 {
133     free(p->chunks);
134     free(p);
135 }
136
137 static int get_blob_sha1_internal(unsigned char *sha1, const char *base, int baselen,
138                                   const char *pathname, unsigned mode, int stage);
139
140
141 static unsigned char blob_sha1[20];
142 static int get_blob_sha1(struct tree* t, const char* pathname, unsigned char* sha1)
143 {
144     const char *pathspec[2];
145     pathspec[0] = pathname;
146     pathspec[1] = NULL;
147     memset(blob_sha1, 0, sizeof(blob_sha1));
148     read_tree_recursive(t, "", 0, 0, pathspec, get_blob_sha1_internal);
149
150     int i;
151     for(i = 0; i < 20; i++) {
152         if(blob_sha1[i] != 0)
153             break;
154     }
155
156     if(i == 20)
157         return -1;
158
159     memcpy(sha1, blob_sha1, 20);
160     return 0;
161 }
162
163 static int get_blob_sha1_internal(unsigned char *sha1, const char *base, int baselen,
164                                   const char *pathname, unsigned mode, int stage)
165 {
166 //    printf("Got blob: %s base: '%s' baselen: %d pathname: '%s' mode: %o stage: %d\n",
167 //           sha1_to_hex(sha1), base, baselen, pathname, mode, stage);
168
169     if(S_ISDIR(mode))
170         return READ_TREE_RECURSIVE;
171
172     memcpy(blob_sha1, sha1, 20);
173     return -1;
174 }
175
176 static void get_blob(struct commit* commit)
177 {
178     struct util_info* info = commit->object.util;
179     char type[20];
180
181     if(info->buf)
182         return;
183
184     info->buf = read_sha1_file(info->sha1, type, &info->size);
185     assert(!strcmp(type, "blob"));
186 }
187
188 void print_patch(struct patch* p)
189 {
190     printf("Num chunks: %d\n", p->num);
191     int i;
192     for(i = 0; i < p->num; i++) {
193         printf("%d,%d %d,%d\n", p->chunks[i].off1, p->chunks[i].len1, p->chunks[i].off2, p->chunks[i].len2);
194     }
195 }
196
197
198 // p is a patch from commit to other.
199 void fill_line_map(struct commit* commit, struct commit* other, struct patch* p)
200 {
201     int num_lines = ((struct util_info*) commit->object.util)->num_lines;
202     int* line_map = ((struct util_info*) commit->object.util)->line_map;
203     int num_lines2 = ((struct util_info*) other->object.util)->num_lines;
204     int* line_map2 = ((struct util_info*) other->object.util)->line_map;
205     int cur_chunk = 0;
206     int i1, i2;
207
208     if(p->num && DEBUG)
209         print_patch(p);
210
211     for(i1 = 0; i1 < num_lines; i1++)
212         line_map[i1] = -1;
213
214     if(DEBUG)
215         printf("num lines 1: %d num lines 2: %d\n", num_lines, num_lines2);
216
217     for(i1 = 0, i2 = 0; i1 < num_lines; i1++, i2++) {
218         if(DEBUG > 1)
219             printf("%d %d\n", i1, i2);
220
221         if(i2 >= num_lines2)
222             break;
223
224         line_map[i1] = line_map2[i2];
225
226         struct chunk* chunk = NULL;
227         if(cur_chunk < p->num)
228             chunk = &p->chunks[cur_chunk];
229
230         if(chunk && chunk->off1 == i1) {
231             i2 = chunk->off2;
232
233             if(chunk->len1 > 0)
234                 i1 += chunk->len1-1;
235             if(chunk->len2 > 0)
236                 i2 += chunk->len2-1;
237             cur_chunk++;
238         }
239     }
240 }
241
242 int map_line(struct commit* commit, int line)
243 {
244     struct util_info* info = commit->object.util;
245     assert(line >= 0 && line < info->num_lines);
246     return info->line_map[line];
247 }
248
249 int fill_util_info(struct commit* commit, const char* path)
250 {
251     if(commit->object.util)
252         return 0;
253
254     struct util_info* util = xmalloc(sizeof(struct util_info));
255     util->buf = NULL;
256     util->size = 0;
257     util->num_lines = -1;
258     util->line_map = NULL;
259
260     commit->object.util = util;
261
262     if(get_blob_sha1(commit->tree, path, util->sha1))
263         return -1;
264
265     return 0;
266 }
267
268 void alloc_line_map(struct commit* commit)
269 {
270     struct util_info* util = commit->object.util;
271
272     if(util->line_map)
273         return;
274
275     get_blob(commit);
276
277     int i;
278     util->num_lines = 0;
279     for(i = 0; i < util->size; i++) {
280         if(util->buf[i] == '\n')
281             util->num_lines++;
282     }
283     util->line_map = xmalloc(sizeof(int)*util->num_lines);
284 }
285
286 void copy_line_map(struct commit* dst, struct commit* src)
287 {
288     struct util_info* u_dst = dst->object.util;
289     struct util_info* u_src = src->object.util;
290
291     u_dst->line_map = u_src->line_map;
292     u_dst->num_lines = u_src->num_lines;
293     u_dst->buf = u_src->buf;
294     u_dst->size = u_src->size;
295 }
296
297 void process_commits(struct commit_list* list, const char* path)
298 {
299     int i;
300
301     while(list) {
302         struct commit* commit = pop_commit(&list);
303         struct commit_list* parents;
304         struct util_info* info;
305
306         info = commit->object.util;
307         num_commits++;
308         if(DEBUG)
309             printf("\nProcessing commit: %d %s\n", num_commits, sha1_to_hex(commit->object.sha1));
310         for(parents = commit->parents;
311             parents != NULL; parents = parents->next) {
312             struct commit* parent = parents->item;
313
314             if(parse_commit(parent) < 0)
315                 die("parse_commit error");
316
317             if(DEBUG)
318                 printf("parent: %s\n", sha1_to_hex(parent->object.sha1));
319
320             if(fill_util_info(parent, path))
321                 continue;
322
323             // Temporarily assign everything to the parent.
324             int num_blame = 0;
325             for(i = 0; i < num_blame_lines; i++) {
326                 if(blame_lines[i] == commit) {
327                     num_blame++;
328                     blame_lines[i] = parent;
329                 }
330             }
331
332             if(num_blame == 0)
333                 continue;
334
335             struct patch* patch = get_patch(parent, commit);
336             if(patch->num == 0) {
337                 copy_line_map(parent, commit);
338             } else {
339                 alloc_line_map(parent);
340                 fill_line_map(parent, commit, patch);
341             }
342
343             for(i = 0; i < patch->num; i++) {
344                 int l;
345                 for(l = 0; l < patch->chunks[i].len2; l++) {
346                     int mapped_line = map_line(commit, patch->chunks[i].off2 + l);
347                     if(mapped_line != -1 && blame_lines[mapped_line] == parent)
348                         blame_lines[mapped_line] = commit;
349                 }
350             }
351             free_patch(patch);
352         }
353     }
354 }
355
356 #define SEEN 1
357 struct commit_list* get_commit_list(struct commit* commit, const char* pathname)
358 {
359     struct commit_list* ret = NULL;
360     struct commit_list* process = NULL;
361     unsigned char sha1[20];
362
363     commit_list_insert(commit, &process);
364
365     while(process) {
366         struct commit* com = pop_commit(&process);
367         if(com->object.flags & SEEN)
368             continue;
369
370         com->object.flags |= SEEN;
371         commit_list_insert(com, &ret);
372         struct commit_list* parents;
373
374         parse_commit(com);
375
376         for(parents = com->parents;
377             parents != NULL; parents = parents->next) {
378             struct commit* parent = parents->item;
379
380             parse_commit(parent);
381
382             if(!get_blob_sha1(parent->tree, pathname, sha1))
383                 commit_list_insert(parent, &process);
384         }
385     }
386
387     return ret;
388 }
389
390 int main(int argc, const char **argv)
391 {
392     unsigned char sha1[20];
393     struct commit *commit;
394     const char* filename;
395     int i;
396
397     setup_git_directory();
398
399     if (argc != 3)
400         die("Usage: blame commit-ish file");
401
402     if (get_sha1(argv[1], sha1))
403         die("get_sha1 failed");
404
405     commit = lookup_commit_reference(sha1);
406
407     filename = argv[2];
408
409     struct commit_list* list = get_commit_list(commit, filename);
410     sort_in_topological_order(&list, 1);
411
412     if(fill_util_info(commit, filename)) {
413         printf("%s not found in %s\n", filename, argv[1]);
414         return 0;
415     }
416     alloc_line_map(commit);
417
418     struct util_info* util = commit->object.util;
419     num_blame_lines = util->num_lines;
420     blame_lines = xmalloc(sizeof(struct commit*)*num_blame_lines);
421
422
423     for(i = 0; i < num_blame_lines; i++) {
424         blame_lines[i] = commit;
425
426         ((struct util_info*) commit->object.util)->line_map[i] = i;
427     }
428
429     process_commits(list, filename);
430
431     for(i = 0; i < num_blame_lines; i++) {
432         printf("%d %s\n", i+1-1, sha1_to_hex(blame_lines[i]->object.sha1));
433 //        printf("%d %s\n", i+1-1, find_unique_abbrev(blame_lines[i]->object.sha1, 6));
434     }
435
436     if(DEBUG) {
437         printf("num get patch: %d\n", num_get_patch);
438         printf("num commits: %d\n", num_commits);
439     }
440
441     return 0;
442 }