From: David Kastrup <hidden> Date: 2016-06-15 22:43:22
Linus Torvalds [off-list ref] writes:
On Wed, 18 Jul 2007, Matthieu Moy wrote:
quoted
If you checkout a branch, create an empty directory in this branch
(probably a placeholder, either for future versionned files, or for
generated files), you cannot tell git "this empty directory is in this
branch, but not in other ones" without adding a file in it.
Right. Which is the suggested setup: add an empty ".gitignore" file
to the directory, and you're done.
That implies that every directory in a versioned tree will exclusively
be created under manual and conscious control. Not by running some
installer or script, unpacking some archive and so on. But if every
content on a disk was created and put there under manual control of
the disk owner, we could still get along with floppy disks quite fine.
In practice, much more content gets sent around and juggled than what
is under immediate supervision of the user.
This is getting silly: you don't need to pull out rabbits out of your
head. You said that you are not inclined to do any work in that area
since it does not touch _your_ use cases (well, at least not to a
degree that you consider worth bothering about) but that is no reason
to get into ridiculous arguments about other usage. No code will come
of that.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
You said that you are not inclined to do any work in that area
since it does not touch _your_ use cases (well, at least not to a
degree that you consider worth bothering about) but that is no reason
to get into ridiculous arguments about other usage.
How hard is it for you to admit that I also said "please send in a patch".
I don't need it. You do. You do the work. I'm just explaining why the work
hasn't been done.
Linus
Gaah.
I'm a damn softie (and soft in the head too, for writing the code).
Ok, here's a trivial patch to start the ball rolling. I'm really not
interested in taking this patch any further personally, but I'm hoping
that maybe it can make somebody else who is actually _interested_ in
trackign empty directories (hint hint) decide that it's a good enough
start that they can fill in the details.
This really updates three different areas, which are nicely separated into
three different files, so while it's one single patch, you can actually
follow along the changes by just looking at the differences in each file,
which directly translate to separate conceptual changes:
- builtin-update-index.c
This simply contains the changes to update the index file. As usual,
there are multiple different cases, and they boil down to:
(a) No index entry existed at all previously. If so, a directory
will first go through the "index_path()" logic, which tries to
create a GITLINK entry for it, if the subdirectory is a git
directory. However, the new thing is that if that fails, it
will instead just create a fake empty tree entry for it, and
set the index mode to S_IFDIR.
(b) It was a gitlink entry before. It stays as a gitlink entry,
even if it cannot be indexed, and a file/symlink entry in
the working tree is a conflict error.
(c) It was a empty directory entry before. A directory stays as an
empty directory entry, and a file/symlink entry in the working
tree is a conflict error.
Somebody should check that we properly delete the directory entry if we
add a file under it, I honestly didn't bother to go through all the
logic. I *think* we do it correctly just thanks to all the previous
code for gitlinks. Whatever.
What I'm trying to say is that the changes are fairly straightforward,
but if somebody decides to push this, they need to think about it a lot
more than I'm ready to right now.
- read-cache.c: match the new index type with the filesystem.
This is pretty damn obvious. A S_ISDIR() always matches, and nothing
else matches at all.
- unpack-trees.c: unpack empty directories not by unpacking them
recursively into the index, but by adding them directly to the index as
a S_IFDIR entry instead.
This one almost certainly needs more work, in particular when merging
trees where one has an empty directory, and the other has files _in_
that directory! But the trivial approach makes a simple "git read-tree"
with an empty directory unpack it into the index as a S_IFDIR entry, so
now doing git-write-tree + git-read-tree should result in the original
index contents.
I think the patch itself is pretty simple, but the subtle interactions
that flow out of this all are anything but. It may "just work" almost
as-is, but quite frankly, I think people need to think about all the
issues that can happen a lot!
So see this as a basis for further work. The "further work" may be pretty
simple, or it may not be. I'm personally not that interested, but like my
original "subprojects" series, hopefully somebody else ends up running
with this (or alternatively just proving that trying to track empty
directories is a total nightmare).
Linus
---
builtin-update-index.c | 33 +++++++++++++++++++++++----------
read-cache.c | 4 ++++
unpack-trees.c | 12 +++++++++---
3 files changed, 36 insertions(+), 13 deletions(-)
@@ -94,8 +94,16 @@ static int add_one_path(struct cache_entry *old, const char *path, int len, strufill_stat_cache_info(ce,st);ce->ce_mode=ce_mode_from_stat(old,st->st_mode);-if(index_path(ce->sha1,path,st,!info_only))-return-1;+if(index_path(ce->sha1,path,st,!info_only)){+/*+*Ifweweren'tabletoindexthedirectoryasaGITLINK,+*seeifwecanjustadditasaplaindirectoryinstead.+*/+if(!S_ISDIR(st->st_mode))+return-1;+ce->ce_mode=htonl(S_IFDIR);+pretend_sha1_file(NULL,0,OBJ_TREE,ce->sha1);+}option=allow_add?ADD_CACHE_OK_TO_ADD:0;option|=allow_replace?ADD_CACHE_OK_TO_REPLACE:0;if(add_cache_entry(ce,option))
@@ -134,6 +142,11 @@ static int process_directory(const char *path, int len, struct stat *st)/* Exact match: file or existing gitlink */if(pos>=0){structcache_entry*ce=active_cache[pos];++/* Was it a directory before? */+if(S_ISDIR(ntohl(ce->ce_mode)))+return0;+if(S_ISGITLINK(ntohl(ce->ce_mode))){/* Do nothing to the index if there is no HEAD! */
@@ -162,12 +175,8 @@ static int process_directory(const char *path, int len, struct stat *st)returnerror("%s: is a directory - add individual files instead",path);}-/* No match - should we add it as a gitlink? */-if(!resolve_gitlink_ref(path,"HEAD",sha1))-returnadd_one_path(NULL,path,len,st);--/* Error out. */-returnerror("%s: is a directory - add files inside instead",path);+/* No match - try to just add it as-is */+returnadd_one_path(NULL,path,len,st);}/*
@@ -178,8 +187,12 @@ static int process_file(const char *path, int len, struct stat *st)intpos=cache_name_pos(path,len);structcache_entry*ce=pos<0?NULL:active_cache[pos];-if(ce&&S_ISGITLINK(ntohl(ce->ce_mode)))-returnerror("%s is already a gitlink, not replacing",path);+if(ce){+if(S_ISGITLINK(ntohl(ce->ce_mode)))+returnerror("%s is already a gitlink, not replacing",path);+if(S_ISDIR(ntohl(ce->ce_mode)))+returnerror("%s is already a directory entry, not replacing",path);+}returnadd_one_path(ce,path,len,st);}
@@ -181,9 +181,13 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,any_dirs=1;parse_tree(tree);subposns[i]=create_tree_entry_list(tree);-posns[i]=posns[i]->next;-src[i+o->merge]=o->df_conflict_entry;-continue;++/* If it wasn't empty, recurse into it */+if(subposns[i]){+posns[i]=posns[i]->next;+src[i+o->merge]=o->df_conflict_entry;+continue;+}}if(!o->merge)
@@ -197,6 +201,8 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,ce=xcalloc(1,ce_size);ce->ce_mode=create_ce_mode(posns[i]->mode);+if(posns[i]->directory)+ce->ce_mode=htonl(S_IFDIR);ce->ce_flags=create_ce_flags(baselen+pathlen,ce_stage);memcpy(ce->name,base,baselen);
Oh, one word of warning: that whole "pretend_sha1_file()" thing won't
create the object itself, and when I did the limited testing that I did, I
actually made sure had a magic zero-sized tree object in my object
directory.
If you don't, some things will complain, because they end up getting a
SHA1 that they cannot look up, becasue *they* didn't create that pretend
entry.
I didn't know which way I wanted to go with that thing. I was kind of
thinking that maybe we would just have the zero-sized OBJ_BLOB and
OBJ_TREE objects as special magical things, and have all git programs just
do that "pretend" at the beginning.
But that kind of thing is probably just a totally unnecessary special
case, and instead, that "pretend_sha1_file()" should have just been a
write_sha1_file(NULL, 0, "tree", ce->sha1);
instead.
Anyway, if there are issues with not finding an object called
4b825dc642cb6eb9a060e54bf8d69288fbee4904, then that's the empty tree
object, and that pretend thing was the cause.
(The git repo itself has the empty tree as an object in it, because one of
the commits has that - probably as a result of a bug, but there you have
it)
Linus
From: David Kastrup <hidden> Date: 2016-06-15 22:43:22
Linus Torvalds [off-list ref] writes:
This really updates three different areas, which are nicely
separated into three different files, so while it's one single
patch, you can actually follow along the changes by just looking at
the differences in each file, which directly translate to separate
conceptual changes:
Ok, I have now acquired enough passing familiarity with the code that
I find part of my way around it. Most of your patch looks like it
caters for the S_ISDIR type not previously in use in the index (how
about the repository?). So that makes for quite a bit of nicer looks.
The disadvantage is that it introduces a new data type and thus one
has to check all the code paths to see how older versions of git will
cater with newer data.
My idea of a fake zero-length file would have had predictable side
effects:
For checking out, git would have created the directory it needed to
place the "file", then try to write an empty file called "." and
failing. Apart from an error message (if we aren't root on Solaris),
this would have worked exactly as intended.
For deletion on checking out, git would have tried deleting "." and
failed. I have not checked the code to see whether git takes this as
a clue not to attempt deleting the containing directory. If not,
again stuff would have worked as intended. If yes, well, the user
needs to clean up manually.
I am not sure what code paths are executed when using S_ISDIR now in
unmodified git. As a theoretical question for now: do git
repositories carry some versioning inside them? Something like "don't
touch me if you are not at least version x"?
Anyway, the code becomes quite less of a dirty hack by using that data
type, so I am pretty much taking your code (which has no overlap to
the work I have done already) as is. Seems like it should play
together quite nicely with my own stuff.
So thanks for doing the heavy lifting in a difficult area.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Ok, I have now acquired enough passing familiarity with the code that
I find part of my way around it. Most of your patch looks like it
caters for the S_ISDIR type not previously in use in the index (how
about the repository?).
The object database has always had S_ISDIR (well, "always" is since very
early on, when I realized that flat trees didn't cut it).
The disadvantage is that it introduces a new data type and thus one
has to check all the code paths to see how older versions of git will
cater with newer data.
Take a look at the "subproject" patches - those did the same (adding the
ntion of a gitlink to the index), except those also changed how the tree
object looked, since now a tree could contain pointers to commits too.
My idea of a fake zero-length file would have had predictable side
effects:
As far as I can tell, it would have been exactly the same thing as the
S_IFDIR, just instead of the S_IFDIR check, you'd have had to check the
end of the filename for being '/'.
Otherwise? Exactly the same.
Except for the fact that we already supported S_IFGITLINK for subprojects
(and there it matches the "struct tree" entry, so it really *does* make
more sense that way), so supporting S_IFDIR was actually easier.
But hey, that's an implementation detail. I don't actually care all that
much. In many ways, the "long-term" data structures are much more
important than the index, the index is a purely temporary - and even more
importantly - a purely local datastructure.
The more important thing is in many ways the object storage, and that's
also the reason for doing the index the way I did - it more closely
matches what the object storage does (ie the "index" ends up mirroring a
linearized and unpacked "tree" object).
Linus
As far as I can tell, it would have been exactly the same thing as the
S_IFDIR, just instead of the S_IFDIR check, you'd have had to check the
end of the filename for being '/'.
BTW, there is actually one big difference, and the '/' at the end actually
has one huge advantage.
Why? Because my preliminary patches sort the index entries wrong. A
directory should always sort *as*if* it had the '/' at the end.
See base_name_compare() for details.
And we've never done that for the index, because the index has never had
this issue (since it never contained directories). So sit down and compare
base_name_compare (for tree entries) with cache_name_compare() (for index
entries), and see how the latter doesn't care about the type of names.
This was actually something that I hit already with subproject support,
and one of my very first patches even had some (aborted) code to start
sorting subprojects in the index the way we sort directories.
And I *should* have done it that way, but I never did. It now makes the
S_ISDIR handling harder, because directories really do have to be sorted
as if they had the '/' at the end, or "git-fsck" will complain about bad
sorting.
Sad, sad, sad. It effectively means that S_IFGITLINK is *not* quite the
same as S_IFDIR, because they sort differently. Duh.
Of course, it seldom matters, but basically, you should test a directory
structure that has the files
dir.c
dir/test
in it, and the "dir" directory should always sort _after_ "dir.c".
And yes, having the index entry with a '/' at the end would handle that
automatically.
As it is, with the "mode" difference, it instead needs to fix up
"cache_name_compare()". Admittedly, that would actually be a cleanup
(since it would now match base_name_compare() in logic, and could actually
use that to do the name comparison!), but it's a damn painful cleanup
because we don't even pass in the mode to "cache_name_compare()", since we
never needed it.
Gaah.
cache_name_compare itself isn't used in that many places, but it's used
by "index_name_pos()/cache_name_pos()", which *is* used in many places.
And again, that one doesn't even have the mode, so it cannot pass it down.
So it probably *is* easier to add the '/' at the end of the name instead,
to make directories sort the right way in the index. I'd still suggest you
*also* make the mode be S_IFDIR, though (and preferably make git-fsck
actually verify that the mode and the last character of the name
matches!).
Linus
From: David Kastrup <hidden> Date: 2016-06-15 22:43:22
Linus Torvalds [off-list ref] writes:
On Fri, 20 Jul 2007, Linus Torvalds wrote:
quoted
As far as I can tell, it would have been exactly the same thing as the
S_IFDIR, just instead of the S_IFDIR check, you'd have had to check the
end of the filename for being '/'.
BTW, there is actually one big difference, and the '/' at the end actually
has one huge advantage.
Why? Because my preliminary patches sort the index entries wrong. A
directory should always sort *as*if* it had the '/' at the end.
Hm, that's bad. The thing is that the directory names I am tracking
are called "." (that's what I was currently trying to reconcile your
code with).
And I *should* have done it that way, but I never did. It now makes
the S_ISDIR handling harder, because directories really do have to
be sorted as if they had the '/' at the end, or "git-fsck" will
complain about bad sorting.
Hm, I'll have to check what git-fsck does.
Of course, it seldom matters, but basically, you should test a directory
structure that has the files
dir.c
dir/test
in it, and the "dir" directory should always sort _after_ "dir.c".
And yes, having the index entry with a '/' at the end would handle
that automatically.
You completely lost me here. I guess I'll be able to pick this up
only after investing considerable more time into the data structures.
And I have to goto bed right now.
As it is, with the "mode" difference, it instead needs to fix up
"cache_name_compare()". Admittedly, that would actually be a cleanup
(since it would now match base_name_compare() in logic, and could
actually use that to do the name comparison!), but it's a damn
painful cleanup because we don't even pass in the mode to
"cache_name_compare()", since we never needed it.
Gaah.
cache_name_compare itself isn't used in that many places, but it's
used by "index_name_pos()/cache_name_pos()", which *is* used in many
places. And again, that one doesn't even have the mode, so it
cannot pass it down.
So it probably *is* easier to add the '/' at the end of the name instead,
to make directories sort the right way in the index. I'd still suggest you
*also* make the mode be S_IFDIR, though (and preferably make git-fsck
actually verify that the mode and the last character of the name
matches!).
The _flattened_ directory name would end in /. in my scheme. I would
not want to use "xxx/" for a directory name, and "xxx" for a tree:
that would be completely backwards. And I also don't like the
duplication of xxx when listing objects.
Sure, that's an implementation detail, but I don't like
implementations hurting my eyes...
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Of course, it seldom matters, but basically, you should test a directory
structure that has the files
dir.c
dir/test
in it, and the "dir" directory should always sort _after_ "dir.c".
And yes, having the index entry with a '/' at the end would handle
that automatically.
You completely lost me here. I guess I'll be able to pick this up
only after investing considerable more time into the data structures.
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
From: David Kastrup <hidden> Date: 2016-06-15 22:43:24
Linus Torvalds [off-list ref] writes:
Why? Because my preliminary patches sort the index entries wrong. A
directory should always sort *as*if* it had the '/' at the end.
See base_name_compare() for details.
And we've never done that for the index, because the index has never had
this issue (since it never contained directories). So sit down and compare
base_name_compare (for tree entries) with cache_name_compare() (for index
entries), and see how the latter doesn't care about the type of names.
This was actually something that I hit already with subproject support,
and one of my very first patches even had some (aborted) code to start
sorting subprojects in the index the way we sort directories.
And I *should* have done it that way, but I never did. It now makes the
S_ISDIR handling harder, because directories really do have to be sorted
as if they had the '/' at the end, or "git-fsck" will complain about bad
sorting.
Sad, sad, sad. It effectively means that S_IFGITLINK is *not* quite the
same as S_IFDIR, because they sort differently. Duh.
Of course, it seldom matters, but basically, you should test a directory
structure that has the files
dir.c
dir/test
in it, and the "dir" directory should always sort _after_ "dir.c".
And yes, having the index entry with a '/' at the end would handle that
automatically.
Personally, I am not much in favor of using different names in index
and repository.
As it is, with the "mode" difference, it instead needs to fix up
"cache_name_compare()". Admittedly, that would actually be a cleanup
(since it would now match base_name_compare() in logic, and could actually
use that to do the name comparison!), but it's a damn painful cleanup
because we don't even pass in the mode to "cache_name_compare()", since we
never needed it.
Gaah.
cache_name_compare itself isn't used in that many places,
dir.c and readcache.c
but it's used by "index_name_pos()/cache_name_pos()", which *is*
used in many places.
And again, that one doesn't even have the mode, so it cannot pass it
down.
So it probably *is* easier to add the '/' at the end of the name
instead, to make directories sort the right way in the index. I'd
still suggest you *also* make the mode be S_IFDIR, though (and
preferably make git-fsck actually verify that the mode and the last
character of the name matches!).
Actually, pretty much all of the above files are likely to get touched
by directory support one way or another anyway. One really should aim
for the cleanest solution in the long run, and this for me more or
less means that it makes no sense to have different names in index and
repository. Putting that slash in always would probably simplify some
logic in the repository as well, but I don't really like something as
marker-like as "/" in the data structures. Putting a slash there
would involve a three-phase plan:
a) make fsck and the other code deal gracefully with either slash or
no slash.
Wait until everybody uses this code.
b) make the code actually _put_ slashes there.
Wait until everybody has used this code.
c) deal with it for all eternity, oops: since rewriting the
cryptographic history of existing repositories is pretty much out
as far as I understand (which might be insufficient), one has to
navigate around slash/noslash all the time when accessing
repositories, including the sorting. The index, however, can at
one point of time phase out the slash-specific sorting. There is
no such thing as prehistoric indexes we would need to mind.
I guess that looks like not being worth the pain. Double the code or
no money back.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum