Mercurial > hg
comparison mercurial/graphmod.py @ 14131:03e1c2d35c6a
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 |