Broken adding of cache entries

Dear diary, on Sat, May 07, 2005 at 04:09:27AM CEST, I got a letter where Kay Sievers <kay.sievers@vrfy.org> told me that... ..snip..

Duh. Well, what could be the reasonwhy cache_name_compare() cares about flags at all? Can you _ever_ have two same-named entries? Junio, what do you think about something like this?

I'll have a look later but as I recall the code (I'm writing this without looking at the specific code, just your patch hunk), the flag comparison there is not about blob vs tree modes but for "stages"; it must answer that two entries with the same name but in different merge stages are different.

I'll keep this in git-jc repository until Linus returns. Pasky and Kay could you give it a try?

-- test case --

$ ls -a ./ ../ $ git-init-db defaulting to local storage area $ date >path $ git-update-cache --add path $ rm path $ mkdir path $ date >path/file $ git-update-cache --add path/file $ git-ls-files --stage 100644 1738f2536b1201218c41153941da065cc26174c9 0 path 100644 620c72f1c1de15f56ff9d63d6d7cdc69e828f1e3 0 path/file $ git-ls-tree $(git-write-tree) ;# using old one 100644 blob 1738f2536b1201218c41153941da065cc26174c9 path 040000 tree ec116937f223e3df95aeac9f076902ae1618ae98 path $ ../git-write-tree ;# using new one You have both path and path/file fatal: write-tree: not able to write tree $ exit

---------------------------------------------------------------- Notice index that has path and path/file and refuse to write such a tree.

Kay Sievers noticed that you can have both path and path/file in the cache and write-tree happily creates a tree object from such a state. Since a merge can result in such situation and the user should be able to see the situation by looking at the cache, rather than forbidding add_cache_entry() to create such conflicts, fix it by making write-tree refuse to write such an nonsensical tree.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---

write-tree.c | 35 +++++++++++++++++++++++++++++++---- 1 files changed, 31 insertions(+), 4 deletions(-)

Dear diary, on Sat, May 07, 2005 at 09:22:21PM CEST, I got a letter where Junio C Hamano <junkio@cox.net> told me that...

I'd still prefer add_cache_entry() to just replace the original entry (as it does otherwise). Only make it to care about which stage it is working in, to make merges to work. IOW, I think you are solving this at the wrong workflow point. It is too "late" to know at that point, and (a huge) PITA for the higher levels to deal with it then - that all when it shouldn't fail _at all_ in the first place.

What about

--- b7ae63ab415e556c2f0f0ad2803f701b4a6d6956/read-cache.c (mode:100644) +++ uncommitted/read-cache.c (mode:100644)

PB> What about PB> ... suggested changes removed. PB> then? (Completely untested and everything.)

It is clear that it is untested. In the sequence Kay had trouble with:

    $ rm -fr path; date >path
    $ git-update-cache --add path
    $ rm -f path; mkdir path; date >path/file
    $ git-update-cache --add path/file

The cache_name_compare function you are looking at is called with "path" and "path/file", and compares the name strings (up to the length of the shorter one), and when they are the same, then compares the lengths of them. At that point, the if() statements have already answered that "path" comes before "path/file" and your changes will _not_ change the behavior of that function.

That said, I understand the behaviour you would want to see, and I tend to agree that this should be prevented from happening in the first place when git-update-cache happens. Let me think a bit more about it.

PB> I'd still prefer add_cache_entry() to just replace the original entry PB> (as it does otherwise).

I do not think it should just silently replace; instead it should make the user take notice, because this is an unusual situation. In other words, it should refuse until the user makes a conscious decision to tell it that the user is removing it and then placing something completely different.

This implies (I am thinking aloud here):

    $ find fs -type f -print | xargs git-update-cache --add
    $ rm -fr fs
    $ date >fs
    $ git-update-cache --add fs

would refuse to add "fs" because it notices it has some entry whose "name" field starts with "fs/". Likewise, for the opposite sequence:

    $ date >fs
    $ git-update-cache --add fs
    $ rm -f fs; mkdir fs; date >fs/file    
    $ find fs -type f -print | xargs git-update-cache --add

Telling git-update-cache about anything that contains a '/' in its name would first check if an entry whose name is exactly one of the leading path prefix, and refuses the operation if it finds one.

The above logic should work and it would also work if we decide to just replace without refusing as well. I'll code it up and see which one I like; maybe it will end up as an option.

This patch makes git-update-cache --add refuse to create an index where one entry is a file and another entry needs to have that entry as its leading directory.

I am not quite sure the semantics is quite right, so I am holding it off from putting it in git-jc repository for now, but please review it, give it a try and tell me what you think.

