mercurial/smartset.py
author Gregory Szorc <gregory.szorc@gmail.com>
Tue, 27 Feb 2018 15:23:04 -0800
changeset 36612 e89959970a08
parent 36265 b44fac3a49fb
child 38261 f3033692ccef
permissions -rw-r--r--
wireproto: don't expose changegroupsubset capability if not available We just marked the changegroupsubset command as only available to version 1 of the wire transports. There is a capability of the same name of the command that indicates if the command is supported. This commit teaches the capabilities code to conditionally emit that capability depending on whether the command is available for the current transport. Most test output is reordering of capabilities. But the limited tests for version 2 of the SSH protocol do show the capability disappearing. Differential Revision: https://phab.mercurial-scm.org/D2486
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
     1
# smartset.py - data structure for revision set
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2010 Matt Mackall <mpm@selenic.com>
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
     8
from __future__ import absolute_import
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
     9
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    10
from . import (
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    11
    encoding,
32819
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
    12
    error,
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    13
    pycompat,
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    14
    util,
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    15
)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    16
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    17
def _formatsetrepr(r):
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    18
    """Format an optional printable representation of a set
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    19
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    20
    ========  =================================
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    21
    type(r)   example
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    22
    ========  =================================
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    23
    tuple     ('<not %r>', other)
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    24
    bytes     '<branch closed>'
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    25
    callable  lambda: '<branch %r>' % sorted(b)
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    26
    object    other
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    27
    ========  =================================
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    28
    """
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    29
    if r is None:
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    30
        return ''
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    31
    elif isinstance(r, tuple):
35904
fc44c2657dc5 py3: drop b'' from repr() of smartset
Yuya Nishihara <yuya@tcha.org>
parents: 35901
diff changeset
    32
        return r[0] % util.rapply(pycompat.maybebytestr, r[1:])
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    33
    elif isinstance(r, bytes):
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    34
        return r
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    35
    elif callable(r):
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    36
        return r()
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    37
    else:
36265
b44fac3a49fb py3: factor out byterepr() which returns an asciified value on py3
Yuya Nishihara <yuya@tcha.org>
parents: 35904
diff changeset
    38
        return pycompat.byterepr(r)
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    39
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    40
def _typename(o):
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
    41
    return pycompat.sysbytes(type(o).__name__).lstrip('_')
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
    42
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    43
class abstractsmartset(object):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    44
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    45
    def __nonzero__(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    46
        """True if the smartset is not empty"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    47
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    48
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
    49
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
    50
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    51
    def __contains__(self, rev):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    52
        """provide fast membership testing"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    53
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    54
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    55
    def __iter__(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    56
        """iterate the set in the order it is supposed to be iterated"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    57
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    58
22716
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    59
    # Attributes containing a function to perform a fast iteration in a given
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    60
    # direction. A smartset can have none, one, or both defined.
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    61
    #
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    62
    # Default value is None instead of a function returning None to avoid
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    63
    # initializing an iterator just for testing if a fast method exists.
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    64
    fastasc = None
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    65
    fastdesc = None
6877ba8d85ff abstractsmartset: document the `fastasc` and `fastdesc` attributes/methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22715
diff changeset
    66
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    67
    def isascending(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    68
        """True if the set will iterate in ascending order"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    69
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    70
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    71
    def isdescending(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    72
        """True if the set will iterate in descending order"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    73
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    74
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
    75
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
    76
        """True if the set will iterate in topographical order"""
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
    77
        raise NotImplementedError()
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
    78
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    79
    def min(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    80
        """return the minimum element in the set"""
30227
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    81
        if self.fastasc is None:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    82
            v = min(self)
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    83
        else:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    84
            for v in self.fastasc():
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    85
                break
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    86
            else:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    87
                raise ValueError('arg is an empty sequence')
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    88
        self.min = lambda: v
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    89
        return v
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    90
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    91
    def max(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
    92
        """return the maximum element in the set"""
30227
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    93
        if self.fastdesc is None:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    94
            return max(self)
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    95
        else:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    96
            for v in self.fastdesc():
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    97
                break
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    98
            else:
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
    99
                raise ValueError('arg is an empty sequence')
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
   100
        self.max = lambda: v
5ee944b9c750 revset: don't cache abstractsmartset min/max invocations infinitely
Mads Kiilerich <madski@unity3d.com>
parents: 30205
diff changeset
   101
        return v
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   102
22808
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   103
    def first(self):
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   104
        """return the first element in the set (user iteration perspective)
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   105
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   106
        Return None if the set is empty"""
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   107
        raise NotImplementedError()
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   108
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   109
    def last(self):
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   110
        """return the last element in the set (user iteration perspective)
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   111
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   112
        Return None if the set is empty"""
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   113
        raise NotImplementedError()
228b0aafb1ce smartset: add first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22805
diff changeset
   114
22995
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   115
    def __len__(self):
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   116
        """return the length of the smartsets
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   117
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   118
        This can be expensive on smartset that could be lazy otherwise."""
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   119
        raise NotImplementedError()
2587631c5f8a revset: make __len__ part of the offical API
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22944
diff changeset
   120
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   121
    def reverse(self):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   122
        """reverse the expected iteration order"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   123
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   124
33072
6d767d62b25e smartset: fix default value of abstractsmartset.sort()
Yuya Nishihara <yuya@tcha.org>
parents: 32977
diff changeset
   125
    def sort(self, reverse=False):
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   126
        """get the set to iterate in an ascending or descending order"""
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   127
        raise NotImplementedError()
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   128
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   129
    def __and__(self, other):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   130
        """Returns a new object with the intersection of the two collections.
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   131
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   132
        This is part of the mandatory API for smartset."""
24459
7d369fae098e revset: optimize "x & fullreposet" case
Yuya Nishihara <yuya@tcha.org>
parents: 24458
diff changeset
   133
        if isinstance(other, fullreposet):
7d369fae098e revset: optimize "x & fullreposet" case
Yuya Nishihara <yuya@tcha.org>
parents: 24458
diff changeset
   134
            return self
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   135
        return self.filter(other.__contains__, condrepr=other, cache=False)
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   136
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   137
    def __add__(self, other):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   138
        """Returns a new object with the union of the two collections.
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   139
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   140
        This is part of the mandatory API for smartset."""
22861
546fa6576815 revset: restore order of `or` operation as in Mercurial 2.9
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22860
diff changeset
   141
        return addset(self, other)
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   142
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   143
    def __sub__(self, other):
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   144
        """Returns a new object with the substraction of the two collections.
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   145
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   146
        This is part of the mandatory API for smartset."""
22730
aeacc2055f0d abstractsmartset: add default implementation for __sub__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22729
diff changeset
   147
        c = other.__contains__
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   148
        return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   149
                           cache=False)
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   150
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   151
    def filter(self, condition, condrepr=None, cache=True):
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   152
        """Returns this smartset filtered by condition as a new smartset.
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   153
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   154
        `condition` is a callable which takes a revision number and returns a
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   155
        boolean. Optional `condrepr` provides a printable representation of
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   156
        the given `condition`.
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   157
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   158
        This is part of the mandatory API for smartset."""
22864
96b6b3d78697 revset: cache most conditions used in `filter`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22863
diff changeset
   159
        # builtin cannot be cached. but do not needs to
96b6b3d78697 revset: cache most conditions used in `filter`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22863
diff changeset
   160
        if cache and util.safehasattr(condition, 'func_code'):
96b6b3d78697 revset: cache most conditions used in `filter`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22863
diff changeset
   161
            condition = util.cachefunc(condition)
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   162
        return filteredset(self, condition, condrepr)
22692
78c916f24dd9 revset: introduce an abstractsmartset class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22691
diff changeset
   163
32819
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   164
    def slice(self, start, stop):
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   165
        """Return new smartset that contains selected elements from this set"""
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   166
        if start < 0 or stop < 0:
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   167
            raise error.ProgrammingError('negative index not allowed')
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   168
        return self._slice(start, stop)
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   169
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   170
    def _slice(self, start, stop):
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   171
        # sub classes may override this. start and stop must not be negative,
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   172
        # but start > stop is allowed, which should be an empty set.
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   173
        ys = []
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   174
        it = iter(self)
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   175
        for x in xrange(start):
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   176
            y = next(it, None)
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   177
            if y is None:
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   178
                break
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   179
        for x in xrange(stop - start):
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   180
            y = next(it, None)
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   181
            if y is None:
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   182
                break
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   183
            ys.append(y)
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   184
        return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self))
