commit 611b0fa94ce935235599a4bf666aef88e46f0b3b
author Victor Stinner <victor.stinner@gmail.com> Wed Sep 14 15:02:01 2016 +0200
committer Victor Stinner <victor.stinner@gmail.com> Wed Sep 14 15:02:01 2016 +0200
tree fe11eeefc011436f6965e2a1b0283540d57f4275
parent 4659ccff704431e23bd3635c9d6beb33551d62b8

Add _PyDict_CheckConsistency()

Issue #28127: Add a function to check that a dictionary remains consistent
after any change.

By default, tables are not checked, only basic attributes. Define DEBUG_PYDICT
(ex: gcc -D DEBUG_PYDICT) to also check dictionary "content".

Objects/dictobject.c

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 06c54b5..0476442 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -310,7 +310,6 @@
 #define DK_MASK(dk) (((dk)->dk_size)-1)
 #define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
 
-
 /* lookup indices.  returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
 static inline Py_ssize_t
 dk_get_index(PyDictKeysObject *keys, Py_ssize_t i)
@@ -433,6 +432,78 @@
 
 #define Py_EMPTY_KEYS &empty_keys_struct
 
+/* Uncomment to check the dict content in _PyDict_CheckConsistency() */
+/* #define DEBUG_PYDICT */
+
+
+#ifdef Py_DEBUG
+static int
+_PyDict_CheckConsistency(PyDictObject *mp)
+{
+    PyDictKeysObject *keys = mp->ma_keys;
+    int splitted = _PyDict_HasSplitTable(mp);
+    Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
+#ifdef DEBUG_PYDICT
+    PyDictKeyEntry *entries = DK_ENTRIES(keys);
+    Py_ssize_t i;
+#endif
+
+    assert(0 <= mp->ma_used && mp->ma_used <= usable);
+    assert(IS_POWER_OF_2(keys->dk_size));
+    assert(0 <= keys->dk_usable
+           && keys->dk_usable <= usable);
+    assert(0 <= keys->dk_nentries
+           && keys->dk_nentries <= usable);
+    assert(keys->dk_usable + keys->dk_nentries <= usable);
+
+    if (!splitted) {
+        /* combined table */
+        assert(keys->dk_refcnt == 1);
+    }
+
+#ifdef DEBUG_PYDICT
+    for (i=0; i < keys->dk_size; i++) {
+        Py_ssize_t ix = dk_get_index(keys, i);
+        assert(DKIX_DUMMY <= ix && ix <= usable);
+    }
+
+    for (i=0; i < usable; i++) {
+        PyDictKeyEntry *entry = &entries[i];
+        PyObject *key = entry->me_key;
+
+        if (key != NULL) {
+            if (PyUnicode_CheckExact(key)) {
+                Py_hash_t hash = ((PyASCIIObject *)key)->hash;
+                assert(hash != -1);
+                assert(entry->me_hash == hash);
+            }
+            else {
+                /* test_dict fails if PyObject_Hash() is called again */
+                assert(entry->me_hash != -1);
+            }
+            if (!splitted) {
+                assert(entry->me_value != NULL);
+            }
+        }
+
+        if (splitted) {
+            assert(entry->me_value == NULL);
+        }
+    }
+
+    if (splitted) {
+        /* splitted table */
+        for (i=0; i < mp->ma_used; i++) {
+            assert(mp->ma_values[i] != NULL);
+        }
+    }
+#endif
+
+    return 1;
+}
+#endif
+
+
 static PyDictKeysObject *new_keys_object(Py_ssize_t size)
 {
     PyDictKeysObject *dk;
@@ -523,6 +594,7 @@
     mp->ma_values = values;
     mp->ma_used = 0;
     mp->ma_version_tag = DICT_NEXT_VERSION();
+    assert(_PyDict_CheckConsistency(mp));
     return (PyObject *)mp;
 }
 
@@ -1089,6 +1161,7 @@
         mp->ma_keys->dk_usable--;
         mp->ma_keys->dk_nentries++;
         assert(mp->ma_keys->dk_usable >= 0);
+        assert(_PyDict_CheckConsistency(mp));
         return 0;
     }
 
@@ -1098,6 +1171,7 @@
     if (old_value != NULL) {
         *value_addr = value;
         mp->ma_version_tag = DICT_NEXT_VERSION();
+        assert(_PyDict_CheckConsistency(mp));
 
         Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
         return 0;
@@ -1109,6 +1183,7 @@
     *value_addr = value;
     mp->ma_used++;
     mp->ma_version_tag = DICT_NEXT_VERSION();
+    assert(_PyDict_CheckConsistency(mp));
     return 0;
 }
 
@@ -1567,6 +1642,8 @@
     ep->me_key = NULL;
     Py_DECREF(old_key);
     Py_DECREF(old_value);
+
+    assert(_PyDict_CheckConsistency(mp));
     return 0;
 }
 
@@ -1603,6 +1680,7 @@
        assert(oldkeys->dk_refcnt == 1);
        DK_DECREF(oldkeys);
     }
+    assert(_PyDict_CheckConsistency(mp));
 }
 
 /* Returns -1 if no more items (or op is not a dict),
@@ -1750,6 +1828,8 @@
     old_key = ep->me_key;
     ep->me_key = NULL;
     Py_DECREF(old_key);
+
+    assert(_PyDict_CheckConsistency(mp));
     return old_value;
 }
 
@@ -2287,6 +2367,7 @@
     }
 
     i = 0;
+    assert(_PyDict_CheckConsistency((PyDictObject *)d));
     goto Return;
 Fail:
     Py_XDECREF(item);
@@ -2413,6 +2494,7 @@
             /* Iterator completed, via error */
             return -1;
     }
+    assert(_PyDict_CheckConsistency((PyDictObject *)a));
     return 0;
 }
 
@@ -2694,9 +2776,11 @@
         mp->ma_keys->dk_nentries++;
         mp->ma_used++;
         mp->ma_version_tag = DICT_NEXT_VERSION();
+        assert(_PyDict_CheckConsistency(mp));
     }
-    else
+    else {
         val = *value_addr;
+    }
     return val;
 }
 
@@ -2788,6 +2872,7 @@
     mp->ma_keys->dk_nentries = i;
     mp->ma_used--;
     mp->ma_version_tag = DICT_NEXT_VERSION();
+    assert(_PyDict_CheckConsistency(mp));
     return res;
 }
 
@@ -3012,6 +3097,7 @@
         Py_DECREF(self);
         return NULL;
     }
+    assert(_PyDict_CheckConsistency(d));
     return self;
 }