Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/graphmod.py @ 14131:03e1c2d35c6a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
graphmod: correctly emit nodes with more than 2 predecessors The grandparent() function was returning only the closest predecessor of a missing parent while it must return all of them to display a correct ancestry graph.
author Patrick Mezard <pmezard@gmail.com>
date Sun, 01 May 2011 15:51:46 +0200
parents e83ced8b6464
children 5e50982c633c
comparison
equal deleted inserted replaced
14130:5e4ec4119485 14131:03e1c2d35c6a
43 if p.rev() in knownrevs])) 43 if p.rev() in knownrevs]))
44 mpars = [p.rev() for p in ctx.parents() if 44 mpars = [p.rev() for p in ctx.parents() if
45 p.rev() != nullrev and p.rev() not in parents] 45 p.rev() != nullrev and p.rev() not in parents]
46 46
47 for mpar in mpars: 47 for mpar in mpars:
48 gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar) 48 gp = gpcache.get(mpar)
49 gpcache[mpar] = gp
50 if gp is None: 49 if gp is None:
50 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
51 if not gp:
51 parents.append(mpar) 52 parents.append(mpar)
52 elif gp not in parents: 53 else:
53 parents.append(gp) 54 parents.extend(g for g in gp if g not in parents)
54 55
55 yield (ctx.rev(), CHANGESET, ctx, parents) 56 yield (ctx.rev(), CHANGESET, ctx, parents)
56 57
57 def nodes(repo, nodes): 58 def nodes(repo, nodes):
58 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples 59 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
117 118
118 # Yield and move on 119 # Yield and move on
119 yield (cur, type, data, (col, color), edges) 120 yield (cur, type, data, (col, color), edges)
120 seen = next 121 seen = next
121 122
122
123 def grandparent(cl, lowestrev, roots, head): 123 def grandparent(cl, lowestrev, roots, head):
124 """Return closest 'root' rev in topological path from 'roots' to 'head'. 124 """Return all ancestors of head in roots which revision is
125 125 greater or equal to lowestrev.
126 Derived from revlog.revlog.nodesbetween, but only returns next rev
127 of topologically sorted list of all nodes N that satisfy of these
128 constraints:
129
130 1. N is a descendant of some node in 'roots'
131 2. N is an ancestor of 'head'
132 3. N is some node in 'roots' or nullrev
133
134 Every node is considered to be both a descendant and an ancestor
135 of itself, so every reachable node in 'roots' and 'head' will be
136 included in 'nodes'.
137 """ 126 """
138 ancestors = set() 127 pending = set([head])
139 # Start at the top and keep marking parents until we're done. 128 seen = set()
140 revstotag = set([head]) 129 kept = set()
141 revstotag.discard(nullrev)
142 llowestrev = max(nullrev, lowestrev) 130 llowestrev = max(nullrev, lowestrev)
143 131 while pending:
144 while revstotag: 132 r = pending.pop()
145 r = revstotag.pop() 133 if r >= llowestrev and r not in seen:
146 # A node's revision number represents its place in a 134 if r in roots:
147 # topologically sorted list of nodes. 135 kept.add(r)
148 if r >= llowestrev: 136 else:
149 if r not in ancestors: 137 pending.update([p for p in cl.parentrevs(r)])
150 # If we are possibly a descendent of one of the roots 138 seen.add(r)
151 # and we haven't already been marked as an ancestor 139 return sorted(kept)
152 ancestors.add(r) # Mark as ancestor
153 # Add non-nullrev parents to list of nodes to tag.
154 revstotag.update([p for p in cl.parentrevs(r)])
155
156 if not ancestors:
157 return
158 # Now that we have our set of ancestors, we want to remove any
159 # roots that are not ancestors.
160
161 # If one of the roots was nullrev, everything is included anyway.
162 if lowestrev > nullrev:
163 # But, since we weren't, let's recompute the lowest rev to not
164 # include roots that aren't ancestors.
165
166 # Filter out roots that aren't ancestors of heads
167 _roots = ancestors.intersection(roots)
168 if not _roots:
169 return
170 # Recompute the lowest revision
171 lowestrev = min(roots)
172 else:
173 # We are descending from nullrev, and don't need to care about
174 # any other roots.
175 lowestrev = nullrev
176 _roots = [nullrev]
177
178 # The roots are just the descendants.
179 # Don't start at nullrev since we don't want nullrev in our output list,
180 # and if nullrev shows up in descedents, empty parents will look like
181 # they're descendents.
182 lowestrevisnullrev = (lowestrev == nullrev)
183 for r in xrange(head - 1, max(lowestrev, -1) - 1, -1):
184 if lowestrevisnullrev or r in _roots:
185 pass
186 elif _roots.issuperset(cl.parentrevs(r)):
187 # A node is a descendent if either of its parents are
188 # descendents. (We seeded the dependents list with the roots
189 # up there, remember?)
190 _roots.add(r)
191 else:
192 continue
193 if r in ancestors:
194 # Only include nodes that are both descendents and ancestors.
195 return r