4710cc4dac99 smartset: extract method to slice abstractsmartset
Yuya Nishihara <yuya@tcha.org>
parents: 32818
diff changeset
   185
22825
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   186
class baseset(abstractsmartset):
20416
e72bcc245ecb revset: added docstring to baseset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20393
diff changeset
   187
    """Basic data structure that represents a revset and contains the basic
e72bcc245ecb revset: added docstring to baseset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20393
diff changeset
   188
    operation that it should be able to perform.
20727
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   189
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   190
    Every method in this class should be implemented by any smartset class.
31019
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   191
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   192
    This class could be constructed by an (unordered) set, or an (ordered)
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   193
    list-like object. If a set is provided, it'll be sorted lazily.
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   194
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   195
    >>> x = [4, 0, 7, 6]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   196
    >>> y = [5, 6, 7, 3]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   197
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   198
    Construct by a set:
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   199
    >>> xs = baseset(set(x))
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   200
    >>> ys = baseset(set(y))
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   201
    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   202
    [[0, 4, 6, 7, 3, 5], [6, 7], [0, 4]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   203
    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   204
    ['addset', 'baseset', 'baseset']
31019
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   205
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   206
    Construct by a list-like:
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   207
    >>> xs = baseset(x)
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   208
    >>> ys = baseset(i for i in y)
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   209
    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   210
    [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   211
    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   212
    ['addset', 'filteredset', 'filteredset']
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   213
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   214
    Populate "_set" fields in the lists so set optimization may be used:
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   215
    >>> [1 in xs, 3 in ys]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   216
    [False, True]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   217
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   218
    Without sort(), results won't be changed:
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   219
    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   220
    [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   221
    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   222
    ['addset', 'filteredset', 'filteredset']
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   223
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   224
    With sort(), set optimization could be used:
31019
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   225
    >>> xs.sort(reverse=True)
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   226
    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   227
    [[7, 6, 4, 0, 5, 3], [7, 6], [4, 0]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   228
    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   229
    ['addset', 'baseset', 'baseset']
31019
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   230
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   231
    >>> ys.sort()
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   232
    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   233
    [[7, 6, 4, 0, 3, 5], [7, 6], [4, 0]]
74f77f1c2215 smartset: add some doctests
Jun Wu <quark@fb.com>
parents: 31015
diff changeset
   234
    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   235
    ['addset', 'baseset', 'baseset']
31066
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   236
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   237
    istopo is preserved across set operations
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   238
    >>> xs = baseset(set(x), istopo=True)
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   239
    >>> rs = xs & ys
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   240
    >>> type(rs).__name__
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   241
    'baseset'
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   242
    >>> rs._istopo
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   243
    True
20416
e72bcc245ecb revset: added docstring to baseset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20393
diff changeset
   244
    """
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   245
    def __init__(self, data=(), datarepr=None, istopo=False):
28425
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   246
        """
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   247
        datarepr: a tuple of (format, obj, ...), a function or an object that
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   248
                  provides a printable representation of the given data.
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   249
        """
28786
69c6e9623bdc revset: force ascending order for baseset initialized from a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28785
diff changeset
   250
        self._ascending = None
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   251
        self._istopo = istopo
31127
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   252
        if isinstance(data, set):
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   253
            # converting set to list has a cost, do it lazily
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   254
            self._set = data
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   255
            # set has no order we pick one for stability purpose
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   256
            self._ascending = True
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   257
        else:
90fb0193f187 smartset: reorder initialization of baseset in more intuitive way
Yuya Nishihara <yuya@tcha.org>
parents: 31066
diff changeset
   258
            if not isinstance(data, list):
31015
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   259
                data = list(data)
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   260
            self._list = data
28425
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   261
        self._datarepr = datarepr
20365
bc770ee6a351 revset: implemented set caching for revset evaluation
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20364
diff changeset
   262
22826
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   263
    @util.propertycache
22879
efe5062145c1 baseset: make `_set` a property cache
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22877
diff changeset
   264
    def _set(self):
efe5062145c1 baseset: make `_set` a property cache
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22877
diff changeset
   265
        return set(self._list)
efe5062145c1 baseset: make `_set` a property cache
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22877
diff changeset
   266
efe5062145c1 baseset: make `_set` a property cache
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22877
diff changeset
   267
    @util.propertycache
22826
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   268
    def _asclist(self):
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   269
        asclist = self._list[:]
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   270
        asclist.sort()
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   271
        return asclist
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   272
31015
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   273
    @util.propertycache
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   274
    def _list(self):
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   275
        # _list is only lazily constructed if we have _set
32148
2cfdf5241096 py3: use raw strings while accessing class.__dict__
Pulkit Goyal <7895pulkit@gmail.com>
parents: 31476
diff changeset
   276
        assert r'_set' in self.__dict__
31015
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   277
        return list(self._set)
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   278
22827
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   279
    def __iter__(self):
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   280
        if self._ascending is None:
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   281
            return iter(self._list)
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   282
        elif self._ascending:
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   283
            return iter(self._asclist)
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   284
        else:
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   285
            return reversed(self._asclist)
c1107cb21df2 baseset: prepare lazy ordering in __iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22826
diff changeset
   286
22826
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   287
    def fastasc(self):
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   288
        return iter(self._asclist)
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   289
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   290
    def fastdesc(self):
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   291
        return reversed(self._asclist)
4ffb327e4719 baseset: implement a fastasc and fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22825
diff changeset
   292
22503
300e07582e9b revset: add an optimised baseset.__contains__ (issue4371)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22105
diff changeset
   293
    @util.propertycache
300e07582e9b revset: add an optimised baseset.__contains__ (issue4371)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22105
diff changeset
   294
    def __contains__(self):
22880
5b635b44af14 baseset: access `_set` directly for containment check
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22879
diff changeset
   295
        return self._set.__contains__
22503
300e07582e9b revset: add an optimised baseset.__contains__ (issue4371)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22105
diff changeset
   296
22691
d8a08b68f754 revset: add a `__nonzero__` to baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22690
diff changeset
   297
    def __nonzero__(self):
31015
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   298
        return bool(len(self))
22825
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   299
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   300
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   301
22825
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   302
    def sort(self, reverse=False):
22829
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   303
        self._ascending = not bool(reverse)
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   304
        self._istopo = False
22825
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   305
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   306
    def reverse(self):
22829
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   307
        if self._ascending is None:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   308
            self._list.reverse()
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   309
        else:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   310
            self._ascending = not self._ascending
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   311
        self._istopo = False
22825
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   312
0e8bb81b58b9 baseset: stop inheriting from built-in list class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22817
diff changeset
   313
    def __len__(self):
35838
f484b9d95c23 smartset: use native string when peeking in __dict__
Augie Fackler <augie@google.com>
parents: 35501
diff changeset
   314
        if r'_list' in self.__dict__:
31015
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   315
            return len(self._list)
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   316
        else:
1076f7eba964 smartset: convert set to list lazily
Jun Wu <quark@fb.com>
parents: 30881
diff changeset
   317
            return len(self._set)
22691
d8a08b68f754 revset: add a `__nonzero__` to baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22690
diff changeset
   318
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   319
    def isascending(self):
20727
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   320
        """Returns True if the collection is ascending order, False if not.
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   321
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   322
        This is part of the mandatory API for smartset."""
22863
a1a02b516cca baseset: empty or one-element sets are ascending and descending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22862
diff changeset
   323
        if len(self) <= 1:
a1a02b516cca baseset: empty or one-element sets are ascending and descending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22862
diff changeset
   324
            return True
22828
966860f7a1a8 baseset: fix isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22827
diff changeset
   325
        return self._ascending is not None and self._ascending
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   326
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   327
    def isdescending(self):
20727
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   328
        """Returns True if the collection is descending order, False if not.
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   329
1e59f760d850 revset: added comments to all methods needed to duck-type from baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20726
diff changeset
   330
        This is part of the mandatory API for smartset."""
22863
a1a02b516cca baseset: empty or one-element sets are ascending and descending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22862
diff changeset
   331
        if len(self) <= 1:
a1a02b516cca baseset: empty or one-element sets are ascending and descending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22862
diff changeset
   332
            return True
22828
966860f7a1a8 baseset: fix isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22827
diff changeset
   333
        return self._ascending is not None and not self._ascending
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   334
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   335
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   336
        """Is the collection is in topographical order or not.
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   337
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   338
        This is part of the mandatory API for smartset."""
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   339
        if len(self) <= 1:
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   340
            return True
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   341
        return self._istopo
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   342
22812
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   343
    def first(self):
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   344
        if self:
