Issue #29203: functools.lru_cache() now respects PEP 468

rhettinger · rhettinger · commit 4ee39141e84c · 2017-01-08T17:28:20.000-08:00
diff --git a/Lib/functools.py b/Lib/functools.py
@@ -421,7 +421,7 @@ def __hash__(self):
 def _make_key(args, kwds, typed,
              kwd_mark = (object(),),
              fasttypes = {int, str, frozenset, type(None)},
-             sorted=sorted, tuple=tuple, type=type, len=len):
+             tuple=tuple, type=type, len=len):
     """Make a cache key from optionally typed positional and keyword arguments
 
     The key is constructed in a way that is flat as possible rather than
@@ -434,14 +434,13 @@ def _make_key(args, kwds, typed,
     """
     key = args
     if kwds:
-        sorted_items = sorted(kwds.items())
         key += kwd_mark
-        for item in sorted_items:
+        for item in kwds.items():
             key += item
     if typed:
         key += tuple(type(v) for v in args)
         if kwds:
-            key += tuple(type(v) for k, v in sorted_items)
+            key += tuple(type(v) for v in kwds.values())
     elif len(key) == 1 and type(key[0]) in fasttypes:
         return key[0]
     return _HashedSeq(key)
diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py
@@ -1306,6 +1306,16 @@ def fib(n):
         self.assertEqual(fib.cache_info(),
             self.module._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
 
+    def test_kwargs_order(self):
+        # PEP 468: Preserving Keyword Argument Order
+        @self.module.lru_cache(maxsize=10)
+        def f(**kwargs):
+            return list(kwargs.items())
+        self.assertEqual(f(a=1, b=2), [('a', 1), ('b', 2)])
+        self.assertEqual(f(b=2, a=1), [('b', 2), ('a', 1)])
+        self.assertEqual(f.cache_info(),
+            self.module._CacheInfo(hits=0, misses=2, maxsize=10, currsize=2))
+
     def test_lru_cache_decoration(self):
         def f(zomg: 'zomg_annotation'):
             """f doc string"""
diff --git a/Misc/NEWS b/Misc/NEWS
@@ -47,6 +47,10 @@ Library
 - Issue #28961: Fix unittest.mock._Call helper: don't ignore the name parameter
   anymore. Patch written by Jiajun Huang.
 
+- Issue #29203:  functools.lru_cache() now respects PEP 468 and preserves
+  the order of keyword arguments.  f(a=1, b=2) is now cached separately
+  from f(b=2, a=1) since both calls could potentially give different results.
+
 - Issue #15812: inspect.getframeinfo() now correctly shows the first line of
   a context.  Patch by Sam Breese.
 
diff --git a/Modules/_functoolsmodule.c b/Modules/_functoolsmodule.c
@@ -704,73 +704,60 @@ static PyTypeObject lru_cache_type;
 static PyObject *
 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
 {
-    PyObject *key, *sorted_items;
-    Py_ssize_t key_size, pos, key_pos;
+    PyObject *key, *keyword, *value;
+    Py_ssize_t key_size, pos, key_pos, kwds_size;
 
     /* short path, key will match args anyway, which is a tuple */
     if (!typed && !kwds) {
         Py_INCREF(args);
         return args;
     }
 
-    if (kwds && PyDict_Size(kwds) > 0) {
-        sorted_items = PyDict_Items(kwds);
-        if (!sorted_items)
-            return NULL;
-        if (PyList_Sort(sorted_items) < 0) {
-            Py_DECREF(sorted_items);
-            return NULL;
-        }
-    } else
-        sorted_items = NULL;
+    kwds_size = kwds ? PyDict_Size(kwds) : 0;
+    assert(kwds_size >= 0);
 
     key_size = PyTuple_GET_SIZE(args);
-    if (sorted_items)
-        key_size += PyList_GET_SIZE(sorted_items);
+    if (kwds_size)
+        key_size += kwds_size * 2 + 1;
     if (typed)
-        key_size *= 2;
-    if (sorted_items)
-        key_size++;
+        key_size += PyTuple_GET_SIZE(args) + kwds_size;
 
     key = PyTuple_New(key_size);
     if (key == NULL)
-        goto done;
+        return NULL;
 
     key_pos = 0;
     for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
         PyObject *item = PyTuple_GET_ITEM(args, pos);
         Py_INCREF(item);
         PyTuple_SET_ITEM(key, key_pos++, item);
     }
-    if (sorted_items) {
+    if (kwds_size) {
         Py_INCREF(kwd_mark);
         PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
-        for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
-            PyObject *item = PyList_GET_ITEM(sorted_items, pos);
-            Py_INCREF(item);
-            PyTuple_SET_ITEM(key, key_pos++, item);
+        for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
+            Py_INCREF(keyword);
+            PyTuple_SET_ITEM(key, key_pos++, keyword);
+            Py_INCREF(value);
+            PyTuple_SET_ITEM(key, key_pos++, value);
         }
+        assert(key_pos == PyTuple_GET_SIZE(args) + kwds_size * 2 + 1);
     }
     if (typed) {
         for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
             PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
             Py_INCREF(item);
             PyTuple_SET_ITEM(key, key_pos++, item);
         }
-        if (sorted_items) {
-            for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
-                PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
-                PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
+        if (kwds_size) {
+            for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
+                PyObject *item = (PyObject *)Py_TYPE(value);
                 Py_INCREF(item);
                 PyTuple_SET_ITEM(key, key_pos++, item);
             }
         }
     }
     assert(key_pos == key_size);
-
-done:
-    if (sorted_items)
-        Py_DECREF(sorted_items);
     return key;
 }
 
