fix a crash in OrderedDict

python · rhettinger · Sep 23, 2024 · Jul 3, 2024 · Jul 3, 2024 · Jul 3, 2024
commit da396cc55067418a1bd4d14fef4b6589a142616f
diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py
@@ -103,6 +103,7 @@ def __new__(cls, /, *args, **kwds):
         self.__root = root = _proxy(self.__hardroot)
         root.prev = root.next = root
         self.__map = {}
+        self.__state = 0
         return self
 
     def __init__(self, other=(), /, **kwds):
@@ -123,6 +124,7 @@ def __setitem__(self, key, value,
             link.prev, link.next, link.key = last, root, key
             last.next = link
             root.prev = proxy(link)
+            self.__state += 1
         dict_setitem(self, key, value)
 
     def __delitem__(self, key, dict_delitem=dict.__delitem__):
@@ -137,6 +139,7 @@ def __delitem__(self, key, dict_delitem=dict.__delitem__):
         link_next.prev = link_prev
         link.prev = None
         link.next = None
+        self.__state += 1
 
     def __iter__(self):
         'od.__iter__() <==> iter(od)'
@@ -160,6 +163,7 @@ def clear(self):
         'od.clear() -> None.  Remove all items from od.'
         root = self.__root
         root.prev = root.next = root
+        self.__state += 1
         self.__map.clear()
         dict.clear(self)
 
@@ -184,6 +188,7 @@ def popitem(self, last=True):
         key = link.key
         del self.__map[key]
         value = dict.pop(self, key)
+        self.__state += 1
         return key, value
 
     def move_to_end(self, key, last=True):
@@ -210,6 +215,7 @@ def move_to_end(self, key, last=True):
             link.next = first
             first.prev = soft_link
             root.next = link
+        self.__state += 1
 
     def __sizeof__(self):
         sizeof = _sys.getsizeof
@@ -218,6 +224,7 @@ def __sizeof__(self):
         size += sizeof(self.__map) * 2          # internal dict and inherited dict
         size += sizeof(self.__hardroot) * n     # link objects
         size += sizeof(self.__root) * n         # proxy objects
+        size += sizeof(self.__state)            # linked list state
         return size
 
     update = __update = _collections_abc.MutableMapping.update
@@ -255,6 +262,7 @@ def pop(self, key, default=__marker):
             link_next.prev = link_prev
             link.prev = None
             link.next = None
+            self.__state += 1
             return result
         if default is marker:
             raise KeyError(key)
@@ -314,8 +322,32 @@ def __eq__(self, other):
         while comparison to a regular mapping is order-insensitive.
 
         '''
+        # The Python implementation is not optimal but matches
+        # the C implementation and the exceptions it may raise.
         if isinstance(other, OrderedDict):
-            return dict.__eq__(self, other) and all(map(_eq, self, other))
+            if not dict.__eq__(self, other):
+                return False
+            state_a, count_a = self.__state, len(self)
+            root_a, curr_a = self.__root, self.__root.next
+            state_b, count_b = other.__state, len(other)
+            root_b, curr_b = other.__root, other.__root.next
+            while True:
+                if curr_a is root_a and curr_b is root_b:
+                    return True
+                if curr_a is root_a or curr_b is root_b:
+                    return False
+                # With the C implementation, calling '==' might have side
+                # effects that would end in segmentation faults, thus the
+                # state and size of the operands need to be checked.
+                res = curr_a.key == curr_b.key
+                if self.__state != state_a or other.__state != state_b:
+                    # changing the size always changes the state
+                    if len(self) != count_a or len(other) != count_b:
+                        raise RuntimeError("OrderedDict changed size during iteration")
+                    raise RuntimeError("OrderedDict mutated during iteration")
+                elif not res:
+                    return False
+                curr_a, curr_b = curr_a.next, curr_b.next
         return dict.__eq__(self, other)
 
     def __ior__(self, other):

diff --git a/Objects/odictobject.c b/Objects/odictobject.c
@@ -699,7 +699,7 @@ _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
 
     _odictnode_KEY(node) = key;
     _odictnode_HASH(node) = hash;
-    _odict_add_tail(od, node);
+    _odict_add_tail(od, node); // this updates 'od_state'
     od->od_fast_nodes[i] = node;
     return 0;
 }
@@ -773,7 +773,7 @@ _odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,
 
     // Now clear the node.
     od->od_fast_nodes[i] = NULL;
-    _odict_remove_node(od, node);
+    _odict_remove_node(od, node); // this updates 'od_state'
     _odictnode_DEALLOC(node);
     return 0;
 }
@@ -796,6 +796,7 @@ _odict_clear_nodes(PyODictObject *od)
         _odictnode_DEALLOC(node);
         node = next;
     }
+    od->od_state++;
 }
 
 /* There isn't any memory management of nodes past this point. */
@@ -806,6 +807,12 @@ _odict_keys_equal(PyODictObject *a, PyODictObject *b)
 {
     _ODictNode *node_a, *node_b;
 
+    // keep operands' state and size to detect undesired mutations
+    const size_t state_a = a->od_state;
+    const Py_ssize_t size_a = PyODict_SIZE(a);
+    const size_t state_b = b->od_state;
+    const Py_ssize_t size_b = PyODict_SIZE(b);
+
     node_a = _odict_FIRST(a);
     node_b = _odict_FIRST(b);
     while (1) {
@@ -820,10 +827,22 @@ _odict_keys_equal(PyODictObject *a, PyODictObject *b)
                                             (PyObject *)_odictnode_KEY(node_a),
                                             (PyObject *)_odictnode_KEY(node_b),
                                             Py_EQ);
-            if (res < 0)
+            if (res < 0) {
                 return res;
-            else if (res == 0)
+            }
+            else if (a->od_state != state_a || b->od_state != state_b) {
+                // If the size changed, then the state must also have changed
+                // since the former changes only if keys are added or removed,
+                // which in turn updates the state.
+                PyErr_SetString(PyExc_RuntimeError,
+                                (size_a != PyODict_SIZE(a) || size_b != PyODict_SIZE(b))
+                                    ? "OrderedDict changed size during iteration"
+                                    : "OrderedDict mutated during iteration");
+                return -1;
+            }
+            else if (res == 0) {
                 return 0;
+            }
 
             /* otherwise it must match, so move on to the next one */
             node_a = _odictnode_NEXT(node_a);