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 -u0 %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 char* format_time(unsigned long time, const char* tz)
 554 {
 555         static char time_buf[128];
 556         time_t t = time;
 557
 558         strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", gmtime(&t));
 559         strcat(time_buf, tz);
 560         return time_buf;
 561 }
 562
 563 int main(int argc, const char **argv)
 564 {
 565         int i;
 566         struct commit *initial = NULL;
 567         unsigned char sha1[20];
 568
 569         const char *filename = NULL, *commit = NULL;
 570         char filename_buf[256];
 571         int sha1_len = 8;
 572         int compability = 0;
 573         int options = 1;
 574
 575         int num_args;
 576         const char* args[10];
 577         struct rev_info rev;
 578
 579         struct commit_info ci;
 580         const char *buf;
 581         int max_digits;
 582
 583         const char* prefix = setup_git_directory();
 584
 585         for(i = 1; i < argc; i++) {
 586                 if(options) {
 587                         if(!strcmp(argv[i], "-h") ||
 588                            !strcmp(argv[i], "--help"))
 589                                 usage(blame_usage);
 590                         else if(!strcmp(argv[i], "-l") ||
 591                                 !strcmp(argv[i], "--long")) {
 592                                 sha1_len = 20;
 593                                 continue;
 594                         } else if(!strcmp(argv[i], "-c") ||
 595                                   !strcmp(argv[i], "--compability")) {
 596                                 compability = 1;
 597                                 continue;
 598                         } else if(!strcmp(argv[i], "--")) {
 599                                 options = 0;
 600                                 continue;
 601                         } else if(argv[i][0] == '-')
 602                                 usage(blame_usage);
 603                         else
 604                                 options = 0;
 605                 }
 606
 607                 if(!options) {
 608                         if(!filename)
 609                                 filename = argv[i];
 610                         else if(!commit)
 611                                 commit = argv[i];
 612                         else
 613                                 usage(blame_usage);
 614                 }
 615         }
 616
 617         if(!filename)
 618                 usage(blame_usage);
 619         if(!commit)
 620                 commit = "HEAD";
 621
 622         if(prefix)
 623                 sprintf(filename_buf, "%s%s", prefix, filename);
 624         else
 625                 strcpy(filename_buf, filename);
 626         filename = filename_buf;
 627
 628         {
 629                 struct commit* c;
 630                 if (get_sha1(commit, sha1))
 631                         die("get_sha1 failed, commit '%s' not found", commit);
 632                 c = lookup_commit_reference(sha1);
 633
 634                 if (fill_util_info(c, filename)) {
 635                         printf("%s not found in %s\n", filename, commit);
 636                         return 1;
 637                 }
 638         }
 639
 640         num_args = 0;
 641         args[num_args++] = NULL;
 642         args[num_args++] = "--topo-order";
 643         args[num_args++] = "--remove-empty";
 644         args[num_args++] = commit;
 645         args[num_args++] = "--";
 646         args[num_args++] = filename;
 647         args[num_args] = NULL;
 648
 649         setup_revisions(num_args, args, &rev, "HEAD");
 650         prepare_revision_walk(&rev);
 651         process_commits(&rev, filename, &initial);
 652
 653         buf = blame_contents;
 654         max_digits = 1 + log(num_blame_lines+1)/log(10);
 655         for (i = 0; i < num_blame_lines; i++) {
 656                 struct commit *c = blame_lines[i];
 657                 if (!c)
 658                         c = initial;
 659
 660                 get_commit_info(c, &ci);
 661                 fwrite(sha1_to_hex(c->object.sha1), sha1_len, 1, stdout);
 662                 if(compability)
 663                         printf("\t(%10s\t%10s\t%d)", ci.author,
 664                                format_time(ci.author_time, ci.author_tz), i+1);
 665                 else
 666                         printf(" (%-15.15s %10s %*d) ", ci.author,
 667                                format_time(ci.author_time, ci.author_tz),
 668                                max_digits, i+1);
 669
 670                 if(i == num_blame_lines - 1) {
 671                         fwrite(buf, blame_len - (buf - blame_contents),
 672                                1, stdout);
 673                         if(blame_contents[blame_len-1] != '\n')
 674                                 putc('\n', stdout);
 675                 } else {
 676                         char* next_buf = index(buf, '\n') + 1;
 677                         fwrite(buf, next_buf - buf, 1, stdout);
 678                         buf = next_buf;
 679                 }
 680         }
 681
 682         if (DEBUG) {
 683                 printf("num get patch: %d\n", num_get_patch);
 684                 printf("num commits: %d\n", num_commits);
 685                 printf("patch time: %f\n", patch_time / 1000000.0);
 686                 printf("initial: %s\n", sha1_to_hex(initial->object.sha1));
 687         }
 688
 689         return 0;
 690 }