# HG changeset patch
# User Eric Hopper
# Date 1128707307 25200
# Node ID 518da3c3b6ce90e37340b01a23685361d3eb5ef9
# Parent 9b3ef6f3cef5c19c0ddf894ec63ad2dbc51a0d63
This implements the nodesbetween method, and it removes the newer method
and replaces it with calls to nodesbetween.
nodesbetween calculates all the changesets needed to have a complete
revision graph between a given set of base nodes and a given set of
head nodes.
diff r 9b3ef6f3cef5 r 518da3c3b6ce mercurial/commands.py
 a/mercurial/commands.py Wed Oct 05 19:27:35 2005 0700
+++ b/mercurial/commands.py Fri Oct 07 10:48:27 2005 0700
@@ 1193,7 +1193,7 @@
o = repo.findincoming(other)
if not o:
return
 o = other.newer(o)
+ o = other.changelog.nodesbetween(o)[0]
for n in o:
show_changeset(ui, other, changenode=n)
if opts['patch']:
@@ 1305,7 +1305,7 @@
dest = ui.expandpath(dest)
other = hg.repository(ui, dest)
o = repo.findoutgoing(other)
 o = repo.newer(o)
+ o = repo.changelog.nodesbetween(o)[0]
for n in o:
show_changeset(ui, repo, changenode=n)
if opts['patch']:
diff r 9b3ef6f3cef5 r 518da3c3b6ce mercurial/localrepo.py
 a/mercurial/localrepo.py Wed Oct 05 19:27:35 2005 0700
+++ b/mercurial/localrepo.py Fri Oct 07 10:48:27 2005 0700
@@ 700,32 +700,6 @@
return r
 def newer(self, nodes):
 m = {}
 nl = []
 pm = {}
 cl = self.changelog
 t = l = cl.count()

 # find the lowest numbered node
 for n in nodes:
 l = min(l, cl.rev(n))
 m[n] = 1

 for i in xrange(l, t):
 n = cl.node(i)
 if n in m: # explicitly listed
 pm[n] = 1
 nl.append(n)
 continue
 for p in cl.parents(n):
 if p in pm: # parent listed
 pm[n] = 1
 nl.append(n)
 break

 return nl

def findincoming(self, remote, base=None, heads=None):
m = self.changelog.nodemap
search = []
@@ 922,7 +896,7 @@
genread = util.chunkbuffer
def gengroup():
 nodes = self.newer(basenodes)
+ nodes = self.changelog.nodesbetween(basenodes)[0]
# construct the link map
linkmap = {}
diff r 9b3ef6f3cef5 r 518da3c3b6ce mercurial/revlog.py
 a/mercurial/revlog.py Wed Oct 05 19:27:35 2005 0700