22829
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   345
            if self._ascending is None:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   346
                return self._list[0]
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   347
            elif self._ascending:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   348
                return self._asclist[0]
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   349
            else:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   350
                return self._asclist[-1]
22812
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   351
        return None
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   352
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   353
    def last(self):
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   354
        if self:
22829
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   355
            if self._ascending is None:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   356
                return self._list[-1]
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   357
            elif self._ascending:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   358
                return self._asclist[-1]
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   359
            else:
36e09c25f870 baseset: explicitly track order of the baseset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22828
diff changeset
   360
                return self._asclist[0]
22812
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   361
        return None
fcd12b310148 baseset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22811
diff changeset
   362
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   363
    def _fastsetop(self, other, op):
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   364
        # try to use native set operations as fast paths
34070
01c9700fbf9f py3: fix type of attribute name in smartset.py
Yuya Nishihara <yuya@tcha.org>
parents: 33109
diff changeset
   365
        if (type(other) is baseset and r'_set' in other.__dict__ and r'_set' in
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   366
            self.__dict__ and self._ascending is not None):
31066
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   367
            s = baseset(data=getattr(self._set, op)(other._set),
c962bb6af909 smartset: preserve istopo for baseset operations
Jun Wu <quark@fb.com>
parents: 31020
diff changeset
   368
                        istopo=self._istopo)
31020
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   369
            s._ascending = self._ascending
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   370
        else:
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   371
            s = getattr(super(baseset, self), op)(other)
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   372
        return s
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   373
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   374
    def __and__(self, other):
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   375
        return self._fastsetop(other, '__and__')
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   376
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   377
    def __sub__(self, other):
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   378
        return self._fastsetop(other, '__sub__')
2d1bf84046f6 smartset: use native set operations as fast paths
Jun Wu <quark@fb.com>
parents: 31019
diff changeset
   379
32820
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   380
    def _slice(self, start, stop):
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   381
        # creating new list should be generally cheaper than iterating items
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   382
        if self._ascending is None:
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   383
            return baseset(self._list[start:stop], istopo=self._istopo)
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   384
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   385
        data = self._asclist
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   386
        if not self._ascending:
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   387
            start, stop = max(len(data) - stop, 0), max(len(data) - start, 0)
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   388
        s = baseset(data[start:stop], istopo=self._istopo)
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   389
        s._ascending = self._ascending
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   390
        return s
653d60455dbe smartset: micro optimize baseset.slice() to use slice of list
Yuya Nishihara <yuya@tcha.org>
parents: 32819
diff changeset
   391
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   392
    @encoding.strmethod
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   393
    def __repr__(self):
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   394
        d = {None: '', False: '-', True: '+'}[self._ascending]
28425
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   395
        s = _formatsetrepr(self._datarepr)
02d7faaf455c revset: stub to add extra data to baseset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28424
diff changeset
   396
        if not s:
28785
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   397
            l = self._list
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   398
            # if _list has been built from a set, it might have a different
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   399
            # order from one python implementation to another.
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   400
            # We fallback to the sorted version for a stable output.
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   401
            if self._ascending is not None:
87b89dca669d revset: stabilize repr of baseset initialized with a set
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 28720
diff changeset
   402
                l = self._asclist
36265
b44fac3a49fb py3: factor out byterepr() which returns an asciified value on py3
Yuya Nishihara <yuya@tcha.org>
parents: 35904
diff changeset
   403
            s = pycompat.byterepr(l)
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   404
        return '<%s%s %s>' % (_typename(self), d, s)
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   405
22726
169aa5e74b52 lazyset: rename the class to filteredset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22725
diff changeset
   406
class filteredset(abstractsmartset):
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   407
    """Duck type for baseset class which iterates lazily over the revisions in
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   408
    the subset and contains a function which tests for membership in the
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   409
    revset
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   410
    """
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   411
    def __init__(self, subset, condition=lambda x: True, condrepr=None):
20738
33943add5d65 revset: add some documentation for lazyset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20737
diff changeset
   412
        """
33943add5d65 revset: add some documentation for lazyset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20737
diff changeset
   413
        condition: a function that decide whether a revision in the subset
33943add5d65 revset: add some documentation for lazyset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20737
diff changeset
   414
                   belongs to the revset or not.
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   415
        condrepr: a tuple of (format, obj, ...), a function or an object that
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   416
                  provides a printable representation of the given condition.
20738
33943add5d65 revset: add some documentation for lazyset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20737
diff changeset
   417
        """
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   418
        self._subset = subset
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   419
        self._condition = condition
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   420
        self._condrepr = condrepr
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   421
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   422
    def __contains__(self, x):
26212
0d8df1f510c6 revset: uncache filteredset.__contains__
Yuya Nishihara <yuya@tcha.org>
parents: 26143
diff changeset
   423
        return x in self._subset and self._condition(x)
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   424
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   425
    def __iter__(self):
22719
21fda9dcd4e8 lazyset: split the iteration logic from the condition filtering logic
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22718
diff changeset
   426
        return self._iterfilter(self._subset)
21fda9dcd4e8 lazyset: split the iteration logic from the condition filtering logic
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22718
diff changeset
   427
21fda9dcd4e8 lazyset: split the iteration logic from the condition filtering logic
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22718
diff changeset
   428
    def _iterfilter(self, it):
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   429
        cond = self._condition
22719
21fda9dcd4e8 lazyset: split the iteration logic from the condition filtering logic
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22718
diff changeset
   430
        for x in it:
20427
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   431
            if cond(x):
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   432
                yield x
4a9191ca848e revset: added lazyset class with basic operations
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20424
diff changeset
   433
22720
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   434
    @property
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   435
    def fastasc(self):
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   436
        it = self._subset.fastasc
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   437
        if it is None:
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   438
            return None
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   439
        return lambda: self._iterfilter(it())
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   440
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   441
    @property
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   442
    def fastdesc(self):
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   443
        it = self._subset.fastdesc
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   444
        if it is None:
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   445
            return None
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   446
        return lambda: self._iterfilter(it())
4388f99c5512 lazyset: inherit the fastasc and fastdesc method from subset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22719
diff changeset
   447
20552
0e99a66eb7bc revset: added __nonzero__ method to lazyset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20540
diff changeset
   448
    def __nonzero__(self):
29304
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   449
        fast = None
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   450
        candidates = [self.fastasc if self.isascending() else None,
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   451
                      self.fastdesc if self.isdescending() else None,
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   452
                      self.fastasc,
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   453
                      self.fastdesc]
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   454
        for candidate in candidates:
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   455
            if candidate is not None:
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   456
                fast = candidate
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   457
                break
5e32852fa4bd revset: make filteredset.__nonzero__ respect the order of the filteredset
Kostia Balytskyi <ikostia@fb.com>
parents: 29265
diff changeset
   458
26307
428a8747f4ee revset: avoid implicit None testing in revset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26306
diff changeset
   459
        if fast is not None:
26306
d157e1f18e3f revset: speed up existence checks for ordered filtered sets
Durham Goode <durham@fb.com>
parents: 26305
diff changeset
   460
            it = fast()
26307
428a8747f4ee revset: avoid implicit None testing in revset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26306
diff changeset
   461
        else:
428a8747f4ee revset: avoid implicit None testing in revset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26306
diff changeset
   462
            it = self
26306
d157e1f18e3f revset: speed up existence checks for ordered filtered sets
Durham Goode <durham@fb.com>
parents: 26305
diff changeset
   463
d157e1f18e3f revset: speed up existence checks for ordered filtered sets
Durham Goode <durham@fb.com>
parents: 26305
diff changeset
   464
        for r in it:
20552
0e99a66eb7bc revset: added __nonzero__ method to lazyset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20540
diff changeset
   465
            return True
0e99a66eb7bc revset: added __nonzero__ method to lazyset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20540
diff changeset
   466
        return False
0e99a66eb7bc revset: added __nonzero__ method to lazyset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20540
diff changeset
   467
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   468
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   469
20429
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   470
    def __len__(self):
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   471
        # Basic implementation to be changed in future patches.
28718
f103f985ac00 revset: prevent infinite recursion on pypy
Maciej Fijalkowski <fijall@gmail.com>
parents: 28717
diff changeset
   472
        # until this gets improved, we use generator expression
