Mercurial > hg-stable
changeset 20735:2115e035da11
merge with crew
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Fri, 14 Mar 2014 13:12:45 -0500 |
parents | 4d27c30d58d5 (diff) b93791e0de25 (current diff) |
children | b0203624ab20 |
files | |
diffstat | 2 files changed, 287 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/revset.py Sat Jun 25 02:46:23 2011 +0200 +++ b/mercurial/revset.py Fri Mar 14 13:12:45 2014 -0500 @@ -940,7 +940,7 @@ hs = set() for b, ls in repo.branchmap().iteritems(): hs.update(repo[h].rev() for h in ls) - return subset.filter(lambda r: r in hs) + return baseset(hs).filter(subset.__contains__) def heads(repo, subset, x): """``heads(set)`` @@ -1492,7 +1492,14 @@ l = [] def invert(s): return "".join(chr(255 - ord(c)) for c in s) - for r in getset(repo, subset, s): + revs = getset(repo, subset, s) + if keys == ["rev"]: + revs.sort() + return revs + elif keys == ["-rev"]: + revs.sort(reverse=True) + return revs + for r in revs: c = repo[r] e = [] for k in keys: @@ -2164,41 +2171,82 @@ class baseset(list): """Basic data structure that represents a revset and contains the basic operation that it should be able to perform. + + Every method in this class should be implemented by any smartset class. """ def __init__(self, data): super(baseset, self).__init__(data) self._set = None def ascending(self): + """Sorts the set in ascending order (in place). + + This is part of the mandatory API for smartset.""" self.sort() def descending(self): + """Sorts the set in descending order (in place). + + This is part of the mandatory API for smartset.""" self.sort(reverse=True) def set(self): + """Returns a set or a smartset containing all the elements. + + The returned structure should be the fastest option for membership + testing. + + This is part of the mandatory API for smartset.""" if not self._set: self._set = set(self) return self._set - def __sub__(self, x): - if isinstance(x, baseset): - s = x.set() + def __sub__(self, other): + """Returns a new object with the substraction of the two collections. + + This is part of the mandatory API for smartset.""" + if isinstance(other, baseset): + s = other.set() else: - s = set(x) + s = set(other) return baseset(self.set() - s) - def __and__(self, x): - if isinstance(x, baseset): - x = x.set() - return baseset([y for y in self if y in x]) + def __and__(self, other): + """Returns a new object with the intersection of the two collections. - def __add__(self, x): + This is part of the mandatory API for smartset.""" + if isinstance(other, baseset): + other = other.set() + return baseset([y for y in self if y in other]) + + def __add__(self, other): + """Returns a new object with the union of the two collections. + + This is part of the mandatory API for smartset.""" s = self.set() - l = [r for r in x if r not in s] + l = [r for r in other if r not in s] return baseset(list(self) + l) - def filter(self, l): - return lazyset(self, l) + def isascending(self): + """Returns True if the collection is ascending order, False if not. + + This is part of the mandatory API for smartset.""" + return False + + def isdescending(self): + """Returns True if the collection is descending order, False if not. + + This is part of the mandatory API for smartset.""" + return False + + def filter(self, condition): + """Returns this smartset filtered by condition as a new smartset. + + `condition` is a callable which takes a revision number and returns a + boolean. + + This is part of the mandatory API for smartset.""" + return lazyset(self, condition) class lazyset(object): """Duck type for baseset class which iterates lazily over the revisions in @@ -2235,7 +2283,7 @@ return lazyset(self, lambda r: r not in x) def __add__(self, x): - return lazyset(_addset(self, x)) + return _addset(self, x) def __nonzero__(self): for r in self: @@ -2253,8 +2301,8 @@ return l[x] def sort(self, reverse=False): - # Basic implementation to be changed in future patches. - self._subset = baseset(self._subset) + if not util.safehasattr(self._subset, 'sort'): + self._subset = baseset(self._subset) self._subset.sort(reverse=reverse) def reverse(self): @@ -2263,6 +2311,12 @@ def set(self): return set([r for r in self]) + def isascending(self): + return False + + def isdescending(self): + return False + def filter(self, l): return lazyset(self, l) @@ -2293,6 +2347,14 @@ return orderedlazyset(self, lambda r: r not in x, ascending=self._ascending) + def __add__(self, x): + kwargs = {} + if self.isascending() and x.isascending(): + kwargs['ascending'] = True + if self.isdescending() and x.isdescending(): + kwargs['ascending'] = False + return _addset(self, x, **kwargs) + def sort(self, reverse=False): if reverse: if self._ascending: @@ -2302,6 +2364,12 @@ self._subset.sort(reverse=reverse) self._ascending = not reverse + def isascending(self): + return self._ascending + + def isdescending(self): + return not self._ascending + def reverse(self): self._subset.reverse() self._ascending = not self._ascending @@ -2324,23 +2392,121 @@ self._r2 = revs2 self._iter = None self._ascending = ascending + self._genlist = None + + @util.propertycache + def _list(self): + if not self._genlist: + self._genlist = baseset(self._iterator()) + return self._genlist + + def filter(self, condition): + if self._ascending is not None: + return orderedlazyset(self, condition, ascending=self._ascending) + return lazyset(self, condition) + + def ascending(self): + if self._ascending is None: + self.sort() + self._ascending = True + else: + if not self._ascending: + self.reverse() + + def descending(self): + if self._ascending is None: + self.sort(reverse=True) + self._ascending = False + else: + if self._ascending: + self.reverse() + + def __and__(self, other): + filterfunc = other.__contains__ + if self._ascending is not None: + return orderedlazyset(self, filterfunc, ascending=self._ascending) + return lazyset(self, filterfunc) + + def __sub__(self, other): + filterfunc = lambda r: r not in other + if self._ascending is not None: + return orderedlazyset(self, filterfunc, ascending=self._ascending) + return lazyset(self, filterfunc) + + def __add__(self, other): + """When both collections are ascending or descending, preserve the order + """ + kwargs = {} + if self._ascending is not None: + if self.isascending() and other.isascending(): + kwargs['ascending'] = True + if self.isdescending() and other.isdescending(): + kwargs['ascending'] = False + return _addset(self, other, **kwargs) def _iterator(self): + """Iterate over both collections without repeating elements + + If the ascending attribute is not set, iterate over the first one and + then over the second one checking for membership on the first one so we + dont yield any duplicates. + + If the ascending attribute is set, iterate over both collections at the + same time, yielding only one value at a time in the given order. + """ if not self._iter: def gen(): - for r in self._r1: - yield r - s = self._r1.set() - for r in self._r2: - if r not in s: + if self._ascending is None: + for r in self._r1: yield r + s = self._r1.set() + for r in self._r2: + if r not in s: + yield r + else: + iter1 = iter(self._r1) + iter2 = iter(self._r2) + + val1 = None + val2 = None + + choice = max + if self._ascending: + choice = min + try: + # Consume both iterators in an ordered way until one is + # empty + while True: + if val1 is None: + val1 = iter1.next() + if val2 is None: + val2 = iter2.next() + next = choice(val1, val2) + yield next + if val1 == next: + val1 = None + if val2 == next: + val2 = None + except StopIteration: + # Flush any remaining values and consume the other one + it = iter2 + if val1 is not None: + yield val1 + it = iter1 + elif val2 is not None: + # might have been equality and both are empty + yield val2 + for val in it: + yield val + self._iter = _generatorset(gen()) return self._iter def __iter__(self): - for r in self._iterator(): - yield r + if self._genlist: + return iter(self._genlist) + return iter(self._iterator()) def __contains__(self, x): return x in self._r1 or x in self._r2 @@ -2348,6 +2514,30 @@ def set(self): return self + def sort(self, reverse=False): + """Sort the added set + + For this we use the cached list with all the generated values and if we + know they are ascending or descending we can sort them in a smart way. + """ + if self._ascending is None: + self._list.sort(reverse=reverse) + self._ascending = not reverse + else: + if bool(self._ascending) == bool(reverse): + self.reverse() + + def isascending(self): + return self._ascending is not None and self._ascending + + def isdescending(self): + return self._ascending is not None and not self._ascending + + def reverse(self): + self._list.reverse() + if self._ascending is not None: + self._ascending = not self._ascending + class _generatorset(object): """Wrap a generator for lazy iteration @@ -2490,6 +2680,11 @@ return self._contained(x) and not (self._hiddenrevs and rev in self._hiddenrevs) + def __nonzero__(self): + for r in self: + return True + return False + def __and__(self, x): if isinstance(x, baseset): x = x.set() @@ -2507,7 +2702,12 @@ return orderedlazyset(self, lambda r: r not in x, ascending=False) def __add__(self, x): - return lazyset(_addset(self, x)) + kwargs = {} + if self.isascending() and x.isascending(): + kwargs['ascending'] = True + if self.isdescending() and x.isdescending(): + kwargs['ascending'] = False + return _addset(self, x, **kwargs) def __len__(self): if not self._hiddenrevs: @@ -2525,8 +2725,7 @@ return l[x] def sort(self, reverse=False): - # Basic implementation to be changed in future patches. - if reverse: + if bool(reverse) != (self._start > self._end): self.reverse() def reverse(self): @@ -2538,6 +2737,12 @@ def set(self): return self + def isascending(self): + return self._start < self._end + + def isdescending(self): + return self._start > self._end + def filter(self, l): if self._start <= self._end: return orderedlazyset(self, l)
--- a/tests/test-revset.t Sat Jun 25 02:46:23 2011 +0200 +++ b/tests/test-revset.t Fri Mar 14 13:12:45 2014 -0500 @@ -460,6 +460,61 @@ $ log 'tag(tip)' 9 +test sort revset +-------------------------------------------- + +test when adding two unordered revsets + + $ log 'sort(keyword(issue) or modifies(b))' + 4 + 6 + +test when sorting a reversed collection in the same way it is + + $ log 'sort(reverse(all()), -rev)' + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 + + +test when sorting a reversed collection + + $ log 'sort(reverse(all()), rev)' + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + + +test sorting two sorted collections in different orders + + $ log 'sort(outgoing() or reverse(removes(a)), rev)' + 2 + 6 + 8 + 9 + +test sorting two sorted collections in different orders backwards + + $ log 'sort(outgoing() or reverse(removes(a)), -rev)' + 9 + 8 + 6 + 2 + check that conversion to _missingancestors works $ try --optimize '::3 - ::1' (minus