Re: git index: how does it work?

Shaun Cutts [off-list ref] writes:

I am wondering if someone could explain and/or point me to an explanation of how
the git index works.

For instance, suppose I have a tracked file: "foo.c"

1) [I modify "foo.c"]
2) git add foo.c
3) [modify again]
4) git commit -m "blah blah"

Since I don't include the "-a" switch, the version I added on step 2 is
committed. But how does the index keep track of these changes? Does the index
file actually contain the hunks of "foo.c" that have been modified? Or is there
a "temporary" blob created, which the index points to? 

Step 2 hashes foo.c and creates a blob object and registers it to the
index.  Step 4 writes out the index as a tree and makes a commit out of
it.

Running this sequence might be instructive.

	1$ edit foo.c
        2$ git add foo.c
        2a$ git ls-files -s foo.c
	2b$ git diff foo.c
        2c$ git diff --cached foo.c
        3$ edit foo.c
        3a$ git ls-files -s foo.c
	3b$ git diff foo.c
        3c$ git diff --cached foo.c
        4$ git commit -m 'half-edit of foo.c'
        4a$ git ls-files -s foo.c
	4b$ git ls-tree HEAD foo.c
        4c$ git diff foo.c
        4d$ git diff --cached foo.c

 - 2a shows the actual blob object that was created out of foo.c in step 2.

 - 2b shows the difference between that blob (now in the index) and foo.c,
   which should be empty.

 - 2c shows the difference between the HEAD commit and the index, which
   should show your edit in step 1.

 - 3a shows the blob in the index; you haven't added, so it should show
   the same as 2a.

 - 3b shows the difference between the index and foo.c, which should show
   the edit in step 3.

 - 3c shows the difference between the HEAD commit and the index, which
   should show your edit in step 1.

 - 4a shows the blob in the index; you haven't added, so it should show
   the same as 2a.

 - 4b shows the blob in the committed tree and the blob object should be
   identical to 2a.

 - 4c shows the difference between the index and foo.c, which should show
   the edit in step 3.

 - 4d shows the difference between the HEAD commit and the index, which
   should now be empty.

Junio,

Your advice was very helpful.

Digging in, however, I find I still am in the dark on one point: how  
does the index track renamed files, and how to query it for  
information about them?

For instance, if I add a 5th step to the sequence:

5) git mv foo.c bar.c

Then I am told by "git status" that the file is renamed, but I can't  
seem to elict this info using "git ls-files". Under some circumstances  
even "git status" lists a new and deleted file after a rename.

Are renames being tracked by the index, and is there a more basic  
interface than "status" to query about them?

Thanks for any help,

--- Shaun

On Aug 5, 2009, at 8:00 PM, Junio C Hamano wrote:

Shaun Cutts [off-list ref] writes:

quoted

I am wondering if someone could explain and/or point me to an  
explanation of how
the git index works.

For instance, suppose I have a tracked file: "foo.c"

1) [I modify "foo.c"]
2) git add foo.c
3) [modify again]
4) git commit -m "blah blah"

Since I don't include the "-a" switch, the version I added on step  
2 is
committed. But how does the index keep track of these changes? Does  
the index
file actually contain the hunks of "foo.c" that have been modified?  
Or is there
a "temporary" blob created, which the index points to?

Step 2 hashes foo.c and creates a blob object and registers it to the
index.  Step 4 writes out the index as a tree and makes a commit out  
of
it.

Running this sequence might be instructive.

	1$ edit foo.c
       2$ git add foo.c
       2a$ git ls-files -s foo.c
	2b$ git diff foo.c
       2c$ git diff --cached foo.c
       3$ edit foo.c
       3a$ git ls-files -s foo.c
	3b$ git diff foo.c
       3c$ git diff --cached foo.c
       4$ git commit -m 'half-edit of foo.c'
       4a$ git ls-files -s foo.c
	4b$ git ls-tree HEAD foo.c
       4c$ git diff foo.c
       4d$ git diff --cached foo.c

- 2a shows the actual blob object that was created out of foo.c in  
step 2.

- 2b shows the difference between that blob (now in the index) and  
foo.c,
  which should be empty.

- 2c shows the difference between the HEAD commit and the index, which
  should show your edit in step 1.

- 3a shows the blob in the index; you haven't added, so it should show
  the same as 2a.

- 3b shows the difference between the index and foo.c, which should  
show
  the edit in step 3.

