Patchwork [3,of,3,V2] merge: add automatic tag merge algorithm

# HG changeset patch
# User Angel Ezquerra <angel.ezquerra@gmail.com>
# Date 1395006485 -3600
#      Sun Mar 16 22:48:05 2014 +0100
# Node ID ee742da53c1e43b33d84555662da9ed3ba938f6f
# Parent  d2b518fe1a6c7d113cd0d8df5ce1f687e6ec0219
merge: add automatic tag merge algorithm

Try to automatically merge conflicting .hgtags files using the following
algorithm:

- keep all tags that are identical on both parents (including their history)
- keep all the tags that are on only one of the merge parents

If there are any tags that are different in any way on both parents, the
automatic merge fails and we revert to the original merge behavior (which is to
do a regular .hgtags text merge).

This is a very simple algorithm, but it solves what is possibly the most common
tag merge conflict: the one that occurs when new, different tags are added on
each merge parent. Without this algorithm that scenario always results on an
.hgtags merge conflict which requires user intervention even though there is a
simple recipe to fix it (the one that this revision implements).

We could probably come up with ways to solve other less common merge conflicts
but those would get us a much smaller gain with an increased risk. We can
explore those in the future.

# Notes:
- The algorithm assumes that tags are never removed from the .hgtags file. This
should be true in most cases (particularly if the user does not normally modify
the .hgtags file on its own). We could improve this merge algorithm to handle
that case as well.
- All existing and new tests pass without modification.

On 03/17/2014 07:36 AM, Angel Ezquerra wrote:
> # HG changeset patch
> # User Angel Ezquerra <angel.ezquerra@gmail.com>
> # Date 1395006485 -3600
> #      Sun Mar 16 22:48:05 2014 +0100
> # Node ID ee742da53c1e43b33d84555662da9ed3ba938f6f
> # Parent  d2b518fe1a6c7d113cd0d8df5ce1f687e6ec0219
> merge: add automatic tag merge algorithm
>
> Try to automatically merge conflicting .hgtags files using the following
> algorithm:
>
> - keep all tags that are identical on both parents (including their history)
> - keep all the tags that are on only one of the merge parents
>
> If there are any tags that are different in any way on both parents, the
> automatic merge fails and we revert to the original merge behavior (which is to
> do a regular .hgtags text merge).
>
> This is a very simple algorithm, but it solves what is possibly the most common
> tag merge conflict: the one that occurs when new, different tags are added on
> each merge parent. Without this algorithm that scenario always results on an
> .hgtags merge conflict which requires user intervention even though there is a
> simple recipe to fix it (the one that this revision implements).
>
> We could probably come up with ways to solve other less common merge conflicts
> but those would get us a much smaller gain with an increased risk. We can
> explore those in the future.
>
> # Notes:
> - The algorithm assumes that tags are never removed from the .hgtags file. This
> should be true in most cases (particularly if the user does not normally modify
> the .hgtags file on its own). We could improve this merge algorithm to handle
> that case as well.
> - All existing and new tests pass without modification.

This is a custom merge tool for a specific file type. Shouldn't it be in 
filemerge like other merge patterns?

It hardcodes an algorithm for merging .hgtags. It might be good enough 
to use by default, but I think we should avoid making it mandatory. 
There might be cases where it not is what the user want (for instance if 
they have their own .hgtags merge tool). It should be possible to 
disable / overrule the use of this tool - perhaps by configuring a merge 
pattern for .hgtags.

The merge algorithm do not use the ancestor - and can thus not see if 
anything has been removed. It do not even detect when it is 
reintroducing removed tags - it will just silently merge it incorrectly. 
I think it should handle that correctly before it is enabled by default.

The merge process will sort the .hgtags entries by tag names when 
writing back. If the .hgtags not already thad the entries grouped by tag 
name (because the tag had been reused), it will rewrite the tag file 
completely. That will make other merges that not are using this merge 
tool much harder. I don't think it is ok it regroups the entries - 
especially not when it not is necessary. It would be significantly less 
intrusive if it started out by writing out all the (undeleted) lines 
from one of the ancestor and then appended the missing entries from the 
other parent.

/Mads



