Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/graphmod.py @ 16132:41fc1e078d68

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
graphmod: add config cache Before, we'd lookup the branch for every edge segment in the entire graph: extremely expensive. This happened even when no per-branch settings existed. Now we define a revision -> config cache function that's LRU-cached and is a no-op when no configuration exists. Still not terribly fast, but hopefully only one real branch lookup per revision. This might degenerate for wide graphs as the LRU is hard-coded to 20 elements.
author Matt Mackall <mpm@selenic.com>
date Fri, 17 Feb 2012 13:53:41 -0600
parents 6f236c8bdc01
children 6e4de55a41a4
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
16132
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
21 import util
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:
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
34 return
14042
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 cl = repo.changelog
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
37 lowestrev = min(revs)
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
38 gpcache = {}
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
39
14088
e83ced8b6464 graphlog: use a set for inclusion test
Patrick Mezard <pmezard@gmail.com>
parents: 14087
diff changeset
40 knownrevs = set(revs)
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
41 for rev in revs:
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
42 ctx = repo[rev]
14088
e83ced8b6464 graphlog: use a set for inclusion test
Patrick Mezard <pmezard@gmail.com>
parents: 14087
diff changeset
43 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
44 if p.rev() in knownrevs]))
14042
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
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
48 for mpar in mpars:
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
49 gp = gpcache.get(mpar)
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
50 if gp is None:
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
51 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
52 if not gp:
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
53 parents.append(mpar)
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
54 else:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
55 parents.extend(g for g in gp if g not in parents)
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
56
14087
f3d585c9b042 graphmod: restore generator nature of dagwalker
Idan Kamara <idankk86@gmail.com>
parents: 14064
diff changeset
57 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
58
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
59 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
60 """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
61
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8837
diff changeset
62 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
63 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
64 """
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
65 include = set(nodes)
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
66 for node in nodes:
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
67 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
68 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
69 yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
8837
d8e3a98018cb graphmod/graphlog: extract nodelistwalk
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8836
diff changeset
70
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
71 def colored(dag, repo):
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
72 """annotates a DAG with colored edge information
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
73
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
74 For each DAG node this function emits tuples::
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 (id, type, data, (col, color), [(col, nextcol, color)])
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
77
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
78 with the following new elements:
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
79
8835
ec5483efc31f graphmod: code cleanup and doc fix
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8225
diff changeset
80 - 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
81 - 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
82 parents.
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
83 """
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
84 seen = []
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
85 colors = {}
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
86 newcolor = 1
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
87 config = {}
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
88
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
89 for key, val in repo.ui.configitems('graph'):
16131
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
90 if '.' in key:
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
91 branch, setting = key.rsplit('.', 1)
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
92 # Validation
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
93 if setting == "width" and val.isdigit():
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
94 config.setdefault(branch, {})[setting] = val
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
95 elif setting == "color" and val.isalnum():
6f236c8bdc01 graphmod: rewrite graph config validation
Matt Mackall <mpm@selenic.com>
parents: 16130
diff changeset
96 config.setdefault(branch, {})[setting] = val
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
97
16132
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
98 if config:
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
99 getconf = util.lrucachefunc(lambda rev: config.get(repo[rev].branch()))
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
100 else:
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
101 getconf = lambda rev: None
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
102
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
103 for (cur, type, data, parents) in dag:
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
104
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
105 # Compute seen and next
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
106 if cur not in seen:
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
107 seen.append(cur) # new head
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
108 colors[cur] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
109 newcolor += 1
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
110
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
111 col = seen.index(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
112 color = colors.pop(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
113 next = seen[:]
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
114
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
115 # Add parents to next
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
116 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
117 next[col:col + 1] = addparents
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
118
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
119 # Set colors for the parents
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
120 for i, p in enumerate(addparents):
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
121 if not i:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
122 colors[p] = color
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
123 else:
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
124 colors[p] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
125 newcolor += 1
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
126
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
127 # Add edges to the graph
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
128 edges = []
8841
94ac080e7af9 graphmod: rename a bunch of vars in graph()
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8840
diff changeset
129 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
130 if eid in next:
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
131 edges.append((
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
132 ecol, next.index(eid), colors[eid],
16132
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
133 getconf(eid)))
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
134 elif eid == cur:
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
135 for p in parents:
16129
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
136 edges.append((
5e50982c633c graph: in hgrc specify line width for main branch
Constantine Linnick <theaspect@gmail.com>
parents: 14131
diff changeset
137 ecol, next.index(p), color,
16132
41fc1e078d68 graphmod: add config cache
Matt Mackall <mpm@selenic.com>
parents: 16131
diff changeset
138 getconf(p)))
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
139
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
140 # Yield and move on
8842
acd03a6e2426 graphmod/webcommands: use generic DAG walks
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8841
diff changeset
141 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
142 seen = next
14042
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 def grandparent(cl, lowestrev, roots, head):
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
145 """Return all ancestors of head in roots which revision is
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
146 greater or equal to lowestrev.
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
147 """
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
148 pending = set([head])
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
149 seen = set()
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
150 kept = set()
14042
9966c95b8c4f graphmod: use revsets internally
Alexander Solovyov <alexander@solovyov.net>
parents: 12951
diff changeset
151 llowestrev = max(nullrev, lowestrev)
14131
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
152 while pending:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
153 r = pending.pop()
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
154 if r >= llowestrev and r not in seen:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
155 if r in roots:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
156 kept.add(r)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
157 else:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
158 pending.update([p for p in cl.parentrevs(r)])
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
159 seen.add(r)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors
Patrick Mezard <pmezard@gmail.com>
parents: 14088
diff changeset
160 return sorted(kept)