- 3c shows the difference between the HEAD commit and the index, which
  should show your edit in step 1.

- 4a shows the blob in the index; you haven't added, so it should show
  the same as 2a.

- 4b shows the blob in the committed tree and the blob object should  
be
  identical to 2a.

- 4c shows the difference between the index and foo.c, which should  
show
  the edit in step 3.

- 4d shows the difference between the HEAD commit and the index, which
  should now be empty.

Heya,

On Wed, Aug 12, 2009 at 04:52, Shaun Cutts[off-list ref] wrote:

Are renames being tracked by the index, and is there a more basic interface
than "status" to query about them?

Nope, git never explicitly tracks renames. Try this:
$ mv foo bar
$ git rm --cached foo
$ git add bar
$ git status

It'll tell you that you renamed foo to bar, even if you never executed 'git mv'.

This is because git does rename _detection_, that is, it'll notice
that you have another file with (almost) the same contents, so it
assumes you did a rename.

-- 
Cheers,

Sverre Rabbelier

Aha ---

that explains it, then.

Is there a lower-level interface to rename detection than via  
"status"? And... um... hmmm.... how does it work? The hash codes don't  
help for "almost" the same. Is there an approximate string matching  
algorithm built in somewhere?

Thanks,

-- Shaun

On Aug 12, 2009, at 7:47 PM, Sverre Rabbelier wrote:

Heya,

On Wed, Aug 12, 2009 at 04:52, Shaun Cutts[off-list ref] wrote:

quoted

Are renames being tracked by the index, and is there a more basic  
interface
than "status" to query about them?

Nope, git never explicitly tracks renames. Try this:
$ mv foo bar
$ git rm --cached foo
$ git add bar
$ git status

It'll tell you that you renamed foo to bar, even if you never  
executed 'git mv'.

This is because git does rename _detection_, that is, it'll notice
that you have another file with (almost) the same contents, so it
assumes you did a rename.

-- 
Cheers,

Sverre Rabbelier

[Please don't top-post, fixed that for you...]

On 2009.08.12 20:45:48 +0200, Shaun Cutts wrote:

On Aug 12, 2009, at 7:47 PM, Sverre Rabbelier wrote:

quoted

Heya,

On Wed, Aug 12, 2009 at 04:52, Shaun Cutts[off-list ref] wrote:

quoted

Are renames being tracked by the index, and is there a more
basic interface
than "status" to query about them?

Nope, git never explicitly tracks renames. Try this:
$ mv foo bar
$ git rm --cached foo
$ git add bar
$ git status

It'll tell you that you renamed foo to bar, even if you never
executed 'git mv'.

This is because git does rename _detection_, that is, it'll notice
that you have another file with (almost) the same contents, so it
assumes you did a rename.

Aha ---

that explains it, then.

Is there a lower-level interface to rename detection than via
"status"? And... um... hmmm.... how does it work? The hash codes
don't help for "almost" the same. Is there an approximate string
matching algorithm built in somewhere?

Roughly, it works like this:
The files are split into small chunks, those are hashed, and if there
are chunks with the same hash in both files, those chunks are treated as
being common to both files. The more the files have in common, the
higher the similarity score. See estimate_similarity() for details.

As the splitting also happens at newlines this has some interesting
effects, for example, you can completely reorder the lines in a file
after renaming it, and git will still detect it as a rename.

Björn

Shaun Cutts [off-list ref] writes:

Are renames being tracked by the index, and is there a more basic
interface than "status" to query about them?

No.  Index, nor git in general, never records renames.  git records
contents, not content changes.  The index records a state, so does the
tree object pointed at by the HEAD commit.

When you ask for "status", git will notice that you have lost a file, and
added a new one, between these two states, by comparing them.  The
contents of these lost files and added files are then compared, and ones
with similar contents are paired up.

That way, you do not have to use "git mv A B" to "rename" A to B.  You can
just as well "mv A B; git rm A; git add B", and get the same outcome,
exactly because git does not record renames.

Instead, we track them by deducing that you renamed from the result.

The tree-vs-index comparison "git status" does to figure all this out is
"git diff-index -M --cached HEAD".

As it should be obvious from the above description,

	git diff-index -M --cached HEAD -- A

is *NOT* the way for you to ask about "possible renames of A".  You need
to run the diff for the whole tree without path limitation so that you can
pair deletions and creations up in order to deduce renames.