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

[Angel Ezquerra]

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. In fact this is a problem that
users face today when they must manually merge the .hgtags file.

>> I don't think forcing the
>> user to manually write some complex command line incantation in a
>> perfectly normal scenario is a good idea. hg is not git :->
>
> I agree, no common case should leave the user in that situation. With the
> prompts mentioned above it would be so uncommon that nothing in the
existing
> tests or your new tests would trigger it (I assume).

I think if we agreed on the correct behavior in cases such as the one I
described above it could definitely be possible to solve most (perhaps even
all) conflicts without user intervention.

Mercurial already has a built-in algorithm to resolve tag conflicts, which
is implemented in the tags/findglobaltags() function which I mentioned
above. We could put a requirement on the tag merge algorithm that the
merged tag file should be such that the output of the findglobaltags
algorithm does not change... We could perhaps even use that findglobaltags
algorithm for doing the merge. If we did there would never be merge
conflicts (at least undecidable ones).

However perhaps that is a bit to ambitious as a first step? That is the
main reason I did not try to pursue this sort of solution in the first
place.

Maybe Matt or others that were around when the current tag infrastructure
was put in place could give their two cents?

>> What I'd like is to have a way to configure mercurial to first try the
>> internal:hgtags tool, and then try some other tool in case of failure,
>> while still letting users completely override the automatic merge
>> algorithm as you suggest.
>>
>> What about this?:
>>
>> - We add an internal:hgtags tool as you suggest.
>> - We add a config entry that lets the user select a fallback hgtags
>> merge tool. For example "merge-tools.internal:hgtags.fallback".
>> - internal:hgtags runs the automatic merge algorithm (with the
>> improvements you suggested). If merge-tools.internal:hgtags.fallback
>> is not set the default text merge tool is run when internal:hgtags
>> fails. Otherwise the fallback tool is run.
>
>
> If there is a need for such fallback functionality in this case then it
> should be made a general feature of the already quite complex merge-tool
> selection mechanism.

Maybe, but nothing stops a merge tool from reading an entry on mercurial's
config file even today? That being said maybe this won't be necessary
depending on the outcome of the rest of this discussion.

>>>> As I said I'd rather not turn this into
>>>> a full blown merge tool unless you really think I should.
>>>
>>> I think a "less than perfect" tool could be fine as something users can
>>> decide to configure in merge-patterns. That could be a fine first
>>> milestone.
>>>
>>> I think it has to be "perfect" before we can consider enabling it by
>>> default
>>> ... and even more so if there is no way to opt out.
>>
>> Depends on what you consider "perfect". IMHO it is OK for a "perfect
>> merge tool" to fail when there are unsolvable conflicts. Do you agree?
>
> For some kind of "fail", yes. Asking for user input would be ok. Handling
> the simple cases but not giving the user any help for the more complex
cases
> would be less OK.
>
> On a related note: These changes towards using the version control history
> instead of the history inside .hgtags kind of change the role of this
> history inside .hgtags. It had some semantics but we never knew exactly
how
> users would leave the file after merge conflicts. Do we all (including
Matt)
> agree that we now should see it as something that we only preserve and
> maintain for backward compatibility?

Even with all these changes mercurial's "global tag calculation" algorithm
will still rely on the tag ranks which are stored on the .hgtags file. It
seems that any tag merge algorithm must make sure to preserve the ranks
(although perhaps not the actual tag histories) to avoid changing the
output of the global tag calculation.

Cheers,

Angel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://selenic.com/pipermail/mercurial-devel/attachments/20140324/181cb4fe/attachment.html>