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