[RFH] straightening out "read-tree -m"

While everybody else was having fun with low-hanging fruit performance tweaking ;-), I was looking at rather depressing picture.

I do not have much energy left to look into this further tonight, but I noticed this while drawing a case table to deal with the recent "why can't I switch between these two branches" problem.

First part is sort of "accomplishment" for tonight. Two case tables that describe desired semantics (meaning, the current "read-tree -m -u" does not do this, and neither does merge-recursive because it shares the same unpack-trees backend).

* 2-way "read-tree -m -u A B".

While switching from branch A to branch B, if a path "foo" is directory/file in A while the path is directory/file in B, then these things should happen...

A B Outcome ---------------------------------------------------------------- D D No problem.

D	F	This should result in refusal when there are
                local modification to paths in "foo" directory,
		or there are untracked (but unignored) paths in
                "foo/".

F	D	This should result in refusal if "foo" has local
                modification.

F	F	This should result in refusal if "foo" has local
		modification.

The patch to "verify_absent()" I sent out earlier tries to deal with the second case above, although it still has issues (namely, the *indpos needs to be recomputed after replacing potentially multiple entries under "foo/" with "foo" from B, which the patch does not do).

Then I started to wonder if we have similar problem on the 3-way side.

* 3-way "read-tree -m -u O A B"

While on branch A, if you try to merge branch B using O as the merge base, if a path "foo" is D/F in A/B/C (there are 8 combinations), these things should happen...

O	A	B	Outcome
----------------------------------------------------------------
D	D	D	No problem.  Paths in the "foo/" directory 
			are merged subject to the usual rule.

D	D	F	File "foo", which did not exist in ancestor
			and we did not touch, is created.  Which means
			that contents of "foo/" is about to be
			lost.  We need to refuse this unless
			everything in "foo/" matches between O
			and A, there is no local modifications
			in "foo/", and there is no untracked but
			unignored paths in "foo/".

D	F	D	File "foo", which did not exist in
			ancestor and they did not touch, is
			created, so we would want to keep it.
			Which means that their changes to paths
			in "foo/" will be lost.  We should leave
			conflict for paths in "foo/" that are
			different between O and B.

D	F	F	No problem.  This is usual "added on
			both branches" conflict.

F	D	D	No problem.  Paths in the "foo/"
        		directory have usual "added on both
        		branches" conflict.

F	D	F	No problem.  If file "foo" was modified
			by them (i.e. O!=B) then usual "remove-modify"
			conflict arises.

F	F	D	No problem.  If file "foo" was modified
			by us (i.e. O!=A) then usual "remove-modify"
			conflict arises.  Also "foo" must not
			have local modifications.

F	F	F	No problem, usual 3-way rule applies.
			Also "foo" must not have local modifications.

The sad story is how confused the current unpack-trees is, given the test case for the above 3-way.

The attached script demonstrates one aspect of the sorry state of three-way merge done with unpack-trees. You would notice that there are multiple paths that have both stage '0' entry and higher stage entries at the same time --- I do not think this should not happen.

Git v1.0.0 to v1.2.0 refuse to merge but leaves two stage '0' entries for path '4' and '8' (which is already incorrect but in a different way). v1.3.0 and later leaves stage 0/1/2/3 entry for path '8'.

Depressing...

#!/bin/sh

# If your 'test' is precious, do not run this script! /bin/rm -fr test

create () {
	rm -f .git/index
	mark="$1"
	shift
	num=0
	for t
	do
		num=$(($num+1))
		rm -fr "$num"
		case "$t" in
		D)
			mkdir "$num"; t="$num/$num" ;;
		F)
			t="$num" ;;
		esac
		echo "$mark" >"$t"
		git add "$t"
	done
	git commit -m "$mark: $*"
}

mkdir test || exit cd test git init-db

create O D D D D F F F F git tag O git branch a git branch b

rm -rf ? git checkout a create A D D F F D D F F git tag A

rm -rf ? git checkout b create B D F D F D F D F git tag B

rm -rf ? git checkout a git read-tree -m O A B

