Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/graphmod.py @ 8836:11ff34956ee7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
graphmod/graphlog: move log walks to graphmod
author Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
date Fri, 19 Jun 2009 13:14:01 +0200
parents ec5483efc31f
children d8e3a98018cb
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
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7873
diff changeset
7 # GNU General Public License version 2, incorporated herein by reference.
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
8
7873
4a4c7f6a5912 cleanup: drop unused imports
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 7565
diff changeset
9 from node import nullrev
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
10
8836
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
11 def revisions(repo, start, stop):
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
12 """cset DAG generator yielding (rev, node, [parents]) tuples
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
13
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
14 This generator function walks through the revision history from revision
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
15 start to revision stop (which must be less than or equal to start).
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
16 """
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
17 assert start >= stop
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
18 cur = start
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
19 while cur >= stop:
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
20 ctx = repo[cur]
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
21 parents = [p.rev() for p in ctx.parents() if p.rev() != nullrev]
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
22 parents.sort()
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
23 yield (ctx, parents)
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
24 cur -= 1
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
25
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
26 def filerevs(repo, path, start, stop):
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
27 """file cset DAG generator yielding (rev, node, [parents]) tuples
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
28
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
29 This generator function walks through the revision history of a single
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
30 file from revision start to revision stop (which must be less than or
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
31 equal to start).
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
32 """
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
33 assert start >= stop
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
34 filerev = len(repo.file(path)) - 1
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
35 while filerev >= 0:
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
36 fctx = repo.filectx(path, fileid=filerev)
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
37 parents = [f.linkrev() for f in fctx.parents() if f.path() == path]
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
38 parents.sort()
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
39 if fctx.rev() <= start:
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
40 yield (fctx, parents)
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
41 if fctx.rev() <= stop:
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
42 break
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
43 filerev -= 1
11ff34956ee7 graphmod/graphlog: move log walks to graphmod
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8835
diff changeset
44
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
45 def graph(repo, start_rev, stop_rev):
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
46 """incremental revision grapher
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
47
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
48 This generator function walks through the revision history from
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
49 revision start_rev to revision stop_rev (which must be less than
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
50 or equal to start_rev) and for each revision emits tuples with the
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
51 following elements:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
52
8835
ec5483efc31f graphmod: code cleanup and doc fix
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8225
diff changeset
53 - Context of the current node
ec5483efc31f graphmod: code cleanup and doc fix
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 8225
diff changeset
54 - Tuple (col, color) with column and color index for the current node
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
55 - Edges; a list of (col, next_col, color) indicating the edges between
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
56 the current node and its parents.
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
57 """
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
58
7565
5f162f61e479 hgweb: fix problems with empty repositories
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 7280
diff changeset
59 if start_rev == nullrev and not stop_rev:
5f162f61e479 hgweb: fix problems with empty repositories
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 7280
diff changeset
60 return
5f162f61e479 hgweb: fix problems with empty repositories
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 7280
diff changeset
61
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
62 assert start_rev >= stop_rev
7030
20a5dd5d6dd9 hgweb: let the web graph cope with low revisions/new repositories (issue1293)
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 6747
diff changeset
63 assert stop_rev >= 0
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
64 curr_rev = start_rev
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
65 revs = []
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
66 cl = repo.changelog
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
67 colors = {}
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
68 new_color = 1
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
69
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
70 while curr_rev >= stop_rev:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
71 # Compute revs and next_revs
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
72 if curr_rev not in revs:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
73 revs.append(curr_rev) # new head
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
74 colors[curr_rev] = new_color
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
75 new_color += 1
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
76
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
77 idx = revs.index(curr_rev)
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
78 color = colors.pop(curr_rev)
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
79 next = revs[:]
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
80
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
81 # Add parents to next_revs
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
82 parents = [x for x in cl.parentrevs(curr_rev) if x != nullrev]
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
83 addparents = [p for p in parents if p not in next]
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
84 next[idx:idx + 1] = addparents
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
85
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
86 # Set colors for the parents
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
87 for i, p in enumerate(addparents):
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
88 if not i:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
89 colors[p] = color
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
90 else:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
91 colors[p] = new_color
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
92 new_color += 1
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
93
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
94 # Add edges to the graph
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
95 edges = []
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
96 for col, r in enumerate(revs):
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
97 if r in next:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
98 edges.append((col, next.index(r), colors[r]))
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
99 elif r == curr_rev:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
100 for p in parents:
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
101 edges.append((col, next.index(p), colors[p]))
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
102
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
103 # Yield and move on
6747
f6c00b17387c use repo[changeid] to get a changectx
Matt Mackall <mpm@selenic.com>
parents: 6691
diff changeset
104 yield (repo[curr_rev], (idx, color), edges)
6691
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
105 revs = next
0dba955c2636 add graph page to hgweb
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents:
diff changeset
106 curr_rev -= 1