Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/graphmod.py @ 14042:9966c95b8c4f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
graphmod: use revsets internally Thanks for the idea and most of the implementation to Klaus Koch Backs revisions() and filerevs() with DAG walker which can iterate through arbitrary list of revisions instead of strict one by one iteration from start to stop. When a gap occurs in a revisions (i.e. in file log), the next topological parent within the revset is searched and the connection to it is printed in the ascii graph. File graph can draw sometimes more connections than previous version, because graph is produced according to the revset, not according to a file's filelog. In case the graph contains several branches where the left parent is null, the graphs for each are printed sequentially, not in parallel as it was a case earlier (see for example the graph for README in hg-dev).
author Alexander Solovyov <alexander@solovyov.net>
date Sun, 13 Mar 2011 15:53:38 +0100
parents 101366ad816c
children 1c1e1232abdc
comparison
equal deleted inserted replaced
14041:bcc6ed0f6c3b 14042:9966c95b8c4f
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 from mercurial.cmdutil import revrange
21 22
22 CHANGESET = 'C' 23 CHANGESET = 'C'
23 24
24 def revisions(repo, start, stop): 25 def revisions(repo, start, end):
26 """DAG generator for revisions between start and end
27 """
28 revset = '%s:%s' % (start, end)
29 return dagwalker(repo, revrange(repo, [revset]))
30
31 def filerevs(repo, path, start, stop, limit=None):
32 """DAG generator, which is limited by file passed
33 """
34 revset = '%s:%s and file("%s")' % (start, stop, path)
35 if limit:
36 revset = 'limit(%s, %s)' % (revset, limit)
37 return dagwalker(repo, revrange(repo, [revset]))
38
39 def dagwalker(repo, revs):
25 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples 40 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
26 41
27 This generator function walks through the revision history from revision 42 This generator function walks through revisions (which should be ordered
28 start to revision stop (which must be less than or equal to start). It 43 from bigger to lower). It returns a tuple for each node. The node and parent
29 returns a tuple for each node. The node and parent ids are arbitrary 44 ids are arbitrary integers which identify a node in the context of the graph
30 integers which identify a node in the context of the graph returned. 45 returned.
31 """ 46 """
32 cur = start 47 if not revs:
33 while cur >= stop: 48 return []
34 ctx = repo[cur] 49
35 parents = set([p.rev() for p in ctx.parents() if p.rev() != nullrev]) 50 ns = [repo[r].node() for r in revs]
36 yield (cur, CHANGESET, ctx, sorted(parents)) 51 revdag = list(nodes(repo, ns))
37 cur -= 1 52
38 53 cl = repo.changelog
39 def filerevs(repo, path, start, stop, limit=None): 54 lowestrev = min(revs)
40 """file cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples 55 gpcache = {}
41 56 leafs = {}
42 This generator function walks through the revision history of a single 57
43 file from revision start down to revision stop. 58 for i, (id, c, ctx, parents) in enumerate(revdag):
44 """ 59 mpars = [p.rev() for p in ctx.parents() if
45 filerev = len(repo.file(path)) - 1 60 p.rev() != nullrev and p.rev() not in parents]
46 rev = stop + 1 61 grandparents = []
47 count = 0 62
48 while filerev >= 0 and rev > stop: 63 for mpar in mpars:
49 fctx = repo.filectx(path, fileid=filerev) 64 gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar)
50 parents = set([f.linkrev() for f in fctx.parents() if f.path() == path]) 65 gpcache[mpar] = gp
51 rev = fctx.rev() 66 if gp is None:
52 if rev <= start: 67 leafs.setdefault(mpar, []).append((i, ctx))
53 yield (rev, CHANGESET, fctx.changectx(), sorted(parents)) 68 else:
54 count += 1 69 grandparents.append(gp)
55 if count == limit: 70
56 break 71 if grandparents:
57 filerev -= 1 72 for gp in grandparents:
73 if gp not in revdag[i][3]:
74 revdag[i][3].append(gp)
75
76 for parent, leafs in leafs.iteritems():
77 for i, ctx in leafs:
78 revdag[i][3].append(parent)
79
80 return revdag
58 81
59 def nodes(repo, nodes): 82 def nodes(repo, nodes):
60 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples 83 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
61 84
62 This generator function walks the given nodes. It only returns parents 85 This generator function walks the given nodes. It only returns parents
118 edges.append((ecol, next.index(p), color)) 141 edges.append((ecol, next.index(p), color))
119 142
120 # Yield and move on 143 # Yield and move on
121 yield (cur, type, data, (col, color), edges) 144 yield (cur, type, data, (col, color), edges)
122 seen = next 145 seen = next
146
147
148 def grandparent(cl, lowestrev, roots, head):
149 """Return closest 'root' rev in topological path from 'roots' to 'head'.
150
151 Derived from revlog.revlog.nodesbetween, but only returns next rev
152 of topologically sorted list of all nodes N that satisfy of these
153 constraints:
154
155 1. N is a descendant of some node in 'roots'
156 2. N is an ancestor of 'head'
157 3. N is some node in 'roots' or nullrev
158
159 Every node is considered to be both a descendant and an ancestor
160 of itself, so every reachable node in 'roots' and 'head' will be
161 included in 'nodes'.
162 """
163 ancestors = set()
164 # Start at the top and keep marking parents until we're done.
165 revstotag = set([head])
166 revstotag.discard(nullrev)
167 llowestrev = max(nullrev, lowestrev)
168
169 while revstotag:
170 r = revstotag.pop()
171 # A node's revision number represents its place in a
172 # topologically sorted list of nodes.
173 if r >= llowestrev:
174 if r not in ancestors:
175 # If we are possibly a descendent of one of the roots
176 # and we haven't already been marked as an ancestor
177 ancestors.add(r) # Mark as ancestor
178 # Add non-nullrev parents to list of nodes to tag.
179 revstotag.update([p for p in cl.parentrevs(r)])
180
181 if not ancestors:
182 return
183 # Now that we have our set of ancestors, we want to remove any
184 # roots that are not ancestors.
185
186 # If one of the roots was nullrev, everything is included anyway.
187 if lowestrev > nullrev:
188 # But, since we weren't, let's recompute the lowest rev to not
189 # include roots that aren't ancestors.
190
191 # Filter out roots that aren't ancestors of heads
192 _roots = ancestors.intersection(roots)
193 if not _roots:
194 return
195 # Recompute the lowest revision
196 lowestrev = min(roots)
197 else:
198 # We are descending from nullrev, and don't need to care about
199 # any other roots.
200 lowestrev = nullrev
201 _roots = [nullrev]
202
203 # The roots are just the descendants.
204 # Don't start at nullrev since we don't want nullrev in our output list,
205 # and if nullrev shows up in descedents, empty parents will look like
206 # they're descendents.
207 lowestrevisnullrev = (lowestrev == nullrev)
208 for r in xrange(head - 1, max(lowestrev, -1) - 1, -1):
209 if lowestrevisnullrev or r in _roots:
210 pass
211 elif _roots.issuperset(cl.parentrevs(r)):
212 # A node is a descendent if either of its parents are
213 # descendents. (We seeded the dependents list with the roots
214 # up there, remember?)
215 _roots.add(r)
216 else:
217 continue
218 if r in ancestors:
219 # Only include nodes that are both descendents and ancestors.
220 return r