Mercurial > public > mercurial-scm > hg

comparison mercurial/smartset.py @ 43076:2372284d9457

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
formatting: blacken the codebase This is using my patch to black (https://github.com/psf/black/pull/826) so we don't un-wrap collection literals. Done with: hg files 'set:**.py - mercurial/thirdparty/** - "contrib/python-zstandard/**"' | xargs black -S # skip-blame mass-reformatting only # no-check-commit reformats foo_bar functions Differential Revision: https://phab.mercurial-scm.org/D6971
author Augie Fackler <augie@google.com>
date Sun, 06 Oct 2019 09:45:02 -0400
parents 6309128ff61f
children 687b865b95ad
comparison
equal deleted inserted replaced
43075:57875cf423c9 43076:2372284d9457
11 encoding, 11 encoding,
12 error, 12 error,
13 pycompat, 13 pycompat,
14 util, 14 util,
15 ) 15 )
16 from .utils import ( 16 from .utils import stringutil
17 stringutil, 17
18 )
19 18
20 def _typename(o): 19 def _typename(o):
21 return pycompat.sysbytes(type(o).__name__).lstrip('_') 20 return pycompat.sysbytes(type(o).__name__).lstrip('_')
22 21
22
23 class abstractsmartset(object): 23 class abstractsmartset(object):
24
25 def __nonzero__(self): 24 def __nonzero__(self):
26 """True if the smartset is not empty""" 25 """True if the smartset is not empty"""
27 raise NotImplementedError() 26 raise NotImplementedError()
28 27
29 __bool__ = __nonzero__ 28 __bool__ = __nonzero__
123 def __sub__(self, other): 122 def __sub__(self, other):
124 """Returns a new object with the substraction of the two collections. 123 """Returns a new object with the substraction of the two collections.
125 124
126 This is part of the mandatory API for smartset.""" 125 This is part of the mandatory API for smartset."""
127 c = other.__contains__ 126 c = other.__contains__
128 return self.filter(lambda r: not c(r), condrepr=('<not %r>', other), 127 return self.filter(
129 cache=False) 128 lambda r: not c(r), condrepr=('<not %r>', other), cache=False
129 )
130 130
131 def filter(self, condition, condrepr=None, cache=True): 131 def filter(self, condition, condrepr=None, cache=True):
132 """Returns this smartset filtered by condition as a new smartset. 132 """Returns this smartset filtered by condition as a new smartset.
133 133
134 `condition` is a callable which takes a revision number and returns a 134 `condition` is a callable which takes a revision number and returns a
161 if y is None: 161 if y is None:
162 break 162 break
163 ys.append(y) 163 ys.append(y)
164 return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self)) 164 return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self))
165 165
166
166 class baseset(abstractsmartset): 167 class baseset(abstractsmartset):
167 """Basic data structure that represents a revset and contains the basic 168 """Basic data structure that represents a revset and contains the basic
168 operation that it should be able to perform. 169 operation that it should be able to perform.
169 170
170 Every method in this class should be implemented by any smartset class. 171 Every method in this class should be implemented by any smartset class.
220 >>> type(rs).__name__ 221 >>> type(rs).__name__
221 'baseset' 222 'baseset'
222 >>> rs._istopo 223 >>> rs._istopo
223 True 224 True
224 """ 225 """
226
225 def __init__(self, data=(), datarepr=None, istopo=False): 227 def __init__(self, data=(), datarepr=None, istopo=False):
226 """ 228 """
227 datarepr: a tuple of (format, obj, ...), a function or an object that 229 datarepr: a tuple of (format, obj, ...), a function or an object that
228 provides a printable representation of the given data. 230 provides a printable representation of the given data.
229 """ 231 """
340 return self._asclist[0] 342 return self._asclist[0]
341 return None 343 return None
342 344
343 def _fastsetop(self, other, op): 345 def _fastsetop(self, other, op):
344 # try to use native set operations as fast paths 346 # try to use native set operations as fast paths
345 if (type(other) is baseset and r'_set' in other.__dict__ and r'_set' in 347 if (
346 self.__dict__ and self._ascending is not None): 348 type(other) is baseset
347 s = baseset(data=getattr(self._set, op)(other._set), 349 and r'_set' in other.__dict__
348 istopo=self._istopo) 350 and r'_set' in self.__dict__
351 and self._ascending is not None
352 ):
353 s = baseset(
354 data=getattr(self._set, op)(other._set), istopo=self._istopo
355 )
349 s._ascending = self._ascending 356 s._ascending = self._ascending
350 else: 357 else:
351 s = getattr(super(baseset, self), op)(other) 358 s = getattr(super(baseset, self), op)(other)
352 return s 359 return s
353 360
381 if self._ascending is not None: 388 if self._ascending is not None:
382 l = self._asclist 389 l = self._asclist
383 s = pycompat.byterepr(l) 390 s = pycompat.byterepr(l)
384 return '<%s%s %s>' % (_typename(self), d, s) 391 return '<%s%s %s>' % (_typename(self), d, s)
385 392
393
386 class filteredset(abstractsmartset): 394 class filteredset(abstractsmartset):
387 """Duck type for baseset class which iterates lazily over the revisions in 395 """Duck type for baseset class which iterates lazily over the revisions in
388 the subset and contains a function which tests for membership in the 396 the subset and contains a function which tests for membership in the
389 revset 397 revset
390 """ 398 """
399
391 def __init__(self, subset, condition=lambda x: True, condrepr=None): 400 def __init__(self, subset, condition=lambda x: True, condrepr=None):
392 """ 401 """
393 condition: a function that decide whether a revision in the subset 402 condition: a function that decide whether a revision in the subset
394 belongs to the revset or not. 403 belongs to the revset or not.
395 condrepr: a tuple of (format, obj, ...), a function or an object that 404 condrepr: a tuple of (format, obj, ...), a function or an object that
425 return None 434 return None
426 return lambda: self._iterfilter(it()) 435 return lambda: self._iterfilter(it())
427 436
428 def __nonzero__(self): 437 def __nonzero__(self):
429 fast = None 438 fast = None
430 candidates = [self.fastasc if self.isascending() else None, 439 candidates = [
431 self.fastdesc if self.isdescending() else None, 440 self.fastasc if self.isascending() else None,
432 self.fastasc, 441 self.fastdesc if self.isdescending() else None,
433 self.fastdesc] 442 self.fastasc,
443 self.fastdesc,
444 ]
434 for candidate in candidates: 445 for candidate in candidates:
435 if candidate is not None: 446 if candidate is not None:
436 fast = candidate 447 fast = candidate
437 break 448 break
438 449
482 elif self.isdescending(): 493 elif self.isdescending():
483 it = self.fastasc 494 it = self.fastasc
484 if it is not None: 495 if it is not None:
485 for x in it(): 496 for x in it():
486 return x 497 return x
487 return None #empty case 498 return None # empty case
488 else: 499 else:
489 x = None 500 x = None
490 for x in self: 501 for x in self:
491 pass 502 pass
492 return x 503 return x
496 xs = [pycompat.byterepr(self._subset)] 507 xs = [pycompat.byterepr(self._subset)]
497 s = stringutil.buildrepr(self._condrepr) 508 s = stringutil.buildrepr(self._condrepr)
498 if s: 509 if s:
499 xs.append(s) 510 xs.append(s)
500 return '<%s %s>' % (_typename(self), ', '.join(xs)) 511 return '<%s %s>' % (_typename(self), ', '.join(xs))
512
501 513
502 def _iterordered(ascending, iter1, iter2): 514 def _iterordered(ascending, iter1, iter2):
503 """produce an ordered iteration from two iterators with the same order 515 """produce an ordered iteration from two iterators with the same order
504 516
505 The ascending is used to indicated the iteration direction. 517 The ascending is used to indicated the iteration direction.
533 # might have been equality and both are empty 545 # might have been equality and both are empty
534 yield val2 546 yield val2
535 for val in it: 547 for val in it:
536 yield val 548 yield val
537 549
550
538 class addset(abstractsmartset): 551 class addset(abstractsmartset):
539 """Represent the addition of two sets 552 """Represent the addition of two sets
540 553
541 Wrapper structure for lazily adding two structures without losing much 554 Wrapper structure for lazily adding two structures without losing much
542 performance on the __contains__ method 555 performance on the __contains__ method
604 >>> rs = addset(generatorset(xs), ys, ascending=False) 617 >>> rs = addset(generatorset(xs), ys, ascending=False)
605 >>> assert rs.fastdesc is None 618 >>> assert rs.fastdesc is None
606 >>> [x for x in rs] 619 >>> [x for x in rs]
607 [5, 4, 3, 2, 0] 620 [5, 4, 3, 2, 0]
608 """ 621 """
622
609 def __init__(self, revs1, revs2, ascending=None): 623 def __init__(self, revs1, revs2, ascending=None):
610 self._r1 = revs1 624 self._r1 = revs1
611 self._r2 = revs2 625 self._r2 = revs2
612 self._iter = None 626 self._iter = None
613 self._ascending = ascending 627 self._ascending = ascending
639 same time, yielding only one value at a time in the given order. 653 same time, yielding only one value at a time in the given order.
640 """ 654 """
641 if self._ascending is None: 655 if self._ascending is None:
642 if self._genlist: 656 if self._genlist:
643 return iter(self._genlist) 657 return iter(self._genlist)
658
644 def arbitraryordergen(): 659 def arbitraryordergen():
645 for r in self._r1: 660 for r in self._r1:
646 yield r 661 yield r
647 inr1 = self._r1.__contains__ 662 inr1 = self._r1.__contains__
648 for r in self._r2: 663 for r in self._r2:
649 if not inr1(r): 664 if not inr1(r):
650 yield r 665 yield r
666
651 return arbitraryordergen() 667 return arbitraryordergen()
652 # try to use our own fast iterator if it exists 668 # try to use our own fast iterator if it exists
653 self._trysetasclist() 669 self._trysetasclist()
654 if self._ascending: 670 if self._ascending:
655 attr = 'fastasc' 671 attr = 'fastasc'
745 @encoding.strmethod 761 @encoding.strmethod
746 def __repr__(self): 762 def __repr__(self):
747 d = {None: '', False: '-', True: '+'}[self._ascending] 763 d = {None: '', False: '-', True: '+'}[self._ascending]
748 return '<%s%s %r, %r>' % (_typename(self), d, self._r1, self._r2) 764 return '<%s%s %r, %r>' % (_typename(self), d, self._r1, self._r2)
749 765
766
750 class generatorset(abstractsmartset): 767 class generatorset(abstractsmartset):
751 """Wrap a generator for lazy iteration 768 """Wrap a generator for lazy iteration
752 769
753 Wrapper structure for generators that provides lazy membership and can 770 Wrapper structure for generators that provides lazy membership and can
754 be iterated more than once. 771 be iterated more than once.
758 >>> xs = generatorset([0, 1, 4], iterasc=True) 775 >>> xs = generatorset([0, 1, 4], iterasc=True)
759 >>> assert xs.last() == xs.last() 776 >>> assert xs.last() == xs.last()
760 >>> xs.last() # cached 777 >>> xs.last() # cached
761 4 778 4
762 """ 779 """
780
763 def __new__(cls, gen, iterasc=None): 781 def __new__(cls, gen, iterasc=None):
764 if iterasc is None: 782 if iterasc is None:
765 typ = cls 783 typ = cls
766 elif iterasc: 784 elif iterasc:
767 typ = _generatorsetasc 785 typ = _generatorsetasc
828 # 846 #
829 # Getting rid of it would provide an about 15% speed up on this 847 # Getting rid of it would provide an about 15% speed up on this
830 # iteration. 848 # iteration.
831 genlist = self._genlist 849 genlist = self._genlist
832 nextgen = self._consumegen() 850 nextgen = self._consumegen()
833 _len, _next = len, next # cache global lookup 851 _len, _next = len, next # cache global lookup
852
834 def gen(): 853 def gen():
835 i = 0 854 i = 0
836 while True: 855 while True:
837 if i < _len(genlist): 856 if i < _len(genlist):
838 yield genlist[i] 857 yield genlist[i]
840 try: 859 try:
841 yield _next(nextgen) 860 yield _next(nextgen)
842 except StopIteration: 861 except StopIteration:
843 return 862 return
844 i += 1 863 i += 1
864
845 return gen() 865 return gen()
846 866
847 def _consumegen(self): 867 def _consumegen(self):
848 cache = self._cache 868 cache = self._cache
849 genlist = self._genlist.append 869 genlist = self._genlist.append
909 @encoding.strmethod 929 @encoding.strmethod
910 def __repr__(self): 930 def __repr__(self):
911 d = {False: '-', True: '+'}[self._ascending] 931 d = {False: '-', True: '+'}[self._ascending]
912 return '<%s%s>' % (_typename(self), d) 932 return '<%s%s>' % (_typename(self), d)
913 933
934
914 class _generatorsetasc(generatorset): 935 class _generatorsetasc(generatorset):
915 """Special case of generatorset optimized for ascending generators.""" 936 """Special case of generatorset optimized for ascending generators."""
916 937
917 fastasc = generatorset._iterator 938 fastasc = generatorset._iterator
918 939
928 break 949 break
929 950
930 self._cache[x] = False 951 self._cache[x] = False
931 return False 952 return False
932 953
954
933 class _generatorsetdesc(generatorset): 955 class _generatorsetdesc(generatorset):
934 """Special case of generatorset optimized for descending generators.""" 956 """Special case of generatorset optimized for descending generators."""
935 957
936 fastdesc = generatorset._iterator 958 fastdesc = generatorset._iterator
937 959
946 if l < x: 968 if l < x:
947 break 969 break
948 970
949 self._cache[x] = False 971 self._cache[x] = False
950 return False 972 return False
973
951 974
952 def spanset(repo, start=0, end=None): 975 def spanset(repo, start=0, end=None):
953 """Create a spanset that represents a range of repository revisions 976 """Create a spanset that represents a range of repository revisions
954 977
955 start: first revision included the set (default to 0) 978 start: first revision included the set (default to 0)
962 ascending = start <= end 985 ascending = start <= end
963 if not ascending: 986 if not ascending:
964 start, end = end + 1, start + 1 987 start, end = end + 1, start + 1
965 return _spanset(start, end, ascending, repo.changelog.filteredrevs) 988 return _spanset(start, end, ascending, repo.changelog.filteredrevs)
966 989
990
967 class _spanset(abstractsmartset): 991 class _spanset(abstractsmartset):
968 """Duck type for baseset class which represents a range of revisions and 992 """Duck type for baseset class which represents a range of revisions and
969 can work lazily and without having all the range in memory 993 can work lazily and without having all the range in memory
970 994
971 Note that spanset(x, y) behave almost like xrange(x, y) except for two 995 Note that spanset(x, y) behave almost like xrange(x, y) except for two
972 notable points: 996 notable points:
973 - when x < y it will be automatically descending, 997 - when x < y it will be automatically descending,
974 - revision filtered with this repoview will be skipped. 998 - revision filtered with this repoview will be skipped.
975 999
976 """ 1000 """
1001
977 def __init__(self, start, end, ascending, hiddenrevs): 1002 def __init__(self, start, end, ascending, hiddenrevs):
978 self._start = start 1003 self._start = start
979 self._end = end 1004 self._end = end
980 self._ascending = ascending 1005 self._ascending = ascending
981 self._hiddenrevs = hiddenrevs 1006 self._hiddenrevs = hiddenrevs
1016 return self._iterfilter(iterrange) 1041 return self._iterfilter(iterrange)
1017 return iter(iterrange) 1042 return iter(iterrange)
1018 1043
1019 def __contains__(self, rev): 1044 def __contains__(self, rev):
1020 hidden = self._hiddenrevs 1045 hidden = self._hiddenrevs
1021 return ((self._start <= rev < self._end) 1046 return (self._start <= rev < self._end) and not (
1022 and not (hidden and rev in hidden)) 1047 hidden and rev in hidden
1048 )
1023 1049
1024 def __nonzero__(self): 1050 def __nonzero__(self):
1025 for r in self: 1051 for r in self:
1026 return True 1052 return True
1027 return False 1053 return False
1079 @encoding.strmethod 1105 @encoding.strmethod
1080 def __repr__(self): 1106 def __repr__(self):
1081 d = {False: '-', True: '+'}[self._ascending] 1107 d = {False: '-', True: '+'}[self._ascending]
1082 return '<%s%s %d:%d>' % (_typename(self), d, self._start, self._end) 1108 return '<%s%s %d:%d>' % (_typename(self), d, self._start, self._end)
1083 1109
1110
1084 class fullreposet(_spanset): 1111 class fullreposet(_spanset):
1085 """a set containing all revisions in the repo 1112 """a set containing all revisions in the repo
1086 1113
1087 This class exists to host special optimization and magic to handle virtual 1114 This class exists to host special optimization and magic to handle virtual
1088 revisions such as "null". 1115 revisions such as "null".
1089 """ 1116 """
1090 1117
1091 def __init__(self, repo): 1118 def __init__(self, repo):
1092 super(fullreposet, self).__init__(0, len(repo), True, 1119 super(fullreposet, self).__init__(
1093 repo.changelog.filteredrevs) 1120 0, len(repo), True, repo.changelog.filteredrevs
1121 )
1094 1122
1095 def __and__(self, other): 1123 def __and__(self, other):
1096 """As self contains the whole repo, all of the other set should also be 1124 """As self contains the whole repo, all of the other set should also be
1097 in self. Therefore `self & other = other`. 1125 in self. Therefore `self & other = other`.
1098 1126