{"thread":{"id":"1846","subject":"Unexpected behavior in git-rev-list","startedAt":"2005-09-18T14:49:31Z","lastAt":"2005-09-22T21:26:16Z","messageCount":9,"participants":["Peter Eriksen","Linus Torvalds","Junio C Hamano","Daniel Barkalow"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"8779","messageId":"20050918144931.GA9561@ebar091.ebar.dtu.dk","threadId":"1846","inReplyTo":null,"subject":"Unexpected behavior in git-rev-list","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2005-09-18T14:49:31Z","receivedAt":"2005-09-18T14:49:31Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"Hello people,\n\nThere's something I don't quite understand about git-rev-list.\nAfter adding two files only one shows up with the --objects option.\n\nI'm looking at commit e621a691e9bdbbe263ce34dd20458d9fbbf1a126 at\n\nhttp://www.student.dtu.dk/~s022018/git/gitweb.cgi?p=recipes.git;a=summary\n\nI can find the difference between the latest commit and it's parent:\n\n> git diff HEAD^ HEAD\ndiff --git a/HS-Plugins/20050403/Recipe b/HS-Plugins/20050403/Recipe\nnew file mode 100644\n--- /dev/null\n+++ b/HS-Plugins/20050403/Recipe\n@@ -0,0 +1,16 @@\n [snip]\ndiff --git a/HS-Plugins/20050403/Resources/Dependencies\nb/HS-Plugins/20050403/Resources/Dependencies\nnew file mode 100644\n--- /dev/null\n+++ b/HS-Plugins/20050403/Resources/Dependencies\n@@ -0,0 +1,5 @@\n [snip] \n\nNotice that it creates exactly two files.  Now I expect the folllowing\nobjects:\n\ntree HS-Plugins\ntree 20050403\nblob Recipe\ntree Resources\nblob Dependencies\n\nNow what I understand so far is that we can list all objects reachable\nfrom the HEAD commit but not reachable from its parent commit by: \n\n> git-rev-list --objects ^HEAD^ HEAD\ne621a691e9bdbbe263ce34dd20458d9fbbf1a126\n609c26436053564e8df145b175d75df339b2318b\nfe47bcfb8f47b55e3f6fabd2b2d188030fb57e1f HS-Plugins\n6c8582e49c9f792f4f550fcf510432c84d24d868 20050403\n808a68c33f87693c873f8f9c5f66c050a5ddc81e Recipe\n\nMy question is now: Why doesn't \"git-rev-list --objects ^HEAD^ HEAD\"\nlist the Dependencies blob?  I'm a bit confused.\n\nRegards,\n\nPeter\n"},{"id":"8784","messageId":"Pine.LNX.4.58.0509181013250.26803@g5.osdl.org","threadId":"1846","inReplyTo":"20050918144931.GA9561@ebar091.ebar.dtu.dk","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-18T17:18:10Z","receivedAt":"2005-09-18T17:18:10Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Sep 2005, Peter Eriksen wrote:\n> \n> There's something I don't quite understand about git-rev-list.\n> After adding two files only one shows up with the --objects option.\n>\n> I can find the difference between the latest commit and it's parent:\n> \n> > git diff HEAD^ HEAD\n> diff --git a/HS-Plugins/20050403/Recipe b/HS-Plugins/20050403/Recipe\n> new file mode 100644\n> --- /dev/null\n> +++ b/HS-Plugins/20050403/Recipe\n> @@ -0,0 +1,16 @@\n>  [snip]\n> diff --git a/HS-Plugins/20050403/Resources/Dependencies\n> b/HS-Plugins/20050403/Resources/Dependencies\n> new file mode 100644\n> --- /dev/null\n> +++ b/HS-Plugins/20050403/Resources/Dependencies\n> @@ -0,0 +1,5 @@\n>  [snip] \n> \n> Notice that it creates exactly two files.  Now I expect the folllowing\n> objects:\n> \n> tree HS-Plugins\n> tree 20050403\n> blob Recipe\n> tree Resources\n> blob Dependencies\n\nWell, it looks like some other file has _exactly_ the same contents as the \nnew \"Dependencies\", which means that git notices that the blob isn't \nactually new.\n\nWhich doesn't surprise me at all - you've got a lot of projects there that \nseem to have a Dependencies thing. Why wouldn't some other project have \nthe exact same ones?\n\n\t\tLinus\n"},{"id":"8795","messageId":"20050918175847.GA10427@ebar091.ebar.dtu.dk","threadId":"1846","inReplyTo":"Pine.LNX.4.58.0509181013250.26803@g5.osdl.org","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2005-09-18T17:58:50Z","receivedAt":"2005-09-18T17:58:50Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sun, Sep 18, 2005 at 10:18:10AM -0700, Linus Torvalds wrote:\n> \n> \n> On Sun, 18 Sep 2005, Peter Eriksen wrote:\n> > \n> > There's something I don't quite understand about git-rev-list.\n> > After adding two files only one shows up with the --objects option.\n...\n> Well, it looks like some other file has _exactly_ the same contents as the \n> new \"Dependencies\", which means that git notices that the blob isn't \n> actually new.\n> \n> Which doesn't surprise me at all - you've got a lot of projects there that \n> seem to have a Dependencies thing. Why wouldn't some other project have \n> the exact same ones?\n\nAh!  You are right, there is a Dependencies file in each of the 1000+\ndirectories and they are generated from almost the same setup, so it\nmust be that there is another one like the one, I just commited.  That\nexplains it.  Now I will try to see, if I actually can get the effect I\nexpected somehow. :-) \n\nSo my new challenge to myself: Given two commit objects A and B list all\nthe tree and blob objects which are not in both A and B. \n\nAfter that I think writing a command which does the same as \n'cvs annotate' would be a good exercise.\n\nThanks for the explanation.\n\nRegards,\n\nPeter\n\n\nP.S.\nI'm on the list, so it's not necessary to cc me. \n"},{"id":"9057","messageId":"20050921164948.GB23525@ebar091.ebar.dtu.dk","threadId":"1846","inReplyTo":"20050918175847.GA10427@ebar091.ebar.dtu.dk","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2005-09-21T16:49:48Z","receivedAt":"2005-09-21T16:49:48Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sun, Sep 18, 2005 at 07:58:50PM +0200, Peter Eriksen wrote:\n...\n> So my new challenge to myself: Given two commit objects A and B list all\n> the tree and blob objects which are not in both A and B. \n\n$ git-diff-tree -t A B\n\n> \n> After that I think writing a command which does the same as \n> 'cvs annotate' would be a good exercise.\n\nOk, I have a prototype.  The algorithm has three steps:\n\n1) traverse the commit DAG in breadth first order\n2) for each commit in 1) find the diff against HEAD\n3) for each diff from 2) accumulate the lines and\n   commit ids that latest affected the current HEAD\n4) print the commit ids found in 3), one for each\n   line in HEAD.   \n\nThe command is used like this:\n$ git-annotate-script.sh Documentation/git.txt >blame\n$ cat blame\n51017101c7a308745ba3c04944457f1dc6a55780\n51017101c7a308745ba3c04944457f1dc6a55780\n3db6b224cf36748b969acdd96b9fb2de641cd641\n51017101c7a308745ba3c04944457f1dc6a55780\n51017101c7a308745ba3c04944457f1dc6a55780\n...\n51017101c7a308745ba3c04944457f1dc6a55780\n51017101c7a308745ba3c04944457f1dc6a55780\n51017101c7a308745ba3c04944457f1dc6a55780\n51017101c7a308745ba3c04944457f1dc6a55780\n$ paste -d ' ' blame - <Documentation/git.txt\n\nThe script runs in about 6 seconds on my machine.\n\nAny comments? \n\nRegards,\n\nPeter\n\n\n\ndiff --git a/git-annotate-bfs.pl b/git-annotate-bfs.pl\nnew file mode 100755\n--- /dev/null\n+++ b/git-annotate-bfs.pl\n@@ -0,0 +1,35 @@\n+#!/usr/bin/env perl\n+\n+# 1) Bredde-først-søgning\n+# 2) For hvert commit A i 1) find diff(parent(A), HEAD)\n+# 3) Byg anklage-tabellen og skriv den ud.\n+\n+use strict;\n+use warnings;\n+\n+my $v0 = $ARGV[0];\n+\n+my @Q;     # BFS helper queue of commit ids.\n+my %C;     # BFS helper colours table. C[commit id] = colour.  1=grey,\n2=black.\n+my $v;\n+\n+$C{v0} = 1;\n+push @Q, $v0;\n+while (@Q) {\n+    $v = shift @Q;\n+    #print \"$v\\n\"; ### DEBUG\n+    open(PARENTS, \"git-rev-list --parents --max-count=1 $v |\");\n+    chomp(my $commits = <PARENTS>);\n+    close PARENTS;\n+    my @parents = split(' ', $commits);\n+    shift @parents;\n+    my $v1;\n+    foreach $v1 (@parents) {\n+        #print \".\";  ## DEBUG\n+        if (not defined($C{$v1})) {\n+            $C{$v1} = 1;\n+            push @Q, $v1;\n+        }\n+    }\n+    print \"$commits\\n\"\n+}\ndiff --git a/git-annotate-diff.sh b/git-annotate-diff.sh\nnew file mode 100755\n--- /dev/null\n+++ b/git-annotate-diff.sh\n@@ -0,0 +1,21 @@\n+#!/bin/sh\n+\n+# 1) Bredde-først-søgning\n+# 2) For hvert commit A i 1) find diff(parent(A), HEAD)\n+# 3) Byg anklage-tabellen og skriv den ud.\n+\n+FILEPATH=$1\n+\n+while read COMMITS; do\n+    COMMIT=${COMMITS:0:40}\n+    echo blame $COMMIT\n+    for PARENT in ${COMMITS#* }; do\n+       # Hvis HEAD har ændret sig i forhold til $PARENT,\n+       # skyldes det ikke $PARENT, men et senere commit,\n+       # nemlig ${COMMITS:0:40}\n+       DIFF=`git-diff-tree -r -m $PARENT $COMMIT $FILEPATH`\n+       if [ -n \"$DIFF\" ]; then\n+           git diff $PARENT HEAD $FILEPATH\n+       fi\n+    done\n+done\ndiff --git a/git-annotate-script.sh b/git-annotate-script.sh\nnew file mode 100755\n--- /dev/null\n+++ b/git-annotate-script.sh\n@@ -0,0 +1,11 @@\n+#!/bin/sh\n+\n+FILEPATH=$1\n+\n+BLOB=`git-ls-files --stage | grep $FILEPATH | cut -c8-47`\n+LENGTH=`git-cat-file blob $BLOB | wc -l`\n+\n+git-annotate-bfs.pl HEAD |   \\\n+#cut -c1-40 | git-diff-tree -r -m --stdin rev-list.c | grep \"^[^:]\" \\\n+git-annotate-diff.sh $FILEPATH | \\\n+git-annotate-table.pl $LENGTH\ndiff --git a/git-annotate-table.pl b/git-annotate-table.pl\nnew file mode 100755\n--- /dev/null\n+++ b/git-annotate-table.pl\n@@ -0,0 +1,41 @@\n+#!/usr/bin/env perl\n+\n+use strict;\n+use warnings;\n+\n+\n+# 1) Bredde-først-søgning\n+# 2) For hvert commit A i 1) find diff(parent(A), HEAD)\n+# 3) Byg anklage-tabellen og skriv den ud.\n+\n+my $len = $ARGV[0];\n+\n+my @T;     # Blame table. T[line number] = commit ids\n+my $n = 0;\n+my $blame;\n+my $cln;\n+my $state = \"header\";\n+\n+while (defined (my $line = <STDIN>) and $n < $len) {\n+    if ($line =~ /^blame ([0-9a-fA-F]{40})/) { $blame = $1; $state =\n\"header\"; }\n+    elsif ($line =~ /^diff --git/) { $state = \"header\"; }\n+    elsif ($line =~ /^@@ -\\d+,\\d+ \\+(\\d+),/) { $cln = $1-1; $state =\n\"chunks\"; }\n+    elsif ($state eq \"chunks\") {\n+        if ($line =~ /^\\+/) {\n+            if (not defined $T[$cln]) { $T[$cln] = $blame; $n++; }\n#print \"$cln $blame\\n\"; }\n+            $cln++;\n+       }\n+        elsif ($line =~ /^-/) { }\n+        elsif ($line =~ /^ /) { $cln++; }\n+        else {\n+            print \"line = $line\\n\";\n+            print \"state = $state\\n\";\n+            print \"cln = $cln\\n\";\n+            die \"I'm not supposed to read this line.\";\n+       }\n+    }\n+}\n+\n+foreach (@T) {\n+    print \"$_\\n\";\n+}\n"},{"id":"9059","messageId":"Pine.LNX.4.58.0509211022180.2553@g5.osdl.org","threadId":"1846","inReplyTo":"20050921164948.GB23525@ebar091.ebar.dtu.dk","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-21T17:40:42Z","receivedAt":"2005-09-21T17:40:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 21 Sep 2005, Peter Eriksen wrote:\n> \n> Ok, I have a prototype.  The algorithm has three steps:\n> \n> 1) traverse the commit DAG in breadth first order\n\nThe thing is, this is _expensive_.\n\nIt's very possible to cut down a lot of the costs by having logic to cut \ndown the expense of looking at the whole commit dag.\n\nIn particular, almost all merges will have the same object in _one_ of the\nparents as in the result. And if you just make the rule be that you only \nfollow the first parent that matches the result in the merge, you'll \nalmost always end up with a nice linear thing, with no need to look at \nmultiple parents at all.\n\nOf course, sometimes the merge actually _does_ merge changes from both \n(or more) sides of a commit, and then you need to follow them down and it \ngets nasty and complicated.\n\nAnyway, I've seriously considered adding a mode to \"git-rev-list\" that\nautomatically avoids following the parents that aren't relevant for a\ncertain set of files.\n\nIe if you did\n\n\tgit-rev-list rev1 rev2 ^rev3 ^rev4 .. pathname\n\nit would only show the revisions that actually _change_ the pathname.\n\nIt's not entirely trivial. The biggest bummer is that we'd have to fake\nout the parent info (ie the \"parent\" would have to be the previous entry\nthat changes it, not the real one).\n\nI'm convinced that it's all quite possible, though, by just rewriting the\n\"commit->parents\" list (remove parents that don't change the set of files,\nand in merges where one parent has zero diffs for that set, just select\n_that_ parent, and then continue to prune).\n\nIt might be best not being done by git-rev-list, but by a specialized \nprogram. However, the advantage of doing it in git-rev-list is that then \nthings like \"git log\" and \"gitk\" would automatically take advantage of it, \nie you could say\n\n\tgitk v2.6.12.. drivers/char/\n\nand it would show a \"cut-down\" revision tree that only contained the stuff \nthat changed anything in drivers/char/.\n\nThis would be (a) very useful (b) very powerful and (c) should even be\npretty efficient. Sure, systems that natively do things in a file-specific\nway are still a lot more efficient on a single-file basis, but the git\narchitecture actually lends itself very well to the above kind of \"track a\nwhole subdirectory\" (or \"track two subdirectories and one filename\", or\nanything like that).\n\nAnd a much more efficient \"annotate\" would fall out automatically out of \nit (although I really think that the \"gitk v2.6.12.. drivers/char/\" is \nwhat would be a lot more useful than annotate has ever been).\n\nWe already have this in \"git-whatchanged\", which I personally find very \nvery powerful. But we could do it even better.\n\n\t\tLinus\n"},{"id":"9060","messageId":"7vfyryw9ra.fsf@assigned-by-dhcp.cox.net","threadId":"1846","inReplyTo":"Pine.LNX.4.58.0509211022180.2553@g5.osdl.org","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-21T18:34:01Z","receivedAt":"2005-09-21T18:34:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> It might be best not being done by git-rev-list, but by a specialized \n> program. However, the advantage of doing it in git-rev-list is that then \n> things like \"git log\" and \"gitk\" would automatically take advantage of it, \n> ie you could say\n>\n> \tgitk v2.6.12.. drivers/char/\n>\n> and it would show a \"cut-down\" revision tree that only contained the stuff \n> that changed anything in drivers/char/.\n\nWouldn't gitk get confused by the sparse set of commits your\nrev-list feeds it, when it tries to draw ancestry lines and find\nmany commits missing in between them?\n\nAh, you told him to use 'rev-list --parents' and you can rewrite\nthe list of parents there -- clever.\n"},{"id":"9062","messageId":"Pine.LNX.4.58.0509211144141.2553@g5.osdl.org","threadId":"1846","inReplyTo":"7vfyryw9ra.fsf@assigned-by-dhcp.cox.net","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-21T18:45:39Z","receivedAt":"2005-09-21T18:45:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 21 Sep 2005, Junio C Hamano wrote:\n>\n> Ah, you told him to use 'rev-list --parents' and you can rewrite\n> the list of parents there -- clever.\n\nExactly. \n\nYes, anything that would parse the \"raw\" commit information would be very \nlost indeed, and not able to figure out parenthood from the sparse list. \nBut gitk already uses the \"fakey\" parents.\n\n\t\tLinus\n"},{"id":"9134","messageId":"Pine.LNX.4.63.0509221617300.23242@iabervon.org","threadId":"1846","inReplyTo":"Pine.LNX.4.58.0509211022180.2553@g5.osdl.org","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-22T21:04:11Z","receivedAt":"2005-09-22T21:04:11Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 21 Sep 2005, Linus Torvalds wrote:\n\n> Anyway, I've seriously considered adding a mode to \"git-rev-list\" that\n> automatically avoids following the parents that aren't relevant for a\n> certain set of files.\n> \n> Ie if you did\n> \n> \tgit-rev-list rev1 rev2 ^rev3 ^rev4 .. pathname\n> \n> it would only show the revisions that actually _change_ the pathname.\n>\n> It's not entirely trivial. The biggest bummer is that we'd have to fake\n> out the parent info (ie the \"parent\" would have to be the previous entry\n> that changes it, not the real one).\n\nHow about a program that made the fake thing real? That is, actually wrote \nto the database the entire history with only those paths included, and \nonly commits that change those paths.\n\nThis would be exactly the right thing for the people who want kbuild to be \na separate project from the kernel, because \"the kbuild project\", with \nfull history, could be automatically generated.\n\nFor that matter, Sam could actually use that repository for maintaining \nkbuild, because if mainline merges that instead of merging the present \nkbuild-in-kernel repository, it'll be exactly the same. He could pick up \nstuff from the mainline by subsetting mainline.\n\nIn fact, this operation would allow Junio to push gitk changes upstream, \nas well; \"git subset -w heads/gitk gitk\" would generate the gitk \nrepository, with the addition of any changes to gitk made and committed in \nthe git repository.\n\nI think the only problem with this scheme would be that, if someone does a \ncommit that changes both gitk and something else, the commit message might \nbe a bit confusing in the gitk tree.\n\n(I'm not sure, but this might also generate just the right thing for \ndriver maintainers who want to distribute the latest version of their \ndrivers as an out-of-tree module)\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"9137","messageId":"Pine.LNX.4.58.0509221424390.2553@g5.osdl.org","threadId":"1846","inReplyTo":"Pine.LNX.4.63.0509221617300.23242@iabervon.org","subject":"Re: Unexpected behavior in git-rev-list","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-22T21:26:16Z","receivedAt":"2005-09-22T21:26:16Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 22 Sep 2005, Daniel Barkalow wrote:\n> >\n> > It's not entirely trivial. The biggest bummer is that we'd have to fake\n> > out the parent info (ie the \"parent\" would have to be the previous entry\n> > that changes it, not the real one).\n> \n> How about a program that made the fake thing real? That is, actually wrote \n> to the database the entire history with only those paths included, and \n> only commits that change those paths.\n\nI think it would be a fine thing to do. If/once git-rev-list can do the \n\"limit by filename\" part, generating a new git history that uses that \nshouldn't be that hard.\n\nAnd yes, it would be a way to generate a \"subproject\" automatically.\n\n\t\tLinus\n"}]}