Which commit has this blob?

Question

Both of the following scripts take the blob’s SHA1 as the first argument, and after it, optionally, any arguments that git log will understand. E.g. --all to search in all branches instead of just the current one, or -g to search in the reflog, or whatever else you fancy.

Here it is as a shell script – short and sweet, but slow:

#!/bin/sh
obj_name="$1"
shift
git log "$@" --pretty=tformat:'%T %h %s' \
| while read tree commit subject ; do
    if git ls-tree -r $tree | grep -q "$obj_name" ; then
        echo $commit "$subject"
    fi
done

And an optimised version in Perl, still quite short but much faster:

#!/usr/bin/perl
use 5.008;
use strict;
use Memoize;

my $obj_name;

sub check_tree {
    my ( $tree ) = @_;
    my @subtree;

    {
        open my $ls_tree, '-|', git => 'ls-tree' => $tree
            or die "Couldn't open pipe to git-ls-tree: $!\n";

        while ( <$ls_tree> ) {
            /\A[0-7]{6} (\S+) (\S+)/
                or die "unexpected git-ls-tree output";
            return 1 if $2 eq $obj_name;
            push @subtree, $2 if $1 eq 'tree';
        }
    }

    check_tree( $_ ) && return 1 for @subtree;

    return;
}

memoize 'check_tree';

die "usage: git-find-blob <blob> [<git-log arguments ...>]\n"
    if not @ARGV;

my $obj_short = shift @ARGV;
$obj_name = do {
    local $ENV{'OBJ_NAME'} = $obj_short;
     `git rev-parse --verify \$OBJ_NAME`;
} or die "Couldn't parse $obj_short: $!\n";
chomp $obj_name;

open my $log, '-|', git => log => @ARGV, '--pretty=format:%T %h %s'
    or die "Couldn't open pipe to git-log: $!\n";

while ( <$log> ) {
    chomp;
    my ( $tree, $commit, $subject ) = split " ", $_, 3;
    print "$commit $subject\n" if check_tree( $tree );
}

Unfortunately scripts were a bit slow for me, so I had to optimize a bit. Luckily I had not only the hash but also the path of a file.

git log --all --pretty=format:%H -- <path> | xargs -I% sh -c "git ls-tree % -- <path> | grep -q <hash> && echo %"

In addition to git describe, that I mention in my previous answer, git log and git diff now benefits as well from the "--find-object=<object-id>" option to limit the findings to changes that involve the named object.
That is in Git 2.16.x/2.17 (Q1 2018)

See commit 4d8c51a, commit 5e50525, commit 15af58c, commit cf63051, commit c1ddc46, commit 929ed70 (04 Jan 2018) by Stefan Beller (stefanbeller).
^{(Merged by Junio C Hamano -- gitster -- in commit c0d75f0, 23 Jan 2018)}

diffcore: add a pickaxe option to find a specific blob

Sometimes users are given a hash of an object and they want to identify it further (ex.: Use verify-pack to find the largest blobs, but what are these? Or this Stack Overflow question "Which commit has this blob?")

One might be tempted to extend git-describe to also work with blobs, such that git describe <blob-id> gives a description as '<commit-ish>:<path>'.
This was implemented here; as seen by the sheer number of responses (>110), it turns out this is tricky to get right.
The hard part to get right is picking the correct 'commit-ish' as that could be the commit that (re-)introduced the blob or the blob that removed the blob; the blob could exist in different branches.

Junio hinted at a different approach of solving this problem, which this patch implements.
Teach the diff machinery another flag for restricting the information to what is shown.
For example:

$ ./git log --oneline --find-object=v2.0.0:Makefile
  b2feb64 Revert the whole "ask curl-config" topic for now
  47fbfde i18n: only extract comments marked with "TRANSLATORS:"

we observe that the Makefile as shipped with 2.0 was appeared in v1.9.2-471-g47fbfded53 and in v2.0.0-rc1-5-gb2feb6430b.
The reason why these commits both occur prior to v2.0.0 are evil merges that are not found using this new mechanism.

---

As noted in the comments by marcono1234, you can combine that with the git log --all option:

this can be useful when you don't know which branch contains the object.

Given the hash of a blob, is there a way to get a list of commits that have this blob in their tree?

With Git 2.16 (Q1 2018), git describe would be a good solution, since it was taught to dig trees deeper to find a <commit-ish>:<path> that refers to a given blob object.

See commit 644eb60, commit 4dbc59a, commit cdaed0c, commit c87b653, commit ce5b6f9 (16 Nov 2017), and commit 91904f5, commit 2deda00 (02 Nov 2017) by Stefan Beller (stefanbeller).
^{(Merged by Junio C Hamano -- gitster -- in commit 556de1a, 28 Dec 2017)}

