Mercurial > public > mercurial-scm > hg

annotate mercurial/graphmod.py @ 14043:1c1e1232abdc

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