Here is what I did.

    $ ls -a
    ./  ../
    $ git-init-db
    defaulting to local storage area
    $ date >path
    $ git-update-cache --add path
    $ rm -f path; mkdir path; date >path/file
    $ git-update-cache --add path/file
    fatal: Unable to add path/file to database
    $ git-update-cache --remove path           ;# *****
    fatal: Unable to add path to database
    $ git-update-cache --force-remove path
    $ git-update-cache --add path/file
    $ git-ls-files --stage
    100644 3e3f5e43a8e7baa7f0b1f2d7b99ed25fcbe582d2 0 path/file
    $ rm -fr path
    $ git-update-cache --remove path/file
    $ mkdir path; date >path/file
    $ git-update-cache --add path/file
    $ git-ls-files --stage
    100644 1b4e067c82b90419c2d2ce80e72079f926a49cc3 0 path/file
    $ rm -fr path; date >path
    $ git-update-cache --add path
    fatal: Unable to add path to database
    $ git-update-cache --remove path/file
    $ git-update-cache --add path
    $ git-ls-files --stage
    100644 b4509b7a4fed200befc45746061eb1d32ad6cbc9 0 path

The one marked with ***** is what I am debating myself about, but that one would probably be an independent fix.

Not-signed-off-yet-by: Junio C Hamano <junkio@cox.net>
---
jit-diff 0:7 read-cache.c
# - HEAD: Notice tree objects with duplicate entries.
# + 7: Refuse to create file/dir conflict cache entry.

JCH> I am not quite sure the semantics is quite right, so I am JCH> holding it off from putting it in git-jc repository for now, but JCH> please review it, give it a try and tell me what you think.

Ok, I have two updates pushed out at git-jc archive at http://members.cox.net/junkio/git-jc.git/

Here is the summary of what the changes do.

The first commit is to simply prevent Kay's situation from happening from git-update-cache.

By default, git-update-cache refuses to:

 - add "path" when "path/file" exists.  That is, you cannot
   replace a directory with a file (or a symlink).

 - add "path/file" when "path" exists.  That is, you cannot
   replace a file (or a symlink) with a directory.

And the second commit introduces --replace option to the command. When --replace is in effect, instead of refusing, the existing path that conflicts with whatever is being added is dropped with a warning message. That means you would lose an entire subdirectory from the index when you rename it and replace it with a file and then call git-update-cache on it (which is probably fine and what the user expects anyway).

Note that this is not enough to prevent nonsensical tree from happening. Three-way read-tree can be fed with an ancestor tree that does not have anything interesting, one side adding "path" (as a file) and the other side adding "path/file". Just after read-tree finishes reading three trees, you would have:

    100644 1 not-interesting
    100644 2 not-interesting
    100644 3 not-interesting
    100644 2 path
    100644 3 path/file

And all of these paths are candidate for trivial "collapsing to stage 0" operation. You would end up with path vs path/file conflicts this way, so the previous change to write-tree to prevent it from writing such a result is still needed.

Ideally the "collapsing to stage 0" logic could also be tweaked to detect and prevent this from happening, but I'd rather keep it simple for now (the tool should not be too clever). The user cannot write such a tree, and when this kind of conflict happens, essentially both heads being merged needs to be examined and manual resolution is required anyway.

Dear diary, on Sun, May 08, 2005 at 07:22:31AM CEST, I got a letter where Junio C Hamano <junkio@cox.net> told me that...

I wanted to merge with you, but I'd like to make some (mostly minor) nitpicks first.

Sorry for totally garbled whitespace and everything, this is just gpm.

--- e19665d8d42877246ac7e98a7c671d11adbe8b56/read-cache.c  (mode:100644)
+++ uncommitted/read-cache.c  (mode:100644)
+               char *ep = strchr(cp, '/');
+               if (ep == 0)

Please use NULL.

+static struct alternate_object_database
+{
+       char *base;
+       char *name;
+} *alt_odb;

The commonly accepted style is to have the { bracket on the same line as the struct identifier.

Sticking a brief explanation to prepare_alt_odb(), like "pass 0 allocates the array and pass 1 fills it" couldn't hurt, it took me a while of staring at it to figure out. There's also unused @buf variable. But I personally think all this alt_odb code is quite creepy. ;-)