+++ b/mercurial/revlog.py Fri Oct 07 10:48:27 2005 0700
@@ 246,6 +246,149 @@
visit.append(p)
return reachable
+ def nodesbetween(self, roots=None, heads=None):
+ """Return a tuple containing three elements. Elements 1 and 2 contain
+ a final list bases and heads after all the unreachable ones have been
+ pruned. Element 0 contains a topologically sorted list of all
+
+ nodes that satisfy these constraints:
+ 1. All nodes must be descended from a node in roots (the nodes on
+ roots are considered descended from themselves).
+ 2. All nodes must also be ancestors of a node in heads (the nodes in
+ heads are considered to be their own ancestors).
+
+ If roots is unspecified, nullid is assumed as the only root.
+ If heads is unspecified, it is taken to be the output of the
+ heads method (i.e. a list of all nodes in the repository that
+ have no children)."""
+ if roots is not None:
+ roots = list(roots)
+ lowestrev = min([self.rev(n) for n in roots])
+ else:
+ roots = [nullid] # Everybody's a descendent of nullid
+ lowestrev = 1
+ if (lowestrev == 1) and (heads is None):
+ # We want _all_ the nodes!
+ return ([self.node(r) for r in xrange(0, self.count())],
+ [nullid], list(self.heads()))
+ if heads is None:
+ # All nodes are ancestors, so the latest ancestor is the last
+ # node.
+ highestrev = self.count()  1
+ # Set ancestors to None to signal that every node is an ancestor.
+ ancestors = None
+ # Set heads to an empty dictionary for later discovery of heads
+ heads = {}
+ else:
+ ancestors = {}
+ # Start at the top and keep marking parents until we're done.
+ nodestotag = list(heads)
+ # Turn heads into a dictionary so we can remove 'fake' heads.
+ # Also, later we will be using it to filter out the heads we can't
+ # find from roots.
+ heads = dict.fromkeys(heads, 0)
+ # Remember where the top was so we can use it as a limit later.
+ highestrev = max([self.rev(n) for n in nodestotag])
+ while nodestotag:
+ # grab a node to tag
+ n = nodestotag.pop()
+ # Never tag nullid
+ if n == nullid:
+ continue
+ # A node's revision number represents its place in a
+ # topologically sorted list of nodes.
+ r = self.rev(n)
+ if r >= lowestrev:
+ if n not in ancestors:
+ # If we are possibly a descendent of one of the roots
+ # and we haven't already been marked as an ancestor
+ ancestors[n] = 1 # Mark as ancestor
+ # Add nonnullid parents to list of nodes to tag.
+ nodestotag.extend([p for p in self.parents(n) if
+ p != nullid])
+ elif n in heads: # We've seen it before, is it a fake head?
+ # So it is, real heads should not be the ancestors of
+ # any other heads.
+ heads.pop(n)
+ # Now that we have our set of ancestors, we want to remove any
+ # roots that are not ancestors.
+
+ # If one of the roots was nullid, everything is included anyway.
+ if lowestrev > 1:
+ # But, since we weren't, let's recompute the lowest rev to not
+ # include roots that aren't ancestors.
+
+ # Filter out roots that aren't ancestors of heads
+ roots = [n for n in roots if n in ancestors]
+ # Recompute the lowest revision
+ if roots:
+ lowestrev = min([self.rev(n) for n in roots])
+ else:
+ # No more roots? Return empty list
+ return ([], [], [])
+ else:
+ # We are descending from nullid, and don't need to care about
+ # any other roots.
+ lowestrev = 1
+ roots = [nullid]
+ # Transform our roots list into a 'set' (i.e. a dictionary where the
+ # values don't matter.
+ descendents = dict.fromkeys(roots, 1)
+ # Also, keep the original roots so we can filter out roots that aren't
+ # 'real' roots (i.e. are descended from other roots).
+ roots = descendents.copy()
+ # Our topologically sorted list of output nodes.
+ orderedout = []
+ # Don't start at nullid since we don't want nullid in our output list,
+ # and if nullid shows up in descedents, empty parents will look like
+ # they're descendents.
+ for r in xrange(max(lowestrev, 0), highestrev + 1):
+ n = self.node(r)
+ isdescendent = False
+ if lowestrev == 1: # Everybody is a descendent of nullid
+ isdescendent = True
+ elif n in descendents:
+ # n is already a descendent
+ isdescendent = True
+ # This check only needs to be done here because all the roots
+ # will start being marked is descendents before the loop.
+ if n in roots:
+ # If n was a root, check if it's a 'real' root.
+ p = tuple(self.parents(n))
+ # If any of its parents are descendents, it's not a root.
+ if (p[0] in descendents) or (p[1] in descendents):
+ roots.pop(n)
+ else:
+ p = tuple(self.parents(n))
+ # A node is a descendent if either of its parents are
+ # descendents. (We seeded the dependents list with the roots
+ # up there, remember?)
+ if (p[0] in descendents) or (p[1] in descendents):
+ descendents[n] = 1
+ isdescendent = True
+ if isdescendent and ((ancestors is None) or (n in ancestors)):
+ # Only include nodes that are both descendents and ancestors.
+ orderedout.append(n)
+ if (ancestors is not None) and (n in heads):
+ # We're trying to figure out which heads are reachable
+ # from roots.
+ # Mark this head as having been reached
+ heads[n] = 1
+ elif ancestors is None:
+ # Otherwise, we're trying to discover the heads.
+ # Assume this is a head because if it isn't, the next step
+ # will eventually remove it.
+ heads[n] = 1
+ # But, obviously its parents aren't.
+ for p in self.parents(n):
+ heads.pop(p, None)
+ heads = [n for n in heads.iterkeys() if heads[n] != 0]
+ roots = roots.keys()
+ assert orderedout
+ assert roots
+ assert heads
+ return (orderedout, roots, heads)
+
def heads(self, stop=None):
"""return the list of all nodes that have no children"""
p = {}