##// END OF EJS Templates
This implements the nodesbetween method, and it removes the newer method...
Eric Hopper -
r1457:518da3c3 default
parent child Browse files
Show More
@@ -1193,7 +1193,7 b' def incoming(ui, repo, source="default",'
1193 1193 o = repo.findincoming(other)
1194 1194 if not o:
1195 1195 return
1196 o = other.newer(o)
1196 o = other.changelog.nodesbetween(o)[0]
1197 1197 for n in o:
1198 1198 show_changeset(ui, other, changenode=n)
1199 1199 if opts['patch']:
@@ -1305,7 +1305,7 b' def outgoing(ui, repo, dest="default-pus'
1305 1305 dest = ui.expandpath(dest)
1306 1306 other = hg.repository(ui, dest)
1307 1307 o = repo.findoutgoing(other)
1308 o = repo.newer(o)
1308 o = repo.changelog.nodesbetween(o)[0]
1309 1309 for n in o:
1310 1310 show_changeset(ui, repo, changenode=n)
1311 1311 if opts['patch']:
@@ -700,32 +700,6 b' class localrepository:'
700 700
701 701 return r
702 702
703 def newer(self, nodes):
704 m = {}
705 nl = []
706 pm = {}
707 cl = self.changelog
708 t = l = cl.count()
709
710 # find the lowest numbered node
711 for n in nodes:
712 l = min(l, cl.rev(n))
713 m[n] = 1
714
715 for i in xrange(l, t):
716 n = cl.node(i)
717 if n in m: # explicitly listed
718 pm[n] = 1
719 nl.append(n)
720 continue
721 for p in cl.parents(n):
722 if p in pm: # parent listed
723 pm[n] = 1
724 nl.append(n)
725 break
726
727 return nl
728
729 703 def findincoming(self, remote, base=None, heads=None):
730 704 m = self.changelog.nodemap
731 705 search = []
@@ -922,7 +896,7 b' class localrepository:'
922 896 genread = util.chunkbuffer
923 897
924 898 def gengroup():
925 nodes = self.newer(basenodes)
899 nodes = self.changelog.nodesbetween(basenodes)[0]
926 900
927 901 # construct the link map
928 902 linkmap = {}
@@ -246,6 +246,149 b' class revlog:'
246 246 visit.append(p)
247 247 return reachable
248 248
249 def nodesbetween(self, roots=None, heads=None):
250 """Return a tuple containing three elements. Elements 1 and 2 contain
251 a final list bases and heads after all the unreachable ones have been
252 pruned. Element 0 contains a topologically sorted list of all
253
254 nodes that satisfy these constraints:
255 1. All nodes must be descended from a node in roots (the nodes on
256 roots are considered descended from themselves).
257 2. All nodes must also be ancestors of a node in heads (the nodes in
258 heads are considered to be their own ancestors).
259
260 If roots is unspecified, nullid is assumed as the only root.
261 If heads is unspecified, it is taken to be the output of the
262 heads method (i.e. a list of all nodes in the repository that
263 have no children)."""
264 if roots is not None:
265 roots = list(roots)
266 lowestrev = min([self.rev(n) for n in roots])
267 else:
268 roots = [nullid] # Everybody's a descendent of nullid
269 lowestrev = -1
270 if (lowestrev == -1) and (heads is None):
271 # We want _all_ the nodes!
272 return ([self.node(r) for r in xrange(0, self.count())],
273 [nullid], list(self.heads()))
274 if heads is None:
275 # All nodes are ancestors, so the latest ancestor is the last
276 # node.
277 highestrev = self.count() - 1
278 # Set ancestors to None to signal that every node is an ancestor.
279 ancestors = None
280 # Set heads to an empty dictionary for later discovery of heads
281 heads = {}
282 else:
283 ancestors = {}
284 # Start at the top and keep marking parents until we're done.
285 nodestotag = list(heads)
286 # Turn heads into a dictionary so we can remove 'fake' heads.
287 # Also, later we will be using it to filter out the heads we can't
288 # find from roots.
289 heads = dict.fromkeys(heads, 0)
290 # Remember where the top was so we can use it as a limit later.
291 highestrev = max([self.rev(n) for n in nodestotag])
292 while nodestotag:
293 # grab a node to tag
294 n = nodestotag.pop()
295 # Never tag nullid
296 if n == nullid:
297 continue
298 # A node's revision number represents its place in a
299 # topologically sorted list of nodes.
300 r = self.rev(n)
301 if r >= lowestrev:
302 if n not in ancestors:
303 # If we are possibly a descendent of one of the roots
304 # and we haven't already been marked as an ancestor
305 ancestors[n] = 1 # Mark as ancestor
306 # Add non-nullid parents to list of nodes to tag.
307 nodestotag.extend([p for p in self.parents(n) if
308 p != nullid])
309 elif n in heads: # We've seen it before, is it a fake head?
310 # So it is, real heads should not be the ancestors of
311 # any other heads.
312 heads.pop(n)
313 # Now that we have our set of ancestors, we want to remove any
314 # roots that are not ancestors.
315
316 # If one of the roots was nullid, everything is included anyway.
317 if lowestrev > -1:
318 # But, since we weren't, let's recompute the lowest rev to not
319 # include roots that aren't ancestors.
320
321 # Filter out roots that aren't ancestors of heads
322 roots = [n for n in roots if n in ancestors]
323 # Recompute the lowest revision
324 if roots:
325 lowestrev = min([self.rev(n) for n in roots])
326 else:
327 # No more roots? Return empty list
328 return ([], [], [])
329 else:
330 # We are descending from nullid, and don't need to care about
331 # any other roots.
332 lowestrev = -1
333 roots = [nullid]
334 # Transform our roots list into a 'set' (i.e. a dictionary where the
335 # values don't matter.
336 descendents = dict.fromkeys(roots, 1)
337 # Also, keep the original roots so we can filter out roots that aren't
338 # 'real' roots (i.e. are descended from other roots).
339 roots = descendents.copy()
340 # Our topologically sorted list of output nodes.
341 orderedout = []
342 # Don't start at nullid since we don't want nullid in our output list,
343 # and if nullid shows up in descedents, empty parents will look like
344 # they're descendents.
345 for r in xrange(max(lowestrev, 0), highestrev + 1):
346 n = self.node(r)
347 isdescendent = False
348 if lowestrev == -1: # Everybody is a descendent of nullid
349 isdescendent = True
350 elif n in descendents:
351 # n is already a descendent
352 isdescendent = True
353 # This check only needs to be done here because all the roots
354 # will start being marked is descendents before the loop.
355 if n in roots:
356 # If n was a root, check if it's a 'real' root.
357 p = tuple(self.parents(n))
358 # If any of its parents are descendents, it's not a root.
359 if (p[0] in descendents) or (p[1] in descendents):
360 roots.pop(n)
361 else:
362 p = tuple(self.parents(n))
363 # A node is a descendent if either of its parents are
364 # descendents. (We seeded the dependents list with the roots
365 # up there, remember?)
366 if (p[0] in descendents) or (p[1] in descendents):
367 descendents[n] = 1
368 isdescendent = True
369 if isdescendent and ((ancestors is None) or (n in ancestors)):
370 # Only include nodes that are both descendents and ancestors.
371 orderedout.append(n)
372 if (ancestors is not None) and (n in heads):
373 # We're trying to figure out which heads are reachable
374 # from roots.
375 # Mark this head as having been reached
376 heads[n] = 1
377 elif ancestors is None:
378 # Otherwise, we're trying to discover the heads.
379 # Assume this is a head because if it isn't, the next step
380 # will eventually remove it.
381 heads[n] = 1
382 # But, obviously its parents aren't.
383 for p in self.parents(n):
384 heads.pop(p, None)
385 heads = [n for n in heads.iterkeys() if heads[n] != 0]
386 roots = roots.keys()
387 assert orderedout
388 assert roots
389 assert heads
390 return (orderedout, roots, heads)
391
249 392 def heads(self, stop=None):
250 393 """return the list of all nodes that have no children"""
251 394 p = {}
General Comments 0
You need to be logged in to leave comments. Login now