##// END OF EJS Templates
graphnode: remove usage of `set()`...
Pierre-Yves David -
r22878:890e874c default
parent child Browse files
Show More
@@ -1,368 +1,368 b''
1 1 # Revision graph generator for Mercurial
2 2 #
3 3 # Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl>
4 4 # Copyright 2007 Joel Rosdahl <joel@rosdahl.net>
5 5 #
6 6 # This software may be used and distributed according to the terms of the
7 7 # GNU General Public License version 2 or any later version.
8 8
9 9 """supports walking the history as DAGs suitable for graphical output
10 10
11 11 The most basic format we use is that of::
12 12
13 13 (id, type, data, [parentids])
14 14
15 15 The node and parent ids are arbitrary integers which identify a node in the
16 16 context of the graph returned. Type is a constant specifying the node type.
17 17 Data depends on type.
18 18 """
19 19
20 20 from mercurial.node import nullrev
21 21 import util
22 22
23 23 CHANGESET = 'C'
24 24
25 25 def dagwalker(repo, revs):
26 26 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
27 27
28 28 This generator function walks through revisions (which should be ordered
29 29 from bigger to lower). It returns a tuple for each node. The node and parent
30 30 ids are arbitrary integers which identify a node in the context of the graph
31 31 returned.
32 32 """
33 33 if not revs:
34 34 return
35 35
36 36 cl = repo.changelog
37 37 lowestrev = revs.min()
38 38 gpcache = {}
39 39
40 knownrevs = revs.set()
40 knownrevs = revs
41 41 for rev in revs:
42 42 ctx = repo[rev]
43 43 parents = sorted(set([p.rev() for p in ctx.parents()
44 44 if p.rev() in knownrevs]))
45 45 mpars = [p.rev() for p in ctx.parents() if
46 46 p.rev() != nullrev and p.rev() not in parents]
47 47
48 48 for mpar in mpars:
49 49 gp = gpcache.get(mpar)
50 50 if gp is None:
51 51 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
52 52 if not gp:
53 53 parents.append(mpar)
54 54 else:
55 55 parents.extend(g for g in gp if g not in parents)
56 56
57 57 yield (ctx.rev(), CHANGESET, ctx, parents)
58 58
59 59 def nodes(repo, nodes):
60 60 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
61 61
62 62 This generator function walks the given nodes. It only returns parents
63 63 that are in nodes, too.
64 64 """
65 65 include = set(nodes)
66 66 for node in nodes:
67 67 ctx = repo[node]
68 68 parents = set([p.rev() for p in ctx.parents() if p.node() in include])
69 69 yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
70 70
71 71 def colored(dag, repo):
72 72 """annotates a DAG with colored edge information
73 73
74 74 For each DAG node this function emits tuples::
75 75
76 76 (id, type, data, (col, color), [(col, nextcol, color)])
77 77
78 78 with the following new elements:
79 79
80 80 - Tuple (col, color) with column and color index for the current node
81 81 - A list of tuples indicating the edges between the current node and its
82 82 parents.
83 83 """
84 84 seen = []
85 85 colors = {}
86 86 newcolor = 1
87 87 config = {}
88 88
89 89 for key, val in repo.ui.configitems('graph'):
90 90 if '.' in key:
91 91 branch, setting = key.rsplit('.', 1)
92 92 # Validation
93 93 if setting == "width" and val.isdigit():
94 94 config.setdefault(branch, {})[setting] = int(val)
95 95 elif setting == "color" and val.isalnum():
96 96 config.setdefault(branch, {})[setting] = val
97 97
98 98 if config:
99 99 getconf = util.lrucachefunc(
100 100 lambda rev: config.get(repo[rev].branch(), {}))
101 101 else:
102 102 getconf = lambda rev: {}
103 103
104 104 for (cur, type, data, parents) in dag:
105 105
106 106 # Compute seen and next
107 107 if cur not in seen:
108 108 seen.append(cur) # new head
109 109 colors[cur] = newcolor
110 110 newcolor += 1
111 111
112 112 col = seen.index(cur)
113 113 color = colors.pop(cur)
114 114 next = seen[:]
115 115
116 116 # Add parents to next
117 117 addparents = [p for p in parents if p not in next]
118 118 next[col:col + 1] = addparents
119 119
120 120 # Set colors for the parents
121 121 for i, p in enumerate(addparents):
122 122 if not i:
123 123 colors[p] = color
124 124 else:
125 125 colors[p] = newcolor
126 126 newcolor += 1
127 127
128 128 # Add edges to the graph
129 129 edges = []
130 130 for ecol, eid in enumerate(seen):
131 131 if eid in next:
132 132 bconf = getconf(eid)
133 133 edges.append((
134 134 ecol, next.index(eid), colors[eid],
135 135 bconf.get('width', -1),
136 136 bconf.get('color', '')))
137 137 elif eid == cur:
138 138 for p in parents:
139 139 bconf = getconf(p)
140 140 edges.append((
141 141 ecol, next.index(p), color,
142 142 bconf.get('width', -1),
143 143 bconf.get('color', '')))
144 144
145 145 # Yield and move on
146 146 yield (cur, type, data, (col, color), edges)
147 147 seen = next
148 148
149 149 def grandparent(cl, lowestrev, roots, head):
150 150 """Return all ancestors of head in roots which revision is
151 151 greater or equal to lowestrev.
152 152 """
153 153 pending = set([head])
154 154 seen = set()
155 155 kept = set()
156 156 llowestrev = max(nullrev, lowestrev)
157 157 while pending:
158 158 r = pending.pop()
159 159 if r >= llowestrev and r not in seen:
160 160 if r in roots:
161 161 kept.add(r)
162 162 else:
163 163 pending.update([p for p in cl.parentrevs(r)])
164 164 seen.add(r)
165 165 return sorted(kept)
166 166
167 167 def asciiedges(type, char, lines, seen, rev, parents):
168 168 """adds edge info to changelog DAG walk suitable for ascii()"""
169 169 if rev not in seen:
170 170 seen.append(rev)
171 171 nodeidx = seen.index(rev)
172 172
173 173 knownparents = []
174 174 newparents = []
175 175 for parent in parents:
176 176 if parent in seen:
177 177 knownparents.append(parent)
178 178 else:
179 179 newparents.append(parent)
180 180
181 181 ncols = len(seen)
182 182 nextseen = seen[:]
183 183 nextseen[nodeidx:nodeidx + 1] = newparents
184 184 edges = [(nodeidx, nextseen.index(p)) for p in knownparents if p != nullrev]
185 185
186 186 while len(newparents) > 2:
187 187 # ascii() only knows how to add or remove a single column between two
188 188 # calls. Nodes with more than two parents break this constraint so we
189 189 # introduce intermediate expansion lines to grow the active node list
190 190 # slowly.
191 191 edges.append((nodeidx, nodeidx))
192 192 edges.append((nodeidx, nodeidx + 1))
193 193 nmorecols = 1
194 194 yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))
195 195 char = '\\'
196 196 lines = []
197 197 nodeidx += 1
198 198 ncols += 1
199 199 edges = []
200 200 del newparents[0]
201 201
202 202 if len(newparents) > 0:
203 203 edges.append((nodeidx, nodeidx))
204 204 if len(newparents) > 1:
205 205 edges.append((nodeidx, nodeidx + 1))
206 206 nmorecols = len(nextseen) - ncols
207 207 seen[:] = nextseen
208 208 yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))
209 209
210 210 def _fixlongrightedges(edges):
211 211 for (i, (start, end)) in enumerate(edges):
212 212 if end > start:
213 213 edges[i] = (start, end + 1)
214 214
215 215 def _getnodelineedgestail(
216 216 node_index, p_node_index, n_columns, n_columns_diff, p_diff, fix_tail):
217 217 if fix_tail and n_columns_diff == p_diff and n_columns_diff != 0:
218 218 # Still going in the same non-vertical direction.
219 219 if n_columns_diff == -1:
220 220 start = max(node_index + 1, p_node_index)
221 221 tail = ["|", " "] * (start - node_index - 1)
222 222 tail.extend(["/", " "] * (n_columns - start))
223 223 return tail
224 224 else:
225 225 return ["\\", " "] * (n_columns - node_index - 1)
226 226 else:
227 227 return ["|", " "] * (n_columns - node_index - 1)
228 228
229 229 def _drawedges(edges, nodeline, interline):
230 230 for (start, end) in edges:
231 231 if start == end + 1:
232 232 interline[2 * end + 1] = "/"
233 233 elif start == end - 1:
234 234 interline[2 * start + 1] = "\\"
235 235 elif start == end:
236 236 interline[2 * start] = "|"
237 237 else:
238 238 if 2 * end >= len(nodeline):
239 239 continue
240 240 nodeline[2 * end] = "+"
241 241 if start > end:
242 242 (start, end) = (end, start)
243 243 for i in range(2 * start + 1, 2 * end):
244 244 if nodeline[i] != "+":
245 245 nodeline[i] = "-"
246 246
247 247 def _getpaddingline(ni, n_columns, edges):
248 248 line = []
249 249 line.extend(["|", " "] * ni)
250 250 if (ni, ni - 1) in edges or (ni, ni) in edges:
251 251 # (ni, ni - 1) (ni, ni)
252 252 # | | | | | | | |
253 253 # +---o | | o---+
254 254 # | | c | | c | |
255 255 # | |/ / | |/ /
256 256 # | | | | | |
257 257 c = "|"
258 258 else:
259 259 c = " "
260 260 line.extend([c, " "])
261 261 line.extend(["|", " "] * (n_columns - ni - 1))
262 262 return line
263 263
264 264 def asciistate():
265 265 """returns the initial value for the "state" argument to ascii()"""
266 266 return [0, 0]
267 267
268 268 def ascii(ui, state, type, char, text, coldata):
269 269 """prints an ASCII graph of the DAG
270 270
271 271 takes the following arguments (one call per node in the graph):
272 272
273 273 - ui to write to
274 274 - Somewhere to keep the needed state in (init to asciistate())
275 275 - Column of the current node in the set of ongoing edges.
276 276 - Type indicator of node data, usually 'C' for changesets.
277 277 - Payload: (char, lines):
278 278 - Character to use as node's symbol.
279 279 - List of lines to display as the node's text.
280 280 - Edges; a list of (col, next_col) indicating the edges between
281 281 the current node and its parents.
282 282 - Number of columns (ongoing edges) in the current revision.
283 283 - The difference between the number of columns (ongoing edges)
284 284 in the next revision and the number of columns (ongoing edges)
285 285 in the current revision. That is: -1 means one column removed;
286 286 0 means no columns added or removed; 1 means one column added.
287 287 """
288 288
289 289 idx, edges, ncols, coldiff = coldata
290 290 assert -2 < coldiff < 2
291 291 if coldiff == -1:
292 292 # Transform
293 293 #
294 294 # | | | | | |
295 295 # o | | into o---+
296 296 # |X / |/ /
297 297 # | | | |
298 298 _fixlongrightedges(edges)
299 299
300 300 # add_padding_line says whether to rewrite
301 301 #
302 302 # | | | | | | | |
303 303 # | o---+ into | o---+
304 304 # | / / | | | # <--- padding line
305 305 # o | | | / /
306 306 # o | |
307 307 add_padding_line = (len(text) > 2 and coldiff == -1 and
308 308 [x for (x, y) in edges if x + 1 < y])
309 309
310 310 # fix_nodeline_tail says whether to rewrite
311 311 #
312 312 # | | o | | | | o | |
313 313 # | | |/ / | | |/ /
314 314 # | o | | into | o / / # <--- fixed nodeline tail
315 315 # | |/ / | |/ /
316 316 # o | | o | |
317 317 fix_nodeline_tail = len(text) <= 2 and not add_padding_line
318 318
319 319 # nodeline is the line containing the node character (typically o)
320 320 nodeline = ["|", " "] * idx
321 321 nodeline.extend([char, " "])
322 322
323 323 nodeline.extend(
324 324 _getnodelineedgestail(idx, state[1], ncols, coldiff,
325 325 state[0], fix_nodeline_tail))
326 326
327 327 # shift_interline is the line containing the non-vertical
328 328 # edges between this entry and the next
329 329 shift_interline = ["|", " "] * idx
330 330 if coldiff == -1:
331 331 n_spaces = 1
332 332 edge_ch = "/"
333 333 elif coldiff == 0:
334 334 n_spaces = 2
335 335 edge_ch = "|"
336 336 else:
337 337 n_spaces = 3
338 338 edge_ch = "\\"
339 339 shift_interline.extend(n_spaces * [" "])
340 340 shift_interline.extend([edge_ch, " "] * (ncols - idx - 1))
341 341
342 342 # draw edges from the current node to its parents
343 343 _drawedges(edges, nodeline, shift_interline)
344 344
345 345 # lines is the list of all graph lines to print
346 346 lines = [nodeline]
347 347 if add_padding_line:
348 348 lines.append(_getpaddingline(idx, ncols, edges))
349 349 lines.append(shift_interline)
350 350
351 351 # make sure that there are as many graph lines as there are
352 352 # log strings
353 353 while len(text) < len(lines):
354 354 text.append("")
355 355 if len(lines) < len(text):
356 356 extra_interline = ["|", " "] * (ncols + coldiff)
357 357 while len(lines) < len(text):
358 358 lines.append(extra_interline)
359 359
360 360 # print lines
361 361 indentation_level = max(ncols, ncols + coldiff)
362 362 for (line, logstr) in zip(lines, text):
363 363 ln = "%-*s %s" % (2 * indentation_level, "".join(line), logstr)
364 364 ui.write(ln.rstrip() + '\n')
365 365
366 366 # ... and start over
367 367 state[0] = coldiff
368 368 state[1] = idx
General Comments 0
You need to be logged in to leave comments. Login now