> diff --git a/mercurial/merge.py b/mercurial/merge.py
> --- a/mercurial/merge.py
> +++ b/mercurial/merge.py
> @@ -12,6 +12,7 @@
>   from mercurial import obsolete
>   import error, util, filemerge, copies, subrepo, worker, dicthelpers
>   import errno, os, shutil
> +import tags
>   
>   _pack = struct.pack
>   _unpack = struct.unpack
> @@ -686,7 +687,13 @@
>                   subrepo.submerge(repo, wctx, mctx, wctx.ancestor(mctx),
>                                    overwrite)
>                   continue
> -            audit(fd)
> +            elif fd == '.hgtags':  # tags need merging
> +                if not tags.tagmerge(repo, wctx, mctx):
> +                    merged += 1
> +                    ms.mark(fd, 'r')
> +                    continue
> +            else:
> +                audit(fd)
>               r = ms.resolve(fd, wctx)
>               if r is not None and r > 0:
>                   unresolved += 1
> diff --git a/mercurial/tags.py b/mercurial/tags.py
> --- a/mercurial/tags.py
> +++ b/mercurial/tags.py
> @@ -299,3 +299,47 @@
>           cachefile.close()
>       except (OSError, IOError):
>           pass
> +
> +def writetags(repo, tags, munge=None):
> +    fp = repo.wfile('.hgtags', 'wb')
> +    for name in tags:
> +        m = munge and munge(name) or name
> +        node, hist = tags[name]
> +        hist.append(node)
> +        for nd in hist:
> +            fp.write('%s %s\n' % (hex(nd), m))
> +    fp.close()
> +
> +def tagmerge(repo, p1ctx, p2ctx):
> +    '''Merge the tags of two revisions'''
> +    ui = repo.ui
> +    ui.note(_('merging .hgtags\n'))
> +    p1tags = _readtags(
> +        ui, repo, p1ctx['.hgtags'].data().splitlines(), "p1 tags")
> +    p2tags = _readtags(
> +        ui, repo, p2ctx['.hgtags'].data().splitlines(), "p2 tags")
> +
> +    conflictedtags = []
> +    mergedtags = p1tags.copy()
> +    # sortdict does not implement iteritems()
> +    for name, nodehist in p2tags.items():
> +        if name not in mergedtags:
> +            mergedtags[name] = nodehist
> +            continue
> +        # there is no conflict unless both tags point to different revisions
> +        # and have a non identical tag history
> +        p1node, p1hist = mergedtags[name]
> +        p2node, p2hist = nodehist
> +        if p1node != p2node or p1hist != p2hist:
> +            conflictedtags.append(name)
> +            continue
> +    if not conflictedtags:
> +        # Write the merged .hgtags file
> +        writetags(repo, mergedtags)
> +        ui.note(_('.hgtags merged successfully\n'))
> +        return None
> +    numconflicts = len(conflictedtags)
> +    ui.warn(_('automatic .hgtags merge failed\n'
> +            'the following %d tags are in conflict: %s\n')
> +            % (numconflicts, ', '.join(sorted(conflictedtags))))
> +    return numconflicts
> diff --git a/tests/test-tag.t b/tests/test-tag.t
> --- a/tests/test-tag.t
> +++ b/tests/test-tag.t
> @@ -323,3 +323,123 @@
>     adding file changes
>     added 2 changesets with 2 changes to 2 files
>   
> +  $ cd ..
> +
> +automatically merge simple tag conflicts
> +
> +  $ hg init repo-automatic-tag-merge
> +  $ cd repo-automatic-tag-merge
> +  $ echo c0 > f0
> +  $ hg ci -A -m0
> +  adding f0
> +  $ hg tag tbase
> +  $ echo c1 > f1
> +  $ hg ci -A -m1
> +  adding f1
> +  $ hg tag t1 t2 t3
> +  $ hg tag --remove t2
> +  $ echo c2 > f2
> +  $ hg ci -A -m2
> +  adding f2
> +  $ hg tag -f t3
> +  $ hg update -C -r 'children(tbase)'
> +  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
> +  $ echo c3 > f3
> +  $ hg ci -A -m3
> +  adding f3
> +  created new head
> +  $ hg tag -f t4 t5 t6
> +  $ hg tag --remove t5
> +  $ echo c4 > f4
> +  $ hg ci -A -m4
> +  adding f4
> +  $ hg tag -f t6
> +  $ hg merge
> +  2 files updated, 1 files merged, 0 files removed, 0 files unresolved
> +  (branch merge, don't forget to commit)
> +  $ hg status
> +  M .hgtags
> +  M f1
> +  M f2
> +  $ hg resolve -l
> +  R .hgtags
> +  $ cat .hgtags
> +  6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
> +  9aa4e1292a27a248f8d07339bed9931d54907be7 t4
> +  9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +  9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +  0000000000000000000000000000000000000000 t5
> +  9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +  9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +  929bca7b18d067cbf3844c3896319a940059d748 t6
> +  4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
> +  4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +  4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +  0000000000000000000000000000000000000000 t2
> +  4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +  4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +  edfec0022752ab491fc116d0e1f6e96c86f63041 t3
> +  $ hg diff --git -r 'p1()' .hgtags
> +  diff --git a/.hgtags b/.hgtags
> +  --- a/.hgtags
> +  +++ b/.hgtags
> +  @@ -1,8 +1,15 @@
> +   6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
> +   9aa4e1292a27a248f8d07339bed9931d54907be7 t4
> +   9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +  -9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +   9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +   0000000000000000000000000000000000000000 t5
> +   9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +   929bca7b18d067cbf3844c3896319a940059d748 t6
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +  +0000000000000000000000000000000000000000 t2
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +  +edfec0022752ab491fc116d0e1f6e96c86f63041 t3
> +  $ hg diff --git -r 'p2()' .hgtags
> +  diff --git a/.hgtags b/.hgtags
> +  --- a/.hgtags
> +  +++ b/.hgtags
> +  @@ -1,8 +1,15 @@
> +   6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t4
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t5
> +  +0000000000000000000000000000000000000000 t5
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +  +9aa4e1292a27a248f8d07339bed9931d54907be7 t6
> +  +929bca7b18d067cbf3844c3896319a940059d748 t6
> +   4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
> +   4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +  -4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +   4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
> +   0000000000000000000000000000000000000000 t2
> +   4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +  +4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
> +   edfec0022752ab491fc116d0e1f6e96c86f63041 t3
> +
> +detect merge tag conflicts
> +
> +  $ hg update -C -r tip
> +  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
> +  $ hg tag t7
> +  $ hg update -C 6
> +  3 files updated, 0 files merged, 2 files removed, 0 files unresolved
> +  $ hg tag -f t7
> +  $ hg merge
> +  automatic .hgtags merge failed
> +  the following 1 tags are in conflict: t7
> +  merging .hgtags
> +  warning: conflicts during merge.
> +  merging .hgtags incomplete! (edit conflicts, then use 'hg resolve --mark')
> +  2 files updated, 0 files merged, 0 files removed, 1 files unresolved
> +  use 'hg resolve' to retry unresolved file merges or 'hg update -C .' to abandon
> +  [1]
> +  $ hg resolve -l
> +  U .hgtags
> +
> +  $ cd ..
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel

On Mon, Mar 24, 2014 at 1:28 AM, Mads Kiilerich <mads@kiilerich.com> wrote:
> On 03/17/2014 07:36 AM, Angel Ezquerra wrote:
>>
>> # HG changeset patch
>> # User Angel Ezquerra <angel.ezquerra@gmail.com>
>> # Date 1395006485 -3600
>> #      Sun Mar 16 22:48:05 2014 +0100
>> # Node ID ee742da53c1e43b33d84555662da9ed3ba938f6f
>> # Parent  d2b518fe1a6c7d113cd0d8df5ce1f687e6ec0219
>> merge: add automatic tag merge algorithm
>>
>> Try to automatically merge conflicting .hgtags files using the following
>> algorithm:
>>
>> - keep all tags that are identical on both parents (including their
>> history)
>> - keep all the tags that are on only one of the merge parents
>>
>> If there are any tags that are different in any way on both parents, the
>> automatic merge fails and we revert to the original merge behavior (which
>> is to
>> do a regular .hgtags text merge).
>>
>> This is a very simple algorithm, but it solves what is possibly the most
>> common
>> tag merge conflict: the one that occurs when new, different tags are added
>> on
>> each merge parent. Without this algorithm that scenario always results on
>> an
>> .hgtags merge conflict which requires user intervention even though there
>> is a
>> simple recipe to fix it (the one that this revision implements).
>>
>> We could probably come up with ways to solve other less common merge
>> conflicts
>> but those would get us a much smaller gain with an increased risk. We can
>> explore those in the future.
>>
>> # Notes:
>> - The algorithm assumes that tags are never removed from the .hgtags file.
>> This
>> should be true in most cases (particularly if the user does not normally
>> modify
>> the .hgtags file on its own). We could improve this merge algorithm to
>> handle
>> that case as well.
>> - All existing and new tests pass without modification.
>
>
> This is a custom merge tool for a specific file type. Shouldn't it be in
> filemerge like other merge patterns?
>
> It hardcodes an algorithm for merging .hgtags. It might be good enough to
> use by default, but I think we should avoid making it mandatory. There might
> be cases where it not is what the user want (for instance if they have their
> own .hgtags merge tool). It should be possible to disable / overrule the use
> of this tool - perhaps by configuring a merge pattern for .hgtags.

When I first started writing this reply I was going to agree with you.
However, after thinking a bit about it I am not so sure anymore. Let
me explain my reasoning:

I think we should definitely be able to configure a _fallback_ tag
merge tool which is run when this merge algorithm fails to merge
(because of conflicts). However, if we guarantee that the default the
algorithm never does the wrong thing (i.e. that it only successfully
merges the .hgtags file when there are no conflicts and there is only
one valid way the merge should be done), shouldn't we always accept
that correct merge result?

Imagine that we turned this algorithm into an actual merge tool (lets
call it hgtagmerge, for example). This would have several drawbacks:

1. There would be no way to configure mercurial to use a fallback
merge tool for .hgtags. You could either use the default merge
algorithm or your own tool, but not both (unless I misunderstood the
way merge-patterns work). This means that if I wanted to use WinMerge
(for example) to resolve .hgtags conflicts (instead of the default
KDiff3 tool that TortoiseHg uses for most file types), I would not be
able to do so while still using the default merge algorithm.

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.

3. The user could choose to use the hgtagmerge to merge any filetype
of his choice. Does it ever make sense to use this merge algorithm
(which is quite specific to the .hgtags format) for any other sort of
file?

So IMHO the merging of .hgtags should be a bit special, always go
through this merge algorithm first, and only if that fails it should
try to execute the merge tool of your choice (the fallback tag merge
tool, usually the default text merge tool).

> The merge algorithm do not use the ancestor - and can thus not see if
> anything has been removed. It do not even detect when it is reintroducing
> removed tags - it will just silently merge it incorrectly. I think it should
> handle that correctly before it is enabled by default.

I agree (actually the commit message mentions this). As I said above
the algorithm should never do the wrong thing.

> The merge process will sort the .hgtags entries by tag names when writing
> back. If the .hgtags not already thad the entries grouped by tag name
> (because the tag had been reused), it will rewrite the tag file completely.
> That will make other merges that not are using this merge tool much harder.
> I don't think it is ok it regroups the entries - especially not when it not
> is necessary. It would be significantly less intrusive if it started out by
> writing out all the (undeleted) lines from one of the ancestor and then
> appended the missing entries from the other parent.

That is a good idea. Since the merge algorithm can only add new
entries to the .hgtags file I think we could do as you suggest. I'll
have a look and send an updated version that also handles the removal
of tags from the .hgtags file. As I said I'd rather not turn this into
a full blown merge tool unless you really think I should.

Thanks for the review and the thoughtful comments! Please let me know
what you think about my arguments against turning this into a full
blown hgtagmerge tool.

Angel

On 03/24/2014 12:33 PM, Angel Ezquerra wrote:
> I think we should definitely be able to configure a _fallback_ tag
> merge tool which is run when this merge algorithm fails to merge
> (because of conflicts). However, if we guarantee that the default the
> algorithm never does the wrong thing (i.e. that it only successfully
> merges the .hgtags file when there are no conflicts and there is only
> one valid way the merge should be done), shouldn't we always accept
> that correct merge result?

We can change Mercurial if it fixes bugs or are areas that previously 
were undefined or failed badly. Merging of .hgtags is something where we 
clearly have told users that they were on their own ... and users might 
have found their own way of doing it. Some users might rely on something 
that is clearly "incorrect". One example could be to ignore all .hgtags 
changes when merging to release branches and only accept tags done on 
the release branch. I think we have to be very careful when introducing 
automatic merging.

> Imagine that we turned this algorithm into an actual merge tool (lets
> call it hgtagmerge, for example). This would have several drawbacks:
>
> 1. There would be no way to configure mercurial to use a fallback
> merge tool for .hgtags. You could either use the default merge
> algorithm or your own tool, but not both (unless I misunderstood the
> way merge-patterns work). This means that if I wanted to use WinMerge
> (for example) to resolve .hgtags conflicts (instead of the default
> KDiff3 tool that TortoiseHg uses for most file types), I would not be
> able to do so while still using the default merge algorithm.

I don't understand this ... unless it is the same as the next:

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

> 3. The user could choose to use the hgtagmerge to merge any filetype
> of his choice. Does it ever make sense to use this merge algorithm
> (which is quite specific to the .hgtags format) for any other sort of
> file?

http://www.catb.org/jargon/html/D/Don-t-do-that-then-.html

I imagine it could be 'internal:hgtags'. It should perhaps be mentioned 
somewhere in the documentation but I don't think it would have to be 
shown in the merge-tools help topic.

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

/Mads

On Mon, Mar 24, 2014 at 1:52 PM, Mads Kiilerich <mads@kiilerich.com> wrote:
> On 03/24/2014 12:33 PM, Angel Ezquerra wrote:
>>
>> I think we should definitely be able to configure a _fallback_ tag
>> merge tool which is run when this merge algorithm fails to merge
>> (because of conflicts). However, if we guarantee that the default the
>> algorithm never does the wrong thing (i.e. that it only successfully
>> merges the .hgtags file when there are no conflicts and there is only
>> one valid way the merge should be done), shouldn't we always accept
>> that correct merge result?
>
>
> We can change Mercurial if it fixes bugs or are areas that previously were
> undefined or failed badly. Merging of .hgtags is something where we clearly
> have told users that they were on their own ... and users might have found
> their own way of doing it. Some users might rely on something that is
> clearly "incorrect". One example could be to ignore all .hgtags changes when
> merging to release branches and only accept tags done on the release branch.
> I think we have to be very careful when introducing automatic merging.

OK, that is a good point.

>> Imagine that we turned this algorithm into an actual merge tool (lets
>> call it hgtagmerge, for example). This would have several drawbacks:
>>
>> 1. There would be no way to configure mercurial to use a fallback
>> merge tool for .hgtags. You could either use the default merge
>> algorithm or your own tool, but not both (unless I misunderstood the
>> way merge-patterns work). This means that if I wanted to use WinMerge
>> (for example) to resolve .hgtags conflicts (instead of the default
>> KDiff3 tool that TortoiseHg uses for most file types), I would not be
>> able to do so while still using the default merge algorithm.
>
>
> I don't understand this ... unless it is the same as the next:

I guess they are two sides of the same problem.

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

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.

I think this would give us the both of both worlds. We would let users
completely override the default merge algorithm, and it would let most
users get automated merges with their desired fallback tool.

What do you think?

>> 3. The user could choose to use the hgtagmerge to merge any filetype
>> of his choice. Does it ever make sense to use this merge algorithm
>> (which is quite specific to the .hgtags format) for any other sort of
>> file?
>
>
> http://www.catb.org/jargon/html/D/Don-t-do-that-then-.html
>
> I imagine it could be 'internal:hgtags'. It should perhaps be mentioned
> somewhere in the documentation but I don't think it would have to be shown
> in the merge-tools help topic.

OK.

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

Cheers,

Angel

On 03/24/2014 02:29 PM, Angel Ezquerra wrote:
> On Mon, Mar 24, 2014 at 1:52 PM, Mads Kiilerich <mads@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 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).

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

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