30332
318a24b52eeb spelling: fixes of non-dictionary words
Mads Kiilerich <madski@unity3d.com>
parents: 30227
diff changeset
   473
        # here, since list comprehensions are free to call __len__ again
28718
f103f985ac00 revset: prevent infinite recursion on pypy
Maciej Fijalkowski <fijall@gmail.com>
parents: 28717
diff changeset
   474
        # causing infinite recursion
f103f985ac00 revset: prevent infinite recursion on pypy
Maciej Fijalkowski <fijall@gmail.com>
parents: 28717
diff changeset
   475
        l = baseset(r for r in self)
20429
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   476
        return len(l)
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   477
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   478
    def sort(self, reverse=False):
22862
9e5576f822cc filteredset: drop explicit order management
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22861
diff changeset
   479
        self._subset.sort(reverse=reverse)
20429
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   480
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   481
    def reverse(self):
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   482
        self._subset.reverse()
f5b560c60bcd revset: added operations to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20428
diff changeset
   483
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   484
    def isascending(self):
22862
9e5576f822cc filteredset: drop explicit order management
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22861
diff changeset
   485
        return self._subset.isascending()
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   486
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   487
    def isdescending(self):
22862
9e5576f822cc filteredset: drop explicit order management
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22861
diff changeset
   488
        return self._subset.isdescending()
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
   489
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   490
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   491
        return self._subset.istopo()
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   492
22813
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   493
    def first(self):
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   494
        for x in self:
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   495
            return x
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   496
        return None
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   497
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   498
    def last(self):
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   499
        it = None
25648
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   500
        if self.isascending():
22862
9e5576f822cc filteredset: drop explicit order management
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22861
diff changeset
   501
            it = self.fastdesc
25648
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   502
        elif self.isdescending():
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   503
            it = self.fastasc
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   504
        if it is not None:
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   505
            for x in it():
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   506
                return x
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   507
            return None #empty case
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   508
        else:
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   509
            x = None
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   510
            for x in self:
9b9877d2b229 revset: rework 'filteredset.last'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25647
diff changeset
   511
                pass
22813
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   512
            return x
5a96df266b2b filteredset: implement `first` and `last`
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22812
diff changeset
   513
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   514
    @encoding.strmethod
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   515
    def __repr__(self):
36265
b44fac3a49fb py3: factor out byterepr() which returns an asciified value on py3
Yuya Nishihara <yuya@tcha.org>
parents: 35904
diff changeset
   516
        xs = [pycompat.byterepr(self._subset)]
28423
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   517
        s = _formatsetrepr(self._condrepr)
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   518
        if s:
0d79d91ba7e3 revset: add extra data to filteredset for better inspection
Yuya Nishihara <yuya@tcha.org>
parents: 28395
diff changeset
   519
            xs.append(s)
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   520
        return '<%s %s>' % (_typename(self), ', '.join(xs))
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   521
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   522
def _iterordered(ascending, iter1, iter2):
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   523
    """produce an ordered iteration from two iterators with the same order
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   524
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   525
    The ascending is used to indicated the iteration direction.
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   526
    """
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   527
    choice = max
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   528
    if ascending:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   529
        choice = min
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   530
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   531
    val1 = None
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   532
    val2 = None
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   533
    try:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   534
        # Consume both iterators in an ordered way until one is empty
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   535
        while True:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   536
            if val1 is None:
29216
ead25aa27a43 py3: convert to next() function
timeless <timeless@mozdev.org>
parents: 29215
diff changeset
   537
                val1 = next(iter1)
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   538
            if val2 is None:
29216
ead25aa27a43 py3: convert to next() function
timeless <timeless@mozdev.org>
parents: 29215
diff changeset
   539
                val2 = next(iter2)
29215
f5983805574e revset: rename variable to avoid shadowing with builtin next() function
timeless <timeless@mozdev.org>
parents: 29147
diff changeset
   540
            n = choice(val1, val2)
f5983805574e revset: rename variable to avoid shadowing with builtin next() function
timeless <timeless@mozdev.org>
parents: 29147
diff changeset
   541
            yield n
f5983805574e revset: rename variable to avoid shadowing with builtin next() function
timeless <timeless@mozdev.org>
parents: 29147
diff changeset
   542
            if val1 == n:
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   543
                val1 = None
29215
f5983805574e revset: rename variable to avoid shadowing with builtin next() function
timeless <timeless@mozdev.org>
parents: 29147
diff changeset
   544
            if val2 == n:
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   545
                val2 = None
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   546
    except StopIteration:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   547
        # Flush any remaining values and consume the other one
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   548
        it = iter2
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   549
        if val1 is not None:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   550
            yield val1
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   551
            it = iter1
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   552
        elif val2 is not None:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   553
            # might have been equality and both are empty
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   554
            yield val2
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   555
        for val in it:
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   556
            yield val
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   557
22793
ff6689b47e48 addset: drop the leading underscore from the class name
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22792
diff changeset
   558
class addset(abstractsmartset):
20708
17c89e5a5627 revset: made addset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20707
diff changeset
   559
    """Represent the addition of two sets
17c89e5a5627 revset: made addset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20707
diff changeset
   560
17c89e5a5627 revset: made addset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20707
diff changeset
   561
    Wrapper structure for lazily adding two structures without losing much
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   562
    performance on the __contains__ method
20708
17c89e5a5627 revset: made addset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20707
diff changeset
   563
20712
c152e538b85b revset: added ascending attribute to addset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20711
diff changeset
   564
    If the ascending attribute is set, that means the two structures are
c152e538b85b revset: added ascending attribute to addset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20711
diff changeset
   565
    ordered in either an ascending or descending way. Therefore, we can add
21024
7731a2281cf0 spelling: fixes from spell checker
Mads Kiilerich <madski@unity3d.com>
parents: 20991
diff changeset
   566
    them maintaining the order by iterating over both at the same time
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   567
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   568
    >>> xs = baseset([0, 3, 2])
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   569
    >>> ys = baseset([5, 2, 4])
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   570
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   571
    >>> rs = addset(xs, ys)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   572
    >>> bool(rs), 0 in rs, 1 in rs, 5 in rs, rs.first(), rs.last()
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   573
    (True, True, False, True, 0, 4)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   574
    >>> rs = addset(xs, baseset([]))
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   575
    >>> bool(rs), 0 in rs, 1 in rs, rs.first(), rs.last()
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   576
    (True, True, False, 0, 2)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   577
    >>> rs = addset(baseset([]), baseset([]))
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   578
    >>> bool(rs), 0 in rs, rs.first(), rs.last()
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   579
    (False, False, None, None)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   580
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   581
    iterate unsorted:
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   582
    >>> rs = addset(xs, ys)
28717
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   583
    >>> # (use generator because pypy could call len())
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   584
    >>> list(x for x in rs)  # without _genlist
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   585
    [0, 3, 2, 5, 4]
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   586
    >>> assert not rs._genlist
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   587
    >>> len(rs)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   588
    5
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   589
    >>> [x for x in rs]  # with _genlist
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   590
    [0, 3, 2, 5, 4]
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   591
    >>> assert rs._genlist
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   592
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   593
    iterate ascending:
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   594
    >>> rs = addset(xs, ys, ascending=True)
28717
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   595
    >>> # (use generator because pypy could call len())
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   596
    >>> list(x for x in rs), list(x for x in rs.fastasc())  # without _asclist
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   597
    ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   598
    >>> assert not rs._asclist
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   599
    >>> len(rs)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   600
    5
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   601
    >>> [x for x in rs], [x for x in rs.fastasc()]
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   602
    ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   603
    >>> assert rs._asclist
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   604
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   605
    iterate descending:
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   606
    >>> rs = addset(xs, ys, ascending=False)
28717
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   607
    >>> # (use generator because pypy could call len())
c5f212c8ad78 pypy: fix doctests for pypy optimizations
Maciej Fijalkowski <fijall@gmail.com>
parents: 28708
diff changeset
   608
    >>> list(x for x in rs), list(x for x in rs.fastdesc())  # without _asclist
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   609
    ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   610
    >>> assert not rs._asclist
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   611
    >>> len(rs)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   612
    5
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   613
    >>> [x for x in rs], [x for x in rs.fastdesc()]
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   614
    ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   615
    >>> assert rs._asclist
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   616
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   617
    iterate ascending without fastasc:
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   618
    >>> rs = addset(xs, generatorset(ys), ascending=True)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   619
    >>> assert rs.fastasc is None
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   620
    >>> [x for x in rs]
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   621
    [0, 2, 3, 4, 5]
25024
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   622
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   623
    iterate descending without fastdesc:
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   624
    >>> rs = addset(generatorset(xs), ys, ascending=False)
263bbed1833c revset: test current behavior of addset class
Yuya Nishihara <yuya@tcha.org>
parents: 25023
diff changeset
   625
    >>> assert rs.fastdesc is None
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   626
    >>> [x for x in rs]
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   627
    [5, 4, 3, 2, 0]
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   628
    """
