@@ -9,6 +9,7 @@
from i18n import _
import util, simplemerge, match, error, templater, templatekw
import os, tempfile, re, filecmp
+import tagmerge
def _toolstr(ui, tool, part, default=""):
return ui.config("merge-tools", tool + "." + part, default)
@@ -221,6 +222,16 @@
return True, r
return False, 0
+@internaltool('tagmerge', True,
+ _("automatic tag merging of %s failed! "
+ "(use 'hg resolve --tool internal:merge' or another merge "
+ "tool of your choice)\n"))
+def _itagmerge(repo, mynode, orig, fcd, fco, fca, toolconf, files, labels=None):
+ """
+ Uses the internal tag merge algorithm.
+ """
+ return tagmerge.merge(repo, fcd, fco, fca)
+
@internaltool('dump', True)
def _idump(repo, mynode, orig, fcd, fco, fca, toolconf, files, labels=None):
"""
@@ -0,0 +1,265 @@
+# tagmerge.py - merge .hgtags files
+#
+# Copyright 2014 Angel Ezquerra <angel.ezquerra@gmail.com>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+# This module implements an automatic merge algorithm for mercurial's tag files
+#
+# The tagmerge algorithm implemented in this module is able to resolve most
+# merge conflicts that currently would trigger a .hgtags merge conflict. The
+# only case that it does not (and cannot) handle is that in which two tags point
+# to different revisions on each merge parent _and_ their corresponding tag
+# histories have the same rank (i.e. the same length). In all other cases the
+# merge algorithm will choose the revision belonging to the parent with the
+# highest ranked tag history. The merged tag history is the combination of both
+# tag histories (special care is taken to try to combine common tag histories
+# where possible).
+#
+# In addition to actually merging the tags from two parents, taking into
+# account the base, the algorithm also tries to minimize the difference
+# between the merged tag file and the first parent's tag file (i.e. it tries to
+# make the merged tag order as as similar as possible to the first parent's tag
+# file order).
+#
+# The algorithm works as follows:
+# 1. read the tags from p1, p2 and the base
+# - when reading the p1 tags, also get the line numbers associated to each
+# tag node (these will be used to sort the merged tags in a way that
+# minimizes the diff to p1). Ignore the file numbers when reading p2 and
+# the base
+# 2. recover the "lost tags" (i.e. those that are found in the base but not on
+# p1 or p2) and add them back to p1 and/or p2
+# - at this point the only tags that are on p1 but not on p2 are those new
+# tags that were introduced in p1. Same thing for the tags that are on p2
+# but not on p2
+# 3. take all tags that are only on p1 or only on p2 (but not on the base)
+# - Note that these are the tags that were introduced between base and p1
+# and between base and p2, possibly on separate clones
+# 4. for each tag found both on p1 and p2 perform the following merge algorithm:
+# - the tags conflict if their tag "histories" have the same "rank" (i.e.
+# length) _AND_ the last (current) tag is _NOT_ the same
+# - for non conflicting tags:
+# - choose which are the high and the low ranking nodes
+# - the high ranking list of nodes is the one that is longer.
+# In case of draw favor p1
+# - the merged node list is made of 3 parts:
+# - first the nodes that are common to the beginning of both
+# the low and the high ranking nodes
+# - second the non common low ranking nodes
+# - finally the non common high ranking nodes (with the last
+# one being the merged tag node)
+# - note that this is equivalent to putting the whole low ranking
+# node list first, followed by the non common high ranking nodes
+# - note that during the merge we keep the "node line numbers", which will
+# be used when writing the merged tags to the tag file
+# 5. write the merged tags taking into account to their positions in the first
+# parent (i.e. try to keep the relative ordering of the nodes that come
+# from p1). This minimizes the diff between the merged and the p1 tag files
+# This is donw by using the following algorithm
+# - group the nodes for a given tag that must be written next to each other
+# - A: nodes that come from consecutive lines on p1
+# - B: nodes that come from p2 (i.e. whose associated line number is
+# None) and are next to one of the a nodes in A
+# - each group is associated with a line number coming from p1
+# - generate a "tag block" for each of the groups
+# - a tag block is a set of consecutive "node tag" lines belonging to
+# the same tag and which will be written next to each other on the
+# merged tags file
+# - sort the "tag blocks" according to their associated number line
+# - put blocks whose nodes come all from p2 first
+# - write the tag blocks in the sorted order
+
+import tags
+import util
+from node import nullid, hex
+from i18n import _
+import operator
+hexnullid = hex(nullid)
+
+def readtagsformerge(ui, repo, lines, fn='', keeplinenums=False):
+ '''read the .hgtags file into a structure that is suitable for merging
+
+ Sepending on the keeplinenumbers flag, clear the line numbers associated
+ with each tag. Rhis is done because only the line numbers of the first
+ parent are useful for merging
+ '''
+ filetags = tags._readtaghist(ui, repo, lines, fn=fn, recode=None,
+ calcnodelines=True)[1]
+ for tagname, taginfo in filetags.items():
+ if not keeplinenums:
+ for el in taginfo:
+ el[1] = None
+ return filetags
+
+def grouptagnodesbyline(tagnodes):
+ '''
+ Group nearby nodes (i.e. those that must be written next to each other)
+
+ The input is a list of [node, position] pairs, corresponding to a given tag
+ The position is the line number where the node was found on the first parent
+ .hgtags file, or None for those nodes that came from the base or the second
+ parent .hgtags files.
+
+ This function groups those [node, position] pairs, returning a list of
+ groups of nodes that must be written next to each other because their
+ positions are consecutive or have no position preference (because their
+ position is None).
+
+ The result is a list of [position, [consecutive node list]]
+ '''
+ firstlinenum = None
+ for hexnode, linenum in tagnodes:
+ firstlinenum = linenum
+ if firstlinenum is not None:
+ break
+ if firstlinenum is None:
+ return [[None, [el[0] for el in tagnodes]]]
+ tagnodes[0][1] = firstlinenum
+ groupednodes = [[firstlinenum, []]]
+ prevlinenum = firstlinenum
+ for hexnode, linenum in tagnodes:
+ if linenum is not None and linenum - prevlinenum > 1:
+ groupednodes.append([linenum, []])
+ groupednodes[-1][1].append(hexnode)
+ if linenum is not None:
+ prevlinenum = linenum
+ return groupednodes
+
+def writemergedtags(repo, mergedtags):
+ '''
+ write the merged tags while trying to minimize the diff to the first parent
+
+ This function uses the ordering info stored on the merged tags dict to
+ generate an .hgtags file which is correct (in the sense that its contents
+ correspond to the result of the tag merge) while also being as close as
+ possible to the first parent's .hgtags file.
+ '''
+ # group the node-tag pairs that must be written next to each other
+ for tname, taglist in mergedtags.items():
+ mergedtags[tname] = grouptagnodesbyline(taglist)
+
+ # convert the grouped merged tags dict into a format that resembles the
+ # final .hgtags file (i.e. a list of blocks of 'node tag' pairs)
+ def taglist2string(tlist, tname):
+ return '\n'.join(['%s %s' % (hexnode, tname) for hexnode in tlist])
+
+ finaltags = []
+ for tname, tags in mergedtags.items():
+ for block in tags:
+ block[1] = taglist2string(block[1], tname)
+ finaltags += tags
+
+ # the tag groups are linked to a "position" that can be used to sort them
+ # before writing them
+ # the position is calculated to ensure that the diff of the merged .hgtags
+ # file to the first parent's .hgtags file is as small as possible
+ finaltags.sort(key=operator.itemgetter(0))
+
+ # finally we can join the sorted groups to get the final contents of the
+ # merged .hgtags file, and then write it to disk
+ mergedtagstring = '\n'.join([tags for rank, tags in finaltags if tags])
+ fp = repo.wfile('.hgtags', 'wb')
+ fp.write(mergedtagstring + '\n')
+ fp.close()
+
+def singletagmerge(p1nodes, p2nodes):
+ '''
+ merge the nodes corresponding to a single tag
+
+ Note that the inputs are lists of node-linenum pairs (i.e. not just lists
+ of nodes)
+ '''
+ if not p2nodes:
+ return p1nodes
+ if not p1nodes:
+ return p2nodes
+
+ # there is no conflict unless both tags point to different revisions
+ # and have a non identical tag history
+ p1currentnode = p1nodes[-1][0]
+ p2currentnode = p2nodes[-1][0]
+ if p1currentnode != p2currentnode and len(p1nodes) == len(p2nodes):
+ # cannot merge two tags with same rank pointing to different nodes
+ return None
+
+ # which are the highest ranking (hr) / lowest ranking (lr) nodes?
+ if len(p1nodes) >= len(p2nodes):
+ hrnodes, lrnodes = p1nodes, p2nodes
+ else:
+ hrnodes, lrnodes = p2nodes, p1nodes
+
+ # the lowest ranking nodes will be written first, followed by the highest
+ # ranking nodes
+ # to avoid unwanted tag rank explosion we try to see if there are some
+ # common nodes that can be written only once
+ commonidx = len(lrnodes)
+ for n in range(len(lrnodes)):
+ if hrnodes[n][0] != lrnodes[n][0]:
+ commonidx = n
+ break
+ lrnodes[n][1] = p1nodes[n][1]
+
+ # the merged node list has 3 parts:
+ # - common nodes
+ # - non common lowest ranking nodes
+ # - non common highest ranking nodes
+ # note that the common nodes plus the non common lowest ranking nodes is the
+ # whole list of lr nodes
+ return lrnodes + hrnodes[commonidx:]
+
+def merge(repo, fcd, fco, fca):
+ '''
+ Merge the tags of two revisions, taking into account the base tags
+ Try to minimize the diff between the merged tags and the first parent tags
+ '''
+ ui = repo.ui
+ # read the p1, p2 and base tags
+ # only keep the line numbers for the p1 tags
+ p1tags = readtagsformerge(
+ ui, repo, fcd.data().splitlines(), fn="p1 tags",
+ keeplinenums=True)
+ p2tags = readtagsformerge(
+ ui, repo, fco.data().splitlines(), fn="p2 tags",
+ keeplinenums=False)
+ basetags = readtagsformerge(
+ ui, repo, fca.data().splitlines(), fn="base tags",
+ keeplinenums=False)
+
+ # recover the list of "lost tags" (i.e. those that were found on the base
+ # revision but not on one of the revisions being merged)
+ basetagset = set(basetags)
+ for n, pntags in enumerate((p1tags, p2tags)):
+ pntagset = set(pntags)
+ pnlosttagset = basetagset - pntagset
+ for t in pnlosttagset:
+ pntags[t] = basetags[t]
+ if pntags[t][-1][0] != hexnullid:
+ pntags[t].append([hexnullid, None])
+
+ conflictedtags = [] # for reporting purposes
+ mergedtags = util.sortdict(p1tags)
+ # sortdict does not implement iteritems()
+ for tname, p2nodes in p2tags.items():
+ if tname not in mergedtags:
+ mergedtags[tname] = p2nodes
+ continue
+ p1nodes = mergedtags[tname]
+ mergednodes = singletagmerge(p1nodes, p2nodes)
+ if mergednodes is None:
+ conflictedtags.append(tname)
+ continue
+ mergedtags[tname] = mergednodes
+
+ if conflictedtags:
+ numconflicts = len(conflictedtags)
+ ui.warn(_('automatic .hgtags merge failed\n'
+ 'the following %d tags are in conflict: %s\n')
+ % (numconflicts, ', '.join(sorted(conflictedtags))))
+ return True, 1
+
+ writemergedtags(repo, mergedtags)
+ ui.note(_('.hgtags merged successfully\n'))
+ return False, 0
+
@@ -403,3 +403,204 @@
adding file changes
added 2 changesets with 2 changes to 2 files
+automatically merge resolvable tag conflicts (i.e. tags that differ in rank)
+create two clones with some different tags as well as some common tags
+check that we can merge tags that differ in rank
+
+ $ hg init repo-automatic-tag-merge
+ $ cd repo-automatic-tag-merge
+ $ echo c0 > f0
+ $ hg ci -A -m0
+ adding f0
+ $ hg tag tbase
+ $ cd ..
+ $ hg clone repo-automatic-tag-merge repo-automatic-tag-merge-clone
+ updating to branch default
+ 2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+ $ cd repo-automatic-tag-merge-clone
+ $ echo c1 > f1
+ $ hg ci -A -m1
+ adding f1
+ $ hg tag t1 t2 t3
+ $ hg tag --remove t2
+ $ hg tag t5
+ $ echo c2 > f2
+ $ hg ci -A -m2
+ adding f2
+ $ hg tag -f t3
+
+ $ cd ../repo-automatic-tag-merge
+ $ echo c3 > f3
+ $ hg ci -A -m3
+ adding f3
+ $ hg tag -f t4 t5 t6
+ $ hg tag --remove t5
+ $ echo c4 > f4
+ $ hg ci -A -m4
+ adding f4
+ $ hg tag t2
+ $ hg tag -f t6
+
+ $ cd ../repo-automatic-tag-merge-clone
+ $ hg pull
+ pulling from $TESTTMP/repo-automatic-tag-merge (glob)
+ searching for changes
+ adding changesets
+ adding manifests
+ adding file changes
+ added 6 changesets with 6 changes to 3 files (+1 heads)
+ (run 'hg heads' to see heads, 'hg merge' to merge)
+ $ hg merge --tool internal:tagmerge
+ merging .hgtags
+ 2 files updated, 1 files merged, 0 files removed, 0 files unresolved
+ (branch merge, don't forget to commit)
+ $ hg status
+ M .hgtags
+ M f3
+ M f4
+ $ hg resolve -l
+ R .hgtags
+ $ cat .hgtags
+ 9aa4e1292a27a248f8d07339bed9931d54907be7 t4
+ 9aa4e1292a27a248f8d07339bed9931d54907be7 t6
+ 9aa4e1292a27a248f8d07339bed9931d54907be7 t6
+ 09af2ce14077a94effef208b49a718f4836d4338 t6
+ 6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
+ 929bca7b18d067cbf3844c3896319a940059d748 t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 0000000000000000000000000000000000000000 t2
+ 875517b4806a848f942811a315a5bce30804ae85 t5
+ 9aa4e1292a27a248f8d07339bed9931d54907be7 t5
+ 9aa4e1292a27a248f8d07339bed9931d54907be7 t5
+ 0000000000000000000000000000000000000000 t5
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 79505d5360b07e3e79d1052e347e73c02b8afa5b t3
+
+check that the merge tried to minimize the diff witht he first merge parent
+
+ $ hg diff --git -r 'p1()' .hgtags
+ diff --git a/.hgtags b/.hgtags
+ --- a/.hgtags
+ +++ b/.hgtags
+ @@ -1,9 +1,17 @@
+ +9aa4e1292a27a248f8d07339bed9931d54907be7 t4
+ +9aa4e1292a27a248f8d07339bed9931d54907be7 t6
+ +9aa4e1292a27a248f8d07339bed9931d54907be7 t6
+ +09af2ce14077a94effef208b49a718f4836d4338 t6
+ 6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
+ +929bca7b18d067cbf3844c3896319a940059d748 t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 0000000000000000000000000000000000000000 t2
+ 875517b4806a848f942811a315a5bce30804ae85 t5
+ +9aa4e1292a27a248f8d07339bed9931d54907be7 t5
+ +9aa4e1292a27a248f8d07339bed9931d54907be7 t5
+ +0000000000000000000000000000000000000000 t5
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 79505d5360b07e3e79d1052e347e73c02b8afa5b t3
+
+detect merge tag conflicts
+
+ $ hg update -C -r tip
+ 3 files updated, 0 files merged, 2 files removed, 0 files unresolved
+ $ hg tag t7
+ $ hg update -C -r 'first(sort(head()))'
+ 3 files updated, 0 files merged, 2 files removed, 0 files unresolved
+ $ printf "%s %s\n" `hg log -r . --template "{node} t7"` >> .hgtags
+ $ hg commit -m "manually add conflicting t7 tag"
+ $ hg merge --tool internal:tagmerge
+ merging .hgtags
+ automatic .hgtags merge failed
+ the following 1 tags are in conflict: t7
+ automatic tag merging of .hgtags failed! (use 'hg resolve --tool internal:merge' or another merge tool of your choice)
+ 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
+ $ cat .hgtags
+ 6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 0000000000000000000000000000000000000000 t2
+ 875517b4806a848f942811a315a5bce30804ae85 t5
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 79505d5360b07e3e79d1052e347e73c02b8afa5b t3
+ ea918d56be86a4afc5a95312e8b6750e1428d9d2 t7
+
+ $ cd ..
+
+handle the loss of tags
+
+ $ hg clone repo-automatic-tag-merge-clone repo-merge-lost-tags
+ updating to branch default
+ 4 files updated, 0 files merged, 0 files removed, 0 files unresolved
+ $ cd repo-merge-lost-tags
+ $ echo c5 > f5
+ $ hg ci -A -m5
+ adding f5
+ $ hg tag -f t7
+ $ hg update -r 'p1(t7)'
+ 1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+ $ printf '' > .hgtags
+ $ hg commit -m 'delete all tags'
+ created new head
+ $ hg update -r 'max(t7::)'
+ 2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+ $ hg merge -r tip --tool internal:tagmerge
+ merging .hgtags
+ 0 files updated, 1 files merged, 0 files removed, 0 files unresolved
+ (branch merge, don't forget to commit)
+ $ hg resolve -l
+ R .hgtags
+ $ cat .hgtags
+ 6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
+ 0000000000000000000000000000000000000000 tbase
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
+ 0000000000000000000000000000000000000000 t1
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 0000000000000000000000000000000000000000 t2
+ 875517b4806a848f942811a315a5bce30804ae85 t5
+ 0000000000000000000000000000000000000000 t5
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 79505d5360b07e3e79d1052e347e73c02b8afa5b t3
+ 0000000000000000000000000000000000000000 t3
+ ea918d56be86a4afc5a95312e8b6750e1428d9d2 t7
+ 0000000000000000000000000000000000000000 t7
+ ea918d56be86a4afc5a95312e8b6750e1428d9d2 t7
+ fd3a9e394ce3afb354a496323bf68ac1755a30de t7
+
+also check that we minimize the diff with the 1st merge parent
+
+ $ hg diff --git -r 'p1()' .hgtags
+ diff --git a/.hgtags b/.hgtags
+ --- a/.hgtags
+ +++ b/.hgtags
+ @@ -1,12 +1,17 @@
+ 6cee5c8f3e5b4ae1a3996d2f6489c3e08eb5aea7 tbase
+ +0000000000000000000000000000000000000000 tbase
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t1
+ +0000000000000000000000000000000000000000 t1
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t2
+ 0000000000000000000000000000000000000000 t2
+ 875517b4806a848f942811a315a5bce30804ae85 t5
+ +0000000000000000000000000000000000000000 t5
+ 4f3e9b90005b68b4d8a3f4355cedc302a8364f5c t3
+ 79505d5360b07e3e79d1052e347e73c02b8afa5b t3
+ +0000000000000000000000000000000000000000 t3
+ ea918d56be86a4afc5a95312e8b6750e1428d9d2 t7
+ +0000000000000000000000000000000000000000 t7
+ ea918d56be86a4afc5a95312e8b6750e1428d9d2 t7
+ fd3a9e394ce3afb354a496323bf68ac1755a30de t7
+