/Mads

On Mon, Mar 24, 2014 at 4:42 PM, Mads Kiilerich <mads@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@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

On 03/24/2014 07:31 PM, Angel Ezquerra wrote:
>
> > 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.
>

I think a simpler first step would be fine - as long as it not is 
enabled by default.

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

Yes, that is an important point. I have argued that we should be aware 
of these ranks and preserve them ... but I think the correct way to 
actually merge the tags primarily should consider the two parents + 
ancestor. Once the merge result had been decided it should try to 
preserve/create a "correct" rank for it.

"Rank" might by definition be good enough for consistently and 
efficiently "resolving" conflicts when "merging" .hgtags on runtime ... 
but I am not sure it necessarily also is the right way to resolve "real" 
merges.

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

Perhaps - that would be clever if it worked. The algorithm is by 
definition right for runtime merging, but I doubt it will merge 
"correctly" for real merges. And I assume it will fail to remove removed 
tags? That could perhaps be retro fitted somehow.

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

I don't know. But it sounds like this project will end up clarifying and 
extending on TagDesign. You could perhaps improve that page and start a 
TagMergeDesign page and summarize the thoughts you have done and the 
questions that has popped up.

/Mads

On Mon, 2014-03-24 at 19:31 +0100, Angel Ezquerra wrote:
> On Mon, Mar 24, 2014 at 4:42 PM, Mads Kiilerich <mads@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@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".

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