20712
c152e538b85b revset: added ascending attribute to addset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20711
diff changeset
   629
    def __init__(self, revs1, revs2, ascending=None):
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   630
        self._r1 = revs1
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   631
        self._r2 = revs2
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   632
        self._iter = None
20712
c152e538b85b revset: added ascending attribute to addset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20711
diff changeset
   633
        self._ascending = ascending
20720
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   634
        self._genlist = None
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   635
        self._asclist = None
20720
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   636
20845
bc95143446e8 _addset: add a __len__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20833
diff changeset
   637
    def __len__(self):
bc95143446e8 _addset: add a __len__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20833
diff changeset
   638
        return len(self._list)
bc95143446e8 _addset: add a __len__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20833
diff changeset
   639
22743
eccf9907b844 addset: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22742
diff changeset
   640
    def __nonzero__(self):
23100
ac494b087feb revset: fix O(2^n) perf regression in addset
Durham Goode <durham@fb.com>
parents: 23078
diff changeset
   641
        return bool(self._r1) or bool(self._r2)
22743
eccf9907b844 addset: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22742
diff changeset
   642
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   643
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   644
20720
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   645
    @util.propertycache
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   646
    def _list(self):
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   647
        if not self._genlist:
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   648
            self._genlist = baseset(iter(self))
20720
5f8400efca0b revset: added cached generated list to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20719
diff changeset
   649
        return self._genlist
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   650
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   651
    def __iter__(self):
20722
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   652
        """Iterate over both collections without repeating elements
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   653
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   654
        If the ascending attribute is not set, iterate over the first one and
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   655
        then over the second one checking for membership on the first one so we
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   656
        dont yield any duplicates.
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   657
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   658
        If the ascending attribute is set, iterate over both collections at the
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   659
        same time, yielding only one value at a time in the given order.
6894223ebc38 revset: changed _iterator() method on addset to work with a given order
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20721
diff changeset
   660
        """
22799
bafa371d7af3 addset: drop caching through generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22798
diff changeset
   661
        if self._ascending is None:
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   662
            if self._genlist:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   663
                return iter(self._genlist)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   664
            def arbitraryordergen():
22799
bafa371d7af3 addset: drop caching through generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22798
diff changeset
   665
                for r in self._r1:
bafa371d7af3 addset: drop caching through generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22798
diff changeset
   666
                    yield r
22881
057ebf7714e1 addset: drop `.set()` usage during iteration
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22880
diff changeset
   667
                inr1 = self._r1.__contains__
22799
bafa371d7af3 addset: drop caching through generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22798
diff changeset
   668
                for r in self._r2:
22881
057ebf7714e1 addset: drop `.set()` usage during iteration
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22880
diff changeset
   669
                    if not inr1(r):
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   670
                        yield r
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   671
            return arbitraryordergen()
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   672
        # try to use our own fast iterator if it exists
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   673
        self._trysetasclist()
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   674
        if self._ascending:
25130
a94ef7f517e0 revset: use fastasc/fastdesc switch consistently in addset.__iter__
Yuya Nishihara <yuya@tcha.org>
parents: 25129
diff changeset
   675
            attr = 'fastasc'
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   676
        else:
25130
a94ef7f517e0 revset: use fastasc/fastdesc switch consistently in addset.__iter__
Yuya Nishihara <yuya@tcha.org>
parents: 25129
diff changeset
   677
            attr = 'fastdesc'
a94ef7f517e0 revset: use fastasc/fastdesc switch consistently in addset.__iter__
Yuya Nishihara <yuya@tcha.org>
parents: 25129
diff changeset
   678
        it = getattr(self, attr)
25115
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   679
        if it is not None:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   680
            return it()
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   681
        # maybe half of the component supports fast
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   682
        # get iterator for _r1
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   683
        iter1 = getattr(self._r1, attr)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   684
        if iter1 is None:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   685
            # let's avoid side effect (not sure it matters)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   686
            iter1 = iter(sorted(self._r1, reverse=not self._ascending))
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   687
        else:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   688
            iter1 = iter1()
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   689
        # get iterator for _r2
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   690
        iter2 = getattr(self._r2, attr)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   691
        if iter2 is None:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   692
            # let's avoid side effect (not sure it matters)
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   693
            iter2 = iter(sorted(self._r2, reverse=not self._ascending))
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   694
        else:
5548f558db3d revset: fix iteration over ordered addset composed of non-ordered operands
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25105
diff changeset
   695
            iter2 = iter2()
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   696
        return _iterordered(self._ascending, iter1, iter2)
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   697
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   698
    def _trysetasclist(self):
23139
e53f6b72a0e4 spelling: fixes from proofreading of spell checker issues
Mads Kiilerich <madski@unity3d.com>
parents: 23127
diff changeset
   699
        """populate the _asclist attribute if possible and necessary"""
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   700
        if self._genlist is not None and self._asclist is None:
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   701
            self._asclist = sorted(self._genlist)
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   702
22742
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   703
    @property
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   704
    def fastasc(self):
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   705
        self._trysetasclist()
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   706
        if self._asclist is not None:
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   707
            return self._asclist.__iter__
22742
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   708
        iter1 = self._r1.fastasc
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   709
        iter2 = self._r2.fastasc
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   710
        if None in (iter1, iter2):
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   711
            return None
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   712
        return lambda: _iterordered(True, iter1(), iter2())
22742
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   713
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   714
    @property
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   715
    def fastdesc(self):
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   716
        self._trysetasclist()
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   717
        if self._asclist is not None:
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   718
            return self._asclist.__reversed__
22742
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   719
        iter1 = self._r1.fastdesc
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   720
        iter2 = self._r2.fastdesc
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   721
        if None in (iter1, iter2):
6bbc26adcc6a addset: offer a fastasc and fastdesc methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22741
diff changeset
   722
            return None
25131
adfe4d9680bf revset: extract addset._iterordered to free function
Yuya Nishihara <yuya@tcha.org>
parents: 25130
diff changeset
   723
        return lambda: _iterordered(False, iter1(), iter2())
22741
ef2c1ea8fb2c addset: split simple and ordered iteration
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22740
diff changeset
   724
20694
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   725
    def __contains__(self, x):
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   726
        return x in self._r1 or x in self._r2
621c94378d0d revset: added addset class with its basic methods
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20693
diff changeset
   727
20724
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   728
    def sort(self, reverse=False):
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   729
        """Sort the added set
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   730
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   731
        For this we use the cached list with all the generated values and if we
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   732
        know they are ascending or descending we can sort them in a smart way.
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   733
        """
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   734
        self._ascending = not reverse
20724
e9a64b3f2925 revset: added sort method in addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20723
diff changeset
   735
20733
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   736
    def isascending(self):
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   737
        return self._ascending is not None and self._ascending
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   738
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   739
    def isdescending(self):
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   740
        return self._ascending is not None and not self._ascending
adf4ec7e6f60 revset: added isascending and isdescending methods to _addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20732
diff changeset
   741
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   742
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   743
        # not worth the trouble asserting if the two sets combined are still
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   744
        # in topographical order. Use the sort() predicate to explicitly sort
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   745
        # again instead.
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   746
        return False
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   747
20723
fb9852c46a42 revset: added reverse method to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20722
diff changeset
   748
    def reverse(self):
22859
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   749
        if self._ascending is None:
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   750
            self._list.reverse()
513c0ba61db8 addset: do lazy sorting
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22857
diff changeset
   751
        else:
20723
fb9852c46a42 revset: added reverse method to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20722
diff changeset
   752
            self._ascending = not self._ascending
fb9852c46a42 revset: added reverse method to addset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20722
diff changeset
   753
22810
7f97cb12782f addset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22809
diff changeset
   754
    def first(self):
23127
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   755
        for x in self:
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   756
            return x
22810
7f97cb12782f addset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22809
diff changeset
   757
        return None
7f97cb12782f addset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22809
diff changeset
   758
7f97cb12782f addset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22809
diff changeset
   759
    def last(self):
