Mercurial > hg-stable

--- a/mercurial/filemerge.py	Fri Jul 18 21:49:52 2014 -0500
+++ b/mercurial/filemerge.py	Thu Jun 26 01:20:25 2014 +0200
@@ -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 (experimental).
+    """
+    return tagmerge.merge(repo, fcd, fco, fca)
+
 @internaltool('dump', True)
 def _idump(repo, mynode, orig, fcd, fco, fca, toolconf, files, labels=None):
     """
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/tagmerge.py	Thu Jun 26 01:20:25 2014 +0200
@@ -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
+
--- a/tests/test-tag.t	Fri Jul 18 21:49:52 2014 -0500
+++ b/tests/test-tag.t	Thu Jun 26 01:20:25 2014 +0200
@@ -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
+