{"thread":{"id":"2178","subject":"Teach git-rev-list to follow just a specified set of files","startedAt":"2005-10-21T04:25:09Z","lastAt":"2005-10-21T04:25:09Z","messageCount":1,"participants":["Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"10411","messageId":"Pine.LNX.4.64.0510202105140.10477@g5.osdl.org","threadId":"2178","inReplyTo":null,"subject":"Teach git-rev-list to follow just a specified set of files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-10-21T04:25:09Z","receivedAt":"2005-10-21T04:25:09Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is the first cut at a git-rev-list that knows to ignore commits that \ndon't change a certain file (or set of files).\n\nNOTE! For now it only prunes _merge_ commits, and follows the parent where \nthere are no differences in the set of files specified. In the long run, \nI'd like to make it re-write the straight-line history too, but for now \nthe merge simplification is much more fundamentally important (the \nrewriting of straight-line history is largely a separate simplification \nphase, but the merge simplification needs to happen early if we want to \noptimize away unnecessary commit parsing).\n\nIf all parents of a merge change some of the files, the merge is left as \nis, so the end result is in no way guaranteed to be a linear history, but \nit will often be a lot /more/ linear than the full tree, since it prunes \nout parents that didn't matter for that set of files.\n\nAs an example from the current kernel:\n\n\t[torvalds@g5 linux]$ git-rev-list HEAD | wc -l\n\t9885\n\t[torvalds@g5 linux]$ git-rev-list HEAD -- Makefile | wc -l\n\t4084\n\t[torvalds@g5 linux]$ git-rev-list HEAD -- drivers/usb | wc -l\n\t5206\n\nand you can also use 'gitk' to more visually see the pruning of the \nhistory tree, with something like\n\n\tgitk -- drivers/usb\n\nshowing a simplified history that tries to follow the first parent in a \nmerge that is the parent that fully defines drivers/usb/.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nThis should make it much more efficient to do something like a \ngit-annotate. The merges are the expensive part. Normal straigh-line \ncommits that don't change something is pretty easy.\n\nNOTE! For that \"gitk\" command line to work, you need to have applied both \nof my rev-list.c patches from earlier today..\n\nNOTE 2! At least for now, git-rev-list requires the \"--\" between the revs \nand the filenames. That's actually very inconsistent: all the other git \ntools that take filenames will just assume that something that isn't a rev \nand isn't a flag must be a filename.\n\nI'd actually like to make git-rev-list work that way too (it would make \nthe syntax for gitk etc much more natural), but I chickened out \n(git-rev-list used to error out when it didn't recognize a rev, and this \nugly syntax keeps that as an error case. Whether it's for a good reason or \nnot, I don't know).\n\nNOTE 3! I've tested this, and it all _seems_ to work. But hey, this is \neven more \"core\" than git-diff-tree, so buyer beware!\n\ndiff --git a/rev-list.c b/rev-list.c\nindex 3a32e40..b5dbb9f 100644\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -5,6 +5,7 @@\n #include \"tree.h\"\n #include \"blob.h\"\n #include \"epoch.h\"\n+#include \"diff.h\"\n \n #define SEEN\t\t(1u << 0)\n #define INTERESTING\t(1u << 1)\n@@ -44,6 +45,7 @@ static int show_breaks = 0;\n static int stop_traversal = 0;\n static int topo_order = 0;\n static int no_merges = 0;\n+static const char **paths = NULL;\n \n static void show_commit(struct commit *commit)\n {\n@@ -377,18 +379,129 @@ static void mark_edges_uninteresting(str\n \t}\n }\n \n+static int is_different = 0;\n+\n+static void file_add_remove(struct diff_options *options,\n+\t\t    int addremove, unsigned mode,\n+\t\t    const unsigned char *sha1,\n+\t\t    const char *base, const char *path)\n+{\n+\tis_different = 1;\n+}\n+\n+static void file_change(struct diff_options *options,\n+\t\t unsigned old_mode, unsigned new_mode,\n+\t\t const unsigned char *old_sha1,\n+\t\t const unsigned char *new_sha1,\n+\t\t const char *base, const char *path)\n+{\n+\tis_different = 1;\n+}\n+\n+static struct diff_options diff_opt = {\n+\t.recursive = 1,\n+\t.add_remove = file_add_remove,\n+\t.change = file_change,\n+};\n+\n+static struct commit *try_to_simplify_merge(struct commit *commit, struct commit_list *parent)\n+{\n+\tif (!commit->tree)\n+\t\treturn NULL;\n+\n+\twhile (parent) {\n+\t\tstruct commit *p = parent->item;\n+\t\tparent = parent->next;\n+\t\tparse_commit(p);\n+\t\tif (!p->tree)\n+\t\t\tcontinue;\n+\t\tis_different = 0;\n+\t\tif (diff_tree_sha1(commit->tree->object.sha1,\n+\t\t\t\t   p->tree->object.sha1, \"\", &diff_opt) < 0)\n+\t\t\tcontinue;\n+\t\tif (!is_different)\n+\t\t\treturn p;\n+\t}\n+\treturn NULL;\n+}\n+\n+static void add_parents_to_list(struct commit *commit, struct commit_list **list)\n+{\n+\tstruct commit_list *parent = commit->parents;\n+\n+\t/*\n+\t * If the commit is uninteresting, don't try to\n+\t * prune parents - we want the maximal uninteresting\n+\t * set.\n+\t *\n+\t * Normally we haven't parsed the parent\n+\t * yet, so we won't have a parent of a parent\n+\t * here. However, it may turn out that we've\n+\t * reached this commit some other way (where it\n+\t * wasn't uninteresting), in which case we need\n+\t * to mark its parents recursively too..\n+\t */\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\twhile (parent) {\n+\t\t\tstruct commit *p = parent->item;\n+\t\t\tparent = parent->next;\n+\t\t\tparse_commit(p);\n+\t\t\tp->object.flags |= UNINTERESTING;\n+\t\t\tif (p->parents)\n+\t\t\t\tmark_parents_uninteresting(p);\n+\t\t\tif (p->object.flags & SEEN)\n+\t\t\t\tcontinue;\n+\t\t\tp->object.flags |= SEEN;\n+\t\t\tinsert_by_date(p, list);\n+\t\t}\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * Ok, the commit wasn't uninteresting. If it\n+\t * is a merge, try to find the parent that has\n+\t * no differences in the path set if one exists.\n+\t */\n+\tif (paths && parent && parent->next) {\n+\t\tstruct commit *preferred;\n+\n+\t\tpreferred = try_to_simplify_merge(commit, parent);\n+\t\tif (preferred) {\n+\t\t\tparent->item = preferred;\n+\t\t\tparent->next = NULL;\n+\t\t}\n+\t}\n+\n+\twhile (parent) {\n+\t\tstruct commit *p = parent->item;\n+\n+\t\tparent = parent->next;\n+\n+\t\tparse_commit(p);\n+\t\tif (p->object.flags & SEEN)\n+\t\t\tcontinue;\n+\t\tp->object.flags |= SEEN;\n+\t\tinsert_by_date(p, list);\n+\t}\n+}\n+\n static struct commit_list *limit_list(struct commit_list *list)\n {\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n \twhile (list) {\n-\t\tstruct commit *commit = pop_most_recent_commit(&list, SEEN);\n+\t\tstruct commit_list *entry = list;\n+\t\tstruct commit *commit = list->item;\n \t\tstruct object *obj = &commit->object;\n \n+\t\tlist = list->next;\n+\t\tfree(entry);\n+\n \t\tif (max_age != -1 && (commit->date < max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n \t\tif (unpacked && has_sha1_pack(obj->sha1))\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\tadd_parents_to_list(commit, &list);\n \t\tif (obj->flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(commit);\n \t\t\tif (everybody_uninteresting(list))\n@@ -507,15 +620,15 @@ static void handle_all(struct commit_lis\n \tglobal_lst = NULL;\n }\n \n-int main(int argc, char **argv)\n+int main(int argc, const char **argv)\n {\n+\tconst char *prefix = setup_git_directory();\n \tstruct commit_list *list = NULL;\n \tint i, limited = 0;\n \n-\tsetup_git_directory();\n \tfor (i = 1 ; i < argc; i++) {\n \t\tint flags;\n-\t\tchar *arg = argv[i];\n+\t\tconst char *arg = argv[i];\n \t\tchar *dotdot;\n \t\tstruct commit *commit;\n \n@@ -587,6 +700,14 @@ int main(int argc, char **argv)\n \t\t        limited = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--\")) {\n+\t\t\tpaths = get_pathspec(prefix, argv + i + 1);\n+\t\t\tif (paths) {\n+\t\t\t\tlimited = 1;\n+\t\t\t\tdiff_tree_setup_paths(paths);\n+\t\t\t}\n+\t\t\tbreak;\n+\t\t}\n \n \t\tif (show_breaks && !merge_order)\n \t\t\tusage(rev_list_usage);\n"}]}