Re: Comments in read-tree about #nALT

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Aug 28, 2005, 00:16 UTC
Message-ID: <Pine.LNX.4.63.0508271941090.23242@iabervon.org>
In-Reply-To: <Pine.LNX.4.58.0508271621210.3317@g5.osdl.org>

On Sat, 27 Aug 2005, Linus Torvalds wrote:

Show 23 quoted lines

> On Sat, 27 Aug 2005, Daniel Barkalow wrote:
> >
> > What I missed was that the effect of causes_df_conflict is to give "no
> > merge" for the entry, rather than giving an error overall. So I do need an
> > equivalent.
>
> Daniel,
>  I'm not 100% sure what you're trying to do, but one thing that might work
> out is to just having multiple "stage 3" entries with the same pathname.
>
> We current use 4 stages:
>  - stage 0 is "resolved"
>  - stage 1 is "original"
>  - stage 2 is "one branch"
>  - stage 3 is "another branch"
>
> But if we allowed duplicate entries per stage, I think we could easily
> just fold stage 2/3 into one stage, and just have <n> entries in stage 2.
> That would immediately mean that a three-way merge could be <n> way.
>
> The only rule would be that when you add a entry to stage 2, you must
> always add it after any previous entry that is already in stage 2. That
> should be easy.

It looks like stage 2 is currently special as the stage that's similar to the index/HEAD/working tree. However, I don't see any problem with <n> entries in stage 3, except that, if you have a non-maximal number of them for some reason, it'll be impossible to determine which came from which tree.

> In fact, this extension might even allow us to solve the "multiple merge
> base" problem: we could allow multiple entries in "stage 1" too, ie one
> entry per merge base (and just collapse identical entries - there's no
> ordering involved in stage 1 entries).

That's actually the problem I was working on.

Show 5 quoted lines

> So you could merge "n" trees with "m" bases, and all without really
> changing the current logic much at all.
>
> Maybe I'm missing something (like what you're trying to do in the first
> place), but this _seems_ doable.

I'd be afraid of confusing everything by removing the uniqueness invariant, although I guess not too much does anything with entries in stages other than 0. I probably just don't find the index as intuitive as you do and as the struct tree representation.

I'm working on arranging the code to look at each path in sequence, with the input trees as the inner loop, rather than with the loops in the other order; using parse_tree to parse the objects instead of read_tree; and doing trivial merges before putting things in the cache, rather than after. I'd been thinking that this would avoid a limit on the number of stages, since I hadn't considered whether multiple entries for the same path and stage could be allowed.

I still think that my order is likely to be easier to understand and involve read-tree relying less on tricky properties of the data structures, but I'll have to get it done before I can say that for sure.

	-Daniel
*This .sig left intentionally blank*