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