mercurial-scm/hg-stable: mercurial/graphmod.py annotate

annotate mercurial/graphmod.py @ 14087:f3d585c9b042

graphmod: restore generator nature of dagwalker 9966c95b8c4f introduced the ability to walk the DAG given arbitrary revisions, but changed the behaviour of it to return a list of all nodes (and create a changectx for each one) rather than doing it lazily. This has a pretty significant impact on performance for large repositories (tested on CPython repo, with output disabled): $ time hg glog real 0m2.642s user 0m2.560s sys 0m0.080s Before 9966c95b8c4f: $ time hg glog real 0m0.143s user 0m0.112s sys 0m0.032s And after this fix: $ time hg glog real 0m0.213s user 0m0.184s sys 0m0.028s

author	Idan Kamara <idankk86@gmail.com>
date	Sat, 30 Apr 2011 15:10:58 +0300
parents	e4bfb9c337f3
children	e83ced8b6464

rev	line source
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	1 # Revision graph generator for Mercurial
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	2 #
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	3 # Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl>
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	4 # Copyright 2007 Joel Rosdahl <joel@rosdahl.net>
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	5 #
8225 46293a0c7e9f updated license to be explicit about GPL version 2 Martin Geisler <mg@lazybytes.net> parents: 7873 diff changeset	6 # This software may be used and distributed according to the terms of the
10263 25e572394f5c Update license to GPLv2+ Matt Mackall <mpm@selenic.com> parents: 10084 diff changeset	7 # GNU General Public License version 2 or any later version.
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	8
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	9 """supports walking the history as DAGs suitable for graphical output
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	10
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	11 The most basic format we use is that of::
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	12
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	13 (id, type, data, [parentids])
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	14
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	15 The node and parent ids are arbitrary integers which identify a node in the
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	16 context of the graph returned. Type is a constant specifying the node type.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	17 Data depends on type.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	18 """
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	19
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	20 from mercurial.node import nullrev
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	21
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	22 CHANGESET = 'C'
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	23
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	24 def dagwalker(repo, revs):
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	25 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	26
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	27 This generator function walks through revisions (which should be ordered
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	28 from bigger to lower). It returns a tuple for each node. The node and parent
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	29 ids are arbitrary integers which identify a node in the context of the graph
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	30 returned.
8836 11ff34956ee7 graphmod/graphlog: move log walks to graphmod Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8835 diff changeset	31 """
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	32 if not revs:
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	33 return
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	34
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	35 cl = repo.changelog
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	36 lowestrev = min(revs)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	37 gpcache = {}
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	38
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	39 for rev in revs:
f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	40 ctx = repo[rev]
f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	41 parents = sorted(set([p.rev() for p in ctx.parents() if p.rev() in revs]))
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	42 mpars = [p.rev() for p in ctx.parents() if
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	43 p.rev() != nullrev and p.rev() not in parents]
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	44
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	45 for mpar in mpars:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	46 gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	47 gpcache[mpar] = gp
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	48 if gp is None:
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	49 parents.append(mpar)
f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	50 elif gp not in parents:
f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	51 parents.append(gp)
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	52
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	53 yield (ctx.rev(), CHANGESET, ctx, parents)
8836 11ff34956ee7 graphmod/graphlog: move log walks to graphmod Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8835 diff changeset	54
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	55 def nodes(repo, nodes):
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	56 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	57
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	58 This generator function walks the given nodes. It only returns parents
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	59 that are in nodes, too.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	60 """
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	61 include = set(nodes)
d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	62 for node in nodes:
d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	63 ctx = repo[node]
12951 101366ad816c graphmod: safer code when a changeset has two identical parents Nicolas Dumazet <nicdumz.commits@gmail.com> parents: 10602 diff changeset	64 parents = set([p.rev() for p in ctx.parents() if p.node() in include])
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	65 yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	66
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	67 def colored(dag):
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	68 """annotates a DAG with colored edge information
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	69
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	70 For each DAG node this function emits tuples::
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	71
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	72 (id, type, data, (col, color), [(col, nextcol, color)])
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	73
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	74 with the following new elements:
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	75
8835 ec5483efc31f graphmod: code cleanup and doc fix Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8225 diff changeset	76 - Tuple (col, color) with column and color index for the current node
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	77 - A list of tuples indicating the edges between the current node and its
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	78 parents.
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	79 """
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	80 seen = []
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	81 colors = {}
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	82 newcolor = 1
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	83 for (cur, type, data, parents) in dag:
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	84
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	85 # Compute seen and next
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	86 if cur not in seen:
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	87 seen.append(cur) # new head
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	88 colors[cur] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	89 newcolor += 1
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	90
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	91 col = seen.index(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	92 color = colors.pop(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	93 next = seen[:]
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	94
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	95 # Add parents to next
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	96 addparents = [p for p in parents if p not in next]
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	97 next[col:col + 1] = addparents
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	98
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	99 # Set colors for the parents
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	100 for i, p in enumerate(addparents):
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	101 if not i:
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	102 colors[p] = color
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	103 else:
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	104 colors[p] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	105 newcolor += 1
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	106
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	107 # Add edges to the graph
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	108 edges = []
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	109 for ecol, eid in enumerate(seen):
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	110 if eid in next:
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	111 edges.append((ecol, next.index(eid), colors[eid]))
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	112 elif eid == cur:
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	113 for p in parents:
10602 94145b531cf9 hgweb/graph: edge should be same color as the destination Benoit Boissinot <benoit.boissinot@ens-lyon.org> parents: 10264 diff changeset	114 edges.append((ecol, next.index(p), color))
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	115
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	116 # Yield and move on
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	117 yield (cur, type, data, (col, color), edges)
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	118 seen = next
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	119
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	120
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	121 def grandparent(cl, lowestrev, roots, head):
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	122 """Return closest 'root' rev in topological path from 'roots' to 'head'.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	123
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	124 Derived from revlog.revlog.nodesbetween, but only returns next rev
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	125 of topologically sorted list of all nodes N that satisfy of these
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	126 constraints:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	127
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	128 1. N is a descendant of some node in 'roots'
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	129 2. N is an ancestor of 'head'
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	130 3. N is some node in 'roots' or nullrev
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	131
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	132 Every node is considered to be both a descendant and an ancestor
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	133 of itself, so every reachable node in 'roots' and 'head' will be
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	134 included in 'nodes'.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	135 """
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	136 ancestors = set()
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	137 # Start at the top and keep marking parents until we're done.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	138 revstotag = set([head])
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	139 revstotag.discard(nullrev)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	140 llowestrev = max(nullrev, lowestrev)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	141
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	142 while revstotag:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	143 r = revstotag.pop()
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	144 # A node's revision number represents its place in a
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	145 # topologically sorted list of nodes.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	146 if r >= llowestrev:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	147 if r not in ancestors:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	148 # If we are possibly a descendent of one of the roots
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	149 # and we haven't already been marked as an ancestor
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	150 ancestors.add(r) # Mark as ancestor
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	151 # Add non-nullrev parents to list of nodes to tag.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	152 revstotag.update([p for p in cl.parentrevs(r)])
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	153
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	154 if not ancestors:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	155 return
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	156 # Now that we have our set of ancestors, we want to remove any
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	157 # roots that are not ancestors.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	158
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	159 # If one of the roots was nullrev, everything is included anyway.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	160 if lowestrev > nullrev:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	161 # But, since we weren't, let's recompute the lowest rev to not
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	162 # include roots that aren't ancestors.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	163
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	164 # Filter out roots that aren't ancestors of heads
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	165 _roots = ancestors.intersection(roots)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	166 if not _roots:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	167 return
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	168 # Recompute the lowest revision
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	169 lowestrev = min(roots)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	170 else:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	171 # We are descending from nullrev, and don't need to care about
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	172 # any other roots.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	173 lowestrev = nullrev
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	174 _roots = [nullrev]
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	175
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	176 # The roots are just the descendants.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	177 # Don't start at nullrev since we don't want nullrev in our output list,
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	178 # and if nullrev shows up in descedents, empty parents will look like
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	179 # they're descendents.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	180 lowestrevisnullrev = (lowestrev == nullrev)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	181 for r in xrange(head - 1, max(lowestrev, -1) - 1, -1):
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	182 if lowestrevisnullrev or r in _roots:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	183 pass
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	184 elif _roots.issuperset(cl.parentrevs(r)):
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	185 # A node is a descendent if either of its parents are
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	186 # descendents. (We seeded the dependents list with the roots
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	187 # up there, remember?)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	188 _roots.add(r)
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	189 else:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	190 continue
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	191 if r in ancestors:
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	192 # Only include nodes that are both descendents and ancestors.
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	193 return r

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/graphmod.py @ 14087:f3d585c9b042