{"thread":{"id":"26638","subject":"[RFC] git blame-tree","startedAt":"2011-03-02T16:40:32Z","lastAt":"2011-03-05T05:41:07Z","messageCount":17,"participants":["Jeff King","Piotr Krukowiecki","Junio C Hamano","Jakub Narebski","Will Palmer","Ryan Tomayko"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"162651","messageId":"20110302164031.GA18233@sigill.intra.peff.net","threadId":"26638","inReplyTo":null,"subject":"[RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T16:40:32Z","receivedAt":"2011-03-02T16:40:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[I know, I know, another RFC. I'll get to actually cleaning up and\nsubmitting some of these patches soon.]\n\nIt's sometimes useful to get a list of files in a tree along with the\nlast commit that touched them. This is the default tree view shown on\ngithub.com, but it can also be handy from the command line (there has\nbeen talk lately of having a \"git ls\"), or as plumbing for a local\nfancier tree view. E.g., something like:\n\n     add.c 6e7293e git-add: make -A description clearer vs. -u\n   apply.c fd03881 add description parameter to OPT__VERBOSE\n   blame.c 9ca1169 parse-options: Don't call parse_options_check() so much\n  branch.c 62270f6 branch_merged: fix grammar in warning\n  bundle.c 62b4698 Use angles for placeholders consistently\n\nThe obvious naive way to do this is something like:\n\n  for i in `git ls-tree --name-only HEAD`; do\n    echo \"`git rev-list -1 --no-merges HEAD -- $i` $i\";\n  done\n\nwhich is really slow, because we end up traversing the same commits many\ntimes (plus the startup overhead for each rev-list).  It takes about 35\nseconds to run on git.git.\n\nSo the next obvious thing is to do one traversal, output the changed\nfiles for each commit, and then mark each file as you see it. The perl\nscript below does this (though the careful reader will note it is\nactually buggy with sub-trees; I didn't bother fixing it since it was\njust a stage in the evolution):\n\n-- >8 --\n#!/usr/bin/perl\n\nmy $tree = shift;\nmy @revs = @ARGV;\n\nmy @files = `git ls-tree --name-only $tree`;\nchomp @files;\nmy $num_interesting = @files;\n\nopen(my $fh, '-|', join(' ',\n        \"git rev-list --no-merges\",\n        @revs,\n        \"| git diff-tree --stdin --name-status\")\n) or die \"unable to run rev-list: $!\";\n\nmy %last = map { $_ => undef } @files;\nwhile($num_interesting and $_ = <$fh>) {\n        if (/^[0-9a-f]{40}$/) {\n                $sha1 = $&;\n        }\n        elsif (/^.\\t(.*)/) {\n                next unless exists $last{$1};\n                next if defined $last{$1};\n                $last{$1} = $sha1;\n                $num_interesting--;\n        }\n}\n\nforeach my $file (sort keys(%last)) {\n        print \"$last{$file} $file\\n\";\n}\n-- 8< --\n\nThis runs in about 3 seconds. And besides the above-mentioned bug,\nalso doesn't properly handle things like filenames that need quoting.\n\nSo I wrote it in C, which drops the time down to about 1.5 seconds, and\nof course doesn't have any parsing issues.  The patch is below.\n\nI wasn't sure at first what to call it or what the calling conventions\nshould be. The initial thought was to make it part of \"ls-tree\". But\nthat feels wrong, as ls-tree otherwise never cares about traversal. The\ncombination of traversal and diff made me think of blame, and indeed, I\nthink this is really just about blaming a whole tree at the file-level,\nrather than at the content-level. Thus I called it blame-tree, and I\nused the same calling conventions as blame: \"git blame-tree <path>\n<rev opts>\". See the test script for examples.\n\nI have many thoughts on the patch already, but rather than put them\nhere, I'll include the patch without further ado, and put them inline in\na reply.\n\n---\n .gitignore            |    1 +\n Makefile              |    3 +\n blame-tree.c          |  156 +++++++++++++++++++++++++++++++++++++++++++++++++\n blame-tree.h          |   25 ++++++++\n builtin.h             |    1 +\n builtin/blame-tree.c  |   34 +++++++++++\n git.c                 |    1 +\n t/t8010-blame-tree.sh |   90 ++++++++++++++++++++++++++++\n 8 files changed, 311 insertions(+), 0 deletions(-)\n create mode 100644 blame-tree.c\n create mode 100644 blame-tree.h\n create mode 100644 builtin/blame-tree.c\n create mode 100755 t/t8010-blame-tree.sh\n\ndiff --git a/.gitignore b/.gitignore\nindex c460c66..20c6501 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -14,6 +14,7 @@\n /git-bisect\n /git-bisect--helper\n /git-blame\n+/git-blame-tree\n /git-branch\n /git-bundle\n /git-cat-file\ndiff --git a/Makefile b/Makefile\nindex ade7923..918ce1a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -494,6 +494,7 @@ VCSSVN_LIB=vcs-svn/lib.a\n LIB_H += advice.h\n LIB_H += archive.h\n LIB_H += attr.h\n+LIB_H += blame-tree.h\n LIB_H += blob.h\n LIB_H += builtin.h\n LIB_H += cache.h\n@@ -571,6 +572,7 @@ LIB_OBJS += archive-zip.o\n LIB_OBJS += attr.o\n LIB_OBJS += base85.o\n LIB_OBJS += bisect.o\n+LIB_OBJS += blame-tree.o\n LIB_OBJS += blob.o\n LIB_OBJS += branch.o\n LIB_OBJS += bundle.o\n@@ -683,6 +685,7 @@ BUILTIN_OBJS += builtin/apply.o\n BUILTIN_OBJS += builtin/archive.o\n BUILTIN_OBJS += builtin/bisect--helper.o\n BUILTIN_OBJS += builtin/blame.o\n+BUILTIN_OBJS += builtin/blame-tree.o\n BUILTIN_OBJS += builtin/branch.o\n BUILTIN_OBJS += builtin/bundle.o\n BUILTIN_OBJS += builtin/cat-file.o\ndiff --git a/blame-tree.c b/blame-tree.c\nnew file mode 100644\nindex 0000000..79ceb7e\n--- /dev/null\n+++ b/blame-tree.c\n@@ -0,0 +1,156 @@\n+#include \"cache.h\"\n+#include \"blame-tree.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"diffcore.h\"\n+#include \"revision.h\"\n+\n+void blame_tree_init(struct blame_tree *bt)\n+{\n+\tmemset(bt, 0, sizeof(*bt));\n+\tbt->paths.strdup_strings = 1;\n+\tinit_revisions(&bt->rev, NULL);\n+\tbt->rev.no_merges = 1;\n+\tbt->rev.def = \"HEAD\";\n+}\n+\n+void blame_tree_release(struct blame_tree *bt)\n+{\n+\tstring_list_clear(&bt->paths, 0);\n+\tfree(bt->prefix);\n+}\n+\n+static int add_path(const unsigned char *sha1, const char *base, int baselen,\n+\t\t    const char *name, unsigned mode, int stage, void *data)\n+{\n+\tstruct string_list *paths = data;\n+\tstring_list_append(paths, name);\n+\treturn 0;\n+}\n+\n+static int add_from_revs(struct blame_tree *bt)\n+{\n+\tstruct object_array_entry *obj;\n+\tunsigned char sha1[20];\n+\tunsigned mode;\n+\tstruct tree *tree;\n+\n+\tif (!bt->rev.pending.nr)\n+\t\treturn error(\"no revisions specified\");\n+\n+\tobj = bt->rev.pending.objects;\n+\tif (get_tree_entry(obj->item->sha1, bt->prefix, sha1, &mode) < 0)\n+\t\treturn error(\"no such path: %s:%s\", obj->name, bt->prefix);\n+\n+\ttree = parse_tree_indirect(sha1);\n+\tif (!tree)\n+\t\treturn error(\"not a tree: %s:%s\", obj->name, bt->prefix);\n+\n+\tif (read_tree_recursive(tree, \"\", 0, 0, NULL, add_path, &bt->paths) < 0)\n+\t\treturn error(\"unable to read tree object\");\n+\n+\tsort_string_list(&bt->paths);\n+\treturn 0;\n+}\n+\n+void blame_tree_set_path(struct blame_tree *bt, const char *path,\n+\t\t\t const char *prefix)\n+{\n+\tif (!path) {\n+\t\tbt->prefix = xstrdup(\"\");\n+\t\treturn;\n+\t}\n+\tbt->prefix = prefix_path(prefix, prefix ? strlen(prefix) : 0, path);\n+}\n+\n+void blame_tree_set_revs(struct blame_tree *bt, int argc, const char **argv)\n+{\n+\tsetup_revisions(argc, argv, &bt->rev, NULL);\n+}\n+\n+struct blame_tree_callback_data {\n+\tstruct commit *commit;\n+\tstruct string_list *paths;\n+\tint num_interesting;\n+\n+\tblame_tree_callback callback;\n+\tvoid *callback_data;\n+};\n+\n+static void process_diff(struct diff_queue_struct *q,\n+\t\t\t struct diff_options *opt, void *cbdata)\n+{\n+\tstruct blame_tree_callback_data *data = cbdata;\n+\tint i;\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tconst char *path = p->one->path;\n+\t\tstruct string_list_item *item;\n+\n+\t\titem = string_list_lookup(data->paths, path);\n+\t\t/* Not an interesting path to us */\n+\t\tif (!item)\n+\t\t\tcontinue;\n+\t\t/* We already found its latest commit */\n+\t\tif (item->util)\n+\t\t\tcontinue;\n+\n+\t\titem->util = data->commit;\n+\t\tdata->num_interesting--;\n+\t\tif (data->callback)\n+\t\t\tdata->callback(path, data->commit, data->callback_data);\n+\t}\n+}\n+\n+int blame_tree_run(struct blame_tree *bt, blame_tree_callback cb, void *cbdata)\n+{\n+\tstruct blame_tree_callback_data data;\n+\tstruct commit *commit;\n+\n+\tif (add_from_revs(bt) < 0)\n+\t\treturn -1;\n+\n+\tdata.paths = &bt->paths;\n+\tdata.num_interesting = bt->paths.nr;\n+\tdata.callback = cb;\n+\tdata.callback_data = cbdata;\n+\n+\tbt->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n+\tbt->rev.diffopt.format_callback = process_diff;\n+\tbt->rev.diffopt.format_callback_data = &data;\n+\tdiff_setup_done(&bt->rev.diffopt);\n+\n+\tprepare_revision_walk(&bt->rev);\n+\n+\twhile (data.num_interesting > 0 &&\n+\t       (commit = get_revision(&bt->rev)) != NULL) {\n+\t\tunsigned char to_sha1[20];\n+\t\tunsigned mode;\n+\n+\t\tif (get_tree_entry(commit->object.sha1, bt->prefix,\n+\t\t\t\t   to_sha1, &mode) < 0)\n+\t\t\tcontinue;\n+\n+\t\tdata.commit = commit;\n+\n+\t\tif (commit->parents) {\n+\t\t\tstruct commit_list *p;\n+\t\t\tfor (p = commit->parents; p; p = p->next) {\n+\t\t\t\tunsigned char from_sha1[20];\n+\t\t\t\tif (get_tree_entry(p->item->object.sha1,\n+\t\t\t\t\t\t   bt->prefix,\n+\t\t\t\t\t\t   from_sha1, &mode) < 0)\n+\t\t\t\t\tdiff_root_tree_sha1(to_sha1, \"\",\n+\t\t\t\t\t\t\t    &bt->rev.diffopt);\n+\t\t\t\telse\n+\t\t\t\t\tdiff_tree_sha1(from_sha1, to_sha1,\n+\t\t\t\t\t\t       \"\", &bt->rev.diffopt);\n+\t\t\t}\n+\t\t}\n+\t\telse\n+\t\t\tdiff_root_tree_sha1(to_sha1, \"\", &bt->rev.diffopt);\n+\t\tdiff_flush(&bt->rev.diffopt);\n+\t}\n+\treturn 0;\n+}\ndiff --git a/blame-tree.h b/blame-tree.h\nnew file mode 100644\nindex 0000000..c39f203\n--- /dev/null\n+++ b/blame-tree.h\n@@ -0,0 +1,25 @@\n+#ifndef BLAME_TREE_H\n+#define BLAME_TREE_H\n+\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"string-list.h\"\n+\n+struct blame_tree {\n+\tstruct string_list paths;\n+\tchar *prefix;\n+\tstruct rev_info rev;\n+};\n+\n+void blame_tree_init(struct blame_tree *);\n+void blame_tree_release(struct blame_tree *);\n+\n+void blame_tree_set_path(struct blame_tree *, const char *path,\n+\t\t\t const char *prefix);\n+void blame_tree_set_revs(struct blame_tree *, int argc, const char **argv);\n+\n+typedef void (*blame_tree_callback)(const char *, const struct commit *, void *);\n+int blame_tree_run(struct blame_tree *, blame_tree_callback, void *);\n+\n+#endif /* BLAME_TREE_H */\ndiff --git a/builtin.h b/builtin.h\nindex 0e9da90..01f7842 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -143,5 +143,6 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);\n extern int cmd_show_ref(int argc, const char **argv, const char *prefix);\n extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);\n extern int cmd_replace(int argc, const char **argv, const char *prefix);\n+extern int cmd_blame_tree(int argc, const char **argv, const char *prefix);\n \n #endif\ndiff --git a/builtin/blame-tree.c b/builtin/blame-tree.c\nnew file mode 100644\nindex 0000000..3f580c6\n--- /dev/null\n+++ b/builtin/blame-tree.c\n@@ -0,0 +1,34 @@\n+#include \"cache.h\"\n+#include \"blame-tree.h\"\n+#include \"quote.h\"\n+#include \"parse-options.h\"\n+\n+static void show_entry(const char *path, const struct commit *commit, void *d)\n+{\n+\tprintf(\"%s\\t\", sha1_to_hex(commit->object.sha1));\n+\twrite_name_quoted(path, stdout, '\\n');\n+\tfflush(stdout);\n+}\n+\n+int cmd_blame_tree(int argc, const char **argv, const char *prefix)\n+{\n+\tstruct blame_tree bt;\n+\tconst char *path = NULL;\n+\n+\tgit_config(git_default_config, NULL);\n+\n+\tif (argv[1]) {\n+\t\tpath = argv[1];\n+\t\targc--;\n+\t\targv++;\n+\t}\n+\n+\tblame_tree_init(&bt);\n+\tblame_tree_set_path(&bt, path, prefix);\n+\tblame_tree_set_revs(&bt, argc, argv);\n+\tif (blame_tree_run(&bt, show_entry, NULL) < 0)\n+\t\tdie(\"error running blame-tree traversal\");\n+\tblame_tree_release(&bt);\n+\n+\treturn 0;\n+}\ndiff --git a/git.c b/git.c\nindex ef598c3..54ad91d 100644\n--- a/git.c\n+++ b/git.c\n@@ -318,6 +318,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"archive\", cmd_archive },\n \t\t{ \"bisect--helper\", cmd_bisect__helper, RUN_SETUP | NEED_WORK_TREE },\n \t\t{ \"blame\", cmd_blame, RUN_SETUP },\n+\t\t{ \"blame-tree\", cmd_blame_tree, RUN_SETUP },\n \t\t{ \"branch\", cmd_branch, RUN_SETUP },\n \t\t{ \"bundle\", cmd_bundle, RUN_SETUP_GENTLY },\n \t\t{ \"cat-file\", cmd_cat_file, RUN_SETUP },\ndiff --git a/t/t8010-blame-tree.sh b/t/t8010-blame-tree.sh\nnew file mode 100755\nindex 0000000..21833f3\n--- /dev/null\n+++ b/t/t8010-blame-tree.sh\n@@ -0,0 +1,90 @@\n+#!/bin/sh\n+\n+test_description='basic blame-tree tests'\n+. ./test-lib.sh\n+\n+test_expect_success 'setup' '\n+\ttest_commit 1 file &&\n+\tmkdir sub &&\n+\ttest_commit 2 sub/file &&\n+\tmkdir -p deep/sub/nesting &&\n+\ttest_commit 3 deep/sub/nesting/file\n+'\n+\n+cat >expect.root <<'EOF'\n+1 file\n+2 sub\n+3 deep\n+EOF\n+\n+echo 2 file >expect.sub\n+echo 3 sub >expect.deep\n+echo 3 nesting >expect.deep.sub\n+echo 3 file >expect.deep.sub.nesting\n+\n+check() {\n+\texpect=$1; shift\n+\tgit blame-tree \"$@\" >actual &&\n+\tgit name-rev --stdin --name-only --tags <actual >tmp &&\n+\tmv tmp actual &&\n+\ttr '\\t' ' ' <actual >tmp &&\n+\tmv tmp actual &&\n+\tsort <actual >tmp &&\n+\tmv tmp actual &&\n+\ttest_cmp \"$expect\" actual\n+}\n+\n+test_expect_success 'blame root' '\n+\tcheck expect.root . HEAD\n+'\n+\n+test_expect_success 'blame subdir' '\n+\tcheck expect.sub sub HEAD\n+'\n+\n+test_expect_success 'blame nested subdirs' '\n+\tcheck expect.deep deep HEAD &&\n+\tcheck expect.deep.sub deep/sub HEAD &&\n+\tcheck expect.deep.sub.nesting deep/sub/nesting\n+'\n+\n+test_expect_success 'assume HEAD if no rev opts' '\n+\tcheck expect.root .\n+'\n+\n+test_expect_success 'assume root if no path opt' '\n+\tcheck expect.root\n+'\n+\n+test_expect_success 'blame from older revision' '\n+\techo 1 file >expect &&\n+\tcheck expect . HEAD~2\n+'\n+\n+test_expect_success 'rev limiting works' '\n+\techo 3 deep >expect &&\n+\tcheck expect . -1\n+'\n+\n+test_expect_success 'complaint about a bogus path' '\n+\ttest_must_fail git blame-tree bogus HEAD\n+'\n+\n+test_expect_success 'complain about a non-tree' '\n+\ttest_must_fail git blame-tree file HEAD\n+'\n+\n+test_expect_success 'blame from subdir defaults to root' '\n+\t(cd deep &&\n+\t check ../expect.root\n+\t)\n+'\n+\n+test_expect_success 'blame from subdir uses relative paths' '\n+\t(cd deep &&\n+\t check ../expect.deep . &&\n+\t check ../expect.deep.sub sub\n+\t)\n+'\n+\n+test_done\n-- \n1.7.4.rc1.11.g1c440\n"},{"id":"162653","messageId":"20110302171653.GA18957@sigill.intra.peff.net","threadId":"26638","inReplyTo":"20110302164031.GA18233@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T17:16:54Z","receivedAt":"2011-03-02T17:16:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 11:40:32AM -0500, Jeff King wrote:\n\n>  blame-tree.c          |  156 +++++++++++++++++++++++++++++++++++++++++++++++++\n>  blame-tree.h          |   25 ++++++++\n>  builtin.h             |    1 +\n>  builtin/blame-tree.c  |   34 +++++++++++\n\nI tried to lib-ify the implementation as much as possible. It increases\nthe lines of code, of course, but I figured there was a reasonable\nchance that there might be a user-friendly \"git ls\" command eventually,\nand this would probably make a good \"-v\" option to it.\n\nI considered making it a special mode of \"git blame\" when blame is fed a\ndirectory instead of a file. But the implementations aren't shared at\nall (nor do I think they need to be; blame-tree is _way_ simpler). And I\ndidn't want to steal that concept in case somebody can think of a more\ncontent-level way of blaming a whole tree that makes sense (obviously\njust showing the concatenation of the blames of each file is one way,\nbut I don't know how useful that would be). If we want to go that way,\nwe can always catch the special case in blame and just exec blame-tree.\n\n> +void blame_tree_init(struct blame_tree *bt)\n> +{\n> +\tmemset(bt, 0, sizeof(*bt));\n> +\tbt->paths.strdup_strings = 1;\n> +\tinit_revisions(&bt->rev, NULL);\n> +\tbt->rev.no_merges = 1;\n> +\tbt->rev.def = \"HEAD\";\n> +}\n\nI turn off merges by default, since they are unlikely to be interesting\nmatches (you will see the merge of a side-branch that touched a file\ninstead of the actual commit on the side-branch). You could of course do\n\"git blame-tree . --no-merges\" to get the same effect. I think no-merges\nmakes a saner default, but sadly it doesn't seem like there is a way to\nturn no-merges back off (\"--merges\" means something else, and there is\nno --no-no-merges\").\n\n> +static int add_from_revs(struct blame_tree *bt)\n> +{\n> +\tstruct object_array_entry *obj;\n> +\tunsigned char sha1[20];\n> +\tunsigned mode;\n> +\tstruct tree *tree;\n> +\n> +\tif (!bt->rev.pending.nr)\n> +\t\treturn error(\"no revisions specified\");\n> +\n> +\tobj = bt->rev.pending.objects;\n> +\tif (get_tree_entry(obj->item->sha1, bt->prefix, sha1, &mode) < 0)\n> +\t\treturn error(\"no such path: %s:%s\", obj->name, bt->prefix);\n> +\n> +\ttree = parse_tree_indirect(sha1);\n> +\tif (!tree)\n> +\t\treturn error(\"not a tree: %s:%s\", obj->name, bt->prefix);\n> +\n> +\tif (read_tree_recursive(tree, \"\", 0, 0, NULL, add_path, &bt->paths) < 0)\n> +\t\treturn error(\"unable to read tree object\");\n> +\n> +\tsort_string_list(&bt->paths);\n> +\treturn 0;\n> +}\n\nThe initial set of interesting files we come up with is gotten by\nlooking at the tree of the first pending object after parsing the rev\noptions (defaulting to HEAD). Which sounds a little flaky to me, but\ndoes what you want in practice. I'd be curious if somebody can come up\nwith a counterexample where the ability to manually specify the source\ntree would be more useful.\n\nRight now the code just handles trees. But in the long run, it would\nprobably make sense to get the list of files from the index, and mark\nfiles modified in the working tree or index, too. So something like:\n\n  foo.c  1234abcd this is a commit subject\n  bar.c  modified in working tree\n  baz.c  modified in index\n\nSort of like how gitk shows \"pseudo-commits\" on top of history to\nindicate changes.\n\n> +static void process_diff(struct diff_queue_struct *q,\n> +\t\t\t struct diff_options *opt, void *cbdata)\n> +{\n> +\tstruct blame_tree_callback_data *data = cbdata;\n> +\tint i;\n> +\n> +\tfor (i = 0; i < q->nr; i++) {\n> +\t\tstruct diff_filepair *p = q->queue[i];\n> +\t\tconst char *path = p->one->path;\n> +\t\tstruct string_list_item *item;\n> +\n> +\t\titem = string_list_lookup(data->paths, path);\n> +\t\t/* Not an interesting path to us */\n> +\t\tif (!item)\n> +\t\t\tcontinue;\n> +\t\t/* We already found its latest commit */\n> +\t\tif (item->util)\n> +\t\t\tcontinue;\n> +\n> +\t\titem->util = data->commit;\n> +\t\tdata->num_interesting--;\n> +\t\tif (data->callback)\n> +\t\t\tdata->callback(path, data->commit, data->callback_data);\n> +\t}\n> +}\n\nSo this is the per-commit processing. Basically we just do a diff for\neach commit, and see if each path has been claimed.  Note that it\ndepends on the string-list item->util being initialized to zero. Hence\nmy recent patch to string-list, and this needs to go on top of 62b8102\n(which is in master and maint).\n\nNote that the further back you go in history, the less interesting most\nof the diffs will be, so you waste a lot of time generating boring diffs\nand then looking up those diffs in the string list (which is at least a\nbinary search). I considered an implementation where we literally just\ndo a 3-way merge-traversal of the old tree, the new tree, and the list\nof paths still to be claimed. That would make it O(# of paths) for each\ncommit. But I decided against it because:\n\n  1. It would be a lot more complex, having to hook into unpack_trees\n     instead of the diff machinery.\n\n  2. I'm not sure it would actually be that much faster. If prior\n     measurements are any indication, we are probably spending most of\n     our time unpacking the tree objects.\n\n  3. It closes the door for more advanced diff machinery, like rename\n     detection.\n\n> +\twhile (data.num_interesting > 0 &&\n\nAn optimization; we can quit the traversal as soon as everything is\nclaimed. In practice this helps disappointingly little. Blaming git.git,\nthe last thing that gets claimed is tar.h, which saves only 3838 commits\n(out of ~24500) being traversed. Similarly, COPYING in linux-2.6 is the\nlast, saving only 8378 commits out of ~232000. Still, every little bit\nhelps.\n\n> +\t\tif (commit->parents) {\n> +\t\t\tstruct commit_list *p;\n> +\t\t\tfor (p = commit->parents; p; p = p->next) {\n> +\t\t\t\tunsigned char from_sha1[20];\n> +\t\t\t\tif (get_tree_entry(p->item->object.sha1,\n> +\t\t\t\t\t\t   bt->prefix,\n> +\t\t\t\t\t\t   from_sha1, &mode) < 0)\n> +\t\t\t\t\tdiff_root_tree_sha1(to_sha1, \"\",\n> +\t\t\t\t\t\t\t    &bt->rev.diffopt);\n> +\t\t\t\telse\n> +\t\t\t\t\tdiff_tree_sha1(from_sha1, to_sha1,\n> +\t\t\t\t\t\t       \"\", &bt->rev.diffopt);\n> +\t\t\t}\n> +\t\t}\n\nMy merge handling is just \"which files are different from the parents\".\nWhich is reasonable, but I don't actually exercise it since we use\n--no-merges by default. :)\n\nWe could try to do something clever here about evil merges. If the sha1\nfor a file is different in the merge from both parents, then we know\nthere was at least a conflict. So we could perhaps not blame the merge\nfor non-conflict cases pretty easily, and that would be more useful than\nthe current behavior.  But finding out if a conflicted file was simply\nresolved or if content was introduced is much more expensive.\n\n> +\t\telse\n> +\t\t\tdiff_root_tree_sha1(to_sha1, \"\", &bt->rev.diffopt);\n> +\t\tdiff_flush(&bt->rev.diffopt);\n\nHmm. I mentioned rename detection previously. Probably I should\ndiffcore_std here so that it actually works.\n\n> --- /dev/null\n> +++ b/builtin/blame-tree.c\n> [...]\n> +static void show_entry(const char *path, const struct commit *commit, void *d)\n> +{\n> +\tprintf(\"%s\\t\", sha1_to_hex(commit->object.sha1));\n> +\twrite_name_quoted(path, stdout, '\\n');\n> +\tfflush(stdout);\n> +}\n\nThis callback just shows entries and their commit sha1s as we find them\nduring the traversal.  So the output is not ordered by pathname, but\nrather by traversal order (which is chronological-ish, though you can\nalso use --date-order to get a more certain ordering). It does keep the\noutput streaming, which is nice if you are incrementally filling in a\ndisplay.\n\nProbably for a porcelain command we would want to collect and sort the\nresults by pathname. And show actual commit onelines instead of the\nsha1.\n\n> +int cmd_blame_tree(int argc, const char **argv, const char *prefix)\n> +{\n> +\tstruct blame_tree bt;\n> +\tconst char *path = NULL;\n> +\n> +\tgit_config(git_default_config, NULL);\n> +\n> +\tif (argv[1]) {\n> +\t\tpath = argv[1];\n> +\t\targc--;\n> +\t\targv++;\n> +\t}\n\nObviously no options. Probably there should at least be \"--porcelain\" to\noutput the current form, and the default output should be more\nuser-friendly. And probably \"-z\" to avoid quoting issues.\n\n> --- /dev/null\n> +++ b/t/t8010-blame-tree.sh\n> [...]\n> +test_description='basic blame-tree tests'\n\nThese are extremely basic. If people can think of more interesting\ncorner cases, I'd love to exercise this more. I definitely need to\nconsider merge behavior a bit more and codify it in some tests. Probably\nalso diffcore stuff like renames and copies should be tested.\n\n-Peff\n"},{"id":"162655","messageId":"20110302174056.GB18957@sigill.intra.peff.net","threadId":"26638","inReplyTo":"20110302164031.GA18233@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T17:40:56Z","receivedAt":"2011-03-02T17:40:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 11:40:32AM -0500, Jeff King wrote:\n\n> It's sometimes useful to get a list of files in a tree along with the\n> last commit that touched them. This is the default tree view shown on\n> github.com...\n\nA note on the motivation for this patch.\n\nSome of you may already know this, but I started working full-time for\nGitHub in January, working specifically on git. Most of it is just doing\nthe same general git work I've been doing; obviously GitHub has a vested\ninterest in git being awesome, and this gives me time to make it more\nso.\n\nI'm also working on changes that are going to be useful to large service\nproviders like GitHub more than other people. My plan is to open-source\nthose changes by putting them in a form that's useful to other git users\nand submitting them as patches to the list.  This is the first example,\nbut I have one or two more so far (GitHub actually runs a surprisingly\nstock git).\n\nI wanted to mention it here because:\n\n  1. GitHub is paying money for git development, which I think is cool\n     and they deserve some credit. Having more git time, I'm hoping to\n     tackle some of the long-standing issues that I have queued up\n     (e.g., I'll probably be working on multi-file follow and better\n     support for large binary files in the near future).\n\n  2. I want to be very open about the background behind my patches. I\n     think the list more-or-less operates on a per-patch meritocracy,\n     so in theory the patches should stand on their own or not. But as a\n     long-time contributor, I think it's best to be honest about the\n     fact that my motivations aren't _just_ scratching my own itch\n     anymore.\n\n     I have more or less full autonomy with respect to how I spend my\n     time, so there will still be a lot of itch-scratching. And if\n     something is junk or not useful to non-GitHub users, I won't waste\n     your time with it. So I think in general there won't be any change\n     in the usefulness of my patches. But being open about it lets you\n     choose how many grains of salt to take my patches with. :)\n\n-Peff\n"},{"id":"162656","messageId":"AANLkTim4fKO=Lb0dY0DzRu1QqC8NHPoF8iveYQ2E6OBH@mail.gmail.com","threadId":"26638","inReplyTo":"20110302171653.GA18957@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Piotr Krukowiecki","fromEmail":"piotr.krukowiecki@gmail.com","sentAt":"2011-03-02T17:51:57Z","receivedAt":"2011-03-02T17:51:57Z","isPatch":false,"sender":{"key":"piotr.krukowiecki@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3259959?v=4"},"body":"Hi,\n\nOn Wed, Mar 2, 2011 at 6:16 PM, Jeff King <peff@peff.net> wrote:\n> I considered making it a special mode of \"git blame\" when blame is fed a\n> directory instead of a file. But the implementations aren't shared at\n> all (nor do I think they need to be; blame-tree is _way_ simpler). And I\n\ngit blame dir/file.c\n  \"Show what revision and author last modified each line of a file\"\n\ngit blame dir/\n  \"Show what revision and author last modified each file\"\n\nThis makes sense to me (the user).\nI don't understand the implementation thing. I don't see a difference between\nthose two commands. Even more, if I'm educated  Unix user I might know\ndirectories are also files.\n\n\n> didn't want to steal that concept in case somebody can think of a more\n> content-level way of blaming a whole tree that makes sense (obviously\n> just showing the concatenation of the blames of each file is one way,\n> but I don't know how useful that would be). If we want to go that way,\n> we can always catch the special case in blame and just exec blame-tree.\n\nStill can be in git-blame command, no?\n\n\n> The initial set of interesting files we come up with is gotten by\n> looking at the tree of the first pending object after parsing the rev\n> options (defaulting to HEAD). Which sounds a little flaky to me, but\n> does what you want in practice. I'd be curious if somebody can come up\n> with a counterexample where the ability to manually specify the source\n> tree would be more useful.\n\nSame argument as for normal blame: I want to know who modified files at\nthe state of commit X (if I understand the question correctly).\n\n\n\n\n-- \nPiotrek\n"},{"id":"162658","messageId":"20110302180722.GA20287@sigill.intra.peff.net","threadId":"26638","inReplyTo":"AANLkTim4fKO=Lb0dY0DzRu1QqC8NHPoF8iveYQ2E6OBH@mail.gmail.com","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T18:07:23Z","receivedAt":"2011-03-02T18:07:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 06:51:57PM +0100, Piotr Krukowiecki wrote:\n\n> On Wed, Mar 2, 2011 at 6:16 PM, Jeff King <peff@peff.net> wrote:\n> > I considered making it a special mode of \"git blame\" when blame is fed a\n> > directory instead of a file. But the implementations aren't shared at\n> > all (nor do I think they need to be; blame-tree is _way_ simpler). And I\n> \n> git blame dir/file.c\n>   \"Show what revision and author last modified each line of a file\"\n> \n> git blame dir/\n>   \"Show what revision and author last modified each file\"\n\nRight, I think we are agreeing.\n\n> This makes sense to me (the user).  I don't understand the\n> implementation thing. I don't see a difference between those two\n> commands. Even more, if I'm educated  Unix user I might know\n> directories are also files.\n\nI mean the implementations are very different, so there was not much\npoint in putting the code into builtin/blame.c.\n\n> > didn't want to steal that concept in case somebody can think of a more\n> > content-level way of blaming a whole tree that makes sense (obviously\n> > just showing the concatenation of the blames of each file is one way,\n> > but I don't know how useful that would be). If we want to go that way,\n> > we can always catch the special case in blame and just exec blame-tree.\n> \n> Still can be in git-blame command, no?\n\nRight. What I meant was that we don't have to make the decision now. If\npeople like blame-tree, we can later magically turn:\n\n  git blame dir\n\ninto \"git blame-tree dir\". So I think we are just agreeing.\n\n> > The initial set of interesting files we come up with is gotten by\n> > looking at the tree of the first pending object after parsing the rev\n> > options (defaulting to HEAD). Which sounds a little flaky to me, but\n> > does what you want in practice. I'd be curious if somebody can come up\n> > with a counterexample where the ability to manually specify the source\n> > tree would be more useful.\n> \n> Same argument as for normal blame: I want to know who modified files at\n> the state of commit X (if I understand the question correctly).\n\nYeah, that's what it does now. Specifically I was wondering about more\nelaborate examples, like:\n\n  git blame-tree dir branch1 branch2\n\nIt will traverse using both branch1 and branch2, but get the initial\nlist of files from branch1. I guess we could also union those trees or\nsomething. But I expect most calls to be:\n\n  git blame-tree dir commit\n\nand that's it.\n\n-Peff\n"},{"id":"162661","messageId":"7vbp1tcr25.fsf@alter.siamese.dyndns.org","threadId":"26638","inReplyTo":"20110302171653.GA18957@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-02T18:31:30Z","receivedAt":"2011-03-02T18:31:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I considered making it a special mode of \"git blame\" when blame is fed a\n> directory instead of a file...  ... If we want to go that way,\n> we can always catch the special case in blame and just exec blame-tree.\n\nI agree that rolling it into \"blame\" will be a good way to conclude this\nfeature from the end-user UI point of view, provided if (as you said) this\nproves to be the most reasonable way to give a coarser, file-level blame\nto a history.\n\nIt has been my opinion that the default github view that seems to be\nmodeled after cvsview is the least useful choice of the default in the\nmore modern git era ;-), but I guess people's eyes and brains are trained\nby the old school \"file boundaries matter\" way of thinking.\n\nI am not against catering to them as long as it is done in a modular way\nthat does not negatively affect the other parts of the code, and this\nimplementation certainly is a good one from a cursory reading, except for\ntwo points.\n\nOne is merges, which you punted on with --no-merges ;-).  If I were doing\nthis, I would probably have traversed without --no-merges, and would blame\nall cases that are not TREESAME to the merge (i.e. regardless of the\ncleanness of the content level merge), as this feature is about file level\nblame.  If the child took the whole content as-is from a parent, it is a\nno-event, but if the child has the resulting content that is different\nfrom any of its parents, then that child is responsible for the end-result\ncontent at the file level.\n\nDoing nothing else makes sense.  There is a fundamental expectation for\nfile level history: if you give a commit C as the result for path F,\nsaying C was the one that touched path F the last, you are saying that F\nthat is contained in C is exactly the same as F at the tip of the history\n(i.e. whereever you started digging back from).  If you don't stop at a\nmerge that had content-level merge, you would break that expectation.  You\nwould also rely on the local clock of the merged branches to say which\nbranch made a commit touching the path the last, but it is much minor\nissue compared to the breakage of \"result must match where we say it came\nfrom\" expectation.\n\n> The initial set of interesting files we come up with is gotten by\n> looking at the tree of the first pending object after parsing the rev\n> options (defaulting to HEAD). Which sounds a little flaky to me, but\n> does what you want in practice. I'd be curious if somebody can come up\n> with a counterexample where the ability to manually specify the source\n> tree would be more useful.\n\nI started writing \"In what sense is it flaky?  What corner case do you\nhave in mind?\" in a few lines above and then moved that here ;-).\n\nThe second point is \"why didn't you use pathspec, but chose to take only\none path?\"  It would be useful if you can say\n\n\t$ git blame v2.6.24..v2.6.37 -- net include/net\n\nno?\n\n> So this is the per-commit processing. Basically we just do a diff for\n> each commit, and see if each path has been claimed.  Note that it\n> depends on the string-list item->util being initialized to zero. Hence\n> my recent patch to string-list, and this needs to go on top of 62b8102\n> (which is in master and maint).\n\nOnce you know who the guilty party is, can't you just remove that element\nfrom the list, so that later search from the \"remaining path\" list would\ndecrease in cost as you go deeper?\n\nAlso at some point the set of remaining path would become small and it\nmight make sense to feed that as diff-tree pathspec.  After all, aren't\nyou re-initializing the diff machinery for each commit (which is _not_ a\nbad thing to do--I am just pointing out that there is an opportunity to\nuse narrower pathspecs as you go without any additional cost)?  Note that\nI am not suggesting to update the pathspec used for commit traversal in\nthe middle; that is a lot trickier.\n\n>> +\twhile (data.num_interesting > 0 &&\n>\n> An optimization; we can quit the traversal as soon as everything is\n> claimed. In practice this helps disappointingly little.\n\nThat is somewhat unexpected, but would strongly suggest that the approach\nto use more specific pathspec that cover only the remaining paths would\ngive you faster per-commit diff?\n\n> My merge handling is just \"which files are different from the parents\".\n> Which is reasonable, but I don't actually exercise it since we use\n> --no-merges by default. :)\n\nI think that is a big mistake and I already said it above.\n\n> We could try to do something clever here about evil merges.\n\nAgain, I wouldn't even think about it; this is a \"file boundary matters\"\ntool; you shouldn't care about cleanliness of content-level merges.\n"},{"id":"162662","messageId":"AANLkTi=m_WTohMfJZxTqObRT3rhhtxo=QfnDJCHO=U0K@mail.gmail.com","threadId":"26638","inReplyTo":"20110302180722.GA20287@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Piotr Krukowiecki","fromEmail":"piotr.krukowiecki@gmail.com","sentAt":"2011-03-02T18:39:20Z","receivedAt":"2011-03-02T18:39:20Z","isPatch":false,"sender":{"key":"piotr.krukowiecki@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3259959?v=4"},"body":"On Wed, Mar 2, 2011 at 7:07 PM, Jeff King <peff@peff.net> wrote:\n> On Wed, Mar 02, 2011 at 06:51:57PM +0100, Piotr Krukowiecki wrote:\n>\n>> On Wed, Mar 2, 2011 at 6:16 PM, Jeff King <peff@peff.net> wrote:\n>> > I considered making it a special mode of \"git blame\" when blame is fed a\n>> > directory instead of a file. But the implementations aren't shared at\n>> > all (nor do I think they need to be; blame-tree is _way_ simpler). And I\n>>\n>> git blame dir/file.c\n>>   \"Show what revision and author last modified each line of a file\"\n>>\n>> git blame dir/\n>>   \"Show what revision and author last modified each file\"\n>\n> Right, I think we are agreeing.\n>\n>> This makes sense to me (the user).  I don't understand the\n>> implementation thing. I don't see a difference between those two\n>> commands. Even more, if I'm educated  Unix user I might know\n>> directories are also files.\n>\n> I mean the implementations are very different, so there was not much\n> point in putting the code into builtin/blame.c.\n\nAh, ok.\n\n\n>> > didn't want to steal that concept in case somebody can think of a more\n>> > content-level way of blaming a whole tree that makes sense (obviously\n>> > just showing the concatenation of the blames of each file is one way,\n>> > but I don't know how useful that would be). If we want to go that way,\n>> > we can always catch the special case in blame and just exec blame-tree.\n>>\n>> Still can be in git-blame command, no?\n>\n> Right. What I meant was that we don't have to make the decision now. If\n> people like blame-tree, we can later magically turn:\n>\n>  git blame dir\n>\n> into \"git blame-tree dir\". So I think we are just agreeing.\n\nI hope nobody likes \"blame-dir\" :)\n\n\n>> > The initial set of interesting files we come up with is gotten by\n>> > looking at the tree of the first pending object after parsing the rev\n>> > options (defaulting to HEAD). Which sounds a little flaky to me, but\n>> > does what you want in practice. I'd be curious if somebody can come up\n>> > with a counterexample where the ability to manually specify the source\n>> > tree would be more useful.\n>>\n>> Same argument as for normal blame: I want to know who modified files at\n>> the state of commit X (if I understand the question correctly).\n>\n> Yeah, that's what it does now. Specifically I was wondering about more\n> elaborate examples, like:\n>\n>  git blame-tree dir branch1 branch2\n>\n> It will traverse using both branch1 and branch2, but get the initial\n> list of files from branch1. I guess we could also union those trees or\n> something.\n\nI'd expect this to be something like union. Currently I can only think about\nfollowing case:\n\nSome files were changed in branch1, some in branch2, some in both.\nShow me how the files are changed. For example:\n  file1 changed in branch1 in commit1\n  file2 changed in branch2 in commit2\n  file3 changed in branch1 in commit3 and in branch2 in commit4\n\nIf file was not changed since branch creation then don't show it (optionally).\n\nBut maybe this is more like a diff or log than a blame. Maybe there's already\nsuch mode - I could not find it.\n\n\n$ git init\nInitialized empty Git repository in /tmp/a/.git/\n$ echo a > a\n$ echo b > b\n$ echo c > c\n$ git add .\n$ git commit -a -m new\n[master (root-commit) af5d319] new\n 3 files changed, 3 insertions(+), 0 deletions(-)\n create mode 100644 a\n create mode 100644 b\n create mode 100644 c\n$ git branch branch1\n$ echo trunk1 > a\n$ git commit -a -m trunk1\n[master 2dc7f47] trunk1\n 1 files changed, 1 insertions(+), 1 deletions(-)\n$ echo trunk2 > b\n$ git commit -a -m trunk1\n[master 736fcd2] trunk1\n 1 files changed, 1 insertions(+), 1 deletions(-)\n$ git checkout branch1\nSwitched to branch 'branch1'\n$ echo branch1 > c\n$ git commit -a -m branch1\n[branch1 52e371d] branch1\n 1 files changed, 1 insertions(+), 1 deletions(-)\n$ echo branch2 > b\n$ git commit -a -m branch2\n[branch1 9fed07c] branch2\n 1 files changed, 1 insertions(+), 1 deletions(-)\n$ git diff --stat branch1 master\n a |    2 +-\n b |    2 +-\n c |    2 +-\n 3 files changed, 3 insertions(+), 3 deletions(-)\n\n\nI would like to see output like this:\n a   2dc7f47  (master)\n b   736fcd2  (master)\n b   9fed07c  (branch1)\n c   52e371d  (branch1)\n\n\nNot sure how useful it would be. Just an idea.\n\n\n> But I expect most calls to be:\n>\n>  git blame-tree dir commit\n>\n> and that's it.\n\nMe too.\n\n\n-- \nPiotrek\n"},{"id":"162669","messageId":"20110302210434.GB20400@sigill.intra.peff.net","threadId":"26638","inReplyTo":"7vbp1tcr25.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T21:04:34Z","receivedAt":"2011-03-02T21:04:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 10:31:30AM -0800, Junio C Hamano wrote:\n\n> I agree that rolling it into \"blame\" will be a good way to conclude this\n> feature from the end-user UI point of view, provided if (as you said) this\n> proves to be the most reasonable way to give a coarser, file-level blame\n> to a history.\n\nOK, then I'll proceed with it as a separate command, and we can decide\non rolling it in later.\n\n> One is merges, which you punted on with --no-merges ;-).  If I were doing\n> this, I would probably have traversed without --no-merges, and would blame\n> all cases that are not TREESAME to the merge (i.e. regardless of the\n> cleanness of the content level merge), as this feature is about file level\n> blame.  If the child took the whole content as-is from a parent, it is a\n> no-event, but if the child has the resulting content that is different\n> from any of its parents, then that child is responsible for the end-result\n> content at the file level.\n\nYeah. I made the initial implementation as absolutely simple as\npossible. But after writing my comments, I can't see why I ever thought\nanything but what you propose (and what I mentioned in the reply to\nmyself) would make any sense.\n\nWith sensible semantics, we can turn off --no-merges and still get good\nresults. And anybody who cares for something different can use\n--no-merges themselves. Though I expect the opposite to be the case; I\ncan imagine somebody wanting --first-parent to blame files only to\nmerges.  I'll have to make sure that works properly in my re-roll.\n\n> > The initial set of interesting files we come up with is gotten by\n> > looking at the tree of the first pending object after parsing the rev\n> > options (defaulting to HEAD). Which sounds a little flaky to me, but\n> > does what you want in practice. I'd be curious if somebody can come up\n> > with a counterexample where the ability to manually specify the source\n> > tree would be more useful.\n> \n> I started writing \"In what sense is it flaky?  What corner case do you\n> have in mind?\" in a few lines above and then moved that here ;-).\n\nI was thinking something like:\n\n  git blame-tree dir branch1 branch2\n\nwhere branch2 is actually _ahead_ of branch1. We take the file list from\nbranch1, but may blame commits on branch2. It's probably a little bit of\na crazy thing to ask for, though.\n\n> The second point is \"why didn't you use pathspec, but chose to take only\n> one path?\"  It would be useful if you can say\n> \n> \t$ git blame v2.6.24..v2.6.37 -- net include/net\n> \n> no?\n\nThanks for mentioning; it was one of the things I meant to bring up but\nforgot to. There was one thing that gave me pause[1].  The paths here\nare not about limiting a traversal; they are about limiting the\n_initial_ tree that defines which paths we care about.  So in the\ntraversal above, if 2.6.25 removes net/foo.c, then a regular traversal\nwill think that's interesting and mention it.  But for blame-tree, we\ndon't want that. We want to mention net/foo.c only if it existed at the\nbeginning.\n\nOf course it would be easy enough to parse the revision parameters, then\ncreate our initial path list by combining the initial tree and the\npathspecs. But I wonder if the different semantics implies that we\nshould be using different syntax. I dunno.\n\nThere is also the matter of output. Right now blame-tree takes one path\nparameter, we look it up as a tree, and if it's not a tree we complain.\nThen we output paths that are relative to the inside of that tree. If I\nhave _two_ trees, what should the output be? Should all of the entries\nin \"net\" be prefixed with net/? Should there be a \"--relative\" option?\nWhat should be the default when one pathspec is given. Two pathspecs?\n\n[1] Actually, there was a second thing, but considering it more, I think\nI am just being silly. Pathspecs like that imply to me that we are\ninterested in all paths underneath. But blame-tree (to me, anyway) is\nabout listing the contents of a single tree, and not recursing. But I\nthink I am being silly because we _are_ interested in all things\nunderneath for blame-tree. We just don't necessarily mention the\ndetails. When net/subdir/foo.c changes, we do care, we just say\n\"net/subdir\" changed. So I think it is just a matter of my mental model\nmatching what is happening. And also we could support both modes (blame\na tree without recursion, or blame recursively all files under a tree).\n\n> > So this is the per-commit processing. Basically we just do a diff for\n> > each commit, and see if each path has been claimed.  Note that it\n> > depends on the string-list item->util being initialized to zero. Hence\n> > my recent patch to string-list, and this needs to go on top of 62b8102\n> > (which is in master and maint).\n> \n> Once you know who the guilty party is, can't you just remove that element\n> from the list, so that later search from the \"remaining path\" list would\n> decrease in cost as you go deeper?\n\nYou can, and I considered that, but I don't think it would speed things\nup. The lookup is a binary search, so it's already lg(# of paths), and\nthat number is small (in the hundreds). So there's not much to be saved.\nThe expensive part is actually looking at the tree and doing even the\nraw diff for each commit.\n\nIn an ideal world, trees would be random-access, and for each commit, I\nwould check each unclaimed path to see how it differed in the commit's\ntree versus the parent trees. And then I would do O(# of paths) work for\neach commit, with that # getting smaller each time. But obviously that\nis not the case.\n\n> Also at some point the set of remaining path would become small and it\n> might make sense to feed that as diff-tree pathspec.  After all, aren't\n> you re-initializing the diff machinery for each commit (which is _not_ a\n> bad thing to do--I am just pointing out that there is an opportunity to\n> use narrower pathspecs as you go without any additional cost)?  Note that\n> I am not suggesting to update the pathspec used for commit traversal in\n> the middle; that is a lot trickier.\n\nIs that going to be any cheaper than what I'm doing now? The whole thing\nis a single non-recursive tree diff. So now the diff machinery looks at\neach entry, shows me the differences, and then I look them up pretty\nefficiently against my list.\n\nBy feeding diff the pathspec, it still has to traverse the whole tree\nlooking for interesting entries comparing them against my list, and then\nhand me the reduced list. Its examination of the pathspec is going to be\non par with my list lookup, complexity-wise. I guess there is one small\noptimization it can do: if the trees and pathspec are sorted, as it gets\nto an entry with \"t\" and sees that the last interesting pathspec is \"q\",\nit knows it can stop comparing entries.\n\nI'm not sure if we do that optimization. Even if we do, I'm not sure how\nmuch practical difference it will make. I expect most of the time is\nspent getting the tree out of storage at all, not walking the entries.\nBut I admit I haven't done any timing; that's just based on previous\nexperience.\n\n\nAll that being said, I think I may need to restructure diff calls\nanyway. Right now I find the relevant trees and call diff_tree_sha1. But\nthat doesn't leave any room for rename detection, since the diff\nmachinery never even knows about the other parts of the project ouside\nour subtree, which may be rename sources.  So probably I need to be\nfeeding the whole commit to the diff machinery, getting full pathnames\nin my callback, and then picking out the interesting ones.\n\nAnd then I _will_ need to feed the proper pathspecs to diff. Because it\nwon't be a matter of looking at a few extra entries in a tree we have\nalready pulled from storage. We need to tell diff not to delve into\nthose extra trees at all (unless we need them for rename sources, but we\nshould avoid it for the case that rename detection is not enabled).\n\nI'll have to look into it.\n\n> > An optimization; we can quit the traversal as soon as everything is\n> > claimed. In practice this helps disappointingly little.\n> \n> That is somewhat unexpected, but would strongly suggest that the approach\n> to use more specific pathspec that cover only the remaining paths would\n> give you faster per-commit diff?\n\nI don't think so, for the reasons stated above. But I didn't time.\n\n> > My merge handling is just \"which files are different from the parents\".\n> > Which is reasonable, but I don't actually exercise it since we use\n> > --no-merges by default. :)\n> \n> I think that is a big mistake and I already said it above.\n> \n> > We could try to do something clever here about evil merges.\n> \n> Again, I wouldn't even think about it; this is a \"file boundary matters\"\n> tool; you shouldn't care about cleanliness of content-level merges.\n\nYeah, I am very much in agreement with you on both points now.\n\n-Peff\n"},{"id":"162670","messageId":"20110302211035.GC20400@sigill.intra.peff.net","threadId":"26638","inReplyTo":"AANLkTi=m_WTohMfJZxTqObRT3rhhtxo=QfnDJCHO=U0K@mail.gmail.com","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T21:10:35Z","receivedAt":"2011-03-02T21:10:35Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 07:39:20PM +0100, Piotr Krukowiecki wrote:\n\n> I'd expect this to be something like union. Currently I can only think about\n> following case:\n> \n> Some files were changed in branch1, some in branch2, some in both.\n> Show me how the files are changed. For example:\n>   file1 changed in branch1 in commit1\n>   file2 changed in branch2 in commit2\n>   file3 changed in branch1 in commit3 and in branch2 in commit4\n> \n> If file was not changed since branch creation then don't show it (optionally).\n\nI think we are getting into something different here, because you are\ncaring not just about the commit in some traversal that touched a file,\nbut for each source, which commits got us there and potentially multiple\nsuch commits, one per source for each file.\n\nAnd that's a bit more expensive to compute, and the answers are not\nalways unambiguous. For example, let's say branch1 and branch2 fork from\nsome merge-base M. In the parent of M, file \"foo\" was changed. We\ntraverse from branch1 and branch2, not seeing anything interesting for\n\"foo\". We hit M, and then finally see that its parent touched \"foo\".\n\nWhat do we output? Both branches have equal claim to the commit.\n\nI think you could figure out semantics that make sense if you spent\nenough time on it. But I also think it is making the relatively simple\nproblem of blame-tree a lot more complex.\n\n-Peff\n"},{"id":"162673","messageId":"AANLkTi=hqVcGw16q6uJBO5kPjKtsa=ujtQxg4FRj_+i6@mail.gmail.com","threadId":"26638","inReplyTo":"20110302211035.GC20400@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Piotr Krukowiecki","fromEmail":"piotr.krukowiecki@gmail.com","sentAt":"2011-03-02T21:24:29Z","receivedAt":"2011-03-02T21:24:29Z","isPatch":false,"sender":{"key":"piotr.krukowiecki@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3259959?v=4"},"body":"On Wed, Mar 2, 2011 at 10:10 PM, Jeff King <peff@peff.net> wrote:\n> On Wed, Mar 02, 2011 at 07:39:20PM +0100, Piotr Krukowiecki wrote:\n>\n>> I'd expect this to be something like union. Currently I can only think about\n>> following case:\n>>\n>> Some files were changed in branch1, some in branch2, some in both.\n>> Show me how the files are changed. For example:\n>>   file1 changed in branch1 in commit1\n>>   file2 changed in branch2 in commit2\n>>   file3 changed in branch1 in commit3 and in branch2 in commit4\n>>\n>> If file was not changed since branch creation then don't show it (optionally).\n>\n> I think we are getting into something different here, because you are\n> caring not just about the commit in some traversal that touched a file,\n> but for each source, which commits got us there and potentially multiple\n> such commits, one per source for each file.\n\nYah, it might be something for git-log or git-diff.\n\n\n> And that's a bit more expensive to compute, and the answers are not\n> always unambiguous. For example, let's say branch1 and branch2 fork from\n> some merge-base M. In the parent of M, file \"foo\" was changed. We\n> traverse from branch1 and branch2, not seeing anything interesting for\n> \"foo\". We hit M, and then finally see that its parent touched \"foo\".\n\nSo it's like this?\n\nB1\n|\nM - B2\n|\nP <- changes foo\n\n\n> What do we output? Both branches have equal claim to the commit.\n\nThat's easy. In \"show only differences\" we don't show anything,\nbecause on both branches last-change-commit of \"foo\" is the same.\nIn \"show all\" last-change-commit is P so show it (with message like\n\"changed in common root\" or whatever).\n\n\n> I think you could figure out semantics that make sense if you spent\n> enough time on it. But I also think it is making the relatively simple\n> problem of blame-tree a lot more complex.\n\nI think this is simple, but maybe I don't understand some git\ninternals that make it hard.\n\n\n-- \nPiotrek\n"},{"id":"162679","messageId":"20110302214142.GH20400@sigill.intra.peff.net","threadId":"26638","inReplyTo":"AANLkTi=hqVcGw16q6uJBO5kPjKtsa=ujtQxg4FRj_+i6@mail.gmail.com","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-02T21:41:42Z","receivedAt":"2011-03-02T21:41:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 10:24:29PM +0100, Piotr Krukowiecki wrote:\n\n> So it's like this?\n> \n> B1\n> |\n> M - B2\n> |\n> P <- changes foo\n\nYes.\n\n> > What do we output? Both branches have equal claim to the commit.\n> \n> That's easy. In \"show only differences\" we don't show anything,\n> because on both branches last-change-commit of \"foo\" is the same.\n> In \"show all\" last-change-commit is P so show it (with message like\n> \"changed in common root\" or whatever).\n\nAh, that is totally not the output I would have expected. But now I\nunderstand a little better what you are talking about. In the former\ncase, you are interested in a blame traversal going to the merge-base of\nbranch1 and branch2, and you are interested in the source. So I think\nyou could do it with something like:\n\n  git blame-tree dir --left-right branch1...branch2\n\nthough of course the current output doesn't actually notice things like\nleft-right markings from the revision traversal machinery.\n\nAnd then there is also the question of representing greater than two\nbranches. If \"foo\" blames to a commit that is in branch1 and branch2,\nbut not branch3, what should be output? Presumably you would want it\nenumerated as \"branch1 and branch2 touched it in commit X, branch three\ntouched it in commit Y\". But I'm not sure how well git's revision\nmachinery tracks more than two sources.\n\n> I think this is simple, but maybe I don't understand some git\n> internals that make it hard.\n\nI think it is possible, and probably would build on top of the work I am\ndoing. But I am going to try to get the basics right first, and then we\ncan see about building other stuff on top.\n\n-Peff\n"},{"id":"162689","messageId":"7v39n5az15.fsf@alter.siamese.dyndns.org","threadId":"26638","inReplyTo":"20110302210434.GB20400@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-02T23:22:14Z","receivedAt":"2011-03-02T23:22:14Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> With sensible semantics, we can turn off --no-merges and still get good\n> results. And anybody who cares for something different can use\n> --no-merges themselves. Though I expect the opposite to be the case; I\n> can imagine somebody wanting --first-parent to blame files only to\n> merges.  I'll have to make sure that works properly in my re-roll.\n\nI still do not understand why anybody would even want to say --no-merges.\n\nWhat does this even mean?\n\n\tgit blame --no-merges master..pu -- builtin | builtin/push.c\n\nIt may find ab/i18n or mm/push-default-advice depending on the timestamp,\nby ignoring a content-level merge but is it a useful information?\n\n> I was thinking something like:\n>\n>   git blame-tree dir branch1 branch2\n>\n> where branch2 is actually _ahead_ of branch1. We take the file list from\n> branch1, but may blame commits on branch2. It's probably a little bit of\n> a crazy thing to ask for, though.\n\nTo be compatible with all the git commands, the order of parameters should\nbe revs first and then pathspec, i.e. \"git blame-tree branch1 branch2 dir\".\nBut that is a tangent.\n\nAgain, the same \"what does that mean\" applies.\n\n>> The second point is \"why didn't you use pathspec, but chose to take only\n>> one path?\"  It would be useful if you can say\n>> \n>> \t$ git blame v2.6.24..v2.6.37 -- net include/net\n>> \n>> no?\n>\n> ...  So in the\n> traversal above, if 2.6.25 removes net/foo.c, then a regular traversal\n> will think that's interesting and mention it.  But for blame-tree, we\n> don't want that. We want to mention net/foo.c only if it existed at the\n> beginning.\n\nOf course, if v2.6.37 that is the endpoint of the history (i.e. \"at the\nbeginning\" above) didn't have net/foo.c, then we shouldn't show it.\n\nBut that doesn't change my question.  Why are you taking a single\ndirectory and doing \"ls-tree $endpoint $that_directory\" to populate the\nset of paths to find who touched them last, instead of using the args as\nregular pathspecs and running \"ls-tree $endpoint -- net include/net\" to\npopulate the set?\n\n> Of course it would be easy enough to parse the revision parameters, then\n> create our initial path list by combining the initial tree and the\n> pathspecs....\n\nAs I said already, it does not make any sense to have more than one\nendpoint to begin with when you are asking \"what is the last one that\ntouched things\", and that also applies to the regular blame, which I think\nalready has a logic to make sure you have only one positive commit in the\nstarting rev list.\n\n> ... When net/subdir/foo.c changes, we do care, we just say\n> \"net/subdir\" changed.\n\nI think you would want diff-tree with or without -r then.  I suspect\npeople may want to pass --recursive to this command.\n\n> The expensive part is actually looking at the tree and doing even the\n> raw diff for each commit.\n\n... which may probably be helped by limiting the recursion of that diff\nwith pathspec, but I realize that you are not by default running recursive\ndiff, so...\n\nIt also occurs to me that it may also be a plausible implementation to\nhook this into the usual revision traversal machinery.\n\n> I'm not sure if we do that optimization. Even if we do, I'm not sure how\n> much practical difference it will make. I expect most of the time is\n> spent getting the tree out of storage at all, not walking the entries.\n\nYeah, my \"pathspec\" comment primarily comes from my expectation that this\nwould want to be recursive.  If you are only scanning a single flat tree\nwithout recursing, then there is no need.\n\n> And then I _will_ need to feed the proper pathspecs to diff. Because it\n> won't be a matter of looking at a few extra entries in a tree we have\n> already pulled from storage. We need to tell diff not to delve into\n> those extra trees at all...\n\nYes.\n"},{"id":"162725","messageId":"20110303153647.GE1074@sigill.intra.peff.net","threadId":"26638","inReplyTo":"7v39n5az15.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-03T15:36:48Z","receivedAt":"2011-03-03T15:36:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 02, 2011 at 03:22:14PM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > With sensible semantics, we can turn off --no-merges and still get good\n> > results. And anybody who cares for something different can use\n> > --no-merges themselves. Though I expect the opposite to be the case; I\n> > can imagine somebody wanting --first-parent to blame files only to\n> > merges.  I'll have to make sure that works properly in my re-roll.\n> \n> I still do not understand why anybody would even want to say --no-merges.\n\nOriginally, because my merge semantics were crap. But what I was saying\nhere was \"if, for whatever reason, somebody decided that --no-merges,\nthey can still do it\". So I don't know why. My point was we can safely\ndrop the automatic no-merges as junk.\n\n> > I was thinking something like:\n> >\n> >   git blame-tree dir branch1 branch2\n> >\n> > where branch2 is actually _ahead_ of branch1. We take the file list from\n> > branch1, but may blame commits on branch2. It's probably a little bit of\n> > a crazy thing to ask for, though.\n> \n> To be compatible with all the git commands, the order of parameters should\n> be revs first and then pathspec, i.e. \"git blame-tree branch1 branch2 dir\".\n> But that is a tangent.\n\nYeah, agreed (for some reason when I wrote the original patch, I had the\nbrain-dead idea that I was matching blame. But obviously that is not the\ncase).\n\n> Again, the same \"what does that mean\" applies.\n\nAssuming we switched it, we have:\n\n  git blame-tree branch1 branch2 -- dir\n\nAnd no, I don't know what that means. My question was what should we do\nwith it? I think your answer is \"complain if rev.pending.nr != 1\", and\nthat sounds sensible to me.\n\nOne other possible answer is to take the union of the trees of each\nrevision listed on the command line. Then you could do something like\n\"git blame-tree --all -- path\", and see all files in all trees. But I\ndon't really see how that is a particularly useful output, so I'd just\nas soon disallow it for now.\n\n> But that doesn't change my question.  Why are you taking a single\n> directory and doing \"ls-tree $endpoint $that_directory\" to populate the\n> set of paths to find who touched them last, instead of using the args as\n> regular pathspecs and running \"ls-tree $endpoint -- net include/net\" to\n> populate the set?\n\nBecause my initial attempt was bolted onto ls-tree before I realized\nthat what I really wanted was blame-tree, and this historical crap\nsurvived from an earlier iteration. I think what you are suggesting is\nmuch better.\n\n> As I said already, it does not make any sense to have more than one\n> endpoint to begin with when you are asking \"what is the last one that\n> touched things\", and that also applies to the regular blame, which I think\n> already has a logic to make sure you have only one positive commit in the\n> starting rev list.\n\nYeah, agreed.\n\n> > ... When net/subdir/foo.c changes, we do care, we just say\n> > \"net/subdir\" changed.\n> \n> I think you would want diff-tree with or without -r then.  I suspect\n> people may want to pass --recursive to this command.\n\nYeah, I am coming to that conclusion the more I think about it.\n\n> ... which may probably be helped by limiting the recursion of that diff\n> with pathspec, but I realize that you are not by default running recursive\n> diff, so...\n\nYes, I definitely didn't want recursion. But clearly that is an obvious\noption for people to want, and we should support it. So the code needs\nto be structured to handle both cases.\n\nPartially I was blinded in my initial effort by trying to make it as\nfast and simple as possible for one specific case. But I think we can\nget good performance results using the more traditional traversal and\ndiff machinery, and have a lot more options, too. My rewrite will be\nbased around that.\n\nThanks for the comments.\n\n-Peff\n"},{"id":"162734","messageId":"m3fwr46jp3.fsf@localhost.localdomain","threadId":"26638","inReplyTo":"20110302171653.GA18957@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-03-03T20:20:10Z","receivedAt":"2011-03-03T20:20:10Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Mar 02, 2011 at 11:40:32AM -0500, Jeff King wrote:\n\n> > It's sometimes useful to get a list of files in a tree along with the\n> > last commit that touched them. This is the default tree view shown on\n> > github.com, but it can also be handy from the command line (there has\n> > been talk lately of having a \"git ls\"), or as plumbing for a local\n> > fancier tree view. E.g., something like:\n> > \n> >      add.c 6e7293e git-add: make -A description clearer vs. -u\n> >    apply.c fd03881 add description parameter to OPT__VERBOSE\n> >    blame.c 9ca1169 parse-options: Don't call parse_options_check() so much\n> >   branch.c 62270f6 branch_merged: fix grammar in warning\n> >   bundle.c 62b4698 Use angles for placeholders consistently\n[...] \n\n> >  blame-tree.c          |  156 +++++++++++++++++++++++++++++++++++++++++++++++++\n> >  blame-tree.h          |   25 ++++++++\n> >  builtin.h             |    1 +\n> >  builtin/blame-tree.c  |   34 +++++++++++\n> \n> I tried to lib-ify the implementation as much as possible. It increases\n> the lines of code, of course, but I figured there was a reasonable\n> chance that there might be a user-friendly \"git ls\" command eventually,\n> and this would probably make a good \"-v\" option to it.\n\nI think it _might_ be a good idea to add `--blame' option to\n\"git ls-tree\", as a one of ways of presenting tree-blame output.\nOr perhaps as part of \"git ls\".\n\nIn \"[RFC] Tree blame (git blame <directory>)\"[1] I proposed for\n\n  $ git blame --abbrev v1.6.3.3 -- .\n\nto generate\n\n  100644 blob e57630e ba19a80 Junio C Hamano      Feb 10 17:42   walker.c\n  100644 blob 8a149e1 c13b263 Daniel Barkalow     Apr 26  2008   walker.h\n  100644 blob 7eb3218 fc71db3 Alex Riesen         Apr 29 23:21   wrapper.c\n  100644 blob 4c29255 559e840 Junio C Hamano      Jul 20  2008   write_or_die.c\n  100644 blob 819c797 a437900 Junio C Hamano      Jun 21 02:35   ws.c\n  100644 blob 1b6df45 2af202b Linus Torvalds      Jun 18 10:28   wt-status.c\n  100644 blob 78add09 6c2ce04 Marius Storm-Olsen  Jun  5  2008   wt-status.h\n  100644 blob b9b0db8 eb3a9dd Benjamin Kramer     Mar  7 21:02   xdiff-interface.c\n  100644 blob 7352b9a 86295bb Rene Scharfe        Oct 25  2008   xdiff-interface.h\n  040000 tree ef5d413 5719db9 Charles Bailey      May 25 01:21   xdiff/\n\nor something like that.  Date doesn't have to be in this strange format\nused by 'ls'.  Also instead of name we can use username part of email,\nor just email; OTOH git-blame uses above format for author.\n\nThis could be result of \"git ls-tree --abbrev --blame v1.6.3.3\"...\nand it could be combined with `-l' option of git-ls-tree.\n\n[1]: http://article.gmane.org/gmane.comp.version-control.git/122830\n\n> \n> I considered making it a special mode of \"git blame\" when blame is fed a\n> directory instead of a file. But the implementations aren't shared at\n> all (nor do I think they need to be; blame-tree is _way_ simpler). And I\n> didn't want to steal that concept in case somebody can think of a more\n> content-level way of blaming a whole tree that makes sense (obviously\n> just showing the concatenation of the blames of each file is one way,\n> but I don't know how useful that would be). If we want to go that way,\n> we can always catch the special case in blame and just exec blame-tree.\n\nWell, having \"git blame [<rev>] <directory>\" to output tre-blame\nwould allow to reuse some of already existing options to ordinary\ngit-blame; well those that makes sense, like `-b', `-S <revs-file>',\n`--reverse', perhaps (depending on available output) also `-l', `-t',\n`-s', `--date <format>'.\n\n<rev> is here starting revision or revision range; if it is revision\nrange then negative specifiers function as boundary.\n\nWe could use `-M' to turn on rename detection, and `-C' to turn on\ncopy detection; I think that in tree-blame we need to consider only\n_exact_ renames (pure renames, i.e. the same SHA-1, different name).\n\nAlso for GitHub (and perhaps also in the future for gitweb too) would\nI think use `--porcelain' or even `--incremental' version of tree-blame;\nin [1] I have proposed the following output (following existing \"for\nporcelain\" format):\n\n  $ git blame --porcelain v1.6.3.3 -- .\n\n  86295bb6bac1482d29650d1f77f19d8e7a7cc2fe 7352b9a9c204c2b1d4ca9df5ce040fe22d6f521c\n  author Rene Scharfe\n  author-mail <rene.scharfe@lsrfire.ath.cx>\n  author-time 1224941475\n  author-tz +0200\n  committer Junio C Hamano\n  committer-mail <gitster@pobox.com>\n  committer-time 1224961771\n  committer-tz -0700\n  summary add xdi_diff_hunks() for callers that only need hunk lengths\n  filename xdiff-interface.h\n  100644 blob 7352b9a9c204c2b1d4ca9df5ce040fe22d6f521c    xdiff-interface.h\n  5719db91ce5915ee07c50f1afdc94fe34e91529f ef5d413237b3a390007fba56671b00d7c371ae1e\n  author Charles Bailey\n  author-mail <charles@hashpling.org>\n  author-time 1243210874\n  author-tz +0100\n  committer Junio C Hamano\n  committer-mail <gitster@pobox.com>\n  committer-time 1243234594\n  committer-tz -0700\n  summary add xdi_diff_hunks() for callers that only need hunk lengths\n  filename xdiff\n  040000 tree ef5d413237b3a390007fba56671b00d7c371ae1e    xdiff\n\n> > +void blame_tree_init(struct blame_tree *bt)\n> > +{\n> > +\tmemset(bt, 0, sizeof(*bt));\n> > +\tbt->paths.strdup_strings = 1;\n> > +\tinit_revisions(&bt->rev, NULL);\n> > +\tbt->rev.no_merges = 1;\n> > +\tbt->rev.def = \"HEAD\";\n> > +}\n> \n> I turn off merges by default, since they are unlikely to be interesting\n> matches (you will see the merge of a side-branch that touched a file\n> instead of the actual commit on the side-branch). You could of course do\n> \"git blame-tree . --no-merges\" to get the same effect. I think no-merges\n> makes a saner default, but sadly it doesn't seem like there is a way to\n> turn no-merges back off (\"--merges\" means something else, and there is\n> no --no-no-merges\").\n\nIMHO merges are interecting; moreover if I remember correctly my proof\nof concept of tree-blame which I tried to implement in Perl using\nGit.pm (git cat-file --batch + git diff-tree --stdin), I have problems\nwith merges in tree-blame of subdirectory (\"--relative\" option doesn't\nwork as I thought it did).\n \n> Right now the code just handles trees. But in the long run, it would\n> probably make sense to get the list of files from the index, and mark\n> files modified in the working tree or index, too. So something like:\n> \n>   foo.c  1234abcd this is a commit subject\n>   bar.c  modified in working tree\n>   baz.c  modified in index\n> \n> Sort of like how gitk shows \"pseudo-commits\" on top of history to\n> indicate changes.\n\nOr how \"git blame\" handles \"--contents <file>\" option... though what\nyou mentioned is more than that.\n\n[...] \n> > +int cmd_blame_tree(int argc, const char **argv, const char *prefix)\n> > +{\n> > +\tstruct blame_tree bt;\n> > +\tconst char *path = NULL;\n> > +\n> > +\tgit_config(git_default_config, NULL);\n> > +\n> > +\tif (argv[1]) {\n> > +\t\tpath = argv[1];\n> > +\t\targc--;\n> > +\t\targv++;\n> > +\t}\n> \n> Obviously no options. Probably there should at least be \"--porcelain\" to\n> output the current form, and the default output should be more\n> user-friendly. And probably \"-z\" to avoid quoting issues.\n\nThank you for working on this.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"162767","messageId":"1299249614.2133.19.camel@wpalmer.simply-domain","threadId":"26638","inReplyTo":"20110302164031.GA18233@sigill.intra.peff.net","subject":"Re: [RFC] git blame-tree","fromName":"Will Palmer","fromEmail":"wmpalmer@gmail.com","sentAt":"2011-03-04T14:40:14Z","receivedAt":"2011-03-04T14:40:14Z","isPatch":false,"sender":{"key":"wmpalmer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/357044?v=4"},"body":"On Wed, 2011-03-02 at 11:40 -0500, Jeff King wrote:\n> [I know, I know, another RFC. I'll get to actually cleaning up and\n> submitting some of these patches soon.]\n> \n> It's sometimes useful to get a list of files in a tree along with the\n> last commit that touched them. This is the default tree view shown on\n> github.com, but it can also be handy from the command line (there has\n> been talk lately of having a \"git ls\"), or as plumbing for a local\n> fancier tree view. E.g., something like:\n> \n>      add.c 6e7293e git-add: make -A description clearer vs. -u\n>    apply.c fd03881 add description parameter to OPT__VERBOSE\n>    blame.c 9ca1169 parse-options: Don't call parse_options_check() so much\n>   branch.c 62270f6 branch_merged: fix grammar in warning\n>   bundle.c 62b4698 Use angles for placeholders consistently\n> \n> The obvious naive way to do this is something like:\n> \n>   for i in `git ls-tree --name-only HEAD`; do\n>     echo \"`git rev-list -1 --no-merges HEAD -- $i` $i\";\n>   done\n> \n> which is really slow, because we end up traversing the same commits many\n> times (plus the startup overhead for each rev-list).  It takes about 35\n> seconds to run on git.git.\n> \n> So the next obvious thing is to do one traversal, output the changed\n> files for each commit, and then mark each file as you see it. The perl\n> script below does this (though the careful reader will note it is\n> actually buggy with sub-trees; I didn't bother fixing it since it was\n> just a stage in the evolution):\n> \n[code snipped]\n> \n> This runs in about 3 seconds. And besides the above-mentioned bug,\n> also doesn't properly handle things like filenames that need quoting.\n> \n> So I wrote it in C, which drops the time down to about 1.5 seconds, and\n> of course doesn't have any parsing issues.  The patch is below.\n> \n> I wasn't sure at first what to call it or what the calling conventions\n> should be. The initial thought was to make it part of \"ls-tree\". But\n> that feels wrong, as ls-tree otherwise never cares about traversal. The\n> combination of traversal and diff made me think of blame, and indeed, I\n> think this is really just about blaming a whole tree at the file-level,\n> rather than at the content-level. Thus I called it blame-tree, and I\n> used the same calling conventions as blame: \"git blame-tree <path>\n> <rev opts>\". See the test script for examples.\n> \n> I have many thoughts on the patch already, but rather than put them\n> here, I'll include the patch without further ado, and put them inline in\n> a reply.\n> \n[patch snipped]\n\nCoincidentally, I'm doing a similar thing in a shell script at the\nmoment. Unfortunately, no tree-object is involved: I'm instead using the\noutput from \"git diff\" on two different branches to generate a list of\nfiles I care about. How hard would it be to accept a nul-delimited list\nof filenames via stdin, rather than from a tree? If I'm reading this\nright, it looks like a pretty trivial change. (I couldn't get the\nexisting patch to apply, myself.. I assume I'm just doing something\nwrong as I don't need to use \"git am\" very often.)\n"},{"id":"162768","messageId":"20110304145340.GA8345@sigill.intra.peff.net","threadId":"26638","inReplyTo":"1299249614.2133.19.camel@wpalmer.simply-domain","subject":"Re: [RFC] git blame-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-04T14:53:40Z","receivedAt":"2011-03-04T14:53:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 04, 2011 at 02:40:14PM +0000, Will Palmer wrote:\n\n> Coincidentally, I'm doing a similar thing in a shell script at the\n> moment. Unfortunately, no tree-object is involved: I'm instead using the\n> output from \"git diff\" on two different branches to generate a list of\n> files I care about. How hard would it be to accept a nul-delimited list\n> of filenames via stdin, rather than from a tree? If I'm reading this\n> right, it looks like a pretty trivial change.\n\nMy planned rewrite will take arbitrary pathspecs, so you can ask for a\nsubset of the project files, not just a specific tree, on the\ncommand-line.  Which may be enough for your purposes (coupled with\nxargs). But it would also be easy enough to take rev options on stdin\nfor very large cases that would exceed the usual command-line limits.\n\n> (I couldn't get the existing patch to apply, myself.. I assume I'm\n> just doing something wrong as I don't need to use \"git am\" very\n> often.)\n\nIt's also possible I screwed something up in posting it. If you describe\nthe problem, I might be able to help.\n\n-Peff\n"},{"id":"162807","messageId":"AANLkTinGkDga_X1gJnK_HDSNRD_F1XKWjBQm2LUxkyiM@mail.gmail.com","threadId":"26638","inReplyTo":"7vbp1tcr25.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] git blame-tree","fromName":"Ryan Tomayko","fromEmail":"ryan@github.com","sentAt":"2011-03-05T05:41:07Z","receivedAt":"2011-03-05T05:41:07Z","isPatch":false,"sender":{"key":"ryan@github.com","avatar":null},"body":"On Wed, Mar 2, 2011 at 10:31 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> It has been my opinion that the default github view that seems to be\n> modeled after cvsview is the least useful choice of the default in the\n> more modern git era ;-), but I guess people's eyes and brains are trained\n> by the old school \"file boundaries matter\" way of thinking.\n\nJunio, would you mind elaborating a bit here? I read this as \"the\nfile tree is less interesting than the commit history\", or maybe\nsome other view? I'm curious what would be your preference for\ndefault view.\n\nRyan\n"}]}