Mercurial > hg-stable
changeset 1457:518da3c3b6ce
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.
| author | Eric Hopper <hopper@omnifarious.org> |
|---|---|
| date | Fri, 07 Oct 2005 10:48:27 -0700 |
| parents | 9b3ef6f3cef5 |
| children | 1033892bbb87 |
| files | mercurial/commands.py mercurial/localrepo.py mercurial/revlog.py |
| diffstat | 3 files changed, 146 insertions(+), 29 deletions(-) [+] |
line wrap: on
line diff
--- 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']:
--- 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 = {}
--- 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 non-nullid 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 = {}