##// END OF EJS Templates
py3: catch StopIteration from next() in generatorset...
Martin von Zweigbergk -
r32977:27ba0d8d default
parent child Browse files
Show More
@@ -1,1117 +1,1120 b''
1 # smartset.py - data structure for revision set
1 # smartset.py - data structure for revision set
2 #
2 #
3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
4 #
4 #
5 # This software may be used and distributed according to the terms of the
5 # This software may be used and distributed according to the terms of the
6 # GNU General Public License version 2 or any later version.
6 # GNU General Public License version 2 or any later version.
7
7
8 from __future__ import absolute_import
8 from __future__ import absolute_import
9
9
10 from . import (
10 from . import (
11 error,
11 error,
12 util,
12 util,
13 )
13 )
14
14
15 def _formatsetrepr(r):
15 def _formatsetrepr(r):
16 """Format an optional printable representation of a set
16 """Format an optional printable representation of a set
17
17
18 ======== =================================
18 ======== =================================
19 type(r) example
19 type(r) example
20 ======== =================================
20 ======== =================================
21 tuple ('<not %r>', other)
21 tuple ('<not %r>', other)
22 str '<branch closed>'
22 str '<branch closed>'
23 callable lambda: '<branch %r>' % sorted(b)
23 callable lambda: '<branch %r>' % sorted(b)
24 object other
24 object other
25 ======== =================================
25 ======== =================================
26 """
26 """
27 if r is None:
27 if r is None:
28 return ''
28 return ''
29 elif isinstance(r, tuple):
29 elif isinstance(r, tuple):
30 return r[0] % r[1:]
30 return r[0] % r[1:]
31 elif isinstance(r, str):
31 elif isinstance(r, str):
32 return r
32 return r
33 elif callable(r):
33 elif callable(r):
34 return r()
34 return r()
35 else:
35 else:
36 return repr(r)
36 return repr(r)
37
37
38 class abstractsmartset(object):
38 class abstractsmartset(object):
39
39
40 def __nonzero__(self):
40 def __nonzero__(self):
41 """True if the smartset is not empty"""
41 """True if the smartset is not empty"""
42 raise NotImplementedError()
42 raise NotImplementedError()
43
43
44 __bool__ = __nonzero__
44 __bool__ = __nonzero__
45
45
46 def __contains__(self, rev):
46 def __contains__(self, rev):
47 """provide fast membership testing"""
47 """provide fast membership testing"""
48 raise NotImplementedError()
48 raise NotImplementedError()
49
49
50 def __iter__(self):
50 def __iter__(self):
51 """iterate the set in the order it is supposed to be iterated"""
51 """iterate the set in the order it is supposed to be iterated"""
52 raise NotImplementedError()
52 raise NotImplementedError()
53
53
54 # Attributes containing a function to perform a fast iteration in a given
54 # Attributes containing a function to perform a fast iteration in a given
55 # direction. A smartset can have none, one, or both defined.
55 # direction. A smartset can have none, one, or both defined.
56 #
56 #
57 # Default value is None instead of a function returning None to avoid
57 # Default value is None instead of a function returning None to avoid
58 # initializing an iterator just for testing if a fast method exists.
58 # initializing an iterator just for testing if a fast method exists.
59 fastasc = None
59 fastasc = None
60 fastdesc = None
60 fastdesc = None
61
61
62 def isascending(self):
62 def isascending(self):
63 """True if the set will iterate in ascending order"""
63 """True if the set will iterate in ascending order"""
64 raise NotImplementedError()
64 raise NotImplementedError()
65
65
66 def isdescending(self):
66 def isdescending(self):
67 """True if the set will iterate in descending order"""
67 """True if the set will iterate in descending order"""
68 raise NotImplementedError()
68 raise NotImplementedError()
69
69
70 def istopo(self):
70 def istopo(self):
71 """True if the set will iterate in topographical order"""
71 """True if the set will iterate in topographical order"""
72 raise NotImplementedError()
72 raise NotImplementedError()
73
73
74 def min(self):
74 def min(self):
75 """return the minimum element in the set"""
75 """return the minimum element in the set"""
76 if self.fastasc is None:
76 if self.fastasc is None:
77 v = min(self)
77 v = min(self)
78 else:
78 else:
79 for v in self.fastasc():
79 for v in self.fastasc():
80 break
80 break
81 else:
81 else:
82 raise ValueError('arg is an empty sequence')
82 raise ValueError('arg is an empty sequence')
83 self.min = lambda: v
83 self.min = lambda: v
84 return v
84 return v
85
85
86 def max(self):
86 def max(self):
87 """return the maximum element in the set"""
87 """return the maximum element in the set"""
88 if self.fastdesc is None:
88 if self.fastdesc is None:
89 return max(self)
89 return max(self)
90 else:
90 else:
91 for v in self.fastdesc():
91 for v in self.fastdesc():
92 break
92 break
93 else:
93 else:
94 raise ValueError('arg is an empty sequence')
94 raise ValueError('arg is an empty sequence')
95 self.max = lambda: v
95 self.max = lambda: v
96 return v
96 return v
97
97
98 def first(self):
98 def first(self):
99 """return the first element in the set (user iteration perspective)
99 """return the first element in the set (user iteration perspective)
100
100
101 Return None if the set is empty"""
101 Return None if the set is empty"""
102 raise NotImplementedError()
102 raise NotImplementedError()
103
103
104 def last(self):
104 def last(self):
105 """return the last element in the set (user iteration perspective)
105 """return the last element in the set (user iteration perspective)
106
106
107 Return None if the set is empty"""
107 Return None if the set is empty"""
108 raise NotImplementedError()
108 raise NotImplementedError()
109
109
110 def __len__(self):
110 def __len__(self):
111 """return the length of the smartsets
111 """return the length of the smartsets
112
112
113 This can be expensive on smartset that could be lazy otherwise."""
113 This can be expensive on smartset that could be lazy otherwise."""
114 raise NotImplementedError()
114 raise NotImplementedError()
115
115
116 def reverse(self):
116 def reverse(self):
117 """reverse the expected iteration order"""
117 """reverse the expected iteration order"""
118 raise NotImplementedError()
118 raise NotImplementedError()
119
119
120 def sort(self, reverse=True):
120 def sort(self, reverse=True):
121 """get the set to iterate in an ascending or descending order"""
121 """get the set to iterate in an ascending or descending order"""
122 raise NotImplementedError()
122 raise NotImplementedError()
123
123
124 def __and__(self, other):
124 def __and__(self, other):
125 """Returns a new object with the intersection of the two collections.
125 """Returns a new object with the intersection of the two collections.
126
126
127 This is part of the mandatory API for smartset."""
127 This is part of the mandatory API for smartset."""
128 if isinstance(other, fullreposet):
128 if isinstance(other, fullreposet):
129 return self
129 return self
130 return self.filter(other.__contains__, condrepr=other, cache=False)
130 return self.filter(other.__contains__, condrepr=other, cache=False)
131
131
132 def __add__(self, other):
132 def __add__(self, other):
133 """Returns a new object with the union of the two collections.
133 """Returns a new object with the union of the two collections.
134
134
135 This is part of the mandatory API for smartset."""
135 This is part of the mandatory API for smartset."""
136 return addset(self, other)
136 return addset(self, other)
137
137
138 def __sub__(self, other):
138 def __sub__(self, other):
139 """Returns a new object with the substraction of the two collections.
139 """Returns a new object with the substraction of the two collections.
140
140
141 This is part of the mandatory API for smartset."""
141 This is part of the mandatory API for smartset."""
142 c = other.__contains__
142 c = other.__contains__
143 return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),
143 return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),
144 cache=False)
144 cache=False)
145
145
146 def filter(self, condition, condrepr=None, cache=True):
146 def filter(self, condition, condrepr=None, cache=True):
147 """Returns this smartset filtered by condition as a new smartset.
147 """Returns this smartset filtered by condition as a new smartset.
148
148
149 `condition` is a callable which takes a revision number and returns a
149 `condition` is a callable which takes a revision number and returns a
150 boolean. Optional `condrepr` provides a printable representation of
150 boolean. Optional `condrepr` provides a printable representation of
151 the given `condition`.
151 the given `condition`.
152
152
153 This is part of the mandatory API for smartset."""
153 This is part of the mandatory API for smartset."""
154 # builtin cannot be cached. but do not needs to
154 # builtin cannot be cached. but do not needs to
155 if cache and util.safehasattr(condition, 'func_code'):
155 if cache and util.safehasattr(condition, 'func_code'):
156 condition = util.cachefunc(condition)
156 condition = util.cachefunc(condition)
157 return filteredset(self, condition, condrepr)
157 return filteredset(self, condition, condrepr)
158
158
159 def slice(self, start, stop):
159 def slice(self, start, stop):
160 """Return new smartset that contains selected elements from this set"""
160 """Return new smartset that contains selected elements from this set"""
161 if start < 0 or stop < 0:
161 if start < 0 or stop < 0:
162 raise error.ProgrammingError('negative index not allowed')
162 raise error.ProgrammingError('negative index not allowed')
163 return self._slice(start, stop)
163 return self._slice(start, stop)
164
164
165 def _slice(self, start, stop):
165 def _slice(self, start, stop):
166 # sub classes may override this. start and stop must not be negative,
166 # sub classes may override this. start and stop must not be negative,
167 # but start > stop is allowed, which should be an empty set.
167 # but start > stop is allowed, which should be an empty set.
168 ys = []
168 ys = []
169 it = iter(self)
169 it = iter(self)
170 for x in xrange(start):
170 for x in xrange(start):
171 y = next(it, None)
171 y = next(it, None)
172 if y is None:
172 if y is None:
173 break
173 break
174 for x in xrange(stop - start):
174 for x in xrange(stop - start):
175 y = next(it, None)
175 y = next(it, None)
176 if y is None:
176 if y is None:
177 break
177 break
178 ys.append(y)
178 ys.append(y)
179 return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self))
179 return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self))
180
180
181 class baseset(abstractsmartset):
181 class baseset(abstractsmartset):
182 """Basic data structure that represents a revset and contains the basic
182 """Basic data structure that represents a revset and contains the basic
183 operation that it should be able to perform.
183 operation that it should be able to perform.
184
184
185 Every method in this class should be implemented by any smartset class.
185 Every method in this class should be implemented by any smartset class.
186
186
187 This class could be constructed by an (unordered) set, or an (ordered)
187 This class could be constructed by an (unordered) set, or an (ordered)
188 list-like object. If a set is provided, it'll be sorted lazily.
188 list-like object. If a set is provided, it'll be sorted lazily.
189
189
190 >>> x = [4, 0, 7, 6]
190 >>> x = [4, 0, 7, 6]
191 >>> y = [5, 6, 7, 3]
191 >>> y = [5, 6, 7, 3]
192
192
193 Construct by a set:
193 Construct by a set:
194 >>> xs = baseset(set(x))
194 >>> xs = baseset(set(x))
195 >>> ys = baseset(set(y))
195 >>> ys = baseset(set(y))
196 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
196 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
197 [[0, 4, 6, 7, 3, 5], [6, 7], [0, 4]]
197 [[0, 4, 6, 7, 3, 5], [6, 7], [0, 4]]
198 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
198 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
199 ['addset', 'baseset', 'baseset']
199 ['addset', 'baseset', 'baseset']
200
200
201 Construct by a list-like:
201 Construct by a list-like:
202 >>> xs = baseset(x)
202 >>> xs = baseset(x)
203 >>> ys = baseset(i for i in y)
203 >>> ys = baseset(i for i in y)
204 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
204 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
205 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
205 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
206 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
206 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
207 ['addset', 'filteredset', 'filteredset']
207 ['addset', 'filteredset', 'filteredset']
208
208
209 Populate "_set" fields in the lists so set optimization may be used:
209 Populate "_set" fields in the lists so set optimization may be used:
210 >>> [1 in xs, 3 in ys]
210 >>> [1 in xs, 3 in ys]
211 [False, True]
211 [False, True]
212
212
213 Without sort(), results won't be changed:
213 Without sort(), results won't be changed:
214 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
214 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
215 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
215 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
216 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
216 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
217 ['addset', 'filteredset', 'filteredset']
217 ['addset', 'filteredset', 'filteredset']
218
218
219 With sort(), set optimization could be used:
219 With sort(), set optimization could be used:
220 >>> xs.sort(reverse=True)
220 >>> xs.sort(reverse=True)
221 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
221 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
222 [[7, 6, 4, 0, 5, 3], [7, 6], [4, 0]]
222 [[7, 6, 4, 0, 5, 3], [7, 6], [4, 0]]
223 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
223 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
224 ['addset', 'baseset', 'baseset']
224 ['addset', 'baseset', 'baseset']
225
225
226 >>> ys.sort()
226 >>> ys.sort()
227 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
227 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
228 [[7, 6, 4, 0, 3, 5], [7, 6], [4, 0]]
228 [[7, 6, 4, 0, 3, 5], [7, 6], [4, 0]]
229 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
229 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
230 ['addset', 'baseset', 'baseset']
230 ['addset', 'baseset', 'baseset']
231
231
232 istopo is preserved across set operations
232 istopo is preserved across set operations
233 >>> xs = baseset(set(x), istopo=True)
233 >>> xs = baseset(set(x), istopo=True)
234 >>> rs = xs & ys
234 >>> rs = xs & ys
235 >>> type(rs).__name__
235 >>> type(rs).__name__
236 'baseset'
236 'baseset'
237 >>> rs._istopo
237 >>> rs._istopo
238 True
238 True
239 """
239 """
240 def __init__(self, data=(), datarepr=None, istopo=False):
240 def __init__(self, data=(), datarepr=None, istopo=False):
241 """
241 """
242 datarepr: a tuple of (format, obj, ...), a function or an object that
242 datarepr: a tuple of (format, obj, ...), a function or an object that
243 provides a printable representation of the given data.
243 provides a printable representation of the given data.
244 """
244 """
245 self._ascending = None
245 self._ascending = None
246 self._istopo = istopo
246 self._istopo = istopo
247 if isinstance(data, set):
247 if isinstance(data, set):
248 # converting set to list has a cost, do it lazily
248 # converting set to list has a cost, do it lazily
249 self._set = data
249 self._set = data
250 # set has no order we pick one for stability purpose
250 # set has no order we pick one for stability purpose
251 self._ascending = True
251 self._ascending = True
252 else:
252 else:
253 if not isinstance(data, list):
253 if not isinstance(data, list):
254 data = list(data)
254 data = list(data)
255 self._list = data
255 self._list = data
256 self._datarepr = datarepr
256 self._datarepr = datarepr
257
257
258 @util.propertycache
258 @util.propertycache
259 def _set(self):
259 def _set(self):
260 return set(self._list)
260 return set(self._list)
261
261
262 @util.propertycache
262 @util.propertycache
263 def _asclist(self):
263 def _asclist(self):
264 asclist = self._list[:]
264 asclist = self._list[:]
265 asclist.sort()
265 asclist.sort()
266 return asclist
266 return asclist
267
267
268 @util.propertycache
268 @util.propertycache
269 def _list(self):
269 def _list(self):
270 # _list is only lazily constructed if we have _set
270 # _list is only lazily constructed if we have _set
271 assert r'_set' in self.__dict__
271 assert r'_set' in self.__dict__
272 return list(self._set)
272 return list(self._set)
273
273
274 def __iter__(self):
274 def __iter__(self):
275 if self._ascending is None:
275 if self._ascending is None:
276 return iter(self._list)
276 return iter(self._list)
277 elif self._ascending:
277 elif self._ascending:
278 return iter(self._asclist)
278 return iter(self._asclist)
279 else:
279 else:
280 return reversed(self._asclist)
280 return reversed(self._asclist)
281
281
282 def fastasc(self):
282 def fastasc(self):
283 return iter(self._asclist)
283 return iter(self._asclist)
284
284
285 def fastdesc(self):
285 def fastdesc(self):
286 return reversed(self._asclist)
286 return reversed(self._asclist)
287
287
288 @util.propertycache
288 @util.propertycache
289 def __contains__(self):
289 def __contains__(self):
290 return self._set.__contains__
290 return self._set.__contains__
291
291
292 def __nonzero__(self):
292 def __nonzero__(self):
293 return bool(len(self))
293 return bool(len(self))
294
294
295 __bool__ = __nonzero__
295 __bool__ = __nonzero__
296
296
297 def sort(self, reverse=False):
297 def sort(self, reverse=False):
298 self._ascending = not bool(reverse)
298 self._ascending = not bool(reverse)
299 self._istopo = False
299 self._istopo = False
300
300
301 def reverse(self):
301 def reverse(self):
302 if self._ascending is None:
302 if self._ascending is None:
303 self._list.reverse()
303 self._list.reverse()
304 else:
304 else:
305 self._ascending = not self._ascending
305 self._ascending = not self._ascending
306 self._istopo = False
306 self._istopo = False
307
307
308 def __len__(self):
308 def __len__(self):
309 if '_list' in self.__dict__:
309 if '_list' in self.__dict__:
310 return len(self._list)
310 return len(self._list)
311 else:
311 else:
312 return len(self._set)
312 return len(self._set)
313
313
314 def isascending(self):
314 def isascending(self):
315 """Returns True if the collection is ascending order, False if not.
315 """Returns True if the collection is ascending order, False if not.
316
316
317 This is part of the mandatory API for smartset."""
317 This is part of the mandatory API for smartset."""
318 if len(self) <= 1:
318 if len(self) <= 1:
319 return True
319 return True
320 return self._ascending is not None and self._ascending
320 return self._ascending is not None and self._ascending
321
321
322 def isdescending(self):
322 def isdescending(self):
323 """Returns True if the collection is descending order, False if not.
323 """Returns True if the collection is descending order, False if not.
324
324
325 This is part of the mandatory API for smartset."""
325 This is part of the mandatory API for smartset."""
326 if len(self) <= 1:
326 if len(self) <= 1:
327 return True
327 return True
328 return self._ascending is not None and not self._ascending
328 return self._ascending is not None and not self._ascending
329
329
330 def istopo(self):
330 def istopo(self):
331 """Is the collection is in topographical order or not.
331 """Is the collection is in topographical order or not.
332
332
333 This is part of the mandatory API for smartset."""
333 This is part of the mandatory API for smartset."""
334 if len(self) <= 1:
334 if len(self) <= 1:
335 return True
335 return True
336 return self._istopo
336 return self._istopo
337
337
338 def first(self):
338 def first(self):
339 if self:
339 if self:
340 if self._ascending is None:
340 if self._ascending is None:
341 return self._list[0]
341 return self._list[0]
342 elif self._ascending:
342 elif self._ascending:
343 return self._asclist[0]
343 return self._asclist[0]
344 else:
344 else:
345 return self._asclist[-1]
345 return self._asclist[-1]
346 return None
346 return None
347
347
348 def last(self):
348 def last(self):
349 if self:
349 if self:
350 if self._ascending is None:
350 if self._ascending is None:
351 return self._list[-1]
351 return self._list[-1]
352 elif self._ascending:
352 elif self._ascending:
353 return self._asclist[-1]
353 return self._asclist[-1]
354 else:
354 else:
355 return self._asclist[0]
355 return self._asclist[0]
356 return None
356 return None
357
357
358 def _fastsetop(self, other, op):
358 def _fastsetop(self, other, op):
359 # try to use native set operations as fast paths
359 # try to use native set operations as fast paths
360 if (type(other) is baseset and '_set' in other.__dict__ and '_set' in
360 if (type(other) is baseset and '_set' in other.__dict__ and '_set' in
361 self.__dict__ and self._ascending is not None):
361 self.__dict__ and self._ascending is not None):
362 s = baseset(data=getattr(self._set, op)(other._set),
362 s = baseset(data=getattr(self._set, op)(other._set),
363 istopo=self._istopo)
363 istopo=self._istopo)
364 s._ascending = self._ascending
364 s._ascending = self._ascending
365 else:
365 else:
366 s = getattr(super(baseset, self), op)(other)
366 s = getattr(super(baseset, self), op)(other)
367 return s
367 return s
368
368
369 def __and__(self, other):
369 def __and__(self, other):
370 return self._fastsetop(other, '__and__')
370 return self._fastsetop(other, '__and__')
371
371
372 def __sub__(self, other):
372 def __sub__(self, other):
373 return self._fastsetop(other, '__sub__')
373 return self._fastsetop(other, '__sub__')
374
374
375 def _slice(self, start, stop):
375 def _slice(self, start, stop):
376 # creating new list should be generally cheaper than iterating items
376 # creating new list should be generally cheaper than iterating items
377 if self._ascending is None:
377 if self._ascending is None:
378 return baseset(self._list[start:stop], istopo=self._istopo)
378 return baseset(self._list[start:stop], istopo=self._istopo)
379
379
380 data = self._asclist
380 data = self._asclist
381 if not self._ascending:
381 if not self._ascending:
382 start, stop = max(len(data) - stop, 0), max(len(data) - start, 0)
382 start, stop = max(len(data) - stop, 0), max(len(data) - start, 0)
383 s = baseset(data[start:stop], istopo=self._istopo)
383 s = baseset(data[start:stop], istopo=self._istopo)
384 s._ascending = self._ascending
384 s._ascending = self._ascending
385 return s
385 return s
386
386
387 def __repr__(self):
387 def __repr__(self):
388 d = {None: '', False: '-', True: '+'}[self._ascending]
388 d = {None: '', False: '-', True: '+'}[self._ascending]
389 s = _formatsetrepr(self._datarepr)
389 s = _formatsetrepr(self._datarepr)
390 if not s:
390 if not s:
391 l = self._list
391 l = self._list
392 # if _list has been built from a set, it might have a different
392 # if _list has been built from a set, it might have a different
393 # order from one python implementation to another.
393 # order from one python implementation to another.
394 # We fallback to the sorted version for a stable output.
394 # We fallback to the sorted version for a stable output.
395 if self._ascending is not None:
395 if self._ascending is not None:
396 l = self._asclist
396 l = self._asclist
397 s = repr(l)
397 s = repr(l)
398 return '<%s%s %s>' % (type(self).__name__, d, s)
398 return '<%s%s %s>' % (type(self).__name__, d, s)
399
399
400 class filteredset(abstractsmartset):
400 class filteredset(abstractsmartset):
401 """Duck type for baseset class which iterates lazily over the revisions in
401 """Duck type for baseset class which iterates lazily over the revisions in
402 the subset and contains a function which tests for membership in the
402 the subset and contains a function which tests for membership in the
403 revset
403 revset
404 """
404 """
405 def __init__(self, subset, condition=lambda x: True, condrepr=None):
405 def __init__(self, subset, condition=lambda x: True, condrepr=None):
406 """
406 """
407 condition: a function that decide whether a revision in the subset
407 condition: a function that decide whether a revision in the subset
408 belongs to the revset or not.
408 belongs to the revset or not.
409 condrepr: a tuple of (format, obj, ...), a function or an object that
409 condrepr: a tuple of (format, obj, ...), a function or an object that
410 provides a printable representation of the given condition.
410 provides a printable representation of the given condition.
411 """
411 """
412 self._subset = subset
412 self._subset = subset
413 self._condition = condition
413 self._condition = condition
414 self._condrepr = condrepr
414 self._condrepr = condrepr
415
415
416 def __contains__(self, x):
416 def __contains__(self, x):
417 return x in self._subset and self._condition(x)
417 return x in self._subset and self._condition(x)
418
418
419 def __iter__(self):
419 def __iter__(self):
420 return self._iterfilter(self._subset)
420 return self._iterfilter(self._subset)
421
421
422 def _iterfilter(self, it):
422 def _iterfilter(self, it):
423 cond = self._condition
423 cond = self._condition
424 for x in it:
424 for x in it:
425 if cond(x):
425 if cond(x):
426 yield x
426 yield x
427
427
428 @property
428 @property
429 def fastasc(self):
429 def fastasc(self):
430 it = self._subset.fastasc
430 it = self._subset.fastasc
431 if it is None:
431 if it is None:
432 return None
432 return None
433 return lambda: self._iterfilter(it())
433 return lambda: self._iterfilter(it())
434
434
435 @property
435 @property
436 def fastdesc(self):
436 def fastdesc(self):
437 it = self._subset.fastdesc
437 it = self._subset.fastdesc
438 if it is None:
438 if it is None:
439 return None
439 return None
440 return lambda: self._iterfilter(it())
440 return lambda: self._iterfilter(it())
441
441
442 def __nonzero__(self):
442 def __nonzero__(self):
443 fast = None
443 fast = None
444 candidates = [self.fastasc if self.isascending() else None,
444 candidates = [self.fastasc if self.isascending() else None,
445 self.fastdesc if self.isdescending() else None,
445 self.fastdesc if self.isdescending() else None,
446 self.fastasc,
446 self.fastasc,
447 self.fastdesc]
447 self.fastdesc]
448 for candidate in candidates:
448 for candidate in candidates:
449 if candidate is not None:
449 if candidate is not None:
450 fast = candidate
450 fast = candidate
451 break
451 break
452
452
453 if fast is not None:
453 if fast is not None:
454 it = fast()
454 it = fast()
455 else:
455 else:
456 it = self
456 it = self
457
457
458 for r in it:
458 for r in it:
459 return True
459 return True
460 return False
460 return False
461
461
462 __bool__ = __nonzero__
462 __bool__ = __nonzero__
463
463
464 def __len__(self):
464 def __len__(self):
465 # Basic implementation to be changed in future patches.
465 # Basic implementation to be changed in future patches.
466 # until this gets improved, we use generator expression
466 # until this gets improved, we use generator expression
467 # here, since list comprehensions are free to call __len__ again
467 # here, since list comprehensions are free to call __len__ again
468 # causing infinite recursion
468 # causing infinite recursion
469 l = baseset(r for r in self)
469 l = baseset(r for r in self)
470 return len(l)
470 return len(l)
471
471
472 def sort(self, reverse=False):
472 def sort(self, reverse=False):
473 self._subset.sort(reverse=reverse)
473 self._subset.sort(reverse=reverse)
474
474
475 def reverse(self):
475 def reverse(self):
476 self._subset.reverse()
476 self._subset.reverse()
477
477
478 def isascending(self):
478 def isascending(self):
479 return self._subset.isascending()
479 return self._subset.isascending()
480
480
481 def isdescending(self):
481 def isdescending(self):
482 return self._subset.isdescending()
482 return self._subset.isdescending()
483
483
484 def istopo(self):
484 def istopo(self):
485 return self._subset.istopo()
485 return self._subset.istopo()
486
486
487 def first(self):
487 def first(self):
488 for x in self:
488 for x in self:
489 return x
489 return x
490 return None
490 return None
491
491
492 def last(self):
492 def last(self):
493 it = None
493 it = None
494 if self.isascending():
494 if self.isascending():
495 it = self.fastdesc
495 it = self.fastdesc
496 elif self.isdescending():
496 elif self.isdescending():
497 it = self.fastasc
497 it = self.fastasc
498 if it is not None:
498 if it is not None:
499 for x in it():
499 for x in it():
500 return x
500 return x
501 return None #empty case
501 return None #empty case
502 else:
502 else:
503 x = None
503 x = None
504 for x in self:
504 for x in self:
505 pass
505 pass
506 return x
506 return x
507
507
508 def __repr__(self):
508 def __repr__(self):
509 xs = [repr(self._subset)]
509 xs = [repr(self._subset)]
510 s = _formatsetrepr(self._condrepr)
510 s = _formatsetrepr(self._condrepr)
511 if s:
511 if s:
512 xs.append(s)
512 xs.append(s)
513 return '<%s %s>' % (type(self).__name__, ', '.join(xs))
513 return '<%s %s>' % (type(self).__name__, ', '.join(xs))
514
514
515 def _iterordered(ascending, iter1, iter2):
515 def _iterordered(ascending, iter1, iter2):
516 """produce an ordered iteration from two iterators with the same order
516 """produce an ordered iteration from two iterators with the same order
517
517
518 The ascending is used to indicated the iteration direction.
518 The ascending is used to indicated the iteration direction.
519 """
519 """
520 choice = max
520 choice = max
521 if ascending:
521 if ascending:
522 choice = min
522 choice = min
523
523
524 val1 = None
524 val1 = None
525 val2 = None
525 val2 = None
526 try:
526 try:
527 # Consume both iterators in an ordered way until one is empty
527 # Consume both iterators in an ordered way until one is empty
528 while True:
528 while True:
529 if val1 is None:
529 if val1 is None:
530 val1 = next(iter1)
530 val1 = next(iter1)
531 if val2 is None:
531 if val2 is None:
532 val2 = next(iter2)
532 val2 = next(iter2)
533 n = choice(val1, val2)
533 n = choice(val1, val2)
534 yield n
534 yield n
535 if val1 == n:
535 if val1 == n:
536 val1 = None
536 val1 = None
537 if val2 == n:
537 if val2 == n:
538 val2 = None
538 val2 = None
539 except StopIteration:
539 except StopIteration:
540 # Flush any remaining values and consume the other one
540 # Flush any remaining values and consume the other one
541 it = iter2
541 it = iter2
542 if val1 is not None:
542 if val1 is not None:
543 yield val1
543 yield val1
544 it = iter1
544 it = iter1
545 elif val2 is not None:
545 elif val2 is not None:
546 # might have been equality and both are empty
546 # might have been equality and both are empty
547 yield val2
547 yield val2
548 for val in it:
548 for val in it:
549 yield val
549 yield val
550
550
551 class addset(abstractsmartset):
551 class addset(abstractsmartset):
552 """Represent the addition of two sets
552 """Represent the addition of two sets
553
553
554 Wrapper structure for lazily adding two structures without losing much
554 Wrapper structure for lazily adding two structures without losing much
555 performance on the __contains__ method
555 performance on the __contains__ method
556
556
557 If the ascending attribute is set, that means the two structures are
557 If the ascending attribute is set, that means the two structures are
558 ordered in either an ascending or descending way. Therefore, we can add
558 ordered in either an ascending or descending way. Therefore, we can add
559 them maintaining the order by iterating over both at the same time
559 them maintaining the order by iterating over both at the same time
560
560
561 >>> xs = baseset([0, 3, 2])
561 >>> xs = baseset([0, 3, 2])
562 >>> ys = baseset([5, 2, 4])
562 >>> ys = baseset([5, 2, 4])
563
563
564 >>> rs = addset(xs, ys)
564 >>> rs = addset(xs, ys)
565 >>> bool(rs), 0 in rs, 1 in rs, 5 in rs, rs.first(), rs.last()
565 >>> bool(rs), 0 in rs, 1 in rs, 5 in rs, rs.first(), rs.last()
566 (True, True, False, True, 0, 4)
566 (True, True, False, True, 0, 4)
567 >>> rs = addset(xs, baseset([]))
567 >>> rs = addset(xs, baseset([]))
568 >>> bool(rs), 0 in rs, 1 in rs, rs.first(), rs.last()
568 >>> bool(rs), 0 in rs, 1 in rs, rs.first(), rs.last()
569 (True, True, False, 0, 2)
569 (True, True, False, 0, 2)
570 >>> rs = addset(baseset([]), baseset([]))
570 >>> rs = addset(baseset([]), baseset([]))
571 >>> bool(rs), 0 in rs, rs.first(), rs.last()
571 >>> bool(rs), 0 in rs, rs.first(), rs.last()
572 (False, False, None, None)
572 (False, False, None, None)
573
573
574 iterate unsorted:
574 iterate unsorted:
575 >>> rs = addset(xs, ys)
575 >>> rs = addset(xs, ys)
576 >>> # (use generator because pypy could call len())
576 >>> # (use generator because pypy could call len())
577 >>> list(x for x in rs) # without _genlist
577 >>> list(x for x in rs) # without _genlist
578 [0, 3, 2, 5, 4]
578 [0, 3, 2, 5, 4]
579 >>> assert not rs._genlist
579 >>> assert not rs._genlist
580 >>> len(rs)
580 >>> len(rs)
581 5
581 5
582 >>> [x for x in rs] # with _genlist
582 >>> [x for x in rs] # with _genlist
583 [0, 3, 2, 5, 4]
583 [0, 3, 2, 5, 4]
584 >>> assert rs._genlist
584 >>> assert rs._genlist
585
585
586 iterate ascending:
586 iterate ascending:
587 >>> rs = addset(xs, ys, ascending=True)
587 >>> rs = addset(xs, ys, ascending=True)
588 >>> # (use generator because pypy could call len())
588 >>> # (use generator because pypy could call len())
589 >>> list(x for x in rs), list(x for x in rs.fastasc()) # without _asclist
589 >>> list(x for x in rs), list(x for x in rs.fastasc()) # without _asclist
590 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
590 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
591 >>> assert not rs._asclist
591 >>> assert not rs._asclist
592 >>> len(rs)
592 >>> len(rs)
593 5
593 5
594 >>> [x for x in rs], [x for x in rs.fastasc()]
594 >>> [x for x in rs], [x for x in rs.fastasc()]
595 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
595 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
596 >>> assert rs._asclist
596 >>> assert rs._asclist
597
597
598 iterate descending:
598 iterate descending:
599 >>> rs = addset(xs, ys, ascending=False)
599 >>> rs = addset(xs, ys, ascending=False)
600 >>> # (use generator because pypy could call len())
600 >>> # (use generator because pypy could call len())
601 >>> list(x for x in rs), list(x for x in rs.fastdesc()) # without _asclist
601 >>> list(x for x in rs), list(x for x in rs.fastdesc()) # without _asclist
602 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
602 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
603 >>> assert not rs._asclist
603 >>> assert not rs._asclist
604 >>> len(rs)
604 >>> len(rs)
605 5
605 5
606 >>> [x for x in rs], [x for x in rs.fastdesc()]
606 >>> [x for x in rs], [x for x in rs.fastdesc()]
607 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
607 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
608 >>> assert rs._asclist
608 >>> assert rs._asclist
609
609
610 iterate ascending without fastasc:
610 iterate ascending without fastasc:
611 >>> rs = addset(xs, generatorset(ys), ascending=True)
611 >>> rs = addset(xs, generatorset(ys), ascending=True)
612 >>> assert rs.fastasc is None
612 >>> assert rs.fastasc is None
613 >>> [x for x in rs]
613 >>> [x for x in rs]
614 [0, 2, 3, 4, 5]
614 [0, 2, 3, 4, 5]
615
615
616 iterate descending without fastdesc:
616 iterate descending without fastdesc:
617 >>> rs = addset(generatorset(xs), ys, ascending=False)
617 >>> rs = addset(generatorset(xs), ys, ascending=False)
618 >>> assert rs.fastdesc is None
618 >>> assert rs.fastdesc is None
619 >>> [x for x in rs]
619 >>> [x for x in rs]
620 [5, 4, 3, 2, 0]
620 [5, 4, 3, 2, 0]
621 """
621 """
622 def __init__(self, revs1, revs2, ascending=None):
622 def __init__(self, revs1, revs2, ascending=None):
623 self._r1 = revs1
623 self._r1 = revs1
624 self._r2 = revs2
624 self._r2 = revs2
625 self._iter = None
625 self._iter = None
626 self._ascending = ascending
626 self._ascending = ascending
627 self._genlist = None
627 self._genlist = None
628 self._asclist = None
628 self._asclist = None
629
629
630 def __len__(self):
630 def __len__(self):
631 return len(self._list)
631 return len(self._list)
632
632
633 def __nonzero__(self):
633 def __nonzero__(self):
634 return bool(self._r1) or bool(self._r2)
634 return bool(self._r1) or bool(self._r2)
635
635
636 __bool__ = __nonzero__
636 __bool__ = __nonzero__
637
637
638 @util.propertycache
638 @util.propertycache
639 def _list(self):
639 def _list(self):
640 if not self._genlist:
640 if not self._genlist:
641 self._genlist = baseset(iter(self))
641 self._genlist = baseset(iter(self))
642 return self._genlist
642 return self._genlist
643
643
644 def __iter__(self):
644 def __iter__(self):
645 """Iterate over both collections without repeating elements
645 """Iterate over both collections without repeating elements
646
646
647 If the ascending attribute is not set, iterate over the first one and
647 If the ascending attribute is not set, iterate over the first one and
648 then over the second one checking for membership on the first one so we
648 then over the second one checking for membership on the first one so we
649 dont yield any duplicates.
649 dont yield any duplicates.
650
650
651 If the ascending attribute is set, iterate over both collections at the
651 If the ascending attribute is set, iterate over both collections at the
652 same time, yielding only one value at a time in the given order.
652 same time, yielding only one value at a time in the given order.
653 """
653 """
654 if self._ascending is None:
654 if self._ascending is None:
655 if self._genlist:
655 if self._genlist:
656 return iter(self._genlist)
656 return iter(self._genlist)
657 def arbitraryordergen():
657 def arbitraryordergen():
658 for r in self._r1:
658 for r in self._r1:
659 yield r
659 yield r
660 inr1 = self._r1.__contains__
660 inr1 = self._r1.__contains__
661 for r in self._r2:
661 for r in self._r2:
662 if not inr1(r):
662 if not inr1(r):
663 yield r
663 yield r
664 return arbitraryordergen()
664 return arbitraryordergen()
665 # try to use our own fast iterator if it exists
665 # try to use our own fast iterator if it exists
666 self._trysetasclist()
666 self._trysetasclist()
667 if self._ascending:
667 if self._ascending:
668 attr = 'fastasc'
668 attr = 'fastasc'
669 else:
669 else:
670 attr = 'fastdesc'
670 attr = 'fastdesc'
671 it = getattr(self, attr)
671 it = getattr(self, attr)
672 if it is not None:
672 if it is not None:
673 return it()
673 return it()
674 # maybe half of the component supports fast
674 # maybe half of the component supports fast
675 # get iterator for _r1
675 # get iterator for _r1
676 iter1 = getattr(self._r1, attr)
676 iter1 = getattr(self._r1, attr)
677 if iter1 is None:
677 if iter1 is None:
678 # let's avoid side effect (not sure it matters)
678 # let's avoid side effect (not sure it matters)
679 iter1 = iter(sorted(self._r1, reverse=not self._ascending))
679 iter1 = iter(sorted(self._r1, reverse=not self._ascending))
680 else:
680 else:
681 iter1 = iter1()
681 iter1 = iter1()
682 # get iterator for _r2
682 # get iterator for _r2
683 iter2 = getattr(self._r2, attr)
683 iter2 = getattr(self._r2, attr)
684 if iter2 is None:
684 if iter2 is None:
685 # let's avoid side effect (not sure it matters)
685 # let's avoid side effect (not sure it matters)
686 iter2 = iter(sorted(self._r2, reverse=not self._ascending))
686 iter2 = iter(sorted(self._r2, reverse=not self._ascending))
687 else:
687 else:
688 iter2 = iter2()
688 iter2 = iter2()
689 return _iterordered(self._ascending, iter1, iter2)
689 return _iterordered(self._ascending, iter1, iter2)
690
690
691 def _trysetasclist(self):
691 def _trysetasclist(self):
692 """populate the _asclist attribute if possible and necessary"""
692 """populate the _asclist attribute if possible and necessary"""
693 if self._genlist is not None and self._asclist is None:
693 if self._genlist is not None and self._asclist is None:
694 self._asclist = sorted(self._genlist)
694 self._asclist = sorted(self._genlist)
695
695
696 @property
696 @property
697 def fastasc(self):
697 def fastasc(self):
698 self._trysetasclist()
698 self._trysetasclist()
699 if self._asclist is not None:
699 if self._asclist is not None:
700 return self._asclist.__iter__
700 return self._asclist.__iter__
701 iter1 = self._r1.fastasc
701 iter1 = self._r1.fastasc
702 iter2 = self._r2.fastasc
702 iter2 = self._r2.fastasc
703 if None in (iter1, iter2):
703 if None in (iter1, iter2):
704 return None
704 return None
705 return lambda: _iterordered(True, iter1(), iter2())
705 return lambda: _iterordered(True, iter1(), iter2())
706
706
707 @property
707 @property
708 def fastdesc(self):
708 def fastdesc(self):
709 self._trysetasclist()
709 self._trysetasclist()
710 if self._asclist is not None:
710 if self._asclist is not None:
711 return self._asclist.__reversed__
711 return self._asclist.__reversed__
712 iter1 = self._r1.fastdesc
712 iter1 = self._r1.fastdesc
713 iter2 = self._r2.fastdesc
713 iter2 = self._r2.fastdesc
714 if None in (iter1, iter2):
714 if None in (iter1, iter2):
715 return None
715 return None
716 return lambda: _iterordered(False, iter1(), iter2())
716 return lambda: _iterordered(False, iter1(), iter2())
717
717
718 def __contains__(self, x):
718 def __contains__(self, x):
719 return x in self._r1 or x in self._r2
719 return x in self._r1 or x in self._r2
720
720
721 def sort(self, reverse=False):
721 def sort(self, reverse=False):
722 """Sort the added set
722 """Sort the added set
723
723
724 For this we use the cached list with all the generated values and if we
724 For this we use the cached list with all the generated values and if we
725 know they are ascending or descending we can sort them in a smart way.
725 know they are ascending or descending we can sort them in a smart way.
726 """
726 """
727 self._ascending = not reverse
727 self._ascending = not reverse
728
728
729 def isascending(self):
729 def isascending(self):
730 return self._ascending is not None and self._ascending
730 return self._ascending is not None and self._ascending
731
731
732 def isdescending(self):
732 def isdescending(self):
733 return self._ascending is not None and not self._ascending
733 return self._ascending is not None and not self._ascending
734
734
735 def istopo(self):
735 def istopo(self):
736 # not worth the trouble asserting if the two sets combined are still
736 # not worth the trouble asserting if the two sets combined are still
737 # in topographical order. Use the sort() predicate to explicitly sort
737 # in topographical order. Use the sort() predicate to explicitly sort
738 # again instead.
738 # again instead.
739 return False
739 return False
740
740
741 def reverse(self):
741 def reverse(self):
742 if self._ascending is None:
742 if self._ascending is None:
743 self._list.reverse()
743 self._list.reverse()
744 else:
744 else:
745 self._ascending = not self._ascending
745 self._ascending = not self._ascending
746
746
747 def first(self):
747 def first(self):
748 for x in self:
748 for x in self:
749 return x
749 return x
750 return None
750 return None
751
751
752 def last(self):
752 def last(self):
753 self.reverse()
753 self.reverse()
754 val = self.first()
754 val = self.first()
755 self.reverse()
755 self.reverse()
756 return val
756 return val
757
757
758 def __repr__(self):
758 def __repr__(self):
759 d = {None: '', False: '-', True: '+'}[self._ascending]
759 d = {None: '', False: '-', True: '+'}[self._ascending]
760 return '<%s%s %r, %r>' % (type(self).__name__, d, self._r1, self._r2)
760 return '<%s%s %r, %r>' % (type(self).__name__, d, self._r1, self._r2)
761
761
762 class generatorset(abstractsmartset):
762 class generatorset(abstractsmartset):
763 """Wrap a generator for lazy iteration
763 """Wrap a generator for lazy iteration
764
764
765 Wrapper structure for generators that provides lazy membership and can
765 Wrapper structure for generators that provides lazy membership and can
766 be iterated more than once.
766 be iterated more than once.
767 When asked for membership it generates values until either it finds the
767 When asked for membership it generates values until either it finds the
768 requested one or has gone through all the elements in the generator
768 requested one or has gone through all the elements in the generator
769 """
769 """
770 def __init__(self, gen, iterasc=None):
770 def __init__(self, gen, iterasc=None):
771 """
771 """
772 gen: a generator producing the values for the generatorset.
772 gen: a generator producing the values for the generatorset.
773 """
773 """
774 self._gen = gen
774 self._gen = gen
775 self._asclist = None
775 self._asclist = None
776 self._cache = {}
776 self._cache = {}
777 self._genlist = []
777 self._genlist = []
778 self._finished = False
778 self._finished = False
779 self._ascending = True
779 self._ascending = True
780 if iterasc is not None:
780 if iterasc is not None:
781 if iterasc:
781 if iterasc:
782 self.fastasc = self._iterator
782 self.fastasc = self._iterator
783 self.__contains__ = self._asccontains
783 self.__contains__ = self._asccontains
784 else:
784 else:
785 self.fastdesc = self._iterator
785 self.fastdesc = self._iterator
786 self.__contains__ = self._desccontains
786 self.__contains__ = self._desccontains
787
787
788 def __nonzero__(self):
788 def __nonzero__(self):
789 # Do not use 'for r in self' because it will enforce the iteration
789 # Do not use 'for r in self' because it will enforce the iteration
790 # order (default ascending), possibly unrolling a whole descending
790 # order (default ascending), possibly unrolling a whole descending
791 # iterator.
791 # iterator.
792 if self._genlist:
792 if self._genlist:
793 return True
793 return True
794 for r in self._consumegen():
794 for r in self._consumegen():
795 return True
795 return True
796 return False
796 return False
797
797
798 __bool__ = __nonzero__
798 __bool__ = __nonzero__
799
799
800 def __contains__(self, x):
800 def __contains__(self, x):
801 if x in self._cache:
801 if x in self._cache:
802 return self._cache[x]
802 return self._cache[x]
803
803
804 # Use new values only, as existing values would be cached.
804 # Use new values only, as existing values would be cached.
805 for l in self._consumegen():
805 for l in self._consumegen():
806 if l == x:
806 if l == x:
807 return True
807 return True
808
808
809 self._cache[x] = False
809 self._cache[x] = False
810 return False
810 return False
811
811
812 def _asccontains(self, x):
812 def _asccontains(self, x):
813 """version of contains optimised for ascending generator"""
813 """version of contains optimised for ascending generator"""
814 if x in self._cache:
814 if x in self._cache:
815 return self._cache[x]
815 return self._cache[x]
816
816
817 # Use new values only, as existing values would be cached.
817 # Use new values only, as existing values would be cached.
818 for l in self._consumegen():
818 for l in self._consumegen():
819 if l == x:
819 if l == x:
820 return True
820 return True
821 if l > x:
821 if l > x:
822 break
822 break
823
823
824 self._cache[x] = False
824 self._cache[x] = False
825 return False
825 return False
826
826
827 def _desccontains(self, x):
827 def _desccontains(self, x):
828 """version of contains optimised for descending generator"""
828 """version of contains optimised for descending generator"""
829 if x in self._cache:
829 if x in self._cache:
830 return self._cache[x]
830 return self._cache[x]
831
831
832 # Use new values only, as existing values would be cached.
832 # Use new values only, as existing values would be cached.
833 for l in self._consumegen():
833 for l in self._consumegen():
834 if l == x:
834 if l == x:
835 return True
835 return True
836 if l < x:
836 if l < x:
837 break
837 break
838
838
839 self._cache[x] = False
839 self._cache[x] = False
840 return False
840 return False
841
841
842 def __iter__(self):
842 def __iter__(self):
843 if self._ascending:
843 if self._ascending:
844 it = self.fastasc
844 it = self.fastasc
845 else:
845 else:
846 it = self.fastdesc
846 it = self.fastdesc
847 if it is not None:
847 if it is not None:
848 return it()
848 return it()
849 # we need to consume the iterator
849 # we need to consume the iterator
850 for x in self._consumegen():
850 for x in self._consumegen():
851 pass
851 pass
852 # recall the same code
852 # recall the same code
853 return iter(self)
853 return iter(self)
854
854
855 def _iterator(self):
855 def _iterator(self):
856 if self._finished:
856 if self._finished:
857 return iter(self._genlist)
857 return iter(self._genlist)
858
858
859 # We have to use this complex iteration strategy to allow multiple
859 # We have to use this complex iteration strategy to allow multiple
860 # iterations at the same time. We need to be able to catch revision
860 # iterations at the same time. We need to be able to catch revision
861 # removed from _consumegen and added to genlist in another instance.
861 # removed from _consumegen and added to genlist in another instance.
862 #
862 #
863 # Getting rid of it would provide an about 15% speed up on this
863 # Getting rid of it would provide an about 15% speed up on this
864 # iteration.
864 # iteration.
865 genlist = self._genlist
865 genlist = self._genlist
866 nextgen = self._consumegen()
866 nextgen = self._consumegen()
867 _len, _next = len, next # cache global lookup
867 _len, _next = len, next # cache global lookup
868 def gen():
868 def gen():
869 i = 0
869 i = 0
870 while True:
870 while True:
871 if i < _len(genlist):
871 if i < _len(genlist):
872 yield genlist[i]
872 yield genlist[i]
873 else:
873 else:
874 try:
874 yield _next(nextgen)
875 yield _next(nextgen)
876 except StopIteration:
877 return
875 i += 1
878 i += 1
876 return gen()
879 return gen()
877
880
878 def _consumegen(self):
881 def _consumegen(self):
879 cache = self._cache
882 cache = self._cache
880 genlist = self._genlist.append
883 genlist = self._genlist.append
881 for item in self._gen:
884 for item in self._gen:
882 cache[item] = True
885 cache[item] = True
883 genlist(item)
886 genlist(item)
884 yield item
887 yield item
885 if not self._finished:
888 if not self._finished:
886 self._finished = True
889 self._finished = True
887 asc = self._genlist[:]
890 asc = self._genlist[:]
888 asc.sort()
891 asc.sort()
889 self._asclist = asc
892 self._asclist = asc
890 self.fastasc = asc.__iter__
893 self.fastasc = asc.__iter__
891 self.fastdesc = asc.__reversed__
894 self.fastdesc = asc.__reversed__
892
895
893 def __len__(self):
896 def __len__(self):
894 for x in self._consumegen():
897 for x in self._consumegen():
895 pass
898 pass
896 return len(self._genlist)
899 return len(self._genlist)
897
900
898 def sort(self, reverse=False):
901 def sort(self, reverse=False):
899 self._ascending = not reverse
902 self._ascending = not reverse
900
903
901 def reverse(self):
904 def reverse(self):
902 self._ascending = not self._ascending
905 self._ascending = not self._ascending
903
906
904 def isascending(self):
907 def isascending(self):
905 return self._ascending
908 return self._ascending
906
909
907 def isdescending(self):
910 def isdescending(self):
908 return not self._ascending
911 return not self._ascending
909
912
910 def istopo(self):
913 def istopo(self):
911 # not worth the trouble asserting if the two sets combined are still
914 # not worth the trouble asserting if the two sets combined are still
912 # in topographical order. Use the sort() predicate to explicitly sort
915 # in topographical order. Use the sort() predicate to explicitly sort
913 # again instead.
916 # again instead.
914 return False
917 return False
915
918
916 def first(self):
919 def first(self):
917 if self._ascending:
920 if self._ascending:
918 it = self.fastasc
921 it = self.fastasc
919 else:
922 else:
920 it = self.fastdesc
923 it = self.fastdesc
921 if it is None:
924 if it is None:
922 # we need to consume all and try again
925 # we need to consume all and try again
923 for x in self._consumegen():
926 for x in self._consumegen():
924 pass
927 pass
925 return self.first()
928 return self.first()
926 return next(it(), None)
929 return next(it(), None)
927
930
928 def last(self):
931 def last(self):
929 if self._ascending:
932 if self._ascending:
930 it = self.fastdesc
933 it = self.fastdesc
931 else:
934 else:
932 it = self.fastasc
935 it = self.fastasc
933 if it is None:
936 if it is None:
934 # we need to consume all and try again
937 # we need to consume all and try again
935 for x in self._consumegen():
938 for x in self._consumegen():
936 pass
939 pass
937 return self.first()
940 return self.first()
938 return next(it(), None)
941 return next(it(), None)
939
942
940 def __repr__(self):
943 def __repr__(self):
941 d = {False: '-', True: '+'}[self._ascending]
944 d = {False: '-', True: '+'}[self._ascending]
942 return '<%s%s>' % (type(self).__name__, d)
945 return '<%s%s>' % (type(self).__name__, d)
943
946
944 def spanset(repo, start=0, end=None):
947 def spanset(repo, start=0, end=None):
945 """Create a spanset that represents a range of repository revisions
948 """Create a spanset that represents a range of repository revisions
946
949
947 start: first revision included the set (default to 0)
950 start: first revision included the set (default to 0)
948 end: first revision excluded (last+1) (default to len(repo))
951 end: first revision excluded (last+1) (default to len(repo))
949
952
950 Spanset will be descending if `end` < `start`.
953 Spanset will be descending if `end` < `start`.
951 """
954 """
952 if end is None:
955 if end is None:
953 end = len(repo)
956 end = len(repo)
954 ascending = start <= end
957 ascending = start <= end
955 if not ascending:
958 if not ascending:
956 start, end = end + 1, start + 1
959 start, end = end + 1, start + 1
957 return _spanset(start, end, ascending, repo.changelog.filteredrevs)
960 return _spanset(start, end, ascending, repo.changelog.filteredrevs)
958
961
959 class _spanset(abstractsmartset):
962 class _spanset(abstractsmartset):
960 """Duck type for baseset class which represents a range of revisions and
963 """Duck type for baseset class which represents a range of revisions and
961 can work lazily and without having all the range in memory
964 can work lazily and without having all the range in memory
962
965
963 Note that spanset(x, y) behave almost like xrange(x, y) except for two
966 Note that spanset(x, y) behave almost like xrange(x, y) except for two
964 notable points:
967 notable points:
965 - when x < y it will be automatically descending,
968 - when x < y it will be automatically descending,
966 - revision filtered with this repoview will be skipped.
969 - revision filtered with this repoview will be skipped.
967
970
968 """
971 """
969 def __init__(self, start, end, ascending, hiddenrevs):
972 def __init__(self, start, end, ascending, hiddenrevs):
970 self._start = start
973 self._start = start
971 self._end = end
974 self._end = end
972 self._ascending = ascending
975 self._ascending = ascending
973 self._hiddenrevs = hiddenrevs
976 self._hiddenrevs = hiddenrevs
974
977
975 def sort(self, reverse=False):
978 def sort(self, reverse=False):
976 self._ascending = not reverse
979 self._ascending = not reverse
977
980
978 def reverse(self):
981 def reverse(self):
979 self._ascending = not self._ascending
982 self._ascending = not self._ascending
980
983
981 def istopo(self):
984 def istopo(self):
982 # not worth the trouble asserting if the two sets combined are still
985 # not worth the trouble asserting if the two sets combined are still
983 # in topographical order. Use the sort() predicate to explicitly sort
986 # in topographical order. Use the sort() predicate to explicitly sort
984 # again instead.
987 # again instead.
985 return False
988 return False
986
989
987 def _iterfilter(self, iterrange):
990 def _iterfilter(self, iterrange):
988 s = self._hiddenrevs
991 s = self._hiddenrevs
989 for r in iterrange:
992 for r in iterrange:
990 if r not in s:
993 if r not in s:
991 yield r
994 yield r
992
995
993 def __iter__(self):
996 def __iter__(self):
994 if self._ascending:
997 if self._ascending:
995 return self.fastasc()
998 return self.fastasc()
996 else:
999 else:
997 return self.fastdesc()
1000 return self.fastdesc()
998
1001
999 def fastasc(self):
1002 def fastasc(self):
1000 iterrange = xrange(self._start, self._end)
1003 iterrange = xrange(self._start, self._end)
1001 if self._hiddenrevs:
1004 if self._hiddenrevs:
1002 return self._iterfilter(iterrange)
1005 return self._iterfilter(iterrange)
1003 return iter(iterrange)
1006 return iter(iterrange)
1004
1007
1005 def fastdesc(self):
1008 def fastdesc(self):
1006 iterrange = xrange(self._end - 1, self._start - 1, -1)
1009 iterrange = xrange(self._end - 1, self._start - 1, -1)
1007 if self._hiddenrevs:
1010 if self._hiddenrevs:
1008 return self._iterfilter(iterrange)
1011 return self._iterfilter(iterrange)
1009 return iter(iterrange)
1012 return iter(iterrange)
1010
1013
1011 def __contains__(self, rev):
1014 def __contains__(self, rev):
1012 hidden = self._hiddenrevs
1015 hidden = self._hiddenrevs
1013 return ((self._start <= rev < self._end)
1016 return ((self._start <= rev < self._end)
1014 and not (hidden and rev in hidden))
1017 and not (hidden and rev in hidden))
1015
1018
1016 def __nonzero__(self):
1019 def __nonzero__(self):
1017 for r in self:
1020 for r in self:
1018 return True
1021 return True
1019 return False
1022 return False
1020
1023
1021 __bool__ = __nonzero__
1024 __bool__ = __nonzero__
1022
1025
1023 def __len__(self):
1026 def __len__(self):
1024 if not self._hiddenrevs:
1027 if not self._hiddenrevs:
1025 return abs(self._end - self._start)
1028 return abs(self._end - self._start)
1026 else:
1029 else:
1027 count = 0
1030 count = 0
1028 start = self._start
1031 start = self._start
1029 end = self._end
1032 end = self._end
1030 for rev in self._hiddenrevs:
1033 for rev in self._hiddenrevs:
1031 if (end < rev <= start) or (start <= rev < end):
1034 if (end < rev <= start) or (start <= rev < end):
1032 count += 1
1035 count += 1
1033 return abs(self._end - self._start) - count
1036 return abs(self._end - self._start) - count
1034
1037
1035 def isascending(self):
1038 def isascending(self):
1036 return self._ascending
1039 return self._ascending
1037
1040
1038 def isdescending(self):
1041 def isdescending(self):
1039 return not self._ascending
1042 return not self._ascending
1040
1043
1041 def first(self):
1044 def first(self):
1042 if self._ascending:
1045 if self._ascending:
1043 it = self.fastasc
1046 it = self.fastasc
1044 else:
1047 else:
1045 it = self.fastdesc
1048 it = self.fastdesc
1046 for x in it():
1049 for x in it():
1047 return x
1050 return x
1048 return None
1051 return None
1049
1052
1050 def last(self):
1053 def last(self):
1051 if self._ascending:
1054 if self._ascending:
1052 it = self.fastdesc
1055 it = self.fastdesc
1053 else:
1056 else:
1054 it = self.fastasc
1057 it = self.fastasc
1055 for x in it():
1058 for x in it():
1056 return x
1059 return x
1057 return None
1060 return None
1058
1061
1059 def _slice(self, start, stop):
1062 def _slice(self, start, stop):
1060 if self._hiddenrevs:
1063 if self._hiddenrevs:
1061 # unoptimized since all hidden revisions in range has to be scanned
1064 # unoptimized since all hidden revisions in range has to be scanned
1062 return super(_spanset, self)._slice(start, stop)
1065 return super(_spanset, self)._slice(start, stop)
1063 if self._ascending:
1066 if self._ascending:
1064 x = min(self._start + start, self._end)
1067 x = min(self._start + start, self._end)
1065 y = min(self._start + stop, self._end)
1068 y = min(self._start + stop, self._end)
1066 else:
1069 else:
1067 x = max(self._end - stop, self._start)
1070 x = max(self._end - stop, self._start)
1068 y = max(self._end - start, self._start)
1071 y = max(self._end - start, self._start)
1069 return _spanset(x, y, self._ascending, self._hiddenrevs)
1072 return _spanset(x, y, self._ascending, self._hiddenrevs)
1070
1073
1071 def __repr__(self):
1074 def __repr__(self):
1072 d = {False: '-', True: '+'}[self._ascending]
1075 d = {False: '-', True: '+'}[self._ascending]
1073 return '<%s%s %d:%d>' % (type(self).__name__.lstrip('_'), d,
1076 return '<%s%s %d:%d>' % (type(self).__name__.lstrip('_'), d,
1074 self._start, self._end)
1077 self._start, self._end)
1075
1078
1076 class fullreposet(_spanset):
1079 class fullreposet(_spanset):
1077 """a set containing all revisions in the repo
1080 """a set containing all revisions in the repo
1078
1081
1079 This class exists to host special optimization and magic to handle virtual
1082 This class exists to host special optimization and magic to handle virtual
1080 revisions such as "null".
1083 revisions such as "null".
1081 """
1084 """
1082
1085
1083 def __init__(self, repo):
1086 def __init__(self, repo):
1084 super(fullreposet, self).__init__(0, len(repo), True,
1087 super(fullreposet, self).__init__(0, len(repo), True,
1085 repo.changelog.filteredrevs)
1088 repo.changelog.filteredrevs)
1086
1089
1087 def __and__(self, other):
1090 def __and__(self, other):
1088 """As self contains the whole repo, all of the other set should also be
1091 """As self contains the whole repo, all of the other set should also be
1089 in self. Therefore `self & other = other`.
1092 in self. Therefore `self & other = other`.
1090
1093
1091 This boldly assumes the other contains valid revs only.
1094 This boldly assumes the other contains valid revs only.
1092 """
1095 """
1093 # other not a smartset, make is so
1096 # other not a smartset, make is so
1094 if not util.safehasattr(other, 'isascending'):
1097 if not util.safehasattr(other, 'isascending'):
1095 # filter out hidden revision
1098 # filter out hidden revision
1096 # (this boldly assumes all smartset are pure)
1099 # (this boldly assumes all smartset are pure)
1097 #
1100 #
1098 # `other` was used with "&", let's assume this is a set like
1101 # `other` was used with "&", let's assume this is a set like
1099 # object.
1102 # object.
1100 other = baseset(other - self._hiddenrevs)
1103 other = baseset(other - self._hiddenrevs)
1101
1104
1102 other.sort(reverse=self.isdescending())
1105 other.sort(reverse=self.isdescending())
1103 return other
1106 return other
1104
1107
1105 def prettyformat(revs):
1108 def prettyformat(revs):
1106 lines = []
1109 lines = []
1107 rs = repr(revs)
1110 rs = repr(revs)
1108 p = 0
1111 p = 0
1109 while p < len(rs):
1112 while p < len(rs):
1110 q = rs.find('<', p + 1)
1113 q = rs.find('<', p + 1)
1111 if q < 0:
1114 if q < 0:
1112 q = len(rs)
1115 q = len(rs)
1113 l = rs.count('<', 0, p) - rs.count('>', 0, p)
1116 l = rs.count('<', 0, p) - rs.count('>', 0, p)
1114 assert l >= 0
1117 assert l >= 0
1115 lines.append((l, rs[p:q].rstrip()))
1118 lines.append((l, rs[p:q].rstrip()))
1116 p = q
1119 p = q
1117 return '\n'.join(' ' * l + s for l, s in lines)
1120 return '\n'.join(' ' * l + s for l, s in lines)
General Comments 0
You need to be logged in to leave comments. Login now