23127
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   760
        self.reverse()
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   761
        val = self.first()
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   762
        self.reverse()
7361d8244efb addset: fix `first` and `last` on sorted addset (issue4426)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23115
diff changeset
   763
        return val
22810
7f97cb12782f addset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22809
diff changeset
   764
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   765
    @encoding.strmethod
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   766
    def __repr__(self):
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   767
        d = {None: '', False: '-', True: '+'}[self._ascending]
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   768
        return '<%s%s %r, %r>' % (_typename(self), d, self._r1, self._r2)
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   769
22795
c21342159fad generatorset: drop the leading underscore in the class name
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22794
diff changeset
   770
class generatorset(abstractsmartset):
20705
9cc2249a9461 revset: made generatorset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20703
diff changeset
   771
    """Wrap a generator for lazy iteration
9cc2249a9461 revset: made generatorset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20703
diff changeset
   772
9cc2249a9461 revset: made generatorset a private class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20703
diff changeset
   773
    Wrapper structure for generators that provides lazy membership and can
20540
fa16c710a3d8 revset: added cached generated list on generatorset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20538
diff changeset
   774
    be iterated more than once.
fa16c710a3d8 revset: added cached generated list on generatorset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20538
diff changeset
   775
    When asked for membership it generates values until either it finds the
fa16c710a3d8 revset: added cached generated list on generatorset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20538
diff changeset
   776
    requested one or has gone through all the elements in the generator
33109
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   777
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   778
    >>> xs = generatorset([0, 1, 4], iterasc=True)
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   779
    >>> assert xs.last() == xs.last()
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   780
    >>> xs.last()  # cached
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   781
    4
20540
fa16c710a3d8 revset: added cached generated list on generatorset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20538
diff changeset
   782
    """
35501
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   783
    def __new__(cls, gen, iterasc=None):
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   784
        if iterasc is None:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   785
            typ = cls
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   786
        elif iterasc:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   787
            typ = _generatorsetasc
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   788
        else:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   789
            typ = _generatorsetdesc
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   790
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   791
        return super(generatorset, cls).__new__(typ)
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   792
22755
f9a825b593be generatorset: make it possible to use gen as fastasc or fastdesc
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22754
diff changeset
   793
    def __init__(self, gen, iterasc=None):
20739
1b4f2399f3c4 revset: add documentation and comment for _generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20738
diff changeset
   794
        """
1b4f2399f3c4 revset: add documentation and comment for _generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20738
diff changeset
   795
        gen: a generator producing the values for the generatorset.
1b4f2399f3c4 revset: add documentation and comment for _generatorset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20738
diff changeset
   796
        """
20536
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   797
        self._gen = gen
22798
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   798
        self._asclist = None
20536
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   799
        self._cache = {}
22796
43f664bf2e1e generatorset: stop using a base as the _genlist
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22795
diff changeset
   800
        self._genlist = []
20703
e07b1fd30805 revset: added sort methods to generatorsets
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20695
diff changeset
   801
        self._finished = False
22800
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   802
        self._ascending = True
20540
fa16c710a3d8 revset: added cached generated list on generatorset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20538
diff changeset
   803
22739
4ed47a1b2d24 generatorset: implement __nonzero__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22738
diff changeset
   804
    def __nonzero__(self):
24936
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   805
        # Do not use 'for r in self' because it will enforce the iteration
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   806
        # order (default ascending), possibly unrolling a whole descending
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   807
        # iterator.
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   808
        if self._genlist:
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   809
            return True
2aa94b6fe51c revset: make generatorset.__nonzero__ lazy
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 24932
diff changeset
   810
        for r in self._consumegen():
22739
4ed47a1b2d24 generatorset: implement __nonzero__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22738
diff changeset
   811
            return True
4ed47a1b2d24 generatorset: implement __nonzero__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22738
diff changeset
   812
        return False
4ed47a1b2d24 generatorset: implement __nonzero__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22738
diff changeset
   813
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   814
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
   815
20536
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   816
    def __contains__(self, x):
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   817
        if x in self._cache:
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   818
            return self._cache[x]
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   819
20828
3210b7930899 revset: improve performance of _generatorset.__contains__ (issue 4201)
Gregory Szorc <gregory.szorc@gmail.com>
parents: 20780
diff changeset
   820
        # Use new values only, as existing values would be cached.
3210b7930899 revset: improve performance of _generatorset.__contains__ (issue 4201)
Gregory Szorc <gregory.szorc@gmail.com>
parents: 20780
diff changeset
   821
        for l in self._consumegen():
20634
f2bb7ba59456 revset: changed generatorset code to remove unnecesary function call
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20613
diff changeset
   822
            if l == x:
f2bb7ba59456 revset: changed generatorset code to remove unnecesary function call
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20613
diff changeset
   823
                return True
20536
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   824
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   825
        self._cache[x] = False
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   826
        return False
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   827
532b114a6e02 revset: added generatorset class with cached __contains__ method
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20534
diff changeset
   828
    def __iter__(self):
22800
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   829
        if self._ascending:
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   830
            it = self.fastasc
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   831
        else:
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   832
            it = self.fastdesc
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   833
        if it is not None:
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   834
            return it()
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   835
        # we need to consume the iterator
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   836
        for x in self._consumegen():
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   837
            pass
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   838
        # recall the same code
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   839
        return iter(self)
22797
61ecabeeadb3 generatorset: move iteration code into _iterator
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22796
diff changeset
   840
61ecabeeadb3 generatorset: move iteration code into _iterator
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22796
diff changeset
   841
    def _iterator(self):
20833
47d43e2323c5 revset: fix generatorset race condition
Durham Goode <durham@fb.com>
parents: 20829
diff changeset
   842
        if self._finished:
22670
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   843
            return iter(self._genlist)
20833
47d43e2323c5 revset: fix generatorset race condition
Durham Goode <durham@fb.com>
parents: 20829
diff changeset
   844
22494
14f6cebfcb8a revset: document the choice made in __generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22487
diff changeset
   845
        # We have to use this complex iteration strategy to allow multiple
14f6cebfcb8a revset: document the choice made in __generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22487
diff changeset
   846
        # iterations at the same time. We need to be able to catch revision
23139
e53f6b72a0e4 spelling: fixes from proofreading of spell checker issues
Mads Kiilerich <madski@unity3d.com>
parents: 23127
diff changeset
   847
        # removed from _consumegen and added to genlist in another instance.
22494
14f6cebfcb8a revset: document the choice made in __generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22487
diff changeset
   848
        #
14f6cebfcb8a revset: document the choice made in __generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22487
diff changeset
   849
        # Getting rid of it would provide an about 15% speed up on this
14f6cebfcb8a revset: document the choice made in __generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22487
diff changeset
   850
        # iteration.
20833
47d43e2323c5 revset: fix generatorset race condition
Durham Goode <durham@fb.com>
parents: 20829
diff changeset
   851
        genlist = self._genlist
31446
9a94239e4f12 py3: use next() to obtain next item from inner generator of generatorset
Yuya Nishihara <yuya@tcha.org>
parents: 31127
diff changeset
   852
        nextgen = self._consumegen()
9a94239e4f12 py3: use next() to obtain next item from inner generator of generatorset
Yuya Nishihara <yuya@tcha.org>
parents: 31127
diff changeset
   853
        _len, _next = len, next # cache global lookup
22670
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   854
        def gen():
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   855
            i = 0
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   856
            while True:
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   857
                if i < _len(genlist):
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   858
                    yield genlist[i]
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   859
                else:
32977
27ba0d8dc26c py3: catch StopIteration from next() in generatorset
Martin von Zweigbergk <martinvonz@google.com>
parents: 32821
diff changeset
   860
                    try:
27ba0d8dc26c py3: catch StopIteration from next() in generatorset
Martin von Zweigbergk <martinvonz@google.com>
parents: 32821
diff changeset
   861
                        yield _next(nextgen)
27ba0d8dc26c py3: catch StopIteration from next() in generatorset
Martin von Zweigbergk <martinvonz@google.com>
parents: 32821
diff changeset
   862
                    except StopIteration:
27ba0d8dc26c py3: catch StopIteration from next() in generatorset
Martin von Zweigbergk <martinvonz@google.com>
parents: 32821
diff changeset
   863
                        return
22670
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   864
                i += 1
44dce874de97 revset: rely on built in iterator when possible in _generatorset.__iter__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22669
diff changeset
   865
        return gen()
