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