Show More
@@ -1,205 +1,193 b'' | |||||
1 | # Revision graph generator for Mercurial |
|
1 | # Revision graph generator for Mercurial | |
2 | # |
|
2 | # | |
3 | # Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl> |
|
3 | # Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl> | |
4 | # Copyright 2007 Joel Rosdahl <joel@rosdahl.net> |
|
4 | # Copyright 2007 Joel Rosdahl <joel@rosdahl.net> | |
5 | # |
|
5 | # | |
6 | # This software may be used and distributed according to the terms of the |
|
6 | # This software may be used and distributed according to the terms of the | |
7 | # GNU General Public License version 2 or any later version. |
|
7 | # GNU General Public License version 2 or any later version. | |
8 |
|
8 | |||
9 | """supports walking the history as DAGs suitable for graphical output |
|
9 | """supports walking the history as DAGs suitable for graphical output | |
10 |
|
10 | |||
11 | The most basic format we use is that of:: |
|
11 | The most basic format we use is that of:: | |
12 |
|
12 | |||
13 | (id, type, data, [parentids]) |
|
13 | (id, type, data, [parentids]) | |
14 |
|
14 | |||
15 | The node and parent ids are arbitrary integers which identify a node in the |
|
15 | The node and parent ids are arbitrary integers which identify a node in the | |
16 | context of the graph returned. Type is a constant specifying the node type. |
|
16 | context of the graph returned. Type is a constant specifying the node type. | |
17 | Data depends on type. |
|
17 | Data depends on type. | |
18 | """ |
|
18 | """ | |
19 |
|
19 | |||
20 | from mercurial.node import nullrev |
|
20 | from mercurial.node import nullrev | |
21 |
|
21 | |||
22 | CHANGESET = 'C' |
|
22 | CHANGESET = 'C' | |
23 |
|
23 | |||
24 | def dagwalker(repo, revs): |
|
24 | def dagwalker(repo, revs): | |
25 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples |
|
25 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples | |
26 |
|
26 | |||
27 | This generator function walks through revisions (which should be ordered |
|
27 | This generator function walks through revisions (which should be ordered | |
28 | from bigger to lower). It returns a tuple for each node. The node and parent |
|
28 | from bigger to lower). It returns a tuple for each node. The node and parent | |
29 | ids are arbitrary integers which identify a node in the context of the graph |
|
29 | ids are arbitrary integers which identify a node in the context of the graph | |
30 | returned. |
|
30 | returned. | |
31 | """ |
|
31 | """ | |
32 | if not revs: |
|
32 | if not revs: | |
33 |
return |
|
33 | return | |
34 |
|
||||
35 | ns = [repo[r].node() for r in revs] |
|
|||
36 | revdag = list(nodes(repo, ns)) |
|
|||
37 |
|
34 | |||
38 | cl = repo.changelog |
|
35 | cl = repo.changelog | |
39 | lowestrev = min(revs) |
|
36 | lowestrev = min(revs) | |
40 | gpcache = {} |
|
37 | gpcache = {} | |
41 | leafs = {} |
|
|||
42 |
|
38 | |||
43 | for i, (id, c, ctx, parents) in enumerate(revdag): |
|
39 | for rev in revs: | |
|
40 | ctx = repo[rev] | |||
|
41 | parents = sorted(set([p.rev() for p in ctx.parents() if p.rev() in revs])) | |||
44 | mpars = [p.rev() for p in ctx.parents() if |
|
42 | mpars = [p.rev() for p in ctx.parents() if | |
45 | p.rev() != nullrev and p.rev() not in parents] |
|
43 | p.rev() != nullrev and p.rev() not in parents] | |
46 | grandparents = [] |
|
|||
47 |
|
44 | |||
48 | for mpar in mpars: |
|
45 | for mpar in mpars: | |
49 | gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar) |
|
46 | gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar) | |
50 | gpcache[mpar] = gp |
|
47 | gpcache[mpar] = gp | |
51 | if gp is None: |
|
48 | if gp is None: | |
52 | leafs.setdefault(mpar, []).append((i, ctx)) |
|
49 | parents.append(mpar) | |
53 |
el |
|
50 | elif gp not in parents: | |
54 |
|
|
51 | parents.append(gp) | |
55 |
|
52 | |||
56 | if grandparents: |
|
53 | yield (ctx.rev(), CHANGESET, ctx, parents) | |
57 | for gp in grandparents: |
|
|||
58 | if gp not in revdag[i][3]: |
|
|||
59 | revdag[i][3].append(gp) |
|
|||
60 |
|
||||
61 | for parent, leafs in leafs.iteritems(): |
|
|||
62 | for i, ctx in leafs: |
|
|||
63 | revdag[i][3].append(parent) |
|
|||
64 |
|
||||
65 | return revdag |
|
|||
66 |
|
54 | |||
67 | def nodes(repo, nodes): |
|
55 | def nodes(repo, nodes): | |
68 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples |
|
56 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples | |
69 |
|
57 | |||
70 | This generator function walks the given nodes. It only returns parents |
|
58 | This generator function walks the given nodes. It only returns parents | |
71 | that are in nodes, too. |
|
59 | that are in nodes, too. | |
72 | """ |
|
60 | """ | |
73 | include = set(nodes) |
|
61 | include = set(nodes) | |
74 | for node in nodes: |
|
62 | for node in nodes: | |
75 | ctx = repo[node] |
|
63 | ctx = repo[node] | |
76 | parents = set([p.rev() for p in ctx.parents() if p.node() in include]) |
|
64 | parents = set([p.rev() for p in ctx.parents() if p.node() in include]) | |
77 | yield (ctx.rev(), CHANGESET, ctx, sorted(parents)) |
|
65 | yield (ctx.rev(), CHANGESET, ctx, sorted(parents)) | |
78 |
|
66 | |||
79 | def colored(dag): |
|
67 | def colored(dag): | |
80 | """annotates a DAG with colored edge information |
|
68 | """annotates a DAG with colored edge information | |
81 |
|
69 | |||
82 | For each DAG node this function emits tuples:: |
|
70 | For each DAG node this function emits tuples:: | |
83 |
|
71 | |||
84 | (id, type, data, (col, color), [(col, nextcol, color)]) |
|
72 | (id, type, data, (col, color), [(col, nextcol, color)]) | |
85 |
|
73 | |||
86 | with the following new elements: |
|
74 | with the following new elements: | |
87 |
|
75 | |||
88 | - Tuple (col, color) with column and color index for the current node |
|
76 | - Tuple (col, color) with column and color index for the current node | |
89 | - A list of tuples indicating the edges between the current node and its |
|
77 | - A list of tuples indicating the edges between the current node and its | |
90 | parents. |
|
78 | parents. | |
91 | """ |
|
79 | """ | |
92 | seen = [] |
|
80 | seen = [] | |
93 | colors = {} |
|
81 | colors = {} | |
94 | newcolor = 1 |
|
82 | newcolor = 1 | |
95 | for (cur, type, data, parents) in dag: |
|
83 | for (cur, type, data, parents) in dag: | |
96 |
|
84 | |||
97 | # Compute seen and next |
|
85 | # Compute seen and next | |
98 | if cur not in seen: |
|
86 | if cur not in seen: | |
99 | seen.append(cur) # new head |
|
87 | seen.append(cur) # new head | |
100 | colors[cur] = newcolor |
|
88 | colors[cur] = newcolor | |
101 | newcolor += 1 |
|
89 | newcolor += 1 | |
102 |
|
90 | |||
103 | col = seen.index(cur) |
|
91 | col = seen.index(cur) | |
104 | color = colors.pop(cur) |
|
92 | color = colors.pop(cur) | |
105 | next = seen[:] |
|
93 | next = seen[:] | |
106 |
|
94 | |||
107 | # Add parents to next |
|
95 | # Add parents to next | |
108 | addparents = [p for p in parents if p not in next] |
|
96 | addparents = [p for p in parents if p not in next] | |
109 | next[col:col + 1] = addparents |
|
97 | next[col:col + 1] = addparents | |
110 |
|
98 | |||
111 | # Set colors for the parents |
|
99 | # Set colors for the parents | |
112 | for i, p in enumerate(addparents): |
|
100 | for i, p in enumerate(addparents): | |
113 | if not i: |
|
101 | if not i: | |
114 | colors[p] = color |
|
102 | colors[p] = color | |
115 | else: |
|
103 | else: | |
116 | colors[p] = newcolor |
|
104 | colors[p] = newcolor | |
117 | newcolor += 1 |
|
105 | newcolor += 1 | |
118 |
|
106 | |||
119 | # Add edges to the graph |
|
107 | # Add edges to the graph | |
120 | edges = [] |
|
108 | edges = [] | |
121 | for ecol, eid in enumerate(seen): |
|
109 | for ecol, eid in enumerate(seen): | |
122 | if eid in next: |
|
110 | if eid in next: | |
123 | edges.append((ecol, next.index(eid), colors[eid])) |
|
111 | edges.append((ecol, next.index(eid), colors[eid])) | |
124 | elif eid == cur: |
|
112 | elif eid == cur: | |
125 | for p in parents: |
|
113 | for p in parents: | |
126 | edges.append((ecol, next.index(p), color)) |
|
114 | edges.append((ecol, next.index(p), color)) | |
127 |
|
115 | |||
128 | # Yield and move on |
|
116 | # Yield and move on | |
129 | yield (cur, type, data, (col, color), edges) |
|
117 | yield (cur, type, data, (col, color), edges) | |
130 | seen = next |
|
118 | seen = next | |
131 |
|
119 | |||
132 |
|
120 | |||
133 | def grandparent(cl, lowestrev, roots, head): |
|
121 | def grandparent(cl, lowestrev, roots, head): | |
134 | """Return closest 'root' rev in topological path from 'roots' to 'head'. |
|
122 | """Return closest 'root' rev in topological path from 'roots' to 'head'. | |
135 |
|
123 | |||
136 | Derived from revlog.revlog.nodesbetween, but only returns next rev |
|
124 | Derived from revlog.revlog.nodesbetween, but only returns next rev | |
137 | of topologically sorted list of all nodes N that satisfy of these |
|
125 | of topologically sorted list of all nodes N that satisfy of these | |
138 | constraints: |
|
126 | constraints: | |
139 |
|
127 | |||
140 | 1. N is a descendant of some node in 'roots' |
|
128 | 1. N is a descendant of some node in 'roots' | |
141 | 2. N is an ancestor of 'head' |
|
129 | 2. N is an ancestor of 'head' | |
142 | 3. N is some node in 'roots' or nullrev |
|
130 | 3. N is some node in 'roots' or nullrev | |
143 |
|
131 | |||
144 | Every node is considered to be both a descendant and an ancestor |
|
132 | Every node is considered to be both a descendant and an ancestor | |
145 | of itself, so every reachable node in 'roots' and 'head' will be |
|
133 | of itself, so every reachable node in 'roots' and 'head' will be | |
146 | included in 'nodes'. |
|
134 | included in 'nodes'. | |
147 | """ |
|
135 | """ | |
148 | ancestors = set() |
|
136 | ancestors = set() | |
149 | # Start at the top and keep marking parents until we're done. |
|
137 | # Start at the top and keep marking parents until we're done. | |
150 | revstotag = set([head]) |
|
138 | revstotag = set([head]) | |
151 | revstotag.discard(nullrev) |
|
139 | revstotag.discard(nullrev) | |
152 | llowestrev = max(nullrev, lowestrev) |
|
140 | llowestrev = max(nullrev, lowestrev) | |
153 |
|
141 | |||
154 | while revstotag: |
|
142 | while revstotag: | |
155 | r = revstotag.pop() |
|
143 | r = revstotag.pop() | |
156 | # A node's revision number represents its place in a |
|
144 | # A node's revision number represents its place in a | |
157 | # topologically sorted list of nodes. |
|
145 | # topologically sorted list of nodes. | |
158 | if r >= llowestrev: |
|
146 | if r >= llowestrev: | |
159 | if r not in ancestors: |
|
147 | if r not in ancestors: | |
160 | # If we are possibly a descendent of one of the roots |
|
148 | # If we are possibly a descendent of one of the roots | |
161 | # and we haven't already been marked as an ancestor |
|
149 | # and we haven't already been marked as an ancestor | |
162 | ancestors.add(r) # Mark as ancestor |
|
150 | ancestors.add(r) # Mark as ancestor | |
163 | # Add non-nullrev parents to list of nodes to tag. |
|
151 | # Add non-nullrev parents to list of nodes to tag. | |
164 | revstotag.update([p for p in cl.parentrevs(r)]) |
|
152 | revstotag.update([p for p in cl.parentrevs(r)]) | |
165 |
|
153 | |||
166 | if not ancestors: |
|
154 | if not ancestors: | |
167 | return |
|
155 | return | |
168 | # Now that we have our set of ancestors, we want to remove any |
|
156 | # Now that we have our set of ancestors, we want to remove any | |
169 | # roots that are not ancestors. |
|
157 | # roots that are not ancestors. | |
170 |
|
158 | |||
171 | # If one of the roots was nullrev, everything is included anyway. |
|
159 | # If one of the roots was nullrev, everything is included anyway. | |
172 | if lowestrev > nullrev: |
|
160 | if lowestrev > nullrev: | |
173 | # But, since we weren't, let's recompute the lowest rev to not |
|
161 | # But, since we weren't, let's recompute the lowest rev to not | |
174 | # include roots that aren't ancestors. |
|
162 | # include roots that aren't ancestors. | |
175 |
|
163 | |||
176 | # Filter out roots that aren't ancestors of heads |
|
164 | # Filter out roots that aren't ancestors of heads | |
177 | _roots = ancestors.intersection(roots) |
|
165 | _roots = ancestors.intersection(roots) | |
178 | if not _roots: |
|
166 | if not _roots: | |
179 | return |
|
167 | return | |
180 | # Recompute the lowest revision |
|
168 | # Recompute the lowest revision | |
181 | lowestrev = min(roots) |
|
169 | lowestrev = min(roots) | |
182 | else: |
|
170 | else: | |
183 | # We are descending from nullrev, and don't need to care about |
|
171 | # We are descending from nullrev, and don't need to care about | |
184 | # any other roots. |
|
172 | # any other roots. | |
185 | lowestrev = nullrev |
|
173 | lowestrev = nullrev | |
186 | _roots = [nullrev] |
|
174 | _roots = [nullrev] | |
187 |
|
175 | |||
188 | # The roots are just the descendants. |
|
176 | # The roots are just the descendants. | |
189 | # Don't start at nullrev since we don't want nullrev in our output list, |
|
177 | # Don't start at nullrev since we don't want nullrev in our output list, | |
190 | # and if nullrev shows up in descedents, empty parents will look like |
|
178 | # and if nullrev shows up in descedents, empty parents will look like | |
191 | # they're descendents. |
|
179 | # they're descendents. | |
192 | lowestrevisnullrev = (lowestrev == nullrev) |
|
180 | lowestrevisnullrev = (lowestrev == nullrev) | |
193 | for r in xrange(head - 1, max(lowestrev, -1) - 1, -1): |
|
181 | for r in xrange(head - 1, max(lowestrev, -1) - 1, -1): | |
194 | if lowestrevisnullrev or r in _roots: |
|
182 | if lowestrevisnullrev or r in _roots: | |
195 | pass |
|
183 | pass | |
196 | elif _roots.issuperset(cl.parentrevs(r)): |
|
184 | elif _roots.issuperset(cl.parentrevs(r)): | |
197 | # A node is a descendent if either of its parents are |
|
185 | # A node is a descendent if either of its parents are | |
198 | # descendents. (We seeded the dependents list with the roots |
|
186 | # descendents. (We seeded the dependents list with the roots | |
199 | # up there, remember?) |
|
187 | # up there, remember?) | |
200 | _roots.add(r) |
|
188 | _roots.add(r) | |
201 | else: |
|
189 | else: | |
202 | continue |
|
190 | continue | |
203 | if r in ancestors: |
|
191 | if r in ancestors: | |
204 | # Only include nodes that are both descendents and ancestors. |
|
192 | # Only include nodes that are both descendents and ancestors. | |
205 | return r |
|
193 | return r |
General Comments 0
You need to be logged in to leave comments.
Login now