builtin/describe.c: describe a blob

Sometimes users are given a hash of an object and they want to identify it further (ex.: Use verify-pack to find the largest blobs, but what are these? or this very SO question "Which commit has this blob?")

When describing commits, we try to anchor them to tags or refs, as these are conceptually on a higher level than the commit. And if there is no ref or tag that matches exactly, we're out of luck.
So we employ a heuristic to make up a name for the commit. These names are ambiguous, there might be different tags or refs to anchor to, and there might be different path in the DAG to travel to arrive at the commit precisely.

When describing a blob, we want to describe the blob from a higher layer as well, which is a tuple of (commit, deep/path) as the tree objects involved are rather uninteresting.
The same blob can be referenced by multiple commits, so how we decide which commit to use?

This patch implements a rather naive approach on this: As there are no back pointers from blobs to commits in which the blob occurs, we'll start walking from any tips available, listing the blobs in-order of the commit and once we found the blob, we'll take the first commit that listed the blob.

For example:

git describe --tags v0.99:Makefile
conversion-901-g7672db20c2:Makefile

tells us the Makefile as it was in v0.99 was introduced in commit 7672db2.

The walking is performed in reverse order to show the introduction of a blob rather than its last occurrence.

That means the git describe man page adds to the purposes of this command:

Instead of simply describing a commit using the most recent tag reachable from it, git describe will actually give an object a human readable name based on an available ref when used as git describe <blob>.

If the given object refers to a blob, it will be described as <commit-ish>:<path>, such that the blob can be found at <path> in the <commit-ish>, which itself describes the first commit in which this blob occurs in a reverse revision walk from HEAD.

But:

BUGS

Tree objects as well as tag objects not pointing at commits, cannot be described.
When describing blobs, the lightweight tags pointing at blobs are ignored, but the blob is still described as <committ-ish>:<path> despite the lightweight tag being favorable.

For humans, the most useful command is probably

git whatchanged --all --find-object=<blob hash>

This shows, across --all branches, any commits that added or removed a file with that hash, along with what the path was.

git$ git whatchanged --all --find-object=b3bb59f06644
commit 8ef93124645f89c45c9ec3edd3b268b38154061a 
⋮
diff: do not show submodule with untracked files as "-dirty"
⋮
:100644 100644 b3bb59f06644 8f6227c993a5 M      submodule.c

commit 7091499bc0a9bccd81a1c864de7b5f87a366480e 
⋮
Revert "submodules: fix of regression on fetching of non-init subsub-repo"
⋮
:100644 100644 eef5204e641e b3bb59f06644 M  submodule.c

Note that git whatchanged already includes the before-and-after blob hashes in its output lines.

I thought this would be a generally useful thing to have, so I wrote up a little perl script to do it:

#!/usr/bin/perl -w

use strict;

my @commits;
my %trees;
my $blob;

sub blob_in_tree {
    my $tree = $_[0];
    if (defined $trees{$tree}) {
        return $trees{$tree};
    }
    my $r = 0;
    open(my $f, "git cat-file -p $tree|") or die $!;
    while (<$f>) {
        if (/^\d+ blob (\w+)/ && $1 eq $blob) {
            $r = 1;
        } elsif (/^\d+ tree (\w+)/) {
            $r = blob_in_tree($1);
        }
        last if $r;
    }
    close($f);
    $trees{$tree} = $r;
    return $r;
}

sub handle_commit {
    my $commit = $_[0];
    open(my $f, "git cat-file commit $commit|") or die $!;
    my $tree = <$f>;
    die unless $tree =~ /^tree (\w+)$/;
    if (blob_in_tree($1)) {
        print "$commit\n";
    }
    while (1) {
        my $parent = <$f>;
        last unless $parent =~ /^parent (\w+)$/;
        push @commits, $1;
    }
    close($f);
}

if (!@ARGV) {
    print STDERR "Usage: git-find-blob blob [head ...]\n";
    exit 1;
}

$blob = $ARGV[0];
if (@ARGV > 1) {
    foreach (@ARGV) {
        handle_commit($_);
    }
} else {
    handle_commit("HEAD");
}
while (@commits) {
    handle_commit(pop @commits);
}

I'll put this up on github when I get home this evening.

Update: It looks like somebody already did this. That one uses the same general idea but the details are different and the implementation is much shorter. I don't know which would be faster but performance is probably not a concern here!

Update 2: For what it's worth, my implementation is orders of magnitude faster, especially for a large repository. That git ls-tree -r really hurts.

Update 3: I should note that my performance comments above apply to the implementation I linked above in the first Update. Aristotle's implementation performs comparably to mine. More details in the comments for those who are curious.