new read-tree questions.

new read-tree questions.

[Junio C Hamano]

I am trying to understand the new git-read-tree, by using
git-resolve-script as an example and also reading read-tree.c; I
am somewhat confused.

* two-way merge (git-read-tree -m $H $M)

My understanding is that the current index is allowed to be
empty, but if it is not, they are kept at stage0, and each of
them must match $H and must be up-to-date if the merge involves
them.

To summarize my understanding of what should happen for each
path:

  stage0 (index)  stage1 ($H)             stage2 ($M)
------------------------------------------------------------
  no such path    no such path            no such path
  * this does not happen (the code would not see such thing).
  ----------------------------------------------------------
  no such path    no such path            exists
  * take $M without complaining.
  ----------------------------------------------------------
  no such path    exists                  (does not matter)   *0*
  * although index does not match $H, we do not reject, so
    that a merge can happen on an empty cache.  We take $M.
  ----------------------------------------------------------
  exists          no such path            no such path
  * reject, because index does not match $H.
  ----------------------------------------------------------
  exists          no such path            exists (index!=$M)
  * reject, because index does not match $H.
  ----------------------------------------------------------
  exists          no such path            exists (index=$M)   *1*
  * take $M (same as "keep stage0").
  ----------------------------------------------------------
  exists          exists (index!=$H)      (does not matter)
  * reject, because index does not match $H.
  ----------------------------------------------------------
  exists          exists (index=$H)       no such path        *2*
  * path is removed.
  ----------------------------------------------------------
  exists          exists (index=$H)       exists
  * take stage2.
  ----------------------------------------------------------

Does the above matrix represent the intended behaviour?

I think I understand why we would want *0*, but this asymmetry
feels wrong.

I am having trouble with the case *1*.  This would call
twoway_check with !seen_stage1 and it says OK, because the
merged tree has the same contents as what we started with.  Is
it to help the case where" the merged tree changes things the
same way we already have as our local change" case?

Also I am not sure if the code does the right thing for case
*2*.  If I am reading the code right, for such a path, we will
see stage0 and stage1, and at that point say seen_stage1 = 1 and
keep stage0 entry in "old".  Then we continue on to the next
path.  When it happens to be:

    - stage0: we barf because we still have our "old".

    - stage1: we barf because our "old" does not match the new
      path; !path_matches(old,ce) triggers.

    - stage2: we barf because our "old" does not match the new
      path; twoway_check(old, seen_stage1, ce) triggers.

Only when such a "exists-exists-removed" were the last entry,
the control falls out of the loop and "unmatched with a new
entry?"  check takes care of it without barfing.  The path is
removed which is what I understand you want to happen in the
case *2*.

Maybe my version of intended behaviour for case *2* is wrong,
but then I do not understand why.

I'll do a similar matrix for three-way merge case later and
probably ask more questions.

Re: new read-tree questions.

[Linus Torvalds]

On Mon, 6 Jun 2005, Junio C Hamano wrote:
>
> I am trying to understand the new git-read-tree, by using
> git-resolve-script as an example and also reading read-tree.c; I
> am somewhat confused.

It _is_ a confusing piece of code. You don't see it in the revision 
history, but I threw away a lot of trials that were crapola.

> * two-way merge (git-read-tree -m $H $M)
> 
> My understanding is that the current index is allowed to be
> empty, but if it is not, they are kept at stage0, and each of
> them must match $H and must be up-to-date if the merge involves
> them.

The rule really boils down to: "no information that only existed in the
old 'stag0' must be lost".

So that means that an empty old stage0 is always fine.

It also means that if the old stage0 exactly matches the result, then 
that's also always fine (regardless of the state of the actual checked out 
file: we've not _changed_ anything).

But it means that if the old stage0 gets deleted or over-written, then the 
information that the old stage0 _used_ to have needs to be encoded either 
in the result _or_ it needs to have been there in the original tree, ie 
the "loss" of information needs to be in the merge itself.

See? It's ok to drop information if that drop is encoded in the merge
itself ("we're merging a delete"), but it's _not_ ok to drop information
that wasn't part of the merge ("we're merging a delete where the index
file described something more than what was in the original tree")

Does that clarify what I'm aiming for? It may not clarify the code (which 
may or may not match my aims ;), but at least it hopefully clarifies what 
the _point_ of the code was supposed to be.

