Mercurial > kallithea

annotate rhodecode/lib/graphmod.py @ 4147:1c8f818787b3 rhodecode-2.2.5-gpl

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
old style: show the full link box on summary page - no overlap or truncation
author Mads Kiilerich <madski@unity3d.com>
date Wed, 02 Jul 2014 19:03:23 -0400
parents ffd45b185016
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4116
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
1 # -*- coding: utf-8 -*-
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
2 # This program is free software: you can redistribute it and/or modify
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
3 # it under the terms of the GNU General Public License as published by
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
4 # the Free Software Foundation, either version 3 of the License, or
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
5 # (at your option) any later version.
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
6 #
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
7 # This program is distributed in the hope that it will be useful,
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
8 # but WITHOUT ANY WARRANTY; without even the implied warranty of
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
9 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
10 # GNU General Public License for more details.
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
11 #
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
12 # You should have received a copy of the GNU General Public License
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
13 # along with this program. If not, see <http://www.gnu.org/licenses/>.
2380
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
14 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
15 Modified mercurial DAG graph functions that re-uses VCS structure
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
16
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
17 It allows to have a shared codebase for DAG generation for hg and git repos
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
18 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
19
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
20 nullrev = -1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
21
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
22
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
23 def grandparent(parentrev_func, lowestrev, roots, head):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
24 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
25 Return all ancestors of head in roots which revision is
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
26 greater or equal to lowestrev.
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
27 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
28 pending = set([head])
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
29 seen = set()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
30 kept = set()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
31 llowestrev = max(nullrev, lowestrev)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
32 while pending:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
33 r = pending.pop()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
34 if r >= llowestrev and r not in seen:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
35 if r in roots:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
36 kept.add(r)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
37 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
38 pending.update([p for p in parentrev_func(r)])
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
39 seen.add(r)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
40 return sorted(kept)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
41
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
42
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
43 def _dagwalker(repo, revs, alias):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
44 if not revs:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
45 return
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
46
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
47 if alias == 'hg':
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
48 cl = repo._repo.changelog.parentrevs
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
49 repo = repo
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
50 elif alias == 'git':
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
51 def cl(rev):
4116
ffd45b185016 Imported some of the GPLv3'd changes from RhodeCode v2.2.5.
Bradley M. Kuhn <bkuhn@sfconservancy.org>
parents: 2380
diff changeset
52 return [x.revision for x in repo[rev].parents]
2380
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
53 repo = repo
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
54
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
55 lowestrev = min(revs)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
56 gpcache = {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
57
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
58 knownrevs = set(revs)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
59 for rev in revs:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
60 ctx = repo[rev]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
61 parents = sorted(set([p.revision for p in ctx.parents
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
62 if p.revision in knownrevs]))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
63 mpars = [p.revision for p in ctx.parents if
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
64 p.revision != nullrev and p.revision not in parents]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
65
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
66 for mpar in mpars:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
67 gp = gpcache.get(mpar)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
68 if gp is None:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
69 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
70 if not gp:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
71 parents.append(mpar)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
72 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
73 parents.extend(g for g in gp if g not in parents)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
74
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
75 yield (ctx.revision, 'C', ctx, parents)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
76
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
77
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
78 def _colored(dag):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
79 """annotates a DAG with colored edge information
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
80
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
81 For each DAG node this function emits tuples::
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
82
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
83 (id, type, data, (col, color), [(col, nextcol, color)])
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
84
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
85 with the following new elements:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
86
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
87 - Tuple (col, color) with column and color index for the current node
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
88 - A list of tuples indicating the edges between the current node and its
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
89 parents.
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
90 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
91 seen = []
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
92 colors = {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
93 newcolor = 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
94
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
95 getconf = lambda rev: {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
96
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
97 for (cur, type, data, parents) in dag:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
98
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
99 # Compute seen and next
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
100 if cur not in seen:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
101 seen.append(cur) # new head
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
102 colors[cur] = newcolor
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
103 newcolor += 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
104
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
105 col = seen.index(cur)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
106 color = colors.pop(cur)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
107 next = seen[:]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
108
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
109 # Add parents to next
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
110 addparents = [p for p in parents if p not in next]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
111 next[col:col + 1] = addparents
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
112
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
113 # Set colors for the parents
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
114 for i, p in enumerate(addparents):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
115 if not i:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
116 colors[p] = color
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
117 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
118 colors[p] = newcolor
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
119 newcolor += 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
120
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
121 # Add edges to the graph
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
122 edges = []
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
123 for ecol, eid in enumerate(seen):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
124 if eid in next:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
125 bconf = getconf(eid)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
126 edges.append((
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
127 ecol, next.index(eid), colors[eid],
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
128 bconf.get('width', -1),
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
129 bconf.get('color', '')))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
130 elif eid == cur:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
131 for p in parents:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
132 bconf = getconf(p)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
133 edges.append((
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
134 ecol, next.index(p), color,
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
135 bconf.get('width', -1),
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
136 bconf.get('color', '')))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
137
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
138 # Yield and move on
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
139 yield (cur, type, data, (col, color), edges)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
140 seen = next