This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1780

smartset: split generatorset classes to avoid cycle
ClosedPublic

Authored by indygreg on Dec 27 2017, 1:25 PM.

Details

Reviewers
quark
yuja
Group Reviewers
hg-reviewers
Commits
rHG12a46ad67a3c: smartset: split generatorset classes to avoid cycle
Summary

I uncovered a cycle manifesting in a memory leak by running
hgperfrevset '::tip'. The cycle was due to generatorset.init
assigning a bound method to self.contains. Internet sleuthing
revealed that assigning a bound method to an instance attribute
always creates a cycle.

This commit creates two new variants of generatorset for the special
cases of ascending and descending generators. The special
implementations of contains have been extracted to these classes
where they are defined as contains.

generatorset now implements new and changes the spawned type to
one of the new classes if needed.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg created this revision.Dec 27 2017, 1:25 PM
quark accepted this revision.Dec 27 2017, 2:13 PM
quark added a subscriber: quark.
quark added inline comments.
mercurial/smartset.py
817

@staticmethod could be a simpler way to break cycles.

yuja accepted this revision.Dec 28 2017, 7:24 AM
yuja added a subscriber: yuja.

Queued, thanks. I've made asc/desc classes private as their constructor
behavior is weird.

@staticmethod could be a simpler way to break cycles.

Subclassing is a better tool in this case since we want to override __contains__,
which can't be replaced by __dict__['__contains__'].

This revision is now accepted and ready to land.Dec 28 2017, 7:24 AM
Closed by commit rHG12a46ad67a3c: smartset: split generatorset classes to avoid cycle (authored by indygreg). · Explain WhyDec 28 2017, 8:19 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/smartset.py (87 lines)
Mtests/test-revset.t (2 lines)
Mtests/test-revset2.t (6 lines)

Diff 4658

mercurial/smartset.py

When asked for membership it generates values until either it finds the When asked for membership it generates values until either it finds the
requested one or has gone through all the elements in the generator requested one or has gone through all the elements in the generator
>>> xs = generatorset([0, 1, 4], iterasc=True) >>> xs = generatorset([0, 1, 4], iterasc=True)
>>> assert xs.last() == xs.last() >>> assert xs.last() == xs.last()
>>> xs.last() # cached >>> xs.last() # cached
4 4
""" """
def __new__(cls, gen, iterasc=None):
if iterasc is None:
typ = cls
elif iterasc:
typ = _generatorsetasc
else:
typ = _generatorsetdesc
return super(generatorset, cls).__new__(typ)
def __init__(self, gen, iterasc=None): def __init__(self, gen, iterasc=None):
""" """
gen: a generator producing the values for the generatorset. gen: a generator producing the values for the generatorset.
""" """
self._gen = gen self._gen = gen
self._asclist = None self._asclist = None
self._cache = {} self._cache = {}
self._genlist = [] self._genlist = []
self._finished = False self._finished = False
self._ascending = True self._ascending = True
if iterasc is not None:
if iterasc:
self.fastasc = self._iterator
self.__contains__ = self._asccontains
else:
self.fastdesc = self._iterator
self.__contains__ = self._desccontains
def __nonzero__(self): def __nonzero__(self):
# Do not use 'for r in self' because it will enforce the iteration # Do not use 'for r in self' because it will enforce the iteration
# order (default ascending), possibly unrolling a whole descending # order (default ascending), possibly unrolling a whole descending
# iterator. # iterator.
if self._genlist: if self._genlist:
return True return True
for r in self._consumegen(): for r in self._consumegen():
# Use new values only, as existing values would be cached. # Use new values only, as existing values would be cached.
for l in self._consumegen(): for l in self._consumegen():
if l == x: if l == x:
return True return True
self._cache[x] = False self._cache[x] = False
return False return False
def _asccontains(self, x):
quarkUnsubmitted
Not Done

@staticmethod could be a simpler way to break cycles.

