Re: [RFC PATCH] Re: Empty directories...

On Sat, 21 Jul 2007, David Kastrup wrote:

So the basic issue is that not only does git obviously think that only content matters, but it describes it with a single SHA1.

That's not an issue at all for a single file, but if you want to describe *multiple* files with a single SHA1 (which git obviously very much wants to do), the way you generate the SHA1 matters a lot.

In particular, the order.

So git is very very strict about the ordering of tree structures. A tree structure is not just a random list of

	<ASCII mode> + <space> + <filename> + <NUL> + <SHA1>

it's very much an _ordered_ list of those things, because we want the SHA1 of the tree to be well-specified by the contents, and that means that the contents of a tree object has have absolutely _zero_ ambiguity.

This means, for example, that git is very fundamentally case sensitive. There's no sane way *not* to be, because if you're case insensitive in any way at all, you'll end up having two trees that are "the same", but end up having different SHA1's.

It also means that git objects have absolutely zero "localization". There is no locale at all, and there very fundamnetally *must*not* be. Again, for the same reason: if you can describe the same filename with two different encodings, you'd have two different SHA1's for the same content.

So git filenames are very much a "stream of bytes", not anything else. And they need to sort 100% reliably, always the same way, and never with any localized meaning.

And, partly because it seemed most natural, and partly for historical reasons, the way git sorts filenames is by sorting by *pathname*. So if you have three files named

	a.c
	a/c
	abc

then they sort in that exact order, and no other! They sort as a "memcmp" in the full pathname, and that's really nice when you see whole collections of files, and you know the list is globally sorted.

So that "global pathname sorting" has nice properties, and it seems "obvious", but it means that because git actually *encodes* those three files hierarchically as two different trees (because there's a subdirectory there), the tree objects themselves sort a bit oddly. The tree obejcts themselves will look like

 top-level tree:
	100644 a.c -> blob1
	040000 a   -> tree2
	100644 abc -> blob3

 sub-tree:
	100644 c    -> blob2

and notice how the *tree* is not sorted alphabetically at all. It has a subtly different sort, where the entry "a" sorts *after* the entry "a.c", because we know that it's a tree entry, and thus will (in the *global* order) sort as if it had a "/" at the end!

Traditionally, when we have the index, the index sorting has been very simple: you just sort the names as memcmp() would sort them. But note how that changes, if "a" is an empty directory. Now the index needs to sort as

	file a.c
	dir  a
	file abc

because when we create the tree entry, it needs to be sorted the same way all tree entries are always sorted - as if "a" had a slash at the end!

[ Yeah, yeah, we could make a special case and just say "the empty tree 
  sorts differently", but that actually results in huge problems when 
  doing a "diff" between two trees: our diff machinery very much depends 
  on the fact that the index and the trees always sort the same way, and 
  if we sorted the "a" entry (when it is an empty directory) differently 
  from the "a" entry (when it has entries in it), that would just be 
  insane and cause no end of trouble for comparing two trees - one with an 
  empty directory and one with content added to that directory.

  So the sorting is doubly important: it's what makes "one content" always 
  have the same SHA1, but it is also much easier and efficient to compare 
  directories when we know they are sorted the same way. ]

In other words, introducing tree entries in the index ended up also introducing all the issues that we already had with the tree objects since they got split up hierarchically, but that the code didn't use to have to care about.

The easiest way to solve this really does seem to be to add the rule that the index entry for an empty directory has to have the "/" at the end of the name - then the "sort mindlessly by name" will just continue to work.

But that was what I said was broken: my patches I sent out didn't actually do that.

It's *probably* just a few lines of code, and it actually would result in some nice changes ("git ls-files" would show a '/' at the end of an empty directory entry, for example), so this is not a big deal, but it's an example of how subtly different a directory is from a file when it comes to git.

			Linus