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

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

[Junio C Hamano]

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

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

[Matthias Lederhofer]

Junio C Hamano <junkio@cox.net> wrote:
> 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/".

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?

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

[Brian Gernhardt]

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

> Junio C Hamano <junkio@cox.net> wrote:
>> 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/".
>
> 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?

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

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

[Junio C Hamano]

Matthias Lederhofer <matled@gmx.net> writes:

> Junio C Hamano <junkio@cox.net> wrote:
>> 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/".
>
> 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?

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.

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

[Steven Grimm]

Junio C Hamano wrote:
> 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).
>   

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

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

[Junio C Hamano]

Steven Grimm <koreth@midwinter.com> writes:

> 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.

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.