Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/graphmod.py @ 14088:e83ced8b6464

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
graphlog: use a set for inclusion test This makes a big difference in performance in the special case where all revisions are being graphed.
author Patrick Mezard <pmezard@gmail.com>
date Sat, 30 Apr 2011 19:42:00 +0200
parents f3d585c9b042
children 03e1c2d35c6a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
14088
e83ced8b6464 graphlog: use a set for inclusion test
Patrick Mezard <pmezard@gmail.com>
parents: 14087
diff changeset
39 knownrevs = set(revs)
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
40 for rev in revs:
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
41 ctx = repo[rev]
14088
e83ced8b6464 graphlog: use a set for inclusion test
Patrick Mezard <pmezard@gmail.com>
parents: 14087
diff changeset
42 parents = sorted(set([p.rev() for p in ctx.parents()
e83ced8b6464 graphlog: use a set for inclusion test
Patrick Mezard <pmezard@gmail.com>
parents: 14087
diff changeset
43 if p.rev() in knownrevs]))
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
44 mpars = [p.rev() for p in ctx.parents() if
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
45 p.rev() != nullrev and p.rev() not in parents]
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
46
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
47 for mpar in mpars:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
48 gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
49 gpcache[mpar] = gp
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
50 if gp is None:
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
51 parents.append(mpar)
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
52 elif gp not in parents:
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
53 parents.append(gp)
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
54
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
55 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
56
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
57 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
58 """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
59
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8837
diff changeset
60 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
61 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
62 """
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
63 include = set(nodes)
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
64 for node in nodes:
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
65 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
66 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
67 yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
68
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
69 def colored(dag):
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
70 """annotates a DAG with colored edge information
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
71
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
72 For each DAG node this function emits tuples::
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 (id, type, data, (col, color), [(col, nextcol, color)])
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
75
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
76 with the following new elements:
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
77
8835
ec5483efc31f graphmod: code cleanup and doc fix
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8225
diff changeset
78 - 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
79 - 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
80 parents.
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
81 """
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
82 seen = []
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
83 colors = {}
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
84 newcolor = 1
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
85 for (cur, type, data, parents) in dag:
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
86
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
87 # Compute seen and next
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
88 if cur not in seen:
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
89 seen.append(cur) # new head
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
90 colors[cur] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
91 newcolor += 1
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
92
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
93 col = seen.index(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
94 color = colors.pop(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
95 next = seen[:]
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
96
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
97 # Add parents to next
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
98 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
99 next[col:col + 1] = addparents
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
100
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
101 # Set colors for the parents
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
102 for i, p in enumerate(addparents):
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
103 if not i:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
104 colors[p] = color
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
105 else:
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
106 colors[p] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
107 newcolor += 1
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
108
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
109 # Add edges to the graph
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
110 edges = []
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
111 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
112 if eid in next:
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
113 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
114 elif eid == cur:
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
115 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
116 edges.append((ecol, next.index(p), color))
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
117
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
118 # Yield and move on
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
119 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
120 seen = next
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
121
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
122
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
123 def grandparent(cl, lowestrev, roots, head):
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
124 """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
125
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
126 Derived from revlog.revlog.nodesbetween, but only returns next rev
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
127 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
128 constraints:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
129
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
130 1. N is a descendant of some node in 'roots'
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
131 2. N is an ancestor of 'head'
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
132 3. N is some node in 'roots' or nullrev
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
133
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
134 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
135 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
136 included in 'nodes'.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
137 """
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
138 ancestors = set()
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
139 # 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
140 revstotag = set([head])
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
141 revstotag.discard(nullrev)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
142 llowestrev = max(nullrev, lowestrev)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
143
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
144 while revstotag:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
145 r = revstotag.pop()
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
146 # A node's revision number represents its place in a
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
147 # topologically sorted list of nodes.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
148 if r >= llowestrev:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
149 if r not in ancestors:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
150 # 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
151 # and we haven't already been marked as an ancestor
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
152 ancestors.add(r) # Mark as ancestor
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
153 # Add non-nullrev parents to list of nodes to tag.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
154 revstotag.update([p for p in cl.parentrevs(r)])
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
155
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
156 if not ancestors:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
157 return
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
158 # 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
159 # roots that are not ancestors.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
160
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
161 # 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
162 if lowestrev > nullrev:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
163 # 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
164 # include roots that aren't ancestors.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
165
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
166 # Filter out roots that aren't ancestors of heads
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
167 _roots = ancestors.intersection(roots)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
168 if not _roots:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
169 return
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
170 # Recompute the lowest revision
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
171 lowestrev = min(roots)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
172 else:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
173 # 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
174 # any other roots.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
175 lowestrev = nullrev
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
176 _roots = [nullrev]
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
177
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
178 # The roots are just the descendants.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
179 # 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
180 # 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
181 # they're descendents.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
182 lowestrevisnullrev = (lowestrev == nullrev)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
183 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
184 if lowestrevisnullrev or r in _roots:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
185 pass
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
186 elif _roots.issuperset(cl.parentrevs(r)):
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
187 # 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
188 # descendents. (We seeded the dependents list with the roots
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
189 # up there, remember?)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
190 _roots.add(r)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
191 else:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
192 continue
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
193 if r in ancestors:
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
194 # Only include nodes that are both descendents and ancestors.
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
195 return r