On Wed, Mar 26, 2014 at 7:46 PM, Matt Mackall <mpm@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@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@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

On Fri, Mar 28, 2014 at 11:12 PM, Angel Ezquerra <ezquerra@gmail.com> wrote:
> On Wed, Mar 26, 2014 at 7:46 PM, Matt Mackall <mpm@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@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@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".

Matt, sorry for coming back on this, but after thinking about your
suggestion a bit more I am not sure I understand it.
Which of the following are you suggesting?

1. Interleave the rank items, taking one from each head
alternativelly, (i.e. one from one head, then the next one from the
other head, and so on)
2. Put all the rank items (from both heads) on a single list, and
reorder them according to their distance from tip?

I am not sure #2 would be the right thing to do. For example, if  the
user ever moved a tag backwards we would now be reordering the tags
involved in that backwards move.

#1 seems better, but I think that interleaving the rank items (whether
it is using #1 or #2) would make it unnecessarily harder for users to
do a manual tag merge with the result of this merge later (for example
if they were using an older mercurial version).

Instead I think it would be better to do, for each conflicting tag:
1. Place the rank entries common to both heads first
2. Place the remaining rank entries of the lowest rank head
3. Place the remaining rank entries of the highest rank head

I think this would be simpler to implement, would avoid the tag
reordering issues and make interop with older mercurial versions
easier.