20828
3210b7930899 revset: improve performance of _generatorset.__contains__ (issue 4201)
Gregory Szorc <gregory.szorc@gmail.com>
parents: 20780
diff changeset
   866
3210b7930899 revset: improve performance of _generatorset.__contains__ (issue 4201)
Gregory Szorc <gregory.szorc@gmail.com>
parents: 20780
diff changeset
   867
    def _consumegen(self):
22528
b6dc3b79bb25 revset: avoid in loop lookup in _generatorset._consumegen
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22527
diff changeset
   868
        cache = self._cache
b6dc3b79bb25 revset: avoid in loop lookup in _generatorset._consumegen
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22527
diff changeset
   869
        genlist = self._genlist.append
20634
f2bb7ba59456 revset: changed generatorset code to remove unnecesary function call
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20613
diff changeset
   870
        for item in self._gen:
22528
b6dc3b79bb25 revset: avoid in loop lookup in _generatorset._consumegen
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22527
diff changeset
   871
            cache[item] = True
b6dc3b79bb25 revset: avoid in loop lookup in _generatorset._consumegen
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22527
diff changeset
   872
            genlist(item)
20634
f2bb7ba59456 revset: changed generatorset code to remove unnecesary function call
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20613
diff changeset
   873
            yield item
22798
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   874
        if not self._finished:
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   875
            self._finished = True
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   876
            asc = self._genlist[:]
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   877
            asc.sort()
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   878
            self._asclist = asc
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   879
            self.fastasc = asc.__iter__
586d7058ea48 generatorset: get list-based fast iterations after the generator is consumed
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22797
diff changeset
   880
            self.fastdesc = asc.__reversed__
20703
e07b1fd30805 revset: added sort methods to generatorsets
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20695
diff changeset
   881
22996
a43d929d1fa1 generatorset: implement __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22995
diff changeset
   882
    def __len__(self):
a43d929d1fa1 generatorset: implement __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22995
diff changeset
   883
        for x in self._consumegen():
a43d929d1fa1 generatorset: implement __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22995
diff changeset
   884
            pass
a43d929d1fa1 generatorset: implement __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22995
diff changeset
   885
        return len(self._genlist)
a43d929d1fa1 generatorset: implement __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22995
diff changeset
   886
20703
e07b1fd30805 revset: added sort methods to generatorsets
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20695
diff changeset
   887
    def sort(self, reverse=False):
22800
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   888
        self._ascending = not reverse
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   889
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   890
    def reverse(self):
29a8c20e14a8 generatorset: explicitly track iteration order
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22799
diff changeset
   891
        self._ascending = not self._ascending
20703
e07b1fd30805 revset: added sort methods to generatorsets
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20695
diff changeset
   892
22801
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   893
    def isascending(self):
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   894
        return self._ascending
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   895
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   896
    def isdescending(self):
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   897
        return not self._ascending
6af9e9b6af39 generatorset: implement isascending and isdescending
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22800
diff changeset
   898
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   899
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   900
        # not worth the trouble asserting if the two sets combined are still
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   901
        # in topographical order. Use the sort() predicate to explicitly sort
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   902
        # again instead.
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   903
        return False
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
   904
22811
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   905
    def first(self):
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   906
        if self._ascending:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   907
            it = self.fastasc
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   908
        else:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   909
            it = self.fastdesc
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   910
        if it is None:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   911
            # we need to consume all and try again
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   912
            for x in self._consumegen():
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   913
                pass
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   914
            return self.first()
25146
f542a2c89b60 generatorset: use 'next()' to simplify the code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25145
diff changeset
   915
        return next(it(), None)
22811
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   916
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   917
    def last(self):
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   918
        if self._ascending:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   919
            it = self.fastdesc
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   920
        else:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   921
            it = self.fastasc
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   922
        if it is None:
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   923
            # we need to consume all and try again
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   924
            for x in self._consumegen():
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   925
                pass
33109
247bae545061 smartset: fix generatorset.last() to not return the first element (issue5609)
Yuya Nishihara <yuya@tcha.org>
parents: 33072
diff changeset
   926
            return self.last()
25146
f542a2c89b60 generatorset: use 'next()' to simplify the code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25145
diff changeset
   927
        return next(it(), None)
22811
c1fd827e1ae0 generatorset: implement first and last methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22810
diff changeset
   928
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   929
    @encoding.strmethod
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   930
    def __repr__(self):
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   931
        d = {False: '-', True: '+'}[self._ascending]
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
   932
        return '<%s%s>' % (_typename(self), d)
35501
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   933
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   934
class _generatorsetasc(generatorset):
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   935
    """Special case of generatorset optimized for ascending generators."""
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   936
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   937
    fastasc = generatorset._iterator
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   938
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   939
    def __contains__(self, x):
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   940
        if x in self._cache:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   941
            return self._cache[x]
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   942
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   943
        # Use new values only, as existing values would be cached.
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   944
        for l in self._consumegen():
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   945
            if l == x:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   946
                return True
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   947
            if l > x:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   948
                break
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   949
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   950
        self._cache[x] = False
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   951
        return False
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   952
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   953
class _generatorsetdesc(generatorset):
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   954
    """Special case of generatorset optimized for descending generators."""
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   955
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   956
    fastdesc = generatorset._iterator
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   957
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   958
    def __contains__(self, x):
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   959
        if x in self._cache:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   960
            return self._cache[x]
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   961
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   962
        # Use new values only, as existing values would be cached.
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   963
        for l in self._consumegen():
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   964
            if l == x:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   965
                return True
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   966
            if l < x:
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   967
                break
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   968
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   969
        self._cache[x] = False
12a46ad67a3c smartset: split generatorset classes to avoid cycle
Gregory Szorc <gregory.szorc@gmail.com>
parents: 34070
diff changeset
   970
        return False
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
   971
32818
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   972
def spanset(repo, start=0, end=None):
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   973
    """Create a spanset that represents a range of repository revisions
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   974
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   975
    start: first revision included the set (default to 0)
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   976
    end:   first revision excluded (last+1) (default to len(repo))
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   977
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   978
    Spanset will be descending if `end` < `start`.
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   979
    """
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   980
    if end is None:
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   981
        end = len(repo)
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   982
    ascending = start <= end
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   983
    if not ascending:
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   984
        start, end = end + 1, start + 1
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   985
    return _spanset(start, end, ascending, repo.changelog.filteredrevs)
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   986
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   987
class _spanset(abstractsmartset):
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
   988
    """Duck type for baseset class which represents a range of revisions and
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
   989
    can work lazily and without having all the range in memory
20737
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   990
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   991
    Note that spanset(x, y) behave almost like xrange(x, y) except for two
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   992
    notable points:
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   993
    - when x < y it will be automatically descending,
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   994
    - revision filtered with this repoview will be skipped.
b141080e70c5 revset: added documentation and comment for spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20734
diff changeset
   995
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
   996
    """
32818
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
   997
    def __init__(self, start, end, ascending, hiddenrevs):
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
   998
        self._start = start
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
   999
        self._end = end
32818
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
  1000
        self._ascending = ascending
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
  1001
        self._hiddenrevs = hiddenrevs
20521
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1002
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1003
    def sort(self, reverse=False):
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1004
        self._ascending = not reverse
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1005
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1006
    def reverse(self):
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1007
        self._ascending = not self._ascending
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1008
29346
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1009
    def istopo(self):
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1010
        # not worth the trouble asserting if the two sets combined are still
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1011
        # in topographical order. Use the sort() predicate to explicitly sort
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1012
        # again instead.
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1013
        return False
38e0c83c7ee4 revset: record if a set is in topographical order
Martijn Pieters <mjpieters@fb.com>
parents: 29304
diff changeset
  1014
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1015
    def _iterfilter(self, iterrange):
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1016
        s = self._hiddenrevs
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1017
        for r in iterrange:
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1018
            if r not in s:
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1019
                yield r
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1020
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
  1021
    def __iter__(self):
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1022
        if self._ascending:
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1023
            return self.fastasc()
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
  1024
        else:
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1025
            return self.fastdesc()
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1026
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1027
    def fastasc(self):
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1028
        iterrange = xrange(self._start, self._end)
20521
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1029
        if self._hiddenrevs:
22717
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1030
            return self._iterfilter(iterrange)
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1031
        return iter(iterrange)
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1032
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1033
    def fastdesc(self):
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1034
        iterrange = xrange(self._end - 1, self._start - 1, -1)
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1035
        if self._hiddenrevs:
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1036
            return self._iterfilter(iterrange)
