[PATCH 3 of 3 V2] merge: add automatic tag merge algorithm

[Angel Ezquerra]

On Wed, Mar 26, 2014 at 7:46 PM, Matt Mackall <mpm at selenic.com> wrote:
> On Mon, 2014-03-24 at 19:31 +0100, Angel Ezquerra wrote:
>> On Mon, Mar 24, 2014 at 4:42 PM, Mads Kiilerich <mads at kiilerich.com> wrote:
>> > On 03/24/2014 02:29 PM, Angel Ezquerra wrote:
>> >>
>> >> On Mon, Mar 24, 2014 at 1:52 PM, Mads Kiilerich <mads at kiilerich.com>
>> >> wrote:
>> >>>>
>> >>>> 2. When the hgtagmerge algorithm fails we want to revert to a regular,
>> >>>> old-style text merge, so that the user can use his merge tool of
>> >>>> choice to do the merge. I don't think (but I may be wrong) that it is
>> >>>> possible to configure mercurial to call a second merge tool if the
>> >>>> first one that you specified via a merge pattern fails.
>> >>>
>> >>>
>> >>> I would say that the tool should be so good that we think it can solve
>> >>> all
>> >>> common and not-so-common cases.
>> >>>
>> >>> In the rare case where it fails I think it would be fine if it failed
>> >>> with
>> >>> "error: .hgtags cannot be merged automatically - use 'hg merge --config
>> >>> merge-patterns..hgtags=!' to resolve with your normal merge tool" ... or
>> >>> suggest 'hg merge --tool kdiff3 .hgtags'. Users who end up here are
>> doing
>> >>> weird stuff. Let's give them the power and responsibility for working it
>> >>> out
>> >>> instead of adding more conceptual complexity.
>> >>
>> >> The thing is that users don't need to do very weird stuff for a fully
>> >> automated merge to be impossible. Two different users may decide that
>> >> a different revision must be tagged "A". That is an actual conflict
>> >> that no automated merge tool can resolve.
>> >
>> >
>> > Right. That is a common case I haven't considered/mentioned.
>> >
>> > The tool could ask "tag X was 01234, (l)ocal changed to 12345, (o)ther
>> > changed to 23456 - pick one" (similar to largefile merging) (and similar
>> > prompts for the 2 change+delete cases and add+add).
>> >
>> > Your tool has the necessary information ... and I think it would be
>> > reasonable to expect it to handle these common cases too.
>>
>> I thought about this a bit before going for a simpler algorithm as a first
>> step.
>>
>> It is true that the algorithm has the necessary information. However it is
>> not as simple as just choosing one tag or the other. We must also combine
>> the histories of the tags that are in conflict (or at least preserve what
>> the tags.findglobaltags algorithm calls the tag "rank").
>
>> For example, the local revision may have the following entries in it's
>> .hgtags file:
>>
>> HASH_A TAG_A
>> HASH_B TAG_A
>> HASH_C TAG_A
>>
>> While the remote .hgtags may be:
>>
>> HASH_A TAG_A
>> HASH_D TAG_A
>> HASH_E TAG_A
>> HASH_F TAG_A
>>
>> In theory the merge algorithm should pick HASH_F as the hash of the
>> revision pointed to by TAG_A since it is the tag with the longest history
>> (i.e. the highest tag "rank"). However, what should the merged tag history
>> be? It seems that we could just keep the tag history of the tag with the
>> highest rank, i.e.:
>>
>> HASH_A TAG_A
>> HASH_D TAG_A
>> HASH_E TAG_A
>> HASH_F TAG_A
>>
>> Would that be OK? It seems so, but we'd be "losing" the TAG_A history from
>> the local revision branch... It does not seem to really be a problem and in
>> fact there is no way around that I think.
>
> I don't think this is the right answer. I think instead we should keep
> all of them as each on is an ordering assertion. We should probably
> interleave them in order of distance from tip, so either:
>
> A < B < C        <- closer to tip, so B trumps D
> A < D < E < F
> -------------
> A < D < B < E < C < F
>
> or
>
> A < D < E < F
> A < B < C
> -------------
> A < B < D < C < E < F
>
> This basically says "at the time of merge, this is how things stood in
> the tag ranking". As a side effect, the "rank" of F gets increased a
> bunch. I think this is fine, as it's primarily a tie-breaker that says
> "the tag with the most history wins".

OK. I guess it is fine to give a big bump to the rank of a tag that
has been merged, even if that means changing that the findglobaltags
algorithm will say after the merge. That would rule out my idea of
perhaps trying to make sure that the output of a merge does not change
the result of the findglobaltags algorithm though...

Another thing that must be decided is how to handle deleted tags:
- For explicitly deleted tags your suggest would not work as is,
because a removed tag points to the 0000 revision and thus cannot be
ordered with the rest. Maybe we could simply follow the rule that a
deleted tag must be added right after the tag it deletes?
- For implicitly deleted tags (i.e. those that were removed from
.hgtags) I think we could reintroduce the tag with its history (as it
was on the base of the merge) on the head that were the tag is
removed, add an explicit deletion marker on top of it, and then use
the regular tag merge algorithm for explicitly deleted tags

> (At a higher level, I have to confess I don't care all that much:
> development teams who are moving the same tags simultaneously on
> multiple branches are begging for horrible things to happen to them
> anyway. But the above is closer to correct.)

OK, I will combine this with Mads suggestions and try to come up with
a new patch.

Thanks to you both for your comments!

Angel