In the end I don't think this is a big deal, because we do not really
use the content of the rank history, just the rank itself, and as you
said people who end up in this scenario are already doing something
very wrong. That is why I'd rather go for the simpler solution that I
suggest or for #1 if you think that is better.

Cheers,

Angel

On Sun, 2014-03-30 at 15:14 +0200, Angel Ezquerra wrote:
> On Fri, Mar 28, 2014 at 11:12 PM, Angel Ezquerra <ezquerra@gmail.com> wrote:
> > On Wed, Mar 26, 2014 at 7:46 PM, Matt Mackall <mpm@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@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@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".
> 
> Matt, sorry for coming back on this, but after thinking about your
> suggestion a bit more I am not sure I understand it.
> Which of the following are you suggesting?
> 
> 1. Interleave the rank items, taking one from each head
> alternativelly, (i.e. one from one head, then the next one from the
> other head, and so on)
> 2. Put all the rank items (from both heads) on a single list, and
> reorder them according to their distance from tip?
> 
> I am not sure #2 would be the right thing to do. For example, if  the
> user ever moved a tag backwards we would now be reordering the tags
> involved in that backwards move.

#1.

My algorithm would be basically:

a = [...] # branch closer to tip
b = [...]
c = []

while a and b:
   c.append(a.pop(0))
   if c[-1] == b[0]:
       b.pop(0)
   else:
       c.append(b.pop(0))