{"thread":{"id":"28227","subject":"Looking up objects that point to other objects","startedAt":"2011-08-26T19:01:22Z","lastAt":"2011-08-26T20:10:55Z","messageCount":2,"participants":["Ævar Arnfjörð Bjarmason","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"174339","messageId":"CACBZZX6sydEmuwj_C-KNocjra=6ynud5KFoezPd_Rr3bN4wh2w@mail.gmail.com","threadId":"28227","inReplyTo":null,"subject":"Looking up objects that point to other objects","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-08-26T19:01:22Z","receivedAt":"2011-08-26T19:01:22Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Here's a couple of tasks that require brute-force with the Git object\nformat that I've wanted to do at some point.\n\n * Associate a blob with trees\n\n   Given a blob sha1 find trees that reference it.\n\n * Associate trees with commits / other trees.\n\n   Given a tree find which commit points to that tree, or a parent\n   tree N levels up the stack that a commit points to.\n\nHas anyone written tools to do this? They'd obviously be very CPU and\nI/O intensive, but occasionally I encounter cases where I'd find this\nuseful, e.g. to find what commit contains this huge blob, or what\ntrees / commits are involved with a corrupted object.\n"},{"id":"174343","messageId":"20110826201055.GA9223@sigill.intra.peff.net","threadId":"28227","inReplyTo":"CACBZZX6sydEmuwj_C-KNocjra=6ynud5KFoezPd_Rr3bN4wh2w@mail.gmail.com","subject":"Re: Looking up objects that point to other objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-26T20:10:55Z","receivedAt":"2011-08-26T20:10:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 26, 2011 at 09:01:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> Here's a couple of tasks that require brute-force with the Git object\n> format that I've wanted to do at some point.\n> \n>  * Associate a blob with trees\n> \n>    Given a blob sha1 find trees that reference it.\n> \n>  * Associate trees with commits / other trees.\n> \n>    Given a tree find which commit points to that tree, or a parent\n>    tree N levels up the stack that a commit points to.\n\nI've more frequently wanted to find the entrance and exit points of a\nparticular blob in history, and used something like:\n\n  git log --all --no-abbrev -c --raw --format='commit %H' |\n  perl -le '\n    my @blobs = map { qr/$_/ } @ARGV;\n    while(<STDIN>) {\n      if (/^commit (.*)/) {\n        $commit = $1;\n      }\n      else {\n        foreach my $re (@blobs) {\n          next unless /$re/;\n          print $commit;\n          last;\n        }\n      }\n    }\n  ' $blobs\n\nwhich is fairly efficient. It's brute-force, but at least it all happens\nin O(1) processes. It can find blobs in git.git in about a minute or so\non my machine.\n\nI don't think there's a way to ask for all of the trees in a commit in a\nsingle process. It wouldn't be hard to write in C, of course, but it's\nnot something the current tools support. However, you can use the above\nscript to narrow the range of commits that you know contain a blob, and\nthen individually run ls-tree each one. It's better at least than running\nls-tree on every commit in the repo.\n\nAnything that iterates over commits is going to end up seeing the same\ntrees again and again. I think you could probably do better by thinking\nof it like a directed graph problem. Nodes are sha1s, and edges are any\nreferences of interest:\n\n  1. For a commit, make an edge from the commit to its tree.\n\n  2. For a tree, make an edge from the tree to each of its entries.\n\nAnd then the problem is reduced to \"find all commit nodes that have a\npath to $blob\". Which you can do by breadth-first search from the\ncommits (or backwards from the blob).\n\n-Peff\n"}]}