{"thread":{"id":"3527","subject":"[PATCH] git-blame, take 2","startedAt":"2006-03-02T21:28:17Z","lastAt":"2006-03-02T21:45:18Z","messageCount":2,"participants":["Fredrik Kuivinen","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"17071","messageId":"20060302212816.GA11015@c165.ib.student.liu.se","threadId":"3527","inReplyTo":null,"subject":"[PATCH] git-blame, take 2","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-03-02T21:28:17Z","receivedAt":"2006-03-02T21:28:17Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nHere is an updated version of git-blame. The main changes compared to\nthe first version are:\n\n* Use the new revision.h interface to do the revision walking\n* Do the right thing in a lot of more cases than before. In particular\n  parallel development tracks are hopefully handled sanely.\n* Lots of clean-up\n\nIt still won't follow file renames though. The patch is against\ncurrent pu.\n\nThere are still some differences in the output between git-blame and\ngit-annotate. For example, in 'Makefile' git-blame assigns lines\n354-358 to 455a7f3275d264f6e66045b92c83747ec461dda5 and git-annotate\nassigns the same lines to 79a9d8ea0d88a3667ad19be8e705405ab5d896f1.\n\nI think git-blame is correct in this case. This patterns occur in\nseveral other places, git-annotate seems to sometimes assign lines to\nmerge commits when the lines actually changed in some other commit\nwhich precedes the merge.\n\n- Fredrik\n\n\nSigned-off-by: Fredrik Kuivinen <freku045@student.liu.se>\n\n\n---\n\n blame.c |  888 ++++++++++++++++++++++++++++++++++++---------------------------\n 1 files changed, 504 insertions(+), 384 deletions(-)\n\n3a81d6759da19a4776102a405505f35811320d61\ndiff --git a/blame.c b/blame.c\nindex dbce7e2..0b5d6bd 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1,4 +1,10 @@\n+/*\n+ * Copyright (C) 2006, Fredrik Kuivinen <freku045@student.liu.se>\n+ */\n+\n #include <assert.h>\n+#include <time.h>\n+#include <sys/time.h>\n \n #include \"cache.h\"\n #include \"refs.h\"\n@@ -7,436 +13,550 @@\n #include \"tree.h\"\n #include \"blob.h\"\n #include \"diff.h\"\n+#include \"revision.h\"\n \n #define DEBUG 0\n \n-struct commit** blame_lines;\n+struct commit **blame_lines;\n int num_blame_lines;\n \n-struct util_info\n-{\n-    int* line_map;\n-    int num_lines;\n-    unsigned char sha1[20]; /* blob sha, not commit! */\n-    char* buf;\n-    unsigned long size;\n+struct util_info {\n+\tint *line_map;\n+\tunsigned char sha1[20];\t/* blob sha, not commit! */\n+\tchar *buf;\n+\tunsigned long size;\n+\tint num_lines;\n //    const char* path;\n };\n \n-struct chunk\n-{\n-    int off1, len1; // ---\n-    int off2, len2; // +++\n+struct chunk {\n+\tint off1, len1;\t// ---\n+\tint off2, len2;\t// +++\n };\n \n-struct patch\n-{\n-    struct chunk* chunks;\n-    int num;\n+struct patch {\n+\tstruct chunk *chunks;\n+\tint num;\n };\n \n-static void get_blob(struct commit* commit);\n-\n-int num_get_patch = 0;\n-int num_commits = 0;\n-\n-struct patch* get_patch(struct commit* commit, struct commit* other)\n-{\n-    struct patch* ret = xmalloc(sizeof(struct patch));\n-    ret->chunks = NULL;\n-    ret->num = 0;\n-\n-    struct util_info* info_c = (struct util_info*) commit->object.util;\n-    struct util_info* info_o = (struct util_info*) other->object.util;\n-\n-    if(!memcmp(info_c->sha1, info_o->sha1, 20))\n-        return ret;\n-\n-    get_blob(commit);\n-    get_blob(other);\n-\n-    FILE* fout = fopen(\"/tmp/git-blame-tmp1\", \"w\");\n-    if(!fout)\n-        die(\"fopen tmp1 failed: %s\", strerror(errno));\n-\n-    if(fwrite(info_c->buf, info_c->size, 1, fout) != 1)\n-        die(\"fwrite 1 failed: %s\", strerror(errno));\n-    fclose(fout);\n-\n-    fout = fopen(\"/tmp/git-blame-tmp2\", \"w\");\n-    if(!fout)\n-        die(\"fopen tmp2 failed: %s\", strerror(errno));\n-\n-    if(fwrite(info_o->buf, info_o->size, 1, fout) != 1)\n-        die(\"fwrite 2 failed: %s\", strerror(errno));\n-    fclose(fout);\n-\n-    FILE* fin = popen(\"diff -u0 /tmp/git-blame-tmp1 /tmp/git-blame-tmp2\", \"r\");\n-    if(!fin)\n-        die(\"popen failed: %s\", strerror(errno));\n-\n-    char buf[1024];\n-    while(fgets(buf, sizeof(buf), fin)) {\n-        if(buf[0] != '@' || buf[1] != '@')\n-            continue;\n-\n-        if(DEBUG)\n-            printf(\"chunk line: %s\", buf);\n-        ret->num++;\n-        ret->chunks = xrealloc(ret->chunks, sizeof(struct chunk)*ret->num);\n-        struct chunk* chunk = &ret->chunks[ret->num-1];\n-\n-        assert(!strncmp(buf, \"@@ -\", 4));\n-\n-        char* start = buf+4;\n-        char* sp = index(start, ' ');\n-        *sp = '\\0';\n-        if(index(start, ',')) {\n-            int ret = sscanf(start, \"%d,%d\", &chunk->off1, &chunk->len1);\n-            assert(ret == 2);\n-        } else {\n-            int ret = sscanf(start, \"%d\", &chunk->off1);\n-            assert(ret == 1);\n-            chunk->len1 = 1;\n-        }\n-        *sp = ' ';\n-\n-        start = sp+1;\n-        sp = index(start, ' ');\n-        *sp = '\\0';\n-        if(index(start, ',')) {\n-            int ret = sscanf(start, \"%d,%d\", &chunk->off2, &chunk->len2);\n-            assert(ret == 2);\n-        } else {\n-            int ret = sscanf(start, \"%d\", &chunk->off2);\n-            assert(ret == 1);\n-            chunk->len2 = 1;\n-        }\n-        *sp = ' ';\n-\n-        if(chunk->off1 > 0)\n-            chunk->off1 -= 1;\n-        if(chunk->off2 > 0)\n-            chunk->off2 -= 1;\n-\n-        assert(chunk->off1 >= 0);\n-        assert(chunk->off2 >= 0);\n-    }\n-    fclose(fin);\n-\n-    num_get_patch++;\n-    return ret;\n-}\n-\n-void free_patch(struct patch* p)\n-{\n-    free(p->chunks);\n-    free(p);\n-}\n-\n-static int get_blob_sha1_internal(unsigned char *sha1, const char *base, int baselen,\n-                                  const char *pathname, unsigned mode, int stage);\n+static void get_blob(struct commit *commit);\n \n+/* Only used for statistics */\n+static int num_get_patch = 0;\n+static int num_commits = 0;\n+static int patch_time = 0;\n+\n+#define TEMPFILE_PATH_LEN 60\n+static struct patch *get_patch(struct commit *commit, struct commit *other)\n+{\n+\tstruct patch *ret;\n+\tstruct util_info *info_c = (struct util_info *)commit->object.util;\n+\tstruct util_info *info_o = (struct util_info *)other->object.util;\n+\tchar tmp_path1[TEMPFILE_PATH_LEN], tmp_path2[TEMPFILE_PATH_LEN];\n+\tchar diff_cmd[TEMPFILE_PATH_LEN*2 + 20];\n+\tstruct timeval tv_start, tv_end;\n+\tint fd;\n+\tFILE *fin;\n+\tchar buf[1024];\n+\t\n+\tret = xmalloc(sizeof(struct patch));\n+\tret->chunks = NULL;\n+\tret->num = 0;\n+\n+\tget_blob(commit);\n+\tget_blob(other);\n+\n+\tgettimeofday(&tv_start, NULL);\n+\n+\tfd = git_mkstemp(tmp_path1, TEMPFILE_PATH_LEN, \"git-blame-XXXXXX\");\n+\tif (fd < 0)\n+\t\tdie(\"unable to create temp-file: %s\", strerror(errno));\n+\n+\tif (xwrite(fd, info_c->buf, info_c->size) != info_c->size)\n+\t\tdie(\"write failed: %s\", strerror(errno));\n+\tclose(fd);\n+\n+\tfd = git_mkstemp(tmp_path2, TEMPFILE_PATH_LEN, \"git-blame-XXXXXX\");\n+\tif (fd < 0)\n+\t\tdie(\"unable to create temp-file: %s\", strerror(errno));\n+\n+\tif (xwrite(fd, info_o->buf, info_o->size) != info_o->size)\n+\t\tdie(\"write failed: %s\", strerror(errno));\n+\tclose(fd);\n+\n+\tsprintf(diff_cmd, \"diff -u0 %s %s\", tmp_path1, tmp_path2);\n+\tfin = popen(diff_cmd, \"r\");\n+\tif (!fin)\n+\t\tdie(\"popen failed: %s\", strerror(errno));\n+\n+\twhile (fgets(buf, sizeof(buf), fin)) {\n+\t\tstruct chunk *chunk;\n+\t\tchar *start, *sp;\n+\t\t\n+\t\tif (buf[0] != '@' || buf[1] != '@')\n+\t\t\tcontinue;\n+\n+\t\tif (DEBUG)\n+\t\t\tprintf(\"chunk line: %s\", buf);\n+\t\tret->num++;\n+\t\tret->chunks = xrealloc(ret->chunks,\n+\t\t\t\t       sizeof(struct chunk) * ret->num);\n+\t\tchunk = &ret->chunks[ret->num - 1];\n+\n+\t\tassert(!strncmp(buf, \"@@ -\", 4));\n+\n+\t\tstart = buf + 4;\n+\t\tsp = index(start, ' ');\n+\t\t*sp = '\\0';\n+\t\tif (index(start, ',')) {\n+\t\t\tint ret =\n+\t\t\t    sscanf(start, \"%d,%d\", &chunk->off1, &chunk->len1);\n+\t\t\tassert(ret == 2);\n+\t\t} else {\n+\t\t\tint ret = sscanf(start, \"%d\", &chunk->off1);\n+\t\t\tassert(ret == 1);\n+\t\t\tchunk->len1 = 1;\n+\t\t}\n+\t\t*sp = ' ';\n+\n+\t\tstart = sp + 1;\n+\t\tsp = index(start, ' ');\n+\t\t*sp = '\\0';\n+\t\tif (index(start, ',')) {\n+\t\t\tint ret =\n+\t\t\t    sscanf(start, \"%d,%d\", &chunk->off2, &chunk->len2);\n+\t\t\tassert(ret == 2);\n+\t\t} else {\n+\t\t\tint ret = sscanf(start, \"%d\", &chunk->off2);\n+\t\t\tassert(ret == 1);\n+\t\t\tchunk->len2 = 1;\n+\t\t}\n+\t\t*sp = ' ';\n+\n+\t\tif (chunk->len1 == 0)\n+\t\t\tchunk->off1++;\n+\t\tif (chunk->len2 == 0)\n+\t\t\tchunk->off2++;\n+\n+\t\tif (chunk->off1 > 0)\n+\t\t\tchunk->off1--;\n+\t\tif (chunk->off2 > 0)\n+\t\t\tchunk->off2--;\n+\n+\t\tassert(chunk->off1 >= 0);\n+\t\tassert(chunk->off2 >= 0);\n+\t}\n+\tpclose(fin);\n+\tunlink(tmp_path1);\n+\tunlink(tmp_path2);\n+\t\n+\tgettimeofday(&tv_end, NULL);\n+\tpatch_time += 1000000 * (tv_end.tv_sec - tv_start.tv_sec) +\n+\t\ttv_end.tv_usec - tv_start.tv_usec;\n+\n+\tnum_get_patch++;\n+\treturn ret;\n+}\n+\n+static void free_patch(struct patch *p)\n+{\n+\tfree(p->chunks);\n+\tfree(p);\n+}\n+\n+static int get_blob_sha1_internal(unsigned char *sha1, const char *base,\n+\t\t\t\t  int baselen, const char *pathname,\n+\t\t\t\t  unsigned mode, int stage);\n \n static unsigned char blob_sha1[20];\n-static int get_blob_sha1(struct tree* t, const char* pathname, unsigned char* sha1)\n+static int get_blob_sha1(struct tree *t, const char *pathname,\n+\t\t\t unsigned char *sha1)\n {\n-    const char *pathspec[2];\n-    pathspec[0] = pathname;\n-    pathspec[1] = NULL;\n-    memset(blob_sha1, 0, sizeof(blob_sha1));\n-    read_tree_recursive(t, \"\", 0, 0, pathspec, get_blob_sha1_internal);\n+\tint i;\n+\tconst char *pathspec[2];\n+\tpathspec[0] = pathname;\n+\tpathspec[1] = NULL;\n+\tmemset(blob_sha1, 0, sizeof(blob_sha1));\n+\tread_tree_recursive(t, \"\", 0, 0, pathspec, get_blob_sha1_internal);\n \n-    int i;\n-    for(i = 0; i < 20; i++) {\n-        if(blob_sha1[i] != 0)\n-            break;\n-    }\n+\tfor (i = 0; i < 20; i++) {\n+\t\tif (blob_sha1[i] != 0)\n+\t\t\tbreak;\n+\t}\n \n-    if(i == 20)\n-        return -1;\n+\tif (i == 20)\n+\t\treturn -1;\n \n-    memcpy(sha1, blob_sha1, 20);\n-    return 0;\n+\tmemcpy(sha1, blob_sha1, 20);\n+\treturn 0;\n }\n \n-static int get_blob_sha1_internal(unsigned char *sha1, const char *base, int baselen,\n-                                  const char *pathname, unsigned mode, int stage)\n+static int get_blob_sha1_internal(unsigned char *sha1, const char *base,\n+\t\t\t\t  int baselen, const char *pathname,\n+\t\t\t\t  unsigned mode, int stage)\n {\n-//    printf(\"Got blob: %s base: '%s' baselen: %d pathname: '%s' mode: %o stage: %d\\n\",\n-//           sha1_to_hex(sha1), base, baselen, pathname, mode, stage);\n-\n-    if(S_ISDIR(mode))\n-        return READ_TREE_RECURSIVE;\n+\tif (S_ISDIR(mode))\n+\t\treturn READ_TREE_RECURSIVE;\n \n-    memcpy(blob_sha1, sha1, 20);\n-    return -1;\n+\tmemcpy(blob_sha1, sha1, 20);\n+\treturn -1;\n }\n \n-static void get_blob(struct commit* commit)\n+static void get_blob(struct commit *commit)\n {\n-    struct util_info* info = commit->object.util;\n-    char type[20];\n+\tstruct util_info *info = commit->object.util;\n+\tchar type[20];\n \n-    if(info->buf)\n-        return;\n+\tif (info->buf)\n+\t\treturn;\n \n-    info->buf = read_sha1_file(info->sha1, type, &info->size);\n-    assert(!strcmp(type, \"blob\"));\n-}\n+\tinfo->buf = read_sha1_file(info->sha1, type, &info->size);\n \n-void print_patch(struct patch* p)\n-{\n-    printf(\"Num chunks: %d\\n\", p->num);\n-    int i;\n-    for(i = 0; i < p->num; i++) {\n-        printf(\"%d,%d %d,%d\\n\", p->chunks[i].off1, p->chunks[i].len1, p->chunks[i].off2, p->chunks[i].len2);\n-    }\n+\tassert(!strcmp(type, \"blob\"));\n }\n \n-\n-// p is a patch from commit to other.\n-void fill_line_map(struct commit* commit, struct commit* other, struct patch* p)\n+/* For debugging only */\n+static void print_patch(struct patch *p)\n {\n-    int num_lines = ((struct util_info*) commit->object.util)->num_lines;\n-    int* line_map = ((struct util_info*) commit->object.util)->line_map;\n-    int num_lines2 = ((struct util_info*) other->object.util)->num_lines;\n-    int* line_map2 = ((struct util_info*) other->object.util)->line_map;\n-    int cur_chunk = 0;\n-    int i1, i2;\n-\n-    if(p->num && DEBUG)\n-        print_patch(p);\n-\n-    for(i1 = 0; i1 < num_lines; i1++)\n-        line_map[i1] = -1;\n-\n-    if(DEBUG)\n-        printf(\"num lines 1: %d num lines 2: %d\\n\", num_lines, num_lines2);\n-\n-    for(i1 = 0, i2 = 0; i1 < num_lines; i1++, i2++) {\n-        if(DEBUG > 1)\n-            printf(\"%d %d\\n\", i1, i2);\n-\n-        if(i2 >= num_lines2)\n-            break;\n-\n-        line_map[i1] = line_map2[i2];\n-\n-        struct chunk* chunk = NULL;\n-        if(cur_chunk < p->num)\n-            chunk = &p->chunks[cur_chunk];\n-\n-        if(chunk && chunk->off1 == i1) {\n-            i2 = chunk->off2;\n-\n-            if(chunk->len1 > 0)\n-                i1 += chunk->len1-1;\n-            if(chunk->len2 > 0)\n-                i2 += chunk->len2-1;\n-            cur_chunk++;\n-        }\n-    }\n-}\n-\n-int map_line(struct commit* commit, int line)\n-{\n-    struct util_info* info = commit->object.util;\n-    assert(line >= 0 && line < info->num_lines);\n-    return info->line_map[line];\n+\tint i;\n+\tprintf(\"Num chunks: %d\\n\", p->num);\n+\tfor (i = 0; i < p->num; i++) {\n+\t\tprintf(\"%d,%d %d,%d\\n\", p->chunks[i].off1, p->chunks[i].len1,\n+\t\t       p->chunks[i].off2, p->chunks[i].len2);\n+\t}\n }\n \n-int fill_util_info(struct commit* commit, const char* path)\n+/* For debugging only */\n+static void print_map(struct commit *cmit, struct commit *other)\n {\n-    if(commit->object.util)\n-        return 0;\n-\n-    struct util_info* util = xmalloc(sizeof(struct util_info));\n-    util->buf = NULL;\n-    util->size = 0;\n-    util->num_lines = -1;\n-    util->line_map = NULL;\n+\tstruct util_info *util = cmit->object.util;\n+\tstruct util_info *util2 = other->object.util;\n \n-    commit->object.util = util;\n+\tint i;\n+\tint max =\n+\t    util->num_lines >\n+\t    util2->num_lines ? util->num_lines : util2->num_lines;\n+\tint num;\n \n-    if(get_blob_sha1(commit->tree, path, util->sha1))\n-        return -1;\n+\tfor (i = 0; i < max; i++) {\n+\t\tprintf(\"i: %d \", i);\n+\t\tnum = -1;\n \n-    return 0;\n-}\n-\n-void alloc_line_map(struct commit* commit)\n-{\n-    struct util_info* util = commit->object.util;\n+\t\tif (i < util->num_lines) {\n+\t\t\tnum = util->line_map[i];\n+\t\t\tprintf(\"%d\\t\", num);\n+\t\t} else\n+\t\t\tprintf(\"\\t\");\n \n-    if(util->line_map)\n-        return;\n+\t\tif (i < util2->num_lines) {\n+\t\t\tint num2 = util2->line_map[i];\n+\t\t\tprintf(\"%d\\t\", num2);\n+\t\t\tif (num != -1 && num2 != num)\n+\t\t\t\tprintf(\"---\");\n+\t\t} else\n+\t\t\tprintf(\"\\t\");\n \n-    get_blob(commit);\n-\n-    int i;\n-    util->num_lines = 0;\n-    for(i = 0; i < util->size; i++) {\n-        if(util->buf[i] == '\\n')\n-            util->num_lines++;\n-    }\n-    util->line_map = xmalloc(sizeof(int)*util->num_lines);\n+\t\tprintf(\"\\n\");\n+\t}\n }\n \n-void copy_line_map(struct commit* dst, struct commit* src)\n-{\n-    struct util_info* u_dst = dst->object.util;\n-    struct util_info* u_src = src->object.util;\n-\n-    u_dst->line_map = u_src->line_map;\n-    u_dst->num_lines = u_src->num_lines;\n-    u_dst->buf = u_src->buf;\n-    u_dst->size = u_src->size;\n-}\n-\n-void process_commits(struct commit_list* list, const char* path)\n-{\n-    int i;\n-\n-    while(list) {\n-        struct commit* commit = pop_commit(&list);\n-        struct commit_list* parents;\n-        struct util_info* info;\n-\n-        info = commit->object.util;\n-        num_commits++;\n-        if(DEBUG)\n-            printf(\"\\nProcessing commit: %d %s\\n\", num_commits, sha1_to_hex(commit->object.sha1));\n-        for(parents = commit->parents;\n-            parents != NULL; parents = parents->next) {\n-            struct commit* parent = parents->item;\n-\n-            if(parse_commit(parent) < 0)\n-                die(\"parse_commit error\");\n-\n-            if(DEBUG)\n-                printf(\"parent: %s\\n\", sha1_to_hex(parent->object.sha1));\n-\n-            if(fill_util_info(parent, path))\n-                continue;\n-\n-            // Temporarily assign everything to the parent.\n-            int num_blame = 0;\n-            for(i = 0; i < num_blame_lines; i++) {\n-                if(blame_lines[i] == commit) {\n-                    num_blame++;\n-                    blame_lines[i] = parent;\n-                }\n-            }\n-\n-            if(num_blame == 0)\n-                continue;\n-\n-            struct patch* patch = get_patch(parent, commit);\n-            if(patch->num == 0) {\n-                copy_line_map(parent, commit);\n-            } else {\n-                alloc_line_map(parent);\n-                fill_line_map(parent, commit, patch);\n-            }\n-\n-            for(i = 0; i < patch->num; i++) {\n-                int l;\n-                for(l = 0; l < patch->chunks[i].len2; l++) {\n-                    int mapped_line = map_line(commit, patch->chunks[i].off2 + l);\n-                    if(mapped_line != -1 && blame_lines[mapped_line] == parent)\n-                        blame_lines[mapped_line] = commit;\n-                }\n-            }\n-            free_patch(patch);\n-        }\n-    }\n-}\n-\n-#define SEEN 1\n-struct commit_list* get_commit_list(struct commit* commit, const char* pathname)\n+// p is a patch from commit to other.\n+static void fill_line_map(struct commit *commit, struct commit *other,\n+\t\t\t  struct patch *p)\n {\n-    struct commit_list* ret = NULL;\n-    struct commit_list* process = NULL;\n-    unsigned char sha1[20];\n-\n-    commit_list_insert(commit, &process);\n-\n-    while(process) {\n-        struct commit* com = pop_commit(&process);\n-        if(com->object.flags & SEEN)\n-            continue;\n-\n-        com->object.flags |= SEEN;\n-        commit_list_insert(com, &ret);\n-        struct commit_list* parents;\n-\n-        parse_commit(com);\n-\n-        for(parents = com->parents;\n-            parents != NULL; parents = parents->next) {\n-            struct commit* parent = parents->item;\n-\n-            parse_commit(parent);\n-\n-            if(!get_blob_sha1(parent->tree, pathname, sha1))\n-                commit_list_insert(parent, &process);\n-        }\n-    }\n-\n-    return ret;\n+\tstruct util_info *util = commit->object.util;\n+\tstruct util_info *util2 = other->object.util;\n+\tint *map = util->line_map;\n+\tint *map2 = util2->line_map;\n+\tint cur_chunk = 0;\n+\tint i1, i2;\n+\n+\tif (p->num && DEBUG)\n+\t\tprint_patch(p);\n+\n+\tif (DEBUG)\n+\t\tprintf(\"num lines 1: %d num lines 2: %d\\n\", util->num_lines,\n+\t\t       util2->num_lines);\n+\n+\tfor (i1 = 0, i2 = 0; i1 < util->num_lines; i1++, i2++) {\n+\t\tstruct chunk *chunk = NULL;\n+\t\tif (cur_chunk < p->num)\n+\t\t\tchunk = &p->chunks[cur_chunk];\n+\n+\t\tif (chunk && chunk->off1 == i1) {\n+\t\t\tif (DEBUG && i2 != chunk->off2)\n+\t\t\t\tprintf(\"i2: %d off2: %d\\n\", i2, chunk->off2);\n+\n+\t\t\tassert(i2 == chunk->off2);\n+\n+\t\t\ti1--;\n+\t\t\ti2--;\n+\t\t\tif (chunk->len1 > 0)\n+\t\t\t\ti1 += chunk->len1;\n+\t\t\t\n+\t\t\tif (chunk->len2 > 0)\n+\t\t\t\ti2 += chunk->len2;\n+\n+\t\t\tcur_chunk++;\n+\t\t} else {\n+\t\t\tif (i2 >= util2->num_lines)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (map[i1] != map2[i2] && map[i1] != -1) {\n+\t\t\t\tif (DEBUG)\n+\t\t\t\t\tprintf(\"map: i1: %d %d %p i2: %d %d %p\\n\",\n+\t\t\t\t\t       i1, map[i1],\n+\t\t\t\t\t       i1 != -1 ? blame_lines[map[i1]] : NULL,\n+\t\t\t\t\t       i2, map2[i2],\n+\t\t\t\t\t       i2 != -1 ? blame_lines[map2[i2]] : NULL);\n+\t\t\t\tif (map2[i2] != -1 &&\n+\t\t\t\t    blame_lines[map[i1]] &&\n+\t\t\t\t    !blame_lines[map2[i2]])\n+\t\t\t\t\tmap[i1] = map2[i2];\n+\t\t\t}\n+\n+\t\t\tif (map[i1] == -1 && map2[i2] != -1)\n+\t\t\t\tmap[i1] = map2[i2];\n+\t\t}\n+\n+\t\tif (DEBUG > 1)\n+\t\t\tprintf(\"l1: %d l2: %d i1: %d i2: %d\\n\",\n+\t\t\t       map[i1], map2[i2], i1, i2);\n+\t}\n+}\n+\n+static int map_line(struct commit *commit, int line)\n+{\n+\tstruct util_info *info = commit->object.util;\n+\tassert(line >= 0 && line < info->num_lines);\n+\treturn info->line_map[line];\n+}\n+\n+static int fill_util_info(struct commit *commit, const char *path)\n+{\n+\tstruct util_info *util;\n+\tif (commit->object.util)\n+\t\treturn 0;\n+\n+\tutil = xmalloc(sizeof(struct util_info));\n+\n+\tif (get_blob_sha1(commit->tree, path, util->sha1)) {\n+\t\tfree(util);\n+\t\treturn 1;\n+\t} else {\n+\t\tutil->buf = NULL;\n+\t\tutil->size = 0;\n+\t\tutil->line_map = NULL;\n+\t\tutil->num_lines = -1;\n+\t\tcommit->object.util = util;\n+\t\treturn 0;\n+\t}\n+}\n+\n+static void alloc_line_map(struct commit *commit)\n+{\n+\tstruct util_info *util = commit->object.util;\n+\tint i;\n+\n+\tif (util->line_map)\n+\t\treturn;\n+\n+\tget_blob(commit);\n+\n+\tutil->num_lines = 0;\n+\tfor (i = 0; i < util->size; i++) {\n+\t\tif (util->buf[i] == '\\n')\n+\t\t\tutil->num_lines++;\n+\t}\n+\tif(util->buf[util->size - 1] != '\\n')\n+\t\tutil->num_lines++;\n+\t\n+\tutil->line_map = xmalloc(sizeof(int) * util->num_lines);\n+\n+\tfor (i = 0; i < util->num_lines; i++)\n+\t\tutil->line_map[i] = -1;\n+}\n+\n+static void init_first_commit(struct commit* commit, const char* filename)\n+{\n+\tstruct util_info* util;\n+\tint i;\n+\t\n+\tif (fill_util_info(commit, filename))\n+\t\tdie(\"fill_util_info failed\");\n+\n+\talloc_line_map(commit);\n+\n+\tutil = commit->object.util;\n+\tnum_blame_lines = util->num_lines;\n+\n+\tfor (i = 0; i < num_blame_lines; i++)\n+\t\tutil->line_map[i] = i;\n+}\n+\n+\n+static void process_commits(struct rev_info *rev, const char *path,\n+\t\t\t    struct commit** initial)\n+{\n+\tint i;\n+\tstruct util_info* util;\n+\tint lines_left;\n+\tint *blame_p;\n+\tint *new_lines;\n+\tint new_lines_len;\n+\n+\tstruct commit* commit = get_revision(rev);\n+\tassert(commit);\n+\tinit_first_commit(commit, path);\n+\n+\tutil = commit->object.util;\n+\tnum_blame_lines = util->num_lines;\n+\tblame_lines = xmalloc(sizeof(struct commit *) * num_blame_lines);\n+\tfor (i = 0; i < num_blame_lines; i++)\n+\t\tblame_lines[i] = NULL;\n+\n+\tlines_left = num_blame_lines;\n+\tblame_p = xmalloc(sizeof(int) * num_blame_lines);\n+\tnew_lines = xmalloc(sizeof(int) * num_blame_lines);\n+\tdo {\n+\t\tstruct commit_list *parents;\n+\t\tint num_parents;\n+\t\tstruct util_info *util;\n+\n+\t\tif (DEBUG)\n+\t\t\tprintf(\"\\nProcessing commit: %d %s\\n\", num_commits,\n+\t\t\t       sha1_to_hex(commit->object.sha1));\n+\n+\t\tif (lines_left == 0)\n+\t\t\treturn;\n+\n+\t\tnum_commits++;\n+\t\tmemset(blame_p, 0, sizeof(int) * num_blame_lines);\n+\t\tnew_lines_len = 0;\n+\t\tnum_parents = 0;\n+\t\tfor (parents = commit->parents;\n+\t\t     parents != NULL; parents = parents->next)\n+\t\t\tnum_parents++;\n+\n+\t\tif(num_parents == 0)\n+\t\t\t*initial = commit;\n+\n+\t\tif(fill_util_info(commit, path))\n+\t\t\tcontinue;\n+\n+\t\talloc_line_map(commit);\n+\t\tutil = commit->object.util;\n+\n+\t\tfor (parents = commit->parents;\n+\t\t     parents != NULL; parents = parents->next) {\n+\t\t\tstruct commit *parent = parents->item;\n+\t\t\tstruct patch *patch;\n+\t\t\t\n+\t\t\tif (parse_commit(parent) < 0)\n+\t\t\t\tdie(\"parse_commit error\");\n+\n+\t\t\tif (DEBUG)\n+\t\t\t\tprintf(\"parent: %s\\n\",\n+\t\t\t\t       sha1_to_hex(parent->object.sha1));\n+\n+\t\t\tif(fill_util_info(parent, path)) {\n+\t\t\t\tnum_parents--;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\t\n+\t\t\tpatch = get_patch(parent, commit);\n+                        alloc_line_map(parent);\n+                        fill_line_map(parent, commit, patch);\n+                        \n+                        for (i = 0; i < patch->num; i++) {\n+                            int l;\n+                            for (l = 0; l < patch->chunks[i].len2; l++) {\n+                                int mapped_line =\n+                                    map_line(commit, patch->chunks[i].off2 + l);\n+                                if (mapped_line != -1) {\n+                                    blame_p[mapped_line]++;\n+                                    if (blame_p[mapped_line] == num_parents)\n+                                        new_lines[new_lines_len++] = mapped_line;\n+                                }\n+                            }\n+\t\t\t}\n+                        free_patch(patch);\n+\t\t}\n+\n+\t\tif (DEBUG)\n+\t\t\tprintf(\"parents: %d\\n\", num_parents);\n+\n+\t\tfor (i = 0; i < new_lines_len; i++) {\n+\t\t\tint mapped_line = new_lines[i];\n+\t\t\tif (blame_lines[mapped_line] == NULL) {\n+\t\t\t\tblame_lines[mapped_line] = commit;\n+\t\t\t\tlines_left--;\n+\t\t\t\tif (DEBUG)\n+\t\t\t\t\tprintf(\"blame: mapped: %d i: %d\\n\",\n+\t\t\t\t\t       mapped_line, i);\n+\t\t\t}\n+\t\t}\n+\t} while ((commit = get_revision(rev)) != NULL);\n }\n \n int main(int argc, const char **argv)\n {\n-    unsigned char sha1[20];\n-    struct commit *commit;\n-    const char* filename;\n-    int i;\n-\n-    setup_git_directory();\n-\n-    if (argc != 3)\n-        die(\"Usage: blame commit-ish file\");\n-\n-    if (get_sha1(argv[1], sha1))\n-        die(\"get_sha1 failed\");\n-\n-    commit = lookup_commit_reference(sha1);\n-\n-    filename = argv[2];\n-\n-    struct commit_list* list = get_commit_list(commit, filename);\n-    sort_in_topological_order(&list, 1);\n-\n-    if(fill_util_info(commit, filename)) {\n-        printf(\"%s not found in %s\\n\", filename, argv[1]);\n-        return 0;\n-    }\n-    alloc_line_map(commit);\n-\n-    struct util_info* util = commit->object.util;\n-    num_blame_lines = util->num_lines;\n-    blame_lines = xmalloc(sizeof(struct commit*)*num_blame_lines);\n-\n-\n-    for(i = 0; i < num_blame_lines; i++) {\n-        blame_lines[i] = commit;\n-\n-        ((struct util_info*) commit->object.util)->line_map[i] = i;\n-    }\n-\n-    process_commits(list, filename);\n-\n-    for(i = 0; i < num_blame_lines; i++) {\n-        printf(\"%d %s\\n\", i+1-1, sha1_to_hex(blame_lines[i]->object.sha1));\n-//        printf(\"%d %s\\n\", i+1-1, find_unique_abbrev(blame_lines[i]->object.sha1, 6));\n-    }\n-\n-    if(DEBUG) {\n-        printf(\"num get patch: %d\\n\", num_get_patch);\n-        printf(\"num commits: %d\\n\", num_commits);\n-    }\n+\tint i;\n+\tstruct commit *initial = NULL;\n+\tunsigned char sha1[20];\n+\tconst char* filename;\n+\tint num_args;\n+\tconst char* args[10];\n+\tstruct rev_info rev;\n+\t\n+\tsetup_git_directory();\n+\n+\tif (argc != 3)\n+\t\tdie(\"Usage: blame commit-ish file\");\n+\n+\n+\tfilename = argv[2];\t\n+\t\n+\t{\n+\t\tstruct commit* commit;\n+\t\tif (get_sha1(argv[1], sha1))\n+\t\t\tdie(\"get_sha1 failed\");\t\n+\t\tcommit = lookup_commit_reference(sha1);\n+\n+\t\tif (fill_util_info(commit, filename)) {\n+\t\t\tprintf(\"%s not found in %s\\n\", filename, argv[1]);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tnum_args = 0;\n+\targs[num_args++] = NULL;\n+\targs[num_args++] = \"--topo-order\";\n+\targs[num_args++] = \"--remove-empty\";\n+\targs[num_args++] = argv[1];\n+\targs[num_args++] = \"--\";\n+\targs[num_args++] = filename;\n+\targs[num_args] = NULL;\n+\t\n+\tsetup_revisions(num_args, args, &rev, \"HEAD\");\n+\tprepare_revision_walk(&rev);\n+\tprocess_commits(&rev, filename, &initial);\n+\n+\tfor (i = 0; i < num_blame_lines; i++) {\n+\t\tstruct commit *c = blame_lines[i];\n+\t\tif (!c)\n+\t\t\tc = initial;\n+\n+\t\tprintf(\"%d %.8s\\n\", i, sha1_to_hex(c->object.sha1));\n+// printf(\"%d %s\\n\", i, find_unique_abbrev(blame_lines[i]->object.sha1, 6));\n+\t}\n+\n+\tif (DEBUG) {\n+\t\tprintf(\"num get patch: %d\\n\", num_get_patch);\n+\t\tprintf(\"num commits: %d\\n\", num_commits);\n+\t\tprintf(\"patch time: %f\\n\", patch_time / 1000000.0);\n+\t\tprintf(\"initial: %s\\n\", sha1_to_hex(initial->object.sha1));\n+\t}\n \n-    return 0;\n+\treturn 0;\n }\n-- \n1.2.4.g90ab-dirty\n"},{"id":"17072","messageId":"Pine.LNX.4.64.0603021338130.22647@g5.osdl.org","threadId":"3527","inReplyTo":"20060302212816.GA11015@c165.ib.student.liu.se","subject":"Re: [PATCH] git-blame, take 2","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-02T21:45:18Z","receivedAt":"2006-03-02T21:45:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 2 Mar 2006, Fredrik Kuivinen wrote:\n> \n> Here is an updated version of git-blame. The main changes compared to\n> the first version are:\n> \n> * Use the new revision.h interface to do the revision walking\n...\n> +\n> +\tnum_args = 0;\n> +\targs[num_args++] = NULL;\n> +\targs[num_args++] = \"--topo-order\";\n> +\targs[num_args++] = \"--remove-empty\";\n> +\targs[num_args++] = argv[1];\n> +\targs[num_args++] = \"--\";\n> +\targs[num_args++] = filename;\n> +\targs[num_args] = NULL;\n> +\t\n> +\tsetup_revisions(num_args, args, &rev, \"HEAD\");\n\nOk, that wasn't really supposed to be necessary.\n\nI guess the above works fine, but it should be perfectly fine to also just \ndo a nicer helper function that just initializes rev_info with something \nlike\n\n\tmemset(revs, 0, sizeof(*revs));\n\trevs->max_count = -1;\n\trevs->min_date = -1;\n\trevs->max_date = -1;\n\trevs->dense = 1;\n\nand then you can just fill in the things you want to directly. Just add \nthe commits you want to populate things with to the \"revs->commits\" list, \nthe paths to \"revs->paths\", set \"revs->limited\" to 1, and then do the \n\"prepare_revision_walk()\" and start walking.\n\nBut hey, the above \"fake the arguments\" thing also works. It makes me \nwince a bit, though.\n\n\t\tLinus\n"}]}