Mercurial > hg

comparison mercurial/smartset.py @ 30881:1be65deb3d54

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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)