Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/revset.py @ 30913: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 41e31a6f5296
children 11c253997b0e
comparison
equal deleted inserted replaced
30912:b6c051cd1231 30913:1be65deb3d54
24 pathutil, 24 pathutil,
25 phases, 25 phases,
26 pycompat, 26 pycompat,
27 registrar, 27 registrar,
28 repoview, 28 repoview,
29 smartset,
29 util, 30 util,
30 ) 31 )
32
33 baseset = smartset.baseset
34 generatorset = smartset.generatorset
35 spanset = smartset.spanset
36 fullreposet = smartset.fullreposet
31 37
32 def _revancestors(repo, revs, followfirst): 38 def _revancestors(repo, revs, followfirst):
33 """Like revlog.ancestors(), but supports followfirst.""" 39 """Like revlog.ancestors(), but supports followfirst."""
34 if followfirst: 40 if followfirst:
35 cut = 1 41 cut = 1
2938 funcs |= funcsused(s) 2944 funcs |= funcsused(s)
2939 if tree[0] == 'func': 2945 if tree[0] == 'func':
2940 funcs.add(tree[1][1]) 2946 funcs.add(tree[1][1])
2941 return funcs 2947 return funcs
2942 2948
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
3904 def loadpredicate(ui, extname, registrarobj): 2949 def loadpredicate(ui, extname, registrarobj):
3905 """Load revset predicates from specified registrarobj 2950 """Load revset predicates from specified registrarobj
3906 """ 2951 """
3907 for name, func in registrarobj._table.iteritems(): 2952 for name, func in registrarobj._table.iteritems():
3908 symbols[name] = func 2953 symbols[name] = func