{"thread":{"id":"4153","subject":"[RFC, PATCH] Teach revision.c about renames","startedAt":"2006-05-15T20:37:00Z","lastAt":"2006-05-15T20:37:00Z","messageCount":1,"participants":["Fredrik Kuivinen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"20031","messageId":"20060515203700.GB4497@c165.ib.student.liu.se","threadId":"4153","inReplyTo":null,"subject":"[RFC, PATCH] Teach revision.c about renames","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-05-15T20:37:00Z","receivedAt":"2006-05-15T20:37:00Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nThe attached patch is a work in progress to add support for rename\nfollowing to the revision walking code in revision.c.\n\nWhen the rename following is enabled (with the new '--renames' flag)\nany pathspecs given on the command line are interpreted as\nfilenames. Those filenames are then followed through the commit graph.\n\nFor example, 'git log --renames -- git-fetch.sh' will show us the\nhistory of 'git-fetch.sh' till commit\n215a7ad1ef790467a4cd3f0dcffbd6e5f04c38f7 where it was renamed from\ngit-fetch-script, we then get the history of git-fetch-script instead.\n\nThis works with all commands that use revision.c. So 'gitk --renames\ngit-fetch.sh' and 'git whatchanged --renames git-fetch.sh' also\nwork. Multiple filenames are supposed to work (e.g., 'gitk --renames\n-- git-fetch.sh Documentation/technical/pack-protocol.txt')\n\nThe patch currently have a few issues (that I am aware of):\n\n* A linked list is used to keep track of which filenames that we care\n  about for each commit. A more efficient data structure may be a good\n  idea.\n\n* Memory leaks. In particular the struct path_lists are never freed.\n\n* Pathspecs that aren't filenames cause assertion failures. (for\n  example 'git log --renames -- Documentation/') I don't really know\n  what we should do in this case. Should we interpret 'Documentation/'\n  as if the user supplied us with all the files in the Documentation\n  directory and then track those? Or, should we show commits that\n  change anything under Documentation/ (i.e., the old non-rename\n  following behaviour) and additionally track files that are moved\n  from Documentation/ to some other location. Yet another alternative\n  is to disallow non-filenames. Thoughts?\n\n* Is '--renames' a good name for the flag? I considered\n  '--follow-renames' first, but found it a bit too long.\n\n\nAny comments would be greatly appreciated.\n\n- Fredrik\n\nSigned-off-by: Fredrik Kuivinen <freku045@student.liu.se>\n\n---\n\n log-tree.c |    7 +\n revision.c |  347 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n revision.h |   30 +++++\n 3 files changed, 381 insertions(+), 3 deletions(-)\n\ndiff --git a/log-tree.c b/log-tree.c\nindex b90ba67..8ed500a 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -84,11 +84,12 @@ int log_tree_diff_flush(struct rev_info \n }\n \n static int diff_root_tree(struct rev_info *opt,\n-\t\t\t  const unsigned char *new, const char *base)\n+\t\t\t  struct commit* commit, const char *base)\n {\n \tint retval;\n \tvoid *tree;\n \tstruct tree_desc empty, real;\n+\tconst unsigned char* new = commit->object.sha1;\n \n \ttree = read_object_with_reference(new, tree_type, &real.size, NULL);\n \tif (!tree)\n@@ -97,6 +98,7 @@ static int diff_root_tree(struct rev_inf\n \n \tempty.buf = \"\";\n \tempty.size = 0;\n+\trev_setup_diffopt_paths(opt, commit, NULL);\n \tretval = diff_tree(&empty, &real, base, &opt->diffopt);\n \tfree(tree);\n \tlog_tree_diff_flush(opt);\n@@ -129,7 +131,7 @@ static int log_tree_diff(struct rev_info\n \tparents = commit->parents;\n \tif (!parents) {\n \t\tif (opt->show_root_diff)\n-\t\t\tdiff_root_tree(opt, sha1, \"\");\n+\t\t\tdiff_root_tree(opt, commit, \"\");\n \t\treturn !opt->loginfo;\n \t}\n \n@@ -148,6 +150,7 @@ static int log_tree_diff(struct rev_info\n \tfor (;;) {\n \t\tstruct commit *parent = parents->item;\n \n+\t\trev_setup_diffopt_paths(opt, commit, parent);\n \t\tdiff_tree_sha1(parent->object.sha1, sha1, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \ndiff --git a/revision.c b/revision.c\nindex 2294b16..523ab29 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1,12 +1,17 @@\n+#include <assert.h>\n+\n #include \"cache.h\"\n #include \"tag.h\"\n #include \"blob.h\"\n #include \"tree.h\"\n #include \"commit.h\"\n #include \"diff.h\"\n+#include \"diffcore.h\"\n #include \"refs.h\"\n #include \"revision.h\"\n \n+#define DEBUG 0\n+\n static char *path_name(struct name_path *path, const char *name)\n {\n \tstruct name_path *p;\n@@ -507,6 +512,320 @@ static int add_parents_only(struct rev_i\n \treturn 1;\n }\n \n+/* Rename following code */\n+const struct path_list* path_list_find(const struct path_list* list,\n+\t\t\t\t\t      const char* path)\n+{\n+\tfor(; list; list = list->next) {\n+\t\tif (!strcmp(path, list->item))\n+\t\t\treturn list;\n+\t}\n+\n+\treturn NULL;\n+}\n+\n+struct path_list* path_list_insert(char *item, struct path_list **list_p)\n+{\n+\tstruct path_list *new_list = xmalloc(sizeof(struct path_list));\n+\tnew_list->item = item;\n+\tnew_list->next = *list_p;\n+\t*list_p = new_list;\n+\treturn new_list;\n+}\n+\n+void path_list_print(FILE* file, struct path_list* list)\n+{\n+\tfor(; list; list = list->next)\n+\t\tfprintf(file, \"%s \", list->item);\n+\tfputc('\\n', file);\n+}\n+\n+void free_path_list(struct path_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct path_list *temp = list;\n+\t\tlist = temp->next;\n+\t\tfree(temp);\n+\t}\n+}\n+\n+const char** convert_to_pathspec(struct path_list* l1, struct path_list* l2)\n+{\n+\tstruct path_list* l;\n+\tconst char** ret;\n+\tint i, len = 0;\n+\n+\tfor(l = l1; l; l = l->next, len++)\n+\t\t;\n+\tfor(l = l2; l; l = l->next, len++)\n+\t\t;\n+\n+\tret = xmalloc((len+1)*sizeof(char*));\n+\tfor(i = 0; l1; l1 = l1->next, i++)\n+\t\tret[i] = l1->item;\n+ \tfor(; l2; l2 = l2->next, i++)\n+\t\tret[i] = l2->item;\n+\n+\tret[len] = NULL;\n+\treturn ret;\n+}\n+\n+static struct rev_commit_info* get_util(struct commit *commit)\n+{\n+\tstruct rev_commit_info *util = commit->object.util;\n+\n+\tif (util)\n+\t\treturn util;\n+\n+\tutil = xmalloc(sizeof(struct rev_commit_info));\n+\tutil->paths = NULL;\n+\tutil->topo_data = NULL;\n+\tcommit->object.util = util;\n+\treturn util;\n+}\n+\n+void rev_setup_diffopt_paths(struct rev_info* revs,\n+\t\t\t     struct commit* commit,\n+\t\t\t     struct commit* parent)\n+{\n+\tconst char** pathspec =\n+\t\tconvert_to_pathspec(get_util(commit)->paths,\n+\t\t\t\t    parent ? get_util(parent)->paths : NULL);\n+\n+\t/* FIXME we can't free revs->diffopt.paths here because the\n+\t * initial value of that variable isn't necessarily allocated\n+\t * by malloc.\n+\t *\n+\t * free(revs->diffopt.paths); */\n+\tdiff_tree_release_paths(&revs->diffopt);\n+\tdiff_tree_setup_paths(pathspec, &revs->diffopt);\n+}\n+\n+\n+static void topo_setter(struct commit* c, void* data)\n+{\n+\tstruct rev_commit_info* util = c->object.util;\n+\tutil->topo_data = data;\n+}\n+\n+static void* topo_getter(struct commit* c)\n+{\n+\tstruct rev_commit_info* util = c->object.util;\n+\treturn util->topo_data;\n+}\n+\n+\n+static int same_tree_as_empty_paths(struct rev_info *revs, struct tree* t1,\n+\t\t\t\t    struct path_list* paths)\n+{\n+\tint ret;\n+\n+\tconst char** pathspec = convert_to_pathspec(paths, NULL);\n+\tdiff_tree_setup_paths(pathspec, &revs->pruning);\n+\tret = rev_same_tree_as_empty(revs, t1);\n+\tdiff_tree_release_paths(&revs->pruning);\n+\tfree(pathspec);\n+\treturn ret;\n+}\n+\n+\n+static struct path_list* file_removals;\n+static void file_add_remove_ren(struct diff_options *options,\n+\t\t\t\tint addremove, unsigned mode,\n+\t\t\t\tconst unsigned char *sha1,\n+\t\t\t\tconst char *base, const char *path)\n+{\n+\tif (DEBUG)\n+\t\tprintf(\"%c base: '%s' path: '%s'\\n\", addremove, base, path);\n+\n+\tif (addremove == '-') {\n+\t\tchar* p = xmalloc(strlen(base) + strlen(path) + 1);\n+\t\tstrcpy(p, base);\n+\t\tstrcat(p, path);\n+\t\tpath_list_insert(p, &file_removals);\n+\t\ttree_difference = REV_TREE_NEW;\n+\t} else {\n+\t\tassert(0);\n+\t}\n+}\n+\n+static void file_change_ren(struct diff_options *options,\n+\t\t\t    unsigned old_mode, unsigned new_mode,\n+\t\t\t    const unsigned char *old_sha1,\n+\t\t\t    const unsigned char *new_sha1,\n+\t\t\t    const char *base, const char *path)\n+{\n+\tif (tree_difference == REV_TREE_SAME)\n+\t\ttree_difference = REV_TREE_DIFFERENT;\n+}\n+\n+static int compare_tree_paths(struct rev_info* revs,\n+\t\t\t      struct commit* parent, struct commit* commit,\n+\t\t\t      struct path_list** added)\n+{\n+\tconst char** pathspec;\n+\tstruct diff_options dopts;\n+\n+\tdiff_setup(&dopts);\n+\tdopts.recursive = 1;\n+\tdopts.add_remove = file_add_remove_ren;\n+\tdopts.change = file_change_ren;\n+\tdopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\n+\tpathspec = convert_to_pathspec(get_util(commit)->paths, NULL);\n+\tdiff_tree_setup_paths(pathspec, &dopts);\n+\n+\tif (diff_setup_done(&dopts) < 0)\n+\t\tdie(\"diff_setup_done failed\");\n+\n+\tfile_removals = NULL;\n+\ttree_difference = REV_TREE_SAME;\n+\n+\tdiff_tree_sha1(commit->tree->object.sha1, parent->tree->object.sha1,\n+\t\t       \"\", &dopts);\n+\n+\tdiff_flush(&dopts);\n+\tdiff_tree_release_paths(&dopts);\n+\tfree(pathspec);\n+\n+\t*added = file_removals;\n+\treturn tree_difference;\n+}\n+\n+static struct path_list* find_renames(struct commit* commit,\n+\t\t\t\t      struct commit* parent,\n+\t\t\t\t      struct path_list* paths)\n+{\n+\tint i;\n+\tstruct diff_options dopts;\n+\tstruct path_list* ret = NULL;\n+\n+\tif (DEBUG) {\n+\t\tprintf(\"find_renames commit: %s \",\n+\t\t       sha1_to_hex(commit->object.sha1));\n+\t\tputs(sha1_to_hex(parent->object.sha1));\n+\t\tprintf(\"rename from paths: \");\n+\t\tpath_list_print(stdout, paths);\n+\t}\n+\n+\tdiff_setup(&dopts);\n+\tdopts.recursive = 1;\n+\tdopts.detect_rename = DIFF_DETECT_RENAME;\n+\tdopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\n+\tif (diff_setup_done(&dopts) < 0)\n+\t\tdie(\"diff_setup_done failed\");\n+\n+\tdiff_tree_sha1(commit->tree->object.sha1, parent->tree->object.sha1,\n+\t\t       \"\", &dopts);\n+\tdiffcore_std(&dopts);\n+\n+\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n+\n+\t\tif (0 && p->status == 'R' && DEBUG)\n+\t\t\tprintf(\"rename %s -> %s\\n\", p->one->path, p->two->path);\n+\n+\t\tif (p->status == 'R' && path_list_find(paths, p->one->path)) {\n+\t\t\tif (DEBUG)\n+\t\t\t\tprintf(\"rename %s -> %s\\n\",\n+\t\t\t\t       p->one->path, p->two->path);\n+\t\t\tpath_list_insert(strdup(p->two->path), &ret);\n+\t\t}\n+\t}\n+\tdiff_flush(&dopts);\n+\n+\tif (DEBUG) {\n+\t\tprintf(\"rename result: \");\n+\t\tpath_list_print(stdout, ret);\n+\t}\n+\treturn ret;\n+}\n+\n+static struct path_list* rewrite_paths(struct rev_info *revs,\n+\t\t\t\t       struct commit* commit,\n+\t\t\t\t       struct commit* parent,\n+\t\t\t\t       struct path_list* removed)\n+{\n+\tstruct path_list* new_paths = find_renames(commit, parent, removed);\n+\tstruct path_list* cpaths = get_util(commit)->paths;\n+\tfor(; cpaths; cpaths = cpaths->next) {\n+\t\tif (!path_list_find(removed, cpaths->item))\n+\t\t\tpath_list_insert(cpaths->item, &new_paths);\n+\t}\n+\treturn new_paths;\n+}\n+\n+static void simplify_commit_rename(struct rev_info *revs,\n+\t\t\t\t   struct commit *commit)\n+{\n+\tstruct commit_list **pp, *parent;\n+\n+\tif (!commit->tree)\n+\t\treturn;\n+\n+\t{\n+\t\tstruct rev_commit_info* util = get_util(commit);\n+\t\tif (!util->paths) {\n+\t\t\tutil->paths = revs->initial_paths;\n+\t\t\tif (DEBUG)\n+\t\t\t\tprintf(\"NULL paths\\n\");\n+\t\t}\n+\t}\n+\n+\tif (!commit->parents) {\n+\t\tstruct rev_commit_info* util = commit->object.util;\n+\t\tif (!same_tree_as_empty_paths(revs, commit->tree,\n+\t\t\t\t\t      util->paths))\n+\t\t\tcommit->object.flags |= TREECHANGE;\n+\t\treturn;\n+\t}\n+\n+\tpp = &commit->parents;\n+\twhile ((parent = *pp) != NULL) {\n+\t\tstruct commit *p = parent->item;\n+\t\tstruct path_list* removed;\n+\n+\t\tif (p->object.flags & UNINTERESTING) {\n+\t\t\tpp = &parent->next;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tparse_commit(p);\n+\t\tswitch (compare_tree_paths(revs, p, commit, &removed)) {\n+\t\tcase REV_TREE_SAME:\n+\t\t\tparent->next = NULL;\n+\t\t\tcommit->parents = parent;\n+\t\t\tget_util(p)->paths = get_util(commit)->paths;\n+\t\t\treturn;\n+\n+\t\tcase REV_TREE_NEW:\n+\t\t{\n+\t\t\tstruct path_list* new_paths =\n+\t\t\t\trewrite_paths(revs, commit, p, removed);\n+\t\t\tif (new_paths) {\n+\t\t\t\tstruct rev_commit_info* putil = get_util(p);\n+\t\t\t\tif (!putil->paths)\n+\t\t\t\t\tputil->paths = new_paths;\n+\t\t\t} else {\n+\t\t\t\t*pp = parent->next;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* fallthrough */\n+\t\tcase REV_TREE_DIFFERENT:\n+\t\t\tpp = &parent->next;\n+\t\t\tif (!get_util(p)->paths)\n+\t\t\t\tget_util(p)->paths = get_util(commit)->paths;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tdie(\"bad tree compare for commit %s\",\n+\t\t    sha1_to_hex(commit->object.sha1));\n+\t}\n+\tcommit->object.flags |= TREECHANGE;\n+}\n+\n void init_revisions(struct rev_info *revs)\n {\n \tmemset(revs, 0, sizeof(*revs));\n@@ -742,6 +1061,11 @@ int setup_revisions(int argc, const char\n \t\t\t\trevs->full_diff = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(arg, \"--renames\")) {\n+\t\t\t\trevs->follow_renames = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n \t\t\topts = diff_opt_parse(&revs->diffopt, argv+i, argc-i);\n \t\t\tif (opts > 0) {\n \t\t\t\trevs->diff = 1;\n@@ -841,6 +1165,29 @@ int setup_revisions(int argc, const char\n \t\t    (revs->diffopt.output_format != DIFF_FORMAT_DIFFSTAT))\n \t\t\trevs->diffopt.output_format = DIFF_FORMAT_PATCH;\n \t}\n+\tif (revs->follow_renames && revs->prune_data) {\n+\t\tif (revs->remove_empty_trees)\n+\t\t\tdie(\"--renames and --remove-empty are currently \"\n+\t\t\t    \"mutually exclusive\");\n+\t\trevs->prune_fn = simplify_commit_rename;\n+\t\trevs->topo_setter = topo_setter;\n+\t\trevs->topo_getter = topo_getter;\n+\t\trevs->limited = 1;\n+\n+\t\t{\n+\t\t\tchar** p;\n+\t\t\tfor(p = revs->prune_data; *p; p++) {\n+\t\t\t\tif (DEBUG)\n+\t\t\t\t\tprintf(\"filename: %s\\n\", *p);\n+\t\t\t\tpath_list_insert(strdup(*p),\n+\t\t\t\t\t\t &revs->initial_paths);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (DEBUG)\n+\t\t\tprintf(\"prefix: %s\\n\", revs->prefix);\n+\t}\n+\n \trevs->diffopt.abbrev = revs->abbrev;\n \tdiff_setup_done(&revs->diffopt);\n \ndiff --git a/revision.h b/revision.h\nindex 48d7b4c..e73a327 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -39,7 +39,8 @@ struct rev_info {\n \t\t\tlimited:1,\n \t\t\tunpacked:1,\n \t\t\tboundary:1,\n-\t\t\tparents:1;\n+\t\t\tparents:1,\n+\t\t\tfollow_renames:1;\n \n \t/* Diff flags */\n \tunsigned int\tdiff:1,\n@@ -68,6 +69,9 @@ struct rev_info {\n \tstruct diff_options diffopt;\n \tstruct diff_options pruning;\n \n+\t/* Rename following */\n+\tstruct path_list* initial_paths;\n+\n \ttopo_sort_set_fn_t topo_setter;\n \ttopo_sort_get_fn_t topo_getter;\n };\n@@ -99,4 +103,28 @@ extern struct object_list **add_object(s\n \t\t\t\t       struct name_path *path,\n \t\t\t\t       const char *name);\n \n+\n+\n+struct path_list {\n+\tchar* item;\n+\tstruct path_list *next;\n+};\n+\n+struct rev_commit_info {\n+\tstruct path_list* paths;\n+\tvoid* topo_data;\n+};\n+\n+extern const struct path_list*\n+path_list_find(const struct path_list* list, const char* path);\n+extern struct path_list*\n+path_list_insert(char *item, struct path_list **list_p);\n+extern void path_list_print(FILE*, struct path_list* list);\n+extern void free_path_list(struct path_list *list);\n+extern const char** convert_to_pathspec(struct path_list* l1,\n+\t\t\t\t\tstruct path_list* l2);\n+extern void rev_setup_diffopt_paths(struct rev_info* revs,\n+\t\t\t\t    struct commit* commit,\n+\t\t\t\t    struct commit* parent);\n+\n #endif\n"}]}