git ls-files -s

Junio C Hamano <junkio@cox.net> wrote:

What about ignored configuration files like config.mak? Let's say there is an ignored configuration file in a subdirectory. If this subdirectory is replaced by a file git would delete the ignored configuration file?

On Mar 18, 2007, at 8:18 AM, Matthias Lederhofer wrote:

I would sincerely hope that a file not being tracked by git would count as "local modifications" in that case. "Ignored" does not mean "unimportant".

My $0.02, ~~ Brian

Matthias Lederhofer <matled@gmx.net> writes:

You certainly could argue that way. At that point switching from branch A to branch B would become impossible after building in A ("foo/hello.o" is built but that is ignored) without running "make clean" first, but I do not think it is a big deal.

Anyway, my Request For Help was not about such details about what to do with untracked working tree files. It was about a more fundamental issue, the confused behaviour of unpack-trees engine (switching branches, and performing tree-level 3-way merges), which is used by both read-tree and merge-recursive. It's so central in everyday git operation, that leaving it buggy in the presense of D/F conflict is an more serious issue, and compared to that what we may end up doing to untracked working tree files is secondary. We'll get to it eventually but we need to deal with bigger issue first, as its resolution would change how the code to deal with the untracked files will be implemented.

In any case, the reason why for full two years this switching between branches that have "foo/" and "foo" never surfaced as an issue is that people are saner than doing that in practice (and I think people coming from CVS couldn't do that before so they may not even think about doing so).

For example, if you are writing a paper, it may start out as a small single file, paper.txt (or paper.tex), then as it grows you might split it and give it its own subdirectory. You would not create paper.txt directory and have its chapters in separate files paper.txt/ch01.txt, paper.txt/ch02.txt, etc. when you do so in practice. Your directory would most likely be named just "paper", and the chapters are in paper/ch01.txt, paper/ch02.txt.

So in that sense, switching branches with D/F conflict is much lower priority item in the real world sense than others cooking right now. But I hate leaving known bugs in such a core piece like unpack-trees, and that was why I sent out my RFH.

By the way, setting Mail-Followup-To: to me is rude. Please don't. The person who wants to talk to you about _your_ message may not be interested in bothering me.

Junio C Hamano wrote:

I can at least give you some insight into the real-world scenario that led to the current discussion. It's only slightly insane. :) We had a shell script called "foo" in our source directory. It had to turn into a multi-source-file app for various reasons. So the standalone script got replaced with a directory "foo" containing the source files.

I suppose one could argue that we should have called the original "foo.sh" or something and renamed it to "foo" at build/deploy time, but given that extensions aren't required on shell scripts (and that we have zillions of other scripts happily living without extensions) I suppose that just felt unnecessary.

By the way, Subversion required that we do this in two separate commits, the first to delete the shell script and the second to make the directory with the files in it. We originally tried to do both in one commit and it got confused. Then, some time after we'd done the separate commits in svn, we updated our git-svn repositories and ran into the problem.

In fact, when we tried to merge in the batch of changes from the git-svn tracking branch, we also ran into merge problems. Git got rather confused and the merge started complaining about files being untracked when in fact they were tracked in both branches! It looked like the index and/or working copy were left in an inconsistent state when the merge engine bailed out on the file-to-directory transition.

On my to-do list for next week is to try to come up with a minimally complex test case to demonstrate the problem, as the actual repositories in question are pretty convoluted and there were a bunch of other unrelated changes. I didn't mention it before now because I knew my description was certain to be too vague to be useful without a test case to look at.

We ended up successfully doing the merge by doing exactly what we had to do on the Subversion side: first explicitly merge up to the "delete the file" revision, then merge the "create the directory" revision. After that git was able to successfully fast-forward us through the subsequent revisions.

-Steve

Steven Grimm <koreth@midwinter.com> writes:

You are free to come up with test case, but I have a feeling that the problem is already well understood (and that is why the last part of my RFH matters a lot more than the former "case table"). In short, "read-tree -m" (and unpack-trees) is screwy in the presense of D/F conflicts.