Mercurial > kallithea

annotate rhodecode/lib/graphmod.py @ 3774:60335b702a00 beta

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
invalidation: don't create CacheInvalidation records on startup Creating the records early gave an advantage before lightweight was introduced. With lightweight it is no longer necessary. The records will be created on demand anyway and there is no reason to create and maintain them before they are used.
author Mads Kiilerich <madski@unity3d.com>
date Wed, 03 Apr 2013 15:56:12 +0200
parents 0c7dc3402efa
children ffd45b185016
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2380
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
1 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
2 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
3
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
4 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
5 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
6
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
7 nullrev = -1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
8
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
9
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
10 def grandparent(parentrev_func, lowestrev, roots, head):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
11 """
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
12 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
13 greater or equal to lowestrev.
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 pending = set([head])
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
16 seen = set()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
17 kept = set()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
18 llowestrev = max(nullrev, lowestrev)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
19 while pending:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
20 r = pending.pop()
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
21 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
22 if r in roots:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
23 kept.add(r)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
24 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
25 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
26 seen.add(r)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
27 return sorted(kept)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
28
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
29
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
30 def _dagwalker(repo, revs, alias):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
31 if not revs:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
32 return
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
33
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
34 if alias == 'hg':
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
35 cl = repo._repo.changelog.parentrevs
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
36 repo = repo
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
37 elif alias == 'git':
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
38 def cl(rev):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
39 return [x.revision for x in repo[rev].parents()]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
40 repo = repo
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 lowestrev = min(revs)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
43 gpcache = {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
44
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
45 knownrevs = set(revs)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
46 for rev in revs:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
47 ctx = repo[rev]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
48 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
49 if p.revision in knownrevs]))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
50 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
51 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
52
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
53 for mpar in mpars:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
54 gp = gpcache.get(mpar)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
55 if gp is None:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
56 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
57 if not gp:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
58 parents.append(mpar)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
59 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
60 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
61
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
62 yield (ctx.revision, 'C', ctx, parents)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
63
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
64
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
65 def _colored(dag):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
66 """annotates a DAG with colored edge information
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
67
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
68 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
69
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
70 (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
71
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
72 with the following new elements:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
73
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
74 - 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
75 - 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
76 parents.
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 seen = []
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
79 colors = {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
80 newcolor = 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
81
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
82 getconf = lambda rev: {}
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
83
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
84 for (cur, type, data, parents) in dag:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
85
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
86 # Compute seen and next
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
87 if cur not in seen:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
88 seen.append(cur) # new head
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
89 colors[cur] = newcolor
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
90 newcolor += 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
91
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
92 col = seen.index(cur)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
93 color = colors.pop(cur)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
94 next = seen[:]
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
95
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
96 # Add parents to next
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
97 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
98 next[col:col + 1] = addparents
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
99
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
100 # Set colors for the parents
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
101 for i, p in enumerate(addparents):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
102 if not i:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
103 colors[p] = color
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
104 else:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
105 colors[p] = newcolor
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
106 newcolor += 1
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
107
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
108 # Add edges to the graph
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
109 edges = []
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
110 for ecol, eid in enumerate(seen):
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
111 if eid in next:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
112 bconf = getconf(eid)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
113 edges.append((
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
114 ecol, next.index(eid), colors[eid],
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
115 bconf.get('width', -1),
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
116 bconf.get('color', '')))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
117 elif eid == cur:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
118 for p in parents:
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
119 bconf = getconf(p)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
120 edges.append((
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
121 ecol, next.index(p), color,
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
122 bconf.get('width', -1),
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
123 bconf.get('color', '')))
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
124
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
125 # Yield and move on
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
126 yield (cur, type, data, (col, color), edges)
0c7dc3402efa Unified DAG generation for hg and git
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
127 seen = next