From 886128f4f8b30b7e3623418eab063a3a8dd3495c Mon Sep 17 00:00:00 2001
From: Tim Peters <tim.peters@gmail.com>
Date: Sun, 25 May 2003 01:45:11 +0000
Subject: SF 742860: WeakKeyDictionary __delitem__ uses iterkeys

Someone review this, please!  Final releases are getting close, Fred
(the weakref guy) won't be around until Tuesday, and the pre-patch
code can indeed raise spurious RuntimeErrors in the presence of
threads or mutating comparison functions.

See the bug report for my confusions:  I can't see any reason for why
__delitem__ iterated over the keys.  The new one-liner implementation
is much faster, can't raise RuntimeError, and should be better-behaved
in all respects wrt threads.

New tests test_weak_keyed_bad_delitem and
test_weak_keyed_cascading_deletes fail before this patch.

Bugfix candidate for 2.2.3 too, if someone else agrees with this patch.
---
 Lib/test/test_weakref.py | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
 Lib/weakref.py           |  6 +-----
 Misc/NEWS                |  6 ++++++
 3 files changed, 58 insertions(+), 5 deletions(-)

diff --git a/Lib/test/test_weakref.py b/Lib/test/test_weakref.py
index 7e7d068..c5fbb8d 100644
--- a/Lib/test/test_weakref.py
+++ b/Lib/test/test_weakref.py
@@ -516,6 +516,57 @@ class MappingTestCase(TestBase):
         self.assert_(len(d) == 1)
         self.assert_(d.items() == [('something else', o2)])
 
+    def test_weak_keyed_bad_delitem(self):
+        d = weakref.WeakKeyDictionary()
+        o = Object('1')
+        # An attempt to delete an object that isn't there should raise
+        # KetError.  It didn't before 2.3.
+        self.assertRaises(KeyError, d.__delitem__, o)
+
+    def test_weak_keyed_cascading_deletes(self):
+        # SF bug 742860.  For some reason, before 2.3 __delitem__ iterated
+        # over the keys via self.data.iterkeys().  If things vanished from
+        # the dict during this (or got added), that caused a RuntimeError.
+
+        d = weakref.WeakKeyDictionary()
+        mutate = False
+
+        class C(object):
+            def __init__(self, i):
+                self.value = i
+            def __hash__(self):
+                return hash(self.value)
+            def __eq__(self, other):
+                if mutate:
+                    # Side effect that mutates the dict, by removing the
+                    # last strong reference to a key.
+                    del objs[-1]
+                return self.value == other.value
+
+        objs = [C(i) for i in range(4)]
+        for o in objs:
+            d[o] = o.value
+        del o   # now the only strong references to keys are in objs
+        # Find the order in which iterkeys sees the keys.
+        objs = d.keys()
+        # Reverse it, so that the iteration implementation of __delitem__
+        # has to keep looping to find the first object we delete.
+        objs.reverse()
+        # Turn on mutation in C.__eq__.  The first time thru the loop,
+        # under the iterkeys() business the first comparison will delete
+        # the last item iterkeys() would see, and that causes a
+        #     RuntimeError: dictionary changed size during iteration
+        # when the iterkeys() loop goes around to try comparing the next
+        # key.  After ths was fixed, it just deletes the last object *our*
+        # "for o in obj" loop would have gotten to.
+        mutate = True
+        count = 0
+        for o in objs:
+            count += 1
+            del d[o]
+        self.assertEqual(len(d), 0)
+        self.assertEqual(count, 2)
+
 from test_userdict import TestMappingProtocol
 
 class WeakValueDictionaryTestCase(TestMappingProtocol):
diff --git a/Lib/weakref.py b/Lib/weakref.py
index 838ff5e..09bed65 100644
--- a/Lib/weakref.py
+++ b/Lib/weakref.py
@@ -164,11 +164,7 @@ class WeakKeyDictionary(UserDict.UserDict):
         if dict is not None: self.update(dict)
 
     def __delitem__(self, key):
-        for ref in self.data.iterkeys():
-            o = ref()
-            if o == key:
-                del self.data[ref]
-                return
+        del self.data[ref(key)]
 
     def __getitem__(self, key):
         return self.data[ref(key)]
diff --git a/Misc/NEWS b/Misc/NEWS
index a63f022..bc15f42 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -12,6 +12,12 @@ What's New in Python 2.3 beta 2?
 Core and builtins
 -----------------
 
+- SF bug 742860: WeakKeyDictionary __delitem__ uses iterkeys.  This
+  wasn't as threadsafe as it should be, was very inefficient, and could
+  raise RuntimeError if another thread mutated the dict during
+  __delitem__, or if a comparison function mutated it.  A new
+  implementation of WeakKeyDictionary.__delitem__ repairs all that.
+
 - SF bug 705231:  builtin pow() no longer lets the platform C pow()
   raise -1.0 to integer powers, because (at least) glibc gets it wrong
   in some cases.  The result should be -1.0 if the power is odd and 1.0
-- 
cgit v0.12