--- e19665d8d42877246ac7e98a7c671d11adbe8b56/write-tree.c  (mode:100644)
+++ uncommitted/write-tree.c  (mode:100644)
-                       if (++unmerged > 10) {
+                       if (10 < ++funny) {

Do those changes make any sense? The former version is certainly much easier to read for me. I can live with it in the new code, but changing old code to it...

With the current update-cache protections, how can you legally achieve a cache with duplicate entries, so that you need to check for that in write-tree?

Thanks,

PB> Dear diary, on Sun, May 08, 2005 at 07:22:31AM CEST, I got a letter PB> where Junio C Hamano <junkio@cox.net> told me that...

PB> I wanted to merge with you, but I'd like to make some (mostly minor) PB> nitpicks first.

I've addressed the points you raised and pushed them out. Thanks again for the review.

Dear diary, on Sun, May 08, 2005 at 11:06:02PM CEST, I got a letter where Junio C Hamano <junkio@cox.net> told me that...

Great, thanks.

Still, I'd like to know why the checking in write-tree is necessary.

PB> Still, I'd like to know why the checking in write-tree is necessary.

The following is just a rephrase of what I wrote in my previous message <7vll6q70mg.fsf@assigned-by-dhcp.cox.net>.

------------ test.sh ------------ #!/bin/sh

test="++testdir" rm -fr $test mkdir $test cd $test || exit

show () {
	echo "# ls ($1)"
	ls -F
	echo "# git-ls-files --stage ($1)"
	git-ls-files --stage
	case "$2" in
	'')	;;
	?*)
		echo "# git-ls-tree -r ($1)"
		git-ls-tree -r $2
		;;
	esac
}

echo "# Original" git-init-db date >not-so-interesting git-update-cache --add not-so-interesting original=$(echo Original | git-commit-tree $(git-write-tree)) show Original $original rm -rf path not-so-interesting

echo "# Branch A"
git-read-tree $original
git-checkout-cache -f -a
date >path
git-update-cache --add path
branchA=$(echo Branch A Changes |
          git-commit-tree $(git-write-tree) -p $original)
show 'Branch A' $branchA
rm -rf path not-so-interesting

echo "# Branch B"
git-read-tree $original
git-checkout-cache -f -a
mkdir path
date >path/file
git-update-cache --add path/file
branchB=$(echo Branch B Changes |
          git-commit-tree $(git-write-tree) -p $original)
show 'Branch B' $branchB
rm -rf path not-so-interesting

echo "# Attempt merge O A B" mb=$(git-merge-base $branchA $branchB) echo "Original $original" echo "Branch-A $branchA" echo "Branch-B $branchB" echo "MergeBase $mb"

git-read-tree -m $mb $branchA $branchB show "Merge" ------------ test.out ------------ # Original defaulting to local storage area Committing initial tree 682c2247823f37e4cf64f240009c9ba932b04fe0 # ls (Original) not-so-interesting # git-ls-files --stage (Original) 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 not-so-interesting # git-ls-tree -r (Original) 100644 blob 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 not-so-interesting # Branch A # ls (Branch A) not-so-interesting path # git-ls-files --stage (Branch A) 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 not-so-interesting 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 path # git-ls-tree -r (Branch A) 100644 blob 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 not-so-interesting 100644 blob 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 path # Branch B # ls (Branch B) not-so-interesting path/ # git-ls-files --stage (Branch B) 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 not-so-interesting 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 path/file # git-ls-tree -r (Branch B) 100644 blob 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 not-so-interesting 040000 tree f4e939c9b65aff9a59118f3f3f299ef30744adfa path 100644 blob 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 path/file # Attempt merge O A B Original 40c1d8a0e79df9e681667e0074664266b6bd9935 Branch-A 88b3e7e4ce0ba55c60fe4de6523968ecabb1cc78 Branch-B 0faa7f6b7f68ce2951fe3f26f937766ee53dc11c MergeBase 40c1d8a0e79df9e681667e0074664266b6bd9935 # ls (Merge) # git-ls-files --stage (Merge) 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 0 not-so-interesting 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 2 path 100644 9bcc8fabbbb587ba312a45b144dce8f4d9191da5 3 path/file

PB> Still, I'd like to know why the checking in write-tree is necessary.

Ok, having thought about it a bit more, I think we can yank it out. I'd rather keep ourselves cautious, though; there may be some other ways we haven't thought of to create such nonsense, and it would not hurt to be cautious before writing a tree out.

JCH> Ok, having thought about it a bit more, I think we can yank it JCH> out. I'd rather keep ourselves cautious, though; there may be JCH> some other ways we haven't thought of to create such nonsense, JCH> and it would not hurt to be cautious before writing a tree out.

Here is a revert you can apply after merging with the tip of my tree if you wanted to. As you pointed out correctly, three-way read-tree would not produce the situation as I feared, and the attempt to postprocess the result by git-merge-one-file-script git-merge-cache calls would be caught with the changes we made to git-update-cache, so there is no need for the extra check by write-tree in that workflow example. Sorry for being ultra dense.

The only reason why I am holding off from pushing this out is because I still cannot convince myself that we eradicated _all_ the possibile paths to create such nonsense in the index, and I feel safer to keep the check this patch is reverting, at least for now.

---
Author: Junio C Hamano <junkio@cox.net>
Date:   Sun May 8 15:34:17 2005 -0700
    
Revert the extra-careful check in write-tree.c

I am not particularly fond of reverting this, but with the git-update-cache changes it is unlikely that we will have file vs directory conflicts in the index anymore, so there may be no point in being extra careful when writing the tree out.

Signed-off-by: Junio C Hamano <junkio@cox.net>