Author: Armin Rigo <[email protected]>
Branch:
Changeset: r91958:3c4fb99e0c59
Date: 2017-07-24 10:07 +0200
http://bitbucket.org/pypy/pypy/changeset/3c4fb99e0c59/
Log: Issue #2612
Simplify gc.get_referrers(). Before, it wasn't guaranteed to return
the opposite result as gc.get_referents().
diff --git a/pypy/module/gc/referents.py b/pypy/module/gc/referents.py
--- a/pypy/module/gc/referents.py
+++ b/pypy/module/gc/referents.py
@@ -47,57 +47,6 @@
# ____________________________________________________________
-class PathEntry(object):
- # PathEntries are nodes of a complete tree of all objects, but
- # built lazily (there is only one branch alive at any time).
- # Each node has a 'gcref' and the list of referents from this gcref.
- def __init__(self, prev, gcref, referents):
- self.prev = prev
- self.gcref = gcref
- self.referents = referents
- self.remaining = len(referents)
-
- def get_most_recent_w_obj(self):
- entry = self
- while entry is not None:
- if entry.gcref:
- w_obj = try_cast_gcref_to_w_root(entry.gcref)
- if w_obj is not None:
- return w_obj
- entry = entry.prev
- return None
-
-def do_get_referrers(w_arg):
- result_w = []
- gcarg = rgc.cast_instance_to_gcref(w_arg)
- roots = [gcref for gcref in rgc.get_rpy_roots() if gcref]
- head = PathEntry(None, rgc.NULL_GCREF, roots)
- while True:
- head.remaining -= 1
- if head.remaining >= 0:
- gcref = head.referents[head.remaining]
- if not rgc.get_gcflag_extra(gcref):
- # not visited so far
- if gcref == gcarg:
- w_obj = head.get_most_recent_w_obj()
- if w_obj is not None:
- result_w.append(w_obj) # found!
- rgc.toggle_gcflag_extra(gcref) # toggle twice
- rgc.toggle_gcflag_extra(gcref)
- head = PathEntry(head, gcref, rgc.get_rpy_referents(gcref))
- else:
- # no more referents to visit
- head = head.prev
- if head is None:
- break
- # done. Clear flags carefully
- rgc.toggle_gcflag_extra(gcarg)
- rgc.clear_gcflag_extra(roots)
- rgc.clear_gcflag_extra([gcarg])
- return result_w
-
-# ____________________________________________________________
-
def _list_w_obj_referents(gcref, result_w):
# Get all W_Root reachable directly from gcref, and add them to
# the list 'result_w'.
@@ -184,9 +133,22 @@
"""Return the list of objects that directly refer to any of objs."""
if not rgc.has_gcflag_extra():
raise missing_operation(space)
+ # xxx uses a lot of memory to make the list of all W_Root objects,
+ # but it's simpler this way and more correct than the previous
+ # version of this code (issue #2612). It is potentially very slow
+ # because each of the n calls to _list_w_obj_referents() could take
+ # O(n) time as well, in theory, but I hope in practice the whole
+ # thing takes much less than O(n^2). We could re-add an algorithm
+ # that visits most objects only once, if needed...
+ all_objects_w = rgc.do_get_objects(try_cast_gcref_to_w_root)
result_w = []
- for w_arg in args_w:
- result_w += do_get_referrers(w_arg)
+ for w_obj in all_objects_w:
+ refs_w = []
+ gcref = rgc.cast_instance_to_gcref(w_obj)
+ _list_w_obj_referents(gcref, refs_w)
+ for w_arg in args_w:
+ if w_arg in refs_w:
+ result_w.append(w_obj)
rgc.assert_no_more_gcflags()
return space.newlist(result_w)
diff --git a/pypy/module/gc/test/test_referents.py
b/pypy/module/gc/test/test_referents.py
--- a/pypy/module/gc/test/test_referents.py
+++ b/pypy/module/gc/test/test_referents.py
@@ -116,3 +116,37 @@
break # found
else:
assert 0, "the tuple (7,) is not found as gc.get_referrers(7)"
+
+
+class AppTestReferentsMore(object):
+
+ def setup_class(cls):
+ from rpython.rlib import rgc
+ cls._backup = [rgc.get_rpy_roots]
+ l4 = cls.space.newlist([])
+ cls.ALL_ROOTS = [l4]
+ cls.w_ALL_ROOTS = cls.space.newlist(cls.ALL_ROOTS)
+ rgc.get_rpy_roots = lambda: (
+ map(rgc._GcRef, cls.ALL_ROOTS) + [rgc.NULL_GCREF]*2)
+ cls.w_runappdirect = cls.space.wrap(option.runappdirect)
+
+ def teardown_class(cls):
+ from rpython.rlib import rgc
+ rgc.get_rpy_roots = cls._backup[0]
+
+ def test_get_referrers(self):
+ import gc
+ class A(object):
+ pass
+ a = A()
+ if not self.runappdirect:
+ l4 = self.ALL_ROOTS[0]
+ l4.append(a) # add 'a' to the list which is in roots
+ lst = gc.get_referrers(A)
+ assert a in lst
+ lst = gc.get_referrers(A)
+ assert a in lst
+ lst = gc.get_referrers(A)
+ assert a in lst
+ lst = gc.get_referrers(A)
+ assert a in lst
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
