##// END OF EJS Templates
ancestor: add lazy membership testing to lazyancestors...
Siddharth Agarwal -
r18091:f7f8159c default
parent child Browse files
Show More
@@ -82,7 +82,7 b' def perfancestorset(ui, repo, revset):'
82 revs = repo.revs(revset)
82 revs = repo.revs(revset)
83 heads = repo.changelog.headrevs()
83 heads = repo.changelog.headrevs()
84 def d():
84 def d():
85 s = set(repo.changelog.ancestors(heads))
85 s = repo.changelog.ancestors(heads)
86 for rev in revs:
86 for rev in revs:
87 rev in s
87 rev in s
88 timer(d)
88 timer(d)
@@ -177,8 +177,8 b' class lazyancestors(object):'
177 """Create a new object generating ancestors for the given revs. Does
177 """Create a new object generating ancestors for the given revs. Does
178 not generate revs lower than stoprev.
178 not generate revs lower than stoprev.
179
179
180 This is computed lazily starting from revs. The object only supports
180 This is computed lazily starting from revs. The object supports
181 iteration.
181 iteration and membership.
182
182
183 cl should be a changelog and revs should be an iterable. inclusive is
183 cl should be a changelog and revs should be an iterable. inclusive is
184 a boolean that indicates whether revs should be included. Revs lower
184 a boolean that indicates whether revs should be included. Revs lower
@@ -190,6 +190,19 b' class lazyancestors(object):'
190 self._stoprev = stoprev
190 self._stoprev = stoprev
191 self._inclusive = inclusive
191 self._inclusive = inclusive
192
192
193 # Initialize data structures for __contains__.
194 # For __contains__, we use a heap rather than a deque because
195 # (a) it minimizes the number of parentrevs calls made
196 # (b) it makes the loop termination condition obvious
197 # Python's heap is a min-heap. Multiply all values by -1 to convert it
198 # into a max-heap.
199 self._containsvisit = [-rev for rev in revs]
200 heapq.heapify(self._containsvisit)
201 if inclusive:
202 self._containsseen = set(revs)
203 else:
204 self._containsseen = set()
205
193 def __iter__(self):
206 def __iter__(self):
194 """Generate the ancestors of _initrevs in reverse topological order.
207 """Generate the ancestors of _initrevs in reverse topological order.
195
208
@@ -219,3 +232,33 b' class lazyancestors(object):'
219 visit.append(parent)
232 visit.append(parent)
220 seen.add(parent)
233 seen.add(parent)
221 yield parent
234 yield parent
235
236 def __contains__(self, target):
237 """Test whether target is an ancestor of self._initrevs."""
238 # Trying to do both __iter__ and __contains__ using the same visit
239 # heap and seen set is complex enough that it slows down both. Keep
240 # them separate.
241 seen = self._containsseen
242 if target in seen:
243 return True
244
245 parentrevs = self._parentrevs
246 visit = self._containsvisit
247 stoprev = self._stoprev
248 heappop = heapq.heappop
249 heappush = heapq.heappush
250
251 targetseen = False
252
253 while visit and -visit[0] > target and not targetseen:
254 for parent in parentrevs(-heappop(visit)):
255 if parent < stoprev or parent in seen:
256 continue
257 # We need to make sure we push all parents into the heap so
258 # that we leave it in a consistent state for future calls.
259 heappush(visit, -parent)
260 seen.add(parent)
261 if parent == target:
262 targetseen = True
263
264 return targetseen
@@ -34,6 +34,9 b' graph = {0: [-1], 1: [0], 2: [1], 3: [1]'
34 13: [8]}
34 13: [8]}
35 pfunc = graph.get
35 pfunc = graph.get
36
36
37 class mockchangelog(object):
38 parentrevs = graph.get
39
37 def runmissingancestors(revs, bases):
40 def runmissingancestors(revs, bases):
38 print "%% ancestors of %s and not of %s" % (revs, bases)
41 print "%% ancestors of %s and not of %s" % (revs, bases)
39 print ancestor.missingancestors(revs, bases, pfunc)
42 print ancestor.missingancestors(revs, bases, pfunc)
@@ -70,5 +73,34 b' def test_missingancestors():'
70 runmissingancestors([10, 11, 12], [13])
73 runmissingancestors([10, 11, 12], [13])
71 runmissingancestors([13], [10, 11, 12])
74 runmissingancestors([13], [10, 11, 12])
72
75
76 def genlazyancestors(revs, stoprev=0, inclusive=False):
77 print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
78 (revs, stoprev, inclusive))
79 return ancestor.lazyancestors(mockchangelog, revs, stoprev=stoprev,
80 inclusive=inclusive)
81
82 def printlazyancestors(s, l):
83 print [n for n in l if n in s]
84
85 def test_lazyancestors():
86 # Empty revs
87 s = genlazyancestors([])
88 printlazyancestors(s, [3, 0, -1])
89
90 # Standard example
91 s = genlazyancestors([11, 13])
92 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
93
94 # Including revs
95 s = genlazyancestors([11, 13], inclusive=True)
96 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
97
98 # Test with stoprev
99 s = genlazyancestors([11, 13], stoprev=6)
100 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
101 s = genlazyancestors([11, 13], stoprev=6, inclusive=True)
102 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
103
73 if __name__ == '__main__':
104 if __name__ == '__main__':
74 test_missingancestors()
105 test_missingancestors()
106 test_lazyancestors()
@@ -34,3 +34,13 b''
34 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]
34 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]
35 % ancestors of [13] and not of [10, 11, 12]
35 % ancestors of [13] and not of [10, 11, 12]
36 [8, 13]
36 [8, 13]
37 % lazy ancestor set for [], stoprev = 0, inclusive = False
38 []
39 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = False
40 [7, 8, 3, 4, 1, 0]
41 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = True
42 [11, 13, 7, 8, 3, 4, 1, 0]
43 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = False
44 [7, 8]
45 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = True
46 [11, 13, 7, 8]
General Comments 0
You need to be logged in to leave comments. Login now