Skip to contentSkip to conversation

Kernel SCM saga..

DISCUSSION Rajesh Venkatasubramanian 3 participants 4 messages Apr 8, 2005 – Apr 9, 2005

lore
Share & tools
lore
#0 lore raw
Quoted 4 lines · Linus
Quoted 2 lines

It looks like an operation like "show me the history of mm/memory.c" will be pretty expensive using git.

Yes. Per-file history is expensive in git, because if the way it is indexed. Things are indexed by tree and by changeset, and there are no per-file indexes.

Although directory changes are tracked using change-sets, there seems to be no easy way to answer "give me the diff corresponding to the commit (change-set) object <sha1>". That will be really helpful to
review the changes.

Rajesh

#1 lore raw
Quoted 5 lines · Rajesh Venkatasubramanian

Although directory changes are tracked using change-sets, there seems to be no easy way to answer "give me the diff corresponding to the commit (change-set) object <sha1>". That will be really helpful to review the changes.

Actually, it is very easy indeed. Here's what you do:

- look up the commit object ("cat-file commit <sha1>")

This object starts out with "tree <sha1>", followed by a list of parent commit objects: "parent <sha1>"

Remember the tree object (it defines what the tree looks like at the time of the commit). Pick the parent object you want to diff against (normally the first one).

Also, print the checking messages at the end of the commit object.

- look up the parent object ("cat-file commit <parentsha1>")

Here you have the same kind of object, but this time you don't care about going deeper, you just pick up the tree <sha1> that describes the tree at the parent.

- look up the two tree objects. Unlike a commit object, a tree object is a binary data blob, but the format is an _extremely_ simple table of thse guys:

<ascii octal filemode> <space> <pathname> <NUL character> <20-byte sha1>

and the reason it's binary is really that that way "git" doesn't end up having any issues with strange pathnames. If you want to have spaces and newlines in your pathname, go wild.

In particular, the tree object is also _sorted_ by the pathname. This makes things simple, because you now have to sorted trees, and the first thing you do is just walk the two trees in lock-step, which is trivial thanks to the sorted nature of the tree "array".

So now you have three cases:
- you have the same name, and the same sha1

ignore it - the file didn't change, you don't even have to look at the contents (although if the file mode changed you might want to note that)

- you have the same name in parent and child tree lists, but the sha differs. Now you just need to do a "cat-file" on both of the SHA1 values, and do a "diff -u" between them.

- you have the filename in only parent or only child. Do a "create" or "delete" diff with the content of the sha1 file.

See? Very efficient. For any files that didn't change, you didn't have to do anything at all - you didn't even have to look at their data.

Also note that the above algorithm really works for _any_ two commit points (apart for the two first steps, which are obviously all about finding the parent tree when you want to diff against a predecessor).

It doesn't have to be parent and child. Pick any commit you have. And pick them in the other order, and you'll automatically get the reverse diff.

You can even do diffs between unrelated projects this way if you use the shared sha1 directory model, although that obviously doesn't tend to be all that sensible ;)

Linus

#2 lore raw
Quoted 4 lines · Linus Torvalds

Also note that the above algorithm really works for _any_ two commit points (apart for the two first steps, which are obviously all about finding the parent tree when you want to diff against a predecessor).

Btw, if you want to try this, you should get an updated copy. I've pushed a "raw" git archive of both git and sparse (the latter is much more interesting from an archive standpoint, since it actually has 1400 changesets in it) to kernel.org, but I'm not convinced it gets mirrored out. I think the mirror scripts may mirror only things they understand.

I've also added a partial "fsck" for the "git filesystem". It doesn't do the connectivity analysis yet, but that should be pretty straightforward to add - it already parses all the data, it just doesn't save it away (and the connectivity analysis will automatically show how many "root" changesets you have, and what the different HEADs are).

I'll make a tar-file (git-0.03), although at this point I've actually been maintaining it in itself, so to some degree it's almost getting easier if I'd just have a place to rsync it..

Linus

#3 lore raw
In reply to Linus Torvalds
Quoted 2 lines · Linus

If you want to have spaces
and newlines in your pathname, go wild.

So long as there is only one pathname in a record, you don't need nul-terminators to be allow spaces in the name. The rest of the record is well known, so the pathname is just whatever is left after chomping off the rest of the record.

It's only the support for embedded newlines that forces you to use nul-terminators.

Not worth it - in my view. Rather, do just enough hackery that such a pathname doesn't break you, even if it means not giving full service to such names.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.650.933.1373, 1.925.600.0401