Mercurial > hg
comparison mercurial/ancestor.py @ 23334:59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
This allows multiple efficient missing ancestor queries against the same set of
bases. In upcoming patches we'll also define ways to grow the set of bases.
The fact that the test output hasn't changed establishes this patch's
correctness.
author | Siddharth Agarwal <sid0@fb.com> |
---|---|
date | Fri, 14 Nov 2014 23:44:38 -0800 |
parents | 9a2489015592 |
children | 5c3a29be8fae |
comparison
equal
deleted
inserted
replaced
23333:9a2489015592 | 23334:59e6e5dd3605 |
---|---|
132 | 132 |
133 if len(gca) <= 1: | 133 if len(gca) <= 1: |
134 return gca | 134 return gca |
135 return deepest(gca) | 135 return deepest(gca) |
136 | 136 |
137 class incrementalmissingancestors(object): | |
138 '''persistent state used to calculate missing ancestors incrementally | |
139 | |
140 Although similar in spirit to lazyancestors below, this is a separate class | |
141 because trying to support contains and missingancestors operations with the | |
142 same internal data structures adds needless complexity.''' | |
143 def __init__(self, pfunc, bases): | |
144 self.bases = set(bases) | |
145 if not self.bases: | |
146 self.bases.add(nullrev) | |
147 self.pfunc = pfunc | |
148 | |
149 def missingancestors(self, revs): | |
150 '''return all the ancestors of revs that are not ancestors of self.bases | |
151 | |
152 This may include elements from revs. | |
153 | |
154 Equivalent to the revset (::revs - ::self.bases). Revs are returned in | |
155 revision number order, which is a topological order.''' | |
156 revsvisit = set(revs) | |
157 basesvisit = self.bases | |
158 pfunc = self.pfunc | |
159 bothvisit = revsvisit.intersection(basesvisit) | |
160 revsvisit.difference_update(bothvisit) | |
161 if not revsvisit: | |
162 return [] | |
163 | |
164 start = max(max(revsvisit), max(basesvisit)) | |
165 # At this point, we hold the invariants that: | |
166 # - revsvisit is the set of nodes we know are an ancestor of at least | |
167 # one of the nodes in revs | |
168 # - basesvisit is the same for bases | |
169 # - bothvisit is the set of nodes we know are ancestors of at least one | |
170 # of the nodes in revs and one of the nodes in bases. bothvisit and | |
171 # revsvisit are mutually exclusive, but bothvisit is a subset of | |
172 # basesvisit. | |
173 # Now we walk down in reverse topo order, adding parents of nodes | |
174 # already visited to the sets while maintaining the invariants. When a | |
175 # node is found in both revsvisit and basesvisit, it is removed from | |
176 # revsvisit and added to bothvisit. When revsvisit becomes empty, there | |
177 # are no more ancestors of revs that aren't also ancestors of bases, so | |
178 # exit. | |
179 | |
180 missing = [] | |
181 for curr in xrange(start, nullrev, -1): | |
182 if not revsvisit: | |
183 break | |
184 | |
185 if curr in bothvisit: | |
186 bothvisit.remove(curr) | |
187 # curr's parents might have made it into revsvisit through | |
188 # another path | |
189 for p in pfunc(curr): | |
190 revsvisit.discard(p) | |
191 basesvisit.add(p) | |
192 bothvisit.add(p) | |
193 continue | |
194 | |
195 if curr in revsvisit: | |
196 missing.append(curr) | |
197 revsvisit.remove(curr) | |
198 thisvisit = revsvisit | |
199 othervisit = basesvisit | |
200 elif curr in basesvisit: | |
201 thisvisit = basesvisit | |
202 othervisit = revsvisit | |
203 else: | |
204 # not an ancestor of revs or bases: ignore | |
205 continue | |
206 | |
207 for p in pfunc(curr): | |
208 if p == nullrev: | |
209 pass | |
210 elif p in othervisit or p in bothvisit: | |
211 # p is implicitly in thisvisit. This means p is or should be | |
212 # in bothvisit | |
213 revsvisit.discard(p) | |
214 basesvisit.add(p) | |
215 bothvisit.add(p) | |
216 else: | |
217 # visit later | |
218 thisvisit.add(p) | |
219 | |
220 missing.reverse() | |
221 return missing | |
222 | |
137 def missingancestors(revs, bases, pfunc): | 223 def missingancestors(revs, bases, pfunc): |
138 """Return all the ancestors of revs that are not ancestors of bases. | 224 inc = incrementalmissingancestors(pfunc, bases) |
139 | 225 return inc.missingancestors(revs) |
140 This may include elements from revs. | |
141 | |
142 Equivalent to the revset (::revs - ::bases). Revs are returned in | |
143 revision number order, which is a topological order. | |
144 | |
145 revs and bases should both be iterables. pfunc must return a list of | |
146 parent revs for a given revs. | |
147 """ | |
148 | |
149 revsvisit = set(revs) | |
150 basesvisit = set(bases) | |
151 if not basesvisit: | |
152 basesvisit.add(nullrev) | |
153 bothvisit = revsvisit.intersection(basesvisit) | |
154 revsvisit.difference_update(bothvisit) | |
155 if not revsvisit: | |
156 return [] | |
157 start = max(max(revsvisit), max(basesvisit)) | |
158 # At this point, we hold the invariants that: | |
159 # - revsvisit is the set of nodes we know are an ancestor of at least one | |
160 # of the nodes in revs | |
161 # - basesvisit is the same for bases | |
162 # - bothvisit is the set of nodes we know are ancestors of at least one of | |
163 # the nodes in revs and one of the nodes in bases, and that are smaller | |
164 # than curr. bothvisit and revsvisit are mutually exclusive, but bothvisit | |
165 # is a subset of basesvisit. | |
166 # Now we walk down in reverse topo order, adding parents of nodes already | |
167 # visited to the sets while maintaining the invariants. When a node is found | |
168 # in both revsvisit and basesvisit, it is removed from revsvisit and added | |
169 # to bothvisit. When revsvisit becomes empty, there are no more ancestors of | |
170 # revs that aren't also ancestors of bases, so exit. | |
171 | |
172 missing = [] | |
173 for curr in xrange(start, nullrev, -1): | |
174 if not revsvisit: | |
175 break | |
176 | |
177 if curr in bothvisit: | |
178 bothvisit.remove(curr) | |
179 # curr's parents might have made it into revsvisit through another | |
180 # path | |
181 for p in pfunc(curr): | |
182 revsvisit.discard(p) | |
183 basesvisit.add(p) | |
184 bothvisit.add(p) | |
185 continue | |
186 | |
187 if curr in revsvisit: | |
188 missing.append(curr) | |
189 revsvisit.remove(curr) | |
190 thisvisit = revsvisit | |
191 othervisit = basesvisit | |
192 elif curr in basesvisit: | |
193 thisvisit = basesvisit | |
194 othervisit = revsvisit | |
195 else: | |
196 # not an ancestor of revs or bases: ignore | |
197 continue | |
198 | |
199 for p in pfunc(curr): | |
200 if p == nullrev: | |
201 pass | |
202 elif p in othervisit or p in bothvisit: | |
203 # p is implicitly in thisvisit. This means p is or should be | |
204 # in bothvisit | |
205 revsvisit.discard(p) | |
206 basesvisit.add(p) | |
207 bothvisit.add(p) | |
208 else: | |
209 # visit later | |
210 thisvisit.add(p) | |
211 | |
212 missing.reverse() | |
213 return missing | |
214 | 226 |
215 class lazyancestors(object): | 227 class lazyancestors(object): |
216 def __init__(self, pfunc, revs, stoprev=0, inclusive=False): | 228 def __init__(self, pfunc, revs, stoprev=0, inclusive=False): |
217 """Create a new object generating ancestors for the given revs. Does | 229 """Create a new object generating ancestors for the given revs. Does |
218 not generate revs lower than stoprev. | 230 not generate revs lower than stoprev. |