Issue #14159: Fix the len() of weak containers (WeakSet, WeakKeyDictionary, WeakValueDictionary) to return a better approximation when some objects are dead or dying.

Moreover, the implementation is now O(1) rather than O(n).
Thanks to Yury Selivanov for reporting.

5 files changed, 115 insertions, 3 deletions

diff --git a/Lib/_weakrefset.py b/Lib/_weakrefset.py
index 42653699a3..f34aa864bc 100644
--- a/Lib/_weakrefset.py
+++ b/Lib/_weakrefset.py
@@ -63,7 +63,7 @@ class WeakSet:
                     yield item
 
     def __len__(self):
-        return sum(x() is not None for x in self.data)
+        return len(self.data) - len(self._pending_removals)
 
     def __contains__(self, item):
         try:
diff --git a/Lib/test/test_weakref.py b/Lib/test/test_weakref.py
index 8b5bbc3d36..74b9a87852 100644
--- a/Lib/test/test_weakref.py
+++ b/Lib/test/test_weakref.py
@@ -812,11 +812,71 @@ class Object:
     def __hash__(self):
         return hash(self.arg)
 
+class RefCycle:
+    def __init__(self):
+        self.cycle = self
+
 
 class MappingTestCase(TestBase):
 
     COUNT = 10
 
+    def check_len_cycles(self, dict_type, cons):
+        N = 20
+        items = [RefCycle() for i in range(N)]
+        dct = dict_type(cons(o) for o in items)
+        # Keep an iterator alive
+        it = dct.items()
+        try:
+            next(it)
+        except StopIteration:
+            pass
+        del items
+        gc.collect()
+        n1 = len(dct)
+        del it
+        gc.collect()
+        n2 = len(dct)
+        # one item may be kept alive inside the iterator
+        self.assertIn(n1, (0, 1))
+        self.assertEqual(n2, 0)
+
+    def test_weak_keyed_len_cycles(self):
+        self.check_len_cycles(weakref.WeakKeyDictionary, lambda k: (k, 1))
+
+    def test_weak_valued_len_cycles(self):
+        self.check_len_cycles(weakref.WeakValueDictionary, lambda k: (1, k))
+
+    def check_len_race(self, dict_type, cons):
+        # Extended sanity checks for len() in the face of cyclic collection
+        self.addCleanup(gc.set_threshold, *gc.get_threshold())
+        for th in range(1, 100):
+            N = 20
+            gc.collect(0)
+            gc.set_threshold(th, th, th)
+            items = [RefCycle() for i in range(N)]
+            dct = dict_type(cons(o) for o in items)
+            del items
+            # All items will be collected at next garbage collection pass
+            it = dct.items()
+            try:
+                next(it)
+            except StopIteration:
+                pass
+            n1 = len(dct)
+            del it
+            n2 = len(dct)
+            self.assertGreaterEqual(n1, 0)
+            self.assertLessEqual(n1, N)
+            self.assertGreaterEqual(n2, 0)
+            self.assertLessEqual(n2, n1)
+
+    def test_weak_keyed_len_race(self):
+        self.check_len_race(weakref.WeakKeyDictionary, lambda k: (k, 1))
+
+    def test_weak_valued_len_race(self):
+        self.check_len_race(weakref.WeakValueDictionary, lambda k: (1, k))
+
     def test_weak_values(self):
         #
         #  This exercises d.copy(), d.items(), d[], del d[], len(d).
diff --git a/Lib/test/test_weakset.py b/Lib/test/test_weakset.py
index 3cddf40c24..35db7a6232 100644
--- a/Lib/test/test_weakset.py
+++ b/Lib/test/test_weakset.py
@@ -17,6 +17,10 @@ import contextlib
 class Foo:
     pass
 
+class RefCycle:
+    def __init__(self):
+        self.cycle = self
+
 
 class TestWeakSet(unittest.TestCase):
 
@@ -359,6 +363,49 @@ class TestWeakSet(unittest.TestCase):
             s.clear()
         self.assertEqual(len(s), 0)
 
+    def test_len_cycles(self):
+        N = 20
+        items = [RefCycle() for i in range(N)]
+        s = WeakSet(items)
+        del items
+        it = iter(s)
+        try:
+            next(it)
+        except StopIteration:
+            pass
+        gc.collect()
+        n1 = len(s)
+        del it
+        gc.collect()
+        n2 = len(s)
+        # one item may be kept alive inside the iterator
+        self.assertIn(n1, (0, 1))
+        self.assertEqual(n2, 0)
+
+    def test_len_race(self):
+        # Extended sanity checks for len() in the face of cyclic collection
+        self.addCleanup(gc.set_threshold, *gc.get_threshold())
+        for th in range(1, 100):
+            N = 20
+            gc.collect(0)
+            gc.set_threshold(th, th, th)
+            items = [RefCycle() for i in range(N)]
+            s = WeakSet(items)
+            del items
+            # All items will be collected at next garbage collection pass
+            it = iter(s)
+            try:
+                next(it)
+            except StopIteration:
+                pass
+            n1 = len(s)
+            del it
+            n2 = len(s)
+            self.assertGreaterEqual(n1, 0)
+            self.assertLessEqual(n1, N)
+            self.assertGreaterEqual(n2, 0)
+            self.assertLessEqual(n2, n1)
+
 
 def test_main(verbose=None):
     support.run_unittest(TestWeakSet)
diff --git a/Lib/weakref.py b/Lib/weakref.py
index 468f8f1029..fcb6b74d1b 100644
--- a/Lib/weakref.py
+++ b/Lib/weakref.py
@@ -78,7 +78,7 @@ class WeakValueDictionary(collections.MutableMapping):
         del self.data[key]
 
     def __len__(self):
-        return sum(wr() is not None for wr in self.data.values())
+        return len(self.data) - len(self._pending_removals)
 
     def __contains__(self, key):
         try:
@@ -290,7 +290,7 @@ class WeakKeyDictionary(collections.MutableMapping):
         return self.data[ref(key)]
 
     def __len__(self):
-        return len(self.data)
+        return len(self.data) - len(self._pending_removals)
 
     def __repr__(self):
         return "<WeakKeyDictionary at %s>" % id(self)
diff --git a/Misc/NEWS b/Misc/NEWS
index d8dbe791d4..c1385f3fad 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -127,6 +127,11 @@ Core and Builtins
 Library
 -------
 
+- Issue #14159: Fix the len() of weak containers (WeakSet, WeakKeyDictionary,
+  WeakValueDictionary) to return a better approximation when some objects
+  are dead or dying.  Moreover, the implementation is now O(1) rather than
+  O(n).
+
 - Issue #13125: Silence spurious test_lib2to3 output when in non-verbose mode.
   Patch by Mikhail Novikov.