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 |
|