b89f7e3a414d spanset: enforce the order lazily to gain `fastasc` and `fastdesc` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22716
diff changeset
  1037
        return iter(iterrange)
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
  1038
21201
c8b9c6147108 revset: fix revision filtering in spanset.contains (regression)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21199
diff changeset
  1039
    def __contains__(self, rev):
22526
1e6d2b6b37ea revset: do less lookup during spanset.__contains__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22510
diff changeset
  1040
        hidden = self._hiddenrevs
22718
7b123e5639f4 spanset: do a single range check in __contains__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22717
diff changeset
  1041
        return ((self._start <= rev < self._end)
22526
1e6d2b6b37ea revset: do less lookup during spanset.__contains__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22510
diff changeset
  1042
                and not (hidden and rev in hidden))
20482
a979078bd788 revset: added spanset class to represent revision ranges
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20481
diff changeset
  1043
20716
fa1ac5faa7c4 revset: added __nonzero__ method to spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20714
diff changeset
  1044
    def __nonzero__(self):
fa1ac5faa7c4 revset: added __nonzero__ method to spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20714
diff changeset
  1045
        for r in self:
fa1ac5faa7c4 revset: added __nonzero__ method to spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20714
diff changeset
  1046
            return True
fa1ac5faa7c4 revset: added __nonzero__ method to spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20714
diff changeset
  1047
        return False
fa1ac5faa7c4 revset: added __nonzero__ method to spanset class
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20714
diff changeset
  1048
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
  1049
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 31446
diff changeset
  1050
20484
0f1ef9e9e904 revset: added operations to spanset to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20483
diff changeset
  1051
    def __len__(self):
20521
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1052
        if not self._hiddenrevs:
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1053
            return abs(self._end - self._start)
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1054
        else:
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1055
            count = 0
21205
e2031c8ca4f8 revset: also inline spanset._contained in __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21204
diff changeset
  1056
            start = self._start
e2031c8ca4f8 revset: also inline spanset._contained in __len__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21204
diff changeset
  1057
            end = self._end
20521
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1058
            for rev in self._hiddenrevs:
21284
3e53a64345c1 revset: cosmetic changes in spanset range comparison
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21283
diff changeset
  1059
                if (end < rev <= start) or (start <= rev < end):
20521
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1060
                    count += 1
1850a7f5fb66 revset: changed spanset implementation to take hidden revisions into account
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20512
diff changeset
  1061
            return abs(self._end - self._start) - count
20484
0f1ef9e9e904 revset: added operations to spanset to duck type baseset
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20483
diff changeset
  1062
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
  1063
    def isascending(self):
23826
c90d195320c5 revset: fix spanset.isascending() to honor sort() or reverse() request
Yuya Nishihara <yuya@tcha.org>
parents: 23724
diff changeset
  1064
        return self._ascending
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
  1065
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
  1066
    def isdescending(self):
23826
c90d195320c5 revset: fix spanset.isascending() to honor sort() or reverse() request
Yuya Nishihara <yuya@tcha.org>
parents: 23724
diff changeset
  1067
        return not self._ascending
20725
cf628b50afbb revset: added isascending and isdescending methods to smartset classes
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20724
diff changeset
  1068
22809
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1069
    def first(self):
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1070
        if self._ascending:
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1071
            it = self.fastasc
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1072
        else:
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1073
            it = self.fastdesc
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1074
        for x in it():
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1075
            return x
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1076
        return None
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1077
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1078
    def last(self):
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1079
        if self._ascending:
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1080
            it = self.fastdesc
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1081
        else:
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1082
            it = self.fastasc
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1083
        for x in it():
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1084
            return x
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1085
        return None
88dad916c008 spanset: implement `first` and `last` methods
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22808
diff changeset
  1086
32821
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1087
    def _slice(self, start, stop):
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1088
        if self._hiddenrevs:
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1089
            # unoptimized since all hidden revisions in range has to be scanned
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1090
            return super(_spanset, self)._slice(start, stop)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1091
        if self._ascending:
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1092
            x = min(self._start + start, self._end)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1093
            y = min(self._start + stop, self._end)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1094
        else:
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1095
            x = max(self._end - stop, self._start)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1096
            y = max(self._end - start, self._start)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1097
        return _spanset(x, y, self._ascending, self._hiddenrevs)
9b7d615108d7 smartset: micro optimize spanset.slice() to narrow range accordingly
Yuya Nishihara <yuya@tcha.org>
parents: 32820
diff changeset
  1098
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
  1099
    @encoding.strmethod
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
  1100
    def __repr__(self):
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
  1101
        d = {False: '-', True: '+'}[self._ascending]
35901
f0827211eb1f py3: build repr() of smartset as bytes then convert to str
Yuya Nishihara <yuya@tcha.org>
parents: 35838
diff changeset
  1102
        return '<%s%s %d:%d>' % (_typename(self), d, self._start, self._end)
24457
c5022f3579b9 revset: add __repr__ to all smartset classes
Yuya Nishihara <yuya@tcha.org>
parents: 24446
diff changeset
  1103
32818
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
  1104
class fullreposet(_spanset):
22508
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1105
    """a set containing all revisions in the repo
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1106
24204
d2de20e1451f revset: extend fullreposet to make "null" revision magically appears in set
Yuya Nishihara <yuya@tcha.org>
parents: 24203
diff changeset
  1107
    This class exists to host special optimization and magic to handle virtual
d2de20e1451f revset: extend fullreposet to make "null" revision magically appears in set
Yuya Nishihara <yuya@tcha.org>
parents: 24203
diff changeset
  1108
    revisions such as "null".
22508
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1109
    """
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1110
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1111
    def __init__(self, repo):
32818
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
  1112
        super(fullreposet, self).__init__(0, len(repo), True,
9ddb18ae342e smartset: extract spanset factory to make it constructed without a repo
Yuya Nishihara <yuya@tcha.org>
parents: 32817
diff changeset
  1113
                                          repo.changelog.filteredrevs)
22508
2434c68d82a8 revert: add a fullreposet class
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22504
diff changeset
  1114
22510
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1115
    def __and__(self, other):
23139
e53f6b72a0e4 spelling: fixes from proofreading of spell checker issues
Mads Kiilerich <madski@unity3d.com>
parents: 23127
diff changeset
  1116
        """As self contains the whole repo, all of the other set should also be
e53f6b72a0e4 spelling: fixes from proofreading of spell checker issues
Mads Kiilerich <madski@unity3d.com>
parents: 23127
diff changeset
  1117
        in self. Therefore `self & other = other`.
22510
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1118
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1119
        This boldly assumes the other contains valid revs only.
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1120
        """
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1121
        # other not a smartset, make is so
22883
e7b8cf352614 fullreposet: detect smartset using "isascending" instead of "set"
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22882
diff changeset
  1122
        if not util.safehasattr(other, 'isascending'):
22510
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1123
            # filter out hidden revision
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1124
            # (this boldly assumes all smartset are pure)
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1125
            #
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1126
            # `other` was used with "&", let's assume this is a set like
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1127
            # object.
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1128
            other = baseset(other - self._hiddenrevs)
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1129
23827
4982fade9733 revset: simplify fullreposet.__and__ to call sort() with boolean flag
Yuya Nishihara <yuya@tcha.org>
parents: 23822
diff changeset
  1130
        other.sort(reverse=self.isdescending())
22510
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1131
        return other
911f5a6579d1 revset: fast implementation for fullreposet.__and__
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22509
diff changeset
  1132
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
  1133
def prettyformat(revs):
24458
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1134
    lines = []
36265
b44fac3a49fb py3: factor out byterepr() which returns an asciified value on py3
Yuya Nishihara <yuya@tcha.org>
parents: 35904
diff changeset
  1135
    rs = pycompat.byterepr(revs)
24458
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1136
    p = 0
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1137
    while p < len(rs):
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1138
        q = rs.find('<', p + 1)
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1139
        if q < 0:
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1140
            q = len(rs)
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1141
        l = rs.count('<', 0, p) - rs.count('>', 0, p)
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1142
        assert l >= 0
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1143
        lines.append((l, rs[p:q].rstrip()))
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1144
        p = q
7d87f672d069 debugrevspec: show nesting structure of smartsets if verbose
Yuya Nishihara <yuya@tcha.org>
parents: 24457
diff changeset
  1145
    return '\n'.join('  ' * l + s for l, s in lines)