quark: `@staticmethod` could be a simpler way to break cycles.
"""version of contains optimised for ascending generator"""
if x in self._cache:
return self._cache[x]
# Use new values only, as existing values would be cached.
for l in self._consumegen():
if l == x:
return True
if l > x:
break
self._cache[x] = False
return False
def _desccontains(self, x):
"""version of contains optimised for descending generator"""
if x in self._cache:
return self._cache[x]
# Use new values only, as existing values would be cached.
for l in self._consumegen():
if l == x:
return True
if l < x:
break
self._cache[x] = False
return False
def __iter__(self): def __iter__(self):
if self._ascending: if self._ascending:
it = self.fastasc it = self.fastasc
else: else:
it = self.fastdesc it = self.fastdesc
if it is not None: if it is not None:
return it() return it()
# we need to consume the iterator # we need to consume the iterator
# we need to consume all and try again # we need to consume all and try again
for x in self._consumegen(): for x in self._consumegen():
pass pass
return self.last() return self.last()
return next(it(), None) return next(it(), None)
def __repr__(self): def __repr__(self):
d = {False: '-', True: '+'}[self._ascending] d = {False: '-', True: '+'}[self._ascending]
return '<%s%s>' % (type(self).__name__, d) return '<%s%s>' % (type(self).__name__.lstrip('_'), d)
class _generatorsetasc(generatorset):
"""Special case of generatorset optimized for ascending generators."""
fastasc = generatorset._iterator
def __contains__(self, x):
if x in self._cache:
return self._cache[x]
# Use new values only, as existing values would be cached.
for l in self._consumegen():
if l == x:
return True
if l > x:
break
self._cache[x] = False
return False
class _generatorsetdesc(generatorset):
"""Special case of generatorset optimized for descending generators."""
fastdesc = generatorset._iterator
def __contains__(self, x):
if x in self._cache:
return self._cache[x]
# Use new values only, as existing values would be cached.
for l in self._consumegen():
if l == x:
return True
if l < x:
break
self._cache[x] = False
return False
def spanset(repo, start=0, end=None): def spanset(repo, start=0, end=None):
"""Create a spanset that represents a range of repository revisions """Create a spanset that represents a range of repository revisions
start: first revision included the set (default to 0) start: first revision included the set (default to 0)
end: first revision excluded (last+1) (default to len(repo)) end: first revision excluded (last+1) (default to len(repo))
Spanset will be descending if `end` < `start`. Spanset will be descending if `end` < `start`.

tests/test-revset.t

0 0
1 1
Test scmutil.revsingle() should return the last revision Test scmutil.revsingle() should return the last revision
$ hg debugrevspec -s 'last(0::)' $ hg debugrevspec -s 'last(0::)'
* set: * set:
<baseset slice=0:1 <baseset slice=0:1
<generatorset->> <generatorsetasc->>
9 9
$ hg identify -r '0::' --num $ hg identify -r '0::' --num
9 9
Test matching Test matching
$ log 'matching(6)' $ log 'matching(6)'
6 6

tests/test-revset2.t

(symbol '1') (symbol '1')
(symbol '5'))) (symbol '5')))
(func (func
(symbol 'ancestors') (symbol 'ancestors')
(symbol '4')))) (symbol '4'))))
* set: * set:
<addset <addset
<baseset- [1, 3, 5]>, <baseset- [1, 3, 5]>,
<generatorset+>> <generatorsetdesc+>>
5 5
3 3
1 1
0 0
2 2
4 4
$ try 'sort(ancestors(4) or reverse(1::5))' $ try 'sort(ancestors(4) or reverse(1::5))'
(func (func
(symbol 'sort') (symbol 'sort')
(or (or
(list (list
(func (func
(symbol 'ancestors') (symbol 'ancestors')
(symbol '4')) (symbol '4'))
(func (func
(symbol 'reverse') (symbol 'reverse')
(dagrange (dagrange
(symbol '1') (symbol '1')
(symbol '5')))))) (symbol '5'))))))
* set: * set:
<addset+ <addset+
<generatorset+>, <generatorsetdesc+>,
<baseset- [1, 3, 5]>> <baseset- [1, 3, 5]>>
0 0
1 1
2 2
3 3
4 4
5 5
(symbol 'sincem') (symbol 'sincem')
* expanded: * expanded:
(func (func
(symbol 'descendants') (symbol 'descendants')
(func (func
(symbol 'merge') (symbol 'merge')
None)) None))
* set: * set:
<generatorset+> <generatorsetasc+>
6 6
7 7
test infinite recursion test infinite recursion
$ echo 'recurse1 = recurse2' >> .hg/hgrc $ echo 'recurse1 = recurse2' >> .hg/hgrc
$ echo 'recurse2 = recurse1' >> .hg/hgrc $ echo 'recurse2 = recurse1' >> .hg/hgrc
$ try recurse1 $ try recurse1