##// END OF EJS Templates
tagmerge: use 'wvfs' instead of 'wfile'...
Pierre-Yves David -
r31415:5d92107d default
parent child Browse files
Show More
@@ -1,274 +1,274
1 1 # tagmerge.py - merge .hgtags files
2 2 #
3 3 # Copyright 2014 Angel Ezquerra <angel.ezquerra@gmail.com>
4 4 #
5 5 # This software may be used and distributed according to the terms of the
6 6 # GNU General Public License version 2 or any later version.
7 7
8 8 # This module implements an automatic merge algorithm for mercurial's tag files
9 9 #
10 10 # The tagmerge algorithm implemented in this module is able to resolve most
11 11 # merge conflicts that currently would trigger a .hgtags merge conflict. The
12 12 # only case that it does not (and cannot) handle is that in which two tags point
13 13 # to different revisions on each merge parent _and_ their corresponding tag
14 14 # histories have the same rank (i.e. the same length). In all other cases the
15 15 # merge algorithm will choose the revision belonging to the parent with the
16 16 # highest ranked tag history. The merged tag history is the combination of both
17 17 # tag histories (special care is taken to try to combine common tag histories
18 18 # where possible).
19 19 #
20 20 # In addition to actually merging the tags from two parents, taking into
21 21 # account the base, the algorithm also tries to minimize the difference
22 22 # between the merged tag file and the first parent's tag file (i.e. it tries to
23 23 # make the merged tag order as as similar as possible to the first parent's tag
24 24 # file order).
25 25 #
26 26 # The algorithm works as follows:
27 27 # 1. read the tags from p1, p2 and the base
28 28 # - when reading the p1 tags, also get the line numbers associated to each
29 29 # tag node (these will be used to sort the merged tags in a way that
30 30 # minimizes the diff to p1). Ignore the file numbers when reading p2 and
31 31 # the base
32 32 # 2. recover the "lost tags" (i.e. those that are found in the base but not on
33 33 # p1 or p2) and add them back to p1 and/or p2
34 34 # - at this point the only tags that are on p1 but not on p2 are those new
35 35 # tags that were introduced in p1. Same thing for the tags that are on p2
36 36 # but not on p2
37 37 # 3. take all tags that are only on p1 or only on p2 (but not on the base)
38 38 # - Note that these are the tags that were introduced between base and p1
39 39 # and between base and p2, possibly on separate clones
40 40 # 4. for each tag found both on p1 and p2 perform the following merge algorithm:
41 41 # - the tags conflict if their tag "histories" have the same "rank" (i.e.
42 42 # length) AND the last (current) tag is NOT the same
43 43 # - for non conflicting tags:
44 44 # - choose which are the high and the low ranking nodes
45 45 # - the high ranking list of nodes is the one that is longer.
46 46 # In case of draw favor p1
47 47 # - the merged node list is made of 3 parts:
48 48 # - first the nodes that are common to the beginning of both
49 49 # the low and the high ranking nodes
50 50 # - second the non common low ranking nodes
51 51 # - finally the non common high ranking nodes (with the last
52 52 # one being the merged tag node)
53 53 # - note that this is equivalent to putting the whole low ranking
54 54 # node list first, followed by the non common high ranking nodes
55 55 # - note that during the merge we keep the "node line numbers", which will
56 56 # be used when writing the merged tags to the tag file
57 57 # 5. write the merged tags taking into account to their positions in the first
58 58 # parent (i.e. try to keep the relative ordering of the nodes that come
59 59 # from p1). This minimizes the diff between the merged and the p1 tag files
60 60 # This is done by using the following algorithm
61 61 # - group the nodes for a given tag that must be written next to each other
62 62 # - A: nodes that come from consecutive lines on p1
63 63 # - B: nodes that come from p2 (i.e. whose associated line number is
64 64 # None) and are next to one of the a nodes in A
65 65 # - each group is associated with a line number coming from p1
66 66 # - generate a "tag block" for each of the groups
67 67 # - a tag block is a set of consecutive "node tag" lines belonging to
68 68 # the same tag and which will be written next to each other on the
69 69 # merged tags file
70 70 # - sort the "tag blocks" according to their associated number line
71 71 # - put blocks whose nodes come all from p2 first
72 72 # - write the tag blocks in the sorted order
73 73
74 74 from __future__ import absolute_import
75 75
76 76 import operator
77 77
78 78 from .i18n import _
79 79 from .node import (
80 80 hex,
81 81 nullid,
82 82 )
83 83 from .import (
84 84 tags as tagsmod,
85 85 util,
86 86 )
87 87
88 88 hexnullid = hex(nullid)
89 89
90 90 def readtagsformerge(ui, repo, lines, fn='', keeplinenums=False):
91 91 '''read the .hgtags file into a structure that is suitable for merging
92 92
93 93 Depending on the keeplinenums flag, clear the line numbers associated
94 94 with each tag. This is done because only the line numbers of the first
95 95 parent are useful for merging.
96 96 '''
97 97 filetags = tagsmod._readtaghist(ui, repo, lines, fn=fn, recode=None,
98 98 calcnodelines=True)[1]
99 99 for tagname, taginfo in filetags.items():
100 100 if not keeplinenums:
101 101 for el in taginfo:
102 102 el[1] = None
103 103 return filetags
104 104
105 105 def grouptagnodesbyline(tagnodes):
106 106 '''
107 107 Group nearby nodes (i.e. those that must be written next to each other)
108 108
109 109 The input is a list of [node, position] pairs, corresponding to a given tag
110 110 The position is the line number where the node was found on the first parent
111 111 .hgtags file, or None for those nodes that came from the base or the second
112 112 parent .hgtags files.
113 113
114 114 This function groups those [node, position] pairs, returning a list of
115 115 groups of nodes that must be written next to each other because their
116 116 positions are consecutive or have no position preference (because their
117 117 position is None).
118 118
119 119 The result is a list of [position, [consecutive node list]]
120 120 '''
121 121 firstlinenum = None
122 122 for hexnode, linenum in tagnodes:
123 123 firstlinenum = linenum
124 124 if firstlinenum is not None:
125 125 break
126 126 if firstlinenum is None:
127 127 return [[None, [el[0] for el in tagnodes]]]
128 128 tagnodes[0][1] = firstlinenum
129 129 groupednodes = [[firstlinenum, []]]
130 130 prevlinenum = firstlinenum
131 131 for hexnode, linenum in tagnodes:
132 132 if linenum is not None and linenum - prevlinenum > 1:
133 133 groupednodes.append([linenum, []])
134 134 groupednodes[-1][1].append(hexnode)
135 135 if linenum is not None:
136 136 prevlinenum = linenum
137 137 return groupednodes
138 138
139 139 def writemergedtags(repo, mergedtags):
140 140 '''
141 141 write the merged tags while trying to minimize the diff to the first parent
142 142
143 143 This function uses the ordering info stored on the merged tags dict to
144 144 generate an .hgtags file which is correct (in the sense that its contents
145 145 correspond to the result of the tag merge) while also being as close as
146 146 possible to the first parent's .hgtags file.
147 147 '''
148 148 # group the node-tag pairs that must be written next to each other
149 149 for tname, taglist in mergedtags.items():
150 150 mergedtags[tname] = grouptagnodesbyline(taglist)
151 151
152 152 # convert the grouped merged tags dict into a format that resembles the
153 153 # final .hgtags file (i.e. a list of blocks of 'node tag' pairs)
154 154 def taglist2string(tlist, tname):
155 155 return '\n'.join(['%s %s' % (hexnode, tname) for hexnode in tlist])
156 156
157 157 finaltags = []
158 158 for tname, tags in mergedtags.items():
159 159 for block in tags:
160 160 block[1] = taglist2string(block[1], tname)
161 161 finaltags += tags
162 162
163 163 # the tag groups are linked to a "position" that can be used to sort them
164 164 # before writing them
165 165 # the position is calculated to ensure that the diff of the merged .hgtags
166 166 # file to the first parent's .hgtags file is as small as possible
167 167 finaltags.sort(key=operator.itemgetter(0))
168 168
169 169 # finally we can join the sorted groups to get the final contents of the
170 170 # merged .hgtags file, and then write it to disk
171 171 mergedtagstring = '\n'.join([tags for rank, tags in finaltags if tags])
172 fp = repo.wfile('.hgtags', 'wb')
172 fp = repo.wvfs('.hgtags', 'wb')
173 173 fp.write(mergedtagstring + '\n')
174 174 fp.close()
175 175
176 176 def singletagmerge(p1nodes, p2nodes):
177 177 '''
178 178 merge the nodes corresponding to a single tag
179 179
180 180 Note that the inputs are lists of node-linenum pairs (i.e. not just lists
181 181 of nodes)
182 182 '''
183 183 if not p2nodes:
184 184 return p1nodes
185 185 if not p1nodes:
186 186 return p2nodes
187 187
188 188 # there is no conflict unless both tags point to different revisions
189 189 # and have a non identical tag history
190 190 p1currentnode = p1nodes[-1][0]
191 191 p2currentnode = p2nodes[-1][0]
192 192 if p1currentnode != p2currentnode and len(p1nodes) == len(p2nodes):
193 193 # cannot merge two tags with same rank pointing to different nodes
194 194 return None
195 195
196 196 # which are the highest ranking (hr) / lowest ranking (lr) nodes?
197 197 if len(p1nodes) >= len(p2nodes):
198 198 hrnodes, lrnodes = p1nodes, p2nodes
199 199 else:
200 200 hrnodes, lrnodes = p2nodes, p1nodes
201 201
202 202 # the lowest ranking nodes will be written first, followed by the highest
203 203 # ranking nodes
204 204 # to avoid unwanted tag rank explosion we try to see if there are some
205 205 # common nodes that can be written only once
206 206 commonidx = len(lrnodes)
207 207 for n in range(len(lrnodes)):
208 208 if hrnodes[n][0] != lrnodes[n][0]:
209 209 commonidx = n
210 210 break
211 211 lrnodes[n][1] = p1nodes[n][1]
212 212
213 213 # the merged node list has 3 parts:
214 214 # - common nodes
215 215 # - non common lowest ranking nodes
216 216 # - non common highest ranking nodes
217 217 # note that the common nodes plus the non common lowest ranking nodes is the
218 218 # whole list of lr nodes
219 219 return lrnodes + hrnodes[commonidx:]
220 220
221 221 def merge(repo, fcd, fco, fca):
222 222 '''
223 223 Merge the tags of two revisions, taking into account the base tags
224 224 Try to minimize the diff between the merged tags and the first parent tags
225 225 '''
226 226 ui = repo.ui
227 227 # read the p1, p2 and base tags
228 228 # only keep the line numbers for the p1 tags
229 229 p1tags = readtagsformerge(
230 230 ui, repo, fcd.data().splitlines(), fn="p1 tags",
231 231 keeplinenums=True)
232 232 p2tags = readtagsformerge(
233 233 ui, repo, fco.data().splitlines(), fn="p2 tags",
234 234 keeplinenums=False)
235 235 basetags = readtagsformerge(
236 236 ui, repo, fca.data().splitlines(), fn="base tags",
237 237 keeplinenums=False)
238 238
239 239 # recover the list of "lost tags" (i.e. those that were found on the base
240 240 # revision but not on one of the revisions being merged)
241 241 basetagset = set(basetags)
242 242 for n, pntags in enumerate((p1tags, p2tags)):
243 243 pntagset = set(pntags)
244 244 pnlosttagset = basetagset - pntagset
245 245 for t in pnlosttagset:
246 246 pntags[t] = basetags[t]
247 247 if pntags[t][-1][0] != hexnullid:
248 248 pntags[t].append([hexnullid, None])
249 249
250 250 conflictedtags = [] # for reporting purposes
251 251 mergedtags = util.sortdict(p1tags)
252 252 # sortdict does not implement iteritems()
253 253 for tname, p2nodes in p2tags.items():
254 254 if tname not in mergedtags:
255 255 mergedtags[tname] = p2nodes
256 256 continue
257 257 p1nodes = mergedtags[tname]
258 258 mergednodes = singletagmerge(p1nodes, p2nodes)
259 259 if mergednodes is None:
260 260 conflictedtags.append(tname)
261 261 continue
262 262 mergedtags[tname] = mergednodes
263 263
264 264 if conflictedtags:
265 265 numconflicts = len(conflictedtags)
266 266 ui.warn(_('automatic .hgtags merge failed\n'
267 267 'the following %d tags are in conflict: %s\n')
268 268 % (numconflicts, ', '.join(sorted(conflictedtags))))
269 269 return True, 1
270 270
271 271 writemergedtags(repo, mergedtags)
272 272 ui.note(_('.hgtags merged successfully\n'))
273 273 return False, 0
274 274
General Comments 0
You need to be logged in to leave comments. Login now