2943 def _formatsetrepr(r):

  2944     """Format an optional printable representation of a set

  2945 

  2946     ========  =================================

  2947     type(r)   example

  2948     ========  =================================

  2949     tuple     ('<not %r>', other)

  2950     str       '<branch closed>'

  2951     callable  lambda: '<branch %r>' % sorted(b)

  2952     object    other

  2953     ========  =================================

  2954     """

  2955     if r is None:

  2956         return ''

  2957     elif isinstance(r, tuple):

  2958         return r[0] % r[1:]

  2959     elif isinstance(r, str):

  2960         return r

  2961     elif callable(r):

  2962         return r()

  2963     else:

  2964         return repr(r)

  2965 

  2966 class abstractsmartset(object):

  2967 

  2968     def __nonzero__(self):

  2969         """True if the smartset is not empty"""

  2970         raise NotImplementedError()

  2971 

  2972     def __contains__(self, rev):

  2973         """provide fast membership testing"""

  2974         raise NotImplementedError()

  2975 

  2976     def __iter__(self):

  2977         """iterate the set in the order it is supposed to be iterated"""

  2978         raise NotImplementedError()

  2979 

  2980     # Attributes containing a function to perform a fast iteration in a given

  2981     # direction. A smartset can have none, one, or both defined.

  2982     #

  2983     # Default value is None instead of a function returning None to avoid

  2984     # initializing an iterator just for testing if a fast method exists.

  2985     fastasc = None

  2986     fastdesc = None

  2987 

  2988     def isascending(self):

  2989         """True if the set will iterate in ascending order"""

  2990         raise NotImplementedError()

  2991 

  2992     def isdescending(self):

  2993         """True if the set will iterate in descending order"""

  2994         raise NotImplementedError()

  2995 

  2996     def istopo(self):

  2997         """True if the set will iterate in topographical order"""

  2998         raise NotImplementedError()

  2999 

  3000     def min(self):

  3001         """return the minimum element in the set"""

  3002         if self.fastasc is None:

  3003             v = min(self)

  3004         else:

  3005             for v in self.fastasc():

  3006                 break

  3007             else:

  3008                 raise ValueError('arg is an empty sequence')

  3009         self.min = lambda: v

  3010         return v

  3011 

  3012     def max(self):

  3013         """return the maximum element in the set"""

  3014         if self.fastdesc is None:

  3015             return max(self)

  3016         else:

  3017             for v in self.fastdesc():

  3018                 break

  3019             else:

  3020                 raise ValueError('arg is an empty sequence')

  3021         self.max = lambda: v

  3022         return v

  3023 

  3024     def first(self):

  3025         """return the first element in the set (user iteration perspective)

  3026 

  3027         Return None if the set is empty"""

  3028         raise NotImplementedError()

  3029 

  3030     def last(self):

  3031         """return the last element in the set (user iteration perspective)

  3032 

  3033         Return None if the set is empty"""

  3034         raise NotImplementedError()

  3035 

  3036     def __len__(self):

  3037         """return the length of the smartsets

  3038 

  3039         This can be expensive on smartset that could be lazy otherwise."""

  3040         raise NotImplementedError()

  3041 

  3042     def reverse(self):

  3043         """reverse the expected iteration order"""

  3044         raise NotImplementedError()

  3045 

  3046     def sort(self, reverse=True):

  3047         """get the set to iterate in an ascending or descending order"""

  3048         raise NotImplementedError()

  3049 

  3050     def __and__(self, other):

  3051         """Returns a new object with the intersection of the two collections.

  3052 

  3053         This is part of the mandatory API for smartset."""

  3054         if isinstance(other, fullreposet):

  3055             return self

  3056         return self.filter(other.__contains__, condrepr=other, cache=False)

  3057 

  3058     def __add__(self, other):

  3059         """Returns a new object with the union of the two collections.

  3060 

  3061         This is part of the mandatory API for smartset."""

  3062         return addset(self, other)

  3063 

  3064     def __sub__(self, other):

  3065         """Returns a new object with the substraction of the two collections.

  3066 

  3067         This is part of the mandatory API for smartset."""

  3068         c = other.__contains__

  3069         return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),

  3070                            cache=False)

  3071 

  3072     def filter(self, condition, condrepr=None, cache=True):

  3073         """Returns this smartset filtered by condition as a new smartset.

  3074 

  3075         `condition` is a callable which takes a revision number and returns a

  3076         boolean. Optional `condrepr` provides a printable representation of

  3077         the given `condition`.

  3078 

  3079         This is part of the mandatory API for smartset."""

  3080         # builtin cannot be cached. but do not needs to

  3081         if cache and util.safehasattr(condition, 'func_code'):

  3082             condition = util.cachefunc(condition)

  3083         return filteredset(self, condition, condrepr)

  3084 

  3085 class baseset(abstractsmartset):

  3086     """Basic data structure that represents a revset and contains the basic

  3087     operation that it should be able to perform.

  3088 

  3089     Every method in this class should be implemented by any smartset class.

  3090     """

  3091     def __init__(self, data=(), datarepr=None, istopo=False):

  3092         """

  3093         datarepr: a tuple of (format, obj, ...), a function or an object that

  3094                   provides a printable representation of the given data.

  3095         """

  3096         self._ascending = None

  3097         self._istopo = istopo

  3098         if not isinstance(data, list):

  3099             if isinstance(data, set):

  3100                 self._set = data

  3101                 # set has no order we pick one for stability purpose

  3102                 self._ascending = True

  3103             data = list(data)

  3104         self._list = data

  3105         self._datarepr = datarepr

  3106 

  3107     @util.propertycache

  3108     def _set(self):

  3109         return set(self._list)

  3110 

  3111     @util.propertycache

  3112     def _asclist(self):

  3113         asclist = self._list[:]

  3114         asclist.sort()

  3115         return asclist

  3116 

  3117     def __iter__(self):

  3118         if self._ascending is None:

  3119             return iter(self._list)

  3120         elif self._ascending:

  3121             return iter(self._asclist)

  3122         else:

  3123             return reversed(self._asclist)

  3124 

  3125     def fastasc(self):

  3126         return iter(self._asclist)

  3127 

  3128     def fastdesc(self):

  3129         return reversed(self._asclist)

  3130 

  3131     @util.propertycache

  3132     def __contains__(self):

  3133         return self._set.__contains__

  3134 

  3135     def __nonzero__(self):

  3136         return bool(self._list)

  3137 

  3138     def sort(self, reverse=False):

  3139         self._ascending = not bool(reverse)

  3140         self._istopo = False

  3141 

  3142     def reverse(self):

  3143         if self._ascending is None:

  3144             self._list.reverse()

  3145         else:

  3146             self._ascending = not self._ascending

  3147         self._istopo = False

  3148 

  3149     def __len__(self):

  3150         return len(self._list)

  3151 

  3152     def isascending(self):

  3153         """Returns True if the collection is ascending order, False if not.

  3154 

  3155         This is part of the mandatory API for smartset."""

  3156         if len(self) <= 1:

  3157             return True

  3158         return self._ascending is not None and self._ascending

  3159 

  3160     def isdescending(self):

  3161         """Returns True if the collection is descending order, False if not.

  3162 

  3163         This is part of the mandatory API for smartset."""

  3164         if len(self) <= 1:

  3165             return True

  3166         return self._ascending is not None and not self._ascending

  3167 

  3168     def istopo(self):

  3169         """Is the collection is in topographical order or not.

  3170 

  3171         This is part of the mandatory API for smartset."""

  3172         if len(self) <= 1:

  3173             return True

  3174         return self._istopo

  3175 

  3176     def first(self):

  3177         if self:

  3178             if self._ascending is None:

  3179                 return self._list[0]

  3180             elif self._ascending:

  3181                 return self._asclist[0]

  3182             else:

  3183                 return self._asclist[-1]

  3184         return None

  3185 

  3186     def last(self):

  3187         if self:

  3188             if self._ascending is None:

  3189                 return self._list[-1]

  3190             elif self._ascending:

  3191                 return self._asclist[-1]

  3192             else:

  3193                 return self._asclist[0]

  3194         return None

  3195 

  3196     def __repr__(self):

  3197         d = {None: '', False: '-', True: '+'}[self._ascending]

  3198         s = _formatsetrepr(self._datarepr)

  3199         if not s:

  3200             l = self._list

  3201             # if _list has been built from a set, it might have a different

  3202             # order from one python implementation to another.

  3203             # We fallback to the sorted version for a stable output.

  3204             if self._ascending is not None:

  3205                 l = self._asclist

  3206             s = repr(l)

  3207         return '<%s%s %s>' % (type(self).__name__, d, s)

  3208 

  3209 class filteredset(abstractsmartset):

  3210     """Duck type for baseset class which iterates lazily over the revisions in

  3211     the subset and contains a function which tests for membership in the

  3212     revset

  3213     """

  3214     def __init__(self, subset, condition=lambda x: True, condrepr=None):

  3215         """

  3216         condition: a function that decide whether a revision in the subset

  3217                    belongs to the revset or not.

  3218         condrepr: a tuple of (format, obj, ...), a function or an object that

  3219                   provides a printable representation of the given condition.

  3220         """

  3221         self._subset = subset

  3222         self._condition = condition

  3223         self._condrepr = condrepr

  3224 

  3225     def __contains__(self, x):

  3226         return x in self._subset and self._condition(x)

  3227 

  3228     def __iter__(self):

  3229         return self._iterfilter(self._subset)

  3230 

  3231     def _iterfilter(self, it):

  3232         cond = self._condition

  3233         for x in it:

  3234             if cond(x):

  3235                 yield x

  3236 

  3237     @property

  3238     def fastasc(self):

  3239         it = self._subset.fastasc

  3240         if it is None:

  3241             return None

  3242         return lambda: self._iterfilter(it())

  3243 

  3244     @property

  3245     def fastdesc(self):

  3246         it = self._subset.fastdesc

  3247         if it is None:

  3248             return None

  3249         return lambda: self._iterfilter(it())

  3250 

  3251     def __nonzero__(self):

  3252         fast = None

  3253         candidates = [self.fastasc if self.isascending() else None,

  3254                       self.fastdesc if self.isdescending() else None,

  3255                       self.fastasc,

  3256                       self.fastdesc]

  3257         for candidate in candidates:

  3258             if candidate is not None:

  3259                 fast = candidate

  3260                 break

  3261 

  3262         if fast is not None:

  3263             it = fast()

  3264         else:

  3265             it = self

  3266 

  3267         for r in it:

  3268             return True

  3269         return False

  3270 

  3271     def __len__(self):

  3272         # Basic implementation to be changed in future patches.

  3273         # until this gets improved, we use generator expression

  3274         # here, since list comprehensions are free to call __len__ again

  3275         # causing infinite recursion

  3276         l = baseset(r for r in self)

  3277         return len(l)

  3278 

  3279     def sort(self, reverse=False):

  3280         self._subset.sort(reverse=reverse)

  3281 

  3282     def reverse(self):

  3283         self._subset.reverse()

  3284 

  3285     def isascending(self):

  3286         return self._subset.isascending()

  3287 

  3288     def isdescending(self):

  3289         return self._subset.isdescending()

  3290 

  3291     def istopo(self):

  3292         return self._subset.istopo()

  3293 

  3294     def first(self):

  3295         for x in self:

  3296             return x

  3297         return None

  3298 

  3299     def last(self):

  3300         it = None

  3301         if self.isascending():

  3302             it = self.fastdesc

  3303         elif self.isdescending():

  3304             it = self.fastasc

  3305         if it is not None:

  3306             for x in it():

  3307                 return x

  3308             return None #empty case

  3309         else:

  3310             x = None

  3311             for x in self:

  3312                 pass

  3313             return x

  3314 

  3315     def __repr__(self):

  3316         xs = [repr(self._subset)]

  3317         s = _formatsetrepr(self._condrepr)

  3318         if s:

  3319             xs.append(s)

  3320         return '<%s %s>' % (type(self).__name__, ', '.join(xs))

  3321 

  3322 def _iterordered(ascending, iter1, iter2):

  3323     """produce an ordered iteration from two iterators with the same order

  3324 

  3325     The ascending is used to indicated the iteration direction.

  3326     """

  3327     choice = max

  3328     if ascending:

  3329         choice = min

  3330 

  3331     val1 = None

  3332     val2 = None

  3333     try:

  3334         # Consume both iterators in an ordered way until one is empty

  3335         while True:

  3336             if val1 is None:

  3337                 val1 = next(iter1)

  3338             if val2 is None:

  3339                 val2 = next(iter2)

  3340             n = choice(val1, val2)

  3341             yield n

  3342             if val1 == n:

  3343                 val1 = None

  3344             if val2 == n:

  3345                 val2 = None

  3346     except StopIteration:

  3347         # Flush any remaining values and consume the other one

  3348         it = iter2

  3349         if val1 is not None:

  3350             yield val1

  3351             it = iter1

  3352         elif val2 is not None:

  3353             # might have been equality and both are empty

  3354             yield val2

  3355         for val in it:

  3356             yield val

  3357 

  3358 class addset(abstractsmartset):

  3359     """Represent the addition of two sets

  3360 

  3361     Wrapper structure for lazily adding two structures without losing much

  3362     performance on the __contains__ method

  3363 

  3364     If the ascending attribute is set, that means the two structures are

  3365     ordered in either an ascending or descending way. Therefore, we can add

  3366     them maintaining the order by iterating over both at the same time

  3367 

  3368     >>> xs = baseset([0, 3, 2])

  3369     >>> ys = baseset([5, 2, 4])

  3370 

  3371     >>> rs = addset(xs, ys)

  3372     >>> bool(rs), 0 in rs, 1 in rs, 5 in rs, rs.first(), rs.last()

  3373     (True, True, False, True, 0, 4)

  3374     >>> rs = addset(xs, baseset([]))

  3375     >>> bool(rs), 0 in rs, 1 in rs, rs.first(), rs.last()

  3376     (True, True, False, 0, 2)

  3377     >>> rs = addset(baseset([]), baseset([]))

  3378     >>> bool(rs), 0 in rs, rs.first(), rs.last()

  3379     (False, False, None, None)

  3380 

  3381     iterate unsorted:

  3382     >>> rs = addset(xs, ys)

  3383     >>> # (use generator because pypy could call len())

  3384     >>> list(x for x in rs)  # without _genlist

  3385     [0, 3, 2, 5, 4]

  3386     >>> assert not rs._genlist

  3387     >>> len(rs)

  3388     5

  3389     >>> [x for x in rs]  # with _genlist

  3390     [0, 3, 2, 5, 4]

  3391     >>> assert rs._genlist

  3392 

  3393     iterate ascending:

  3394     >>> rs = addset(xs, ys, ascending=True)

  3395     >>> # (use generator because pypy could call len())

  3396     >>> list(x for x in rs), list(x for x in rs.fastasc())  # without _asclist

  3397     ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])

  3398     >>> assert not rs._asclist

  3399     >>> len(rs)

  3400     5

  3401     >>> [x for x in rs], [x for x in rs.fastasc()]

  3402     ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])

  3403     >>> assert rs._asclist

  3404 

  3405     iterate descending:

  3406     >>> rs = addset(xs, ys, ascending=False)

  3407     >>> # (use generator because pypy could call len())

  3408     >>> list(x for x in rs), list(x for x in rs.fastdesc())  # without _asclist

  3409     ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])

  3410     >>> assert not rs._asclist

  3411     >>> len(rs)

  3412     5

  3413     >>> [x for x in rs], [x for x in rs.fastdesc()]

  3414     ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])

  3415     >>> assert rs._asclist

  3416 

  3417     iterate ascending without fastasc:

  3418     >>> rs = addset(xs, generatorset(ys), ascending=True)

  3419     >>> assert rs.fastasc is None

  3420     >>> [x for x in rs]

  3421     [0, 2, 3, 4, 5]

  3422 

  3423     iterate descending without fastdesc:

  3424     >>> rs = addset(generatorset(xs), ys, ascending=False)

  3425     >>> assert rs.fastdesc is None

  3426     >>> [x for x in rs]

  3427     [5, 4, 3, 2, 0]

  3428     """

  3429     def __init__(self, revs1, revs2, ascending=None):

  3430         self._r1 = revs1

  3431         self._r2 = revs2

  3432         self._iter = None

  3433         self._ascending = ascending

  3434         self._genlist = None

  3435         self._asclist = None

  3436 

  3437     def __len__(self):

  3438         return len(self._list)

  3439 

  3440     def __nonzero__(self):

  3441         return bool(self._r1) or bool(self._r2)

  3442 

  3443     @util.propertycache

  3444     def _list(self):

  3445         if not self._genlist:

  3446             self._genlist = baseset(iter(self))

  3447         return self._genlist

  3448 

  3449     def __iter__(self):

  3450         """Iterate over both collections without repeating elements

  3451 

  3452         If the ascending attribute is not set, iterate over the first one and

  3453         then over the second one checking for membership on the first one so we

  3454         dont yield any duplicates.

  3455 

  3456         If the ascending attribute is set, iterate over both collections at the

  3457         same time, yielding only one value at a time in the given order.

  3458         """

  3459         if self._ascending is None:

  3460             if self._genlist:

  3461                 return iter(self._genlist)

  3462             def arbitraryordergen():

  3463                 for r in self._r1:

  3464                     yield r

  3465                 inr1 = self._r1.__contains__

  3466                 for r in self._r2:

  3467                     if not inr1(r):

  3468                         yield r

  3469             return arbitraryordergen()

  3470         # try to use our own fast iterator if it exists

  3471         self._trysetasclist()

  3472         if self._ascending:

  3473             attr = 'fastasc'

  3474         else:

  3475             attr = 'fastdesc'

  3476         it = getattr(self, attr)

  3477         if it is not None:

  3478             return it()

  3479         # maybe half of the component supports fast

  3480         # get iterator for _r1

  3481         iter1 = getattr(self._r1, attr)

  3482         if iter1 is None:

  3483             # let's avoid side effect (not sure it matters)

  3484             iter1 = iter(sorted(self._r1, reverse=not self._ascending))

  3485         else:

  3486             iter1 = iter1()

  3487         # get iterator for _r2

  3488         iter2 = getattr(self._r2, attr)

  3489         if iter2 is None:

  3490             # let's avoid side effect (not sure it matters)

  3491             iter2 = iter(sorted(self._r2, reverse=not self._ascending))

  3492         else:

  3493             iter2 = iter2()

  3494         return _iterordered(self._ascending, iter1, iter2)

  3495 

  3496     def _trysetasclist(self):

  3497         """populate the _asclist attribute if possible and necessary"""

  3498         if self._genlist is not None and self._asclist is None:

  3499             self._asclist = sorted(self._genlist)

  3500 

  3501     @property

  3502     def fastasc(self):

  3503         self._trysetasclist()

  3504         if self._asclist is not None:

  3505             return self._asclist.__iter__

  3506         iter1 = self._r1.fastasc

  3507         iter2 = self._r2.fastasc

  3508         if None in (iter1, iter2):

  3509             return None

  3510         return lambda: _iterordered(True, iter1(), iter2())

  3511 

  3512     @property

  3513     def fastdesc(self):

  3514         self._trysetasclist()

  3515         if self._asclist is not None:

  3516             return self._asclist.__reversed__

  3517         iter1 = self._r1.fastdesc

  3518         iter2 = self._r2.fastdesc

  3519         if None in (iter1, iter2):

  3520             return None

  3521         return lambda: _iterordered(False, iter1(), iter2())

  3522 

  3523     def __contains__(self, x):

  3524         return x in self._r1 or x in self._r2

  3525 

  3526     def sort(self, reverse=False):

  3527         """Sort the added set

  3528 

  3529         For this we use the cached list with all the generated values and if we

  3530         know they are ascending or descending we can sort them in a smart way.

  3531         """

  3532         self._ascending = not reverse

  3533 

  3534     def isascending(self):

  3535         return self._ascending is not None and self._ascending

  3536 

  3537     def isdescending(self):

  3538         return self._ascending is not None and not self._ascending

  3539 

  3540     def istopo(self):

  3541         # not worth the trouble asserting if the two sets combined are still

  3542         # in topographical order. Use the sort() predicate to explicitly sort

  3543         # again instead.

  3544         return False

  3545 

  3546     def reverse(self):

  3547         if self._ascending is None:

  3548             self._list.reverse()

  3549         else:

  3550             self._ascending = not self._ascending

  3551 

  3552     def first(self):

  3553         for x in self:

  3554             return x

  3555         return None

  3556 

  3557     def last(self):

  3558         self.reverse()

  3559         val = self.first()

  3560         self.reverse()

  3561         return val

  3562 

  3563     def __repr__(self):

  3564         d = {None: '', False: '-', True: '+'}[self._ascending]

  3565         return '<%s%s %r, %r>' % (type(self).__name__, d, self._r1, self._r2)

  3566 

  3567 class generatorset(abstractsmartset):

  3568     """Wrap a generator for lazy iteration

  3569 

  3570     Wrapper structure for generators that provides lazy membership and can

  3571     be iterated more than once.

  3572     When asked for membership it generates values until either it finds the

  3573     requested one or has gone through all the elements in the generator

  3574     """

  3575     def __init__(self, gen, iterasc=None):

  3576         """

  3577         gen: a generator producing the values for the generatorset.

  3578         """

  3579         self._gen = gen

  3580         self._asclist = None

  3581         self._cache = {}

  3582         self._genlist = []

  3583         self._finished = False

  3584         self._ascending = True

  3585         if iterasc is not None:

  3586             if iterasc:

  3587                 self.fastasc = self._iterator

  3588                 self.__contains__ = self._asccontains

  3589             else:

  3590                 self.fastdesc = self._iterator

  3591                 self.__contains__ = self._desccontains

  3592 

  3593     def __nonzero__(self):

  3594         # Do not use 'for r in self' because it will enforce the iteration

  3595         # order (default ascending), possibly unrolling a whole descending

  3596         # iterator.

  3597         if self._genlist:

  3598             return True

  3599         for r in self._consumegen():

  3600             return True

  3601         return False

  3602 

  3603     def __contains__(self, x):

  3604         if x in self._cache:

  3605             return self._cache[x]

  3606 

  3607         # Use new values only, as existing values would be cached.

  3608         for l in self._consumegen():

  3609             if l == x:

  3610                 return True

  3611 

  3612         self._cache[x] = False

  3613         return False

  3614 

  3615     def _asccontains(self, x):

  3616         """version of contains optimised for ascending generator"""

  3617         if x in self._cache:

  3618             return self._cache[x]

  3619 

  3620         # Use new values only, as existing values would be cached.

  3621         for l in self._consumegen():

  3622             if l == x:

  3623                 return True

  3624             if l > x:

  3625                 break

  3626 

  3627         self._cache[x] = False

  3628         return False

  3629 

  3630     def _desccontains(self, x):

  3631         """version of contains optimised for descending generator"""

  3632         if x in self._cache:

  3633             return self._cache[x]

  3634 

  3635         # Use new values only, as existing values would be cached.

  3636         for l in self._consumegen():

  3637             if l == x:

  3638                 return True

  3639             if l < x:

  3640                 break

  3641 

  3642         self._cache[x] = False

  3643         return False

  3644 

  3645     def __iter__(self):

  3646         if self._ascending:

  3647             it = self.fastasc

  3648         else:

  3649             it = self.fastdesc

  3650         if it is not None:

  3651             return it()

  3652         # we need to consume the iterator

  3653         for x in self._consumegen():

  3654             pass

  3655         # recall the same code

  3656         return iter(self)

  3657 

  3658     def _iterator(self):

  3659         if self._finished:

  3660             return iter(self._genlist)

  3661 

  3662         # We have to use this complex iteration strategy to allow multiple

  3663         # iterations at the same time. We need to be able to catch revision

  3664         # removed from _consumegen and added to genlist in another instance.

  3665         #

  3666         # Getting rid of it would provide an about 15% speed up on this

  3667         # iteration.

  3668         genlist = self._genlist

  3669         nextrev = self._consumegen().next

  3670         _len = len # cache global lookup

  3671         def gen():

  3672             i = 0

  3673             while True:

  3674                 if i < _len(genlist):

  3675                     yield genlist[i]

  3676                 else:

  3677                     yield nextrev()

  3678                 i += 1

  3679         return gen()

  3680 

  3681     def _consumegen(self):

  3682         cache = self._cache

  3683         genlist = self._genlist.append

  3684         for item in self._gen:

  3685             cache[item] = True

  3686             genlist(item)

  3687             yield item

  3688         if not self._finished:

  3689             self._finished = True

  3690             asc = self._genlist[:]

  3691             asc.sort()

  3692             self._asclist = asc

  3693             self.fastasc = asc.__iter__

  3694             self.fastdesc = asc.__reversed__

  3695 

  3696     def __len__(self):

  3697         for x in self._consumegen():

  3698             pass

  3699         return len(self._genlist)

  3700 

  3701     def sort(self, reverse=False):

  3702         self._ascending = not reverse

  3703 

  3704     def reverse(self):

  3705         self._ascending = not self._ascending

  3706 

  3707     def isascending(self):

  3708         return self._ascending

  3709 

  3710     def isdescending(self):

  3711         return not self._ascending

  3712 

  3713     def istopo(self):

  3714         # not worth the trouble asserting if the two sets combined are still

  3715         # in topographical order. Use the sort() predicate to explicitly sort

  3716         # again instead.

  3717         return False

  3718 

  3719     def first(self):

  3720         if self._ascending:

  3721             it = self.fastasc

  3722         else:

  3723             it = self.fastdesc

  3724         if it is None:

  3725             # we need to consume all and try again

  3726             for x in self._consumegen():

  3727                 pass

  3728             return self.first()

  3729         return next(it(), None)

  3730 

  3731     def last(self):

  3732         if self._ascending:

  3733             it = self.fastdesc

  3734         else:

  3735             it = self.fastasc

  3736         if it is None:

  3737             # we need to consume all and try again

  3738             for x in self._consumegen():

  3739                 pass

  3740             return self.first()

  3741         return next(it(), None)

  3742 

  3743     def __repr__(self):

  3744         d = {False: '-', True: '+'}[self._ascending]

  3745         return '<%s%s>' % (type(self).__name__, d)

  3746 

  3747 class spanset(abstractsmartset):

  3748     """Duck type for baseset class which represents a range of revisions and

  3749     can work lazily and without having all the range in memory

  3750 

  3751     Note that spanset(x, y) behave almost like xrange(x, y) except for two

  3752     notable points:

  3753     - when x < y it will be automatically descending,

  3754     - revision filtered with this repoview will be skipped.

  3755 

  3756     """

  3757     def __init__(self, repo, start=0, end=None):

  3758         """

  3759         start: first revision included the set

  3760                (default to 0)

  3761         end:   first revision excluded (last+1)

  3762                (default to len(repo)

  3763 

  3764         Spanset will be descending if `end` < `start`.

  3765         """

  3766         if end is None:

  3767             end = len(repo)

  3768         self._ascending = start <= end

  3769         if not self._ascending:

  3770             start, end = end + 1, start +1

  3771         self._start = start

  3772         self._end = end

  3773         self._hiddenrevs = repo.changelog.filteredrevs

  3774 

  3775     def sort(self, reverse=False):

  3776         self._ascending = not reverse

  3777 

  3778     def reverse(self):

  3779         self._ascending = not self._ascending

  3780 

  3781     def istopo(self):

  3782         # not worth the trouble asserting if the two sets combined are still

  3783         # in topographical order. Use the sort() predicate to explicitly sort

  3784         # again instead.

  3785         return False

  3786 

  3787     def _iterfilter(self, iterrange):

  3788         s = self._hiddenrevs

  3789         for r in iterrange:

  3790             if r not in s:

  3791                 yield r

  3792 

  3793     def __iter__(self):

  3794         if self._ascending:

  3795             return self.fastasc()

  3796         else:

  3797             return self.fastdesc()

  3798 

  3799     def fastasc(self):

  3800         iterrange = xrange(self._start, self._end)

  3801         if self._hiddenrevs:

  3802             return self._iterfilter(iterrange)

  3803         return iter(iterrange)

  3804 

  3805     def fastdesc(self):

  3806         iterrange = xrange(self._end - 1, self._start - 1, -1)

  3807         if self._hiddenrevs:

  3808             return self._iterfilter(iterrange)

  3809         return iter(iterrange)

  3810 

  3811     def __contains__(self, rev):

  3812         hidden = self._hiddenrevs

  3813         return ((self._start <= rev < self._end)

  3814                 and not (hidden and rev in hidden))

  3815 

  3816     def __nonzero__(self):

  3817         for r in self:

  3818             return True

  3819         return False

  3820 

  3821     def __len__(self):

  3822         if not self._hiddenrevs:

  3823             return abs(self._end - self._start)

  3824         else:

  3825             count = 0

  3826             start = self._start

  3827             end = self._end

  3828             for rev in self._hiddenrevs:

  3829                 if (end < rev <= start) or (start <= rev < end):

  3830                     count += 1

  3831             return abs(self._end - self._start) - count

  3832 

  3833     def isascending(self):

  3834         return self._ascending

  3835 

  3836     def isdescending(self):

  3837         return not self._ascending

  3838 

  3839     def first(self):

  3840         if self._ascending:

  3841             it = self.fastasc

  3842         else:

  3843             it = self.fastdesc

  3844         for x in it():

  3845             return x

  3846         return None

  3847 

  3848     def last(self):

  3849         if self._ascending:

  3850             it = self.fastdesc

  3851         else:

  3852             it = self.fastasc

  3853         for x in it():

  3854             return x

  3855         return None

  3856 

  3857     def __repr__(self):

  3858         d = {False: '-', True: '+'}[self._ascending]

  3859         return '<%s%s %d:%d>' % (type(self).__name__, d,

  3860                                  self._start, self._end - 1)

  3861 

  3862 class fullreposet(spanset):

  3863     """a set containing all revisions in the repo

  3864 

  3865     This class exists to host special optimization and magic to handle virtual

  3866     revisions such as "null".

  3867     """

  3868 

  3869     def __init__(self, repo):

  3870         super(fullreposet, self).__init__(repo)

  3871 

  3872     def __and__(self, other):

  3873         """As self contains the whole repo, all of the other set should also be

  3874         in self. Therefore `self & other = other`.

  3875 

  3876         This boldly assumes the other contains valid revs only.

  3877         """

  3878         # other not a smartset, make is so

  3879         if not util.safehasattr(other, 'isascending'):

  3880             # filter out hidden revision

  3881             # (this boldly assumes all smartset are pure)

  3882             #

  3883             # `other` was used with "&", let's assume this is a set like

  3884             # object.

  3885             other = baseset(other - self._hiddenrevs)

  3886 

  3887         other.sort(reverse=self.isdescending())

  3888         return other

  3889 

  3890 def prettyformatset(revs):

  3891     lines = []

  3892     rs = repr(revs)

  3893     p = 0

  3894     while p < len(rs):

  3895         q = rs.find('<', p + 1)

  3896         if q < 0:

  3897             q = len(rs)

  3898         l = rs.count('<', 0, p) - rs.count('>', 0, p)

  3899         assert l >= 0

  3900         lines.append((l, rs[p:q].rstrip()))

  3901         p = q

  3902     return '\n'.join('  ' * l + s for l, s in lines)

  3903