> To summarize my understanding of what should happen for each
> path:
> 
>   stage0 (index)  stage1 ($H)             stage2 ($M)
> ------------------------------------------------------------
>   no such path    no such path            no such path
>   * this does not happen (the code would not see such thing).

Yeah, I htink I get this right ;)

>   ----------------------------------------------------------
>   no such path    no such path            exists
>   * take $M without complaining.

Yes.

>   ----------------------------------------------------------
>   no such path    exists                  (does not matter)   *0*
>   * although index does not match $H, we do not reject, so
>     that a merge can happen on an empty cache.  We take $M.

Right. We didn't lose anything hugely important. 

In theory this could be a delete that we've missed, and we could add a 
flag to actually reject this case. However, it's always easy to "recover" 
deletes (just delete it again ;), so the loss of information is absolutely 
minimal, and it allows starting from an empty index file.

But this is debatable. We could reject it if you prefer that, and if you 
want to make it a command line flag I'll definitely apply the patch.

>   ----------------------------------------------------------
>   exists          no such path            no such path
>   * reject, because index does not match $H.

Exactly. The end result would have dropped the existing data, and the 
_merge_ didn't contain that drop, so we reject that.

>   ----------------------------------------------------------
>   exists          no such path            exists (index!=$M)
>   * reject, because index does not match $H.

Yes.

>   ----------------------------------------------------------
>   exists          no such path            exists (index=$M)   *1*
>   * take $M (same as "keep stage0").

This one is questionable. I think it should be accepted simply because 
there's no point in not accepting it.

>   ----------------------------------------------------------
>   exists          exists (index!=$H)      (does not matter)
>   * reject, because index does not match $H.

Yes.

>   ----------------------------------------------------------
>   exists          exists (index=$H)       no such path        *2*
>   * path is removed.

Yes. This drops the information, but since the merge contained that 
_exact_ drop, that's what we want it to do. This one is not questionable 
at all (except I got it wrong at one stage ;)

>   ----------------------------------------------------------
>   exists          exists (index=$H)       exists
>   * take stage2.

Yes. 

> Does the above matrix represent the intended behaviour?
> 
> I think I understand why we would want *0*, but this asymmetry
> feels wrong.

Yup, you got it.

> I am having trouble with the case *1*.

The fact that you're having trouble is good, it means you realize that 
reversing the merge doesn't get you the original state.

> Also I am not sure if the code does the right thing for case
> *2*.  If I am reading the code right, for such a path, we will
> see stage0 and stage1, and at that point say seen_stage1 = 1 and
> keep stage0 entry in "old".  Then we continue on to the next
> path.  When it happens to be:

You're right. I messed up. Again. And the test-case I used for this 
happened to not care (I think it may have been the only file, and as such 
the next path never happened).

Anyway, you definitely get the idea.

Another way of encoding the rules: we _should_ eventually aim for a
situation where if a git-read-tree succeeds (even if it leaves crap
entries in the tree), we should be able to do a

	git-read-tree -u -m <OLDHEAD>

and get back to the old state - or at least "close enough" (right now "-u"  
doesn't do anything for the single-tree case, and "-m" complains about
unmerged entries, but the point isn't that it works today, the point is 
what should be possible at some point ;)

		Linus

Re: clarifying two tree merge semantics

[Junio C Hamano]

By the way, there is one case that you need to keep an eye on if
you are making further fixes to "git-read-tree -m $H $M",
especially now we are talking about keeping what we slurp from
stage0 sometimes:

 (1) index has DF (file)
 (2) $H has DF (file); the index matches it.
 (3) $M has DF/DF (file), implicitly making DF a directory.

For path DF, this rule from the earlier matrix applies:

  exists          exists (index=$H)       no such path        *2*
  * path is removed.

For path DF/DF, this rule from the earlier matrix applies:

  no such path    no such path            exists
  * take $M without complaining.

Thanks to *2*, the current code gets it right and we do not end
up with a cache that records both DF and DF/DF at the same time.
I cannot tell if it is by design or by accident :-).

There is a safety valve at the end of write-tree to refuse to
write out such a nonsensical tree but as Pasky argued back then
(a similar problem was discussed and resolved when you were
away, around the beginning of May, involving update-cache), when
that safety valuve was added, the damage has already been done
if we allow such a cache entry to be created in the first place.